Revert "RevWalk: stop mixing lines of history in topo sort"

This reverts commit b5e764abd21bd4593287361a625ecc49bc0efd77.

PlotWalk uses the TopoSortGenerator, which is causing problems for EGit users
who rely on the emission of commits being somewhat based on date as in the
previous topo-sort algorithm.

Bug: 560529
Change-Id: I3dbd3598a7aeb960de3fc39352699b4f11a8c226
Signed-off-by: Alex Spradlin <alexaspradlin@google.com>

3 files changed, 43 insertions, 159 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/RebaseCommandTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/RebaseCommandTest.java
index d1522e98e2..86239023dc 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/RebaseCommandTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/RebaseCommandTest.java
@@ -563,10 +563,10 @@ public class RebaseCommandTest extends RepositoryTestCase {
 			RevCommit newD = rw.next();
 			assertDerivedFrom(newD, d);
 			assertEquals(2, newD.getParentCount());
-			RevCommit newE = rw.next();
-			assertEquals(e, newE);
 			RevCommit newC = rw.next();
 			assertDerivedFrom(newC, c);
+			RevCommit newE = rw.next();
+			assertEquals(e, newE);
 			assertEquals(newC, newD.getParent(0));
 			assertEquals(e, newD.getParent(1));
 			assertEquals(g, rw.next());
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revplot/PlotCommitListTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revplot/PlotCommitListTest.java
index 45225a2bdc..4e0bba2f28 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revplot/PlotCommitListTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revplot/PlotCommitListTest.java
@@ -254,12 +254,12 @@ public class PlotCommitListTest extends RevWalkTestCase {
 			int posI = test.commit(i).lanePos(childPositions).parents(h)
 					.getLanePos();
 			test.commit(h).lanePos(posI).parents(f);
+			test.commit(g).lanePos(childPositions).parents(a);
 			test.commit(f).lanePos(posI).parents(e, d);
-			test.commit(d).lanePos(1).parents(b);
 			test.commit(e).lanePos(posI).parents(c);
+			test.commit(d).lanePos(2).parents(b);
 			test.commit(c).lanePos(posI).parents(b);
 			test.commit(b).lanePos(posI).parents(a);
-			test.commit(g).lanePos(childPositions).parents(a);
 			test.commit(a).lanePos(0).parents();
 		}
 	}
@@ -325,42 +325,42 @@ public class PlotCommitListTest extends RevWalkTestCase {
 					.lanePos(mainPos);
 			test.commit(merge_update_eclipse)
 					.parents(add_a_clear, update_eclipse).lanePos(mainPos);
-			test.commit(update_eclipse).parents(add_Maven).lanePos(2);
 			test.commit(add_a_clear).parents(fix_broken).lanePos(mainPos);
 			test.commit(fix_broken).parents(merge_disable_comment)
 					.lanePos(mainPos);
 			test.commit(merge_disable_comment)
 					.parents(merge_resolve_handler, disable_comment)
 					.lanePos(mainPos);
-			test.commit(disable_comment).parents(clone_operation).lanePos(3);
+			test.commit(disable_comment).parents(clone_operation).lanePos(2);
 			test.commit(merge_resolve_handler)
 					.parents(clone_operation, resolve_handler).lanePos(mainPos);
-			test.commit(resolve_handler).parents(merge_fix).lanePos(4);
+			test.commit(update_eclipse).parents(add_Maven).lanePos(3);
 			test.commit(clone_operation).parents(merge_changeset_implementation)
 					.lanePos(mainPos);
 			test.commit(merge_changeset_implementation)
 					.parents(merge_disable_source, changeset_implementation)
 					.lanePos(mainPos);
-			test.commit(changeset_implementation).parents(clear_repositorycache)
-					.lanePos(1);
 			test.commit(merge_disable_source)
 					.parents(update_eclipse_iplog2, disable_source)
 					.lanePos(mainPos);
-			test.commit(disable_source).parents(merge_use_remote).lanePos(3);
 			test.commit(update_eclipse_iplog2).parents(merge_use_remote)
 					.lanePos(mainPos);
+			test.commit(disable_source).parents(merge_use_remote).lanePos(1);
 			test.commit(merge_use_remote)
 					.parents(update_eclipse_iplog, use_remote).lanePos(mainPos);
-			test.commit(use_remote).parents(clear_repositorycache).lanePos(3);
+			test.commit(changeset_implementation).parents(clear_repositorycache)
+					.lanePos(2);
 			test.commit(update_eclipse_iplog).parents(merge_add_Maven)
 					.lanePos(mainPos);
 			test.commit(merge_add_Maven).parents(findToolBar_layout, add_Maven)
 					.lanePos(mainPos);
-			test.commit(add_Maven).parents(clear_repositorycache).lanePos(2);
 			test.commit(findToolBar_layout).parents(clear_repositorycache)
 					.lanePos(mainPos);
+			test.commit(use_remote).parents(clear_repositorycache).lanePos(1);
+			test.commit(add_Maven).parents(clear_repositorycache).lanePos(3);
 			test.commit(clear_repositorycache).parents(merge_remove)
 					.lanePos(mainPos);
+			test.commit(resolve_handler).parents(merge_fix).lanePos(4);
 			test.commit(merge_remove).parents(add_simple, remove_unused)
 					.lanePos(mainPos);
 			test.commit(remove_unused).parents(merge_fix).lanePos(1);
@@ -453,36 +453,33 @@ public class PlotCommitListTest extends RevWalkTestCase {
 			pcl.source(pw);
 			pcl.fillTo(Integer.MAX_VALUE);
 
-			Set<Integer> positions = asSet(0, 1);
-			CommitListAssert test = new CommitListAssert(pcl);
-			int posA = test.commit(a5).lanePos(positions).getLanePos();
-			test.commit(a4);
-			test.commit(a3).lanePos(posA);
-			test.commit(e);
-			test.commit(d);
-			test.commit(a2).lanePos(posA);
-			int posB = test.commit(b3).lanePos(positions).getLanePos();
-			test.commit(b2).lanePos(posB);
-			test.commit(b1).lanePos(posB);
-			test.commit(c);
-			test.commit(a1).lanePos(posA);
-			test.noMoreCommits();
-			assertNotEquals("a lane is the same as b lane", posA, posB);
+			// test that the commits b1, b2 and b3 are on the same position
+			int bPos = pcl.get(9).lane.position; // b1
+			assertEquals("b2 is an a different position", bPos,
+					pcl.get(7).lane.position);
+			assertEquals("b3 is on a different position", bPos,
+					pcl.get(4).lane.position);
+
+			// test that nothing blocks the connections between b1, b2 and b3
+			assertNotEquals("b lane is blocked by c", bPos,
+					pcl.get(8).lane.position);
+			assertNotEquals("b lane is blocked by a2", bPos,
+					pcl.get(6).lane.position);
+			assertNotEquals("b lane is blocked by d", bPos,
+					pcl.get(5).lane.position);
 		}
 	}
 
 	/**
 	 * <pre>
 	 *    b3
-	 * a5 |
-	 * |  |
 	 * a4 |
 	 * | \|
 	 * |  b2
 	 * a3 |
 	 * | \|
-	 * |  b1
 	 * a2 |
+	 * |  b1
 	 * | /
 	 * a1
 	 * </pre>
@@ -497,11 +494,10 @@ public class PlotCommitListTest extends RevWalkTestCase {
 		final RevCommit a3 = commit(a2, b1);
 		final RevCommit b2 = commit(b1);
 		final RevCommit a4 = commit(a3, b2);
-		final RevCommit a5 = commit(a4);
 		final RevCommit b3 = commit(b2);
 
 		try (PlotWalk pw = new PlotWalk(db)) {
-			pw.markStart(pw.lookupCommit(a5));
+			pw.markStart(pw.lookupCommit(a4));
 			pw.markStart(pw.lookupCommit(b3));
 			PlotCommitList<PlotLane> pcl = new PlotCommitList<>();
 			pcl.source(pw);
@@ -510,12 +506,11 @@ public class PlotCommitListTest extends RevWalkTestCase {
 			Set<Integer> positions = asSet(0, 1);
 			CommitListAssert test = new CommitListAssert(pcl);
 			int posB = test.commit(b3).lanePos(positions).getLanePos();
-			int posA = test.commit(a5).lanePos(positions).getLanePos();
-			test.commit(a4).lanePos(posA);
+			int posA = test.commit(a4).lanePos(positions).getLanePos();
 			test.commit(b2).lanePos(posB);
 			test.commit(a3).lanePos(posA);
-			test.commit(b1).lanePos(posB);
 			test.commit(a2).lanePos(posA);
+			test.commit(b1).lanePos(posB);
 			test.commit(a1).lanePos(posA);
 			test.noMoreCommits();
 		}
@@ -524,17 +519,13 @@ public class PlotCommitListTest extends RevWalkTestCase {
 	/**
 	 * <pre>
 	 * a4
-	 * |
-	 * a3
-	 * | \\
-	 * a2  \\
-	 * |    \\
-	 * |  b3 ||
-	 * |  |  ||
-	 * |  b2 ||
-	 * |  | //
-	 * |  b1
-	 * |  |
+	 * |   b3
+	 * a3  |
+	 * | \\|
+	 * |   |\\
+	 * |   b2||
+	 * a2  | //
+	 * |   b1
 	 * | /
 	 * a1
 	 * </pre>
@@ -561,10 +552,10 @@ public class PlotCommitListTest extends RevWalkTestCase {
 			Set<Integer> positions = asSet(0, 1);
 			CommitListAssert test = new CommitListAssert(pcl);
 			int posA = test.commit(a4).lanePos(positions).getLanePos();
-			test.commit(a3).lanePos(posA);
-			test.commit(a2).lanePos(posA);
 			int posB = test.commit(b3).lanePos(positions).getLanePos();
+			test.commit(a3).lanePos(posA);
 			test.commit(b2).lanePos(posB);
+			test.commit(a2).lanePos(posA);
 			// b1 is not repositioned, uses "detour lane"
 			// (drawn as a double arc in the ascii graph above)
 			test.commit(b1).lanePos(posB);
@@ -578,14 +569,13 @@ public class PlotCommitListTest extends RevWalkTestCase {
 	 *      b2
 	 * a4   |
 	 * |  \ |
-	 * |    b1
-	 * a3   |
+	 * a3  \|
 	 * | \  |
 	 * |  c |
 	 * | /  |
 	 * a2   |
-	 * |    |
-	 * |   /
+	 * |    b1
+	 *     /
 	 * |  /
 	 * a1
 	 * </pre>
@@ -614,10 +604,10 @@ public class PlotCommitListTest extends RevWalkTestCase {
 			CommitListAssert test = new CommitListAssert(pcl);
 			int posB = test.commit(b2).lanePos(positions).getLanePos();
 			int posA = test.commit(a4).lanePos(positions).getLanePos();
-			test.commit(b1).lanePos(posB); // repositioned to go around c
 			test.commit(a3).lanePos(posA);
 			test.commit(c).lanePos(positions);
 			test.commit(a2).lanePos(posA);
+			test.commit(b1).lanePos(posB); // repositioned to go around c
 			test.commit(a1).lanePos(posA);
 			test.noMoreCommits();
 		}
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 3f29e09e39..6f110fa317 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
@@ -144,110 +144,4 @@ public class RevWalkSortTest extends RevWalkTestCase {
 		assertCommit(d, rw.next());
 		assertNull(rw.next());
 	}
-
-        @Test
-	public void testSort_TOPO_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);
-		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_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);
-		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_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);
-		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_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);
-		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_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);
-		markStart(a4);
-		markUninteresting(a2);
-		assertCommit(a4, rw.next());
-		assertCommit(b, rw.next());
-		assertCommit(a3, rw.next());
-		assertNull(rw.next());
-	}
 }