Skip to main content

treesearch/engine/
tree_walker.rs

1//! Tree Walker — Best-First Search over document trees.
2//!
3//! Core algorithm (ported from Python tree_searcher.py):
4//! 1. Anchor Retrieval: use host-provided scores to find high-value entry nodes
5//! 2. Tree Walk: BFS expansion from anchors along parent/child/sibling edges
6//! 3. Path Aggregation: select best root-to-leaf paths as results
7
8use 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/// State in the Best-First Search frontier.
19#[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    /// Original retrieval anchor that initiated this walk branch.
29    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        // Max-heap: higher score first, then lower hop and lexical identity.
47        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/// A scored root-to-answer path.
60#[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/// Flat node from tree walker reranking.
78#[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
88/// Tree searcher engine.
89pub struct TreeSearcher<'a> {
90    config: &'a TreeSearchConfig,
91}
92
93/// Reuses document lookups across every phase of one tree-search request.
94struct 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    /// Builds all structural maps in linear time for one document.
104    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    /// Returns one uniquely identified node from the prebuilt lookup.
115    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    /// Run tree search across documents.
126    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        // Sort documents by maximum initial score descending.
145        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            // IDF estimation for large documents
166            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            // Stage 1: Anchor retrieval
178            let anchors = self.select_anchors(index, doc_scores, &plan, idf.as_ref());
179            if anchors.is_empty() {
180                continue;
181            }
182
183            // Stage 2: Tree walk
184            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        // Stage 3: Select top paths globally
202        all_paths.sort_by(compare_paths);
203        all_paths.truncate(self.config.path_top_k);
204
205        // Build flat nodes with reranking
206        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    // ---------------------------------------------------------------
222    // Stage 1: Anchor Retrieval
223    // ---------------------------------------------------------------
224
225    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    // ---------------------------------------------------------------
310    // Stage 2: Tree Walk (Best-First Search)
311    // ---------------------------------------------------------------
312
313    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        // Pre-cache term overlap for initially scored nodes.
327        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        // Initialize frontier
344        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            // Expand neighbors
370            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    // ---------------------------------------------------------------
511    // Stage 3: Build flat nodes with reranking
512    // ---------------------------------------------------------------
513
514    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        // 1. Base: host-provided initial scores.
524        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        // 2. Generic section demotion + leaf preference (merged pass)
531        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            // Generic section demotion
543            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            // Leaf preference
556            if node.children.is_empty() && node.text.len() > 100 {
557                *score *= 1.08;
558            }
559        }
560
561        // 3. Walk boost
562        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        // 4. Title match boost
570        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        // Preserve relative ordering while restoring the public score range
600        // after leaf, walk, and title boosts.
601        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        // Build flat node list
609        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
636// ---------------------------------------------------------------
637// Helpers
638// ---------------------------------------------------------------
639
640/// Filters invalid direct walker inputs and globally calibrates raw scores.
641fn 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
668/// Returns at most `max_characters` without splitting a UTF-8 code point.
669fn 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
694/// Returns the strongest score on the strict ancestor chain of one node.
695fn 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
713/// Orders traversal states deterministically for stable ranking and tests.
714fn 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
724/// Orders path results by score and stable transport identities.
725fn 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    // Children
743    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    // Parent
750    if let Some(Some(pid)) = parent_map.get(node_id) {
751        neighbors.push((pid.clone(), "parent".into()));
752
753        // Siblings (via parent's children)
754        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}