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 crate::matcher::{self, LENGTH_PENALTY};
15
16#[derive(Clone, Debug)]
17pub struct PathMatchCandidate<'a> {
18 pub is_dir: bool,
19 pub path: &'a RelPath,
20}
21
22#[derive(Clone, Debug)]
23pub struct PathMatch {
24 pub score: f64,
25 pub positions: Vec<usize>,
26 pub worktree_id: usize,
27 pub path: Arc<RelPath>,
28 pub path_prefix: Arc<RelPath>,
29 pub is_dir: bool,
30 /// Number of steps removed from a shared parent with the relative path
31 /// Used to order closer paths first in the search list
32 pub distance_to_relative_ancestor: usize,
33}
34
35pub trait PathMatchCandidateSet<'a>: Send + Sync {
36 type Candidates: Iterator<Item = PathMatchCandidate<'a>>;
37 fn id(&self) -> usize;
38 fn len(&self) -> usize;
39 fn is_empty(&self) -> bool {
40 self.len() == 0
41 }
42 fn root_is_file(&self) -> bool;
43 fn prefix(&self) -> Arc<RelPath>;
44 fn candidates(&'a self, start: usize) -> Self::Candidates;
45 fn path_style(&self) -> PathStyle;
46}
47
48impl PartialEq for PathMatch {
49 fn eq(&self, other: &Self) -> bool {
50 self.cmp(other).is_eq()
51 }
52}
53
54impl Eq for PathMatch {}
55
56impl PartialOrd for PathMatch {
57 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
58 Some(self.cmp(other))
59 }
60}
61
62impl Ord for PathMatch {
63 fn cmp(&self, other: &Self) -> Ordering {
64 self.score
65 .partial_cmp(&other.score)
66 .unwrap_or(Ordering::Equal)
67 .then_with(|| self.worktree_id.cmp(&other.worktree_id))
68 .then_with(|| {
69 other
70 .distance_to_relative_ancestor
71 .cmp(&self.distance_to_relative_ancestor)
72 })
73 .then_with(|| self.path.cmp(&other.path))
74 }
75}
76
77fn make_atoms(query: &str, smart_case: bool) -> Vec<Atom> {
78 let case = if smart_case {
79 CaseMatching::Smart
80 } else {
81 CaseMatching::Ignore
82 };
83 query
84 .split_whitespace()
85 .map(|word| Atom::new(word, case, Normalization::Smart, AtomKind::Fuzzy, false))
86 .collect()
87}
88
89pub(crate) fn distance_between_paths(path: &RelPath, relative_to: &RelPath) -> usize {
90 let mut path_components = path.components();
91 let mut relative_components = relative_to.components();
92
93 while path_components
94 .next()
95 .zip(relative_components.next())
96 .map(|(path_component, relative_component)| path_component == relative_component)
97 .unwrap_or_default()
98 {}
99 path_components.count() + relative_components.count() + 1
100}
101
102fn get_filename_match_bonus(
103 candidate_buf: &str,
104 query_atoms: &[Atom],
105 matcher: &mut nucleo::Matcher,
106) -> f64 {
107 let filename = match std::path::Path::new(candidate_buf).file_name() {
108 Some(f) => f.to_str().unwrap_or(""),
109 None => return 0.0,
110 };
111 if filename.is_empty() || query_atoms.is_empty() {
112 return 0.0;
113 }
114 let mut buf = Vec::new();
115 let haystack = Utf32Str::new(filename, &mut buf);
116 let mut total_score = 0u32;
117 for atom in query_atoms {
118 if let Some(score) = atom.score(haystack, matcher) {
119 total_score = total_score.saturating_add(score as u32);
120 }
121 }
122 total_score as f64 / filename.len().max(1) as f64
123}
124struct Cancelled;
125
126fn path_match_helper<'a>(
127 matcher: &mut nucleo::Matcher,
128 atoms: &[Atom],
129 candidates: impl Iterator<Item = PathMatchCandidate<'a>>,
130 results: &mut Vec<PathMatch>,
131 worktree_id: usize,
132 path_prefix: &Arc<RelPath>,
133 root_is_file: bool,
134 relative_to: &Option<Arc<RelPath>>,
135 path_style: PathStyle,
136 cancel_flag: &AtomicBool,
137) -> Result<(), Cancelled> {
138 let mut candidate_buf = if !path_prefix.is_empty() && !root_is_file {
139 let mut s = path_prefix.display(path_style).to_string();
140 s.push_str(path_style.primary_separator());
141 s
142 } else {
143 String::new()
144 };
145 let path_prefix_len = candidate_buf.len();
146 let mut buf = Vec::new();
147 let mut matched_chars: Vec<u32> = Vec::new();
148 let mut atom_matched_chars = Vec::new();
149 for candidate in candidates {
150 buf.clear();
151 matched_chars.clear();
152 if cancel_flag.load(atomic::Ordering::Relaxed) {
153 return Err(Cancelled);
154 }
155
156 candidate_buf.truncate(path_prefix_len);
157 if root_is_file {
158 candidate_buf.push_str(path_prefix.as_unix_str());
159 } else {
160 candidate_buf.push_str(candidate.path.as_unix_str());
161 }
162
163 let haystack = Utf32Str::new(&candidate_buf, &mut buf);
164
165 let mut total_score: u32 = 0;
166 let mut all_matched = true;
167
168 for atom in atoms {
169 atom_matched_chars.clear();
170 if let Some(score) = atom.indices(haystack, matcher, &mut atom_matched_chars) {
171 total_score = total_score.saturating_add(score as u32);
172 matched_chars.extend_from_slice(&atom_matched_chars);
173 } else {
174 all_matched = false;
175 break;
176 }
177 }
178
179 if all_matched && !atoms.is_empty() {
180 matched_chars.sort_unstable();
181 matched_chars.dedup();
182
183 let length_penalty = candidate_buf.len() as f64 * LENGTH_PENALTY;
184 let filename_bonus = get_filename_match_bonus(&candidate_buf, atoms, matcher);
185 let adjusted_score = total_score as f64 + filename_bonus - length_penalty;
186 let mut positions: Vec<usize> = candidate_buf
187 .char_indices()
188 .enumerate()
189 .filter_map(|(char_offset, (byte_offset, _))| {
190 matched_chars
191 .contains(&(char_offset as u32))
192 .then_some(byte_offset)
193 })
194 .collect();
195 positions.sort_unstable();
196
197 results.push(PathMatch {
198 score: adjusted_score,
199 positions,
200 worktree_id,
201 path: if root_is_file {
202 Arc::clone(path_prefix)
203 } else {
204 candidate.path.into()
205 },
206 path_prefix: if root_is_file {
207 RelPath::empty().into()
208 } else {
209 Arc::clone(path_prefix)
210 },
211 is_dir: candidate.is_dir,
212 distance_to_relative_ancestor: relative_to
213 .as_ref()
214 .map_or(usize::MAX, |relative_to| {
215 distance_between_paths(candidate.path, relative_to.as_ref())
216 }),
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 smart_case: bool,
229 max_results: usize,
230 path_style: PathStyle,
231) -> Vec<PathMatch> {
232 let mut config = nucleo::Config::DEFAULT;
233 config.set_match_paths();
234 let mut matcher = matcher::get_matcher(config);
235
236 let atoms = make_atoms(query, smart_case);
237
238 let root_is_file = worktree_root_name.is_some() && candidates.iter().all(|c| c.path.is_empty());
239
240 let path_prefix = worktree_root_name.unwrap_or_else(|| RelPath::empty().into());
241
242 let mut results = Vec::new();
243
244 path_match_helper(
245 &mut matcher,
246 &atoms,
247 candidates.into_iter(),
248 &mut results,
249 worktree_id,
250 &path_prefix,
251 root_is_file,
252 &None,
253 path_style,
254 &AtomicBool::new(false),
255 )
256 .ok();
257 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
258 matcher::return_matcher(matcher);
259 results
260}
261
262pub async fn match_path_sets<'a, Set: PathMatchCandidateSet<'a>>(
263 candidate_sets: &'a [Set],
264 query: &str,
265 relative_to: &Option<Arc<RelPath>>,
266 smart_case: bool,
267 max_results: usize,
268 cancel_flag: &AtomicBool,
269 executor: BackgroundExecutor,
270) -> Vec<PathMatch> {
271 let path_count: usize = candidate_sets.iter().map(|s| s.len()).sum();
272 if path_count == 0 {
273 return Vec::new();
274 }
275
276 let path_style = candidate_sets[0].path_style();
277
278 let query = if path_style.is_windows() {
279 query.replace('\\', "/")
280 } else {
281 query.to_owned()
282 };
283
284 let atoms = make_atoms(&query, smart_case);
285
286 let num_cpus = executor.num_cpus().min(path_count);
287 let segment_size = path_count.div_ceil(num_cpus);
288 let mut segment_results = (0..num_cpus)
289 .map(|_| Vec::with_capacity(max_results))
290 .collect::<Vec<_>>();
291 let mut config = nucleo::Config::DEFAULT;
292 config.set_match_paths();
293 let mut matchers = matcher::get_matchers(num_cpus, config);
294 executor
295 .scoped(|scope| {
296 for (segment_idx, (results, matcher)) in segment_results
297 .iter_mut()
298 .zip(matchers.iter_mut())
299 .enumerate()
300 {
301 let atoms = atoms.clone();
302 let relative_to = relative_to.clone();
303 scope.spawn(async move {
304 let segment_start = segment_idx * segment_size;
305 let segment_end = segment_start + segment_size;
306
307 let mut tree_start = 0;
308 for candidate_set in candidate_sets {
309 let tree_end = tree_start + candidate_set.len();
310
311 if tree_start < segment_end && segment_start < tree_end {
312 let start = tree_start.max(segment_start) - tree_start;
313 let end = tree_end.min(segment_end) - tree_start;
314 let candidates = candidate_set.candidates(start).take(end - start);
315
316 if path_match_helper(
317 matcher,
318 &atoms,
319 candidates,
320 results,
321 candidate_set.id(),
322 &candidate_set.prefix(),
323 candidate_set.root_is_file(),
324 &relative_to,
325 path_style,
326 cancel_flag,
327 )
328 .is_err()
329 {
330 break;
331 }
332 }
333
334 if tree_end >= segment_end {
335 break;
336 }
337 tree_start = tree_end;
338 }
339 });
340 }
341 })
342 .await;
343
344 matcher::return_matchers(matchers);
345 if cancel_flag.load(atomic::Ordering::Acquire) {
346 return Vec::new();
347 }
348
349 let mut results = segment_results.concat();
350 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
351 results
352}