TimSorter overflows its 49-entry run stack on a legal input of 1,093,938,049 elements, because it checks only the top three runs

Lucene's TimSorter keeps the sorted stretches (runs) it has found but not yet merged on a stack of 49 entries (runEnds has 1 + STACKSIZE = 50 slots, TimSorter.java:45, :62). The stack stays that small only if every run on it is longer than the two above it together; ensureInvariants (:127-153) checks that only for the top three runs, so a merge can break the rule one level deeper without anyone noticing. In 2015 LUCENE-6293 (#7355) met this flaw and raised the stack from 40 to 49 entries; in 2018 Auger, Jugé, Nicaud and Pivoteau showed for Java's identical check that such a bound still fails, and OpenJDK fixed its TimSort in JDK 11 (JDK-8203864) by also checking the fourth run. Lucene's TimSorter never got that check.

A legal input of 1,093,938,049 elements in 1,061 runs (every run but the one-element last run is at least 38, above minRun(n) = 33, so sort() detects exactly these runs; the lengths were solved for with a linear program) fills all 49 entries, and the 1,061st push throws ArrayIndexOutOfBoundsException: Index 50 out of bounds for length 50 at TimSorter.pushRunLen(TimSorter.java:98). It is reached through the Java-public CollectionUtil.timSort and ArrayUtil.timSort (methods of @lucene.internal classes), any TimSorter subclass, and index sorting, which is supported public API: IndexWriterConfig.setIndexSort plus IndexWriter.commit() on a 1,093,938,049-document in-memory segment (the writer is then closed and the buffered documents are lost) and SortingCodecReader.wrap on a segment that large, both run with a deliberately extreme setup. A plain sort leaves its data unsorted but still a permutation of the input. Every release from 5.1.0 to 10.6.0 and main is affected; the one-line fourth-run check fixes it.

static final int STACKSIZE = 49; // depends on MINRUN                       // TimSorter.java:45
runEnds = new int[1 + STACKSIZE];                                           // :62, 50 slots, up to 49 runs

void pushRunLen(int len) {                                                  // :97
  runEnds[stackSize + 1] = runEnds[stackSize] + len;                        // :98, no bound check
  ++stackSize;
}

void ensureInvariants() {                                                   // :127
  while (stackSize > 1) {
    final int runLen0 = runLen(0);                                          // top run
    final int runLen1 = runLen(1);
    if (stackSize > 2) {
      final int runLen2 = runLen(2);
      if (runLen2 <= runLen1 + runLen0) {                                   // :135, top three runs only
        if (runLen2 < runLen0) { mergeAt(1); } else { mergeAt(0); }
        continue;
      }
    }
    if (runLen1 <= runLen0) { mergeAt(0); continue; }                       // :146
    break;
  }
}

// sort(from, to), :202-205
do {
  ensureInvariants();                                                       // :203
  pushRunLen(nextRun());                                                    // :204
} while (runEnd(0) < to);

nextRun() (:103-125) takes the next maximal non-descending stretch (or a strictly descending one, reversed) and extends it to at least minRun elements with a binary sort; minRun(length) is 32 to 64 (:67-78).

TimSort wants every run on the stack to be longer than the two runs above it together, and longer than the one directly above it. Then lengths grow at least like Fibonacci numbers from the top down; with runs of at least 32 elements, 40 entries already reach Integer.MAX_VALUE. The stack was sized at 40 on that basis in 2013, and LUCENE-6293 (2015) raised it to 49 after the first counterexample to the three-run check, keeping the check. For this input's n and minRun(n) = 33 the rule would allow at most 35 runs (35 such runs hold at least 836,296,060 elements; 36 would need 1,353,155,492, more than n), the bound the diagram draws.

1. Stack, bottom to top: 1,200 | 800 | 250 | 200. Every rule holds: 1,200 > 800 + 250, 800 > 250 + 200, 250 > 200.
2. A run of 300 is pushed. The top three: 250 <= 200 + 300, and 250 < 300, so 250 and 200 merge (mergeAt(1)): 1,200 | 800 | 450 | 300.
3. The top three again: 800 > 450 + 300 and 450 > 300, so the loop stops.
4. One level deeper the rule is now broken: 1,200 < 800 + 450 = 1,250, and nothing checks it again. With the fourth-run check, step 3 sees 1,200 <= 800 + 450 and keeps merging.

The study kept the merge decisions of the published Java crash sequence (Auger et al., ESA 2018) fixed and re-solved its run lengths as a linear program so that every run is at least minRun(n); 17 such sequences were found, from 1,093,938,049 to 1,719,699,526 elements; the three run on the real jar (1,093,938,049, 1,285,317,058 and 1,719,699,526) all crash it. With the smallest, before the 1,061st push the stack holds 49 runs, from 299,699,572 elements at the bottom down to 38 at the top, and the rule is broken at 32 of its levels, for example 299,699,572 < 227,937,415 + 113,968,730 at the bottom (computed with the study's mirror of ensureInvariants; the diagram's probe, which records the real TimSorter's stack, shows the same 49 runs). The push then writes runEnds[50] and throws.

Lucene's larger minRun (32 to 64; the JDK uses 16 to 32) does not protect it: merge decisions depend only on ratios of run lengths, this pattern needs n/minRun of about 2^24.54, and for n between 2^30 and 2^31 Lucene allows up to 2^25. That is also why no input below 2^30 elements is known; smaller inputs with other patterns were not searched.

• Flush. IndexingChain.flush calls maybeSortSegment first (IndexingChain.java:305), which calls Sorter.sortAndLeaveUnpacked (:297); that builds a doc comparator with a doc-ID tie-break (index/Sorter.java:225-238) and sorts all maxDoc doc IDs with DocValueSorter extends TimSorter (index/Sorter.java:85, :132-154). DocumentsWriterPerThread.flush turns any exception into an aborting one and fires a tragic event (DocumentsWriterPerThread.java:585-602).
• Re-sort. SortingCodecReader.wrap(reader, sort) calls new Sorter(sort).sort(reader) (SortingCodecReader.java:445-446), the same path. The sort is skipped only when the segment is already sorted (index/Sorter.java:133-143).

• Who. Callers of CollectionUtil.timSort and ArrayUtil.timSort (public methods of @lucene.internal classes) or of a TimSorter subclass, on 1,093,938,049 or more elements in a run pattern like this one; and applications that use index sorting, the supported public route, on segments of that many documents. FreqProxTermsWriter's DocOffsetSorter (postings of index-sorted segments) is another in-tree TimSorter subclass; it was not assessed.
• Default vs opt-in. The utility path needs no setting. Index sorting is opt-in (IndexWriterConfig.setIndexSort).
• Scale. 1,093,938,049 elements, the smallest overflowing input the study found: below Integer.MAX_VALUE and below IndexWriter.MAX_DOCS (IndexWriter.java:208). The executed index routes were deliberately extreme: NoMergePolicy, a 1024 MB RAM buffer, one reused document holding only the sort field, a single segment of 1,093,938,049 documents, a 16 GB heap and about 5 minutes each. With real documents the per-thread hard RAM limit (default 1945 MB, IndexWriterConfig.java:93) makes a single flushed segment that large much less likely. The re-sort route is not bounded by that setting, but it still needs an existing segment of about 1.09 billion documents, an int[maxDoc] doc map (index/Sorter.java:146) and a large heap. The default TieredMergePolicy caps merged segments at 5 GB (TieredMergePolicy.java:77); how a normal application would come to hold such a segment was not studied.
• Effect. A loud ArrayIndexOutOfBoundsException. A plain sort leaves its data unsorted but still a permutation of the input. On the flush route the IndexWriter is closed with the exception as its tragic exception, so the uncommitted documents are lost.
• Likelihood: contrived. The run lengths must follow a pattern solved for with a linear program; the study's search, which kept one merge pattern fixed, found no smaller legal input. Priority low.

• The input. Run i is RUNS[i] - 1 false values followed by one true, so it is ascending and ends at a descent; the last run is a single false. n = 1,093,938,049, minRun(n) = 33, and every run except the last is at least 38, so sort() detects exactly these runs. It is the smallest legal overflowing input the study found; its search kept one merge pattern fixed.
• Why a bit set. A RandomAccess list view of a FixedBitSet keeps 1.09 billion elements in about 137 MB. With the sorter's temp array (Object[n / 64], about 68 MB, CollectionUtil.java:86, :166) the test needs about 205 MB of heap: it ran out of memory with -Xmx160m, and fails the same way with -Xmx224m and with 512 MB, the Gradle test default. It takes about 10 s with a plain JVM and about a minute under Gradle's default test JVM flags.
• What it asserts. That the sort does not throw, and that the result is sorted: the first set bit is at n - 1,060.
• Index-sorting route (prose only). The same runs as NumericDocValuesField values in doc-ID order, with setIndexSort(new Sort(new SortField("v", SortField.Type.INT))) and setRAMBufferSizeMB(1024): commit() of 1,093,938,049 buffered documents throws the same exception and closes the writer; SortingCodecReader.wrap on a committed unsorted segment of that size throws too. That program needs a 16 GB heap and about 5 minutes, so it is supporting evidence, not a second repro.
• Regression test. The same test; given its size it may belong under @Nightly, like TestTimSorterWorstCase. ./gradlew tidy (google-java-format) re-indents the RUNS array and changes nothing else, but the file gets one line shorter, so the test frames then read :132 and :135.

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

# Gradle, main 645d4fe14a20, seed DEADBEEF, assertions on, default 512 MB test heap
TestTimSorterRunStackOverflow > testTimSortLegalInput FAILED
    java.lang.AssertionError: timSort of 1093938049 elements threw java.lang.ArrayIndexOutOfBoundsException: Index 50 out of bounds for length 50
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:202A3451691B6A42]:0)
        at org.apache.lucene.util.TestTimSorterRunStackOverflow.testTimSortLegalInput(TestTimSorterRunStackOverflow.java:136)

        Caused by:
        java.lang.ArrayIndexOutOfBoundsException: Index 50 out of bounds for length 50
            at org.apache.lucene.util.TimSorter.pushRunLen(TimSorter.java:98)
            at org.apache.lucene.util.TimSorter.sort(TimSorter.java:204)
            at org.apache.lucene.util.CollectionUtil.timSort(CollectionUtil.java:166)
            at org.apache.lucene.util.TestTimSorterRunStackOverflow.testTimSortLegalInput(TestTimSorterRunStackOverflow.java:133)

# index-sorting flush route, stock main, assertions off (plain main(), 16 GB heap)
route=flush buffered docs=1093938049
java.lang.AssertionError: IndexWriter.commit() with index sort <int: "v"> and 1093938049 buffered docs threw
  java.lang.ArrayIndexOutOfBoundsException: Index 50 out of bounds for length 50; writer open: false,
  tragic exception: java.lang.ArrayIndexOutOfBoundsException: Index 50 out of bounds for length 50
# frames: TimSorter.pushRunLen(:98) <- TimSorter.sort(:204) <- index.Sorter.sort(Sorter.java:154)
#   <- Sorter.sortAndLeaveUnpacked(:238) <- IndexingChain.maybeSortSegment(:297) <- IndexingChain.flush(:305)
#   <- DocumentsWriterPerThread.flush(:492) <- ... <- IndexWriter.commit(:4215)

• Contract. Sorter.sort(from, to): "Sort the slice which starts at from (inclusive) and ends at to (exclusive)." (util/Sorter.java:75-79). CollectionUtil.timSort documents only IllegalArgumentException for lists without random access (CollectionUtil.java:155-162); ArrayUtil.timSort documents no exception (ArrayUtil.java:558-600); the TimSorter class javadoc names no size limit (TimSorter.java:21-40). IndexWriterConfig.setIndexSort: "Set the Sort order to use for all (flushed and merged) segments." (IndexWriterConfig.java:504).
• Intent. STACKSIZE = 49; // depends on MINRUN says the stack is meant to be large enough. LUCENE-6293 is listed under Bug Fixes in CHANGES 5.1.0 ("Fixed TimSorter bug.") and added the worst-case test that is now the @Nightly TestTimSorterWorstCase, which drives a TimSorter with an adversarial run pattern and expects sort() to finish.
• The 2015 discussion named both fixes. Adrien Grand on #7355: "There are two suggested ways to fix the issue, either change the max stack size or change the condition upon which consecutive runs are collapsed. I opted for the first one which is easier to implement." This bug report is about the second one.
• Precedent. OpenJDK treated the same residual as a bug (JDK-8203864, fixed in JDK 11). JDK 25's java.util.TimSort.mergeCollapse has the fourth-run check and credits the Auger et al. analysis in its comment.

The strongest case for "not a bug": the classes are @lucene.internal; the input is absurd, 1.09 billion elements in an order solved for with a linear program, and the failure is loud. In 2015 Adrien Grand wrote "This bug cannot corrupt data, it can just raise an ArrayIndexOutOfBoundsException if you happen to have a large array which has a very specific pattern", and Robert Muir asked for "no high-risk fixes for low-risk bugs". The cross-model adversary refuted on the @lucene.internal ground alone, while agreeing on the reproduction, the root cause and the fix.

Why it fails: @lucene.internal is a compatibility notice ("might change in incompatible ways in the next release"), not permission to crash on valid input. The objection does apply to the minimal test, which goes through internal classes; but the same overflow is reached through supported public API, IndexWriterConfig.setIndexSort plus IndexWriter.commit(), where it closes the writer, although only with a deliberately extreme setup (one in-memory segment of 1.09 billion one-field documents). The 2015 maintainers held the same "very specific pattern, no corruption" view and still fixed it, believing 49 was enough; it is not. The condition fix that looked riskier in 2015 is now the JDK's own code. What the argument does establish: priority is low.

Three options. Option A was applied in a scratch worktree of main 645d4fe14a20 and run with Gradle against the minimal test, the closest suites, all core tests and core's static checks; earlier runs also tested it, with TimSorter shadowed, against the index-sorting re-sort route.

One line in ensureInvariants (TimSorter.java:135). It is the JDK's mergeCollapse condition n > 1 && runLen[n-2] <= runLen[n] + runLen[n-1] in TimSorter's top-of-stack indexing, with the same choice of which run to merge. The JDK's comment says the invariants then hold upon entry to its method; that is about the JDK's loop, not a proof for Lucene's, and no general proof for TimSorter was written. What was checked: with the fix the stack peaks at 19 runs on this input and on each of the study's 17 legal overflowing sequences (a run-length mirror), and the diagram's probe on the real code sees at most 18 runs before a push; both are far below 49. The diff's comment names CPython's listsort for its 2015 change (bpo-23515); current CPython was not checked.

       if (stackSize > 2) {
         final int runLen2 = runLen(2);
 
-        if (runLen2 <= runLen1 + runLen0) {
+        // also check the fourth run from the top (as in OpenJDK's JDK-8203864 fix and CPython's
+        // listsort), otherwise the invariant can break deeper in the stack and overflow runEnds
+        if (runLen2 <= runLen1 + runLen0 || (stackSize > 3 && runLen(3) <= runLen2 + runLen1)) {
           // merge the smaller of 0 and 2 with 1
           if (runLen2 < runLen0) {
             mergeAt(1);

Trade-offs

Changes the merge order only when the fourth-run rule is broken (the small walk above is such a state); how often that happens on real data, and any performance effect, were not measured. One extra comparison per loop iteration. In 2015 this was the option judged harder to implement; it is now the JDK's own code.

What the checks validated

• The minimal test fails on stock main under Gradle and passes with the fix, with assertions on (73.6 s) and off (69.6 s), in a scratch worktree of main 645d4fe14a20, seed DEADBEEF.
• Closest suites: TestTimSorter, TestCollectionUtil, TestArrayUtil, TestIndexSorting and TestSortingCodecReader, 97 tests, 0 failures; the @Nightly TestTimSorterWorstCase with -Ptests.nightly=true passes.
• All of :lucene:core:test: 8,898 tests, 322 skipped, 0 failures, the minimal test included.
• :lucene:core:check -x test passes once ./gradlew tidy has re-indented the test's RUNS array; the fix itself needed no reformatting.
• Earlier, with TimSorter shadowed: the index-sorting re-sort route on the 1,093,938,049-document segment passes (it fails on stock main), and 32 upstream sorter tests pass.

Size the stack from Auger et al.'s height bound for the three-run check, which the study reads as at most 86 entries for n < 2^31.

Trade-offs

Keeps every merge decision unchanged and costs 37 more ints per sort, but keeps a broken invariant and relies on a published bound once more, which is what failed after 2015. Not validated.

Open #10671 (LUCENE-9632) discusses replacing Lucene's TimSort with the JDK's.

Trade-offs

Not a fix for this bug: maintainers there note that TimSorter must stay for the Sorter API (parallel arrays), and index sorting's DocValueSorter would keep using it.

• An AI tool replayed the crash sequence that Auger, Jugé, Nicaud and Pivoteau published for Java's TimSort (ESA 2018) through TimSorter's package-private internals, and the stack overflowed. That sequence has runs of 17 elements, below Lucene's minRun(n) = 33, and the real sort() of that exact array succeeds (maximum stack depth 44). So the finder concluded, wrongly, that no reachable overflow was known.
• An independent verifier recorded the 4,138 comparisons ensureInvariants makes on that trace as linear constraints, minimised n with every run at least m (HiGHS), and rounded the solution run by run while keeping every merge decision. That gave 17 legal sequences from 1,093,938,049 to 1,719,699,526 elements; the three run on the stock jar crashed it, through CollectionUtil.timSort, a TimSorter subclass and, at 1,285,317,058, ArrayUtil.timSort(Boolean[]). The Python mirror and the linear program only found inputs; every behavioural claim comes from the real jar.
• It was later reduced to one test with the smallest input found (Java-public methods of @lucene.internal classes), and a tie-break executed the index-sorting routes, which are supported public API.