fst_incremental

An updatable finite state set for Rust. fst::Set is compact and fast to query but immutable once built; IncrementalFstSet puts a sorted in-memory mutation buffer in front of one, so inserts and removes are cheap and reads still see the current state. The buffer is folded back into a fresh FST when it grows past a configured threshold. Persistence stays yours to drive: the crate opens no files, and every mutation reports whether the FST or only the buffer changed, so the expensive write can be skipped. Full walkthrough in the usage guide, signatures in the API reference.

Example

use fst_incremental::{FstChangeType, IncrementalFstSet};

let set = IncrementalFstSet::new(None).unwrap();
set.insert(b"apple".to_vec()).unwrap();
set.insert(b"apricot".to_vec()).unwrap();
assert!(set.contains(b"apple").unwrap());

set.remove(b"apple").unwrap();
assert!(!set.contains(b"apple").unwrap());

assert_eq!(set.force_rebuild().unwrap().change_type, FstChangeType::FstRebuilt);

Install

[dependencies]
fst_incremental = "1"

The fst crate is re-exported as fst_incremental::fst, so you do not need your own dependency on it to name an Automaton or bring Streamer into scope.

Feature	Default	Effect
`serde`	yes	Derives `Serialize`/`Deserialize` on `SerializableFstBuffers` and `CompactArenaSet`, so the mutation buffer can be persisted in a format of your choosing.

What to reach for

You want to	Use
Build a set in memory	`IncrementalFstSet::new`
Load one from FST bytes you already hold	`IncrementalFstSet::from_data`
Load a large one without reading it in	`IncrementalFstSet::from_persisted_mmap`
Add or remove a single key	`insert`, `remove`
Load many keys at once	`bulk_insert`, then `finish_bulk_operations_and_rebuild_if_needed`
Test membership	`contains`
Walk every key in order	`stream`
Run an automaton (prefix, fuzzy, regex) over the set	`search`
Decide what needs writing to disk	the `FstChangeType` on every mutation result
Save the set	`persisted_fst_as_bytes` plus `buffers_snapshot`
Control when rebuilds happen	`FstConfigOptions`
See what rebuilds are costing	`get_metrics`

Status

Stable. The public API is frozen for the 1.x line.

Measured figures for every operation, and a comparison against the pre-rewrite implementation, are in docs/benches.

Minimum supported Rust version is 1.85, required by edition 2024. An MSRV increase is a minor version bump.

License