]>
Commit | Line | Data |
---|---|---|
8faf50e0 XL |
1 | //! This module contains the "canonicalizer" itself. |
2 | //! | |
a1dfa0c6 | 3 | //! For an overview of what canonicalization is and how it fits into |
ba9703b0 | 4 | //! rustc, check out the [chapter in the rustc dev guide][c]. |
8faf50e0 | 5 | //! |
f9f354fc | 6 | //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html |
8faf50e0 | 7 | |
9fa01778 | 8 | use crate::infer::canonical::{ |
9c376795 | 9 | Canonical, CanonicalTyVarKind, CanonicalVarInfo, CanonicalVarKind, OriginalQueryValues, |
8faf50e0 | 10 | }; |
9fa01778 | 11 | use crate::infer::InferCtxt; |
ba9703b0 | 12 | use rustc_middle::ty::flags::FlagComputation; |
923072b8 | 13 | use rustc_middle::ty::fold::{TypeFoldable, TypeFolder, TypeSuperFoldable}; |
ba9703b0 | 14 | use rustc_middle::ty::subst::GenericArg; |
9ffffee4 | 15 | use rustc_middle::ty::{self, BoundVar, InferConst, List, Ty, TyCtxt, TypeFlags, TypeVisitableExt}; |
dfeec247 | 16 | use std::sync::atomic::Ordering; |
8faf50e0 XL |
17 | |
18 | use rustc_data_structures::fx::FxHashMap; | |
e74abb32 | 19 | use rustc_index::vec::Idx; |
b7449926 | 20 | use smallvec::SmallVec; |
8faf50e0 | 21 | |
2b03887a | 22 | impl<'tcx> InferCtxt<'tcx> { |
8faf50e0 XL |
23 | /// Canonicalizes a query value `V`. When we canonicalize a query, |
24 | /// we not only canonicalize unbound inference variables, but we | |
25 | /// *also* replace all free regions whatsoever. So for example a | |
26 | /// query like `T: Trait<'static>` would be canonicalized to | |
27 | /// | |
28 | /// ```text | |
29 | /// T: Trait<'?0> | |
30 | /// ``` | |
31 | /// | |
32 | /// with a mapping M that maps `'?0` to `'static`. | |
33 | /// | |
34 | /// To get a good understanding of what is happening here, check | |
ba9703b0 | 35 | /// out the [chapter in the rustc dev guide][c]. |
8faf50e0 | 36 | /// |
f9f354fc | 37 | /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#canonicalizing-the-query |
8faf50e0 XL |
38 | pub fn canonicalize_query<V>( |
39 | &self, | |
fc512014 | 40 | value: V, |
0bf4aa26 | 41 | query_state: &mut OriginalQueryValues<'tcx>, |
9c376795 | 42 | ) -> Canonical<'tcx, V> |
8faf50e0 | 43 | where |
9ffffee4 | 44 | V: TypeFoldable<TyCtxt<'tcx>>, |
8faf50e0 | 45 | { |
dfeec247 | 46 | self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed); |
8faf50e0 | 47 | |
136023e0 | 48 | Canonicalizer::canonicalize(value, self, self.tcx, &CanonicalizeAllFreeRegions, query_state) |
8faf50e0 XL |
49 | } |
50 | ||
5099ac24 FG |
51 | /// Like [Self::canonicalize_query], but preserves distinct universes. For |
52 | /// example, canonicalizing `&'?0: Trait<'?1>`, where `'?0` is in `U1` and | |
9ffffee4 | 53 | /// `'?1` is in `U3` would be canonicalized to have `?0` in `U1` and `'?1` |
5099ac24 FG |
54 | /// in `U2`. |
55 | /// | |
56 | /// This is used for Chalk integration. | |
57 | pub fn canonicalize_query_preserving_universes<V>( | |
58 | &self, | |
59 | value: V, | |
60 | query_state: &mut OriginalQueryValues<'tcx>, | |
9c376795 | 61 | ) -> Canonical<'tcx, V> |
5099ac24 | 62 | where |
9ffffee4 | 63 | V: TypeFoldable<TyCtxt<'tcx>>, |
5099ac24 FG |
64 | { |
65 | self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed); | |
66 | ||
67 | Canonicalizer::canonicalize( | |
68 | value, | |
69 | self, | |
70 | self.tcx, | |
71 | &CanonicalizeAllFreeRegionsPreservingUniverses, | |
72 | query_state, | |
73 | ) | |
74 | } | |
75 | ||
8faf50e0 XL |
76 | /// Canonicalizes a query *response* `V`. When we canonicalize a |
77 | /// query response, we only canonicalize unbound inference | |
78 | /// variables, and we leave other free regions alone. So, | |
79 | /// continuing with the example from `canonicalize_query`, if | |
80 | /// there was an input query `T: Trait<'static>`, it would have | |
81 | /// been canonicalized to | |
82 | /// | |
83 | /// ```text | |
84 | /// T: Trait<'?0> | |
85 | /// ``` | |
86 | /// | |
87 | /// with a mapping M that maps `'?0` to `'static`. But if we found that there | |
88 | /// exists only one possible impl of `Trait`, and it looks like | |
04454e1e FG |
89 | /// ```ignore (illustrative) |
90 | /// impl<T> Trait<'static> for T { .. } | |
91 | /// ``` | |
8faf50e0 XL |
92 | /// then we would prepare a query result R that (among other |
93 | /// things) includes a mapping to `'?0 := 'static`. When | |
94 | /// canonicalizing this query result R, we would leave this | |
95 | /// reference to `'static` alone. | |
96 | /// | |
97 | /// To get a good understanding of what is happening here, check | |
ba9703b0 | 98 | /// out the [chapter in the rustc dev guide][c]. |
8faf50e0 | 99 | /// |
f9f354fc | 100 | /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#canonicalizing-the-query-result |
9c376795 | 101 | pub fn canonicalize_response<V>(&self, value: V) -> Canonical<'tcx, V> |
8faf50e0 | 102 | where |
9ffffee4 | 103 | V: TypeFoldable<TyCtxt<'tcx>>, |
8faf50e0 | 104 | { |
0bf4aa26 | 105 | let mut query_state = OriginalQueryValues::default(); |
8faf50e0 XL |
106 | Canonicalizer::canonicalize( |
107 | value, | |
136023e0 | 108 | self, |
8faf50e0 | 109 | self.tcx, |
0bf4aa26 XL |
110 | &CanonicalizeQueryResponse, |
111 | &mut query_state, | |
8faf50e0 XL |
112 | ) |
113 | } | |
114 | ||
9c376795 | 115 | pub fn canonicalize_user_type_annotation<V>(&self, value: V) -> Canonical<'tcx, V> |
a1dfa0c6 | 116 | where |
9ffffee4 | 117 | V: TypeFoldable<TyCtxt<'tcx>>, |
a1dfa0c6 XL |
118 | { |
119 | let mut query_state = OriginalQueryValues::default(); | |
120 | Canonicalizer::canonicalize( | |
121 | value, | |
136023e0 | 122 | self, |
a1dfa0c6 XL |
123 | self.tcx, |
124 | &CanonicalizeUserTypeAnnotation, | |
125 | &mut query_state, | |
126 | ) | |
127 | } | |
128 | ||
136023e0 XL |
129 | /// A variant of `canonicalize_query` that does not |
130 | /// canonicalize `'static`. This is useful when | |
131 | /// the query implementation can perform more efficient | |
132 | /// handling of `'static` regions (e.g. trait evaluation). | |
133 | pub fn canonicalize_query_keep_static<V>( | |
8faf50e0 | 134 | &self, |
fc512014 | 135 | value: V, |
0bf4aa26 | 136 | query_state: &mut OriginalQueryValues<'tcx>, |
9c376795 | 137 | ) -> Canonical<'tcx, V> |
8faf50e0 | 138 | where |
9ffffee4 | 139 | V: TypeFoldable<TyCtxt<'tcx>>, |
8faf50e0 | 140 | { |
dfeec247 | 141 | self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed); |
8faf50e0 XL |
142 | |
143 | Canonicalizer::canonicalize( | |
144 | value, | |
136023e0 | 145 | self, |
8faf50e0 | 146 | self.tcx, |
0bf4aa26 XL |
147 | &CanonicalizeFreeRegionsOtherThanStatic, |
148 | query_state, | |
8faf50e0 XL |
149 | ) |
150 | } | |
151 | } | |
152 | ||
0bf4aa26 XL |
153 | /// Controls how we canonicalize "free regions" that are not inference |
154 | /// variables. This depends on what we are canonicalizing *for* -- | |
155 | /// e.g., if we are canonicalizing to create a query, we want to | |
156 | /// replace those with inference variables, since we want to make a | |
157 | /// maximally general query. But if we are canonicalizing a *query | |
158 | /// response*, then we don't typically replace free regions, as they | |
159 | /// must have been introduced from other parts of the system. | |
5099ac24 | 160 | trait CanonicalizeMode { |
a2a8927a | 161 | fn canonicalize_free_region<'tcx>( |
0bf4aa26 | 162 | &self, |
dc9dc135 | 163 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, |
0bf4aa26 XL |
164 | r: ty::Region<'tcx>, |
165 | ) -> ty::Region<'tcx>; | |
166 | ||
167 | fn any(&self) -> bool; | |
5099ac24 FG |
168 | |
169 | // Do we preserve universe of variables. | |
170 | fn preserve_universes(&self) -> bool; | |
8faf50e0 XL |
171 | } |
172 | ||
0bf4aa26 XL |
173 | struct CanonicalizeQueryResponse; |
174 | ||
5099ac24 | 175 | impl CanonicalizeMode for CanonicalizeQueryResponse { |
a2a8927a | 176 | fn canonicalize_free_region<'tcx>( |
0bf4aa26 | 177 | &self, |
dc9dc135 | 178 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, |
0bf4aa26 XL |
179 | r: ty::Region<'tcx>, |
180 | ) -> ty::Region<'tcx> { | |
5099ac24 | 181 | match *r { |
f2b60f7d | 182 | ty::ReFree(_) | ty::ReErased | ty::ReStatic | ty::ReEarlyBound(..) => r, |
74b04a01 | 183 | |
a1dfa0c6 | 184 | ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region( |
5099ac24 | 185 | CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderRegion(placeholder) }, |
a1dfa0c6 XL |
186 | r, |
187 | ), | |
74b04a01 | 188 | |
a1dfa0c6 | 189 | ty::ReVar(vid) => { |
5099ac24 | 190 | let universe = canonicalizer.region_var_universe(vid); |
a1dfa0c6 | 191 | canonicalizer.canonical_var_for_region( |
dfeec247 | 192 | CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) }, |
a1dfa0c6 XL |
193 | r, |
194 | ) | |
195 | } | |
74b04a01 | 196 | |
0bf4aa26 XL |
197 | _ => { |
198 | // Other than `'static` or `'empty`, the query | |
199 | // response should be executing in a fully | |
200 | // canonicalized environment, so there shouldn't be | |
201 | // any other region names it can come up. | |
0731742a XL |
202 | // |
203 | // rust-lang/rust#57464: `impl Trait` can leak local | |
204 | // scopes (in manner violating typeck). Therefore, use | |
205 | // `delay_span_bug` to allow type error over an ICE. | |
9ffffee4 FG |
206 | canonicalizer.tcx.sess.delay_span_bug( |
207 | rustc_span::DUMMY_SP, | |
208 | &format!("unexpected region in query response: `{:?}`", r), | |
209 | ); | |
0731742a | 210 | r |
0bf4aa26 XL |
211 | } |
212 | } | |
213 | } | |
214 | ||
8faf50e0 | 215 | fn any(&self) -> bool { |
0bf4aa26 XL |
216 | false |
217 | } | |
5099ac24 FG |
218 | |
219 | fn preserve_universes(&self) -> bool { | |
220 | true | |
221 | } | |
0bf4aa26 XL |
222 | } |
223 | ||
a1dfa0c6 XL |
224 | struct CanonicalizeUserTypeAnnotation; |
225 | ||
5099ac24 | 226 | impl CanonicalizeMode for CanonicalizeUserTypeAnnotation { |
a2a8927a | 227 | fn canonicalize_free_region<'tcx>( |
a1dfa0c6 | 228 | &self, |
dc9dc135 | 229 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, |
a1dfa0c6 XL |
230 | r: ty::Region<'tcx>, |
231 | ) -> ty::Region<'tcx> { | |
5099ac24 | 232 | match *r { |
74b04a01 | 233 | ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReStatic => r, |
a1dfa0c6 XL |
234 | ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r), |
235 | _ => { | |
236 | // We only expect region names that the user can type. | |
237 | bug!("unexpected region in query response: `{:?}`", r) | |
238 | } | |
239 | } | |
240 | } | |
241 | ||
242 | fn any(&self) -> bool { | |
243 | false | |
244 | } | |
5099ac24 FG |
245 | |
246 | fn preserve_universes(&self) -> bool { | |
247 | false | |
248 | } | |
a1dfa0c6 XL |
249 | } |
250 | ||
0bf4aa26 XL |
251 | struct CanonicalizeAllFreeRegions; |
252 | ||
5099ac24 | 253 | impl CanonicalizeMode for CanonicalizeAllFreeRegions { |
a2a8927a | 254 | fn canonicalize_free_region<'tcx>( |
0bf4aa26 | 255 | &self, |
dc9dc135 | 256 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, |
0bf4aa26 XL |
257 | r: ty::Region<'tcx>, |
258 | ) -> ty::Region<'tcx> { | |
a1dfa0c6 | 259 | canonicalizer.canonical_var_for_region_in_root_universe(r) |
0bf4aa26 XL |
260 | } |
261 | ||
262 | fn any(&self) -> bool { | |
263 | true | |
264 | } | |
5099ac24 FG |
265 | |
266 | fn preserve_universes(&self) -> bool { | |
267 | false | |
268 | } | |
269 | } | |
270 | ||
271 | struct CanonicalizeAllFreeRegionsPreservingUniverses; | |
272 | ||
273 | impl CanonicalizeMode for CanonicalizeAllFreeRegionsPreservingUniverses { | |
274 | fn canonicalize_free_region<'tcx>( | |
275 | &self, | |
276 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, | |
277 | r: ty::Region<'tcx>, | |
278 | ) -> ty::Region<'tcx> { | |
279 | let universe = canonicalizer.infcx.universe_of_region(r); | |
280 | canonicalizer.canonical_var_for_region( | |
281 | CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) }, | |
282 | r, | |
283 | ) | |
284 | } | |
285 | ||
286 | fn any(&self) -> bool { | |
287 | true | |
288 | } | |
289 | ||
290 | fn preserve_universes(&self) -> bool { | |
291 | true | |
292 | } | |
0bf4aa26 XL |
293 | } |
294 | ||
295 | struct CanonicalizeFreeRegionsOtherThanStatic; | |
296 | ||
5099ac24 | 297 | impl CanonicalizeMode for CanonicalizeFreeRegionsOtherThanStatic { |
a2a8927a | 298 | fn canonicalize_free_region<'tcx>( |
0bf4aa26 | 299 | &self, |
dc9dc135 | 300 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, |
0bf4aa26 XL |
301 | r: ty::Region<'tcx>, |
302 | ) -> ty::Region<'tcx> { | |
5099ac24 | 303 | if r.is_static() { r } else { canonicalizer.canonical_var_for_region_in_root_universe(r) } |
0bf4aa26 XL |
304 | } |
305 | ||
306 | fn any(&self) -> bool { | |
307 | true | |
8faf50e0 | 308 | } |
5099ac24 FG |
309 | |
310 | fn preserve_universes(&self) -> bool { | |
311 | false | |
312 | } | |
8faf50e0 XL |
313 | } |
314 | ||
dc9dc135 | 315 | struct Canonicalizer<'cx, 'tcx> { |
2b03887a | 316 | infcx: &'cx InferCtxt<'tcx>, |
dc9dc135 | 317 | tcx: TyCtxt<'tcx>, |
fc512014 | 318 | variables: SmallVec<[CanonicalVarInfo<'tcx>; 8]>, |
0bf4aa26 | 319 | query_state: &'cx mut OriginalQueryValues<'tcx>, |
8faf50e0 XL |
320 | // Note that indices is only used once `var_values` is big enough to be |
321 | // heap-allocated. | |
e74abb32 | 322 | indices: FxHashMap<GenericArg<'tcx>, BoundVar>, |
5099ac24 | 323 | canonicalize_mode: &'cx dyn CanonicalizeMode, |
8faf50e0 | 324 | needs_canonical_flags: TypeFlags, |
a1dfa0c6 XL |
325 | |
326 | binder_index: ty::DebruijnIndex, | |
8faf50e0 XL |
327 | } |
328 | ||
9ffffee4 FG |
329 | impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> { |
330 | fn interner(&self) -> TyCtxt<'tcx> { | |
8faf50e0 XL |
331 | self.tcx |
332 | } | |
333 | ||
cdc7bbd5 | 334 | fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T> |
dfeec247 | 335 | where |
9ffffee4 | 336 | T: TypeFoldable<TyCtxt<'tcx>>, |
a1dfa0c6 XL |
337 | { |
338 | self.binder_index.shift_in(1); | |
339 | let t = t.super_fold_with(self); | |
340 | self.binder_index.shift_out(1); | |
341 | t | |
342 | } | |
343 | ||
8faf50e0 XL |
344 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
345 | match *r { | |
a1dfa0c6 XL |
346 | ty::ReLateBound(index, ..) => { |
347 | if index >= self.binder_index { | |
60c5eb7d | 348 | bug!("escaping late-bound region during canonicalization"); |
a1dfa0c6 XL |
349 | } else { |
350 | r | |
351 | } | |
8faf50e0 XL |
352 | } |
353 | ||
354 | ty::ReVar(vid) => { | |
f035d41b | 355 | let resolved_vid = self |
dfeec247 | 356 | .infcx |
74b04a01 XL |
357 | .inner |
358 | .borrow_mut() | |
359 | .unwrap_region_constraints() | |
f035d41b | 360 | .opportunistic_resolve_var(vid); |
8faf50e0 XL |
361 | debug!( |
362 | "canonical: region var found with vid {:?}, \ | |
363 | opportunistically resolved to {:?}", | |
f2b60f7d | 364 | vid, resolved_vid |
8faf50e0 | 365 | ); |
9ffffee4 | 366 | let r = self.tcx.mk_re_var(resolved_vid); |
5099ac24 | 367 | self.canonicalize_mode.canonicalize_free_region(self, r) |
8faf50e0 XL |
368 | } |
369 | ||
0bf4aa26 XL |
370 | ty::ReStatic |
371 | | ty::ReEarlyBound(..) | |
9ffffee4 | 372 | | ty::ReError(_) |
8faf50e0 | 373 | | ty::ReFree(_) |
0bf4aa26 | 374 | | ty::RePlaceholder(..) |
5099ac24 | 375 | | ty::ReErased => self.canonicalize_mode.canonicalize_free_region(self, r), |
8faf50e0 XL |
376 | } |
377 | } | |
378 | ||
379 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
1b1a35ee | 380 | match *t.kind() { |
a1dfa0c6 | 381 | ty::Infer(ty::TyVar(vid)) => { |
0731742a | 382 | debug!("canonical: type var found with vid {:?}", vid); |
136023e0 | 383 | match self.infcx.probe_ty_var(vid) { |
60c5eb7d | 384 | // `t` could be a float / int variable; canonicalize that instead. |
0731742a XL |
385 | Ok(t) => { |
386 | debug!("(resolved to {:?})", t); | |
387 | self.fold_ty(t) | |
388 | } | |
a1dfa0c6 XL |
389 | |
390 | // `TyVar(vid)` is unresolved, track its universe index in the canonicalized | |
60c5eb7d | 391 | // result. |
a1dfa0c6 | 392 | Err(mut ui) => { |
5099ac24 FG |
393 | if !self.canonicalize_mode.preserve_universes() { |
394 | // FIXME: perf problem described in #55921. | |
395 | ui = ty::UniverseIndex::ROOT; | |
396 | } | |
a1dfa0c6 XL |
397 | self.canonicalize_ty_var( |
398 | CanonicalVarInfo { | |
dfeec247 | 399 | kind: CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)), |
a1dfa0c6 | 400 | }, |
dfeec247 | 401 | t, |
a1dfa0c6 XL |
402 | ) |
403 | } | |
404 | } | |
405 | } | |
8faf50e0 | 406 | |
a1dfa0c6 | 407 | ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var( |
dfeec247 XL |
408 | CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Int) }, |
409 | t, | |
a1dfa0c6 | 410 | ), |
8faf50e0 | 411 | |
a1dfa0c6 | 412 | ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var( |
dfeec247 XL |
413 | CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Float) }, |
414 | t, | |
a1dfa0c6 | 415 | ), |
8faf50e0 | 416 | |
ba9703b0 | 417 | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { |
8faf50e0 XL |
418 | bug!("encountered a fresh type during canonicalization") |
419 | } | |
420 | ||
9ffffee4 FG |
421 | ty::Placeholder(mut placeholder) => { |
422 | if !self.canonicalize_mode.preserve_universes() { | |
423 | placeholder.universe = ty::UniverseIndex::ROOT; | |
424 | } | |
425 | self.canonicalize_ty_var( | |
426 | CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderTy(placeholder) }, | |
427 | t, | |
428 | ) | |
429 | } | |
a1dfa0c6 XL |
430 | |
431 | ty::Bound(debruijn, _) => { | |
432 | if debruijn >= self.binder_index { | |
433 | bug!("escaping bound type during canonicalization") | |
434 | } else { | |
435 | t | |
436 | } | |
8faf50e0 XL |
437 | } |
438 | ||
b7449926 XL |
439 | ty::Closure(..) |
440 | | ty::Generator(..) | |
441 | | ty::GeneratorWitness(..) | |
9ffffee4 | 442 | | ty::GeneratorWitnessMIR(..) |
b7449926 XL |
443 | | ty::Bool |
444 | | ty::Char | |
445 | | ty::Int(..) | |
446 | | ty::Uint(..) | |
447 | | ty::Float(..) | |
448 | | ty::Adt(..) | |
449 | | ty::Str | |
f035d41b | 450 | | ty::Error(_) |
b7449926 XL |
451 | | ty::Array(..) |
452 | | ty::Slice(..) | |
453 | | ty::RawPtr(..) | |
454 | | ty::Ref(..) | |
455 | | ty::FnDef(..) | |
456 | | ty::FnPtr(_) | |
457 | | ty::Dynamic(..) | |
458 | | ty::Never | |
459 | | ty::Tuple(..) | |
9c376795 | 460 | | ty::Alias(..) |
b7449926 | 461 | | ty::Foreign(..) |
9c376795 | 462 | | ty::Param(..) => { |
1b1a35ee | 463 | if t.flags().intersects(self.needs_canonical_flags) { |
8faf50e0 XL |
464 | t.super_fold_with(self) |
465 | } else { | |
466 | t | |
467 | } | |
468 | } | |
469 | } | |
470 | } | |
48663c56 | 471 | |
5099ac24 | 472 | fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { |
923072b8 | 473 | match ct.kind() { |
60c5eb7d | 474 | ty::ConstKind::Infer(InferConst::Var(vid)) => { |
48663c56 | 475 | debug!("canonical: const var found with vid {:?}", vid); |
136023e0 | 476 | match self.infcx.probe_const_var(vid) { |
48663c56 XL |
477 | Ok(c) => { |
478 | debug!("(resolved to {:?})", c); | |
479 | return self.fold_const(c); | |
480 | } | |
481 | ||
482 | // `ConstVar(vid)` is unresolved, track its universe index in the | |
483 | // canonicalized result | |
484 | Err(mut ui) => { | |
5099ac24 FG |
485 | if !self.canonicalize_mode.preserve_universes() { |
486 | // FIXME: perf problem described in #55921. | |
487 | ui = ty::UniverseIndex::ROOT; | |
488 | } | |
48663c56 | 489 | return self.canonicalize_const_var( |
5099ac24 | 490 | CanonicalVarInfo { kind: CanonicalVarKind::Const(ui, ct.ty()) }, |
48663c56 XL |
491 | ct, |
492 | ); | |
493 | } | |
494 | } | |
495 | } | |
60c5eb7d | 496 | ty::ConstKind::Infer(InferConst::Fresh(_)) => { |
48663c56 XL |
497 | bug!("encountered a fresh const during canonicalization") |
498 | } | |
60c5eb7d | 499 | ty::ConstKind::Bound(debruijn, _) => { |
48663c56 | 500 | if debruijn >= self.binder_index { |
487cf647 | 501 | bug!("escaping bound const during canonicalization") |
48663c56 XL |
502 | } else { |
503 | return ct; | |
504 | } | |
505 | } | |
60c5eb7d | 506 | ty::ConstKind::Placeholder(placeholder) => { |
48663c56 | 507 | return self.canonicalize_const_var( |
064997fb FG |
508 | CanonicalVarInfo { |
509 | kind: CanonicalVarKind::PlaceholderConst(placeholder, ct.ty()), | |
510 | }, | |
48663c56 XL |
511 | ct, |
512 | ); | |
513 | } | |
514 | _ => {} | |
515 | } | |
516 | ||
517 | let flags = FlagComputation::for_const(ct); | |
dfeec247 | 518 | if flags.intersects(self.needs_canonical_flags) { ct.super_fold_with(self) } else { ct } |
48663c56 | 519 | } |
8faf50e0 XL |
520 | } |
521 | ||
dc9dc135 | 522 | impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> { |
8faf50e0 XL |
523 | /// The main `canonicalize` method, shared impl of |
524 | /// `canonicalize_query` and `canonicalize_response`. | |
525 | fn canonicalize<V>( | |
fc512014 | 526 | value: V, |
2b03887a | 527 | infcx: &InferCtxt<'tcx>, |
dc9dc135 | 528 | tcx: TyCtxt<'tcx>, |
5099ac24 | 529 | canonicalize_region_mode: &dyn CanonicalizeMode, |
0bf4aa26 | 530 | query_state: &mut OriginalQueryValues<'tcx>, |
9c376795 | 531 | ) -> Canonical<'tcx, V> |
8faf50e0 | 532 | where |
9ffffee4 | 533 | V: TypeFoldable<TyCtxt<'tcx>>, |
8faf50e0 | 534 | { |
8faf50e0 | 535 | let needs_canonical_flags = if canonicalize_region_mode.any() { |
ba9703b0 | 536 | TypeFlags::NEEDS_INFER | |
5099ac24 | 537 | TypeFlags::HAS_FREE_REGIONS | // `HAS_RE_PLACEHOLDER` implies `HAS_FREE_REGIONS` |
48663c56 XL |
538 | TypeFlags::HAS_TY_PLACEHOLDER | |
539 | TypeFlags::HAS_CT_PLACEHOLDER | |
8faf50e0 | 540 | } else { |
ba9703b0 | 541 | TypeFlags::NEEDS_INFER |
dfeec247 XL |
542 | | TypeFlags::HAS_RE_PLACEHOLDER |
543 | | TypeFlags::HAS_TY_PLACEHOLDER | |
544 | | TypeFlags::HAS_CT_PLACEHOLDER | |
8faf50e0 XL |
545 | }; |
546 | ||
8faf50e0 XL |
547 | // Fast path: nothing that needs to be canonicalized. |
548 | if !value.has_type_flags(needs_canonical_flags) { | |
8faf50e0 | 549 | let canon_value = Canonical { |
a1dfa0c6 | 550 | max_universe: ty::UniverseIndex::ROOT, |
b7449926 | 551 | variables: List::empty(), |
fc512014 | 552 | value, |
8faf50e0 XL |
553 | }; |
554 | return canon_value; | |
555 | } | |
556 | ||
557 | let mut canonicalizer = Canonicalizer { | |
558 | infcx, | |
559 | tcx, | |
5099ac24 | 560 | canonicalize_mode: canonicalize_region_mode, |
8faf50e0 XL |
561 | needs_canonical_flags, |
562 | variables: SmallVec::new(), | |
0bf4aa26 | 563 | query_state, |
8faf50e0 | 564 | indices: FxHashMap::default(), |
a1dfa0c6 | 565 | binder_index: ty::INNERMOST, |
8faf50e0 XL |
566 | }; |
567 | let out_value = value.fold_with(&mut canonicalizer); | |
568 | ||
569 | // Once we have canonicalized `out_value`, it should not | |
570 | // contain anything that ties it to this inference context | |
5099ac24 FG |
571 | // anymore. |
572 | debug_assert!(!out_value.needs_infer() && !out_value.has_placeholders()); | |
8faf50e0 | 573 | |
5099ac24 | 574 | let canonical_variables = |
9ffffee4 | 575 | tcx.mk_canonical_var_infos(&canonicalizer.universe_canonicalized_variables()); |
8faf50e0 | 576 | |
a1dfa0c6 XL |
577 | let max_universe = canonical_variables |
578 | .iter() | |
579 | .map(|cvar| cvar.universe()) | |
580 | .max() | |
581 | .unwrap_or(ty::UniverseIndex::ROOT); | |
582 | ||
dfeec247 | 583 | Canonical { max_universe, variables: canonical_variables, value: out_value } |
8faf50e0 XL |
584 | } |
585 | ||
586 | /// Creates a canonical variable replacing `kind` from the input, | |
587 | /// or returns an existing variable if `kind` has already been | |
588 | /// seen. `kind` is expected to be an unbound variable (or | |
589 | /// potentially a free region). | |
fc512014 | 590 | fn canonical_var(&mut self, info: CanonicalVarInfo<'tcx>, kind: GenericArg<'tcx>) -> BoundVar { |
dfeec247 | 591 | let Canonicalizer { variables, query_state, indices, .. } = self; |
8faf50e0 | 592 | |
0bf4aa26 XL |
593 | let var_values = &mut query_state.var_values; |
594 | ||
5099ac24 FG |
595 | let universe = info.universe(); |
596 | if universe != ty::UniverseIndex::ROOT { | |
597 | assert!(self.canonicalize_mode.preserve_universes()); | |
598 | ||
599 | // Insert universe into the universe map. To preserve the order of the | |
600 | // universes in the value being canonicalized, we don't update the | |
601 | // universe in `info` until we have finished canonicalizing. | |
602 | match query_state.universe_map.binary_search(&universe) { | |
603 | Err(idx) => query_state.universe_map.insert(idx, universe), | |
604 | Ok(_) => {} | |
605 | } | |
606 | } | |
607 | ||
8faf50e0 XL |
608 | // This code is hot. `variables` and `var_values` are usually small |
609 | // (fewer than 8 elements ~95% of the time). They are SmallVec's to | |
610 | // avoid allocations in those cases. We also don't use `indices` to | |
611 | // determine if a kind has been seen before until the limit of 8 has | |
612 | // been exceeded, to also avoid allocations for `indices`. | |
ba9703b0 | 613 | if !var_values.spilled() { |
8faf50e0 XL |
614 | // `var_values` is stack-allocated. `indices` isn't used yet. Do a |
615 | // direct linear search of `var_values`. | |
616 | if let Some(idx) = var_values.iter().position(|&k| k == kind) { | |
617 | // `kind` is already present in `var_values`. | |
a1dfa0c6 | 618 | BoundVar::new(idx) |
8faf50e0 XL |
619 | } else { |
620 | // `kind` isn't present in `var_values`. Append it. Likewise | |
621 | // for `info` and `variables`. | |
622 | variables.push(info); | |
623 | var_values.push(kind); | |
624 | assert_eq!(variables.len(), var_values.len()); | |
625 | ||
626 | // If `var_values` has become big enough to be heap-allocated, | |
627 | // fill up `indices` to facilitate subsequent lookups. | |
b7449926 | 628 | if var_values.spilled() { |
8faf50e0 | 629 | assert!(indices.is_empty()); |
0bf4aa26 XL |
630 | *indices = var_values |
631 | .iter() | |
632 | .enumerate() | |
a1dfa0c6 | 633 | .map(|(i, &kind)| (kind, BoundVar::new(i))) |
0bf4aa26 | 634 | .collect(); |
8faf50e0 XL |
635 | } |
636 | // The cv is the index of the appended element. | |
a1dfa0c6 | 637 | BoundVar::new(var_values.len() - 1) |
8faf50e0 XL |
638 | } |
639 | } else { | |
640 | // `var_values` is large. Do a hashmap search via `indices`. | |
0bf4aa26 XL |
641 | *indices.entry(kind).or_insert_with(|| { |
642 | variables.push(info); | |
643 | var_values.push(kind); | |
644 | assert_eq!(variables.len(), var_values.len()); | |
a1dfa0c6 | 645 | BoundVar::new(variables.len() - 1) |
0bf4aa26 | 646 | }) |
ba9703b0 | 647 | } |
8faf50e0 XL |
648 | } |
649 | ||
5099ac24 FG |
650 | /// Replaces the universe indexes used in `var_values` with their index in |
651 | /// `query_state.universe_map`. This minimizes the maximum universe used in | |
652 | /// the canonicalized value. | |
653 | fn universe_canonicalized_variables(self) -> SmallVec<[CanonicalVarInfo<'tcx>; 8]> { | |
654 | if self.query_state.universe_map.len() == 1 { | |
655 | return self.variables; | |
656 | } | |
657 | ||
658 | let reverse_universe_map: FxHashMap<ty::UniverseIndex, ty::UniverseIndex> = self | |
659 | .query_state | |
660 | .universe_map | |
661 | .iter() | |
662 | .enumerate() | |
663 | .map(|(idx, universe)| (*universe, ty::UniverseIndex::from_usize(idx))) | |
664 | .collect(); | |
665 | ||
666 | self.variables | |
667 | .iter() | |
668 | .map(|v| CanonicalVarInfo { | |
669 | kind: match v.kind { | |
670 | CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => { | |
671 | return *v; | |
672 | } | |
673 | CanonicalVarKind::Ty(CanonicalTyVarKind::General(u)) => { | |
674 | CanonicalVarKind::Ty(CanonicalTyVarKind::General(reverse_universe_map[&u])) | |
675 | } | |
676 | CanonicalVarKind::Region(u) => { | |
677 | CanonicalVarKind::Region(reverse_universe_map[&u]) | |
678 | } | |
679 | CanonicalVarKind::Const(u, t) => { | |
680 | CanonicalVarKind::Const(reverse_universe_map[&u], t) | |
681 | } | |
682 | CanonicalVarKind::PlaceholderTy(placeholder) => { | |
683 | CanonicalVarKind::PlaceholderTy(ty::Placeholder { | |
684 | universe: reverse_universe_map[&placeholder.universe], | |
685 | ..placeholder | |
686 | }) | |
687 | } | |
688 | CanonicalVarKind::PlaceholderRegion(placeholder) => { | |
689 | CanonicalVarKind::PlaceholderRegion(ty::Placeholder { | |
690 | universe: reverse_universe_map[&placeholder.universe], | |
691 | ..placeholder | |
692 | }) | |
693 | } | |
064997fb FG |
694 | CanonicalVarKind::PlaceholderConst(placeholder, t) => { |
695 | CanonicalVarKind::PlaceholderConst( | |
696 | ty::Placeholder { | |
697 | universe: reverse_universe_map[&placeholder.universe], | |
698 | ..placeholder | |
699 | }, | |
700 | t, | |
701 | ) | |
5099ac24 FG |
702 | } |
703 | }, | |
704 | }) | |
705 | .collect() | |
706 | } | |
707 | ||
a1dfa0c6 XL |
708 | /// Shorthand helper that creates a canonical region variable for |
709 | /// `r` (always in the root universe). The reason that we always | |
710 | /// put these variables into the root universe is because this | |
711 | /// method is used during **query construction:** in that case, we | |
712 | /// are taking all the regions and just putting them into the most | |
713 | /// generic context we can. This may generate solutions that don't | |
714 | /// fit (e.g., that equate some region variable with a placeholder | |
715 | /// it can't name) on the caller side, but that's ok, the caller | |
716 | /// can figure that out. In the meantime, it maximizes our | |
717 | /// caching. | |
718 | /// | |
719 | /// (This works because unification never fails -- and hence trait | |
720 | /// selection is never affected -- due to a universe mismatch.) | |
721 | fn canonical_var_for_region_in_root_universe( | |
722 | &mut self, | |
723 | r: ty::Region<'tcx>, | |
724 | ) -> ty::Region<'tcx> { | |
725 | self.canonical_var_for_region( | |
dfeec247 | 726 | CanonicalVarInfo { kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT) }, |
a1dfa0c6 XL |
727 | r, |
728 | ) | |
729 | } | |
730 | ||
731 | /// Returns the universe in which `vid` is defined. | |
732 | fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex { | |
136023e0 | 733 | self.infcx.inner.borrow_mut().unwrap_region_constraints().var_universe(vid) |
a1dfa0c6 XL |
734 | } |
735 | ||
9fa01778 | 736 | /// Creates a canonical variable (with the given `info`) |
a1dfa0c6 XL |
737 | /// representing the region `r`; return a region referencing it. |
738 | fn canonical_var_for_region( | |
739 | &mut self, | |
fc512014 | 740 | info: CanonicalVarInfo<'tcx>, |
a1dfa0c6 XL |
741 | r: ty::Region<'tcx>, |
742 | ) -> ty::Region<'tcx> { | |
743 | let var = self.canonical_var(info, r.into()); | |
487cf647 | 744 | let br = ty::BoundRegion { var, kind: ty::BrAnon(var.as_u32(), None) }; |
9ffffee4 | 745 | self.interner().mk_re_late_bound(self.binder_index, br) |
0bf4aa26 XL |
746 | } |
747 | ||
8faf50e0 XL |
748 | /// Given a type variable `ty_var` of the given kind, first check |
749 | /// if `ty_var` is bound to anything; if so, canonicalize | |
750 | /// *that*. Otherwise, create a new canonical variable for | |
751 | /// `ty_var`. | |
fc512014 | 752 | fn canonicalize_ty_var(&mut self, info: CanonicalVarInfo<'tcx>, ty_var: Ty<'tcx>) -> Ty<'tcx> { |
136023e0 | 753 | let infcx = self.infcx; |
8faf50e0 XL |
754 | let bound_to = infcx.shallow_resolve(ty_var); |
755 | if bound_to != ty_var { | |
756 | self.fold_ty(bound_to) | |
757 | } else { | |
a1dfa0c6 | 758 | let var = self.canonical_var(info, ty_var.into()); |
9ffffee4 | 759 | self.interner().mk_bound(self.binder_index, var.into()) |
8faf50e0 XL |
760 | } |
761 | } | |
48663c56 XL |
762 | |
763 | /// Given a type variable `const_var` of the given kind, first check | |
764 | /// if `const_var` is bound to anything; if so, canonicalize | |
765 | /// *that*. Otherwise, create a new canonical variable for | |
766 | /// `const_var`. | |
767 | fn canonicalize_const_var( | |
768 | &mut self, | |
fc512014 | 769 | info: CanonicalVarInfo<'tcx>, |
5099ac24 FG |
770 | const_var: ty::Const<'tcx>, |
771 | ) -> ty::Const<'tcx> { | |
136023e0 | 772 | let infcx = self.infcx; |
416331ca | 773 | let bound_to = infcx.shallow_resolve(const_var); |
48663c56 XL |
774 | if bound_to != const_var { |
775 | self.fold_const(bound_to) | |
776 | } else { | |
777 | let var = self.canonical_var(info, const_var.into()); | |
9ffffee4 | 778 | self.interner().mk_const( |
487cf647 FG |
779 | ty::ConstKind::Bound(self.binder_index, var), |
780 | self.fold_ty(const_var.ty()), | |
781 | ) | |
48663c56 XL |
782 | } |
783 | } | |
8faf50e0 | 784 | } |