compiler/rustc_infer/src/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
   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<'tcx> 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`.
  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 impl<'tcx> TraitObligation<'tcx> {
  73     /// Returns `true` if the trait predicate is considered `const` in its ParamEnv.
  74     pub fn is_const(&self) -> bool {
  75         match (self.predicate.skip_binder().constness, self.param_env.constness()) {
  76             (ty::BoundConstness::ConstIfConst, hir::Constness::Const) => true,
  77             _ => false,
  78         }
  79     }
  80
  81     pub fn derived_cause(
  82         &self,
  83         variant: impl FnOnce(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>,
  84     ) -> ObligationCause<'tcx> {
  85         self.cause.clone().derived_cause(self.predicate, variant)
  86     }
  87 }
  88
  89 // `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
  90 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
  91 static_assert_size!(PredicateObligation<'_>, 48);
  92
  93 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
  94
  95 pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>;
  96
  97 pub struct FulfillmentError<'tcx> {
  98     pub obligation: PredicateObligation<'tcx>,
  99     pub code: FulfillmentErrorCode<'tcx>,
 100     /// Diagnostics only: the 'root' obligation which resulted in
 101     /// the failure to process `obligation`. This is the obligation
 102     /// that was initially passed to `register_predicate_obligation`
 103     pub root_obligation: PredicateObligation<'tcx>,
 104 }
 105
 106 #[derive(Clone)]
 107 pub enum FulfillmentErrorCode<'tcx> {
 108     CodeSelectionError(SelectionError<'tcx>),
 109     CodeProjectionError(MismatchedProjectionTypes<'tcx>),
 110     CodeSubtypeError(ExpectedFound<Ty<'tcx>>, TypeError<'tcx>), // always comes from a SubtypePredicate
 111     CodeConstEquateError(ExpectedFound<Const<'tcx>>, TypeError<'tcx>),
 112     CodeAmbiguity,
 113 }
 114
 115 impl<'tcx, O> Obligation<'tcx, O> {
 116     pub fn new(
 117         cause: ObligationCause<'tcx>,
 118         param_env: ty::ParamEnv<'tcx>,
 119         predicate: O,
 120     ) -> Obligation<'tcx, O> {
 121         Obligation { cause, param_env, recursion_depth: 0, predicate }
 122     }
 123
 124     pub fn with_depth(
 125         cause: ObligationCause<'tcx>,
 126         recursion_depth: usize,
 127         param_env: ty::ParamEnv<'tcx>,
 128         predicate: O,
 129     ) -> Obligation<'tcx, O> {
 130         Obligation { cause, param_env, recursion_depth, predicate }
 131     }
 132
 133     pub fn misc(
 134         span: Span,
 135         body_id: hir::HirId,
 136         param_env: ty::ParamEnv<'tcx>,
 137         trait_ref: O,
 138     ) -> Obligation<'tcx, O> {
 139         Obligation::new(ObligationCause::misc(span, body_id), param_env, trait_ref)
 140     }
 141
 142     pub fn with<P>(&self, value: P) -> Obligation<'tcx, P> {
 143         Obligation {
 144             cause: self.cause.clone(),
 145             param_env: self.param_env,
 146             recursion_depth: self.recursion_depth,
 147             predicate: value,
 148         }
 149     }
 150 }
 151
 152 impl<'tcx> FulfillmentError<'tcx> {
 153     pub fn new(
 154         obligation: PredicateObligation<'tcx>,
 155         code: FulfillmentErrorCode<'tcx>,
 156         root_obligation: PredicateObligation<'tcx>,
 157     ) -> FulfillmentError<'tcx> {
 158         FulfillmentError { obligation, code, root_obligation }
 159     }
 160 }
 161
 162 impl<'tcx> TraitObligation<'tcx> {
 163     pub fn polarity(&self) -> ty::ImplPolarity {
 164         self.predicate.skip_binder().polarity
 165     }
 166
 167     pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
 168         self.predicate.map_bound(|p| p.self_ty())
 169     }
 170 }