Fix "no common ancestry" bug

In 5169e145587d we added logic to try and detect when the commits
being uploaded have no common ancestor with the destination project.
Unfortunately the logic behind this check was flawed, as it required
that the common ancestor be one of the active branch heads or tags.

Instead we need to use two colors, set on each side, and walk the
iterator until a commit with both colors appears.  If we find such
a commit, that is at least one of the common merge bases, and thus
we have proven there is a common ancestry.  If we cannot find such
a commit, then there is absolutely no common ancestry.

Change-Id: I3c235f514240710bddd78db35b6b48e8f939ca4c
Signed-off-by: Shawn O. Pearce <sop@google.com>

1 files changed, 18 insertions, 12 deletions

diff --git a/src/main/java/com/google/gerrit/server/ssh/commands/Receive.java b/src/main/java/com/google/gerrit/server/ssh/commands/Receive.java
index af499b22bc..a46dbd2d0c 100644
--- a/src/main/java/com/google/gerrit/server/ssh/commands/Receive.java
+++ b/src/main/java/com/google/gerrit/server/ssh/commands/Receive.java
@@ -70,6 +70,7 @@ import org.spearce.jgit.revwalk.FooterKey;
 import org.spearce.jgit.revwalk.FooterLine;
 import org.spearce.jgit.revwalk.RevCommit;
 import org.spearce.jgit.revwalk.RevFlag;
+import org.spearce.jgit.revwalk.RevFlagSet;
 import org.spearce.jgit.revwalk.RevObject;
 import org.spearce.jgit.revwalk.RevSort;
 import org.spearce.jgit.revwalk.RevTag;
@@ -541,36 +542,41 @@ final class Receive extends AbstractGitCommand {
     //
     try {
       final RevWalk walk = rp.getRevWalk();
-      final RevFlag CONNECTED = walk.newFlag("CONNECTED");
-      walk.carry(CONNECTED);
+
+      final RevFlag SIDE_NEW = walk.newFlag("NEW");
+      final RevFlag SIDE_HAVE = walk.newFlag("HAVE");
+      final RevFlagSet COMMON = new RevFlagSet();
+      COMMON.add(SIDE_NEW);
+      COMMON.add(SIDE_HAVE);
+      walk.carry(COMMON);
+
       walk.reset();
       walk.sort(RevSort.TOPO);
       walk.sort(RevSort.REVERSE, true);
 
       final RevCommit tip = walk.parseCommit(newChange.getNewId());
-      tip.add(CONNECTED);
+      tip.add(SIDE_NEW);
       walk.markStart(tip);
 
-      final List<RevCommit> heads = new ArrayList<RevCommit>();
+      boolean haveHeads = false;
       for (final Ref r : rp.getAdvertisedRefs().values()) {
         if (isHead(r) || isTag(r)) {
           try {
             final RevCommit h = walk.parseCommit(r.getObjectId());
-            walk.markUninteresting(h);
-            heads.add(h);
+            h.add(SIDE_HAVE);
+            walk.markStart(h);
+            haveHeads = true;
           } catch (IOException e) {
             continue;
           }
         }
       }
 
-      if (!heads.isEmpty()) {
-        while (walk.next() != null) {
-          /* nothing, just pump the RevWalk until its done */
-        }
+      if (haveHeads) {
         boolean isConnected = false;
-        for (final RevCommit c : heads) {
-          if (c.has(CONNECTED)) {
+        RevCommit c;
+        while ((c = walk.next()) != null) {
+          if (c.hasAll(COMMON)) {
             isConnected = true;
             break;
           }