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
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 0a03fc3..9aea3b4b 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 @@
}
@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 009914b..56f881e 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.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 @@
}
@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 @@
}
@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 @@
}
@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 a78f4d2..e210acf 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 @@
}
}
+ @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 d96648e..5e2c350 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 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 095276f..9e2ae91 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 @@
}
@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 @@
}
@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;
}
