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.
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.
11 use rustc_data_structures::graph;
20 struct CFGBuilder<'a, 'tcx: 'a> {
21 tcx: &'a ty::ctxt<'tcx>,
24 loop_scopes: Vec<LoopScope>,
27 #[derive(Copy, Clone)]
29 loop_id: ast::NodeId, // id of loop/while node
30 continue_index: CFGIndex, // where to go on a `loop`
31 break_index: CFGIndex, // where to go on a `break
34 pub fn construct(tcx: &ty::ctxt,
35 blk: &ast::Block) -> CFG {
36 let mut graph = graph::Graph::new();
37 let entry = graph.add_node(CFGNodeData::Entry);
39 // `fn_exit` is target of return exprs, which lies somewhere
40 // outside input `blk`. (Distinguishing `fn_exit` and `block_exit`
41 // also resolves chicken-and-egg problem that arises if you try to
42 // have return exprs jump to `block_exit` during construction.)
43 let fn_exit = graph.add_node(CFGNodeData::Exit);
46 let mut cfg_builder = CFGBuilder {
50 loop_scopes: Vec::new()
52 block_exit = cfg_builder.block(blk, entry);
53 cfg_builder.add_contained_edge(block_exit, fn_exit);
54 let CFGBuilder {graph, ..} = cfg_builder;
60 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
61 fn block(&mut self, blk: &ast::Block, pred: CFGIndex) -> CFGIndex {
62 let mut stmts_exit = pred;
63 for stmt in &blk.stmts {
64 stmts_exit = self.stmt(&**stmt, stmts_exit);
67 let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
69 self.add_ast_node(blk.id, &[expr_exit])
72 fn stmt(&mut self, stmt: &ast::Stmt, pred: CFGIndex) -> CFGIndex {
74 ast::StmtDecl(ref decl, id) => {
75 let exit = self.decl(&**decl, pred);
76 self.add_ast_node(id, &[exit])
79 ast::StmtExpr(ref expr, id) | ast::StmtSemi(ref expr, id) => {
80 let exit = self.expr(&**expr, pred);
81 self.add_ast_node(id, &[exit])
85 self.tcx.sess.span_bug(stmt.span, "unexpanded macro");
90 fn decl(&mut self, decl: &ast::Decl, pred: CFGIndex) -> CFGIndex {
92 ast::DeclLocal(ref local) => {
93 let init_exit = self.opt_expr(&local.init, pred);
94 self.pat(&*local.pat, init_exit)
103 fn pat(&mut self, pat: &ast::Pat, pred: CFGIndex) -> CFGIndex {
105 ast::PatIdent(_, _, None) |
106 ast::PatEnum(_, None) |
111 self.add_ast_node(pat.id, &[pred])
114 ast::PatBox(ref subpat) |
115 ast::PatRegion(ref subpat, _) |
116 ast::PatIdent(_, _, Some(ref subpat)) => {
117 let subpat_exit = self.pat(&**subpat, pred);
118 self.add_ast_node(pat.id, &[subpat_exit])
121 ast::PatEnum(_, Some(ref subpats)) |
122 ast::PatTup(ref subpats) => {
123 let pats_exit = self.pats_all(subpats.iter(), pred);
124 self.add_ast_node(pat.id, &[pats_exit])
127 ast::PatStruct(_, ref subpats, _) => {
129 self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
130 self.add_ast_node(pat.id, &[pats_exit])
133 ast::PatVec(ref pre, ref vec, ref post) => {
134 let pre_exit = self.pats_all(pre.iter(), pred);
135 let vec_exit = self.pats_all(vec.iter(), pre_exit);
136 let post_exit = self.pats_all(post.iter(), vec_exit);
137 self.add_ast_node(pat.id, &[post_exit])
141 self.tcx.sess.span_bug(pat.span, "unexpanded macro");
146 fn pats_all<'b, I: Iterator<Item=&'b P<ast::Pat>>>(&mut self,
148 pred: CFGIndex) -> CFGIndex {
149 //! Handles case where all of the patterns must match.
150 pats.fold(pred, |pred, pat| self.pat(&**pat, pred))
153 fn expr(&mut self, expr: &ast::Expr, pred: CFGIndex) -> CFGIndex {
155 ast::ExprBlock(ref blk) => {
156 let blk_exit = self.block(&**blk, pred);
157 self.add_ast_node(expr.id, &[blk_exit])
160 ast::ExprIf(ref cond, ref then, None) => {
175 let cond_exit = self.expr(&**cond, pred); // 1
176 let then_exit = self.block(&**then, cond_exit); // 2
177 self.add_ast_node(expr.id, &[cond_exit, then_exit]) // 3,4
180 ast::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
195 let cond_exit = self.expr(&**cond, pred); // 1
196 let then_exit = self.block(&**then, cond_exit); // 2
197 let else_exit = self.expr(&**otherwise, cond_exit); // 3
198 self.add_ast_node(expr.id, &[then_exit, else_exit]) // 4, 5
201 ast::ExprIfLet(..) => {
202 self.tcx.sess.span_bug(expr.span, "non-desugared ExprIfLet");
205 ast::ExprWhile(ref cond, ref body, _) => {
220 // Note that `break` and `continue` statements
221 // may cause additional edges.
223 // Is the condition considered part of the loop?
224 let loopback = self.add_dummy_node(&[pred]); // 1
225 let cond_exit = self.expr(&**cond, loopback); // 2
226 let expr_exit = self.add_ast_node(expr.id, &[cond_exit]); // 3
227 self.loop_scopes.push(LoopScope {
229 continue_index: loopback,
230 break_index: expr_exit
232 let body_exit = self.block(&**body, cond_exit); // 4
233 self.add_contained_edge(body_exit, loopback); // 5
234 self.loop_scopes.pop();
238 ast::ExprWhileLet(..) => {
239 self.tcx.sess.span_bug(expr.span, "non-desugared ExprWhileLet");
242 ast::ExprForLoop(..) => {
243 self.tcx.sess.span_bug(expr.span, "non-desugared ExprForLoop");
246 ast::ExprLoop(ref body, _) => {
258 // Note that `break` and `loop` statements
259 // may cause additional edges.
261 let loopback = self.add_dummy_node(&[pred]); // 1
262 let expr_exit = self.add_ast_node(expr.id, &[]); // 2
263 self.loop_scopes.push(LoopScope {
265 continue_index: loopback,
266 break_index: expr_exit,
268 let body_exit = self.block(&**body, loopback); // 3
269 self.add_contained_edge(body_exit, loopback); // 4
270 self.loop_scopes.pop();
274 ast::ExprMatch(ref discr, ref arms, _) => {
275 self.match_(expr.id, &discr, &arms, pred)
278 ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op.node) => {
293 let l_exit = self.expr(&**l, pred); // 1
294 let r_exit = self.expr(&**r, l_exit); // 2
295 self.add_ast_node(expr.id, &[l_exit, r_exit]) // 3,4
298 ast::ExprRet(ref v) => {
299 let v_exit = self.opt_expr(v, pred);
300 let b = self.add_ast_node(expr.id, &[v_exit]);
301 self.add_returning_edge(expr, b);
302 self.add_unreachable_node()
305 ast::ExprBreak(label) => {
306 let loop_scope = self.find_scope(expr, label);
307 let b = self.add_ast_node(expr.id, &[pred]);
308 self.add_exiting_edge(expr, b,
309 loop_scope, loop_scope.break_index);
310 self.add_unreachable_node()
313 ast::ExprAgain(label) => {
314 let loop_scope = self.find_scope(expr, label);
315 let a = self.add_ast_node(expr.id, &[pred]);
316 self.add_exiting_edge(expr, a,
317 loop_scope, loop_scope.continue_index);
318 self.add_unreachable_node()
321 ast::ExprVec(ref elems) => {
322 self.straightline(expr, pred, elems.iter().map(|e| &**e))
325 ast::ExprCall(ref func, ref args) => {
326 self.call(expr, pred, &**func, args.iter().map(|e| &**e))
329 ast::ExprMethodCall(_, _, ref args) => {
330 self.call(expr, pred, &*args[0], args[1..].iter().map(|e| &**e))
333 ast::ExprIndex(ref l, ref r) |
334 ast::ExprBinary(_, ref l, ref r) if self.tcx.is_method_call(expr.id) => {
335 self.call(expr, pred, &**l, Some(&**r).into_iter())
338 ast::ExprRange(ref start, ref end) => {
339 let fields = start.as_ref().map(|e| &**e).into_iter()
340 .chain(end.as_ref().map(|e| &**e));
341 self.straightline(expr, pred, fields)
344 ast::ExprUnary(_, ref e) if self.tcx.is_method_call(expr.id) => {
345 self.call(expr, pred, &**e, None::<ast::Expr>.iter())
348 ast::ExprTup(ref exprs) => {
349 self.straightline(expr, pred, exprs.iter().map(|e| &**e))
352 ast::ExprStruct(_, ref fields, ref base) => {
353 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
354 self.opt_expr(base, field_cfg)
357 ast::ExprRepeat(ref elem, ref count) => {
358 self.straightline(expr, pred, [elem, count].iter().map(|&e| &**e))
361 ast::ExprAssign(ref l, ref r) |
362 ast::ExprAssignOp(_, ref l, ref r) => {
363 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
366 ast::ExprBox(Some(ref l), ref r) |
367 ast::ExprIndex(ref l, ref r) |
368 ast::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier
369 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
372 ast::ExprBox(None, ref e) |
373 ast::ExprAddrOf(_, ref e) |
374 ast::ExprCast(ref e, _) |
375 ast::ExprUnary(_, ref e) |
376 ast::ExprParen(ref e) |
377 ast::ExprField(ref e, _) |
378 ast::ExprTupField(ref e, _) => {
379 self.straightline(expr, pred, Some(&**e).into_iter())
382 ast::ExprInlineAsm(ref inline_asm) => {
383 let inputs = inline_asm.inputs.iter();
384 let outputs = inline_asm.outputs.iter();
385 let post_inputs = self.exprs(inputs.map(|a| {
386 debug!("cfg::construct InlineAsm id:{} input:{:?}", expr.id, a);
387 let &(_, ref expr) = a;
390 let post_outputs = self.exprs(outputs.map(|a| {
391 debug!("cfg::construct InlineAsm id:{} output:{:?}", expr.id, a);
392 let &(_, ref expr, _) = a;
395 self.add_ast_node(expr.id, &[post_outputs])
399 ast::ExprClosure(..) |
401 ast::ExprPath(..) => {
402 self.straightline(expr, pred, None::<ast::Expr>.iter())
407 fn call<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
408 call_expr: &ast::Expr,
410 func_or_rcvr: &ast::Expr,
411 args: I) -> CFGIndex {
412 let method_call = ty::MethodCall::expr(call_expr.id);
413 let fn_ty = match self.tcx.tables.borrow().method_map.get(&method_call) {
414 Some(method) => method.ty,
415 None => self.tcx.expr_ty_adjusted(func_or_rcvr)
418 let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
419 let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
420 if fn_ty.fn_ret().diverges() {
421 self.add_unreachable_node()
427 fn exprs<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
429 pred: CFGIndex) -> CFGIndex {
430 //! Constructs graph for `exprs` evaluated in order
431 exprs.fold(pred, |p, e| self.expr(e, p))
434 fn opt_expr(&mut self,
435 opt_expr: &Option<P<ast::Expr>>,
436 pred: CFGIndex) -> CFGIndex {
437 //! Constructs graph for `opt_expr` evaluated, if Some
438 opt_expr.iter().fold(pred, |p, e| self.expr(&**e, p))
441 fn straightline<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
444 subexprs: I) -> CFGIndex {
445 //! Handles case of an expression that evaluates `subexprs` in order
447 let subexprs_exit = self.exprs(subexprs, pred);
448 self.add_ast_node(expr.id, &[subexprs_exit])
451 fn match_(&mut self, id: ast::NodeId, discr: &ast::Expr,
452 arms: &[ast::Arm], pred: CFGIndex) -> CFGIndex {
453 // The CFG for match expression is quite complex, so no ASCII
456 // The CFG generated below matches roughly what trans puts
457 // out. Each pattern and guard is visited in parallel, with
458 // arms containing multiple patterns generating multiple nodes
459 // for the same guard expression. The guard expressions chain
460 // into each other from top to bottom, with a specific
461 // exception to allow some additional valid programs
462 // (explained below). Trans differs slightly in that the
463 // pattern matching may continue after a guard but the visible
464 // behaviour should be the same.
466 // What is going on is explained in further comments.
468 // Visit the discriminant expression
469 let discr_exit = self.expr(discr, pred);
471 // Add a node for the exit of the match expression as a whole.
472 let expr_exit = self.add_ast_node(id, &[]);
474 // Keep track of the previous guard expressions
475 let mut prev_guards = Vec::new();
476 // Track if the previous pattern contained bindings or wildcards
477 let mut prev_has_bindings = false;
480 // Add an exit node for when we've visited all the
481 // patterns and the guard (if there is one) in the arm.
482 let arm_exit = self.add_dummy_node(&[]);
484 for pat in &arm.pats {
485 // Visit the pattern, coming from the discriminant exit
486 let mut pat_exit = self.pat(&**pat, discr_exit);
488 // If there is a guard expression, handle it here
489 if let Some(ref guard) = arm.guard {
490 // Add a dummy node for the previous guard
491 // expression to target
492 let guard_start = self.add_dummy_node(&[pat_exit]);
493 // Visit the guard expression
494 let guard_exit = self.expr(&**guard, guard_start);
496 let this_has_bindings = pat_util::pat_contains_bindings_or_wild(
497 &self.tcx.def_map, &**pat);
499 // If both this pattern and the previous pattern
500 // were free of bindings, they must consist only
501 // of "constant" patterns. Note we cannot match an
502 // all-constant pattern, fail the guard, and then
503 // match *another* all-constant pattern. This is
504 // because if the previous pattern matches, then
505 // we *cannot* match this one, unless all the
506 // constants are the same (which is rejected by
509 // We can use this to be smarter about the flow
510 // along guards. If the previous pattern matched,
511 // then we know we will not visit the guard in
512 // this one (whether or not the guard succeeded),
513 // if the previous pattern failed, then we know
514 // the guard for that pattern will not have been
515 // visited. Thus, it is not possible to visit both
516 // the previous guard and the current one when
517 // both patterns consist only of constant
520 // However, if the above does not hold, then all
521 // previous guards need to be wired to visit the
522 // current guard pattern.
523 if prev_has_bindings || this_has_bindings {
524 while let Some(prev) = prev_guards.pop() {
525 self.add_contained_edge(prev, guard_start);
529 prev_has_bindings = this_has_bindings;
531 // Push the guard onto the list of previous guards
532 prev_guards.push(guard_exit);
534 // Update the exit node for the pattern
535 pat_exit = guard_exit;
538 // Add an edge from the exit of this pattern to the
540 self.add_contained_edge(pat_exit, arm_exit);
543 // Visit the body of this arm
544 let body_exit = self.expr(&arm.body, arm_exit);
546 // Link the body to the exit of the expression
547 self.add_contained_edge(body_exit, expr_exit);
553 fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
554 self.add_node(CFGNodeData::Dummy, preds)
557 fn add_ast_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
558 assert!(id != ast::DUMMY_NODE_ID);
559 self.add_node(CFGNodeData::AST(id), preds)
562 fn add_unreachable_node(&mut self) -> CFGIndex {
563 self.add_node(CFGNodeData::Unreachable, &[])
566 fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
567 let node = self.graph.add_node(data);
569 self.add_contained_edge(pred, node);
574 fn add_contained_edge(&mut self,
577 let data = CFGEdgeData {exiting_scopes: vec!() };
578 self.graph.add_edge(source, target, data);
581 fn add_exiting_edge(&mut self,
582 from_expr: &ast::Expr,
583 from_index: CFGIndex,
585 to_index: CFGIndex) {
586 let mut data = CFGEdgeData {exiting_scopes: vec!() };
587 let mut scope = self.tcx.region_maps.node_extent(from_expr.id);
588 let target_scope = self.tcx.region_maps.node_extent(to_loop.loop_id);
589 while scope != target_scope {
590 data.exiting_scopes.push(scope.node_id(&self.tcx.region_maps));
591 scope = self.tcx.region_maps.encl_scope(scope);
593 self.graph.add_edge(from_index, to_index, data);
596 fn add_returning_edge(&mut self,
597 _from_expr: &ast::Expr,
598 from_index: CFGIndex) {
599 let mut data = CFGEdgeData {
600 exiting_scopes: vec!(),
602 for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
603 data.exiting_scopes.push(id);
605 self.graph.add_edge(from_index, self.fn_exit, data);
610 label: Option<ast::Ident>) -> LoopScope {
612 return *self.loop_scopes.last().unwrap();
615 match self.tcx.def_map.borrow().get(&expr.id).map(|d| d.full_def()) {
616 Some(def::DefLabel(loop_id)) => {
617 for l in &self.loop_scopes {
618 if l.loop_id == loop_id {
622 self.tcx.sess.span_bug(expr.span,
623 &format!("no loop scope for id {}", loop_id));
627 self.tcx.sess.span_bug(expr.span,
628 &format!("bad entry `{:?}` in def_map for label", r));