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 "cmComputeTargetDepends.h"
4
5 #include <cassert>
6 #include <cstdio>
7 #include <memory>
8 #include <sstream>
9 #include <utility>
10
11 #include "cmComputeComponentGraph.h"
12 #include "cmGeneratorTarget.h"
13 #include "cmGlobalGenerator.h"
14 #include "cmLinkItem.h"
15 #include "cmListFileCache.h"
16 #include "cmLocalGenerator.h"
17 #include "cmMakefile.h"
18 #include "cmMessageType.h"
19 #include "cmPolicies.h"
20 #include "cmRange.h"
21 #include "cmSourceFile.h"
22 #include "cmSourceFileLocationKind.h"
23 #include "cmState.h"
24 #include "cmStateTypes.h"
25 #include "cmSystemTools.h"
26 #include "cmTarget.h"
27 #include "cmTargetDepend.h"
28 #include "cmValue.h"
29 #include "cmake.h"
30
31 /*
32
33 This class is meant to analyze inter-target dependencies globally
34 during the generation step. The goal is to produce a set of direct
35 dependencies for each target such that no cycles are left and the
36 build order is safe.
37
38 For most target types cyclic dependencies are not allowed. However
39 STATIC libraries may depend on each other in a cyclic fashion. In
40 general the directed dependency graph forms a directed-acyclic-graph
41 of strongly connected components. All strongly connected components
42 should consist of only STATIC_LIBRARY targets.
43
44 In order to safely break dependency cycles we must preserve all other
45 dependencies passing through the corresponding strongly connected component.
46 The approach taken by this class is as follows:
47
48 - Collect all targets and form the original dependency graph
49 - Run Tarjan's algorithm to extract the strongly connected components
50 (error if any member of a non-trivial component is not STATIC)
51 - The original dependencies imply a DAG on the components.
52 Use the implied DAG to construct a final safe set of dependencies.
53
54 The final dependency set is constructed as follows:
55
56 - For each connected component targets are placed in an arbitrary
57 order. Each target depends on the target following it in the order.
58 The first target is designated the head and the last target the tail.
59 (most components will be just 1 target anyway)
60
61 - Original dependencies between targets in different components are
62 converted to connect the depender's component tail to the
63 dependee's component head.
64
65 In most cases this will reproduce the original dependencies. However
66 when there are cycles of static libraries they will be broken in a
67 safe manner.
68
69 For example, consider targets A0, A1, A2, B0, B1, B2, and C with these
70 dependencies:
71
72 A0 -> A1 -> A2 -> A0 , B0 -> B1 -> B2 -> B0 -> A0 , C -> B0
73
74 Components may be identified as
75
76 Component 0: A0, A1, A2
77 Component 1: B0, B1, B2
78 Component 2: C
79
80 Intra-component dependencies are:
81
82 0: A0 -> A1 -> A2 , head=A0, tail=A2
83 1: B0 -> B1 -> B2 , head=B0, tail=B2
84 2: head=C, tail=C
85
86 The inter-component dependencies are converted as:
87
88 B0 -> A0 is component 1->0 and becomes B2 -> A0
89 C -> B0 is component 2->1 and becomes C -> B0
90
91 This leads to the final target dependencies:
92
93 C -> B0 -> B1 -> B2 -> A0 -> A1 -> A2
94
95 These produce a safe build order since C depends directly or
96 transitively on all the static libraries it links.
97
98 */
99
cmComputeTargetDepends(cmGlobalGenerator * gg)100 cmComputeTargetDepends::cmComputeTargetDepends(cmGlobalGenerator* gg)
101 {
102 this->GlobalGenerator = gg;
103 cmake* cm = this->GlobalGenerator->GetCMakeInstance();
104 this->DebugMode =
105 cm->GetState()->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
106 this->NoCycles =
107 cm->GetState()->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_NO_CYCLES");
108 }
109
110 cmComputeTargetDepends::~cmComputeTargetDepends() = default;
111
Compute()112 bool cmComputeTargetDepends::Compute()
113 {
114 // Build the original graph.
115 this->CollectTargets();
116 this->CollectDepends();
117 if (this->DebugMode) {
118 this->DisplayGraph(this->InitialGraph, "initial");
119 }
120 cmComputeComponentGraph ccg1(this->InitialGraph);
121 ccg1.Compute();
122 if (!this->CheckComponents(ccg1)) {
123 return false;
124 }
125
126 // Compute the intermediate graph.
127 this->CollectSideEffects();
128 this->ComputeIntermediateGraph();
129 if (this->DebugMode) {
130 this->DisplaySideEffects();
131 this->DisplayGraph(this->IntermediateGraph, "intermediate");
132 }
133
134 // Identify components.
135 cmComputeComponentGraph ccg2(this->IntermediateGraph);
136 ccg2.Compute();
137 if (this->DebugMode) {
138 this->DisplayComponents(ccg2, "intermediate");
139 }
140 if (!this->CheckComponents(ccg2)) {
141 return false;
142 }
143
144 // Compute the final dependency graph.
145 if (!this->ComputeFinalDepends(ccg2)) {
146 return false;
147 }
148 if (this->DebugMode) {
149 this->DisplayGraph(this->FinalGraph, "final");
150 }
151
152 return true;
153 }
154
GetTargetDirectDepends(cmGeneratorTarget const * t,cmTargetDependSet & deps)155 void cmComputeTargetDepends::GetTargetDirectDepends(cmGeneratorTarget const* t,
156 cmTargetDependSet& deps)
157 {
158 // Lookup the index for this target. All targets should be known by
159 // this point.
160 auto tii = this->TargetIndex.find(t);
161 assert(tii != this->TargetIndex.end());
162 int i = tii->second;
163
164 // Get its final dependencies.
165 EdgeList const& nl = this->FinalGraph[i];
166 for (cmGraphEdge const& ni : nl) {
167 cmGeneratorTarget const* dep = this->Targets[ni];
168 auto di = deps.insert(dep).first;
169 di->SetType(ni.IsStrong());
170 di->SetCross(ni.IsCross());
171 di->SetBacktrace(ni.GetBacktrace());
172 }
173 }
174
CollectTargets()175 void cmComputeTargetDepends::CollectTargets()
176 {
177 // Collect all targets from all generators.
178 auto const& lgens = this->GlobalGenerator->GetLocalGenerators();
179 for (const auto& lgen : lgens) {
180 for (const auto& ti : lgen->GetGeneratorTargets()) {
181 int index = static_cast<int>(this->Targets.size());
182 this->TargetIndex[ti.get()] = index;
183 this->Targets.push_back(ti.get());
184 }
185 }
186 }
187
CollectDepends()188 void cmComputeTargetDepends::CollectDepends()
189 {
190 // Allocate the dependency graph adjacency lists.
191 this->InitialGraph.resize(this->Targets.size());
192
193 // Compute each dependency list.
194 for (unsigned int i = 0; i < this->Targets.size(); ++i) {
195 this->CollectTargetDepends(i);
196 }
197 }
198
CollectTargetDepends(int depender_index)199 void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
200 {
201 // Get the depender.
202 cmGeneratorTarget const* depender = this->Targets[depender_index];
203 if (!depender->IsInBuildSystem()) {
204 return;
205 }
206
207 // Loop over all targets linked directly in all configs.
208 // We need to make targets depend on the union of all config-specific
209 // dependencies in all targets, because the generated build-systems can't
210 // deal with config-specific dependencies.
211 {
212 std::set<cmLinkItem> emitted;
213
214 std::vector<std::string> const& configs =
215 depender->Makefile->GetGeneratorConfigs(cmMakefile::IncludeEmptyConfig);
216 for (std::string const& it : configs) {
217 // A target should not depend on itself.
218 emitted.insert(cmLinkItem(depender, false, cmListFileBacktrace()));
219 emitted.insert(cmLinkItem(depender, true, cmListFileBacktrace()));
220
221 if (cmLinkImplementation const* impl =
222 depender->GetLinkImplementation(it)) {
223 for (cmLinkImplItem const& lib : impl->Libraries) {
224 // Don't emit the same library twice for this target.
225 if (emitted.insert(lib).second) {
226 this->AddTargetDepend(depender_index, lib, true, false);
227 this->AddInterfaceDepends(depender_index, lib, it, emitted);
228 }
229 }
230 for (cmLinkItem const& obj : impl->Objects) {
231 if (cmSourceFile const* o = depender->Makefile->GetSource(
232 obj.AsStr(), cmSourceFileLocationKind::Known)) {
233 this->AddObjectDepends(depender_index, o, emitted);
234 }
235 }
236 }
237
238 // Add dependencies on object libraries not otherwise handled above.
239 std::vector<cmSourceFile const*> objectFiles;
240 depender->GetExternalObjects(objectFiles, it);
241 for (cmSourceFile const* o : objectFiles) {
242 this->AddObjectDepends(depender_index, o, emitted);
243 }
244 }
245 }
246
247 // Loop over all utility dependencies.
248 {
249 std::set<cmLinkItem> const& tutils = depender->GetUtilityItems();
250 std::set<cmLinkItem> emitted;
251 // A target should not depend on itself.
252 emitted.insert(cmLinkItem(depender, false, cmListFileBacktrace()));
253 emitted.insert(cmLinkItem(depender, true, cmListFileBacktrace()));
254 for (cmLinkItem const& litem : tutils) {
255 // Don't emit the same utility twice for this target.
256 if (emitted.insert(litem).second) {
257 this->AddTargetDepend(depender_index, litem, false, litem.Cross);
258 }
259 }
260 }
261 }
262
AddInterfaceDepends(int depender_index,const cmGeneratorTarget * dependee,cmListFileBacktrace const & dependee_backtrace,const std::string & config,std::set<cmLinkItem> & emitted)263 void cmComputeTargetDepends::AddInterfaceDepends(
264 int depender_index, const cmGeneratorTarget* dependee,
265 cmListFileBacktrace const& dependee_backtrace, const std::string& config,
266 std::set<cmLinkItem>& emitted)
267 {
268 cmGeneratorTarget const* depender = this->Targets[depender_index];
269 if (cmLinkInterface const* iface =
270 dependee->GetLinkInterface(config, depender)) {
271 for (cmLinkItem const& lib : iface->Libraries) {
272 // Don't emit the same library twice for this target.
273 if (emitted.insert(lib).second) {
274 // Inject the backtrace of the original link dependency whose
275 // link interface we are adding. This indicates the line of
276 // code in the project that caused this dependency to be added.
277 cmLinkItem libBT = lib;
278 libBT.Backtrace = dependee_backtrace;
279 this->AddTargetDepend(depender_index, libBT, true, false);
280 this->AddInterfaceDepends(depender_index, libBT, config, emitted);
281 }
282 }
283 for (cmLinkItem const& obj : iface->Objects) {
284 if (cmSourceFile const* o = depender->Makefile->GetSource(
285 obj.AsStr(), cmSourceFileLocationKind::Known)) {
286 this->AddObjectDepends(depender_index, o, emitted);
287 }
288 }
289 }
290 }
291
AddInterfaceDepends(int depender_index,cmLinkItem const & dependee_name,const std::string & config,std::set<cmLinkItem> & emitted)292 void cmComputeTargetDepends::AddInterfaceDepends(
293 int depender_index, cmLinkItem const& dependee_name,
294 const std::string& config, std::set<cmLinkItem>& emitted)
295 {
296 cmGeneratorTarget const* depender = this->Targets[depender_index];
297 cmGeneratorTarget const* dependee = dependee_name.Target;
298 // Skip targets that will not really be linked. This is probably a
299 // name conflict between an external library and an executable
300 // within the project.
301 if (dependee && dependee->GetType() == cmStateEnums::EXECUTABLE &&
302 !dependee->IsExecutableWithExports()) {
303 dependee = nullptr;
304 }
305
306 if (dependee) {
307 // A target should not depend on itself.
308 emitted.insert(cmLinkItem(depender, false, cmListFileBacktrace()));
309 emitted.insert(cmLinkItem(depender, true, cmListFileBacktrace()));
310 this->AddInterfaceDepends(depender_index, dependee,
311 dependee_name.Backtrace, config, emitted);
312 }
313 }
314
AddObjectDepends(int depender_index,cmSourceFile const * o,std::set<cmLinkItem> & emitted)315 void cmComputeTargetDepends::AddObjectDepends(int depender_index,
316 cmSourceFile const* o,
317 std::set<cmLinkItem>& emitted)
318 {
319 std::string const& objLib = o->GetObjectLibrary();
320 if (objLib.empty()) {
321 return;
322 }
323 cmGeneratorTarget const* depender = this->Targets[depender_index];
324 cmLinkItem const& objItem =
325 depender->ResolveLinkItem(BT<std::string>(objLib));
326 if (emitted.insert(objItem).second) {
327 if (depender->GetType() != cmStateEnums::EXECUTABLE &&
328 depender->GetType() != cmStateEnums::STATIC_LIBRARY &&
329 depender->GetType() != cmStateEnums::SHARED_LIBRARY &&
330 depender->GetType() != cmStateEnums::MODULE_LIBRARY &&
331 depender->GetType() != cmStateEnums::OBJECT_LIBRARY) {
332 this->GlobalGenerator->GetCMakeInstance()->IssueMessage(
333 MessageType::FATAL_ERROR,
334 "Only executables and libraries may reference target objects.",
335 depender->GetBacktrace());
336 return;
337 }
338 const_cast<cmGeneratorTarget*>(depender)->Target->AddUtility(objLib,
339 false);
340 }
341 }
342
AddTargetDepend(int depender_index,cmLinkItem const & dependee_name,bool linking,bool cross)343 void cmComputeTargetDepends::AddTargetDepend(int depender_index,
344 cmLinkItem const& dependee_name,
345 bool linking, bool cross)
346 {
347 // Get the depender.
348 cmGeneratorTarget const* depender = this->Targets[depender_index];
349
350 // Check the target's makefile first.
351 cmGeneratorTarget const* dependee = dependee_name.Target;
352
353 if (!dependee && !linking &&
354 (depender->GetType() != cmStateEnums::GLOBAL_TARGET)) {
355 MessageType messageType = MessageType::AUTHOR_WARNING;
356 bool issueMessage = false;
357 std::ostringstream e;
358 switch (depender->GetPolicyStatusCMP0046()) {
359 case cmPolicies::WARN:
360 e << cmPolicies::GetPolicyWarning(cmPolicies::CMP0046) << "\n";
361 issueMessage = true;
362 CM_FALLTHROUGH;
363 case cmPolicies::OLD:
364 break;
365 case cmPolicies::NEW:
366 case cmPolicies::REQUIRED_IF_USED:
367 case cmPolicies::REQUIRED_ALWAYS:
368 issueMessage = true;
369 messageType = MessageType::FATAL_ERROR;
370 break;
371 }
372 if (issueMessage) {
373 cmake* cm = this->GlobalGenerator->GetCMakeInstance();
374
375 e << "The dependency target \"" << dependee_name << "\" of target \""
376 << depender->GetName() << "\" does not exist.";
377
378 cm->IssueMessage(messageType, e.str(), dependee_name.Backtrace);
379 }
380 }
381
382 // Skip targets that will not really be linked. This is probably a
383 // name conflict between an external library and an executable
384 // within the project.
385 if (linking && dependee && dependee->GetType() == cmStateEnums::EXECUTABLE &&
386 !dependee->IsExecutableWithExports()) {
387 dependee = nullptr;
388 }
389
390 if (dependee) {
391 this->AddTargetDepend(depender_index, dependee, dependee_name.Backtrace,
392 linking, cross);
393 }
394 }
395
AddTargetDepend(int depender_index,cmGeneratorTarget const * dependee,cmListFileBacktrace const & dependee_backtrace,bool linking,bool cross)396 void cmComputeTargetDepends::AddTargetDepend(
397 int depender_index, cmGeneratorTarget const* dependee,
398 cmListFileBacktrace const& dependee_backtrace, bool linking, bool cross)
399 {
400 if (!dependee->IsInBuildSystem()) {
401 // Skip targets that are not in the buildsystem but follow their
402 // utility dependencies.
403 std::set<cmLinkItem> const& utils = dependee->GetUtilityItems();
404 for (cmLinkItem const& i : utils) {
405 if (cmGeneratorTarget const* transitive_dependee = i.Target) {
406 this->AddTargetDepend(depender_index, transitive_dependee, i.Backtrace,
407 false, i.Cross);
408 }
409 }
410 } else {
411 // Lookup the index for this target. All targets should be known by
412 // this point.
413 auto tii = this->TargetIndex.find(dependee);
414 assert(tii != this->TargetIndex.end());
415 int dependee_index = tii->second;
416
417 // Add this entry to the dependency graph.
418 this->InitialGraph[depender_index].emplace_back(dependee_index, !linking,
419 cross, dependee_backtrace);
420 }
421 }
422
CollectSideEffects()423 void cmComputeTargetDepends::CollectSideEffects()
424 {
425 this->SideEffects.resize(0);
426 this->SideEffects.resize(this->InitialGraph.size());
427
428 int n = static_cast<int>(this->InitialGraph.size());
429 std::set<int> visited;
430 for (int i = 0; i < n; ++i) {
431 this->CollectSideEffectsForTarget(visited, i);
432 }
433 }
434
CollectSideEffectsForTarget(std::set<int> & visited,int depender_index)435 void cmComputeTargetDepends::CollectSideEffectsForTarget(
436 std::set<int>& visited, int depender_index)
437 {
438 if (!visited.count(depender_index)) {
439 auto& se = this->SideEffects[depender_index];
440 visited.insert(depender_index);
441 this->Targets[depender_index]->AppendCustomCommandSideEffects(
442 se.CustomCommandSideEffects);
443 this->Targets[depender_index]->AppendLanguageSideEffects(
444 se.LanguageSideEffects);
445
446 for (auto const& edge : this->InitialGraph[depender_index]) {
447 this->CollectSideEffectsForTarget(visited, edge);
448 auto const& dse = this->SideEffects[edge];
449 se.CustomCommandSideEffects.insert(dse.CustomCommandSideEffects.cbegin(),
450 dse.CustomCommandSideEffects.cend());
451 for (auto const& it : dse.LanguageSideEffects) {
452 se.LanguageSideEffects[it.first].insert(it.second.cbegin(),
453 it.second.cend());
454 }
455 }
456 }
457 }
458
ComputeIntermediateGraph()459 void cmComputeTargetDepends::ComputeIntermediateGraph()
460 {
461 this->IntermediateGraph.resize(0);
462 this->IntermediateGraph.resize(this->InitialGraph.size());
463
464 int n = static_cast<int>(this->InitialGraph.size());
465 for (int i = 0; i < n; ++i) {
466 auto const& initialEdges = this->InitialGraph[i];
467 auto& intermediateEdges = this->IntermediateGraph[i];
468 cmGeneratorTarget const* gt = this->Targets[i];
469 if (gt->GetType() != cmStateEnums::STATIC_LIBRARY &&
470 gt->GetType() != cmStateEnums::OBJECT_LIBRARY) {
471 intermediateEdges = initialEdges;
472 } else {
473 if (cmValue optimizeDependencies =
474 gt->GetProperty("OPTIMIZE_DEPENDENCIES")) {
475 if (cmIsOn(optimizeDependencies)) {
476 this->OptimizeLinkDependencies(gt, intermediateEdges, initialEdges);
477 } else {
478 intermediateEdges = initialEdges;
479 }
480 } else {
481 intermediateEdges = initialEdges;
482 }
483 }
484 }
485 }
486
OptimizeLinkDependencies(cmGeneratorTarget const * gt,cmGraphEdgeList & outputEdges,cmGraphEdgeList const & inputEdges)487 void cmComputeTargetDepends::OptimizeLinkDependencies(
488 cmGeneratorTarget const* gt, cmGraphEdgeList& outputEdges,
489 cmGraphEdgeList const& inputEdges)
490 {
491 std::set<int> emitted;
492 for (auto const& edge : inputEdges) {
493 if (edge.IsStrong()) {
494 // Preserve strong edges
495 outputEdges.push_back(edge);
496 } else {
497 auto const& dse = this->SideEffects[edge];
498
499 // Add edges that have custom command side effects
500 for (cmGeneratorTarget const* dep : dse.CustomCommandSideEffects) {
501 auto index = this->TargetIndex[dep];
502 if (!emitted.count(index)) {
503 emitted.insert(index);
504 outputEdges.push_back(
505 cmGraphEdge(index, false, edge.IsCross(), edge.GetBacktrace()));
506 }
507 }
508
509 // Add edges that have language side effects for languages we
510 // care about
511 for (auto const& lang : gt->GetAllConfigCompileLanguages()) {
512 auto it = dse.LanguageSideEffects.find(lang);
513 if (it != dse.LanguageSideEffects.end()) {
514 for (cmGeneratorTarget const* dep : it->second) {
515 auto index = this->TargetIndex[dep];
516 if (!emitted.count(index)) {
517 emitted.insert(index);
518 outputEdges.push_back(cmGraphEdge(index, false, edge.IsCross(),
519 edge.GetBacktrace()));
520 }
521 }
522 }
523 }
524 }
525 }
526 }
527
DisplayGraph(Graph const & graph,const std::string & name)528 void cmComputeTargetDepends::DisplayGraph(Graph const& graph,
529 const std::string& name)
530 {
531 fprintf(stderr, "The %s target dependency graph is:\n", name.c_str());
532 int n = static_cast<int>(graph.size());
533 for (int depender_index = 0; depender_index < n; ++depender_index) {
534 EdgeList const& nl = graph[depender_index];
535 cmGeneratorTarget const* depender = this->Targets[depender_index];
536 fprintf(stderr, "target %d is [%s]\n", depender_index,
537 depender->GetName().c_str());
538 for (cmGraphEdge const& ni : nl) {
539 int dependee_index = ni;
540 cmGeneratorTarget const* dependee = this->Targets[dependee_index];
541 fprintf(stderr, " depends on target %d [%s] (%s)\n", dependee_index,
542 dependee->GetName().c_str(), ni.IsStrong() ? "strong" : "weak");
543 }
544 }
545 fprintf(stderr, "\n");
546 }
547
DisplaySideEffects()548 void cmComputeTargetDepends::DisplaySideEffects()
549 {
550 fprintf(stderr, "The side effects are:\n");
551 int n = static_cast<int>(this->SideEffects.size());
552 for (int depender_index = 0; depender_index < n; ++depender_index) {
553 cmGeneratorTarget const* depender = this->Targets[depender_index];
554 fprintf(stderr, "target %d is [%s]\n", depender_index,
555 depender->GetName().c_str());
556 if (!this->SideEffects[depender_index].CustomCommandSideEffects.empty()) {
557 fprintf(stderr, " custom commands\n");
558 for (auto const* gt :
559 this->SideEffects[depender_index].CustomCommandSideEffects) {
560 fprintf(stderr, " from target %d [%s]\n", this->TargetIndex[gt],
561 gt->GetName().c_str());
562 }
563 }
564 for (auto const& it :
565 this->SideEffects[depender_index].LanguageSideEffects) {
566 fprintf(stderr, " language %s\n", it.first.c_str());
567 for (auto const* gt : it.second) {
568 fprintf(stderr, " from target %d [%s]\n", this->TargetIndex[gt],
569 gt->GetName().c_str());
570 }
571 }
572 }
573 fprintf(stderr, "\n");
574 }
575
DisplayComponents(cmComputeComponentGraph const & ccg,const std::string & name)576 void cmComputeTargetDepends::DisplayComponents(
577 cmComputeComponentGraph const& ccg, const std::string& name)
578 {
579 fprintf(stderr, "The strongly connected components for the %s graph are:\n",
580 name.c_str());
581 std::vector<NodeList> const& components = ccg.GetComponents();
582 int n = static_cast<int>(components.size());
583 for (int c = 0; c < n; ++c) {
584 NodeList const& nl = components[c];
585 fprintf(stderr, "Component (%d):\n", c);
586 for (int i : nl) {
587 fprintf(stderr, " contains target %d [%s]\n", i,
588 this->Targets[i]->GetName().c_str());
589 }
590 }
591 fprintf(stderr, "\n");
592 }
593
CheckComponents(cmComputeComponentGraph const & ccg)594 bool cmComputeTargetDepends::CheckComponents(
595 cmComputeComponentGraph const& ccg)
596 {
597 // All non-trivial components should consist only of static
598 // libraries.
599 std::vector<NodeList> const& components = ccg.GetComponents();
600 int nc = static_cast<int>(components.size());
601 for (int c = 0; c < nc; ++c) {
602 // Get the current component.
603 NodeList const& nl = components[c];
604
605 // Skip trivial components.
606 if (nl.size() < 2) {
607 continue;
608 }
609
610 // Immediately complain if no cycles are allowed at all.
611 if (this->NoCycles) {
612 this->ComplainAboutBadComponent(ccg, c);
613 return false;
614 }
615
616 // Make sure the component is all STATIC_LIBRARY targets.
617 for (int ni : nl) {
618 if (this->Targets[ni]->GetType() != cmStateEnums::STATIC_LIBRARY) {
619 this->ComplainAboutBadComponent(ccg, c);
620 return false;
621 }
622 }
623 }
624 return true;
625 }
626
ComplainAboutBadComponent(cmComputeComponentGraph const & ccg,int c,bool strong)627 void cmComputeTargetDepends::ComplainAboutBadComponent(
628 cmComputeComponentGraph const& ccg, int c, bool strong)
629 {
630 // Construct the error message.
631 std::ostringstream e;
632 e << "The inter-target dependency graph contains the following "
633 << "strongly connected component (cycle):\n";
634 std::vector<NodeList> const& components = ccg.GetComponents();
635 std::vector<int> const& cmap = ccg.GetComponentMap();
636 NodeList const& cl = components[c];
637 for (int i : cl) {
638 // Get the depender.
639 cmGeneratorTarget const* depender = this->Targets[i];
640
641 // Describe the depender.
642 e << " \"" << depender->GetName() << "\" of type "
643 << cmState::GetTargetTypeName(depender->GetType()) << "\n";
644
645 // List its dependencies that are inside the component.
646 EdgeList const& nl = this->InitialGraph[i];
647 for (cmGraphEdge const& ni : nl) {
648 int j = ni;
649 if (cmap[j] == c) {
650 cmGeneratorTarget const* dependee = this->Targets[j];
651 e << " depends on \"" << dependee->GetName() << "\""
652 << " (" << (ni.IsStrong() ? "strong" : "weak") << ")\n";
653 }
654 }
655 }
656 if (strong) {
657 // Custom command executable dependencies cannot occur within a
658 // component of static libraries. The cycle must appear in calls
659 // to add_dependencies.
660 e << "The component contains at least one cycle consisting of strong "
661 << "dependencies (created by add_dependencies) that cannot be broken.";
662 } else if (this->NoCycles) {
663 e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
664 << "cyclic dependencies are not allowed even among static libraries.";
665 } else {
666 e << "At least one of these targets is not a STATIC_LIBRARY. "
667 << "Cyclic dependencies are allowed only among static libraries.";
668 }
669 cmSystemTools::Error(e.str());
670 }
671
IntraComponent(std::vector<int> const & cmap,int c,int i,int * head,std::set<int> & emitted,std::set<int> & visited)672 bool cmComputeTargetDepends::IntraComponent(std::vector<int> const& cmap,
673 int c, int i, int* head,
674 std::set<int>& emitted,
675 std::set<int>& visited)
676 {
677 if (!visited.insert(i).second) {
678 // Cycle in utility depends!
679 return false;
680 }
681 if (emitted.insert(i).second) {
682 // Honor strong intra-component edges in the final order.
683 EdgeList const& el = this->InitialGraph[i];
684 for (cmGraphEdge const& edge : el) {
685 int j = edge;
686 if (cmap[j] == c && edge.IsStrong()) {
687 this->FinalGraph[i].emplace_back(j, true, edge.IsCross(),
688 edge.GetBacktrace());
689 if (!this->IntraComponent(cmap, c, j, head, emitted, visited)) {
690 return false;
691 }
692 }
693 }
694
695 // Prepend to a linear linked-list of intra-component edges.
696 if (*head >= 0) {
697 this->FinalGraph[i].emplace_back(*head, false, false,
698 cmListFileBacktrace());
699 } else {
700 this->ComponentTail[c] = i;
701 }
702 *head = i;
703 }
704 return true;
705 }
706
ComputeFinalDepends(cmComputeComponentGraph const & ccg)707 bool cmComputeTargetDepends::ComputeFinalDepends(
708 cmComputeComponentGraph const& ccg)
709 {
710 // Get the component graph information.
711 std::vector<NodeList> const& components = ccg.GetComponents();
712 Graph const& cgraph = ccg.GetComponentGraph();
713
714 // Allocate the final graph.
715 this->FinalGraph.resize(0);
716 this->FinalGraph.resize(this->InitialGraph.size());
717
718 // Choose intra-component edges to linearize dependencies.
719 std::vector<int> const& cmap = ccg.GetComponentMap();
720 this->ComponentHead.resize(components.size());
721 this->ComponentTail.resize(components.size());
722 int nc = static_cast<int>(components.size());
723 for (int c = 0; c < nc; ++c) {
724 int head = -1;
725 std::set<int> emitted;
726 NodeList const& nl = components[c];
727 for (int ni : cmReverseRange(nl)) {
728 std::set<int> visited;
729 if (!this->IntraComponent(cmap, c, ni, &head, emitted, visited)) {
730 // Cycle in add_dependencies within component!
731 this->ComplainAboutBadComponent(ccg, c, true);
732 return false;
733 }
734 }
735 this->ComponentHead[c] = head;
736 }
737
738 // Convert inter-component edges to connect component tails to heads.
739 int n = static_cast<int>(cgraph.size());
740 for (int depender_component = 0; depender_component < n;
741 ++depender_component) {
742 int depender_component_tail = this->ComponentTail[depender_component];
743 EdgeList const& nl = cgraph[depender_component];
744 for (cmGraphEdge const& ni : nl) {
745 int dependee_component = ni;
746 int dependee_component_head = this->ComponentHead[dependee_component];
747 this->FinalGraph[depender_component_tail].emplace_back(
748 dependee_component_head, ni.IsStrong(), ni.IsCross(),
749 ni.GetBacktrace());
750 }
751 }
752 return true;
753 }
754