Root/
1 | #! /usr/bin/perl |
2 | # |
3 | # Detect cycles in the header file dependency graph |
4 | # Vegard Nossum <vegardno@ifi.uio.no> |
5 | # |
6 | |
7 | use strict; |
8 | use warnings; |
9 | |
10 | use Getopt::Long; |
11 | |
12 | my $opt_all; |
13 | my @opt_include; |
14 | my $opt_graph; |
15 | |
16 | &Getopt::Long::Configure(qw(bundling pass_through)); |
17 | &GetOptions( |
18 | help => \&help, |
19 | version => \&version, |
20 | |
21 | all => \$opt_all, |
22 | "I=s" => \@opt_include, |
23 | graph => \$opt_graph, |
24 | ); |
25 | |
26 | push @opt_include, 'include'; |
27 | my %deps = (); |
28 | my %linenos = (); |
29 | |
30 | my @headers = grep { strip($_) } @ARGV; |
31 | |
32 | parse_all(@headers); |
33 | |
34 | if($opt_graph) { |
35 | graph(); |
36 | } else { |
37 | detect_cycles(@headers); |
38 | } |
39 | |
40 | |
41 | sub help { |
42 | print "Usage: $0 [options] file...\n"; |
43 | print "\n"; |
44 | print "Options:\n"; |
45 | print " --all\n"; |
46 | print " --graph\n"; |
47 | print "\n"; |
48 | print " -I includedir\n"; |
49 | print "\n"; |
50 | print "To make nice graphs, try:\n"; |
51 | print " $0 --graph include/linux/kernel.h | dot -Tpng -o graph.png\n"; |
52 | exit; |
53 | } |
54 | |
55 | sub version { |
56 | print "headerdep version 2\n"; |
57 | exit; |
58 | } |
59 | |
60 | # Get a file name that is relative to our include paths |
61 | sub strip { |
62 | my $filename = shift; |
63 | |
64 | for my $i (@opt_include) { |
65 | my $stripped = $filename; |
66 | $stripped =~ s/^$i\///; |
67 | |
68 | return $stripped if $stripped ne $filename; |
69 | } |
70 | |
71 | return $filename; |
72 | } |
73 | |
74 | # Search for the file name in the list of include paths |
75 | sub search { |
76 | my $filename = shift; |
77 | return $filename if -f $filename; |
78 | |
79 | for my $i (@opt_include) { |
80 | my $path = "$i/$filename"; |
81 | return $path if -f $path; |
82 | } |
83 | |
84 | return undef; |
85 | } |
86 | |
87 | sub parse_all { |
88 | # Parse all the headers. |
89 | my @queue = @_; |
90 | while(@queue) { |
91 | my $header = pop @queue; |
92 | next if exists $deps{$header}; |
93 | |
94 | $deps{$header} = [] unless exists $deps{$header}; |
95 | |
96 | my $path = search($header); |
97 | next unless $path; |
98 | |
99 | open(my $file, '<', $path) or die($!); |
100 | chomp(my @lines = <$file>); |
101 | close($file); |
102 | |
103 | for my $i (0 .. $#lines) { |
104 | my $line = $lines[$i]; |
105 | if(my($dep) = ($line =~ m/^#\s*include\s*<(.*?)>/)) { |
106 | push @queue, $dep; |
107 | push @{$deps{$header}}, [$i + 1, $dep]; |
108 | } |
109 | } |
110 | } |
111 | } |
112 | |
113 | sub print_cycle { |
114 | # $cycle[n] includes $cycle[n + 1]; |
115 | # $cycle[-1] will be the culprit |
116 | my $cycle = shift; |
117 | |
118 | # Adjust the line numbers |
119 | for my $i (0 .. $#$cycle - 1) { |
120 | $cycle->[$i]->[0] = $cycle->[$i + 1]->[0]; |
121 | } |
122 | $cycle->[-1]->[0] = 0; |
123 | |
124 | my $first = shift @$cycle; |
125 | my $last = pop @$cycle; |
126 | |
127 | my $msg = "In file included"; |
128 | printf "%s from %s,\n", $msg, $last->[1] if defined $last; |
129 | |
130 | for my $header (reverse @$cycle) { |
131 | printf "%s from %s:%d%s\n", |
132 | " " x length $msg, |
133 | $header->[1], $header->[0], |
134 | $header->[1] eq $last->[1] ? ' <-- here' : ''; |
135 | } |
136 | |
137 | printf "%s:%d: warning: recursive header inclusion\n", |
138 | $first->[1], $first->[0]; |
139 | } |
140 | |
141 | # Find and print the smallest cycle starting in the specified node. |
142 | sub detect_cycles { |
143 | my @queue = map { [[0, $_]] } @_; |
144 | while(@queue) { |
145 | my $top = pop @queue; |
146 | my $name = $top->[-1]->[1]; |
147 | |
148 | for my $dep (@{$deps{$name}}) { |
149 | my $chain = [@$top, [$dep->[0], $dep->[1]]]; |
150 | |
151 | # If the dep already exists in the chain, we have a |
152 | # cycle... |
153 | if(grep { $_->[1] eq $dep->[1] } @$top) { |
154 | print_cycle($chain); |
155 | next if $opt_all; |
156 | return; |
157 | } |
158 | |
159 | push @queue, $chain; |
160 | } |
161 | } |
162 | } |
163 | |
164 | sub mangle { |
165 | $_ = shift; |
166 | s/\//__/g; |
167 | s/\./_/g; |
168 | s/-/_/g; |
169 | $_; |
170 | } |
171 | |
172 | # Output dependency graph in GraphViz language. |
173 | sub graph { |
174 | print "digraph {\n"; |
175 | |
176 | print "\t/* vertices */\n"; |
177 | for my $header (keys %deps) { |
178 | printf "\t%s [label=\"%s\"];\n", |
179 | mangle($header), $header; |
180 | } |
181 | |
182 | print "\n"; |
183 | |
184 | print "\t/* edges */\n"; |
185 | for my $header (keys %deps) { |
186 | for my $dep (@{$deps{$header}}) { |
187 | printf "\t%s -> %s;\n", |
188 | mangle($header), mangle($dep->[1]); |
189 | } |
190 | } |
191 | |
192 | print "}\n"; |
193 | } |
194 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9