Allow submit of merge of non change branch

Commit a61b6eed5337049a7feb58ac935543624f107129 introduced a bug that
prevents mergeing of a branch that is not a change.
It marks the branch to be merged into as uninteresting whereas the
branch that gets merged is not, which causes Gerrit to think that it
is not allowed to merge it resulting in MISSING_DEPENDENCIES error.

In the case where the walk hits a commit that does not have canMergeFlag
and is not in the commits to be submitted, check if commit is already
merged.

Bug: Issue 4930
Change-Id: Ib4f95ebe336e381d6fcbf36867e84d927ac13eb1
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/change/AbstractSubmit.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/change/AbstractSubmit.java
index 56dfa21..a00dd7c 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/change/AbstractSubmit.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/change/AbstractSubmit.java
@@ -25,6 +25,7 @@
 import com.google.common.base.Function;
 import com.google.common.base.Strings;
 import com.google.common.collect.HashMultimap;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.common.collect.Maps;
@@ -305,6 +306,33 @@
     submit(change1.getChangeId());
   }
 
+  @Test
+  public void submitMergeOfNonChangeBranchTip() throws Exception {
+    // Merge a branch with commits that have not been submitted as
+    // changes.
+    //
+    // M  -- mergeCommit (pushed for review and submitted)
+    // | \
+    // |  S -- stable (pushed directly to refs/heads/stable)
+    // | /
+    // I   -- master
+    //
+    RevCommit master = getRemoteHead(project, "master");
+    PushOneCommit stableTip = pushFactory.create(db, admin.getIdent(), testRepo,
+        "Tip of branch stable", "stable.txt", "");
+    PushOneCommit.Result stable = stableTip.to("refs/heads/stable");
+    PushOneCommit mergeCommit = pushFactory.create(db, admin.getIdent(),
+        testRepo, "The merge commit", "merge.txt", "");
+    mergeCommit.setParents(ImmutableList.of(master, stable.getCommit()));
+    PushOneCommit.Result mergeReview = mergeCommit.to("refs/for/master");
+    approve(mergeReview.getChangeId());
+    submit(mergeReview.getChangeId());
+
+    List<RevCommit> log = getRemoteLog();
+    assertThat(log).contains(stable.getCommit());
+    assertThat(log).contains(mergeReview.getCommit());
+  }
+
   private void assertSubmitter(PushOneCommit.Result change) throws Exception {
     ChangeInfo info = get(change.getChangeId(), ListChangesOption.MESSAGES);
     assertThat(info.messages).isNotNull();
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/RebaseSorter.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/RebaseSorter.java
index be181fa..6cba750 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/git/RebaseSorter.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/RebaseSorter.java
@@ -32,12 +32,14 @@
   private final CodeReviewRevWalk rw;
   private final RevFlag canMergeFlag;
   private final RevCommit initialTip;
+  private final Set<RevCommit> alreadyAccepted;
 
   public RebaseSorter(CodeReviewRevWalk rw, RevCommit initialTip,
-      RevFlag canMergeFlag) {
+      Set<RevCommit> alreadyAccepted, RevFlag canMergeFlag) {
     this.rw = rw;
     this.canMergeFlag = canMergeFlag;
     this.initialTip = initialTip;
+    this.alreadyAccepted = alreadyAccepted;
   }
 
   public List<CodeReviewCommit> sort(Collection<CodeReviewCommit> incoming)
@@ -57,6 +59,10 @@
       final List<CodeReviewCommit> contents = new ArrayList<>();
       while ((c = rw.next()) != null) {
         if (!c.has(canMergeFlag) || !incoming.contains(c)) {
+          if (isAlreadyMerged(c)) {
+            rw.markUninteresting(c);
+            break;
+          }
           // We cannot merge n as it would bring something we
           // aren't permitted to merge at this time. Drop n.
           //
@@ -82,6 +88,21 @@
     return sorted;
   }
 
+  private boolean isAlreadyMerged(CodeReviewCommit commit) throws IOException {
+    try (CodeReviewRevWalk mirw =
+        CodeReviewCommit.newRevWalk(rw.getObjectReader())) {
+      mirw.reset();
+      mirw.markStart(commit);
+      for (RevCommit accepted : alreadyAccepted) {
+        if (mirw.isMergedInto(mirw.parseCommit(accepted),
+            mirw.parseCommit(commit))) {
+          return true;
+        }
+      }
+    }
+    return false;
+  }
+
   private static <T> T removeOne(final Collection<T> c) {
     final Iterator<T> i = c.iterator();
     final T r = i.next();
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/strategy/RebaseIfNecessary.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/strategy/RebaseIfNecessary.java
index 4413e26..0bb669b 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/git/strategy/RebaseIfNecessary.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/strategy/RebaseIfNecessary.java
@@ -176,8 +176,8 @@
   private List<CodeReviewCommit> sort(Collection<CodeReviewCommit> toSort,
       RevCommit initialTip) throws IntegrationException {
     try {
-      return new RebaseSorter(
-          args.rw, initialTip, args.canMergeFlag).sort(toSort);
+      return new RebaseSorter(args.rw, initialTip, args.alreadyAccepted,
+          args.canMergeFlag).sort(toSort);
     } catch (IOException e) {
       throw new IntegrationException("Commit sorting failed", e);
     }