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.
13 use rustc_data_structures::graph::implementation as graph;
15 use ty::{self, TyCtxt};
17 use hir::{self, PatKind};
18 use hir::def_id::DefId;
20 struct CFGBuilder<'a, 'tcx: 'a> {
21 tcx: TyCtxt<'a, 'tcx, 'tcx>,
23 tables: &'a ty::TypeckTables<'tcx>,
26 loop_scopes: Vec<LoopScope>,
27 breakable_block_scopes: Vec<BlockScope>,
30 #[derive(Copy, Clone)]
32 block_expr_id: hir::ItemLocalId, // id of breakable block expr node
33 break_index: CFGIndex, // where to go on `break`
36 #[derive(Copy, Clone)]
38 loop_id: hir::ItemLocalId, // id of loop/while node
39 continue_index: CFGIndex, // where to go on a `loop`
40 break_index: CFGIndex, // where to go on a `break`
43 pub fn construct<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
44 body: &hir::Body) -> CFG {
45 let mut graph = graph::Graph::new();
46 let entry = graph.add_node(CFGNodeData::Entry);
48 // `fn_exit` is target of return exprs, which lies somewhere
49 // outside input `body`. (Distinguishing `fn_exit` and `body_exit`
50 // also resolves chicken-and-egg problem that arises if you try to
51 // have return exprs jump to `body_exit` during construction.)
52 let fn_exit = graph.add_node(CFGNodeData::Exit);
55 // Find the tables for this body.
56 let owner_def_id = tcx.hir().local_def_id(tcx.hir().body_owner(body.id()));
57 let tables = tcx.typeck_tables_of(owner_def_id);
59 let mut cfg_builder = CFGBuilder {
65 loop_scopes: Vec::new(),
66 breakable_block_scopes: Vec::new(),
68 body_exit = cfg_builder.expr(&body.value, entry);
69 cfg_builder.add_contained_edge(body_exit, fn_exit);
70 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.hir_id.local_id, &[]);
84 self.breakable_block_scopes.push(BlockScope {
85 block_expr_id: blk.hir_id.local_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.hir_id.local_id, &[expr_exit])
111 fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex {
112 let hir_id = self.tcx.hir().node_to_hir_id(stmt.node.id());
114 hir::StmtKind::Decl(ref decl, _) => {
115 let exit = self.decl(&decl, pred);
116 self.add_ast_node(hir_id.local_id, &[exit])
119 hir::StmtKind::Expr(ref expr, _) |
120 hir::StmtKind::Semi(ref expr, _) => {
121 let exit = self.expr(&expr, pred);
122 self.add_ast_node(hir_id.local_id, &[exit])
127 fn decl(&mut self, decl: &hir::Decl, pred: CFGIndex) -> CFGIndex {
129 hir::DeclKind::Local(ref local) => {
130 let init_exit = self.opt_expr(&local.init, pred);
131 self.pat(&local.pat, init_exit)
134 hir::DeclKind::Item(_) => pred,
138 fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex {
140 PatKind::Binding(.., None) |
144 PatKind::Wild => self.add_ast_node(pat.hir_id.local_id, &[pred]),
146 PatKind::Box(ref subpat) |
147 PatKind::Ref(ref subpat, _) |
148 PatKind::Binding(.., Some(ref subpat)) => {
149 let subpat_exit = self.pat(&subpat, pred);
150 self.add_ast_node(pat.hir_id.local_id, &[subpat_exit])
153 PatKind::TupleStruct(_, ref subpats, _) |
154 PatKind::Tuple(ref subpats, _) => {
155 let pats_exit = self.pats_all(subpats.iter(), pred);
156 self.add_ast_node(pat.hir_id.local_id, &[pats_exit])
159 PatKind::Struct(_, ref subpats, _) => {
160 let pats_exit = self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
161 self.add_ast_node(pat.hir_id.local_id, &[pats_exit])
164 PatKind::Slice(ref pre, ref vec, ref post) => {
165 let pre_exit = self.pats_all(pre.iter(), pred);
166 let vec_exit = self.pats_all(vec.iter(), pre_exit);
167 let post_exit = self.pats_all(post.iter(), vec_exit);
168 self.add_ast_node(pat.hir_id.local_id, &[post_exit])
173 fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>(&mut self,
175 pred: CFGIndex) -> CFGIndex {
176 //! Handles case where all of the patterns must match.
177 pats.fold(pred, |pred, pat| self.pat(&pat, pred))
180 fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex {
182 hir::ExprKind::Block(ref blk, _) => {
183 let blk_exit = self.block(&blk, pred);
184 self.add_ast_node(expr.hir_id.local_id, &[blk_exit])
187 hir::ExprKind::If(ref cond, ref then, None) => {
202 let cond_exit = self.expr(&cond, pred); // 1
203 let then_exit = self.expr(&then, cond_exit); // 2
204 self.add_ast_node(expr.hir_id.local_id, &[cond_exit, then_exit]) // 3,4
207 hir::ExprKind::If(ref cond, ref then, Some(ref otherwise)) => {
222 let cond_exit = self.expr(&cond, pred); // 1
223 let then_exit = self.expr(&then, cond_exit); // 2
224 let else_exit = self.expr(&otherwise, cond_exit); // 3
225 self.add_ast_node(expr.hir_id.local_id, &[then_exit, else_exit]) // 4, 5
228 hir::ExprKind::While(ref cond, ref body, _) => {
243 // Note that `break` and `continue` statements
244 // may cause additional edges.
246 let loopback = self.add_dummy_node(&[pred]); // 1
248 // Create expr_exit without pred (cond_exit)
249 let expr_exit = self.add_ast_node(expr.hir_id.local_id, &[]); // 3
251 // The LoopScope needs to be on the loop_scopes stack while evaluating the
252 // condition and the body of the loop (both can break out of the loop)
253 self.loop_scopes.push(LoopScope {
254 loop_id: expr.hir_id.local_id,
255 continue_index: loopback,
256 break_index: expr_exit
259 let cond_exit = self.expr(&cond, loopback); // 2
261 // Add pred (cond_exit) to expr_exit
262 self.add_contained_edge(cond_exit, expr_exit);
264 let body_exit = self.block(&body, cond_exit); // 4
265 self.add_contained_edge(body_exit, loopback); // 5
266 self.loop_scopes.pop();
270 hir::ExprKind::Loop(ref body, _, _) => {
282 // Note that `break` and `loop` statements
283 // may cause additional edges.
285 let loopback = self.add_dummy_node(&[pred]); // 1
286 let expr_exit = self.add_ast_node(expr.hir_id.local_id, &[]); // 2
287 self.loop_scopes.push(LoopScope {
288 loop_id: expr.hir_id.local_id,
289 continue_index: loopback,
290 break_index: expr_exit,
292 let body_exit = self.block(&body, loopback); // 3
293 self.add_contained_edge(body_exit, loopback); // 4
294 self.loop_scopes.pop();
298 hir::ExprKind::Match(ref discr, ref arms, _) => {
299 self.match_(expr.hir_id.local_id, &discr, &arms, pred)
302 hir::ExprKind::Binary(op, ref l, ref r) if op.node.is_lazy() => {
317 let l_exit = self.expr(&l, pred); // 1
318 let r_exit = self.expr(&r, l_exit); // 2
319 self.add_ast_node(expr.hir_id.local_id, &[l_exit, r_exit]) // 3,4
322 hir::ExprKind::Ret(ref v) => {
323 let v_exit = self.opt_expr(v, pred);
324 let b = self.add_ast_node(expr.hir_id.local_id, &[v_exit]);
325 self.add_returning_edge(expr, b);
326 self.add_unreachable_node()
329 hir::ExprKind::Break(destination, ref opt_expr) => {
330 let v = self.opt_expr(opt_expr, pred);
331 let (target_scope, break_dest) =
332 self.find_scope_edge(expr, destination, ScopeCfKind::Break);
333 let b = self.add_ast_node(expr.hir_id.local_id, &[v]);
334 self.add_exiting_edge(expr, b, target_scope, break_dest);
335 self.add_unreachable_node()
338 hir::ExprKind::Continue(destination) => {
339 let (target_scope, cont_dest) =
340 self.find_scope_edge(expr, destination, ScopeCfKind::Continue);
341 let a = self.add_ast_node(expr.hir_id.local_id, &[pred]);
342 self.add_exiting_edge(expr, a, target_scope, cont_dest);
343 self.add_unreachable_node()
346 hir::ExprKind::Array(ref elems) => {
347 self.straightline(expr, pred, elems.iter().map(|e| &*e))
350 hir::ExprKind::Call(ref func, ref args) => {
351 self.call(expr, pred, &func, args.iter().map(|e| &*e))
354 hir::ExprKind::MethodCall(.., ref args) => {
355 self.call(expr, pred, &args[0], args[1..].iter().map(|e| &*e))
358 hir::ExprKind::Index(ref l, ref r) |
359 hir::ExprKind::Binary(_, ref l, ref r) if self.tables.is_method_call(expr) => {
360 self.call(expr, pred, &l, Some(&**r).into_iter())
363 hir::ExprKind::Unary(_, ref e) if self.tables.is_method_call(expr) => {
364 self.call(expr, pred, &e, None::<hir::Expr>.iter())
367 hir::ExprKind::Tup(ref exprs) => {
368 self.straightline(expr, pred, exprs.iter().map(|e| &*e))
371 hir::ExprKind::Struct(_, ref fields, ref base) => {
372 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
373 self.opt_expr(base, field_cfg)
376 hir::ExprKind::Assign(ref l, ref r) |
377 hir::ExprKind::AssignOp(_, ref l, ref r) => {
378 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
381 hir::ExprKind::Index(ref l, ref r) |
382 hir::ExprKind::Binary(_, ref l, ref r) => { // NB: && and || handled earlier
383 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
386 hir::ExprKind::Box(ref e) |
387 hir::ExprKind::AddrOf(_, ref e) |
388 hir::ExprKind::Cast(ref e, _) |
389 hir::ExprKind::Type(ref e, _) |
390 hir::ExprKind::Unary(_, ref e) |
391 hir::ExprKind::Field(ref e, _) |
392 hir::ExprKind::Yield(ref e) |
393 hir::ExprKind::Repeat(ref e, _) => {
394 self.straightline(expr, pred, Some(&**e).into_iter())
397 hir::ExprKind::InlineAsm(_, ref outputs, ref inputs) => {
398 let post_outputs = self.exprs(outputs.iter().map(|e| &*e), pred);
399 let post_inputs = self.exprs(inputs.iter().map(|e| &*e), post_outputs);
400 self.add_ast_node(expr.hir_id.local_id, &[post_inputs])
403 hir::ExprKind::Closure(..) |
404 hir::ExprKind::Lit(..) |
405 hir::ExprKind::Path(_) => {
406 self.straightline(expr, pred, None::<hir::Expr>.iter())
411 fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
412 call_expr: &hir::Expr,
414 func_or_rcvr: &hir::Expr,
415 args: I) -> CFGIndex {
416 let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
417 let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
418 // FIXME(canndrew): This is_never should probably be an is_uninhabited.
419 if self.tables.expr_ty(call_expr).is_never() {
420 self.add_unreachable_node()
426 fn exprs<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
428 pred: CFGIndex) -> CFGIndex {
429 //! Constructs graph for `exprs` evaluated in order
430 exprs.fold(pred, |p, e| self.expr(e, p))
433 fn opt_expr(&mut self,
434 opt_expr: &Option<P<hir::Expr>>,
435 pred: CFGIndex) -> CFGIndex {
436 //! Constructs graph for `opt_expr` evaluated, if Some
437 opt_expr.iter().fold(pred, |p, e| self.expr(&e, p))
440 fn straightline<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
443 subexprs: I) -> CFGIndex {
444 //! Handles case of an expression that evaluates `subexprs` in order
446 let subexprs_exit = self.exprs(subexprs, pred);
447 self.add_ast_node(expr.hir_id.local_id, &[subexprs_exit])
450 fn match_(&mut self, id: hir::ItemLocalId, discr: &hir::Expr,
451 arms: &[hir::Arm], pred: CFGIndex) -> CFGIndex {
452 // The CFG for match expression is quite complex, so no ASCII
455 // The CFG generated below matches roughly what MIR contains.
456 // Each pattern and guard is visited in parallel, with
457 // arms containing multiple patterns generating multiple nodes
458 // for the same guard expression. The guard expressions chain
459 // into each other from top to bottom, with a specific
460 // exception to allow some additional valid programs
461 // (explained below). MIR differs slightly in that the
462 // pattern matching may continue after a guard but the visible
463 // behaviour should be the same.
465 // What is going on is explained in further comments.
467 // Visit the discriminant expression
468 let discr_exit = self.expr(discr, pred);
470 // Add a node for the exit of the match expression as a whole.
471 let expr_exit = self.add_ast_node(id, &[]);
473 // Keep track of the previous guard expressions
474 let mut prev_guards = Vec::new();
477 // Add an exit node for when we've visited all the
478 // patterns and the guard (if there is one) in the arm.
479 let arm_exit = self.add_dummy_node(&[]);
481 for pat in &arm.pats {
482 // Visit the pattern, coming from the discriminant exit
483 let mut pat_exit = self.pat(&pat, discr_exit);
485 // If there is a guard expression, handle it here
486 if let Some(ref guard) = arm.guard {
487 // Add a dummy node for the previous guard
488 // expression to target
489 let guard_start = self.add_dummy_node(&[pat_exit]);
490 // Visit the guard expression
491 let guard_exit = match guard {
492 hir::Guard::If(ref e) => self.expr(e, guard_start),
494 // #47295: We used to have very special case code
495 // here for when a pair of arms are both formed
496 // solely from constants, and if so, not add these
497 // edges. But this was not actually sound without
498 // other constraints that we stopped enforcing at
500 while let Some(prev) = prev_guards.pop() {
501 self.add_contained_edge(prev, guard_start);
504 // Push the guard onto the list of previous guards
505 prev_guards.push(guard_exit);
507 // Update the exit node for the pattern
508 pat_exit = guard_exit;
511 // Add an edge from the exit of this pattern to the
513 self.add_contained_edge(pat_exit, arm_exit);
516 // Visit the body of this arm
517 let body_exit = self.expr(&arm.body, arm_exit);
519 // Link the body to the exit of the expression
520 self.add_contained_edge(body_exit, expr_exit);
526 fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
527 self.add_node(CFGNodeData::Dummy, preds)
530 fn add_ast_node(&mut self, id: hir::ItemLocalId, preds: &[CFGIndex]) -> CFGIndex {
531 self.add_node(CFGNodeData::AST(id), preds)
534 fn add_unreachable_node(&mut self) -> CFGIndex {
535 self.add_node(CFGNodeData::Unreachable, &[])
538 fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
539 let node = self.graph.add_node(data);
541 self.add_contained_edge(pred, node);
546 fn add_contained_edge(&mut self,
549 let data = CFGEdgeData {exiting_scopes: vec![] };
550 self.graph.add_edge(source, target, data);
553 fn add_exiting_edge(&mut self,
554 from_expr: &hir::Expr,
555 from_index: CFGIndex,
556 target_scope: region::Scope,
557 to_index: CFGIndex) {
558 let mut data = CFGEdgeData { exiting_scopes: vec![] };
559 let mut scope = region::Scope {
560 id: from_expr.hir_id.local_id,
561 data: region::ScopeData::Node
563 let region_scope_tree = self.tcx.region_scope_tree(self.owner_def_id);
564 while scope != target_scope {
565 data.exiting_scopes.push(scope.item_local_id());
566 scope = region_scope_tree.encl_scope(scope);
568 self.graph.add_edge(from_index, to_index, data);
571 fn add_returning_edge(&mut self,
572 _from_expr: &hir::Expr,
573 from_index: CFGIndex) {
574 let data = CFGEdgeData {
575 exiting_scopes: self.loop_scopes.iter()
577 .map(|&LoopScope { loop_id: id, .. }| id)
580 self.graph.add_edge(from_index, self.fn_exit, data);
583 fn find_scope_edge(&self,
585 destination: hir::Destination,
586 scope_cf_kind: ScopeCfKind) -> (region::Scope, CFGIndex) {
588 match destination.target_id {
590 for b in &self.breakable_block_scopes {
591 if b.block_expr_id == self.tcx.hir().node_to_hir_id(loop_id).local_id {
592 let scope = region::Scope {
593 id: self.tcx.hir().node_to_hir_id(loop_id).local_id,
594 data: region::ScopeData::Node
596 return (scope, match scope_cf_kind {
597 ScopeCfKind::Break => b.break_index,
598 ScopeCfKind::Continue => bug!("can't continue to block"),
602 for l in &self.loop_scopes {
603 if l.loop_id == self.tcx.hir().node_to_hir_id(loop_id).local_id {
604 let scope = region::Scope {
605 id: self.tcx.hir().node_to_hir_id(loop_id).local_id,
606 data: region::ScopeData::Node
608 return (scope, match scope_cf_kind {
609 ScopeCfKind::Break => l.break_index,
610 ScopeCfKind::Continue => l.continue_index,
614 span_bug!(expr.span, "no scope for id {}", loop_id);
616 Err(err) => span_bug!(expr.span, "scope error: {}", err),
621 #[derive(Copy, Clone, Eq, PartialEq)]