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();