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