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