← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/tools/llvm-config/find-cycles.pl

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

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