Merge changes I36d9b63e,I8c5db581,I2c02e89c

* changes:
  Compare getting all refs except specific refs with seek and with filter
  Add getsRefsByPrefixWithSkips (excluding prefixes) to ReftableDatabase
  Add seekPastPrefix method to RefCursor

5 files changed, 421 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/FileReftableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/FileReftableTest.java
index 33bacbe3e2..15c9109ca0 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/FileReftableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/FileReftableTest.java
@@ -28,14 +28,18 @@ import java.io.File;
 import java.io.IOException;
 import java.security.SecureRandom;
 import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
 import java.util.List;
 
+import java.util.Set;
 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.NullProgressMonitor;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.PersonIdent;
 import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.RefDatabase;
 import org.eclipse.jgit.lib.RefRename;
 import org.eclipse.jgit.lib.RefUpdate;
 import org.eclipse.jgit.lib.RefUpdate.Result;
@@ -579,6 +583,64 @@ public class FileReftableTest extends SampleDataRepositoryTestCase {
 		assertEquals(Ref.Storage.PACKED, b.getStorage());
 	}
 
+	@Test
+	public void testGetRefsExcludingPrefix() throws IOException {
+		Set<String> prefixes = new HashSet<>();
+		prefixes.add("refs/tags");
+		// HEAD + 12 refs/heads are present here.
+		List<Ref> refs =
+				db.getRefDatabase().getRefsByPrefixWithExclusions(RefDatabase.ALL, prefixes);
+		assertEquals(13, refs.size());
+		checkContainsRef(refs, db.exactRef("HEAD"));
+		checkContainsRef(refs, db.exactRef("refs/heads/a"));
+		for (Ref notInResult : db.getRefDatabase().getRefsByPrefix("refs/tags")) {
+			assertFalse(refs.contains(notInResult));
+		}
+	}
+
+	@Test
+	public void testGetRefsExcludingPrefixes() throws IOException {
+		Set<String> exclude = new HashSet<>();
+		exclude.add("refs/tags/");
+		exclude.add("refs/heads/");
+		List<Ref> refs = db.getRefDatabase().getRefsByPrefixWithExclusions(RefDatabase.ALL, exclude);
+		assertEquals(1, refs.size());
+		checkContainsRef(refs, db.exactRef("HEAD"));
+	}
+
+	@Test
+	public void testGetRefsExcludingNonExistingPrefixes() throws IOException {
+		Set<String> exclude = new HashSet<>();
+		exclude.add("refs/tags/");
+		exclude.add("refs/heads/");
+		exclude.add("refs/nonexistent/");
+		List<Ref> refs = db.getRefDatabase().getRefsByPrefixWithExclusions(RefDatabase.ALL, exclude);
+		assertEquals(1, refs.size());
+		checkContainsRef(refs, db.exactRef("HEAD"));
+	}
+
+	@Test
+	public void testGetRefsWithPrefixExcludingPrefixes() throws IOException {
+		Set<String> exclude = new HashSet<>();
+		exclude.add("refs/heads/pa");
+		String include = "refs/heads/p";
+		List<Ref> refs = db.getRefDatabase().getRefsByPrefixWithExclusions(include, exclude);
+		assertEquals(1, refs.size());
+		checkContainsRef(refs, db.exactRef("refs/heads/prefix/a"));
+	}
+
+	@Test
+	public void testGetRefsWithPrefixExcludingOverlappingPrefixes() throws IOException {
+		Set<String> exclude = new HashSet<>();
+		exclude.add("refs/heads/pa");
+		exclude.add("refs/heads/");
+		exclude.add("refs/heads/p");
+		exclude.add("refs/tags/");
+		List<Ref> refs = db.getRefDatabase().getRefsByPrefixWithExclusions(RefDatabase.ALL, exclude);
+		assertEquals(1, refs.size());
+		checkContainsRef(refs, db.exactRef("HEAD"));
+	}
+
 	private RefUpdate updateRef(String name) throws IOException {
 		final RefUpdate ref = db.updateRef(name);
 		ref.setNewObjectId(db.resolve(Constants.HEAD));
@@ -596,4 +658,14 @@ public class FileReftableTest extends SampleDataRepositoryTestCase {
 			fail("link " + src + " to " + dst);
 		}
 	}
+
+	private static void checkContainsRef(Collection<Ref> haystack, Ref needle) {
+		for (Ref ref : haystack) {
+			if (ref.getName().equals(needle.getName()) &&
+					ref.getObjectId().equals(needle.getObjectId())) {
+				return;
+			}
+		}
+		fail("list " + haystack + " does not contain ref " + needle);
+	}
 }
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/RefDirectoryTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/RefDirectoryTest.java
index 97ef5993b9..38c545ef57 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/RefDirectoryTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/RefDirectoryTest.java
@@ -30,8 +30,10 @@ import java.io.IOException;
 import java.time.Instant;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.atomic.AtomicReference;
 
@@ -353,6 +355,24 @@ public class RefDirectoryTest extends LocalDiskRepositoryTestCase {
 	}
 
 	@Test
+	public void testGetRefs_ExcludingPrefixes() throws IOException {
+		writeLooseRef("refs/heads/A", A);
+		writeLooseRef("refs/heads/B", B);
+		writeLooseRef("refs/tags/tag", A);
+		writeLooseRef("refs/something/something", B);
+		writeLooseRef("refs/aaa/aaa", A);
+
+		Set<String> toExclude = new HashSet<>();
+		toExclude.add("refs/aaa/");
+		toExclude.add("refs/heads/");
+		List<Ref> refs = refdir.getRefsByPrefixWithExclusions(RefDatabase.ALL, toExclude);
+
+		assertEquals(2, refs.size());
+		assertTrue(refs.contains(refdir.exactRef("refs/tags/tag")));
+		assertTrue(refs.contains(refdir.exactRef("refs/something/something")));
+	}
+
+	@Test
 	public void testFirstExactRef_IgnoresGarbageRef() throws IOException {
 		writeLooseRef("refs/heads/A", A);
 		write(new File(diskRepo.getDirectory(), "refs/heads/bad"), "FAIL\n");
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.test/tst/org/eclipse/jgit/lib/RefTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/lib/RefTest.java
index 88d17ec153..7590048a71 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/lib/RefTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/lib/RefTest.java
@@ -26,6 +26,7 @@ import java.io.File;
 import java.io.FileOutputStream;
 import java.io.IOException;
 import java.util.Collection;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Optional;
 import java.util.Set;
@@ -318,6 +319,64 @@ public class RefTest extends SampleDataRepositoryTestCase {
 	}
 
 	@Test
+	public void testGetRefsExcludingPrefix() throws IOException {
+		Set<String> exclude = new HashSet<>();
+		exclude.add("refs/tags");
+		// HEAD + 12 refs/heads are present here.
+		List<Ref> refs =
+				db.getRefDatabase().getRefsByPrefixWithExclusions(RefDatabase.ALL, exclude);
+		assertEquals(13, refs.size());
+		checkContainsRef(refs, db.exactRef("HEAD"));
+		checkContainsRef(refs, db.exactRef("refs/heads/a"));
+		for (Ref notInResult : db.getRefDatabase().getRefsByPrefix("refs/tags")) {
+			assertFalse(refs.contains(notInResult));
+		}
+	}
+
+	@Test
+	public void testGetRefsExcludingPrefixes() throws IOException {
+		Set<String> exclude = new HashSet<>();
+		exclude.add("refs/tags/");
+		exclude.add("refs/heads/");
+		List<Ref> refs = db.getRefDatabase().getRefsByPrefixWithExclusions(RefDatabase.ALL, exclude);
+		assertEquals(1, refs.size());
+		checkContainsRef(refs, db.exactRef("HEAD"));
+	}
+
+	@Test
+	public void testGetRefsExcludingNonExistingPrefixes() throws IOException {
+		Set<String> prefixes = new HashSet<>();
+		prefixes.add("refs/tags/");
+		prefixes.add("refs/heads/");
+		prefixes.add("refs/nonexistent/");
+		List<Ref> refs = db.getRefDatabase().getRefsByPrefixWithExclusions(RefDatabase.ALL, prefixes);
+		assertEquals(1, refs.size());
+		checkContainsRef(refs, db.exactRef("HEAD"));
+	}
+
+	@Test
+	public void testGetRefsWithPrefixExcludingPrefixes() throws IOException {
+		Set<String> exclude = new HashSet<>();
+		exclude.add("refs/heads/pa");
+		String include = "refs/heads/p";
+		List<Ref> refs = db.getRefDatabase().getRefsByPrefixWithExclusions(include, exclude);
+		assertEquals(1, refs.size());
+		checkContainsRef(refs, db.exactRef("refs/heads/prefix/a"));
+	}
+
+	@Test
+	public void testGetRefsWithPrefixExcludingOverlappingPrefixes() throws IOException {
+		Set<String> exclude = new HashSet<>();
+		exclude.add("refs/heads/pa");
+		exclude.add("refs/heads/");
+		exclude.add("refs/heads/p");
+		exclude.add("refs/tags/");
+		List<Ref> refs = db.getRefDatabase().getRefsByPrefixWithExclusions(RefDatabase.ALL, exclude);
+		assertEquals(1, refs.size());
+		checkContainsRef(refs, db.exactRef("HEAD"));
+	}
+
+	@Test
 	public void testResolveTipSha1() throws IOException {
 		ObjectId masterId = db.resolve("refs/heads/master");
 		Set<Ref> resolved = db.getRefDatabase().getTipsWithSha1(masterId);