rustc_infer/infer/canonical/
canonicalizer.rs

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

rustc_infer/infer/canonical/
canonicalizer.rs
