fallow_types/
levenshtein.rs

1//! Levenshtein-distance helpers for typo detection.
2//!
3//! One algorithm and one distance and length policy for every "did you mean?"
4//! suggestion: rule names, plugin enablers, and suppression issue kinds.
5//! `fallow-config` re-exports this module unchanged.
6
7/// Levenshtein edit distance between two ASCII-leaning strings.
8///
9/// Uses two `Vec<usize>` rows so the working set stays bounded; the inputs we
10/// match against (rule names, package names) are short and allocation cost is
11/// negligible at config-load time.
12#[must_use]
13pub fn levenshtein(a: &str, b: &str) -> usize {
14    let a_bytes = a.as_bytes();
15    let b_bytes = b.as_bytes();
16    let (a_len, b_len) = (a_bytes.len(), b_bytes.len());
17
18    if a_len == 0 {
19        return b_len;
20    }
21    if b_len == 0 {
22        return a_len;
23    }
24
25    let mut prev: Vec<usize> = (0..=b_len).collect();
26    let mut curr: Vec<usize> = vec![0; b_len + 1];
27
28    for i in 1..=a_len {
29        curr[0] = i;
30        for j in 1..=b_len {
31            let cost = usize::from(a_bytes[i - 1] != b_bytes[j - 1]);
32            curr[j] = (prev[j] + 1) // deletion
33                .min(curr[j - 1] + 1) // insertion
34                .min(prev[j - 1] + cost); // substitution
35        }
36        std::mem::swap(&mut prev, &mut curr);
37    }
38
39    prev[b_len]
40}
41
42/// Find the closest candidate to `input` when it is plausibly a typo.
43///
44/// Returns the best match when the Levenshtein distance is at most 2 AND the
45/// input is long enough that the match is not coincidental
46/// (`input.len() / 2 > distance`). Returns `None` when no candidate clears the
47/// bar so callers stay silent on completely novel strings rather than emitting
48/// a misleading suggestion.
49///
50/// Input is lowercased before comparison; callers should pass canonical-case
51/// candidates (kebab-case for rule names, original-case for package names).
52pub fn closest_match<'a, I>(input: &str, candidates: I) -> Option<&'a str>
53where
54    I: IntoIterator<Item = &'a str>,
55{
56    let input_lower = input.to_ascii_lowercase();
57    let mut best: Option<(&'a str, usize)> = None;
58
59    for candidate in candidates {
60        let d = levenshtein(&input_lower, &candidate.to_ascii_lowercase());
61        if best.is_none_or(|(_, b_dist)| d < b_dist) {
62            best = Some((candidate, d));
63        }
64    }
65
66    best.filter(|&(_, d)| d > 0 && d <= 2 && input_lower.len() / 2 > d)
67        .map(|(name, _)| name)
68}
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    #[test]
75    fn levenshtein_identical() {
76        assert_eq!(levenshtein("abc", "abc"), 0);
77    }
78
79    #[test]
80    fn levenshtein_one_insertion() {
81        assert_eq!(levenshtein("abc", "abcd"), 1);
82    }
83
84    #[test]
85    fn levenshtein_empty_pair() {
86        assert_eq!(levenshtein("", ""), 0);
87        assert_eq!(levenshtein("abc", ""), 3);
88        assert_eq!(levenshtein("", "abc"), 3);
89    }
90
91    #[test]
92    fn closest_match_finds_typo() {
93        let candidates = ["@vue/core", "react", "svelte"];
94        assert_eq!(
95            closest_match("@vue/cor", candidates.iter().copied()),
96            Some("@vue/core")
97        );
98    }
99
100    #[test]
101    fn closest_match_returns_none_for_novel_input() {
102        let candidates = ["react", "vue"];
103        assert_eq!(
104            closest_match("acme-magic", candidates.iter().copied()),
105            None
106        );
107    }
108
109    #[test]
110    fn closest_match_returns_none_when_input_too_short() {
111        let candidates = ["react"];
112        assert_eq!(closest_match("rea", candidates.iter().copied()), None);
113    }
114
115    #[test]
116    fn closest_match_skips_exact_match() {
117        let candidates = ["react"];
118        assert_eq!(closest_match("react", candidates.iter().copied()), None);
119    }
120
121    #[test]
122    fn closest_match_is_case_insensitive() {
123        let candidates = ["@vue/core"];
124        assert_eq!(
125            closest_match("@VUE/CORE", candidates.iter().copied()),
126            None,
127            "exact match (ignoring case) should not produce a suggestion"
128        );
129        assert_eq!(
130            closest_match("@VUE/CORX", candidates.iter().copied()),
131            Some("@vue/core")
132        );
133    }
134
135    #[test]
136    fn closest_match_empty_candidates() {
137        let candidates: [&str; 0] = [];
138        assert_eq!(closest_match("anything", candidates.iter().copied()), None);
139    }
140}
fallow_types/levenshtein.rs

fallow_types/
levenshtein.rs
