Merge "Improve configuration of trusting file attributes in FileSnapshot"
diff --git a/org.eclipse.jgit.test/META-INF/MANIFEST.MF b/org.eclipse.jgit.test/META-INF/MANIFEST.MF
index 5a5dd88..af5fd1c 100644
--- a/org.eclipse.jgit.test/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit.test/META-INF/MANIFEST.MF
@@ -48,6 +48,7 @@
org.eclipse.jgit.internal.storage.file;version="[7.2.0,7.3.0)",
org.eclipse.jgit.internal.storage.io;version="[7.2.0,7.3.0)",
org.eclipse.jgit.internal.storage.memory;version="[7.2.0,7.3.0)",
+ org.eclipse.jgit.internal.storage.midx;version="[7.2.0,7.3.0)",
org.eclipse.jgit.internal.storage.pack;version="[7.2.0,7.3.0)",
org.eclipse.jgit.internal.storage.reftable;version="[7.2.0,7.3.0)",
org.eclipse.jgit.internal.transport.connectivity;version="[7.2.0,7.3.0)",
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/PackIndexTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/PackIndexTestCase.java
index 24bdc4a..1f934ac 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/PackIndexTestCase.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/PackIndexTestCase.java
@@ -13,6 +13,7 @@
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertThrows;
+import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import java.io.File;
@@ -25,6 +26,7 @@
import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.internal.storage.file.PackIndex.MutableEntry;
import org.eclipse.jgit.junit.RepositoryTestCase;
+import org.eclipse.jgit.lib.MutableObjectId;
import org.eclipse.jgit.lib.ObjectId;
import org.junit.Test;
@@ -99,6 +101,39 @@ public void testIteratorMethodsContract() {
}
}
+ @Test
+ public void testIteratorMutableEntryCompareTo() {
+ Iterator<PackIndex.MutableEntry> iterA = smallIdx.iterator();
+ Iterator<PackIndex.MutableEntry> iterB = smallIdx.iterator();
+
+ MutableEntry aEntry = iterA.next();
+ iterB.next();
+ MutableEntry bEntry = iterB.next();
+ // b is one ahead
+ assertTrue(aEntry.compareBySha1To(bEntry) < 0);
+ assertTrue(bEntry.compareBySha1To(aEntry) > 0);
+
+ // advance a, now should be equal
+ assertEquals(0, iterA.next().compareBySha1To(bEntry));
+ }
+
+ @Test
+ public void testIteratorMutableEntryCopyTo() {
+ Iterator<PackIndex.MutableEntry> it = smallIdx.iterator();
+
+ MutableObjectId firstOidCopy = new MutableObjectId();
+ MutableEntry next = it.next();
+ next.copyOidTo(firstOidCopy);
+ ObjectId firstImmutable = next.toObjectId();
+
+ MutableEntry second = it.next();
+
+ // The copy has the right value after "next"
+ assertTrue(firstImmutable.equals(firstOidCopy));
+ assertFalse("iterator has moved",
+ second.toObjectId().equals(firstImmutable));
+ }
+
/**
* Test results of iterator comparing to content of well-known (prepared)
* small index.
@@ -106,22 +141,22 @@ public void testIteratorMethodsContract() {
@Test
public void testIteratorReturnedValues1() {
Iterator<PackIndex.MutableEntry> iter = smallIdx.iterator();
- assertEquals("4b825dc642cb6eb9a060e54bf8d69288fbee4904", iter.next()
- .name());
- assertEquals("540a36d136cf413e4b064c2b0e0a4db60f77feab", iter.next()
- .name());
- assertEquals("5b6e7c66c276e7610d4a73c70ec1a1f7c1003259", iter.next()
- .name());
- assertEquals("6ff87c4664981e4397625791c8ea3bbb5f2279a3", iter.next()
- .name());
- assertEquals("82c6b885ff600be425b4ea96dee75dca255b69e7", iter.next()
- .name());
- assertEquals("902d5476fa249b7abc9d84c611577a81381f0327", iter.next()
- .name());
- assertEquals("aabf2ffaec9b497f0950352b3e582d73035c2035", iter.next()
- .name());
- assertEquals("c59759f143fb1fe21c197981df75a7ee00290799", iter.next()
- .name());
+ assertEquals("4b825dc642cb6eb9a060e54bf8d69288fbee4904",
+ iter.next().name());
+ assertEquals("540a36d136cf413e4b064c2b0e0a4db60f77feab",
+ iter.next().name());
+ assertEquals("5b6e7c66c276e7610d4a73c70ec1a1f7c1003259",
+ iter.next().name());
+ assertEquals("6ff87c4664981e4397625791c8ea3bbb5f2279a3",
+ iter.next().name());
+ assertEquals("82c6b885ff600be425b4ea96dee75dca255b69e7",
+ iter.next().name());
+ assertEquals("902d5476fa249b7abc9d84c611577a81381f0327",
+ iter.next().name());
+ assertEquals("aabf2ffaec9b497f0950352b3e582d73035c2035",
+ iter.next().name());
+ assertEquals("c59759f143fb1fe21c197981df75a7ee00290799",
+ iter.next().name());
assertFalse(iter.hasNext());
}
@@ -198,16 +233,16 @@ public void testCompareEntriesOffsetsWithGetOffsets() {
@Test
public void testIteratorReturnedValues2() {
Iterator<PackIndex.MutableEntry> iter = denseIdx.iterator();
- while (!iter.next().name().equals(
- "0a3d7772488b6b106fb62813c4d6d627918d9181")) {
+ while (!iter.next().name()
+ .equals("0a3d7772488b6b106fb62813c4d6d627918d9181")) {
// just iterating
}
- assertEquals("1004d0d7ac26fbf63050a234c9b88a46075719d3", iter.next()
- .name()); // same level-1
- assertEquals("10da5895682013006950e7da534b705252b03be6", iter.next()
- .name()); // same level-1
- assertEquals("1203b03dc816ccbb67773f28b3c19318654b0bc8", iter.next()
- .name());
+ assertEquals("1004d0d7ac26fbf63050a234c9b88a46075719d3",
+ iter.next().name()); // same level-1
+ assertEquals("10da5895682013006950e7da534b705252b03be6",
+ iter.next().name()); // same level-1
+ assertEquals("1203b03dc816ccbb67773f28b3c19318654b0bc8",
+ iter.next().name());
}
@Test
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 0000000..1d8bde0
--- /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 0000000..917288a
--- /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
diff --git a/org.eclipse.jgit/META-INF/MANIFEST.MF b/org.eclipse.jgit/META-INF/MANIFEST.MF
index 659ad85..f5cc16c 100644
--- a/org.eclipse.jgit/META-INF/MANIFEST.MF
+++ b/org.eclipse.jgit/META-INF/MANIFEST.MF
@@ -105,6 +105,7 @@
org.eclipse.jgit.pgm",
org.eclipse.jgit.internal.storage.memory;version="7.2.0";
x-friends:="org.eclipse.jgit.test",
+ org.eclipse.jgit.internal.storage.midx;version="7.2.0",
org.eclipse.jgit.internal.storage.pack;version="7.2.0";
x-friends:="org.eclipse.jgit.junit,
org.eclipse.jgit.test,
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java
index 7189ce2..b3e4efb 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java
@@ -286,7 +286,7 @@ long findCRC32(AnyObjectId objId)
* the index cannot be read.
*/
void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
- int matchLimit) throws IOException;
+ int matchLimit) throws IOException;
/**
* Get pack checksum
@@ -304,6 +304,7 @@ void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
class MutableEntry {
/** Buffer of the ObjectId visited by the EntriesIterator. */
final MutableObjectId idBuffer = new MutableObjectId();
+
/** Offset into the packfile of the current object. */
long offset;
@@ -345,6 +346,34 @@ public MutableEntry cloneEntry() {
r.offset = offset;
return r;
}
+
+ /**
+ * Similar to {@link Comparable#compareTo(Object)}, using only the
+ * object id in the entry.
+ *
+ * @param other
+ * Another mutable entry (probably from another index)
+ *
+ * @return a negative integer, zero, or a positive integer as this
+ * object is less than, equal to, or greater than the specified
+ * object.
+ */
+ public int compareBySha1To(MutableEntry other) {
+ return idBuffer.compareTo(other.idBuffer);
+ }
+
+ /**
+ * Copy the current ObjectId to dest
+ * <p>
+ * Like {@link #toObjectId()}, but reusing the destination instead of
+ * creating a new ObjectId instance.
+ *
+ * @param dest
+ * destination for the object id
+ */
+ public void copyOidTo(MutableObjectId dest) {
+ dest.fromObjectId(idBuffer);
+ }
}
/**
@@ -368,7 +397,6 @@ protected EntriesIterator(long objectCount) {
this.objectCount = objectCount;
}
-
@Override
public boolean hasNext() {
return returnedNumber < objectCount;
@@ -393,7 +421,6 @@ public MutableEntry next() {
*/
protected abstract void readNext();
-
/**
* Copies to the entry an {@link ObjectId} from the int buffer and
* position idx
@@ -423,7 +450,8 @@ protected void setIdBuffer(byte[] raw, int idx) {
/**
* Sets the {@code offset} to the entry
*
- * @param offset the offset in the pack file
+ * @param offset
+ * the offset in the pack file
*/
protected void setOffset(long offset) {
entry.offset = offset;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/PackIndexMerger.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/PackIndexMerger.java
new file mode 100644
index 0000000..89814af
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/PackIndexMerger.java
@@ -0,0 +1,337 @@
+/*
+ * 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 java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.stream.Collectors;
+
+import org.eclipse.jgit.internal.storage.file.PackIndex;
+import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.MutableObjectId;
+
+/**
+ * Collect the stats and offers an iterator over the union of n-pack indexes.
+ * <p>
+ * The multipack index is a list of (sha1, packid, offset) ordered by sha1. We
+ * can build it from the individual pack indexes (sha1, offset) ordered by sha1,
+ * with a simple merge ignoring duplicates.
+ * <p>
+ * This class encapsulates the merging logic and precalculates the stats that
+ * the index needs (like total count of objects). To limit memory consumption,
+ * it does the merge as it goes during the iteration and iterators use mutable
+ * entries. The stats of the combined index are calculated in an iteration at
+ * construction time.
+ */
+class PackIndexMerger {
+
+ private static final int LIMIT_31_BITS = (1 << 31) - 1;
+
+ private static final long LIMIT_32_BITS = (1L << 32) - 1;
+
+ /**
+ * Object returned by the iterator.
+ * <p>
+ * The iterator returns (on each next()) the same instance with different
+ * values, to avoid allocating many short-lived objects. Callers should not
+ * keep a reference to that returned value.
+ */
+ static class MidxMutableEntry {
+ // The object id
+ private final MutableObjectId oid = new MutableObjectId();
+
+ // Position of the pack in the ordered list of pack in this merger
+ private int packId;
+
+ // Offset in its pack
+ private long offset;
+
+ public AnyObjectId getObjectId() {
+ return oid;
+ }
+
+ public int getPackId() {
+ return packId;
+ }
+
+ public long getOffset() {
+ return offset;
+ }
+
+ /**
+ * Copy values from another mutable entry
+ *
+ * @param packId
+ * packId
+ * @param other
+ * another mutable entry
+ */
+ private void fill(int packId, PackIndex.MutableEntry other) {
+ other.copyOidTo(oid);
+ this.packId = packId;
+ this.offset = other.getOffset();
+ }
+ }
+
+ private final List<String> packNames;
+
+ private final List<PackIndex> indexes;
+
+ private final boolean needsLargeOffsetsChunk;
+
+ private final int offsetsOver31BitsCount;
+
+ private final int uniqueObjectCount;
+
+ PackIndexMerger(Map<String, PackIndex> packs) {
+ this.packNames = packs.keySet().stream().sorted()
+ .collect(Collectors.toUnmodifiableList());
+
+ this.indexes = packNames.stream().map(packs::get)
+ .collect(Collectors.toUnmodifiableList());
+
+ // Iterate for duplicates
+ int objectCount = 0;
+ boolean hasLargeOffsets = false;
+ int over31bits = 0;
+ MutableObjectId lastSeen = new MutableObjectId();
+ MultiIndexIterator it = new MultiIndexIterator(indexes);
+ while (it.hasNext()) {
+ MidxMutableEntry entry = it.next();
+ if (lastSeen.equals(entry.oid)) {
+ continue;
+ }
+ // If there is at least one offset value larger than 2^32-1, then
+ // the large offset chunk must exist, and offsets larger than
+ // 2^31-1 must be stored in it instead
+ if (entry.offset > LIMIT_32_BITS) {
+ hasLargeOffsets = true;
+ }
+ if (entry.offset > LIMIT_31_BITS) {
+ over31bits++;
+ }
+
+ lastSeen.fromObjectId(entry.oid);
+ objectCount++;
+ }
+ uniqueObjectCount = objectCount;
+ offsetsOver31BitsCount = over31bits;
+ needsLargeOffsetsChunk = hasLargeOffsets;
+ }
+
+ /**
+ * Object count of the merged index (i.e. without duplicates)
+ *
+ * @return object count of the merged index
+ */
+ int getUniqueObjectCount() {
+ return uniqueObjectCount;
+ }
+
+ /**
+ * If any object in any of the indexes has an offset over 2^32-1
+ *
+ * @return true if there is any object with offset > 2^32 -1
+ */
+ boolean needsLargeOffsetsChunk() {
+ return needsLargeOffsetsChunk;
+ }
+
+ /**
+ * How many object have offsets over 2^31-1
+ * <p>
+ * Per multipack index spec, IF there is large offset chunk, all this
+ * offsets should be there.
+ *
+ * @return number of objects with offsets over 2^31-1
+ */
+ int getOffsetsOver31BitsCount() {
+ return offsetsOver31BitsCount;
+ }
+
+ /**
+ * List of pack names in alphabetical order.
+ * <p>
+ * Order matters: In case of duplicates, the multipack index prefers the
+ * first package with it. This is in the same order we are using to
+ * prioritize duplicates.
+ *
+ * @return List of pack names, in the order used by the merge.
+ */
+ List<String> getPackNames() {
+ return packNames;
+ }
+
+ /**
+ * How many packs are being merged
+ *
+ * @return count of packs merged
+ */
+ int getPackCount() {
+ return packNames.size();
+ }
+
+ /**
+ * Iterator over the merged indexes in sha1 order without duplicates
+ * <p>
+ * The returned entry in the iterator is mutable, callers should NOT keep a
+ * reference to it.
+ *
+ * @return an iterator in sha1 order without duplicates.
+ */
+ Iterator<MidxMutableEntry> bySha1Iterator() {
+ return new DedupMultiIndexIterator(new MultiIndexIterator(indexes),
+ getUniqueObjectCount());
+ }
+
+ /**
+ * For testing. Iterate all entries, not skipping duplicates (stable order)
+ *
+ * @return an iterator of all objects in sha1 order, including duplicates.
+ */
+ Iterator<MidxMutableEntry> rawIterator() {
+ return new MultiIndexIterator(indexes);
+ }
+
+ /**
+ * Iterator over n-indexes in ObjectId order.
+ * <p>
+ * It returns duplicates if the same object id is in different indexes. Wrap
+ * it with {@link DedupMultiIndexIterator (Iterator, int)} to avoid
+ * duplicates.
+ */
+ private static final class MultiIndexIterator
+ implements Iterator<MidxMutableEntry> {
+
+ private final List<PackIndexPeekIterator> indexIterators;
+
+ private final MidxMutableEntry mutableEntry = new MidxMutableEntry();
+
+ MultiIndexIterator(List<PackIndex> indexes) {
+ this.indexIterators = new ArrayList<>(indexes.size());
+ for (int i = 0; i < indexes.size(); i++) {
+ PackIndexPeekIterator it = new PackIndexPeekIterator(i,
+ indexes.get(i));
+ // Position in the first element
+ if (it.next() != null) {
+ indexIterators.add(it);
+ }
+ }
+ }
+
+ @Override
+ public boolean hasNext() {
+ return !indexIterators.isEmpty();
+ }
+
+ @Override
+ public MidxMutableEntry next() {
+ PackIndexPeekIterator winner = null;
+ for (int index = 0; index < indexIterators.size(); index++) {
+ PackIndexPeekIterator current = indexIterators.get(index);
+ if (winner == null
+ || current.peek().compareBySha1To(winner.peek()) < 0) {
+ winner = current;
+ }
+ }
+
+ if (winner == null) {
+ throw new NoSuchElementException();
+ }
+
+ mutableEntry.fill(winner.getPackId(), winner.peek());
+ if (winner.next() == null) {
+ indexIterators.remove(winner);
+ };
+ return mutableEntry;
+ }
+ }
+
+ private static class DedupMultiIndexIterator
+ implements Iterator<MidxMutableEntry> {
+ private final MultiIndexIterator src;
+
+ private int remaining;
+
+ private final MutableObjectId lastOid = new MutableObjectId();
+
+ DedupMultiIndexIterator(MultiIndexIterator src, int totalCount) {
+ this.src = src;
+ this.remaining = totalCount;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return remaining > 0;
+ }
+
+ @Override
+ public MidxMutableEntry next() {
+ MidxMutableEntry next = src.next();
+ while (next != null && lastOid.equals(next.oid)) {
+ next = src.next();
+ }
+
+ if (next == null) {
+ throw new NoSuchElementException();
+ }
+
+ lastOid.fromObjectId(next.oid);
+ remaining--;
+ return next;
+ }
+ }
+
+ /**
+ * Convenience around the PackIndex iterator to read the current value
+ * multiple times without consuming it.
+ * <p>
+ * This is used to merge indexes in the multipack index, where we need to
+ * compare the current value between indexes multiple times to find the
+ * next.
+ * <p>
+ * We could also implement this keeping the position (int) and
+ * MutableEntry#getObjectId, but that would create an ObjectId per entry.
+ * This implementation reuses the MutableEntry and avoid instantiations.
+ */
+ // Visible for testing
+ static class PackIndexPeekIterator {
+ private final Iterator<PackIndex.MutableEntry> it;
+
+ private final int packId;
+
+ PackIndex.MutableEntry current;
+
+ PackIndexPeekIterator(int packId, PackIndex index) {
+ it = index.iterator();
+ this.packId = packId;
+ }
+
+ PackIndex.MutableEntry next() {
+ if (it.hasNext()) {
+ current = it.next();
+ } else {
+ current = null;
+ }
+ return current;
+ }
+
+ PackIndex.MutableEntry peek() {
+ return current;
+ }
+
+ int getPackId() {
+ return packId;
+ }
+ }
+}
