All notable changes to this project will be documented in this file.
The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.
vinary-tree-interop retained-resource ABI and changed liblevenshtein's
bindings to consume vt.dictionary.v1 resources instead of owning
libdictenstein dictionary constructors or CRUD. Query cursors return leased,
contiguous batches (or a zero-copy reducer callback), retain an O(1)
query-start snapshot, and may outlive both the transducer and source handle.
C/C++, Python custom providers, Java 22 FFM, Clojure, TypeScript, and
ClojureScript facades form the first migration wave. Example and property
tests keep one partially consumed cursor alive across insert, remove, update,
clear, compact, and checkpoint mutations; C ABI tests additionally enforce
lease lifetime and one callback per batch. Native CI covers Linux x86_64 and
aarch64, macOS aarch64, Windows x86_64, BSD targets, and experimental armv7.@vinary-tree/vinary-tree umbrella runtime so related projects
share one resource table. Tier 2 and Tier 3 bindings, including OCaml and
Fortran, are withheld from publication until their older dictionary-owning
facades complete the same migration.liblevenshtein executable, REPL, filesystem grep pipeline, and
archive/document extractors into the new liblevenshtein-cli crate.cli, grep-compression, grep-archives, and
grep-documents feature families and their application-only dependencies.parallel-grep in the
library.MittonCorpus::load_birkbeck_zip; archive-backed corpus fixture
loading is no longer part of the library API.Alignment-expressible Class-A presets and references.
OperationSet::{hamming,indel,bounded_skip}, Unicode-scalar Hamming, and
full/banded insertion-deletion distances expose exact reference semantics.
OperationSet::validate enforces progress, finite non-negative weights,
zero-cost length preservation, checked aggregation, and a 4,096-unit
resource ceiling before generalized traversal. Twenty-thousand generated
cases, an exhaustive 42,395-pair Birkbeck gate, runnable examples, and
Rocq/Dafny/Verus/Z3/cvc5/TLA+ models cross-check the invariants. Dedicated
dictionary walkers remain unshipped because the preregistered structural
reduction threshold was not met.
Exact affine-gap dictionary search. AffineGapParams,
Transducer::query_affine, scaled string/token entry points, and
QueryBuilder::affine_gap expose Gotoh's three-layer recurrence with exact
decimal scaling. The lazy kernel implements layer-aware completion,
operation-derived windows, and formally verified same-index B-4
subsumption; an independent quadratic oracle and 2,000-case differential,
invariant, backend, and policy properties enforce complete result-map and
cost equality. Rocq, Dafny, Verus, Z3/cvc5, and TLA+ cross-check the core
invariants. Cross-index B-5 pruning remains deliberately disabled, with its
minimized unfused-transition counterexample retained as a regression seed.
Budget-bounded unrestricted Damerau–Levenshtein search.
Algorithm::DamerauLevenshtein, Transducer::with_damerau_levenshtein, and
the full Lowrance–Wagner reference DP add true history-composing
transpositions without changing OSA. A DamerauPending macro chain preserves
all Standard paths and refines entry/extension/resolution exactly. Serde,
FromStr, FFI, WASM, REPL, examples, Criterion, 2,000-case differential and
metric properties, a 42,395-pair Birkbeck gate, and Rocq/Verus/SMT/TLA+
evidence ship together. The compact delta ceiling is explicit at 255 and
unsupported weighted/product engines fail rather than silently projecting to
another distance.
Zero-width PositionKind/AutomatonVariant seam. Position remains 24
bytes on 64-bit targets while typed continuation kind and payload now
participate in its total order. Legacy transition and subsumption policy is
selected once per repeated dictionary-edge loop and statically specialized
inside the position loop; the one-position API uses one direct match and an
owned return. Algorithm is now #[non_exhaustive]; downstream exhaustive
matches require a wildcard arm. Property, Rocq, Verus, Z3/cvc5, and TLA+
gates pass. All six pre-registered Criterion suites pass across 423 cases;
the stricter byte-identical-disassembly hypothesis is retained as a documented
negative result because its probe also measured intentional payload and
ownership changes. A separate optimized-LLVM-IR audit passes by showing that
the constant-Standard probe retains no runtime selector, non-Standard leaf,
or selector switch.
Observable elastic-search pruning and a shared UCR harness.
ElasticSearchStats and search_knn_with_stats report prefix, column,
candidate, exact-evaluation, cutoff, node, and edge counts without changing
ordered results. The generalized elastic-ucr --measure experiment runs
MSM, ERP, TWED, discrete Fréchet, or banded DTW under one preregistered
51-dataset protocol, with flat/trie distance agreement, process peak memory,
checksums, paired case outcomes, and deterministic summaries. Rocq, Verus,
Z3/cvc5, example, integration, and 2,000-case property tests enforce result
transparency and counter partitions.
Exact TWED kernel and trie search. TwedConfig implements unit-spaced
Time Warp Edit Distance with a two-row cutoff DP, carry-aware interval
columns, and the $|m-n|*lambda$ candidate bound. MetricTwedConfig
validates finite nu > 0 and lambda >= 0 and alone supplies the static
metric witness; the unrestricted zero-stiffness family remains available
without an unsound marker. Differential, example, property, integration,
Rocq, Verus, Z3/cvc5, documentation, and registered benchmark coverage ship
with the kernel.
Ordered cost-monoid seam. CostMonoid provides a fixed minimum choice,
total ordering, inclusive budget predicate, and lawful accumulation for
UnitCost, additive WeightedCost, and minimax BottleneckCost.
CostScale converts decimal operation weights into checked exact integer
costs without silent rounding or overflow. Rocq, Verus, Z3/cvc5, and
property tests cover the algebra and explicitly delimit IEEE-754 rounding.
Repaired GeneralizedAutomaton acceptance. Runtime operations now drive
the complete alignment, including empty-side behavior, multi-scalar
restrictions, and adjacent transposition. Fractional weights accumulate in
an exact scaled-integer domain instead of truncating to zero. Fallible APIs
report invalid weights, overflow, and the one-million-cell resource guard;
Hamming, indel, bounded-skip, Unicode, and standard semantics are checked
against independent references and formal models.
VersionedQueryCache (liblevenshtein::transducer::VersionedQueryCache) — an
opt-in, dictionary-version-tied cross-query result cache that memoizes
(query, max_distance) → results and self-invalidates on a dictionary version bump
(correct for dynamic dictionaries). On repeated-query workloads a cache hit skips the
automaton state-transition inner loop (≈80% of query CPU per AMD uProf profiling);
measured ≈11,500× faster on a pre-registered repeated-query benchmark
(Welch t p≈3×10⁻¹⁷⁰, Cohen's d≈−81), with cached results proven identical to
uncached. It does not touch the hot path, so unique-query workloads are unaffected. See
docs/scientific-ledger/version-tied-cross-query-result-cache-*.md.
AutomatonZipper::infer_distance previously passed dictionary depth to a
state method whose argument is query length, undercharging shorter terms and
overcharging longer ones. Node, intersection, and zipper traversal now agree;
the true-Damerau separator CA → ABC is retained at distance 2.CandidateIteratorF64 / OperationCostsF64) previously
returned wrong distances whenever insertion or deletion differed from 1.0:
trailing deletions needed to reach acceptance were charged at unit cost, and a padded
look-ahead window could emit a spurious past-query-end position whose cheaper
substitution cost was reported instead of the true edit distance. StateF64::infer_distance
now charges trailing deletions at deletion cost and rejects positions with
term_index > query_length. Unit-cost results are unchanged.PositionF64::subsumes
scales the index-realignment bound by max(insertion, deletion), so a position leading to
the only in-budget match is no longer discarded when insertion/deletion > 1.GeneralizedPosition ordering is now consistent with its derived Eq/Hash (tiebreaks
on entry_char), restoring the Ord/Eq contract binary_search relies on.HashMap iteration order).wrapping_add — Myers' bit-parallel recurrence — is documented).time_series::encoding) explicitly clamps NaN/±∞/out-of-range inputs;
OperationCostsF64::is_valid also rejects non-finite costs.Algorithm::MergeAndSplit as an intentional wildcard over-approximation, and
phonetic_weight / NFA Transition.weight as reserved (not applied to matching cost).See docs/design/numeric-and-weighted-cost-hardening.md for the full invariant catalogue and verification methodology.
DoubleArrayTrieChar, DynamicDawgChar, and SuffixAutomatonChar are now
reachable via liblevenshtein::prelude (previously only their ASCII
counterparts and ScdawgChar were), closing a gap where the UTF-8 dictionaries
were unreachable through liblevenshtein's public surface.PathMap.
examples/mork_fuzzy_query.rs runs a Transducer over libdictenstein's new
PathMapSnapshot / PathMapRef (borrowed, zero-copy) and a subtrie-scoped
from_trie_ref — no trie copy, no lock. tests/pathmap_snapshot_tests.rs
proves the borrowed dictionary drives the full query stack with no hidden
'static bound, plus transducer-level snapshot isolation and Unicode.benches/pathmap_node_ops_benchmark.rs — node-op micro-benchmarks (transition
by depth, edges by fanout, root-snapshot cost, mixed-width char edges) plus
comb/deep-node variants (transition_at_depth_branching,
edges_at_depth_branching, char_edges_at_depth) that defeat pathmap's path
compression to measure the 𝒪(depth)→𝒪(1) node behaviour directly against the
frozen pre-rework tree.𝒪(1) copy-on-write
snapshot (libdictenstein's TrieRef rework): queries no longer re-walk the
path from the root under a per-operation lock. Existing PathMapDictionary{,Char}
usage is behaviorally identical; in-flight queries gain snapshot isolation.liblevenshtein::dictionary::* re-exports were repointed to the
new submodule paths (their names are unchanged).libdictenstein re-exports in the prelude
(the dictionary types, the Dictionary traits, and the factory/substring
re-exports). Import these from libdictenstein directly; the convenience
re-exports remain available but will be removed in a future release.llattice, libdictenstein) so the
path dependencies resolve against dev versions; release builds, packaging,
and the crates.io publish resolve them from their published versions. The
crates.io publish step is now idempotent on re-release.libdictenstein requirement bumped 0.1 → 0.2 — its dictionary-family
submodule reorg is a breaking module-path change, published as libdictenstein
0.2.0.pathmap requirement widened to >=0.2.2, <0.4 (resolves to 0.2.2 on
crates.io; compiles against a local PathMap 0.3.0).duallity crate.
The wfst feature and the liblevenshtein::wfst::* module — LevenshteinWfst,
DictionaryBackend, and the universal / WallBreaker / generalized / phonetic WFST
variants — were extracted into duallity (which depends on both liblevenshtein and
lling-llang), breaking the liblevenshtein ⇄ lling-llang dependency cycle. Migrate
use liblevenshtein::wfst::X → use duallity::X, and depend on duallity instead of
enabling the wfst feature. (No crates.io consumer is affected: the old wfst feature
was unusable from the registry because its lling-llang dependency was a path dependency.)MsmTransducer (2026-05-28)time_series::MsmTransducer, an exact Move-Split-Merge similarity index
over a trie of quantized reference series. search_range(query, tau) returns exactly
{ id : MSM(query, ref_id) <= tau } (no false negatives, no false positives) and
search_knn(query, k, initial_threshold) the exact k nearest by MSM distance. It
walks the trie with an interval-relaxed MSM dynamic program (time_series::msm_interval),
prunes subtrees by an admissible column lower bound, and re-scores survivors against the
stored full-precision originals — closing the completeness gap of
HybridSearchIndex::search_exact, whose lossy Levenshtein pre-filter can drop true
MSM-near neighbors.QuantizationConfig::bin_bounds(bin) -> (f64, f64), the admissible per-bin
value interval [lo, hi] (extreme bins extend to ±∞), consumed by the interval-MSM
bounds.docs/verification/msm/theories/Indexing/{IntervalCost,QuantizationBounds,IntervalColumn}.v)
and the trie-walk soundness/completeness is model-checked in TLA+
(docs/verification/tla/MsmTrieSearch.tla). See docs/verification/msm/INTERVAL_MSM.md.simd, scdawg-bloom, scdawg-simd Cargo Features Removed (2026-05-22)simd, scdawg-bloom, scdawg-simd Cargo features.
x86_64 targets and dispatched at runtime via
is_x86_feature_detected!("avx2") / "sse4.1", with same-module scalar fallbacks.
The Cargo feature was redundant — it gated whether the always-correct code compiled
at all, not whether SIMD ran (which has always been a runtime decision).scdawg-bloom and scdawg-simd features had no source-level gates in this
crate; they were pass-through delegations to libdictenstein, which removed them
in 4b17b43. Their continued presence here had already broken --features simd
builds.#[cfg(feature = "simd")] gates throughout the source tree were converted to
#[cfg(target_arch = "x86_64")]. The simd modules (src/distance/simd.rs,
src/transducer/simd.rs) are now compiled exclusively on x86_64; the dead
non-x86_64 scalar fallbacks inside them have been removed (call sites already
select the scalar implementation on non-x86_64).features = ["simd"] in their Cargo.toml should drop it.
No behavior change on x86_64; non-x86_64 targets continue to use the scalar
implementation automatically.phonetic::language::rules and dispatch are now feature-gated on embedded-rulesphonetic::language::rules::*) and the
dispatch entry points (rules_for_language, default_language, is_supported,
supported_languages) require the embedded-rules Cargo feature. They depend on
the per-language phonetic rule modules under phonetic::rules::*, which have always
been gated on embedded-rules. Builds without this feature previously failed with
unresolved-import errors; they now compile cleanly with the language dispatcher
simply absent.DynamicDawg: Supports online insert/delete/compact with better performanceDoubleArrayTrie: Faster O(1) transitions for static dictionariesDawgDictionary::from_terms() or OptimizedDawg::from_terms() with:
DynamicDawg::from_terms() for mutable scenariosDoubleArrayTrie::from_terms() for static/read-only scenariossrc/dictionary/dawg.rs, src/dictionary/dawg_query.rs, src/dictionary/optimized_dawg.rsdawg_demo.rs, dawg_query_comparison.rsdawg_benchmarks.rsDoubleArrayTrie / DoubleArrayTrieChar - O(1) transitions for static dictionariesDynamicDawg / DynamicDawgChar - Mutable DAWG with online minimizationSuffixAutomaton / SuffixAutomatonChar - Substring matchingSCDAWG / ScdawgChar - Symmetric Compact DAWG for bidirectional traversalPersistentARTrie / PersistentARTrieChar - Disk-based adaptive radix triePathMap / PathMapChar - Dynamic trie (feature-gated)Phonetic-aware fuzzy dictionary implementing Approach 1 from compositional spelling correction
PhoneticNormalizedDictionary::from_terms() - create with default rulesPhoneticNormalizedDictionary::from_terms_with_rules() - create with custom rulesquery() - fuzzy search in normalized space with edit distance toleranceRegex Query Support for grep-like pattern matching
query_regex() - match regex patterns against normalized formsquery_with_product() - use pre-compiled NFA for repeated queriesPhonetic Pattern Expansion for reverse phonetic matching
query_phonetic_pattern() - auto-expand query to match phonetic variantsexpand_phonetic_alternatives_char() - convert normalized string to regex patternexpand_with_costs() - expand with rule weight trackingNew Types
PhoneticNormalizedCandidate - query result with term, distance, normalized formRegexQueryError - error type for regex operationsFuzzyMultiMap Enhancements
query_with_distance() - returns matched key, distance, and valueswasm feature flag enables wasm-bindgen bindingswasm-phonetic feature combines WASM with phonetic rulesffi feature exposes C-compatible functions for WASI/native FFIComplete LLev Parser and NFA Engine
*, +, ?, {n,m}, {,m}), alternation, grouping[:alpha:], [:digit:], [:vowel:], etc.)Phonetic Spellcheck Example
Automatic NFA Optimization - Reduces NFA size and improves matching performance
New Types
OptimizationConfig: Configuration with full(), quick(), none() presetsOptimizationStats: Statistics on optimization results (states/transitions removed)NfaOptimizerChar / NfaOptimizer: Optimizer implementations for char/byte NFAsNFAChar/NFA API Additions
optimize(): Apply full optimizationoptimize_with(config): Apply custom optimization, returns statisticscount_epsilon_transitions(): Count ε-transitions in NFACompiler Integration
NFACompilerChar::with_optimization(config): Set optimization configurationNFACompilerChar::without_optimization(): Disable automatic optimizationcompile() functionLevenshtein Automaton Proofs in Coq/Rocq
Phonetic Rewrite Rules Verification
H7+H8+H9 Combined Optimizations - 2-7× speedup for NFA operations
Phonetic Lexer Optimizations
Position Skipping Optimization - Up to 26.6× speedup
Phonetic Rules Allocation Elimination - 27-30% speedup
apply_rules_with_skip() for position skipping behaviorapply_rules() uses standard sequential matchingapply_rules_seq_opt calls with explicit skip APIMORK and PathMap Integration
WFST Documentation
Theoretical Foundations
Phonetic Split Operations ⟨1,2⟩ (92% complete - 22/24 tests passing)
entry_char field to ISplitting/MSplitting positions to track character at split entryNew SubstitutionSet APIs
has_source(&self, source: &[u8]) -> bool: Check if source exists in restriction sethas_target_starting_with(&self, source: &[u8], first_char: char) -> bool: Validate target starts with given characterNew OperationType APIs
can_apply_to_source(&self, dict_chars: &[u8]) -> bool: Validate source without target for speculative split entrymatches_first_target_char(&self, dict_chars: &[u8], first_target_char: char) -> bool: Validate first character of split targetEntry Character Architecture Issue
previous_input_char was shared at state level, causing incorrect character for parallel exploration pathsentry_char in each splitting position to track character read when entering that specific splitSplit Entry Priority Issue
Split Entry Validation Issue
matches_first_target_char() before entering split stateI-Splitting Invariant Issue
|offset| <= errors too restrictive for accumulated errors from other operationsNegative Match Index Handling
entry_char: char fieldnew_i_splitting, new_m_splitting) with entry_char parametertest_phonetic_split_multiple, test_phonetic_split_with_standard_opsH1: Const Arrays for Presets - 15-28% faster initialization
docs/optimization/substitution-set/02-hypothesis1-const-arrays.mdH3: Hybrid Small/Large Strategy - 9-46% faster for small sets
docs/optimization/substitution-set/06-hypothesis3-hybrid.mdH2: Bitmap Optimization - Rejected
docs/optimization/substitution-set/03-hypothesis2-bitmap.mdComplete optimization summary
docs/optimization/substitution-set/07-final-summary.mdOptimizedDawg::from_terms() to DynamicDawg::from_terms()docs/deprecations/OPTIMIZED_DAWG_DEPRECATION.mddocs/implementation-status/phase-6-dictionary-layer-completeness.mdDynamicContextualCompletionEngine with multiple dictionary backends
ContextualCompletionEngine to DynamicContextualCompletionEngine for clarityContextualCompletionEngine for backward compatibility (will be removed in 1.0.0)D: MutableMappedDictionary<Value = Vec<ContextId>>with_pathmap(), with_pathmap_char(), with_dynamic_dawg(), with_dynamic_dawg_char()StaticContextualCompletionEngine for read-only dictionaries
D: MappedDictionary<Value = Vec<ContextId>>with_double_array_trie(), with_double_array_trie_char()Comprehensive Unicode support across all backends
ContextualCompletionEngine is now a deprecated type aliasDynamicContextualCompletionEngine for clarityNew SuffixAutomatonChar dictionary backend
char) instead of bytes (u8)Full suffix automaton capabilities with Unicode
SuffixAutomatonChar<V: DictionaryValue = ()>Performance characteristics
char vs 1 byte per u8)Comprehensive testing and documentation
DynamicDawgZipper - Byte-level DAWG navigation
DictZipper and ValuedDictZipper traitsDynamicDawgCharZipper - Character-level DAWG navigation
Vec<char>SuffixAutomatonZipper - Byte-level substring navigation
SuffixAutomatonCharZipper - Unicode substring navigation
Extended SuffixAutomaton with value support
V: DictionaryValue (default ())MappedDictionary and MappedDictionaryNode traitsinsert_with_value() and get_value() methodsUse cases
Serialization bounds for DoubleArrayTrieChar
V--all-features flagDATSharedChar and DoubleArrayTrieChar structsType annotations in examples and tests
SuffixAutomaton::<()>)compressed_suffix_demo.rs exampleImport paths in SuffixAutomatonChar doctests
suffix_automaton:: to suffix_automaton_char::Updated src/dictionary/mod.rs
Updated DOCUMENTATION_INDEX.md
src/dictionary/compressed_suffix_automaton.rsCompressedSuffixAutomaton should migrate to:
SuffixAutomaton for byte-level substring matchingSuffixAutomatonChar for Unicode substring matchingNew DynamicDawgChar dictionary backend
char) instead of bytes (u8)Full dynamic operations with Unicode
DynamicDawgChar<V: DictionaryValue = ()>Performance characteristics
char vs 1 byte per u8)Comprehensive testing and documentation
tests/test_dynamic_dawg_char.rs covering Unicode scenariosexamples/dynamic_dawg_unicode.rs demonstrating Unicode handlingUse cases
Made DynamicDawg generic over value types
DynamicDawg to DynamicDawg<V: DictionaryValue = ()> with default type parametervalue: Option<V> field to DawgNode for storing associated valuesinsert_with_value() and get_value() methodsDynamicDawg continues to workNew MutableMappedDictionary trait
insert_with_value() methodGeneric ContextualCompletionEngine
D: MutableMappedDictionary<Value = Vec<ContextId>>with_dictionary() constructor for custom backendsComprehensive integration tests
tests/dynamic_dawg_integration.rsCritical bug fix: Suffix sharing causing incorrect term acceptance
Bug discovery and verification
tests/debug_proptest_failure.rs--all-features enabledBloom Filter for fast negative lookups (88-93% improvement)
contains() operations by rejecting non-existent terms earlywith_config() API: DynamicDawg::with_config(f32::INFINITY, Some(10000))Lazy Auto-Minimization (30% improvement for large datasets)
with_config()DynamicDawg::with_config(1.5, None) minimizes at 50% growthSorted Batch Insertion (4-8% improvement)
from_terms() now pre-sorts input before insertionComprehensive optimization analysis
docs/optimizations/all_optimizations_final_report.mdNew benchmarks for optimization validation
benches/auto_minimize_benchmark.rs - Auto-minimization threshold tuningbenches/bloom_filter_benchmark.rs - Bloom filter performance analysisbenches/compact_benchmark.rs - Compaction strategy comparisonDocumentation
docs/optimizations/all_optimizations_final_report.md - Comprehensive optimization results (7 candidates analyzed)docs/optimizations/rcu_assessment.md - Detailed RCU trade-off analysisdocs/optimizations/dynamic_dawg_optimization_results.md - Benchmark data and decision logHierarchical scope-aware code completion with zipper-based navigation
Zipper architecture for efficient dictionary traversal
DictZipper and ValuedDictZipper trait abstractions (src/dictionary/zipper.rs)PathMapZipper implementation with lock-per-operation patternAutomatonZipper for Levenshtein automaton state trackingIntersectionZipper composing dictionary and automaton navigationZipperQueryIterator with BFS-based traversal and StatePool reuseContextualCompletionEngine API (src/contextual/)
create_root_context() / create_child_context() - Hierarchical scope creationinsert_char() / insert_str() - Incremental draft building (~4 µs per char)checkpoint() / undo() - State management for editor undo/redo (~116 ns per checkpoint)finalize() / finalize_direct() - Promote drafts to permanent dictionary termscomplete() - Fuzzy query with hierarchical visibility filteringdiscard() / rollback_char() - Draft manipulationValue-filtered queries for scoped completions
query_filtered() - Custom predicate-based filtering during traversalquery_by_value_set() - Efficient set-based scope filteringPerformance characteristics
Comprehensive test coverage
Benchmarks and performance analysis
benches/contextual_completion_benchmarks.rs - Single-threaded performancebenches/concurrent_completion_benchmarks.rs - Concurrency benchmarksbenches/zipper_vs_node_benchmark.rs - Comparison with node-based queriesDocumentation
docs/design/contextual-completion-api.md - Complete API specification (906 lines)docs/design/contextual-completion-roadmap.md - 6-phase implementation plan (490 lines)docs/design/contextual-completion-zipper.md - Architecture design (745 lines)docs/design/contextual-completion-progress.md - Implementation tracking and statusdocs/design/zipper-vs-node-performance.md - Performance analysis and trade-offsExample code
examples/contextual_completion.rs - Complete demonstration (221 lines)
Use Cases
Performance Notes
docs/optimization/UTF8_OPTIMIZATION_STATUS.mddocs/optimization/README.md index with UTF-8 section and reading guides#[cfg(feature = "pathmap-backend")] to test_dynamic_dawg_char_value_filtered_query() in tests/test_dynamic_dawg_char.rsFuzzyMultiMap from cache module which requires pathmap-backend featureerror[E0433]: failed to resolve: could not find 'cache' in 'liblevenshtein'pathmap-backend = ["pathmap"] to empty marker feature pathmap-backend = []feature 'pathmap-backend' includes 'pathmap' which is neither a dependency nor another feature.github/workflows/release.yml line 454-456multiple_bound_locations: Removed duplicate D: Dictionary bound (src/cli/commands.rs:689)unused_imports: Removed unused Dictionary import (src/contextual/engine.rs:13)should_implement_trait: Renamed DraftBuffer::from_str() to from_string() to avoid confusion with std::str::FromStr::from_str() (src/contextual/draft_buffer.rs:107)filter_next: Replaced .filter().next() with .find() (src/dictionary/pathmap_char.rs:432)needless_range_loop (4 instances): Converted index-based loops to idiomatic iterator patterns with enumerate() (src/transducer/simd.rs:150, 400, 461, 861)Character-level dictionary variants for correct Unicode Levenshtein distances
DoubleArrayTrieChar - Character-level Double-Array Trie implementationPathMapDictionaryChar - Character-level PathMap with dynamic updates (requires pathmap-backend feature)CharUnit trait abstraction over u8 (byte-level) and char (character-level)Comprehensive Unicode test coverage
Fixed core Unicode issue: "" → "¡" now correctly requires distance 1 (one character) instead of distance 2 (two bytes)
Updated cache eviction nodes
Unit typeDocumentation
UTF8_IMPLEMENTATION.md - Complete technical design document (300+ lines)UTF8_IMPLEMENTATION_STATUS.md - Implementation status report (250+ lines)Comprehensive SIMD acceleration across critical performance paths
Batch 1: SSE4.1 fallback + SIMD affix stripping
is_x86_feature_detected!)Batch 2A: Transducer state operations
State::min_distance() and transducer transitionsBatch 2B: Dictionary edge lookup SIMD (commit: 89cb3b8, 488707b, 337fd83)
usize and u32 targetsBatch 3: Distance matrix SIMD (pre-existing)
distance::standard_distance() when SIMD feature enabledComprehensive test coverage
Documentation
docs/PHASE4_SIMD_COMPLETION_STATUS.md - Overall completion summary (350+ lines)docs/BATCH2A_INTEGRATION_ANALYSIS.md - State operations analysisdocs/BATCH2B_PERFORMANCE_ANALYSIS.md - Edge lookup detailed analysis (450+ lines)Comprehensive query iterator testing and optimization
Adaptive sorting optimization
Query iterator benchmarks (benches/query_iterator_benchmarks.rs, benches/query_profiling.rs)
Analysis documentation moved to docs/analysis/
docs/analysis/fuzzy-maps/ - 7-phase optimization journey (01-07)docs/analysis/hierarchical-scope/ - Design and benchmark analysisDocumentation structure improvements
docs/analysis/fuzzy-maps/ - Complete fuzzy maps optimization story (-7.1% → +5.8%)docs/analysis/hierarchical-scope/ - Scope completion design and resultsdocs/guides/HIERARCHICAL_SCOPE_COMPLETION.md - User-facing guidedocs/README.md with new "Analysis & Research" section.gitignore with LaTeX artifact patternsOptimization documentation moved to docs/optimization/
Documentation consolidation
docs/optimization/README.md - Main optimization documentation indexBug #1: Large distance queries dropping results (src/transducer/ordered_query.rs:126-197)
tests/large_distance_test.rsBug #2: Lexicographic ordering not maintained (src/transducer/ordered_query.rs:64-83, 126-197)
tests/query_comprehensive_test.rsArch Linux package support (1199173)
.pkg.tar.zst packages for x86_64 and aarch64 architecturespackaging/arch/PKGBUILD with architecture-specific RUSTFLAGSRPM package support (1199173)
.rpm packages for RedHat, Fedora, CentOS distributionsCargo.toml using cargo-generate-rpm-C target-feature=+aes,+sse2 for x86_64, +aes,+neon for ARM64)-C target-cpu=native to ensure gxhash dependency compatibilitynightly.yml and release.yml workflowsCode quality improvements (0f29a30)
if let Err(_) = ... → .is_err() (2 instances)parse_limit logic&Box<T> → &T (2 instances)enumerate() (5 instances)from_iter → from_terms to avoid FromIterator confusion (44 call sites)Library naming corrections (1199173)
libliblevenshtein.so (Linux shared library)libliblevenshtein.rlib (Rust static library)libliblevenshtein.dylib (macOS shared library)[patch] sections in Cargo.toml./scripts/install-git-hooks.sh.githooks/README.mdgit = "https://github.com/Adam-Vandervorst/PathMap.git"[patch] section for local development override.cargo/config.toml.local-example for local dev setupdocs/README.md as central documentation index (177 lines)docs/archive/benchmarks/FEATURES.md for v0.2.0 (DynamicDawg, OrderedQueryIterator, compression, protobuf)BUILD.md (434 lines) with build instructionsCONTRIBUTING.md for v0.2.0 features and workflowsGitHub Actions workflow badges (5c5853a)
Comprehensive GitHub Actions workflows (e065043)
ci.yml: Main CI with test matrix (Ubuntu + macOS, stable + nightly Rust)release.yml: Multi-platform builds (Linux x86_64/ARM64, macOS x86_64/ARM64, .deb packages)nightly.yml: Daily validation with code coverage, security audits, benchmark trackingGzip compression for dictionary serialization (f8e23b6)
GzipSerializer<S> wrapper for any serialization formatcompression feature flagCLI integration for compressed formats (519e183)
bincode-gz, json-gz, protobuf-gz format variantsFiltering and prefix matching (eea90dd)
OrderedQueryIteratorContextual filtering optimizations (9c27575)
advanced_contextual_filtering.rs, contextual_filtering_optimization.rsCode completion guide (c3551ee)
Distance-first, lexicographic ordering (319d4e8)
Index-based DAWG query iterator (56fc643)
DynamicDawg with online modifications (ec76137)
DAWG and serialization support (4fc3c16)
Real-world dictionary validation (4a9ed37)
Phase 3: Final optimizations (5c485a4)
Phase 2: Aggressive inlining (5cd73f5)
Phase 1: Initial optimizations (90e1482)
3.3x speedup for DAWG operations (3f6bc58)
Lightweight PathNode optimization (9fc42b1)
Arc Path Sharing (9de7421)
StatePool allocation reuse (e375303)
SmallVec integration (44157d5)
Lazy edge iteration (10ea210)
Comprehensive documentation restructure for improved discoverability
11 new README.md navigation indexes
4 new comprehensive user guides (10,000+ lines total)
getting-started.md - Installation, basic usage, backend/algorithm selectionalgorithms.md - Deep dive into Standard, Transposition, and MergeAndSplit algorithmsbackends.md - Complete backend comparison with performance characteristicsserialization.md - Save/load dictionaries with format comparison and best practicesUpdated all cross-references and internal links
Consolidated related documentation
Comprehensive optimization summary (b536a7a)
Code completion guide (c3551ee)
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |