diff options
Diffstat (limited to 'Source/cmOrderDirectories.cxx')
| -rw-r--r-- | Source/cmOrderDirectories.cxx | 648 |
1 files changed, 648 insertions, 0 deletions
diff --git a/Source/cmOrderDirectories.cxx b/Source/cmOrderDirectories.cxx new file mode 100644 index 0000000..3cdd2f6 --- /dev/null +++ b/Source/cmOrderDirectories.cxx @@ -0,0 +1,648 @@ +/*============================================================================ + CMake - Cross Platform Makefile Generator + Copyright 2000-2009 Kitware, Inc., Insight Software Consortium + + Distributed under the OSI-approved BSD License (the "License"); + see accompanying file Copyright.txt for details. + + This software is distributed WITHOUT ANY WARRANTY; without even the + implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the License for more information. +============================================================================*/ +#include "cmOrderDirectories.h" + +#include "cmGlobalGenerator.h" +#include "cmSystemTools.h" +#include "cmake.h" + +#include <assert.h> + +#include <algorithm> + +/* +Directory ordering computation. + - Useful to compute a safe runtime library path order + - Need runtime path for supporting INSTALL_RPATH_USE_LINK_PATH + - Need runtime path at link time to pickup transitive link dependencies + for shared libraries. +*/ + +//---------------------------------------------------------------------------- +class cmOrderDirectoriesConstraint +{ +public: + cmOrderDirectoriesConstraint(cmOrderDirectories* od, + std::string const& file): + OD(od), GlobalGenerator(od->GlobalGenerator) + { + this->FullPath = file; + + if(file.rfind(".framework") != std::string::npos) + { + static cmsys::RegularExpression + splitFramework("^(.*)/(.*).framework/(.*)$"); + if(splitFramework.find(file) && + (std::string::npos != + splitFramework.match(3).find(splitFramework.match(2)))) + { + this->Directory = splitFramework.match(1); + this->FileName = + std::string(file.begin() + this->Directory.size() + 1, file.end()); + } + } + + if(this->FileName.empty()) + { + this->Directory = cmSystemTools::GetFilenamePath(file); + this->FileName = cmSystemTools::GetFilenameName(file); + } + } + virtual ~cmOrderDirectoriesConstraint() {} + + void AddDirectory() + { + this->DirectoryIndex = this->OD->AddOriginalDirectory(this->Directory); + } + + virtual void Report(std::ostream& e) = 0; + + void FindConflicts(unsigned int index) + { + for(unsigned int i=0; i < this->OD->OriginalDirectories.size(); ++i) + { + // Check if this directory conflicts with the entry. + std::string const& dir = this->OD->OriginalDirectories[i]; + if(dir != this->Directory && + cmSystemTools::GetRealPath(dir) != + cmSystemTools::GetRealPath(this->Directory) && + this->FindConflict(dir)) + { + // The library will be found in this directory but this is not + // the directory named for it. Add an entry to make sure the + // desired directory comes before this one. + cmOrderDirectories::ConflictPair p(this->DirectoryIndex, index); + this->OD->ConflictGraph[i].push_back(p); + } + } + } + + void FindImplicitConflicts(cmOStringStream& w) + { + bool first = true; + for(unsigned int i=0; i < this->OD->OriginalDirectories.size(); ++i) + { + // Check if this directory conflicts with the entry. + std::string const& dir = this->OD->OriginalDirectories[i]; + if(dir != this->Directory && + cmSystemTools::GetRealPath(dir) != + cmSystemTools::GetRealPath(this->Directory) && + this->FindConflict(dir)) + { + // The library will be found in this directory but it is + // supposed to be found in an implicit search directory. + if(first) + { + first = false; + w << " "; + this->Report(w); + w << " in " << this->Directory << " may be hidden by files in:\n"; + } + w << " " << dir << "\n"; + } + } + } +protected: + virtual bool FindConflict(std::string const& dir) = 0; + + bool FileMayConflict(std::string const& dir, std::string const& name); + + cmOrderDirectories* OD; + cmGlobalGenerator* GlobalGenerator; + + // The location in which the item is supposed to be found. + std::string FullPath; + std::string Directory; + std::string FileName; + + // The index assigned to the directory. + int DirectoryIndex; +}; + +//---------------------------------------------------------------------------- +bool cmOrderDirectoriesConstraint::FileMayConflict(std::string const& dir, + std::string const& name) +{ + // Check if the file exists on disk. + std::string file = dir; + file += "/"; + file += name; + if(cmSystemTools::FileExists(file.c_str(), true)) + { + // The file conflicts only if it is not the same as the original + // file due to a symlink or hardlink. + return !cmSystemTools::SameFile(this->FullPath, file); + } + + // Check if the file will be built by cmake. + std::set<std::string> const& files = + (this->GlobalGenerator->GetDirectoryContent(dir, false)); + std::set<std::string>::const_iterator fi = files.find(name); + return fi != files.end(); +} + +//---------------------------------------------------------------------------- +class cmOrderDirectoriesConstraintSOName: public cmOrderDirectoriesConstraint +{ +public: + cmOrderDirectoriesConstraintSOName(cmOrderDirectories* od, + std::string const& file, + const char* soname): + cmOrderDirectoriesConstraint(od, file), SOName(soname? soname : "") + { + if(this->SOName.empty()) + { + // Try to guess the soname. + std::string soguess; + if(cmSystemTools::GuessLibrarySOName(file, soguess)) + { + this->SOName = soguess; + } + } + } + + virtual void Report(std::ostream& e) + { + e << "runtime library ["; + if(this->SOName.empty()) + { + e << this->FileName; + } + else + { + e << this->SOName; + } + e << "]"; + } + + virtual bool FindConflict(std::string const& dir); +private: + // The soname of the shared library if it is known. + std::string SOName; +}; + +//---------------------------------------------------------------------------- +bool cmOrderDirectoriesConstraintSOName::FindConflict(std::string const& dir) +{ + // Determine which type of check to do. + if(!this->SOName.empty()) + { + // We have the library soname. Check if it will be found. + if(this->FileMayConflict(dir, this->SOName)) + { + return true; + } + } + else + { + // We do not have the soname. Look for files in the directory + // that may conflict. + std::set<std::string> const& files = + (this->GlobalGenerator + ->GetDirectoryContent(dir, true)); + + // Get the set of files that might conflict. Since we do not + // know the soname just look at all files that start with the + // file name. Usually the soname starts with the library name. + std::string base = this->FileName; + std::set<std::string>::const_iterator first = files.lower_bound(base); + ++base[base.size()-1]; + std::set<std::string>::const_iterator last = files.upper_bound(base); + if(first != last) + { + return true; + } + } + return false; +} + +//---------------------------------------------------------------------------- +class cmOrderDirectoriesConstraintLibrary: public cmOrderDirectoriesConstraint +{ +public: + cmOrderDirectoriesConstraintLibrary(cmOrderDirectories* od, + std::string const& file): + cmOrderDirectoriesConstraint(od, file) + { + } + + virtual void Report(std::ostream& e) + { + e << "link library [" << this->FileName << "]"; + } + + virtual bool FindConflict(std::string const& dir); +}; + +//---------------------------------------------------------------------------- +bool cmOrderDirectoriesConstraintLibrary::FindConflict(std::string const& dir) +{ + // We have the library file name. Check if it will be found. + if(this->FileMayConflict(dir, this->FileName)) + { + return true; + } + + // Now check if the file exists with other extensions the linker + // might consider. + if(!this->OD->LinkExtensions.empty() && + this->OD->RemoveLibraryExtension.find(this->FileName)) + { + std::string lib = this->OD->RemoveLibraryExtension.match(1); + std::string ext = this->OD->RemoveLibraryExtension.match(2); + for(std::vector<std::string>::iterator + i = this->OD->LinkExtensions.begin(); + i != this->OD->LinkExtensions.end(); ++i) + { + if(*i != ext) + { + std::string fname = lib; + fname += *i; + if(this->FileMayConflict(dir, fname)) + { + return true; + } + } + } + } + return false; +} + +//---------------------------------------------------------------------------- +cmOrderDirectories::cmOrderDirectories(cmGlobalGenerator* gg, + cmTarget const* target, + const char* purpose) +{ + this->GlobalGenerator = gg; + this->Target = target; + this->Purpose = purpose; + this->Computed = false; +} + +//---------------------------------------------------------------------------- +cmOrderDirectories::~cmOrderDirectories() +{ + for(std::vector<cmOrderDirectoriesConstraint*>::iterator + i = this->ConstraintEntries.begin(); + i != this->ConstraintEntries.end(); ++i) + { + delete *i; + } + for(std::vector<cmOrderDirectoriesConstraint*>::iterator + i = this->ImplicitDirEntries.begin(); + i != this->ImplicitDirEntries.end(); ++i) + { + delete *i; + } +} + +//---------------------------------------------------------------------------- +std::vector<std::string> const& cmOrderDirectories::GetOrderedDirectories() +{ + if(!this->Computed) + { + this->Computed = true; + this->CollectOriginalDirectories(); + this->FindConflicts(); + this->OrderDirectories(); + } + return this->OrderedDirectories; +} + +//---------------------------------------------------------------------------- +void cmOrderDirectories::AddRuntimeLibrary(std::string const& fullPath, + const char* soname) +{ + // Add the runtime library at most once. + if(this->EmmittedConstraintSOName.insert(fullPath).second) + { + // Implicit link directories need special handling. + if(!this->ImplicitDirectories.empty()) + { + std::string dir = cmSystemTools::GetFilenamePath(fullPath); + + if(fullPath.rfind(".framework") != std::string::npos) + { + static cmsys::RegularExpression + splitFramework("^(.*)/(.*).framework/(.*)$"); + if(splitFramework.find(fullPath) && + (std::string::npos != + splitFramework.match(3).find(splitFramework.match(2)))) + { + dir = splitFramework.match(1); + } + } + + if(this->ImplicitDirectories.find(dir) != + this->ImplicitDirectories.end()) + { + this->ImplicitDirEntries.push_back( + new cmOrderDirectoriesConstraintSOName(this, fullPath, soname)); + return; + } + } + + // Construct the runtime information entry for this library. + this->ConstraintEntries.push_back( + new cmOrderDirectoriesConstraintSOName(this, fullPath, soname)); + } + else + { + // This can happen if the same library is linked multiple times. + // In that case the runtime information check need be done only + // once anyway. For shared libs we could add a check in AddItem + // to not repeat them. + } +} + +//---------------------------------------------------------------------------- +void cmOrderDirectories::AddLinkLibrary(std::string const& fullPath) +{ + // Link extension info is required for library constraints. + assert(!this->LinkExtensions.empty()); + + // Add the link library at most once. + if(this->EmmittedConstraintLibrary.insert(fullPath).second) + { + // Implicit link directories need special handling. + if(!this->ImplicitDirectories.empty()) + { + std::string dir = cmSystemTools::GetFilenamePath(fullPath); + if(this->ImplicitDirectories.find(dir) != + this->ImplicitDirectories.end()) + { + this->ImplicitDirEntries.push_back( + new cmOrderDirectoriesConstraintLibrary(this, fullPath)); + return; + } + } + + // Construct the link library entry. + this->ConstraintEntries.push_back( + new cmOrderDirectoriesConstraintLibrary(this, fullPath)); + } +} + +//---------------------------------------------------------------------------- +void +cmOrderDirectories +::AddUserDirectories(std::vector<std::string> const& extra) +{ + this->UserDirectories.insert(this->UserDirectories.end(), + extra.begin(), extra.end()); +} + +//---------------------------------------------------------------------------- +void +cmOrderDirectories +::AddLanguageDirectories(std::vector<std::string> const& dirs) +{ + this->LanguageDirectories.insert(this->LanguageDirectories.end(), + dirs.begin(), dirs.end()); +} + +//---------------------------------------------------------------------------- +void +cmOrderDirectories +::SetImplicitDirectories(std::set<std::string> const& implicitDirs) +{ + this->ImplicitDirectories = implicitDirs; +} + +//---------------------------------------------------------------------------- +void +cmOrderDirectories +::SetLinkExtensionInfo(std::vector<std::string> const& linkExtensions, + std::string const& removeExtRegex) +{ + this->LinkExtensions = linkExtensions; + this->RemoveLibraryExtension.compile(removeExtRegex.c_str()); +} + +//---------------------------------------------------------------------------- +void cmOrderDirectories::CollectOriginalDirectories() +{ + // Add user directories specified for inclusion. These should be + // indexed first so their original order is preserved as much as + // possible subject to the constraints. + this->AddOriginalDirectories(this->UserDirectories); + + // Add directories containing constraints. + for(unsigned int i=0; i < this->ConstraintEntries.size(); ++i) + { + this->ConstraintEntries[i]->AddDirectory(); + } + + // Add language runtime directories last. + this->AddOriginalDirectories(this->LanguageDirectories); +} + +//---------------------------------------------------------------------------- +int cmOrderDirectories::AddOriginalDirectory(std::string const& dir) +{ + // Add the runtime directory with a unique index. + std::map<std::string, int>::iterator i = + this->DirectoryIndex.find(dir); + if(i == this->DirectoryIndex.end()) + { + std::map<std::string, int>::value_type + entry(dir, static_cast<int>(this->OriginalDirectories.size())); + i = this->DirectoryIndex.insert(entry).first; + this->OriginalDirectories.push_back(dir); + } + + return i->second; +} + +//---------------------------------------------------------------------------- +void +cmOrderDirectories +::AddOriginalDirectories(std::vector<std::string> const& dirs) +{ + for(std::vector<std::string>::const_iterator di = dirs.begin(); + di != dirs.end(); ++di) + { + // We never explicitly specify implicit link directories. + if(this->ImplicitDirectories.find(*di) != + this->ImplicitDirectories.end()) + { + continue; + } + + // Skip the empty string. + if(di->empty()) + { + continue; + } + + // Add this directory. + this->AddOriginalDirectory(*di); + } +} + +//---------------------------------------------------------------------------- +struct cmOrderDirectoriesCompare +{ + typedef std::pair<int, int> ConflictPair; + + // The conflict pair is unique based on just the directory + // (first). The second element is only used for displaying + // information about why the entry is present. + bool operator()(ConflictPair const& l, + ConflictPair const& r) + { + return l.first == r.first; + } +}; + +//---------------------------------------------------------------------------- +void cmOrderDirectories::FindConflicts() +{ + // Allocate the conflict graph. + this->ConflictGraph.resize(this->OriginalDirectories.size()); + this->DirectoryVisited.resize(this->OriginalDirectories.size(), 0); + + // Find directories conflicting with each entry. + for(unsigned int i=0; i < this->ConstraintEntries.size(); ++i) + { + this->ConstraintEntries[i]->FindConflicts(i); + } + + // Clean up the conflict graph representation. + for(std::vector<ConflictList>::iterator + i = this->ConflictGraph.begin(); + i != this->ConflictGraph.end(); ++i) + { + // Sort the outgoing edges for each graph node so that the + // original order will be preserved as much as possible. + std::sort(i->begin(), i->end()); + + // Make the edge list unique so cycle detection will be reliable. + ConflictList::iterator last = + std::unique(i->begin(), i->end(), cmOrderDirectoriesCompare()); + i->erase(last, i->end()); + } + + // Check items in implicit link directories. + this->FindImplicitConflicts(); +} + +//---------------------------------------------------------------------------- +void cmOrderDirectories::FindImplicitConflicts() +{ + // Check for items in implicit link directories that have conflicts + // in the explicit directories. + cmOStringStream conflicts; + for(unsigned int i=0; i < this->ImplicitDirEntries.size(); ++i) + { + this->ImplicitDirEntries[i]->FindImplicitConflicts(conflicts); + } + + // Skip warning if there were no conflicts. + std::string text = conflicts.str(); + if(text.empty()) + { + return; + } + + // Warn about the conflicts. + cmOStringStream w; + w << "Cannot generate a safe " << this->Purpose + << " for target " << this->Target->GetName() + << " because files in some directories may conflict with " + << " libraries in implicit directories:\n" + << text + << "Some of these libraries may not be found correctly."; + this->GlobalGenerator->GetCMakeInstance() + ->IssueMessage(cmake::WARNING, w.str(), this->Target->GetBacktrace()); +} + +//---------------------------------------------------------------------------- +void cmOrderDirectories::OrderDirectories() +{ + // Allow a cycle to be diagnosed once. + this->CycleDiagnosed = false; + this->WalkId = 0; + + // Iterate through the directories in the original order. + for(unsigned int i=0; i < this->OriginalDirectories.size(); ++i) + { + // Start a new DFS from this node. + ++this->WalkId; + this->VisitDirectory(i); + } +} + +//---------------------------------------------------------------------------- +void cmOrderDirectories::VisitDirectory(unsigned int i) +{ + // Skip nodes already visited. + if(this->DirectoryVisited[i]) + { + if(this->DirectoryVisited[i] == this->WalkId) + { + // We have reached a node previously visited on this DFS. + // There is a cycle. + this->DiagnoseCycle(); + } + return; + } + + // We are now visiting this node so mark it. + this->DirectoryVisited[i] = this->WalkId; + + // Visit the neighbors of the node first. + ConflictList const& clist = this->ConflictGraph[i]; + for(ConflictList::const_iterator j = clist.begin(); + j != clist.end(); ++j) + { + this->VisitDirectory(j->first); + } + + // Now that all directories required to come before this one have + // been emmitted, emit this directory. + this->OrderedDirectories.push_back(this->OriginalDirectories[i]); +} + +//---------------------------------------------------------------------------- +void cmOrderDirectories::DiagnoseCycle() +{ + // Report the cycle at most once. + if(this->CycleDiagnosed) + { + return; + } + this->CycleDiagnosed = true; + + // Construct the message. + cmOStringStream e; + e << "Cannot generate a safe " << this->Purpose + << " for target " << this->Target->GetName() + << " because there is a cycle in the constraint graph:\n"; + + // Display the conflict graph. + for(unsigned int i=0; i < this->ConflictGraph.size(); ++i) + { + ConflictList const& clist = this->ConflictGraph[i]; + e << " dir " << i << " is [" << this->OriginalDirectories[i] << "]\n"; + for(ConflictList::const_iterator j = clist.begin(); + j != clist.end(); ++j) + { + e << " dir " << j->first << " must precede it due to "; + this->ConstraintEntries[j->second]->Report(e); + e << "\n"; + } + } + e << "Some of these libraries may not be found correctly."; + this->GlobalGenerator->GetCMakeInstance() + ->IssueMessage(cmake::WARNING, e.str(), this->Target->GetBacktrace()); +} |