~dynamite-a-d/ubuntu/precise/cmake/fix-for-972419
» Revision
50
: .pc/spelling_formatting_fixes.diff/Source/cmComputeLinkDepends.cxx
« back to all changes in this revision
Viewing changes to .pc/spelling_formatting_fixes.diff/Source/cmComputeLinkDepends.cxx
- browse files at revision 50
- compare with another revision
- download diff
- download tarball
- view history from revision 50
- Committer: Bazaar Package Importer
- Author(s): Felix Geyer
- Date: 2011-07-11 00:51:46 UTC
- mfrom: (3.1.24 sid)
- Revision ID: james.westby@ubuntu.com-20110711005146-v81594j17p4gqjrd
Tags: 2.8.5-1ubuntu1
Disable CTestTestUpload test as it requires internet access.
- files added:
- .pc/multiarch_lib_dirs_should_be_implicit.diff
- .pc/multiarch_lib_dirs_should_be_implicit.diff/Source
- files removed:
- .pc/screen-256color-bce.diff
- .pc/screen-256color-bce.diff/Source
- .pc/screen-256color-bce.diff/Source/kwsys
- .pc/spelling_formatting_fixes.diff
- .pc/spelling_formatting_fixes.diff/Modules
- .pc/spelling_formatting_fixes.diff/Source
- files modified:
- .pc/FindBoost_add_-lpthread_#563479.diff/Modules/FindBoost.cmake
added
removed
.pc/spelling_formatting_fixes.diff/Source/cmComputeLinkDepends.cxx
1
/*============================================================================
2
CMake - Cross Platform Makefile Generator
3
Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
4
5
Distributed under the OSI-approved BSD License (the "License");
6
see accompanying file Copyright.txt for details.
7
8
This software is distributed WITHOUT ANY WARRANTY; without even the
9
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10
See the License for more information.
11
============================================================================*/
12
#include "cmComputeLinkDepends.h"
13
14
#include "cmComputeComponentGraph.h"
15
#include "cmGlobalGenerator.h"
16
#include "cmLocalGenerator.h"
17
#include "cmMakefile.h"
18
#include "cmTarget.h"
19
#include "cmake.h"
20
21
#include <cmsys/stl/algorithm>
22
23
#include <assert.h>
24
25
/*
26
27
This file computes an ordered list of link items to use when linking a
28
single target in one configuration. Each link item is identified by
29
the string naming it. A graph of dependencies is created in which
30
each node corresponds to one item and directed eges lead from nodes to
31
those which must *follow* them on the link line. For example, the
32
graph
33
34
A -> B -> C
35
36
will lead to the link line order
37
38
A B C
39
40
The set of items placed in the graph is formed with a breadth-first
41
search of the link dependencies starting from the main target.
42
43
There are two types of items: those with known direct dependencies and
44
those without known dependencies. We will call the two types "known
45
items" and "unknown items", respecitvely. Known items are those whose
46
names correspond to targets (built or imported) and those for which an
47
old-style <item>_LIB_DEPENDS variable is defined. All other items are
48
unknown and we must infer dependencies for them. For items that look
49
like flags (beginning with '-') we trivially infer no dependencies,
50
and do not include them in the dependencies of other items.
51
52
Known items have dependency lists ordered based on how the user
53
specified them. We can use this order to infer potential dependencies
54
of unknown items. For example, if link items A and B are unknown and
55
items X and Y are known, then we might have the following dependency
56
lists:
57
58
X: Y A B
59
Y: A B
60
61
The explicitly known dependencies form graph edges
62
63
X -> Y , X -> A , X -> B , Y -> A , Y -> B
64
65
We can also infer the edge
66
67
A -> B
68
69
because *every* time A appears B is seen on its right. We do not know
70
whether A really needs symbols from B to link, but it *might* so we
71
must preserve their order. This is the case also for the following
72
explict lists:
73
74
X: A B Y
75
Y: A B
76
77
Here, A is followed by the set {B,Y} in one list, and {B} in the other
78
list. The intersection of these sets is {B}, so we can infer that A
79
depends on at most B. Meanwhile B is followed by the set {Y} in one
80
list and {} in the other. The intersection is {} so we can infer that
81
B has no dependencies.
82
83
Let's make a more complex example by adding unknown item C and
84
considering these dependency lists:
85
86
X: A B Y C
87
Y: A C B
88
89
The explicit edges are
90
91
X -> Y , X -> A , X -> B , X -> C , Y -> A , Y -> B , Y -> C
92
93
For the unknown items, we infer dependencies by looking at the
94
"follow" sets:
95
96
A: intersect( {B,Y,C} , {C,B} ) = {B,C} ; infer edges A -> B , A -> C
97
B: intersect( {Y,C} , {} ) = {} ; infer no edges
98
C: intersect( {} , {B} ) = {} ; infer no edges
99
100
Note that targets are never inferred as dependees because outside
101
libraries should not depend on them.
102
103
------------------------------------------------------------------------------
104
105
The initial exploration of dependencies using a BFS associates an
106
integer index with each link item. When the graph is built outgoing
107
edges are sorted by this index.
108
109
After the initial exploration of the link interface tree, any
110
transitive (dependent) shared libraries that were encountered and not
111
included in the interface are processed in their own BFS. This BFS
112
follows only the dependent library lists and not the link interfaces.
113
They are added to the link items with a mark indicating that the are
114
transitive dependencies. Then cmComputeLinkInformation deals with
115
them on a per-platform basis.
116
117
The complete graph formed from all known and inferred dependencies may
118
not be acyclic, so an acyclic version must be created.
119
The original graph is converted to a directed acyclic graph in which
120
each node corresponds to a strongly connected component of the
121
original graph. For example, the dependency graph
122
123
X -> A -> B -> C -> A -> Y
124
125
contains strongly connected components {X}, {A,B,C}, and {Y}. The
126
implied directed acyclic graph (DAG) is
127
128
{X} -> {A,B,C} -> {Y}
129
130
We then compute a topological order for the DAG nodes to serve as a
131
reference for satisfying dependencies efficiently. We perform the DFS
132
in reverse order and assign topological order indices counting down so
133
that the result is as close to the original BFS order as possible
134
without violating dependencies.
135
136
------------------------------------------------------------------------------
137
138
The final link entry order is constructed as follows. We first walk
139
through and emit the *original* link line as specified by the user.
140
As each item is emitted, a set of pending nodes in the component DAG
141
is maintained. When a pending component has been completely seen, it
142
is removed from the pending set and its dependencies (following edges
143
of the DAG) are added. A trivial component (those with one item) is
144
complete as soon as its item is seen. A non-trivial component (one
145
with more than one item; assumed to be static libraries) is complete
146
when *all* its entries have been seen *twice* (all entries seen once,
147
then all entries seen again, not just each entry twice). A pending
148
component tracks which items have been seen and a count of how many
149
times the component needs to be seen (once for trivial components,
150
twice for non-trivial). If at any time another component finishes and
151
re-adds an already pending component, the pending component is reset
152
so that it needs to be seen in its entirety again. This ensures that
153
all dependencies of a component are satisified no matter where it
154
appears.
155
156
After the original link line has been completed, we append to it the
157
remaining pending components and their dependencies. This is done by
158
repeatedly emitting the first item from the first pending component
159
and following the same update rules as when traversing the original
160
link line. Since the pending components are kept in topological order
161
they are emitted with minimal repeats (we do not want to emit a
162
component just to have it added again when another component is
163
completed later). This process continues until no pending components
164
remain. We know it will terminate because the component graph is
165
guaranteed to be acyclic.
166
167
The final list of items produced by this procedure consists of the
168
original user link line followed by minimal additional items needed to
169
satisfy dependencies.
170
171
*/
172
173
//----------------------------------------------------------------------------
174
cmComputeLinkDepends
175
::cmComputeLinkDepends(cmTarget* target, const char* config)
176
{
177
// Store context information.
178
this->Target = target;
179
this->Makefile = this->Target->GetMakefile();
180
this->LocalGenerator = this->Makefile->GetLocalGenerator();
181
this->GlobalGenerator = this->LocalGenerator->GetGlobalGenerator();
182
this->CMakeInstance = this->GlobalGenerator->GetCMakeInstance();
183
184
// The configuration being linked.
185
this->Config = (config && *config)? config : 0;
186
this->LinkType = this->Target->ComputeLinkType(this->Config);
187
188
// Enable debug mode if requested.
189
this->DebugMode = this->Makefile->IsOn("CMAKE_LINK_DEPENDS_DEBUG_MODE");
190
191
// Assume no compatibility until set.
192
this->OldLinkDirMode = false;
193
194
// No computation has been done.
195
this->CCG = 0;
196
}
197
198
//----------------------------------------------------------------------------
199
cmComputeLinkDepends::~cmComputeLinkDepends()
200
{
201
for(std::vector<DependSetList*>::iterator
202
i = this->InferredDependSets.begin();
203
i != this->InferredDependSets.end(); ++i)
204
{
205
delete *i;
206
}
207
delete this->CCG;
208
}
209
210
//----------------------------------------------------------------------------
211
void cmComputeLinkDepends::SetOldLinkDirMode(bool b)
212
{
213
this->OldLinkDirMode = b;
214
}
215
216
//----------------------------------------------------------------------------
217
std::vector<cmComputeLinkDepends::LinkEntry> const&
218
cmComputeLinkDepends::Compute()
219
{
220
// Follow the link dependencies of the target to be linked.
221
this->AddDirectLinkEntries();
222
223
// Complete the breadth-first search of dependencies.
224
while(!this->BFSQueue.empty())
225
{
226
// Get the next entry.
227
BFSEntry qe = this->BFSQueue.front();
228
this->BFSQueue.pop();
229
230
// Follow the entry's dependencies.
231
this->FollowLinkEntry(qe);
232
}
233
234
// Complete the search of shared library dependencies.
235
while(!this->SharedDepQueue.empty())
236
{
237
// Handle the next entry.
238
this->HandleSharedDependency(this->SharedDepQueue.front());
239
this->SharedDepQueue.pop();
240
}
241
242
// Infer dependencies of targets for which they were not known.
243
this->InferDependencies();
244
245
// Cleanup the constraint graph.
246
this->CleanConstraintGraph();
247
248
// Display the constraint graph.
249
if(this->DebugMode)
250
{
251
fprintf(stderr,
252
"---------------------------------------"
253
"---------------------------------------\n");
254
fprintf(stderr, "Link dependency analysis for target %s, config %s\n",
255
this->Target->GetName(), this->Config?this->Config:"noconfig");
256
this->DisplayConstraintGraph();
257
}
258
259
// Compute the final ordering.
260
this->OrderLinkEntires();
261
262
// Compute the final set of link entries.
263
for(std::vector<int>::const_iterator li = this->FinalLinkOrder.begin();
264
li != this->FinalLinkOrder.end(); ++li)
265
{
266
this->FinalLinkEntries.push_back(this->EntryList[*li]);
267
}
268
269
// Display the final set.
270
if(this->DebugMode)
271
{
272
this->DisplayFinalEntries();
273
}
274
275
return this->FinalLinkEntries;
276
}
277
278
//----------------------------------------------------------------------------
279
std::map<cmStdString, int>::iterator
280
cmComputeLinkDepends::AllocateLinkEntry(std::string const& item)
281
{
282
std::map<cmStdString, int>::value_type
283
index_entry(item, static_cast<int>(this->EntryList.size()));
284
std::map<cmStdString, int>::iterator
285
lei = this->LinkEntryIndex.insert(index_entry).first;
286
this->EntryList.push_back(LinkEntry());
287
this->InferredDependSets.push_back(0);
288
this->EntryConstraintGraph.push_back(EdgeList());
289
return lei;
290
}
291
292
//----------------------------------------------------------------------------
293
int cmComputeLinkDepends::AddLinkEntry(int depender_index,
294
std::string const& item)
295
{
296
// Check if the item entry has already been added.
297
std::map<cmStdString, 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.
301
return lei->second;
302
}
303
304
// Allocate a spot for the item entry.
305
lei = this->AllocateLinkEntry(item);
306
307
// Initialize the item entry.
308
int index = lei->second;
309
LinkEntry& entry = this->EntryList[index];
310
entry.Item = item;
311
entry.Target = this->FindTargetToLink(depender_index, entry.Item.c_str());
312
entry.IsFlag = (!entry.Target && item[0] == '-' && item[1] != 'l' &&
313
item.substr(0, 10) != "-framework");
314
315
// If the item has dependencies queue it to follow them.
316
if(entry.Target)
317
{
318
// Target dependencies are always known. Follow them.
319
BFSEntry qe = {index, 0};
320
this->BFSQueue.push(qe);
321
}
322
else
323
{
324
// Look for an old-style <item>_LIB_DEPENDS variable.
325
std::string var = entry.Item;
326
var += "_LIB_DEPENDS";
327
if(const char* val = this->Makefile->GetDefinition(var.c_str()))
328
{
329
// The item dependencies are known. Follow them.
330
BFSEntry qe = {index, val};
331
this->BFSQueue.push(qe);
332
}
333
else if(!entry.IsFlag)
334
{
335
// The item dependencies are not known. We need to infer them.
336
this->InferredDependSets[index] = new DependSetList;
337
}
338
}
339
340
return index;
341
}
342
343
//----------------------------------------------------------------------------
344
void cmComputeLinkDepends::FollowLinkEntry(BFSEntry const& qe)
345
{
346
// Get this entry representation.
347
int depender_index = qe.Index;
348
LinkEntry const& entry = this->EntryList[depender_index];
349
350
// Follow the item's dependencies.
351
if(entry.Target)
352
{
353
// Follow the target dependencies.
354
if(cmTarget::LinkInterface const* iface =
355
entry.Target->GetLinkInterface(this->Config))
356
{
357
// This target provides its own link interface information.
358
this->AddLinkEntries(depender_index, iface->Libraries);
359
360
// Handle dependent shared libraries.
361
this->QueueSharedDependencies(depender_index, iface->SharedDeps);
362
363
// Support for CMP0003.
364
for(std::vector<std::string>::const_iterator
365
oi = iface->WrongConfigLibraries.begin();
366
oi != iface->WrongConfigLibraries.end(); ++oi)
367
{
368
this->CheckWrongConfigItem(depender_index, *oi);
369
}
370
}
371
}
372
else
373
{
374
// Follow the old-style dependency list.
375
this->AddVarLinkEntries(depender_index, qe.LibDepends);
376
}
377
}
378
379
//----------------------------------------------------------------------------
380
void
381
cmComputeLinkDepends
382
::QueueSharedDependencies(int depender_index,
383
std::vector<std::string> const& deps)
384
{
385
for(std::vector<std::string>::const_iterator li = deps.begin();
386
li != deps.end(); ++li)
387
{
388
SharedDepEntry qe;
389
qe.Item = *li;
390
qe.DependerIndex = depender_index;
391
this->SharedDepQueue.push(qe);
392
}
393
}
394
395
//----------------------------------------------------------------------------
396
void cmComputeLinkDepends::HandleSharedDependency(SharedDepEntry const& dep)
397
{
398
// Check if the target already has an entry.
399
std::map<cmStdString, int>::iterator lei =
400
this->LinkEntryIndex.find(dep.Item);
401
if(lei == this->LinkEntryIndex.end())
402
{
403
// Allocate a spot for the item entry.
404
lei = this->AllocateLinkEntry(dep.Item);
405
406
// Initialize the item entry.
407
LinkEntry& entry = this->EntryList[lei->second];
408
entry.Item = dep.Item;
409
entry.Target = this->FindTargetToLink(dep.DependerIndex,
410
dep.Item.c_str());
411
412
// This item was added specifically because it is a dependent
413
// shared library. It may get special treatment
414
// in cmComputeLinkInformation.
415
entry.IsSharedDep = true;
416
}
417
418
// Get the link entry for this target.
419
int index = lei->second;
420
LinkEntry& entry = this->EntryList[index];
421
422
// This shared library dependency must follow the item that listed
423
// it.
424
this->EntryConstraintGraph[dep.DependerIndex].push_back(index);
425
426
// Target items may have their own dependencies.
427
if(entry.Target)
428
{
429
if(cmTarget::LinkInterface const* iface =
430
entry.Target->GetLinkInterface(this->Config))
431
{
432
// We use just the shared dependencies, not the interface.
433
this->QueueSharedDependencies(index, iface->SharedDeps);
434
}
435
}
436
}
437
438
//----------------------------------------------------------------------------
439
void cmComputeLinkDepends::AddVarLinkEntries(int depender_index,
440
const char* value)
441
{
442
// This is called to add the dependencies named by
443
// <item>_LIB_DEPENDS. The variable contains a semicolon-separated
444
// list. The list contains link-type;item pairs and just items.
445
std::vector<std::string> deplist;
446
cmSystemTools::ExpandListArgument(value, deplist);
447
448
// Look for entries meant for this configuration.
449
std::vector<std::string> actual_libs;
450
cmTarget::LinkLibraryType llt = cmTarget::GENERAL;
451
bool haveLLT = false;
452
for(std::vector<std::string>::const_iterator di = deplist.begin();
453
di != deplist.end(); ++di)
454
{
455
if(*di == "debug")
456
{
457
llt = cmTarget::DEBUG;
458
haveLLT = true;
459
}
460
else if(*di == "optimized")
461
{
462
llt = cmTarget::OPTIMIZED;
463
haveLLT = true;
464
}
465
else if(*di == "general")
466
{
467
llt = cmTarget::GENERAL;
468
haveLLT = true;
469
}
470
else if(!di->empty())
471
{
472
// If no explicit link type was given prior to this entry then
473
// check if the entry has its own link type variable. This is
474
// needed for compatibility with dependency files generated by
475
// the export_library_dependencies command from CMake 2.4 and
476
// lower.
477
if(!haveLLT)
478
{
479
std::string var = *di;
480
var += "_LINK_TYPE";
481
if(const char* val = this->Makefile->GetDefinition(var.c_str()))
482
{
483
if(strcmp(val, "debug") == 0)
484
{
485
llt = cmTarget::DEBUG;
486
}
487
else if(strcmp(val, "optimized") == 0)
488
{
489
llt = cmTarget::OPTIMIZED;
490
}
491
}
492
}
493
494
// If the library is meant for this link type then use it.
495
if(llt == cmTarget::GENERAL || llt == this->LinkType)
496
{
497
actual_libs.push_back(*di);
498
}
499
else if(this->OldLinkDirMode)
500
{
501
this->CheckWrongConfigItem(depender_index, *di);
502
}
503
504
// Reset the link type until another explicit type is given.
505
llt = cmTarget::GENERAL;
506
haveLLT = false;
507
}
508
}
509
510
// Add the entries from this list.
511
this->AddLinkEntries(depender_index, actual_libs);
512
}
513
514
//----------------------------------------------------------------------------
515
void cmComputeLinkDepends::AddDirectLinkEntries()
516
{
517
// Add direct link dependencies in this configuration.
518
cmTarget::LinkImplementation const* impl =
519
this->Target->GetLinkImplementation(this->Config);
520
this->AddLinkEntries(-1, impl->Libraries);
521
for(std::vector<std::string>::const_iterator
522
wi = impl->WrongConfigLibraries.begin();
523
wi != impl->WrongConfigLibraries.end(); ++wi)
524
{
525
this->CheckWrongConfigItem(-1, *wi);
526
}
527
}
528
529
//----------------------------------------------------------------------------
530
void
531
cmComputeLinkDepends::AddLinkEntries(int depender_index,
532
std::vector<std::string> const& libs)
533
{
534
// Track inferred dependency sets implied by this list.
535
std::map<int, DependSet> dependSets;
536
537
// Loop over the libraries linked directly by the depender.
538
for(std::vector<std::string>::const_iterator li = libs.begin();
539
li != libs.end(); ++li)
540
{
541
// Skip entries that will resolve to the target getting linked or
542
// are empty.
543
std::string item = this->Target->CheckCMP0004(*li);
544
if(item == this->Target->GetName() || item.empty())
545
{
546
continue;
547
}
548
549
// Add a link entry for this item.
550
int dependee_index = this->AddLinkEntry(depender_index, item);
551
552
// The dependee must come after the depender.
553
if(depender_index >= 0)
554
{
555
this->EntryConstraintGraph[depender_index].push_back(dependee_index);
556
}
557
else
558
{
559
// This is a direct dependency of the target being linked.
560
this->OriginalEntries.push_back(dependee_index);
561
}
562
563
// Update the inferred dependencies for earlier items.
564
for(std::map<int, DependSet>::iterator dsi = dependSets.begin();
565
dsi != dependSets.end(); ++dsi)
566
{
567
// Add this item to the inferred dependencies of other items.
568
// Target items are never inferred dependees because unknown
569
// items are outside libraries that should not be depending on
570
// targets.
571
if(!this->EntryList[dependee_index].Target &&
572
!this->EntryList[dependee_index].IsFlag &&
573
dependee_index != dsi->first)
574
{
575
dsi->second.insert(dependee_index);
576
}
577
}
578
579
// If this item needs to have dependencies inferred, do so.
580
if(this->InferredDependSets[dependee_index])
581
{
582
// Make sure an entry exists to hold the set for the item.
583
dependSets[dependee_index];
584
}
585
}
586
587
// Store the inferred dependency sets discovered for this list.
588
for(std::map<int, DependSet>::iterator dsi = dependSets.begin();
589
dsi != dependSets.end(); ++dsi)
590
{
591
this->InferredDependSets[dsi->first]->push_back(dsi->second);
592
}
593
}
594
595
//----------------------------------------------------------------------------
596
cmTarget* cmComputeLinkDepends::FindTargetToLink(int depender_index,
597
const char* name)
598
{
599
// Look for a target in the scope of the depender.
600
cmMakefile* mf = this->Makefile;
601
if(depender_index >= 0)
602
{
603
if(cmTarget* depender = this->EntryList[depender_index].Target)
604
{
605
mf = depender->GetMakefile();
606
}
607
}
608
cmTarget* tgt = mf->FindTargetToUse(name);
609
610
// Skip targets that will not really be linked. This is probably a
611
// name conflict between an external library and an executable
612
// within the project.
613
if(tgt && tgt->GetType() == cmTarget::EXECUTABLE &&
614
!tgt->IsExecutableWithExports())
615
{
616
tgt = 0;
617
}
618
619
// Return the target found, if any.
620
return tgt;
621
}
622
623
//----------------------------------------------------------------------------
624
void cmComputeLinkDepends::InferDependencies()
625
{
626
// The inferred dependency sets for each item list the possible
627
// dependencies. The intersection of the sets for one item form its
628
// inferred dependencies.
629
for(unsigned int depender_index=0;
630
depender_index < this->InferredDependSets.size(); ++depender_index)
631
{
632
// Skip items for which dependencies do not need to be inferred or
633
// for which the inferred dependency sets are empty.
634
DependSetList* sets = this->InferredDependSets[depender_index];
635
if(!sets || sets->empty())
636
{
637
continue;
638
}
639
640
// Intersect the sets for this item.
641
DependSetList::const_iterator i = sets->begin();
642
DependSet common = *i;
643
for(++i; i != sets->end(); ++i)
644
{
645
DependSet intersection;
646
cmsys_stl::set_intersection
647
(common.begin(), common.end(), i->begin(), i->end(),
648
std::inserter(intersection, intersection.begin()));
649
common = intersection;
650
}
651
652
// Add the inferred dependencies to the graph.
653
for(DependSet::const_iterator j = common.begin(); j != common.end(); ++j)
654
{
655
int dependee_index = *j;
656
this->EntryConstraintGraph[depender_index].push_back(dependee_index);
657
}
658
}
659
}
660
661
//----------------------------------------------------------------------------
662
void cmComputeLinkDepends::CleanConstraintGraph()
663
{
664
for(Graph::iterator i = this->EntryConstraintGraph.begin();
665
i != this->EntryConstraintGraph.end(); ++i)
666
{
667
// Sort the outgoing edges for each graph node so that the
668
// original order will be preserved as much as possible.
669
cmsys_stl::sort(i->begin(), i->end());
670
671
// Make the edge list unique.
672
EdgeList::iterator last = cmsys_stl::unique(i->begin(), i->end());
673
i->erase(last, i->end());
674
}
675
}
676
677
//----------------------------------------------------------------------------
678
void cmComputeLinkDepends::DisplayConstraintGraph()
679
{
680
// Display the graph nodes and their edges.
681
cmOStringStream e;
682
for(unsigned int i=0; i < this->EntryConstraintGraph.size(); ++i)
683
{
684
EdgeList const& nl = this->EntryConstraintGraph[i];
685
e << "item " << i << " is [" << this->EntryList[i].Item << "]\n";
686
for(EdgeList::const_iterator j = nl.begin(); j != nl.end(); ++j)
687
{
688
e << " item " << *j << " must follow it\n";
689
}
690
}
691
fprintf(stderr, "%s\n", e.str().c_str());
692
}
693
694
//----------------------------------------------------------------------------
695
void cmComputeLinkDepends::OrderLinkEntires()
696
{
697
// Compute the DAG of strongly connected components. The algorithm
698
// used by cmComputeComponentGraph should identify the components in
699
// the same order in which the items were originally discovered in
700
// the BFS. This should preserve the original order when no
701
// constraints disallow it.
702
this->CCG = new cmComputeComponentGraph(this->EntryConstraintGraph);
703
704
// The component graph is guaranteed to be acyclic. Start a DFS
705
// from every entry to compute a topological order for the
706
// components.
707
Graph const& cgraph = this->CCG->GetComponentGraph();
708
int n = static_cast<int>(cgraph.size());
709
this->ComponentVisited.resize(cgraph.size(), 0);
710
this->ComponentOrder.resize(cgraph.size(), n);
711
this->ComponentOrderId = n;
712
// Run in reverse order so the topological order will preserve the
713
// original order where there are no constraints.
714
for(int c = n-1; c >= 0; --c)
715
{
716
this->VisitComponent(c);
717
}
718
719
// Display the component graph.
720
if(this->DebugMode)
721
{
722
this->DisplayComponents();
723
}
724
725
// Start with the original link line.
726
for(std::vector<int>::const_iterator i = this->OriginalEntries.begin();
727
i != this->OriginalEntries.end(); ++i)
728
{
729
this->VisitEntry(*i);
730
}
731
732
// Now explore anything left pending. Since the component graph is
733
// guaranteed to be acyclic we know this will terminate.
734
while(!this->PendingComponents.empty())
735
{
736
// Visit one entry from the first pending component. The visit
737
// logic will update the pending components accordingly. Since
738
// the pending components are kept in topological order this will
739
// not repeat one.
740
int e = *this->PendingComponents.begin()->second.Entries.begin();
741
this->VisitEntry(e);
742
}
743
}
744
745
//----------------------------------------------------------------------------
746
void
747
cmComputeLinkDepends::DisplayComponents()
748
{
749
fprintf(stderr, "The strongly connected components are:\n");
750
std::vector<NodeList> const& components = this->CCG->GetComponents();
751
for(unsigned int c=0; c < components.size(); ++c)
752
{
753
fprintf(stderr, "Component (%u):\n", c);
754
NodeList const& nl = components[c];
755
for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
756
{
757
int i = *ni;
758
fprintf(stderr, " item %d [%s]\n", i,
759
this->EntryList[i].Item.c_str());
760
}
761
EdgeList const& ol = this->CCG->GetComponentGraphEdges(c);
762
for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
763
{
764
int i = *oi;
765
fprintf(stderr, " followed by Component (%d)\n", i);
766
}
767
fprintf(stderr, " topo order index %d\n",
768
this->ComponentOrder[c]);
769
}
770
fprintf(stderr, "\n");
771
}
772
773
//----------------------------------------------------------------------------
774
void cmComputeLinkDepends::VisitComponent(unsigned int c)
775
{
776
// Check if the node has already been visited.
777
if(this->ComponentVisited[c])
778
{
779
return;
780
}
781
782
// We are now visiting this component so mark it.
783
this->ComponentVisited[c] = 1;
784
785
// Visit the neighbors of the component first.
786
// Run in reverse order so the topological order will preserve the
787
// original order where there are no constraints.
788
EdgeList const& nl = this->CCG->GetComponentGraphEdges(c);
789
for(EdgeList::const_reverse_iterator ni = nl.rbegin();
790
ni != nl.rend(); ++ni)
791
{
792
this->VisitComponent(*ni);
793
}
794
795
// Assign an ordering id to this component.
796
this->ComponentOrder[c] = --this->ComponentOrderId;
797
}
798
799
//----------------------------------------------------------------------------
800
void cmComputeLinkDepends::VisitEntry(int index)
801
{
802
// Include this entry on the link line.
803
this->FinalLinkOrder.push_back(index);
804
805
// This entry has now been seen. Update its component.
806
bool completed = false;
807
int component = this->CCG->GetComponentMap()[index];
808
std::map<int, PendingComponent>::iterator mi =
809
this->PendingComponents.find(this->ComponentOrder[component]);
810
if(mi != this->PendingComponents.end())
811
{
812
// The entry is in an already pending component.
813
PendingComponent& pc = mi->second;
814
815
// Remove the entry from those pending in its component.
816
pc.Entries.erase(index);
817
if(pc.Entries.empty())
818
{
819
// The complete component has been seen since it was last needed.
820
--pc.Count;
821
822
if(pc.Count == 0)
823
{
824
// The component has been completed.
825
this->PendingComponents.erase(mi);
826
completed = true;
827
}
828
else
829
{
830
// The whole component needs to be seen again.
831
NodeList const& nl = this->CCG->GetComponent(component);
832
assert(nl.size() > 1);
833
pc.Entries.insert(nl.begin(), nl.end());
834
}
835
}
836
}
837
else
838
{
839
// The entry is not in an already pending component.
840
NodeList const& nl = this->CCG->GetComponent(component);
841
if(nl.size() > 1)
842
{
843
// This is a non-trivial component. It is now pending.
844
PendingComponent& pc = this->MakePendingComponent(component);
845
846
// The starting entry has already been seen.
847
pc.Entries.erase(index);
848
}
849
else
850
{
851
// This is a trivial component, so it is already complete.
852
completed = true;
853
}
854
}
855
856
// If the entry completed a component, the component's dependencies
857
// are now pending.
858
if(completed)
859
{
860
EdgeList const& ol = this->CCG->GetComponentGraphEdges(component);
861
for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
862
{
863
// This entire component is now pending no matter whether it has
864
// been partially seen already.
865
this->MakePendingComponent(*oi);
866
}
867
}
868
}
869
870
//----------------------------------------------------------------------------
871
cmComputeLinkDepends::PendingComponent&
872
cmComputeLinkDepends::MakePendingComponent(unsigned int component)
873
{
874
// Create an entry (in topological order) for the component.
875
PendingComponent& pc =
876
this->PendingComponents[this->ComponentOrder[component]];
877
pc.Id = component;
878
NodeList const& nl = this->CCG->GetComponent(component);
879
880
if(nl.size() == 1)
881
{
882
// Trivial components need be seen only once.
883
pc.Count = 1;
884
}
885
else
886
{
887
// This is a non-trivial strongly connected component of the
888
// original graph. It consists of two or more libraries
889
// (archives) that mutually require objects from one another. In
890
// the worst case we may have to repeat the list of libraries as
891
// many times as there are object files in the biggest archive.
892
// For now we just list them twice.
893
//
894
// The list of items in the component has been sorted by the order
895
// of discovery in the original BFS of dependencies. This has the
896
// advantage that the item directly linked by a target requiring
897
// this component will come first which minimizes the number of
898
// repeats needed.
899
pc.Count = this->ComputeComponentCount(nl);
900
}
901
902
// Store the entries to be seen.
903
pc.Entries.insert(nl.begin(), nl.end());
904
905
return pc;
906
}
907
908
//----------------------------------------------------------------------------
909
int cmComputeLinkDepends::ComputeComponentCount(NodeList const& nl)
910
{
911
int count = 2;
912
for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
913
{
914
if(cmTarget* target = this->EntryList[*ni].Target)
915
{
916
if(cmTarget::LinkInterface const* iface =
917
target->GetLinkInterface(this->Config))
918
{
919
if(iface->Multiplicity > count)
920
{
921
count = iface->Multiplicity;
922
}
923
}
924
}
925
}
926
return count;
927
}
928
929
//----------------------------------------------------------------------------
930
void cmComputeLinkDepends::DisplayFinalEntries()
931
{
932
fprintf(stderr, "target [%s] links to:\n", this->Target->GetName());
933
for(std::vector<LinkEntry>::const_iterator lei =
934
this->FinalLinkEntries.begin();
935
lei != this->FinalLinkEntries.end(); ++lei)
936
{
937
if(lei->Target)
938
{
939
fprintf(stderr, " target [%s]\n", lei->Target->GetName());
940
}
941
else
942
{
943
fprintf(stderr, " item [%s]\n", lei->Item.c_str());
944
}
945
}
946
fprintf(stderr, "\n");
947
}
948
949
//----------------------------------------------------------------------------
950
void cmComputeLinkDepends::CheckWrongConfigItem(int depender_index,
951
std::string const& item)
952
{
953
if(!this->OldLinkDirMode)
954
{
955
return;
956
}
957
958
// For CMake 2.4 bug-compatibility we need to consider the output
959
// directories of targets linked in another configuration as link
960
// directories.
961
if(cmTarget* tgt = this->FindTargetToLink(depender_index, item.c_str()))
962
{
963
if(!tgt->IsImported())
964
{
965
this->OldWrongConfigItems.insert(tgt);
966
}
967
}
968
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1