Source/cmOrderDirectories.cxx

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