]>
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 | |
2b03887a | 23 | impl<'tcx> InferCtxt<'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 { |
f2b60f7d | 183 | ty::ReFree(_) | ty::ReErased | ty::ReStatic | ty::ReEarlyBound(..) => r, |
74b04a01 | 184 | |
a1dfa0c6 | 185 | ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region( |
5099ac24 | 186 | CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderRegion(placeholder) }, |
a1dfa0c6 XL |
187 | r, |
188 | ), | |
74b04a01 | 189 | |
a1dfa0c6 | 190 | ty::ReVar(vid) => { |
5099ac24 | 191 | let universe = canonicalizer.region_var_universe(vid); |
a1dfa0c6 | 192 | canonicalizer.canonical_var_for_region( |
dfeec247 | 193 | CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) }, |
a1dfa0c6 XL |
194 | r, |
195 | ) | |
196 | } | |
74b04a01 | 197 | |
0bf4aa26 XL |
198 | _ => { |
199 | // Other than `'static` or `'empty`, the query | |
200 | // response should be executing in a fully | |
201 | // canonicalized environment, so there shouldn't be | |
202 | // any other region names it can come up. | |
0731742a XL |
203 | // |
204 | // rust-lang/rust#57464: `impl Trait` can leak local | |
205 | // scopes (in manner violating typeck). Therefore, use | |
206 | // `delay_span_bug` to allow type error over an ICE. | |
3dfed10e XL |
207 | ty::tls::with(|tcx| { |
208 | tcx.sess.delay_span_bug( | |
dfeec247 XL |
209 | rustc_span::DUMMY_SP, |
210 | &format!("unexpected region in query response: `{:?}`", r), | |
211 | ); | |
0731742a XL |
212 | }); |
213 | r | |
0bf4aa26 XL |
214 | } |
215 | } | |
216 | } | |
217 | ||
8faf50e0 | 218 | fn any(&self) -> bool { |
0bf4aa26 XL |
219 | false |
220 | } | |
5099ac24 FG |
221 | |
222 | fn preserve_universes(&self) -> bool { | |
223 | true | |
224 | } | |
0bf4aa26 XL |
225 | } |
226 | ||
a1dfa0c6 XL |
227 | struct CanonicalizeUserTypeAnnotation; |
228 | ||
5099ac24 | 229 | impl CanonicalizeMode for CanonicalizeUserTypeAnnotation { |
a2a8927a | 230 | fn canonicalize_free_region<'tcx>( |
a1dfa0c6 | 231 | &self, |
dc9dc135 | 232 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, |
a1dfa0c6 XL |
233 | r: ty::Region<'tcx>, |
234 | ) -> ty::Region<'tcx> { | |
5099ac24 | 235 | match *r { |
74b04a01 | 236 | ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReStatic => r, |
a1dfa0c6 XL |
237 | ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r), |
238 | _ => { | |
239 | // We only expect region names that the user can type. | |
240 | bug!("unexpected region in query response: `{:?}`", r) | |
241 | } | |
242 | } | |
243 | } | |
244 | ||
245 | fn any(&self) -> bool { | |
246 | false | |
247 | } | |
5099ac24 FG |
248 | |
249 | fn preserve_universes(&self) -> bool { | |
250 | false | |
251 | } | |
a1dfa0c6 XL |
252 | } |
253 | ||
0bf4aa26 XL |
254 | struct CanonicalizeAllFreeRegions; |
255 | ||
5099ac24 | 256 | impl CanonicalizeMode for CanonicalizeAllFreeRegions { |
a2a8927a | 257 | fn canonicalize_free_region<'tcx>( |
0bf4aa26 | 258 | &self, |
dc9dc135 | 259 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, |
0bf4aa26 XL |
260 | r: ty::Region<'tcx>, |
261 | ) -> ty::Region<'tcx> { | |
a1dfa0c6 | 262 | canonicalizer.canonical_var_for_region_in_root_universe(r) |
0bf4aa26 XL |
263 | } |
264 | ||
265 | fn any(&self) -> bool { | |
266 | true | |
267 | } | |
5099ac24 FG |
268 | |
269 | fn preserve_universes(&self) -> bool { | |
270 | false | |
271 | } | |
272 | } | |
273 | ||
274 | struct CanonicalizeAllFreeRegionsPreservingUniverses; | |
275 | ||
276 | impl CanonicalizeMode for CanonicalizeAllFreeRegionsPreservingUniverses { | |
277 | fn canonicalize_free_region<'tcx>( | |
278 | &self, | |
279 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, | |
280 | r: ty::Region<'tcx>, | |
281 | ) -> ty::Region<'tcx> { | |
282 | let universe = canonicalizer.infcx.universe_of_region(r); | |
283 | canonicalizer.canonical_var_for_region( | |
284 | CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) }, | |
285 | r, | |
286 | ) | |
287 | } | |
288 | ||
289 | fn any(&self) -> bool { | |
290 | true | |
291 | } | |
292 | ||
293 | fn preserve_universes(&self) -> bool { | |
294 | true | |
295 | } | |
0bf4aa26 XL |
296 | } |
297 | ||
298 | struct CanonicalizeFreeRegionsOtherThanStatic; | |
299 | ||
5099ac24 | 300 | impl CanonicalizeMode for CanonicalizeFreeRegionsOtherThanStatic { |
a2a8927a | 301 | fn canonicalize_free_region<'tcx>( |
0bf4aa26 | 302 | &self, |
dc9dc135 | 303 | canonicalizer: &mut Canonicalizer<'_, 'tcx>, |
0bf4aa26 XL |
304 | r: ty::Region<'tcx>, |
305 | ) -> ty::Region<'tcx> { | |
5099ac24 | 306 | if r.is_static() { r } else { canonicalizer.canonical_var_for_region_in_root_universe(r) } |
0bf4aa26 XL |
307 | } |
308 | ||
309 | fn any(&self) -> bool { | |
310 | true | |
8faf50e0 | 311 | } |
5099ac24 FG |
312 | |
313 | fn preserve_universes(&self) -> bool { | |
314 | false | |
315 | } | |
8faf50e0 XL |
316 | } |
317 | ||
dc9dc135 | 318 | struct Canonicalizer<'cx, 'tcx> { |
2b03887a | 319 | infcx: &'cx InferCtxt<'tcx>, |
dc9dc135 | 320 | tcx: TyCtxt<'tcx>, |
fc512014 | 321 | variables: SmallVec<[CanonicalVarInfo<'tcx>; 8]>, |
0bf4aa26 | 322 | query_state: &'cx mut OriginalQueryValues<'tcx>, |
8faf50e0 XL |
323 | // Note that indices is only used once `var_values` is big enough to be |
324 | // heap-allocated. | |
e74abb32 | 325 | indices: FxHashMap<GenericArg<'tcx>, BoundVar>, |
5099ac24 | 326 | canonicalize_mode: &'cx dyn CanonicalizeMode, |
8faf50e0 | 327 | needs_canonical_flags: TypeFlags, |
a1dfa0c6 XL |
328 | |
329 | binder_index: ty::DebruijnIndex, | |
8faf50e0 XL |
330 | } |
331 | ||
dc9dc135 XL |
332 | impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> { |
333 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { | |
8faf50e0 XL |
334 | self.tcx |
335 | } | |
336 | ||
cdc7bbd5 | 337 | fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T> |
dfeec247 XL |
338 | where |
339 | T: TypeFoldable<'tcx>, | |
a1dfa0c6 XL |
340 | { |
341 | self.binder_index.shift_in(1); | |
342 | let t = t.super_fold_with(self); | |
343 | self.binder_index.shift_out(1); | |
344 | t | |
345 | } | |
346 | ||
8faf50e0 XL |
347 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
348 | match *r { | |
a1dfa0c6 XL |
349 | ty::ReLateBound(index, ..) => { |
350 | if index >= self.binder_index { | |
60c5eb7d | 351 | bug!("escaping late-bound region during canonicalization"); |
a1dfa0c6 XL |
352 | } else { |
353 | r | |
354 | } | |
8faf50e0 XL |
355 | } |
356 | ||
357 | ty::ReVar(vid) => { | |
f035d41b | 358 | let resolved_vid = self |
dfeec247 | 359 | .infcx |
74b04a01 XL |
360 | .inner |
361 | .borrow_mut() | |
362 | .unwrap_region_constraints() | |
f035d41b | 363 | .opportunistic_resolve_var(vid); |
8faf50e0 XL |
364 | debug!( |
365 | "canonical: region var found with vid {:?}, \ | |
366 | opportunistically resolved to {:?}", | |
f2b60f7d | 367 | vid, resolved_vid |
8faf50e0 | 368 | ); |
f035d41b | 369 | let r = self.tcx.reuse_or_mk_region(r, ty::ReVar(resolved_vid)); |
5099ac24 | 370 | self.canonicalize_mode.canonicalize_free_region(self, r) |
8faf50e0 XL |
371 | } |
372 | ||
0bf4aa26 XL |
373 | ty::ReStatic |
374 | | ty::ReEarlyBound(..) | |
8faf50e0 | 375 | | ty::ReFree(_) |
0bf4aa26 | 376 | | ty::RePlaceholder(..) |
5099ac24 | 377 | | ty::ReErased => self.canonicalize_mode.canonicalize_free_region(self, r), |
8faf50e0 XL |
378 | } |
379 | } | |
380 | ||
381 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
1b1a35ee | 382 | match *t.kind() { |
a1dfa0c6 | 383 | ty::Infer(ty::TyVar(vid)) => { |
0731742a | 384 | debug!("canonical: type var found with vid {:?}", vid); |
136023e0 | 385 | match self.infcx.probe_ty_var(vid) { |
60c5eb7d | 386 | // `t` could be a float / int variable; canonicalize that instead. |
0731742a XL |
387 | Ok(t) => { |
388 | debug!("(resolved to {:?})", t); | |
389 | self.fold_ty(t) | |
390 | } | |
a1dfa0c6 XL |
391 | |
392 | // `TyVar(vid)` is unresolved, track its universe index in the canonicalized | |
60c5eb7d | 393 | // result. |
a1dfa0c6 | 394 | Err(mut ui) => { |
5099ac24 FG |
395 | if !self.canonicalize_mode.preserve_universes() { |
396 | // FIXME: perf problem described in #55921. | |
397 | ui = ty::UniverseIndex::ROOT; | |
398 | } | |
a1dfa0c6 XL |
399 | self.canonicalize_ty_var( |
400 | CanonicalVarInfo { | |
dfeec247 | 401 | kind: CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)), |
a1dfa0c6 | 402 | }, |
dfeec247 | 403 | t, |
a1dfa0c6 XL |
404 | ) |
405 | } | |
406 | } | |
407 | } | |
8faf50e0 | 408 | |
a1dfa0c6 | 409 | ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var( |
dfeec247 XL |
410 | CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Int) }, |
411 | t, | |
a1dfa0c6 | 412 | ), |
8faf50e0 | 413 | |
a1dfa0c6 | 414 | ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var( |
dfeec247 XL |
415 | CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Float) }, |
416 | t, | |
a1dfa0c6 | 417 | ), |
8faf50e0 | 418 | |
ba9703b0 | 419 | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { |
8faf50e0 XL |
420 | bug!("encountered a fresh type during canonicalization") |
421 | } | |
422 | ||
a1dfa0c6 | 423 | ty::Placeholder(placeholder) => self.canonicalize_ty_var( |
dfeec247 XL |
424 | CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderTy(placeholder) }, |
425 | t, | |
a1dfa0c6 XL |
426 | ), |
427 | ||
428 | ty::Bound(debruijn, _) => { | |
429 | if debruijn >= self.binder_index { | |
430 | bug!("escaping bound type during canonicalization") | |
431 | } else { | |
432 | t | |
433 | } | |
8faf50e0 XL |
434 | } |
435 | ||
b7449926 XL |
436 | ty::Closure(..) |
437 | | ty::Generator(..) | |
438 | | ty::GeneratorWitness(..) | |
439 | | ty::Bool | |
440 | | ty::Char | |
441 | | ty::Int(..) | |
442 | | ty::Uint(..) | |
443 | | ty::Float(..) | |
444 | | ty::Adt(..) | |
445 | | ty::Str | |
f035d41b | 446 | | ty::Error(_) |
b7449926 XL |
447 | | ty::Array(..) |
448 | | ty::Slice(..) | |
449 | | ty::RawPtr(..) | |
450 | | ty::Ref(..) | |
451 | | ty::FnDef(..) | |
452 | | ty::FnPtr(_) | |
453 | | ty::Dynamic(..) | |
454 | | ty::Never | |
455 | | ty::Tuple(..) | |
456 | | ty::Projection(..) | |
457 | | ty::Foreign(..) | |
458 | | ty::Param(..) | |
459 | | ty::Opaque(..) => { | |
1b1a35ee | 460 | if t.flags().intersects(self.needs_canonical_flags) { |
8faf50e0 XL |
461 | t.super_fold_with(self) |
462 | } else { | |
463 | t | |
464 | } | |
465 | } | |
466 | } | |
467 | } | |
48663c56 | 468 | |
5099ac24 | 469 | fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { |
923072b8 | 470 | match ct.kind() { |
60c5eb7d | 471 | ty::ConstKind::Infer(InferConst::Var(vid)) => { |
48663c56 | 472 | debug!("canonical: const var found with vid {:?}", vid); |
136023e0 | 473 | match self.infcx.probe_const_var(vid) { |
48663c56 XL |
474 | Ok(c) => { |
475 | debug!("(resolved to {:?})", c); | |
476 | return self.fold_const(c); | |
477 | } | |
478 | ||
479 | // `ConstVar(vid)` is unresolved, track its universe index in the | |
480 | // canonicalized result | |
481 | Err(mut ui) => { | |
5099ac24 FG |
482 | if !self.canonicalize_mode.preserve_universes() { |
483 | // FIXME: perf problem described in #55921. | |
484 | ui = ty::UniverseIndex::ROOT; | |
485 | } | |
48663c56 | 486 | return self.canonicalize_const_var( |
5099ac24 | 487 | CanonicalVarInfo { kind: CanonicalVarKind::Const(ui, ct.ty()) }, |
48663c56 XL |
488 | ct, |
489 | ); | |
490 | } | |
491 | } | |
492 | } | |
60c5eb7d | 493 | ty::ConstKind::Infer(InferConst::Fresh(_)) => { |
48663c56 XL |
494 | bug!("encountered a fresh const during canonicalization") |
495 | } | |
60c5eb7d | 496 | ty::ConstKind::Bound(debruijn, _) => { |
48663c56 | 497 | if debruijn >= self.binder_index { |
487cf647 | 498 | bug!("escaping bound const during canonicalization") |
48663c56 XL |
499 | } else { |
500 | return ct; | |
501 | } | |
502 | } | |
60c5eb7d | 503 | ty::ConstKind::Placeholder(placeholder) => { |
48663c56 | 504 | return self.canonicalize_const_var( |
064997fb FG |
505 | CanonicalVarInfo { |
506 | kind: CanonicalVarKind::PlaceholderConst(placeholder, ct.ty()), | |
507 | }, | |
48663c56 XL |
508 | ct, |
509 | ); | |
510 | } | |
511 | _ => {} | |
512 | } | |
513 | ||
514 | let flags = FlagComputation::for_const(ct); | |
dfeec247 | 515 | if flags.intersects(self.needs_canonical_flags) { ct.super_fold_with(self) } else { ct } |
48663c56 | 516 | } |
8faf50e0 XL |
517 | } |
518 | ||
dc9dc135 | 519 | impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> { |
8faf50e0 XL |
520 | /// The main `canonicalize` method, shared impl of |
521 | /// `canonicalize_query` and `canonicalize_response`. | |
522 | fn canonicalize<V>( | |
fc512014 | 523 | value: V, |
2b03887a | 524 | infcx: &InferCtxt<'tcx>, |
dc9dc135 | 525 | tcx: TyCtxt<'tcx>, |
5099ac24 | 526 | canonicalize_region_mode: &dyn CanonicalizeMode, |
0bf4aa26 | 527 | query_state: &mut OriginalQueryValues<'tcx>, |
dc9dc135 | 528 | ) -> Canonicalized<'tcx, V> |
8faf50e0 | 529 | where |
dc9dc135 | 530 | V: TypeFoldable<'tcx>, |
8faf50e0 | 531 | { |
8faf50e0 | 532 | let needs_canonical_flags = if canonicalize_region_mode.any() { |
ba9703b0 | 533 | TypeFlags::NEEDS_INFER | |
5099ac24 | 534 | TypeFlags::HAS_FREE_REGIONS | // `HAS_RE_PLACEHOLDER` implies `HAS_FREE_REGIONS` |
48663c56 XL |
535 | TypeFlags::HAS_TY_PLACEHOLDER | |
536 | TypeFlags::HAS_CT_PLACEHOLDER | |
8faf50e0 | 537 | } else { |
ba9703b0 | 538 | TypeFlags::NEEDS_INFER |
dfeec247 XL |
539 | | TypeFlags::HAS_RE_PLACEHOLDER |
540 | | TypeFlags::HAS_TY_PLACEHOLDER | |
541 | | TypeFlags::HAS_CT_PLACEHOLDER | |
8faf50e0 XL |
542 | }; |
543 | ||
8faf50e0 XL |
544 | // Fast path: nothing that needs to be canonicalized. |
545 | if !value.has_type_flags(needs_canonical_flags) { | |
8faf50e0 | 546 | let canon_value = Canonical { |
a1dfa0c6 | 547 | max_universe: ty::UniverseIndex::ROOT, |
b7449926 | 548 | variables: List::empty(), |
fc512014 | 549 | value, |
8faf50e0 XL |
550 | }; |
551 | return canon_value; | |
552 | } | |
553 | ||
554 | let mut canonicalizer = Canonicalizer { | |
555 | infcx, | |
556 | tcx, | |
5099ac24 | 557 | canonicalize_mode: canonicalize_region_mode, |
8faf50e0 XL |
558 | needs_canonical_flags, |
559 | variables: SmallVec::new(), | |
0bf4aa26 | 560 | query_state, |
8faf50e0 | 561 | indices: FxHashMap::default(), |
a1dfa0c6 | 562 | binder_index: ty::INNERMOST, |
8faf50e0 XL |
563 | }; |
564 | let out_value = value.fold_with(&mut canonicalizer); | |
565 | ||
566 | // Once we have canonicalized `out_value`, it should not | |
567 | // contain anything that ties it to this inference context | |
5099ac24 FG |
568 | // anymore. |
569 | debug_assert!(!out_value.needs_infer() && !out_value.has_placeholders()); | |
8faf50e0 | 570 | |
5099ac24 FG |
571 | let canonical_variables = |
572 | tcx.intern_canonical_var_infos(&canonicalizer.universe_canonicalized_variables()); | |
8faf50e0 | 573 | |
a1dfa0c6 XL |
574 | let max_universe = canonical_variables |
575 | .iter() | |
576 | .map(|cvar| cvar.universe()) | |
577 | .max() | |
578 | .unwrap_or(ty::UniverseIndex::ROOT); | |
579 | ||
dfeec247 | 580 | Canonical { max_universe, variables: canonical_variables, value: out_value } |
8faf50e0 XL |
581 | } |
582 | ||
583 | /// Creates a canonical variable replacing `kind` from the input, | |
584 | /// or returns an existing variable if `kind` has already been | |
585 | /// seen. `kind` is expected to be an unbound variable (or | |
586 | /// potentially a free region). | |
fc512014 | 587 | fn canonical_var(&mut self, info: CanonicalVarInfo<'tcx>, kind: GenericArg<'tcx>) -> BoundVar { |
dfeec247 | 588 | let Canonicalizer { variables, query_state, indices, .. } = self; |
8faf50e0 | 589 | |
0bf4aa26 XL |
590 | let var_values = &mut query_state.var_values; |
591 | ||
5099ac24 FG |
592 | let universe = info.universe(); |
593 | if universe != ty::UniverseIndex::ROOT { | |
594 | assert!(self.canonicalize_mode.preserve_universes()); | |
595 | ||
596 | // Insert universe into the universe map. To preserve the order of the | |
597 | // universes in the value being canonicalized, we don't update the | |
598 | // universe in `info` until we have finished canonicalizing. | |
599 | match query_state.universe_map.binary_search(&universe) { | |
600 | Err(idx) => query_state.universe_map.insert(idx, universe), | |
601 | Ok(_) => {} | |
602 | } | |
603 | } | |
604 | ||
8faf50e0 XL |
605 | // This code is hot. `variables` and `var_values` are usually small |
606 | // (fewer than 8 elements ~95% of the time). They are SmallVec's to | |
607 | // avoid allocations in those cases. We also don't use `indices` to | |
608 | // determine if a kind has been seen before until the limit of 8 has | |
609 | // been exceeded, to also avoid allocations for `indices`. | |
ba9703b0 | 610 | if !var_values.spilled() { |
8faf50e0 XL |
611 | // `var_values` is stack-allocated. `indices` isn't used yet. Do a |
612 | // direct linear search of `var_values`. | |
613 | if let Some(idx) = var_values.iter().position(|&k| k == kind) { | |
614 | // `kind` is already present in `var_values`. | |
a1dfa0c6 | 615 | BoundVar::new(idx) |
8faf50e0 XL |
616 | } else { |
617 | // `kind` isn't present in `var_values`. Append it. Likewise | |
618 | // for `info` and `variables`. | |
619 | variables.push(info); | |
620 | var_values.push(kind); | |
621 | assert_eq!(variables.len(), var_values.len()); | |
622 | ||
623 | // If `var_values` has become big enough to be heap-allocated, | |
624 | // fill up `indices` to facilitate subsequent lookups. | |
b7449926 | 625 | if var_values.spilled() { |
8faf50e0 | 626 | assert!(indices.is_empty()); |
0bf4aa26 XL |
627 | *indices = var_values |
628 | .iter() | |
629 | .enumerate() | |
a1dfa0c6 | 630 | .map(|(i, &kind)| (kind, BoundVar::new(i))) |
0bf4aa26 | 631 | .collect(); |
8faf50e0 XL |
632 | } |
633 | // The cv is the index of the appended element. | |
a1dfa0c6 | 634 | BoundVar::new(var_values.len() - 1) |
8faf50e0 XL |
635 | } |
636 | } else { | |
637 | // `var_values` is large. Do a hashmap search via `indices`. | |
0bf4aa26 XL |
638 | *indices.entry(kind).or_insert_with(|| { |
639 | variables.push(info); | |
640 | var_values.push(kind); | |
641 | assert_eq!(variables.len(), var_values.len()); | |
a1dfa0c6 | 642 | BoundVar::new(variables.len() - 1) |
0bf4aa26 | 643 | }) |
ba9703b0 | 644 | } |
8faf50e0 XL |
645 | } |
646 | ||
5099ac24 FG |
647 | /// Replaces the universe indexes used in `var_values` with their index in |
648 | /// `query_state.universe_map`. This minimizes the maximum universe used in | |
649 | /// the canonicalized value. | |
650 | fn universe_canonicalized_variables(self) -> SmallVec<[CanonicalVarInfo<'tcx>; 8]> { | |
651 | if self.query_state.universe_map.len() == 1 { | |
652 | return self.variables; | |
653 | } | |
654 | ||
655 | let reverse_universe_map: FxHashMap<ty::UniverseIndex, ty::UniverseIndex> = self | |
656 | .query_state | |
657 | .universe_map | |
658 | .iter() | |
659 | .enumerate() | |
660 | .map(|(idx, universe)| (*universe, ty::UniverseIndex::from_usize(idx))) | |
661 | .collect(); | |
662 | ||
663 | self.variables | |
664 | .iter() | |
665 | .map(|v| CanonicalVarInfo { | |
666 | kind: match v.kind { | |
667 | CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => { | |
668 | return *v; | |
669 | } | |
670 | CanonicalVarKind::Ty(CanonicalTyVarKind::General(u)) => { | |
671 | CanonicalVarKind::Ty(CanonicalTyVarKind::General(reverse_universe_map[&u])) | |
672 | } | |
673 | CanonicalVarKind::Region(u) => { | |
674 | CanonicalVarKind::Region(reverse_universe_map[&u]) | |
675 | } | |
676 | CanonicalVarKind::Const(u, t) => { | |
677 | CanonicalVarKind::Const(reverse_universe_map[&u], t) | |
678 | } | |
679 | CanonicalVarKind::PlaceholderTy(placeholder) => { | |
680 | CanonicalVarKind::PlaceholderTy(ty::Placeholder { | |
681 | universe: reverse_universe_map[&placeholder.universe], | |
682 | ..placeholder | |
683 | }) | |
684 | } | |
685 | CanonicalVarKind::PlaceholderRegion(placeholder) => { | |
686 | CanonicalVarKind::PlaceholderRegion(ty::Placeholder { | |
687 | universe: reverse_universe_map[&placeholder.universe], | |
688 | ..placeholder | |
689 | }) | |
690 | } | |
064997fb FG |
691 | CanonicalVarKind::PlaceholderConst(placeholder, t) => { |
692 | CanonicalVarKind::PlaceholderConst( | |
693 | ty::Placeholder { | |
694 | universe: reverse_universe_map[&placeholder.universe], | |
695 | ..placeholder | |
696 | }, | |
697 | t, | |
698 | ) | |
5099ac24 FG |
699 | } |
700 | }, | |
701 | }) | |
702 | .collect() | |
703 | } | |
704 | ||
a1dfa0c6 XL |
705 | /// Shorthand helper that creates a canonical region variable for |
706 | /// `r` (always in the root universe). The reason that we always | |
707 | /// put these variables into the root universe is because this | |
708 | /// method is used during **query construction:** in that case, we | |
709 | /// are taking all the regions and just putting them into the most | |
710 | /// generic context we can. This may generate solutions that don't | |
711 | /// fit (e.g., that equate some region variable with a placeholder | |
712 | /// it can't name) on the caller side, but that's ok, the caller | |
713 | /// can figure that out. In the meantime, it maximizes our | |
714 | /// caching. | |
715 | /// | |
716 | /// (This works because unification never fails -- and hence trait | |
717 | /// selection is never affected -- due to a universe mismatch.) | |
718 | fn canonical_var_for_region_in_root_universe( | |
719 | &mut self, | |
720 | r: ty::Region<'tcx>, | |
721 | ) -> ty::Region<'tcx> { | |
722 | self.canonical_var_for_region( | |
dfeec247 | 723 | CanonicalVarInfo { kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT) }, |
a1dfa0c6 XL |
724 | r, |
725 | ) | |
726 | } | |
727 | ||
728 | /// Returns the universe in which `vid` is defined. | |
729 | fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex { | |
136023e0 | 730 | self.infcx.inner.borrow_mut().unwrap_region_constraints().var_universe(vid) |
a1dfa0c6 XL |
731 | } |
732 | ||
9fa01778 | 733 | /// Creates a canonical variable (with the given `info`) |
a1dfa0c6 XL |
734 | /// representing the region `r`; return a region referencing it. |
735 | fn canonical_var_for_region( | |
736 | &mut self, | |
fc512014 | 737 | info: CanonicalVarInfo<'tcx>, |
a1dfa0c6 XL |
738 | r: ty::Region<'tcx>, |
739 | ) -> ty::Region<'tcx> { | |
740 | let var = self.canonical_var(info, r.into()); | |
487cf647 | 741 | let br = ty::BoundRegion { var, kind: ty::BrAnon(var.as_u32(), None) }; |
fc512014 | 742 | let region = ty::ReLateBound(self.binder_index, br); |
a1dfa0c6 | 743 | self.tcx().mk_region(region) |
0bf4aa26 XL |
744 | } |
745 | ||
8faf50e0 XL |
746 | /// Given a type variable `ty_var` of the given kind, first check |
747 | /// if `ty_var` is bound to anything; if so, canonicalize | |
748 | /// *that*. Otherwise, create a new canonical variable for | |
749 | /// `ty_var`. | |
fc512014 | 750 | fn canonicalize_ty_var(&mut self, info: CanonicalVarInfo<'tcx>, ty_var: Ty<'tcx>) -> Ty<'tcx> { |
136023e0 | 751 | let infcx = self.infcx; |
8faf50e0 XL |
752 | let bound_to = infcx.shallow_resolve(ty_var); |
753 | if bound_to != ty_var { | |
754 | self.fold_ty(bound_to) | |
755 | } else { | |
a1dfa0c6 XL |
756 | let var = self.canonical_var(info, ty_var.into()); |
757 | self.tcx().mk_ty(ty::Bound(self.binder_index, var.into())) | |
8faf50e0 XL |
758 | } |
759 | } | |
48663c56 XL |
760 | |
761 | /// Given a type variable `const_var` of the given kind, first check | |
762 | /// if `const_var` is bound to anything; if so, canonicalize | |
763 | /// *that*. Otherwise, create a new canonical variable for | |
764 | /// `const_var`. | |
765 | fn canonicalize_const_var( | |
766 | &mut self, | |
fc512014 | 767 | info: CanonicalVarInfo<'tcx>, |
5099ac24 FG |
768 | const_var: ty::Const<'tcx>, |
769 | ) -> ty::Const<'tcx> { | |
136023e0 | 770 | let infcx = self.infcx; |
416331ca | 771 | let bound_to = infcx.shallow_resolve(const_var); |
48663c56 XL |
772 | if bound_to != const_var { |
773 | self.fold_const(bound_to) | |
774 | } else { | |
775 | let var = self.canonical_var(info, const_var.into()); | |
487cf647 FG |
776 | self.tcx().mk_const( |
777 | ty::ConstKind::Bound(self.binder_index, var), | |
778 | self.fold_ty(const_var.ty()), | |
779 | ) | |
48663c56 XL |
780 | } |
781 | } | |
8faf50e0 | 782 | } |