RevWalk: Allow disabling parent rewriting

Previously, setting any TreeFilter on a RevWalk triggered parent
rewriting, which in the current StartGenerator implementation ends up
buffering the entire commit history in memory. Aside from causing poor
performance on large histories, this does not match the default
behavior of `git rev-list`, which does not rewrite parent SHAs unless
asked to via --parents/--children.

Add a new method setRewriteParents() to RevWalk to disable this
behavior. Continue rewriting parents by default to maintain backwards
compatibility.

Change-Id: I1f38e05526071c75ca58095e312663de5e6f334d

3 files changed, 124 insertions, 3 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkPathFilter1Test.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkPathFilter1Test.java
index d2083e6b5b..6ec529c319 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkPathFilter1Test.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkPathFilter1Test.java
@@ -129,6 +129,25 @@ public class RevWalkPathFilter1Test extends RevWalkTestCase {
 	}
 
 	@Test
+	public void testStringOfPearls_FilePath1_NoParentRewriting()
+			throws Exception {
+		final RevCommit a = commit(tree(file("d/f", blob("a"))));
+		final RevCommit b = commit(tree(file("d/f", blob("a"))), a);
+		final RevCommit c = commit(tree(file("d/f", blob("b"))), b);
+		filter("d/f");
+		markStart(c);
+		rw.setRewriteParents(false);
+
+		assertCommit(c, rw.next());
+		assertEquals(1, c.getParentCount());
+		assertCommit(b, c.getParent(0));
+
+		assertCommit(a, rw.next()); // b was skipped
+		assertEquals(0, a.getParentCount());
+		assertNull(rw.next());
+	}
+
+	@Test
 	public void testStringOfPearls_FilePath2() throws Exception {
 		final RevCommit a = commit(tree(file("d/f", blob("a"))));
 		final RevCommit b = commit(tree(file("d/f", blob("a"))), a);
@@ -148,6 +167,28 @@ public class RevWalkPathFilter1Test extends RevWalkTestCase {
 	}
 
 	@Test
+	public void testStringOfPearls_FilePath2_NoParentRewriting()
+	throws Exception {
+		final RevCommit a = commit(tree(file("d/f", blob("a"))));
+		final RevCommit b = commit(tree(file("d/f", blob("a"))), a);
+		final RevCommit c = commit(tree(file("d/f", blob("b"))), b);
+		final RevCommit d = commit(tree(file("d/f", blob("b"))), c);
+		filter("d/f");
+		markStart(d);
+		rw.setRewriteParents(false);
+
+		// d was skipped
+		assertCommit(c, rw.next());
+		assertEquals(1, c.getParentCount());
+		assertCommit(b, c.getParent(0));
+
+		// b was skipped
+		assertCommit(a, rw.next());
+		assertEquals(0, a.getParentCount());
+		assertNull(rw.next());
+	}
+
+	@Test
 	public void testStringOfPearls_DirPath2() throws Exception {
 		final RevCommit a = commit(tree(file("d/f", blob("a"))));
 		final RevCommit b = commit(tree(file("d/f", blob("a"))), a);
@@ -167,6 +208,28 @@ public class RevWalkPathFilter1Test extends RevWalkTestCase {
 	}
 
 	@Test
+	public void testStringOfPearls_DirPath2_NoParentRewriting()
+			throws Exception {
+		final RevCommit a = commit(tree(file("d/f", blob("a"))));
+		final RevCommit b = commit(tree(file("d/f", blob("a"))), a);
+		final RevCommit c = commit(tree(file("d/f", blob("b"))), b);
+		final RevCommit d = commit(tree(file("d/f", blob("b"))), c);
+		filter("d");
+		markStart(d);
+		rw.setRewriteParents(false);
+
+		// d was skipped
+		assertCommit(c, rw.next());
+		assertEquals(1, c.getParentCount());
+		assertCommit(b, c.getParent(0));
+
+		// b was skipped
+		assertCommit(a, rw.next());
+		assertEquals(0, a.getParentCount());
+		assertNull(rw.next());
+	}
+
+	@Test
 	public void testStringOfPearls_FilePath3() throws Exception {
 		final RevCommit a = commit(tree(file("d/f", blob("a"))));
 		final RevCommit b = commit(tree(file("d/f", blob("a"))), a);
@@ -192,4 +255,35 @@ public class RevWalkPathFilter1Test extends RevWalkTestCase {
 		assertEquals(0, a.getParentCount());
 		assertNull(rw.next());
 	}
+
+	@Test
+	public void testStringOfPearls_FilePath3_NoParentRewriting()
+			throws Exception {
+		final RevCommit a = commit(tree(file("d/f", blob("a"))));
+		final RevCommit b = commit(tree(file("d/f", blob("a"))), a);
+		final RevCommit c = commit(tree(file("d/f", blob("b"))), b);
+		final RevCommit d = commit(tree(file("d/f", blob("b"))), c);
+		final RevCommit e = commit(tree(file("d/f", blob("b"))), d);
+		final RevCommit f = commit(tree(file("d/f", blob("b"))), e);
+		final RevCommit g = commit(tree(file("d/f", blob("b"))), f);
+		final RevCommit h = commit(tree(file("d/f", blob("b"))), g);
+		final RevCommit i = commit(tree(file("d/f", blob("c"))), h);
+		filter("d/f");
+		markStart(i);
+		rw.setRewriteParents(false);
+
+		assertCommit(i, rw.next());
+		assertEquals(1, i.getParentCount());
+		assertCommit(h, i.getParent(0));
+
+		// h..d was skipped
+		assertCommit(c, rw.next());
+		assertEquals(1, c.getParentCount());
+		assertCommit(b, c.getParent(0));
+
+		// b was skipped
+		assertCommit(a, rw.next());
+		assertEquals(0, a.getParentCount());
+		assertNull(rw.next());
+	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
index b3c4cced74..79cc42d170 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -190,6 +190,8 @@ public class RevWalk implements Iterable<RevCommit> {
 
 	private boolean retainBody;
 
+	private boolean rewriteParents = true;
+
 	boolean shallowCommitsInitialized;
 
 	/**
@@ -533,8 +535,9 @@ public class RevWalk implements Iterable<RevCommit> {
 	 * will not be simplified.
 	 * <p>
 	 * If non-null and not {@link TreeFilter#ALL} then the tree filter will be
-	 * installed and commits will have their ancestry simplified to hide commits
-	 * that do not contain tree entries matched by the filter.
+	 * installed. Commits will have their ancestry simplified to hide commits that
+	 * do not contain tree entries matched by the filter, unless
+	 * {@code setRewriteParents(false)} is called.
 	 * <p>
 	 * Usually callers should be inserting a filter graph including
 	 * {@link TreeFilter#ANY_DIFF} along with one or more
@@ -551,6 +554,28 @@ public class RevWalk implements Iterable<RevCommit> {
 	}
 
 	/**
+	 * Set whether to rewrite parent pointers when filtering by modified paths.
+	 * <p>
+	 * By default, when {@link #setTreeFilter(TreeFilter)} is called with non-
+	 * null and non-{@link TreeFilter#ALL} filter, commits will have their
+	 * ancestry simplified and parents rewritten to hide commits that do not match
+	 * the filter.
+	 * <p>
+	 * This behavior can be bypassed by passing false to this method.
+	 *
+	 * @param rewrite
+	 *            whether to rewrite parents; defaults to true.
+	 * @since 3.4
+	 */
+	public void setRewriteParents(boolean rewrite) {
+		rewriteParents = rewrite;
+	}
+
+	boolean getRewriteParents() {
+		return rewriteParents;
+	}
+
+	/**
 	 * Should the body of a commit or tag be retained after parsing its headers?
 	 * <p>
 	 * Usually the body is always retained, but some application code might not
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
index 5b264fcf3d..9c4e53c979 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/StartGenerator.java
@@ -128,7 +128,9 @@ class StartGenerator extends Generator {
 			pending = new DateRevQueue(q);
 		if (tf != TreeFilter.ALL) {
 			rf = AndRevFilter.create(new RewriteTreeFilter(w, tf), rf);
-			pendingOutputType |= HAS_REWRITE | NEEDS_REWRITE;
+			pendingOutputType |= HAS_REWRITE;
+			if (w.getRewriteParents())
+				pendingOutputType |= NEEDS_REWRITE;
 		}
 
 		walker.queue = q;