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}
 29
 30pub trait PathMatchCandidateSet<'a>: Send + Sync {
 31    type Candidates: Iterator<Item = PathMatchCandidate<'a>>;
 32    fn id(&self) -> usize;
 33    fn len(&self) -> usize;
 34    fn is_empty(&self) -> bool {
 35        self.len() == 0
 36    }
 37    fn prefix(&self) -> Arc<str>;
 38    fn candidates(&'a self, start: usize) -> Self::Candidates;
 39}
 40
 41impl Match for PathMatch {
 42    fn score(&self) -> f64 {
 43        self.score
 44    }
 45
 46    fn set_positions(&mut self, positions: Vec<usize>) {
 47        self.positions = positions;
 48    }
 49}
 50
 51impl<'a> MatchCandidate for PathMatchCandidate<'a> {
 52    fn has_chars(&self, bag: CharBag) -> bool {
 53        self.char_bag.is_superset(bag)
 54    }
 55
 56    fn to_string(&self) -> Cow<'a, str> {
 57        self.path.to_string_lossy()
 58    }
 59}
 60
 61impl PartialEq for PathMatch {
 62    fn eq(&self, other: &Self) -> bool {
 63        self.cmp(other).is_eq()
 64    }
 65}
 66
 67impl Eq for PathMatch {}
 68
 69impl PartialOrd for PathMatch {
 70    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 71        Some(self.cmp(other))
 72    }
 73}
 74
 75impl Ord for PathMatch {
 76    fn cmp(&self, other: &Self) -> Ordering {
 77        self.score
 78            .partial_cmp(&other.score)
 79            .unwrap_or(Ordering::Equal)
 80            .then_with(|| self.worktree_id.cmp(&other.worktree_id))
 81            .then_with(|| self.path.cmp(&other.path))
 82    }
 83}
 84
 85pub async fn match_path_sets<'a, Set: PathMatchCandidateSet<'a>>(
 86    candidate_sets: &'a [Set],
 87    query: &str,
 88    smart_case: bool,
 89    max_results: usize,
 90    cancel_flag: &AtomicBool,
 91    background: Arc<executor::Background>,
 92) -> Vec<PathMatch> {
 93    let path_count: usize = candidate_sets.iter().map(|s| s.len()).sum();
 94    if path_count == 0 {
 95        return Vec::new();
 96    }
 97
 98    let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
 99    let query = query.chars().collect::<Vec<_>>();
100
101    let lowercase_query = &lowercase_query;
102    let query = &query;
103    let query_char_bag = CharBag::from(&lowercase_query[..]);
104
105    let num_cpus = background.num_cpus().min(path_count);
106    let segment_size = (path_count + num_cpus - 1) / num_cpus;
107    let mut segment_results = (0..num_cpus)
108        .map(|_| Vec::with_capacity(max_results))
109        .collect::<Vec<_>>();
110
111    background
112        .scoped(|scope| {
113            for (segment_idx, results) in segment_results.iter_mut().enumerate() {
114                scope.spawn(async move {
115                    let segment_start = segment_idx * segment_size;
116                    let segment_end = segment_start + segment_size;
117                    let mut matcher = Matcher::new(
118                        query,
119                        lowercase_query,
120                        query_char_bag,
121                        smart_case,
122                        max_results,
123                    );
124
125                    let mut tree_start = 0;
126                    for candidate_set in candidate_sets {
127                        let tree_end = tree_start + candidate_set.len();
128
129                        if tree_start < segment_end && segment_start < tree_end {
130                            let start = cmp::max(tree_start, segment_start) - tree_start;
131                            let end = cmp::min(tree_end, segment_end) - tree_start;
132                            let candidates = candidate_set.candidates(start).take(end - start);
133
134                            let worktree_id = candidate_set.id();
135                            let prefix = candidate_set.prefix().chars().collect::<Vec<_>>();
136                            let lowercase_prefix = prefix
137                                .iter()
138                                .map(|c| c.to_ascii_lowercase())
139                                .collect::<Vec<_>>();
140                            matcher.match_candidates(
141                                &prefix,
142                                &lowercase_prefix,
143                                candidates,
144                                results,
145                                cancel_flag,
146                                |candidate, score| PathMatch {
147                                    score,
148                                    worktree_id,
149                                    positions: Vec::new(),
150                                    path: candidate.path.clone(),
151                                    path_prefix: candidate_set.prefix(),
152                                },
153                            );
154                        }
155                        if tree_end >= segment_end {
156                            break;
157                        }
158                        tree_start = tree_end;
159                    }
160                })
161            }
162        })
163        .await;
164
165    let mut results = Vec::new();
166    for segment_result in segment_results {
167        if results.is_empty() {
168            results = segment_result;
169        } else {
170            util::extend_sorted(&mut results, segment_result, max_results, |a, b| b.cmp(a));
171        }
172    }
173    results
174}