Merge "RevWalk: new topo sort to not mix lines of history"

9 files changed, 375 insertions, 2 deletions

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 4a3b04d4e2..c8256b89c0 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 @@ public class FirstParentRevWalkTest extends RevWalkTestCase {
 	}
 
 	@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 @@ public class FirstParentRevWalkTest extends RevWalkTestCase {
 		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 6f110fa317..18ea2c83ce 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 @@ public class RevWalkSortTest extends RevWalkTestCase {
 		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 1218ee612d..c46cd4a36f 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 @@ cannotChangeActionOnComment=Cannot change action on comment line in git-rebase-t
 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 6235dd83d9..9d8acad7a8 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 class JGitText extends TranslationBundle {
 	/***/ 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 5ce4bc33b5..4d2684a0f0 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 @@ public abstract class RevObject extends ObjectIdOwnerMap.Entry {
 	 */
 	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 fc6ae28dc9..08396a8061 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 @@ public enum RevSort {
 	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 f425e87618..6b62fcdf6d 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 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 	 */
 	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 2c1b0a59ee..18af012afd 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 @@ class StartGenerator extends Generator {
 		}
 
 		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 0000000000..4f6d417ed1
--- /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;
+		}
+	}
+}