Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
59 contributors

Users who have contributed to this file

@nikomatsakis @eddyb @bors @Aaron1011 @scalexm @Mark-Simulacrum @Zoxc @varkor @alexreg @alexcrichton @canndrew @aravind-pg @kennytm @soltanmm-google @qnighy @nnethercote @petrochenkov @tmandry @mark-i-m @ljedrz @oli-obk @Centril @sgrif @Manishearth @leodasvacas @zackmdavis
4335 lines (3919 sloc) 167 KB
// ignore-tidy-filelength
//! Candidate selection. See the [rustc guide] for more information on how this works.
//!
//! [rustc guide]: https://rust-lang.github.io/rustc-guide/traits/resolution.html#selection
use self::EvaluationResult::*;
use self::SelectionCandidate::*;
use super::coherence::{self, Conflict};
use super::project;
use super::project::{normalize_with_depth, Normalized, ProjectionCacheKey};
use super::util;
use super::DerivedObligationCause;
use super::Selection;
use super::SelectionResult;
use super::TraitNotObjectSafe;
use super::{BuiltinDerivedObligation, ImplDerivedObligation, ObligationCauseCode};
use super::{IntercrateMode, TraitQueryMode};
use super::{ObjectCastObligation, Obligation};
use super::{ObligationCause, PredicateObligation, TraitObligation};
use super::{OutputTypeParameterMismatch, Overflow, SelectionError, Unimplemented};
use super::{
VtableAutoImpl, VtableBuiltin, VtableClosure, VtableFnPointer, VtableGenerator, VtableImpl,
VtableObject, VtableParam, VtableTraitAlias,
};
use super::{
VtableAutoImplData, VtableBuiltinData, VtableClosureData, VtableFnPointerData,
VtableGeneratorData, VtableImplData, VtableObjectData, VtableTraitAliasData,
};
use crate::dep_graph::{DepKind, DepNodeIndex};
use crate::hir::def_id::DefId;
use crate::infer::{CombinedSnapshot, InferCtxt, InferOk, PlaceholderMap, TypeFreshener};
use crate::middle::lang_items;
use crate::mir::interpret::GlobalId;
use crate::ty::fast_reject;
use crate::ty::relate::TypeRelation;
use crate::ty::subst::{Subst, SubstsRef};
use crate::ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, TypeFoldable};
use crate::hir;
use rustc_data_structures::bit_set::GrowableBitSet;
use rustc_data_structures::sync::Lock;
use rustc_target::spec::abi::Abi;
use std::cell::{Cell, RefCell};
use std::cmp;
use std::fmt::{self, Display};
use std::iter;
use std::rc::Rc;
use crate::util::nodemap::{FxHashMap, FxHashSet};
pub struct SelectionContext<'cx, 'tcx> {
infcx: &'cx InferCtxt<'cx, 'tcx>,
/// Freshener used specifically for entries on the obligation
/// stack. This ensures that all entries on the stack at one time
/// will have the same set of placeholder entries, which is
/// important for checking for trait bounds that recursively
/// require themselves.
freshener: TypeFreshener<'cx, 'tcx>,
/// If `true`, indicates that the evaluation should be conservative
/// and consider the possibility of types outside this crate.
/// This comes up primarily when resolving ambiguity. Imagine
/// there is some trait reference `$0: Bar` where `$0` is an
/// inference variable. If `intercrate` is true, then we can never
/// say for sure that this reference is not implemented, even if
/// there are *no impls at all for `Bar`*, because `$0` could be
/// bound to some type that in a downstream crate that implements
/// `Bar`. This is the suitable mode for coherence. Elsewhere,
/// though, we set this to false, because we are only interested
/// in types that the user could actually have written --- in
/// other words, we consider `$0: Bar` to be unimplemented if
/// there is no type that the user could *actually name* that
/// would satisfy it. This avoids crippling inference, basically.
intercrate: Option<IntercrateMode>,
intercrate_ambiguity_causes: Option<Vec<IntercrateAmbiguityCause>>,
/// Controls whether or not to filter out negative impls when selecting.
/// This is used in librustdoc to distinguish between the lack of an impl
/// and a negative impl
allow_negative_impls: bool,
/// The mode that trait queries run in, which informs our error handling
/// policy. In essence, canonicalized queries need their errors propagated
/// rather than immediately reported because we do not have accurate spans.
query_mode: TraitQueryMode,
}
#[derive(Clone, Debug)]
pub enum IntercrateAmbiguityCause {
DownstreamCrate {
trait_desc: String,
self_desc: Option<String>,
},
UpstreamCrateUpdate {
trait_desc: String,
self_desc: Option<String>,
},
}
impl IntercrateAmbiguityCause {
/// Emits notes when the overlap is caused by complex intercrate ambiguities.
/// See #23980 for details.
pub fn add_intercrate_ambiguity_hint(&self, err: &mut errors::DiagnosticBuilder<'_>) {
err.note(&self.intercrate_ambiguity_hint());
}
pub fn intercrate_ambiguity_hint(&self) -> String {
match self {
&IntercrateAmbiguityCause::DownstreamCrate {
ref trait_desc,
ref self_desc,
} => {
let self_desc = if let &Some(ref ty) = self_desc {
format!(" for type `{}`", ty)
} else {
String::new()
};
format!(
"downstream crates may implement trait `{}`{}",
trait_desc, self_desc
)
}
&IntercrateAmbiguityCause::UpstreamCrateUpdate {
ref trait_desc,
ref self_desc,
} => {
let self_desc = if let &Some(ref ty) = self_desc {
format!(" for type `{}`", ty)
} else {
String::new()
};
format!(
"upstream crates may add new impl of trait `{}`{} \
in future versions",
trait_desc, self_desc
)
}
}
}
}
// A stack that walks back up the stack frame.
struct TraitObligationStack<'prev, 'tcx> {
obligation: &'prev TraitObligation<'tcx>,
/// Trait ref from `obligation` but "freshened" with the
/// selection-context's freshener. Used to check for recursion.
fresh_trait_ref: ty::PolyTraitRef<'tcx>,
/// Starts out equal to `depth` -- if, during evaluation, we
/// encounter a cycle, then we will set this flag to the minimum
/// depth of that cycle for all participants in the cycle. These
/// participants will then forego caching their results. This is
/// not the most efficient solution, but it addresses #60010. The
/// problem we are trying to prevent:
///
/// - If you have `A: AutoTrait` requires `B: AutoTrait` and `C: NonAutoTrait`
/// - `B: AutoTrait` requires `A: AutoTrait` (coinductive cycle, ok)
/// - `C: NonAutoTrait` requires `A: AutoTrait` (non-coinductive cycle, not ok)
///
/// you don't want to cache that `B: AutoTrait` or `A: AutoTrait`
/// is `EvaluatedToOk`; this is because they were only considered
/// ok on the premise that if `A: AutoTrait` held, but we indeed
/// encountered a problem (later on) with `A: AutoTrait. So we
/// currently set a flag on the stack node for `B: AutoTrait` (as
/// well as the second instance of `A: AutoTrait`) to supress
/// caching.
///
/// This is a simple, targeted fix. A more-performant fix requires
/// deeper changes, but would permit more caching: we could
/// basically defer caching until we have fully evaluated the
/// tree, and then cache the entire tree at once. In any case, the
/// performance impact here shouldn't be so horrible: every time
/// this is hit, we do cache at least one trait, so we only
/// evaluate each member of a cycle up to N times, where N is the
/// length of the cycle. This means the performance impact is
/// bounded and we shouldn't have any terrible worst-cases.
reached_depth: Cell<usize>,
previous: TraitObligationStackList<'prev, 'tcx>,
/// Number of parent frames plus one -- so the topmost frame has depth 1.
depth: usize,
/// Depth-first number of this node in the search graph -- a
/// pre-order index. Basically a freshly incremented counter.
dfn: usize,
}
#[derive(Clone, Default)]
pub struct SelectionCache<'tcx> {
hashmap: Lock<
FxHashMap<ty::TraitRef<'tcx>, WithDepNode<SelectionResult<'tcx, SelectionCandidate<'tcx>>>>,
>,
}
/// 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 `int`. 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 required" 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
///
/// 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:
///
/// 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)]
enum SelectionCandidate<'tcx> {
/// If has_nested is false, there are no *further* obligations
BuiltinCandidate {
has_nested: bool,
},
ParamCandidate(ty::PolyTraitRef<'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.
ProjectionCandidate,
/// Implementation of a `Fn`-family trait by one of the anonymous types
/// generated for a `||` 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,
TraitAliasCandidate(DefId),
ObjectCandidate,
BuiltinObjectCandidate,
BuiltinUnsizeCandidate,
}
impl<'a, 'tcx> ty::Lift<'tcx> for SelectionCandidate<'a> {
type Lifted = SelectionCandidate<'tcx>;
fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
Some(match *self {
BuiltinCandidate { has_nested } => BuiltinCandidate { has_nested },
ImplCandidate(def_id) => ImplCandidate(def_id),
AutoImplCandidate(def_id) => AutoImplCandidate(def_id),
ProjectionCandidate => ProjectionCandidate,
ClosureCandidate => ClosureCandidate,
GeneratorCandidate => GeneratorCandidate,
FnPointerCandidate => FnPointerCandidate,
TraitAliasCandidate(def_id) => TraitAliasCandidate(def_id),
ObjectCandidate => ObjectCandidate,
BuiltinObjectCandidate => BuiltinObjectCandidate,
BuiltinUnsizeCandidate => BuiltinUnsizeCandidate,
ParamCandidate(ref trait_ref) => {
return tcx.lift(trait_ref).map(ParamCandidate);
}
})
}
}
EnumTypeFoldableImpl! {
impl<'tcx> TypeFoldable<'tcx> for SelectionCandidate<'tcx> {
(SelectionCandidate::BuiltinCandidate) { has_nested },
(SelectionCandidate::ParamCandidate)(poly_trait_ref),
(SelectionCandidate::ImplCandidate)(def_id),
(SelectionCandidate::AutoImplCandidate)(def_id),
(SelectionCandidate::ProjectionCandidate),
(SelectionCandidate::ClosureCandidate),
(SelectionCandidate::GeneratorCandidate),
(SelectionCandidate::FnPointerCandidate),
(SelectionCandidate::TraitAliasCandidate)(def_id),
(SelectionCandidate::ObjectCandidate),
(SelectionCandidate::BuiltinObjectCandidate),
(SelectionCandidate::BuiltinUnsizeCandidate),
}
}
struct SelectionCandidateSet<'tcx> {
// a list of candidates that definitely apply to the current
// obligation (meaning: types unify).
vec: Vec<SelectionCandidate<'tcx>>,
// if this is true, then there were candidates that might or might
// not have applied, but we couldn't tell. This occurs when some
// of the input types are type variables, in which case there are
// various "builtin" rules that might or might not trigger.
ambiguous: bool,
}
#[derive(PartialEq, Eq, Debug, Clone)]
struct EvaluatedCandidate<'tcx> {
candidate: SelectionCandidate<'tcx>,
evaluation: EvaluationResult,
}
/// When does the builtin impl for `T: Trait` apply?
enum BuiltinImplConditions<'tcx> {
/// The impl is conditional on T1,T2,.. : Trait
Where(ty::Binder<Vec<Ty<'tcx>>>),
/// There is no built-in impl. There may be some other
/// candidate (a where-clause or user-defined impl).
None,
/// It is unknown whether there is an impl.
Ambiguous,
}
#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
/// 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.
pub enum EvaluationResult {
/// Evaluation successful
EvaluatedToOk,
/// Evaluation successful, but there were unevaluated region obligations
EvaluatedToOkModuloRegions,
/// 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 {
EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToUnknown => {
true
}
EvaluatedToErr | EvaluatedToRecur => false,
}
}
fn is_stack_dependent(self) -> bool {
match self {
EvaluatedToUnknown | EvaluatedToRecur => true,
EvaluatedToOk | EvaluatedToOkModuloRegions | EvaluatedToAmbig | EvaluatedToErr => false,
}
}
}
impl_stable_hash_for!(enum self::EvaluationResult {
EvaluatedToOk,
EvaluatedToOkModuloRegions,
EvaluatedToAmbig,
EvaluatedToUnknown,
EvaluatedToRecur,
EvaluatedToErr
});
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
/// Indicates that trait evaluation caused overflow.
pub struct OverflowError;
impl_stable_hash_for!(struct OverflowError {});
impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
fn from(OverflowError: OverflowError) -> SelectionError<'tcx> {
SelectionError::Overflow
}
}
#[derive(Clone, Default)]
pub struct EvaluationCache<'tcx> {
hashmap: Lock<FxHashMap<ty::PolyTraitRef<'tcx>, WithDepNode<EvaluationResult>>>,
}
impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>) -> SelectionContext<'cx, 'tcx> {
SelectionContext {
infcx,
freshener: infcx.freshener(),
intercrate: None,
intercrate_ambiguity_causes: None,
allow_negative_impls: false,
query_mode: TraitQueryMode::Standard,
}
}
pub fn intercrate(
infcx: &'cx InferCtxt<'cx, 'tcx>,
mode: IntercrateMode,
) -> SelectionContext<'cx, 'tcx> {
debug!("intercrate({:?})", mode);
SelectionContext {
infcx,
freshener: infcx.freshener(),
intercrate: Some(mode),
intercrate_ambiguity_causes: None,
allow_negative_impls: false,
query_mode: TraitQueryMode::Standard,
}
}
pub fn with_negative(
infcx: &'cx InferCtxt<'cx, 'tcx>,
allow_negative_impls: bool,
) -> SelectionContext<'cx, 'tcx> {
debug!("with_negative({:?})", allow_negative_impls);
SelectionContext {
infcx,
freshener: infcx.freshener(),
intercrate: None,
intercrate_ambiguity_causes: None,
allow_negative_impls,
query_mode: TraitQueryMode::Standard,
}
}
pub fn with_query_mode(
infcx: &'cx InferCtxt<'cx, 'tcx>,
query_mode: TraitQueryMode,
) -> SelectionContext<'cx, 'tcx> {
debug!("with_query_mode({:?})", query_mode);
SelectionContext {
infcx,
freshener: infcx.freshener(),
intercrate: None,
intercrate_ambiguity_causes: None,
allow_negative_impls: false,
query_mode,
}
}
/// Enables tracking of intercrate ambiguity causes. These are
/// used in coherence to give improved diagnostics. We don't do
/// this until we detect a coherence error because it can lead to
/// false overflow results (#47139) and because it costs
/// computation time.
pub fn enable_tracking_intercrate_ambiguity_causes(&mut self) {
assert!(self.intercrate.is_some());
assert!(self.intercrate_ambiguity_causes.is_none());
self.intercrate_ambiguity_causes = Some(vec![]);
debug!("selcx: enable_tracking_intercrate_ambiguity_causes");
}
/// Gets the intercrate ambiguity causes collected since tracking
/// was enabled and disables tracking at the same time. If
/// tracking is not enabled, just returns an empty vector.
pub fn take_intercrate_ambiguity_causes(&mut self) -> Vec<IntercrateAmbiguityCause> {
assert!(self.intercrate.is_some());
self.intercrate_ambiguity_causes.take().unwrap_or(vec![])
}
pub fn infcx(&self) -> &'cx InferCtxt<'cx, 'tcx> {
self.infcx
}
pub fn tcx(&self) -> TyCtxt<'tcx> {
self.infcx.tcx
}
pub fn closure_typer(&self) -> &'cx InferCtxt<'cx, 'tcx> {
self.infcx
}
///////////////////////////////////////////////////////////////////////////
// Selection
//
// The selection phase tries to identify *how* an obligation will
// be resolved. For example, it will identify which impl or
// parameter bound is to be used. The process can be inconclusive
// if the self type in the obligation is not fully inferred. Selection
// can result in an error in one of two ways:
//
// 1. If no applicable impl or parameter bound can be found.
// 2. If the output type parameters in the obligation do not match
// those specified by the impl/bound. For example, if the obligation
// is `Vec<Foo>:Iterable<Bar>`, but the impl specifies
// `impl<T> Iterable<T> for Vec<T>`, than an error would result.
/// Attempts to satisfy the obligation. If successful, this will affect the surrounding
/// type environment by performing unification.
pub fn select(
&mut self,
obligation: &TraitObligation<'tcx>,
) -> SelectionResult<'tcx, Selection<'tcx>> {
debug!("select({:?})", obligation);
debug_assert!(!obligation.predicate.has_escaping_bound_vars());
let pec = &ProvisionalEvaluationCache::default();
let stack = self.push_stack(TraitObligationStackList::empty(pec), obligation);
let candidate = match self.candidate_from_obligation(&stack) {
Err(SelectionError::Overflow) => {
// In standard mode, overflow must have been caught and reported
// earlier.
assert!(self.query_mode == TraitQueryMode::Canonical);
return Err(SelectionError::Overflow);
}
Err(e) => {
return Err(e);
}
Ok(None) => {
return Ok(None);
}
Ok(Some(candidate)) => candidate,
};
match self.confirm_candidate(obligation, candidate) {
Err(SelectionError::Overflow) => {
assert!(self.query_mode == TraitQueryMode::Canonical);
Err(SelectionError::Overflow)
}
Err(e) => Err(e),
Ok(candidate) => Ok(Some(candidate)),
}
}
///////////////////////////////////////////////////////////////////////////
// EVALUATION
//
// Tests whether an obligation can be selected or whether an impl
// can be applied to particular types. It skips the "confirmation"
// step and hence completely ignores output type parameters.
//
// The result is "true" if the obligation *may* hold and "false" if
// we can be sure it does not.
/// Evaluates whether the obligation `obligation` can be satisfied (by any means).
pub fn predicate_may_hold_fatal(&mut self, obligation: &PredicateObligation<'tcx>) -> bool {
debug!("predicate_may_hold_fatal({:?})", obligation);
// This fatal query is a stopgap that should only be used in standard mode,
// where we do not expect overflow to be propagated.
assert!(self.query_mode == TraitQueryMode::Standard);
self.evaluate_root_obligation(obligation)
.expect("Overflow should be caught earlier in standard query mode")
.may_apply()
}
/// Evaluates whether the obligation `obligation` can be satisfied
/// and returns an `EvaluationResult`. This is meant for the
/// *initial* call.
pub fn evaluate_root_obligation(
&mut self,
obligation: &PredicateObligation<'tcx>,
) -> Result<EvaluationResult, OverflowError> {
self.evaluation_probe(|this| {
this.evaluate_predicate_recursively(
TraitObligationStackList::empty(&ProvisionalEvaluationCache::default()),
obligation.clone(),
)
})
}
fn evaluation_probe(
&mut self,
op: impl FnOnce(&mut Self) -> Result<EvaluationResult, OverflowError>,
) -> Result<EvaluationResult, OverflowError> {
self.infcx.probe(|snapshot| -> Result<EvaluationResult, OverflowError> {
let result = op(self)?;
match self.infcx.region_constraints_added_in_snapshot(snapshot) {
None => Ok(result),
Some(_) => Ok(result.max(EvaluatedToOkModuloRegions)),
}
})
}
/// Evaluates the predicates in `predicates` recursively. Note that
/// this applies projections in the predicates, and therefore
/// is run within an inference probe.
fn evaluate_predicates_recursively<'o, I>(
&mut self,
stack: TraitObligationStackList<'o, 'tcx>,
predicates: I,
) -> Result<EvaluationResult, OverflowError>
where
I: IntoIterator<Item = PredicateObligation<'tcx>>,
{
let mut result = EvaluatedToOk;
for obligation in predicates {
let eval = self.evaluate_predicate_recursively(stack, obligation.clone())?;
debug!(
"evaluate_predicate_recursively({:?}) = {:?}",
obligation, eval
);
if let EvaluatedToErr = eval {
// fast-path - EvaluatedToErr is the top of the lattice,
// so we don't need to look on the other predicates.
return Ok(EvaluatedToErr);
} else {
result = cmp::max(result, eval);
}
}
Ok(result)
}
fn evaluate_predicate_recursively<'o>(
&mut self,
previous_stack: TraitObligationStackList<'o, 'tcx>,
obligation: PredicateObligation<'tcx>,
) -> Result<EvaluationResult, OverflowError> {
debug!("evaluate_predicate_recursively(previous_stack={:?}, obligation={:?})",
previous_stack.head(), obligation);
// Previous_stack stores a TraitObligatiom, while 'obligation' is
// a PredicateObligation. These are distinct types, so we can't
// use any Option combinator method that would force them to be
// the same
match previous_stack.head() {
Some(h) => self.check_recursion_limit(&obligation, h.obligation)?,
None => self.check_recursion_limit(&obligation, &obligation)?
}
match obligation.predicate {
ty::Predicate::Trait(ref t) => {
debug_assert!(!t.has_escaping_bound_vars());
let obligation = obligation.with(t.clone());
self.evaluate_trait_predicate_recursively(previous_stack, obligation)
}
ty::Predicate::Subtype(ref p) => {
// does this code ever run?
match self.infcx
.subtype_predicate(&obligation.cause, obligation.param_env, p)
{
Some(Ok(InferOk { mut obligations, .. })) => {
self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
self.evaluate_predicates_recursively(previous_stack,obligations.into_iter())
}
Some(Err(_)) => Ok(EvaluatedToErr),
None => Ok(EvaluatedToAmbig),
}
}
ty::Predicate::WellFormed(ty) => match ty::wf::obligations(
self.infcx,
obligation.param_env,
obligation.cause.body_id,
ty,
obligation.cause.span,
) {
Some(mut obligations) => {
self.add_depth(obligations.iter_mut(), obligation.recursion_depth);
self.evaluate_predicates_recursively(previous_stack, obligations.into_iter())
}
None => Ok(EvaluatedToAmbig),
},
ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
// we do not consider region relationships when
// evaluating trait matches
Ok(EvaluatedToOkModuloRegions)
}
ty::Predicate::ObjectSafe(trait_def_id) => {
if self.tcx().is_object_safe(trait_def_id) {
Ok(EvaluatedToOk)
} else {
Ok(EvaluatedToErr)
}
}
ty::Predicate::Projection(ref data) => {
let project_obligation = obligation.with(data.clone());
match project::poly_project_and_unify_type(self, &project_obligation) {
Ok(Some(mut subobligations)) => {
self.add_depth(subobligations.iter_mut(), obligation.recursion_depth);
let result = self.evaluate_predicates_recursively(
previous_stack,
subobligations.into_iter(),
);
if let Some(key) =
ProjectionCacheKey::from_poly_projection_predicate(self, data)
{
self.infcx.projection_cache.borrow_mut().complete(key);
}
result
}
Ok(None) => Ok(EvaluatedToAmbig),
Err(_) => Ok(EvaluatedToErr),
}
}
ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) => {
match self.infcx.closure_kind(closure_def_id, closure_substs) {
Some(closure_kind) => {
if closure_kind.extends(kind) {
Ok(EvaluatedToOk)
} else {
Ok(EvaluatedToErr)
}
}
None => Ok(EvaluatedToAmbig),
}
}
ty::Predicate::ConstEvaluatable(def_id, substs) => {
let tcx = self.tcx();
if !(obligation.param_env, substs).has_local_value() {
let param_env = obligation.param_env;
let instance =
ty::Instance::resolve(tcx, param_env, def_id, substs);
if let Some(instance) = instance {
let cid = GlobalId {
instance,
promoted: None,
};
match self.tcx().const_eval(param_env.and(cid)) {
Ok(_) => Ok(EvaluatedToOk),
Err(_) => Ok(EvaluatedToErr),
}
} else {
Ok(EvaluatedToErr)
}
} else {
// Inference variables still left in param_env or substs.
Ok(EvaluatedToAmbig)
}
}
}
}
fn evaluate_trait_predicate_recursively<'o>(
&mut self,
previous_stack: TraitObligationStackList<'o, 'tcx>,
mut obligation: TraitObligation<'tcx>,
) -> Result<EvaluationResult, OverflowError> {
debug!("evaluate_trait_predicate_recursively({:?})", obligation);
if self.intercrate.is_none() && obligation.is_global()
&& obligation
.param_env
.caller_bounds
.iter()
.all(|bound| bound.needs_subst())
{
// If a param env has no global bounds, global obligations do not
// depend on its particular value in order to work, so we can clear
// out the param env and get better caching.
debug!(
"evaluate_trait_predicate_recursively({:?}) - in global",
obligation
);
obligation.param_env = obligation.param_env.without_caller_bounds();
}
let stack = self.push_stack(previous_stack, &obligation);
let fresh_trait_ref = stack.fresh_trait_ref;
if let Some(result) = self.check_evaluation_cache(obligation.param_env, fresh_trait_ref) {
debug!("CACHE HIT: EVAL({:?})={:?}", fresh_trait_ref, result);
return Ok(result);
}
if let Some(result) = stack.cache().get_provisional(fresh_trait_ref) {
debug!("PROVISIONAL CACHE HIT: EVAL({:?})={:?}", fresh_trait_ref, result);
stack.update_reached_depth(stack.cache().current_reached_depth());
return Ok(result);
}
// Check if this is a match for something already on the
// stack. If so, we don't want to insert the result into the
// main cache (it is cycle dependent) nor the provisional
// cache (which is meant for things that have completed but
// for a "backedge" -- this result *is* the backedge).
if let Some(cycle_result) = self.check_evaluation_cycle(&stack) {
return Ok(cycle_result);
}
let (result, dep_node) = self.in_task(|this| this.evaluate_stack(&stack));
let result = result?;
if !result.must_apply_modulo_regions() {
stack.cache().on_failure(stack.dfn);
}
let reached_depth = stack.reached_depth.get();
if reached_depth >= stack.depth {
debug!("CACHE MISS: EVAL({:?})={:?}", fresh_trait_ref, result);
self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, dep_node, result);
stack.cache().on_completion(stack.depth, |fresh_trait_ref, provisional_result| {
self.insert_evaluation_cache(
obligation.param_env,
fresh_trait_ref,
dep_node,
provisional_result.max(result),
);
});
} else {
debug!("PROVISIONAL: {:?}={:?}", fresh_trait_ref, result);
debug!(
"evaluate_trait_predicate_recursively: caching provisionally because {:?} \
is a cycle participant (at depth {}, reached depth {})",
fresh_trait_ref,
stack.depth,
reached_depth,
);
stack.cache().insert_provisional(
stack.dfn,
reached_depth,
fresh_trait_ref,
result,
);
}
Ok(result)
}
/// If there is any previous entry on the stack that precisely
/// matches this obligation, then we can assume that the
/// obligation is satisfied for now (still all other conditions
/// must be met of course). One obvious case this comes up is
/// marker traits like `Send`. Think of a linked list:
///
/// struct List<T> { data: T, next: Option<Box<List<T>>> }
///
/// `Box<List<T>>` will be `Send` if `T` is `Send` and
/// `Option<Box<List<T>>>` is `Send`, and in turn
/// `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is
/// `Send`.
///
/// Note that we do this comparison using the `fresh_trait_ref`
/// fields. Because these have all been freshened using
/// `self.freshener`, we can be sure that (a) this will not
/// affect the inferencer state and (b) that if we see two
/// fresh regions with the same index, they refer to the same
/// unbound type variable.
fn check_evaluation_cycle(
&mut self,
stack: &TraitObligationStack<'_, 'tcx>,
) -> Option<EvaluationResult> {
if let Some(cycle_depth) = stack.iter()
.skip(1) // skip top-most frame
.find(|prev| stack.obligation.param_env == prev.obligation.param_env &&
stack.fresh_trait_ref == prev.fresh_trait_ref)
.map(|stack| stack.depth)
{
debug!(
"evaluate_stack({:?}) --> recursive at depth {}",
stack.fresh_trait_ref,
cycle_depth,
);
// If we have a stack like `A B C D E A`, where the top of
// the stack is the final `A`, then this will iterate over
// `A, E, D, C, B` -- i.e., all the participants apart
// from the cycle head. We mark them as participating in a
// cycle. This suppresses caching for those nodes. See
// `in_cycle` field for more details.
stack.update_reached_depth(cycle_depth);
// Subtle: when checking for a coinductive cycle, we do
// not compare using the "freshened trait refs" (which
// have erased regions) but rather the fully explicit
// trait refs. This is important because it's only a cycle
// if the regions match exactly.
let cycle = stack.iter().skip(1).take_while(|s| s.depth >= cycle_depth);
let cycle = cycle.map(|stack| ty::Predicate::Trait(stack.obligation.predicate));
if self.coinductive_match(cycle) {
debug!(
"evaluate_stack({:?}) --> recursive, coinductive",
stack.fresh_trait_ref
);
Some(EvaluatedToOk)
} else {
debug!(
"evaluate_stack({:?}) --> recursive, inductive",
stack.fresh_trait_ref
);
Some(EvaluatedToRecur)
}
} else {
None
}
}
fn evaluate_stack<'o>(
&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
) -> Result<EvaluationResult, OverflowError> {
// In intercrate mode, whenever any of the types are unbound,
// there can always be an impl. Even if there are no impls in
// this crate, perhaps the type would be unified with
// something from another crate that does provide an impl.
//
// In intra mode, we must still be conservative. The reason is
// that we want to avoid cycles. Imagine an impl like:
//
// impl<T:Eq> Eq for Vec<T>
//
// and a trait reference like `$0 : Eq` where `$0` is an
// unbound variable. When we evaluate this trait-reference, we
// will unify `$0` with `Vec<$1>` (for some fresh variable
// `$1`), on the condition that `$1 : Eq`. We will then wind
// up with many candidates (since that are other `Eq` impls
// that apply) and try to winnow things down. This results in
// a recursive evaluation that `$1 : Eq` -- as you can
// imagine, this is just where we started. To avoid that, we
// check for unbound variables and return an ambiguous (hence possible)
// match if we've seen this trait before.
//
// This suffices to allow chains like `FnMut` implemented in
// terms of `Fn` etc, but we could probably make this more
// precise still.
let unbound_input_types = stack
.fresh_trait_ref
.skip_binder()
.input_types()
.any(|ty| ty.is_fresh());
// this check was an imperfect workaround for a bug n the old
// intercrate mode, it should be removed when that goes away.
if unbound_input_types && self.intercrate == Some(IntercrateMode::Issue43355) {
debug!(
"evaluate_stack({:?}) --> unbound argument, intercrate --> ambiguous",
stack.fresh_trait_ref
);
// Heuristics: show the diagnostics when there are no candidates in crate.
if self.intercrate_ambiguity_causes.is_some() {
debug!("evaluate_stack: intercrate_ambiguity_causes is some");
if let Ok(candidate_set) = self.assemble_candidates(stack) {
if !candidate_set.ambiguous && candidate_set.vec.is_empty() {
let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
let self_ty = trait_ref.self_ty();
let cause = IntercrateAmbiguityCause::DownstreamCrate {
trait_desc: trait_ref.to_string(),
self_desc: if self_ty.has_concrete_skeleton() {
Some(self_ty.to_string())
} else {
None
},
};
debug!("evaluate_stack: pushing cause = {:?}", cause);
self.intercrate_ambiguity_causes
.as_mut()
.unwrap()
.push(cause);
}
}
}
return Ok(EvaluatedToAmbig);
}
if unbound_input_types && stack.iter().skip(1).any(|prev| {
stack.obligation.param_env == prev.obligation.param_env
&& self.match_fresh_trait_refs(&stack.fresh_trait_ref, &prev.fresh_trait_ref)
}) {
debug!(
"evaluate_stack({:?}) --> unbound argument, recursive --> giving up",
stack.fresh_trait_ref
);
return Ok(EvaluatedToUnknown);
}
match self.candidate_from_obligation(stack) {
Ok(Some(c)) => self.evaluate_candidate(stack, &c),
Ok(None) => Ok(EvaluatedToAmbig),
Err(Overflow) => Err(OverflowError),
Err(..) => Ok(EvaluatedToErr),
}
}
/// For defaulted traits, we use a co-inductive strategy to solve, so
/// that recursion is ok. This routine returns true if the top of the
/// stack (`cycle[0]`):
///
/// - is a defaulted trait,
/// - it also appears in the backtrace at some position `X`,
/// - all the predicates at positions `X..` between `X` an the top are
/// also defaulted traits.
pub fn coinductive_match<I>(&mut self, cycle: I) -> bool
where
I: Iterator<Item = ty::Predicate<'tcx>>,
{
let mut cycle = cycle;
cycle.all(|predicate| self.coinductive_predicate(predicate))
}
fn coinductive_predicate(&self, predicate: ty::Predicate<'tcx>) -> bool {
let result = match predicate {
ty::Predicate::Trait(ref data) => self.tcx().trait_is_auto(data.def_id()),
_ => false,
};
debug!("coinductive_predicate({:?}) = {:?}", predicate, result);
result
}
/// Further evaluate `candidate` to decide whether all type parameters match and whether nested
/// obligations are met. Returns whether `candidate` remains viable after this further
/// scrutiny.
fn evaluate_candidate<'o>(
&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
candidate: &SelectionCandidate<'tcx>,
) -> Result<EvaluationResult, OverflowError> {
debug!(
"evaluate_candidate: depth={} candidate={:?}",
stack.obligation.recursion_depth, candidate
);
let result = self.evaluation_probe(|this| {
let candidate = (*candidate).clone();
match this.confirm_candidate(stack.obligation, candidate) {
Ok(selection) => this.evaluate_predicates_recursively(
stack.list(),
selection.nested_obligations().into_iter()
),
Err(..) => Ok(EvaluatedToErr),
}
})?;
debug!(
"evaluate_candidate: depth={} result={:?}",
stack.obligation.recursion_depth, result
);
Ok(result)
}
fn check_evaluation_cache(
&self,
param_env: ty::ParamEnv<'tcx>,
trait_ref: ty::PolyTraitRef<'tcx>,
) -> Option<EvaluationResult> {
let tcx = self.tcx();
if self.can_use_global_caches(param_env) {
let cache = tcx.evaluation_cache.hashmap.borrow();
if let Some(cached) = cache.get(&trait_ref) {
return Some(cached.get(tcx));
}
}
self.infcx
.evaluation_cache
.hashmap
.borrow()
.get(&trait_ref)
.map(|v| v.get(tcx))
}
fn insert_evaluation_cache(
&mut self,
param_env: ty::ParamEnv<'tcx>,
trait_ref: ty::PolyTraitRef<'tcx>,
dep_node: DepNodeIndex,
result: EvaluationResult,
) {
// Avoid caching results that depend on more than just the trait-ref
// - the stack can create recursion.
if result.is_stack_dependent() {
return;
}
if self.can_use_global_caches(param_env) {
if !trait_ref.has_local_value() {
debug!(
"insert_evaluation_cache(trait_ref={:?}, candidate={:?}) global",
trait_ref, result,
);
// This may overwrite the cache with the same value
// FIXME: Due to #50507 this overwrites the different values
// This should be changed to use HashMapExt::insert_same
// when that is fixed
self.tcx()
.evaluation_cache
.hashmap
.borrow_mut()
.insert(trait_ref, WithDepNode::new(dep_node, result));
return;
}
}
debug!(
"insert_evaluation_cache(trait_ref={:?}, candidate={:?})",
trait_ref, result,
);
self.infcx
.evaluation_cache
.hashmap
.borrow_mut()
.insert(trait_ref, WithDepNode::new(dep_node, result));
}
// For various reasons, it's possible for a subobligation
// to have a *lower* recursion_depth than the obligation used to create it.
// Projection sub-obligations may be returned from the projection cache,
// which results in obligations with an 'old' recursion_depth.
// Additionally, methods like ty::wf::obligations and
// InferCtxt.subtype_predicate produce subobligations without
// taking in a 'parent' depth, causing the generated subobligations
// to have a recursion_depth of 0
//
// To ensure that obligation_depth never decreasees, we force all subobligations
// to have at least the depth of the original obligation.
fn add_depth<T: 'cx, I: Iterator<Item = &'cx mut Obligation<'tcx, T>>>(&self, it: I,
min_depth: usize) {
it.for_each(|o| o.recursion_depth = cmp::max(min_depth, o.recursion_depth) + 1);
}
// Check that the recursion limit has not been exceeded.
//
// The weird return type of this function allows it to be used with the 'try' (?)
// operator within certain functions
fn check_recursion_limit<T: Display + TypeFoldable<'tcx>, V: Display + TypeFoldable<'tcx>>(
&self,
obligation: &Obligation<'tcx, T>,
error_obligation: &Obligation<'tcx, V>
) -> Result<(), OverflowError> {
let recursion_limit = *self.infcx.tcx.sess.recursion_limit.get();
if obligation.recursion_depth >= recursion_limit {
match self.query_mode {
TraitQueryMode::Standard => {
self.infcx().report_overflow_error(error_obligation, true);
}
TraitQueryMode::Canonical => {
return Err(OverflowError);
}
}
}
Ok(())
}
///////////////////////////////////////////////////////////////////////////
// CANDIDATE ASSEMBLY
//
// The selection process begins by examining all in-scope impls,
// caller obligations, and so forth and assembling a list of
// candidates. See the [rustc guide] for more details.
//
// [rustc guide]:
// https://rust-lang.github.io/rustc-guide/traits/resolution.html#candidate-assembly
fn candidate_from_obligation<'o>(
&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
// Watch out for overflow. This intentionally bypasses (and does
// not update) the cache.
self.check_recursion_limit(&stack.obligation, &stack.obligation)?;
// Check the cache. Note that we freshen the trait-ref
// separately rather than using `stack.fresh_trait_ref` --
// this is because we want the unbound variables to be
// replaced with fresh types starting from index 0.
let cache_fresh_trait_pred = self.infcx.freshen(stack.obligation.predicate.clone());
debug!(
"candidate_from_obligation(cache_fresh_trait_pred={:?}, obligation={:?})",
cache_fresh_trait_pred, stack
);
debug_assert!(!stack.obligation.predicate.has_escaping_bound_vars());
if let Some(c) =
self.check_candidate_cache(stack.obligation.param_env, &cache_fresh_trait_pred)
{
debug!("CACHE HIT: SELECT({:?})={:?}", cache_fresh_trait_pred, c);
return c;
}
// If no match, compute result and insert into cache.
//
// FIXME(nikomatsakis) -- this cache is not taking into
// account cycles that may have occurred in forming the
// candidate. I don't know of any specific problems that
// result but it seems awfully suspicious.
let (candidate, dep_node) =
self.in_task(|this| this.candidate_from_obligation_no_cache(stack));
debug!(
"CACHE MISS: SELECT({:?})={:?}",
cache_fresh_trait_pred, candidate
);
self.insert_candidate_cache(
stack.obligation.param_env,
cache_fresh_trait_pred,
dep_node,
candidate.clone(),
);
candidate
}
fn in_task<OP, R>(&mut self, op: OP) -> (R, DepNodeIndex)
where
OP: FnOnce(&mut Self) -> R,
{
let (result, dep_node) = self.tcx()
.dep_graph
.with_anon_task(DepKind::TraitSelect, || op(self));
self.tcx().dep_graph.read_index(dep_node);
(result, dep_node)
}
// Treat negative impls as unimplemented
fn filter_negative_impls(
&self,
candidate: SelectionCandidate<'tcx>,
) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
if let ImplCandidate(def_id) = candidate {
if !self.allow_negative_impls
&& self.tcx().impl_polarity(def_id) == hir::ImplPolarity::Negative
{
return Err(Unimplemented);
}
}
Ok(Some(candidate))
}
fn candidate_from_obligation_no_cache<'o>(
&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> {
if stack.obligation.predicate.references_error() {
// If we encounter a `Error`, we generally prefer the
// most "optimistic" result in response -- that is, the
// one least likely to report downstream errors. But
// because this routine is shared by coherence and by
// trait selection, there isn't an obvious "right" choice
// here in that respect, so we opt to just return
// ambiguity and let the upstream clients sort it out.
return Ok(None);
}
if let Some(conflict) = self.is_knowable(stack) {
debug!("coherence stage: not knowable");
if self.intercrate_ambiguity_causes.is_some() {
debug!("evaluate_stack: intercrate_ambiguity_causes is some");
// Heuristics: show the diagnostics when there are no candidates in crate.
if let Ok(candidate_set) = self.assemble_candidates(stack) {
let mut no_candidates_apply = true;
{
let evaluated_candidates = candidate_set
.vec
.iter()
.map(|c| self.evaluate_candidate(stack, &c));
for ec in evaluated_candidates {
match ec {
Ok(c) => {
if c.may_apply() {
no_candidates_apply = false;
break;
}
}
Err(e) => return Err(e.into()),
}
}
}
if !candidate_set.ambiguous && no_candidates_apply {
let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
let self_ty = trait_ref.self_ty();
let trait_desc = trait_ref.to_string();
let self_desc = if self_ty.has_concrete_skeleton() {
Some(self_ty.to_string())
} else {
None
};
let cause = if let Conflict::Upstream = conflict {
IntercrateAmbiguityCause::UpstreamCrateUpdate {
trait_desc,
self_desc,
}
} else {
IntercrateAmbiguityCause::DownstreamCrate {
trait_desc,
self_desc,
}
};
debug!("evaluate_stack: pushing cause = {:?}", cause);
self.intercrate_ambiguity_causes
.as_mut()
.unwrap()
.push(cause);
}
}
}
return Ok(None);
}
let candidate_set = self.assemble_candidates(stack)?;
if candidate_set.ambiguous {
debug!("candidate set contains ambig");
return Ok(None);
}
let mut candidates = candidate_set.vec;
debug!(
"assembled {} candidates for {:?}: {:?}",
candidates.len(),
stack,
candidates
);
// At this point, we know that each of the entries in the
// candidate set is *individually* applicable. Now we have to
// figure out if they contain mutual incompatibilities. This
// frequently arises if we have an unconstrained input type --
// for example, we are looking for $0:Eq where $0 is some
// unconstrained type variable. In that case, we'll get a
// candidate which assumes $0 == int, one that assumes $0 ==
// usize, etc. This spells an ambiguity.
// If there is more than one candidate, first winnow them down
// by considering extra conditions (nested obligations and so
// forth). We don't winnow if there is exactly one
// candidate. This is a relatively minor distinction but it
// can lead to better inference and error-reporting. An
// example would be if there was an impl:
//
// impl<T:Clone> Vec<T> { fn push_clone(...) { ... } }
//
// and we were to see some code `foo.push_clone()` where `boo`
// is a `Vec<Bar>` and `Bar` does not implement `Clone`. If
// we were to winnow, we'd wind up with zero candidates.
// Instead, we select the right impl now but report `Bar does
// not implement Clone`.
if candidates.len() == 1 {
return self.filter_negative_impls(candidates.pop().unwrap());
}
// Winnow, but record the exact outcome of evaluation, which
// is needed for specialization. Propagate overflow if it occurs.
let mut candidates = candidates
.into_iter()
.map(|c| match self.evaluate_candidate(stack, &c) {
Ok(eval) if eval.may_apply() => Ok(Some(EvaluatedCandidate {
candidate: c,
evaluation: eval,
})),
Ok(_) => Ok(None),
Err(OverflowError) => Err(Overflow),
})
.flat_map(Result::transpose)
.collect::<Result<Vec<_>, _>>()?;
debug!(
"winnowed to {} candidates for {:?}: {:?}",
candidates.len(),
stack,
candidates
);
// If there are STILL multiple candidates, we can further
// reduce the list by dropping duplicates -- including
// resolving specializations.
if candidates.len() > 1 {
let mut i = 0;
while i < candidates.len() {
let is_dup = (0..candidates.len()).filter(|&j| i != j).any(|j| {
self.candidate_should_be_dropped_in_favor_of(&candidates[i], &candidates[j])
});
if is_dup {
debug!(
"Dropping candidate #{}/{}: {:?}",
i,
candidates.len(),
candidates[i]
);
candidates.swap_remove(i);
} else {
debug!(
"Retaining candidate #{}/{}: {:?}",
i,
candidates.len(),
candidates[i]
);
i += 1;
// If there are *STILL* multiple candidates, give up
// and report ambiguity.
if i > 1 {
debug!("multiple matches, ambig");
return Ok(None);
}
}
}
}
// If there are *NO* candidates, then there are no impls --
// that we know of, anyway. Note that in the case where there
// are unbound type variables within the obligation, it might
// be the case that you could still satisfy the obligation
// from another crate by instantiating the type variables with
// a type from another crate that does have an impl. This case
// is checked for in `evaluate_stack` (and hence users
// who might care about this case, like coherence, should use
// that function).
if candidates.is_empty() {
return Err(Unimplemented);
}
// Just one candidate left.
self.filter_negative_impls(candidates.pop().unwrap().candidate)
}
fn is_knowable<'o>(&mut self, stack: &TraitObligationStack<'o, 'tcx>) -> Option<Conflict> {
debug!("is_knowable(intercrate={:?})", self.intercrate);
if !self.intercrate.is_some() {
return None;
}
let obligation = &stack.obligation;
let predicate = self.infcx()
.resolve_vars_if_possible(&obligation.predicate);
// Okay to skip binder because of the nature of the
// trait-ref-is-knowable check, which does not care about
// bound regions.
let trait_ref = predicate.skip_binder().trait_ref;
let result = coherence::trait_ref_is_knowable(self.tcx(), trait_ref);
if let (
Some(Conflict::Downstream {
used_to_be_broken: true,
}),
Some(IntercrateMode::Issue43355),
) = (result, self.intercrate)
{
debug!("is_knowable: IGNORING conflict to be bug-compatible with #43355");
None
} else {
result
}
}
/// Returns `true` if the global caches can be used.
/// Do note that if the type itself is not in the
/// global tcx, the local caches will be used.
fn can_use_global_caches(&self, param_env: ty::ParamEnv<'tcx>) -> bool {
// If there are any where-clauses in scope, then we always use
// a cache local to this particular scope. Otherwise, we
// switch to a global cache. We used to try and draw
// finer-grained distinctions, but that led to a serious of
// annoying and weird bugs like #22019 and #18290. This simple
// rule seems to be pretty clearly safe and also still retains
// a very high hit rate (~95% when compiling rustc).
if !param_env.caller_bounds.is_empty() {
return false;
}
// Avoid using the master cache during coherence and just rely
// on the local cache. This effectively disables caching
// during coherence. It is really just a simplification to
// avoid us having to fear that coherence results "pollute"
// the master cache. Since coherence executes pretty quickly,
// it's not worth going to more trouble to increase the
// hit-rate I don't think.
if self.intercrate.is_some() {
return false;
}
// Otherwise, we can use the global cache.
true
}
fn check_candidate_cache(
&mut self,
param_env: ty::ParamEnv<'tcx>,
cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>,
) -> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>> {
let tcx = self.tcx();
let trait_ref = &cache_fresh_trait_pred.skip_binder().trait_ref;
if self.can_use_global_caches(param_env) {
let cache = tcx.selection_cache.hashmap.borrow();
if let Some(cached) = cache.get(&trait_ref) {
return Some(cached.get(tcx));
}
}
self.infcx
.selection_cache
.hashmap
.borrow()
.get(trait_ref)
.map(|v| v.get(tcx))
}
/// Determines whether can we safely cache the result
/// of selecting an obligation. This is almost always 'true',
/// except when dealing with certain ParamCandidates.
///
/// Ordinarily, a ParamCandidate will contain no inference variables,
/// since it was usually produced directly from a DefId. However,
/// certain cases (currently only librustdoc's blanket impl finder),
/// a ParamEnv may be explicitly constructed with inference types.
/// When this is the case, we do *not* want to cache the resulting selection
/// candidate. This is due to the fact that it might not always be possible
/// to equate the obligation's trait ref and the candidate's trait ref,
/// if more constraints end up getting added to an inference variable.
///
/// Because of this, we always want to re-run the full selection
/// process for our obligation the next time we see it, since
/// we might end up picking a different SelectionCandidate (or none at all)
fn can_cache_candidate(&self,
result: &SelectionResult<'tcx, SelectionCandidate<'tcx>>
) -> bool {
match result {
Ok(Some(SelectionCandidate::ParamCandidate(trait_ref))) => {
!trait_ref.skip_binder().input_types().any(|t| t.walk().any(|t_| t_.is_ty_infer()))
},
_ => true
}
}
fn insert_candidate_cache(
&mut self,
param_env: ty::ParamEnv<'tcx>,
cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
dep_node: DepNodeIndex,
candidate: SelectionResult<'tcx, SelectionCandidate<'tcx>>,
) {
let tcx = self.tcx();
let trait_ref = cache_fresh_trait_pred.skip_binder().trait_ref;
if !self.can_cache_candidate(&candidate) {
debug!("insert_candidate_cache(trait_ref={:?}, candidate={:?} -\
candidate is not cacheable", trait_ref, candidate);
return;
}
if self.can_use_global_caches(param_env) {
if let Err(Overflow) = candidate {
// Don't cache overflow globally; we only produce this
// in certain modes.
} else if !trait_ref.has_local_value() {
if !candidate.has_local_value() {
debug!(
"insert_candidate_cache(trait_ref={:?}, candidate={:?}) global",
trait_ref, candidate,
);
// This may overwrite the cache with the same value
tcx.selection_cache
.hashmap
.borrow_mut()
.insert(trait_ref, WithDepNode::new(dep_node, candidate));
return;
}
}
}
debug!(
"insert_candidate_cache(trait_ref={:?}, candidate={:?}) local",
trait_ref, candidate,
);
self.infcx
.selection_cache
.hashmap
.borrow_mut()
.insert(trait_ref, WithDepNode::new(dep_node, candidate));
}
fn assemble_candidates<'o>(
&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
) -> Result<SelectionCandidateSet<'tcx>, SelectionError<'tcx>> {
let TraitObligationStack { obligation, .. } = *stack;
let ref obligation = Obligation {
param_env: obligation.param_env,
cause: obligation.cause.clone(),
recursion_depth: obligation.recursion_depth,
predicate: self.infcx()
.resolve_vars_if_possible(&obligation.predicate),
};
if obligation.predicate.skip_binder().self_ty().is_ty_var() {
// Self is a type variable (e.g., `_: AsRef<str>`).
//
// This is somewhat problematic, as the current scheme can't really
// handle it turning to be a projection. This does end up as truly
// ambiguous in most cases anyway.
//
// Take the fast path out - this also improves
// performance by preventing assemble_candidates_from_impls from
// matching every impl for this trait.
return Ok(SelectionCandidateSet {
vec: vec![],
ambiguous: true,
});
}
let mut candidates = SelectionCandidateSet {
vec: Vec::new(),
ambiguous: false,
};
self.assemble_candidates_for_trait_alias(obligation, &mut candidates)?;
// Other bounds. Consider both in-scope bounds from fn decl
// and applicable impls. There is a certain set of precedence rules here.
let def_id = obligation.predicate.def_id();
let lang_items = self.tcx().lang_items();
if lang_items.copy_trait() == Some(def_id) {
debug!(
"obligation self ty is {:?}",
obligation.predicate.skip_binder().self_ty()
);
// User-defined copy impls are permitted, but only for
// structs and enums.
self.assemble_candidates_from_impls(obligation, &mut candidates)?;
// For other types, we'll use the builtin rules.
let copy_conditions = self.copy_clone_conditions(obligation);
self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates)?;
} else if lang_items.sized_trait() == Some(def_id) {
// Sized is never implementable by end-users, it is
// always automatically computed.
let sized_conditions = self.sized_conditions(obligation);
self.assemble_builtin_bound_candidates(sized_conditions, &mut candidates)?;
} else if lang_items.unsize_trait() == Some(def_id) {
self.assemble_candidates_for_unsizing(obligation, &mut candidates);
} else {
if lang_items.clone_trait() == Some(def_id) {
// Same builtin conditions as `Copy`, i.e., every type which has builtin support
// for `Copy` also has builtin support for `Clone`, + tuples and arrays of `Clone`
// types have builtin support for `Clone`.
let clone_conditions = self.copy_clone_conditions(obligation);
self.assemble_builtin_bound_candidates(clone_conditions, &mut candidates)?;
}
self.assemble_generator_candidates(obligation, &mut candidates)?;
self.assemble_closure_candidates(obligation, &mut candidates)?;
self.assemble_fn_pointer_candidates(obligation, &mut candidates)?;
self.assemble_candidates_from_impls(obligation, &mut candidates)?;
self.assemble_candidates_from_object_ty(obligation, &mut candidates);
}
self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
self.assemble_candidates_from_caller_bounds(stack, &mut candidates)?;
// Auto implementations have lower priority, so we only
// consider triggering a default if there is no other impl that can apply.
if candidates.vec.is_empty() {
self.assemble_candidates_from_auto_impls(obligation, &mut candidates)?;
}
debug!("candidate list size: {}", candidates.vec.len());
Ok(candidates)
}
fn assemble_candidates_from_projected_tys(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) {
debug!("assemble_candidates_for_projected_tys({:?})", obligation);
// before we go into the whole placeholder thing, just
// quickly check if the self-type is a projection at all.
match obligation.predicate.skip_binder().trait_ref.self_ty().sty {
ty::Projection(_) | ty::Opaque(..) => {}
ty::Infer(ty::TyVar(_)) => {
span_bug!(
obligation.cause.span,
"Self=_ should have been handled by assemble_candidates"
);
}
_ => return,
}
let result = self.infcx.probe(|snapshot| {
self.match_projection_obligation_against_definition_bounds(
obligation,
snapshot,
)
});
if result {
candidates.vec.push(ProjectionCandidate);
}
}
fn match_projection_obligation_against_definition_bounds(
&mut self,
obligation: &TraitObligation<'tcx>,
snapshot: &CombinedSnapshot<'_, 'tcx>,
) -> bool {
let poly_trait_predicate = self.infcx()
.resolve_vars_if_possible(&obligation.predicate);
let (placeholder_trait_predicate, placeholder_map) = self.infcx()
.replace_bound_vars_with_placeholders(&poly_trait_predicate);
debug!(
"match_projection_obligation_against_definition_bounds: \
placeholder_trait_predicate={:?}",
placeholder_trait_predicate,
);
let (def_id, substs) = match placeholder_trait_predicate.trait_ref.self_ty().sty {
ty::Projection(ref data) => (data.trait_ref(self.tcx()).def_id, data.substs),
ty::Opaque(def_id, substs) => (def_id, substs),
_ => {
span_bug!(
obligation.cause.span,
"match_projection_obligation_against_definition_bounds() called \
but self-ty is not a projection: {:?}",
placeholder_trait_predicate.trait_ref.self_ty()
);
}
};
debug!(
"match_projection_obligation_against_definition_bounds: \
def_id={:?}, substs={:?}",
def_id, substs
);
let predicates_of = self.tcx().predicates_of(def_id);
let bounds = predicates_of.instantiate(self.tcx(), substs);
debug!(
"match_projection_obligation_against_definition_bounds: \
bounds={:?}",
bounds
);
let elaborated_predicates = util::elaborate_predicates(self.tcx(), bounds.predicates);
let matching_bound = elaborated_predicates
.filter_to_traits()
.find(|bound| {
self.infcx.probe(|_| {
self.match_projection(
obligation,
bound.clone(),
placeholder_trait_predicate.trait_ref.clone(),
&placeholder_map,
snapshot,
)
})
});
debug!(
"match_projection_obligation_against_definition_bounds: \
matching_bound={:?}",
matching_bound
);
match matching_bound {
None => false,
Some(bound) => {
// Repeat the successful match, if any, this time outside of a probe.
let result = self.match_projection(
obligation,
bound,
placeholder_trait_predicate.trait_ref.clone(),
&placeholder_map,
snapshot,
);
assert!(result);
true
}
}
}
fn match_projection(
&mut self,
obligation: &TraitObligation<'tcx>,
trait_bound: ty::PolyTraitRef<'tcx>,
placeholder_trait_ref: ty::TraitRef<'tcx>,
placeholder_map: &PlaceholderMap<'tcx>,
snapshot: &CombinedSnapshot<'_, 'tcx>,
) -> bool {
debug_assert!(!placeholder_trait_ref.has_escaping_bound_vars());
self.infcx
.at(&obligation.cause, obligation.param_env)
.sup(ty::Binder::dummy(placeholder_trait_ref), trait_bound)
.is_ok()
&&
self.infcx.leak_check(false, placeholder_map, snapshot).is_ok()
}
/// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller
/// supplied to find out whether it is listed among them.
///
/// Never affects inference environment.
fn assemble_candidates_from_caller_bounds<'o>(
&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) -> Result<(), SelectionError<'tcx>> {
debug!(
"assemble_candidates_from_caller_bounds({:?})",
stack.obligation
);
let all_bounds = stack
.obligation
.param_env
.caller_bounds
.iter()
.filter_map(|o| o.to_opt_poly_trait_ref());
// Micro-optimization: filter out predicates relating to different traits.
let matching_bounds =
all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
// Keep only those bounds which may apply, and propagate overflow if it occurs.
let mut param_candidates = vec![];
for bound in matching_bounds {
let wc = self.evaluate_where_clause(stack, bound.clone())?;
if wc.may_apply() {
param_candidates.push(ParamCandidate(bound));
}
}
candidates.vec.extend(param_candidates);
Ok(())
}
fn evaluate_where_clause<'o>(
&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
where_clause_trait_ref: ty::PolyTraitRef<'tcx>,
) -> Result<EvaluationResult, OverflowError> {
self.evaluation_probe(|this| {
match this.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
Ok(obligations) => {
this.evaluate_predicates_recursively(stack.list(), obligations.into_iter())
}
Err(()) => Ok(EvaluatedToErr),
}
})
}
fn assemble_generator_candidates(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) -> Result<(), SelectionError<'tcx>> {
if self.tcx().lang_items().gen_trait() != Some(obligation.predicate.def_id()) {
return Ok(());
}
// Okay to skip binder because the substs on generator types never
// touch bound regions, they just capture the in-scope
// type/region parameters.
let self_ty = *obligation.self_ty().skip_binder();
match self_ty.sty {
ty::Generator(..) => {
debug!(
"assemble_generator_candidates: self_ty={:?} obligation={:?}",
self_ty, obligation
);
candidates.vec.push(GeneratorCandidate);
}
ty::Infer(ty::TyVar(_)) => {
debug!("assemble_generator_candidates: ambiguous self-type");
candidates.ambiguous = true;
}
_ => {}
}
Ok(())
}
/// Checks for the artificial impl that the compiler will create for an obligation like `X :
/// FnMut<..>` where `X` is a closure type.
///
/// Note: the type parameters on a closure candidate are modeled as *output* type
/// parameters and hence do not affect whether this trait is a match or not. They will be
/// unified during the confirmation step.
fn assemble_closure_candidates(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) -> Result<(), SelectionError<'tcx>> {
let kind = match self.tcx()
.lang_items()
.fn_trait_kind(obligation.predicate.def_id())
{
Some(k) => k,
None => {
return Ok(());
}
};
// Okay to skip binder because the substs on closure types never
// touch bound regions, they just capture the in-scope
// type/region parameters
match obligation.self_ty().skip_binder().sty {
ty::Closure(closure_def_id, closure_substs) => {
debug!(
"assemble_unboxed_candidates: kind={:?} obligation={:?}",
kind, obligation
);
match self.infcx.closure_kind(closure_def_id, closure_substs) {
Some(closure_kind) => {
debug!(
"assemble_unboxed_candidates: closure_kind = {:?}",
closure_kind
);
if closure_kind.extends(kind) {
candidates.vec.push(ClosureCandidate);
}
}
None => {
debug!("assemble_unboxed_candidates: closure_kind not yet known");
candidates.vec.push(ClosureCandidate);
}
}
}
ty::Infer(ty::TyVar(_)) => {
debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
candidates.ambiguous = true;
}
_ => {}
}
Ok(())
}
/// Implement one of the `Fn()` family for a fn pointer.
fn assemble_fn_pointer_candidates(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) -> Result<(), SelectionError<'tcx>> {
// We provide impl of all fn traits for fn pointers.
if self.tcx()
.lang_items()
.fn_trait_kind(obligation.predicate.def_id())
.is_none()
{
return Ok(());
}
// Okay to skip binder because what we are inspecting doesn't involve bound regions
let self_ty = *obligation.self_ty().skip_binder();
match self_ty.sty {
ty::Infer(ty::TyVar(_)) => {
debug!("assemble_fn_pointer_candidates: ambiguous self-type");
candidates.ambiguous = true; // could wind up being a fn() type
}
// provide an impl, but only for suitable `fn` pointers
ty::FnDef(..) | ty::FnPtr(_) => {
if let ty::FnSig {
unsafety: hir::Unsafety::Normal,
abi: Abi::Rust,
c_variadic: false,
..
} = self_ty.fn_sig(self.tcx()).skip_binder()
{
candidates.vec.push(FnPointerCandidate);
}
}
_ => {}
}
Ok(())
}
/// Search for impls that might apply to `obligation`.
fn assemble_candidates_from_impls(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) -> Result<(), SelectionError<'tcx>> {
debug!(
"assemble_candidates_from_impls(obligation={:?})",
obligation
);
self.tcx().for_each_relevant_impl(
obligation.predicate.def_id(),
obligation.predicate.skip_binder().trait_ref.self_ty(),
|impl_def_id| {
self.infcx.probe(|snapshot| {
if let Ok(_substs) = self.match_impl(impl_def_id, obligation, snapshot)
{
candidates.vec.push(ImplCandidate(impl_def_id));
}
});
},
);
Ok(())
}
fn assemble_candidates_from_auto_impls(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) -> Result<(), SelectionError<'tcx>> {
// Okay to skip binder here because the tests we do below do not involve bound regions.
let self_ty = *obligation.self_ty().skip_binder();
debug!("assemble_candidates_from_auto_impls(self_ty={:?})", self_ty);
let def_id = obligation.predicate.def_id();
if self.tcx().trait_is_auto(def_id) {
match self_ty.sty {
ty::Dynamic(..) => {
// For object types, we don't know what the closed
// over types are. This means we conservatively
// say nothing; a candidate may be added by
// `assemble_candidates_from_object_ty`.
}
ty::Foreign(..) => {
// Since the contents of foreign types is unknown,
// we don't add any `..` impl. Default traits could
// still be provided by a manual implementation for
// this trait and type.
}
ty::Param(..) | ty::Projection(..) => {
// In these cases, we don't know what the actual
// type is. Therefore, we cannot break it down
// into its constituent types. So we don't
// consider the `..` impl but instead just add no
// candidates: this means that typeck will only
// succeed if there is another reason to believe
// that this obligation holds. That could be a
// where-clause or, in the case of an object type,
// it could be that the object type lists the
// trait (e.g., `Foo+Send : Send`). See
// `compile-fail/typeck-default-trait-impl-send-param.rs`
// for an example of a test case that exercises
// this path.
}
ty::Infer(ty::TyVar(_)) => {
// the auto impl might apply, we don't know
candidates.ambiguous = true;
}
ty::Generator(_, _, movability)
if self.tcx().lang_items().unpin_trait() == Some(def_id) =>
{
match movability {
hir::GeneratorMovability::Static => {
// Immovable generators are never `Unpin`, so
// suppress the normal auto-impl candidate for it.
}
hir::GeneratorMovability::Movable => {
// Movable generators are always `Unpin`, so add an
// unconditional builtin candidate.
candidates.vec.push(BuiltinCandidate {
has_nested: false,
});
}
}
}
_ => candidates.vec.push(AutoImplCandidate(def_id.clone())),
}
}
Ok(())
}
/// Search for impls that might apply to `obligation`.
fn assemble_candidates_from_object_ty(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) {
debug!(
"assemble_candidates_from_object_ty(self_ty={:?})",
obligation.self_ty().skip_binder()
);
self.infcx.probe(|_snapshot| {
// The code below doesn't care about regions, and the
// self-ty here doesn't escape this probe, so just erase
// any LBR.
let self_ty = self.tcx().erase_late_bound_regions(&obligation.self_ty());
let poly_trait_ref = match self_ty.sty {
ty::Dynamic(ref data, ..) => {
if data.auto_traits()
.any(|did| did == obligation.predicate.def_id())
{
debug!(
"assemble_candidates_from_object_ty: matched builtin bound, \
pushing candidate"
);
candidates.vec.push(BuiltinObjectCandidate);
return;
}
if let Some(principal) = data.principal() {
principal.with_self_ty(self.tcx(), self_ty)
} else {
// Only auto-trait bounds exist.
return;
}
}
ty::Infer(ty::TyVar(_)) => {
debug!("assemble_candidates_from_object_ty: ambiguous");
candidates.ambiguous = true; // could wind up being an object type
return;
}
_ => return,
};
debug!(
"assemble_candidates_from_object_ty: poly_trait_ref={:?}",
poly_trait_ref
);
// Count only those upcast versions that match the trait-ref
// we are looking for. Specifically, do not only check for the
// correct trait, but also the correct type parameters.
// For example, we may be trying to upcast `Foo` to `Bar<i32>`,
// but `Foo` is declared as `trait Foo : Bar<u32>`.
let upcast_trait_refs = util::supertraits(self.tcx(), poly_trait_ref)
.filter(|upcast_trait_ref| {
self.infcx.probe(|_| {
let upcast_trait_ref = upcast_trait_ref.clone();
self.match_poly_trait_ref(obligation, upcast_trait_ref)
.is_ok()
})
})
.count();
if upcast_trait_refs > 1 {
// Can be upcast in many ways; need more type information.
candidates.ambiguous = true;
} else if upcast_trait_refs == 1 {
candidates.vec.push(ObjectCandidate);
}
})
}
/// Search for unsizing that might apply to `obligation`.
fn assemble_candidates_for_unsizing(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) {
// We currently never consider higher-ranked obligations e.g.
// `for<'a> &'a T: Unsize<Trait+'a>` to be implemented. This is not
// because they are a priori invalid, and we could potentially add support
// for them later, it's just that there isn't really a strong need for it.
// A `T: Unsize<U>` obligation is always used as part of a `T: CoerceUnsize<U>`
// impl, and those are generally applied to concrete types.
//
// That said, one might try to write a fn with a where clause like
// for<'a> Foo<'a, T>: Unsize<Foo<'a, Trait>>
// where the `'a` is kind of orthogonal to the relevant part of the `Unsize`.
// Still, you'd be more likely to write that where clause as
// T: Trait
// so it seems ok if we (conservatively) fail to accept that `Unsize`
// obligation above. Should be possible to extend this in the future.
let source = match obligation.self_ty().no_bound_vars() {
Some(t) => t,
None => {
// Don't add any candidates if there are bound regions.
return;
}
};
let target = obligation
.predicate
.skip_binder()
.trait_ref
.substs
.type_at(1);
debug!(
"assemble_candidates_for_unsizing(source={:?}, target={:?})",
source, target
);
let may_apply = match (&source.sty, &target.sty) {
// Trait+Kx+'a -> Trait+Ky+'b (upcasts).
(&ty::Dynamic(ref data_a, ..), &ty::Dynamic(ref data_b, ..)) => {
// Upcasts permit two things:
//
// 1. Dropping builtin bounds, e.g., `Foo+Send` to `Foo`
// 2. Tightening the region bound, e.g., `Foo+'a` to `Foo+'b` if `'a : 'b`
//
// Note that neither of these changes requires any
// change at runtime. Eventually this will be
// generalized.
//
// We always upcast when we can because of reason
// #2 (region bounds).
data_a.principal_def_id() == data_b.principal_def_id()
&& data_b.auto_traits()
// All of a's auto traits need to be in b's auto traits.
.all(|b| data_a.auto_traits().any(|a| a == b))
}
// T -> Trait.
(_, &ty::Dynamic(..)) => true,
// Ambiguous handling is below T -> Trait, because inference
// variables can still implement Unsize<Trait> and nested
// obligations will have the final say (likely deferred).
(&ty::Infer(ty::TyVar(_)), _) | (_, &ty::Infer(ty::TyVar(_))) => {
debug!("assemble_candidates_for_unsizing: ambiguous");
candidates.ambiguous = true;
false
}
// [T; n] -> [T].
(&ty::Array(..), &ty::Slice(_)) => true,
// Struct<T> -> Struct<U>.
(&ty::Adt(def_id_a, _), &ty::Adt(def_id_b, _)) if def_id_a.is_struct() => {
def_id_a == def_id_b
}
// (.., T) -> (.., U).
(&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => tys_a.len() == tys_b.len(),
_ => false,
};
if may_apply {
candidates.vec.push(BuiltinUnsizeCandidate);
}
}
fn assemble_candidates_for_trait_alias(
&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) -> Result<(), SelectionError<'tcx>> {
// Okay to skip binder here because the tests we do below do not involve bound regions.
let self_ty = *obligation.self_ty().skip_binder();
debug!("assemble_candidates_for_trait_alias(self_ty={:?})", self_ty);
let def_id = obligation.predicate.def_id();
if self.tcx().is_trait_alias(def_id) {
candidates.vec.push(TraitAliasCandidate(def_id.clone()));
}
Ok(())
}
///////////////////////////////////////////////////////////////////////////
// WINNOW
//
// Winnowing is the process of attempting to resolve ambiguity by
// probing further. During the winnowing process, we unify all
// type variables and then we also attempt to evaluate recursive
// bounds to see if they are satisfied.
/// Returns `true` if `victim` should be dropped in favor of
/// `other`. Generally speaking we will drop duplicate
/// candidates and prefer where-clause candidates.
///
/// See the comment for "SelectionCandidate" for more details.
fn candidate_should_be_dropped_in_favor_of(
&mut self,
victim: &EvaluatedCandidate<'tcx>,
other: &EvaluatedCandidate<'tcx>,
) -> bool {
if victim.candidate == other.candidate {
return true;
}
// Check if a bound would previously have been removed when normalizing
// the param_env so that it can be given the lowest priority. See
// #50825 for the motivation for this.
let is_global =
|cand: &ty::PolyTraitRef<'_>| cand.is_global() && !cand.has_late_bound_regions();
match other.candidate {
// Prefer BuiltinCandidate { has_nested: false } to anything else.
// This is a fix for #53123 and prevents winnowing from accidentally extending the
// lifetime of a variable.
BuiltinCandidate { has_nested: false } => true,
ParamCandidate(ref cand) => match victim.candidate {
AutoImplCandidate(..) => {
bug!(
"default implementations shouldn't be recorded \
when there are other valid candidates"
);
}
// Prefer BuiltinCandidate { has_nested: false } to anything else.
// This is a fix for #53123 and prevents winnowing from accidentally extending the
// lifetime of a variable.
BuiltinCandidate { has_nested: false } => false,
ImplCandidate(..)
| ClosureCandidate
| GeneratorCandidate
| FnPointerCandidate
| BuiltinObjectCandidate
| BuiltinUnsizeCandidate
| BuiltinCandidate { .. }
| TraitAliasCandidate(..) => {
// Global bounds from the where clause should be ignored
// here (see issue #50825). Otherwise, we have a where
// clause so don't go around looking for impls.
!is_global(cand)
}
ObjectCandidate | ProjectionCandidate => {
// Arbitrarily give param candidates priority
// over projection and object candidates.
!is_global(cand)
}
ParamCandidate(..) => false,
},
ObjectCandidate | ProjectionCandidate => match victim.candidate {
AutoImplCandidate(..) => {
bug!(
"default implementations shouldn't be recorded \
when there are other valid candidates"
);
}
// Prefer BuiltinCandidate { has_nested: false } to anything else.
// This is a fix for #53123 and prevents winnowing from accidentally extending the
// lifetime of a variable.
BuiltinCandidate { has_nested: false } => false,
ImplCandidate(..)
| ClosureCandidate
| GeneratorCandidate
| FnPointerCandidate
| BuiltinObjectCandidate
| BuiltinUnsizeCandidate
| BuiltinCandidate { .. }
| TraitAliasCandidate(..) => true,
ObjectCandidate | ProjectionCandidate => {
// Arbitrarily give param candidates priority
// over projection and object candidates.
true
}
ParamCandidate(ref cand) => is_global(cand),
},
ImplCandidate(other_def) => {
// See if we can toss out `victim` based on specialization.
// This requires us to know *for sure* that the `other` impl applies
// i.e., EvaluatedToOk:
if other.evaluation.must_apply_modulo_regions() {
match victim.candidate {
ImplCandidate(victim_def) => {
let tcx = self.tcx().global_tcx();
return tcx.specializes((other_def, victim_def))
|| tcx.impls_are_allowed_to_overlap(
other_def, victim_def).is_some();
}
ParamCandidate(ref cand) => {
// Prefer the impl to a global where clause candidate.
return is_global(cand);
}
_ => (),
}
}
false
}
ClosureCandidate
| GeneratorCandidate
| FnPointerCandidate
| BuiltinObjectCandidate
| BuiltinUnsizeCandidate
| BuiltinCandidate { has_nested: true } => {
match victim.candidate {
ParamCandidate(ref cand) => {
// Prefer these to a global where-clause bound
// (see issue #50825)
is_global(cand) && other.evaluation.must_apply_modulo_regions()
}
_ => false,
}
}
_ => false,
}
}
///////////////////////////////////////////////////////////////////////////
// BUILTIN BOUNDS
//
// These cover the traits that are built-in to the language
// itself: `Copy`, `Clone` and `Sized`.
fn assemble_builtin_bound_candidates(
&mut self,
conditions: BuiltinImplConditions<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>,
) -> Result<(), SelectionError<'tcx>> {
match conditions {
BuiltinImplConditions::Where(nested) => {
debug!("builtin_bound: nested={:?}", nested);
candidates.vec.push(BuiltinCandidate {
has_nested: nested.skip_binder().len() > 0,
});
}
BuiltinImplConditions::None => {}
BuiltinImplConditions::Ambiguous => {
debug!("assemble_builtin_bound_candidates: ambiguous builtin");
candidates.ambiguous = true;
}
}
Ok(())
}
fn sized_conditions(
&mut self,
obligation: &TraitObligation<'tcx>,
) -> BuiltinImplConditions<'tcx> {
use self::BuiltinImplConditions::{Ambiguous, None, Where};
// NOTE: binder moved to (*)
let self_ty = self.infcx
.shallow_resolve(obligation.predicate.skip_binder().self_ty());
match self_ty.sty {
ty::Infer(ty::IntVar(_))
| ty::Infer(ty::FloatVar(_))
| ty::Uint(_)
| ty::Int(_)
| ty::Bool
| ty::Float(_)
| ty::FnDef(..)
| ty::FnPtr(_)
| ty::RawPtr(..)
| ty::Char
| ty::Ref(..)
| ty::Generator(..)
| ty::GeneratorWitness(..)
| ty::Array(..)
| ty::Closure(..)
| ty::Never
| ty::Error => {
// safe for everything
Where(ty::Binder::dummy(Vec::new()))
}
ty::Str | ty::Slice(_) | ty::Dynamic(..) | ty::Foreign(..) => None,
ty::Tuple(tys) => {
Where(ty::Binder::bind(tys.last().into_iter().map(|k| k.expect_ty()).collect()))
}
ty::Adt(def, substs) => {
let sized_crit = def.sized_constraint(self.tcx());
// (*) binder moved here
Where(ty::Binder::bind(
sized_crit
.iter()
.map(|ty| ty.subst(self.tcx(), substs))
.collect(),
))
}
ty::Projection(_) | ty::Param(_) | ty::Opaque(..) => None,
ty::Infer(ty::TyVar(_)) => Ambiguous,
ty::UnnormalizedProjection(..)
| ty::Placeholder(..)
| ty::Bound(..)
| ty::Infer(ty::FreshTy(_))
| ty::Infer(ty::FreshIntTy(_))
| ty::Infer(ty::FreshFloatTy(_)) => {
bug!(
"asked to assemble builtin bounds of unexpected type: {:?}",
self_ty
);
}
}
}
fn copy_clone_conditions(
&mut self,
obligation: &TraitObligation<'tcx>,
) -> BuiltinImplConditions<'tcx> {
// NOTE: binder moved to (*)
let self_ty = self.infcx
.shallow_resolve(obligation.predicate.skip_binder().self_ty());
use self::BuiltinImplConditions::{Ambiguous, None, Where};
match self_ty.sty {
ty::Infer(ty::IntVar(_))
| ty::Infer(ty::FloatVar(_))
| ty::FnDef(..)
| ty::FnPtr(_)
| ty::Error => Where(ty::Binder::dummy(Vec::new())),
ty::Uint(_)
| ty::Int(_)
| ty::Bool
| ty::Float(_)
| ty::Char
| ty::RawPtr(..)
| ty::Never
| ty::Ref(_, _, hir::MutImmutable) => {
// Implementations provided in libcore
None
}
ty::Dynamic(..)
| ty::Str
| ty::Slice(..)
| ty::Generator(..)
| ty::GeneratorWitness(..)
| ty::Foreign(..)
| ty::Ref(_, _, hir::MutMutable) => None,
ty::Array(element_ty, _) => {
// (*) binder moved here
Where(ty::Binder::bind(vec![element_ty]))
}
ty::Tuple(tys) => {
// (*) binder moved here
Where(ty::Binder::bind(tys.iter().map(|k| k.expect_ty()).collect()))
}
ty::Closure(def_id, substs) => {
// (*) binder moved here
Where(ty::Binder::bind(
substs.upvar_tys(def_id, self.tcx()).collect(),
))
}
ty::Adt(..) | ty::Projection(..) | ty::Param(..) | ty::Opaque(..) => {
// Fallback to whatever user-defined impls exist in this case.
None
}
ty::Infer(ty::TyVar(_)) => {
// Unbound type variable. Might or might not have
// applicable impls and so forth, depending on what
// those type variables wind up being bound to.
Ambiguous
}
ty::UnnormalizedProjection(..)
| ty::Placeholder(..)
| ty::Bound(..)
| ty::Infer(ty::FreshTy(_))
| ty::Infer(ty::FreshIntTy(_))
| ty::Infer(ty::FreshFloatTy(_)) => {
bug!(
"asked to assemble builtin bounds of unexpected type: {:?}",
self_ty
);
}
}
}
/// For default impls, we need to break apart a type into its
/// "constituent types" -- meaning, the types that it contains.
///
/// Here are some (simple) examples:
///
/// ```
/// (i32, u32) -> [i32, u32]
/// Foo where struct Foo { x: i32, y: u32 } -> [i32, u32]
/// Bar<i32> where struct Bar<T> { x: T, y: u32 } -> [i32, u32]
/// Zed<i32> where enum Zed { A(T), B(u32) } -> [i32, u32]
/// ```
fn constituent_types_for_ty(&self, t: Ty<'tcx>) -> Vec<Ty<'tcx>> {
match t.sty {
ty::Uint(_)
| ty::Int(_)
| ty::Bool
| ty::Float(_)
| ty::FnDef(..)
| ty::FnPtr(_)
| ty::Str
| ty::Error
| ty::Infer(ty::IntVar(_))
| ty::Infer(ty::FloatVar(_))
| ty::Never
| ty::Char => Vec::new(),
ty::UnnormalizedProjection(..)
| ty::Placeholder(..)
| ty::Dynamic(..)
| ty::Param(..)
| ty::Foreign(..)
| ty::Projection(..)
| ty::Bound(..)
| ty::Infer(ty::TyVar(_))
| ty::Infer(ty::FreshTy(_))
| ty::Infer(ty::FreshIntTy(_))
| ty::Infer(ty::FreshFloatTy(_)) => {
bug!(
"asked to assemble constituent types of unexpected type: {:?}",
t
);
}
ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => {
vec![element_ty]
}
ty::Array(element_ty, _) | ty::Slice(element_ty) => vec![element_ty],
ty::Tuple(ref tys) => {
// (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
tys.iter().map(|k| k.expect_ty()).collect()
}
ty::Closure(def_id, ref substs) => substs.upvar_tys(def_id, self.tcx()).collect(),
ty::Generator(def_id, ref substs, _) => {
let witness = substs.witness(def_id, self.tcx());
substs
.upvar_tys(def_id, self.tcx())
.chain(iter::once(witness))
.collect()
}
ty::GeneratorWitness(types) => {
// This is sound because no regions in the witness can refer to
// the binder outside the witness. So we'll effectivly reuse
// the implicit binder around the witness.
types.skip_binder().to_vec()
}
// for `PhantomData<T>`, we pass `T`
ty::Adt(def, substs) if def.is_phantom_data() => substs.types().collect(),
ty::Adt(def, substs) => def.all_fields().map(|f| f.ty(self.tcx(), substs)).collect(),
ty::Opaque(def_id, substs) => {
// We can resolve the `impl Trait` to its concrete type,
// which enforces a DAG between the functions requiring
// the auto trait bounds in question.
vec![self.tcx().type_of(def_id).subst(self.tcx(), substs)]
}
}
}
fn collect_predicates_for_types(
&mut self,
param_env: ty::ParamEnv<'tcx>,
cause: ObligationCause<'tcx>,
recursion_depth: usize,
trait_def_id: DefId,
types: ty::Binder<Vec<Ty<'tcx>>>,
) -> Vec<PredicateObligation<'tcx>> {
// Because the types were potentially derived from
// higher-ranked obligations they may reference late-bound
// regions. For example, `for<'a> Foo<&'a int> : Copy` would
// yield a type like `for<'a> &'a int`. In general, we
// maintain the invariant that we never manipulate bound
// regions, so we have to process these bound regions somehow.
//
// The strategy is to:
//
// 1. Instantiate those regions to placeholder regions (e.g.,
// `for<'a> &'a int` becomes `&0 int`.
// 2. Produce something like `&'0 int : Copy`
// 3. Re-bind the regions back to `for<'a> &'a int : Copy`
types
.skip_binder()
.into_iter()
.flat_map(|ty| {
// binder moved -\
let ty: ty::Binder<Ty<'tcx>> = ty::Binder::bind(ty); // <----/
self.infcx.in_snapshot(|_| {
let (skol_ty, _) = self.infcx
.replace_bound_vars_with_placeholders(&ty);
let Normalized {
value: normalized_ty,
mut obligations,
} = project::normalize_with_depth(
self,
param_env,
cause.clone(),
recursion_depth,
&skol_ty,
);
let skol_obligation = self.tcx().predicate_for_trait_def(
param_env,
cause.clone(),
trait_def_id,
recursion_depth,
normalized_ty,
&[],
);
obligations.push(skol_obligation);
obligations
})
})
.collect()
}
///////////////////////////////////////////////////////////////////////////
// CONFIRMATION
//
// Confirmation unifies the output type parameters of the trait
// with the values found in the obligation, possibly yielding a
// type error. See the [rustc guide] for more details.
//
// [rustc guide]:
// https://rust-lang.github.io/rustc-guide/traits/resolution.html#confirmation
fn confirm_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
candidate: SelectionCandidate<'tcx>,
) -> Result<Selection<'tcx>, SelectionError<'tcx>> {
debug!("confirm_candidate({:?}, {:?})", obligation, candidate);
match candidate {
BuiltinCandidate { has_nested } => {
let data = self.confirm_builtin_candidate(obligation, has_nested);
Ok(VtableBuiltin(data))
}
ParamCandidate(param) => {
let obligations = self.confirm_param_candidate(obligation, param);
Ok(VtableParam(obligations))
}
ImplCandidate(impl_def_id) => Ok(VtableImpl(self.confirm_impl_candidate(
obligation,
impl_def_id,
))),
AutoImplCandidate(trait_def_id) => {
let data = self.confirm_auto_impl_candidate(obligation, trait_def_id);
Ok(VtableAutoImpl(data))
}
ProjectionCandidate => {
self.confirm_projection_candidate(obligation);
Ok(VtableParam(Vec::new()))
}
ClosureCandidate => {
let vtable_closure = self.confirm_closure_candidate(obligation)?;
Ok(VtableClosure(vtable_closure))
}
GeneratorCandidate => {
let vtable_generator = self.confirm_generator_candidate(obligation)?;
Ok(VtableGenerator(vtable_generator))
}
FnPointerCandidate => {
let data = self.confirm_fn_pointer_candidate(obligation)?;
Ok(VtableFnPointer(data))
}
TraitAliasCandidate(alias_def_id) => {
let data = self.confirm_trait_alias_candidate(obligation, alias_def_id);
Ok(VtableTraitAlias(data))
}
ObjectCandidate => {
let data = self.confirm_object_candidate(obligation);
Ok(VtableObject(data))
}
BuiltinObjectCandidate => {
// This indicates something like `(Trait+Send) :
// Send`. In this case, we know that this holds
// because that's what the object type is telling us,
// and there's really no additional obligations to
// prove and no types in particular to unify etc.
Ok(VtableParam(Vec::new()))
}
BuiltinUnsizeCandidate => {
let data = self.confirm_builtin_unsize_candidate(obligation)?;
Ok(VtableBuiltin(data))
}
}
}
fn confirm_projection_candidate(&mut self, obligation: &TraitObligation<'tcx>) {
self.infcx.in_snapshot(|snapshot| {
let result =
self.match_projection_obligation_against_definition_bounds(
obligation,
snapshot,
);
assert!(result);
})
}
fn confirm_param_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
param: ty::PolyTraitRef<'tcx>,
) -> Vec<PredicateObligation<'tcx>> {
debug!("confirm_param_candidate({:?},{:?})", obligation, param);
// During evaluation, we already checked that this
// where-clause trait-ref could be unified with the obligation
// trait-ref. Repeat that unification now without any
// transactional boundary; it should not fail.
match self.match_where_clause_trait_ref(obligation, param.clone()) {
Ok(obligations) => obligations,
Err(()) => {
bug!(
"Where clause `{:?}` was applicable to `{:?}` but now is not",
param,
obligation
);
}
}
}
fn confirm_builtin_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
has_nested: bool,
) -> VtableBuiltinData<PredicateObligation<'tcx>> {
debug!(
"confirm_builtin_candidate({:?}, {:?})",
obligation, has_nested
);
let lang_items = self.tcx().lang_items();
let obligations = if has_nested {
let trait_def = obligation.predicate.def_id();
let conditions = if Some(trait_def) == lang_items.sized_trait() {
self.sized_conditions(obligation)
} else if Some(trait_def) == lang_items.copy_trait() {
self.copy_clone_conditions(obligation)
} else if Some(trait_def) == lang_items.clone_trait() {
self.copy_clone_conditions(obligation)
} else {
bug!("unexpected builtin trait {:?}", trait_def)
};
let nested = match conditions {
BuiltinImplConditions::Where(nested) => nested,
_ => bug!(
"obligation {:?} had matched a builtin impl but now doesn't",
obligation
),
};
let cause = obligation.derived_cause(BuiltinDerivedObligation);
self.collect_predicates_for_types(
obligation.param_env,
cause,
obligation.recursion_depth + 1,
trait_def,
nested,
)
} else {
vec![]
};
debug!("confirm_builtin_candidate: obligations={:?}", obligations);
VtableBuiltinData {
nested: obligations,
}
}
/// This handles the case where a `auto trait Foo` impl is being used.
/// The idea is that the impl applies to `X : Foo` if the following conditions are met:
///
/// 1. For each constituent type `Y` in `X`, `Y : Foo` holds
/// 2. For each where-clause `C` declared on `Foo`, `[Self => X] C` holds.
fn confirm_auto_impl_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
trait_def_id: DefId,
) -> VtableAutoImplData<PredicateObligation<'tcx>> {
debug!(
"confirm_auto_impl_candidate({:?}, {:?})",
obligation, trait_def_id
);
let types = obligation.predicate.map_bound(|inner| {
let self_ty = self.infcx.shallow_resolve(inner.self_ty());
self.constituent_types_for_ty(self_ty)
});
self.vtable_auto_impl(obligation, trait_def_id, types)
}
/// See `confirm_auto_impl_candidate`.
fn vtable_auto_impl(
&mut self,
obligation: &TraitObligation<'tcx>,
trait_def_id: DefId,
nested: ty::Binder<Vec<Ty<'tcx>>>,
) -> VtableAutoImplData<PredicateObligation<'tcx>> {
debug!("vtable_auto_impl: nested={:?}", nested);
let cause = obligation.derived_cause(BuiltinDerivedObligation);
let mut obligations = self.collect_predicates_for_types(
obligation.param_env,
cause,
obligation.recursion_depth + 1,
trait_def_id,
nested,
);
let trait_obligations: Vec<PredicateObligation<'_>> = self.infcx.in_snapshot(|_| {
let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
let (trait_ref, _) = self.infcx
.replace_bound_vars_with_placeholders(&poly_trait_ref);
let cause = obligation.derived_cause(ImplDerivedObligation);
self.impl_or_trait_obligations(
cause,
obligation.recursion_depth + 1,
obligation.param_env,
trait_def_id,
&trait_ref.substs,
)
});
// Adds the predicates from the trait. Note that this contains a `Self: Trait`
// predicate as usual. It won't have any effect since auto traits are coinductive.
obligations.extend(trait_obligations);
debug!("vtable_auto_impl: obligations={:?}", obligations);
VtableAutoImplData {
trait_def_id,
nested: obligations,
}
}
fn confirm_impl_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
impl_def_id: DefId,
) -> VtableImplData<'tcx, PredicateObligation<'tcx>> {
debug!("confirm_impl_candidate({:?},{:?})", obligation, impl_def_id);
// First, create the substitutions by matching the impl again,
// this time not in a probe.
self.infcx.in_snapshot(|snapshot| {
let substs = self.rematch_impl(impl_def_id, obligation, snapshot);
debug!("confirm_impl_candidate: substs={:?}", substs);
let cause = obligation.derived_cause(ImplDerivedObligation);
self.vtable_impl(
impl_def_id,
substs,
cause,
obligation.recursion_depth + 1,
obligation.param_env,
)
})
}
fn vtable_impl(
&mut self,
impl_def_id: DefId,
mut substs: Normalized<'tcx, SubstsRef<'tcx>>,
cause: ObligationCause<'tcx>,
recursion_depth: usize,
param_env: ty::ParamEnv<'tcx>,
) -> VtableImplData<'tcx, PredicateObligation<'tcx>> {
debug!(
"vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={})",
impl_def_id, substs, recursion_depth,
);
let mut impl_obligations = self.impl_or_trait_obligations(
cause,
recursion_depth,
param_env,
impl_def_id,
&substs.value,
);
debug!(
"vtable_impl: impl_def_id={:?} impl_obligations={:?}",
impl_def_id, impl_obligations
);
// Because of RFC447, the impl-trait-ref and obligations
// are sufficient to determine the impl substs, without
// relying on projections in the impl-trait-ref.
//
// e.g., `impl<U: Tr, V: Iterator<Item=U>> Foo<<U as Tr>::T> for V`
impl_obligations.append(&mut substs.obligations);
VtableImplData {
impl_def_id,
substs: substs.value,
nested: impl_obligations,
}
}
fn confirm_object_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
) -> VtableObjectData<'tcx, PredicateObligation<'tcx>> {
debug!("confirm_object_candidate({:?})", obligation);
// FIXME(nmatsakis) skipping binder here seems wrong -- we should
// probably flatten the binder from the obligation and the binder
// from the object. Have to try to make a broken test case that
// results.
let self_ty = self.infcx
.shallow_resolve(*obligation.self_ty().skip_binder());
let poly_trait_ref = match self_ty.sty {
ty::Dynamic(ref data, ..) =>
data.principal().unwrap_or_else(|| {
span_bug!(obligation.cause.span, "object candidate with no principal")
}).with_self_ty(self.tcx(), self_ty),
_ => span_bug!(obligation.cause.span, "object candidate with non-object"),
};
let mut upcast_trait_ref = None;
let mut nested = vec![];
let vtable_base;
{
let tcx = self.tcx();
// We want to find the first supertrait in the list of
// supertraits that we can unify with, and do that
// unification. We know that there is exactly one in the list
// where we can unify because otherwise select would have
// reported an ambiguity. (When we do find a match, also
// record it for later.)
let nonmatching = util::supertraits(tcx, poly_trait_ref).take_while(
|&t| match self.infcx.commit_if_ok(|_| self.match_poly_trait_ref(obligation, t)) {
Ok(obligations) => {
upcast_trait_ref = Some(t);
nested.extend(obligations);
false
}
Err(_) => true,
},
);
// Additionally, for each of the nonmatching predicates that
// we pass over, we sum up the set of number of vtable
// entries, so that we can compute the offset for the selected
// trait.
vtable_base = nonmatching.map(|t| tcx.count_own_vtable_entries(t)).sum();
}
VtableObjectData {
upcast_trait_ref: upcast_trait_ref.unwrap(),
vtable_base,
nested,
}
}
fn confirm_fn_pointer_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
) -> Result<VtableFnPointerData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
debug!("confirm_fn_pointer_candidate({:?})", obligation);
// Okay to skip binder; it is reintroduced below.
let self_ty = self.infcx
.shallow_resolve(*obligation.self_ty().skip_binder());
let sig = self_ty.fn_sig(self.tcx());
let trait_ref = self.tcx()
.closure_trait_ref_and_return_type(
obligation.predicate.def_id(),
self_ty,
sig,
util::TupleArgumentsFlag::Yes,
)
.map_bound(|(trait_ref, _)| trait_ref);
let Normalized {
value: trait_ref,
obligations,
} = project::normalize_with_depth(
self,
obligation.param_env,
obligation.cause.clone(),
obligation.recursion_depth + 1,
&trait_ref,
);
self.confirm_poly_trait_refs(
obligation.cause.clone(),
obligation.param_env,
obligation.predicate.to_poly_trait_ref(),
trait_ref,
)?;
Ok(VtableFnPointerData {
fn_ty: self_ty,
nested: obligations,
})
}
fn confirm_trait_alias_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
alias_def_id: DefId,
) -> VtableTraitAliasData<'tcx, PredicateObligation<'tcx>> {
debug!(
"confirm_trait_alias_candidate({:?}, {:?})",
obligation, alias_def_id
);
self.infcx.in_snapshot(|_| {
let (predicate, _) = self.infcx()
.replace_bound_vars_with_placeholders(&obligation.predicate);
let trait_ref = predicate.trait_ref;
let trait_def_id = trait_ref.def_id;
let substs = trait_ref.substs;
let trait_obligations = self.impl_or_trait_obligations(
obligation.cause.clone(),
obligation.recursion_depth,
obligation.param_env,
trait_def_id,
&substs,
);
debug!(
"confirm_trait_alias_candidate: trait_def_id={:?} trait_obligations={:?}",
trait_def_id, trait_obligations
);
VtableTraitAliasData {
alias_def_id,
substs: substs,
nested: trait_obligations,
}
})
}
fn confirm_generator_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
) -> Result<VtableGeneratorData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
// Okay to skip binder because the substs on generator types never
// touch bound regions, they just capture the in-scope
// type/region parameters.
let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
let (generator_def_id, substs) = match self_ty.sty {
ty::Generator(id, substs, _) => (id, substs),
_ => bug!("closure candidate for non-closure {:?}", obligation),
};
debug!(
"confirm_generator_candidate({:?},{:?},{:?})",
obligation, generator_def_id, substs
);
let trait_ref = self.generator_trait_ref_unnormalized(obligation, generator_def_id, substs);
let Normalized {
value: trait_ref,
mut obligations,
} = normalize_with_depth(
self,
obligation.param_env,
obligation.cause.clone(),
obligation.recursion_depth + 1,
&trait_ref,
);
debug!(
"confirm_generator_candidate(generator_def_id={:?}, \
trait_ref={:?}, obligations={:?})",
generator_def_id, trait_ref, obligations
);
obligations.extend(self.confirm_poly_trait_refs(
obligation.cause.clone(),
obligation.param_env,
obligation.predicate.to_poly_trait_ref(),
trait_ref,
)?);
Ok(VtableGeneratorData {
generator_def_id: generator_def_id,
substs: substs.clone(),
nested: obligations,
})
}
fn confirm_closure_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
) -> Result<VtableClosureData<'tcx, PredicateObligation<'tcx>>, SelectionError<'tcx>> {
debug!("confirm_closure_candidate({:?})", obligation);
let kind = self.tcx()
.lang_items()
.fn_trait_kind(obligation.predicate.def_id())
.unwrap_or_else(|| bug!("closure candidate for non-fn trait {:?}", obligation));
// Okay to skip binder because the substs on closure types never
// touch bound regions, they just capture the in-scope
// type/region parameters.
let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
let (closure_def_id, substs) = match self_ty.sty {
ty::Closure(id, substs) => (id, substs),
_ => bug!("closure candidate for non-closure {:?}", obligation),
};
let trait_ref = self.closure_trait_ref_unnormalized(obligation, closure_def_id, substs);
let Normalized {
value: trait_ref,
mut obligations,
} = normalize_with_depth(
self,
obligation.param_env,
obligation.cause.clone(),
obligation.recursion_depth + 1,
&trait_ref,
);
debug!(
"confirm_closure_candidate(closure_def_id={:?}, trait_ref={:?}, obligations={:?})",
closure_def_id, trait_ref, obligations
);
obligations.extend(self.confirm_poly_trait_refs(
obligation.cause.clone(),
obligation.param_env,
obligation.predicate.to_poly_trait_ref(),
trait_ref,
)?);
// FIXME: chalk
if !self.tcx().sess.opts.debugging_opts.chalk {
obligations.push(Obligation::new(
obligation.cause.clone(),
obligation.param_env,
ty::Predicate::ClosureKind(closure_def_id, substs, kind),
));
}
Ok(VtableClosureData {
closure_def_id,
substs: substs.clone(),
nested: obligations,
})
}
/// In the case of closure types and fn pointers,
/// we currently treat the input type parameters on the trait as
/// outputs. This means that when we have a match we have only
/// considered the self type, so we have to go back and make sure
/// to relate the argument types too. This is kind of wrong, but
/// since we control the full set of impls, also not that wrong,
/// and it DOES yield better error messages (since we don't report
/// errors as if there is no applicable impl, but rather report
/// errors are about mismatched argument types.
///
/// Here is an example. Imagine we have a closure expression
/// and we desugared it so that the type of the expression is
/// `Closure`, and `Closure` expects an int as argument. Then it
/// is "as if" the compiler generated this impl:
///
/// impl Fn(int) for Closure { ... }
///
/// Now imagine our obligation is `Fn(usize) for Closure`. So far
/// we have matched the self type `Closure`. At this point we'll
/// compare the `int` to `usize` and generate an error.
///
/// Note that this checking occurs *after* the impl has selected,
/// because these output type parameters should not affect the
/// selection of the impl. Therefore, if there is a mismatch, we
/// report an error to the user.
fn confirm_poly_trait_refs(
&mut self,
obligation_cause: ObligationCause<'tcx>,
obligation_param_env: ty::ParamEnv<'tcx>,
obligation_trait_ref: ty::PolyTraitRef<'tcx>,
expected_trait_ref: ty::PolyTraitRef<'tcx>,
) -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
let obligation_trait_ref = obligation_trait_ref.clone();
self.infcx
.at(&obligation_cause, obligation_param_env)
.sup(obligation_trait_ref, expected_trait_ref)
.map(|InferOk { obligations, .. }| obligations)
.map_err(|e| OutputTypeParameterMismatch(expected_trait_ref, obligation_trait_ref, e))
}
fn confirm_builtin_unsize_candidate(
&mut self,
obligation: &TraitObligation<'tcx>,
) -> Result<VtableBuiltinData<PredicateObligation<'tcx>>, SelectionError<'tcx>> {
let tcx = self.tcx();
// assemble_candidates_for_unsizing should ensure there are no late bound
// regions here. See the comment there for more details.
let source = self.infcx
.shallow_resolve(obligation.self_ty().no_bound_vars().unwrap());
let target = obligation
.predicate
.skip_binder()
.trait_ref
.substs
.type_at(1);
let target = self.infcx.shallow_resolve(target);
debug!(
"confirm_builtin_unsize_candidate(source={:?}, target={:?})",
source, target
);
let mut nested = vec![];
match (&source.sty, &target.sty) {
// Trait+Kx+'a -> Trait+Ky+'b (upcasts).
(&ty::Dynamic(ref data_a, r_a), &ty::Dynamic(ref data_b, r_b)) => {
// See assemble_candidates_for_unsizing for more info.
let existential_predicates = data_a.map_bound(|data_a| {
let iter =
data_a.principal().map(|x| ty::ExistentialPredicate::Trait(x))
.into_iter().chain(
data_a
.projection_bounds()
.map(|x| ty::ExistentialPredicate::Projection(x)),
)
.chain(
data_b
.auto_traits()
.map(ty::ExistentialPredicate::AutoTrait),
);
tcx.mk_existential_predicates(iter)
});
let source_trait = tcx.mk_dynamic(existential_predicates, r_b);
// Require that the traits involved in this upcast are **equal**;
// only the **lifetime bound** is changed.
//
// FIXME: This condition is arguably too strong -- it
// would suffice for the source trait to be a
// *subtype* of the target trait. In particular
// changing from something like `for<'a, 'b> Foo<'a,
// 'b>` to `for<'a> Foo<'a, 'a>` should be
// permitted. And, indeed, in the in commit
// 904a0bde93f0348f69914ee90b1f8b6e4e0d7cbc, this
// condition was loosened. However, when the leak check was added
// back, using subtype here actually guies the coercion code in
// such a way that it accepts `old-lub-glb-object.rs`. This is probably
// a good thing, but I've modified this to `.eq` because I want
// to continue rejecting that test (as we have done for quite some time)
// before we are firmly comfortable with what our behavior
// should be there. -nikomatsakis
let InferOk { obligations, .. } = self.infcx
.at(&obligation.cause, obligation.param_env)
.eq(target, source_trait) // FIXME -- see below
.map_err(|_| Unimplemented)?;
nested.extend(obligations);
// Register one obligation for 'a: 'b.
let cause = ObligationCause::new(
obligation.cause.span,
obligation.cause.body_id,
ObjectCastObligation(target),
);
let outlives = ty::OutlivesPredicate(r_a, r_b);
nested.push(Obligation::with_depth(
cause,
obligation.recursion_depth + 1,
obligation.param_env,
ty::Binder::bind(outlives).to_predicate(),
));
}
// T -> Trait.
(_, &ty::Dynamic(ref data, r)) => {
let mut object_dids = data.auto_traits()
.chain(data.principal_def_id());
if let Some(did) = object_dids.find(|did| !tcx.is_object_safe(*did)) {
return Err(TraitNotObjectSafe(did));
}
let cause = ObligationCause::new(
obligation.cause.span,
obligation.cause.body_id,
ObjectCastObligation(target),
);
let predicate_to_obligation = |predicate| {
Obligation::with_depth(
cause.clone(),
obligation.recursion_depth + 1,
obligation.param_env,
predicate,
)
};
// Create obligations:
// - Casting T to Trait
// - For all the various builtin bounds attached to the object cast. (In other
// words, if the object type is Foo+Send, this would create an obligation for the
// Send check.)
// - Projection predicates
nested.extend(
data.iter()
.map(|d| predicate_to_obligation(d.with_self_ty(tcx, source))),
);
// We can only make objects from sized types.
let tr = ty::TraitRef {
def_id: tcx.require_lang_item(lang_items::SizedTraitLangItem),
substs: tcx.mk_substs_trait(source, &[]),
};
nested.push(predicate_to_obligation(tr.to_predicate()));
// If the type is `Foo+'a`, ensures that the type
// being cast to `Foo+'a` outlives `'a`:
let outlives = ty::OutlivesPredicate(source, r);
nested.push(predicate_to_obligation(
ty::Binder::dummy(outlives).to_predicate(),
));
}
// [T; n] -> [T].
(&ty::Array(a, _), &ty::Slice(b)) => {
let InferOk { obligations, .. } = self.infcx
.at(&obligation.cause, obligation.param_env)
.eq(b, a)
.map_err(|_| Unimplemented)?;
nested.extend(obligations);
}
// Struct<T> -> Struct<U>.
(&ty::Adt(def, substs_a), &ty::Adt(_, substs_b)) => {
let fields = def.all_fields()
.map(|f| tcx.type_of(f.did))
.collect::<Vec<_>>();
// The last field of the structure has to exist and contain type parameters.
let field = if let Some(&field) = fields.last() {
field
} else {
return Err(Unimplemented);
};
let mut ty_params = GrowableBitSet::new_empty();
let mut found = false;
for ty in field.walk() {
if let ty::Param(p) = ty.sty {
ty_params.insert(p.index as usize);
found = true;
}
}
if !found {
return Err(Unimplemented);
}
// Replace type parameters used in unsizing with
// Error and ensure they do not affect any other fields.
// This could be checked after type collection for any struct
// with a potentially unsized trailing field.
let params = substs_a.iter().enumerate().map(|(i, &k)| {
if ty_params.contains(i) {
tcx.types.err.into()
} else {
k
}
});
let substs = tcx.mk_substs(params);
for &ty in fields.split_last().unwrap().1 {
if ty.subst(tcx, substs).references_error() {
return Err(Unimplemented);
}
}
// Extract Field<T> and Field<U> from Struct<T> and Struct<U>.
let inner_source = field.subst(tcx, substs_a);
let inner_target = field.subst(tcx, substs_b);
// Check that the source struct with the target's
// unsized parameters is equal to the target.
let params = substs_a.iter().enumerate().map(|(i, &k)| {
if ty_params.contains(i) {
substs_b.type_at(i).into()
} else {
k
}
});
let new_struct = tcx.mk_adt(def, tcx.mk_substs(params));
let InferOk { obligations, .. } = self.infcx
.at(&obligation.cause, obligation.param_env)
.eq(target, new_struct)
.map_err(|_| Unimplemented)?;
nested.extend(obligations);
// Construct the nested Field<T>: Unsize<Field<U>> predicate.
nested.push(tcx.predicate_for_trait_def(
obligation.param_env,
obligation.cause.clone(),
obligation.predicate.def_id(),
obligation.recursion_depth + 1,
inner_source,
&[inner_target.into()],
));
}
// (.., T) -> (.., U).
(&ty::Tuple(tys_a), &ty::Tuple(tys_b)) => {
assert_eq!(tys_a.len(), tys_b.len());
// The last field of the tuple has to exist.
let (&a_last, a_mid) = if let Some(x) = tys_a.split_last() {
x
} else {
return Err(Unimplemented);
};
let &b_last = tys_b.last().unwrap();
// Check that the source tuple with the target's
// last element is equal to the target.
let new_tuple = tcx.mk_tup(
a_mid.iter().map(|k| k.expect_ty()).chain(iter::once(b_last.expect_ty())),
);
let InferOk { obligations, .. } = self.infcx
.at(&obligation.cause, obligation.param_env)
.eq(target, new_tuple)
.map_err(|_| Unimplemented)?;
nested.extend(obligations);
// Construct the nested T: Unsize<U> predicate.
nested.push(tcx.predicate_for_trait_def(
obligation.param_env,
obligation.cause.clone(),
obligation.predicate.def_id(),
obligation.recursion_depth + 1,
a_last.expect_ty(),
&[b_last.into()],
));
}
_ => bug!(),
};
Ok(VtableBuiltinData { nested })
}
///////////////////////////////////////////////////////////////////////////
// Matching
//
// Matching is a common path used for both evaluation and
// confirmation. It basically unifies types that appear in impls
// and traits. This does affect the surrounding environment;
// therefore, when used during evaluation, match routines must be
// run inside of a `probe()` so that their side-effects are
// contained.
fn rematch_impl(
&mut self,
impl_def_id: DefId,
obligation: &TraitObligation<'tcx>,
snapshot: &CombinedSnapshot<'_, 'tcx>,
) -> Normalized<'tcx, SubstsRef<'tcx>> {
match self.match_impl(impl_def_id, obligation, snapshot) {
Ok(substs) => substs,
Err(()) => {
bug!(
"Impl {:?} was matchable against {:?} but now is not",
impl_def_id,
obligation
);
}
}
}
fn match_impl(
&mut self,
impl_def_id: DefId,
obligation: &TraitObligation<'tcx>,
snapshot: &CombinedSnapshot<'_, 'tcx>,
) -> Result<Normalized<'tcx, SubstsRef<'tcx>>, ()> {
let impl_trait_ref = self.tcx().impl_trait_ref(impl_def_id).unwrap();
// Before we create the substitutions and everything, first
// consider a "quick reject". This avoids creating more types
// and so forth that we need to.
if self.