/src/CMake/Source/cmOrderDirectories.cxx

Source
/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file LICENSE.rst or https://cmake.org/licensing for details.  */
#include "cmOrderDirectories.h"

#include <algorithm>
#include <cassert>
#include <functional>
#include <sstream>
#include <vector>

#include <cm/memory>
#include <cmext/algorithm>

#include "cmGeneratorTarget.h"
#include "cmGlobalGenerator.h"
#include "cmMessageType.h"
#include "cmStringAlgorithms.h"
#include "cmSystemTools.h"
#include "cmake.h"

/*
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() = default;

  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 (!this->OD->IsSameDirectory(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(std::ostringstream& w)
  {
    bool first = true;
    for (std::string const& dir : this->OD->OriginalDirectories) {
      // Check if this directory conflicts with the entry.
      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 = cmStrCat(dir, '/', name);
  if (cmSystemTools::FileExists(file, 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));
  auto fi = files.find(name);
  return fi != files.end();
}

class cmOrderDirectoriesConstraintSOName : public cmOrderDirectoriesConstraint
{
public:
  cmOrderDirectoriesConstraintSOName(cmOrderDirectories* od,
                                     std::string const& file,
                                     char const* 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;
      }
    }
  }

  void Report(std::ostream& e) override
  {
    e << "runtime library [";
    if (this->SOName.empty()) {
      e << this->FileName;
    } else {
      e << this->SOName;
    }
    e << "]";
  }

  bool FindConflict(std::string const& dir) override;

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;
    auto first = files.lower_bound(base);
    ++base.back();
    auto 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)
  {
  }

  void Report(std::ostream& e) override
  {
    e << "link library [" << this->FileName << "]";
  }

  bool FindConflict(std::string const& dir) override;
};

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::string const& LinkExtension : this->OD->LinkExtensions) {
      if (LinkExtension != ext) {
        std::string fname = cmStrCat(lib, LinkExtension);
        if (this->FileMayConflict(dir, fname)) {
          return true;
        }
      }
    }
  }
  return false;
}

cmOrderDirectories::cmOrderDirectories(cmGlobalGenerator* gg,
                                       cmGeneratorTarget const* target,
                                       char const* purpose)
{
  this->GlobalGenerator = gg;
  this->Target = target;
  this->Purpose = purpose;
  this->Computed = false;
}

cmOrderDirectories::~cmOrderDirectories() = default;

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,
                                           char const* soname)
{
  // Add the runtime library at most once.
  if (this->EmittedConstraintSOName.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->IsImplicitDirectory(dir)) {
        this->ImplicitDirEntries.push_back(
          cm::make_unique<cmOrderDirectoriesConstraintSOName>(this, fullPath,
                                                              soname));
        return;
      }
    }

    // Construct the runtime information entry for this library.
    this->ConstraintEntries.push_back(
      cm::make_unique<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->EmittedConstraintLibrary.insert(fullPath).second) {
    // Implicit link directories need special handling.
    if (!this->ImplicitDirectories.empty()) {
      std::string dir = cmSystemTools::GetFilenamePath(fullPath);
      if (this->IsImplicitDirectory(dir)) {
        this->ImplicitDirEntries.push_back(
          cm::make_unique<cmOrderDirectoriesConstraintLibrary>(this,
                                                               fullPath));
        return;
      }
    }

    // Construct the link library entry.
    this->ConstraintEntries.push_back(
      cm::make_unique<cmOrderDirectoriesConstraintLibrary>(this, fullPath));
  }
}

void cmOrderDirectories::AddUserDirectories(
  std::vector<std::string> const& extra)
{
  cm::append(this->UserDirectories, extra);
}

void cmOrderDirectories::AddLanguageDirectories(
  std::vector<std::string> const& dirs)
{
  cm::append(this->LanguageDirectories, dirs);
}

void cmOrderDirectories::SetImplicitDirectories(
  std::set<std::string> const& implicitDirs)
{
  this->ImplicitDirectories.clear();
  for (std::string const& implicitDir : implicitDirs) {
    this->ImplicitDirectories.insert(this->GetRealPath(implicitDir));
  }
}

bool cmOrderDirectories::IsImplicitDirectory(std::string const& dir)
{
  std::string const& real = this->GetRealPath(dir);
  return this->ImplicitDirectories.find(real) !=
    this->ImplicitDirectories.end();
}

void cmOrderDirectories::SetLinkExtensionInfo(
  std::vector<std::string> const& linkExtensions,
  std::string const& removeExtRegex)
{
  this->LinkExtensions = linkExtensions;
  this->RemoveLibraryExtension.compile(removeExtRegex);
}

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 (auto const& entry : this->ConstraintEntries) {
    entry->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.
  auto 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::string const& dir : dirs) {
    // We never explicitly specify implicit link directories.
    if (this->IsImplicitDirectory(dir)) {
      continue;
    }

    // Skip the empty string.
    if (dir.empty()) {
      continue;
    }

    // Add this directory.
    this->AddOriginalDirectory(dir);
  }
}

struct cmOrderDirectoriesCompare
{
  using ConflictPair = std::pair<int, int>;

  // 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 l, ConflictPair 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 (ConflictList& cl : this->ConflictGraph) {
    // Sort the outgoing edges for each graph node so that the
    // original order will be preserved as much as possible.
    std::sort(cl.begin(), cl.end());

    // Make the edge list unique so cycle detection will be reliable.
    auto last = std::unique(cl.begin(), cl.end(), cmOrderDirectoriesCompare());
    cl.erase(last, cl.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.
  std::ostringstream conflicts;
  for (auto const& entry : this->ImplicitDirEntries) {
    entry->FindImplicitConflicts(conflicts);
  }

  // Skip warning if there were no conflicts.
  std::string const text = conflicts.str();
  if (text.empty()) {
    return;
  }

  // Warn about the conflicts.
  this->GlobalGenerator->GetCMakeInstance()->IssueMessage(
    MessageType::WARNING,
    cmStrCat("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->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 (ConflictPair const& j : clist) {
    this->VisitDirectory(j.first);
  }

  // Now that all directories required to come before this one have
  // been emitted, 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.
  std::ostringstream 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 (ConflictPair const& j : clist) {
      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(
    MessageType::WARNING, e.str(), this->Target->GetBacktrace());
}

bool cmOrderDirectories::IsSameDirectory(std::string const& l,
                                         std::string const& r)
{
  return this->GetRealPath(l) == this->GetRealPath(r);
}

std::string const& cmOrderDirectories::GetRealPath(std::string const& dir)
{
  auto i = this->RealPaths.lower_bound(dir);
  if (i == this->RealPaths.end() ||
      this->RealPaths.key_comp()(dir, i->first)) {
    using value_type = std::map<std::string, std::string>::value_type;
    i = this->RealPaths.insert(
      i, value_type(dir, cmSystemTools::GetRealPath(dir)));
  }
  return i->second;
}

Coverage Report

Created: 2026-03-12 06:35

Line	Count	Source
1		/* Distributed under the OSI-approved BSD 3-Clause License. See accompanying
2		file LICENSE.rst 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	0	: OD(od)
34	0	, GlobalGenerator(od->GlobalGenerator)
35	0	{
36	0	this->FullPath = file;
37
38	0	if (file.rfind(".framework") != std::string::npos) {
39	0	static cmsys::RegularExpression splitFramework(
40	0	"^(.)/(.).framework/(.*)$");
41	0	if (splitFramework.find(file) &&
42	0	(std::string::npos !=
43	0	splitFramework.match(3).find(splitFramework.match(2)))) {
44	0	this->Directory = splitFramework.match(1);
45	0	this->FileName =
46	0	std::string(file.begin() + this->Directory.size() + 1, file.end());
47	0	}
48	0	}
49
50	0	if (this->FileName.empty()) {
51	0	this->Directory = cmSystemTools::GetFilenamePath(file);
52	0	this->FileName = cmSystemTools::GetFilenameName(file);
53	0	}
54	0	}
55	0	virtual ~cmOrderDirectoriesConstraint() = default;
56
57		void AddDirectory()
58	0	{
59	0	this->DirectoryIndex = this->OD->AddOriginalDirectory(this->Directory);
60	0	}
61
62		virtual void Report(std::ostream& e) = 0;
63
64		void FindConflicts(unsigned int index)
65	0	{
66	0	for (unsigned int i = 0; i < this->OD->OriginalDirectories.size(); ++i) {
67		// Check if this directory conflicts with the entry.
68	0	std::string const& dir = this->OD->OriginalDirectories[i];
69	0	if (!this->OD->IsSameDirectory(dir, this->Directory) &&
70	0	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	0	cmOrderDirectories::ConflictPair p(this->DirectoryIndex, index);
75	0	this->OD->ConflictGraph[i].push_back(p);
76	0	}
77	0	}
78	0	}
79
80		void FindImplicitConflicts(std::ostringstream& w)
81	0	{
82	0	bool first = true;
83	0	for (std::string const& dir : this->OD->OriginalDirectories) {
84		// Check if this directory conflicts with the entry.
85	0	if (dir != this->Directory &&
86	0	cmSystemTools::GetRealPath(dir) !=
87	0	cmSystemTools::GetRealPath(this->Directory) &&
88	0	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	0	if (first) {
92	0	first = false;
93	0	w << " ";
94	0	this->Report(w);
95	0	w << " in " << this->Directory << " may be hidden by files in:\n";
96	0	}
97	0	w << " " << dir << "\n";
98	0	}
99	0	}
100	0	}
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	0	{
122		// Check if the file exists on disk.
123	0	std::string file = cmStrCat(dir, '/', name);
124	0	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	0	return !cmSystemTools::SameFile(this->FullPath, file);
128	0	}
129
130		// Check if the file will be built by cmake.
131	0	std::set<std::string> const& files =
132	0	(this->GlobalGenerator->GetDirectoryContent(dir, false));
133	0	auto fi = files.find(name);
134	0	return fi != files.end();
135	0	}
136
137		class cmOrderDirectoriesConstraintSOName : public cmOrderDirectoriesConstraint
138		{
139		public:
140		cmOrderDirectoriesConstraintSOName(cmOrderDirectories* od,
141		std::string const& file,
142		char const* soname)
143	0	: cmOrderDirectoriesConstraint(od, file)
144	0	, SOName(soname ? soname : "")
145	0	{
146	0	if (this->SOName.empty()) {
147		// Try to guess the soname.
148	0	std::string soguess;
149	0	if (cmSystemTools::GuessLibrarySOName(file, soguess)) {
150	0	this->SOName = soguess;
151	0	}
152	0	}
153	0	}
154
155		void Report(std::ostream& e) override
156	0	{
157	0	e << "runtime library [";
158	0	if (this->SOName.empty()) {
159	0	e << this->FileName;
160	0	} else {
161	0	e << this->SOName;
162	0	}
163	0	e << "]";
164	0	}
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	0	{
175		// Determine which type of check to do.
176	0	if (!this->SOName.empty()) {
177		// We have the library soname. Check if it will be found.
178	0	if (this->FileMayConflict(dir, this->SOName)) {
179	0	return true;
180	0	}
181	0	} else {
182		// We do not have the soname. Look for files in the directory
183		// that may conflict.
184	0	std::set<std::string> const& files =
185	0	(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	0	std::string base = this->FileName;
191	0	auto first = files.lower_bound(base);
192	0	++base.back();
193	0	auto last = files.upper_bound(base);
194	0	if (first != last) {
195	0	return true;
196	0	}
197	0	}
198	0	return false;
199	0	}
200
201		class cmOrderDirectoriesConstraintLibrary : public cmOrderDirectoriesConstraint
202		{
203		public:
204		cmOrderDirectoriesConstraintLibrary(cmOrderDirectories* od,
205		std::string const& file)
206	0	: cmOrderDirectoriesConstraint(od, file)
207	0	{
208	0	}
209
210		void Report(std::ostream& e) override
211	0	{
212	0	e << "link library [" << this->FileName << "]";
213	0	}
214
215		bool FindConflict(std::string const& dir) override;
216		};
217
218		bool cmOrderDirectoriesConstraintLibrary::FindConflict(std::string const& dir)
219	0	{
220		// We have the library file name. Check if it will be found.
221	0	if (this->FileMayConflict(dir, this->FileName)) {
222	0	return true;
223	0	}
224
225		// Now check if the file exists with other extensions the linker
226		// might consider.
227	0	if (!this->OD->LinkExtensions.empty() &&
228	0	this->OD->RemoveLibraryExtension.find(this->FileName)) {
229	0	std::string lib = this->OD->RemoveLibraryExtension.match(1);
230	0	std::string ext = this->OD->RemoveLibraryExtension.match(2);
231	0	for (std::string const& LinkExtension : this->OD->LinkExtensions) {
232	0	if (LinkExtension != ext) {
233	0	std::string fname = cmStrCat(lib, LinkExtension);
234	0	if (this->FileMayConflict(dir, fname)) {
235	0	return true;
236	0	}
237	0	}
238	0	}
239	0	}
240	0	return false;
241	0	}
242
243		cmOrderDirectories::cmOrderDirectories(cmGlobalGenerator* gg,
244		cmGeneratorTarget const* target,
245		char const* purpose)
246	0	{
247	0	this->GlobalGenerator = gg;
248	0	this->Target = target;
249	0	this->Purpose = purpose;
250	0	this->Computed = false;
251	0	}
252
253	0	cmOrderDirectories::~cmOrderDirectories() = default;
254
255		std::vector<std::string> const& cmOrderDirectories::GetOrderedDirectories()
256	0	{
257	0	if (!this->Computed) {
258	0	this->Computed = true;
259	0	this->CollectOriginalDirectories();
260	0	this->FindConflicts();
261	0	this->OrderDirectories();
262	0	}
263	0	return this->OrderedDirectories;
264	0	}
265
266		void cmOrderDirectories::AddRuntimeLibrary(std::string const& fullPath,
267		char const* soname)
268	0	{
269		// Add the runtime library at most once.
270	0	if (this->EmittedConstraintSOName.insert(fullPath).second) {
271		// Implicit link directories need special handling.
272	0	if (!this->ImplicitDirectories.empty()) {
273	0	std::string dir = cmSystemTools::GetFilenamePath(fullPath);
274
275	0	if (fullPath.rfind(".framework") != std::string::npos) {
276	0	static cmsys::RegularExpression splitFramework(
277	0	"^(.)/(.).framework/(.*)$");
278	0	if (splitFramework.find(fullPath) &&
279	0	(std::string::npos !=
280	0	splitFramework.match(3).find(splitFramework.match(2)))) {
281	0	dir = splitFramework.match(1);
282	0	}
283	0	}
284
285	0	if (this->IsImplicitDirectory(dir)) {
286	0	this->ImplicitDirEntries.push_back(
287	0	cm::make_unique<cmOrderDirectoriesConstraintSOName>(this, fullPath,
288	0	soname));
289	0	return;
290	0	}
291	0	}
292
293		// Construct the runtime information entry for this library.
294	0	this->ConstraintEntries.push_back(
295	0	cm::make_unique<cmOrderDirectoriesConstraintSOName>(this, fullPath,
296	0	soname));
297	0	} 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	0	}
303	0	}
304
305		void cmOrderDirectories::AddLinkLibrary(std::string const& fullPath)
306	0	{
307		// Link extension info is required for library constraints.
308	0	assert(!this->LinkExtensions.empty());
309
310		// Add the link library at most once.
311	0	if (this->EmittedConstraintLibrary.insert(fullPath).second) {
312		// Implicit link directories need special handling.
313	0	if (!this->ImplicitDirectories.empty()) {
314	0	std::string dir = cmSystemTools::GetFilenamePath(fullPath);
315	0	if (this->IsImplicitDirectory(dir)) {
316	0	this->ImplicitDirEntries.push_back(
317	0	cm::make_unique<cmOrderDirectoriesConstraintLibrary>(this,
318	0	fullPath));
319	0	return;
320	0	}
321	0	}
322
323		// Construct the link library entry.
324	0	this->ConstraintEntries.push_back(
325	0	cm::make_unique<cmOrderDirectoriesConstraintLibrary>(this, fullPath));
326	0	}
327	0	}
328
329		void cmOrderDirectories::AddUserDirectories(
330		std::vector<std::string> const& extra)
331	0	{
332	0	cm::append(this->UserDirectories, extra);
333	0	}
334
335		void cmOrderDirectories::AddLanguageDirectories(
336		std::vector<std::string> const& dirs)
337	0	{
338	0	cm::append(this->LanguageDirectories, dirs);
339	0	}
340
341		void cmOrderDirectories::SetImplicitDirectories(
342		std::set<std::string> const& implicitDirs)
343	0	{
344	0	this->ImplicitDirectories.clear();
345	0	for (std::string const& implicitDir : implicitDirs) {
346	0	this->ImplicitDirectories.insert(this->GetRealPath(implicitDir));
347	0	}
348	0	}
349
350		bool cmOrderDirectories::IsImplicitDirectory(std::string const& dir)
351	0	{
352	0	std::string const& real = this->GetRealPath(dir);
353	0	return this->ImplicitDirectories.find(real) !=
354	0	this->ImplicitDirectories.end();
355	0	}
356
357		void cmOrderDirectories::SetLinkExtensionInfo(
358		std::vector<std::string> const& linkExtensions,
359		std::string const& removeExtRegex)
360	0	{
361	0	this->LinkExtensions = linkExtensions;
362	0	this->RemoveLibraryExtension.compile(removeExtRegex);
363	0	}
364
365		void cmOrderDirectories::CollectOriginalDirectories()
366	0	{
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	0	this->AddOriginalDirectories(this->UserDirectories);
371
372		// Add directories containing constraints.
373	0	for (auto const& entry : this->ConstraintEntries) {
374	0	entry->AddDirectory();
375	0	}
376
377		// Add language runtime directories last.
378	0	this->AddOriginalDirectories(this->LanguageDirectories);
379	0	}
380
381		int cmOrderDirectories::AddOriginalDirectory(std::string const& dir)
382	0	{
383		// Add the runtime directory with a unique index.
384	0	auto i = this->DirectoryIndex.find(dir);
385	0	if (i == this->DirectoryIndex.end()) {
386	0	std::map<std::string, int>::value_type entry(
387	0	dir, static_cast<int>(this->OriginalDirectories.size()));
388	0	i = this->DirectoryIndex.insert(entry).first;
389	0	this->OriginalDirectories.push_back(dir);
390	0	}
391
392	0	return i->second;
393	0	}
394
395		void cmOrderDirectories::AddOriginalDirectories(
396		std::vector<std::string> const& dirs)
397	0	{
398	0	for (std::string const& dir : dirs) {
399		// We never explicitly specify implicit link directories.
400	0	if (this->IsImplicitDirectory(dir)) {
401	0	continue;
402	0	}
403
404		// Skip the empty string.
405	0	if (dir.empty()) {
406	0	continue;
407	0	}
408
409		// Add this directory.
410	0	this->AddOriginalDirectory(dir);
411	0	}
412	0	}
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	0	{
423	0	return l.first == r.first;
424	0	}
425		};
426
427		void cmOrderDirectories::FindConflicts()
428	0	{
429		// Allocate the conflict graph.
430	0	this->ConflictGraph.resize(this->OriginalDirectories.size());
431	0	this->DirectoryVisited.resize(this->OriginalDirectories.size(), 0);
432
433		// Find directories conflicting with each entry.
434	0	for (unsigned int i = 0; i < this->ConstraintEntries.size(); ++i) {
435	0	this->ConstraintEntries[i]->FindConflicts(i);
436	0	}
437
438		// Clean up the conflict graph representation.
439	0	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	0	std::sort(cl.begin(), cl.end());
443
444		// Make the edge list unique so cycle detection will be reliable.
445	0	auto last = std::unique(cl.begin(), cl.end(), cmOrderDirectoriesCompare());
446	0	cl.erase(last, cl.end());
447	0	}
448
449		// Check items in implicit link directories.
450	0	this->FindImplicitConflicts();
451	0	}
452
453		void cmOrderDirectories::FindImplicitConflicts()
454	0	{
455		// Check for items in implicit link directories that have conflicts
456		// in the explicit directories.
457	0	std::ostringstream conflicts;
458	0	for (auto const& entry : this->ImplicitDirEntries) {
459	0	entry->FindImplicitConflicts(conflicts);
460	0	}
461
462		// Skip warning if there were no conflicts.
463	0	std::string const text = conflicts.str();
464	0	if (text.empty()) {
465	0	return;
466	0	}
467
468		// Warn about the conflicts.
469	0	this->GlobalGenerator->GetCMakeInstance()->IssueMessage(
470	0	MessageType::WARNING,
471	0	cmStrCat("Cannot generate a safe ", this->Purpose, " for target ",
472	0	this->Target->GetName(),
473	0	" because files in some directories may "
474	0	"conflict with libraries in implicit directories:\n",
475	0	text, "Some of these libraries may not be found correctly."),
476	0	this->Target->GetBacktrace());
477	0	}
478
479		void cmOrderDirectories::OrderDirectories()
480	0	{
481		// Allow a cycle to be diagnosed once.
482	0	this->CycleDiagnosed = false;
483	0	this->WalkId = 0;
484
485		// Iterate through the directories in the original order.
486	0	for (unsigned int i = 0; i < this->OriginalDirectories.size(); ++i) {
487		// Start a new DFS from this node.
488	0	++this->WalkId;
489	0	this->VisitDirectory(i);
490	0	}
491	0	}
492
493		void cmOrderDirectories::VisitDirectory(unsigned int i)
494	0	{
495		// Skip nodes already visited.
496	0	if (this->DirectoryVisited[i]) {
497	0	if (this->DirectoryVisited[i] == this->WalkId) {
498		// We have reached a node previously visited on this DFS.
499		// There is a cycle.
500	0	this->DiagnoseCycle();
501	0	}
502	0	return;
503	0	}
504
505		// We are now visiting this node so mark it.
506	0	this->DirectoryVisited[i] = this->WalkId;
507
508		// Visit the neighbors of the node first.
509	0	ConflictList const& clist = this->ConflictGraph[i];
510	0	for (ConflictPair const& j : clist) {
511	0	this->VisitDirectory(j.first);
512	0	}
513
514		// Now that all directories required to come before this one have
515		// been emitted, emit this directory.
516	0	this->OrderedDirectories.push_back(this->OriginalDirectories[i]);
517	0	}
518
519		void cmOrderDirectories::DiagnoseCycle()
520	0	{
521		// Report the cycle at most once.
522	0	if (this->CycleDiagnosed) {
523	0	return;
524	0	}
525	0	this->CycleDiagnosed = true;
526
527		// Construct the message.
528	0	std::ostringstream e;
529	0	e << "Cannot generate a safe " << this->Purpose << " for target "
530	0	<< this->Target->GetName()
531	0	<< " because there is a cycle in the constraint graph:\n";
532
533		// Display the conflict graph.
534	0	for (unsigned int i = 0; i < this->ConflictGraph.size(); ++i) {
535	0	ConflictList const& clist = this->ConflictGraph[i];
536	0	e << " dir " << i << " is [" << this->OriginalDirectories[i] << "]\n";
537	0	for (ConflictPair const& j : clist) {
538	0	e << " dir " << j.first << " must precede it due to ";
539	0	this->ConstraintEntries[j.second]->Report(e);
540	0	e << "\n";
541	0	}
542	0	}
543	0	e << "Some of these libraries may not be found correctly.";
544	0	this->GlobalGenerator->GetCMakeInstance()->IssueMessage(
545	0	MessageType::WARNING, e.str(), this->Target->GetBacktrace());
546	0	}
547
548		bool cmOrderDirectories::IsSameDirectory(std::string const& l,
549		std::string const& r)
550	0	{
551	0	return this->GetRealPath(l) == this->GetRealPath(r);
552	0	}
553
554		std::string const& cmOrderDirectories::GetRealPath(std::string const& dir)
555	0	{
556	0	auto i = this->RealPaths.lower_bound(dir);
557	0	if (i == this->RealPaths.end() \|\|
558	0	this->RealPaths.key_comp()(dir, i->first)) {
559	0	using value_type = std::map<std::string, std::string>::value_type;
560	0	i = this->RealPaths.insert(
561	0	i, value_type(dir, cmSystemTools::GetRealPath(dir)));
562	0	}
563	0	return i->second;
564	0	}