Postings docIDRunEnd() returns Integer.MIN_VALUE near 2^31 doc IDs, so CheckIndex flags a healthy segment as broken

BlockPostingsEnum#docIDRunEnd() in the default postings reader (Lucene104PostingsReader, and the same code in the Lucene101 and Lucene103 readers) extends a fully dense 256-doc block's run to the end of the enclosing 8,192-doc level-1 skip block when the doc-ID gap and the doc-count gap to that block's end are equal. After a term's last complete level-1 block there is no such block: skipLevel1To sets level1LastDocID = NO_MORE_DOCS as a sentinel but still adds 8,192 to level1DocCountUpto, and the shortcut does not exclude the sentinel. For ordinary doc IDs the gaps differ by about two billion and the method is correct; within 8,192 doc IDs of 2^31 they can be equal, and the method returns NO_MORE_DOCS + 1 = Integer.MIN_VALUE, breaking its contract ("The returned doc is greater than docID()").

For a term in every document this happens on every dense block after the term's last complete level-1 block once maxDoc >= 2,147,475,712, up to IndexWriter.MAX_DOCS = 2,147,483,519. On a default-codec segment of exactly MAX_DOCS documents written by IndexWriter, CheckIndex at level 2 reports "Run end -2147483648 is <= doc ID 2147475456" and "1 broken segments (containing 2147483519 documents)", and says -exorcise would remove the segment; with a one-condition guard the same segment is clean. Query results stay exact (the value is below docID(), so consumers only lose a shortcut). Introduced by #14390 in 10.2.0; every release from 10.2.0 to 10.6.0 and main is affected.

Constants: BLOCK_SIZE = 256, LEVEL1_FACTOR = 32, LEVEL1_NUM_DOCS = 8,192 (Lucene104PostingsFormat.java:343, :348, :351).

1. Small terms never reach it. With docFreq < LEVEL1_NUM_DOCS the enum starts with level1LastDocID = NO_MORE_DOCS and level1DocCountUpto = 0 (Lucene104PostingsReader.java:559-568); the shortcut's right side is then negative and can never match. A term needs at least one complete level-1 block.
2. The sentinel state. skipLevel1To (:674 on) computes docCountLeft = docFreq - level1DocCountUpto (:683), then adds LEVEL1_NUM_DOCS to level1DocCountUpto (:684), and only then, if fewer than 8,192 docs are left, sets level1LastDocID = NO_MORE_DOCS and stops (:686-688). In a term's tail the counter therefore includes a full phantom level-1 block.
3. The unguarded shortcut. docIDRunEnd() (:1099-1129), for a UNARY block whose four 64-bit words are all set (:1101-1115), computes level0DocCountUpto = docFreq - docCountLeft (:1117) and tests level1LastDocID - level0LastDocID == level1DocCountUpto - level0DocCountUpto (:1118-1119); if true it returns level1LastDocID + 1 (:1121), else level0LastDocID + 1 (:1124).
4. When it misfires. For the j-th full block after the last complete level-1 block (j = 1..31) the right side is 8,192 - 256 x j (at most 7,936) and the left side is NO_MORE_DOCS - level0LastDocID, about two billion for ordinary doc IDs. They are equal exactly when level0LastDocID = NO_MORE_DOCS - (8,192 - 256 x j), so only blocks whose docs are all at or above 2^31 - 8,192 = 2,147,475,456 can trigger it; then :1121 returns NO_MORE_DOCS + 1 = Integer.MIN_VALUE, with assertions on or off.
5. Worked example (the minimal test). One term of 8,448 consecutive doc IDs, 2,147,467,264 to 2,147,475,711: one complete level-1 block ending at 2,147,475,455, then one dense block 2,147,475,456 to 2,147,475,711. At doc 2,147,475,456: level1LastDocID = 2,147,483,647 (sentinel), level1DocCountUpto = 16,384 (two blocks counted, one exists), level0LastDocID = 2,147,475,711, level0DocCountUpto = 8,448. Left 7,936, right 7,936: it returns -2,147,483,648 instead of 2,147,475,712. Shifted 1,000,000 doc IDs lower, the left side is 1,007,936 and the answer is right.
6. A term in every document. After k complete level-1 blocks the test reduces to k x 8,192 = 2^31 - 8,192, so k = 262,143: it fires on every dense tail block exactly when maxDoc is in [2,147,475,712, MAX_DOCS]. A Z3 bit-vector model with Java int semantics derived this range (unique k) and proved the bad state unreachable while level0LastDocID < MAX_DOCS - 16,386.
7. The reader knows the sentinel elsewhere. Impacts.numLevels() returns 1 when level1LastDocID == NO_MORE_DOCS (:1358); docIDRunEnd() does not check it.
8. Older formats. The backward-codecs readers for indexes written by 10.1.x to 10.3.x (Lucene101 and Lucene103 formats) have the same shortcut with 128-doc blocks and 4,096-doc level-1 blocks (Lucene101PostingsReader.java:1059-1062, Lucene103PostingsReader.java:1105-1108, sentinel at :679 in both); their first failing doc is 2,147,479,552. 10.1.0 code has no postings docIDRunEnd, but 10.1.0 already writes the Lucene101 format, and a term it wrote near 2^31 returns -2,147,483,648 at doc 2,147,479,552 once main reads it (executed).
9. Who sees the value. CheckIndex testPostings runs only at level >= 2 (CheckIndex.java:1114-1125, :4754) and checks runs of every term with docFreq > 1024, every 1024th term, or all terms at level 3 (:2090-2104); checkDocIDRuns throws "Run end X is <= doc ID Y" (:2549) and the segment is reported FAILED with "exorciseIndex() would remove reference to this segment" (:1208). The CLI default is level 1 (:4742, :4748); new CheckIndex(dir) without setLevel keeps 0 (:499). The test framework's AssertingPostingsEnum asserts endDocID > startDocID (AssertingLeafReader.java:609). DenseConjunctionBulkScorer evaluates a clause with a short run end normally and DisjunctionDISIApproximation discards it with Math.max (DenseConjunctionBulkScorer.java:196-212, DisjunctionDISIApproximation.java:225-233).

• Who is hit. A single segment within about 8,000 doc IDs of IndexWriter.MAX_DOCS with a term that is dense near the end of the doc-ID space, for example a term in every document of a shard force-merged to one segment at the hard limit, checked with CheckIndex at level 2 or higher, or Lucene's own tests at that scale with the default postings format (such as testExactlyAtTrueLimit: predicted, not run).
• Default vs opt-in. The default codec and IndexWriter settings produce the state; nothing is configured. Seeing it needs CheckIndex at level 2 or 3 (the CLI default is 1), the test framework's check-on-close, or a caller of docIDRunEnd() that relies on the contract.
• Scale. maxDoc >= 2,147,475,712 for a term in every document; in general a dense 256-doc block whose docs are all at or above 2,147,475,456 (2,147,479,552 for indexes written by 10.1.x to 10.3.x) right after the term's last complete level-1 block. A 67,108,864-doc segment is clean.
• What goes wrong. CheckIndex reports a valid segment as broken ("1 broken segments (containing 2147483519 documents)") and says -exorcise would remove it; an operator who trusts it and runs -exorcise would drop about 2^31 healthy documents (follows from CheckIndex's code and warning; not executed). docIDRunEnd() breaks its contract on up to 7,936 docs per term. Under the test framework, AssertingPostingsEnum fails.
• Queries are fine. The value is below docID(), so it can only shorten a run. Five FILTER conjunctions, some with nested disjunctions, over a MAX_DOCS segment with holes inside the affected tail returned exact results with assertions on and off while the bad value was consumed 2 to 4 times per query; the same with the fix, with no measurable time difference.
• Likelihood: contrived. Almost no deployment runs single segments at the 2^31 limit, but Lucene supports and tests that limit.

The test is codec level: it uses the public Lucene104PostingsWriter (setField, startTerm, startDoc/finishDoc, finishTerm) on a SegmentInfo with maxDoc = IndexWriter.MAX_DOCS, then Lucene104PostingsReader.postings (marked @lucene.experimental) with the term state the writer filled in. The terms dictionary is skipped because docIDRunEnd does not use it. The doc IDs must be consecutive across the level-1 boundary: with docs 0..8,191 followed by the 256-doc block, that block's first delta is large, it is stored PACKED rather than dense, and the test passes on main.

It is deterministic (the failing value does not depend on the seed; seeds DEADBEEF, 5EED1234 and 7E1B4EA4 fail), single-threaded and needs the default test heap. The FieldInfo arguments are packed for brevity (./gradlew tidy reformats them). As a regression test it can stay its own class or become a method of TestLucene104PostingsFormat (same package).

The CheckIndex report is not part of this test. It was seen end to end on a segment of exactly MAX_DOCS documents that IndexWriter wrote (a plain program with only lucene-core: two small single-segment indexes built with addDocument and forceMerge(1), then addIndexes(CodecReader...) of 512 copies into one new segment, about 4 minutes and 79 MB), and in the study's codec-level CheckIndex.testPostings runs. The @Monster test testExactlyAtTrueLimit itself was not run.

# gradle, main 645d4fe14a20, stock (same failure with -Ptests.asserts=false)
> Task :lucene:core:test FAILED

TestDocIDRunEndNearMaxDoc > testDenseBlockAfterLastLevel1Block FAILED
    java.lang.AssertionError: expected docIDRunEnd() > 2147475456, got -2147483648
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:71C1222622114FDE]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.codecs.lucene104.TestDocIDRunEndNearMaxDoc.testDenseBlockAfterLastLevel1Block(TestDocIDRunEndNearMaxDoc.java:77)
:lucene:core:test (FAILURE): 1 test, 1  failure

# with the fix: :lucene:core:test (SUCCESS): 1 test (assertions on and off)

# end to end: IndexWriter-built segment of MAX_DOCS documents, CheckIndex level 2, main, assertions off (excerpt; timestamps removed)
advance(2147475456) = 2147475456, docIDRunEnd() = -2147483648
docIDRunEnd() contract (result > docID()) over 8063 postings from 2147475456 to 2147483518: violations=7936 first at doc 2147475456 (docIDRunEnd()=-2147483648), last at doc 2147483391
1 of 1: name=_0 maxDoc=2147483519
    codec=Lucene104
    test: terms, freq, prox...ERROR: org.apache.lucene.index.CheckIndex$CheckIndexException: Run end -2147483648 is <= doc ID 2147475456
FAILED
    WARNING: exorciseIndex() would remove reference to this segment; full exception:
WARNING: 1 broken segments (containing 2147483519 documents) detected

# same index with the guard
advance(2147475456) = 2147475456, docIDRunEnd() = 2147475712
    test: terms, freq, prox...OK [1 terms; 2147483519 terms/docs pairs; 2147483519 tokens]
No problems were detected with this index.

• Contract. DocIdSetIterator.java:245-263: "1. The returned doc is greater than docID(). 2. All docs in range [docID(), docIDRunEnd()) match this iterator." The only exception: "It is illegal to call this method when the iterator is exhausted or not positioned." The method is public, without @lucene.internal or @lucene.experimental.
• Lucene enforces it. #14390 added the postings shortcut together with CheckIndex.checkDocIDRuns, which rejects a run end <= doc; AssertingPostingsEnum asserts it too.
• The limit is supported. IndexWriter.MAX_DOCS = Integer.MAX_VALUE - 128 is the "Hard limit on the maximum number of documents that may be added to the index" (IndexWriter.java:202-208). TestIndexWriterMaxDocs#testExactlyAtTrueLimit (:47-89) adds exactly MAX_DOCS documents with one StringField, calls forceMerge(1) and closes a test directory, which runs CheckIndex.
• The reader handles the sentinel elsewhere. Impacts.numLevels() (Lucene104PostingsReader.java:1358).
• History. The bodies, comments and reviews of #14390, #14693 and #15160 never mention the NO_MORE_DOCS level-1 sentinel or doc IDs near 2^31; no comment, test, CHANGES.txt or MIGRATE.md entry allows Integer.MIN_VALUE.
• Precedent. #16161 "SkipBlockRangeIterator: Don't extend docIdRunEnd into sparse blocks" (merged 2026-06-01) fixed the same class of bug, a run end extended up the skip levels without a density check, in the doc-values skipper iterator.

The strongest case for "not a bug": (1) nobody runs a single segment within 8,192 docs of 2^31; (2) the first repros wrote postings through @lucene.experimental codec classes and a hand-built SegmentInfo instead of IndexWriter; (3) the sentinel looks meant to make the density test fail, so the author assumed doc IDs stay far from 2^31; (4) no query returns a wrong result. A later reading-only adversary also gave a procedural "not real" because it could not run code; on the merits it agreed with the root cause and the fix.

Why it fails: (1) the limit is documented and has its own test; (2) the same value at the same doc was reproduced on a segment that IndexWriter wrote and DirectoryReader opened, and the codec-level test only feeds the default writer legal doc IDs below MAX_DOCS; (3) that assumption is written nowhere, the contract has no exception, and the reader's own numLevels() handles the sentinel; (4) low impact lowers the priority, it does not make a false corruption report intended. Nor is it a case of an absurd parameter that then fails loudly: the parameter is Lucene's own tested limit, and the loud failure is a false report on a valid segment that recommends removing it. Verdict: a defect, low priority.

Two fixes were checked; the guard is the smaller and fully validated one.

+12/-3 in Lucene104PostingsReader, backward_codecs/lucene101/Lucene101PostingsReader and backward_codecs/lucene103/Lucene103PostingsReader (the last two with two spaces less indentation). In a term's tail the method falls back to level0LastDocID + 1, the end of the current dense block; wherever a real level-1 block exists the shortcut is unchanged.

int level0DocCountUpto = docFreq - docCountLeft;
// After the last complete level-1 block, level1LastDocID is the NO_MORE_DOCS sentinel:
// there is no level-1 block to extend the run into.
boolean level1IsDense =
    level1LastDocID != NO_MORE_DOCS
        && level1LastDocID - level0LastDocID == level1DocCountUpto - level0DocCountUpto;
if (level1IsDense) {
  return level1LastDocID + 1;
}
return level0LastDocID + 1;

Trade-offs

• One extra int comparison per call on a dense block. No result changes outside the bug window: for terms below 8,192 docs, and for tails far from 2^31, the equality is already false.
• Reader-only: no format change; existing indexes written by 10.1.x to 10.6.x are read correctly without reindexing (the data on disk is valid).
• Mirrors how Impacts.numLevels() already treats the sentinel.

What the checks validated

• Gradle in a scratch worktree of 645d4fe14a20, JDK 25.0.3: the minimal test fails stock and passes with the fix, with assertions on and off.
• With the fix: org.apache.lucene.codecs.lucene104.*, TestCheckIndex, TestDenseConjunctionBulkScorer, TestBulkScorerConsistency and TestDocIdSetIterator: 12 classes, 226 tests, 6 skipped, 0 failures; backward-codecs lucene101.* and lucene103.*: 11 classes, 106 tests, 6 skipped, 0 failures.
• The @Nightly BasePostingsFormatTestCase#testDocIDRunEnd (100 force-merged IndexWriter segments, each checked by CheckIndex at level 3; skipped by default) with -Ptests.nightly=true for TestLucene104PostingsFormat, TestLucene101PostingsFormat, TestLucene101PostingsFormatV0 and TestLucene103PostingsFormat: 4 tests, 0 failures.
• :lucene:core:check :lucene:backward-codecs:check -x test passes (google-java-format, ecjLint, forbiddenApis).
• The Lucene104 hunk alone makes the IndexWriter-built MAX_DOCS segment CheckIndex-clean; ported to the 10.2.0 reader it makes the version-spanning probe pass.

In skipLevel1To, move level1DocCountUpto += LEVEL1_NUM_DOCS; below the if (docCountLeft < LEVEL1_NUM_DOCS) { level1LastDocID = NO_MORE_DOCS; break; } block, so the counter only counts level-1 blocks that exist. In the tail the shortcut's right side is then negative and never matches.

docCountLeft = docFreq - level1DocCountUpto;

if (docCountLeft < LEVEL1_NUM_DOCS) {
  level1LastDocID = NO_MORE_DOCS;
  break;
}
level1DocCountUpto += LEVEL1_NUM_DOCS;

Trade-offs

Fixes the state where it is created and also stops level1DocCountUpto from wrapping to Integer.MIN_VALUE for an all-docs term at MAX_DOCS (262,144 x 8,192 = 2^31 with the phantom block). The field is read only in skipLevel1To and docIDRunEnd, and the method is not entered again after the sentinel, but it touches the advance path and changes a field's meaning, so it needs a closer review; the two backward-codecs readers need the same change.

What the checks validated

The minimal test passes with only this change shadowed into the stock main jar, assertions on and off. No suites were run.

Would silence the false report.

Trade-offs

Hides a real contract violation from every other caller of docIDRunEnd().

Method: semi-formal (the hypothesis came from code reading; the SMT model then produced the witness, the unreachability bound and the exact trigger range).

• The finder's hunt unit modelled the Lucene104 reader's skip state. Reading docIDRunEnd next to skipLevel1To, it noticed that the level-1 shortcut compares a doc-ID gap measured from the NO_MORE_DOCS sentinel with a doc count that includes a phantom level-1 block.
• A Z3 bit-vector model of the skip arithmetic with 32-bit Java int semantics: Q4a found a witness (level0LastDocID = 2,147,477,503, returning NO_MORE_DOCS + 1); Q4b showed the state unreachable while level0LastDocID < MAX_DOCS - 16,386; Q4c gave the all-docs trigger range, maxDoc in [2,147,475,712, MAX_DOCS] with the unique count k = 262,143 of complete level-1 blocks.
• A codec-level JUnit on the stock jar failed on main (assertions on and off) and on 10.4.0 and 10.5.2 (assertions on). A run on a separate test host wrote 2,147,475,712 postings of an all-docs term in 10.7 s and failed a CheckIndex-style loop at doc 2,147,475,456, the first doc of the predicted tail block.
• The unit's postings differential (191 million checks, 0 mismatches) never reached doc IDs near 2^31; its mutant "level-1 density always true" was killed, so the shortcut is exercised at ordinary scale.
• Cross-model reviews, an independent reproducer, a devil's advocate and an adjudication then confirmed it; the repro was later cut to the one test above, and a tie-break on current main reproduced it on an IndexWriter-built segment.