SparseFixedBitSet.nextClearBit returns NO_MORE_DOCS in the last 4096-bit block

SparseFixedBitSet is Lucene's bit set for sparse sets; the default codec uses it for the deleted docs of sparsely deleted segments. It splits its bits into blocks of 4,096. Its nextClearBit, added in 10.5.0 by #16072 to make BitSetIterator#docIDRunEnd fast, caps the search in each block at Math.min(blockBase + 4096, length), computed in int. For the last block an int-indexed set can have, which starts at 2^31 - 4096 = 2,147,479,552, the sum is 2^31 and wraps to Integer.MIN_VALUE: the block is skipped unread and nextClearBit returns NO_MORE_DOCS although clear bits exist.

Every set longer than 2,147,479,552 bits is affected whenever the search reaches its last block: a start inside it, or an earlier start with every bit from there up to the block set. BitSetIterator#docIDRunEnd turns the wrong answer into a run that covers docs not in the set. Through public reader API, the deleted-docs iterator of a sparsely deleted 2,147,482,624-doc segment (built from a synthetic reader for speed) claims 1,000 consecutive deleted docs where only 1 is. No in-tree query path that consumes the wrong value was found, so the practical impact is very low; the fix is two lines.

private int firstClearInBlock(int i4096, int fromGlobal, int upperBound) {
  final int blockBase = i4096 << 12;                        // :435  last block: 524287 << 12 = 2147479552
  final int blockEnd = Math.min(blockBase + 4096, length);  // :436  2147479552 + 4096 wraps to Integer.MIN_VALUE
  int from = Math.max(fromGlobal, blockBase);
  final int blockCap = Math.min(upperBound, blockEnd);      // :438  Integer.MIN_VALUE
  if (from >= blockCap) {                                   // :439  always true
    return DocIdSetIterator.NO_MORE_DOCS;                   // :440  the block is never read
  }

• Call chain. nextClearBit(int) and nextClearBit(int, int) (:418-428) call nextClearBitInRange (:484-500), which asks firstClearInBlock block by block and returns NO_MORE_DOCS when every block says none.
• When. Block i4096 = 524287 exists exactly when length > 2147479552. An empty set is enough: the early return fires before the block's bits are looked at. Lengths up to 2,147,479,552 work; 2147479553, 2147483519 (IndexWriter.MAX_DOCS) and 2147483647 fail. FixedBitSet is correct for the same bits. The search also reaches that block from an earlier start when every bit from there up to the block is set (nextClearBitInRange moves on block by block, :488-498): with only bits 2147479542 to 2147479551 set, nextClearBit(2147479542) returns NO_MORE_DOCS instead of 2147479552 (a scratch check, assertions on and off; fix A passes it).
• A second wrap behind it. pos = wStart + 64 (:475) overflows on the last 64-bit word (start 2^31 - 64) when length > 2^31 - 64. The early return hides it today. A fix of :436 alone exposes it: on a set of Integer.MAX_VALUE bits whose last word has all its bits set, nextClearBit(2147483584) then returns -2147483648. (The same expression at :459 never runs: inside while (pos < blockCap), the return pos just before it always fires.)

int upTo = doc + Math.min(length - doc, MAX_RUN_END_SCAN);  // :114, MAX_RUN_END_SCAN = 1 << 16 (:59)
if (runEnd < upTo) {
  int end = bits.nextClearBit(runEnd, upTo);                // :116
  runEnd = end == NO_MORE_DOCS ? upTo : end;                // :117
}

• A wrong NO_MORE_DOCS becomes a run up to upTo: up to 65,536 docs ahead on 10.6.0 and main, up to the end of the set on 10.5.x (end == NO_MORE_DOCS ? length : end). The claimed run can end that far ahead, but the docs it wrongly includes all lie in the last block: fewer than 4,096. That breaks DocIdSetIterator#docIDRunEnd: "All docs in range [docID(), docIDRunEnd()) match this iterator" (DocIdSetIterator.java:251).
• DenseConjunctionBulkScorer (:197-211) trusts a clause's run of at least WINDOW_SIZE / 2 and calls collector.collectRange(min, runEnd). Driven directly with a one-doc SparseFixedBitSet filter of length MAX_DOCS, it collected 3,966 docs instead of 1; the FixedBitSet control collected 1.

• Scale. Bit sets are sized to a segment's maxDoc, so in an index this needs one segment with more than 2,147,479,552 docs: the 3,967 largest legal sizes, up to and including IndexWriter.MAX_DOCS = 2,147,483,519, so within 3,966 docs of it. A set built directly can be any length up to Integer.MAX_VALUE (4,095 bad lengths).
• Default code builds such sets. The default codec reads live docs with at most 1% deletions into a SparseFixedBitSet(maxDoc) of the deleted docs (Lucene90LiveDocsFormat.java:69, :113-116, :141); BitSet.of and AcceptDocs build one for sparse filters.
• Public reach (executed). LeafReader#getLiveDocsWithDeletedIterator() (@lucene.experimental) returns that LiveDocs, whose deletedDocsIterator() is a BitSetIterator over it; docIDRunEnd() has no internal marker. On a single on-disk segment of 2,147,482,624 docs (default codec, two deletes, committed and reopened; built for speed with IndexWriter#addIndexes from a synthetic, field-less CodecReader whose overridden accessors are @lucene.internal; normal indexing of that many docs was not run for this bug), the iterator on deleted doc 2,147,481,624 returns docIDRunEnd() = 2,147,482,624 instead of 2,147,481,625. The deleted doc outside the last block gives the right answer. Fails on main, 10.6.0 and 10.5.2.
• No in-tree consumer found (a grep survey, not a proof). No main-source code calls getLiveDocsWithDeletedIterator() or deletedDocsIterator(); the other production nextClearBit callers (HNSW building) get a FixedBitSet; the AcceptDocs iterators feed kNN, which only calls nextDoc() or bits(). Wrong search hits need custom code, such as a query that hands such an iterator to a conjunction.
• Silent. No exception and no assertion; the same with assertions on and off.
• Narrower live-docs window today. On 10.4.0 and later, deletions in a segment above 2,147,482,624 docs cannot be committed at all (a separate bug, LFV-147), so the live-docs path is open for maxDoc in (2,147,479,552, 2,147,482,624].

• Smallest input. An empty set is enough, because the early return fires before any bit is read. SparseFixedBitSet is a public @lucene.internal class; the test sits in its package but uses no package-private member.
• Assertions. It fails the same way with assertions on and off on main and 10.6.0. On 10.5.0 to 10.5.2 run it with -Ptests.asserts=false: with assertions on, the constructor's own blockCount assertion (fixed by #16347 in 10.6.0) fires first.
• As the regression test: this same method, for example in TestSparseFixedBitSet. It does not cover the fix's second hunk: it also passes with only the first line changed. The evidence for that hunk is the scratch second-wrap check (Suggested fix).

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

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions on
TestSparseFixedBitSetLastBlock > testNextClearBitInLastBlock FAILED
    java.lang.AssertionError: expected:<2147483646> but was:<2147483647>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:23E3908A24453277]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:647)
        at org.junit.Assert.assertEquals(Assert.java:633)
        at org.apache.lucene.util.TestSparseFixedBitSetLastBlock.testNextClearBitInLastBlock(TestSparseFixedBitSetLastBlock.java:26)
1 test completed, 1 failed
# gradle, assertions off (-Ptests.asserts=false): the same AssertionError
# 10.6.0, assertions on and off; 10.5.0, 10.5.1, 10.5.2, assertions off: the same AssertionError
# with fix A or B: BUILD SUCCESSFUL, 1 test
# (2147483647 is DocIdSetIterator.NO_MORE_DOCS)

• Contract. BitSet.java:105-111: "Returns the index of the first unset (clear) bit at or after index, or NO_MORE_DOCS if every bit in [index, length()) is set." :113-117: "Returns the first unset bit in [start, upperBound), or NO_MORE_DOCS if none." DocIdSetIterator.java:251: "All docs in range [docID(), docIDRunEnd()) match this iterator."
• Any length is accepted. SparseFixedBitSet.java:60-67: "Create a SparseFixedBitSet that can contain bits between 0 included and length excluded"; only length < 1 is rejected. IndexWriter.MAX_DOCS = Integer.MAX_VALUE - 128 (IndexWriter.java:208) makes such segment sizes legal.
• The code means to cap the block. Math.min(blockBase + 4096, length) exists to stop at length; the wrap defeats it.
• Precedent. #16347 ("Fix integer underflow in assertion in SparseFixedBitSet", romseygeek, merged 2026-07-03, 10.6.0) fixed the blockCount assertion at these lengths and added TestSparseFixedBitSet.testLargeValuesDoNotOverflow (blockCount(2147479553), the smallest length that fails here). Its body: "the error is only in the assertion; the actual calculated block count is correct and there is no production bug". This one is in the returned value.
• Why tests miss it. #16072's testNextClearBit uses sets of 1 to 40,000 bits.

Strongest case for "not a bug" (a cross-model reviewer, OpenAI GPT-5.6, refute lens, who reproduced it and agreed on the cause and the fix): BitSet, SparseFixedBitSet and BitSetIterator are all @lucene.internal, so outside callers cannot rely on them, and no non-internal path had been shown. The reviewer rated this "moderate" and wrote that "nothing ... documents the wrong NO_MORE_DOCS result itself as intended" and that a maintainer "may still reasonably fix this".

Why it fails: the tie-break observed the wrong run end through a consumer path that names no internal type: DirectoryReader, LeafReader#getLiveDocsWithDeletedIterator, the @lucene.experimental LiveDocs, and DocIdSetIterator#docIDRunEnd. (To be fair to the objection: that test built its segment with IndexWriter#addIndexes from a synthetic CodecReader whose overridden accessors are @lucene.internal; an application would have to index more than 2,147,479,552 docs into one segment, which was not run for this bug.) @lucene.internal limits API stability, not correctness, and Lucene's own BitSetIterator relies on this contract. Nor is it absurd input failing loudly: the sizes are within the documented MAX_DOCS, and the failure is silent.

Two validated options, both applied in a scratch worktree of main 645d4fe14a20 and run with gradle. Both need two changes: the block end, and an early return that keeps pos = wStart + 64 from wrapping on the last 64-bit word. Not recommended: changing only the block-end line (it passes the test but exposes the second wrap), or rewriting the loop in long arithmetic (a bigger change to a hot loop for no gain; not run). The minimal test does not cover the second hunk (it also passes with the first line only); the scratch second-wrap check does.

Two hunks in SparseFixedBitSet.firstClearInBlock. cand is the first clear bit at or after pos in this word. If it is at or past the cap, no clear bit lies in [pos, blockCap), so NO_MORE_DOCS is the right answer for this block, and returning it skips the increment. On every word but the last, the current code reaches the same answer one step later; on the last word, which starts at 2^31 - 64, it would compute wStart + 64, which wraps (with the first hunk only, the scratch check returns -2147483648). That word's top bit, 2^31 - 1, is below no int length, so it is always clear and the loop always returns at that word.

// SparseFixedBitSet.firstClearInBlock
-    final int blockEnd = Math.min(blockBase + 4096, length);
+    final int blockEnd = MathUtil.unsignedMin(blockBase + 4096, length);
...
         final int cand = pos + Long.numberOfTrailingZeros(inv);
-        if (cand < blockCap) {
-          return cand;
-        }
+        return cand < blockCap ? cand : DocIdSetIterator.NO_MORE_DOCS;

Trade-offs

• Two lines; MathUtil.unsignedMin is the idiom DenseConjunctionBulkScorer already uses against the same kind of wrap (DenseConjunctionBulkScorer.java:198).
• unsignedMin takes a moment to read: 2^31 read as unsigned is larger than any length.
• No extra work on the hot path; the early return skips the rest of the word loop.

What the checks validated

• Gradle, scratch worktree of 645d4fe14a20, seed DEADBEEF: the minimal test fails before the change and passes after it, with assertions on and off.
• Seed DEADBEEF: TestSparseFixedBitSet (19), TestBitSetIterator (11), TestSparseFixedBitDocIdSet (7), TestFixedBitSet (34), TestLiveDocs (26), TestLucene90LiveDocsFormat (4, 1 skipped), TestDenseConjunctionBulkScorer (26), TestDocIdSetIterator (10) and the minimal test: 138 tests, 0 failures.
• Seed 5EED1234: every org.apache.lucene.util.Test* class plus TestDenseConjunctionBulkScorer and TestLucene90LiveDocsFormat: 69 suites, 586 tests, 11 skipped, 0 failures.
• A scratch check of the second wrap (last word full, nextClearBit(2147483584)) returns NO_MORE_DOCS with A and -2147483648 with only the first hunk.
• The public-path end-to-end test (2,147,482,624-doc segment) passes with this class patched.
• Not run: the whole :lucene:core:test or check.

final int blockEnd = blockBase + Math.min(4096, length - blockBase); (the study verifier's root-cause line), plus the same early return as A. length - blockBase is positive because a block only exists below length.

-    final int blockEnd = Math.min(blockBase + 4096, length);
+    final int blockEnd = blockBase + Math.min(4096, length - blockBase);
...
-        if (cand < blockCap) {
-          return cand;
-        }
+        return cand < blockCap ? cand : DocIdSetIterator.NO_MORE_DOCS;

Trade-offs

Plain signed arithmetic, perhaps easier to read than unsignedMin; the same behaviour as A.

What the checks validated

Gradle, seed DEADBEEF: the minimal test, the second-wrap check, TestSparseFixedBitSet, TestBitSetIterator, TestSparseFixedBitDocIdSet, TestLiveDocs and TestDenseConjunctionBulkScorer: 91 tests, 0 failures.

Either form of the first line alone passes the minimal test but leaves pos = wStart + 64 (:475) free to wrap for lengths above 2^31 - 64.

Trade-offs

One line, but nextClearBit can then return a negative number.

What the checks validated

Gradle, seed DEADBEEF, unsignedMin line only: the minimal test passes; the second-wrap check fails with expected:<2147483647> but was:<-2147483648>.

• Sweep. The study's overflow-at-scale experiment (main 7cecf79523, 2026-10-22) used CodeQL to list every non-constant int multiplication, left shift and "x + C" window or block addition in the target packages (602 + 63 rows); SparseFixedBitSet.java:436, :459 and :475 were three of them (:459 later turned out to be unreachable).
• Solver. Each scale-relevant expression was transcribed into Z3 bit-vector logic with Java wraparound and the documented limits as preconditions. For this line: a counterexample (length 2147483135, block 524287); a proof that the line is exact if and only if length <= 2^31 - 4096; a proof that wStart + 64 is safe up to MAX_DOCS, and a counterexample for lengths above 2^31 - 64.
• Bytecode. JBMC on the real lucene-core jar found its own counterexample (length 2147480574, start 2147480000, result 2147483647), with blockEnd = blockCap = -2147483648 in its trace; replayed on the JVM it gives the same wrong result. A JVM sweep of 556,920 (length, start) pairs in the safe region found no mismatch.
• Verification. An independent verifier wrote its own 8 tests (threshold sweep, docIDRunEnd, DenseConjunctionBulkScorer, the second-wrap probe) and reproduced it; the hunt then reduced it to the one-assertion test and found the public live-docs path.