rusty_bubbles/internal/
fuzzy.rs

1//! Fuzzy string matching, ported inline from `github.com/sahilm/fuzzy`
2//! (used by the list component's `DefaultFilter`).
3//!
4//! Provides fuzzy string matching optimized for filenames and code symbols
5//! in the style of Sublime Text, VSCode, IntelliJ IDEA et al.
6
7use std::cmp::Ordering;
8
9/// Match represents a matched string.
10#[derive(Debug, Clone)]
11pub struct Match {
12    /// The matched string.
13    pub str: String,
14    /// The index of the matched string in the supplied slice.
15    pub index: usize,
16    /// The indexes of matched characters. Useful for highlighting matches.
17    pub matched_indexes: Vec<usize>,
18    /// Score used to rank matches.
19    pub score: i32,
20}
21
22const FIRST_CHAR_MATCH_BONUS: i32 = 10;
23const MATCH_FOLLOWING_SEPARATOR_BONUS: i32 = 20;
24const CAMEL_CASE_MATCH_BONUS: i32 = 20;
25const ADJACENT_MATCH_BONUS: i32 = 5;
26const UNMATCHED_LEADING_CHAR_PENALTY: i32 = -5;
27const MAX_UNMATCHED_LEADING_CHAR_PENALTY: i32 = -15;
28
29const SEPARATORS: [char; 6] = ['/', '-', '_', '.', ' ', '\\'];
30
31/// Find looks up pattern in data and returns matches in descending order of
32/// match quality. Match quality is determined by a set of bonus and penalty
33/// rules.
34///
35/// The following types of matches apply a bonus:
36///
37/// * The first character in the pattern matches the first character in the
38///   match string.
39/// * The matched character is camel cased.
40/// * The matched character follows a separator such as an underscore
41///   character.
42/// * The matched character is adjacent to a previous match.
43///
44/// Penalties are applied for every character in the search string that
45/// wasn't matched and all leading characters up to the first match.
46///
47/// Results are sorted by best match.
48pub fn find(pattern: &str, data: &[String]) -> Vec<Match> {
49    let mut matches = find_no_sort(pattern, data);
50    matches.sort_by(|a, b| a.score.cmp(&b.score).reverse());
51    matches
52}
53
54/// FindNoSort is an alternative Find implementation that does not sort
55/// the results in the end.
56pub fn find_no_sort(pattern: &str, data: &[String]) -> Vec<Match> {
57    if pattern.is_empty() {
58        return vec![];
59    }
60    let runes: Vec<char> = pattern.chars().collect();
61    let mut matches: Vec<Match> = Vec::new();
62    let mut matched_indexes: Option<Vec<usize>> = None;
63    for (i, s) in data.iter().enumerate() {
64        let mut match_ = Match {
65            str: s.clone(),
66            index: i,
67            matched_indexes: matched_indexes
68                .take()
69                .unwrap_or_else(|| Vec::with_capacity(runes.len())),
70            score: 0,
71        };
72        let mut pattern_index = 0usize;
73        let mut best_score = -1i32;
74        let mut matched_index: isize = -1;
75        let mut curr_adjacent_match_bonus = 0i32;
76        let mut last: char = '\0';
77        let mut last_index = 0usize;
78        let chars: Vec<char> = s.chars().collect();
79        let mut j = 0usize;
80        while j < chars.len() {
81            let candidate = chars[j];
82            if let Some(pc) = runes.get(pattern_index).copied() {
83                if equal_fold(candidate, pc) {
84                    let mut score = 0i32;
85                    if j == 0 {
86                        score += FIRST_CHAR_MATCH_BONUS;
87                    }
88                    if last.is_lowercase() && candidate.is_uppercase() {
89                        score += CAMEL_CASE_MATCH_BONUS;
90                    }
91                    if j != 0 && is_separator(last) {
92                        score += MATCH_FOLLOWING_SEPARATOR_BONUS;
93                    }
94                    if let Some(&last_match) = match_.matched_indexes.last() {
95                        let bonus =
96                            adjacent_char_bonus(last_index, last_match, curr_adjacent_match_bonus);
97                        score += bonus;
98                        // adjacent matches are incremental and keep
99                        // increasing based on previous adjacent matches thus
100                        // we need to maintain the current match bonus
101                        curr_adjacent_match_bonus += bonus;
102                    }
103                    if score > best_score {
104                        best_score = score;
105                        matched_index = j as isize;
106                    }
107                }
108            }
109            let nextp = if pattern_index + 1 < runes.len() {
110                Some(runes[pattern_index + 1])
111            } else {
112                None
113            };
114            let nextc = if j + 1 < chars.len() {
115                Some(chars[j + 1])
116            } else {
117                None
118            };
119            // We apply the best score when we have the next match coming up
120            // or when the search string has ended. Tracking when the next
121            // match is coming up allows us to exhaustively find the best
122            // match and not necessarily the first match.
123            if ((nextp.is_some() && nextc.is_some() && equal_fold(nextp.unwrap(), nextc.unwrap()))
124                || nextc.is_none())
125                && matched_index > -1
126            {
127                if match_.matched_indexes.is_empty() {
128                    let penalty = matched_index as i32 * UNMATCHED_LEADING_CHAR_PENALTY;
129                    best_score += max(penalty, MAX_UNMATCHED_LEADING_CHAR_PENALTY);
130                }
131                match_.score += best_score;
132                match_.matched_indexes.push(matched_index as usize);
133                best_score = -1;
134                pattern_index += 1;
135            }
136            last_index = j;
137            last = candidate;
138            j += 1;
139        }
140        // apply penalty for each unmatched character
141        let penalty = match_.matched_indexes.len() as i32 - chars.len() as i32;
142        match_.score += penalty;
143        if match_.matched_indexes.len() == runes.len() {
144            matches.push(match_);
145            matched_indexes = None;
146        } else {
147            matched_indexes = Some(match_.matched_indexes.clone());
148        }
149    }
150    matches
151}
152
153/// Taken from strings.EqualFold
154fn equal_fold(tr: char, sr: char) -> bool {
155    if tr == sr {
156        return true;
157    }
158    if tr.to_lowercase().collect::<String>() == sr.to_lowercase().collect::<String>() {
159        return true;
160    }
161    // ASCII fast path: uppercase vs lowercase pair.
162    let tr_lower = tr.to_ascii_lowercase();
163    let sr_lower = sr.to_ascii_lowercase();
164    tr_lower == sr_lower && (tr.is_ascii_alphabetic() || sr.is_ascii_alphabetic())
165}
166
167fn adjacent_char_bonus(i: usize, last_match: usize, current_bonus: i32) -> i32 {
168    if last_match == i {
169        return current_bonus * 2 + ADJACENT_MATCH_BONUS;
170    }
171    0
172}
173
174fn is_separator(s: char) -> bool {
175    SEPARATORS.contains(&s)
176}
177
178fn max(x: i32, y: i32) -> i32 {
179    if x > y {
180        x
181    } else {
182        y
183    }
184}
185
186/// SortOrder is used by callers that sort matches themselves (matching Go's
187/// `sort.Stable` on score descending).
188pub fn score_cmp(a: &Match, b: &Match) -> Ordering {
189    b.score.cmp(&a.score)
190}
rusty_bubbles/internal/fuzzy.rs

rusty_bubbles/internal/
fuzzy.rs
