src/librustc/traits/select.rs

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