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