rl_lang/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}
rl_lang/utils/suggest.rs

rl_lang/utils/
suggest.rs
