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