1use std::collections::{HashMap, HashSet};
4
5use crate::config::{SearchMode, TreeSearchConfig};
6use crate::document::{Document, SearchResult};
7use crate::engine::tree_walker::{PathResult, TreeSearcher};
8
9pub type CandidateScoreMap = HashMap<String, HashMap<String, f64>>;
11
12#[derive(Debug, Clone, PartialEq)]
14pub struct ScoredNodeCandidate {
15 pub doc_id: String,
17 pub node_id: String,
19 pub score: f64,
21}
22
23impl ScoredNodeCandidate {
24 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#[derive(Debug, Clone)]
36pub struct CandidateSearchOutcome {
37 pub paths: Vec<PathResult>,
39 pub results: Vec<SearchResult>,
41}
42
43#[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 fn empty() -> Self {
67 Self {
68 paths: Vec::new(),
69 results: Vec::new(),
70 }
71 }
72}
73
74pub 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
91pub 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
107pub 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
132pub 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
157pub 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
190fn 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
208fn 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
263fn 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
319fn 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
448fn 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
498fn 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
523fn 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
547fn 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 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 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}