lean_ctx/core/
levenshtein.rs

1//! Shared edit-distance "did you mean" helper (#712).
2//!
3//! One implementation for every typo-suggestion surface: CLI commands
4//! (`cli/dispatch/suggest.rs`), config keys (`cli/config_cmd.rs`) and MCP
5//! tool names (`server/dispatch`). Wagner-Fischer over Unicode scalar values
6//! with a single rolling row — candidate sets are tiny (dozens of names), so
7//! O(a·b) time per pair is irrelevant; what matters is that all callers agree
8//! on distances.
9
10/// Classic Wagner-Fischer edit distance with O(min) memory.
11pub fn levenshtein(a: &str, b: &str) -> usize {
12    let a: Vec<char> = a.chars().collect();
13    let b: Vec<char> = b.chars().collect();
14    if a.is_empty() {
15        return b.len();
16    }
17    if b.is_empty() {
18        return a.len();
19    }
20    let mut prev: Vec<usize> = (0..=b.len()).collect();
21    let mut curr = vec![0usize; b.len() + 1];
22    for (i, &ca) in a.iter().enumerate() {
23        curr[0] = i + 1;
24        for (j, &cb) in b.iter().enumerate() {
25            let cost = usize::from(ca != cb);
26            curr[j + 1] = (prev[j + 1] + 1).min(curr[j] + 1).min(prev[j] + cost);
27        }
28        std::mem::swap(&mut prev, &mut curr);
29    }
30    prev[b.len()]
31}
32
33/// The closest candidate within a length-scaled edit budget (one edit for
34/// short names, roughly a third of the length for longer ones), or `None`
35/// when nothing is near enough to suggest with confidence. Ties resolve to
36/// the first candidate in iteration order.
37pub fn closest<'a, I>(input: &str, candidates: I) -> Option<&'a str>
38where
39    I: IntoIterator<Item = &'a str>,
40{
41    let input = input.trim();
42    if input.is_empty() {
43        return None;
44    }
45    let budget = (input.chars().count() / 3).max(1);
46    candidates
47        .into_iter()
48        .map(|cand| (cand, levenshtein(input, cand)))
49        .filter(|&(_, dist)| dist <= budget)
50        .min_by_key(|&(_, dist)| dist)
51        .map(|(cand, _)| cand)
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn basic_distances() {
60        assert_eq!(levenshtein("", ""), 0);
61        assert_eq!(levenshtein("abc", "abc"), 0);
62        assert_eq!(levenshtein("abc", "abd"), 1);
63        assert_eq!(levenshtein("udpate", "update"), 2);
64        assert_eq!(levenshtein("kitten", "sitting"), 3);
65    }
66
67    #[test]
68    fn unicode_scalars_not_bytes() {
69        assert_eq!(levenshtein("héllo", "hello"), 1);
70    }
71
72    #[test]
73    fn closest_respects_length_scaled_budget() {
74        let tools = ["ctx_read", "ctx_search", "ctx_shell", "ctx_tree"];
75        assert_eq!(closest("ctx_raed", tools), Some("ctx_read"));
76        assert_eq!(closest("ctx_serach", tools), Some("ctx_search"));
77        // Distance beyond the budget → no confident suggestion.
78        assert_eq!(closest("completely_else", tools), None);
79        assert_eq!(closest("", tools), None);
80    }
81}
lean_ctx/core/levenshtein.rs

lean_ctx/core/
levenshtein.rs
