UploadPack: support deepen-since in protocol v2

Support the deepen-since parameter when requested by a client using
protocol v2. This is done by:
 - adding a DepthWalk.RevWalk#setDeepenSince method
 - updating DepthGenerator to recognize when deepen-since is set
 - recording in DepthWalk.Commit whether a commit is a boundary commit

Existing users of DepthWalk such as UploadPack previously recognized
boundary commits by comparing their depths against the threshold, not
tracking whether any parents were truly excluded. This behavior is
preserved - UploadPack considers a commit as boundary if its depth is
equal to the threshold *or* a parent was excluded (whether by depth or
by deepen-since).

Change-Id: I852bba6b1279f9cc8aee38282e9339d62b8dcddc
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>

4 files changed, 130 insertions, 12 deletions

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 317ac32e6d..20fb12b3ef 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
@@ -27,6 +27,7 @@ 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.PersonIdent;
 import org.eclipse.jgit.lib.ProgressMonitor;
 import org.eclipse.jgit.lib.Ref;
 import org.eclipse.jgit.lib.Repository;
@@ -1191,6 +1192,59 @@ public class UploadPackTest {
 	}
 
 	@Test
+	public void testV2FetchShallowSince() throws Exception {
+		PersonIdent person = new PersonIdent(remote.getRepository());
+
+		RevCommit beyondBoundary = remote.commit()
+			.committer(new PersonIdent(person, 1510000000, 0)).create();
+		RevCommit boundary = remote.commit().parent(beyondBoundary)
+			.committer(new PersonIdent(person, 1520000000, 0)).create();
+		RevCommit tooOld = remote.commit()
+			.committer(new PersonIdent(person, 1500000000, 0)).create();
+		RevCommit merge = remote.commit().parent(boundary).parent(tooOld)
+			.committer(new PersonIdent(person, 1530000000, 0)).create();
+
+		remote.update("branch1", merge);
+
+		// Report that we only have "boundary" as a shallow boundary.
+		ByteArrayInputStream recvStream = uploadPackV2(
+			"command=fetch\n",
+			PacketLineIn.DELIM,
+			"shallow " + boundary.toObjectId().getName() + "\n",
+			"deepen-since 1510000\n",
+			"want " + merge.toObjectId().getName() + "\n",
+			"have " + boundary.toObjectId().getName() + "\n",
+			"done\n",
+			PacketLineIn.END);
+		PacketLineIn pckIn = new PacketLineIn(recvStream);
+		assertThat(pckIn.readString(), is("shallow-info"));
+
+		// "merge" is shallow because one of its parents is committed
+		// earlier than the given deepen-since time.
+		assertThat(pckIn.readString(), is("shallow " + merge.toObjectId().getName()));
+
+		// "boundary" is unshallow because its parent committed at or
+		// later than the given deepen-since time.
+		assertThat(pckIn.readString(), is("unshallow " + boundary.toObjectId().getName()));
+
+		assertThat(pckIn.readString(), theInstance(PacketLineIn.DELIM));
+		assertThat(pckIn.readString(), is("packfile"));
+		parsePack(recvStream);
+
+		// The server does not send this because it is committed
+		// earlier than the given deepen-since time.
+		assertFalse(client.hasObject(tooOld.toObjectId()));
+
+		// The server does not send this because the client claims to
+		// have it.
+		assertFalse(client.hasObject(boundary.toObjectId()));
+
+		// The server sends both these commits.
+		assertTrue(client.hasObject(beyondBoundary.toObjectId()));
+		assertTrue(client.hasObject(merge.toObjectId()));
+	}
+
+	@Test
 	public void testV2FetchUnrecognizedArgument() throws Exception {
 		thrown.expect(PackProtocolException.class);
 		thrown.expectMessage("unexpected invalid-argument");
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthGenerator.java
index 3e96f5a170..6c6cc95c2e 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthGenerator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthGenerator.java
@@ -59,6 +59,8 @@ class DepthGenerator extends Generator {
 
 	private final int depth;
 
+	private final int deepenSince;
+
 	private final RevWalk walk;
 
 	/**
@@ -91,6 +93,7 @@ class DepthGenerator extends Generator {
 		walk = (RevWalk)w;
 
 		this.depth = w.getDepth();
+		this.deepenSince = w.getDeepenSince();
 		this.UNSHALLOW = w.getUnshallowFlag();
 		this.REINTERESTING = w.getReinterestingFlag();
 
@@ -142,12 +145,24 @@ class DepthGenerator extends Generator {
 				// this depth is guaranteed to be the smallest value that
 				// any path could produce.
 				if (dp.depth == -1) {
+					boolean failsDeepenSince = false;
+					if (deepenSince != 0) {
+						if ((p.flags & RevWalk.PARSED) == 0) {
+							p.parseHeaders(walk);
+						}
+						failsDeepenSince =
+							p.getCommitTime() < deepenSince;
+					}
+
 					dp.depth = newDepth;
 
 					// If the parent is not too deep, add it to the queue
 					// so that we can produce it later
-					if (newDepth <= depth)
+					if (newDepth <= depth && !failsDeepenSince) {
 						pending.add(p);
+					} else {
+						c.isBoundary = true;
+					}
 				}
 
 				// If the current commit has become unshallowed, everything
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthWalk.java
index 06a5272b98..3499572d07 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/DepthWalk.java
@@ -63,6 +63,15 @@ public interface DepthWalk {
 	 */
 	public int getDepth();
 
+	/**
+	 * @return the deepen-since value; if not 0, this walk only returns commits
+	 *         whose commit time is at or after this limit
+	 * @since 5.2
+	 */
+	public default int getDeepenSince() {
+		return 0;
+	}
+
 	/** @return flag marking commits that should become unshallow. */
 	/**
 	 * Get flag marking commits that should become unshallow.
@@ -83,12 +92,23 @@ public interface DepthWalk {
 		/** Depth of this commit in the graph, via shortest path. */
 		int depth;
 
+		boolean isBoundary;
+
 		/** @return depth of this commit, as found by the shortest path. */
 		public int getDepth() {
 			return depth;
 		}
 
 		/**
+		 * @return true if at least one of this commit's children was excluded
+		 *         due to a depth or shallow-since restriction, false otherwise
+		 * @since 5.2
+		 */
+		public boolean isBoundary() {
+			return isBoundary;
+		}
+
+		/**
 		 * Initialize a new commit.
 		 *
 		 * @param id
@@ -104,6 +124,8 @@ public interface DepthWalk {
 	public class RevWalk extends org.eclipse.jgit.revwalk.RevWalk implements DepthWalk {
 		private final int depth;
 
+		private int deepenSince;
+
 		private final RevFlag UNSHALLOW;
 
 		private final RevFlag REINTERESTING;
@@ -159,6 +181,22 @@ public interface DepthWalk {
 		}
 
 		@Override
+		public int getDeepenSince() {
+			return deepenSince;
+		}
+
+		/**
+		 * Sets the deepen-since value.
+		 *
+		 * @param limit
+		 *            new deepen-since value
+		 * @since 5.2
+		 */
+		public void setDeepenSince(int limit) {
+			deepenSince = limit;
+		}
+
+		@Override
 		public RevFlag getUnshallowFlag() {
 			return UNSHALLOW;
 		}
@@ -174,6 +212,7 @@ public interface DepthWalk {
 		@Override
 		public ObjectWalk toObjectWalkWithSameObjects() {
 			ObjectWalk ow = new ObjectWalk(reader, depth);
+			ow.deepenSince = deepenSince;
 			ow.objects = objects;
 			ow.freeFlags = freeFlags;
 			return ow;
@@ -184,6 +223,8 @@ public interface DepthWalk {
 	public class ObjectWalk extends org.eclipse.jgit.revwalk.ObjectWalk implements DepthWalk {
 		private final int depth;
 
+		private int deepenSince;
+
 		private final RevFlag UNSHALLOW;
 
 		private final RevFlag REINTERESTING;
@@ -263,6 +304,11 @@ public interface DepthWalk {
 		}
 
 		@Override
+		public int getDeepenSince() {
+			return deepenSince;
+		}
+
+		@Override
 		public RevFlag getUnshallowFlag() {
 			return UNSHALLOW;
 		}
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 428b6edfe5..213bfe504b 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
@@ -841,7 +841,7 @@ public class UploadPack {
 
 			if (!clientShallowCommits.isEmpty())
 				verifyClientShallow(clientShallowCommits);
-			if (depth != 0) {
+			if (depth != 0 || shallowSince != 0) {
 				computeShallowsAndUnshallows(wantIds, shallow -> {
 					pckOut.writeString("shallow " + shallow.name() + '\n'); //$NON-NLS-1$
 				}, unshallow -> {
@@ -1143,17 +1143,18 @@ public class UploadPack {
 			IOConsumer<ObjectId> shallowFunc,
 			IOConsumer<ObjectId> unshallowFunc)
 			throws IOException {
-		if (options.contains(OPTION_DEEPEN_RELATIVE) || shallowSince != 0
-				|| !deepenNotRefs.isEmpty()) {
-			// TODO(jonathantanmy): Implement deepen-relative, deepen-since,
+		if (options.contains(OPTION_DEEPEN_RELATIVE) || !deepenNotRefs.isEmpty()) {
+			// TODO(jonathantanmy): Implement deepen-relative
 			// and deepen-not.
 			throw new UnsupportedOperationException();
 		}
 
-		int walkDepth = depth - 1;
+		int walkDepth = depth == 0 ? Integer.MAX_VALUE : depth - 1;
 		try (DepthWalk.RevWalk depthWalk = new DepthWalk.RevWalk(
 				walk.getObjectReader(), walkDepth)) {
 
+			depthWalk.setDeepenSince(shallowSince);
+
 			// Find all the commits which will be shallow
 			for (ObjectId o : wants) {
 				try {
@@ -1167,17 +1168,17 @@ public class UploadPack {
 			while ((o = depthWalk.next()) != null) {
 				DepthWalk.Commit c = (DepthWalk.Commit) o;
 
+				boolean isBoundary = (c.getDepth() == walkDepth) || c.isBoundary();
+
 				// Commits at the boundary which aren't already shallow in
 				// the client need to be marked as such
-				if (c.getDepth() == walkDepth
-						&& !clientShallowCommits.contains(c)) {
+				if (isBoundary && !clientShallowCommits.contains(c)) {
 					shallowFunc.accept(c.copy());
 				}
 
 				// Commits not on the boundary which are shallow in the client
 				// need to become unshallowed
-				if (c.getDepth() < walkDepth
-						&& clientShallowCommits.remove(c)) {
+				if (!isBoundary && clientShallowCommits.remove(c)) {
 					unshallowFunc.accept(c.copy());
 				}
 			}
@@ -1987,9 +1988,11 @@ public class UploadPack {
 			}
 
 			RevWalk rw = walk;
-			if (depth > 0) {
+			if (depth > 0 || shallowSince != 0) {
+				int walkDepth = depth == 0 ? Integer.MAX_VALUE : depth - 1;
 				pw.setShallowPack(depth, unshallowCommits);
-				rw = new DepthWalk.RevWalk(walk.getObjectReader(), depth - 1);
+				rw = new DepthWalk.RevWalk(walk.getObjectReader(), walkDepth);
+				((DepthWalk.RevWalk) rw).setDeepenSince(shallowSince);
 				rw.assumeShallow(clientShallowCommits);
 			}