summaryrefslogtreecommitdiff
path: root/Source/cmOrderDirectories.cxx
diff options
context:
space:
mode:
authorAnas Nashif <anas.nashif@intel.com>2012-10-30 15:39:57 -0700
committerAnas Nashif <anas.nashif@intel.com>2012-10-30 15:39:57 -0700
commit035c7fabc3b82cbc9a346c11abe2e9462b4c0379 (patch)
tree7e40f5a790eae329a8c5d3e59f046451767956ff /Source/cmOrderDirectories.cxx
downloadcmake-035c7fabc3b82cbc9a346c11abe2e9462b4c0379.tar.gz
cmake-035c7fabc3b82cbc9a346c11abe2e9462b4c0379.tar.bz2
cmake-035c7fabc3b82cbc9a346c11abe2e9462b4c0379.zip
Imported Upstream version 2.8.9upstream/2.8.9
Diffstat (limited to 'Source/cmOrderDirectories.cxx')
-rw-r--r--Source/cmOrderDirectories.cxx611
1 files changed, 611 insertions, 0 deletions
diff --git a/Source/cmOrderDirectories.cxx b/Source/cmOrderDirectories.cxx
new file mode 100644
index 000000000..6e41768b0
--- /dev/null
+++ b/Source/cmOrderDirectories.cxx
@@ -0,0 +1,611 @@
+/*============================================================================
+ 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;
+ 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 && 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 && 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.c_str(), file.c_str());
+ }
+
+ // Check if the file will be built by cmake.
+ std::set<cmStdString> const& files =
+ (this->GlobalGenerator->GetDirectoryContent(dir, false));
+ std::set<cmStdString>::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<cmStdString> 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<cmStdString>::const_iterator first = files.lower_bound(base);
+ ++base[base.size()-1];
+ std::set<cmStdString>::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))
+ {
+ cmStdString lib = this->OD->RemoveLibraryExtension.match(1);
+ cmStdString 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.c_str()))
+ {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+}
+
+//----------------------------------------------------------------------------
+cmOrderDirectories::cmOrderDirectories(cmGlobalGenerator* gg,
+ cmTarget* 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(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<cmStdString> 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<cmStdString, int>::iterator i =
+ this->DirectoryIndex.find(dir);
+ if(i == this->DirectoryIndex.end())
+ {
+ std::map<cmStdString, 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());
+}