Skip to main content

treesearch/engine/
search.rs

1//! Search pipeline with UTF-8-safe query routing and FTS5-backed flat/tree scoring.
2//!
3//! Two-stage pipeline:
4//! 1. FTS5 pre-scoring: batch score all documents
5//! 2. Mode routing: flat mode (FTS5 results directly) or tree mode (tree walk + reranking)
6
7use std::collections::HashMap;
8
9use anyhow::{bail, Result};
10use regex::{Regex, RegexBuilder};
11
12use crate::config::{SearchMode, TreeSearchConfig};
13use crate::document::{Document, Node, SearchResult};
14use crate::engine::candidate_search;
15use crate::engine::fts::FTS5Index;
16
17#[derive(Debug, Clone)]
18struct QueryMode {
19    effective_query: String,
20    fts_expression: Option<String>,
21    regex_pattern: Option<String>,
22}
23
24fn classify_query_mode(query: &str, fts_expression: Option<&str>, regex: bool) -> QueryMode {
25    if regex {
26        return QueryMode {
27            effective_query: query.to_string(),
28            fts_expression: None,
29            regex_pattern: Some(query.to_string()),
30        };
31    }
32    if let Some(expr) = fts_expression {
33        return QueryMode {
34            effective_query: if query.is_empty() {
35                expr.to_string()
36            } else {
37                query.to_string()
38            },
39            fts_expression: Some(expr.to_string()),
40            regex_pattern: None,
41        };
42    }
43    let trimmed = query.trim();
44    let prefix_body = trimmed.strip_suffix('*').unwrap_or(trimmed);
45    let no_internal_star = !prefix_body.contains('*');
46    let middle = trimmed
47        .strip_prefix('*')
48        .and_then(|value| value.strip_suffix('*'))
49        .unwrap_or("");
50
51    if trimmed.starts_with('*')
52        && trimmed.ends_with('*')
53        && trimmed.chars().count() > 2
54        && !middle.contains('*')
55        && !middle.chars().any(|c| c.is_whitespace())
56    {
57        let term = middle.to_string();
58        return QueryMode {
59            effective_query: term.clone(),
60            fts_expression: None,
61            regex_pattern: Some(regex::escape(&term)),
62        };
63    }
64
65    if trimmed.ends_with('*')
66        && !trimmed.starts_with('*')
67        && trimmed.chars().count() > 1
68        && no_internal_star
69        && !prefix_body.chars().any(|c| c.is_whitespace())
70    {
71        return QueryMode {
72            effective_query: prefix_body.to_string(),
73            fts_expression: Some(trimmed.to_string()),
74            regex_pattern: None,
75        };
76    }
77
78    QueryMode {
79        effective_query: query.to_string(),
80        fts_expression: None,
81        regex_pattern: None,
82    }
83}
84
85fn compile_contains_regex(pattern: &str) -> Result<Regex> {
86    Ok(RegexBuilder::new(pattern).case_insensitive(true).build()?)
87}
88
89fn regex_score_doc(doc: &Document, regex: &Regex) -> HashMap<String, f64> {
90    fn count_matches(regex: &Regex, text: &str) -> usize {
91        regex.find_iter(text).count()
92    }
93
94    fn score_node(node: &Node, regex: &Regex, scores: &mut HashMap<String, f64>) {
95        let hit_count = count_matches(regex, &node.title)
96            + count_matches(regex, &node.summary)
97            + count_matches(regex, &node.text);
98        if hit_count > 0 {
99            scores.insert(node.node_id.clone(), hit_count as f64);
100        }
101    }
102
103    let mut scores = HashMap::new();
104    let mut stack: Vec<&Node> = doc.structure.iter().rev().collect();
105    while let Some(node) = stack.pop() {
106        score_node(node, regex, &mut scores);
107        stack.extend(node.children.iter().rev());
108    }
109
110    if let Some(max_score) = scores.values().copied().reduce(f64::max) {
111        if max_score > 0.0 {
112            for score in scores.values_mut() {
113                *score /= max_score;
114            }
115        }
116    }
117    scores
118}
119
120/// Unified search entry point.
121pub fn search(
122    query: &str,
123    documents: &[Document],
124    fts_index: &FTS5Index,
125    config: &TreeSearchConfig,
126) -> Result<Vec<SearchResult>> {
127    search_with_options(query, documents, fts_index, config, None, false)
128}
129
130pub fn search_with_options(
131    query: &str,
132    documents: &[Document],
133    fts_index: &FTS5Index,
134    config: &TreeSearchConfig,
135    fts_expression: Option<&str>,
136    regex: bool,
137) -> Result<Vec<SearchResult>> {
138    if regex && fts_expression.is_some() {
139        bail!("regex and fts_expression cannot be used together");
140    }
141    if query.trim().is_empty() && fts_expression.is_none() {
142        return Ok(Vec::new());
143    }
144
145    let query_mode = classify_query_mode(query, fts_expression, regex);
146    let mode = candidate_search::resolve_search_mode(config.search_mode, documents);
147    match mode {
148        SearchMode::Flat => search_flat(documents, fts_index, config, &query_mode),
149        SearchMode::Tree => search_tree(documents, fts_index, config, &query_mode),
150        SearchMode::Auto => unreachable!("resolve_search_mode should never return Auto"),
151    }
152}
153
154/// Flat search: FTS5 results directly, ranked by BM25.
155fn search_flat(
156    documents: &[Document],
157    fts_index: &FTS5Index,
158    config: &TreeSearchConfig,
159    query_mode: &QueryMode,
160) -> Result<Vec<SearchResult>> {
161    let scores = if let Some(pattern) = &query_mode.regex_pattern {
162        let regex = compile_contains_regex(pattern)?;
163        documents
164            .iter()
165            .filter_map(|document| {
166                let scores = regex_score_doc(document, &regex);
167                (!scores.is_empty()).then_some((document.doc_id.clone(), scores))
168            })
169            .collect()
170    } else {
171        let doc_ids: Vec<String> = documents.iter().map(|d| d.doc_id.clone()).collect();
172        fts_index.score_nodes_batch_with_expr(
173            &query_mode.effective_query,
174            Some(&doc_ids),
175            0.0,
176            query_mode.fts_expression.as_deref(),
177        )?
178    };
179    let mut flat_config = config.clone();
180    flat_config.search_mode = SearchMode::Flat;
181    Ok(candidate_search::search_with_scores(
182        &query_mode.effective_query,
183        documents,
184        &scores,
185        &flat_config,
186    )
187    .results)
188}
189
190/// Tree search: anchor retrieval + tree walk + path scoring + flat reranking.
191fn search_tree(
192    documents: &[Document],
193    fts_index: &FTS5Index,
194    config: &TreeSearchConfig,
195    query_mode: &QueryMode,
196) -> Result<Vec<SearchResult>> {
197    // Get FTS5 scores for all documents (single batch query)
198    let doc_ids: Vec<String> = documents.iter().map(|d| d.doc_id.clone()).collect();
199    let fts_score_map = if let Some(pattern) = &query_mode.regex_pattern {
200        let regex = compile_contains_regex(pattern)?;
201        documents
202            .iter()
203            .filter_map(|doc| {
204                let scores = regex_score_doc(doc, &regex);
205                if scores.is_empty() {
206                    None
207                } else {
208                    Some((doc.doc_id.clone(), scores))
209                }
210            })
211            .collect()
212    } else {
213        fts_index.score_nodes_batch_with_expr(
214            &query_mode.effective_query,
215            Some(&doc_ids),
216            0.6,
217            query_mode.fts_expression.as_deref(),
218        )?
219    };
220
221    Ok(candidate_search::search_with_scores(
222        &query_mode.effective_query,
223        documents,
224        &fts_score_map,
225        config,
226    )
227    .results)
228}
229
230#[cfg(test)]
231mod tests {
232    use super::{classify_query_mode, search, search_with_options};
233    use crate::config::{SearchMode, TreeSearchConfig};
234    use crate::document::{Document, Node, SourceType};
235    use crate::engine::fts::FTS5Index;
236
237    fn wildcard_documents() -> Vec<Document> {
238        let mut exact = Document::new("exact", "Exact Auth", SourceType::Text);
239        let mut exact_root = Node::new("0", "Exact Auth");
240        exact_root.summary = "Contains the exact auth token.".to_string();
241        exact_root.text = "Use auth tokens for API access.".to_string();
242        exact.structure.push(exact_root);
243
244        let mut prefix = Document::new("prefix", "Authentication Guide", SourceType::Text);
245        let mut prefix_root = Node::new("0", "Authentication");
246        prefix_root.summary = "Authentication and authorizer details.".to_string();
247        prefix_root.text = "Authentication depends on an authorizer service.".to_string();
248        prefix.structure.push(prefix_root);
249
250        let mut contains = Document::new("contains", "OAuth Guide", SourceType::Text);
251        let mut contains_root = Node::new("0", "OAuth");
252        contains_root.summary = "OAuth callback handling.".to_string();
253        contains_root.text = "OAuth callbacks must be validated.".to_string();
254        contains.structure.push(contains_root);
255
256        vec![exact, prefix, contains]
257    }
258
259    fn default_config() -> TreeSearchConfig {
260        TreeSearchConfig {
261            search_mode: SearchMode::Flat,
262            top_k_docs: 3,
263            max_nodes_per_doc: 5,
264            ..TreeSearchConfig::default()
265        }
266    }
267
268    #[test]
269    fn test_plain_query_preserves_exact_term_behavior() {
270        let index = FTS5Index::new(None, None).unwrap();
271        let docs = wildcard_documents();
272        for doc in &docs {
273            index.index_document(doc, false).unwrap();
274        }
275
276        let results = search("auth", &docs, &index, &default_config()).unwrap();
277        let doc_names: Vec<&str> = results.iter().map(|r| r.doc_name.as_str()).collect();
278
279        assert!(doc_names.contains(&"Exact Auth"));
280        assert!(!doc_names.contains(&"Authentication Guide"));
281        assert!(!doc_names.contains(&"OAuth Guide"));
282    }
283
284    #[test]
285    fn test_suffix_star_query_uses_prefix_matching() {
286        let index = FTS5Index::new(None, None).unwrap();
287        let docs = wildcard_documents();
288        for doc in &docs {
289            index.index_document(doc, false).unwrap();
290        }
291
292        let results = search("auth*", &docs, &index, &default_config()).unwrap();
293        let doc_names: Vec<&str> = results.iter().map(|r| r.doc_name.as_str()).collect();
294
295        assert!(doc_names.contains(&"Exact Auth"));
296        assert!(doc_names.contains(&"Authentication Guide"));
297        assert!(!doc_names.contains(&"OAuth Guide"));
298    }
299
300    #[test]
301    fn test_explicit_fts_expression_uses_prefix_matching() {
302        let index = FTS5Index::new(None, None).unwrap();
303        let docs = wildcard_documents();
304        for doc in &docs {
305            index.index_document(doc, false).unwrap();
306        }
307
308        let results = search_with_options(
309            "ignored",
310            &docs,
311            &index,
312            &default_config(),
313            Some("auth*"),
314            false,
315        )
316        .unwrap();
317        let doc_names: Vec<&str> = results.iter().map(|r| r.doc_name.as_str()).collect();
318
319        assert!(doc_names.contains(&"Exact Auth"));
320        assert!(doc_names.contains(&"Authentication Guide"));
321        assert!(!doc_names.contains(&"OAuth Guide"));
322    }
323
324    #[test]
325    fn test_surrounded_star_query_uses_contains_matching() {
326        let index = FTS5Index::new(None, None).unwrap();
327        let docs = wildcard_documents();
328        for doc in &docs {
329            index.index_document(doc, false).unwrap();
330        }
331
332        let results = search("*auth*", &docs, &index, &default_config()).unwrap();
333        let doc_names: Vec<&str> = results.iter().map(|r| r.doc_name.as_str()).collect();
334
335        assert!(doc_names.contains(&"Exact Auth"));
336        assert!(doc_names.contains(&"Authentication Guide"));
337        assert!(doc_names.contains(&"OAuth Guide"));
338    }
339
340    #[test]
341    fn test_explicit_regex_query_uses_regex_matching() {
342        let index = FTS5Index::new(None, None).unwrap();
343        let docs = wildcard_documents();
344        for doc in &docs {
345            index.index_document(doc, false).unwrap();
346        }
347
348        let results =
349            search_with_options("o?auth", &docs, &index, &default_config(), None, true).unwrap();
350        let doc_names: Vec<&str> = results.iter().map(|r| r.doc_name.as_str()).collect();
351
352        assert!(doc_names.contains(&"Exact Auth"));
353        assert!(doc_names.contains(&"Authentication Guide"));
354        assert!(doc_names.contains(&"OAuth Guide"));
355    }
356
357    #[test]
358    fn test_explicit_regex_invalid_pattern_returns_error() {
359        let index = FTS5Index::new(None, None).unwrap();
360        let docs = wildcard_documents();
361        for doc in &docs {
362            index.index_document(doc, false).unwrap();
363        }
364
365        let error =
366            search_with_options("(", &docs, &index, &default_config(), None, true).unwrap_err();
367
368        assert!(error.to_string().contains("regex parse error"));
369    }
370
371    #[test]
372    fn test_unsupported_wildcard_shape_falls_back_to_plain_query() {
373        let index = FTS5Index::new(None, None).unwrap();
374        let docs = wildcard_documents();
375        for doc in &docs {
376            index.index_document(doc, false).unwrap();
377        }
378
379        let results = search("au*th", &docs, &index, &default_config()).unwrap();
380        let doc_names: Vec<&str> = results.iter().map(|r| r.doc_name.as_str()).collect();
381        assert_eq!(doc_names, vec!["Exact Auth"]);
382    }
383
384    #[test]
385    fn test_cjk_punctuation_query_classification_is_utf8_safe() {
386        let mode = classify_query_mode("如何自行报价?", None, false);
387        assert_eq!(mode.effective_query, "如何自行报价?");
388        assert!(mode.fts_expression.is_none());
389        assert!(mode.regex_pattern.is_none());
390    }
391}