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 Arc<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 async fn match_path_sets<'a, Set: PathMatchCandidateSet<'a>>(
94 candidate_sets: &'a [Set],
95 query: &str,
96 relative_to: Option<Arc<Path>>,
97 smart_case: bool,
98 max_results: usize,
99 cancel_flag: &AtomicBool,
100 background: Arc<executor::Background>,
101) -> Vec<PathMatch> {
102 let path_count: usize = candidate_sets.iter().map(|s| s.len()).sum();
103 if path_count == 0 {
104 return Vec::new();
105 }
106
107 let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
108 let query = query.chars().collect::<Vec<_>>();
109
110 let lowercase_query = &lowercase_query;
111 let query = &query;
112 let query_char_bag = CharBag::from(&lowercase_query[..]);
113
114 let num_cpus = background.num_cpus().min(path_count);
115 let segment_size = (path_count + num_cpus - 1) / num_cpus;
116 let mut segment_results = (0..num_cpus)
117 .map(|_| Vec::with_capacity(max_results))
118 .collect::<Vec<_>>();
119
120 background
121 .scoped(|scope| {
122 for (segment_idx, results) in segment_results.iter_mut().enumerate() {
123 let relative_to = relative_to.clone();
124 scope.spawn(async move {
125 let segment_start = segment_idx * segment_size;
126 let segment_end = segment_start + segment_size;
127 let mut matcher = Matcher::new(
128 query,
129 lowercase_query,
130 query_char_bag,
131 smart_case,
132 max_results,
133 );
134
135 let mut tree_start = 0;
136 for candidate_set in candidate_sets {
137 let tree_end = tree_start + candidate_set.len();
138
139 if tree_start < segment_end && segment_start < tree_end {
140 let start = cmp::max(tree_start, segment_start) - tree_start;
141 let end = cmp::min(tree_end, segment_end) - tree_start;
142 let candidates = candidate_set.candidates(start).take(end - start);
143
144 let worktree_id = candidate_set.id();
145 let prefix = candidate_set.prefix().chars().collect::<Vec<_>>();
146 let lowercase_prefix = prefix
147 .iter()
148 .map(|c| c.to_ascii_lowercase())
149 .collect::<Vec<_>>();
150 matcher.match_candidates(
151 &prefix,
152 &lowercase_prefix,
153 candidates,
154 results,
155 cancel_flag,
156 |candidate, score| PathMatch {
157 score,
158 worktree_id,
159 positions: Vec::new(),
160 path: candidate.path.clone(),
161 path_prefix: candidate_set.prefix(),
162 distance_to_relative_ancestor: distance_to_relative_ancestor(
163 candidate.path.as_ref(),
164 &relative_to,
165 ),
166 },
167 );
168 }
169 if tree_end >= segment_end {
170 break;
171 }
172 tree_start = tree_end;
173 }
174 })
175 }
176 })
177 .await;
178
179 let mut results = Vec::new();
180 for segment_result in segment_results {
181 if results.is_empty() {
182 results = segment_result;
183 } else {
184 util::extend_sorted(&mut results, segment_result, max_results, |a, b| b.cmp(a));
185 }
186 }
187 results
188}
189
190/// Compute the distance from a given path to some other path
191/// If there is no shared path, returns usize::MAX
192fn distance_to_relative_ancestor(path: &Path, relative_to: &Option<Arc<Path>>) -> usize {
193 let Some(relative_to) = relative_to else {
194 return usize::MAX;
195 };
196
197 for (path_ancestor_count, path_ancestor) in path.ancestors().enumerate() {
198 for (relative_ancestor_count, relative_ancestor) in relative_to.ancestors().enumerate() {
199 if path_ancestor == relative_ancestor {
200 return path_ancestor_count + relative_ancestor_count;
201 }
202 }
203 }
204
205 usize::MAX
206}