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