dgit: Replace branch_is_gdr with a history walker

The debrebase-last approach is fundamentally wrong, because, for
example, cloning a stitched laundered gdr branch from a git server
does not establish debrebase-last, so dgit would make patches
itself (slowly).

So, instead, use git-debrebase make-patches in situations where it
will succeed.  We could just run it but that's slower, and it is a bit
awkward because we have to consider whether gdr is installed.  So
provide our own implementation.  It can be simpler because it only has
to handle the easy cases;

On testing of the new algorithm: we want to be confident that this
doesn't misfire; otherwise dgit users could be inconvenienced.  And we
want it to work for gdr users of course.

We can analyse the test coverage of the logic in branch_is_gdr
by running the whole test suite and then comparing this:

  cat tests/tmp/*.log |perl -ne 'next unless s/^branch_is_gdr  \w+ //; print' |sort -u |less

with this:

  git-grep 'branch_is_gdr  ' | perl -pe 's/^^dgit:\s+//' |sort |less

Noting that we should ideally have one each of all the gdr kinds we
try to recognise.  Currently that shows that we are missing only:

  gdr merged-breakwater
  unmarked BreakwaterStart YES

Closes: #907208.

Signed-off-by: Ian Jackson <ijackson@chiark.greenend.org.uk>

1 files changed, 73 insertions, 8 deletions

diff --git a/dgit b/dgit
index 3438f62..2774f7e 100755
--- a/dgit
+++ b/dgit
@@ -308,13 +308,6 @@ sub branch_gdr_info ($$) {
     return ($ffq_prev, $gdrlast);
 }
 
-sub branch_is_gdr ($$) {
-    my ($symref, $head) = @_;
-    my ($ffq_prev, $gdrlast) = branch_gdr_info($symref, $head);
-    return 0 unless $ffq_prev || $gdrlast;
-    return 1;
-}
-
 sub branch_is_gdr_unstitched_ff ($$$) {
     my ($symref, $head, $ancestor) = @_;
     my ($ffq_prev, $gdrlast) = branch_gdr_info($symref, $head);
@@ -323,6 +316,78 @@ sub branch_is_gdr_unstitched_ff ($$$) {
     return 1;
 }
 
+sub branch_is_gdr ($) {
+    my ($head) = @_;
+    # This is quite like git-debrebase's keycommits.
+    # We have our own implementation because:
+    #  - our algorighm can do fewer tests so is faster
+    #  - it saves testing to see if gdr is installed
+    my $walk = $head;
+    local $Debian::Dgit::debugcmd_when_debuglevel = 3;
+    printdebug "branch_is_gdr $head...\n";
+    my $get_patches = sub {
+	my $t = git_cat_file "$_[0]:debian/patches", [qw(missing tree)];
+	return $t // '';
+    };
+    my $tip_patches = $get_patches->($head);
+  WALK:
+    for (;;) {
+	my $cdata = git_cat_file $walk, 'commit';
+	my ($hdrs,$msg) = $cdata =~ m{\n\n} ? ($`,$') : ($cdata,'');
+	if ($msg =~ m{^\[git-debrebase\ (
+			  anchor | pseudomerge | changelog | 
+			  make-patches | merged-breakwater
+		      ) [: ] }mx) {
+	    # no need to analyse this - it's sufficient
+	    # (gdr classifications: Anchor, MergedBreakwaters)
+	    # (made by gdr: Pseudomerge, Changelog)
+	    printdebug "branch_is_gdr  $walk gdr $1 YES\n";
+	    return 1;
+	}
+	my @parents = ($hdrs =~ m/^parent (\w+)$/gm);
+	if (@parents==2) {
+	    my $walk_tree = get_tree_of_commit $walk;
+	    foreach my $p (@parents) {
+		my $p_tree = get_tree_of_commit $p;
+		if ($p_tree eq $walk_tree) { # pseudomerge contriburor
+		    # (gdr classification: Pseudomerge; not made by gdr)
+		    printdebug "branch_is_gdr  $walk unmarked pseudomerge\n"
+			if $debuglevel >= 2;
+		    $walk = $p;
+		    next WALK;
+		}
+	    }
+	    # some other non-gdr merge
+	    # (gdr classification: VanillaMerge, DgitImportUnpatched, ?)
+	    printdebug "branch_is_gdr  $walk ?-2-merge NO\n";
+	    return 0;
+	}
+	if (@parents>2) {
+	    # (gdr classification: ?)
+	    printdebug "branch_is_gdr  $walk ?-octopus NO\n";
+	    return 0;
+	}
+	if ($get_patches->($walk) ne $tip_patches) {
+	    # Our parent added, removed, or edited patches, and wasn't
+	    # a gdr make-patches commit.  gdr make-patches probably
+	    # won't do that well, then.
+	    # (gdr classification of parent: AddPatches or ?)
+	    printdebug "branch_is_gdr  $walk ?-patches NO\n";
+	    return 0;
+	}
+	if ($tip_patches eq '' and
+	    !defined git_cat_file "$walk:debian") {
+	    # (gdr classification of parent: BreakwaterStart
+	    printdebug "branch_is_gdr  $walk unmarked BreakwaterStart YES\n";
+	    return 1;
+	}
+	# (gdr classification: Upstream Packaging Mixed Changelog)
+	printdebug "branch_is_gdr  $walk plain\n"
+	    if $debuglevel >= 2;
+	$walk = $parents[0];
+    }
+}
+
 #---------- remote protocol support, common ----------
 
 # remote push initiator/responder protocol:
@@ -5548,7 +5613,7 @@ END
 
     if ($quilt_mode eq 'linear'
 	&& !$fopts->{'single-debian-patch'}
-	&& branch_is_gdr($symref, $headref)) {
+	&& branch_is_gdr($headref)) {
 	# This is much faster.  It also makes patches that gdr
 	# likes better for future updates without laundering.
 	#