]>
Commit | Line | Data |
---|---|---|
8faf50e0 XL |
1 | //! **Canonicalization** is the key to constructing a query in the |
2 | //! middle of type inference. Ordinarily, it is not possible to store | |
3 | //! types from type inference in query keys, because they contain | |
4 | //! references to inference variables whose lifetimes are too short | |
5 | //! and so forth. Canonicalizing a value T1 using `canonicalize_query` | |
6 | //! produces two things: | |
7 | //! | |
8 | //! - a value T2 where each unbound inference variable has been | |
9 | //! replaced with a **canonical variable**; | |
10 | //! - a map M (of type `CanonicalVarValues`) from those canonical | |
11 | //! variables back to the original. | |
12 | //! | |
a1dfa0c6 | 13 | //! We can then do queries using T2. These will give back constraints |
8faf50e0 XL |
14 | //! on the canonical variables which can be translated, using the map |
15 | //! M, into constraints in our source context. This process of | |
16 | //! translating the results back is done by the | |
17 | //! `instantiate_query_result` method. | |
18 | //! | |
19 | //! For a more detailed look at what is happening here, check | |
20 | //! out the [chapter in the rustc guide][c]. | |
21 | //! | |
a1dfa0c6 | 22 | //! [c]: https://rust-lang.github.io/rustc-guide/traits/canonicalization.html |
8faf50e0 | 23 | |
74b04a01 | 24 | use crate::infer::MemberConstraint; |
dfeec247 XL |
25 | use crate::ty::subst::GenericArg; |
26 | use crate::ty::{self, BoundVar, List, Region, TyCtxt}; | |
e74abb32 | 27 | use rustc_index::vec::IndexVec; |
532ac7d7 | 28 | use rustc_macros::HashStable; |
416331ca | 29 | use rustc_serialize::UseSpecializedDecodable; |
a1dfa0c6 | 30 | use smallvec::SmallVec; |
8faf50e0 | 31 | use std::ops::Index; |
8faf50e0 | 32 | |
8faf50e0 | 33 | /// A "canonicalized" type `V` is one where all free inference |
b7449926 | 34 | /// variables have been rewritten to "canonical vars". These are |
8faf50e0 | 35 | /// numbered starting from 0 in order of first appearance. |
60c5eb7d XL |
36 | #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] |
37 | #[derive(HashStable, TypeFoldable, Lift)] | |
dc9dc135 | 38 | pub struct Canonical<'tcx, V> { |
a1dfa0c6 | 39 | pub max_universe: ty::UniverseIndex, |
dc9dc135 | 40 | pub variables: CanonicalVarInfos<'tcx>, |
8faf50e0 XL |
41 | pub value: V, |
42 | } | |
43 | ||
dc9dc135 | 44 | pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo>; |
8faf50e0 | 45 | |
dc9dc135 | 46 | impl<'tcx> UseSpecializedDecodable for CanonicalVarInfos<'tcx> {} |
8faf50e0 XL |
47 | |
48 | /// A set of values corresponding to the canonical variables from some | |
49 | /// `Canonical`. You can give these values to | |
50 | /// `canonical_value.substitute` to substitute them into the canonical | |
51 | /// value at the right places. | |
52 | /// | |
53 | /// When you canonicalize a value `V`, you get back one of these | |
54 | /// vectors with the original values that were replaced by canonical | |
55 | /// variables. You will need to supply it later to instantiate the | |
56 | /// canonicalized query response. | |
60c5eb7d XL |
57 | #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] |
58 | #[derive(HashStable, TypeFoldable, Lift)] | |
8faf50e0 | 59 | pub struct CanonicalVarValues<'tcx> { |
e74abb32 | 60 | pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>, |
8faf50e0 XL |
61 | } |
62 | ||
0bf4aa26 XL |
63 | /// When we canonicalize a value to form a query, we wind up replacing |
64 | /// various parts of it with canonical variables. This struct stores | |
65 | /// those replaced bits to remember for when we process the query | |
66 | /// result. | |
e74abb32 | 67 | #[derive(Clone, Debug)] |
0bf4aa26 | 68 | pub struct OriginalQueryValues<'tcx> { |
a1dfa0c6 XL |
69 | /// Map from the universes that appear in the query to the |
70 | /// universes in the caller context. For the time being, we only | |
71 | /// ever put ROOT values into the query, so this map is very | |
72 | /// simple. | |
73 | pub universe_map: SmallVec<[ty::UniverseIndex; 4]>, | |
74 | ||
0bf4aa26 XL |
75 | /// This is equivalent to `CanonicalVarValues`, but using a |
76 | /// `SmallVec` yields a significant performance win. | |
e74abb32 | 77 | pub var_values: SmallVec<[GenericArg<'tcx>; 8]>, |
0bf4aa26 | 78 | } |
8faf50e0 | 79 | |
a1dfa0c6 XL |
80 | impl Default for OriginalQueryValues<'tcx> { |
81 | fn default() -> Self { | |
82 | let mut universe_map = SmallVec::default(); | |
83 | universe_map.push(ty::UniverseIndex::ROOT); | |
84 | ||
dfeec247 | 85 | Self { universe_map, var_values: SmallVec::default() } |
a1dfa0c6 XL |
86 | } |
87 | } | |
88 | ||
8faf50e0 XL |
89 | /// Information about a canonical variable that is included with the |
90 | /// canonical value. This is sufficient information for code to create | |
91 | /// a copy of the canonical value in some other inference context, | |
92 | /// with fresh inference variables replacing the canonical values. | |
532ac7d7 | 93 | #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)] |
8faf50e0 XL |
94 | pub struct CanonicalVarInfo { |
95 | pub kind: CanonicalVarKind, | |
96 | } | |
97 | ||
a1dfa0c6 XL |
98 | impl CanonicalVarInfo { |
99 | pub fn universe(&self) -> ty::UniverseIndex { | |
100 | self.kind.universe() | |
101 | } | |
102 | ||
103 | pub fn is_existential(&self) -> bool { | |
104 | match self.kind { | |
105 | CanonicalVarKind::Ty(_) => true, | |
106 | CanonicalVarKind::PlaceholderTy(_) => false, | |
107 | CanonicalVarKind::Region(_) => true, | |
108 | CanonicalVarKind::PlaceholderRegion(..) => false, | |
48663c56 XL |
109 | CanonicalVarKind::Const(_) => true, |
110 | CanonicalVarKind::PlaceholderConst(_) => false, | |
a1dfa0c6 XL |
111 | } |
112 | } | |
113 | } | |
114 | ||
8faf50e0 XL |
115 | /// Describes the "kind" of the canonical variable. This is a "kind" |
116 | /// in the type-theory sense of the term -- i.e., a "meta" type system | |
117 | /// that analyzes type-like values. | |
532ac7d7 | 118 | #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)] |
8faf50e0 XL |
119 | pub enum CanonicalVarKind { |
120 | /// Some kind of type inference variable. | |
121 | Ty(CanonicalTyVarKind), | |
122 | ||
a1dfa0c6 XL |
123 | /// A "placeholder" that represents "any type". |
124 | PlaceholderTy(ty::PlaceholderType), | |
125 | ||
8faf50e0 | 126 | /// Region variable `'?R`. |
a1dfa0c6 XL |
127 | Region(ty::UniverseIndex), |
128 | ||
129 | /// A "placeholder" that represents "any region". Created when you | |
130 | /// are solving a goal like `for<'a> T: Foo<'a>` to represent the | |
131 | /// bound region `'a`. | |
132 | PlaceholderRegion(ty::PlaceholderRegion), | |
48663c56 XL |
133 | |
134 | /// Some kind of const inference variable. | |
135 | Const(ty::UniverseIndex), | |
136 | ||
137 | /// A "placeholder" that represents "any const". | |
138 | PlaceholderConst(ty::PlaceholderConst), | |
a1dfa0c6 XL |
139 | } |
140 | ||
141 | impl CanonicalVarKind { | |
142 | pub fn universe(self) -> ty::UniverseIndex { | |
143 | match self { | |
144 | CanonicalVarKind::Ty(kind) => match kind { | |
145 | CanonicalTyVarKind::General(ui) => ui, | |
146 | CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT, | |
dfeec247 | 147 | }, |
a1dfa0c6 XL |
148 | |
149 | CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe, | |
150 | CanonicalVarKind::Region(ui) => ui, | |
151 | CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe, | |
48663c56 XL |
152 | CanonicalVarKind::Const(ui) => ui, |
153 | CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe, | |
a1dfa0c6 XL |
154 | } |
155 | } | |
8faf50e0 XL |
156 | } |
157 | ||
158 | /// Rust actually has more than one category of type variables; | |
159 | /// notably, the type variables we create for literals (e.g., 22 or | |
160 | /// 22.) can only be instantiated with integral/float types (e.g., | |
161 | /// usize or f32). In order to faithfully reproduce a type, we need to | |
162 | /// know what set of types a given type variable can be unified with. | |
532ac7d7 | 163 | #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)] |
8faf50e0 XL |
164 | pub enum CanonicalTyVarKind { |
165 | /// General type variable `?T` that can be unified with arbitrary types. | |
a1dfa0c6 | 166 | General(ty::UniverseIndex), |
8faf50e0 XL |
167 | |
168 | /// Integral type variable `?I` (that can only be unified with integral types). | |
169 | Int, | |
170 | ||
171 | /// Floating-point type variable `?F` (that can only be unified with float types). | |
172 | Float, | |
173 | } | |
174 | ||
175 | /// After we execute a query with a canonicalized key, we get back a | |
0bf4aa26 | 176 | /// `Canonical<QueryResponse<..>>`. You can use |
8faf50e0 | 177 | /// `instantiate_query_result` to access the data in this result. |
60c5eb7d | 178 | #[derive(Clone, Debug, HashStable, TypeFoldable, Lift)] |
0bf4aa26 | 179 | pub struct QueryResponse<'tcx, R> { |
8faf50e0 | 180 | pub var_values: CanonicalVarValues<'tcx>, |
dc9dc135 | 181 | pub region_constraints: QueryRegionConstraints<'tcx>, |
8faf50e0 XL |
182 | pub certainty: Certainty, |
183 | pub value: R, | |
184 | } | |
185 | ||
60c5eb7d | 186 | #[derive(Clone, Debug, Default, HashStable, TypeFoldable, Lift)] |
dc9dc135 XL |
187 | pub struct QueryRegionConstraints<'tcx> { |
188 | pub outlives: Vec<QueryOutlivesConstraint<'tcx>>, | |
189 | pub member_constraints: Vec<MemberConstraint<'tcx>>, | |
190 | } | |
191 | ||
192 | impl QueryRegionConstraints<'_> { | |
193 | /// Represents an empty (trivially true) set of region | |
194 | /// constraints. | |
195 | pub fn is_empty(&self) -> bool { | |
196 | self.outlives.is_empty() && self.member_constraints.is_empty() | |
197 | } | |
198 | } | |
8faf50e0 | 199 | |
dc9dc135 XL |
200 | pub type Canonicalized<'tcx, V> = Canonical<'tcx, V>; |
201 | ||
dfeec247 | 202 | pub type CanonicalizedQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>; |
8faf50e0 XL |
203 | |
204 | /// Indicates whether or not we were able to prove the query to be | |
205 | /// true. | |
532ac7d7 | 206 | #[derive(Copy, Clone, Debug, HashStable)] |
8faf50e0 XL |
207 | pub enum Certainty { |
208 | /// The query is known to be true, presuming that you apply the | |
209 | /// given `var_values` and the region-constraints are satisfied. | |
210 | Proven, | |
211 | ||
212 | /// The query is not known to be true, but also not known to be | |
213 | /// false. The `var_values` represent *either* values that must | |
214 | /// hold in order for the query to be true, or helpful tips that | |
215 | /// *might* make it true. Currently rustc's trait solver cannot | |
216 | /// distinguish the two (e.g., due to our preference for where | |
217 | /// clauses over impls). | |
218 | /// | |
219 | /// After some unifiations and things have been done, it makes | |
220 | /// sense to try and prove again -- of course, at that point, the | |
221 | /// canonical form will be different, making this a distinct | |
222 | /// query. | |
223 | Ambiguous, | |
224 | } | |
225 | ||
226 | impl Certainty { | |
227 | pub fn is_proven(&self) -> bool { | |
228 | match self { | |
229 | Certainty::Proven => true, | |
230 | Certainty::Ambiguous => false, | |
231 | } | |
232 | } | |
233 | ||
234 | pub fn is_ambiguous(&self) -> bool { | |
235 | !self.is_proven() | |
236 | } | |
237 | } | |
238 | ||
0bf4aa26 | 239 | impl<'tcx, R> QueryResponse<'tcx, R> { |
8faf50e0 XL |
240 | pub fn is_proven(&self) -> bool { |
241 | self.certainty.is_proven() | |
242 | } | |
243 | ||
244 | pub fn is_ambiguous(&self) -> bool { | |
245 | !self.is_proven() | |
246 | } | |
247 | } | |
248 | ||
0bf4aa26 | 249 | impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> { |
8faf50e0 XL |
250 | pub fn is_proven(&self) -> bool { |
251 | self.value.is_proven() | |
252 | } | |
253 | ||
254 | pub fn is_ambiguous(&self) -> bool { | |
255 | !self.is_proven() | |
256 | } | |
257 | } | |
258 | ||
dc9dc135 | 259 | impl<'tcx, V> Canonical<'tcx, V> { |
b7449926 XL |
260 | /// Allows you to map the `value` of a canonical while keeping the |
261 | /// same set of bound variables. | |
262 | /// | |
263 | /// **WARNING:** This function is very easy to mis-use, hence the | |
264 | /// name! In particular, the new value `W` must use all **the | |
265 | /// same type/region variables** in **precisely the same order** | |
266 | /// as the original! (The ordering is defined by the | |
267 | /// `TypeFoldable` implementation of the type in question.) | |
268 | /// | |
269 | /// An example of a **correct** use of this: | |
270 | /// | |
271 | /// ```rust,ignore (not real code) | |
272 | /// let a: Canonical<'_, T> = ...; | |
273 | /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, )); | |
274 | /// ``` | |
275 | /// | |
276 | /// An example of an **incorrect** use of this: | |
277 | /// | |
278 | /// ```rust,ignore (not real code) | |
279 | /// let a: Canonical<'tcx, T> = ...; | |
280 | /// let ty: Ty<'tcx> = ...; | |
281 | /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty)); | |
282 | /// ``` | |
dc9dc135 | 283 | pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> { |
dfeec247 XL |
284 | let Canonical { max_universe, variables, value } = self; |
285 | Canonical { max_universe, variables, value: map_op(value) } | |
b7449926 XL |
286 | } |
287 | } | |
288 | ||
dc9dc135 | 289 | pub type QueryOutlivesConstraint<'tcx> = |
e74abb32 | 290 | ty::Binder<ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>; |
8faf50e0 | 291 | |
8faf50e0 | 292 | CloneTypeFoldableAndLiftImpls! { |
9fa01778 XL |
293 | crate::infer::canonical::Certainty, |
294 | crate::infer::canonical::CanonicalVarInfo, | |
295 | crate::infer::canonical::CanonicalVarKind, | |
8faf50e0 XL |
296 | } |
297 | ||
298 | CloneTypeFoldableImpls! { | |
299 | for <'tcx> { | |
9fa01778 | 300 | crate::infer::canonical::CanonicalVarInfos<'tcx>, |
8faf50e0 XL |
301 | } |
302 | } | |
303 | ||
8faf50e0 | 304 | impl<'tcx> CanonicalVarValues<'tcx> { |
0731742a | 305 | pub fn len(&self) -> usize { |
8faf50e0 XL |
306 | self.var_values.len() |
307 | } | |
0731742a | 308 | |
9fa01778 | 309 | /// Makes an identity substitution from this one: each bound var |
0731742a XL |
310 | /// is matched to the same bound var, preserving the original kinds. |
311 | /// For example, if we have: | |
312 | /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]` | |
313 | /// we'll return a substitution `subst` with: | |
314 | /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`. | |
dc9dc135 | 315 | pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self { |
e74abb32 | 316 | use crate::ty::subst::GenericArgKind; |
0731742a XL |
317 | |
318 | CanonicalVarValues { | |
dfeec247 XL |
319 | var_values: self |
320 | .var_values | |
321 | .iter() | |
0731742a XL |
322 | .zip(0..) |
323 | .map(|(kind, i)| match kind.unpack() { | |
dfeec247 XL |
324 | GenericArgKind::Type(..) => { |
325 | tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into() | |
326 | } | |
327 | GenericArgKind::Lifetime(..) => tcx | |
328 | .mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion::BrAnon(i))) | |
329 | .into(), | |
330 | GenericArgKind::Const(ct) => tcx | |
331 | .mk_const(ty::Const { | |
48663c56 | 332 | ty: ct.ty, |
60c5eb7d | 333 | val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)), |
dfeec247 XL |
334 | }) |
335 | .into(), | |
0731742a | 336 | }) |
dfeec247 | 337 | .collect(), |
0731742a XL |
338 | } |
339 | } | |
8faf50e0 XL |
340 | } |
341 | ||
342 | impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> { | |
e74abb32 XL |
343 | type Item = GenericArg<'tcx>; |
344 | type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>; | |
8faf50e0 XL |
345 | |
346 | fn into_iter(self) -> Self::IntoIter { | |
347 | self.var_values.iter().cloned() | |
348 | } | |
349 | } | |
350 | ||
a1dfa0c6 | 351 | impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> { |
e74abb32 | 352 | type Output = GenericArg<'tcx>; |
8faf50e0 | 353 | |
e74abb32 | 354 | fn index(&self, value: BoundVar) -> &GenericArg<'tcx> { |
8faf50e0 XL |
355 | &self.var_values[value] |
356 | } | |
357 | } |