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 std::cmp;
  12
  13 use hir::def_id::LocalDefId;
  14 use rustc_hir as hir;
  15 use rustc_middle::ty::error::{ExpectedFound, TypeError};
  16 use rustc_middle::ty::{self, Const, ToPredicate, Ty, TyCtxt};
  17 use rustc_span::Span;
  18
  19 pub use self::FulfillmentErrorCode::*;
  20 pub use self::ImplSource::*;
  21 pub use self::ObligationCauseCode::*;
  22 pub use self::SelectionError::*;
  23
  24 pub use self::engine::{TraitEngine, TraitEngineExt};
  25 pub use self::project::MismatchedProjectionTypes;
  26 pub(crate) use self::project::UndoLog;
  27 pub use self::project::{
  28     Normalized, NormalizedTy, ProjectionCache, ProjectionCacheEntry, ProjectionCacheKey,
  29     ProjectionCacheStorage, Reveal,
  30 };
  31 pub use rustc_middle::traits::*;
  32
  33 /// An `Obligation` represents some trait reference (e.g., `i32: Eq`) for
  34 /// which the "impl_source" must be found. The process of finding an "impl_source" is
  35 /// called "resolving" the `Obligation`. This process consists of
  36 /// either identifying an `impl` (e.g., `impl Eq for i32`) that
  37 /// satisfies the obligation, or else finding a bound that is in
  38 /// scope. The eventual result is usually a `Selection` (defined below).
  39 #[derive(Clone, PartialEq, Eq, Hash)]
  40 pub struct Obligation<'tcx, T> {
  41     /// The reason we have to prove this thing.
  42     pub cause: ObligationCause<'tcx>,
  43
  44     /// The environment in which we should prove this thing.
  45     pub param_env: ty::ParamEnv<'tcx>,
  46
  47     /// The thing we are trying to prove.
  48     pub predicate: T,
  49
  50     /// If we started proving this as a result of trying to prove
  51     /// something else, track the total depth to ensure termination.
  52     /// If this goes over a certain threshold, we abort compilation --
  53     /// in such cases, we can not say whether or not the predicate
  54     /// holds for certain. Stupid halting problem; such a drag.
  55     pub recursion_depth: usize,
  56 }
  57
  58 impl<'tcx, P> From<Obligation<'tcx, P>> for solve::Goal<'tcx, P> {
  59     fn from(value: Obligation<'tcx, P>) -> Self {
  60         solve::Goal { param_env: value.param_env, predicate: value.predicate }
  61     }
  62 }
  63
  64 pub type PredicateObligation<'tcx> = Obligation<'tcx, ty::Predicate<'tcx>>;
  65 pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
  66
  67 impl<'tcx> PredicateObligation<'tcx> {
  68     /// Flips the polarity of the inner predicate.
  69     ///
  70     /// Given `T: Trait` predicate it returns `T: !Trait` and given `T: !Trait` returns `T: Trait`.
  71     pub fn flip_polarity(&self, tcx: TyCtxt<'tcx>) -> Option<PredicateObligation<'tcx>> {
  72         Some(PredicateObligation {
  73             cause: self.cause.clone(),
  74             param_env: self.param_env,
  75             predicate: self.predicate.flip_polarity(tcx)?,
  76             recursion_depth: self.recursion_depth,
  77         })
  78     }
  79
  80     pub fn without_const(mut self, tcx: TyCtxt<'tcx>) -> PredicateObligation<'tcx> {
  81         self.param_env = self.param_env.without_const();
  82         if let ty::PredicateKind::Clause(ty::Clause::Trait(trait_pred)) = self.predicate.kind().skip_binder() && trait_pred.is_const_if_const() {
  83             self.predicate = tcx.mk_predicate(self.predicate.kind().map_bound(|_| ty::PredicateKind::Clause(ty::Clause::Trait(trait_pred.without_const()))));
  84         }
  85         self
  86     }
  87 }
  88
  89 impl<'tcx> TraitObligation<'tcx> {
  90     /// Returns `true` if the trait predicate is considered `const` in its ParamEnv.
  91     pub fn is_const(&self) -> bool {
  92         match (self.predicate.skip_binder().constness, self.param_env.constness()) {
  93             (ty::BoundConstness::ConstIfConst, hir::Constness::Const) => true,
  94             _ => false,
  95         }
  96     }
  97
  98     pub fn derived_cause(
  99         &self,
 100         variant: impl FnOnce(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>,
 101     ) -> ObligationCause<'tcx> {
 102         self.cause.clone().derived_cause(self.predicate, variant)
 103     }
 104 }
 105
 106 // `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
 107 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
 108 static_assert_size!(PredicateObligation<'_>, 48);
 109
 110 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
 111
 112 pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>;
 113
 114 pub struct FulfillmentError<'tcx> {
 115     pub obligation: PredicateObligation<'tcx>,
 116     pub code: FulfillmentErrorCode<'tcx>,
 117     /// Diagnostics only: the 'root' obligation which resulted in
 118     /// the failure to process `obligation`. This is the obligation
 119     /// that was initially passed to `register_predicate_obligation`
 120     pub root_obligation: PredicateObligation<'tcx>,
 121 }
 122
 123 #[derive(Clone)]
 124 pub enum FulfillmentErrorCode<'tcx> {
 125     /// Inherently impossible to fulfill; this trait is implemented if and only if it is already implemented.
 126     CodeCycle(Vec<Obligation<'tcx, ty::Predicate<'tcx>>>),
 127     CodeSelectionError(SelectionError<'tcx>),
 128     CodeProjectionError(MismatchedProjectionTypes<'tcx>),
 129     CodeSubtypeError(ExpectedFound<Ty<'tcx>>, TypeError<'tcx>), // always comes from a SubtypePredicate
 130     CodeConstEquateError(ExpectedFound<Const<'tcx>>, TypeError<'tcx>),
 131     CodeAmbiguity {
 132         /// Overflow reported from the new solver `-Ztrait-solver=next`, which will
 133         /// be reported as an regular error as opposed to a fatal error.
 134         overflow: bool,
 135     },
 136 }
 137
 138 impl<'tcx, O> Obligation<'tcx, O> {
 139     pub fn new(
 140         tcx: TyCtxt<'tcx>,
 141         cause: ObligationCause<'tcx>,
 142         param_env: ty::ParamEnv<'tcx>,
 143         predicate: impl ToPredicate<'tcx, O>,
 144     ) -> Obligation<'tcx, O> {
 145         Self::with_depth(tcx, cause, 0, param_env, predicate)
 146     }
 147
 148     /// We often create nested obligations without setting the correct depth.
 149     ///
 150     /// To deal with this evaluate and fulfill explicitly update the depth
 151     /// of nested obligations using this function.
 152     pub fn set_depth_from_parent(&mut self, parent_depth: usize) {
 153         self.recursion_depth = cmp::max(parent_depth + 1, self.recursion_depth);
 154     }
 155
 156     pub fn with_depth(
 157         tcx: TyCtxt<'tcx>,
 158         cause: ObligationCause<'tcx>,
 159         recursion_depth: usize,
 160         param_env: ty::ParamEnv<'tcx>,
 161         predicate: impl ToPredicate<'tcx, O>,
 162     ) -> Obligation<'tcx, O> {
 163         let predicate = predicate.to_predicate(tcx);
 164         Obligation { cause, param_env, recursion_depth, predicate }
 165     }
 166
 167     pub fn misc(
 168         tcx: TyCtxt<'tcx>,
 169         span: Span,
 170         body_id: LocalDefId,
 171         param_env: ty::ParamEnv<'tcx>,
 172         trait_ref: impl ToPredicate<'tcx, O>,
 173     ) -> Obligation<'tcx, O> {
 174         Obligation::new(tcx, ObligationCause::misc(span, body_id), param_env, trait_ref)
 175     }
 176
 177     pub fn with<P>(
 178         &self,
 179         tcx: TyCtxt<'tcx>,
 180         value: impl ToPredicate<'tcx, P>,
 181     ) -> Obligation<'tcx, P> {
 182         Obligation::with_depth(tcx, self.cause.clone(), self.recursion_depth, self.param_env, value)
 183     }
 184 }
 185
 186 impl<'tcx> FulfillmentError<'tcx> {
 187     pub fn new(
 188         obligation: PredicateObligation<'tcx>,
 189         code: FulfillmentErrorCode<'tcx>,
 190         root_obligation: PredicateObligation<'tcx>,
 191     ) -> FulfillmentError<'tcx> {
 192         FulfillmentError { obligation, code, root_obligation }
 193     }
 194 }
 195
 196 impl<'tcx> TraitObligation<'tcx> {
 197     pub fn polarity(&self) -> ty::ImplPolarity {
 198         self.predicate.skip_binder().polarity
 199     }
 200
 201     pub fn self_ty(&self) -> ty::Binder<'tcx, Ty<'tcx>> {
 202         self.predicate.map_bound(|p| p.self_ty())
 203     }
 204 }