IntroSorter's heap-sort fallback overflows int and asks for a negative slot when 2*to - from > 2^31

IntroSorter (behind ArrayUtil.introSort and CollectionUtil.introSort) runs quicksort and falls back to Sorter.heapSort(from, to) once its depth budget of 2 * log2(n) levels is used up. Heap sort's siftDown finds a node's left child with heapChild(from, i) = ((i - from) << 1) + 1 + from, computed in int, and loops while leftChild < to. For a node with no child the exact index can be 2^31 or more; it then wraps to a negative int, passes leftChild < to, and compare(i, leftChild) runs with that negative slot. For array-valid slots (0 <= from <= to) this can happen exactly when 2*to - from > 2^31: more than 2^30 = 1,073,741,824 elements from index 0, or a slice that ends near ArrayUtil.MAX_ARRAY_LENGTH. It also needs an element order that uses up the quicksort budget; the recorded random controls did not. Array-backed sorts throw ArrayIndexOutOfBoundsException at the first out-of-slice compare, before any out-of-slice swap; a custom Sorter subclass is handed the negative slot. It is never a silent mis-sort through Lucene's array sorters. The code dates from LUCENE-4946 (4.4.0, 2013), and an overflow-safe loop guard fixes it. No in-tree Lucene caller was shown to reach it.

1. IntroSorter.sort(from, to) calls sort(from, to, 2 * MathUtil.log(to - from, 2)) (IntroSorter.java:44). When --maxDepth < 0 it calls heapSort(from, to) on the sub-range left at that point (:59-61, "Max recursion depth exceeded: fallback to heap sort").
2. heapSort (Sorter.java:259-268) builds the heap with heapify (:270-274), then sifts each extracted element down. siftDown loops for (int leftChild = heapChild(from, i); leftChild < to; leftChild = heapChild(from, i)) (:277) and calls compare(i, leftChild) first (:279).
3. heapChild(from, i) is ((i - from) << 1) + 1 + from in int (:300-302). The largest node, to - 1, gets the exact child 2*to - from - 1, so some node's child index reaches 2^31 exactly when 2*to - from > 2^31 (a Z3 proof). For array-valid slots (0 <= from <= i < to <= Integer.MAX_VALUE, the model's precondition; checkRange rejects only to < from) the exact value is below 2^32, so the wrapped int is always negative, and every negative value passes leftChild < to. Whether siftDown reaches such a leaf depends on the data.
4. ArrayIntroSorter.compare reads arr[j] (ArrayIntroSorter.java:40-42) and throws ArrayIndexOutOfBoundsException; the default IntroSorter.compare calls setPivot(i) and comparePivot(j) (IntroSorter.java:155-158), so a custom sorter is handed the negative slot. This happens before any out-of-slice swap; earlier in-slice swaps have run, so the slice is left partly reordered.
5. On this path the other index arithmetic is overflow-safe: heapParent uses >>> 1 (Sorter.java:296-298; Z3 Q2 UNSAT) and IntroSorter's pivot-sampling indices, including the midpoint (from + last) >>> 1 (IntroSorter.java:67), stay in the slice (Q3, Q3b UNSAT). Here only heapChild's << 1 wraps. Not all of the sorters' index arithmetic is safe: the same Z3 sweep found that Sorter.upper2's t += delta << 1 (Sorter.java:173, used only by TimSorter's merge) can wrap (Q4 SAT, not executed), and insertionSort's from + 1 (Sorter.java:241) wraps for the empty range [Integer.MAX_VALUE, Integer.MAX_VALUE). Both are separate sites, not part of this bug.

The minimal test sorts 60 values at slots [2147483571, 2147483631), the last 60 slots of an array of length MAX_ARRAY_LENGTH = 2,147,483,631 (16-byte array header). A trace of the same input shows heapSort(2147483604, 2147483631) (27 slots); heapify walks a value down to the last slot, 2,147,483,630 (offset 26, a leaf), and heapChild gives 2,147,483,604 + 53 = 2,147,483,657, which wraps to -2,147,483,639. With a 24-byte header (-XX:-UseCompressedOops) the slice is [2147483563, 2147483623) and the bad slot -2,147,483,647. On a real Integer[2147483631] with a 1,000-value adversarial tail, ArrayUtil.introSort throws Index -2147482757 out of bounds for length 2147483631. Random values in the same slice sort without reaching heap sort.

• Who is hit. Application code that sorts with ArrayUtil.introSort (ArrayUtil.java:509-520), CollectionUtil.introSort (CollectionUtil.java:133, by reading) or its own IntroSorter subclass. These classes are @lucene.internal but public, so downstream code can call them.
• Default vs opt-in. The default code path of the sorter; no setting. -ea and -da behave the same.
• Scale. Both (a) 2*to - from > 2^31 (more than 2^30 elements from 0, or a slice ending near MAX_ARRAY_LENGTH, about 8 GiB of references) and (b) an order that exhausts the 2*log2(n) budget (about 60 levels for a billion elements). The from-0 case was shown only by calling heapSort directly on virtual data; it would need an adversarial input of about 10^9 elements end to end.
• Lucene's own size domain. DocValuesFieldUpdates sorts up to Integer.MAX_VALUE buffered entries with an IntroSorter (index/DocValuesFieldUpdates.java:297-337, :376-378), so sizes above 2^30 are in scope for IntroSorter; reaching the fallback there was not executed and is not claimed.
• Effect. One sort ends with an exception (or a custom sorter sees a negative slot). No hang, no wrong results through Lucene's array sorters, no index data touched.

The 60 values are a fixed permutation of 0..59, computed once with McIlroy's quicksort adversary ("A Killer Adversary for Quicksort", 1999) run through IntroSorter at slots [0, 60), so the sort uses up its depth budget; frozen, they replay the same comparisons with a plain int comparator. 60 is the smallest size of such an adversary input (sizes 17 to 300 were searched) that fails with both a 16- and a 24-byte array header; the simple orders tried (ascending, descending, organ pipe, sawtooth and others) produced no slot outside the slice at this position up to n = 4,096. The test asserts only that no slot outside [from, to) is requested, not sortedness. The slice ends at MAX_ARRAY_LENGTH, not Integer.MAX_VALUE, so the arithmetic is exactly that of ArrayUtil.introSort(a, from, to) on a real maximum-length array; the same failure on such a real array needs about 12 GB of heap and is evidence, not the proposed test.

As the regression test: the same test, for example as a new method in TestIntroSorter.

cp TestIntroSorterHeapSortAtArrayEnd.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.TestIntroSorterHeapSortAtArrayEnd -Ptests.seed=DEADBEEF
# assertions off: add -Ptests.asserts=false (same result)

# gradle, main 645d4fe14a20, seed DEADBEEF (assertions on; the same with -Ptests.asserts=false)
TestIntroSorterHeapSortAtArrayEnd > testHeapSortFallbackStaysInSlice FAILED
    java.lang.AssertionError: slot -2147483639 is outside [2147483571, 2147483631)
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:9A0DA62F0AC7FEFD]:0)
        at org.apache.lucene.util.TestIntroSorterHeapSortAtArrayEnd$1.value(TestIntroSorterHeapSortAtArrayEnd.java:36)
        at org.apache.lucene.util.TestIntroSorterHeapSortAtArrayEnd$1.comparePivot(TestIntroSorterHeapSortAtArrayEnd.java:48)
        at org.apache.lucene.util.IntroSorter.compare(IntroSorter.java:157)
        at org.apache.lucene.util.Sorter.siftDown(Sorter.java:279)
        at org.apache.lucene.util.Sorter.heapify(Sorter.java:272)
        at org.apache.lucene.util.Sorter.heapSort(Sorter.java:263)
        at org.apache.lucene.util.IntroSorter.sort(IntroSorter.java:61)
        at org.apache.lucene.util.IntroSorter.sort(IntroSorter.java:44)
        at org.apache.lucene.util.TestIntroSorterHeapSortAtArrayEnd.testHeapSortFallbackStaysInSlice(TestIntroSorterHeapSortAtArrayEnd.java:57)

# scratch trace of the same input (abridged): the heap-sort sub-range and the wrapped child
heapSort(2147483604, 2147483631) size=27
compare(i=2147483630, leftChild=-2147483639)  exact child = 2147483604 + 2*26 + 1 = 2147483657 > 2147483647

# -XX:-UseCompressedOops (24-byte array header, MAX_ARRAY_LENGTH = 2147483623)
java.lang.AssertionError: slot -2147483647 is outside [2147483563, 2147483623)

# ArrayUtil.introSort on a real Integer[2147483631], adversarial last 1,000 values (-Xmx12g, -da; main ea57360912ed and 645d4fe14a20, and 10.5.2)
java.lang.ArrayIndexOutOfBoundsException: Index -2147482757 out of bounds for length 2147483631
        at org.apache.lucene.util.ArrayIntroSorter.compare(ArrayIntroSorter.java:41)
        at org.apache.lucene.util.Sorter.siftDown(Sorter.java:279)
        ...
        at org.apache.lucene.util.ArrayUtil.introSort(ArrayUtil.java:519)    (ArrayUtil.java:520 on 10.5.2)

# with either fix: the test passes (assertions on and off for the loop guard)

• Contract. Sorter.sort sorts "the slice which starts at from (inclusive) and ends at to (exclusive)" (Sorter.java:75-79); heapSort sorts "items between from inclusive and to exclusive" and "is used as a fall-back by IntroSorter" (:254-258); checkRange rejects only to < from (:81-86). ArrayUtil.introSort "Sorts the given array slice" with no size limit (ArrayUtil.java:509-520); MAX_ARRAY_LENGTH is the documented maximum (:32-34). No javadoc, CHANGES.txt, MIGRATE.md text or test sets a 2^30 limit.
• Tests. Upstream tests use small offsets and lengths, so the heap path at large indices is untested, not specified. TestArrayUtil.testQuickToHeapSortFallback (TestArrayUtil.java:168-178) is named for the fallback (its comment dates it to LUCENE-3054 and the old merge-sort fallback), but its input, createSparseRandomArray(40000) (:159-166), holds only 0s and 1s and does not reach heapSort on main: a fact-check probe counted 0 of 6,000 such arrays reaching it.
• Purpose of the fallback. The IntroSorter javadoc (IntroSorter.java:19-25), and the LUCENE-7097 description (#8152, by Mike McCandless): introsort "detects when an adversary is at work and cuts over to heapsort".
• Precedent. LUCENE-6293 (#7355), an AIOOBE in TimSorter on a huge, specially patterned input, was fixed although its author (Adrien Grand) called it "rather unlikely to happen in practice". In a 2019 IntroSelector review (lucene-solr PR #966) he wrote that index additions "can overflow on large arrays ... This is a famous bug".

The strongest case (an independent reviewer from another model family, OpenAI GPT-5.6; the intended-behaviour checker; the adjudication): every class involved is @lucene.internal ("APIs in this package are primarily internal and may change between releases"); the first test called the package-private heapSort; the trigger is extreme in size and adversarial in order; no in-tree caller reaches it; and in the 2013 LUCENE-4946 review (#6010) Uwe Schindler wrote "The overflow issue is no real issue as the meximum array size is limited, too" (sic).

Why it fails: @lucene.internal marks API stability, not a size cap or a correctness waiver; the minimal test uses only the public sort and protected hooks, and ArrayUtil.introSort fails on a real legal array; the 2013 remark answered Dawid Weiss's point that an exclusive end index "would overflow into negative values" when sorting a full array, the to bound at 2^31, while heapChild already wraps from 2^30 elements on and was never discussed; and adversarial orders are what the fallback is for. These limit severity, not validity, and they do limit it: the trigger is remote (an array of about 8 GiB of references with a 12 GiB heap, or about 10^9 elements, in an order built to defeat quicksort), and @lucene.internal supports a low priority. The cross-model reviewer rated the works-as-designed case weak; the fact check's cross-model reviewer rated it moderate: enough for low priority, not for "by design".

Two equivalent fixes; both were run through gradle in a scratch worktree of 645d4fe14a20.

With k = i - from and n = to - from, a left child exists iff 2k + 1 < n iff k < floor(n / 2). Inside the loop heapChild is then at most to - 1 and rightChild at most to, so neither can overflow. It is the guard java.util.PriorityQueue uses (int half = n >>> 1; // loop while a non-leaf, while (k < half)).

   void siftDown(int i, int from, int to) {
-    for (int leftChild = heapChild(from, i); leftChild < to; leftChild = heapChild(from, i)) {
+    // Loop while i has a left child. Unlike heapChild(from, i) < to, this test cannot overflow.
+    while (i - from < (to - from) >>> 1) {
+      final int leftChild = heapChild(from, i);
       final int rightChild = leftChild + 1;

Trade-offs

No API or format change, and the same comparisons and swaps as today for every slice that does not overflow. The loop test compares i - from with (to - from) >>> 1 (loop-invariant) instead of comparing heapChild(from, i) with to; heapChild is still computed inside the loop, so each step adds one subtraction. Performance was not measured, and this is the cold fallback path.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20: without the fix the repro fails with assertions on and off.
• With the fix it passes with assertions on and off (-Ptests.asserts=false).
• Closest suites, the core util sorter and selector tests (TestIntroSorter, TestArrayUtil, TestCollectionUtil, TestInPlaceMergeSorter, TestTimSorter, TestMSBRadixSorter, TestStableMSBRadixSorter, TestStringSorter, TestIntroSelector): 9 classes, 74 tests, 0 failures.
• ./gradlew :lucene:core:check -x test (google-java-format, ecj lint, forbidden APIs) passes with the repro test in place. The full test suite was not run.
• Earlier, the same guard written as a for loop, shadowed into the stock jars, passed the finder's test, a separate public-API probe and the minimal test with assertions on and off.

Keeps siftDown as is.

   static int heapChild(int from, int i) {
-    return ((i - from) << 1) + 1 + from;
+    // The exact index can exceed Integer.MAX_VALUE; saturate, since any value >= to means no child.
+    return (int) Math.min(((long) (i - from) << 1) + 1 + from, Integer.MAX_VALUE);
   }

Trade-offs

Correct because to <= Integer.MAX_VALUE, so a saturated value always fails leftChild < to. One long shift and a min per step; slightly less direct than the loop guard.

What the checks validated

Gradle in the same scratch worktree: the repro, TestIntroSorter and TestArrayUtil pass with assertions on (3 classes, 29 tests, 0 failures). With assertions off, the minimal test passes with this fix standalone (fact check). The other suites and the static checks were not run for this option. The independent reproducer validated a close variant (the loop computing the child in long) on its 11 tests and on the real Integer[MAX_ARRAY_LENGTH] run.

Reject slices with 2*to - from > 2^31 in checkRange, or document the limit.

Trade-offs

Rejects legal slices that sort fine with ordinary data; Math.multiplyExact would likewise turn the bad slot into an ArithmeticException and still fail a legal sort.

Method: formal (SMT solving). In the hunt unit on sorters and selectors, the finder modelled the int index arithmetic of Sorter, IntroSorter and their helpers as 32-bit bit-vectors with exact Java wrap-around and asked Z3: Q1 (can heapChild wrap inside siftDown for a legal slice?) SAT; Q1b, the minimal to for from = 0: 1,073,741,825; Q1c, a 2-slot slice at the top of the range; Q1d, the exact condition 2*to - from > 2^31 (negation UNSAT); Q1e, safe for to <= 2^30 (UNSAT). heapParent and IntroSorter's pivot-sampling indices were proved to stay in range (Q2, Q3, Q3b UNSAT); the same sweep found a possible wrap in TimSorter's Sorter.upper2 (Q4 SAT; not executed; a separate site). The unit was chosen by area (the sorters' index arithmetic), not with this bug in mind. A same-package JUnit that calls heapSort at slots [MAX - 1000, MAX) then failed on the stock build; an independent reproducer built the public-API path and the real-array run with McIlroy's adversary, and the test was later cut to the 60-value one shown here.