Merge "Fix WalkSorter.sortProject for some corner cases."
diff --git a/java/com/google/gerrit/server/change/WalkSorter.java b/java/com/google/gerrit/server/change/WalkSorter.java
index 6c903b8..cc87ea8 100644
--- a/java/com/google/gerrit/server/change/WalkSorter.java
+++ b/java/com/google/gerrit/server/change/WalkSorter.java
@@ -23,6 +23,7 @@
 import com.google.common.collect.ListMultimap;
 import com.google.common.collect.MultimapBuilder;
 import com.google.common.collect.Ordering;
+import com.google.common.collect.SetMultimap;
 import com.google.common.flogger.FluentLogger;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import com.google.gerrit.entities.PatchSet;
@@ -146,8 +147,8 @@
 
       Set<RevCommit> commits = byCommit.keySet();
       ListMultimap<RevCommit, RevCommit> children = collectChildren(commits);
-      ListMultimap<RevCommit, RevCommit> pending =
-          MultimapBuilder.hashKeys().arrayListValues().build();
+      SetMultimap<RevCommit, RevCommit> pending =
+          MultimapBuilder.hashKeys().hashSetValues().build();
       Deque<RevCommit> todo = new ArrayDeque<>();
 
       RevFlag done = rw.newFlag("done");
@@ -156,6 +157,7 @@
       int found = 0;
       RevCommit c;
       List<PatchSetData> result = new ArrayList<>(expected);
+      int maxPopSize = commits.size() * commits.size();
       while (found < expected && (c = rw.next()) != null) {
         if (!commits.contains(c)) {
           continue;
@@ -164,9 +166,15 @@
         todo.add(c);
         int i = 0;
         while (!todo.isEmpty()) {
-          // Sanity check: we can't pop more than N pending commits, otherwise
-          // we have an infinite loop due to programmer error or something.
-          checkState(++i <= commits.size(), "Too many pending steps while sorting %s", commits);
+          // Sanity check: in the worst case scenario, each commit can add all previous commits in
+          // the todo queue. This can lead to (n-1) + (n-2) + ... +1 iterations of the algorithm.
+          // So, in the worst case we can't pop more than N^2 pending commits, otherwise
+          // we have an infinite loop due to programmer error or something. (actually, it is
+          // (N-1) + (N-2) + (N-3) + (1) + 1 = N/2*(N-1)+1, but N^2 is enough for us.)
+          checkState(
+              ++i <= maxPopSize,
+              "Too many pending steps while sorting %s - can be a problem in the algorithm.",
+              commits);
           RevCommit t = todo.removeFirst();
           if (t.has(done)) {
             continue;
diff --git a/javatests/com/google/gerrit/server/change/WalkSorterTest.java b/javatests/com/google/gerrit/server/change/WalkSorterTest.java
index 7775452..0d000a5 100644
--- a/javatests/com/google/gerrit/server/change/WalkSorterTest.java
+++ b/javatests/com/google/gerrit/server/change/WalkSorterTest.java
@@ -86,6 +86,114 @@
   }
 
   @Test
+  public void seriesOfMergeChangesInSpecialOrder() throws Exception {
+    TestRepository<Repo> p = newRepo("p");
+    // For this test, the RevWalk in the sortProject must return commits in the following order:
+    // c3, c1, c2, c4.
+    // To achieve this order, the commit timestamps must be set in a specific order - RevWalk
+    // returns them sorted by timestamp, starting from the newest one.
+
+    // timestamp: base + 3
+    RevCommit c1 = p.commit().tick(3).create();
+    // timestamp: base + 2
+    RevCommit c2 = p.commit().tick(-1).parent(c1).create();
+    // timestamp: base + 4
+    RevCommit c3 = p.commit().tick(2).parent(c1).parent(c2).create();
+    // timestamp: base + 1
+    RevCommit c4 = p.commit().tick(-3).parent(c3).create();
+
+    ChangeData cd1 = newChange(p, c1);
+    ChangeData cd2 = newChange(p, c2);
+    ChangeData cd3 = newChange(p, c3);
+    ChangeData cd4 = newChange(p, c4);
+
+    List<ChangeData> changes = ImmutableList.of(cd1, cd2, cd3, cd4);
+    WalkSorter sorter = new WalkSorter(repoManager);
+
+    assertSorted(
+        sorter,
+        changes,
+        ImmutableList.of(
+            patchSetData(cd4, c4),
+            patchSetData(cd3, c3),
+            patchSetData(cd2, c2),
+            patchSetData(cd1, c1)));
+  }
+
+  @Test
+  public void seriesOfMergeChangesWorstCaseForTopoSorting() throws Exception {
+    TestRepository<Repo> p = newRepo("p");
+    // For this test, the RevWalk in the sortProject must return commits in the following order:
+    // c1, c2, c3, c4, c5, c6, c7.
+    // To achieve this order, the commit timestamps must be set in a specific order - RevWalk
+    // returns them sorted by timestamp, starting from the newest one.
+
+    // timestamp: base + 8
+    RevCommit c1 = p.commit().tick(8).create();
+    // timestamp: base + 7
+    RevCommit c2 = p.commit().tick(-1).parent(c1).create();
+    // timestamp: base + 6
+    RevCommit c3 = p.commit().tick(-1).parent(c1).parent(c2).create();
+    // timestamp: base + 5
+    RevCommit c4 = p.commit().tick(-1).parent(c1).parent(c2).parent(c3).create();
+    // timestamp: base + 4
+    RevCommit c5 = p.commit().tick(-1).parent(c1).parent(c2).parent(c3).parent(c4).create();
+    // timestamp: base + 3
+    RevCommit c6 =
+        p.commit().tick(-1).parent(c1).parent(c2).parent(c3).parent(c4).parent(c5).create();
+    // timestamp: base + 2
+    RevCommit c7 =
+        p.commit()
+            .tick(-1)
+            .parent(c1)
+            .parent(c2)
+            .parent(c3)
+            .parent(c4)
+            .parent(c5)
+            .parent(c6)
+            .create();
+    // timestamp: base + 1
+    RevCommit c8 =
+        p.commit()
+            .tick(-1)
+            .parent(c1)
+            .parent(c2)
+            .parent(c3)
+            .parent(c4)
+            .parent(c5)
+            .parent(c6)
+            .parent(c7)
+            .create();
+
+    ChangeData cd1 = newChange(p, c1);
+    ChangeData cd2 = newChange(p, c2);
+    ChangeData cd3 = newChange(p, c3);
+    ChangeData cd4 = newChange(p, c4);
+    ChangeData cd5 = newChange(p, c5);
+    ChangeData cd6 = newChange(p, c6);
+    ChangeData cd7 = newChange(p, c7);
+    ChangeData cd8 = newChange(p, c8);
+
+    List<ChangeData> changes = ImmutableList.of(cd1, cd2, cd3, cd4, cd5, cd6, cd7, cd8);
+    WalkSorter sorter = new WalkSorter(repoManager);
+
+    // Do not use assertSorted because it tests all permutations. We don't need it for this test
+    // and total number of permutations is quite big.
+    assertThat(sorter.sort(changes))
+        .containsExactlyElementsIn(
+            ImmutableList.of(
+                patchSetData(cd8, c8),
+                patchSetData(cd7, c7),
+                patchSetData(cd6, c6),
+                patchSetData(cd5, c5),
+                patchSetData(cd4, c4),
+                patchSetData(cd3, c3),
+                patchSetData(cd2, c2),
+                patchSetData(cd1, c1)))
+        .inOrder();
+  }
+
+  @Test
   public void subsetOfSeriesOfChanges() throws Exception {
     TestRepository<Repo> p = newRepo("p");
     RevCommit c1_1 = p.commit().create();