Skip to main content

rustc_middle/infer/
canonical.rs

1//! **Canonicalization** is the key to constructing a query in the
2//! middle of type inference. Ordinarily, it is not possible to store
3//! types from type inference in query keys, because they contain
4//! references to inference variables whose lifetimes are too short
5//! and so forth. Canonicalizing a value T1 using `canonicalize_query`
6//! produces two things:
7//!
8//! - a value T2 where each unbound inference variable has been
9//!   replaced with a **canonical variable**;
10//! - a map M (of type `CanonicalVarValues`) from those canonical
11//!   variables back to the original.
12//!
13//! We can then do queries using T2. These will give back constraints
14//! on the canonical variables which can be translated, using the map
15//! M, into constraints in our source context. This process of
16//! translating the results back is done by the
17//! `instantiate_query_result` method.
18//!
19//! For a more detailed look at what is happening here, check
20//! out the [chapter in the rustc dev guide][c].
21//!
22//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
23
24use std::collections::hash_map::Entry;
25
26use rustc_data_structures::fx::FxHashMap;
27use rustc_data_structures::sync::Lock;
28use rustc_macros::{StableHash, TypeFoldable, TypeVisitable};
29pub use rustc_type_ir as ir;
30use smallvec::SmallVec;
31
32use crate::mir::ConstraintCategory;
33use crate::ty::{self, GenericArg, GenericArgs, List, Ty, TyCtxt, TypeFlags, TypeVisitableExt};
34
35pub type CanonicalQueryInput<'tcx, V> = ir::CanonicalQueryInput<TyCtxt<'tcx>, V>;
36pub type Canonical<'tcx, V> = ir::Canonical<TyCtxt<'tcx>, V>;
37pub type Canonicalized<V> = ir::Canonicalized<V>;
38pub type CanonicalVarKind<'tcx> = ir::CanonicalVarKind<TyCtxt<'tcx>>;
39pub type CanonicalVarValues<'tcx> = ir::CanonicalVarValues<TyCtxt<'tcx>>;
40pub type CanonicalVarKinds<'tcx> = &'tcx List<CanonicalVarKind<'tcx>>;
41
42/// When we canonicalize a value to form a query, we wind up replacing
43/// various parts of it with canonical variables. This struct stores
44/// those replaced bits to remember for when we process the query
45/// result.
46#[derive(#[automatically_derived]impl<'tcx> ::core::clone::Clone for
    OriginalQueryValues<'tcx> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        OriginalQueryValues {
            universe_map: ::core::clone::Clone::clone(&self.universe_map),
            var_values: ::core::clone::Clone::clone(&self.var_values),
        }
    }
}Clone, #[automatically_derived]impl<'tcx> ::core::fmt::Debug for
    OriginalQueryValues<'tcx> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field2_finish(f,
            "OriginalQueryValues universe_map var_values", &self.universe_map,
            &&self.var_values)
    }
}Debug)]
47pub struct OriginalQueryValues<'tcx> {
48    /// Map from the universes that appear in the query to the universes in the
49    /// caller context. For all queries except `evaluate_goal` (used by Chalk),
50    /// we only ever put ROOT values into the query, so this map is very
51    /// simple.
52    pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
53
54    /// This is equivalent to `CanonicalVarValues`, but using a
55    /// `SmallVec` yields a significant performance win.
56    pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
57}
58
59impl<'tcx> Default for OriginalQueryValues<'tcx> {
60    fn default() -> Self {
61        let mut universe_map = SmallVec::default();
62        universe_map.push(ty::UniverseIndex::ROOT);
63
64        Self { universe_map, var_values: SmallVec::default() }
65    }
66}
67
68/// After we execute a query with a canonicalized key, we get back a
69/// `Canonical<QueryResponse<..>>`. You can use
70/// `instantiate_query_result` to access the data in this result.
71#[derive(#[automatically_derived]impl<'tcx, R: ::core::clone::Clone>
    ::core::clone::Clone for QueryResponse<'tcx, R> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        QueryResponse {
            var_values: ::core::clone::Clone::clone(&self.var_values),
            region_constraints: ::core::clone::Clone::clone(&self.region_constraints),
            certainty: ::core::clone::Clone::clone(&self.certainty),
            opaque_types: ::core::clone::Clone::clone(&self.opaque_types),
            value: ::core::clone::Clone::clone(&self.value),
        }
    }
}Clone, #[automatically_derived]impl<'tcx, R: ::core::fmt::Debug> ::core::fmt::Debug
    for QueryResponse<'tcx, R> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field5_finish(f,
            "QueryResponse var_values region_constraints certainty opaque_types value",
            &self.var_values, &self.region_constraints, &self.certainty,
            &self.opaque_types, &&self.value)
    }
}Debug, const _: () =
    {
        impl<'tcx, R> ::rustc_data_structures::stable_hash::StableHash for
            QueryResponse<'tcx, R> where
            R: ::rustc_data_structures::stable_hash::StableHash {
            #[inline]
            fn stable_hash<__Hcx: ::rustc_data_structures::stable_hash::StableHashCtxt>(&self,
                __hcx: &mut __Hcx,
                __hasher:
                    &mut ::rustc_data_structures::stable_hash::StableHasher) {
                match *self {
                    QueryResponse {
                        var_values: ref __binding_0,
                        region_constraints: ref __binding_1,
                        certainty: ref __binding_2,
                        opaque_types: ref __binding_3,
                        value: ref __binding_4 } => {
                        { __binding_0.stable_hash(__hcx, __hasher); }
                        { __binding_1.stable_hash(__hcx, __hasher); }
                        { __binding_2.stable_hash(__hcx, __hasher); }
                        { __binding_3.stable_hash(__hcx, __hasher); }
                        { __binding_4.stable_hash(__hcx, __hasher); }
                    }
                }
            }
        }
    };StableHash, const _: () =
    {
        impl<'tcx, R>
            ::rustc_middle::ty::TypeFoldable<::rustc_middle::ty::TyCtxt<'tcx>>
            for QueryResponse<'tcx, R> where
            R: ::rustc_middle::ty::TypeFoldable<::rustc_middle::ty::TyCtxt<'tcx>>
            {
            fn try_fold_with<__F: ::rustc_middle::ty::FallibleTypeFolder<::rustc_middle::ty::TyCtxt<'tcx>>>(self,
                __folder: &mut __F) -> Result<Self, __F::Error> {
                Ok(match self {
                        QueryResponse {
                            var_values: __binding_0,
                            region_constraints: __binding_1,
                            certainty: __binding_2,
                            opaque_types: __binding_3,
                            value: __binding_4 } => {
                            QueryResponse {
                                var_values: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_0,
                                        __folder)?,
                                region_constraints: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_1,
                                        __folder)?,
                                certainty: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_2,
                                        __folder)?,
                                opaque_types: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_3,
                                        __folder)?,
                                value: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_4,
                                        __folder)?,
                            }
                        }
                    })
            }
            fn fold_with<__F: ::rustc_middle::ty::TypeFolder<::rustc_middle::ty::TyCtxt<'tcx>>>(self,
                __folder: &mut __F) -> Self {
                match self {
                    QueryResponse {
                        var_values: __binding_0,
                        region_constraints: __binding_1,
                        certainty: __binding_2,
                        opaque_types: __binding_3,
                        value: __binding_4 } => {
                        QueryResponse {
                            var_values: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_0,
                                __folder),
                            region_constraints: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_1,
                                __folder),
                            certainty: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_2,
                                __folder),
                            opaque_types: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_3,
                                __folder),
                            value: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_4,
                                __folder),
                        }
                    }
                }
            }
        }
    };TypeFoldable, const _: () =
    {
        impl<'tcx, R>
            ::rustc_middle::ty::TypeVisitable<::rustc_middle::ty::TyCtxt<'tcx>>
            for QueryResponse<'tcx, R> where
            R: ::rustc_middle::ty::TypeVisitable<::rustc_middle::ty::TyCtxt<'tcx>>
            {
            fn visit_with<__V: ::rustc_middle::ty::TypeVisitor<::rustc_middle::ty::TyCtxt<'tcx>>>(&self,
                __visitor: &mut __V) -> __V::Result {
                match *self {
                    QueryResponse {
                        var_values: ref __binding_0,
                        region_constraints: ref __binding_1,
                        certainty: ref __binding_2,
                        opaque_types: ref __binding_3,
                        value: ref __binding_4 } => {
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_0,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_1,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_2,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_3,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_4,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                    }
                }
                <__V::Result as ::rustc_middle::ty::VisitorResult>::output()
            }
        }
    };TypeVisitable)]
72pub struct QueryResponse<'tcx, R> {
73    pub var_values: GenericArgs<'tcx>,
74    pub region_constraints: QueryRegionConstraints<'tcx>,
75    pub certainty: Certainty,
76    pub opaque_types: Vec<(ty::OpaqueTypeKey<'tcx>, Ty<'tcx>)>,
77    pub value: R,
78}
79
80#[derive(#[automatically_derived]impl<'tcx> ::core::clone::Clone for
    QueryRegionConstraints<'tcx> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        QueryRegionConstraints {
            constraints: ::core::clone::Clone::clone(&self.constraints),
            assumptions: ::core::clone::Clone::clone(&self.assumptions),
        }
    }
}Clone, #[automatically_derived]impl<'tcx> ::core::fmt::Debug for
    QueryRegionConstraints<'tcx> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field2_finish(f,
            "QueryRegionConstraints constraints assumptions",
            &self.constraints, &&self.assumptions)
    }
}Debug, #[automatically_derived]impl<'tcx> ::core::default::Default for
    QueryRegionConstraints<'tcx> {
    #[inline]
    fn default() -> Self {
        QueryRegionConstraints {
            constraints: ::core::default::Default::default(),
            assumptions: ::core::default::Default::default(),
        }
    }
}Default, #[automatically_derived]impl<'tcx> ::core::marker::StructuralPartialEq for
    QueryRegionConstraints<'tcx> {
}
#[automatically_derived]impl<'tcx> ::core::cmp::PartialEq for
    QueryRegionConstraints<'tcx> {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        self.constraints == other.constraints &&
            self.assumptions == other.assumptions
    }
}PartialEq, #[automatically_derived]impl<'tcx> ::core::cmp::Eq for
    QueryRegionConstraints<'tcx> {
    #[inline]
    #[doc(hidden)]
    #[coverage(off)]
    fn assert_fields_are_eq(&self) {
        let _: ::core::cmp::AssertParamIsEq<Vec<QueryRegionConstraint<'tcx>>>;
        let _: ::core::cmp::AssertParamIsEq<Vec<ty::ArgOutlivesClause<'tcx>>>;
    }
}Eq, #[automatically_derived]impl<'tcx> ::core::hash::Hash for
    QueryRegionConstraints<'tcx> {
    #[inline]
    fn hash<__H: ::core::hash::Hasher>(&self, state: &mut __H) {
        ::core::hash::Hash::hash(&self.constraints, state);
        ::core::hash::Hash::hash(&self.assumptions, state)
    }
}Hash)]
81#[derive(const _: () =
    {
        impl<'tcx> ::rustc_data_structures::stable_hash::StableHash for
            QueryRegionConstraints<'tcx> {
            #[inline]
            fn stable_hash<__Hcx: ::rustc_data_structures::stable_hash::StableHashCtxt>(&self,
                __hcx: &mut __Hcx,
                __hasher:
                    &mut ::rustc_data_structures::stable_hash::StableHasher) {
                match *self {
                    QueryRegionConstraints {
                        constraints: ref __binding_0, assumptions: ref __binding_1 }
                        => {
                        { __binding_0.stable_hash(__hcx, __hasher); }
                        { __binding_1.stable_hash(__hcx, __hasher); }
                    }
                }
            }
        }
    };StableHash, const _: () =
    {
        impl<'tcx>
            ::rustc_middle::ty::TypeFoldable<::rustc_middle::ty::TyCtxt<'tcx>>
            for QueryRegionConstraints<'tcx> {
            fn try_fold_with<__F: ::rustc_middle::ty::FallibleTypeFolder<::rustc_middle::ty::TyCtxt<'tcx>>>(self,
                __folder: &mut __F) -> Result<Self, __F::Error> {
                Ok(match self {
                        QueryRegionConstraints {
                            constraints: __binding_0, assumptions: __binding_1 } => {
                            QueryRegionConstraints {
                                constraints: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_0,
                                        __folder)?,
                                assumptions: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_1,
                                        __folder)?,
                            }
                        }
                    })
            }
            fn fold_with<__F: ::rustc_middle::ty::TypeFolder<::rustc_middle::ty::TyCtxt<'tcx>>>(self,
                __folder: &mut __F) -> Self {
                match self {
                    QueryRegionConstraints {
                        constraints: __binding_0, assumptions: __binding_1 } => {
                        QueryRegionConstraints {
                            constraints: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_0,
                                __folder),
                            assumptions: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_1,
                                __folder),
                        }
                    }
                }
            }
        }
    };TypeFoldable, const _: () =
    {
        impl<'tcx>
            ::rustc_middle::ty::TypeVisitable<::rustc_middle::ty::TyCtxt<'tcx>>
            for QueryRegionConstraints<'tcx> {
            fn visit_with<__V: ::rustc_middle::ty::TypeVisitor<::rustc_middle::ty::TyCtxt<'tcx>>>(&self,
                __visitor: &mut __V) -> __V::Result {
                match *self {
                    QueryRegionConstraints {
                        constraints: ref __binding_0, assumptions: ref __binding_1 }
                        => {
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_0,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_1,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                    }
                }
                <__V::Result as ::rustc_middle::ty::VisitorResult>::output()
            }
        }
    };TypeVisitable)]
82pub struct QueryRegionConstraints<'tcx> {
83    pub constraints: Vec<QueryRegionConstraint<'tcx>>,
84    pub assumptions: Vec<ty::ArgOutlivesClause<'tcx>>,
85}
86
87impl QueryRegionConstraints<'_> {
88    /// Represents an empty (trivially true) set of region constraints.
89    ///
90    /// FIXME(higher_ranked_auto): This could still just be true if there are only assumptions?
91    /// Because I don't expect for us to get cases where an assumption from one query would
92    /// discharge a requirement from another query, which is a potential problem if we did throw
93    /// away these assumptions because there were no constraints.
94    pub fn is_empty(&self) -> bool {
95        let QueryRegionConstraints { constraints, assumptions } = self;
96        constraints.is_empty() && assumptions.is_empty()
97    }
98}
99
100pub type CanonicalQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;
101
102/// Indicates whether or not we were able to prove the query to be
103/// true.
104#[derive(#[automatically_derived]impl ::core::marker::Copy for Certainty { }Copy, #[automatically_derived]#[doc(hidden)]unsafe impl ::core::clone::TrivialClone
    for Certainty {
}
#[automatically_derived]impl ::core::clone::Clone for Certainty {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self { *self }
}Clone, #[automatically_derived]impl ::core::fmt::Debug for Certainty {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::write_str(f,
            match self {
                Certainty::Proven => "Proven",
                Certainty::Ambiguous => "Ambiguous",
            })
    }
}Debug, const _: () =
    {
        impl ::rustc_data_structures::stable_hash::StableHash for Certainty {
            #[inline]
            fn stable_hash<__Hcx: ::rustc_data_structures::stable_hash::StableHashCtxt>(&self,
                __hcx: &mut __Hcx,
                __hasher:
                    &mut ::rustc_data_structures::stable_hash::StableHasher) {
                match *self {
                    Certainty::Proven => 0u8.stable_hash(__hcx, __hasher),
                    Certainty::Ambiguous => 1u8.stable_hash(__hcx, __hasher),
                }
                match *self {
                    Certainty::Proven => {}
                    Certainty::Ambiguous => {}
                }
            }
        }
    };StableHash)]
105pub enum Certainty {
106    /// The query is known to be true, presuming that you apply the
107    /// given `var_values` and the region-constraints are satisfied.
108    Proven,
109
110    /// The query is not known to be true, but also not known to be
111    /// false. The `var_values` represent *either* values that must
112    /// hold in order for the query to be true, or helpful tips that
113    /// *might* make it true. Currently rustc's trait solver cannot
114    /// distinguish the two (e.g., due to our preference for where
115    /// clauses over impls).
116    ///
117    /// After some unification and things have been done, it makes
118    /// sense to try and prove again -- of course, at that point, the
119    /// canonical form will be different, making this a distinct
120    /// query.
121    Ambiguous,
122}
123
124impl Certainty {
125    pub fn is_proven(&self) -> bool {
126        match self {
127            Certainty::Proven => true,
128            Certainty::Ambiguous => false,
129        }
130    }
131}
132
133impl<'tcx, R> QueryResponse<'tcx, R> {
134    pub fn is_proven(&self) -> bool {
135        self.certainty.is_proven()
136    }
137}
138
139#[derive(#[automatically_derived]impl<'tcx> ::core::fmt::Debug for
    QueryRegionConstraint<'tcx> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        ::core::fmt::Formatter::debug_struct_field3_finish(f,
            "QueryRegionConstraint constraint category visible_for_leak_check",
            &self.constraint, &self.category, &&self.visible_for_leak_check)
    }
}Debug, const _: () =
    {
        impl<'tcx> ::rustc_data_structures::stable_hash::StableHash for
            QueryRegionConstraint<'tcx> {
            #[inline]
            fn stable_hash<__Hcx: ::rustc_data_structures::stable_hash::StableHashCtxt>(&self,
                __hcx: &mut __Hcx,
                __hasher:
                    &mut ::rustc_data_structures::stable_hash::StableHasher) {
                match *self {
                    QueryRegionConstraint {
                        constraint: ref __binding_0,
                        category: ref __binding_1,
                        visible_for_leak_check: ref __binding_2 } => {
                        { __binding_0.stable_hash(__hcx, __hasher); }
                        { __binding_1.stable_hash(__hcx, __hasher); }
                        { __binding_2.stable_hash(__hcx, __hasher); }
                    }
                }
            }
        }
    };StableHash, #[automatically_derived]impl<'tcx> ::core::hash::Hash for
    QueryRegionConstraint<'tcx> {
    #[inline]
    fn hash<__H: ::core::hash::Hasher>(&self, state: &mut __H) {
        ::core::hash::Hash::hash(&self.constraint, state);
        ::core::hash::Hash::hash(&self.category, state);
        ::core::hash::Hash::hash(&self.visible_for_leak_check, state)
    }
}Hash, #[automatically_derived]impl<'tcx> ::core::cmp::Eq for
    QueryRegionConstraint<'tcx> {
    #[inline]
    #[doc(hidden)]
    #[coverage(off)]
    fn assert_fields_are_eq(&self) {
        let _: ::core::cmp::AssertParamIsEq<ty::RegionConstraint<'tcx>>;
        let _: ::core::cmp::AssertParamIsEq<ConstraintCategory<'tcx>>;
        let _: ::core::cmp::AssertParamIsEq<ty::VisibleForLeakCheck>;
    }
}Eq, #[automatically_derived]impl<'tcx> ::core::marker::StructuralPartialEq for
    QueryRegionConstraint<'tcx> {
}
#[automatically_derived]impl<'tcx> ::core::cmp::PartialEq for
    QueryRegionConstraint<'tcx> {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        self.constraint == other.constraint && self.category == other.category
            && self.visible_for_leak_check == other.visible_for_leak_check
    }
}PartialEq, const _: () =
    {
        impl<'tcx>
            ::rustc_middle::ty::TypeVisitable<::rustc_middle::ty::TyCtxt<'tcx>>
            for QueryRegionConstraint<'tcx> {
            fn visit_with<__V: ::rustc_middle::ty::TypeVisitor<::rustc_middle::ty::TyCtxt<'tcx>>>(&self,
                __visitor: &mut __V) -> __V::Result {
                match *self {
                    QueryRegionConstraint {
                        constraint: ref __binding_0,
                        category: ref __binding_1,
                        visible_for_leak_check: ref __binding_2 } => {
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_0,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_1,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                        {
                            match ::rustc_middle::ty::VisitorResult::branch(::rustc_middle::ty::TypeVisitable::visit_with(__binding_2,
                                        __visitor)) {
                                ::core::ops::ControlFlow::Continue(()) => {}
                                ::core::ops::ControlFlow::Break(r) => {
                                    return ::rustc_middle::ty::VisitorResult::from_residual(r);
                                }
                            }
                        }
                    }
                }
                <__V::Result as ::rustc_middle::ty::VisitorResult>::output()
            }
        }
    };TypeVisitable, #[automatically_derived]#[doc(hidden)]unsafe impl<'tcx>
    ::core::clone::TrivialClone for QueryRegionConstraint<'tcx> {
}
#[automatically_derived]impl<'tcx> ::core::clone::Clone for
    QueryRegionConstraint<'tcx> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        let _: ::core::clone::AssertParamIsClone<ty::RegionConstraint<'tcx>>;
        let _: ::core::clone::AssertParamIsClone<ConstraintCategory<'tcx>>;
        let _: ::core::clone::AssertParamIsClone<ty::VisibleForLeakCheck>;
        *self
    }
}Clone, const _: () =
    {
        impl<'tcx>
            ::rustc_middle::ty::TypeFoldable<::rustc_middle::ty::TyCtxt<'tcx>>
            for QueryRegionConstraint<'tcx> {
            fn try_fold_with<__F: ::rustc_middle::ty::FallibleTypeFolder<::rustc_middle::ty::TyCtxt<'tcx>>>(self,
                __folder: &mut __F) -> Result<Self, __F::Error> {
                Ok(match self {
                        QueryRegionConstraint {
                            constraint: __binding_0,
                            category: __binding_1,
                            visible_for_leak_check: __binding_2 } => {
                            QueryRegionConstraint {
                                constraint: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_0,
                                        __folder)?,
                                category: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_1,
                                        __folder)?,
                                visible_for_leak_check: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_2,
                                        __folder)?,
                            }
                        }
                    })
            }
            fn fold_with<__F: ::rustc_middle::ty::TypeFolder<::rustc_middle::ty::TyCtxt<'tcx>>>(self,
                __folder: &mut __F) -> Self {
                match self {
                    QueryRegionConstraint {
                        constraint: __binding_0,
                        category: __binding_1,
                        visible_for_leak_check: __binding_2 } => {
                        QueryRegionConstraint {
                            constraint: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_0,
                                __folder),
                            category: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_1,
                                __folder),
                            visible_for_leak_check: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_2,
                                __folder),
                        }
                    }
                }
            }
        }
    };TypeFoldable, #[automatically_derived]impl<'tcx> ::core::marker::Copy for
    QueryRegionConstraint<'tcx> {
}Copy)]
140pub struct QueryRegionConstraint<'tcx> {
141    pub constraint: ty::RegionConstraint<'tcx>,
142    pub category: ConstraintCategory<'tcx>,
143    pub visible_for_leak_check: ty::VisibleForLeakCheck,
144}
145
146#[derive(#[automatically_derived]impl<'tcx> ::core::default::Default for
    CanonicalParamEnvCache<'tcx> {
    #[inline]
    fn default() -> Self {
        CanonicalParamEnvCache { map: ::core::default::Default::default() }
    }
}Default)]
147pub struct CanonicalParamEnvCache<'tcx> {
148    map: Lock<
149        FxHashMap<
150            ty::ParamEnv<'tcx>,
151            (Canonical<'tcx, ty::ParamEnv<'tcx>>, &'tcx [GenericArg<'tcx>]),
152        >,
153    >,
154}
155
156impl<'tcx> CanonicalParamEnvCache<'tcx> {
157    /// Gets the cached canonical form of `key` or executes
158    /// `canonicalize_op` and caches the result if not present.
159    ///
160    /// `canonicalize_op` is intentionally not allowed to be a closure to
161    /// statically prevent it from capturing `InferCtxt` and resolving
162    /// inference variables, which invalidates the cache.
163    pub fn get_or_insert(
164        &self,
165        tcx: TyCtxt<'tcx>,
166        key: ty::ParamEnv<'tcx>,
167        state: &mut OriginalQueryValues<'tcx>,
168        canonicalize_op: fn(
169            TyCtxt<'tcx>,
170            ty::ParamEnv<'tcx>,
171            &mut OriginalQueryValues<'tcx>,
172        ) -> Canonical<'tcx, ty::ParamEnv<'tcx>>,
173    ) -> Canonical<'tcx, ty::ParamEnv<'tcx>> {
174        if !key.has_type_flags(
175            TypeFlags::HAS_INFER | TypeFlags::HAS_PLACEHOLDER | TypeFlags::HAS_FREE_REGIONS,
176        ) {
177            return Canonical {
178                max_universe: ty::UniverseIndex::ROOT,
179                var_kinds: List::empty(),
180                value: key,
181            };
182        }
183
184        {
    match (&state.var_values.len(), &0) {
        (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!(state.var_values.len(), 0);
185        {
    match (&state.universe_map.len(), &1) {
        (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!(state.universe_map.len(), 1);
186        if true {
    {
        match (&&*state.universe_map, &&[ty::UniverseIndex::ROOT]) {
            (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);
                }
            }
        }
    };
};debug_assert_eq!(&*state.universe_map, &[ty::UniverseIndex::ROOT]);
187
188        match self.map.borrow().entry(key) {
189            Entry::Occupied(e) => {
190                let (canonical, var_values) = e.get();
191                if truecfg!(debug_assertions) {
192                    let mut state = state.clone();
193                    let rerun_canonical = canonicalize_op(tcx, key, &mut state);
194                    {
    match (&rerun_canonical, &*canonical) {
        (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!(rerun_canonical, *canonical);
195                    let OriginalQueryValues { var_values: rerun_var_values, universe_map } = state;
196                    {
    match (&universe_map.len(), &1) {
        (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!(universe_map.len(), 1);
197                    {
    match (&**var_values, &*rerun_var_values) {
        (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_values, *rerun_var_values);
198                }
199                state.var_values.extend_from_slice(var_values);
200                *canonical
201            }
202            Entry::Vacant(e) => {
203                let canonical = canonicalize_op(tcx, key, state);
204                let OriginalQueryValues { var_values, universe_map } = state;
205                {
    match (&universe_map.len(), &1) {
        (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!(universe_map.len(), 1);
206                e.insert((canonical, tcx.arena.alloc_slice(var_values)));
207                canonical
208            }
209        }
210    }
211}