Introduce RefDatabase#getTipsWithSha1 to list refs pointing to object

Add resolveTipSha1, an inverse of exactRef(String ...), to RefDatabase
and provide a default implementation that runs in O(n) time where n is
the number of refs. For RefTable, provide an implementation that runs
in O(log(n)) time.

[ifrade@google.com: with tests in InMemoryRepositoryTest to exercise
 the reftable code path, too]

Change-Id: I2811ccd0339cdc1c74b42cce2ea003f07a2ce9e1
Signed-off-by: Patrick Hiesel <hiesel@google.com>
Signed-off-by: Ivan Frade <ifrade@google.com>

4 files changed, 120 insertions, 2 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/InMemoryRepositoryTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/InMemoryRepositoryTest.java
index 3b26c1f5ea..bab6110ce6 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/InMemoryRepositoryTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/dfs/InMemoryRepositoryTest.java
@@ -45,6 +45,8 @@ package org.eclipse.jgit.internal.storage.dfs;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 
+import java.util.Set;
+
 import org.eclipse.jgit.junit.TestRepository;
 import org.eclipse.jgit.lib.ObjectIdRef;
 import org.eclipse.jgit.lib.Ref;
@@ -91,4 +93,58 @@ public class InMemoryRepositoryTest {
 			assertEquals(1000, peeledRef.getUpdateIndex());
 		}
 	}
+
+	@Test
+	public void sha1ToTip_ref() throws Exception {
+		InMemoryRepository repo = new InMemoryRepository(
+				new DfsRepositoryDescription());
+		try (TestRepository<InMemoryRepository> git = new TestRepository<>(
+				repo)) {
+			RevCommit commit = git.branch("master").commit()
+					.message("first commit").create();
+
+			Set<Ref> tipsWithSha1 = repo.getRefDatabase()
+					.getTipsWithSha1(commit.getId());
+			assertEquals(1, tipsWithSha1.size());
+			Ref ref = tipsWithSha1.iterator().next();
+			assertEquals(ref.getName(), "refs/heads/master");
+			assertEquals(commit.getId(), ref.getObjectId());
+		}
+	}
+
+	@Test
+	public void sha1ToTip_annotatedTag() throws Exception {
+		InMemoryRepository repo = new InMemoryRepository(
+				new DfsRepositoryDescription());
+		try (TestRepository<InMemoryRepository> git = new TestRepository<>(
+				repo)) {
+			RevCommit commit = git.commit()
+					.message("first commit").create();
+			RevTag tagObj = git.tag("v0.1", commit);
+			git.update("refs/tags/v0.1", tagObj);
+			Set<Ref> tipsWithSha1 = repo.getRefDatabase()
+					.getTipsWithSha1(commit.getId());
+			assertEquals(1, tipsWithSha1.size());
+			Ref ref = tipsWithSha1.iterator().next();
+			assertEquals(ref.getName(), "refs/tags/v0.1");
+			assertEquals(commit.getId(), ref.getPeeledObjectId());
+		}
+	}
+
+	@Test
+	public void sha1ToTip_tag() throws Exception {
+		InMemoryRepository repo = new InMemoryRepository(
+				new DfsRepositoryDescription());
+		try (TestRepository<InMemoryRepository> git = new TestRepository<>(
+				repo)) {
+			RevCommit commit = git.commit().message("first commit").create();
+			git.update("refs/tags/v0.2", commit);
+			Set<Ref> tipsWithSha1 = repo.getRefDatabase()
+					.getTipsWithSha1(commit.getId());
+			assertEquals(1, tipsWithSha1.size());
+			Ref ref = tipsWithSha1.iterator().next();
+			assertEquals(ref.getName(), "refs/tags/v0.2");
+			assertEquals(commit.getId(), ref.getObjectId());
+		}
+	}
 }
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 7d2c4a2784..b53d5b9448 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
@@ -58,8 +58,10 @@ import static org.junit.Assert.fail;
 import java.io.File;
 import java.io.FileOutputStream;
 import java.io.IOException;
+import java.util.Collection;
 import java.util.List;
 import java.util.Optional;
+import java.util.Set;
 import java.util.TreeSet;
 
 import org.eclipse.jgit.lib.Ref.Storage;
@@ -313,7 +315,7 @@ public class RefTest extends SampleDataRepositoryTestCase {
 		assertEquals(dst.isPeeled(), ref.isPeeled());
 	}
 
-	private static void checkContainsRef(List<Ref> haystack, Ref needle) {
+	private static void checkContainsRef(Collection<Ref> haystack, Ref needle) {
 		for (Ref ref : haystack) {
 			if (ref.getName().equals(needle.getName()) &&
 					ref.getObjectId().equals(needle.getObjectId())) {
@@ -347,4 +349,17 @@ public class RefTest extends SampleDataRepositoryTestCase {
 		checkContainsRef(refs, db.exactRef("refs/heads/prefix/a"));
 		checkContainsRef(refs, db.exactRef("refs/tags/A"));
 	}
+
+	@Test
+	public void testResolveTipSha1() throws IOException {
+		ObjectId masterId = db.resolve("refs/heads/master");
+		Set<Ref> resolved = db.getRefDatabase().getTipsWithSha1(masterId);
+
+		assertEquals(2, resolved.size());
+		checkContainsRef(resolved, db.exactRef("refs/heads/master"));
+		checkContainsRef(resolved, db.exactRef("HEAD"));
+
+		assertEquals(db.getRefDatabase()
+				.getTipsWithSha1(ObjectId.zeroId()).size(), 0);
+	}
 }
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 87983ce8c0..6050c15992 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
@@ -47,8 +47,10 @@ import java.io.IOException;
 import java.util.Arrays;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.concurrent.locks.ReentrantLock;
 
 import org.eclipse.jgit.annotations.Nullable;
@@ -277,6 +279,25 @@ public class DfsReftableDatabase extends DfsRefDatabase {
 
 	/** {@inheritDoc} */
 	@Override
+	public Set<Ref> getTipsWithSha1(ObjectId id) throws IOException {
+		if (!getReftableConfig().isIndexObjects()) {
+			return super.getTipsWithSha1(id);
+		}
+		lock.lock();
+		try {
+			RefCursor cursor = reader().byObjectId(id);
+			Set<Ref> refs = new HashSet<>();
+			while (cursor.next()) {
+				refs.add(cursor.getRef());
+			}
+			return refs;
+		} finally {
+			lock.unlock();
+		}
+	}
+
+	/** {@inheritDoc} */
+	@Override
 	public Ref peel(Ref ref) throws IOException {
 		Ref oldLeaf = ref.getLeaf();
 		if (oldLeaf.isPeeled() || oldLeaf.getObjectId() == null) {
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 877792097c..4d9450e758 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java
@@ -44,6 +44,7 @@
 package org.eclipse.jgit.lib;
 
 import static java.util.stream.Collectors.toList;
+import static java.util.stream.Collectors.toSet;
 
 import java.io.IOException;
 import java.util.ArrayList;
@@ -52,7 +53,7 @@ import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
-
+import java.util.Set;
 import org.eclipse.jgit.annotations.NonNull;
 import org.eclipse.jgit.annotations.Nullable;
 
@@ -470,6 +471,31 @@ public abstract class RefDatabase {
 		return Collections.unmodifiableList(result);
 	}
 
+
+	/**
+	 * Returns all refs that resolve directly to the given {@link ObjectId}.
+	 * Includes peeled {@linkObjectId}s. This is the inverse lookup of
+	 * {@link #exactRef(String...)}.
+	 *
+	 * <p>
+	 * The default implementation uses a linear scan. Implementors of
+	 * {@link RefDatabase} should override this method directly if a better
+	 * implementation is possible.
+	 *
+	 * @param id
+	 *            {@link ObjectId} to resolve
+	 * @return a {@link Set} of {@link Ref}s whose tips point to the provided
+	 *         id.
+	 * @throws java.io.IOException
+	 *             the reference space cannot be accessed.
+	 * @since 5.4
+	 */
+	@NonNull
+	public Set<Ref> getTipsWithSha1(ObjectId id) throws IOException {
+		return getRefs().stream().filter(r -> id.equals(r.getObjectId())
+				|| id.equals(r.getPeeledObjectId())).collect(toSet());
+	}
+
 	/**
 	 * Check if any refs exist in the ref database.
 	 * <p>