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