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