1use gpui::BackgroundExecutor;
2use std::{
3 cmp::{self, Ordering},
4 sync::{
5 Arc,
6 atomic::{self, AtomicBool},
7 },
8};
9use util::{paths::PathStyle, rel_path::RelPath};
10
11use crate::{
12 CharBag,
13 char_bag::simple_lowercase,
14 matcher::{MatchCandidate, Matcher},
15};
16
17#[derive(Clone, Debug)]
18pub struct PathMatchCandidate<'a> {
19 pub is_dir: bool,
20 pub path: &'a RelPath,
21 pub char_bag: CharBag,
22}
23
24#[derive(Clone, Debug)]
25pub struct PathMatch {
26 pub score: f64,
27 pub positions: Vec<usize>,
28 pub worktree_id: usize,
29 pub path: Arc<RelPath>,
30 pub path_prefix: Arc<RelPath>,
31 pub is_dir: bool,
32 /// Number of steps removed from a shared parent with the relative path
33 /// Used to order closer paths first in the search list
34 pub distance_to_relative_ancestor: usize,
35}
36
37pub trait PathMatchCandidateSet<'a>: Send + Sync {
38 type Candidates: Iterator<Item = PathMatchCandidate<'a>>;
39 fn id(&self) -> usize;
40 fn len(&self) -> usize;
41 fn is_empty(&self) -> bool {
42 self.len() == 0
43 }
44 fn root_is_file(&self) -> bool;
45 fn prefix(&self) -> Arc<RelPath>;
46 fn candidates(&'a self, start: usize) -> Self::Candidates;
47 fn path_style(&self) -> PathStyle;
48}
49
50impl<'a> MatchCandidate for PathMatchCandidate<'a> {
51 fn has_chars(&self, bag: CharBag) -> bool {
52 self.char_bag.is_superset(bag)
53 }
54
55 fn candidate_chars(&self) -> impl Iterator<Item = char> {
56 self.path.as_unix_str().chars()
57 }
58}
59
60impl PartialEq for PathMatch {
61 fn eq(&self, other: &Self) -> bool {
62 self.cmp(other).is_eq()
63 }
64}
65
66impl Eq for PathMatch {}
67
68impl PartialOrd for PathMatch {
69 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
70 Some(self.cmp(other))
71 }
72}
73
74impl Ord for PathMatch {
75 fn cmp(&self, other: &Self) -> Ordering {
76 self.score
77 .partial_cmp(&other.score)
78 .unwrap_or(Ordering::Equal)
79 .then_with(|| self.worktree_id.cmp(&other.worktree_id))
80 .then_with(|| {
81 other
82 .distance_to_relative_ancestor
83 .cmp(&self.distance_to_relative_ancestor)
84 })
85 .then_with(|| self.path.cmp(&other.path))
86 }
87}
88
89pub fn match_fixed_path_set(
90 candidates: Vec<PathMatchCandidate>,
91 worktree_id: usize,
92 worktree_root_name: Option<Arc<RelPath>>,
93 query: &str,
94 smart_case: bool,
95 max_results: usize,
96 path_style: PathStyle,
97) -> Vec<PathMatch> {
98 let lowercase_query = query.chars().map(simple_lowercase).collect::<Vec<_>>();
99 let query = query.chars().collect::<Vec<_>>();
100 let query_char_bag = CharBag::from(&lowercase_query[..]);
101
102 let mut matcher = Matcher::new(&query, &lowercase_query, query_char_bag, smart_case, true);
103
104 let mut results = Vec::with_capacity(candidates.len());
105 let (path_prefix, path_prefix_chars, lowercase_prefix) = match worktree_root_name {
106 Some(worktree_root_name) => {
107 let mut path_prefix_chars = worktree_root_name
108 .display(path_style)
109 .chars()
110 .collect::<Vec<_>>();
111 path_prefix_chars.extend(path_style.primary_separator().chars());
112 let lowercase_pfx = path_prefix_chars
113 .iter()
114 .map(|c| simple_lowercase(*c))
115 .collect::<Vec<_>>();
116
117 (worktree_root_name, path_prefix_chars, lowercase_pfx)
118 }
119 None => (
120 RelPath::empty().into(),
121 Default::default(),
122 Default::default(),
123 ),
124 };
125
126 matcher.match_candidates(
127 &path_prefix_chars,
128 &lowercase_prefix,
129 candidates.into_iter(),
130 &mut results,
131 &AtomicBool::new(false),
132 |candidate, score, positions| PathMatch {
133 score,
134 worktree_id,
135 positions: positions.clone(),
136 is_dir: candidate.is_dir,
137 path: candidate.path.into(),
138 path_prefix: path_prefix.clone(),
139 distance_to_relative_ancestor: usize::MAX,
140 },
141 );
142 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
143 results
144}
145
146pub async fn match_path_sets<'a, Set: PathMatchCandidateSet<'a>>(
147 candidate_sets: &'a [Set],
148 query: &str,
149 relative_to: &Option<Arc<RelPath>>,
150 smart_case: bool,
151 max_results: usize,
152 cancel_flag: &AtomicBool,
153 executor: BackgroundExecutor,
154) -> Vec<PathMatch> {
155 let path_count: usize = candidate_sets.iter().map(|s| s.len()).sum();
156 if path_count == 0 {
157 return Vec::new();
158 }
159
160 let path_style = candidate_sets[0].path_style();
161
162 let query = query
163 .chars()
164 .map(|char| {
165 if path_style.is_windows() && char == '\\' {
166 '/'
167 } else {
168 char
169 }
170 })
171 .collect::<Vec<_>>();
172
173 let lowercase_query = query
174 .iter()
175 .map(|query| simple_lowercase(*query))
176 .collect::<Vec<_>>();
177
178 let query = &query;
179 let lowercase_query = &lowercase_query;
180 let query_char_bag = CharBag::from_iter(lowercase_query.iter().copied());
181
182 let num_cpus = executor.num_cpus().min(path_count);
183 let segment_size = path_count.div_ceil(num_cpus);
184 let mut segment_results = (0..num_cpus)
185 .map(|_| Vec::with_capacity(max_results))
186 .collect::<Vec<_>>();
187
188 executor
189 .scoped(|scope| {
190 for (segment_idx, results) in segment_results.iter_mut().enumerate() {
191 scope.spawn(async move {
192 let segment_start = segment_idx * segment_size;
193 let segment_end = segment_start + segment_size;
194 let mut matcher =
195 Matcher::new(query, lowercase_query, query_char_bag, smart_case, true);
196
197 let mut tree_start = 0;
198 for candidate_set in candidate_sets {
199 if cancel_flag.load(atomic::Ordering::Acquire) {
200 break;
201 }
202
203 let tree_end = tree_start + candidate_set.len();
204
205 if tree_start < segment_end && segment_start < tree_end {
206 let start = cmp::max(tree_start, segment_start) - tree_start;
207 let end = cmp::min(tree_end, segment_end) - tree_start;
208 let candidates = candidate_set.candidates(start).take(end - start);
209
210 let worktree_id = candidate_set.id();
211 let mut prefix = candidate_set
212 .prefix()
213 .as_unix_str()
214 .chars()
215 .collect::<Vec<_>>();
216 if !candidate_set.root_is_file() && !prefix.is_empty() {
217 prefix.push('/');
218 }
219 let lowercase_prefix = prefix
220 .iter()
221 .map(|c| simple_lowercase(*c))
222 .collect::<Vec<_>>();
223 matcher.match_candidates(
224 &prefix,
225 &lowercase_prefix,
226 candidates,
227 results,
228 cancel_flag,
229 |candidate, score, positions| PathMatch {
230 score,
231 worktree_id,
232 positions: positions.clone(),
233 path: Arc::from(candidate.path),
234 is_dir: candidate.is_dir,
235 path_prefix: candidate_set.prefix(),
236 distance_to_relative_ancestor: relative_to.as_ref().map_or(
237 usize::MAX,
238 |relative_to| {
239 distance_between_paths(
240 candidate.path,
241 relative_to.as_ref(),
242 )
243 },
244 ),
245 },
246 );
247 }
248 if tree_end >= segment_end {
249 break;
250 }
251 tree_start = tree_end;
252 }
253 })
254 }
255 })
256 .await;
257
258 if cancel_flag.load(atomic::Ordering::Acquire) {
259 return Vec::new();
260 }
261
262 let mut results = segment_results.concat();
263 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
264 results
265}
266
267/// Compute the distance from a given path to some other path
268/// If there is no shared path, returns usize::MAX
269fn distance_between_paths(path: &RelPath, relative_to: &RelPath) -> usize {
270 let mut path_components = path.components();
271 let mut relative_components = relative_to.components();
272
273 while path_components
274 .next()
275 .zip(relative_components.next())
276 .map(|(path_component, relative_component)| path_component == relative_component)
277 .unwrap_or_default()
278 {}
279 path_components.count() + relative_components.count() + 1
280}
281
282#[cfg(test)]
283mod tests {
284 use util::rel_path::RelPath;
285
286 use super::distance_between_paths;
287
288 #[test]
289 fn test_distance_between_paths_empty() {
290 distance_between_paths(RelPath::empty(), RelPath::empty());
291 }
292}