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 syntax::ast;
  16 use syntax::ast_util;
  17 use syntax::opt_vec;
  18 use util::nodemap::NodeMap;
  19
  20 struct CFGBuilder {
  21     tcx: ty::ctxt,
  22     method_map: typeck::MethodMap,
  23     exit_map: NodeMap<CFGIndex>,
  24     graph: CFGGraph,
  25     loop_scopes: Vec<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: NodeMap::new(),
  39         graph: graph::Graph::new(),
  40         tcx: tcx,
  41         method_map: method_map,
  42         loop_scopes: Vec::new()
  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.as_slice(),
 302                                                   guard_exit); // 3
 303                     let body_exit = self.expr(arm.body, pats_exit);      // 4
 304                     self.add_contained_edge(body_exit, expr_exit);       // 5
 305                 }
 306                 expr_exit
 307             }
 308
 309             ast::ExprBinary(op, l, r) if ast_util::lazy_binop(op) => {
 310                 //
 311                 //     [pred]
 312                 //       |
 313                 //       v 1
 314                 //      [l]
 315                 //       |
 316                 //      / \
 317                 //     /   \
 318                 //    v 2  *
 319                 //   [r]   |
 320                 //    |    |
 321                 //    v 3  v 4
 322                 //   [..exit..]
 323                 //
 324                 let l_exit = self.expr(l, pred);                         // 1
 325                 let r_exit = self.expr(r, l_exit);                       // 2
 326                 self.add_node(expr.id, [l_exit, r_exit])                 // 3,4
 327             }
 328
 329             ast::ExprRet(v) => {
 330                 let v_exit = self.opt_expr(v, pred);
 331                 let loop_scope = self.loop_scopes[0];
 332                 self.add_exiting_edge(expr, v_exit,
 333                                       loop_scope, loop_scope.break_index);
 334                 self.add_node(expr.id, [])
 335             }
 336
 337             ast::ExprBreak(label) => {
 338                 let loop_scope = self.find_scope(expr, label);
 339                 self.add_exiting_edge(expr, pred,
 340                                       loop_scope, loop_scope.break_index);
 341                 self.add_node(expr.id, [])
 342             }
 343
 344             ast::ExprAgain(label) => {
 345                 let loop_scope = self.find_scope(expr, label);
 346                 self.add_exiting_edge(expr, pred,
 347                                       loop_scope, loop_scope.continue_index);
 348                 self.add_node(expr.id, [])
 349             }
 350
 351             ast::ExprVec(ref elems, _) => {
 352                 self.straightline(expr, pred, elems.as_slice())
 353             }
 354
 355             ast::ExprCall(func, ref args) => {
 356                 self.call(expr, pred, func, args.as_slice())
 357             }
 358
 359             ast::ExprMethodCall(_, _, ref args) => {
 360                 self.call(expr, pred, *args.get(0), args.slice_from(1))
 361             }
 362
 363             ast::ExprIndex(l, r) |
 364             ast::ExprBinary(_, l, r) if self.is_method_call(expr) => {
 365                 self.call(expr, pred, l, [r])
 366             }
 367
 368             ast::ExprUnary(_, e) if self.is_method_call(expr) => {
 369                 self.call(expr, pred, e, [])
 370             }
 371
 372             ast::ExprTup(ref exprs) => {
 373                 self.straightline(expr, pred, exprs.as_slice())
 374             }
 375
 376             ast::ExprStruct(_, ref fields, base) => {
 377                 let base_exit = self.opt_expr(base, pred);
 378                 let field_exprs: Vec<@ast::Expr> =
 379                     fields.iter().map(|f| f.expr).collect();
 380                 self.straightline(expr, base_exit, field_exprs)
 381             }
 382
 383             ast::ExprRepeat(elem, count, _) => {
 384                 self.straightline(expr, pred, [elem, count])
 385             }
 386
 387             ast::ExprAssign(l, r) |
 388             ast::ExprAssignOp(_, l, r) => {
 389                 self.straightline(expr, pred, [r, l])
 390             }
 391
 392             ast::ExprIndex(l, r) |
 393             ast::ExprBinary(_, l, r) => { // NB: && and || handled earlier
 394                 self.straightline(expr, pred, [l, r])
 395             }
 396
 397             ast::ExprBox(p, e) => {
 398                 self.straightline(expr, pred, [p, e])
 399             }
 400
 401             ast::ExprAddrOf(_, e) |
 402             ast::ExprCast(e, _) |
 403             ast::ExprUnary(_, e) |
 404             ast::ExprParen(e) |
 405             ast::ExprVstore(e, _) |
 406             ast::ExprField(e, _, _) => {
 407                 self.straightline(expr, pred, [e])
 408             }
 409
 410             ast::ExprLogLevel |
 411             ast::ExprMac(..) |
 412             ast::ExprInlineAsm(..) |
 413             ast::ExprFnBlock(..) |
 414             ast::ExprProc(..) |
 415             ast::ExprLit(..) |
 416             ast::ExprPath(..) => {
 417                 self.straightline(expr, pred, [])
 418             }
 419         }
 420     }
 421
 422     fn call(&mut self,
 423             call_expr: @ast::Expr,
 424             pred: CFGIndex,
 425             func_or_rcvr: @ast::Expr,
 426             args: &[@ast::Expr]) -> CFGIndex {
 427         let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
 428         self.straightline(call_expr, func_or_rcvr_exit, args)
 429     }
 430
 431     fn exprs(&mut self,
 432              exprs: &[@ast::Expr],
 433              pred: CFGIndex) -> CFGIndex {
 434         //! Constructs graph for `exprs` evaluated in order
 435
 436         exprs.iter().fold(pred, |p, &e| self.expr(e, p))
 437     }
 438
 439     fn opt_expr(&mut self,
 440                 opt_expr: Option<@ast::Expr>,
 441                 pred: CFGIndex) -> CFGIndex {
 442         //! Constructs graph for `opt_expr` evaluated, if Some
 443
 444         opt_expr.iter().fold(pred, |p, &e| self.expr(e, p))
 445     }
 446
 447     fn straightline(&mut self,
 448                     expr: @ast::Expr,
 449                     pred: CFGIndex,
 450                     subexprs: &[@ast::Expr]) -> CFGIndex {
 451         //! Handles case of an expression that evaluates `subexprs` in order
 452
 453         let subexprs_exit = self.exprs(subexprs, pred);
 454         self.add_node(expr.id, [subexprs_exit])
 455     }
 456
 457     fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
 458         self.add_node(0, preds)
 459     }
 460
 461     fn add_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
 462         assert!(!self.exit_map.contains_key(&id));
 463         let node = self.graph.add_node(CFGNodeData {id: id});
 464         self.exit_map.insert(id, node);
 465         for &pred in preds.iter() {
 466             self.add_contained_edge(pred, node);
 467         }
 468         node
 469     }
 470
 471     fn add_contained_edge(&mut self,
 472                           source: CFGIndex,
 473                           target: CFGIndex) {
 474         let data = CFGEdgeData {exiting_scopes: opt_vec::Empty};
 475         self.graph.add_edge(source, target, data);
 476     }
 477
 478     fn add_exiting_edge(&mut self,
 479                         from_expr: @ast::Expr,
 480                         from_index: CFGIndex,
 481                         to_loop: LoopScope,
 482                         to_index: CFGIndex) {
 483         let mut data = CFGEdgeData {exiting_scopes: opt_vec::Empty};
 484         let mut scope_id = from_expr.id;
 485         while scope_id != to_loop.loop_id {
 486             data.exiting_scopes.push(scope_id);
 487             scope_id = self.tcx.region_maps.encl_scope(scope_id);
 488         }
 489         self.graph.add_edge(from_index, to_index, data);
 490     }
 491
 492     fn find_scope(&self,
 493                   expr: @ast::Expr,
 494                   label: Option<ast::Ident>) -> LoopScope {
 495         match label {
 496             None => {
 497                 return *self.loop_scopes.last().unwrap();
 498             }
 499
 500             Some(_) => {
 501                 let def_map = self.tcx.def_map.borrow();
 502                 match def_map.get().find(&expr.id) {
 503                     Some(&ast::DefLabel(loop_id)) => {
 504                         for l in self.loop_scopes.iter() {
 505                             if l.loop_id == loop_id {
 506                                 return *l;
 507                             }
 508                         }
 509                         self.tcx.sess.span_bug(
 510                             expr.span,
 511                             format!("no loop scope for id {:?}", loop_id));
 512                     }
 513
 514                     r => {
 515                         self.tcx.sess.span_bug(
 516                             expr.span,
 517                             format!("bad entry `{:?}` in def_map for label", r));
 518                     }
 519                 }
 520             }
 521         }
 522     }
 523
 524     fn is_method_call(&self, expr: &ast::Expr) -> bool {
 525         let method_map = self.method_map.borrow();
 526         method_map.get().contains_key(&expr.id)
 527     }
 528 }