Skip to main content

searchlight/
executor.rs

1use std::collections::HashSet;
2
3use crate::cache::{fuzzy_cache_key, SearchCache};
4use crate::fuzzy;
5use crate::index::InvertedIndex;
6use crate::pinyin::PinyinIndex;
7use crate::query::{ParsedQuery, QueryOp};
8use crate::SearchOptions;
9
10/// Limits applied during query evaluation.
11#[derive(Debug, Clone, Copy)]
12pub struct ExecutorLimits {
13    pub max_candidates: usize,
14    pub max_fuzzy_terms_scan: usize,
15    pub max_fuzzy_results_per_term: usize,
16}
17
18impl Default for ExecutorLimits {
19    fn default() -> Self {
20        ExecutorLimits {
21            max_candidates: 10_000,
22            max_fuzzy_terms_scan: 5_000,
23            max_fuzzy_results_per_term: 32,
24        }
25    }
26}
27
28/// Context passed to the query executor.
29pub struct ExecutorContext<'a> {
30    pub index: &'a InvertedIndex,
31    pub pinyin_index: &'a PinyinIndex,
32    pub cache: &'a SearchCache,
33    pub index_generation: u64,
34    pub options: &'a SearchOptions,
35    pub parsed: &'a ParsedQuery,
36    pub query: &'a str,
37    pub limits: ExecutorLimits,
38}
39
40/// Result of evaluating a query AST against the index.
41#[derive(Debug, Default)]
42pub struct QueryEvaluation {
43    pub candidates: HashSet<usize>,
44    pub fuzzy_terms: HashSet<String>,
45}
46
47/// Evaluates `QueryOp` AST with correct boolean semantics.
48pub struct QueryExecutor;
49
50impl QueryExecutor {
51    pub fn evaluate(ctx: &ExecutorContext<'_>, op: &QueryOp) -> QueryEvaluation {
52        let mut evaluation = QueryEvaluation::default();
53        evaluation.candidates = Self::evaluate_op(ctx, op, &mut evaluation.fuzzy_terms);
54        evaluation
55    }
56
57    /// Whether a single document satisfies the query AST.
58    pub fn document_matches(ctx: &ExecutorContext<'_>, op: &QueryOp, doc_id: usize) -> bool {
59        Self::evaluate_op(ctx, op, &mut HashSet::new()).contains(&doc_id)
60    }
61
62    /// Collect document IDs that match a pinyin query string.
63    pub fn pinyin_candidates(ctx: &ExecutorContext<'_>, query: &str) -> HashSet<usize> {
64        let mut docs = HashSet::new();
65        let pinyin_results = ctx.pinyin_index.search_by_pinyin_detailed(query);
66        for chinese_term in pinyin_results.keys() {
67            if docs.len() >= ctx.limits.max_candidates {
68                break;
69            }
70            extend_docs_from_term(ctx, chinese_term, &mut docs);
71        }
72        docs
73    }
74
75    fn evaluate_op(
76        ctx: &ExecutorContext<'_>,
77        op: &QueryOp,
78        fuzzy_terms: &mut HashSet<String>,
79    ) -> HashSet<usize> {
80        match op {
81            QueryOp::Term(term) => {
82                let distance = if ctx.options.fuzzy {
83                    ctx.options.max_edit_distance
84                } else {
85                    0
86                };
87                docs_for_term(ctx, term, distance, fuzzy_terms)
88            }
89            QueryOp::Phrase(terms) => docs_for_phrase(ctx, terms, fuzzy_terms),
90            QueryOp::Fuzzy(term, distance) => {
91                docs_for_term(ctx, term, (*distance).min(3), fuzzy_terms)
92            }
93            QueryOp::Prefix(prefix) => docs_for_prefix(ctx, prefix),
94            QueryOp::CharMatch(chars) => {
95                let sets: Vec<HashSet<usize>> = chars
96                    .iter()
97                    .map(|c| docs_for_term(ctx, &c.to_string(), 0, fuzzy_terms))
98                    .collect();
99                intersect_sets(&sets, ctx.limits.max_candidates)
100            }
101            QueryOp::And(children) => {
102                let mut include_sets = Vec::new();
103                let mut exclude_sets = Vec::new();
104
105                for child in children {
106                    match child {
107                        QueryOp::Not(inner) => {
108                            exclude_sets.push(Self::evaluate_op(ctx, inner, fuzzy_terms));
109                        }
110                        _ => include_sets.push(Self::evaluate_op(ctx, child, fuzzy_terms)),
111                    }
112                }
113
114                let mut result = if include_sets.is_empty() {
115                    HashSet::new()
116                } else {
117                    intersect_sets(&include_sets, ctx.limits.max_candidates)
118                };
119
120                for exclude in exclude_sets {
121                    result = result.difference(&exclude).copied().collect::<HashSet<_>>();
122                }
123
124                truncate_set(&mut result, ctx.limits.max_candidates);
125                result
126            }
127            QueryOp::Or(children) => {
128                let sets: Vec<HashSet<usize>> = children
129                    .iter()
130                    .filter(|c| !matches!(c, QueryOp::Not(_)))
131                    .map(|c| Self::evaluate_op(ctx, c, fuzzy_terms))
132                    .collect();
133                union_sets(&sets, ctx.limits.max_candidates)
134            }
135            QueryOp::Not(_) => HashSet::new(),
136        }
137    }
138}
139
140fn docs_for_term(
141    ctx: &ExecutorContext<'_>,
142    term: &str,
143    max_distance: usize,
144    fuzzy_terms: &mut HashSet<String>,
145) -> HashSet<usize> {
146    let mut docs = HashSet::new();
147    extend_docs_from_term(ctx, term, &mut docs);
148
149    if max_distance > 0 {
150        for expanded in fuzzy_expansion(ctx, term, max_distance) {
151            fuzzy_terms.insert(expanded.clone());
152            extend_docs_from_term(ctx, &expanded, &mut docs);
153            if docs.len() >= ctx.limits.max_candidates {
154                break;
155            }
156        }
157    }
158
159    truncate_set(&mut docs, ctx.limits.max_candidates);
160    docs
161}
162
163fn docs_for_phrase(
164    ctx: &ExecutorContext<'_>,
165    terms: &[String],
166    fuzzy_terms: &mut HashSet<String>,
167) -> HashSet<usize> {
168    if terms.is_empty() {
169        return HashSet::new();
170    }
171
172    let sets: Vec<HashSet<usize>> = terms
173        .iter()
174        .map(|t| docs_for_term(ctx, t, 0, fuzzy_terms))
175        .collect();
176    let mut docs = intersect_sets(&sets, ctx.limits.max_candidates);
177
178    docs.retain(|&doc_id| phrase_matches(ctx.index, doc_id, terms));
179    truncate_set(&mut docs, ctx.limits.max_candidates);
180    docs
181}
182
183fn docs_for_prefix(ctx: &ExecutorContext<'_>, prefix: &str) -> HashSet<usize> {
184    let mut docs = HashSet::new();
185    for term in ctx.index.terms_with_prefix(prefix) {
186        extend_docs_from_term(ctx, &term, &mut docs);
187        if docs.len() >= ctx.limits.max_candidates {
188            break;
189        }
190    }
191    docs
192}
193
194fn extend_docs_from_term(ctx: &ExecutorContext<'_>, term: &str, docs: &mut HashSet<usize>) {
195    if docs.len() >= ctx.limits.max_candidates {
196        return;
197    }
198    if let Some(postings) = ctx.index.posting_list(term) {
199        for posting in postings {
200            if docs.len() >= ctx.limits.max_candidates {
201                break;
202            }
203            docs.insert(posting.doc_id);
204        }
205    }
206}
207
208fn fuzzy_expansion(ctx: &ExecutorContext<'_>, term: &str, max_distance: usize) -> Vec<String> {
209    let cache_key = fuzzy_cache_key(ctx.index_generation, term, max_distance);
210
211    if ctx.options.enable_cache {
212        if let Some(cached) = ctx.cache.get_fuzzy_expansion(cache_key) {
213            return cached;
214        }
215    }
216
217    let all_terms = ctx
218        .index
219        .terms_with_prefix_limited("", ctx.limits.max_fuzzy_terms_scan);
220    let matches = fuzzy::fuzzy_match_limited(
221        term,
222        &all_terms,
223        max_distance,
224        ctx.limits.max_fuzzy_results_per_term,
225    );
226    let terms: Vec<String> = matches.into_iter().map(|m| m.term).collect();
227
228    if ctx.options.enable_cache {
229        ctx.cache.put_fuzzy_expansion(cache_key, terms.clone());
230    }
231
232    terms
233}
234
235pub(crate) fn phrase_matches_public(
236    index: &InvertedIndex,
237    doc_id: usize,
238    phrase: &[String],
239) -> bool {
240    phrase_matches(index, doc_id, phrase)
241}
242
243pub(crate) fn fuzzy_expansion_public(
244    ctx: &ExecutorContext<'_>,
245    term: &str,
246    max_distance: usize,
247) -> Vec<String> {
248    fuzzy_expansion(ctx, term, max_distance)
249}
250
251fn phrase_matches(index: &InvertedIndex, doc_id: usize, phrase: &[String]) -> bool {
252    if phrase.len() < 2 {
253        return phrase
254            .first()
255            .map(|t| index.term_freq_in_doc(t, doc_id) > 0)
256            .unwrap_or(false);
257    }
258
259    let Some(tokens) = index.document_tokens(doc_id) else {
260        return false;
261    };
262
263    let token_texts: Vec<&str> = tokens.iter().map(|t| t.text.as_str()).collect();
264    let phrase_refs: Vec<&str> = phrase.iter().map(String::as_str).collect();
265    let window = phrase.len();
266
267    token_texts
268        .windows(window)
269        .any(|w| w == phrase_refs.as_slice())
270}
271
272fn intersect_sets(sets: &[HashSet<usize>], max: usize) -> HashSet<usize> {
273    if sets.is_empty() {
274        return HashSet::new();
275    }
276
277    let mut result = sets[0].clone();
278    for set in sets.iter().skip(1) {
279        result = result.intersection(set).copied().collect();
280        if result.is_empty() {
281            return result;
282        }
283    }
284
285    truncate_set(&mut result, max);
286    result
287}
288
289fn union_sets(sets: &[HashSet<usize>], max: usize) -> HashSet<usize> {
290    let mut result = HashSet::new();
291    for set in sets {
292        for &doc_id in set {
293            if result.len() >= max {
294                return result;
295            }
296            result.insert(doc_id);
297        }
298    }
299    result
300}
301
302fn truncate_set(set: &mut HashSet<usize>, max: usize) {
303    if set.len() <= max {
304        return;
305    }
306    let keep: HashSet<usize> = set.iter().take(max).copied().collect();
307    *set = keep;
308}
309
310#[cfg(test)]
311mod tests {
312    use super::*;
313    use crate::pinyin::PinyinIndex;
314    use crate::query::QueryParser;
315    use crate::SearchCache;
316
317    struct Fixture {
318        index: InvertedIndex,
319        pinyin_index: PinyinIndex,
320        cache: SearchCache,
321    }
322
323    impl Fixture {
324        fn index(&mut self, text: &str) {
325            self.index.add_document(text);
326        }
327
328        fn eval(&self, query: &str, options: SearchOptions) -> HashSet<usize> {
329            let parser = QueryParser::new();
330            let parsed = parser.parse(query);
331            let ctx = ExecutorContext {
332                index: &self.index,
333                pinyin_index: &self.pinyin_index,
334                cache: &self.cache,
335                index_generation: 0,
336                options: &options,
337                parsed: &parsed,
338                query,
339                limits: ExecutorLimits::default(),
340            };
341            QueryExecutor::evaluate(&ctx, &parsed.root).candidates
342        }
343    }
344
345    #[test]
346    fn test_and_intersection() {
347        let mut fx = Fixture {
348            index: InvertedIndex::new(),
349            pinyin_index: PinyinIndex::new(),
350            cache: SearchCache::new(),
351        };
352        fx.index("Rust and Python are great");
353        fx.index("Python is easy");
354        fx.index("Rust is memory safe");
355
356        assert_eq!(
357            fx.eval("Rust AND Python", SearchOptions::default()).len(),
358            1
359        );
360    }
361
362    #[test]
363    fn test_or_union() {
364        let mut fx = Fixture {
365            index: InvertedIndex::new(),
366            pinyin_index: PinyinIndex::new(),
367            cache: SearchCache::new(),
368        };
369        fx.index("only rust here");
370        fx.index("only python here");
371
372        assert_eq!(fx.eval("rust OR python", SearchOptions::default()).len(), 2);
373    }
374
375    #[test]
376    fn test_not_exclusion() {
377        let mut fx = Fixture {
378            index: InvertedIndex::new(),
379            pinyin_index: PinyinIndex::new(),
380            cache: SearchCache::new(),
381        };
382        fx.index("rust programming");
383        fx.index("python programming");
384
385        assert_eq!(
386            fx.eval("programming -python", SearchOptions::default())
387                .len(),
388            1
389        );
390    }
391
392    #[test]
393    fn test_phrase_consecutive() {
394        let mut fx = Fixture {
395            index: InvertedIndex::new(),
396            pinyin_index: PinyinIndex::new(),
397            cache: SearchCache::new(),
398        };
399        fx.index("I love rust programming");
400        fx.index("rust is great for programming");
401
402        assert_eq!(
403            fx.eval("\"rust programming\"", SearchOptions::default())
404                .len(),
405            1
406        );
407    }
408
409    #[test]
410    fn test_implicit_and_multi_term() {
411        let mut fx = Fixture {
412            index: InvertedIndex::new(),
413            pinyin_index: PinyinIndex::new(),
414            cache: SearchCache::new(),
415        };
416        fx.index("hello world");
417        fx.index("hello there");
418        fx.index("world alone");
419
420        assert_eq!(fx.eval("hello world", SearchOptions::default()).len(), 1);
421    }
422}