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