src/librustc_mir/build/scope.rs

   1 // Copyright 2015 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 /*!
  12 Managing the scope stack. The scopes are tied to lexical scopes, so as
  13 we descend the HAIR, we push a scope on the stack, translate ite
  14 contents, and then pop it off. Every scope is named by a
  15 `CodeExtent`.
  16
  17 ### SEME Regions
  18
  19 When pushing a new scope, we record the current point in the graph (a
  20 basic block); this marks the entry to the scope. We then generate more
  21 stuff in the control-flow graph. Whenever the scope is exited, either
  22 via a `break` or `return` or just by fallthrough, that marks an exit
  23 from the scope. Each lexical scope thus corresponds to a single-entry,
  24 multiple-exit (SEME) region in the control-flow graph.
  25
  26 For now, we keep a mapping from each `CodeExtent` to its
  27 corresponding SEME region for later reference (see caveat in next
  28 paragraph). This is because region scopes are tied to
  29 them. Eventually, when we shift to non-lexical lifetimes, three should
  30 be no need to remember this mapping.
  31
  32 There is one additional wrinkle, actually, that I wanted to hide from
  33 you but duty compels me to mention. In the course of translating
  34 matches, it sometimes happen that certain code (namely guards) gets
  35 executed multiple times. This means that the scope lexical scope may
  36 in fact correspond to multiple, disjoint SEME regions. So in fact our
  37 mapping os from one scope to a vector of SEME regions.
  38
  39 ### Drops
  40
  41 The primary purpose for scopes is to insert drops: while translating
  42 the contents, we also accumulate lvalues that need to be dropped upon
  43 exit from each scope. This is done by calling `schedule_drop`. Once a
  44 drop is scheduled, whenever we branch out we will insert drops of all
  45 those lvalues onto the outgoing edge. Note that we don't know the full
  46 set of scheduled drops up front, and so whenever we exit from the
  47 scope we only drop the values scheduled thus far. For example, consider
  48 the scope S corresponding to this loop:
  49
  50 ```
  51 loop {
  52     let x = ...;
  53     if cond { break; }
  54     let y = ...;
  55 }
  56 ```
  57
  58 When processing the `let x`, we will add one drop to the scope for
  59 `x`.  The break will then insert a drop for `x`. When we process `let
  60 y`, we will add another drop (in fact, to a subscope, but let's ignore
  61 that for now); any later drops would also drop `y`.
  62
  63 ### Early exit
  64
  65 There are numerous "normal" ways to early exit a scope: `break`,
  66 `continue`, `return` (panics are handled separately). Whenever an
  67 early exit occurs, the method `exit_scope` is called. It is given the
  68 current point in execution where the early exit occurs, as well as the
  69 scope you want to branch to (note that all early exits from to some
  70 other enclosing scope). `exit_scope` will record thid exit point and
  71 also add all drops.
  72
  73 Panics are handled in a similar fashion, except that a panic always
  74 returns out to the `DIVERGE_BLOCK`. To trigger a panic, simply call
  75 `panic(p)` with the current point `p`. Or else you can call
  76 `diverge_cleanup`, which will produce a block that you can branch to
  77 which does the appropriate cleanup and then diverges. `panic(p)`
  78 simply calls `diverge_cleanup()` and adds an edge from `p` to the
  79 result.
  80
  81 ### Loop scopes
  82
  83 In addition to the normal scope stack, we track a loop scope stack
  84 that contains only loops. It tracks where a `break` and `continue`
  85 should go to.
  86
  87 */
  88
  89 use build::{BlockAnd, Builder, CFG};
  90 use repr::*;
  91 use rustc::middle::region::CodeExtent;
  92 use rustc::middle::ty::Ty;
  93 use syntax::codemap::Span;
  94
  95 pub struct Scope<'tcx> {
  96     extent: CodeExtent,
  97     exits: Vec<ExecutionPoint>,
  98     drops: Vec<(DropKind, Span, Lvalue<'tcx>)>,
  99     cached_block: Option<BasicBlock>,
 100 }
 101
 102 #[derive(Clone, Debug)]
 103 pub struct LoopScope {
 104     pub extent: CodeExtent, // extent of the loop
 105     pub continue_block: BasicBlock, // where to go on a `loop`
 106     pub break_block: BasicBlock, // where to go on a `break
 107 }
 108
 109 impl<'a,'tcx> Builder<'a,'tcx> {
 110     /// Start a loop scope, which tracks where `continue` and `break`
 111     /// should branch to. See module comment for more details.
 112     pub fn in_loop_scope<F, R>(&mut self,
 113                                loop_block: BasicBlock,
 114                                break_block: BasicBlock,
 115                                f: F)
 116                                -> BlockAnd<R>
 117         where F: FnOnce(&mut Builder<'a, 'tcx>) -> BlockAnd<R>
 118     {
 119         let extent = self.extent_of_innermost_scope().unwrap();
 120         let loop_scope = LoopScope {
 121             extent: extent.clone(),
 122             continue_block: loop_block,
 123             break_block: break_block,
 124         };
 125         self.loop_scopes.push(loop_scope);
 126         let r = f(self);
 127         assert!(self.loop_scopes.pop().unwrap().extent == extent);
 128         r
 129     }
 130
 131     /// Start a scope. The closure `f` should translate the contents
 132     /// of the scope. See module comment for more details.
 133     pub fn in_scope<F, R>(&mut self, extent: CodeExtent, block: BasicBlock, f: F) -> BlockAnd<R>
 134         where F: FnOnce(&mut Builder<'a, 'tcx>) -> BlockAnd<R>
 135     {
 136         debug!("in_scope(extent={:?}, block={:?})", extent, block);
 137
 138         let start_point = self.cfg.end_point(block);
 139
 140         // push scope, execute `f`, then pop scope again
 141         self.scopes.push(Scope {
 142             extent: extent.clone(),
 143             drops: vec![],
 144             exits: vec![],
 145             cached_block: None,
 146         });
 147         let BlockAnd(fallthrough_block, rv) = f(self);
 148         let mut scope = self.scopes.pop().unwrap();
 149
 150         // add in any drops needed on the fallthrough path (any other
 151         // exiting paths, such as those that arise from `break`, will
 152         // have drops already)
 153         for (kind, span, lvalue) in scope.drops {
 154             self.cfg.push_drop(fallthrough_block, span, kind, &lvalue);
 155         }
 156
 157         // add the implicit fallthrough edge
 158         scope.exits.push(self.cfg.end_point(fallthrough_block));
 159
 160         // compute the extent from start to finish and store it in the graph
 161         let graph_extent = self.graph_extent(start_point, scope.exits);
 162         self.extents.entry(extent)
 163                     .or_insert(vec![])
 164                     .push(graph_extent);
 165
 166         debug!("in_scope: exiting extent={:?} fallthrough_block={:?}", extent, fallthrough_block);
 167         fallthrough_block.and(rv)
 168     }
 169
 170     /// Creates a graph extent (SEME region) from an entry point and
 171     /// exit points.
 172     fn graph_extent(&self, entry: ExecutionPoint, exits: Vec<ExecutionPoint>) -> GraphExtent {
 173         if exits.len() == 1 && entry.block == exits[0].block {
 174             GraphExtent {
 175                 entry: entry,
 176                 exit: GraphExtentExit::Statement(exits[0].statement),
 177             }
 178         } else {
 179             GraphExtent {
 180                 entry: entry,
 181                 exit: GraphExtentExit::Points(exits),
 182             }
 183         }
 184     }
 185
 186     /// Finds the loop scope for a given label. This is used for
 187     /// resolving `break` and `continue`.
 188     pub fn find_loop_scope(&mut self,
 189                            span: Span,
 190                            label: Option<CodeExtent>)
 191                            -> LoopScope {
 192         let loop_scope =
 193             match label {
 194                 None => {
 195                     // no label? return the innermost loop scope
 196                     self.loop_scopes.iter()
 197                                     .rev()
 198                                     .next()
 199                 }
 200                 Some(label) => {
 201                     // otherwise, find the loop-scope with the correct id
 202                     self.loop_scopes.iter()
 203                                     .rev()
 204                                     .filter(|loop_scope| loop_scope.extent == label)
 205                                     .next()
 206                 }
 207             };
 208
 209         match loop_scope {
 210             Some(loop_scope) => loop_scope.clone(),
 211             None => self.hir.span_bug(span, "no enclosing loop scope found?"),
 212         }
 213     }
 214
 215     /// Branch out of `block` to `target`, exiting all scopes up to
 216     /// and including `extent`.  This will insert whatever drops are
 217     /// needed, as well as tracking this exit for the SEME region. See
 218     /// module comment for details.
 219     pub fn exit_scope(&mut self,
 220                       span: Span,
 221                       extent: CodeExtent,
 222                       block: BasicBlock,
 223                       target: BasicBlock) {
 224         let popped_scopes =
 225             match self.scopes.iter().rev().position(|scope| scope.extent == extent) {
 226                 Some(p) => p + 1,
 227                 None => self.hir.span_bug(span, &format!("extent {:?} does not enclose",
 228                                                               extent)),
 229             };
 230
 231         for scope in self.scopes.iter_mut().rev().take(popped_scopes) {
 232             for &(kind, drop_span, ref lvalue) in &scope.drops {
 233                 self.cfg.push_drop(block, drop_span, kind, lvalue);
 234             }
 235
 236             scope.exits.push(self.cfg.end_point(block));
 237         }
 238
 239         self.cfg.terminate(block, Terminator::Goto { target: target });
 240     }
 241
 242     /// Creates a path that performs all required cleanup for
 243     /// unwinding. This path terminates in DIVERGE. Returns the start
 244     /// of the path. See module comment for more details.
 245     pub fn diverge_cleanup(&mut self) -> BasicBlock {
 246         diverge_cleanup_helper(&mut self.cfg, &mut self.scopes)
 247     }
 248
 249     /// Create diverge cleanup and branch to it from `block`.
 250     pub fn panic(&mut self, block: BasicBlock) {
 251         let cleanup = self.diverge_cleanup();
 252         self.cfg.terminate(block, Terminator::Panic { target: cleanup });
 253     }
 254
 255     /// Indicates that `lvalue` should be dropped on exit from
 256     /// `extent`.
 257     pub fn schedule_drop(&mut self,
 258                          span: Span,
 259                          extent: CodeExtent,
 260                          kind: DropKind,
 261                          lvalue: &Lvalue<'tcx>,
 262                          lvalue_ty: Ty<'tcx>) {
 263         if self.hir.needs_drop(lvalue_ty, span) {
 264             match self.scopes.iter_mut().rev().find(|s| s.extent == extent) {
 265                 Some(scope) => {
 266                     scope.drops.push((kind, span, lvalue.clone()));
 267                     scope.cached_block = None;
 268                 }
 269                 None => self.hir.span_bug(span, &format!("extent {:?} not in scope to drop {:?}",
 270                                                          extent, lvalue)),
 271             }
 272         }
 273     }
 274
 275     pub fn extent_of_innermost_scope(&self) -> Option<CodeExtent> {
 276         self.scopes.last().map(|scope| scope.extent)
 277     }
 278
 279     pub fn extent_of_outermost_scope(&self) -> Option<CodeExtent> {
 280         self.scopes.first().map(|scope| scope.extent)
 281     }
 282 }
 283
 284 fn diverge_cleanup_helper<'tcx>(cfg: &mut CFG<'tcx>, scopes: &mut [Scope<'tcx>]) -> BasicBlock {
 285     let len = scopes.len();
 286
 287     if len == 0 {
 288         return DIVERGE_BLOCK;
 289     }
 290
 291     let (remaining, scope) = scopes.split_at_mut(len - 1);
 292     let scope = &mut scope[0];
 293
 294     if let Some(b) = scope.cached_block {
 295         return b;
 296     }
 297
 298     let block = cfg.start_new_block();
 299     for &(kind, span, ref lvalue) in &scope.drops {
 300         cfg.push_drop(block, span, kind, lvalue);
 301     }
 302     scope.cached_block = Some(block);
 303
 304     let remaining_cleanup_block = diverge_cleanup_helper(cfg, remaining);
 305     cfg.terminate(block, Terminator::Goto { target: remaining_cleanup_block });
 306     block
 307 }