2 use crate::middle::region;
3 use rustc_data_structures::graph::implementation as graph;
5 use crate::ty::{self, TyCtxt};
7 use crate::hir::{self, PatKind};
8 use crate::hir::def_id::DefId;
10 struct CFGBuilder<'a, 'tcx: 'a> {
11 tcx: TyCtxt<'a, 'tcx, 'tcx>,
13 tables: &'a ty::TypeckTables<'tcx>,
16 loop_scopes: Vec<LoopScope>,
17 breakable_block_scopes: Vec<BlockScope>,
20 #[derive(Copy, Clone)]
22 block_expr_id: hir::ItemLocalId, // id of breakable block expr node
23 break_index: CFGIndex, // where to go on `break`
26 #[derive(Copy, Clone)]
28 loop_id: hir::ItemLocalId, // id of loop/while node
29 continue_index: CFGIndex, // where to go on a `loop`
30 break_index: CFGIndex, // where to go on a `break`
33 pub fn construct<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
34 body: &hir::Body) -> CFG {
35 let mut graph = graph::Graph::new();
36 let entry = graph.add_node(CFGNodeData::Entry);
38 // `fn_exit` is target of return exprs, which lies somewhere
39 // outside input `body`. (Distinguishing `fn_exit` and `body_exit`
40 // also resolves chicken-and-egg problem that arises if you try to
41 // have return exprs jump to `body_exit` during construction.)
42 let fn_exit = graph.add_node(CFGNodeData::Exit);
45 // Find the tables for this body.
46 let owner_def_id = tcx.hir().local_def_id(tcx.hir().body_owner(body.id()));
47 let tables = tcx.typeck_tables_of(owner_def_id);
49 let mut cfg_builder = CFGBuilder {
55 loop_scopes: Vec::new(),
56 breakable_block_scopes: Vec::new(),
58 body_exit = cfg_builder.expr(&body.value, entry);
59 cfg_builder.add_contained_edge(body_exit, fn_exit);
60 let CFGBuilder { graph, .. } = cfg_builder;
69 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
70 fn block(&mut self, blk: &hir::Block, pred: CFGIndex) -> CFGIndex {
71 if blk.targeted_by_break {
72 let expr_exit = self.add_ast_node(blk.hir_id.local_id, &[]);
74 self.breakable_block_scopes.push(BlockScope {
75 block_expr_id: blk.hir_id.local_id,
76 break_index: expr_exit,
79 let mut stmts_exit = pred;
80 for stmt in &blk.stmts {
81 stmts_exit = self.stmt(stmt, stmts_exit);
83 let blk_expr_exit = self.opt_expr(&blk.expr, stmts_exit);
84 self.add_contained_edge(blk_expr_exit, expr_exit);
86 self.breakable_block_scopes.pop();
90 let mut stmts_exit = pred;
91 for stmt in &blk.stmts {
92 stmts_exit = self.stmt(stmt, stmts_exit);
95 let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
97 self.add_ast_node(blk.hir_id.local_id, &[expr_exit])
101 fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex {
102 let exit = match stmt.node {
103 hir::StmtKind::Local(ref local) => {
104 let init_exit = self.opt_expr(&local.init, pred);
105 self.pat(&local.pat, init_exit)
107 hir::StmtKind::Item(_) => {
110 hir::StmtKind::Expr(ref expr) |
111 hir::StmtKind::Semi(ref expr) => {
112 self.expr(&expr, pred)
115 self.add_ast_node(stmt.hir_id.local_id, &[exit])
118 fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex {
120 PatKind::Binding(.., None) |
124 PatKind::Wild => self.add_ast_node(pat.hir_id.local_id, &[pred]),
126 PatKind::Box(ref subpat) |
127 PatKind::Ref(ref subpat, _) |
128 PatKind::Binding(.., Some(ref subpat)) => {
129 let subpat_exit = self.pat(&subpat, pred);
130 self.add_ast_node(pat.hir_id.local_id, &[subpat_exit])
133 PatKind::TupleStruct(_, ref subpats, _) |
134 PatKind::Tuple(ref subpats, _) => {
135 let pats_exit = self.pats_all(subpats.iter(), pred);
136 self.add_ast_node(pat.hir_id.local_id, &[pats_exit])
139 PatKind::Struct(_, ref subpats, _) => {
140 let pats_exit = self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
141 self.add_ast_node(pat.hir_id.local_id, &[pats_exit])
144 PatKind::Slice(ref pre, ref vec, ref post) => {
145 let pre_exit = self.pats_all(pre.iter(), pred);
146 let vec_exit = self.pats_all(vec.iter(), pre_exit);
147 let post_exit = self.pats_all(post.iter(), vec_exit);
148 self.add_ast_node(pat.hir_id.local_id, &[post_exit])
153 fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>(
158 //! Handles case where all of the patterns must match.
159 pats.fold(pred, |pred, pat| self.pat(&pat, pred))
162 fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex {
164 hir::ExprKind::Block(ref blk, _) => {
165 let blk_exit = self.block(&blk, pred);
166 self.add_ast_node(expr.hir_id.local_id, &[blk_exit])
169 hir::ExprKind::While(ref cond, ref body, _) => {
184 // Note that `break` and `continue` statements
185 // may cause additional edges.
187 let loopback = self.add_dummy_node(&[pred]); // 1
189 // Create expr_exit without pred (cond_exit)
190 let expr_exit = self.add_ast_node(expr.hir_id.local_id, &[]); // 3
192 // The LoopScope needs to be on the loop_scopes stack while evaluating the
193 // condition and the body of the loop (both can break out of the loop)
194 self.loop_scopes.push(LoopScope {
195 loop_id: expr.hir_id.local_id,
196 continue_index: loopback,
197 break_index: expr_exit
200 let cond_exit = self.expr(&cond, loopback); // 2
202 // Add pred (cond_exit) to expr_exit
203 self.add_contained_edge(cond_exit, expr_exit);
205 let body_exit = self.block(&body, cond_exit); // 4
206 self.add_contained_edge(body_exit, loopback); // 5
207 self.loop_scopes.pop();
211 hir::ExprKind::Loop(ref body, _, _) => {
223 // Note that `break` and `loop` statements
224 // may cause additional edges.
226 let loopback = self.add_dummy_node(&[pred]); // 1
227 let expr_exit = self.add_ast_node(expr.hir_id.local_id, &[]); // 2
228 self.loop_scopes.push(LoopScope {
229 loop_id: expr.hir_id.local_id,
230 continue_index: loopback,
231 break_index: expr_exit,
233 let body_exit = self.block(&body, loopback); // 3
234 self.add_contained_edge(body_exit, loopback); // 4
235 self.loop_scopes.pop();
239 hir::ExprKind::Match(ref discr, ref arms, _) => {
240 self.match_(expr.hir_id.local_id, &discr, &arms, pred)
243 hir::ExprKind::Binary(op, ref l, ref r) if op.node.is_lazy() => {
258 let l_exit = self.expr(&l, pred); // 1
259 let r_exit = self.expr(&r, l_exit); // 2
260 self.add_ast_node(expr.hir_id.local_id, &[l_exit, r_exit]) // 3,4
263 hir::ExprKind::Ret(ref v) => {
264 let v_exit = self.opt_expr(v, pred);
265 let b = self.add_ast_node(expr.hir_id.local_id, &[v_exit]);
266 self.add_returning_edge(expr, b);
267 self.add_unreachable_node()
270 hir::ExprKind::Break(destination, ref opt_expr) => {
271 let v = self.opt_expr(opt_expr, pred);
272 let (target_scope, break_dest) =
273 self.find_scope_edge(expr, destination, ScopeCfKind::Break);
274 let b = self.add_ast_node(expr.hir_id.local_id, &[v]);
275 self.add_exiting_edge(expr, b, target_scope, break_dest);
276 self.add_unreachable_node()
279 hir::ExprKind::Continue(destination) => {
280 let (target_scope, cont_dest) =
281 self.find_scope_edge(expr, destination, ScopeCfKind::Continue);
282 let a = self.add_ast_node(expr.hir_id.local_id, &[pred]);
283 self.add_exiting_edge(expr, a, target_scope, cont_dest);
284 self.add_unreachable_node()
287 hir::ExprKind::Array(ref elems) => {
288 self.straightline(expr, pred, elems.iter().map(|e| &*e))
291 hir::ExprKind::Call(ref func, ref args) => {
292 self.call(expr, pred, &func, args.iter().map(|e| &*e))
295 hir::ExprKind::MethodCall(.., ref args) => {
296 self.call(expr, pred, &args[0], args[1..].iter().map(|e| &*e))
299 hir::ExprKind::Index(ref l, ref r) |
300 hir::ExprKind::Binary(_, ref l, ref r) if self.tables.is_method_call(expr) => {
301 self.call(expr, pred, &l, Some(&**r).into_iter())
304 hir::ExprKind::Unary(_, ref e) if self.tables.is_method_call(expr) => {
305 self.call(expr, pred, &e, None::<hir::Expr>.iter())
308 hir::ExprKind::Tup(ref exprs) => {
309 self.straightline(expr, pred, exprs.iter().map(|e| &*e))
312 hir::ExprKind::Struct(_, ref fields, ref base) => {
313 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
314 self.opt_expr(base, field_cfg)
317 hir::ExprKind::Assign(ref l, ref r) |
318 hir::ExprKind::AssignOp(_, ref l, ref r) => {
319 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
322 hir::ExprKind::Index(ref l, ref r) |
323 hir::ExprKind::Binary(_, ref l, ref r) => { // N.B., && and || handled earlier
324 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
327 hir::ExprKind::Box(ref e) |
328 hir::ExprKind::AddrOf(_, ref e) |
329 hir::ExprKind::Cast(ref e, _) |
330 hir::ExprKind::Type(ref e, _) |
331 hir::ExprKind::DropTemps(ref e) |
332 hir::ExprKind::Unary(_, ref e) |
333 hir::ExprKind::Field(ref e, _) |
334 hir::ExprKind::Yield(ref e) |
335 hir::ExprKind::Repeat(ref e, _) => {
336 self.straightline(expr, pred, Some(&**e).into_iter())
339 hir::ExprKind::InlineAsm(_, ref outputs, ref inputs) => {
340 let post_outputs = self.exprs(outputs.iter().map(|e| &*e), pred);
341 let post_inputs = self.exprs(inputs.iter().map(|e| &*e), post_outputs);
342 self.add_ast_node(expr.hir_id.local_id, &[post_inputs])
345 hir::ExprKind::Closure(..) |
346 hir::ExprKind::Lit(..) |
347 hir::ExprKind::Path(_) |
348 hir::ExprKind::Err => {
349 self.straightline(expr, pred, None::<hir::Expr>.iter())
354 fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
355 call_expr: &hir::Expr,
357 func_or_rcvr: &hir::Expr,
358 args: I) -> CFGIndex {
359 let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
360 let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
361 let m = self.tcx.hir().get_module_parent_by_hir_id(call_expr.hir_id);
362 if self.tcx.is_ty_uninhabited_from(m, self.tables.expr_ty(call_expr)) {
363 self.add_unreachable_node()
369 fn exprs<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
371 pred: CFGIndex) -> CFGIndex {
372 //! Constructs graph for `exprs` evaluated in order
373 exprs.fold(pred, |p, e| self.expr(e, p))
376 fn opt_expr(&mut self,
377 opt_expr: &Option<P<hir::Expr>>,
378 pred: CFGIndex) -> CFGIndex {
379 //! Constructs graph for `opt_expr` evaluated, if Some
380 opt_expr.iter().fold(pred, |p, e| self.expr(&e, p))
383 fn straightline<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
386 subexprs: I) -> CFGIndex {
387 //! Handles case of an expression that evaluates `subexprs` in order
389 let subexprs_exit = self.exprs(subexprs, pred);
390 self.add_ast_node(expr.hir_id.local_id, &[subexprs_exit])
393 fn match_(&mut self, id: hir::ItemLocalId, discr: &hir::Expr,
394 arms: &[hir::Arm], pred: CFGIndex) -> CFGIndex {
395 // The CFG for match expression is quite complex, so no ASCII
398 // The CFG generated below matches roughly what MIR contains.
399 // Each pattern and guard is visited in parallel, with
400 // arms containing multiple patterns generating multiple nodes
401 // for the same guard expression. The guard expressions chain
402 // into each other from top to bottom, with a specific
403 // exception to allow some additional valid programs
404 // (explained below). MIR differs slightly in that the
405 // pattern matching may continue after a guard but the visible
406 // behaviour should be the same.
408 // What is going on is explained in further comments.
410 // Visit the discriminant expression
411 let discr_exit = self.expr(discr, pred);
413 // Add a node for the exit of the match expression as a whole.
414 let expr_exit = self.add_ast_node(id, &[]);
416 // Keep track of the previous guard expressions
417 let mut prev_guards = Vec::new();
420 // Add an exit node for when we've visited all the
421 // patterns and the guard (if there is one) in the arm.
422 let bindings_exit = self.add_dummy_node(&[]);
424 for pat in &arm.pats {
425 // Visit the pattern, coming from the discriminant exit
426 let mut pat_exit = self.pat(&pat, discr_exit);
428 // If there is a guard expression, handle it here
429 if let Some(ref guard) = arm.guard {
430 // Add a dummy node for the previous guard
431 // expression to target
432 let guard_start = self.add_dummy_node(&[pat_exit]);
433 // Visit the guard expression
434 let guard_exit = match guard {
435 hir::Guard::If(ref e) => self.expr(e, guard_start),
437 // #47295: We used to have very special case code
438 // here for when a pair of arms are both formed
439 // solely from constants, and if so, not add these
440 // edges. But this was not actually sound without
441 // other constraints that we stopped enforcing at
443 while let Some(prev) = prev_guards.pop() {
444 self.add_contained_edge(prev, guard_start);
447 // Push the guard onto the list of previous guards
448 prev_guards.push(guard_exit);
450 // Update the exit node for the pattern
451 pat_exit = guard_exit;
454 // Add an edge from the exit of this pattern to the
456 self.add_contained_edge(pat_exit, bindings_exit);
459 // Visit the body of this arm
460 let body_exit = self.expr(&arm.body, bindings_exit);
462 let arm_exit = self.add_ast_node(arm.hir_id.local_id, &[body_exit]);
464 // Link the body to the exit of the expression
465 self.add_contained_edge(arm_exit, expr_exit);
471 fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
472 self.add_node(CFGNodeData::Dummy, preds)
475 fn add_ast_node(&mut self, id: hir::ItemLocalId, preds: &[CFGIndex]) -> CFGIndex {
476 self.add_node(CFGNodeData::AST(id), preds)
479 fn add_unreachable_node(&mut self) -> CFGIndex {
480 self.add_node(CFGNodeData::Unreachable, &[])
483 fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
484 let node = self.graph.add_node(data);
486 self.add_contained_edge(pred, node);
491 fn add_contained_edge(&mut self,
494 let data = CFGEdgeData {exiting_scopes: vec![] };
495 self.graph.add_edge(source, target, data);
498 fn add_exiting_edge(&mut self,
499 from_expr: &hir::Expr,
500 from_index: CFGIndex,
501 target_scope: region::Scope,
502 to_index: CFGIndex) {
503 let mut data = CFGEdgeData { exiting_scopes: vec![] };
504 let mut scope = region::Scope {
505 id: from_expr.hir_id.local_id,
506 data: region::ScopeData::Node
508 let region_scope_tree = self.tcx.region_scope_tree(self.owner_def_id);
509 while scope != target_scope {
510 data.exiting_scopes.push(scope.item_local_id());
511 scope = region_scope_tree.encl_scope(scope);
513 self.graph.add_edge(from_index, to_index, data);
516 fn add_returning_edge(&mut self,
517 _from_expr: &hir::Expr,
518 from_index: CFGIndex) {
519 let data = CFGEdgeData {
520 exiting_scopes: self.loop_scopes.iter()
522 .map(|&LoopScope { loop_id: id, .. }| id)
525 self.graph.add_edge(from_index, self.fn_exit, data);
528 fn find_scope_edge(&self,
530 destination: hir::Destination,
531 scope_cf_kind: ScopeCfKind) -> (region::Scope, CFGIndex) {
533 match destination.target_id {
535 for b in &self.breakable_block_scopes {
536 if b.block_expr_id == loop_id.local_id {
537 let scope = region::Scope {
538 id: loop_id.local_id,
539 data: region::ScopeData::Node
541 return (scope, match scope_cf_kind {
542 ScopeCfKind::Break => b.break_index,
543 ScopeCfKind::Continue => bug!("can't continue to block"),
547 for l in &self.loop_scopes {
548 if l.loop_id == loop_id.local_id {
549 let scope = region::Scope {
550 id: loop_id.local_id,
551 data: region::ScopeData::Node
553 return (scope, match scope_cf_kind {
554 ScopeCfKind::Break => l.break_index,
555 ScopeCfKind::Continue => l.continue_index,
559 span_bug!(expr.span, "no scope for id {}", loop_id);
561 Err(err) => span_bug!(expr.span, "scope error: {}", err),
566 #[derive(Copy, Clone, Eq, PartialEq)]