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 "cmComputeLinkDepends.h"
4
5 #include <algorithm>
6 #include <cassert>
7 #include <cstdio>
8 #include <iterator>
9 #include <sstream>
10 #include <unordered_map>
11 #include <utility>
12
13 #include <cm/memory>
14
15 #include "cmComputeComponentGraph.h"
16 #include "cmGeneratorTarget.h"
17 #include "cmGlobalGenerator.h"
18 #include "cmListFileCache.h"
19 #include "cmLocalGenerator.h"
20 #include "cmMakefile.h"
21 #include "cmRange.h"
22 #include "cmStateTypes.h"
23 #include "cmStringAlgorithms.h"
24 #include "cmTarget.h"
25 #include "cmValue.h"
26 #include "cmake.h"
27
28 /*
29
30 This file computes an ordered list of link items to use when linking a
31 single target in one configuration. Each link item is identified by
32 the string naming it. A graph of dependencies is created in which
33 each node corresponds to one item and directed edges lead from nodes to
34 those which must *follow* them on the link line. For example, the
35 graph
36
37 A -> B -> C
38
39 will lead to the link line order
40
41 A B C
42
43 The set of items placed in the graph is formed with a breadth-first
44 search of the link dependencies starting from the main target.
45
46 There are two types of items: those with known direct dependencies and
47 those without known dependencies. We will call the two types "known
48 items" and "unknown items", respectively. Known items are those whose
49 names correspond to targets (built or imported) and those for which an
50 old-style <item>_LIB_DEPENDS variable is defined. All other items are
51 unknown and we must infer dependencies for them. For items that look
52 like flags (beginning with '-') we trivially infer no dependencies,
53 and do not include them in the dependencies of other items.
54
55 Known items have dependency lists ordered based on how the user
56 specified them. We can use this order to infer potential dependencies
57 of unknown items. For example, if link items A and B are unknown and
58 items X and Y are known, then we might have the following dependency
59 lists:
60
61 X: Y A B
62 Y: A B
63
64 The explicitly known dependencies form graph edges
65
66 X -> Y , X -> A , X -> B , Y -> A , Y -> B
67
68 We can also infer the edge
69
70 A -> B
71
72 because *every* time A appears B is seen on its right. We do not know
73 whether A really needs symbols from B to link, but it *might* so we
74 must preserve their order. This is the case also for the following
75 explicit lists:
76
77 X: A B Y
78 Y: A B
79
80 Here, A is followed by the set {B,Y} in one list, and {B} in the other
81 list. The intersection of these sets is {B}, so we can infer that A
82 depends on at most B. Meanwhile B is followed by the set {Y} in one
83 list and {} in the other. The intersection is {} so we can infer that
84 B has no dependencies.
85
86 Let's make a more complex example by adding unknown item C and
87 considering these dependency lists:
88
89 X: A B Y C
90 Y: A C B
91
92 The explicit edges are
93
94 X -> Y , X -> A , X -> B , X -> C , Y -> A , Y -> B , Y -> C
95
96 For the unknown items, we infer dependencies by looking at the
97 "follow" sets:
98
99 A: intersect( {B,Y,C} , {C,B} ) = {B,C} ; infer edges A -> B , A -> C
100 B: intersect( {Y,C} , {} ) = {} ; infer no edges
101 C: intersect( {} , {B} ) = {} ; infer no edges
102
103 Note that targets are never inferred as dependees because outside
104 libraries should not depend on them.
105
106 ------------------------------------------------------------------------------
107
108 The initial exploration of dependencies using a BFS associates an
109 integer index with each link item. When the graph is built outgoing
110 edges are sorted by this index.
111
112 After the initial exploration of the link interface tree, any
113 transitive (dependent) shared libraries that were encountered and not
114 included in the interface are processed in their own BFS. This BFS
115 follows only the dependent library lists and not the link interfaces.
116 They are added to the link items with a mark indicating that the are
117 transitive dependencies. Then cmComputeLinkInformation deals with
118 them on a per-platform basis.
119
120 The complete graph formed from all known and inferred dependencies may
121 not be acyclic, so an acyclic version must be created.
122 The original graph is converted to a directed acyclic graph in which
123 each node corresponds to a strongly connected component of the
124 original graph. For example, the dependency graph
125
126 X -> A -> B -> C -> A -> Y
127
128 contains strongly connected components {X}, {A,B,C}, and {Y}. The
129 implied directed acyclic graph (DAG) is
130
131 {X} -> {A,B,C} -> {Y}
132
133 We then compute a topological order for the DAG nodes to serve as a
134 reference for satisfying dependencies efficiently. We perform the DFS
135 in reverse order and assign topological order indices counting down so
136 that the result is as close to the original BFS order as possible
137 without violating dependencies.
138
139 ------------------------------------------------------------------------------
140
141 The final link entry order is constructed as follows. We first walk
142 through and emit the *original* link line as specified by the user.
143 As each item is emitted, a set of pending nodes in the component DAG
144 is maintained. When a pending component has been completely seen, it
145 is removed from the pending set and its dependencies (following edges
146 of the DAG) are added. A trivial component (those with one item) is
147 complete as soon as its item is seen. A non-trivial component (one
148 with more than one item; assumed to be static libraries) is complete
149 when *all* its entries have been seen *twice* (all entries seen once,
150 then all entries seen again, not just each entry twice). A pending
151 component tracks which items have been seen and a count of how many
152 times the component needs to be seen (once for trivial components,
153 twice for non-trivial). If at any time another component finishes and
154 re-adds an already pending component, the pending component is reset
155 so that it needs to be seen in its entirety again. This ensures that
156 all dependencies of a component are satisfied no matter where it
157 appears.
158
159 After the original link line has been completed, we append to it the
160 remaining pending components and their dependencies. This is done by
161 repeatedly emitting the first item from the first pending component
162 and following the same update rules as when traversing the original
163 link line. Since the pending components are kept in topological order
164 they are emitted with minimal repeats (we do not want to emit a
165 component just to have it added again when another component is
166 completed later). This process continues until no pending components
167 remain. We know it will terminate because the component graph is
168 guaranteed to be acyclic.
169
170 The final list of items produced by this procedure consists of the
171 original user link line followed by minimal additional items needed to
172 satisfy dependencies. The final list is then filtered to de-duplicate
173 items that we know the linker will re-use automatically (shared libs).
174
175 */
176
cmComputeLinkDepends(const cmGeneratorTarget * target,const std::string & config)177 cmComputeLinkDepends::cmComputeLinkDepends(const cmGeneratorTarget* target,
178 const std::string& config)
179 {
180 // Store context information.
181 this->Target = target;
182 this->Makefile = this->Target->Target->GetMakefile();
183 this->GlobalGenerator =
184 this->Target->GetLocalGenerator()->GetGlobalGenerator();
185 this->CMakeInstance = this->GlobalGenerator->GetCMakeInstance();
186
187 // The configuration being linked.
188 this->HasConfig = !config.empty();
189 this->Config = (this->HasConfig) ? config : std::string();
190 std::vector<std::string> debugConfigs =
191 this->Makefile->GetCMakeInstance()->GetDebugConfigs();
192 this->LinkType = CMP0003_ComputeLinkType(this->Config, debugConfigs);
193
194 // Enable debug mode if requested.
195 this->DebugMode = this->Makefile->IsOn("CMAKE_LINK_DEPENDS_DEBUG_MODE");
196
197 // Assume no compatibility until set.
198 this->OldLinkDirMode = false;
199
200 // No computation has been done.
201 this->CCG = nullptr;
202 }
203
204 cmComputeLinkDepends::~cmComputeLinkDepends() = default;
205
SetOldLinkDirMode(bool b)206 void cmComputeLinkDepends::SetOldLinkDirMode(bool b)
207 {
208 this->OldLinkDirMode = b;
209 }
210
211 std::vector<cmComputeLinkDepends::LinkEntry> const&
Compute()212 cmComputeLinkDepends::Compute()
213 {
214 // Follow the link dependencies of the target to be linked.
215 this->AddDirectLinkEntries();
216
217 // Complete the breadth-first search of dependencies.
218 while (!this->BFSQueue.empty()) {
219 // Get the next entry.
220 BFSEntry qe = this->BFSQueue.front();
221 this->BFSQueue.pop();
222
223 // Follow the entry's dependencies.
224 this->FollowLinkEntry(qe);
225 }
226
227 // Complete the search of shared library dependencies.
228 while (!this->SharedDepQueue.empty()) {
229 // Handle the next entry.
230 this->HandleSharedDependency(this->SharedDepQueue.front());
231 this->SharedDepQueue.pop();
232 }
233
234 // Infer dependencies of targets for which they were not known.
235 this->InferDependencies();
236
237 // Cleanup the constraint graph.
238 this->CleanConstraintGraph();
239
240 // Display the constraint graph.
241 if (this->DebugMode) {
242 fprintf(stderr,
243 "---------------------------------------"
244 "---------------------------------------\n");
245 fprintf(stderr, "Link dependency analysis for target %s, config %s\n",
246 this->Target->GetName().c_str(),
247 this->HasConfig ? this->Config.c_str() : "noconfig");
248 this->DisplayConstraintGraph();
249 }
250
251 // Compute the final ordering.
252 this->OrderLinkEntires();
253
254 // Compute the final set of link entries.
255 // Iterate in reverse order so we can keep only the last occurrence
256 // of a shared library.
257 std::set<int> emitted;
258 for (int i : cmReverseRange(this->FinalLinkOrder)) {
259 LinkEntry const& e = this->EntryList[i];
260 cmGeneratorTarget const* t = e.Target;
261 // Entries that we know the linker will re-use do not need to be repeated.
262 bool uniquify = t && t->GetType() == cmStateEnums::SHARED_LIBRARY;
263 if (!uniquify || emitted.insert(i).second) {
264 this->FinalLinkEntries.push_back(e);
265 }
266 }
267 // Place explicitly linked object files in the front. The linker will
268 // always use them anyway, and they may depend on symbols from libraries.
269 // Append in reverse order since we reverse the final order below.
270 for (int i : cmReverseRange(this->ObjectEntries)) {
271 this->FinalLinkEntries.emplace_back(this->EntryList[i]);
272 }
273 // Reverse the resulting order since we iterated in reverse.
274 std::reverse(this->FinalLinkEntries.begin(), this->FinalLinkEntries.end());
275
276 // Display the final set.
277 if (this->DebugMode) {
278 this->DisplayFinalEntries();
279 }
280
281 return this->FinalLinkEntries;
282 }
283
AllocateLinkEntry(cmLinkItem const & item)284 std::map<cmLinkItem, int>::iterator cmComputeLinkDepends::AllocateLinkEntry(
285 cmLinkItem const& item)
286 {
287 std::map<cmLinkItem, int>::value_type index_entry(
288 item, static_cast<int>(this->EntryList.size()));
289 auto lei = this->LinkEntryIndex.insert(index_entry).first;
290 this->EntryList.emplace_back();
291 this->InferredDependSets.emplace_back();
292 this->EntryConstraintGraph.emplace_back();
293 return lei;
294 }
295
AddLinkEntry(cmLinkItem const & item)296 int cmComputeLinkDepends::AddLinkEntry(cmLinkItem const& item)
297 {
298 // Check if the item entry has already been added.
299 auto lei = this->LinkEntryIndex.find(item);
300 if (lei != this->LinkEntryIndex.end()) {
301 // Yes. We do not need to follow the item's dependencies again.
302 return lei->second;
303 }
304
305 // Allocate a spot for the item entry.
306 lei = this->AllocateLinkEntry(item);
307
308 // Initialize the item entry.
309 int index = lei->second;
310 LinkEntry& entry = this->EntryList[index];
311 entry.Item = BT<std::string>(item.AsStr(), item.Backtrace);
312 entry.Target = item.Target;
313 entry.IsFlag = (!entry.Target && entry.Item.Value[0] == '-' &&
314 entry.Item.Value[1] != 'l' &&
315 entry.Item.Value.substr(0, 10) != "-framework");
316
317 // If the item has dependencies queue it to follow them.
318 if (entry.Target) {
319 // Target dependencies are always known. Follow them.
320 BFSEntry qe = { index, nullptr };
321 this->BFSQueue.push(qe);
322 } else {
323 // Look for an old-style <item>_LIB_DEPENDS variable.
324 std::string var = cmStrCat(entry.Item.Value, "_LIB_DEPENDS");
325 if (cmValue val = this->Makefile->GetDefinition(var)) {
326 // The item dependencies are known. Follow them.
327 BFSEntry qe = { index, val->c_str() };
328 this->BFSQueue.push(qe);
329 } else if (!entry.IsFlag) {
330 // The item dependencies are not known. We need to infer them.
331 this->InferredDependSets[index].Initialized = true;
332 }
333 }
334
335 return index;
336 }
337
AddLinkObject(cmLinkItem const & item)338 void cmComputeLinkDepends::AddLinkObject(cmLinkItem const& item)
339 {
340 // Check if the item entry has already been added.
341 auto lei = this->LinkEntryIndex.find(item);
342 if (lei != this->LinkEntryIndex.end()) {
343 return;
344 }
345
346 // Allocate a spot for the item entry.
347 lei = this->AllocateLinkEntry(item);
348
349 // Initialize the item entry.
350 int index = lei->second;
351 LinkEntry& entry = this->EntryList[index];
352 entry.Item = BT<std::string>(item.AsStr(), item.Backtrace);
353 entry.IsObject = true;
354
355 // Record explicitly linked object files separately.
356 this->ObjectEntries.emplace_back(index);
357 }
358
FollowLinkEntry(BFSEntry qe)359 void cmComputeLinkDepends::FollowLinkEntry(BFSEntry qe)
360 {
361 // Get this entry representation.
362 int depender_index = qe.Index;
363 LinkEntry const& entry = this->EntryList[depender_index];
364
365 // Follow the item's dependencies.
366 if (entry.Target) {
367 // Follow the target dependencies.
368 if (cmLinkInterface const* iface =
369 entry.Target->GetLinkInterface(this->Config, this->Target)) {
370 const bool isIface =
371 entry.Target->GetType() == cmStateEnums::INTERFACE_LIBRARY;
372 // This target provides its own link interface information.
373 this->AddLinkEntries(depender_index, iface->Libraries);
374 this->AddLinkObjects(iface->Objects);
375 for (auto const& language : iface->Languages) {
376 auto runtimeEntries = iface->LanguageRuntimeLibraries.find(language);
377 if (runtimeEntries != iface->LanguageRuntimeLibraries.end()) {
378 this->AddLinkEntries(depender_index, runtimeEntries->second);
379 }
380 }
381
382 if (isIface) {
383 return;
384 }
385
386 // Handle dependent shared libraries.
387 this->FollowSharedDeps(depender_index, iface);
388
389 // Support for CMP0003.
390 for (cmLinkItem const& oi : iface->WrongConfigLibraries) {
391 this->CheckWrongConfigItem(oi);
392 }
393 }
394 } else {
395 // Follow the old-style dependency list.
396 this->AddVarLinkEntries(depender_index, qe.LibDepends);
397 }
398 }
399
FollowSharedDeps(int depender_index,cmLinkInterface const * iface,bool follow_interface)400 void cmComputeLinkDepends::FollowSharedDeps(int depender_index,
401 cmLinkInterface const* iface,
402 bool follow_interface)
403 {
404 // Follow dependencies if we have not followed them already.
405 if (this->SharedDepFollowed.insert(depender_index).second) {
406 if (follow_interface) {
407 this->QueueSharedDependencies(depender_index, iface->Libraries);
408 }
409 this->QueueSharedDependencies(depender_index, iface->SharedDeps);
410 }
411 }
412
QueueSharedDependencies(int depender_index,std::vector<cmLinkItem> const & deps)413 void cmComputeLinkDepends::QueueSharedDependencies(
414 int depender_index, std::vector<cmLinkItem> const& deps)
415 {
416 for (cmLinkItem const& li : deps) {
417 SharedDepEntry qe;
418 qe.Item = li;
419 qe.DependerIndex = depender_index;
420 this->SharedDepQueue.push(qe);
421 }
422 }
423
HandleSharedDependency(SharedDepEntry const & dep)424 void cmComputeLinkDepends::HandleSharedDependency(SharedDepEntry const& dep)
425 {
426 // Check if the target already has an entry.
427 auto lei = this->LinkEntryIndex.find(dep.Item);
428 if (lei == this->LinkEntryIndex.end()) {
429 // Allocate a spot for the item entry.
430 lei = this->AllocateLinkEntry(dep.Item);
431
432 // Initialize the item entry.
433 LinkEntry& entry = this->EntryList[lei->second];
434 entry.Item = BT<std::string>(dep.Item.AsStr(), dep.Item.Backtrace);
435 entry.Target = dep.Item.Target;
436
437 // This item was added specifically because it is a dependent
438 // shared library. It may get special treatment
439 // in cmComputeLinkInformation.
440 entry.IsSharedDep = true;
441 }
442
443 // Get the link entry for this target.
444 int index = lei->second;
445 LinkEntry& entry = this->EntryList[index];
446
447 // This shared library dependency must follow the item that listed
448 // it.
449 this->EntryConstraintGraph[dep.DependerIndex].emplace_back(
450 index, true, false, cmListFileBacktrace());
451
452 // Target items may have their own dependencies.
453 if (entry.Target) {
454 if (cmLinkInterface const* iface =
455 entry.Target->GetLinkInterface(this->Config, this->Target)) {
456 // Follow public and private dependencies transitively.
457 this->FollowSharedDeps(index, iface, true);
458 }
459 }
460 }
461
AddVarLinkEntries(int depender_index,const char * value)462 void cmComputeLinkDepends::AddVarLinkEntries(int depender_index,
463 const char* value)
464 {
465 // This is called to add the dependencies named by
466 // <item>_LIB_DEPENDS. The variable contains a semicolon-separated
467 // list. The list contains link-type;item pairs and just items.
468 std::vector<std::string> deplist = cmExpandedList(value);
469
470 // Look for entries meant for this configuration.
471 std::vector<cmLinkItem> actual_libs;
472 cmTargetLinkLibraryType llt = GENERAL_LibraryType;
473 bool haveLLT = false;
474 for (std::string const& d : deplist) {
475 if (d == "debug") {
476 llt = DEBUG_LibraryType;
477 haveLLT = true;
478 } else if (d == "optimized") {
479 llt = OPTIMIZED_LibraryType;
480 haveLLT = true;
481 } else if (d == "general") {
482 llt = GENERAL_LibraryType;
483 haveLLT = true;
484 } else if (!d.empty()) {
485 // If no explicit link type was given prior to this entry then
486 // check if the entry has its own link type variable. This is
487 // needed for compatibility with dependency files generated by
488 // the export_library_dependencies command from CMake 2.4 and
489 // lower.
490 if (!haveLLT) {
491 std::string var = cmStrCat(d, "_LINK_TYPE");
492 if (cmValue val = this->Makefile->GetDefinition(var)) {
493 if (*val == "debug") {
494 llt = DEBUG_LibraryType;
495 } else if (*val == "optimized") {
496 llt = OPTIMIZED_LibraryType;
497 }
498 }
499 }
500
501 // If the library is meant for this link type then use it.
502 if (llt == GENERAL_LibraryType || llt == this->LinkType) {
503 actual_libs.emplace_back(this->ResolveLinkItem(depender_index, d));
504 } else if (this->OldLinkDirMode) {
505 cmLinkItem item = this->ResolveLinkItem(depender_index, d);
506 this->CheckWrongConfigItem(item);
507 }
508
509 // Reset the link type until another explicit type is given.
510 llt = GENERAL_LibraryType;
511 haveLLT = false;
512 }
513 }
514
515 // Add the entries from this list.
516 this->AddLinkEntries(depender_index, actual_libs);
517 }
518
AddDirectLinkEntries()519 void cmComputeLinkDepends::AddDirectLinkEntries()
520 {
521 // Add direct link dependencies in this configuration.
522 cmLinkImplementation const* impl =
523 this->Target->GetLinkImplementation(this->Config);
524 this->AddLinkEntries(-1, impl->Libraries);
525 this->AddLinkObjects(impl->Objects);
526
527 for (auto const& language : impl->Languages) {
528 auto runtimeEntries = impl->LanguageRuntimeLibraries.find(language);
529 if (runtimeEntries != impl->LanguageRuntimeLibraries.end()) {
530 this->AddLinkEntries(-1, runtimeEntries->second);
531 }
532 }
533 for (cmLinkItem const& wi : impl->WrongConfigLibraries) {
534 this->CheckWrongConfigItem(wi);
535 }
536 }
537
538 template <typename T>
AddLinkEntries(int depender_index,std::vector<T> const & libs)539 void cmComputeLinkDepends::AddLinkEntries(int depender_index,
540 std::vector<T> const& libs)
541 {
542 // Track inferred dependency sets implied by this list.
543 std::map<int, DependSet> dependSets;
544
545 // Loop over the libraries linked directly by the depender.
546 for (T const& l : libs) {
547 // Skip entries that will resolve to the target getting linked or
548 // are empty.
549 cmLinkItem const& item = l;
550 if (item.AsStr() == this->Target->GetName() || item.AsStr().empty()) {
551 continue;
552 }
553
554 // Add a link entry for this item.
555 int dependee_index = this->AddLinkEntry(l);
556
557 // The dependee must come after the depender.
558 if (depender_index >= 0) {
559 this->EntryConstraintGraph[depender_index].emplace_back(
560 dependee_index, false, false, cmListFileBacktrace());
561 } else {
562 // This is a direct dependency of the target being linked.
563 this->OriginalEntries.push_back(dependee_index);
564 }
565
566 // Update the inferred dependencies for earlier items.
567 for (auto& dependSet : dependSets) {
568 // Add this item to the inferred dependencies of other items.
569 // Target items are never inferred dependees because unknown
570 // items are outside libraries that should not be depending on
571 // targets.
572 if (!this->EntryList[dependee_index].Target &&
573 !this->EntryList[dependee_index].IsFlag &&
574 dependee_index != dependSet.first) {
575 dependSet.second.insert(dependee_index);
576 }
577 }
578
579 // If this item needs to have dependencies inferred, do so.
580 if (this->InferredDependSets[dependee_index].Initialized) {
581 // Make sure an entry exists to hold the set for the item.
582 dependSets[dependee_index];
583 }
584 }
585
586 // Store the inferred dependency sets discovered for this list.
587 for (auto const& dependSet : dependSets) {
588 this->InferredDependSets[dependSet.first].push_back(dependSet.second);
589 }
590 }
591
AddLinkObjects(std::vector<cmLinkItem> const & objs)592 void cmComputeLinkDepends::AddLinkObjects(std::vector<cmLinkItem> const& objs)
593 {
594 for (cmLinkItem const& obj : objs) {
595 this->AddLinkObject(obj);
596 }
597 }
598
ResolveLinkItem(int depender_index,const std::string & name)599 cmLinkItem cmComputeLinkDepends::ResolveLinkItem(int depender_index,
600 const std::string& name)
601 {
602 // Look for a target in the scope of the depender.
603 cmGeneratorTarget const* from = this->Target;
604 if (depender_index >= 0) {
605 if (cmGeneratorTarget const* depender =
606 this->EntryList[depender_index].Target) {
607 from = depender;
608 }
609 }
610 return from->ResolveLinkItem(BT<std::string>(name));
611 }
612
InferDependencies()613 void cmComputeLinkDepends::InferDependencies()
614 {
615 // The inferred dependency sets for each item list the possible
616 // dependencies. The intersection of the sets for one item form its
617 // inferred dependencies.
618 for (unsigned int depender_index = 0;
619 depender_index < this->InferredDependSets.size(); ++depender_index) {
620 // Skip items for which dependencies do not need to be inferred or
621 // for which the inferred dependency sets are empty.
622 DependSetList& sets = this->InferredDependSets[depender_index];
623 if (!sets.Initialized || sets.empty()) {
624 continue;
625 }
626
627 // Intersect the sets for this item.
628 DependSet common = sets.front();
629 for (DependSet const& i : cmMakeRange(sets).advance(1)) {
630 DependSet intersection;
631 std::set_intersection(common.begin(), common.end(), i.begin(), i.end(),
632 std::inserter(intersection, intersection.begin()));
633 common = intersection;
634 }
635
636 // Add the inferred dependencies to the graph.
637 cmGraphEdgeList& edges = this->EntryConstraintGraph[depender_index];
638 edges.reserve(edges.size() + common.size());
639 for (auto const& c : common) {
640 edges.emplace_back(c, true, false, cmListFileBacktrace());
641 }
642 }
643 }
644
CleanConstraintGraph()645 void cmComputeLinkDepends::CleanConstraintGraph()
646 {
647 for (cmGraphEdgeList& edgeList : this->EntryConstraintGraph) {
648 // Sort the outgoing edges for each graph node so that the
649 // original order will be preserved as much as possible.
650 std::sort(edgeList.begin(), edgeList.end());
651
652 // Make the edge list unique.
653 edgeList.erase(std::unique(edgeList.begin(), edgeList.end()),
654 edgeList.end());
655 }
656 }
657
DisplayConstraintGraph()658 void cmComputeLinkDepends::DisplayConstraintGraph()
659 {
660 // Display the graph nodes and their edges.
661 std::ostringstream e;
662 for (unsigned int i = 0; i < this->EntryConstraintGraph.size(); ++i) {
663 EdgeList const& nl = this->EntryConstraintGraph[i];
664 e << "item " << i << " is [" << this->EntryList[i].Item << "]\n";
665 e << cmWrap(" item ", nl, " must follow it", "\n") << "\n";
666 }
667 fprintf(stderr, "%s\n", e.str().c_str());
668 }
669
OrderLinkEntires()670 void cmComputeLinkDepends::OrderLinkEntires()
671 {
672 // Compute the DAG of strongly connected components. The algorithm
673 // used by cmComputeComponentGraph should identify the components in
674 // the same order in which the items were originally discovered in
675 // the BFS. This should preserve the original order when no
676 // constraints disallow it.
677 this->CCG =
678 cm::make_unique<cmComputeComponentGraph>(this->EntryConstraintGraph);
679 this->CCG->Compute();
680
681 // The component graph is guaranteed to be acyclic. Start a DFS
682 // from every entry to compute a topological order for the
683 // components.
684 Graph const& cgraph = this->CCG->GetComponentGraph();
685 int n = static_cast<int>(cgraph.size());
686 this->ComponentVisited.resize(cgraph.size(), 0);
687 this->ComponentOrder.resize(cgraph.size(), n);
688 this->ComponentOrderId = n;
689 // Run in reverse order so the topological order will preserve the
690 // original order where there are no constraints.
691 for (int c = n - 1; c >= 0; --c) {
692 this->VisitComponent(c);
693 }
694
695 // Display the component graph.
696 if (this->DebugMode) {
697 this->DisplayComponents();
698 }
699
700 // Start with the original link line.
701 for (int originalEntry : this->OriginalEntries) {
702 this->VisitEntry(originalEntry);
703 }
704
705 // Now explore anything left pending. Since the component graph is
706 // guaranteed to be acyclic we know this will terminate.
707 while (!this->PendingComponents.empty()) {
708 // Visit one entry from the first pending component. The visit
709 // logic will update the pending components accordingly. Since
710 // the pending components are kept in topological order this will
711 // not repeat one.
712 int e = *this->PendingComponents.begin()->second.Entries.begin();
713 this->VisitEntry(e);
714 }
715 }
716
DisplayComponents()717 void cmComputeLinkDepends::DisplayComponents()
718 {
719 fprintf(stderr, "The strongly connected components are:\n");
720 std::vector<NodeList> const& components = this->CCG->GetComponents();
721 for (unsigned int c = 0; c < components.size(); ++c) {
722 fprintf(stderr, "Component (%u):\n", c);
723 NodeList const& nl = components[c];
724 for (int i : nl) {
725 fprintf(stderr, " item %d [%s]\n", i,
726 this->EntryList[i].Item.Value.c_str());
727 }
728 EdgeList const& ol = this->CCG->GetComponentGraphEdges(c);
729 for (cmGraphEdge const& oi : ol) {
730 int i = oi;
731 fprintf(stderr, " followed by Component (%d)\n", i);
732 }
733 fprintf(stderr, " topo order index %d\n", this->ComponentOrder[c]);
734 }
735 fprintf(stderr, "\n");
736 }
737
VisitComponent(unsigned int c)738 void cmComputeLinkDepends::VisitComponent(unsigned int c)
739 {
740 // Check if the node has already been visited.
741 if (this->ComponentVisited[c]) {
742 return;
743 }
744
745 // We are now visiting this component so mark it.
746 this->ComponentVisited[c] = 1;
747
748 // Visit the neighbors of the component first.
749 // Run in reverse order so the topological order will preserve the
750 // original order where there are no constraints.
751 EdgeList const& nl = this->CCG->GetComponentGraphEdges(c);
752 for (cmGraphEdge const& edge : cmReverseRange(nl)) {
753 this->VisitComponent(edge);
754 }
755
756 // Assign an ordering id to this component.
757 this->ComponentOrder[c] = --this->ComponentOrderId;
758 }
759
VisitEntry(int index)760 void cmComputeLinkDepends::VisitEntry(int index)
761 {
762 // Include this entry on the link line.
763 this->FinalLinkOrder.push_back(index);
764
765 // This entry has now been seen. Update its component.
766 bool completed = false;
767 int component = this->CCG->GetComponentMap()[index];
768 auto mi = this->PendingComponents.find(this->ComponentOrder[component]);
769 if (mi != this->PendingComponents.end()) {
770 // The entry is in an already pending component.
771 PendingComponent& pc = mi->second;
772
773 // Remove the entry from those pending in its component.
774 pc.Entries.erase(index);
775 if (pc.Entries.empty()) {
776 // The complete component has been seen since it was last needed.
777 --pc.Count;
778
779 if (pc.Count == 0) {
780 // The component has been completed.
781 this->PendingComponents.erase(mi);
782 completed = true;
783 } else {
784 // The whole component needs to be seen again.
785 NodeList const& nl = this->CCG->GetComponent(component);
786 assert(nl.size() > 1);
787 pc.Entries.insert(nl.begin(), nl.end());
788 }
789 }
790 } else {
791 // The entry is not in an already pending component.
792 NodeList const& nl = this->CCG->GetComponent(component);
793 if (nl.size() > 1) {
794 // This is a non-trivial component. It is now pending.
795 PendingComponent& pc = this->MakePendingComponent(component);
796
797 // The starting entry has already been seen.
798 pc.Entries.erase(index);
799 } else {
800 // This is a trivial component, so it is already complete.
801 completed = true;
802 }
803 }
804
805 // If the entry completed a component, the component's dependencies
806 // are now pending.
807 if (completed) {
808 EdgeList const& ol = this->CCG->GetComponentGraphEdges(component);
809 for (cmGraphEdge const& oi : ol) {
810 // This entire component is now pending no matter whether it has
811 // been partially seen already.
812 this->MakePendingComponent(oi);
813 }
814 }
815 }
816
817 cmComputeLinkDepends::PendingComponent&
MakePendingComponent(unsigned int component)818 cmComputeLinkDepends::MakePendingComponent(unsigned int component)
819 {
820 // Create an entry (in topological order) for the component.
821 PendingComponent& pc =
822 this->PendingComponents[this->ComponentOrder[component]];
823 pc.Id = component;
824 NodeList const& nl = this->CCG->GetComponent(component);
825
826 if (nl.size() == 1) {
827 // Trivial components need be seen only once.
828 pc.Count = 1;
829 } else {
830 // This is a non-trivial strongly connected component of the
831 // original graph. It consists of two or more libraries
832 // (archives) that mutually require objects from one another. In
833 // the worst case we may have to repeat the list of libraries as
834 // many times as there are object files in the biggest archive.
835 // For now we just list them twice.
836 //
837 // The list of items in the component has been sorted by the order
838 // of discovery in the original BFS of dependencies. This has the
839 // advantage that the item directly linked by a target requiring
840 // this component will come first which minimizes the number of
841 // repeats needed.
842 pc.Count = this->ComputeComponentCount(nl);
843 }
844
845 // Store the entries to be seen.
846 pc.Entries.insert(nl.begin(), nl.end());
847
848 return pc;
849 }
850
ComputeComponentCount(NodeList const & nl)851 int cmComputeLinkDepends::ComputeComponentCount(NodeList const& nl)
852 {
853 unsigned int count = 2;
854 for (int ni : nl) {
855 if (cmGeneratorTarget const* target = this->EntryList[ni].Target) {
856 if (cmLinkInterface const* iface =
857 target->GetLinkInterface(this->Config, this->Target)) {
858 if (iface->Multiplicity > count) {
859 count = iface->Multiplicity;
860 }
861 }
862 }
863 }
864 return count;
865 }
866
DisplayFinalEntries()867 void cmComputeLinkDepends::DisplayFinalEntries()
868 {
869 fprintf(stderr, "target [%s] links to:\n", this->Target->GetName().c_str());
870 for (LinkEntry const& lei : this->FinalLinkEntries) {
871 if (lei.Target) {
872 fprintf(stderr, " target [%s]\n", lei.Target->GetName().c_str());
873 } else {
874 fprintf(stderr, " item [%s]\n", lei.Item.Value.c_str());
875 }
876 }
877 fprintf(stderr, "\n");
878 }
879
CheckWrongConfigItem(cmLinkItem const & item)880 void cmComputeLinkDepends::CheckWrongConfigItem(cmLinkItem const& item)
881 {
882 if (!this->OldLinkDirMode) {
883 return;
884 }
885
886 // For CMake 2.4 bug-compatibility we need to consider the output
887 // directories of targets linked in another configuration as link
888 // directories.
889 if (item.Target && !item.Target->IsImported()) {
890 this->OldWrongConfigItems.insert(item.Target);
891 }
892 }
893