pxh/recall/query.rs
1//! Parsed recall query: the single owner of the query→atoms mapping shared
2//! by the DB prefilter and the nucleo fuzzy stage.
3//!
4//! The invariant this module exists to hold in one place: the LIKE
5//! conditions from `like_patterns()` must accept every row the nucleo
6//! pattern from `scoring_pattern()` can match (the prefilter is a strict
7//! superset of the fuzzy stage). Both sides derive from the same
8//! normalization and the same atom split, so they cannot drift apart.
9//!
10//! Known bounded exception: nucleo's `Normalization::Smart` folds accented
11//! haystack chars onto ASCII query chars (`cafe` matches `café`); a byte-wise
12//! LIKE cannot express that, so a haystack whose only match is via folding
13//! can still be prefiltered away. Non-ASCII *query* chars are simply not
14//! required by the prefilter (requiring less always preserves the superset).
15
16use nucleo::pattern::{CaseMatching, Normalization, Pattern};
17
18/// Characters treated as word separators in recall search. `-` covers flag
19/// forms (`--release`), `*` covers glob queries, and `/` covers path
20/// components so a match after any of them scores like a whitespace boundary
21/// rather than nucleo's (lower) delimiter boundary.
22pub fn is_recall_separator(c: char) -> bool {
23 matches!(c, '-' | '*' | '/')
24}
25
26/// Map separator chars to space so nucleo treats them as word boundaries;
27/// pass through everything else.
28pub fn normalize_recall_char(c: char) -> char {
29 if is_recall_separator(c) { ' ' } else { c }
30}
31
32/// A recall query parsed once into nucleo-style atoms.
33///
34/// Equality is on the raw text: two queries compare equal iff the user typed
35/// the same thing, which is what cache keying wants.
36#[derive(Debug, Clone)]
37pub struct RecallQuery {
38 raw: String,
39 normalized: String,
40 /// Character runs the DB prefilter requires as ordered subsequences, one
41 /// per positive atom (operators stripped, escapes resolved, non-ASCII
42 /// dropped). Negated atoms contribute nothing: LIKE can only require
43 /// presence, so the fuzzy stage alone enforces absence.
44 required: Vec<String>,
45}
46
47impl PartialEq for RecallQuery {
48 fn eq(&self, other: &Self) -> bool {
49 self.raw == other.raw
50 }
51}
52
53impl RecallQuery {
54 pub fn parse(raw: &str) -> Self {
55 let normalized: String = raw.chars().map(normalize_recall_char).collect();
56 let required = atomize(&normalized).into_iter().filter_map(required_chars).collect();
57 RecallQuery { raw: raw.to_string(), normalized, required }
58 }
59
60 pub fn raw(&self) -> &str {
61 &self.raw
62 }
63
64 pub fn is_empty(&self) -> bool {
65 self.raw.is_empty()
66 }
67
68 /// Whether this query produces any DB-level prefilter conditions.
69 /// Queries of only negated/operator atoms don't, and load identically
70 /// to no query.
71 pub fn has_prefilter(&self) -> bool {
72 !self.required.is_empty()
73 }
74
75 /// One LIKE pattern per positive atom. "gcm" becomes "%g%c%m%" so it
76 /// matches "git commit -m"; atoms match in any order because each is an
77 /// independent AND'd condition, mirroring nucleo's atom semantics.
78 pub fn like_patterns(&self) -> Vec<String> {
79 self.required.iter().map(|req| like_pattern(req)).collect()
80 }
81
82 /// Whether a candidate set loaded with `self`'s prefilter necessarily
83 /// contains every row a load with `other`'s prefilter would return:
84 /// each of `self`'s required runs must be an (ASCII-case-insensitive,
85 /// matching LIKE's NOCASE) subsequence of one of `other`'s runs, so each
86 /// of `self`'s conditions is implied by one of `other`'s.
87 ///
88 /// Truncation caveat, shared with a fresh load: both sets keep only the
89 /// most recent rows within the oversampled window, so "covers" is
90 /// relative to that window, not the full table.
91 pub fn covers(&self, other: &RecallQuery) -> bool {
92 self.required.iter().all(|prev| other.required.iter().any(|new| is_subsequence(prev, new)))
93 }
94
95 /// Total required chars -- more chars means a narrower candidate set.
96 pub fn specificity(&self) -> usize {
97 self.required.iter().map(String::len).sum()
98 }
99
100 /// The pattern the fuzzy stage scores with: separators normalized to
101 /// spaces so matches after them get nucleo's whitespace-boundary bonus.
102 pub fn scoring_pattern(&self) -> Pattern {
103 Pattern::parse(&self.normalized, CaseMatching::Smart, Normalization::Smart)
104 }
105
106 /// The pattern used for highlight indices: the raw query, so
107 /// "--release" highlights its dashes in the original command text.
108 pub fn highlight_pattern(&self) -> Pattern {
109 Pattern::parse(&self.raw, CaseMatching::Smart, Normalization::Smart)
110 }
111}
112
113/// Split a normalized query into atoms the way nucleo's `Pattern::parse`
114/// does: unescaped whitespace separates atoms, `\ ` keeps a space inside
115/// one. Backslashes are preserved for `required_chars` to resolve, so a
116/// trailing `\$` is still distinguishable from a suffix anchor.
117fn atomize(normalized: &str) -> Vec<String> {
118 let mut atoms = Vec::new();
119 let mut cur = String::new();
120 let mut escaped = false;
121 for c in normalized.chars() {
122 if escaped {
123 cur.push(c);
124 escaped = false;
125 } else if c == '\\' {
126 cur.push(c);
127 escaped = true;
128 } else if c.is_whitespace() {
129 if !cur.is_empty() {
130 atoms.push(std::mem::take(&mut cur));
131 }
132 } else {
133 cur.push(c);
134 }
135 }
136 if !cur.is_empty() {
137 atoms.push(cur);
138 }
139 atoms
140}
141
142/// The chars one positive atom requires the haystack to contain in order,
143/// with fzf-style operators stripped (`^`/`'` prefix, unescaped `$` suffix)
144/// and escapes resolved. `None` for negated atoms and atoms that reduce to
145/// nothing. Non-ASCII chars are dropped: nucleo may satisfy them via Unicode
146/// folding that LIKE can't express, and requiring less keeps the superset.
147fn required_chars(atom: String) -> Option<String> {
148 let mut rest = atom.as_str();
149 if rest.starts_with('!') {
150 return None;
151 }
152 rest = rest.strip_prefix(['^', '\'']).unwrap_or(rest);
153 if rest.ends_with('$') && !rest.ends_with("\\$") {
154 rest = &rest[..rest.len() - 1];
155 }
156
157 let mut required = String::new();
158 let mut escaped = false;
159 for c in rest.chars() {
160 if escaped {
161 escaped = false;
162 if c.is_ascii() {
163 required.push(c);
164 }
165 } else if c == '\\' {
166 escaped = true;
167 } else if c.is_ascii() {
168 required.push(c);
169 }
170 }
171 (!required.is_empty()).then_some(required)
172}
173
174/// Build a LIKE pattern matching `required` as an ordered subsequence:
175/// "gcm" becomes "%g%c%m%".
176fn like_pattern(required: &str) -> String {
177 let mut pattern = String::with_capacity(required.len() * 2 + 1);
178 pattern.push('%');
179 for ch in required.chars() {
180 if matches!(ch, '%' | '_' | '\\') {
181 pattern.push('\\');
182 }
183 pattern.push(ch);
184 pattern.push('%');
185 }
186 pattern
187}
188
189/// Whether `needle`'s chars appear in `hay` in order, ignoring ASCII case
190/// (matching LIKE's NOCASE collation).
191fn is_subsequence(needle: &str, hay: &str) -> bool {
192 let mut hay_chars = hay.chars();
193 needle.chars().all(|n| hay_chars.any(|h| h.eq_ignore_ascii_case(&n)))
194}
195
196#[cfg(test)]
197mod tests {
198 use super::*;
199
200 fn patterns(query: &str) -> Vec<String> {
201 RecallQuery::parse(query).like_patterns()
202 }
203
204 #[test]
205 fn test_separators_split_atoms_before_operator_parsing() {
206 // The prefilter must see the same atoms nucleo scores with:
207 // separators become atom boundaries, not intra-atom wildcards.
208 assert_eq!(patterns("rs/main"), ["%r%s%", "%m%a%i%n%"]);
209 assert_eq!(patterns("git-log"), ["%g%i%t%", "%l%o%g%"]);
210 assert_eq!(patterns("*.rs"), ["%.%r%s%"]);
211 }
212
213 #[test]
214 fn test_operators_stripped_per_atom() {
215 assert_eq!(patterns("^cargo"), ["%c%a%r%g%o%"]);
216 assert_eq!(patterns("'build"), ["%b%u%i%l%d%"]);
217 assert_eq!(patterns("push$"), ["%p%u%s%h%"]);
218 assert_eq!(patterns("^git push$"), ["%g%i%t%", "%p%u%s%h%"]);
219 }
220
221 #[test]
222 fn test_negated_atoms_contribute_nothing() {
223 assert_eq!(patterns("!vim"), Vec::<String>::new());
224 assert_eq!(patterns("!vim cargo"), ["%c%a%r%g%o%"]);
225 // Normalization can split a negated atom; only its leading piece
226 // stays negated, matching what nucleo sees after normalization.
227 assert_eq!(patterns("!foo-bar"), ["%b%a%r%"]);
228 }
229
230 #[test]
231 fn test_escapes_resolved_like_nucleo() {
232 // `\ ` keeps the space inside one atom instead of splitting.
233 assert_eq!(patterns("foo\\ bar"), ["%f%o%o% %b%a%r%"]);
234 // `\$` is a literal dollar, not a suffix anchor.
235 assert_eq!(patterns("cost\\$"), ["%c%o%s%t%$%"]);
236 // `\!` is a literal bang, not negation.
237 assert_eq!(patterns("\\!urgent"), ["%!%u%r%g%e%n%t%"]);
238 // A dangling backslash requires nothing extra.
239 assert_eq!(patterns("foo\\"), ["%f%o%o%"]);
240 }
241
242 #[test]
243 fn test_like_metacharacters_escaped() {
244 assert_eq!(patterns("50%_x"), ["%5%0%\\%%\\_%x%"]);
245 }
246
247 #[test]
248 fn test_non_ascii_chars_not_required() {
249 // nucleo's Smart normalization may satisfy these via folding; LIKE
250 // can't, so the prefilter must not demand them.
251 assert_eq!(patterns("café"), ["%c%a%f%"]);
252 assert!(!RecallQuery::parse("é").has_prefilter());
253 }
254
255 #[test]
256 fn test_has_prefilter() {
257 assert!(RecallQuery::parse("cargo").has_prefilter());
258 assert!(RecallQuery::parse("!vim cargo").has_prefilter());
259 assert!(!RecallQuery::parse("!vim").has_prefilter());
260 assert!(!RecallQuery::parse("^$").has_prefilter());
261 assert!(!RecallQuery::parse(" ").has_prefilter());
262 assert!(!RecallQuery::parse("").has_prefilter());
263 }
264
265 #[test]
266 fn test_covers_extension_and_new_atoms() {
267 let covers = |a: &str, b: &str| RecallQuery::parse(a).covers(&RecallQuery::parse(b));
268 // Appending chars or atoms only narrows the set.
269 assert!(covers("git", "gith"));
270 assert!(covers("git", "git push"));
271 assert!(covers("rs", "rs/main"), "separator append must stay covered");
272 // Atom order doesn't matter: each condition is independent.
273 assert!(covers("push", "git push"));
274 // LIKE is NOCASE, so coverage is too.
275 assert!(covers("GIT", "git push"));
276 // Divergent or broader queries are not covered.
277 assert!(!covers("abc", "abx"));
278 assert!(!covers("git push", "git"));
279 // The no-condition query covers everything (modulo the window).
280 assert!(covers("!vim", "git"));
281 assert!(!covers("git", "!vim"));
282 }
283
284 #[test]
285 fn test_specificity_orders_narrowness() {
286 assert!(
287 RecallQuery::parse("git push").specificity() > RecallQuery::parse("git").specificity()
288 );
289 assert_eq!(RecallQuery::parse("!vim").specificity(), 0);
290 }
291}