Merge "reftable: explicitly store update_index per ref"

7 files changed, 74 insertions, 26 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockReader.java
index a92bedcebd..ce2ba4a2e1 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockReader.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockReader.java
@@ -166,6 +166,10 @@ class BlockReader {
 		return readVarint64();
 	}
 
+	long readUpdateIndexDelta() {
+		return readVarint64();
+	}
+
 	Ref readRef() throws IOException {
 		String name = RawParseUtils.decode(UTF_8, nameBuf, 0, nameLen);
 		switch (valueType & VALUE_TYPE_MASK) {
@@ -490,6 +494,7 @@ class BlockReader {
 	void skipValue() {
 		switch (blockType) {
 		case REF_BLOCK_TYPE:
+			readVarint64(); // update_index_delta
 			switch (valueType & VALUE_TYPE_MASK) {
 			case VALUE_NONE:
 				return;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockWriter.java
index 8f3e889de6..b3173e838c 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockWriter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockWriter.java
@@ -354,10 +354,12 @@ class BlockWriter {
 
 	static class RefEntry extends Entry {
 		final Ref ref;
+		final long updateIndexDelta;
 
-		RefEntry(Ref ref) {
+		RefEntry(Ref ref, long updateIndexDelta) {
 			super(nameUtf8(ref));
 			this.ref = ref;
+			this.updateIndexDelta = updateIndexDelta;
 		}
 
 		@Override
@@ -380,17 +382,18 @@ class BlockWriter {
 
 		@Override
 		int valueSize() {
+			int n = computeVarintSize(updateIndexDelta);
 			switch (valueType()) {
 			case VALUE_NONE:
-				return 0;
+				return n;
 			case VALUE_1ID:
-				return OBJECT_ID_LENGTH;
+				return n + OBJECT_ID_LENGTH;
 			case VALUE_2ID:
-				return 2 * OBJECT_ID_LENGTH;
+				return n + 2 * OBJECT_ID_LENGTH;
 			case VALUE_SYMREF:
 				if (ref.isSymbolic()) {
 					int nameLen = nameUtf8(ref.getTarget()).length;
-					return computeVarintSize(nameLen) + nameLen;
+					return n + computeVarintSize(nameLen) + nameLen;
 				}
 			}
 			throw new IllegalStateException();
@@ -398,6 +401,7 @@ class BlockWriter {
 
 		@Override
 		void writeValue(ReftableOutputStream os) throws IOException {
+			os.writeVarint(updateIndexDelta);
 			switch (valueType()) {
 			case VALUE_NONE:
 				return;
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 71144cd30d..9fc6ae2bb4 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,13 +100,6 @@ public class MergedReftable extends Reftable {
 
 	@Override
 	public RefCursor seekRef(String name) throws IOException {
-		if (name.endsWith("/")) { //$NON-NLS-1$
-			return seekRefPrefix(name);
-		}
-		return seekSingleRef(name);
-	}
-
-	private RefCursor seekRefPrefix(String name) throws IOException {
 		MergedRefCursor m = new MergedRefCursor();
 		for (int i = 0; i < tables.length; i++) {
 			m.add(new RefQueueEntry(tables[i].seekRef(name), i));
@@ -114,17 +107,6 @@ public class MergedReftable extends Reftable {
 		return m;
 	}
 
-	private RefCursor seekSingleRef(String name) throws IOException {
-		// Walk the tables from highest priority (end of list) to lowest.
-		// As soon as the reference is found (queue not empty), all lower
-		// priority tables are irrelevant as current table shadows them.
-		MergedRefCursor m = new MergedRefCursor();
-		for (int i = tables.length - 1; i >= 0 && m.queue.isEmpty(); i--) {
-			m.add(new RefQueueEntry(tables[i].seekRef(name), i));
-		}
-		return m;
-	}
-
 	@Override
 	public RefCursor byObjectId(AnyObjectId name) throws IOException {
 		MergedRefCursor m = new MergedRefCursor();
@@ -168,6 +150,7 @@ public class MergedReftable extends Reftable {
 		private final PriorityQueue<RefQueueEntry> queue;
 		private RefQueueEntry head;
 		private Ref ref;
+		private long updateIndex;
 
 		MergedRefCursor() {
 			queue = new PriorityQueue<>(queueSize(), RefQueueEntry::compare);
@@ -205,6 +188,7 @@ public class MergedReftable extends Reftable {
 				}
 
 				ref = t.rc.getRef();
+				updateIndex = t.rc.getUpdateIndex();
 				boolean include = includeDeletes || !t.rc.wasDeleted();
 				skipShadowedRefs(ref.getName());
 				add(t);
@@ -240,7 +224,16 @@ public class MergedReftable extends Reftable {
 		}
 
 		@Override
+		public long getUpdateIndex() {
+			return updateIndex;
+		}
+
+		@Override
 		public void close() {
+			if (head != null) {
+				head.rc.close();
+				head = null;
+			}
 			while (!queue.isEmpty()) {
 				queue.remove().rc.close();
 			}
@@ -251,6 +244,10 @@ public class MergedReftable extends Reftable {
 		static int compare(RefQueueEntry a, RefQueueEntry b) {
 			int cmp = a.name().compareTo(b.name());
 			if (cmp == 0) {
+				// higher updateIndex shadows lower updateIndex.
+				cmp = Long.signum(b.updateIndex() - a.updateIndex());
+			}
+			if (cmp == 0) {
 				// higher index shadows lower index, so higher index first.
 				cmp = b.stackIdx - a.stackIdx;
 			}
@@ -268,6 +265,10 @@ public class MergedReftable extends Reftable {
 		String name() {
 			return rc.getRef().getName();
 		}
+
+		long updateIndex() {
+			return rc.getUpdateIndex();
+		}
 	}
 
 	private class MergedLogCursor extends LogCursor {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java
index 786fae1a69..d8e9c609f0 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java
@@ -61,6 +61,9 @@ public abstract class RefCursor implements AutoCloseable {
 	/** @return reference at the current position. */
 	public abstract Ref getRef();
 
+	/** @return updateIndex that last modified the current reference, */
+	public abstract long getUpdateIndex();
+
 	/** @return {@code true} if the current reference was deleted. */
 	public boolean wasDeleted() {
 		Ref r = getRef();
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableCompactor.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableCompactor.java
index 4f92267100..e7f406ce0d 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableCompactor.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableCompactor.java
@@ -220,7 +220,7 @@ public class ReftableCompactor {
 	private void mergeRefs(MergedReftable mr) throws IOException {
 		try (RefCursor rc = mr.allRefs()) {
 			while (rc.next()) {
-				writer.writeRef(rc.getRef());
+				writer.writeRef(rc.getRef(), rc.getUpdateIndex());
 			}
 		}
 	}
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 be1eb40edb..407a77c7d3 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
@@ -455,6 +455,7 @@ public class ReftableReader extends Reftable {
 		private final boolean prefix;
 
 		private Ref ref;
+		private long updateIndex;
 		BlockReader block;
 
 		RefCursorImpl(long scanEnd, byte[] match, boolean prefix) {
@@ -483,6 +484,7 @@ public class ReftableReader extends Reftable {
 					return false;
 				}
 
+				updateIndex = minUpdateIndex + block.readUpdateIndexDelta();
 				ref = block.readRef();
 				if (!includeDeletes && wasDeleted()) {
 					continue;
@@ -497,6 +499,11 @@ public class ReftableReader extends Reftable {
 		}
 
 		@Override
+		public long getUpdateIndex() {
+			return updateIndex;
+		}
+
+		@Override
 		public void close() {
 			// Do nothing.
 		}
@@ -574,6 +581,7 @@ public class ReftableReader extends Reftable {
 		private final ObjectId match;
 
 		private Ref ref;
+		private long updateIndex;
 		private int listIdx;
 
 		private LongList blockPos;
@@ -647,6 +655,7 @@ public class ReftableReader extends Reftable {
 				}
 
 				block.parseKey();
+				updateIndex = minUpdateIndex + block.readUpdateIndexDelta();
 				ref = block.readRef();
 				ObjectId id = ref.getObjectId();
 				if (id != null && match.equals(id)
@@ -662,6 +671,11 @@ public class ReftableReader extends Reftable {
 		}
 
 		@Override
+		public long getUpdateIndex() {
+			return updateIndex;
+		}
+
+		@Override
 		public void close() {
 			// Do nothing.
 		}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java
index 45b759f952..0ac2445fc0 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableWriter.java
@@ -214,7 +214,7 @@ public class ReftableWriter {
 	public ReftableWriter sortAndWriteRefs(Collection<Ref> refsToPack)
 			throws IOException {
 		Iterator<RefEntry> itr = refsToPack.stream()
-				.map(RefEntry::new)
+				.map(r -> new RefEntry(r, maxUpdateIndex - minUpdateIndex))
 				.sorted(Entry::compare)
 				.iterator();
 		while (itr.hasNext()) {
@@ -236,7 +236,28 @@ public class ReftableWriter {
 	 *             if reftable cannot be written.
 	 */
 	public void writeRef(Ref ref) throws IOException {
-		long blockPos = refs.write(new RefEntry(ref));
+		writeRef(ref, maxUpdateIndex);
+	}
+
+	/**
+	 * Write one reference to the reftable.
+	 * <p>
+	 * References must be passed in sorted order.
+	 *
+	 * @param ref
+	 *            the reference to store.
+	 * @param updateIndex
+	 *            the updateIndex that modified this reference. Must be
+	 *            {@code >= minUpdateIndex} for this file.
+	 * @throws IOException
+	 *             if reftable cannot be written.
+	 */
+	public void writeRef(Ref ref, long updateIndex) throws IOException {
+		if (updateIndex < minUpdateIndex) {
+			throw new IllegalArgumentException();
+		}
+		long d = updateIndex - minUpdateIndex;
+		long blockPos = refs.write(new RefEntry(ref, d));
 		indexRef(ref, blockPos);
 	}