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