1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
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.
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.
16 //! Most of the documentation on regions can be found in
17 //! `middle/infer/region_inference/README.md`
19 use hir::map as hir_map;
21 use util::nodemap::{FxHashMap, NodeMap, NodeSet};
24 use std::collections::hash_map::Entry;
29 use syntax::ast::{self, NodeId};
32 use ty::maps::Providers;
35 use hir::def_id::{CrateNum, LOCAL_CRATE};
36 use hir::intravisit::{self, Visitor, FnKind, NestedVisitorMap};
37 use hir::{Body, Block, Item, FnDecl, Arm, Pat, PatKind, Stmt, Expr, Local};
39 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable,
40 RustcDecodable, Copy)]
41 pub struct CodeExtent(u32);
43 impl fmt::Debug for CodeExtent {
44 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
45 write!(f, "CodeExtent({:?}", self.0)?;
47 ty::tls::with_opt(|opt_tcx| {
48 if let Some(tcx) = opt_tcx {
49 let region_maps = tcx.region_maps();
51 let code_extents = ®ion_maps.code_extents;
52 if let Some(data) = code_extents.get(self.0 as usize) {
53 write!(f, "/{:?}", data)?;
55 mem::drop(code_extents); // FIXME why is this necessary?
65 /// CodeExtent represents a statically-describable extent that can be
66 /// used to bound the lifetime/region for values.
68 /// `Misc(node_id)`: Any AST node that has any extent at all has the
69 /// `Misc(node_id)` extent. Other variants represent special cases not
70 /// immediately derivable from the abstract syntax tree structure.
72 /// `DestructionScope(node_id)` represents the extent of destructors
73 /// implicitly-attached to `node_id` that run immediately after the
74 /// expression for `node_id` itself. Not every AST node carries a
75 /// `DestructionScope`, but those that are `terminating_scopes` do;
76 /// see discussion with `RegionMaps`.
78 /// `Remainder(BlockRemainder { block, statement_index })` represents
79 /// the extent of user code running immediately after the initializer
80 /// expression for the indexed statement, until the end of the block.
82 /// So: the following code can be broken down into the extents beneath:
84 /// let a = f().g( 'b: { let x = d(); let y = d(); x.h(y) } ) ;
89 /// +---------+ (R10.)
91 /// +----------+ (M8.)
92 /// +----------------------+ (R7.)
94 /// +----------+ (M5.)
95 /// +-----------------------------------+ (M4.)
96 /// +--------------------------------------------------+ (M3.)
98 /// +-----------------------------------------------------------+ (M1.)
100 /// (M1.): Misc extent of the whole `let a = ...;` statement.
101 /// (M2.): Misc extent of the `f()` expression.
102 /// (M3.): Misc extent of the `f().g(..)` expression.
103 /// (M4.): Misc extent of the block labelled `'b:`.
104 /// (M5.): Misc extent of the `let x = d();` statement
105 /// (D6.): DestructionScope for temporaries created during M5.
106 /// (R7.): Remainder extent for block `'b:`, stmt 0 (let x = ...).
107 /// (M8.): Misc Extent of the `let y = d();` statement.
108 /// (D9.): DestructionScope for temporaries created during M8.
109 /// (R10.): Remainder extent for block `'b:`, stmt 1 (let y = ...).
110 /// (D11.): DestructionScope for temporaries and bindings from block `'b:`.
111 /// (D12.): DestructionScope for temporaries created during M1 (e.g. f()).
113 /// Note that while the above picture shows the destruction scopes
114 /// as following their corresponding misc extents, in the internal
115 /// data structures of the compiler the destruction scopes are
116 /// represented as enclosing parents. This is sound because we use the
117 /// enclosing parent relationship just to ensure that referenced
118 /// values live long enough; phrased another way, the starting point
119 /// of each range is not really the important thing in the above
120 /// picture, but rather the ending point.
122 /// FIXME (pnkfelix): This currently derives `PartialOrd` and `Ord` to
123 /// placate the same deriving in `ty::FreeRegion`, but we may want to
124 /// actually attach a more meaningful ordering to scopes than the one
125 /// generated via deriving here.
126 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, Debug, Copy)]
127 pub enum CodeExtentData {
130 // extent of the call-site for a function or closure (outlives
131 // the parameters as well as the body).
132 CallSiteScope { fn_id: ast::NodeId, body_id: ast::NodeId },
134 // extent of parameters passed to a function or closure (they
136 ParameterScope { fn_id: ast::NodeId, body_id: ast::NodeId },
138 // extent of destructors for temporaries of node-id
139 DestructionScope(ast::NodeId),
141 // extent of code following a `let id = expr;` binding in a block
142 Remainder(BlockRemainder)
145 /// extent of call-site for a function/method.
146 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable,
147 RustcDecodable, Debug, Copy)]
148 pub struct CallSiteScopeData {
149 pub fn_id: ast::NodeId, pub body_id: ast::NodeId,
152 impl CallSiteScopeData {
153 pub fn to_code_extent(&self, region_maps: &RegionMaps) -> CodeExtent {
154 region_maps.lookup_code_extent(
156 CallSiteScopeData { fn_id, body_id } =>
157 CodeExtentData::CallSiteScope { fn_id: fn_id, body_id: body_id },
162 /// Represents a subscope of `block` for a binding that is introduced
163 /// by `block.stmts[first_statement_index]`. Such subscopes represent
164 /// a suffix of the block. Note that each subscope does not include
165 /// the initializer expression, if any, for the statement indexed by
166 /// `first_statement_index`.
168 /// For example, given `{ let (a, b) = EXPR_1; let c = EXPR_2; ... }`:
170 /// * the subscope with `first_statement_index == 0` is scope of both
171 /// `a` and `b`; it does not include EXPR_1, but does include
172 /// everything after that first `let`. (If you want a scope that
173 /// includes EXPR_1 as well, then do not use `CodeExtentData::Remainder`,
174 /// but instead another `CodeExtent` that encompasses the whole block,
175 /// e.g. `CodeExtentData::Misc`.
177 /// * the subscope with `first_statement_index == 1` is scope of `c`,
178 /// and thus does not include EXPR_2, but covers the `...`.
179 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable,
180 RustcDecodable, Debug, Copy)]
181 pub struct BlockRemainder {
182 pub block: ast::NodeId,
183 pub first_statement_index: u32,
186 impl CodeExtentData {
187 /// Returns a node id associated with this scope.
189 /// NB: likely to be replaced as API is refined; e.g. pnkfelix
190 /// anticipates `fn entry_node_id` and `fn each_exit_node_id`.
191 pub fn node_id(&self) -> ast::NodeId {
193 CodeExtentData::Misc(node_id) => node_id,
195 // These cases all return rough approximations to the
196 // precise extent denoted by `self`.
197 CodeExtentData::Remainder(br) => br.block,
198 CodeExtentData::DestructionScope(node_id) => node_id,
199 CodeExtentData::CallSiteScope { fn_id: _, body_id } |
200 CodeExtentData::ParameterScope { fn_id: _, body_id } => body_id,
206 pub fn node_id(&self, region_maps: &RegionMaps) -> ast::NodeId {
207 region_maps.code_extent_data(*self).node_id()
210 /// Returns the span of this CodeExtent. Note that in general the
211 /// returned span may not correspond to the span of any node id in
213 pub fn span(&self, region_maps: &RegionMaps, hir_map: &hir_map::Map) -> Option<Span> {
214 match hir_map.find(self.node_id(region_maps)) {
215 Some(hir_map::NodeBlock(ref blk)) => {
216 match region_maps.code_extent_data(*self) {
217 CodeExtentData::CallSiteScope { .. } |
218 CodeExtentData::ParameterScope { .. } |
219 CodeExtentData::Misc(_) |
220 CodeExtentData::DestructionScope(_) => Some(blk.span),
222 CodeExtentData::Remainder(r) => {
223 assert_eq!(r.block, blk.id);
224 // Want span for extent starting after the
225 // indexed statement and ending at end of
226 // `blk`; reuse span of `blk` and shift `lo`
227 // forward to end of indexed statement.
229 // (This is the special case aluded to in the
230 // doc-comment for this method)
231 let stmt_span = blk.stmts[r.first_statement_index as usize].span;
232 Some(Span { lo: stmt_span.hi, hi: blk.span.hi, ctxt: stmt_span.ctxt })
236 Some(hir_map::NodeExpr(ref expr)) => Some(expr.span),
237 Some(hir_map::NodeStmt(ref stmt)) => Some(stmt.span),
238 Some(hir_map::NodeItem(ref item)) => Some(item.span),
239 Some(_) | None => None,
244 /// The region maps encode information about region relationships.
245 pub struct RegionMaps {
246 code_extents: Vec<CodeExtentData>,
247 code_extent_interner: FxHashMap<CodeExtentData, CodeExtent>,
248 /// `scope_map` maps from a scope id to the enclosing scope id;
249 /// this is usually corresponding to the lexical nesting, though
250 /// in the case of closures the parent scope is the innermost
251 /// conditional expression or repeating block. (Note that the
252 /// enclosing scope id for the block associated with a closure is
253 /// the closure itself.)
254 scope_map: Vec<Option<CodeExtent>>,
256 /// `var_map` maps from a variable or binding id to the block in
257 /// which that variable is declared.
258 var_map: NodeMap<CodeExtent>,
260 /// `rvalue_scopes` includes entries for those expressions whose cleanup scope is
261 /// larger than the default. The map goes from the expression id
262 /// to the cleanup scope id. For rvalues not present in this
263 /// table, the appropriate cleanup scope is the innermost
264 /// enclosing statement, conditional expression, or repeating
265 /// block (see `terminating_scopes`).
266 rvalue_scopes: NodeMap<CodeExtent>,
268 /// Records the value of rvalue scopes before they were shrunk by
269 /// #36082, for error reporting.
271 /// FIXME: this should be temporary. Remove this by 1.18.0 or
273 shrunk_rvalue_scopes: NodeMap<CodeExtent>,
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"
283 /// section of the README in infer::region_inference for
285 fn_tree: NodeMap<ast::NodeId>,
288 #[derive(Debug, Copy, Clone)]
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
294 /// the README in infer::region_inference for more
296 root_id: Option<ast::NodeId>,
298 /// the scope that contains any new variables declared
299 var_parent: Option<CodeExtent>,
301 /// region parent of expressions etc
302 parent: Option<CodeExtent>,
305 struct RegionResolutionVisitor<'hir: 'a, 'a> {
309 region_maps: &'a mut RegionMaps,
313 map: &'a hir_map::Map<'hir>,
315 /// `terminating_scopes` is a set containing the ids of each
316 /// statement, or conditional/repeating expression. These scopes
317 /// are calling "terminating scopes" because, when attempting to
318 /// find the scope of a temporary, by default we search up the
319 /// enclosing scopes until we encounter the terminating scope. A
320 /// conditional/repeating expression is one which is not
321 /// guaranteed to execute exactly once upon entering the parent
322 /// scope. This could be because the expression only executes
323 /// conditionally, such as the expression `b` in `a && b`, or
324 /// because the expression may execute many times, such as a loop
325 /// body. The reason that we distinguish such expressions is that,
326 /// upon exiting the parent scope, we cannot statically know how
327 /// many times the expression executed, and thus if the expression
328 /// creates temporaries we cannot know statically how many such
329 /// temporaries we would have to cleanup. Therefore we ensure that
330 /// the temporaries never outlast the conditional/repeating
331 /// expression, preventing the need for dynamic checks and/or
332 /// arbitrary amounts of stack space. Terminating scopes end
333 /// up being contained in a DestructionScope that contains the
334 /// destructor's execution.
335 terminating_scopes: NodeSet
340 pub fn lookup_code_extent(&self, e: CodeExtentData) -> CodeExtent {
341 match self.code_extent_interner.get(&e) {
343 None => bug!("unknown code extent {:?}", e)
346 pub fn node_extent(&self, n: ast::NodeId) -> CodeExtent {
347 self.lookup_code_extent(CodeExtentData::Misc(n))
349 // Returns the code extent for an item - the destruction scope.
350 pub fn item_extent(&self, n: ast::NodeId) -> CodeExtent {
351 self.lookup_code_extent(CodeExtentData::DestructionScope(n))
353 pub fn call_site_extent(&self, fn_id: ast::NodeId, body_id: ast::NodeId) -> CodeExtent {
354 assert!(fn_id != body_id);
355 self.lookup_code_extent(CodeExtentData::CallSiteScope { fn_id: fn_id, body_id: body_id })
357 pub fn opt_destruction_extent(&self, n: ast::NodeId) -> Option<CodeExtent> {
358 self.code_extent_interner.get(&CodeExtentData::DestructionScope(n)).cloned()
360 pub fn intern_code_extent(&mut self,
362 parent: Option<CodeExtent>) -> CodeExtent {
363 match self.code_extent_interner.entry(e) {
364 Entry::Occupied(_) => {
365 bug!("intern_code_extent: already exists")
367 Entry::Vacant(v) => {
368 if self.code_extents.len() > 0xffffffffusize {
369 bug!() // should pass a sess,
370 // but this isn't the only place
372 let idx = CodeExtent(self.code_extents.len() as u32);
373 debug!("CodeExtent({:?}) = {:?} [parent={:?}]", idx, e, parent);
374 self.code_extents.push(e);
375 self.scope_map.push(parent);
380 pub fn intern_node(&mut self,
382 parent: Option<CodeExtent>) -> CodeExtent {
383 self.intern_code_extent(CodeExtentData::Misc(n), parent)
385 pub fn code_extent_data(&self, e: CodeExtent) -> CodeExtentData {
386 self.code_extents[e.0 as usize]
388 pub fn each_encl_scope<E>(&self, mut e:E) where E: FnMut(&CodeExtent, &CodeExtent) {
389 for child_id in 1..self.code_extents.len() {
390 let child = CodeExtent(child_id as u32);
391 if let Some(parent) = self.opt_encl_scope(child) {
396 pub fn each_var_scope<E>(&self, mut e:E) where E: FnMut(&ast::NodeId, &CodeExtent) {
397 for (child, parent) in self.var_map.iter() {
402 /// Records that `sub_fn` is defined within `sup_fn`. These ids
403 /// should be the id of the block that is the fn body, which is
404 /// also the root of the region hierarchy for that fn.
405 fn record_fn_parent(&mut self, sub_fn: ast::NodeId, sup_fn: ast::NodeId) {
406 debug!("record_fn_parent(sub_fn={:?}, sup_fn={:?})", sub_fn, sup_fn);
407 assert!(sub_fn != sup_fn);
408 let previous = self.fn_tree.insert(sub_fn, sup_fn);
409 assert!(previous.is_none());
412 fn fn_is_enclosed_by(&self, mut sub_fn: ast::NodeId, sup_fn: ast::NodeId) -> bool {
414 if sub_fn == sup_fn { return true; }
415 match self.fn_tree.get(&sub_fn) {
416 Some(&s) => { sub_fn = s; }
417 None => { return false; }
422 fn record_var_scope(&mut self, var: ast::NodeId, lifetime: CodeExtent) {
423 debug!("record_var_scope(sub={:?}, sup={:?})", var, lifetime);
424 assert!(var != lifetime.node_id(self));
425 self.var_map.insert(var, lifetime);
428 fn record_rvalue_scope(&mut self, var: ast::NodeId, lifetime: CodeExtent) {
429 debug!("record_rvalue_scope(sub={:?}, sup={:?})", var, lifetime);
430 assert!(var != lifetime.node_id(self));
431 self.rvalue_scopes.insert(var, lifetime);
434 fn record_shrunk_rvalue_scope(&mut self, var: ast::NodeId, lifetime: CodeExtent) {
435 debug!("record_rvalue_scope(sub={:?}, sup={:?})", var, lifetime);
436 assert!(var != lifetime.node_id(self));
437 self.shrunk_rvalue_scopes.insert(var, lifetime);
440 pub fn opt_encl_scope(&self, id: CodeExtent) -> Option<CodeExtent> {
441 //! Returns the narrowest scope that encloses `id`, if any.
442 self.scope_map[id.0 as usize]
445 #[allow(dead_code)] // used in cfg
446 pub fn encl_scope(&self, id: CodeExtent) -> CodeExtent {
447 //! Returns the narrowest scope that encloses `id`, if any.
448 self.opt_encl_scope(id).unwrap()
451 /// Returns the lifetime of the local variable `var_id`
452 pub fn var_scope(&self, var_id: ast::NodeId) -> CodeExtent {
453 match self.var_map.get(&var_id) {
455 None => { bug!("no enclosing scope for id {:?}", var_id); }
459 pub fn temporary_scope2(&self, expr_id: ast::NodeId) -> (Option<CodeExtent>, bool) {
460 let temporary_scope = self.temporary_scope(expr_id);
461 let was_shrunk = match self.shrunk_rvalue_scopes.get(&expr_id) {
463 info!("temporary_scope2({:?}, scope={:?}, shrunk={:?})",
464 expr_id, temporary_scope, s);
465 temporary_scope != Some(s)
469 info!("temporary_scope2({:?}) - was_shrunk={:?}", expr_id, was_shrunk);
470 (temporary_scope, was_shrunk)
473 pub fn old_and_new_temporary_scope(&self, expr_id: ast::NodeId) ->
474 (Option<CodeExtent>, Option<CodeExtent>)
476 let temporary_scope = self.temporary_scope(expr_id);
478 self.shrunk_rvalue_scopes
479 .get(&expr_id).cloned()
480 .or(temporary_scope))
483 pub fn temporary_scope(&self, expr_id: ast::NodeId) -> Option<CodeExtent> {
484 //! Returns the scope when temp created by expr_id will be cleaned up
486 // check for a designated rvalue scope
487 if let Some(&s) = self.rvalue_scopes.get(&expr_id) {
488 debug!("temporary_scope({:?}) = {:?} [custom]", expr_id, s);
492 let scope_map : &[Option<CodeExtent>] = &self.scope_map;
493 let code_extents: &[CodeExtentData] = &self.code_extents;
495 // else, locate the innermost terminating scope
496 // if there's one. Static items, for instance, won't
497 // have an enclosing scope, hence no scope will be
499 let mut id = self.node_extent(expr_id);
501 while let Some(p) = scope_map[id.0 as usize] {
502 match code_extents[p.0 as usize] {
503 CodeExtentData::DestructionScope(..) => {
504 debug!("temporary_scope({:?}) = {:?} [enclosing]",
512 debug!("temporary_scope({:?}) = None", expr_id);
516 pub fn var_region(&self, id: ast::NodeId) -> ty::Region {
517 //! Returns the lifetime of the variable `id`.
519 let scope = ty::ReScope(self.var_scope(id));
520 debug!("var_region({:?}) = {:?}", id, scope);
524 pub fn scopes_intersect(&self, scope1: CodeExtent, scope2: CodeExtent)
526 self.is_subscope_of(scope1, scope2) ||
527 self.is_subscope_of(scope2, scope1)
530 /// Returns true if `subscope` is equal to or is lexically nested inside `superscope` and false
532 pub fn is_subscope_of(&self,
533 subscope: CodeExtent,
534 superscope: CodeExtent)
536 let mut s = subscope;
537 debug!("is_subscope_of({:?}, {:?})", subscope, superscope);
538 while superscope != s {
539 match self.opt_encl_scope(s) {
541 debug!("is_subscope_of({:?}, {:?}, s={:?})=false",
542 subscope, superscope, s);
545 Some(scope) => s = scope
549 debug!("is_subscope_of({:?}, {:?})=true",
550 subscope, superscope);
555 /// Finds the nearest common ancestor (if any) of two scopes. That is, finds the smallest
556 /// scope which is greater than or equal to both `scope_a` and `scope_b`.
557 pub fn nearest_common_ancestor(&self,
561 if scope_a == scope_b { return scope_a; }
563 /// [1] The initial values for `a_buf` and `b_buf` are not used.
564 /// The `ancestors_of` function will return some prefix that
565 /// is re-initialized with new values (or else fallback to a
566 /// heap-allocated vector).
567 let mut a_buf: [CodeExtent; 32] = [scope_a /* [1] */; 32];
568 let mut a_vec: Vec<CodeExtent> = vec![];
569 let mut b_buf: [CodeExtent; 32] = [scope_b /* [1] */; 32];
570 let mut b_vec: Vec<CodeExtent> = vec![];
571 let scope_map : &[Option<CodeExtent>] = &self.scope_map;
572 let a_ancestors = ancestors_of(scope_map, scope_a, &mut a_buf, &mut a_vec);
573 let b_ancestors = ancestors_of(scope_map, scope_b, &mut b_buf, &mut b_vec);
574 let mut a_index = a_ancestors.len() - 1;
575 let mut b_index = b_ancestors.len() - 1;
577 // Here, [ab]_ancestors is a vector going from narrow to broad.
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.
585 if a_ancestors[a_index] != b_ancestors[b_index] {
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
590 // infer::region_inference for more details.
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]);
593 return match (a_root_scope, b_root_scope) {
594 (CodeExtentData::DestructionScope(a_root_id),
595 CodeExtentData::DestructionScope(b_root_id)) => {
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`
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`
603 // neither fn encloses the other
608 // root ids are always Misc right now
615 // Loop invariant: a_ancestors[a_index] == b_ancestors[b_index]
616 // for all indices between a_index and the end of the array
617 if a_index == 0 { return scope_a; }
618 if b_index == 0 { return scope_b; }
621 if a_ancestors[a_index] != b_ancestors[b_index] {
622 return a_ancestors[a_index + 1];
626 fn ancestors_of<'a>(scope_map: &[Option<CodeExtent>],
628 buf: &'a mut [CodeExtent; 32],
629 vec: &'a mut Vec<CodeExtent>)
630 -> &'a [CodeExtent] {
631 // debug!("ancestors_of(scope={:?})", scope);
632 let mut scope = scope;
637 match scope_map[scope.0 as usize] {
638 Some(superscope) => scope = superscope,
639 _ => return &buf[..i+1]
644 *vec = Vec::with_capacity(64);
645 vec.extend_from_slice(buf);
648 match scope_map[scope.0 as usize] {
649 Some(superscope) => scope = superscope,
657 /// Records the lifetime of a local variable as `cx.var_parent`
658 fn record_var_lifetime(visitor: &mut RegionResolutionVisitor,
661 match visitor.cx.var_parent {
663 // this can happen in extern fn declarations like
665 // extern fn isalnum(c: c_int) -> c_int
667 Some(parent_scope) =>
668 visitor.region_maps.record_var_scope(var_id, parent_scope),
672 fn resolve_block<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'tcx, 'a>, blk: &'tcx hir::Block) {
673 debug!("resolve_block(blk.id={:?})", blk.id);
675 let prev_cx = visitor.cx;
676 let block_extent = visitor.new_node_extent_with_dtor(blk.id);
678 // We treat the tail expression in the block (if any) somewhat
679 // differently from the statements. The issue has to do with
680 // temporary lifetimes. Consider the following:
683 // let inner = ... (&bar()) ...;
685 // (... (&foo()) ...) // (the tail expression)
686 // }, other_argument());
688 // Each of the statements within the block is a terminating
689 // scope, and thus a temporary (e.g. the result of calling
690 // `bar()` in the initalizer expression for `let inner = ...;`)
691 // will be cleaned up immediately after its corresponding
692 // statement (i.e. `let inner = ...;`) executes.
694 // On the other hand, temporaries associated with evaluating the
695 // tail expression for the block are assigned lifetimes so that
696 // they will be cleaned up as part of the terminating scope
697 // *surrounding* the block expression. Here, the terminating
698 // scope for the block expression is the `quux(..)` call; so
699 // those temporaries will only be cleaned up *after* both
700 // `other_argument()` has run and also the call to `quux(..)`
701 // itself has returned.
703 visitor.cx = Context {
704 root_id: prev_cx.root_id,
705 var_parent: Some(block_extent),
706 parent: Some(block_extent),
710 // This block should be kept approximately in sync with
711 // `intravisit::walk_block`. (We manually walk the block, rather
712 // than call `walk_block`, in order to maintain precise
713 // index information.)
715 for (i, statement) in blk.stmts.iter().enumerate() {
716 if let hir::StmtDecl(..) = statement.node {
717 // Each StmtDecl introduces a subscope for bindings
718 // introduced by the declaration; this subscope covers
719 // a suffix of the block . Each subscope in a block
720 // has the previous subscope in the block as a parent,
721 // except for the first such subscope, which has the
722 // block itself as a parent.
723 let stmt_extent = visitor.new_code_extent(
724 CodeExtentData::Remainder(BlockRemainder {
726 first_statement_index: i as u32
729 visitor.cx = Context {
730 root_id: prev_cx.root_id,
731 var_parent: Some(stmt_extent),
732 parent: Some(stmt_extent),
735 visitor.visit_stmt(statement)
737 walk_list!(visitor, visit_expr, &blk.expr);
740 visitor.cx = prev_cx;
743 fn resolve_arm<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'tcx, 'a>, arm: &'tcx hir::Arm) {
744 visitor.terminating_scopes.insert(arm.body.id);
746 if let Some(ref expr) = arm.guard {
747 visitor.terminating_scopes.insert(expr.id);
750 intravisit::walk_arm(visitor, arm);
753 fn resolve_pat<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'tcx, 'a>, pat: &'tcx hir::Pat) {
754 visitor.new_node_extent(pat.id);
756 // If this is a binding then record the lifetime of that binding.
757 if let PatKind::Binding(..) = pat.node {
758 record_var_lifetime(visitor, pat.id, pat.span);
761 intravisit::walk_pat(visitor, pat);
764 fn resolve_stmt<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'tcx, 'a>, stmt: &'tcx hir::Stmt) {
765 let stmt_id = stmt.node.id();
766 debug!("resolve_stmt(stmt.id={:?})", stmt_id);
768 // Every statement will clean up the temporaries created during
769 // execution of that statement. Therefore each statement has an
770 // associated destruction scope that represents the extent of the
771 // statement plus its destructors, and thus the extent for which
772 // regions referenced by the destructors need to survive.
773 visitor.terminating_scopes.insert(stmt_id);
774 let stmt_extent = visitor.new_node_extent_with_dtor(stmt_id);
776 let prev_parent = visitor.cx.parent;
777 visitor.cx.parent = Some(stmt_extent);
778 intravisit::walk_stmt(visitor, stmt);
779 visitor.cx.parent = prev_parent;
782 fn resolve_expr<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'tcx, 'a>, expr: &'tcx hir::Expr) {
783 debug!("resolve_expr(expr.id={:?})", expr.id);
785 let expr_extent = visitor.new_node_extent_with_dtor(expr.id);
786 let prev_cx = visitor.cx;
787 visitor.cx.parent = Some(expr_extent);
790 let terminating_scopes = &mut visitor.terminating_scopes;
791 let mut terminating = |id: ast::NodeId| {
792 terminating_scopes.insert(id);
795 // Conditional or repeating scopes are always terminating
796 // scopes, meaning that temporaries cannot outlive them.
797 // This ensures fixed size stacks.
799 hir::ExprBinary(codemap::Spanned { node: hir::BiAnd, .. }, _, ref r) |
800 hir::ExprBinary(codemap::Spanned { node: hir::BiOr, .. }, _, ref r) => {
801 // For shortcircuiting operators, mark the RHS as a terminating
802 // scope since it only executes conditionally.
806 hir::ExprIf(ref expr, ref then, Some(ref otherwise)) => {
807 terminating(expr.id);
808 terminating(then.id);
809 terminating(otherwise.id);
812 hir::ExprIf(ref expr, ref then, None) => {
813 terminating(expr.id);
814 terminating(then.id);
817 hir::ExprLoop(ref body, _, _) => {
818 terminating(body.id);
821 hir::ExprWhile(ref expr, ref body, _) => {
822 terminating(expr.id);
823 terminating(body.id);
826 hir::ExprMatch(..) => {
827 visitor.cx.var_parent = Some(expr_extent);
830 hir::ExprAssignOp(..) | hir::ExprIndex(..) |
831 hir::ExprUnary(..) | hir::ExprCall(..) | hir::ExprMethodCall(..) => {
832 // FIXME(#6268) Nested method calls
834 // The lifetimes for a call or method call look as follows:
842 // The idea is that call.callee_id represents *the time when
843 // the invoked function is actually running* and call.id
844 // represents *the time to prepare the arguments and make the
845 // call*. See the section "Borrows in Calls" borrowck/README.md
846 // for an extended explanation of why this distinction is
849 // record_superlifetime(new_cx, expr.callee_id);
856 intravisit::walk_expr(visitor, expr);
857 visitor.cx = prev_cx;
860 fn resolve_local<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'tcx, 'a>,
861 local: &'tcx hir::Local) {
862 debug!("resolve_local(local.id={:?},local.init={:?})",
863 local.id,local.init.is_some());
865 // For convenience in trans, associate with the local-id the var
866 // scope that will be used for any bindings declared in this
868 let blk_scope = visitor.cx.var_parent;
869 let blk_scope = blk_scope.expect("locals must be within a block");
870 visitor.region_maps.record_var_scope(local.id, blk_scope);
872 // As an exception to the normal rules governing temporary
873 // lifetimes, initializers in a let have a temporary lifetime
874 // of the enclosing block. This means that e.g. a program
875 // like the following is legal:
877 // let ref x = HashMap::new();
879 // Because the hash map will be freed in the enclosing block.
881 // We express the rules more formally based on 3 grammars (defined
882 // fully in the helpers below that implement them):
884 // 1. `E&`, which matches expressions like `&<rvalue>` that
885 // own a pointer into the stack.
887 // 2. `P&`, which matches patterns like `ref x` or `(ref x, ref
888 // y)` that produce ref bindings into the value they are
889 // matched against or something (at least partially) owned by
890 // the value they are matched against. (By partially owned,
891 // I mean that creating a binding into a ref-counted or managed value
892 // would still count.)
894 // 3. `ET`, which matches both rvalues like `foo()` as well as lvalues
895 // based on rvalues like `foo().x[2].y`.
897 // A subexpression `<rvalue>` that appears in a let initializer
898 // `let pat [: ty] = expr` has an extended temporary lifetime if
899 // any of the following conditions are met:
901 // A. `pat` matches `P&` and `expr` matches `ET`
902 // (covers cases where `pat` creates ref bindings into an rvalue
903 // produced by `expr`)
904 // B. `ty` is a borrowed pointer and `expr` matches `ET`
905 // (covers cases where coercion creates a borrow)
906 // C. `expr` matches `E&`
907 // (covers cases `expr` borrows an rvalue that is then assigned
908 // to memory (at least partially) owned by the binding)
910 // Here are some examples hopefully giving an intuition where each
911 // rule comes into play and why:
913 // Rule A. `let (ref x, ref y) = (foo().x, 44)`. The rvalue `(22, 44)`
914 // would have an extended lifetime, but not `foo()`.
916 // Rule B. `let x: &[...] = [foo().x]`. The rvalue `[foo().x]`
917 // would have an extended lifetime, but not `foo()`.
919 // Rule C. `let x = &foo().x`. The rvalue ``foo()` would have extended
922 // In some cases, multiple rules may apply (though not to the same
923 // rvalue). For example:
925 // let ref x = [&a(), &b()];
927 // Here, the expression `[...]` has an extended lifetime due to rule
928 // A, but the inner rvalues `a()` and `b()` have an extended lifetime
931 // FIXME(#6308) -- Note that `[]` patterns work more smoothly post-DST.
933 if let Some(ref expr) = local.init {
934 record_rvalue_scope_if_borrow_expr(visitor, &expr, blk_scope);
937 if let Some(ref ty) = local.ty { is_borrowed_ty(&ty) } else { false };
939 if is_binding_pat(&local.pat) {
940 record_rvalue_scope(visitor, &expr, blk_scope, false);
941 } else if is_borrow {
942 record_rvalue_scope(visitor, &expr, blk_scope, true);
946 intravisit::walk_local(visitor, local);
948 /// True if `pat` match the `P&` nonterminal:
951 /// | StructName { ..., P&, ... }
952 /// | VariantName(..., P&, ...)
953 /// | [ ..., P&, ... ]
954 /// | ( ..., P&, ... )
956 fn is_binding_pat(pat: &hir::Pat) -> bool {
958 PatKind::Binding(hir::BindByRef(_), ..) => true,
960 PatKind::Struct(_, ref field_pats, _) => {
961 field_pats.iter().any(|fp| is_binding_pat(&fp.node.pat))
964 PatKind::Slice(ref pats1, ref pats2, ref pats3) => {
965 pats1.iter().any(|p| is_binding_pat(&p)) ||
966 pats2.iter().any(|p| is_binding_pat(&p)) ||
967 pats3.iter().any(|p| is_binding_pat(&p))
970 PatKind::TupleStruct(_, ref subpats, _) |
971 PatKind::Tuple(ref subpats, _) => {
972 subpats.iter().any(|p| is_binding_pat(&p))
975 PatKind::Box(ref subpat) => {
976 is_binding_pat(&subpat)
983 /// True if `ty` is a borrowed pointer type like `&int` or `&[...]`.
984 fn is_borrowed_ty(ty: &hir::Ty) -> bool {
986 hir::TyRptr(..) => true,
991 /// If `expr` matches the `E&` grammar, then records an extended rvalue scope as appropriate:
994 /// | StructName { ..., f: E&, ... }
995 /// | [ ..., E&, ... ]
996 /// | ( ..., E&, ... )
1001 fn record_rvalue_scope_if_borrow_expr(visitor: &mut RegionResolutionVisitor,
1003 blk_id: CodeExtent) {
1005 hir::ExprAddrOf(_, ref subexpr) => {
1006 record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id);
1007 record_rvalue_scope(visitor, &subexpr, blk_id, false);
1009 hir::ExprStruct(_, ref fields, _) => {
1010 for field in fields {
1011 record_rvalue_scope_if_borrow_expr(
1012 visitor, &field.expr, blk_id);
1015 hir::ExprArray(ref subexprs) |
1016 hir::ExprTup(ref subexprs) => {
1017 for subexpr in subexprs {
1018 record_rvalue_scope_if_borrow_expr(
1019 visitor, &subexpr, blk_id);
1022 hir::ExprCast(ref subexpr, _) => {
1023 record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id)
1025 hir::ExprBlock(ref block) => {
1026 if let Some(ref subexpr) = block.expr {
1027 record_rvalue_scope_if_borrow_expr(
1028 visitor, &subexpr, blk_id);
1035 /// Applied to an expression `expr` if `expr` -- or something owned or partially owned by
1036 /// `expr` -- is going to be indirectly referenced by a variable in a let statement. In that
1037 /// case, the "temporary lifetime" or `expr` is extended to be the block enclosing the `let`
1040 /// More formally, if `expr` matches the grammar `ET`, record the rvalue scope of the matching
1041 /// `<rvalue>` as `blk_id`:
1049 /// Note: ET is intended to match "rvalues or lvalues based on rvalues".
1050 fn record_rvalue_scope<'a>(visitor: &mut RegionResolutionVisitor,
1051 expr: &'a hir::Expr,
1052 blk_scope: CodeExtent,
1054 let mut expr = expr;
1056 // Note: give all the expressions matching `ET` with the
1057 // extended temporary lifetime, not just the innermost rvalue,
1058 // because in trans if we must compile e.g. `*rvalue()`
1059 // into a temporary, we request the temporary scope of the
1060 // outer expression.
1062 // this changed because of #36082
1063 visitor.region_maps.record_shrunk_rvalue_scope(expr.id, blk_scope);
1065 visitor.region_maps.record_rvalue_scope(expr.id, blk_scope);
1069 hir::ExprAddrOf(_, ref subexpr) |
1070 hir::ExprUnary(hir::UnDeref, ref subexpr) |
1071 hir::ExprField(ref subexpr, _) |
1072 hir::ExprTupField(ref subexpr, _) |
1073 hir::ExprIndex(ref subexpr, _) => {
1084 fn resolve_item_like<'a, 'tcx, F>(visitor: &mut RegionResolutionVisitor<'tcx, 'a>,
1087 where F: FnOnce(&mut RegionResolutionVisitor<'tcx, 'a>)
1089 // Items create a new outer block scope as far as we're concerned.
1090 let prev_cx = visitor.cx;
1091 let prev_ts = mem::replace(&mut visitor.terminating_scopes, NodeSet());
1092 visitor.cx = Context {
1098 visitor.create_item_scope_if_needed(id);
1099 visitor.cx = prev_cx;
1100 visitor.terminating_scopes = prev_ts;
1103 fn resolve_fn<'a, 'tcx>(visitor: &mut RegionResolutionVisitor<'tcx, 'a>,
1105 decl: &'tcx hir::FnDecl,
1106 body_id: hir::BodyId,
1109 debug!("region::resolve_fn(id={:?}, \
1114 visitor.sess.codemap().span_to_string(sp),
1118 visitor.cx.parent = Some(visitor.new_code_extent(
1119 CodeExtentData::CallSiteScope { fn_id: id, body_id: body_id.node_id }));
1121 let fn_decl_scope = visitor.new_code_extent(
1122 CodeExtentData::ParameterScope { fn_id: id, body_id: body_id.node_id });
1124 if let Some(root_id) = visitor.cx.root_id {
1125 visitor.region_maps.record_fn_parent(body_id.node_id, root_id);
1128 let outer_cx = visitor.cx;
1129 let outer_ts = mem::replace(&mut visitor.terminating_scopes, NodeSet());
1130 visitor.terminating_scopes.insert(body_id.node_id);
1132 // The arguments and `self` are parented to the fn.
1133 visitor.cx = Context {
1134 root_id: Some(body_id.node_id),
1136 var_parent: Some(fn_decl_scope),
1139 intravisit::walk_fn_decl(visitor, decl);
1140 intravisit::walk_fn_kind(visitor, kind);
1142 // The body of the every fn is a root scope.
1143 visitor.cx = Context {
1144 root_id: Some(body_id.node_id),
1145 parent: Some(fn_decl_scope),
1146 var_parent: Some(fn_decl_scope),
1148 visitor.visit_nested_body(body_id);
1150 // Restore context we had at the start.
1151 visitor.cx = outer_cx;
1152 visitor.terminating_scopes = outer_ts;
1155 impl<'hir, 'a> RegionResolutionVisitor<'hir, 'a> {
1156 /// Records the current parent (if any) as the parent of `child_scope`.
1157 fn new_code_extent(&mut self, child_scope: CodeExtentData) -> CodeExtent {
1158 self.region_maps.intern_code_extent(child_scope, self.cx.parent)
1161 fn new_node_extent(&mut self, child_scope: ast::NodeId) -> CodeExtent {
1162 self.new_code_extent(CodeExtentData::Misc(child_scope))
1165 fn new_node_extent_with_dtor(&mut self, id: ast::NodeId) -> CodeExtent {
1166 // If node was previously marked as a terminating scope during the
1167 // recursive visit of its parent node in the AST, then we need to
1168 // account for the destruction scope representing the extent of
1169 // the destructors that run immediately after it completes.
1170 if self.terminating_scopes.contains(&id) {
1171 let ds = self.new_code_extent(
1172 CodeExtentData::DestructionScope(id));
1173 self.region_maps.intern_node(id, Some(ds))
1175 self.new_node_extent(id)
1179 fn create_item_scope_if_needed(&mut self, id: ast::NodeId) {
1180 // create a region for the destruction scope - this is needed
1181 // for constructing parameter environments based on the item.
1182 // functions put their destruction scopes *inside* their parameter
1184 let scope = CodeExtentData::DestructionScope(id);
1185 if !self.region_maps.code_extent_interner.contains_key(&scope) {
1186 self.region_maps.intern_code_extent(scope, None);
1191 impl<'hir, 'a> Visitor<'hir> for RegionResolutionVisitor<'hir, 'a> {
1192 fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'hir> {
1193 NestedVisitorMap::OnlyBodies(&self.map)
1196 fn visit_body(&mut self, b: &'hir Body) {
1197 // make sure that every body owner has an item scope, since
1198 // MIR construction wants that
1199 let owner = self.map.body_owner(b.id());
1200 self.create_item_scope_if_needed(owner);
1202 intravisit::walk_body(self, b);
1205 fn visit_block(&mut self, b: &'hir Block) {
1206 resolve_block(self, b);
1209 fn visit_item(&mut self, i: &'hir Item) {
1210 resolve_item_like(self, i.id, |this| intravisit::walk_item(this, i));
1213 fn visit_impl_item(&mut self, ii: &'hir hir::ImplItem) {
1214 resolve_item_like(self, ii.id, |this| intravisit::walk_impl_item(this, ii));
1217 fn visit_trait_item(&mut self, ti: &'hir hir::TraitItem) {
1218 resolve_item_like(self, ti.id, |this| intravisit::walk_trait_item(this, ti));
1221 fn visit_fn(&mut self, fk: FnKind<'hir>, fd: &'hir FnDecl,
1222 b: hir::BodyId, s: Span, n: NodeId) {
1223 resolve_fn(self, fk, fd, b, s, n);
1225 fn visit_arm(&mut self, a: &'hir Arm) {
1226 resolve_arm(self, a);
1228 fn visit_pat(&mut self, p: &'hir Pat) {
1229 resolve_pat(self, p);
1231 fn visit_stmt(&mut self, s: &'hir Stmt) {
1232 resolve_stmt(self, s);
1234 fn visit_expr(&mut self, ex: &'hir Expr) {
1235 resolve_expr(self, ex);
1237 fn visit_local(&mut self, l: &'hir Local) {
1238 resolve_local(self, l);
1242 pub fn resolve_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Rc<RegionMaps> {
1243 tcx.region_resolve_crate(LOCAL_CRATE)
1246 fn region_resolve_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum)
1249 debug_assert!(crate_num == LOCAL_CRATE);
1251 let sess = &tcx.sess;
1252 let hir_map = &tcx.hir;
1254 let krate = hir_map.krate();
1256 let mut maps = RegionMaps {
1257 code_extents: vec![],
1258 code_extent_interner: FxHashMap(),
1261 rvalue_scopes: NodeMap(),
1262 shrunk_rvalue_scopes: NodeMap(),
1266 let mut visitor = RegionResolutionVisitor {
1268 region_maps: &mut maps,
1275 terminating_scopes: NodeSet()
1277 krate.visit_all_item_likes(&mut visitor.as_deep_visitor());
1282 pub fn provide(providers: &mut Providers) {
1283 *providers = Providers {
1284 region_resolve_crate,