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:
cmOrderDirectoriesConstraint(cmOrderDirectories * od,std::string const & file)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
AddDirectory()57 void AddDirectory()
58 {
59 this->DirectoryIndex = this->OD->AddOriginalDirectory(this->Directory);
60 }
61
62 virtual void Report(std::ostream& e) = 0;
63
FindConflicts(unsigned int index)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
FindImplicitConflicts(std::ostringstream & w)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
FileMayConflict(std::string const & dir,std::string const & name)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:
cmOrderDirectoriesConstraintSOName(cmOrderDirectories * od,std::string const & file,const char * soname)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
Report(std::ostream & e)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
FindConflict(std::string const & dir)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:
cmOrderDirectoriesConstraintLibrary(cmOrderDirectories * od,std::string const & file)204 cmOrderDirectoriesConstraintLibrary(cmOrderDirectories* od,
205 std::string const& file)
206 : cmOrderDirectoriesConstraint(od, file)
207 {
208 }
209
Report(std::ostream & e)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
FindConflict(std::string const & dir)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
cmOrderDirectories(cmGlobalGenerator * gg,const cmGeneratorTarget * target,const char * purpose)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
GetOrderedDirectories()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
AddRuntimeLibrary(std::string const & fullPath,const char * soname)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
AddLinkLibrary(std::string const & fullPath)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
AddUserDirectories(std::vector<std::string> const & extra)329 void cmOrderDirectories::AddUserDirectories(
330 std::vector<std::string> const& extra)
331 {
332 cm::append(this->UserDirectories, extra);
333 }
334
AddLanguageDirectories(std::vector<std::string> const & dirs)335 void cmOrderDirectories::AddLanguageDirectories(
336 std::vector<std::string> const& dirs)
337 {
338 cm::append(this->LanguageDirectories, dirs);
339 }
340
SetImplicitDirectories(std::set<std::string> const & implicitDirs)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
IsImplicitDirectory(std::string const & dir)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
SetLinkExtensionInfo(std::vector<std::string> const & linkExtensions,std::string const & removeExtRegex)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
CollectOriginalDirectories()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
AddOriginalDirectory(std::string const & dir)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
AddOriginalDirectories(std::vector<std::string> const & dirs)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.
operator ()cmOrderDirectoriesCompare421 bool operator()(ConflictPair l, ConflictPair r)
422 {
423 return l.first == r.first;
424 }
425 };
426
FindConflicts()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
FindImplicitConflicts()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
OrderDirectories()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
VisitDirectory(unsigned int i)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
DiagnoseCycle()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
IsSameDirectory(std::string const & l,std::string const & r)548 bool cmOrderDirectories::IsSameDirectory(std::string const& l,
549 std::string const& r)
550 {
551 return this->GetRealPath(l) == this->GetRealPath(r);
552 }
553
GetRealPath(std::string const & dir)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 }
565