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