]>
Commit | Line | Data |
---|---|---|
9fa01778 XL |
1 | use crate::cfg::*; |
2 | use crate::middle::region; | |
8faf50e0 | 3 | use rustc_data_structures::graph::implementation as graph; |
9fa01778 | 4 | use crate::ty::{self, TyCtxt}; |
1a4d82fc | 5 | |
9fa01778 XL |
6 | use crate::hir::{self, PatKind}; |
7 | use crate::hir::def_id::DefId; | |
416331ca | 8 | use crate::hir::ptr::P; |
e9174d1e | 9 | |
dc9dc135 XL |
10 | struct CFGBuilder<'a, 'tcx> { |
11 | tcx: TyCtxt<'tcx>, | |
7cac9316 | 12 | owner_def_id: DefId, |
32a655c1 | 13 | tables: &'a ty::TypeckTables<'tcx>, |
1a4d82fc JJ |
14 | graph: CFGGraph, |
15 | fn_exit: CFGIndex, | |
16 | loop_scopes: Vec<LoopScope>, | |
cc61c64b XL |
17 | breakable_block_scopes: Vec<BlockScope>, |
18 | } | |
19 | ||
20 | #[derive(Copy, Clone)] | |
21 | struct BlockScope { | |
ea8adc8c | 22 | block_expr_id: hir::ItemLocalId, // id of breakable block expr node |
cc61c64b | 23 | break_index: CFGIndex, // where to go on `break` |
1a4d82fc JJ |
24 | } |
25 | ||
c34b1796 | 26 | #[derive(Copy, Clone)] |
1a4d82fc | 27 | struct LoopScope { |
ea8adc8c | 28 | loop_id: hir::ItemLocalId, // id of loop/while node |
1a4d82fc | 29 | continue_index: CFGIndex, // where to go on a `loop` |
cc61c64b | 30 | break_index: CFGIndex, // where to go on a `break` |
1a4d82fc JJ |
31 | } |
32 | ||
416331ca | 33 | pub fn construct(tcx: TyCtxt<'_>, body: &hir::Body) -> CFG { |
1a4d82fc | 34 | let mut graph = graph::Graph::new(); |
c34b1796 | 35 | let entry = graph.add_node(CFGNodeData::Entry); |
1a4d82fc JJ |
36 | |
37 | // `fn_exit` is target of return exprs, which lies somewhere | |
476ff2be | 38 | // outside input `body`. (Distinguishing `fn_exit` and `body_exit` |
1a4d82fc | 39 | // also resolves chicken-and-egg problem that arises if you try to |
476ff2be | 40 | // have return exprs jump to `body_exit` during construction.) |
c34b1796 | 41 | let fn_exit = graph.add_node(CFGNodeData::Exit); |
476ff2be | 42 | let body_exit; |
1a4d82fc | 43 | |
8bb4bdeb | 44 | // Find the tables for this body. |
dc9dc135 | 45 | let owner_def_id = tcx.hir().body_owner_def_id(body.id()); |
7cac9316 | 46 | let tables = tcx.typeck_tables_of(owner_def_id); |
32a655c1 | 47 | |
1a4d82fc | 48 | let mut cfg_builder = CFGBuilder { |
041b39d2 | 49 | tcx, |
7cac9316 | 50 | owner_def_id, |
041b39d2 XL |
51 | tables, |
52 | graph, | |
53 | fn_exit, | |
cc61c64b XL |
54 | loop_scopes: Vec::new(), |
55 | breakable_block_scopes: Vec::new(), | |
1a4d82fc | 56 | }; |
8bb4bdeb | 57 | body_exit = cfg_builder.expr(&body.value, entry); |
476ff2be | 58 | cfg_builder.add_contained_edge(body_exit, fn_exit); |
cc61c64b XL |
59 | let CFGBuilder { graph, .. } = cfg_builder; |
60 | CFG { | |
ea8adc8c | 61 | owner_def_id, |
041b39d2 XL |
62 | graph, |
63 | entry, | |
cc61c64b XL |
64 | exit: fn_exit, |
65 | } | |
1a4d82fc JJ |
66 | } |
67 | ||
1a4d82fc | 68 | impl<'a, 'tcx> CFGBuilder<'a, 'tcx> { |
e9174d1e | 69 | fn block(&mut self, blk: &hir::Block, pred: CFGIndex) -> CFGIndex { |
cc61c64b | 70 | if blk.targeted_by_break { |
ea8adc8c | 71 | let expr_exit = self.add_ast_node(blk.hir_id.local_id, &[]); |
cc61c64b XL |
72 | |
73 | self.breakable_block_scopes.push(BlockScope { | |
ea8adc8c | 74 | block_expr_id: blk.hir_id.local_id, |
cc61c64b XL |
75 | break_index: expr_exit, |
76 | }); | |
77 | ||
78 | let mut stmts_exit = pred; | |
79 | for stmt in &blk.stmts { | |
80 | stmts_exit = self.stmt(stmt, stmts_exit); | |
81 | } | |
82 | let blk_expr_exit = self.opt_expr(&blk.expr, stmts_exit); | |
83 | self.add_contained_edge(blk_expr_exit, expr_exit); | |
84 | ||
85 | self.breakable_block_scopes.pop(); | |
86 | ||
87 | expr_exit | |
88 | } else { | |
89 | let mut stmts_exit = pred; | |
90 | for stmt in &blk.stmts { | |
91 | stmts_exit = self.stmt(stmt, stmts_exit); | |
92 | } | |
1a4d82fc | 93 | |
cc61c64b | 94 | let expr_exit = self.opt_expr(&blk.expr, stmts_exit); |
1a4d82fc | 95 | |
ea8adc8c | 96 | self.add_ast_node(blk.hir_id.local_id, &[expr_exit]) |
cc61c64b | 97 | } |
1a4d82fc JJ |
98 | } |
99 | ||
e9174d1e | 100 | fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex { |
9fa01778 XL |
101 | let exit = match stmt.node { |
102 | hir::StmtKind::Local(ref local) => { | |
1a4d82fc | 103 | let init_exit = self.opt_expr(&local.init, pred); |
7453a54e | 104 | self.pat(&local.pat, init_exit) |
1a4d82fc | 105 | } |
9fa01778 XL |
106 | hir::StmtKind::Item(_) => { |
107 | pred | |
108 | } | |
109 | hir::StmtKind::Expr(ref expr) | | |
110 | hir::StmtKind::Semi(ref expr) => { | |
111 | self.expr(&expr, pred) | |
112 | } | |
113 | }; | |
114 | self.add_ast_node(stmt.hir_id.local_id, &[exit]) | |
1a4d82fc JJ |
115 | } |
116 | ||
e9174d1e | 117 | fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex { |
1a4d82fc | 118 | match pat.node { |
9e0c209e | 119 | PatKind::Binding(.., None) | |
476ff2be | 120 | PatKind::Path(_) | |
7453a54e SL |
121 | PatKind::Lit(..) | |
122 | PatKind::Range(..) | | |
ea8adc8c | 123 | PatKind::Wild => self.add_ast_node(pat.hir_id.local_id, &[pred]), |
1a4d82fc | 124 | |
7453a54e SL |
125 | PatKind::Box(ref subpat) | |
126 | PatKind::Ref(ref subpat, _) | | |
9e0c209e | 127 | PatKind::Binding(.., Some(ref subpat)) => { |
7453a54e | 128 | let subpat_exit = self.pat(&subpat, pred); |
ea8adc8c | 129 | self.add_ast_node(pat.hir_id.local_id, &[subpat_exit]) |
1a4d82fc JJ |
130 | } |
131 | ||
3157f602 XL |
132 | PatKind::TupleStruct(_, ref subpats, _) | |
133 | PatKind::Tuple(ref subpats, _) => { | |
1a4d82fc | 134 | let pats_exit = self.pats_all(subpats.iter(), pred); |
ea8adc8c | 135 | self.add_ast_node(pat.hir_id.local_id, &[pats_exit]) |
1a4d82fc JJ |
136 | } |
137 | ||
7453a54e | 138 | PatKind::Struct(_, ref subpats, _) => { |
cc61c64b | 139 | let pats_exit = self.pats_all(subpats.iter().map(|f| &f.node.pat), pred); |
ea8adc8c | 140 | self.add_ast_node(pat.hir_id.local_id, &[pats_exit]) |
1a4d82fc JJ |
141 | } |
142 | ||
c30ab7b3 | 143 | PatKind::Slice(ref pre, ref vec, ref post) => { |
1a4d82fc JJ |
144 | let pre_exit = self.pats_all(pre.iter(), pred); |
145 | let vec_exit = self.pats_all(vec.iter(), pre_exit); | |
146 | let post_exit = self.pats_all(post.iter(), vec_exit); | |
ea8adc8c | 147 | self.add_ast_node(pat.hir_id.local_id, &[post_exit]) |
1a4d82fc | 148 | } |
1a4d82fc JJ |
149 | } |
150 | } | |
151 | ||
9fa01778 XL |
152 | fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>( |
153 | &mut self, | |
154 | pats: I, | |
155 | pred: CFGIndex | |
156 | ) -> CFGIndex { | |
1a4d82fc | 157 | //! Handles case where all of the patterns must match. |
7453a54e | 158 | pats.fold(pred, |pred, pat| self.pat(&pat, pred)) |
1a4d82fc JJ |
159 | } |
160 | ||
e9174d1e | 161 | fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex { |
1a4d82fc | 162 | match expr.node { |
8faf50e0 | 163 | hir::ExprKind::Block(ref blk, _) => { |
7453a54e | 164 | let blk_exit = self.block(&blk, pred); |
ea8adc8c | 165 | self.add_ast_node(expr.hir_id.local_id, &[blk_exit]) |
1a4d82fc JJ |
166 | } |
167 | ||
8faf50e0 | 168 | hir::ExprKind::Loop(ref body, _, _) => { |
1a4d82fc JJ |
169 | // |
170 | // [pred] | |
171 | // | | |
172 | // v 1 | |
173 | // [loopback] <---+ | |
174 | // | 4 | | |
175 | // v 3 | | |
176 | // [body] ------+ | |
177 | // | |
178 | // [expr] 2 | |
179 | // | |
180 | // Note that `break` and `loop` statements | |
181 | // may cause additional edges. | |
182 | ||
183 | let loopback = self.add_dummy_node(&[pred]); // 1 | |
ea8adc8c | 184 | let expr_exit = self.add_ast_node(expr.hir_id.local_id, &[]); // 2 |
1a4d82fc | 185 | self.loop_scopes.push(LoopScope { |
ea8adc8c | 186 | loop_id: expr.hir_id.local_id, |
1a4d82fc JJ |
187 | continue_index: loopback, |
188 | break_index: expr_exit, | |
189 | }); | |
7453a54e | 190 | let body_exit = self.block(&body, loopback); // 3 |
1a4d82fc JJ |
191 | self.add_contained_edge(body_exit, loopback); // 4 |
192 | self.loop_scopes.pop(); | |
193 | expr_exit | |
194 | } | |
195 | ||
8faf50e0 | 196 | hir::ExprKind::Match(ref discr, ref arms, _) => { |
ea8adc8c | 197 | self.match_(expr.hir_id.local_id, &discr, &arms, pred) |
1a4d82fc JJ |
198 | } |
199 | ||
8faf50e0 | 200 | hir::ExprKind::Binary(op, ref l, ref r) if op.node.is_lazy() => { |
1a4d82fc JJ |
201 | // |
202 | // [pred] | |
203 | // | | |
204 | // v 1 | |
205 | // [l] | |
206 | // | | |
207 | // / \ | |
208 | // / \ | |
209 | // v 2 * | |
210 | // [r] | | |
211 | // | | | |
212 | // v 3 v 4 | |
213 | // [..exit..] | |
214 | // | |
7453a54e SL |
215 | let l_exit = self.expr(&l, pred); // 1 |
216 | let r_exit = self.expr(&r, l_exit); // 2 | |
ea8adc8c | 217 | self.add_ast_node(expr.hir_id.local_id, &[l_exit, r_exit]) // 3,4 |
1a4d82fc JJ |
218 | } |
219 | ||
8faf50e0 | 220 | hir::ExprKind::Ret(ref v) => { |
1a4d82fc | 221 | let v_exit = self.opt_expr(v, pred); |
ea8adc8c | 222 | let b = self.add_ast_node(expr.hir_id.local_id, &[v_exit]); |
1a4d82fc | 223 | self.add_returning_edge(expr, b); |
c34b1796 | 224 | self.add_unreachable_node() |
1a4d82fc JJ |
225 | } |
226 | ||
8faf50e0 | 227 | hir::ExprKind::Break(destination, ref opt_expr) => { |
476ff2be | 228 | let v = self.opt_expr(opt_expr, pred); |
ea8adc8c | 229 | let (target_scope, break_dest) = |
cc61c64b | 230 | self.find_scope_edge(expr, destination, ScopeCfKind::Break); |
ea8adc8c XL |
231 | let b = self.add_ast_node(expr.hir_id.local_id, &[v]); |
232 | self.add_exiting_edge(expr, b, target_scope, break_dest); | |
c34b1796 | 233 | self.add_unreachable_node() |
1a4d82fc JJ |
234 | } |
235 | ||
8faf50e0 | 236 | hir::ExprKind::Continue(destination) => { |
ea8adc8c | 237 | let (target_scope, cont_dest) = |
cc61c64b | 238 | self.find_scope_edge(expr, destination, ScopeCfKind::Continue); |
ea8adc8c XL |
239 | let a = self.add_ast_node(expr.hir_id.local_id, &[pred]); |
240 | self.add_exiting_edge(expr, a, target_scope, cont_dest); | |
c34b1796 | 241 | self.add_unreachable_node() |
1a4d82fc JJ |
242 | } |
243 | ||
8faf50e0 | 244 | hir::ExprKind::Array(ref elems) => { |
476ff2be | 245 | self.straightline(expr, pred, elems.iter().map(|e| &*e)) |
1a4d82fc JJ |
246 | } |
247 | ||
8faf50e0 | 248 | hir::ExprKind::Call(ref func, ref args) => { |
476ff2be | 249 | self.call(expr, pred, &func, args.iter().map(|e| &*e)) |
1a4d82fc JJ |
250 | } |
251 | ||
8faf50e0 | 252 | hir::ExprKind::MethodCall(.., ref args) => { |
476ff2be | 253 | self.call(expr, pred, &args[0], args[1..].iter().map(|e| &*e)) |
1a4d82fc JJ |
254 | } |
255 | ||
8faf50e0 XL |
256 | hir::ExprKind::Index(ref l, ref r) | |
257 | hir::ExprKind::Binary(_, ref l, ref r) if self.tables.is_method_call(expr) => { | |
7453a54e | 258 | self.call(expr, pred, &l, Some(&**r).into_iter()) |
1a4d82fc JJ |
259 | } |
260 | ||
8faf50e0 | 261 | hir::ExprKind::Unary(_, ref e) if self.tables.is_method_call(expr) => { |
7453a54e | 262 | self.call(expr, pred, &e, None::<hir::Expr>.iter()) |
1a4d82fc JJ |
263 | } |
264 | ||
8faf50e0 | 265 | hir::ExprKind::Tup(ref exprs) => { |
476ff2be | 266 | self.straightline(expr, pred, exprs.iter().map(|e| &*e)) |
1a4d82fc JJ |
267 | } |
268 | ||
8faf50e0 | 269 | hir::ExprKind::Struct(_, ref fields, ref base) => { |
1a4d82fc JJ |
270 | let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr)); |
271 | self.opt_expr(base, field_cfg) | |
272 | } | |
273 | ||
8faf50e0 XL |
274 | hir::ExprKind::Assign(ref l, ref r) | |
275 | hir::ExprKind::AssignOp(_, ref l, ref r) => { | |
1a4d82fc JJ |
276 | self.straightline(expr, pred, [r, l].iter().map(|&e| &**e)) |
277 | } | |
278 | ||
8faf50e0 | 279 | hir::ExprKind::Index(ref l, ref r) | |
0731742a | 280 | hir::ExprKind::Binary(_, ref l, ref r) => { // N.B., && and || handled earlier |
1a4d82fc JJ |
281 | self.straightline(expr, pred, [l, r].iter().map(|&e| &**e)) |
282 | } | |
283 | ||
8faf50e0 XL |
284 | hir::ExprKind::Box(ref e) | |
285 | hir::ExprKind::AddrOf(_, ref e) | | |
286 | hir::ExprKind::Cast(ref e, _) | | |
287 | hir::ExprKind::Type(ref e, _) | | |
48663c56 | 288 | hir::ExprKind::DropTemps(ref e) | |
8faf50e0 XL |
289 | hir::ExprKind::Unary(_, ref e) | |
290 | hir::ExprKind::Field(ref e, _) | | |
dc9dc135 | 291 | hir::ExprKind::Yield(ref e, _) | |
8faf50e0 | 292 | hir::ExprKind::Repeat(ref e, _) => { |
1a4d82fc JJ |
293 | self.straightline(expr, pred, Some(&**e).into_iter()) |
294 | } | |
295 | ||
8faf50e0 | 296 | hir::ExprKind::InlineAsm(_, ref outputs, ref inputs) => { |
476ff2be SL |
297 | let post_outputs = self.exprs(outputs.iter().map(|e| &*e), pred); |
298 | let post_inputs = self.exprs(inputs.iter().map(|e| &*e), post_outputs); | |
ea8adc8c | 299 | self.add_ast_node(expr.hir_id.local_id, &[post_inputs]) |
1a4d82fc JJ |
300 | } |
301 | ||
8faf50e0 XL |
302 | hir::ExprKind::Closure(..) | |
303 | hir::ExprKind::Lit(..) | | |
0731742a XL |
304 | hir::ExprKind::Path(_) | |
305 | hir::ExprKind::Err => { | |
e9174d1e | 306 | self.straightline(expr, pred, None::<hir::Expr>.iter()) |
1a4d82fc JJ |
307 | } |
308 | } | |
309 | } | |
310 | ||
e9174d1e SL |
311 | fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self, |
312 | call_expr: &hir::Expr, | |
1a4d82fc | 313 | pred: CFGIndex, |
e9174d1e | 314 | func_or_rcvr: &hir::Expr, |
1a4d82fc | 315 | args: I) -> CFGIndex { |
1a4d82fc JJ |
316 | let func_or_rcvr_exit = self.expr(func_or_rcvr, pred); |
317 | let ret = self.straightline(call_expr, func_or_rcvr_exit, args); | |
dc9dc135 | 318 | let m = self.tcx.hir().get_module_parent(call_expr.hir_id); |
0731742a | 319 | if self.tcx.is_ty_uninhabited_from(m, self.tables.expr_ty(call_expr)) { |
c34b1796 | 320 | self.add_unreachable_node() |
1a4d82fc JJ |
321 | } else { |
322 | ret | |
323 | } | |
324 | } | |
325 | ||
e9174d1e | 326 | fn exprs<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self, |
1a4d82fc JJ |
327 | exprs: I, |
328 | pred: CFGIndex) -> CFGIndex { | |
329 | //! Constructs graph for `exprs` evaluated in order | |
330 | exprs.fold(pred, |p, e| self.expr(e, p)) | |
331 | } | |
332 | ||
333 | fn opt_expr(&mut self, | |
e9174d1e | 334 | opt_expr: &Option<P<hir::Expr>>, |
1a4d82fc JJ |
335 | pred: CFGIndex) -> CFGIndex { |
336 | //! Constructs graph for `opt_expr` evaluated, if Some | |
7453a54e | 337 | opt_expr.iter().fold(pred, |p, e| self.expr(&e, p)) |
1a4d82fc JJ |
338 | } |
339 | ||
e9174d1e SL |
340 | fn straightline<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self, |
341 | expr: &hir::Expr, | |
1a4d82fc JJ |
342 | pred: CFGIndex, |
343 | subexprs: I) -> CFGIndex { | |
344 | //! Handles case of an expression that evaluates `subexprs` in order | |
345 | ||
346 | let subexprs_exit = self.exprs(subexprs, pred); | |
ea8adc8c | 347 | self.add_ast_node(expr.hir_id.local_id, &[subexprs_exit]) |
c34b1796 AL |
348 | } |
349 | ||
ea8adc8c | 350 | fn match_(&mut self, id: hir::ItemLocalId, discr: &hir::Expr, |
e9174d1e | 351 | arms: &[hir::Arm], pred: CFGIndex) -> CFGIndex { |
c34b1796 AL |
352 | // The CFG for match expression is quite complex, so no ASCII |
353 | // art for it (yet). | |
354 | // | |
94b46f34 XL |
355 | // The CFG generated below matches roughly what MIR contains. |
356 | // Each pattern and guard is visited in parallel, with | |
c34b1796 AL |
357 | // arms containing multiple patterns generating multiple nodes |
358 | // for the same guard expression. The guard expressions chain | |
359 | // into each other from top to bottom, with a specific | |
360 | // exception to allow some additional valid programs | |
94b46f34 | 361 | // (explained below). MIR differs slightly in that the |
c34b1796 AL |
362 | // pattern matching may continue after a guard but the visible |
363 | // behaviour should be the same. | |
364 | // | |
365 | // What is going on is explained in further comments. | |
366 | ||
367 | // Visit the discriminant expression | |
368 | let discr_exit = self.expr(discr, pred); | |
369 | ||
370 | // Add a node for the exit of the match expression as a whole. | |
371 | let expr_exit = self.add_ast_node(id, &[]); | |
372 | ||
373 | // Keep track of the previous guard expressions | |
416331ca XL |
374 | let mut prev_guard = None; |
375 | let match_scope = region::Scope { id, data: region::ScopeData::Node }; | |
c34b1796 AL |
376 | |
377 | for arm in arms { | |
378 | // Add an exit node for when we've visited all the | |
379 | // patterns and the guard (if there is one) in the arm. | |
dc9dc135 | 380 | let bindings_exit = self.add_dummy_node(&[]); |
c34b1796 AL |
381 | |
382 | for pat in &arm.pats { | |
383 | // Visit the pattern, coming from the discriminant exit | |
7453a54e | 384 | let mut pat_exit = self.pat(&pat, discr_exit); |
c34b1796 AL |
385 | |
386 | // If there is a guard expression, handle it here | |
387 | if let Some(ref guard) = arm.guard { | |
388 | // Add a dummy node for the previous guard | |
389 | // expression to target | |
390 | let guard_start = self.add_dummy_node(&[pat_exit]); | |
391 | // Visit the guard expression | |
b7449926 | 392 | let guard_exit = match guard { |
416331ca | 393 | hir::Guard::If(ref e) => (&**e, self.expr(e, guard_start)), |
b7449926 | 394 | }; |
83c7162d XL |
395 | // #47295: We used to have very special case code |
396 | // here for when a pair of arms are both formed | |
397 | // solely from constants, and if so, not add these | |
398 | // edges. But this was not actually sound without | |
399 | // other constraints that we stopped enforcing at | |
400 | // some point. | |
416331ca XL |
401 | if let Some((prev_guard, prev_index)) = prev_guard.take() { |
402 | self.add_exiting_edge(prev_guard, prev_index, match_scope, guard_start); | |
c34b1796 AL |
403 | } |
404 | ||
c34b1796 | 405 | // Push the guard onto the list of previous guards |
416331ca | 406 | prev_guard = Some(guard_exit); |
c34b1796 AL |
407 | |
408 | // Update the exit node for the pattern | |
416331ca | 409 | pat_exit = guard_exit.1; |
c34b1796 AL |
410 | } |
411 | ||
412 | // Add an edge from the exit of this pattern to the | |
413 | // exit of the arm | |
dc9dc135 | 414 | self.add_contained_edge(pat_exit, bindings_exit); |
c34b1796 AL |
415 | } |
416 | ||
417 | // Visit the body of this arm | |
dc9dc135 XL |
418 | let body_exit = self.expr(&arm.body, bindings_exit); |
419 | ||
420 | let arm_exit = self.add_ast_node(arm.hir_id.local_id, &[body_exit]); | |
c34b1796 AL |
421 | |
422 | // Link the body to the exit of the expression | |
dc9dc135 | 423 | self.add_contained_edge(arm_exit, expr_exit); |
c34b1796 AL |
424 | } |
425 | ||
426 | expr_exit | |
1a4d82fc JJ |
427 | } |
428 | ||
429 | fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex { | |
c34b1796 | 430 | self.add_node(CFGNodeData::Dummy, preds) |
1a4d82fc JJ |
431 | } |
432 | ||
ea8adc8c | 433 | fn add_ast_node(&mut self, id: hir::ItemLocalId, preds: &[CFGIndex]) -> CFGIndex { |
c34b1796 AL |
434 | self.add_node(CFGNodeData::AST(id), preds) |
435 | } | |
436 | ||
437 | fn add_unreachable_node(&mut self) -> CFGIndex { | |
438 | self.add_node(CFGNodeData::Unreachable, &[]) | |
439 | } | |
440 | ||
441 | fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex { | |
442 | let node = self.graph.add_node(data); | |
85aaf69f | 443 | for &pred in preds { |
1a4d82fc JJ |
444 | self.add_contained_edge(pred, node); |
445 | } | |
446 | node | |
447 | } | |
448 | ||
449 | fn add_contained_edge(&mut self, | |
450 | source: CFGIndex, | |
451 | target: CFGIndex) { | |
c30ab7b3 | 452 | let data = CFGEdgeData {exiting_scopes: vec![] }; |
1a4d82fc JJ |
453 | self.graph.add_edge(source, target, data); |
454 | } | |
455 | ||
456 | fn add_exiting_edge(&mut self, | |
e9174d1e | 457 | from_expr: &hir::Expr, |
1a4d82fc | 458 | from_index: CFGIndex, |
ea8adc8c | 459 | target_scope: region::Scope, |
1a4d82fc | 460 | to_index: CFGIndex) { |
cc61c64b | 461 | let mut data = CFGEdgeData { exiting_scopes: vec![] }; |
b7449926 XL |
462 | let mut scope = region::Scope { |
463 | id: from_expr.hir_id.local_id, | |
464 | data: region::ScopeData::Node | |
465 | }; | |
ea8adc8c | 466 | let region_scope_tree = self.tcx.region_scope_tree(self.owner_def_id); |
1a4d82fc | 467 | while scope != target_scope { |
ea8adc8c XL |
468 | data.exiting_scopes.push(scope.item_local_id()); |
469 | scope = region_scope_tree.encl_scope(scope); | |
1a4d82fc JJ |
470 | } |
471 | self.graph.add_edge(from_index, to_index, data); | |
472 | } | |
473 | ||
474 | fn add_returning_edge(&mut self, | |
e9174d1e | 475 | _from_expr: &hir::Expr, |
1a4d82fc | 476 | from_index: CFGIndex) { |
8faf50e0 XL |
477 | let data = CFGEdgeData { |
478 | exiting_scopes: self.loop_scopes.iter() | |
479 | .rev() | |
480 | .map(|&LoopScope { loop_id: id, .. }| id) | |
481 | .collect() | |
1a4d82fc | 482 | }; |
1a4d82fc JJ |
483 | self.graph.add_edge(from_index, self.fn_exit, data); |
484 | } | |
485 | ||
cc61c64b | 486 | fn find_scope_edge(&self, |
e9174d1e | 487 | expr: &hir::Expr, |
cc61c64b | 488 | destination: hir::Destination, |
ea8adc8c | 489 | scope_cf_kind: ScopeCfKind) -> (region::Scope, CFGIndex) { |
cc61c64b XL |
490 | |
491 | match destination.target_id { | |
94b46f34 | 492 | Ok(loop_id) => { |
cc61c64b | 493 | for b in &self.breakable_block_scopes { |
532ac7d7 | 494 | if b.block_expr_id == loop_id.local_id { |
b7449926 | 495 | let scope = region::Scope { |
532ac7d7 | 496 | id: loop_id.local_id, |
b7449926 XL |
497 | data: region::ScopeData::Node |
498 | }; | |
499 | return (scope, match scope_cf_kind { | |
cc61c64b XL |
500 | ScopeCfKind::Break => b.break_index, |
501 | ScopeCfKind::Continue => bug!("can't continue to block"), | |
502 | }); | |
503 | } | |
504 | } | |
c34b1796 | 505 | for l in &self.loop_scopes { |
532ac7d7 | 506 | if l.loop_id == loop_id.local_id { |
b7449926 | 507 | let scope = region::Scope { |
532ac7d7 | 508 | id: loop_id.local_id, |
b7449926 XL |
509 | data: region::ScopeData::Node |
510 | }; | |
511 | return (scope, match scope_cf_kind { | |
cc61c64b XL |
512 | ScopeCfKind::Break => l.break_index, |
513 | ScopeCfKind::Continue => l.continue_index, | |
514 | }); | |
1a4d82fc JJ |
515 | } |
516 | } | |
94b46f34 | 517 | span_bug!(expr.span, "no scope for id {}", loop_id); |
1a4d82fc | 518 | } |
94b46f34 | 519 | Err(err) => span_bug!(expr.span, "scope error: {}", err), |
1a4d82fc JJ |
520 | } |
521 | } | |
1a4d82fc | 522 | } |
cc61c64b XL |
523 | |
524 | #[derive(Copy, Clone, Eq, PartialEq)] | |
525 | enum ScopeCfKind { | |
526 | Break, | |
527 | Continue, | |
528 | } |