1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
//! Candidate selection. See the [rustc dev guide] for more information on how this works.
//!
//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection

use self::EvaluationResult::*;

use super::{SelectionError, SelectionResult};
use rustc_errors::ErrorGuaranteed;

use crate::ty;

use rustc_hir::def_id::DefId;
use rustc_query_system::cache::Cache;

pub type SelectionCache<'tcx> = Cache<
    // This cache does not use `ParamEnvAnd` in its keys because `ParamEnv::and` can replace
    // caller bounds with an empty list if the `TraitPredicate` looks global, which may happen
    // after erasing lifetimes from the predicate.
    (ty::ParamEnv<'tcx>, ty::TraitPredicate<'tcx>),
    SelectionResult<'tcx, SelectionCandidate<'tcx>>,
>;

pub type EvaluationCache<'tcx> = Cache<
    // See above: this cache does not use `ParamEnvAnd` in its keys due to sometimes incorrectly
    // caching with the wrong `ParamEnv`.
    (ty::ParamEnv<'tcx>, ty::PolyTraitPredicate<'tcx>),
    EvaluationResult,
>;

/// The selection process begins by considering all impls, where
/// clauses, and so forth that might resolve an obligation. Sometimes
/// we'll be able to say definitively that (e.g.) an impl does not
/// apply to the obligation: perhaps it is defined for `usize` but the
/// obligation is for `i32`. In that case, we drop the impl out of the
/// list. But the other cases are considered *candidates*.
///
/// For selection to succeed, there must be exactly one matching
/// candidate. If the obligation is fully known, this is guaranteed
/// by coherence. However, if the obligation contains type parameters
/// or variables, there may be multiple such impls.
///
/// It is not a real problem if multiple matching impls exist because
/// of type variables - it just means the obligation isn't sufficiently
/// elaborated. In that case we report an ambiguity, and the caller can
/// try again after more type information has been gathered or report a
/// "type annotations needed" error.
///
/// However, with type parameters, this can be a real problem - type
/// parameters don't unify with regular types, but they *can* unify
/// with variables from blanket impls, and (unless we know its bounds
/// will always be satisfied) picking the blanket impl will be wrong
/// for at least *some* substitutions. To make this concrete, if we have
///
/// ```rust, ignore
/// trait AsDebug { type Out: fmt::Debug; fn debug(self) -> Self::Out; }
/// impl<T: fmt::Debug> AsDebug for T {
///     type Out = T;
///     fn debug(self) -> fmt::Debug { self }
/// }
/// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); }
/// ```
///
/// we can't just use the impl to resolve the `<T as AsDebug>` obligation
/// -- a type from another crate (that doesn't implement `fmt::Debug`) could
/// implement `AsDebug`.
///
/// Because where-clauses match the type exactly, multiple clauses can
/// only match if there are unresolved variables, and we can mostly just
/// report this ambiguity in that case. This is still a problem - we can't
/// *do anything* with ambiguities that involve only regions. This is issue
/// #21974.
///
/// If a single where-clause matches and there are no inference
/// variables left, then it definitely matches and we can just select
/// it.
///
/// In fact, we even select the where-clause when the obligation contains
/// inference variables. The can lead to inference making "leaps of logic",
/// for example in this situation:
///
/// ```rust, ignore
/// pub trait Foo<T> { fn foo(&self) -> T; }
/// impl<T> Foo<()> for T { fn foo(&self) { } }
/// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } }
///
/// pub fn foo<T>(t: T) where T: Foo<bool> {
///     println!("{:?}", <T as Foo<_>>::foo(&t));
/// }
/// fn main() { foo(false); }
/// ```
///
/// Here the obligation `<T as Foo<$0>>` can be matched by both the blanket
/// impl and the where-clause. We select the where-clause and unify `$0=bool`,
/// so the program prints "false". However, if the where-clause is omitted,
/// the blanket impl is selected, we unify `$0=()`, and the program prints
/// "()".
///
/// Exactly the same issues apply to projection and object candidates, except
/// that we can have both a projection candidate and a where-clause candidate
/// for the same obligation. In that case either would do (except that
/// different "leaps of logic" would occur if inference variables are
/// present), and we just pick the where-clause. This is, for example,
/// required for associated types to work in default impls, as the bounds
/// are visible both as projection bounds and as where-clauses from the
/// parameter environment.
#[derive(PartialEq, Eq, Debug, Clone, TypeFoldable, TypeVisitable)]
pub enum SelectionCandidate<'tcx> {
    BuiltinCandidate {
        /// `false` if there are no *further* obligations.
        has_nested: bool,
    },

    /// Implementation of transmutability trait.
    TransmutabilityCandidate,

    ParamCandidate(ty::PolyTraitPredicate<'tcx>),
    ImplCandidate(DefId),
    AutoImplCandidate(DefId),

    /// This is a trait matching with a projected type as `Self`, and we found
    /// an applicable bound in the trait definition. The `usize` is an index
    /// into the list returned by `tcx.item_bounds`.
    ProjectionCandidate(usize),

    /// Implementation of a `Fn`-family trait by one of the anonymous types
    /// generated for an `||` expression.
    ClosureCandidate,

    /// Implementation of a `Generator` trait by one of the anonymous types
    /// generated for a generator.
    GeneratorCandidate,

    /// Implementation of a `Fn`-family trait by one of the anonymous
    /// types generated for a fn pointer type (e.g., `fn(int) -> int`)
    FnPointerCandidate {
        is_const: bool,
    },

    /// Builtin implementation of `DiscriminantKind`.
    DiscriminantKindCandidate,

    /// Builtin implementation of `Pointee`.
    PointeeCandidate,

    TraitAliasCandidate(DefId),

    /// Matching `dyn Trait` with a supertrait of `Trait`. The index is the
    /// position in the iterator returned by
    /// `rustc_infer::traits::util::supertraits`.
    ObjectCandidate(usize),

    /// Perform trait upcasting coercion of `dyn Trait` to a supertrait of `Trait`.
    /// The index is the position in the iterator returned by
    /// `rustc_infer::traits::util::supertraits`.
    TraitUpcastingUnsizeCandidate(usize),

    BuiltinObjectCandidate,

    BuiltinUnsizeCandidate,

    /// Implementation of `const Destruct`, optionally from a custom `impl const Drop`.
    ConstDestructCandidate(Option<DefId>),

    /// Witnesses the fact that a type is a tuple.
    TupleCandidate,
}

/// The result of trait evaluation. The order is important
/// here as the evaluation of a list is the maximum of the
/// evaluations.
///
/// The evaluation results are ordered:
///     - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
///       implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
///     - `EvaluatedToErr` implies `EvaluatedToRecur`
///     - the "union" of evaluation results is equal to their maximum -
///     all the "potential success" candidates can potentially succeed,
///     so they are noops when unioned with a definite error, and within
///     the categories it's easy to see that the unions are correct.
#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)]
pub enum EvaluationResult {
    /// Evaluation successful.
    EvaluatedToOk,
    /// Evaluation successful, but there were unevaluated region obligations.
    EvaluatedToOkModuloRegions,
    /// Evaluation successful, but need to rerun because opaque types got
    /// hidden types assigned without it being known whether the opaque types
    /// are within their defining scope
    EvaluatedToOkModuloOpaqueTypes,
    /// Evaluation is known to be ambiguous -- it *might* hold for some
    /// assignment of inference variables, but it might not.
    ///
    /// While this has the same meaning as `EvaluatedToUnknown` -- we can't
    /// know whether this obligation holds or not -- it is the result we
    /// would get with an empty stack, and therefore is cacheable.
    EvaluatedToAmbig,
    /// Evaluation failed because of recursion involving inference
    /// variables. We are somewhat imprecise there, so we don't actually
    /// know the real result.
    ///
    /// This can't be trivially cached for the same reason as `EvaluatedToRecur`.
    EvaluatedToUnknown,
    /// Evaluation failed because we encountered an obligation we are already
    /// trying to prove on this branch.
    ///
    /// We know this branch can't be a part of a minimal proof-tree for
    /// the "root" of our cycle, because then we could cut out the recursion
    /// and maintain a valid proof tree. However, this does not mean
    /// that all the obligations on this branch do not hold -- it's possible
    /// that we entered this branch "speculatively", and that there
    /// might be some other way to prove this obligation that does not
    /// go through this cycle -- so we can't cache this as a failure.
    ///
    /// For example, suppose we have this:
    ///
    /// ```rust,ignore (pseudo-Rust)
    /// pub trait Trait { fn xyz(); }
    /// // This impl is "useless", but we can still have
    /// // an `impl Trait for SomeUnsizedType` somewhere.
    /// impl<T: Trait + Sized> Trait for T { fn xyz() {} }
    ///
    /// pub fn foo<T: Trait + ?Sized>() {
    ///     <T as Trait>::xyz();
    /// }
    /// ```
    ///
    /// When checking `foo`, we have to prove `T: Trait`. This basically
    /// translates into this:
    ///
    /// ```plain,ignore
    /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait
    /// ```
    ///
    /// When we try to prove it, we first go the first option, which
    /// recurses. This shows us that the impl is "useless" -- it won't
    /// tell us that `T: Trait` unless it already implemented `Trait`
    /// by some other means. However, that does not prevent `T: Trait`
    /// does not hold, because of the bound (which can indeed be satisfied
    /// by `SomeUnsizedType` from another crate).
    //
    // FIXME: when an `EvaluatedToRecur` goes past its parent root, we
    // ought to convert it to an `EvaluatedToErr`, because we know
    // there definitely isn't a proof tree for that obligation. Not
    // doing so is still sound -- there isn't any proof tree, so the
    // branch still can't be a part of a minimal one -- but does not re-enable caching.
    EvaluatedToRecur,
    /// Evaluation failed.
    EvaluatedToErr,
}

impl EvaluationResult {
    /// Returns `true` if this evaluation result is known to apply, even
    /// considering outlives constraints.
    pub fn must_apply_considering_regions(self) -> bool {
        self == EvaluatedToOk
    }

    /// Returns `true` if this evaluation result is known to apply, ignoring
    /// outlives constraints.
    pub fn must_apply_modulo_regions(self) -> bool {
        self <= EvaluatedToOkModuloRegions
    }

    pub fn may_apply(self) -> bool {
        match self {
            EvaluatedToOkModuloOpaqueTypes
            | EvaluatedToOk
            | EvaluatedToOkModuloRegions
            | EvaluatedToAmbig
            | EvaluatedToUnknown => true,

            EvaluatedToErr | EvaluatedToRecur => false,
        }
    }

    pub fn is_stack_dependent(self) -> bool {
        match self {
            EvaluatedToUnknown | EvaluatedToRecur => true,

            EvaluatedToOkModuloOpaqueTypes
            | EvaluatedToOk
            | EvaluatedToOkModuloRegions
            | EvaluatedToAmbig
            | EvaluatedToErr => false,
        }
    }
}

/// Indicates that trait evaluation caused overflow and in which pass.
#[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)]
pub enum OverflowError {
    Error(ErrorGuaranteed),
    Canonical,
    ErrorReporting,
}

impl From<ErrorGuaranteed> for OverflowError {
    fn from(e: ErrorGuaranteed) -> OverflowError {
        OverflowError::Error(e)
    }
}

TrivialTypeTraversalAndLiftImpls! {
    OverflowError,
}

impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
    fn from(overflow_error: OverflowError) -> SelectionError<'tcx> {
        match overflow_error {
            OverflowError::Error(e) => SelectionError::Overflow(OverflowError::Error(e)),
            OverflowError::Canonical => SelectionError::Overflow(OverflowError::Canonical),
            OverflowError::ErrorReporting => SelectionError::ErrorReporting,
        }
    }
}