| 1 | //! Fuzzy matching for pickers and filters: a case-insensitive subsequence |
| 2 | //! match that prefers what a person means by a short query. |
| 3 | //! |
| 4 | //! A candidate matches when every character of the query appears in it, in |
| 5 | //! order. Among matches, the score rewards the places a person aims at (the |
| 6 | //! start of the candidate, the start of a word, the character after a path |
| 7 | //! separator, a camelCase hump) and runs of consecutive characters, and |
| 8 | //! charges for gaps. The scorer is deterministic and stable: equal scores |
| 9 | //! keep the caller's order, so a list does not shuffle as you type. |
| 10 | //! |
| 11 | //! Matching is greedy and allocation-free apart from the returned positions: |
| 12 | //! a forward scan finds where the earliest full match ends, and a backward |
| 13 | //! scan from there tightens it to the most compact window. That is the |
| 14 | //! matcher the Codewhale engine uses for `@`-mention and slash-command |
| 15 | //! completion (`mention_completion.rs`, `widgets/mod.rs` |
| 16 | //! `fuzzy_chars_in_order`, `file_search.rs` `fuzzy_score` at `58b1dd3dd`), |
| 17 | //! with the engine's density-and-coverage score replaced by per-character |
| 18 | //! bonuses so the highlight and the rank agree. |
| 19 | //! |
| 20 | //! Positions are `char` indices into the candidate as given, so a picker |
| 21 | //! highlights exactly what it paints. Run caller text through |
| 22 | //! [`crate::text::display_safe`] before scoring when the same text is |
| 23 | //! painted, so the indices line up. |
| 24 | |
| 25 | use std::cmp::Reverse; |
| 26 | |
| 27 | /// A successful match: how good, and which characters of the candidate the |
| 28 | /// query landed on. |
| 29 | #[derive(Clone, Debug, Default, PartialEq, Eq)] |
| 30 | pub struct FuzzyMatch { |
| 31 | /// Higher is better. Comparable only between candidates of one query. |
| 32 | pub score: i32, |
| 33 | /// `char` indices into the candidate, one per query character |
| 34 | /// (whitespace in the query is ignored), ascending. Empty for an empty |
| 35 | /// query. |
| 36 | pub positions: Vec<usize>, |
| 37 | } |
| 38 | |
| 39 | /// One ranked candidate from [`rank_matches`]. |
| 40 | #[derive(Clone, Debug, PartialEq, Eq)] |
| 41 | pub struct FuzzyHit { |
| 42 | /// Index of the candidate in the order it was given. |
| 43 | pub index: usize, |
| 44 | pub score: i32, |
| 45 | pub positions: Vec<usize>, |
| 46 | } |
| 47 | |
| 48 | /// Every matched character. |
| 49 | const SCORE_MATCH: i32 = 16; |
| 50 | /// The first character of the candidate. |
| 51 | const BONUS_START: i32 = 10; |
| 52 | /// The character after a path separator. |
| 53 | const BONUS_PATH: i32 = 10; |
| 54 | /// The character after a space, `_`, `-`, `.` or other punctuation. |
| 55 | const BONUS_WORD: i32 = 8; |
| 56 | /// An uppercase letter after a lowercase one (`camelCase`). |
| 57 | const BONUS_CAMEL: i32 = 7; |
| 58 | /// A digit after a letter (`v2`). |
| 59 | const BONUS_DIGIT: i32 = 3; |
| 60 | /// A character right after the previous match. |
| 61 | const BONUS_RUN: i32 = 5; |
| 62 | /// Typed in the same case as the candidate. |
| 63 | const BONUS_CASE: i32 = 1; |
| 64 | /// The query is the whole candidate. |
| 65 | const BONUS_WHOLE: i32 = 16; |
| 66 | /// Opening a gap between two matches, then each skipped character. |
| 67 | const GAP_OPEN: i32 = 3; |
| 68 | const GAP_EXTEND: i32 = 1; |
| 69 | /// Characters skipped before the first match, up to a cap. |
| 70 | const LEAD_CAP: i32 = 6; |
| 71 | /// Unmatched characters in the candidate, up to a cap, at half a point each, |
| 72 | /// so of two equal matches the shorter wins. |
| 73 | const LENGTH_CAP: usize = 64; |
| 74 | |
| 75 | fn fold(c: char) -> char { |
| 76 | if c.is_ascii() { |
| 77 | c.to_ascii_lowercase() |
| 78 | } else { |
| 79 | c.to_lowercase().next().unwrap_or(c) |
| 80 | } |
| 81 | } |
| 82 | |
| 83 | /// What kind of boundary `c` sits on, given the character before it. |
| 84 | fn boundary(prev: Option<char>, c: char) -> i32 { |
| 85 | let Some(prev) = prev else { |
| 86 | return BONUS_START; |
| 87 | }; |
| 88 | if prev == '/' || prev == '\\' { |
| 89 | BONUS_PATH |
| 90 | } else if !prev.is_alphanumeric() { |
| 91 | BONUS_WORD |
| 92 | } else if prev.is_lowercase() && c.is_uppercase() { |
| 93 | BONUS_CAMEL |
| 94 | } else if prev.is_alphabetic() && c.is_ascii_digit() { |
| 95 | BONUS_DIGIT |
| 96 | } else { |
| 97 | 0 |
| 98 | } |
| 99 | } |
| 100 | |
| 101 | /// The query's characters, folded, whitespace dropped. |
| 102 | fn query_chars(query: &str) -> impl DoubleEndedIterator<Item = char> + Clone + '_ { |
| 103 | query.chars().filter(|c| !c.is_whitespace()).map(fold) |
| 104 | } |
| 105 | |
| 106 | /// Match `query` against `candidate`, or `None` when the query is not a |
| 107 | /// subsequence of it. An empty query matches everything with a zero score. |
| 108 | #[must_use] |
| 109 | pub fn fuzzy_score(query: &str, candidate: &str) -> Option<FuzzyMatch> { |
| 110 | let wanted = query_chars(query).count(); |
| 111 | if wanted == 0 { |
| 112 | return Some(FuzzyMatch::default()); |
| 113 | } |
| 114 | |
| 115 | // Forward: the earliest end of a full match. |
| 116 | let mut need = query_chars(query); |
| 117 | let mut next = need.next(); |
| 118 | let mut end = None; |
| 119 | for (i, c) in candidate.chars().enumerate() { |
| 120 | if Some(fold(c)) == next { |
| 121 | next = need.next(); |
| 122 | if next.is_none() { |
| 123 | end = Some(i); |
| 124 | break; |
| 125 | } |
| 126 | } |
| 127 | } |
| 128 | let end = end?; |
| 129 | let len = candidate.chars().count(); |
| 130 | |
| 131 | // Backward: the latest start that still reaches `end`. |
| 132 | let mut need = query_chars(query).rev(); |
| 133 | let mut next = need.next(); |
| 134 | let mut positions = Vec::with_capacity(wanted); |
| 135 | for (i, c) in candidate.chars().rev().enumerate() { |
| 136 | let at = len - 1 - i; |
| 137 | if at > end { |
| 138 | continue; |
| 139 | } |
| 140 | if Some(fold(c)) == next { |
| 141 | positions.push(at); |
| 142 | next = need.next(); |
| 143 | if next.is_none() { |
| 144 | break; |
| 145 | } |
| 146 | } |
| 147 | } |
| 148 | positions.reverse(); |
| 149 | debug_assert_eq!(positions.len(), wanted); |
| 150 | |
| 151 | let score = score_positions(query, candidate, &positions, len); |
| 152 | Some(FuzzyMatch { score, positions }) |
| 153 | } |
| 154 | |
| 155 | fn score_positions(query: &str, candidate: &str, positions: &[usize], len: usize) -> i32 { |
| 156 | let mut typed = query.chars().filter(|c| !c.is_whitespace()); |
| 157 | let mut score = 0; |
| 158 | let mut prev: Option<char> = None; |
| 159 | let mut last: Option<usize> = None; |
| 160 | let mut run_boundary = 0; |
| 161 | let mut k = 0; |
| 162 | for (i, c) in candidate.chars().enumerate() { |
| 163 | if k < positions.len() && positions[k] == i { |
| 164 | let b = boundary(prev, c); |
| 165 | score += SCORE_MATCH; |
| 166 | match last { |
| 167 | Some(l) if l + 1 == i => score += BONUS_RUN.max(run_boundary).max(b), |
| 168 | Some(l) => { |
| 169 | let gap = i32::try_from(i - l - 1).unwrap_or(i32::MAX); |
| 170 | score -= GAP_OPEN + (gap - 1).max(0) * GAP_EXTEND; |
| 171 | score += b; |
| 172 | run_boundary = b; |
| 173 | } |
| 174 | None => { |
| 175 | score -= i32::try_from(i).unwrap_or(i32::MAX).min(LEAD_CAP) * GAP_EXTEND; |
| 176 | score += b; |
| 177 | run_boundary = b; |
| 178 | } |
| 179 | } |
| 180 | if typed.next() == Some(c) { |
| 181 | score += BONUS_CASE; |
| 182 | } |
| 183 | last = Some(i); |
| 184 | k += 1; |
| 185 | } |
| 186 | prev = Some(c); |
| 187 | } |
| 188 | if positions.len() == len { |
| 189 | score += BONUS_WHOLE; |
| 190 | } |
| 191 | let unmatched = (len - positions.len()).min(LENGTH_CAP); |
| 192 | score - i32::try_from(unmatched / 2).unwrap_or(0) |
| 193 | } |
| 194 | |
| 195 | /// Rank `items` against `query`: the matching ones with their scores and |
| 196 | /// positions, best first; equal scores keep their original order. An empty |
| 197 | /// query returns every item in its original order with no positions. |
| 198 | pub fn rank_matches<S: AsRef<str>>( |
| 199 | query: &str, |
| 200 | items: impl IntoIterator<Item = S>, |
| 201 | ) -> Vec<FuzzyHit> { |
| 202 | let mut hits: Vec<FuzzyHit> = items |
| 203 | .into_iter() |
| 204 | .enumerate() |
| 205 | .filter_map(|(index, item)| { |
| 206 | fuzzy_score(query, item.as_ref()).map(|m| FuzzyHit { |
| 207 | index, |
| 208 | score: m.score, |
| 209 | positions: m.positions, |
| 210 | }) |
| 211 | }) |
| 212 | .collect(); |
| 213 | hits.sort_by_key(|h| (Reverse(h.score), h.index)); |
| 214 | hits |
| 215 | } |
| 216 | |
| 217 | /// The indices of the items that match `query`, best first, equal scores in |
| 218 | /// their original order. An empty query returns every index in order. |
| 219 | pub fn rank<S: AsRef<str>>(query: &str, items: impl IntoIterator<Item = S>) -> Vec<usize> { |
| 220 | rank_matches(query, items) |
| 221 | .into_iter() |
| 222 | .map(|h| h.index) |
| 223 | .collect() |
| 224 | } |
| 225 |