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