New dependency tracking system for make_kconfig.pl

From: Trent Piepho <xyzzy@speakeasy.org>

Restructure make_kconfig.pl and clean the code up some more.

The dependency tracking code is rewritten.  This version converts the
"depends on" and "select X if" lines into Perl expressions, which are
then evaluated.  This way all complex expressions are handled correctly. 
Dependencies are tracked recursively until all are found.  "select" lines
with an "if" clause are handled correctly; the selected variable is only
required when the "if" clause is true.

Another improvement is that hex/string/int variables that don't have
their dependencies met will not appear in the .config file.  They aren't
supposed to.

make_kconfig will fail with an error message if MODULES is turned off in
the Kernel's config, as building out of tree makes no sense in that
situation.

Signed-off-by: Trent Piepho <xyzzy@speakeasy.org>

1 files changed, 264 insertions, 201 deletions

diff --git a/v4l/scripts/make_kconfig.pl b/v4l/scripts/make_kconfig.pl
index a9db697e9..6f1b108c1 100755
--- a/v4l/scripts/make_kconfig.pl
+++ b/v4l/scripts/make_kconfig.pl
@@ -1,5 +1,6 @@
 #!/usr/bin/perl
 use FileHandle;
+use strict;
 
 my %depend = ();
 my %minver = ();
@@ -9,18 +10,18 @@ my %hexopt = ();
 my %tristate = ();
 my %kernopts = ();
 my %depmods = ();
-my $version, $level, $sublevel, $kernver;
+my ($version, $level, $sublevel, $kernver);
 
-my $kernel=shift;
-my $force_kconfig=shift;
+my $kernel = shift;
+my $force_kconfig = shift;
 
 my $debug=0;
 
 ###########################################################
 # Read a .config file (first argument) and put the resulting options in a
-# hash which is returned.  This subroutine should be called in a hash
+# hash, which is returned.  This subroutine should be called in a hash
 # context or it will not be very useful.
-sub process_config ($)
+sub process_config($)
 {
 	my $filename = shift;
 	my %conf;
@@ -29,11 +30,12 @@ sub process_config ($)
 	open $in, $filename or die "File not found: $filename";
 	while (<$in>) {
 		if (/^CONFIG_(\w+)\s*=\s*(\S.*?)\s*$/) {
-			$conf{$1} = $2;
+			my $c = \($conf{$1} = $2);
+			$$c =~ y/nmy/012/ if $$c =~ /^.$/;
 			next;
 		}
 		if (/^# CONFIG_(\w+) is not set$/) {
-			$conf{$1} = 'n';
+			$conf{$1} = 0;
 			next;
 		}
 		unless (/^#|$/) {
@@ -49,10 +51,8 @@ sub add_bool($)
 	my $arg=shift;
 
 	exists $config{$arg} or die "Adding unknown boolean '$arg'";
-	$tristate{$arg}="bool";
-	printf "Boolean:%s\n",$arg if $debug;
-
-	$kernopts{$arg}='y';
+	print "Boolean: $arg\n" if $debug;
+	$tristate{$arg} = "bool";
 }
 
 sub add_tristate($)
@@ -60,9 +60,10 @@ sub add_tristate($)
 	my $arg=shift;
 
 	exists $config{$arg} or die "Adding unknown tristate '$arg'";
+	print "Tristate: $arg\n" if $debug;
 	$tristate{$arg}="tristate";
-
-	$kernopts{$arg}='m';
+	# tri default is 'm'
+	$config{$arg} = 1 if($config{$arg});
 }
 
 sub add_int($)
@@ -96,18 +97,17 @@ sub set_hex_value($$)
 	my $val = shift;
 
 	exists $hexopt{$key} or die "Default for unknown hex option '$key'";
-	$hexopt{$key} = "0x".$val;
+	$hexopt{$key} = "0x$val";
 }
 
 sub add_config($)
 {
-	my $arg=shift;
+	my $arg = shift;
 
-	if ($arg =~ m/^(\w+)/) {
-		# Have option default to 'on'
-		$config{$1} = 1;
+	if ($arg =~ /^(\w+)\s*$/) {
+		$config{$1} = 2;
 	} else {
-	    die "Do not understand config variable '$arg'";
+		die "Do not understand config variable '$arg'";
 	}
 }
 
@@ -120,90 +120,172 @@ sub disable_config($)
 	$config{$key} = 0 if (exists $config{$key});
 }
 
-#################################################################
-# Make a list of dependencies and the number of references for it
-sub check_deps($$)
+# %{$depend{'FOO'}} lists all variables which depend on FOO.  This is the
+# reverse of the variables that FOO depends on.
+my %depend = ();
+sub finddeps($$)
 {
-	my $key=shift;
-	my $arg=shift;
-
-	if ($depmods{$key}) {
-		$depmods{$key}=$depmods{$key}." $arg";
-	} else {
-		$depmods{$key}=$arg;
-	}
-	$arg=$arg." ";
-
-	while ($arg ne "") {
-		if ($arg =~ m/^([A-Z0-9_]+) /) {
-			my $val=$1;
-			my $prev=$depend{$val};
-			$depend { $val } = 1+$prev;
-		}
-		$arg =~ s/^[^ ]+[ ]+//;
-	}
+	my $key = shift;
+	my $deps = shift;
 
-	return $ok;
+	$deps =~ s/^\W+//;
+	$depend{$_}{$key} = 1 foreach(split(/\W[\Wynm]*/, $deps));
 }
 
-######################################################
-# Checks if all dependencies for the key are satisfied
-sub deps_ok($)
+# @{$depends{'FOO'}} is a list of dependency expressions that FOO depends
+# on.  This is the reverse of the variables that depend on FOO.
+my %depends = ();
+sub depends($$)
 {
-	my $key=shift;
-	my $arg=$depmods{$key};
-	my $ok=1;
+	my $key = shift;
+	my $deps = shift;
 
-	if ($arg eq "") {
-		return $ok;
+	if(!defined $key || $key eq '') {
+		print "Got bad key with $deps\n";
+		return;
 	}
+	finddeps($key, $deps);
+	push @{$depends{$key}}, $deps;
+}
 
-	$arg=$arg." ";
-
-
-	printf "$key: deps are '$arg'\n" if $debug;
+sub selects($$$)
+{
+	my $key = shift;
+	my $select = shift;
+	my $if = shift;
+
+	finddeps($key, $select);
+	if(defined $if) {
+		finddeps($key, $if);
+		# Transform "select X if Y" into "depends on !Y || X"
+		$select = "!($if) || ($select)";
+	}
+	push @{$depends{$key}}, $select;
+}
 
-	while ($arg ne "") {
-		if ($arg =~ m/^([A-Z0-9_]+) /) {
-			if ((! exists $kernopts {$1}) || ($kernopts {$1} eq 'n')) {
-				printf "$key: Required kernel opt '$1' is not present\n";
-				$ok=0;
+# Needs:
+# %depend <- %depend{FOO} lists the variables that depend on FOO
+# %depends <- %depends{FOO} lists the dependency expressions for FOO
+# %config <- the value of all media variables
+# %kernopts <- the value of all kernel variables (including media ones)
+#
+# Checks the dependencies of all media variables, recursively.  Returns
+# a new hash that has the new values of all media variables.
+sub checkdeps()
+{
+	my %allconfig;
+
+	@allconfig{keys %depend} = @kernopts{keys %depend};
+	@allconfig{keys %config} = values %config;
+	# Set undef values to 0
+	map { defined $_ or $_ = 0 } values %allconfig;
+
+	# First run, check deps for all the v4l-dvb variables.  Following
+	# runs, check all variables which depend on a variable that was
+	# changed.  Stop when no more variables change.
+	for(my %changed = (), my @tocheck = keys %config; @tocheck;
+	    @tocheck = keys %changed, %changed = ()) {
+		foreach (@tocheck) {
+			next unless($allconfig{$_});	# skip disabled vars
+			if (!checkvardeps($_)) {
+				$changed{$_} = 1 foreach keys %{$depend{$_}};
 			}
 		}
-		if ($arg =~ m/^\!([A-Z0-9_]+) /) {
-			if ($kernopts {$1} eq 'y') {
-				printf "$key: Driver is incompatible with  '$1'\n";
-				$ok=0;
+	}
+	return map { $_ => $allconfig{$_} } keys %config;
+
+	# Check the dependencies of a variable, if one fails the variable
+	# is set to 0.  Returns 0 if the variable failed, 1 if it passed.
+	sub checkvardeps($) {
+		my $key = shift;
+		my $deps = $depends{$key};
+		foreach (@$deps) {
+			if (!eval(toperl($_))) {
+				$allconfig{$key} = 0;
+				return 0;
 			}
 		}
-		$arg =~ s/^[^ ]+ //;
+		return 1;
 	}
 
-	return $ok;
+	# Convert a Kconfig expression to a Perl expression
+	sub toperl($)
+	{
+		$_ = shift;
+
+		# Turn n,m,y into 0,1,2
+		s/\bn\b/0/g; s/\bm\b/1/g; s/\by\b/2/g;
+
+		# Turn = into ==, but keep != as != (ie. not !==)
+		s/(?<!!)=/==/g;
+
+		# Turn FOO into the value of $allconfig{FOO}
+		s/\b([A-Za-z_]\w*)\b/$allconfig{$1}/g;
+
+		return $_;
+	}
 }
 
-# List of all kconfig files read in, could be used to make dependencies
-# for the output combined Kconfig file.
-my @kconfigfiles = ();
+# Text to be added to disabled options
+my $disabled_msg = <<'EOF';
+	---help---
+	  WARNING! This driver needs at least kernel %s!  It may not
+	  compile or work correctly on your kernel, which is too old.
 
-# Read and parse a Kconfig file.  First base of source directory tree the
-# second is the file (with path).  Recursivly parses Kconfig files from
-# 'source' directives.
+EOF
+
+# List of all kconfig files read in, used to make dependencies for the
+# output combined Kconfig file.
+my @kconfigfiles = ();
 
+# Read and parse a Kconfig file.  First argument is base of source
+# directory tree, the second is the file to open (with path).  Recursivly
+# parses Kconfig files from 'source' directives.
+#
 # Prints to OUT a combined version of all the Kconfig files.  This file
 # is edited slightly to disable options that need a newer kernel.
 sub open_kconfig($$) {
 	my ($dir,$file)=@_;
 	my $in = new FileHandle;
-	my $disabled=0;
 	my $key;
+	my $disabled = 0;
+	my $in_help = 0;
+	my $default_seen = 0;
 
 	print "Opening $file\n" if $debug;
-	open $in, "$file" or die "File not found: $file";
+	open $in, '<', $file or die "File not found: $file";
 	push @kconfigfiles, $file;
 	while (<$in>) {
+		# In our Kconfig files, the first non-help line after the
+		# help text always has no indention.  Technically, the
+		# help text is ended by just by the indention decreasing,
+		# but that is a pain to keep track of.
+		if ($in_help && /^\S/) {
+			$in_help = 0;
+		} elsif ($in_help) {
+			# Still inside help text
+			next;
+		}
+
+		# Start of help text
+		if (/^\s*(---)?help(---)?\s*$/) {
+			$in_help = 1;
+			# Insert VIDEO_KERNEL_VERSION dependency, default
+			# n line, and help text note for disabled drivers.
+			if ($disabled) {
+				if(exists $tristate{$key} && !$default_seen) {
+					print OUT "\tdefault n\n";
+				}
+				print OUT "\tdepends on VIDEO_KERNEL_VERSION\n";
+				$_ = sprintf($disabled_msg, $minver{$key});
+			}
+			next;
+		}
+		# No help text should get processed past this point
+		$in_help and die "I'm very confused";
+
 		# start of a new stanza, reset
-		if (m/^\w/) {
+		if (/^\w/) {
 			$disabled = 0;
 			$default_seen = 0;
 			$key = undef;
@@ -211,78 +293,60 @@ sub open_kconfig($$) {
 
 		if (m|^\s*source\s+"([^"]+)"\s*$| ||
 		    m|^\s*source\s+(\S+)\s*$|) {
-			open_kconfig($dir,"$dir/$1");
+			open_kconfig($dir, "$dir/$1");
+			$_ = '';	# don't print the source line itself
 			next;
 		}
-		if (m|^\s+depends on\s+(.+?)\s*$|) {
-			check_deps ($key,$1);
-		}
-		# If a "select" dependency is not satisfied, that
-		#    dependency is broken
-		if (m|^\s+select\s+(.+?)\s*(if .*?)?\s*$|) {
-			check_deps ($key,$1);
-		}
-		if (m|^\s+bool(ean)?\s|) {
-			add_bool($key);
-		}
-		if (m|^\s+tristate\s|) {
-			add_tristate($key);
-		}
-		if (m|^\s+int\s|) {
-			add_int($key);
-		}
-		if (m|^\s+hex\s|) {
-			add_hex($key);
+
+		if (m|^\s*config (\w+)\s*$|) {
+			$key = $1;
+			add_config($key);
+
+			if (exists $minver{$key} &&
+			    cmp_ver($minver{$key}, $kernver) > 0) {
+				$disabled = 1;
+				disable_config($key);
+				print "$key: Requires at least kernel $minver{$key}\n";
+				print OUT "# $key disabled for insufficient kernel version\n";
+			} else {
+				$disabled=0;
+			}
+		} elsif (m|^\s*comment\s+"[^"]*"\s*$|) {
+			$key = 'comment';
+		} elsif (m|^\s*menu\s+"[^"]*"\s*$|) {
+			$key = 'menu';
 		}
+
+		# Don't process any directives in comment blocks (or menus)
+		next if ($key eq 'comment' || $key eq 'menu');
+
+		add_bool($key) if(/^\s*bool(ean)?\s/);
+		add_tristate($key) if (/^\s*tristate\s/);
+		add_int($key) if (/^\s*int\s/);
+		add_hex($key) if (/^\s*hex\s/);
+
+		depends($key, $1) if (m|^\s*depends on\s+(.+?)\s*$|);
+		selects($key, $1, $3) if (m|^\s*select\s+(\w+)(\s+if\s+(.+?))?\s*$|);
+
 		# Get default for int options
-		if (m|^\s+default "(\d+)"| && exists $intopt{$key}) {
+		if (m|^\s*default "(\d+)"| && exists $intopt{$key}) {
 			set_int_value($key, $1);
+			next;
 		}
 		# Get default for hex options
-		if (m|^\s+default "(0x)?([[:xdigit:]]+)"| && exists $hexopt{$key}) {
+		if (m|^\s*default "(0x)?([[:xdigit:]]+)"| && exists $hexopt{$key}) {
 			set_hex_value($key, $2);
+			next;
 		}
 		# Override default for disabled tri/bool options
-		if (m/^\s+default (y|n|m|"yes"|"no")\s+(if .*)?$/ &&
+		# We don't care about the default for tri/bool options otherwise
+		if (m/^\s*default (y|n|m|"yes"|"no")(\s+if .*)?\s*$/ &&
 		    exists $tristate{$key} && $disabled) {
 			$default_seen = 1;
 			$_ = "\tdefault n\n";
-		}
-		# check for end of config definition for disabled drivers
-		# we need to make sure we've disabled it, and add a bit
-		# to the help text
-		if (m|^\s*(---)?help(---)?\s*$| && $disabled) {
-			if(exists $tristate{$key} && !$default_seen) {
-				print OUT "\tdefault n\n";
-			}
-			print OUT <<"EOF";
-	depends on VIDEO_KERNEL_VERSION
-	help
-	  WARNING! This driver needs at least kernel $minver{$key}!  It may not
-	  compile or work correctly on your kernel, which is too old.
-
-EOF
 			next;
 		}
-
-		if (m|^\s*config (\w+)\s*$|) {
-			$key=$1;
-			add_config ($1);
-
-			if (exists $minver{$key} &&
-			    cmp_ver($minver{$key}, $kernver) > 0) {
-				$disabled=1;
-				disable_config ($key);
-				print "$key requires version $minver{$key}\n";
-				print OUT "# $key disabled for insufficient kernel version\n";
-			} else {
-				printf "OK: $key requires version %s\n", exists $minver{$key}?$minver{$key}:"any" if $debug;
-				$disabled=0;
-			}
-		}
-
-		s/^main(menu\s\"[^\"]+)/\1 - DON'T CHANGE IT!/;
-
+	} continue {
 		print OUT $_;
 	}
 	close $in;
@@ -293,7 +357,7 @@ sub parse_versions()
 	my $in = new FileHandle;
 	my $ver;
 
-	open $in, "versions.txt" or die "File not found: versions.txt";
+	open $in, '<versions.txt' or die "File not found: versions.txt";
 	while (<$in>) {
 		if (/\[(\d+\.\d+\.\d+)\]/) {
 			$ver = $1;
@@ -335,9 +399,23 @@ sub cmp_ver($$)
 	return $v1_sublevel <=> $v2_sublevel;
 }
 
-# Get kernel's config settings
+# Get Kernel's config settings
 %kernopts = process_config("$kernel/.config");
 
+# Modules must be on, or building out of tree drivers makes no sense
+if(!$kernopts{MODULES}) {
+	print <<"EOF";
+You appear to have loadable modules turned off in your kernel.  You can
+not compile the v4l-dvb drivers, as modules, and use them with a kernel
+that has modules disabled.
+
+If you want to compile these drivers into your kernel, you should
+use 'make kernel-links' to link the source for these drivers into
+your kernel tree.  Then configure and compile the kernel.
+EOF
+	exit -1;
+}
+
 # Get minimum kernel version for our variables
 parse_versions();
 
@@ -346,11 +424,13 @@ get_version();
 
 print "Preparing to compile for kernel version $kernver\n";
 
-open OUT,">Kconfig" or die "Cannot write Kconfig file";
+kernelcheck();
 
+open OUT, ">Kconfig" or die "Cannot write Kconfig file";
 print OUT <<"EOF";
 mainmenu "V4L/DVB menu"
 source Kconfig.kern
+source Kconfig.sound
 config VIDEO_KERNEL_VERSION
 	bool "Enable drivers not supported by this kernel"
 	default n
@@ -372,44 +452,67 @@ config VIDEO_KERNEL_VERSION
 
 EOF
 
-open_kconfig ("../linux","../linux/drivers/media/Kconfig");
-open_kconfig (".","./Kconfig.sound");
-
-print OUT "source Kconfig.sound\n";
+open_kconfig('../linux', '../linux/drivers/media/Kconfig');
+open_kconfig('.', './Kconfig.sound');
 close OUT;
 
-# Create make dependency rule for the Kconfig
-open OUT, '>.kconfig.dep' or die "Cannot write .kconfig.dep";
-print OUT "Kconfig: ";
-print OUT join(" \\\n\t", @kconfigfiles), "\n";
-close OUT;
+# These options should default to off
+disable_config('DVB_AV7110_FIRMWARE');
+disable_config('DVB_CINERGYT2_TUNING');
+disable_config('DVB_FE_CUSTOMISE');
 
-while ( my ($key, $value) = each(%config) ) {
-		delete $depend{$key};
-}
+# Check dependencies
+my %newconfig = checkdeps();
 
-open OUT,">Kconfig.kern" or die "Cannot write Kconfig.kern file";
+# TODO: tell the user which options were disabled at this point
+%config = %newconfig;
 
-while ( my ($key, $value) = each(%depend) ) {
-	if ($kernopts{$key}) {
-		print OUT "# $key with $value refs\nconfig $key\n\ttristate\n\tdefault ".
-			$kernopts{$key}."\n\n";
-	} else {
-		print OUT "# $key with $value refs\nconfig $key\n\ttristate\n\tdefault n #not found\n\n";
-	}
+# Create Kconfig.kern, listing all non-media (i.e. kernel) variables
+# that something depended on.
+$depend{MODULES}{always} = 1;	# Make sure MODULES will appear
+open OUT, '>Kconfig.kern' or die "Cannot write Kconfig.kern file: $!";
+while (my ($key, $deps) = each %depend) {
+	next if exists $config{$key};	# Skip media variables
+
+	print OUT "# Needed by ", join(', ', keys %$deps), "\n";
+	print OUT "config $key\n\ttristate\n";
+	print OUT "\tdefault ", qw(n m y)[$kernopts{$key}], "\n\n";
 }
 close OUT;
 
-# These options should default to off
-disable_config('DVB_AV7110_FIRMWARE');
-disable_config('DVB_CINERGYT2_TUNING');
-disable_config('DVB_FE_CUSTOMISE');
+# Create make dependency rules for the Kconfig file
+open OUT, '>.kconfig.dep' or die "Cannot write .kconfig.dep file: $!";
+print OUT 'Kconfig: ';
+print OUT join(" \\\n\t", @kconfigfiles), "\n";
+close OUT;
 
-# Hack for check sound/oss/aci.h header
+# Produce a .config file if forced or one doesn't already exist
+if ($force_kconfig==1 || !-e '.config') {
+	open OUT, '>.config' or die "Cannot write .config file: $!";
+	foreach (keys %tristate) {
+		if ($config{$_}) {
+			print OUT "CONFIG_$_=", qw(n m y)[$config{$_}], "\n";
+		} else {
+			print OUT "# CONFIG_$_ is not set\n";
+		}
+	}
+	while (my ($key,$value) = each %intopt) {
+		print OUT "CONFIG_$key=$value\n" if($config{$key});
+	}
+	while (my ($key,$value) = each %hexopt) {
+		print OUT "CONFIG_$key=$value\n" if($config{$key});
+	}
+	close OUT;
+	print "Created default (all yes) .config file\n";
+}
+
+# Check for full kernel sources and print a warning
+sub kernelcheck()
+{
+	my $fullkernel="$kernel/fs/fcntl.c";
+	if (! -e $fullkernel) {
+		print <<"EOF2";
 
-my $fullkernel="$kernel/fs/fcntl.c";
-if (! -e $fullkernel) {
-	print <<"EOF2";
 ***WARNING:*** You do not have the full kernel sources installed.
 This does not prevent you from building the v4l-dvb tree if you have the
 kernel headers, but the full kernel source may be required in order to use
@@ -428,45 +531,5 @@ make all modules_install install
 Please see your distro's web site for instructions to build a new kernel.
 
 EOF2
-}
-
-# Recursively check for broken dependencies
-my $i;
-do {
-	$i=0;
-	while ( my ($key,$value) = each(%kernopts) ) {
-		if ($value ne 'n') {
-			if (!deps_ok($key)) {
-				$kernopts{$key}='n';
-			}
-			$i=$i+1;
-		}
 	}
-} until (!$disable);
-
-# Produce a .config file if it's forced or one doesn't already exist
-if (($force_kconfig eq 1) || !open IN,".config") {
-	open OUT,">.config" or die "Cannot write .config file";
-	while ( my ($key,$value) = each(%tristate) ) {
-		if (!$config{$key}) {
-			print OUT "# CONFIG_$key is not set\n";
-		} elsif ($kernopts{$key}) {
-			if ($kernopts{$key} eq 'n') {
-				print OUT "# CONFIG_$key is not set\n";
-			} else {
-				print OUT "CONFIG_$key=".$kernopts{$key}."\n";
-			}
-		} elsif ($value eq 'tristate') {
-			print OUT "CONFIG_$key=m\n";
-		} else { # must be 'bool'
-			print OUT "CONFIG_$key=y\n";
-		}
-	}
-	while ( my ($key,$value) = each(%intopt) ) {
-		print OUT "CONFIG_$key=$value\n";
-	}
-	while ( my ($key,$value) = each(%hexopt) ) {
-		print OUT "CONFIG_$key=$value\n";
-	}
-	close OUT;
 }