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.
18 use util::nodemap::NodeMap;
22 struct CFGBuilder<'a, 'tcx: 'a> {
23 tcx: &'a ty::ctxt<'tcx>,
24 exit_map: NodeMap<CFGIndex>,
27 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.clone(), stmts_exit);
75 let expr_exit = self.opt_expr(blk.expr.clone(), stmts_exit);
77 self.add_node(blk.id, [expr_exit])
80 fn stmt(&mut self, stmt: Gc<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.clone(), 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.clone(), 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) => {
131 self.pats_all(subpats.iter().map(|p| p.clone()), pred);
132 self.add_node(pat.id, [pats_exit])
135 ast::PatStruct(_, ref subpats, _) => {
137 self.pats_all(subpats.iter().map(|f| f.pat.clone()), pred);
138 self.add_node(pat.id, [pats_exit])
141 ast::PatVec(ref pre, ref vec, ref post) => {
143 self.pats_all(pre.iter().map(|p| *p), pred);
145 self.pats_all(vec.iter().map(|p| *p), pre_exit);
147 self.pats_all(post.iter().map(|p| *p), vec_exit);
148 self.add_node(pat.id, [post_exit])
152 self.tcx.sess.span_bug(pat.span, "unexpanded macro");
157 fn pats_all<I: Iterator<Gc<ast::Pat>>>(&mut self,
159 pred: CFGIndex) -> CFGIndex {
160 //! Handles case where all of the patterns must match.
162 pats.fold(pred, |pred, pat| self.pat(&*pat, pred))
165 fn pats_any(&mut self,
166 pats: &[Gc<ast::Pat>],
167 pred: CFGIndex) -> CFGIndex {
168 //! Handles case where just one of the patterns must match.
171 self.pat(&*pats[0], pred)
173 let collect = self.add_dummy_node([]);
174 for &pat in pats.iter() {
175 let pat_exit = self.pat(&*pat, pred);
176 self.add_contained_edge(pat_exit, collect);
182 fn expr(&mut self, expr: Gc<ast::Expr>, pred: CFGIndex) -> CFGIndex {
184 ast::ExprBlock(ref blk) => {
185 let blk_exit = self.block(&**blk, pred);
186 self.add_node(expr.id, [blk_exit])
189 ast::ExprIf(ref cond, ref then, None) => {
204 let cond_exit = self.expr(cond.clone(), pred); // 1
205 let then_exit = self.block(&**then, cond_exit); // 2
206 self.add_node(expr.id, [cond_exit, then_exit]) // 3,4
209 ast::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
224 let cond_exit = self.expr(cond.clone(), pred); // 1
225 let then_exit = self.block(&**then, cond_exit); // 2
226 let else_exit = self.expr(otherwise.clone(), cond_exit); // 3
227 self.add_node(expr.id, [then_exit, else_exit]) // 4, 5
230 ast::ExprWhile(ref cond, ref body, _) => {
245 // Note that `break` and `continue` statements
246 // may cause additional edges.
248 // Is the condition considered part of the loop?
249 let loopback = self.add_dummy_node([pred]); // 1
250 let cond_exit = self.expr(cond.clone(), loopback); // 2
251 let expr_exit = self.add_node(expr.id, [cond_exit]); // 3
252 self.loop_scopes.push(LoopScope {
254 continue_index: loopback,
255 break_index: expr_exit
257 let body_exit = self.block(&**body, cond_exit); // 4
258 self.add_contained_edge(body_exit, loopback); // 5
259 self.loop_scopes.pop();
263 ast::ExprForLoop(ref pat, ref head, ref body, _) => {
283 // Note that `break` and `continue` statements
284 // may cause additional edges.
286 let head = self.expr(head.clone(), pred); // 1
287 let loopback = self.add_dummy_node([head]); // 2
288 let cond = self.add_dummy_node([loopback]); // 3
289 let expr_exit = self.add_node(expr.id, [cond]); // 4
290 self.loop_scopes.push(LoopScope {
292 continue_index: loopback,
293 break_index: expr_exit,
295 let pat = self.pat(&**pat, cond); // 5
296 let body = self.block(&**body, pat); // 6
297 self.add_contained_edge(body, loopback); // 7
298 self.loop_scopes.pop();
302 ast::ExprLoop(ref body, _) => {
314 // Note that `break` and `loop` statements
315 // may cause additional edges.
317 let loopback = self.add_dummy_node([pred]); // 1
318 let expr_exit = self.add_node(expr.id, []); // 2
319 self.loop_scopes.push(LoopScope {
321 continue_index: loopback,
322 break_index: expr_exit,
324 let body_exit = self.block(&**body, loopback); // 3
325 self.add_contained_edge(body_exit, loopback); // 4
326 self.loop_scopes.pop();
330 ast::ExprMatch(ref discr, ref arms) => {
356 let discr_exit = self.expr(discr.clone(), pred); // 1
358 let expr_exit = self.add_node(expr.id, []);
359 let mut cond_exit = discr_exit;
360 for arm in arms.iter() {
361 cond_exit = self.add_dummy_node([cond_exit]); // 2
362 let pats_exit = self.pats_any(arm.pats.as_slice(),
364 let guard_exit = self.opt_expr(arm.guard,
366 let body_exit = self.expr(arm.body.clone(),
368 self.add_contained_edge(body_exit, expr_exit); // 6
373 ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op) => {
388 let l_exit = self.expr(l.clone(), pred); // 1
389 let r_exit = self.expr(r.clone(), l_exit); // 2
390 self.add_node(expr.id, [l_exit, r_exit]) // 3,4
393 ast::ExprRet(ref v) => {
394 let v_exit = self.opt_expr(v.clone(), pred);
395 let b = self.add_node(expr.id, [v_exit]);
396 self.add_returning_edge(expr, b);
397 self.add_node(ast::DUMMY_NODE_ID, [])
400 ast::ExprBreak(label) => {
401 let loop_scope = self.find_scope(expr, label);
402 let b = self.add_node(expr.id, [pred]);
403 self.add_exiting_edge(expr, b,
404 loop_scope, loop_scope.break_index);
405 self.add_node(ast::DUMMY_NODE_ID, [])
408 ast::ExprAgain(label) => {
409 let loop_scope = self.find_scope(expr, label);
410 let a = self.add_node(expr.id, [pred]);
411 self.add_exiting_edge(expr, a,
412 loop_scope, loop_scope.continue_index);
413 self.add_node(ast::DUMMY_NODE_ID, [])
416 ast::ExprVec(ref elems) => {
417 self.straightline(expr, pred, elems.as_slice())
420 ast::ExprCall(ref func, ref args) => {
421 self.call(expr, pred, func.clone(), args.as_slice())
424 ast::ExprMethodCall(_, _, ref args) => {
425 self.call(expr, pred, *args.get(0), args.slice_from(1))
428 ast::ExprIndex(ref l, ref r) |
429 ast::ExprBinary(_, ref l, ref r) if self.is_method_call(&*expr) => {
430 self.call(expr, pred, l.clone(), [r.clone()])
433 ast::ExprUnary(_, ref e) if self.is_method_call(&*expr) => {
434 self.call(expr, pred, e.clone(), [])
437 ast::ExprTup(ref exprs) => {
438 self.straightline(expr, pred, exprs.as_slice())
441 ast::ExprStruct(_, ref fields, base) => {
442 let base_exit = self.opt_expr(base, pred);
443 let field_exprs: Vec<Gc<ast::Expr>> =
444 fields.iter().map(|f| f.expr).collect();
445 self.straightline(expr, base_exit, field_exprs.as_slice())
448 ast::ExprRepeat(elem, count) => {
449 self.straightline(expr, pred, [elem, count])
452 ast::ExprAssign(l, r) |
453 ast::ExprAssignOp(_, l, r) => {
454 self.straightline(expr, pred, [r, l])
457 ast::ExprIndex(l, r) |
458 ast::ExprBinary(_, l, r) => { // NB: && and || handled earlier
459 self.straightline(expr, pred, [l, r])
462 ast::ExprBox(p, e) => {
463 self.straightline(expr, pred, [p, e])
466 ast::ExprAddrOf(_, e) |
467 ast::ExprCast(e, _) |
468 ast::ExprUnary(_, e) |
470 ast::ExprField(e, _, _) |
471 ast::ExprTupField(e, _, _) => {
472 self.straightline(expr, pred, [e])
475 ast::ExprInlineAsm(ref inline_asm) => {
476 let inputs = inline_asm.inputs.iter();
477 let outputs = inline_asm.outputs.iter();
478 let post_inputs = self.exprs(inputs.map(|a| {
479 debug!("cfg::construct InlineAsm id:{} input:{:?}", expr.id, a);
483 let post_outputs = self.exprs(outputs.map(|a| {
484 debug!("cfg::construct InlineAsm id:{} output:{:?}", expr.id, a);
485 let &(_, expr, _) = a;
488 self.add_node(expr.id, [post_outputs])
492 ast::ExprFnBlock(..) |
494 ast::ExprUnboxedFn(..) |
496 ast::ExprPath(..) => {
497 self.straightline(expr, pred, [])
503 call_expr: Gc<ast::Expr>,
505 func_or_rcvr: Gc<ast::Expr>,
506 args: &[Gc<ast::Expr>]) -> CFGIndex {
507 let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
508 let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
510 let return_ty = ty::node_id_to_type(self.tcx, call_expr.id);
511 let fails = ty::type_is_bot(return_ty);
513 self.add_node(ast::DUMMY_NODE_ID, [])
519 fn exprs<I:Iterator<Gc<ast::Expr>>>(&mut self,
521 pred: CFGIndex) -> CFGIndex {
522 //! Constructs graph for `exprs` evaluated in order
523 exprs.fold(pred, |p, e| self.expr(e, p))
526 fn opt_expr(&mut self,
527 opt_expr: Option<Gc<ast::Expr>>,
528 pred: CFGIndex) -> CFGIndex {
529 //! Constructs graph for `opt_expr` evaluated, if Some
531 opt_expr.iter().fold(pred, |p, &e| self.expr(e, p))
534 fn straightline(&mut self,
537 subexprs: &[Gc<ast::Expr>]) -> CFGIndex {
538 //! Handles case of an expression that evaluates `subexprs` in order
540 let subexprs_exit = self.exprs(subexprs.iter().map(|&e|e), pred);
541 self.add_node(expr.id, [subexprs_exit])
544 fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
545 self.add_node(ast::DUMMY_NODE_ID, preds)
548 fn add_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
549 assert!(!self.exit_map.contains_key(&id));
550 let node = self.graph.add_node(CFGNodeData {id: id});
551 if id != ast::DUMMY_NODE_ID {
552 assert!(!self.exit_map.contains_key(&id));
553 self.exit_map.insert(id, node);
555 for &pred in preds.iter() {
556 self.add_contained_edge(pred, node);
561 fn add_contained_edge(&mut self,
564 let data = CFGEdgeData {exiting_scopes: vec!() };
565 self.graph.add_edge(source, target, data);
568 fn add_exiting_edge(&mut self,
569 from_expr: Gc<ast::Expr>,
570 from_index: CFGIndex,
572 to_index: CFGIndex) {
573 let mut data = CFGEdgeData {exiting_scopes: vec!() };
574 let mut scope_id = from_expr.id;
575 while scope_id != to_loop.loop_id {
577 data.exiting_scopes.push(scope_id);
578 scope_id = self.tcx.region_maps.encl_scope(scope_id);
580 self.graph.add_edge(from_index, to_index, data);
583 fn add_returning_edge(&mut self,
584 _from_expr: Gc<ast::Expr>,
585 from_index: CFGIndex) {
586 let mut data = CFGEdgeData {
587 exiting_scopes: vec!(),
589 for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
590 data.exiting_scopes.push(id);
592 self.graph.add_edge(from_index, self.fn_exit, data);
597 label: Option<ast::Ident>) -> LoopScope {
600 return *self.loop_scopes.last().unwrap();
604 match self.tcx.def_map.borrow().find(&expr.id) {
605 Some(&def::DefLabel(loop_id)) => {
606 for l in self.loop_scopes.iter() {
607 if l.loop_id == loop_id {
611 self.tcx.sess.span_bug(
613 format!("no loop scope for id {:?}",
614 loop_id).as_slice());
618 self.tcx.sess.span_bug(
620 format!("bad entry `{:?}` in def_map for label",
628 fn is_method_call(&self, expr: &ast::Expr) -> bool {
629 let method_call = typeck::MethodCall::expr(expr.id);
630 self.tcx.method_map.borrow().contains_key(&method_call)