]>
git.proxmox.com Git - rustc.git/blob - src/libsyntax/util/lev_distance.rs
2 use crate::symbol
::Symbol
;
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
11 return b
.chars().count();
12 } else if b
.is_empty() {
13 return a
.chars().count();
16 let mut dcol
: Vec
<_
> = (0..=b
.len()).collect();
19 for (i
, sc
) in a
.chars().enumerate() {
21 dcol
[0] = current
+ 1;
23 for (j
, tc
) in b
.chars().enumerate() {
24 let next
= dcol
[j
+ 1];
26 dcol
[j
+ 1] = current
;
28 dcol
[j
+ 1] = cmp
::min(current
, next
);
29 dcol
[j
+ 1] = cmp
::min(dcol
[j
+ 1], dcol
[j
]) + 1;
38 /// Finds the best match for a given word in the given iterator
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.
44 /// Besides Levenshtein, we use case insensitive comparison to improve accuracy on an edge case with
45 /// a lower(upper)case letters mismatch.
46 pub fn find_best_match_for_name
<'a
, T
>(iter_names
: T
,
48 dist
: Option
<usize>) -> Option
<Symbol
>
49 where T
: Iterator
<Item
= &'a Symbol
> {
50 let max_dist
= dist
.map_or_else(|| cmp
::max(lookup
.len(), 3) / 3, |d
| d
);
52 let (case_insensitive_match
, levenstein_match
) = iter_names
54 let dist
= lev_distance(lookup
, &name
.as_str());
61 // Here we are collecting the next structure:
62 // (case_insensitive_match, (levenstein_match, levenstein_distance))
63 .fold((None
, None
), |result
, (candidate
, dist
)| {
65 if candidate
.as_str().to_uppercase() == lookup
.to_uppercase() {
71 None
=> Some((candidate
, dist
)),
72 Some((c
, d
)) => Some(if dist
< d { (candidate, dist) }
else { (c, d) }
)
77 if let Some(candidate
) = case_insensitive_match
{
78 Some(candidate
) // exact case insensitive match has a higher priority
80 levenstein_match
.map(|(candidate
, _
)| candidate
)