sinter_store/
traverse.rs

1//! Graph traversals over the persisted adjacency tables: reverse blast
2//! radius and shortest path. Point reads only — never loads the corpus.
3
4use std::collections::{BTreeSet, HashMap, HashSet, VecDeque};
5
6use sinter_core::{Confidence, Edge, Evidence, Node, NodeId, Relation};
7
8use crate::error::StoreError;
9use crate::store::Store;
10
11/// Which edges a traversal may walk. Containment is structure, not
12/// dependency, so it never participates.
13#[derive(Debug, Default, Clone)]
14pub struct EdgeFilter {
15    /// Allowed evidence kinds; None = all.
16    pub evidence: Option<BTreeSet<Evidence>>,
17    /// Minimum confidence; None = any.
18    pub min_confidence: Option<Confidence>,
19}
20
21impl EdgeFilter {
22    pub fn admits(&self, edge: &Edge) -> bool {
23        if edge.relation == Relation::Contains {
24            return false;
25        }
26        if let Some(allowed) = &self.evidence
27            && !allowed.contains(&edge.evidence)
28        {
29            return false;
30        }
31        if self.min_confidence == Some(Confidence::Certain)
32            && edge.confidence != Confidence::Certain
33        {
34            return false;
35        }
36        true
37    }
38}
39
40/// One step of a traversal result: the node reached, how deep, and the edge
41/// that reached it.
42pub struct Reached {
43    pub node: Node,
44    pub depth: usize,
45    pub via: Edge,
46}
47
48impl Store {
49    /// Reverse blast radius: everything transitively depending on `id`
50    /// (incoming non-Contains edges), breadth-first, deduplicated.
51    pub fn dependents(
52        &self,
53        id: &NodeId,
54        filter: &EdgeFilter,
55        max_depth: usize,
56    ) -> Result<Vec<Reached>, StoreError> {
57        let mut seen: HashSet<NodeId> = HashSet::from([id.clone()]);
58        let mut queue: VecDeque<(NodeId, usize)> = VecDeque::from([(id.clone(), 0)]);
59        let mut out = Vec::new();
60        while let Some((current, depth)) = queue.pop_front() {
61            if depth >= max_depth {
62                continue;
63            }
64            for edge in self.in_edges(&current)? {
65                if !filter.admits(&edge) || !seen.insert(edge.src.clone()) {
66                    continue;
67                }
68                if let Some(node) = self.node(&edge.src)? {
69                    queue.push_back((edge.src.clone(), depth + 1));
70                    out.push(Reached {
71                        node,
72                        depth: depth + 1,
73                        via: edge,
74                    });
75                }
76            }
77        }
78        Ok(out)
79    }
80
81    /// Shortest edge path `from -> to` over outgoing edges, or None.
82    pub fn shortest_path(
83        &self,
84        from: &NodeId,
85        to: &NodeId,
86        filter: &EdgeFilter,
87    ) -> Result<Option<Vec<Edge>>, StoreError> {
88        let mut prev: HashMap<NodeId, Edge> = HashMap::new();
89        let mut seen: HashSet<NodeId> = HashSet::from([from.clone()]);
90        let mut queue: VecDeque<NodeId> = VecDeque::from([from.clone()]);
91        // A file's dependencies live in the symbols it contains; a file
92        // start seeds through its contains edges (shown as path steps).
93        // Containment stays non-traversable everywhere past the start.
94        if self
95            .node(from)?
96            .is_some_and(|n| n.kind == sinter_core::SymbolKind::File)
97        {
98            for edge in self.out_edges(from)? {
99                if edge.relation == Relation::Contains && seen.insert(edge.dst.clone()) {
100                    prev.insert(edge.dst.clone(), edge.clone());
101                    queue.push_back(edge.dst.clone());
102                }
103            }
104        }
105        while let Some(current) = queue.pop_front() {
106            if &current == to {
107                let mut path = Vec::new();
108                let mut at = to.clone();
109                while &at != from {
110                    let edge = prev[&at].clone();
111                    at = edge.src.clone();
112                    path.push(edge);
113                }
114                path.reverse();
115                return Ok(Some(path));
116            }
117            for edge in self.out_edges(&current)? {
118                if !filter.admits(&edge) || !seen.insert(edge.dst.clone()) {
119                    continue;
120                }
121                prev.insert(edge.dst.clone(), edge.clone());
122                queue.push_back(edge.dst.clone());
123            }
124        }
125        Ok(None)
126    }
127}
sinter_store/traverse.rs

sinter_store/
traverse.rs
