From 1376c5a617be5c25655d0d7cb63e3beaa5a6e026 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:20:39 +0200 Subject: Merging upstream version 1.70.0+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_infer/src/traits/util.rs | 246 ++++++++++++++++++-------------- 1 file changed, 139 insertions(+), 107 deletions(-) (limited to 'compiler/rustc_infer/src/traits/util.rs') diff --git a/compiler/rustc_infer/src/traits/util.rs b/compiler/rustc_infer/src/traits/util.rs index c07ff5165..ef01d5d51 100644 --- a/compiler/rustc_infer/src/traits/util.rs +++ b/compiler/rustc_infer/src/traits/util.rs @@ -1,7 +1,7 @@ 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; @@ -66,93 +66,146 @@ impl<'tcx> Extend> for PredicateSet<'tcx> { /// 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>, +pub struct Elaborator<'tcx, O> { + stack: Vec, 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>, -) -> 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>, -) -> 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, 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>, -) -> Elaborator<'tcx> { - let mut elaborator = Elaborator { stack: Vec::new(), visited: PredicateSet::new(tcx) }; + obligations: impl IntoIterator, +) -> 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>) { +impl<'tcx, O: Elaboratable<'tcx>> Elaborator<'tcx, O> { + fn extend_deduped(&mut self, obligations: impl IntoIterator) { // 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 { - 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))| { @@ -160,24 +213,11 @@ impl<'tcx> Elaborator<'tcx> { 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"); @@ -280,20 +320,14 @@ impl<'tcx> Elaborator<'tcx> { .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(..)) => { @@ -303,8 +337,8 @@ impl<'tcx> Elaborator<'tcx> { } } -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) { (self.stack.len(), None) @@ -325,23 +359,23 @@ impl<'tcx> Iterator for Elaborator<'tcx> { // Supertrait iterator /////////////////////////////////////////////////////////////////////////// -pub type Supertraits<'tcx> = FilterToTraits>; - 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> { + elaborate(tcx, [trait_ref.to_predicate(tcx)]).filter_only_self().filter_to_traits() } pub fn transitive_bounds<'tcx>( tcx: TyCtxt<'tcx>, - bounds: impl Iterator>, -) -> Supertraits<'tcx> { - elaborate_trait_refs(tcx, bounds).filter_to_traits() + trait_refs: impl Iterator>, +) -> impl Iterator> { + 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 @@ -358,10 +392,8 @@ pub fn transitive_bounds_that_define_assoc_type<'tcx>( 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() { @@ -381,24 +413,24 @@ pub fn transitive_bounds_that_define_assoc_type<'tcx>( // Other /////////////////////////////////////////////////////////////////////////// +impl<'tcx> Elaborator<'tcx, ty::Predicate<'tcx>> { + fn filter_to_traits(self) -> FilterToTraits { + FilterToTraits { base_iterator: self } + } +} + /// A filter around an iterator of predicates that makes it yield up /// just trait references. pub struct FilterToTraits { base_iterator: I, } -impl FilterToTraits { - fn new(base: I) -> FilterToTraits { - FilterToTraits { base_iterator: base } - } -} - -impl<'tcx, I: Iterator>> Iterator for FilterToTraits { +impl<'tcx, I: Iterator>> Iterator for FilterToTraits { type Item = ty::PolyTraitRef<'tcx>; fn next(&mut self) -> Option> { - 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)); } } -- cgit v1.2.3