BloomFilter: make post-invert semantics observable in the type system

[tisonkun]

Context

BloomFilter::invert() flips every bit in the backing array. #194 raised the resulting contract questions and #202 documented the altered guarantees, but left the API-shape decision open: after inversion the type signature is unchanged and still permits every update operation.

The semantics after inversion are worth pinning down precisely. Let B be the bit array before inversion and S(x) the k hash positions of an item x:

• contains(x) == true after inversion means every position of S(x) was 0 in B, so x was definitely not inserted before the inversion. This direction is certain; it has no error probability.
• contains(x) == false means at least one position of S(x) was 1 in B. All inserted items land here, but so does any absent item with at least one colliding position — with probability roughly 1 - (1 - load_factor)^k, which is close to 1 for typical configurations. So false carries little information.
• Inversion is therefore not the exact logical complement of the pre-inversion answer: a true result requires all k positions to have been clear, not merely one.

For updates after inversion:

• insert(z) only sets bits, so it can only flip query results from false to true — it manufactures new "definitely absent" claims. The claim about z itself is sound only if z was absent before inversion, a precondition the filter cannot check. Existing true answers are never corrupted, since setting bits preserves all-set patterns.
• The opposite update — recording that a newly seen item belongs to the original stream — would require clearing bits, i.e. the deletion a Bloom filter fundamentally cannot support.
• union()/intersect() remain well-defined as raw bit-array boolean operations and, combined with invert(), enable compositions such as approximate set difference (A AND NOT B). invert() is also an exact involution: inverting twice restores the original filter bit-for-bit, guarantees included.

Nothing in the object records that it was inverted, and the serialized format stores only the bit array, so invertedness cannot be persisted without a format change. Any marker is necessarily ephemeral and type-level. This matches the C++ and Java implementations, where invert() is a plain mutating bit operation:

• C++: https://github.com/apache/datasketches-cpp/blob/master/filters/include/bloom_filter.hpp
• Java: https://github.com/apache/datasketches-java/blob/main/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilter.java

Problem

After invert(), a BloomFilter is a valid bit array but no longer satisfies the update-side contract of a set-membership sketch: insert() and contains_and_insert() assert a "definitely absent" fact whose soundness precondition the filter cannot verify. Queries remain well-defined (with the flipped, one-sided meaning above), but nothing in the type system distinguishes the two modes, so unsound updates compile silently.

Design options

A. Documentation only (status quo)

Keep invert(&mut self) and extend the post-invert qualification to the update methods: state that insert() after inversion asserts a caller-guaranteed absence, and that union()/intersect() compose raw bit state. Non-breaking and consistent with C++/Java, but the footgun remains — nothing prevents or flags unsound updates.

B. Consuming invert returning a read-only view (recommended)

impl BloomFilter {
    pub fn invert(self) -> InvertedBloomFilter;
}

impl InvertedBloomFilter {
    /// `true` means the item was definitely not inserted before inversion.
    pub fn contains<T: Hash>(&self, item: &T) -> bool;
    // capacity(), num_hashes(), seed(), bits_used(), load_factor()

    /// Exact round-trip: restores the original filter bit-for-bit.
    pub fn invert(self) -> BloomFilter;

    /// Explicit escape hatch for boolean composition (e.g. A AND NOT B);
    /// the caller takes responsibility for the bit-level interpretation.
    pub fn into_filter(self) -> BloomFilter;
}

• Makes the altered contract observable at compile time: query-only after inversion, with insert()/contains_and_insert() unrepresentable.
• Preserves the legitimate uses: the exact double-invert round-trip and boolean composition both remain possible, the latter through an explicit, documented conversion.
• Wire format unchanged: an inverted filter serializes as its raw bits and deserializes as a plain BloomFilter. If InvertedBloomFilter exposes serialize(), that asymmetry must be documented.

Cost: a breaking change to invert()'s signature, and an API-level (not format-level) divergence from C++/Java.

C. Runtime flag

Track an inverted boolean and panic or no-op on insert() after inversion. Adds per-object state, cannot round-trip through serialization without a format change, and turns a compile-time question into a runtime failure. Not recommended.

Desired outcome

• Decide between A and B (B recommended); C is recorded as rejected.
• If B: add InvertedBloomFilter under datasketches/src/bloom/, change invert() to consume self, move the inverted-semantics documentation onto the new type, and update the doctests in datasketches/src/bloom/mod.rs and sketch.rs.
• Update tests-integration/tests/bloom_test/sketch.rs: test_invert_is_reversible becomes an invert().invert() round-trip; add tests covering the flipped one-sided query meaning (inserted items always return false; true implies definite absence) and into_filter() composition.
• Add a changelog entry per CONTRIBUTING.md.
• Run cargo x check, cargo x test, and cargo x lint before submitting.

[tisonkun]

InvertedBloomFilter

I don't like this name a lot. But the direction looks reasonable.

[v0id-X]

Hi @tisonkun , I'd like to work on this and implement Option B.

Regarding the naming for InvertedBloomFilter: alternatives could be FlippedBloomFilter, NegatedBloomFilter, or ComplementBloomFilter (though keeping InvertedBloomFilter has the advantage of pairing directly with .invert()).

Let me know your preference on the type name, and please assign this to me. I'll follow up with the implementation, updated doctests, and integration tests.

[tisonkun]

@v0id-X You can just submit a PR and ping me as a reviewer.

About naming, I may consider BloomFiliterInvertedView but it reads a bit wordy.

[v0id-X]

I actually like BloomFilterInvertedView, it makes it crystal clear that it's an unmodifiable view rather than a standalone filter. I'll go with that, get the implementation and tests in place, and ping you once the PR is open.

[tisonkun]

Superseded by #278.

Further analysis showed the framing here was wrong: an inverted Bloom filter has no sound standalone query semantics worth encoding in a type (as an absence oracle it is strictly worse than the original filter, whose false answers are already certain), and the only composition with a clean per-item meaning is A AND NOT B. #278 removes invert() and exposes that use case directly as BloomFilter::difference, making the read-only-view design unnecessary.