src/librustc_typeck/check/generator_interior.rs

   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.
   5
   6 use super::FnCtxt;
   7 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
   8 use rustc_hir as hir;
   9 use rustc_hir::def::{CtorKind, DefKind, Res};
  10 use rustc_hir::def_id::DefId;
  11 use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
  12 use rustc_hir::{Expr, ExprKind, Pat, PatKind};
  13 use rustc_middle::middle::region::{self, YieldData};
  14 use rustc_middle::ty::{self, Ty};
  15 use rustc_span::Span;
  16
  17 struct InteriorVisitor<'a, 'tcx> {
  18     fcx: &'a FnCtxt<'a, 'tcx>,
  19     closure_def_id: DefId,
  20     types: FxHashMap<ty::GeneratorInteriorTypeCause<'tcx>, usize>,
  21     region_scope_tree: &'tcx region::ScopeTree,
  22     expr_count: usize,
  23     kind: hir::GeneratorKind,
  24     prev_unresolved_span: Option<Span>,
  25 }
  26
  27 impl<'a, 'tcx> InteriorVisitor<'a, 'tcx> {
  28     fn record(
  29         &mut self,
  30         ty: Ty<'tcx>,
  31         scope: Option<region::Scope>,
  32         expr: Option<&'tcx Expr<'tcx>>,
  33         source_span: Span,
  34         is_upvar: bool,
  35     ) {
  36         use rustc_span::DUMMY_SP;
  37
  38         debug!(
  39             "generator_interior: attempting to record type {:?} {:?} {:?} {:?}",
  40             ty, scope, expr, source_span
  41         );
  42
  43         let live_across_yield = scope
  44             .map(|s| {
  45                 self.region_scope_tree.yield_in_scope(s).and_then(|yield_data| {
  46                     // If we are recording an expression that is the last yield
  47                     // in the scope, or that has a postorder CFG index larger
  48                     // than the one of all of the yields, then its value can't
  49                     // be storage-live (and therefore live) at any of the yields.
  50                     //
  51                     // See the mega-comment at `yield_in_scope` for a proof.
  52
  53                     debug!(
  54                         "comparing counts yield: {} self: {}, source_span = {:?}",
  55                         yield_data.expr_and_pat_count, self.expr_count, source_span
  56                     );
  57
  58                     if yield_data.expr_and_pat_count >= self.expr_count {
  59                         Some(yield_data)
  60                     } else {
  61                         None
  62                     }
  63                 })
  64             })
  65             .unwrap_or_else(|| {
  66                 Some(YieldData { span: DUMMY_SP, expr_and_pat_count: 0, source: self.kind.into() })
  67             });
  68
  69         if let Some(yield_data) = live_across_yield {
  70             let ty = self.fcx.resolve_vars_if_possible(&ty);
  71             debug!(
  72                 "type in expr = {:?}, scope = {:?}, type = {:?}, count = {}, yield_span = {:?}",
  73                 expr, scope, ty, self.expr_count, yield_data.span
  74             );
  75
  76             if let Some((unresolved_type, unresolved_type_span)) =
  77                 self.fcx.unresolved_type_vars(&ty)
  78             {
  79                 let note = format!(
  80                     "the type is part of the {} because of this {}",
  81                     self.kind, yield_data.source
  82                 );
  83
  84                 // If unresolved type isn't a ty_var then unresolved_type_span is None
  85                 let span = self
  86                     .prev_unresolved_span
  87                     .unwrap_or_else(|| unresolved_type_span.unwrap_or(source_span));
  88                 self.fcx
  89                     .need_type_info_err_in_generator(self.kind, span, unresolved_type)
  90                     .span_note(yield_data.span, &*note)
  91                     .emit();
  92             } else {
  93                 // Map the type to the number of types added before it
  94                 let entries = self.types.len();
  95                 let scope_span = scope.map(|s| s.span(self.fcx.tcx, self.region_scope_tree));
  96                 self.types
  97                     .entry(ty::GeneratorInteriorTypeCause {
  98                         span: source_span,
  99                         ty: &ty,
 100                         scope_span,
 101                         yield_span: Some(yield_data.span),
 102                         expr: expr.map(|e| e.hir_id),
 103                     })
 104                     .or_insert(entries);
 105             }
 106         } else {
 107             debug!(
 108                 "no type in expr = {:?}, count = {:?}, span = {:?}",
 109                 expr,
 110                 self.expr_count,
 111                 expr.map(|e| e.span)
 112             );
 113             let ty = self.fcx.resolve_vars_if_possible(&ty);
 114             if let Some((unresolved_type, unresolved_type_span)) =
 115                 self.fcx.unresolved_type_vars(&ty)
 116             {
 117                 debug!(
 118                     "remained unresolved_type = {:?}, unresolved_type_span: {:?}",
 119                     unresolved_type, unresolved_type_span
 120                 );
 121                 self.prev_unresolved_span = unresolved_type_span;
 122             } else {
 123                 if is_upvar {
 124                     let entries = self.types.len();
 125                     let scope_span = scope.map(|s| s.span(self.fcx.tcx, self.region_scope_tree));
 126                     self.types
 127                         .entry(ty::GeneratorInteriorTypeCause {
 128                             span: source_span,
 129                             ty: &ty,
 130                             scope_span,
 131                             yield_span: None,
 132                             expr: expr.map(|e| e.hir_id),
 133                         })
 134                         .or_insert(entries);
 135                 }
 136             }
 137         }
 138     }
 139 }
 140
 141 pub fn resolve_interior<'a, 'tcx>(
 142     fcx: &'a FnCtxt<'a, 'tcx>,
 143     def_id: DefId,
 144     body_id: hir::BodyId,
 145     interior: Ty<'tcx>,
 146     kind: hir::GeneratorKind,
 147 ) {
 148     let body = fcx.tcx.hir().body(body_id);
 149
 150     let closure_def_id = fcx.tcx.hir().body_owner_def_id(body_id).to_def_id();
 151
 152     let mut visitor = InteriorVisitor {
 153         fcx,
 154         closure_def_id,
 155         types: FxHashMap::default(),
 156         region_scope_tree: fcx.tcx.region_scope_tree(def_id),
 157         expr_count: 0,
 158         kind,
 159         prev_unresolved_span: None,
 160     };
 161     intravisit::walk_body(&mut visitor, body);
 162
 163     // Check that we visited the same amount of expressions and the RegionResolutionVisitor
 164     let region_expr_count = visitor.region_scope_tree.body_expr_count(body_id).unwrap();
 165     assert_eq!(region_expr_count, visitor.expr_count);
 166
 167     let mut types: Vec<_> = visitor.types.drain().collect();
 168
 169     // Sort types by insertion order
 170     types.sort_by_key(|t| t.1);
 171
 172     // The types in the generator interior contain lifetimes local to the generator itself,
 173     // which should not be exposed outside of the generator. Therefore, we replace these
 174     // lifetimes with existentially-bound lifetimes, which reflect the exact value of the
 175     // lifetimes not being known by users.
 176     //
 177     // These lifetimes are used in auto trait impl checking (for example,
 178     // if a Sync generator contains an &'α T, we need to check whether &'α T: Sync),
 179     // so knowledge of the exact relationships between them isn't particularly important.
 180
 181     debug!("types in generator {:?}, span = {:?}", types, body.value.span);
 182
 183     let mut counter = 0;
 184     let mut captured_tys = FxHashSet::default();
 185     let type_causes: Vec<_> = types
 186         .into_iter()
 187         .filter_map(|(mut cause, _)| {
 188             // Erase regions and canonicalize late-bound regions to deduplicate as many types as we
 189             // can.
 190             let erased = fcx.tcx.erase_regions(&cause.ty);
 191             if captured_tys.insert(erased) {
 192                 // Replace all regions inside the generator interior with late bound regions.
 193                 // Note that each region slot in the types gets a new fresh late bound region,
 194                 // which means that none of the regions inside relate to any other, even if
 195                 // typeck had previously found constraints that would cause them to be related.
 196                 let folded = fcx.tcx.fold_regions(&erased, &mut false, |_, current_depth| {
 197                     counter += 1;
 198                     fcx.tcx.mk_region(ty::ReLateBound(current_depth, ty::BrAnon(counter)))
 199                 });
 200
 201                 cause.ty = folded;
 202                 Some(cause)
 203             } else {
 204                 None
 205             }
 206         })
 207         .collect();
 208
 209     // Extract type components to build the witness type.
 210     let type_list = fcx.tcx.mk_type_list(type_causes.iter().map(|cause| cause.ty));
 211     let witness = fcx.tcx.mk_generator_witness(ty::Binder::bind(type_list));
 212
 213     // Store the generator types and spans into the tables for this generator.
 214     visitor.fcx.inh.tables.borrow_mut().generator_interior_types = type_causes;
 215
 216     debug!(
 217         "types in generator after region replacement {:?}, span = {:?}",
 218         witness, body.value.span
 219     );
 220
 221     // Unify the type variable inside the generator with the new witness
 222     match fcx.at(&fcx.misc(body.value.span), fcx.param_env).eq(interior, witness) {
 223         Ok(ok) => fcx.register_infer_ok_obligations(ok),
 224         _ => bug!(),
 225     }
 226 }
 227
 228 // This visitor has to have the same visit_expr calls as RegionResolutionVisitor in
 229 // librustc_middle/middle/region.rs since `expr_count` is compared against the results
 230 // there.
 231 impl<'a, 'tcx> Visitor<'tcx> for InteriorVisitor<'a, 'tcx> {
 232     type Map = intravisit::ErasedMap<'tcx>;
 233
 234     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 235         NestedVisitorMap::None
 236     }
 237
 238     fn visit_pat(&mut self, pat: &'tcx Pat<'tcx>) {
 239         intravisit::walk_pat(self, pat);
 240
 241         self.expr_count += 1;
 242
 243         if let PatKind::Binding(..) = pat.kind {
 244             let scope = self.region_scope_tree.var_scope(pat.hir_id.local_id);
 245             let ty = self.fcx.tables.borrow().pat_ty(pat);
 246             self.record(ty, Some(scope), None, pat.span, false);
 247         }
 248     }
 249
 250     fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
 251         match &expr.kind {
 252             ExprKind::Call(callee, args) => match &callee.kind {
 253                 ExprKind::Path(qpath) => {
 254                     let res = self.fcx.tables.borrow().qpath_res(qpath, callee.hir_id);
 255                     match res {
 256                         // Direct calls never need to keep the callee `ty::FnDef`
 257                         // ZST in a temporary, so skip its type, just in case it
 258                         // can significantly complicate the generator type.
 259                         Res::Def(
 260                             DefKind::Fn | DefKind::AssocFn | DefKind::Ctor(_, CtorKind::Fn),
 261                             _,
 262                         ) => {
 263                             // NOTE(eddyb) this assumes a path expression has
 264                             // no nested expressions to keep track of.
 265                             self.expr_count += 1;
 266
 267                             // Record the rest of the call expression normally.
 268                             for arg in *args {
 269                                 self.visit_expr(arg);
 270                             }
 271                         }
 272                         _ => intravisit::walk_expr(self, expr),
 273                     }
 274                 }
 275                 _ => intravisit::walk_expr(self, expr),
 276             },
 277             _ => intravisit::walk_expr(self, expr),
 278         }
 279
 280         self.expr_count += 1;
 281
 282         let scope = self.region_scope_tree.temporary_scope(expr.hir_id.local_id);
 283
 284         // If there are adjustments, then record the final type --
 285         // this is the actual value that is being produced.
 286         if let Some(adjusted_ty) = self.fcx.tables.borrow().expr_ty_adjusted_opt(expr) {
 287             self.record(adjusted_ty, scope, Some(expr), expr.span, false);
 288         }
 289
 290         // Also record the unadjusted type (which is the only type if
 291         // there are no adjustments). The reason for this is that the
 292         // unadjusted value is sometimes a "temporary" that would wind
 293         // up in a MIR temporary.
 294         //
 295         // As an example, consider an expression like `vec![].push()`.
 296         // Here, the `vec![]` would wind up MIR stored into a
 297         // temporary variable `t` which we can borrow to invoke
 298         // `<Vec<_>>::push(&mut t)`.
 299         //
 300         // Note that an expression can have many adjustments, and we
 301         // are just ignoring those intermediate types. This is because
 302         // those intermediate values are always linearly "consumed" by
 303         // the other adjustments, and hence would never be directly
 304         // captured in the MIR.
 305         //
 306         // (Note that this partly relies on the fact that the `Deref`
 307         // traits always return references, which means their content
 308         // can be reborrowed without needing to spill to a temporary.
 309         // If this were not the case, then we could conceivably have
 310         // to create intermediate temporaries.)
 311         //
 312         // The type table might not have information for this expression
 313         // if it is in a malformed scope. (#66387)
 314         if let Some(ty) = self.fcx.tables.borrow().expr_ty_opt(expr) {
 315             self.record(ty, scope, Some(expr), expr.span, false);
 316         } else {
 317             self.fcx.tcx.sess.delay_span_bug(expr.span, "no type for node");
 318         }
 319
 320         if let Some(upvars) = self.fcx.tcx.upvars(self.closure_def_id) {
 321             for (upvar_id, upvar) in upvars.iter() {
 322                 let upvar_ty = self.fcx.tables.borrow().node_type(*upvar_id);
 323                 debug!("type of upvar: {:?}", upvar_ty);
 324                 self.record(upvar_ty, scope, Some(expr), upvar.span, true);
 325             }
 326         }
 327     }
 328 }