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_data_structures::sso::SsoHashMap;
10use rustc_index::Idx;
11use rustc_middle::bug;
12use rustc_middle::ty::{
13    self, BoundVar, GenericArg, InferConst, List, Ty, TyCtxt, TypeFlags, TypeFoldable, TypeFolder,
14    TypeSuperFoldable, TypeVisitableExt,
15};
16use smallvec::SmallVec;
17use tracing::debug;
18
19use crate::infer::InferCtxt;
20use crate::infer::canonical::{
21    Canonical, CanonicalQueryInput, CanonicalVarKind, 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 ty::ParamEnvAnd { param_env, value } = value;
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.kind() {
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.kind() {
175            ty::ReLateParam(_) | ty::ReErased | ty::ReStatic | ty::ReEarlyParam(..) => r,
176
177            ty::RePlaceholder(placeholder) => canonicalizer
178                .canonical_var_for_region(CanonicalVarKind::PlaceholderRegion(placeholder), r),
179
180            ty::ReVar(vid) => {
181                let universe = infcx
182                    .inner
183                    .borrow_mut()
184                    .unwrap_region_constraints()
185                    .probe_value(vid)
186                    .unwrap_err();
187                canonicalizer.canonical_var_for_region(CanonicalVarKind::Region(universe), r)
188            }
189
190            _ => {
191                // Other than `'static` or `'empty`, the query
192                // response should be executing in a fully
193                // canonicalized environment, so there shouldn't be
194                // any other region names it can come up.
195                //
196                // rust-lang/rust#57464: `impl Trait` can leak local
197                // scopes (in manner violating typeck). Therefore, use
198                // `delayed_bug` to allow type error over an ICE.
199                canonicalizer
200                    .tcx
201                    .dcx()
202                    .delayed_bug(format!("unexpected region in query response: `{r:?}`"));
203                r
204            }
205        }
206    }
207
208    fn any(&self) -> bool {
209        false
210    }
211
212    fn preserve_universes(&self) -> bool {
213        true
214    }
215}
216
217struct CanonicalizeUserTypeAnnotation;
218
219impl CanonicalizeMode for CanonicalizeUserTypeAnnotation {
220    fn canonicalize_free_region<'tcx>(
221        &self,
222        canonicalizer: &mut Canonicalizer<'_, 'tcx>,
223        r: ty::Region<'tcx>,
224    ) -> ty::Region<'tcx> {
225        match r.kind() {
226            ty::ReEarlyParam(_)
227            | ty::ReLateParam(_)
228            | ty::ReErased
229            | ty::ReStatic
230            | ty::ReError(_) => r,
231            ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r),
232            ty::RePlaceholder(..) | ty::ReBound(..) => {
233                // We only expect region names that the user can type.
234                bug!("unexpected region in query response: `{:?}`", r)
235            }
236        }
237    }
238
239    fn any(&self) -> bool {
240        false
241    }
242
243    fn preserve_universes(&self) -> bool {
244        false
245    }
246}
247
248struct CanonicalizeAllFreeRegions;
249
250impl CanonicalizeMode for CanonicalizeAllFreeRegions {
251    fn canonicalize_free_region<'tcx>(
252        &self,
253        canonicalizer: &mut Canonicalizer<'_, 'tcx>,
254        r: ty::Region<'tcx>,
255    ) -> ty::Region<'tcx> {
256        canonicalizer.canonical_var_for_region_in_root_universe(r)
257    }
258
259    fn any(&self) -> bool {
260        true
261    }
262
263    fn preserve_universes(&self) -> bool {
264        false
265    }
266}
267
268struct CanonicalizeFreeRegionsOtherThanStatic;
269
270impl CanonicalizeMode for CanonicalizeFreeRegionsOtherThanStatic {
271    fn canonicalize_free_region<'tcx>(
272        &self,
273        canonicalizer: &mut Canonicalizer<'_, 'tcx>,
274        r: ty::Region<'tcx>,
275    ) -> ty::Region<'tcx> {
276        if r.is_static() { r } else { canonicalizer.canonical_var_for_region_in_root_universe(r) }
277    }
278
279    fn any(&self) -> bool {
280        true
281    }
282
283    fn preserve_universes(&self) -> bool {
284        false
285    }
286}
287
288struct Canonicalizer<'cx, 'tcx> {
289    /// Set to `None` to disable the resolution of inference variables.
290    infcx: Option<&'cx InferCtxt<'tcx>>,
291    tcx: TyCtxt<'tcx>,
292    variables: SmallVec<[CanonicalVarKind<'tcx>; 8]>,
293    query_state: &'cx mut OriginalQueryValues<'tcx>,
294    // Note that indices is only used once `var_values` is big enough to be
295    // heap-allocated.
296    indices: FxHashMap<GenericArg<'tcx>, BoundVar>,
297    /// Maps each `sub_unification_table_root_var` to the index of the first
298    /// variable which used it.
299    ///
300    /// This means in case two type variables have the same sub relations root,
301    /// we set the `sub_root` of the second variable to the position of the first.
302    /// Otherwise the `sub_root` of each type variable is just its own position.
303    sub_root_lookup_table: SsoHashMap<ty::TyVid, usize>,
304    canonicalize_mode: &'cx dyn CanonicalizeMode,
305    needs_canonical_flags: TypeFlags,
306
307    binder_index: ty::DebruijnIndex,
308}
309
310impl<'cx, 'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'cx, 'tcx> {
311    fn cx(&self) -> TyCtxt<'tcx> {
312        self.tcx
313    }
314
315    fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
316    where
317        T: TypeFoldable<TyCtxt<'tcx>>,
318    {
319        self.binder_index.shift_in(1);
320        let t = t.super_fold_with(self);
321        self.binder_index.shift_out(1);
322        t
323    }
324
325    fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
326        match r.kind() {
327            ty::ReBound(index, ..) => {
328                if index >= self.binder_index {
329                    bug!("escaping late-bound region during canonicalization");
330                } else {
331                    r
332                }
333            }
334
335            ty::ReStatic
336            | ty::ReEarlyParam(..)
337            | ty::ReError(_)
338            | ty::ReLateParam(_)
339            | ty::RePlaceholder(..)
340            | ty::ReVar(_)
341            | ty::ReErased => self.canonicalize_mode.canonicalize_free_region(self, r),
342        }
343    }
344
345    fn fold_ty(&mut self, mut t: Ty<'tcx>) -> Ty<'tcx> {
346        match *t.kind() {
347            ty::Infer(ty::TyVar(mut vid)) => {
348                // We need to canonicalize the *root* of our ty var.
349                // This is so that our canonical response correctly reflects
350                // any equated inference vars correctly!
351                let root_vid = self.infcx.unwrap().root_var(vid);
352                if root_vid != vid {
353                    t = Ty::new_var(self.tcx, root_vid);
354                    vid = root_vid;
355                }
356
357                debug!("canonical: type var found with vid {:?}", vid);
358                match self.infcx.unwrap().probe_ty_var(vid) {
359                    // `t` could be a float / int variable; canonicalize that instead.
360                    Ok(t) => {
361                        debug!("(resolved to {:?})", t);
362                        self.fold_ty(t)
363                    }
364
365                    // `TyVar(vid)` is unresolved, track its universe index in the canonicalized
366                    // result.
367                    Err(mut ui) => {
368                        if !self.canonicalize_mode.preserve_universes() {
369                            // FIXME: perf problem described in #55921.
370                            ui = ty::UniverseIndex::ROOT;
371                        }
372                        let sub_root = self.get_or_insert_sub_root(vid);
373                        self.canonicalize_ty_var(CanonicalVarKind::Ty { ui, sub_root }, t)
374                    }
375                }
376            }
377
378            ty::Infer(ty::IntVar(vid)) => {
379                let nt = self.infcx.unwrap().opportunistic_resolve_int_var(vid);
380                if nt != t {
381                    return self.fold_ty(nt);
382                } else {
383                    self.canonicalize_ty_var(CanonicalVarKind::Int, t)
384                }
385            }
386            ty::Infer(ty::FloatVar(vid)) => {
387                let nt = self.infcx.unwrap().opportunistic_resolve_float_var(vid);
388                if nt != t {
389                    return self.fold_ty(nt);
390                } else {
391                    self.canonicalize_ty_var(CanonicalVarKind::Float, t)
392                }
393            }
394
395            ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
396                bug!("encountered a fresh type during canonicalization")
397            }
398
399            ty::Placeholder(mut placeholder) => {
400                if !self.canonicalize_mode.preserve_universes() {
401                    placeholder.universe = ty::UniverseIndex::ROOT;
402                }
403                self.canonicalize_ty_var(CanonicalVarKind::PlaceholderTy(placeholder), t)
404            }
405
406            ty::Bound(debruijn, _) => {
407                if debruijn >= self.binder_index {
408                    bug!("escaping bound type during canonicalization")
409                } else {
410                    t
411                }
412            }
413
414            ty::Closure(..)
415            | ty::CoroutineClosure(..)
416            | ty::Coroutine(..)
417            | ty::CoroutineWitness(..)
418            | ty::Bool
419            | ty::Char
420            | ty::Int(..)
421            | ty::Uint(..)
422            | ty::Float(..)
423            | ty::Adt(..)
424            | ty::Str
425            | ty::Error(_)
426            | ty::Array(..)
427            | ty::Slice(..)
428            | ty::RawPtr(..)
429            | ty::Ref(..)
430            | ty::FnDef(..)
431            | ty::FnPtr(..)
432            | ty::Dynamic(..)
433            | ty::UnsafeBinder(_)
434            | ty::Never
435            | ty::Tuple(..)
436            | ty::Alias(..)
437            | ty::Foreign(..)
438            | ty::Pat(..)
439            | ty::Param(..) => {
440                if t.flags().intersects(self.needs_canonical_flags) {
441                    t.super_fold_with(self)
442                } else {
443                    t
444                }
445            }
446        }
447    }
448
449    fn fold_const(&mut self, mut ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
450        match ct.kind() {
451            ty::ConstKind::Infer(InferConst::Var(mut vid)) => {
452                // We need to canonicalize the *root* of our const var.
453                // This is so that our canonical response correctly reflects
454                // any equated inference vars correctly!
455                let root_vid = self.infcx.unwrap().root_const_var(vid);
456                if root_vid != vid {
457                    ct = ty::Const::new_var(self.tcx, root_vid);
458                    vid = root_vid;
459                }
460
461                debug!("canonical: const var found with vid {:?}", vid);
462                match self.infcx.unwrap().probe_const_var(vid) {
463                    Ok(c) => {
464                        debug!("(resolved to {:?})", c);
465                        return self.fold_const(c);
466                    }
467
468                    // `ConstVar(vid)` is unresolved, track its universe index in the
469                    // canonicalized result
470                    Err(mut ui) => {
471                        if !self.canonicalize_mode.preserve_universes() {
472                            // FIXME: perf problem described in #55921.
473                            ui = ty::UniverseIndex::ROOT;
474                        }
475                        return self.canonicalize_const_var(CanonicalVarKind::Const(ui), ct);
476                    }
477                }
478            }
479            ty::ConstKind::Infer(InferConst::Fresh(_)) => {
480                bug!("encountered a fresh const during canonicalization")
481            }
482            ty::ConstKind::Bound(debruijn, _) => {
483                if debruijn >= self.binder_index {
484                    bug!("escaping bound const during canonicalization")
485                } else {
486                    return ct;
487                }
488            }
489            ty::ConstKind::Placeholder(placeholder) => {
490                return self
491                    .canonicalize_const_var(CanonicalVarKind::PlaceholderConst(placeholder), ct);
492            }
493            _ => {}
494        }
495
496        if ct.flags().intersects(self.needs_canonical_flags) {
497            ct.super_fold_with(self)
498        } else {
499            ct
500        }
501    }
502
503    fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
504        if p.flags().intersects(self.needs_canonical_flags) { p.super_fold_with(self) } else { p }
505    }
506
507    fn fold_clauses(&mut self, c: ty::Clauses<'tcx>) -> ty::Clauses<'tcx> {
508        if c.flags().intersects(self.needs_canonical_flags) { c.super_fold_with(self) } else { c }
509    }
510}
511
512impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
513    /// The main `canonicalize` method, shared impl of
514    /// `canonicalize_query` and `canonicalize_response`.
515    fn canonicalize<V>(
516        value: V,
517        infcx: Option<&InferCtxt<'tcx>>,
518        tcx: TyCtxt<'tcx>,
519        canonicalize_region_mode: &dyn CanonicalizeMode,
520        query_state: &mut OriginalQueryValues<'tcx>,
521    ) -> Canonical<'tcx, V>
522    where
523        V: TypeFoldable<TyCtxt<'tcx>>,
524    {
525        let base = Canonical {
526            max_universe: ty::UniverseIndex::ROOT,
527            variables: List::empty(),
528            value: (),
529        };
530        Canonicalizer::canonicalize_with_base(
531            base,
532            value,
533            infcx,
534            tcx,
535            canonicalize_region_mode,
536            query_state,
537        )
538        .unchecked_map(|((), val)| val)
539    }
540
541    fn canonicalize_with_base<U, V>(
542        base: Canonical<'tcx, U>,
543        value: V,
544        infcx: Option<&InferCtxt<'tcx>>,
545        tcx: TyCtxt<'tcx>,
546        canonicalize_region_mode: &dyn CanonicalizeMode,
547        query_state: &mut OriginalQueryValues<'tcx>,
548    ) -> Canonical<'tcx, (U, V)>
549    where
550        V: TypeFoldable<TyCtxt<'tcx>>,
551    {
552        let needs_canonical_flags = if canonicalize_region_mode.any() {
553            TypeFlags::HAS_INFER | TypeFlags::HAS_PLACEHOLDER | TypeFlags::HAS_FREE_REGIONS
554        } else {
555            TypeFlags::HAS_INFER | TypeFlags::HAS_PLACEHOLDER
556        };
557
558        // Fast path: nothing that needs to be canonicalized.
559        if !value.has_type_flags(needs_canonical_flags) {
560            return base.unchecked_map(|b| (b, value));
561        }
562
563        let mut canonicalizer = Canonicalizer {
564            infcx,
565            tcx,
566            canonicalize_mode: canonicalize_region_mode,
567            needs_canonical_flags,
568            variables: SmallVec::from_slice(base.variables),
569            query_state,
570            indices: FxHashMap::default(),
571            sub_root_lookup_table: Default::default(),
572            binder_index: ty::INNERMOST,
573        };
574        if canonicalizer.query_state.var_values.spilled() {
575            canonicalizer.indices = canonicalizer
576                .query_state
577                .var_values
578                .iter()
579                .enumerate()
580                .map(|(i, &kind)| (kind, BoundVar::new(i)))
581                .collect();
582        }
583        let out_value = value.fold_with(&mut canonicalizer);
584
585        // Once we have canonicalized `out_value`, it should not
586        // contain anything that ties it to this inference context
587        // anymore.
588        debug_assert!(!out_value.has_infer() && !out_value.has_placeholders());
589
590        let canonical_variables =
591            tcx.mk_canonical_var_kinds(&canonicalizer.universe_canonicalized_variables());
592
593        let max_universe = canonical_variables
594            .iter()
595            .map(|cvar| cvar.universe())
596            .max()
597            .unwrap_or(ty::UniverseIndex::ROOT);
598
599        Canonical { max_universe, variables: canonical_variables, value: (base.value, out_value) }
600    }
601
602    /// Creates a canonical variable replacing `kind` from the input,
603    /// or returns an existing variable if `kind` has already been
604    /// seen. `kind` is expected to be an unbound variable (or
605    /// potentially a free region).
606    fn canonical_var(
607        &mut self,
608        var_kind: CanonicalVarKind<'tcx>,
609        value: GenericArg<'tcx>,
610    ) -> BoundVar {
611        let Canonicalizer { variables, query_state, indices, .. } = self;
612
613        let var_values = &mut query_state.var_values;
614
615        let universe = var_kind.universe();
616        if universe != ty::UniverseIndex::ROOT {
617            assert!(self.canonicalize_mode.preserve_universes());
618
619            // Insert universe into the universe map. To preserve the order of the
620            // universes in the value being canonicalized, we don't update the
621            // universe in `var_kind` until we have finished canonicalizing.
622            match query_state.universe_map.binary_search(&universe) {
623                Err(idx) => query_state.universe_map.insert(idx, universe),
624                Ok(_) => {}
625            }
626        }
627
628        // This code is hot. `variables` and `var_values` are usually small
629        // (fewer than 8 elements ~95% of the time). They are SmallVec's to
630        // avoid allocations in those cases. We also don't use `indices` to
631        // determine if a kind has been seen before until the limit of 8 has
632        // been exceeded, to also avoid allocations for `indices`.
633        if !var_values.spilled() {
634            // `var_values` is stack-allocated. `indices` isn't used yet. Do a
635            // direct linear search of `var_values`.
636            if let Some(idx) = var_values.iter().position(|&v| v == value) {
637                // `kind` is already present in `var_values`.
638                BoundVar::new(idx)
639            } else {
640                // `kind` isn't present in `var_values`. Append it. Likewise
641                // for `var_kind` and `variables`.
642                variables.push(var_kind);
643                var_values.push(value);
644                assert_eq!(variables.len(), var_values.len());
645
646                // If `var_values` has become big enough to be heap-allocated,
647                // fill up `indices` to facilitate subsequent lookups.
648                if var_values.spilled() {
649                    assert!(indices.is_empty());
650                    *indices = var_values
651                        .iter()
652                        .enumerate()
653                        .map(|(i, &value)| (value, BoundVar::new(i)))
654                        .collect();
655                }
656                // The cv is the index of the appended element.
657                BoundVar::new(var_values.len() - 1)
658            }
659        } else {
660            // `var_values` is large. Do a hashmap search via `indices`.
661            *indices.entry(value).or_insert_with(|| {
662                variables.push(var_kind);
663                var_values.push(value);
664                assert_eq!(variables.len(), var_values.len());
665                BoundVar::new(variables.len() - 1)
666            })
667        }
668    }
669
670    fn get_or_insert_sub_root(&mut self, vid: ty::TyVid) -> ty::BoundVar {
671        let root_vid = self.infcx.unwrap().sub_unification_table_root_var(vid);
672        let idx =
673            *self.sub_root_lookup_table.entry(root_vid).or_insert_with(|| self.variables.len());
674        ty::BoundVar::from(idx)
675    }
676
677    /// Replaces the universe indexes used in `var_values` with their index in
678    /// `query_state.universe_map`. This minimizes the maximum universe used in
679    /// the canonicalized value.
680    fn universe_canonicalized_variables(self) -> SmallVec<[CanonicalVarKind<'tcx>; 8]> {
681        if self.query_state.universe_map.len() == 1 {
682            return self.variables;
683        }
684
685        let reverse_universe_map: FxHashMap<ty::UniverseIndex, ty::UniverseIndex> = self
686            .query_state
687            .universe_map
688            .iter()
689            .enumerate()
690            .map(|(idx, universe)| (*universe, ty::UniverseIndex::from_usize(idx)))
691            .collect();
692
693        self.variables
694            .iter()
695            .map(|&kind| match kind {
696                CanonicalVarKind::Int | CanonicalVarKind::Float => {
697                    return kind;
698                }
699                CanonicalVarKind::Ty { ui, sub_root } => {
700                    CanonicalVarKind::Ty { ui: reverse_universe_map[&ui], sub_root }
701                }
702                CanonicalVarKind::Region(u) => CanonicalVarKind::Region(reverse_universe_map[&u]),
703                CanonicalVarKind::Const(u) => CanonicalVarKind::Const(reverse_universe_map[&u]),
704                CanonicalVarKind::PlaceholderTy(placeholder) => {
705                    CanonicalVarKind::PlaceholderTy(ty::Placeholder {
706                        universe: reverse_universe_map[&placeholder.universe],
707                        ..placeholder
708                    })
709                }
710                CanonicalVarKind::PlaceholderRegion(placeholder) => {
711                    CanonicalVarKind::PlaceholderRegion(ty::Placeholder {
712                        universe: reverse_universe_map[&placeholder.universe],
713                        ..placeholder
714                    })
715                }
716                CanonicalVarKind::PlaceholderConst(placeholder) => {
717                    CanonicalVarKind::PlaceholderConst(ty::Placeholder {
718                        universe: reverse_universe_map[&placeholder.universe],
719                        ..placeholder
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(CanonicalVarKind::Region(ty::UniverseIndex::ROOT), r)
744    }
745
746    /// Creates a canonical variable (with the given `info`)
747    /// representing the region `r`; return a region referencing it.
748    fn canonical_var_for_region(
749        &mut self,
750        var_kind: CanonicalVarKind<'tcx>,
751        r: ty::Region<'tcx>,
752    ) -> ty::Region<'tcx> {
753        let var = self.canonical_var(var_kind, r.into());
754        let br = ty::BoundRegion { var, kind: ty::BoundRegionKind::Anon };
755        ty::Region::new_bound(self.cx(), self.binder_index, br)
756    }
757
758    /// Given a type variable `ty_var` of the given kind, first check
759    /// if `ty_var` is bound to anything; if so, canonicalize
760    /// *that*. Otherwise, create a new canonical variable for
761    /// `ty_var`.
762    fn canonicalize_ty_var(
763        &mut self,
764        var_kind: CanonicalVarKind<'tcx>,
765        ty_var: Ty<'tcx>,
766    ) -> Ty<'tcx> {
767        debug_assert!(!self.infcx.is_some_and(|infcx| ty_var != infcx.shallow_resolve(ty_var)));
768        let var = self.canonical_var(var_kind, ty_var.into());
769        let bt = ty::BoundTy { var, kind: ty::BoundTyKind::Anon };
770        Ty::new_bound(self.tcx, self.binder_index, bt)
771    }
772
773    /// Given a type variable `const_var` of the given kind, first check
774    /// if `const_var` is bound to anything; if so, canonicalize
775    /// *that*. Otherwise, create a new canonical variable for
776    /// `const_var`.
777    fn canonicalize_const_var(
778        &mut self,
779        var_kind: CanonicalVarKind<'tcx>,
780        ct_var: ty::Const<'tcx>,
781    ) -> ty::Const<'tcx> {
782        debug_assert!(
783            !self.infcx.is_some_and(|infcx| ct_var != infcx.shallow_resolve_const(ct_var))
784        );
785        let var = self.canonical_var(var_kind, ct_var.into());
786        let bc = ty::BoundConst { var };
787        ty::Const::new_bound(self.tcx, self.binder_index, bc)
788    }
789}
rustc_infer/infer/canonical/canonicalizer.rs

rustc_infer/infer/canonical/
canonicalizer.rs
