]>
Commit | Line | Data |
---|---|---|
dfeec247 XL |
1 | //! This file builds up the `ScopeTree`, which describes |
2 | //! the parent links in the region hierarchy. | |
3 | //! | |
4 | //! For more information about how MIR-based region-checking works, | |
5 | //! see the [rustc guide]. | |
6 | //! | |
74b04a01 | 7 | //! [rustc guide]: https://rust-lang.github.io/rustc-guide/borrow_check.html |
dfeec247 XL |
8 | |
9 | use rustc::hir::map::Map; | |
10 | use rustc::middle::region::*; | |
11 | use rustc::ty::query::Providers; | |
12 | use rustc::ty::TyCtxt; | |
74b04a01 | 13 | use rustc_ast::walk_list; |
dfeec247 XL |
14 | use rustc_data_structures::fx::FxHashSet; |
15 | use rustc_hir as hir; | |
16 | use rustc_hir::def_id::DefId; | |
17 | use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor}; | |
18 | use rustc_hir::{Arm, Block, Expr, Local, Node, Pat, PatKind, Stmt}; | |
19 | use rustc_index::vec::Idx; | |
20 | use rustc_span::source_map; | |
21 | use rustc_span::Span; | |
dfeec247 XL |
22 | |
23 | use std::mem; | |
24 | ||
25 | #[derive(Debug, Copy, Clone)] | |
26 | pub struct Context { | |
27 | /// The root of the current region tree. This is typically the id | |
28 | /// of the innermost fn body. Each fn forms its own disjoint tree | |
29 | /// in the region hierarchy. These fn bodies are themselves | |
30 | /// arranged into a tree. See the "Modeling closures" section of | |
31 | /// the README in `infer::region_constraints` for more | |
32 | /// details. | |
33 | root_id: Option<hir::ItemLocalId>, | |
34 | ||
35 | /// The scope that contains any new variables declared, plus its depth in | |
36 | /// the scope tree. | |
37 | var_parent: Option<(Scope, ScopeDepth)>, | |
38 | ||
39 | /// Region parent of expressions, etc., plus its depth in the scope tree. | |
40 | parent: Option<(Scope, ScopeDepth)>, | |
41 | } | |
42 | ||
43 | struct RegionResolutionVisitor<'tcx> { | |
44 | tcx: TyCtxt<'tcx>, | |
45 | ||
46 | // The number of expressions and patterns visited in the current body. | |
47 | expr_and_pat_count: usize, | |
48 | // When this is `true`, we record the `Scopes` we encounter | |
49 | // when processing a Yield expression. This allows us to fix | |
50 | // up their indices. | |
51 | pessimistic_yield: bool, | |
52 | // Stores scopes when `pessimistic_yield` is `true`. | |
53 | fixup_scopes: Vec<Scope>, | |
54 | // The generated scope tree. | |
55 | scope_tree: ScopeTree, | |
56 | ||
57 | cx: Context, | |
58 | ||
59 | /// `terminating_scopes` is a set containing the ids of each | |
60 | /// statement, or conditional/repeating expression. These scopes | |
61 | /// are calling "terminating scopes" because, when attempting to | |
62 | /// find the scope of a temporary, by default we search up the | |
63 | /// enclosing scopes until we encounter the terminating scope. A | |
64 | /// conditional/repeating expression is one which is not | |
65 | /// guaranteed to execute exactly once upon entering the parent | |
66 | /// scope. This could be because the expression only executes | |
67 | /// conditionally, such as the expression `b` in `a && b`, or | |
68 | /// because the expression may execute many times, such as a loop | |
69 | /// body. The reason that we distinguish such expressions is that, | |
70 | /// upon exiting the parent scope, we cannot statically know how | |
71 | /// many times the expression executed, and thus if the expression | |
72 | /// creates temporaries we cannot know statically how many such | |
73 | /// temporaries we would have to cleanup. Therefore, we ensure that | |
74 | /// the temporaries never outlast the conditional/repeating | |
75 | /// expression, preventing the need for dynamic checks and/or | |
76 | /// arbitrary amounts of stack space. Terminating scopes end | |
77 | /// up being contained in a DestructionScope that contains the | |
78 | /// destructor's execution. | |
79 | terminating_scopes: FxHashSet<hir::ItemLocalId>, | |
80 | } | |
81 | ||
82 | /// Records the lifetime of a local variable as `cx.var_parent` | |
83 | fn record_var_lifetime( | |
84 | visitor: &mut RegionResolutionVisitor<'_>, | |
85 | var_id: hir::ItemLocalId, | |
86 | _sp: Span, | |
87 | ) { | |
88 | match visitor.cx.var_parent { | |
89 | None => { | |
90 | // this can happen in extern fn declarations like | |
91 | // | |
92 | // extern fn isalnum(c: c_int) -> c_int | |
93 | } | |
94 | Some((parent_scope, _)) => visitor.scope_tree.record_var_scope(var_id, parent_scope), | |
95 | } | |
96 | } | |
97 | ||
98 | fn resolve_block<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, blk: &'tcx hir::Block<'tcx>) { | |
99 | debug!("resolve_block(blk.hir_id={:?})", blk.hir_id); | |
100 | ||
101 | let prev_cx = visitor.cx; | |
102 | ||
103 | // We treat the tail expression in the block (if any) somewhat | |
104 | // differently from the statements. The issue has to do with | |
105 | // temporary lifetimes. Consider the following: | |
106 | // | |
107 | // quux({ | |
108 | // let inner = ... (&bar()) ...; | |
109 | // | |
110 | // (... (&foo()) ...) // (the tail expression) | |
111 | // }, other_argument()); | |
112 | // | |
113 | // Each of the statements within the block is a terminating | |
114 | // scope, and thus a temporary (e.g., the result of calling | |
115 | // `bar()` in the initializer expression for `let inner = ...;`) | |
116 | // will be cleaned up immediately after its corresponding | |
117 | // statement (i.e., `let inner = ...;`) executes. | |
118 | // | |
119 | // On the other hand, temporaries associated with evaluating the | |
120 | // tail expression for the block are assigned lifetimes so that | |
121 | // they will be cleaned up as part of the terminating scope | |
122 | // *surrounding* the block expression. Here, the terminating | |
123 | // scope for the block expression is the `quux(..)` call; so | |
124 | // those temporaries will only be cleaned up *after* both | |
125 | // `other_argument()` has run and also the call to `quux(..)` | |
126 | // itself has returned. | |
127 | ||
128 | visitor.enter_node_scope_with_dtor(blk.hir_id.local_id); | |
129 | visitor.cx.var_parent = visitor.cx.parent; | |
130 | ||
131 | { | |
132 | // This block should be kept approximately in sync with | |
133 | // `intravisit::walk_block`. (We manually walk the block, rather | |
134 | // than call `walk_block`, in order to maintain precise | |
135 | // index information.) | |
136 | ||
137 | for (i, statement) in blk.stmts.iter().enumerate() { | |
138 | match statement.kind { | |
139 | hir::StmtKind::Local(..) | hir::StmtKind::Item(..) => { | |
140 | // Each declaration introduces a subscope for bindings | |
141 | // introduced by the declaration; this subscope covers a | |
142 | // suffix of the block. Each subscope in a block has the | |
143 | // previous subscope in the block as a parent, except for | |
144 | // the first such subscope, which has the block itself as a | |
145 | // parent. | |
146 | visitor.enter_scope(Scope { | |
147 | id: blk.hir_id.local_id, | |
148 | data: ScopeData::Remainder(FirstStatementIndex::new(i)), | |
149 | }); | |
150 | visitor.cx.var_parent = visitor.cx.parent; | |
151 | } | |
152 | hir::StmtKind::Expr(..) | hir::StmtKind::Semi(..) => {} | |
153 | } | |
154 | visitor.visit_stmt(statement) | |
155 | } | |
156 | walk_list!(visitor, visit_expr, &blk.expr); | |
157 | } | |
158 | ||
159 | visitor.cx = prev_cx; | |
160 | } | |
161 | ||
162 | fn resolve_arm<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, arm: &'tcx hir::Arm<'tcx>) { | |
163 | let prev_cx = visitor.cx; | |
164 | ||
165 | visitor.enter_scope(Scope { id: arm.hir_id.local_id, data: ScopeData::Node }); | |
166 | visitor.cx.var_parent = visitor.cx.parent; | |
167 | ||
168 | visitor.terminating_scopes.insert(arm.body.hir_id.local_id); | |
169 | ||
170 | if let Some(hir::Guard::If(ref expr)) = arm.guard { | |
171 | visitor.terminating_scopes.insert(expr.hir_id.local_id); | |
172 | } | |
173 | ||
174 | intravisit::walk_arm(visitor, arm); | |
175 | ||
176 | visitor.cx = prev_cx; | |
177 | } | |
178 | ||
179 | fn resolve_pat<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, pat: &'tcx hir::Pat<'tcx>) { | |
180 | visitor.record_child_scope(Scope { id: pat.hir_id.local_id, data: ScopeData::Node }); | |
181 | ||
182 | // If this is a binding then record the lifetime of that binding. | |
183 | if let PatKind::Binding(..) = pat.kind { | |
184 | record_var_lifetime(visitor, pat.hir_id.local_id, pat.span); | |
185 | } | |
186 | ||
187 | debug!("resolve_pat - pre-increment {} pat = {:?}", visitor.expr_and_pat_count, pat); | |
188 | ||
189 | intravisit::walk_pat(visitor, pat); | |
190 | ||
191 | visitor.expr_and_pat_count += 1; | |
192 | ||
193 | debug!("resolve_pat - post-increment {} pat = {:?}", visitor.expr_and_pat_count, pat); | |
194 | } | |
195 | ||
196 | fn resolve_stmt<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, stmt: &'tcx hir::Stmt<'tcx>) { | |
197 | let stmt_id = stmt.hir_id.local_id; | |
198 | debug!("resolve_stmt(stmt.id={:?})", stmt_id); | |
199 | ||
200 | // Every statement will clean up the temporaries created during | |
201 | // execution of that statement. Therefore each statement has an | |
202 | // associated destruction scope that represents the scope of the | |
203 | // statement plus its destructors, and thus the scope for which | |
204 | // regions referenced by the destructors need to survive. | |
205 | visitor.terminating_scopes.insert(stmt_id); | |
206 | ||
207 | let prev_parent = visitor.cx.parent; | |
208 | visitor.enter_node_scope_with_dtor(stmt_id); | |
209 | ||
210 | intravisit::walk_stmt(visitor, stmt); | |
211 | ||
212 | visitor.cx.parent = prev_parent; | |
213 | } | |
214 | ||
215 | fn resolve_expr<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, expr: &'tcx hir::Expr<'tcx>) { | |
216 | debug!("resolve_expr - pre-increment {} expr = {:?}", visitor.expr_and_pat_count, expr); | |
217 | ||
218 | let prev_cx = visitor.cx; | |
219 | visitor.enter_node_scope_with_dtor(expr.hir_id.local_id); | |
220 | ||
221 | { | |
222 | let terminating_scopes = &mut visitor.terminating_scopes; | |
223 | let mut terminating = |id: hir::ItemLocalId| { | |
224 | terminating_scopes.insert(id); | |
225 | }; | |
226 | match expr.kind { | |
227 | // Conditional or repeating scopes are always terminating | |
228 | // scopes, meaning that temporaries cannot outlive them. | |
229 | // This ensures fixed size stacks. | |
230 | hir::ExprKind::Binary( | |
231 | source_map::Spanned { node: hir::BinOpKind::And, .. }, | |
232 | _, | |
233 | ref r, | |
234 | ) | |
235 | | hir::ExprKind::Binary( | |
236 | source_map::Spanned { node: hir::BinOpKind::Or, .. }, | |
237 | _, | |
238 | ref r, | |
239 | ) => { | |
240 | // For shortcircuiting operators, mark the RHS as a terminating | |
241 | // scope since it only executes conditionally. | |
242 | terminating(r.hir_id.local_id); | |
243 | } | |
244 | ||
245 | hir::ExprKind::Loop(ref body, _, _) => { | |
246 | terminating(body.hir_id.local_id); | |
247 | } | |
248 | ||
249 | hir::ExprKind::DropTemps(ref expr) => { | |
250 | // `DropTemps(expr)` does not denote a conditional scope. | |
251 | // Rather, we want to achieve the same behavior as `{ let _t = expr; _t }`. | |
252 | terminating(expr.hir_id.local_id); | |
253 | } | |
254 | ||
255 | hir::ExprKind::AssignOp(..) | |
256 | | hir::ExprKind::Index(..) | |
257 | | hir::ExprKind::Unary(..) | |
258 | | hir::ExprKind::Call(..) | |
259 | | hir::ExprKind::MethodCall(..) => { | |
260 | // FIXME(https://github.com/rust-lang/rfcs/issues/811) Nested method calls | |
261 | // | |
262 | // The lifetimes for a call or method call look as follows: | |
263 | // | |
264 | // call.id | |
265 | // - arg0.id | |
266 | // - ... | |
267 | // - argN.id | |
268 | // - call.callee_id | |
269 | // | |
270 | // The idea is that call.callee_id represents *the time when | |
271 | // the invoked function is actually running* and call.id | |
272 | // represents *the time to prepare the arguments and make the | |
273 | // call*. See the section "Borrows in Calls" borrowck/README.md | |
274 | // for an extended explanation of why this distinction is | |
275 | // important. | |
276 | // | |
277 | // record_superlifetime(new_cx, expr.callee_id); | |
278 | } | |
279 | ||
280 | _ => {} | |
281 | } | |
282 | } | |
283 | ||
284 | let prev_pessimistic = visitor.pessimistic_yield; | |
285 | ||
286 | // Ordinarily, we can rely on the visit order of HIR intravisit | |
287 | // to correspond to the actual execution order of statements. | |
74b04a01 | 288 | // However, there's a weird corner case with compound assignment |
dfeec247 XL |
289 | // operators (e.g. `a += b`). The evaluation order depends on whether |
290 | // or not the operator is overloaded (e.g. whether or not a trait | |
291 | // like AddAssign is implemented). | |
292 | ||
293 | // For primitive types (which, despite having a trait impl, don't actually | |
294 | // end up calling it), the evluation order is right-to-left. For example, | |
295 | // the following code snippet: | |
296 | // | |
297 | // let y = &mut 0; | |
298 | // *{println!("LHS!"); y} += {println!("RHS!"); 1}; | |
299 | // | |
300 | // will print: | |
301 | // | |
302 | // RHS! | |
303 | // LHS! | |
304 | // | |
305 | // However, if the operator is used on a non-primitive type, | |
306 | // the evaluation order will be left-to-right, since the operator | |
307 | // actually get desugared to a method call. For example, this | |
308 | // nearly identical code snippet: | |
309 | // | |
310 | // let y = &mut String::new(); | |
311 | // *{println!("LHS String"); y} += {println!("RHS String"); "hi"}; | |
312 | // | |
313 | // will print: | |
314 | // LHS String | |
315 | // RHS String | |
316 | // | |
317 | // To determine the actual execution order, we need to perform | |
318 | // trait resolution. Unfortunately, we need to be able to compute | |
319 | // yield_in_scope before type checking is even done, as it gets | |
320 | // used by AST borrowcheck. | |
321 | // | |
322 | // Fortunately, we don't need to know the actual execution order. | |
323 | // It suffices to know the 'worst case' order with respect to yields. | |
324 | // Specifically, we need to know the highest 'expr_and_pat_count' | |
325 | // that we could assign to the yield expression. To do this, | |
326 | // we pick the greater of the two values from the left-hand | |
327 | // and right-hand expressions. This makes us overly conservative | |
328 | // about what types could possibly live across yield points, | |
329 | // but we will never fail to detect that a type does actually | |
330 | // live across a yield point. The latter part is critical - | |
331 | // we're already overly conservative about what types will live | |
332 | // across yield points, as the generated MIR will determine | |
333 | // when things are actually live. However, for typecheck to work | |
334 | // properly, we can't miss any types. | |
335 | ||
336 | match expr.kind { | |
337 | // Manually recurse over closures, because they are the only | |
338 | // case of nested bodies that share the parent environment. | |
339 | hir::ExprKind::Closure(.., body, _, _) => { | |
340 | let body = visitor.tcx.hir().body(body); | |
341 | visitor.visit_body(body); | |
342 | } | |
343 | hir::ExprKind::AssignOp(_, ref left_expr, ref right_expr) => { | |
344 | debug!( | |
345 | "resolve_expr - enabling pessimistic_yield, was previously {}", | |
346 | prev_pessimistic | |
347 | ); | |
348 | ||
349 | let start_point = visitor.fixup_scopes.len(); | |
350 | visitor.pessimistic_yield = true; | |
351 | ||
352 | // If the actual execution order turns out to be right-to-left, | |
353 | // then we're fine. However, if the actual execution order is left-to-right, | |
354 | // then we'll assign too low a count to any `yield` expressions | |
355 | // we encounter in 'right_expression' - they should really occur after all of the | |
356 | // expressions in 'left_expression'. | |
357 | visitor.visit_expr(&right_expr); | |
358 | visitor.pessimistic_yield = prev_pessimistic; | |
359 | ||
360 | debug!("resolve_expr - restoring pessimistic_yield to {}", prev_pessimistic); | |
361 | visitor.visit_expr(&left_expr); | |
362 | debug!("resolve_expr - fixing up counts to {}", visitor.expr_and_pat_count); | |
363 | ||
364 | // Remove and process any scopes pushed by the visitor | |
365 | let target_scopes = visitor.fixup_scopes.drain(start_point..); | |
366 | ||
367 | for scope in target_scopes { | |
368 | let mut yield_data = visitor.scope_tree.yield_in_scope.get_mut(&scope).unwrap(); | |
369 | let count = yield_data.expr_and_pat_count; | |
370 | let span = yield_data.span; | |
371 | ||
372 | // expr_and_pat_count never decreases. Since we recorded counts in yield_in_scope | |
373 | // before walking the left-hand side, it should be impossible for the recorded | |
374 | // count to be greater than the left-hand side count. | |
375 | if count > visitor.expr_and_pat_count { | |
376 | bug!( | |
377 | "Encountered greater count {} at span {:?} - expected no greater than {}", | |
378 | count, | |
379 | span, | |
380 | visitor.expr_and_pat_count | |
381 | ); | |
382 | } | |
383 | let new_count = visitor.expr_and_pat_count; | |
384 | debug!( | |
385 | "resolve_expr - increasing count for scope {:?} from {} to {} at span {:?}", | |
386 | scope, count, new_count, span | |
387 | ); | |
388 | ||
389 | yield_data.expr_and_pat_count = new_count; | |
390 | } | |
391 | } | |
392 | ||
393 | _ => intravisit::walk_expr(visitor, expr), | |
394 | } | |
395 | ||
396 | visitor.expr_and_pat_count += 1; | |
397 | ||
398 | debug!("resolve_expr post-increment {}, expr = {:?}", visitor.expr_and_pat_count, expr); | |
399 | ||
400 | if let hir::ExprKind::Yield(_, source) = &expr.kind { | |
401 | // Mark this expr's scope and all parent scopes as containing `yield`. | |
402 | let mut scope = Scope { id: expr.hir_id.local_id, data: ScopeData::Node }; | |
403 | loop { | |
404 | let data = YieldData { | |
405 | span: expr.span, | |
406 | expr_and_pat_count: visitor.expr_and_pat_count, | |
407 | source: *source, | |
408 | }; | |
409 | visitor.scope_tree.yield_in_scope.insert(scope, data); | |
410 | if visitor.pessimistic_yield { | |
411 | debug!("resolve_expr in pessimistic_yield - marking scope {:?} for fixup", scope); | |
412 | visitor.fixup_scopes.push(scope); | |
413 | } | |
414 | ||
415 | // Keep traversing up while we can. | |
416 | match visitor.scope_tree.parent_map.get(&scope) { | |
417 | // Don't cross from closure bodies to their parent. | |
418 | Some(&(superscope, _)) => match superscope.data { | |
419 | ScopeData::CallSite => break, | |
420 | _ => scope = superscope, | |
421 | }, | |
422 | None => break, | |
423 | } | |
424 | } | |
425 | } | |
426 | ||
427 | visitor.cx = prev_cx; | |
428 | } | |
429 | ||
430 | fn resolve_local<'tcx>( | |
431 | visitor: &mut RegionResolutionVisitor<'tcx>, | |
432 | pat: Option<&'tcx hir::Pat<'tcx>>, | |
433 | init: Option<&'tcx hir::Expr<'tcx>>, | |
434 | ) { | |
435 | debug!("resolve_local(pat={:?}, init={:?})", pat, init); | |
436 | ||
437 | let blk_scope = visitor.cx.var_parent.map(|(p, _)| p); | |
438 | ||
439 | // As an exception to the normal rules governing temporary | |
440 | // lifetimes, initializers in a let have a temporary lifetime | |
441 | // of the enclosing block. This means that e.g., a program | |
442 | // like the following is legal: | |
443 | // | |
444 | // let ref x = HashMap::new(); | |
445 | // | |
446 | // Because the hash map will be freed in the enclosing block. | |
447 | // | |
448 | // We express the rules more formally based on 3 grammars (defined | |
449 | // fully in the helpers below that implement them): | |
450 | // | |
451 | // 1. `E&`, which matches expressions like `&<rvalue>` that | |
452 | // own a pointer into the stack. | |
453 | // | |
454 | // 2. `P&`, which matches patterns like `ref x` or `(ref x, ref | |
455 | // y)` that produce ref bindings into the value they are | |
456 | // matched against or something (at least partially) owned by | |
457 | // the value they are matched against. (By partially owned, | |
458 | // I mean that creating a binding into a ref-counted or managed value | |
459 | // would still count.) | |
460 | // | |
461 | // 3. `ET`, which matches both rvalues like `foo()` as well as places | |
462 | // based on rvalues like `foo().x[2].y`. | |
463 | // | |
464 | // A subexpression `<rvalue>` that appears in a let initializer | |
465 | // `let pat [: ty] = expr` has an extended temporary lifetime if | |
466 | // any of the following conditions are met: | |
467 | // | |
468 | // A. `pat` matches `P&` and `expr` matches `ET` | |
469 | // (covers cases where `pat` creates ref bindings into an rvalue | |
470 | // produced by `expr`) | |
471 | // B. `ty` is a borrowed pointer and `expr` matches `ET` | |
472 | // (covers cases where coercion creates a borrow) | |
473 | // C. `expr` matches `E&` | |
474 | // (covers cases `expr` borrows an rvalue that is then assigned | |
475 | // to memory (at least partially) owned by the binding) | |
476 | // | |
477 | // Here are some examples hopefully giving an intuition where each | |
478 | // rule comes into play and why: | |
479 | // | |
480 | // Rule A. `let (ref x, ref y) = (foo().x, 44)`. The rvalue `(22, 44)` | |
481 | // would have an extended lifetime, but not `foo()`. | |
482 | // | |
483 | // Rule B. `let x = &foo().x`. The rvalue `foo()` would have extended | |
484 | // lifetime. | |
485 | // | |
486 | // In some cases, multiple rules may apply (though not to the same | |
487 | // rvalue). For example: | |
488 | // | |
489 | // let ref x = [&a(), &b()]; | |
490 | // | |
491 | // Here, the expression `[...]` has an extended lifetime due to rule | |
492 | // A, but the inner rvalues `a()` and `b()` have an extended lifetime | |
493 | // due to rule C. | |
494 | ||
495 | if let Some(expr) = init { | |
496 | record_rvalue_scope_if_borrow_expr(visitor, &expr, blk_scope); | |
497 | ||
498 | if let Some(pat) = pat { | |
499 | if is_binding_pat(pat) { | |
500 | record_rvalue_scope(visitor, &expr, blk_scope); | |
501 | } | |
502 | } | |
503 | } | |
504 | ||
505 | // Make sure we visit the initializer first, so expr_and_pat_count remains correct | |
506 | if let Some(expr) = init { | |
507 | visitor.visit_expr(expr); | |
508 | } | |
509 | if let Some(pat) = pat { | |
510 | visitor.visit_pat(pat); | |
511 | } | |
512 | ||
513 | /// Returns `true` if `pat` match the `P&` non-terminal. | |
514 | /// | |
515 | /// ```text | |
516 | /// P& = ref X | |
517 | /// | StructName { ..., P&, ... } | |
518 | /// | VariantName(..., P&, ...) | |
519 | /// | [ ..., P&, ... ] | |
520 | /// | ( ..., P&, ... ) | |
521 | /// | ... "|" P& "|" ... | |
522 | /// | box P& | |
523 | /// ``` | |
524 | fn is_binding_pat(pat: &hir::Pat<'_>) -> bool { | |
525 | // Note that the code below looks for *explicit* refs only, that is, it won't | |
526 | // know about *implicit* refs as introduced in #42640. | |
527 | // | |
528 | // This is not a problem. For example, consider | |
529 | // | |
530 | // let (ref x, ref y) = (Foo { .. }, Bar { .. }); | |
531 | // | |
532 | // Due to the explicit refs on the left hand side, the below code would signal | |
533 | // that the temporary value on the right hand side should live until the end of | |
534 | // the enclosing block (as opposed to being dropped after the let is complete). | |
535 | // | |
536 | // To create an implicit ref, however, you must have a borrowed value on the RHS | |
537 | // already, as in this example (which won't compile before #42640): | |
538 | // | |
539 | // let Foo { x, .. } = &Foo { x: ..., ... }; | |
540 | // | |
541 | // in place of | |
542 | // | |
543 | // let Foo { ref x, .. } = Foo { ... }; | |
544 | // | |
545 | // In the former case (the implicit ref version), the temporary is created by the | |
546 | // & expression, and its lifetime would be extended to the end of the block (due | |
547 | // to a different rule, not the below code). | |
548 | match pat.kind { | |
549 | PatKind::Binding(hir::BindingAnnotation::Ref, ..) | |
550 | | PatKind::Binding(hir::BindingAnnotation::RefMut, ..) => true, | |
551 | ||
552 | PatKind::Struct(_, ref field_pats, _) => { | |
553 | field_pats.iter().any(|fp| is_binding_pat(&fp.pat)) | |
554 | } | |
555 | ||
556 | PatKind::Slice(ref pats1, ref pats2, ref pats3) => { | |
557 | pats1.iter().any(|p| is_binding_pat(&p)) | |
558 | || pats2.iter().any(|p| is_binding_pat(&p)) | |
559 | || pats3.iter().any(|p| is_binding_pat(&p)) | |
560 | } | |
561 | ||
562 | PatKind::Or(ref subpats) | |
563 | | PatKind::TupleStruct(_, ref subpats, _) | |
564 | | PatKind::Tuple(ref subpats, _) => subpats.iter().any(|p| is_binding_pat(&p)), | |
565 | ||
566 | PatKind::Box(ref subpat) => is_binding_pat(&subpat), | |
567 | ||
568 | PatKind::Ref(_, _) | |
569 | | PatKind::Binding(hir::BindingAnnotation::Unannotated, ..) | |
570 | | PatKind::Binding(hir::BindingAnnotation::Mutable, ..) | |
571 | | PatKind::Wild | |
572 | | PatKind::Path(_) | |
573 | | PatKind::Lit(_) | |
574 | | PatKind::Range(_, _, _) => false, | |
575 | } | |
576 | } | |
577 | ||
578 | /// If `expr` matches the `E&` grammar, then records an extended rvalue scope as appropriate: | |
579 | /// | |
580 | /// ```text | |
581 | /// E& = & ET | |
582 | /// | StructName { ..., f: E&, ... } | |
583 | /// | [ ..., E&, ... ] | |
584 | /// | ( ..., E&, ... ) | |
585 | /// | {...; E&} | |
586 | /// | box E& | |
587 | /// | E& as ... | |
588 | /// | ( E& ) | |
589 | /// ``` | |
590 | fn record_rvalue_scope_if_borrow_expr<'tcx>( | |
591 | visitor: &mut RegionResolutionVisitor<'tcx>, | |
592 | expr: &hir::Expr<'_>, | |
593 | blk_id: Option<Scope>, | |
594 | ) { | |
595 | match expr.kind { | |
596 | hir::ExprKind::AddrOf(_, _, ref subexpr) => { | |
597 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id); | |
598 | record_rvalue_scope(visitor, &subexpr, blk_id); | |
599 | } | |
600 | hir::ExprKind::Struct(_, fields, _) => { | |
601 | for field in fields { | |
602 | record_rvalue_scope_if_borrow_expr(visitor, &field.expr, blk_id); | |
603 | } | |
604 | } | |
605 | hir::ExprKind::Array(subexprs) | hir::ExprKind::Tup(subexprs) => { | |
606 | for subexpr in subexprs { | |
607 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id); | |
608 | } | |
609 | } | |
610 | hir::ExprKind::Cast(ref subexpr, _) => { | |
611 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id) | |
612 | } | |
613 | hir::ExprKind::Block(ref block, _) => { | |
614 | if let Some(ref subexpr) = block.expr { | |
615 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id); | |
616 | } | |
617 | } | |
618 | _ => {} | |
619 | } | |
620 | } | |
621 | ||
622 | /// Applied to an expression `expr` if `expr` -- or something owned or partially owned by | |
623 | /// `expr` -- is going to be indirectly referenced by a variable in a let statement. In that | |
624 | /// case, the "temporary lifetime" or `expr` is extended to be the block enclosing the `let` | |
625 | /// statement. | |
626 | /// | |
627 | /// More formally, if `expr` matches the grammar `ET`, record the rvalue scope of the matching | |
628 | /// `<rvalue>` as `blk_id`: | |
629 | /// | |
630 | /// ```text | |
631 | /// ET = *ET | |
632 | /// | ET[...] | |
633 | /// | ET.f | |
634 | /// | (ET) | |
635 | /// | <rvalue> | |
636 | /// ``` | |
637 | /// | |
638 | /// Note: ET is intended to match "rvalues or places based on rvalues". | |
639 | fn record_rvalue_scope<'tcx>( | |
640 | visitor: &mut RegionResolutionVisitor<'tcx>, | |
641 | expr: &hir::Expr<'_>, | |
642 | blk_scope: Option<Scope>, | |
643 | ) { | |
644 | let mut expr = expr; | |
645 | loop { | |
646 | // Note: give all the expressions matching `ET` with the | |
647 | // extended temporary lifetime, not just the innermost rvalue, | |
648 | // because in codegen if we must compile e.g., `*rvalue()` | |
649 | // into a temporary, we request the temporary scope of the | |
650 | // outer expression. | |
651 | visitor.scope_tree.record_rvalue_scope(expr.hir_id.local_id, blk_scope); | |
652 | ||
653 | match expr.kind { | |
654 | hir::ExprKind::AddrOf(_, _, ref subexpr) | |
655 | | hir::ExprKind::Unary(hir::UnOp::UnDeref, ref subexpr) | |
656 | | hir::ExprKind::Field(ref subexpr, _) | |
657 | | hir::ExprKind::Index(ref subexpr, _) => { | |
658 | expr = &subexpr; | |
659 | } | |
660 | _ => { | |
661 | return; | |
662 | } | |
663 | } | |
664 | } | |
665 | } | |
666 | } | |
667 | ||
668 | impl<'tcx> RegionResolutionVisitor<'tcx> { | |
669 | /// Records the current parent (if any) as the parent of `child_scope`. | |
670 | /// Returns the depth of `child_scope`. | |
671 | fn record_child_scope(&mut self, child_scope: Scope) -> ScopeDepth { | |
672 | let parent = self.cx.parent; | |
673 | self.scope_tree.record_scope_parent(child_scope, parent); | |
674 | // If `child_scope` has no parent, it must be the root node, and so has | |
675 | // a depth of 1. Otherwise, its depth is one more than its parent's. | |
676 | parent.map_or(1, |(_p, d)| d + 1) | |
677 | } | |
678 | ||
679 | /// Records the current parent (if any) as the parent of `child_scope`, | |
680 | /// and sets `child_scope` as the new current parent. | |
681 | fn enter_scope(&mut self, child_scope: Scope) { | |
682 | let child_depth = self.record_child_scope(child_scope); | |
683 | self.cx.parent = Some((child_scope, child_depth)); | |
684 | } | |
685 | ||
686 | fn enter_node_scope_with_dtor(&mut self, id: hir::ItemLocalId) { | |
687 | // If node was previously marked as a terminating scope during the | |
688 | // recursive visit of its parent node in the AST, then we need to | |
689 | // account for the destruction scope representing the scope of | |
690 | // the destructors that run immediately after it completes. | |
691 | if self.terminating_scopes.contains(&id) { | |
692 | self.enter_scope(Scope { id, data: ScopeData::Destruction }); | |
693 | } | |
694 | self.enter_scope(Scope { id, data: ScopeData::Node }); | |
695 | } | |
696 | } | |
697 | ||
698 | impl<'tcx> Visitor<'tcx> for RegionResolutionVisitor<'tcx> { | |
699 | type Map = Map<'tcx>; | |
700 | ||
701 | fn nested_visit_map(&mut self) -> NestedVisitorMap<'_, Self::Map> { | |
702 | NestedVisitorMap::None | |
703 | } | |
704 | ||
705 | fn visit_block(&mut self, b: &'tcx Block<'tcx>) { | |
706 | resolve_block(self, b); | |
707 | } | |
708 | ||
709 | fn visit_body(&mut self, body: &'tcx hir::Body<'tcx>) { | |
710 | let body_id = body.id(); | |
711 | let owner_id = self.tcx.hir().body_owner(body_id); | |
712 | ||
713 | debug!( | |
714 | "visit_body(id={:?}, span={:?}, body.id={:?}, cx.parent={:?})", | |
715 | owner_id, | |
716 | self.tcx.sess.source_map().span_to_string(body.value.span), | |
717 | body_id, | |
718 | self.cx.parent | |
719 | ); | |
720 | ||
721 | let outer_ec = mem::replace(&mut self.expr_and_pat_count, 0); | |
722 | let outer_cx = self.cx; | |
723 | let outer_ts = mem::take(&mut self.terminating_scopes); | |
724 | self.terminating_scopes.insert(body.value.hir_id.local_id); | |
725 | ||
726 | if let Some(root_id) = self.cx.root_id { | |
727 | self.scope_tree.record_closure_parent(body.value.hir_id.local_id, root_id); | |
728 | } | |
729 | self.cx.root_id = Some(body.value.hir_id.local_id); | |
730 | ||
731 | self.enter_scope(Scope { id: body.value.hir_id.local_id, data: ScopeData::CallSite }); | |
732 | self.enter_scope(Scope { id: body.value.hir_id.local_id, data: ScopeData::Arguments }); | |
733 | ||
734 | // The arguments and `self` are parented to the fn. | |
735 | self.cx.var_parent = self.cx.parent.take(); | |
736 | for param in body.params { | |
737 | self.visit_pat(¶m.pat); | |
738 | } | |
739 | ||
740 | // The body of the every fn is a root scope. | |
741 | self.cx.parent = self.cx.var_parent; | |
742 | if self.tcx.hir().body_owner_kind(owner_id).is_fn_or_closure() { | |
743 | self.visit_expr(&body.value) | |
744 | } else { | |
745 | // Only functions have an outer terminating (drop) scope, while | |
746 | // temporaries in constant initializers may be 'static, but only | |
747 | // according to rvalue lifetime semantics, using the same | |
748 | // syntactical rules used for let initializers. | |
749 | // | |
750 | // e.g., in `let x = &f();`, the temporary holding the result from | |
751 | // the `f()` call lives for the entirety of the surrounding block. | |
752 | // | |
753 | // Similarly, `const X: ... = &f();` would have the result of `f()` | |
754 | // live for `'static`, implying (if Drop restrictions on constants | |
755 | // ever get lifted) that the value *could* have a destructor, but | |
756 | // it'd get leaked instead of the destructor running during the | |
757 | // evaluation of `X` (if at all allowed by CTFE). | |
758 | // | |
759 | // However, `const Y: ... = g(&f());`, like `let y = g(&f());`, | |
760 | // would *not* let the `f()` temporary escape into an outer scope | |
761 | // (i.e., `'static`), which means that after `g` returns, it drops, | |
762 | // and all the associated destruction scope rules apply. | |
763 | self.cx.var_parent = None; | |
764 | resolve_local(self, None, Some(&body.value)); | |
765 | } | |
766 | ||
767 | if body.generator_kind.is_some() { | |
768 | self.scope_tree.body_expr_count.insert(body_id, self.expr_and_pat_count); | |
769 | } | |
770 | ||
771 | // Restore context we had at the start. | |
772 | self.expr_and_pat_count = outer_ec; | |
773 | self.cx = outer_cx; | |
774 | self.terminating_scopes = outer_ts; | |
775 | } | |
776 | ||
777 | fn visit_arm(&mut self, a: &'tcx Arm<'tcx>) { | |
778 | resolve_arm(self, a); | |
779 | } | |
780 | fn visit_pat(&mut self, p: &'tcx Pat<'tcx>) { | |
781 | resolve_pat(self, p); | |
782 | } | |
783 | fn visit_stmt(&mut self, s: &'tcx Stmt<'tcx>) { | |
784 | resolve_stmt(self, s); | |
785 | } | |
786 | fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) { | |
787 | resolve_expr(self, ex); | |
788 | } | |
789 | fn visit_local(&mut self, l: &'tcx Local<'tcx>) { | |
790 | resolve_local(self, Some(&l.pat), l.init.as_ref().map(|e| &**e)); | |
791 | } | |
792 | } | |
793 | ||
794 | fn region_scope_tree(tcx: TyCtxt<'_>, def_id: DefId) -> &ScopeTree { | |
795 | let closure_base_def_id = tcx.closure_base_def_id(def_id); | |
796 | if closure_base_def_id != def_id { | |
797 | return tcx.region_scope_tree(closure_base_def_id); | |
798 | } | |
799 | ||
800 | let id = tcx.hir().as_local_hir_id(def_id).unwrap(); | |
801 | let scope_tree = if let Some(body_id) = tcx.hir().maybe_body_owned_by(id) { | |
802 | let mut visitor = RegionResolutionVisitor { | |
803 | tcx, | |
804 | scope_tree: ScopeTree::default(), | |
805 | expr_and_pat_count: 0, | |
806 | cx: Context { root_id: None, parent: None, var_parent: None }, | |
807 | terminating_scopes: Default::default(), | |
808 | pessimistic_yield: false, | |
809 | fixup_scopes: vec![], | |
810 | }; | |
811 | ||
812 | let body = tcx.hir().body(body_id); | |
813 | visitor.scope_tree.root_body = Some(body.value.hir_id); | |
814 | ||
815 | // If the item is an associated const or a method, | |
816 | // record its impl/trait parent, as it can also have | |
817 | // lifetime parameters free in this body. | |
818 | match tcx.hir().get(id) { | |
819 | Node::ImplItem(_) | Node::TraitItem(_) => { | |
820 | visitor.scope_tree.root_parent = Some(tcx.hir().get_parent_item(id)); | |
821 | } | |
822 | _ => {} | |
823 | } | |
824 | ||
825 | visitor.visit_body(body); | |
826 | ||
827 | visitor.scope_tree | |
828 | } else { | |
829 | ScopeTree::default() | |
830 | }; | |
831 | ||
832 | tcx.arena.alloc(scope_tree) | |
833 | } | |
834 | ||
835 | pub fn provide(providers: &mut Providers<'_>) { | |
836 | *providers = Providers { region_scope_tree, ..*providers }; | |
837 | } |