1 //! This calculates the types which has storage which lives across a suspension point in a
2 //! generator from the perspective of typeck. The actual types used at runtime
3 //! is calculated in `rustc_mir::transform::generator` and may be a subset of the
4 //! types computed here.
7 use rustc_data_structures::fx::{FxHashSet, FxIndexSet};
9 use rustc_hir::def::{CtorKind, DefKind, Res};
10 use rustc_hir::def_id::DefId;
11 use rustc_hir::hir_id::HirIdSet;
12 use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
13 use rustc_hir::{Arm, Expr, ExprKind, Guard, HirId, Pat, PatKind};
14 use rustc_middle::middle::region::{self, YieldData};
15 use rustc_middle::ty::{self, Ty};
17 use smallvec::SmallVec;
19 struct InteriorVisitor<'a, 'tcx> {
20 fcx: &'a FnCtxt<'a, 'tcx>,
21 types: FxIndexSet<ty::GeneratorInteriorTypeCause<'tcx>>,
22 region_scope_tree: &'tcx region::ScopeTree,
24 kind: hir::GeneratorKind,
25 prev_unresolved_span: Option<Span>,
26 /// Match arm guards have temporary borrows from the pattern bindings.
27 /// In case there is a yield point in a guard with a reference to such bindings,
28 /// such borrows can span across this yield point.
29 /// As such, we need to track these borrows and record them despite of the fact
30 /// that they may succeed the said yield point in the post-order.
31 guard_bindings: SmallVec<[SmallVec<[HirId; 4]>; 1]>,
32 guard_bindings_set: HirIdSet,
35 impl<'a, 'tcx> InteriorVisitor<'a, 'tcx> {
39 scope: Option<region::Scope>,
40 expr: Option<&'tcx Expr<'tcx>>,
42 guard_borrowing_from_pattern: bool,
44 use rustc_span::DUMMY_SP;
47 "generator_interior: attempting to record type {:?} {:?} {:?} {:?}",
48 ty, scope, expr, source_span
51 let live_across_yield = scope
53 self.region_scope_tree.yield_in_scope(s).and_then(|yield_data| {
54 // If we are recording an expression that is the last yield
55 // in the scope, or that has a postorder CFG index larger
56 // than the one of all of the yields, then its value can't
57 // be storage-live (and therefore live) at any of the yields.
59 // See the mega-comment at `yield_in_scope` for a proof.
62 "comparing counts yield: {} self: {}, source_span = {:?}",
63 yield_data.expr_and_pat_count, self.expr_count, source_span
66 // If it is a borrowing happening in the guard,
67 // it needs to be recorded regardless because they
68 // do live across this yield point.
69 if guard_borrowing_from_pattern
70 || yield_data.expr_and_pat_count >= self.expr_count
79 Some(YieldData { span: DUMMY_SP, expr_and_pat_count: 0, source: self.kind.into() })
82 if let Some(yield_data) = live_across_yield {
83 let ty = self.fcx.resolve_vars_if_possible(ty);
85 "type in expr = {:?}, scope = {:?}, type = {:?}, count = {}, yield_span = {:?}",
86 expr, scope, ty, self.expr_count, yield_data.span
89 if let Some((unresolved_type, unresolved_type_span)) =
90 self.fcx.unresolved_type_vars(&ty)
93 "the type is part of the {} because of this {}",
94 self.kind, yield_data.source
97 // If unresolved type isn't a ty_var then unresolved_type_span is None
100 .unwrap_or_else(|| unresolved_type_span.unwrap_or(source_span));
102 .need_type_info_err_in_generator(self.kind, span, unresolved_type)
103 .span_note(yield_data.span, &*note)
106 // Insert the type into the ordered set.
107 let scope_span = scope.map(|s| s.span(self.fcx.tcx, self.region_scope_tree));
108 self.types.insert(ty::GeneratorInteriorTypeCause {
112 yield_span: yield_data.span,
113 expr: expr.map(|e| e.hir_id),
118 "no type in expr = {:?}, count = {:?}, span = {:?}",
123 let ty = self.fcx.resolve_vars_if_possible(ty);
124 if let Some((unresolved_type, unresolved_type_span)) =
125 self.fcx.unresolved_type_vars(&ty)
128 "remained unresolved_type = {:?}, unresolved_type_span: {:?}",
129 unresolved_type, unresolved_type_span
131 self.prev_unresolved_span = unresolved_type_span;
137 pub fn resolve_interior<'a, 'tcx>(
138 fcx: &'a FnCtxt<'a, 'tcx>,
140 body_id: hir::BodyId,
142 kind: hir::GeneratorKind,
144 let body = fcx.tcx.hir().body(body_id);
145 let mut visitor = InteriorVisitor {
147 types: FxIndexSet::default(),
148 region_scope_tree: fcx.tcx.region_scope_tree(def_id),
151 prev_unresolved_span: None,
152 guard_bindings: <_>::default(),
153 guard_bindings_set: <_>::default(),
155 intravisit::walk_body(&mut visitor, body);
157 // Check that we visited the same amount of expressions and the RegionResolutionVisitor
158 let region_expr_count = visitor.region_scope_tree.body_expr_count(body_id).unwrap();
159 assert_eq!(region_expr_count, visitor.expr_count);
161 // The types are already kept in insertion order.
162 let types = visitor.types;
164 // The types in the generator interior contain lifetimes local to the generator itself,
165 // which should not be exposed outside of the generator. Therefore, we replace these
166 // lifetimes with existentially-bound lifetimes, which reflect the exact value of the
167 // lifetimes not being known by users.
169 // These lifetimes are used in auto trait impl checking (for example,
170 // if a Sync generator contains an &'α T, we need to check whether &'α T: Sync),
171 // so knowledge of the exact relationships between them isn't particularly important.
173 debug!("types in generator {:?}, span = {:?}", types, body.value.span);
176 let mut captured_tys = FxHashSet::default();
177 let type_causes: Vec<_> = types
179 .filter_map(|mut cause| {
180 // Erase regions and canonicalize late-bound regions to deduplicate as many types as we
182 let erased = fcx.tcx.erase_regions(cause.ty);
183 if captured_tys.insert(erased) {
184 // Replace all regions inside the generator interior with late bound regions.
185 // Note that each region slot in the types gets a new fresh late bound region,
186 // which means that none of the regions inside relate to any other, even if
187 // typeck had previously found constraints that would cause them to be related.
188 let folded = fcx.tcx.fold_regions(erased, &mut false, |_, current_depth| {
189 let br = ty::BoundRegion {
190 var: ty::BoundVar::from_u32(counter),
191 kind: ty::BrAnon(counter),
193 let r = fcx.tcx.mk_region(ty::ReLateBound(current_depth, br));
206 // Extract type components to build the witness type.
207 let type_list = fcx.tcx.mk_type_list(type_causes.iter().map(|cause| cause.ty));
208 let bound_vars = fcx.tcx.mk_bound_variable_kinds(
209 (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i))),
212 fcx.tcx.mk_generator_witness(ty::Binder::bind_with_vars(type_list, bound_vars.clone()));
214 // Store the generator types and spans into the typeck results for this generator.
215 visitor.fcx.inh.typeck_results.borrow_mut().generator_interior_types =
216 ty::Binder::bind_with_vars(type_causes, bound_vars);
219 "types in generator after region replacement {:?}, span = {:?}",
220 witness, body.value.span
223 // Unify the type variable inside the generator with the new witness
224 match fcx.at(&fcx.misc(body.value.span), fcx.param_env).eq(interior, witness) {
225 Ok(ok) => fcx.register_infer_ok_obligations(ok),
230 // This visitor has to have the same visit_expr calls as RegionResolutionVisitor in
231 // librustc_middle/middle/region.rs since `expr_count` is compared against the results
233 impl<'a, 'tcx> Visitor<'tcx> for InteriorVisitor<'a, 'tcx> {
234 type Map = intravisit::ErasedMap<'tcx>;
236 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
237 NestedVisitorMap::None
240 fn visit_arm(&mut self, arm: &'tcx Arm<'tcx>) {
241 let Arm { guard, pat, body, .. } = arm;
243 if let Some(ref g) = guard {
244 self.guard_bindings.push(<_>::default());
246 guard_bindings_set: &mut self.guard_bindings_set,
250 .expect("should have pushed at least one earlier"),
255 Guard::If(ref e) => {
258 Guard::IfLet(ref pat, ref e) => {
264 let mut scope_var_ids =
265 self.guard_bindings.pop().expect("should have pushed at least one earlier");
266 for var_id in scope_var_ids.drain(..) {
267 self.guard_bindings_set.remove(&var_id);
270 self.visit_expr(body);
273 fn visit_pat(&mut self, pat: &'tcx Pat<'tcx>) {
274 intravisit::walk_pat(self, pat);
276 self.expr_count += 1;
278 if let PatKind::Binding(..) = pat.kind {
279 let scope = self.region_scope_tree.var_scope(pat.hir_id.local_id);
280 let ty = self.fcx.typeck_results.borrow().pat_ty(pat);
281 self.record(ty, Some(scope), None, pat.span, false);
285 fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
286 let mut guard_borrowing_from_pattern = false;
288 ExprKind::Call(callee, args) => match &callee.kind {
289 ExprKind::Path(qpath) => {
290 let res = self.fcx.typeck_results.borrow().qpath_res(qpath, callee.hir_id);
292 // Direct calls never need to keep the callee `ty::FnDef`
293 // ZST in a temporary, so skip its type, just in case it
294 // can significantly complicate the generator type.
296 DefKind::Fn | DefKind::AssocFn | DefKind::Ctor(_, CtorKind::Fn),
299 // NOTE(eddyb) this assumes a path expression has
300 // no nested expressions to keep track of.
301 self.expr_count += 1;
303 // Record the rest of the call expression normally.
305 self.visit_expr(arg);
308 _ => intravisit::walk_expr(self, expr),
311 _ => intravisit::walk_expr(self, expr),
313 ExprKind::Path(qpath) => {
314 intravisit::walk_expr(self, expr);
315 let res = self.fcx.typeck_results.borrow().qpath_res(qpath, expr.hir_id);
317 Res::Local(id) if self.guard_bindings_set.contains(&id) => {
318 guard_borrowing_from_pattern = true;
323 _ => intravisit::walk_expr(self, expr),
326 self.expr_count += 1;
328 let scope = self.region_scope_tree.temporary_scope(expr.hir_id.local_id);
330 // If there are adjustments, then record the final type --
331 // this is the actual value that is being produced.
332 if let Some(adjusted_ty) = self.fcx.typeck_results.borrow().expr_ty_adjusted_opt(expr) {
333 self.record(adjusted_ty, scope, Some(expr), expr.span, guard_borrowing_from_pattern);
336 // Also record the unadjusted type (which is the only type if
337 // there are no adjustments). The reason for this is that the
338 // unadjusted value is sometimes a "temporary" that would wind
339 // up in a MIR temporary.
341 // As an example, consider an expression like `vec![].push(x)`.
342 // Here, the `vec![]` would wind up MIR stored into a
343 // temporary variable `t` which we can borrow to invoke
344 // `<Vec<_>>::push(&mut t, x)`.
346 // Note that an expression can have many adjustments, and we
347 // are just ignoring those intermediate types. This is because
348 // those intermediate values are always linearly "consumed" by
349 // the other adjustments, and hence would never be directly
350 // captured in the MIR.
352 // (Note that this partly relies on the fact that the `Deref`
353 // traits always return references, which means their content
354 // can be reborrowed without needing to spill to a temporary.
355 // If this were not the case, then we could conceivably have
356 // to create intermediate temporaries.)
358 // The type table might not have information for this expression
359 // if it is in a malformed scope. (#66387)
360 if let Some(ty) = self.fcx.typeck_results.borrow().expr_ty_opt(expr) {
361 if guard_borrowing_from_pattern {
362 // Match guards create references to all the bindings in the pattern that are used
363 // in the guard, e.g. `y if is_even(y) => ...` becomes `is_even(*r_y)` where `r_y`
364 // is a reference to `y`, so we must record a reference to the type of the binding.
365 let tcx = self.fcx.tcx;
366 let ref_ty = tcx.mk_ref(
367 // Use `ReErased` as `resolve_interior` is going to replace all the regions anyway.
368 tcx.mk_region(ty::RegionKind::ReErased),
369 ty::TypeAndMut { ty, mutbl: hir::Mutability::Not },
371 self.record(ref_ty, scope, Some(expr), expr.span, guard_borrowing_from_pattern);
373 self.record(ty, scope, Some(expr), expr.span, guard_borrowing_from_pattern);
375 self.fcx.tcx.sess.delay_span_bug(expr.span, "no type for node");
380 struct ArmPatCollector<'a> {
381 guard_bindings_set: &'a mut HirIdSet,
382 guard_bindings: &'a mut SmallVec<[HirId; 4]>,
385 impl<'a, 'tcx> Visitor<'tcx> for ArmPatCollector<'a> {
386 type Map = intravisit::ErasedMap<'tcx>;
388 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
389 NestedVisitorMap::None
392 fn visit_pat(&mut self, pat: &'tcx Pat<'tcx>) {
393 intravisit::walk_pat(self, pat);
394 if let PatKind::Binding(_, id, ..) = pat.kind {
395 self.guard_bindings.push(id);
396 self.guard_bindings_set.insert(id);