src/librustc/cfg/construct.rs

   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.
   4 //
   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.
  10
  11 use rustc_data_structures::graph;
  12 use cfg::*;
  13 use hir::def::Def;
  14 use hir::pat_util;
  15 use ty::{self, TyCtxt};
  16 use syntax::ast;
  17 use syntax::ptr::P;
  18
  19 use hir::{self, PatKind};
  20
  21 struct CFGBuilder<'a, 'tcx: 'a> {
  22     tcx: TyCtxt<'a, 'tcx, 'tcx>,
  23     graph: CFGGraph,
  24     fn_exit: CFGIndex,
  25     loop_scopes: Vec<LoopScope>,
  26 }
  27
  28 #[derive(Copy, Clone)]
  29 struct LoopScope {
  30     loop_id: ast::NodeId,     // id of loop/while node
  31     continue_index: CFGIndex, // where to go on a `loop`
  32     break_index: CFGIndex,    // where to go on a `break
  33 }
  34
  35 pub fn construct<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
  36                            blk: &hir::Block) -> CFG {
  37     let mut graph = graph::Graph::new();
  38     let entry = graph.add_node(CFGNodeData::Entry);
  39
  40     // `fn_exit` is target of return exprs, which lies somewhere
  41     // outside input `blk`. (Distinguishing `fn_exit` and `block_exit`
  42     // also resolves chicken-and-egg problem that arises if you try to
  43     // have return exprs jump to `block_exit` during construction.)
  44     let fn_exit = graph.add_node(CFGNodeData::Exit);
  45     let block_exit;
  46
  47     let mut cfg_builder = CFGBuilder {
  48         graph: graph,
  49         fn_exit: fn_exit,
  50         tcx: tcx,
  51         loop_scopes: Vec::new()
  52     };
  53     block_exit = cfg_builder.block(blk, entry);
  54     cfg_builder.add_contained_edge(block_exit, fn_exit);
  55     let CFGBuilder {graph, ..} = cfg_builder;
  56     CFG {graph: graph,
  57          entry: entry,
  58          exit: fn_exit}
  59 }
  60
  61 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
  62     fn block(&mut self, blk: &hir::Block, pred: CFGIndex) -> CFGIndex {
  63         let mut stmts_exit = pred;
  64         for stmt in &blk.stmts {
  65             stmts_exit = self.stmt(stmt, stmts_exit);
  66         }
  67
  68         let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
  69
  70         self.add_ast_node(blk.id, &[expr_exit])
  71     }
  72
  73     fn stmt(&mut self, stmt: &hir::Stmt, pred: CFGIndex) -> CFGIndex {
  74         match stmt.node {
  75             hir::StmtDecl(ref decl, id) => {
  76                 let exit = self.decl(&decl, pred);
  77                 self.add_ast_node(id, &[exit])
  78             }
  79
  80             hir::StmtExpr(ref expr, id) | hir::StmtSemi(ref expr, id) => {
  81                 let exit = self.expr(&expr, pred);
  82                 self.add_ast_node(id, &[exit])
  83             }
  84         }
  85     }
  86
  87     fn decl(&mut self, decl: &hir::Decl, pred: CFGIndex) -> CFGIndex {
  88         match decl.node {
  89             hir::DeclLocal(ref local) => {
  90                 let init_exit = self.opt_expr(&local.init, pred);
  91                 self.pat(&local.pat, init_exit)
  92             }
  93
  94             hir::DeclItem(_) => {
  95                 pred
  96             }
  97         }
  98     }
  99
 100     fn pat(&mut self, pat: &hir::Pat, pred: CFGIndex) -> CFGIndex {
 101         match pat.node {
 102             PatKind::Binding(.., None) |
 103             PatKind::Path(..) |
 104             PatKind::Lit(..) |
 105             PatKind::Range(..) |
 106             PatKind::Wild => {
 107                 self.add_ast_node(pat.id, &[pred])
 108             }
 109
 110             PatKind::Box(ref subpat) |
 111             PatKind::Ref(ref subpat, _) |
 112             PatKind::Binding(.., Some(ref subpat)) => {
 113                 let subpat_exit = self.pat(&subpat, pred);
 114                 self.add_ast_node(pat.id, &[subpat_exit])
 115             }
 116
 117             PatKind::TupleStruct(_, ref subpats, _) |
 118             PatKind::Tuple(ref subpats, _) => {
 119                 let pats_exit = self.pats_all(subpats.iter(), pred);
 120                 self.add_ast_node(pat.id, &[pats_exit])
 121             }
 122
 123             PatKind::Struct(_, ref subpats, _) => {
 124                 let pats_exit =
 125                     self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
 126                 self.add_ast_node(pat.id, &[pats_exit])
 127             }
 128
 129             PatKind::Slice(ref pre, ref vec, ref post) => {
 130                 let pre_exit = self.pats_all(pre.iter(), pred);
 131                 let vec_exit = self.pats_all(vec.iter(), pre_exit);
 132                 let post_exit = self.pats_all(post.iter(), vec_exit);
 133                 self.add_ast_node(pat.id, &[post_exit])
 134             }
 135         }
 136     }
 137
 138     fn pats_all<'b, I: Iterator<Item=&'b P<hir::Pat>>>(&mut self,
 139                                           pats: I,
 140                                           pred: CFGIndex) -> CFGIndex {
 141         //! Handles case where all of the patterns must match.
 142         pats.fold(pred, |pred, pat| self.pat(&pat, pred))
 143     }
 144
 145     fn expr(&mut self, expr: &hir::Expr, pred: CFGIndex) -> CFGIndex {
 146         match expr.node {
 147             hir::ExprBlock(ref blk) => {
 148                 let blk_exit = self.block(&blk, pred);
 149                 self.add_ast_node(expr.id, &[blk_exit])
 150             }
 151
 152             hir::ExprIf(ref cond, ref then, None) => {
 153                 //
 154                 //     [pred]
 155                 //       |
 156                 //       v 1
 157                 //     [cond]
 158                 //       |
 159                 //      / \
 160                 //     /   \
 161                 //    v 2   *
 162                 //  [then]  |
 163                 //    |     |
 164                 //    v 3   v 4
 165                 //   [..expr..]
 166                 //
 167                 let cond_exit = self.expr(&cond, pred);                // 1
 168                 let then_exit = self.block(&then, cond_exit);          // 2
 169                 self.add_ast_node(expr.id, &[cond_exit, then_exit])      // 3,4
 170             }
 171
 172             hir::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
 173                 //
 174                 //     [pred]
 175                 //       |
 176                 //       v 1
 177                 //     [cond]
 178                 //       |
 179                 //      / \
 180                 //     /   \
 181                 //    v 2   v 3
 182                 //  [then][otherwise]
 183                 //    |     |
 184                 //    v 4   v 5
 185                 //   [..expr..]
 186                 //
 187                 let cond_exit = self.expr(&cond, pred);                // 1
 188                 let then_exit = self.block(&then, cond_exit);          // 2
 189                 let else_exit = self.expr(&otherwise, cond_exit);      // 3
 190                 self.add_ast_node(expr.id, &[then_exit, else_exit])      // 4, 5
 191             }
 192
 193             hir::ExprWhile(ref cond, ref body, _) => {
 194                 //
 195                 //         [pred]
 196                 //           |
 197                 //           v 1
 198                 //       [loopback] <--+ 5
 199                 //           |         |
 200                 //           v 2       |
 201                 //   +-----[cond]      |
 202                 //   |       |         |
 203                 //   |       v 4       |
 204                 //   |     [body] -----+
 205                 //   v 3
 206                 // [expr]
 207                 //
 208                 // Note that `break` and `continue` statements
 209                 // may cause additional edges.
 210
 211                 // Is the condition considered part of the loop?
 212                 let loopback = self.add_dummy_node(&[pred]);              // 1
 213                 let cond_exit = self.expr(&cond, loopback);             // 2
 214                 let expr_exit = self.add_ast_node(expr.id, &[cond_exit]); // 3
 215                 self.loop_scopes.push(LoopScope {
 216                     loop_id: expr.id,
 217                     continue_index: loopback,
 218                     break_index: expr_exit
 219                 });
 220                 let body_exit = self.block(&body, cond_exit);          // 4
 221                 self.add_contained_edge(body_exit, loopback);            // 5
 222                 self.loop_scopes.pop();
 223                 expr_exit
 224             }
 225
 226             hir::ExprLoop(ref body, _) => {
 227                 //
 228                 //     [pred]
 229                 //       |
 230                 //       v 1
 231                 //   [loopback] <---+
 232                 //       |      4   |
 233                 //       v 3        |
 234                 //     [body] ------+
 235                 //
 236                 //     [expr] 2
 237                 //
 238                 // Note that `break` and `loop` statements
 239                 // may cause additional edges.
 240
 241                 let loopback = self.add_dummy_node(&[pred]);              // 1
 242                 let expr_exit = self.add_ast_node(expr.id, &[]);          // 2
 243                 self.loop_scopes.push(LoopScope {
 244                     loop_id: expr.id,
 245                     continue_index: loopback,
 246                     break_index: expr_exit,
 247                 });
 248                 let body_exit = self.block(&body, loopback);           // 3
 249                 self.add_contained_edge(body_exit, loopback);            // 4
 250                 self.loop_scopes.pop();
 251                 expr_exit
 252             }
 253
 254             hir::ExprMatch(ref discr, ref arms, _) => {
 255                 self.match_(expr.id, &discr, &arms, pred)
 256             }
 257
 258             hir::ExprBinary(op, ref l, ref r) if op.node.is_lazy() => {
 259                 //
 260                 //     [pred]
 261                 //       |
 262                 //       v 1
 263                 //      [l]
 264                 //       |
 265                 //      / \
 266                 //     /   \
 267                 //    v 2  *
 268                 //   [r]   |
 269                 //    |    |
 270                 //    v 3  v 4
 271                 //   [..exit..]
 272                 //
 273                 let l_exit = self.expr(&l, pred);                      // 1
 274                 let r_exit = self.expr(&r, l_exit);                    // 2
 275                 self.add_ast_node(expr.id, &[l_exit, r_exit])            // 3,4
 276             }
 277
 278             hir::ExprRet(ref v) => {
 279                 let v_exit = self.opt_expr(v, pred);
 280                 let b = self.add_ast_node(expr.id, &[v_exit]);
 281                 self.add_returning_edge(expr, b);
 282                 self.add_unreachable_node()
 283             }
 284
 285             hir::ExprBreak(label) => {
 286                 let loop_scope = self.find_scope(expr, label.map(|l| l.node));
 287                 let b = self.add_ast_node(expr.id, &[pred]);
 288                 self.add_exiting_edge(expr, b,
 289                                       loop_scope, loop_scope.break_index);
 290                 self.add_unreachable_node()
 291             }
 292
 293             hir::ExprAgain(label) => {
 294                 let loop_scope = self.find_scope(expr, label.map(|l| l.node));
 295                 let a = self.add_ast_node(expr.id, &[pred]);
 296                 self.add_exiting_edge(expr, a,
 297                                       loop_scope, loop_scope.continue_index);
 298                 self.add_unreachable_node()
 299             }
 300
 301             hir::ExprArray(ref elems) => {
 302                 self.straightline(expr, pred, elems.iter().map(|e| &**e))
 303             }
 304
 305             hir::ExprCall(ref func, ref args) => {
 306                 self.call(expr, pred, &func, args.iter().map(|e| &**e))
 307             }
 308
 309             hir::ExprMethodCall(.., ref args) => {
 310                 self.call(expr, pred, &args[0], args[1..].iter().map(|e| &**e))
 311             }
 312
 313             hir::ExprIndex(ref l, ref r) |
 314             hir::ExprBinary(_, ref l, ref r) if self.tcx.tables().is_method_call(expr.id) => {
 315                 self.call(expr, pred, &l, Some(&**r).into_iter())
 316             }
 317
 318             hir::ExprUnary(_, ref e) if self.tcx.tables().is_method_call(expr.id) => {
 319                 self.call(expr, pred, &e, None::<hir::Expr>.iter())
 320             }
 321
 322             hir::ExprTup(ref exprs) => {
 323                 self.straightline(expr, pred, exprs.iter().map(|e| &**e))
 324             }
 325
 326             hir::ExprStruct(_, ref fields, ref base) => {
 327                 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
 328                 self.opt_expr(base, field_cfg)
 329             }
 330
 331             hir::ExprRepeat(ref elem, ref count) => {
 332                 self.straightline(expr, pred, [elem, count].iter().map(|&e| &**e))
 333             }
 334
 335             hir::ExprAssign(ref l, ref r) |
 336             hir::ExprAssignOp(_, ref l, ref r) => {
 337                 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
 338             }
 339
 340             hir::ExprIndex(ref l, ref r) |
 341             hir::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier
 342                 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
 343             }
 344
 345             hir::ExprBox(ref e) |
 346             hir::ExprAddrOf(_, ref e) |
 347             hir::ExprCast(ref e, _) |
 348             hir::ExprType(ref e, _) |
 349             hir::ExprUnary(_, ref e) |
 350             hir::ExprField(ref e, _) |
 351             hir::ExprTupField(ref e, _) => {
 352                 self.straightline(expr, pred, Some(&**e).into_iter())
 353             }
 354
 355             hir::ExprInlineAsm(_, ref outputs, ref inputs) => {
 356                 let post_outputs = self.exprs(outputs.iter().map(|e| &**e), pred);
 357                 let post_inputs = self.exprs(inputs.iter().map(|e| &**e), post_outputs);
 358                 self.add_ast_node(expr.id, &[post_inputs])
 359             }
 360
 361             hir::ExprClosure(..) |
 362             hir::ExprLit(..) |
 363             hir::ExprPath(..) => {
 364                 self.straightline(expr, pred, None::<hir::Expr>.iter())
 365             }
 366         }
 367     }
 368
 369     fn call<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
 370             call_expr: &hir::Expr,
 371             pred: CFGIndex,
 372             func_or_rcvr: &hir::Expr,
 373             args: I) -> CFGIndex {
 374         let method_call = ty::MethodCall::expr(call_expr.id);
 375         let fn_ty = match self.tcx.tables().method_map.get(&method_call) {
 376             Some(method) => method.ty,
 377             None => self.tcx.tables().expr_ty_adjusted(func_or_rcvr)
 378         };
 379
 380         let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
 381         let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
 382         // FIXME(canndrew): This is_never should probably be an is_uninhabited.
 383         if fn_ty.fn_ret().0.is_never() {
 384             self.add_unreachable_node()
 385         } else {
 386             ret
 387         }
 388     }
 389
 390     fn exprs<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
 391                                              exprs: I,
 392                                              pred: CFGIndex) -> CFGIndex {
 393         //! Constructs graph for `exprs` evaluated in order
 394         exprs.fold(pred, |p, e| self.expr(e, p))
 395     }
 396
 397     fn opt_expr(&mut self,
 398                 opt_expr: &Option<P<hir::Expr>>,
 399                 pred: CFGIndex) -> CFGIndex {
 400         //! Constructs graph for `opt_expr` evaluated, if Some
 401         opt_expr.iter().fold(pred, |p, e| self.expr(&e, p))
 402     }
 403
 404     fn straightline<'b, I: Iterator<Item=&'b hir::Expr>>(&mut self,
 405                     expr: &hir::Expr,
 406                     pred: CFGIndex,
 407                     subexprs: I) -> CFGIndex {
 408         //! Handles case of an expression that evaluates `subexprs` in order
 409
 410         let subexprs_exit = self.exprs(subexprs, pred);
 411         self.add_ast_node(expr.id, &[subexprs_exit])
 412     }
 413
 414     fn match_(&mut self, id: ast::NodeId, discr: &hir::Expr,
 415               arms: &[hir::Arm], pred: CFGIndex) -> CFGIndex {
 416         // The CFG for match expression is quite complex, so no ASCII
 417         // art for it (yet).
 418         //
 419         // The CFG generated below matches roughly what trans puts
 420         // out. Each pattern and guard is visited in parallel, with
 421         // arms containing multiple patterns generating multiple nodes
 422         // for the same guard expression. The guard expressions chain
 423         // into each other from top to bottom, with a specific
 424         // exception to allow some additional valid programs
 425         // (explained below). Trans differs slightly in that the
 426         // pattern matching may continue after a guard but the visible
 427         // behaviour should be the same.
 428         //
 429         // What is going on is explained in further comments.
 430
 431         // Visit the discriminant expression
 432         let discr_exit = self.expr(discr, pred);
 433
 434         // Add a node for the exit of the match expression as a whole.
 435         let expr_exit = self.add_ast_node(id, &[]);
 436
 437         // Keep track of the previous guard expressions
 438         let mut prev_guards = Vec::new();
 439         // Track if the previous pattern contained bindings or wildcards
 440         let mut prev_has_bindings = false;
 441
 442         for arm in arms {
 443             // Add an exit node for when we've visited all the
 444             // patterns and the guard (if there is one) in the arm.
 445             let arm_exit = self.add_dummy_node(&[]);
 446
 447             for pat in &arm.pats {
 448                 // Visit the pattern, coming from the discriminant exit
 449                 let mut pat_exit = self.pat(&pat, discr_exit);
 450
 451                 // If there is a guard expression, handle it here
 452                 if let Some(ref guard) = arm.guard {
 453                     // Add a dummy node for the previous guard
 454                     // expression to target
 455                     let guard_start = self.add_dummy_node(&[pat_exit]);
 456                     // Visit the guard expression
 457                     let guard_exit = self.expr(&guard, guard_start);
 458
 459                     let this_has_bindings = pat_util::pat_contains_bindings_or_wild(&pat);
 460
 461                     // If both this pattern and the previous pattern
 462                     // were free of bindings, they must consist only
 463                     // of "constant" patterns. Note we cannot match an
 464                     // all-constant pattern, fail the guard, and then
 465                     // match *another* all-constant pattern. This is
 466                     // because if the previous pattern matches, then
 467                     // we *cannot* match this one, unless all the
 468                     // constants are the same (which is rejected by
 469                     // `check_match`).
 470                     //
 471                     // We can use this to be smarter about the flow
 472                     // along guards. If the previous pattern matched,
 473                     // then we know we will not visit the guard in
 474                     // this one (whether or not the guard succeeded),
 475                     // if the previous pattern failed, then we know
 476                     // the guard for that pattern will not have been
 477                     // visited. Thus, it is not possible to visit both
 478                     // the previous guard and the current one when
 479                     // both patterns consist only of constant
 480                     // sub-patterns.
 481                     //
 482                     // However, if the above does not hold, then all
 483                     // previous guards need to be wired to visit the
 484                     // current guard pattern.
 485                     if prev_has_bindings || this_has_bindings {
 486                         while let Some(prev) = prev_guards.pop() {
 487                             self.add_contained_edge(prev, guard_start);
 488                         }
 489                     }
 490
 491                     prev_has_bindings = this_has_bindings;
 492
 493                     // Push the guard onto the list of previous guards
 494                     prev_guards.push(guard_exit);
 495
 496                     // Update the exit node for the pattern
 497                     pat_exit = guard_exit;
 498                 }
 499
 500                 // Add an edge from the exit of this pattern to the
 501                 // exit of the arm
 502                 self.add_contained_edge(pat_exit, arm_exit);
 503             }
 504
 505             // Visit the body of this arm
 506             let body_exit = self.expr(&arm.body, arm_exit);
 507
 508             // Link the body to the exit of the expression
 509             self.add_contained_edge(body_exit, expr_exit);
 510         }
 511
 512         expr_exit
 513     }
 514
 515     fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
 516         self.add_node(CFGNodeData::Dummy, preds)
 517     }
 518
 519     fn add_ast_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
 520         assert!(id != ast::DUMMY_NODE_ID);
 521         self.add_node(CFGNodeData::AST(id), preds)
 522     }
 523
 524     fn add_unreachable_node(&mut self) -> CFGIndex {
 525         self.add_node(CFGNodeData::Unreachable, &[])
 526     }
 527
 528     fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
 529         let node = self.graph.add_node(data);
 530         for &pred in preds {
 531             self.add_contained_edge(pred, node);
 532         }
 533         node
 534     }
 535
 536     fn add_contained_edge(&mut self,
 537                           source: CFGIndex,
 538                           target: CFGIndex) {
 539         let data = CFGEdgeData {exiting_scopes: vec![] };
 540         self.graph.add_edge(source, target, data);
 541     }
 542
 543     fn add_exiting_edge(&mut self,
 544                         from_expr: &hir::Expr,
 545                         from_index: CFGIndex,
 546                         to_loop: LoopScope,
 547                         to_index: CFGIndex) {
 548         let mut data = CFGEdgeData {exiting_scopes: vec![] };
 549         let mut scope = self.tcx.region_maps.node_extent(from_expr.id);
 550         let target_scope = self.tcx.region_maps.node_extent(to_loop.loop_id);
 551         while scope != target_scope {
 552             data.exiting_scopes.push(scope.node_id(&self.tcx.region_maps));
 553             scope = self.tcx.region_maps.encl_scope(scope);
 554         }
 555         self.graph.add_edge(from_index, to_index, data);
 556     }
 557
 558     fn add_returning_edge(&mut self,
 559                           _from_expr: &hir::Expr,
 560                           from_index: CFGIndex) {
 561         let mut data = CFGEdgeData {
 562             exiting_scopes: vec![],
 563         };
 564         for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
 565             data.exiting_scopes.push(id);
 566         }
 567         self.graph.add_edge(from_index, self.fn_exit, data);
 568     }
 569
 570     fn find_scope(&self,
 571                   expr: &hir::Expr,
 572                   label: Option<ast::Name>) -> LoopScope {
 573         if label.is_none() {
 574             return *self.loop_scopes.last().unwrap();
 575         }
 576
 577         match self.tcx.expect_def(expr.id) {
 578             Def::Label(loop_id) => {
 579                 for l in &self.loop_scopes {
 580                     if l.loop_id == loop_id {
 581                         return *l;
 582                     }
 583                 }
 584                 span_bug!(expr.span, "no loop scope for id {}", loop_id);
 585             }
 586
 587             r => {
 588                 span_bug!(expr.span, "bad entry `{:?}` in def_map for label", r);
 589             }
 590         }
 591     }
 592 }