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                 //    [cond1]
 337                 //      /  \
 338                 //     |    \
 339                 //     v 3   \
 340                 //  [pat1]    \
 341                 //     |       |
 342                 //     v 4     |
 343                 //  [guard1]   |
 344                 //     |       |
 345                 //     |       |
 346                 //     v 5     v
 347                 //  [body1]  [cond2]
 348                 //     |      /  \
 349                 //     |    ...  ...
 350                 //     |     |    |
 351                 //     v 6   v    v
 352                 //  [.....expr.....]
 353                 //
 354                 let discr_exit = self.expr(discr.clone(), pred);         // 1
 355
 356                 let expr_exit = self.add_node(expr.id, []);
 357                 let mut cond_exit = discr_exit;
 358                 for arm in arms.iter() {
 359                     cond_exit = self.add_dummy_node([cond_exit]);        // 2
 360                     let pats_exit = self.pats_any(arm.pats.as_slice(),
 361                                                   cond_exit);            // 3
 362                     let guard_exit = self.opt_expr(arm.guard,
 363                                                    pats_exit);           // 4
 364                     let body_exit = self.expr(arm.body.clone(),
 365                                               guard_exit);               // 5
 366                     self.add_contained_edge(body_exit, expr_exit);       // 6
 367                 }
 368                 expr_exit
 369             }
 370
 371             ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op) => {
 372                 //
 373                 //     [pred]
 374                 //       |
 375                 //       v 1
 376                 //      [l]
 377                 //       |
 378                 //      / \
 379                 //     /   \
 380                 //    v 2  *
 381                 //   [r]   |
 382                 //    |    |
 383                 //    v 3  v 4
 384                 //   [..exit..]
 385                 //
 386                 let l_exit = self.expr(l.clone(), pred);                  // 1
 387                 let r_exit = self.expr(r.clone(), l_exit);               // 2
 388                 self.add_node(expr.id, [l_exit, r_exit])                 // 3,4
 389             }
 390
 391             ast::ExprRet(ref v) => {
 392                 let v_exit = self.opt_expr(v.clone(), pred);
 393                 let b = self.add_node(expr.id, [v_exit]);
 394                 self.add_returning_edge(expr, b);
 395                 self.add_node(ast::DUMMY_NODE_ID, [])
 396             }
 397
 398             ast::ExprBreak(label) => {
 399                 let loop_scope = self.find_scope(expr, label);
 400                 let b = self.add_node(expr.id, [pred]);
 401                 self.add_exiting_edge(expr, b,
 402                                       loop_scope, loop_scope.break_index);
 403                 self.add_node(ast::DUMMY_NODE_ID, [])
 404             }
 405
 406             ast::ExprAgain(label) => {
 407                 let loop_scope = self.find_scope(expr, label);
 408                 let a = self.add_node(expr.id, [pred]);
 409                 self.add_exiting_edge(expr, a,
 410                                       loop_scope, loop_scope.continue_index);
 411                 self.add_node(ast::DUMMY_NODE_ID, [])
 412             }
 413
 414             ast::ExprVec(ref elems) => {
 415                 self.straightline(expr, pred, elems.as_slice())
 416             }
 417
 418             ast::ExprCall(ref func, ref args) => {
 419                 self.call(expr, pred, func.clone(), args.as_slice())
 420             }
 421
 422             ast::ExprMethodCall(_, _, ref args) => {
 423                 self.call(expr, pred, *args.get(0), args.slice_from(1))
 424             }
 425
 426             ast::ExprIndex(ref l, ref r) |
 427             ast::ExprBinary(_, ref l, ref r) if self.is_method_call(&*expr) => {
 428                 self.call(expr, pred, l.clone(), [r.clone()])
 429             }
 430
 431             ast::ExprUnary(_, ref e) if self.is_method_call(&*expr) => {
 432                 self.call(expr, pred, e.clone(), [])
 433             }
 434
 435             ast::ExprTup(ref exprs) => {
 436                 self.straightline(expr, pred, exprs.as_slice())
 437             }
 438
 439             ast::ExprStruct(_, ref fields, base) => {
 440                 let base_exit = self.opt_expr(base, pred);
 441                 let field_exprs: Vec<Gc<ast::Expr>> =
 442                     fields.iter().map(|f| f.expr).collect();
 443                 self.straightline(expr, base_exit, field_exprs.as_slice())
 444             }
 445
 446             ast::ExprRepeat(elem, count) => {
 447                 self.straightline(expr, pred, [elem, count])
 448             }
 449
 450             ast::ExprAssign(l, r) |
 451             ast::ExprAssignOp(_, l, r) => {
 452                 self.straightline(expr, pred, [r, l])
 453             }
 454
 455             ast::ExprIndex(l, r) |
 456             ast::ExprBinary(_, l, r) => { // NB: && and || handled earlier
 457                 self.straightline(expr, pred, [l, r])
 458             }
 459
 460             ast::ExprBox(p, e) => {
 461                 self.straightline(expr, pred, [p, e])
 462             }
 463
 464             ast::ExprAddrOf(_, e) |
 465             ast::ExprCast(e, _) |
 466             ast::ExprUnary(_, e) |
 467             ast::ExprParen(e) |
 468             ast::ExprVstore(e, _) |
 469             ast::ExprField(e, _, _) => {
 470                 self.straightline(expr, pred, [e])
 471             }
 472
 473             ast::ExprInlineAsm(ref inline_asm) => {
 474                 let inputs = inline_asm.inputs.iter();
 475                 let outputs = inline_asm.outputs.iter();
 476                 fn extract_expr<A>(&(_, expr): &(A, Gc<ast::Expr>)) -> Gc<ast::Expr> { expr }
 477                 let post_inputs = self.exprs(inputs.map(|a| {
 478                     debug!("cfg::construct InlineAsm id:{} input:{:?}", expr.id, a);
 479                     extract_expr(a)
 480                 }), pred);
 481                 let post_outputs = self.exprs(outputs.map(|a| {
 482                     debug!("cfg::construct InlineAsm id:{} output:{:?}", expr.id, a);
 483                     extract_expr(a)
 484                 }), post_inputs);
 485                 self.add_node(expr.id, [post_outputs])
 486             }
 487
 488             ast::ExprMac(..) |
 489             ast::ExprFnBlock(..) |
 490             ast::ExprProc(..) |
 491             ast::ExprUnboxedFn(..) |
 492             ast::ExprLit(..) |
 493             ast::ExprPath(..) => {
 494                 self.straightline(expr, pred, [])
 495             }
 496         }
 497     }
 498
 499     fn call(&mut self,
 500             call_expr: Gc<ast::Expr>,
 501             pred: CFGIndex,
 502             func_or_rcvr: Gc<ast::Expr>,
 503             args: &[Gc<ast::Expr>]) -> CFGIndex {
 504         let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
 505         let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
 506
 507         let return_ty = ty::node_id_to_type(self.tcx, call_expr.id);
 508         let fails = ty::type_is_bot(return_ty);
 509         if fails {
 510             self.add_node(ast::DUMMY_NODE_ID, [])
 511         } else {
 512             ret
 513         }
 514     }
 515
 516     fn exprs<I:Iterator<Gc<ast::Expr>>>(&mut self,
 517                                         mut exprs: I,
 518                                         pred: CFGIndex) -> CFGIndex {
 519         //! Constructs graph for `exprs` evaluated in order
 520         exprs.fold(pred, |p, e| self.expr(e, p))
 521     }
 522
 523     fn opt_expr(&mut self,
 524                 opt_expr: Option<Gc<ast::Expr>>,
 525                 pred: CFGIndex) -> CFGIndex {
 526         //! Constructs graph for `opt_expr` evaluated, if Some
 527
 528         opt_expr.iter().fold(pred, |p, &e| self.expr(e, p))
 529     }
 530
 531     fn straightline(&mut self,
 532                     expr: Gc<ast::Expr>,
 533                     pred: CFGIndex,
 534                     subexprs: &[Gc<ast::Expr>]) -> CFGIndex {
 535         //! Handles case of an expression that evaluates `subexprs` in order
 536
 537         let subexprs_exit = self.exprs(subexprs.iter().map(|&e|e), pred);
 538         self.add_node(expr.id, [subexprs_exit])
 539     }
 540
 541     fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
 542         self.add_node(ast::DUMMY_NODE_ID, preds)
 543     }
 544
 545     fn add_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
 546         assert!(!self.exit_map.contains_key(&id));
 547         let node = self.graph.add_node(CFGNodeData {id: id});
 548         if id != ast::DUMMY_NODE_ID {
 549             assert!(!self.exit_map.contains_key(&id));
 550             self.exit_map.insert(id, node);
 551         }
 552         for &pred in preds.iter() {
 553             self.add_contained_edge(pred, node);
 554         }
 555         node
 556     }
 557
 558     fn add_contained_edge(&mut self,
 559                           source: CFGIndex,
 560                           target: CFGIndex) {
 561         let data = CFGEdgeData {exiting_scopes: vec!() };
 562         self.graph.add_edge(source, target, data);
 563     }
 564
 565     fn add_exiting_edge(&mut self,
 566                         from_expr: Gc<ast::Expr>,
 567                         from_index: CFGIndex,
 568                         to_loop: LoopScope,
 569                         to_index: CFGIndex) {
 570         let mut data = CFGEdgeData {exiting_scopes: vec!() };
 571         let mut scope_id = from_expr.id;
 572         while scope_id != to_loop.loop_id {
 573
 574             data.exiting_scopes.push(scope_id);
 575             scope_id = self.tcx.region_maps.encl_scope(scope_id);
 576         }
 577         self.graph.add_edge(from_index, to_index, data);
 578     }
 579
 580     fn add_returning_edge(&mut self,
 581                           _from_expr: Gc<ast::Expr>,
 582                           from_index: CFGIndex) {
 583         let mut data = CFGEdgeData {
 584             exiting_scopes: vec!(),
 585         };
 586         for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
 587             data.exiting_scopes.push(id);
 588         }
 589         self.graph.add_edge(from_index, self.fn_exit, data);
 590     }
 591
 592     fn find_scope(&self,
 593                   expr: Gc<ast::Expr>,
 594                   label: Option<ast::Ident>) -> LoopScope {
 595         match label {
 596             None => {
 597                 return *self.loop_scopes.last().unwrap();
 598             }
 599
 600             Some(_) => {
 601                 match self.tcx.def_map.borrow().find(&expr.id) {
 602                     Some(&def::DefLabel(loop_id)) => {
 603                         for l in self.loop_scopes.iter() {
 604                             if l.loop_id == loop_id {
 605                                 return *l;
 606                             }
 607                         }
 608                         self.tcx.sess.span_bug(
 609                             expr.span,
 610                             format!("no loop scope for id {:?}",
 611                                     loop_id).as_slice());
 612                     }
 613
 614                     r => {
 615                         self.tcx.sess.span_bug(
 616                             expr.span,
 617                             format!("bad entry `{:?}` in def_map for label",
 618                                     r).as_slice());
 619                     }
 620                 }
 621             }
 622         }
 623     }
 624
 625     fn is_method_call(&self, expr: &ast::Expr) -> bool {
 626         let method_call = typeck::MethodCall::expr(expr.id);
 627         self.tcx.method_map.borrow().contains_key(&method_call)
 628     }
 629 }