Add seekPastPrefix method to RefCursor

This method will be used by the follow-up change. This useful if we want
to go over all the changes after a specific ref.

For example, the new method allows us to create a follow-up that would
go over all the refs until we reach a specific ref (e.g refs/changes/),
and then we use seekPastPrefix(refs/changes/) to read the rest of the refs,
thus basically we return all refs except a specific prefix.

When seeking past a prefix, the previous condition that created the
RefCursor still applies. E.g, if the cursor was created by
seekRefsWithPrefix, we can skip some refs but we will not return refs
that are not starting with this prefix.

Signed-off-by: Gal Paikin <paiking@google.com>
Change-Id: I2c02e89c877fe90da8619cb8a4a9a0c865f238ef

5 files changed, 327 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
index 0a03fc3523..9aea3b4b25 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/MergedReftableTest.java
@@ -138,6 +138,118 @@ public class MergedReftableTest {
 	}
 
 	@Test
+	public void twoTableSeekPastWithRefCursor() throws IOException {
+		List<Ref> delta1 = Arrays.asList(
+				ref("refs/heads/apple", 1),
+				ref("refs/heads/master", 2));
+		List<Ref> delta2 = Arrays.asList(
+				ref("refs/heads/banana", 3),
+				ref("refs/heads/zzlast", 4));
+
+		MergedReftable mr = merge(write(delta1), write(delta2));
+		try (RefCursor rc = mr.seekRefsWithPrefix("")) {
+			assertTrue(rc.next());
+			assertEquals("refs/heads/apple", rc.getRef().getName());
+			assertEquals(id(1), rc.getRef().getObjectId());
+
+			rc.seekPastPrefix("refs/heads/banana/");
+
+			assertTrue(rc.next());
+			assertEquals("refs/heads/master", rc.getRef().getName());
+			assertEquals(id(2), rc.getRef().getObjectId());
+
+			assertTrue(rc.next());
+			assertEquals("refs/heads/zzlast", rc.getRef().getName());
+			assertEquals(id(4), rc.getRef().getObjectId());
+
+			assertEquals(1, rc.getRef().getUpdateIndex());
+		}
+	}
+
+	@Test
+	public void oneTableSeekPastWithRefCursor() throws IOException {
+		List<Ref> delta1 = Arrays.asList(
+				ref("refs/heads/apple", 1),
+				ref("refs/heads/master", 2));
+
+		MergedReftable mr = merge(write(delta1));
+		try (RefCursor rc = mr.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/heads/apple");
+
+			assertTrue(rc.next());
+			assertEquals("refs/heads/master", rc.getRef().getName());
+			assertEquals(id(2), rc.getRef().getObjectId());
+
+			assertEquals(1, rc.getRef().getUpdateIndex());
+		}
+	}
+
+	@Test
+	public void seekPastToNonExistentPrefixToTheMiddle() throws IOException {
+		List<Ref> delta1 = Arrays.asList(
+				ref("refs/heads/apple", 1),
+				ref("refs/heads/master", 2));
+		List<Ref> delta2 = Arrays.asList(
+				ref("refs/heads/banana", 3),
+				ref("refs/heads/zzlast", 4));
+
+		MergedReftable mr = merge(write(delta1), write(delta2));
+		try (RefCursor rc = mr.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/heads/x");
+
+			assertTrue(rc.next());
+			assertEquals("refs/heads/zzlast", rc.getRef().getName());
+			assertEquals(id(4), rc.getRef().getObjectId());
+
+			assertEquals(1, rc.getRef().getUpdateIndex());
+		}
+	}
+
+	@Test
+	public void seekPastToNonExistentPrefixToTheEnd() throws IOException {
+		List<Ref> delta1 = Arrays.asList(
+				ref("refs/heads/apple", 1),
+				ref("refs/heads/master", 2));
+		List<Ref> delta2 = Arrays.asList(
+				ref("refs/heads/banana", 3),
+				ref("refs/heads/zzlast", 4));
+
+		MergedReftable mr = merge(write(delta1), write(delta2));
+		try (RefCursor rc = mr.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/heads/zzz");
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
+	public void seekPastManyTimes() throws IOException {
+		List<Ref> delta1 = Arrays.asList(
+				ref("refs/heads/apple", 1),
+				ref("refs/heads/master", 2));
+		List<Ref> delta2 = Arrays.asList(
+				ref("refs/heads/banana", 3),
+				ref("refs/heads/zzlast", 4));
+
+		MergedReftable mr = merge(write(delta1), write(delta2));
+		try (RefCursor rc = mr.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/heads/apple");
+			rc.seekPastPrefix("refs/heads/banana");
+			rc.seekPastPrefix("refs/heads/master");
+			rc.seekPastPrefix("refs/heads/zzlast");
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
+	public void seekPastOnEmptyTable() throws IOException {
+		MergedReftable mr = merge(write(), write());
+		try (RefCursor rc = mr.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/");
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
 	public void twoTableById() throws IOException {
 		List<Ref> delta1 = Arrays.asList(
 				ref("refs/heads/apple", 1),
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
index 009914b35c..56f881ec53 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftable/ReftableTest.java
@@ -10,6 +10,7 @@
 
 package org.eclipse.jgit.internal.storage.reftable;
 
+import static java.nio.charset.StandardCharsets.UTF_8;
 import static org.eclipse.jgit.lib.Constants.HEAD;
 import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH;
 import static org.eclipse.jgit.lib.Constants.R_HEADS;
@@ -49,8 +50,16 @@ import org.hamcrest.Matchers;
 import org.junit.Test;
 
 public class ReftableTest {
+	private static final byte[] LAST_UTF8_CHAR = new byte[] {
+			(byte)0x10,
+			(byte)0xFF,
+			(byte)0xFF};
+
 	private static final String MASTER = "refs/heads/master";
 	private static final String NEXT = "refs/heads/next";
+	private static final String AFTER_NEXT = "refs/heads/nextnext";
+	private static final String LAST = "refs/heads/nextnextnext";
+	private static final String NOT_REF_HEADS = "refs/zzz/zzz";
 	private static final String V1_0 = "refs/tags/v1.0";
 
 	private Stats stats;
@@ -396,6 +405,135 @@ public class ReftableTest {
 	}
 
 	@Test
+	public void seekPastRefWithRefCursor() throws IOException {
+		Ref exp = ref(MASTER, 1);
+		Ref next = ref(NEXT, 2);
+		Ref afterNext = ref(AFTER_NEXT, 3);
+		Ref afterNextNext = ref(LAST, 4);
+		ReftableReader t = read(write(exp, next, afterNext, afterNextNext));
+		try (RefCursor rc = t.seekRefsWithPrefix("")) {
+			assertTrue(rc.next());
+			assertEquals(MASTER, rc.getRef().getName());
+
+			rc.seekPastPrefix("refs/heads/next/");
+
+			assertTrue(rc.next());
+			assertEquals(AFTER_NEXT, rc.getRef().getName());
+			assertTrue(rc.next());
+			assertEquals(LAST, rc.getRef().getName());
+
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
+	public void seekPastToNonExistentPrefixToTheMiddle() throws IOException {
+		Ref exp = ref(MASTER, 1);
+		Ref next = ref(NEXT, 2);
+		Ref afterNext = ref(AFTER_NEXT, 3);
+		Ref afterNextNext = ref(LAST, 4);
+		ReftableReader t = read(write(exp, next, afterNext, afterNextNext));
+		try (RefCursor rc = t.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/heads/master_non_existent");
+
+			assertTrue(rc.next());
+			assertEquals(NEXT, rc.getRef().getName());
+
+			assertTrue(rc.next());
+			assertEquals(AFTER_NEXT, rc.getRef().getName());
+
+			assertTrue(rc.next());
+			assertEquals(LAST, rc.getRef().getName());
+
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
+	public void seekPastToNonExistentPrefixToTheEnd() throws IOException {
+		Ref exp = ref(MASTER, 1);
+		Ref next = ref(NEXT, 2);
+		Ref afterNext = ref(AFTER_NEXT, 3);
+		Ref afterNextNext = ref(LAST, 4);
+		ReftableReader t = read(write(exp, next, afterNext, afterNextNext));
+		try (RefCursor rc = t.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/heads/nextnon_existent_end");
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
+	public void seekPastWithSeekRefsWithPrefix() throws IOException {
+		Ref exp = ref(MASTER, 1);
+		Ref next = ref(NEXT, 2);
+		Ref afterNext = ref(AFTER_NEXT, 3);
+		Ref afterNextNext = ref(LAST, 4);
+		Ref notRefsHeads = ref(NOT_REF_HEADS, 5);
+		ReftableReader t = read(write(exp, next, afterNext, afterNextNext, notRefsHeads));
+		try (RefCursor rc = t.seekRefsWithPrefix("refs/heads/")) {
+			rc.seekPastPrefix("refs/heads/next/");
+			assertTrue(rc.next());
+			assertEquals(AFTER_NEXT, rc.getRef().getName());
+			assertTrue(rc.next());
+			assertEquals(LAST, rc.getRef().getName());
+
+			// NOT_REF_HEADS is next, but it's omitted because of
+			// seekRefsWithPrefix("refs/heads/").
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
+	public void seekPastWithLotsOfRefs() throws IOException {
+		Ref[] refs = new Ref[500];
+		for (int i = 1; i <= 500; i++) {
+			refs[i - 1] = ref(String.format("refs/%d", i), i);
+		}
+		ReftableReader t = read(write(refs));
+		try (RefCursor rc = t.allRefs()) {
+			rc.seekPastPrefix("refs/3");
+			assertTrue(rc.next());
+			assertEquals("refs/4", rc.getRef().getName());
+			assertTrue(rc.next());
+			assertEquals("refs/40", rc.getRef().getName());
+
+			rc.seekPastPrefix("refs/8");
+			assertTrue(rc.next());
+			assertEquals("refs/9", rc.getRef().getName());
+			assertTrue(rc.next());
+			assertEquals("refs/90", rc.getRef().getName());
+			assertTrue(rc.next());
+			assertEquals("refs/91", rc.getRef().getName());
+		}
+	}
+
+	@Test
+	public void seekPastManyTimes() throws IOException {
+		Ref exp = ref(MASTER, 1);
+		Ref next = ref(NEXT, 2);
+		Ref afterNext = ref(AFTER_NEXT, 3);
+		Ref afterNextNext = ref(LAST, 4);
+		ReftableReader t = read(write(exp, next, afterNext, afterNextNext));
+
+		try (RefCursor rc = t.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/heads/master");
+			rc.seekPastPrefix("refs/heads/next");
+			rc.seekPastPrefix("refs/heads/nextnext");
+			rc.seekPastPrefix("refs/heads/nextnextnext");
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
+	public void seekPastOnEmptyTable() throws IOException {
+		ReftableReader t = read(write());
+		try (RefCursor rc = t.seekRefsWithPrefix("")) {
+			rc.seekPastPrefix("refs/");
+			assertFalse(rc.next());
+		}
+	}
+
+	@Test
 	public void indexScan() throws IOException {
 		List<Ref> refs = new ArrayList<>();
 		for (int i = 1; i <= 5670; i++) {
@@ -874,6 +1012,14 @@ public class ReftableTest {
 	}
 
 	@Test
+	public void byObjectIdSkipPastPrefix() throws IOException {
+		ReftableReader t = read(write());
+		try (RefCursor rc = t.byObjectId(id(2))) {
+			assertThrows(UnsupportedOperationException.class, () -> rc.seekPastPrefix("refs/heads/"));
+		}
+	}
+
+	@Test
 	public void unpeeledDoesNotWrite() {
 		try {
 			write(new ObjectIdRef.Unpeeled(PACKED, MASTER, id(1)));
@@ -884,6 +1030,18 @@ public class ReftableTest {
 	}
 
 	@Test
+	public void skipPastRefWithLastUTF8() throws IOException {
+		ReftableReader t = read(write(ref(String.format("refs/heads/%sbla", new String(LAST_UTF8_CHAR
+				, UTF_8)), 1)));
+
+		try (RefCursor rc = t.allRefs()) {
+			rc.seekPastPrefix("refs/heads/");
+			assertFalse(rc.next());
+		}
+	}
+
+
+	@Test
 	public void nameTooLongDoesNotWrite() throws IOException {
 		try {
 			ReftableConfig cfg = new ReftableConfig();
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/MergedReftable.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/MergedReftable.java
index a78f4d24da..e210acf058 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/MergedReftable.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/MergedReftable.java
@@ -11,6 +11,7 @@
 package org.eclipse.jgit.internal.storage.reftable;
 
 import java.io.IOException;
+import java.util.ArrayList;
 import java.util.List;
 import java.util.PriorityQueue;
 
@@ -215,6 +216,23 @@ public class MergedReftable extends Reftable {
 			}
 		}
 
+		@Override
+		public void seekPastPrefix(String prefixName) throws IOException {
+			List<RefQueueEntry> entriesToAdd = new ArrayList<>();
+			entriesToAdd.addAll(queue);
+			if (head != null) {
+				entriesToAdd.add(head);
+			}
+
+			head = null;
+			queue.clear();
+
+			for(RefQueueEntry entry : entriesToAdd){
+				entry.rc.seekPastPrefix(prefixName);
+				add(entry);
+			}
+		}
+
 		private RefQueueEntry poll() {
 			RefQueueEntry e = head;
 			if (e != null) {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java
index d96648eb50..5e2c350883 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java
@@ -29,6 +29,19 @@ public abstract class RefCursor implements AutoCloseable {
 	public abstract boolean next() throws IOException;
 
 	/**
+	 * Seeks forward to the first ref record lexicographically beyond
+	 * {@code prefixName} that doesn't start with {@code prefixName}. If there are
+	 * no more results, skipping some refs won't add new results. E.g if we create a
+	 * RefCursor that returns only results with a specific prefix, skipping that
+	 * prefix won't give results that are not part of the original prefix.
+	 *
+	 * @param prefixName prefix that should be skipped. All previous refs before it
+	 *                   will be skipped.
+	 * @throws java.io.IOException references cannot be read.
+	 */
+	public abstract void seekPastPrefix(String prefixName) throws IOException;
+
+	/**
 	 * Get reference at the current position.
 	 *
 	 * @return reference at the current position.
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java
index 095276f57b..9e2ae91608 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java
@@ -509,6 +509,21 @@ public class ReftableReader extends Reftable implements AutoCloseable {
 		}
 
 		@Override
+		public void seekPastPrefix(String prefixName) throws IOException {
+			initRefIndex();
+			byte[] key = prefixName.getBytes(UTF_8);
+			ByteBuffer byteBuffer = ByteBuffer.allocate(key.length + 1);
+			byteBuffer.put(key);
+			// Add the representation of the last byte lexicographically. Based on how UTF_8
+			// representation works, this byte will be bigger lexicographically than any
+			// UTF_8 character when translated into bytes, since 0xFF can never be a part of
+			// a UTF_8 string.
+			byteBuffer.put((byte) 0xFF);
+
+			block = seek(REF_BLOCK_TYPE, byteBuffer.array(), refIndex, 0, refEnd);
+		}
+
+		@Override
 		public Ref getRef() {
 			return ref;
 		}
@@ -682,6 +697,17 @@ public class ReftableReader extends Reftable implements AutoCloseable {
 		}
 
 		@Override
+		/**
+		 * The implementation here would not be efficient complexity-wise since it
+		 * expected that there are a small number of refs that match the same object id.
+		 * In such case it's better to not even use this method (as the caller might
+		 * expect it to be efficient).
+		 */
+		public void seekPastPrefix(String prefixName) throws IOException {
+		    throw new UnsupportedOperationException();
+		}
+
+		@Override
 		public Ref getRef() {
 			return ref;
 		}