]>
Commit | Line | Data |
---|---|---|
ba9703b0 | 1 | //! Trait Resolution. See the [rustc-dev-guide] for more information on how this works. |
74b04a01 | 2 | //! |
ba9703b0 | 3 | //! [rustc-dev-guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html |
74b04a01 | 4 | |
74b04a01 XL |
5 | mod engine; |
6 | pub mod error_reporting; | |
74b04a01 | 7 | mod project; |
74b04a01 | 8 | mod structural_impls; |
ba9703b0 | 9 | pub mod util; |
74b04a01 | 10 | |
74b04a01 | 11 | use rustc_hir as hir; |
ba9703b0 | 12 | use rustc_middle::ty::error::{ExpectedFound, TypeError}; |
487cf647 | 13 | use rustc_middle::ty::{self, Const, ToPredicate, Ty, TyCtxt}; |
ba9703b0 | 14 | use rustc_span::Span; |
74b04a01 XL |
15 | |
16 | pub use self::FulfillmentErrorCode::*; | |
f035d41b | 17 | pub use self::ImplSource::*; |
74b04a01 XL |
18 | pub use self::ObligationCauseCode::*; |
19 | pub use self::SelectionError::*; | |
74b04a01 | 20 | |
74b04a01 | 21 | pub use self::engine::{TraitEngine, TraitEngineExt}; |
74b04a01 | 22 | pub use self::project::MismatchedProjectionTypes; |
f9f354fc | 23 | pub(crate) use self::project::UndoLog; |
74b04a01 | 24 | pub use self::project::{ |
ba9703b0 | 25 | Normalized, NormalizedTy, ProjectionCache, ProjectionCacheEntry, ProjectionCacheKey, |
f9f354fc | 26 | ProjectionCacheStorage, Reveal, |
74b04a01 | 27 | }; |
ba9703b0 | 28 | pub use rustc_middle::traits::*; |
74b04a01 | 29 | |
f035d41b | 30 | /// An `Obligation` represents some trait reference (e.g., `i32: Eq`) for |
94222f64 | 31 | /// which the "impl_source" must be found. The process of finding an "impl_source" is |
74b04a01 | 32 | /// called "resolving" the `Obligation`. This process consists of |
f035d41b XL |
33 | /// either identifying an `impl` (e.g., `impl Eq for i32`) that |
34 | /// satisfies the obligation, or else finding a bound that is in | |
74b04a01 XL |
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 | ||
a2a8927a | 58 | impl<'tcx> PredicateObligation<'tcx> { |
3c0e092e XL |
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`. | |
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 | } | |
2b03887a FG |
70 | |
71 | pub fn without_const(mut self, tcx: TyCtxt<'tcx>) -> PredicateObligation<'tcx> { | |
72 | self.param_env = self.param_env.without_const(); | |
487cf647 FG |
73 | if let ty::PredicateKind::Clause(ty::Clause::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::Clause(ty::Clause::Trait(trait_pred.without_const())))); | |
2b03887a FG |
75 | } |
76 | self | |
77 | } | |
3c0e092e XL |
78 | } |
79 | ||
923072b8 | 80 | impl<'tcx> TraitObligation<'tcx> { |
a2a8927a XL |
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, | |
85 | _ => false, | |
86 | } | |
87 | } | |
923072b8 FG |
88 | |
89 | pub fn derived_cause( | |
90 | &self, | |
91 | variant: impl FnOnce(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>, | |
92 | ) -> ObligationCause<'tcx> { | |
93 | self.cause.clone().derived_cause(self.predicate, variant) | |
94 | } | |
a2a8927a XL |
95 | } |
96 | ||
74b04a01 | 97 | // `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger. |
6a06907d | 98 | #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))] |
a2a8927a | 99 | static_assert_size!(PredicateObligation<'_>, 48); |
74b04a01 | 100 | |
74b04a01 | 101 | pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>; |
74b04a01 | 102 | |
f035d41b | 103 | pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>; |
74b04a01 XL |
104 | |
105 | pub struct FulfillmentError<'tcx> { | |
106 | pub obligation: PredicateObligation<'tcx>, | |
107 | pub code: FulfillmentErrorCode<'tcx>, | |
136023e0 XL |
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>, | |
74b04a01 XL |
112 | } |
113 | ||
114 | #[derive(Clone)] | |
115 | pub enum FulfillmentErrorCode<'tcx> { | |
2b03887a FG |
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>>>), | |
74b04a01 XL |
118 | CodeSelectionError(SelectionError<'tcx>), |
119 | CodeProjectionError(MismatchedProjectionTypes<'tcx>), | |
120 | CodeSubtypeError(ExpectedFound<Ty<'tcx>>, TypeError<'tcx>), // always comes from a SubtypePredicate | |
5099ac24 | 121 | CodeConstEquateError(ExpectedFound<Const<'tcx>>, TypeError<'tcx>), |
74b04a01 XL |
122 | CodeAmbiguity, |
123 | } | |
124 | ||
74b04a01 XL |
125 | impl<'tcx, O> Obligation<'tcx, O> { |
126 | pub fn new( | |
487cf647 | 127 | tcx: TyCtxt<'tcx>, |
74b04a01 XL |
128 | cause: ObligationCause<'tcx>, |
129 | param_env: ty::ParamEnv<'tcx>, | |
487cf647 | 130 | predicate: impl ToPredicate<'tcx, O>, |
74b04a01 | 131 | ) -> Obligation<'tcx, O> { |
487cf647 | 132 | Self::with_depth(tcx, cause, 0, param_env, predicate) |
74b04a01 XL |
133 | } |
134 | ||
ba9703b0 | 135 | pub fn with_depth( |
487cf647 | 136 | tcx: TyCtxt<'tcx>, |
74b04a01 XL |
137 | cause: ObligationCause<'tcx>, |
138 | recursion_depth: usize, | |
139 | param_env: ty::ParamEnv<'tcx>, | |
487cf647 | 140 | predicate: impl ToPredicate<'tcx, O>, |
74b04a01 | 141 | ) -> Obligation<'tcx, O> { |
487cf647 | 142 | let predicate = predicate.to_predicate(tcx); |
74b04a01 XL |
143 | Obligation { cause, param_env, recursion_depth, predicate } |
144 | } | |
145 | ||
146 | pub fn misc( | |
487cf647 | 147 | tcx: TyCtxt<'tcx>, |
74b04a01 XL |
148 | span: Span, |
149 | body_id: hir::HirId, | |
150 | param_env: ty::ParamEnv<'tcx>, | |
487cf647 | 151 | trait_ref: impl ToPredicate<'tcx, O>, |
74b04a01 | 152 | ) -> Obligation<'tcx, O> { |
487cf647 | 153 | Obligation::new(tcx, ObligationCause::misc(span, body_id), param_env, trait_ref) |
74b04a01 XL |
154 | } |
155 | ||
487cf647 FG |
156 | pub fn with<P>( |
157 | &self, | |
158 | tcx: TyCtxt<'tcx>, | |
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) | |
74b04a01 XL |
162 | } |
163 | } | |
164 | ||
165 | impl<'tcx> FulfillmentError<'tcx> { | |
ba9703b0 | 166 | pub fn new( |
74b04a01 XL |
167 | obligation: PredicateObligation<'tcx>, |
168 | code: FulfillmentErrorCode<'tcx>, | |
136023e0 | 169 | root_obligation: PredicateObligation<'tcx>, |
74b04a01 | 170 | ) -> FulfillmentError<'tcx> { |
c295e0f8 | 171 | FulfillmentError { obligation, code, root_obligation } |
74b04a01 XL |
172 | } |
173 | } | |
174 | ||
175 | impl<'tcx> TraitObligation<'tcx> { | |
3c0e092e XL |
176 | pub fn polarity(&self) -> ty::ImplPolarity { |
177 | self.predicate.skip_binder().polarity | |
178 | } | |
179 | ||
cdc7bbd5 | 180 | pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> { |
74b04a01 XL |
181 | self.predicate.map_bound(|p| p.self_ty()) |
182 | } | |
183 | } |