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 ///
  15 /// Returns None if the distance exceeds the limit.
  16 pub fn lev_distance(a: &str, b: &str, limit: usize) -> Option<usize> {
  17     let n = a.chars().count();
  18     let m = b.chars().count();
  19     let min_dist = if n < m { m - n } else { n - m };
  20
  21     if min_dist > limit {
  22         return None;
  23     }
  24     if n == 0 || m == 0 {
  25         return (min_dist <= limit).then_some(min_dist);
  26     }
  27
  28     let mut dcol: Vec<_> = (0..=m).collect();
  29
  30     for (i, sc) in a.chars().enumerate() {
  31         let mut current = i;
  32         dcol[0] = current + 1;
  33
  34         for (j, tc) in b.chars().enumerate() {
  35             let next = dcol[j + 1];
  36             if sc == tc {
  37                 dcol[j + 1] = current;
  38             } else {
  39                 dcol[j + 1] = cmp::min(current, next);
  40                 dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1;
  41             }
  42             current = next;
  43         }
  44     }
  45
  46     (dcol[m] <= limit).then_some(dcol[m])
  47 }
  48
  49 /// Finds the best match for a given word in the given iterator.
  50 ///
  51 /// As a loose rule to avoid the obviously incorrect suggestions, it takes
  52 /// an optional limit for the maximum allowable edit distance, which defaults
  53 /// to one-third of the given word.
  54 ///
  55 /// Besides Levenshtein, we use case insensitive comparison to improve accuracy
  56 /// on an edge case with a lower(upper)case letters mismatch.
  57 #[cold]
  58 pub fn find_best_match_for_name(
  59     candidates: &[Symbol],
  60     lookup: Symbol,
  61     dist: Option<usize>,
  62 ) -> Option<Symbol> {
  63     let lookup = lookup.as_str();
  64     let lookup_uppercase = lookup.to_uppercase();
  65
  66     // Priority of matches:
  67     // 1. Exact case insensitive match
  68     // 2. Levenshtein distance match
  69     // 3. Sorted word match
  70     if let Some(c) = candidates.iter().find(|c| c.as_str().to_uppercase() == lookup_uppercase) {
  71         return Some(*c);
  72     }
  73
  74     let mut dist = dist.unwrap_or_else(|| cmp::max(lookup.len(), 3) / 3);
  75     let mut best = None;
  76     for c in candidates {
  77         match lev_distance(lookup, c.as_str(), dist) {
  78             Some(0) => return Some(*c),
  79             Some(d) => {
  80                 dist = d - 1;
  81                 best = Some(*c);
  82             }
  83             None => {}
  84         }
  85     }
  86     if best.is_some() {
  87         return best;
  88     }
  89
  90     find_match_by_sorted_words(candidates, lookup)
  91 }
  92
  93 fn find_match_by_sorted_words(iter_names: &[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) {
  96             Some(*candidate)
  97         } else {
  98             result
  99         }
 100     })
 101 }
 102
 103 fn sort_by_words(name: &str) -> String {
 104     let mut split_words: Vec<&str> = name.split('_').collect();
 105     // We are sorting primitive &strs and can use unstable sort here.
 106     split_words.sort_unstable();
 107     split_words.join("_")
 108 }