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 316 317 318
//! 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, TypeVisitable)]
pub enum SelectionCandidate<'tcx> {
/// A builtin implementation for some specific traits, used in cases
/// where we cannot rely an ordinary library implementations.
///
/// The most notable examples are `sized`, `Copy` and `Clone`. This is also
/// used for the `DiscriminantKind` and `Pointee` trait, both of which have
/// an associated type.
BuiltinCandidate {
/// `false` if there are no *further* obligations.
has_nested: bool,
},
/// Implementation of transmutability trait.
TransmutabilityCandidate,
ParamCandidate(ty::PolyTraitPredicate<'tcx>),
ImplCandidate(DefId),
AutoImplCandidate,
/// 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`. The constness is the
/// constness of the bound in the trait.
// FIXME(effects) do we need this constness
ProjectionCandidate(usize, ty::BoundConstness),
/// Implementation of a `Fn`-family trait by one of the anonymous types
/// generated for an `||` expression.
ClosureCandidate {
is_const: bool,
},
/// Implementation of a `Generator` trait by one of the anonymous types
/// generated for a generator.
GeneratorCandidate,
/// Implementation of a `Future` trait by one of the generator types
/// generated for an async construct.
FutureCandidate,
/// 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,
},
TraitAliasCandidate,
/// 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>),
}
/// 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)
}
}
TrivialTypeTraversalImpls! { 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,
}
}
}