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