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