src/libsyntax/util/lev_distance.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use std::cmp;
  12 use symbol::Symbol;
  13
  14 /// Find the Levenshtein distance between two strings
  15 pub fn lev_distance(a: &str, b: &str) -> usize {
  16     // cases which don't require further computation
  17     if a.is_empty() {
  18         return b.chars().count();
  19     } else if b.is_empty() {
  20         return a.chars().count();
  21     }
  22
  23     let mut dcol: Vec<_> = (0..=b.len()).collect();
  24     let mut t_last = 0;
  25
  26     for (i, sc) in a.chars().enumerate() {
  27         let mut current = i;
  28         dcol[0] = current + 1;
  29
  30         for (j, tc) in b.chars().enumerate() {
  31             let next = dcol[j + 1];
  32             if sc == tc {
  33                 dcol[j + 1] = current;
  34             } else {
  35                 dcol[j + 1] = cmp::min(current, next);
  36                 dcol[j + 1] = cmp::min(dcol[j + 1], dcol[j]) + 1;
  37             }
  38             current = next;
  39             t_last = j;
  40         }
  41     }
  42     dcol[t_last + 1]
  43 }
  44
  45 /// Find the best match for a given word in the given iterator
  46 ///
  47 /// As a loose rule to avoid the obviously incorrect suggestions, it takes
  48 /// an optional limit for the maximum allowable edit distance, which defaults
  49 /// to one-third of the given word.
  50 ///
  51 /// Besides Levenshtein, we use case insensitive comparison to improve accuracy on an edge case with
  52 /// a lower(upper)case letters mismatch.
  53 pub fn find_best_match_for_name<'a, T>(iter_names: T,
  54                                        lookup: &str,
  55                                        dist: Option<usize>) -> Option<Symbol>
  56     where T: Iterator<Item = &'a Symbol> {
  57     let max_dist = dist.map_or_else(|| cmp::max(lookup.len(), 3) / 3, |d| d);
  58
  59     let (case_insensitive_match, levenstein_match) = iter_names
  60     .filter_map(|&name| {
  61         let dist = lev_distance(lookup, &name.as_str());
  62         if dist <= max_dist {
  63             Some((name, dist))
  64         } else {
  65             None
  66         }
  67     })
  68     // Here we are collecting the next structure:
  69     // (case_insensitive_match, (levenstein_match, levenstein_distance))
  70     .fold((None, None), |result, (candidate, dist)| {
  71         (
  72             if candidate.as_str().to_uppercase() == lookup.to_uppercase() {
  73                 Some(candidate)
  74             } else {
  75                 result.0
  76             },
  77             match result.1 {
  78                 None => Some((candidate, dist)),
  79                 Some((c, d)) => Some(if dist < d { (candidate, dist) } else { (c, d) })
  80             }
  81         )
  82     });
  83
  84     if let Some(candidate) = case_insensitive_match {
  85         Some(candidate) // exact case insensitive match has a higher priority
  86     } else {
  87         if let Some((candidate, _)) = levenstein_match { Some(candidate) } else { None }
  88     }
  89 }
  90
  91 #[test]
  92 fn test_lev_distance() {
  93     use std::char::{from_u32, MAX};
  94     // Test bytelength agnosticity
  95     for c in (0..MAX as u32)
  96              .filter_map(|i| from_u32(i))
  97              .map(|i| i.to_string()) {
  98         assert_eq!(lev_distance(&c[..], &c[..]), 0);
  99     }
 100
 101     let a = "\nMäry häd ä little lämb\n\nLittle lämb\n";
 102     let b = "\nMary häd ä little lämb\n\nLittle lämb\n";
 103     let c = "Mary häd ä little lämb\n\nLittle lämb\n";
 104     assert_eq!(lev_distance(a, b), 1);
 105     assert_eq!(lev_distance(b, a), 1);
 106     assert_eq!(lev_distance(a, c), 2);
 107     assert_eq!(lev_distance(c, a), 2);
 108     assert_eq!(lev_distance(b, c), 1);
 109     assert_eq!(lev_distance(c, b), 1);
 110 }
 111
 112 #[test]
 113 fn test_find_best_match_for_name() {
 114     use with_globals;
 115     with_globals(|| {
 116         let input = vec![Symbol::intern("aaab"), Symbol::intern("aaabc")];
 117         assert_eq!(
 118             find_best_match_for_name(input.iter(), "aaaa", None),
 119             Some(Symbol::intern("aaab"))
 120         );
 121
 122         assert_eq!(
 123             find_best_match_for_name(input.iter(), "1111111111", None),
 124             None
 125         );
 126
 127         let input = vec![Symbol::intern("aAAA")];
 128         assert_eq!(
 129             find_best_match_for_name(input.iter(), "AAAA", None),
 130             Some(Symbol::intern("aAAA"))
 131         );
 132
 133         let input = vec![Symbol::intern("AAAA")];
 134         // Returns None because `lev_distance > max_dist / 3`
 135         assert_eq!(
 136             find_best_match_for_name(input.iter(), "aaaa", None),
 137             None
 138         );
 139
 140         let input = vec![Symbol::intern("AAAA")];
 141         assert_eq!(
 142             find_best_match_for_name(input.iter(), "aaaa", Some(4)),
 143             Some(Symbol::intern("AAAA"))
 144         );
 145     })
 146 }