cmComputeTargetDepends.cxx 20.3 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
146
    }

  return true;
}

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

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

//----------------------------------------------------------------------------
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)
    {
    cmTargets& targets = lgens[i]->GetMakefile()->GetTargets();
    for(cmTargets::iterator ti = targets.begin(); ti != targets.end(); ++ti)
      {
      cmTarget* target = &ti->second;
      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.
188
  this->InitialGraph.resize(this->Targets.size());
189
190
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.
  cmTarget* depender = this->Targets[depender_index];

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

  // Loop over all utility dependencies.
250
  {
251
  std::set<cmStdString> const& tutils = depender->GetUtilities();
252
253
254
  std::set<cmStdString> emitted;
  // A target should not depend on itself.
  emitted.insert(depender->GetName());
255
256
257
258
259
260
  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)
      {
261
      this->AddTargetDepend(depender_index, util->c_str(), false);
262
263
      }
    }
264
  }
265
266
}

267
268
269
270
271
272
//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
                                                 cmTarget* dependee,
                                                 const char *config,
                                               std::set<cmStdString> &emitted)
{
273
  cmTarget* depender = this->Targets[depender_index];
274
  if(cmTarget::LinkInterface const* iface =
275
                                dependee->GetLinkInterface(config, depender))
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
    {
    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);
        }
      }
    }
}

//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
                                             const char* dependee_name,
                                             bool linking,
                                             std::set<cmStdString> &emitted)
{
  cmTarget* depender = this->Targets[depender_index];
  cmTarget* dependee =
    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);
      }
    }
}

325
326
//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
327
328
                                             const char* dependee_name,
                                             bool linking)
329
330
331
332
333
334
{
  // Get the depender.
  cmTarget* depender = this->Targets[depender_index];

  // Check the target's makefile first.
  cmTarget* dependee =
335
    depender->GetMakefile()->FindTargetToUse(dependee_name);
336

337
338
339
340
341
342
343
344
345
346
  // 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;
    }

347
  if(dependee)
348
    {
349
    this->AddTargetDepend(depender_index, dependee, linking);
350
    }
351
}
352

353
354
355
356
357
358
359
360
361
362
363
364
//----------------------------------------------------------------------------
void cmComputeTargetDepends::AddTargetDepend(int depender_index,
                                             cmTarget* dependee,
                                             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)
      {
365
366
367
368
369
      if(cmTarget* transitive_dependee =
         dependee->GetMakefile()->FindTargetToUse(i->c_str()))
        {
        this->AddTargetDepend(depender_index, transitive_dependee, false);
        }
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
      }
    }
  else
    {
    // Lookup the index for this target.  All targets should be known by
    // this point.
    std::map<cmTarget*, int>::const_iterator tii =
      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
}

//----------------------------------------------------------------------------
void
389
cmComputeTargetDepends::DisplayGraph(Graph const& graph, const char* name)
390
391
392
393
394
{
  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)
    {
395
    EdgeList const& nl = graph[depender_index];
396
397
398
    cmTarget* depender = this->Targets[depender_index];
    fprintf(stderr, "target %d is [%s]\n",
            depender_index, depender->GetName());
399
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
400
      {
401
      int dependee_index = *ni;
402
      cmTarget* dependee = this->Targets[dependee_index];
403
404
      fprintf(stderr, "  depends on target %d [%s] (%s)\n", dependee_index,
              dependee->GetName(), ni->IsStrong()? "strong" : "weak");
405
406
407
408
409
410
      }
    }
  fprintf(stderr, "\n");
}

//----------------------------------------------------------------------------
411
412
413
void
cmComputeTargetDepends
::DisplayComponents(cmComputeComponentGraph const& ccg)
414
415
{
  fprintf(stderr, "The strongly connected components are:\n");
416
417
  std::vector<NodeList> const& components = ccg.GetComponents();
  int n = static_cast<int>(components.size());
418
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
      {
424
      int i = *ni;
425
426
427
428
429
430
431
432
      fprintf(stderr, "  contains target %d [%s]\n",
              i, this->Targets[i]->GetName());
      }
    }
  fprintf(stderr, "\n");
}

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

    // Skip trivial components.
447
    if(nl.size() < 2)
448
449
450
451
      {
      continue;
      }

452
453
454
455
456
457
458
    // Immediately complain if no cycles are allowed at all.
    if(this->NoCycles)
      {
      this->ComplainAboutBadComponent(ccg, c);
      return false;
      }

459
    // Make sure the component is all STATIC_LIBRARY targets.
460
    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
461
      {
462
      if(this->Targets[*ni]->GetType() != cmTarget::STATIC_LIBRARY)
463
        {
464
        this->ComplainAboutBadComponent(ccg, c);
465
466
467
468
469
470
471
472
473
        return false;
        }
      }
    }
  return true;
}

//----------------------------------------------------------------------------
void
474
cmComputeTargetDepends
475
476
::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c,
                            bool strong)
477
478
479
480
481
{
  // Construct the error message.
  cmOStringStream e;
  e << "The inter-target dependency graph contains the following "
    << "strongly connected component (cycle):\n";
482
483
484
485
  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)
486
487
488
489
490
491
    {
    // Get the depender.
    int i = *ci;
    cmTarget* depender = this->Targets[i];

    // Describe the depender.
492
    e << "  \"" << depender->GetName() << "\" of type "
Nicolas Despres's avatar
Nicolas Despres committed
493
      << cmTarget::GetTargetTypeName(depender->GetType()) << "\n";
494
495

    // List its dependencies that are inside the component.
496
497
    EdgeList const& nl = this->InitialGraph[i];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
498
      {
499
500
      int j = *ni;
      if(cmap[j] == c)
501
502
        {
        cmTarget* dependee = this->Targets[j];
503
504
        e << "    depends on \"" << dependee->GetName() << "\""
          << " (" << (ni->IsStrong()? "strong" : "weak") << ")\n";
505
506
507
        }
      }
    }
508
509
510
511
512
513
514
515
516
  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)
517
518
519
520
521
522
523
524
525
    {
    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.";
    }
526
527
528
529
  cmSystemTools::Error(e.str().c_str());
}

//----------------------------------------------------------------------------
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
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())
        {
549
        this->FinalGraph[i].push_back(cmGraphEdge(j, true));
550
551
552
553
554
555
556
557
558
559
        if(!this->IntraComponent(cmap, c, j, head, emitted, visited))
          {
          return false;
          }
        }
      }

    // Prepend to a linear linked-list of intra-component edges.
    if(*head >= 0)
      {
560
      this->FinalGraph[i].push_back(cmGraphEdge(*head, false));
561
562
563
564
565
566
567
568
569
570
571
572
      }
    else
      {
      this->ComponentTail[c] = i;
      }
    *head = i;
    }
  return true;
}

//----------------------------------------------------------------------------
bool
573
574
cmComputeTargetDepends
::ComputeFinalDepends(cmComputeComponentGraph const& ccg)
575
{
576
577
578
579
580
581
582
  // 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());
583

584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
  // 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;
    }

608
  // Convert inter-component edges to connect component tails to heads.
609
610
  int n = static_cast<int>(cgraph.size());
  for(int depender_component=0; depender_component < n; ++depender_component)
611
    {
612
    int depender_component_tail = this->ComponentTail[depender_component];
613
614
    EdgeList const& nl = cgraph[depender_component];
    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
615
      {
616
      int dependee_component = *ni;
617
      int dependee_component_head = this->ComponentHead[dependee_component];
618
      this->FinalGraph[depender_component_tail]
619
        .push_back(cmGraphEdge(dependee_component_head, ni->IsStrong()));
620
621
      }
    }
622
  return true;
623
}