compiler/rustc_span/src/lev_distance.rs

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