diff options
| author | Jonathan Tan <jonathantanmy@google.com> | 2023-05-08 13:55:40 -0700 |
|---|---|---|
| committer | Jonathan Tan <jonathantanmy@google.com> | 2023-05-23 13:57:32 -0700 |
| commit | 6b3b2b33a528458aa23428db7d43655aa0d883d5 (patch) | |
| tree | 900530bace22ab191e7c12c9af1ae71fc47ec75b | |
| parent | 4562e79e234696ae3e1601db9bf8b73a1ef7edf8 (diff) | |
| download | jgit-6b3b2b33a528458aa23428db7d43655aa0d883d5.tar.gz jgit-6b3b2b33a528458aa23428db7d43655aa0d883d5.zip | |
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>
2 files changed, 30 insertions, 2 deletions
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 0000000000..b533d5c985 --- /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 b0df46732e..22b4011f9f 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 @@ class GraphObjectIndex { 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 @@ class GraphObjectIndex { } else { low = mid + 1; } - } while (low < high); + } return -1; } |