cmComputeTargetDepends.cxx 20.1 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
      // 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);
241
          this->AddInterfaceDepends(depender_index, *lib, *it, 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, config, emitted);
277
278
      }
    }
279
  }
280
281
}

282
283
void cmComputeTargetDepends::AddInterfaceDepends(
  int depender_index, cmLinkItem const& dependee_name,
284
  const std::string& config, 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
298
299
    // A target should not depend on itself.
    emitted.insert(depender->GetName());
    this->AddInterfaceDepends(depender_index, dependee, config, emitted);
300
  }
301
302
}

303
304
305
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
                                             cmLinkItem const& dependee_name,
                                             bool linking)
306
307
{
  // Get the depender.
308
  cmGeneratorTarget const* depender = this->Targets[depender_index];
309
310

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

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

333
334
      e << "The dependency target \"" << dependee_name << "\" of target \""
        << depender->GetName() << "\" does not exist.";
335
336

      cmListFileBacktrace const* backtrace =
337
        depender->GetUtilityBacktrace(dependee_name);
338
      if (backtrace) {
339
        cm->IssueMessage(messageType, e.str(), *backtrace);
340
      } else {
341
        cm->IssueMessage(messageType, e.str());
342
343
      }
    }
344
  }
345

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

354
  if (dependee) {
355
    this->AddTargetDepend(depender_index, dependee, linking);
356
  }
357
}
358

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

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

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

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

    // Skip trivial components.
438
    if (nl.size() < 2) {
439
      continue;
440
    }
441

442
    // Immediately complain if no cycles are allowed at all.
443
    if (this->NoCycles) {
444
445
      this->ComplainAboutBadComponent(ccg, c);
      return false;
446
    }
447

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

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

    // Describe the depender.
475
    e << "  \"" << depender->GetName() << "\" of type "
476
      << cmState::GetTargetTypeName(depender->GetType()) << "\n";
477
478

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

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

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

538
539
bool cmComputeTargetDepends::ComputeFinalDepends(
  cmComputeComponentGraph const& ccg)
540
{
541
542
543
544
545
546
547
  // 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());
548

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

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