cmComputeTargetDepends.cxx 20.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
  for (EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) {
152
    cmGeneratorTarget const* dep = this->Targets[*ni];
153
154
    cmTargetDependSet::iterator di = deps.insert(dep).first;
    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 (unsigned int i = 0; i < lgens.size(); ++i) {
Stephen Kelly's avatar
Stephen Kelly committed
164
    const std::vector<cmGeneratorTarget*> targets =
165
166
167
      lgens[i]->GetGeneratorTargets();
    for (std::vector<cmGeneratorTarget*>::const_iterator ti = targets.begin();
         ti != targets.end(); ++ti) {
Stephen Kelly's avatar
Stephen Kelly committed
168
      cmGeneratorTarget* gt = *ti;
169
      int index = static_cast<int>(this->Targets.size());
170
171
      this->TargetIndex[gt] = index;
      this->Targets.push_back(gt);
172
    }
173
  }
174
175
176
177
178
}

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

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

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

195
196
197
198
  // 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.
199
  {
200
    std::set<std::string> emitted;
201

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

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

233
234
235
236
237
238
239
240
241
      // A target should not depend on itself.
      emitted.insert(depender->GetName());
      for (std::vector<cmLinkImplItem>::const_iterator lib =
             impl->Libraries.begin();
           lib != impl->Libraries.end(); ++lib) {
        // Don't emit the same library twice for this target.
        if (emitted.insert(*lib).second) {
          this->AddTargetDepend(depender_index, *lib, true);
          this->AddInterfaceDepends(depender_index, *lib, emitted);
242
243
244
245
        }
      }
    }
  }
246
247

  // Loop over all utility dependencies.
248
  {
249
250
251
252
253
254
255
256
257
    std::set<cmLinkItem> const& tutils = depender->GetUtilityItems();
    std::set<std::string> emitted;
    // A target should not depend on itself.
    emitted.insert(depender->GetName());
    for (std::set<cmLinkItem>::const_iterator util = tutils.begin();
         util != tutils.end(); ++util) {
      // Don't emit the same utility twice for this target.
      if (emitted.insert(*util).second) {
        this->AddTargetDepend(depender_index, *util, false);
258
259
      }
    }
260
  }
261
262
}

263
264
265
void cmComputeTargetDepends::AddInterfaceDepends(
  int depender_index, const cmGeneratorTarget* dependee,
  const std::string& config, std::set<std::string>& emitted)
266
{
267
  cmGeneratorTarget const* depender = this->Targets[depender_index];
268
269
270
271
272
  if (cmLinkInterface const* iface =
        dependee->GetLinkInterface(config, depender)) {
    for (std::vector<cmLinkItem>::const_iterator lib =
           iface->Libraries.begin();
         lib != iface->Libraries.end(); ++lib) {
273
      // Don't emit the same library twice for this target.
274
      if (emitted.insert(*lib).second) {
Stephen Kelly's avatar
Stephen Kelly committed
275
        this->AddTargetDepend(depender_index, *lib, true);
276
        this->AddInterfaceDepends(depender_index, *lib, emitted);
277
278
      }
    }
279
  }
280
281
}

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

296
  if (dependee) {
297
    this->AddInterfaceDepends(depender_index, dependee, "", emitted);
298
    std::vector<std::string> configs;
299
    depender->Makefile->GetConfigurations(configs);
300
    for (std::vector<std::string>::const_iterator it = configs.begin();
301
         it != configs.end(); ++it) {
302
303
      // A target should not depend on itself.
      emitted.insert(depender->GetName());
304
      this->AddInterfaceDepends(depender_index, dependee, *it, emitted);
305
    }
306
  }
307
308
}

309
310
311
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
                                             cmLinkItem const& dependee_name,
                                             bool linking)
312
313
{
  // Get the depender.
314
  cmGeneratorTarget const* depender = this->Targets[depender_index];
315
316

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

319
  if (!dependee && !linking &&
320
      (depender->GetType() != cmStateEnums::GLOBAL_TARGET)) {
321
322
    cmake::MessageType messageType = cmake::AUTHOR_WARNING;
    bool issueMessage = false;
323
    std::ostringstream e;
324
    switch (depender->GetPolicyStatusCMP0046()) {
325
      case cmPolicies::WARN:
Stephen Kelly's avatar
Stephen Kelly committed
326
        e << cmPolicies::GetPolicyWarning(cmPolicies::CMP0046) << "\n";
327
328
329
330
331
332
333
334
        issueMessage = true;
      case cmPolicies::OLD:
        break;
      case cmPolicies::NEW:
      case cmPolicies::REQUIRED_IF_USED:
      case cmPolicies::REQUIRED_ALWAYS:
        issueMessage = true;
        messageType = cmake::FATAL_ERROR;
335
336
    }
    if (issueMessage) {
337
      cmake* cm = this->GlobalGenerator->GetCMakeInstance();
338

339
340
      e << "The dependency target \"" << dependee_name << "\" of target \""
        << depender->GetName() << "\" does not exist.";
341
342

      cmListFileBacktrace const* backtrace =
343
        depender->GetUtilityBacktrace(dependee_name);
344
      if (backtrace) {
345
        cm->IssueMessage(messageType, e.str(), *backtrace);
346
      } else {
347
        cm->IssueMessage(messageType, e.str());
348
349
      }
    }
350
  }
351

352
353
354
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
355
  if (linking && dependee && dependee->GetType() == cmStateEnums::EXECUTABLE &&
356
      !dependee->IsExecutableWithExports()) {
Daniel Pfeifer's avatar
Daniel Pfeifer committed
357
    dependee = CM_NULLPTR;
358
  }
359

360
  if (dependee) {
361
    this->AddTargetDepend(depender_index, dependee, linking);
362
  }
363
}
364

365
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
366
                                             const cmGeneratorTarget* dependee,
367
368
                                             bool linking)
{
369
  if (dependee->IsImported() ||
370
      dependee->GetType() == cmStateEnums::INTERFACE_LIBRARY) {
371
372
    // Skip IMPORTED and INTERFACE targets but follow their utility
    // dependencies.
373
    std::set<cmLinkItem> const& utils = dependee->GetUtilityItems();
374
375
376
    for (std::set<cmLinkItem>::const_iterator i = utils.begin();
         i != utils.end(); ++i) {
      if (cmGeneratorTarget const* transitive_dependee = i->Target) {
377
        this->AddTargetDepend(depender_index, transitive_dependee, false);
378
379
      }
    }
380
  } else {
381
382
    // Lookup the index for this target.  All targets should be known by
    // this point.
383
    std::map<cmGeneratorTarget const*, int>::const_iterator tii =
384
385
386
387
388
389
390
      this->TargetIndex.find(dependee);
    assert(tii != this->TargetIndex.end());
    int dependee_index = tii->second;

    // Add this entry to the dependency graph.
    this->InitialGraph[depender_index].push_back(
      cmGraphEdge(dependee_index, !linking));
391
  }
392
393
}

394
395
void cmComputeTargetDepends::DisplayGraph(Graph const& graph,
                                          const std::string& name)
396
{
397
  fprintf(stderr, "The %s target dependency graph is:\n", name.c_str());
398
  int n = static_cast<int>(graph.size());
399
  for (int depender_index = 0; depender_index < n; ++depender_index) {
400
    EdgeList const& nl = graph[depender_index];
401
    cmGeneratorTarget const* depender = this->Targets[depender_index];
402
403
404
    fprintf(stderr, "target %d is [%s]\n", depender_index,
            depender->GetName().c_str());
    for (EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) {
405
      int dependee_index = *ni;
406
      cmGeneratorTarget const* dependee = this->Targets[dependee_index];
407
      fprintf(stderr, "  depends on target %d [%s] (%s)\n", dependee_index,
408
              dependee->GetName().c_str(), ni->IsStrong() ? "strong" : "weak");
409
    }
410
  }
411
412
413
  fprintf(stderr, "\n");
}

414
415
void cmComputeTargetDepends::DisplayComponents(
  cmComputeComponentGraph const& ccg)
416
417
{
  fprintf(stderr, "The strongly connected components are:\n");
418
419
  std::vector<NodeList> const& components = ccg.GetComponents();
  int n = static_cast<int>(components.size());
420
  for (int c = 0; c < n; ++c) {
421
    NodeList const& nl = components[c];
422
    fprintf(stderr, "Component (%d):\n", c);
423
    for (NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) {
424
      int i = *ni;
425
426
      fprintf(stderr, "  contains target %d [%s]\n", i,
              this->Targets[i]->GetName().c_str());
427
    }
428
  }
429
430
431
  fprintf(stderr, "\n");
}

432
433
bool cmComputeTargetDepends::CheckComponents(
  cmComputeComponentGraph const& ccg)
434
435
436
{
  // All non-trivial components should consist only of static
  // libraries.
437
438
  std::vector<NodeList> const& components = ccg.GetComponents();
  int nc = static_cast<int>(components.size());
439
  for (int c = 0; c < nc; ++c) {
440
    // Get the current component.
441
    NodeList const& nl = components[c];
442
443

    // Skip trivial components.
444
    if (nl.size() < 2) {
445
      continue;
446
    }
447

448
    // Immediately complain if no cycles are allowed at all.
449
    if (this->NoCycles) {
450
451
      this->ComplainAboutBadComponent(ccg, c);
      return false;
452
    }
453

454
    // Make sure the component is all STATIC_LIBRARY targets.
455
    for (NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) {
456
      if (this->Targets[*ni]->GetType() != cmStateEnums::STATIC_LIBRARY) {
457
        this->ComplainAboutBadComponent(ccg, c);
458
459
460
        return false;
      }
    }
461
  }
462
463
464
  return true;
}

465
466
void cmComputeTargetDepends::ComplainAboutBadComponent(
  cmComputeComponentGraph const& ccg, int c, bool strong)
467
468
{
  // Construct the error message.
469
  std::ostringstream e;
470
471
  e << "The inter-target dependency graph contains the following "
    << "strongly connected component (cycle):\n";
472
473
474
  std::vector<NodeList> const& components = ccg.GetComponents();
  std::vector<int> const& cmap = ccg.GetComponentMap();
  NodeList const& cl = components[c];
475
  for (NodeList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci) {
476
477
    // Get the depender.
    int i = *ci;
478
    cmGeneratorTarget const* depender = this->Targets[i];
479
480

    // Describe the depender.
481
    e << "  \"" << depender->GetName() << "\" of type "
482
      << cmState::GetTargetTypeName(depender->GetType()) << "\n";
483
484

    // List its dependencies that are inside the component.
485
    EdgeList const& nl = this->InitialGraph[i];
486
    for (EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) {
487
      int j = *ni;
488
      if (cmap[j] == c) {
489
        cmGeneratorTarget const* dependee = this->Targets[j];
490
        e << "    depends on \"" << dependee->GetName() << "\""
491
          << " (" << (ni->IsStrong() ? "strong" : "weak") << ")\n";
492
493
      }
    }
494
495
  }
  if (strong) {
496
497
498
499
500
    // 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.";
501
  } else if (this->NoCycles) {
502
503
    e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
      << "cyclic dependencies are not allowed even among static libraries.";
504
  } else {
505
506
    e << "At least one of these targets is not a STATIC_LIBRARY.  "
      << "Cyclic dependencies are allowed only among static libraries.";
507
  }
508
509
510
  cmSystemTools::Error(e.str().c_str());
}

511
512
513
514
bool cmComputeTargetDepends::IntraComponent(std::vector<int> const& cmap,
                                            int c, int i, int* head,
                                            std::set<int>& emitted,
                                            std::set<int>& visited)
515
{
516
  if (!visited.insert(i).second) {
517
518
    // Cycle in utility depends!
    return false;
519
520
  }
  if (emitted.insert(i).second) {
521
522
    // Honor strong intra-component edges in the final order.
    EdgeList const& el = this->InitialGraph[i];
523
    for (EdgeList::const_iterator ei = el.begin(); ei != el.end(); ++ei) {
524
      int j = *ei;
525
      if (cmap[j] == c && ei->IsStrong()) {
526
        this->FinalGraph[i].push_back(cmGraphEdge(j, true));
527
        if (!this->IntraComponent(cmap, c, j, head, emitted, visited)) {
528
529
530
          return false;
        }
      }
531
    }
532
533

    // Prepend to a linear linked-list of intra-component edges.
534
    if (*head >= 0) {
535
      this->FinalGraph[i].push_back(cmGraphEdge(*head, false));
536
    } else {
537
538
      this->ComponentTail[c] = i;
    }
539
540
    *head = i;
  }
541
542
543
  return true;
}

544
545
bool cmComputeTargetDepends::ComputeFinalDepends(
  cmComputeComponentGraph const& ccg)
546
{
547
548
549
550
551
552
553
  // 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());
554

555
556
557
558
559
  // 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());
560
  for (int c = 0; c < nc; ++c) {
561
562
563
    int head = -1;
    std::set<int> emitted;
    NodeList const& nl = components[c];
564
565
    for (NodeList::const_reverse_iterator ni = nl.rbegin(); ni != nl.rend();
         ++ni) {
566
      std::set<int> visited;
567
      if (!this->IntraComponent(cmap, c, *ni, &head, emitted, visited)) {
568
569
570
571
572
        // Cycle in add_dependencies within component!
        this->ComplainAboutBadComponent(ccg, c, true);
        return false;
      }
    }
573
574
    this->ComponentHead[c] = head;
  }
575

576
  // Convert inter-component edges to connect component tails to heads.
577
  int n = static_cast<int>(cgraph.size());
578
579
  for (int depender_component = 0; depender_component < n;
       ++depender_component) {
580
    int depender_component_tail = this->ComponentTail[depender_component];
581
    EdgeList const& nl = cgraph[depender_component];
582
    for (EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) {
583
      int dependee_component = *ni;
584
      int dependee_component_head = this->ComponentHead[dependee_component];
585
586
      this->FinalGraph[depender_component_tail].push_back(
        cmGraphEdge(dependee_component_head, ni->IsStrong()));
587
    }
588
  }
589
  return true;
590
}