1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
#!/usr/bin/perl
#
# Program: find-cycles.pl
#
# Synopsis: Given a list of possibly cyclic dependencies, merge all the
# cycles. This makes it possible to topologically sort the
# dependencies between different parts of LLVM.
#
# Syntax: find-cycles.pl < LibDeps.txt > FinalLibDeps.txt
#
# Input: cycmem1: cycmem2 dep1 dep2
# cycmem2: cycmem1 dep3 dep4
# boring: dep4
#
# Output: cycmem1 cycmem2: dep1 dep2 dep3 dep4
# boring: dep4
#
# This file was written by Eric Kidd, and is placed into the public domain.
#
use 5.006;
use strict;
use warnings;
my %DEPS;
my @CYCLES;
sub find_all_cycles;
# Read our dependency information.
while (<>) {
chomp;
my ($module, $dependency_str) = /^\s*([^:]+):\s*(.*)\s*$/;
die "Malformed data: $_" unless defined $dependency_str;
my @dependencies = split(/ /, $dependency_str);
$DEPS{$module} = \@dependencies;
}
# Partition our raw dependencies into sets of cyclically-connected nodes.
find_all_cycles();
# Print out the finished cycles, with their dependencies.
my @output;
my $cycles_found = 0;
foreach my $cycle (@CYCLES) {
my @modules = sort keys %{$cycle};
# Merge the dependencies of all modules in this cycle.
my %dependencies;
foreach my $module (@modules) {
@dependencies{@{$DEPS{$module}}} = 1;
}
# Prune the known cyclic dependencies.
foreach my $module (@modules) {
delete $dependencies{$module};
}
# Warn about possible linker problems.
my @archives = grep(/\.a$/, @modules);
if (@archives > 1) {
$cycles_found = $cycles_found + 1;
print STDERR "find-cycles.pl: Circular dependency between *.a files:\n";
print STDERR "find-cycles.pl: ", join(' ', @archives), "\n";
push @modules, @archives; # WORKAROUND: Duplicate *.a files. Ick.
}
# Add to our output. (@modules is already as sorted as we need it to be.)
push @output, (join(' ', @modules) . ': ' .
join(' ', sort keys %dependencies) . "\n");
}
print sort @output;
exit $cycles_found;
#==========================================================================
# Depedency Cycle Support
#==========================================================================
# For now, we have cycles in our dependency graph. Ideally, each cycle
# would be collapsed down to a single *.a file, saving us all this work.
#
# To understand this code, you'll need a working knowledge of Perl 5,
# and possibly some quality time with 'man perlref'.
my %SEEN;
my %CYCLES;
sub find_cycles ($@);
sub found_cycles ($@);
sub find_all_cycles {
# Find all multi-item cycles.
my @modules = sort keys %DEPS;
foreach my $module (@modules) { find_cycles($module); }
# Build fake one-item "cycles" for the remaining modules, so we can
# treat them uniformly.
foreach my $module (@modules) {
unless (defined $CYCLES{$module}) {
my %cycle = ($module, 1);
$CYCLES{$module} = \%cycle;
}
}
# Find all our unique cycles. We have to do this the hard way because
# we apparently can't store hash references as hash keys without making
# 'strict refs' sad.
my %seen;
foreach my $cycle (values %CYCLES) {
unless ($seen{$cycle}) {
$seen{$cycle} = 1;
push @CYCLES, $cycle;
}
}
}
# Walk through our graph depth-first (keeping a trail in @path), and report
# any cycles we find.
sub find_cycles ($@) {
my ($module, @path) = @_;
if (str_in_list($module, @path)) {
found_cycle($module, @path);
} else {
return if defined $SEEN{$module};
$SEEN{$module} = 1;
foreach my $dep (@{$DEPS{$module}}) {
find_cycles($dep, @path, $module);
}
}
}
# Give a cycle, attempt to merge it with pre-existing cycle data.
sub found_cycle ($@) {
my ($module, @path) = @_;
# Pop any modules which aren't part of our cycle.
while ($path[0] ne $module) { shift @path; }
#print join("->", @path, $module) . "\n";
# Collect the modules in our cycle into a hash.
my %cycle;
foreach my $item (@path) {
$cycle{$item} = 1;
if (defined $CYCLES{$item}) {
# Looks like we intersect with an existing cycle, so merge
# all those in, too.
foreach my $old_item (keys %{$CYCLES{$item}}) {
$cycle{$old_item} = 1;
}
}
}
# Update our global cycle table.
my $cycle_ref = \%cycle;
foreach my $item (keys %cycle) {
$CYCLES{$item} = $cycle_ref;
}
#print join(":", sort keys %cycle) . "\n";
}
sub str_in_list ($@) {
my ($str, @list) = @_;
foreach my $item (@list) {
return 1 if ($item eq $str);
}
return 0;
}
|
