git-debrebase: New merge handing, experimental and preliminary

Classification:
* Classify octopus merges as unknown, separately
* Classify 2-parent general merges as VanillaMerge, if feature enabled
* Introduce new merged-breakwater commit tag, classify as MergedBreakwaters
* Classify other gdr-generated 2-parent merges as unknown

Inspection (keycommits):
* VanillaMerge commits require laundry, much like dgit imports,
  and prevent discernment of the actual breakwater and anchor

Laundry (walk):
* Rewrite VanillaMerge using new merge_series function

Test suite:
* We get a slightly different error message in gdr-unprocessable, now.
  Later, when we make this non-experimental all the time, we are going
  to have to soup up gdr-unprocessable to make a worse test commit.

There are a lot of known bugs and infelicites, marked with "xxx".
There is a test (which will appear in a moment) but it's rather a poor
test, so there will be many uknown bugs.

So all of this is enabled only if GIT_DEBREBASE_EXPERIMENTAL_MERGE is
set in the environment.  (Strictly, only the classification is gated,
but that is sufficient.)  No significant functional change without
this setting.

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

2 files changed, 350 insertions, 2 deletions

diff --git a/git-debrebase b/git-debrebase
index 66cbb58..ae3fb45 100755
--- a/git-debrebase
+++ b/git-debrebase
@@ -340,6 +340,181 @@ sub gbp_pq_export ($$$) {
     runcmd @git, qw(add -f debian/patches);
 }
 
+
+# xxx allow merge separately from laundering
+#
+# xxx docs highlight forbidden things
+# xxx docs list allowable things ?
+# xxx docs explicitly forbid some rebase
+#
+# xxx provide a way for the user to help
+# xxx (eg, provide wreckage provide way to continue)
+
+# later/rework?
+#  use git-format-patch?
+#  our own patch identification algorithm?
+#  this is an alternative strategy
+
+sub merge_series ($$;@) {
+    my ($newbase, $base_q, @input_qs) = @_;
+    # $base_q{SeriesBase}  $input_qs[]{SeriesBase}
+    # $base_q{SeriesTip}   $input_qs[]{SeriesTip}
+    # ^ specifies several patch series (currently we only support exactly 2)
+    # return value is a commit which is the result of
+    # merging the two versions of the same topic branch
+    #   $input_q[0] and $input_q[1]
+    # with respect to the old version
+    #   $base_q
+    # all onto $newbase.
+
+    # Creates, in *_q, a key MR for its private use
+
+    $input_qs[$_]{MR}{S} = $_ foreach (0..$#input_qs);
+    $base_q->{MR}{S} = 'base';
+
+    my %prereq;
+    # $prereq{<patch filename>}{<possible prereq}{<S>} = 1 or absent
+    # $prereq{<patch filename>}{<possible prereq}  exists or not (later)
+    # $prereq{<patch filename>}               exists or not (even later)
+
+    my $result;
+
+    local $workarea = fresh_playground "$playprefix/merge";
+    my $seriesfile = "debian/patches/series";
+    in_workarea sub {
+	playtree_setup();
+	foreach my $q ($base_q, reverse @input_qs) {
+	    my $s = $q->{MR}{S};
+	    gbp_pq_export "p-$s", $q->{SeriesBase}, $q->{SeriesTip};
+	    if (open S, $seriesfile) {
+		my @earlier;
+		while (my $patch = <S>) {
+		    chomp $patch or die $!;
+		    foreach my $earlier (@earlier) {
+			$prereq{$patch}{$earlier}{$s}++ and die;
+		    }
+		    push @earlier, $patch;
+		    stat "debian/patches/$patch" or die "$patch ?";
+		}
+		S->error and die "$seriesfile $!";
+		close S;
+	    } else {
+		die "$seriesfile $!" unless $!==ENOENT;
+	    }
+	    read_tree_upstream $newbase, 1;
+	    my $pec = make_commit [ grep { defined } $base_q->{MR}{PEC} ], [
+                "Convert $s to patch queue for merging",
+                "[git-debrebase merge-innards patch-queue import:".
+                " $q->{SeriesTip}]"
+            ];
+	    runcmd @git, qw(rm -q --cached), $seriesfile;
+	    $pec = make_commit [ $pec ], [
+                "Drop series file from $s to avoid merge trouble",
+                "[git-debrebase merge-innards patch-queue prep:".
+                " $q->{SeriesTip}]"
+            ];
+            runcmd @git, qw(reset -q --hard), $pec;
+	    $q->{MR}{PEC} = $pec;
+	}
+	# now, because of reverse, we are on $input_q->{MR}{OQC}
+	runcmd @git, qw(checkout -q -b merge);
+	my @mergecmd = (@git, qw(merge --quiet --no-edit), "p-1");
+	debugcmd '+', @mergecmd;
+	$!=0; $?=-1;
+	if (system @mergecmd) {
+	    failedcmd @mergecmd;
+	}
+
+	# We need to construct a new series file
+	# Firstly, resolve prereq
+	foreach my $f (keys %prereq) {
+	    if (!stat_exists "debian/patches/$f") {
+		# git merge deleted it; that's how we tell it's not wanted
+		delete $prereq{$f};
+		next;
+	    }
+	    foreach my $g (keys %{ $prereq{$f} }) {
+		my $gfp = $prereq{$f}{$g};
+		next unless
+		    # want to keep it
+		    !!$gfp->{0} == !!$gfp->{1}
+		    ? $gfp->{0}
+		    : !$gfp->{base}
+		    ;
+		delete $prereq{$f}{$g};
+	    }
+	}
+
+	my $unsat = sub {
+	    my ($f) = @_;
+	    return scalar keys %{ $prereq{$f} };
+	};
+
+	my $nodate = time + 1;
+	my %authordate;
+	# $authordate{<patch filename>};
+	my $authordate = sub {
+	    my ($f) = @_;
+	    $authordate{$f} //= do {
+		open PF, "<", "debian/patches/$f" or die "$f $!";
+		while (<PF>) {
+		    return $nodate if m/^$/;
+		    last if s{^Date: }{};
+		}
+		chomp;
+		return cmdoutput qw(date +%s -d), $_;
+	    };
+	};
+
+	open NS, '>', $seriesfile or die $!;
+
+	while (keys %prereq) {
+	    my $best;
+	    foreach my $try (sort keys %prereq) {
+		if ($best) {
+		    next if (
+			     $unsat->($try) <=> $unsat->($best) or
+			     $authordate->($try) <=> $authordate->($best) or
+			     $try cmp $best
+			    ) >= 0;
+		}
+		$best = $try;
+	    }
+	    print NS "$best\n" or die $!;
+	    delete $prereq{$best};
+	    foreach my $gp (values %prereq) {
+		delete $gp->{$best};
+	    }
+	}
+
+	runcmd @git, qw(add), $seriesfile;
+	runcmd @git, qw(commit --quiet -m), 'Merged series';
+
+	runcmd qw(gbp pq import);
+
+	# OK now we are on patch-queue/merge, and we need to rebase
+	# onto the intended parent and drop the patches from each one
+
+	my $build = $newbase;
+	my @lcmd = (@git, qw(rev-list --reverse merge..patch-queue/merge));
+	foreach my $c (grep /./, split /\n/, cmdoutput @lcmd) {
+	    my $commit = git_cat_file $c, 'commit';
+	    read_tree_upstream $c;
+	    my $tree = cmdoutput @git, qw(write-tree);
+	    $commit =~ s{^parent (\S+)$}{parent $build}m or confess;
+	    $commit =~ s{^tree (\S+)$}{tree $tree}m      or confess;
+	    open C, ">", "../mcommit" or die $!;
+	    print C $commit or die $!;
+	    close C or die $!;
+	    $build = cmdoutput @git, qw(hash-object -w -t commit ../mcommit);
+	}
+	$result = $build;
+	runcmd @git, qw(update-ref refs/heads/result), $result;
+    };
+    printdebug "merge_series returns $result\n";
+    return $result;
+}
+
 # classify returns an info hash like this
 #   CommitId => $objid
 #   Hdr => # commit headers, including 1 final newline
@@ -597,7 +772,22 @@ sub classify ($) {
 			   OrigParents => \@orig_ps);
     }
 
-    return $unknown->("complex merge");
+    if (@p > 2) {
+	return $unknown->("octopus merge");
+    }
+    if (@p == 2 and
+	$r->{Msg} =~ m{^\[git-debrebase merged-breakwater.*\]$}m) {
+	return $classify->("MergedBreakwaters");
+    }
+    if ($r->{Msg} =~ m{^\[(git-debrebase|dgit)[: ].*\]$}m) {
+	return $unknown->("unknown kind of merge from $1");
+    }
+
+    if (!$ENV{GIT_DEBREBASE_EXPERIMENTAL_MERGE}) {
+	return $unknown->("general two-parent merge");
+    }
+
+    return $classify->("VanillaMerge");
 }
 
 sub keycommits ($;$$$$) {
@@ -680,6 +870,10 @@ sub keycommits ($;$$$$) {
 		     " ($head)");
 		return (undef,undef);
 	    }
+	} elsif ($ty eq 'VanillaMerge') {
+	    $x->($trouble, 'vanillamerge',
+		 "found vanilla merge"," ($head)");
+	    return (undef,undef);
 	} else {
 	    $x->($fatal, 'unprocessable',
 		 "found unprocessable commit, cannot cope: $cl->{Why}",
@@ -760,6 +954,10 @@ sub walk ($;$$$) {
 	no warnings qw(exiting); last;
     };
 
+    my $nomerge = sub {
+	fail "something useful about failed merge attempt @_ xxx".Dumper($cl);
+    };
+
     my $last_anchor;
 
     for (;;) {
@@ -863,6 +1061,139 @@ sub walk ($;$$$) {
 		return $bomb->();
 	    }
 	    die "$ty ?";
+	} elsif ($ty eq 'VanillaMerge' or $ty eq 'MergedBreakwaters') {
+	    # xxx need to handle ffq if one side was unstitched
+	    # wait both of them may be!
+	    my $ok=1;
+	    my $best_anchor;
+	    # We expect to find a dominating anchor amongst the
+	    # inputs' anchors.  That will be the new anchor.
+	    #
+	    # More complicated is finding a merge base for the
+	    # breakwaters.  We need a merge base that is a breakwater
+	    # commit.  The ancestors of breakwater commits are more
+	    # breakwater commits and possibly upstream commits and the
+	    # ancestors of those upstream.  Upstreams might have
+	    # arbitrary ancestors.  But any upstream commit U is
+	    # either included in both anchors, in which case the
+	    # earlier anchor is a better merge base than any of U's
+	    # ancestors; or U is not included in the older anchor, in
+	    # which case U is not an ancestor of the vanilla merge at
+	    # all.  So no upstream commit, nor any ancestor thereof,
+	    # is a best merge base.  As for non-breakwater Debian
+	    # commits: these are never ancestors of any breakwater.
+	    #
+	    # So any best merge base as found by git-merge-base
+	    # is a suitable breakwater anchor.  Usually there will
+	    # be only one.
+
+	    printdebug "*** MERGE\n";
+
+	    # xxx avoid calling walk without nogenerate when
+	    # we have a MergedBreakwater; instead call keycommits ?
+
+	    my @bwbcmd = (@git, qw(merge-base));
+	    my @ibcmd = (@git, qw(merge-base --all));
+	    my $might_be_in_bw = 1;
+
+	    my $ps = $cl->{Parents};
+
+	    foreach my $p (@$ps) {
+		$prline->(" VanillaMerge ".$p->{Ix});
+		$prprdelim->();
+		my ($ptip, $pbw, $panchor) =
+		    walk $p->{CommitId}, 0, $report,
+		         $report_lprefix.'  ';
+		$p->{Laundered} = $p->{SeriesTip} = $ptip;
+		$p->{Breakwater} = $p->{SeriesBase} = $pbw;
+		$p->{Anchor} = $panchor;
+
+		$best_anchor = $panchor if
+		    !defined $best_anchor or
+		    is_fast_fwd $best_anchor, $panchor;
+
+		printdebug " MERGE BA best=".($best_anchor//'-').
+		    " p=$panchor\n";
+	    }
+
+	    foreach my $p (@$ps) {
+		$prline->(" VanillaMerge ".$p->{Ix});
+		if (!is_fast_fwd $p->{Anchor}, $best_anchor) {
+		    $nomerge->('DivergentAnchor');
+		} elsif ($p->{Anchor} eq $best_anchor) {
+		    print $report " SameAnchor" if $report;
+		} else {
+		    print $report " SupersededAnchor" if $report;
+		}
+		if ($p->{Breakwater} eq $p->{CommitId}) {
+		    # this parent commit was its own breakwater,
+		    # ie it is part of the breakwater
+		    print $report " Breakwater" if $report;
+		} else {
+		    $might_be_in_bw = 0;
+		}
+		push @bwbcmd, $p->{Breakwater};
+		push @ibcmd, $p->{CommitId};
+	    }
+
+	    if ($ok && $might_be_in_bw) {
+		$prline->(" VanillaMerge MergedBreakwaters");
+		$last_anchor = $best_anchor;
+		$build_start->('MergedBreakwaters', $cur);
+	    }
+
+	    $nomerge->("alleged merged-breakwater is not a breakwater")
+		unless $ty eq 'VanillaMerge';
+
+	    my $bwb = cmdoutput @bwbcmd;
+
+	    # OK, now we have a breakwater base, but we need the merge
+	    # base for the interchange branch because we need the delta
+	    # queue.
+	    #
+	    # This a the best merge base of our inputs which has the
+	    # breakwater merge base as an ancestor.
+
+	    my @ibs =
+		grep { is_fast_fwd $bwb, $_ }
+		grep /./,
+		split /\n/,
+		cmdoutput @ibcmd;
+	    my ($ib) = @ibs
+		or $nomerge->("no suitable interchange merge base");
+
+	    $prline->("  VanillaMerge Base");
+	    $prprdelim->();
+	    my ($btip, $bbw, $banchor) =
+		walk $ib, 0, $report, $report_lprefix.'  ';
+
+	    my $ibinfo = { SeriesTip => $btip,
+			   SeriesBase => $bbw,
+			   Anchor => $banchor };
+	    $bbw eq $bwb
+		or $nomerge->("interchange merge-base ($ib)'s".
+			      " breakwater ($bbw)".
+			      " != breakwaters' merge-base ($bwb)");
+	    grep { $_->{Anchor} eq $ibinfo->{Anchor} } @$ps
+		 or $nomerge->("interchange merge-base ($ib)'s".
+			       " anchor ($ibinfo->{SeriesBase})".
+			       " != any merge input's anchor (".
+			       (join ' ', map { $_->{Anchor} } @$ps).
+			       ")");
+
+
+	    $cl->{MergeInterchangeBaseInfo} = $ibinfo;
+	    $cl->{MergeBestAnchor} = $best_anchor;
+	    push @brw_cl, {
+                %$cl,
+                SpecialMethod => 'MergeCreateMergedBreakwaters',
+                $xmsg->('construct merged breakwater from vanilla merge'),
+            };
+	    push @upp_cl, {
+                %$cl,
+                SpecialMethod => 'MergeMergeSeries',
+            };
+	    $build_start->('MergeBreakwaters', $cur);
         } else {
             printdebug "*** WALK BOMB unrecognised\n";
 	    return $bomb->();
@@ -923,6 +1254,23 @@ sub walk ($;$$$) {
 		next unless $differs & D_UPS;
 		read_tree_upstream($cltree);
 		push @parents, map { $_->{CommitId} } @{ $cl->{OrigParents} };
+	    } elsif ($method eq 'MergeCreateMergedBreakwaters') {
+		print "Found a general merge, will try to tidy it up.\n";
+		$rewriting = 1;
+		read_tree_upstream($cl->{MergeBestAnchor});
+		read_tree_upstream($cl->{MergeBestAnchor});
+		read_tree_debian($cltree);
+		@parents = map { $_->{Breakwater} } @{ $cl->{Parents} };
+	    } elsif ($method eq 'MergeMergeSeries') {
+		print "Running merge resolution for $cl->{CommitId}...\n";
+		$build = merge_series
+		    $build,
+		    $cl->{MergeInterchangeBaseInfo},
+		    @{ $cl->{Parents} };
+		$last_anchor = $cl->{MergeBestAnchor};
+		# xxx need to check the tree somehow
+		print "Merge resolution successful.\n";
+		next;
 	    } else {
 		confess "$method ?";
 	    }
diff --git a/tests/tests/gdr-unprocessable b/tests/tests/gdr-unprocessable
index 14d1e8e..5e86522 100755
--- a/tests/tests/gdr-unprocessable
+++ b/tests/tests/gdr-unprocessable
@@ -14,7 +14,7 @@ t-dgit setup-mergechangelogs
 subcmd () {
 	cmd=("$@")
 
-	branch merge 'complex merge'
+	branch merge 'general two-parent merge'
 	branch origin 'origin commit'
 }