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, 21 insertions, 33 deletions

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 1abcf6962f..5ce4bc33b5 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevObject.java
@@ -151,7 +151,7 @@ public abstract class RevObject extends ObjectIdOwnerMap.Entry {
 	 *            buffer to append a debug description of core RevFlags onto.
 	 */
 	protected void appendCoreFlags(StringBuilder s) {
-		s.append((flags & RevWalk.TOPO_QUEUED) != 0 ? 'o' : '-');
+		s.append((flags & RevWalk.TOPO_DELAY) != 0 ? 'o' : '-');
 		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/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
index 383428c858..f425e87618 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -125,11 +125,11 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 	/**
 	 * Temporary mark for use within {@link TopoSortGenerator}.
 	 * <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.
+	 * This mark indicates the commit could not produce when it wanted to, as at
+	 * least one child was behind it. Commits with this flag are delayed until
+	 * all children have been output first.
 	 */
-	static final int TOPO_QUEUED = 1 << 5;
+	static final int TOPO_DELAY = 1 << 5;
 
 	/** Number of flag bits we keep internal for our own use. See above flags. */
 	static final int RESERVED_FLAGS = 6;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java
index 3c553b06cf..7a5db43a7a 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/TopoSortGenerator.java
@@ -17,7 +17,7 @@ import org.eclipse.jgit.errors.MissingObjectException;
 
 /** Sorts commits in topological order. */
 class TopoSortGenerator extends Generator {
-	private static final int TOPO_QUEUED = RevWalk.TOPO_QUEUED;
+	private static final int TOPO_DELAY = RevWalk.TOPO_DELAY;
 
 	private final FIFORevQueue pending;
 
@@ -47,16 +47,12 @@ class TopoSortGenerator extends Generator {
 			if (c == null) {
 				break;
 			}
-			if ((c.flags & TOPO_QUEUED) == 0) {
-				for (RevCommit p : c.parents) {
-					p.inDegree++;
-
-					if (firstParent) {
-						break;
-					}
+			for (RevCommit p : c.parents) {
+				p.inDegree++;
+				if (firstParent) {
+					break;
 				}
 			}
-			c.flags |= TOPO_QUEUED;
 			pending.add(c);
 		}
 	}
@@ -75,42 +71,34 @@ class TopoSortGenerator extends Generator {
 	RevCommit next() throws MissingObjectException,
 			IncorrectObjectTypeException, IOException {
 		for (;;) {
-			RevCommit c = pending.next();
-			if (c == null) {
+			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.
 				//
+				c.flags |= TOPO_DELAY;
 				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;
-			}
-
+			// All of our children have already produced,
+			// so it is OK for us to produce now as well.
+			//
 			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.
+				if (--p.inDegree == 0 && (p.flags & TOPO_DELAY) != 0) {
+					// This parent tried to come before us, but we are
+					// his last child. unpop the parent so it goes right
+					// behind this child.
 					//
+					p.flags &= ~TOPO_DELAY;
 					pending.unpop(p);
 				}
 				if (firstParent) {
 					break;
 				}
 			}
-
-			c.flags &= ~TOPO_QUEUED;
 			return c;
 		}
 	}