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"
10 #include <unordered_map>
14 #include <cm/string_view>
15 #include <cmext/string_view>
17 #include "cmComputeComponentGraph.h"
18 #include "cmGeneratorExpression.h"
19 #include "cmGeneratorExpressionDAGChecker.h"
20 #include "cmGeneratorTarget.h"
21 #include "cmGlobalGenerator.h"
22 #include "cmListFileCache.h"
23 #include "cmLocalGenerator.h"
24 #include "cmMakefile.h"
25 #include "cmMessageType.h"
27 #include "cmStateTypes.h"
28 #include "cmStringAlgorithms.h"
35 This file computes an ordered list of link items to use when linking a
36 single target in one configuration. Each link item is identified by
37 the string naming it. A graph of dependencies is created in which
38 each node corresponds to one item and directed edges lead from nodes to
39 those which must *follow* them on the link line. For example, the
44 will lead to the link line order
48 The set of items placed in the graph is formed with a breadth-first
49 search of the link dependencies starting from the main target.
51 There are two types of items: those with known direct dependencies and
52 those without known dependencies. We will call the two types "known
53 items" and "unknown items", respectively. Known items are those whose
54 names correspond to targets (built or imported) and those for which an
55 old-style <item>_LIB_DEPENDS variable is defined. All other items are
56 unknown and we must infer dependencies for them. For items that look
57 like flags (beginning with '-') we trivially infer no dependencies,
58 and do not include them in the dependencies of other items.
60 Known items have dependency lists ordered based on how the user
61 specified them. We can use this order to infer potential dependencies
62 of unknown items. For example, if link items A and B are unknown and
63 items X and Y are known, then we might have the following dependency
69 The explicitly known dependencies form graph edges
71 X -> Y , X -> A , X -> B , Y -> A , Y -> B
73 We can also infer the edge
77 because *every* time A appears B is seen on its right. We do not know
78 whether A really needs symbols from B to link, but it *might* so we
79 must preserve their order. This is the case also for the following
85 Here, A is followed by the set {B,Y} in one list, and {B} in the other
86 list. The intersection of these sets is {B}, so we can infer that A
87 depends on at most B. Meanwhile B is followed by the set {Y} in one
88 list and {} in the other. The intersection is {} so we can infer that
89 B has no dependencies.
91 Let's make a more complex example by adding unknown item C and
92 considering these dependency lists:
97 The explicit edges are
99 X -> Y , X -> A , X -> B , X -> C , Y -> A , Y -> B , Y -> C
101 For the unknown items, we infer dependencies by looking at the
104 A: intersect( {B,Y,C} , {C,B} ) = {B,C} ; infer edges A -> B , A -> C
105 B: intersect( {Y,C} , {} ) = {} ; infer no edges
106 C: intersect( {} , {B} ) = {} ; infer no edges
108 Note that targets are never inferred as dependees because outside
109 libraries should not depend on them.
111 ------------------------------------------------------------------------------
113 The initial exploration of dependencies using a BFS associates an
114 integer index with each link item. When the graph is built outgoing
115 edges are sorted by this index.
117 After the initial exploration of the link interface tree, any
118 transitive (dependent) shared libraries that were encountered and not
119 included in the interface are processed in their own BFS. This BFS
120 follows only the dependent library lists and not the link interfaces.
121 They are added to the link items with a mark indicating that the are
122 transitive dependencies. Then cmComputeLinkInformation deals with
123 them on a per-platform basis.
125 The complete graph formed from all known and inferred dependencies may
126 not be acyclic, so an acyclic version must be created.
127 The original graph is converted to a directed acyclic graph in which
128 each node corresponds to a strongly connected component of the
129 original graph. For example, the dependency graph
131 X -> A -> B -> C -> A -> Y
133 contains strongly connected components {X}, {A,B,C}, and {Y}. The
134 implied directed acyclic graph (DAG) is
136 {X} -> {A,B,C} -> {Y}
138 We then compute a topological order for the DAG nodes to serve as a
139 reference for satisfying dependencies efficiently. We perform the DFS
140 in reverse order and assign topological order indices counting down so
141 that the result is as close to the original BFS order as possible
142 without violating dependencies.
144 ------------------------------------------------------------------------------
146 The final link entry order is constructed as follows. We first walk
147 through and emit the *original* link line as specified by the user.
148 As each item is emitted, a set of pending nodes in the component DAG
149 is maintained. When a pending component has been completely seen, it
150 is removed from the pending set and its dependencies (following edges
151 of the DAG) are added. A trivial component (those with one item) is
152 complete as soon as its item is seen. A non-trivial component (one
153 with more than one item; assumed to be static libraries) is complete
154 when *all* its entries have been seen *twice* (all entries seen once,
155 then all entries seen again, not just each entry twice). A pending
156 component tracks which items have been seen and a count of how many
157 times the component needs to be seen (once for trivial components,
158 twice for non-trivial). If at any time another component finishes and
159 re-adds an already pending component, the pending component is reset
160 so that it needs to be seen in its entirety again. This ensures that
161 all dependencies of a component are satisfied no matter where it
164 After the original link line has been completed, we append to it the
165 remaining pending components and their dependencies. This is done by
166 repeatedly emitting the first item from the first pending component
167 and following the same update rules as when traversing the original
168 link line. Since the pending components are kept in topological order
169 they are emitted with minimal repeats (we do not want to emit a
170 component just to have it added again when another component is
171 completed later). This process continues until no pending components
172 remain. We know it will terminate because the component graph is
173 guaranteed to be acyclic.
175 The final list of items produced by this procedure consists of the
176 original user link line followed by minimal additional items needed to
177 satisfy dependencies. The final list is then filtered to de-duplicate
178 items that we know the linker will re-use automatically (shared libs).
183 // LINK_LIBRARY helpers
184 const auto LL_BEGIN = "<LINK_LIBRARY:"_s;
185 const auto LL_END = "</LINK_LIBRARY:"_s;
187 inline std::string ExtractFeature(std::string const& item)
189 return item.substr(LL_BEGIN.length(),
190 item.find('>', LL_BEGIN.length()) - LL_BEGIN.length());
193 bool IsFeatureSupported(cmMakefile* makefile, std::string const& linkLanguage,
194 std::string const& feature)
196 auto featureSupported = cmStrCat(
197 "CMAKE_", linkLanguage, "_LINK_LIBRARY_USING_", feature, "_SUPPORTED");
198 if (makefile->GetDefinition(featureSupported).IsOn()) {
203 cmStrCat("CMAKE_LINK_LIBRARY_USING_", feature, "_SUPPORTED");
204 return makefile->GetDefinition(featureSupported).IsOn();
207 // LINK_GROUP helpers
208 const auto LG_BEGIN = "<LINK_GROUP:"_s;
209 const auto LG_END = "</LINK_GROUP:"_s;
211 inline std::string ExtractGroupFeature(std::string const& item)
213 return item.substr(LG_BEGIN.length(),
214 item.find(':', LG_BEGIN.length()) - LG_BEGIN.length());
217 bool IsGroupFeatureSupported(cmMakefile* makefile,
218 std::string const& linkLanguage,
219 std::string const& feature)
221 auto featureSupported = cmStrCat(
222 "CMAKE_", linkLanguage, "_LINK_GROUP_USING_", feature, "_SUPPORTED");
223 if (makefile->GetDefinition(featureSupported).IsOn()) {
228 cmStrCat("CMAKE_LINK_GROUP_USING_", feature, "_SUPPORTED");
229 return makefile->GetDefinition(featureSupported).IsOn();
233 const std::string cmComputeLinkDepends::LinkEntry::DEFAULT = "DEFAULT";
235 cmComputeLinkDepends::cmComputeLinkDepends(const cmGeneratorTarget* target,
236 const std::string& config,
237 const std::string& linkLanguage)
239 // Store context information.
240 this->Target = target;
241 this->Makefile = this->Target->Target->GetMakefile();
242 this->GlobalGenerator =
243 this->Target->GetLocalGenerator()->GetGlobalGenerator();
244 this->CMakeInstance = this->GlobalGenerator->GetCMakeInstance();
245 this->LinkLanguage = linkLanguage;
247 // target oriented feature override property takes precedence over
248 // global override property
249 cm::string_view lloPrefix = "LINK_LIBRARY_OVERRIDE_"_s;
250 auto const& keys = this->Target->GetPropertyKeys();
252 keys.cbegin(), keys.cend(),
253 [this, &lloPrefix, &config, &linkLanguage](std::string const& key) {
254 if (cmHasPrefix(key, lloPrefix)) {
255 if (cmValue feature = this->Target->GetProperty(key)) {
256 if (!feature->empty() && key.length() > lloPrefix.length()) {
257 auto item = key.substr(lloPrefix.length());
258 cmGeneratorExpressionDAGChecker dag{ this->Target->GetBacktrace(),
260 "LINK_LIBRARY_OVERRIDE",
262 auto overrideFeature = cmGeneratorExpression::Evaluate(
263 feature, this->Target->GetLocalGenerator(), config, this->Target,
264 &dag, this->Target, linkLanguage);
265 this->LinkLibraryOverride.emplace(item, overrideFeature);
270 // global override property
271 if (cmValue linkLibraryOverride =
272 this->Target->GetProperty("LINK_LIBRARY_OVERRIDE")) {
273 cmGeneratorExpressionDAGChecker dag{ target->GetBacktrace(), target,
274 "LINK_LIBRARY_OVERRIDE", nullptr,
276 auto overrideValue = cmGeneratorExpression::Evaluate(
277 linkLibraryOverride, target->GetLocalGenerator(), config, target, &dag,
278 target, linkLanguage);
280 auto overrideList = cmTokenize(overrideValue, ","_s);
281 if (overrideList.size() >= 2) {
282 auto const& feature = overrideList.front();
283 for_each(overrideList.cbegin() + 1, overrideList.cend(),
284 [this, &feature](std::string const& item) {
285 this->LinkLibraryOverride.emplace(item, feature);
290 // The configuration being linked.
291 this->HasConfig = !config.empty();
292 this->Config = (this->HasConfig) ? config : std::string();
293 std::vector<std::string> debugConfigs =
294 this->Makefile->GetCMakeInstance()->GetDebugConfigs();
295 this->LinkType = CMP0003_ComputeLinkType(this->Config, debugConfigs);
297 // Enable debug mode if requested.
298 this->DebugMode = this->Makefile->IsOn("CMAKE_LINK_DEPENDS_DEBUG_MODE");
300 // Assume no compatibility until set.
301 this->OldLinkDirMode = false;
303 // No computation has been done.
307 cmComputeLinkDepends::~cmComputeLinkDepends() = default;
309 void cmComputeLinkDepends::SetOldLinkDirMode(bool b)
311 this->OldLinkDirMode = b;
314 std::vector<cmComputeLinkDepends::LinkEntry> const&
315 cmComputeLinkDepends::Compute()
317 // Follow the link dependencies of the target to be linked.
318 this->AddDirectLinkEntries();
320 // Complete the breadth-first search of dependencies.
321 while (!this->BFSQueue.empty()) {
322 // Get the next entry.
323 BFSEntry qe = this->BFSQueue.front();
324 this->BFSQueue.pop();
326 // Follow the entry's dependencies.
327 this->FollowLinkEntry(qe);
330 // Complete the search of shared library dependencies.
331 while (!this->SharedDepQueue.empty()) {
332 // Handle the next entry.
333 this->HandleSharedDependency(this->SharedDepQueue.front());
334 this->SharedDepQueue.pop();
337 // Infer dependencies of targets for which they were not known.
338 this->InferDependencies();
340 // finalize groups dependencies
341 // All dependencies which are raw items must be replaced by the group
342 // it belongs to, if any.
343 this->UpdateGroupDependencies();
345 // Cleanup the constraint graph.
346 this->CleanConstraintGraph();
348 // Display the constraint graph.
349 if (this->DebugMode) {
351 "---------------------------------------"
352 "---------------------------------------\n");
353 fprintf(stderr, "Link dependency analysis for target %s, config %s\n",
354 this->Target->GetName().c_str(),
355 this->HasConfig ? this->Config.c_str() : "noconfig");
356 this->DisplayConstraintGraph();
359 // Compute the DAG of strongly connected components. The algorithm
360 // used by cmComputeComponentGraph should identify the components in
361 // the same order in which the items were originally discovered in
362 // the BFS. This should preserve the original order when no
363 // constraints disallow it.
365 cm::make_unique<cmComputeComponentGraph>(this->EntryConstraintGraph);
366 this->CCG->Compute();
368 if (!this->CheckCircularDependencies()) {
369 return this->FinalLinkEntries;
372 // Compute the final ordering.
373 this->OrderLinkEntries();
375 // Compute the final set of link entries.
376 // Iterate in reverse order so we can keep only the last occurrence
377 // of a shared library.
378 std::set<int> emitted;
379 for (int i : cmReverseRange(this->FinalLinkOrder)) {
380 LinkEntry const& e = this->EntryList[i];
381 cmGeneratorTarget const* t = e.Target;
382 // Entries that we know the linker will re-use do not need to be repeated.
383 bool uniquify = t && t->GetType() == cmStateEnums::SHARED_LIBRARY;
384 if (!uniquify || emitted.insert(i).second) {
385 this->FinalLinkEntries.push_back(e);
388 // Place explicitly linked object files in the front. The linker will
389 // always use them anyway, and they may depend on symbols from libraries.
390 // Append in reverse order since we reverse the final order below.
391 for (int i : cmReverseRange(this->ObjectEntries)) {
392 this->FinalLinkEntries.emplace_back(this->EntryList[i]);
394 // Reverse the resulting order since we iterated in reverse.
395 std::reverse(this->FinalLinkEntries.begin(), this->FinalLinkEntries.end());
397 // Expand group items
398 if (!this->GroupItems.empty()) {
399 for (const auto& group : this->GroupItems) {
400 const LinkEntry& groupEntry = this->EntryList[group.first];
401 auto it = this->FinalLinkEntries.begin();
403 it = std::find_if(it, this->FinalLinkEntries.end(),
404 [&groupEntry](const LinkEntry& entry) -> bool {
405 return groupEntry.Item == entry.Item;
407 if (it == this->FinalLinkEntries.end()) {
410 it->Item.Value = "</LINK_GROUP>";
411 for (auto i = group.second.rbegin(); i != group.second.rend(); ++i) {
412 it = this->FinalLinkEntries.insert(it, this->EntryList[*i]);
414 it = this->FinalLinkEntries.insert(it, groupEntry);
415 it->Item.Value = "<LINK_GROUP>";
420 // Display the final set.
421 if (this->DebugMode) {
422 this->DisplayFinalEntries();
425 return this->FinalLinkEntries;
428 std::string const& cmComputeLinkDepends::GetCurrentFeature(
429 std::string const& item, std::string const& defaultFeature) const
431 auto it = this->LinkLibraryOverride.find(item);
432 return it == this->LinkLibraryOverride.end() ? defaultFeature : it->second;
435 std::pair<std::map<cmLinkItem, int>::iterator, bool>
436 cmComputeLinkDepends::AllocateLinkEntry(cmLinkItem const& item)
438 std::map<cmLinkItem, int>::value_type index_entry(
439 item, static_cast<int>(this->EntryList.size()));
440 auto lei = this->LinkEntryIndex.insert(index_entry);
442 this->EntryList.emplace_back();
443 this->InferredDependSets.emplace_back();
444 this->EntryConstraintGraph.emplace_back();
449 std::pair<int, bool> cmComputeLinkDepends::AddLinkEntry(cmLinkItem const& item,
452 // Allocate a spot for the item entry.
453 auto lei = this->AllocateLinkEntry(item);
455 // Check if the item entry has already been added.
457 // Yes. We do not need to follow the item's dependencies again.
458 return { lei.first->second, false };
461 // Initialize the item entry.
462 int index = lei.first->second;
463 LinkEntry& entry = this->EntryList[index];
464 entry.Item = BT<std::string>(item.AsStr(), item.Backtrace);
465 entry.Target = item.Target;
466 if (!entry.Target && entry.Item.Value[0] == '-' &&
467 entry.Item.Value[1] != 'l' &&
468 entry.Item.Value.substr(0, 10) != "-framework") {
469 entry.Kind = LinkEntry::Flag;
470 } else if (cmHasPrefix(entry.Item.Value, LG_BEGIN) &&
471 cmHasSuffix(entry.Item.Value, '>')) {
472 entry.Kind = LinkEntry::Group;
475 if (entry.Kind != LinkEntry::Group) {
476 // If the item has dependencies queue it to follow them.
478 // Target dependencies are always known. Follow them.
479 BFSEntry qe = { index, groupIndex, nullptr };
480 this->BFSQueue.push(qe);
482 // Look for an old-style <item>_LIB_DEPENDS variable.
483 std::string var = cmStrCat(entry.Item.Value, "_LIB_DEPENDS");
484 if (cmValue val = this->Makefile->GetDefinition(var)) {
485 // The item dependencies are known. Follow them.
486 BFSEntry qe = { index, groupIndex, val->c_str() };
487 this->BFSQueue.push(qe);
488 } else if (entry.Kind != LinkEntry::Flag) {
489 // The item dependencies are not known. We need to infer them.
490 this->InferredDependSets[index].Initialized = true;
495 return { index, true };
498 void cmComputeLinkDepends::AddLinkObject(cmLinkItem const& item)
500 // Allocate a spot for the item entry.
501 auto lei = this->AllocateLinkEntry(item);
503 // Check if the item entry has already been added.
508 // Initialize the item entry.
509 int index = lei.first->second;
510 LinkEntry& entry = this->EntryList[index];
511 entry.Item = BT<std::string>(item.AsStr(), item.Backtrace);
512 entry.Kind = LinkEntry::Object;
514 // Record explicitly linked object files separately.
515 this->ObjectEntries.emplace_back(index);
518 void cmComputeLinkDepends::FollowLinkEntry(BFSEntry qe)
520 // Get this entry representation.
521 int depender_index = qe.GroupIndex == -1 ? qe.Index : qe.GroupIndex;
522 LinkEntry const& entry = this->EntryList[qe.Index];
524 // Follow the item's dependencies.
526 // Follow the target dependencies.
527 if (cmLinkInterface const* iface =
528 entry.Target->GetLinkInterface(this->Config, this->Target)) {
530 entry.Target->GetType() == cmStateEnums::INTERFACE_LIBRARY;
531 // This target provides its own link interface information.
532 this->AddLinkEntries(depender_index, iface->Libraries);
533 this->AddLinkObjects(iface->Objects);
534 for (auto const& language : iface->Languages) {
535 auto runtimeEntries = iface->LanguageRuntimeLibraries.find(language);
536 if (runtimeEntries != iface->LanguageRuntimeLibraries.end()) {
537 this->AddLinkEntries(depender_index, runtimeEntries->second);
545 // Handle dependent shared libraries.
546 this->FollowSharedDeps(depender_index, iface);
548 // Support for CMP0003.
549 for (cmLinkItem const& oi : iface->WrongConfigLibraries) {
550 this->CheckWrongConfigItem(oi);
554 // Follow the old-style dependency list.
555 this->AddVarLinkEntries(depender_index, qe.LibDepends);
559 void cmComputeLinkDepends::FollowSharedDeps(int depender_index,
560 cmLinkInterface const* iface,
561 bool follow_interface)
563 // Follow dependencies if we have not followed them already.
564 if (this->SharedDepFollowed.insert(depender_index).second) {
565 if (follow_interface) {
566 this->QueueSharedDependencies(depender_index, iface->Libraries);
568 this->QueueSharedDependencies(depender_index, iface->SharedDeps);
572 void cmComputeLinkDepends::QueueSharedDependencies(
573 int depender_index, std::vector<cmLinkItem> const& deps)
575 for (cmLinkItem const& li : deps) {
578 qe.DependerIndex = depender_index;
579 this->SharedDepQueue.push(qe);
583 void cmComputeLinkDepends::HandleSharedDependency(SharedDepEntry const& dep)
585 // Allocate a spot for the item entry.
586 auto lei = this->AllocateLinkEntry(dep.Item);
587 int index = lei.first->second;
589 // Check if the target does not already has an entry.
591 // Initialize the item entry.
592 LinkEntry& entry = this->EntryList[index];
593 entry.Item = BT<std::string>(dep.Item.AsStr(), dep.Item.Backtrace);
594 entry.Target = dep.Item.Target;
596 // This item was added specifically because it is a dependent
597 // shared library. It may get special treatment
598 // in cmComputeLinkInformation.
599 entry.Kind = LinkEntry::SharedDep;
602 // Get the link entry for this target.
603 LinkEntry& entry = this->EntryList[index];
605 // This shared library dependency must follow the item that listed
607 this->EntryConstraintGraph[dep.DependerIndex].emplace_back(
608 index, true, false, cmListFileBacktrace());
610 // Target items may have their own dependencies.
612 if (cmLinkInterface const* iface =
613 entry.Target->GetLinkInterface(this->Config, this->Target)) {
614 // Follow public and private dependencies transitively.
615 this->FollowSharedDeps(index, iface, true);
620 void cmComputeLinkDepends::AddVarLinkEntries(int depender_index,
623 // This is called to add the dependencies named by
624 // <item>_LIB_DEPENDS. The variable contains a semicolon-separated
625 // list. The list contains link-type;item pairs and just items.
626 std::vector<std::string> deplist = cmExpandedList(value);
628 // Look for entries meant for this configuration.
629 std::vector<cmLinkItem> actual_libs;
630 cmTargetLinkLibraryType llt = GENERAL_LibraryType;
631 bool haveLLT = false;
632 for (std::string const& d : deplist) {
634 llt = DEBUG_LibraryType;
636 } else if (d == "optimized") {
637 llt = OPTIMIZED_LibraryType;
639 } else if (d == "general") {
640 llt = GENERAL_LibraryType;
642 } else if (!d.empty()) {
643 // If no explicit link type was given prior to this entry then
644 // check if the entry has its own link type variable. This is
645 // needed for compatibility with dependency files generated by
646 // the export_library_dependencies command from CMake 2.4 and
649 std::string var = cmStrCat(d, "_LINK_TYPE");
650 if (cmValue val = this->Makefile->GetDefinition(var)) {
651 if (*val == "debug") {
652 llt = DEBUG_LibraryType;
653 } else if (*val == "optimized") {
654 llt = OPTIMIZED_LibraryType;
659 // If the library is meant for this link type then use it.
660 if (llt == GENERAL_LibraryType || llt == this->LinkType) {
661 actual_libs.emplace_back(this->ResolveLinkItem(depender_index, d));
662 } else if (this->OldLinkDirMode) {
663 cmLinkItem item = this->ResolveLinkItem(depender_index, d);
664 this->CheckWrongConfigItem(item);
667 // Reset the link type until another explicit type is given.
668 llt = GENERAL_LibraryType;
673 // Add the entries from this list.
674 this->AddLinkEntries(depender_index, actual_libs);
677 void cmComputeLinkDepends::AddDirectLinkEntries()
679 // Add direct link dependencies in this configuration.
680 cmLinkImplementation const* impl = this->Target->GetLinkImplementation(
681 this->Config, cmGeneratorTarget::LinkInterfaceFor::Link);
682 this->AddLinkEntries(-1, impl->Libraries);
683 this->AddLinkObjects(impl->Objects);
685 for (auto const& language : impl->Languages) {
686 auto runtimeEntries = impl->LanguageRuntimeLibraries.find(language);
687 if (runtimeEntries != impl->LanguageRuntimeLibraries.end()) {
688 this->AddLinkEntries(-1, runtimeEntries->second);
691 for (cmLinkItem const& wi : impl->WrongConfigLibraries) {
692 this->CheckWrongConfigItem(wi);
696 template <typename T>
697 void cmComputeLinkDepends::AddLinkEntries(int depender_index,
698 std::vector<T> const& libs)
700 // Track inferred dependency sets implied by this list.
701 std::map<int, DependSet> dependSets;
702 std::string feature = LinkEntry::DEFAULT;
704 bool inGroup = false;
705 std::pair<int, bool> groupIndex{ -1, false };
706 std::vector<int> groupItems;
708 // Loop over the libraries linked directly by the depender.
709 for (T const& l : libs) {
710 // Skip entries that will resolve to the target getting linked or
712 cmLinkItem const& item = l;
713 if (item.AsStr() == this->Target->GetName() || item.AsStr().empty()) {
717 if (cmHasPrefix(item.AsStr(), LL_BEGIN) &&
718 cmHasSuffix(item.AsStr(), '>')) {
719 feature = ExtractFeature(item.AsStr());
720 // emit a warning if an undefined feature is used as part of
721 // an imported target
722 if (depender_index >= 0) {
723 const auto& depender = this->EntryList[depender_index];
724 if (depender.Target != nullptr && depender.Target->IsImported() &&
725 !IsFeatureSupported(this->Makefile, this->LinkLanguage, feature)) {
726 this->CMakeInstance->IssueMessage(
727 MessageType::AUTHOR_ERROR,
728 cmStrCat("The 'IMPORTED' target '", depender.Target->GetName(),
729 "' uses the generator-expression '$<LINK_LIBRARY>' with "
732 "', which is undefined or unsupported.\nDid you miss to "
733 "define it by setting variables \"CMAKE_",
734 this->LinkLanguage, "_LINK_LIBRARY_USING_", feature,
735 "\" and \"CMAKE_", this->LinkLanguage,
736 "_LINK_LIBRARY_USING_", feature, "_SUPPORTED\"?"),
737 this->Target->GetBacktrace());
742 if (cmHasPrefix(item.AsStr(), LL_END) && cmHasSuffix(item.AsStr(), '>')) {
743 feature = LinkEntry::DEFAULT;
747 if (cmHasPrefix(item.AsStr(), LG_BEGIN) &&
748 cmHasSuffix(item.AsStr(), '>')) {
749 groupIndex = this->AddLinkEntry(item);
750 if (groupIndex.second) {
751 LinkEntry& entry = this->EntryList[groupIndex.first];
752 entry.Feature = ExtractGroupFeature(item.AsStr());
755 if (depender_index >= 0) {
756 this->EntryConstraintGraph[depender_index].emplace_back(
757 groupIndex.first, false, false, cmListFileBacktrace());
759 // This is a direct dependency of the target being linked.
760 this->OriginalEntries.push_back(groupIndex.first);
767 if (cmHasPrefix(item.AsStr(), LG_END) && cmHasSuffix(item.AsStr(), '>')) {
768 dependee_index = groupIndex.first;
769 if (groupIndex.second) {
770 this->GroupItems.emplace(groupIndex.first, groupItems);
773 groupIndex = std::make_pair(-1, false);
778 if (depender_index >= 0 && inGroup) {
779 const auto& depender = this->EntryList[depender_index];
780 const auto& groupFeature = this->EntryList[groupIndex.first].Feature;
781 if (depender.Target != nullptr && depender.Target->IsImported() &&
782 !IsGroupFeatureSupported(this->Makefile, this->LinkLanguage,
784 this->CMakeInstance->IssueMessage(
785 MessageType::AUTHOR_ERROR,
786 cmStrCat("The 'IMPORTED' target '", depender.Target->GetName(),
787 "' uses the generator-expression '$<LINK_GROUP>' with "
790 "', which is undefined or unsupported.\nDid you miss to "
791 "define it by setting variables \"CMAKE_",
792 this->LinkLanguage, "_LINK_GROUP_USING_", groupFeature,
793 "\" and \"CMAKE_", this->LinkLanguage, "_LINK_GROUP_USING_",
794 groupFeature, "_SUPPORTED\"?"),
795 this->Target->GetBacktrace());
799 // Add a link entry for this item.
800 auto ale = this->AddLinkEntry(item, groupIndex.first);
801 dependee_index = ale.first;
802 LinkEntry& entry = this->EntryList[dependee_index];
803 auto const& itemFeature =
804 this->GetCurrentFeature(entry.Item.Value, feature);
805 if (inGroup && ale.second && entry.Target != nullptr &&
806 (entry.Target->GetType() == cmStateEnums::TargetType::OBJECT_LIBRARY ||
807 entry.Target->GetType() ==
808 cmStateEnums::TargetType::INTERFACE_LIBRARY)) {
809 const auto& groupFeature = this->EntryList[groupIndex.first].Feature;
810 this->CMakeInstance->IssueMessage(
811 MessageType::AUTHOR_WARNING,
813 "The feature '", groupFeature,
814 "', specified as part of a generator-expression "
816 LG_BEGIN, groupFeature, ">', will not be applied to the ",
817 (entry.Target->GetType() == cmStateEnums::TargetType::OBJECT_LIBRARY
820 " library '", entry.Item.Value, "'."),
821 this->Target->GetBacktrace());
823 if (itemFeature != LinkEntry::DEFAULT) {
825 // current item not yet defined
826 if (entry.Target != nullptr &&
827 (entry.Target->GetType() ==
828 cmStateEnums::TargetType::OBJECT_LIBRARY ||
829 entry.Target->GetType() ==
830 cmStateEnums::TargetType::INTERFACE_LIBRARY)) {
831 this->CMakeInstance->IssueMessage(
832 MessageType::AUTHOR_WARNING,
833 cmStrCat("The feature '", feature,
834 "', specified as part of a generator-expression "
836 LL_BEGIN, feature, ">', will not be applied to the ",
837 (entry.Target->GetType() ==
838 cmStateEnums::TargetType::OBJECT_LIBRARY
841 " library '", entry.Item.Value, "'."),
842 this->Target->GetBacktrace());
844 entry.Feature = itemFeature;
849 bool supportedItem = entry.Target == nullptr ||
850 (entry.Target->GetType() != cmStateEnums::TargetType::OBJECT_LIBRARY &&
851 entry.Target->GetType() != cmStateEnums::TargetType::INTERFACE_LIBRARY);
855 const auto& currentFeature = this->EntryList[groupIndex.first].Feature;
856 for (const auto& g : this->GroupItems) {
857 const auto& groupFeature = this->EntryList[g.first].Feature;
858 if (groupFeature == currentFeature) {
861 if (std::find(g.second.cbegin(), g.second.cend(), dependee_index) !=
863 this->CMakeInstance->IssueMessage(
864 MessageType::FATAL_ERROR,
865 cmStrCat("Impossible to link target '", this->Target->GetName(),
866 "' because the link item '", entry.Item.Value,
867 "', specified with the group feature '", currentFeature,
868 '\'', ", has already occurred with the feature '",
869 groupFeature, '\'', ", which is not allowed."),
870 this->Target->GetBacktrace());
875 if (entry.Feature != itemFeature) {
876 // incompatibles features occurred
877 this->CMakeInstance->IssueMessage(
878 MessageType::FATAL_ERROR,
879 cmStrCat("Impossible to link target '", this->Target->GetName(),
880 "' because the link item '", entry.Item.Value,
882 (itemFeature == LinkEntry::DEFAULT
883 ? "without any feature or 'DEFAULT' feature"
884 : cmStrCat("with the feature '", itemFeature, '\'')),
885 ", has already occurred ",
886 (entry.Feature == LinkEntry::DEFAULT
887 ? "without any feature or 'DEFAULT' feature"
888 : cmStrCat("with the feature '", entry.Feature, '\'')),
889 ", which is not allowed."),
890 this->Target->GetBacktrace());
895 // store item index for dependencies handling
896 groupItems.push_back(dependee_index);
898 std::vector<int> indexes;
899 bool entryHandled = false;
900 // search any occurrence of the library in already defined groups
901 for (const auto& group : this->GroupItems) {
902 for (auto index : group.second) {
903 if (entry.Item.Value == this->EntryList[index].Item.Value) {
904 indexes.push_back(group.first);
911 indexes.push_back(dependee_index);
914 for (auto index : indexes) {
915 // The dependee must come after the depender.
916 if (depender_index >= 0) {
917 this->EntryConstraintGraph[depender_index].emplace_back(
918 index, false, false, cmListFileBacktrace());
920 // This is a direct dependency of the target being linked.
921 this->OriginalEntries.push_back(index);
924 // Update the inferred dependencies for earlier items.
925 for (auto& dependSet : dependSets) {
926 // Add this item to the inferred dependencies of other items.
927 // Target items are never inferred dependees because unknown
928 // items are outside libraries that should not be depending on
930 if (!this->EntryList[index].Target &&
931 this->EntryList[index].Kind != LinkEntry::Flag &&
932 this->EntryList[index].Kind != LinkEntry::Group &&
933 dependee_index != dependSet.first) {
934 dependSet.second.insert(index);
938 // If this item needs to have dependencies inferred, do so.
939 if (this->InferredDependSets[index].Initialized) {
940 // Make sure an entry exists to hold the set for the item.
947 // Store the inferred dependency sets discovered for this list.
948 for (auto const& dependSet : dependSets) {
949 this->InferredDependSets[dependSet.first].push_back(dependSet.second);
953 void cmComputeLinkDepends::AddLinkObjects(std::vector<cmLinkItem> const& objs)
955 for (cmLinkItem const& obj : objs) {
956 this->AddLinkObject(obj);
960 cmLinkItem cmComputeLinkDepends::ResolveLinkItem(int depender_index,
961 const std::string& name)
963 // Look for a target in the scope of the depender.
964 cmGeneratorTarget const* from = this->Target;
965 if (depender_index >= 0) {
966 if (cmGeneratorTarget const* depender =
967 this->EntryList[depender_index].Target) {
971 return from->ResolveLinkItem(BT<std::string>(name));
974 void cmComputeLinkDepends::InferDependencies()
976 // The inferred dependency sets for each item list the possible
977 // dependencies. The intersection of the sets for one item form its
978 // inferred dependencies.
979 for (unsigned int depender_index = 0;
980 depender_index < this->InferredDependSets.size(); ++depender_index) {
981 // Skip items for which dependencies do not need to be inferred or
982 // for which the inferred dependency sets are empty.
983 DependSetList& sets = this->InferredDependSets[depender_index];
984 if (!sets.Initialized || sets.empty()) {
988 // Intersect the sets for this item.
989 DependSet common = sets.front();
990 for (DependSet const& i : cmMakeRange(sets).advance(1)) {
991 DependSet intersection;
992 std::set_intersection(common.begin(), common.end(), i.begin(), i.end(),
993 std::inserter(intersection, intersection.begin()));
994 common = intersection;
997 // Add the inferred dependencies to the graph.
998 cmGraphEdgeList& edges = this->EntryConstraintGraph[depender_index];
999 edges.reserve(edges.size() + common.size());
1000 for (auto const& c : common) {
1001 edges.emplace_back(c, true, false, cmListFileBacktrace());
1006 void cmComputeLinkDepends::UpdateGroupDependencies()
1008 if (this->GroupItems.empty()) {
1012 // Walks through all entries of the constraint graph to replace dependencies
1013 // over raw items by the group it belongs to, if any.
1014 for (auto& edgeList : this->EntryConstraintGraph) {
1015 for (auto& edge : edgeList) {
1017 if (this->EntryList[index].Kind == LinkEntry::Group ||
1018 this->EntryList[index].Kind == LinkEntry::Flag ||
1019 this->EntryList[index].Kind == LinkEntry::Object) {
1022 // search the item in the defined groups
1023 for (const auto& groupItems : this->GroupItems) {
1024 auto pos = std::find(groupItems.second.cbegin(),
1025 groupItems.second.cend(), index);
1026 if (pos != groupItems.second.cend()) {
1027 // replace lib dependency by the group it belongs to
1028 edge = cmGraphEdge{ groupItems.first, false, false,
1029 cmListFileBacktrace() };
1036 void cmComputeLinkDepends::CleanConstraintGraph()
1038 for (cmGraphEdgeList& edgeList : this->EntryConstraintGraph) {
1039 // Sort the outgoing edges for each graph node so that the
1040 // original order will be preserved as much as possible.
1041 std::sort(edgeList.begin(), edgeList.end());
1043 // Make the edge list unique.
1044 edgeList.erase(std::unique(edgeList.begin(), edgeList.end()),
1049 bool cmComputeLinkDepends::CheckCircularDependencies() const
1051 std::vector<NodeList> const& components = this->CCG->GetComponents();
1052 int nc = static_cast<int>(components.size());
1053 for (int c = 0; c < nc; ++c) {
1054 // Get the current component.
1055 NodeList const& nl = components[c];
1057 // Skip trivial components.
1058 if (nl.size() < 2) {
1062 // no group must be evolved
1063 bool cycleDetected = false;
1065 if (this->EntryList[ni].Kind == LinkEntry::Group) {
1066 cycleDetected = true;
1070 if (!cycleDetected) {
1074 // Construct the error message.
1075 auto formatItem = [](LinkEntry const& entry) -> std::string {
1076 if (entry.Kind == LinkEntry::Group) {
1078 entry.Item.Value.substr(entry.Item.Value.find(':', 12) + 1);
1080 std::replace(items.begin(), items.end(), '|', ',');
1081 return cmStrCat("group \"", ExtractGroupFeature(entry.Item.Value),
1082 ":{", items, "}\"");
1084 return cmStrCat('"', entry.Item.Value, '"');
1087 std::ostringstream e;
1088 e << "The inter-target dependency graph, for the target \""
1089 << this->Target->GetName()
1090 << "\", contains the following strongly connected component "
1092 std::vector<int> const& cmap = this->CCG->GetComponentMap();
1094 // Get the depender.
1095 LinkEntry const& depender = this->EntryList[i];
1097 // Describe the depender.
1098 e << " " << formatItem(depender) << "\n";
1100 // List its dependencies that are inside the component.
1101 EdgeList const& el = this->EntryConstraintGraph[i];
1102 for (cmGraphEdge const& ni : el) {
1105 LinkEntry const& dependee = this->EntryList[j];
1106 e << " depends on " << formatItem(dependee) << "\n";
1110 this->CMakeInstance->IssueMessage(MessageType::FATAL_ERROR, e.str(),
1111 this->Target->GetBacktrace());
1119 void cmComputeLinkDepends::DisplayConstraintGraph()
1121 // Display the graph nodes and their edges.
1122 std::ostringstream e;
1123 for (unsigned int i = 0; i < this->EntryConstraintGraph.size(); ++i) {
1124 EdgeList const& nl = this->EntryConstraintGraph[i];
1125 e << "item " << i << " is [" << this->EntryList[i].Item << "]\n";
1126 e << cmWrap(" item ", nl, " must follow it", "\n") << "\n";
1128 fprintf(stderr, "%s\n", e.str().c_str());
1131 void cmComputeLinkDepends::OrderLinkEntries()
1133 // The component graph is guaranteed to be acyclic. Start a DFS
1134 // from every entry to compute a topological order for the
1136 Graph const& cgraph = this->CCG->GetComponentGraph();
1137 int n = static_cast<int>(cgraph.size());
1138 this->ComponentVisited.resize(cgraph.size(), 0);
1139 this->ComponentOrder.resize(cgraph.size(), n);
1140 this->ComponentOrderId = n;
1141 // Run in reverse order so the topological order will preserve the
1142 // original order where there are no constraints.
1143 for (int c = n - 1; c >= 0; --c) {
1144 this->VisitComponent(c);
1147 // Display the component graph.
1148 if (this->DebugMode) {
1149 this->DisplayComponents();
1152 // Start with the original link line.
1153 for (int originalEntry : this->OriginalEntries) {
1154 this->VisitEntry(originalEntry);
1157 // Now explore anything left pending. Since the component graph is
1158 // guaranteed to be acyclic we know this will terminate.
1159 while (!this->PendingComponents.empty()) {
1160 // Visit one entry from the first pending component. The visit
1161 // logic will update the pending components accordingly. Since
1162 // the pending components are kept in topological order this will
1164 int e = *this->PendingComponents.begin()->second.Entries.begin();
1165 this->VisitEntry(e);
1169 void cmComputeLinkDepends::DisplayComponents()
1171 fprintf(stderr, "The strongly connected components are:\n");
1172 std::vector<NodeList> const& components = this->CCG->GetComponents();
1173 for (unsigned int c = 0; c < components.size(); ++c) {
1174 fprintf(stderr, "Component (%u):\n", c);
1175 NodeList const& nl = components[c];
1177 fprintf(stderr, " item %d [%s]\n", i,
1178 this->EntryList[i].Item.Value.c_str());
1180 EdgeList const& ol = this->CCG->GetComponentGraphEdges(c);
1181 for (cmGraphEdge const& oi : ol) {
1183 fprintf(stderr, " followed by Component (%d)\n", i);
1185 fprintf(stderr, " topo order index %d\n", this->ComponentOrder[c]);
1187 fprintf(stderr, "\n");
1190 void cmComputeLinkDepends::VisitComponent(unsigned int c)
1192 // Check if the node has already been visited.
1193 if (this->ComponentVisited[c]) {
1197 // We are now visiting this component so mark it.
1198 this->ComponentVisited[c] = 1;
1200 // Visit the neighbors of the component first.
1201 // Run in reverse order so the topological order will preserve the
1202 // original order where there are no constraints.
1203 EdgeList const& nl = this->CCG->GetComponentGraphEdges(c);
1204 for (cmGraphEdge const& edge : cmReverseRange(nl)) {
1205 this->VisitComponent(edge);
1208 // Assign an ordering id to this component.
1209 this->ComponentOrder[c] = --this->ComponentOrderId;
1212 void cmComputeLinkDepends::VisitEntry(int index)
1214 // Include this entry on the link line.
1215 this->FinalLinkOrder.push_back(index);
1217 // This entry has now been seen. Update its component.
1218 bool completed = false;
1219 int component = this->CCG->GetComponentMap()[index];
1220 auto mi = this->PendingComponents.find(this->ComponentOrder[component]);
1221 if (mi != this->PendingComponents.end()) {
1222 // The entry is in an already pending component.
1223 PendingComponent& pc = mi->second;
1225 // Remove the entry from those pending in its component.
1226 pc.Entries.erase(index);
1227 if (pc.Entries.empty()) {
1228 // The complete component has been seen since it was last needed.
1231 if (pc.Count == 0) {
1232 // The component has been completed.
1233 this->PendingComponents.erase(mi);
1236 // The whole component needs to be seen again.
1237 NodeList const& nl = this->CCG->GetComponent(component);
1238 assert(nl.size() > 1);
1239 pc.Entries.insert(nl.begin(), nl.end());
1243 // The entry is not in an already pending component.
1244 NodeList const& nl = this->CCG->GetComponent(component);
1245 if (nl.size() > 1) {
1246 // This is a non-trivial component. It is now pending.
1247 PendingComponent& pc = this->MakePendingComponent(component);
1249 // The starting entry has already been seen.
1250 pc.Entries.erase(index);
1252 // This is a trivial component, so it is already complete.
1257 // If the entry completed a component, the component's dependencies
1260 EdgeList const& ol = this->CCG->GetComponentGraphEdges(component);
1261 for (cmGraphEdge const& oi : ol) {
1262 // This entire component is now pending no matter whether it has
1263 // been partially seen already.
1264 this->MakePendingComponent(oi);
1269 cmComputeLinkDepends::PendingComponent&
1270 cmComputeLinkDepends::MakePendingComponent(unsigned int component)
1272 // Create an entry (in topological order) for the component.
1273 PendingComponent& pc =
1274 this->PendingComponents[this->ComponentOrder[component]];
1276 NodeList const& nl = this->CCG->GetComponent(component);
1278 if (nl.size() == 1) {
1279 // Trivial components need be seen only once.
1282 // This is a non-trivial strongly connected component of the
1283 // original graph. It consists of two or more libraries
1284 // (archives) that mutually require objects from one another. In
1285 // the worst case we may have to repeat the list of libraries as
1286 // many times as there are object files in the biggest archive.
1287 // For now we just list them twice.
1289 // The list of items in the component has been sorted by the order
1290 // of discovery in the original BFS of dependencies. This has the
1291 // advantage that the item directly linked by a target requiring
1292 // this component will come first which minimizes the number of
1294 pc.Count = this->ComputeComponentCount(nl);
1297 // Store the entries to be seen.
1298 pc.Entries.insert(nl.begin(), nl.end());
1303 int cmComputeLinkDepends::ComputeComponentCount(NodeList const& nl)
1305 unsigned int count = 2;
1307 if (cmGeneratorTarget const* target = this->EntryList[ni].Target) {
1308 if (cmLinkInterface const* iface =
1309 target->GetLinkInterface(this->Config, this->Target)) {
1310 if (iface->Multiplicity > count) {
1311 count = iface->Multiplicity;
1319 void cmComputeLinkDepends::DisplayFinalEntries()
1321 fprintf(stderr, "target [%s] links to:\n", this->Target->GetName().c_str());
1324 for (LinkEntry const& lei : this->FinalLinkEntries) {
1325 if (lei.Kind == LinkEntry::Group) {
1326 fprintf(stderr, " %s group",
1327 lei.Item.Value == "<LINK_GROUP>" ? "start" : "end");
1328 count = lei.Item.Value == "<LINK_GROUP>" ? 4 : 2;
1329 } else if (lei.Target) {
1330 fprintf(stderr, "%*starget [%s]", count, space,
1331 lei.Target->GetName().c_str());
1333 fprintf(stderr, "%*sitem [%s]", count, space, lei.Item.Value.c_str());
1335 if (lei.Feature != LinkEntry::DEFAULT) {
1336 fprintf(stderr, ", feature [%s]", lei.Feature.c_str());
1338 fprintf(stderr, "\n");
1340 fprintf(stderr, "\n");
1343 void cmComputeLinkDepends::CheckWrongConfigItem(cmLinkItem const& item)
1345 if (!this->OldLinkDirMode) {
1349 // For CMake 2.4 bug-compatibility we need to consider the output
1350 // directories of targets linked in another configuration as link
1352 if (item.Target && !item.Target->IsImported()) {
1353 this->OldWrongConfigItems.insert(item.Target);