cmComputeTargetDepends.cxx 19.3 KB
Newer Older
1
2
/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing for details.  */
3
4
#include "cmComputeTargetDepends.h"

5
#include "cmComputeComponentGraph.h"
6
#include "cmGeneratorTarget.h"
7
#include "cmGlobalGenerator.h"
8
#include "cmLinkItem.h"
9
10
#include "cmLocalGenerator.h"
#include "cmMakefile.h"
11
#include "cmPolicies.h"
12
#include "cmSourceFile.h"
13
#include "cmState.h"
14
#include "cmStateTypes.h"
15
16
#include "cmSystemTools.h"
#include "cmTarget.h"
17
#include "cmTargetDepend.h"
18
19
20
#include "cmake.h"

#include <assert.h>
21
22
23
24
25
#include <sstream>
#include <stdio.h>
#include <utility>

class cmListFileBacktrace;
26
27
28
29
30
31
32
33
34

/*

This class is meant to analyze inter-target dependencies globally
during the generation step.  The goal is to produce a set of direct
dependencies for each target such that no cycles are left and the
build order is safe.

For most target types cyclic dependencies are not allowed.  However
35
STATIC libraries may depend on each other in a cyclic fashion.  In
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
general the directed dependency graph forms a directed-acyclic-graph
of strongly connected components.  All strongly connected components
should consist of only STATIC_LIBRARY targets.

In order to safely break dependency cycles we must preserve all other
dependencies passing through the corresponding strongly connected component.
The approach taken by this class is as follows:

  - Collect all targets and form the original dependency graph
  - Run Tarjan's algorithm to extract the strongly connected components
    (error if any member of a non-trivial component is not STATIC)
  - The original dependencies imply a DAG on the components.
    Use the implied DAG to construct a final safe set of dependencies.

The final dependency set is constructed as follows:

  - For each connected component targets are placed in an arbitrary
    order.  Each target depends on the target following it in the order.
    The first target is designated the head and the last target the tail.
    (most components will be just 1 target anyway)

  - Original dependencies between targets in different components are
    converted to connect the depender's component tail to the
    dependee's component head.

In most cases this will reproduce the original dependencies.  However
when there are cycles of static libraries they will be broken in a
safe manner.

For example, consider targets A0, A1, A2, B0, B1, B2, and C with these
dependencies:

  A0 -> A1 -> A2 -> A0  ,  B0 -> B1 -> B2 -> B0 -> A0  ,  C -> B0

Components may be identified as

  Component 0: A0, A1, A2
  Component 1: B0, B1, B2
  Component 2: C

Intra-component dependencies are:

  0: A0 -> A1 -> A2   , head=A0, tail=A2
  1: B0 -> B1 -> B2   , head=B0, tail=B2
  2: head=C, tail=C

The inter-component dependencies are converted as:

  B0 -> A0  is component 1->0 and becomes  B2 -> A0
  C  -> B0  is component 2->1 and becomes  C  -> B0

This leads to the final target dependencies:

  C -> B0 -> B1 -> B2 -> A0 -> A1 -> A2

These produce a safe build order since C depends directly or
transitively on all the static libraries it links.

*/

cmComputeTargetDepends::cmComputeTargetDepends(cmGlobalGenerator* gg)
{
  this->GlobalGenerator = gg;
  cmake* cm = this->GlobalGenerator->GetCMakeInstance();
100
101
102
103
  this->DebugMode =
    cm->GetState()->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
  this->NoCycles =
    cm->GetState()->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_NO_CYCLES");
104
105
106
107
108
109
110
111
112
113
114
}

cmComputeTargetDepends::~cmComputeTargetDepends()
{
}

bool cmComputeTargetDepends::Compute()
{
  // Build the original graph.
  this->CollectTargets();
  this->CollectDepends();
115
  if (this->DebugMode) {
116
    this->DisplayGraph(this->InitialGraph, "initial");
117
  }
118
119

  // Identify components.
120
  cmComputeComponentGraph ccg(this->InitialGraph);
121
  if (this->DebugMode) {
122
    this->DisplayComponents(ccg);
123
124
  }
  if (!this->CheckComponents(ccg)) {
125
    return false;
126
  }
127
128

  // Compute the final dependency graph.
129
  if (!this->ComputeFinalDepends(ccg)) {
130
    return false;
131
132
  }
  if (this->DebugMode) {
133
    this->DisplayGraph(this->FinalGraph, "final");
134
  }
135
136
137
138

  return true;
}

139
140
void cmComputeTargetDepends::GetTargetDirectDepends(cmGeneratorTarget const* t,
                                                    cmTargetDependSet& deps)
141
142
143
{
  // Lookup the index for this target.  All targets should be known by
  // this point.
144
145
  std::map<cmGeneratorTarget const*, int>::const_iterator tii =
    this->TargetIndex.find(t);
146
147
148
149
  assert(tii != this->TargetIndex.end());
  int i = tii->second;

  // Get its final dependencies.
150
  EdgeList const& nl = this->FinalGraph[i];
151
152
  for (cmGraphEdge const& ni : nl) {
    cmGeneratorTarget const* dep = this->Targets[ni];
153
    cmTargetDependSet::iterator di = deps.insert(dep).first;
154
    di->SetType(ni.IsStrong());
155
  }
156
157
158
159
160
161
162
}

void cmComputeTargetDepends::CollectTargets()
{
  // Collect all targets from all generators.
  std::vector<cmLocalGenerator*> const& lgens =
    this->GlobalGenerator->GetLocalGenerators();
163
  for (cmLocalGenerator* lgen : lgens) {
164
    const std::vector<cmGeneratorTarget*>& targets =
165
166
      lgen->GetGeneratorTargets();
    for (cmGeneratorTarget const* ti : targets) {
167
      int index = static_cast<int>(this->Targets.size());
168
169
      this->TargetIndex[ti] = index;
      this->Targets.push_back(ti);
170
    }
171
  }
172
173
174
175
176
}

void cmComputeTargetDepends::CollectDepends()
{
  // Allocate the dependency graph adjacency lists.
177
  this->InitialGraph.resize(this->Targets.size());
178
179

  // Compute each dependency list.
180
  for (unsigned int i = 0; i < this->Targets.size(); ++i) {
181
    this->CollectTargetDepends(i);
182
  }
183
184
185
186
187
}

void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
{
  // Get the depender.
188
  cmGeneratorTarget const* depender = this->Targets[depender_index];
189
  if (depender->GetType() == cmStateEnums::INTERFACE_LIBRARY) {
190
    return;
191
  }
192

193
194
195
196
  // Loop over all targets linked directly in all configs.
  // We need to make targets depend on the union of all config-specific
  // dependencies in all targets, because the generated build-systems can't
  // deal with config-specific dependencies.
197
  {
198
    std::set<cmLinkItem> emitted;
199

200
201
202
    std::vector<std::string> configs;
    depender->Makefile->GetConfigurations(configs);
    if (configs.empty()) {
203
      configs.emplace_back();
204
    }
205
    for (std::string const& it : configs) {
206
      std::vector<cmSourceFile const*> objectFiles;
207
208
      depender->GetExternalObjects(objectFiles, it);
      for (cmSourceFile const* o : objectFiles) {
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
        std::string const& objLib = o->GetObjectLibrary();
        if (!objLib.empty()) {
          cmLinkItem const& objItem = depender->ResolveLinkItem(objLib);
          if (emitted.insert(objItem).second) {
            if (depender->GetType() != cmStateEnums::EXECUTABLE &&
                depender->GetType() != cmStateEnums::STATIC_LIBRARY &&
                depender->GetType() != cmStateEnums::SHARED_LIBRARY &&
                depender->GetType() != cmStateEnums::MODULE_LIBRARY &&
                depender->GetType() != cmStateEnums::OBJECT_LIBRARY) {
              this->GlobalGenerator->GetCMakeInstance()->IssueMessage(
                cmake::FATAL_ERROR,
                "Only executables and libraries may reference target objects.",
                depender->GetBacktrace());
              return;
            }
            const_cast<cmGeneratorTarget*>(depender)->Target->AddUtility(
              objLib);
226
227
228
          }
        }
      }
229

230
      cmLinkImplementation const* impl = depender->GetLinkImplementation(it);
231

232
      // A target should not depend on itself.
233
      emitted.insert(cmLinkItem(depender));
234
      for (cmLinkImplItem const& lib : impl->Libraries) {
235
        // Don't emit the same library twice for this target.
236
        if (emitted.insert(lib).second) {
237
238
          this->AddTargetDepend(depender_index, lib, true);
          this->AddInterfaceDepends(depender_index, lib, it, emitted);
239
240
241
242
        }
      }
    }
  }
243
244

  // Loop over all utility dependencies.
245
  {
246
    std::set<cmLinkItem> const& tutils = depender->GetUtilityItems();
247
    std::set<cmLinkItem> emitted;
248
    // A target should not depend on itself.
249
    emitted.insert(cmLinkItem(depender));
250
    for (cmLinkItem const& litem : tutils) {
251
      // Don't emit the same utility twice for this target.
252
      if (emitted.insert(litem).second) {
253
        this->AddTargetDepend(depender_index, litem, false);
254
255
      }
    }
256
  }
257
258
}

259
260
void cmComputeTargetDepends::AddInterfaceDepends(
  int depender_index, const cmGeneratorTarget* dependee,
261
  const std::string& config, std::set<cmLinkItem>& emitted)
262
{
263
  cmGeneratorTarget const* depender = this->Targets[depender_index];
264
265
  if (cmLinkInterface const* iface =
        dependee->GetLinkInterface(config, depender)) {
266
    for (cmLinkItem const& lib : iface->Libraries) {
267
      // Don't emit the same library twice for this target.
268
      if (emitted.insert(lib).second) {
269
270
        this->AddTargetDepend(depender_index, lib, true);
        this->AddInterfaceDepends(depender_index, lib, config, emitted);
271
272
      }
    }
273
  }
274
275
}

276
277
void cmComputeTargetDepends::AddInterfaceDepends(
  int depender_index, cmLinkItem const& dependee_name,
278
  const std::string& config, std::set<cmLinkItem>& emitted)
279
{
280
  cmGeneratorTarget const* depender = this->Targets[depender_index];
281
  cmGeneratorTarget const* dependee = dependee_name.Target;
282
283
284
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
285
  if (dependee && dependee->GetType() == cmStateEnums::EXECUTABLE &&
286
      !dependee->IsExecutableWithExports()) {
Daniel Pfeifer's avatar
Daniel Pfeifer committed
287
    dependee = nullptr;
288
  }
289

290
  if (dependee) {
291
    // A target should not depend on itself.
292
    emitted.insert(cmLinkItem(depender));
293
    this->AddInterfaceDepends(depender_index, dependee, config, emitted);
294
  }
295
296
}

297
298
299
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
                                             cmLinkItem const& dependee_name,
                                             bool linking)
300
301
{
  // Get the depender.
302
  cmGeneratorTarget const* depender = this->Targets[depender_index];
303
304

  // Check the target's makefile first.
305
  cmGeneratorTarget const* dependee = dependee_name.Target;
306

307
  if (!dependee && !linking &&
308
      (depender->GetType() != cmStateEnums::GLOBAL_TARGET)) {
309
310
    cmake::MessageType messageType = cmake::AUTHOR_WARNING;
    bool issueMessage = false;
311
    std::ostringstream e;
312
    switch (depender->GetPolicyStatusCMP0046()) {
313
      case cmPolicies::WARN:
Stephen Kelly's avatar
Stephen Kelly committed
314
        e << cmPolicies::GetPolicyWarning(cmPolicies::CMP0046) << "\n";
315
316
317
318
319
320
321
322
        issueMessage = true;
      case cmPolicies::OLD:
        break;
      case cmPolicies::NEW:
      case cmPolicies::REQUIRED_IF_USED:
      case cmPolicies::REQUIRED_ALWAYS:
        issueMessage = true;
        messageType = cmake::FATAL_ERROR;
323
324
    }
    if (issueMessage) {
325
      cmake* cm = this->GlobalGenerator->GetCMakeInstance();
326

327
328
      e << "The dependency target \"" << dependee_name << "\" of target \""
        << depender->GetName() << "\" does not exist.";
329
330

      cmListFileBacktrace const* backtrace =
331
        depender->GetUtilityBacktrace(dependee_name.AsStr());
332
      if (backtrace) {
333
        cm->IssueMessage(messageType, e.str(), *backtrace);
334
      } else {
335
        cm->IssueMessage(messageType, e.str());
336
337
      }
    }
338
  }
339

340
341
342
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
343
  if (linking && dependee && dependee->GetType() == cmStateEnums::EXECUTABLE &&
344
      !dependee->IsExecutableWithExports()) {
Daniel Pfeifer's avatar
Daniel Pfeifer committed
345
    dependee = nullptr;
346
  }
347

348
  if (dependee) {
349
    this->AddTargetDepend(depender_index, dependee, linking);
350
  }
351
}
352

353
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
354
                                             const cmGeneratorTarget* dependee,
355
356
                                             bool linking)
{
357
  if (dependee->IsImported() ||
358
      dependee->GetType() == cmStateEnums::INTERFACE_LIBRARY) {
359
360
    // Skip IMPORTED and INTERFACE targets but follow their utility
    // dependencies.
361
    std::set<cmLinkItem> const& utils = dependee->GetUtilityItems();
362
363
    for (cmLinkItem const& i : utils) {
      if (cmGeneratorTarget const* transitive_dependee = i.Target) {
364
        this->AddTargetDepend(depender_index, transitive_dependee, false);
365
366
      }
    }
367
  } else {
368
369
    // Lookup the index for this target.  All targets should be known by
    // this point.
370
    std::map<cmGeneratorTarget const*, int>::const_iterator tii =
371
372
373
374
375
      this->TargetIndex.find(dependee);
    assert(tii != this->TargetIndex.end());
    int dependee_index = tii->second;

    // Add this entry to the dependency graph.
376
    this->InitialGraph[depender_index].emplace_back(dependee_index, !linking);
377
  }
378
379
}

380
381
void cmComputeTargetDepends::DisplayGraph(Graph const& graph,
                                          const std::string& name)
382
{
383
  fprintf(stderr, "The %s target dependency graph is:\n", name.c_str());
384
  int n = static_cast<int>(graph.size());
385
  for (int depender_index = 0; depender_index < n; ++depender_index) {
386
    EdgeList const& nl = graph[depender_index];
387
    cmGeneratorTarget const* depender = this->Targets[depender_index];
388
389
    fprintf(stderr, "target %d is [%s]\n", depender_index,
            depender->GetName().c_str());
390
391
    for (cmGraphEdge const& ni : nl) {
      int dependee_index = ni;
392
      cmGeneratorTarget const* dependee = this->Targets[dependee_index];
393
      fprintf(stderr, "  depends on target %d [%s] (%s)\n", dependee_index,
394
              dependee->GetName().c_str(), ni.IsStrong() ? "strong" : "weak");
395
    }
396
  }
397
398
399
  fprintf(stderr, "\n");
}

400
401
void cmComputeTargetDepends::DisplayComponents(
  cmComputeComponentGraph const& ccg)
402
403
{
  fprintf(stderr, "The strongly connected components are:\n");
404
405
  std::vector<NodeList> const& components = ccg.GetComponents();
  int n = static_cast<int>(components.size());
406
  for (int c = 0; c < n; ++c) {
407
    NodeList const& nl = components[c];
408
    fprintf(stderr, "Component (%d):\n", c);
409
    for (int i : nl) {
410
411
      fprintf(stderr, "  contains target %d [%s]\n", i,
              this->Targets[i]->GetName().c_str());
412
    }
413
  }
414
415
416
  fprintf(stderr, "\n");
}

417
418
bool cmComputeTargetDepends::CheckComponents(
  cmComputeComponentGraph const& ccg)
419
420
421
{
  // All non-trivial components should consist only of static
  // libraries.
422
423
  std::vector<NodeList> const& components = ccg.GetComponents();
  int nc = static_cast<int>(components.size());
424
  for (int c = 0; c < nc; ++c) {
425
    // Get the current component.
426
    NodeList const& nl = components[c];
427
428

    // Skip trivial components.
429
    if (nl.size() < 2) {
430
      continue;
431
    }
432

433
    // Immediately complain if no cycles are allowed at all.
434
    if (this->NoCycles) {
435
436
      this->ComplainAboutBadComponent(ccg, c);
      return false;
437
    }
438

439
    // Make sure the component is all STATIC_LIBRARY targets.
440
441
    for (int ni : nl) {
      if (this->Targets[ni]->GetType() != cmStateEnums::STATIC_LIBRARY) {
442
        this->ComplainAboutBadComponent(ccg, c);
443
444
445
        return false;
      }
    }
446
  }
447
448
449
  return true;
}

450
451
void cmComputeTargetDepends::ComplainAboutBadComponent(
  cmComputeComponentGraph const& ccg, int c, bool strong)
452
453
{
  // Construct the error message.
454
  std::ostringstream e;
455
456
  e << "The inter-target dependency graph contains the following "
    << "strongly connected component (cycle):\n";
457
458
459
  std::vector<NodeList> const& components = ccg.GetComponents();
  std::vector<int> const& cmap = ccg.GetComponentMap();
  NodeList const& cl = components[c];
460
  for (int i : cl) {
461
    // Get the depender.
462
    cmGeneratorTarget const* depender = this->Targets[i];
463
464

    // Describe the depender.
465
    e << "  \"" << depender->GetName() << "\" of type "
466
      << cmState::GetTargetTypeName(depender->GetType()) << "\n";
467
468

    // List its dependencies that are inside the component.
469
    EdgeList const& nl = this->InitialGraph[i];
470
471
    for (cmGraphEdge const& ni : nl) {
      int j = ni;
472
      if (cmap[j] == c) {
473
        cmGeneratorTarget const* dependee = this->Targets[j];
474
        e << "    depends on \"" << dependee->GetName() << "\""
475
          << " (" << (ni.IsStrong() ? "strong" : "weak") << ")\n";
476
477
      }
    }
478
479
  }
  if (strong) {
480
481
482
483
484
    // Custom command executable dependencies cannot occur within a
    // component of static libraries.  The cycle must appear in calls
    // to add_dependencies.
    e << "The component contains at least one cycle consisting of strong "
      << "dependencies (created by add_dependencies) that cannot be broken.";
485
  } else if (this->NoCycles) {
486
487
    e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
      << "cyclic dependencies are not allowed even among static libraries.";
488
  } else {
489
490
    e << "At least one of these targets is not a STATIC_LIBRARY.  "
      << "Cyclic dependencies are allowed only among static libraries.";
491
  }
492
493
494
  cmSystemTools::Error(e.str().c_str());
}

495
496
497
498
bool cmComputeTargetDepends::IntraComponent(std::vector<int> const& cmap,
                                            int c, int i, int* head,
                                            std::set<int>& emitted,
                                            std::set<int>& visited)
499
{
500
  if (!visited.insert(i).second) {
501
502
    // Cycle in utility depends!
    return false;
503
504
  }
  if (emitted.insert(i).second) {
505
506
    // Honor strong intra-component edges in the final order.
    EdgeList const& el = this->InitialGraph[i];
507
508
509
    for (cmGraphEdge const& edge : el) {
      int j = edge;
      if (cmap[j] == c && edge.IsStrong()) {
510
        this->FinalGraph[i].emplace_back(j, true);
511
        if (!this->IntraComponent(cmap, c, j, head, emitted, visited)) {
512
513
514
          return false;
        }
      }
515
    }
516
517

    // Prepend to a linear linked-list of intra-component edges.
518
    if (*head >= 0) {
519
      this->FinalGraph[i].emplace_back(*head, false);
520
    } else {
521
522
      this->ComponentTail[c] = i;
    }
523
524
    *head = i;
  }
525
526
527
  return true;
}

528
529
bool cmComputeTargetDepends::ComputeFinalDepends(
  cmComputeComponentGraph const& ccg)
530
{
531
532
533
534
535
536
537
  // Get the component graph information.
  std::vector<NodeList> const& components = ccg.GetComponents();
  Graph const& cgraph = ccg.GetComponentGraph();

  // Allocate the final graph.
  this->FinalGraph.resize(0);
  this->FinalGraph.resize(this->InitialGraph.size());
538

539
540
541
542
543
  // Choose intra-component edges to linearize dependencies.
  std::vector<int> const& cmap = ccg.GetComponentMap();
  this->ComponentHead.resize(components.size());
  this->ComponentTail.resize(components.size());
  int nc = static_cast<int>(components.size());
544
  for (int c = 0; c < nc; ++c) {
545
546
547
    int head = -1;
    std::set<int> emitted;
    NodeList const& nl = components[c];
548
549
    for (NodeList::const_reverse_iterator ni = nl.rbegin(); ni != nl.rend();
         ++ni) {
550
      std::set<int> visited;
551
      if (!this->IntraComponent(cmap, c, *ni, &head, emitted, visited)) {
552
553
554
555
556
        // Cycle in add_dependencies within component!
        this->ComplainAboutBadComponent(ccg, c, true);
        return false;
      }
    }
557
558
    this->ComponentHead[c] = head;
  }
559

560
  // Convert inter-component edges to connect component tails to heads.
561
  int n = static_cast<int>(cgraph.size());
562
563
  for (int depender_component = 0; depender_component < n;
       ++depender_component) {
564
    int depender_component_tail = this->ComponentTail[depender_component];
565
    EdgeList const& nl = cgraph[depender_component];
566
567
    for (cmGraphEdge const& ni : nl) {
      int dependee_component = ni;
568
      int dependee_component_head = this->ComponentHead[dependee_component];
569
570
      this->FinalGraph[depender_component_tail].emplace_back(
        dependee_component_head, ni.IsStrong());
571
    }
572
  }
573
  return true;
574
}