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