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    /// Allowed relations; None = all (Contains stays excluded either way).
20    pub relations: Option<BTreeSet<Relation>>,
21}
22
23impl EdgeFilter {
24    pub fn admits(&self, edge: &Edge) -> bool {
25        if edge.relation == Relation::Contains {
26            return false;
27        }
28        if let Some(allowed) = &self.relations
29            && !allowed.contains(&edge.relation)
30        {
31            return false;
32        }
33        if let Some(allowed) = &self.evidence
34            && !allowed.contains(&edge.evidence)
35        {
36            return false;
37        }
38        if self.min_confidence == Some(Confidence::Certain)
39            && edge.confidence != Confidence::Certain
40        {
41            return false;
42        }
43        true
44    }
45}
46
47/// One step of a traversal result: the node reached, how deep, and the edge
48/// that reached it.
49pub struct Reached {
50    pub node: Node,
51    pub depth: usize,
52    pub via: Edge,
53}
54
55impl Store {
56    /// Reverse blast radius: everything transitively depending on `id`
57    /// (incoming non-Contains edges), breadth-first, deduplicated.
58    pub fn dependents(
59        &self,
60        id: &NodeId,
61        filter: &EdgeFilter,
62        max_depth: usize,
63    ) -> Result<Vec<Reached>, StoreError> {
64        let mut seen: HashSet<NodeId> = HashSet::from([id.clone()]);
65        let mut queue: VecDeque<(NodeId, usize)> = VecDeque::from([(id.clone(), 0)]);
66        let mut out = Vec::new();
67        while let Some((current, depth)) = queue.pop_front() {
68            if depth >= max_depth {
69                continue;
70            }
71            for edge in self.in_edges(&current)? {
72                if !filter.admits(&edge) || !seen.insert(edge.src.clone()) {
73                    continue;
74                }
75                if let Some(node) = self.node(&edge.src)? {
76                    queue.push_back((edge.src.clone(), depth + 1));
77                    out.push(Reached {
78                        node,
79                        depth: depth + 1,
80                        via: edge,
81                    });
82                }
83            }
84        }
85        Ok(out)
86    }
87
88    /// Forward transitive closure: everything `id` depends on (outgoing
89    /// non-Contains edges), breadth-first, deduplicated. A file start seeds
90    /// through its Contains edges (a file's dependencies live in the
91    /// symbols it contains), silently — containment is not a dependency.
92    pub fn dependencies(
93        &self,
94        id: &NodeId,
95        filter: &EdgeFilter,
96        max_depth: usize,
97    ) -> Result<Vec<Reached>, StoreError> {
98        let mut seen: HashSet<NodeId> = HashSet::from([id.clone()]);
99        let mut queue: VecDeque<(NodeId, usize)> = VecDeque::from([(id.clone(), 0)]);
100        if self
101            .node(id)?
102            .is_some_and(|n| n.kind == sinter_core::SymbolKind::File)
103        {
104            for edge in self.out_edges(id)? {
105                if edge.relation == Relation::Contains && seen.insert(edge.dst.clone()) {
106                    queue.push_back((edge.dst.clone(), 0));
107                }
108            }
109        }
110        let mut out = Vec::new();
111        while let Some((current, depth)) = queue.pop_front() {
112            if depth >= max_depth {
113                continue;
114            }
115            for edge in self.out_edges(&current)? {
116                if !filter.admits(&edge) || !seen.insert(edge.dst.clone()) {
117                    continue;
118                }
119                if let Some(node) = self.node(&edge.dst)? {
120                    queue.push_back((edge.dst.clone(), depth + 1));
121                    out.push(Reached {
122                        node,
123                        depth: depth + 1,
124                        via: edge,
125                    });
126                }
127            }
128        }
129        Ok(out)
130    }
131
132    /// Shortest edge path `from -> to` over outgoing edges, or None.
133    pub fn shortest_path(
134        &self,
135        from: &NodeId,
136        to: &NodeId,
137        filter: &EdgeFilter,
138    ) -> Result<Option<Vec<Edge>>, StoreError> {
139        let mut prev: HashMap<NodeId, Edge> = HashMap::new();
140        let mut seen: HashSet<NodeId> = HashSet::from([from.clone()]);
141        let mut queue: VecDeque<NodeId> = VecDeque::from([from.clone()]);
142        // A file's dependencies live in the symbols it contains; a file
143        // start seeds through its contains edges (shown as path steps).
144        // Containment stays non-traversable everywhere past the start.
145        if self
146            .node(from)?
147            .is_some_and(|n| n.kind == sinter_core::SymbolKind::File)
148        {
149            for edge in self.out_edges(from)? {
150                if edge.relation == Relation::Contains && seen.insert(edge.dst.clone()) {
151                    prev.insert(edge.dst.clone(), edge.clone());
152                    queue.push_back(edge.dst.clone());
153                }
154            }
155        }
156        while let Some(current) = queue.pop_front() {
157            if &current == to {
158                let mut path = Vec::new();
159                let mut at = to.clone();
160                while &at != from {
161                    let edge = prev[&at].clone();
162                    at = edge.src.clone();
163                    path.push(edge);
164                }
165                path.reverse();
166                return Ok(Some(path));
167            }
168            for edge in self.out_edges(&current)? {
169                if !filter.admits(&edge) || !seen.insert(edge.dst.clone()) {
170                    continue;
171                }
172                prev.insert(edge.dst.clone(), edge.clone());
173                queue.push_back(edge.dst.clone());
174            }
175        }
176        Ok(None)
177    }
178}
sinter_store/traverse.rs

sinter_store/
traverse.rs
