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 "cmComputeTargetDepends.h"
14 #include "cmComputeComponentGraph.h"
15 #include "cmGlobalGenerator.h"
16 #include "cmLocalGenerator.h"
17 #include "cmMakefile.h"
18 #include "cmSystemTools.h"
28 This class is meant to analyze inter-target dependencies globally
29 during the generation step. The goal is to produce a set of direct
30 dependencies for each target such that no cycles are left and the
33 For most target types cyclic dependencies are not allowed. However
34 STATIC libraries may depend on each other in a cyclic fashion. In
35 general the directed dependency graph forms a directed-acyclic-graph
36 of strongly connected components. All strongly connected components
37 should consist of only STATIC_LIBRARY targets.
39 In order to safely break dependency cycles we must preserve all other
40 dependencies passing through the corresponding strongly connected component.
41 The approach taken by this class is as follows:
43 - Collect all targets and form the original dependency graph
44 - Run Tarjan's algorithm to extract the strongly connected components
45 (error if any member of a non-trivial component is not STATIC)
46 - The original dependencies imply a DAG on the components.
47 Use the implied DAG to construct a final safe set of dependencies.
49 The final dependency set is constructed as follows:
51 - For each connected component targets are placed in an arbitrary
52 order. Each target depends on the target following it in the order.
53 The first target is designated the head and the last target the tail.
54 (most components will be just 1 target anyway)
56 - Original dependencies between targets in different components are
57 converted to connect the depender's component tail to the
58 dependee's component head.
60 In most cases this will reproduce the original dependencies. However
61 when there are cycles of static libraries they will be broken in a
64 For example, consider targets A0, A1, A2, B0, B1, B2, and C with these
67 A0 -> A1 -> A2 -> A0 , B0 -> B1 -> B2 -> B0 -> A0 , C -> B0
69 Components may be identified as
71 Component 0: A0, A1, A2
72 Component 1: B0, B1, B2
75 Intra-component dependencies are:
77 0: A0 -> A1 -> A2 , head=A0, tail=A2
78 1: B0 -> B1 -> B2 , head=B0, tail=B2
81 The inter-component dependencies are converted as:
83 B0 -> A0 is component 1->0 and becomes B2 -> A0
84 C -> B0 is component 2->1 and becomes C -> B0
86 This leads to the final target dependencies:
88 C -> B0 -> B1 -> B2 -> A0 -> A1 -> A2
90 These produce a safe build order since C depends directly or
91 transitively on all the static libraries it links.
95 //----------------------------------------------------------------------------
96 cmComputeTargetDepends::cmComputeTargetDepends(cmGlobalGenerator* gg)
98 this->GlobalGenerator = gg;
99 cmake* cm = this->GlobalGenerator->GetCMakeInstance();
100 this->DebugMode = cm->GetPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
101 this->NoCycles = cm->GetPropertyAsBool("GLOBAL_DEPENDS_NO_CYCLES");
104 //----------------------------------------------------------------------------
105 cmComputeTargetDepends::~cmComputeTargetDepends()
109 //----------------------------------------------------------------------------
110 bool cmComputeTargetDepends::Compute()
112 // Build the original graph.
113 this->CollectTargets();
114 this->CollectDepends();
117 this->DisplayGraph(this->InitialGraph, "initial");
120 // Identify components.
121 cmComputeComponentGraph ccg(this->InitialGraph);
124 this->DisplayComponents(ccg);
126 if(!this->CheckComponents(ccg))
131 // Compute the final dependency graph.
132 if(!this->ComputeFinalDepends(ccg))
138 this->DisplayGraph(this->FinalGraph, "final");
144 //----------------------------------------------------------------------------
146 cmComputeTargetDepends::GetTargetDirectDepends(cmTarget* t,
147 cmTargetDependSet& deps)
149 // Lookup the index for this target. All targets should be known by
151 std::map<cmTarget*, int>::const_iterator tii = this->TargetIndex.find(t);
152 assert(tii != this->TargetIndex.end());
155 // Get its final dependencies.
156 EdgeList const& nl = this->FinalGraph[i];
157 for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
159 cmTarget* dep = this->Targets[*ni];
160 cmTargetDependSet::iterator di = deps.insert(dep).first;
161 di->SetType(ni->IsStrong());
165 //----------------------------------------------------------------------------
166 void cmComputeTargetDepends::CollectTargets()
168 // Collect all targets from all generators.
169 std::vector<cmLocalGenerator*> const& lgens =
170 this->GlobalGenerator->GetLocalGenerators();
171 for(unsigned int i = 0; i < lgens.size(); ++i)
173 cmTargets& targets = lgens[i]->GetMakefile()->GetTargets();
174 for(cmTargets::iterator ti = targets.begin(); ti != targets.end(); ++ti)
176 cmTarget* target = &ti->second;
177 int index = static_cast<int>(this->Targets.size());
178 this->TargetIndex[target] = index;
179 this->Targets.push_back(target);
184 //----------------------------------------------------------------------------
185 void cmComputeTargetDepends::CollectDepends()
187 // Allocate the dependency graph adjacency lists.
188 this->InitialGraph.resize(this->Targets.size());
190 // Compute each dependency list.
191 for(unsigned int i=0; i < this->Targets.size(); ++i)
193 this->CollectTargetDepends(i);
197 //----------------------------------------------------------------------------
198 void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
201 cmTarget* depender = this->Targets[depender_index];
203 // Loop over all targets linked directly in all configs.
204 // We need to make targets depend on the union of all config-specific
205 // dependencies in all targets, because the generated build-systems can't
206 // deal with config-specific dependencies.
208 std::set<cmStdString> emitted;
210 std::vector<std::string> tlibs;
211 depender->GetDirectLinkLibraries(0, tlibs, depender);
212 // A target should not depend on itself.
213 emitted.insert(depender->GetName());
214 for(std::vector<std::string>::const_iterator lib = tlibs.begin();
215 lib != tlibs.end(); ++lib)
217 // Don't emit the same library twice for this target.
218 if(emitted.insert(*lib).second)
220 this->AddTargetDepend(depender_index, lib->c_str(), true);
221 this->AddInterfaceDepends(depender_index, lib->c_str(),
226 std::vector<std::string> configs;
227 depender->GetMakefile()->GetConfigurations(configs);
228 for (std::vector<std::string>::const_iterator it = configs.begin();
229 it != configs.end(); ++it)
231 std::vector<std::string> tlibs;
232 depender->GetDirectLinkLibraries(it->c_str(), tlibs, depender);
233 // A target should not depend on itself.
234 emitted.insert(depender->GetName());
235 for(std::vector<std::string>::const_iterator lib = tlibs.begin();
236 lib != tlibs.end(); ++lib)
238 // Don't emit the same library twice for this target.
239 if(emitted.insert(*lib).second)
241 this->AddTargetDepend(depender_index, lib->c_str(), true);
242 this->AddInterfaceDepends(depender_index, lib->c_str(),
249 // Loop over all utility dependencies.
251 std::set<cmStdString> const& tutils = depender->GetUtilities();
252 std::set<cmStdString> emitted;
253 // A target should not depend on itself.
254 emitted.insert(depender->GetName());
255 for(std::set<cmStdString>::const_iterator util = tutils.begin();
256 util != tutils.end(); ++util)
258 // Don't emit the same utility twice for this target.
259 if(emitted.insert(*util).second)
261 this->AddTargetDepend(depender_index, util->c_str(), false);
267 //----------------------------------------------------------------------------
268 void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
271 std::set<cmStdString> &emitted)
273 cmTarget* depender = this->Targets[depender_index];
274 if(cmTarget::LinkInterface const* iface =
275 dependee->GetLinkInterface(config, depender))
277 for(std::vector<std::string>::const_iterator
278 lib = iface->Libraries.begin();
279 lib != iface->Libraries.end(); ++lib)
281 // Don't emit the same library twice for this target.
282 if(emitted.insert(*lib).second)
284 this->AddTargetDepend(depender_index, lib->c_str(), true);
285 this->AddInterfaceDepends(depender_index, lib->c_str(),
292 //----------------------------------------------------------------------------
293 void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
294 const char* dependee_name,
296 std::set<cmStdString> &emitted)
298 cmTarget* depender = this->Targets[depender_index];
300 depender->GetMakefile()->FindTargetToUse(dependee_name);
301 // Skip targets that will not really be linked. This is probably a
302 // name conflict between an external library and an executable
303 // within the project.
304 if(linking && dependee &&
305 dependee->GetType() == cmTarget::EXECUTABLE &&
306 !dependee->IsExecutableWithExports())
313 this->AddInterfaceDepends(depender_index, dependee, 0, emitted);
314 std::vector<std::string> configs;
315 depender->GetMakefile()->GetConfigurations(configs);
316 for (std::vector<std::string>::const_iterator it = configs.begin();
317 it != configs.end(); ++it)
319 // A target should not depend on itself.
320 emitted.insert(depender->GetName());
321 this->AddInterfaceDepends(depender_index, dependee,
322 it->c_str(), emitted);
327 //----------------------------------------------------------------------------
328 void cmComputeTargetDepends::AddTargetDepend(int depender_index,
329 const char* dependee_name,
333 cmTarget* depender = this->Targets[depender_index];
335 // Check the target's makefile first.
337 depender->GetMakefile()->FindTargetToUse(dependee_name);
339 // Skip targets that will not really be linked. This is probably a
340 // name conflict between an external library and an executable
341 // within the project.
342 if(linking && dependee &&
343 dependee->GetType() == cmTarget::EXECUTABLE &&
344 !dependee->IsExecutableWithExports())
351 this->AddTargetDepend(depender_index, dependee, linking);
355 //----------------------------------------------------------------------------
356 void cmComputeTargetDepends::AddTargetDepend(int depender_index,
360 if(dependee->IsImported())
362 // Skip imported targets but follow their utility dependencies.
363 std::set<cmStdString> const& utils = dependee->GetUtilities();
364 for(std::set<cmStdString>::const_iterator i = utils.begin();
365 i != utils.end(); ++i)
367 if(cmTarget* transitive_dependee =
368 dependee->GetMakefile()->FindTargetToUse(i->c_str()))
370 this->AddTargetDepend(depender_index, transitive_dependee, false);
376 // Lookup the index for this target. All targets should be known by
378 std::map<cmTarget*, int>::const_iterator tii =
379 this->TargetIndex.find(dependee);
380 assert(tii != this->TargetIndex.end());
381 int dependee_index = tii->second;
383 // Add this entry to the dependency graph.
384 this->InitialGraph[depender_index].push_back(
385 cmGraphEdge(dependee_index, !linking));
389 //----------------------------------------------------------------------------
391 cmComputeTargetDepends::DisplayGraph(Graph const& graph, const char* name)
393 fprintf(stderr, "The %s target dependency graph is:\n", name);
394 int n = static_cast<int>(graph.size());
395 for(int depender_index = 0; depender_index < n; ++depender_index)
397 EdgeList const& nl = graph[depender_index];
398 cmTarget* depender = this->Targets[depender_index];
399 fprintf(stderr, "target %d is [%s]\n",
400 depender_index, depender->GetName());
401 for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
403 int dependee_index = *ni;
404 cmTarget* dependee = this->Targets[dependee_index];
405 fprintf(stderr, " depends on target %d [%s] (%s)\n", dependee_index,
406 dependee->GetName(), ni->IsStrong()? "strong" : "weak");
409 fprintf(stderr, "\n");
412 //----------------------------------------------------------------------------
414 cmComputeTargetDepends
415 ::DisplayComponents(cmComputeComponentGraph const& ccg)
417 fprintf(stderr, "The strongly connected components are:\n");
418 std::vector<NodeList> const& components = ccg.GetComponents();
419 int n = static_cast<int>(components.size());
420 for(int c = 0; c < n; ++c)
422 NodeList const& nl = components[c];
423 fprintf(stderr, "Component (%d):\n", c);
424 for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
427 fprintf(stderr, " contains target %d [%s]\n",
428 i, this->Targets[i]->GetName());
431 fprintf(stderr, "\n");
434 //----------------------------------------------------------------------------
436 cmComputeTargetDepends
437 ::CheckComponents(cmComputeComponentGraph const& ccg)
439 // All non-trivial components should consist only of static
441 std::vector<NodeList> const& components = ccg.GetComponents();
442 int nc = static_cast<int>(components.size());
443 for(int c=0; c < nc; ++c)
445 // Get the current component.
446 NodeList const& nl = components[c];
448 // Skip trivial components.
454 // Immediately complain if no cycles are allowed at all.
457 this->ComplainAboutBadComponent(ccg, c);
461 // Make sure the component is all STATIC_LIBRARY targets.
462 for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
464 if(this->Targets[*ni]->GetType() != cmTarget::STATIC_LIBRARY)
466 this->ComplainAboutBadComponent(ccg, c);
474 //----------------------------------------------------------------------------
476 cmComputeTargetDepends
477 ::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c,
480 // Construct the error message.
482 e << "The inter-target dependency graph contains the following "
483 << "strongly connected component (cycle):\n";
484 std::vector<NodeList> const& components = ccg.GetComponents();
485 std::vector<int> const& cmap = ccg.GetComponentMap();
486 NodeList const& cl = components[c];
487 for(NodeList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci)
491 cmTarget* depender = this->Targets[i];
493 // Describe the depender.
494 e << " \"" << depender->GetName() << "\" of type "
495 << cmTarget::GetTargetTypeName(depender->GetType()) << "\n";
497 // List its dependencies that are inside the component.
498 EdgeList const& nl = this->InitialGraph[i];
499 for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
504 cmTarget* dependee = this->Targets[j];
505 e << " depends on \"" << dependee->GetName() << "\""
506 << " (" << (ni->IsStrong()? "strong" : "weak") << ")\n";
512 // Custom command executable dependencies cannot occur within a
513 // component of static libraries. The cycle must appear in calls
514 // to add_dependencies.
515 e << "The component contains at least one cycle consisting of strong "
516 << "dependencies (created by add_dependencies) that cannot be broken.";
518 else if(this->NoCycles)
520 e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
521 << "cyclic dependencies are not allowed even among static libraries.";
525 e << "At least one of these targets is not a STATIC_LIBRARY. "
526 << "Cyclic dependencies are allowed only among static libraries.";
528 cmSystemTools::Error(e.str().c_str());
531 //----------------------------------------------------------------------------
533 cmComputeTargetDepends
534 ::IntraComponent(std::vector<int> const& cmap, int c, int i, int* head,
535 std::set<int>& emitted, std::set<int>& visited)
537 if(!visited.insert(i).second)
539 // Cycle in utility depends!
542 if(emitted.insert(i).second)
544 // Honor strong intra-component edges in the final order.
545 EdgeList const& el = this->InitialGraph[i];
546 for(EdgeList::const_iterator ei = el.begin(); ei != el.end(); ++ei)
549 if(cmap[j] == c && ei->IsStrong())
551 this->FinalGraph[i].push_back(cmGraphEdge(j, true));
552 if(!this->IntraComponent(cmap, c, j, head, emitted, visited))
559 // Prepend to a linear linked-list of intra-component edges.
562 this->FinalGraph[i].push_back(cmGraphEdge(*head, false));
566 this->ComponentTail[c] = i;
573 //----------------------------------------------------------------------------
575 cmComputeTargetDepends
576 ::ComputeFinalDepends(cmComputeComponentGraph const& ccg)
578 // Get the component graph information.
579 std::vector<NodeList> const& components = ccg.GetComponents();
580 Graph const& cgraph = ccg.GetComponentGraph();
582 // Allocate the final graph.
583 this->FinalGraph.resize(0);
584 this->FinalGraph.resize(this->InitialGraph.size());
586 // Choose intra-component edges to linearize dependencies.
587 std::vector<int> const& cmap = ccg.GetComponentMap();
588 this->ComponentHead.resize(components.size());
589 this->ComponentTail.resize(components.size());
590 int nc = static_cast<int>(components.size());
591 for(int c=0; c < nc; ++c)
594 std::set<int> emitted;
595 NodeList const& nl = components[c];
596 for(NodeList::const_reverse_iterator ni = nl.rbegin();
597 ni != nl.rend(); ++ni)
599 std::set<int> visited;
600 if(!this->IntraComponent(cmap, c, *ni, &head, emitted, visited))
602 // Cycle in add_dependencies within component!
603 this->ComplainAboutBadComponent(ccg, c, true);
607 this->ComponentHead[c] = head;
610 // Convert inter-component edges to connect component tails to heads.
611 int n = static_cast<int>(cgraph.size());
612 for(int depender_component=0; depender_component < n; ++depender_component)
614 int depender_component_tail = this->ComponentTail[depender_component];
615 EdgeList const& nl = cgraph[depender_component];
616 for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
618 int dependee_component = *ni;
619 int dependee_component_head = this->ComponentHead[dependee_component];
620 this->FinalGraph[depender_component_tail]
621 .push_back(cmGraphEdge(dependee_component_head, ni->IsStrong()));