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