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, ToPredicate, 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     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())));
  75         }
  76         self
  77     }
  78 }
  79
  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,
  85             _ => false,
  86         }
  87     }
  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     }
  95 }
  96
  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);
 100
 101 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
 102
 103 pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>;
 104
 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>,
 112 }
 113
 114 #[derive(Clone)]
 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>),
 122     CodeAmbiguity,
 123 }
 124
 125 impl<'tcx, O> Obligation<'tcx, O> {
 126     pub fn new(
 127         tcx: TyCtxt<'tcx>,
 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)
 133     }
 134
 135     pub fn with_depth(
 136         tcx: TyCtxt<'tcx>,
 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 }
 144     }
 145
 146     pub fn misc(
 147         tcx: TyCtxt<'tcx>,
 148         span: Span,
 149         body_id: hir::HirId,
 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)
 154     }
 155
 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)
 162     }
 163 }
 164
 165 impl<'tcx> FulfillmentError<'tcx> {
 166     pub fn new(
 167         obligation: PredicateObligation<'tcx>,
 168         code: FulfillmentErrorCode<'tcx>,
 169         root_obligation: PredicateObligation<'tcx>,
 170     ) -> FulfillmentError<'tcx> {
 171         FulfillmentError { obligation, code, root_obligation }
 172     }
 173 }
 174
 175 impl<'tcx> TraitObligation<'tcx> {
 176     pub fn polarity(&self) -> ty::ImplPolarity {
 177         self.predicate.skip_binder().polarity
 178     }
 179
 180     pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
 181         self.predicate.map_bound(|p| p.self_ty())
 182     }
 183 }