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