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_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 query: &str,
92 smart_case: bool,
93 max_results: usize,
94) -> Vec<PathMatch> {
95 let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
96 let query = query.chars().collect::<Vec<_>>();
97 let query_char_bag = CharBag::from(&lowercase_query[..]);
98
99 let mut matcher = Matcher::new(&query, &lowercase_query, query_char_bag, smart_case, true);
100
101 let mut results = Vec::new();
102 matcher.match_candidates(
103 &[],
104 &[],
105 candidates.into_iter(),
106 &mut results,
107 &AtomicBool::new(false),
108 |candidate, score, positions| PathMatch {
109 score,
110 worktree_id,
111 positions: positions.clone(),
112 is_dir: candidate.is_dir,
113 path: candidate.path.into(),
114 path_prefix: RelPath::empty().into(),
115 distance_to_relative_ancestor: usize::MAX,
116 },
117 );
118 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
119 results
120}
121
122pub async fn match_path_sets<'a, Set: PathMatchCandidateSet<'a>>(
123 candidate_sets: &'a [Set],
124 query: &str,
125 relative_to: &Option<Arc<RelPath>>,
126 smart_case: bool,
127 max_results: usize,
128 cancel_flag: &AtomicBool,
129 executor: BackgroundExecutor,
130) -> Vec<PathMatch> {
131 let path_count: usize = candidate_sets.iter().map(|s| s.len()).sum();
132 if path_count == 0 {
133 return Vec::new();
134 }
135
136 let path_style = candidate_sets[0].path_style();
137
138 let query = query
139 .chars()
140 .map(|char| {
141 if path_style.is_windows() && char == '\\' {
142 '/'
143 } else {
144 char
145 }
146 })
147 .collect::<Vec<_>>();
148
149 let lowercase_query = query
150 .iter()
151 .map(|query| query.to_ascii_lowercase())
152 .collect::<Vec<_>>();
153
154 let query = &query;
155 let lowercase_query = &lowercase_query;
156 let query_char_bag = CharBag::from_iter(lowercase_query.iter().copied());
157
158 let num_cpus = executor.num_cpus().min(path_count);
159 let segment_size = path_count.div_ceil(num_cpus);
160 let mut segment_results = (0..num_cpus)
161 .map(|_| Vec::with_capacity(max_results))
162 .collect::<Vec<_>>();
163
164 executor
165 .scoped(|scope| {
166 for (segment_idx, results) in segment_results.iter_mut().enumerate() {
167 scope.spawn(async move {
168 let segment_start = segment_idx * segment_size;
169 let segment_end = segment_start + segment_size;
170 let mut matcher =
171 Matcher::new(query, lowercase_query, query_char_bag, smart_case, true);
172
173 let mut tree_start = 0;
174 for candidate_set in candidate_sets {
175 if cancel_flag.load(atomic::Ordering::Acquire) {
176 break;
177 }
178
179 let tree_end = tree_start + candidate_set.len();
180
181 if tree_start < segment_end && segment_start < tree_end {
182 let start = cmp::max(tree_start, segment_start) - tree_start;
183 let end = cmp::min(tree_end, segment_end) - tree_start;
184 let candidates = candidate_set.candidates(start).take(end - start);
185
186 let worktree_id = candidate_set.id();
187 let mut prefix =
188 candidate_set.prefix().as_str().chars().collect::<Vec<_>>();
189 if !candidate_set.root_is_file() && !prefix.is_empty() {
190 prefix.push('/');
191 }
192 let lowercase_prefix = prefix
193 .iter()
194 .map(|c| c.to_ascii_lowercase())
195 .collect::<Vec<_>>();
196 matcher.match_candidates(
197 &prefix,
198 &lowercase_prefix,
199 candidates,
200 results,
201 cancel_flag,
202 |candidate, score, positions| PathMatch {
203 score,
204 worktree_id,
205 positions: positions.clone(),
206 path: Arc::from(candidate.path),
207 is_dir: candidate.is_dir,
208 path_prefix: candidate_set.prefix(),
209 distance_to_relative_ancestor: relative_to.as_ref().map_or(
210 usize::MAX,
211 |relative_to| {
212 distance_between_paths(
213 candidate.path,
214 relative_to.as_ref(),
215 )
216 },
217 ),
218 },
219 );
220 }
221 if tree_end >= segment_end {
222 break;
223 }
224 tree_start = tree_end;
225 }
226 })
227 }
228 })
229 .await;
230
231 if cancel_flag.load(atomic::Ordering::Acquire) {
232 return Vec::new();
233 }
234
235 let mut results = segment_results.concat();
236 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
237 results
238}
239
240/// Compute the distance from a given path to some other path
241/// If there is no shared path, returns usize::MAX
242fn distance_between_paths(path: &RelPath, relative_to: &RelPath) -> usize {
243 let mut path_components = path.components();
244 let mut relative_components = relative_to.components();
245
246 while path_components
247 .next()
248 .zip(relative_components.next())
249 .map(|(path_component, relative_component)| path_component == relative_component)
250 .unwrap_or_default()
251 {}
252 path_components.count() + relative_components.count() + 1
253}
254
255#[cfg(test)]
256mod tests {
257 use util::rel_path::RelPath;
258
259 use super::distance_between_paths;
260
261 #[test]
262 fn test_distance_between_paths_empty() {
263 distance_between_paths(RelPath::empty(), RelPath::empty());
264 }
265}