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 "cmStateTypes.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:
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
}