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