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>

2 files changed, 72 insertions, 1 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);
+	}
 }