Preliminary support for tree:<depth> filter

This is used when fetching, and in particular to populate a partial
clone or a virtual file system cache as the user navigates. With this,
a client can pre-fetch a few directories deeper than only the current
directory.

depth:0 will omit all trees, and is useful if you only want to fetch
the commits of a repository, or fetch just a single tree or blob object.
depth:1 will fetch only the root tree of all commits fetched. depth:2
will fetch the root tree and all blobs and tree objects directly
referenced from it. depth:3 gets one more level, and so on. depth:#
will not filter a blob or tree that is explicitly marked wanted.

Bitmaps are disabled when this filter is used.

This implementation is quite slow because it iterates over all omitted
objects rather than skipping them. This will be addressed in follow-up
commits.

Change-Id: Ic312fee22d60e32cfcad59da56980e90ae2cae6a
Signed-off-by: Matthew DeVore <matvore@gmail.com>

3 files changed, 215 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/ProtocolV0ParserTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/ProtocolV0ParserTest.java
index 017f98079c..28a9c03ecc 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/ProtocolV0ParserTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/ProtocolV0ParserTest.java
@@ -194,6 +194,7 @@ public class ProtocolV0ParserTest {
 				hasOnlyObjectIds("4624442d68ee402a94364191085b77137618633e",
 						"f900c8326a43303685c46b279b9f70411bff1a4b"));
 		assertEquals(13000, request.getFilterSpec().getBlobLimit());
+		assertEquals(-1, request.getFilterSpec().getTreeDepthLimit());
 	}
 
 }
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/ProtocolV2ParserTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/ProtocolV2ParserTest.java
index 36c39568ee..740d92ef4d 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/ProtocolV2ParserTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/ProtocolV2ParserTest.java
@@ -233,6 +233,7 @@ public class ProtocolV2ParserTest {
 				ConfigBuilder.start().allowFilter().done());
 		FetchV2Request request = parser.parseFetchRequest(pckIn);
 		assertEquals(0, request.getFilterSpec().getBlobLimit());
+		assertEquals(-1, request.getFilterSpec().getTreeDepthLimit());
 	}
 
 	@Test
@@ -244,6 +245,19 @@ public class ProtocolV2ParserTest {
 				ConfigBuilder.start().allowFilter().done());
 		FetchV2Request request = parser.parseFetchRequest(pckIn);
 		assertEquals(15, request.getFilterSpec().getBlobLimit());
+		assertEquals(-1, request.getFilterSpec().getTreeDepthLimit());
+	}
+
+	@Test
+	public void testFetchWithTreeDepthFilter() throws IOException {
+		PacketLineIn pckIn = formatAsPacketLine(PacketLineIn.DELIM,
+				"filter tree:3",
+				PacketLineIn.END);
+		ProtocolV2Parser parser = new ProtocolV2Parser(
+				ConfigBuilder.start().allowFilter().done());
+		FetchV2Request request = parser.parseFetchRequest(pckIn);
+		assertEquals(-1, request.getFilterSpec().getBlobLimit());
+		assertEquals(3, request.getFilterSpec().getTreeDepthLimit());
 	}
 
 	@Test
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/UploadPackTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/UploadPackTest.java
index 0dda4a599a..5a3f98235b 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/UploadPackTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/transport/UploadPackTest.java
@@ -16,11 +16,16 @@ import java.io.ByteArrayInputStream;
 import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.io.StringWriter;
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
 
+import org.eclipse.jgit.dircache.DirCache;
+import org.eclipse.jgit.dircache.DirCacheBuilder;
+import org.eclipse.jgit.dircache.DirCacheEntry;
 import org.eclipse.jgit.errors.PackProtocolException;
 import org.eclipse.jgit.errors.TransportException;
 import org.eclipse.jgit.internal.storage.dfs.DfsGarbageCollector;
@@ -28,6 +33,8 @@ import org.eclipse.jgit.internal.storage.dfs.DfsRepositoryDescription;
 import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository;
 import org.eclipse.jgit.junit.TestRepository;
 import org.eclipse.jgit.lib.NullProgressMonitor;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
 import org.eclipse.jgit.lib.PersonIdent;
 import org.eclipse.jgit.lib.ProgressMonitor;
 import org.eclipse.jgit.lib.Ref;
@@ -1551,6 +1558,199 @@ public class UploadPackTest {
 		assertTrue(client.getObjectDatabase().has(small.toObjectId()));
 	}
 
+	abstract class TreeBuilder {
+		abstract void addElements(DirCacheBuilder dcBuilder) throws Exception;
+
+		RevTree build() throws Exception {
+			DirCache dc = DirCache.newInCore();
+			DirCacheBuilder dcBuilder = dc.builder();
+			addElements(dcBuilder);
+			dcBuilder.finish();
+			ObjectId id;
+			try (ObjectInserter ins =
+					remote.getRepository().newObjectInserter()) {
+				id = dc.writeTree(ins);
+				ins.flush();
+			}
+			return remote.getRevWalk().parseTree(id);
+		}
+	}
+
+	class DeepTreePreparator {
+		RevBlob blobLowDepth = remote.blob("lo");
+		RevBlob blobHighDepth = remote.blob("hi");
+
+		RevTree subtree = remote.tree(remote.file("1", blobHighDepth));
+		RevTree rootTree = (new TreeBuilder() {
+				@Override
+				void addElements(DirCacheBuilder dcBuilder) throws Exception {
+					dcBuilder.add(remote.file("1", blobLowDepth));
+					dcBuilder.addTree(new byte[] {'2'}, DirCacheEntry.STAGE_0,
+							remote.getRevWalk().getObjectReader(), subtree);
+				}
+			}).build();
+		RevCommit commit = remote.commit(rootTree);
+
+		DeepTreePreparator() throws Exception {}
+	}
+
+	private void uploadV2WithTreeDepthFilter(
+			long depth, ObjectId... wants) throws Exception {
+		server.getConfig().setBoolean("uploadpack", null, "allowfilter", true);
+
+		List<String> input = new ArrayList();
+		input.add("command=fetch\n");
+		input.add(PacketLineIn.DELIM);
+		for (ObjectId want : wants) {
+			input.add("want " + want.getName() + "\n");
+		}
+		input.add("filter tree:" + depth + "\n");
+		input.add("done\n");
+		input.add(PacketLineIn.END);
+		ByteArrayInputStream recvStream =
+				uploadPackV2(RequestPolicy.ANY, /*refFilter=*/null,
+							 /*hook=*/null, input.toArray(new String[0]));
+		PacketLineIn pckIn = new PacketLineIn(recvStream);
+		assertThat(pckIn.readString(), is("packfile"));
+		parsePack(recvStream);
+	}
+
+	@Test
+	public void testV2FetchFilterTreeDepth0() throws Exception {
+		DeepTreePreparator preparator = new DeepTreePreparator();
+		remote.update("master", preparator.commit);
+
+		uploadV2WithTreeDepthFilter(0, preparator.commit.toObjectId());
+
+		assertFalse(client.getObjectDatabase()
+				.has(preparator.rootTree.toObjectId()));
+		assertFalse(client.getObjectDatabase()
+				.has(preparator.subtree.toObjectId()));
+		assertFalse(client.getObjectDatabase()
+				.has(preparator.blobLowDepth.toObjectId()));
+		assertFalse(client.getObjectDatabase()
+				.has(preparator.blobHighDepth.toObjectId()));
+	}
+
+	@Test
+	public void testV2FetchFilterTreeDepth1_serverHasBitmap() throws Exception {
+		DeepTreePreparator preparator = new DeepTreePreparator();
+		remote.update("master", preparator.commit);
+
+		// The bitmap should be ignored since we need to track the depth while
+		// traversing the trees.
+		generateBitmaps(server);
+
+		uploadV2WithTreeDepthFilter(1, preparator.commit.toObjectId());
+
+		assertTrue(client.getObjectDatabase()
+				.has(preparator.rootTree.toObjectId()));
+		assertFalse(client.getObjectDatabase()
+				.has(preparator.subtree.toObjectId()));
+		assertFalse(client.getObjectDatabase()
+				.has(preparator.blobLowDepth.toObjectId()));
+		assertFalse(client.getObjectDatabase()
+				.has(preparator.blobHighDepth.toObjectId()));
+	}
+
+	@Test
+	public void testV2FetchFilterTreeDepth2() throws Exception {
+		DeepTreePreparator preparator = new DeepTreePreparator();
+		remote.update("master", preparator.commit);
+
+		uploadV2WithTreeDepthFilter(2, preparator.commit.toObjectId());
+
+		assertTrue(client.getObjectDatabase()
+				.has(preparator.rootTree.toObjectId()));
+		assertTrue(client.getObjectDatabase()
+				.has(preparator.subtree.toObjectId()));
+		assertTrue(client.getObjectDatabase()
+				.has(preparator.blobLowDepth.toObjectId()));
+		assertFalse(client.getObjectDatabase()
+				.has(preparator.blobHighDepth.toObjectId()));
+	}
+
+	/**
+	 * Creates a commit with the following files:
+	 * <pre>
+	 * a/x/b/foo
+	 * x/b/foo
+	 * </pre>
+	 * which has an identical tree in two locations: once at / and once at /a
+	 */
+	class RepeatedSubtreePreparator {
+		RevBlob foo = remote.blob("foo");
+		RevTree subtree3 = remote.tree(remote.file("foo", foo));
+		RevTree subtree2 = (new TreeBuilder() {
+			@Override
+			void addElements(DirCacheBuilder dcBuilder) throws Exception {
+				dcBuilder.addTree(new byte[] {'b'}, DirCacheEntry.STAGE_0,
+						remote.getRevWalk().getObjectReader(), subtree3);
+			}
+		}).build();
+		RevTree subtree1 = (new TreeBuilder() {
+			@Override
+			void addElements(DirCacheBuilder dcBuilder) throws Exception {
+				dcBuilder.addTree(new byte[] {'x'}, DirCacheEntry.STAGE_0,
+						remote.getRevWalk().getObjectReader(), subtree2);
+			}
+		}).build();
+		RevTree rootTree = (new TreeBuilder() {
+			@Override
+			void addElements(DirCacheBuilder dcBuilder) throws Exception {
+				dcBuilder.addTree(new byte[] {'a'}, DirCacheEntry.STAGE_0,
+						remote.getRevWalk().getObjectReader(), subtree1);
+				dcBuilder.addTree(new byte[] {'x'}, DirCacheEntry.STAGE_0,
+						remote.getRevWalk().getObjectReader(), subtree2);
+			}
+		}).build();
+		RevCommit commit = remote.commit(rootTree);
+
+		RepeatedSubtreePreparator() throws Exception {}
+	}
+
+	@Test
+	public void testV2FetchFilterTreeDepth_iterateOverTreeAtTwoLevels()
+			throws Exception {
+		// Test tree:<depth> where a tree is iterated to twice - once where a
+		// subentry is too deep to be included, and again where the blob inside
+		// it is shallow enough to be included.
+		RepeatedSubtreePreparator preparator = new RepeatedSubtreePreparator();
+		remote.update("master", preparator.commit);
+
+		uploadV2WithTreeDepthFilter(4, preparator.commit.toObjectId());
+
+		assertTrue(client.getObjectDatabase()
+				.has(preparator.foo.toObjectId()));
+	}
+
+	@Test
+	public void testWantFilteredObject() throws Exception {
+		RepeatedSubtreePreparator preparator = new RepeatedSubtreePreparator();
+		remote.update("master", preparator.commit);
+
+		// Specify wanted blob objects that are deep enough to be filtered. We
+		// should still upload them.
+		uploadV2WithTreeDepthFilter(
+				3,
+				preparator.commit.toObjectId(),
+				preparator.foo.toObjectId());
+		assertTrue(client.getObjectDatabase()
+				.has(preparator.foo.toObjectId()));
+
+		client = newRepo("client");
+		// Specify a wanted tree object that is deep enough to be filtered. We
+		// should still upload it.
+		uploadV2WithTreeDepthFilter(
+				2,
+				preparator.commit.toObjectId(),
+				preparator.subtree3.toObjectId());
+		assertTrue(client.getObjectDatabase()
+				.has(preparator.foo.toObjectId()));
+		assertTrue(client.getObjectDatabase()
+				.has(preparator.subtree3.toObjectId()));
+	}
+
 	@Test
 	public void testV2FetchFilterWhenNotAllowed() throws Exception {
 		RevCommit commit = remote.commit().message("0").create();