smpl/analysis/
unique_linear_cfg_traversal.rs

1use petgraph::graph::NodeIndex;
2
3use super::control_data::*;
4use super::control_flow::*;
5
6pub trait UniquePassenger<E> {
7    fn start(&mut self, id: NodeIndex) -> Result<(), E>;
8    fn end(&mut self, id: NodeIndex) -> Result<(), E>;
9    fn loop_head(
10        &mut self,
11        id: NodeIndex,
12        ld: &mut LoopData,
13        expr: &mut ExprData,
14    ) -> Result<(), E>;
15    fn loop_foot(&mut self, id: NodeIndex, ld: &mut LoopData) -> Result<(), E>;
16    fn cont(&mut self, id: NodeIndex, ld: &mut LoopData) -> Result<(), E>;
17    fn br(&mut self, id: NodeIndex, ld: &mut LoopData) -> Result<(), E>;
18    fn enter_scope(&mut self, id: NodeIndex) -> Result<(), E>;
19    fn exit_scope(&mut self, id: NodeIndex) -> Result<(), E>;
20    fn local_var_decl(
21        &mut self,
22        id: NodeIndex,
23        decl: &mut LocalVarDeclData,
24    ) -> Result<(), E>;
25    fn assignment(
26        &mut self,
27        id: NodeIndex,
28        assign: &mut AssignmentData,
29    ) -> Result<(), E>;
30    fn expr(&mut self, id: NodeIndex, expr: &mut ExprData) -> Result<(), E>;
31    fn ret(&mut self, id: NodeIndex, rdata: &mut ReturnData) -> Result<(), E>;
32
33    fn loop_start_true_path(&mut self, id: NodeIndex) -> Result<(), E>;
34    fn loop_end_true_path(&mut self, id: NodeIndex) -> Result<(), E>;
35
36    fn branch_split(
37        &mut self,
38        id: NodeIndex,
39        b: &mut BranchingData,
40        e: &mut ExprData,
41    ) -> Result<(), E>;
42    fn branch_merge(
43        &mut self,
44        id: NodeIndex,
45        b: &mut BranchingData,
46    ) -> Result<(), E>;
47    fn branch_start_true_path(&mut self, id: NodeIndex) -> Result<(), E>;
48    fn branch_start_false_path(&mut self, id: NodeIndex) -> Result<(), E>;
49    fn branch_end_true_path(
50        &mut self,
51        id: NodeIndex,
52        b: &mut BranchingData,
53    ) -> Result<(), E>;
54    fn branch_end_false_path(
55        &mut self,
56        id: NodeIndex,
57        b: &mut BranchingData,
58    ) -> Result<(), E>;
59}
60
61pub fn traverse<E>(
62    graph: &mut CFG,
63    passenger: &mut dyn UniquePassenger<E>,
64) -> Result<(), E> {
65    let mut current = Some(graph.start());
66    let node_count = graph.graph().node_count();
67
68    // Traverser::visit_node should be called AT MAX the number of nodes in the graph
69    for _ in 0..node_count {
70        match current {
71            Some(to_visit) => current = visit_node(graph, to_visit, passenger)?,
72            None => break,
73        }
74    }
75
76    if current.is_some() {
77        panic!("Graph traversal error. Node::End should have returned None. If Node::End was reached, this panic should not be triggered.")
78    }
79
80    Ok(())
81}
82
83fn visit_node<E>(
84    graph: &mut CFG,
85    current: NodeIndex,
86    passenger: &mut dyn UniquePassenger<E>,
87) -> Result<Option<NodeIndex>, E> {
88    let node_count = graph.graph().node_count();
89    match graph.node_weight_mut(current) {
90        Node::End => {
91            passenger.end(current)?;
92            Ok(None)
93        }
94
95        Node::Start => {
96            passenger.start(current)?;
97            Ok(Some(graph.next(current)))
98        }
99
100        Node::BranchSplit(ref mut branch_data, ref mut expr_data) => {
101            passenger.branch_split(current, branch_data, expr_data)?;
102
103            let (true_path, false_path) = graph.after_conditional(current);
104
105            passenger.branch_start_true_path(true_path)?;
106
107            let mut merge = None;
108
109            // True path
110            let mut current_node = true_path;
111            for _ in 0..node_count {
112                match graph.node_weight_mut(current_node) {
113                    Node::BranchMerge(ref mut branch_data) => {
114                        passenger
115                            .branch_end_true_path(current_node, branch_data)?;
116                        merge = Some(current_node);
117                        break;
118                    }
119
120                    _ => (),
121                }
122
123                match visit_node(graph, current_node, passenger)? {
124                    Some(next) => current_node = next,
125                    None => break,
126                }
127            }
128
129            if merge.is_none() {
130                panic!("Traversed entire graph and did not find Condition::BranchMerge");
131            }
132
133            passenger.branch_start_false_path(false_path)?;
134
135            // False path
136            let mut current_node = false_path;
137            let mut merge = None;
138            for _ in 0..node_count {
139                match graph.node_weight_mut(current_node) {
140                    Node::BranchMerge(ref mut branch_data) => {
141                        passenger
142                            .branch_end_false_path(current_node, branch_data)?;
143                        passenger.branch_merge(current_node, branch_data)?;
144                        merge = Some(current_node);
145                        break;
146                    }
147
148                    _ => (),
149                }
150
151                match visit_node(graph, current_node, passenger)? {
152                    Some(next) => current_node = next,
153                    None => panic!(),
154                }
155            }
156
157            if merge.is_none() {
158                panic!("Traversed entire graph and did not find Condition::BranchMerge");
159            }
160
161            Ok(Some(graph.next(merge.unwrap())))
162        }
163
164        Node::BranchMerge(ref mut _branch_data) => {
165            unreachable!();
166        }
167
168        Node::LoopHead(ref mut branch_data, ref mut expr_data) => {
169            passenger.loop_head(current, branch_data, expr_data)?;
170            let (true_path, false_path) = graph.after_conditional(current);
171            passenger.loop_start_true_path(true_path)?;
172
173            let mut current_node = true_path;
174            let mut found_foot = false;
175            for _ in 0..node_count {
176                match graph.node_weight_mut(current_node) {
177                    Node::LoopFoot(ref mut loop_data) => {
178                        passenger.loop_end_true_path(current_node)?;
179                        passenger.loop_foot(current_node, loop_data)?;
180                        found_foot = true;
181                        break;
182                    }
183
184                    _ => (),
185                }
186
187                match visit_node(graph, current_node, passenger)? {
188                    Some(next) => current_node = next,
189                    None => return Ok(None),
190                }
191            }
192
193            if found_foot == false {
194                panic!(
195                    "Traversed the rest of the graph but did not find a Node::LoopFoot."
196                );
197            }
198
199            match graph.node_weight_mut(false_path) {
200                Node::LoopFoot(_) => (),
201                ref mut n @ _ => println!("Loop condition should be connected to Node::LoopFoot along the false path. Found {:?}.", n),
202            }
203
204            Ok(Some(graph.after_loop_foot(false_path)))
205        }
206
207        Node::LoopFoot(ref mut _data) => {
208            unreachable!();
209        }
210
211        Node::Continue(ref mut data) => {
212            passenger.cont(current, data)?;
213            Ok(Some(graph.after_continue(current)))
214        }
215
216        Node::Break(ref mut data) => {
217            passenger.br(current, data)?;
218            Ok(Some(graph.after_break(current)))
219        }
220
221        Node::EnterScope => {
222            passenger.enter_scope(current)?;
223            Ok(Some(graph.next(current)))
224        }
225
226        Node::ExitScope => {
227            passenger.exit_scope(current)?;
228            Ok(Some(graph.next(current)))
229        }
230
231        Node::Block(ref mut basic_block) => {
232            for n in basic_block.graph_mut() {
233                match *n {
234                    BlockNode::LocalVarDecl(ref mut decl) => {
235                        passenger.local_var_decl(current, decl)?;
236                    }
237
238                    BlockNode::Assignment(ref mut assign) => {
239                        passenger.assignment(current, assign)?;
240                    }
241
242                    BlockNode::Expr(ref mut expr) => {
243                        passenger.expr(current, expr)?;
244                    }
245                }
246            }
247
248            Ok(Some(graph.next(current)))
249        }
250
251        Node::Return(ref mut rdata) => {
252            passenger.ret(current, rdata)?;
253            Ok(Some(graph.after_return(current)))
254        }
255    }
256}
smpl/analysis/unique_linear_cfg_traversal.rs

smpl/analysis/
unique_linear_cfg_traversal.rs
