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, TypeVisitableExt};
  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 }
  47
  48 impl<'a, 'tcx> TypeFreshener<'a, 'tcx> {
  49     pub fn new(infcx: &'a InferCtxt<'tcx>) -> TypeFreshener<'a, 'tcx> {
  50         TypeFreshener {
  51             infcx,
  52             ty_freshen_count: 0,
  53             const_freshen_count: 0,
  54             ty_freshen_map: Default::default(),
  55             const_freshen_map: Default::default(),
  56         }
  57     }
  58
  59     fn freshen_ty<F>(&mut self, opt_ty: Option<Ty<'tcx>>, key: ty::InferTy, mk_fresh: F) -> Ty<'tcx>
  60     where
  61         F: FnOnce(u32) -> Ty<'tcx>,
  62     {
  63         if let Some(ty) = opt_ty {
  64             return ty.fold_with(self);
  65         }
  66
  67         match self.ty_freshen_map.entry(key) {
  68             Entry::Occupied(entry) => *entry.get(),
  69             Entry::Vacant(entry) => {
  70                 let index = self.ty_freshen_count;
  71                 self.ty_freshen_count += 1;
  72                 let t = mk_fresh(index);
  73                 entry.insert(t);
  74                 t
  75             }
  76         }
  77     }
  78
  79     fn freshen_const<F>(
  80         &mut self,
  81         opt_ct: Option<ty::Const<'tcx>>,
  82         key: ty::InferConst<'tcx>,
  83         freshener: F,
  84         ty: Ty<'tcx>,
  85     ) -> ty::Const<'tcx>
  86     where
  87         F: FnOnce(u32) -> ty::InferConst<'tcx>,
  88     {
  89         if let Some(ct) = opt_ct {
  90             return ct.fold_with(self);
  91         }
  92
  93         match self.const_freshen_map.entry(key) {
  94             Entry::Occupied(entry) => *entry.get(),
  95             Entry::Vacant(entry) => {
  96                 let index = self.const_freshen_count;
  97                 self.const_freshen_count += 1;
  98                 let ct = self.infcx.tcx.mk_const(freshener(index), ty);
  99                 entry.insert(ct);
 100                 ct
 101             }
 102         }
 103     }
 104 }
 105
 106 impl<'a, 'tcx> TypeFolder<TyCtxt<'tcx>> for TypeFreshener<'a, 'tcx> {
 107     fn interner(&self) -> TyCtxt<'tcx> {
 108         self.infcx.tcx
 109     }
 110
 111     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 112         match *r {
 113             ty::ReLateBound(..) => {
 114                 // leave bound regions alone
 115                 r
 116             }
 117
 118             ty::ReEarlyBound(..)
 119             | ty::ReFree(_)
 120             | ty::ReVar(_)
 121             | ty::RePlaceholder(..)
 122             | ty::ReStatic
 123             | ty::ReError(_)
 124             | ty::ReErased => self.interner().lifetimes.re_erased,
 125         }
 126     }
 127
 128     #[inline]
 129     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 130         if !t.needs_infer() && !t.has_erasable_regions() {
 131             t
 132         } else {
 133             match *t.kind() {
 134                 ty::Infer(v) => self.fold_infer_ty(v).unwrap_or(t),
 135
 136                 // This code is hot enough that a non-debug assertion here makes a noticeable
 137                 // difference on benchmarks like `wg-grammar`.
 138                 #[cfg(debug_assertions)]
 139                 ty::Placeholder(..) | ty::Bound(..) => bug!("unexpected type {:?}", t),
 140
 141                 _ => t.super_fold_with(self),
 142             }
 143         }
 144     }
 145
 146     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 147         match ct.kind() {
 148             ty::ConstKind::Infer(ty::InferConst::Var(v)) => {
 149                 let opt_ct = self
 150                     .infcx
 151                     .inner
 152                     .borrow_mut()
 153                     .const_unification_table()
 154                     .probe_value(v)
 155                     .val
 156                     .known();
 157                 self.freshen_const(opt_ct, ty::InferConst::Var(v), ty::InferConst::Fresh, ct.ty())
 158             }
 159             ty::ConstKind::Infer(ty::InferConst::Fresh(i)) => {
 160                 if i >= self.const_freshen_count {
 161                     bug!(
 162                         "Encountered a freshend const with id {} \
 163                             but our counter is only at {}",
 164                         i,
 165                         self.const_freshen_count,
 166                     );
 167                 }
 168                 ct
 169             }
 170
 171             ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => {
 172                 bug!("unexpected const {:?}", ct)
 173             }
 174
 175             ty::ConstKind::Param(_)
 176             | ty::ConstKind::Value(_)
 177             | ty::ConstKind::Unevaluated(..)
 178             | ty::ConstKind::Expr(..)
 179             | ty::ConstKind::Error(_) => ct.super_fold_with(self),
 180         }
 181     }
 182 }
 183
 184 impl<'a, 'tcx> TypeFreshener<'a, 'tcx> {
 185     // This is separate from `fold_ty` to keep that method small and inlinable.
 186     #[inline(never)]
 187     fn fold_infer_ty(&mut self, v: ty::InferTy) -> Option<Ty<'tcx>> {
 188         match v {
 189             ty::TyVar(v) => {
 190                 let opt_ty = self.infcx.inner.borrow_mut().type_variables().probe(v).known();
 191                 Some(self.freshen_ty(opt_ty, ty::TyVar(v), |n| self.infcx.tcx.mk_fresh_ty(n)))
 192             }
 193
 194             ty::IntVar(v) => Some(
 195                 self.freshen_ty(
 196                     self.infcx
 197                         .inner
 198                         .borrow_mut()
 199                         .int_unification_table()
 200                         .probe_value(v)
 201                         .map(|v| v.to_type(self.infcx.tcx)),
 202                     ty::IntVar(v),
 203                     |n| self.infcx.tcx.mk_fresh_int_ty(n),
 204                 ),
 205             ),
 206
 207             ty::FloatVar(v) => Some(
 208                 self.freshen_ty(
 209                     self.infcx
 210                         .inner
 211                         .borrow_mut()
 212                         .float_unification_table()
 213                         .probe_value(v)
 214                         .map(|v| v.to_type(self.infcx.tcx)),
 215                     ty::FloatVar(v),
 216                     |n| self.infcx.tcx.mk_fresh_float_ty(n),
 217                 ),
 218             ),
 219
 220             ty::FreshTy(ct) | ty::FreshIntTy(ct) | ty::FreshFloatTy(ct) => {
 221                 if ct >= self.ty_freshen_count {
 222                     bug!(
 223                         "Encountered a freshend type with id {} \
 224                           but our counter is only at {}",
 225                         ct,
 226                         self.ty_freshen_count
 227                     );
 228                 }
 229                 None
 230             }
 231         }
 232     }
 233 }