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