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 (idx, candidate) in scored.into_iter().enumerate() {
34        if idx >= max {
35            break;
36        }
37        out.push(candidate.candidate);
38    }
39    out
40}
41
42/// Compute the Levenshtein edit distance between two strings.
43pub fn levenshtein(a: &str, b: &str) -> usize {
44    let a_chars: Vec<char> = a.chars().collect();
45    let b_chars: Vec<char> = b.chars().collect();
46    let m = a_chars.len();
47    let n = b_chars.len();
48
49    let mut dp = vec![vec![0usize; n + 1]; m + 1];
50    for (i, row) in dp.iter_mut().enumerate() {
51        row[0] = i;
52    }
53
54    for (j, value) in dp[0].iter_mut().enumerate() {
55        *value = j;
56    }
57
58    for i in 1..=m {
59        for j in 1..=n {
60            let cost = if a_chars[i - 1] == b_chars[j - 1] {
61                0
62            } else {
63                1
64            };
65            let del = dp[i - 1][j] + 1;
66            let ins = dp[i][j - 1] + 1;
67            let sub = dp[i - 1][j - 1] + cost;
68            dp[i][j] = del.min(ins).min(sub);
69        }
70    }
71
72    dp[m][n]
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn levenshtein_matches_ts_examples() {
81        assert_eq!(levenshtein("kitten", "sitting"), 3);
82        assert_eq!(levenshtein("", "a"), 1);
83        assert_eq!(levenshtein("a", ""), 1);
84        assert_eq!(levenshtein("a", "a"), 0);
85    }
86
87    #[test]
88    fn nearest_matches_is_stable_on_ties() {
89        let candidates = vec!["aa".to_string(), "ab".to_string(), "ac".to_string()];
90        let out = nearest_matches("a", &candidates, 3);
91        // All have distance 1; preserve original order.
92        assert_eq!(out, vec!["aa", "ab", "ac"]);
93    }
94}
ito_common/match_.rs

ito_common/
match_.rs
