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