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.
14 use middle::region::CodeExtent;
19 use util::nodemap::NodeMap;
21 struct CFGBuilder<'a, 'tcx: 'a> {
22 tcx: &'a ty::ctxt<'tcx>,
23 exit_map: NodeMap<CFGIndex>,
26 loop_scopes: Vec<LoopScope>,
31 loop_id: ast::NodeId, // id of loop/while node
32 continue_index: CFGIndex, // where to go on a `loop`
33 break_index: CFGIndex, // where to go on a `break
36 pub fn construct(tcx: &ty::ctxt,
37 blk: &ast::Block) -> CFG {
38 let mut graph = graph::Graph::new();
39 let entry = add_initial_dummy_node(&mut graph);
41 // `fn_exit` is target of return exprs, which lies somewhere
42 // outside input `blk`. (Distinguishing `fn_exit` and `block_exit`
43 // also resolves chicken-and-egg problem that arises if you try to
44 // have return exprs jump to `block_exit` during construction.)
45 let fn_exit = add_initial_dummy_node(&mut graph);
48 let mut cfg_builder = CFGBuilder {
49 exit_map: NodeMap::new(),
53 loop_scopes: Vec::new()
55 block_exit = cfg_builder.block(blk, entry);
56 cfg_builder.add_contained_edge(block_exit, fn_exit);
57 let CFGBuilder {exit_map, graph, ..} = cfg_builder;
58 CFG {exit_map: exit_map,
64 fn add_initial_dummy_node(g: &mut CFGGraph) -> CFGIndex {
65 g.add_node(CFGNodeData { id: ast::DUMMY_NODE_ID })
68 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
69 fn block(&mut self, blk: &ast::Block, pred: CFGIndex) -> CFGIndex {
70 let mut stmts_exit = pred;
71 for stmt in blk.stmts.iter() {
72 stmts_exit = self.stmt(&**stmt, stmts_exit);
75 let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
77 self.add_node(blk.id, &[expr_exit])
80 fn stmt(&mut self, stmt: &ast::Stmt, pred: CFGIndex) -> CFGIndex {
82 ast::StmtDecl(ref decl, id) => {
83 let exit = self.decl(&**decl, pred);
84 self.add_node(id, &[exit])
87 ast::StmtExpr(ref expr, id) | ast::StmtSemi(ref expr, id) => {
88 let exit = self.expr(&**expr, pred);
89 self.add_node(id, &[exit])
93 self.tcx.sess.span_bug(stmt.span, "unexpanded macro");
98 fn decl(&mut self, decl: &ast::Decl, pred: CFGIndex) -> CFGIndex {
100 ast::DeclLocal(ref local) => {
101 let init_exit = self.opt_expr(&local.init, pred);
102 self.pat(&*local.pat, init_exit)
105 ast::DeclItem(_) => {
111 fn pat(&mut self, pat: &ast::Pat, pred: CFGIndex) -> CFGIndex {
113 ast::PatIdent(_, _, None) |
114 ast::PatEnum(_, None) |
118 self.add_node(pat.id, &[pred])
121 ast::PatBox(ref subpat) |
122 ast::PatRegion(ref subpat) |
123 ast::PatIdent(_, _, Some(ref subpat)) => {
124 let subpat_exit = self.pat(&**subpat, pred);
125 self.add_node(pat.id, &[subpat_exit])
128 ast::PatEnum(_, Some(ref subpats)) |
129 ast::PatTup(ref subpats) => {
130 let pats_exit = self.pats_all(subpats.iter(), pred);
131 self.add_node(pat.id, &[pats_exit])
134 ast::PatStruct(_, ref subpats, _) => {
136 self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
137 self.add_node(pat.id, &[pats_exit])
140 ast::PatVec(ref pre, ref vec, ref post) => {
141 let pre_exit = self.pats_all(pre.iter(), pred);
142 let vec_exit = self.pats_all(vec.iter(), pre_exit);
143 let post_exit = self.pats_all(post.iter(), vec_exit);
144 self.add_node(pat.id, &[post_exit])
148 self.tcx.sess.span_bug(pat.span, "unexpanded macro");
153 fn pats_all<'b, I: Iterator<Item=&'b P<ast::Pat>>>(&mut self,
155 pred: CFGIndex) -> CFGIndex {
156 //! Handles case where all of the patterns must match.
157 pats.fold(pred, |pred, pat| self.pat(&**pat, pred))
160 fn pats_any(&mut self,
161 pats: &[P<ast::Pat>],
162 pred: CFGIndex) -> CFGIndex {
163 //! Handles case where just one of the patterns must match.
166 self.pat(&*pats[0], pred)
168 let collect = self.add_dummy_node(&[]);
169 for pat in pats.iter() {
170 let pat_exit = self.pat(&**pat, pred);
171 self.add_contained_edge(pat_exit, collect);
177 fn expr(&mut self, expr: &ast::Expr, pred: CFGIndex) -> CFGIndex {
179 ast::ExprBlock(ref blk) => {
180 let blk_exit = self.block(&**blk, pred);
181 self.add_node(expr.id, &[blk_exit])
184 ast::ExprIf(ref cond, ref then, None) => {
199 let cond_exit = self.expr(&**cond, pred); // 1
200 let then_exit = self.block(&**then, cond_exit); // 2
201 self.add_node(expr.id, &[cond_exit, then_exit]) // 3,4
204 ast::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
219 let cond_exit = self.expr(&**cond, pred); // 1
220 let then_exit = self.block(&**then, cond_exit); // 2
221 let else_exit = self.expr(&**otherwise, cond_exit); // 3
222 self.add_node(expr.id, &[then_exit, else_exit]) // 4, 5
225 ast::ExprIfLet(..) => {
226 self.tcx.sess.span_bug(expr.span, "non-desugared ExprIfLet");
229 ast::ExprWhile(ref cond, ref body, _) => {
244 // Note that `break` and `continue` statements
245 // may cause additional edges.
247 // Is the condition considered part of the loop?
248 let loopback = self.add_dummy_node(&[pred]); // 1
249 let cond_exit = self.expr(&**cond, loopback); // 2
250 let expr_exit = self.add_node(expr.id, &[cond_exit]); // 3
251 self.loop_scopes.push(LoopScope {
253 continue_index: loopback,
254 break_index: expr_exit
256 let body_exit = self.block(&**body, cond_exit); // 4
257 self.add_contained_edge(body_exit, loopback); // 5
258 self.loop_scopes.pop();
262 ast::ExprWhileLet(..) => {
263 self.tcx.sess.span_bug(expr.span, "non-desugared ExprWhileLet");
266 ast::ExprForLoop(ref pat, ref head, ref body, _) => {
286 // Note that `break` and `continue` statements
287 // may cause additional edges.
289 let head = self.expr(&**head, pred); // 1
290 let loopback = self.add_dummy_node(&[head]); // 2
291 let cond = self.add_dummy_node(&[loopback]); // 3
292 let expr_exit = self.add_node(expr.id, &[cond]); // 4
293 self.loop_scopes.push(LoopScope {
295 continue_index: loopback,
296 break_index: expr_exit,
298 let pat = self.pat(&**pat, cond); // 5
299 let body = self.block(&**body, pat); // 6
300 self.add_contained_edge(body, loopback); // 7
301 self.loop_scopes.pop();
305 ast::ExprLoop(ref body, _) => {
317 // Note that `break` and `loop` statements
318 // may cause additional edges.
320 let loopback = self.add_dummy_node(&[pred]); // 1
321 let expr_exit = self.add_node(expr.id, &[]); // 2
322 self.loop_scopes.push(LoopScope {
324 continue_index: loopback,
325 break_index: expr_exit,
327 let body_exit = self.block(&**body, loopback); // 3
328 self.add_contained_edge(body_exit, loopback); // 4
329 self.loop_scopes.pop();
333 ast::ExprMatch(ref discr, ref arms, _) => {
359 let discr_exit = self.expr(&**discr, pred); // 1
361 let expr_exit = self.add_node(expr.id, &[]);
362 let mut cond_exit = discr_exit;
363 for arm in arms.iter() {
364 cond_exit = self.add_dummy_node(&[cond_exit]); // 2
365 let pats_exit = self.pats_any(arm.pats[],
367 let guard_exit = self.opt_expr(&arm.guard,
369 let body_exit = self.expr(&*arm.body, guard_exit); // 5
370 self.add_contained_edge(body_exit, expr_exit); // 6
375 ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op) => {
390 let l_exit = self.expr(&**l, pred); // 1
391 let r_exit = self.expr(&**r, l_exit); // 2
392 self.add_node(expr.id, &[l_exit, r_exit]) // 3,4
395 ast::ExprRet(ref v) => {
396 let v_exit = self.opt_expr(v, pred);
397 let b = self.add_node(expr.id, &[v_exit]);
398 self.add_returning_edge(expr, b);
399 self.add_node(ast::DUMMY_NODE_ID, &[])
402 ast::ExprBreak(label) => {
403 let loop_scope = self.find_scope(expr, label);
404 let b = self.add_node(expr.id, &[pred]);
405 self.add_exiting_edge(expr, b,
406 loop_scope, loop_scope.break_index);
407 self.add_node(ast::DUMMY_NODE_ID, &[])
410 ast::ExprAgain(label) => {
411 let loop_scope = self.find_scope(expr, label);
412 let a = self.add_node(expr.id, &[pred]);
413 self.add_exiting_edge(expr, a,
414 loop_scope, loop_scope.continue_index);
415 self.add_node(ast::DUMMY_NODE_ID, &[])
418 ast::ExprVec(ref elems) => {
419 self.straightline(expr, pred, elems.iter().map(|e| &**e))
422 ast::ExprCall(ref func, ref args) => {
423 self.call(expr, pred, &**func, args.iter().map(|e| &**e))
426 ast::ExprMethodCall(_, _, ref args) => {
427 self.call(expr, pred, &*args[0], args.slice_from(1).iter().map(|e| &**e))
430 ast::ExprIndex(ref l, ref r) |
431 ast::ExprBinary(_, ref l, ref r) if self.is_method_call(expr) => {
432 self.call(expr, pred, &**l, Some(&**r).into_iter())
435 ast::ExprRange(ref start, ref end) => {
436 let fields = start.as_ref().map(|e| &**e).into_iter()
437 .chain(end.as_ref().map(|e| &**e).into_iter());
438 self.straightline(expr, pred, fields)
441 ast::ExprUnary(_, ref e) if self.is_method_call(expr) => {
442 self.call(expr, pred, &**e, None::<ast::Expr>.iter())
445 ast::ExprTup(ref exprs) => {
446 self.straightline(expr, pred, exprs.iter().map(|e| &**e))
449 ast::ExprStruct(_, ref fields, ref base) => {
450 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
451 self.opt_expr(base, field_cfg)
454 ast::ExprRepeat(ref elem, ref count) => {
455 self.straightline(expr, pred, [elem, count].iter().map(|&e| &**e))
458 ast::ExprAssign(ref l, ref r) |
459 ast::ExprAssignOp(_, ref l, ref r) => {
460 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
463 ast::ExprBox(Some(ref l), ref r) |
464 ast::ExprIndex(ref l, ref r) |
465 ast::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier
466 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
469 ast::ExprBox(None, ref e) |
470 ast::ExprAddrOf(_, ref e) |
471 ast::ExprCast(ref e, _) |
472 ast::ExprUnary(_, ref e) |
473 ast::ExprParen(ref e) |
474 ast::ExprField(ref e, _) |
475 ast::ExprTupField(ref e, _) => {
476 self.straightline(expr, pred, Some(&**e).into_iter())
479 ast::ExprInlineAsm(ref inline_asm) => {
480 let inputs = inline_asm.inputs.iter();
481 let outputs = inline_asm.outputs.iter();
482 let post_inputs = self.exprs(inputs.map(|a| {
483 debug!("cfg::construct InlineAsm id:{} input:{}", expr.id, a);
484 let &(_, ref expr) = a;
487 let post_outputs = self.exprs(outputs.map(|a| {
488 debug!("cfg::construct InlineAsm id:{} output:{}", expr.id, a);
489 let &(_, ref expr, _) = a;
492 self.add_node(expr.id, &[post_outputs])
496 ast::ExprClosure(..) |
498 ast::ExprPath(..) => {
499 self.straightline(expr, pred, None::<ast::Expr>.iter())
504 fn call<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
505 call_expr: &ast::Expr,
507 func_or_rcvr: &ast::Expr,
508 args: I) -> CFGIndex {
509 let method_call = ty::MethodCall::expr(call_expr.id);
510 let return_ty = ty::ty_fn_ret(match self.tcx.method_map.borrow().get(&method_call) {
511 Some(method) => method.ty,
512 None => ty::expr_ty_adjusted(self.tcx, func_or_rcvr)
515 let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
516 let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
517 if return_ty == ty::FnDiverging {
518 self.add_node(ast::DUMMY_NODE_ID, &[])
524 fn exprs<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
526 pred: CFGIndex) -> CFGIndex {
527 //! Constructs graph for `exprs` evaluated in order
528 exprs.fold(pred, |p, e| self.expr(e, p))
531 fn opt_expr(&mut self,
532 opt_expr: &Option<P<ast::Expr>>,
533 pred: CFGIndex) -> CFGIndex {
534 //! Constructs graph for `opt_expr` evaluated, if Some
535 opt_expr.iter().fold(pred, |p, e| self.expr(&**e, p))
538 fn straightline<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
541 subexprs: I) -> CFGIndex {
542 //! Handles case of an expression that evaluates `subexprs` in order
544 let subexprs_exit = self.exprs(subexprs, pred);
545 self.add_node(expr.id, &[subexprs_exit])
548 fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
549 self.add_node(ast::DUMMY_NODE_ID, preds)
552 fn add_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
553 assert!(!self.exit_map.contains_key(&id));
554 let node = self.graph.add_node(CFGNodeData {id: id});
555 if id != ast::DUMMY_NODE_ID {
556 assert!(!self.exit_map.contains_key(&id));
557 self.exit_map.insert(id, node);
559 for &pred in preds.iter() {
560 self.add_contained_edge(pred, node);
565 fn add_contained_edge(&mut self,
568 let data = CFGEdgeData {exiting_scopes: vec!() };
569 self.graph.add_edge(source, target, data);
572 fn add_exiting_edge(&mut self,
573 from_expr: &ast::Expr,
574 from_index: CFGIndex,
576 to_index: CFGIndex) {
577 let mut data = CFGEdgeData {exiting_scopes: vec!() };
578 let mut scope = CodeExtent::from_node_id(from_expr.id);
579 let target_scope = CodeExtent::from_node_id(to_loop.loop_id);
580 while scope != target_scope {
582 data.exiting_scopes.push(scope.node_id());
583 scope = self.tcx.region_maps.encl_scope(scope);
585 self.graph.add_edge(from_index, to_index, data);
588 fn add_returning_edge(&mut self,
589 _from_expr: &ast::Expr,
590 from_index: CFGIndex) {
591 let mut data = CFGEdgeData {
592 exiting_scopes: vec!(),
594 for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
595 data.exiting_scopes.push(id);
597 self.graph.add_edge(from_index, self.fn_exit, data);
602 label: Option<ast::Ident>) -> LoopScope {
605 return *self.loop_scopes.last().unwrap();
609 match self.tcx.def_map.borrow().get(&expr.id) {
610 Some(&def::DefLabel(loop_id)) => {
611 for l in self.loop_scopes.iter() {
612 if l.loop_id == loop_id {
616 self.tcx.sess.span_bug(
618 format!("no loop scope for id {}",
623 self.tcx.sess.span_bug(
625 format!("bad entry `{}` in def_map for label",
633 fn is_method_call(&self, expr: &ast::Expr) -> bool {
634 let method_call = ty::MethodCall::expr(expr.id);
635 self.tcx.method_map.borrow().contains_key(&method_call)