]>
Commit | Line | Data |
---|---|---|
1a4d82fc | 1 | // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT |
223e47cc LB |
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 | ||
1a4d82fc JJ |
11 | //! This file actually contains two passes related to regions. The first |
12 | //! pass builds up the `scope_map`, which describes the parent links in | |
13 | //! the region hierarchy. The second pass infers which types must be | |
14 | //! region parameterized. | |
15 | //! | |
16 | //! Most of the documentation on regions can be found in | |
9cc50fc6 | 17 | //! `middle/infer/region_inference/README.md` |
1a4d82fc | 18 | |
7453a54e | 19 | use dep_graph::DepNode; |
54a0048b | 20 | use hir::map as ast_map; |
1a4d82fc | 21 | use session::Session; |
e9174d1e | 22 | use util::nodemap::{FnvHashMap, NodeMap, NodeSet}; |
92a42be0 | 23 | use middle::cstore::InlinedItem; |
54a0048b | 24 | use ty; |
1a4d82fc JJ |
25 | |
26 | use std::cell::RefCell; | |
e9174d1e SL |
27 | use std::collections::hash_map::Entry; |
28 | use std::fmt; | |
29 | use std::mem; | |
85aaf69f | 30 | use syntax::codemap::{self, Span}; |
e9174d1e SL |
31 | use syntax::ast::{self, NodeId}; |
32 | ||
54a0048b SL |
33 | use hir; |
34 | use hir::intravisit::{self, Visitor, FnKind}; | |
35 | use hir::{Block, Item, FnDecl, Arm, Pat, PatKind, Stmt, Expr, Local}; | |
e9174d1e SL |
36 | |
37 | #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable, | |
38 | RustcDecodable, Copy)] | |
39 | pub struct CodeExtent(u32); | |
40 | ||
41 | impl fmt::Debug for CodeExtent { | |
42 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
54a0048b | 43 | write!(f, "CodeExtent({:?}", self.0)?; |
e9174d1e | 44 | |
54a0048b | 45 | ty::tls::with_opt(|opt_tcx| { |
e9174d1e | 46 | if let Some(tcx) = opt_tcx { |
54a0048b SL |
47 | if let Some(data) = tcx.region_maps.code_extents.borrow().get(self.0 as usize) { |
48 | write!(f, "/{:?}", data)?; | |
49 | } | |
e9174d1e SL |
50 | } |
51 | Ok(()) | |
54a0048b | 52 | })?; |
e9174d1e SL |
53 | |
54 | write!(f, ")") | |
55 | } | |
56 | } | |
57 | ||
58 | /// The root of everything. I should be using NonZero or profiling | |
59 | /// instead of this (probably). | |
60 | pub const ROOT_CODE_EXTENT : CodeExtent = CodeExtent(0); | |
61 | /// A placeholder used in trans to stand for real code extents | |
62 | pub const DUMMY_CODE_EXTENT : CodeExtent = CodeExtent(1); | |
223e47cc | 63 | |
1a4d82fc JJ |
64 | /// CodeExtent represents a statically-describable extent that can be |
65 | /// used to bound the lifetime/region for values. | |
66 | /// | |
85aaf69f SL |
67 | /// `Misc(node_id)`: Any AST node that has any extent at all has the |
68 | /// `Misc(node_id)` extent. Other variants represent special cases not | |
69 | /// immediately derivable from the abstract syntax tree structure. | |
70 | /// | |
71 | /// `DestructionScope(node_id)` represents the extent of destructors | |
72 | /// implicitly-attached to `node_id` that run immediately after the | |
73 | /// expression for `node_id` itself. Not every AST node carries a | |
74 | /// `DestructionScope`, but those that are `terminating_scopes` do; | |
75 | /// see discussion with `RegionMaps`. | |
76 | /// | |
77 | /// `Remainder(BlockRemainder { block, statement_index })` represents | |
78 | /// the extent of user code running immediately after the initializer | |
79 | /// expression for the indexed statement, until the end of the block. | |
80 | /// | |
81 | /// So: the following code can be broken down into the extents beneath: | |
82 | /// ``` | |
83 | /// let a = f().g( 'b: { let x = d(); let y = d(); x.h(y) } ) ; | |
84 | /// ``` | |
85 | /// | |
86 | /// +-+ (D12.) | |
87 | /// +-+ (D11.) | |
88 | /// +---------+ (R10.) | |
89 | /// +-+ (D9.) | |
90 | /// +----------+ (M8.) | |
91 | /// +----------------------+ (R7.) | |
92 | /// +-+ (D6.) | |
93 | /// +----------+ (M5.) | |
94 | /// +-----------------------------------+ (M4.) | |
95 | /// +--------------------------------------------------+ (M3.) | |
96 | /// +--+ (M2.) | |
97 | /// +-----------------------------------------------------------+ (M1.) | |
98 | /// | |
99 | /// (M1.): Misc extent of the whole `let a = ...;` statement. | |
100 | /// (M2.): Misc extent of the `f()` expression. | |
101 | /// (M3.): Misc extent of the `f().g(..)` expression. | |
102 | /// (M4.): Misc extent of the block labelled `'b:`. | |
103 | /// (M5.): Misc extent of the `let x = d();` statement | |
104 | /// (D6.): DestructionScope for temporaries created during M5. | |
105 | /// (R7.): Remainder extent for block `'b:`, stmt 0 (let x = ...). | |
106 | /// (M8.): Misc Extent of the `let y = d();` statement. | |
107 | /// (D9.): DestructionScope for temporaries created during M8. | |
108 | /// (R10.): Remainder extent for block `'b:`, stmt 1 (let y = ...). | |
109 | /// (D11.): DestructionScope for temporaries and bindings from block `'b:`. | |
110 | /// (D12.): DestructionScope for temporaries created during M1 (e.g. f()). | |
111 | /// | |
112 | /// Note that while the above picture shows the destruction scopes | |
113 | /// as following their corresponding misc extents, in the internal | |
114 | /// data structures of the compiler the destruction scopes are | |
115 | /// represented as enclosing parents. This is sound because we use the | |
116 | /// enclosing parent relationship just to ensure that referenced | |
117 | /// values live long enough; phrased another way, the starting point | |
118 | /// of each range is not really the important thing in the above | |
119 | /// picture, but rather the ending point. | |
120 | /// | |
1a4d82fc JJ |
121 | /// FIXME (pnkfelix): This currently derives `PartialOrd` and `Ord` to |
122 | /// placate the same deriving in `ty::FreeRegion`, but we may want to | |
123 | /// actually attach a more meaningful ordering to scopes than the one | |
124 | /// generated via deriving here. | |
e9174d1e SL |
125 | #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, Debug, Copy)] |
126 | pub enum CodeExtentData { | |
85aaf69f | 127 | Misc(ast::NodeId), |
9346a6ac | 128 | |
9cc50fc6 SL |
129 | // extent of the call-site for a function or closure (outlives |
130 | // the parameters as well as the body). | |
131 | CallSiteScope { fn_id: ast::NodeId, body_id: ast::NodeId }, | |
132 | ||
9346a6ac AL |
133 | // extent of parameters passed to a function or closure (they |
134 | // outlive its body) | |
135 | ParameterScope { fn_id: ast::NodeId, body_id: ast::NodeId }, | |
136 | ||
137 | // extent of destructors for temporaries of node-id | |
138 | DestructionScope(ast::NodeId), | |
139 | ||
140 | // extent of code following a `let id = expr;` binding in a block | |
85aaf69f SL |
141 | Remainder(BlockRemainder) |
142 | } | |
143 | ||
9cc50fc6 | 144 | /// extent of call-site for a function/method. |
85aaf69f SL |
145 | #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable, |
146 | RustcDecodable, Debug, Copy)] | |
9cc50fc6 SL |
147 | pub struct CallSiteScopeData { |
148 | pub fn_id: ast::NodeId, pub body_id: ast::NodeId, | |
85aaf69f SL |
149 | } |
150 | ||
9cc50fc6 | 151 | impl CallSiteScopeData { |
e9174d1e SL |
152 | pub fn to_code_extent(&self, region_maps: &RegionMaps) -> CodeExtent { |
153 | region_maps.lookup_code_extent( | |
9cc50fc6 SL |
154 | match *self { |
155 | CallSiteScopeData { fn_id, body_id } => | |
156 | CodeExtentData::CallSiteScope { fn_id: fn_id, body_id: body_id }, | |
157 | }) | |
85aaf69f SL |
158 | } |
159 | } | |
160 | ||
161 | /// Represents a subscope of `block` for a binding that is introduced | |
162 | /// by `block.stmts[first_statement_index]`. Such subscopes represent | |
163 | /// a suffix of the block. Note that each subscope does not include | |
164 | /// the initializer expression, if any, for the statement indexed by | |
165 | /// `first_statement_index`. | |
166 | /// | |
167 | /// For example, given `{ let (a, b) = EXPR_1; let c = EXPR_2; ... }`: | |
168 | /// | |
169 | /// * the subscope with `first_statement_index == 0` is scope of both | |
170 | /// `a` and `b`; it does not include EXPR_1, but does include | |
171 | /// everything after that first `let`. (If you want a scope that | |
e9174d1e | 172 | /// includes EXPR_1 as well, then do not use `CodeExtentData::Remainder`, |
85aaf69f | 173 | /// but instead another `CodeExtent` that encompasses the whole block, |
e9174d1e | 174 | /// e.g. `CodeExtentData::Misc`. |
85aaf69f SL |
175 | /// |
176 | /// * the subscope with `first_statement_index == 1` is scope of `c`, | |
177 | /// and thus does not include EXPR_2, but covers the `...`. | |
178 | #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable, | |
179 | RustcDecodable, Debug, Copy)] | |
180 | pub struct BlockRemainder { | |
181 | pub block: ast::NodeId, | |
e9174d1e | 182 | pub first_statement_index: u32, |
1a4d82fc | 183 | } |
223e47cc | 184 | |
e9174d1e | 185 | impl CodeExtentData { |
1a4d82fc JJ |
186 | /// Returns a node id associated with this scope. |
187 | /// | |
188 | /// NB: likely to be replaced as API is refined; e.g. pnkfelix | |
189 | /// anticipates `fn entry_node_id` and `fn each_exit_node_id`. | |
190 | pub fn node_id(&self) -> ast::NodeId { | |
191 | match *self { | |
e9174d1e | 192 | CodeExtentData::Misc(node_id) => node_id, |
9346a6ac AL |
193 | |
194 | // These cases all return rough approximations to the | |
195 | // precise extent denoted by `self`. | |
e9174d1e SL |
196 | CodeExtentData::Remainder(br) => br.block, |
197 | CodeExtentData::DestructionScope(node_id) => node_id, | |
9cc50fc6 | 198 | CodeExtentData::CallSiteScope { fn_id: _, body_id } | |
e9174d1e | 199 | CodeExtentData::ParameterScope { fn_id: _, body_id } => body_id, |
1a4d82fc JJ |
200 | } |
201 | } | |
e9174d1e | 202 | } |
223e47cc | 203 | |
e9174d1e SL |
204 | impl CodeExtent { |
205 | #[inline] | |
206 | fn into_option(self) -> Option<CodeExtent> { | |
207 | if self == ROOT_CODE_EXTENT { | |
208 | None | |
209 | } else { | |
210 | Some(self) | |
1a4d82fc JJ |
211 | } |
212 | } | |
e9174d1e SL |
213 | pub fn node_id(&self, region_maps: &RegionMaps) -> ast::NodeId { |
214 | region_maps.code_extent_data(*self).node_id() | |
215 | } | |
85aaf69f SL |
216 | |
217 | /// Returns the span of this CodeExtent. Note that in general the | |
218 | /// returned span may not correspond to the span of any node id in | |
219 | /// the AST. | |
e9174d1e SL |
220 | pub fn span(&self, region_maps: &RegionMaps, ast_map: &ast_map::Map) -> Option<Span> { |
221 | match ast_map.find(self.node_id(region_maps)) { | |
85aaf69f | 222 | Some(ast_map::NodeBlock(ref blk)) => { |
e9174d1e | 223 | match region_maps.code_extent_data(*self) { |
9cc50fc6 | 224 | CodeExtentData::CallSiteScope { .. } | |
e9174d1e SL |
225 | CodeExtentData::ParameterScope { .. } | |
226 | CodeExtentData::Misc(_) | | |
227 | CodeExtentData::DestructionScope(_) => Some(blk.span), | |
85aaf69f | 228 | |
e9174d1e | 229 | CodeExtentData::Remainder(r) => { |
85aaf69f SL |
230 | assert_eq!(r.block, blk.id); |
231 | // Want span for extent starting after the | |
232 | // indexed statement and ending at end of | |
233 | // `blk`; reuse span of `blk` and shift `lo` | |
234 | // forward to end of indexed statement. | |
235 | // | |
236 | // (This is the special case aluded to in the | |
237 | // doc-comment for this method) | |
e9174d1e | 238 | let stmt_span = blk.stmts[r.first_statement_index as usize].span; |
85aaf69f SL |
239 | Some(Span { lo: stmt_span.hi, ..blk.span }) |
240 | } | |
241 | } | |
242 | } | |
243 | Some(ast_map::NodeExpr(ref expr)) => Some(expr.span), | |
244 | Some(ast_map::NodeStmt(ref stmt)) => Some(stmt.span), | |
245 | Some(ast_map::NodeItem(ref item)) => Some(item.span), | |
246 | Some(_) | None => None, | |
247 | } | |
248 | } | |
1a4d82fc | 249 | } |
223e47cc | 250 | |
1a4d82fc | 251 | /// The region maps encode information about region relationships. |
970d7e83 | 252 | pub struct RegionMaps { |
e9174d1e SL |
253 | code_extents: RefCell<Vec<CodeExtentData>>, |
254 | code_extent_interner: RefCell<FnvHashMap<CodeExtentData, CodeExtent>>, | |
c34b1796 AL |
255 | /// `scope_map` maps from a scope id to the enclosing scope id; |
256 | /// this is usually corresponding to the lexical nesting, though | |
257 | /// in the case of closures the parent scope is the innermost | |
258 | /// conditional expression or repeating block. (Note that the | |
259 | /// enclosing scope id for the block associated with a closure is | |
260 | /// the closure itself.) | |
e9174d1e | 261 | scope_map: RefCell<Vec<CodeExtent>>, |
c34b1796 AL |
262 | |
263 | /// `var_map` maps from a variable or binding id to the block in | |
264 | /// which that variable is declared. | |
1a4d82fc | 265 | var_map: RefCell<NodeMap<CodeExtent>>, |
c34b1796 | 266 | |
c34b1796 AL |
267 | /// `rvalue_scopes` includes entries for those expressions whose cleanup scope is |
268 | /// larger than the default. The map goes from the expression id | |
269 | /// to the cleanup scope id. For rvalues not present in this | |
270 | /// table, the appropriate cleanup scope is the innermost | |
271 | /// enclosing statement, conditional expression, or repeating | |
272 | /// block (see `terminating_scopes`). | |
1a4d82fc | 273 | rvalue_scopes: RefCell<NodeMap<CodeExtent>>, |
c34b1796 | 274 | |
c34b1796 AL |
275 | /// Encodes the hierarchy of fn bodies. Every fn body (including |
276 | /// closures) forms its own distinct region hierarchy, rooted in | |
277 | /// the block that is the fn body. This map points from the id of | |
278 | /// that root block to the id of the root block for the enclosing | |
279 | /// fn, if any. Thus the map structures the fn bodies into a | |
280 | /// hierarchy based on their lexical mapping. This is used to | |
281 | /// handle the relationships between regions in a fn and in a | |
282 | /// closure defined by that fn. See the "Modeling closures" | |
54a0048b | 283 | /// section of the README in infer::region_inference for |
c34b1796 AL |
284 | /// more details. |
285 | fn_tree: RefCell<NodeMap<ast::NodeId>>, | |
970d7e83 | 286 | } |
223e47cc | 287 | |
c34b1796 | 288 | #[derive(Debug, Copy, Clone)] |
970d7e83 | 289 | pub struct Context { |
c34b1796 AL |
290 | /// the root of the current region tree. This is typically the id |
291 | /// of the innermost fn body. Each fn forms its own disjoint tree | |
292 | /// in the region hierarchy. These fn bodies are themselves | |
293 | /// arranged into a tree. See the "Modeling closures" section of | |
54a0048b | 294 | /// the README in infer::region_inference for more |
c34b1796 AL |
295 | /// details. |
296 | root_id: Option<ast::NodeId>, | |
297 | ||
298 | /// the scope that contains any new variables declared | |
e9174d1e | 299 | var_parent: CodeExtent, |
223e47cc | 300 | |
c34b1796 | 301 | /// region parent of expressions etc |
e9174d1e | 302 | parent: CodeExtent |
1a4d82fc | 303 | } |
970d7e83 | 304 | |
1a4d82fc JJ |
305 | struct RegionResolutionVisitor<'a> { |
306 | sess: &'a Session, | |
970d7e83 | 307 | |
1a4d82fc JJ |
308 | // Generated maps: |
309 | region_maps: &'a RegionMaps, | |
310 | ||
e9174d1e SL |
311 | cx: Context, |
312 | ||
313 | /// `terminating_scopes` is a set containing the ids of each | |
314 | /// statement, or conditional/repeating expression. These scopes | |
315 | /// are calling "terminating scopes" because, when attempting to | |
316 | /// find the scope of a temporary, by default we search up the | |
317 | /// enclosing scopes until we encounter the terminating scope. A | |
318 | /// conditional/repeating expression is one which is not | |
319 | /// guaranteed to execute exactly once upon entering the parent | |
320 | /// scope. This could be because the expression only executes | |
321 | /// conditionally, such as the expression `b` in `a && b`, or | |
322 | /// because the expression may execute many times, such as a loop | |
323 | /// body. The reason that we distinguish such expressions is that, | |
324 | /// upon exiting the parent scope, we cannot statically know how | |
325 | /// many times the expression executed, and thus if the expression | |
326 | /// creates temporaries we cannot know statically how many such | |
327 | /// temporaries we would have to cleanup. Therefore we ensure that | |
328 | /// the temporaries never outlast the conditional/repeating | |
329 | /// expression, preventing the need for dynamic checks and/or | |
330 | /// arbitrary amounts of stack space. Terminating scopes end | |
331 | /// up being contained in a DestructionScope that contains the | |
332 | /// destructor's execution. | |
333 | terminating_scopes: NodeSet | |
223e47cc LB |
334 | } |
335 | ||
1a4d82fc | 336 | |
970d7e83 | 337 | impl RegionMaps { |
e9174d1e SL |
338 | /// create a bogus code extent for the regions in astencode types. Nobody |
339 | /// really cares about the contents of these. | |
340 | pub fn bogus_code_extent(&self, e: CodeExtentData) -> CodeExtent { | |
341 | self.intern_code_extent(e, DUMMY_CODE_EXTENT) | |
342 | } | |
343 | pub fn lookup_code_extent(&self, e: CodeExtentData) -> CodeExtent { | |
344 | match self.code_extent_interner.borrow().get(&e) { | |
345 | Some(&d) => d, | |
54a0048b | 346 | None => bug!("unknown code extent {:?}", e) |
e9174d1e SL |
347 | } |
348 | } | |
349 | pub fn node_extent(&self, n: ast::NodeId) -> CodeExtent { | |
350 | self.lookup_code_extent(CodeExtentData::Misc(n)) | |
351 | } | |
352 | // Returns the code extent for an item - the destruction scope. | |
353 | pub fn item_extent(&self, n: ast::NodeId) -> CodeExtent { | |
354 | self.lookup_code_extent(CodeExtentData::DestructionScope(n)) | |
355 | } | |
9cc50fc6 SL |
356 | pub fn call_site_extent(&self, fn_id: ast::NodeId, body_id: ast::NodeId) -> CodeExtent { |
357 | assert!(fn_id != body_id); | |
358 | self.lookup_code_extent(CodeExtentData::CallSiteScope { fn_id: fn_id, body_id: body_id }) | |
359 | } | |
e9174d1e SL |
360 | pub fn opt_destruction_extent(&self, n: ast::NodeId) -> Option<CodeExtent> { |
361 | self.code_extent_interner.borrow().get(&CodeExtentData::DestructionScope(n)).cloned() | |
362 | } | |
363 | pub fn intern_code_extent(&self, | |
364 | e: CodeExtentData, | |
365 | parent: CodeExtent) -> CodeExtent { | |
366 | match self.code_extent_interner.borrow_mut().entry(e) { | |
367 | Entry::Occupied(o) => { | |
368 | // this can happen when the bogus code extents from tydecode | |
369 | // have (bogus) NodeId-s that overlap items created during | |
370 | // inlining. | |
371 | // We probably shouldn't be creating bogus code extents | |
372 | // though. | |
373 | let idx = *o.get(); | |
374 | if parent == DUMMY_CODE_EXTENT { | |
375 | info!("CodeExtent({}) = {:?} [parent={}] BOGUS!", | |
376 | idx.0, e, parent.0); | |
377 | } else { | |
378 | assert_eq!(self.scope_map.borrow()[idx.0 as usize], | |
379 | DUMMY_CODE_EXTENT); | |
380 | info!("CodeExtent({}) = {:?} [parent={}] RECLAIMED!", | |
381 | idx.0, e, parent.0); | |
382 | self.scope_map.borrow_mut()[idx.0 as usize] = parent; | |
383 | } | |
384 | idx | |
385 | } | |
386 | Entry::Vacant(v) => { | |
387 | if self.code_extents.borrow().len() > 0xffffffffusize { | |
54a0048b SL |
388 | bug!() // should pass a sess, |
389 | // but this isn't the only place | |
e9174d1e SL |
390 | } |
391 | let idx = CodeExtent(self.code_extents.borrow().len() as u32); | |
392 | info!("CodeExtent({}) = {:?} [parent={}]", idx.0, e, parent.0); | |
393 | self.code_extents.borrow_mut().push(e); | |
394 | self.scope_map.borrow_mut().push(parent); | |
395 | *v.insert(idx) | |
396 | } | |
397 | } | |
398 | } | |
399 | pub fn intern_node(&self, | |
400 | n: ast::NodeId, | |
401 | parent: CodeExtent) -> CodeExtent { | |
402 | self.intern_code_extent(CodeExtentData::Misc(n), parent) | |
403 | } | |
404 | pub fn code_extent_data(&self, e: CodeExtent) -> CodeExtentData { | |
405 | self.code_extents.borrow()[e.0 as usize] | |
406 | } | |
85aaf69f | 407 | pub fn each_encl_scope<E>(&self, mut e:E) where E: FnMut(&CodeExtent, &CodeExtent) { |
b039eaaf | 408 | for child_id in 1..self.code_extents.borrow().len() { |
e9174d1e SL |
409 | let child = CodeExtent(child_id as u32); |
410 | if let Some(parent) = self.opt_encl_scope(child) { | |
411 | e(&child, &parent) | |
412 | } | |
85aaf69f SL |
413 | } |
414 | } | |
415 | pub fn each_var_scope<E>(&self, mut e:E) where E: FnMut(&ast::NodeId, &CodeExtent) { | |
416 | for (child, parent) in self.var_map.borrow().iter() { | |
417 | e(child, parent) | |
418 | } | |
419 | } | |
85aaf69f SL |
420 | pub fn each_rvalue_scope<E>(&self, mut e:E) where E: FnMut(&ast::NodeId, &CodeExtent) { |
421 | for (child, parent) in self.rvalue_scopes.borrow().iter() { | |
422 | e(child, parent) | |
423 | } | |
424 | } | |
c34b1796 AL |
425 | /// Records that `sub_fn` is defined within `sup_fn`. These ids |
426 | /// should be the id of the block that is the fn body, which is | |
427 | /// also the root of the region hierarchy for that fn. | |
428 | fn record_fn_parent(&self, sub_fn: ast::NodeId, sup_fn: ast::NodeId) { | |
429 | debug!("record_fn_parent(sub_fn={:?}, sup_fn={:?})", sub_fn, sup_fn); | |
430 | assert!(sub_fn != sup_fn); | |
431 | let previous = self.fn_tree.borrow_mut().insert(sub_fn, sup_fn); | |
432 | assert!(previous.is_none()); | |
433 | } | |
434 | ||
435 | fn fn_is_enclosed_by(&self, mut sub_fn: ast::NodeId, sup_fn: ast::NodeId) -> bool { | |
436 | let fn_tree = self.fn_tree.borrow(); | |
437 | loop { | |
438 | if sub_fn == sup_fn { return true; } | |
439 | match fn_tree.get(&sub_fn) { | |
440 | Some(&s) => { sub_fn = s; } | |
441 | None => { return false; } | |
442 | } | |
443 | } | |
444 | } | |
445 | ||
c34b1796 | 446 | fn record_var_scope(&self, var: ast::NodeId, lifetime: CodeExtent) { |
1a4d82fc | 447 | debug!("record_var_scope(sub={:?}, sup={:?})", var, lifetime); |
e9174d1e | 448 | assert!(var != lifetime.node_id(self)); |
1a4d82fc | 449 | self.var_map.borrow_mut().insert(var, lifetime); |
970d7e83 | 450 | } |
223e47cc | 451 | |
c34b1796 | 452 | fn record_rvalue_scope(&self, var: ast::NodeId, lifetime: CodeExtent) { |
1a4d82fc | 453 | debug!("record_rvalue_scope(sub={:?}, sup={:?})", var, lifetime); |
e9174d1e | 454 | assert!(var != lifetime.node_id(self)); |
1a4d82fc JJ |
455 | self.rvalue_scopes.borrow_mut().insert(var, lifetime); |
456 | } | |
970d7e83 | 457 | |
1a4d82fc | 458 | pub fn opt_encl_scope(&self, id: CodeExtent) -> Option<CodeExtent> { |
970d7e83 | 459 | //! Returns the narrowest scope that encloses `id`, if any. |
e9174d1e | 460 | self.scope_map.borrow()[id.0 as usize].into_option() |
970d7e83 LB |
461 | } |
462 | ||
54a0048b | 463 | #[allow(dead_code)] // used in cfg |
1a4d82fc | 464 | pub fn encl_scope(&self, id: CodeExtent) -> CodeExtent { |
970d7e83 | 465 | //! Returns the narrowest scope that encloses `id`, if any. |
e9174d1e | 466 | self.opt_encl_scope(id).unwrap() |
970d7e83 LB |
467 | } |
468 | ||
1a4d82fc JJ |
469 | /// Returns the lifetime of the local variable `var_id` |
470 | pub fn var_scope(&self, var_id: ast::NodeId) -> CodeExtent { | |
471 | match self.var_map.borrow().get(&var_id) { | |
472 | Some(&r) => r, | |
54a0048b | 473 | None => { bug!("no enclosing scope for id {:?}", var_id); } |
1a4d82fc | 474 | } |
970d7e83 LB |
475 | } |
476 | ||
1a4d82fc JJ |
477 | pub fn temporary_scope(&self, expr_id: ast::NodeId) -> Option<CodeExtent> { |
478 | //! Returns the scope when temp created by expr_id will be cleaned up | |
970d7e83 | 479 | |
1a4d82fc JJ |
480 | // check for a designated rvalue scope |
481 | match self.rvalue_scopes.borrow().get(&expr_id) { | |
482 | Some(&s) => { | |
483 | debug!("temporary_scope({:?}) = {:?} [custom]", expr_id, s); | |
484 | return Some(s); | |
485 | } | |
486 | None => { } | |
970d7e83 | 487 | } |
1a4d82fc | 488 | |
e9174d1e SL |
489 | let scope_map : &[CodeExtent] = &self.scope_map.borrow(); |
490 | let code_extents: &[CodeExtentData] = &self.code_extents.borrow(); | |
491 | ||
1a4d82fc JJ |
492 | // else, locate the innermost terminating scope |
493 | // if there's one. Static items, for instance, won't | |
494 | // have an enclosing scope, hence no scope will be | |
495 | // returned. | |
e9174d1e SL |
496 | let expr_extent = self.node_extent(expr_id); |
497 | // For some reason, the expr's scope itself is skipped here. | |
498 | let mut id = match scope_map[expr_extent.0 as usize].into_option() { | |
1a4d82fc | 499 | Some(i) => i, |
e9174d1e | 500 | _ => return None |
1a4d82fc JJ |
501 | }; |
502 | ||
e9174d1e SL |
503 | while let Some(p) = scope_map[id.0 as usize].into_option() { |
504 | match code_extents[p.0 as usize] { | |
505 | CodeExtentData::DestructionScope(..) => { | |
506 | debug!("temporary_scope({:?}) = {:?} [enclosing]", | |
507 | expr_id, id); | |
508 | return Some(id); | |
1a4d82fc | 509 | } |
e9174d1e | 510 | _ => id = p |
1a4d82fc JJ |
511 | } |
512 | } | |
e9174d1e SL |
513 | |
514 | debug!("temporary_scope({:?}) = None", expr_id); | |
515 | return None; | |
970d7e83 LB |
516 | } |
517 | ||
1a4d82fc JJ |
518 | pub fn var_region(&self, id: ast::NodeId) -> ty::Region { |
519 | //! Returns the lifetime of the variable `id`. | |
970d7e83 | 520 | |
1a4d82fc JJ |
521 | let scope = ty::ReScope(self.var_scope(id)); |
522 | debug!("var_region({:?}) = {:?}", id, scope); | |
523 | scope | |
970d7e83 LB |
524 | } |
525 | ||
1a4d82fc | 526 | pub fn scopes_intersect(&self, scope1: CodeExtent, scope2: CodeExtent) |
970d7e83 LB |
527 | -> bool { |
528 | self.is_subscope_of(scope1, scope2) || | |
529 | self.is_subscope_of(scope2, scope1) | |
530 | } | |
531 | ||
1a4d82fc JJ |
532 | /// Returns true if `subscope` is equal to or is lexically nested inside `superscope` and false |
533 | /// otherwise. | |
970d7e83 | 534 | pub fn is_subscope_of(&self, |
1a4d82fc JJ |
535 | subscope: CodeExtent, |
536 | superscope: CodeExtent) | |
970d7e83 | 537 | -> bool { |
970d7e83 | 538 | let mut s = subscope; |
e9174d1e | 539 | debug!("is_subscope_of({:?}, {:?})", subscope, superscope); |
970d7e83 | 540 | while superscope != s { |
e9174d1e | 541 | match self.opt_encl_scope(s) { |
970d7e83 | 542 | None => { |
1a4d82fc | 543 | debug!("is_subscope_of({:?}, {:?}, s={:?})=false", |
970d7e83 | 544 | subscope, superscope, s); |
970d7e83 LB |
545 | return false; |
546 | } | |
e9174d1e | 547 | Some(scope) => s = scope |
223e47cc LB |
548 | } |
549 | } | |
223e47cc | 550 | |
1a4d82fc | 551 | debug!("is_subscope_of({:?}, {:?})=true", |
970d7e83 LB |
552 | subscope, superscope); |
553 | ||
554 | return true; | |
555 | } | |
556 | ||
1a4d82fc JJ |
557 | /// Finds the nearest common ancestor (if any) of two scopes. That is, finds the smallest |
558 | /// scope which is greater than or equal to both `scope_a` and `scope_b`. | |
970d7e83 | 559 | pub fn nearest_common_ancestor(&self, |
1a4d82fc JJ |
560 | scope_a: CodeExtent, |
561 | scope_b: CodeExtent) | |
c34b1796 AL |
562 | -> CodeExtent { |
563 | if scope_a == scope_b { return scope_a; } | |
970d7e83 | 564 | |
e9174d1e SL |
565 | let mut a_buf: [CodeExtent; 32] = [ROOT_CODE_EXTENT; 32]; |
566 | let mut a_vec: Vec<CodeExtent> = vec![]; | |
567 | let mut b_buf: [CodeExtent; 32] = [ROOT_CODE_EXTENT; 32]; | |
568 | let mut b_vec: Vec<CodeExtent> = vec![]; | |
569 | let scope_map : &[CodeExtent] = &self.scope_map.borrow(); | |
570 | let a_ancestors = ancestors_of(scope_map, | |
571 | scope_a, &mut a_buf, &mut a_vec); | |
572 | let b_ancestors = ancestors_of(scope_map, | |
573 | scope_b, &mut b_buf, &mut b_vec); | |
85aaf69f SL |
574 | let mut a_index = a_ancestors.len() - 1; |
575 | let mut b_index = b_ancestors.len() - 1; | |
970d7e83 | 576 | |
c34b1796 | 577 | // Here, [ab]_ancestors is a vector going from narrow to broad. |
970d7e83 LB |
578 | // The end of each vector will be the item where the scope is |
579 | // defined; if there are any common ancestors, then the tails of | |
580 | // the vector will be the same. So basically we want to walk | |
581 | // backwards from the tail of each vector and find the first point | |
582 | // where they diverge. If one vector is a suffix of the other, | |
583 | // then the corresponding scope is a superscope of the other. | |
584 | ||
223e47cc | 585 | if a_ancestors[a_index] != b_ancestors[b_index] { |
c34b1796 AL |
586 | // In this case, the two regions belong to completely |
587 | // different functions. Compare those fn for lexical | |
588 | // nesting. The reasoning behind this is subtle. See the | |
589 | // "Modeling closures" section of the README in | |
54a0048b | 590 | // infer::region_inference for more details. |
e9174d1e SL |
591 | let a_root_scope = self.code_extent_data(a_ancestors[a_index]); |
592 | let b_root_scope = self.code_extent_data(a_ancestors[a_index]); | |
c34b1796 | 593 | return match (a_root_scope, b_root_scope) { |
e9174d1e SL |
594 | (CodeExtentData::DestructionScope(a_root_id), |
595 | CodeExtentData::DestructionScope(b_root_id)) => { | |
c34b1796 AL |
596 | if self.fn_is_enclosed_by(a_root_id, b_root_id) { |
597 | // `a` is enclosed by `b`, hence `b` is the ancestor of everything in `a` | |
598 | scope_b | |
599 | } else if self.fn_is_enclosed_by(b_root_id, a_root_id) { | |
600 | // `b` is enclosed by `a`, hence `a` is the ancestor of everything in `b` | |
601 | scope_a | |
602 | } else { | |
603 | // neither fn encloses the other | |
54a0048b | 604 | bug!() |
c34b1796 AL |
605 | } |
606 | } | |
607 | _ => { | |
608 | // root ids are always Misc right now | |
54a0048b | 609 | bug!() |
c34b1796 AL |
610 | } |
611 | }; | |
223e47cc | 612 | } |
223e47cc | 613 | |
970d7e83 LB |
614 | loop { |
615 | // Loop invariant: a_ancestors[a_index] == b_ancestors[b_index] | |
616 | // for all indices between a_index and the end of the array | |
c34b1796 AL |
617 | if a_index == 0 { return scope_a; } |
618 | if b_index == 0 { return scope_b; } | |
85aaf69f SL |
619 | a_index -= 1; |
620 | b_index -= 1; | |
970d7e83 | 621 | if a_ancestors[a_index] != b_ancestors[b_index] { |
c34b1796 | 622 | return a_ancestors[a_index + 1]; |
970d7e83 LB |
623 | } |
624 | } | |
625 | ||
e9174d1e SL |
626 | fn ancestors_of<'a>(scope_map: &[CodeExtent], |
627 | scope: CodeExtent, | |
628 | buf: &'a mut [CodeExtent; 32], | |
629 | vec: &'a mut Vec<CodeExtent>) -> &'a [CodeExtent] { | |
1a4d82fc | 630 | // debug!("ancestors_of(scope={:?})", scope); |
970d7e83 | 631 | let mut scope = scope; |
e9174d1e SL |
632 | |
633 | let mut i = 0; | |
634 | while i < 32 { | |
635 | buf[i] = scope; | |
636 | match scope_map[scope.0 as usize].into_option() { | |
637 | Some(superscope) => scope = superscope, | |
638 | _ => return &buf[..i+1] | |
639 | } | |
640 | i += 1; | |
641 | } | |
642 | ||
643 | *vec = Vec::with_capacity(64); | |
92a42be0 | 644 | vec.extend_from_slice(buf); |
970d7e83 | 645 | loop { |
e9174d1e SL |
646 | vec.push(scope); |
647 | match scope_map[scope.0 as usize].into_option() { | |
648 | Some(superscope) => scope = superscope, | |
649 | _ => return &*vec | |
970d7e83 | 650 | } |
970d7e83 LB |
651 | } |
652 | } | |
223e47cc LB |
653 | } |
654 | } | |
655 | ||
1a4d82fc JJ |
656 | /// Records the lifetime of a local variable as `cx.var_parent` |
657 | fn record_var_lifetime(visitor: &mut RegionResolutionVisitor, | |
658 | var_id: ast::NodeId, | |
659 | _sp: Span) { | |
e9174d1e SL |
660 | match visitor.cx.var_parent { |
661 | ROOT_CODE_EXTENT => { | |
1a4d82fc JJ |
662 | // this can happen in extern fn declarations like |
663 | // | |
664 | // extern fn isalnum(c: c_int) -> c_int | |
665 | } | |
e9174d1e SL |
666 | parent_scope => |
667 | visitor.region_maps.record_var_scope(var_id, parent_scope), | |
1a4d82fc JJ |
668 | } |
669 | } | |
670 | ||
e9174d1e | 671 | fn resolve_block(visitor: &mut RegionResolutionVisitor, blk: &hir::Block) { |
1a4d82fc JJ |
672 | debug!("resolve_block(blk.id={:?})", blk.id); |
673 | ||
85aaf69f | 674 | let prev_cx = visitor.cx; |
e9174d1e | 675 | let block_extent = visitor.new_node_extent_with_dtor(blk.id); |
223e47cc | 676 | |
1a4d82fc JJ |
677 | // We treat the tail expression in the block (if any) somewhat |
678 | // differently from the statements. The issue has to do with | |
85aaf69f SL |
679 | // temporary lifetimes. Consider the following: |
680 | // | |
681 | // quux({ | |
682 | // let inner = ... (&bar()) ...; | |
683 | // | |
684 | // (... (&foo()) ...) // (the tail expression) | |
685 | // }, other_argument()); | |
1a4d82fc | 686 | // |
85aaf69f SL |
687 | // Each of the statements within the block is a terminating |
688 | // scope, and thus a temporary (e.g. the result of calling | |
689 | // `bar()` in the initalizer expression for `let inner = ...;`) | |
690 | // will be cleaned up immediately after its corresponding | |
691 | // statement (i.e. `let inner = ...;`) executes. | |
1a4d82fc | 692 | // |
85aaf69f SL |
693 | // On the other hand, temporaries associated with evaluating the |
694 | // tail expression for the block are assigned lifetimes so that | |
695 | // they will be cleaned up as part of the terminating scope | |
696 | // *surrounding* the block expression. Here, the terminating | |
697 | // scope for the block expression is the `quux(..)` call; so | |
698 | // those temporaries will only be cleaned up *after* both | |
699 | // `other_argument()` has run and also the call to `quux(..)` | |
700 | // itself has returned. | |
701 | ||
702 | visitor.cx = Context { | |
c34b1796 | 703 | root_id: prev_cx.root_id, |
e9174d1e SL |
704 | var_parent: block_extent, |
705 | parent: block_extent, | |
85aaf69f SL |
706 | }; |
707 | ||
708 | { | |
709 | // This block should be kept approximately in sync with | |
92a42be0 | 710 | // `intravisit::walk_block`. (We manually walk the block, rather |
85aaf69f | 711 | // than call `walk_block`, in order to maintain precise |
e9174d1e | 712 | // index information.) |
85aaf69f SL |
713 | |
714 | for (i, statement) in blk.stmts.iter().enumerate() { | |
e9174d1e | 715 | if let hir::StmtDecl(..) = statement.node { |
85aaf69f SL |
716 | // Each StmtDecl introduces a subscope for bindings |
717 | // introduced by the declaration; this subscope covers | |
718 | // a suffix of the block . Each subscope in a block | |
719 | // has the previous subscope in the block as a parent, | |
720 | // except for the first such subscope, which has the | |
721 | // block itself as a parent. | |
e9174d1e SL |
722 | let stmt_extent = visitor.new_code_extent( |
723 | CodeExtentData::Remainder(BlockRemainder { | |
724 | block: blk.id, | |
725 | first_statement_index: i as u32 | |
726 | }) | |
727 | ); | |
85aaf69f | 728 | visitor.cx = Context { |
c34b1796 | 729 | root_id: prev_cx.root_id, |
e9174d1e SL |
730 | var_parent: stmt_extent, |
731 | parent: stmt_extent, | |
85aaf69f SL |
732 | }; |
733 | } | |
92a42be0 | 734 | visitor.visit_stmt(statement) |
85aaf69f | 735 | } |
b039eaaf | 736 | walk_list!(visitor, visit_expr, &blk.expr); |
85aaf69f | 737 | } |
223e47cc | 738 | |
1a4d82fc | 739 | visitor.cx = prev_cx; |
223e47cc LB |
740 | } |
741 | ||
e9174d1e SL |
742 | fn resolve_arm(visitor: &mut RegionResolutionVisitor, arm: &hir::Arm) { |
743 | visitor.terminating_scopes.insert(arm.body.id); | |
223e47cc | 744 | |
e9174d1e SL |
745 | if let Some(ref expr) = arm.guard { |
746 | visitor.terminating_scopes.insert(expr.id); | |
223e47cc | 747 | } |
1a4d82fc | 748 | |
92a42be0 | 749 | intravisit::walk_arm(visitor, arm); |
223e47cc LB |
750 | } |
751 | ||
e9174d1e SL |
752 | fn resolve_pat(visitor: &mut RegionResolutionVisitor, pat: &hir::Pat) { |
753 | visitor.new_node_extent(pat.id); | |
223e47cc | 754 | |
1a4d82fc JJ |
755 | // If this is a binding (or maybe a binding, I'm too lazy to check |
756 | // the def map) then record the lifetime of that binding. | |
757 | match pat.node { | |
7453a54e | 758 | PatKind::Ident(..) => { |
1a4d82fc | 759 | record_var_lifetime(visitor, pat.id, pat.span); |
970d7e83 | 760 | } |
1a4d82fc JJ |
761 | _ => { } |
762 | } | |
970d7e83 | 763 | |
92a42be0 | 764 | intravisit::walk_pat(visitor, pat); |
1a4d82fc | 765 | } |
970d7e83 | 766 | |
e9174d1e | 767 | fn resolve_stmt(visitor: &mut RegionResolutionVisitor, stmt: &hir::Stmt) { |
54a0048b | 768 | let stmt_id = stmt.node.id(); |
1a4d82fc | 769 | debug!("resolve_stmt(stmt.id={:?})", stmt_id); |
223e47cc | 770 | |
85aaf69f SL |
771 | // Every statement will clean up the temporaries created during |
772 | // execution of that statement. Therefore each statement has an | |
773 | // associated destruction scope that represents the extent of the | |
774 | // statement plus its destructors, and thus the extent for which | |
775 | // regions referenced by the destructors need to survive. | |
e9174d1e SL |
776 | visitor.terminating_scopes.insert(stmt_id); |
777 | let stmt_extent = visitor.new_node_extent_with_dtor(stmt_id); | |
223e47cc | 778 | |
1a4d82fc | 779 | let prev_parent = visitor.cx.parent; |
e9174d1e | 780 | visitor.cx.parent = stmt_extent; |
92a42be0 | 781 | intravisit::walk_stmt(visitor, stmt); |
1a4d82fc | 782 | visitor.cx.parent = prev_parent; |
223e47cc LB |
783 | } |
784 | ||
e9174d1e | 785 | fn resolve_expr(visitor: &mut RegionResolutionVisitor, expr: &hir::Expr) { |
1a4d82fc | 786 | debug!("resolve_expr(expr.id={:?})", expr.id); |
223e47cc | 787 | |
e9174d1e | 788 | let expr_extent = visitor.new_node_extent_with_dtor(expr.id); |
1a4d82fc | 789 | let prev_cx = visitor.cx; |
e9174d1e | 790 | visitor.cx.parent = expr_extent; |
970d7e83 | 791 | |
1a4d82fc | 792 | { |
e9174d1e SL |
793 | let terminating_scopes = &mut visitor.terminating_scopes; |
794 | let mut terminating = |id: ast::NodeId| { | |
795 | terminating_scopes.insert(id); | |
1a4d82fc JJ |
796 | }; |
797 | match expr.node { | |
798 | // Conditional or repeating scopes are always terminating | |
799 | // scopes, meaning that temporaries cannot outlive them. | |
800 | // This ensures fixed size stacks. | |
801 | ||
e9174d1e SL |
802 | hir::ExprBinary(codemap::Spanned { node: hir::BiAnd, .. }, _, ref r) | |
803 | hir::ExprBinary(codemap::Spanned { node: hir::BiOr, .. }, _, ref r) => { | |
1a4d82fc JJ |
804 | // For shortcircuiting operators, mark the RHS as a terminating |
805 | // scope since it only executes conditionally. | |
e9174d1e | 806 | terminating(r.id); |
1a4d82fc | 807 | } |
223e47cc | 808 | |
e9174d1e SL |
809 | hir::ExprIf(_, ref then, Some(ref otherwise)) => { |
810 | terminating(then.id); | |
811 | terminating(otherwise.id); | |
1a4d82fc | 812 | } |
223e47cc | 813 | |
e9174d1e SL |
814 | hir::ExprIf(ref expr, ref then, None) => { |
815 | terminating(expr.id); | |
816 | terminating(then.id); | |
1a4d82fc | 817 | } |
223e47cc | 818 | |
e9174d1e SL |
819 | hir::ExprLoop(ref body, _) => { |
820 | terminating(body.id); | |
1a4d82fc | 821 | } |
223e47cc | 822 | |
e9174d1e SL |
823 | hir::ExprWhile(ref expr, ref body, _) => { |
824 | terminating(expr.id); | |
825 | terminating(body.id); | |
1a4d82fc | 826 | } |
223e47cc | 827 | |
e9174d1e SL |
828 | hir::ExprMatch(..) => { |
829 | visitor.cx.var_parent = expr_extent; | |
1a4d82fc | 830 | } |
223e47cc | 831 | |
e9174d1e SL |
832 | hir::ExprAssignOp(..) | hir::ExprIndex(..) | |
833 | hir::ExprUnary(..) | hir::ExprCall(..) | hir::ExprMethodCall(..) => { | |
1a4d82fc JJ |
834 | // FIXME(#6268) Nested method calls |
835 | // | |
836 | // The lifetimes for a call or method call look as follows: | |
837 | // | |
838 | // call.id | |
839 | // - arg0.id | |
840 | // - ... | |
841 | // - argN.id | |
842 | // - call.callee_id | |
843 | // | |
844 | // The idea is that call.callee_id represents *the time when | |
845 | // the invoked function is actually running* and call.id | |
846 | // represents *the time to prepare the arguments and make the | |
c34b1796 | 847 | // call*. See the section "Borrows in Calls" borrowck/README.md |
1a4d82fc JJ |
848 | // for an extended explanation of why this distinction is |
849 | // important. | |
850 | // | |
851 | // record_superlifetime(new_cx, expr.callee_id); | |
852 | } | |
223e47cc | 853 | |
1a4d82fc JJ |
854 | _ => {} |
855 | } | |
223e47cc | 856 | } |
223e47cc | 857 | |
92a42be0 | 858 | intravisit::walk_expr(visitor, expr); |
1a4d82fc | 859 | visitor.cx = prev_cx; |
223e47cc LB |
860 | } |
861 | ||
e9174d1e | 862 | fn resolve_local(visitor: &mut RegionResolutionVisitor, local: &hir::Local) { |
1a4d82fc JJ |
863 | debug!("resolve_local(local.id={:?},local.init={:?})", |
864 | local.id,local.init.is_some()); | |
223e47cc | 865 | |
1a4d82fc JJ |
866 | // For convenience in trans, associate with the local-id the var |
867 | // scope that will be used for any bindings declared in this | |
868 | // pattern. | |
e9174d1e SL |
869 | let blk_scope = visitor.cx.var_parent; |
870 | assert!(blk_scope != ROOT_CODE_EXTENT); // locals must be within a block | |
1a4d82fc | 871 | visitor.region_maps.record_var_scope(local.id, blk_scope); |
223e47cc | 872 | |
1a4d82fc JJ |
873 | // As an exception to the normal rules governing temporary |
874 | // lifetimes, initializers in a let have a temporary lifetime | |
875 | // of the enclosing block. This means that e.g. a program | |
876 | // like the following is legal: | |
223e47cc | 877 | // |
1a4d82fc | 878 | // let ref x = HashMap::new(); |
223e47cc | 879 | // |
1a4d82fc | 880 | // Because the hash map will be freed in the enclosing block. |
223e47cc | 881 | // |
1a4d82fc JJ |
882 | // We express the rules more formally based on 3 grammars (defined |
883 | // fully in the helpers below that implement them): | |
223e47cc | 884 | // |
1a4d82fc JJ |
885 | // 1. `E&`, which matches expressions like `&<rvalue>` that |
886 | // own a pointer into the stack. | |
223e47cc | 887 | // |
1a4d82fc JJ |
888 | // 2. `P&`, which matches patterns like `ref x` or `(ref x, ref |
889 | // y)` that produce ref bindings into the value they are | |
890 | // matched against or something (at least partially) owned by | |
891 | // the value they are matched against. (By partially owned, | |
892 | // I mean that creating a binding into a ref-counted or managed value | |
893 | // would still count.) | |
223e47cc | 894 | // |
1a4d82fc JJ |
895 | // 3. `ET`, which matches both rvalues like `foo()` as well as lvalues |
896 | // based on rvalues like `foo().x[2].y`. | |
223e47cc | 897 | // |
1a4d82fc JJ |
898 | // A subexpression `<rvalue>` that appears in a let initializer |
899 | // `let pat [: ty] = expr` has an extended temporary lifetime if | |
900 | // any of the following conditions are met: | |
901 | // | |
902 | // A. `pat` matches `P&` and `expr` matches `ET` | |
903 | // (covers cases where `pat` creates ref bindings into an rvalue | |
904 | // produced by `expr`) | |
905 | // B. `ty` is a borrowed pointer and `expr` matches `ET` | |
906 | // (covers cases where coercion creates a borrow) | |
907 | // C. `expr` matches `E&` | |
908 | // (covers cases `expr` borrows an rvalue that is then assigned | |
909 | // to memory (at least partially) owned by the binding) | |
910 | // | |
911 | // Here are some examples hopefully giving an intuition where each | |
912 | // rule comes into play and why: | |
913 | // | |
914 | // Rule A. `let (ref x, ref y) = (foo().x, 44)`. The rvalue `(22, 44)` | |
915 | // would have an extended lifetime, but not `foo()`. | |
916 | // | |
917 | // Rule B. `let x: &[...] = [foo().x]`. The rvalue `[foo().x]` | |
918 | // would have an extended lifetime, but not `foo()`. | |
919 | // | |
920 | // Rule C. `let x = &foo().x`. The rvalue ``foo()` would have extended | |
921 | // lifetime. | |
922 | // | |
923 | // In some cases, multiple rules may apply (though not to the same | |
924 | // rvalue). For example: | |
925 | // | |
926 | // let ref x = [&a(), &b()]; | |
927 | // | |
928 | // Here, the expression `[...]` has an extended lifetime due to rule | |
929 | // A, but the inner rvalues `a()` and `b()` have an extended lifetime | |
930 | // due to rule C. | |
931 | // | |
932 | // FIXME(#6308) -- Note that `[]` patterns work more smoothly post-DST. | |
933 | ||
934 | match local.init { | |
935 | Some(ref expr) => { | |
7453a54e | 936 | record_rvalue_scope_if_borrow_expr(visitor, &expr, blk_scope); |
1a4d82fc JJ |
937 | |
938 | let is_borrow = | |
7453a54e | 939 | if let Some(ref ty) = local.ty { is_borrowed_ty(&ty) } else { false }; |
1a4d82fc | 940 | |
7453a54e SL |
941 | if is_binding_pat(&local.pat) || is_borrow { |
942 | record_rvalue_scope(visitor, &expr, blk_scope); | |
223e47cc LB |
943 | } |
944 | } | |
223e47cc | 945 | |
1a4d82fc | 946 | None => { } |
223e47cc | 947 | } |
223e47cc | 948 | |
92a42be0 | 949 | intravisit::walk_local(visitor, local); |
1a4d82fc JJ |
950 | |
951 | /// True if `pat` match the `P&` nonterminal: | |
952 | /// | |
953 | /// P& = ref X | |
954 | /// | StructName { ..., P&, ... } | |
955 | /// | VariantName(..., P&, ...) | |
956 | /// | [ ..., P&, ... ] | |
957 | /// | ( ..., P&, ... ) | |
958 | /// | box P& | |
e9174d1e | 959 | fn is_binding_pat(pat: &hir::Pat) -> bool { |
1a4d82fc | 960 | match pat.node { |
7453a54e | 961 | PatKind::Ident(hir::BindByRef(_), _, _) => true, |
223e47cc | 962 | |
7453a54e SL |
963 | PatKind::Struct(_, ref field_pats, _) => { |
964 | field_pats.iter().any(|fp| is_binding_pat(&fp.node.pat)) | |
223e47cc | 965 | } |
1a4d82fc | 966 | |
7453a54e SL |
967 | PatKind::Vec(ref pats1, ref pats2, ref pats3) => { |
968 | pats1.iter().any(|p| is_binding_pat(&p)) || | |
969 | pats2.iter().any(|p| is_binding_pat(&p)) || | |
970 | pats3.iter().any(|p| is_binding_pat(&p)) | |
1a4d82fc JJ |
971 | } |
972 | ||
7453a54e SL |
973 | PatKind::TupleStruct(_, Some(ref subpats)) | |
974 | PatKind::Tup(ref subpats) => { | |
975 | subpats.iter().any(|p| is_binding_pat(&p)) | |
1a4d82fc JJ |
976 | } |
977 | ||
7453a54e SL |
978 | PatKind::Box(ref subpat) => { |
979 | is_binding_pat(&subpat) | |
1a4d82fc JJ |
980 | } |
981 | ||
982 | _ => false, | |
223e47cc | 983 | } |
223e47cc | 984 | } |
223e47cc | 985 | |
1a4d82fc | 986 | /// True if `ty` is a borrowed pointer type like `&int` or `&[...]`. |
e9174d1e | 987 | fn is_borrowed_ty(ty: &hir::Ty) -> bool { |
1a4d82fc | 988 | match ty.node { |
e9174d1e | 989 | hir::TyRptr(..) => true, |
1a4d82fc JJ |
990 | _ => false |
991 | } | |
223e47cc | 992 | } |
223e47cc | 993 | |
1a4d82fc JJ |
994 | /// If `expr` matches the `E&` grammar, then records an extended rvalue scope as appropriate: |
995 | /// | |
996 | /// E& = & ET | |
997 | /// | StructName { ..., f: E&, ... } | |
998 | /// | [ ..., E&, ... ] | |
999 | /// | ( ..., E&, ... ) | |
1000 | /// | {...; E&} | |
1001 | /// | box E& | |
1002 | /// | E& as ... | |
1003 | /// | ( E& ) | |
1004 | fn record_rvalue_scope_if_borrow_expr(visitor: &mut RegionResolutionVisitor, | |
e9174d1e | 1005 | expr: &hir::Expr, |
1a4d82fc JJ |
1006 | blk_id: CodeExtent) { |
1007 | match expr.node { | |
e9174d1e | 1008 | hir::ExprAddrOf(_, ref subexpr) => { |
7453a54e SL |
1009 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id); |
1010 | record_rvalue_scope(visitor, &subexpr, blk_id); | |
223e47cc | 1011 | } |
e9174d1e | 1012 | hir::ExprStruct(_, ref fields, _) => { |
85aaf69f | 1013 | for field in fields { |
1a4d82fc | 1014 | record_rvalue_scope_if_borrow_expr( |
7453a54e | 1015 | visitor, &field.expr, blk_id); |
223e47cc | 1016 | } |
1a4d82fc | 1017 | } |
e9174d1e SL |
1018 | hir::ExprVec(ref subexprs) | |
1019 | hir::ExprTup(ref subexprs) => { | |
85aaf69f | 1020 | for subexpr in subexprs { |
1a4d82fc | 1021 | record_rvalue_scope_if_borrow_expr( |
7453a54e | 1022 | visitor, &subexpr, blk_id); |
1a4d82fc JJ |
1023 | } |
1024 | } | |
b039eaaf | 1025 | hir::ExprCast(ref subexpr, _) => { |
7453a54e | 1026 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id) |
1a4d82fc | 1027 | } |
e9174d1e | 1028 | hir::ExprBlock(ref block) => { |
1a4d82fc JJ |
1029 | match block.expr { |
1030 | Some(ref subexpr) => { | |
1031 | record_rvalue_scope_if_borrow_expr( | |
7453a54e | 1032 | visitor, &subexpr, blk_id); |
223e47cc | 1033 | } |
1a4d82fc | 1034 | None => { } |
223e47cc LB |
1035 | } |
1036 | } | |
1a4d82fc JJ |
1037 | _ => { |
1038 | } | |
223e47cc | 1039 | } |
1a4d82fc | 1040 | } |
223e47cc | 1041 | |
1a4d82fc JJ |
1042 | /// Applied to an expression `expr` if `expr` -- or something owned or partially owned by |
1043 | /// `expr` -- is going to be indirectly referenced by a variable in a let statement. In that | |
1044 | /// case, the "temporary lifetime" or `expr` is extended to be the block enclosing the `let` | |
1045 | /// statement. | |
1046 | /// | |
1047 | /// More formally, if `expr` matches the grammar `ET`, record the rvalue scope of the matching | |
1048 | /// `<rvalue>` as `blk_id`: | |
1049 | /// | |
1050 | /// ET = *ET | |
1051 | /// | ET[...] | |
1052 | /// | ET.f | |
1053 | /// | (ET) | |
1054 | /// | <rvalue> | |
1055 | /// | |
1056 | /// Note: ET is intended to match "rvalues or lvalues based on rvalues". | |
1057 | fn record_rvalue_scope<'a>(visitor: &mut RegionResolutionVisitor, | |
e9174d1e | 1058 | expr: &'a hir::Expr, |
1a4d82fc JJ |
1059 | blk_scope: CodeExtent) { |
1060 | let mut expr = expr; | |
1061 | loop { | |
1062 | // Note: give all the expressions matching `ET` with the | |
1063 | // extended temporary lifetime, not just the innermost rvalue, | |
1064 | // because in trans if we must compile e.g. `*rvalue()` | |
1065 | // into a temporary, we request the temporary scope of the | |
1066 | // outer expression. | |
1067 | visitor.region_maps.record_rvalue_scope(expr.id, blk_scope); | |
1068 | ||
1069 | match expr.node { | |
e9174d1e SL |
1070 | hir::ExprAddrOf(_, ref subexpr) | |
1071 | hir::ExprUnary(hir::UnDeref, ref subexpr) | | |
1072 | hir::ExprField(ref subexpr, _) | | |
1073 | hir::ExprTupField(ref subexpr, _) | | |
b039eaaf | 1074 | hir::ExprIndex(ref subexpr, _) => { |
7453a54e | 1075 | expr = &subexpr; |
223e47cc | 1076 | } |
1a4d82fc JJ |
1077 | _ => { |
1078 | return; | |
223e47cc LB |
1079 | } |
1080 | } | |
223e47cc | 1081 | } |
223e47cc | 1082 | } |
1a4d82fc | 1083 | } |
223e47cc | 1084 | |
e9174d1e | 1085 | fn resolve_item(visitor: &mut RegionResolutionVisitor, item: &hir::Item) { |
1a4d82fc JJ |
1086 | // Items create a new outer block scope as far as we're concerned. |
1087 | let prev_cx = visitor.cx; | |
e9174d1e | 1088 | let prev_ts = mem::replace(&mut visitor.terminating_scopes, NodeSet()); |
85aaf69f | 1089 | visitor.cx = Context { |
c34b1796 | 1090 | root_id: None, |
e9174d1e SL |
1091 | var_parent: ROOT_CODE_EXTENT, |
1092 | parent: ROOT_CODE_EXTENT | |
85aaf69f | 1093 | }; |
92a42be0 | 1094 | intravisit::walk_item(visitor, item); |
e9174d1e | 1095 | visitor.create_item_scope_if_needed(item.id); |
1a4d82fc | 1096 | visitor.cx = prev_cx; |
e9174d1e | 1097 | visitor.terminating_scopes = prev_ts; |
1a4d82fc | 1098 | } |
223e47cc | 1099 | |
1a4d82fc | 1100 | fn resolve_fn(visitor: &mut RegionResolutionVisitor, |
e9174d1e SL |
1101 | kind: FnKind, |
1102 | decl: &hir::FnDecl, | |
1103 | body: &hir::Block, | |
1a4d82fc JJ |
1104 | sp: Span, |
1105 | id: ast::NodeId) { | |
1106 | debug!("region::resolve_fn(id={:?}, \ | |
1107 | span={:?}, \ | |
1108 | body.id={:?}, \ | |
1109 | cx.parent={:?})", | |
1110 | id, | |
1111 | visitor.sess.codemap().span_to_string(sp), | |
1112 | body.id, | |
1113 | visitor.cx.parent); | |
1114 | ||
9cc50fc6 SL |
1115 | visitor.cx.parent = visitor.new_code_extent( |
1116 | CodeExtentData::CallSiteScope { fn_id: id, body_id: body.id }); | |
1117 | ||
e9174d1e SL |
1118 | let fn_decl_scope = visitor.new_code_extent( |
1119 | CodeExtentData::ParameterScope { fn_id: id, body_id: body.id }); | |
1a4d82fc | 1120 | |
c34b1796 AL |
1121 | if let Some(root_id) = visitor.cx.root_id { |
1122 | visitor.region_maps.record_fn_parent(body.id, root_id); | |
1123 | } | |
1124 | ||
1a4d82fc | 1125 | let outer_cx = visitor.cx; |
e9174d1e SL |
1126 | let outer_ts = mem::replace(&mut visitor.terminating_scopes, NodeSet()); |
1127 | visitor.terminating_scopes.insert(body.id); | |
1a4d82fc | 1128 | |
9346a6ac | 1129 | // The arguments and `self` are parented to the fn. |
85aaf69f | 1130 | visitor.cx = Context { |
c34b1796 | 1131 | root_id: Some(body.id), |
e9174d1e SL |
1132 | parent: ROOT_CODE_EXTENT, |
1133 | var_parent: fn_decl_scope, | |
85aaf69f | 1134 | }; |
e9174d1e | 1135 | |
92a42be0 SL |
1136 | intravisit::walk_fn_decl(visitor, decl); |
1137 | intravisit::walk_fn_kind(visitor, kind); | |
1a4d82fc | 1138 | |
c34b1796 AL |
1139 | // The body of the every fn is a root scope. |
1140 | visitor.cx = Context { | |
1141 | root_id: Some(body.id), | |
e9174d1e SL |
1142 | parent: fn_decl_scope, |
1143 | var_parent: fn_decl_scope | |
c34b1796 AL |
1144 | }; |
1145 | visitor.visit_block(body); | |
1146 | ||
1147 | // Restore context we had at the start. | |
1148 | visitor.cx = outer_cx; | |
e9174d1e | 1149 | visitor.terminating_scopes = outer_ts; |
1a4d82fc JJ |
1150 | } |
1151 | ||
e9174d1e SL |
1152 | impl<'a> RegionResolutionVisitor<'a> { |
1153 | /// Records the current parent (if any) as the parent of `child_scope`. | |
1154 | fn new_code_extent(&mut self, child_scope: CodeExtentData) -> CodeExtent { | |
1155 | self.region_maps.intern_code_extent(child_scope, self.cx.parent) | |
1156 | } | |
1157 | ||
1158 | fn new_node_extent(&mut self, child_scope: ast::NodeId) -> CodeExtent { | |
1159 | self.new_code_extent(CodeExtentData::Misc(child_scope)) | |
1160 | } | |
1161 | ||
1162 | fn new_node_extent_with_dtor(&mut self, id: ast::NodeId) -> CodeExtent { | |
1163 | // If node was previously marked as a terminating scope during the | |
1164 | // recursive visit of its parent node in the AST, then we need to | |
1165 | // account for the destruction scope representing the extent of | |
1166 | // the destructors that run immediately after it completes. | |
1167 | if self.terminating_scopes.contains(&id) { | |
1168 | let ds = self.new_code_extent( | |
1169 | CodeExtentData::DestructionScope(id)); | |
1170 | self.region_maps.intern_node(id, ds) | |
1171 | } else { | |
1172 | self.new_node_extent(id) | |
1173 | } | |
1174 | } | |
1175 | ||
1176 | fn create_item_scope_if_needed(&mut self, id: ast::NodeId) { | |
1177 | // create a region for the destruction scope - this is needed | |
1178 | // for constructing parameter environments based on the item. | |
1179 | // functions put their destruction scopes *inside* their parameter | |
1180 | // scopes. | |
1181 | let scope = CodeExtentData::DestructionScope(id); | |
1182 | if !self.region_maps.code_extent_interner.borrow().contains_key(&scope) { | |
1183 | self.region_maps.intern_code_extent(scope, ROOT_CODE_EXTENT); | |
1184 | } | |
1185 | } | |
1186 | } | |
223e47cc | 1187 | |
e9174d1e | 1188 | impl<'a, 'v> Visitor<'v> for RegionResolutionVisitor<'a> { |
1a4d82fc JJ |
1189 | fn visit_block(&mut self, b: &Block) { |
1190 | resolve_block(self, b); | |
223e47cc LB |
1191 | } |
1192 | ||
1a4d82fc JJ |
1193 | fn visit_item(&mut self, i: &Item) { |
1194 | resolve_item(self, i); | |
223e47cc | 1195 | } |
223e47cc | 1196 | |
e9174d1e | 1197 | fn visit_impl_item(&mut self, ii: &hir::ImplItem) { |
92a42be0 | 1198 | intravisit::walk_impl_item(self, ii); |
e9174d1e SL |
1199 | self.create_item_scope_if_needed(ii.id); |
1200 | } | |
1201 | ||
1202 | fn visit_trait_item(&mut self, ti: &hir::TraitItem) { | |
92a42be0 | 1203 | intravisit::walk_trait_item(self, ti); |
e9174d1e SL |
1204 | self.create_item_scope_if_needed(ti.id); |
1205 | } | |
1206 | ||
1a4d82fc JJ |
1207 | fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v FnDecl, |
1208 | b: &'v Block, s: Span, n: NodeId) { | |
1209 | resolve_fn(self, fk, fd, b, s, n); | |
1210 | } | |
1211 | fn visit_arm(&mut self, a: &Arm) { | |
1212 | resolve_arm(self, a); | |
1213 | } | |
1214 | fn visit_pat(&mut self, p: &Pat) { | |
1215 | resolve_pat(self, p); | |
1216 | } | |
1217 | fn visit_stmt(&mut self, s: &Stmt) { | |
1218 | resolve_stmt(self, s); | |
1219 | } | |
1220 | fn visit_expr(&mut self, ex: &Expr) { | |
1221 | resolve_expr(self, ex); | |
1222 | } | |
1223 | fn visit_local(&mut self, l: &Local) { | |
1224 | resolve_local(self, l); | |
1225 | } | |
223e47cc LB |
1226 | } |
1227 | ||
7453a54e SL |
1228 | pub fn resolve_crate(sess: &Session, map: &ast_map::Map) -> RegionMaps { |
1229 | let _task = map.dep_graph.in_task(DepNode::RegionResolveCrate); | |
1230 | let krate = map.krate(); | |
1231 | ||
1a4d82fc | 1232 | let maps = RegionMaps { |
e9174d1e SL |
1233 | code_extents: RefCell::new(vec![]), |
1234 | code_extent_interner: RefCell::new(FnvHashMap()), | |
1235 | scope_map: RefCell::new(vec![]), | |
85aaf69f | 1236 | var_map: RefCell::new(NodeMap()), |
85aaf69f | 1237 | rvalue_scopes: RefCell::new(NodeMap()), |
c34b1796 | 1238 | fn_tree: RefCell::new(NodeMap()), |
223e47cc | 1239 | }; |
e9174d1e SL |
1240 | let root_extent = maps.bogus_code_extent( |
1241 | CodeExtentData::DestructionScope(ast::DUMMY_NODE_ID)); | |
1242 | assert_eq!(root_extent, ROOT_CODE_EXTENT); | |
1243 | let bogus_extent = maps.bogus_code_extent( | |
1244 | CodeExtentData::Misc(ast::DUMMY_NODE_ID)); | |
1245 | assert_eq!(bogus_extent, DUMMY_CODE_EXTENT); | |
223e47cc | 1246 | { |
1a4d82fc JJ |
1247 | let mut visitor = RegionResolutionVisitor { |
1248 | sess: sess, | |
1249 | region_maps: &maps, | |
85aaf69f | 1250 | cx: Context { |
c34b1796 | 1251 | root_id: None, |
e9174d1e SL |
1252 | parent: ROOT_CODE_EXTENT, |
1253 | var_parent: ROOT_CODE_EXTENT | |
1254 | }, | |
1255 | terminating_scopes: NodeSet() | |
1a4d82fc | 1256 | }; |
92a42be0 | 1257 | krate.visit_all_items(&mut visitor); |
223e47cc | 1258 | } |
1a4d82fc JJ |
1259 | return maps; |
1260 | } | |
223e47cc | 1261 | |
1a4d82fc JJ |
1262 | pub fn resolve_inlined_item(sess: &Session, |
1263 | region_maps: &RegionMaps, | |
e9174d1e | 1264 | item: &InlinedItem) { |
1a4d82fc JJ |
1265 | let mut visitor = RegionResolutionVisitor { |
1266 | sess: sess, | |
1267 | region_maps: region_maps, | |
85aaf69f | 1268 | cx: Context { |
c34b1796 | 1269 | root_id: None, |
e9174d1e SL |
1270 | parent: ROOT_CODE_EXTENT, |
1271 | var_parent: ROOT_CODE_EXTENT | |
1272 | }, | |
1273 | terminating_scopes: NodeSet() | |
1a4d82fc | 1274 | }; |
e9174d1e | 1275 | item.visit(&mut visitor); |
223e47cc | 1276 | } |