dh: Rewrite sequence handling

Rewrite the way we compute the sequences to ensure that:

 1) Rules target remain opaque (particularly "subtargets" are now
    also opaque).
 2) Opaque targets are run first, so they can run their subtargets
    before dh runs a command that depends on it.

This is the first half of fixing Debian#880840.

Signed-off-by: Niels Thykier <niels@thykier.net>

3 files changed, 270 insertions, 113 deletions

diff --git a/dh b/dh
index 0403d0ca..201baa77 100755
--- a/dh
+++ b/dh
@@ -9,6 +9,7 @@ dh - debhelper command sequencer
 use strict;
 use warnings;
 use Debian::Debhelper::Dh_Lib;
+use Debian::Debhelper::SequencerUtil;
 
 our $VERSION = DH_BUILTIN_VERSION;
 
@@ -364,10 +365,9 @@ if (! defined $sequence) {
 # Also support completely empty override targets.
 # Note: it's not safe to use rules_explicit_target before this check,
 # since it causes dh to be run.
-my $dummy_target="debhelper-fail-me";
 if ($sequence eq 'debian/rules' ||
     $sequence =~ /^override_dh_/ ||
-    $sequence eq $dummy_target) {
+    $sequence eq DUMMY_TARGET) {
 	exit 0;
 }
 
@@ -454,13 +454,13 @@ $sequences{'build-indep'} = [@bd];
 $sequences{'build-arch'} = [@bd];
 if (! compat(8)) {
 	# From v9, sequences take standard rules targets into account.
-	$sequences{build} = [@bd_minimal, rules("build-arch"), rules("build-indep")];
-	$sequences{'install-indep'} = [rules("build-indep"), @i];
-	$sequences{'install-arch'} = [rules("build-arch"), @i];
-	$sequences{'install'} = [rules("build"), rules("install-arch"), rules("install-indep")];
-	$sequences{'binary-indep'} = [rules("install-indep"), @b];
-	$sequences{'binary-arch'} = [rules("install-arch"), @ba, @b];
-	$sequences{binary} = [rules("install"), rules("binary-arch"), rules("binary-indep")];
+	$sequences{build} = [@bd_minimal, to_rules_target("build-arch"), to_rules_target("build-indep")];
+	$sequences{'install-indep'} = [to_rules_target("build-indep"), @i];
+	$sequences{'install-arch'} = [to_rules_target("build-arch"), @i];
+	$sequences{'install'} = [to_rules_target("build"), to_rules_target("install-arch"), to_rules_target("install-indep")];
+	$sequences{'binary-indep'} = [to_rules_target("install-indep"), @b];
+	$sequences{'binary-arch'} = [to_rules_target("install-arch"), @ba, @b];
+	$sequences{binary} = [to_rules_target("install"), to_rules_target("binary-arch"), to_rules_target("binary-indep")];
 }
 else {
 	$sequences{build} = [@bd];
@@ -574,7 +574,10 @@ if (! exists $sequences{$sequence}) {
 	error "Unknown sequence $sequence (choose from: ".
 		join(" ", sort keys %sequences).")";
 }
-my @sequence=optimize_sequence(@{$sequences{$sequence}});
+# In compat <= 9, the sequences are always inlined (those versions do not
+# recurse into debian/rules anyway).  In compat 10+, we never inline an
+# existing rules target.
+my @sequence = optimize_sequence(\%sequences, $sequence, (!compat(9) ? 0 : 1));
 
 # The list of all packages that can be acted on.
 my @packages=@{$dh{DOPACKAGES}};
@@ -670,7 +673,7 @@ foreach my $package (@packages) {
 			# everything (admittedly, it is bit of an over
 			# approximation)
 			# Related bug: #851071
-			my @seq = optimize_sequence(@{$sequences{'build'}});
+			my @seq = optimize_sequence(\%sequences, 'build', 1);
 			$optimized_build_seq = \@seq;
 		}
 		@log = @{$optimized_build_seq};
@@ -735,7 +738,7 @@ foreach my $i (0..$stoppoint) {
 	}
 	next unless @todo;
 
-	my $rules_target = rules_target($command);
+	my $rules_target = extract_rules_target_name($command);
 	if (defined $rules_target) {
 		# Don't pass DH_ environment variables, since this is
 		# a fresh invocation of debian/rules and any sub-dh commands.
@@ -895,42 +898,6 @@ sub run_override {
 	return @rest;
 }
 
-sub optimize_sequence {
-	my (@commands) = @_;
-	my (@sequence, %seen);
-	my $add=sub {
-		# commands can appear multiple times when sequences are
-		# inlined together; only the first should be needed
-		my $command=shift;
-		if (! $seen{$command}) {
-			$seen{$command}=1;
-			push @sequence, $command;
-		}
-	};
-	foreach my $command (@commands) {
-		my $rules_target=rules_target($command);
-		if (defined $rules_target &&
-		    ! defined rules_explicit_target($rules_target)) {
-			# inline the sequence for this implicit target
-			$add->($_) foreach optimize_sequence(@{$sequences{$rules_target}});
-		}
-		else {
-			$add->($command);
-		}
-	}
-	return @sequence;
-}
-
-sub rules_target {
-	my ($command) = @_;
-	if ($command =~ /^debian\/rules\s+(.*)/) {
-		return $1
-	}
-	else {
-		return undef;
-	}
-}
-
 sub stamp_target {
 	my ($command) = @_;
 	if ($command =~ s/^create-stamp\s+//) {
@@ -939,71 +906,6 @@ sub stamp_target {
 	return;
 }
 
-sub rules {
-	return "debian/rules ".join(" ", @_);
-}
-
-{
-my %targets;
-my $rules_parsed;
-
-sub rules_explicit_target {
-	# Checks if a specified target exists as an explicit target
-	# in debian/rules.
-	# undef is returned if target does not exist, 0 if target is noop
-	# and 1 if target has dependencies or executes commands.
-	my ($target) = @_;
-
-	if (! $rules_parsed) {
-		my $processing_targets = 0;
-		my $not_a_target = 0;
-		my $current_target;
-		open(MAKE, "LC_ALL=C make -Rrnpsf debian/rules $dummy_target 2>/dev/null |");
-		while (<MAKE>) {
-			if ($processing_targets) {
-				if (/^# Not a target:/) {
-					$not_a_target = 1;
-				}
-				else {
-					if (!$not_a_target && /^([^#:]+)::?\s*(.*)$/) {
-						# Target is defined. NOTE: if it is a dependency of
-						# .PHONY it will be defined too but that's ok.
-						# $2 contains target dependencies if any.
-						$current_target = $1;
-						$targets{$current_target} = ($2) ? 1 : 0;
-					}
-					else {
-						if (defined $current_target) {
-							if (/^#/) {
-								# Check if target has commands to execute
-								if (/^#\s*(commands|recipe) to execute/) {
-									$targets{$current_target} = 1;
-								}
-							}
-							else {
-								# Target parsed.
-								$current_target = undef;
-							}
-						}
-					}
-					# "Not a target:" is always followed by
-					# a target name, so resetting this one
-					# here is safe.
-					$not_a_target = 0;
-				}
-			}
-			elsif (/^# Files$/) {
-				$processing_targets = 1;
-			}
-		}
-		close MAKE;
-		$rules_parsed = 1;
-	}
-
-	return $targets{$target};
-}
-
-}
 
 sub warn_deprecated {
 	foreach my $deprecated ('until', 'after', 'before', 'remaining') {
diff --git a/lib/Debian/Debhelper/SequencerUtil.pm b/lib/Debian/Debhelper/SequencerUtil.pm
new file mode 100644
index 00000000..d78aa032
--- /dev/null
+++ b/lib/Debian/Debhelper/SequencerUtil.pm
@@ -0,0 +1,128 @@
+#!/usr/bin/perl
+#
+# Internal library functions for the dh(1) command
+
+package Debian::Debhelper::SequencerUtil;
+use strict;
+use warnings;
+use constant DUMMY_TARGET => 'debhelper-fail-me';
+
+use Exporter qw(import);
+
+our @EXPORT = qw(
+	extract_rules_target_name
+	to_rules_target
+	optimize_sequence
+	rules_explicit_target
+	DUMMY_TARGET
+);
+
+our (%EXPLICIT_TARGETS, $RULES_PARSED);
+
+sub extract_rules_target_name {
+	my ($command) = @_;
+	if ($command =~ m{^debian/rules\s++(.++)}) {
+		return $1
+	}
+	return;
+}
+
+sub to_rules_target  {
+	return 'debian/rules '.join(' ', @_);
+}
+
+sub optimize_sequence {
+	my ($sequences, $sequence_name, $always_inline) = @_;
+	my (@sequence, @targets, %seen, %non_inlineable_targets, @stack);
+	push(@stack, [@{$sequences->{$sequence_name}}]);
+	while (@stack) {
+		my $current_sequence = pop(@stack);
+	  COMMAND:
+		while (@{$current_sequence}) {
+			my $command = shift(@{$current_sequence});
+			my $rules_target=extract_rules_target_name($command);
+			if (defined($rules_target) &&
+				! exists($non_inlineable_targets{$rules_target}) &&
+				! defined(rules_explicit_target($rules_target))) {
+
+				# inline the sequence for this implicit target.
+				push(@stack, $current_sequence);
+				$current_sequence = [@{$sequences->{$rules_target}}];
+				next COMMAND;
+			} else {
+				if (defined($rules_target) and not $always_inline) {
+					next COMMAND if exists($non_inlineable_targets{$rules_target});
+					my @opaque_targets = ($rules_target);
+					while (my $opaque_target = pop(@opaque_targets)) {
+						for my $c (@{$sequences->{$opaque_target}}) {
+							my $subtarget = extract_rules_target_name($c);
+							next if not defined($subtarget);
+							next if exists($non_inlineable_targets{$subtarget});
+							$non_inlineable_targets{$subtarget} = $rules_target;
+						}
+					}
+					push(@targets, $command) if not $seen{$command}++;
+				} elsif (! $seen{$command}) {
+					$seen{$command} = 1;
+					push(@sequence, $command);
+				}
+			}
+		}
+	}
+	return (@targets, @sequence);
+}
+
+
+sub rules_explicit_target {
+	# Checks if a specified target exists as an explicit target
+	# in debian/rules.
+	# undef is returned if target does not exist, 0 if target is noop
+	# and 1 if target has dependencies or executes commands.
+	my ($target) = @_;
+
+	if (! $RULES_PARSED) {
+		my $processing_targets = 0;
+		my $not_a_target = 0;
+		my $current_target;
+		open(MAKE, "LC_ALL=C make -Rrnpsf debian/rules ${\DUMMY_TARGET} 2>/dev/null |");
+		while (<MAKE>) {
+			if ($processing_targets) {
+				if (/^# Not a target:/) {
+					$not_a_target = 1;
+				} else {
+					if (!$not_a_target && m/^([^#:]+)::?\s*(.*)$/) {
+						# Target is defined. NOTE: if it is a dependency of
+						# .PHONY it will be defined too but that's ok.
+						# $2 contains target dependencies if any.
+						$current_target = $1;
+						$EXPLICIT_TARGETS{$current_target} = ($2) ? 1 : 0;
+					} else {
+						if (defined($current_target)) {
+							if (m/^#/) {
+								# Check if target has commands to execute
+								if (m/^#\s*(commands|recipe) to execute/) {
+									$EXPLICIT_TARGETS{$current_target} = 1;
+								}
+							} else {
+								# Target parsed.
+								$current_target = undef;
+							}
+						}
+					}
+					# "Not a target:" is always followed by
+					# a target name, so resetting this one
+					# here is safe.
+					$not_a_target = 0;
+				}
+			} elsif (m/^# Files$/) {
+				$processing_targets = 1;
+			}
+		}
+		close MAKE;
+		$RULES_PARSED = 1;
+	}
+
+	return $EXPLICIT_TARGETS{$target};
+}
+
+1;
diff --git a/t/dh-sequencer.t b/t/dh-sequencer.t
new file mode 100755
index 00000000..8f554594
--- /dev/null
+++ b/t/dh-sequencer.t
@@ -0,0 +1,127 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use Test::More;
+
+use Debian::Debhelper::SequencerUtil;
+
+# Shorten variants of the sequences.
+my @bd_minimal = qw{
+	dh_testdir
+};
+my @bd = (qw{
+	dh_auto_configure
+	dh_auto_build
+	dh_auto_test
+});
+my @i = (qw{
+	dh_testroot
+	dh_prep
+	dh_auto_install
+
+	dh_install
+	dh_missing
+});
+my @ba=qw{
+	dh_strip
+	dh_makeshlibs
+	dh_shlibdeps
+};
+my @b=qw{
+	dh_installdeb
+	dh_gencontrol
+	dh_builddeb
+};
+
+my %sequences = (
+    'build-indep' => [@bd_minimal, @bd],
+    'build-arch'  => [@bd_minimal, @bd],
+    'build'       => [@bd_minimal, to_rules_target("build-arch"), to_rules_target("build-indep")],
+
+    'install-indep' => [to_rules_target("build-indep"), @i],
+    'install-arch'  => [to_rules_target("build-arch"), @i],
+    'install'       => [to_rules_target("build"), to_rules_target("install-arch"), to_rules_target("install-indep")],
+
+    'binary-indep' => [to_rules_target("install-indep"), @b],
+    'binary-arch'  => [to_rules_target("install-arch"), @ba, @b],
+    'binary'       => [to_rules_target("install"), to_rules_target("binary-arch"), to_rules_target("binary-indep")],
+);
+
+
+plan tests => 9;
+
+# We will horse around with %EXPLICIT_TARGETS in this test; it should
+# definitely not attempt to read d/rules or the test will be break.
+$Debian::Debhelper::SequencerUtil::RULES_PARSED = 1;
+
+
+is_deeply(
+    [optimize_sequence(\%sequences, 'build')],
+    [@bd_minimal, @bd],
+    'Inlined build sequence matches build-indep/build-arch');
+
+is_deeply(
+    [optimize_sequence(\%sequences, 'install')],
+    [@bd_minimal, @bd, @i],
+    'Inlined install sequence matches build-indep/build-arch + install commands');
+
+is_deeply(
+    [optimize_sequence(\%sequences, 'binary-arch')],
+    [@bd_minimal, @bd, @i, @ba, @b],
+    'Inlined binary-arch sequence has all the commands');
+
+is_deeply(
+    [optimize_sequence(\%sequences, 'binary-indep')],
+    [@bd_minimal, @bd, @i, @b],
+    'Inlined binary-indep sequence has all the commands except @bd');
+
+is_deeply(
+    [optimize_sequence(\%sequences, 'binary')],
+    [@bd_minimal, @bd, @i, @ba, @b],
+    'Inlined binary sequence has all the commands');
+
+{
+    local $Debian::Debhelper::SequencerUtil::EXPLICIT_TARGETS{'build'} = 1;
+
+    is_deeply(
+        [optimize_sequence(\%sequences, 'binary')],
+        [to_rules_target('build'), @i, @ba, @b],
+        'Inlined binary sequence has all the commands but build target is opaque');
+
+    is_deeply(
+        [optimize_sequence(\%sequences, 'build')],
+        [@bd_minimal, @bd],
+        'build sequence is inlineable');
+
+}
+
+{
+    local $Debian::Debhelper::SequencerUtil::EXPLICIT_TARGETS{'install-arch'} = 1;
+
+    is_deeply(
+        [optimize_sequence(\%sequences, 'binary')],
+		# @bd_minimal, @bd and @i should be "-i"-only, @ba + @b should be both.
+		# Unfortunately, optimize_sequence cannot show that.
+        [to_rules_target('install-arch'), @bd_minimal, @bd, @i, @ba, @b],
+        'Inlined binary sequence has all the commands');
+}
+
+{
+	local $Debian::Debhelper::SequencerUtil::EXPLICIT_TARGETS{'install-arch'} = 1;
+	local $Debian::Debhelper::SequencerUtil::EXPLICIT_TARGETS{'build'} = 1;
+
+	my $actual = [optimize_sequence(\%sequences, 'binary')];
+	# @i should be "-i"-only, @ba + @b should be both.
+	# Unfortunately, optimize_sequence cannot show that.
+	my $expected = [to_rules_target('build'), to_rules_target('install-arch'), @i, @ba, @b];
+	# Permit some fuzz on the order between build and install-arch
+	if ($actual->[0] eq to_rules_target('install-arch')) {
+		$expected->[0] = to_rules_target('install-arch');
+		$expected->[1] = to_rules_target('build');
+	}
+	is_deeply(
+		$actual,
+		$expected,
+		'Inlined binary sequence has all the commands');
+}