ito_common/
match_.rs

1//! Fuzzy matching helpers.
2//!
3//! Used for "did you mean" suggestions in CLI error messages.
4
5#[derive(Debug, Clone, PartialEq, Eq)]
6/// A candidate string scored by edit distance.
7pub struct ScoredCandidate {
8    /// The candidate string.
9    pub candidate: String,
10    /// The edit distance to the input.
11    pub distance: usize,
12    /// The original index in the input list (used for stable tie-breaking).
13    pub index: usize,
14}
15
16/// Return up to `max` candidates closest to `input`.
17///
18/// Matches are sorted by Levenshtein distance and are stable on ties.
19pub fn nearest_matches(input: &str, candidates: &[String], max: usize) -> Vec<String> {
20    let mut scored = Vec::new();
21    for (idx, c) in candidates.iter().enumerate() {
22        scored.push(ScoredCandidate {
23            candidate: c.clone(),
24            distance: levenshtein(input, c),
25            index: idx,
26        });
27    }
28
29    // Match JS behavior: sort by distance, stable on original order.
30    scored.sort_by(|a, b| a.distance.cmp(&b.distance).then(a.index.cmp(&b.index)));
31
32    let mut out = Vec::new();
33    for s in scored.into_iter().take(max) {
34        out.push(s.candidate);
35    }
36    out
37}
38
39/// Compute the Levenshtein edit distance between two strings.
40pub fn levenshtein(a: &str, b: &str) -> usize {
41    let a_chars: Vec<char> = a.chars().collect();
42    let b_chars: Vec<char> = b.chars().collect();
43    let m = a_chars.len();
44    let n = b_chars.len();
45
46    let mut dp = vec![vec![0usize; n + 1]; m + 1];
47    for (i, row) in dp.iter_mut().enumerate() {
48        row[0] = i;
49    }
50    for (j, cell) in dp[0].iter_mut().enumerate() {
51        *cell = j;
52    }
53
54    for i in 1..=m {
55        for j in 1..=n {
56            let cost = if a_chars[i - 1] == b_chars[j - 1] {
57                0
58            } else {
59                1
60            };
61            let del = dp[i - 1][j] + 1;
62            let ins = dp[i][j - 1] + 1;
63            let sub = dp[i - 1][j - 1] + cost;
64            dp[i][j] = del.min(ins).min(sub);
65        }
66    }
67
68    dp[m][n]
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn levenshtein_matches_ts_examples() {
77        assert_eq!(levenshtein("kitten", "sitting"), 3);
78        assert_eq!(levenshtein("", "a"), 1);
79        assert_eq!(levenshtein("a", ""), 1);
80        assert_eq!(levenshtein("a", "a"), 0);
81    }
82
83    #[test]
84    fn nearest_matches_is_stable_on_ties() {
85        let candidates = vec!["aa".to_string(), "ab".to_string(), "ac".to_string()];
86        let out = nearest_matches("a", &candidates, 3);
87        // All have distance 1; preserve original order.
88        assert_eq!(out, vec!["aa", "ab", "ac"]);
89    }
90}
ito_common/match_.rs

ito_common/
match_.rs
