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::ImplSource::*;
24pub use self::SelectionError::*;
25pub use self::engine::{FromSolverError, ScrubbedTraitError, TraitEngine};
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(Clone, TypeFoldable, TypeVisitable)]
40pub struct Obligation<'tcx, T> {
41    /// The reason we have to prove this thing.
42    #[type_foldable(identity)]
43    #[type_visitable(ignore)]
44    pub cause: ObligationCause<'tcx>,
45
46    /// The environment in which we should prove this thing.
47    pub param_env: ty::ParamEnv<'tcx>,
48
49    /// The thing we are trying to prove.
50    pub predicate: T,
51
52    /// If we started proving this as a result of trying to prove
53    /// something else, track the total depth to ensure termination.
54    /// If this goes over a certain threshold, we abort compilation --
55    /// in such cases, we can not say whether or not the predicate
56    /// holds for certain. Stupid halting problem; such a drag.
57    #[type_foldable(identity)]
58    #[type_visitable(ignore)]
59    pub recursion_depth: usize,
60}
61
62impl<'tcx, T: Copy> Obligation<'tcx, T> {
63    pub fn as_goal(&self) -> solve::Goal<'tcx, T> {
64        solve::Goal { param_env: self.param_env, predicate: self.predicate }
65    }
66}
67
68impl<'tcx, T: PartialEq> PartialEq<Obligation<'tcx, T>> for Obligation<'tcx, T> {
69    #[inline]
70    fn eq(&self, other: &Obligation<'tcx, T>) -> bool {
71        // Ignore `cause` and `recursion_depth`. This is a small performance
72        // win for a few crates, and a huge performance win for the crate in
73        // https://github.com/rust-lang/rustc-perf/pull/1680, which greatly
74        // stresses the trait system.
75        self.param_env == other.param_env && self.predicate == other.predicate
76    }
77}
78
79impl<T: Eq> Eq for Obligation<'_, T> {}
80
81impl<T: Hash> Hash for Obligation<'_, T> {
82    fn hash<H: Hasher>(&self, state: &mut H) -> () {
83        // See the comment on `Obligation::eq`.
84        self.param_env.hash(state);
85        self.predicate.hash(state);
86    }
87}
88
89pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
90pub type TraitObligation<'tcx> = Obligation<'tcx, ty::TraitPredicate<'tcx>>;
91pub type PolyTraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
92
93pub type PredicateObligations<'tcx> = ThinVec<PredicateObligation<'tcx>>;
94
95impl<'tcx> PredicateObligation<'tcx> {
96    /// Flips the polarity of the inner predicate.
97    ///
98    /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
99    pub fn flip_polarity(&self, tcx: TyCtxt<'tcx>) -> Option<PredicateObligation<'tcx>> {
100        Some(PredicateObligation {
101            cause: self.cause.clone(),
102            param_env: self.param_env,
103            predicate: self.predicate.flip_polarity(tcx)?,
104            recursion_depth: self.recursion_depth,
105        })
106    }
107}
108
109impl<'tcx> PolyTraitObligation<'tcx> {
110    pub fn derived_cause(
111        &self,
112        variant: impl FnOnce(DerivedCause<'tcx>) -> ObligationCauseCode<'tcx>,
113    ) -> ObligationCause<'tcx> {
114        self.cause.clone().derived_cause(self.predicate, variant)
115    }
116}
117
118// `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
119#[cfg(target_pointer_width = "64")]
120rustc_data_structures::static_assert_size!(PredicateObligation<'_>, 48);
121
122pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>;
123
124/// A callback that can be provided to `inspect_typeck`. Invoked on evaluation
125/// of root obligations.
126pub type ObligationInspector<'tcx> =
127    fn(&InferCtxt<'tcx>, &PredicateObligation<'tcx>, Result<Certainty, NoSolution>);
128
129impl<'tcx, O> Obligation<'tcx, O> {
130    pub fn new(
131        tcx: TyCtxt<'tcx>,
132        cause: ObligationCause<'tcx>,
133        param_env: ty::ParamEnv<'tcx>,
134        predicate: impl Upcast<TyCtxt<'tcx>, O>,
135    ) -> Obligation<'tcx, O> {
136        Self::with_depth(tcx, cause, 0, param_env, predicate)
137    }
138
139    /// We often create nested obligations without setting the correct depth.
140    ///
141    /// To deal with this evaluate and fulfill explicitly update the depth
142    /// of nested obligations using this function.
143    pub fn set_depth_from_parent(&mut self, parent_depth: usize) {
144        self.recursion_depth = cmp::max(parent_depth + 1, self.recursion_depth);
145    }
146
147    pub fn with_depth(
148        tcx: TyCtxt<'tcx>,
149        cause: ObligationCause<'tcx>,
150        recursion_depth: usize,
151        param_env: ty::ParamEnv<'tcx>,
152        predicate: impl Upcast<TyCtxt<'tcx>, O>,
153    ) -> Obligation<'tcx, O> {
154        let predicate = predicate.upcast(tcx);
155        Obligation { cause, param_env, recursion_depth, predicate }
156    }
157
158    pub fn misc(
159        tcx: TyCtxt<'tcx>,
160        span: Span,
161        body_id: LocalDefId,
162        param_env: ty::ParamEnv<'tcx>,
163        trait_ref: impl Upcast<TyCtxt<'tcx>, O>,
164    ) -> Obligation<'tcx, O> {
165        Obligation::new(tcx, ObligationCause::misc(span, body_id), param_env, trait_ref)
166    }
167
168    pub fn with<P>(
169        &self,
170        tcx: TyCtxt<'tcx>,
171        value: impl Upcast<TyCtxt<'tcx>, P>,
172    ) -> Obligation<'tcx, P> {
173        Obligation::with_depth(tcx, self.cause.clone(), self.recursion_depth, self.param_env, value)
174    }
175}
176
177impl<'tcx> PolyTraitObligation<'tcx> {
178    pub fn polarity(&self) -> ty::PredicatePolarity {
179        self.predicate.skip_binder().polarity
180    }
181
182    pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
183        self.predicate.map_bound(|p| p.self_ty())
184    }
185}
rustc_infer/traits/mod.rs

rustc_infer/traits/
mod.rs
