chiark / gitweb /
git-debrebase: New merge handing, experimental and preliminary
authorIan Jackson <ijackson@chiark.greenend.org.uk>
Sat, 11 Aug 2018 08:50:04 +0000 (09:50 +0100)
committerIan Jackson <ijackson@chiark.greenend.org.uk>
Sat, 11 Aug 2018 09:30:31 +0000 (10:30 +0100)
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>
git-debrebase
tests/tests/gdr-unprocessable

index 66cbb58..ae3fb45 100755 (executable)
@@ -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 ?";
            }
index 14d1e8e..5e86522 100755 (executable)
@@ -14,7 +14,7 @@ t-dgit setup-mergechangelogs
 subcmd () {
        cmd=("$@")
 
-       branch merge 'complex merge'
+       branch merge 'general two-parent merge'
        branch origin 'origin commit'
 }