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 rustc::hir::def_id::DefId;
   7 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
   8 use rustc::hir::{self, Pat, PatKind, Expr};
   9 use rustc::middle::region;
  10 use rustc::ty::{self, Ty};
  11 use syntax_pos::Span;
  12 use super::FnCtxt;
  13 use crate::util::nodemap::FxHashMap;
  14
  15 struct InteriorVisitor<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  16     fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
  17     types: FxHashMap<Ty<'tcx>, usize>,
  18     region_scope_tree: &'gcx region::ScopeTree,
  19     expr_count: usize,
  20 }
  21
  22 impl<'a, 'gcx, 'tcx> InteriorVisitor<'a, 'gcx, 'tcx> {
  23     fn record(&mut self,
  24               ty: Ty<'tcx>,
  25               scope: Option<region::Scope>,
  26               expr: Option<&'tcx Expr>,
  27               source_span: Span) {
  28         use syntax_pos::DUMMY_SP;
  29
  30         let live_across_yield = scope.map_or(Some(DUMMY_SP), |s| {
  31             self.region_scope_tree.yield_in_scope(s).and_then(|(yield_span, expr_count)| {
  32                 // If we are recording an expression that is the last yield
  33                 // in the scope, or that has a postorder CFG index larger
  34                 // than the one of all of the yields, then its value can't
  35                 // be storage-live (and therefore live) at any of the yields.
  36                 //
  37                 // See the mega-comment at `yield_in_scope` for a proof.
  38
  39                 debug!("comparing counts yield: {} self: {}, source_span = {:?}",
  40                        expr_count, self.expr_count, source_span);
  41
  42                 if expr_count >= self.expr_count {
  43                     Some(yield_span)
  44                 } else {
  45                     None
  46                 }
  47             })
  48         });
  49
  50         if let Some(yield_span) = live_across_yield {
  51             let ty = self.fcx.resolve_vars_if_possible(&ty);
  52
  53             debug!("type in expr = {:?}, scope = {:?}, type = {:?}, count = {}, yield_span = {:?}",
  54                    expr, scope, ty, self.expr_count, yield_span);
  55
  56             if let Some((unresolved_type, unresolved_type_span)) =
  57                 self.fcx.unresolved_type_vars(&ty)
  58             {
  59                 // If unresolved type isn't a ty_var then unresolved_type_span is None
  60                 self.fcx.need_type_info_err_in_generator(
  61                     unresolved_type_span.unwrap_or(yield_span),
  62                     unresolved_type)
  63                     .span_note(yield_span,
  64                                "the type is part of the generator because of this `yield`")
  65                     .emit();
  66             } else {
  67                 // Map the type to the number of types added before it
  68                 let entries = self.types.len();
  69                 self.types.entry(&ty).or_insert(entries);
  70             }
  71         } else {
  72             debug!("no type in expr = {:?}, count = {:?}, span = {:?}",
  73                    expr, self.expr_count, expr.map(|e| e.span));
  74         }
  75     }
  76 }
  77
  78 pub fn resolve_interior<'a, 'gcx, 'tcx>(fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
  79                                         def_id: DefId,
  80                                         body_id: hir::BodyId,
  81                                         interior: Ty<'tcx>) {
  82     let body = fcx.tcx.hir().body(body_id);
  83     let mut visitor = InteriorVisitor {
  84         fcx,
  85         types: FxHashMap::default(),
  86         region_scope_tree: fcx.tcx.region_scope_tree(def_id),
  87         expr_count: 0,
  88     };
  89     intravisit::walk_body(&mut visitor, body);
  90
  91     // Check that we visited the same amount of expressions and the RegionResolutionVisitor
  92     let region_expr_count = visitor.region_scope_tree.body_expr_count(body_id).unwrap();
  93     assert_eq!(region_expr_count, visitor.expr_count);
  94
  95     let mut types: Vec<_> = visitor.types.drain().collect();
  96
  97     // Sort types by insertion order
  98     types.sort_by_key(|t| t.1);
  99
 100     // Extract type components
 101     let type_list = fcx.tcx.mk_type_list(types.into_iter().map(|t| t.0));
 102
 103     // The types in the generator interior contain lifetimes local to the generator itself,
 104     // which should not be exposed outside of the generator. Therefore, we replace these
 105     // lifetimes with existentially-bound lifetimes, which reflect the exact value of the
 106     // lifetimes not being known by users.
 107     //
 108     // These lifetimes are used in auto trait impl checking (for example,
 109     // if a Sync generator contains an &'α T, we need to check whether &'α T: Sync),
 110     // so knowledge of the exact relationships between them isn't particularly important.
 111
 112     debug!("Types in generator {:?}, span = {:?}", type_list, body.value.span);
 113
 114     // Replace all regions inside the generator interior with late bound regions
 115     // Note that each region slot in the types gets a new fresh late bound region,
 116     // which means that none of the regions inside relate to any other, even if
 117     // typeck had previously found constraints that would cause them to be related.
 118     let mut counter = 0;
 119     let type_list = fcx.tcx.fold_regions(&type_list, &mut false, |_, current_depth| {
 120         counter += 1;
 121         fcx.tcx.mk_region(ty::ReLateBound(current_depth, ty::BrAnon(counter)))
 122     });
 123
 124     let witness = fcx.tcx.mk_generator_witness(ty::Binder::bind(type_list));
 125
 126     debug!("Types in generator after region replacement {:?}, span = {:?}",
 127             witness, body.value.span);
 128
 129     // Unify the type variable inside the generator with the new witness
 130     match fcx.at(&fcx.misc(body.value.span), fcx.param_env).eq(interior, witness) {
 131         Ok(ok) => fcx.register_infer_ok_obligations(ok),
 132         _ => bug!(),
 133     }
 134 }
 135
 136 // This visitor has to have the same visit_expr calls as RegionResolutionVisitor in
 137 // librustc/middle/region.rs since `expr_count` is compared against the results
 138 // there.
 139 impl<'a, 'gcx, 'tcx> Visitor<'tcx> for InteriorVisitor<'a, 'gcx, 'tcx> {
 140     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
 141         NestedVisitorMap::None
 142     }
 143
 144     fn visit_pat(&mut self, pat: &'tcx Pat) {
 145         intravisit::walk_pat(self, pat);
 146
 147         self.expr_count += 1;
 148
 149         if let PatKind::Binding(..) = pat.node {
 150             let scope = self.region_scope_tree.var_scope(pat.hir_id.local_id);
 151             let ty = self.fcx.tables.borrow().pat_ty(pat);
 152             self.record(ty, Some(scope), None, pat.span);
 153         }
 154     }
 155
 156     fn visit_expr(&mut self, expr: &'tcx Expr) {
 157         intravisit::walk_expr(self, expr);
 158
 159         self.expr_count += 1;
 160
 161         let scope = self.region_scope_tree.temporary_scope(expr.hir_id.local_id);
 162
 163         // Record the unadjusted type
 164         let ty = self.fcx.tables.borrow().expr_ty(expr);
 165         self.record(ty, scope, Some(expr), expr.span);
 166
 167         // Also include the adjusted types, since these can result in MIR locals
 168         for adjustment in self.fcx.tables.borrow().expr_adjustments(expr) {
 169             self.record(adjustment.target, scope, Some(expr), expr.span);
 170         }
 171     }
 172 }