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::mir::interpret::ConstValue;
  35 use crate::ty::{self, Ty, TyCtxt, TypeFoldable};
  36 use crate::ty::fold::TypeFolder;
  37 use crate::util::nodemap::FxHashMap;
  38
  39 use std::collections::hash_map::Entry;
  40
  41 use super::InferCtxt;
  42 use super::unify_key::ToType;
  43
  44 pub struct TypeFreshener<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
  45     infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
  46     ty_freshen_count: u32,
  47     const_freshen_count: u32,
  48     ty_freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>,
  49     const_freshen_map: FxHashMap<ty::InferConst<'tcx>, &'tcx ty::Const<'tcx>>,
  50 }
  51
  52 impl<'a, 'gcx, 'tcx> TypeFreshener<'a, 'gcx, 'tcx> {
  53     pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>)
  54                -> TypeFreshener<'a, 'gcx, 'tcx> {
  55         TypeFreshener {
  56             infcx,
  57             ty_freshen_count: 0,
  58             const_freshen_count: 0,
  59             ty_freshen_map: Default::default(),
  60             const_freshen_map: Default::default(),
  61         }
  62     }
  63
  64     fn freshen_ty<F>(
  65         &mut self,
  66         opt_ty: Option<Ty<'tcx>>,
  67         key: ty::InferTy,
  68         freshener: F,
  69     ) -> Ty<'tcx>
  70     where
  71         F: FnOnce(u32) -> ty::InferTy,
  72     {
  73         if let Some(ty) = opt_ty {
  74             return ty.fold_with(self);
  75         }
  76
  77         match self.ty_freshen_map.entry(key) {
  78             Entry::Occupied(entry) => *entry.get(),
  79             Entry::Vacant(entry) => {
  80                 let index = self.ty_freshen_count;
  81                 self.ty_freshen_count += 1;
  82                 let t = self.infcx.tcx.mk_ty_infer(freshener(index));
  83                 entry.insert(t);
  84                 t
  85             }
  86         }
  87     }
  88
  89     fn freshen_const<F>(
  90         &mut self,
  91         opt_ct: Option<&'tcx ty::Const<'tcx>>,
  92         key: ty::InferConst<'tcx>,
  93         freshener: F,
  94         ty: Ty<'tcx>,
  95     ) -> &'tcx ty::Const<'tcx>
  96     where
  97         F: FnOnce(u32) -> ty::InferConst<'tcx>,
  98     {
  99         if let Some(ct) = opt_ct {
 100             return ct.fold_with(self);
 101         }
 102
 103         match self.const_freshen_map.entry(key) {
 104             Entry::Occupied(entry) => *entry.get(),
 105             Entry::Vacant(entry) => {
 106                 let index = self.const_freshen_count;
 107                 self.const_freshen_count += 1;
 108                 let ct = self.infcx.tcx.mk_const_infer(freshener(index), ty);
 109                 entry.insert(ct);
 110                 ct
 111             }
 112         }
 113     }
 114 }
 115
 116 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
 117     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
 118         self.infcx.tcx
 119     }
 120
 121     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 122         match *r {
 123             ty::ReLateBound(..) => {
 124                 // leave bound regions alone
 125                 r
 126             }
 127
 128             ty::ReStatic |
 129             ty::ReEarlyBound(..) |
 130             ty::ReFree(_) |
 131             ty::ReScope(_) |
 132             ty::ReVar(_) |
 133             ty::RePlaceholder(..) |
 134             ty::ReEmpty |
 135             ty::ReErased => {
 136                 // replace all free regions with 'erased
 137                 self.tcx().lifetimes.re_erased
 138             }
 139
 140             ty::ReClosureBound(..) => {
 141                 bug!(
 142                     "encountered unexpected region: {:?}",
 143                     r,
 144                 );
 145             }
 146         }
 147     }
 148
 149     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 150         if !t.needs_infer() && !t.has_erasable_regions() &&
 151             !(t.has_closure_types() && self.infcx.in_progress_tables.is_some()) {
 152             return t;
 153         }
 154
 155         let tcx = self.infcx.tcx;
 156
 157         match t.sty {
 158             ty::Infer(ty::TyVar(v)) => {
 159                 let opt_ty = self.infcx.type_variables.borrow_mut().probe(v).known();
 160                 self.freshen_ty(
 161                     opt_ty,
 162                     ty::TyVar(v),
 163                     ty::FreshTy)
 164             }
 165
 166             ty::Infer(ty::IntVar(v)) => {
 167                 self.freshen_ty(
 168                     self.infcx.int_unification_table.borrow_mut()
 169                                                     .probe_value(v)
 170                                                     .map(|v| v.to_type(tcx)),
 171                     ty::IntVar(v),
 172                     ty::FreshIntTy)
 173             }
 174
 175             ty::Infer(ty::FloatVar(v)) => {
 176                 self.freshen_ty(
 177                     self.infcx.float_unification_table.borrow_mut()
 178                                                       .probe_value(v)
 179                                                       .map(|v| v.to_type(tcx)),
 180                     ty::FloatVar(v),
 181                     ty::FreshFloatTy)
 182             }
 183
 184             ty::Infer(ty::FreshTy(ct)) |
 185             ty::Infer(ty::FreshIntTy(ct)) |
 186             ty::Infer(ty::FreshFloatTy(ct)) => {
 187                 if ct >= self.ty_freshen_count {
 188                     bug!("Encountered a freshend type with id {} \
 189                           but our counter is only at {}",
 190                          ct,
 191                          self.ty_freshen_count);
 192                 }
 193                 t
 194             }
 195
 196             ty::Generator(..) |
 197             ty::Bool |
 198             ty::Char |
 199             ty::Int(..) |
 200             ty::Uint(..) |
 201             ty::Float(..) |
 202             ty::Adt(..) |
 203             ty::Str |
 204             ty::Error |
 205             ty::Array(..) |
 206             ty::Slice(..) |
 207             ty::RawPtr(..) |
 208             ty::Ref(..) |
 209             ty::FnDef(..) |
 210             ty::FnPtr(_) |
 211             ty::Dynamic(..) |
 212             ty::Never |
 213             ty::Tuple(..) |
 214             ty::Projection(..) |
 215             ty::UnnormalizedProjection(..) |
 216             ty::Foreign(..) |
 217             ty::Param(..) |
 218             ty::Closure(..) |
 219             ty::GeneratorWitness(..) |
 220             ty::Opaque(..) => {
 221                 t.super_fold_with(self)
 222             }
 223
 224             ty::Placeholder(..) |
 225             ty::Bound(..) => bug!("unexpected type {:?}", t),
 226         }
 227     }
 228
 229     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 230         match ct.val {
 231             ConstValue::Infer(ty::InferConst::Var(v)) => {
 232                 let opt_ct = self.infcx.const_unification_table
 233                     .borrow_mut()
 234                     .probe_value(v)
 235                     .val
 236                     .known();
 237                 return self.freshen_const(
 238                     opt_ct,
 239                     ty::InferConst::Var(v),
 240                     ty::InferConst::Fresh,
 241                     ct.ty,
 242                 );
 243             }
 244             ConstValue::Infer(ty::InferConst::Fresh(i)) => {
 245                 if i >= self.const_freshen_count {
 246                     bug!(
 247                         "Encountered a freshend const with id {} \
 248                             but our counter is only at {}",
 249                         i,
 250                         self.const_freshen_count,
 251                     );
 252                 }
 253                 return ct;
 254             }
 255
 256             ConstValue::Infer(ty::InferConst::Canonical(..)) |
 257             ConstValue::Placeholder(_) => {
 258                 bug!("unexpected const {:?}", ct)
 259             }
 260
 261             ConstValue::Param(_) |
 262             ConstValue::Scalar(_) |
 263             ConstValue::Slice { .. } |
 264             ConstValue::ByRef(..) |
 265             ConstValue::Unevaluated(..) => {}
 266         }
 267
 268         ct.super_fold_with(self)
 269     }
 270 }