1use std::{
  2    borrow::Cow,
  3    cmp::{self, Ordering},
  4    sync::{atomic::AtomicBool, Arc},
  5};
  6
  7use gpui::executor;
  8
  9use crate::{
 10    matcher::{Match, MatchCandidate, Matcher},
 11    CharBag,
 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 PartialEq for StringMatch {
 60    fn eq(&self, other: &Self) -> bool {
 61        self.cmp(other).is_eq()
 62    }
 63}
 64
 65impl Eq for StringMatch {}
 66
 67impl PartialOrd for StringMatch {
 68    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 69        Some(self.cmp(other))
 70    }
 71}
 72
 73impl Ord for StringMatch {
 74    fn cmp(&self, other: &Self) -> Ordering {
 75        self.score
 76            .partial_cmp(&other.score)
 77            .unwrap_or(Ordering::Equal)
 78            .then_with(|| self.candidate_id.cmp(&other.candidate_id))
 79    }
 80}
 81
 82pub async fn match_strings(
 83    candidates: &[StringMatchCandidate],
 84    query: &str,
 85    smart_case: bool,
 86    max_results: usize,
 87    cancel_flag: &AtomicBool,
 88    background: Arc<executor::Background>,
 89) -> Vec<StringMatch> {
 90    if candidates.is_empty() || max_results == 0 {
 91        return Default::default();
 92    }
 93
 94    if query.is_empty() {
 95        return candidates
 96            .iter()
 97            .map(|candidate| StringMatch {
 98                candidate_id: candidate.id,
 99                score: 0.,
100                positions: Default::default(),
101                string: candidate.string.clone(),
102            })
103            .collect();
104    }
105
106    let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
107    let query = query.chars().collect::<Vec<_>>();
108
109    let lowercase_query = &lowercase_query;
110    let query = &query;
111    let query_char_bag = CharBag::from(&lowercase_query[..]);
112
113    let num_cpus = background.num_cpus().min(candidates.len());
114    let segment_size = (candidates.len() + num_cpus - 1) / num_cpus;
115    let mut segment_results = (0..num_cpus)
116        .map(|_| Vec::with_capacity(max_results.min(candidates.len())))
117        .collect::<Vec<_>>();
118
119    background
120        .scoped(|scope| {
121            for (segment_idx, results) in segment_results.iter_mut().enumerate() {
122                let cancel_flag = &cancel_flag;
123                scope.spawn(async move {
124                    let segment_start = cmp::min(segment_idx * segment_size, candidates.len());
125                    let segment_end = cmp::min(segment_start + segment_size, candidates.len());
126                    let mut matcher = Matcher::new(
127                        query,
128                        lowercase_query,
129                        query_char_bag,
130                        smart_case,
131                        max_results,
132                    );
133
134                    matcher.match_candidates(
135                        &[],
136                        &[],
137                        candidates[segment_start..segment_end].iter(),
138                        results,
139                        cancel_flag,
140                        |candidate, score| StringMatch {
141                            candidate_id: candidate.id,
142                            score,
143                            positions: Vec::new(),
144                            string: candidate.string.to_string(),
145                        },
146                    );
147                });
148            }
149        })
150        .await;
151
152    let mut results = Vec::new();
153    for segment_result in segment_results {
154        if results.is_empty() {
155            results = segment_result;
156        } else {
157            util::extend_sorted(&mut results, segment_result, max_results, |a, b| b.cmp(a));
158        }
159    }
160    results
161}