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