ailloli_ui_editor/code/search.rs
1//! Cached, non-overlapping UTF-8 byte-range text search.
2
3use std::ops::Range;
4
5use crate::code::DocumentVersion;
6
7/// Query used by the code editor search engine.
8///
9/// Matching is case-insensitive and substring-based by default. Case folding
10/// and whole-word boundaries intentionally use ASCII semantics.
11///
12/// # Examples
13///
14/// ```
15/// use ailloli_ui_editor::SearchQuery;
16///
17/// let query = SearchQuery::new("name").case_sensitive(true).whole_word(true);
18/// assert_eq!(query.text, "name");
19/// assert!(query.case_sensitive && query.whole_word);
20/// ```
21#[derive(Debug, Clone, PartialEq, Eq, Hash)]
22pub struct SearchQuery {
23 /// Search needle; an empty string matches nothing.
24 pub text: String,
25 /// Whether ASCII letter case must match exactly.
26 pub case_sensitive: bool,
27 /// Whether adjacent ASCII letters, digits, or underscores reject a match.
28 pub whole_word: bool,
29}
30
31/// Builds search queries.
32impl SearchQuery {
33 /// Creates a case-insensitive substring query.
34 ///
35 /// # Examples
36 ///
37 /// ```
38 /// use ailloli_ui_editor::SearchQuery;
39 ///
40 /// let query = SearchQuery::new("TODO");
41 /// assert!(!query.case_sensitive);
42 /// assert!(!query.whole_word);
43 /// ```
44 pub fn new(text: impl Into<String>) -> Self {
45 Self {
46 text: text.into(),
47 case_sensitive: false,
48 whole_word: false,
49 }
50 }
51
52 /// Sets exact ASCII case matching and returns the query.
53 ///
54 /// # Examples
55 ///
56 /// ```
57 /// use ailloli_ui_editor::SearchQuery;
58 ///
59 /// assert!(SearchQuery::new("x").case_sensitive(true).case_sensitive);
60 /// ```
61 pub fn case_sensitive(mut self, case_sensitive: bool) -> Self {
62 self.case_sensitive = case_sensitive;
63 self
64 }
65
66 /// Sets ASCII whole-word filtering and returns the query.
67 ///
68 /// # Examples
69 ///
70 /// ```
71 /// use ailloli_ui_editor::SearchQuery;
72 ///
73 /// assert!(SearchQuery::new("let").whole_word(true).whole_word);
74 /// ```
75 pub fn whole_word(mut self, whole_word: bool) -> Self {
76 self.whole_word = whole_word;
77 self
78 }
79}
80
81/// One non-overlapping search result expressed as a UTF-8 byte range.
82///
83/// # Examples
84///
85/// ```
86/// use ailloli_ui_editor::SearchMatch;
87///
88/// let found = SearchMatch { range: 2..5 };
89/// assert_eq!(found.range.len(), 3);
90/// ```
91#[derive(Debug, Clone, PartialEq, Eq)]
92pub struct SearchMatch {
93 /// Half-open UTF-8 byte range in the searched text.
94 pub range: Range<usize>,
95}
96
97/// Mutable search results, selection, and cache state.
98///
99/// The cache key contains only the query and [`DocumentVersion`]. Callers must
100/// change the version whenever the searched text changes or explicitly call
101/// [`SearchState::invalidate_cache`].
102///
103/// # Examples
104///
105/// ```
106/// use ailloli_ui_editor::{DocumentVersion, SearchQuery, SearchState};
107///
108/// let mut state = SearchState::new(SearchQuery::new("go"));
109/// assert!(state.refresh("go stop go", DocumentVersion(1)));
110/// assert_eq!(state.matches.len(), 2);
111/// assert_eq!(state.active_index, Some(0));
112/// ```
113#[derive(Debug, Clone, PartialEq, Eq)]
114pub struct SearchState {
115 /// Query used by the next refresh.
116 pub query: SearchQuery,
117 /// Ordered, non-overlapping matches from the last refresh.
118 pub matches: Vec<SearchMatch>,
119 /// Selected match index, or `None` when no match is selected.
120 pub active_index: Option<usize>,
121 /// Query/version pair used to detect redundant refreshes.
122 cache_key: Option<SearchCacheKey>,
123}
124
125/// Creates an empty search state with an empty query.
126impl Default for SearchState {
127 /// Creates an empty, unrefreshed state with the default empty query.
128 fn default() -> Self {
129 Self {
130 query: SearchQuery::new(""),
131 matches: Vec::new(),
132 active_index: None,
133 cache_key: None,
134 }
135 }
136}
137
138/// Updates search results and active-match selection.
139impl SearchState {
140 /// Creates an unrefreshed state for `query`.
141 ///
142 /// # Examples
143 ///
144 /// ```
145 /// use ailloli_ui_editor::{SearchQuery, SearchState};
146 ///
147 /// let state = SearchState::new(SearchQuery::new("needle"));
148 /// assert_eq!(state.query.text, "needle");
149 /// assert!(state.matches.is_empty() && state.active_index.is_none());
150 /// ```
151 pub fn new(query: SearchQuery) -> Self {
152 Self {
153 query,
154 ..Self::default()
155 }
156 }
157
158 /// Replaces the query and clears cached results when it differs.
159 ///
160 /// Supplying an equal query is a no-op and preserves both matches and the
161 /// active index.
162 ///
163 /// # Examples
164 ///
165 /// ```
166 /// use ailloli_ui_editor::{DocumentVersion, SearchQuery, SearchState};
167 ///
168 /// let mut state = SearchState::new(SearchQuery::new("old"));
169 /// state.refresh("old", DocumentVersion(1));
170 /// state.set_query(SearchQuery::new("new"));
171 /// assert!(state.matches.is_empty() && state.active_index.is_none());
172 /// ```
173 pub fn set_query(&mut self, query: SearchQuery) {
174 if self.query != query {
175 self.query = query;
176 self.matches.clear();
177 self.active_index = None;
178 self.cache_key = None;
179 }
180 }
181
182 /// Recomputes results unless the query/version cache key is unchanged.
183 ///
184 /// Returns `true` after recomputation and `false` for a cache hit. An
185 /// existing active index is clamped to the new final match; non-empty fresh
186 /// results otherwise select index zero.
187 ///
188 /// # Examples
189 ///
190 /// ```
191 /// use ailloli_ui_editor::{DocumentVersion, SearchQuery, SearchState};
192 ///
193 /// let mut state = SearchState::new(SearchQuery::new("a"));
194 /// assert!(state.refresh("a a", DocumentVersion(4)));
195 /// assert!(!state.refresh("different text", DocumentVersion(4)));
196 /// assert_eq!(state.matches.len(), 2);
197 /// ```
198 pub fn refresh(&mut self, text: &str, version: DocumentVersion) -> bool {
199 let key = SearchCacheKey {
200 version,
201 query: self.query.clone(),
202 };
203 if self.cache_key.as_ref() == Some(&key) {
204 return false;
205 }
206 self.matches = find_matches(text, &self.query);
207 self.active_index = if self.matches.is_empty() {
208 None
209 } else {
210 Some(self.active_index.unwrap_or(0).min(self.matches.len() - 1))
211 };
212 self.cache_key = Some(key);
213 true
214 }
215
216 /// Selects and returns the following match, wrapping at the end.
217 ///
218 /// Because a successful refresh selects index zero, the first call after a
219 /// multi-match refresh advances to index one. With no results, this returns
220 /// `None` and clears the active index.
221 ///
222 /// # Examples
223 ///
224 /// ```
225 /// use ailloli_ui_editor::{DocumentVersion, SearchQuery, SearchState};
226 ///
227 /// let mut state = SearchState::new(SearchQuery::new("x"));
228 /// state.refresh("x x", DocumentVersion(1));
229 /// assert_eq!(state.next_match().map(|m| m.range.clone()), Some(2..3));
230 /// assert_eq!(state.next_match().map(|m| m.range.clone()), Some(0..1));
231 /// ```
232 pub fn next_match(&mut self) -> Option<&SearchMatch> {
233 if self.matches.is_empty() {
234 self.active_index = None;
235 return None;
236 }
237 let next = self
238 .active_index
239 .map(|idx| (idx + 1) % self.matches.len())
240 .unwrap_or(0);
241 self.active_index = Some(next);
242 self.matches.get(next)
243 }
244
245 /// Selects and returns the preceding match, wrapping at the start.
246 ///
247 /// With no results, this returns `None` and clears the active index.
248 ///
249 /// # Examples
250 ///
251 /// ```
252 /// use ailloli_ui_editor::{DocumentVersion, SearchQuery, SearchState};
253 ///
254 /// let mut state = SearchState::new(SearchQuery::new("x"));
255 /// state.refresh("x x", DocumentVersion(1));
256 /// assert_eq!(state.previous_match().map(|m| m.range.clone()), Some(2..3));
257 /// ```
258 pub fn previous_match(&mut self) -> Option<&SearchMatch> {
259 if self.matches.is_empty() {
260 self.active_index = None;
261 return None;
262 }
263 let previous = self
264 .active_index
265 .map(|idx| {
266 if idx == 0 {
267 self.matches.len() - 1
268 } else {
269 idx - 1
270 }
271 })
272 .unwrap_or(0);
273 self.active_index = Some(previous);
274 self.matches.get(previous)
275 }
276
277 /// Selects an in-range match index, otherwise clears the selection.
278 ///
279 /// # Examples
280 ///
281 /// ```
282 /// use ailloli_ui_editor::{DocumentVersion, SearchQuery, SearchState};
283 ///
284 /// let mut state = SearchState::new(SearchQuery::new("x"));
285 /// state.refresh("x x", DocumentVersion(1));
286 /// state.set_active_index(Some(9));
287 /// assert_eq!(state.active_index, None);
288 /// state.set_active_index(Some(1));
289 /// assert_eq!(state.active_index, Some(1));
290 /// ```
291 pub fn set_active_index(&mut self, active_index: Option<usize>) {
292 self.active_index = active_index.filter(|idx| *idx < self.matches.len());
293 }
294
295 /// Restores the default empty query, results, selection, and cache.
296 ///
297 /// # Examples
298 ///
299 /// ```
300 /// use ailloli_ui_editor::{DocumentVersion, SearchQuery, SearchState};
301 ///
302 /// let mut state = SearchState::new(SearchQuery::new("x"));
303 /// state.refresh("x", DocumentVersion(1));
304 /// state.clear();
305 /// assert!(state.query.text.is_empty() && state.matches.is_empty());
306 /// ```
307 pub fn clear(&mut self) {
308 *self = Self::default();
309 }
310
311 /// Forces the next [`SearchState::refresh`] to recompute.
312 ///
313 /// Existing results and selection remain available until that refresh.
314 ///
315 /// # Examples
316 ///
317 /// ```
318 /// use ailloli_ui_editor::{DocumentVersion, SearchQuery, SearchState};
319 ///
320 /// let mut state = SearchState::new(SearchQuery::new("x"));
321 /// state.refresh("x", DocumentVersion(1));
322 /// state.invalidate_cache();
323 /// assert!(state.refresh("x x", DocumentVersion(1)));
324 /// assert_eq!(state.matches.len(), 2);
325 /// ```
326 pub fn invalidate_cache(&mut self) {
327 self.cache_key = None;
328 }
329}
330
331/// Internal key for reusing a completed search.
332#[derive(Debug, Clone, PartialEq, Eq)]
333struct SearchCacheKey {
334 /// Caller-owned version of the searched document.
335 version: DocumentVersion,
336 /// Query whose results are cached.
337 query: SearchQuery,
338}
339
340/// Finds ordered, non-overlapping matches for a query.
341///
342/// Ranges are UTF-8 byte offsets. An empty needle returns no matches;
343/// case-insensitive matching folds ASCII only; whole-word mode treats ASCII
344/// letters, digits, and `_` as word characters.
345///
346/// # Examples
347///
348/// ```
349/// use ailloli_ui_editor::{code::find_matches, SearchQuery};
350///
351/// let query = SearchQuery::new("cat").whole_word(true);
352/// let ranges: Vec<_> = find_matches("Cat scatter cat", &query)
353/// .into_iter()
354/// .map(|m| m.range)
355/// .collect();
356/// assert_eq!(ranges, [0..3, 12..15]);
357/// assert!(find_matches("anything", &SearchQuery::new("")).is_empty());
358/// ```
359pub fn find_matches(text: &str, query: &SearchQuery) -> Vec<SearchMatch> {
360 if query.text.is_empty() {
361 return Vec::new();
362 }
363 let matches = if query.case_sensitive {
364 find_matches_case_sensitive(text, &query.text)
365 } else {
366 find_matches_case_insensitive(text, &query.text)
367 };
368 if query.whole_word {
369 matches
370 .into_iter()
371 .filter(|search_match| is_whole_word_match(text, search_match.range.clone()))
372 .collect()
373 } else {
374 matches
375 }
376}
377
378/// Finds exact-case, non-overlapping substring matches.
379fn find_matches_case_sensitive(text: &str, needle: &str) -> Vec<SearchMatch> {
380 let mut matches = Vec::new();
381 let mut start = 0;
382 while let Some(pos) = text[start..].find(needle) {
383 let lo = start + pos;
384 let hi = lo + needle.len();
385 matches.push(SearchMatch { range: lo..hi });
386 start = hi;
387 }
388 matches
389}
390
391/// Tests ASCII word boundaries around a valid match range.
392fn is_whole_word_match(text: &str, range: Range<usize>) -> bool {
393 let before = text[..range.start].chars().next_back();
394 let after = text[range.end..].chars().next();
395 !before.is_some_and(is_ascii_word_char) && !after.is_some_and(is_ascii_word_char)
396}
397
398/// Returns whether a character participates in an ASCII identifier-like word.
399fn is_ascii_word_char(ch: char) -> bool {
400 ch == '_' || ch.is_ascii_alphanumeric()
401}
402
403/// Finds ASCII-case-insensitive, non-overlapping substring matches.
404fn find_matches_case_insensitive(text: &str, needle: &str) -> Vec<SearchMatch> {
405 let mut matches = Vec::new();
406 let mut start = 0;
407 while start <= text.len().saturating_sub(needle.len()) {
408 let mut found = None;
409 for (relative, _) in text[start..].char_indices() {
410 let lo = start + relative;
411 let hi = lo + needle.len();
412 if hi <= text.len()
413 && text.is_char_boundary(hi)
414 && text[lo..hi].eq_ignore_ascii_case(needle)
415 {
416 found = Some(lo);
417 break;
418 }
419 }
420 let Some(lo) = found else {
421 break;
422 };
423 let hi = lo + needle.len();
424 matches.push(SearchMatch { range: lo..hi });
425 start = hi;
426 }
427 matches
428}