[JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER

["Shawn O. Pearce" <spearce@spearce.org>]

I must have been on crack the day I wrote 3b27268f49 ("Allow RevWalk
users to ask for FIFO style ordering").  Its a really bad idea.

Applications can get themselves into a situation where they process
one branch long before another, and then abort too early, before all
commits have been correctly flagged UNINTERESTING.

For example, given the graph:

  Z-A------------B
  |             /
  |    ---------
  \   /
   Q-R-S-T-U-V

If B is "interesting" and A,V are UNINTERESTING, without forcing the
commit timestamp ordering in the pending queue we wind up processing
all of B-Z, producing R,Q as "interesting" output in the process, and
terminate before S can even be parsed. Consequently we never push the
UNINTERESTING flag down onto R, and R,Q produced when they shouldn't.

We now require that the pending queue use a DateRevQueue instead of
the FIFORevQueue, so that in the above graph S must be parsed before
we can even consider R or A, even though R,A were reached earlier.
This of course still assumes there is no clock skew between S and R.
The next commit will address some limited clock skew issues.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/revwalk/PendingGenerator.java |    8 +++-----
 .../src/org/spearce/jgit/revwalk/RevSort.java      |   11 -----------
 .../src/org/spearce/jgit/revwalk/RevWalk.java      |    6 +++---
 .../org/spearce/jgit/revwalk/StartGenerator.java   |    8 ++------
 4 files changed, 8 insertions(+), 25 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
index 25b2966..144e909 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
@@ -62,7 +62,7 @@
 
 	private final RevWalk walker;
 
-	private final AbstractRevQueue pending;
+	private final DateRevQueue pending;
 
 	private final RevFilter filter;
 
@@ -70,7 +70,7 @@
 
 	boolean canDispose;
 
-	PendingGenerator(final RevWalk w, final AbstractRevQueue p,
+	PendingGenerator(final RevWalk w, final DateRevQueue p,
 			final RevFilter f, final int out) {
 		walker = w;
 		pending = p;
@@ -81,9 +81,7 @@ PendingGenerator(final RevWalk w, final AbstractRevQueue p,
 
 	@Override
 	int outputType() {
-		if (pending instanceof DateRevQueue)
-			return output | SORT_COMMIT_TIME_DESC;
-		return output;
+		return output | SORT_COMMIT_TIME_DESC;
 	}
 
 	@Override
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java
index b0a03ad..8c3eaed 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java
@@ -49,17 +49,6 @@
 	NONE,
 
 	/**
-	 * Maintain the order commits were marked as starting points.
-	 * <p>
-	 * This strategy is largely a FIFO strategy; commits are enumerated in the
-	 * order they were added to the RevWalk by the application. Parents not yet
-	 * visited are added behind all commits already enqueued for visiting.
-	 * <p>
-	 * This strategy should not be combined with {@link #COMMIT_TIME_DESC}.
-	 */
-	START_ORDER,
-
-	/**
 	 * Sort by commit time, descending (newest first, oldest last).
 	 * <p>
 	 * This strategy can be combined with {@link #TOPO}.
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java
index c8ec458..316f722 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java
@@ -187,7 +187,7 @@ public RevWalk(final Repository repo) {
 		idBuffer = new MutableObjectId();
 		objects = new ObjectIdSubclassMap<RevObject>();
 		roots = new ArrayList<RevCommit>();
-		queue = new FIFORevQueue();
+		queue = new DateRevQueue();
 		pending = new StartGenerator(this);
 		sorting = EnumSet.of(RevSort.NONE);
 		filter = RevFilter.ALL;
@@ -915,7 +915,7 @@ protected void reset(int retainFlags) {
 
 		curs.release();
 		roots.clear();
-		queue = new FIFORevQueue();
+		queue = new DateRevQueue();
 		pending = new StartGenerator(this);
 	}
 
@@ -934,7 +934,7 @@ public void dispose() {
 		objects.clear();
 		curs.release();
 		roots.clear();
-		queue = new FIFORevQueue();
+		queue = new DateRevQueue();
 		pending = new StartGenerator(this);
 	}
 
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java
index 1b7947f..bf7067a 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java
@@ -108,11 +108,7 @@ RevCommit next() throws MissingObjectException,
 		}
 
 		int pendingOutputType = 0;
-		if (walker.hasRevSort(RevSort.START_ORDER)
-				&& !(q instanceof FIFORevQueue))
-			q = new FIFORevQueue(q);
-		if (walker.hasRevSort(RevSort.COMMIT_TIME_DESC)
-				&& !(q instanceof DateRevQueue))
+		if (!(q instanceof DateRevQueue))
 			q = new DateRevQueue(q);
 		if (tf != TreeFilter.ALL) {
 			rf = AndRevFilter.create(rf, new RewriteTreeFilter(w, tf));
@@ -120,7 +116,7 @@ RevCommit next() throws MissingObjectException,
 		}
 
 		walker.queue = q;
-		g = new PendingGenerator(w, q, rf, pendingOutputType);
+		g = new PendingGenerator(w, (DateRevQueue) q, rf, pendingOutputType);
 
 		if (boundary) {
 			// Because the boundary generator may produce uninteresting
-- 
1.6.2.288.gc3f22