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