compiler/rustc_span/src/lev_distance.rs

   1 //! Levenshtein distances.
   2 //!
   3 //! The [Levenshtein distance] is a metric for measuring the difference between two strings.
   4 //!
   5 //! [Levenshtein distance]: https://en.wikipedia.org/wiki/Levenshtein_distance
   6
   7 use crate::symbol::Symbol;
   8 use std::cmp;
   9
  10 #[cfg(test)]
  11 mod tests;
  12
  13 /// Finds the Levenshtein distance between two strings.
  14 pub fn lev_distance(a: &str, b: &str) -> usize {
  15     // cases which don't require further computation
  16     if a.is_empty() {
  17         return b.chars().count();
  18     } else if b.is_empty() {
  19         return a.chars().count();
  20     }
  21
  22     let mut dcol: Vec<_> = (0..=b.len()).collect();
  23     let mut t_last = 0;
  24
  25     for (i, sc) in a.chars().enumerate() {
  26         let mut current = i;
  27         dcol[0] = current + 1;
  28
  29         for (j, tc) in b.chars().enumerate() {
  30             let next = dcol[j + 1];
  31             if sc == tc {
  32                 dcol[j + 1] = current;
  33             } else {
  34                 dcol[j + 1] = cmp::min(current, next);
  35                 dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1;
  36             }
  37             current = next;
  38             t_last = j;
  39         }
  40     }
  41     dcol[t_last + 1]
  42 }
  43
  44 /// Finds the best match for a given word in the given iterator.
  45 ///
  46 /// As a loose rule to avoid the obviously incorrect suggestions, it takes
  47 /// an optional limit for the maximum allowable edit distance, which defaults
  48 /// to one-third of the given word.
  49 ///
  50 /// Besides Levenshtein, we use case insensitive comparison to improve accuracy
  51 /// on an edge case with a lower(upper)case letters mismatch.
  52 #[cold]
  53 pub fn find_best_match_for_name(
  54     name_vec: &[Symbol],
  55     lookup: Symbol,
  56     dist: Option<usize>,
  57 ) -> Option<Symbol> {
  58     let lookup = lookup.as_str();
  59     let lookup_uppercase = lookup.to_uppercase();
  60     let max_dist = dist.unwrap_or_else(|| cmp::max(lookup.len(), 3) / 3);
  61
  62     // Priority of matches:
  63     // 1. Exact case insensitive match
  64     // 2. Levenshtein distance match
  65     // 3. Sorted word match
  66     if let Some(case_insensitive_match) =
  67         name_vec.iter().find(|candidate| candidate.as_str().to_uppercase() == lookup_uppercase)
  68     {
  69         return Some(*case_insensitive_match);
  70     }
  71     let levenshtein_match = name_vec
  72         .iter()
  73         .filter_map(|&name| {
  74             let dist = lev_distance(lookup, name.as_str());
  75             if dist <= max_dist { Some((name, dist)) } else { None }
  76         })
  77         // Here we are collecting the next structure:
  78         // (levenshtein_match, levenshtein_distance)
  79         .fold(None, |result, (candidate, dist)| match result {
  80             None => Some((candidate, dist)),
  81             Some((c, d)) => Some(if dist < d { (candidate, dist) } else { (c, d) }),
  82         });
  83     if levenshtein_match.is_some() {
  84         levenshtein_match.map(|(candidate, _)| candidate)
  85     } else {
  86         find_match_by_sorted_words(name_vec, lookup)
  87     }
  88 }
  89
  90 fn find_match_by_sorted_words(iter_names: &[Symbol], lookup: &str) -> Option<Symbol> {
  91     iter_names.iter().fold(None, |result, candidate| {
  92         if sort_by_words(candidate.as_str()) == sort_by_words(lookup) {
  93             Some(*candidate)
  94         } else {
  95             result
  96         }
  97     })
  98 }
  99
 100 fn sort_by_words(name: &str) -> String {
 101     let mut split_words: Vec<&str> = name.split('_').collect();
 102     // We are sorting primitive &strs and can use unstable sort here.
 103     split_words.sort_unstable();
 104     split_words.join("_")
 105 }