PriorityQueue.downHeap computes the child index i << 1 in int, so a queue holding 2^30 or more elements can throw ArrayIndexOutOfBoundsException (when a sift-down reaches node 2^30) from updateTop, pop or insertWithOverflow and is left with one element lost and another duplicated

Finding LFV-294Area: util / PriorityQueue (sift-down; base class of HitQueue and FieldValueHitQueue)Priority: lowImpact: crashNovelty: new

Finding page for LFV-294

AI-assisted finding, confirmed by automated checks, not yet triaged by a human Lucene committer. This site files nothing upstream.

What it shows

You fill a Lucene PriorityQueue with 2^30 + 1 elements, a size its constructor accepts (any maxSize below ArrayUtil.MAX_ARRAY_LENGTH), and call updateTop, pop or insertWithOverflow; you expect the usual log(size) sift-down and the new least element back. Instead, when the sift-down reaches node 2^30, the child index i << 1 wraps to Integer.MIN_VALUE, the negative index -2147483647 passes the 'k <= size' check, and the call throws ArrayIndexOutOfBoundsException after children were already moved up, so the queue has lost the element being sifted and holds a second copy of another. A queue of 2^30 - 1 elements works; exactly 2^30 already fails for updateTop.

Expected vs actual

Files

Run it

# Lucene checkout at the tested commit, built with: ./gradlew --no-daemon assemble   (JDK 25)
LUCENE=/path/to/lucene; V=12.0.0-SNAPSHOT
CP=$LUCENE/lucene/core/build/libs/lucene-core-$V.jar
CP=$CP:$LUCENE/lucene/codecs/build/libs/lucene-codecs-$V.jar
CP=$CP:$LUCENE/lucene/test-framework/build/libs/lucene-test-framework-$V.jar
CP=$CP:randomizedtesting-runner-2.9.2.jar:junit-4.13.2.jar:hamcrest-3.0.jar   # test-framework dependencies (Maven Central)
CP=$CP:junit-platform-console-standalone-6.1.3.jar   # JUnit Platform console launcher (Maven Central)

javac -d classes-src -cp "$CP" $(find src -name '*.java')
javac -d classes-src2 -cp "$CP" $(find src2 -name '*.java')

# run 1: assertions on, seed DEADBEEF
java -ea -esa -Xmx7g --add-modules jdk.incubator.vector --enable-native-access=ALL-UNNAMED -XX:ParallelGCThreads=2 -XX:ConcGCThreads=1 -Dtests.seed=DEADBEEF \
     -cp "classes-src:$CP" org.junit.platform.console.ConsoleLauncher \
     execute --select-class org.apache.lucene.util.TestPriorityQueueDownHeapIndexOverflow
java -ea -esa -Xmx7g --add-modules jdk.incubator.vector --enable-native-access=ALL-UNNAMED -XX:ParallelGCThreads=2 -XX:ConcGCThreads=1 -Dtests.seed=DEADBEEF \
     -cp "classes-src2:$CP" org.junit.platform.console.ConsoleLauncher \
     execute --select-class org.apache.lucene.util.TestPriorityQueueDownHeapIndexOverflow

Gradle alternative: copy the test into the matching module's src/test/ tree of the checkout and run ./gradlew -p lucene/<module> test --tests <class> -Ptests.seed=<seed> (add -Ptests.asserts=false for a run without assertions).

Files shown on the finding page

Formal models and scripts this finding's part of the hunt used: priorityqueue-topdocs-merge

Feedback

Open an issue in lucene-ai-bug-hunt. Please do not open issues or pull requests in apache/lucene about this finding unless a Lucene committer agrees it should be filed.

Snapshot of 2026-11-04. AI-assisted; not yet triaged by a human Lucene committer. Feedback: open an issue in lucene-ai-bug-hunt.