fluidattacks_blends_domain/path_search/
utils.rs

1//! Counterpart of `blends/path_search/utils.py`.
2
3use alloc::vec;
4use alloc::vec::Vec;
5
6use crate::path_search::Path;
7use crate::query::{lookup_first_cfg_parent, pred_cfg};
8use crate::syntax::SyntaxGraph;
9use crate::NodeId;
10
11pub struct BackwardPaths<'a> {
12    graph: &'a SyntaxGraph,
13    stack: Vec<Path>,
14}
15
16impl Iterator for BackwardPaths<'_> {
17    type Item = Path;
18
19    fn next(&mut self) -> Option<Self::Item> {
20        while let Some(path) = self.stack.pop() {
21            let Some(&tail) = path.last() else {
22                continue;
23            };
24            let parents: Vec<NodeId> = pred_cfg(self.graph, tail, None)
25                .into_iter()
26                .filter(|parent| !path.contains(parent))
27                .collect();
28            if parents.is_empty() {
29                return Some(path);
30            }
31            for parent in parents.into_iter().rev() {
32                let mut next = path.clone();
33                next.push(parent);
34                self.stack.push(next);
35            }
36        }
37        None
38    }
39}
40
41#[must_use]
42pub fn iter_backward_paths(graph: &SyntaxGraph, cfg_n_id: NodeId) -> BackwardPaths<'_> {
43    BackwardPaths {
44        graph,
45        stack: vec![vec![cfg_n_id]],
46    }
47}
48
49#[must_use]
50pub fn get_backward_paths(graph: &SyntaxGraph, n_id: NodeId, limit: Option<usize>) -> Vec<Path> {
51    let cfg_id = lookup_first_cfg_parent(graph, n_id);
52    let paths = iter_backward_paths(graph, cfg_id);
53    match limit.filter(|&value| value != 0) {
54        Some(value) => paths.take(value.saturating_sub(1)).collect(),
55        None => paths.collect(),
56    }
57}
58
59#[cfg(test)]
60mod tests {
61    use super::{get_backward_paths, iter_backward_paths};
62    use crate::syntax::{SyntaxGraph, SyntaxNode};
63    use crate::NodeId;
64    use alloc::vec::Vec;
65
66    fn node(graph: &mut SyntaxGraph, id: u64) {
67        graph.add_node(NodeId(id), SyntaxNode::ExecutionBlock);
68    }
69
70    #[test]
71    fn linear_chain_yields_one_path_to_the_root() {
72        let mut graph = SyntaxGraph::new();
73        node(&mut graph, 1);
74        node(&mut graph, 2);
75        node(&mut graph, 3);
76        graph.add_cfg_edge(NodeId(1), NodeId(2));
77        graph.add_cfg_edge(NodeId(2), NodeId(3));
78
79        assert_eq!(
80            get_backward_paths(&graph, NodeId(3), Some(100)),
81            [[NodeId(3), NodeId(2), NodeId(1)]]
82        );
83    }
84
85    #[test]
86    fn iter_yields_every_path_unbounded_from_the_given_cfg_node() {
87        let mut graph = SyntaxGraph::new();
88        node(&mut graph, 1);
89        node(&mut graph, 2);
90        node(&mut graph, 3);
91        graph.add_cfg_edge(NodeId(1), NodeId(3));
92        graph.add_cfg_edge(NodeId(2), NodeId(3));
93
94        let paths: Vec<_> = iter_backward_paths(&graph, NodeId(3)).collect();
95        assert_eq!(
96            paths,
97            [vec![NodeId(3), NodeId(1)], vec![NodeId(3), NodeId(2)],]
98        );
99    }
100
101    #[test]
102    fn a_branch_upstream_yields_one_path_per_predecessor_in_id_order() {
103        let mut graph = SyntaxGraph::new();
104        node(&mut graph, 1);
105        node(&mut graph, 2);
106        node(&mut graph, 3);
107        node(&mut graph, 4);
108        graph.add_cfg_edge(NodeId(1), NodeId(3));
109        graph.add_cfg_edge(NodeId(2), NodeId(3));
110        graph.add_cfg_edge(NodeId(3), NodeId(4));
111
112        assert_eq!(
113            get_backward_paths(&graph, NodeId(4), Some(100)),
114            [
115                vec![NodeId(4), NodeId(3), NodeId(1)],
116                vec![NodeId(4), NodeId(3), NodeId(2)],
117            ]
118        );
119    }
120
121    #[test]
122    fn a_back_edge_cycle_terminates() {
123        let mut graph = SyntaxGraph::new();
124        node(&mut graph, 1);
125        node(&mut graph, 2);
126        graph.add_cfg_edge(NodeId(1), NodeId(2));
127        graph.add_cfg_edge(NodeId(2), NodeId(1));
128
129        assert_eq!(
130            get_backward_paths(&graph, NodeId(2), Some(100)),
131            [[NodeId(2), NodeId(1)]]
132        );
133    }
134
135    #[test]
136    fn the_limit_caps_the_number_of_paths() {
137        let mut graph = SyntaxGraph::new();
138        for id in 1..=4 {
139            node(&mut graph, id);
140        }
141        graph.add_cfg_edge(NodeId(1), NodeId(4));
142        graph.add_cfg_edge(NodeId(2), NodeId(4));
143        graph.add_cfg_edge(NodeId(3), NodeId(4));
144
145        assert_eq!(get_backward_paths(&graph, NodeId(4), Some(3)).len(), 2);
146    }
147
148    #[test]
149    fn a_none_limit_returns_every_path_unbounded() {
150        let mut graph = SyntaxGraph::new();
151        node(&mut graph, 1);
152        node(&mut graph, 2);
153        node(&mut graph, 3);
154        graph.add_cfg_edge(NodeId(1), NodeId(3));
155        graph.add_cfg_edge(NodeId(2), NodeId(3));
156
157        assert_eq!(
158            get_backward_paths(&graph, NodeId(3), None),
159            [vec![NodeId(3), NodeId(1)], vec![NodeId(3), NodeId(2)]]
160        );
161    }
162}
fluidattacks_blends_domain/path_search/utils.rs

fluidattacks_blends_domain/path_search/
utils.rs
