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

rustc_infer/traits/
mod.rs
