tenant.openagents/omega

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