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>

4 files changed, 207 insertions, 37 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java
index 70df8c08e2..c86afb08c3 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriter.java
@@ -873,6 +873,21 @@ public class PackWriter implements AutoCloseable {
 	}
 
 	/**
+	 * A visitation policy which causes objects to be visited repeatedly by
+	 * making {@code shouldVisit} always return {@code true}.
+	 */
+	private static final ObjectWalk.VisitationPolicy ALWAYS_VISIT_POLICY =
+			new ObjectWalk.VisitationPolicy() {
+		@Override
+		public boolean shouldVisit(RevObject o) {
+			return true;
+		}
+
+		@Override
+		public void visited(RevObject o) {}
+	};
+
+	/**
 	 * Prepare the list of objects to be written to the pack stream.
 	 * <p>
 	 * Basing on these 2 sets, another set of objects to put in a pack file is
@@ -913,6 +928,9 @@ public class PackWriter implements AutoCloseable {
 		if (shallowPack && !(walk instanceof DepthWalk.ObjectWalk))
 			throw new IllegalArgumentException(
 					JGitText.get().shallowPacksRequireDepthWalk);
+		if (filterSpec.getTreeDepthLimit() >= 0) {
+			walk.setVisitationPolicy(ALWAYS_VISIT_POLICY);
+		}
 		findObjectsToPack(countingMonitor, walk, interestingObjects,
 				uninterestingObjects, noBitmaps);
 	}
@@ -1972,7 +1990,9 @@ public class PackWriter implements AutoCloseable {
 				byte[] pathBuf = walker.getPathBuffer();
 				int pathLen = walker.getPathLength();
 				bases.addBase(o.getType(), pathBuf, pathLen, pathHash);
-				filterAndAddObject(o, o.getType(), pathHash, want);
+				if (!depthSkip(o, walker)) {
+					filterAndAddObject(o, o.getType(), pathHash, want);
+				}
 				countingMonitor.update(1);
 			}
 		} else {
@@ -1982,7 +2002,10 @@ public class PackWriter implements AutoCloseable {
 					continue;
 				if (exclude(o))
 					continue;
-				filterAndAddObject(o, o.getType(), walker.getPathHashCode(), want);
+				if (!depthSkip(o, walker)) {
+					filterAndAddObject(o, o.getType(), walker.getPathHashCode(),
+									   want);
+				}
 				countingMonitor.update(1);
 			}
 		}
@@ -2074,6 +2097,33 @@ public class PackWriter implements AutoCloseable {
 		objectsMap.add(otp);
 	}
 
+	/**
+	 * Determines if the object should be omitted from the pack as a result of
+	 * its depth (probably because of the tree:<depth> filter).
+	 *
+	 * @param obj
+	 *            the object to check whether it should be omitted.
+	 * @param walker
+	 *            the walker being used for traveresal.
+	 * @return whether the given object should be skipped.
+	 */
+	private boolean depthSkip(@NonNull RevObject obj, ObjectWalk walker) {
+		long treeDepth = walker.getTreeDepth();
+
+		// Check if this object needs to be rejected because it is a tree or
+		// blob that is too deep from the root tree.
+
+		// A blob is considered one level deeper than the tree that contains it.
+		if (obj.getType() == OBJ_BLOB) {
+			treeDepth++;
+		}
+
+		// TODO: Do not continue traversing the tree, since its children
+		// will also be too deep.
+		return filterSpec.getTreeDepthLimit() != -1 &&
+				treeDepth > filterSpec.getTreeDepthLimit();
+	}
+
 	// Adds the given object as an object to be packed, first performing
 	// filtering on blobs at or exceeding a given size.
 	private void filterAndAddObject(@NonNull AnyObjectId src, int type,
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java
index 8f0dd9beb2..3312b8aa81 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java
@@ -43,6 +43,7 @@
 
 package org.eclipse.jgit.revwalk;
 
+import static java.util.Objects.requireNonNull;
 import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
 import static org.eclipse.jgit.lib.Constants.OBJ_COMMIT;
 import static org.eclipse.jgit.lib.Constants.OBJ_TREE;
@@ -97,6 +98,55 @@ public class ObjectWalk extends RevWalk {
 	 */
 	private static final int IN_PENDING = RevWalk.REWRITE;
 
+	/**
+	 * When walking over a tree and blob graph, objects are usually marked as
+	 * seen as they are visited and this "seen" status is checked upon the next
+	 * visit. If they are already "seen" then they are not processed (returned
+	 * by {@link ObjectWalk#nextObject()}) again. However, this behavior can be
+	 * overridden by supplying a different implementation of this class.
+	 *
+	 * @since 5.4
+	 */
+	public interface VisitationPolicy {
+		/**
+		 * Whenever the rev or object walk reaches a Git object, if that object
+		 * already exists as a RevObject, this method is called to determine if
+		 * that object should be visited.
+		 *
+		 * @param o
+		 *            the object to check if it should be visited
+		 * @return true if the object should be visited
+		 */
+		boolean shouldVisit(RevObject o);
+
+		/**
+		 * Called when an object is visited.
+		 *
+		 * @param o
+		 *            the object that was visited
+		 */
+		void visited(RevObject o);
+	}
+
+	/**
+	 * The default visitation policy: causes all objects to be visited exactly
+	 * once.
+	 *
+	 * @since 5.4
+	 */
+	public static final VisitationPolicy SIMPLE_VISITATION_POLICY =
+			new VisitationPolicy() {
+		@Override
+		public boolean shouldVisit(RevObject o) {
+			return (o.flags & SEEN) == 0;
+		}
+
+		@Override
+		public void visited(RevObject o) {
+			o.flags |= SEEN;
+		}
+	};
+
 	private List<RevObject> rootObjects;
 
 	private BlockObjQueue pendingObjects;
@@ -113,6 +163,8 @@ public class ObjectWalk extends RevWalk {
 
 	private boolean boundary;
 
+	private VisitationPolicy visitationPolicy = SIMPLE_VISITATION_POLICY;
+
 	/**
 	 * Create a new revision and object walker for a given repository.
 	 *
@@ -299,6 +351,18 @@ public class ObjectWalk extends RevWalk {
 		objectFilter = newFilter != null ? newFilter : ObjectFilter.ALL;
 	}
 
+	/**
+	 * Sets the visitation policy to use during this walk.
+	 *
+	 * @param policy
+	 *            the {@code VisitationPolicy} to use
+	 * @since 5.4
+	 */
+	public void setVisitationPolicy(VisitationPolicy policy) {
+		assertNotStarted();
+		visitationPolicy = requireNonNull(policy);
+	}
+
 	/** {@inheritDoc} */
 	@Override
 	public RevCommit next() throws MissingObjectException,
@@ -357,24 +421,23 @@ public class ObjectWalk extends RevWalk {
 				}
 
 				RevObject obj = objects.get(idBuffer);
-				if (obj != null && (obj.flags & SEEN) != 0)
+				if (obj != null && !visitationPolicy.shouldVisit(obj))
 					continue;
 
 				int mode = parseMode(buf, startPtr, ptr, tv);
-				int flags;
 				switch (mode >>> TYPE_SHIFT) {
 				case TYPE_FILE:
 				case TYPE_SYMLINK:
 					if (obj == null) {
 						obj = new RevBlob(idBuffer);
-						obj.flags = SEEN;
+						visitationPolicy.visited(obj);
 						objects.add(obj);
 						return obj;
 					}
 					if (!(obj instanceof RevBlob))
 						throw new IncorrectObjectTypeException(obj, OBJ_BLOB);
-					obj.flags = flags = obj.flags | SEEN;
-					if ((flags & UNINTERESTING) == 0)
+					visitationPolicy.visited(obj);
+					if ((obj.flags & UNINTERESTING) == 0)
 						return obj;
 					if (boundary)
 						return obj;
@@ -383,14 +446,14 @@ public class ObjectWalk extends RevWalk {
 				case TYPE_TREE:
 					if (obj == null) {
 						obj = new RevTree(idBuffer);
-						obj.flags = SEEN;
+						visitationPolicy.visited(obj);
 						objects.add(obj);
 						return pushTree(obj);
 					}
 					if (!(obj instanceof RevTree))
 						throw new IncorrectObjectTypeException(obj, OBJ_TREE);
-					obj.flags = flags = obj.flags | SEEN;
-					if ((flags & UNINTERESTING) == 0)
+					visitationPolicy.visited(obj);
+					if ((obj.flags & UNINTERESTING) == 0)
 						return pushTree(obj);
 					if (boundary)
 						return pushTree(obj);
@@ -419,12 +482,11 @@ public class ObjectWalk extends RevWalk {
 			if (o == null) {
 				return null;
 			}
-			int flags = o.flags;
-			if ((flags & SEEN) != 0)
+			if (!visitationPolicy.shouldVisit(o)) {
 				continue;
-			flags |= SEEN;
-			o.flags = flags;
-			if ((flags & UNINTERESTING) == 0 | boundary) {
+			}
+			visitationPolicy.visited(o);
+			if ((o.flags & UNINTERESTING) == 0 | boundary) {
 				if (o instanceof RevTree) {
 					// The previous while loop should have exhausted the stack
 					// of trees.
@@ -576,6 +638,17 @@ public class ObjectWalk extends RevWalk {
 	}
 
 	/**
+	 * @return the current traversal depth from the root tree object
+	 * @since 5.4
+	 */
+	public int getTreeDepth() {
+		if (currVisit == null) {
+			return 0;
+		}
+		return currVisit.depth;
+	}
+
+	/**
 	 * Get the current object's path hash code.
 	 * <p>
 	 * This method computes a hash code on the fly for this path, the hash is
@@ -778,6 +851,11 @@ public class ObjectWalk extends RevWalk {
 		tv.buf = reader.open(obj, OBJ_TREE).getCachedBytes();
 		tv.parent = currVisit;
 		currVisit = tv;
+		if (tv.parent == null) {
+			tv.depth = 1;
+		} else {
+			tv.depth = tv.parent.depth + 1;
+		}
 
 		return obj;
 	}
@@ -809,5 +887,8 @@ public class ObjectWalk extends RevWalk {
 
 		/** Number of bytes in the path leading up to this tree. */
 		int pathLen;
+
+		/** Number of levels deep from the root tree. 0 for root tree. */
+		int depth;
 	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/FilterSpec.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/FilterSpec.java
index 7e77419dec..a663c9b470 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/FilterSpec.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/FilterSpec.java
@@ -59,13 +59,22 @@ public final class FilterSpec {
 
 	private final long blobLimit;
 
-	private FilterSpec(long blobLimit) {
+	private final long treeDepthLimit;
+
+	private FilterSpec(long blobLimit, long treeDepthLimit) {
 		this.blobLimit = blobLimit;
+		this.treeDepthLimit = treeDepthLimit;
 	}
 
 	/**
 	 * Process the content of "filter" line from the protocol. It has a shape
-	 * like "blob:none" or "blob:limit=N", with limit a positive number.
+	 * like:
+	 *
+	 * <ul>
+	 *   <li>"blob:none"
+	 *   <li>"blob:limit=N", with N &gt;= 0
+	 *   <li>"tree:DEPTH", with DEPTH &gt;= 0
+	 * </ul>
 	 *
 	 * @param filterLine
 	 *            the content of the "filter" line in the protocol
@@ -76,31 +85,37 @@ public final class FilterSpec {
 	 */
 	public static FilterSpec fromFilterLine(String filterLine)
 			throws PackProtocolException {
-		long blobLimit = -1;
-
 		if (filterLine.equals("blob:none")) { //$NON-NLS-1$
-			blobLimit = 0;
+			return FilterSpec.withBlobLimit(0);
 		} else if (filterLine.startsWith("blob:limit=")) { //$NON-NLS-1$
+			long blobLimit = -1;
 			try {
 				blobLimit = Long
 						.parseLong(filterLine.substring("blob:limit=".length())); //$NON-NLS-1$
 			} catch (NumberFormatException e) {
-				throw new PackProtocolException(MessageFormat
-						.format(JGitText.get().invalidFilter, filterLine));
+				// Do not change blobLimit so that we throw a
+				// PackProtocolException later.
+			}
+			if (blobLimit >= 0) {
+				return FilterSpec.withBlobLimit(blobLimit);
+			}
+		} else if (filterLine.startsWith("tree:")) { //$NON-NLS-1$
+			long treeDepthLimit = -1;
+			try {
+				treeDepthLimit = Long
+						.parseLong(filterLine.substring("tree:".length())); //$NON-NLS-1$
+			} catch (NumberFormatException e) {
+				// Do not change blobLimit so that we throw a
+				// PackProtocolException later.
+			}
+			if (treeDepthLimit >= 0) {
+				return FilterSpec.withTreeDepthLimit(treeDepthLimit);
 			}
-		}
-		/*
-		 * We must have (1) either "blob:none" or "blob:limit=" set (because we
-		 * only support blob size limits for now), and (2) if the latter, then
-		 * it must be nonnegative. Throw if (1) or (2) is not met.
-		 */
-		if (blobLimit < 0) {
-			throw new PackProtocolException(
-					MessageFormat.format(
-							JGitText.get().invalidFilter, filterLine));
 		}
 
-		return new FilterSpec(blobLimit);
+		// Did not match any known filter format.
+		throw new PackProtocolException(
+				MessageFormat.format(JGitText.get().invalidFilter, filterLine));
 	}
 
 	/**
@@ -113,13 +128,27 @@ public final class FilterSpec {
 			throw new IllegalArgumentException(
 					"blobLimit cannot be negative: " + blobLimit); //$NON-NLS-1$
 		}
-		return new FilterSpec(blobLimit);
+		return new FilterSpec(blobLimit, -1);
+	}
+
+	/**
+	 * @param treeDepthLimit
+	 *            the tree depth limit in a "tree:[depth]" filter line
+	 * @return a filter spec which filters blobs and trees beyond a certain tree
+	 *         depth
+	 */
+	static FilterSpec withTreeDepthLimit(long treeDepthLimit) {
+		if (treeDepthLimit < 0) {
+			throw new IllegalArgumentException(
+					"treeDepthLimit cannot be negative: " + treeDepthLimit); //$NON-NLS-1$
+		}
+		return new FilterSpec(-1, treeDepthLimit);
 	}
 
 	/**
 	 * A placeholder that indicates no filtering.
 	 */
-	public static final FilterSpec NO_FILTER = new FilterSpec(-1);
+	public static final FilterSpec NO_FILTER = new FilterSpec(-1, -1);
 
 	/**
 	 * @return -1 if this filter does not filter blobs based on size, or a
@@ -130,10 +159,19 @@ public final class FilterSpec {
 	}
 
 	/**
+	 * @return -1 if this filter does not filter blobs and trees based on depth,
+	 *         or a non-negative integer representing the max tree depth of
+	 *         blobs and trees to fetch
+	 */
+	public long getTreeDepthLimit() {
+		return treeDepthLimit;
+	}
+
+	/**
 	 * @return true if this filter doesn't filter out anything
 	 */
 	public boolean isNoOp() {
-		return blobLimit == -1;
+		return blobLimit == -1 && treeDepthLimit == -1;
 	}
 
 	/**
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
index fb50a533f4..27090f4383 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
@@ -2110,7 +2110,8 @@ public class UploadPack {
 			}
 			pw.setUseBitmaps(
 					req.getDepth() == 0
-							&& req.getClientShallowCommits().isEmpty());
+							&& req.getClientShallowCommits().isEmpty()
+							&& req.getFilterSpec().getTreeDepthLimit() == -1);
 			pw.setClientShallowCommits(req.getClientShallowCommits());
 			pw.setReuseDeltaCommits(true);
 			pw.setDeltaBaseAsOffset(