tisonkun opened a new issue, #270: URL: https://github.com/apache/datasketches-rust/issues/270
## 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) ```rust 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. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
