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::Pattern;
13
14use fuzzy::CharBag;
15
16use crate::matcher::{self, LENGTH_PENALTY};
17use crate::{Cancelled, Case, Query, case_penalty, count_case_mismatches, 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
99pub(crate) fn distance_between_paths(path: &RelPath, relative_to: &RelPath) -> usize {
100 let mut path_components = path.components();
101 let mut relative_components = relative_to.components();
102
103 while path_components
104 .next()
105 .zip(relative_components.next())
106 .map(|(path_component, relative_component)| path_component == relative_component)
107 .unwrap_or_default()
108 {}
109 path_components.count() + relative_components.count() + 1
110}
111
112#[inline]
113fn get_filename_match_bonus(
114 candidate_buf: &str,
115 pattern: &Pattern,
116 matcher: &mut nucleo::Matcher,
117) -> f64 {
118 let Some(filename) = std::path::Path::new(candidate_buf)
119 .file_name()
120 .and_then(|f| f.to_str())
121 .filter(|f| !f.is_empty())
122 else {
123 return 0.0;
124 };
125 let mut buf = Vec::new();
126 let haystack = Utf32Str::new(filename, &mut buf);
127 let score: u32 = pattern
128 .atoms
129 .iter()
130 .filter_map(|atom| atom.score(haystack, matcher))
131 .map(|s| s as u32)
132 .sum();
133
134 score as f64 / filename.len().max(1) as f64
135}
136
137fn path_match_helper<'a>(
138 matcher: &mut nucleo::Matcher,
139 query: &Query,
140 candidates: impl Iterator<Item = PathMatchCandidate<'a>>,
141 results: &mut Vec<PathMatch>,
142 worktree_id: usize,
143 path_prefix: &Arc<RelPath>,
144 root_is_file: bool,
145 relative_to: &Option<Arc<RelPath>>,
146 path_style: PathStyle,
147 cancel_flag: &AtomicBool,
148) -> Result<(), Cancelled> {
149 let mut candidate_buf = if !path_prefix.is_empty() && !root_is_file {
150 let mut s = path_prefix.display(path_style).to_string();
151 s.push_str(path_style.primary_separator());
152 s
153 } else {
154 String::new()
155 };
156 let path_prefix_len = candidate_buf.len();
157 let mut buf = Vec::new();
158 let mut matched_chars: Vec<u32> = Vec::new();
159 let mut candidate_chars: Vec<char> = Vec::new();
160 for candidate in candidates {
161 buf.clear();
162 matched_chars.clear();
163 if cancel_flag.load(atomic::Ordering::Relaxed) {
164 return Err(Cancelled);
165 }
166
167 if !candidate.char_bag.is_superset(query.char_bag) {
168 continue;
169 }
170
171 candidate_buf.truncate(path_prefix_len);
172 if root_is_file {
173 candidate_buf.push_str(path_prefix.as_unix_str());
174 } else {
175 candidate_buf.push_str(candidate.path.as_unix_str());
176 }
177
178 let haystack = Utf32Str::new(&candidate_buf, &mut buf);
179
180 let Some(score) = query.pattern.indices(haystack, matcher, &mut matched_chars) else {
181 continue;
182 };
183
184 let case_mismatches = count_case_mismatches(
185 query.query_chars.as_deref(),
186 &matched_chars,
187 &candidate_buf,
188 &mut candidate_chars,
189 );
190
191 matched_chars.sort_unstable();
192 matched_chars.dedup();
193
194 let length_penalty = candidate_buf.len() as f64 * LENGTH_PENALTY;
195 let filename_bonus = get_filename_match_bonus(&candidate_buf, &query.pattern, matcher);
196 let positive = (score as f64 + filename_bonus) * case_penalty(case_mismatches);
197 let adjusted_score = positive - length_penalty;
198 let positions = positions_from_sorted(&candidate_buf, &matched_chars);
199
200 results.push(PathMatch {
201 score: adjusted_score,
202 positions,
203 worktree_id,
204 path: if root_is_file {
205 Arc::clone(path_prefix)
206 } else {
207 candidate.path.into()
208 },
209 path_prefix: if root_is_file {
210 RelPath::empty().into()
211 } else {
212 Arc::clone(path_prefix)
213 },
214 is_dir: candidate.is_dir,
215 distance_to_relative_ancestor: relative_to.as_ref().map_or(usize::MAX, |relative_to| {
216 distance_between_paths(candidate.path, relative_to.as_ref())
217 }),
218 });
219 }
220 Ok(())
221}
222
223pub fn match_fixed_path_set(
224 candidates: Vec<PathMatchCandidate>,
225 worktree_id: usize,
226 worktree_root_name: Option<Arc<RelPath>>,
227 query: &str,
228 case: Case,
229 max_results: usize,
230 path_style: PathStyle,
231) -> Vec<PathMatch> {
232 let Some(query) = Query::build(query, case) else {
233 return Vec::new();
234 };
235
236 let mut config = nucleo::Config::DEFAULT;
237 config.set_match_paths();
238 let mut matcher = matcher::get_matcher(config);
239
240 let root_is_file = worktree_root_name.is_some() && candidates.iter().all(|c| c.path.is_empty());
241
242 let path_prefix = worktree_root_name.unwrap_or_else(|| RelPath::empty().into());
243
244 let mut results = Vec::new();
245
246 path_match_helper(
247 &mut matcher,
248 &query,
249 candidates.into_iter(),
250 &mut results,
251 worktree_id,
252 &path_prefix,
253 root_is_file,
254 &None,
255 path_style,
256 &AtomicBool::new(false),
257 )
258 .ok();
259 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
260 matcher::return_matcher(matcher);
261 results
262}
263
264pub async fn match_path_sets<'a, Set: PathMatchCandidateSet<'a>>(
265 candidate_sets: &'a [Set],
266 query: &str,
267 relative_to: &Option<Arc<RelPath>>,
268 case: Case,
269 max_results: usize,
270 cancel_flag: &AtomicBool,
271 executor: BackgroundExecutor,
272) -> Vec<PathMatch> {
273 let path_count: usize = candidate_sets.iter().map(|s| s.len()).sum();
274 if path_count == 0 {
275 return Vec::new();
276 }
277
278 let path_style = candidate_sets[0].path_style();
279
280 let query = if path_style.is_windows() {
281 query.replace('\\', "/")
282 } else {
283 query.to_owned()
284 };
285
286 let Some(query) = Query::build(&query, case) else {
287 return Vec::new();
288 };
289
290 let num_cpus = executor.num_cpus().min(path_count);
291 let segment_size = path_count.div_ceil(num_cpus);
292 let mut segment_results = (0..num_cpus)
293 .map(|_| Vec::with_capacity(max_results))
294 .collect::<Vec<_>>();
295 let mut config = nucleo::Config::DEFAULT;
296 config.set_match_paths();
297 let mut matchers = matcher::get_matchers(num_cpus, config);
298 executor
299 .scoped(|scope| {
300 for (segment_idx, (results, matcher)) in segment_results
301 .iter_mut()
302 .zip(matchers.iter_mut())
303 .enumerate()
304 {
305 let query = &query;
306 let relative_to = relative_to.clone();
307 scope.spawn(async move {
308 let segment_start = segment_idx * segment_size;
309 let segment_end = segment_start + segment_size;
310
311 let mut tree_start = 0;
312 for candidate_set in candidate_sets {
313 let tree_end = tree_start + candidate_set.len();
314
315 if tree_start < segment_end && segment_start < tree_end {
316 let start = tree_start.max(segment_start) - tree_start;
317 let end = tree_end.min(segment_end) - tree_start;
318 let candidates = candidate_set.candidates(start).take(end - start);
319
320 if path_match_helper(
321 matcher,
322 query,
323 candidates,
324 results,
325 candidate_set.id(),
326 &candidate_set.prefix(),
327 candidate_set.root_is_file(),
328 &relative_to,
329 path_style,
330 cancel_flag,
331 )
332 .is_err()
333 {
334 break;
335 }
336 }
337
338 if tree_end >= segment_end {
339 break;
340 }
341 tree_start = tree_end;
342 }
343 });
344 }
345 })
346 .await;
347
348 matcher::return_matchers(matchers);
349 if cancel_flag.load(atomic::Ordering::Acquire) {
350 return Vec::new();
351 }
352
353 let mut results = segment_results.concat();
354 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
355 results
356}