rl_utils/
suggest.rs

1/// Find the closest match to `target` from `candidates` using Levenshtein
2/// distance. Returns `Some(name)` only when the best candidate is within
3/// `max(target.len() / 3, 1)` edits - enough to catch typical typos
4/// without surfacing wild guesses.
5pub fn closest_match<'a, I>(target: &str, candidates: I) -> Option<&'a str>
6where
7    I: IntoIterator<Item = &'a str>,
8{
9    let threshold = target.len().div_ceil(3).max(1);
10    let mut best: Option<(&str, usize)> = None;
11    for cand in candidates {
12        if cand == target {
13            continue;
14        }
15        let d = levenshtein(target, cand);
16        if d <= threshold && best.is_none_or(|(_, bd)| d < bd) {
17            best = Some((cand, d));
18        }
19    }
20    best.map(|(s, _)| s)
21}
22
23/// Computes the Levenshtein edit distance between two strings.
24fn levenshtein(a: &str, b: &str) -> usize {
25    let a: Vec<char> = a.chars().collect();
26    let b: Vec<char> = b.chars().collect();
27    if a.is_empty() {
28        return b.len();
29    }
30    if b.is_empty() {
31        return a.len();
32    }
33
34    let mut prev: Vec<usize> = (0..=b.len()).collect();
35    let mut curr: Vec<usize> = vec![0; b.len() + 1];
36
37    for i in 1..=a.len() {
38        curr[0] = i;
39        for j in 1..=b.len() {
40            let cost = if a[i - 1] == b[j - 1] { 0 } else { 1 };
41            curr[j] = (prev[j] + 1) // deletion
42                .min(curr[j - 1] + 1) // insertion
43                .min(prev[j - 1] + cost); // substitution
44        }
45        std::mem::swap(&mut prev, &mut curr);
46    }
47    prev[b.len()]
48}
49
50#[cfg(test)]
51mod tests {
52    use super::closest_match;
53    use super::levenshtein;
54
55    #[test]
56    fn test_levenshtein() {
57        assert_eq!(levenshtein("rust", "rlang"), 4);
58        assert_eq!(levenshtein("ferris", ""), 6);
59        assert_eq!(levenshtein("", "ferris"), 6);
60        assert_eq!(levenshtein("monad", "monad"), 0);
61    }
62
63    #[test]
64    fn test_closest_match() {
65        let target = "println(\"foo\"";
66        let correct_closest_match = "println(\"foo\")";
67        assert_eq!(
68            closest_match(target, [correct_closest_match, "alice", "bob"]),
69            Some(correct_closest_match)
70        );
71        assert_eq!(closest_match(target, ["alice", "bob", "charlie"]), None);
72    }
73}
rl_utils/suggest.rs

rl_utils/
suggest.rs
