src/librustc/middle/cfg/construct.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use rustc_data_structures::graph;
  12 use middle::cfg::*;
  13 use middle::def;
  14 use middle::pat_util;
  15 use middle::region::CodeExtent;
  16 use middle::ty;
  17 use syntax::ast;
  18 use syntax::ast_util;
  19 use syntax::ptr::P;
  20
  21 struct CFGBuilder<'a, 'tcx: 'a> {
  22     tcx: &'a ty::ctxt<'tcx>,
  23     graph: CFGGraph,
  24     fn_exit: CFGIndex,
  25     loop_scopes: Vec<LoopScope>,
  26 }
  27
  28 #[derive(Copy, Clone)]
  29 struct LoopScope {
  30     loop_id: ast::NodeId,     // id of loop/while node
  31     continue_index: CFGIndex, // where to go on a `loop`
  32     break_index: CFGIndex,    // where to go on a `break
  33 }
  34
  35 pub fn construct(tcx: &ty::ctxt,
  36                  blk: &ast::Block) -> CFG {
  37     let mut graph = graph::Graph::new();
  38     let entry = graph.add_node(CFGNodeData::Entry);
  39
  40     // `fn_exit` is target of return exprs, which lies somewhere
  41     // outside input `blk`. (Distinguishing `fn_exit` and `block_exit`
  42     // also resolves chicken-and-egg problem that arises if you try to
  43     // have return exprs jump to `block_exit` during construction.)
  44     let fn_exit = graph.add_node(CFGNodeData::Exit);
  45     let block_exit;
  46
  47     let mut cfg_builder = CFGBuilder {
  48         graph: graph,
  49         fn_exit: fn_exit,
  50         tcx: tcx,
  51         loop_scopes: Vec::new()
  52     };
  53     block_exit = cfg_builder.block(blk, entry);
  54     cfg_builder.add_contained_edge(block_exit, fn_exit);
  55     let CFGBuilder {graph, ..} = cfg_builder;
  56     CFG {graph: graph,
  57          entry: entry,
  58          exit: fn_exit}
  59 }
  60
  61 impl<'a, 'tcx> CFGBuilder<'a, 'tcx> {
  62     fn block(&mut self, blk: &ast::Block, pred: CFGIndex) -> CFGIndex {
  63         let mut stmts_exit = pred;
  64         for stmt in &blk.stmts {
  65             stmts_exit = self.stmt(&**stmt, stmts_exit);
  66         }
  67
  68         let expr_exit = self.opt_expr(&blk.expr, stmts_exit);
  69
  70         self.add_ast_node(blk.id, &[expr_exit])
  71     }
  72
  73     fn stmt(&mut self, stmt: &ast::Stmt, pred: CFGIndex) -> CFGIndex {
  74         match stmt.node {
  75             ast::StmtDecl(ref decl, id) => {
  76                 let exit = self.decl(&**decl, pred);
  77                 self.add_ast_node(id, &[exit])
  78             }
  79
  80             ast::StmtExpr(ref expr, id) | ast::StmtSemi(ref expr, id) => {
  81                 let exit = self.expr(&**expr, pred);
  82                 self.add_ast_node(id, &[exit])
  83             }
  84
  85             ast::StmtMac(..) => {
  86                 self.tcx.sess.span_bug(stmt.span, "unexpanded macro");
  87             }
  88         }
  89     }
  90
  91     fn decl(&mut self, decl: &ast::Decl, pred: CFGIndex) -> CFGIndex {
  92         match decl.node {
  93             ast::DeclLocal(ref local) => {
  94                 let init_exit = self.opt_expr(&local.init, pred);
  95                 self.pat(&*local.pat, init_exit)
  96             }
  97
  98             ast::DeclItem(_) => {
  99                 pred
 100             }
 101         }
 102     }
 103
 104     fn pat(&mut self, pat: &ast::Pat, pred: CFGIndex) -> CFGIndex {
 105         match pat.node {
 106             ast::PatIdent(_, _, None) |
 107             ast::PatEnum(_, None) |
 108             ast::PatQPath(..) |
 109             ast::PatLit(..) |
 110             ast::PatRange(..) |
 111             ast::PatWild(_) => {
 112                 self.add_ast_node(pat.id, &[pred])
 113             }
 114
 115             ast::PatBox(ref subpat) |
 116             ast::PatRegion(ref subpat, _) |
 117             ast::PatIdent(_, _, Some(ref subpat)) => {
 118                 let subpat_exit = self.pat(&**subpat, pred);
 119                 self.add_ast_node(pat.id, &[subpat_exit])
 120             }
 121
 122             ast::PatEnum(_, Some(ref subpats)) |
 123             ast::PatTup(ref subpats) => {
 124                 let pats_exit = self.pats_all(subpats.iter(), pred);
 125                 self.add_ast_node(pat.id, &[pats_exit])
 126             }
 127
 128             ast::PatStruct(_, ref subpats, _) => {
 129                 let pats_exit =
 130                     self.pats_all(subpats.iter().map(|f| &f.node.pat), pred);
 131                 self.add_ast_node(pat.id, &[pats_exit])
 132             }
 133
 134             ast::PatVec(ref pre, ref vec, ref post) => {
 135                 let pre_exit = self.pats_all(pre.iter(), pred);
 136                 let vec_exit = self.pats_all(vec.iter(), pre_exit);
 137                 let post_exit = self.pats_all(post.iter(), vec_exit);
 138                 self.add_ast_node(pat.id, &[post_exit])
 139             }
 140
 141             ast::PatMac(_) => {
 142                 self.tcx.sess.span_bug(pat.span, "unexpanded macro");
 143             }
 144         }
 145     }
 146
 147     fn pats_all<'b, I: Iterator<Item=&'b P<ast::Pat>>>(&mut self,
 148                                           pats: I,
 149                                           pred: CFGIndex) -> CFGIndex {
 150         //! Handles case where all of the patterns must match.
 151         pats.fold(pred, |pred, pat| self.pat(&**pat, pred))
 152     }
 153
 154     fn expr(&mut self, expr: &ast::Expr, pred: CFGIndex) -> CFGIndex {
 155         match expr.node {
 156             ast::ExprBlock(ref blk) => {
 157                 let blk_exit = self.block(&**blk, pred);
 158                 self.add_ast_node(expr.id, &[blk_exit])
 159             }
 160
 161             ast::ExprIf(ref cond, ref then, None) => {
 162                 //
 163                 //     [pred]
 164                 //       |
 165                 //       v 1
 166                 //     [cond]
 167                 //       |
 168                 //      / \
 169                 //     /   \
 170                 //    v 2   *
 171                 //  [then]  |
 172                 //    |     |
 173                 //    v 3   v 4
 174                 //   [..expr..]
 175                 //
 176                 let cond_exit = self.expr(&**cond, pred);                // 1
 177                 let then_exit = self.block(&**then, cond_exit);          // 2
 178                 self.add_ast_node(expr.id, &[cond_exit, then_exit])      // 3,4
 179             }
 180
 181             ast::ExprIf(ref cond, ref then, Some(ref otherwise)) => {
 182                 //
 183                 //     [pred]
 184                 //       |
 185                 //       v 1
 186                 //     [cond]
 187                 //       |
 188                 //      / \
 189                 //     /   \
 190                 //    v 2   v 3
 191                 //  [then][otherwise]
 192                 //    |     |
 193                 //    v 4   v 5
 194                 //   [..expr..]
 195                 //
 196                 let cond_exit = self.expr(&**cond, pred);                // 1
 197                 let then_exit = self.block(&**then, cond_exit);          // 2
 198                 let else_exit = self.expr(&**otherwise, cond_exit);      // 3
 199                 self.add_ast_node(expr.id, &[then_exit, else_exit])      // 4, 5
 200             }
 201
 202             ast::ExprIfLet(..) => {
 203                 self.tcx.sess.span_bug(expr.span, "non-desugared ExprIfLet");
 204             }
 205
 206             ast::ExprWhile(ref cond, ref body, _) => {
 207                 //
 208                 //         [pred]
 209                 //           |
 210                 //           v 1
 211                 //       [loopback] <--+ 5
 212                 //           |         |
 213                 //           v 2       |
 214                 //   +-----[cond]      |
 215                 //   |       |         |
 216                 //   |       v 4       |
 217                 //   |     [body] -----+
 218                 //   v 3
 219                 // [expr]
 220                 //
 221                 // Note that `break` and `continue` statements
 222                 // may cause additional edges.
 223
 224                 // Is the condition considered part of the loop?
 225                 let loopback = self.add_dummy_node(&[pred]);              // 1
 226                 let cond_exit = self.expr(&**cond, loopback);             // 2
 227                 let expr_exit = self.add_ast_node(expr.id, &[cond_exit]); // 3
 228                 self.loop_scopes.push(LoopScope {
 229                     loop_id: expr.id,
 230                     continue_index: loopback,
 231                     break_index: expr_exit
 232                 });
 233                 let body_exit = self.block(&**body, cond_exit);          // 4
 234                 self.add_contained_edge(body_exit, loopback);            // 5
 235                 self.loop_scopes.pop();
 236                 expr_exit
 237             }
 238
 239             ast::ExprWhileLet(..) => {
 240                 self.tcx.sess.span_bug(expr.span, "non-desugared ExprWhileLet");
 241             }
 242
 243             ast::ExprForLoop(..) => {
 244                 self.tcx.sess.span_bug(expr.span, "non-desugared ExprForLoop");
 245             }
 246
 247             ast::ExprLoop(ref body, _) => {
 248                 //
 249                 //     [pred]
 250                 //       |
 251                 //       v 1
 252                 //   [loopback] <---+
 253                 //       |      4   |
 254                 //       v 3        |
 255                 //     [body] ------+
 256                 //
 257                 //     [expr] 2
 258                 //
 259                 // Note that `break` and `loop` statements
 260                 // may cause additional edges.
 261
 262                 let loopback = self.add_dummy_node(&[pred]);              // 1
 263                 let expr_exit = self.add_ast_node(expr.id, &[]);          // 2
 264                 self.loop_scopes.push(LoopScope {
 265                     loop_id: expr.id,
 266                     continue_index: loopback,
 267                     break_index: expr_exit,
 268                 });
 269                 let body_exit = self.block(&**body, loopback);           // 3
 270                 self.add_contained_edge(body_exit, loopback);            // 4
 271                 self.loop_scopes.pop();
 272                 expr_exit
 273             }
 274
 275             ast::ExprMatch(ref discr, ref arms, _) => {
 276                 self.match_(expr.id, &discr, &arms, pred)
 277             }
 278
 279             ast::ExprBinary(op, ref l, ref r) if ast_util::lazy_binop(op.node) => {
 280                 //
 281                 //     [pred]
 282                 //       |
 283                 //       v 1
 284                 //      [l]
 285                 //       |
 286                 //      / \
 287                 //     /   \
 288                 //    v 2  *
 289                 //   [r]   |
 290                 //    |    |
 291                 //    v 3  v 4
 292                 //   [..exit..]
 293                 //
 294                 let l_exit = self.expr(&**l, pred);                      // 1
 295                 let r_exit = self.expr(&**r, l_exit);                    // 2
 296                 self.add_ast_node(expr.id, &[l_exit, r_exit])            // 3,4
 297             }
 298
 299             ast::ExprRet(ref v) => {
 300                 let v_exit = self.opt_expr(v, pred);
 301                 let b = self.add_ast_node(expr.id, &[v_exit]);
 302                 self.add_returning_edge(expr, b);
 303                 self.add_unreachable_node()
 304             }
 305
 306             ast::ExprBreak(label) => {
 307                 let loop_scope = self.find_scope(expr, label);
 308                 let b = self.add_ast_node(expr.id, &[pred]);
 309                 self.add_exiting_edge(expr, b,
 310                                       loop_scope, loop_scope.break_index);
 311                 self.add_unreachable_node()
 312             }
 313
 314             ast::ExprAgain(label) => {
 315                 let loop_scope = self.find_scope(expr, label);
 316                 let a = self.add_ast_node(expr.id, &[pred]);
 317                 self.add_exiting_edge(expr, a,
 318                                       loop_scope, loop_scope.continue_index);
 319                 self.add_unreachable_node()
 320             }
 321
 322             ast::ExprVec(ref elems) => {
 323                 self.straightline(expr, pred, elems.iter().map(|e| &**e))
 324             }
 325
 326             ast::ExprCall(ref func, ref args) => {
 327                 self.call(expr, pred, &**func, args.iter().map(|e| &**e))
 328             }
 329
 330             ast::ExprMethodCall(_, _, ref args) => {
 331                 self.call(expr, pred, &*args[0], args[1..].iter().map(|e| &**e))
 332             }
 333
 334             ast::ExprIndex(ref l, ref r) |
 335             ast::ExprBinary(_, ref l, ref r) if self.tcx.is_method_call(expr.id) => {
 336                 self.call(expr, pred, &**l, Some(&**r).into_iter())
 337             }
 338
 339             ast::ExprRange(ref start, ref end) => {
 340                 let fields = start.as_ref().map(|e| &**e).into_iter()
 341                     .chain(end.as_ref().map(|e| &**e));
 342                 self.straightline(expr, pred, fields)
 343             }
 344
 345             ast::ExprUnary(_, ref e) if self.tcx.is_method_call(expr.id) => {
 346                 self.call(expr, pred, &**e, None::<ast::Expr>.iter())
 347             }
 348
 349             ast::ExprTup(ref exprs) => {
 350                 self.straightline(expr, pred, exprs.iter().map(|e| &**e))
 351             }
 352
 353             ast::ExprStruct(_, ref fields, ref base) => {
 354                 let field_cfg = self.straightline(expr, pred, fields.iter().map(|f| &*f.expr));
 355                 self.opt_expr(base, field_cfg)
 356             }
 357
 358             ast::ExprRepeat(ref elem, ref count) => {
 359                 self.straightline(expr, pred, [elem, count].iter().map(|&e| &**e))
 360             }
 361
 362             ast::ExprAssign(ref l, ref r) |
 363             ast::ExprAssignOp(_, ref l, ref r) => {
 364                 self.straightline(expr, pred, [r, l].iter().map(|&e| &**e))
 365             }
 366
 367             ast::ExprBox(Some(ref l), ref r) |
 368             ast::ExprIndex(ref l, ref r) |
 369             ast::ExprBinary(_, ref l, ref r) => { // NB: && and || handled earlier
 370                 self.straightline(expr, pred, [l, r].iter().map(|&e| &**e))
 371             }
 372
 373             ast::ExprBox(None, ref e) |
 374             ast::ExprAddrOf(_, ref e) |
 375             ast::ExprCast(ref e, _) |
 376             ast::ExprUnary(_, ref e) |
 377             ast::ExprParen(ref e) |
 378             ast::ExprField(ref e, _) |
 379             ast::ExprTupField(ref e, _) => {
 380                 self.straightline(expr, pred, Some(&**e).into_iter())
 381             }
 382
 383             ast::ExprInlineAsm(ref inline_asm) => {
 384                 let inputs = inline_asm.inputs.iter();
 385                 let outputs = inline_asm.outputs.iter();
 386                 let post_inputs = self.exprs(inputs.map(|a| {
 387                     debug!("cfg::construct InlineAsm id:{} input:{:?}", expr.id, a);
 388                     let &(_, ref expr) = a;
 389                     &**expr
 390                 }), pred);
 391                 let post_outputs = self.exprs(outputs.map(|a| {
 392                     debug!("cfg::construct InlineAsm id:{} output:{:?}", expr.id, a);
 393                     let &(_, ref expr, _) = a;
 394                     &**expr
 395                 }), post_inputs);
 396                 self.add_ast_node(expr.id, &[post_outputs])
 397             }
 398
 399             ast::ExprMac(..) |
 400             ast::ExprClosure(..) |
 401             ast::ExprLit(..) |
 402             ast::ExprPath(..) => {
 403                 self.straightline(expr, pred, None::<ast::Expr>.iter())
 404             }
 405         }
 406     }
 407
 408     fn call<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
 409             call_expr: &ast::Expr,
 410             pred: CFGIndex,
 411             func_or_rcvr: &ast::Expr,
 412             args: I) -> CFGIndex {
 413         let method_call = ty::MethodCall::expr(call_expr.id);
 414         let fn_ty = match self.tcx.tables.borrow().method_map.get(&method_call) {
 415             Some(method) => method.ty,
 416             None => self.tcx.expr_ty_adjusted(func_or_rcvr)
 417         };
 418
 419         let func_or_rcvr_exit = self.expr(func_or_rcvr, pred);
 420         let ret = self.straightline(call_expr, func_or_rcvr_exit, args);
 421         if fn_ty.fn_ret().diverges() {
 422             self.add_unreachable_node()
 423         } else {
 424             ret
 425         }
 426     }
 427
 428     fn exprs<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
 429                                              exprs: I,
 430                                              pred: CFGIndex) -> CFGIndex {
 431         //! Constructs graph for `exprs` evaluated in order
 432         exprs.fold(pred, |p, e| self.expr(e, p))
 433     }
 434
 435     fn opt_expr(&mut self,
 436                 opt_expr: &Option<P<ast::Expr>>,
 437                 pred: CFGIndex) -> CFGIndex {
 438         //! Constructs graph for `opt_expr` evaluated, if Some
 439         opt_expr.iter().fold(pred, |p, e| self.expr(&**e, p))
 440     }
 441
 442     fn straightline<'b, I: Iterator<Item=&'b ast::Expr>>(&mut self,
 443                     expr: &ast::Expr,
 444                     pred: CFGIndex,
 445                     subexprs: I) -> CFGIndex {
 446         //! Handles case of an expression that evaluates `subexprs` in order
 447
 448         let subexprs_exit = self.exprs(subexprs, pred);
 449         self.add_ast_node(expr.id, &[subexprs_exit])
 450     }
 451
 452     fn match_(&mut self, id: ast::NodeId, discr: &ast::Expr,
 453               arms: &[ast::Arm], pred: CFGIndex) -> CFGIndex {
 454         // The CFG for match expression is quite complex, so no ASCII
 455         // art for it (yet).
 456         //
 457         // The CFG generated below matches roughly what trans puts
 458         // out. Each pattern and guard is visited in parallel, with
 459         // arms containing multiple patterns generating multiple nodes
 460         // for the same guard expression. The guard expressions chain
 461         // into each other from top to bottom, with a specific
 462         // exception to allow some additional valid programs
 463         // (explained below). Trans differs slightly in that the
 464         // pattern matching may continue after a guard but the visible
 465         // behaviour should be the same.
 466         //
 467         // What is going on is explained in further comments.
 468
 469         // Visit the discriminant expression
 470         let discr_exit = self.expr(discr, pred);
 471
 472         // Add a node for the exit of the match expression as a whole.
 473         let expr_exit = self.add_ast_node(id, &[]);
 474
 475         // Keep track of the previous guard expressions
 476         let mut prev_guards = Vec::new();
 477         // Track if the previous pattern contained bindings or wildcards
 478         let mut prev_has_bindings = false;
 479
 480         for arm in arms {
 481             // Add an exit node for when we've visited all the
 482             // patterns and the guard (if there is one) in the arm.
 483             let arm_exit = self.add_dummy_node(&[]);
 484
 485             for pat in &arm.pats {
 486                 // Visit the pattern, coming from the discriminant exit
 487                 let mut pat_exit = self.pat(&**pat, discr_exit);
 488
 489                 // If there is a guard expression, handle it here
 490                 if let Some(ref guard) = arm.guard {
 491                     // Add a dummy node for the previous guard
 492                     // expression to target
 493                     let guard_start = self.add_dummy_node(&[pat_exit]);
 494                     // Visit the guard expression
 495                     let guard_exit = self.expr(&**guard, guard_start);
 496
 497                     let this_has_bindings = pat_util::pat_contains_bindings_or_wild(
 498                         &self.tcx.def_map, &**pat);
 499
 500                     // If both this pattern and the previous pattern
 501                     // were free of bindings, they must consist only
 502                     // of "constant" patterns. Note we cannot match an
 503                     // all-constant pattern, fail the guard, and then
 504                     // match *another* all-constant pattern. This is
 505                     // because if the previous pattern matches, then
 506                     // we *cannot* match this one, unless all the
 507                     // constants are the same (which is rejected by
 508                     // `check_match`).
 509                     //
 510                     // We can use this to be smarter about the flow
 511                     // along guards. If the previous pattern matched,
 512                     // then we know we will not visit the guard in
 513                     // this one (whether or not the guard succeeded),
 514                     // if the previous pattern failed, then we know
 515                     // the guard for that pattern will not have been
 516                     // visited. Thus, it is not possible to visit both
 517                     // the previous guard and the current one when
 518                     // both patterns consist only of constant
 519                     // sub-patterns.
 520                     //
 521                     // However, if the above does not hold, then all
 522                     // previous guards need to be wired to visit the
 523                     // current guard pattern.
 524                     if prev_has_bindings || this_has_bindings {
 525                         while let Some(prev) = prev_guards.pop() {
 526                             self.add_contained_edge(prev, guard_start);
 527                         }
 528                     }
 529
 530                     prev_has_bindings = this_has_bindings;
 531
 532                     // Push the guard onto the list of previous guards
 533                     prev_guards.push(guard_exit);
 534
 535                     // Update the exit node for the pattern
 536                     pat_exit = guard_exit;
 537                 }
 538
 539                 // Add an edge from the exit of this pattern to the
 540                 // exit of the arm
 541                 self.add_contained_edge(pat_exit, arm_exit);
 542             }
 543
 544             // Visit the body of this arm
 545             let body_exit = self.expr(&arm.body, arm_exit);
 546
 547             // Link the body to the exit of the expression
 548             self.add_contained_edge(body_exit, expr_exit);
 549         }
 550
 551         expr_exit
 552     }
 553
 554     fn add_dummy_node(&mut self, preds: &[CFGIndex]) -> CFGIndex {
 555         self.add_node(CFGNodeData::Dummy, preds)
 556     }
 557
 558     fn add_ast_node(&mut self, id: ast::NodeId, preds: &[CFGIndex]) -> CFGIndex {
 559         assert!(id != ast::DUMMY_NODE_ID);
 560         self.add_node(CFGNodeData::AST(id), preds)
 561     }
 562
 563     fn add_unreachable_node(&mut self) -> CFGIndex {
 564         self.add_node(CFGNodeData::Unreachable, &[])
 565     }
 566
 567     fn add_node(&mut self, data: CFGNodeData, preds: &[CFGIndex]) -> CFGIndex {
 568         let node = self.graph.add_node(data);
 569         for &pred in preds {
 570             self.add_contained_edge(pred, node);
 571         }
 572         node
 573     }
 574
 575     fn add_contained_edge(&mut self,
 576                           source: CFGIndex,
 577                           target: CFGIndex) {
 578         let data = CFGEdgeData {exiting_scopes: vec!() };
 579         self.graph.add_edge(source, target, data);
 580     }
 581
 582     fn add_exiting_edge(&mut self,
 583                         from_expr: &ast::Expr,
 584                         from_index: CFGIndex,
 585                         to_loop: LoopScope,
 586                         to_index: CFGIndex) {
 587         let mut data = CFGEdgeData {exiting_scopes: vec!() };
 588         let mut scope = CodeExtent::from_node_id(from_expr.id);
 589         let target_scope = CodeExtent::from_node_id(to_loop.loop_id);
 590         while scope != target_scope {
 591
 592             data.exiting_scopes.push(scope.node_id());
 593             scope = self.tcx.region_maps.encl_scope(scope);
 594         }
 595         self.graph.add_edge(from_index, to_index, data);
 596     }
 597
 598     fn add_returning_edge(&mut self,
 599                           _from_expr: &ast::Expr,
 600                           from_index: CFGIndex) {
 601         let mut data = CFGEdgeData {
 602             exiting_scopes: vec!(),
 603         };
 604         for &LoopScope { loop_id: id, .. } in self.loop_scopes.iter().rev() {
 605             data.exiting_scopes.push(id);
 606         }
 607         self.graph.add_edge(from_index, self.fn_exit, data);
 608     }
 609
 610     fn find_scope(&self,
 611                   expr: &ast::Expr,
 612                   label: Option<ast::Ident>) -> LoopScope {
 613         if label.is_none() {
 614             return *self.loop_scopes.last().unwrap();
 615         }
 616
 617         match self.tcx.def_map.borrow().get(&expr.id).map(|d| d.full_def()) {
 618             Some(def::DefLabel(loop_id)) => {
 619                 for l in &self.loop_scopes {
 620                     if l.loop_id == loop_id {
 621                         return *l;
 622                     }
 623                 }
 624                 self.tcx.sess.span_bug(expr.span,
 625                     &format!("no loop scope for id {}", loop_id));
 626             }
 627
 628             r => {
 629                 self.tcx.sess.span_bug(expr.span,
 630                     &format!("bad entry `{:?}` in def_map for label", r));
 631             }
 632         }
 633     }
 634 }