midx.PackIndexMerger: Helper to iterate over n-indexesHEADmaster

The multipack index can be build merging the individual pack indexes
and handling correctly the duplicates.

PackIndexMerger is a utility function that gathers n-indexes and
allows to iterate as one with the correct sha1 order. It also
precalculates some of the needed metadata (as count of objects without
duplicates, or if offsets go over 32 bits).

Change-Id: I515b70fffff4489d83834488daf975f85726ea96

2 files changed, 310 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/midx/PackIndexMergerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/midx/PackIndexMergerTest.java
new file mode 100644
index 0000000000..1d8bde0f44
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/midx/PackIndexMergerTest.java
@@ -0,0 +1,239 @@
+/*
+ * Copyright (C) 2025, Google Inc.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.internal.storage.midx;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.eclipse.jgit.internal.storage.file.PackIndex;
+import org.eclipse.jgit.junit.FakeIndexFactory;
+import org.eclipse.jgit.junit.FakeIndexFactory.IndexObject;
+import org.junit.Test;
+
+public class PackIndexMergerTest {
+
+	@Test
+	public void rawIterator_noDuplicates() {
+		PackIndex idxOne = indexOf(
+				oidOffset("0000000000000000000000000000000000000001", 500),
+				oidOffset("0000000000000000000000000000000000000005", 12),
+				oidOffset("0000000000000000000000000000000000000010", 1500));
+		PackIndex idxTwo = indexOf(
+				oidOffset("0000000000000000000000000000000000000002", 501),
+				oidOffset("0000000000000000000000000000000000000003", 13),
+				oidOffset("0000000000000000000000000000000000000015", 1501));
+		PackIndex idxThree = indexOf(
+				oidOffset("0000000000000000000000000000000000000004", 502),
+				oidOffset("0000000000000000000000000000000000000007", 14),
+				oidOffset("0000000000000000000000000000000000000012", 1502));
+		PackIndexMerger merger = new PackIndexMerger(
+				Map.of("p1", idxOne, "p2", idxTwo, "p3", idxThree));
+		assertEquals(9, merger.getUniqueObjectCount());
+		assertEquals(3, merger.getPackCount());
+		assertFalse(merger.needsLargeOffsetsChunk());
+		Iterator<PackIndexMerger.MidxMutableEntry> it = merger.rawIterator();
+		assertNextEntry(it, "0000000000000000000000000000000000000001", 0, 500);
+		assertNextEntry(it, "0000000000000000000000000000000000000002", 1, 501);
+		assertNextEntry(it, "0000000000000000000000000000000000000003", 1, 13);
+		assertNextEntry(it, "0000000000000000000000000000000000000004", 2, 502);
+		assertNextEntry(it, "0000000000000000000000000000000000000005", 0, 12);
+		assertNextEntry(it, "0000000000000000000000000000000000000007", 2, 14);
+		assertNextEntry(it, "0000000000000000000000000000000000000010", 0,
+				1500);
+		assertNextEntry(it, "0000000000000000000000000000000000000012", 2,
+				1502);
+		assertNextEntry(it, "0000000000000000000000000000000000000015", 1,
+				1501);
+		assertFalse(it.hasNext());
+	}
+
+	@Test
+	public void rawIterator_allDuplicates() {
+		PackIndex idxOne = indexOf(
+				oidOffset("0000000000000000000000000000000000000001", 500),
+				oidOffset("0000000000000000000000000000000000000005", 12),
+				oidOffset("0000000000000000000000000000000000000010", 1500));
+		PackIndexMerger merger = new PackIndexMerger(
+				Map.of("p1", idxOne, "p2", idxOne, "p3", idxOne));
+		assertEquals(3, merger.getUniqueObjectCount());
+		assertEquals(3, merger.getPackCount());
+		assertFalse(merger.needsLargeOffsetsChunk());
+		Iterator<PackIndexMerger.MidxMutableEntry> it = merger.rawIterator();
+		assertNextEntry(it, "0000000000000000000000000000000000000001", 0, 500);
+		assertNextEntry(it, "0000000000000000000000000000000000000001", 1, 500);
+		assertNextEntry(it, "0000000000000000000000000000000000000001", 2, 500);
+		assertNextEntry(it, "0000000000000000000000000000000000000005", 0, 12);
+		assertNextEntry(it, "0000000000000000000000000000000000000005", 1, 12);
+		assertNextEntry(it, "0000000000000000000000000000000000000005", 2, 12);
+		assertNextEntry(it, "0000000000000000000000000000000000000010", 0,
+				1500);
+		assertNextEntry(it, "0000000000000000000000000000000000000010", 1,
+				1500);
+		assertNextEntry(it, "0000000000000000000000000000000000000010", 2,
+				1500);
+		assertFalse(it.hasNext());
+	}
+
+	@Test
+	public void bySha1Iterator_noDuplicates() {
+		PackIndex idxOne = indexOf(
+				oidOffset("0000000000000000000000000000000000000001", 500),
+				oidOffset("0000000000000000000000000000000000000005", 12),
+				oidOffset("0000000000000000000000000000000000000010", 1500));
+		PackIndex idxTwo = indexOf(
+				oidOffset("0000000000000000000000000000000000000002", 501),
+				oidOffset("0000000000000000000000000000000000000003", 13),
+				oidOffset("0000000000000000000000000000000000000015", 1501));
+		PackIndex idxThree = indexOf(
+				oidOffset("0000000000000000000000000000000000000004", 502),
+				oidOffset("0000000000000000000000000000000000000007", 14),
+				oidOffset("0000000000000000000000000000000000000012", 1502));
+		PackIndexMerger merger = new PackIndexMerger(
+				Map.of("p1", idxOne, "p2", idxTwo, "p3", idxThree));
+		assertEquals(9, merger.getUniqueObjectCount());
+		assertEquals(3, merger.getPackCount());
+		assertFalse(merger.needsLargeOffsetsChunk());
+		Iterator<PackIndexMerger.MidxMutableEntry> it = merger.bySha1Iterator();
+		assertNextEntry(it, "0000000000000000000000000000000000000001", 0, 500);
+		assertNextEntry(it, "0000000000000000000000000000000000000002", 1, 501);
+		assertNextEntry(it, "0000000000000000000000000000000000000003", 1, 13);
+		assertNextEntry(it, "0000000000000000000000000000000000000004", 2, 502);
+		assertNextEntry(it, "0000000000000000000000000000000000000005", 0, 12);
+		assertNextEntry(it, "0000000000000000000000000000000000000007", 2, 14);
+		assertNextEntry(it, "0000000000000000000000000000000000000010", 0,
+				1500);
+		assertNextEntry(it, "0000000000000000000000000000000000000012", 2,
+				1502);
+		assertNextEntry(it, "0000000000000000000000000000000000000015", 1,
+				1501);
+		assertFalse(it.hasNext());
+	}
+
+	@Test
+	public void bySha1Iterator_allDuplicates() {
+		PackIndex idxOne = indexOf(
+				oidOffset("0000000000000000000000000000000000000001", 500),
+				oidOffset("0000000000000000000000000000000000000005", 12),
+				oidOffset("0000000000000000000000000000000000000010", 1500));
+		PackIndexMerger merger = new PackIndexMerger(
+				Map.of("p1", idxOne, "p2", idxOne, "p3", idxOne));
+		assertEquals(3, merger.getUniqueObjectCount());
+		assertEquals(3, merger.getPackCount());
+		assertFalse(merger.needsLargeOffsetsChunk());
+		Iterator<PackIndexMerger.MidxMutableEntry> it = merger.bySha1Iterator();
+		assertNextEntry(it, "0000000000000000000000000000000000000001", 0, 500);
+		assertNextEntry(it, "0000000000000000000000000000000000000005", 0, 12);
+		assertNextEntry(it, "0000000000000000000000000000000000000010", 0,
+				1500);
+		assertFalse(it.hasNext());
+	}
+
+	@Test
+	public void bySha1Iterator_differentIndexSizes() {
+		PackIndex idxOne = indexOf(
+				oidOffset("0000000000000000000000000000000000000010", 1500));
+		PackIndex idxTwo = indexOf(
+				oidOffset("0000000000000000000000000000000000000002", 500),
+				oidOffset("0000000000000000000000000000000000000003", 12));
+		PackIndex idxThree = indexOf(
+				oidOffset("0000000000000000000000000000000000000004", 500),
+				oidOffset("0000000000000000000000000000000000000007", 12),
+				oidOffset("0000000000000000000000000000000000000012", 1500));
+		PackIndexMerger merger = new PackIndexMerger(
+				Map.of("p1", idxOne, "p2", idxTwo, "p3", idxThree));
+		assertEquals(6, merger.getUniqueObjectCount());
+		assertEquals(3, merger.getPackCount());
+		assertFalse(merger.needsLargeOffsetsChunk());
+		Iterator<PackIndexMerger.MidxMutableEntry> it = merger.bySha1Iterator();
+		assertNextEntry(it, "0000000000000000000000000000000000000002", 1, 500);
+		assertNextEntry(it, "0000000000000000000000000000000000000003", 1, 12);
+		assertNextEntry(it, "0000000000000000000000000000000000000004", 2, 500);
+		assertNextEntry(it, "0000000000000000000000000000000000000007", 2, 12);
+		assertNextEntry(it, "0000000000000000000000000000000000000010", 0,
+				1500);
+		assertNextEntry(it, "0000000000000000000000000000000000000012", 2,
+				1500);
+		assertFalse(it.hasNext());
+	}
+
+	@Test
+	public void merger_noIndexes() {
+		PackIndexMerger merger = new PackIndexMerger(Map.of());
+		assertEquals(0, merger.getUniqueObjectCount());
+		assertFalse(merger.needsLargeOffsetsChunk());
+		assertTrue(merger.getPackNames().isEmpty());
+		assertEquals(0, merger.getPackCount());
+		assertFalse(merger.bySha1Iterator().hasNext());
+	}
+
+	@Test
+	public void merger_emptyIndexes() {
+		PackIndexMerger merger = new PackIndexMerger(
+				Map.of("p1", indexOf(), "p2", indexOf()));
+		assertEquals(0, merger.getUniqueObjectCount());
+		assertFalse(merger.needsLargeOffsetsChunk());
+		assertEquals(2, merger.getPackNames().size());
+		assertEquals(2, merger.getPackCount());
+		assertFalse(merger.bySha1Iterator().hasNext());
+	}
+
+	@Test
+	public void bySha1Iterator_largeOffsets_needsChunk() {
+		PackIndex idx1 = indexOf(
+				oidOffset("0000000000000000000000000000000000000002", 1L << 32),
+				oidOffset("0000000000000000000000000000000000000004", 12));
+		PackIndex idx2 = indexOf(oidOffset(
+				"0000000000000000000000000000000000000003", (1L << 31) + 10));
+		PackIndexMerger merger = new PackIndexMerger(
+				Map.of("p1", idx1, "p2", idx2));
+		assertTrue(merger.needsLargeOffsetsChunk());
+		assertEquals(2, merger.getOffsetsOver31BitsCount());
+		assertEquals(3, merger.getUniqueObjectCount());
+	}
+
+	@Test
+	public void bySha1Iterator_largeOffsets_noChunk() {
+		// If no value is over 2^32-1, then we don't need large offset
+		PackIndex idx1 = indexOf(
+				oidOffset("0000000000000000000000000000000000000002",
+						(1L << 31) + 15),
+				oidOffset("0000000000000000000000000000000000000004", 12));
+		PackIndex idx2 = indexOf(oidOffset(
+				"0000000000000000000000000000000000000003", (1L << 31) + 10));
+		PackIndexMerger merger = new PackIndexMerger(
+				Map.of("p1", idx1, "p2", idx2));
+		assertFalse(merger.needsLargeOffsetsChunk());
+		assertEquals(2, merger.getOffsetsOver31BitsCount());
+		assertEquals(3, merger.getUniqueObjectCount());
+	}
+
+	private static void assertNextEntry(
+			Iterator<PackIndexMerger.MidxMutableEntry> it, String oid,
+			int packId, long offset) {
+		assertTrue(it.hasNext());
+		PackIndexMerger.MidxMutableEntry e = it.next();
+		assertEquals(oid, e.getObjectId().name());
+		assertEquals(packId, e.getPackId());
+		assertEquals(offset, e.getOffset());
+	}
+
+	private static IndexObject oidOffset(String oid, long offset) {
+		return new IndexObject(oid, offset);
+	}
+
+	private static PackIndex indexOf(IndexObject... objs) {
+		return FakeIndexFactory.indexOf(Arrays.asList(objs));
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/midx/PackIndexPeekIteratorTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/midx/PackIndexPeekIteratorTest.java
new file mode 100644
index 0000000000..917288a899
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/midx/PackIndexPeekIteratorTest.java
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2025, Google Inc.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.internal.storage.midx;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
+
+import java.util.Arrays;
+
+import org.eclipse.jgit.internal.storage.file.PackIndex;
+import org.eclipse.jgit.junit.FakeIndexFactory;
+import org.junit.Test;
+
+public class PackIndexPeekIteratorTest {
+    @Test
+    public void next() {
+        PackIndex index1 = indexOf(
+                object("0000000000000000000000000000000000000001", 500),
+                object("0000000000000000000000000000000000000003", 1500),
+                object("0000000000000000000000000000000000000005", 3000));
+        PackIndexMerger.PackIndexPeekIterator it = new PackIndexMerger.PackIndexPeekIterator(0, index1);
+        assertEquals("0000000000000000000000000000000000000001", it.next().name());
+        assertEquals("0000000000000000000000000000000000000003", it.next().name());
+        assertEquals("0000000000000000000000000000000000000005", it.next().name());
+        assertNull(it.next());
+    }
+
+    @Test
+    public void peek_doesNotAdvance() {
+        PackIndex index1 = indexOf(
+                object("0000000000000000000000000000000000000001", 500),
+                object("0000000000000000000000000000000000000003", 1500),
+                object("0000000000000000000000000000000000000005", 3000));
+        PackIndexMerger.PackIndexPeekIterator it = new PackIndexMerger.PackIndexPeekIterator(0, index1);
+        it.next();
+        assertEquals("0000000000000000000000000000000000000001", it.peek().name());
+        assertEquals("0000000000000000000000000000000000000001", it.peek().name());
+        it.next();
+        assertEquals("0000000000000000000000000000000000000003", it.peek().name());
+        assertEquals("0000000000000000000000000000000000000003", it.peek().name());
+        it.next();
+        assertEquals("0000000000000000000000000000000000000005", it.peek().name());
+        assertEquals("0000000000000000000000000000000000000005", it.peek().name());
+        it.next();
+        assertNull(it.peek());
+        assertNull(it.peek());
+    }
+
+    @Test
+    public void empty() {
+        PackIndex index1 = indexOf();
+        PackIndexMerger.PackIndexPeekIterator it = new PackIndexMerger.PackIndexPeekIterator(0, index1);
+        assertNull(it.next());
+        assertNull(it.peek());
+    }
+
+    private static PackIndex indexOf(FakeIndexFactory.IndexObject... objs) {
+        return FakeIndexFactory.indexOf(Arrays.asList(objs));
+    }
+
+    private static FakeIndexFactory.IndexObject object(String name, long offset) {
+        return new FakeIndexFactory.IndexObject(name, offset);
+    }
+}
\ No newline at end of file