Skip to main content

treesearch/engine/
candidate_search.rs

1//! Runs tree traversal and final ranking from host-provided in-memory candidate scores.
2
3use std::collections::{HashMap, HashSet};
4
5use crate::config::{SearchMode, TreeSearchConfig};
6use crate::document::{Document, SearchResult};
7use crate::engine::tree_walker::{PathResult, TreeSearcher};
8
9/// Initial lexical or hybrid scores grouped by document ID and then node ID.
10pub type CandidateScoreMap = HashMap<String, HashMap<String, f64>>;
11
12/// One scored node candidate supplied by an external retrieval adapter.
13#[derive(Debug, Clone, PartialEq)]
14pub struct ScoredNodeCandidate {
15    /// Document identity matching [`Document::doc_id`].
16    pub doc_id: String,
17    /// Node identity within the document.
18    pub node_id: String,
19    /// Normalized retrieval score in `0.0..=1.0`.
20    pub score: f64,
21}
22
23impl ScoredNodeCandidate {
24    /// Creates one externally ranked candidate.
25    pub fn new(doc_id: impl Into<String>, node_id: impl Into<String>, score: f64) -> Self {
26        Self {
27            doc_id: doc_id.into(),
28            node_id: node_id.into(),
29            score,
30        }
31    }
32}
33
34/// Tree paths and flattened ranked nodes produced by one in-memory search.
35#[derive(Debug, Clone)]
36pub struct CandidateSearchOutcome {
37    /// Highest-ranked root-to-answer tree paths; empty in Flat mode.
38    pub paths: Vec<PathResult>,
39    /// Stable transport-ready node results after mode-specific ranking.
40    pub results: Vec<SearchResult>,
41}
42
43/// Validation failure returned by strict external-score entry points.
44#[derive(Debug, Clone, PartialEq, thiserror::Error)]
45pub enum CandidateSearchError {
46    #[error("candidate search query cannot be empty")]
47    EmptyQuery,
48    #[error("candidate references unknown document `{doc_id}`")]
49    UnknownDocument { doc_id: String },
50    #[error("candidate references unknown node `{node_id}` in document `{doc_id}`")]
51    UnknownNode { doc_id: String, node_id: String },
52    #[error("candidate score for `{doc_id}/{node_id}` must be finite and within 0..=1")]
53    InvalidScore { doc_id: String, node_id: String },
54    #[error("candidate `{doc_id}/{node_id}` occurs more than once")]
55    DuplicateCandidate { doc_id: String, node_id: String },
56    #[error("document ID `{doc_id}` occurs more than once")]
57    DuplicateDocument { doc_id: String },
58    #[error("document `{doc_id}` has an invalid structure: {reason}")]
59    InvalidDocument { doc_id: String, reason: String },
60    #[error("candidate search configuration field `{field}` is invalid")]
61    InvalidConfiguration { field: &'static str },
62}
63
64impl CandidateSearchOutcome {
65    /// Creates an empty outcome for an empty or invalid candidate set.
66    fn empty() -> Self {
67        Self {
68            paths: Vec::new(),
69            results: Vec::new(),
70        }
71    }
72}
73
74/// Searches a document forest using a host-provided nested score map.
75///
76/// Scores must be finite and positive. If any accepted value is above `1.0`,
77/// all accepted scores are divided by the global maximum, preserving cross-node
78/// and cross-document ordering. Unknown documents/nodes, zero/negative scores,
79/// and non-finite values are ignored. The documents may still contain zero-score
80/// ancestors: traversal reaches them through the tree.
81pub fn search_with_scores(
82    query: &str,
83    documents: &[Document],
84    scores: &CandidateScoreMap,
85    config: &TreeSearchConfig,
86) -> CandidateSearchOutcome {
87    let normalized = normalize_scores(documents, scores);
88    search_normalized(query, documents, &normalized, config)
89}
90
91/// Strictly validates a nested score map before running candidate search.
92///
93/// Unlike [`search_with_scores`], this returns an error for an empty query,
94/// unknown IDs, non-finite scores, negative scores, or scores above `1.0`.
95/// Zero-score ancestors are accepted and ignored as retrieval seeds.
96pub fn search_with_scores_strict(
97    query: &str,
98    documents: &[Document],
99    scores: &CandidateScoreMap,
100    config: &TreeSearchConfig,
101) -> Result<CandidateSearchOutcome, CandidateSearchError> {
102    validate_config(config)?;
103    validate_scores(query, documents, scores)?;
104    Ok(search_with_scores(query, documents, scores, config))
105}
106
107/// Searches from a flat candidate list, merging duplicate document/node pairs by maximum score.
108///
109/// This convenience API applies the same validation as [`search_with_scores`].
110pub fn search_with_candidates(
111    query: &str,
112    documents: &[Document],
113    candidates: &[ScoredNodeCandidate],
114    config: &TreeSearchConfig,
115) -> CandidateSearchOutcome {
116    let mut scores = CandidateScoreMap::new();
117    for candidate in candidates {
118        if !candidate.score.is_finite() || candidate.score <= 0.0 {
119            continue;
120        }
121        let score = candidate.score;
122        scores
123            .entry(candidate.doc_id.clone())
124            .or_default()
125            .entry(candidate.node_id.clone())
126            .and_modify(|current| *current = current.max(score))
127            .or_insert(score);
128    }
129    search_with_scores(query, documents, &scores, config)
130}
131
132/// Strictly validates a flat candidate list and rejects duplicate node identities.
133pub fn search_with_candidates_strict(
134    query: &str,
135    documents: &[Document],
136    candidates: &[ScoredNodeCandidate],
137    config: &TreeSearchConfig,
138) -> Result<CandidateSearchOutcome, CandidateSearchError> {
139    let mut identities = HashSet::new();
140    let mut scores = CandidateScoreMap::new();
141    for candidate in candidates {
142        let identity = (candidate.doc_id.clone(), candidate.node_id.clone());
143        if !identities.insert(identity) {
144            return Err(CandidateSearchError::DuplicateCandidate {
145                doc_id: candidate.doc_id.clone(),
146                node_id: candidate.node_id.clone(),
147            });
148        }
149        scores
150            .entry(candidate.doc_id.clone())
151            .or_default()
152            .insert(candidate.node_id.clone(), candidate.score);
153    }
154    search_with_scores_strict(query, documents, &scores, config)
155}
156
157/// Resolves Auto mode with the same hierarchy ratio used by the SQLite adapter.
158pub fn resolve_search_mode(mode: SearchMode, documents: &[Document]) -> SearchMode {
159    const MIN_TREE_DEPTH: u32 = 2;
160    const TREE_RATIO_THRESHOLD: f64 = 0.3;
161
162    if mode != SearchMode::Auto {
163        return mode;
164    }
165    if documents.is_empty() {
166        return SearchMode::Flat;
167    }
168    let tree_count = documents
169        .iter()
170        .filter(|document| {
171            let benefits_from_tree = matches!(
172                document.source_type,
173                crate::document::SourceType::Markdown
174                    | crate::document::SourceType::Json
175                    | crate::document::SourceType::Yaml
176                    | crate::document::SourceType::Toml
177                    | crate::document::SourceType::Html
178            );
179            benefits_from_tree && document.max_depth() >= MIN_TREE_DEPTH
180        })
181        .count();
182    let ratio = tree_count as f64 / documents.len() as f64;
183    if ratio >= TREE_RATIO_THRESHOLD {
184        SearchMode::Tree
185    } else {
186        SearchMode::Flat
187    }
188}
189
190/// Validates numeric policies that participate in score comparisons.
191fn validate_config(config: &TreeSearchConfig) -> Result<(), CandidateSearchError> {
192    for (field, value) in [
193        ("min_frontier_score", config.min_frontier_score),
194        ("early_stop_score", config.early_stop_score),
195    ] {
196        if !value.is_finite() || !(0.0..=1.0).contains(&value) {
197            return Err(CandidateSearchError::InvalidConfiguration { field });
198        }
199    }
200    if config.early_stop_score < config.min_frontier_score {
201        return Err(CandidateSearchError::InvalidConfiguration {
202            field: "early_stop_score",
203        });
204    }
205    Ok(())
206}
207
208/// Validates strict host-score invariants without mutating the caller's map.
209fn validate_scores(
210    query: &str,
211    documents: &[Document],
212    scores: &CandidateScoreMap,
213) -> Result<(), CandidateSearchError> {
214    if query.trim().is_empty() {
215        return Err(CandidateSearchError::EmptyQuery);
216    }
217    let mut known_documents: HashMap<&str, HashSet<&str>> = HashMap::new();
218    for document in documents {
219        if known_documents.contains_key(document.doc_id.as_str()) {
220            return Err(CandidateSearchError::DuplicateDocument {
221                doc_id: document.doc_id.clone(),
222            });
223        }
224        if let Err(error) = document.validate_structure() {
225            return Err(CandidateSearchError::InvalidDocument {
226                doc_id: document.doc_id.clone(),
227                reason: error.to_string(),
228            });
229        }
230        known_documents.insert(
231            document.doc_id.as_str(),
232            document
233                .flatten_nodes()
234                .into_iter()
235                .map(|node| node.node_id.as_str())
236                .collect(),
237        );
238    }
239    for (doc_id, node_scores) in scores {
240        let Some(known_nodes) = known_documents.get(doc_id.as_str()) else {
241            return Err(CandidateSearchError::UnknownDocument {
242                doc_id: doc_id.clone(),
243            });
244        };
245        for (node_id, score) in node_scores {
246            if !known_nodes.contains(node_id.as_str()) {
247                return Err(CandidateSearchError::UnknownNode {
248                    doc_id: doc_id.clone(),
249                    node_id: node_id.clone(),
250                });
251            }
252            if !score.is_finite() || *score < 0.0 || *score > 1.0 {
253                return Err(CandidateSearchError::InvalidScore {
254                    doc_id: doc_id.clone(),
255                    node_id: node_id.clone(),
256                });
257            }
258        }
259    }
260    Ok(())
261}
262
263/// Filters host scores to known nodes and normalizes the range expected by the scorer.
264fn normalize_scores(documents: &[Document], scores: &CandidateScoreMap) -> CandidateScoreMap {
265    let mut document_counts: HashMap<&str, usize> = HashMap::new();
266    for document in documents {
267        *document_counts.entry(document.doc_id.as_str()).or_default() += 1;
268    }
269    let known_documents: HashMap<&str, HashSet<&str>> = documents
270        .iter()
271        .filter(|document| {
272            document_counts.get(document.doc_id.as_str()) == Some(&1)
273                && document.validate_structure().is_ok()
274        })
275        .map(|document| {
276            (
277                document.doc_id.as_str(),
278                document
279                    .flatten_nodes()
280                    .into_iter()
281                    .map(|node| node.node_id.as_str())
282                    .collect(),
283            )
284        })
285        .collect();
286
287    let mut normalized: CandidateScoreMap = scores
288        .iter()
289        .filter_map(|(doc_id, node_scores)| {
290            let known_nodes = known_documents.get(doc_id.as_str())?;
291            let normalized: HashMap<String, f64> = node_scores
292                .iter()
293                .filter_map(|(node_id, score)| {
294                    if !known_nodes.contains(node_id.as_str())
295                        || !score.is_finite()
296                        || *score <= 0.0
297                    {
298                        return None;
299                    }
300                    Some((node_id.clone(), *score))
301                })
302                .collect();
303            (!normalized.is_empty()).then_some((doc_id.clone(), normalized))
304        })
305        .collect();
306    let global_max = normalized
307        .values()
308        .flat_map(HashMap::values)
309        .copied()
310        .fold(0.0_f64, f64::max);
311    if global_max > 1.0 {
312        for score in normalized.values_mut().flat_map(HashMap::values_mut) {
313            *score /= global_max;
314        }
315    }
316    normalized
317}
318
319/// Runs the existing tree walker and maps its output to the stable search-result contract.
320fn search_normalized(
321    query: &str,
322    documents: &[Document],
323    scores: &CandidateScoreMap,
324    config: &TreeSearchConfig,
325) -> CandidateSearchOutcome {
326    if query.trim().is_empty() || documents.is_empty() || scores.is_empty() {
327        return CandidateSearchOutcome::empty();
328    }
329
330    match resolve_search_mode(config.search_mode, documents) {
331        SearchMode::Flat => return flat_search(documents, scores, config),
332        SearchMode::Tree => {}
333        SearchMode::Auto => unreachable!("resolve_search_mode must return a concrete mode"),
334    }
335
336    let searcher = TreeSearcher::new(config);
337    let (paths, flat_nodes) = searcher.search(query, documents, scores);
338    let doc_map: HashMap<&str, &Document> = documents
339        .iter()
340        .map(|document| (document.doc_id.as_str(), document))
341        .collect();
342    let depth_maps: HashMap<&str, HashMap<String, u32>> = documents
343        .iter()
344        .map(|document| (document.doc_id.as_str(), document.build_depth_map()))
345        .collect();
346    let parent_maps: HashMap<&str, HashMap<String, Option<String>>> = documents
347        .iter()
348        .map(|document| (document.doc_id.as_str(), document.build_parent_map()))
349        .collect();
350    let node_maps: HashMap<&str, HashMap<&str, &crate::document::Node>> = documents
351        .iter()
352        .map(|document| (document.doc_id.as_str(), document.build_node_map()))
353        .collect();
354    let top_k = config.max_nodes_per_doc.saturating_mul(config.top_k_docs);
355    let mut results: Vec<SearchResult> = flat_nodes
356        .into_iter()
357        .filter_map(|flat| {
358            let document = doc_map.get(flat.doc_id.as_str())?;
359            let node_map = node_maps.get(flat.doc_id.as_str())?;
360            let node = node_map.get(flat.node_id.as_str())?;
361            let breadcrumb = breadcrumb_titles(
362                &flat.node_id,
363                parent_maps.get(flat.doc_id.as_str())?,
364                node_map,
365            );
366            let depth = depth_maps
367                .get(flat.doc_id.as_str())
368                .and_then(|depths| depths.get(&flat.node_id))
369                .copied()
370                .unwrap_or(0);
371            Some(SearchResult {
372                node_id: flat.node_id,
373                doc_id: flat.doc_id,
374                doc_name: flat.doc_name,
375                title: flat.title,
376                summary: node.summary.clone(),
377                text: bounded_result_text(&node.text, config.max_result_chars),
378                source_type: document.source_type.to_string(),
379                source_path: document.source_path.clone(),
380                line_start: node.line_start,
381                line_end: node.line_end,
382                score: flat.score,
383                depth,
384                breadcrumb,
385            })
386        })
387        .collect();
388
389    for path in &paths {
390        if results
391            .iter()
392            .any(|result| result.doc_id == path.doc_id && result.node_id == path.target_node_id)
393        {
394            continue;
395        }
396        let Some(document) = doc_map.get(path.doc_id.as_str()) else {
397            continue;
398        };
399        let Some(node) = node_maps
400            .get(path.doc_id.as_str())
401            .and_then(|nodes| nodes.get(path.target_node_id.as_str()))
402        else {
403            continue;
404        };
405        results.push(SearchResult {
406            node_id: path.target_node_id.clone(),
407            doc_id: path.doc_id.clone(),
408            doc_name: path.doc_name.clone(),
409            title: node.title.clone(),
410            summary: node.summary.clone(),
411            text: bounded_result_text(&node.text, config.max_result_chars),
412            source_type: document.source_type.to_string(),
413            source_path: document.source_path.clone(),
414            line_start: node.line_start,
415            line_end: node.line_end,
416            score: path.score,
417            depth: depth_maps
418                .get(path.doc_id.as_str())
419                .and_then(|depths| depths.get(&path.target_node_id))
420                .copied()
421                .unwrap_or(0),
422            breadcrumb: path.path.iter().map(|item| item.title.clone()).collect(),
423        });
424    }
425
426    results.sort_by(|left, right| {
427        right
428            .score
429            .total_cmp(&left.score)
430            .then_with(|| left.doc_id.cmp(&right.doc_id))
431            .then_with(|| left.node_id.cmp(&right.node_id))
432    });
433    limit_ranked_results(&mut results, config);
434    let returned_targets: HashSet<(&str, &str)> = results
435        .iter()
436        .map(|result| (result.doc_id.as_str(), result.node_id.as_str()))
437        .collect();
438    let paths = paths
439        .into_iter()
440        .filter(|path| {
441            returned_targets.contains(&(path.doc_id.as_str(), path.target_node_id.as_str()))
442        })
443        .collect();
444    debug_assert!(results.len() <= top_k);
445    CandidateSearchOutcome { paths, results }
446}
447
448/// Maps host-ranked nodes directly into the stable result contract for Flat mode.
449fn flat_search(
450    documents: &[Document],
451    scores: &CandidateScoreMap,
452    config: &TreeSearchConfig,
453) -> CandidateSearchOutcome {
454    let mut results = Vec::new();
455    for document in documents {
456        let Some(node_scores) = scores.get(&document.doc_id) else {
457            continue;
458        };
459        let depth_map = document.build_depth_map();
460        let parent_map = document.build_parent_map();
461        let node_map = document.build_node_map();
462        for (node_id, score) in node_scores {
463            let Some(node) = node_map.get(node_id.as_str()) else {
464                continue;
465            };
466            let breadcrumb = breadcrumb_titles(node_id, &parent_map, &node_map);
467            results.push(SearchResult {
468                node_id: node_id.clone(),
469                doc_id: document.doc_id.clone(),
470                doc_name: document.doc_name.clone(),
471                title: node.title.clone(),
472                summary: node.summary.clone(),
473                text: bounded_result_text(&node.text, config.max_result_chars),
474                source_type: document.source_type.to_string(),
475                source_path: document.source_path.clone(),
476                line_start: node.line_start,
477                line_end: node.line_end,
478                score: *score,
479                depth: depth_map.get(node_id).copied().unwrap_or(0),
480                breadcrumb,
481            });
482        }
483    }
484    results.sort_by(|left, right| {
485        right
486            .score
487            .total_cmp(&left.score)
488            .then_with(|| left.doc_id.cmp(&right.doc_id))
489            .then_with(|| left.node_id.cmp(&right.node_id))
490    });
491    limit_ranked_results(&mut results, config);
492    CandidateSearchOutcome {
493        paths: Vec::new(),
494        results,
495    }
496}
497
498/// Resolves one breadcrumb from prebuilt maps in O(depth), with cycle defense.
499fn breadcrumb_titles(
500    node_id: &str,
501    parent_map: &HashMap<String, Option<String>>,
502    node_map: &HashMap<&str, &crate::document::Node>,
503) -> Vec<String> {
504    let mut titles = Vec::new();
505    let mut visited = HashSet::new();
506    let mut current = Some(node_id);
507    while let Some(current_id) = current {
508        if !visited.insert(current_id) {
509            return Vec::new();
510        }
511        let Some(node) = node_map.get(current_id) else {
512            return Vec::new();
513        };
514        titles.push(node.title.clone());
515        current = parent_map
516            .get(current_id)
517            .and_then(|parent| parent.as_deref());
518    }
519    titles.reverse();
520    titles
521}
522
523/// Enforces both the distinct-document and per-document result limits.
524fn limit_ranked_results(results: &mut Vec<SearchResult>, config: &TreeSearchConfig) {
525    if config.top_k_docs == 0 || config.max_nodes_per_doc == 0 {
526        results.clear();
527        return;
528    }
529    let mut selected_documents = HashSet::new();
530    let mut per_document = HashMap::<String, usize>::new();
531    results.retain(|result| {
532        if !selected_documents.contains(&result.doc_id)
533            && selected_documents.len() >= config.top_k_docs
534        {
535            return false;
536        }
537        let count = per_document.entry(result.doc_id.clone()).or_default();
538        if *count >= config.max_nodes_per_doc {
539            return false;
540        }
541        selected_documents.insert(result.doc_id.clone());
542        *count += 1;
543        true
544    });
545}
546
547/// Copies a result body up to a UTF-8-safe character limit.
548fn bounded_result_text(text: &str, max_characters: usize) -> String {
549    match text.char_indices().nth(max_characters) {
550        Some((end, _)) => text[..end].to_string(),
551        None => text.to_string(),
552    }
553}
554
555#[cfg(test)]
556mod tests {
557    use super::*;
558    use crate::document::{Node, SourceType};
559
560    /// Builds one nested document for candidate-search behavior tests.
561    fn nested_document() -> Document {
562        let mut document = Document::new("guide", "Guide", SourceType::Markdown);
563        let mut root = Node::new("root", "Root");
564        root.text = "General introduction".into();
565        let mut section = Node::new("section", "Authentication");
566        section.text = "Authentication overview".into();
567        let mut leaf = Node::new("leaf", "Token validation");
568        leaf.text = "Validate bearer tokens before serving protected data.".into();
569        section.children.push(leaf);
570        root.children.push(section);
571        document.structure.push(root);
572        document
573    }
574
575    /// Uses deterministic tree-search limits shared by these tests.
576    fn tree_config() -> TreeSearchConfig {
577        TreeSearchConfig {
578            top_k_docs: 1,
579            max_nodes_per_doc: 5,
580            anchor_top_k: 3,
581            path_top_k: 3,
582            ..TreeSearchConfig::default()
583        }
584    }
585
586    #[test]
587    fn scored_leaf_produces_root_to_leaf_path() {
588        let document = nested_document();
589        let candidates = [ScoredNodeCandidate::new("guide", "leaf", 0.9)];
590        let mut config = tree_config();
591        config.search_mode = SearchMode::Tree;
592        let outcome =
593            search_with_candidates("validate bearer tokens", &[document], &candidates, &config);
594
595        assert!(!outcome.results.is_empty());
596        assert!(outcome.paths.iter().any(|path| {
597            path.path
598                .iter()
599                .map(|item| item.node_id.as_str())
600                .eq(["root", "section", "leaf"])
601        }));
602    }
603
604    #[test]
605    fn empty_unknown_and_non_finite_candidates_are_ignored() {
606        let document = nested_document();
607        let candidates = [
608            ScoredNodeCandidate::new("missing", "leaf", 1.0),
609            ScoredNodeCandidate::new("guide", "missing", 1.0),
610            ScoredNodeCandidate::new("guide", "leaf", f64::NAN),
611            ScoredNodeCandidate::new("guide", "leaf", f64::INFINITY),
612            ScoredNodeCandidate::new("guide", "leaf", 0.0),
613            ScoredNodeCandidate::new("guide", "leaf", -1.0),
614        ];
615
616        let outcome = search_with_candidates("tokens", &[document], &candidates, &tree_config());
617        assert!(outcome.paths.is_empty());
618        assert!(outcome.results.is_empty());
619    }
620
621    #[test]
622    fn duplicate_candidates_keep_the_highest_score_once() {
623        let document = nested_document();
624        let duplicates = [
625            ScoredNodeCandidate::new("guide", "leaf", 0.2),
626            ScoredNodeCandidate::new("guide", "leaf", 0.9),
627            ScoredNodeCandidate::new("guide", "leaf", 0.4),
628        ];
629        let single = [ScoredNodeCandidate::new("guide", "leaf", 0.9)];
630
631        let duplicate_outcome = search_with_candidates(
632            "tokens",
633            std::slice::from_ref(&document),
634            &duplicates,
635            &tree_config(),
636        );
637        let single_outcome = search_with_candidates("tokens", &[document], &single, &tree_config());
638        let duplicate_pairs: Vec<(&str, &str, f64)> = duplicate_outcome
639            .results
640            .iter()
641            .map(|result| {
642                (
643                    result.doc_id.as_str(),
644                    result.node_id.as_str(),
645                    result.score,
646                )
647            })
648            .collect();
649        let single_pairs: Vec<(&str, &str, f64)> = single_outcome
650            .results
651            .iter()
652            .map(|result| {
653                (
654                    result.doc_id.as_str(),
655                    result.node_id.as_str(),
656                    result.score,
657                )
658            })
659            .collect();
660
661        assert_eq!(duplicate_pairs, single_pairs);
662    }
663
664    #[test]
665    fn flat_mode_maps_only_supplied_candidates_without_paths() {
666        let document = nested_document();
667        let candidates = [ScoredNodeCandidate::new("guide", "leaf", 0.9)];
668        let mut config = tree_config();
669        config.search_mode = SearchMode::Flat;
670
671        let outcome = search_with_candidates("tokens", &[document], &candidates, &config);
672
673        assert!(outcome.paths.is_empty());
674        assert_eq!(outcome.results.len(), 1);
675        assert_eq!(outcome.results[0].node_id, "leaf");
676        assert_eq!(outcome.results[0].depth, 2);
677    }
678
679    #[test]
680    fn auto_mode_uses_hierarchy_and_source_type() {
681        let nested = nested_document();
682        let mut plain = Document::new("plain", "Plain", SourceType::Text);
683        plain.structure.push(Node::new("only", "Only node"));
684        let config = tree_config();
685
686        assert_eq!(
687            resolve_search_mode(SearchMode::Auto, std::slice::from_ref(&nested)),
688            SearchMode::Tree
689        );
690        assert_eq!(
691            resolve_search_mode(SearchMode::Auto, std::slice::from_ref(&plain)),
692            SearchMode::Flat
693        );
694
695        let nested_outcome = search_with_candidates(
696            "tokens",
697            &[nested],
698            &[ScoredNodeCandidate::new("guide", "leaf", 0.9)],
699            &config,
700        );
701        let plain_outcome = search_with_candidates(
702            "only",
703            &[plain],
704            &[ScoredNodeCandidate::new("plain", "only", 0.9)],
705            &config,
706        );
707        assert!(!nested_outcome.paths.is_empty());
708        assert!(plain_outcome.paths.is_empty());
709        assert_eq!(plain_outcome.results.len(), 1);
710    }
711
712    #[test]
713    fn strict_scores_accept_zero_ancestors_and_reject_invalid_ids_and_values() {
714        let document = nested_document();
715        let mut config = tree_config();
716        config.search_mode = SearchMode::Tree;
717        let valid = CandidateScoreMap::from([(
718            "guide".to_string(),
719            HashMap::from([
720                ("root".to_string(), 0.0),
721                ("section".to_string(), 0.0),
722                ("leaf".to_string(), 0.9),
723            ]),
724        )]);
725        let valid_outcome =
726            search_with_scores_strict("tokens", std::slice::from_ref(&document), &valid, &config)
727                .expect("valid strict scores");
728        assert!(valid_outcome
729            .results
730            .iter()
731            .all(|result| result.score.is_finite() && (0.0..=1.0).contains(&result.score)));
732
733        let unknown = CandidateScoreMap::from([(
734            "guide".to_string(),
735            HashMap::from([("missing".to_string(), 0.5)]),
736        )]);
737        assert!(matches!(
738            search_with_scores_strict("tokens", std::slice::from_ref(&document), &unknown, &config),
739            Err(CandidateSearchError::UnknownNode { .. })
740        ));
741
742        let invalid = CandidateScoreMap::from([(
743            "guide".to_string(),
744            HashMap::from([("leaf".to_string(), f64::NAN)]),
745        )]);
746        assert!(matches!(
747            search_with_scores_strict("tokens", &[document], &invalid, &config),
748            Err(CandidateSearchError::InvalidScore { .. })
749        ));
750    }
751
752    #[test]
753    fn strict_candidates_reject_duplicates() {
754        let document = nested_document();
755        let duplicates = [
756            ScoredNodeCandidate::new("guide", "leaf", 0.2),
757            ScoredNodeCandidate::new("guide", "leaf", 0.9),
758        ];
759
760        assert!(matches!(
761            search_with_candidates_strict("tokens", &[document], &duplicates, &tree_config()),
762            Err(CandidateSearchError::DuplicateCandidate { .. })
763        ));
764    }
765
766    #[test]
767    fn lenient_raw_scores_are_globally_calibrated_without_losing_order() {
768        let document = nested_document();
769        let mut config = tree_config();
770        config.search_mode = SearchMode::Flat;
771        let candidates = [
772            ScoredNodeCandidate::new("guide", "section", 20.0),
773            ScoredNodeCandidate::new("guide", "leaf", 10.0),
774        ];
775
776        let outcome = search_with_candidates("tokens", &[document], &candidates, &config);
777        assert_eq!(outcome.results[0].node_id, "section");
778        assert_eq!(outcome.results[0].score, 1.0);
779        assert_eq!(outcome.results[1].score, 0.5);
780    }
781
782    #[test]
783    fn strict_search_rejects_duplicate_document_and_node_identities() {
784        let document = nested_document();
785        let scores = CandidateScoreMap::from([(
786            "guide".to_string(),
787            HashMap::from([("leaf".to_string(), 0.9)]),
788        )]);
789        assert!(matches!(
790            search_with_scores_strict(
791                "tokens",
792                &[document.clone(), document.clone()],
793                &scores,
794                &tree_config(),
795            ),
796            Err(CandidateSearchError::DuplicateDocument { .. })
797        ));
798
799        let mut duplicate_node = document;
800        duplicate_node.structure[0].children[0].node_id = "root".into();
801        assert!(matches!(
802            search_with_scores_strict("tokens", &[duplicate_node], &scores, &tree_config()),
803            Err(CandidateSearchError::InvalidDocument { .. })
804        ));
805    }
806
807    #[test]
808    fn result_limits_apply_per_document_with_stable_ties() {
809        let first = nested_document();
810        let mut second = nested_document();
811        second.doc_id = "second".into();
812        second.doc_name = "Second".into();
813        let candidates = [
814            ScoredNodeCandidate::new("guide", "section", 0.9),
815            ScoredNodeCandidate::new("guide", "leaf", 0.9),
816            ScoredNodeCandidate::new("second", "section", 0.9),
817            ScoredNodeCandidate::new("second", "leaf", 0.9),
818        ];
819        let mut config = tree_config();
820        config.search_mode = SearchMode::Flat;
821        config.top_k_docs = 1;
822        config.max_nodes_per_doc = 1;
823
824        for candidates in [candidates.to_vec(), candidates.into_iter().rev().collect()] {
825            let outcome = search_with_candidates(
826                "tokens",
827                &[first.clone(), second.clone()],
828                &candidates,
829                &config,
830            );
831            assert_eq!(outcome.results.len(), 1);
832            assert_eq!(outcome.results[0].doc_id, "guide");
833            assert_eq!(outcome.results[0].node_id, "leaf");
834        }
835    }
836
837    #[test]
838    fn strict_search_rejects_non_finite_thresholds() {
839        let document = nested_document();
840        let scores = CandidateScoreMap::from([(
841            "guide".to_string(),
842            HashMap::from([("leaf".to_string(), 0.9)]),
843        )]);
844        let mut config = tree_config();
845        config.min_frontier_score = f64::NAN;
846        assert!(matches!(
847            search_with_scores_strict("tokens", &[document], &scores, &config),
848            Err(CandidateSearchError::InvalidConfiguration {
849                field: "min_frontier_score"
850            })
851        ));
852    }
853
854    #[test]
855    fn tree_paths_use_the_actual_anchor_and_utf8_safe_snippets() {
856        let mut document = nested_document();
857        document.structure[0].children[0].children[0].text = "报价".repeat(200);
858        let candidates = [ScoredNodeCandidate::new("guide", "leaf", 0.9)];
859        let mut config = tree_config();
860        config.search_mode = SearchMode::Tree;
861        config.early_stop_score = 1.0;
862
863        let outcome = search_with_candidates("报价", &[document], &candidates, &config);
864        let leaf_path = outcome
865            .paths
866            .iter()
867            .find(|path| path.target_node_id == "leaf")
868            .expect("leaf path");
869        assert_eq!(leaf_path.anchor_node_id, "leaf");
870        assert_eq!(leaf_path.snippet.chars().count(), 300);
871    }
872
873    #[test]
874    fn result_text_respects_utf8_character_limit() {
875        let mut document = nested_document();
876        document.structure[0].children[0].children[0].text = "证据".repeat(20);
877        let mut config = tree_config();
878        config.search_mode = SearchMode::Flat;
879        config.max_result_chars = 7;
880        let outcome = search_with_candidates(
881            "证据",
882            &[document],
883            &[ScoredNodeCandidate::new("guide", "leaf", 0.9)],
884            &config,
885        );
886        assert_eq!(outcome.results[0].text.chars().count(), 7);
887        assert_eq!(outcome.results[0].text, "证据证据证据证");
888    }
889
890    #[test]
891    fn tree_ranking_is_stable_across_document_and_candidate_orders() {
892        let first = nested_document();
893        let mut second = nested_document();
894        second.doc_id = "second".into();
895        second.doc_name = "Second".into();
896        let candidates = vec![
897            ScoredNodeCandidate::new("guide", "leaf", 0.8),
898            ScoredNodeCandidate::new("second", "leaf", 0.8),
899        ];
900        let mut config = tree_config();
901        config.search_mode = SearchMode::Tree;
902        config.top_k_docs = 2;
903        config.path_top_k = 4;
904
905        let mut expected = None;
906        for (documents, candidates) in [
907            (vec![first.clone(), second.clone()], candidates.clone()),
908            (
909                vec![second.clone(), first.clone()],
910                candidates.iter().cloned().rev().collect(),
911            ),
912        ] {
913            let outcome = search_with_candidates("tokens", &documents, &candidates, &config);
914            let projection = (
915                outcome
916                    .results
917                    .iter()
918                    .map(|result| (result.doc_id.clone(), result.node_id.clone(), result.score))
919                    .collect::<Vec<_>>(),
920                outcome
921                    .paths
922                    .iter()
923                    .map(|path| {
924                        (
925                            path.doc_id.clone(),
926                            path.anchor_node_id.clone(),
927                            path.target_node_id.clone(),
928                            path.score,
929                        )
930                    })
931                    .collect::<Vec<_>>(),
932            );
933            if let Some(expected) = &expected {
934                assert_eq!(&projection, expected);
935            } else {
936                expected = Some(projection);
937            }
938        }
939    }
940
941    #[test]
942    #[ignore = "explicit local scalability baseline"]
943    fn benchmark_large_candidate_forest() {
944        let mut documents = Vec::new();
945        let mut candidates = Vec::new();
946        for document_index in 0..100 {
947            let doc_id = format!("doc-{document_index:03}");
948            let mut document = Document::new(&doc_id, &doc_id, SourceType::Markdown);
949            let mut root = Node::new("root", "Knowledge base");
950            for node_index in 0..20 {
951                let node_id = format!("node-{node_index:02}");
952                let mut node = Node::new(&node_id, format!("Section {node_index}"));
953                node.text = format!(
954                    "bounded retrieval evidence for document {document_index} node {node_index}"
955                );
956                root.children.push(node);
957                candidates.push(ScoredNodeCandidate::new(
958                    &doc_id,
959                    node_id,
960                    (node_index + 1) as f64,
961                ));
962            }
963            document.structure.push(root);
964            documents.push(document);
965        }
966        let mut config = tree_config();
967        config.search_mode = SearchMode::Tree;
968        config.top_k_docs = 10;
969        config.max_nodes_per_doc = 5;
970        let iterations = 100;
971        let started = std::time::Instant::now();
972        for _ in 0..iterations {
973            let outcome = search_with_candidates(
974                "bounded retrieval evidence",
975                &documents,
976                &candidates,
977                &config,
978            );
979            assert!(!outcome.results.is_empty());
980        }
981        let elapsed = started.elapsed();
982        eprintln!(
983            "candidate_search docs=100 nodes=2000 iterations={iterations} avg_ms={:.3}",
984            elapsed.as_secs_f64() * 1000.0 / iterations as f64
985        );
986    }
987
988    #[cfg(feature = "sqlite-fts")]
989    #[test]
990    fn in_memory_scores_match_sqlite_adapter_in_flat_and_tree_modes() {
991        use crate::config::SearchMode;
992        use crate::engine::{fts::FTS5Index, search};
993
994        let document = nested_document();
995        let documents = vec![document];
996        let index = FTS5Index::new(None, None).expect("in-memory FTS index");
997        for document in &documents {
998            index
999                .index_document(document, false)
1000                .expect("index test document");
1001        }
1002        let doc_ids = vec!["guide".to_string()];
1003        for mode in [SearchMode::Flat, SearchMode::Tree] {
1004            let scores = index
1005                .score_nodes_batch_with_expr(
1006                    "tokens",
1007                    Some(&doc_ids),
1008                    if mode == SearchMode::Tree { 0.6 } else { 0.0 },
1009                    None,
1010                )
1011                .expect("score test candidates");
1012            let mut config = tree_config();
1013            config.search_mode = mode;
1014            let sqlite = search::search("tokens", &documents, &index, &config)
1015                .expect("SQLite-backed search");
1016            let in_memory = search_with_scores("tokens", &documents, &scores, &config);
1017            let sqlite_projection: Vec<(&str, &str, f64)> = sqlite
1018                .iter()
1019                .map(|result| {
1020                    (
1021                        result.doc_id.as_str(),
1022                        result.node_id.as_str(),
1023                        result.score,
1024                    )
1025                })
1026                .collect();
1027            let memory_projection: Vec<(&str, &str, f64)> = in_memory
1028                .results
1029                .iter()
1030                .map(|result| {
1031                    (
1032                        result.doc_id.as_str(),
1033                        result.node_id.as_str(),
1034                        result.score,
1035                    )
1036                })
1037                .collect();
1038
1039            assert_eq!(memory_projection, sqlite_projection, "mode={mode:?}");
1040        }
1041    }
1042}