| //! Freshening is the process of replacing unknown variables with fresh types. The idea is that |
| //! the type, after freshening, contains no inference variables but instead contains either a |
| //! value for each variable or fresh "arbitrary" types wherever a variable would have been. |
| //! |
| //! Freshening is used primarily to get a good type for inserting into a cache. The result |
| //! summarizes what the type inferencer knows "so far". The primary place it is used right now is |
| //! in the trait matching algorithm, which needs to be able to cache whether an `impl` self type |
| //! matches some other type X -- *without* affecting `X`. That means that if the type `X` is in |
| //! fact an unbound type variable, we want the match to be regarded as ambiguous, because depending |
| //! on what type that type variable is ultimately assigned, the match may or may not succeed. |
| //! |
| //! To handle closures, freshened types also have to contain the signature and kind of any |
| //! closure in the local inference context, as otherwise the cache key might be invalidated. |
| //! The way this is done is somewhat hacky - the closure signature is appended to the args, |
| //! as well as the closure kind "encoded" as a type. Also, special handling is needed when |
| //! the closure signature contains a reference to the original closure. |
| //! |
| //! Note that you should be careful not to allow the output of freshening to leak to the user in |
| //! error messages or in any other form. Freshening is only really useful as an internal detail. |
| //! |
| //! Because of the manipulation required to handle closures, doing arbitrary operations on |
| //! freshened types is not recommended. However, in addition to doing equality/hash |
| //! comparisons (for caching), it is possible to do a `ty::_match` operation between |
| //! two freshened types - this works even with the closure encoding. |
| //! |
| //! __An important detail concerning regions.__ The freshener also replaces *all* free regions with |
| //! 'erased. The reason behind this is that, in general, we do not take region relationships into |
| //! account when making type-overloaded decisions. This is important because of the design of the |
| //! region inferencer, which is not based on unification but rather on accumulating and then |
| //! solving a set of constraints. In contrast, the type inferencer assigns a value to each type |
| //! variable only once, and it does so as soon as it can, so it is reasonable to ask what the type |
| //! inferencer knows "so far". |
| |
| use std::collections::hash_map::Entry; |
| |
| use rustc_data_structures::fx::FxHashMap; |
| use rustc_middle::bug; |
| use rustc_middle::ty::{ |
| self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, |
| }; |
| |
| use super::InferCtxt; |
| |
| pub struct TypeFreshener<'a, 'tcx> { |
| infcx: &'a InferCtxt<'tcx>, |
| ty_freshen_count: u32, |
| const_freshen_count: u32, |
| ty_freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>, |
| const_freshen_map: FxHashMap<ty::InferConst, ty::Const<'tcx>>, |
| } |
| |
| impl<'a, 'tcx> TypeFreshener<'a, 'tcx> { |
| pub fn new(infcx: &'a InferCtxt<'tcx>) -> TypeFreshener<'a, 'tcx> { |
| TypeFreshener { |
| infcx, |
| ty_freshen_count: 0, |
| const_freshen_count: 0, |
| ty_freshen_map: Default::default(), |
| const_freshen_map: Default::default(), |
| } |
| } |
| |
| fn freshen_ty<F>(&mut self, input: ty::InferTy, mk_fresh: F) -> Ty<'tcx> |
| where |
| F: FnOnce(u32) -> Ty<'tcx>, |
| { |
| match self.ty_freshen_map.entry(input) { |
| Entry::Occupied(entry) => *entry.get(), |
| Entry::Vacant(entry) => { |
| let index = self.ty_freshen_count; |
| self.ty_freshen_count += 1; |
| let t = mk_fresh(index); |
| entry.insert(t); |
| t |
| } |
| } |
| } |
| |
| fn freshen_const<F>(&mut self, input: ty::InferConst, freshener: F) -> ty::Const<'tcx> |
| where |
| F: FnOnce(u32) -> ty::InferConst, |
| { |
| match self.const_freshen_map.entry(input) { |
| Entry::Occupied(entry) => *entry.get(), |
| Entry::Vacant(entry) => { |
| let index = self.const_freshen_count; |
| self.const_freshen_count += 1; |
| let ct = ty::Const::new_infer(self.infcx.tcx, freshener(index)); |
| entry.insert(ct); |
| ct |
| } |
| } |
| } |
| } |
| |
| impl<'a, 'tcx> TypeFolder<TyCtxt<'tcx>> for TypeFreshener<'a, 'tcx> { |
| fn cx(&self) -> TyCtxt<'tcx> { |
| self.infcx.tcx |
| } |
| |
| fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
| match r.kind() { |
| // Leave bound regions alone, since they affect selection via the leak check. |
| ty::ReBound(..) => r, |
| // Leave error regions alone, since they affect selection b/c of incompleteness. |
| ty::ReError(_) => r, |
| |
| ty::ReEarlyParam(..) |
| | ty::ReLateParam(_) |
| | ty::ReVar(_) |
| | ty::RePlaceholder(..) |
| | ty::ReStatic |
| | ty::ReErased => self.cx().lifetimes.re_erased, |
| } |
| } |
| |
| #[inline] |
| fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { |
| if !t.has_infer() && !t.has_erasable_regions() { |
| t |
| } else { |
| match *t.kind() { |
| ty::Infer(v) => self.fold_infer_ty(v), |
| |
| // This code is hot enough that a non-debug assertion here makes a noticeable |
| // difference on benchmarks like `wg-grammar`. |
| #[cfg(debug_assertions)] |
| ty::Placeholder(..) | ty::Bound(..) => bug!("unexpected type {:?}", t), |
| |
| _ => t.super_fold_with(self), |
| } |
| } |
| } |
| |
| fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { |
| match ct.kind() { |
| ty::ConstKind::Infer(ty::InferConst::Var(v)) => { |
| let mut inner = self.infcx.inner.borrow_mut(); |
| match inner.const_unification_table().probe_value(v).known() { |
| Some(const_) => { |
| drop(inner); |
| const_.fold_with(self) |
| } |
| None => { |
| let input = |
| ty::InferConst::Var(inner.const_unification_table().find(v).vid); |
| self.freshen_const(input, ty::InferConst::Fresh) |
| } |
| } |
| } |
| ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => { |
| bug!("trying to freshen already-freshened const {ct:?}"); |
| } |
| |
| ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => { |
| bug!("unexpected const {ct:?}") |
| } |
| |
| ty::ConstKind::Param(_) |
| | ty::ConstKind::Value(_) |
| | ty::ConstKind::Alias(..) |
| | ty::ConstKind::Expr(..) |
| | ty::ConstKind::Error(_) => ct.super_fold_with(self), |
| } |
| } |
| } |
| |
| impl<'a, 'tcx> TypeFreshener<'a, 'tcx> { |
| // This is separate from `fold_ty` to keep that method small and inlinable. |
| #[inline(never)] |
| fn fold_infer_ty(&mut self, ty: ty::InferTy) -> Ty<'tcx> { |
| match ty { |
| ty::TyVar(v) => { |
| let mut inner = self.infcx.inner.borrow_mut(); |
| match inner.type_variables().probe(v).known() { |
| Some(ty) => { |
| drop(inner); |
| ty.fold_with(self) |
| } |
| None => { |
| let input = ty::TyVar(inner.type_variables().root_var(v)); |
| self.freshen_ty(input, |n| Ty::new_fresh(self.infcx.tcx, n)) |
| } |
| } |
| } |
| |
| ty::IntVar(v) => { |
| let mut inner = self.infcx.inner.borrow_mut(); |
| let value = inner.int_unification_table().probe_value(v); |
| match value { |
| ty::IntVarValue::IntType(ty) => Ty::new_int(self.infcx.tcx, ty), |
| ty::IntVarValue::UintType(ty) => Ty::new_uint(self.infcx.tcx, ty), |
| ty::IntVarValue::Unknown => { |
| let input = ty::IntVar(inner.int_unification_table().find(v)); |
| self.freshen_ty(input, |n| Ty::new_fresh_int(self.infcx.tcx, n)) |
| } |
| } |
| } |
| |
| ty::FloatVar(v) => { |
| let mut inner = self.infcx.inner.borrow_mut(); |
| let value = inner.float_unification_table().probe_value(v); |
| match value { |
| ty::FloatVarValue::Known(ty) => Ty::new_float(self.infcx.tcx, ty), |
| ty::FloatVarValue::Unknown => { |
| let input = ty::FloatVar(inner.float_unification_table().find(v)); |
| self.freshen_ty(input, |n| Ty::new_fresh_float(self.infcx.tcx, n)) |
| } |
| } |
| } |
| |
| ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_) => { |
| bug!("trying to freshen already-freshened type {ty:?}"); |
| } |
| } |
| } |
| } |
