Skip to main content

logicaffeine_language/
suggest.rs

1//! Spelling suggestions for unknown words.
2//!
3//! This module provides fuzzy matching to suggest corrections for misspelled
4//! words in the input. It uses Levenshtein distance to find similar words
5//! from a known vocabulary list.
6//!
7//! When the parser encounters an unknown word, this module can suggest
8//! "Did you mean X?" alternatives based on edit distance.
9
10/// Compute the Levenshtein edit distance between two strings.
11pub fn levenshtein(a: &str, b: &str) -> usize {
12    let a_chars: Vec<char> = a.chars().collect();
13    let b_chars: Vec<char> = b.chars().collect();
14    let m = a_chars.len();
15    let n = b_chars.len();
16
17    if m == 0 {
18        return n;
19    }
20    if n == 0 {
21        return m;
22    }
23
24    let mut prev: Vec<usize> = (0..=n).collect();
25    let mut curr = vec![0; n + 1];
26
27    for i in 1..=m {
28        curr[0] = i;
29        for j in 1..=n {
30            let cost = if a_chars[i - 1] == b_chars[j - 1] {
31                0
32            } else {
33                1
34            };
35            curr[j] = (prev[j] + 1).min(curr[j - 1] + 1).min(prev[j - 1] + cost);
36        }
37        std::mem::swap(&mut prev, &mut curr);
38    }
39
40    prev[n]
41}
42
43pub fn find_similar<'a>(
44    word: &str,
45    candidates: &[&'a str],
46    max_distance: usize,
47) -> Option<&'a str> {
48    let word_lower = word.to_lowercase();
49    let mut best: Option<(&str, usize)> = None;
50
51    for &candidate in candidates {
52        let dist = levenshtein(&word_lower, &candidate.to_lowercase());
53        if dist <= max_distance {
54            match best {
55                None => best = Some((candidate, dist)),
56                Some((_, d)) if dist < d => best = Some((candidate, dist)),
57                _ => {}
58            }
59        }
60    }
61
62    best.map(|(s, _)| s)
63}
64
65/// The candidate an author most likely meant by `word` — the nearest by edit distance, compared
66/// case-insensitively, when it is within a third of the word's length (at least one edit). The
67/// first of equally near candidates wins, so a caller that lists candidates in a stable order gets
68/// a stable answer. `word` itself never counts as a suggestion for itself.
69///
70/// The one did-you-mean rule every LGX refusal uses: a misspelt event qualifier, an unknown
71/// component, an unresolved name in a template, a prop a placement does not declare.
72pub fn did_you_mean<'c>(
73    word: &str,
74    candidates: impl IntoIterator<Item = &'c str>,
75) -> Option<&'c str> {
76    let lower = word.to_lowercase();
77    let budget = (lower.chars().count() / 3).max(1);
78    let mut best: Option<(usize, &'c str)> = None;
79    for candidate in candidates {
80        if candidate == word {
81            continue;
82        }
83        let distance = typo_distance(&lower, &candidate.to_lowercase());
84        if distance <= budget && best.map_or(true, |(d, _)| distance < d) {
85            best = Some((distance, candidate));
86        }
87    }
88    best.map(|(_, c)| c)
89}
90
91/// Edit distance where swapping two adjacent characters is one edit (the optimal string alignment
92/// distance) — the typo a fast typist makes most (`doen` for `done`), which plain Levenshtein
93/// counts as two.
94pub fn typo_distance(a: &str, b: &str) -> usize {
95    let a: Vec<char> = a.chars().collect();
96    let b: Vec<char> = b.chars().collect();
97    let (m, n) = (a.len(), b.len());
98    let mut d = vec![vec![0usize; n + 1]; m + 1];
99    for (i, row) in d.iter_mut().enumerate() {
100        row[0] = i;
101    }
102    for j in 0..=n {
103        d[0][j] = j;
104    }
105    for i in 1..=m {
106        for j in 1..=n {
107            let cost = if a[i - 1] == b[j - 1] { 0 } else { 1 };
108            d[i][j] = (d[i - 1][j] + 1)
109                .min(d[i][j - 1] + 1)
110                .min(d[i - 1][j - 1] + cost);
111            if i > 1 && j > 1 && a[i - 1] == b[j - 2] && a[i - 2] == b[j - 1] {
112                d[i][j] = d[i][j].min(d[i - 2][j - 2] + 1);
113            }
114        }
115    }
116    d[m][n]
117}
118
119pub const KNOWN_WORDS: &[&str] = &[
120    "all",
121    "some",
122    "no",
123    "most",
124    "few",
125    "every",
126    "the",
127    "a",
128    "an",
129    "this",
130    "that",
131    "is",
132    "are",
133    "was",
134    "were",
135    "be",
136    "and",
137    "or",
138    "if",
139    "then",
140    "not",
141    "must",
142    "can",
143    "may",
144    "should",
145    "would",
146    "could",
147    "who",
148    "what",
149    "where",
150    "when",
151    "why",
152    "how",
153    "man",
154    "men",
155    "woman",
156    "women",
157    "dog",
158    "cat",
159    "bird",
160    "mortal",
161    "happy",
162    "sad",
163    "tall",
164    "fast",
165    "slow",
166    "loves",
167    "runs",
168    "sees",
169    "knows",
170    "thinks",
171    "logic",
172    "reason",
173    "truth",
174    "false",
175    "John",
176    "Mary",
177    "Socrates",
178    "Aristotle",
179    "to",
180    "by",
181    "with",
182    "from",
183    "for",
184    "in",
185    "on",
186    "at",
187    "himself",
188    "herself",
189    "itself",
190    "themselves",
191    "he",
192    "she",
193    "it",
194    "they",
195    "him",
196    "her",
197    "them",
198];
199
200#[cfg(test)]
201#[path = "../../logicaffeine_tests/unit/logicaffeine_language/suggest/tests.rs"]
202mod tests;