# Edit Distances > StringZilla for Rust `LevenshteinEngine` prepares a batch of queries once — Myers' bit-parallel masks, the capability, and on a device the launch geometry — then scores as many batches of candidates against it as a caller has. Preparation is the expensive half, so a long-lived engine amortizes it across every later round, and the round's scratch grows to fit the widest batch it has seen and is never shrunk. ```rust fn new>(queries: &[Q], symbol: LevenshteinSymbol, stream: &Stream) -> Result; fn distances<'scope>(&'scope mut self, scope: &'scope Scope<'scope, '_>, candidates: StringsView<'scope>, bound: Option, distances: &'scope mut [usize], distances_stride: usize) -> Result<(), Status>; ``` `LevenshteinSymbol::Bytes` counts bytes and `LevenshteinSymbol::Runes` counts UTF-8 runes, each maximal ill-formed subpart decoding to one `U+FFFD`; the two alphabets are one engine and one verb rather than two spellings. Costs are unit — one per substitution, insertion and deletion — and there are no gap costs and no substitution matrix. The output is a `[queries, candidates]` block the caller owns: query `q` against candidate `c` lands at `distances[q * distances_stride + c]`, the stride counting entries rather than bytes and being at least the candidate count. A stride wider than the candidate count is what lets one round fill a sub-block of a larger matrix. A `bound` of `Some(limit)` keeps a distance exact up to `limit` and reports `limit + 1` for every candidate past it, on every backend, so a round can stop early; `None` keeps every distance exact. ```rust use stringzilla::{Capabilities, LevenshteinEngine, LevenshteinSymbol, Stream, StringsView}; let cpu = Stream::default(Capabilities::cpu_enabled()); let mut engine = LevenshteinEngine::new(&["kitten", "saturday"], LevenshteinSymbol::Bytes, &cpu).unwrap(); let mut distances = [0usize; 4]; let candidates = StringsView::from_slices(&["sitting", "sunday"]); cpu.scope(|scope| engine.distances(scope, candidates, None, &mut distances, 2)).unwrap(); assert_eq!(distances[0], 3); // kitten vs sitting assert_eq!(distances[3], 3); // saturday vs sunday // The same engine, a second round over an Arrow tape, no preparation repeated. let mut again = [0usize; 4]; let arrow = StringsView::from_u32_tape(b"mittenkitten", &[0, 6, 12]).unwrap(); cpu.scope(|scope| engine.distances(scope, arrow, None, &mut again, 2)).unwrap(); assert_eq!(again[..2], [1, 0]); // kitten vs mitten and kitten // Bounded at 1, a candidate two edits away reports exactly 2. cpu.scope(|scope| engine.distances(scope, candidates, Some(1), &mut distances, 2)).unwrap(); assert_eq!(distances[0], 2); // kitten vs sitting is 3, past the bound // Runes rather than bytes, for text where a codepoint is the unit. let mut unicode = LevenshteinEngine::new(&["café"], LevenshteinSymbol::Runes, &cpu).unwrap(); let mut one = [0usize; 1]; cpu.scope(|scope| unicode.distances(scope, StringsView::from_slices(&["cafe"]), None, &mut one, 1)).unwrap(); assert_eq!(one[0], 1); ``` `use stringzilla::LevenshteinSymbol;` `use stringzilla::LevenshteinEngine;` ## LevenshteinSymbol Which symbols a batch counts, since the alphabet picks the transpose and the mask layout alike. ```rust pub enum LevenshteinSymbol ``` Corresponds to `sz_levenshtein_symbol_t` in the C API. - `Bytes` = `0`: Every byte is its own symbol, and a distance counts bytes. - `Runes` = `1`: Every UTF-8 rune is one symbol, each maximal ill-formed subpart decoding to one `U+FFFD`. Implements: `Debug`, `Clone`, `Copy`, `StructuralPartialEq`, `PartialEq`, `Eq` ## LevenshteinEngine A batch of prepared queries, scored against as many batches of candidates as a caller has. ```rust pub struct LevenshteinEngine ``` Myers' bit-parallel masks are built once per batch and reused by every round, so the preparation a one-shot distance repeats per pair is paid here exactly once. Construction also fixes the capability and, on a GPU, the launch geometry. The fields mirror `sz_levenshtein_engine_t` one for one and only `count`, [`symbol`](#symbol) and `capability` are read from Rust, so the layout is load-bearing and the engine travels to C by pointer. Owning raw pointers makes it neither `Send` nor `Sync`, which is what the C contract wants: a compute verb grows the engine's round scratch, so it mutates, and every verb below takes `&mut self` for that reason. Examples: ``` use stringzilla::{Capabilities, LevenshteinEngine, LevenshteinSymbol, Stream, StringsView}; let cpu = Stream::default(Capabilities::cpu_enabled()); let mut engine = LevenshteinEngine::new(&["kitten", "saturday"], LevenshteinSymbol::Bytes, &cpu).unwrap(); // A `[queries, candidates]` block, query `q` starting at `q * stride`. let mut distances = [0usize; 4]; let candidates = StringsView::from_slices(&["sitting", "sunday"]); cpu.scope(|scope| engine.distances(scope, candidates, None, &mut distances, 2)) .unwrap(); assert_eq!(distances[0], 3); // kitten vs sitting assert_eq!(distances[3], 3); // saturday vs sunday // A candidate past a bound of 1 reports exactly 2. let candidates = StringsView::from_slices(&["sitting", "sunday"]); cpu.scope(|scope| engine.distances(scope, candidates, Some(1), &mut distances, 2)) .unwrap(); assert_eq!(distances[0], 2); assert_eq!(distances[3], 2); ``` Implements: `Drop` ## new Prepares `queries` with the capabilities of `stream`, like [`Capabilities::cpu_enabled`](https://www.unum.cloud/docs/stringzilla/rust/runtime-dispatch.md#cpu_enabled) or a GPU's [`Capabilities::cuda_enabled`](https://www.unum.cloud/docs/stringzilla/rust/runtime-dispatch.md#cuda_enabled), fixing the capability and, on a GPU, the launch geometry once for every round that follows, on the device `stream` names, which it may join. ```rust pub fn new( queries: &[Query], symbol: LevenshteinSymbol, stream: &Stream, ) -> Result where Query: AsRef<[u8]>, ``` The queries themselves are read on the host, so they need no device residency; everything the engine builds from them does. Ice Lake answers a [`LevenshteinSymbol::Runes`](#Runes) batch through its Skylake kernel, because Ice Lake's byte lanes have no rune arm. ## queries_count Queries the batch holds, which is the first axis of every output. ```rust pub fn queries_count(&self) -> usize ``` ## symbol The alphabet the batch was prepared over. ```rust pub fn symbol(&self) -> LevenshteinSymbol ``` ## distances Queues on the stream of [`scope`](https://www.unum.cloud/docs/stringzilla/rust/runtime-dispatch.md#scope) the edit distances from every prepared query to every candidate, on the capability the constructor fixed. ```rust pub fn distances<'scope>( &'scope mut self, scope: &'scope Scope<'scope, '_>, candidates: StringsView<'scope>, bound: Option, distances: &'scope mut [usize], distances_stride: usize, ) -> Result<(), Status> ``` [`distances`](#distances) receives a `[queries, candidates]` block: query `q` against candidate `c` lands at `distances[q * distances_stride + c]`, the stride counting entries rather than bytes and being at least the candidate count. The round's scratch grows here when a batch needs more than the last one did, and is never shrunk. A `bound` of `Some(limit)` keeps a distance exact up to `limit` and reports `limit + 1` for every candidate past it, on every backend, which lets a round stop early. `None` keeps every distance exact. A GPU engine takes candidates and [`distances`](#distances) in memory its device reaches, such as a [`Strings`](https://www.unum.cloud/docs/stringzilla/rust/types.md#Strings) and a `Vec` in a [`UnifiedAllocator`](https://www.unum.cloud/docs/stringzilla/rust/memory-operations.md#UnifiedAllocator). A stream of another group than the engine's is refused with [`Status::DeviceMemoryMismatch`](https://www.unum.cloud/docs/stringzilla/rust/types.md#DeviceMemoryMismatch).