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>

1 files changed, 94 insertions, 13 deletions

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;
 	}
 }