cmComputeLinkDepends.cxx 29.9 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 "cmComputeLinkDepends.h"

5
#include "cmAlgorithms.h"
6
#include "cmComputeComponentGraph.h"
7
#include "cmGeneratorTarget.h"
8
#include "cmGlobalGenerator.h"
9
#include "cmLocalGenerator.h"
10
#include "cmMakefile.h"
11
#include "cmStateTypes.h"
12
#include "cmSystemTools.h"
13
#include "cmTarget.h"
14
#include "cmake.h"
15

16
#include <algorithm>
17
#include <assert.h>
18 19 20 21 22
#include <iterator>
#include <sstream>
#include <stdio.h>
#include <string.h>
#include <utility>
23

24 25 26 27 28
/*

This file computes an ordered list of link items to use when linking a
single target in one configuration.  Each link item is identified by
the string naming it.  A graph of dependencies is created in which
29
each node corresponds to one item and directed edges lead from nodes to
30
those which must *follow* them on the link line.  For example, the
31 32
graph

33
  A -> B -> C
34 35 36 37 38 39 40 41 42 43

will lead to the link line order

  A B C

The set of items placed in the graph is formed with a breadth-first
search of the link dependencies starting from the main target.

There are two types of items: those with known direct dependencies and
those without known dependencies.  We will call the two types "known
44
items" and "unknown items", respectively.  Known items are those whose
45 46
names correspond to targets (built or imported) and those for which an
old-style <item>_LIB_DEPENDS variable is defined.  All other items are
47 48 49
unknown and we must infer dependencies for them.  For items that look
like flags (beginning with '-') we trivially infer no dependencies,
and do not include them in the dependencies of other items.
50 51 52 53 54 55 56 57 58 59 60 61

Known items have dependency lists ordered based on how the user
specified them.  We can use this order to infer potential dependencies
of unknown items.  For example, if link items A and B are unknown and
items X and Y are known, then we might have the following dependency
lists:

  X: Y A B
  Y: A B

The explicitly known dependencies form graph edges

62
  X -> Y  ,  X -> A  ,  X -> B  ,  Y -> A  ,  Y -> B
63 64 65

We can also infer the edge

66
  A -> B
67 68 69 70

because *every* time A appears B is seen on its right.  We do not know
whether A really needs symbols from B to link, but it *might* so we
must preserve their order.  This is the case also for the following
71
explicit lists:
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

  X: A B Y
  Y: A B

Here, A is followed by the set {B,Y} in one list, and {B} in the other
list.  The intersection of these sets is {B}, so we can infer that A
depends on at most B.  Meanwhile B is followed by the set {Y} in one
list and {} in the other.  The intersection is {} so we can infer that
B has no dependencies.

Let's make a more complex example by adding unknown item C and
considering these dependency lists:

  X: A B Y C
  Y: A C B

The explicit edges are

90
  X -> Y  ,  X -> A  ,  X -> B  ,  X -> C  ,  Y -> A  ,  Y -> B  ,  Y -> C
91 92 93 94

For the unknown items, we infer dependencies by looking at the
"follow" sets:

95
  A: intersect( {B,Y,C} , {C,B} ) = {B,C} ; infer edges  A -> B  ,  A -> C
96 97 98
  B: intersect( {Y,C}   , {}    ) = {}    ; infer no edges
  C: intersect( {}      , {B}   ) = {}    ; infer no edges

99 100 101
Note that targets are never inferred as dependees because outside
libraries should not depend on them.

102 103
------------------------------------------------------------------------------

104 105 106 107 108 109 110 111 112 113 114
The initial exploration of dependencies using a BFS associates an
integer index with each link item.  When the graph is built outgoing
edges are sorted by this index.

After the initial exploration of the link interface tree, any
transitive (dependent) shared libraries that were encountered and not
included in the interface are processed in their own BFS.  This BFS
follows only the dependent library lists and not the link interfaces.
They are added to the link items with a mark indicating that the are
transitive dependencies.  Then cmComputeLinkInformation deals with
them on a per-platform basis.
115

116 117
The complete graph formed from all known and inferred dependencies may
not be acyclic, so an acyclic version must be created.
118 119 120 121
The original graph is converted to a directed acyclic graph in which
each node corresponds to a strongly connected component of the
original graph.  For example, the dependency graph

122
  X -> A -> B -> C -> A -> Y
123

124 125
contains strongly connected components {X}, {A,B,C}, and {Y}.  The
implied directed acyclic graph (DAG) is
126

127
  {X} -> {A,B,C} -> {Y}
128

129 130 131 132 133
We then compute a topological order for the DAG nodes to serve as a
reference for satisfying dependencies efficiently.  We perform the DFS
in reverse order and assign topological order indices counting down so
that the result is as close to the original BFS order as possible
without violating dependencies.
134 135

------------------------------------------------------------------------------
136

137 138 139 140 141 142 143 144 145 146 147 148 149 150 151
The final link entry order is constructed as follows.  We first walk
through and emit the *original* link line as specified by the user.
As each item is emitted, a set of pending nodes in the component DAG
is maintained.  When a pending component has been completely seen, it
is removed from the pending set and its dependencies (following edges
of the DAG) are added.  A trivial component (those with one item) is
complete as soon as its item is seen.  A non-trivial component (one
with more than one item; assumed to be static libraries) is complete
when *all* its entries have been seen *twice* (all entries seen once,
then all entries seen again, not just each entry twice).  A pending
component tracks which items have been seen and a count of how many
times the component needs to be seen (once for trivial components,
twice for non-trivial).  If at any time another component finishes and
re-adds an already pending component, the pending component is reset
so that it needs to be seen in its entirety again.  This ensures that
152
all dependencies of a component are satisfied no matter where it
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
appears.

After the original link line has been completed, we append to it the
remaining pending components and their dependencies.  This is done by
repeatedly emitting the first item from the first pending component
and following the same update rules as when traversing the original
link line.  Since the pending components are kept in topological order
they are emitted with minimal repeats (we do not want to emit a
component just to have it added again when another component is
completed later).  This process continues until no pending components
remain.  We know it will terminate because the component graph is
guaranteed to be acyclic.

The final list of items produced by this procedure consists of the
original user link line followed by minimal additional items needed to
168 169
satisfy dependencies.  The final list is then filtered to de-duplicate
items that we know the linker will re-use automatically (shared libs).
170

171 172
*/

173 174
cmComputeLinkDepends::cmComputeLinkDepends(const cmGeneratorTarget* target,
                                           const std::string& config)
175 176 177
{
  // Store context information.
  this->Target = target;
178
  this->Makefile = this->Target->Target->GetMakefile();
179
  this->GlobalGenerator =
180
    this->Target->GetLocalGenerator()->GetGlobalGenerator();
181
  this->CMakeInstance = this->GlobalGenerator->GetCMakeInstance();
182 183

  // The configuration being linked.
184
  this->HasConfig = !config.empty();
185
  this->Config = (this->HasConfig) ? config : std::string();
186 187 188
  std::vector<std::string> debugConfigs =
    this->Makefile->GetCMakeInstance()->GetDebugConfigs();
  this->LinkType = CMP0003_ComputeLinkType(this->Config, debugConfigs);
189 190 191

  // Enable debug mode if requested.
  this->DebugMode = this->Makefile->IsOn("CMAKE_LINK_DEPENDS_DEBUG_MODE");
192 193 194

  // Assume no compatibility until set.
  this->OldLinkDirMode = false;
195 196

  // No computation has been done.
Daniel Pfeifer's avatar
Daniel Pfeifer committed
197
  this->CCG = CM_NULLPTR;
198 199 200 201
}

cmComputeLinkDepends::~cmComputeLinkDepends()
{
202
  cmDeleteAll(this->InferredDependSets);
203
  delete this->CCG;
204 205
}

206 207 208 209 210
void cmComputeLinkDepends::SetOldLinkDirMode(bool b)
{
  this->OldLinkDirMode = b;
}

211 212 213 214
std::vector<cmComputeLinkDepends::LinkEntry> const&
cmComputeLinkDepends::Compute()
{
  // Follow the link dependencies of the target to be linked.
215
  this->AddDirectLinkEntries();
216 217

  // Complete the breadth-first search of dependencies.
218
  while (!this->BFSQueue.empty()) {
219 220 221 222 223 224
    // Get the next entry.
    BFSEntry qe = this->BFSQueue.front();
    this->BFSQueue.pop();

    // Follow the entry's dependencies.
    this->FollowLinkEntry(qe);
225
  }
226

227
  // Complete the search of shared library dependencies.
228
  while (!this->SharedDepQueue.empty()) {
229 230 231
    // Handle the next entry.
    this->HandleSharedDependency(this->SharedDepQueue.front());
    this->SharedDepQueue.pop();
232
  }
233

234 235 236
  // Infer dependencies of targets for which they were not known.
  this->InferDependencies();

237 238 239
  // Cleanup the constraint graph.
  this->CleanConstraintGraph();

240
  // Display the constraint graph.
241 242 243
  if (this->DebugMode) {
    fprintf(stderr, "---------------------------------------"
                    "---------------------------------------\n");
244
    fprintf(stderr, "Link dependency analysis for target %s, config %s\n",
245
            this->Target->GetName().c_str(),
246
            this->HasConfig ? this->Config.c_str() : "noconfig");
247
    this->DisplayConstraintGraph();
248
  }
249

250
  // Compute the final ordering.
251
  this->OrderLinkEntires();
252 253

  // Compute the final set of link entries.
254 255
  // Iterate in reverse order so we can keep only the last occurrence
  // of a shared library.
256
  std::set<int> emmitted;
257 258 259 260
  for (std::vector<int>::const_reverse_iterator
         li = this->FinalLinkOrder.rbegin(),
         le = this->FinalLinkOrder.rend();
       li != le; ++li) {
261 262
    int i = *li;
    LinkEntry const& e = this->EntryList[i];
263
    cmGeneratorTarget const* t = e.Target;
264
    // Entries that we know the linker will re-use do not need to be repeated.
265
    bool uniquify = t && t->GetType() == cmStateEnums::SHARED_LIBRARY;
266
    if (!uniquify || emmitted.insert(i).second) {
267
      this->FinalLinkEntries.push_back(e);
268
    }
269
  }
270 271
  // Reverse the resulting order since we iterated in reverse.
  std::reverse(this->FinalLinkEntries.begin(), this->FinalLinkEntries.end());
272 273

  // Display the final set.
274
  if (this->DebugMode) {
275
    this->DisplayFinalEntries();
276
  }
277 278 279 280

  return this->FinalLinkEntries;
}

281 282
std::map<std::string, int>::iterator cmComputeLinkDepends::AllocateLinkEntry(
  std::string const& item)
283
{
284 285 286 287
  std::map<std::string, int>::value_type index_entry(
    item, static_cast<int>(this->EntryList.size()));
  std::map<std::string, int>::iterator lei =
    this->LinkEntryIndex.insert(index_entry).first;
288
  this->EntryList.push_back(LinkEntry());
Daniel Pfeifer's avatar
Daniel Pfeifer committed
289
  this->InferredDependSets.push_back(CM_NULLPTR);
290
  this->EntryConstraintGraph.push_back(EdgeList());
291 292 293
  return lei;
}

294
int cmComputeLinkDepends::AddLinkEntry(cmLinkItem const& item)
295 296
{
  // Check if the item entry has already been added.
297
  std::map<std::string, int>::iterator lei = this->LinkEntryIndex.find(item);
298
  if (lei != this->LinkEntryIndex.end()) {
299 300
    // Yes.  We do not need to follow the item's dependencies again.
    return lei->second;
301
  }
302 303

  // Allocate a spot for the item entry.
304
  lei = this->AllocateLinkEntry(item);
305 306 307 308 309

  // Initialize the item entry.
  int index = lei->second;
  LinkEntry& entry = this->EntryList[index];
  entry.Item = item;
310
  entry.Target = item.Target;
311 312
  entry.IsFlag = (!entry.Target && item[0] == '-' && item[1] != 'l' &&
                  item.substr(0, 10) != "-framework");
313 314

  // If the item has dependencies queue it to follow them.
315
  if (entry.Target) {
316
    // Target dependencies are always known.  Follow them.
Daniel Pfeifer's avatar
Daniel Pfeifer committed
317
    BFSEntry qe = { index, CM_NULLPTR };
318
    this->BFSQueue.push(qe);
319
  } else {
320 321 322
    // Look for an old-style <item>_LIB_DEPENDS variable.
    std::string var = entry.Item;
    var += "_LIB_DEPENDS";
323
    if (const char* val = this->Makefile->GetDefinition(var)) {
324
      // The item dependencies are known.  Follow them.
325
      BFSEntry qe = { index, val };
326
      this->BFSQueue.push(qe);
327
    } else if (!entry.IsFlag) {
328 329 330
      // The item dependencies are not known.  We need to infer them.
      this->InferredDependSets[index] = new DependSetList;
    }
331
  }
332 333 334 335 336 337 338 339 340 341 342

  return index;
}

void cmComputeLinkDepends::FollowLinkEntry(BFSEntry const& qe)
{
  // Get this entry representation.
  int depender_index = qe.Index;
  LinkEntry const& entry = this->EntryList[depender_index];

  // Follow the item's dependencies.
343
  if (entry.Target) {
344
    // Follow the target dependencies.
345 346
    if (cmLinkInterface const* iface =
          entry.Target->GetLinkInterface(this->Config, this->Target)) {
347
      const bool isIface =
348
        entry.Target->GetType() == cmStateEnums::INTERFACE_LIBRARY;
349
      // This target provides its own link interface information.
Brad King's avatar
Brad King committed
350
      this->AddLinkEntries(depender_index, iface->Libraries);
351

352
      if (isIface) {
353
        return;
354
      }
355

356
      // Handle dependent shared libraries.
357
      this->FollowSharedDeps(depender_index, iface);
358 359

      // Support for CMP0003.
360 361 362
      for (std::vector<cmLinkItem>::const_iterator oi =
             iface->WrongConfigLibraries.begin();
           oi != iface->WrongConfigLibraries.end(); ++oi) {
363
        this->CheckWrongConfigItem(*oi);
364
      }
365
    }
366
  } else {
367 368
    // Follow the old-style dependency list.
    this->AddVarLinkEntries(depender_index, qe.LibDepends);
369
  }
370 371
}

372 373 374
void cmComputeLinkDepends::FollowSharedDeps(int depender_index,
                                            cmLinkInterface const* iface,
                                            bool follow_interface)
375 376
{
  // Follow dependencies if we have not followed them already.
377 378
  if (this->SharedDepFollowed.insert(depender_index).second) {
    if (follow_interface) {
379 380
      this->QueueSharedDependencies(depender_index, iface->Libraries);
    }
381 382
    this->QueueSharedDependencies(depender_index, iface->SharedDeps);
  }
383 384
}

385 386
void cmComputeLinkDepends::QueueSharedDependencies(
  int depender_index, std::vector<cmLinkItem> const& deps)
387
{
388 389
  for (std::vector<cmLinkItem>::const_iterator li = deps.begin();
       li != deps.end(); ++li) {
390 391 392 393
    SharedDepEntry qe;
    qe.Item = *li;
    qe.DependerIndex = depender_index;
    this->SharedDepQueue.push(qe);
394
  }
395 396 397 398 399
}

void cmComputeLinkDepends::HandleSharedDependency(SharedDepEntry const& dep)
{
  // Check if the target already has an entry.
400
  std::map<std::string, int>::iterator lei =
401
    this->LinkEntryIndex.find(dep.Item);
402
  if (lei == this->LinkEntryIndex.end()) {
403 404 405 406 407 408
    // Allocate a spot for the item entry.
    lei = this->AllocateLinkEntry(dep.Item);

    // Initialize the item entry.
    LinkEntry& entry = this->EntryList[lei->second];
    entry.Item = dep.Item;
409
    entry.Target = dep.Item.Target;
410 411 412 413 414

    // This item was added specifically because it is a dependent
    // shared library.  It may get special treatment
    // in cmComputeLinkInformation.
    entry.IsSharedDep = true;
415
  }
416 417 418 419 420

  // Get the link entry for this target.
  int index = lei->second;
  LinkEntry& entry = this->EntryList[index];

421 422 423
  // This shared library dependency must follow the item that listed
  // it.
  this->EntryConstraintGraph[dep.DependerIndex].push_back(index);
424 425

  // Target items may have their own dependencies.
426 427 428
  if (entry.Target) {
    if (cmLinkInterface const* iface =
          entry.Target->GetLinkInterface(this->Config, this->Target)) {
429
      // Follow public and private dependencies transitively.
430
      this->FollowSharedDeps(index, iface, true);
431
    }
432
  }
433 434
}

435 436 437 438 439 440 441 442 443
void cmComputeLinkDepends::AddVarLinkEntries(int depender_index,
                                             const char* value)
{
  // This is called to add the dependencies named by
  // <item>_LIB_DEPENDS.  The variable contains a semicolon-separated
  // list.  The list contains link-type;item pairs and just items.
  std::vector<std::string> deplist;
  cmSystemTools::ExpandListArgument(value, deplist);

444
  // Look for entries meant for this configuration.
445
  std::vector<cmLinkItem> actual_libs;
446
  cmTargetLinkLibraryType llt = GENERAL_LibraryType;
447
  bool haveLLT = false;
448 449 450
  for (std::vector<std::string>::const_iterator di = deplist.begin();
       di != deplist.end(); ++di) {
    if (*di == "debug") {
451
      llt = DEBUG_LibraryType;
452
      haveLLT = true;
453
    } else if (*di == "optimized") {
454
      llt = OPTIMIZED_LibraryType;
455
      haveLLT = true;
456
    } else if (*di == "general") {
457
      llt = GENERAL_LibraryType;
458
      haveLLT = true;
459
    } else if (!di->empty()) {
460 461 462 463 464
      // If no explicit link type was given prior to this entry then
      // check if the entry has its own link type variable.  This is
      // needed for compatibility with dependency files generated by
      // the export_library_dependencies command from CMake 2.4 and
      // lower.
465
      if (!haveLLT) {
466 467
        std::string var = *di;
        var += "_LINK_TYPE";
468 469
        if (const char* val = this->Makefile->GetDefinition(var)) {
          if (strcmp(val, "debug") == 0) {
470
            llt = DEBUG_LibraryType;
471
          } else if (strcmp(val, "optimized") == 0) {
472
            llt = OPTIMIZED_LibraryType;
473 474
          }
        }
475
      }
476 477

      // If the library is meant for this link type then use it.
478
      if (llt == GENERAL_LibraryType || llt == this->LinkType) {
479 480
        cmLinkItem item(*di, this->FindTargetToLink(depender_index, *di));
        actual_libs.push_back(item);
481
      } else if (this->OldLinkDirMode) {
482 483
        cmLinkItem item(*di, this->FindTargetToLink(depender_index, *di));
        this->CheckWrongConfigItem(item);
484
      }
485 486

      // Reset the link type until another explicit type is given.
487
      llt = GENERAL_LibraryType;
488
      haveLLT = false;
489
    }
490
  }
491 492

  // Add the entries from this list.
493
  this->AddLinkEntries(depender_index, actual_libs);
494 495
}

496
void cmComputeLinkDepends::AddDirectLinkEntries()
497
{
498
  // Add direct link dependencies in this configuration.
499
  cmLinkImplementation const* impl =
500
    this->Target->GetLinkImplementation(this->Config);
501
  this->AddLinkEntries(-1, impl->Libraries);
502 503 504
  for (std::vector<cmLinkItem>::const_iterator wi =
         impl->WrongConfigLibraries.begin();
       wi != impl->WrongConfigLibraries.end(); ++wi) {
505
    this->CheckWrongConfigItem(*wi);
506
  }
507 508
}

509
template <typename T>
510 511
void cmComputeLinkDepends::AddLinkEntries(int depender_index,
                                          std::vector<T> const& libs)
512
{
513 514 515
  // Track inferred dependency sets implied by this list.
  std::map<int, DependSet> dependSets;

516
  // Loop over the libraries linked directly by the depender.
517 518
  for (typename std::vector<T>::const_iterator li = libs.begin();
       li != libs.end(); ++li) {
519 520
    // Skip entries that will resolve to the target getting linked or
    // are empty.
521
    cmLinkItem const& item = *li;
522
    if (item == this->Target->GetName() || item.empty()) {
523
      continue;
524
    }
525 526

    // Add a link entry for this item.
527
    int dependee_index = this->AddLinkEntry(*li);
528

529
    // The dependee must come after the depender.
530
    if (depender_index >= 0) {
531
      this->EntryConstraintGraph[depender_index].push_back(dependee_index);
532
    } else {
533 534
      // This is a direct dependency of the target being linked.
      this->OriginalEntries.push_back(dependee_index);
535
    }
536 537

    // Update the inferred dependencies for earlier items.
538 539
    for (std::map<int, DependSet>::iterator dsi = dependSets.begin();
         dsi != dependSets.end(); ++dsi) {
540 541 542 543
      // Add this item to the inferred dependencies of other items.
      // Target items are never inferred dependees because unknown
      // items are outside libraries that should not be depending on
      // targets.
544 545 546
      if (!this->EntryList[dependee_index].Target &&
          !this->EntryList[dependee_index].IsFlag &&
          dependee_index != dsi->first) {
547 548
        dsi->second.insert(dependee_index);
      }
549
    }
550 551

    // If this item needs to have dependencies inferred, do so.
552
    if (this->InferredDependSets[dependee_index]) {
553 554 555
      // Make sure an entry exists to hold the set for the item.
      dependSets[dependee_index];
    }
556
  }
557 558

  // Store the inferred dependency sets discovered for this list.
559 560
  for (std::map<int, DependSet>::iterator dsi = dependSets.begin();
       dsi != dependSets.end(); ++dsi) {
561
    this->InferredDependSets[dsi->first]->push_back(dsi->second);
562
  }
563 564
}

565 566
cmGeneratorTarget const* cmComputeLinkDepends::FindTargetToLink(
  int depender_index, const std::string& name)
567
{
568
  // Look for a target in the scope of the depender.
569
  cmGeneratorTarget const* from = this->Target;
570 571 572
  if (depender_index >= 0) {
    if (cmGeneratorTarget const* depender =
          this->EntryList[depender_index].Target) {
573
      from = depender;
574
    }
575
  }
576
  return from->FindTargetToLink(name);
577 578
}

579 580 581 582 583
void cmComputeLinkDepends::InferDependencies()
{
  // The inferred dependency sets for each item list the possible
  // dependencies.  The intersection of the sets for one item form its
  // inferred dependencies.
584 585
  for (unsigned int depender_index = 0;
       depender_index < this->InferredDependSets.size(); ++depender_index) {
586 587 588
    // Skip items for which dependencies do not need to be inferred or
    // for which the inferred dependency sets are empty.
    DependSetList* sets = this->InferredDependSets[depender_index];
589
    if (!sets || sets->empty()) {
590
      continue;
591
    }
592 593 594 595

    // Intersect the sets for this item.
    DependSetList::const_iterator i = sets->begin();
    DependSet common = *i;
596
    for (++i; i != sets->end(); ++i) {
597
      DependSet intersection;
598 599
      std::set_intersection(common.begin(), common.end(), i->begin(), i->end(),
                            std::inserter(intersection, intersection.begin()));
600
      common = intersection;
601
    }
602 603

    // Add the inferred dependencies to the graph.
604 605
    cmGraphEdgeList& edges = this->EntryConstraintGraph[depender_index];
    edges.insert(edges.end(), common.begin(), common.end());
606
  }
607 608
}

609 610
void cmComputeLinkDepends::CleanConstraintGraph()
{
611 612
  for (Graph::iterator i = this->EntryConstraintGraph.begin();
       i != this->EntryConstraintGraph.end(); ++i) {
613 614
    // Sort the outgoing edges for each graph node so that the
    // original order will be preserved as much as possible.
Stephen Kelly's avatar
Stephen Kelly committed
615
    std::sort(i->begin(), i->end());
616 617

    // Make the edge list unique.
618
    i->erase(std::unique(i->begin(), i->end()), i->end());
619
  }
620 621
}

622 623
void cmComputeLinkDepends::DisplayConstraintGraph()
{
624
  // Display the graph nodes and their edges.
625
  std::ostringstream e;
626
  for (unsigned int i = 0; i < this->EntryConstraintGraph.size(); ++i) {
627
    EdgeList const& nl = this->EntryConstraintGraph[i];
628
    e << "item " << i << " is [" << this->EntryList[i].Item << "]\n";
629
    e << cmWrap("  item ", nl, " must follow it", "\n") << "\n";
630
  }
631 632 633 634 635
  fprintf(stderr, "%s\n", e.str().c_str());
}

void cmComputeLinkDepends::OrderLinkEntires()
{
636 637 638 639 640
  // Compute the DAG of strongly connected components.  The algorithm
  // used by cmComputeComponentGraph should identify the components in
  // the same order in which the items were originally discovered in
  // the BFS.  This should preserve the original order when no
  // constraints disallow it.
641 642 643 644 645 646 647 648 649 650 651 652
  this->CCG = new cmComputeComponentGraph(this->EntryConstraintGraph);

  // The component graph is guaranteed to be acyclic.  Start a DFS
  // from every entry to compute a topological order for the
  // components.
  Graph const& cgraph = this->CCG->GetComponentGraph();
  int n = static_cast<int>(cgraph.size());
  this->ComponentVisited.resize(cgraph.size(), 0);
  this->ComponentOrder.resize(cgraph.size(), n);
  this->ComponentOrderId = n;
  // Run in reverse order so the topological order will preserve the
  // original order where there are no constraints.
653
  for (int c = n - 1; c >= 0; --c) {
654
    this->VisitComponent(c);
655
  }
656 657

  // Display the component graph.
658
  if (this->DebugMode) {
659
    this->DisplayComponents();
660
  }
661

662
  // Start with the original link line.
663 664
  for (std::vector<int>::const_iterator i = this->OriginalEntries.begin();
       i != this->OriginalEntries.end(); ++i) {
665
    this->VisitEntry(*i);
666
  }
667

668 669
  // Now explore anything left pending.  Since the component graph is
  // guaranteed to be acyclic we know this will terminate.
670
  while (!this->PendingComponents.empty()) {
671 672 673 674 675 676
    // Visit one entry from the first pending component.  The visit
    // logic will update the pending components accordingly.  Since
    // the pending components are kept in topological order this will
    // not repeat one.
    int e = *this->PendingComponents.begin()->second.Entries.begin();
    this->VisitEntry(e);
677
  }
678 679
}

680
void cmComputeLinkDepends::DisplayComponents()
681
{
682
  fprintf(stderr, "The strongly connected components are:\n");
683
  std::vector<NodeList> const& components = this->CCG->GetComponents();
684
  for (unsigned int c = 0; c < components.size(); ++c) {
685 686
    fprintf(stderr, "Component (%u):\n", c);
    NodeList const& nl = components[c];
687
    for (NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) {
688
      int i = *ni;
689 690
      fprintf(stderr, "  item %d [%s]\n", i, this->EntryList[i].Item.c_str());
    }
691
    EdgeList const& ol = this->CCG->GetComponentGraphEdges(c);
692
    for (EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi) {
693 694
      int i = *oi;
      fprintf(stderr, "  followed by Component (%d)\n", i);
695
    }
696 697
    fprintf(stderr, "  topo order index %d\n", this->ComponentOrder[c]);
  }
698 699 700
  fprintf(stderr, "\n");
}

701
void cmComputeLinkDepends::VisitComponent(unsigned int c)
702 703
{
  // Check if the node has already been visited.
704
  if (this->ComponentVisited[c]) {
705
    return;
706
  }
707

708 709
  // We are now visiting this component so mark it.
  this->ComponentVisited[c] = 1;
710

711
  // Visit the neighbors of the component first.
712 713
  // Run in reverse order so the topological order will preserve the
  // original order where there are no constraints.
714
  EdgeList const& nl = this->CCG->GetComponentGraphEdges(c);
715 716
  for (EdgeList::const_reverse_iterator ni = nl.rbegin(); ni != nl.rend();
       ++ni) {
717
    this->VisitComponent(*ni);
718
  }
719

720 721
  // Assign an ordering id to this component.
  this->ComponentOrder[c] = --this->ComponentOrderId;
722 723
}

724
void cmComputeLinkDepends::VisitEntry(int index)
725
{
726 727 728 729 730 731 732 733
  // Include this entry on the link line.
  this->FinalLinkOrder.push_back(index);

  // This entry has now been seen.  Update its component.
  bool completed = false;
  int component = this->CCG->GetComponentMap()[index];
  std::map<int, PendingComponent>::iterator mi =
    this->PendingComponents.find(this->ComponentOrder[component]);
734
  if (mi != this->PendingComponents.end()) {
735 736 737 738 739
    // The entry is in an already pending component.
    PendingComponent& pc = mi->second;

    // Remove the entry from those pending in its component.
    pc.Entries.erase(index);
740
    if (pc.Entries.empty()) {
741 742
      // The complete component has been seen since it was last needed.
      --pc.Count;
743

744
      if (pc.Count == 0) {
745 746 747
        // The component has been completed.
        this->PendingComponents.erase(mi);
        completed = true;
748
      } else {
749 750 751 752 753 754
        // The whole component needs to be seen again.
        NodeList const& nl = this->CCG->GetComponent(component);
        assert(nl.size() > 1);
        pc.Entries.insert(nl.begin(), nl.end());
      }
    }
755
  } else {
756 757
    // The entry is not in an already pending component.
    NodeList const& nl = this->CCG->GetComponent(component);
758
    if (nl.size() > 1) {
759 760 761 762 763
      // This is a non-trivial component.  It is now pending.
      PendingComponent& pc = this->MakePendingComponent(component);

      // The starting entry has already been seen.
      pc.Entries.erase(index);
764
    } else {
765 766
      // This is a trivial component, so it is already complete.
      completed = true;
767
    }
768
  }
769

770 771
  // If the entry completed a component, the component's dependencies
  // are now pending.
772
  if (completed) {
773
    EdgeList const& ol = this->CCG->GetComponentGraphEdges(component);
774
    for (EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi) {
775 776 777
      // This entire component is now pending no matter whether it has
      // been partially seen already.
      this->MakePendingComponent(*oi);
778
    }
779
  }
780 781 782 783 784 785 786 787 788 789 790
}

cmComputeLinkDepends::PendingComponent&
cmComputeLinkDepends::MakePendingComponent(unsigned int component)
{
  // Create an entry (in topological order) for the component.
  PendingComponent& pc =
    this->PendingComponents[this->ComponentOrder[component]];
  pc.Id = component;
  NodeList const& nl = this->CCG->GetComponent(component);

791
  if (nl.size() == 1) {
792 793
    // Trivial components need be seen only once.
    pc.Count = 1;
794
  } else {
795 796 797 798 799 800 801 802 803 804 805 806
    // This is a non-trivial strongly connected component of the
    // original graph.  It consists of two or more libraries
    // (archives) that mutually require objects from one another.  In
    // the worst case we may have to repeat the list of libraries as
    // many times as there are object files in the biggest archive.
    // For now we just list them twice.
    //
    // The list of items in the component has been sorted by the order
    // of discovery in the original BFS of dependencies.  This has the
    // advantage that the item directly linked by a target requiring
    // this component will come first which minimizes the number of
    // repeats needed.
807
    pc.Count = this->ComputeComponentCount(nl);
808
  }
809 810 811 812 813

  // Store the entries to be seen.
  pc.Entries.insert(nl.begin(), nl.end());

  return pc;
814 815
}

816 817
int cmComputeLinkDepends::ComputeComponentCount(NodeList const& nl)
{
818
  unsigned int count = 2;
819 820 821 822 823
  for (NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) {
    if (cmGeneratorTarget const* target = this->EntryList[*ni].Target) {
      if (cmLinkInterface const* iface =
            target->GetLinkInterface(this->Config, this->Target)) {
        if (iface->Multiplicity > count) {
824 825 826 827
          count = iface->Multiplicity;
        }
      }
    }
828
  }
829 830 831
  return count;
}

832 833
void cmComputeLinkDepends::DisplayFinalEntries()
{
834
  fprintf(stderr, "target [%s] links to:\n", this->Target->GetName().c_str());
835 836 837 838
  for (std::vector<LinkEntry>::const_iterator lei =
         this->FinalLinkEntries.begin();
       lei != this->FinalLinkEntries.end(); ++lei) {
    if (lei->Target) {
839
      fprintf(stderr, "  target [%s]\n", lei->Target->GetName().c_str());
840
    } else {
841 842
      fprintf(stderr, "  item [%s]\n", lei->Item.c_str());
    }
843
  }
844 845
  fprintf(stderr, "\n");
}
846

847
void cmComputeLinkDepends::CheckWrongConfigItem(cmLinkItem const& item)
848
{
849
  if (!this->OldLinkDirMode) {
850
    return;
851
  }
852 853 854 855

  // For CMake 2.4 bug-compatibility we need to consider the output
  // directories of targets linked in another configuration as link
  // directories.
856
  if (item.Target && !item.Target->IsImported()) {
857
    this->OldWrongConfigItems.insert(item.Target);
858
  }
859
}