1use std::collections::{BinaryHeap, HashMap, HashSet};
9
10use crate::config::TreeSearchConfig;
11use crate::document::{Document, Node};
12use crate::scorer::heuristics::{
13 build_query_plan_with_mode, check_phrase_match, check_title_match, compute_term_overlap,
14 estimate_idf, is_generic_section, score_anchor, score_path, score_walk_node_with_input,
15 QueryPlan, WalkScoreInput,
16};
17
18#[derive(Debug, Clone)]
20pub struct SearchState {
21 pub doc_id: String,
22 pub node_id: String,
23 pub score: f64,
24 pub hop: usize,
25 pub source: String,
26 pub path: Vec<String>,
27 pub max_ancestor_score: f64,
28 pub anchor_node_id: String,
30}
31
32impl PartialEq for SearchState {
33 fn eq(&self, other: &Self) -> bool {
34 self.cmp(other) == std::cmp::Ordering::Equal
35 }
36}
37impl Eq for SearchState {}
38
39impl PartialOrd for SearchState {
40 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
41 Some(self.cmp(other))
42 }
43}
44impl Ord for SearchState {
45 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
46 self.score
48 .total_cmp(&other.score)
49 .then_with(|| other.hop.cmp(&self.hop))
50 .then_with(|| other.doc_id.cmp(&self.doc_id))
51 .then_with(|| other.node_id.cmp(&self.node_id))
52 .then_with(|| self.max_ancestor_score.total_cmp(&other.max_ancestor_score))
53 .then_with(|| other.anchor_node_id.cmp(&self.anchor_node_id))
54 .then_with(|| other.source.cmp(&self.source))
55 .then_with(|| other.path.cmp(&self.path))
56 }
57}
58
59#[derive(Debug, Clone)]
61pub struct PathResult {
62 pub doc_id: String,
63 pub doc_name: String,
64 pub score: f64,
65 pub anchor_node_id: String,
66 pub target_node_id: String,
67 pub path: Vec<PathNode>,
68 pub snippet: String,
69}
70
71#[derive(Debug, Clone)]
72pub struct PathNode {
73 pub node_id: String,
74 pub title: String,
75}
76
77#[derive(Debug, Clone)]
79pub struct FlatNode {
80 pub node_id: String,
81 pub doc_id: String,
82 pub doc_name: String,
83 pub title: String,
84 pub score: f64,
85 pub text: String,
86}
87
88pub struct TreeSearcher<'a> {
90 config: &'a TreeSearchConfig,
91}
92
93struct DocumentTreeIndex<'a> {
95 document: &'a Document,
96 nodes: HashMap<&'a str, &'a Node>,
97 parents: HashMap<String, Option<String>>,
98 children: HashMap<String, Vec<String>>,
99 depths: HashMap<String, u32>,
100}
101
102impl<'a> DocumentTreeIndex<'a> {
103 fn new(document: &'a Document) -> Self {
105 Self {
106 document,
107 nodes: document.build_node_map(),
108 parents: document.build_parent_map(),
109 children: document.build_children_map(),
110 depths: document.build_depth_map(),
111 }
112 }
113
114 fn node(&self, node_id: &str) -> Option<&'a Node> {
116 self.nodes.get(node_id).copied()
117 }
118}
119
120impl<'a> TreeSearcher<'a> {
121 pub fn new(config: &'a TreeSearchConfig) -> Self {
122 Self { config }
123 }
124
125 pub fn search(
127 &self,
128 query: &str,
129 documents: &[Document],
130 initial_score_map: &HashMap<String, HashMap<String, f64>>,
131 ) -> (Vec<PathResult>, Vec<FlatNode>) {
132 let normalized_scores = initial_score_map
133 .values()
134 .flat_map(HashMap::values)
135 .any(|score| !score.is_finite() || *score <= 0.0 || *score > 1.0)
136 .then(|| normalize_initial_scores(initial_score_map));
137 let initial_score_map = normalized_scores.as_ref().unwrap_or(initial_score_map);
138 let plan = build_query_plan_with_mode(query, self.config.cjk_tokenizer);
139 let mut all_paths: Vec<PathResult> = Vec::new();
140 let mut all_walked_nodes: Vec<(String, String, f64, f64, usize)> = Vec::new();
141 let indexes: Vec<DocumentTreeIndex<'_>> =
142 documents.iter().map(DocumentTreeIndex::new).collect();
143
144 let mut scored_docs: Vec<(f64, &DocumentTreeIndex<'_>, &HashMap<String, f64>)> = indexes
146 .iter()
147 .filter_map(|index| {
148 let scores = initial_score_map.get(&index.document.doc_id)?;
149 if scores.is_empty() {
150 return None;
151 }
152 let max_score = scores.values().cloned().fold(0.0_f64, f64::max);
153 Some((max_score, index, scores))
154 })
155 .collect();
156 scored_docs.sort_by(|left, right| {
157 right
158 .0
159 .total_cmp(&left.0)
160 .then_with(|| left.1.document.doc_id.cmp(&right.1.document.doc_id))
161 });
162 scored_docs.truncate(self.config.top_k_docs);
163
164 for (_, index, doc_scores) in &scored_docs {
165 let idf = if !plan.terms.is_empty() && index.nodes.len() > 20 && doc_scores.len() >= 5 {
167 let corpus: Vec<&str> = index
168 .nodes
169 .values()
170 .map(|node| bounded_prefix(&node.text, self.config.max_node_chars))
171 .collect();
172 Some(estimate_idf(&plan.terms, &corpus))
173 } else {
174 None
175 };
176
177 let anchors = self.select_anchors(index, doc_scores, &plan, idf.as_ref());
179 if anchors.is_empty() {
180 continue;
181 }
182
183 let (doc_paths, walked_states) =
185 self.tree_walk(index, &anchors, doc_scores, &plan, idf.as_ref());
186 all_paths.extend(doc_paths);
187
188 for state in &walked_states {
189 let initial_score = doc_scores.get(&state.node_id).copied().unwrap_or(0.0);
190 let combined = 0.3 * state.score + 0.7 * initial_score;
191 all_walked_nodes.push((
192 index.document.doc_id.clone(),
193 state.node_id.clone(),
194 combined,
195 initial_score,
196 state.hop,
197 ));
198 }
199 }
200
201 all_paths.sort_by(compare_paths);
203 all_paths.truncate(self.config.path_top_k);
204
205 let document_indexes: HashMap<&str, &DocumentTreeIndex<'_>> = indexes
207 .iter()
208 .map(|index| (index.document.doc_id.as_str(), index))
209 .collect();
210 let flat_nodes = self.build_flat_nodes(
211 &all_paths,
212 &all_walked_nodes,
213 &document_indexes,
214 initial_score_map,
215 &plan,
216 );
217
218 (all_paths, flat_nodes)
219 }
220
221 fn select_anchors(
226 &self,
227 index: &DocumentTreeIndex<'_>,
228 doc_scores: &HashMap<String, f64>,
229 plan: &QueryPlan,
230 idf: Option<&HashMap<String, f64>>,
231 ) -> Vec<SearchState> {
232 let max_candidates = self.config.anchor_top_k.saturating_mul(3);
233 let threshold = if doc_scores.len() > max_candidates {
234 let mut scores: Vec<f64> = doc_scores.values().copied().collect();
235 scores.sort_by(|left, right| right.total_cmp(left));
236 scores
237 .get(max_candidates.saturating_sub(1))
238 .copied()
239 .unwrap_or(0.0)
240 } else {
241 0.0
242 };
243
244 let mut candidates: Vec<(f64, String, &Node)> = Vec::new();
245 for (nid, &initial_score) in doc_scores {
246 if initial_score < threshold {
247 continue;
248 }
249 let node = match index.node(nid) {
250 Some(n) => n,
251 None => continue,
252 };
253 let depth = index.depths.get(nid).copied().unwrap_or(0);
254 let node_text = bounded_prefix(&node.text, self.config.max_node_chars);
255 let full_text = format!("{} {}", node.title, node_text);
256 let a_score = score_anchor(
257 initial_score,
258 depth,
259 check_title_match(&node.title, &plan.terms),
260 check_phrase_match(&full_text, &plan.phrases),
261 compute_term_overlap(node_text, &plan.terms, idf),
262 6,
263 );
264 candidates.push((a_score, nid.clone(), node));
265 }
266
267 candidates.sort_by(|left, right| {
268 right
269 .0
270 .total_cmp(&left.0)
271 .then_with(|| left.1.cmp(&right.1))
272 });
273
274 let mut selected: Vec<SearchState> = Vec::new();
275 let mut selected_paths: HashSet<String> = HashSet::new();
276
277 let anchor_limit = self.config.anchor_top_k.min(self.config.max_anchor_per_doc);
278 for (a_score, nid, _node) in &candidates {
279 if selected.len() >= anchor_limit {
280 break;
281 }
282 let path_to_root = path_to_root_via_map(nid, &index.parents);
283 let path_key = path_to_root
284 .iter()
285 .take(3)
286 .cloned()
287 .collect::<Vec<_>>()
288 .join(">");
289 if selected_paths.contains(&path_key) {
290 continue;
291 }
292 selected_paths.insert(path_key);
293
294 selected.push(SearchState {
295 doc_id: index.document.doc_id.clone(),
296 node_id: nid.clone(),
297 score: *a_score,
298 hop: 0,
299 source: "anchor".into(),
300 path: path_to_root,
301 max_ancestor_score: maximum_ancestor_score(nid, &index.parents, doc_scores),
302 anchor_node_id: nid.clone(),
303 });
304 }
305
306 selected
307 }
308
309 fn tree_walk(
314 &self,
315 index: &DocumentTreeIndex<'_>,
316 anchors: &[SearchState],
317 doc_scores: &HashMap<String, f64>,
318 plan: &QueryPlan,
319 idf: Option<&HashMap<String, f64>>,
320 ) -> (Vec<PathResult>, Vec<SearchState>) {
321 let mut visited: HashSet<String> = HashSet::new();
322 let mut frontier: BinaryHeap<SearchState> = BinaryHeap::new();
323 let mut best_states: Vec<SearchState> = Vec::new();
324 let mut expansion_count = 0;
325
326 let mut overlap_cache: HashMap<String, f64> = HashMap::new();
328 if !plan.terms.is_empty() {
329 for nid in doc_scores.keys() {
330 if let Some(node) = index.node(nid) {
331 overlap_cache.insert(
332 nid.clone(),
333 compute_term_overlap(
334 bounded_prefix(&node.text, self.config.max_node_chars),
335 &plan.terms,
336 idf,
337 ),
338 );
339 }
340 }
341 }
342
343 for anchor in anchors {
345 frontier.push(anchor.clone());
346 }
347
348 while let Some(state) = frontier.pop() {
349 if expansion_count >= self.config.max_expansions {
350 break;
351 }
352 if visited.contains(&state.node_id) {
353 continue;
354 }
355 visited.insert(state.node_id.clone());
356 best_states.push(state.clone());
357 expansion_count += 1;
358
359 if state.score >= self.config.early_stop_score {
360 break;
361 }
362 if state.score < self.config.min_frontier_score {
363 continue;
364 }
365 if state.hop >= self.config.max_hops {
366 continue;
367 }
368
369 let neighbors = get_neighbors(
371 &state.node_id,
372 &index.parents,
373 &index.children,
374 self.config.max_siblings,
375 );
376 for (nid, relation) in neighbors {
377 if visited.contains(&nid) {
378 continue;
379 }
380 let node = match index.node(&nid) {
381 Some(n) => n,
382 None => continue,
383 };
384 let lexical = doc_scores.get(&nid).copied().unwrap_or(0.0);
385 let overlap = overlap_cache.get(&nid).copied().unwrap_or_else(|| {
386 if !plan.terms.is_empty() {
387 let ov = compute_term_overlap(
388 bounded_prefix(&node.text, self.config.max_node_chars),
389 &plan.terms,
390 idf,
391 );
392 overlap_cache.insert(nid.clone(), ov);
393 ov
394 } else {
395 0.0
396 }
397 });
398 let new_max_anc = maximum_ancestor_score(&nid, &index.parents, doc_scores);
399 let full_text = format!(
400 "{} {}",
401 node.title,
402 bounded_prefix(&node.text, self.config.max_node_chars)
403 );
404 let w_score = score_walk_node_with_input(WalkScoreInput {
405 lexical_score: lexical,
406 has_title_match: check_title_match(&node.title, &plan.terms),
407 has_phrase_match: check_phrase_match(&full_text, &plan.phrases),
408 body_term_overlap: overlap,
409 ancestor_support: new_max_anc,
410 hop: u32::try_from(state.hop.saturating_add(1)).unwrap_or(u32::MAX),
411 is_redundant: false,
412 max_hops: u32::try_from(self.config.max_hops).unwrap_or(u32::MAX),
413 });
414
415 let new_path = if relation == "child" {
416 let mut p = state.path.clone();
417 p.push(nid.clone());
418 p
419 } else {
420 path_to_root_via_map(&nid, &index.parents)
421 };
422
423 frontier.push(SearchState {
424 doc_id: index.document.doc_id.clone(),
425 node_id: nid,
426 score: w_score,
427 hop: state.hop.saturating_add(1),
428 source: relation,
429 path: new_path,
430 max_ancestor_score: new_max_anc,
431 anchor_node_id: state.anchor_node_id.clone(),
432 });
433 }
434 }
435
436 let paths = self.states_to_paths(index, &mut best_states, doc_scores, plan);
437 (paths, best_states)
438 }
439
440 fn states_to_paths(
441 &self,
442 index: &DocumentTreeIndex<'_>,
443 states: &mut [SearchState],
444 doc_scores: &HashMap<String, f64>,
445 plan: &QueryPlan,
446 ) -> Vec<PathResult> {
447 states.sort_by(compare_states);
448 let mut results: Vec<PathResult> = Vec::new();
449 let mut seen_targets: HashSet<String> = HashSet::new();
450 let max_to_process = self.config.path_top_k.saturating_mul(2);
451
452 for state in states.iter() {
453 if results.len() >= max_to_process {
454 break;
455 }
456 if seen_targets.contains(&state.node_id) {
457 continue;
458 }
459 seen_targets.insert(state.node_id.clone());
460
461 let full_path = path_to_root_via_map(&state.node_id, &index.parents);
462 let mut path_titles = Vec::new();
463 let mut path_texts = Vec::new();
464 let mut path_nodes = Vec::new();
465 for pid in &full_path {
466 if let Some(pnode) = index.node(pid) {
467 path_titles.push(pnode.title.clone());
468 path_texts
469 .push(bounded_prefix(&pnode.text, self.config.max_node_chars).to_string());
470 path_nodes.push(PathNode {
471 node_id: pid.clone(),
472 title: pnode.title.clone(),
473 });
474 }
475 }
476
477 let p_score = score_path(
478 state.score,
479 &path_titles,
480 &path_texts,
481 &plan.terms,
482 full_path.len(),
483 doc_scores.get(&state.node_id).copied().unwrap_or(0.0),
484 6,
485 );
486
487 let snippet = index
488 .node(&state.node_id)
489 .map(|node| {
490 bounded_prefix(&node.text, self.config.max_result_chars.min(300)).to_string()
491 })
492 .unwrap_or_default();
493
494 results.push(PathResult {
495 doc_id: index.document.doc_id.clone(),
496 doc_name: index.document.doc_name.clone(),
497 score: (p_score * 10000.0).round() / 10000.0,
498 anchor_node_id: state.anchor_node_id.clone(),
499 target_node_id: state.node_id.clone(),
500 path: path_nodes,
501 snippet,
502 });
503 }
504
505 results.sort_by(compare_paths);
506 results.truncate(self.config.path_top_k);
507 results
508 }
509
510 fn build_flat_nodes(
515 &self,
516 _paths: &[PathResult],
517 walked_nodes: &[(String, String, f64, f64, usize)],
518 document_indexes: &HashMap<&str, &DocumentTreeIndex<'_>>,
519 initial_score_map: &HashMap<String, HashMap<String, f64>>,
520 plan: &QueryPlan,
521 ) -> Vec<FlatNode> {
522 let mut node_scores: HashMap<(String, String), f64> = HashMap::new();
523 for (doc_id, doc_scores) in initial_score_map {
525 for (nid, &initial_score) in doc_scores {
526 node_scores.insert((doc_id.clone(), nid.clone()), initial_score);
527 }
528 }
529
530 for ((doc_id, nid), score) in node_scores.iter_mut() {
532 let index = match document_indexes.get(doc_id.as_str()) {
533 Some(index) => index,
534 None => continue,
535 };
536 let node = match index.node(nid) {
537 Some(n) => n,
538 None => continue,
539 };
540 let depth = index.depths.get(nid.as_str()).copied().unwrap_or(0);
541
542 if depth > 0 && is_generic_section(&node.title, depth) {
544 let demote = if !plan.terms.is_empty() {
545 let base_title = node.title.to_lowercase();
546 !plan.terms.iter().any(|t| base_title.contains(t.as_str()))
547 } else {
548 true
549 };
550 if demote {
551 *score *= 0.70;
552 }
553 }
554
555 if node.children.is_empty() && node.text.len() > 100 {
557 *score *= 1.08;
558 }
559 }
560
561 for (doc_id, nid, combined_score, _initial_score, _hop) in walked_nodes {
563 let key = (doc_id.clone(), nid.clone());
564 if let Some(score) = node_scores.get_mut(&key) {
565 *score += 0.15 * combined_score;
566 }
567 }
568
569 if !plan.terms.is_empty() {
571 let keys: Vec<(String, String)> = node_scores.keys().cloned().collect();
572 for key in &keys {
573 let score = match node_scores.get(key) {
574 Some(&s) if s >= 0.05 => s,
575 _ => continue,
576 };
577 let index = match document_indexes.get(key.0.as_str()) {
578 Some(index) => index,
579 None => continue,
580 };
581 let node = match index.node(&key.1) {
582 Some(n) => n,
583 None => continue,
584 };
585 let title_lower = node.title.to_lowercase();
586 let title_hits = plan
587 .terms
588 .iter()
589 .filter(|t| title_lower.contains(t.as_str()))
590 .count();
591 if title_hits > 0 {
592 let title_overlap = title_hits as f64 / plan.terms.len() as f64;
593 let title_bonus = 0.15 * title_overlap * score.max(0.10);
594 node_scores.insert(key.clone(), score + title_bonus);
595 }
596 }
597 }
598
599 let global_max = node_scores.values().copied().fold(0.0_f64, f64::max);
602 if global_max > 1.0 {
603 for score in node_scores.values_mut() {
604 *score /= global_max;
605 }
606 }
607
608 let mut flat_nodes: Vec<FlatNode> = node_scores
610 .into_iter()
611 .filter_map(|((doc_id, nid), score)| {
612 let index = document_indexes.get(doc_id.as_str())?;
613 let node = index.node(&nid)?;
614 Some(FlatNode {
615 node_id: nid,
616 doc_id: doc_id.clone(),
617 doc_name: index.document.doc_name.clone(),
618 title: node.title.clone(),
619 score: (score * 10000.0).round() / 10000.0,
620 text: bounded_prefix(&node.text, self.config.max_result_chars).to_string(),
621 })
622 })
623 .collect();
624
625 flat_nodes.sort_by(|left, right| {
626 right
627 .score
628 .total_cmp(&left.score)
629 .then_with(|| left.doc_id.cmp(&right.doc_id))
630 .then_with(|| left.node_id.cmp(&right.node_id))
631 });
632 flat_nodes
633 }
634}
635
636fn normalize_initial_scores(
642 scores: &HashMap<String, HashMap<String, f64>>,
643) -> HashMap<String, HashMap<String, f64>> {
644 let mut normalized: HashMap<String, HashMap<String, f64>> = scores
645 .iter()
646 .filter_map(|(document_id, node_scores)| {
647 let valid: HashMap<String, f64> = node_scores
648 .iter()
649 .filter(|(_, score)| score.is_finite() && **score > 0.0)
650 .map(|(node_id, score)| (node_id.clone(), *score))
651 .collect();
652 (!valid.is_empty()).then_some((document_id.clone(), valid))
653 })
654 .collect();
655 let global_max = normalized
656 .values()
657 .flat_map(HashMap::values)
658 .copied()
659 .fold(0.0_f64, f64::max);
660 if global_max > 1.0 {
661 for score in normalized.values_mut().flat_map(HashMap::values_mut) {
662 *score /= global_max;
663 }
664 }
665 normalized
666}
667
668fn bounded_prefix(text: &str, max_characters: usize) -> &str {
670 match text.char_indices().nth(max_characters) {
671 Some((end, _)) => &text[..end],
672 None => text,
673 }
674}
675
676fn path_to_root_via_map(
677 node_id: &str,
678 parent_map: &HashMap<String, Option<String>>,
679) -> Vec<String> {
680 let mut path = Vec::new();
681 let mut visited = HashSet::new();
682 let mut current = Some(node_id.to_string());
683 while let Some(nid) = current {
684 if !visited.insert(nid.clone()) {
685 return Vec::new();
686 }
687 path.push(nid.clone());
688 current = parent_map.get(&nid).and_then(|p| p.clone());
689 }
690 path.reverse();
691 path
692}
693
694fn maximum_ancestor_score(
696 node_id: &str,
697 parent_map: &HashMap<String, Option<String>>,
698 scores: &HashMap<String, f64>,
699) -> f64 {
700 let mut maximum = 0.0_f64;
701 let mut visited = HashSet::new();
702 let mut current = parent_map.get(node_id).and_then(Clone::clone);
703 while let Some(node_id) = current {
704 if !visited.insert(node_id.clone()) {
705 break;
706 }
707 maximum = maximum.max(scores.get(&node_id).copied().unwrap_or(0.0));
708 current = parent_map.get(&node_id).and_then(Clone::clone);
709 }
710 maximum
711}
712
713fn compare_states(left: &SearchState, right: &SearchState) -> std::cmp::Ordering {
715 right
716 .score
717 .total_cmp(&left.score)
718 .then_with(|| left.hop.cmp(&right.hop))
719 .then_with(|| left.doc_id.cmp(&right.doc_id))
720 .then_with(|| left.node_id.cmp(&right.node_id))
721 .then_with(|| left.anchor_node_id.cmp(&right.anchor_node_id))
722}
723
724fn compare_paths(left: &PathResult, right: &PathResult) -> std::cmp::Ordering {
726 right
727 .score
728 .total_cmp(&left.score)
729 .then_with(|| left.doc_id.cmp(&right.doc_id))
730 .then_with(|| left.target_node_id.cmp(&right.target_node_id))
731 .then_with(|| left.anchor_node_id.cmp(&right.anchor_node_id))
732}
733
734fn get_neighbors(
735 node_id: &str,
736 parent_map: &HashMap<String, Option<String>>,
737 children_map: &HashMap<String, Vec<String>>,
738 max_siblings: usize,
739) -> Vec<(String, String)> {
740 let mut neighbors = Vec::new();
741
742 if let Some(children) = children_map.get(node_id) {
744 for cid in children {
745 neighbors.push((cid.clone(), "child".into()));
746 }
747 }
748
749 if let Some(Some(pid)) = parent_map.get(node_id) {
751 neighbors.push((pid.clone(), "parent".into()));
752
753 if let Some(siblings) = children_map.get(pid.as_str()) {
755 let mut count = 0;
756 for sid in siblings {
757 if sid != node_id && count < max_siblings {
758 neighbors.push((sid.clone(), "sibling".into()));
759 count += 1;
760 }
761 }
762 }
763 }
764
765 neighbors
766}
767
768#[cfg(test)]
769mod tests {
770 use super::normalize_initial_scores;
771 use std::collections::HashMap;
772
773 #[test]
774 fn direct_walker_scores_are_filtered_and_globally_calibrated() {
775 let scores = HashMap::from([
776 (
777 "a".to_string(),
778 HashMap::from([
779 ("high".to_string(), 20.0),
780 ("low".to_string(), 10.0),
781 ("nan".to_string(), f64::NAN),
782 ("negative".to_string(), -1.0),
783 ]),
784 ),
785 (
786 "b".to_string(),
787 HashMap::from([("infinite".to_string(), f64::INFINITY)]),
788 ),
789 ]);
790
791 let normalized = normalize_initial_scores(&scores);
792 assert_eq!(normalized["a"]["high"], 1.0);
793 assert_eq!(normalized["a"]["low"], 0.5);
794 assert!(!normalized["a"].contains_key("nan"));
795 assert!(!normalized["a"].contains_key("negative"));
796 assert!(!normalized.contains_key("b"));
797 }
798}