Skip to main content

rustc_infer/traits/
mod.rs

1//! Trait Resolution. See the [rustc-dev-guide] for more information on how this works.
2//!
3//! [rustc-dev-guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html
4
5mod engine;
6mod project;
7mod structural_impls;
8pub mod util;
9
10use std::cmp;
11use std::hash::{Hash, Hasher};
12
13use hir::def_id::LocalDefId;
14use rustc_hir as hir;
15use rustc_macros::{TypeFoldable, TypeVisitable};
16use rustc_middle::traits::query::NoSolution;
17use rustc_middle::traits::solve::Certainty;
18pub use rustc_middle::traits::*;
19use rustc_middle::ty::{self, Ty, TyCtxt, Upcast};
20use rustc_span::Span;
21use thin_vec::ThinVec;
22
23pub use self::engine::{
24    EngineError, FromSolverError, ScrubbedTraitError, TraitEngine, TraitErrors,
25};
26pub(crate) use self::project::UndoLog;
27pub use self::project::{
28    MismatchedProjectionTypes, Normalized, NormalizedTerm, ProjectionCache, ProjectionCacheEntry,
29    ProjectionCacheKey, ProjectionCacheStorage,
30};
31use crate::infer::InferCtxt;
32
33/// An `Obligation` represents some trait reference (e.g., `i32: Eq`) for
34/// which the "impl_source" must be found. The process of finding an "impl_source" is
35/// called "resolving" the `Obligation`. This process consists of
36/// either identifying an `impl` (e.g., `impl Eq for i32`) that
37/// satisfies the obligation, or else finding a bound that is in
38/// scope. The eventual result is usually a `Selection` (defined below).
39#[derive(#[automatically_derived]impl<'tcx, T: ::core::clone::Clone>
    ::core::clone::Clone for Obligation<'tcx, T> {
    #[inline]
    #[rustc_trivial_field_reads]
    fn clone(&self) -> Self {
        Obligation {
            cause: ::core::clone::Clone::clone(&self.cause),
            param_env: ::core::clone::Clone::clone(&self.param_env),
            predicate: ::core::clone::Clone::clone(&self.predicate),
            recursion_depth: ::core::clone::Clone::clone(&self.recursion_depth),
        }
    }
}Clone, const _: () =
    {
        impl<'tcx, T>
            ::rustc_middle::ty::TypeFoldable<::rustc_middle::ty::TyCtxt<'tcx>>
            for Obligation<'tcx, T> where
            T: ::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 {
                        Obligation {
                            cause: __binding_0,
                            param_env: __binding_1,
                            predicate: __binding_2,
                            recursion_depth: __binding_3 } => {
                            Obligation {
                                cause: __binding_0,
                                param_env: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_1,
                                        __folder)?,
                                predicate: ::rustc_middle::ty::TypeFoldable::try_fold_with(__binding_2,
                                        __folder)?,
                                recursion_depth: __binding_3,
                            }
                        }
                    })
            }
            fn fold_with<__F: ::rustc_middle::ty::TypeFolder<::rustc_middle::ty::TyCtxt<'tcx>>>(self,
                __folder: &mut __F) -> Self {
                match self {
                    Obligation {
                        cause: __binding_0,
                        param_env: __binding_1,
                        predicate: __binding_2,
                        recursion_depth: __binding_3 } => {
                        Obligation {
                            cause: __binding_0,
                            param_env: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_1,
                                __folder),
                            predicate: ::rustc_middle::ty::TypeFoldable::fold_with(__binding_2,
                                __folder),
                            recursion_depth: __binding_3,
                        }
                    }
                }
            }
        }
    };TypeFoldable, const _: () =
    {
        impl<'tcx, T>
            ::rustc_middle::ty::TypeVisitable<::rustc_middle::ty::TyCtxt<'tcx>>
            for Obligation<'tcx, T> where
            T: ::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 {
                    Obligation {
                        param_env: ref __binding_1, predicate: ref __binding_2, .. }
                        => {
                        {
                            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)]
40pub struct Obligation<'tcx, T> {
41    /// The reason we have to prove this thing.
42    /// FIXME: we shouldn't ignore the cause but instead change the affected visitors
43    /// to only visit predicates manually.
44    #[type_foldable(identity)]
45    #[type_visitable(ignore)]
46    pub cause: ObligationCause<'tcx>,
47
48    /// The environment in which we should prove this thing.
49    pub param_env: ty::ParamEnv<'tcx>,
50
51    /// The thing we are trying to prove.
52    pub predicate: T,
53
54    /// If we started proving this as a result of trying to prove
55    /// something else, track the total depth to ensure termination.
56    /// If this goes over a certain threshold, we abort compilation --
57    /// in such cases, we can not say whether or not the predicate
58    /// holds for certain. Stupid halting problem; such a drag.
59    #[type_foldable(identity)]
60    #[type_visitable(ignore)]
61    pub recursion_depth: usize,
62}
63
64impl<'tcx, T: Copy> Obligation<'tcx, T> {
65    pub fn as_goal(&self) -> solve::Goal<'tcx, T> {
66        solve::Goal { param_env: self.param_env, predicate: self.predicate }
67    }
68}
69
70impl<'tcx, T: PartialEq> PartialEq<Obligation<'tcx, T>> for Obligation<'tcx, T> {
71    #[inline]
72    fn eq(&self, other: &Obligation<'tcx, T>) -> bool {
73        // Ignore `cause` and `recursion_depth`. This is a small performance
74        // win for a few crates, and a huge performance win for the crate in
75        // https://github.com/rust-lang/rustc-perf/pull/1680, which greatly
76        // stresses the trait system.
77        self.param_env == other.param_env && self.predicate == other.predicate
78    }
79}
80
81impl<T: Eq> Eq for Obligation<'_, T> {}
82
83impl<T: Hash> Hash for Obligation<'_, T> {
84    fn hash<H: Hasher>(&self, state: &mut H) -> () {
85        // See the comment on `Obligation::eq`.
86        self.param_env.hash(state);
87        self.predicate.hash(state);
88    }
89}
90
91pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
92pub type TraitObligation<'tcx> = Obligation<'tcx, ty::TraitClause<'tcx>>;
93pub type PolyTraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitClause<'tcx>>;
94
95pub type PredicateObligations<'tcx> = ThinVec<PredicateObligation<'tcx>>;
96
97impl<'tcx> PredicateObligation<'tcx> {
98    /// Flips the polarity of the inner predicate.
99    ///
100    /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
101    pub fn flip_polarity(&self, tcx: TyCtxt<'tcx>) -> Option<PredicateObligation<'tcx>> {
102        Some(PredicateObligation {
103            cause: self.cause.clone(),
104            param_env: self.param_env,
105            predicate: self.predicate.flip_polarity(tcx)?,
106            recursion_depth: self.recursion_depth,
107        })
108    }
109}
110
111impl<'tcx> PolyTraitObligation<'tcx> {
112    pub fn derived_cause(
113        &self,
114        variant: impl FnOnce(DerivedCause<'tcx>) -> ObligationCauseCode<'tcx>,
115    ) -> ObligationCause<'tcx> {
116        self.cause.clone().derived_cause(self.predicate, variant)
117    }
118}
119
120// `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
121#[cfg(target_pointer_width = "64")]
122const _: [(); 48] = [(); ::std::mem::size_of::<PredicateObligation<'_>>()];rustc_data_structures::static_assert_size!(PredicateObligation<'_>, 48);
123
124pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>;
125
126/// A callback that can be provided to `inspect_typeck`. Invoked on evaluation
127/// of root obligations.
128pub type ObligationInspector<'tcx> =
129    fn(&InferCtxt<'tcx>, &PredicateObligation<'tcx>, Result<Certainty, NoSolution>);
130
131impl<'tcx, O> Obligation<'tcx, O> {
132    pub fn new(
133        tcx: TyCtxt<'tcx>,
134        cause: ObligationCause<'tcx>,
135        param_env: ty::ParamEnv<'tcx>,
136        predicate: impl Upcast<TyCtxt<'tcx>, O>,
137    ) -> Obligation<'tcx, O> {
138        Self::with_depth(tcx, cause, 0, param_env, predicate)
139    }
140
141    /// We often create nested obligations without setting the correct depth.
142    ///
143    /// To deal with this evaluate and fulfill explicitly update the depth
144    /// of nested obligations using this function.
145    pub fn set_depth_from_parent(&mut self, parent_depth: usize) {
146        self.recursion_depth = cmp::max(parent_depth + 1, self.recursion_depth);
147    }
148
149    pub fn with_depth(
150        tcx: TyCtxt<'tcx>,
151        cause: ObligationCause<'tcx>,
152        recursion_depth: usize,
153        param_env: ty::ParamEnv<'tcx>,
154        predicate: impl Upcast<TyCtxt<'tcx>, O>,
155    ) -> Obligation<'tcx, O> {
156        let predicate = predicate.upcast(tcx);
157        Obligation { cause, param_env, recursion_depth, predicate }
158    }
159
160    pub fn misc(
161        tcx: TyCtxt<'tcx>,
162        span: Span,
163        body_def_id: LocalDefId,
164        param_env: ty::ParamEnv<'tcx>,
165        trait_ref: impl Upcast<TyCtxt<'tcx>, O>,
166    ) -> Obligation<'tcx, O> {
167        Obligation::new(tcx, ObligationCause::misc(span, body_def_id), param_env, trait_ref)
168    }
169
170    pub fn with<P>(
171        &self,
172        tcx: TyCtxt<'tcx>,
173        value: impl Upcast<TyCtxt<'tcx>, P>,
174    ) -> Obligation<'tcx, P> {
175        Obligation::with_depth(tcx, self.cause.clone(), self.recursion_depth, self.param_env, value)
176    }
177}
178
179impl<'tcx> PolyTraitObligation<'tcx> {
180    pub fn polarity(&self) -> ty::ClausePolarity {
181        self.predicate.skip_binder().polarity
182    }
183
184    pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
185        self.predicate.map_bound(|p| p.self_ty())
186    }
187}