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