fluidattacks_blends_domain/syntax/
graph.rs

1//! Syntax graph: node table plus AST-mirroring adjacency.
2
3use alloc::collections::BTreeMap;
4use alloc::string::String;
5use alloc::vec::Vec;
6
7use crate::syntax::{SyntaxEdge, SyntaxKind, SyntaxNode};
8use crate::{Ast, Cfg, CodeGraph, NodeId};
9
10#[derive(Clone, PartialEq, Eq, Debug)]
11pub struct SanitizationEvent {
12    pub node_id: NodeId,
13    pub kind: String,
14    pub subpath: Option<NodeId>,
15}
16
17#[derive(Clone, Copy, PartialEq, Eq, Debug)]
18pub enum UsageRole {
19    Receiver,
20    Argument,
21    MemberWrite,
22}
23
24#[derive(Clone, PartialEq, Eq, Debug)]
25pub struct UsageEvent {
26    pub node_id: NodeId,
27    pub role: UsageRole,
28    pub arg_index: Option<i64>,
29    pub subpath: Option<NodeId>,
30}
31
32#[derive(Clone, PartialEq, Eq, Debug, Default)]
33pub struct SyntaxGraph {
34    pub nodes: BTreeMap<NodeId, SyntaxNode>,
35    pub edges: BTreeMap<NodeId, BTreeMap<NodeId, SyntaxEdge>>,
36    pub symbol_index: BTreeMap<String, BTreeMap<NodeId, Vec<NodeId>>>,
37    pub scope_parent: BTreeMap<NodeId, NodeId>,
38    pub sanitization_index: BTreeMap<String, BTreeMap<NodeId, Vec<SanitizationEvent>>>,
39    pub usage_index: BTreeMap<String, BTreeMap<NodeId, Vec<UsageEvent>>>,
40    pub subpath_index: BTreeMap<NodeId, Option<NodeId>>,
41    pub nodes_by_type: BTreeMap<SyntaxKind, Vec<NodeId>>,
42}
43
44impl SyntaxGraph {
45    #[must_use]
46    pub fn new() -> Self {
47        Self::default()
48    }
49
50    pub fn add_node(&mut self, id: NodeId, node: SyntaxNode) {
51        self.nodes_by_type
52            .entry(SyntaxKind::from(&node))
53            .or_default()
54            .push(id);
55        self.nodes.insert(id, node);
56    }
57
58    pub fn register_sanitization(&mut self, symbol: &str, scope: NodeId, event: SanitizationEvent) {
59        self.sanitization_index
60            .entry(String::from(symbol))
61            .or_default()
62            .entry(scope)
63            .or_default()
64            .push(event);
65    }
66
67    pub fn register_usage(&mut self, symbol: &str, scope: NodeId, event: UsageEvent) {
68        self.usage_index
69            .entry(String::from(symbol))
70            .or_default()
71            .entry(scope)
72            .or_default()
73            .push(event);
74    }
75
76    pub fn add_ast_edge(&mut self, from: NodeId, to: NodeId) {
77        self.edges
78            .entry(from)
79            .or_default()
80            .entry(to)
81            .or_default()
82            .ast = Some(Ast);
83    }
84
85    pub fn add_cfg_edge(&mut self, from: NodeId, to: NodeId) {
86        self.edges
87            .entry(from)
88            .or_default()
89            .entry(to)
90            .or_default()
91            .cfg = Some(Cfg);
92    }
93
94    pub fn finalize_symbol_index(&mut self) {
95        for scope_definitions in self.symbol_index.values_mut() {
96            for definition_list in scope_definitions.values_mut() {
97                definition_list.reverse();
98            }
99        }
100    }
101
102    pub fn remove_edge(&mut self, from: NodeId, to: NodeId) {
103        if let Some(adjacent) = self.edges.get_mut(&from) {
104            adjacent.remove(&to);
105            if adjacent.is_empty() {
106                self.edges.remove(&from);
107            }
108        }
109    }
110}
111
112impl CodeGraph for SyntaxGraph {
113    fn children(&self, n_id: NodeId) -> Vec<NodeId> {
114        self.edges
115            .get(&n_id)
116            .map(|adjacent| adjacent.keys().copied().collect())
117            .unwrap_or_default()
118    }
119
120    fn ast_children(&self, n_id: NodeId) -> Vec<NodeId> {
121        self.edges
122            .get(&n_id)
123            .map(|adjacent| {
124                adjacent
125                    .iter()
126                    .filter(|(_, edge)| edge.ast.is_some())
127                    .map(|(to, _)| *to)
128                    .collect()
129            })
130            .unwrap_or_default()
131    }
132
133    fn parents(&self, n_id: NodeId) -> Vec<NodeId> {
134        self.edges
135            .iter()
136            .filter(|(_, adjacent)| adjacent.contains_key(&n_id))
137            .map(|(from, _)| *from)
138            .collect()
139    }
140
141    fn ast_parents(&self, n_id: NodeId) -> Vec<NodeId> {
142        self.edges
143            .iter()
144            .filter(|(_, adjacent)| adjacent.get(&n_id).is_some_and(|edge| edge.ast.is_some()))
145            .map(|(from, _)| *from)
146            .collect()
147    }
148
149    fn cfg_parents(&self, n_id: NodeId) -> Vec<NodeId> {
150        self.edges
151            .iter()
152            .filter(|(_, adjacent)| adjacent.get(&n_id).is_some_and(|edge| edge.cfg.is_some()))
153            .map(|(from, _)| *from)
154            .collect()
155    }
156
157    fn cfg_children(&self, n_id: NodeId) -> Vec<NodeId> {
158        self.edges
159            .get(&n_id)
160            .map(|adjacent| {
161                adjacent
162                    .iter()
163                    .filter(|(_, edge)| edge.cfg.is_some())
164                    .map(|(to, _)| *to)
165                    .collect()
166            })
167            .unwrap_or_default()
168    }
169
170    fn label_type(&self, n_id: NodeId) -> Option<&str> {
171        self.nodes.get(&n_id).map(SyntaxNode::label_type)
172    }
173}
174
175#[cfg(test)]
176mod tests {
177    use super::SyntaxGraph;
178    use crate::syntax::{SyntaxEdge, SyntaxKind, SyntaxNode};
179    use crate::{Ast, Cfg, CodeGraph, NodeId};
180    use alloc::borrow::ToOwned;
181
182    #[test]
183    fn stores_nodes_and_edges_by_id() {
184        let mut graph = SyntaxGraph::new();
185        graph.add_node(
186            NodeId(1),
187            SyntaxNode::MissingNode {
188                node_type: "stream".to_owned(),
189            },
190        );
191        graph.add_ast_edge(NodeId(1), NodeId(2));
192
193        assert_eq!(
194            graph.nodes.get(&NodeId(1)),
195            Some(&SyntaxNode::MissingNode {
196                node_type: "stream".to_owned()
197            })
198        );
199        assert_eq!(
200            graph
201                .edges
202                .get(&NodeId(1))
203                .and_then(|adjacent| adjacent.get(&NodeId(2))),
204            Some(&SyntaxEdge {
205                ast: Some(Ast),
206                cfg: None
207            })
208        );
209    }
210
211    #[test]
212    fn add_node_indexes_ids_by_syntax_type_in_insertion_order() {
213        let mut graph = SyntaxGraph::new();
214        graph.add_node(NodeId(9), SyntaxNode::Break);
215        graph.add_node(NodeId(1), SyntaxNode::File);
216        graph.add_node(NodeId(2), SyntaxNode::Break);
217
218        assert_eq!(
219            graph.nodes_by_type.get(&SyntaxKind::Break),
220            Some(&alloc::vec![NodeId(9), NodeId(2)])
221        );
222        assert_eq!(
223            graph.nodes_by_type.get(&SyntaxKind::File),
224            Some(&alloc::vec![NodeId(1)])
225        );
226        assert_eq!(graph.nodes_by_type.get(&SyntaxKind::If), None);
227    }
228
229    #[test]
230    fn ast_edge_merges_into_existing_edge() {
231        let mut graph = SyntaxGraph::new();
232        graph.add_ast_edge(NodeId(1), NodeId(2));
233        graph.add_ast_edge(NodeId(1), NodeId(2));
234
235        assert_eq!(
236            graph
237                .edges
238                .get(&NodeId(1))
239                .map(alloc::collections::BTreeMap::len),
240            Some(1)
241        );
242    }
243
244    #[test]
245    fn ast_children_skip_edges_without_the_ast_mark() {
246        let mut graph = SyntaxGraph::new();
247        graph.add_ast_edge(NodeId(1), NodeId(2));
248        graph.edges.entry(NodeId(1)).or_default().insert(
249            NodeId(3),
250            SyntaxEdge {
251                ast: None,
252                cfg: None,
253            },
254        );
255
256        assert_eq!(graph.ast_children(NodeId(1)), [NodeId(2)]);
257    }
258
259    #[test]
260    fn cfg_edge_merges_onto_the_ast_edge() {
261        let mut graph = SyntaxGraph::new();
262        graph.add_ast_edge(NodeId(1), NodeId(2));
263        graph.add_cfg_edge(NodeId(1), NodeId(2));
264
265        assert_eq!(
266            graph
267                .edges
268                .get(&NodeId(1))
269                .and_then(|adjacent| adjacent.get(&NodeId(2))),
270            Some(&SyntaxEdge {
271                ast: Some(Ast),
272                cfg: Some(Cfg)
273            })
274        );
275    }
276
277    #[test]
278    fn remove_edge_drops_the_edge_and_prunes_the_empty_entry() {
279        let mut graph = SyntaxGraph::new();
280        graph.add_ast_edge(NodeId(1), NodeId(2));
281        graph.add_ast_edge(NodeId(1), NodeId(3));
282        graph.add_cfg_edge(NodeId(1), NodeId(2));
283
284        graph.remove_edge(NodeId(1), NodeId(2));
285
286        assert_eq!(graph.children(NodeId(1)), [NodeId(3)]);
287        assert_eq!(graph.parents(NodeId(2)), []);
288
289        graph.remove_edge(NodeId(1), NodeId(3));
290
291        assert!(!graph.edges.contains_key(&NodeId(1)));
292    }
293
294    #[test]
295    fn finalize_symbol_index_puts_the_most_recent_definition_first() {
296        let mut graph = SyntaxGraph::new();
297        graph
298            .symbol_index
299            .entry("x".to_owned())
300            .or_default()
301            .entry(NodeId(1))
302            .or_default()
303            .extend([NodeId(2), NodeId(5), NodeId(9)]);
304
305        graph.finalize_symbol_index();
306
307        assert_eq!(
308            graph
309                .symbol_index
310                .get("x")
311                .and_then(|scopes| scopes.get(&NodeId(1))),
312            Some(&alloc::vec![NodeId(9), NodeId(5), NodeId(2)])
313        );
314    }
315
316    #[test]
317    fn remove_edge_ignores_a_missing_edge() {
318        let mut graph = SyntaxGraph::new();
319        graph.add_ast_edge(NodeId(1), NodeId(2));
320
321        graph.remove_edge(NodeId(7), NodeId(8));
322        graph.remove_edge(NodeId(1), NodeId(9));
323
324        assert_eq!(graph.children(NodeId(1)), [NodeId(2)]);
325    }
326
327    #[test]
328    fn cfg_children_skip_edges_without_the_cfg_mark() {
329        let mut graph = SyntaxGraph::new();
330        graph.add_ast_edge(NodeId(1), NodeId(2));
331        graph.add_ast_edge(NodeId(1), NodeId(3));
332        graph.add_cfg_edge(NodeId(1), NodeId(3));
333
334        assert_eq!(graph.cfg_children(NodeId(1)), [NodeId(3)]);
335        assert_eq!(graph.cfg_children(NodeId(9)), []);
336    }
337}
fluidattacks_blends_domain/syntax/graph.rs

fluidattacks_blends_domain/syntax/
graph.rs
