rl-utils 1.1.1

/// Find the closest match to `target` from `candidates` using Levenshtein
/// distance. Returns `Some(name)` only when the best candidate is within
/// `max(target.len() / 3, 1)` edits - enough to catch typical typos
/// without surfacing wild guesses.
pub fn closest_match<'a, I>(target: &str, candidates: I) -> Option<&'a str>
where
    I: IntoIterator<Item = &'a str>,
{
    let threshold = target.len().div_ceil(3).max(1);
    let mut best: Option<(&str, usize)> = None;
    for cand in candidates {
        if cand == target {
            continue;
        }
        let d = levenshtein(target, cand);
        if d <= threshold && best.is_none_or(|(_, bd)| d < bd) {
            best = Some((cand, d));
        }
    }
    best.map(|(s, _)| s)
}

/// Computes the Levenshtein edit distance between two strings.
fn levenshtein(a: &str, b: &str) -> usize {
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    if a.is_empty() {
        return b.len();
    }
    if b.is_empty() {
        return a.len();
    }

    let mut prev: Vec<usize> = (0..=b.len()).collect();
    let mut curr: Vec<usize> = vec![0; b.len() + 1];

    for i in 1..=a.len() {
        curr[0] = i;
        for j in 1..=b.len() {
            let cost = if a[i - 1] == b[j - 1] { 0 } else { 1 };
            curr[j] = (prev[j] + 1) // deletion
                .min(curr[j - 1] + 1) // insertion
                .min(prev[j - 1] + cost); // substitution
        }
        std::mem::swap(&mut prev, &mut curr);
    }
    prev[b.len()]
}

#[cfg(test)]
mod tests {
    use super::closest_match;
    use super::levenshtein;

    #[test]
    fn test_levenshtein() {
        assert_eq!(levenshtein("rust", "rlang"), 4);
        assert_eq!(levenshtein("ferris", ""), 6);
        assert_eq!(levenshtein("", "ferris"), 6);
        assert_eq!(levenshtein("monad", "monad"), 0);
    }

    #[test]
    fn test_closest_match() {
        let target = "println(\"foo\"";
        let correct_closest_match = "println(\"foo\")";
        assert_eq!(
            closest_match(target, [correct_closest_match, "alice", "bob"]),
            Some(correct_closest_match)
        );
        assert_eq!(closest_match(target, ["alice", "bob", "charlie"]), None);
    }
}