# `ExDataSketch.FilterChain`
[🔗](https://github.com/thanos/ex_data_sketch/blob/main/lib/ex_data_sketch/filter_chain.ex#L1)

Capability-aware composition framework for chaining membership filters.

FilterChain composes membership filter structures into ordered query pipelines.
It enables lifecycle-tier patterns such as a hot Cuckoo filter (absorbing writes)
followed by a cold XorFilter (compacted snapshot).

## Chain Roles

Each filter type has valid chain positions:

- **Front/Middle/Terminal**: Bloom, Cuckoo, Quotient, CQF -- dynamic filters
  that support member? and put.
- **Terminal only**: XorFilter -- static, no incremental insert. Must be the
  last query stage.
- **Adjunct only**: IBLT -- reconciliation helper, not in the query path.

## Query Semantics

`member?/2` evaluates query stages in order with short-circuit semantics:
a definite "no" from any stage returns `false` immediately. Adjuncts are
never queried.

## Insert Semantics

`put/2` forwards to all query stages that support `:put`, skipping static
stages (XorFilter). Returns `{:ok, chain}` or `{:error, :full}` if a
Cuckoo stage is full.

## Delete Semantics

`delete/2` checks that ALL query stages support `:delete`. If any stage
lacks delete support (e.g., Bloom), raises `UnsupportedOperationError`.

## Binary Format (FCN1)

FilterChain serializes each stage independently using its own `serialize/1`
(always the default `:v2` format -- FilterChain does not currently thread
a `:format` option through to its stages), wrapped in a chain manifest
with magic bytes "FCN1". This is a bespoke container format, not an
`ExDataSketch.Codec`/EXSK frame -- it has no `Codec.sketch_id` of its
own. The `format: :v1` escape hatch available on every other sketch
family (opt-in legacy EXSK v1 output for v0.7.x readers, see e.g.
`ExDataSketch.Bloom.serialize/2`) therefore does not apply to
`FilterChain.serialize/1` itself.

# `t`

```elixir
@type t() :: %ExDataSketch.FilterChain{adjuncts: [struct()], stages: [struct()]}
```

# `add_stage`

```elixir
@spec add_stage(
  t(),
  struct()
) :: t()
```

Adds a filter stage to the chain.

The stage is automatically classified based on its module type:
- IBLT goes to the adjuncts list (not in query path)
- XorFilter is appended as a terminal query stage
- All other filters are appended as query stages

Raises `InvalidChainCompositionError` if the composition is invalid
(e.g., adding a query stage after a XorFilter terminal).

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
    iex> length(ExDataSketch.FilterChain.stages(chain))
    1

# `adjuncts`

```elixir
@spec adjuncts(t()) :: [struct()]
```

Returns the list of adjunct stages.

## Examples

    iex> ExDataSketch.FilterChain.adjuncts(ExDataSketch.FilterChain.new())
    []

# `capabilities`

Returns the set of capabilities supported by FilterChain.

# `count`

```elixir
@spec count(t()) :: non_neg_integer()
```

Returns the sum of counts across all query stages.

## Examples

    iex> ExDataSketch.FilterChain.count(ExDataSketch.FilterChain.new())
    0

# `delete`

```elixir
@spec delete(t(), term()) :: t()
```

Deletes an item from all query stages.

Raises `UnsupportedOperationError` if any query stage does not support
`:delete` (e.g., Bloom or XorFilter). Returns a bare chain rather than
`{:ok, chain}`: a per-stage "item not found" (e.g. `Cuckoo.delete/2`'s
`{:error, :not_found}`) is already absorbed as a safe no-op before it
ever reaches this function, and an unsupported stage raises up front
via `validate_all_support_delete!/1` -- there is no `{:error, ...}`
case for a caller to ever pattern-match against, so unlike `put/2`/
`put_many/2` (which really can fail with `{:error, :full}`), wrapping
the result in `{:ok, ...}` would only add friction.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> cuckoo = ExDataSketch.Cuckoo.new()
    iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.put(cuckoo, "hello")
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, cuckoo)
    iex> chain = ExDataSketch.FilterChain.delete(chain, "hello")
    iex> ExDataSketch.FilterChain.member?(chain, "hello")
    false

# `deserialize`

```elixir
@spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()}
```

Deserializes an FCN1 binary into a FilterChain.

Returns `{:ok, chain}` on success or `{:error, reason}` on failure.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
    iex> binary = ExDataSketch.FilterChain.serialize(chain)
    iex> {:ok, recovered} = ExDataSketch.FilterChain.deserialize(binary)
    iex> length(ExDataSketch.FilterChain.stages(recovered))
    1

# `member?`

```elixir
@spec member?(t(), term()) :: boolean()
```

Tests whether an item may be a member by querying all stages in order.

Short-circuits on the first `false` result. Adjuncts are not queried.
Returns `false` if the chain has no query stages.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> bloom = ExDataSketch.Bloom.new(capacity: 100) |> ExDataSketch.Bloom.put("hello")
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, bloom)
    iex> ExDataSketch.FilterChain.member?(chain, "hello")
    true

# `new`

```elixir
@spec new() :: t()
```

Creates an empty FilterChain.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> ExDataSketch.FilterChain.stages(chain)
    []

# `put`

```elixir
@spec put(t(), term()) :: {:ok, t()} | {:error, :full}
```

Inserts an item into all query stages that support `:put`.

Skips static stages (XorFilter). Returns `{:ok, chain}` on success
or `{:error, :full}` if a Cuckoo stage is full.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
    iex> {:ok, chain} = ExDataSketch.FilterChain.put(chain, "hello")
    iex> ExDataSketch.FilterChain.member?(chain, "hello")
    true

# `put_many`

```elixir
@spec put_many(t(), Enumerable.t()) :: {:ok, t()} | {:error, :full, t()}
```

Inserts every item in `items` into all query stages that support
`:put`, batching through each stage's own `put_many/2` instead of
looping `put/2` once per item.

This matters: every family's single-item `put/2` runs in the Pure
backend regardless of configured `:backend` (there's no per-item Rust
NIF for any family), and the Pure backend's immutable-binary state
means a single-item write reconstructs the *entire* state binary --
O(state size) per call. `put_many/2` decodes once, applies every
item, and encodes once per stage (Rust-accelerated where a stage's
own backend supports it), instead of paying that O(state size) cost
per item per stage. Confirmed: 10,000 items into a two-stage
`[Bloom, Cuckoo]` chain (500,000 capacity each) via the old
item-by-item `update_many/2` took ~2.3s; the same batch through this
function takes under a millisecond.

Skips static stages (XorFilter). Returns `{:ok, chain}` if every
stage's batch succeeded, or `{:error, :full, partial_chain}` if a
stage filled up partway through its own batch -- stages before the
failing one fully applied their batch; the failing stage reflects
however much of the batch fit before it filled up; stages after it
are unchanged.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
    iex> {:ok, chain} = ExDataSketch.FilterChain.put_many(chain, ["a", "b", "c"])
    iex> ExDataSketch.FilterChain.member?(chain, "a")
    true

# `serialize`

```elixir
@spec serialize(t()) :: binary()
```

Serializes the FilterChain to the FCN1 binary format.

Each stage is serialized independently using its own `serialize/1`,
then wrapped in a chain manifest.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
    iex> binary = ExDataSketch.FilterChain.serialize(chain)
    iex> <<"FCN1", _rest::binary>> = binary
    iex> byte_size(binary) > 0
    true

# `size_bytes`

```elixir
@spec size_bytes(t()) :: non_neg_integer()
```

# `stages`

```elixir
@spec stages(t()) :: [struct()]
```

Returns the list of query stages.

## Examples

    iex> ExDataSketch.FilterChain.stages(ExDataSketch.FilterChain.new())
    []

# `update`

```elixir
@spec update(t(), term()) :: t()
```

Inserts an item into all query stages that support `:put`, raising if a
stage is full.

Added so `ExDataSketch.FilterChain` satisfies the `ExDataSketch.Sketch`
behaviour's generic `update/2` callback, which requires a bare-struct
return. `put/2` (returning `{:ok, chain} | {:error, :full}`) remains the
family-idiomatic name for callers who need to detect a full stage.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
    iex> chain = ExDataSketch.FilterChain.update(chain, "hello")
    iex> ExDataSketch.FilterChain.member?(chain, "hello")
    true

# `update_many`

```elixir
@spec update_many(t(), Enumerable.t()) :: t()
```

Inserts every item in an enumerable via `put_many/2`, raising if a
stage fills up partway through.

Added so `ExDataSketch.FilterChain` satisfies the `ExDataSketch.Sketch`
behaviour's generic `update_many/2` callback, which requires a
bare-struct return. `put_many/2` remains the family-idiomatic name
for callers who need to detect a full stage and keep the partial
result.

## Examples

    iex> chain = ExDataSketch.FilterChain.new()
    iex> chain = ExDataSketch.FilterChain.add_stage(chain, ExDataSketch.Bloom.new(capacity: 100))
    iex> chain = ExDataSketch.FilterChain.update_many(chain, ["a", "b", "c"])
    iex> ExDataSketch.FilterChain.member?(chain, "a")
    true

---

*Consult [api-reference.md](api-reference.md) for complete listing*