]>
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}; |
54a0048b | 23 | use ty; |
1a4d82fc JJ |
24 | |
25 | use std::cell::RefCell; | |
e9174d1e SL |
26 | use std::collections::hash_map::Entry; |
27 | use std::fmt; | |
28 | use std::mem; | |
3157f602 | 29 | use syntax::codemap; |
e9174d1e | 30 | use syntax::ast::{self, NodeId}; |
3157f602 | 31 | use syntax_pos::Span; |
e9174d1e | 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; |
9e0c209e | 239 | Some(Span { lo: stmt_span.hi, hi: blk.span.hi, expn_id: stmt_span.expn_id }) |
85aaf69f SL |
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); | |
a7813a04 | 392 | debug!("CodeExtent({}) = {:?} [parent={}]", idx.0, e, parent.0); |
e9174d1e SL |
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 | 480 | // check for a designated rvalue scope |
c30ab7b3 SL |
481 | if let Some(&s) = self.rvalue_scopes.borrow().get(&expr_id) { |
482 | debug!("temporary_scope({:?}) = {:?} [custom]", expr_id, s); | |
483 | return Some(s); | |
970d7e83 | 484 | } |
1a4d82fc | 485 | |
e9174d1e SL |
486 | let scope_map : &[CodeExtent] = &self.scope_map.borrow(); |
487 | let code_extents: &[CodeExtentData] = &self.code_extents.borrow(); | |
488 | ||
1a4d82fc JJ |
489 | // else, locate the innermost terminating scope |
490 | // if there's one. Static items, for instance, won't | |
491 | // have an enclosing scope, hence no scope will be | |
492 | // returned. | |
e9174d1e SL |
493 | let expr_extent = self.node_extent(expr_id); |
494 | // For some reason, the expr's scope itself is skipped here. | |
495 | let mut id = match scope_map[expr_extent.0 as usize].into_option() { | |
1a4d82fc | 496 | Some(i) => i, |
e9174d1e | 497 | _ => return None |
1a4d82fc JJ |
498 | }; |
499 | ||
e9174d1e SL |
500 | while let Some(p) = scope_map[id.0 as usize].into_option() { |
501 | match code_extents[p.0 as usize] { | |
502 | CodeExtentData::DestructionScope(..) => { | |
503 | debug!("temporary_scope({:?}) = {:?} [enclosing]", | |
504 | expr_id, id); | |
505 | return Some(id); | |
1a4d82fc | 506 | } |
e9174d1e | 507 | _ => id = p |
1a4d82fc JJ |
508 | } |
509 | } | |
e9174d1e SL |
510 | |
511 | debug!("temporary_scope({:?}) = None", expr_id); | |
512 | return None; | |
970d7e83 LB |
513 | } |
514 | ||
1a4d82fc JJ |
515 | pub fn var_region(&self, id: ast::NodeId) -> ty::Region { |
516 | //! Returns the lifetime of the variable `id`. | |
970d7e83 | 517 | |
1a4d82fc JJ |
518 | let scope = ty::ReScope(self.var_scope(id)); |
519 | debug!("var_region({:?}) = {:?}", id, scope); | |
520 | scope | |
970d7e83 LB |
521 | } |
522 | ||
1a4d82fc | 523 | pub fn scopes_intersect(&self, scope1: CodeExtent, scope2: CodeExtent) |
970d7e83 LB |
524 | -> bool { |
525 | self.is_subscope_of(scope1, scope2) || | |
526 | self.is_subscope_of(scope2, scope1) | |
527 | } | |
528 | ||
1a4d82fc JJ |
529 | /// Returns true if `subscope` is equal to or is lexically nested inside `superscope` and false |
530 | /// otherwise. | |
970d7e83 | 531 | pub fn is_subscope_of(&self, |
1a4d82fc JJ |
532 | subscope: CodeExtent, |
533 | superscope: CodeExtent) | |
970d7e83 | 534 | -> bool { |
970d7e83 | 535 | let mut s = subscope; |
e9174d1e | 536 | debug!("is_subscope_of({:?}, {:?})", subscope, superscope); |
970d7e83 | 537 | while superscope != s { |
e9174d1e | 538 | match self.opt_encl_scope(s) { |
970d7e83 | 539 | None => { |
1a4d82fc | 540 | debug!("is_subscope_of({:?}, {:?}, s={:?})=false", |
970d7e83 | 541 | subscope, superscope, s); |
970d7e83 LB |
542 | return false; |
543 | } | |
e9174d1e | 544 | Some(scope) => s = scope |
223e47cc LB |
545 | } |
546 | } | |
223e47cc | 547 | |
1a4d82fc | 548 | debug!("is_subscope_of({:?}, {:?})=true", |
970d7e83 LB |
549 | subscope, superscope); |
550 | ||
551 | return true; | |
552 | } | |
553 | ||
1a4d82fc JJ |
554 | /// Finds the nearest common ancestor (if any) of two scopes. That is, finds the smallest |
555 | /// scope which is greater than or equal to both `scope_a` and `scope_b`. | |
970d7e83 | 556 | pub fn nearest_common_ancestor(&self, |
1a4d82fc JJ |
557 | scope_a: CodeExtent, |
558 | scope_b: CodeExtent) | |
c34b1796 AL |
559 | -> CodeExtent { |
560 | if scope_a == scope_b { return scope_a; } | |
970d7e83 | 561 | |
e9174d1e SL |
562 | let mut a_buf: [CodeExtent; 32] = [ROOT_CODE_EXTENT; 32]; |
563 | let mut a_vec: Vec<CodeExtent> = vec![]; | |
564 | let mut b_buf: [CodeExtent; 32] = [ROOT_CODE_EXTENT; 32]; | |
565 | let mut b_vec: Vec<CodeExtent> = vec![]; | |
566 | let scope_map : &[CodeExtent] = &self.scope_map.borrow(); | |
567 | let a_ancestors = ancestors_of(scope_map, | |
568 | scope_a, &mut a_buf, &mut a_vec); | |
569 | let b_ancestors = ancestors_of(scope_map, | |
570 | scope_b, &mut b_buf, &mut b_vec); | |
85aaf69f SL |
571 | let mut a_index = a_ancestors.len() - 1; |
572 | let mut b_index = b_ancestors.len() - 1; | |
970d7e83 | 573 | |
c34b1796 | 574 | // Here, [ab]_ancestors is a vector going from narrow to broad. |
970d7e83 LB |
575 | // The end of each vector will be the item where the scope is |
576 | // defined; if there are any common ancestors, then the tails of | |
577 | // the vector will be the same. So basically we want to walk | |
578 | // backwards from the tail of each vector and find the first point | |
579 | // where they diverge. If one vector is a suffix of the other, | |
580 | // then the corresponding scope is a superscope of the other. | |
581 | ||
223e47cc | 582 | if a_ancestors[a_index] != b_ancestors[b_index] { |
c34b1796 AL |
583 | // In this case, the two regions belong to completely |
584 | // different functions. Compare those fn for lexical | |
585 | // nesting. The reasoning behind this is subtle. See the | |
586 | // "Modeling closures" section of the README in | |
54a0048b | 587 | // infer::region_inference for more details. |
e9174d1e SL |
588 | let a_root_scope = self.code_extent_data(a_ancestors[a_index]); |
589 | let b_root_scope = self.code_extent_data(a_ancestors[a_index]); | |
c34b1796 | 590 | return match (a_root_scope, b_root_scope) { |
e9174d1e SL |
591 | (CodeExtentData::DestructionScope(a_root_id), |
592 | CodeExtentData::DestructionScope(b_root_id)) => { | |
c34b1796 AL |
593 | if self.fn_is_enclosed_by(a_root_id, b_root_id) { |
594 | // `a` is enclosed by `b`, hence `b` is the ancestor of everything in `a` | |
595 | scope_b | |
596 | } else if self.fn_is_enclosed_by(b_root_id, a_root_id) { | |
597 | // `b` is enclosed by `a`, hence `a` is the ancestor of everything in `b` | |
598 | scope_a | |
599 | } else { | |
600 | // neither fn encloses the other | |
54a0048b | 601 | bug!() |
c34b1796 AL |
602 | } |
603 | } | |
604 | _ => { | |
605 | // root ids are always Misc right now | |
54a0048b | 606 | bug!() |
c34b1796 AL |
607 | } |
608 | }; | |
223e47cc | 609 | } |
223e47cc | 610 | |
970d7e83 LB |
611 | loop { |
612 | // Loop invariant: a_ancestors[a_index] == b_ancestors[b_index] | |
613 | // for all indices between a_index and the end of the array | |
c34b1796 AL |
614 | if a_index == 0 { return scope_a; } |
615 | if b_index == 0 { return scope_b; } | |
85aaf69f SL |
616 | a_index -= 1; |
617 | b_index -= 1; | |
970d7e83 | 618 | if a_ancestors[a_index] != b_ancestors[b_index] { |
c34b1796 | 619 | return a_ancestors[a_index + 1]; |
970d7e83 LB |
620 | } |
621 | } | |
622 | ||
e9174d1e SL |
623 | fn ancestors_of<'a>(scope_map: &[CodeExtent], |
624 | scope: CodeExtent, | |
625 | buf: &'a mut [CodeExtent; 32], | |
626 | vec: &'a mut Vec<CodeExtent>) -> &'a [CodeExtent] { | |
1a4d82fc | 627 | // debug!("ancestors_of(scope={:?})", scope); |
970d7e83 | 628 | let mut scope = scope; |
e9174d1e SL |
629 | |
630 | let mut i = 0; | |
631 | while i < 32 { | |
632 | buf[i] = scope; | |
633 | match scope_map[scope.0 as usize].into_option() { | |
634 | Some(superscope) => scope = superscope, | |
635 | _ => return &buf[..i+1] | |
636 | } | |
637 | i += 1; | |
638 | } | |
639 | ||
640 | *vec = Vec::with_capacity(64); | |
92a42be0 | 641 | vec.extend_from_slice(buf); |
970d7e83 | 642 | loop { |
e9174d1e SL |
643 | vec.push(scope); |
644 | match scope_map[scope.0 as usize].into_option() { | |
645 | Some(superscope) => scope = superscope, | |
646 | _ => return &*vec | |
970d7e83 | 647 | } |
970d7e83 LB |
648 | } |
649 | } | |
223e47cc LB |
650 | } |
651 | } | |
652 | ||
1a4d82fc JJ |
653 | /// Records the lifetime of a local variable as `cx.var_parent` |
654 | fn record_var_lifetime(visitor: &mut RegionResolutionVisitor, | |
655 | var_id: ast::NodeId, | |
656 | _sp: Span) { | |
e9174d1e SL |
657 | match visitor.cx.var_parent { |
658 | ROOT_CODE_EXTENT => { | |
1a4d82fc JJ |
659 | // this can happen in extern fn declarations like |
660 | // | |
661 | // extern fn isalnum(c: c_int) -> c_int | |
662 | } | |
e9174d1e SL |
663 | parent_scope => |
664 | visitor.region_maps.record_var_scope(var_id, parent_scope), | |
1a4d82fc JJ |
665 | } |
666 | } | |
667 | ||
e9174d1e | 668 | fn resolve_block(visitor: &mut RegionResolutionVisitor, blk: &hir::Block) { |
1a4d82fc JJ |
669 | debug!("resolve_block(blk.id={:?})", blk.id); |
670 | ||
85aaf69f | 671 | let prev_cx = visitor.cx; |
e9174d1e | 672 | let block_extent = visitor.new_node_extent_with_dtor(blk.id); |
223e47cc | 673 | |
1a4d82fc JJ |
674 | // We treat the tail expression in the block (if any) somewhat |
675 | // differently from the statements. The issue has to do with | |
85aaf69f SL |
676 | // temporary lifetimes. Consider the following: |
677 | // | |
678 | // quux({ | |
679 | // let inner = ... (&bar()) ...; | |
680 | // | |
681 | // (... (&foo()) ...) // (the tail expression) | |
682 | // }, other_argument()); | |
1a4d82fc | 683 | // |
85aaf69f SL |
684 | // Each of the statements within the block is a terminating |
685 | // scope, and thus a temporary (e.g. the result of calling | |
686 | // `bar()` in the initalizer expression for `let inner = ...;`) | |
687 | // will be cleaned up immediately after its corresponding | |
688 | // statement (i.e. `let inner = ...;`) executes. | |
1a4d82fc | 689 | // |
85aaf69f SL |
690 | // On the other hand, temporaries associated with evaluating the |
691 | // tail expression for the block are assigned lifetimes so that | |
692 | // they will be cleaned up as part of the terminating scope | |
693 | // *surrounding* the block expression. Here, the terminating | |
694 | // scope for the block expression is the `quux(..)` call; so | |
695 | // those temporaries will only be cleaned up *after* both | |
696 | // `other_argument()` has run and also the call to `quux(..)` | |
697 | // itself has returned. | |
698 | ||
699 | visitor.cx = Context { | |
c34b1796 | 700 | root_id: prev_cx.root_id, |
e9174d1e SL |
701 | var_parent: block_extent, |
702 | parent: block_extent, | |
85aaf69f SL |
703 | }; |
704 | ||
705 | { | |
706 | // This block should be kept approximately in sync with | |
92a42be0 | 707 | // `intravisit::walk_block`. (We manually walk the block, rather |
85aaf69f | 708 | // than call `walk_block`, in order to maintain precise |
e9174d1e | 709 | // index information.) |
85aaf69f SL |
710 | |
711 | for (i, statement) in blk.stmts.iter().enumerate() { | |
e9174d1e | 712 | if let hir::StmtDecl(..) = statement.node { |
85aaf69f SL |
713 | // Each StmtDecl introduces a subscope for bindings |
714 | // introduced by the declaration; this subscope covers | |
715 | // a suffix of the block . Each subscope in a block | |
716 | // has the previous subscope in the block as a parent, | |
717 | // except for the first such subscope, which has the | |
718 | // block itself as a parent. | |
e9174d1e SL |
719 | let stmt_extent = visitor.new_code_extent( |
720 | CodeExtentData::Remainder(BlockRemainder { | |
721 | block: blk.id, | |
722 | first_statement_index: i as u32 | |
723 | }) | |
724 | ); | |
85aaf69f | 725 | visitor.cx = Context { |
c34b1796 | 726 | root_id: prev_cx.root_id, |
e9174d1e SL |
727 | var_parent: stmt_extent, |
728 | parent: stmt_extent, | |
85aaf69f SL |
729 | }; |
730 | } | |
92a42be0 | 731 | visitor.visit_stmt(statement) |
85aaf69f | 732 | } |
b039eaaf | 733 | walk_list!(visitor, visit_expr, &blk.expr); |
85aaf69f | 734 | } |
223e47cc | 735 | |
1a4d82fc | 736 | visitor.cx = prev_cx; |
223e47cc LB |
737 | } |
738 | ||
e9174d1e SL |
739 | fn resolve_arm(visitor: &mut RegionResolutionVisitor, arm: &hir::Arm) { |
740 | visitor.terminating_scopes.insert(arm.body.id); | |
223e47cc | 741 | |
e9174d1e SL |
742 | if let Some(ref expr) = arm.guard { |
743 | visitor.terminating_scopes.insert(expr.id); | |
223e47cc | 744 | } |
1a4d82fc | 745 | |
92a42be0 | 746 | intravisit::walk_arm(visitor, arm); |
223e47cc LB |
747 | } |
748 | ||
e9174d1e SL |
749 | fn resolve_pat(visitor: &mut RegionResolutionVisitor, pat: &hir::Pat) { |
750 | visitor.new_node_extent(pat.id); | |
223e47cc | 751 | |
3157f602 XL |
752 | // If this is a binding then record the lifetime of that binding. |
753 | if let PatKind::Binding(..) = pat.node { | |
754 | record_var_lifetime(visitor, pat.id, pat.span); | |
1a4d82fc | 755 | } |
970d7e83 | 756 | |
92a42be0 | 757 | intravisit::walk_pat(visitor, pat); |
1a4d82fc | 758 | } |
970d7e83 | 759 | |
e9174d1e | 760 | fn resolve_stmt(visitor: &mut RegionResolutionVisitor, stmt: &hir::Stmt) { |
54a0048b | 761 | let stmt_id = stmt.node.id(); |
1a4d82fc | 762 | debug!("resolve_stmt(stmt.id={:?})", stmt_id); |
223e47cc | 763 | |
85aaf69f SL |
764 | // Every statement will clean up the temporaries created during |
765 | // execution of that statement. Therefore each statement has an | |
766 | // associated destruction scope that represents the extent of the | |
767 | // statement plus its destructors, and thus the extent for which | |
768 | // regions referenced by the destructors need to survive. | |
e9174d1e SL |
769 | visitor.terminating_scopes.insert(stmt_id); |
770 | let stmt_extent = visitor.new_node_extent_with_dtor(stmt_id); | |
223e47cc | 771 | |
1a4d82fc | 772 | let prev_parent = visitor.cx.parent; |
e9174d1e | 773 | visitor.cx.parent = stmt_extent; |
92a42be0 | 774 | intravisit::walk_stmt(visitor, stmt); |
1a4d82fc | 775 | visitor.cx.parent = prev_parent; |
223e47cc LB |
776 | } |
777 | ||
e9174d1e | 778 | fn resolve_expr(visitor: &mut RegionResolutionVisitor, expr: &hir::Expr) { |
1a4d82fc | 779 | debug!("resolve_expr(expr.id={:?})", expr.id); |
223e47cc | 780 | |
e9174d1e | 781 | let expr_extent = visitor.new_node_extent_with_dtor(expr.id); |
1a4d82fc | 782 | let prev_cx = visitor.cx; |
e9174d1e | 783 | visitor.cx.parent = expr_extent; |
970d7e83 | 784 | |
1a4d82fc | 785 | { |
e9174d1e SL |
786 | let terminating_scopes = &mut visitor.terminating_scopes; |
787 | let mut terminating = |id: ast::NodeId| { | |
788 | terminating_scopes.insert(id); | |
1a4d82fc JJ |
789 | }; |
790 | match expr.node { | |
791 | // Conditional or repeating scopes are always terminating | |
792 | // scopes, meaning that temporaries cannot outlive them. | |
793 | // This ensures fixed size stacks. | |
794 | ||
e9174d1e SL |
795 | hir::ExprBinary(codemap::Spanned { node: hir::BiAnd, .. }, _, ref r) | |
796 | hir::ExprBinary(codemap::Spanned { node: hir::BiOr, .. }, _, ref r) => { | |
1a4d82fc JJ |
797 | // For shortcircuiting operators, mark the RHS as a terminating |
798 | // scope since it only executes conditionally. | |
e9174d1e | 799 | terminating(r.id); |
1a4d82fc | 800 | } |
223e47cc | 801 | |
9e0c209e SL |
802 | hir::ExprIf(ref expr, ref then, Some(ref otherwise)) => { |
803 | terminating(expr.id); | |
e9174d1e SL |
804 | terminating(then.id); |
805 | terminating(otherwise.id); | |
1a4d82fc | 806 | } |
223e47cc | 807 | |
e9174d1e SL |
808 | hir::ExprIf(ref expr, ref then, None) => { |
809 | terminating(expr.id); | |
810 | terminating(then.id); | |
1a4d82fc | 811 | } |
223e47cc | 812 | |
e9174d1e SL |
813 | hir::ExprLoop(ref body, _) => { |
814 | terminating(body.id); | |
1a4d82fc | 815 | } |
223e47cc | 816 | |
e9174d1e SL |
817 | hir::ExprWhile(ref expr, ref body, _) => { |
818 | terminating(expr.id); | |
819 | terminating(body.id); | |
1a4d82fc | 820 | } |
223e47cc | 821 | |
e9174d1e SL |
822 | hir::ExprMatch(..) => { |
823 | visitor.cx.var_parent = expr_extent; | |
1a4d82fc | 824 | } |
223e47cc | 825 | |
e9174d1e SL |
826 | hir::ExprAssignOp(..) | hir::ExprIndex(..) | |
827 | hir::ExprUnary(..) | hir::ExprCall(..) | hir::ExprMethodCall(..) => { | |
1a4d82fc JJ |
828 | // FIXME(#6268) Nested method calls |
829 | // | |
830 | // The lifetimes for a call or method call look as follows: | |
831 | // | |
832 | // call.id | |
833 | // - arg0.id | |
834 | // - ... | |
835 | // - argN.id | |
836 | // - call.callee_id | |
837 | // | |
838 | // The idea is that call.callee_id represents *the time when | |
839 | // the invoked function is actually running* and call.id | |
840 | // represents *the time to prepare the arguments and make the | |
c34b1796 | 841 | // call*. See the section "Borrows in Calls" borrowck/README.md |
1a4d82fc JJ |
842 | // for an extended explanation of why this distinction is |
843 | // important. | |
844 | // | |
845 | // record_superlifetime(new_cx, expr.callee_id); | |
846 | } | |
223e47cc | 847 | |
1a4d82fc JJ |
848 | _ => {} |
849 | } | |
223e47cc | 850 | } |
223e47cc | 851 | |
92a42be0 | 852 | intravisit::walk_expr(visitor, expr); |
1a4d82fc | 853 | visitor.cx = prev_cx; |
223e47cc LB |
854 | } |
855 | ||
e9174d1e | 856 | fn resolve_local(visitor: &mut RegionResolutionVisitor, local: &hir::Local) { |
1a4d82fc JJ |
857 | debug!("resolve_local(local.id={:?},local.init={:?})", |
858 | local.id,local.init.is_some()); | |
223e47cc | 859 | |
1a4d82fc JJ |
860 | // For convenience in trans, associate with the local-id the var |
861 | // scope that will be used for any bindings declared in this | |
862 | // pattern. | |
e9174d1e SL |
863 | let blk_scope = visitor.cx.var_parent; |
864 | assert!(blk_scope != ROOT_CODE_EXTENT); // locals must be within a block | |
1a4d82fc | 865 | visitor.region_maps.record_var_scope(local.id, blk_scope); |
223e47cc | 866 | |
1a4d82fc JJ |
867 | // As an exception to the normal rules governing temporary |
868 | // lifetimes, initializers in a let have a temporary lifetime | |
869 | // of the enclosing block. This means that e.g. a program | |
870 | // like the following is legal: | |
223e47cc | 871 | // |
1a4d82fc | 872 | // let ref x = HashMap::new(); |
223e47cc | 873 | // |
1a4d82fc | 874 | // Because the hash map will be freed in the enclosing block. |
223e47cc | 875 | // |
1a4d82fc JJ |
876 | // We express the rules more formally based on 3 grammars (defined |
877 | // fully in the helpers below that implement them): | |
223e47cc | 878 | // |
1a4d82fc JJ |
879 | // 1. `E&`, which matches expressions like `&<rvalue>` that |
880 | // own a pointer into the stack. | |
223e47cc | 881 | // |
1a4d82fc JJ |
882 | // 2. `P&`, which matches patterns like `ref x` or `(ref x, ref |
883 | // y)` that produce ref bindings into the value they are | |
884 | // matched against or something (at least partially) owned by | |
885 | // the value they are matched against. (By partially owned, | |
886 | // I mean that creating a binding into a ref-counted or managed value | |
887 | // would still count.) | |
223e47cc | 888 | // |
1a4d82fc JJ |
889 | // 3. `ET`, which matches both rvalues like `foo()` as well as lvalues |
890 | // based on rvalues like `foo().x[2].y`. | |
223e47cc | 891 | // |
1a4d82fc JJ |
892 | // A subexpression `<rvalue>` that appears in a let initializer |
893 | // `let pat [: ty] = expr` has an extended temporary lifetime if | |
894 | // any of the following conditions are met: | |
895 | // | |
896 | // A. `pat` matches `P&` and `expr` matches `ET` | |
897 | // (covers cases where `pat` creates ref bindings into an rvalue | |
898 | // produced by `expr`) | |
899 | // B. `ty` is a borrowed pointer and `expr` matches `ET` | |
900 | // (covers cases where coercion creates a borrow) | |
901 | // C. `expr` matches `E&` | |
902 | // (covers cases `expr` borrows an rvalue that is then assigned | |
903 | // to memory (at least partially) owned by the binding) | |
904 | // | |
905 | // Here are some examples hopefully giving an intuition where each | |
906 | // rule comes into play and why: | |
907 | // | |
908 | // Rule A. `let (ref x, ref y) = (foo().x, 44)`. The rvalue `(22, 44)` | |
909 | // would have an extended lifetime, but not `foo()`. | |
910 | // | |
911 | // Rule B. `let x: &[...] = [foo().x]`. The rvalue `[foo().x]` | |
912 | // would have an extended lifetime, but not `foo()`. | |
913 | // | |
914 | // Rule C. `let x = &foo().x`. The rvalue ``foo()` would have extended | |
915 | // lifetime. | |
916 | // | |
917 | // In some cases, multiple rules may apply (though not to the same | |
918 | // rvalue). For example: | |
919 | // | |
920 | // let ref x = [&a(), &b()]; | |
921 | // | |
922 | // Here, the expression `[...]` has an extended lifetime due to rule | |
923 | // A, but the inner rvalues `a()` and `b()` have an extended lifetime | |
924 | // due to rule C. | |
925 | // | |
926 | // FIXME(#6308) -- Note that `[]` patterns work more smoothly post-DST. | |
927 | ||
c30ab7b3 SL |
928 | if let Some(ref expr) = local.init { |
929 | record_rvalue_scope_if_borrow_expr(visitor, &expr, blk_scope); | |
1a4d82fc | 930 | |
c30ab7b3 SL |
931 | let is_borrow = |
932 | if let Some(ref ty) = local.ty { is_borrowed_ty(&ty) } else { false }; | |
1a4d82fc | 933 | |
c30ab7b3 SL |
934 | if is_binding_pat(&local.pat) || is_borrow { |
935 | record_rvalue_scope(visitor, &expr, blk_scope); | |
223e47cc | 936 | } |
223e47cc | 937 | } |
223e47cc | 938 | |
92a42be0 | 939 | intravisit::walk_local(visitor, local); |
1a4d82fc JJ |
940 | |
941 | /// True if `pat` match the `P&` nonterminal: | |
942 | /// | |
943 | /// P& = ref X | |
944 | /// | StructName { ..., P&, ... } | |
945 | /// | VariantName(..., P&, ...) | |
946 | /// | [ ..., P&, ... ] | |
947 | /// | ( ..., P&, ... ) | |
948 | /// | box P& | |
e9174d1e | 949 | fn is_binding_pat(pat: &hir::Pat) -> bool { |
1a4d82fc | 950 | match pat.node { |
9e0c209e | 951 | PatKind::Binding(hir::BindByRef(_), ..) => true, |
223e47cc | 952 | |
7453a54e SL |
953 | PatKind::Struct(_, ref field_pats, _) => { |
954 | field_pats.iter().any(|fp| is_binding_pat(&fp.node.pat)) | |
223e47cc | 955 | } |
1a4d82fc | 956 | |
c30ab7b3 | 957 | PatKind::Slice(ref pats1, ref pats2, ref pats3) => { |
7453a54e SL |
958 | pats1.iter().any(|p| is_binding_pat(&p)) || |
959 | pats2.iter().any(|p| is_binding_pat(&p)) || | |
960 | pats3.iter().any(|p| is_binding_pat(&p)) | |
1a4d82fc JJ |
961 | } |
962 | ||
3157f602 XL |
963 | PatKind::TupleStruct(_, ref subpats, _) | |
964 | PatKind::Tuple(ref subpats, _) => { | |
7453a54e | 965 | subpats.iter().any(|p| is_binding_pat(&p)) |
1a4d82fc JJ |
966 | } |
967 | ||
7453a54e SL |
968 | PatKind::Box(ref subpat) => { |
969 | is_binding_pat(&subpat) | |
1a4d82fc JJ |
970 | } |
971 | ||
972 | _ => false, | |
223e47cc | 973 | } |
223e47cc | 974 | } |
223e47cc | 975 | |
1a4d82fc | 976 | /// True if `ty` is a borrowed pointer type like `&int` or `&[...]`. |
e9174d1e | 977 | fn is_borrowed_ty(ty: &hir::Ty) -> bool { |
1a4d82fc | 978 | match ty.node { |
e9174d1e | 979 | hir::TyRptr(..) => true, |
1a4d82fc JJ |
980 | _ => false |
981 | } | |
223e47cc | 982 | } |
223e47cc | 983 | |
1a4d82fc JJ |
984 | /// If `expr` matches the `E&` grammar, then records an extended rvalue scope as appropriate: |
985 | /// | |
986 | /// E& = & ET | |
987 | /// | StructName { ..., f: E&, ... } | |
988 | /// | [ ..., E&, ... ] | |
989 | /// | ( ..., E&, ... ) | |
990 | /// | {...; E&} | |
991 | /// | box E& | |
992 | /// | E& as ... | |
993 | /// | ( E& ) | |
994 | fn record_rvalue_scope_if_borrow_expr(visitor: &mut RegionResolutionVisitor, | |
e9174d1e | 995 | expr: &hir::Expr, |
1a4d82fc JJ |
996 | blk_id: CodeExtent) { |
997 | match expr.node { | |
e9174d1e | 998 | hir::ExprAddrOf(_, ref subexpr) => { |
7453a54e SL |
999 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id); |
1000 | record_rvalue_scope(visitor, &subexpr, blk_id); | |
223e47cc | 1001 | } |
e9174d1e | 1002 | hir::ExprStruct(_, ref fields, _) => { |
85aaf69f | 1003 | for field in fields { |
1a4d82fc | 1004 | record_rvalue_scope_if_borrow_expr( |
7453a54e | 1005 | visitor, &field.expr, blk_id); |
223e47cc | 1006 | } |
1a4d82fc | 1007 | } |
c30ab7b3 | 1008 | hir::ExprArray(ref subexprs) | |
e9174d1e | 1009 | hir::ExprTup(ref subexprs) => { |
85aaf69f | 1010 | for subexpr in subexprs { |
1a4d82fc | 1011 | record_rvalue_scope_if_borrow_expr( |
7453a54e | 1012 | visitor, &subexpr, blk_id); |
1a4d82fc JJ |
1013 | } |
1014 | } | |
b039eaaf | 1015 | hir::ExprCast(ref subexpr, _) => { |
7453a54e | 1016 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id) |
1a4d82fc | 1017 | } |
e9174d1e | 1018 | hir::ExprBlock(ref block) => { |
c30ab7b3 SL |
1019 | if let Some(ref subexpr) = block.expr { |
1020 | record_rvalue_scope_if_borrow_expr( | |
1021 | visitor, &subexpr, blk_id); | |
223e47cc LB |
1022 | } |
1023 | } | |
c30ab7b3 | 1024 | _ => {} |
223e47cc | 1025 | } |
1a4d82fc | 1026 | } |
223e47cc | 1027 | |
1a4d82fc JJ |
1028 | /// Applied to an expression `expr` if `expr` -- or something owned or partially owned by |
1029 | /// `expr` -- is going to be indirectly referenced by a variable in a let statement. In that | |
1030 | /// case, the "temporary lifetime" or `expr` is extended to be the block enclosing the `let` | |
1031 | /// statement. | |
1032 | /// | |
1033 | /// More formally, if `expr` matches the grammar `ET`, record the rvalue scope of the matching | |
1034 | /// `<rvalue>` as `blk_id`: | |
1035 | /// | |
1036 | /// ET = *ET | |
1037 | /// | ET[...] | |
1038 | /// | ET.f | |
1039 | /// | (ET) | |
1040 | /// | <rvalue> | |
1041 | /// | |
1042 | /// Note: ET is intended to match "rvalues or lvalues based on rvalues". | |
1043 | fn record_rvalue_scope<'a>(visitor: &mut RegionResolutionVisitor, | |
e9174d1e | 1044 | expr: &'a hir::Expr, |
1a4d82fc JJ |
1045 | blk_scope: CodeExtent) { |
1046 | let mut expr = expr; | |
1047 | loop { | |
1048 | // Note: give all the expressions matching `ET` with the | |
1049 | // extended temporary lifetime, not just the innermost rvalue, | |
1050 | // because in trans if we must compile e.g. `*rvalue()` | |
1051 | // into a temporary, we request the temporary scope of the | |
1052 | // outer expression. | |
1053 | visitor.region_maps.record_rvalue_scope(expr.id, blk_scope); | |
1054 | ||
1055 | match expr.node { | |
e9174d1e SL |
1056 | hir::ExprAddrOf(_, ref subexpr) | |
1057 | hir::ExprUnary(hir::UnDeref, ref subexpr) | | |
1058 | hir::ExprField(ref subexpr, _) | | |
1059 | hir::ExprTupField(ref subexpr, _) | | |
b039eaaf | 1060 | hir::ExprIndex(ref subexpr, _) => { |
7453a54e | 1061 | expr = &subexpr; |
223e47cc | 1062 | } |
1a4d82fc JJ |
1063 | _ => { |
1064 | return; | |
223e47cc LB |
1065 | } |
1066 | } | |
223e47cc | 1067 | } |
223e47cc | 1068 | } |
1a4d82fc | 1069 | } |
223e47cc | 1070 | |
e9174d1e | 1071 | fn resolve_item(visitor: &mut RegionResolutionVisitor, item: &hir::Item) { |
1a4d82fc JJ |
1072 | // Items create a new outer block scope as far as we're concerned. |
1073 | let prev_cx = visitor.cx; | |
e9174d1e | 1074 | let prev_ts = mem::replace(&mut visitor.terminating_scopes, NodeSet()); |
85aaf69f | 1075 | visitor.cx = Context { |
c34b1796 | 1076 | root_id: None, |
e9174d1e SL |
1077 | var_parent: ROOT_CODE_EXTENT, |
1078 | parent: ROOT_CODE_EXTENT | |
85aaf69f | 1079 | }; |
92a42be0 | 1080 | intravisit::walk_item(visitor, item); |
e9174d1e | 1081 | visitor.create_item_scope_if_needed(item.id); |
1a4d82fc | 1082 | visitor.cx = prev_cx; |
e9174d1e | 1083 | visitor.terminating_scopes = prev_ts; |
1a4d82fc | 1084 | } |
223e47cc | 1085 | |
1a4d82fc | 1086 | fn resolve_fn(visitor: &mut RegionResolutionVisitor, |
e9174d1e SL |
1087 | kind: FnKind, |
1088 | decl: &hir::FnDecl, | |
1089 | body: &hir::Block, | |
1a4d82fc JJ |
1090 | sp: Span, |
1091 | id: ast::NodeId) { | |
1092 | debug!("region::resolve_fn(id={:?}, \ | |
1093 | span={:?}, \ | |
1094 | body.id={:?}, \ | |
1095 | cx.parent={:?})", | |
1096 | id, | |
1097 | visitor.sess.codemap().span_to_string(sp), | |
1098 | body.id, | |
1099 | visitor.cx.parent); | |
1100 | ||
9cc50fc6 SL |
1101 | visitor.cx.parent = visitor.new_code_extent( |
1102 | CodeExtentData::CallSiteScope { fn_id: id, body_id: body.id }); | |
1103 | ||
e9174d1e SL |
1104 | let fn_decl_scope = visitor.new_code_extent( |
1105 | CodeExtentData::ParameterScope { fn_id: id, body_id: body.id }); | |
1a4d82fc | 1106 | |
c34b1796 AL |
1107 | if let Some(root_id) = visitor.cx.root_id { |
1108 | visitor.region_maps.record_fn_parent(body.id, root_id); | |
1109 | } | |
1110 | ||
1a4d82fc | 1111 | let outer_cx = visitor.cx; |
e9174d1e SL |
1112 | let outer_ts = mem::replace(&mut visitor.terminating_scopes, NodeSet()); |
1113 | visitor.terminating_scopes.insert(body.id); | |
1a4d82fc | 1114 | |
9346a6ac | 1115 | // The arguments and `self` are parented to the fn. |
85aaf69f | 1116 | visitor.cx = Context { |
c34b1796 | 1117 | root_id: Some(body.id), |
e9174d1e SL |
1118 | parent: ROOT_CODE_EXTENT, |
1119 | var_parent: fn_decl_scope, | |
85aaf69f | 1120 | }; |
e9174d1e | 1121 | |
92a42be0 SL |
1122 | intravisit::walk_fn_decl(visitor, decl); |
1123 | intravisit::walk_fn_kind(visitor, kind); | |
1a4d82fc | 1124 | |
c34b1796 AL |
1125 | // The body of the every fn is a root scope. |
1126 | visitor.cx = Context { | |
1127 | root_id: Some(body.id), | |
e9174d1e SL |
1128 | parent: fn_decl_scope, |
1129 | var_parent: fn_decl_scope | |
c34b1796 AL |
1130 | }; |
1131 | visitor.visit_block(body); | |
1132 | ||
1133 | // Restore context we had at the start. | |
1134 | visitor.cx = outer_cx; | |
e9174d1e | 1135 | visitor.terminating_scopes = outer_ts; |
1a4d82fc JJ |
1136 | } |
1137 | ||
e9174d1e SL |
1138 | impl<'a> RegionResolutionVisitor<'a> { |
1139 | /// Records the current parent (if any) as the parent of `child_scope`. | |
1140 | fn new_code_extent(&mut self, child_scope: CodeExtentData) -> CodeExtent { | |
1141 | self.region_maps.intern_code_extent(child_scope, self.cx.parent) | |
1142 | } | |
1143 | ||
1144 | fn new_node_extent(&mut self, child_scope: ast::NodeId) -> CodeExtent { | |
1145 | self.new_code_extent(CodeExtentData::Misc(child_scope)) | |
1146 | } | |
1147 | ||
1148 | fn new_node_extent_with_dtor(&mut self, id: ast::NodeId) -> CodeExtent { | |
1149 | // If node was previously marked as a terminating scope during the | |
1150 | // recursive visit of its parent node in the AST, then we need to | |
1151 | // account for the destruction scope representing the extent of | |
1152 | // the destructors that run immediately after it completes. | |
1153 | if self.terminating_scopes.contains(&id) { | |
1154 | let ds = self.new_code_extent( | |
1155 | CodeExtentData::DestructionScope(id)); | |
1156 | self.region_maps.intern_node(id, ds) | |
1157 | } else { | |
1158 | self.new_node_extent(id) | |
1159 | } | |
1160 | } | |
1161 | ||
1162 | fn create_item_scope_if_needed(&mut self, id: ast::NodeId) { | |
1163 | // create a region for the destruction scope - this is needed | |
1164 | // for constructing parameter environments based on the item. | |
1165 | // functions put their destruction scopes *inside* their parameter | |
1166 | // scopes. | |
1167 | let scope = CodeExtentData::DestructionScope(id); | |
1168 | if !self.region_maps.code_extent_interner.borrow().contains_key(&scope) { | |
1169 | self.region_maps.intern_code_extent(scope, ROOT_CODE_EXTENT); | |
1170 | } | |
1171 | } | |
1172 | } | |
223e47cc | 1173 | |
e9174d1e | 1174 | impl<'a, 'v> Visitor<'v> for RegionResolutionVisitor<'a> { |
1a4d82fc JJ |
1175 | fn visit_block(&mut self, b: &Block) { |
1176 | resolve_block(self, b); | |
223e47cc LB |
1177 | } |
1178 | ||
1a4d82fc JJ |
1179 | fn visit_item(&mut self, i: &Item) { |
1180 | resolve_item(self, i); | |
223e47cc | 1181 | } |
223e47cc | 1182 | |
e9174d1e | 1183 | fn visit_impl_item(&mut self, ii: &hir::ImplItem) { |
92a42be0 | 1184 | intravisit::walk_impl_item(self, ii); |
e9174d1e SL |
1185 | self.create_item_scope_if_needed(ii.id); |
1186 | } | |
1187 | ||
1188 | fn visit_trait_item(&mut self, ti: &hir::TraitItem) { | |
92a42be0 | 1189 | intravisit::walk_trait_item(self, ti); |
e9174d1e SL |
1190 | self.create_item_scope_if_needed(ti.id); |
1191 | } | |
1192 | ||
1a4d82fc JJ |
1193 | fn visit_fn(&mut self, fk: FnKind<'v>, fd: &'v FnDecl, |
1194 | b: &'v Block, s: Span, n: NodeId) { | |
1195 | resolve_fn(self, fk, fd, b, s, n); | |
1196 | } | |
1197 | fn visit_arm(&mut self, a: &Arm) { | |
1198 | resolve_arm(self, a); | |
1199 | } | |
1200 | fn visit_pat(&mut self, p: &Pat) { | |
1201 | resolve_pat(self, p); | |
1202 | } | |
1203 | fn visit_stmt(&mut self, s: &Stmt) { | |
1204 | resolve_stmt(self, s); | |
1205 | } | |
1206 | fn visit_expr(&mut self, ex: &Expr) { | |
1207 | resolve_expr(self, ex); | |
1208 | } | |
1209 | fn visit_local(&mut self, l: &Local) { | |
1210 | resolve_local(self, l); | |
1211 | } | |
223e47cc LB |
1212 | } |
1213 | ||
7453a54e SL |
1214 | pub fn resolve_crate(sess: &Session, map: &ast_map::Map) -> RegionMaps { |
1215 | let _task = map.dep_graph.in_task(DepNode::RegionResolveCrate); | |
1216 | let krate = map.krate(); | |
1217 | ||
1a4d82fc | 1218 | let maps = RegionMaps { |
e9174d1e SL |
1219 | code_extents: RefCell::new(vec![]), |
1220 | code_extent_interner: RefCell::new(FnvHashMap()), | |
1221 | scope_map: RefCell::new(vec![]), | |
85aaf69f | 1222 | var_map: RefCell::new(NodeMap()), |
85aaf69f | 1223 | rvalue_scopes: RefCell::new(NodeMap()), |
c34b1796 | 1224 | fn_tree: RefCell::new(NodeMap()), |
223e47cc | 1225 | }; |
e9174d1e SL |
1226 | let root_extent = maps.bogus_code_extent( |
1227 | CodeExtentData::DestructionScope(ast::DUMMY_NODE_ID)); | |
1228 | assert_eq!(root_extent, ROOT_CODE_EXTENT); | |
1229 | let bogus_extent = maps.bogus_code_extent( | |
1230 | CodeExtentData::Misc(ast::DUMMY_NODE_ID)); | |
1231 | assert_eq!(bogus_extent, DUMMY_CODE_EXTENT); | |
223e47cc | 1232 | { |
1a4d82fc JJ |
1233 | let mut visitor = RegionResolutionVisitor { |
1234 | sess: sess, | |
1235 | region_maps: &maps, | |
85aaf69f | 1236 | cx: Context { |
c34b1796 | 1237 | root_id: None, |
e9174d1e SL |
1238 | parent: ROOT_CODE_EXTENT, |
1239 | var_parent: ROOT_CODE_EXTENT | |
1240 | }, | |
1241 | terminating_scopes: NodeSet() | |
1a4d82fc | 1242 | }; |
92a42be0 | 1243 | krate.visit_all_items(&mut visitor); |
223e47cc | 1244 | } |
1a4d82fc JJ |
1245 | return maps; |
1246 | } |