]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
d9579d0f | 11 | use rustc_data_structures::graph; |
1a4d82fc | 12 | use middle::cfg::*; |
7453a54e | 13 | use middle::def::Def; |
c34b1796 | 14 | use middle::pat_util; |
1a4d82fc JJ |
15 | use middle::ty; |
16 | use syntax::ast; | |
1a4d82fc | 17 | use syntax::ptr::P; |
1a4d82fc | 18 | |
7453a54e | 19 | use rustc_front::hir::{self, PatKind}; |
e9174d1e | 20 | |
1a4d82fc JJ |
21 | struct CFGBuilder<'a, 'tcx: 'a> { |
22 | tcx: &'a ty::ctxt<'tcx>, | |
1a4d82fc JJ |
23 | graph: CFGGraph, |
24 | fn_exit: CFGIndex, | |
25 | loop_scopes: Vec<LoopScope>, | |
26 | } | |
27 | ||
c34b1796 | 28 | #[derive(Copy, Clone)] |
1a4d82fc JJ |
29 | struct LoopScope { |
30 | loop_id: ast::NodeId, // id of loop/while node | |
31 | continue_index: CFGIndex, // where to go on a `loop` | |
32 | break_index: CFGIndex, // where to go on a `break | |
33 | } | |
34 | ||
35 | pub fn construct(tcx: &ty::ctxt, | |
e9174d1e | 36 | blk: &hir::Block) -> CFG { |
1a4d82fc | 37 | let mut graph = graph::Graph::new(); |
c34b1796 | 38 | let entry = graph.add_node(CFGNodeData::Entry); |
1a4d82fc JJ |
39 | |
40 | // `fn_exit` is target of return exprs, which lies somewhere | |
41 | // outside input `blk`. (Distinguishing `fn_exit` and `block_exit` | |
42 | // also resolves chicken-and-egg problem that arises if you try to | |
43 | // have return exprs jump to `block_exit` during construction.) | |
c34b1796 | 44 | let fn_exit = graph.add_node(CFGNodeData::Exit); |
1a4d82fc JJ |
45 | let block_exit; |
46 | ||
47 | let mut cfg_builder = CFGBuilder { | |
1a4d82fc JJ |
48 | graph: graph, |
49 | fn_exit: fn_exit, | |
50 | tcx: tcx, | |
51 | loop_scopes: Vec::new() | |
52 | }; | |
53 | block_exit = cfg_builder.block(blk, entry); | |
54 | cfg_builder.add_contained_edge(block_exit, fn_exit); | |
c34b1796 AL |
55 | let CFGBuilder {graph, ..} = cfg_builder; |
56 | CFG {graph: graph, | |
1a4d82fc JJ |
57 | entry: entry, |
58 | exit: fn_exit} | |
59 | } | |
60 | ||
1a4d82fc | 61 | impl<'a, 'tcx> CFGBuilder<'a, 'tcx> { |
e9174d1e | 62 | fn block(&mut self, blk: &hir::Block, pred: CFGIndex) -> CFGIndex { |
1a4d82fc | 63 | let mut stmts_exit = pred; |
85aaf69f | 64 | for stmt in &blk.stmts { |
92a42be0 | 65 | stmts_exit = self.stmt(stmt, stmts_exit); |
1a4d82fc JJ |
66 | } |
67 | ||
68 | let expr_exit = self.opt_expr(&blk.expr, stmts_exit); | |
69 | ||
c34b1796 | 70 | self.add_ast_node(blk.id, &[expr_exit]) |
1a4d82fc JJ |
71 | } |
72 | ||
e9174d1e | 73 | fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex { |
1a4d82fc | 74 | match stmt.node { |
e9174d1e | 75 | hir::StmtDecl(ref decl, id) => { |
7453a54e | 76 | let exit = self.decl(&decl, pred); |
c34b1796 | 77 | self.add_ast_node(id, &[exit]) |
1a4d82fc JJ |
78 | } |
79 | ||
e9174d1e | 80 | hir::StmtExpr(ref expr, id) | hir::StmtSemi(ref expr, id) => { |
7453a54e | 81 | let exit = self.expr(&expr, pred); |
c34b1796 | 82 | self.add_ast_node(id, &[exit]) |
1a4d82fc | 83 | } |
1a4d82fc JJ |
84 | } |
85 | } | |
86 | ||
e9174d1e | 87 | fn decl(&mut self, decl: &hir::Decl, pred: CFGIndex) -> CFGIndex { |
1a4d82fc | 88 | match decl.node { |
e9174d1e | 89 | hir::DeclLocal(ref local) => { |
1a4d82fc | 90 | let init_exit = self.opt_expr(&local.init, pred); |
7453a54e | 91 | self.pat(&local.pat, init_exit) |
1a4d82fc JJ |
92 | } |
93 | ||
e9174d1e | 94 | hir::DeclItem(_) => { |
1a4d82fc JJ |
95 | pred |
96 | } | |
97 | } | |
98 | } | |
99 | ||
e9174d1e | 100 | fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex { |
1a4d82fc | 101 | match pat.node { |
7453a54e SL |
102 | PatKind::Ident(_, _, None) | |
103 | PatKind::TupleStruct(_, None) | | |
104 | PatKind::Path(..) | | |
105 | PatKind::QPath(..) | | |
106 | PatKind::Lit(..) | | |
107 | PatKind::Range(..) | | |
108 | PatKind::Wild => { | |
c34b1796 | 109 | self.add_ast_node(pat.id, &[pred]) |
1a4d82fc JJ |
110 | } |
111 | ||
7453a54e SL |
112 | PatKind::Box(ref subpat) | |
113 | PatKind::Ref(ref subpat, _) | | |
114 | PatKind::Ident(_, _, Some(ref subpat)) => { | |
115 | let subpat_exit = self.pat(&subpat, pred); | |
c34b1796 | 116 | self.add_ast_node(pat.id, &[subpat_exit]) |
1a4d82fc JJ |
117 | } |
118 | ||
7453a54e SL |
119 | PatKind::TupleStruct(_, Some(ref subpats)) | |
120 | PatKind::Tup(ref subpats) => { | |
1a4d82fc | 121 | let pats_exit = self.pats_all(subpats.iter(), pred); |
c34b1796 | 122 | self.add_ast_node(pat.id, &[pats_exit]) |
1a4d82fc JJ |
123 | } |
124 | ||
7453a54e | 125 | PatKind::Struct(_, ref subpats, _) => { |
1a4d82fc JJ |
126 | let pats_exit = |
127 | self.pats_all(subpats.iter().map(|f| &f.node.pat), pred); | |
c34b1796 | 128 | self.add_ast_node(pat.id, &[pats_exit]) |
1a4d82fc JJ |
129 | } |
130 | ||
7453a54e | 131 | PatKind::Vec(ref pre, ref vec, ref post) => { |
1a4d82fc JJ |
132 | let pre_exit = self.pats_all(pre.iter(), pred); |
133 | let vec_exit = self.pats_all(vec.iter(), pre_exit); | |
134 | let post_exit = self.pats_all(post.iter(), vec_exit); | |
c34b1796 | 135 | self.add_ast_node(pat.id, &[post_exit]) |
1a4d82fc | 136 | } |
1a4d82fc JJ |
137 | } |
138 | } | |
139 | ||
e9174d1e | 140 | fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>(&mut self, |
1a4d82fc JJ |
141 | pats: I, |
142 | pred: CFGIndex) -> CFGIndex { | |
143 | //! Handles case where all of the patterns must match. | |
7453a54e | 144 | pats.fold(pred, |pred, pat| self.pat(&pat, pred)) |
1a4d82fc JJ |
145 | } |
146 | ||
e9174d1e | 147 | fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex { |
1a4d82fc | 148 | match expr.node { |
e9174d1e | 149 | hir::ExprBlock(ref blk) => { |
7453a54e | 150 | let blk_exit = self.block(&blk, pred); |
c34b1796 | 151 | self.add_ast_node(expr.id, &[blk_exit]) |
1a4d82fc JJ |
152 | } |
153 | ||
e9174d1e | 154 | hir::ExprIf(ref cond, ref then, None) => { |
1a4d82fc JJ |
155 | // |
156 | // [pred] | |
157 | // | | |
158 | // v 1 | |
159 | // [cond] | |
160 | // | | |
161 | // / \ | |
162 | // / \ | |
163 | // v 2 * | |
164 | // [then] | | |
165 | // | | | |
166 | // v 3 v 4 | |
167 | // [..expr..] | |
168 | // | |
7453a54e SL |
169 | let cond_exit = self.expr(&cond, pred); // 1 |
170 | let then_exit = self.block(&then, cond_exit); // 2 | |
c34b1796 | 171 | self.add_ast_node(expr.id, &[cond_exit, then_exit]) // 3,4 |
1a4d82fc JJ |
172 | } |
173 | ||
e9174d1e | 174 | hir::ExprIf(ref cond, ref then, Some(ref otherwise)) => { |
1a4d82fc JJ |
175 | // |
176 | // [pred] | |
177 | // | | |
178 | // v 1 | |
179 | // [cond] | |
180 | // | | |
181 | // / \ | |
182 | // / \ | |
183 | // v 2 v 3 | |
184 | // [then][otherwise] | |
185 | // | | | |
186 | // v 4 v 5 | |
187 | // [..expr..] | |
188 | // | |
7453a54e SL |
189 | let cond_exit = self.expr(&cond, pred); // 1 |
190 | let then_exit = self.block(&then, cond_exit); // 2 | |
191 | let else_exit = self.expr(&otherwise, cond_exit); // 3 | |
c34b1796 | 192 | self.add_ast_node(expr.id, &[then_exit, else_exit]) // 4, 5 |
1a4d82fc JJ |
193 | } |
194 | ||
e9174d1e | 195 | hir::ExprWhile(ref cond, ref body, _) => { |
1a4d82fc JJ |
196 | // |
197 | // [pred] | |
198 | // | | |
199 | // v 1 | |
200 | // [loopback] <--+ 5 | |
201 | // | | | |
202 | // v 2 | | |
203 | // +-----[cond] | | |
204 | // | | | | |
205 | // | v 4 | | |
206 | // | [body] -----+ | |
207 | // v 3 | |
208 | // [expr] | |
209 | // | |
210 | // Note that `break` and `continue` statements | |
211 | // may cause additional edges. | |
212 | ||
213 | // Is the condition considered part of the loop? | |
214 | let loopback = self.add_dummy_node(&[pred]); // 1 | |
7453a54e | 215 | let cond_exit = self.expr(&cond, loopback); // 2 |
c34b1796 | 216 | let expr_exit = self.add_ast_node(expr.id, &[cond_exit]); // 3 |
1a4d82fc JJ |
217 | self.loop_scopes.push(LoopScope { |
218 | loop_id: expr.id, | |
219 | continue_index: loopback, | |
220 | break_index: expr_exit | |
221 | }); | |
7453a54e | 222 | let body_exit = self.block(&body, cond_exit); // 4 |
1a4d82fc JJ |
223 | self.add_contained_edge(body_exit, loopback); // 5 |
224 | self.loop_scopes.pop(); | |
225 | expr_exit | |
226 | } | |
227 | ||
e9174d1e | 228 | hir::ExprLoop(ref body, _) => { |
1a4d82fc JJ |
229 | // |
230 | // [pred] | |
231 | // | | |
232 | // v 1 | |
233 | // [loopback] <---+ | |
234 | // | 4 | | |
235 | // v 3 | | |
236 | // [body] ------+ | |
237 | // | |
238 | // [expr] 2 | |
239 | // | |
240 | // Note that `break` and `loop` statements | |
241 | // may cause additional edges. | |
242 | ||
243 | let loopback = self.add_dummy_node(&[pred]); // 1 | |
c34b1796 | 244 | let expr_exit = self.add_ast_node(expr.id, &[]); // 2 |
1a4d82fc JJ |
245 | self.loop_scopes.push(LoopScope { |
246 | loop_id: expr.id, | |
247 | continue_index: loopback, | |
248 | break_index: expr_exit, | |
249 | }); | |
7453a54e | 250 | let body_exit = self.block(&body, loopback); // 3 |
1a4d82fc JJ |
251 | self.add_contained_edge(body_exit, loopback); // 4 |
252 | self.loop_scopes.pop(); | |
253 | expr_exit | |
254 | } | |
255 | ||
e9174d1e | 256 | hir::ExprMatch(ref discr, ref arms, _) => { |
c34b1796 | 257 | self.match_(expr.id, &discr, &arms, pred) |
1a4d82fc JJ |
258 | } |
259 | ||
e9174d1e | 260 | hir::ExprBinary(op, ref l, ref r) if ::rustc_front::util::lazy_binop(op.node) => { |
1a4d82fc JJ |
261 | // |
262 | // [pred] | |
263 | // | | |
264 | // v 1 | |
265 | // [l] | |
266 | // | | |
267 | // / \ | |
268 | // / \ | |
269 | // v 2 * | |
270 | // [r] | | |
271 | // | | | |
272 | // v 3 v 4 | |
273 | // [..exit..] | |
274 | // | |
7453a54e SL |
275 | let l_exit = self.expr(&l, pred); // 1 |
276 | let r_exit = self.expr(&r, l_exit); // 2 | |
c34b1796 | 277 | self.add_ast_node(expr.id, &[l_exit, r_exit]) // 3,4 |
1a4d82fc JJ |
278 | } |
279 | ||
e9174d1e | 280 | hir::ExprRet(ref v) => { |
1a4d82fc | 281 | let v_exit = self.opt_expr(v, pred); |
c34b1796 | 282 | let b = self.add_ast_node(expr.id, &[v_exit]); |
1a4d82fc | 283 | self.add_returning_edge(expr, b); |
c34b1796 | 284 | self.add_unreachable_node() |
1a4d82fc JJ |
285 | } |
286 | ||
e9174d1e | 287 | hir::ExprBreak(label) => { |
b039eaaf | 288 | let loop_scope = self.find_scope(expr, label.map(|l| l.node.name)); |
c34b1796 | 289 | let b = self.add_ast_node(expr.id, &[pred]); |
1a4d82fc JJ |
290 | self.add_exiting_edge(expr, b, |
291 | loop_scope, loop_scope.break_index); | |
c34b1796 | 292 | self.add_unreachable_node() |
1a4d82fc JJ |
293 | } |
294 | ||
e9174d1e | 295 | hir::ExprAgain(label) => { |
b039eaaf | 296 | let loop_scope = self.find_scope(expr, label.map(|l| l.node.name)); |
c34b1796 | 297 | let a = self.add_ast_node(expr.id, &[pred]); |
1a4d82fc JJ |
298 | self.add_exiting_edge(expr, a, |
299 | loop_scope, loop_scope.continue_index); | |
c34b1796 | 300 | self.add_unreachable_node() |
1a4d82fc JJ |
301 | } |
302 | ||
e9174d1e | 303 | hir::ExprVec(ref elems) => { |
1a4d82fc JJ |
304 | self.straightline(expr, pred, elems.iter().map(|e| &**e)) |
305 | } | |
306 | ||
e9174d1e | 307 | hir::ExprCall(ref func, ref args) => { |
7453a54e | 308 | self.call(expr, pred, &func, args.iter().map(|e| &**e)) |
1a4d82fc JJ |
309 | } |
310 | ||
e9174d1e | 311 | hir::ExprMethodCall(_, _, ref args) => { |
7453a54e | 312 | self.call(expr, pred, &args[0], args[1..].iter().map(|e| &**e)) |
1a4d82fc JJ |
313 | } |
314 | ||
e9174d1e SL |
315 | hir::ExprIndex(ref l, ref r) | |
316 | hir::ExprBinary(_, ref l, ref r) if self.tcx.is_method_call(expr.id) => { | |
7453a54e | 317 | self.call(expr, pred, &l, Some(&**r).into_iter()) |
1a4d82fc JJ |
318 | } |
319 | ||
e9174d1e | 320 | hir::ExprRange(ref start, ref end) => { |
1a4d82fc | 321 | let fields = start.as_ref().map(|e| &**e).into_iter() |
62682a34 | 322 | .chain(end.as_ref().map(|e| &**e)); |
1a4d82fc JJ |
323 | self.straightline(expr, pred, fields) |
324 | } | |
325 | ||
e9174d1e | 326 | hir::ExprUnary(_, ref e) if self.tcx.is_method_call(expr.id) => { |
7453a54e | 327 | self.call(expr, pred, &e, None::<hir::Expr>.iter()) |
1a4d82fc JJ |
328 | } |
329 | ||
e9174d1e | 330 | hir::ExprTup(ref exprs) => { |
1a4d82fc JJ |
331 | self.straightline(expr, pred, exprs.iter().map(|e| &**e)) |
332 | } | |
333 | ||
e9174d1e | 334 | hir::ExprStruct(_, ref fields, ref base) => { |
1a4d82fc JJ |
335 | let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr)); |
336 | self.opt_expr(base, field_cfg) | |
337 | } | |
338 | ||
e9174d1e | 339 | hir::ExprRepeat(ref elem, ref count) => { |
1a4d82fc JJ |
340 | self.straightline(expr, pred, [elem, count].iter().map(|&e| &**e)) |
341 | } | |
342 | ||
e9174d1e SL |
343 | hir::ExprAssign(ref l, ref r) | |
344 | hir::ExprAssignOp(_, ref l, ref r) => { | |
1a4d82fc JJ |
345 | self.straightline(expr, pred, [r, l].iter().map(|&e| &**e)) |
346 | } | |
347 | ||
e9174d1e SL |
348 | hir::ExprIndex(ref l, ref r) | |
349 | hir::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier | |
1a4d82fc JJ |
350 | self.straightline(expr, pred, [l, r].iter().map(|&e| &**e)) |
351 | } | |
352 | ||
b039eaaf | 353 | hir::ExprBox(ref e) | |
e9174d1e SL |
354 | hir::ExprAddrOf(_, ref e) | |
355 | hir::ExprCast(ref e, _) | | |
9cc50fc6 | 356 | hir::ExprType(ref e, _) | |
e9174d1e | 357 | hir::ExprUnary(_, ref e) | |
e9174d1e SL |
358 | hir::ExprField(ref e, _) | |
359 | hir::ExprTupField(ref e, _) => { | |
1a4d82fc JJ |
360 | self.straightline(expr, pred, Some(&**e).into_iter()) |
361 | } | |
362 | ||
e9174d1e | 363 | hir::ExprInlineAsm(ref inline_asm) => { |
1a4d82fc JJ |
364 | let inputs = inline_asm.inputs.iter(); |
365 | let outputs = inline_asm.outputs.iter(); | |
366 | let post_inputs = self.exprs(inputs.map(|a| { | |
367 | debug!("cfg::construct InlineAsm id:{} input:{:?}", expr.id, a); | |
368 | let &(_, ref expr) = a; | |
369 | &**expr | |
370 | }), pred); | |
371 | let post_outputs = self.exprs(outputs.map(|a| { | |
372 | debug!("cfg::construct InlineAsm id:{} output:{:?}", expr.id, a); | |
9cc50fc6 | 373 | &*a.expr |
1a4d82fc | 374 | }), post_inputs); |
c34b1796 | 375 | self.add_ast_node(expr.id, &[post_outputs]) |
1a4d82fc JJ |
376 | } |
377 | ||
e9174d1e SL |
378 | hir::ExprClosure(..) | |
379 | hir::ExprLit(..) | | |
380 | hir::ExprPath(..) => { | |
381 | self.straightline(expr, pred, None::<hir::Expr>.iter()) | |
1a4d82fc JJ |
382 | } |
383 | } | |
384 | } | |
385 | ||
e9174d1e SL |
386 | fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self, |
387 | call_expr: &hir::Expr, | |
1a4d82fc | 388 | pred: CFGIndex, |
e9174d1e | 389 | func_or_rcvr: &hir::Expr, |
1a4d82fc JJ |
390 | args: I) -> CFGIndex { |
391 | let method_call = ty::MethodCall::expr(call_expr.id); | |
c1a9b12d | 392 | let fn_ty = match self.tcx.tables.borrow().method_map.get(&method_call) { |
1a4d82fc | 393 | Some(method) => method.ty, |
c1a9b12d SL |
394 | None => self.tcx.expr_ty_adjusted(func_or_rcvr) |
395 | }; | |
1a4d82fc JJ |
396 | |
397 | let func_or_rcvr_exit = self.expr(func_or_rcvr, pred); | |
398 | let ret = self.straightline(call_expr, func_or_rcvr_exit, args); | |
c1a9b12d | 399 | if fn_ty.fn_ret().diverges() { |
c34b1796 | 400 | self.add_unreachable_node() |
1a4d82fc JJ |
401 | } else { |
402 | ret | |
403 | } | |
404 | } | |
405 | ||
e9174d1e | 406 | fn exprs<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self, |
1a4d82fc JJ |
407 | exprs: I, |
408 | pred: CFGIndex) -> CFGIndex { | |
409 | //! Constructs graph for `exprs` evaluated in order | |
410 | exprs.fold(pred, |p, e| self.expr(e, p)) | |
411 | } | |
412 | ||
413 | fn opt_expr(&mut self, | |
e9174d1e | 414 | opt_expr: &Option<P<hir::Expr>>, |
1a4d82fc JJ |
415 | pred: CFGIndex) -> CFGIndex { |
416 | //! Constructs graph for `opt_expr` evaluated, if Some | |
7453a54e | 417 | opt_expr.iter().fold(pred, |p, e| self.expr(&e, p)) |
1a4d82fc JJ |
418 | } |
419 | ||
e9174d1e SL |
420 | fn straightline<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self, |
421 | expr: &hir::Expr, | |
1a4d82fc JJ |
422 | pred: CFGIndex, |
423 | subexprs: I) -> CFGIndex { | |
424 | //! Handles case of an expression that evaluates `subexprs` in order | |
425 | ||
426 | let subexprs_exit = self.exprs(subexprs, pred); | |
c34b1796 AL |
427 | self.add_ast_node(expr.id, &[subexprs_exit]) |
428 | } | |
429 | ||
e9174d1e SL |
430 | fn match_(&mut self, id: ast::NodeId, discr: &hir::Expr, |
431 | arms: &[hir::Arm], pred: CFGIndex) -> CFGIndex { | |
c34b1796 AL |
432 | // The CFG for match expression is quite complex, so no ASCII |
433 | // art for it (yet). | |
434 | // | |
435 | // The CFG generated below matches roughly what trans puts | |
436 | // out. Each pattern and guard is visited in parallel, with | |
437 | // arms containing multiple patterns generating multiple nodes | |
438 | // for the same guard expression. The guard expressions chain | |
439 | // into each other from top to bottom, with a specific | |
440 | // exception to allow some additional valid programs | |
441 | // (explained below). Trans differs slightly in that the | |
442 | // pattern matching may continue after a guard but the visible | |
443 | // behaviour should be the same. | |
444 | // | |
445 | // What is going on is explained in further comments. | |
446 | ||
447 | // Visit the discriminant expression | |
448 | let discr_exit = self.expr(discr, pred); | |
449 | ||
450 | // Add a node for the exit of the match expression as a whole. | |
451 | let expr_exit = self.add_ast_node(id, &[]); | |
452 | ||
453 | // Keep track of the previous guard expressions | |
454 | let mut prev_guards = Vec::new(); | |
455 | // Track if the previous pattern contained bindings or wildcards | |
456 | let mut prev_has_bindings = false; | |
457 | ||
458 | for arm in arms { | |
459 | // Add an exit node for when we've visited all the | |
460 | // patterns and the guard (if there is one) in the arm. | |
461 | let arm_exit = self.add_dummy_node(&[]); | |
462 | ||
463 | for pat in &arm.pats { | |
464 | // Visit the pattern, coming from the discriminant exit | |
7453a54e | 465 | let mut pat_exit = self.pat(&pat, discr_exit); |
c34b1796 AL |
466 | |
467 | // If there is a guard expression, handle it here | |
468 | if let Some(ref guard) = arm.guard { | |
469 | // Add a dummy node for the previous guard | |
470 | // expression to target | |
471 | let guard_start = self.add_dummy_node(&[pat_exit]); | |
472 | // Visit the guard expression | |
7453a54e | 473 | let guard_exit = self.expr(&guard, guard_start); |
c34b1796 AL |
474 | |
475 | let this_has_bindings = pat_util::pat_contains_bindings_or_wild( | |
7453a54e | 476 | &self.tcx.def_map.borrow(), &pat); |
c34b1796 AL |
477 | |
478 | // If both this pattern and the previous pattern | |
479 | // were free of bindings, they must consist only | |
480 | // of "constant" patterns. Note we cannot match an | |
481 | // all-constant pattern, fail the guard, and then | |
482 | // match *another* all-constant pattern. This is | |
483 | // because if the previous pattern matches, then | |
484 | // we *cannot* match this one, unless all the | |
485 | // constants are the same (which is rejected by | |
486 | // `check_match`). | |
487 | // | |
488 | // We can use this to be smarter about the flow | |
489 | // along guards. If the previous pattern matched, | |
490 | // then we know we will not visit the guard in | |
491 | // this one (whether or not the guard succeeded), | |
492 | // if the previous pattern failed, then we know | |
493 | // the guard for that pattern will not have been | |
494 | // visited. Thus, it is not possible to visit both | |
495 | // the previous guard and the current one when | |
496 | // both patterns consist only of constant | |
497 | // sub-patterns. | |
498 | // | |
499 | // However, if the above does not hold, then all | |
500 | // previous guards need to be wired to visit the | |
501 | // current guard pattern. | |
502 | if prev_has_bindings || this_has_bindings { | |
503 | while let Some(prev) = prev_guards.pop() { | |
504 | self.add_contained_edge(prev, guard_start); | |
505 | } | |
506 | } | |
507 | ||
508 | prev_has_bindings = this_has_bindings; | |
509 | ||
510 | // Push the guard onto the list of previous guards | |
511 | prev_guards.push(guard_exit); | |
512 | ||
513 | // Update the exit node for the pattern | |
514 | pat_exit = guard_exit; | |
515 | } | |
516 | ||
517 | // Add an edge from the exit of this pattern to the | |
518 | // exit of the arm | |
519 | self.add_contained_edge(pat_exit, arm_exit); | |
520 | } | |
521 | ||
522 | // Visit the body of this arm | |
523 | let body_exit = self.expr(&arm.body, arm_exit); | |
524 | ||
525 | // Link the body to the exit of the expression | |
526 | self.add_contained_edge(body_exit, expr_exit); | |
527 | } | |
528 | ||
529 | expr_exit | |
1a4d82fc JJ |
530 | } |
531 | ||
532 | fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex { | |
c34b1796 | 533 | self.add_node(CFGNodeData::Dummy, preds) |
1a4d82fc JJ |
534 | } |
535 | ||
c34b1796 AL |
536 | fn add_ast_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex { |
537 | assert!(id != ast::DUMMY_NODE_ID); | |
538 | self.add_node(CFGNodeData::AST(id), preds) | |
539 | } | |
540 | ||
541 | fn add_unreachable_node(&mut self) -> CFGIndex { | |
542 | self.add_node(CFGNodeData::Unreachable, &[]) | |
543 | } | |
544 | ||
545 | fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex { | |
546 | let node = self.graph.add_node(data); | |
85aaf69f | 547 | for &pred in preds { |
1a4d82fc JJ |
548 | self.add_contained_edge(pred, node); |
549 | } | |
550 | node | |
551 | } | |
552 | ||
553 | fn add_contained_edge(&mut self, | |
554 | source: CFGIndex, | |
555 | target: CFGIndex) { | |
556 | let data = CFGEdgeData {exiting_scopes: vec!() }; | |
557 | self.graph.add_edge(source, target, data); | |
558 | } | |
559 | ||
560 | fn add_exiting_edge(&mut self, | |
e9174d1e | 561 | from_expr: &hir::Expr, |
1a4d82fc JJ |
562 | from_index: CFGIndex, |
563 | to_loop: LoopScope, | |
564 | to_index: CFGIndex) { | |
565 | let mut data = CFGEdgeData {exiting_scopes: vec!() }; | |
e9174d1e SL |
566 | let mut scope = self.tcx.region_maps.node_extent(from_expr.id); |
567 | let target_scope = self.tcx.region_maps.node_extent(to_loop.loop_id); | |
1a4d82fc | 568 | while scope != target_scope { |
e9174d1e | 569 | data.exiting_scopes.push(scope.node_id(&self.tcx.region_maps)); |
1a4d82fc JJ |
570 | scope = self.tcx.region_maps.encl_scope(scope); |
571 | } | |
572 | self.graph.add_edge(from_index, to_index, data); | |
573 | } | |
574 | ||
575 | fn add_returning_edge(&mut self, | |
e9174d1e | 576 | _from_expr: &hir::Expr, |
1a4d82fc JJ |
577 | from_index: CFGIndex) { |
578 | let mut data = CFGEdgeData { | |
579 | exiting_scopes: vec!(), | |
580 | }; | |
581 | for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() { | |
582 | data.exiting_scopes.push(id); | |
583 | } | |
584 | self.graph.add_edge(from_index, self.fn_exit, data); | |
585 | } | |
586 | ||
587 | fn find_scope(&self, | |
e9174d1e | 588 | expr: &hir::Expr, |
b039eaaf | 589 | label: Option<ast::Name>) -> LoopScope { |
c34b1796 AL |
590 | if label.is_none() { |
591 | return *self.loop_scopes.last().unwrap(); | |
592 | } | |
1a4d82fc | 593 | |
c34b1796 | 594 | match self.tcx.def_map.borrow().get(&expr.id).map(|d| d.full_def()) { |
7453a54e | 595 | Some(Def::Label(loop_id)) => { |
c34b1796 AL |
596 | for l in &self.loop_scopes { |
597 | if l.loop_id == loop_id { | |
598 | return *l; | |
1a4d82fc JJ |
599 | } |
600 | } | |
c34b1796 AL |
601 | self.tcx.sess.span_bug(expr.span, |
602 | &format!("no loop scope for id {}", loop_id)); | |
603 | } | |
604 | ||
605 | r => { | |
606 | self.tcx.sess.span_bug(expr.span, | |
607 | &format!("bad entry `{:?}` in def_map for label", r)); | |
1a4d82fc JJ |
608 | } |
609 | } | |
610 | } | |
1a4d82fc | 611 | } |