FixedBitSet.ensureCapacity overflows when it grows a set to bit 1,908,874,241 or more, so a sparse doc-values or norms field with a value past doc 1.91 billion can silently lose all its values

FixedBitSet.ensureCapacity(bits, desiredBit) grows the backing long[] with about 1/8 headroom and returns new FixedBitSet(arr, arr.length << 6). The shift is int arithmetic, so once the array has 2^25 words the length wraps negative: asking for bit 2,000,000,000 from a small set gives 35,156,251 words and length() = -2,044,967,232, and the first failing bit after one jump is 1,908,874,241. The constructor accepts the negative length; with assertions on, its ghost-bits check throws ArrayIndexOutOfBoundsException.

DocsWithFieldSet, which the doc-values and norms writers use to remember which documents have a value, grows its bit set this way once a field is sparse, and its iterator stops at once for a negative length. So, with assertions off, once a sparse field gets a value past doc about 1.91 billion (below IndexWriter.MAX_DOCS = 2,147,483,519) and its bit set grows there, the flushed segment silently has no value for that field on any document; executed for numeric doc values, sorted doc values and norms, with the postings intact. It needs about 1.9 billion nearly empty documents in one in-memory segment, so the priority is low. The sibling LongBitSet had the same overflow and was fixed in 2015 (LUCENE-6409); casting to long and capping at Integer.MAX_VALUE fixes FixedBitSet too.

1. The growth. util/FixedBitSet.java:62-83 (ensureCapacityInternal, shared by ensureCapacity :49-51 and ensureCapacityAndClear :58-60): numWords = bits2words(desiredBit) (:72), arr = ArrayUtil.grow(arr, numWords + 1) (:76; ArrayUtil.oversize adds minTargetSize >> 3, util/ArrayUtil.java:157, :166), then return new FixedBitSet(arr, arr.length << 6); (:81), an int shift.
2. The numbers. desiredBit 2,000,000,000: 31,250,000 words needed, grown to 35,156,251 words (281 MB); 35,156,251 × 64 = 2,250,000,064 wraps to -2,044,967,232. Threshold after one jump from a small set: 1,908,874,241 needs 29,826,161 words and grows to 29,826,162 + 3,728,270 = 33,554,432 = 2^25 words, whose × 64 is 2^31, i.e. Integer.MIN_VALUE; 1,908,874,240 still gives 2,147,483,584. The grown size depends only on desiredBit, so every growth step to a bit of 1,908,874,241 or more wraps and every lower one does not (exhaustive sweep over all int values); when a growth happens depends on the set's history: growth in 1M-bit steps first fails at 2,105,000,003. Both are below IndexWriter.MAX_DOCS = 2,147,483,519 (index/IndexWriter.java:208).
3. No rejection. The constructor FixedBitSet(long[], int) (util/FixedBitSet.java:160-170) computes numWords = bits2words(numBits) (((numBits - 1) >> 6) + 1, :86-90). For the 2e9 witness that is -31,952,613, so its "too small" check passes. With assertions on, assert verifyGhostBitsClear() (:169) reads bits[-31952613] (:184-185) and throws ArrayIndexOutOfBoundsException. Integer.MIN_VALUE is the special case: numBits - 1 wraps to Integer.MAX_VALUE, so the word count is +2^25, exactly the array size, the check passes and length() is Integer.MIN_VALUE in both modes. Later calls never restore a valid length: desiredBit < numBits (:64) is never true, and for any doc ID the array is already big enough, so the call keeps the same negative length; only a request for bit 2,147,483,584 or more (beyond any doc ID) can grow a 2^25-word set again, and that length wraps too.
4. The consumer. index/DocsWithFieldSet.java: the first gap creates new FixedBitSet(docID + 1) (:54-58); every later add grows it with FixedBitSet.ensureCapacity(set, docID) (:52; addRange :84). So the field must already be sparse when a value arrives that grows the set past bit 1,908,874,241; if the first gap is itself that high, the direct constructor is fine and only a later value takes the bad path. iterator() returns new BitSetIterator(set, cardinality) (:103), which caches length = bits.length() (util/BitSetIterator.java:72) and returns NO_MORE_DOCS whenever target >= length (:94-95): at once for a negative length. DocsWithFieldSet.cardinality(), a separate counter, still counts every add. A probe on the stock jar shows the three bits are set (get(2000000000) is true), yet the bit set's own cardinality() is 0 and the iterator returns NO_MORE_DOCS at once.
5. The writers. NumericDocValuesWriter flushes through docsWithField.iterator() (index/NumericDocValuesWriter.java:134-142, :167), and so do NormValuesWriter (:70, :93) and SortedDocValuesWriter (:249-256, :286); the binary, sorted-numeric and sorted-set writers use the same class (code reading). So the codec writes the field with no documents.
6. Merges and vectors. Doc-values and norms merges do not use DocsWithFieldSet, so for them the loss is on the flush path. By code reading only, vectors use it on both paths: at flush, Lucene99FlatVectorsWriter's field writer adds every document with a vector (codecs/lucene99/Lucene99FlatVectorsWriter.java:499, :529) and writeMeta (:335-354) passes the set to OrdToDocDISIReaderConfiguration.writeStoredMeta; at merge, writeVectorData (:377-391) builds one over the merged doc IDs. So a sparse vector field that gets a value past doc 1.91e9, or is merged into a segment of 1.91e9+ documents, reaches the same growth; with a non-zero count and an empty iterator, DirectMonotonicWriter.finish() should then throw IllegalStateException (codecs/lucene95/OrdToDocDISIReaderConfiguration.java:86-111, util/packed/DirectMonotonicWriter.java:137-141), a loud failure (not executed).

• Who can be hit. A doc-values or norms field in a single in-memory segment (one DocumentsWriterPerThread) that is already sparse (an earlier document lacks it, so its DocsWithFieldSet uses a bit set) and then gets a value whose doc ID makes that bit set grow past bit 1,908,874,241. A sparse field with no value that high is not affected. Executed end to end for numeric doc values, sorted doc values and norms; binary, sorted-numeric and sorted-set doc values use the same class (code reading).
• Defaults. An otherwise default IndexWriterConfig pinned to the default codec (Lucene104Codec, through TestUtil.getDefaultCodec(), since the test framework randomizes the codec) and an FSDirectory reproduce it. There is no per-segment document cap below IndexWriter.MAX_DOCS (DocumentsWriterPerThread.reserveOneDoc checks only the index-wide limit), and maxBufferedDocs is off by default.
• Silent. With assertions off (the JVM default) the field's values vanish with no error. CheckIndex reports nothing for the numeric field and the norms, and flags the sorted field only as "reports wrong maxOrd=2 but this is not the case: -1". The postings are intact (docFreq 3), so the documents are still found; they only lose the field's values (sorting, faceting, norms-based scoring, FieldExistsQuery). With assertions on, addDocument throws a non-aborting ArrayIndexOutOfBoundsException for that one document and the writer stays open.
• Scale. The field's bit set counts toward the RAM buffer, so with values spread out the default 16 MB buffer would flush long before doc 1.9e9 (code reading). The executed trigger therefore uses about 1.9 billion empty documents and one commit (344-913 s per run). The RAM limits cannot stop the final jump, though (code reading): the writer updates its RAM accounting only after DocsWithFieldSet.add returns, so the growth to 281 MB and the wrap happen before any flush can react, and the 281 MB set stays below the default per-thread hard limit of 1,945 MiB. The vector routes (a sparse vector field at flush or at merge) are code reading only and likely fail loudly.
• Other callers (code reading only): SloppyPhraseMatcher, FieldUpdatesBuffer, ReadersAndUpdates and HnswGraphSearcher (ensureCapacityAndClear) and the misc module's MemoryAccountingBitsetCollector would get the same negative length for a bit of about 1.91e9 or more; none was run at that size.

The test sits in org.apache.lucene.util, next to TestFixedBitSet, and calls the public static FixedBitSet.ensureCapacity (the class is marked @lucene.internal). The try/catch only turns the assertions-on ArrayIndexOutOfBoundsException, thrown inside ensureCapacity by the constructor's ghost-bits check, into a failure that names the call.

As a regression test it is the same test, for example as TestFixedBitSet.testHugeCapacity next to TestLongBitSet.testHugeCapacity; it fails on stock and passes with the fix. It needs a 281 MB array and passed under gradle's default 512 MB test heap; the LongBitSet sibling is tagged @Monster("needs hundreds of MB of heap") and so does not run by default, and maintainers may want the same tag.

The end-to-end consequence (a NumericDocValuesField on docs 0, 2 and 2,000,000,000 with empty documents in between, one commit: "doc 0 lost its value" with assertions off, ArrayIndexOutOfBoundsException inside addDocument with assertions on) takes about 2 billion addDocument calls and 6-15 minutes, so it is deliberately not part of the repro.

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions on
TestFixedBitSetEnsureCapacityOverflow > testEnsureCapacityTo2BillionBits FAILED
    java.lang.AssertionError: ensureCapacity(bits, 2000000000) threw java.lang.ArrayIndexOutOfBoundsException: Index -31952613 out of bounds for length 35156251
        Caused by:
        java.lang.ArrayIndexOutOfBoundsException: Index -31952613 out of bounds for length 35156251
            at org.apache.lucene.util.FixedBitSet.verifyGhostBitsClear(FixedBitSet.java:185)
            at org.apache.lucene.util.FixedBitSet.<init>(FixedBitSet.java:169)
            at org.apache.lucene.util.FixedBitSet.ensureCapacityInternal(FixedBitSet.java:81)
            at org.apache.lucene.util.FixedBitSet.ensureCapacity(FixedBitSet.java:50)

# assertions off (-Ptests.asserts=false)
TestFixedBitSetEnsureCapacityOverflow > testEnsureCapacityTo2BillionBits FAILED
    java.lang.AssertionError: expected length() > 2000000000 but was -2044967232

# 10.6.0 release jars: the same two failures (FixedBitSet.java:187 <- :171 <- :83 <- :52 with assertions on)

# with the fix (gradle, seed DEADBEEF): the test passes with assertions on and off

# end to end, stock main jar, assertions off (independent reproducer, 344 s)
numeric doc values lost: expected docs [1, 3, 1950000000]
sorted doc values lost: expected docs [1, 3, 1950000000]
norms lost: expected docs [1, 3, 1950000000]
maxDoc=1950000001 numDocs=1950000001 leaves=1
numeric docs with value: []
sorted docs with value: [] valueCount=3
norms docs with value: []
docFreq(t:hello)=3
CheckIndex: dv for field: s reports wrong maxOrd=2 but this is not the case: -1 (nothing reported for the numeric field or the norms)

# end to end, assertions on (665 s)
addDocument(doc 1950000000) threw java.lang.ArrayIndexOutOfBoundsException: Index -32831520 out of bounds for length 34277344
writer open after that: true, tragic=null; docs 1 and 3 keep their values

• The contract. "Ensure the given bits can store a value at desiredBit index. If the current [#length()] is sufficient, bits is simply returned. Otherwise, a new, larger bitset is allocated, with contents of bits copied." (FixedBitSet.java:44-46). A set whose length() is negative cannot store bit 2,000,000,000.
• The class's own limit is higher. "accessed with an int index ... If you need to manage more than 2.1B bits, use LongBitSet" (FixedBitSet.java:24-27). The failing requests start at 1,908,874,241, and new FixedBitSet(Integer.MAX_VALUE) works (executed), so the failure depends only on how the set grew.
• Its own invariant check. With assertions on, the constructor's assert verifyGhostBitsClear() throws on the result (:169, :184-185).
• Legal input. IndexWriter.MAX_DOCS = Integer.MAX_VALUE - 128 is the only document cap (a count, so doc IDs run to 2,147,483,518). DocsWithFieldSet is public (since 9.1.0) with no @lucene.internal tag; its javadoc states no limit on doc IDs, and add only rejects out-of-order IDs.
• Intent and precedent. The method was added in LUCENE-5440 (2014) at a reviewer's request so the doc-values writers could grow their docs-with-field set by doc ID. The same commit gave LongBitSet.ensureCapacity the same shift; LUCENE-6409 (#7469, 5.2.0, "Fixed integer overflow in LongBitSet.ensureCapacity") cast it to long and added TestLongBitSet.testHugeCapacity. That commit edited FixedBitSet.java but not this line; a comment in #7469 quotes the FixedBitSet line only about over-allocation. TestFixedBitSet.testEnsureCapacity uses sets of at most 384 bits (literal sizes 5, 8 and 72; growth makes them 320 and 384 bits, and the reuse call asks for bit 318).

The strongest case for "intended": FixedBitSet is @lucene.internal, the workload is absurd (one in-memory segment of about 1.9 billion nearly empty documents; with ordinary documents the 16 MB RAM buffer and the 1,945 MiB per-thread hard limit flush long before), and the upstream 2B monster tests use only dense fields, so sparse fields in near-2B segments were never meant to be supported.

Why it fails: the path is reached through public API (IndexWriter.addDocument and the public DocsWithFieldSet) with inputs inside every documented limit; no document says sparse fields stop working below MAX_DOCS; the RAM limits make the trigger rare but cannot prevent it, since the jump happens inside one add before any flush can react; the result breaks the method's own javadoc and assertion; and upstream treated the identical LongBitSet overflow as a bug. Internal status and scale lower the priority, not the validity. The reviews by another model family rated the intended-behaviour case weak (a later review by the same family rated it moderate, citing the RAM limits, and still found it defeated), and the intended-behaviour checker found no limit in javadoc, CHANGES, MIGRATE or tests.

The hunt's one-line fix (without its comment line) was run through gradle in a scratch worktree of 645d4fe14a20 (OpenJDK 25.0.3, seed DEADBEEF); the worktree was removed afterwards.

In FixedBitSet.ensureCapacityInternal (:81). Below 2^25 words nothing changes. From 2^25 words the length is Integer.MAX_VALUE, which holds every bit index up to 2,147,483,646, so every doc ID below MAX_DOCS; bits2words(Integer.MAX_VALUE) = 2^25 words fits the array, the extra words are zero, and the top bit of the last word can never have been set, so the ghost-bits invariant holds. A Z3 query proves the capped length is greater than desiredBit and fits the array for one growth step from a set of 1 to 64 bits and every desiredBit up to 2^31 - 2. No int-length FixedBitSet can hold bit index Integer.MAX_VALUE itself; that is NO_MORE_DOCS, not a doc ID.

-      return new FixedBitSet(arr, arr.length << 6);
+      return new FixedBitSet(arr, (int) Math.min((long) arr.length << 6, Integer.MAX_VALUE));

Trade-offs

One long shift and a min on the growth path only; set and get are unchanged. A request for bit 2e9 still allocates 35,156,251 words (281 MB), of which 33,554,432 are addressable.

What the checks validated

• The repro fails on stock (assertions on and off) and passes with the fix in both modes.
• Closest suites (TestFixedBitSet, TestLongBitSet, TestSparseFixedBitSet, TestBitSetIterator, TestDocsWithFieldSet): 5 classes, 81 tests, 0 failures (1 skipped).
• org.apache.lucene.util.* plus index.*DocValues*, index.*Norms* and TestDocsWithFieldSet: 144 classes, 1,327 tests, 0 failures (36 skipped).
• :lucene:core:check -x test (formatting, ecj lint, forbidden APIs) passes with the fix and the test in place.
• Earlier, with the class shadowed: the hunt's and the checkers' tests and 40 upstream TestFixedBitSet and TestDocsWithFieldSet tests pass.

Cap the grown size at bits2words(Integer.MAX_VALUE) words, with an exact allocation on both the preserving and the clearing path.

Trade-offs

Saves up to about 12.8 MB at this size (35,156,251 versus 33,554,432 words), at the cost of more code for a size nobody reaches today; a possible follow-up.

Return new FixedBitSet(arr, desiredBit + 1).

Trade-offs

Callers rely on the length covering the whole array (TestFixedBitSet.testEnsureCapacity reuses up to length() - 2), and every later DocsWithFieldSet.add past that length would allocate a new FixedBitSet object.

Fail loudly when the length does not fit.

Trade-offs

Turns silent loss into a loud failure, but rejects doc IDs that IndexWriter accepts (below MAX_DOCS).

Method: semi-formal (code reading, then an SMT solver, then executed tests), a hunt unit on bit sets, live docs and accept docs.

• The unit wrote int-overflow obligations for the bit-set code; the 2026-10-22 study's overflow inventory had not covered FixedBitSet.
• A Z3 bit-vector model of the growth found a counterexample, the smallest failing desiredBit from a 64-bit set (1,908,874,241), proved the method correct below it, found failing doc IDs below MAX_DOCS from larger earlier arrays too, and proved the saturating long-shift fix.
• JUnit tests on the stock main jar confirmed the negative length and the empty DocsWithFieldSet iterator in both assertion modes, and an end-to-end test (2,000,000,001 documents, one commit) showed the lost value.
• An independent verifier then wrote its own tests from the claim, including its own end-to-end run with numeric, sorted and norms fields.