]>
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; | |
5099ac24 | 13 | use rustc_hir::intravisit::{self, Visitor}; |
a2a8927a | 14 | use rustc_hir::{Arm, Block, Expr, Local, Pat, PatKind, Stmt}; |
dfeec247 | 15 | use rustc_index::vec::Idx; |
ba9703b0 | 16 | use rustc_middle::middle::region::*; |
ba9703b0 | 17 | use rustc_middle::ty::TyCtxt; |
dfeec247 XL |
18 | use rustc_span::source_map; |
19 | use rustc_span::Span; | |
dfeec247 XL |
20 | |
21 | use std::mem; | |
22 | ||
23 | #[derive(Debug, Copy, Clone)] | |
24 | pub struct Context { | |
dfeec247 XL |
25 | /// The scope that contains any new variables declared, plus its depth in |
26 | /// the scope tree. | |
27 | var_parent: Option<(Scope, ScopeDepth)>, | |
28 | ||
29 | /// Region parent of expressions, etc., plus its depth in the scope tree. | |
30 | parent: Option<(Scope, ScopeDepth)>, | |
31 | } | |
32 | ||
33 | struct RegionResolutionVisitor<'tcx> { | |
34 | tcx: TyCtxt<'tcx>, | |
35 | ||
36 | // The number of expressions and patterns visited in the current body. | |
37 | expr_and_pat_count: usize, | |
38 | // When this is `true`, we record the `Scopes` we encounter | |
39 | // when processing a Yield expression. This allows us to fix | |
40 | // up their indices. | |
41 | pessimistic_yield: bool, | |
42 | // Stores scopes when `pessimistic_yield` is `true`. | |
43 | fixup_scopes: Vec<Scope>, | |
44 | // The generated scope tree. | |
45 | scope_tree: ScopeTree, | |
46 | ||
47 | cx: Context, | |
48 | ||
49 | /// `terminating_scopes` is a set containing the ids of each | |
50 | /// statement, or conditional/repeating expression. These scopes | |
51 | /// are calling "terminating scopes" because, when attempting to | |
52 | /// find the scope of a temporary, by default we search up the | |
53 | /// enclosing scopes until we encounter the terminating scope. A | |
54 | /// conditional/repeating expression is one which is not | |
55 | /// guaranteed to execute exactly once upon entering the parent | |
56 | /// scope. This could be because the expression only executes | |
57 | /// conditionally, such as the expression `b` in `a && b`, or | |
58 | /// because the expression may execute many times, such as a loop | |
59 | /// body. The reason that we distinguish such expressions is that, | |
60 | /// upon exiting the parent scope, we cannot statically know how | |
61 | /// many times the expression executed, and thus if the expression | |
62 | /// creates temporaries we cannot know statically how many such | |
63 | /// temporaries we would have to cleanup. Therefore, we ensure that | |
64 | /// the temporaries never outlast the conditional/repeating | |
65 | /// expression, preventing the need for dynamic checks and/or | |
66 | /// arbitrary amounts of stack space. Terminating scopes end | |
67 | /// up being contained in a DestructionScope that contains the | |
68 | /// destructor's execution. | |
69 | terminating_scopes: FxHashSet<hir::ItemLocalId>, | |
70 | } | |
71 | ||
72 | /// Records the lifetime of a local variable as `cx.var_parent` | |
73 | fn record_var_lifetime( | |
74 | visitor: &mut RegionResolutionVisitor<'_>, | |
75 | var_id: hir::ItemLocalId, | |
76 | _sp: Span, | |
77 | ) { | |
78 | match visitor.cx.var_parent { | |
79 | None => { | |
80 | // this can happen in extern fn declarations like | |
81 | // | |
82 | // extern fn isalnum(c: c_int) -> c_int | |
83 | } | |
84 | Some((parent_scope, _)) => visitor.scope_tree.record_var_scope(var_id, parent_scope), | |
85 | } | |
86 | } | |
87 | ||
88 | fn resolve_block<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, blk: &'tcx hir::Block<'tcx>) { | |
89 | debug!("resolve_block(blk.hir_id={:?})", blk.hir_id); | |
90 | ||
91 | let prev_cx = visitor.cx; | |
92 | ||
93 | // We treat the tail expression in the block (if any) somewhat | |
94 | // differently from the statements. The issue has to do with | |
95 | // temporary lifetimes. Consider the following: | |
96 | // | |
97 | // quux({ | |
98 | // let inner = ... (&bar()) ...; | |
99 | // | |
100 | // (... (&foo()) ...) // (the tail expression) | |
101 | // }, other_argument()); | |
102 | // | |
103 | // Each of the statements within the block is a terminating | |
104 | // scope, and thus a temporary (e.g., the result of calling | |
105 | // `bar()` in the initializer expression for `let inner = ...;`) | |
106 | // will be cleaned up immediately after its corresponding | |
107 | // statement (i.e., `let inner = ...;`) executes. | |
108 | // | |
109 | // On the other hand, temporaries associated with evaluating the | |
110 | // tail expression for the block are assigned lifetimes so that | |
111 | // they will be cleaned up as part of the terminating scope | |
112 | // *surrounding* the block expression. Here, the terminating | |
113 | // scope for the block expression is the `quux(..)` call; so | |
114 | // those temporaries will only be cleaned up *after* both | |
115 | // `other_argument()` has run and also the call to `quux(..)` | |
116 | // itself has returned. | |
117 | ||
118 | visitor.enter_node_scope_with_dtor(blk.hir_id.local_id); | |
119 | visitor.cx.var_parent = visitor.cx.parent; | |
120 | ||
121 | { | |
122 | // This block should be kept approximately in sync with | |
123 | // `intravisit::walk_block`. (We manually walk the block, rather | |
124 | // than call `walk_block`, in order to maintain precise | |
125 | // index information.) | |
126 | ||
127 | for (i, statement) in blk.stmts.iter().enumerate() { | |
128 | match statement.kind { | |
129 | hir::StmtKind::Local(..) | hir::StmtKind::Item(..) => { | |
130 | // Each declaration introduces a subscope for bindings | |
131 | // introduced by the declaration; this subscope covers a | |
132 | // suffix of the block. Each subscope in a block has the | |
133 | // previous subscope in the block as a parent, except for | |
134 | // the first such subscope, which has the block itself as a | |
135 | // parent. | |
136 | visitor.enter_scope(Scope { | |
137 | id: blk.hir_id.local_id, | |
138 | data: ScopeData::Remainder(FirstStatementIndex::new(i)), | |
139 | }); | |
140 | visitor.cx.var_parent = visitor.cx.parent; | |
141 | } | |
142 | hir::StmtKind::Expr(..) | hir::StmtKind::Semi(..) => {} | |
143 | } | |
144 | visitor.visit_stmt(statement) | |
145 | } | |
146 | walk_list!(visitor, visit_expr, &blk.expr); | |
147 | } | |
148 | ||
149 | visitor.cx = prev_cx; | |
150 | } | |
151 | ||
152 | fn resolve_arm<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, arm: &'tcx hir::Arm<'tcx>) { | |
153 | let prev_cx = visitor.cx; | |
154 | ||
155 | visitor.enter_scope(Scope { id: arm.hir_id.local_id, data: ScopeData::Node }); | |
156 | visitor.cx.var_parent = visitor.cx.parent; | |
157 | ||
158 | visitor.terminating_scopes.insert(arm.body.hir_id.local_id); | |
159 | ||
160 | if let Some(hir::Guard::If(ref expr)) = arm.guard { | |
161 | visitor.terminating_scopes.insert(expr.hir_id.local_id); | |
162 | } | |
163 | ||
164 | intravisit::walk_arm(visitor, arm); | |
165 | ||
166 | visitor.cx = prev_cx; | |
167 | } | |
168 | ||
169 | fn resolve_pat<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, pat: &'tcx hir::Pat<'tcx>) { | |
170 | visitor.record_child_scope(Scope { id: pat.hir_id.local_id, data: ScopeData::Node }); | |
171 | ||
172 | // If this is a binding then record the lifetime of that binding. | |
173 | if let PatKind::Binding(..) = pat.kind { | |
174 | record_var_lifetime(visitor, pat.hir_id.local_id, pat.span); | |
175 | } | |
176 | ||
177 | debug!("resolve_pat - pre-increment {} pat = {:?}", visitor.expr_and_pat_count, pat); | |
178 | ||
179 | intravisit::walk_pat(visitor, pat); | |
180 | ||
181 | visitor.expr_and_pat_count += 1; | |
182 | ||
183 | debug!("resolve_pat - post-increment {} pat = {:?}", visitor.expr_and_pat_count, pat); | |
184 | } | |
185 | ||
186 | fn resolve_stmt<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, stmt: &'tcx hir::Stmt<'tcx>) { | |
187 | let stmt_id = stmt.hir_id.local_id; | |
188 | debug!("resolve_stmt(stmt.id={:?})", stmt_id); | |
189 | ||
190 | // Every statement will clean up the temporaries created during | |
191 | // execution of that statement. Therefore each statement has an | |
192 | // associated destruction scope that represents the scope of the | |
193 | // statement plus its destructors, and thus the scope for which | |
194 | // regions referenced by the destructors need to survive. | |
195 | visitor.terminating_scopes.insert(stmt_id); | |
196 | ||
197 | let prev_parent = visitor.cx.parent; | |
198 | visitor.enter_node_scope_with_dtor(stmt_id); | |
199 | ||
200 | intravisit::walk_stmt(visitor, stmt); | |
201 | ||
202 | visitor.cx.parent = prev_parent; | |
203 | } | |
204 | ||
205 | fn resolve_expr<'tcx>(visitor: &mut RegionResolutionVisitor<'tcx>, expr: &'tcx hir::Expr<'tcx>) { | |
206 | debug!("resolve_expr - pre-increment {} expr = {:?}", visitor.expr_and_pat_count, expr); | |
207 | ||
208 | let prev_cx = visitor.cx; | |
209 | visitor.enter_node_scope_with_dtor(expr.hir_id.local_id); | |
210 | ||
211 | { | |
212 | let terminating_scopes = &mut visitor.terminating_scopes; | |
213 | let mut terminating = |id: hir::ItemLocalId| { | |
214 | terminating_scopes.insert(id); | |
215 | }; | |
216 | match expr.kind { | |
217 | // Conditional or repeating scopes are always terminating | |
218 | // scopes, meaning that temporaries cannot outlive them. | |
219 | // This ensures fixed size stacks. | |
220 | hir::ExprKind::Binary( | |
221 | source_map::Spanned { node: hir::BinOpKind::And, .. }, | |
222 | _, | |
223 | ref r, | |
224 | ) | |
225 | | hir::ExprKind::Binary( | |
226 | source_map::Spanned { node: hir::BinOpKind::Or, .. }, | |
227 | _, | |
228 | ref r, | |
229 | ) => { | |
230 | // For shortcircuiting operators, mark the RHS as a terminating | |
231 | // scope since it only executes conditionally. | |
232 | terminating(r.hir_id.local_id); | |
233 | } | |
234 | ||
94222f64 | 235 | hir::ExprKind::If(_, ref then, Some(ref otherwise)) => { |
5869c6ff XL |
236 | terminating(then.hir_id.local_id); |
237 | terminating(otherwise.hir_id.local_id); | |
238 | } | |
239 | ||
94222f64 | 240 | hir::ExprKind::If(_, ref then, None) => { |
5869c6ff XL |
241 | terminating(then.hir_id.local_id); |
242 | } | |
243 | ||
244 | hir::ExprKind::Loop(ref body, _, _, _) => { | |
dfeec247 XL |
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 | |
5e7ed085 | 293 | // end up calling it), the evaluation order is right-to-left. For example, |
dfeec247 XL |
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 { | |
3c0e092e | 336 | // Manually recurse over closures and inline consts, because they are the only |
dfeec247 | 337 | // case of nested bodies that share the parent environment. |
923072b8 | 338 | hir::ExprKind::Closure { body, .. } |
3c0e092e | 339 | | hir::ExprKind::ConstBlock(hir::AnonConst { body, .. }) => { |
dfeec247 XL |
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 { | |
5099ac24 FG |
368 | let mut yield_data = |
369 | visitor.scope_tree.yield_in_scope.get_mut(&scope).unwrap().last_mut().unwrap(); | |
dfeec247 XL |
370 | let count = yield_data.expr_and_pat_count; |
371 | let span = yield_data.span; | |
372 | ||
373 | // expr_and_pat_count never decreases. Since we recorded counts in yield_in_scope | |
374 | // before walking the left-hand side, it should be impossible for the recorded | |
375 | // count to be greater than the left-hand side count. | |
376 | if count > visitor.expr_and_pat_count { | |
377 | bug!( | |
378 | "Encountered greater count {} at span {:?} - expected no greater than {}", | |
379 | count, | |
380 | span, | |
381 | visitor.expr_and_pat_count | |
382 | ); | |
383 | } | |
384 | let new_count = visitor.expr_and_pat_count; | |
385 | debug!( | |
386 | "resolve_expr - increasing count for scope {:?} from {} to {} at span {:?}", | |
387 | scope, count, new_count, span | |
388 | ); | |
389 | ||
390 | yield_data.expr_and_pat_count = new_count; | |
391 | } | |
392 | } | |
393 | ||
94222f64 XL |
394 | hir::ExprKind::If(ref cond, ref then, Some(ref otherwise)) => { |
395 | let expr_cx = visitor.cx; | |
396 | visitor.enter_scope(Scope { id: then.hir_id.local_id, data: ScopeData::IfThen }); | |
397 | visitor.cx.var_parent = visitor.cx.parent; | |
398 | visitor.visit_expr(cond); | |
399 | visitor.visit_expr(then); | |
400 | visitor.cx = expr_cx; | |
401 | visitor.visit_expr(otherwise); | |
402 | } | |
403 | ||
404 | hir::ExprKind::If(ref cond, ref then, None) => { | |
405 | let expr_cx = visitor.cx; | |
406 | visitor.enter_scope(Scope { id: then.hir_id.local_id, data: ScopeData::IfThen }); | |
407 | visitor.cx.var_parent = visitor.cx.parent; | |
408 | visitor.visit_expr(cond); | |
409 | visitor.visit_expr(then); | |
410 | visitor.cx = expr_cx; | |
411 | } | |
412 | ||
dfeec247 XL |
413 | _ => intravisit::walk_expr(visitor, expr), |
414 | } | |
415 | ||
416 | visitor.expr_and_pat_count += 1; | |
417 | ||
418 | debug!("resolve_expr post-increment {}, expr = {:?}", visitor.expr_and_pat_count, expr); | |
419 | ||
420 | if let hir::ExprKind::Yield(_, source) = &expr.kind { | |
421 | // Mark this expr's scope and all parent scopes as containing `yield`. | |
422 | let mut scope = Scope { id: expr.hir_id.local_id, data: ScopeData::Node }; | |
423 | loop { | |
a2a8927a XL |
424 | let span = match expr.kind { |
425 | hir::ExprKind::Yield(expr, hir::YieldSource::Await { .. }) => { | |
426 | expr.span.shrink_to_hi().to(expr.span) | |
427 | } | |
428 | _ => expr.span, | |
dfeec247 | 429 | }; |
a2a8927a XL |
430 | let data = |
431 | YieldData { span, expr_and_pat_count: visitor.expr_and_pat_count, source: *source }; | |
5099ac24 FG |
432 | match visitor.scope_tree.yield_in_scope.get_mut(&scope) { |
433 | Some(yields) => yields.push(data), | |
434 | None => { | |
435 | visitor.scope_tree.yield_in_scope.insert(scope, vec![data]); | |
436 | } | |
437 | } | |
438 | ||
dfeec247 XL |
439 | if visitor.pessimistic_yield { |
440 | debug!("resolve_expr in pessimistic_yield - marking scope {:?} for fixup", scope); | |
441 | visitor.fixup_scopes.push(scope); | |
442 | } | |
443 | ||
444 | // Keep traversing up while we can. | |
445 | match visitor.scope_tree.parent_map.get(&scope) { | |
446 | // Don't cross from closure bodies to their parent. | |
447 | Some(&(superscope, _)) => match superscope.data { | |
448 | ScopeData::CallSite => break, | |
449 | _ => scope = superscope, | |
450 | }, | |
451 | None => break, | |
452 | } | |
453 | } | |
454 | } | |
455 | ||
456 | visitor.cx = prev_cx; | |
457 | } | |
458 | ||
459 | fn resolve_local<'tcx>( | |
460 | visitor: &mut RegionResolutionVisitor<'tcx>, | |
461 | pat: Option<&'tcx hir::Pat<'tcx>>, | |
462 | init: Option<&'tcx hir::Expr<'tcx>>, | |
463 | ) { | |
464 | debug!("resolve_local(pat={:?}, init={:?})", pat, init); | |
465 | ||
466 | let blk_scope = visitor.cx.var_parent.map(|(p, _)| p); | |
467 | ||
468 | // As an exception to the normal rules governing temporary | |
469 | // lifetimes, initializers in a let have a temporary lifetime | |
470 | // of the enclosing block. This means that e.g., a program | |
471 | // like the following is legal: | |
472 | // | |
473 | // let ref x = HashMap::new(); | |
474 | // | |
475 | // Because the hash map will be freed in the enclosing block. | |
476 | // | |
477 | // We express the rules more formally based on 3 grammars (defined | |
478 | // fully in the helpers below that implement them): | |
479 | // | |
480 | // 1. `E&`, which matches expressions like `&<rvalue>` that | |
481 | // own a pointer into the stack. | |
482 | // | |
483 | // 2. `P&`, which matches patterns like `ref x` or `(ref x, ref | |
484 | // y)` that produce ref bindings into the value they are | |
485 | // matched against or something (at least partially) owned by | |
486 | // the value they are matched against. (By partially owned, | |
487 | // I mean that creating a binding into a ref-counted or managed value | |
488 | // would still count.) | |
489 | // | |
490 | // 3. `ET`, which matches both rvalues like `foo()` as well as places | |
491 | // based on rvalues like `foo().x[2].y`. | |
492 | // | |
493 | // A subexpression `<rvalue>` that appears in a let initializer | |
494 | // `let pat [: ty] = expr` has an extended temporary lifetime if | |
495 | // any of the following conditions are met: | |
496 | // | |
497 | // A. `pat` matches `P&` and `expr` matches `ET` | |
498 | // (covers cases where `pat` creates ref bindings into an rvalue | |
499 | // produced by `expr`) | |
500 | // B. `ty` is a borrowed pointer and `expr` matches `ET` | |
501 | // (covers cases where coercion creates a borrow) | |
502 | // C. `expr` matches `E&` | |
503 | // (covers cases `expr` borrows an rvalue that is then assigned | |
504 | // to memory (at least partially) owned by the binding) | |
505 | // | |
506 | // Here are some examples hopefully giving an intuition where each | |
507 | // rule comes into play and why: | |
508 | // | |
509 | // Rule A. `let (ref x, ref y) = (foo().x, 44)`. The rvalue `(22, 44)` | |
510 | // would have an extended lifetime, but not `foo()`. | |
511 | // | |
512 | // Rule B. `let x = &foo().x`. The rvalue `foo()` would have extended | |
513 | // lifetime. | |
514 | // | |
515 | // In some cases, multiple rules may apply (though not to the same | |
516 | // rvalue). For example: | |
517 | // | |
518 | // let ref x = [&a(), &b()]; | |
519 | // | |
520 | // Here, the expression `[...]` has an extended lifetime due to rule | |
521 | // A, but the inner rvalues `a()` and `b()` have an extended lifetime | |
522 | // due to rule C. | |
523 | ||
524 | if let Some(expr) = init { | |
525 | record_rvalue_scope_if_borrow_expr(visitor, &expr, blk_scope); | |
526 | ||
527 | if let Some(pat) = pat { | |
528 | if is_binding_pat(pat) { | |
923072b8 FG |
529 | visitor.scope_tree.record_rvalue_candidate( |
530 | expr.hir_id, | |
531 | RvalueCandidateType::Pattern { | |
532 | target: expr.hir_id.local_id, | |
533 | lifetime: blk_scope, | |
534 | }, | |
535 | ); | |
dfeec247 XL |
536 | } |
537 | } | |
538 | } | |
539 | ||
540 | // Make sure we visit the initializer first, so expr_and_pat_count remains correct | |
541 | if let Some(expr) = init { | |
542 | visitor.visit_expr(expr); | |
543 | } | |
544 | if let Some(pat) = pat { | |
545 | visitor.visit_pat(pat); | |
546 | } | |
547 | ||
548 | /// Returns `true` if `pat` match the `P&` non-terminal. | |
549 | /// | |
550 | /// ```text | |
551 | /// P& = ref X | |
552 | /// | StructName { ..., P&, ... } | |
553 | /// | VariantName(..., P&, ...) | |
554 | /// | [ ..., P&, ... ] | |
555 | /// | ( ..., P&, ... ) | |
556 | /// | ... "|" P& "|" ... | |
557 | /// | box P& | |
558 | /// ``` | |
559 | fn is_binding_pat(pat: &hir::Pat<'_>) -> bool { | |
560 | // Note that the code below looks for *explicit* refs only, that is, it won't | |
561 | // know about *implicit* refs as introduced in #42640. | |
562 | // | |
563 | // This is not a problem. For example, consider | |
564 | // | |
565 | // let (ref x, ref y) = (Foo { .. }, Bar { .. }); | |
566 | // | |
567 | // Due to the explicit refs on the left hand side, the below code would signal | |
568 | // that the temporary value on the right hand side should live until the end of | |
569 | // the enclosing block (as opposed to being dropped after the let is complete). | |
570 | // | |
571 | // To create an implicit ref, however, you must have a borrowed value on the RHS | |
572 | // already, as in this example (which won't compile before #42640): | |
573 | // | |
574 | // let Foo { x, .. } = &Foo { x: ..., ... }; | |
575 | // | |
576 | // in place of | |
577 | // | |
578 | // let Foo { ref x, .. } = Foo { ... }; | |
579 | // | |
580 | // In the former case (the implicit ref version), the temporary is created by the | |
581 | // & expression, and its lifetime would be extended to the end of the block (due | |
582 | // to a different rule, not the below code). | |
583 | match pat.kind { | |
584 | PatKind::Binding(hir::BindingAnnotation::Ref, ..) | |
585 | | PatKind::Binding(hir::BindingAnnotation::RefMut, ..) => true, | |
586 | ||
587 | PatKind::Struct(_, ref field_pats, _) => { | |
588 | field_pats.iter().any(|fp| is_binding_pat(&fp.pat)) | |
589 | } | |
590 | ||
591 | PatKind::Slice(ref pats1, ref pats2, ref pats3) => { | |
592 | pats1.iter().any(|p| is_binding_pat(&p)) | |
593 | || pats2.iter().any(|p| is_binding_pat(&p)) | |
594 | || pats3.iter().any(|p| is_binding_pat(&p)) | |
595 | } | |
596 | ||
597 | PatKind::Or(ref subpats) | |
598 | | PatKind::TupleStruct(_, ref subpats, _) | |
599 | | PatKind::Tuple(ref subpats, _) => subpats.iter().any(|p| is_binding_pat(&p)), | |
600 | ||
601 | PatKind::Box(ref subpat) => is_binding_pat(&subpat), | |
602 | ||
603 | PatKind::Ref(_, _) | |
ba9703b0 XL |
604 | | PatKind::Binding( |
605 | hir::BindingAnnotation::Unannotated | hir::BindingAnnotation::Mutable, | |
606 | .., | |
607 | ) | |
dfeec247 XL |
608 | | PatKind::Wild |
609 | | PatKind::Path(_) | |
610 | | PatKind::Lit(_) | |
611 | | PatKind::Range(_, _, _) => false, | |
612 | } | |
613 | } | |
614 | ||
615 | /// If `expr` matches the `E&` grammar, then records an extended rvalue scope as appropriate: | |
616 | /// | |
617 | /// ```text | |
618 | /// E& = & ET | |
619 | /// | StructName { ..., f: E&, ... } | |
620 | /// | [ ..., E&, ... ] | |
621 | /// | ( ..., E&, ... ) | |
622 | /// | {...; E&} | |
623 | /// | box E& | |
624 | /// | E& as ... | |
625 | /// | ( E& ) | |
626 | /// ``` | |
627 | fn record_rvalue_scope_if_borrow_expr<'tcx>( | |
628 | visitor: &mut RegionResolutionVisitor<'tcx>, | |
629 | expr: &hir::Expr<'_>, | |
630 | blk_id: Option<Scope>, | |
631 | ) { | |
632 | match expr.kind { | |
923072b8 FG |
633 | hir::ExprKind::AddrOf(_, _, subexpr) => { |
634 | record_rvalue_scope_if_borrow_expr(visitor, subexpr, blk_id); | |
635 | visitor.scope_tree.record_rvalue_candidate( | |
636 | subexpr.hir_id, | |
637 | RvalueCandidateType::Borrow { | |
638 | target: subexpr.hir_id.local_id, | |
639 | lifetime: blk_id, | |
640 | }, | |
641 | ); | |
dfeec247 XL |
642 | } |
643 | hir::ExprKind::Struct(_, fields, _) => { | |
644 | for field in fields { | |
645 | record_rvalue_scope_if_borrow_expr(visitor, &field.expr, blk_id); | |
646 | } | |
647 | } | |
648 | hir::ExprKind::Array(subexprs) | hir::ExprKind::Tup(subexprs) => { | |
649 | for subexpr in subexprs { | |
650 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id); | |
651 | } | |
652 | } | |
653 | hir::ExprKind::Cast(ref subexpr, _) => { | |
654 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id) | |
655 | } | |
656 | hir::ExprKind::Block(ref block, _) => { | |
657 | if let Some(ref subexpr) = block.expr { | |
658 | record_rvalue_scope_if_borrow_expr(visitor, &subexpr, blk_id); | |
659 | } | |
660 | } | |
923072b8 FG |
661 | hir::ExprKind::Call(..) | hir::ExprKind::MethodCall(..) => { |
662 | // FIXME(@dingxiangfei2009): choose call arguments here | |
663 | // for candidacy for extended parameter rule application | |
664 | } | |
665 | hir::ExprKind::Index(..) => { | |
666 | // FIXME(@dingxiangfei2009): select the indices | |
667 | // as candidate for rvalue scope rules | |
dfeec247 | 668 | } |
923072b8 | 669 | _ => {} |
dfeec247 XL |
670 | } |
671 | } | |
672 | } | |
673 | ||
674 | impl<'tcx> RegionResolutionVisitor<'tcx> { | |
675 | /// Records the current parent (if any) as the parent of `child_scope`. | |
676 | /// Returns the depth of `child_scope`. | |
677 | fn record_child_scope(&mut self, child_scope: Scope) -> ScopeDepth { | |
678 | let parent = self.cx.parent; | |
679 | self.scope_tree.record_scope_parent(child_scope, parent); | |
680 | // If `child_scope` has no parent, it must be the root node, and so has | |
681 | // a depth of 1. Otherwise, its depth is one more than its parent's. | |
682 | parent.map_or(1, |(_p, d)| d + 1) | |
683 | } | |
684 | ||
685 | /// Records the current parent (if any) as the parent of `child_scope`, | |
686 | /// and sets `child_scope` as the new current parent. | |
687 | fn enter_scope(&mut self, child_scope: Scope) { | |
688 | let child_depth = self.record_child_scope(child_scope); | |
689 | self.cx.parent = Some((child_scope, child_depth)); | |
690 | } | |
691 | ||
692 | fn enter_node_scope_with_dtor(&mut self, id: hir::ItemLocalId) { | |
693 | // If node was previously marked as a terminating scope during the | |
694 | // recursive visit of its parent node in the AST, then we need to | |
695 | // account for the destruction scope representing the scope of | |
696 | // the destructors that run immediately after it completes. | |
697 | if self.terminating_scopes.contains(&id) { | |
698 | self.enter_scope(Scope { id, data: ScopeData::Destruction }); | |
699 | } | |
700 | self.enter_scope(Scope { id, data: ScopeData::Node }); | |
701 | } | |
702 | } | |
703 | ||
704 | impl<'tcx> Visitor<'tcx> for RegionResolutionVisitor<'tcx> { | |
dfeec247 XL |
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(); | |
5e7ed085 | 711 | let owner_id = self.tcx.hir().body_owner_def_id(body_id); |
dfeec247 XL |
712 | |
713 | debug!( | |
714 | "visit_body(id={:?}, span={:?}, body.id={:?}, cx.parent={:?})", | |
715 | owner_id, | |
17df50a5 | 716 | self.tcx.sess.source_map().span_to_diagnostic_string(body.value.span), |
dfeec247 XL |
717 | body_id, |
718 | self.cx.parent | |
719 | ); | |
720 | ||
ba9703b0 XL |
721 | // Save all state that is specific to the outer function |
722 | // body. These will be restored once down below, once we've | |
723 | // visited the body. | |
dfeec247 XL |
724 | let outer_ec = mem::replace(&mut self.expr_and_pat_count, 0); |
725 | let outer_cx = self.cx; | |
726 | let outer_ts = mem::take(&mut self.terminating_scopes); | |
ba9703b0 XL |
727 | // The 'pessimistic yield' flag is set to true when we are |
728 | // processing a `+=` statement and have to make pessimistic | |
729 | // control flow assumptions. This doesn't apply to nested | |
730 | // bodies within the `+=` statements. See #69307. | |
731 | let outer_pessimistic_yield = mem::replace(&mut self.pessimistic_yield, false); | |
dfeec247 XL |
732 | self.terminating_scopes.insert(body.value.hir_id.local_id); |
733 | ||
dfeec247 XL |
734 | self.enter_scope(Scope { id: body.value.hir_id.local_id, data: ScopeData::CallSite }); |
735 | self.enter_scope(Scope { id: body.value.hir_id.local_id, data: ScopeData::Arguments }); | |
736 | ||
737 | // The arguments and `self` are parented to the fn. | |
738 | self.cx.var_parent = self.cx.parent.take(); | |
739 | for param in body.params { | |
740 | self.visit_pat(¶m.pat); | |
741 | } | |
742 | ||
743 | // The body of the every fn is a root scope. | |
744 | self.cx.parent = self.cx.var_parent; | |
745 | if self.tcx.hir().body_owner_kind(owner_id).is_fn_or_closure() { | |
746 | self.visit_expr(&body.value) | |
747 | } else { | |
748 | // Only functions have an outer terminating (drop) scope, while | |
749 | // temporaries in constant initializers may be 'static, but only | |
750 | // according to rvalue lifetime semantics, using the same | |
751 | // syntactical rules used for let initializers. | |
752 | // | |
753 | // e.g., in `let x = &f();`, the temporary holding the result from | |
754 | // the `f()` call lives for the entirety of the surrounding block. | |
755 | // | |
756 | // Similarly, `const X: ... = &f();` would have the result of `f()` | |
757 | // live for `'static`, implying (if Drop restrictions on constants | |
758 | // ever get lifted) that the value *could* have a destructor, but | |
759 | // it'd get leaked instead of the destructor running during the | |
760 | // evaluation of `X` (if at all allowed by CTFE). | |
761 | // | |
762 | // However, `const Y: ... = g(&f());`, like `let y = g(&f());`, | |
763 | // would *not* let the `f()` temporary escape into an outer scope | |
764 | // (i.e., `'static`), which means that after `g` returns, it drops, | |
765 | // and all the associated destruction scope rules apply. | |
766 | self.cx.var_parent = None; | |
767 | resolve_local(self, None, Some(&body.value)); | |
768 | } | |
769 | ||
770 | if body.generator_kind.is_some() { | |
771 | self.scope_tree.body_expr_count.insert(body_id, self.expr_and_pat_count); | |
772 | } | |
773 | ||
774 | // Restore context we had at the start. | |
775 | self.expr_and_pat_count = outer_ec; | |
776 | self.cx = outer_cx; | |
777 | self.terminating_scopes = outer_ts; | |
ba9703b0 | 778 | self.pessimistic_yield = outer_pessimistic_yield; |
dfeec247 XL |
779 | } |
780 | ||
781 | fn visit_arm(&mut self, a: &'tcx Arm<'tcx>) { | |
782 | resolve_arm(self, a); | |
783 | } | |
784 | fn visit_pat(&mut self, p: &'tcx Pat<'tcx>) { | |
785 | resolve_pat(self, p); | |
786 | } | |
787 | fn visit_stmt(&mut self, s: &'tcx Stmt<'tcx>) { | |
788 | resolve_stmt(self, s); | |
789 | } | |
790 | fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) { | |
791 | resolve_expr(self, ex); | |
792 | } | |
793 | fn visit_local(&mut self, l: &'tcx Local<'tcx>) { | |
c295e0f8 | 794 | resolve_local(self, Some(&l.pat), l.init); |
dfeec247 XL |
795 | } |
796 | } | |
797 | ||
923072b8 FG |
798 | /// Per-body `region::ScopeTree`. The `DefId` should be the owner `DefId` for the body; |
799 | /// in the case of closures, this will be redirected to the enclosing function. | |
800 | /// | |
801 | /// Performance: This is a query rather than a simple function to enable | |
802 | /// re-use in incremental scenarios. We may sometimes need to rerun the | |
803 | /// type checker even when the HIR hasn't changed, and in those cases | |
804 | /// we can avoid reconstructing the region scope tree. | |
805 | pub fn region_scope_tree(tcx: TyCtxt<'_>, def_id: DefId) -> &ScopeTree { | |
3c0e092e XL |
806 | let typeck_root_def_id = tcx.typeck_root_def_id(def_id); |
807 | if typeck_root_def_id != def_id { | |
808 | return tcx.region_scope_tree(typeck_root_def_id); | |
dfeec247 XL |
809 | } |
810 | ||
3dfed10e | 811 | let id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local()); |
dfeec247 XL |
812 | let scope_tree = if let Some(body_id) = tcx.hir().maybe_body_owned_by(id) { |
813 | let mut visitor = RegionResolutionVisitor { | |
814 | tcx, | |
815 | scope_tree: ScopeTree::default(), | |
816 | expr_and_pat_count: 0, | |
cdc7bbd5 | 817 | cx: Context { parent: None, var_parent: None }, |
dfeec247 XL |
818 | terminating_scopes: Default::default(), |
819 | pessimistic_yield: false, | |
820 | fixup_scopes: vec![], | |
821 | }; | |
822 | ||
823 | let body = tcx.hir().body(body_id); | |
824 | visitor.scope_tree.root_body = Some(body.value.hir_id); | |
dfeec247 | 825 | visitor.visit_body(body); |
dfeec247 XL |
826 | visitor.scope_tree |
827 | } else { | |
828 | ScopeTree::default() | |
829 | }; | |
830 | ||
831 | tcx.arena.alloc(scope_tree) | |
832 | } |