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.
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.
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
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.
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.
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.
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:
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`.
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
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
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`
89 use build::{BlockAnd, Builder, CFG};
91 use rustc::middle::region::CodeExtent;
92 use rustc::middle::ty::Ty;
93 use syntax::codemap::Span;
95 pub struct Scope<'tcx> {
97 exits: Vec<ExecutionPoint>,
98 drops: Vec<(DropKind, Span, Lvalue<'tcx>)>,
99 cached_block: Option<BasicBlock>,
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
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,
117 where F: FnOnce(&mut Builder<'a, 'tcx>) -> BlockAnd<R>
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,
125 self.loop_scopes.push(loop_scope);
127 assert!(self.loop_scopes.pop().unwrap().extent == extent);
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>
136 debug!("in_scope(extent={:?}, block={:?})", extent, block);
138 let start_point = self.cfg.end_point(block);
140 // push scope, execute `f`, then pop scope again
141 self.scopes.push(Scope {
142 extent: extent.clone(),
147 let BlockAnd(fallthrough_block, rv) = f(self);
148 let mut scope = self.scopes.pop().unwrap();
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);
157 // add the implicit fallthrough edge
158 scope.exits.push(self.cfg.end_point(fallthrough_block));
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)
166 debug!("in_scope: exiting extent={:?} fallthrough_block={:?}", extent, fallthrough_block);
167 fallthrough_block.and(rv)
170 /// Creates a graph extent (SEME region) from an entry point and
172 fn graph_extent(&self, entry: ExecutionPoint, exits: Vec<ExecutionPoint>) -> GraphExtent {
173 if exits.len() == 1 && entry.block == exits[0].block {
176 exit: GraphExtentExit::Statement(exits[0].statement),
181 exit: GraphExtentExit::Points(exits),
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,
190 label: Option<CodeExtent>)
195 // no label? return the innermost loop scope
196 self.loop_scopes.iter()
201 // otherwise, find the loop-scope with the correct id
202 self.loop_scopes.iter()
204 .filter(|loop_scope| loop_scope.extent == label)
210 Some(loop_scope) => loop_scope.clone(),
211 None => self.hir.span_bug(span, "no enclosing loop scope found?"),
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,
223 target: BasicBlock) {
225 match self.scopes.iter().rev().position(|scope| scope.extent == extent) {
227 None => self.hir.span_bug(span, &format!("extent {:?} does not enclose",
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);
236 scope.exits.push(self.cfg.end_point(block));
239 self.cfg.terminate(block, Terminator::Goto { target: target });
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)
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 });
255 /// Indicates that `lvalue` should be dropped on exit from
257 pub fn schedule_drop(&mut self,
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) {
266 scope.drops.push((kind, span, lvalue.clone()));
267 scope.cached_block = None;
269 None => self.hir.span_bug(span, &format!("extent {:?} not in scope to drop {:?}",
275 pub fn extent_of_innermost_scope(&self) -> Option<CodeExtent> {
276 self.scopes.last().map(|scope| scope.extent)
279 pub fn extent_of_outermost_scope(&self) -> Option<CodeExtent> {
280 self.scopes.first().map(|scope| scope.extent)
284 fn diverge_cleanup_helper<'tcx>(cfg: &mut CFG<'tcx>, scopes: &mut [Scope<'tcx>]) -> BasicBlock {
285 let len = scopes.len();
288 return DIVERGE_BLOCK;
291 let (remaining, scope) = scopes.split_at_mut(len - 1);
292 let scope = &mut scope[0];
294 if let Some(b) = scope.cached_block {
298 let block = cfg.start_new_block();
299 for &(kind, span, ref lvalue) in &scope.drops {
300 cfg.push_drop(block, span, kind, lvalue);
302 scope.cached_block = Some(block);
304 let remaining_cleanup_block = diverge_cleanup_helper(cfg, remaining);
305 cfg.terminate(block, Terminator::Goto { target: remaining_cleanup_block });