src/librustc/cfg/construct.rs

   1 use crate::cfg::*;
   2 use crate::middle::region;
   3 use rustc_data_structures::graph::implementation as graph;
   4 use crate::ty::{self, TyCtxt};
   5
   6 use crate::hir::{self, PatKind};
   7 use crate::hir::def_id::DefId;
   8 use crate::hir::ptr::P;
   9
  10 struct CFGBuilder<'a, 'tcx> {
  11     tcx: TyCtxt<'tcx>,
  12     owner_def_id: DefId,
  13     tables: &'a ty::TypeckTables<'tcx>,
  14     graph: CFGGraph,
  15     fn_exit: CFGIndex,
  16     loop_scopes: Vec<LoopScope>,
  17     breakable_block_scopes: Vec<BlockScope>,
  18 }
  19
  20 #[derive(Copy, Clone)]
  21 struct BlockScope {
  22     block_expr_id: hir::ItemLocalId, // id of breakable block expr node
  23     break_index: CFGIndex, // where to go on `break`
  24 }
  25
  26 #[derive(Copy, Clone)]
  27 struct LoopScope {
  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`
  31 }
  32
  33 pub fn construct(tcx: TyCtxt<'_>, body: &hir::Body) -> CFG {
  34     let mut graph = graph::Graph::new();
  35     let entry = graph.add_node(CFGNodeData::Entry);
  36
  37     // `fn_exit` is target of return exprs, which lies somewhere
  38     // outside input `body`. (Distinguishing `fn_exit` and `body_exit`
  39     // also resolves chicken-and-egg problem that arises if you try to
  40     // have return exprs jump to `body_exit` during construction.)
  41     let fn_exit = graph.add_node(CFGNodeData::Exit);
  42     let body_exit;
  43
  44     // Find the tables for this body.
  45     let owner_def_id = tcx.hir().body_owner_def_id(body.id());
  46     let tables = tcx.typeck_tables_of(owner_def_id);
  47
  48     let mut cfg_builder = CFGBuilder {
  49         tcx,
  50         owner_def_id,
  51         tables,
  52         graph,
  53         fn_exit,
  54         loop_scopes: Vec::new(),
  55         breakable_block_scopes: Vec::new(),
  56     };
  57     body_exit = cfg_builder.expr(&body.value, entry);
  58     cfg_builder.add_contained_edge(body_exit, fn_exit);
  59     let CFGBuilder { graph, .. } = cfg_builder;
  60     CFG {
  61         owner_def_id,
  62         graph,
  63         entry,
  64         exit: fn_exit,
  65     }
  66 }
  67
  68 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
  69     fn block(&mut self, blk: &hir::Block, pred: CFGIndex) -> CFGIndex {
  70         if blk.targeted_by_break {
  71             let expr_exit = self.add_ast_node(blk.hir_id.local_id, &[]);
  72
  73             self.breakable_block_scopes.push(BlockScope {
  74                 block_expr_id: blk.hir_id.local_id,
  75                 break_index: expr_exit,
  76             });
  77
  78             let mut stmts_exit = pred;
  79             for stmt in &blk.stmts {
  80                 stmts_exit = self.stmt(stmt, stmts_exit);
  81             }
  82             let blk_expr_exit = self.opt_expr(&blk.expr, stmts_exit);
  83             self.add_contained_edge(blk_expr_exit, expr_exit);
  84
  85             self.breakable_block_scopes.pop();
  86
  87             expr_exit
  88         } else {
  89             let mut stmts_exit = pred;
  90             for stmt in &blk.stmts {
  91                 stmts_exit = self.stmt(stmt, stmts_exit);
  92             }
  93
  94             let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
  95
  96             self.add_ast_node(blk.hir_id.local_id, &[expr_exit])
  97         }
  98     }
  99
 100     fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex {
 101         let exit = match stmt.node {
 102             hir::StmtKind::Local(ref local) => {
 103                 let init_exit = self.opt_expr(&local.init, pred);
 104                 self.pat(&local.pat, init_exit)
 105             }
 106             hir::StmtKind::Item(_) => {
 107                 pred
 108             }
 109             hir::StmtKind::Expr(ref expr) |
 110             hir::StmtKind::Semi(ref expr) => {
 111                 self.expr(&expr, pred)
 112             }
 113         };
 114         self.add_ast_node(stmt.hir_id.local_id, &[exit])
 115     }
 116
 117     fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex {
 118         match pat.node {
 119             PatKind::Binding(.., None) |
 120             PatKind::Path(_) |
 121             PatKind::Lit(..) |
 122             PatKind::Range(..) |
 123             PatKind::Wild => self.add_ast_node(pat.hir_id.local_id, &[pred]),
 124
 125             PatKind::Box(ref subpat) |
 126             PatKind::Ref(ref subpat, _) |
 127             PatKind::Binding(.., Some(ref subpat)) => {
 128                 let subpat_exit = self.pat(&subpat, pred);
 129                 self.add_ast_node(pat.hir_id.local_id, &[subpat_exit])
 130             }
 131
 132             PatKind::TupleStruct(_, ref subpats, _) |
 133             PatKind::Tuple(ref subpats, _) => {
 134                 let pats_exit = self.pats_all(subpats.iter(), pred);
 135                 self.add_ast_node(pat.hir_id.local_id, &[pats_exit])
 136             }
 137
 138             PatKind::Struct(_, ref subpats, _) => {
 139                 let pats_exit = self.pats_all(subpats.iter().map(|f| &f.pat), pred);
 140                 self.add_ast_node(pat.hir_id.local_id, &[pats_exit])
 141             }
 142
 143             PatKind::Or(ref pats) => {
 144                 let branches: Vec<_> = pats.iter().map(|p| self.pat(p, pred)).collect();
 145                 self.add_ast_node(pat.hir_id.local_id, &branches)
 146             }
 147
 148             PatKind::Slice(ref pre, ref vec, ref post) => {
 149                 let pre_exit = self.pats_all(pre.iter(), pred);
 150                 let vec_exit = self.pats_all(vec.iter(), pre_exit);
 151                 let post_exit = self.pats_all(post.iter(), vec_exit);
 152                 self.add_ast_node(pat.hir_id.local_id, &[post_exit])
 153             }
 154         }
 155     }
 156
 157     fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>(
 158         &mut self,
 159         pats: I,
 160         pred: CFGIndex
 161     ) -> CFGIndex {
 162         //! Handles case where all of the patterns must match.
 163         pats.fold(pred, |pred, pat| self.pat(&pat, pred))
 164     }
 165
 166     fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex {
 167         match expr.node {
 168             hir::ExprKind::Block(ref blk, _) => {
 169                 let blk_exit = self.block(&blk, pred);
 170                 self.add_ast_node(expr.hir_id.local_id, &[blk_exit])
 171             }
 172
 173             hir::ExprKind::Loop(ref body, _, _) => {
 174                 //
 175                 //     [pred]
 176                 //       |
 177                 //       v 1
 178                 //   [loopback] <---+
 179                 //       |      4   |
 180                 //       v 3        |
 181                 //     [body] ------+
 182                 //
 183                 //     [expr] 2
 184                 //
 185                 // Note that `break` and `loop` statements
 186                 // may cause additional edges.
 187
 188                 let loopback = self.add_dummy_node(&[pred]);              // 1
 189                 let expr_exit = self.add_ast_node(expr.hir_id.local_id, &[]);          // 2
 190                 self.loop_scopes.push(LoopScope {
 191                     loop_id: expr.hir_id.local_id,
 192                     continue_index: loopback,
 193                     break_index: expr_exit,
 194                 });
 195                 let body_exit = self.block(&body, loopback);           // 3
 196                 self.add_contained_edge(body_exit, loopback);            // 4
 197                 self.loop_scopes.pop();
 198                 expr_exit
 199             }
 200
 201             hir::ExprKind::Match(ref discr, ref arms, _) => {
 202                 self.match_(expr.hir_id.local_id, &discr, &arms, pred)
 203             }
 204
 205             hir::ExprKind::Binary(op, ref l, ref r) if op.node.is_lazy() => {
 206                 //
 207                 //     [pred]
 208                 //       |
 209                 //       v 1
 210                 //      [l]
 211                 //       |
 212                 //      / \
 213                 //     /   \
 214                 //    v 2  *
 215                 //   [r]   |
 216                 //    |    |
 217                 //    v 3  v 4
 218                 //   [..exit..]
 219                 //
 220                 let l_exit = self.expr(&l, pred);                      // 1
 221                 let r_exit = self.expr(&r, l_exit);                    // 2
 222                 self.add_ast_node(expr.hir_id.local_id, &[l_exit, r_exit])            // 3,4
 223             }
 224
 225             hir::ExprKind::Ret(ref v) => {
 226                 let v_exit = self.opt_expr(v, pred);
 227                 let b = self.add_ast_node(expr.hir_id.local_id, &[v_exit]);
 228                 self.add_returning_edge(expr, b);
 229                 self.add_unreachable_node()
 230             }
 231
 232             hir::ExprKind::Break(destination, ref opt_expr) => {
 233                 let v = self.opt_expr(opt_expr, pred);
 234                 let (target_scope, break_dest) =
 235                     self.find_scope_edge(expr, destination, ScopeCfKind::Break);
 236                 let b = self.add_ast_node(expr.hir_id.local_id, &[v]);
 237                 self.add_exiting_edge(expr, b, target_scope, break_dest);
 238                 self.add_unreachable_node()
 239             }
 240
 241             hir::ExprKind::Continue(destination) => {
 242                 let (target_scope, cont_dest) =
 243                     self.find_scope_edge(expr, destination, ScopeCfKind::Continue);
 244                 let a = self.add_ast_node(expr.hir_id.local_id, &[pred]);
 245                 self.add_exiting_edge(expr, a, target_scope, cont_dest);
 246                 self.add_unreachable_node()
 247             }
 248
 249             hir::ExprKind::Array(ref elems) => {
 250                 self.straightline(expr, pred, elems.iter().map(|e| &*e))
 251             }
 252
 253             hir::ExprKind::Call(ref func, ref args) => {
 254                 self.call(expr, pred, &func, args.iter().map(|e| &*e))
 255             }
 256
 257             hir::ExprKind::MethodCall(.., ref args) => {
 258                 self.call(expr, pred, &args[0], args[1..].iter().map(|e| &*e))
 259             }
 260
 261             hir::ExprKind::Index(ref l, ref r) |
 262             hir::ExprKind::Binary(_, ref l, ref r) if self.tables.is_method_call(expr) => {
 263                 self.call(expr, pred, &l, Some(&**r).into_iter())
 264             }
 265
 266             hir::ExprKind::Unary(_, ref e) if self.tables.is_method_call(expr) => {
 267                 self.call(expr, pred, &e, None::<hir::Expr>.iter())
 268             }
 269
 270             hir::ExprKind::Tup(ref exprs) => {
 271                 self.straightline(expr, pred, exprs.iter().map(|e| &*e))
 272             }
 273
 274             hir::ExprKind::Struct(_, ref fields, ref base) => {
 275                 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
 276                 self.opt_expr(base, field_cfg)
 277             }
 278
 279             hir::ExprKind::Assign(ref l, ref r) |
 280             hir::ExprKind::AssignOp(_, ref l, ref r) => {
 281                 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
 282             }
 283
 284             hir::ExprKind::Index(ref l, ref r) |
 285             hir::ExprKind::Binary(_, ref l, ref r) => { // N.B., && and || handled earlier
 286                 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
 287             }
 288
 289             hir::ExprKind::Box(ref e) |
 290             hir::ExprKind::AddrOf(_, ref e) |
 291             hir::ExprKind::Cast(ref e, _) |
 292             hir::ExprKind::Type(ref e, _) |
 293             hir::ExprKind::DropTemps(ref e) |
 294             hir::ExprKind::Unary(_, ref e) |
 295             hir::ExprKind::Field(ref e, _) |
 296             hir::ExprKind::Yield(ref e, _) |
 297             hir::ExprKind::Repeat(ref e, _) => {
 298                 self.straightline(expr, pred, Some(&**e).into_iter())
 299             }
 300
 301             hir::ExprKind::InlineAsm(_, ref outputs, ref inputs) => {
 302                 let post_outputs = self.exprs(outputs.iter().map(|e| &*e), pred);
 303                 let post_inputs = self.exprs(inputs.iter().map(|e| &*e), post_outputs);
 304                 self.add_ast_node(expr.hir_id.local_id, &[post_inputs])
 305             }
 306
 307             hir::ExprKind::Closure(..) |
 308             hir::ExprKind::Lit(..) |
 309             hir::ExprKind::Path(_) |
 310             hir::ExprKind::Err => {
 311                 self.straightline(expr, pred, None::<hir::Expr>.iter())
 312             }
 313         }
 314     }
 315
 316     fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
 317             call_expr: &hir::Expr,
 318             pred: CFGIndex,
 319             func_or_rcvr: &hir::Expr,
 320             args: I) -> CFGIndex {
 321         let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
 322         let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
 323         let m = self.tcx.hir().get_module_parent(call_expr.hir_id);
 324         if self.tcx.is_ty_uninhabited_from(m, self.tables.expr_ty(call_expr)) {
 325             self.add_unreachable_node()
 326         } else {
 327             ret
 328         }
 329     }
 330
 331     fn exprs<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
 332                                              exprs: I,
 333                                              pred: CFGIndex) -> CFGIndex {
 334         //! Constructs graph for `exprs` evaluated in order
 335         exprs.fold(pred, |p, e| self.expr(e, p))
 336     }
 337
 338     fn opt_expr(&mut self,
 339                 opt_expr: &Option<P<hir::Expr>>,
 340                 pred: CFGIndex) -> CFGIndex {
 341         //! Constructs graph for `opt_expr` evaluated, if Some
 342         opt_expr.iter().fold(pred, |p, e| self.expr(&e, p))
 343     }
 344
 345     fn straightline<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
 346                     expr: &hir::Expr,
 347                     pred: CFGIndex,
 348                     subexprs: I) -> CFGIndex {
 349         //! Handles case of an expression that evaluates `subexprs` in order
 350
 351         let subexprs_exit = self.exprs(subexprs, pred);
 352         self.add_ast_node(expr.hir_id.local_id, &[subexprs_exit])
 353     }
 354
 355     fn match_(&mut self, id: hir::ItemLocalId, discr: &hir::Expr,
 356               arms: &[hir::Arm], pred: CFGIndex) -> CFGIndex {
 357         // The CFG for match expression is quite complex, so no ASCII
 358         // art for it (yet).
 359         //
 360         // The CFG generated below matches roughly what MIR contains.
 361         // Each pattern and guard is visited in parallel, with
 362         // arms containing multiple patterns generating multiple nodes
 363         // for the same guard expression. The guard expressions chain
 364         // into each other from top to bottom, with a specific
 365         // exception to allow some additional valid programs
 366         // (explained below). MIR differs slightly in that the
 367         // pattern matching may continue after a guard but the visible
 368         // behaviour should be the same.
 369         //
 370         // What is going on is explained in further comments.
 371
 372         // Visit the discriminant expression
 373         let discr_exit = self.expr(discr, pred);
 374
 375         // Add a node for the exit of the match expression as a whole.
 376         let expr_exit = self.add_ast_node(id, &[]);
 377
 378         // Keep track of the previous guard expressions
 379         let mut prev_guard = None;
 380         let match_scope = region::Scope { id, data: region::ScopeData::Node };
 381
 382         for arm in arms {
 383             // Add an exit node for when we've visited all the
 384             // patterns and the guard (if there is one) in the arm.
 385             let bindings_exit = self.add_dummy_node(&[]);
 386
 387             for pat in &arm.pats {
 388                 // Visit the pattern, coming from the discriminant exit
 389                 let mut pat_exit = self.pat(&pat, discr_exit);
 390
 391                 // If there is a guard expression, handle it here
 392                 if let Some(ref guard) = arm.guard {
 393                     // Add a dummy node for the previous guard
 394                     // expression to target
 395                     let guard_start = self.add_dummy_node(&[pat_exit]);
 396                     // Visit the guard expression
 397                     let guard_exit = match guard {
 398                         hir::Guard::If(ref e) => (&**e, self.expr(e, guard_start)),
 399                     };
 400                     // #47295: We used to have very special case code
 401                     // here for when a pair of arms are both formed
 402                     // solely from constants, and if so, not add these
 403                     // edges.  But this was not actually sound without
 404                     // other constraints that we stopped enforcing at
 405                     // some point.
 406                     if let Some((prev_guard, prev_index)) = prev_guard.take() {
 407                         self.add_exiting_edge(prev_guard, prev_index, match_scope, guard_start);
 408                     }
 409
 410                     // Push the guard onto the list of previous guards
 411                     prev_guard = Some(guard_exit);
 412
 413                     // Update the exit node for the pattern
 414                     pat_exit = guard_exit.1;
 415                 }
 416
 417                 // Add an edge from the exit of this pattern to the
 418                 // exit of the arm
 419                 self.add_contained_edge(pat_exit, bindings_exit);
 420             }
 421
 422             // Visit the body of this arm
 423             let body_exit = self.expr(&arm.body, bindings_exit);
 424
 425             let arm_exit = self.add_ast_node(arm.hir_id.local_id, &[body_exit]);
 426
 427             // Link the body to the exit of the expression
 428             self.add_contained_edge(arm_exit, expr_exit);
 429         }
 430
 431         expr_exit
 432     }
 433
 434     fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
 435         self.add_node(CFGNodeData::Dummy, preds)
 436     }
 437
 438     fn add_ast_node(&mut self, id: hir::ItemLocalId, preds: &[CFGIndex]) -> CFGIndex {
 439         self.add_node(CFGNodeData::AST(id), preds)
 440     }
 441
 442     fn add_unreachable_node(&mut self) -> CFGIndex {
 443         self.add_node(CFGNodeData::Unreachable, &[])
 444     }
 445
 446     fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
 447         let node = self.graph.add_node(data);
 448         for &pred in preds {
 449             self.add_contained_edge(pred, node);
 450         }
 451         node
 452     }
 453
 454     fn add_contained_edge(&mut self,
 455                           source: CFGIndex,
 456                           target: CFGIndex) {
 457         let data = CFGEdgeData {exiting_scopes: vec![] };
 458         self.graph.add_edge(source, target, data);
 459     }
 460
 461     fn add_exiting_edge(&mut self,
 462                         from_expr: &hir::Expr,
 463                         from_index: CFGIndex,
 464                         target_scope: region::Scope,
 465                         to_index: CFGIndex) {
 466         let mut data = CFGEdgeData { exiting_scopes: vec![] };
 467         let mut scope = region::Scope {
 468             id: from_expr.hir_id.local_id,
 469             data: region::ScopeData::Node
 470         };
 471         let region_scope_tree = self.tcx.region_scope_tree(self.owner_def_id);
 472         while scope != target_scope {
 473             data.exiting_scopes.push(scope.item_local_id());
 474             scope = region_scope_tree.encl_scope(scope);
 475         }
 476         self.graph.add_edge(from_index, to_index, data);
 477     }
 478
 479     fn add_returning_edge(&mut self,
 480                           _from_expr: &hir::Expr,
 481                           from_index: CFGIndex) {
 482         let data = CFGEdgeData {
 483             exiting_scopes: self.loop_scopes.iter()
 484                                             .rev()
 485                                             .map(|&LoopScope { loop_id: id, .. }| id)
 486                                             .collect()
 487         };
 488         self.graph.add_edge(from_index, self.fn_exit, data);
 489     }
 490
 491     fn find_scope_edge(&self,
 492                   expr: &hir::Expr,
 493                   destination: hir::Destination,
 494                   scope_cf_kind: ScopeCfKind) -> (region::Scope, CFGIndex) {
 495
 496         match destination.target_id {
 497             Ok(loop_id) => {
 498                 for b in &self.breakable_block_scopes {
 499                     if b.block_expr_id == loop_id.local_id {
 500                         let scope = region::Scope {
 501                             id: loop_id.local_id,
 502                             data: region::ScopeData::Node
 503                         };
 504                         return (scope, match scope_cf_kind {
 505                             ScopeCfKind::Break => b.break_index,
 506                             ScopeCfKind::Continue => bug!("can't continue to block"),
 507                         });
 508                     }
 509                 }
 510                 for l in &self.loop_scopes {
 511                     if l.loop_id == loop_id.local_id {
 512                         let scope = region::Scope {
 513                             id: loop_id.local_id,
 514                             data: region::ScopeData::Node
 515                         };
 516                         return (scope, match scope_cf_kind {
 517                             ScopeCfKind::Break => l.break_index,
 518                             ScopeCfKind::Continue => l.continue_index,
 519                         });
 520                     }
 521                 }
 522                 span_bug!(expr.span, "no scope for id {}", loop_id);
 523             }
 524             Err(err) => span_bug!(expr.span, "scope error: {}",  err),
 525         }
 526     }
 527 }
 528
 529 #[derive(Copy, Clone, Eq, PartialEq)]
 530 enum ScopeCfKind {
 531     Break,
 532     Continue,
 533 }