nova_diagnostics/
suggest.rs

1//! "Did you mean" (spec
2//! `docs/superpowers/specs/2026-10-10-phase-3-4b-fixes-and-colour-design.md`
3//! §4.3).
4
5use crate::{Edit, Fix, Spanned};
6
7/// The optimal string alignment distance between `a` and `b`, over Unicode
8/// scalar values: an insertion, a deletion, a substitution, or a swap of two
9/// adjacent characters each counts one.
10// The indices are offsets into three arrays at once, which is what the
11// lint's iterator form cannot express.
12#[allow(clippy::needless_range_loop)]
13pub fn distance(a: &str, b: &str) -> usize {
14    let a: Vec<char> = a.chars().collect();
15    let b: Vec<char> = b.chars().collect();
16    let mut d = vec![vec![0usize; b.len() + 1]; a.len() + 1];
17    for (i, row) in d.iter_mut().enumerate() {
18        row[0] = i;
19    }
20    for (j, cell) in d[0].iter_mut().enumerate() {
21        *cell = j;
22    }
23    for i in 1..=a.len() {
24        for j in 1..=b.len() {
25            let cost = usize::from(a[i - 1] != b[j - 1]);
26            let mut best = (d[i - 1][j] + 1)
27                .min(d[i][j - 1] + 1)
28                .min(d[i - 1][j - 1] + cost);
29            if i > 1 && j > 1 && a[i - 1] == b[j - 2] && a[i - 2] == b[j - 1] {
30                best = best.min(d[i - 2][j - 2] + 1);
31            }
32            d[i][j] = best;
33        }
34    }
35    d[a.len()][b.len()]
36}
37
38/// The candidate to offer for the unknown `name`, other than `name`
39/// itself (spec §4.3): one equal to it ignoring ASCII case, at any
40/// distance; else the nearest within `max(len, 3) / 3` edits, `len` in
41/// characters; ties in byte order.
42pub fn closest<'c>(name: &str, candidates: impl IntoIterator<Item = &'c str>) -> Option<&'c str> {
43    let len = name.chars().count();
44    let bound = len.max(3) / 3;
45    let mut best: Option<(bool, usize, &'c str)> = None;
46    for c in candidates {
47        if c == name {
48            continue;
49        }
50        let key = if c.eq_ignore_ascii_case(name) {
51            (false, 0, c)
52        } else {
53            // Its distance is at least the difference in length (spec
54            // 3.5a §3, follow-up 8).
55            if c.chars().count().abs_diff(len) > bound {
56                continue;
57            }
58            let d = distance(name, c);
59            if d > bound {
60                continue;
61            }
62            (true, d, c)
63        };
64        if best.map_or(true, |b| key < b) {
65            best = Some(key);
66        }
67    }
68    best.map(|(_, _, c)| c)
69}
70
71/// "change `x` to `y`", `y` the closest of `candidates` (spec §4.3).
72pub fn change_to<'c>(
73    name: &Spanned<String>,
74    candidates: impl IntoIterator<Item = &'c str>,
75) -> Option<Fix> {
76    let to = closest(&name.value, candidates)?;
77    Some(Fix::new(
78        format!("change `{}` to `{to}`", name.value),
79        vec![Edit::replace(name.span, to)],
80    ))
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86    use crate::{FileId, Span};
87
88    #[test]
89    fn a_swap_is_one_edit() {
90        assert_eq!(distance("cuont", "count"), 1);
91        assert_eq!(distance("kitten", "sitting"), 3);
92        assert_eq!(distance("", "ab"), 2);
93    }
94
95    #[test]
96    fn the_nearest_within_the_bound_wins_then_byte_order() {
97        assert_eq!(closest("cuont", ["mount", "count"]), Some("count"));
98        assert_eq!(closest("ab", ["ac", "aa"]), Some("aa"));
99        assert_eq!(closest("count", ["count"]), None);
100    }
101
102    #[test]
103    fn the_bound_is_a_third_of_the_length() {
104        // Five characters: one edit is offered, two are not.
105        assert_eq!(closest("abcde", ["abxde"]), Some("abxde"));
106        assert_eq!(closest("abcde", ["axxde"]), None);
107        // Six characters: two edits are offered.
108        assert_eq!(closest("abcdef", ["axxdef"]), Some("axxdef"));
109    }
110
111    #[test]
112    fn a_name_equal_ignoring_case_is_offered_at_any_distance() {
113        assert_eq!(
114            closest("HTTPCLIENT", ["HTTPCLIENTS", "HttpClient"]),
115            Some("HttpClient")
116        );
117    }
118
119    #[test]
120    fn closest_counts_characters_not_bytes() {
121        // Review Focus 4: Thai is three bytes a character. Four characters
122        // allow one edit; counted in bytes, twelve would allow four.
123        assert_eq!(closest("ราคน", ["ราคา"]), Some("ราคา"));
124        assert_eq!(closest("ราคน", ["รากก"]), None);
125    }
126
127    #[test]
128    fn change_to_replaces_the_name() {
129        let name = Spanned::new("cuont".to_string(), Span::new(4, 9, FileId::DUMMY));
130        let fix = change_to(&name, ["count"]).unwrap();
131        assert_eq!(fix.title, "change `cuont` to `count`");
132        assert_eq!(fix.edits, vec![Edit::replace(name.span, "count")]);
133    }
134
135    #[test]
136    fn a_candidate_too_long_or_short_to_qualify_is_skipped() {
137        // Guard (follow-up 8, spec 3.5a §3): the behaviour must not change
138        // when such candidates are skipped before their distance is taken.
139        assert_eq!(closest("count", ["countdown", "cnt", "coun"]), Some("coun"));
140        assert_eq!(closest("count", ["countdowns", "c"]), None);
141        assert_eq!(closest("count", ["COUNT"]), Some("COUNT"));
142    }
143}
nova_diagnostics/suggest.rs

nova_diagnostics/
suggest.rs
