apache / apache/datasketches-rust

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

Open
#270 4 comments 0 reactions 0 assignees View on GitHub
good first issue help wanted
Dominant language
Rust
Stars
123
Forks
45
Avg merge
9h 3m
Merged PRs (30d)
52

Description

## 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(&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.

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing BloomFilter implementation under datasketches/src/bloom/ and the doctests in datasketches/src/bloom/mod.rs and sketch.rs. Review tests-integration/tests/bloom_test/sketch.rs, CONTRIBUTING.md, and the documented options before deciding between A and B. Done means the chosen API and semantics are documented, tests cover reversibility and flipped queries, the changelog is updated, and cargo x check, cargo x test, and cargo x lint pass.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.