src/librustc_typeck/check/generator_interior.rs

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