eidos_kernel/
graph_index.rs

1//! Indexed read view over a [`Graph`].
2//!
3//! The serialized graph stays as simple vectors for deterministic artifacts. Hot read paths build
4//! this borrowed view when they need repeated node/edge lookups.
5
6use std::collections::HashMap;
7
8use crate::schema::{Edge, Graph, Kind, Node};
9
10#[derive(Debug)]
11pub struct GraphIndex<'a> {
12    nodes_by_id: HashMap<&'a str, &'a Node>,
13    incoming_by_id: HashMap<&'a str, Vec<&'a Edge>>,
14    outgoing_by_id: HashMap<&'a str, Vec<&'a Edge>>,
15}
16
17impl<'a> GraphIndex<'a> {
18    pub fn build(graph: &'a Graph) -> Self {
19        let mut nodes_by_id = HashMap::with_capacity(graph.nodes.len());
20        for node in &graph.nodes {
21            nodes_by_id.insert(node.id.as_str(), node);
22        }
23
24        let mut incoming_by_id: HashMap<&'a str, Vec<&'a Edge>> = HashMap::new();
25        let mut outgoing_by_id: HashMap<&'a str, Vec<&'a Edge>> = HashMap::new();
26        for edge in &graph.edges {
27            outgoing_by_id
28                .entry(edge.from.as_str())
29                .or_default()
30                .push(edge);
31            incoming_by_id
32                .entry(edge.to.as_str())
33                .or_default()
34                .push(edge);
35        }
36
37        for edges in incoming_by_id.values_mut() {
38            edges.sort_by(|a, b| (&a.from, &a.to, &a.relation).cmp(&(&b.from, &b.to, &b.relation)));
39        }
40        for edges in outgoing_by_id.values_mut() {
41            edges.sort_by(|a, b| (&a.from, &a.to, &a.relation).cmp(&(&b.from, &b.to, &b.relation)));
42        }
43
44        Self {
45            nodes_by_id,
46            incoming_by_id,
47            outgoing_by_id,
48        }
49    }
50
51    pub fn node(&self, id: &str) -> Option<&'a Node> {
52        self.nodes_by_id.get(id).copied()
53    }
54
55    pub fn is_kind(&self, id: &str, kind: Kind) -> bool {
56        self.node(id).is_some_and(|node| node.kind == kind)
57    }
58
59    pub fn incoming(&self, id: &str) -> impl Iterator<Item = &'a Edge> + '_ {
60        self.incoming_by_id
61            .get(id)
62            .into_iter()
63            .flat_map(|edges| edges.iter().copied())
64    }
65
66    pub fn outgoing(&self, id: &str) -> impl Iterator<Item = &'a Edge> + '_ {
67        self.outgoing_by_id
68            .get(id)
69            .into_iter()
70            .flat_map(|edges| edges.iter().copied())
71    }
72
73    pub fn has_outgoing(&self, from: &str, relation: &str, to: &str) -> bool {
74        self.outgoing(from)
75            .any(|edge| edge.relation == relation && edge.to == to)
76    }
77
78    pub fn source_of(&self, node_id: &str) -> Option<String> {
79        let node = self.node(node_id)?;
80        if let Some(span) = &node.span {
81            if span.start_line == span.end_line {
82                return Some(format!("{}:{}", span.path, span.start_line));
83            }
84            return Some(format!(
85                "{}:{}-{}",
86                span.path, span.start_line, span.end_line
87            ));
88        }
89        node.source_files.first().cloned()
90    }
91}
92
93#[cfg(test)]
94mod tests {
95    use super::*;
96    use crate::schema::{Edge, Kind, Node, Span, relation};
97
98    fn node(id: &str, kind: Kind) -> Node {
99        Node {
100            id: id.into(),
101            kind,
102            subkind: None,
103            title: id.into(),
104            summary: String::new(),
105            aliases: Vec::new(),
106            tags: Vec::new(),
107            query_examples: Vec::new(),
108            source_files: vec![format!("fixtures/{id}.rs")],
109            span: None,
110            partition: None,
111        }
112    }
113
114    #[test]
115    fn indexes_nodes_and_edges() {
116        let graph = Graph {
117            nodes: vec![node("a", Kind::Function), node("b", Kind::Type)],
118            edges: vec![Edge {
119                from: "a".into(),
120                to: "b".into(),
121                relation: relation::REFERENCES.into(),
122                evidence: "test".into(),
123                ..Default::default()
124            }],
125            ..Default::default()
126        };
127
128        let index = GraphIndex::build(&graph);
129
130        assert!(index.is_kind("a", Kind::Function));
131        assert_eq!(index.node("b").map(|n| n.title.as_str()), Some("b"));
132        assert!(index.has_outgoing("a", relation::REFERENCES, "b"));
133        assert_eq!(index.incoming("b").count(), 1);
134        assert_eq!(index.outgoing("a").count(), 1);
135    }
136
137    #[test]
138    fn source_receipt_prefers_exact_span() {
139        let mut n = node("a", Kind::Function);
140        n.span = Some(Span {
141            path: "fixtures/a.rs".into(),
142            start_line: 4,
143            end_line: 7,
144        });
145        let graph = Graph {
146            nodes: vec![n],
147            edges: Vec::new(),
148            ..Default::default()
149        };
150
151        let index = GraphIndex::build(&graph);
152
153        assert_eq!(index.source_of("a").as_deref(), Some("fixtures/a.rs:4-7"));
154    }
155}
eidos_kernel/graph_index.rs

eidos_kernel/
graph_index.rs
