From 93a0e50ed087ec2de2b57483d2775a20fab03b75 Mon Sep 17 00:00:00 2001 From: Patrick Hiesel Date: Tue, 22 Jan 2019 10:02:14 +0100 Subject: [PATCH] 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 Signed-off-by: Ivan Frade --- .../storage/dfs/InMemoryRepositoryTest.java | 56 +++++++++++++++++++ .../tst/org/eclipse/jgit/lib/RefTest.java | 17 +++++- .../storage/dfs/DfsReftableDatabase.java | 21 +++++++ .../src/org/eclipse/jgit/lib/RefDatabase.java | 28 +++++++++- 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 git = new TestRepository<>( + repo)) { + RevCommit commit = git.branch("master").commit() + .message("first commit").create(); + + Set 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 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 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 git = new TestRepository<>( + repo)) { + RevCommit commit = git.commit().message("first commit").create(); + git.update("refs/tags/v0.2", commit); + Set 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 haystack, Ref needle) { + private static void checkContainsRef(Collection 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 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; @@ -275,6 +277,25 @@ public class DfsReftableDatabase extends DfsRefDatabase { return Collections.unmodifiableList(all); } + /** {@inheritDoc} */ + @Override + public Set getTipsWithSha1(ObjectId id) throws IOException { + if (!getReftableConfig().isIndexObjects()) { + return super.getTipsWithSha1(id); + } + lock.lock(); + try { + RefCursor cursor = reader().byObjectId(id); + Set refs = new HashSet<>(); + while (cursor.next()) { + refs.add(cursor.getRef()); + } + return refs; + } finally { + lock.unlock(); + } + } + /** {@inheritDoc} */ @Override public Ref peel(Ref ref) throws IOException { 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...)}. + * + *

+ * 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 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. *

-- 2.39.5