Skip to main content

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