1 //! Trait Resolution. See the [rustc-dev-guide] for more information on how this works.
3 //! [rustc-dev-guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html
6 pub mod error_reporting;
12 use rustc_middle::ty::error::{ExpectedFound, TypeError};
13 use rustc_middle::ty::{self, Const, ToPredicate, Ty, TyCtxt};
16 pub use self::FulfillmentErrorCode::*;
17 pub use self::ImplSource::*;
18 pub use self::ObligationCauseCode::*;
19 pub use self::SelectionError::*;
21 pub use self::engine::{TraitEngine, TraitEngineExt};
22 pub use self::project::MismatchedProjectionTypes;
23 pub(crate) use self::project::UndoLog;
24 pub use self::project::{
25 Normalized, NormalizedTy, ProjectionCache, ProjectionCacheEntry, ProjectionCacheKey,
26 ProjectionCacheStorage, Reveal,
28 pub use rustc_middle::traits::*;
30 /// An `Obligation` represents some trait reference (e.g., `i32: Eq`) for
31 /// which the "impl_source" must be found. The process of finding an "impl_source" is
32 /// called "resolving" the `Obligation`. This process consists of
33 /// either identifying an `impl` (e.g., `impl Eq for i32`) that
34 /// satisfies the obligation, or else finding a bound that is in
35 /// scope. The eventual result is usually a `Selection` (defined below).
36 #[derive(Clone, PartialEq, Eq, Hash)]
37 pub struct Obligation<'tcx, T> {
38 /// The reason we have to prove this thing.
39 pub cause: ObligationCause<'tcx>,
41 /// The environment in which we should prove this thing.
42 pub param_env: ty::ParamEnv<'tcx>,
44 /// The thing we are trying to prove.
47 /// If we started proving this as a result of trying to prove
48 /// something else, track the total depth to ensure termination.
49 /// If this goes over a certain threshold, we abort compilation --
50 /// in such cases, we can not say whether or not the predicate
51 /// holds for certain. Stupid halting problem; such a drag.
52 pub recursion_depth: usize,
55 pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
56 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
58 impl<'tcx> PredicateObligation<'tcx> {
59 /// Flips the polarity of the inner predicate.
61 /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
62 pub fn flip_polarity(&self, tcx: TyCtxt<'tcx>) -> Option<PredicateObligation<'tcx>> {
63 Some(PredicateObligation {
64 cause: self.cause.clone(),
65 param_env: self.param_env,
66 predicate: self.predicate.flip_polarity(tcx)?,
67 recursion_depth: self.recursion_depth,
71 pub fn without_const(mut self, tcx: TyCtxt<'tcx>) -> PredicateObligation<'tcx> {
72 self.param_env = self.param_env.without_const();
73 if let ty::PredicateKind::Trait(trait_pred) = self.predicate.kind().skip_binder() && trait_pred.is_const_if_const() {
74 self.predicate = tcx.mk_predicate(self.predicate.kind().map_bound(|_| ty::PredicateKind::Trait(trait_pred.without_const())));
80 impl<'tcx> TraitObligation<'tcx> {
81 /// Returns `true` if the trait predicate is considered `const` in its ParamEnv.
82 pub fn is_const(&self) -> bool {
83 match (self.predicate.skip_binder().constness, self.param_env.constness()) {
84 (ty::BoundConstness::ConstIfConst, hir::Constness::Const) => true,
91 variant: impl FnOnce(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>,
92 ) -> ObligationCause<'tcx> {
93 self.cause.clone().derived_cause(self.predicate, variant)
97 // `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
98 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
99 static_assert_size!(PredicateObligation<'_>, 48);
101 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
103 pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>;
105 pub struct FulfillmentError<'tcx> {
106 pub obligation: PredicateObligation<'tcx>,
107 pub code: FulfillmentErrorCode<'tcx>,
108 /// Diagnostics only: the 'root' obligation which resulted in
109 /// the failure to process `obligation`. This is the obligation
110 /// that was initially passed to `register_predicate_obligation`
111 pub root_obligation: PredicateObligation<'tcx>,
115 pub enum FulfillmentErrorCode<'tcx> {
116 /// Inherently impossible to fulfill; this trait is implemented if and only if it is already implemented.
117 CodeCycle(Vec<Obligation<'tcx, ty::Predicate<'tcx>>>),
118 CodeSelectionError(SelectionError<'tcx>),
119 CodeProjectionError(MismatchedProjectionTypes<'tcx>),
120 CodeSubtypeError(ExpectedFound<Ty<'tcx>>, TypeError<'tcx>), // always comes from a SubtypePredicate
121 CodeConstEquateError(ExpectedFound<Const<'tcx>>, TypeError<'tcx>),
125 impl<'tcx, O> Obligation<'tcx, O> {
128 cause: ObligationCause<'tcx>,
129 param_env: ty::ParamEnv<'tcx>,
130 predicate: impl ToPredicate<'tcx, O>,
131 ) -> Obligation<'tcx, O> {
132 Self::with_depth(tcx, cause, 0, param_env, predicate)
137 cause: ObligationCause<'tcx>,
138 recursion_depth: usize,
139 param_env: ty::ParamEnv<'tcx>,
140 predicate: impl ToPredicate<'tcx, O>,
141 ) -> Obligation<'tcx, O> {
142 let predicate = predicate.to_predicate(tcx);
143 Obligation { cause, param_env, recursion_depth, predicate }
150 param_env: ty::ParamEnv<'tcx>,
151 trait_ref: impl ToPredicate<'tcx, O>,
152 ) -> Obligation<'tcx, O> {
153 Obligation::new(tcx, ObligationCause::misc(span, body_id), param_env, trait_ref)
159 value: impl ToPredicate<'tcx, P>,
160 ) -> Obligation<'tcx, P> {
161 Obligation::with_depth(tcx, self.cause.clone(), self.recursion_depth, self.param_env, value)
165 impl<'tcx> FulfillmentError<'tcx> {
167 obligation: PredicateObligation<'tcx>,
168 code: FulfillmentErrorCode<'tcx>,
169 root_obligation: PredicateObligation<'tcx>,
170 ) -> FulfillmentError<'tcx> {
171 FulfillmentError { obligation, code, root_obligation }
175 impl<'tcx> TraitObligation<'tcx> {
176 pub fn polarity(&self) -> ty::ImplPolarity {
177 self.predicate.skip_binder().polarity
180 pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
181 self.predicate.map_bound(|p| p.self_ty())