[PATCH] headerdep: a tool for detecting inclusion cycles in header file

[PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Vegard Nossum]

Hi Sam,

Maybe something like this could be useful for cleaning up headers (and
maintaining that cleanliness once it has been achieved). What do you think?

(One thing which might or might not be good is that 'make headerdep' will
 also compile using CC if they're not already compiled. If this should be
 fixed, I think you'd know how to do it.)

Vegard


>From af7e8d3b620a5935b7bc15660d153b909a14abd9 Mon Sep 17 00:00:00 2001
From: Vegard Nossum <vegard.nossum@gmail.com>
Date: Sat, 26 Apr 2008 11:47:33 +0200
Subject: [PATCH] headerdep: a tool for detecting inclusion cycles in header files

Signed-off-by: Vegard Nossum <vegard.nossum@gmail.com>
---
 Makefile             |    5 ++
 scripts/headerdep.pl |  143 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 148 insertions(+), 0 deletions(-)
 create mode 100755 scripts/headerdep.pl

diff --git a/Makefile b/Makefile
index 39516bf..488b193 100644
--- a/Makefile
+++ b/Makefile
@@ -1021,6 +1021,10 @@ PHONY += headers_check
 headers_check: headers_install
 	$(Q)$(MAKE) -f $(srctree)/scripts/Makefile.headersinst ARCH=$(SRCARCH) obj=include HDRCHECK=1
 
+PHONY += headerdep
+headerdep:
+	$(Q)$(MAKE) C=2 CHECK=scripts/headerdep.pl
+
 # ---------------------------------------------------------------------------
 # Modules
 
@@ -1210,6 +1214,7 @@ help:
 	@if [ -r $(srctree)/include/asm-$(SRCARCH)/Kbuild ]; then \
 	 echo  '  headers_check   - Sanity check on exported headers'; \
 	 fi
+	@echo  '  headerdep       - Detect inclusion cycles in headers'
 	@echo  ''
 	@echo  'Kernel packaging:'
 	@$(MAKE) $(build)=$(package-dir) help
diff --git a/scripts/headerdep.pl b/scripts/headerdep.pl
new file mode 100755
index 0000000..c993d16
--- /dev/null
+++ b/scripts/headerdep.pl
@@ -0,0 +1,143 @@
+#! /usr/bin/perl
+#
+# Detect cycles in the header file dependency graph
+# Vegard Nossum <vegardno@ifi.uio.no>
+#
+
+use strict;
+use warnings;
+
+my @I = ('include');
+my %deps = ();
+
+my @headers = grep { strip($_) } @ARGV;
+
+parse_all(@headers);
+
+detect_cycles(@headers);
+#graph();
+exit;
+
+
+# Get a file name that is relative to our include paths
+sub strip {
+	my $filename = shift;
+
+	for my $i (@I) {
+		my $stripped = $filename;
+		$stripped =~ s/^$i\///;
+
+		return $stripped if $stripped ne $filename;
+	}
+
+	return $filename;
+}
+
+# Search for the file name in the list of include paths
+sub search {
+	my $filename = shift;
+	return $filename if -f $filename;
+
+	for my $i (@I) {
+		my $path = sprintf "%s/%s", $i, $filename;
+		return $path if -f $path;
+	}
+
+	return undef;
+}
+
+sub parse_all {
+	# Parse all the headers.
+	my @queue = @_;
+	while(@queue) {
+		my $header = pop @queue;
+		next if exists $deps{$header};
+
+		$deps{$header} = [] unless exists $deps{$header};
+
+		my $path = search($header);
+		next unless $path;
+
+		open(my $file, '<', $path) or die($!);
+		chomp(my @lines = <$file>);
+		close($file);
+
+		for my $line (@lines) {
+			if(my($dep) = ($line =~ m/^#\s*include <([^>]+)>/)) {
+				push @queue, $dep;
+				push @{$deps{$header}}, $dep;
+			}
+		}
+	}
+}
+
+sub print_cycle {
+	my $cycle = shift;
+
+	my $first = shift @$cycle;
+	my $last = pop @$cycle;
+
+	my $msg = "In file included";
+	printf "%s from %s,\n", $msg, $last if defined $last;
+
+	for my $header (reverse @$cycle) {
+		printf "%*.s from %s\n", length $msg, '', $header;
+	}
+
+	printf "%s: warning: recursive header inclusion\n", $first;
+}
+
+# Find and print the smallest cycle starting in the specified node.
+sub detect_cycles {
+	my @queue = map { [$_] } @_;
+	while(@queue) {
+		my $top = pop @queue;
+		my $name = $top->[-1];
+
+		for my $dep (@{$deps{$name}}) {
+			my $chain = [@$top, $dep];
+
+			if(grep { $_ eq $dep } @$top) {
+				print_cycle($chain);
+				return;
+			}
+
+			push @queue, $chain;
+		}
+	}
+}
+
+sub mangle {
+	$_ = shift;
+	s/\//__/g;
+	s/\./_/g;
+	s/-/_/g;
+	$_;
+}
+
+sub escape {
+	$_ = shift;
+}
+
+# Output dependency graph in GraphViz language.
+sub graph {
+	printf "digraph {\n";
+
+	printf "\t/* vertices */\n";
+	for my $header (keys %deps) {
+		printf "\t%s [label=\"%s\"];\n",
+			mangle($header), escape($header);
+	}
+
+	printf "\n";
+
+	printf "\t/* edges */\n";
+	for my $header (keys %deps) {
+		for my $dep (@{$deps{$header}}) {
+			printf "\t%s -> %s;\n",
+				mangle($header), mangle($dep);
+		}
+	}
+
+	printf "}\n";
+}
-- 
1.5.4.1

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Pekka Enberg]

Hi Vegard,

Vegard Nossum wrote:
> @@ -0,0 +1,143 @@
> +#! /usr/bin/perl
> +#
> +# Detect cycles in the header file dependency graph
> +# Vegard Nossum <vegardno@ifi.uio.no>
> +#
> +
> +use strict;
> +use warnings;
> +
> +my @I = ('include');
> +my %deps = ();
> +
> +my @headers = grep { strip($_) } @ARGV;
> +
> +parse_all(@headers);
> +
> +detect_cycles(@headers);
> +#graph();

[snip]

> +exit;

> +# Output dependency graph in GraphViz language.
> +sub graph {

Shouldn't there be a command line option for printing out the GraphViz 
files?

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Vegard Nossum]

On 4/26/08, Pekka Enberg <penberg@cs.helsinki.fi> wrote:
> > +# Output dependency graph in GraphViz language.
> > +sub graph {
> >
>
>  Shouldn't there be a command line option for printing out the GraphViz
> files?

Hm. For now, it's a hidden feature that requires editing the script :-)

I didn't want to get into the lands of parsing options since we would
need to handle gcc options and skip arguments to those, etc.

Maybe it's better just to chuck the whole GraphViz thing. It's not
really that useful anyway.

Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Nick Andrew]

On Sat, Apr 26, 2008 at 04:17:15PM +0200, Vegard Nossum wrote:
> I didn't want to get into the lands of parsing options since we would
> need to handle gcc options and skip arguments to those, etc.

?

use Getopt::Std qw(getopts);

use vars qw($opt_g);

getopts('g');

[...]

if ($opt_g) {
	graph();
}

Nick.
-- 
PGP Key ID = 0x418487E7                      http://www.nick-andrew.net/
PGP Key fingerprint = B3ED 6894 8E49 1770 C24A  67E3 6266 6EB9 4184 87E7

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Jan Engelhardt]

On Saturday 2008-04-26 16:22, Nick Andrew wrote:
>On Sat, Apr 26, 2008 at 04:17:15PM +0200, Vegard Nossum wrote:
>> I didn't want to get into the lands of parsing options since we would
>> need to handle gcc options and skip arguments to those, etc.
>
>?
>
>use Getopt::Std qw(getopts);
>use vars qw($opt_g);
>getopts('g');
>[...]
>if ($opt_g) {
>	graph();
>}

Try this, at least it is known to handle pass_through, which
is _just what we want_ for handling unknown options:

	use Getopt::Long;
	&Getopt::Long::Configure(qw(bundling pass_through));
	&GetOptions("g" => \$opt_g, "I" => \@include_paths);

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Adrian Bunk]

On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
> Hi Sam,
> 
> Maybe something like this could be useful for cleaning up headers (and
> maintaining that cleanliness once it has been achieved). What do you think?
> 
> (One thing which might or might not be good is that 'make headerdep' will
>  also compile using CC if they're not already compiled. If this should be
>  fixed, I think you'd know how to do it.)

This way you only catch problems in the current kernel configuration.

The only problems are under include/, and you should be able to do this 
by parsing all headers and without hooking into the build system.

> Vegard
>...

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Julia Lawall]

On Sat, 26 Apr 2008, Adrian Bunk wrote:

> On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
> > Hi Sam,
> > 
> > Maybe something like this could be useful for cleaning up headers (and
> > maintaining that cleanliness once it has been achieved). What do you think?
> > 
> > (One thing which might or might not be good is that 'make headerdep' will
> >  also compile using CC if they're not already compiled. If this should be
> >  fixed, I think you'd know how to do it.)
> 
> This way you only catch problems in the current kernel configuration.
> 
> The only problems are under include/, and you should be able to do this 
> by parsing all headers and without hooking into the build system.

I guess one would still have to consider all of the possible permutations 
of values of configuration variables, to interpret the #ifdefs that have 
an impact on what is included?  A quick grep suggests that they are mostly 
related to  __KERNEL__, so perhaps it would not be too expensive to do.

julia

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Vegard Nossum]

On 4/26/08, Julia Lawall <julia@diku.dk> wrote:
> On Sat, 26 Apr 2008, Adrian Bunk wrote:
>
>  > On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
>  > > Hi Sam,
>  > >
>  > > Maybe something like this could be useful for cleaning up headers (and
>  > > maintaining that cleanliness once it has been achieved). What do you think?
>  > >
>  > > (One thing which might or might not be good is that 'make headerdep' will
>  > >  also compile using CC if they're not already compiled. If this should be
>  > >  fixed, I think you'd know how to do it.)
>  >
>  > This way you only catch problems in the current kernel configuration.
>  >
>  > The only problems are under include/, and you should be able to do this
>  > by parsing all headers and without hooking into the build system.
>
>
> I guess one would still have to consider all of the possible permutations
>  of values of configuration variables, to interpret the #ifdefs that have
>  an impact on what is included?  A quick grep suggests that they are mostly
>  related to  __KERNEL__, so perhaps it would not be too expensive to do.

We don't interpret #defines or #ifdefs or #ifs at all. If we did this,
then the program would detect no cycles (because of the header
guards).

The rationale is that any cycle at all, regardless of any guards that
might exist, is wrong. In my opinion anwyay :-)

Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Vegard Nossum]

On 4/26/08, Adrian Bunk <bunk@kernel.org> wrote:
> On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
>  > Hi Sam,
>  >
>  > Maybe something like this could be useful for cleaning up headers (and
>  > maintaining that cleanliness once it has been achieved). What do you think?
>  >
>  > (One thing which might or might not be good is that 'make headerdep' will
>  >  also compile using CC if they're not already compiled. If this should be
>  >  fixed, I think you'd know how to do it.)
>
>
> This way you only catch problems in the current kernel configuration.
>
>  The only problems are under include/, and you should be able to do this
>  by parsing all headers and without hooking into the build system.

This seems correct. Then a solution similar to 'make headers_check'
should be used.

Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Matthew Wilcox]

On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
> Maybe something like this could be useful for cleaning up headers (and
> maintaining that cleanliness once it has been achieved). What do you think?
> 
> Subject: [PATCH] headerdep: a tool for detecting inclusion cycles in header files

Do we actually have inclusion cycles in header files?  I remember gcc
warning about them when we were working on the parisc port (because we
needed includes that differed from x86).  Has the new build system got
rid of these warnings?

I think a more useful tool would be one which mapped something like
'use of down()' to 'needs to include <linux/semaphore.h>'.  It needs
to be at least somewhat done by hand because there are rules such
as 'include linux/spinlock.h to get spinlock_t' (which is actually
defined in linux/spinlock_types.h), but you want people to include
<linux/completion.h> directly rather than rely on it being pulled in
through linux/sched.h, for example.

It's further complicated by multi-file drivers, such as qla2xxx.  Each
file includes qla_def.h which includes a lot of the necessary header
files for them ... but then each file will include a few more header
files that it needs.

So some implicit includes are _good_ and other implicit includes are
_bad_ (as they hurt when trying to rationalise the header files).
Anyone who likes complexity and fuzzy logic like this want to take a
stab at writing such a tool?

-- 
Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Adrian Bunk]

On Sat, Apr 26, 2008 at 10:17:14AM -0600, Matthew Wilcox wrote:
> On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
> > Maybe something like this could be useful for cleaning up headers (and
> > maintaining that cleanliness once it has been achieved). What do you think?
> > 
> > Subject: [PATCH] headerdep: a tool for detecting inclusion cycles in header files
> 
> Do we actually have inclusion cycles in header files?
>...

Yes, e.g. between include/linux/vmstat.h and include/linux/mm.h that 
directly #include each other.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

"Anyone who likes complexity and fuzzy logic" (Re: [PATCH] headerdep:...)

[Oleg Verych]

Matthew Wilcox @ Sat, 26 Apr 2008 10:17:14 -0600:

> I think a more useful tool would be one which mapped something like
> 'use of down()' to 'needs to include <linux/semaphore.h>'.  It needs
> to be at least somewhat done by hand because there are rules such
> as 'include linux/spinlock.h to get spinlock_t' (which is actually
> defined in linux/spinlock_types.h), but you want people to include
><linux/completion.h> directly rather than rely on it being pulled in
> through linux/sched.h, for example.
>
> It's further complicated by multi-file drivers, such as qla2xxx.  Each
> file includes qla_def.h which includes a lot of the necessary header
> files for them ... but then each file will include a few more header
> files that it needs.
(gee...)
> So some implicit includes are _good_ and other implicit includes are
> _bad_ (as they hurt when trying to rationalise the header files).
> Anyone who likes complexity and fuzzy logic like this want to take a
> stab at writing such a tool?

Why? Why GNU C compiler developers didn't do such (obviously useful)
tool? C compiler (some part of it) *is* responsible for parsing,
tokenizing, etc. Why there is development of never-ending buggy
optimizations only[0]?


Matthew, i know you've asked for regular expressions ninjas once, here
simple example.

Syntax highlighting for text editors is the most notable
invention/implementation for ease of programming in last 20 years or so.

Question: why any parser, e.g. GNU/FOSS [C, SED, AWK, ELISP], Perl,
Python, do NOT have option to output OWN highlighted syntax? Don't those
parsers know what they parse, rules, syntax errors, etc.[1]? (Note: at
least framework in parser, so that trivial extending/configuring would be
possible).


Is it really so complex?


=[0]= rant =[0]=

Isn't that hardware had developed in exponential rate toward speed and
cache/RAM size, so any bloat and huge volumes of sources without flexible
configuration systems (to download and work with e.g. only one GCC or
Linux port) are handled quickly?

=[1]= rant =[1]=

No, unreadable and buggy regexp-based highlighting is everywhere with
never-ending features added WRT basic regular expressions!

For those Perl hackers out there: why mister Wall is attributed to
invent non greedy RE match, why he did so by introducing non portable
and non-readable syntax to already crappy RE?

Simple BRE based idea: '\{0, s\}'. Just like `sed` had overcame second
RE basic pronciple: first-match, by using flags 's///here'.

No, let's invent crutches!

Oh, crap....
--
sed 'sed && sh + olecom = love' << ''
-o--=O`C
 #oo'L O
<___=E M

Re: "Anyone who likes complexity and fuzzy logic" (Re: [PATCH] headerdep:...)

[Matthew Wilcox]

On Wed, Apr 30, 2008 at 07:57:16PM +0200, Oleg Verych wrote:
> Why? Why GNU C compiler developers didn't do such (obviously useful)
> tool? C compiler (some part of it) *is* responsible for parsing,
> tokenizing, etc. Why there is development of never-ending buggy
> optimizations only[0]?

Shut up.

-- 
Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Adrian Bunk]

On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
> Hi Sam,
> 
> Maybe something like this could be useful for cleaning up headers (and
> maintaining that cleanliness once it has been achieved). What do you think?
>...

And another note (after looking at the Cc list):

Header cleanup is *not* something suitable as a first task for a janitor.

The interesting cases are non-trivial.

And you need cross compilers for all architectures since fiddling with 
#include's under include/ breaks code left and right that only compiled 
due to some implicit #include (and if it still works due to another 
implicit #include on x86 the latter might not be present on all 
architectures).

> Vegard
>...

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Vegard Nossum]

On 4/26/08, Adrian Bunk <bunk@kernel.org> wrote:
> On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
>
> > Hi Sam,
>  >
>  > Maybe something like this could be useful for cleaning up headers (and
>  > maintaining that cleanliness once it has been achieved). What do you think?
>
> >...
>
>  And another note (after looking at the Cc list):
>
>  Header cleanup is *not* something suitable as a first task for a janitor.

Hehe, yes, I could not agree more!

I have been trying to resolve some of these errors myself, but it's
incredibly hard to get right.

The reason I CCed kernel-janitors is that this IS a janitorial
project. But I am not implying that janitor means "newbie" or trivial.
At least the way I see it, janitor work is cleaning up, but not
necessarily easy work. But I agree, definitely not a first task job.

>  The interesting cases are non-trivial.
>
>  And you need cross compilers for all architectures since fiddling with
>  #include's under include/ breaks code left and right that only compiled
>  due to some implicit #include (and if it still works due to another
>  implicit #include on x86 the latter might not be present on all
>  architectures).

Yep. I have been compiling cross-compilers myself. As a btw, I had
already started some project to distribute binary cross-compilers
http://folk.uio.no/vegardno/crosstool/ for the purpose of making
cross-compiling easier to get started with. (It would be cool to have
a complete suite of working cross-compilers in a single download.)

Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Adrian Bunk]

On Sat, Apr 26, 2008 at 06:57:09PM +0200, Vegard Nossum wrote:
> On 4/26/08, Adrian Bunk <bunk@kernel.org> wrote:
> > On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
> >
> > > Hi Sam,
> >  >
> >  > Maybe something like this could be useful for cleaning up headers (and
> >  > maintaining that cleanliness once it has been achieved). What do you think?
> >
> > >...
> >
> >  And another note (after looking at the Cc list):
> >
> >  Header cleanup is *not* something suitable as a first task for a janitor.
> 
> Hehe, yes, I could not agree more!
> 
> I have been trying to resolve some of these errors myself, but it's
> incredibly hard to get right.
> 
> The reason I CCed kernel-janitors is that this IS a janitorial
> project. But I am not implying that janitor means "newbie" or trivial.
> At least the way I see it, janitor work is cleaning up, but not
> necessarily easy work. But I agree, definitely not a first task job.

kernel-janitors is basically for "I'm new to kernel development and 
want an easy task".

> >  The interesting cases are non-trivial.
> >
> >  And you need cross compilers for all architectures since fiddling with
> >  #include's under include/ breaks code left and right that only compiled
> >  due to some implicit #include (and if it still works due to another
> >  implicit #include on x86 the latter might not be present on all
> >  architectures).
> 
> Yep. I have been compiling cross-compilers myself. As a btw, I had
> already started some project to distribute binary cross-compilers
> http://folk.uio.no/vegardno/crosstool/ for the purpose of making
> cross-compiling easier to get started with. (It would be cool to have
> a complete suite of working cross-compilers in a single download.)

"The source code for the binary files below can be downloaded from the 
 aforementioned project websites."

-> GPL violation

> Vegard

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Vegard Nossum]

On 4/26/08, Adrian Bunk <bunk@kernel.org> wrote:
> On Sat, Apr 26, 2008 at 06:57:09PM +0200, Vegard Nossum wrote:
>  > On 4/26/08, Adrian Bunk <bunk@kernel.org> wrote:
>  > >  And you need cross compilers for all architectures since fiddling with
>  > >  #include's under include/ breaks code left and right that only compiled
>  > >  due to some implicit #include (and if it still works due to another
>  > >  implicit #include on x86 the latter might not be present on all
>  > >  architectures).
>  >
>  > Yep. I have been compiling cross-compilers myself. As a btw, I had
>  > already started some project to distribute binary cross-compilers
>  > http://folk.uio.no/vegardno/crosstool/ for the purpose of making
>  > cross-compiling easier to get started with. (It would be cool to have
>  > a complete suite of working cross-compilers in a single download.)
>
>
> "The source code for the binary files below can be downloaded from the
>   aforementioned project websites."
>
>  -> GPL violation

Thanks, corrected.

Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Jan Engelhardt]

On Saturday 2008-04-26 15:45, Vegard Nossum wrote:

>+exit;

exit is implicit.

>+# Get a file name that is relative to our include paths
>+sub strip {
>+	my $filename = shift;
>+
>+	for my $i (@I) {
>+		my $stripped = $filename;
>+		$stripped =~ s/^$i\///;

			s/^\Q$i\/\E//;

>+# Search for the file name in the list of include paths
>+sub search {
>+	my $filename = shift;
>+	return $filename if -f $filename;
>+
>+	for my $i (@I) {
>+		my $path = sprintf "%s/%s", $i, $filename;

		my $path = "$i/$filename";

>+		return $path if -f $path;
>+	}
>+
>+	return undef;
>+}
>+
>+sub parse_all {
>+	# Parse all the headers.
>+	my @queue = @_;
>+	while(@queue) {
>+		my $header = pop @queue;
>+		next if exists $deps{$header};
>+
>+		$deps{$header} = [] unless exists $deps{$header};
>+
>+		my $path = search($header);
>+		next unless $path;
>+
>+		open(my $file, '<', $path) or die($!);
>+		chomp(my @lines = <$file>);
>+		close($file);
>+
>+		for my $line (@lines) {
>+			if(my($dep) = ($line =~ m/^#\s*include <([^>]+)>/)) {

			$line =~ m/^#\s*include\s*<(.*?)>/

>+				push @queue, $dep;
>+				push @{$deps{$header}}, $dep;
>+			}
>+		}
>+	}
>+}
>+
>+sub print_cycle {
>+	my $cycle = shift;
>+
>+	my $first = shift @$cycle;
>+	my $last = pop @$cycle;
>+
>+	my $msg = "In file included";
>+	printf "%s from %s,\n", $msg, $last if defined $last;

	print "$msg from $last,\n" if defined $last;
>+
>+	for my $header (reverse @$cycle) {
>+		printf "%*.s from %s\n", length $msg, '', $header;

		print " " x length($msg), "from $header\n";

>+	}
>+
>+	printf "%s: warning: recursive header inclusion\n", $first;

	print "$first: warning: recursive header inclusion\n";

You seem to be addicted to printf?

>+}
>+
>+# Find and print the smallest cycle starting in the specified node.
>+sub detect_cycles {
>+	my @queue = map { [$_] } @_;
>+	while(@queue) {
>+		my $top = pop @queue;
>+		my $name = $top->[-1];
>+
>+		for my $dep (@{$deps{$name}}) {
>+			my $chain = [@$top, $dep];
>+
>+			if(grep { $_ eq $dep } @$top) {
>+				print_cycle($chain);
>+				return;
>+			}
>+
>+			push @queue, $chain;
>+		}
>+	}
>+}
>+
>+sub mangle {
>+	$_ = shift;
>+	s/\//__/g;
>+	s/\./_/g;
>+	s/-/_/g;
>+	$_;
>+}
>+
>+sub escape {
>+	$_ = shift;
>+}

Does escape() have... any use?

>+
>+# Output dependency graph in GraphViz language.
>+sub graph {
>+	printf "digraph {\n";
>+
>+	printf "\t/* vertices */\n";
>+	for my $header (keys %deps) {
>+		printf "\t%s [label=\"%s\"];\n",
>+			mangle($header), escape($header);
>+	}
>+
>+	printf "\n";
>+
>+	printf "\t/* edges */\n";
>+	for my $header (keys %deps) {
>+		for my $dep (@{$deps{$header}}) {
>+			printf "\t%s -> %s;\n",
>+				mangle($header), mangle($dep);
>+		}
>+	}
>+
>+	printf "}\n";
>+}

Might want to replace all those printfs too.

Re: [PATCH] headerdep: a tool for detecting inclusion cycles in header file

[Sam Ravnborg]

On Sat, Apr 26, 2008 at 03:45:54PM +0200, Vegard Nossum wrote:
> Hi Sam,
> 
> Maybe something like this could be useful for cleaning up headers (and
> maintaining that cleanliness once it has been achieved). What do you think?
Hi Vegard.

I really like the idea to use some automated checks to increase the
quality of our headers.
And that raises the question about what is the most important
issue we have with our headers and how do we detect them in the
best possible way?

To detect inclusion cycles in a configured kernel I really think
sparse is the better place to detect it. We have sparse as an
advenced sanity check tool and adding the possibility to detect
inclusion cycles should be easier than it was to cook up this
perl script.

But we have much more important issues.
In general we have far to many dependencies in the current headers
and too much code rely on headers being implicitly pulled.

We have headers that uses types we actually do not want to use
in the kernel.

We have headers that export stuff to userspace they shouldnt.

We have heders defining prototypes for non existing functions.

We have headers defining extern variables that no longer exists.

You could continue the list.
And some of the above topics are really newbies material to fix.

If you then decide to automate it then I would need a good
explanation why we did not use sparse before considering
including the tool in the kernel.

So I do not plan to apply this patch because this should be
done in sparse and not in a random perl script.

> 
> (One thing which might or might not be good is that 'make headerdep' will
>  also compile using CC if they're not already compiled. If this should be
>  fixed, I think you'd know how to do it.)

Not a big deal - we neither support this for sparse.


> +# Output dependency graph in GraphViz language.
> +sub graph {
> +	printf "digraph {\n";
> +
> +	printf "\t/* vertices */\n";
> +	for my $header (keys %deps) {
> +		printf "\t%s [label=\"%s\"];\n",
> +			mangle($header), escape($header);
> +	}
> +
> +	printf "\n";
> +
> +	printf "\t/* edges */\n";
> +	for my $header (keys %deps) {
> +		for my $dep (@{$deps{$header}}) {
> +			printf "\t%s -> %s;\n",
> +				mangle($header), mangle($dep);
> +		}
> +	}
> +
> +	printf "}\n";
> +}

I like this part. I would be nice to see a full dependency graph
for any file that kbuild builds.
But again maybe we should do this as a sparse backend?

	Sam