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