Skip to main content

Changelog

All notable changes to this project are documented here. The format follows Keep a Changelog and the project follows Semantic Versioning (0.x until the API settles).

[Unreleased]​

Changed​

  • Breaking (0.x): the wasm, Node, C and Python bindings use the core's Unicode normalisation (issue #67): terms are built with Trie::build_normalized and queries searched with search_text, so case and diacritics are folded (sao paulo finds São Paulo, ACAO finds ação, strasse finds Straße). Hits now return the caller's original text instead of the ASCII-lower-cased one, and terms equal after folding are merged. Python no longer refuses non-ASCII text and gains Index(items, *, fold_case=True, fold_diacritics=True); the query limit of the wasm, Node (MAX_QUERY_BYTES is now MAX_QUERY_LENGTH), C and Python bindings is 128 code points after folding. C: KH_ABI_VERSION is 2 (kh_hit.term semantics, kh_hit.input_index appended, KH_MAX_QUERY_LEN in code points), with the additions kh_index_build_ex, KH_NORM_KEEP_CASE, KH_NORM_KEEP_DIACRITICS and KH_MAX_QUERY_BYTES. The wasm module grows from 18 155 to 19 559 bytes gzip (gzip -9 -n, budget 20 480; one machine). All four bindings are tested against one expected-results file produced by the core (bindings/testdata). A term that folds to nothing is an error in the C, Python and Node bindings (only the raw wasm text format skips it). The wasm gzip budget has about 0.75 KB left (19 728 bytes measured by CI on the last commit of the PR, 19 511 on the first one): the next wasm feature must either shrink the module or raise WASM_GZIP_BUDGET with a stated reason.
  • Breaking (0.x): the search alphabet is Unicode code points instead of UTF-8 bytes (issue #19). Terms are split into chars and byte queries are decoded as UTF-8 (a byte that is not valid UTF-8 becomes a symbol that matches no term), so é against e is one substitution, not two edits. ASCII results, costs, term ids, input_index, trie shape and Stats are unchanged, pinned by tests/ascii_regression.rs (digests recorded on the byte engine) and by identical node counts on the M0 data (docs/benchmarks/unicode.md). Trie::label returns a char (migrate with u32::from(label), or label as u8 for ASCII); MAX_QUERY_LEN and SearchError::QueryTooLong::len count code points; cost::class changed for bytes 128-255 (now Latin-1 code points, see cost::symbol_class); CostModel::sub_cost, ins_cost and del_cost are generic (u8, char and u32 symbols; an untyped integer literal argument no longer infers). Layout keys outside a-z are neighbouring keys now: ç on ABNT2, ù (added) on AZERTY, ü, ö, ä (added) on QWERTZ, and the punctuation keys of ABNT2, Dvorak and Colemak; no pair of two letters a-z changes and QWERTY is unchanged, but CostModel::for_layout(Layout::Abnt2) no longer equals CostModel::qwerty(). The bindings are unchanged: wasm, Node and C now compare non-ASCII text per code point, Python still refuses it. Design and proof notes: docs/design/unicode.md, docs/design/lower-bound.md section 3.
  • SearchConfig::default() now has tsb: true (the subtree bound was off). Hits, order and costs are unchanged unless max_nodes truncates a search (then both modes return a correct prefix of the same list, possibly of different length) (oracle-tested); on the 300 Birkbeck typo pairs it expands 33-35% fewer nodes with about 19-21% lower p95 latency at the default budget (one machine, shared, median of three runs), and costs no extra memory (the per-node data is always built). Stats node counts change, and the WebAssembly module, which builds its config from the default, now runs with the bound on. Set tsb: false for the old behaviour. See docs/benchmarks/tsb-default.md (issue #49).

Added​

  • Match highlighting (issue #32): Searcher::highlight and Searcher::highlight_text return, for one hit of search/search_prefix (HighlightMode::Whole/Prefix) or their _text variants, the characters of the caller's original term string that the query matched (aligned with an equal symbol, or transposed), as sorted, disjoint half-open ranges in code points, UTF-8 bytes and UTF-16 units, plus the aligned span. The alignment is recomputed on the full matrix only for the hits asked for and walked back with a documented tie rule; its cost always equals Hit::cost (otherwise HighlightError::CostMismatch). Folding is mapped back through text::SourceMap (ß counts as typed when one of its s is; a dropped combining mark follows its letter). The DP cell candidates now come from one function shared by the search rows and the traceback; search results and work counters are unchanged (identical node counts on the M0 data). New module keyhammer::highlight, a highlight fuzz target, property, golden and UTF-16 tests. Design: docs/design/highlighting.md; costs: docs/benchmarks/highlighting.md, bench/src/bin/highlight.rs. Not exposed in the bindings yet.
  • text module (no_std, no dependencies, tables of our own generated by crates/keyhammer/scripts/gen_text_tables.py): Normalizer folds diacritics (Latin-1 Supplement and Latin Extended-A letters, combining marks U+0300-U+036F, æ œ ß þ and the ligatures U+FB00-U+FB06) and case (Unicode full case folding in those ranges; no locale), each switchable; SourceMap, utf8_range/utf16_range and offsets for ranges in code points, UTF-8 bytes and UTF-16 units (the part of #32 that needs Unicode). Trie::build_normalized, Trie::normalizer, Searcher::search_text and Searcher::search_prefix_text fold terms and queries identically. Oracle tests on non-ASCII and normalised dictionaries, exhaustive idempotence tests of the normaliser, and two fuzz targets (normalize, text_oracle_equality). Limits (no Greek or Cyrillic folding, no NFC, no Turkic mode) are in docs/design/unicode.md (issue #19).
  • cost::Layout (QWERTY, QWERTZ, AZERTY, ABNT2, Dvorak, Colemak; #[non_exhaustive]) and CostModel::for_layout: the neighbour table is derived from key geometry (staggered rows), CostModel::qwerty() is unchanged (regression-tested against the old table). Keys outside a-z count since the code-point alphabet (see Changed, issue #19). Search, band width and subtree bound use the model's minimum costs, so they hold for every layout (oracle and fuzz tests run all layouts). CostModel now also derives PartialEq/Eq. First part of issue #20: not exposed in the bindings yet, no dead keys.
  • docs/benchmarks/sum-bound.md, tests/sum_bound.rs, bench/src/bin/sumbound.rs: research on a summed subtree-signature bound (#44). The sum is admissible under the current costs (argued in docs/design/lower-bound.md section 3a, no counterexample in about 13.2 million tested cases) but expands only 0.14-0.33% fewer nodes than max; not adopted, core unchanged.
  • bench/src/bin/{recall,phonetic}.rs and docs/benchmarks/recall-beyond-two-edits.md: research on recall beyond two edits (budgets 32, 48 and 64 with paired differences, nodes and latency; what the unreachable pairs are) and on phonetic and spelling-rule candidates prototyped outside the core with held-out splits. Verdict: no budget-64 preset, no spelling-rule operation; phonetic candidates are a promising follow-up (issue #22).
  • Searcher::search_prefix: a prefix (autocomplete) mode. A term matches when the query is within the budget of some prefix of it (cost = best alignment of the whole query against any prefix, transpositions only inside the prefix); ranking is as in search (cost rank, weight, id). The subtree bound is adapted (only the upper length end constrains a prefix) and subtrees whose terms all cost the same are enumerated by weight without DP rows. Oracle-tested against a brute-force prefix reference (tsb on/off, both rankings), with a property test of the adapted bound and a new prefix_oracle_equality fuzz target. Stats gains rows_computed and is now #[non_exhaustive] (it can no longer be built with a struct literal outside the crate). Work counters against the exact mode are in docs/benchmarks/prefix-mode.md; the proof is in docs/design/prefix-mode.md (issue #30).
  • bench/src/bin/calib.rs (behind --features calibration), bench/experiments/cost-knobs.patch and docs/benchmarks/calibration{-preregistration,}.md: a pre-registered calibration of the cost model on four corpora with train, validation and test splits (300 models). The rule proposes a follow-up (first-byte factor 1.25, neighbouring-key substitution 12, indel 12: +0.0134 MRR@10 on the test split, SE 0.0015, but about 1.67x the nodes expanded); the shipped costs are unchanged and the core crate is untouched (issue #21).
  • bindings/node: a Node.js package for the new engine, plain JavaScript over the WebAssembly build (Index.build, index.search with k, budget and ranking, TypeScript types, argument errors); tested by a CI job on ubuntu, macos and windows with Node 18 and 22. Nothing is published. The choice against a native addon is in docs/design/node-binding.md.
  • bench/src/bin/tiebreak.rs and docs/benchmarks/tiebreak-{preregistration,result}.md: a pre-registered test of a ranking tie-break variant on disjoint typo samples (fetch-typo-corpora.mjs --holdout). Verdict: do not adopt (+0.0030 MRR@10 at 274 137 words, but a significant loss on two error categories); the default ranking is unchanged.
  • bindings/python: a Python package (PyO3 and maturin, abi3 wheels) with Index, SearchConfig, Ranking, errors as exceptions and type stubs. ASCII only for now; no add/remove/export because the core has none yet (#31, #26). A CI job builds and tests the wheel on Linux, macOS and Windows; nothing is published. Its dependencies (pyo3 and maturin) are MIT OR Apache-2.0; see bindings/python/README.md.
  • bench/fetch-finger-slips.mjs and bench/src/bin/slips.rs: a corpus of real typing errors built from the 136M Keystrokes dataset (SHA-256 checked, never committed, non-commercial licence), classified by edit operation, and a first measurement of the engine against a unit-cost baseline on it. The shipped engine ranked below a plain OSA<=2 baseline (MRR@10 -0.031, SE 0.004), all of it on first-letter pairs; elsewhere +0.002 (SE 0.003); no measurable benefit of the adjacency costs; see docs/benchmarks/finger-slips.md.
  • keyhammer-c (bindings/c): a stable, handle-based C ABI (kh_index_build, kh_search, explicit free functions, status codes with kh_last_error, kh_abi_version), a cbindgen-generated include/keyhammer.h checked for freshness in CI, a C smoke test compiled in CI, and docs/design/c-abi.md with the ABI stability rules. Unsafe code is confined to this crate.
  • Fuzz targets (crates/keyhammer/fuzz, cargo-fuzz) for build and search robustness, brute-force oracle equality and tsb on/off equivalence, a weekly fuzz workflow, and a deterministic tests/fuzz_like.rs running the same properties in cargo test; see docs/fuzzing.md.
  • CI: cargo deny (licences, advisories, bans, sources; deny.toml), a weekly Miri run over the core tests, and a gzipped .wasm size gate (budget 20 KB).
  • SearchConfig::high_recall(): an opt-in preset with budget = 48 and tsb: true; the default budget stays 32. On the 300 Birkbeck typo pairs it found the right word more often. With tsb: true on both sides, it expanded about 4.6-5.2x the nodes and had about 5.5-7.3x the p95 latency (about 5.2-7.5x with the bound off); see docs/benchmarks/recall-preset.md. The M0 harness reports the preset too.
  • New keyhammer core crate (M0 prototype): keyboard-weighted cost model, flat trie, exact best-first search, and brute-force oracle tests.
  • CI workflow for the core crate.
  • bench/js-competitors/: a harness that runs the WebAssembly build in Node against MiniSearch, Fuse.js, uFuzzy and fuzzysort, with its report docs/benchmarks/competitors-js.md; a CI job runs a small smoke configuration of it.
  • bench/ harnesses and the dataset fetch script.
  • docs/papers.md (reference check and prior art) and docs/benchmarks/m0.md (M0 benchmark results).
  • search::Ranking (Coarse, the default, and Exact), the SearchConfig::ranking field, cost::COST_UNIT and cost::whole_units.
  • Trie::input_index: maps a term id (a position in the sorted, deduplicated list) back to the index in the input slice of the entry that was kept.
  • trie::BuildError::TooManyTerms: Trie::build returns it instead of wrapping when given more than u32::MAX terms.
  • docs/design/lower-bound.md: a written proof that the search's lower bound is admissible, with what the tests check and what is only argued.

Removed​

  • crates/node, the Node binding of the legacy engine; bench/compare.mjs now loads bindings/node and so runs the new engine.

Changed​

  • The M0 harness (bench/src/bin/m0.rs) now exits with status 1 when a gate check on the largest dictionary prints FAIL ((b) p95 ratio, (c) strict MRR; the informational (c') does not count), when a legacy search returns an error (counted and shown as errors=N in the legacy row) or when a gate row is missing. Malformed TSV lines and non-u16 frequencies now abort with status 2 and the file and line, instead of being dropped or read as 0. Each engine runs an untimed warm-up pass before timing. --help documents the exit codes. Printed quality numbers are unchanged. On the published data (c) fails on the full dictionary, so the harness exits 1 there; this is the documented G0 partial pass (docs/benchmarks/m0.md), not a new failure.
  • License changed from MIT to AGPL-3.0-or-later, effective from the commit "chore: relicense to AGPL-3.0-or-later". Versions obtained before that commit remain under MIT for those who received them.
  • Current engine moved to legacy/ and kept only as a benchmark reference.
  • Default ranking is now the weighted cost rounded up to whole units of 16, then higher weight, then term id (Ranking::Coarse). This is not a count of edits: the x1.5 factor on the first byte makes an ordinary (non-neighbouring-key) edit there cost 24, i.e. two units, while a neighbouring-key substitution there costs 12 (one unit) and a transposition 18 (two units); two cheap edits (8 + 8) count as one. Ranking::Exact restores the previous order by exact weighted cost. Hit::cost is the exact weighted cost in both modes.
  • With the default ranking, Output::hits is no longer ordered by ascending exact cost: do not assume that hits[0].cost is the minimum; use Ranking::Exact for that order.
  • SearchConfig gained the public field ranking and is not #[non_exhaustive], so code that builds it with a struct literal without ..SearchConfig::default() no longer compiles.