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 max_results: usize,
121 cancel_flag: &AtomicBool,
122 executor: BackgroundExecutor,
123) -> Vec<StringMatch>
124where
125 T: Borrow<StringMatchCandidate> + Sync,
126{
127 if candidates.is_empty() || max_results == 0 {
128 return Default::default();
129 }
130
131 if query.is_empty() {
132 return candidates
133 .iter()
134 .map(|candidate| StringMatch {
135 candidate_id: candidate.borrow().id,
136 score: 0.,
137 positions: Default::default(),
138 string: candidate.borrow().string.clone(),
139 })
140 .collect();
141 }
142
143 let lowercase_query = query.to_lowercase().chars().collect::<Vec<_>>();
144 let query = query.chars().collect::<Vec<_>>();
145
146 let lowercase_query = &lowercase_query;
147 let query = &query;
148 let query_char_bag = CharBag::from(&lowercase_query[..]);
149
150 let num_cpus = executor.num_cpus().min(candidates.len());
151 let segment_size = candidates.len().div_ceil(num_cpus);
152 let mut segment_results = (0..num_cpus)
153 .map(|_| Vec::with_capacity(max_results.min(candidates.len())))
154 .collect::<Vec<_>>();
155
156 executor
157 .scoped(|scope| {
158 for (segment_idx, results) in segment_results.iter_mut().enumerate() {
159 let cancel_flag = &cancel_flag;
160 scope.spawn(async move {
161 let segment_start = cmp::min(segment_idx * segment_size, candidates.len());
162 let segment_end = cmp::min(segment_start + segment_size, candidates.len());
163 let mut matcher =
164 Matcher::new(query, lowercase_query, query_char_bag, smart_case);
165
166 matcher.match_candidates(
167 &[],
168 &[],
169 candidates[segment_start..segment_end]
170 .iter()
171 .map(|c| c.borrow()),
172 results,
173 cancel_flag,
174 |candidate: &&StringMatchCandidate, score, positions| StringMatch {
175 candidate_id: candidate.id,
176 score,
177 positions: positions.clone(),
178 string: candidate.string.to_string(),
179 },
180 );
181 });
182 }
183 })
184 .await;
185
186 if cancel_flag.load(atomic::Ordering::Relaxed) {
187 return Vec::new();
188 }
189
190 let mut results = segment_results.concat();
191 util::truncate_to_bottom_n_sorted_by(&mut results, max_results, &|a, b| b.cmp(a));
192 results
193}