//! Spelling suggestions from an affix dictionary, one engine for every language that reads one //! (Czech, Croatian, Indonesian, Italian, Polish, Portuguese, Russian, Spanish). Candidates come //! in rounds of rising cost, each checked against the dictionary: //! 1. letter case (`warszawa` → `Warszawa`); //! 2. missing or wrong diacritics and other MAP slips, a few letters changed (`zolw` → `żółw`): //! adding a missing accent is the commonest slip and ranks first, while taking away one the //! writer typed ranks after the known confusions; //! 3. the REP table of common confusions (`żeka` → `rzeka`); //! 4. a missing space (`napewno` → `na pewno`), or a missing apostrophe where the dictionary //! knows the elided form (`jadore` → `j'adore`, `lacqua` → `l'acqua`); an elision ranks just //! before the missing space, so after accent-adding, MAP and REP fixes (tying with dropping a //! typed accent); //! 5. keyboard neighbours from the KEY rows, then one typo: a letter left out, added, swapped with //! the next or mistyped (TRY letters); //! 6. when that finds fewer than asked for: the stems that start like the word (MAP relatives //! folded) and share the most letter pairs with it, whose forms are ranked by an edit distance in //! which a MAP slip costs half (two typos at most). //! //! The tables come from the dictionary; a language's [`Tuning`] adds the ones its dictionaries may //! lack and the slips no table can say. The input is bounded ([`MAX_LETTERS`]), and so is every //! round, so a call costs a few thousand dictionary lookups at most. use std::borrow::Cow; use std::collections::{HashMap, HashSet}; use crate::affix::{AffixDict, Casing, capitalize, casing}; /// Longest word suggestions are looked for, in letters. pub(crate) const MAX_LETTERS: usize = 40; const MAX_MAP_VARIANTS: usize = 4096; /// Most candidates kept waiting for the compound check in one call (the rest are dropped). const MAX_DEFERRED: usize = 1 << 14; /// Stems the scan of round 6 expands. const SCAN_STEMS: usize = 48; /// Most affix rules tried in all to make those stems' forms (Mongolian has 12,000 rules). const SCAN_FORMS_WORK: usize = 1 << 16; const COST_CASE: u32 = 0; pub(crate) const COST_ADD_DIACRITIC: u32 = 4; pub(crate) const COST_OTHER_MAP: u32 = 7; const COST_DROP_DIACRITIC: u32 = 11; const COST_REP: u32 = 10; pub(crate) const COST_SPLIT: u32 = 12; /// A missing apostrophe between an elided word and a dictionary word of two letters or more /// (`j'adore`, `qu'il`, `dell'anno`). const COST_ELISION: u32 = COST_SPLIT - 1; /// Any other missing apostrophe the dictionary accepts (a possessive `church's`, an enclitic /// `acusi't`, a contraction `he'd`), ranked after every one-letter fix (`churches`, `acudit`). const COST_APOSTROPHE: u32 = COST_MISTYPE + 1; /// Longest elided first part tried, in letters (`quoiqu'`, `lorsqu'`, `quell'`). const MAX_ELIDED: usize = 7; /// A missing space leaving a half shorter than three letters ([`Split::Anywhere`]). const COST_SPLIT_SHORT: u32 = 17; /// A missing space between two longer halves with no short word beside it ([`Split::Near`]). pub(crate) const COST_SPLIT_LONG: u32 = 18; const COST_KEY: u32 = 13; const COST_SWAP: u32 = 14; const COST_DROP_OR_ADD: u32 = 15; pub(crate) const COST_MISTYPE: u32 = 16; const COST_SCAN: u32 = 20; /// A missing space ranked after every one-word candidate (English: [`Split::Custom`]). pub(crate) const COST_SPLIT_LAST: u32 = COST_SCAN + 4 * 3 + 1; /// What a language adds to its dictionary's tables. pub(crate) struct Tuning { /// Where a missing space may go (round 4). pub split: Split, /// TRY letters for a dictionary without a TRY line. pub alphabet: &'static str, /// MAP groups the language adds to its dictionary's (each string is one group: `"cčć"`). pub map: &'static [&'static str], /// REP confusions the language adds to its dictionary's. pub rep: &'static [(&'static str, &'static str)], /// The cost of a REP confusion. pub rep_cost: u32, /// Most letters a MAP variant changes. pub max_map_changes: usize, /// The cost of changing letter `from` to its MAP relative `to`. pub map_cost: fn(char, char) -> u32, /// The cost of typing letter `c` at `i` of the word (`chars`, lower case) instead. pub mistype_cost: fn(&[char], usize, char) -> u32, /// Offer a word only the dictionary capitalizes (a name, an abbreviation: `Col`, `Wis`) only /// when the word itself is capitalized, and never as half of a missing space (`Che Que`). pub strict_case: bool, /// Offer a missing apostrophe before a suggestible word of 2+ letters as an elision (French /// `j'adore`, Italian `l'acqua`), ranked at [`COST_ELISION`]: after accent-adding, MAP and REP fixes (a tie with dropping a typed accent), /// before the missing space (`j adore`) and the typos. On by default ([`Tuning::DEFAULT`]) because /// the pack languages share it, so it does not mean "this language elides": the dictionary check /// gates it, and a dictionary without such forms never offers one. A language that never elides /// and has apostrophe forms that compete turns it off (English); then every missing apostrophe /// ranks after the one-letter fixes (`churchs` → `churches` before `church's`, `neer` → `never` /// before `ne'er`). pub elision: bool, } /// Where a missing space may go. pub(crate) enum Split { /// Anywhere, dearer when a half is shorter than three letters. Anywhere, /// After a short word that often runs into the next one (`na pewno`, `w ogóle`) or before one /// that runs into the word before (`kocham cię`), dearer between two longer halves, and never /// leaving a stray short half (`że ka`). Near { leading: &'static [&'static str], trailing: &'static [&'static str] }, /// The language's own rule: the cost of the halves `a b`, or `None` to skip them. Custom(fn(&str, &str) -> Option), } impl Tuning { /// The dictionary's tables alone (Czech, Indonesian, Spanish). pub(crate) const DEFAULT: Tuning = Tuning { split: Split::Anywhere, alphabet: "", map: &[], rep: &[], rep_cost: COST_REP, max_map_changes: 4, map_cost, mistype_cost, strict_case: false, elision: true, }; } /// The cost of changing letter `from` to its MAP relative `to`. Adding a missing accent is the /// commonest slip (typing without diacritics); an accent the writer did type is likelier right, /// so taking one away costs more than a known confusion from the REP table. pub(crate) fn map_cost(from: char, to: char) -> u32 { match (from.is_ascii(), to.is_ascii()) { (true, false) => COST_ADD_DIACRITIC, (false, true) => COST_DROP_DIACRITIC, _ => COST_OTHER_MAP, } } /// Any mistyped letter costs the same. fn mistype_cost(_: &[char], _: usize, _: char) -> u32 { COST_MISTYPE } struct Collector<'a> { d: &'a AffixDict, /// The word, lower case. input: String, /// Candidate → the cheapest cost it was offered at (rounds don't run in rising cost). tested: HashMap, /// Suggestion → (cost, order found). found: HashMap, seq: usize, /// May a word the dictionary only has capitalized be offered ([`Tuning::strict_case`])? names: bool, /// May half of a missing space be one ([`Tuning::strict_case`])? split_names: bool, /// Candidates no simple word, left for the compound check: (cost, order, candidate). deferred: Vec<(u32, usize, String)>, /// Steps left for the compound searches of this call (`MAX_SUGGEST_COMPOUND_WORK` at first). compound_work: usize, /// The pieces those searches analysed, shared between them. pieces: crate::affix::Pieces, } impl Collector<'_> { /// Check a lower-case candidate (a word, or two separated by a space) and keep it if every /// word is in the dictionary, as written or capitalized (names). fn offer(&mut self, cand: &str, cost: u32) { if cand.is_empty() || cand == self.input { return; } match self.tested.get_mut(cand) { Some(prev) if *prev <= cost => return, Some(prev) => *prev = cost, None => { self.tested.insert(cand.to_string(), cost); } } // A candidate is checked as simple words here; one of a single word that isn't one waits // for the compound check, which the cheapest candidates get first ([`Self::compounds`]). if !self.accept(cand, cost, false) && self.d.flag_compounds() && !cand.contains(' ') && self.deferred.len() < MAX_DEFERRED { self.seq += 1; self.deferred.push((cost, self.seq, cand.to_string())); } } /// Check the waiting candidates as compounds, cheapest (then earliest) first, in one budget /// of steps per call: compound checks cost far more than lookups, and a one-letter slip of a /// long compound is the likeliest intent. /// /// A candidate changed where the word stops being parts (`ziekenhusopname`: `zieken` and /// `opname` are, `hus` isn't) goes first. fn compounds(&mut self) { let mut waiting = std::mem::take(&mut self.deferred); if waiting.is_empty() { return; } let gap = self.d.compound_gap(&self.input, self.names, &mut self.compound_work, &mut self.pieces); let input: Vec = self.input.chars().collect(); let outside = |cand: &str| { let Some((from, to)) = gap else { return false }; let at = cand.chars().zip(&input).position(|(a, b)| a != *b).unwrap_or(input.len().min(cand.chars().count())); at + 1 < from || at > to + 1 }; let mut waiting: Vec<(bool, u32, usize, String)> = waiting.drain(..).map(|(cost, seq, cand)| (outside(&cand), cost, seq, cand)).collect(); waiting.sort_unstable(); for (_, cost, _, cand) in waiting { if self.compound_work == 0 { break; } // Offered again at a lower cost meanwhile: that offer is the one to check. if self.tested.get(&cand).is_some_and(|&c| c < cost) || self.found.contains_key(&cand) { continue; } self.accept(&cand, cost, true); } } /// Keep `cand` if each of its words is in the dictionary (`compounds`: flag-based compounds /// count); whether it was. fn accept(&mut self, cand: &str, cost: u32, compounds: bool) -> bool { let mut words = Vec::new(); let mut cost = cost; let names = if cand.contains(' ') { self.split_names } else { self.names }; let d = self.d; let mut work = self.compound_work; let pieces = &mut self.pieces; let mut is_word = |w: &str| if compounds { d.flag_compound_spending_suggestible(w, &mut work, pieces) } else { d.contains_suggestible_with(w, false) }; for part in cand.split(' ') { if is_word(part) { words.push(part.to_string()); } else if !names { self.compound_work = work; return false; } else { let c = capitalize(part); if !is_word(&c) { self.compound_work = work; return false; } words.push(c); // A name ranks after a common word at the same distance (`moze` → `może`, then // `Mozę`). cost += 1; } } self.compound_work = work; self.keep(words.join(" "), cost); true } /// Keep a suggestion known to be correct, unless the dictionary says never to offer it. fn keep(&mut self, text: String, cost: u32) { if !text.split(' ').all(|part| self.d.can_suggest(part)) { return; } self.seq += 1; let seq = self.seq; let e = self.found.entry(text).or_insert((cost, seq)); if cost < e.0 { *e = (cost, seq); } } fn count_within(&self, cost: u32) -> usize { self.found.values().filter(|(c, _)| *c <= cost).count() } } /// The MAP groups: the dictionary's, then the language's. fn groups<'a>(d: &'a AffixDict, t: &Tuning) -> Cow<'a, [Vec]> { if t.map.is_empty() { return Cow::Borrowed(d.map()); } Cow::Owned(d.map().iter().cloned().chain(t.map.iter().map(|g| g.chars().collect())).collect()) } /// The other members of every MAP group of `c` (its likely confusions), each once. fn alternatives(c: char, map: &[Vec]) -> Vec { let mut out: Vec = Vec::new(); for x in map.iter().filter(|g| g.contains(&c)).flat_map(|g| g.iter().copied()) { if x != c && !out.contains(&x) { out.push(x); } } out } /// Every way of changing up to `t.max_map_changes` letters of `chars` to a MAP relative (`alts`, /// letter by letter), with its cost: all one-change variants first, then two, and so on, so the /// [`MAX_MAP_VARIANTS`] cap drops the variants with the most changes. fn map_variants(chars: &[char], alts: &[Vec], t: &Tuning, out: &mut Vec<(String, u32)>) { let mut buf = Vec::with_capacity(chars.len()); for n in 1..=t.max_map_changes.min(chars.len()) { exact_map_variants(chars, alts, t, n, 0, &mut buf, out); } } /// [`map_variants`] with exactly `left` more changes, each written after `buf`. fn exact_map_variants(chars: &[char], alts: &[Vec], t: &Tuning, left: usize, cost: u32, buf: &mut Vec, out: &mut Vec<(String, u32)>) { if out.len() >= MAX_MAP_VARIANTS || left > chars.len() { return; } let Some((&c, rest)) = chars.split_first() else { out.push((buf.iter().collect(), cost)); return; }; let (here, later) = alts.split_first().map_or((&[][..], &[][..]), |(h, l)| (h.as_slice(), l)); buf.push(c); exact_map_variants(rest, later, t, left, cost, buf, out); buf.pop(); if left > 0 { for &a in here { buf.push(a); exact_map_variants(rest, later, t, left - 1, cost + (t.map_cost)(c, a), buf, out); buf.pop(); } } } /// A letter's MAP representative (the first of its first group), lower case: `ż` → `z`, `ó` → `o`. pub(crate) fn fold(c: char, map: &[Vec]) -> char { let l = c.to_lowercase().next().unwrap_or(c); map.iter().find(|g| g.contains(&l)).and_then(|g| g.first().copied()).unwrap_or(l) } /// Optimal string alignment distance where a MAP slip (`a`/`ą`, `u`/`ó`) costs 1 and any other /// edit 2; `limit + 1` once it is certainly above `limit`. pub(crate) fn weighted_distance(a: &[char], b: &[char], related: &dyn Fn(char, char) -> bool, limit: u32) -> u32 { let m = b.len(); let over = limit + 1; let mut prev2 = vec![0u32; m + 1]; let mut prev: Vec = (0..=m as u32).map(|j| j * 2).collect(); let mut cur = vec![0u32; m + 1]; for (i, &ai) in a.iter().enumerate() { if let Some(c) = cur.get_mut(0) { *c = (i as u32 + 1) * 2; } let mut row_min = u32::MAX; for (j, &bj) in b.iter().enumerate() { let sub = if ai == bj { 0 } else if related(ai, bj) { 1 } else { 2 }; let at = |v: &[u32], k: usize| v.get(k).copied().unwrap_or(u32::MAX / 4); let mut v = (at(&prev, j + 1) + 2).min(at(&cur, j) + 2).min(at(&prev, j) + sub); if i > 0 && j > 0 && a.get(i - 1) == Some(&bj) && b.get(j - 1) == Some(&ai) { v = v.min(at(&prev2, j - 1) + 2); } if let Some(c) = cur.get_mut(j + 1) { *c = v; } row_min = row_min.min(v); } if m > 0 && row_min > limit { return over; } std::mem::swap(&mut prev2, &mut prev); std::mem::swap(&mut prev, &mut cur); } prev.get(m).copied().unwrap_or(over).min(over) } /// The cost of a missing space between `a` and `b`, or `None` when the split isn't offered. fn split_cost(split: &Split, a: &str, b: &str) -> Option { let long = |part: &str| part.chars().count() >= 3; match split { Split::Anywhere => Some(if long(a) && long(b) { COST_SPLIT } else { COST_SPLIT_SHORT }), Split::Near { leading, trailing } => { if (leading.contains(&a) && long(b)) || (long(a) && trailing.contains(&b)) { Some(COST_SPLIT) } else if long(a) && long(b) { Some(COST_SPLIT_LONG) } else { None } } Split::Custom(cost) => cost(a, b), } } /// Spelling suggestions for `word` from `d`, best first, at most `max`, in the word's letter case. pub(crate) fn suggest_in(d: &AffixDict, word: &str, max: usize, t: &Tuning) -> Vec { let word = word.trim(); let n = word.chars().count(); if n == 0 || n > MAX_LETTERS || max == 0 || d.is_empty() || word.contains(char::is_whitespace) { return Vec::new(); } // The simple-word checks of this call share one budget of affix rules. let _steps = crate::affix::SuggestSteps::start(); let case = casing(word); let input = word.to_lowercase(); let chars: Vec = input.chars().collect(); let names = !t.strict_case || case != Casing::Lower; let split_names = !t.strict_case; let mut col = Collector { d, input: input.clone(), tested: HashMap::new(), found: HashMap::new(), seq: 0, names, split_names, deferred: Vec::new(), compound_work: crate::affix::MAX_SUGGEST_COMPOUND_WORK, pieces: Default::default(), }; add_case(&mut col, word, &input); let map = groups(d, t); add_map_slips(&mut col, &chars, &map, t); add_confusions(&mut col, &input, t); add_splits(&mut col, &input, t); add_key_neighbours(&mut col, &chars); add_typos(&mut col, &chars, t); col.compounds(); // 6. Further off: scan the stems that start like the word. if col.count_within(COST_MISTYPE) < max { scan(&mut col, &chars, &map); col.compounds(); } let mut found: Vec<(String, (u32, usize))> = col.found.into_iter().collect(); // Among equal costs, the change nearest the word's start is the likelier intent // (the first changed letter breaks ties). let diff_at = |text: &str| chars.iter().zip(text.chars()).position(|(a, b)| *a != b).unwrap_or(n); found.sort_by_key(|(text, (cost, seq))| (*cost, diff_at(text), *seq)); let mut out: Vec = Vec::new(); 'found: for (text, _) in found { // A KEEPCASE word only exists in its dictionary case: `Km` would be flagged, so offer `km`. // Under CHECKSHARPS one with `ß` may still be capitalized, or written in capitals with SS // (`Fußball`, `FUSSBALL`), as hunspell 1.7.5 offers. let locked = text.split(' ').any(|p| d.case_locked(p)); let sharp = d.check_sharps() && text.contains('ß'); let recased: Vec = match case { Casing::Initial if !locked || sharp => vec![capitalize(&text)], // In capitals `ß` stays `ß` (`STRAßE` is right with or without CHECKSHARPS); under // CHECKSHARPS the SS spelling comes first, as Hunspell offers it. Casing::Upper if n > 1 => { let ss = text.to_uppercase(); let kept: String = text.split('ß').map(str::to_uppercase).collect::>().join("ß"); match (locked, sharp) { (false, false) => vec![kept], (false, true) => vec![ss, kept], (true, true) => vec![ss, text.clone()], (true, false) => vec![text.clone()], } } _ => vec![text.clone()], }; for t in recased { // Shown as the dictionary's OCONV table writes it (`'` → `’` in French). let t = d.output(&t).into_owned(); if t != word && !out.contains(&t) { out.push(t); } if out.len() >= max { break 'found; } } } out } /// Round 1: letter case. fn add_case(col: &mut Collector, word: &str, input: &str) { if col.d.contains(input) && word != input { col.keep(input.to_string(), COST_CASE); } else if col.d.contains(&capitalize(input)) && word != capitalize(input) { col.keep(capitalize(input), COST_CASE); } } /// Round 2: accents and other MAP slips. fn add_map_slips(col: &mut Collector, chars: &[char], map: &[Vec], t: &Tuning) { let alts: Vec> = chars.iter().map(|&c| alternatives(c, map)).collect(); let mut variants = Vec::new(); map_variants(chars, &alts, t, &mut variants); variants.sort_by_key(|v| v.1); for (v, cost) in &variants { col.offer(v, *cost); } } /// Round 3: common confusions. fn add_confusions(col: &mut Collector, input: &str, t: &Tuning) { let rep = col.d.rep().iter().map(|(from, to)| (from.as_str(), to.as_str())).chain(t.rep.iter().copied()); for (from, to) in rep { if from.is_empty() { continue; } for (i, _) in input.match_indices(from) { if let (Some(a), Some(b)) = (input.get(..i), input.get(i + from.len()..)) { col.offer(&format!("{a}{to}{b}"), t.rep_cost); } } } } /// Round 4: a missing space; both halves must be dictionary words. Before it, a missing /// apostrophe: the dictionary's own check says whether `a'b` is right, so no language list is /// needed and a dictionary without such forms never offers one. A true elision, whose second part /// is a word itself (French `j'adore`, Italian and Catalan `l'acqua`, `dell'anno`), ranks before /// the space (`j adore`) and every typo while [`Tuning::elision`] is on; any other form ranks /// after the one-letter fixes ([`COST_APOSTROPHE`]). At most two lookups per split, and only after /// a short first part ([`MAX_ELIDED`]). fn add_splits(col: &mut Collector, input: &str, t: &Tuning) { let no_apostrophe = !input.contains(['\'', '’']); for (n, (i, _)) in input.char_indices().enumerate().skip(1) { let (Some(a), Some(b)) = (input.get(..i), input.get(i..)) else { continue }; if no_apostrophe && n <= MAX_ELIDED { let word = t.elision && b.chars().nth(1).is_some() && col.d.contains_suggestible_with(b, false); col.offer(&format!("{a}'{b}"), if word { COST_ELISION } else { COST_APOSTROPHE }); } if let Some(cost) = split_cost(&t.split, a, b) { col.offer(&format!("{a} {b}"), cost); } } } /// Round 5: keyboard neighbours from the dictionary's KEY rows. fn add_key_neighbours(col: &mut Collector, chars: &[char]) { for row in col.d.key().split('|').take(32) { let keys: Vec = row.chars().take(128).collect(); for pair in keys.windows(2) { let [a, b] = pair else { continue }; for (i, &c) in chars.iter().enumerate() { let replacement = if c == *a { Some(*b) } else if c == *b { Some(*a) } else { None }; if let Some(replacement) = replacement { let mut v = chars.to_vec(); if let Some(x) = v.get_mut(i) { *x = replacement; } col.offer(&v.iter().collect::(), COST_KEY); } } } } } /// Round 5, second half: one typo, with the TRY letters (the language's when the dictionary has /// none), bounded and each once, in their order: a TRY line lists the commonest letters first, so /// equal-cost candidates come out in that order. fn add_typos(col: &mut Collector, chars: &[char], t: &Tuning) { let d = col.d; let n = chars.len(); let try_chars = if d.try_chars().is_empty() { t.alphabet } else { d.try_chars() }; let mut letters: Vec = Vec::new(); for c in try_chars.chars().filter(|c| c.is_lowercase()).take(128) { if !letters.contains(&c) { letters.push(c); } } let s = |v: &[char]| v.iter().collect::(); for i in 0..n.saturating_sub(1) { if chars.get(i) != chars.get(i + 1) { let mut v = chars.to_vec(); v.swap(i, i + 1); col.offer(&s(&v), COST_SWAP); } } for i in 0..n { let mut v = chars.to_vec(); v.remove(i); col.offer(&s(&v), COST_DROP_OR_ADD); } for i in 0..=n { for &c in &letters { let mut v = chars.to_vec(); v.insert(i, c); col.offer(&s(&v), COST_DROP_OR_ADD); } } for i in 0..n { for &c in &letters { if chars.get(i) != Some(&c) { let mut v = chars.to_vec(); if let Some(x) = v.get_mut(i) { *x = c; } col.offer(&s(&v), (t.mistype_cost)(chars, i, c)); } } } } /// Round 6: rank the stems starting with the word's first letter (or a MAP relative of it, either /// case) by shared letter pairs, then keep the forms of the best within two typos. fn scan(col: &mut Collector, chars: &[char], map: &[Vec]) { let d = col.d; let Some(&first) = chars.first() else { return }; let folded: Vec = chars.iter().map(|&c| fold(c, map)).collect(); let pairs: HashSet<(char, char)> = std::iter::once(' ').chain(folded.iter().copied()).zip(folded.iter().copied()).collect(); let mut firsts: Vec = std::iter::once(first).chain(alternatives(first, map)).collect(); let upper: Vec = firsts.iter().flat_map(|c| c.to_uppercase()).collect(); firsts.extend(upper); firsts.sort_unstable(); firsts.dedup(); let n = folded.len(); let mut best: Vec<(u32, &str)> = Vec::new(); for f in firsts { let prefix = f.to_string(); for stem in d.stems_with_prefix(&prefix) { let sf: Vec = stem.chars().map(|c| fold(c, map)).collect(); let shared = std::iter::once(' ').chain(sf.iter().copied()).zip(sf.iter().copied()).filter(|p| pairs.contains(p)).count(); if shared < 2 { continue; } // Shared pairs, less the stem's letters the word doesn't explain, less a length gap // beyond what an ending explains. let extra = sf.len().saturating_sub(shared); let gap = sf.len().abs_diff(n).saturating_sub(4); let score = (shared * 4).saturating_sub(extra * 3 + gap * 2) as u32; if score == 0 { continue; } if best.len() < SCAN_STEMS { best.push((score, stem)); } else if let Some(min) = best.iter_mut().min_by_key(|b| b.0) && score > min.0 { *min = (score, stem); } } } best.sort_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(b.1))); let related = |a: char, b: char| fold(a, map) == fold(b, map); let limit = 4; let mut budget = SCAN_FORMS_WORK; for (_, stem) in best { for form in d.forms_spending(stem, &mut budget) { let lf: Vec = form.to_lowercase().chars().collect(); if lf.len().abs_diff(chars.len()) > 2 { continue; } if !col.names && form.chars().any(char::is_uppercase) { continue; } let dist = weighted_distance(&lf, chars, &related, limit); if dist <= limit && lf.as_slice() != chars { col.keep(form, COST_SCAN + dist * 3); } } } } #[cfg(test)] mod tests { use super::*; /// craft-libs#487 review: MAP variants are made by number of changes, so when a long word has /// more than [`MAX_MAP_VARIANTS`] of them the cap drops the most-changed ones, never a single /// slip (here the first letter's, which depth-first order reached last). #[test] fn the_map_cap_keeps_the_fewest_changes() { let chars: Vec = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".chars().collect(); let alts = vec!["áàâäãåā".chars().collect::>(); chars.len()]; let mut out = Vec::new(); map_variants(&chars, &alts, &Tuning::DEFAULT, &mut out); assert_eq!(out.len(), MAX_MAP_VARIANTS); let changed = |v: &str| v.chars().filter(|&c| c != 'a').count(); assert_eq!(out.iter().filter(|(v, _)| changed(v) == 1).count(), 30 * 7, "every single slip is kept"); assert!(out.iter().any(|(v, _)| v.starts_with('á') && changed(v) == 1)); assert!(out.windows(2).all(|w| changed(&w[0].0) <= changed(&w[1].0)), "fewest changes first"); } /// craft-libs#490 review: a suggestion recased to capitals keeps `ß` (`STRAßE`, right with or /// without CHECKSHARPS); under CHECKSHARPS the SS form comes first, and a KEEPCASE `ß` word may /// be capitalized or written in capitals with SS. Expected lists are the hunspell 1.7.5 CLI's /// on the same files; every suggestion is right. #[test] fn sharp_s_suggestions_match_hunspell() { let try_ = "TRY esianrtolcdugmphbyfvkwzß\n"; let cases: &[(String, &str, &str, &[&str])] = &[ (format!("SET UTF-8\n{try_}"), "1\nstraße\n", "STRAßEE", &["STRAßE"]), (format!("SET UTF-8\nCHECKSHARPS\n{try_}"), "1\nstraße\n", "STRAßEE", &["STRASSE", "STRAßE"]), (format!("SET UTF-8\nCHECKSHARPS\n{try_}"), "1\nstraße\n", "Straßee", &["Straße"]), (format!("SET UTF-8\nCHECKSHARPS\nKEEPCASE k\n{try_}"), "2\nfußball/k\nGruß/k\n", "FUSBALL", &["FUSSBALL", "fußball"]), (format!("SET UTF-8\nCHECKSHARPS\nKEEPCASE k\n{try_}"), "2\nfußball/k\nGruß/k\n", "Fusball", &["Fußball"]), (format!("SET UTF-8\nCHECKSHARPS\nKEEPCASE k\n{try_}"), "2\nfußball/k\nGruß/k\n", "GRUS", &["GRUSS", "Gruß"]), ]; for (aff, dic, word, want) in cases { let d = AffixDict::from_hunspell(aff, dic, &[]).unwrap(); let got = suggest_in(&d, word, 8, &Tuning::DEFAULT); assert_eq!(&got, want, "{word} with\n{aff}"); for g in &got { assert!(d.check(g), "{word} → {g} is not right"); } } } /// craft-libs#489 review repros: OCONV applies to a suggestion after its case is set, case /// sensitively, as the hunspell 1.7.5 CLI answers on the same files (`KBT` → `KAT`, not /// `K’T`), and every suggestion is right. #[test] fn oconv_suggestions_match_hunspell() { type Case = (&'static str, &'static str, &'static [(&'static str, &'static str)]); let cases: &[Case] = &[ ("SET UTF-8\nTRY ab\nOCONV 1\nOCONV a ’\n", "1\nkat\n", &[("kbt", "k’t"), ("Kbt", "K’t"), ("KBT", "KAT"), ("kot", "k’t")]), ("SET UTF-8\nTRY ab\nOCONV 1\nOCONV k q\n", "1\nkat\n", &[("kbt", "qat"), ("Kbt", "Kat"), ("KBT", "KAT"), ("kot", "qat")]), ( "SET UTF-8\nTRY esianrtolcdugmphbyfvkwz'\nICONV 1\nICONV ’ '\nOCONV 1\nOCONV ' ’\nSFX S Y 1\nSFX S 0 's .\n", "2\ncolour/S\ndon't\n", &[("dont", "don’t"), ("DONT", "DON’T"), ("colours", "colour’s")], ), ]; for (aff, dic, words) in cases { let d = AffixDict::from_hunspell(aff, dic, &[]).unwrap(); for (word, want) in *words { let got = suggest_in(&d, word, 8, &Tuning::DEFAULT); assert!(got.iter().any(|g| g == want), "{word}: {got:?}, want {want}"); for g in &got { assert!(d.check(g) || !aff.contains("ICONV"), "{word} → {g} is not right"); } } } } /// craft-libs#489 review: 65,536 ICONV pairs on one first character cost one hash lookup per /// prefix, not a scan of the table, per position of a long word and per suggestion. #[test] fn a_huge_conversion_table_on_one_character_stays_fast() { let mut aff = String::from("SET UTF-8\nTRY abc\nICONV 65536\n"); let a60 = "a".repeat(60); for c in (0x100u32..).filter_map(char::from_u32).take(65_536) { aff.push_str(&format!("ICONV {a60}{c} x\n")); } let d = AffixDict::from_hunspell(&aff, "1\nabc\n", &[]).unwrap(); let t = std::time::Instant::now(); assert!(!d.check(&"a".repeat(470))); let _ = suggest_in(&d, "abd", 4, &Tuning::DEFAULT); let _ = suggest_in(&d, &"a".repeat(40), 4, &Tuning::DEFAULT); assert!(t.elapsed().as_secs() < 5, "{:?}", t.elapsed()); } #[test] fn an_extra_trailing_letter_is_dropped_before_a_short_word_split() { let d = AffixDict::from_hunspell("", "2\npočítač\nz\n", &[]).unwrap(); let suggestions = suggest_in(&d, "počítačz", 8, &Tuning::DEFAULT); assert_eq!(suggestions.first().map(String::as_str), Some("počítač"), "{suggestions:?}"); assert!(suggestions.contains(&"počítač z".into()), "{suggestions:?}"); } /// A candidate offered again at a lower cost (a REP confusion after a MAP diacritic drop) /// ranks at the lower one. #[test] fn a_cheaper_later_offer_wins() { let d = AffixDict::from_hunspell("", "1\ncafe\n", &[]).unwrap(); let mut col = Collector { d: &d, input: "cafè".into(), tested: HashMap::new(), found: HashMap::new(), seq: 0, names: true, split_names: true, deferred: Vec::new(), compound_work: crate::affix::MAX_SUGGEST_COMPOUND_WORK, pieces: Default::default(), }; col.offer("cafe", COST_DROP_DIACRITIC); col.offer("cafe", COST_REP); col.offer("cafe", COST_SCAN); assert_eq!(col.found.get("cafe").map(|e| e.0), Some(COST_REP)); } #[test] fn distance_weighs_map_slips_half() { let map = vec![vec!['a', 'ą'], vec!['o', 'ó', 'u']]; let related = |a: char, b: char| fold(a, &map) == fold(b, &map); let c = |s: &str| s.chars().collect::>(); assert_eq!(weighted_distance(&c("ktury"), &c("który"), &related, 9), 1); assert_eq!(weighted_distance(&c("kot"), &c("kto"), &related, 9), 2); assert_eq!(weighted_distance(&c("kot"), &c("kotek"), &related, 9), 4); assert_eq!(weighted_distance(&c("kot"), &c("pies"), &related, 2), 3); assert_eq!(weighted_distance(&c(""), &c("ab"), &related, 9), 4); } /// A KEEPCASE word is offered in its dictionary case when the word's own case would be flagged /// (`Kmm` → `km`, never `Km`), and a capitalised KEEPCASE word gets its dictionary form. #[test] fn keepcase_suggestions_are_not_recased_into_errors() { let d = AffixDict::from_hunspell("KEEPCASE K\n", "2\nkm/K\npies\n", &[]).unwrap(); assert!(!d.check("Km") && !d.check("KM")); for (word, want) in [("Kmm", "km"), ("KMM", "km"), ("Km", "km")] { let got = suggest_in(&d, word, 4, &Tuning::DEFAULT); assert!(got.iter().all(|s| s.split(' ').all(|p| d.check(p))), "{word}: {got:?}"); assert_eq!(got.first().map(String::as_str), Some(want), "{word}: {got:?}"); } assert_eq!(suggest_in(&d, "Pies", 4, &Tuning::DEFAULT), Vec::::new()); assert_eq!(suggest_in(&d, "Piesx", 4, &Tuning::DEFAULT).first().map(String::as_str), Some("Pies")); } /// A language's tables come after its dictionary's, a TRY alphabet stands in for a missing TRY /// line, and a split rule decides which missing spaces are offered. #[test] fn tuning_adds_to_the_dictionary_tables() { let d = AffixDict::from_hunspell("", "3\nčaj\nkot\nna\n", &[]).unwrap(); let tuned = Tuning { map: &["cč"], alphabet: "t", rep: &[("xy", "kot")], ..Tuning::DEFAULT }; assert!(!suggest_in(&d, "caj", 4, &Tuning::DEFAULT).contains(&"čaj".into())); assert!(suggest_in(&d, "caj", 4, &tuned).contains(&"čaj".into()), "the language's MAP group"); assert!(suggest_in(&d, "xy", 4, &tuned).contains(&"kot".into()), "the language's REP pair"); assert!(suggest_in(&d, "ko", 4, &tuned).contains(&"kot".into()), "the language's TRY letters"); let near = Tuning { split: Split::Near { leading: &["na"], trailing: &[] }, ..Tuning::DEFAULT }; assert!(suggest_in(&d, "nakot", 4, &near).contains(&"na kot".into())); assert!(!suggest_in(&d, "kotna", 4, &near).contains(&"kot na".into()), "no stray short half"); assert!(suggest_in(&d, "kotna", 4, &Tuning::DEFAULT).contains(&"kot na".into())); } /// A French elision in the shape of the LibreOffice `fr` dictionary (written for this test): /// long flags named after the elided word, `’` read as `'` and written back as `’`. const FR_AFF: &str = "SET UTF-8\nFLAG long\nWORDCHARS -’'\nICONV 1\nICONV ’ '\nOCONV 1\nOCONV ' ’\n\ PFX j' Y 1\nPFX j' 0 j' .\nPFX l' Y 1\nPFX l' 0 l' .\n"; const FR_DIC: &str = "5\nadore/j'\nami/l'\njade\nj\nl\n"; /// Craft-proof bug: French `Jadore` was offered `Adore, J adore, Jade` but never `J’adore`. A /// missing apostrophe the dictionary accepts comes before the missing space, in the /// writer's case and with the dictionary's apostrophe. #[test] fn a_missing_elision_apostrophe_is_offered_before_the_missing_space() { let d = AffixDict::from_hunspell(FR_AFF, FR_DIC, &[]).unwrap(); assert!(d.check("j'adore") && d.check("j’adore") && !d.check("jadore")); for (word, want, space) in [("Jadore", "J’adore", "J adore"), ("jadore", "j’adore", "j adore"), ("JADORE", "J’ADORE", "J ADORE"), ("lami", "l’ami", "l ami")] { let got = suggest_in(&d, word, 6, &Tuning::DEFAULT); assert_eq!(got.first().map(String::as_str), Some(want), "{word}: {got:?}"); let at = |s: &str| got.iter().position(|g| g == s); assert!(at(want) < at(space) || at(space).is_none(), "{word}: {got:?}"); } // A word the writer gave an apostrophe isn't split again. assert!(!suggest_in(&d, "j'adorr", 6, &Tuning::DEFAULT).iter().any(|g| g.matches('’').count() > 1)); } /// A dictionary without elided forms offers no apostrophe: the missing space is still first. #[test] fn no_apostrophe_without_elided_forms_in_the_dictionary() { let d = AffixDict::from_hunspell("SET UTF-8\n", "4\nadore\nj\nna\npewno\n", &[]).unwrap(); for word in ["jadore", "napewno"] { let got = suggest_in(&d, word, 6, &Tuning::DEFAULT); assert!(got.iter().all(|g| !g.contains(['\'', '’'])), "{word}: {got:?}"); } assert_eq!(suggest_in(&d, "napewno", 6, &Tuning::DEFAULT).first().map(String::as_str), Some("na pewno")); } /// Review of the elision fix: an apostrophe form whose second part is no word (a Catalan /// enclitic `acusi't`, an English possessive `church's`) ranks after the one-letter fixes, /// while a true elision (`l'home`) still ranks first among them. #[test] fn an_apostrophe_before_no_word_ranks_after_one_letter_fixes() { let aff = "SET UTF-8\nTRY acdehimorstu\nWORDCHARS '\nSFX T Y 1\nSFX T 0 't .\nPFX L Y 1\nPFX L 0 l' .\nSFX S Y 1\nSFX S 0 es .\nSFX M Y 1\nSFX M 0 's .\n"; let d = AffixDict::from_hunspell(aff, "5\nacudit\nacusi/T\nhome/L\nl\nchurch/SM\n", &[]).unwrap(); assert!(d.check("acusi't") && d.check("church's")); for (word, before, after) in [("acusit", "acudit", "acusi't"), ("churchs", "churches", "church's"), ("lhome", "l'home", "l home")] { let got = suggest_in(&d, word, 8, &Tuning::DEFAULT); let at = |s: &str| got.iter().position(|g| g == s); assert!(at(before).is_some() && at(before) < at(after) && at(after).is_some(), "{word}: {got:?}"); } assert_eq!(suggest_in(&d, "lhome", 8, &Tuning::DEFAULT).first().map(String::as_str), Some("l'home")); assert!(suggest_in(&d, "churchs", 8, &Tuning::DEFAULT).iter().position(|g| g == "church") < Some(2), "drop the s"); } /// A language without elision ([`Tuning::elision`], English) ranks every missing apostrophe /// after the one-letter fixes, even before a word (`neer` → `near` before `ne'er`). #[test] fn a_language_without_elision_ranks_apostrophes_late() { let d = AffixDict::from_hunspell("SET UTF-8\nTRY aenr\nWORDCHARS '\n", "3\nne'er\ner\nnear\n", &[]).unwrap(); let english = Tuning { elision: false, ..Tuning::DEFAULT }; assert_eq!(suggest_in(&d, "neer", 4, &english).first().map(String::as_str), Some("near")); assert!(suggest_in(&d, "neer", 4, &english).contains(&"ne'er".to_string())); assert_eq!(suggest_in(&d, "neer", 4, &Tuning::DEFAULT).first().map(String::as_str), Some("ne'er"), "an elision"); } }