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