gpick: fetch pre-cherry-pick PatchSets for MERGED Changes

gerrit creates a new PatchSet for the commit it cherry-picked into the
target branch. this commit has the wrong parent, and is excluded from
the listing by the negated upstream refs. both consequences would pose
problems later on, so make an effort to fetch the PatchSet before the
cherry-picked one.

Change-Id: I22192202202df2ef734e7d61f995507d50f9ef08
Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@gmx.de>

2 files changed, 244 insertions, 21 deletions

diff --git a/bin/git-gpick b/bin/git-gpick
index 93960a7..4a44d8a 100755
--- a/bin/git-gpick
+++ b/bin/git-gpick
@@ -626,41 +626,170 @@ sub map_update_spec($$$)
     }
 }
 
+sub add_patchset($$)
+{
+    my ($ginfo, $idxes) = @_;
+
+    my $idx = $$ginfo{pick_idx};
+    $$idxes{$idx} = 1;
+    my $revs = $$ginfo{revs};
+    $$idxes{$idx - 1} = 1
+        if (($idx > 0) && ($idx == $#$revs) && ($$ginfo{status} eq 'MERGED'));
+}
+
 # Fetch the latest PatchSets for the specified Changes.
 # We don't re-fetch PatchSets which we already have.
-sub fetch_patchsets($)
+sub fetch_patchsets($$)
 {
-    my ($ginfos) = @_;
+    my ($ginfos, $visits) = @_;
 
     my @refs;
     foreach my $ginfo (@$ginfos) {
-        my ($revs, $pick_idx) = ($$ginfo{revs}, $$ginfo{pick_idx});
-        my $rev = $$revs[$pick_idx];
-        my ($rev_id, $rev_ps) = ($$rev{id}, $$rev{ps});
-        if (defined($$ginfo{fetched}{$rev_ps})) {
-            print "Already have PatchSet $rev_ps for $$ginfo{id}.\n" if ($debug);
-        } else {
-            push @refs, "+$$rev{ref}:refs/gpush/g$$ginfo{key}_$rev_ps";
+        my %idxes;
+        add_patchset($ginfo, \%idxes);
+        my $revs = $$ginfo{revs};
+        foreach my $idx (keys %idxes) {
+            my $rev = $$revs[$idx];
+            my ($rev_id, $rev_ps) = ($$rev{id}, $$rev{ps});
+            if (defined($$ginfo{fetched}{$rev_ps})) {
+                print "Already have PatchSet $rev_ps for $$ginfo{id}.\n" if ($debug);
+                $$visits{$rev_id} = 1;
+            } else {
+                push @refs, "+$$rev{ref}:refs/gpush/g$$ginfo{key}_$rev_ps";
+                $$visits{$rev_id} = 1;
+            }
         }
-        my $commit = {
-            id => $rev_id,
-            parents => $$rev{parents}
-        };
-        init_commit($commit);
-        $$ginfo{pick_commit} = $commit;
     }
     if (@refs) {
+        # We need to fetch the current upstream to be able to exclude it.
+        # See visit_local_commits() for explanation for fetching all branches.
+        push @refs, "+refs/heads/*:refs/remotes/$remote/*";
         print "Fetching PatchSets ...\n" if (!$quiet);
         my @gitcmd = ("git", "fetch");
         # The git-fetch output is quite noisy and unhelpful here, unless debugging.
         push @gitcmd, '-q' if (!$debug);
         push @gitcmd, $remote, @refs;
         run_process(FWD_OUTPUT, @gitcmd);
+        print "Re-enumerating branches from Gerrit remote ...\n" if ($debug);
+        load_refs("refs/remotes/$remote/");
+        update_excludes();
     } else {
         print "No PatchSets need fetching.\n" if ($debug);
     }
 }
 
+# Verify that the 2nd commit is a cherry-pick of the 1st one.
+sub verify_cherrypick($$)
+{
+    my ($prev, $curr) = @_;
+
+    return 0 if ("@{$$curr{author}}" ne "@{$$prev{author}}");
+
+    my @curr_msg = split(/$/m, $$curr{message});
+    my @prev_msg = split(/$/m, $$prev{message});
+    # Cherry-picking may add various footers to the commit message.
+    # Therefore, we verify that the current message is a strict
+    # superset of the previous one.
+    while (@curr_msg && @prev_msg) {
+        my $line = pop @curr_msg;
+        # If this was an added line, we will re-sync at some point.
+        # If it wasn't, unconsumed lines will remain in @prev_msg.
+        pop @prev_msg if ($line eq $prev_msg[-1]);
+    }
+    return 0 if (@curr_msg || @prev_msg);
+
+    my $tree;
+    my $base = get_1st_parent($curr);
+    if (get_1st_parent($prev) eq $base) {
+        # If the pick didn't rebase, we can just compare the trees.
+        $tree = $$prev{tree};
+    } else {
+        # Otherwise the diff needs rebasing.
+        ($tree, undef) = apply_diff($prev, $base, NUL_STDERR);
+        return 0 if (!defined($tree));
+    }
+    return 0 if ($tree ne $$curr{tree});
+
+    return 1;
+}
+
+sub drop_merged_patchsets($$)
+{
+    my ($ginfos, $cmt_by_id) = @_;
+
+    foreach my $ginfo (@$ginfos) {
+        my $revs = $$ginfo{revs};
+        my $curr_commit = $$cmt_by_id{$$revs[-1]{id}};
+        next if (!$curr_commit);  # The Change doesn't need fixup.
+        my $prev_commit = $commit_by_id{$$revs[-2]{id}};
+        wfail("Last-but-one PatchSet of Change $$ginfo{key} is ALSO already upstream?!\n")
+            if (!$prev_commit);  # Actually seen in the wild. Qt Gerrit bug ...
+
+        # This can happen for Changes which were not cherry-picked -
+        # for example merges, or commits which were amended and then
+        # direct-pushed.
+        wfail("Last PatchSet of Change $$ginfo{key} is already upstream,"
+                ." and is not a cherry-pick of the previous one.\n")
+            if (!verify_cherrypick($prev_commit, $curr_commit));
+
+        print "Dropping upstreamed last PatchSet of $$ginfo{id}.\n" if ($debug);
+        pop @$revs;
+    }
+}
+
+sub analyze_patchset($)
+{
+    my ($ginfo) = @_;
+
+    my $idx = $$ginfo{pick_idx};
+    my $revs = $$ginfo{revs};
+    $$ginfo{pick_idx} = --$idx
+        if ($idx == @$revs);
+    my $rev = $$revs[$idx];
+    my $rev_id = $$rev{id};
+    my $commit = $commit_by_id{$rev_id};
+    wfail("PatchSet $$rev{ps} of Change $$ginfo{key} is apparently upstream?!\n")
+        if (!$commit);
+    $$ginfo{pick_commit} = $commit;
+}
+
+# Extract additional information from the fetched PatchSets.
+sub analyze_patchsets($)
+{
+    my ($ginfos) = @_;
+
+    print "Analyzing fetched PatchSets ...\n" if ($debug);
+    my @upstream;
+    foreach my $ginfo (@$ginfos) {
+        next if ($$ginfo{status} ne 'MERGED');
+
+        my $revs = $$ginfo{revs};
+        next if ($$ginfo{pick_idx} != $#$revs);
+
+        # Gerrit creates a new PatchSet when cherry-picking into the target
+        # branch. Obviously, this commit is excluded by ^@{upstream}.
+        my $rev_id = $$revs[-1]{id};
+
+        die("Change $$ginfo{key} is already merged, but not excluded by upstream?!\n")
+            if ($debug && $commit_by_id{$rev_id});
+
+        # This can happen for Changes which were not cherry-picked -
+        # for example merges.
+        fail("Change $$ginfo{key} has only one PatchSet, and that is already upstream.\n")
+            if (@$revs == 1);
+
+        push @upstream, $rev_id;
+    }
+    if (@upstream) {
+        my $commits = visit_commits_raw(\@upstream, ['--no-walk']);
+        my %cmt_by_id = map { $$_{id} => $_ } @$commits;
+        with_local_git_index(\&drop_merged_patchsets, $ginfos, \%cmt_by_id);
+    }
+    foreach my $ginfo (@$ginfos) {
+        analyze_patchset($ginfo);
+    }
+}
+
 # Download the metadata and PatchSets referenced by the specs.
 sub complete_spec_heads($)
 {
@@ -668,7 +797,7 @@ sub complete_spec_heads($)
 
     print "Completing commit specs ...\n" if ($debug);
 
-    my %picks;
+    my (%picks, %visits);
     foreach my $spec (@$specs) {
         my $action = $$spec{action};
         if ($action == INSERT) {
@@ -698,7 +827,12 @@ sub complete_spec_heads($)
     }
     exit(1) if ($any_errors);
 
-    fetch_patchsets(\@fetches) if (@fetches);
+    fetch_patchsets(\@fetches, \%visits) if (@fetches);
+
+    print "Visiting fetched PatchSets ...\n" if ($debug);
+    visit_local_commits([ keys %visits ]);
+
+    analyze_patchsets(\@fetches) if (@fetches);
 }
 
 sub check_specs($)
diff --git a/bin/git_gpush.pm b/bin/git_gpush.pm
index 5dccd11..430e10a 100644
--- a/bin/git_gpush.pm
+++ b/bin/git_gpush.pm
@@ -21,6 +21,7 @@ use List::Util qw(min max);
 use File::Spec;
 use File::Temp qw(mktemp);
 use IPC::Open3 qw(open3);
+use Symbol qw(gensym);
 use Term::ReadKey;
 use Text::Wrap;
 use JSON;
@@ -114,7 +115,7 @@ use constant {
     USE_STDOUT => 4,
     FWD_STDOUT => 8,
     NUL_STDERR => 0,
-    # USE_STDERR is not needed
+    USE_STDERR => 16,
     FWD_STDERR => 32,
     FWD_OUTPUT => 40,
     SILENT_STDIN => 64,  # Suppress debug output for stdin
@@ -159,7 +160,10 @@ sub open_process($@)
     } else {
         $out = \'>&NUL';
     }
-    if ($flags & FWD_STDERR) {
+    if ($flags & USE_STDERR) {
+        $err = \$process{stderr};
+        $$err = gensym();
+    } elsif ($flags & FWD_STDERR) {
         $err = \'>&STDERR';
     } else {
         $err = \'>&NUL';
@@ -184,6 +188,9 @@ sub close_process($)
     if ($$process{stdout}) {
         close($$process{stdout}) or wfail("Failed to close read pipe of '$cmd': $!\n");
     }
+    if ($$process{stderr}) {
+        close($$process{stderr}) or wfail("Failed to close error read pipe of '$cmd': $!\n");
+    }
     waitpid($$process{pid}, 0) or wfail("Failed to wait for '$cmd': $!\n");
     if ($? & 128) {
         wfail("'$cmd' crashed with signal ".($? & 127).".\n") if ($? != 141); # allow SIGPIPE
@@ -251,6 +258,16 @@ sub read_fields($@)
     return 1;
 }
 
+# Read all of a process' output channel as a single string.
+sub get_process_output($$)
+{
+    my ($process, $which) = @_;
+
+    local $/;
+    my $fh = $$process{$which};
+    return <$fh>;
+}
+
 # The equivalent of system().
 sub run_process($@)
 {
@@ -425,6 +442,10 @@ sub update_excludes()
     if ($urefs) {
         $heads{$_} = 1 foreach (values %$urefs);
     }
+    my $grefs = $remote_refs{$remote};
+    if ($grefs) {
+        $heads{$_} = 1 foreach (values %$grefs);
+    }
     @upstream_excludes = map { "^$_" } keys %heads;
 }
 
@@ -1046,13 +1067,36 @@ sub visit_commits_raw($$;$)
     return \@commits;
 }
 
+# Note: The return value is reliable only for the first call.
 sub visit_commits($$;$)
 {
     my ($tips, $args, $cid_opt) = @_;
 
-    my $commits = visit_commits_raw($tips, $args, $cid_opt);
+    my @revs = grep {
+        if ($commit_by_id{$_}) {
+            print "Already visited $_.\n" if ($debug);
+            0;
+        } else {
+            1;
+        }
+    } @$tips;
+    return if (!@revs);
+
+    # The grep above excludes tips which match previous tips or their
+    # ancestors. A tip that is a descendant of a previous tip still
+    # needs to be visited, but the traversal needs to be cut off, so
+    # pass all previous tips as exclusions to git.
+    state %visited;
+    my @excl = map { "^$_" } keys %visited;
+    $visited{$_} = 1 foreach (@revs);
+    push @revs, @excl;
+
+    my $commits = visit_commits_raw(\@revs, $args, $cid_opt);
     foreach my $commit (@$commits) {
         init_commit($commit);
+        # This excludes tips that were in fact ancestors of other tips,
+        # thereby cutting down the noise in the exclusion list.
+        delete $visited{$_} foreach (@{$$commit{parents}});
     }
     return $commits;
 }
@@ -1065,6 +1109,9 @@ sub visit_local_commits($;$)
     # because Gerrit will ignore all known commits (reviewed or not).
     # This matters for cross-branch pushes and re-targeted Changes, where a commit
     # can have known ancestors which aren't on its upstream branch.
+    # When traversing PatchSets from Gerrit, we need to exclude the heads from the
+    # gerrit remote as well, as they may be actually ahead of our merge-base with
+    # upstream.
     return visit_commits($tips, \@upstream_excludes, $cid_opt);
 }
 
@@ -1233,6 +1280,49 @@ sub parse_local_rev($$)
 }
 
 ###################
+# commit creation #
+###################
+
+# Cache of diffs. Global, so it can be flushed from the outside.
+our %commit2diff;
+
+# Apply one commit's diff on top of another commit; return the new tree.
+sub apply_diff($$$)
+{
+    my ($commit, $base_id, $flags) = @_;
+
+    my $sha1 = $$commit{id};
+    my $diff = $commit2diff{$sha1};
+    if (!defined($diff)) {
+        my $show = open_cmd_pipe(0, 'git', 'diff-tree', '--binary', '--root', "$sha1^!");
+        $diff = get_process_output($show, 'stdout');
+        close_process($show);
+        $commit2diff{$sha1} = $diff;
+    }
+
+    # We don't know the tree when the base is an upstream commit.
+    # This is just fine, as this will be the first commit in the
+    # series by definition, so we need to load it anyway. The
+    # subsequent apply will change it in every case, so there
+    # is no chance to recycle it, either.
+    state $curr_tree = "";
+    my $base = $commit_by_id{$base_id};
+    run_process(FWD_STDERR, 'git', 'read-tree', ($base_id eq 'ROOT') ? '--empty' : $base_id)
+        if (!$base || ($curr_tree ne $$base{tree}));
+    $curr_tree = "";
+
+    my $proc = open_process(SOFT_FAIL | USE_STDIN | SILENT_STDIN | NUL_STDOUT | $flags,
+                            'git', 'apply', '--cached', '-C1', '--whitespace=nowarn');
+    write_process($proc, $diff);
+    my $errors = get_process_output($proc, 'stderr')
+        if ($flags & USE_STDERR);
+    close_process($proc);
+    return (undef, $errors) if ($?);
+    $curr_tree = read_cmd_line(0, 'git', 'write-tree');
+    return ($curr_tree, undef);
+}
+
+###################
 # branch tracking #
 ###################
 
@@ -1349,7 +1439,6 @@ sub query_gerrit($;$)
             defined($ref) or fail("Huh?! PatchSet $number in $changeid has no ref?\n");
             my %rev = (
                 id => $revision,
-                parents => $$cps{'parents'} // [],
                 ps => $number,
                 ts => int($ts),
                 ref => $ref