src/librustc/middle/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 middle::cfg::*;
  12 use middle::def;
  13 use middle::graph;
  14 use middle::typeck;
  15 use middle::ty;
  16 use syntax::ast;
  17 use syntax::ast_util;
  18 use syntax::ptr::P;
  19 use util::nodemap::NodeMap;
  20
  21 struct CFGBuilder<'a, 'tcx: 'a> {
  22     tcx: &'a ty::ctxt<'tcx>,
  23     exit_map: NodeMap<CFGIndex>,
  24     graph: CFGGraph,
  25     fn_exit: CFGIndex,
  26     loop_scopes: Vec<LoopScope>,
  27 }
  28
  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(tcx: &ty::ctxt,
  36                  blk: &ast::Block) -> CFG {
  37     let mut graph = graph::Graph::new();
  38     let entry = add_initial_dummy_node(&mut graph);
  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 = add_initial_dummy_node(&mut graph);
  45     let block_exit;
  46
  47     let mut cfg_builder = CFGBuilder {
  48         exit_map: NodeMap::new(),
  49         graph: graph,
  50         fn_exit: fn_exit,
  51         tcx: tcx,
  52         loop_scopes: Vec::new()
  53     };
  54     block_exit = cfg_builder.block(blk, entry);
  55     cfg_builder.add_contained_edge(block_exit, fn_exit);
  56     let CFGBuilder {exit_map, graph, ..} = cfg_builder;
  57     CFG {exit_map: exit_map,
  58          graph: graph,
  59          entry: entry,
  60          exit: fn_exit}
  61 }
  62
  63 fn add_initial_dummy_node(g: &mut CFGGraph) -> CFGIndex {
  64     g.add_node(CFGNodeData { id: ast::DUMMY_NODE_ID })
  65 }
  66
  67 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
  68     fn block(&mut self, blk: &ast::Block, pred: CFGIndex) -> CFGIndex {
  69         let mut stmts_exit = pred;
  70         for stmt in blk.stmts.iter() {
  71             stmts_exit = self.stmt(&**stmt, stmts_exit);
  72         }
  73
  74         let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
  75
  76         self.add_node(blk.id, [expr_exit])
  77     }
  78
  79     fn stmt(&mut self, stmt: &ast::Stmt, pred: CFGIndex) -> CFGIndex {
  80         match stmt.node {
  81             ast::StmtDecl(ref decl, id) => {
  82                 let exit = self.decl(&**decl, pred);
  83                 self.add_node(id, [exit])
  84             }
  85
  86             ast::StmtExpr(ref expr, id) | ast::StmtSemi(ref expr, id) => {
  87                 let exit = self.expr(&**expr, pred);
  88                 self.add_node(id, [exit])
  89             }
  90
  91             ast::StmtMac(..) => {
  92                 self.tcx.sess.span_bug(stmt.span, "unexpanded macro");
  93             }
  94         }
  95     }
  96
  97     fn decl(&mut self, decl: &ast::Decl, pred: CFGIndex) -> CFGIndex {
  98         match decl.node {
  99             ast::DeclLocal(ref local) => {
 100                 let init_exit = self.opt_expr(&local.init, pred);
 101                 self.pat(&*local.pat, init_exit)
 102             }
 103
 104             ast::DeclItem(_) => {
 105                 pred
 106             }
 107         }
 108     }
 109
 110     fn pat(&mut self, pat: &ast::Pat, pred: CFGIndex) -> CFGIndex {
 111         match pat.node {
 112             ast::PatIdent(_, _, None) |
 113             ast::PatEnum(_, None) |
 114             ast::PatLit(..) |
 115             ast::PatRange(..) |
 116             ast::PatWild(_) => {
 117                 self.add_node(pat.id, [pred])
 118             }
 119
 120             ast::PatBox(ref subpat) |
 121             ast::PatRegion(ref subpat) |
 122             ast::PatIdent(_, _, Some(ref subpat)) => {
 123                 let subpat_exit = self.pat(&**subpat, pred);
 124                 self.add_node(pat.id, [subpat_exit])
 125             }
 126
 127             ast::PatEnum(_, Some(ref subpats)) |
 128             ast::PatTup(ref subpats) => {
 129                 let pats_exit = self.pats_all(subpats.iter(), pred);
 130                 self.add_node(pat.id, [pats_exit])
 131             }
 132
 133             ast::PatStruct(_, ref subpats, _) => {
 134                 let pats_exit =
 135                     self.pats_all(subpats.iter().map(|f| &f.pat), pred);
 136                 self.add_node(pat.id, [pats_exit])
 137             }
 138
 139             ast::PatVec(ref pre, ref vec, ref post) => {
 140                 let pre_exit = self.pats_all(pre.iter(), pred);
 141                 let vec_exit = self.pats_all(vec.iter(), pre_exit);
 142                 let post_exit = self.pats_all(post.iter(), vec_exit);
 143                 self.add_node(pat.id, [post_exit])
 144             }
 145
 146             ast::PatMac(_) => {
 147                 self.tcx.sess.span_bug(pat.span, "unexpanded macro");
 148             }
 149         }
 150     }
 151
 152     fn pats_all<'a, I: Iterator<&'a P<ast::Pat>>>(&mut self,
 153                                           pats: I,
 154                                           pred: CFGIndex) -> CFGIndex {
 155         //! Handles case where all of the patterns must match.
 156         let mut pats = pats;
 157         pats.fold(pred, |pred, pat| self.pat(&**pat, pred))
 158     }
 159
 160     fn pats_any(&mut self,
 161                 pats: &[P<ast::Pat>],
 162                 pred: CFGIndex) -> CFGIndex {
 163         //! Handles case where just one of the patterns must match.
 164
 165         if pats.len() == 1 {
 166             self.pat(&*pats[0], pred)
 167         } else {
 168             let collect = self.add_dummy_node([]);
 169             for pat in pats.iter() {
 170                 let pat_exit = self.pat(&**pat, pred);
 171                 self.add_contained_edge(pat_exit, collect);
 172             }
 173             collect
 174         }
 175     }
 176
 177     fn expr(&mut self, expr: &ast::Expr, pred: CFGIndex) -> CFGIndex {
 178         match expr.node {
 179             ast::ExprBlock(ref blk) => {
 180                 let blk_exit = self.block(&**blk, pred);
 181                 self.add_node(expr.id, [blk_exit])
 182             }
 183
 184             ast::ExprIf(ref cond, ref then, None) => {
 185                 //
 186                 //     [pred]
 187                 //       |
 188                 //       v 1
 189                 //     [cond]
 190                 //       |
 191                 //      / \
 192                 //     /   \
 193                 //    v 2   *
 194                 //  [then]  |
 195                 //    |     |
 196                 //    v 3   v 4
 197                 //   [..expr..]
 198                 //
 199                 let cond_exit = self.expr(&**cond, pred);                // 1
 200                 let then_exit = self.block(&**then, cond_exit);          // 2
 201                 self.add_node(expr.id, [cond_exit, then_exit])           // 3,4
 202             }
 203
 204             ast::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
 205                 //
 206                 //     [pred]
 207                 //       |
 208                 //       v 1
 209                 //     [cond]
 210                 //       |
 211                 //      / \
 212                 //     /   \
 213                 //    v 2   v 3
 214                 //  [then][otherwise]
 215                 //    |     |
 216                 //    v 4   v 5
 217                 //   [..expr..]
 218                 //
 219                 let cond_exit = self.expr(&**cond, pred);                // 1
 220                 let then_exit = self.block(&**then, cond_exit);          // 2
 221                 let else_exit = self.expr(&**otherwise, cond_exit);      // 3
 222                 self.add_node(expr.id, [then_exit, else_exit])           // 4, 5
 223             }
 224
 225             ast::ExprWhile(ref cond, ref body, _) => {
 226                 //
 227                 //         [pred]
 228                 //           |
 229                 //           v 1
 230                 //       [loopback] <--+ 5
 231                 //           |         |
 232                 //           v 2       |
 233                 //   +-----[cond]      |
 234                 //   |       |         |
 235                 //   |       v 4       |
 236                 //   |     [body] -----+
 237                 //   v 3
 238                 // [expr]
 239                 //
 240                 // Note that `break` and `continue` statements
 241                 // may cause additional edges.
 242
 243                 // Is the condition considered part of the loop?
 244                 let loopback = self.add_dummy_node([pred]);              // 1
 245                 let cond_exit = self.expr(&**cond, loopback);            // 2
 246                 let expr_exit = self.add_node(expr.id, [cond_exit]);     // 3
 247                 self.loop_scopes.push(LoopScope {
 248                     loop_id: expr.id,
 249                     continue_index: loopback,
 250                     break_index: expr_exit
 251                 });
 252                 let body_exit = self.block(&**body, cond_exit);          // 4
 253                 self.add_contained_edge(body_exit, loopback);            // 5
 254                 self.loop_scopes.pop();
 255                 expr_exit
 256             }
 257
 258             ast::ExprForLoop(ref pat, ref head, ref body, _) => {
 259                 //
 260                 //          [pred]
 261                 //            |
 262                 //            v 1
 263                 //          [head]
 264                 //            |
 265                 //            v 2
 266                 //        [loopback] <--+ 7
 267                 //            |         |
 268                 //            v 3       |
 269                 //   +------[cond]      |
 270                 //   |        |         |
 271                 //   |        v 5       |
 272                 //   |       [pat]      |
 273                 //   |        |         |
 274                 //   |        v 6       |
 275                 //   v 4    [body] -----+
 276                 // [expr]
 277                 //
 278                 // Note that `break` and `continue` statements
 279                 // may cause additional edges.
 280
 281                 let head = self.expr(&**head, pred);            // 1
 282                 let loopback = self.add_dummy_node([head]);     // 2
 283                 let cond = self.add_dummy_node([loopback]);     // 3
 284                 let expr_exit = self.add_node(expr.id, [cond]); // 4
 285                 self.loop_scopes.push(LoopScope {
 286                     loop_id: expr.id,
 287                     continue_index: loopback,
 288                     break_index: expr_exit,
 289                 });
 290                 let pat = self.pat(&**pat, cond);               // 5
 291                 let body = self.block(&**body, pat);            // 6
 292                 self.add_contained_edge(body, loopback);        // 7
 293                 self.loop_scopes.pop();
 294                 expr_exit
 295             }
 296
 297             ast::ExprLoop(ref body, _) => {
 298                 //
 299                 //     [pred]
 300                 //       |
 301                 //       v 1
 302                 //   [loopback] <---+
 303                 //       |      4   |
 304                 //       v 3        |
 305                 //     [body] ------+
 306                 //
 307                 //     [expr] 2
 308                 //
 309                 // Note that `break` and `loop` statements
 310                 // may cause additional edges.
 311
 312                 let loopback = self.add_dummy_node([pred]);              // 1
 313                 let expr_exit = self.add_node(expr.id, []);              // 2
 314                 self.loop_scopes.push(LoopScope {
 315                     loop_id: expr.id,
 316                     continue_index: loopback,
 317                     break_index: expr_exit,
 318                 });
 319                 let body_exit = self.block(&**body, loopback);           // 3
 320                 self.add_contained_edge(body_exit, loopback);            // 4
 321                 self.loop_scopes.pop();
 322                 expr_exit
 323             }
 324
 325             ast::ExprMatch(ref discr, ref arms) => {
 326                 //
 327                 //     [pred]
 328                 //       |
 329                 //       v 1
 330                 //    [discr]
 331                 //       |
 332                 //       v 2
 333                 //    [cond1]
 334                 //      /  \
 335                 //     |    \
 336                 //     v 3   \
 337                 //  [pat1]    \
 338                 //     |       |
 339                 //     v 4     |
 340                 //  [guard1]   |
 341                 //     |       |
 342                 //     |       |
 343                 //     v 5     v
 344                 //  [body1]  [cond2]
 345                 //     |      /  \
 346                 //     |    ...  ...
 347                 //     |     |    |
 348                 //     v 6   v    v
 349                 //  [.....expr.....]
 350                 //
 351                 let discr_exit = self.expr(&**discr, pred);              // 1
 352
 353                 let expr_exit = self.add_node(expr.id, []);
 354                 let mut cond_exit = discr_exit;
 355                 for arm in arms.iter() {
 356                     cond_exit = self.add_dummy_node([cond_exit]);        // 2
 357                     let pats_exit = self.pats_any(arm.pats.as_slice(),
 358                                                   cond_exit);            // 3
 359                     let guard_exit = self.opt_expr(&arm.guard,
 360                                                    pats_exit);           // 4
 361                     let body_exit = self.expr(&*arm.body, guard_exit);   // 5
 362                     self.add_contained_edge(body_exit, expr_exit);       // 6
 363                 }
 364                 expr_exit
 365             }
 366
 367             ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op) => {
 368                 //
 369                 //     [pred]
 370                 //       |
 371                 //       v 1
 372                 //      [l]
 373                 //       |
 374                 //      / \
 375                 //     /   \
 376                 //    v 2  *
 377                 //   [r]   |
 378                 //    |    |
 379                 //    v 3  v 4
 380                 //   [..exit..]
 381                 //
 382                 let l_exit = self.expr(&**l, pred);                      // 1
 383                 let r_exit = self.expr(&**r, l_exit);                    // 2
 384                 self.add_node(expr.id, [l_exit, r_exit])                 // 3,4
 385             }
 386
 387             ast::ExprRet(ref v) => {
 388                 let v_exit = self.opt_expr(v, pred);
 389                 let b = self.add_node(expr.id, [v_exit]);
 390                 self.add_returning_edge(expr, b);
 391                 self.add_node(ast::DUMMY_NODE_ID, [])
 392             }
 393
 394             ast::ExprBreak(label) => {
 395                 let loop_scope = self.find_scope(expr, label);
 396                 let b = self.add_node(expr.id, [pred]);
 397                 self.add_exiting_edge(expr, b,
 398                                       loop_scope, loop_scope.break_index);
 399                 self.add_node(ast::DUMMY_NODE_ID, [])
 400             }
 401
 402             ast::ExprAgain(label) => {
 403                 let loop_scope = self.find_scope(expr, label);
 404                 let a = self.add_node(expr.id, [pred]);
 405                 self.add_exiting_edge(expr, a,
 406                                       loop_scope, loop_scope.continue_index);
 407                 self.add_node(ast::DUMMY_NODE_ID, [])
 408             }
 409
 410             ast::ExprVec(ref elems) => {
 411                 self.straightline(expr, pred, elems.iter().map(|e| &**e))
 412             }
 413
 414             ast::ExprCall(ref func, ref args) => {
 415                 self.call(expr, pred, &**func, args.iter().map(|e| &**e))
 416             }
 417
 418             ast::ExprMethodCall(_, _, ref args) => {
 419                 self.call(expr, pred, &**args.get(0), args.slice_from(1).iter().map(|e| &**e))
 420             }
 421
 422             ast::ExprIndex(ref l, ref r) |
 423             ast::ExprBinary(_, ref l, ref r) if self.is_method_call(expr) => {
 424                 self.call(expr, pred, &**l, Some(&**r).into_iter())
 425             }
 426
 427             ast::ExprSlice(ref base, ref start, ref end, _) => {
 428                 self.call(expr,
 429                           pred,
 430                           &**base,
 431                           start.iter().chain(end.iter()).map(|x| &**x))
 432             }
 433
 434             ast::ExprUnary(_, ref e) if self.is_method_call(expr) => {
 435                 self.call(expr, pred, &**e, None::<ast::Expr>.iter())
 436             }
 437
 438             ast::ExprTup(ref exprs) => {
 439                 self.straightline(expr, pred, exprs.iter().map(|e| &**e))
 440             }
 441
 442             ast::ExprStruct(_, ref fields, ref base) => {
 443                 let base_exit = self.opt_expr(base, pred);
 444                 self.straightline(expr, base_exit, fields.iter().map(|f| &*f.expr))
 445             }
 446
 447             ast::ExprRepeat(ref elem, ref count) => {
 448                 self.straightline(expr, pred, [elem, count].iter().map(|&e| &**e))
 449             }
 450
 451             ast::ExprAssign(ref l, ref r) |
 452             ast::ExprAssignOp(_, ref l, ref r) => {
 453                 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
 454             }
 455
 456             ast::ExprIndex(ref l, ref r) |
 457             ast::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier
 458                 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
 459             }
 460
 461             ast::ExprBox(ref p, ref e) => {
 462                 self.straightline(expr, pred, [p, e].iter().map(|&e| &**e))
 463             }
 464
 465             ast::ExprAddrOf(_, ref e) |
 466             ast::ExprCast(ref e, _) |
 467             ast::ExprUnary(_, ref e) |
 468             ast::ExprParen(ref e) |
 469             ast::ExprField(ref e, _, _) |
 470             ast::ExprTupField(ref e, _, _) => {
 471                 self.straightline(expr, pred, Some(&**e).into_iter())
 472             }
 473
 474             ast::ExprInlineAsm(ref inline_asm) => {
 475                 let inputs = inline_asm.inputs.iter();
 476                 let outputs = inline_asm.outputs.iter();
 477                 let post_inputs = self.exprs(inputs.map(|a| {
 478                     debug!("cfg::construct InlineAsm id:{} input:{:?}", expr.id, a);
 479                     let &(_, ref expr) = a;
 480                     &**expr
 481                 }), pred);
 482                 let post_outputs = self.exprs(outputs.map(|a| {
 483                     debug!("cfg::construct InlineAsm id:{} output:{:?}", expr.id, a);
 484                     let &(_, ref expr, _) = a;
 485                     &**expr
 486                 }), post_inputs);
 487                 self.add_node(expr.id, [post_outputs])
 488             }
 489
 490             ast::ExprMac(..) |
 491             ast::ExprFnBlock(..) |
 492             ast::ExprProc(..) |
 493             ast::ExprUnboxedFn(..) |
 494             ast::ExprLit(..) |
 495             ast::ExprPath(..) => {
 496                 self.straightline(expr, pred, None::<ast::Expr>.iter())
 497             }
 498         }
 499     }
 500
 501     fn call<'a, I: Iterator<&'a ast::Expr>>(&mut self,
 502             call_expr: &ast::Expr,
 503             pred: CFGIndex,
 504             func_or_rcvr: &ast::Expr,
 505             args: I) -> CFGIndex {
 506         let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
 507         let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
 508
 509         let return_ty = ty::node_id_to_type(self.tcx, call_expr.id);
 510         let fails = ty::type_is_bot(return_ty);
 511         if fails {
 512             self.add_node(ast::DUMMY_NODE_ID, [])
 513         } else {
 514             ret
 515         }
 516     }
 517
 518     fn exprs<'a, I: Iterator<&'a ast::Expr>>(&mut self,
 519                                              mut exprs: I,
 520                                              pred: CFGIndex) -> CFGIndex {
 521         //! Constructs graph for `exprs` evaluated in order
 522         exprs.fold(pred, |p, e| self.expr(e, p))
 523     }
 524
 525     fn opt_expr(&mut self,
 526                 opt_expr: &Option<P<ast::Expr>>,
 527                 pred: CFGIndex) -> CFGIndex {
 528         //! Constructs graph for `opt_expr` evaluated, if Some
 529         opt_expr.iter().fold(pred, |p, e| self.expr(&**e, p))
 530     }
 531
 532     fn straightline<'a, I: Iterator<&'a ast::Expr>>(&mut self,
 533                     expr: &ast::Expr,
 534                     pred: CFGIndex,
 535                     subexprs: I) -> CFGIndex {
 536         //! Handles case of an expression that evaluates `subexprs` in order
 537
 538         let subexprs_exit = self.exprs(subexprs, pred);
 539         self.add_node(expr.id, [subexprs_exit])
 540     }
 541
 542     fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
 543         self.add_node(ast::DUMMY_NODE_ID, preds)
 544     }
 545
 546     fn add_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
 547         assert!(!self.exit_map.contains_key(&id));
 548         let node = self.graph.add_node(CFGNodeData {id: id});
 549         if id != ast::DUMMY_NODE_ID {
 550             assert!(!self.exit_map.contains_key(&id));
 551             self.exit_map.insert(id, node);
 552         }
 553         for &pred in preds.iter() {
 554             self.add_contained_edge(pred, node);
 555         }
 556         node
 557     }
 558
 559     fn add_contained_edge(&mut self,
 560                           source: CFGIndex,
 561                           target: CFGIndex) {
 562         let data = CFGEdgeData {exiting_scopes: vec!() };
 563         self.graph.add_edge(source, target, data);
 564     }
 565
 566     fn add_exiting_edge(&mut self,
 567                         from_expr: &ast::Expr,
 568                         from_index: CFGIndex,
 569                         to_loop: LoopScope,
 570                         to_index: CFGIndex) {
 571         let mut data = CFGEdgeData {exiting_scopes: vec!() };
 572         let mut scope_id = from_expr.id;
 573         while scope_id != to_loop.loop_id {
 574
 575             data.exiting_scopes.push(scope_id);
 576             scope_id = self.tcx.region_maps.encl_scope(scope_id);
 577         }
 578         self.graph.add_edge(from_index, to_index, data);
 579     }
 580
 581     fn add_returning_edge(&mut self,
 582                           _from_expr: &ast::Expr,
 583                           from_index: CFGIndex) {
 584         let mut data = CFGEdgeData {
 585             exiting_scopes: vec!(),
 586         };
 587         for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
 588             data.exiting_scopes.push(id);
 589         }
 590         self.graph.add_edge(from_index, self.fn_exit, data);
 591     }
 592
 593     fn find_scope(&self,
 594                   expr: &ast::Expr,
 595                   label: Option<ast::Ident>) -> LoopScope {
 596         match label {
 597             None => {
 598                 return *self.loop_scopes.last().unwrap();
 599             }
 600
 601             Some(_) => {
 602                 match self.tcx.def_map.borrow().find(&expr.id) {
 603                     Some(&def::DefLabel(loop_id)) => {
 604                         for l in self.loop_scopes.iter() {
 605                             if l.loop_id == loop_id {
 606                                 return *l;
 607                             }
 608                         }
 609                         self.tcx.sess.span_bug(
 610                             expr.span,
 611                             format!("no loop scope for id {:?}",
 612                                     loop_id).as_slice());
 613                     }
 614
 615                     r => {
 616                         self.tcx.sess.span_bug(
 617                             expr.span,
 618                             format!("bad entry `{:?}` in def_map for label",
 619                                     r).as_slice());
 620                     }
 621                 }
 622             }
 623         }
 624     }
 625
 626     fn is_method_call(&self, expr: &ast::Expr) -> bool {
 627         let method_call = typeck::MethodCall::expr(expr.id);
 628         self.tcx.method_map.borrow().contains_key(&method_call)
 629     }
 630 }