Source/cmOrderDirectories.cxx

   1 /*============================================================================
   2   CMake - Cross Platform Makefile Generator
   3   Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
   4
   5   Distributed under the OSI-approved BSD License (the "License");
   6   see accompanying file Copyright.txt for details.
   7
   8   This software is distributed WITHOUT ANY WARRANTY; without even the
   9   implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  10   See the License for more information.
  11 ============================================================================*/
  12 #include "cmOrderDirectories.h"
  13
  14 #include "cmGlobalGenerator.h"
  15 #include "cmSystemTools.h"
  16 #include "cmake.h"
  17
  18 #include <assert.h>
  19
  20 #include <algorithm>
  21
  22 /*
  23 Directory ordering computation.
  24   - Useful to compute a safe runtime library path order
  25   - Need runtime path for supporting INSTALL_RPATH_USE_LINK_PATH
  26   - Need runtime path at link time to pickup transitive link dependencies
  27     for shared libraries.
  28 */
  29
  30 //----------------------------------------------------------------------------
  31 class cmOrderDirectoriesConstraint
  32 {
  33 public:
  34   cmOrderDirectoriesConstraint(cmOrderDirectories* od,
  35                                std::string const& file):
  36     OD(od), GlobalGenerator(od->GlobalGenerator)
  37     {
  38     this->FullPath = file;
  39
  40     if(file.rfind(".framework") != std::string::npos)
  41       {
  42       cmsys::RegularExpression splitFramework;
  43       splitFramework.compile("^(.*)/(.*).framework/(.*)$");
  44       if(splitFramework.find(file) &&
  45         (std::string::npos !=
  46          splitFramework.match(3).find(splitFramework.match(2))))
  47         {
  48         this->Directory = splitFramework.match(1);
  49         this->FileName =
  50           std::string(file.begin() + this->Directory.size() + 1, file.end());
  51         }
  52       }
  53
  54     if(this->FileName.empty())
  55       {
  56       this->Directory = cmSystemTools::GetFilenamePath(file);
  57       this->FileName = cmSystemTools::GetFilenameName(file);
  58       }
  59     }
  60   virtual ~cmOrderDirectoriesConstraint() {}
  61
  62   void AddDirectory()
  63     {
  64     this->DirectoryIndex = this->OD->AddOriginalDirectory(this->Directory);
  65     }
  66
  67   virtual void Report(std::ostream& e) = 0;
  68
  69   void FindConflicts(unsigned int index)
  70     {
  71     for(unsigned int i=0; i < this->OD->OriginalDirectories.size(); ++i)
  72       {
  73       // Check if this directory conflicts with the entry.
  74       std::string const& dir = this->OD->OriginalDirectories[i];
  75       if(dir != this->Directory && this->FindConflict(dir))
  76         {
  77         // The library will be found in this directory but this is not
  78         // the directory named for it.  Add an entry to make sure the
  79         // desired directory comes before this one.
  80         cmOrderDirectories::ConflictPair p(this->DirectoryIndex, index);
  81         this->OD->ConflictGraph[i].push_back(p);
  82         }
  83       }
  84     }
  85
  86   void FindImplicitConflicts(cmOStringStream& w)
  87     {
  88     bool first = true;
  89     for(unsigned int i=0; i < this->OD->OriginalDirectories.size(); ++i)
  90       {
  91       // Check if this directory conflicts with the entry.
  92       std::string const& dir = this->OD->OriginalDirectories[i];
  93       if(dir != this->Directory && this->FindConflict(dir))
  94         {
  95         // The library will be found in this directory but it is
  96         // supposed to be found in an implicit search directory.
  97         if(first)
  98           {
  99           first = false;
 100           w << "  ";
 101           this->Report(w);
 102           w << " in " << this->Directory << " may be hidden by files in:\n";
 103           }
 104         w << "    " << dir << "\n";
 105         }
 106       }
 107     }
 108 protected:
 109   virtual bool FindConflict(std::string const& dir) = 0;
 110
 111   bool FileMayConflict(std::string const& dir, std::string const& name);
 112
 113   cmOrderDirectories* OD;
 114   cmGlobalGenerator* GlobalGenerator;
 115
 116   // The location in which the item is supposed to be found.
 117   std::string FullPath;
 118   std::string Directory;
 119   std::string FileName;
 120
 121   // The index assigned to the directory.
 122   int DirectoryIndex;
 123 };
 124
 125 //----------------------------------------------------------------------------
 126 bool cmOrderDirectoriesConstraint::FileMayConflict(std::string const& dir,
 127                                                    std::string const& name)
 128 {
 129   // Check if the file exists on disk.
 130   std::string file = dir;
 131   file += "/";
 132   file += name;
 133   if(cmSystemTools::FileExists(file.c_str(), true))
 134     {
 135     // The file conflicts only if it is not the same as the original
 136     // file due to a symlink or hardlink.
 137     return !cmSystemTools::SameFile(this->FullPath.c_str(), file.c_str());
 138     }
 139
 140   // Check if the file will be built by cmake.
 141   std::set<cmStdString> const& files =
 142     (this->GlobalGenerator->GetDirectoryContent(dir, false));
 143   std::set<cmStdString>::const_iterator fi = files.find(name);
 144   return fi != files.end();
 145 }
 146
 147 //----------------------------------------------------------------------------
 148 class cmOrderDirectoriesConstraintSOName: public cmOrderDirectoriesConstraint
 149 {
 150 public:
 151   cmOrderDirectoriesConstraintSOName(cmOrderDirectories* od,
 152                                      std::string const& file,
 153                                      const char* soname):
 154     cmOrderDirectoriesConstraint(od, file), SOName(soname? soname : "")
 155     {
 156     if(this->SOName.empty())
 157       {
 158       // Try to guess the soname.
 159       std::string soguess;
 160       if(cmSystemTools::GuessLibrarySOName(file, soguess))
 161         {
 162         this->SOName = soguess;
 163         }
 164       }
 165     }
 166
 167   virtual void Report(std::ostream& e)
 168     {
 169     e << "runtime library [";
 170     if(this->SOName.empty())
 171       {
 172       e << this->FileName;
 173       }
 174     else
 175       {
 176       e << this->SOName;
 177       }
 178     e << "]";
 179     }
 180
 181   virtual bool FindConflict(std::string const& dir);
 182 private:
 183   // The soname of the shared library if it is known.
 184   std::string SOName;
 185 };
 186
 187 //----------------------------------------------------------------------------
 188 bool cmOrderDirectoriesConstraintSOName::FindConflict(std::string const& dir)
 189 {
 190   // Determine which type of check to do.
 191   if(!this->SOName.empty())
 192     {
 193     // We have the library soname.  Check if it will be found.
 194     if(this->FileMayConflict(dir, this->SOName))
 195       {
 196       return true;
 197       }
 198     }
 199   else
 200     {
 201     // We do not have the soname.  Look for files in the directory
 202     // that may conflict.
 203     std::set<cmStdString> const& files =
 204       (this->GlobalGenerator
 205        ->GetDirectoryContent(dir, true));
 206
 207     // Get the set of files that might conflict.  Since we do not
 208     // know the soname just look at all files that start with the
 209     // file name.  Usually the soname starts with the library name.
 210     std::string base = this->FileName;
 211     std::set<cmStdString>::const_iterator first = files.lower_bound(base);
 212     ++base[base.size()-1];
 213     std::set<cmStdString>::const_iterator last = files.upper_bound(base);
 214     if(first != last)
 215       {
 216       return true;
 217       }
 218     }
 219   return false;
 220 }
 221
 222 //----------------------------------------------------------------------------
 223 class cmOrderDirectoriesConstraintLibrary: public cmOrderDirectoriesConstraint
 224 {
 225 public:
 226   cmOrderDirectoriesConstraintLibrary(cmOrderDirectories* od,
 227                                       std::string const& file):
 228     cmOrderDirectoriesConstraint(od, file)
 229     {
 230     }
 231
 232   virtual void Report(std::ostream& e)
 233     {
 234     e << "link library [" << this->FileName << "]";
 235     }
 236
 237   virtual bool FindConflict(std::string const& dir);
 238 };
 239
 240 //----------------------------------------------------------------------------
 241 bool cmOrderDirectoriesConstraintLibrary::FindConflict(std::string const& dir)
 242 {
 243   // We have the library file name.  Check if it will be found.
 244   if(this->FileMayConflict(dir, this->FileName))
 245     {
 246     return true;
 247     }
 248
 249   // Now check if the file exists with other extensions the linker
 250   // might consider.
 251   if(!this->OD->LinkExtensions.empty() &&
 252      this->OD->RemoveLibraryExtension.find(this->FileName))
 253     {
 254     cmStdString lib = this->OD->RemoveLibraryExtension.match(1);
 255     cmStdString ext = this->OD->RemoveLibraryExtension.match(2);
 256     for(std::vector<std::string>::iterator
 257           i = this->OD->LinkExtensions.begin();
 258         i != this->OD->LinkExtensions.end(); ++i)
 259       {
 260       if(*i != ext)
 261         {
 262         std::string fname = lib;
 263         fname += *i;
 264         if(this->FileMayConflict(dir, fname.c_str()))
 265           {
 266           return true;
 267           }
 268         }
 269       }
 270     }
 271   return false;
 272 }
 273
 274 //----------------------------------------------------------------------------
 275 cmOrderDirectories::cmOrderDirectories(cmGlobalGenerator* gg,
 276                                        cmTarget* target,
 277                                        const char* purpose)
 278 {
 279   this->GlobalGenerator = gg;
 280   this->Target = target;
 281   this->Purpose = purpose;
 282   this->Computed = false;
 283 }
 284
 285 //----------------------------------------------------------------------------
 286 cmOrderDirectories::~cmOrderDirectories()
 287 {
 288   for(std::vector<cmOrderDirectoriesConstraint*>::iterator
 289         i = this->ConstraintEntries.begin();
 290       i != this->ConstraintEntries.end(); ++i)
 291     {
 292     delete *i;
 293     }
 294   for(std::vector<cmOrderDirectoriesConstraint*>::iterator
 295         i = this->ImplicitDirEntries.begin();
 296       i != this->ImplicitDirEntries.end(); ++i)
 297     {
 298     delete *i;
 299     }
 300 }
 301
 302 //----------------------------------------------------------------------------
 303 std::vector<std::string> const& cmOrderDirectories::GetOrderedDirectories()
 304 {
 305   if(!this->Computed)
 306     {
 307     this->Computed = true;
 308     this->CollectOriginalDirectories();
 309     this->FindConflicts();
 310     this->OrderDirectories();
 311     }
 312   return this->OrderedDirectories;
 313 }
 314
 315 //----------------------------------------------------------------------------
 316 void cmOrderDirectories::AddRuntimeLibrary(std::string const& fullPath,
 317                                            const char* soname)
 318 {
 319   // Add the runtime library at most once.
 320   if(this->EmmittedConstraintSOName.insert(fullPath).second)
 321     {
 322     // Implicit link directories need special handling.
 323     if(!this->ImplicitDirectories.empty())
 324       {
 325       std::string dir = cmSystemTools::GetFilenamePath(fullPath);
 326
 327       if(fullPath.rfind(".framework") != std::string::npos)
 328         {
 329         cmsys::RegularExpression splitFramework;
 330         splitFramework.compile("^(.*)/(.*).framework/(.*)$");
 331         if(splitFramework.find(fullPath) &&
 332           (std::string::npos !=
 333            splitFramework.match(3).find(splitFramework.match(2))))
 334           {
 335           dir = splitFramework.match(1);
 336           }
 337         }
 338
 339       if(this->ImplicitDirectories.find(dir) !=
 340          this->ImplicitDirectories.end())
 341         {
 342         this->ImplicitDirEntries.push_back(
 343           new cmOrderDirectoriesConstraintSOName(this, fullPath, soname));
 344         return;
 345         }
 346       }
 347
 348     // Construct the runtime information entry for this library.
 349     this->ConstraintEntries.push_back(
 350       new cmOrderDirectoriesConstraintSOName(this, fullPath, soname));
 351     }
 352   else
 353     {
 354     // This can happen if the same library is linked multiple times.
 355     // In that case the runtime information check need be done only
 356     // once anyway.  For shared libs we could add a check in AddItem
 357     // to not repeat them.
 358     }
 359 }
 360
 361 //----------------------------------------------------------------------------
 362 void cmOrderDirectories::AddLinkLibrary(std::string const& fullPath)
 363 {
 364   // Link extension info is required for library constraints.
 365   assert(!this->LinkExtensions.empty());
 366
 367   // Add the link library at most once.
 368   if(this->EmmittedConstraintLibrary.insert(fullPath).second)
 369     {
 370     // Implicit link directories need special handling.
 371     if(!this->ImplicitDirectories.empty())
 372       {
 373       std::string dir = cmSystemTools::GetFilenamePath(fullPath);
 374       if(this->ImplicitDirectories.find(dir) !=
 375          this->ImplicitDirectories.end())
 376         {
 377         this->ImplicitDirEntries.push_back(
 378           new cmOrderDirectoriesConstraintLibrary(this, fullPath));
 379         return;
 380         }
 381       }
 382
 383     // Construct the link library entry.
 384     this->ConstraintEntries.push_back(
 385       new cmOrderDirectoriesConstraintLibrary(this, fullPath));
 386     }
 387 }
 388
 389 //----------------------------------------------------------------------------
 390 void
 391 cmOrderDirectories
 392 ::AddUserDirectories(std::vector<std::string> const& extra)
 393 {
 394   this->UserDirectories.insert(this->UserDirectories.end(),
 395                                extra.begin(), extra.end());
 396 }
 397
 398 //----------------------------------------------------------------------------
 399 void
 400 cmOrderDirectories
 401 ::AddLanguageDirectories(std::vector<std::string> const& dirs)
 402 {
 403   this->LanguageDirectories.insert(this->LanguageDirectories.end(),
 404                                    dirs.begin(), dirs.end());
 405 }
 406
 407 //----------------------------------------------------------------------------
 408 void
 409 cmOrderDirectories
 410 ::SetImplicitDirectories(std::set<cmStdString> const& implicitDirs)
 411 {
 412   this->ImplicitDirectories = implicitDirs;
 413 }
 414
 415 //----------------------------------------------------------------------------
 416 void
 417 cmOrderDirectories
 418 ::SetLinkExtensionInfo(std::vector<std::string> const& linkExtensions,
 419                        std::string const& removeExtRegex)
 420 {
 421   this->LinkExtensions = linkExtensions;
 422   this->RemoveLibraryExtension.compile(removeExtRegex.c_str());
 423 }
 424
 425 //----------------------------------------------------------------------------
 426 void cmOrderDirectories::CollectOriginalDirectories()
 427 {
 428   // Add user directories specified for inclusion.  These should be
 429   // indexed first so their original order is preserved as much as
 430   // possible subject to the constraints.
 431   this->AddOriginalDirectories(this->UserDirectories);
 432
 433   // Add directories containing constraints.
 434   for(unsigned int i=0; i < this->ConstraintEntries.size(); ++i)
 435     {
 436     this->ConstraintEntries[i]->AddDirectory();
 437     }
 438
 439   // Add language runtime directories last.
 440   this->AddOriginalDirectories(this->LanguageDirectories);
 441 }
 442
 443 //----------------------------------------------------------------------------
 444 int cmOrderDirectories::AddOriginalDirectory(std::string const& dir)
 445 {
 446   // Add the runtime directory with a unique index.
 447   std::map<cmStdString, int>::iterator i =
 448     this->DirectoryIndex.find(dir);
 449   if(i == this->DirectoryIndex.end())
 450     {
 451     std::map<cmStdString, int>::value_type
 452       entry(dir, static_cast<int>(this->OriginalDirectories.size()));
 453     i = this->DirectoryIndex.insert(entry).first;
 454     this->OriginalDirectories.push_back(dir);
 455     }
 456
 457   return i->second;
 458 }
 459
 460 //----------------------------------------------------------------------------
 461 void
 462 cmOrderDirectories
 463 ::AddOriginalDirectories(std::vector<std::string> const& dirs)
 464 {
 465   for(std::vector<std::string>::const_iterator di = dirs.begin();
 466       di != dirs.end(); ++di)
 467     {
 468     // We never explicitly specify implicit link directories.
 469     if(this->ImplicitDirectories.find(*di) !=
 470        this->ImplicitDirectories.end())
 471       {
 472       continue;
 473       }
 474
 475     // Skip the empty string.
 476     if(di->empty())
 477       {
 478       continue;
 479       }
 480
 481     // Add this directory.
 482     this->AddOriginalDirectory(*di);
 483     }
 484 }
 485
 486 //----------------------------------------------------------------------------
 487 struct cmOrderDirectoriesCompare
 488 {
 489   typedef std::pair<int, int> ConflictPair;
 490
 491   // The conflict pair is unique based on just the directory
 492   // (first).  The second element is only used for displaying
 493   // information about why the entry is present.
 494   bool operator()(ConflictPair const& l,
 495                   ConflictPair const& r)
 496     {
 497     return l.first == r.first;
 498     }
 499 };
 500
 501 //----------------------------------------------------------------------------
 502 void cmOrderDirectories::FindConflicts()
 503 {
 504   // Allocate the conflict graph.
 505   this->ConflictGraph.resize(this->OriginalDirectories.size());
 506   this->DirectoryVisited.resize(this->OriginalDirectories.size(), 0);
 507
 508   // Find directories conflicting with each entry.
 509   for(unsigned int i=0; i < this->ConstraintEntries.size(); ++i)
 510     {
 511     this->ConstraintEntries[i]->FindConflicts(i);
 512     }
 513
 514   // Clean up the conflict graph representation.
 515   for(std::vector<ConflictList>::iterator
 516         i = this->ConflictGraph.begin();
 517       i != this->ConflictGraph.end(); ++i)
 518     {
 519     // Sort the outgoing edges for each graph node so that the
 520     // original order will be preserved as much as possible.
 521     std::sort(i->begin(), i->end());
 522
 523     // Make the edge list unique so cycle detection will be reliable.
 524     ConflictList::iterator last =
 525       std::unique(i->begin(), i->end(), cmOrderDirectoriesCompare());
 526     i->erase(last, i->end());
 527     }
 528
 529   // Check items in implicit link directories.
 530   this->FindImplicitConflicts();
 531 }
 532
 533 //----------------------------------------------------------------------------
 534 void cmOrderDirectories::FindImplicitConflicts()
 535 {
 536   // Check for items in implicit link directories that have conflicts
 537   // in the explicit directories.
 538   cmOStringStream conflicts;
 539   for(unsigned int i=0; i < this->ImplicitDirEntries.size(); ++i)
 540     {
 541     this->ImplicitDirEntries[i]->FindImplicitConflicts(conflicts);
 542     }
 543
 544   // Skip warning if there were no conflicts.
 545   std::string text = conflicts.str();
 546   if(text.empty())
 547     {
 548     return;
 549     }
 550
 551   // Warn about the conflicts.
 552   cmOStringStream w;
 553   w << "Cannot generate a safe " << this->Purpose
 554     << " for target " << this->Target->GetName()
 555     << " because files in some directories may conflict with "
 556     << " libraries in implicit directories:\n"
 557     << text
 558     << "Some of these libraries may not be found correctly.";
 559   this->GlobalGenerator->GetCMakeInstance()
 560     ->IssueMessage(cmake::WARNING, w.str(), this->Target->GetBacktrace());
 561 }
 562
 563 //----------------------------------------------------------------------------
 564 void cmOrderDirectories::OrderDirectories()
 565 {
 566   // Allow a cycle to be diagnosed once.
 567   this->CycleDiagnosed = false;
 568   this->WalkId = 0;
 569
 570   // Iterate through the directories in the original order.
 571   for(unsigned int i=0; i < this->OriginalDirectories.size(); ++i)
 572     {
 573     // Start a new DFS from this node.
 574     ++this->WalkId;
 575     this->VisitDirectory(i);
 576     }
 577 }
 578
 579 //----------------------------------------------------------------------------
 580 void cmOrderDirectories::VisitDirectory(unsigned int i)
 581 {
 582   // Skip nodes already visited.
 583   if(this->DirectoryVisited[i])
 584     {
 585     if(this->DirectoryVisited[i] == this->WalkId)
 586       {
 587       // We have reached a node previously visited on this DFS.
 588       // There is a cycle.
 589       this->DiagnoseCycle();
 590       }
 591     return;
 592     }
 593
 594   // We are now visiting this node so mark it.
 595   this->DirectoryVisited[i] = this->WalkId;
 596
 597   // Visit the neighbors of the node first.
 598   ConflictList const& clist = this->ConflictGraph[i];
 599   for(ConflictList::const_iterator j = clist.begin();
 600       j != clist.end(); ++j)
 601     {
 602     this->VisitDirectory(j->first);
 603     }
 604
 605   // Now that all directories required to come before this one have
 606   // been emmitted, emit this directory.
 607   this->OrderedDirectories.push_back(this->OriginalDirectories[i]);
 608 }
 609
 610 //----------------------------------------------------------------------------
 611 void cmOrderDirectories::DiagnoseCycle()
 612 {
 613   // Report the cycle at most once.
 614   if(this->CycleDiagnosed)
 615     {
 616     return;
 617     }
 618   this->CycleDiagnosed = true;
 619
 620   // Construct the message.
 621   cmOStringStream e;
 622   e << "Cannot generate a safe " << this->Purpose
 623     << " for target " << this->Target->GetName()
 624     << " because there is a cycle in the constraint graph:\n";
 625
 626   // Display the conflict graph.
 627   for(unsigned int i=0; i < this->ConflictGraph.size(); ++i)
 628     {
 629     ConflictList const& clist = this->ConflictGraph[i];
 630     e << "  dir " << i << " is [" << this->OriginalDirectories[i] << "]\n";
 631     for(ConflictList::const_iterator j = clist.begin();
 632         j != clist.end(); ++j)
 633       {
 634       e << "    dir " << j->first << " must precede it due to ";
 635       this->ConstraintEntries[j->second]->Report(e);
 636       e << "\n";
 637       }
 638     }
 639   e << "Some of these libraries may not be found correctly.";
 640   this->GlobalGenerator->GetCMakeInstance()
 641     ->IssueMessage(cmake::WARNING, e.str(), this->Target->GetBacktrace());
 642 }