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
15
#include "cmSystemTools.h"
#include "cmTarget.h"
16
#include "cmTargetDepend.h"
17
18
19
#include "cmake.h"

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

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

/*

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
34
STATIC libraries may depend on each other in a cyclic fashion.  In
35
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
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();
99
100
101
102
  this->DebugMode =
    cm->GetState()->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
  this->NoCycles =
    cm->GetState()->GetGlobalPropertyAsBool("GLOBAL_DEPENDS_NO_CYCLES");
103
104
105
106
107
108
109
110
111
112
113
}

cmComputeTargetDepends::~cmComputeTargetDepends()
{
}

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

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

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

  return true;
}

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

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

void cmComputeTargetDepends::CollectTargets()
{
  // Collect all targets from all generators.
  std::vector<cmLocalGenerator*> const& lgens =
    this->GlobalGenerator->GetLocalGenerators();
162
  for (unsigned int i = 0; i < lgens.size(); ++i) {
Stephen Kelly's avatar
Stephen Kelly committed
163
    const std::vector<cmGeneratorTarget*> targets =
164
165
166
      lgens[i]->GetGeneratorTargets();
    for (std::vector<cmGeneratorTarget*>::const_iterator ti = targets.begin();
         ti != targets.end(); ++ti) {
Stephen Kelly's avatar
Stephen Kelly committed
167
      cmGeneratorTarget* gt = *ti;
168
      int index = static_cast<int>(this->Targets.size());
169
170
      this->TargetIndex[gt] = index;
      this->Targets.push_back(gt);
171
    }
172
  }
173
174
175
176
177
}

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

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

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

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

201
202
203
204
    std::vector<std::string> configs;
    depender->Makefile->GetConfigurations(configs);
    if (configs.empty()) {
      configs.push_back("");
205
    }
206
207
208
209
210
211
212
213
214
    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) {
215
216
217
218
          if (depender->GetType() != cmStateEnums::EXECUTABLE &&
              depender->GetType() != cmStateEnums::STATIC_LIBRARY &&
              depender->GetType() != cmStateEnums::SHARED_LIBRARY &&
              depender->GetType() != cmStateEnums::MODULE_LIBRARY) {
219
220
221
222
223
224
            this->GlobalGenerator->GetCMakeInstance()->IssueMessage(
              cmake::FATAL_ERROR,
              "Only executables and non-OBJECT libraries may "
              "reference target objects.",
              depender->GetBacktrace());
            return;
225
          }
226
          const_cast<cmGeneratorTarget*>(depender)->Target->AddUtility(objLib);
227
228
        }
      }
229

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

232
233
234
235
236
237
238
239
240
      // 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);
241
242
243
244
        }
      }
    }
  }
245
246

  // Loop over all utility dependencies.
247
  {
248
249
250
251
252
253
254
255
256
    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);
257
258
      }
    }
259
  }
260
261
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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