1use std::{
2 borrow::{Borrow, Cow},
3 collections::BTreeMap,
4 sync::atomic::{self, AtomicBool},
5};
6
7use crate::CharBag;
8
9const BASE_DISTANCE_PENALTY: f64 = 0.6;
10const ADDITIONAL_DISTANCE_PENALTY: f64 = 0.05;
11const MIN_DISTANCE_PENALTY: f64 = 0.2;
12
13// TODO:
14// Use `Path` instead of `&str` for paths.
15pub struct Matcher<'a> {
16 query: &'a [char],
17 lowercase_query: &'a [char],
18 query_char_bag: CharBag,
19 smart_case: bool,
20 min_score: f64,
21 match_positions: Vec<usize>,
22 last_positions: Vec<usize>,
23 score_matrix: Vec<Option<f64>>,
24 best_position_matrix: Vec<usize>,
25}
26
27pub trait MatchCandidate {
28 fn has_chars(&self, bag: CharBag) -> bool;
29 fn to_string(&self) -> Cow<'_, str>;
30}
31
32impl<'a> Matcher<'a> {
33 pub fn new(
34 query: &'a [char],
35 lowercase_query: &'a [char],
36 query_char_bag: CharBag,
37 smart_case: bool,
38 ) -> Self {
39 Self {
40 query,
41 lowercase_query,
42 query_char_bag,
43 min_score: 0.0,
44 last_positions: vec![0; lowercase_query.len()],
45 match_positions: vec![0; query.len()],
46 score_matrix: Vec::new(),
47 best_position_matrix: Vec::new(),
48 smart_case,
49 }
50 }
51
52 /// Filter and score fuzzy match candidates. Results are returned unsorted, in the same order as
53 /// the input candidates.
54 pub(crate) fn match_candidates<C, R, F, T>(
55 &mut self,
56 prefix: &[char],
57 lowercase_prefix: &[char],
58 candidates: impl Iterator<Item = T>,
59 results: &mut Vec<R>,
60 cancel_flag: &AtomicBool,
61 build_match: F,
62 ) where
63 C: MatchCandidate,
64 T: Borrow<C>,
65 F: Fn(&C, f64, &Vec<usize>) -> R,
66 {
67 let mut candidate_chars = Vec::new();
68 let mut lowercase_candidate_chars = Vec::new();
69 let mut extra_lowercase_chars = BTreeMap::new();
70
71 for candidate in candidates {
72 if !candidate.borrow().has_chars(self.query_char_bag) {
73 continue;
74 }
75
76 if cancel_flag.load(atomic::Ordering::Relaxed) {
77 break;
78 }
79
80 candidate_chars.clear();
81 lowercase_candidate_chars.clear();
82 extra_lowercase_chars.clear();
83 for (i, c) in candidate.borrow().to_string().chars().enumerate() {
84 candidate_chars.push(c);
85 let mut char_lowercased = c.to_lowercase().collect::<Vec<_>>();
86 if char_lowercased.len() > 1 {
87 extra_lowercase_chars.insert(i, char_lowercased.len() - 1);
88 }
89 lowercase_candidate_chars.append(&mut char_lowercased);
90 }
91
92 if !self.find_last_positions(lowercase_prefix, &lowercase_candidate_chars) {
93 continue;
94 }
95
96 let matrix_len = self.query.len() * (prefix.len() + candidate_chars.len());
97 self.score_matrix.clear();
98 self.score_matrix.resize(matrix_len, None);
99 self.best_position_matrix.clear();
100 self.best_position_matrix.resize(matrix_len, 0);
101
102 let score = self.score_match(
103 &candidate_chars,
104 &lowercase_candidate_chars,
105 prefix,
106 lowercase_prefix,
107 &extra_lowercase_chars,
108 );
109
110 if score > 0.0 {
111 results.push(build_match(
112 candidate.borrow(),
113 score,
114 &self.match_positions,
115 ));
116 }
117 }
118 }
119
120 fn find_last_positions(
121 &mut self,
122 lowercase_prefix: &[char],
123 lowercase_candidate: &[char],
124 ) -> bool {
125 let mut lowercase_prefix = lowercase_prefix.iter();
126 let mut lowercase_candidate = lowercase_candidate.iter();
127 for (i, char) in self.lowercase_query.iter().enumerate().rev() {
128 if let Some(j) = lowercase_candidate.rposition(|c| c == char) {
129 self.last_positions[i] = j + lowercase_prefix.len();
130 } else if let Some(j) = lowercase_prefix.rposition(|c| c == char) {
131 self.last_positions[i] = j;
132 } else {
133 return false;
134 }
135 }
136 true
137 }
138
139 fn score_match(
140 &mut self,
141 path: &[char],
142 path_lowercased: &[char],
143 prefix: &[char],
144 lowercase_prefix: &[char],
145 extra_lowercase_chars: &BTreeMap<usize, usize>,
146 ) -> f64 {
147 let score = self.recursive_score_match(
148 path,
149 path_lowercased,
150 prefix,
151 lowercase_prefix,
152 0,
153 0,
154 self.query.len() as f64,
155 extra_lowercase_chars,
156 ) * self.query.len() as f64;
157
158 if score <= 0.0 {
159 return 0.0;
160 }
161
162 let path_len = prefix.len() + path.len();
163 let mut cur_start = 0;
164 let mut byte_ix = 0;
165 let mut char_ix = 0;
166 for i in 0..self.query.len() {
167 let match_char_ix = self.best_position_matrix[i * path_len + cur_start];
168 while char_ix < match_char_ix {
169 let ch = prefix
170 .get(char_ix)
171 .or_else(|| path.get(char_ix - prefix.len()))
172 .unwrap();
173 byte_ix += ch.len_utf8();
174 char_ix += 1;
175 }
176 cur_start = match_char_ix + 1;
177 self.match_positions[i] = byte_ix;
178 }
179
180 score
181 }
182
183 fn recursive_score_match(
184 &mut self,
185 path: &[char],
186 path_lowercased: &[char],
187 prefix: &[char],
188 lowercase_prefix: &[char],
189 query_idx: usize,
190 path_idx: usize,
191 cur_score: f64,
192 extra_lowercase_chars: &BTreeMap<usize, usize>,
193 ) -> f64 {
194 use std::path::MAIN_SEPARATOR;
195
196 if query_idx == self.query.len() {
197 return 1.0;
198 }
199
200 let path_len = prefix.len() + path.len();
201
202 if let Some(memoized) = self.score_matrix[query_idx * path_len + path_idx] {
203 return memoized;
204 }
205
206 let mut score = 0.0;
207 let mut best_position = 0;
208
209 let query_char = self.lowercase_query[query_idx];
210 let limit = self.last_positions[query_idx];
211
212 let mut last_slash = 0;
213 for j in path_idx..=limit {
214 let extra_lowercase_chars_count = extra_lowercase_chars
215 .iter()
216 .take_while(|(i, _)| i < &&j)
217 .map(|(_, increment)| increment)
218 .sum::<usize>();
219 let j_regular = j - extra_lowercase_chars_count;
220
221 let path_char = if j_regular < prefix.len() {
222 lowercase_prefix[j]
223 } else {
224 path_lowercased[j - prefix.len()]
225 };
226 let is_path_sep = path_char == MAIN_SEPARATOR;
227
228 if query_idx == 0 && is_path_sep {
229 last_slash = j_regular;
230 }
231
232 #[cfg(not(target_os = "windows"))]
233 let need_to_score =
234 query_char == path_char || (is_path_sep && query_char == '_' || query_char == '\\');
235 // `query_char == '\\'` breaks `test_match_path_entries` on Windows, `\` is only used as a path separator on Windows.
236 #[cfg(target_os = "windows")]
237 let need_to_score = query_char == path_char || (is_path_sep && query_char == '_');
238 if need_to_score {
239 let curr = if j_regular < prefix.len() {
240 prefix[j_regular]
241 } else {
242 path[j_regular - prefix.len()]
243 };
244
245 let mut char_score = 1.0;
246 if j > path_idx {
247 let last = if j_regular - 1 < prefix.len() {
248 prefix[j_regular - 1]
249 } else {
250 path[j_regular - 1 - prefix.len()]
251 };
252
253 if last == MAIN_SEPARATOR {
254 char_score = 0.9;
255 } else if (last == '-' || last == '_' || last == ' ' || last.is_numeric())
256 || (last.is_lowercase() && curr.is_uppercase())
257 {
258 char_score = 0.8;
259 } else if last == '.' {
260 char_score = 0.7;
261 } else if query_idx == 0 {
262 char_score = BASE_DISTANCE_PENALTY;
263 } else {
264 char_score = MIN_DISTANCE_PENALTY.max(
265 BASE_DISTANCE_PENALTY
266 - (j - path_idx - 1) as f64 * ADDITIONAL_DISTANCE_PENALTY,
267 );
268 }
269 }
270
271 // Apply a severe penalty if the case doesn't match.
272 // This will make the exact matches have higher score than the case-insensitive and the
273 // path insensitive matches.
274 if (self.smart_case || curr == MAIN_SEPARATOR) && self.query[query_idx] != curr {
275 char_score *= 0.001;
276 }
277
278 let mut multiplier = char_score;
279
280 // Scale the score based on how deep within the path we found the match.
281 if query_idx == 0 {
282 multiplier /= ((prefix.len() + path.len()) - last_slash) as f64;
283 }
284
285 let mut next_score = 1.0;
286 if self.min_score > 0.0 {
287 next_score = cur_score * multiplier;
288 // Scores only decrease. If we can't pass the previous best, bail
289 if next_score < self.min_score {
290 // Ensure that score is non-zero so we use it in the memo table.
291 if score == 0.0 {
292 score = 1e-18;
293 }
294 continue;
295 }
296 }
297
298 let new_score = self.recursive_score_match(
299 path,
300 path_lowercased,
301 prefix,
302 lowercase_prefix,
303 query_idx + 1,
304 j + 1,
305 next_score,
306 extra_lowercase_chars,
307 ) * multiplier;
308
309 if new_score > score {
310 score = new_score;
311 best_position = j_regular;
312 // Optimization: can't score better than 1.
313 if new_score == 1.0 {
314 break;
315 }
316 }
317 }
318 }
319
320 if best_position != 0 {
321 self.best_position_matrix[query_idx * path_len + path_idx] = best_position;
322 }
323
324 self.score_matrix[query_idx * path_len + path_idx] = Some(score);
325 score
326 }
327}
328
329#[cfg(test)]
330mod tests {
331 use crate::{PathMatch, PathMatchCandidate};
332
333 use super::*;
334 use std::{
335 path::{Path, PathBuf},
336 sync::Arc,
337 };
338
339 #[test]
340 fn test_get_last_positions() {
341 let mut query: &[char] = &['d', 'c'];
342 let mut matcher = Matcher::new(query, query, query.into(), false);
343 let result = matcher.find_last_positions(&['a', 'b', 'c'], &['b', 'd', 'e', 'f']);
344 assert!(!result);
345
346 query = &['c', 'd'];
347 let mut matcher = Matcher::new(query, query, query.into(), false);
348 let result = matcher.find_last_positions(&['a', 'b', 'c'], &['b', 'd', 'e', 'f']);
349 assert!(result);
350 assert_eq!(matcher.last_positions, vec![2, 4]);
351
352 query = &['z', '/', 'z', 'f'];
353 let mut matcher = Matcher::new(query, query, query.into(), false);
354 let result = matcher.find_last_positions(&['z', 'e', 'd', '/'], &['z', 'e', 'd', '/', 'f']);
355 assert!(result);
356 assert_eq!(matcher.last_positions, vec![0, 3, 4, 8]);
357 }
358
359 #[cfg(not(target_os = "windows"))]
360 #[test]
361 fn test_match_path_entries() {
362 let paths = vec![
363 "",
364 "a",
365 "ab",
366 "abC",
367 "abcd",
368 "alphabravocharlie",
369 "AlphaBravoCharlie",
370 "thisisatestdir",
371 "/////ThisIsATestDir",
372 "/this/is/a/test/dir",
373 "/test/tiatd",
374 ];
375
376 assert_eq!(
377 match_single_path_query("abc", false, &paths),
378 vec![
379 ("abC", vec![0, 1, 2]),
380 ("abcd", vec![0, 1, 2]),
381 ("AlphaBravoCharlie", vec![0, 5, 10]),
382 ("alphabravocharlie", vec![4, 5, 10]),
383 ]
384 );
385 assert_eq!(
386 match_single_path_query("t/i/a/t/d", false, &paths),
387 vec![("/this/is/a/test/dir", vec![1, 5, 6, 8, 9, 10, 11, 15, 16]),]
388 );
389
390 assert_eq!(
391 match_single_path_query("tiatd", false, &paths),
392 vec![
393 ("/test/tiatd", vec![6, 7, 8, 9, 10]),
394 ("/this/is/a/test/dir", vec![1, 6, 9, 11, 16]),
395 ("/////ThisIsATestDir", vec![5, 9, 11, 12, 16]),
396 ("thisisatestdir", vec![0, 2, 6, 7, 11]),
397 ]
398 );
399 }
400
401 /// todo(windows)
402 /// Now, on Windows, users can only use the backslash as a path separator.
403 /// I do want to support both the backslash and the forward slash as path separators on Windows.
404 #[cfg(target_os = "windows")]
405 #[test]
406 fn test_match_path_entries() {
407 let paths = vec![
408 "",
409 "a",
410 "ab",
411 "abC",
412 "abcd",
413 "alphabravocharlie",
414 "AlphaBravoCharlie",
415 "thisisatestdir",
416 "\\\\\\\\\\ThisIsATestDir",
417 "\\this\\is\\a\\test\\dir",
418 "\\test\\tiatd",
419 ];
420
421 assert_eq!(
422 match_single_path_query("abc", false, &paths),
423 vec![
424 ("abC", vec![0, 1, 2]),
425 ("abcd", vec![0, 1, 2]),
426 ("AlphaBravoCharlie", vec![0, 5, 10]),
427 ("alphabravocharlie", vec![4, 5, 10]),
428 ]
429 );
430 assert_eq!(
431 match_single_path_query("t\\i\\a\\t\\d", false, &paths),
432 vec![(
433 "\\this\\is\\a\\test\\dir",
434 vec![1, 5, 6, 8, 9, 10, 11, 15, 16]
435 ),]
436 );
437
438 assert_eq!(
439 match_single_path_query("tiatd", false, &paths),
440 vec![
441 ("\\test\\tiatd", vec![6, 7, 8, 9, 10]),
442 ("\\this\\is\\a\\test\\dir", vec![1, 6, 9, 11, 16]),
443 ("\\\\\\\\\\ThisIsATestDir", vec![5, 9, 11, 12, 16]),
444 ("thisisatestdir", vec![0, 2, 6, 7, 11]),
445 ]
446 );
447 }
448
449 #[test]
450 fn test_lowercase_longer_than_uppercase() {
451 // This character has more chars in lower-case than in upper-case.
452 let paths = vec!["\u{0130}"];
453 let query = "\u{0130}";
454 assert_eq!(
455 match_single_path_query(query, false, &paths),
456 vec![("\u{0130}", vec![0])]
457 );
458
459 // Path is the lower-case version of the query
460 let paths = vec!["i\u{307}"];
461 let query = "\u{0130}";
462 assert_eq!(
463 match_single_path_query(query, false, &paths),
464 vec![("i\u{307}", vec![0])]
465 );
466 }
467
468 #[test]
469 fn test_match_multibyte_path_entries() {
470 let paths = vec![
471 "aαbβ/cγdδ",
472 "αβγδ/bcde",
473 "c1️⃣2️⃣3️⃣/d4️⃣5️⃣6️⃣/e7️⃣8️⃣9️⃣/f",
474 "/d/🆒/h",
475 ];
476 assert_eq!("1️⃣".len(), 7);
477 assert_eq!(
478 match_single_path_query("bcd", false, &paths),
479 vec![
480 ("αβγδ/bcde", vec![9, 10, 11]),
481 ("aαbβ/cγdδ", vec![3, 7, 10]),
482 ]
483 );
484 assert_eq!(
485 match_single_path_query("cde", false, &paths),
486 vec![
487 ("αβγδ/bcde", vec![10, 11, 12]),
488 ("c1️⃣2️⃣3️⃣/d4️⃣5️⃣6️⃣/e7️⃣8️⃣9️⃣/f", vec![0, 23, 46]),
489 ]
490 );
491 }
492
493 fn match_single_path_query<'a>(
494 query: &str,
495 smart_case: bool,
496 paths: &[&'a str],
497 ) -> Vec<(&'a str, Vec<usize>)> {
498 let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
499 let query = query.chars().collect::<Vec<_>>();
500 let query_chars = CharBag::from(&lowercase_query[..]);
501
502 let path_arcs: Vec<Arc<Path>> = paths
503 .iter()
504 .map(|path| Arc::from(PathBuf::from(path)))
505 .collect::<Vec<_>>();
506 let mut path_entries = Vec::new();
507 for (i, path) in paths.iter().enumerate() {
508 let lowercase_path = path.to_lowercase().chars().collect::<Vec<_>>();
509 let char_bag = CharBag::from(lowercase_path.as_slice());
510 path_entries.push(PathMatchCandidate {
511 is_dir: false,
512 char_bag,
513 path: &path_arcs[i],
514 });
515 }
516
517 let mut matcher = Matcher::new(&query, &lowercase_query, query_chars, smart_case);
518
519 let cancel_flag = AtomicBool::new(false);
520 let mut results = Vec::new();
521
522 matcher.match_candidates(
523 &[],
524 &[],
525 path_entries.into_iter(),
526 &mut results,
527 &cancel_flag,
528 |candidate, score, positions| PathMatch {
529 score,
530 worktree_id: 0,
531 positions: positions.clone(),
532 path: Arc::from(candidate.path),
533 path_prefix: "".into(),
534 distance_to_relative_ancestor: usize::MAX,
535 is_dir: false,
536 },
537 );
538 results.sort_by(|a, b| b.cmp(a));
539
540 results
541 .into_iter()
542 .map(|result| {
543 (
544 paths
545 .iter()
546 .copied()
547 .find(|p| result.path.as_ref() == Path::new(p))
548 .unwrap(),
549 result.positions,
550 )
551 })
552 .collect()
553 }
554}