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 
5 mod engine;
6 pub mod error_reporting;
7 mod project;
8 mod structural_impls;
9 pub mod util;
10 
11 use rustc_hir as hir;
12 use rustc_middle::ty::error::{ExpectedFound, TypeError};
13 use rustc_middle::ty::{self, Const, Ty, TyCtxt};
14 use rustc_span::Span;
15 
16 pub use self::FulfillmentErrorCode::*;
17 pub use self::ImplSource::*;
18 pub use self::ObligationCauseCode::*;
19 pub use self::SelectionError::*;
20 
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,
27 };
28 pub use rustc_middle::traits::*;
29 
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>,
40 
41     /// The environment in which we should prove this thing.
42     pub param_env: ty::ParamEnv<'tcx>,
43 
44     /// The thing we are trying to prove.
45     pub predicate: T,
46 
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,
53 }
54 
55 pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
56 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
57 
58 impl PredicateObligation<'tcx> {
59     /// Flips the polarity of the inner predicate.
60     ///
61     /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
flip_polarity(&self, tcx: TyCtxt<'tcx>) -> Option<PredicateObligation<'tcx>>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,
68         })
69     }
70 }
71 
72 // `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
73 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
74 static_assert_size!(PredicateObligation<'_>, 32);
75 
76 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
77 
78 pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>;
79 
80 pub struct FulfillmentError<'tcx> {
81     pub obligation: PredicateObligation<'tcx>,
82     pub code: FulfillmentErrorCode<'tcx>,
83     /// Diagnostics only: the 'root' obligation which resulted in
84     /// the failure to process `obligation`. This is the obligation
85     /// that was initially passed to `register_predicate_obligation`
86     pub root_obligation: PredicateObligation<'tcx>,
87 }
88 
89 #[derive(Clone)]
90 pub enum FulfillmentErrorCode<'tcx> {
91     CodeSelectionError(SelectionError<'tcx>),
92     CodeProjectionError(MismatchedProjectionTypes<'tcx>),
93     CodeSubtypeError(ExpectedFound<Ty<'tcx>>, TypeError<'tcx>), // always comes from a SubtypePredicate
94     CodeConstEquateError(ExpectedFound<&'tcx Const<'tcx>>, TypeError<'tcx>),
95     CodeAmbiguity,
96 }
97 
98 impl<'tcx, O> Obligation<'tcx, O> {
new( cause: ObligationCause<'tcx>, param_env: ty::ParamEnv<'tcx>, predicate: O, ) -> Obligation<'tcx, O>99     pub fn new(
100         cause: ObligationCause<'tcx>,
101         param_env: ty::ParamEnv<'tcx>,
102         predicate: O,
103     ) -> Obligation<'tcx, O> {
104         Obligation { cause, param_env, recursion_depth: 0, predicate }
105     }
106 
with_depth( cause: ObligationCause<'tcx>, recursion_depth: usize, param_env: ty::ParamEnv<'tcx>, predicate: O, ) -> Obligation<'tcx, O>107     pub fn with_depth(
108         cause: ObligationCause<'tcx>,
109         recursion_depth: usize,
110         param_env: ty::ParamEnv<'tcx>,
111         predicate: O,
112     ) -> Obligation<'tcx, O> {
113         Obligation { cause, param_env, recursion_depth, predicate }
114     }
115 
misc( span: Span, body_id: hir::HirId, param_env: ty::ParamEnv<'tcx>, trait_ref: O, ) -> Obligation<'tcx, O>116     pub fn misc(
117         span: Span,
118         body_id: hir::HirId,
119         param_env: ty::ParamEnv<'tcx>,
120         trait_ref: O,
121     ) -> Obligation<'tcx, O> {
122         Obligation::new(ObligationCause::misc(span, body_id), param_env, trait_ref)
123     }
124 
with<P>(&self, value: P) -> Obligation<'tcx, P>125     pub fn with<P>(&self, value: P) -> Obligation<'tcx, P> {
126         Obligation {
127             cause: self.cause.clone(),
128             param_env: self.param_env,
129             recursion_depth: self.recursion_depth,
130             predicate: value,
131         }
132     }
133 }
134 
135 impl<'tcx> FulfillmentError<'tcx> {
new( obligation: PredicateObligation<'tcx>, code: FulfillmentErrorCode<'tcx>, root_obligation: PredicateObligation<'tcx>, ) -> FulfillmentError<'tcx>136     pub fn new(
137         obligation: PredicateObligation<'tcx>,
138         code: FulfillmentErrorCode<'tcx>,
139         root_obligation: PredicateObligation<'tcx>,
140     ) -> FulfillmentError<'tcx> {
141         FulfillmentError { obligation, code, root_obligation }
142     }
143 }
144 
145 impl<'tcx> TraitObligation<'tcx> {
polarity(&self) -> ty::ImplPolarity146     pub fn polarity(&self) -> ty::ImplPolarity {
147         self.predicate.skip_binder().polarity
148     }
149 
self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>>150     pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
151         self.predicate.map_bound(|p| p.self_ty())
152     }
153 }
154