1use crate::{
  2    matcher::{Match, MatchCandidate, Matcher},
  3    CharBag,
  4};
  5use gpui::BackgroundExecutor;
  6use std::{
  7    borrow::Cow,
  8    cmp::{self, Ordering},
  9    iter,
 10    ops::Range,
 11    sync::atomic::AtomicBool,
 12};
 13
 14#[derive(Clone, Debug)]
 15pub struct StringMatchCandidate {
 16    pub id: usize,
 17    pub string: String,
 18    pub char_bag: CharBag,
 19}
 20
 21impl Match for StringMatch {
 22    fn score(&self) -> f64 {
 23        self.score
 24    }
 25
 26    fn set_positions(&mut self, positions: Vec<usize>) {
 27        self.positions = positions;
 28    }
 29}
 30
 31impl StringMatchCandidate {
 32    pub fn new(id: usize, string: String) -> Self {
 33        Self {
 34            id,
 35            char_bag: CharBag::from(string.as_str()),
 36            string,
 37        }
 38    }
 39}
 40
 41impl<'a> MatchCandidate for &'a StringMatchCandidate {
 42    fn has_chars(&self, bag: CharBag) -> bool {
 43        self.char_bag.is_superset(bag)
 44    }
 45
 46    fn to_string(&self) -> Cow<'a, str> {
 47        self.string.as_str().into()
 48    }
 49}
 50
 51#[derive(Clone, Debug)]
 52pub struct StringMatch {
 53    pub candidate_id: usize,
 54    pub score: f64,
 55    pub positions: Vec<usize>,
 56    pub string: String,
 57}
 58
 59impl StringMatch {
 60    pub fn ranges(&self) -> impl '_ + Iterator<Item = Range<usize>> {
 61        let mut positions = self.positions.iter().peekable();
 62        iter::from_fn(move || {
 63            if let Some(start) = positions.next().copied() {
 64                let mut end = start + self.char_len_at_index(start);
 65                while let Some(next_start) = positions.peek() {
 66                    if end == **next_start {
 67                        end += self.char_len_at_index(end);
 68                        positions.next();
 69                    } else {
 70                        break;
 71                    }
 72                }
 73
 74                return Some(start..end);
 75            }
 76            None
 77        })
 78    }
 79
 80    fn char_len_at_index(&self, ix: usize) -> usize {
 81        self.string[ix..].chars().next().unwrap().len_utf8()
 82    }
 83}
 84
 85impl PartialEq for StringMatch {
 86    fn eq(&self, other: &Self) -> bool {
 87        self.cmp(other).is_eq()
 88    }
 89}
 90
 91impl Eq for StringMatch {}
 92
 93impl PartialOrd for StringMatch {
 94    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 95        Some(self.cmp(other))
 96    }
 97}
 98
 99impl Ord for StringMatch {
100    fn cmp(&self, other: &Self) -> Ordering {
101        self.score
102            .partial_cmp(&other.score)
103            .unwrap_or(Ordering::Equal)
104            .then_with(|| self.candidate_id.cmp(&other.candidate_id))
105    }
106}
107
108pub async fn match_strings(
109    candidates: &[StringMatchCandidate],
110    query: &str,
111    smart_case: bool,
112    max_results: usize,
113    cancel_flag: &AtomicBool,
114    executor: BackgroundExecutor,
115) -> Vec<StringMatch> {
116    if candidates.is_empty() || max_results == 0 {
117        return Default::default();
118    }
119
120    if query.is_empty() {
121        return candidates
122            .iter()
123            .map(|candidate| StringMatch {
124                candidate_id: candidate.id,
125                score: 0.,
126                positions: Default::default(),
127                string: candidate.string.clone(),
128            })
129            .collect();
130    }
131
132    let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
133    let query = query.chars().collect::<Vec<_>>();
134
135    let lowercase_query = &lowercase_query;
136    let query = &query;
137    let query_char_bag = CharBag::from(&lowercase_query[..]);
138
139    let num_cpus = executor.num_cpus().min(candidates.len());
140    let segment_size = (candidates.len() + num_cpus - 1) / num_cpus;
141    let mut segment_results = (0..num_cpus)
142        .map(|_| Vec::with_capacity(max_results.min(candidates.len())))
143        .collect::<Vec<_>>();
144
145    executor
146        .scoped(|scope| {
147            for (segment_idx, results) in segment_results.iter_mut().enumerate() {
148                let cancel_flag = &cancel_flag;
149                scope.spawn(async move {
150                    let segment_start = cmp::min(segment_idx * segment_size, candidates.len());
151                    let segment_end = cmp::min(segment_start + segment_size, candidates.len());
152                    let mut matcher = Matcher::new(
153                        query,
154                        lowercase_query,
155                        query_char_bag,
156                        smart_case,
157                        max_results,
158                    );
159
160                    matcher.match_candidates(
161                        &[],
162                        &[],
163                        candidates[segment_start..segment_end].iter(),
164                        results,
165                        cancel_flag,
166                        |candidate, score| StringMatch {
167                            candidate_id: candidate.id,
168                            score,
169                            positions: Vec::new(),
170                            string: candidate.string.to_string(),
171                        },
172                    );
173                });
174            }
175        })
176        .await;
177
178    let mut results = Vec::new();
179    for segment_result in segment_results {
180        if results.is_empty() {
181            results = segment_result;
182        } else {
183            util::extend_sorted(&mut results, segment_result, max_results, |a, b| b.cmp(a));
184        }
185    }
186    results
187}