fallow_config/
levenshtein.rs

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

fallow_config/
levenshtein.rs
