Merge "RevWalk: new topo sort to not mix lines of history"
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/FirstParentRevWalkTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/FirstParentRevWalkTest.java
index 4a3b04d..c8256b8 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/FirstParentRevWalkTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/FirstParentRevWalkTest.java
@@ -164,6 +164,23 @@
}
@Test
+ public void testTopoNonIntermixSort() throws Exception {
+ RevCommit a = commit();
+ RevCommit b1 = commit(a);
+ RevCommit b2 = commit(a);
+ RevCommit c = commit(b1, b2);
+
+ rw.reset();
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ rw.setFirstParent(true);
+ markStart(c);
+ assertCommit(c, rw.next());
+ assertCommit(b1, rw.next());
+ assertCommit(a, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
public void testCommitTimeSort() throws Exception {
RevCommit a = commit();
RevCommit b1 = commit(a);
@@ -428,4 +445,39 @@
assertCommit(c, rw.next());
assertNull(rw.next());
}
+
+ @Test
+ public void testWithTopoNonIntermixSortAndTreeFilter() throws Exception {
+ RevCommit a = commit();
+ RevCommit b = commit(tree(file("0", blob("b"))), a);
+ RevCommit c = commit(tree(file("0", blob("c"))), b, a);
+ RevCommit d = commit(tree(file("0", blob("d"))), c);
+
+ rw.reset();
+ rw.setFirstParent(true);
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER, true);
+ rw.setTreeFilter(PathFilterGroup.createFromStrings("0"));
+ markStart(d);
+ assertCommit(d, rw.next());
+ assertCommit(c, rw.next());
+ assertCommit(b, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
+ public void testWithTopoNonIntermixSortAndTreeFilter2() throws Exception {
+ RevCommit a = commit();
+ RevCommit b = commit(tree(file("0", blob("b"))), a);
+ RevCommit c = commit(tree(file("0", blob("c"))), a, b);
+ RevCommit d = commit(tree(file("0", blob("d"))), c);
+
+ rw.reset();
+ rw.setFirstParent(true);
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER, true);
+ rw.setTreeFilter(PathFilterGroup.createFromStrings("0"));
+ markStart(d);
+ assertCommit(d, rw.next());
+ assertCommit(c, rw.next());
+ assertNull(rw.next());
+ }
}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkSortTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkSortTest.java
index 6f110fa..18ea2c8 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkSortTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkSortTest.java
@@ -10,9 +10,12 @@
package org.eclipse.jgit.revwalk;
+import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+import org.eclipse.jgit.internal.JGitText;
import org.junit.Test;
public class RevWalkSortTest extends RevWalkTestCase {
@@ -144,4 +147,171 @@
assertCommit(d, rw.next());
assertNull(rw.next());
}
+
+ @Test
+ public void testSort_TOPO_NON_INTERMIX() throws Exception {
+ // c1 is back dated before its parent.
+ //
+ final RevCommit a = commit();
+ final RevCommit b = commit(a);
+ final RevCommit c1 = commit(-5, b);
+ final RevCommit c2 = commit(10, b);
+ final RevCommit d = commit(c1, c2);
+
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ markStart(d);
+ assertCommit(d, rw.next());
+ assertCommit(c2, rw.next());
+ assertCommit(c1, rw.next());
+ assertCommit(b, rw.next());
+ assertCommit(a, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
+ public void testSort_TOPO_NON_INTERMIX_OutOfOrderCommitTimes()
+ throws Exception {
+ // b is committed before c2 in a different line of history.
+ //
+ final RevCommit a = commit();
+ final RevCommit c1 = commit(a);
+ final RevCommit b = commit(a);
+ final RevCommit c2 = commit(c1);
+ final RevCommit d = commit(b, c2);
+
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ markStart(d);
+ assertCommit(d, rw.next());
+ assertCommit(c2, rw.next());
+ assertCommit(c1, rw.next());
+ assertCommit(b, rw.next());
+ assertCommit(a, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
+ public void testSort_TOPO_NON_INTERMIX_MultipleLinesOfHistory()
+ throws Exception {
+ final RevCommit a1 = commit();
+ final RevCommit b1 = commit(a1);
+ final RevCommit a2 = commit(a1, b1);
+ final RevCommit b2 = commit(b1);
+ final RevCommit b3 = commit(b1);
+ final RevCommit a3 = commit(a2, b2);
+ final RevCommit a4 = commit(a3, b3);
+
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ markStart(a4);
+ assertCommit(a4, rw.next());
+ assertCommit(b3, rw.next());
+ assertCommit(a3, rw.next());
+ assertCommit(b2, rw.next());
+ assertCommit(a2, rw.next());
+ assertCommit(b1, rw.next());
+ assertCommit(a1, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
+ public void testSort_TOPO_NON_INTERMIX_REVERSE() throws Exception {
+ // c1 is back dated before its parent.
+ //
+ final RevCommit a = commit();
+ final RevCommit b = commit(a);
+ final RevCommit c1 = commit(-5, b);
+ final RevCommit c2 = commit(10, b);
+ final RevCommit d = commit(c1, c2);
+
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ rw.sort(RevSort.REVERSE, true);
+ markStart(d);
+ assertCommit(a, rw.next());
+ assertCommit(b, rw.next());
+ assertCommit(c1, rw.next());
+ assertCommit(c2, rw.next());
+ assertCommit(d, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
+ public void testSort_TOPO_NON_INTERMIX_REVERSE_MultipleLinesOfHistory()
+ throws Exception {
+ final RevCommit a1 = commit();
+ final RevCommit b1 = commit(a1);
+ final RevCommit a2 = commit(a1, b1);
+ final RevCommit b2 = commit(b1);
+ final RevCommit b3 = commit(b1);
+ final RevCommit a3 = commit(a2, b2);
+ final RevCommit a4 = commit(a3, b3);
+
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ rw.sort(RevSort.REVERSE, true);
+ markStart(a4);
+ assertCommit(a1, rw.next());
+ assertCommit(b1, rw.next());
+ assertCommit(a2, rw.next());
+ assertCommit(b2, rw.next());
+ assertCommit(a3, rw.next());
+ assertCommit(b3, rw.next());
+ assertCommit(a4, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
+ public void testSort_TOPO_NON_INTERMIX_ParentOfMultipleStartChildren()
+ throws Exception {
+ final RevCommit a = commit();
+ final RevCommit b = commit(a);
+ final RevCommit c = commit(a);
+ final RevCommit d1 = commit(a);
+ final RevCommit d2 = commit(d1);
+ final RevCommit e = commit(a);
+
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ markStart(b);
+ markStart(c);
+ markStart(d2);
+ markStart(e);
+ assertCommit(e, rw.next());
+ assertCommit(d2, rw.next());
+ assertCommit(d1, rw.next());
+ assertCommit(c, rw.next());
+ assertCommit(b, rw.next());
+ assertCommit(a, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
+ public void testSort_TOPO_NON_INTERMIX_Uninteresting() throws Exception {
+ final RevCommit a1 = commit();
+ final RevCommit a2 = commit(a1);
+ final RevCommit a3 = commit(a2);
+ final RevCommit b = commit(a1);
+ final RevCommit a4 = commit(a3, b);
+
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ markStart(a4);
+ markUninteresting(a2);
+ assertCommit(a4, rw.next());
+ assertCommit(b, rw.next());
+ assertCommit(a3, rw.next());
+ assertNull(rw.next());
+ }
+
+ @Test
+ public void testSort_TOPO_NON_INTERMIX_and_TOPO_throws() throws Exception {
+ final RevCommit a = commit();
+
+ rw.sort(RevSort.TOPO_KEEP_BRANCH_TOGETHER);
+ rw.sort(RevSort.TOPO, true);
+ markStart(a);
+ try {
+ rw.next();
+ fail("did not throw IllegalStateException");
+ } catch (IllegalStateException e) {
+ assertEquals(
+ JGitText.get().cannotCombineTopoSortWithTopoNonIntermixSort,
+ e.getMessage());
+ }
+ }
}
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 1218ee6..c46cd4a 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -54,6 +54,7 @@
cannotCheckoutFromUnbornBranch=Cannot check out from unborn branch
cannotCheckoutOursSwitchBranch=Checking out ours/theirs is only possible when checking out index, not when switching branches.
cannotCombineSquashWithNoff=Cannot combine --squash with --no-ff.
+cannotCombineTopoSortWithTopoNonIntermixSort=Cannot combine sorts TOPO and TOPO_NON_INTERMIX.
cannotCombineTreeFilterWithRevFilter=Cannot combine TreeFilter {0} with RevFilter {1}.
cannotCommitOnARepoWithState=Cannot commit on a repo with state: {0}
cannotCommitWriteTo=Cannot commit write to {0}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
index 6235dd8..9d8acad 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -82,6 +82,7 @@
/***/ public String cannotCheckoutFromUnbornBranch;
/***/ public String cannotCheckoutOursSwitchBranch;
/***/ public String cannotCombineSquashWithNoff;
+ /***/ public String cannotCombineTopoSortWithTopoNonIntermixSort;
/***/ public String cannotCombineTreeFilterWithRevFilter;
/***/ public String cannotCommitOnARepoWithState;
/***/ public String cannotCommitWriteTo;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java
index 5ce4bc3..4d2684a 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java
@@ -152,6 +152,7 @@
*/
protected void appendCoreFlags(StringBuilder s) {
s.append((flags & RevWalk.TOPO_DELAY) != 0 ? 'o' : '-');
+ s.append((flags & RevWalk.TOPO_QUEUED) != 0 ? 'q' : '-');
s.append((flags & RevWalk.TEMP_MARK) != 0 ? 't' : '-');
s.append((flags & RevWalk.REWRITE) != 0 ? 'r' : '-');
s.append((flags & RevWalk.UNINTERESTING) != 0 ? 'u' : '-');
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevSort.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevSort.java
index fc6ae28..08396a8 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevSort.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevSort.java
@@ -40,6 +40,18 @@
TOPO,
/**
+ * Topological sorting (all children before parents) without intermixing
+ * lines of history.
+ * <p>
+ * This behavior more closely resembles C Git's git-log --topo-order than
+ * {@link #TOPO}. See C Git's topo-order <a href=
+ * "https://git-scm.com/docs/git-log#Documentation/git-log.txt---topo-order">description</a>.
+ *
+ * @since 5.8
+ */
+ TOPO_KEEP_BRANCH_TOGETHER,
+
+ /**
* Flip the output into the reverse ordering.
* <p>
* This strategy can be combined with the others described by this type as
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
index f425e87..6b62fcd 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -131,8 +131,17 @@
*/
static final int TOPO_DELAY = 1 << 5;
+ /**
+ * Temporary mark for use within {@link TopoNonIntermixSortGenerator}.
+ * <p>
+ * This mark indicates the commit has been queued for emission in
+ * {@link TopoSortGenerator} and can be produced. This mark is removed when
+ * the commit has been produced.
+ */
+ static final int TOPO_QUEUED = 1 << 6;
+
/** Number of flag bits we keep internal for our own use. See above flags. */
- static final int RESERVED_FLAGS = 6;
+ static final int RESERVED_FLAGS = 7;
private static final int APP_FLAGS = -1 & ~((1 << RESERVED_FLAGS) - 1);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
index 2c1b0a5..18af012 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
@@ -135,8 +135,18 @@
}
if (walker.hasRevSort(RevSort.TOPO)
- && (g.outputType() & SORT_TOPO) == 0)
+ && walker.hasRevSort(RevSort.TOPO_KEEP_BRANCH_TOGETHER)) {
+ throw new IllegalStateException(JGitText
+ .get().cannotCombineTopoSortWithTopoNonIntermixSort);
+ }
+
+ if (walker.hasRevSort(RevSort.TOPO)
+ && (g.outputType() & SORT_TOPO) == 0) {
g = new TopoSortGenerator(g);
+ } else if (walker.hasRevSort(RevSort.TOPO_KEEP_BRANCH_TOGETHER)
+ && (g.outputType() & SORT_TOPO) == 0) {
+ g = new TopoNonIntermixSortGenerator(g);
+ }
if (walker.hasRevSort(RevSort.REVERSE))
g = new LIFORevQueue(g);
if (boundary)
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoNonIntermixSortGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoNonIntermixSortGenerator.java
new file mode 100644
index 0000000..4f6d417
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoNonIntermixSortGenerator.java
@@ -0,0 +1,117 @@
+/*
+ * Copyright (C) 2020, Google LLC. and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+package org.eclipse.jgit.revwalk;
+
+import java.io.IOException;
+
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+
+/** Sorts commits in topological order without intermixing lines of history. */
+class TopoNonIntermixSortGenerator extends Generator {
+ private static final int TOPO_QUEUED = RevWalk.TOPO_QUEUED;
+
+ private final FIFORevQueue pending;
+
+ private final int outputType;
+
+ /**
+ * Create a new sorter and completely spin the generator.
+ * <p>
+ * When the constructor completes the supplied generator will have no
+ * commits remaining, as all of the commits will be held inside of this
+ * generator's internal buffer.
+ *
+ * @param s
+ * generator to pull all commits out of, and into this buffer.
+ * @throws MissingObjectException
+ * @throws IncorrectObjectTypeException
+ * @throws IOException
+ */
+ TopoNonIntermixSortGenerator(Generator s) throws MissingObjectException,
+ IncorrectObjectTypeException, IOException {
+ super(s.firstParent);
+ pending = new FIFORevQueue(firstParent);
+ outputType = s.outputType() | SORT_TOPO;
+ s.shareFreeList(pending);
+ for (;;) {
+ final RevCommit c = s.next();
+ if (c == null) {
+ break;
+ }
+ if ((c.flags & TOPO_QUEUED) == 0) {
+ for (RevCommit p : c.parents) {
+ p.inDegree++;
+
+ if (firstParent) {
+ break;
+ }
+ }
+ }
+ c.flags |= TOPO_QUEUED;
+ pending.add(c);
+ }
+ }
+
+ @Override
+ int outputType() {
+ return outputType;
+ }
+
+ @Override
+ void shareFreeList(BlockRevQueue q) {
+ q.shareFreeList(pending);
+ }
+
+ @Override
+ RevCommit next() throws MissingObjectException,
+ IncorrectObjectTypeException, IOException {
+ for (;;) {
+ final RevCommit c = pending.next();
+ if (c == null) {
+ return null;
+ }
+
+ if (c.inDegree > 0) {
+ // At least one of our children is missing. We delay
+ // production until all of our children are output.
+ //
+ continue;
+ }
+
+ if ((c.flags & TOPO_QUEUED) == 0) {
+ // c is a parent that already produced or a parent that
+ // was never in the priority queue and should never produce.
+ //
+ continue;
+ }
+
+ for (RevCommit p : c.parents) {
+ if (--p.inDegree == 0 && (p.flags & TOPO_QUEUED) != 0) {
+ // The parent has no unproduced interesting children. unpop
+ // the parent so it goes right behind this child. This means
+ // that this parent commit may appear in "pending" more than
+ // once, but this is safe since upon the second and
+ // subsequent iterations with this commit, it will no longer
+ // have TOPO_QUEUED set, and thus will be skipped.
+ //
+ pending.unpop(p);
+ }
+ if (firstParent) {
+ break;
+ }
+ }
+
+ c.flags &= ~TOPO_QUEUED;
+ return c;
+ }
+ }
+}
