fluidattacks-blends-domain 0.35.0

Blends functional core: pure AST graph to syntax graph (no_std)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

use alloc::collections::BTreeMap;
use alloc::vec::Vec;

use crate::stack::StackNode;
use crate::NodeId;

/// The stack graph: every push/pop/scope node plus the paths between them.
#[derive(Clone, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub struct StackGraph {
    /// Every node, keyed by id.
    pub nodes: BTreeMap<NodeId, StackNode>,
    /// Adjacency: source id -> sink id -> the edge's precedence.
    pub edges: BTreeMap<NodeId, BTreeMap<NodeId, i64>>,
}

impl StackGraph {
    /// An empty stack graph.
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Inserts `node` under `id`, replacing any node already there.
    pub fn add_node(&mut self, id: NodeId, node: StackNode) {
        self.nodes.insert(id, node);
    }

    /// Connects `source` to `sink`, keeping the higher precedence on repeat.
    pub fn add_edge(&mut self, source: NodeId, sink: NodeId, precedence: i64) {
        self.edges
            .entry(source)
            .or_default()
            .entry(sink)
            .and_modify(|existing| *existing = (*existing).max(precedence))
            .or_insert(precedence);
    }

    /// `id`'s outgoing edges, as (sink, precedence) pairs.
    #[must_use]
    pub fn successors(&self, id: NodeId) -> Vec<(NodeId, i64)> {
        self.edges
            .get(&id)
            .map(|adjacent| {
                adjacent
                    .iter()
                    .map(|(sink, precedence)| (*sink, *precedence))
                    .collect()
            })
            .unwrap_or_default()
    }

    /// Ids of every node with an edge into `id`.
    #[must_use]
    pub fn predecessors(&self, id: NodeId) -> Vec<NodeId> {
        self.edges
            .iter()
            .filter(|(_, adjacent)| adjacent.contains_key(&id))
            .map(|(source, _)| *source)
            .collect()
    }
}

#[cfg(test)]
mod tests {
    use super::StackGraph;
    use crate::stack::{StackNode, StackScope};
    use crate::NodeId;
    use alloc::vec;

    #[test]
    fn add_edge_keeps_the_precedence_of_a_new_edge() {
        let mut graph = StackGraph::new();
        graph.add_edge(NodeId(1), NodeId(2), 1);

        assert_eq!(graph.successors(NodeId(1)), vec![(NodeId(2), 1)]);
    }

    #[test]
    fn add_edge_keeps_the_higher_precedence_of_a_repeated_edge() {
        let mut graph = StackGraph::new();
        graph.add_edge(NodeId(1), NodeId(2), 1);
        graph.add_edge(NodeId(1), NodeId(2), 0);
        graph.add_edge(NodeId(3), NodeId(4), 0);
        graph.add_edge(NodeId(3), NodeId(4), 2);

        assert_eq!(graph.successors(NodeId(1)), vec![(NodeId(2), 1)]);
        assert_eq!(graph.successors(NodeId(3)), vec![(NodeId(4), 2)]);
    }

    #[test]
    fn successors_follow_sink_order() {
        let mut graph = StackGraph::new();
        graph.add_edge(NodeId(1), NodeId(9), 0);
        graph.add_edge(NodeId(1), NodeId(3), 1);

        assert_eq!(
            graph.successors(NodeId(1)),
            vec![(NodeId(3), 1), (NodeId(9), 0)]
        );
        assert_eq!(graph.successors(NodeId(9)), vec![]);
    }

    #[test]
    fn predecessors_find_every_source_of_a_sink() {
        let mut graph = StackGraph::new();
        graph.add_edge(NodeId(5), NodeId(1), 0);
        graph.add_edge(NodeId(2), NodeId(1), 1);
        graph.add_edge(NodeId(2), NodeId(7), 0);

        assert_eq!(graph.predecessors(NodeId(1)), vec![NodeId(2), NodeId(5)]);
        assert_eq!(graph.predecessors(NodeId(5)), vec![]);
    }

    #[test]
    fn add_node_replaces_the_node_under_an_id() {
        let mut graph = StackGraph::new();
        graph.add_node(NodeId(1), StackNode::Root);
        graph.add_node(NodeId(1), StackNode::Scope(StackScope::default()));

        assert_eq!(
            graph.nodes.get(&NodeId(1)),
            Some(&StackNode::Scope(StackScope::default()))
        );
        assert_eq!(graph.nodes.len(), 1);
    }
}