use smallvec::smallvec;
use crate::infer::outlives::components::{push_outlives_components, Component};
-use crate::traits::{self, Obligation, ObligationCause, PredicateObligation};
+use crate::traits::{self, Obligation, PredicateObligation};
use rustc_data_structures::fx::{FxHashSet, FxIndexSet};
use rustc_middle::ty::{self, ToPredicate, TyCtxt};
use rustc_span::symbol::Ident;
/// if we know that `T: Ord`, the elaborator would deduce that `T: PartialOrd`
/// holds as well. Similarly, if we have `trait Foo: 'static`, and we know that
/// `T: Foo`, then we know that `T: 'static`.
-pub struct Elaborator<'tcx> {
- stack: Vec<PredicateObligation<'tcx>>,
+pub struct Elaborator<'tcx, O> {
+ stack: Vec<O>,
visited: PredicateSet<'tcx>,
+ only_self: bool,
}
-pub fn elaborate_trait_ref<'tcx>(
- tcx: TyCtxt<'tcx>,
- trait_ref: ty::PolyTraitRef<'tcx>,
-) -> Elaborator<'tcx> {
- elaborate_predicates(tcx, std::iter::once(trait_ref.without_const().to_predicate(tcx)))
+/// Describes how to elaborate an obligation into a sub-obligation.
+///
+/// For [`Obligation`], a sub-obligation is combined with the current obligation's
+/// param-env and cause code. For [`ty::Predicate`], none of this is needed, since
+/// there is no param-env or cause code to copy over.
+pub trait Elaboratable<'tcx> {
+ fn predicate(&self) -> ty::Predicate<'tcx>;
+
+ // Makes a new `Self` but with a different predicate.
+ fn child(&self, predicate: ty::Predicate<'tcx>) -> Self;
+
+ // Makes a new `Self` but with a different predicate and a different cause
+ // code (if `Self` has one).
+ fn child_with_derived_cause(
+ &self,
+ predicate: ty::Predicate<'tcx>,
+ span: Span,
+ parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
+ index: usize,
+ ) -> Self;
}
-pub fn elaborate_trait_refs<'tcx>(
- tcx: TyCtxt<'tcx>,
- trait_refs: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
-) -> Elaborator<'tcx> {
- let predicates = trait_refs.map(|trait_ref| trait_ref.without_const().to_predicate(tcx));
- elaborate_predicates(tcx, predicates)
+impl<'tcx> Elaboratable<'tcx> for PredicateObligation<'tcx> {
+ fn predicate(&self) -> ty::Predicate<'tcx> {
+ self.predicate
+ }
+
+ fn child(&self, predicate: ty::Predicate<'tcx>) -> Self {
+ Obligation {
+ cause: self.cause.clone(),
+ param_env: self.param_env,
+ recursion_depth: 0,
+ predicate,
+ }
+ }
+
+ fn child_with_derived_cause(
+ &self,
+ predicate: ty::Predicate<'tcx>,
+ span: Span,
+ parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
+ index: usize,
+ ) -> Self {
+ let cause = self.cause.clone().derived_cause(parent_trait_pred, |derived| {
+ traits::ImplDerivedObligation(Box::new(traits::ImplDerivedObligationCause {
+ derived,
+ impl_or_alias_def_id: parent_trait_pred.def_id(),
+ impl_def_predicate_index: Some(index),
+ span,
+ }))
+ });
+ Obligation { cause, param_env: self.param_env, recursion_depth: 0, predicate }
+ }
}
-pub fn elaborate_predicates<'tcx>(
- tcx: TyCtxt<'tcx>,
- predicates: impl Iterator<Item = ty::Predicate<'tcx>>,
-) -> Elaborator<'tcx> {
- let obligations = predicates
- .map(|predicate| {
- predicate_obligation(predicate, ty::ParamEnv::empty(), ObligationCause::dummy())
- })
- .collect();
- elaborate_obligations(tcx, obligations)
+impl<'tcx> Elaboratable<'tcx> for ty::Predicate<'tcx> {
+ fn predicate(&self) -> ty::Predicate<'tcx> {
+ *self
+ }
+
+ fn child(&self, predicate: ty::Predicate<'tcx>) -> Self {
+ predicate
+ }
+
+ fn child_with_derived_cause(
+ &self,
+ predicate: ty::Predicate<'tcx>,
+ _span: Span,
+ _parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
+ _index: usize,
+ ) -> Self {
+ predicate
+ }
}
-pub fn elaborate_predicates_with_span<'tcx>(
- tcx: TyCtxt<'tcx>,
- predicates: impl Iterator<Item = (ty::Predicate<'tcx>, Span)>,
-) -> Elaborator<'tcx> {
- let obligations = predicates
- .map(|(predicate, span)| {
- predicate_obligation(
- predicate,
- ty::ParamEnv::empty(),
- ObligationCause::dummy_with_span(span),
- )
- })
- .collect();
- elaborate_obligations(tcx, obligations)
+impl<'tcx> Elaboratable<'tcx> for (ty::Predicate<'tcx>, Span) {
+ fn predicate(&self) -> ty::Predicate<'tcx> {
+ self.0
+ }
+
+ fn child(&self, predicate: ty::Predicate<'tcx>) -> Self {
+ (predicate, self.1)
+ }
+
+ fn child_with_derived_cause(
+ &self,
+ predicate: ty::Predicate<'tcx>,
+ _span: Span,
+ _parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
+ _index: usize,
+ ) -> Self {
+ (predicate, self.1)
+ }
}
-pub fn elaborate_obligations<'tcx>(
+pub fn elaborate<'tcx, O: Elaboratable<'tcx>>(
tcx: TyCtxt<'tcx>,
- obligations: Vec<PredicateObligation<'tcx>>,
-) -> Elaborator<'tcx> {
- let mut elaborator = Elaborator { stack: Vec::new(), visited: PredicateSet::new(tcx) };
+ obligations: impl IntoIterator<Item = O>,
+) -> Elaborator<'tcx, O> {
+ let mut elaborator =
+ Elaborator { stack: Vec::new(), visited: PredicateSet::new(tcx), only_self: false };
elaborator.extend_deduped(obligations);
elaborator
}
-fn predicate_obligation<'tcx>(
- predicate: ty::Predicate<'tcx>,
- param_env: ty::ParamEnv<'tcx>,
- cause: ObligationCause<'tcx>,
-) -> PredicateObligation<'tcx> {
- Obligation { cause, param_env, recursion_depth: 0, predicate }
-}
-
-impl<'tcx> Elaborator<'tcx> {
- fn extend_deduped(&mut self, obligations: impl IntoIterator<Item = PredicateObligation<'tcx>>) {
+impl<'tcx, O: Elaboratable<'tcx>> Elaborator<'tcx, O> {
+ fn extend_deduped(&mut self, obligations: impl IntoIterator<Item = O>) {
// Only keep those bounds that we haven't already seen.
// This is necessary to prevent infinite recursion in some
// cases. One common case is when people define
// `trait Sized: Sized { }` rather than `trait Sized { }`.
// let visited = &mut self.visited;
- self.stack.extend(obligations.into_iter().filter(|o| self.visited.insert(o.predicate)));
+ self.stack.extend(obligations.into_iter().filter(|o| self.visited.insert(o.predicate())));
}
- pub fn filter_to_traits(self) -> FilterToTraits<Self> {
- FilterToTraits::new(self)
+ /// Filter to only the supertraits of trait predicates, i.e. only the predicates
+ /// that have `Self` as their self type, instead of all implied predicates.
+ pub fn filter_only_self(mut self) -> Self {
+ self.only_self = true;
+ self
}
- fn elaborate(&mut self, obligation: &PredicateObligation<'tcx>) {
+ fn elaborate(&mut self, elaboratable: &O) {
let tcx = self.visited.tcx;
- let bound_predicate = obligation.predicate.kind();
+ let bound_predicate = elaboratable.predicate().kind();
match bound_predicate.skip_binder() {
ty::PredicateKind::Clause(ty::Clause::Trait(data)) => {
- // Get predicates declared on the trait.
- let predicates = tcx.super_predicates_of(data.def_id());
+ // Get predicates implied by the trait, or only super predicates if we only care about self predicates.
+ let predicates = if self.only_self {
+ tcx.super_predicates_of(data.def_id())
+ } else {
+ tcx.implied_predicates_of(data.def_id())
+ };
let obligations =
predicates.predicates.iter().enumerate().map(|(index, &(mut pred, span))| {
if data.constness == ty::BoundConstness::NotConst {
pred = pred.without_const(tcx);
}
-
- let cause = obligation.cause.clone().derived_cause(
- bound_predicate.rebind(data),
- |derived| {
- traits::ImplDerivedObligation(Box::new(
- traits::ImplDerivedObligationCause {
- derived,
- impl_or_alias_def_id: data.def_id(),
- impl_def_predicate_index: Some(index),
- span,
- },
- ))
- },
- );
- predicate_obligation(
+ elaboratable.child_with_derived_cause(
pred.subst_supertrait(tcx, &bound_predicate.rebind(data.trait_ref)),
- obligation.param_env,
- cause,
+ span,
+ bound_predicate.rebind(data),
+ index,
)
});
debug!(?data, ?obligations, "super_predicates");
.map(|predicate_kind| {
bound_predicate.rebind(predicate_kind).to_predicate(tcx)
})
- .map(|predicate| {
- predicate_obligation(
- predicate,
- obligation.param_env,
- obligation.cause.clone(),
- )
- }),
+ .map(|predicate| elaboratable.child(predicate)),
);
}
ty::PredicateKind::TypeWellFormedFromEnv(..) => {
// Nothing to elaborate
}
ty::PredicateKind::Ambiguous => {}
- ty::PredicateKind::AliasEq(..) => {
+ ty::PredicateKind::AliasRelate(..) => {
// No
}
ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(..)) => {
}
}
-impl<'tcx> Iterator for Elaborator<'tcx> {
- type Item = PredicateObligation<'tcx>;
+impl<'tcx, O: Elaboratable<'tcx>> Iterator for Elaborator<'tcx, O> {
+ type Item = O;
fn size_hint(&self) -> (usize, Option<usize>) {
(self.stack.len(), None)
// Supertrait iterator
///////////////////////////////////////////////////////////////////////////
-pub type Supertraits<'tcx> = FilterToTraits<Elaborator<'tcx>>;
-
pub fn supertraits<'tcx>(
tcx: TyCtxt<'tcx>,
trait_ref: ty::PolyTraitRef<'tcx>,
-) -> Supertraits<'tcx> {
- elaborate_trait_ref(tcx, trait_ref).filter_to_traits()
+) -> impl Iterator<Item = ty::PolyTraitRef<'tcx>> {
+ elaborate(tcx, [trait_ref.to_predicate(tcx)]).filter_only_self().filter_to_traits()
}
pub fn transitive_bounds<'tcx>(
tcx: TyCtxt<'tcx>,
- bounds: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
-) -> Supertraits<'tcx> {
- elaborate_trait_refs(tcx, bounds).filter_to_traits()
+ trait_refs: impl Iterator<Item = ty::PolyTraitRef<'tcx>>,
+) -> impl Iterator<Item = ty::PolyTraitRef<'tcx>> {
+ elaborate(tcx, trait_refs.map(|trait_ref| trait_ref.to_predicate(tcx)))
+ .filter_only_self()
+ .filter_to_traits()
}
-/// A specialized variant of `elaborate_trait_refs` that only elaborates trait references that may
+/// A specialized variant of `elaborate` that only elaborates trait references that may
/// define the given associated type `assoc_name`. It uses the
/// `super_predicates_that_define_assoc_type` query to avoid enumerating super-predicates that
/// aren't related to `assoc_item`. This is used when resolving types like `Self::Item` or
while let Some(trait_ref) = stack.pop() {
let anon_trait_ref = tcx.anonymize_bound_vars(trait_ref);
if visited.insert(anon_trait_ref) {
- let super_predicates = tcx.super_predicates_that_define_assoc_type((
- trait_ref.def_id(),
- Some(assoc_name),
- ));
+ let super_predicates =
+ tcx.super_predicates_that_define_assoc_type((trait_ref.def_id(), assoc_name));
for (super_predicate, _) in super_predicates.predicates {
let subst_predicate = super_predicate.subst_supertrait(tcx, &trait_ref);
if let Some(binder) = subst_predicate.to_opt_poly_trait_pred() {
// Other
///////////////////////////////////////////////////////////////////////////
+impl<'tcx> Elaborator<'tcx, ty::Predicate<'tcx>> {
+ fn filter_to_traits(self) -> FilterToTraits<Self> {
+ FilterToTraits { base_iterator: self }
+ }
+}
+
/// A filter around an iterator of predicates that makes it yield up
/// just trait references.
pub struct FilterToTraits<I> {
base_iterator: I,
}
-impl<I> FilterToTraits<I> {
- fn new(base: I) -> FilterToTraits<I> {
- FilterToTraits { base_iterator: base }
- }
-}
-
-impl<'tcx, I: Iterator<Item = PredicateObligation<'tcx>>> Iterator for FilterToTraits<I> {
+impl<'tcx, I: Iterator<Item = ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> {
type Item = ty::PolyTraitRef<'tcx>;
fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> {
- while let Some(obligation) = self.base_iterator.next() {
- if let Some(data) = obligation.predicate.to_opt_poly_trait_pred() {
+ while let Some(pred) = self.base_iterator.next() {
+ if let Some(data) = pred.to_opt_poly_trait_pred() {
return Some(data.map_bound(|t| t.trait_ref));
}
}
projects / rustc.git / blobdiff