// option. This file may not be copied, modified, or distributed
// except according to those terms.
-//! See `README.md` for high-level documentation
+//! See [rustc guide] for more info on how this works.
+//!
+//! [rustc guide]: https://rust-lang-nursery.github.io/rustc-guide/trait-resolution.html#selection
-pub use self::MethodMatchResult::*;
-pub use self::MethodMatchedData::*;
use self::SelectionCandidate::*;
use self::EvaluationResult::*;
-use super::coherence;
+use super::coherence::{self, Conflict};
use super::DerivedObligationCause;
+use super::{IntercrateMode, TraitQueryMode};
use super::project;
-use super::project::{normalize_with_depth, Normalized};
+use super::project::{normalize_with_depth, Normalized, ProjectionCacheKey};
use super::{PredicateObligation, TraitObligation, ObligationCause};
use super::{ObligationCauseCode, BuiltinDerivedObligation, ImplDerivedObligation};
-use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch};
+use super::{SelectionError, Unimplemented, OutputTypeParameterMismatch, Overflow};
use super::{ObjectCastObligation, Obligation};
-use super::Reveal;
use super::TraitNotObjectSafe;
use super::Selection;
use super::SelectionResult;
-use super::{VtableBuiltin, VtableImpl, VtableParam, VtableClosure,
- VtableFnPointer, VtableObject, VtableDefaultImpl};
-use super::{VtableImplData, VtableObjectData, VtableBuiltinData,
- VtableClosureData, VtableDefaultImplData, VtableFnPointerData};
+use super::{VtableBuiltin, VtableImpl, VtableParam, VtableClosure, VtableGenerator,
+ VtableFnPointer, VtableObject, VtableAutoImpl};
+use super::{VtableImplData, VtableObjectData, VtableBuiltinData, VtableGeneratorData,
+ VtableClosureData, VtableAutoImplData, VtableFnPointerData};
use super::util;
+use dep_graph::{DepNodeIndex, DepKind};
use hir::def_id::DefId;
use infer;
-use infer::{InferCtxt, InferOk, TypeFreshener, TypeOrigin};
+use infer::{InferCtxt, InferOk, TypeFreshener};
use ty::subst::{Kind, Subst, Substs};
use ty::{self, ToPredicate, ToPolyTraitRef, Ty, TyCtxt, TypeFoldable};
-use traits;
use ty::fast_reject;
use ty::relate::TypeRelation;
+use middle::lang_items;
+use mir::interpret::{GlobalId};
use rustc_data_structures::bitvec::BitVector;
-use rustc_data_structures::snapshot_vec::{SnapshotVecDelegate, SnapshotVec};
+use std::iter;
use std::cell::RefCell;
+use std::cmp;
use std::fmt;
-use std::marker::PhantomData;
use std::mem;
use std::rc::Rc;
-use syntax::abi::Abi;
+use rustc_target::spec::abi::Abi;
use hir;
-use util::nodemap::FnvHashMap;
+use util::nodemap::{FxHashMap, FxHashSet};
-struct InferredObligationsSnapshotVecDelegate<'tcx> {
- phantom: PhantomData<&'tcx i32>,
-}
-impl<'tcx> SnapshotVecDelegate for InferredObligationsSnapshotVecDelegate<'tcx> {
- type Value = PredicateObligation<'tcx>;
- type Undo = ();
- fn reverse(_: &mut Vec<Self::Value>, _: Self::Undo) {}
-}
pub struct SelectionContext<'cx, 'gcx: 'cx+'tcx, 'tcx: 'cx> {
infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
/// 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: bool,
+ 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,
- inferred_obligations: SnapshotVec<InferredObligationsSnapshotVecDelegate<'tcx>>,
+ /// 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<'a, 'tcx>(&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 { "".to_string() };
+ 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 { "".to_string() };
+ 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.
#[derive(Clone)]
pub struct SelectionCache<'tcx> {
- hashmap: RefCell<FnvHashMap<ty::TraitRef<'tcx>,
- SelectionResult<'tcx, SelectionCandidate<'tcx>>>>,
-}
-
-pub enum MethodMatchResult {
- MethodMatched(MethodMatchedData),
- MethodAmbiguous(/* list of impls that could apply */ Vec<DefId>),
- MethodDidNotMatch,
-}
-
-#[derive(Copy, Clone, Debug)]
-pub enum MethodMatchedData {
- // In the case of a precise match, we don't really need to store
- // how the match was found. So don't.
- PreciseMethodMatch,
-
- // In the case of a coercion, we need to know the precise impl so
- // that we can determine the type to which things were coerced.
- CoerciveMethodMatch(/* impl we matched */ DefId)
+ hashmap: RefCell<FxHashMap<ty::TraitRef<'tcx>,
+ WithDepNode<SelectionResult<'tcx, SelectionCandidate<'tcx>>>>>,
}
/// The selection process begins by considering all impls, where
BuiltinCandidate { has_nested: bool },
ParamCandidate(ty::PolyTraitRef<'tcx>),
ImplCandidate(DefId),
- DefaultImplCandidate(DefId),
- DefaultImplObjectCandidate(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. The ty::ClosureKind informs the
- /// confirmation step what ClosureKind obligation to emit.
- ClosureCandidate(/* closure */ DefId, ty::ClosureSubsts<'tcx>, ty::ClosureKind),
+ /// 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`)
Some(match *self {
BuiltinCandidate { has_nested } => {
BuiltinCandidate {
- has_nested: has_nested
+ has_nested,
}
}
ImplCandidate(def_id) => ImplCandidate(def_id),
- DefaultImplCandidate(def_id) => DefaultImplCandidate(def_id),
- DefaultImplObjectCandidate(def_id) => {
- DefaultImplObjectCandidate(def_id)
- }
+ AutoImplCandidate(def_id) => AutoImplCandidate(def_id),
ProjectionCandidate => ProjectionCandidate,
FnPointerCandidate => FnPointerCandidate,
ObjectCandidate => ObjectCandidate,
BuiltinObjectCandidate => BuiltinObjectCandidate,
BuiltinUnsizeCandidate => BuiltinUnsizeCandidate,
+ ClosureCandidate => ClosureCandidate,
+ GeneratorCandidate => GeneratorCandidate,
ParamCandidate(ref trait_ref) => {
return tcx.lift(trait_ref).map(ParamCandidate);
}
- ClosureCandidate(def_id, ref substs, kind) => {
- return tcx.lift(substs).map(|substs| {
- ClosureCandidate(def_id, substs, kind)
- });
- }
})
}
}
/// The result of trait evaluation. The order is important
/// here as the evaluation of a list is the maximum of the
/// evaluations.
-enum EvaluationResult {
+///
+/// The evaluation results are ordered:
+/// - `EvaluatedToOk` 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 no-ops 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 failed because of recursion - treated as ambiguous
- EvaluatedToUnknown,
- /// Evaluation is known to be ambiguous
+ /// 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 {
+ pub fn may_apply(self) -> bool {
+ match self {
+ EvaluatedToOk |
+ EvaluatedToAmbig |
+ EvaluatedToUnknown => true,
+
+ EvaluatedToErr |
+ EvaluatedToRecur => false
+ }
+ }
+
+ fn is_stack_dependent(self) -> bool {
+ match self {
+ EvaluatedToUnknown |
+ EvaluatedToRecur => true,
+
+ EvaluatedToOk |
+ EvaluatedToAmbig |
+ EvaluatedToErr => false,
+ }
+ }
+}
+
+impl_stable_hash_for!(enum self::EvaluationResult {
+ EvaluatedToOk,
+ 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)]
pub struct EvaluationCache<'tcx> {
- hashmap: RefCell<FnvHashMap<ty::PolyTraitRef<'tcx>, EvaluationResult>>
+ hashmap: RefCell<FxHashMap<ty::PolyTraitRef<'tcx>, WithDepNode<EvaluationResult>>>
}
impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
pub fn new(infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>) -> SelectionContext<'cx, 'gcx, 'tcx> {
SelectionContext {
- infcx: infcx,
+ 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, 'gcx, 'tcx>,
+ mode: IntercrateMode) -> SelectionContext<'cx, 'gcx, 'tcx> {
+ debug!("intercrate({:?})", mode);
+ SelectionContext {
+ infcx,
freshener: infcx.freshener(),
- intercrate: false,
- inferred_obligations: SnapshotVec::new(),
+ intercrate: Some(mode),
+ intercrate_ambiguity_causes: None,
+ allow_negative_impls: false,
+ query_mode: TraitQueryMode::Standard,
}
}
- pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>) -> SelectionContext<'cx, 'gcx, 'tcx> {
+ pub fn with_negative(infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
+ allow_negative_impls: bool) -> SelectionContext<'cx, 'gcx, 'tcx> {
+ debug!("with_negative({:?})", allow_negative_impls);
SelectionContext {
- infcx: infcx,
+ infcx,
freshener: infcx.freshener(),
- intercrate: true,
- inferred_obligations: SnapshotVec::new(),
+ intercrate: None,
+ intercrate_ambiguity_causes: None,
+ allow_negative_impls,
+ query_mode: TraitQueryMode::Standard,
}
}
+ pub fn with_query_mode(infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
+ query_mode: TraitQueryMode) -> SelectionContext<'cx, 'gcx, '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, 'gcx, 'tcx> {
self.infcx
}
self.infcx.tcx
}
- pub fn param_env(&self) -> &'cx ty::ParameterEnvironment<'gcx> {
- self.infcx.param_env()
- }
-
pub fn closure_typer(&self) -> &'cx InferCtxt<'cx, 'gcx, 'tcx> {
self.infcx
}
- pub fn projection_mode(&self) -> Reveal {
- self.infcx.projection_mode()
- }
-
/// Wraps the inference context's in_snapshot s.t. snapshot handling is only from the selection
/// context's self.
fn in_snapshot<R, F>(&mut self, f: F) -> R
- where F: FnOnce(&mut Self, &infer::CombinedSnapshot) -> R
+ where F: FnOnce(&mut Self, &infer::CombinedSnapshot<'cx, 'tcx>) -> R
{
- // The irrefutable nature of the operation means we don't need to snapshot the
- // inferred_obligations vector.
self.infcx.in_snapshot(|snapshot| f(self, snapshot))
}
/// Wraps a probe s.t. obligations collected during it are ignored and old obligations are
/// retained.
fn probe<R, F>(&mut self, f: F) -> R
- where F: FnOnce(&mut Self, &infer::CombinedSnapshot) -> R
+ where F: FnOnce(&mut Self, &infer::CombinedSnapshot<'cx, 'tcx>) -> R
{
- let inferred_obligations_snapshot = self.inferred_obligations.start_snapshot();
- let result = self.infcx.probe(|snapshot| f(self, snapshot));
- self.inferred_obligations.rollback_to(inferred_obligations_snapshot);
- result
+ self.infcx.probe(|snapshot| f(self, snapshot))
}
/// Wraps a commit_if_ok s.t. obligations collected during it are not returned in selection if
fn commit_if_ok<T, E, F>(&mut self, f: F) -> Result<T, E> where
F: FnOnce(&mut Self, &infer::CombinedSnapshot) -> Result<T, E>
{
- let inferred_obligations_snapshot = self.inferred_obligations.start_snapshot();
- match self.infcx.commit_if_ok(|snapshot| f(self, snapshot)) {
- Ok(ok) => {
- self.inferred_obligations.commit(inferred_obligations_snapshot);
- Ok(ok)
- },
- Err(err) => {
- self.inferred_obligations.rollback_to(inferred_obligations_snapshot);
- Err(err)
- }
- }
+ self.infcx.commit_if_ok(|snapshot| f(self, snapshot))
}
debug!("select({:?})", obligation);
assert!(!obligation.predicate.has_escaping_regions());
- let dep_node = obligation.predicate.dep_node();
- let _task = self.tcx().dep_graph.in_task(dep_node);
-
let stack = self.push_stack(TraitObligationStackList::empty(), obligation);
- match self.candidate_from_obligation(&stack)? {
- None => Ok(None),
- Some(candidate) => {
- let mut candidate = self.confirm_candidate(obligation, candidate)?;
- // FIXME(#32730) remove this assertion once inferred obligations are propagated
- // from inference
- assert!(self.inferred_obligations.len() == 0);
- let inferred_obligations = (*self.inferred_obligations).into_iter().cloned();
- candidate.nested_obligations_mut().extend(inferred_obligations);
- Ok(Some(candidate))
+
+ 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);
+ return Err(SelectionError::Overflow);
},
+ Err(e) => Err(e),
+ Ok(candidate) => Ok(Some(candidate))
}
}
// we can be sure it does not.
/// Evaluates whether the obligation `obligation` can be satisfied (by any means).
- pub fn evaluate_obligation(&mut self,
- obligation: &PredicateObligation<'tcx>)
- -> bool
+ pub fn predicate_may_hold_fatal(&mut self,
+ obligation: &PredicateObligation<'tcx>)
+ -> bool
{
- debug!("evaluate_obligation({:?})",
+ debug!("predicate_may_hold_fatal({:?})",
obligation);
- self.probe(|this, _| {
- this.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation)
- .may_apply()
- })
+ // 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_obligation_recursively(obligation)
+ .expect("Overflow should be caught earlier in standard query mode")
+ .may_apply()
}
- /// Evaluates whether the obligation `obligation` can be satisfied,
- /// and returns `false` if not certain. However, this is not entirely
- /// accurate if inference variables are involved.
- pub fn evaluate_obligation_conservatively(&mut self,
- obligation: &PredicateObligation<'tcx>)
- -> bool
+ /// Evaluates whether the obligation `obligation` can be satisfied and returns
+ /// an `EvaluationResult`.
+ pub fn evaluate_obligation_recursively(&mut self,
+ obligation: &PredicateObligation<'tcx>)
+ -> Result<EvaluationResult, OverflowError>
{
- debug!("evaluate_obligation_conservatively({:?})",
- obligation);
-
self.probe(|this, _| {
this.evaluate_predicate_recursively(TraitObligationStackList::empty(), obligation)
- == EvaluatedToOk
})
}
fn evaluate_predicates_recursively<'a,'o,I>(&mut self,
stack: TraitObligationStackList<'o, 'tcx>,
predicates: I)
- -> EvaluationResult
- where I : Iterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a
+ -> Result<EvaluationResult, OverflowError>
+ where I : IntoIterator<Item=&'a PredicateObligation<'tcx>>, 'tcx:'a
{
let mut result = EvaluatedToOk;
for obligation in predicates {
- let eval = self.evaluate_predicate_recursively(stack, obligation);
+ let eval = self.evaluate_predicate_recursively(stack, obligation)?;
debug!("evaluate_predicate_recursively({:?}) = {:?}",
obligation, eval);
- match eval {
- EvaluatedToErr => { return EvaluatedToErr; }
- EvaluatedToAmbig => { result = EvaluatedToAmbig; }
- EvaluatedToUnknown => {
- if result < EvaluatedToUnknown {
- result = EvaluatedToUnknown;
- }
- }
- EvaluatedToOk => { }
+ 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);
}
}
- result
+ Ok(result)
}
fn evaluate_predicate_recursively<'o>(&mut self,
previous_stack: TraitObligationStackList<'o, 'tcx>,
obligation: &PredicateObligation<'tcx>)
- -> EvaluationResult
+ -> Result<EvaluationResult, OverflowError>
{
debug!("evaluate_predicate_recursively({:?})",
obligation);
- // Check the cache from the tcx of predicates that we know
- // have been proven elsewhere. This cache only contains
- // predicates that are global in scope and hence unaffected by
- // the current environment.
- if self.tcx().fulfilled_predicates.borrow().check_duplicate(&obligation.predicate) {
- return EvaluatedToOk;
- }
-
match obligation.predicate {
ty::Predicate::Trait(ref t) => {
assert!(!t.has_escaping_regions());
let obligation = obligation.with(t.clone());
- self.evaluate_obligation_recursively(previous_stack, &obligation)
+ self.evaluate_trait_predicate_recursively(previous_stack, obligation)
}
- ty::Predicate::Equate(ref p) => {
+ ty::Predicate::Subtype(ref p) => {
// does this code ever run?
- match self.infcx.equality_predicate(obligation.cause.span, p) {
- Ok(InferOk { obligations, .. }) => {
- self.inferred_obligations.extend(obligations);
- EvaluatedToOk
+ match self.infcx.subtype_predicate(&obligation.cause, obligation.param_env, p) {
+ Some(Ok(InferOk { obligations, .. })) => {
+ self.evaluate_predicates_recursively(previous_stack, &obligations)
},
- Err(_) => EvaluatedToErr
+ Some(Err(_)) => Ok(EvaluatedToErr),
+ None => Ok(EvaluatedToAmbig),
}
}
ty::Predicate::WellFormed(ty) => {
- match ty::wf::obligations(self.infcx, obligation.cause.body_id,
+ match ty::wf::obligations(self.infcx,
+ obligation.param_env,
+ obligation.cause.body_id,
ty, obligation.cause.span) {
Some(obligations) =>
self.evaluate_predicates_recursively(previous_stack, obligations.iter()),
None =>
- EvaluatedToAmbig,
+ Ok(EvaluatedToAmbig),
}
}
ty::Predicate::TypeOutlives(..) | ty::Predicate::RegionOutlives(..) => {
// we do not consider region relationships when
// evaluating trait matches
- EvaluatedToOk
+ Ok(EvaluatedToOk)
}
ty::Predicate::ObjectSafe(trait_def_id) => {
if self.tcx().is_object_safe(trait_def_id) {
- EvaluatedToOk
+ Ok(EvaluatedToOk)
} else {
- EvaluatedToErr
+ Ok(EvaluatedToErr)
}
}
let project_obligation = obligation.with(data.clone());
match project::poly_project_and_unify_type(self, &project_obligation) {
Ok(Some(subobligations)) => {
- self.evaluate_predicates_recursively(previous_stack,
- subobligations.iter())
+ let result = self.evaluate_predicates_recursively(previous_stack,
+ subobligations.iter());
+ if let Some(key) =
+ ProjectionCacheKey::from_poly_projection_predicate(self, data)
+ {
+ self.infcx.projection_cache.borrow_mut().complete(key);
+ }
+ result
}
Ok(None) => {
- EvaluatedToAmbig
+ Ok(EvaluatedToAmbig)
}
Err(_) => {
- EvaluatedToErr
+ Ok(EvaluatedToErr)
}
}
}
- ty::Predicate::ClosureKind(closure_def_id, kind) => {
- match self.infcx.closure_kind(closure_def_id) {
+ 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) {
- EvaluatedToOk
+ Ok(EvaluatedToOk)
} else {
- EvaluatedToErr
+ Ok(EvaluatedToErr)
}
}
None => {
- EvaluatedToAmbig
+ Ok(EvaluatedToAmbig)
+ }
+ }
+ }
+
+ ty::Predicate::ConstEvaluatable(def_id, substs) => {
+ let tcx = self.tcx();
+ match tcx.lift_to_global(&(obligation.param_env, substs)) {
+ Some((param_env, substs)) => {
+ let instance = ty::Instance::resolve(
+ tcx.global_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)
+ }
+ }
+ None => {
+ // Inference variables still left in param_env or substs.
+ Ok(EvaluatedToAmbig)
}
}
}
}
}
- fn evaluate_obligation_recursively<'o>(&mut self,
- previous_stack: TraitObligationStackList<'o, 'tcx>,
- obligation: &TraitObligation<'tcx>)
- -> EvaluationResult
+ fn evaluate_trait_predicate_recursively<'o>(&mut self,
+ previous_stack: TraitObligationStackList<'o, 'tcx>,
+ mut obligation: TraitObligation<'tcx>)
+ -> Result<EvaluationResult, OverflowError>
{
- debug!("evaluate_obligation_recursively({:?})",
+ debug!("evaluate_trait_predicate_recursively({:?})",
obligation);
- let stack = self.push_stack(previous_stack, obligation);
+ if !self.intercrate.is_some() && obligation.is_global() {
+ // If a param env is consistent, 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. (If the current param env is inconsistent, we don't care what happens).
+ 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(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 result;
+ return Ok(result);
}
- let result = self.evaluate_stack(&stack);
+ let (result, dep_node) = self.in_task(|this| this.evaluate_stack(&stack));
+ let result = result?;
debug!("CACHE MISS: EVAL({:?})={:?}",
fresh_trait_ref,
result);
- self.insert_evaluation_cache(fresh_trait_ref, result);
+ self.insert_evaluation_cache(obligation.param_env, fresh_trait_ref, dep_node, result);
- result
+ Ok(result)
}
fn evaluate_stack<'o>(&mut self,
stack: &TraitObligationStack<'o, 'tcx>)
- -> EvaluationResult
+ -> 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 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.input_types().any(|ty| ty.is_fresh());
- if unbound_input_types && self.intercrate {
+ 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);
- return EvaluatedToAmbig;
+ // 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| self.match_fresh_trait_refs(&stack.fresh_trait_ref,
- &prev.fresh_trait_ref))
+ |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 EvaluatedToUnknown;
+ return Ok(EvaluatedToUnknown);
}
// If there is any previous entry on the stack that precisely
// affect the inferencer state and (b) that if we see two
// skolemized types with the same index, they refer to the
// same unbound type variable.
- if
+ if let Some(rec_index) =
stack.iter()
.skip(1) // skip top-most frame
- .any(|prev| stack.fresh_trait_ref == prev.fresh_trait_ref)
+ .position(|prev| stack.obligation.param_env == prev.obligation.param_env &&
+ stack.fresh_trait_ref == prev.fresh_trait_ref)
{
debug!("evaluate_stack({:?}) --> recursive",
stack.fresh_trait_ref);
- return EvaluatedToOk;
+ let cycle = stack.iter().skip(1).take(rec_index+1);
+ 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);
+ return Ok(EvaluatedToOk);
+ } else {
+ debug!("evaluate_stack({:?}) --> recursive, inductive",
+ stack.fresh_trait_ref);
+ return Ok(EvaluatedToRecur);
+ }
}
match self.candidate_from_obligation(stack) {
Ok(Some(c)) => self.evaluate_candidate(stack, &c),
- Ok(None) => EvaluatedToAmbig,
- Err(..) => EvaluatedToErr
+ 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, and
+ /// - it also appears in the backtrace at some position `X`; and,
+ /// - 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 true if `candidate` remains viable after this further
/// scrutiny.
fn evaluate_candidate<'o>(&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
candidate: &SelectionCandidate<'tcx>)
- -> EvaluationResult
+ -> Result<EvaluationResult, OverflowError>
{
debug!("evaluate_candidate: depth={} candidate={:?}",
stack.obligation.recursion_depth, candidate);
stack.list(),
selection.nested_obligations().iter())
}
- Err(..) => EvaluatedToErr
+ Err(..) => Ok(EvaluatedToErr)
}
- });
+ })?;
debug!("evaluate_candidate: depth={} result={:?}",
stack.obligation.recursion_depth, result);
- result
+ Ok(result)
}
- fn check_evaluation_cache(&self, trait_ref: ty::PolyTraitRef<'tcx>)
+ fn check_evaluation_cache(&self,
+ param_env: ty::ParamEnv<'tcx>,
+ trait_ref: ty::PolyTraitRef<'tcx>)
-> Option<EvaluationResult>
{
- if self.can_use_global_caches() {
- let cache = self.tcx().evaluation_cache.hashmap.borrow();
+ 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.clone());
+ return Some(cached.get(tcx));
}
}
- self.infcx.evaluation_cache.hashmap.borrow().get(&trait_ref).cloned()
+ 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 EvaluatedToUnknown, and closure signatures
- // being yet uninferred can create "spurious" EvaluatedToAmbig
- // and EvaluatedToOk.
- if result == EvaluatedToUnknown ||
- ((result == EvaluatedToAmbig || result == EvaluatedToOk)
- && trait_ref.has_closure_types())
- {
+ // 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() {
+ if self.can_use_global_caches(param_env) {
let mut cache = self.tcx().evaluation_cache.hashmap.borrow_mut();
if let Some(trait_ref) = self.tcx().lift_to_global(&trait_ref) {
- cache.insert(trait_ref, result);
+ debug!(
+ "insert_evaluation_cache(trait_ref={:?}, candidate={:?}) global",
+ trait_ref,
+ result,
+ );
+ cache.insert(trait_ref, WithDepNode::new(dep_node, result));
return;
}
}
- self.infcx.evaluation_cache.hashmap.borrow_mut().insert(trait_ref, result);
+ 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));
}
///////////////////////////////////////////////////////////////////////////
//
// The selection process begins by examining all in-scope impls,
// caller obligations, and so forth and assembling a list of
- // candidates. See `README.md` and the `Candidate` type for more
- // details.
+ // candidates. See [rustc guide] for more details.
+ //
+ // [rustc guide]:
+ // https://rust-lang-nursery.github.io/rustc-guide/trait-resolution.html#candidate-assembly
fn candidate_from_obligation<'o>(&mut self,
stack: &TraitObligationStack<'o, 'tcx>)
{
// Watch out for overflow. This intentionally bypasses (and does
// not update) the cache.
- let recursion_limit = self.infcx.tcx.sess.recursion_limit.get();
+ let recursion_limit = *self.infcx.tcx.sess.recursion_limit.get();
if stack.obligation.recursion_depth >= recursion_limit {
- self.infcx().report_overflow_error(&stack.obligation, true);
+ match self.query_mode {
+ TraitQueryMode::Standard => {
+ self.infcx().report_overflow_error(&stack.obligation, true);
+ },
+ TraitQueryMode::Canonical => {
+ return Err(Overflow);
+ },
+ }
}
// Check the cache. Note that we skolemize the trait-ref
stack);
assert!(!stack.obligation.predicate.has_escaping_regions());
- match self.check_candidate_cache(&cache_fresh_trait_pred) {
- Some(c) => {
- debug!("CACHE HIT: SELECT({:?})={:?}",
- cache_fresh_trait_pred,
- c);
- return c;
- }
- None => { }
+ 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.
- let candidate = self.candidate_from_obligation_no_cache(stack);
-
- if self.should_update_candidate_cache(&cache_fresh_trait_pred, &candidate) {
- debug!("CACHE MISS: SELECT({:?})={:?}",
- cache_fresh_trait_pred, candidate);
- self.insert_candidate_cache(cache_fresh_trait_pred, candidate.clone());
- }
+ 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.tcx().trait_impl_polarity(def_id) == hir::ImplPolarity::Negative {
+ if !self.allow_negative_impls &&
+ self.tcx().impl_polarity(def_id) == hir::ImplPolarity::Negative {
return Err(Unimplemented)
}
}
return Ok(None);
}
- if !self.is_knowable(stack) {
- debug!("coherence stage: not knowable");
- return Ok(None);
+ match self.is_knowable(stack) {
+ None => {}
+ Some(conflict) => {
+ 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 no_candidates_apply =
+ candidate_set
+ .vec
+ .iter()
+ .map(|c| self.evaluate_candidate(stack, &c))
+ .collect::<Result<Vec<_>, OverflowError>>()?
+ .iter()
+ .all(|r| !r.may_apply());
+ 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)?;
}
// Winnow, but record the exact outcome of evaluation, which
- // is needed for specialization.
- let mut candidates: Vec<_> = candidates.into_iter().filter_map(|c| {
- let eval = self.evaluate_candidate(stack, &c);
- if eval.may_apply() {
- Some(EvaluatedCandidate {
+ // is needed for specialization. Propagate overflow if it occurs.
+ let candidates: Result<Vec<Option<EvaluatedCandidate>>, _> = candidates
+ .into_iter()
+ .map(|c| match self.evaluate_candidate(stack, &c) {
+ Ok(eval) if eval.may_apply() => Ok(Some(EvaluatedCandidate {
candidate: c,
evaluation: eval,
- })
- } else {
- None
- }
- }).collect();
+ })),
+ Ok(_) => Ok(None),
+ Err(OverflowError) => Err(Overflow),
+ })
+ .collect();
+
+ let mut candidates: Vec<EvaluatedCandidate> =
+ candidates?.into_iter().filter_map(|c| c).collect();
// If there are STILL multiple candidate, we can further
// reduce the list by dropping duplicates -- including
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 *STILL* multiple candidates, give up and
- // report ambiguity.
- if candidates.len() > 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
fn is_knowable<'o>(&mut self,
stack: &TraitObligationStack<'o, 'tcx>)
- -> bool
+ -> Option<Conflict>
{
- debug!("is_knowable(intercrate={})", self.intercrate);
+ debug!("is_knowable(intercrate={:?})", self.intercrate);
- if !self.intercrate {
- return true;
+ if !self.intercrate.is_some() {
+ return None;
}
let obligation = &stack.obligation;
// ok 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 trait_ref = predicate.skip_binder().trait_ref;
- coherence::trait_ref_is_knowable(self.tcx(), 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) -> bool {
+ 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
// 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 !self.param_env().caller_bounds.is_empty() {
+ if !param_env.caller_bounds.is_empty() {
return false;
}
// 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 {
+ if self.intercrate.is_some() {
return false;
}
}
fn check_candidate_cache(&mut self,
+ param_env: ty::ParamEnv<'tcx>,
cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>)
-> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>>
{
- let trait_ref = &cache_fresh_trait_pred.0.trait_ref;
- if self.can_use_global_caches() {
- let cache = self.tcx().selection_cache.hashmap.borrow();
+ 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.clone());
+ return Some(cached.get(tcx));
}
}
- self.infcx.selection_cache.hashmap.borrow().get(trait_ref).cloned()
+ self.infcx.selection_cache.hashmap
+ .borrow()
+ .get(trait_ref)
+ .map(|v| v.get(tcx))
}
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 trait_ref = cache_fresh_trait_pred.0.trait_ref;
- if self.can_use_global_caches() {
- let mut cache = self.tcx().selection_cache.hashmap.borrow_mut();
- if let Some(trait_ref) = self.tcx().lift_to_global(&trait_ref) {
- if let Some(candidate) = self.tcx().lift_to_global(&candidate) {
- cache.insert(trait_ref, candidate);
+ let tcx = self.tcx();
+ let trait_ref = cache_fresh_trait_pred.skip_binder().trait_ref;
+ if self.can_use_global_caches(param_env) {
+ let mut cache = tcx.selection_cache.hashmap.borrow_mut();
+ if let Some(trait_ref) = tcx.lift_to_global(&trait_ref) {
+ if let Some(candidate) = tcx.lift_to_global(&candidate) {
+ debug!(
+ "insert_candidate_cache(trait_ref={:?}, candidate={:?}) global",
+ trait_ref,
+ candidate,
+ );
+ cache.insert(trait_ref, WithDepNode::new(dep_node, candidate));
return;
}
}
}
- self.infcx.selection_cache.hashmap.borrow_mut().insert(trait_ref, candidate);
- }
-
- fn should_update_candidate_cache(&mut self,
- cache_fresh_trait_pred: &ty::PolyTraitPredicate<'tcx>,
- candidate: &SelectionResult<'tcx, SelectionCandidate<'tcx>>)
- -> bool
- {
- // In general, it's a good idea to cache results, even
- // ambiguous ones, to save us some trouble later. But we have
- // to be careful not to cache results that could be
- // invalidated later by advances in inference. Normally, this
- // is not an issue, because any inference variables whose
- // types are not yet bound are "freshened" in the cache key,
- // which means that if we later get the same request once that
- // type variable IS bound, we'll have a different cache key.
- // For example, if we have `Vec<_#0t> : Foo`, and `_#0t` is
- // not yet known, we may cache the result as `None`. But if
- // later `_#0t` is bound to `Bar`, then when we freshen we'll
- // have `Vec<Bar> : Foo` as the cache key.
- //
- // HOWEVER, it CAN happen that we get an ambiguity result in
- // one particular case around closures where the cache key
- // would not change. That is when the precise types of the
- // upvars that a closure references have not yet been figured
- // out (i.e., because it is not yet known if they are captured
- // by ref, and if by ref, what kind of ref). In these cases,
- // when matching a builtin bound, we will yield back an
- // ambiguous result. But the *cache key* is just the closure type,
- // it doesn't capture the state of the upvar computation.
- //
- // To avoid this trap, just don't cache ambiguous results if
- // the self-type contains no inference byproducts (that really
- // shouldn't happen in other circumstances anyway, given
- // coherence).
-
- match *candidate {
- Ok(Some(_)) | Err(_) => true,
- Ok(None) => cache_fresh_trait_pred.has_infer_types()
- }
+ 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,
{
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_type_vars_if_possible(&obligation.predicate)
};
if obligation.predicate.skip_binder().self_ty().is_ty_var() {
- // FIXME(#20297): Self is a type variable (e.g. `_: AsRef<str>`).
+ // 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.
//
- // Until this is fixed, take the fast path out - this also improves
+ // 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 });
// Other bounds. Consider both in-scope bounds from fn decl
// and applicable impls. There is a certain set of precedence rules here.
- match self.tcx().lang_items.to_builtin_kind(obligation.predicate.def_id()) {
- Some(ty::BoundCopy) => {
- debug!("obligation self ty is {:?}",
- obligation.predicate.0.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_conditions(obligation);
- self.assemble_builtin_bound_candidates(copy_conditions, &mut candidates)?;
- }
- Some(ty::BoundSized) => {
- // 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)?;
- }
-
- None if self.tcx().lang_items.unsize_trait() ==
- Some(obligation.predicate.def_id()) => {
- self.assemble_candidates_for_unsizing(obligation, &mut candidates);
- }
-
- Some(ty::BoundSend) |
- Some(ty::BoundSync) |
- None => {
- 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);
- }
+ 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)?;
- // Default implementations have lower priority, so we only
+ // 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_default_impls(obligation, &mut candidates)?;
+ self.assemble_candidates_from_auto_impls(obligation, &mut candidates)?;
}
debug!("candidate list size: {}", candidates.vec.len());
Ok(candidates)
{
debug!("assemble_candidates_for_projected_tys({:?})", obligation);
- // FIXME(#20297) -- just examining the self-type is very simplistic
-
// before we go into the whole skolemization thing, just
// quickly check if the self-type is a projection at all.
- match obligation.predicate.0.trait_ref.self_ty().sty {
+ match obligation.predicate.skip_binder().trait_ref.self_ty().sty {
ty::TyProjection(_) | ty::TyAnon(..) => {}
ty::TyInfer(ty::TyVar(_)) => {
span_bug!(obligation.cause.span,
fn match_projection_obligation_against_definition_bounds(
&mut self,
obligation: &TraitObligation<'tcx>,
- snapshot: &infer::CombinedSnapshot)
+ snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
-> bool
{
let poly_trait_predicate =
self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
let (skol_trait_predicate, skol_map) =
- self.infcx().skolemize_late_bound_regions(&poly_trait_predicate, snapshot);
+ self.infcx().skolemize_late_bound_regions(&poly_trait_predicate);
debug!("match_projection_obligation_against_definition_bounds: \
skol_trait_predicate={:?} skol_map={:?}",
skol_trait_predicate,
skol_map);
let (def_id, substs) = match skol_trait_predicate.trait_ref.self_ty().sty {
- ty::TyProjection(ref data) => (data.trait_ref.def_id, data.trait_ref.substs),
+ ty::TyProjection(ref data) =>
+ (data.trait_ref(self.tcx()).def_id, data.substs),
ty::TyAnon(def_id, substs) => (def_id, substs),
_ => {
span_bug!(
def_id={:?}, substs={:?}",
def_id, substs);
- let item_predicates = self.tcx().lookup_predicates(def_id);
- let bounds = item_predicates.instantiate(self.tcx(), 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);
trait_bound: ty::PolyTraitRef<'tcx>,
skol_trait_ref: ty::TraitRef<'tcx>,
skol_map: &infer::SkolemizationMap<'tcx>,
- snapshot: &infer::CombinedSnapshot)
+ snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
-> bool
{
assert!(!skol_trait_ref.has_escaping_regions());
- let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
- match self.infcx.sub_poly_trait_refs(false,
- origin,
- trait_bound.clone(),
- ty::Binder(skol_trait_ref.clone())) {
- Ok(InferOk { obligations, .. }) => {
- self.inferred_obligations.extend(obligations);
- }
- Err(_) => { return false; }
+ if let Err(_) = self.infcx.at(&obligation.cause, obligation.param_env)
+ .sup(ty::Binder::dummy(skol_trait_ref), trait_bound) {
+ return false;
}
self.infcx.leak_check(false, obligation.cause.span, skol_map, snapshot).is_ok()
stack.obligation);
let all_bounds =
- self.param_env().caller_bounds
- .iter()
- .filter_map(|o| o.to_opt_poly_trait_ref());
+ 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(
- |bound| self.evaluate_where_clause(stack, bound.clone()).may_apply());
+ all_bounds.filter(|p| p.def_id() == stack.obligation.predicate.def_id());
- let param_candidates =
- matching_bounds.map(|bound| ParamCandidate(bound));
+ // 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);
fn evaluate_where_clause<'o>(&mut self,
stack: &TraitObligationStack<'o, 'tcx>,
where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
- -> EvaluationResult
+ -> Result<EvaluationResult, OverflowError>
{
self.probe(move |this, _| {
match this.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) {
Ok(obligations) => {
this.evaluate_predicates_recursively(stack.list(), obligations.iter())
}
- Err(()) => EvaluatedToErr
+ 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(());
+ }
+
+ // ok 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::TyGenerator(..) => {
+ debug!("assemble_generator_candidates: self_ty={:?} obligation={:?}",
+ self_ty,
+ obligation);
+
+ candidates.vec.push(GeneratorCandidate);
+ Ok(())
+ }
+ ty::TyInfer(ty::TyVar(_)) => {
+ debug!("assemble_generator_candidates: ambiguous self-type");
+ candidates.ambiguous = true;
+ return Ok(());
+ }
+ _ => { return Ok(()); }
+ }
+ }
+
/// Check for the artificial impl that the compiler will create for an obligation like `X :
/// FnMut<..>` where `X` is a closure type.
///
candidates: &mut SelectionCandidateSet<'tcx>)
-> Result<(),SelectionError<'tcx>>
{
- let kind = match self.tcx().lang_items.fn_trait_kind(obligation.predicate.0.def_id()) {
+ let kind = match self.tcx().lang_items().fn_trait_kind(obligation.predicate.def_id()) {
Some(k) => k,
None => { return Ok(()); }
};
// ok 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 = *obligation.self_ty().skip_binder();
- let (closure_def_id, substs) = match self_ty.sty {
- ty::TyClosure(id, substs) => (id, substs),
+ match obligation.self_ty().skip_binder().sty {
+ ty::TyClosure(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);
+ }
+ };
+ Ok(())
+ }
ty::TyInfer(ty::TyVar(_)) => {
debug!("assemble_unboxed_closure_candidates: ambiguous self-type");
candidates.ambiguous = true;
return Ok(());
}
_ => { return Ok(()); }
- };
-
- debug!("assemble_unboxed_candidates: self_ty={:?} kind={:?} obligation={:?}",
- self_ty,
- kind,
- obligation);
-
- match self.infcx.closure_kind(closure_def_id) {
- Some(closure_kind) => {
- debug!("assemble_unboxed_candidates: closure_kind = {:?}", closure_kind);
- if closure_kind.extends(kind) {
- candidates.vec.push(ClosureCandidate(closure_def_id, substs, kind));
- }
- }
- None => {
- debug!("assemble_unboxed_candidates: closure_kind not yet known");
- candidates.vec.push(ClosureCandidate(closure_def_id, substs, kind));
- }
}
-
- Ok(())
}
/// Implement one of the `Fn()` family for a fn pointer.
-> 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() {
+ if self.tcx().lang_items().fn_trait_kind(obligation.predicate.def_id()).is_none() {
return Ok(());
}
}
// provide an impl, but only for suitable `fn` pointers
- ty::TyFnDef(.., &ty::BareFnTy {
- unsafety: hir::Unsafety::Normal,
- abi: Abi::Rust,
- sig: ty::Binder(ty::FnSig {
- inputs: _,
- output: _,
- variadic: false
- })
- }) |
- ty::TyFnPtr(&ty::BareFnTy {
- unsafety: hir::Unsafety::Normal,
- abi: Abi::Rust,
- sig: ty::Binder(ty::FnSig {
- inputs: _,
- output: _,
- variadic: false
- })
- }) => {
- candidates.vec.push(FnPointerCandidate);
+ ty::TyFnDef(..) | ty::TyFnPtr(_) => {
+ if let ty::FnSig {
+ unsafety: hir::Unsafety::Normal,
+ abi: Abi::Rust,
+ variadic: false,
+ ..
+ } = self_ty.fn_sig(self.tcx()).skip_binder() {
+ candidates.vec.push(FnPointerCandidate);
+ }
}
_ => { }
{
debug!("assemble_candidates_from_impls(obligation={:?})", obligation);
- let def = self.tcx().lookup_trait_def(obligation.predicate.def_id());
-
- def.for_each_relevant_impl(
- self.tcx(),
- obligation.predicate.0.trait_ref.self_ty(),
+ self.tcx().for_each_relevant_impl(
+ obligation.predicate.def_id(),
+ obligation.predicate.skip_binder().trait_ref.self_ty(),
|impl_def_id| {
self.probe(|this, snapshot| { /* [1] */
match this.match_impl(impl_def_id, obligation, snapshot) {
Ok(())
}
- fn assemble_candidates_from_default_impls(&mut self,
+ fn assemble_candidates_from_auto_impls(&mut self,
obligation: &TraitObligation<'tcx>,
candidates: &mut SelectionCandidateSet<'tcx>)
-> Result<(), SelectionError<'tcx>>
{
// OK 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_default_impls(self_ty={:?})", self_ty);
+ debug!("assemble_candidates_from_auto_impls(self_ty={:?})", self_ty);
let def_id = obligation.predicate.def_id();
- if self.tcx().trait_has_default_impl(def_id) {
+ if self.tcx().trait_is_auto(def_id) {
match self_ty.sty {
- ty::TyTrait(..) => {
+ ty::TyDynamic(..) => {
// For object types, we don't know what the closed
- // over types are. For most traits, this means we
- // conservatively say nothing; a candidate may be
- // added by `assemble_candidates_from_object_ty`.
- // However, for the kind of magic reflect trait,
- // we consider it to be implemented even for
- // object types, because it just lets you reflect
- // onto the object type, not into the object's
- // interior.
- if self.tcx().has_attr(def_id, "rustc_reflect_like") {
- candidates.vec.push(DefaultImplObjectCandidate(def_id));
- }
+ // over types are. This means we conservatively
+ // say nothing; a candidate may be added by
+ // `assemble_candidates_from_object_ty`.
+ }
+ ty::TyForeign(..) => {
+ // 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::TyParam(..) |
- ty::TyProjection(..) |
- ty::TyAnon(..) => {
+ ty::TyProjection(..) => {
// 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
// this path.
}
ty::TyInfer(ty::TyVar(_)) => {
- // the defaulted impl might apply, we don't know
+ // the auto impl might apply, we don't know
candidates.ambiguous = true;
}
_ => {
- candidates.vec.push(DefaultImplCandidate(def_id.clone()))
+ candidates.vec.push(AutoImplCandidate(def_id.clone()))
}
}
}
// any LBR.
let self_ty = this.tcx().erase_late_bound_regions(&obligation.self_ty());
let poly_trait_ref = match self_ty.sty {
- ty::TyTrait(ref data) => {
- match this.tcx().lang_items.to_builtin_kind(obligation.predicate.def_id()) {
- Some(bound @ ty::BoundSend) | Some(bound @ ty::BoundSync) => {
- if data.builtin_bounds.contains(&bound) {
- debug!("assemble_candidates_from_object_ty: matched builtin bound, \
- pushing candidate");
- candidates.vec.push(BuiltinObjectCandidate);
- return;
- }
- }
- _ => {}
+ ty::TyDynamic(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;
}
- data.principal.with_self_ty(this.tcx(), self_ty)
+ match data.principal() {
+ Some(p) => p.with_self_ty(this.tcx(), self_ty),
+ None => return,
+ }
}
ty::TyInfer(ty::TyVar(_)) => {
debug!("assemble_candidates_from_object_ty: ambiguous");
// 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 self.tcx().no_late_bound_regions(&obligation.self_ty()) {
+ let source = match obligation.self_ty().no_late_bound_regions() {
Some(t) => t,
None => {
// Don't add any candidates if there are bound regions.
let may_apply = match (&source.sty, &target.sty) {
// Trait+Kx+'a -> Trait+Ky+'b (upcasts).
- (&ty::TyTrait(ref data_a), &ty::TyTrait(ref data_b)) => {
+ (&ty::TyDynamic(ref data_a, ..), &ty::TyDynamic(ref data_b, ..)) => {
// Upcasts permit two things:
//
// 1. Dropping builtin bounds, e.g. `Foo+Send` to `Foo`
//
// We always upcast when we can because of reason
// #2 (region bounds).
- data_a.principal.def_id() == data_a.principal.def_id() &&
- data_a.builtin_bounds.is_superset(&data_b.builtin_bounds)
+ match (data_a.principal(), data_b.principal()) {
+ (Some(a), Some(b)) => a.def_id() == b.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)),
+ _ => false
+ }
}
// T -> Trait.
- (_, &ty::TyTrait(_)) => true,
+ (_, &ty::TyDynamic(..)) => true,
// Ambiguous handling is below T -> Trait, because inference
// variables can still implement Unsize<Trait> and nested
def_id_a == def_id_b
}
+ // (.., T) -> (.., U).
+ (&ty::TyTuple(tys_a), &ty::TyTuple(tys_b)) => {
+ tys_a.len() == tys_b.len()
+ }
+
_ => false
};
match other.candidate {
ObjectCandidate |
ParamCandidate(_) | ProjectionCandidate => match victim.candidate {
- DefaultImplCandidate(..) => {
+ AutoImplCandidate(..) => {
bug!(
"default implementations shouldn't be recorded \
when there are other valid candidates");
}
ImplCandidate(..) |
- ClosureCandidate(..) |
+ ClosureCandidate |
+ GeneratorCandidate |
FnPointerCandidate |
BuiltinObjectCandidate |
BuiltinUnsizeCandidate |
- DefaultImplObjectCandidate(..) |
BuiltinCandidate { .. } => {
// We have a where-clause so don't go around looking
// for impls.
if other.evaluation == EvaluatedToOk {
if let ImplCandidate(victim_def) = victim.candidate {
let tcx = self.tcx().global_tcx();
- return traits::specializes(tcx, other_def, victim_def);
+ return tcx.specializes((other_def, victim_def)) ||
+ tcx.impls_are_allowed_to_overlap(other_def, victim_def);
}
}
ty::TyInfer(ty::IntVar(_)) | ty::TyInfer(ty::FloatVar(_)) |
ty::TyUint(_) | ty::TyInt(_) | ty::TyBool | ty::TyFloat(_) |
ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyRawPtr(..) |
- ty::TyChar | ty::TyBox(_) | ty::TyRef(..) |
- ty::TyArray(..) | ty::TyClosure(..) | ty::TyNever |
- ty::TyError => {
+ ty::TyChar | ty::TyRef(..) | ty::TyGenerator(..) |
+ ty::TyGeneratorWitness(..) | ty::TyArray(..) | ty::TyClosure(..) |
+ ty::TyNever | ty::TyError => {
// safe for everything
- Where(ty::Binder(Vec::new()))
+ Where(ty::Binder::dummy(Vec::new()))
}
- ty::TyStr | ty::TySlice(_) | ty::TyTrait(..) => Never,
+ ty::TyStr | ty::TySlice(_) | ty::TyDynamic(..) | ty::TyForeign(..) => Never,
ty::TyTuple(tys) => {
- Where(ty::Binder(tys.last().into_iter().cloned().collect()))
+ Where(ty::Binder::bind(tys.last().into_iter().cloned().collect()))
}
ty::TyAdt(def, substs) => {
let sized_crit = def.sized_constraint(self.tcx());
// (*) binder moved here
- Where(ty::Binder(match sized_crit.sty {
- ty::TyTuple(tys) => tys.to_vec().subst(self.tcx(), substs),
- ty::TyBool => vec![],
- _ => vec![sized_crit.subst(self.tcx(), substs)]
- }))
+ Where(ty::Binder::bind(
+ sized_crit.iter().map(|ty| ty.subst(self.tcx(), substs)).collect()
+ ))
}
ty::TyProjection(_) | ty::TyParam(_) | ty::TyAnon(..) => None,
ty::TyInfer(ty::TyVar(_)) => Ambiguous,
- ty::TyInfer(ty::FreshTy(_))
- | ty::TyInfer(ty::FreshIntTy(_))
- | ty::TyInfer(ty::FreshFloatTy(_)) => {
+ ty::TyInfer(ty::CanonicalTy(_)) |
+ ty::TyInfer(ty::FreshTy(_)) |
+ ty::TyInfer(ty::FreshIntTy(_)) |
+ ty::TyInfer(ty::FreshFloatTy(_)) => {
bug!("asked to assemble builtin bounds of unexpected type: {:?}",
self_ty);
}
}
}
- fn copy_conditions(&mut self, obligation: &TraitObligation<'tcx>)
+ fn copy_clone_conditions(&mut self, obligation: &TraitObligation<'tcx>)
-> BuiltinImplConditions<'tcx>
{
// NOTE: binder moved to (*)
match self_ty.sty {
ty::TyInfer(ty::IntVar(_)) | ty::TyInfer(ty::FloatVar(_)) |
+ ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyError => {
+ Where(ty::Binder::dummy(Vec::new()))
+ }
+
ty::TyUint(_) | ty::TyInt(_) | ty::TyBool | ty::TyFloat(_) |
- ty::TyFnDef(..) | ty::TyFnPtr(_) | ty::TyChar |
- ty::TyRawPtr(..) | ty::TyError | ty::TyNever |
+ ty::TyChar | ty::TyRawPtr(..) | ty::TyNever |
ty::TyRef(_, ty::TypeAndMut { ty: _, mutbl: hir::MutImmutable }) => {
- Where(ty::Binder(Vec::new()))
+ // Implementations provided in libcore
+ None
}
- ty::TyBox(_) | ty::TyTrait(..) | ty::TyStr | ty::TySlice(..) |
- ty::TyClosure(..) |
+ ty::TyDynamic(..) | ty::TyStr | ty::TySlice(..) |
+ ty::TyGenerator(..) | ty::TyGeneratorWitness(..) | ty::TyForeign(..) |
ty::TyRef(_, ty::TypeAndMut { ty: _, mutbl: hir::MutMutable }) => {
Never
}
ty::TyArray(element_ty, _) => {
// (*) binder moved here
- Where(ty::Binder(vec![element_ty]))
+ Where(ty::Binder::bind(vec![element_ty]))
}
ty::TyTuple(tys) => {
// (*) binder moved here
- Where(ty::Binder(tys.to_vec()))
+ Where(ty::Binder::bind(tys.to_vec()))
+ }
+
+ ty::TyClosure(def_id, substs) => {
+ let trait_id = obligation.predicate.def_id();
+ let is_copy_trait = Some(trait_id) == self.tcx().lang_items().copy_trait();
+ let is_clone_trait = Some(trait_id) == self.tcx().lang_items().clone_trait();
+ if is_copy_trait || is_clone_trait {
+ Where(ty::Binder::bind(substs.upvar_tys(def_id, self.tcx()).collect()))
+ } else {
+ Never
+ }
}
ty::TyAdt(..) | ty::TyProjection(..) | ty::TyParam(..) | ty::TyAnon(..) => {
Ambiguous
}
- ty::TyInfer(ty::FreshTy(_))
- | ty::TyInfer(ty::FreshIntTy(_))
- | ty::TyInfer(ty::FreshFloatTy(_)) => {
+ ty::TyInfer(ty::CanonicalTy(_)) |
+ ty::TyInfer(ty::FreshTy(_)) |
+ ty::TyInfer(ty::FreshIntTy(_)) |
+ ty::TyInfer(ty::FreshFloatTy(_)) => {
bug!("asked to assemble builtin bounds of unexpected type: {:?}",
self_ty);
}
Vec::new()
}
- ty::TyTrait(..) |
+ ty::TyDynamic(..) |
ty::TyParam(..) |
+ ty::TyForeign(..) |
ty::TyProjection(..) |
- ty::TyAnon(..) |
+ ty::TyInfer(ty::CanonicalTy(_)) |
ty::TyInfer(ty::TyVar(_)) |
ty::TyInfer(ty::FreshTy(_)) |
ty::TyInfer(ty::FreshIntTy(_)) |
t);
}
- ty::TyBox(referent_ty) => { // Box<T>
- vec![referent_ty]
- }
-
ty::TyRawPtr(ty::TypeAndMut { ty: element_ty, ..}) |
ty::TyRef(_, ty::TypeAndMut { ty: element_ty, ..}) => {
vec![element_ty]
tys.to_vec()
}
- ty::TyClosure(_, ref substs) => {
- // FIXME(#27086). We are invariant w/r/t our
- // substs.func_substs, but we don't see them as
- // constituent types; this seems RIGHT but also like
- // something that a normal type couldn't simulate. Is
- // this just a gap with the way that PhantomData and
- // OIBIT interact? That is, there is no way to say
- // "make me invariant with respect to this TYPE, but
- // do not act as though I can reach it"
- substs.upvar_tys.to_vec()
+ ty::TyClosure(def_id, ref substs) => {
+ substs.upvar_tys(def_id, self.tcx()).collect()
+ }
+
+ ty::TyGenerator(def_id, ref substs, interior) => {
+ substs.upvar_tys(def_id, self.tcx()).chain(iter::once(interior.witness)).collect()
+ }
+
+ ty::TyGeneratorWitness(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`
.map(|f| f.ty(self.tcx(), substs))
.collect()
}
+
+ ty::TyAnon(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,
// 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(ty); // <----------/
+ let ty: ty::Binder<Ty<'tcx>> = ty::Binder::bind(ty); // <----/
self.in_snapshot(|this, snapshot| {
let (skol_ty, skol_map) =
- this.infcx().skolemize_late_bound_regions(&ty, snapshot);
+ this.infcx().skolemize_late_bound_regions(&ty);
let Normalized { value: normalized_ty, mut obligations } =
project::normalize_with_depth(this,
+ param_env,
cause.clone(),
recursion_depth,
&skol_ty);
let skol_obligation =
- this.tcx().predicate_for_trait_def(
- cause.clone(),
- trait_def_id,
- recursion_depth,
- normalized_ty,
- &[]);
+ this.tcx().predicate_for_trait_def(param_env,
+ cause.clone(),
+ trait_def_id,
+ recursion_depth,
+ normalized_ty,
+ &[]);
obligations.push(skol_obligation);
- this.infcx().plug_leaks(skol_map, snapshot, &obligations)
+ this.infcx().plug_leaks(skol_map, snapshot, obligations)
})
}).collect()
}
//
// Confirmation unifies the output type parameters of the trait
// with the values found in the obligation, possibly yielding a
- // type error. See `README.md` for more details.
+ // type error. See [rustc guide] for more details.
+ //
+ // [rustc guide]:
+ // https://rust-lang-nursery.github.io/rustc-guide/trait-resolution.html#confirmation
fn confirm_candidate(&mut self,
obligation: &TraitObligation<'tcx>,
match candidate {
BuiltinCandidate { has_nested } => {
- Ok(VtableBuiltin(
- self.confirm_builtin_candidate(obligation, has_nested)))
+ let data = self.confirm_builtin_candidate(obligation, has_nested);
+ Ok(VtableBuiltin(data))
}
ParamCandidate(param) => {
Ok(VtableParam(obligations))
}
- DefaultImplCandidate(trait_def_id) => {
- let data = self.confirm_default_impl_candidate(obligation, trait_def_id);
- Ok(VtableDefaultImpl(data))
- }
-
- DefaultImplObjectCandidate(trait_def_id) => {
- let data = self.confirm_default_impl_object_candidate(obligation, trait_def_id);
- Ok(VtableDefaultImpl(data))
+ AutoImplCandidate(trait_def_id) => {
+ let data = self.confirm_auto_impl_candidate(obligation, trait_def_id);
+ Ok(VtableAutoImpl(data))
}
ImplCandidate(impl_def_id) => {
Ok(VtableImpl(self.confirm_impl_candidate(obligation, impl_def_id)))
}
- ClosureCandidate(closure_def_id, substs, kind) => {
- let vtable_closure =
- self.confirm_closure_candidate(obligation, closure_def_id, substs, kind)?;
+ 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))
+ }
+
BuiltinObjectCandidate => {
// This indicates something like `(Trait+Send) :
// Send`. In this case, we know that this holds
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 = match trait_def {
- _ if Some(trait_def) == self.tcx().lang_items.sized_trait() => {
+ _ if Some(trait_def) == lang_items.sized_trait() => {
self.sized_conditions(obligation)
}
- _ if Some(trait_def) == self.tcx().lang_items.copy_trait() => {
- self.copy_conditions(obligation)
+ _ if Some(trait_def) == lang_items.copy_trait() => {
+ self.copy_clone_conditions(obligation)
+ }
+ _ if Some(trait_def) == lang_items.clone_trait() => {
+ self.copy_clone_conditions(obligation)
}
_ => bug!("unexpected builtin trait {:?}", trait_def)
};
};
let cause = obligation.derived_cause(BuiltinDerivedObligation);
- self.collect_predicates_for_types(cause,
+ self.collect_predicates_for_types(obligation.param_env,
+ cause,
obligation.recursion_depth+1,
trait_def,
nested)
debug!("confirm_builtin_candidate: obligations={:?}",
obligations);
+
VtableBuiltinData { nested: obligations }
}
- /// This handles the case where a `impl Foo for ..` impl is being used.
+ /// 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_default_impl_candidate(&mut self,
- obligation: &TraitObligation<'tcx>,
- trait_def_id: DefId)
- -> VtableDefaultImplData<PredicateObligation<'tcx>>
- {
- debug!("confirm_default_impl_candidate({:?}, {:?})",
- obligation,
- trait_def_id);
-
- // binder is moved below
- let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty());
- let types = self.constituent_types_for_ty(self_ty);
- self.vtable_default_impl(obligation, trait_def_id, ty::Binder(types))
- }
-
- fn confirm_default_impl_object_candidate(&mut self,
- obligation: &TraitObligation<'tcx>,
- trait_def_id: DefId)
- -> VtableDefaultImplData<PredicateObligation<'tcx>>
+ fn confirm_auto_impl_candidate(&mut self,
+ obligation: &TraitObligation<'tcx>,
+ trait_def_id: DefId)
+ -> VtableAutoImplData<PredicateObligation<'tcx>>
{
- debug!("confirm_default_impl_object_candidate({:?}, {:?})",
+ debug!("confirm_auto_impl_candidate({:?}, {:?})",
obligation,
trait_def_id);
- assert!(self.tcx().has_attr(trait_def_id, "rustc_reflect_like"));
-
- // OK to skip binder, it is reintroduced below
- let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty());
- match self_ty.sty {
- ty::TyTrait(ref data) => {
- // OK to skip the binder, it is reintroduced below
- let input_types = data.principal.input_types();
- let assoc_types = data.projection_bounds.iter()
- .map(|pb| pb.skip_binder().ty);
- let all_types: Vec<_> = input_types.chain(assoc_types)
- .collect();
-
- // reintroduce the two binding levels we skipped, then flatten into one
- let all_types = ty::Binder(ty::Binder(all_types));
- let all_types = self.tcx().flatten_late_bound_regions(&all_types);
-
- self.vtable_default_impl(obligation, trait_def_id, all_types)
- }
- _ => {
- bug!("asked to confirm default object implementation for non-object type: {:?}",
- self_ty);
- }
- }
+ 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_default_impl_candidate`
- fn vtable_default_impl(&mut self,
+ /// See `confirm_auto_impl_candidate`
+ fn vtable_auto_impl(&mut self,
obligation: &TraitObligation<'tcx>,
trait_def_id: DefId,
nested: ty::Binder<Vec<Ty<'tcx>>>)
- -> Vtable
DefaultImplData<PredicateObligation<'tcx>>
+ -> Vtable
AutoImplData<PredicateObligation<'tcx>>
{
- debug!("vtable_default_impl: nested={:?}", nested);
+ 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,
let trait_obligations = self.in_snapshot(|this, snapshot| {
let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
let (trait_ref, skol_map) =
- this.infcx().skolemize_late_bound_regions(&poly_trait_ref, snapshot);
+ this.infcx().skolemize_late_bound_regions(&poly_trait_ref);
let cause = obligation.derived_cause(ImplDerivedObligation);
this.impl_or_trait_obligations(cause,
obligation.recursion_depth + 1,
+ obligation.param_env,
trait_def_id,
&trait_ref.substs,
skol_map,
obligations.extend(trait_obligations);
- debug!("vtable_default_impl: obligations={:?}", obligations);
+ debug!("vtable_auto_impl: obligations={:?}", obligations);
- VtableDefaultImplData {
- trait_def_id: trait_def_id,
+ VtableAutoImplData {
+ trait_def_id,
nested: obligations
}
}
snapshot);
debug!("confirm_impl_candidate substs={:?}", substs);
let cause = obligation.derived_cause(ImplDerivedObligation);
- this.vtable_impl(impl_def_id, substs, cause,
+ this.vtable_impl(impl_def_id,
+ substs,
+ cause,
obligation.recursion_depth + 1,
- skol_map, snapshot)
+ obligation.param_env,
+ skol_map,
+ snapshot)
})
}
mut substs: Normalized<'tcx, &'tcx Substs<'tcx>>,
cause: ObligationCause<'tcx>,
recursion_depth: usize,
+ param_env: ty::ParamEnv<'tcx>,
skol_map: infer::SkolemizationMap<'tcx>,
- snapshot: &infer::CombinedSnapshot)
+ snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
-> VtableImplData<'tcx, PredicateObligation<'tcx>>
{
debug!("vtable_impl(impl_def_id={:?}, substs={:?}, recursion_depth={}, skol_map={:?})",
let mut impl_obligations =
self.impl_or_trait_obligations(cause,
recursion_depth,
+ param_env,
impl_def_id,
&substs.value,
skol_map,
// 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: impl_def_id,
+ VtableImplData { impl_def_id,
substs: substs.value,
nested: impl_obligations }
}
// case that results. -nmatsakis
let self_ty = self.infcx.shallow_resolve(*obligation.self_ty().skip_binder());
let poly_trait_ref = match self_ty.sty {
- ty::TyTrait(ref data) => {
- data.principal.with_self_ty(self.tcx(), self_ty)
+ ty::TyDynamic(ref data, ..) => {
+ data.principal().unwrap().with_self_ty(self.tcx(), self_ty)
}
_ => {
span_bug!(obligation.cause.span,
};
let mut upcast_trait_ref = None;
+ let mut nested = vec![];
let vtable_base;
{
self.commit_if_ok(
|this, _| this.match_poly_trait_ref(obligation, t))
{
- Ok(_) => { upcast_trait_ref = Some(t); false }
+ Ok(obligations) => {
+ upcast_trait_ref = Some(t);
+ nested.extend(obligations);
+ false
+ }
Err(_) => { true }
}
});
VtableObjectData {
upcast_trait_ref: upcast_trait_ref.unwrap(),
- vtable_base: vtable_base,
- nested: vec![]
+ vtable_base,
+ nested,
}
}
// ok 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();
+ 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,
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: vec![] })
+ Ok(VtableFnPointerData { fn_ty: self_ty, nested: obligations })
}
- fn confirm_closure_candidate(&mut self,
- obligation: &TraitObligation<'tcx>,
- closure_def_id: DefId,
- substs: ty::ClosureSubsts<'tcx>,
- kind: ty::ClosureKind)
- -> Result<VtableClosureData<'tcx, PredicateObligation<'tcx>>,
+ fn confirm_generator_candidate(&mut self,
+ obligation: &TraitObligation<'tcx>)
+ -> Result<VtableGeneratorData<'tcx, PredicateObligation<'tcx>>,
SelectionError<'tcx>>
{
- debug!("confirm_closure_candidate({:?},{:?},{:?})",
+ // ok 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 (closure_def_id, substs) = match self_ty.sty {
+ ty::TyGenerator(id, substs, _) => (id, substs),
+ _ => bug!("closure candidate for non-closure {:?}", obligation)
+ };
+
+ debug!("confirm_generator_candidate({:?},{:?},{:?})",
obligation,
closure_def_id,
substs);
+ let trait_ref =
+ self.generator_trait_ref_unnormalized(obligation, closure_def_id, substs);
let Normalized {
value: trait_ref,
mut obligations
- } = self.closure_trait_ref(obligation, closure_def_id, substs);
+ } = normalize_with_depth(self,
+ obligation.param_env,
+ obligation.cause.clone(),
+ obligation.recursion_depth+1,
+ &trait_ref);
+
+ debug!("confirm_generator_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)?);
+
+ Ok(VtableGeneratorData {
+ closure_def_id: closure_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 = match self.tcx().lang_items().fn_trait_kind(obligation.predicate.def_id()) {
+ Some(k) => k,
+ None => bug!("closure candidate for non-fn trait {:?}", obligation)
+ };
+
+ // ok 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::TyClosure(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);
- self.confirm_poly_trait_refs(obligation.cause.clone(),
- obligation.predicate.to_poly_trait_ref(),
- trait_ref)?;
+ obligations.extend(
+ self.confirm_poly_trait_refs(obligation.cause.clone(),
+ obligation.param_env,
+ obligation.predicate.to_poly_trait_ref(),
+ trait_ref)?);
obligations.push(Obligation::new(
- obligation.cause.clone(),
- ty::Predicate::ClosureKind(closure_def_id, kind)));
+ obligation.cause.clone(),
+ obligation.param_env,
+ ty::Predicate::ClosureKind(closure_def_id, substs, kind)));
Ok(VtableClosureData {
- closure_def_id: closure_def_id,
+ closure_def_id,
substs: substs.clone(),
nested: obligations
})
/// 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,
+ obligation_cause: ObligationCause<'tcx>,
+ obligation_param_env: ty::ParamEnv<'tcx>,
obligation_trait_ref: ty::PolyTraitRef<'tcx>,
expected_trait_ref: ty::PolyTraitRef<'tcx>)
- -> Result<(), SelectionError<'tcx>>
+ -> Result<Vec<PredicateObligation<'tcx>>, SelectionError<'tcx>>
{
- let origin = TypeOrigin::RelateOutputImplTypes(obligation_cause.span);
-
let obligation_trait_ref = obligation_trait_ref.clone();
- self.infcx.sub_poly_trait_refs(false,
- origin,
- expected_trait_ref.clone(),
- obligation_trait_ref.clone())
- .map(|InferOk { obligations, .. }| self.inferred_obligations.extend(obligations))
+ 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>> {
+ -> 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(
- tcx.no_late_bound_regions(&obligation.self_ty()).unwrap());
+ obligation.self_ty().no_late_bound_regions().unwrap());
let target = obligation.predicate.skip_binder().trait_ref.substs.type_at(1);
let target = self.infcx.shallow_resolve(target);
let mut nested = vec![];
match (&source.sty, &target.sty) {
// Trait+Kx+'a -> Trait+Ky+'b (upcasts).
- (&ty::TyTrait(ref data_a), &ty::TyTrait(ref data_b)) => {
+ (&ty::TyDynamic(ref data_a, r_a), &ty::TyDynamic(ref data_b, r_b)) => {
// See assemble_candidates_for_unsizing for more info.
- let new_trait = tcx.mk_trait(ty::TraitObject {
- principal: data_a.principal,
- region_bound: data_b.region_bound,
- builtin_bounds: data_b.builtin_bounds,
- projection_bounds: data_a.projection_bounds.clone(),
+ let existential_predicates = data_a.map_bound(|data_a| {
+ let principal = data_a.principal();
+ let iter = principal.into_iter().map(ty::ExistentialPredicate::Trait)
+ .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 origin = TypeOrigin::Misc(obligation.cause.span);
+ let new_trait = tcx.mk_dynamic(existential_predicates, r_b);
let InferOk { obligations, .. } =
- self.infcx.sub_types(false, origin, new_trait, target)
- .map_err(|_| Unimplemented)?;
- self.inferred_obligations.extend(obligations);
+ self.infcx.at(&obligation.cause, obligation.param_env)
+ .eq(target, new_trait)
+ .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(data_a.region_bound,
- data_b.region_bound);
+ let outlives = ty::OutlivesPredicate(r_a, r_b);
nested.push(Obligation::with_depth(cause,
obligation.recursion_depth + 1,
- ty::Binder(outlives).to_predicate()));
+ obligation.param_env,
+ ty::Binder::bind(outlives).to_predicate()));
}
// T -> Trait.
- (_, &ty::TyTrait(ref data)) => {
+ (_, &ty::TyDynamic(ref data, r)) => {
let mut object_dids =
- data.builtin_bounds.iter().flat_map(|bound| {
- tcx.lang_items.from_builtin_kind(bound).ok()
- })
- .chain(Some(data.principal.def_id()));
+ data.auto_traits().chain(data.principal().map(|p| p.def_id()));
if let Some(did) = object_dids.find(|did| {
!tcx.is_object_safe(*did)
}) {
let mut push = |predicate| {
nested.push(Obligation::with_depth(cause.clone(),
obligation.recursion_depth + 1,
+ obligation.param_env,
predicate));
};
- // Create the obligation for casting from T to Trait.
- push(data.principal.with_self_ty(tcx, source).to_predicate());
-
- // We can only make objects from sized types.
- let mut builtin_bounds = data.builtin_bounds;
- builtin_bounds.insert(ty::BoundSized);
-
- // Create additional obligations 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.)
- for bound in &builtin_bounds {
- if let Ok(tr) = tcx.trait_ref_for_builtin_bound(bound, source) {
- push(tr.to_predicate());
- } else {
- return Err(Unimplemented);
- }
+ // 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
+ for predicate in data.iter() {
+ push(predicate.with_self_ty(tcx, source));
}
- // Create obligations for the projection predicates.
- for bound in &data.projection_bounds {
- push(bound.with_self_ty(tcx, source).to_predicate());
- }
+ // 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, &[]),
+ };
+ push(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, data.region_bound);
- push(ty::Binder(outlives).to_predicate());
+ let outlives = ty::OutlivesPredicate(source, r);
+ push(ty::Binder::dummy(outlives).to_predicate());
}
// [T; n] -> [T].
(&ty::TyArray(a, _), &ty::TySlice(b)) => {
- let origin = TypeOrigin::Misc(obligation.cause.span);
let InferOk { obligations, .. } =
- self.infcx.sub_types(false, origin, a, b)
- .map_err(|_| Unimplemented)?;
- self.inferred_obligations.extend(obligations);
+ self.infcx.at(&obligation.cause, obligation.param_env)
+ .eq(b, a)
+ .map_err(|_| Unimplemented)?;
+ nested.extend(obligations);
}
// Struct<T> -> Struct<U>.
(&ty::TyAdt(def, substs_a), &ty::TyAdt(_, substs_b)) => {
let fields = def
.all_fields()
- .map(|f| f.unsubst_ty())
+ .map(|f| tcx.type_of(f.did))
.collect::<Vec<_>>();
// The last field of the structure has to exist and contain type parameters.
// TyError 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.params().iter().enumerate().map(|(i, &k)| {
+ let params = substs_a.iter().enumerate().map(|(i, &k)| {
if ty_params.contains(i) {
Kind::from(tcx.types.err)
} else {
k
}
});
- let substs = Substs::new(tcx, params);
+ let substs = tcx.mk_substs(params);
for &ty in fields.split_last().unwrap().1 {
if ty.subst(tcx, substs).references_error() {
return Err(Unimplemented);
let inner_source = field.subst(tcx, substs_a);
let inner_target = field.subst(tcx, substs_b);
- // Check that the source structure with the target's
- // type parameters is a subtype of the target.
- let params = substs_a.params().iter().enumerate().map(|(i, &k)| {
+ // 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) {
- Kind::from(substs_b.type_at(i))
+ substs_b.type_at(i).into()
} else {
k
}
});
- let new_struct = tcx.mk_adt(def, Substs::new(tcx, params));
- let origin = TypeOrigin::Misc(obligation.cause.span);
+ let new_struct = tcx.mk_adt(def, tcx.mk_substs(params));
let InferOk { obligations, .. } =
- self.infcx.sub_types(false, origin, new_struct, target)
- .map_err(|_| Unimplemented)?;
- self.inferred_obligations.extend(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_target]));
}
+ // (.., T) -> (.., U).
+ (&ty::TyTuple(tys_a), &ty::TyTuple(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().chain(Some(b_last)));
+ 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,
+ &[b_last]));
+ }
+
_ => bug!()
};
fn rematch_impl(&mut self,
impl_def_id: DefId,
obligation: &TraitObligation<'tcx>,
- snapshot: &infer::CombinedSnapshot)
+ snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
-> (Normalized<'tcx, &'tcx Substs<'tcx>>,
infer::SkolemizationMap<'tcx>)
{
fn match_impl(&mut self,
impl_def_id: DefId,
obligation: &TraitObligation<'tcx>,
- snapshot: &infer::CombinedSnapshot)
+ snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
-> Result<(Normalized<'tcx, &'tcx Substs<'tcx>>,
infer::SkolemizationMap<'tcx>), ()>
{
}
let (skol_obligation, skol_map) = self.infcx().skolemize_late_bound_regions(
- &obligation.predicate,
- snapshot);
+ &obligation.predicate);
let skol_obligation_trait_ref = skol_obligation.trait_ref;
let impl_substs = self.infcx.fresh_substs_for_item(obligation.cause.span,
let impl_trait_ref = impl_trait_ref.subst(self.tcx(),
impl_substs);
- let impl_trait_ref =
+ let Normalized { value: impl_trait_ref, obligations: mut nested_obligations } =
project::normalize_with_depth(self,
+ obligation.param_env,
obligation.cause.clone(),
obligation.recursion_depth + 1,
&impl_trait_ref);
impl_trait_ref,
skol_obligation_trait_ref);
- let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
let InferOk { obligations, .. } =
- self.infcx.eq_trait_refs(false,
- origin,
- impl_trait_ref.value.clone(),
- skol_obligation_trait_ref)
- .map_err(|e| {
- debug!("match_impl: failed eq_trait_refs due to `{}`", e);
- ()
- })?;
- self.inferred_obligations.extend(obligations);
+ self.infcx.at(&obligation.cause, obligation.param_env)
+ .eq(skol_obligation_trait_ref, impl_trait_ref)
+ .map_err(|e| {
+ debug!("match_impl: failed eq_trait_refs due to `{}`", e);
+ ()
+ })?;
+ nested_obligations.extend(obligations);
if let Err(e) = self.infcx.leak_check(false,
obligation.cause.span,
debug!("match_impl: success impl_substs={:?}", impl_substs);
Ok((Normalized {
value: impl_substs,
- obligations: impl_trait_ref.obligations
+ obligations: nested_obligations
}, skol_map))
}
where_clause_trait_ref: ty::PolyTraitRef<'tcx>)
-> Result<Vec<PredicateObligation<'tcx>>,()>
{
- self.match_poly_trait_ref(obligation, where_clause_trait_ref)?;
- Ok(Vec::new())
+ self.match_poly_trait_ref(obligation, where_clause_trait_ref)
}
/// Returns `Ok` if `poly_trait_ref` being true implies that the
fn match_poly_trait_ref(&mut self,
obligation: &TraitObligation<'tcx>,
poly_trait_ref: ty::PolyTraitRef<'tcx>)
- -> Result<(),()>
+ -> Result<Vec<PredicateObligation<'tcx>>,()>
{
debug!("match_poly_trait_ref: obligation={:?} poly_trait_ref={:?}",
obligation,
poly_trait_ref);
- let origin = TypeOrigin::RelateOutputImplTypes(obligation.cause.span);
- self.infcx.sub_poly_trait_refs(false,
- origin,
- poly_trait_ref,
- obligation.predicate.to_poly_trait_ref())
- .map(|InferOk { obligations, .. }| self.inferred_obligations.extend(obligations))
- .map_err(|_| ())
+ self.infcx.at(&obligation.cause, obligation.param_env)
+ .sup(obligation.predicate.to_poly_trait_ref(), poly_trait_ref)
+ .map(|InferOk { obligations, .. }| obligations)
+ .map_err(|_| ())
}
///////////////////////////////////////////////////////////////////////////
obligation.predicate.to_poly_trait_ref().fold_with(&mut self.freshener);
TraitObligationStack {
- obligation: obligation,
- fresh_trait_ref: fresh_trait_ref,
+ obligation,
+ fresh_trait_ref,
previous: previous_stack,
}
}
substs: ty::ClosureSubsts<'tcx>)
-> ty::PolyTraitRef<'tcx>
{
- let closure_type = self.infcx.closure_type(closure_def_id, substs);
- let ty::Binder((trait_ref, _)) =
- self.tcx().closure_trait_ref_and_return_type(obligation.predicate.def_id(),
- obligation.predicate.0.self_ty(), // (1)
- &closure_type.sig,
- util::TupleArgumentsFlag::No);
+ let closure_type = self.infcx.closure_sig(closure_def_id, substs);
+
// (1) Feels icky to skip the binder here, but OTOH we know
// that the self-type is an unboxed closure type and hence is
// in fact unparameterized (or at least does not reference any
// regions bound in the obligation). Still probably some
// refactoring could make this nicer.
- ty::Binder(trait_ref)
+ self.tcx().closure_trait_ref_and_return_type(obligation.predicate.def_id(),
+ obligation.predicate
+ .skip_binder().self_ty(), // (1)
+ closure_type,
+ util::TupleArgumentsFlag::No)
+ .map_bound(|(trait_ref, _)| trait_ref)
}
- fn closure_trait_ref(&mut self,
- obligation: &TraitObligation<'tcx>,
- closure_def_id: DefId,
- substs: ty::ClosureSubsts<'tcx>)
- -> Normalized<'tcx, ty::PolyTraitRef<'tcx>>
+ fn generator_trait_ref_unnormalized(&mut self,
+ obligation: &TraitObligation<'tcx>,
+ closure_def_id: DefId,
+ substs: ty::ClosureSubsts<'tcx>)
+ -> ty::PolyTraitRef<'tcx>
{
- let trait_ref = self.closure_trait_ref_unnormalized(
- obligation, closure_def_id, substs);
+ let gen_sig = substs.generator_poly_sig(closure_def_id, self.tcx());
- // A closure signature can contain associated types which
- // must be normalized.
- normalize_with_depth(self,
- obligation.cause.clone(),
- obligation.recursion_depth+1,
- &trait_ref)
+ // (1) Feels icky to skip the binder here, but OTOH we know
+ // that the self-type is an generator type and hence is
+ // in fact unparameterized (or at least does not reference any
+ // regions bound in the obligation). Still probably some
+ // refactoring could make this nicer.
+
+ self.tcx().generator_trait_ref_and_outputs(obligation.predicate.def_id(),
+ obligation.predicate
+ .skip_binder().self_ty(), // (1)
+ gen_sig)
+ .map_bound(|(trait_ref, ..)| trait_ref)
}
/// Returns the obligations that are implied by instantiating an
fn impl_or_trait_obligations(&mut self,
cause: ObligationCause<'tcx>,
recursion_depth: usize,
+ param_env: ty::ParamEnv<'tcx>,
def_id: DefId, // of impl or trait
substs: &Substs<'tcx>, // for impl or trait
skol_map: infer::SkolemizationMap<'tcx>,
- snapshot: &infer::CombinedSnapshot)
+ snapshot: &infer::CombinedSnapshot<'cx, 'tcx>)
-> Vec<PredicateObligation<'tcx>>
{
debug!("impl_or_trait_obligations(def_id={:?})", def_id);
// obligation will normalize to `<$0 as Iterator>::Item = $1` and
// `$1: Copy`, so we must ensure the obligations are emitted in
// that order.
- let predicates = tcx.lookup_predicates(def_id);
+ let predicates = tcx.predicates_of(def_id);
assert_eq!(predicates.parent, None);
- let predicates = predicates.predicates.iter().flat_map(|predicate| {
- let predicate = normalize_with_depth(self, cause.clone(), recursion_depth,
+ let mut predicates: Vec<_> = predicates.predicates.iter().flat_map(|predicate| {
+ let predicate = normalize_with_depth(self, param_env, cause.clone(), recursion_depth,
&predicate.subst(tcx, substs));
predicate.obligations.into_iter().chain(
Some(Obligation {
cause: cause.clone(),
- recursion_depth: recursion_depth,
+ recursion_depth,
+ param_env,
predicate: predicate.value
}))
}).collect();
- self.infcx().plug_leaks(skol_map, snapshot, &predicates)
+ // We are performing deduplication here to avoid exponential blowups
+ // (#38528) from happening, but the real cause of the duplication is
+ // unknown. What we know is that the deduplication avoids exponential
+ // amount of predicates being propogated when processing deeply nested
+ // types.
+ let mut seen = FxHashSet();
+ predicates.retain(|i| seen.insert(i.clone()));
+ self.infcx().plug_leaks(skol_map, snapshot, predicates)
}
}
/*!
* Creates a cause for obligations that are derived from
* `obligation` by a recursive search (e.g., for a builtin
- * bound, or eventually a `impl Foo for ..`). If `obligation`
+ * bound, or eventually a `auto trait Foo`). If `obligation`
* is itself a derived obligation, this is just a clone, but
* otherwise we create a "derived obligation" cause so as to
* keep track of the original root obligation for error
impl<'tcx> SelectionCache<'tcx> {
pub fn new() -> SelectionCache<'tcx> {
SelectionCache {
- hashmap: RefCell::new(FnvHashMap())
+ hashmap: RefCell::new(FxHashMap())
}
}
+
+ pub fn clear(&self) {
+ *self.hashmap.borrow_mut() = FxHashMap()
+ }
}
impl<'tcx> EvaluationCache<'tcx> {
pub fn new() -> EvaluationCache<'tcx> {
EvaluationCache {
- hashmap: RefCell::new(FnvHashMap())
+ hashmap: RefCell::new(FxHashMap())
}
}
+
+ pub fn clear(&self) {
+ *self.hashmap.borrow_mut() = FxHashMap()
+ }
}
impl<'o,'tcx> TraitObligationStack<'o,'tcx> {
}
}
-impl EvaluationResult {
- fn may_apply(&self) -> bool {
- match *self {
- EvaluatedToOk |
- EvaluatedToAmbig |
- EvaluatedToUnknown => true,
+#[derive(Clone)]
+pub struct WithDepNode<T> {
+ dep_node: DepNodeIndex,
+ cached_value: T
+}
- EvaluatedToErr => false
- }
+impl<T: Clone> WithDepNode<T> {
+ pub fn new(dep_node: DepNodeIndex, cached_value: T) -> Self {
+ WithDepNode { dep_node, cached_value }
}
-}
-impl MethodMatchResult {
- pub fn may_apply(&self) -> bool {
- match *self {
- MethodMatched(_) => true,
- MethodAmbiguous(_) => true,
- MethodDidNotMatch => false,
- }
+ pub fn get(&self, tcx: TyCtxt) -> T {
+ tcx.dep_graph.read_index(self.dep_node);
+ self.cached_value.clone()
}
}
projects / rustc.git / blobdiff