Introduce RefDatabase#hasFastTipsWithSha1

The reftable format supports fast inverse (SHA1 => ref) queries.

If the ref database does not support fast inverse queries, it may be
advantageous to build a complete SHA1 to ref map in advance for
multiple uses. To let applications decide, this function indicates
whether the inverse map is available.

Signed-off-by: Han-Wen Nienhuys <hanwen@google.com>
Change-Id: Idaf7e01075906972ec21332cade285289619c2b3

9 files changed, 135 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 0e06d459a2..cdc64fa1b2 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
@@ -155,6 +155,8 @@ public class FileReftableTest extends SampleDataRepositoryTestCase {
 		assertFalse(b.isSymbolic());
 		assertTrue(b.isPeeled());
 		assertEquals(bCommit, b.getObjectId().name());
+
+		assertTrue(db.getRefDatabase().hasFastTipsWithSha1());
 	}
 
 	@Test
@@ -169,6 +171,8 @@ public class FileReftableTest extends SampleDataRepositoryTestCase {
 		assertFalse(b.isSymbolic());
 		assertTrue(b.isPeeled());
 		assertEquals(bCommit, b.getObjectId().name());
+
+		assertFalse(db.getRefDatabase().hasFastTipsWithSha1());
 	}
 
 	@Test
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 45e6c7d128..daf540c413 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
@@ -177,6 +177,67 @@ public class ReftableTest {
 	}
 
 	@Test
+	public void hasObjMapRefs() throws IOException {
+		ArrayList<Ref> refs = new ArrayList<>();
+		refs.add(ref(MASTER, 1));
+		byte[] table = write(refs);
+		ReftableReader t = read(table);
+		assertTrue(t.hasObjectMap());
+	}
+
+	@Test
+	public void hasObjMapRefsSmallTable() throws IOException {
+		ArrayList<Ref> refs = new ArrayList<>();
+		ReftableConfig cfg = new ReftableConfig();
+		cfg.setIndexObjects(false);
+		refs.add(ref(MASTER, 1));
+		byte[] table = write(refs);
+		ReftableReader t = read(table);
+		assertTrue(t.hasObjectMap());
+	}
+
+	@Test
+	public void hasObjLogs() throws IOException {
+		PersonIdent who = new PersonIdent("Log", "Ger", 1500079709, -8 * 60);
+		String msg = "test";
+		ReftableConfig cfg = new ReftableConfig();
+		cfg.setIndexObjects(false);
+
+		ByteArrayOutputStream buffer = new ByteArrayOutputStream();
+		ReftableWriter writer = new ReftableWriter(buffer)
+			.setMinUpdateIndex(1)
+			.setConfig(cfg)
+			.setMaxUpdateIndex(1)
+			.begin();
+
+		writer.writeLog("master", 1, who, ObjectId.zeroId(), id(1), msg);
+		writer.finish();
+		byte[] table = buffer.toByteArray();
+
+		ReftableReader t = read(table);
+		assertTrue(t.hasObjectMap());
+	}
+
+	@Test
+	public void hasObjMapRefsNoIndexObjects() throws IOException {
+		ArrayList<Ref> refs = new ArrayList<>();
+		ReftableConfig cfg = new ReftableConfig();
+		cfg.setIndexObjects(false);
+		cfg.setRefBlockSize(256);
+		cfg.setAlignBlocks(true);
+
+		// Fill up 5 blocks.
+		int N = 256 * 5 / 25;
+		for (int i= 0; i < N; i++) {
+			refs.add(ref(String.format("%02d/xxxxxxxxxx", i), i));
+		}
+		byte[] table = write(refs, cfg);
+
+		ReftableReader t = read(table);
+		assertFalse(t.hasObjectMap());
+	}
+
+	@Test
 	public void oneIdRef() throws IOException {
 		Ref exp = ref(MASTER, 1);
 		byte[] table = write(exp);
@@ -936,8 +997,13 @@ public class ReftableTest {
 	}
 
 	private byte[] write(Collection<Ref> refs) throws IOException {
+		return write(refs, new ReftableConfig());
+	}
+
+	private byte[] write(Collection<Ref> refs, ReftableConfig cfg) throws IOException {
 		ByteArrayOutputStream buffer = new ByteArrayOutputStream();
 		stats = new ReftableWriter(buffer)
+				.setConfig(cfg)
 				.begin()
 				.sortAndWriteRefs(refs)
 				.finish()
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 2ad3ae7e62..124131d1d3 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
@@ -218,6 +218,12 @@ public class DfsReftableDatabase extends DfsRefDatabase {
 
 	/** {@inheritDoc} */
 	@Override
+	public boolean hasFastTipsWithSha1() throws IOException {
+		return reftableDatabase.hasFastTipsWithSha1();
+	}
+
+	/** {@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/internal/storage/file/FileReftableDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/FileReftableDatabase.java
index b06fd30b34..fd80ad9ec0 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
@@ -125,6 +125,12 @@ public class FileReftableDatabase extends RefDatabase {
 				&& new File(repoDir, Constants.REFTABLE).isDirectory();
 	}
 
+	/** {@inheritDoc} */
+	@Override
+	public boolean hasFastTipsWithSha1() throws IOException {
+		return reftableDatabase.hasFastTipsWithSha1();
+	}
+
 	/**
 	 * Runs a full compaction for GC purposes.
 	 * @throws IOException on I/O errors
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/MergedReftable.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/MergedReftable.java
index 4de5e392f9..6c312ca7a0 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/MergedReftable.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/MergedReftable.java
@@ -100,6 +100,16 @@ public class MergedReftable extends Reftable {
 
 	/** {@inheritDoc} */
 	@Override
+	public boolean hasObjectMap() throws IOException {
+		boolean has = true;
+		for (int i = 0; has && i < tables.length; i++) {
+			has = has && tables[i].hasObjectMap();
+		};
+		return has;
+	}
+
+	/** {@inheritDoc} */
+	@Override
 	public RefCursor allRefs() throws IOException {
 		MergedRefCursor m = new MergedRefCursor();
 		for (int i = 0; i < tables.length; i++) {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/Reftable.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/Reftable.java
index 8f64261766..8a8a14375a 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/Reftable.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/Reftable.java
@@ -162,6 +162,12 @@ public abstract class Reftable {
 	public abstract RefCursor byObjectId(AnyObjectId id) throws IOException;
 
 	/**
+	 * @return whether this reftable can do a fast SHA1 => ref lookup.
+	 * @throws IOException on I/O problems.
+	 */
+	public abstract boolean hasObjectMap() throws IOException;
+
+	/**
 	 * Seek reader to read log records.
 	 *
 	 * @return cursor to iterate; empty cursor if no logs are present.
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 5a32d29144..c08f1814dc 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
@@ -299,6 +299,19 @@ public abstract class ReftableDatabase {
 	}
 
 	/**
+	 * @return whether there is a fast SHA1 to ref map.
+	 * @throws IOException in case of I/O problems.
+	 */
+	public boolean hasFastTipsWithSha1() throws IOException {
+		lock.lock();
+		try {
+			return reader().hasObjectMap();
+		} finally {
+			lock.unlock();
+		}
+	}
+
+	/**
 	 * Returns all refs that resolve directly to the given {@link ObjectId}.
 	 * Includes peeled {@linkObjectId}s.
 	 *
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java
index c5e667449a..14b821a1ed 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java
@@ -128,6 +128,16 @@ public class ReftableReader extends Reftable implements AutoCloseable {
 		return blockSize;
 	}
 
+	@Override
+	public boolean hasObjectMap() throws IOException {
+		if (objIndexPosition == -1) {
+			readFileFooter();
+		}
+
+		// We have the map, we have no refs, or the table is small.
+		return (objPosition > 0 || refEnd == 24 || refIndexPosition == 0);
+	}
+
 	/**
 	 * Get the minimum update index for log entries that appear in this
 	 * reftable.
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 4d9450e758..9b5a1fdc22 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/RefDatabase.java
@@ -497,6 +497,20 @@ public abstract class RefDatabase {
 	}
 
 	/**
+	 * If the ref database does not support fast inverse queries, it may
+	 * be advantageous to build a complete SHA1 to ref map in advance for
+	 * multiple uses. To let applications decide on this decision,
+	 * this function indicates whether the inverse map is available.
+	 *
+	 * @return whether this RefDatabase supports fast inverse ref queries.
+	 * @throws IOException on I/O problems.
+	 * @since 5.6
+	 */
+	public boolean hasFastTipsWithSha1() throws IOException {
+		return false;
+	}
+
+	/**
 	 * Check if any refs exist in the ref database.
 	 * <p>
 	 * This uses the same definition of refs as {@link #getRefs()}. In