1 /*============================================================================
2 CMake - Cross Platform Makefile Generator
3 Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
5 Distributed under the OSI-approved BSD License (the "License");
6 see accompanying file Copyright.txt for details.
8 This software is distributed WITHOUT ANY WARRANTY; without even the
9 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10 See the License for more information.
11 ============================================================================*/
12 #include "cmComputeLinkDepends.h"
14 #include "cmComputeComponentGraph.h"
15 #include "cmGlobalGenerator.h"
16 #include "cmLocalGenerator.h"
17 #include "cmMakefile.h"
21 #include <cmsys/stl/algorithm>
27 This file computes an ordered list of link items to use when linking a
28 single target in one configuration. Each link item is identified by
29 the string naming it. A graph of dependencies is created in which
30 each node corresponds to one item and directed edges lead from nodes to
31 those which must *follow* them on the link line. For example, the
36 will lead to the link line order
40 The set of items placed in the graph is formed with a breadth-first
41 search of the link dependencies starting from the main target.
43 There are two types of items: those with known direct dependencies and
44 those without known dependencies. We will call the two types "known
45 items" and "unknown items", respectively. Known items are those whose
46 names correspond to targets (built or imported) and those for which an
47 old-style <item>_LIB_DEPENDS variable is defined. All other items are
48 unknown and we must infer dependencies for them. For items that look
49 like flags (beginning with '-') we trivially infer no dependencies,
50 and do not include them in the dependencies of other items.
52 Known items have dependency lists ordered based on how the user
53 specified them. We can use this order to infer potential dependencies
54 of unknown items. For example, if link items A and B are unknown and
55 items X and Y are known, then we might have the following dependency
61 The explicitly known dependencies form graph edges
63 X -> Y , X -> A , X -> B , Y -> A , Y -> B
65 We can also infer the edge
69 because *every* time A appears B is seen on its right. We do not know
70 whether A really needs symbols from B to link, but it *might* so we
71 must preserve their order. This is the case also for the following
77 Here, A is followed by the set {B,Y} in one list, and {B} in the other
78 list. The intersection of these sets is {B}, so we can infer that A
79 depends on at most B. Meanwhile B is followed by the set {Y} in one
80 list and {} in the other. The intersection is {} so we can infer that
81 B has no dependencies.
83 Let's make a more complex example by adding unknown item C and
84 considering these dependency lists:
89 The explicit edges are
91 X -> Y , X -> A , X -> B , X -> C , Y -> A , Y -> B , Y -> C
93 For the unknown items, we infer dependencies by looking at the
96 A: intersect( {B,Y,C} , {C,B} ) = {B,C} ; infer edges A -> B , A -> C
97 B: intersect( {Y,C} , {} ) = {} ; infer no edges
98 C: intersect( {} , {B} ) = {} ; infer no edges
100 Note that targets are never inferred as dependees because outside
101 libraries should not depend on them.
103 ------------------------------------------------------------------------------
105 The initial exploration of dependencies using a BFS associates an
106 integer index with each link item. When the graph is built outgoing
107 edges are sorted by this index.
109 After the initial exploration of the link interface tree, any
110 transitive (dependent) shared libraries that were encountered and not
111 included in the interface are processed in their own BFS. This BFS
112 follows only the dependent library lists and not the link interfaces.
113 They are added to the link items with a mark indicating that the are
114 transitive dependencies. Then cmComputeLinkInformation deals with
115 them on a per-platform basis.
117 The complete graph formed from all known and inferred dependencies may
118 not be acyclic, so an acyclic version must be created.
119 The original graph is converted to a directed acyclic graph in which
120 each node corresponds to a strongly connected component of the
121 original graph. For example, the dependency graph
123 X -> A -> B -> C -> A -> Y
125 contains strongly connected components {X}, {A,B,C}, and {Y}. The
126 implied directed acyclic graph (DAG) is
128 {X} -> {A,B,C} -> {Y}
130 We then compute a topological order for the DAG nodes to serve as a
131 reference for satisfying dependencies efficiently. We perform the DFS
132 in reverse order and assign topological order indices counting down so
133 that the result is as close to the original BFS order as possible
134 without violating dependencies.
136 ------------------------------------------------------------------------------
138 The final link entry order is constructed as follows. We first walk
139 through and emit the *original* link line as specified by the user.
140 As each item is emitted, a set of pending nodes in the component DAG
141 is maintained. When a pending component has been completely seen, it
142 is removed from the pending set and its dependencies (following edges
143 of the DAG) are added. A trivial component (those with one item) is
144 complete as soon as its item is seen. A non-trivial component (one
145 with more than one item; assumed to be static libraries) is complete
146 when *all* its entries have been seen *twice* (all entries seen once,
147 then all entries seen again, not just each entry twice). A pending
148 component tracks which items have been seen and a count of how many
149 times the component needs to be seen (once for trivial components,
150 twice for non-trivial). If at any time another component finishes and
151 re-adds an already pending component, the pending component is reset
152 so that it needs to be seen in its entirety again. This ensures that
153 all dependencies of a component are satisfied no matter where it
156 After the original link line has been completed, we append to it the
157 remaining pending components and their dependencies. This is done by
158 repeatedly emitting the first item from the first pending component
159 and following the same update rules as when traversing the original
160 link line. Since the pending components are kept in topological order
161 they are emitted with minimal repeats (we do not want to emit a
162 component just to have it added again when another component is
163 completed later). This process continues until no pending components
164 remain. We know it will terminate because the component graph is
165 guaranteed to be acyclic.
167 The final list of items produced by this procedure consists of the
168 original user link line followed by minimal additional items needed to
169 satisfy dependencies.
173 //----------------------------------------------------------------------------
175 ::cmComputeLinkDepends(cmTarget* target, const char* config)
177 // Store context information.
178 this->Target = target;
179 this->Makefile = this->Target->GetMakefile();
180 this->LocalGenerator = this->Makefile->GetLocalGenerator();
181 this->GlobalGenerator = this->LocalGenerator->GetGlobalGenerator();
182 this->CMakeInstance = this->GlobalGenerator->GetCMakeInstance();
184 // The configuration being linked.
185 this->Config = (config && *config)? config : 0;
186 this->LinkType = this->Target->ComputeLinkType(this->Config);
188 // Enable debug mode if requested.
189 this->DebugMode = this->Makefile->IsOn("CMAKE_LINK_DEPENDS_DEBUG_MODE");
191 // Assume no compatibility until set.
192 this->OldLinkDirMode = false;
194 // No computation has been done.
198 //----------------------------------------------------------------------------
199 cmComputeLinkDepends::~cmComputeLinkDepends()
201 for(std::vector<DependSetList*>::iterator
202 i = this->InferredDependSets.begin();
203 i != this->InferredDependSets.end(); ++i)
210 //----------------------------------------------------------------------------
211 void cmComputeLinkDepends::SetOldLinkDirMode(bool b)
213 this->OldLinkDirMode = b;
216 //----------------------------------------------------------------------------
217 std::vector<cmComputeLinkDepends::LinkEntry> const&
218 cmComputeLinkDepends::Compute()
220 // Follow the link dependencies of the target to be linked.
221 this->AddDirectLinkEntries();
223 // Complete the breadth-first search of dependencies.
224 while(!this->BFSQueue.empty())
226 // Get the next entry.
227 BFSEntry qe = this->BFSQueue.front();
228 this->BFSQueue.pop();
230 // Follow the entry's dependencies.
231 this->FollowLinkEntry(qe);
234 // Complete the search of shared library dependencies.
235 while(!this->SharedDepQueue.empty())
237 // Handle the next entry.
238 this->HandleSharedDependency(this->SharedDepQueue.front());
239 this->SharedDepQueue.pop();
242 // Infer dependencies of targets for which they were not known.
243 this->InferDependencies();
245 // Cleanup the constraint graph.
246 this->CleanConstraintGraph();
248 // Display the constraint graph.
252 "---------------------------------------"
253 "---------------------------------------\n");
254 fprintf(stderr, "Link dependency analysis for target %s, config %s\n",
255 this->Target->GetName(), this->Config?this->Config:"noconfig");
256 this->DisplayConstraintGraph();
259 // Compute the final ordering.
260 this->OrderLinkEntires();
262 // Compute the final set of link entries.
263 for(std::vector<int>::const_iterator li = this->FinalLinkOrder.begin();
264 li != this->FinalLinkOrder.end(); ++li)
266 this->FinalLinkEntries.push_back(this->EntryList[*li]);
269 // Display the final set.
272 this->DisplayFinalEntries();
275 return this->FinalLinkEntries;
278 //----------------------------------------------------------------------------
279 std::map<cmStdString, int>::iterator
280 cmComputeLinkDepends::AllocateLinkEntry(std::string const& item)
282 std::map<cmStdString, int>::value_type
283 index_entry(item, static_cast<int>(this->EntryList.size()));
284 std::map<cmStdString, int>::iterator
285 lei = this->LinkEntryIndex.insert(index_entry).first;
286 this->EntryList.push_back(LinkEntry());
287 this->InferredDependSets.push_back(0);
288 this->EntryConstraintGraph.push_back(EdgeList());
292 //----------------------------------------------------------------------------
293 int cmComputeLinkDepends::AddLinkEntry(int depender_index,
294 std::string const& item)
296 // Check if the item entry has already been added.
297 std::map<cmStdString, int>::iterator lei = this->LinkEntryIndex.find(item);
298 if(lei != this->LinkEntryIndex.end())
300 // Yes. We do not need to follow the item's dependencies again.
304 // Allocate a spot for the item entry.
305 lei = this->AllocateLinkEntry(item);
307 // Initialize the item entry.
308 int index = lei->second;
309 LinkEntry& entry = this->EntryList[index];
311 entry.Target = this->FindTargetToLink(depender_index, entry.Item.c_str());
312 entry.IsFlag = (!entry.Target && item[0] == '-' && item[1] != 'l' &&
313 item.substr(0, 10) != "-framework");
315 // If the item has dependencies queue it to follow them.
318 // Target dependencies are always known. Follow them.
319 BFSEntry qe = {index, 0};
320 this->BFSQueue.push(qe);
324 // Look for an old-style <item>_LIB_DEPENDS variable.
325 std::string var = entry.Item;
326 var += "_LIB_DEPENDS";
327 if(const char* val = this->Makefile->GetDefinition(var.c_str()))
329 // The item dependencies are known. Follow them.
330 BFSEntry qe = {index, val};
331 this->BFSQueue.push(qe);
333 else if(!entry.IsFlag)
335 // The item dependencies are not known. We need to infer them.
336 this->InferredDependSets[index] = new DependSetList;
343 //----------------------------------------------------------------------------
344 void cmComputeLinkDepends::FollowLinkEntry(BFSEntry const& qe)
346 // Get this entry representation.
347 int depender_index = qe.Index;
348 LinkEntry const& entry = this->EntryList[depender_index];
350 // Follow the item's dependencies.
353 // Follow the target dependencies.
354 if(cmTarget::LinkInterface const* iface =
355 entry.Target->GetLinkInterface(this->Config))
357 // This target provides its own link interface information.
358 this->AddLinkEntries(depender_index, iface->Libraries);
360 // Handle dependent shared libraries.
361 this->FollowSharedDeps(depender_index, iface);
363 // Support for CMP0003.
364 for(std::vector<std::string>::const_iterator
365 oi = iface->WrongConfigLibraries.begin();
366 oi != iface->WrongConfigLibraries.end(); ++oi)
368 this->CheckWrongConfigItem(depender_index, *oi);
374 // Follow the old-style dependency list.
375 this->AddVarLinkEntries(depender_index, qe.LibDepends);
379 //----------------------------------------------------------------------------
382 ::FollowSharedDeps(int depender_index, cmTarget::LinkInterface const* iface,
383 bool follow_interface)
385 // Follow dependencies if we have not followed them already.
386 if(this->SharedDepFollowed.insert(depender_index).second)
390 this->QueueSharedDependencies(depender_index, iface->Libraries);
392 this->QueueSharedDependencies(depender_index, iface->SharedDeps);
396 //----------------------------------------------------------------------------
399 ::QueueSharedDependencies(int depender_index,
400 std::vector<std::string> const& deps)
402 for(std::vector<std::string>::const_iterator li = deps.begin();
403 li != deps.end(); ++li)
407 qe.DependerIndex = depender_index;
408 this->SharedDepQueue.push(qe);
412 //----------------------------------------------------------------------------
413 void cmComputeLinkDepends::HandleSharedDependency(SharedDepEntry const& dep)
415 // Check if the target already has an entry.
416 std::map<cmStdString, int>::iterator lei =
417 this->LinkEntryIndex.find(dep.Item);
418 if(lei == this->LinkEntryIndex.end())
420 // Allocate a spot for the item entry.
421 lei = this->AllocateLinkEntry(dep.Item);
423 // Initialize the item entry.
424 LinkEntry& entry = this->EntryList[lei->second];
425 entry.Item = dep.Item;
426 entry.Target = this->FindTargetToLink(dep.DependerIndex,
429 // This item was added specifically because it is a dependent
430 // shared library. It may get special treatment
431 // in cmComputeLinkInformation.
432 entry.IsSharedDep = true;
435 // Get the link entry for this target.
436 int index = lei->second;
437 LinkEntry& entry = this->EntryList[index];
439 // This shared library dependency must follow the item that listed
441 this->EntryConstraintGraph[dep.DependerIndex].push_back(index);
443 // Target items may have their own dependencies.
446 if(cmTarget::LinkInterface const* iface =
447 entry.Target->GetLinkInterface(this->Config))
449 // Follow public and private dependencies transitively.
450 this->FollowSharedDeps(index, iface, true);
455 //----------------------------------------------------------------------------
456 void cmComputeLinkDepends::AddVarLinkEntries(int depender_index,
459 // This is called to add the dependencies named by
460 // <item>_LIB_DEPENDS. The variable contains a semicolon-separated
461 // list. The list contains link-type;item pairs and just items.
462 std::vector<std::string> deplist;
463 cmSystemTools::ExpandListArgument(value, deplist);
465 // Look for entries meant for this configuration.
466 std::vector<std::string> actual_libs;
467 cmTarget::LinkLibraryType llt = cmTarget::GENERAL;
468 bool haveLLT = false;
469 for(std::vector<std::string>::const_iterator di = deplist.begin();
470 di != deplist.end(); ++di)
474 llt = cmTarget::DEBUG;
477 else if(*di == "optimized")
479 llt = cmTarget::OPTIMIZED;
482 else if(*di == "general")
484 llt = cmTarget::GENERAL;
487 else if(!di->empty())
489 // If no explicit link type was given prior to this entry then
490 // check if the entry has its own link type variable. This is
491 // needed for compatibility with dependency files generated by
492 // the export_library_dependencies command from CMake 2.4 and
496 std::string var = *di;
498 if(const char* val = this->Makefile->GetDefinition(var.c_str()))
500 if(strcmp(val, "debug") == 0)
502 llt = cmTarget::DEBUG;
504 else if(strcmp(val, "optimized") == 0)
506 llt = cmTarget::OPTIMIZED;
511 // If the library is meant for this link type then use it.
512 if(llt == cmTarget::GENERAL || llt == this->LinkType)
514 actual_libs.push_back(*di);
516 else if(this->OldLinkDirMode)
518 this->CheckWrongConfigItem(depender_index, *di);
521 // Reset the link type until another explicit type is given.
522 llt = cmTarget::GENERAL;
527 // Add the entries from this list.
528 this->AddLinkEntries(depender_index, actual_libs);
531 //----------------------------------------------------------------------------
532 void cmComputeLinkDepends::AddDirectLinkEntries()
534 // Add direct link dependencies in this configuration.
535 cmTarget::LinkImplementation const* impl =
536 this->Target->GetLinkImplementation(this->Config);
537 this->AddLinkEntries(-1, impl->Libraries);
538 for(std::vector<std::string>::const_iterator
539 wi = impl->WrongConfigLibraries.begin();
540 wi != impl->WrongConfigLibraries.end(); ++wi)
542 this->CheckWrongConfigItem(-1, *wi);
546 //----------------------------------------------------------------------------
548 cmComputeLinkDepends::AddLinkEntries(int depender_index,
549 std::vector<std::string> const& libs)
551 // Track inferred dependency sets implied by this list.
552 std::map<int, DependSet> dependSets;
554 // Loop over the libraries linked directly by the depender.
555 for(std::vector<std::string>::const_iterator li = libs.begin();
556 li != libs.end(); ++li)
558 // Skip entries that will resolve to the target getting linked or
560 std::string item = this->Target->CheckCMP0004(*li);
561 if(item == this->Target->GetName() || item.empty())
566 // Add a link entry for this item.
567 int dependee_index = this->AddLinkEntry(depender_index, item);
569 // The dependee must come after the depender.
570 if(depender_index >= 0)
572 this->EntryConstraintGraph[depender_index].push_back(dependee_index);
576 // This is a direct dependency of the target being linked.
577 this->OriginalEntries.push_back(dependee_index);
580 // Update the inferred dependencies for earlier items.
581 for(std::map<int, DependSet>::iterator dsi = dependSets.begin();
582 dsi != dependSets.end(); ++dsi)
584 // Add this item to the inferred dependencies of other items.
585 // Target items are never inferred dependees because unknown
586 // items are outside libraries that should not be depending on
588 if(!this->EntryList[dependee_index].Target &&
589 !this->EntryList[dependee_index].IsFlag &&
590 dependee_index != dsi->first)
592 dsi->second.insert(dependee_index);
596 // If this item needs to have dependencies inferred, do so.
597 if(this->InferredDependSets[dependee_index])
599 // Make sure an entry exists to hold the set for the item.
600 dependSets[dependee_index];
604 // Store the inferred dependency sets discovered for this list.
605 for(std::map<int, DependSet>::iterator dsi = dependSets.begin();
606 dsi != dependSets.end(); ++dsi)
608 this->InferredDependSets[dsi->first]->push_back(dsi->second);
612 //----------------------------------------------------------------------------
613 cmTarget* cmComputeLinkDepends::FindTargetToLink(int depender_index,
616 // Look for a target in the scope of the depender.
617 cmMakefile* mf = this->Makefile;
618 if(depender_index >= 0)
620 if(cmTarget* depender = this->EntryList[depender_index].Target)
622 mf = depender->GetMakefile();
625 cmTarget* tgt = mf->FindTargetToUse(name);
627 // Skip targets that will not really be linked. This is probably a
628 // name conflict between an external library and an executable
629 // within the project.
630 if(tgt && tgt->GetType() == cmTarget::EXECUTABLE &&
631 !tgt->IsExecutableWithExports())
636 if(tgt && tgt->GetType() == cmTarget::OBJECT_LIBRARY)
639 e << "Target \"" << this->Target->GetName() << "\" links to "
640 "OBJECT library \"" << tgt->GetName() << "\" but this is not "
642 "One may link only to STATIC or SHARED libraries, or to executables "
643 "with the ENABLE_EXPORTS property set.";
644 this->CMakeInstance->IssueMessage(cmake::FATAL_ERROR, e.str(),
645 this->Target->GetBacktrace());
649 // Return the target found, if any.
653 //----------------------------------------------------------------------------
654 void cmComputeLinkDepends::InferDependencies()
656 // The inferred dependency sets for each item list the possible
657 // dependencies. The intersection of the sets for one item form its
658 // inferred dependencies.
659 for(unsigned int depender_index=0;
660 depender_index < this->InferredDependSets.size(); ++depender_index)
662 // Skip items for which dependencies do not need to be inferred or
663 // for which the inferred dependency sets are empty.
664 DependSetList* sets = this->InferredDependSets[depender_index];
665 if(!sets || sets->empty())
670 // Intersect the sets for this item.
671 DependSetList::const_iterator i = sets->begin();
672 DependSet common = *i;
673 for(++i; i != sets->end(); ++i)
675 DependSet intersection;
676 cmsys_stl::set_intersection
677 (common.begin(), common.end(), i->begin(), i->end(),
678 std::inserter(intersection, intersection.begin()));
679 common = intersection;
682 // Add the inferred dependencies to the graph.
683 for(DependSet::const_iterator j = common.begin(); j != common.end(); ++j)
685 int dependee_index = *j;
686 this->EntryConstraintGraph[depender_index].push_back(dependee_index);
691 //----------------------------------------------------------------------------
692 void cmComputeLinkDepends::CleanConstraintGraph()
694 for(Graph::iterator i = this->EntryConstraintGraph.begin();
695 i != this->EntryConstraintGraph.end(); ++i)
697 // Sort the outgoing edges for each graph node so that the
698 // original order will be preserved as much as possible.
699 cmsys_stl::sort(i->begin(), i->end());
701 // Make the edge list unique.
702 EdgeList::iterator last = cmsys_stl::unique(i->begin(), i->end());
703 i->erase(last, i->end());
707 //----------------------------------------------------------------------------
708 void cmComputeLinkDepends::DisplayConstraintGraph()
710 // Display the graph nodes and their edges.
712 for(unsigned int i=0; i < this->EntryConstraintGraph.size(); ++i)
714 EdgeList const& nl = this->EntryConstraintGraph[i];
715 e << "item " << i << " is [" << this->EntryList[i].Item << "]\n";
716 for(EdgeList::const_iterator j = nl.begin(); j != nl.end(); ++j)
718 e << " item " << *j << " must follow it\n";
721 fprintf(stderr, "%s\n", e.str().c_str());
724 //----------------------------------------------------------------------------
725 void cmComputeLinkDepends::OrderLinkEntires()
727 // Compute the DAG of strongly connected components. The algorithm
728 // used by cmComputeComponentGraph should identify the components in
729 // the same order in which the items were originally discovered in
730 // the BFS. This should preserve the original order when no
731 // constraints disallow it.
732 this->CCG = new cmComputeComponentGraph(this->EntryConstraintGraph);
734 // The component graph is guaranteed to be acyclic. Start a DFS
735 // from every entry to compute a topological order for the
737 Graph const& cgraph = this->CCG->GetComponentGraph();
738 int n = static_cast<int>(cgraph.size());
739 this->ComponentVisited.resize(cgraph.size(), 0);
740 this->ComponentOrder.resize(cgraph.size(), n);
741 this->ComponentOrderId = n;
742 // Run in reverse order so the topological order will preserve the
743 // original order where there are no constraints.
744 for(int c = n-1; c >= 0; --c)
746 this->VisitComponent(c);
749 // Display the component graph.
752 this->DisplayComponents();
755 // Start with the original link line.
756 for(std::vector<int>::const_iterator i = this->OriginalEntries.begin();
757 i != this->OriginalEntries.end(); ++i)
759 this->VisitEntry(*i);
762 // Now explore anything left pending. Since the component graph is
763 // guaranteed to be acyclic we know this will terminate.
764 while(!this->PendingComponents.empty())
766 // Visit one entry from the first pending component. The visit
767 // logic will update the pending components accordingly. Since
768 // the pending components are kept in topological order this will
770 int e = *this->PendingComponents.begin()->second.Entries.begin();
775 //----------------------------------------------------------------------------
777 cmComputeLinkDepends::DisplayComponents()
779 fprintf(stderr, "The strongly connected components are:\n");
780 std::vector<NodeList> const& components = this->CCG->GetComponents();
781 for(unsigned int c=0; c < components.size(); ++c)
783 fprintf(stderr, "Component (%u):\n", c);
784 NodeList const& nl = components[c];
785 for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
788 fprintf(stderr, " item %d [%s]\n", i,
789 this->EntryList[i].Item.c_str());
791 EdgeList const& ol = this->CCG->GetComponentGraphEdges(c);
792 for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
795 fprintf(stderr, " followed by Component (%d)\n", i);
797 fprintf(stderr, " topo order index %d\n",
798 this->ComponentOrder[c]);
800 fprintf(stderr, "\n");
803 //----------------------------------------------------------------------------
804 void cmComputeLinkDepends::VisitComponent(unsigned int c)
806 // Check if the node has already been visited.
807 if(this->ComponentVisited[c])
812 // We are now visiting this component so mark it.
813 this->ComponentVisited[c] = 1;
815 // Visit the neighbors of the component first.
816 // Run in reverse order so the topological order will preserve the
817 // original order where there are no constraints.
818 EdgeList const& nl = this->CCG->GetComponentGraphEdges(c);
819 for(EdgeList::const_reverse_iterator ni = nl.rbegin();
820 ni != nl.rend(); ++ni)
822 this->VisitComponent(*ni);
825 // Assign an ordering id to this component.
826 this->ComponentOrder[c] = --this->ComponentOrderId;
829 //----------------------------------------------------------------------------
830 void cmComputeLinkDepends::VisitEntry(int index)
832 // Include this entry on the link line.
833 this->FinalLinkOrder.push_back(index);
835 // This entry has now been seen. Update its component.
836 bool completed = false;
837 int component = this->CCG->GetComponentMap()[index];
838 std::map<int, PendingComponent>::iterator mi =
839 this->PendingComponents.find(this->ComponentOrder[component]);
840 if(mi != this->PendingComponents.end())
842 // The entry is in an already pending component.
843 PendingComponent& pc = mi->second;
845 // Remove the entry from those pending in its component.
846 pc.Entries.erase(index);
847 if(pc.Entries.empty())
849 // The complete component has been seen since it was last needed.
854 // The component has been completed.
855 this->PendingComponents.erase(mi);
860 // The whole component needs to be seen again.
861 NodeList const& nl = this->CCG->GetComponent(component);
862 assert(nl.size() > 1);
863 pc.Entries.insert(nl.begin(), nl.end());
869 // The entry is not in an already pending component.
870 NodeList const& nl = this->CCG->GetComponent(component);
873 // This is a non-trivial component. It is now pending.
874 PendingComponent& pc = this->MakePendingComponent(component);
876 // The starting entry has already been seen.
877 pc.Entries.erase(index);
881 // This is a trivial component, so it is already complete.
886 // If the entry completed a component, the component's dependencies
890 EdgeList const& ol = this->CCG->GetComponentGraphEdges(component);
891 for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
893 // This entire component is now pending no matter whether it has
894 // been partially seen already.
895 this->MakePendingComponent(*oi);
900 //----------------------------------------------------------------------------
901 cmComputeLinkDepends::PendingComponent&
902 cmComputeLinkDepends::MakePendingComponent(unsigned int component)
904 // Create an entry (in topological order) for the component.
905 PendingComponent& pc =
906 this->PendingComponents[this->ComponentOrder[component]];
908 NodeList const& nl = this->CCG->GetComponent(component);
912 // Trivial components need be seen only once.
917 // This is a non-trivial strongly connected component of the
918 // original graph. It consists of two or more libraries
919 // (archives) that mutually require objects from one another. In
920 // the worst case we may have to repeat the list of libraries as
921 // many times as there are object files in the biggest archive.
922 // For now we just list them twice.
924 // The list of items in the component has been sorted by the order
925 // of discovery in the original BFS of dependencies. This has the
926 // advantage that the item directly linked by a target requiring
927 // this component will come first which minimizes the number of
929 pc.Count = this->ComputeComponentCount(nl);
932 // Store the entries to be seen.
933 pc.Entries.insert(nl.begin(), nl.end());
938 //----------------------------------------------------------------------------
939 int cmComputeLinkDepends::ComputeComponentCount(NodeList const& nl)
942 for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
944 if(cmTarget* target = this->EntryList[*ni].Target)
946 if(cmTarget::LinkInterface const* iface =
947 target->GetLinkInterface(this->Config))
949 if(iface->Multiplicity > count)
951 count = iface->Multiplicity;
959 //----------------------------------------------------------------------------
960 void cmComputeLinkDepends::DisplayFinalEntries()
962 fprintf(stderr, "target [%s] links to:\n", this->Target->GetName());
963 for(std::vector<LinkEntry>::const_iterator lei =
964 this->FinalLinkEntries.begin();
965 lei != this->FinalLinkEntries.end(); ++lei)
969 fprintf(stderr, " target [%s]\n", lei->Target->GetName());
973 fprintf(stderr, " item [%s]\n", lei->Item.c_str());
976 fprintf(stderr, "\n");
979 //----------------------------------------------------------------------------
980 void cmComputeLinkDepends::CheckWrongConfigItem(int depender_index,
981 std::string const& item)
983 if(!this->OldLinkDirMode)
988 // For CMake 2.4 bug-compatibility we need to consider the output
989 // directories of targets linked in another configuration as link
991 if(cmTarget* tgt = this->FindTargetToLink(depender_index, item.c_str()))
993 if(!tgt->IsImported())
995 this->OldWrongConfigItems.insert(tgt);