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 ty::{self, TyCtxt};
17 use hir::{self, PatKind};
19 struct CFGBuilder<'a, 'tcx: 'a> {
20 tcx: TyCtxt<'a, 'tcx, 'tcx>,
21 tables: &'a ty::TypeckTables<'tcx>,
24 loop_scopes: Vec<LoopScope>,
25 breakable_block_scopes: Vec<BlockScope>,
28 #[derive(Copy, Clone)]
30 block_expr_id: ast::NodeId, // id of breakable block expr node
31 break_index: CFGIndex, // where to go on `break`
34 #[derive(Copy, Clone)]
36 loop_id: ast::NodeId, // id of loop/while node
37 continue_index: CFGIndex, // where to go on a `loop`
38 break_index: CFGIndex, // where to go on a `break`
41 pub fn construct<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
42 body: &hir::Body) -> CFG {
43 let mut graph = graph::Graph::new();
44 let entry = graph.add_node(CFGNodeData::Entry);
46 // `fn_exit` is target of return exprs, which lies somewhere
47 // outside input `body`. (Distinguishing `fn_exit` and `body_exit`
48 // also resolves chicken-and-egg problem that arises if you try to
49 // have return exprs jump to `body_exit` during construction.)
50 let fn_exit = graph.add_node(CFGNodeData::Exit);
53 // Find the tables for this body.
54 let owner_def_id = tcx.hir.local_def_id(tcx.hir.body_owner(body.id()));
55 let tables = tcx.typeck_tables_of(owner_def_id);
57 let mut cfg_builder = CFGBuilder {
62 loop_scopes: Vec::new(),
63 breakable_block_scopes: Vec::new(),
65 body_exit = cfg_builder.expr(&body.value, entry);
66 cfg_builder.add_contained_edge(body_exit, fn_exit);
67 let CFGBuilder { graph, .. } = cfg_builder;
75 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
76 fn block(&mut self, blk: &hir::Block, pred: CFGIndex) -> CFGIndex {
77 if blk.targeted_by_break {
78 let expr_exit = self.add_ast_node(blk.id, &[]);
80 self.breakable_block_scopes.push(BlockScope {
81 block_expr_id: blk.id,
82 break_index: expr_exit,
85 let mut stmts_exit = pred;
86 for stmt in &blk.stmts {
87 stmts_exit = self.stmt(stmt, stmts_exit);
89 let blk_expr_exit = self.opt_expr(&blk.expr, stmts_exit);
90 self.add_contained_edge(blk_expr_exit, expr_exit);
92 self.breakable_block_scopes.pop();
96 let mut stmts_exit = pred;
97 for stmt in &blk.stmts {
98 stmts_exit = self.stmt(stmt, stmts_exit);
101 let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
103 self.add_ast_node(blk.id, &[expr_exit])
107 fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex {
109 hir::StmtDecl(ref decl, id) => {
110 let exit = self.decl(&decl, pred);
111 self.add_ast_node(id, &[exit])
114 hir::StmtExpr(ref expr, id) |
115 hir::StmtSemi(ref expr, id) => {
116 let exit = self.expr(&expr, pred);
117 self.add_ast_node(id, &[exit])
122 fn decl(&mut self, decl: &hir::Decl, pred: CFGIndex) -> CFGIndex {
124 hir::DeclLocal(ref local) => {
125 let init_exit = self.opt_expr(&local.init, pred);
126 self.pat(&local.pat, init_exit)
129 hir::DeclItem(_) => pred,
133 fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex {
135 PatKind::Binding(.., None) |
139 PatKind::Wild => self.add_ast_node(pat.id, &[pred]),
141 PatKind::Box(ref subpat) |
142 PatKind::Ref(ref subpat, _) |
143 PatKind::Binding(.., Some(ref subpat)) => {
144 let subpat_exit = self.pat(&subpat, pred);
145 self.add_ast_node(pat.id, &[subpat_exit])
148 PatKind::TupleStruct(_, ref subpats, _) |
149 PatKind::Tuple(ref subpats, _) => {
150 let pats_exit = self.pats_all(subpats.iter(), pred);
151 self.add_ast_node(pat.id, &[pats_exit])
154 PatKind::Struct(_, ref subpats, _) => {
155 let pats_exit = self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
156 self.add_ast_node(pat.id, &[pats_exit])
159 PatKind::Slice(ref pre, ref vec, ref post) => {
160 let pre_exit = self.pats_all(pre.iter(), pred);
161 let vec_exit = self.pats_all(vec.iter(), pre_exit);
162 let post_exit = self.pats_all(post.iter(), vec_exit);
163 self.add_ast_node(pat.id, &[post_exit])
168 fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>(&mut self,
170 pred: CFGIndex) -> CFGIndex {
171 //! Handles case where all of the patterns must match.
172 pats.fold(pred, |pred, pat| self.pat(&pat, pred))
175 fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex {
177 hir::ExprBlock(ref blk) => {
178 let blk_exit = self.block(&blk, pred);
179 self.add_ast_node(expr.id, &[blk_exit])
182 hir::ExprIf(ref cond, ref then, None) => {
197 let cond_exit = self.expr(&cond, pred); // 1
198 let then_exit = self.expr(&then, cond_exit); // 2
199 self.add_ast_node(expr.id, &[cond_exit, then_exit]) // 3,4
202 hir::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
217 let cond_exit = self.expr(&cond, pred); // 1
218 let then_exit = self.expr(&then, cond_exit); // 2
219 let else_exit = self.expr(&otherwise, cond_exit); // 3
220 self.add_ast_node(expr.id, &[then_exit, else_exit]) // 4, 5
223 hir::ExprWhile(ref cond, ref body, _) => {
238 // Note that `break` and `continue` statements
239 // may cause additional edges.
241 let loopback = self.add_dummy_node(&[pred]); // 1
243 // Create expr_exit without pred (cond_exit)
244 let expr_exit = self.add_ast_node(expr.id, &[]); // 3
246 // The LoopScope needs to be on the loop_scopes stack while evaluating the
247 // condition and the body of the loop (both can break out of the loop)
248 self.loop_scopes.push(LoopScope {
250 continue_index: loopback,
251 break_index: expr_exit
254 let cond_exit = self.expr(&cond, loopback); // 2
256 // Add pred (cond_exit) to expr_exit
257 self.add_contained_edge(cond_exit, expr_exit);
259 let body_exit = self.block(&body, cond_exit); // 4
260 self.add_contained_edge(body_exit, loopback); // 5
261 self.loop_scopes.pop();
265 hir::ExprLoop(ref body, _, _) => {
277 // Note that `break` and `loop` statements
278 // may cause additional edges.
280 let loopback = self.add_dummy_node(&[pred]); // 1
281 let expr_exit = self.add_ast_node(expr.id, &[]); // 2
282 self.loop_scopes.push(LoopScope {
284 continue_index: loopback,
285 break_index: expr_exit,
287 let body_exit = self.block(&body, loopback); // 3
288 self.add_contained_edge(body_exit, loopback); // 4
289 self.loop_scopes.pop();
293 hir::ExprMatch(ref discr, ref arms, _) => {
294 self.match_(expr.id, &discr, &arms, pred)
297 hir::ExprBinary(op, ref l, ref r) if op.node.is_lazy() => {
312 let l_exit = self.expr(&l, pred); // 1
313 let r_exit = self.expr(&r, l_exit); // 2
314 self.add_ast_node(expr.id, &[l_exit, r_exit]) // 3,4
317 hir::ExprRet(ref v) => {
318 let v_exit = self.opt_expr(v, pred);
319 let b = self.add_ast_node(expr.id, &[v_exit]);
320 self.add_returning_edge(expr, b);
321 self.add_unreachable_node()
324 hir::ExprBreak(destination, ref opt_expr) => {
325 let v = self.opt_expr(opt_expr, pred);
326 let (scope_id, break_dest) =
327 self.find_scope_edge(expr, destination, ScopeCfKind::Break);
328 let b = self.add_ast_node(expr.id, &[v]);
329 self.add_exiting_edge(expr, b, scope_id, break_dest);
330 self.add_unreachable_node()
333 hir::ExprAgain(destination) => {
334 let (scope_id, cont_dest) =
335 self.find_scope_edge(expr, destination, ScopeCfKind::Continue);
336 let a = self.add_ast_node(expr.id, &[pred]);
337 self.add_exiting_edge(expr, a, scope_id, cont_dest);
338 self.add_unreachable_node()
341 hir::ExprArray(ref elems) => {
342 self.straightline(expr, pred, elems.iter().map(|e| &*e))
345 hir::ExprCall(ref func, ref args) => {
346 self.call(expr, pred, &func, args.iter().map(|e| &*e))
349 hir::ExprMethodCall(.., ref args) => {
350 self.call(expr, pred, &args[0], args[1..].iter().map(|e| &*e))
353 hir::ExprIndex(ref l, ref r) |
354 hir::ExprBinary(_, ref l, ref r) if self.tables.is_method_call(expr.id) => {
355 self.call(expr, pred, &l, Some(&**r).into_iter())
358 hir::ExprUnary(_, ref e) if self.tables.is_method_call(expr.id) => {
359 self.call(expr, pred, &e, None::<hir::Expr>.iter())
362 hir::ExprTup(ref exprs) => {
363 self.straightline(expr, pred, exprs.iter().map(|e| &*e))
366 hir::ExprStruct(_, ref fields, ref base) => {
367 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
368 self.opt_expr(base, field_cfg)
371 hir::ExprAssign(ref l, ref r) |
372 hir::ExprAssignOp(_, ref l, ref r) => {
373 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
376 hir::ExprIndex(ref l, ref r) |
377 hir::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier
378 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
381 hir::ExprBox(ref e) |
382 hir::ExprAddrOf(_, ref e) |
383 hir::ExprCast(ref e, _) |
384 hir::ExprType(ref e, _) |
385 hir::ExprUnary(_, ref e) |
386 hir::ExprField(ref e, _) |
387 hir::ExprTupField(ref e, _) |
388 hir::ExprRepeat(ref e, _) => {
389 self.straightline(expr, pred, Some(&**e).into_iter())
392 hir::ExprInlineAsm(_, ref outputs, ref inputs) => {
393 let post_outputs = self.exprs(outputs.iter().map(|e| &*e), pred);
394 let post_inputs = self.exprs(inputs.iter().map(|e| &*e), post_outputs);
395 self.add_ast_node(expr.id, &[post_inputs])
398 hir::ExprClosure(..) |
400 hir::ExprPath(_) => {
401 self.straightline(expr, pred, None::<hir::Expr>.iter())
406 fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
407 call_expr: &hir::Expr,
409 func_or_rcvr: &hir::Expr,
410 args: I) -> CFGIndex {
411 let method_call = ty::MethodCall::expr(call_expr.id);
412 let fn_ty = match self.tables.method_map.get(&method_call) {
413 Some(method) => method.ty,
414 None => self.tables.expr_ty_adjusted(func_or_rcvr),
417 let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
418 let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
419 // FIXME(canndrew): This is_never should probably be an is_uninhabited.
420 if fn_ty.fn_ret().0.is_never() {
421 self.add_unreachable_node()
427 fn exprs<'b, I: Iterator<Item=&'b hir::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<hir::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 hir::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: &hir::Expr,
452 arms: &[hir::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.contains_bindings_or_wild();
498 // If both this pattern and the previous pattern
499 // were free of bindings, they must consist only
500 // of "constant" patterns. Note we cannot match an
501 // all-constant pattern, fail the guard, and then
502 // match *another* all-constant pattern. This is
503 // because if the previous pattern matches, then
504 // we *cannot* match this one, unless all the
505 // constants are the same (which is rejected by
508 // We can use this to be smarter about the flow
509 // along guards. If the previous pattern matched,
510 // then we know we will not visit the guard in
511 // this one (whether or not the guard succeeded),
512 // if the previous pattern failed, then we know
513 // the guard for that pattern will not have been
514 // visited. Thus, it is not possible to visit both
515 // the previous guard and the current one when
516 // both patterns consist only of constant
519 // However, if the above does not hold, then all
520 // previous guards need to be wired to visit the
521 // current guard pattern.
522 if prev_has_bindings || this_has_bindings {
523 while let Some(prev) = prev_guards.pop() {
524 self.add_contained_edge(prev, guard_start);
528 prev_has_bindings = this_has_bindings;
530 // Push the guard onto the list of previous guards
531 prev_guards.push(guard_exit);
533 // Update the exit node for the pattern
534 pat_exit = guard_exit;
537 // Add an edge from the exit of this pattern to the
539 self.add_contained_edge(pat_exit, arm_exit);
542 // Visit the body of this arm
543 let body_exit = self.expr(&arm.body, arm_exit);
545 // Link the body to the exit of the expression
546 self.add_contained_edge(body_exit, expr_exit);
552 fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
553 self.add_node(CFGNodeData::Dummy, preds)
556 fn add_ast_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
557 assert!(id != ast::DUMMY_NODE_ID);
558 self.add_node(CFGNodeData::AST(id), preds)
561 fn add_unreachable_node(&mut self) -> CFGIndex {
562 self.add_node(CFGNodeData::Unreachable, &[])
565 fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
566 let node = self.graph.add_node(data);
568 self.add_contained_edge(pred, node);
573 fn add_contained_edge(&mut self,
576 let data = CFGEdgeData {exiting_scopes: vec![] };
577 self.graph.add_edge(source, target, data);
580 fn add_exiting_edge(&mut self,
581 from_expr: &hir::Expr,
582 from_index: CFGIndex,
583 scope_id: ast::NodeId,
584 to_index: CFGIndex) {
585 let mut data = CFGEdgeData { exiting_scopes: vec![] };
586 let mut scope = self.tcx.node_extent(from_expr.id);
587 let target_scope = self.tcx.node_extent(scope_id);
588 while scope != target_scope {
589 data.exiting_scopes.push(scope.node_id());
590 scope = self.tcx.region_maps().encl_scope(scope);
592 self.graph.add_edge(from_index, to_index, data);
595 fn add_returning_edge(&mut self,
596 _from_expr: &hir::Expr,
597 from_index: CFGIndex) {
598 let mut data = CFGEdgeData {
599 exiting_scopes: vec![],
601 for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
602 data.exiting_scopes.push(id);
604 self.graph.add_edge(from_index, self.fn_exit, data);
607 fn find_scope_edge(&self,
609 destination: hir::Destination,
610 scope_cf_kind: ScopeCfKind) -> (ast::NodeId, CFGIndex) {
612 match destination.target_id {
613 hir::ScopeTarget::Block(block_expr_id) => {
614 for b in &self.breakable_block_scopes {
615 if b.block_expr_id == block_expr_id {
616 return (block_expr_id, match scope_cf_kind {
617 ScopeCfKind::Break => b.break_index,
618 ScopeCfKind::Continue => bug!("can't continue to block"),
622 span_bug!(expr.span, "no block expr for id {}", block_expr_id);
624 hir::ScopeTarget::Loop(hir::LoopIdResult::Ok(loop_id)) => {
625 for l in &self.loop_scopes {
626 if l.loop_id == loop_id {
627 return (loop_id, match scope_cf_kind {
628 ScopeCfKind::Break => l.break_index,
629 ScopeCfKind::Continue => l.continue_index,
633 span_bug!(expr.span, "no loop scope for id {}", loop_id);
635 hir::ScopeTarget::Loop(hir::LoopIdResult::Err(err)) =>
636 span_bug!(expr.span, "loop scope error: {}", err),
641 #[derive(Copy, Clone, Eq, PartialEq)]