FixedBitSet and LongBitSet equals depend on the backing array capacity, not only on the bits

FixedBitSet(long[] storedBits, int numBits) and LongBitSet(long[] storedBits, long numBits) accept a backing array that is larger than needed, as long as the extra words are clear. Each set remembers numWords, the number of words it actually uses, and hashCode, cardinality, iteration and the bulk operations all stop there. equals does not: after checking numBits it calls Arrays.equals(bits, other.bits), which also compares the two array lengths. So two sets with the same length and the same bits, one over long[1] and one over long[2], have equal hash codes but are not equal; a hash lookup with one misses the other, and a clone of an oversized set is unequal to an exact-size copy. It has been so since 4.0.0. The only non-test call of a bit-set equals found (RunAutomaton) uses exact-size sets, so no index or search result is known to be affected; the fix is one line per class: compare only the first numWords words.

• FixedBitSet.java:146-150: FixedBitSet(int numBits) allocates exactly bits2words(numBits) words, so numWords == bits.length.
• FixedBitSet.java:152-170: FixedBitSet(long[] storedBits, int numBits) sets numWords = bits2words(numBits), rejects only an array that is too small, and keeps the array as it is, so bits.length may exceed numWords. Its javadoc: "The storedBits array must be large enough to accommodate the numBits specified, but may be larger. In that case the 'extra' or 'ghost' bits must be clear". With assertions on it checks that (verifyGhostBitsClear, :183-193).
• FixedBitSet.java:833-846, equals: returns false if numBits differ, else return Arrays.equals(bits, other.bits); (:845). java.util.Arrays.equals(long[], long[]) is false whenever the two lengths differ.
• FixedBitSet.java:848-859, hashCode: for (int i = numWords; --i >= 0; ). Equal numBits means equal numWords, so two sets with the same bits hash the same whatever their capacity. cardinality, nextSetBit, or/and/andNot and the static count helpers also use numWords.
• FixedBitSet.java:826-830, clone(): copies into new long[this.bits.length], so a clone keeps the extra capacity.
• LongBitSet.java:85-103, :427-441 (line 440 is the same Arrays.equals), :443-454, :420-424: identical.
• Not a trigger: ensureCapacity (FixedBitSet.java:81, LongBitSet.java:55) builds the new set with numBits = arr.length << 6, so its array is exact.

new FixedBitSet(64) and new FixedBitSet(new long[2], 64): length 64/64, cardinality 0/0, hashCode -1737092556/-1737092556 (0x98761234), equals false/false (both directions). The study's variant with bits {0, 7, 63, 64, 99} in 100-bit sets over long[2] vs long[5]: cardinality 5/5, hashCode equal, equals false; HashSet.contains with the roomy set returns false; the same for LongBitSet.

• Who is hit. Code that calls equals on, or hashes, these sets when at least one was built with the two-argument constructor over a larger array, or is a clone of such a set, and the other was not. It gets "not equal" for equal sets; HashSet/HashMap lookups miss.
• No affected Lucene code path found. A bytecode scan of the built Lucene jars finds one direct call of a bit-set equals or hashCode in non-test code, RunAutomaton.equals (RunAutomaton.java:200), whose accept set is new FixedBitSet(size) (:69), always exact. Tests also compare bit sets (TestFixedBitSet.java:274-284, TestLongBitSet.java:201-211, TestScorerPerf.java:131, TestBooleanQuery.java:461), all built with the exact-size constructor. The scan cannot see calls through Object.equals, such as a set used as a collection key; a source search found no map or set keyed by a bit set (as Michael McCandless wrote on LUCENE-3531, crediting Uwe Schindler, FixedBitSet's equals/hashCode are "horribly costly" as cache keys), and downstream code was not checked. Lucene does build oversized sets (bkd/DocIdsWriter.java:276-284, over a reused scratch array) but only iterates them.
• Default vs opt-in. No index, query or codec setting reaches it; only direct use of these public @lucene.internal classes.
• Scale. None: any size, from 0 bits up; one spare word in the backing array is enough (executed for 0, 1, 63, 64, 65 and 1000 bits, both classes, -ea and -da).
• Severity. A wrong boolean, and only ever "not equal": it never makes two different sets equal. No crash and no wrong search results were found.

One test class, one method, nothing random (the seed only satisfies LuceneTestCase). Two 64-bit sets with no bits set, backed by long[1] and long[2]; the extra word is 0, as the constructor requires, so the run passes verifyGhostBitsClear with assertions on. LongBitSet has the identical line and fails the same way (shown by the tie-break and study runs, not by this test).

Both sides print as FixedBitSet@98761234: that is Object.toString, which shows the (equal) hashCode.

Regression test: this same test. It fails on stock main and passes with the fix.

cp $REPRO/TestFixedBitSetEqualsBackingCapacity.java $LUCENE/lucene/core/src/test/org/apache/lucene/util/
cd $LUCENE && ./gradlew :lucene:core:test --tests org.apache.lucene.util.TestFixedBitSetEqualsBackingCapacity -Ptests.seed=DEADBEEF -Ptests.asserts=true
# same failure with -Ptests.asserts=false

# gradle, main 645d4fe14a20, seed DEADBEEF, -Ptests.asserts=true (excerpt; ... marks left-out lines)
TestFixedBitSetEqualsBackingCapacity > testEmptySetsWithDifferentBackingArraysAreEqual FAILED
    java.lang.AssertionError: 64 bits, none set, backing long[1] vs long[2] expected: org.apache.lucene.util.FixedBitSet<org.apache.lucene.util.FixedBitSet@98761234> but was: org.apache.lucene.util.FixedBitSet<org.apache.lucene.util.FixedBitSet@98761234>
        at __randomizedtesting.SeedInfo.seed([DEADBEEF:A8A7AF7D109AA018]:0)
        at org.junit.Assert.fail(Assert.java:89)
        at org.junit.Assert.failNotEquals(Assert.java:835)
        at org.junit.Assert.assertEquals(Assert.java:120)
        at org.apache.lucene.util.TestFixedBitSetEqualsBackingCapacity.testEmptySetsWithDifferentBackingArraysAreEqual(TestFixedBitSetEqualsBackingCapacity.java:25)
...
:lucene:core:test (FAILURE): 1 test, 1  failure
...
1 test completed, 1 failed
...
BUILD FAILED in 1m 38s

# -Ptests.asserts=false: the same AssertionError; 10.5.2 (-ea and -da) and 9.12.3: the same
# with the fix: 1 test, 0 failures, both ways

# core-only probe, the same line on all 18 failing releases and pre-releases run (4.0.0-BETA .. 10.6.0) and main
length 64/64 cardinality 0/0 hashCode -1737092556/-1737092556 equals false/false

• The documented contract. LongBitSet.equals: /** returns true if both sets have the same bits set */ (LongBitSet.java:427). FixedBitSet.equals carried the same sentence (4.2.0 FixedBitSet.java:410) until LUCENE-6427 (701b7ddf3a2, 2015) removed it in a "Deleted obsolete doc comments on @Override methods" cleanup of duplicated javadocs.
• Oversized arrays are a documented input (FixedBitSet.java:152-159, LongBitSet.java:85-92).
• hashCode, cardinality, iteration and the bulk operations use the logical bound. LUCENE-4693 (#5758, type:bug, 4.2.0, 44f4f8b9492): with an oversized long[] "the FixedBitSet can return wrong results since we use words.length (bits.lenght) as the bounds ... We should use the actual bound rather than the size of the array" (as Simon Willnauer wrote there). That commit moved hashCode, iteration and the bulk operations to the logical word count; equals stayed on the whole array. Its new test filled the unused words with random longs. A few methods do see the whole array: clear() clears it, ramBytesUsed() counts it, getBits() returns it, clone() copies it, and FixedBitSet.scanIsEmpty compares chunks that can reach past numWords (FixedBitSet.java:710-711). They report memory or representation, or read words the contract keeps clear, so with clear extra words none of them changes a result.
• Tests. TestFixedBitSet.makeFixedBitSet (:329-333) and TestLongBitSet.makeLongBitSet (:276-280) build oversized sets, but the equality tests (TestFixedBitSet.java:269-310) use exact-size sets only.
• Precedent. The predecessor OpenBitSet.equals had the same javadoc and explicitly ignored trailing zero words (4.2.0 OpenBitSet.java:869-893); LUCENE-2216 fixed, as a bug, "OpenBitSet.hashCode returned different hash codes for sets that only differed by trailing zeros" (CHANGES.txt:18372).
• What it is not. Java's equals/hashCode contract is not broken: unequal objects may share a hash code. The defect is that equals disagrees with the value semantics LongBitSet.equals documents, for inputs both constructors allow.

The strongest case, from the cross-model reviewer (rated "moderate"): both classes are @lucene.internal, expose their array (getBits()), show their capacity in ramBytesUsed, clone and clear, and kept the whole-array equals through LUCENE-4693 and LUCENE-6427; FixedBitSet.equals has no javadoc today, and Object.equals does not itself demand value equality. So capacity could be part of the value.

Why it fails: @lucene.internal renders as "This API is for internal purposes only and might change in incompatible ways in the next release" (RenderJavadocPlugin.java:506), a compatibility notice, not a licence for wrong answers; upstream fixed this very defect family in these classes as bugs. LongBitSet.equals states value semantics in writing; FixedBitSet's identical sentence went in a doc cleanup, and neither issue thread discusses equals. hashCode was deliberately moved off the capacity (LUCENE-4693), which points the same way; the methods that do show the capacity report memory or representation, not which bits are set.

One fix was validated through gradle in a scratch worktree of 645d4fe14a20; a documentation-only alternative is listed but was not run.

FixedBitSet.java and LongBitSet.java, one line each:

--- a/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
+++ b/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java
@@ -842,7 +842,7 @@
       return false;
     }
     // Depends on the ghost bits being clear!
-    return Arrays.equals(bits, other.bits);
+    return Arrays.equals(bits, 0, numWords, other.bits, 0, other.numWords);
   }
--- a/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java
+++ b/lucene/core/src/java/org/apache/lucene/util/LongBitSet.java
@@ -437,7 +437,7 @@
       return false;
     }
     // Depends on the ghost bits being clear!
-    return Arrays.equals(bits, other.bits);
+    return Arrays.equals(bits, 0, numWords, other.bits, 0, other.numWords);
   }

Trade-offs

• numBits is already checked equal, so both ranges have the same length; the fix uses the JDK's ranged Arrays.equals overload and compares no more words than before (performance not measured).
• It relies on clear ghost bits, which the constructors already require and hashCode already assumes; the "Depends on the ghost bits being clear!" comment stays true. The constructors check that only with assertions (assert verifyGhostBitsClear()), and getBits() lets a caller break it later.
• Sets of the same capacity whose extra words are clear compare exactly as before. Only sets whose extra words are not clear, a state the contract forbids, can compare differently: those words are now ignored. Like hashCode, the fix still compares the unused high bits of the last word in use, which must be clear too.

What the checks validated

• Scratch worktree of 645d4fe14a20, gradle --offline, OpenJDK 25.0.3, seed DEADBEEF. Stock: the repro fails with assertions on and off. With the fix: the repro passes both ways; TestFixedBitSet, TestLongBitSet, TestSparseFixedBitSet, TestBitSetIterator and the whole org.apache.lucene.util.automaton test package (home of RunAutomaton, the only non-test caller found) pass (assertions on and off: 20 suites, 314 tests, 0 failures, 3 nightly/monster tests skipped); the :lucene:core format, ECJ and forbidden-apis checks pass. No stock run of the same 20 suites was recorded; the second adjudication ran TestFixedBitSet + TestLongBitSet stock and fixed.
• Earlier runs: the shadowed fix makes the minimal test pass with -ea and -da; the tie-break's LongBitSet test passes; TestFixedBitSet + TestLongBitSet 44/44 with the fix over 2 seeds (tie-break) and 45 tests over 5 seeds (study); on 4.0.0 and 4.2.0 an equivalent fix over the words in use (written for those versions' fields) makes the history probe pass.

Change LongBitSet.equals' javadoc, and add one to FixedBitSet.equals, saying that sets over different-size arrays are never equal.

Trade-offs

Keeps today's behaviour, but leaves equals inconsistent with hashCode, cardinality, iteration and the bulk operations, and with the "may be larger" constructors. Not recommended; not run.

A static-analysis pass over lucene-core (SpotBugs, Error Prone with its default checks plus 40 that Lucene turns off, CodeQL, PMD, Checker Framework) produced thousands of findings; 62 triage rows were read by hand. Error Prone's InconsistentHashCode reported "hashCode includes the fields [numWords], which equals does not". That reason is wrong: numWords follows from numBits, which equals does check. Reading the method showed the real problem, the whole-array Arrays.equals. The check is OFF in Lucene's build (ErrorPronePlugin.java:493, "noisy").

An independent verifier then wrote its own deterministic tests (4 fail, 3 controls pass) and validated the one-line fix against TestFixedBitSet and TestLongBitSet.