1use gpui::BackgroundExecutor;
2use std::{
3 borrow::Cow,
4 cmp::{self, Ordering},
5 path::Path,
6 sync::{
7 Arc,
8 atomic::{self, AtomicBool},
9 },
10};
11
12use crate::{
13 CharBag,
14 matcher::{MatchCandidate, Matcher},
15};
16
17#[derive(Clone, Debug)]
18pub struct PathMatchCandidate<'a> {
19 pub is_dir: bool,
20 pub path: &'a Path,
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<Path>,
30 pub path_prefix: Arc<str>,
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 prefix(&self) -> Arc<str>;
45 fn candidates(&'a self, start: usize) -> Self::Candidates;
46}
47
48impl<'a> MatchCandidate for PathMatchCandidate<'a> {
49 fn has_chars(&self, bag: CharBag) -> bool {
50 self.char_bag.is_superset(bag)
51 }
52
53 fn to_string(&self) -> Cow<'a, str> {
54 self.path.to_string_lossy()
55 }
56}
57
58impl PartialEq for PathMatch {
59 fn eq(&self, other: &Self) -> bool {
60 self.cmp(other).is_eq()
61 }
62}
63
64impl Eq for PathMatch {}
65
66impl PartialOrd for PathMatch {
67 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
68 Some(self.cmp(other))
69 }
70}
71
72impl Ord for PathMatch {
73 fn cmp(&self, other: &Self) -> Ordering {
74 self.score
75 .partial_cmp(&other.score)
76 .unwrap_or(Ordering::Equal)
77 .then_with(|| self.worktree_id.cmp(&other.worktree_id))
78 .then_with(|| {
79 other
80 .distance_to_relative_ancestor
81 .cmp(&self.distance_to_relative_ancestor)
82 })
83 .then_with(|| self.path.cmp(&other.path))
84 }
85}
86
87pub fn match_fixed_path_set(
88 candidates: Vec<PathMatchCandidate>,
89 worktree_id: usize,
90 query: &str,
91 smart_case: bool,
92 max_results: usize,
93) -> Vec<PathMatch> {
94 let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
95 let query = query.chars().collect::<Vec<_>>();
96 let query_char_bag = CharBag::from(&lowercase_query[..]);
97
98 let mut matcher = Matcher::new(&query, &lowercase_query, query_char_bag, smart_case, true);
99
100 let mut results = Vec::new();
101 matcher.match_candidates(
102 &[],
103 &[],
104 candidates.into_iter(),
105 &mut results,
106 &AtomicBool::new(false),
107 |candidate, score, positions| PathMatch {
108 score,
109 worktree_id,
110 positions: positions.clone(),
111 is_dir: candidate.is_dir,
112 path: Arc::from(candidate.path),
113 path_prefix: Arc::default(),
114 distance_to_relative_ancestor: usize::MAX,
115 },
116 );
117 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
118 results
119}
120
121pub async fn match_path_sets<'a, Set: PathMatchCandidateSet<'a>>(
122 candidate_sets: &'a [Set],
123 query: &str,
124 relative_to: Option<Arc<Path>>,
125 smart_case: bool,
126 max_results: usize,
127 cancel_flag: &AtomicBool,
128 executor: BackgroundExecutor,
129) -> Vec<PathMatch> {
130 let path_count: usize = candidate_sets.iter().map(|s| s.len()).sum();
131 if path_count == 0 {
132 return Vec::new();
133 }
134
135 let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
136 let query = query.chars().collect::<Vec<_>>();
137
138 let lowercase_query = &lowercase_query;
139 let query = &query;
140 let query_char_bag = CharBag::from(&lowercase_query[..]);
141
142 let num_cpus = executor.num_cpus().min(path_count);
143 let segment_size = path_count.div_ceil(num_cpus);
144 let mut segment_results = (0..num_cpus)
145 .map(|_| Vec::with_capacity(max_results))
146 .collect::<Vec<_>>();
147
148 executor
149 .scoped(|scope| {
150 for (segment_idx, results) in segment_results.iter_mut().enumerate() {
151 let relative_to = relative_to.clone();
152 scope.spawn(async move {
153 let segment_start = segment_idx * segment_size;
154 let segment_end = segment_start + segment_size;
155 let mut matcher =
156 Matcher::new(query, lowercase_query, query_char_bag, smart_case, true);
157
158 let mut tree_start = 0;
159 for candidate_set in candidate_sets {
160 if cancel_flag.load(atomic::Ordering::Relaxed) {
161 break;
162 }
163
164 let tree_end = tree_start + candidate_set.len();
165
166 if tree_start < segment_end && segment_start < tree_end {
167 let start = cmp::max(tree_start, segment_start) - tree_start;
168 let end = cmp::min(tree_end, segment_end) - tree_start;
169 let candidates = candidate_set.candidates(start).take(end - start);
170
171 let worktree_id = candidate_set.id();
172 let prefix = candidate_set.prefix().chars().collect::<Vec<_>>();
173 let lowercase_prefix = prefix
174 .iter()
175 .map(|c| c.to_ascii_lowercase())
176 .collect::<Vec<_>>();
177 matcher.match_candidates(
178 &prefix,
179 &lowercase_prefix,
180 candidates,
181 results,
182 cancel_flag,
183 |candidate, score, positions| PathMatch {
184 score,
185 worktree_id,
186 positions: positions.clone(),
187 path: Arc::from(candidate.path),
188 is_dir: candidate.is_dir,
189 path_prefix: candidate_set.prefix(),
190 distance_to_relative_ancestor: relative_to.as_ref().map_or(
191 usize::MAX,
192 |relative_to| {
193 distance_between_paths(
194 candidate.path,
195 relative_to.as_ref(),
196 )
197 },
198 ),
199 },
200 );
201 }
202 if tree_end >= segment_end {
203 break;
204 }
205 tree_start = tree_end;
206 }
207 })
208 }
209 })
210 .await;
211
212 if cancel_flag.load(atomic::Ordering::Relaxed) {
213 return Vec::new();
214 }
215
216 let mut results = segment_results.concat();
217 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
218 results
219}
220
221/// Compute the distance from a given path to some other path
222/// If there is no shared path, returns usize::MAX
223fn distance_between_paths(path: &Path, relative_to: &Path) -> usize {
224 let mut path_components = path.components();
225 let mut relative_components = relative_to.components();
226
227 while path_components
228 .next()
229 .zip(relative_components.next())
230 .map(|(path_component, relative_component)| path_component == relative_component)
231 .unwrap_or_default()
232 {}
233 path_components.count() + relative_components.count() + 1
234}
235
236#[cfg(test)]
237mod tests {
238 use std::path::Path;
239
240 use super::distance_between_paths;
241
242 #[test]
243 fn test_distance_between_paths_empty() {
244 distance_between_paths(Path::new(""), Path::new(""));
245 }
246}