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::mir::interpret::ConstValue;
35 use crate::ty::{self, Ty, TyCtxt, TypeFoldable};
36 use crate::ty::fold::TypeFolder;
37 use crate::util::nodemap::FxHashMap;
39 use std::collections::hash_map::Entry;
42 use super::unify_key::ToType;
44 pub struct TypeFreshener<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
45 infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
46 ty_freshen_count: u32,
47 const_freshen_count: u32,
48 ty_freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>,
49 const_freshen_map: FxHashMap<ty::InferConst<'tcx>, &'tcx ty::Const<'tcx>>,
52 impl<'a, 'gcx, 'tcx> TypeFreshener<'a, 'gcx, 'tcx> {
53 pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>)
54 -> TypeFreshener<'a, 'gcx, 'tcx> {
58 const_freshen_count: 0,
59 ty_freshen_map: Default::default(),
60 const_freshen_map: Default::default(),
66 opt_ty: Option<Ty<'tcx>>,
71 F: FnOnce(u32) -> ty::InferTy,
73 if let Some(ty) = opt_ty {
74 return ty.fold_with(self);
77 match self.ty_freshen_map.entry(key) {
78 Entry::Occupied(entry) => *entry.get(),
79 Entry::Vacant(entry) => {
80 let index = self.ty_freshen_count;
81 self.ty_freshen_count += 1;
82 let t = self.infcx.tcx.mk_ty_infer(freshener(index));
91 opt_ct: Option<&'tcx ty::Const<'tcx>>,
92 key: ty::InferConst<'tcx>,
95 ) -> &'tcx ty::Const<'tcx>
97 F: FnOnce(u32) -> ty::InferConst<'tcx>,
99 if let Some(ct) = opt_ct {
100 return ct.fold_with(self);
103 match self.const_freshen_map.entry(key) {
104 Entry::Occupied(entry) => *entry.get(),
105 Entry::Vacant(entry) => {
106 let index = self.const_freshen_count;
107 self.const_freshen_count += 1;
108 let ct = self.infcx.tcx.mk_const_infer(freshener(index), ty);
116 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
117 fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
121 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
123 ty::ReLateBound(..) => {
124 // leave bound regions alone
129 ty::ReEarlyBound(..) |
133 ty::RePlaceholder(..) |
136 // replace all free regions with 'erased
137 self.tcx().lifetimes.re_erased
140 ty::ReClosureBound(..) => {
142 "encountered unexpected region: {:?}",
149 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
150 if !t.needs_infer() && !t.has_erasable_regions() &&
151 !(t.has_closure_types() && self.infcx.in_progress_tables.is_some()) {
155 let tcx = self.infcx.tcx;
158 ty::Infer(ty::TyVar(v)) => {
159 let opt_ty = self.infcx.type_variables.borrow_mut().probe(v).known();
166 ty::Infer(ty::IntVar(v)) => {
168 self.infcx.int_unification_table.borrow_mut()
170 .map(|v| v.to_type(tcx)),
175 ty::Infer(ty::FloatVar(v)) => {
177 self.infcx.float_unification_table.borrow_mut()
179 .map(|v| v.to_type(tcx)),
184 ty::Infer(ty::FreshTy(ct)) |
185 ty::Infer(ty::FreshIntTy(ct)) |
186 ty::Infer(ty::FreshFloatTy(ct)) => {
187 if ct >= self.ty_freshen_count {
188 bug!("Encountered a freshend type with id {} \
189 but our counter is only at {}",
191 self.ty_freshen_count);
215 ty::UnnormalizedProjection(..) |
219 ty::GeneratorWitness(..) |
221 t.super_fold_with(self)
224 ty::Placeholder(..) |
225 ty::Bound(..) => bug!("unexpected type {:?}", t),
229 fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
231 ConstValue::Infer(ty::InferConst::Var(v)) => {
232 let opt_ct = self.infcx.const_unification_table
237 return self.freshen_const(
239 ty::InferConst::Var(v),
240 ty::InferConst::Fresh,
244 ConstValue::Infer(ty::InferConst::Fresh(i)) => {
245 if i >= self.const_freshen_count {
247 "Encountered a freshend const with id {} \
248 but our counter is only at {}",
250 self.const_freshen_count,
256 ConstValue::Infer(ty::InferConst::Canonical(..)) |
257 ConstValue::Placeholder(_) => {
258 bug!("unexpected const {:?}", ct)
261 ConstValue::Param(_) |
262 ConstValue::Scalar(_) |
263 ConstValue::Slice { .. } |
264 ConstValue::ByRef(..) |
265 ConstValue::Unevaluated(..) => {}
268 ct.super_fold_with(self)