1 // FIXME(Centril): Move to rustc_span?
3 use rustc_span::symbol::Symbol;
9 /// Finds the Levenshtein distance between two strings
10 pub fn lev_distance(a: &str, b: &str) -> usize {
11 // cases which don't require further computation
13 return b.chars().count();
14 } else if b.is_empty() {
15 return a.chars().count();
18 let mut dcol: Vec<_> = (0..=b.len()).collect();
21 for (i, sc) in a.chars().enumerate() {
23 dcol[0] = current + 1;
25 for (j, tc) in b.chars().enumerate() {
26 let next = dcol[j + 1];
28 dcol[j + 1] = current;
30 dcol[j + 1] = cmp::min(current, next);
31 dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1;
40 /// Finds the best match for a given word in the given iterator
42 /// As a loose rule to avoid the obviously incorrect suggestions, it takes
43 /// an optional limit for the maximum allowable edit distance, which defaults
44 /// to one-third of the given word.
46 /// Besides Levenshtein, we use case insensitive comparison to improve accuracy on an edge case with
47 /// a lower(upper)case letters mismatch.
48 pub fn find_best_match_for_name<'a, T>(
54 T: Iterator<Item = &'a Symbol>,
56 let max_dist = dist.map_or_else(|| cmp::max(lookup.len(), 3) / 3, |d| d);
57 let name_vec: Vec<&Symbol> = iter_names.collect();
59 let (case_insensitive_match, levenshtein_match) = name_vec
62 let dist = lev_distance(lookup, &name.as_str());
63 if dist <= max_dist { Some((name, dist)) } else { None }
65 // Here we are collecting the next structure:
66 // (case_insensitive_match, (levenshtein_match, levenshtein_distance))
67 .fold((None, None), |result, (candidate, dist)| {
69 if candidate.as_str().to_uppercase() == lookup.to_uppercase() {
75 None => Some((candidate, dist)),
76 Some((c, d)) => Some(if dist < d { (candidate, dist) } else { (c, d) }),
80 // Priority of matches:
81 // 1. Exact case insensitive match
82 // 2. Levenshtein distance match
83 // 3. Sorted word match
84 if let Some(candidate) = case_insensitive_match {
86 } else if levenshtein_match.is_some() {
87 levenshtein_match.map(|(candidate, _)| *candidate)
89 find_match_by_sorted_words(name_vec, lookup)
93 fn find_match_by_sorted_words<'a>(iter_names: Vec<&'a Symbol>, lookup: &str) -> Option<Symbol> {
94 iter_names.iter().fold(None, |result, candidate| {
95 if sort_by_words(&candidate.as_str()) == sort_by_words(lookup) {
103 fn sort_by_words(name: &str) -> String {
104 let mut split_words: Vec<&str> = name.split('_').collect();
106 split_words.join("_")