src/librustc/middle/cfg/construct.rs

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