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