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.
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.
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.
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.
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.
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".
34 use crate::ty::{self, Ty, TyCtxt, TypeFoldable};
35 use crate::ty::fold::TypeFolder;
36 use crate::util::nodemap::FxHashMap;
38 use std::collections::hash_map::Entry;
41 use super::unify_key::ToType;
43 pub struct TypeFreshener<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
44 infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
46 freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>,
49 impl<'a, 'gcx, 'tcx> TypeFreshener<'a, 'gcx, 'tcx> {
50 pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>)
51 -> TypeFreshener<'a, 'gcx, 'tcx> {
55 freshen_map: Default::default(),
59 fn freshen<F>(&mut self,
60 opt_ty: Option<Ty<'tcx>>,
64 F: FnOnce(u32) -> ty::InferTy,
66 if let Some(ty) = opt_ty {
67 return ty.fold_with(self);
70 match self.freshen_map.entry(key) {
71 Entry::Occupied(entry) => *entry.get(),
72 Entry::Vacant(entry) => {
73 let index = self.freshen_count;
74 self.freshen_count += 1;
75 let t = self.infcx.tcx.mk_ty_infer(freshener(index));
83 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
84 fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
88 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
90 ty::ReLateBound(..) => {
91 // leave bound regions alone
96 ty::ReEarlyBound(..) |
100 ty::RePlaceholder(..) |
103 // replace all free regions with 'erased
104 self.tcx().lifetimes.re_erased
107 ty::ReClosureBound(..) => {
109 "encountered unexpected region: {:?}",
116 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
117 if !t.needs_infer() && !t.has_erasable_regions() &&
118 !(t.has_closure_types() && self.infcx.in_progress_tables.is_some()) {
122 let tcx = self.infcx.tcx;
125 ty::Infer(ty::TyVar(v)) => {
126 let opt_ty = self.infcx.type_variables.borrow_mut().probe(v).known();
133 ty::Infer(ty::IntVar(v)) => {
135 self.infcx.int_unification_table.borrow_mut()
137 .map(|v| v.to_type(tcx)),
142 ty::Infer(ty::FloatVar(v)) => {
144 self.infcx.float_unification_table.borrow_mut()
146 .map(|v| v.to_type(tcx)),
151 ty::Infer(ty::FreshTy(c)) |
152 ty::Infer(ty::FreshIntTy(c)) |
153 ty::Infer(ty::FreshFloatTy(c)) => {
154 if c >= self.freshen_count {
155 bug!("Encountered a freshend type with id {} \
156 but our counter is only at {}",
182 ty::UnnormalizedProjection(..) |
186 ty::GeneratorWitness(..) |
188 t.super_fold_with(self)
191 ty::Placeholder(..) |
192 ty::Bound(..) => bug!("unexpected type {:?}", t),
196 fn fold_const(&mut self, ct: &'tcx ty::LazyConst<'tcx>) -> &'tcx ty::LazyConst<'tcx> {
197 ct // FIXME(const_generics)