Skip to main content

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}