FixedBitSet.approximateCardinality can return a negative estimate for sets of 2^31-63 bits or more, because its scale factor 64 * numWords overflows int

FixedBitSet.approximateCardinality() estimates the number of set bits by pop-counting 16 of every 1,024 words and scaling the sum by (interval / rangeLength) * numWords / maxWord, that is 64 × numWords / maxWord. That factor is computed in a 32-bit int (FixedBitSet.java:280). For the 63 largest legal lengths, 2^31-63 to 2^31-1 bits, the set has 2^25 words, 64 * numWords is 2^31 and wraps to Integer.MIN_VALUE, and the factor becomes -64: one set bit in a sampled word gives -64, an all-ones set -2,147,418,112, and new BitDocIdSet(bits) throws "cost must be >= 0".

The class documents these lengths as legal (it sends users to LongBitSet only above 2.1B bits) and its own test asserts the 2^25-word count, but nothing in Lucene builds such a set: doc-ID sets stop at IndexWriter.MAX_DOCS = 2^31-129 bits. So it is a latent bug for code that builds such a long FixedBitSet itself, for example over other int ids. It came with the sampled estimate in 9.1.0 (#710); 9.0.0 returned the exact count. A (long) cast fixes it and leaves every smaller set's result unchanged.

public int approximateCardinality() {                                     // FixedBitSet.java:259
  final int rangeLength = 16;                                             // :265
  final int interval = 1024;                                              // :266
  if (numWords <= interval) {                                             // :268
    return cardinality();
  }
  long popCount = 0;
  int maxWord;
  for (maxWord = 0; maxWord + interval < numWords; maxWord += interval) { // :274
    for (int i = 0; i < rangeLength; ++i) {
      popCount += Long.bitCount(bits[maxWord + i]);
    }
  }
  popCount *= (interval / rangeLength) * numWords / maxWord;              // :280, int on the right
  return (int) popCount;                                                  // :281
}

1. numWords = bits2words(2^31 - 1) = ((2^31 - 2) >> 6) + 1 = 2^25 = 33,554,432 (:86-90, :146-150). Upstream TestFixedBitSet.testBits2Words asserts this value.
2. The loop samples 16 words at words 0, 1,024, 2,048, ... and stops with maxWord = 2^25 - 1,024 = 33,553,408: 32,767 samples.
3. :280 evaluates (1024 / 16) * numWords / maxWord in int: 64 × 33,554,432 = 2,147,483,648 = 2^31 wraps to -2,147,483,648, and / 33,553,408 truncates to -64. Only then is the value widened to long.
4. The method returns the sampled count times -64: one set bit in a sampled word gives -64; all bits set give 33,553,408 × -64 = -2,147,418,112.

• Exactly 63 lengths. bits2words reaches 2^25 at 2^31-63 bits, and an int length cannot exceed 2^31-1. Every smaller set has at most 2^25 - 1 words, so 64 * numWords <= 2^31 - 64 fits; the runs at 2^31-64 bits (pass) and 2^31-63 bits (fail) confirm the edge. A Z3 bit-vector query agrees: it returned a counterexample inside this window (2,147,483,596 bits) and proved no overflow for any length up to MAX_DOCS.
• Any set bit in a sampled word is enough, and one is needed. An all-ones set is not needed. A set whose set bits all lie outside the sampled words (the first 16 of every 1,024), for example only bit 1,024 (word 16), or an empty set, gets 0, as it would with the fix. That 0 for a sparse set is the estimator's normal sampling (2^31-64 bits with only bit 1,024 set also gives 0), not this bug.
• Consumers. BitDocIdSet(BitSet) uses the estimate as its cost (BitDocIdSet.java:51-53); BitDocIdSet and BitSetIterator reject a negative cost (BitDocIdSet.java:39-45, BitSetIterator.java:67-70). HnswGraphSearcher.search takes min(approximateCardinality(), graph.size()) as the filtered count (HnswGraphSearcher.java:99-102), asserts it is >= 0 (:127) and runs the filtered strategy only when it is > 0 (:142).

• Who. Code that allocates such a set through the public constructor (256 MiB), sets at least one bit in a sampled word, and calls approximateCardinality(), wraps the set in BitDocIdSet(BitSet), or passes it to HNSW search as accepted ordinals. No setting is involved.
• Not Lucene itself. Every in-tree consumer gets a set sized by a segment's maxDoc or an HNSW graph's size: BitDocIdSet(BitSet) from WithinPrefixTreeQuery and RandomSamplingFacetsCollector, and HnswGraphSearcher. All are at most IndexWriter.MAX_DOCS = 2^31-129, 66 bits below the first failing length.
• Effects (executed). A negative estimate; IllegalArgumentException from BitDocIdSet and BitSetIterator; in HNSW search an AssertionError with assertions on. With assertions off HNSW search takes the unfiltered strategy, even where a correct estimate would pick the filtered one (accepted share below 60% by default, HnswGraphSearcher.java:139-143, KnnSearchStrategy.java:80-83). It still checks the accepted set before collecting each result (HnswGraphSearcher.java:349), so no filtered-out ordinal comes back, but the neighbours can differ: in a probe of 25 queries with half the ordinals accepted, 0 of 250 hits were filtered out, and recall was 0.996 against 0.968 for a same-bits set of legal length. No corruption, no hit outside the accepted set, no hang.
• Likelihood: contrived. No downstream call site found builds a set this long (a read-only search of Elasticsearch, OpenSearch and Solr, not exhaustive).

• Smallest input. One set bit at the largest length. The smallest failing length, 2^31-63 bits, gives the same values; 2^31-64 bits passes.
• Heap. The 256 MiB array fits in gradle's default 512 MB test heap.
• Releases. The same file runs unchanged against the 10.6.0 jars and fails there too.
• As the regression test: this same test, for example as a method of TestFixedBitSet. It passes with the fix.

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

# gradle, main 645d4fe14a20, seed DEADBEEF, assertions on (the same with -Ptests.asserts=false)
TestFixedBitSetApproximateCardinalityOverflow > testIntegerMaxValueBitsOneSet FAILED
    java.lang.AssertionError: expected approximateCardinality() >= 0 but was -64
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:6078D2D47D3316B2]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.assertTrue(Assert.java:42)
        at org.apache.lucene.util.TestFixedBitSetApproximateCardinalityOverflow.testIntegerMaxValueBitsOneSet(TestFixedBitSetApproximateCardinalityOverflow.java:28)

# 10.6.0, assertions on and off: the same AssertionError (-64)

# other values (verifier runs on main): 2^31-63 or Integer.MAX_VALUE bits, all set: -2147418112;
# new BitDocIdSet(bits) with bit 0 set: IllegalArgumentException: cost must be >= 0, got -64;
# 2^31-64 bits, all set: positive, within 1% of the exact count

# with the fix: BUILD SUCCESSFUL, 1 test, assertions on and off

• Contract. "Return an approximation of the cardinality of this set. Some implementations may trade accuracy for speed ..." (BitSet.java:76-81).
• The length is legal. "accessed with an int index ... If you need to manage more than 2.1B bits, use LongBitSet" (FixedBitSet.java:24-27); the constructor accepts Integer.MAX_VALUE (:146-150); testBits2Words asserts bits2words(Integer.MAX_VALUE) == 1 << (31 - 6) (TestFixedBitSet.java:421).
• Lucene rejects the value itself. BitDocIdSet and BitSetIterator throw on a negative cost; HNSW search asserts the count is >= 0.
• The sibling clamps. SparseFixedBitSet.approximateCardinality() returns (int) Math.min(length, estimate) (SparseFixedBitSet.java:113-124).
• History. 9.0.0 returned the exact cardinality(). #710's review covered making the base method abstract, removing the BitUtil.pop_* helpers and small sets, not lengths near Integer.MAX_VALUE, and its test uses 100,000 to 200,000 bits (TestFixedBitSet.java:42-53). e999056c19d (2022, "avoid division by zero on small sets") already fixed the small end of this expression. No javadoc, CHANGES or MIGRATE entry, comment, test or PR discussion limits the method below 2^31-63 bits.

Strongest case for "not a bug" (the cross-model reviews voted not real on this ground only and rated it strong): FixedBitSet, BitSet and BitDocIdSet are @lucene.internal, which the javadoc renders as "This API is for internal purposes only and might change in incompatible ways in the next release"; no Lucene entry point can build a set this long; and the method is allowed to be inaccurate. Maintainers could reasonably close it as unsupported use of an internal utility.

Why it is still a bug: the note limits who should use the classes and how stable their API is; it does not say the method may return invalid values for lengths the class accepts. The public constructor produces the failing state directly, at a length the class documents and its test asserts, and "trade accuracy for speed" does not cover a negative count, which Lucene's own consumers reject. Both reviewers reproduced it and agreed on the cause and the fix. The works-as-designed reviewer called the negative value "undocumented and inconsistent with the method contract, sibling implementation, and tests"; the refute reviewer wrote "The negative arithmetic result is not specifically intended".

What it does establish: low priority, and "won't fix" would be a fair outcome.

Three options; option A was applied in a scratch worktree of main 645d4fe14a20 and run against the minimal test, the closest suites and core's static checks.

In approximateCardinality() only, one line (+2/-1 with a comment).

// long: (interval / rangeLength) * numWords is 2^31 for sets of 2^25 words and overflows int
popCount *= (long) (interval / rangeLength) * numWords / maxWord;
return (int) popCount;

Trade-offs

• No change below the window. For every set of fewer than 2^25 words the int product never overflowed, so the result is the same value as before.
• The result fits in int. popCount is at most the number of sampled bits, which equals maxWord, so the result is at most 64 × numWords; at 2^25 words the integer division gives a factor of exactly 64, so the largest result is 64 × 33,553,408 = 2,147,418,112.
• Cost. One widening multiply per call, outside the loop.

What the checks validated

• The minimal test fails before the change and passes after it, with assertions on and off (gradle, scratch worktree of 645d4fe14a20; also standalone).
• Closest suites pass (61 tests, 0 failures): TestFixedBitSet (34), TestFixedBitDocIdSet (7), TestBitSetIterator (11), TestDocIdSetBuilder (9).
• :lucene:core:check -x test passes with the test in the tree (google-java-format, ecj lint, forbidden APIs, license checks).
• Earlier, on main ea57360912ed: the finder's test, an independent verifier's 5 tests and the cross-model reviewers' tests pass with the same cast.
• Not run: the whole :lucene:core:test; the change leaves every result below 2^25 words unchanged.

return (int) Math.min(length(), popCount); after option A.

Trade-offs

Defence in depth if the arithmetic changes later. Without A it only hides the problem (a negative value stays negative under min). Optional; not validated.

Reject lengths above 2^31-64 in the constructor, or document that the estimate is valid only below 2^25 words.

Trade-offs

Shrinks a range the class documents and its own test asserts, to avoid a one-line fix. Not recommended; not validated.

• The hunt unit covered bit sets, live docs and accepted-docs filters. While writing its integer-overflow obligations, the finder read approximateCardinality() and noticed the int product. Each obligation models Java int as a 32-bit bit-vector with wrap-around, with Lucene's documented limits (MAX_DOCS, the maximum array length) as preconditions.
• The obligation "64 * numWords does not overflow for legal FixedBitSet lengths" returned a counterexample, numBits = 2,147,483,596; the obligation "no overflow for lengths <= MAX_DOCS" was proved, which is why no doc-ID bit set is affected.
• A JUnit test using public constructors and methods only on the stock main build then failed with -2,147,418,112 for an all-ones set of Integer.MAX_VALUE bits, while a 2^31-64 control passed. Independent verifiers reproduced it with their own tests, found the single-bit value -64, and ran it across releases.