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