cmComputeTargetDepends.cxx 21.8 KB
Newer Older
1
2
3
/*============================================================================
  CMake - Cross Platform Makefile Generator
  Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
4

5
6
  Distributed under the OSI-approved BSD License (the "License");
  see accompanying file Copyright.txt for details.
7

8
9
10
11
  This software is distributed WITHOUT ANY WARRANTY; without even the
  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  See the License for more information.
============================================================================*/
12
13
#include "cmComputeTargetDepends.h"

14
#include "cmComputeComponentGraph.h"
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include "cmGlobalGenerator.h"
#include "cmLocalGenerator.h"
#include "cmMakefile.h"
#include "cmSystemTools.h"
#include "cmTarget.h"
#include "cmake.h"

#include <algorithm>

#include <assert.h>

/*

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
99
100
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();
  this->DebugMode = cm->GetPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
101
  this->NoCycles = cm->GetPropertyAsBool("GLOBAL_DEPENDS_NO_CYCLES");
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
}

//----------------------------------------------------------------------------
cmComputeTargetDepends::~cmComputeTargetDepends()
{
}

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

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

  // Compute the final dependency graph.
132
133
134
135
  if(!this->ComputeFinalDepends(ccg))
    {
    return false;
    }
136
137
  if(this->DebugMode)
    {
138
    this->DisplayGraph(this->FinalGraph, "final");
139
140
141
142
143
144
145
    }

  return true;
}

//----------------------------------------------------------------------------
void
146
cmComputeTargetDepends::GetTargetDirectDepends(cmTarget const* t,
147
                                               cmTargetDependSet& deps)
148
149
150
{
  // Lookup the index for this target.  All targets should be known by
  // this point.
151
152
  std::map<cmTarget const*, int>::const_iterator tii
                                                  = this->TargetIndex.find(t);
153
154
155
156
  assert(tii != this->TargetIndex.end());
  int i = tii->second;

  // Get its final dependencies.
157
158
  EdgeList const& nl = this->FinalGraph[i];
  for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
159
    {
160
    cmTarget const* dep = this->Targets[*ni];
161
162
    cmTargetDependSet::iterator di = deps.insert(dep).first;
    di->SetType(ni->IsStrong());
163
164
165
166
167
168
169
170
171
172
173
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::CollectTargets()
{
  // Collect all targets from all generators.
  std::vector<cmLocalGenerator*> const& lgens =
    this->GlobalGenerator->GetLocalGenerators();
  for(unsigned int i = 0; i < lgens.size(); ++i)
    {
174
175
176
    const cmTargets& targets = lgens[i]->GetMakefile()->GetTargets();
    for(cmTargets::const_iterator ti = targets.begin();
        ti != targets.end(); ++ti)
177
      {
178
      cmTarget const* target = &ti->second;
179
180
181
182
183
184
185
186
187
188
189
      int index = static_cast<int>(this->Targets.size());
      this->TargetIndex[target] = index;
      this->Targets.push_back(target);
      }
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::CollectDepends()
{
  // Allocate the dependency graph adjacency lists.
190
  this->InitialGraph.resize(this->Targets.size());
191
192
193
194
195
196
197
198
199
200
201
202

  // Compute each dependency list.
  for(unsigned int i=0; i < this->Targets.size(); ++i)
    {
    this->CollectTargetDepends(i);
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
{
  // Get the depender.
203
  cmTarget const* depender = this->Targets[depender_index];
204
205
206
207
  if (depender->GetType() == cmTarget::INTERFACE_LIBRARY)
    {
    return;
    }
208

209
210
211
212
  // 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.
213
214
  {
  std::set<cmStdString> emitted;
215
216
  {
  std::vector<std::string> tlibs;
217
  depender->GetDirectLinkLibraries(0, tlibs, depender);
218
219
  // A target should not depend on itself.
  emitted.insert(depender->GetName());
220
  for(std::vector<std::string>::const_iterator lib = tlibs.begin();
221
222
223
      lib != tlibs.end(); ++lib)
    {
    // Don't emit the same library twice for this target.
224
    if(emitted.insert(*lib).second)
225
      {
226
227
      this->AddTargetDepend(depender_index, lib->c_str(), true);
      this->AddInterfaceDepends(depender_index, lib->c_str(),
228
                                true, emitted);
229
230
      }
    }
231
  }
232
233
234
235
236
237
  std::vector<std::string> configs;
  depender->GetMakefile()->GetConfigurations(configs);
  for (std::vector<std::string>::const_iterator it = configs.begin();
    it != configs.end(); ++it)
    {
    std::vector<std::string> tlibs;
238
239
    depender->GetDirectLinkLibraries(it->c_str(), tlibs, depender);

240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
    // A target should not depend on itself.
    emitted.insert(depender->GetName());
    for(std::vector<std::string>::const_iterator lib = tlibs.begin();
        lib != tlibs.end(); ++lib)
      {
      // Don't emit the same library twice for this target.
      if(emitted.insert(*lib).second)
        {
        this->AddTargetDepend(depender_index, lib->c_str(), true);
        this->AddInterfaceDepends(depender_index, lib->c_str(),
                                  true, emitted);
        }
      }
    }
  }
255
256

  // Loop over all utility dependencies.
257
  {
258
  std::set<cmStdString> const& tutils = depender->GetUtilities();
259
260
261
  std::set<cmStdString> emitted;
  // A target should not depend on itself.
  emitted.insert(depender->GetName());
262
263
264
265
266
267
  for(std::set<cmStdString>::const_iterator util = tutils.begin();
      util != tutils.end(); ++util)
    {
    // Don't emit the same utility twice for this target.
    if(emitted.insert(*util).second)
      {
268
      this->AddTargetDepend(depender_index, util->c_str(), false);
269
270
      }
    }
271
  }
272
273
}

274
275
//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
276
                                                 cmTarget const* dependee,
277
278
279
                                                 const char *config,
                                               std::set<cmStdString> &emitted)
{
280
  cmTarget const* depender = this->Targets[depender_index];
281
  if(cmTarget::LinkInterface const* iface =
282
                                dependee->GetLinkInterface(config, depender))
283
284
285
286
287
288
289
290
291
    {
    for(std::vector<std::string>::const_iterator
        lib = iface->Libraries.begin();
        lib != iface->Libraries.end(); ++lib)
      {
      // Don't emit the same library twice for this target.
      if(emitted.insert(*lib).second)
        {
        this->AddTargetDepend(depender_index, lib->c_str(), true);
292
293
        this->AddInterfaceDepends(depender_index, lib->c_str(),
                                  true, emitted);
294
295
296
297
298
299
300
301
302
303
304
        }
      }
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
                                             const char* dependee_name,
                                             bool linking,
                                             std::set<cmStdString> &emitted)
{
305
306
  cmTarget const* depender = this->Targets[depender_index];
  cmTarget const* dependee =
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
    depender->GetMakefile()->FindTargetToUse(dependee_name);
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
  if(linking && dependee &&
     dependee->GetType() == cmTarget::EXECUTABLE &&
     !dependee->IsExecutableWithExports())
    {
    dependee = 0;
    }

  if(dependee)
    {
    this->AddInterfaceDepends(depender_index, dependee, 0, emitted);
    std::vector<std::string> configs;
    depender->GetMakefile()->GetConfigurations(configs);
    for (std::vector<std::string>::const_iterator it = configs.begin();
      it != configs.end(); ++it)
      {
      // A target should not depend on itself.
      emitted.insert(depender->GetName());
      this->AddInterfaceDepends(depender_index, dependee,
                                it->c_str(), emitted);
      }
    }
}

334
335
//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
336
337
                                             const char* dependee_name,
                                             bool linking)
338
339
{
  // Get the depender.
340
  cmTarget const* depender = this->Targets[depender_index];
341
342

  // Check the target's makefile first.
343
  cmTarget const* dependee =
344
    depender->GetMakefile()->FindTargetToUse(dependee_name);
345

346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
  if(!dependee && !linking &&
    (depender->GetType() != cmTarget::GLOBAL_TARGET))
    {
    cmMakefile *makefile = depender->GetMakefile();
    cmake::MessageType messageType = cmake::AUTHOR_WARNING;
    bool issueMessage = false;
    switch(makefile->GetPolicyStatus(cmPolicies::CMP0046))
      {
      case cmPolicies::WARN:
        issueMessage = true;
      case cmPolicies::OLD:
        break;
      case cmPolicies::NEW:
      case cmPolicies::REQUIRED_IF_USED:
      case cmPolicies::REQUIRED_ALWAYS:
        issueMessage = true;
        messageType = cmake::FATAL_ERROR;
      }
    if(issueMessage)
      {
      cmake* cm = this->GlobalGenerator->GetCMakeInstance();
      cmOStringStream e;
      e << (makefile->GetPolicies()
        ->GetPolicyWarning(cmPolicies::CMP0046)) << "\n";
      e << "The dependency target \"" <<  dependee_name
        << "\" of target \"" << depender->GetName() << "\" does not exist.";

      cmListFileBacktrace nullBacktrace;
      cmListFileBacktrace const* backtrace =
        depender->GetUtilityBacktrace(dependee_name);
      if(!backtrace)
        {
        backtrace = &nullBacktrace;
        }

      cm->IssueMessage(messageType, e.str(), *backtrace);
      }
    }

385
386
387
388
389
390
391
392
393
394
  // Skip targets that will not really be linked.  This is probably a
  // name conflict between an external library and an executable
  // within the project.
  if(linking && dependee &&
     dependee->GetType() == cmTarget::EXECUTABLE &&
     !dependee->IsExecutableWithExports())
    {
    dependee = 0;
    }

395
  if(dependee)
396
    {
397
    this->AddTargetDepend(depender_index, dependee, linking);
398
    }
399
}
400

401
402
//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
403
                                             cmTarget const* dependee,
404
405
406
407
408
409
410
411
412
                                             bool linking)
{
  if(dependee->IsImported())
    {
    // Skip imported targets but follow their utility dependencies.
    std::set<cmStdString> const& utils = dependee->GetUtilities();
    for(std::set<cmStdString>::const_iterator i = utils.begin();
        i != utils.end(); ++i)
      {
413
      if(cmTarget const* transitive_dependee =
414
415
416
417
         dependee->GetMakefile()->FindTargetToUse(i->c_str()))
        {
        this->AddTargetDepend(depender_index, transitive_dependee, false);
        }
418
419
420
421
422
423
      }
    }
  else
    {
    // Lookup the index for this target.  All targets should be known by
    // this point.
424
    std::map<cmTarget const*, int>::const_iterator tii =
425
426
427
428
429
430
431
432
      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));
    }
433
434
435
436
}

//----------------------------------------------------------------------------
void
437
cmComputeTargetDepends::DisplayGraph(Graph const& graph, const char* name)
438
439
440
441
442
{
  fprintf(stderr, "The %s target dependency graph is:\n", name);
  int n = static_cast<int>(graph.size());
  for(int depender_index = 0; depender_index < n; ++depender_index)
    {
443
    EdgeList const& nl = graph[depender_index];
444
    cmTarget const* depender = this->Targets[depender_index];
445
446
    fprintf(stderr, "target %d is [%s]\n",
            depender_index, depender->GetName());
447
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
448
      {
449
      int dependee_index = *ni;
450
      cmTarget const* dependee = this->Targets[dependee_index];
451
452
      fprintf(stderr, "  depends on target %d [%s] (%s)\n", dependee_index,
              dependee->GetName(), ni->IsStrong()? "strong" : "weak");
453
454
455
456
457
458
      }
    }
  fprintf(stderr, "\n");
}

//----------------------------------------------------------------------------
459
460
461
void
cmComputeTargetDepends
::DisplayComponents(cmComputeComponentGraph const& ccg)
462
463
{
  fprintf(stderr, "The strongly connected components are:\n");
464
465
  std::vector<NodeList> const& components = ccg.GetComponents();
  int n = static_cast<int>(components.size());
466
467
  for(int c = 0; c < n; ++c)
    {
468
    NodeList const& nl = components[c];
469
    fprintf(stderr, "Component (%d):\n", c);
470
    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
471
      {
472
      int i = *ni;
473
474
475
476
477
478
479
480
      fprintf(stderr, "  contains target %d [%s]\n",
              i, this->Targets[i]->GetName());
      }
    }
  fprintf(stderr, "\n");
}

//----------------------------------------------------------------------------
481
482
483
bool
cmComputeTargetDepends
::CheckComponents(cmComputeComponentGraph const& ccg)
484
485
486
{
  // All non-trivial components should consist only of static
  // libraries.
487
488
  std::vector<NodeList> const& components = ccg.GetComponents();
  int nc = static_cast<int>(components.size());
489
490
491
  for(int c=0; c < nc; ++c)
    {
    // Get the current component.
492
    NodeList const& nl = components[c];
493
494

    // Skip trivial components.
495
    if(nl.size() < 2)
496
497
498
499
      {
      continue;
      }

500
501
502
503
504
505
506
    // Immediately complain if no cycles are allowed at all.
    if(this->NoCycles)
      {
      this->ComplainAboutBadComponent(ccg, c);
      return false;
      }

507
    // Make sure the component is all STATIC_LIBRARY targets.
508
    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
509
      {
510
      if(this->Targets[*ni]->GetType() != cmTarget::STATIC_LIBRARY)
511
        {
512
        this->ComplainAboutBadComponent(ccg, c);
513
514
515
516
517
518
519
520
521
        return false;
        }
      }
    }
  return true;
}

//----------------------------------------------------------------------------
void
522
cmComputeTargetDepends
523
524
::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c,
                            bool strong)
525
526
527
528
529
{
  // Construct the error message.
  cmOStringStream e;
  e << "The inter-target dependency graph contains the following "
    << "strongly connected component (cycle):\n";
530
531
532
533
  std::vector<NodeList> const& components = ccg.GetComponents();
  std::vector<int> const& cmap = ccg.GetComponentMap();
  NodeList const& cl = components[c];
  for(NodeList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci)
534
535
536
    {
    // Get the depender.
    int i = *ci;
537
    cmTarget const* depender = this->Targets[i];
538
539

    // Describe the depender.
540
    e << "  \"" << depender->GetName() << "\" of type "
Nicolas Despres's avatar
Nicolas Despres committed
541
      << cmTarget::GetTargetTypeName(depender->GetType()) << "\n";
542
543

    // List its dependencies that are inside the component.
544
545
    EdgeList const& nl = this->InitialGraph[i];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
546
      {
547
548
      int j = *ni;
      if(cmap[j] == c)
549
        {
550
        cmTarget const* dependee = this->Targets[j];
551
552
        e << "    depends on \"" << dependee->GetName() << "\""
          << " (" << (ni->IsStrong()? "strong" : "weak") << ")\n";
553
554
555
        }
      }
    }
556
557
558
559
560
561
562
563
564
  if(strong)
    {
    // 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.";
    }
  else if(this->NoCycles)
565
566
567
568
569
570
571
572
573
    {
    e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
      << "cyclic dependencies are not allowed even among static libraries.";
    }
  else
    {
    e << "At least one of these targets is not a STATIC_LIBRARY.  "
      << "Cyclic dependencies are allowed only among static libraries.";
    }
574
575
576
577
  cmSystemTools::Error(e.str().c_str());
}

//----------------------------------------------------------------------------
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
bool
cmComputeTargetDepends
::IntraComponent(std::vector<int> const& cmap, int c, int i, int* head,
                 std::set<int>& emitted, std::set<int>& visited)
{
  if(!visited.insert(i).second)
    {
    // Cycle in utility depends!
    return false;
    }
  if(emitted.insert(i).second)
    {
    // Honor strong intra-component edges in the final order.
    EdgeList const& el = this->InitialGraph[i];
    for(EdgeList::const_iterator ei = el.begin(); ei != el.end(); ++ei)
      {
      int j = *ei;
      if(cmap[j] == c && ei->IsStrong())
        {
597
        this->FinalGraph[i].push_back(cmGraphEdge(j, true));
598
599
600
601
602
603
604
605
606
607
        if(!this->IntraComponent(cmap, c, j, head, emitted, visited))
          {
          return false;
          }
        }
      }

    // Prepend to a linear linked-list of intra-component edges.
    if(*head >= 0)
      {
608
      this->FinalGraph[i].push_back(cmGraphEdge(*head, false));
609
610
611
612
613
614
615
616
617
618
619
620
      }
    else
      {
      this->ComponentTail[c] = i;
      }
    *head = i;
    }
  return true;
}

//----------------------------------------------------------------------------
bool
621
622
cmComputeTargetDepends
::ComputeFinalDepends(cmComputeComponentGraph const& ccg)
623
{
624
625
626
627
628
629
630
  // 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());
631

632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
  // 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());
  for(int c=0; c < nc; ++c)
    {
    int head = -1;
    std::set<int> emitted;
    NodeList const& nl = components[c];
    for(NodeList::const_reverse_iterator ni = nl.rbegin();
        ni != nl.rend(); ++ni)
      {
      std::set<int> visited;
      if(!this->IntraComponent(cmap, c, *ni, &head, emitted, visited))
        {
        // Cycle in add_dependencies within component!
        this->ComplainAboutBadComponent(ccg, c, true);
        return false;
        }
      }
    this->ComponentHead[c] = head;
    }

656
  // Convert inter-component edges to connect component tails to heads.
657
658
  int n = static_cast<int>(cgraph.size());
  for(int depender_component=0; depender_component < n; ++depender_component)
659
    {
660
    int depender_component_tail = this->ComponentTail[depender_component];
661
662
    EdgeList const& nl = cgraph[depender_component];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
663
      {
664
      int dependee_component = *ni;
665
      int dependee_component_head = this->ComponentHead[dependee_component];
666
      this->FinalGraph[depender_component_tail]
667
        .push_back(cmGraphEdge(dependee_component_head, ni->IsStrong()));
668
669
      }
    }
670
  return true;
671
}