1use gpui::BackgroundExecutor;
2use std::{
3 cmp::Ordering,
4 sync::{
5 Arc,
6 atomic::{self, AtomicBool},
7 },
8};
9use util::{paths::PathStyle, rel_path::RelPath};
10
11use nucleo::Utf32Str;
12use nucleo::pattern::{Atom, AtomKind, CaseMatching, Normalization};
13
14use fuzzy::CharBag;
15
16use crate::matcher::{self, LENGTH_PENALTY};
17use crate::{Cancelled, Case, positions_from_sorted};
18
19#[derive(Clone, Debug)]
20pub struct PathMatchCandidate<'a> {
21 pub is_dir: bool,
22 pub path: &'a RelPath,
23 pub char_bag: CharBag,
24}
25
26impl<'a> PathMatchCandidate<'a> {
27 /// Build a candidate whose prefilter bag covers both the worktree prefix and the path.
28 /// Pass `None` when matching against paths that have no worktree prefix.
29 pub fn new(path: &'a RelPath, is_dir: bool, path_prefix: Option<&RelPath>) -> Self {
30 let mut char_bag = CharBag::default();
31 if let Some(prefix) = path_prefix
32 && !prefix.is_empty()
33 {
34 char_bag.extend(prefix.as_unix_str().chars().map(|c| c.to_ascii_lowercase()));
35 }
36 char_bag.extend(path.as_unix_str().chars().map(|c| c.to_ascii_lowercase()));
37 Self {
38 is_dir,
39 path,
40 char_bag,
41 }
42 }
43}
44
45#[derive(Clone, Debug)]
46pub struct PathMatch {
47 pub score: f64,
48 pub positions: Vec<usize>,
49 pub worktree_id: usize,
50 pub path: Arc<RelPath>,
51 pub path_prefix: Arc<RelPath>,
52 pub is_dir: bool,
53 /// Number of steps removed from a shared parent with the relative path
54 /// Used to order closer paths first in the search list
55 pub distance_to_relative_ancestor: usize,
56}
57
58pub trait PathMatchCandidateSet<'a>: Send + Sync {
59 type Candidates: Iterator<Item = PathMatchCandidate<'a>>;
60 fn id(&self) -> usize;
61 fn len(&self) -> usize;
62 fn is_empty(&self) -> bool {
63 self.len() == 0
64 }
65 fn root_is_file(&self) -> bool;
66 fn prefix(&self) -> Arc<RelPath>;
67 fn candidates(&'a self, start: usize) -> Self::Candidates;
68 fn path_style(&self) -> PathStyle;
69}
70
71impl PartialEq for PathMatch {
72 fn eq(&self, other: &Self) -> bool {
73 self.cmp(other).is_eq()
74 }
75}
76
77impl Eq for PathMatch {}
78
79impl PartialOrd for PathMatch {
80 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
81 Some(self.cmp(other))
82 }
83}
84
85impl Ord for PathMatch {
86 fn cmp(&self, other: &Self) -> Ordering {
87 self.score
88 .total_cmp(&other.score)
89 .then_with(|| self.worktree_id.cmp(&other.worktree_id))
90 .then_with(|| {
91 other
92 .distance_to_relative_ancestor
93 .cmp(&self.distance_to_relative_ancestor)
94 })
95 .then_with(|| self.path.cmp(&other.path))
96 }
97}
98
99// Path matching is always case-insensitive at the nucleo level. `Case::Smart`
100// is honored as a *scoring hint*: when the query contains uppercase, candidates
101// whose matched characters disagree in case are downranked by a factor per
102// mismatch rather than dropped. This keeps `"Editor: Backspace"` matching
103// `"editor: backspace"` while still preferring exact-case hits.
104const SMART_CASE_PENALTY_PER_MISMATCH: f64 = 0.9;
105
106pub(crate) fn make_atoms(query: &str) -> Vec<Atom> {
107 query
108 .split_whitespace()
109 .map(|word| {
110 Atom::new(
111 word,
112 CaseMatching::Ignore,
113 Normalization::Smart,
114 AtomKind::Fuzzy,
115 false,
116 )
117 })
118 .collect()
119}
120
121// Only populated when we will actually charge a smart-case penalty, so the hot
122// path can iterate a plain `&[Atom]` and ignore this slice entirely.
123fn make_source_words(query: &str, case: Case) -> Option<Vec<Vec<char>>> {
124 (case.is_smart() && query.chars().any(|c| c.is_uppercase())).then(|| {
125 query
126 .split_whitespace()
127 .map(|word| word.chars().collect())
128 .collect()
129 })
130}
131
132fn case_penalty(mismatches: u32) -> f64 {
133 if mismatches == 0 {
134 1.0
135 } else {
136 SMART_CASE_PENALTY_PER_MISMATCH.powi(mismatches as i32)
137 }
138}
139
140pub(crate) fn distance_between_paths(path: &RelPath, relative_to: &RelPath) -> usize {
141 let mut path_components = path.components();
142 let mut relative_components = relative_to.components();
143
144 while path_components
145 .next()
146 .zip(relative_components.next())
147 .map(|(path_component, relative_component)| path_component == relative_component)
148 .unwrap_or_default()
149 {}
150 path_components.count() + relative_components.count() + 1
151}
152
153fn get_filename_match_bonus(
154 candidate_buf: &str,
155 query_atoms: &[Atom],
156 matcher: &mut nucleo::Matcher,
157) -> f64 {
158 let filename = match std::path::Path::new(candidate_buf).file_name() {
159 Some(f) => f.to_str().unwrap_or(""),
160 None => return 0.0,
161 };
162 if filename.is_empty() || query_atoms.is_empty() {
163 return 0.0;
164 }
165 let mut buf = Vec::new();
166 let haystack = Utf32Str::new(filename, &mut buf);
167 let mut total_score = 0u32;
168 for atom in query_atoms {
169 if let Some(score) = atom.score(haystack, matcher) {
170 total_score = total_score.saturating_add(score as u32);
171 }
172 }
173 total_score as f64 / filename.len().max(1) as f64
174}
175
176fn path_match_helper<'a>(
177 matcher: &mut nucleo::Matcher,
178 atoms: &[Atom],
179 source_words: Option<&[Vec<char>]>,
180 query_bag: CharBag,
181 candidates: impl Iterator<Item = PathMatchCandidate<'a>>,
182 results: &mut Vec<PathMatch>,
183 worktree_id: usize,
184 path_prefix: &Arc<RelPath>,
185 root_is_file: bool,
186 relative_to: &Option<Arc<RelPath>>,
187 path_style: PathStyle,
188 cancel_flag: &AtomicBool,
189) -> Result<(), Cancelled> {
190 let mut candidate_buf = if !path_prefix.is_empty() && !root_is_file {
191 let mut s = path_prefix.display(path_style).to_string();
192 s.push_str(path_style.primary_separator());
193 s
194 } else {
195 String::new()
196 };
197 let path_prefix_len = candidate_buf.len();
198 let mut buf = Vec::new();
199 let mut matched_chars: Vec<u32> = Vec::new();
200 let mut atom_matched_chars = Vec::new();
201 let mut candidate_chars: Vec<char> = Vec::new();
202 for candidate in candidates {
203 buf.clear();
204 matched_chars.clear();
205 if cancel_flag.load(atomic::Ordering::Relaxed) {
206 return Err(Cancelled);
207 }
208
209 if !candidate.char_bag.is_superset(query_bag) {
210 continue;
211 }
212
213 candidate_buf.truncate(path_prefix_len);
214 if root_is_file {
215 candidate_buf.push_str(path_prefix.as_unix_str());
216 } else {
217 candidate_buf.push_str(candidate.path.as_unix_str());
218 }
219
220 let haystack = Utf32Str::new(&candidate_buf, &mut buf);
221
222 if source_words.is_some() {
223 candidate_chars.clear();
224 candidate_chars.extend(candidate_buf.chars());
225 }
226
227 let mut total_score: u32 = 0;
228 let mut case_mismatches: u32 = 0;
229 let mut all_matched = true;
230
231 for (atom_idx, atom) in atoms.iter().enumerate() {
232 atom_matched_chars.clear();
233 let Some(score) = atom.indices(haystack, matcher, &mut atom_matched_chars) else {
234 all_matched = false;
235 break;
236 };
237 total_score = total_score.saturating_add(score as u32);
238 if let Some(source_words) = source_words {
239 let query_chars = &source_words[atom_idx];
240 if query_chars.len() == atom_matched_chars.len() {
241 for (&query_char, &pos) in query_chars.iter().zip(&atom_matched_chars) {
242 if let Some(&candidate_char) = candidate_chars.get(pos as usize)
243 && candidate_char != query_char
244 && candidate_char.eq_ignore_ascii_case(&query_char)
245 {
246 case_mismatches += 1;
247 }
248 }
249 }
250 }
251 matched_chars.extend_from_slice(&atom_matched_chars);
252 }
253
254 if all_matched && !atoms.is_empty() {
255 matched_chars.sort_unstable();
256 matched_chars.dedup();
257
258 let length_penalty = candidate_buf.len() as f64 * LENGTH_PENALTY;
259 let filename_bonus = get_filename_match_bonus(&candidate_buf, atoms, matcher);
260 let positive = (total_score as f64 + filename_bonus) * case_penalty(case_mismatches);
261 let adjusted_score = positive - length_penalty;
262 let positions = positions_from_sorted(&candidate_buf, &matched_chars);
263
264 results.push(PathMatch {
265 score: adjusted_score,
266 positions,
267 worktree_id,
268 path: if root_is_file {
269 Arc::clone(path_prefix)
270 } else {
271 candidate.path.into()
272 },
273 path_prefix: if root_is_file {
274 RelPath::empty().into()
275 } else {
276 Arc::clone(path_prefix)
277 },
278 is_dir: candidate.is_dir,
279 distance_to_relative_ancestor: relative_to
280 .as_ref()
281 .map_or(usize::MAX, |relative_to| {
282 distance_between_paths(candidate.path, relative_to.as_ref())
283 }),
284 });
285 }
286 }
287 Ok(())
288}
289
290pub fn match_fixed_path_set(
291 candidates: Vec<PathMatchCandidate>,
292 worktree_id: usize,
293 worktree_root_name: Option<Arc<RelPath>>,
294 query: &str,
295 case: Case,
296 max_results: usize,
297 path_style: PathStyle,
298) -> Vec<PathMatch> {
299 let mut config = nucleo::Config::DEFAULT;
300 config.set_match_paths();
301 let mut matcher = matcher::get_matcher(config);
302
303 let atoms = make_atoms(query);
304 let source_words = make_source_words(query, case);
305 let query_bag = CharBag::from(query);
306
307 let root_is_file = worktree_root_name.is_some() && candidates.iter().all(|c| c.path.is_empty());
308
309 let path_prefix = worktree_root_name.unwrap_or_else(|| RelPath::empty().into());
310
311 let mut results = Vec::new();
312
313 path_match_helper(
314 &mut matcher,
315 &atoms,
316 source_words.as_deref(),
317 query_bag,
318 candidates.into_iter(),
319 &mut results,
320 worktree_id,
321 &path_prefix,
322 root_is_file,
323 &None,
324 path_style,
325 &AtomicBool::new(false),
326 )
327 .ok();
328 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
329 matcher::return_matcher(matcher);
330 results
331}
332
333pub async fn match_path_sets<'a, Set: PathMatchCandidateSet<'a>>(
334 candidate_sets: &'a [Set],
335 query: &str,
336 relative_to: &Option<Arc<RelPath>>,
337 case: Case,
338 max_results: usize,
339 cancel_flag: &AtomicBool,
340 executor: BackgroundExecutor,
341) -> Vec<PathMatch> {
342 let path_count: usize = candidate_sets.iter().map(|s| s.len()).sum();
343 if path_count == 0 {
344 return Vec::new();
345 }
346
347 let path_style = candidate_sets[0].path_style();
348
349 let query = if path_style.is_windows() {
350 query.replace('\\', "/")
351 } else {
352 query.to_owned()
353 };
354
355 let atoms = make_atoms(&query);
356 let source_words = make_source_words(&query, case);
357 let query_bag = CharBag::from(query.as_str());
358
359 let num_cpus = executor.num_cpus().min(path_count);
360 let segment_size = path_count.div_ceil(num_cpus);
361 let mut segment_results = (0..num_cpus)
362 .map(|_| Vec::with_capacity(max_results))
363 .collect::<Vec<_>>();
364 let mut config = nucleo::Config::DEFAULT;
365 config.set_match_paths();
366 let mut matchers = matcher::get_matchers(num_cpus, config);
367 executor
368 .scoped(|scope| {
369 for (segment_idx, (results, matcher)) in segment_results
370 .iter_mut()
371 .zip(matchers.iter_mut())
372 .enumerate()
373 {
374 let atoms = atoms.clone();
375 let source_words = source_words.clone();
376 let relative_to = relative_to.clone();
377 scope.spawn(async move {
378 let segment_start = segment_idx * segment_size;
379 let segment_end = segment_start + segment_size;
380
381 let mut tree_start = 0;
382 for candidate_set in candidate_sets {
383 let tree_end = tree_start + candidate_set.len();
384
385 if tree_start < segment_end && segment_start < tree_end {
386 let start = tree_start.max(segment_start) - tree_start;
387 let end = tree_end.min(segment_end) - tree_start;
388 let candidates = candidate_set.candidates(start).take(end - start);
389
390 if path_match_helper(
391 matcher,
392 &atoms,
393 source_words.as_deref(),
394 query_bag,
395 candidates,
396 results,
397 candidate_set.id(),
398 &candidate_set.prefix(),
399 candidate_set.root_is_file(),
400 &relative_to,
401 path_style,
402 cancel_flag,
403 )
404 .is_err()
405 {
406 break;
407 }
408 }
409
410 if tree_end >= segment_end {
411 break;
412 }
413 tree_start = tree_end;
414 }
415 });
416 }
417 })
418 .await;
419
420 matcher::return_matchers(matchers);
421 if cancel_flag.load(atomic::Ordering::Acquire) {
422 return Vec::new();
423 }
424
425 let mut results = segment_results.concat();
426 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
427 results
428}