]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 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. | |
11 | //! | |
3b2f2976 XL |
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. | |
17 | //! | |
1a4d82fc JJ |
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 | //! | |
3b2f2976 XL |
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. | |
25 | //! | |
26 | //! __An important detail concerning regions.__ The freshener also replaces *all* free regions with | |
3157f602 | 27 | //! 'erased. The reason behind this is that, in general, we do not take region relationships into |
1a4d82fc JJ |
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". | |
5e7ed085 FG |
33 | use super::InferCtxt; |
34 | use rustc_data_structures::fx::FxHashMap; | |
35 | use rustc_middle::infer::unify_key::ToType; | |
ba9703b0 | 36 | use rustc_middle::ty::fold::TypeFolder; |
9ffffee4 | 37 | use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable, TypeSuperFoldable, TypeVisitableExt}; |
9e0c209e | 38 | use std::collections::hash_map::Entry; |
1a4d82fc | 39 | |
dc9dc135 | 40 | pub struct TypeFreshener<'a, 'tcx> { |
2b03887a | 41 | infcx: &'a InferCtxt<'tcx>, |
48663c56 XL |
42 | ty_freshen_count: u32, |
43 | const_freshen_count: u32, | |
44 | ty_freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>, | |
5099ac24 | 45 | const_freshen_map: FxHashMap<ty::InferConst<'tcx>, ty::Const<'tcx>>, |
1a4d82fc JJ |
46 | } |
47 | ||
dc9dc135 | 48 | impl<'a, 'tcx> TypeFreshener<'a, 'tcx> { |
353b0b11 | 49 | pub fn new(infcx: &'a InferCtxt<'tcx>) -> TypeFreshener<'a, 'tcx> { |
1a4d82fc | 50 | TypeFreshener { |
041b39d2 | 51 | infcx, |
48663c56 XL |
52 | ty_freshen_count: 0, |
53 | const_freshen_count: 0, | |
54 | ty_freshen_map: Default::default(), | |
55 | const_freshen_map: Default::default(), | |
1a4d82fc JJ |
56 | } |
57 | } | |
58 | ||
9ffffee4 | 59 | fn freshen_ty<F>(&mut self, opt_ty: Option<Ty<'tcx>>, key: ty::InferTy, mk_fresh: F) -> Ty<'tcx> |
48663c56 | 60 | where |
9ffffee4 | 61 | F: FnOnce(u32) -> Ty<'tcx>, |
1a4d82fc | 62 | { |
c30ab7b3 SL |
63 | if let Some(ty) = opt_ty { |
64 | return ty.fold_with(self); | |
1a4d82fc JJ |
65 | } |
66 | ||
48663c56 | 67 | match self.ty_freshen_map.entry(key) { |
1a4d82fc JJ |
68 | Entry::Occupied(entry) => *entry.get(), |
69 | Entry::Vacant(entry) => { | |
48663c56 XL |
70 | let index = self.ty_freshen_count; |
71 | self.ty_freshen_count += 1; | |
9ffffee4 | 72 | let t = mk_fresh(index); |
1a4d82fc JJ |
73 | entry.insert(t); |
74 | t | |
75 | } | |
76 | } | |
77 | } | |
48663c56 XL |
78 | |
79 | fn freshen_const<F>( | |
80 | &mut self, | |
5099ac24 | 81 | opt_ct: Option<ty::Const<'tcx>>, |
48663c56 XL |
82 | key: ty::InferConst<'tcx>, |
83 | freshener: F, | |
84 | ty: Ty<'tcx>, | |
5099ac24 | 85 | ) -> ty::Const<'tcx> |
48663c56 XL |
86 | where |
87 | F: FnOnce(u32) -> ty::InferConst<'tcx>, | |
88 | { | |
89 | if let Some(ct) = opt_ct { | |
90 | return ct.fold_with(self); | |
91 | } | |
92 | ||
93 | match self.const_freshen_map.entry(key) { | |
94 | Entry::Occupied(entry) => *entry.get(), | |
95 | Entry::Vacant(entry) => { | |
96 | let index = self.const_freshen_count; | |
97 | self.const_freshen_count += 1; | |
487cf647 | 98 | let ct = self.infcx.tcx.mk_const(freshener(index), ty); |
48663c56 XL |
99 | entry.insert(ct); |
100 | ct | |
101 | } | |
102 | } | |
103 | } | |
1a4d82fc JJ |
104 | } |
105 | ||
9ffffee4 FG |
106 | impl<'a, 'tcx> TypeFolder<TyCtxt<'tcx>> for TypeFreshener<'a, 'tcx> { |
107 | fn interner(&self) -> TyCtxt<'tcx> { | |
1a4d82fc JJ |
108 | self.infcx.tcx |
109 | } | |
110 | ||
7cac9316 | 111 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9e0c209e | 112 | match *r { |
1a4d82fc JJ |
113 | ty::ReLateBound(..) => { |
114 | // leave bound regions alone | |
115 | r | |
116 | } | |
117 | ||
136023e0 | 118 | ty::ReEarlyBound(..) |
dfeec247 | 119 | | ty::ReFree(_) |
dfeec247 XL |
120 | | ty::ReVar(_) |
121 | | ty::RePlaceholder(..) | |
353b0b11 | 122 | | ty::ReStatic |
9ffffee4 | 123 | | ty::ReError(_) |
353b0b11 | 124 | | ty::ReErased => self.interner().lifetimes.re_erased, |
1a4d82fc JJ |
125 | } |
126 | } | |
127 | ||
9ffffee4 | 128 | #[inline] |
1a4d82fc | 129 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { |
49aad941 | 130 | if !t.has_infer() && !t.has_erasable_regions() { |
9ffffee4 FG |
131 | t |
132 | } else { | |
133 | match *t.kind() { | |
134 | ty::Infer(v) => self.fold_infer_ty(v).unwrap_or(t), | |
62682a34 | 135 | |
9ffffee4 FG |
136 | // This code is hot enough that a non-debug assertion here makes a noticeable |
137 | // difference on benchmarks like `wg-grammar`. | |
138 | #[cfg(debug_assertions)] | |
139 | ty::Placeholder(..) | ty::Bound(..) => bug!("unexpected type {:?}", t), | |
c34b1796 | 140 | |
9ffffee4 | 141 | _ => t.super_fold_with(self), |
1a4d82fc | 142 | } |
1a4d82fc JJ |
143 | } |
144 | } | |
48663c56 | 145 | |
5099ac24 | 146 | fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { |
923072b8 | 147 | match ct.kind() { |
60c5eb7d | 148 | ty::ConstKind::Infer(ty::InferConst::Var(v)) => { |
74b04a01 XL |
149 | let opt_ct = self |
150 | .infcx | |
151 | .inner | |
152 | .borrow_mut() | |
f9f354fc | 153 | .const_unification_table() |
74b04a01 XL |
154 | .probe_value(v) |
155 | .val | |
156 | .known(); | |
923072b8 | 157 | self.freshen_const(opt_ct, ty::InferConst::Var(v), ty::InferConst::Fresh, ct.ty()) |
48663c56 | 158 | } |
60c5eb7d | 159 | ty::ConstKind::Infer(ty::InferConst::Fresh(i)) => { |
48663c56 XL |
160 | if i >= self.const_freshen_count { |
161 | bug!( | |
162 | "Encountered a freshend const with id {} \ | |
163 | but our counter is only at {}", | |
164 | i, | |
165 | self.const_freshen_count, | |
166 | ); | |
167 | } | |
923072b8 | 168 | ct |
48663c56 XL |
169 | } |
170 | ||
dfeec247 | 171 | ty::ConstKind::Bound(..) | ty::ConstKind::Placeholder(_) => { |
48663c56 XL |
172 | bug!("unexpected const {:?}", ct) |
173 | } | |
174 | ||
ba9703b0 XL |
175 | ty::ConstKind::Param(_) |
176 | | ty::ConstKind::Value(_) | |
177 | | ty::ConstKind::Unevaluated(..) | |
487cf647 | 178 | | ty::ConstKind::Expr(..) |
923072b8 | 179 | | ty::ConstKind::Error(_) => ct.super_fold_with(self), |
48663c56 | 180 | } |
48663c56 | 181 | } |
1a4d82fc | 182 | } |
9ffffee4 FG |
183 | |
184 | impl<'a, 'tcx> TypeFreshener<'a, 'tcx> { | |
185 | // This is separate from `fold_ty` to keep that method small and inlinable. | |
186 | #[inline(never)] | |
187 | fn fold_infer_ty(&mut self, v: ty::InferTy) -> Option<Ty<'tcx>> { | |
188 | match v { | |
189 | ty::TyVar(v) => { | |
190 | let opt_ty = self.infcx.inner.borrow_mut().type_variables().probe(v).known(); | |
191 | Some(self.freshen_ty(opt_ty, ty::TyVar(v), |n| self.infcx.tcx.mk_fresh_ty(n))) | |
192 | } | |
193 | ||
194 | ty::IntVar(v) => Some( | |
195 | self.freshen_ty( | |
196 | self.infcx | |
197 | .inner | |
198 | .borrow_mut() | |
199 | .int_unification_table() | |
200 | .probe_value(v) | |
201 | .map(|v| v.to_type(self.infcx.tcx)), | |
202 | ty::IntVar(v), | |
203 | |n| self.infcx.tcx.mk_fresh_int_ty(n), | |
204 | ), | |
205 | ), | |
206 | ||
207 | ty::FloatVar(v) => Some( | |
208 | self.freshen_ty( | |
209 | self.infcx | |
210 | .inner | |
211 | .borrow_mut() | |
212 | .float_unification_table() | |
213 | .probe_value(v) | |
214 | .map(|v| v.to_type(self.infcx.tcx)), | |
215 | ty::FloatVar(v), | |
216 | |n| self.infcx.tcx.mk_fresh_float_ty(n), | |
217 | ), | |
218 | ), | |
219 | ||
220 | ty::FreshTy(ct) | ty::FreshIntTy(ct) | ty::FreshFloatTy(ct) => { | |
221 | if ct >= self.ty_freshen_count { | |
222 | bug!( | |
223 | "Encountered a freshend type with id {} \ | |
224 | but our counter is only at {}", | |
225 | ct, | |
226 | self.ty_freshen_count | |
227 | ); | |
228 | } | |
229 | None | |
230 | } | |
231 | } | |
232 | } | |
233 | } |