src/librustc/infer/freshen.rs

   1 //! Freshening is the process of replacing unknown variables with fresh types. The idea is that
   2 //! the type, after freshening, contains no inference variables but instead contains either a
   3 //! value for each variable or fresh "arbitrary" types wherever a variable would have been.
   4 //!
   5 //! Freshening is used primarily to get a good type for inserting into a cache. The result
   6 //! summarizes what the type inferencer knows "so far". The primary place it is used right now is
   7 //! in the trait matching algorithm, which needs to be able to cache whether an `impl` self type
   8 //! matches some other type X -- *without* affecting `X`. That means if that if the type `X` is in
   9 //! fact an unbound type variable, we want the match to be regarded as ambiguous, because depending
  10 //! on what type that type variable is ultimately assigned, the match may or may not succeed.
  11 //!
  12 //! To handle closures, freshened types also have to contain the signature and kind of any
  13 //! closure in the local inference context, as otherwise the cache key might be invalidated.
  14 //! The way this is done is somewhat hacky - the closure signature is appended to the substs,
  15 //! as well as the closure kind "encoded" as a type. Also, special handling is needed when
  16 //! the closure signature contains a reference to the original closure.
  17 //!
  18 //! Note that you should be careful not to allow the output of freshening to leak to the user in
  19 //! error messages or in any other form. Freshening is only really useful as an internal detail.
  20 //!
  21 //! Because of the manipulation required to handle closures, doing arbitrary operations on
  22 //! freshened types is not recommended. However, in addition to doing equality/hash
  23 //! comparisons (for caching), it is possible to do a `ty::_match` operation between
  24 //! 2 freshened types - this works even with the closure encoding.
  25 //!
  26 //! __An important detail concerning regions.__ The freshener also replaces *all* free regions with
  27 //! 'erased. The reason behind this is that, in general, we do not take region relationships into
  28 //! account when making type-overloaded decisions. This is important because of the design of the
  29 //! region inferencer, which is not based on unification but rather on accumulating and then
  30 //! solving a set of constraints. In contrast, the type inferencer assigns a value to each type
  31 //! variable only once, and it does so as soon as it can, so it is reasonable to ask what the type
  32 //! inferencer knows "so far".
  33
  34 use crate::ty::{self, Ty, TyCtxt, TypeFoldable};
  35 use crate::ty::fold::TypeFolder;
  36 use crate::util::nodemap::FxHashMap;
  37
  38 use std::collections::hash_map::Entry;
  39
  40 use super::InferCtxt;
  41 use super::unify_key::ToType;
  42
  43 pub struct TypeFreshener<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  44     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
  45     freshen_count: u32,
  46     freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>,
  47 }
  48
  49 impl<'a, 'gcx, 'tcx> TypeFreshener<'a, 'gcx, 'tcx> {
  50     pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>)
  51                -> TypeFreshener<'a, 'gcx, 'tcx> {
  52         TypeFreshener {
  53             infcx,
  54             freshen_count: 0,
  55             freshen_map: Default::default(),
  56         }
  57     }
  58
  59     fn freshen<F>(&mut self,
  60                   opt_ty: Option<Ty<'tcx>>,
  61                   key: ty::InferTy,
  62                   freshener: F)
  63                   -> Ty<'tcx> where
  64         F: FnOnce(u32) -> ty::InferTy,
  65     {
  66         if let Some(ty) = opt_ty {
  67             return ty.fold_with(self);
  68         }
  69
  70         match self.freshen_map.entry(key) {
  71             Entry::Occupied(entry) => *entry.get(),
  72             Entry::Vacant(entry) => {
  73                 let index = self.freshen_count;
  74                 self.freshen_count += 1;
  75                 let t = self.infcx.tcx.mk_infer(freshener(index));
  76                 entry.insert(t);
  77                 t
  78             }
  79         }
  80     }
  81 }
  82
  83 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
  84     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
  85         self.infcx.tcx
  86     }
  87
  88     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
  89         match *r {
  90             ty::ReLateBound(..) => {
  91                 // leave bound regions alone
  92                 r
  93             }
  94
  95             ty::ReStatic |
  96             ty::ReEarlyBound(..) |
  97             ty::ReFree(_) |
  98             ty::ReScope(_) |
  99             ty::ReVar(_) |
 100             ty::RePlaceholder(..) |
 101             ty::ReEmpty |
 102             ty::ReErased => {
 103                 // replace all free regions with 'erased
 104                 self.tcx().lifetimes.re_erased
 105             }
 106
 107             ty::ReClosureBound(..) => {
 108                 bug!(
 109                     "encountered unexpected region: {:?}",
 110                     r,
 111                 );
 112             }
 113         }
 114     }
 115
 116     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 117         if !t.needs_infer() && !t.has_erasable_regions() &&
 118             !(t.has_closure_types() && self.infcx.in_progress_tables.is_some()) {
 119             return t;
 120         }
 121
 122         let tcx = self.infcx.tcx;
 123
 124         match t.sty {
 125             ty::Infer(ty::TyVar(v)) => {
 126                 let opt_ty = self.infcx.type_variables.borrow_mut().probe(v).known();
 127                 self.freshen(
 128                     opt_ty,
 129                     ty::TyVar(v),
 130                     ty::FreshTy)
 131             }
 132
 133             ty::Infer(ty::IntVar(v)) => {
 134                 self.freshen(
 135                     self.infcx.int_unification_table.borrow_mut()
 136                                                     .probe_value(v)
 137                                                     .map(|v| v.to_type(tcx)),
 138                     ty::IntVar(v),
 139                     ty::FreshIntTy)
 140             }
 141
 142             ty::Infer(ty::FloatVar(v)) => {
 143                 self.freshen(
 144                     self.infcx.float_unification_table.borrow_mut()
 145                                                       .probe_value(v)
 146                                                       .map(|v| v.to_type(tcx)),
 147                     ty::FloatVar(v),
 148                     ty::FreshFloatTy)
 149             }
 150
 151             ty::Infer(ty::FreshTy(c)) |
 152             ty::Infer(ty::FreshIntTy(c)) |
 153             ty::Infer(ty::FreshFloatTy(c)) => {
 154                 if c >= self.freshen_count {
 155                     bug!("Encountered a freshend type with id {} \
 156                           but our counter is only at {}",
 157                          c,
 158                          self.freshen_count);
 159                 }
 160                 t
 161             }
 162
 163             ty::Generator(..) |
 164             ty::Bool |
 165             ty::Char |
 166             ty::Int(..) |
 167             ty::Uint(..) |
 168             ty::Float(..) |
 169             ty::Adt(..) |
 170             ty::Str |
 171             ty::Error |
 172             ty::Array(..) |
 173             ty::Slice(..) |
 174             ty::RawPtr(..) |
 175             ty::Ref(..) |
 176             ty::FnDef(..) |
 177             ty::FnPtr(_) |
 178             ty::Dynamic(..) |
 179             ty::Never |
 180             ty::Tuple(..) |
 181             ty::Projection(..) |
 182             ty::UnnormalizedProjection(..) |
 183             ty::Foreign(..) |
 184             ty::Param(..) |
 185             ty::Closure(..) |
 186             ty::GeneratorWitness(..) |
 187             ty::Opaque(..) => {
 188                 t.super_fold_with(self)
 189             }
 190
 191             ty::Placeholder(..) |
 192             ty::Bound(..) => bug!("unexpected type {:?}", t),
 193         }
 194     }
 195 }