rustc_infer/infer/canonical/
canonicalizer.rs

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

rustc_infer/infer/canonical/
canonicalizer.rs
