GraphObjectIndex: fix search in findGraphPosition
In findGraphPosition, when there is no object whose OID starts with
the first byte of the sought OID, low equals high. This violates an
invariant of the loop, and when the sought OID is lexicographically
greater than every other OID in the repository, causes an
ArrayIndexOutOfBoundsException (because we're trying to read outside the
list of OIDs).
Therefore, check the "low < high" condition at the start of the loop,
not only after the first iteration.
Change-Id: Ic8ac198c151bd161c4996b9e7cb6e6660f151733
Helped-by: Ivan Frade <ifrade@google.com>
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndexTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndexTest.java
new file mode 100644
index 0000000..b533d5c
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndexTest.java
@@ -0,0 +1,28 @@
+/*
+ * Copyright (C) 2023, Google LLC
+ *
+ * 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.commitgraph;
+
+import org.eclipse.jgit.lib.ObjectId;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+
+public class GraphObjectIndexTest {
+
+ @Test
+ public void findGraphPosition_noObjInBucket() throws CommitGraphFormatException {
+ GraphObjectIndex idx = new GraphObjectIndex(100,
+ new byte[256 * 4], new byte[] {});
+ int graphPosition = idx.findGraphPosition(
+ ObjectId.fromString("731dfd4c5eb6f88b98e983b9b0551b3562a0c46c"));
+ assertEquals(-1, graphPosition);
+ }
+
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndex.java
index b0df467..22b4011 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndex.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/commitgraph/GraphObjectIndex.java
@@ -80,7 +80,7 @@ int findGraphPosition(AnyObjectId id) {
if (levelOne > 0) {
low = fanoutTable[levelOne - 1];
}
- do {
+ while (low < high) {
int mid = (low + high) >>> 1;
int pos = objIdOffset(mid);
int cmp = id.compareTo(oidLookup, pos);
@@ -91,7 +91,7 @@ int findGraphPosition(AnyObjectId id) {
} else {
low = mid + 1;
}
- } while (low < high);
+ }
return -1;
}
