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};
  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 a "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 // `PredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
  59 #[cfg(target_arch = "x86_64")]
  60 static_assert_size!(PredicateObligation<'_>, 40);
  61
  62 pub type Obligations<'tcx, O> = Vec<Obligation<'tcx, O>>;
  63 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
  64 pub type TraitObligations<'tcx> = Vec<TraitObligation<'tcx>>;
  65
  66 pub type Selection<'tcx> = ImplSource<'tcx, PredicateObligation<'tcx>>;
  67
  68 pub struct FulfillmentError<'tcx> {
  69     pub obligation: PredicateObligation<'tcx>,
  70     pub code: FulfillmentErrorCode<'tcx>,
  71     /// Diagnostics only: we opportunistically change the `code.span` when we encounter an
  72     /// obligation error caused by a call argument. When this is the case, we also signal that in
  73     /// this field to ensure accuracy of suggestions.
  74     pub points_at_arg_span: bool,
  75 }
  76
  77 #[derive(Clone)]
  78 pub enum FulfillmentErrorCode<'tcx> {
  79     CodeSelectionError(SelectionError<'tcx>),
  80     CodeProjectionError(MismatchedProjectionTypes<'tcx>),
  81     CodeSubtypeError(ExpectedFound<Ty<'tcx>>, TypeError<'tcx>), // always comes from a SubtypePredicate
  82     CodeConstEquateError(ExpectedFound<&'tcx Const<'tcx>>, TypeError<'tcx>),
  83     CodeAmbiguity,
  84 }
  85
  86 impl<'tcx, O> Obligation<'tcx, O> {
  87     pub fn new(
  88         cause: ObligationCause<'tcx>,
  89         param_env: ty::ParamEnv<'tcx>,
  90         predicate: O,
  91     ) -> Obligation<'tcx, O> {
  92         Obligation { cause, param_env, recursion_depth: 0, predicate }
  93     }
  94
  95     pub fn with_depth(
  96         cause: ObligationCause<'tcx>,
  97         recursion_depth: usize,
  98         param_env: ty::ParamEnv<'tcx>,
  99         predicate: O,
 100     ) -> Obligation<'tcx, O> {
 101         Obligation { cause, param_env, recursion_depth, predicate }
 102     }
 103
 104     pub fn misc(
 105         span: Span,
 106         body_id: hir::HirId,
 107         param_env: ty::ParamEnv<'tcx>,
 108         trait_ref: O,
 109     ) -> Obligation<'tcx, O> {
 110         Obligation::new(ObligationCause::misc(span, body_id), param_env, trait_ref)
 111     }
 112
 113     pub fn with<P>(&self, value: P) -> Obligation<'tcx, P> {
 114         Obligation {
 115             cause: self.cause.clone(),
 116             param_env: self.param_env,
 117             recursion_depth: self.recursion_depth,
 118             predicate: value,
 119         }
 120     }
 121 }
 122
 123 impl<'tcx> FulfillmentError<'tcx> {
 124     pub fn new(
 125         obligation: PredicateObligation<'tcx>,
 126         code: FulfillmentErrorCode<'tcx>,
 127     ) -> FulfillmentError<'tcx> {
 128         FulfillmentError { obligation, code, points_at_arg_span: false }
 129     }
 130 }
 131
 132 impl<'tcx> TraitObligation<'tcx> {
 133     pub fn self_ty(&self) -> ty::Binder<Ty<'tcx>> {
 134         self.predicate.map_bound(|p| p.self_ty())
 135     }
 136 }