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