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;
13 use middle::region::CodeExtent;
14 use ty::{self, TyCtxt};
18 use hir::{self, PatKind};
19 use hir::def_id::DefId;
21 struct CFGBuilder<'a, 'tcx: 'a> {
22 tcx: TyCtxt<'a, 'tcx, 'tcx>,
24 tables: &'a ty::TypeckTables<'tcx>,
27 loop_scopes: Vec<LoopScope>,
28 breakable_block_scopes: Vec<BlockScope>,
31 #[derive(Copy, Clone)]
33 block_expr_id: ast::NodeId, // id of breakable block expr node
34 break_index: CFGIndex, // where to go on `break`
37 #[derive(Copy, Clone)]
39 loop_id: ast::NodeId, // id of loop/while node
40 continue_index: CFGIndex, // where to go on a `loop`
41 break_index: CFGIndex, // where to go on a `break`
44 pub fn construct<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
45 body: &hir::Body) -> CFG {
46 let mut graph = graph::Graph::new();
47 let entry = graph.add_node(CFGNodeData::Entry);
49 // `fn_exit` is target of return exprs, which lies somewhere
50 // outside input `body`. (Distinguishing `fn_exit` and `body_exit`
51 // also resolves chicken-and-egg problem that arises if you try to
52 // have return exprs jump to `body_exit` during construction.)
53 let fn_exit = graph.add_node(CFGNodeData::Exit);
56 // Find the tables for this body.
57 let owner_def_id = tcx.hir.local_def_id(tcx.hir.body_owner(body.id()));
58 let tables = tcx.typeck_tables_of(owner_def_id);
60 let mut cfg_builder = CFGBuilder {
66 loop_scopes: Vec::new(),
67 breakable_block_scopes: Vec::new(),
69 body_exit = cfg_builder.expr(&body.value, entry);
70 cfg_builder.add_contained_edge(body_exit, fn_exit);
71 let CFGBuilder { graph, .. } = cfg_builder;
79 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
80 fn block(&mut self, blk: &hir::Block, pred: CFGIndex) -> CFGIndex {
81 if blk.targeted_by_break {
82 let expr_exit = self.add_ast_node(blk.id, &[]);
84 self.breakable_block_scopes.push(BlockScope {
85 block_expr_id: blk.id,
86 break_index: expr_exit,
89 let mut stmts_exit = pred;
90 for stmt in &blk.stmts {
91 stmts_exit = self.stmt(stmt, stmts_exit);
93 let blk_expr_exit = self.opt_expr(&blk.expr, stmts_exit);
94 self.add_contained_edge(blk_expr_exit, expr_exit);
96 self.breakable_block_scopes.pop();
100 let mut stmts_exit = pred;
101 for stmt in &blk.stmts {
102 stmts_exit = self.stmt(stmt, stmts_exit);
105 let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
107 self.add_ast_node(blk.id, &[expr_exit])
111 fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex {
113 hir::StmtDecl(ref decl, id) => {
114 let exit = self.decl(&decl, pred);
115 self.add_ast_node(id, &[exit])
118 hir::StmtExpr(ref expr, id) |
119 hir::StmtSemi(ref expr, id) => {
120 let exit = self.expr(&expr, pred);
121 self.add_ast_node(id, &[exit])
126 fn decl(&mut self, decl: &hir::Decl, pred: CFGIndex) -> CFGIndex {
128 hir::DeclLocal(ref local) => {
129 let init_exit = self.opt_expr(&local.init, pred);
130 self.pat(&local.pat, init_exit)
133 hir::DeclItem(_) => pred,
137 fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex {
139 PatKind::Binding(.., None) |
143 PatKind::Wild => self.add_ast_node(pat.id, &[pred]),
145 PatKind::Box(ref subpat) |
146 PatKind::Ref(ref subpat, _) |
147 PatKind::Binding(.., Some(ref subpat)) => {
148 let subpat_exit = self.pat(&subpat, pred);
149 self.add_ast_node(pat.id, &[subpat_exit])
152 PatKind::TupleStruct(_, ref subpats, _) |
153 PatKind::Tuple(ref subpats, _) => {
154 let pats_exit = self.pats_all(subpats.iter(), pred);
155 self.add_ast_node(pat.id, &[pats_exit])
158 PatKind::Struct(_, ref subpats, _) => {
159 let pats_exit = self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
160 self.add_ast_node(pat.id, &[pats_exit])
163 PatKind::Slice(ref pre, ref vec, ref post) => {
164 let pre_exit = self.pats_all(pre.iter(), pred);
165 let vec_exit = self.pats_all(vec.iter(), pre_exit);
166 let post_exit = self.pats_all(post.iter(), vec_exit);
167 self.add_ast_node(pat.id, &[post_exit])
172 fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>(&mut self,
174 pred: CFGIndex) -> CFGIndex {
175 //! Handles case where all of the patterns must match.
176 pats.fold(pred, |pred, pat| self.pat(&pat, pred))
179 fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex {
181 hir::ExprBlock(ref blk) => {
182 let blk_exit = self.block(&blk, pred);
183 self.add_ast_node(expr.id, &[blk_exit])
186 hir::ExprIf(ref cond, ref then, None) => {
201 let cond_exit = self.expr(&cond, pred); // 1
202 let then_exit = self.expr(&then, cond_exit); // 2
203 self.add_ast_node(expr.id, &[cond_exit, then_exit]) // 3,4
206 hir::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
221 let cond_exit = self.expr(&cond, pred); // 1
222 let then_exit = self.expr(&then, cond_exit); // 2
223 let else_exit = self.expr(&otherwise, cond_exit); // 3
224 self.add_ast_node(expr.id, &[then_exit, else_exit]) // 4, 5
227 hir::ExprWhile(ref cond, ref body, _) => {
242 // Note that `break` and `continue` statements
243 // may cause additional edges.
245 let loopback = self.add_dummy_node(&[pred]); // 1
247 // Create expr_exit without pred (cond_exit)
248 let expr_exit = self.add_ast_node(expr.id, &[]); // 3
250 // The LoopScope needs to be on the loop_scopes stack while evaluating the
251 // condition and the body of the loop (both can break out of the loop)
252 self.loop_scopes.push(LoopScope {
254 continue_index: loopback,
255 break_index: expr_exit
258 let cond_exit = self.expr(&cond, loopback); // 2
260 // Add pred (cond_exit) to expr_exit
261 self.add_contained_edge(cond_exit, expr_exit);
263 let body_exit = self.block(&body, cond_exit); // 4
264 self.add_contained_edge(body_exit, loopback); // 5
265 self.loop_scopes.pop();
269 hir::ExprLoop(ref body, _, _) => {
281 // Note that `break` and `loop` statements
282 // may cause additional edges.
284 let loopback = self.add_dummy_node(&[pred]); // 1
285 let expr_exit = self.add_ast_node(expr.id, &[]); // 2
286 self.loop_scopes.push(LoopScope {
288 continue_index: loopback,
289 break_index: expr_exit,
291 let body_exit = self.block(&body, loopback); // 3
292 self.add_contained_edge(body_exit, loopback); // 4
293 self.loop_scopes.pop();
297 hir::ExprMatch(ref discr, ref arms, _) => {
298 self.match_(expr.id, &discr, &arms, pred)
301 hir::ExprBinary(op, ref l, ref r) if op.node.is_lazy() => {
316 let l_exit = self.expr(&l, pred); // 1
317 let r_exit = self.expr(&r, l_exit); // 2
318 self.add_ast_node(expr.id, &[l_exit, r_exit]) // 3,4
321 hir::ExprRet(ref v) => {
322 let v_exit = self.opt_expr(v, pred);
323 let b = self.add_ast_node(expr.id, &[v_exit]);
324 self.add_returning_edge(expr, b);
325 self.add_unreachable_node()
328 hir::ExprBreak(destination, ref opt_expr) => {
329 let v = self.opt_expr(opt_expr, pred);
330 let (scope_id, break_dest) =
331 self.find_scope_edge(expr, destination, ScopeCfKind::Break);
332 let b = self.add_ast_node(expr.id, &[v]);
333 self.add_exiting_edge(expr, b, scope_id, break_dest);
334 self.add_unreachable_node()
337 hir::ExprAgain(destination) => {
338 let (scope_id, cont_dest) =
339 self.find_scope_edge(expr, destination, ScopeCfKind::Continue);
340 let a = self.add_ast_node(expr.id, &[pred]);
341 self.add_exiting_edge(expr, a, scope_id, cont_dest);
342 self.add_unreachable_node()
345 hir::ExprArray(ref elems) => {
346 self.straightline(expr, pred, elems.iter().map(|e| &*e))
349 hir::ExprCall(ref func, ref args) => {
350 self.call(expr, pred, &func, args.iter().map(|e| &*e))
353 hir::ExprMethodCall(.., ref args) => {
354 self.call(expr, pred, &args[0], args[1..].iter().map(|e| &*e))
357 hir::ExprIndex(ref l, ref r) |
358 hir::ExprBinary(_, ref l, ref r) if self.tables.is_method_call(expr.id) => {
359 self.call(expr, pred, &l, Some(&**r).into_iter())
362 hir::ExprUnary(_, ref e) if self.tables.is_method_call(expr.id) => {
363 self.call(expr, pred, &e, None::<hir::Expr>.iter())
366 hir::ExprTup(ref exprs) => {
367 self.straightline(expr, pred, exprs.iter().map(|e| &*e))
370 hir::ExprStruct(_, ref fields, ref base) => {
371 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
372 self.opt_expr(base, field_cfg)
375 hir::ExprAssign(ref l, ref r) |
376 hir::ExprAssignOp(_, ref l, ref r) => {
377 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
380 hir::ExprIndex(ref l, ref r) |
381 hir::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier
382 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
385 hir::ExprBox(ref e) |
386 hir::ExprAddrOf(_, ref e) |
387 hir::ExprCast(ref e, _) |
388 hir::ExprType(ref e, _) |
389 hir::ExprUnary(_, ref e) |
390 hir::ExprField(ref e, _) |
391 hir::ExprTupField(ref e, _) |
392 hir::ExprRepeat(ref e, _) => {
393 self.straightline(expr, pred, Some(&**e).into_iter())
396 hir::ExprInlineAsm(_, ref outputs, ref inputs) => {
397 let post_outputs = self.exprs(outputs.iter().map(|e| &*e), pred);
398 let post_inputs = self.exprs(inputs.iter().map(|e| &*e), post_outputs);
399 self.add_ast_node(expr.id, &[post_inputs])
402 hir::ExprClosure(..) |
404 hir::ExprPath(_) => {
405 self.straightline(expr, pred, None::<hir::Expr>.iter())
410 fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
411 call_expr: &hir::Expr,
413 func_or_rcvr: &hir::Expr,
414 args: I) -> CFGIndex {
415 let method_call = ty::MethodCall::expr(call_expr.id);
416 let fn_ty = match self.tables.method_map.get(&method_call) {
417 Some(method) => method.ty,
418 None => self.tables.expr_ty_adjusted(func_or_rcvr),
421 let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
422 let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
423 // FIXME(canndrew): This is_never should probably be an is_uninhabited.
424 if fn_ty.fn_ret().0.is_never() {
425 self.add_unreachable_node()
431 fn exprs<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
433 pred: CFGIndex) -> CFGIndex {
434 //! Constructs graph for `exprs` evaluated in order
435 exprs.fold(pred, |p, e| self.expr(e, p))
438 fn opt_expr(&mut self,
439 opt_expr: &Option<P<hir::Expr>>,
440 pred: CFGIndex) -> CFGIndex {
441 //! Constructs graph for `opt_expr` evaluated, if Some
442 opt_expr.iter().fold(pred, |p, e| self.expr(&e, p))
445 fn straightline<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
448 subexprs: I) -> CFGIndex {
449 //! Handles case of an expression that evaluates `subexprs` in order
451 let subexprs_exit = self.exprs(subexprs, pred);
452 self.add_ast_node(expr.id, &[subexprs_exit])
455 fn match_(&mut self, id: ast::NodeId, discr: &hir::Expr,
456 arms: &[hir::Arm], pred: CFGIndex) -> CFGIndex {
457 // The CFG for match expression is quite complex, so no ASCII
460 // The CFG generated below matches roughly what trans puts
461 // out. Each pattern and guard is visited in parallel, with
462 // arms containing multiple patterns generating multiple nodes
463 // for the same guard expression. The guard expressions chain
464 // into each other from top to bottom, with a specific
465 // exception to allow some additional valid programs
466 // (explained below). Trans differs slightly in that the
467 // pattern matching may continue after a guard but the visible
468 // behaviour should be the same.
470 // What is going on is explained in further comments.
472 // Visit the discriminant expression
473 let discr_exit = self.expr(discr, pred);
475 // Add a node for the exit of the match expression as a whole.
476 let expr_exit = self.add_ast_node(id, &[]);
478 // Keep track of the previous guard expressions
479 let mut prev_guards = Vec::new();
480 // Track if the previous pattern contained bindings or wildcards
481 let mut prev_has_bindings = false;
484 // Add an exit node for when we've visited all the
485 // patterns and the guard (if there is one) in the arm.
486 let arm_exit = self.add_dummy_node(&[]);
488 for pat in &arm.pats {
489 // Visit the pattern, coming from the discriminant exit
490 let mut pat_exit = self.pat(&pat, discr_exit);
492 // If there is a guard expression, handle it here
493 if let Some(ref guard) = arm.guard {
494 // Add a dummy node for the previous guard
495 // expression to target
496 let guard_start = self.add_dummy_node(&[pat_exit]);
497 // Visit the guard expression
498 let guard_exit = self.expr(&guard, guard_start);
500 let this_has_bindings = pat.contains_bindings_or_wild();
502 // If both this pattern and the previous pattern
503 // were free of bindings, they must consist only
504 // of "constant" patterns. Note we cannot match an
505 // all-constant pattern, fail the guard, and then
506 // match *another* all-constant pattern. This is
507 // because if the previous pattern matches, then
508 // we *cannot* match this one, unless all the
509 // constants are the same (which is rejected by
512 // We can use this to be smarter about the flow
513 // along guards. If the previous pattern matched,
514 // then we know we will not visit the guard in
515 // this one (whether or not the guard succeeded),
516 // if the previous pattern failed, then we know
517 // the guard for that pattern will not have been
518 // visited. Thus, it is not possible to visit both
519 // the previous guard and the current one when
520 // both patterns consist only of constant
523 // However, if the above does not hold, then all
524 // previous guards need to be wired to visit the
525 // current guard pattern.
526 if prev_has_bindings || this_has_bindings {
527 while let Some(prev) = prev_guards.pop() {
528 self.add_contained_edge(prev, guard_start);
532 prev_has_bindings = this_has_bindings;
534 // Push the guard onto the list of previous guards
535 prev_guards.push(guard_exit);
537 // Update the exit node for the pattern
538 pat_exit = guard_exit;
541 // Add an edge from the exit of this pattern to the
543 self.add_contained_edge(pat_exit, arm_exit);
546 // Visit the body of this arm
547 let body_exit = self.expr(&arm.body, arm_exit);
549 // Link the body to the exit of the expression
550 self.add_contained_edge(body_exit, expr_exit);
556 fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
557 self.add_node(CFGNodeData::Dummy, preds)
560 fn add_ast_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
561 assert!(id != ast::DUMMY_NODE_ID);
562 self.add_node(CFGNodeData::AST(id), preds)
565 fn add_unreachable_node(&mut self) -> CFGIndex {
566 self.add_node(CFGNodeData::Unreachable, &[])
569 fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
570 let node = self.graph.add_node(data);
572 self.add_contained_edge(pred, node);
577 fn add_contained_edge(&mut self,
580 let data = CFGEdgeData {exiting_scopes: vec![] };
581 self.graph.add_edge(source, target, data);
584 fn add_exiting_edge(&mut self,
585 from_expr: &hir::Expr,
586 from_index: CFGIndex,
587 scope_id: ast::NodeId,
588 to_index: CFGIndex) {
589 let mut data = CFGEdgeData { exiting_scopes: vec![] };
590 let mut scope = CodeExtent::Misc(from_expr.id);
591 let target_scope = CodeExtent::Misc(scope_id);
592 let region_maps = self.tcx.region_maps(self.owner_def_id);
593 while scope != target_scope {
594 data.exiting_scopes.push(scope.node_id());
595 scope = region_maps.encl_scope(scope);
597 self.graph.add_edge(from_index, to_index, data);
600 fn add_returning_edge(&mut self,
601 _from_expr: &hir::Expr,
602 from_index: CFGIndex) {
603 let mut data = CFGEdgeData {
604 exiting_scopes: vec![],
606 for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
607 data.exiting_scopes.push(id);
609 self.graph.add_edge(from_index, self.fn_exit, data);
612 fn find_scope_edge(&self,
614 destination: hir::Destination,
615 scope_cf_kind: ScopeCfKind) -> (ast::NodeId, CFGIndex) {
617 match destination.target_id {
618 hir::ScopeTarget::Block(block_expr_id) => {
619 for b in &self.breakable_block_scopes {
620 if b.block_expr_id == block_expr_id {
621 return (block_expr_id, match scope_cf_kind {
622 ScopeCfKind::Break => b.break_index,
623 ScopeCfKind::Continue => bug!("can't continue to block"),
627 span_bug!(expr.span, "no block expr for id {}", block_expr_id);
629 hir::ScopeTarget::Loop(hir::LoopIdResult::Ok(loop_id)) => {
630 for l in &self.loop_scopes {
631 if l.loop_id == loop_id {
632 return (loop_id, match scope_cf_kind {
633 ScopeCfKind::Break => l.break_index,
634 ScopeCfKind::Continue => l.continue_index,
638 span_bug!(expr.span, "no loop scope for id {}", loop_id);
640 hir::ScopeTarget::Loop(hir::LoopIdResult::Err(err)) =>
641 span_bug!(expr.span, "loop scope error: {}", err),
646 #[derive(Copy, Clone, Eq, PartialEq)]