Add getsRefsByPrefixWithSkips (excluding prefixes) to ReftableDatabase

We sometimes want to get all the refs except specific prefixes,
similarly to getRefsByPrefix that gets all the refs of a specific
prefix.

We now create a new method that gets all refs matching a prefix except a
set of specific prefixes.

One use-case is for Gerrit to be able to get all the refs except
refs/changes; in Gerrit we often have lots of refs/changes, but very
little other refs. Currently, to get all the refs except refs/changes we
need to get all the refs and then filter the refs/changes, which is very
inefficient. With this method, we can simply skip the unneeded prefix so
that we don't have to go over all the elements.

RefDirectory still uses the inefficient implementation, since there
isn't a simple way to use Refcursor to achieve the efficient
implementation (as done in ReftableDatabase).

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

8 files changed, 255 insertions, 0 deletions

diff --git a/org.eclipse.jgit.http.test/src/org/eclipse/jgit/http/test/RefsUnreadableInMemoryRepository.java b/org.eclipse.jgit.http.test/src/org/eclipse/jgit/http/test/RefsUnreadableInMemoryRepository.java
index 80cbe8738c..4167b038e1 100644
--- a/org.eclipse.jgit.http.test/src/org/eclipse/jgit/http/test/RefsUnreadableInMemoryRepository.java
+++ b/org.eclipse.jgit.http.test/src/org/eclipse/jgit/http/test/RefsUnreadableInMemoryRepository.java
@@ -85,6 +85,17 @@ class RefsUnreadableInMemoryRepository extends InMemoryRepository {
 
 		/** {@inheritDoc} */
 		@Override
+		public List<Ref> getRefsByPrefixWithExclusions(String include, Set<String> excludes)
+				throws IOException {
+			if (failing) {
+				throw new IOException("disk failed, no refs found");
+			}
+
+			return super.getRefsByPrefixWithExclusions(include, excludes);
+		}
+
+		/** {@inheritDoc} */
+		@Override
 		public Set<Ref> getTipsWithSha1(ObjectId id) throws IOException {
 			if (failing) {
 				throw new IOException("disk failed, no refs found");
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/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);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReftableDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReftableDatabase.java
index 5561dc6a27..6c3b056efd 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReftableDatabase.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/DfsReftableDatabase.java
@@ -178,6 +178,13 @@ public class DfsReftableDatabase extends DfsRefDatabase {
 
 	/** {@inheritDoc} */
 	@Override
+	public List<Ref> getRefsByPrefixWithExclusions(String include, Set<String> excludes)
+			throws IOException {
+		return reftableDatabase.getRefsByPrefixWithExclusions(include, excludes);
+	}
+
+	/** {@inheritDoc} */
+	@Override
 	public Set<Ref> getTipsWithSha1(ObjectId id) throws IOException {
 		if (!getReftableConfig().isIndexObjects()) {
 			return super.getTipsWithSha1(id);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileReftableDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileReftableDatabase.java
index ad1e753128..a80fa837b7 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileReftableDatabase.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileReftableDatabase.java
@@ -21,6 +21,7 @@ import java.util.Collections;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.TreeSet;
 import java.util.concurrent.locks.Lock;
 import java.util.concurrent.locks.ReentrantLock;
@@ -181,6 +182,13 @@ public class FileReftableDatabase extends RefDatabase {
 
 	/** {@inheritDoc} */
 	@Override
+	public List<Ref> getRefsByPrefixWithExclusions(String include, Set<String> excludes)
+			throws IOException {
+		return reftableDatabase.getRefsByPrefixWithExclusions(include, excludes);
+	}
+
+	/** {@inheritDoc} */
+	@Override
 	public List<Ref> getAdditionalRefs() throws IOException {
 		return Collections.emptyList();
 	}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableDatabase.java
index 4747be3544..0c16828617 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableDatabase.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableDatabase.java
@@ -14,10 +14,12 @@ import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashSet;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
 import java.util.TreeSet;
 import java.util.concurrent.locks.ReentrantLock;
+import java.util.stream.Collectors;
 
 import org.eclipse.jgit.annotations.Nullable;
 import org.eclipse.jgit.lib.ObjectId;
@@ -266,6 +268,54 @@ public abstract class ReftableDatabase {
 	}
 
 	/**
+	 * Returns refs whose names start with a given prefix excluding all refs that
+	 * start with one of the given prefixes.
+	 *
+	 * @param include string that names of refs should start with; may be empty.
+	 * @param excludes strings that names of refs can't start with; may be empty.
+	 * @return immutable list of refs whose names start with {@code include} and
+	 *         none of the strings in {@code exclude}.
+	 * @throws java.io.IOException the reference space cannot be accessed.
+	 */
+	public List<Ref> getRefsByPrefixWithExclusions(String include, Set<String> excludes) throws IOException {
+		if (excludes.isEmpty()) {
+			return getRefsByPrefix(include);
+		}
+		List<Ref> results = new ArrayList<>();
+		lock.lock();
+		try {
+			Reftable table = reader();
+			Iterator<String> excludeIterator =
+					excludes.stream().sorted().collect(Collectors.toList()).iterator();
+			String currentExclusion = excludeIterator.hasNext() ? excludeIterator.next() : null;
+			try (RefCursor rc = RefDatabase.ALL.equals(include) ? table.allRefs() : table.seekRefsWithPrefix(include)) {
+				while (rc.next()) {
+					Ref ref = table.resolve(rc.getRef());
+					if (ref == null || ref.getObjectId() == null) {
+						continue;
+					}
+					// Skip prefixes that will never see since we are already further than those
+					// prefixes lexicographically.
+					while (excludeIterator.hasNext() && !ref.getName().startsWith(currentExclusion)
+							&& ref.getName().compareTo(currentExclusion) > 0) {
+						currentExclusion = excludeIterator.next();
+					}
+
+					if (currentExclusion != null && ref.getName().startsWith(currentExclusion)) {
+						rc.seekPastPrefix(currentExclusion);
+						continue;
+					}
+					results.add(ref);
+				}
+			}
+		} finally {
+			lock.unlock();
+		}
+
+		return Collections.unmodifiableList(results);
+	}
+
+	/**
 	 * @return whether there is a fast SHA1 to ref map.
 	 * @throws IOException in case of I/O problems.
 	 */
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java
index 6832c9cd80..7b7bdebac8 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java
@@ -21,6 +21,9 @@ import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
 import org.eclipse.jgit.annotations.NonNull;
 import org.eclipse.jgit.annotations.Nullable;
 
@@ -414,6 +417,31 @@ public abstract class RefDatabase {
 	}
 
 	/**
+	 * Returns refs whose names start with a given prefix excluding all refs that
+	 * start with one of the given prefixes.
+	 *
+	 * <p>
+	 * The default implementation is not efficient. Implementors of {@link RefDatabase}
+	 * should override this method directly if a better implementation is possible.
+	 * 
+	 * @param include string that names of refs should start with; may be empty.
+	 * @param excludes strings that names of refs can't start with; may be empty.
+	 * @return immutable list of refs whose names start with {@code prefix} and none
+	 *         of the strings in {@code exclude}.
+	 * @throws java.io.IOException the reference space cannot be accessed.
+	 * @since 5.11
+	 */
+	@NonNull
+	public List<Ref> getRefsByPrefixWithExclusions(String include, Set<String> excludes)
+			throws IOException {
+		Stream<Ref> refs = getRefs(include).values().stream();
+		for(String exclude: excludes) {
+			refs = refs.filter(r -> !r.getName().startsWith(exclude));
+		}
+		return Collections.unmodifiableList(refs.collect(Collectors.toList()));
+	}
+
+	/**
 	 * Returns refs whose names start with one of the given prefixes.
 	 * <p>
 	 * The default implementation uses {@link #getRefsByPrefix(String)}.