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#[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
28pub 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#[derive(Debug, Default)]
42pub struct QueryEvaluation {
43 pub candidates: HashSet<usize>,
44 pub fuzzy_terms: HashSet<String>,
45}
46
47pub 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 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 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}