compiler/rustc_middle/src/traits/select.rs

   1 //! Candidate selection. 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#selection
   4
   5 use self::EvaluationResult::*;
   6
   7 use super::{SelectionError, SelectionResult};
   8
   9 use crate::ty;
  10
  11 use rustc_hir::def_id::DefId;
  12 use rustc_query_system::cache::Cache;
  13
  14 pub type SelectionCache<'tcx> = Cache<
  15     ty::ParamEnvAnd<'tcx, ty::TraitPredicate<'tcx>>,
  16     SelectionResult<'tcx, SelectionCandidate<'tcx>>,
  17 >;
  18
  19 pub type EvaluationCache<'tcx> =
  20     Cache<ty::ParamEnvAnd<'tcx, ty::PolyTraitPredicate<'tcx>>, EvaluationResult>;
  21
  22 /// The selection process begins by considering all impls, where
  23 /// clauses, and so forth that might resolve an obligation. Sometimes
  24 /// we'll be able to say definitively that (e.g.) an impl does not
  25 /// apply to the obligation: perhaps it is defined for `usize` but the
  26 /// obligation is for `i32`. In that case, we drop the impl out of the
  27 /// list. But the other cases are considered *candidates*.
  28 ///
  29 /// For selection to succeed, there must be exactly one matching
  30 /// candidate. If the obligation is fully known, this is guaranteed
  31 /// by coherence. However, if the obligation contains type parameters
  32 /// or variables, there may be multiple such impls.
  33 ///
  34 /// It is not a real problem if multiple matching impls exist because
  35 /// of type variables - it just means the obligation isn't sufficiently
  36 /// elaborated. In that case we report an ambiguity, and the caller can
  37 /// try again after more type information has been gathered or report a
  38 /// "type annotations needed" error.
  39 ///
  40 /// However, with type parameters, this can be a real problem - type
  41 /// parameters don't unify with regular types, but they *can* unify
  42 /// with variables from blanket impls, and (unless we know its bounds
  43 /// will always be satisfied) picking the blanket impl will be wrong
  44 /// for at least *some* substitutions. To make this concrete, if we have
  45 ///
  46 /// ```rust, ignore
  47 /// trait AsDebug { type Out: fmt::Debug; fn debug(self) -> Self::Out; }
  48 /// impl<T: fmt::Debug> AsDebug for T {
  49 ///     type Out = T;
  50 ///     fn debug(self) -> fmt::Debug { self }
  51 /// }
  52 /// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); }
  53 /// ```
  54 ///
  55 /// we can't just use the impl to resolve the `<T as AsDebug>` obligation
  56 /// -- a type from another crate (that doesn't implement `fmt::Debug`) could
  57 /// implement `AsDebug`.
  58 ///
  59 /// Because where-clauses match the type exactly, multiple clauses can
  60 /// only match if there are unresolved variables, and we can mostly just
  61 /// report this ambiguity in that case. This is still a problem - we can't
  62 /// *do anything* with ambiguities that involve only regions. This is issue
  63 /// #21974.
  64 ///
  65 /// If a single where-clause matches and there are no inference
  66 /// variables left, then it definitely matches and we can just select
  67 /// it.
  68 ///
  69 /// In fact, we even select the where-clause when the obligation contains
  70 /// inference variables. The can lead to inference making "leaps of logic",
  71 /// for example in this situation:
  72 ///
  73 /// ```rust, ignore
  74 /// pub trait Foo<T> { fn foo(&self) -> T; }
  75 /// impl<T> Foo<()> for T { fn foo(&self) { } }
  76 /// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } }
  77 ///
  78 /// pub fn foo<T>(t: T) where T: Foo<bool> {
  79 ///     println!("{:?}", <T as Foo<_>>::foo(&t));
  80 /// }
  81 /// fn main() { foo(false); }
  82 /// ```
  83 ///
  84 /// Here the obligation `<T as Foo<$0>>` can be matched by both the blanket
  85 /// impl and the where-clause. We select the where-clause and unify `$0=bool`,
  86 /// so the program prints "false". However, if the where-clause is omitted,
  87 /// the blanket impl is selected, we unify `$0=()`, and the program prints
  88 /// "()".
  89 ///
  90 /// Exactly the same issues apply to projection and object candidates, except
  91 /// that we can have both a projection candidate and a where-clause candidate
  92 /// for the same obligation. In that case either would do (except that
  93 /// different "leaps of logic" would occur if inference variables are
  94 /// present), and we just pick the where-clause. This is, for example,
  95 /// required for associated types to work in default impls, as the bounds
  96 /// are visible both as projection bounds and as where-clauses from the
  97 /// parameter environment.
  98 #[derive(PartialEq, Eq, Debug, Clone, TypeFoldable)]
  99 pub enum SelectionCandidate<'tcx> {
 100     BuiltinCandidate {
 101         /// `false` if there are no *further* obligations.
 102         has_nested: bool,
 103     },
 104     ParamCandidate(ty::PolyTraitPredicate<'tcx>),
 105     ImplCandidate(DefId),
 106     AutoImplCandidate(DefId),
 107
 108     /// This is a trait matching with a projected type as `Self`, and we found
 109     /// an applicable bound in the trait definition. The `usize` is an index
 110     /// into the list returned by `tcx.item_bounds`.
 111     ProjectionCandidate(usize),
 112
 113     /// Implementation of a `Fn`-family trait by one of the anonymous types
 114     /// generated for an `||` expression.
 115     ClosureCandidate,
 116
 117     /// Implementation of a `Generator` trait by one of the anonymous types
 118     /// generated for a generator.
 119     GeneratorCandidate,
 120
 121     /// Implementation of a `Fn`-family trait by one of the anonymous
 122     /// types generated for a fn pointer type (e.g., `fn(int) -> int`)
 123     FnPointerCandidate {
 124         is_const: bool,
 125     },
 126
 127     /// Builtin implementation of `DiscriminantKind`.
 128     DiscriminantKindCandidate,
 129
 130     /// Builtin implementation of `Pointee`.
 131     PointeeCandidate,
 132
 133     TraitAliasCandidate(DefId),
 134
 135     /// Matching `dyn Trait` with a supertrait of `Trait`. The index is the
 136     /// position in the iterator returned by
 137     /// `rustc_infer::traits::util::supertraits`.
 138     ObjectCandidate(usize),
 139
 140     /// Perform trait upcasting coercion of `dyn Trait` to a supertrait of `Trait`.
 141     /// The index is the position in the iterator returned by
 142     /// `rustc_infer::traits::util::supertraits`.
 143     TraitUpcastingUnsizeCandidate(usize),
 144
 145     BuiltinObjectCandidate,
 146
 147     BuiltinUnsizeCandidate,
 148
 149     /// Implementation of `const Drop`.
 150     ConstDropCandidate,
 151 }
 152
 153 /// The result of trait evaluation. The order is important
 154 /// here as the evaluation of a list is the maximum of the
 155 /// evaluations.
 156 ///
 157 /// The evaluation results are ordered:
 158 ///     - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
 159 ///       implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
 160 ///     - `EvaluatedToErr` implies `EvaluatedToRecur`
 161 ///     - the "union" of evaluation results is equal to their maximum -
 162 ///     all the "potential success" candidates can potentially succeed,
 163 ///     so they are noops when unioned with a definite error, and within
 164 ///     the categories it's easy to see that the unions are correct.
 165 #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)]
 166 pub enum EvaluationResult {
 167     /// Evaluation successful.
 168     EvaluatedToOk,
 169     /// Evaluation successful, but there were unevaluated region obligations.
 170     EvaluatedToOkModuloRegions,
 171     /// Evaluation is known to be ambiguous -- it *might* hold for some
 172     /// assignment of inference variables, but it might not.
 173     ///
 174     /// While this has the same meaning as `EvaluatedToUnknown` -- we can't
 175     /// know whether this obligation holds or not -- it is the result we
 176     /// would get with an empty stack, and therefore is cacheable.
 177     EvaluatedToAmbig,
 178     /// Evaluation failed because of recursion involving inference
 179     /// variables. We are somewhat imprecise there, so we don't actually
 180     /// know the real result.
 181     ///
 182     /// This can't be trivially cached for the same reason as `EvaluatedToRecur`.
 183     EvaluatedToUnknown,
 184     /// Evaluation failed because we encountered an obligation we are already
 185     /// trying to prove on this branch.
 186     ///
 187     /// We know this branch can't be a part of a minimal proof-tree for
 188     /// the "root" of our cycle, because then we could cut out the recursion
 189     /// and maintain a valid proof tree. However, this does not mean
 190     /// that all the obligations on this branch do not hold -- it's possible
 191     /// that we entered this branch "speculatively", and that there
 192     /// might be some other way to prove this obligation that does not
 193     /// go through this cycle -- so we can't cache this as a failure.
 194     ///
 195     /// For example, suppose we have this:
 196     ///
 197     /// ```rust,ignore (pseudo-Rust)
 198     /// pub trait Trait { fn xyz(); }
 199     /// // This impl is "useless", but we can still have
 200     /// // an `impl Trait for SomeUnsizedType` somewhere.
 201     /// impl<T: Trait + Sized> Trait for T { fn xyz() {} }
 202     ///
 203     /// pub fn foo<T: Trait + ?Sized>() {
 204     ///     <T as Trait>::xyz();
 205     /// }
 206     /// ```
 207     ///
 208     /// When checking `foo`, we have to prove `T: Trait`. This basically
 209     /// translates into this:
 210     ///
 211     /// ```plain,ignore
 212     /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait
 213     /// ```
 214     ///
 215     /// When we try to prove it, we first go the first option, which
 216     /// recurses. This shows us that the impl is "useless" -- it won't
 217     /// tell us that `T: Trait` unless it already implemented `Trait`
 218     /// by some other means. However, that does not prevent `T: Trait`
 219     /// does not hold, because of the bound (which can indeed be satisfied
 220     /// by `SomeUnsizedType` from another crate).
 221     //
 222     // FIXME: when an `EvaluatedToRecur` goes past its parent root, we
 223     // ought to convert it to an `EvaluatedToErr`, because we know
 224     // there definitely isn't a proof tree for that obligation. Not
 225     // doing so is still sound -- there isn't any proof tree, so the
 226     // branch still can't be a part of a minimal one -- but does not re-enable caching.
 227     EvaluatedToRecur,
 228     /// Evaluation failed.
 229     EvaluatedToErr,
 230 }
 231
 232 impl EvaluationResult {
 233     /// Returns `true` if this evaluation result is known to apply, even
 234     /// considering outlives constraints.
 235     pub fn must_apply_considering_regions(self) -> bool {
 236         self == EvaluatedToOk
 237     }
 238
 239     /// Returns `true` if this evaluation result is known to apply, ignoring
 240     /// outlives constraints.
 241     pub fn must_apply_modulo_regions(self) -> bool {
 242         self <= EvaluatedToOkModuloRegions
 243     }
 244
 245     pub fn may_apply(self) -> bool {
 246         match self {
 247             EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToUnknown => {
 248                 true
 249             }
 250
 251             EvaluatedToErr | EvaluatedToRecur => false,
 252         }
 253     }
 254
 255     pub fn is_stack_dependent(self) -> bool {
 256         match self {
 257             EvaluatedToUnknown | EvaluatedToRecur => true,
 258
 259             EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToErr => false,
 260         }
 261     }
 262 }
 263
 264 /// Indicates that trait evaluation caused overflow and in which pass.
 265 #[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)]
 266 pub enum OverflowError {
 267     Canonical,
 268     ErrorReporting,
 269 }
 270
 271 impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
 272     fn from(overflow_error: OverflowError) -> SelectionError<'tcx> {
 273         match overflow_error {
 274             OverflowError::Canonical => SelectionError::Overflow,
 275             OverflowError::ErrorReporting => SelectionError::ErrorReporting,
 276         }
 277     }
 278 }