All of lore.kernel.org
 help / color / mirror / Atom feed
* [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING
@ 2009-03-13  2:07 Shawn O. Pearce
  2009-03-13  2:07 ` [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues Shawn O. Pearce
  2009-03-13 20:00 ` [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Robin Rosenberg
  0 siblings, 2 replies; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-13  2:07 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

Today I uncovered some ugly cases with "jgit rev-list B ^A", where
some commits reachable from A were still being output, even though
we asked that they be excluded.

This series attempts to fix it by forcing date ordering, and delaying
output a little to try and work over any clock skew discovered near
the end of the traversal, just before we give up.

Shawn O. Pearce (5):
  Show critical flags in debug toString() descriptions of rev queues
  Make RevObject.getType implementations final
  Remove the horribly stupid RevSort.START_ORDER
  Fix RevWalk with Linus Torvald's occasional bad commit date hack
  Avoid incorrect output of UNINTERESTING commits when clock skew
    occurs

 .../org/spearce/jgit/revwalk/AbstractRevQueue.java |    5 +
 .../src/org/spearce/jgit/revwalk/DateRevQueue.java |   10 +--
 .../org/spearce/jgit/revwalk/DelayRevQueue.java    |   92 ++++++++++++++++++++
 .../src/org/spearce/jgit/revwalk/FIFORevQueue.java |   10 +--
 .../jgit/revwalk/FixUninterestingGenerator.java    |   77 ++++++++++++++++
 .../src/org/spearce/jgit/revwalk/LIFORevQueue.java |   10 +--
 .../org/spearce/jgit/revwalk/PendingGenerator.java |   59 +++++++++++--
 .../src/org/spearce/jgit/revwalk/RevBlob.java      |    2 +-
 .../src/org/spearce/jgit/revwalk/RevCommit.java    |   15 +++-
 .../src/org/spearce/jgit/revwalk/RevObject.java    |   24 +++++
 .../src/org/spearce/jgit/revwalk/RevSort.java      |   11 ---
 .../src/org/spearce/jgit/revwalk/RevTag.java       |    2 +-
 .../src/org/spearce/jgit/revwalk/RevTree.java      |    2 +-
 .../src/org/spearce/jgit/revwalk/RevWalk.java      |    6 +-
 .../org/spearce/jgit/revwalk/StartGenerator.java   |   27 ++++--
 15 files changed, 296 insertions(+), 56 deletions(-)
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java

^ permalink raw reply	[flat|nested] 13+ messages in thread

* [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues
  2009-03-13  2:07 [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Shawn O. Pearce
@ 2009-03-13  2:07 ` Shawn O. Pearce
  2009-03-13  2:07   ` [JGIT PATCH 2/5] Make RevObject.getType implementations final Shawn O. Pearce
  2009-03-13 20:00 ` [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Robin Rosenberg
  1 sibling, 1 reply; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-13  2:07 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

These can help identify the state of each object, especially the
important UNINTERESTING flag being present (or not).

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/revwalk/AbstractRevQueue.java |    5 ++++
 .../src/org/spearce/jgit/revwalk/DateRevQueue.java |   10 ++------
 .../src/org/spearce/jgit/revwalk/FIFORevQueue.java |   10 ++------
 .../src/org/spearce/jgit/revwalk/LIFORevQueue.java |   10 ++------
 .../src/org/spearce/jgit/revwalk/RevCommit.java    |   12 ++++++++++
 .../src/org/spearce/jgit/revwalk/RevObject.java    |   23 ++++++++++++++++++++
 6 files changed, 49 insertions(+), 21 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractRevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractRevQueue.java
index 4cf7dae..5bb969d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractRevQueue.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/AbstractRevQueue.java
@@ -115,6 +115,11 @@ int outputType() {
 		return outputType;
 	}
 
+	protected static void describe(final StringBuilder s, final RevCommit c) {
+		s.append(c.toString());
+		s.append('\n');
+	}
+
 	private static class AlwaysEmptyQueue extends AbstractRevQueue {
 		@Override
 		public void add(RevCommit c) {
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/DateRevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/DateRevQueue.java
index f797477..210f985 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/DateRevQueue.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/DateRevQueue.java
@@ -126,13 +126,9 @@ int outputType() {
 	}
 
 	public String toString() {
-		final StringBuffer s = new StringBuffer();
-		for (Entry q = head; q != null; q = q.next) {
-			s.append(q.commit.name());
-			s.append(' ');
-			s.append(q.commit.commitTime);
-			s.append('\n');
-		}
+		final StringBuilder s = new StringBuilder();
+		for (Entry q = head; q != null; q = q.next)
+			describe(s, q.commit);
 		return s.toString();
 	}
 
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/FIFORevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/FIFORevQueue.java
index 2c4c003..f086928 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/FIFORevQueue.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/FIFORevQueue.java
@@ -149,14 +149,10 @@ void removeFlag(final int f) {
 	}
 
 	public String toString() {
-		final StringBuffer s = new StringBuffer();
+		final StringBuilder s = new StringBuilder();
 		for (Block q = head; q != null; q = q.next) {
-			for (int i = q.headIndex; i < q.tailIndex; i++) {
-				s.append(q.commits[i].name());
-				s.append(' ');
-				s.append(q.commits[i].commitTime);
-				s.append('\n');
-			}
+			for (int i = q.headIndex; i < q.tailIndex; i++)
+				describe(s, q.commits[i]);
 		}
 		return s.toString();
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/LIFORevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/LIFORevQueue.java
index 5e885c0..045f7f1 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/LIFORevQueue.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/LIFORevQueue.java
@@ -104,14 +104,10 @@ boolean anybodyHasFlag(final int f) {
 	}
 
 	public String toString() {
-		final StringBuffer s = new StringBuffer();
+		final StringBuilder s = new StringBuilder();
 		for (Block q = head; q != null; q = q.next) {
-			for (int i = q.headIndex; i < q.tailIndex; i++) {
-				s.append(q.commits[i].name());
-				s.append(' ');
-				s.append(q.commits[i].commitTime);
-				s.append('\n');
-			}
+			for (int i = q.headIndex; i < q.tailIndex; i++)
+				describe(s, q.commits[i]);
 		}
 		return s.toString();
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java
index de11c39..1b25fce 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java
@@ -388,4 +388,16 @@ public void dispose() {
 		flags &= ~PARSED;
 		buffer = null;
 	}
+
+	@Override
+	public String toString() {
+		final StringBuilder s = new StringBuilder();
+		s.append(Constants.typeString(getType()));
+		s.append(name());
+		s.append(' ');
+		s.append(commitTime);
+		s.append(' ');
+		appendCoreFlags(s);
+		return s.toString();
+	}
 }
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java
index 451205c..7dadb7b 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java
@@ -167,4 +167,27 @@ public void remove(final RevFlagSet set) {
 	public void dispose() {
 		// Nothing needs to be done for most objects.
 	}
+
+	@Override
+	public String toString() {
+		final StringBuilder s = new StringBuilder();
+		s.append(Constants.typeString(getType()));
+		s.append(name());
+		s.append(' ');
+		appendCoreFlags(s);
+		return s.toString();
+	}
+
+	/**
+	 * @param s
+	 *            buffer to append a debug description of core RevFlags onto.
+	 */
+	protected void appendCoreFlags(final StringBuilder s) {
+		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' : '-');
+		s.append((flags & RevWalk.SEEN) != 0 ? 's' : '-');
+		s.append((flags & RevWalk.PARSED) != 0 ? 'p' : '-');
+	}
 }
-- 
1.6.2.288.gc3f22

^ permalink raw reply related	[flat|nested] 13+ messages in thread

* [JGIT PATCH 2/5] Make RevObject.getType implementations final
  2009-03-13  2:07 ` [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues Shawn O. Pearce
@ 2009-03-13  2:07   ` Shawn O. Pearce
  2009-03-13  2:07     ` [JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER Shawn O. Pearce
  0 siblings, 1 reply; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-13  2:07 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

These methods should never be overridden once defined by the base
class of RevCommit, RevTree, RevBlob or RevTag.  An override is
only going to provide confusion to calls who rely upon the return
value to know if a downcast is safe.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/revwalk/RevBlob.java      |    2 +-
 .../src/org/spearce/jgit/revwalk/RevCommit.java    |    3 ++-
 .../src/org/spearce/jgit/revwalk/RevObject.java    |    1 +
 .../src/org/spearce/jgit/revwalk/RevTag.java       |    2 +-
 .../src/org/spearce/jgit/revwalk/RevTree.java      |    2 +-
 5 files changed, 6 insertions(+), 4 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevBlob.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevBlob.java
index 66cdc02..cf241cf 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevBlob.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevBlob.java
@@ -58,7 +58,7 @@ void parse(final RevWalk walk) {
 	}
 	
 	@Override
-	public int getType() {
+	public final int getType() {
 		return Constants.OBJ_BLOB;
 	}
 }
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java
index 1b25fce..2a59ec4 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevCommit.java
@@ -139,7 +139,7 @@ else if (nParents == 1) {
 	}
 	
 	@Override
-	public int getType() {
+	public final int getType() {
 		return Constants.OBJ_COMMIT;
 	}
 
@@ -393,6 +393,7 @@ public void dispose() {
 	public String toString() {
 		final StringBuilder s = new StringBuilder();
 		s.append(Constants.typeString(getType()));
+		s.append(' ');
 		s.append(name());
 		s.append(' ');
 		s.append(commitTime);
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java
index 7dadb7b..8c7cc23 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevObject.java
@@ -172,6 +172,7 @@ public void dispose() {
 	public String toString() {
 		final StringBuilder s = new StringBuilder();
 		s.append(Constants.typeString(getType()));
+		s.append(' ');
 		s.append(name());
 		s.append(' ');
 		appendCoreFlags(s);
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTag.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTag.java
index aba8744..cace82d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTag.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTag.java
@@ -99,7 +99,7 @@ void parseCanonical(final RevWalk walk, final byte[] rawTag)
 	}
 
 	@Override
-	public int getType() {
+	public final int getType() {
 		return Constants.OBJ_TAG;
 	}
 
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTree.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTree.java
index e1cd4b5..4d767e4 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTree.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevTree.java
@@ -58,7 +58,7 @@ void parse(final RevWalk walk) {
 	}
 	
 	@Override
-	public int getType() {
+	public final int getType() {
 		return Constants.OBJ_TREE;
 	}
 }
-- 
1.6.2.288.gc3f22

^ permalink raw reply related	[flat|nested] 13+ messages in thread

* [JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER
  2009-03-13  2:07   ` [JGIT PATCH 2/5] Make RevObject.getType implementations final Shawn O. Pearce
@ 2009-03-13  2:07     ` Shawn O. Pearce
  2009-03-13  2:07       ` [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce
  0 siblings, 1 reply; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-13  2:07 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

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

^ permalink raw reply related	[flat|nested] 13+ messages in thread

* [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack
  2009-03-13  2:07     ` [JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER Shawn O. Pearce
@ 2009-03-13  2:07       ` Shawn O. Pearce
  2009-03-13  2:07         ` [JGIT PATCH 5/5] Avoid incorrect output of UNINTERESTING commits when clock skew occurs Shawn O. Pearce
  2009-03-14  0:54         ` [JGIT PATCH 4/5 v2] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce
  0 siblings, 2 replies; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-13  2:07 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

In git-core commit 7d004199d134c9d465e013064f72dbc04507f6c0 Linus
describes a hack he created to improve the handling of cases where
commit dates are out of order, such as a child commit having a date
older than its parent.  These cases can show up when there is bad
imported data, or significant clock skew between distributed peers.

The original git-core bug report identified a failure in:

  git rev-list A..B C

where commits contained in both A and B were reported, due to out
of order commit dates.

We keep running until the most recent commit in the pending queue
is more recent than the last commit sent to the caller.  If the
pending queue suddenly goes "backwards" due to one of our parent's
having a more recent commit date, this new check ensures we will
keep processing the graph until we see a more consistent cut.

We process an extra OVER_SCAN commits after we decide that all
remaining commits are UNINTERESTING.  Processing these extra
commits ensures flags are carried back further in the graph,
increasing the chances that we correctly mark relevant nodes.

As a result of this hack, we may produce a commit to our caller,
but then later mark it UNINTERESTING if we discover date skew.
To handle such cases, callers could buffer produced commits and
filter out those that are UNINTERESTING, but this somewhat costly
and may not always be necessary.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/revwalk/PendingGenerator.java |   51 ++++++++++++++++++--
 1 files changed, 47 insertions(+), 4 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 144e909..cd24e8f 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
@@ -42,6 +42,7 @@
 import org.spearce.jgit.errors.IncorrectObjectTypeException;
 import org.spearce.jgit.errors.MissingObjectException;
 import org.spearce.jgit.errors.StopWalkException;
+import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.revwalk.filter.RevFilter;
 
 /**
@@ -60,6 +61,24 @@
 
 	private static final int UNINTERESTING = RevWalk.UNINTERESTING;
 
+	/**
+	 * Number of additional commits to scan after we think we are done.
+	 * <p>
+	 * This small buffer of commits is scanned to ensure we didn't miss anything
+	 * as a result of clock skew when the commits were made. We need to set our
+	 * constant to 1 additional commit due to the use of a pre-increment
+	 * operator when accessing the value.
+	 */
+	private static final int OVER_SCAN = 5 + 1;
+
+	/** A commit near the end of time, to initialize {@link #last} with. */
+	private static final RevCommit INIT_LAST;
+
+	static {
+		INIT_LAST = new RevCommit(ObjectId.zeroId());
+		INIT_LAST.commitTime = Integer.MAX_VALUE;
+	}
+
 	private final RevWalk walker;
 
 	private final DateRevQueue pending;
@@ -68,6 +87,17 @@
 
 	private final int output;
 
+	/** Last commit produced to the caller from {@link #next()}. */
+	private RevCommit last = INIT_LAST;
+
+	/**
+	 * Number of commits we have remaining in our over-scan allotment.
+	 * <p>
+	 * Only relevant if there are {@link #UNINTERESTING} commits in the
+	 * {@link #pending} queue.
+	 */
+	private int overScan = OVER_SCAN;
+
 	boolean canDispose;
 
 	PendingGenerator(final RevWalk w, final DateRevQueue p,
@@ -112,14 +142,27 @@ RevCommit next() throws MissingObjectException,
 				walker.carryFlagsImpl(c);
 
 				if ((c.flags & UNINTERESTING) != 0) {
-					if (pending.everbodyHasFlag(UNINTERESTING))
-						throw StopWalkException.INSTANCE;
-					c.dispose();
+					if (pending.everbodyHasFlag(UNINTERESTING)) {
+						final RevCommit n = pending.peek();
+						if (n != null && n.commitTime <= last.commitTime) {
+							// This is too close to call. The next commit we
+							// would pop is before the last one we produced.
+							// We have to keep going to ensure that we carry
+							// flags as much as necessary.
+							//
+							overScan = OVER_SCAN;
+						} else if (--overScan == 0)
+							throw StopWalkException.INSTANCE;
+					} else {
+						overScan = OVER_SCAN;
+					}
+					if (canDispose)
+						c.dispose();
 					continue;
 				}
 
 				if (produce)
-					return c;
+					return last = c;
 				else if (canDispose)
 					c.dispose();
 			}
-- 
1.6.2.288.gc3f22

^ permalink raw reply related	[flat|nested] 13+ messages in thread

* [JGIT PATCH 5/5] Avoid incorrect output of UNINTERESTING commits when clock skew occurs
  2009-03-13  2:07       ` [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce
@ 2009-03-13  2:07         ` Shawn O. Pearce
  2009-03-14  0:54         ` [JGIT PATCH 4/5 v2] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce
  1 sibling, 0 replies; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-13  2:07 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

The prior commit added functionality to scan a few extra commits when
we otherwise would have aborted due to everything left being colored
UNINTERESTING.  When that happens we may wind up coloring a commit
that we already produced to the caller, giving the caller an incorrect
result set.

If we insert a fully buffered generator in the pipeline, such as that
used for RevSort.TOPO or RevSort.REVERSE, we can easily filter these
late-colored commits out before we show them to the application.  But
otherwise we delay the output by 6 commits, just long enough to give
PendingGenerator a reasonable chance at getting the coloring right.

This is only an approximation.  It is still possible for commits to
produce when they should be UNINTERESTING, such as if more than the
OVER_SCAN limit had clock skew between two branches and the common
merge base, even if we are fully buffering our output.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/revwalk/DelayRevQueue.java    |   92 ++++++++++++++++++++
 .../jgit/revwalk/FixUninterestingGenerator.java    |   77 ++++++++++++++++
 .../org/spearce/jgit/revwalk/PendingGenerator.java |    2 +-
 .../org/spearce/jgit/revwalk/StartGenerator.java   |   23 ++++-
 4 files changed, 189 insertions(+), 5 deletions(-)
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java
new file mode 100644
index 0000000..1eb7064
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/DelayRevQueue.java
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2009, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import java.io.IOException;
+
+import org.spearce.jgit.errors.IncorrectObjectTypeException;
+import org.spearce.jgit.errors.MissingObjectException;
+
+/**
+ * Delays commits to be at least {@link PendingGenerator#OVER_SCAN} late.
+ * <p>
+ * This helps to "fix up" weird corner cases resulting from clock skew, by
+ * slowing down what we produce to the caller we get a better chance to ensure
+ * PendingGenerator reached back far enough in the graph to correctly mark
+ * commits {@link RevWalk#UNINTERESTING} if necessary.
+ * <p>
+ * This generator should appear before {@link FixUninterestingGenerator} if the
+ * lower level {@link #pending} isn't already fully buffered.
+ */
+final class DelayRevQueue extends Generator {
+	private static final int OVER_SCAN = PendingGenerator.OVER_SCAN;
+
+	private final Generator pending;
+
+	private final FIFORevQueue delay;
+
+	private int size;
+
+	DelayRevQueue(final Generator g) {
+		pending = g;
+		delay = new FIFORevQueue();
+	}
+
+	@Override
+	int outputType() {
+		return pending.outputType();
+	}
+
+	@Override
+	RevCommit next() throws MissingObjectException,
+			IncorrectObjectTypeException, IOException {
+		while (size < OVER_SCAN) {
+			final RevCommit c = pending.next();
+			if (c == null)
+				break;
+			delay.add(c);
+			size++;
+		}
+
+		final RevCommit c = delay.next();
+		if (c == null)
+			return null;
+		size--;
+		return c;
+	}
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java
new file mode 100644
index 0000000..6a9ba61
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/FixUninterestingGenerator.java
@@ -0,0 +1,77 @@
+/*
+ * Copyright (C) 2009, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import java.io.IOException;
+
+import org.spearce.jgit.errors.IncorrectObjectTypeException;
+import org.spearce.jgit.errors.MissingObjectException;
+
+/**
+ * Filters out commits marked {@link RevWalk#UNINTERESTING}.
+ * <p>
+ * This generator is only in front of another generator that has fully buffered
+ * commits, such that we are called only after the {@link PendingGenerator} has
+ * exhausted its input queue and given up. It skips over any uninteresting
+ * commits that may have leaked out of the PendingGenerator due to clock skew
+ * being detected in the commit objects.
+ */
+final class FixUninterestingGenerator extends Generator {
+	private final Generator pending;
+
+	FixUninterestingGenerator(final Generator g) {
+		pending = g;
+	}
+
+	@Override
+	int outputType() {
+		return pending.outputType();
+	}
+
+	@Override
+	RevCommit next() throws MissingObjectException,
+			IncorrectObjectTypeException, IOException {
+		for (;;) {
+			final RevCommit c = pending.next();
+			if (c == null)
+				return null;
+			if ((c.flags & RevWalk.UNINTERESTING) == 0)
+				return c;
+		}
+	}
+}
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 cd24e8f..ebbb39f 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
@@ -69,7 +69,7 @@
 	 * constant to 1 additional commit due to the use of a pre-increment
 	 * operator when accessing the value.
 	 */
-	private static final int OVER_SCAN = 5 + 1;
+	static final int OVER_SCAN = 5 + 1;
 
 	/** A commit near the end of time, to initialize {@link #last} with. */
 	private static final RevCommit INIT_LAST;
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 bf7067a..3535250 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java
@@ -90,6 +90,7 @@ RevCommit next() throws MissingObjectException,
 			return mbg.next();
 		}
 
+		final boolean uninteresting = q.anybodyHasFlag(RevWalk.UNINTERESTING);
 		boolean boundary = walker.hasRevSort(RevSort.BOUNDARY);
 
 		if (!boundary && walker instanceof ObjectWalk) {
@@ -99,7 +100,7 @@ RevCommit next() throws MissingObjectException,
 			//
 			boundary = true;
 		}
-		if (boundary && !q.anybodyHasFlag(RevWalk.UNINTERESTING)) {
+		if (boundary && !uninteresting) {
 			// If we were not fed uninteresting commits we will never
 			// construct a boundary. There is no reason to include the
 			// extra overhead associated with that in our pipeline.
@@ -107,16 +108,19 @@ RevCommit next() throws MissingObjectException,
 			boundary = false;
 		}
 
+		final DateRevQueue pending;
 		int pendingOutputType = 0;
-		if (!(q instanceof DateRevQueue))
-			q = new DateRevQueue(q);
+		if (q instanceof DateRevQueue)
+			pending = (DateRevQueue)q;
+		else
+			pending = new DateRevQueue(q);
 		if (tf != TreeFilter.ALL) {
 			rf = AndRevFilter.create(rf, new RewriteTreeFilter(w, tf));
 			pendingOutputType |= HAS_REWRITE | NEEDS_REWRITE;
 		}
 
 		walker.queue = q;
-		g = new PendingGenerator(w, (DateRevQueue) q, rf, pendingOutputType);
+		g = new PendingGenerator(w, pending, rf, pendingOutputType);
 
 		if (boundary) {
 			// Because the boundary generator may produce uninteresting
@@ -143,6 +147,17 @@ RevCommit next() throws MissingObjectException,
 			g = new LIFORevQueue(g);
 		if (boundary)
 			g = new BoundaryGenerator(w, g);
+		else if (uninteresting) {
+			// Try to protect ourselves from uninteresting commits producing
+			// due to clock skew in the commit time stamps. Delay such that
+			// we have a chance at coloring enough of the graph correctly,
+			// and then strip any UNINTERESTING nodes that may have leaked
+			// through early.
+			//
+			if (pending.peek() != null)
+				g = new DelayRevQueue(g);
+			g = new FixUninterestingGenerator(g);
+		}
 
 		w.pending = g;
 		return g.next();
-- 
1.6.2.288.gc3f22

^ permalink raw reply related	[flat|nested] 13+ messages in thread

* Re: [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING
  2009-03-13  2:07 [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Shawn O. Pearce
  2009-03-13  2:07 ` [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues Shawn O. Pearce
@ 2009-03-13 20:00 ` Robin Rosenberg
  2009-03-13 22:39   ` [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code Shawn O. Pearce
  1 sibling, 1 reply; 13+ messages in thread
From: Robin Rosenberg @ 2009-03-13 20:00 UTC (permalink / raw)
  To: Shawn O. Pearce; +Cc: git

fredag 13 mars 2009 03:07:37 skrev "Shawn O. Pearce" <spearce@spearce.org>:
> Today I uncovered some ugly cases with "jgit rev-list B ^A", where
> some commits reachable from A were still being output, even though
> we asked that they be excluded.

How about a test suite to prove this is better than before?

-- robin

^ permalink raw reply	[flat|nested] 13+ messages in thread

* [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code
  2009-03-13 20:00 ` [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Robin Rosenberg
@ 2009-03-13 22:39   ` Shawn O. Pearce
  2009-03-14  0:13     ` Shawn O. Pearce
  0 siblings, 1 reply; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-13 22:39 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

These new tests cover some of the common cases we see with using a
RevWalk, and increase our code coverage in this critical area of
the JGit library.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
 > fredag 13 mars 2009 03:07:37 skrev "Shawn O. Pearce" <spearce@spearce.org>:
 > > Today I uncovered some ugly cases with "jgit rev-list B ^A", where
 > > some commits reachable from A were still being output, even though
 > > we asked that they be excluded.
 > 
 > How about a test suite to prove this is better than before?

 Its better.  :-)

 These tests don't pass before the series.  They pass after.
 
 .../org/spearce/jgit/revwalk/RevFlagSetTest.java   |  131 +++++++++++
 .../org/spearce/jgit/revwalk/RevWalkCullTest.java  |   75 +++++++
 .../spearce/jgit/revwalk/RevWalkFilterTest.java    |  233 ++++++++++++++++++++
 .../spearce/jgit/revwalk/RevWalkMergeBaseTest.java |  117 ++++++++++
 .../org/spearce/jgit/revwalk/RevWalkSortTest.java  |  164 ++++++++++++++
 .../org/spearce/jgit/revwalk/RevWalkTestCase.java  |  102 +++++++++
 6 files changed, 822 insertions(+), 0 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java
new file mode 100644
index 0000000..76f3cbb
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java
@@ -0,0 +1,131 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import java.util.Arrays;
+import java.util.Iterator;
+
+public class RevFlagSetTest extends RevWalkTestCase {
+	public void testEmpty() {
+		final RevFlagSet set = new RevFlagSet();
+		assertEquals(0, set.mask);
+		assertEquals(0, set.size());
+		assertNotNull(set.iterator());
+		assertFalse(set.iterator().hasNext());
+	}
+
+	public void testAddOne() {
+		final String flagName = "flag";
+		final RevFlag flag = rw.newFlag(flagName);
+		assertTrue(0 != flag.mask);
+		assertSame(flagName, flag.name);
+
+		final RevFlagSet set = new RevFlagSet();
+		assertTrue(set.add(flag));
+		assertFalse(set.add(flag));
+		assertEquals(flag.mask, set.mask);
+		assertEquals(1, set.size());
+		final Iterator<RevFlag> i = set.iterator();
+		assertTrue(i.hasNext());
+		assertSame(flag, i.next());
+		assertFalse(i.hasNext());
+	}
+
+	public void testAddTwo() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		assertTrue((flag1.mask & flag2.mask) == 0);
+
+		final RevFlagSet set = new RevFlagSet();
+		assertTrue(set.add(flag1));
+		assertTrue(set.add(flag2));
+		assertEquals(flag1.mask | flag2.mask, set.mask);
+		assertEquals(2, set.size());
+	}
+
+	public void testContainsAll() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		final RevFlagSet set1 = new RevFlagSet();
+		assertTrue(set1.add(flag1));
+		assertTrue(set1.add(flag2));
+
+		assertTrue(set1.containsAll(set1));
+		assertTrue(set1.containsAll(Arrays
+				.asList(new RevFlag[] { flag1, flag2 })));
+
+		final RevFlagSet set2 = new RevFlagSet();
+		set2.add(rw.newFlag("flag_3"));
+		assertFalse(set1.containsAll(set2));
+	}
+
+	public void testEquals() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		final RevFlagSet set = new RevFlagSet();
+		assertTrue(set.add(flag1));
+		assertTrue(set.add(flag2));
+
+		assertTrue(new RevFlagSet(set).equals(set));
+		assertTrue(new RevFlagSet(Arrays.asList(new RevFlag[] { flag1, flag2 }))
+				.equals(set));
+	}
+
+	public void testRemove() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		final RevFlagSet set = new RevFlagSet();
+		assertTrue(set.add(flag1));
+		assertTrue(set.add(flag2));
+
+		assertTrue(set.remove(flag1));
+		assertFalse(set.remove(flag1));
+		assertEquals(flag2.mask, set.mask);
+		assertFalse(set.contains(flag1));
+	}
+
+	public void testContains() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		final RevFlagSet set = new RevFlagSet();
+		set.add(flag1);
+		assertTrue(set.contains(flag1));
+		assertFalse(set.contains(flag2));
+		assertFalse(set.contains("bob"));
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java
new file mode 100644
index 0000000..ad78b16
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java
@@ -0,0 +1,75 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import org.spearce.jgit.lib.ObjectId;
+
+public class RevWalkCullTest extends RevWalkTestCase {
+	public void testProperlyCullAllAncestors1() throws Exception {
+		// Credit goes to Junio C Hamano <gitster@pobox.com> for this
+		// test case in git-core (t/t6009-rev-list-parent.sh)
+		//
+		// We induce a clock skew so two is dated before one.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(-2400, a);
+		final ObjectId c = commit(b);
+		final ObjectId d = commit(c);
+
+		markStart(a);
+		markUninteresting(d);
+		assertNull(rw.next());
+	}
+
+	public void testProperlyCullAllAncestors2() throws Exception {
+		// Despite clock skew on c1 being very old it should not
+		// produce, neither should a or b, or any part of that chain.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(-5, b);
+		final ObjectId c2 = commit(10, b);
+		final ObjectId d = commit(c1, c2);
+
+		markStart(d);
+		markUninteresting(c1);
+		assertCommit(d, rw.next());
+		assertCommit(c2, rw.next());
+		assertNull(rw.next());
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java
new file mode 100644
index 0000000..cf2975d
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java
@@ -0,0 +1,233 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import java.io.IOException;
+
+import org.spearce.jgit.errors.IncorrectObjectTypeException;
+import org.spearce.jgit.errors.MissingObjectException;
+import org.spearce.jgit.errors.StopWalkException;
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.revwalk.filter.AndRevFilter;
+import org.spearce.jgit.revwalk.filter.NotRevFilter;
+import org.spearce.jgit.revwalk.filter.OrRevFilter;
+import org.spearce.jgit.revwalk.filter.RevFilter;
+
+public class RevWalkFilterTest extends RevWalkTestCase {
+	private static final MyAll MY_ALL = new MyAll();
+
+	public void testFilter_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(RevFilter.ALL);
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_Negate_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(RevFilter.ALL.negate());
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NOT_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(NotRevFilter.create(RevFilter.ALL));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(RevFilter.NONE);
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NOT_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(NotRevFilter.create(RevFilter.NONE));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_ALL_And_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(AndRevFilter.create(RevFilter.ALL, RevFilter.NONE));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE_And_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(AndRevFilter.create(RevFilter.NONE, RevFilter.ALL));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_ALL_Or_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(OrRevFilter.create(RevFilter.ALL, RevFilter.NONE));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE_Or_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(OrRevFilter.create(RevFilter.NONE, RevFilter.ALL));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_MY_ALL_And_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(AndRevFilter.create(MY_ALL, RevFilter.NONE));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE_And_MY_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(AndRevFilter.create(RevFilter.NONE, MY_ALL));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_MY_ALL_Or_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(OrRevFilter.create(MY_ALL, RevFilter.NONE));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE_Or_MY_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(OrRevFilter.create(RevFilter.NONE, MY_ALL));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NO_MERGES() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(b);
+		final ObjectId c2 = commit(b);
+		final ObjectId d = commit(c1, c2);
+		final ObjectId e = commit(d);
+
+		rw.setRevFilter(RevFilter.NO_MERGES);
+		markStart(e);
+		assertCommit(e, rw.next());
+		assertCommit(c2, rw.next());
+		assertCommit(c1, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	private static class MyAll extends RevFilter {
+		@Override
+		public RevFilter clone() {
+			return this;
+		}
+
+		@Override
+		public boolean include(RevWalk walker, RevCommit cmit)
+				throws StopWalkException, MissingObjectException,
+				IncorrectObjectTypeException, IOException {
+			return true;
+		}
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java
new file mode 100644
index 0000000..b05e774
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java
@@ -0,0 +1,117 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.revwalk.filter.RevFilter;
+
+public class RevWalkMergeBaseTest extends RevWalkTestCase {
+	public void testNone() throws Exception {
+		final ObjectId c1 = commit(commit(commit()));
+		final ObjectId c2 = commit(commit(commit()));
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(c1);
+		markStart(c2);
+		assertNull(rw.next());
+	}
+
+	public void testSimple() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(commit(commit(commit(commit(b)))));
+		final ObjectId c2 = commit(commit(commit(commit(commit(b)))));
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(c1);
+		markStart(c2);
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testMultipleHeads_SameBase1() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(commit(commit(commit(commit(b)))));
+		final ObjectId c2 = commit(commit(commit(commit(commit(b)))));
+		final ObjectId c3 = commit(commit(commit(b)));
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(c1);
+		markStart(c2);
+		markStart(c3);
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testMultipleHeads_SameBase2() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+		final ObjectId d1 = commit(commit(commit(commit(commit(b)))));
+		final ObjectId d2 = commit(commit(commit(commit(commit(c)))));
+		final ObjectId d3 = commit(commit(commit(c)));
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(d1);
+		markStart(d2);
+		markStart(d3);
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testCrissCross() throws Exception {
+		// See http://marc.info/?l=git&m=111463358500362&w=2 for a nice
+		// description of what this test is creating. We don't have a
+		// clean merge base for d,e as they each merged the parents b,c
+		// in different orders.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(a);
+		final ObjectId d = commit(b, c);
+		final ObjectId e = commit(c, b);
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(d);
+		markStart(e);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java
new file mode 100644
index 0000000..6f2eedc
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java
@@ -0,0 +1,164 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import org.spearce.jgit.lib.ObjectId;
+
+public class RevWalkSortTest extends RevWalkTestCase {
+	public void testSort_Default() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(1, a);
+		final ObjectId c = commit(1, b);
+		final ObjectId d = commit(1, c);
+
+		markStart(d);
+		assertCommit(d, rw.next());
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_COMMIT_TIME_DESC() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+		final ObjectId d = commit(c);
+
+		rw.sort(RevSort.COMMIT_TIME_DESC);
+		markStart(d);
+		assertCommit(d, rw.next());
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_REVERSE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+		final ObjectId d = commit(c);
+
+		rw.sort(RevSort.REVERSE);
+		markStart(d);
+		assertCommit(a, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(c, rw.next());
+		assertCommit(d, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_COMMIT_TIME_DESC_OutOfOrder1() throws Exception {
+		// Despite being out of order time-wise, a strand-of-pearls must
+		// still maintain topological order.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(-5, b);
+		final ObjectId d = commit(10, c);
+		assertTrue(parse(a).getCommitTime() < parse(d).getCommitTime());
+		assertTrue(parse(c).getCommitTime() < parse(b).getCommitTime());
+
+		rw.sort(RevSort.COMMIT_TIME_DESC);
+		markStart(d);
+		assertCommit(d, rw.next());
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_COMMIT_TIME_DESC_OutOfOrder2() throws Exception {
+		// c1 is back dated before its parent.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(-5, b);
+		final ObjectId c2 = commit(10, b);
+		final ObjectId d = commit(c1, c2);
+
+		rw.sort(RevSort.COMMIT_TIME_DESC);
+		markStart(d);
+		assertCommit(d, rw.next());
+		assertCommit(c2, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertCommit(c1, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_TOPO() throws Exception {
+		// c1 is back dated before its parent.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(-5, b);
+		final ObjectId c2 = commit(10, b);
+		final ObjectId d = commit(c1, 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());
+	}
+
+	public void testSort_TOPO_REVERSE() throws Exception {
+		// c1 is back dated before its parent.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(-5, b);
+		final ObjectId c2 = commit(10, b);
+		final ObjectId d = commit(c1, c2);
+
+		rw.sort(RevSort.TOPO);
+		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());
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java
new file mode 100644
index 0000000..bd696dd
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import java.util.Date;
+
+import org.spearce.jgit.lib.Commit;
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.ObjectWriter;
+import org.spearce.jgit.lib.PersonIdent;
+import org.spearce.jgit.lib.RepositoryTestCase;
+import org.spearce.jgit.lib.Tree;
+
+/** Support for tests of the {@link RevWalk} class. */
+public abstract class RevWalkTestCase extends RepositoryTestCase {
+	protected ObjectWriter ow;
+
+	protected ObjectId emptyTree;
+
+	protected long nowTick;
+
+	protected RevWalk rw;
+
+	public void setUp() throws Exception {
+		super.setUp();
+		ow = new ObjectWriter(db);
+		emptyTree = ow.writeTree(new Tree(db));
+		nowTick = 1236977987000L;
+		rw = new RevWalk(db);
+	}
+
+	protected void tick(final int secDelta) {
+		nowTick += secDelta * 1000L;
+	}
+
+	protected ObjectId commit(final ObjectId... parents) throws Exception {
+		return commit(1, parents);
+	}
+
+	protected ObjectId commit(final int secDelta, final ObjectId... parents)
+			throws Exception {
+		tick(secDelta);
+		final Commit c = new Commit(db);
+		c.setTreeId(emptyTree);
+		c.setParentIds(parents);
+		c.setAuthor(new PersonIdent(jauthor, new Date(nowTick)));
+		c.setCommitter(new PersonIdent(jcommitter, new Date(nowTick)));
+		c.setMessage("");
+		return ow.writeCommit(c);
+	}
+
+	protected RevCommit parse(final ObjectId commitId) throws Exception {
+		return rw.parseCommit(commitId);
+	}
+
+	protected void markStart(final ObjectId commitId) throws Exception {
+		rw.markStart(parse(commitId));
+	}
+
+	protected void markUninteresting(final ObjectId commitId) throws Exception {
+		rw.markUninteresting(parse(commitId));
+	}
+
+	protected void assertCommit(final ObjectId commitId, final RevCommit commit) {
+		assertEquals(commitId.name(), commit != null ? commit.name() : null);
+	}
+}
-- 
1.6.2.288.gc3f22

^ permalink raw reply related	[flat|nested] 13+ messages in thread

* Re: [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code
  2009-03-13 22:39   ` [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code Shawn O. Pearce
@ 2009-03-14  0:13     ` Shawn O. Pearce
  2009-03-14  0:56       ` [JGIT PATCH 6/5 v2] " Shawn O. Pearce
  0 siblings, 1 reply; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-14  0:13 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

"Shawn O. Pearce" <spearce@spearce.org> wrote:
> These new tests cover some of the common cases we see with using a
> RevWalk, and increase our code coverage in this critical area of
> the JGit library.
> 
> Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
> ---
>  Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
>  > fredag 13 mars 2009 03:07:37 skrev "Shawn O. Pearce" <spearce@spearce.org>:
>  > > Today I uncovered some ugly cases with "jgit rev-list B ^A", where
>  > > some commits reachable from A were still being output, even though
>  > > we asked that they be excluded.
>  > 
>  > How about a test suite to prove this is better than before?
> 
>  Its better.  :-)

Its actually not better.  Although the tests I'm replying to are
right, there's another bug introduced by this series that they
don't detect, but that shows up on the Linux kernel repository.

I have yet to track down the full thing... but I know its busted.
 
-- 
Shawn.

^ permalink raw reply	[flat|nested] 13+ messages in thread

* [JGIT PATCH 4/5 v2] Fix RevWalk with Linus Torvald's occasional bad commit date hack
  2009-03-13  2:07       ` [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce
  2009-03-13  2:07         ` [JGIT PATCH 5/5] Avoid incorrect output of UNINTERESTING commits when clock skew occurs Shawn O. Pearce
@ 2009-03-14  0:54         ` Shawn O. Pearce
  1 sibling, 0 replies; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-14  0:54 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

In git-core commit 7d004199d134c9d465e013064f72dbc04507f6c0 Linus
describes a hack he created to improve the handling of cases where
commit dates are out of order, such as a child commit having a date
older than its parent.  These cases can show up when there is bad
imported data, or significant clock skew between distributed peers.

The original git-core bug report identified a failure in:

  git rev-list A..B C

where commits contained in both A and B were reported, due to out
of order commit dates.

We keep running until the most recent commit in the pending queue
is more recent than the last commit sent to the caller.  If the
pending queue suddenly goes "backwards" due to one of our parent's
having a more recent commit date, this new check ensures we will
keep processing the graph until we see a more consistent cut.

We process an extra OVER_SCAN commits after we decide that all
remaining commits are UNINTERESTING.  Processing these extra
commits ensures flags are carried back further in the graph,
increasing the chances that we correctly mark relevant nodes.

As a result of this hack, we may produce a commit to our caller,
but then later mark it UNINTERESTING if we discover date skew.
To handle such cases, callers could buffer produced commits and
filter out those that are UNINTERESTING, but this somewhat costly
and may not always be necessary.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---

 This version inverts the "n.commitTime <= last.commitTime",
 I confused myself and wrote it backwards.

 The next patch I'm going to send with the tests has a test for
 this condition, to verify its correct.

 .../org/spearce/jgit/revwalk/PendingGenerator.java |   51 ++++++++++++++++++--
 1 files changed, 47 insertions(+), 4 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 144e909..4e24431 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/PendingGenerator.java
@@ -42,6 +42,7 @@
 import org.spearce.jgit.errors.IncorrectObjectTypeException;
 import org.spearce.jgit.errors.MissingObjectException;
 import org.spearce.jgit.errors.StopWalkException;
+import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.revwalk.filter.RevFilter;
 
 /**
@@ -60,6 +61,24 @@
 
 	private static final int UNINTERESTING = RevWalk.UNINTERESTING;
 
+	/**
+	 * Number of additional commits to scan after we think we are done.
+	 * <p>
+	 * This small buffer of commits is scanned to ensure we didn't miss anything
+	 * as a result of clock skew when the commits were made. We need to set our
+	 * constant to 1 additional commit due to the use of a pre-increment
+	 * operator when accessing the value.
+	 */
+	private static final int OVER_SCAN = 5 + 1;
+
+	/** A commit near the end of time, to initialize {@link #last} with. */
+	private static final RevCommit INIT_LAST;
+
+	static {
+		INIT_LAST = new RevCommit(ObjectId.zeroId());
+		INIT_LAST.commitTime = Integer.MAX_VALUE;
+	}
+
 	private final RevWalk walker;
 
 	private final DateRevQueue pending;
@@ -68,6 +87,17 @@
 
 	private final int output;
 
+	/** Last commit produced to the caller from {@link #next()}. */
+	private RevCommit last = INIT_LAST;
+
+	/**
+	 * Number of commits we have remaining in our over-scan allotment.
+	 * <p>
+	 * Only relevant if there are {@link #UNINTERESTING} commits in the
+	 * {@link #pending} queue.
+	 */
+	private int overScan = OVER_SCAN;
+
 	boolean canDispose;
 
 	PendingGenerator(final RevWalk w, final DateRevQueue p,
@@ -112,14 +142,27 @@ RevCommit next() throws MissingObjectException,
 				walker.carryFlagsImpl(c);
 
 				if ((c.flags & UNINTERESTING) != 0) {
-					if (pending.everbodyHasFlag(UNINTERESTING))
-						throw StopWalkException.INSTANCE;
-					c.dispose();
+					if (pending.everbodyHasFlag(UNINTERESTING)) {
+						final RevCommit n = pending.peek();
+						if (n != null && n.commitTime >= last.commitTime) {
+							// This is too close to call. The next commit we
+							// would pop is dated after the last one produced.
+							// We have to keep going to ensure that we carry
+							// flags as much as necessary.
+							//
+							overScan = OVER_SCAN;
+						} else if (--overScan == 0)
+							throw StopWalkException.INSTANCE;
+					} else {
+						overScan = OVER_SCAN;
+					}
+					if (canDispose)
+						c.dispose();
 					continue;
 				}
 
 				if (produce)
-					return c;
+					return last = c;
 				else if (canDispose)
 					c.dispose();
 			}
-- 
1.6.2.288.gc3f22

^ permalink raw reply related	[flat|nested] 13+ messages in thread

* [JGIT PATCH 6/5 v2] Add tests for RevWalk and its supporting code
  2009-03-14  0:13     ` Shawn O. Pearce
@ 2009-03-14  0:56       ` Shawn O. Pearce
  2009-03-15 11:34         ` Robin Rosenberg
  0 siblings, 1 reply; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-14  0:56 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

These new tests cover some of the common cases we see with using a
RevWalk, and increase our code coverage in this critical area of
the JGit library.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 "Shawn O. Pearce" <spearce@spearce.org> wrote:
 > I have yet to track down the full thing... but I know its busted.
 
 This updated test patch includes a test for the bug I was talking
 about, and fixed with 4/5 v2.

 .../org/spearce/jgit/revwalk/RevFlagSetTest.java   |  131 +++++++++++
 .../org/spearce/jgit/revwalk/RevWalkCullTest.java  |   96 ++++++++
 .../spearce/jgit/revwalk/RevWalkFilterTest.java    |  233 ++++++++++++++++++++
 .../spearce/jgit/revwalk/RevWalkMergeBaseTest.java |  117 ++++++++++
 .../org/spearce/jgit/revwalk/RevWalkSortTest.java  |  164 ++++++++++++++
 .../org/spearce/jgit/revwalk/RevWalkTestCase.java  |  102 +++++++++
 6 files changed, 843 insertions(+), 0 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java
new file mode 100644
index 0000000..76f3cbb
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevFlagSetTest.java
@@ -0,0 +1,131 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import java.util.Arrays;
+import java.util.Iterator;
+
+public class RevFlagSetTest extends RevWalkTestCase {
+	public void testEmpty() {
+		final RevFlagSet set = new RevFlagSet();
+		assertEquals(0, set.mask);
+		assertEquals(0, set.size());
+		assertNotNull(set.iterator());
+		assertFalse(set.iterator().hasNext());
+	}
+
+	public void testAddOne() {
+		final String flagName = "flag";
+		final RevFlag flag = rw.newFlag(flagName);
+		assertTrue(0 != flag.mask);
+		assertSame(flagName, flag.name);
+
+		final RevFlagSet set = new RevFlagSet();
+		assertTrue(set.add(flag));
+		assertFalse(set.add(flag));
+		assertEquals(flag.mask, set.mask);
+		assertEquals(1, set.size());
+		final Iterator<RevFlag> i = set.iterator();
+		assertTrue(i.hasNext());
+		assertSame(flag, i.next());
+		assertFalse(i.hasNext());
+	}
+
+	public void testAddTwo() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		assertTrue((flag1.mask & flag2.mask) == 0);
+
+		final RevFlagSet set = new RevFlagSet();
+		assertTrue(set.add(flag1));
+		assertTrue(set.add(flag2));
+		assertEquals(flag1.mask | flag2.mask, set.mask);
+		assertEquals(2, set.size());
+	}
+
+	public void testContainsAll() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		final RevFlagSet set1 = new RevFlagSet();
+		assertTrue(set1.add(flag1));
+		assertTrue(set1.add(flag2));
+
+		assertTrue(set1.containsAll(set1));
+		assertTrue(set1.containsAll(Arrays
+				.asList(new RevFlag[] { flag1, flag2 })));
+
+		final RevFlagSet set2 = new RevFlagSet();
+		set2.add(rw.newFlag("flag_3"));
+		assertFalse(set1.containsAll(set2));
+	}
+
+	public void testEquals() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		final RevFlagSet set = new RevFlagSet();
+		assertTrue(set.add(flag1));
+		assertTrue(set.add(flag2));
+
+		assertTrue(new RevFlagSet(set).equals(set));
+		assertTrue(new RevFlagSet(Arrays.asList(new RevFlag[] { flag1, flag2 }))
+				.equals(set));
+	}
+
+	public void testRemove() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		final RevFlagSet set = new RevFlagSet();
+		assertTrue(set.add(flag1));
+		assertTrue(set.add(flag2));
+
+		assertTrue(set.remove(flag1));
+		assertFalse(set.remove(flag1));
+		assertEquals(flag2.mask, set.mask);
+		assertFalse(set.contains(flag1));
+	}
+
+	public void testContains() {
+		final RevFlag flag1 = rw.newFlag("flag_1");
+		final RevFlag flag2 = rw.newFlag("flag_2");
+		final RevFlagSet set = new RevFlagSet();
+		set.add(flag1);
+		assertTrue(set.contains(flag1));
+		assertFalse(set.contains(flag2));
+		assertFalse(set.contains("bob"));
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java
new file mode 100644
index 0000000..93bd645
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkCullTest.java
@@ -0,0 +1,96 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import org.spearce.jgit.lib.ObjectId;
+
+public class RevWalkCullTest extends RevWalkTestCase {
+	public void testProperlyCullAllAncestors1() throws Exception {
+		// Credit goes to Junio C Hamano <gitster@pobox.com> for this
+		// test case in git-core (t/t6009-rev-list-parent.sh)
+		//
+		// We induce a clock skew so two is dated before one.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(-2400, a);
+		final ObjectId c = commit(b);
+		final ObjectId d = commit(c);
+
+		markStart(a);
+		markUninteresting(d);
+		assertNull(rw.next());
+	}
+
+	public void testProperlyCullAllAncestors2() throws Exception {
+		// Despite clock skew on c1 being very old it should not
+		// produce, neither should a or b, or any part of that chain.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(-5, b);
+		final ObjectId c2 = commit(10, b);
+		final ObjectId d = commit(c1, c2);
+
+		markStart(d);
+		markUninteresting(c1);
+		assertCommit(d, rw.next());
+		assertCommit(c2, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testProperlyCullAllAncestors_LongHistory() throws Exception {
+		final ObjectId a = commit();
+		ObjectId b = commit(a);
+		for (int i = 0; i < 24; i++) {
+			b = commit(b);
+			if ((i & 2) == 0)
+				markUninteresting(b);
+		}
+		final ObjectId c = commit(b);
+
+		markStart(c);
+		markUninteresting(b);
+		assertCommit(c, rw.next());
+		assertNull(rw.next());
+
+		// We should have aborted before we got back so far that "a"
+		// would be parsed. Thus, its parents shouldn't be allocated.
+		//
+		assertNull(rw.lookupCommit(a).parents);
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java
new file mode 100644
index 0000000..cf2975d
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkFilterTest.java
@@ -0,0 +1,233 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import java.io.IOException;
+
+import org.spearce.jgit.errors.IncorrectObjectTypeException;
+import org.spearce.jgit.errors.MissingObjectException;
+import org.spearce.jgit.errors.StopWalkException;
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.revwalk.filter.AndRevFilter;
+import org.spearce.jgit.revwalk.filter.NotRevFilter;
+import org.spearce.jgit.revwalk.filter.OrRevFilter;
+import org.spearce.jgit.revwalk.filter.RevFilter;
+
+public class RevWalkFilterTest extends RevWalkTestCase {
+	private static final MyAll MY_ALL = new MyAll();
+
+	public void testFilter_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(RevFilter.ALL);
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_Negate_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(RevFilter.ALL.negate());
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NOT_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(NotRevFilter.create(RevFilter.ALL));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(RevFilter.NONE);
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NOT_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(NotRevFilter.create(RevFilter.NONE));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_ALL_And_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(AndRevFilter.create(RevFilter.ALL, RevFilter.NONE));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE_And_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(AndRevFilter.create(RevFilter.NONE, RevFilter.ALL));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_ALL_Or_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(OrRevFilter.create(RevFilter.ALL, RevFilter.NONE));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE_Or_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(OrRevFilter.create(RevFilter.NONE, RevFilter.ALL));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_MY_ALL_And_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(AndRevFilter.create(MY_ALL, RevFilter.NONE));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE_And_MY_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(AndRevFilter.create(RevFilter.NONE, MY_ALL));
+		markStart(c);
+		assertNull(rw.next());
+	}
+
+	public void testFilter_MY_ALL_Or_NONE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(OrRevFilter.create(MY_ALL, RevFilter.NONE));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NONE_Or_MY_ALL() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+
+		rw.setRevFilter(OrRevFilter.create(RevFilter.NONE, MY_ALL));
+		markStart(c);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testFilter_NO_MERGES() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(b);
+		final ObjectId c2 = commit(b);
+		final ObjectId d = commit(c1, c2);
+		final ObjectId e = commit(d);
+
+		rw.setRevFilter(RevFilter.NO_MERGES);
+		markStart(e);
+		assertCommit(e, rw.next());
+		assertCommit(c2, rw.next());
+		assertCommit(c1, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	private static class MyAll extends RevFilter {
+		@Override
+		public RevFilter clone() {
+			return this;
+		}
+
+		@Override
+		public boolean include(RevWalk walker, RevCommit cmit)
+				throws StopWalkException, MissingObjectException,
+				IncorrectObjectTypeException, IOException {
+			return true;
+		}
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java
new file mode 100644
index 0000000..b05e774
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkMergeBaseTest.java
@@ -0,0 +1,117 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.revwalk.filter.RevFilter;
+
+public class RevWalkMergeBaseTest extends RevWalkTestCase {
+	public void testNone() throws Exception {
+		final ObjectId c1 = commit(commit(commit()));
+		final ObjectId c2 = commit(commit(commit()));
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(c1);
+		markStart(c2);
+		assertNull(rw.next());
+	}
+
+	public void testSimple() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(commit(commit(commit(commit(b)))));
+		final ObjectId c2 = commit(commit(commit(commit(commit(b)))));
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(c1);
+		markStart(c2);
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testMultipleHeads_SameBase1() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(commit(commit(commit(commit(b)))));
+		final ObjectId c2 = commit(commit(commit(commit(commit(b)))));
+		final ObjectId c3 = commit(commit(commit(b)));
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(c1);
+		markStart(c2);
+		markStart(c3);
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testMultipleHeads_SameBase2() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+		final ObjectId d1 = commit(commit(commit(commit(commit(b)))));
+		final ObjectId d2 = commit(commit(commit(commit(commit(c)))));
+		final ObjectId d3 = commit(commit(commit(c)));
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(d1);
+		markStart(d2);
+		markStart(d3);
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testCrissCross() throws Exception {
+		// See http://marc.info/?l=git&m=111463358500362&w=2 for a nice
+		// description of what this test is creating. We don't have a
+		// clean merge base for d,e as they each merged the parents b,c
+		// in different orders.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(a);
+		final ObjectId d = commit(b, c);
+		final ObjectId e = commit(c, b);
+
+		rw.setRevFilter(RevFilter.MERGE_BASE);
+		markStart(d);
+		markStart(e);
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertNull(rw.next());
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java
new file mode 100644
index 0000000..6f2eedc
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkSortTest.java
@@ -0,0 +1,164 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import org.spearce.jgit.lib.ObjectId;
+
+public class RevWalkSortTest extends RevWalkTestCase {
+	public void testSort_Default() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(1, a);
+		final ObjectId c = commit(1, b);
+		final ObjectId d = commit(1, c);
+
+		markStart(d);
+		assertCommit(d, rw.next());
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_COMMIT_TIME_DESC() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+		final ObjectId d = commit(c);
+
+		rw.sort(RevSort.COMMIT_TIME_DESC);
+		markStart(d);
+		assertCommit(d, rw.next());
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_REVERSE() throws Exception {
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(b);
+		final ObjectId d = commit(c);
+
+		rw.sort(RevSort.REVERSE);
+		markStart(d);
+		assertCommit(a, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(c, rw.next());
+		assertCommit(d, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_COMMIT_TIME_DESC_OutOfOrder1() throws Exception {
+		// Despite being out of order time-wise, a strand-of-pearls must
+		// still maintain topological order.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c = commit(-5, b);
+		final ObjectId d = commit(10, c);
+		assertTrue(parse(a).getCommitTime() < parse(d).getCommitTime());
+		assertTrue(parse(c).getCommitTime() < parse(b).getCommitTime());
+
+		rw.sort(RevSort.COMMIT_TIME_DESC);
+		markStart(d);
+		assertCommit(d, rw.next());
+		assertCommit(c, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_COMMIT_TIME_DESC_OutOfOrder2() throws Exception {
+		// c1 is back dated before its parent.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(-5, b);
+		final ObjectId c2 = commit(10, b);
+		final ObjectId d = commit(c1, c2);
+
+		rw.sort(RevSort.COMMIT_TIME_DESC);
+		markStart(d);
+		assertCommit(d, rw.next());
+		assertCommit(c2, rw.next());
+		assertCommit(b, rw.next());
+		assertCommit(a, rw.next());
+		assertCommit(c1, rw.next());
+		assertNull(rw.next());
+	}
+
+	public void testSort_TOPO() throws Exception {
+		// c1 is back dated before its parent.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(-5, b);
+		final ObjectId c2 = commit(10, b);
+		final ObjectId d = commit(c1, 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());
+	}
+
+	public void testSort_TOPO_REVERSE() throws Exception {
+		// c1 is back dated before its parent.
+		//
+		final ObjectId a = commit();
+		final ObjectId b = commit(a);
+		final ObjectId c1 = commit(-5, b);
+		final ObjectId c2 = commit(10, b);
+		final ObjectId d = commit(c1, c2);
+
+		rw.sort(RevSort.TOPO);
+		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());
+	}
+}
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java
new file mode 100644
index 0000000..bd696dd
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/revwalk/RevWalkTestCase.java
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.revwalk;
+
+import java.util.Date;
+
+import org.spearce.jgit.lib.Commit;
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.ObjectWriter;
+import org.spearce.jgit.lib.PersonIdent;
+import org.spearce.jgit.lib.RepositoryTestCase;
+import org.spearce.jgit.lib.Tree;
+
+/** Support for tests of the {@link RevWalk} class. */
+public abstract class RevWalkTestCase extends RepositoryTestCase {
+	protected ObjectWriter ow;
+
+	protected ObjectId emptyTree;
+
+	protected long nowTick;
+
+	protected RevWalk rw;
+
+	public void setUp() throws Exception {
+		super.setUp();
+		ow = new ObjectWriter(db);
+		emptyTree = ow.writeTree(new Tree(db));
+		nowTick = 1236977987000L;
+		rw = new RevWalk(db);
+	}
+
+	protected void tick(final int secDelta) {
+		nowTick += secDelta * 1000L;
+	}
+
+	protected ObjectId commit(final ObjectId... parents) throws Exception {
+		return commit(1, parents);
+	}
+
+	protected ObjectId commit(final int secDelta, final ObjectId... parents)
+			throws Exception {
+		tick(secDelta);
+		final Commit c = new Commit(db);
+		c.setTreeId(emptyTree);
+		c.setParentIds(parents);
+		c.setAuthor(new PersonIdent(jauthor, new Date(nowTick)));
+		c.setCommitter(new PersonIdent(jcommitter, new Date(nowTick)));
+		c.setMessage("");
+		return ow.writeCommit(c);
+	}
+
+	protected RevCommit parse(final ObjectId commitId) throws Exception {
+		return rw.parseCommit(commitId);
+	}
+
+	protected void markStart(final ObjectId commitId) throws Exception {
+		rw.markStart(parse(commitId));
+	}
+
+	protected void markUninteresting(final ObjectId commitId) throws Exception {
+		rw.markUninteresting(parse(commitId));
+	}
+
+	protected void assertCommit(final ObjectId commitId, final RevCommit commit) {
+		assertEquals(commitId.name(), commit != null ? commit.name() : null);
+	}
+}
-- 
1.6.2.288.gc3f22

^ permalink raw reply related	[flat|nested] 13+ messages in thread

* Re: [JGIT PATCH 6/5 v2] Add tests for RevWalk and its supporting code
  2009-03-14  0:56       ` [JGIT PATCH 6/5 v2] " Shawn O. Pearce
@ 2009-03-15 11:34         ` Robin Rosenberg
  2009-03-16 14:33           ` Shawn O. Pearce
  0 siblings, 1 reply; 13+ messages in thread
From: Robin Rosenberg @ 2009-03-15 11:34 UTC (permalink / raw)
  To: Shawn O. Pearce; +Cc: git


A few /09 interesting/ places in StartGenerator are not covered by the tests.

		if (q instanceof DateRevQueue)
			pending = (DateRevQueue)q;
		else
-->			pending = new DateRevQueue(q);

and

		if (tf != TreeFilter.ALL) {
-->			rf = AndRevFilter.create(rf, new RewriteTreeFilter(w, tf));
-->			pendingOutputType |= HAS_REWRITE | NEEDS_REWRITE;
		}

PendingGenerator
						if (n != null && n.commitTime >= last.commitTime) {
							// This is too close to call. The next commit we
							// would pop is dated after the last one produced.
							// We have to keep going to ensure that we carry
							// flags as much as necessary.
							//
-->							overScan = OVER_SCAN;


I'll merge it anyway since this is still a huge improvement compared to the previous
state.

-- robin

^ permalink raw reply	[flat|nested] 13+ messages in thread

* Re: [JGIT PATCH 6/5 v2] Add tests for RevWalk and its supporting code
  2009-03-15 11:34         ` Robin Rosenberg
@ 2009-03-16 14:33           ` Shawn O. Pearce
  0 siblings, 0 replies; 13+ messages in thread
From: Shawn O. Pearce @ 2009-03-16 14:33 UTC (permalink / raw)
  To: Robin Rosenberg; +Cc: git

Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
> 
> A few /09 interesting/ places in StartGenerator are not covered by the tests.
> 
> 		if (q instanceof DateRevQueue)
> 			pending = (DateRevQueue)q;
> 		else
> -->			pending = new DateRevQueue(q);

This one is difficult to test.  Near as I can tell from the code
in the revwalk package, it never happens.  But if we did get here
with a non date rev queue, DateRevQueue()'s constructor can copy
the data from q over to one with no risk.

Perhaps just test this constructor in isolation?

> and
> 
> 		if (tf != TreeFilter.ALL) {
> -->			rf = AndRevFilter.create(rf, new RewriteTreeFilter(w, tf));
> -->			pendingOutputType |= HAS_REWRITE | NEEDS_REWRITE;
> 		}

That says we have no tests on the path filter code.  Adding one is
likely to identify at least one bug.  Clearly we need additional
tests on the path filter sections.  And it isn't just for this one
little conditional; the entire RewriteTreeFilter and RewriteGenerator
are untested right now.

I can work on adding more test coverage here, but its not in the
critical path for me at day-job right now.  The other problems I
tried to address in this series were.  So its lower in my queue
so-to-speak.  But I'll see what I can do in the near future to
write additional tests for this area of the revwalk package.
 
> PendingGenerator
> 						if (n != null && n.commitTime >= last.commitTime) {
> 							// This is too close to call. The next commit we
> 							// would pop is dated after the last one produced.
> 							// We have to keep going to ensure that we carry
> 							// flags as much as necessary.
> 							//
> -->							overScan = OVER_SCAN;

*sigh*  We never get here in the test suite? I missed that.  I'll try to
work out a test case today and send an additional patch to get coverage
here.  I thought RevWalkCullTest testProperlyCullAllAncestors1() would
be hitting here.  It doesn't.
 
> I'll merge it anyway since this is still a huge improvement compared to the previous
> state.

Thanks.

A co-worker and I are also currently trying to track down a deadlock
between C git-fetch and JGit upload-pack.  Both get stuck waiting
for the other to answer.  Clearly its JGit's fault.

-- 
Shawn.

^ permalink raw reply	[flat|nested] 13+ messages in thread

end of thread, other threads:[~2009-03-16 14:35 UTC | newest]

Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2009-03-13  2:07 [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Shawn O. Pearce
2009-03-13  2:07 ` [JGIT PATCH 1/5] Show critical flags in debug toString() descriptions of rev queues Shawn O. Pearce
2009-03-13  2:07   ` [JGIT PATCH 2/5] Make RevObject.getType implementations final Shawn O. Pearce
2009-03-13  2:07     ` [JGIT PATCH 3/5] Remove the horribly stupid RevSort.START_ORDER Shawn O. Pearce
2009-03-13  2:07       ` [JGIT PATCH 4/5] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce
2009-03-13  2:07         ` [JGIT PATCH 5/5] Avoid incorrect output of UNINTERESTING commits when clock skew occurs Shawn O. Pearce
2009-03-14  0:54         ` [JGIT PATCH 4/5 v2] Fix RevWalk with Linus Torvald's occasional bad commit date hack Shawn O. Pearce
2009-03-13 20:00 ` [JGIT PATCH 0/5] RevWalk fixes for UNINTERESTING Robin Rosenberg
2009-03-13 22:39   ` [JGIT PATCH 0/6] Add tests for RevWalk and its supporting code Shawn O. Pearce
2009-03-14  0:13     ` Shawn O. Pearce
2009-03-14  0:56       ` [JGIT PATCH 6/5 v2] " Shawn O. Pearce
2009-03-15 11:34         ` Robin Rosenberg
2009-03-16 14:33           ` Shawn O. Pearce

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.