diff options
author | Mazdak Farrokhzad <twingoow@gmail.com> | 2020-04-03 22:55:08 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-04-03 22:55:08 +0200 |
commit | 752961b4ca5a596a3711cd493cf3f04076f9f539 (patch) | |
tree | fbf80e2f81bc392c451a9623bcabbcbb0250aec1 | |
parent | a928f6446474cc122e7568e6c243d75dc3baa7c5 (diff) | |
parent | 8bedb7eac1b5ddaf29229f16aeb430609e6b9f69 (diff) | |
download | rust-752961b4ca5a596a3711cd493cf3f04076f9f539.tar.gz |
Rollup merge of #70641 - estebank:dedup-code, r=nikomatsakis
Remove duplicated code in trait selection
-rw-r--r-- | src/librustc_infer/traits/mod.rs | 2 | ||||
-rw-r--r-- | src/librustc_infer/traits/util.rs | 80 | ||||
-rw-r--r-- | src/librustc_trait_selection/traits/util.rs | 297 |
3 files changed, 81 insertions, 298 deletions
diff --git a/src/librustc_infer/traits/mod.rs b/src/librustc_infer/traits/mod.rs index 0c451998be4..758a0b39d43 100644 --- a/src/librustc_infer/traits/mod.rs +++ b/src/librustc_infer/traits/mod.rs @@ -6,7 +6,7 @@ mod engine; pub mod error_reporting; mod project; mod structural_impls; -mod util; +pub mod util; use rustc_hir as hir; use rustc_middle::ty::error::{ExpectedFound, TypeError}; diff --git a/src/librustc_infer/traits/util.rs b/src/librustc_infer/traits/util.rs index 80a1e282809..4fa74f93ddc 100644 --- a/src/librustc_infer/traits/util.rs +++ b/src/librustc_infer/traits/util.rs @@ -2,9 +2,12 @@ use smallvec::smallvec; use rustc_data_structures::fx::FxHashSet; use rustc_middle::ty::outlives::Component; -use rustc_middle::ty::{self, ToPolyTraitRef, TyCtxt}; +use rustc_middle::ty::{self, ToPolyTraitRef, ToPredicate, TyCtxt, WithConstness}; -fn anonymize_predicate<'tcx>(tcx: TyCtxt<'tcx>, pred: &ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { +pub fn anonymize_predicate<'tcx>( + tcx: TyCtxt<'tcx>, + pred: &ty::Predicate<'tcx>, +) -> ty::Predicate<'tcx> { match *pred { ty::Predicate::Trait(ref data, constness) => { ty::Predicate::Trait(tcx.anonymize_late_bound_regions(data), constness) @@ -88,6 +91,21 @@ pub struct Elaborator<'tcx> { visited: PredicateSet<'tcx>, } +pub fn elaborate_trait_ref<'tcx>( + tcx: TyCtxt<'tcx>, + trait_ref: ty::PolyTraitRef<'tcx>, +) -> Elaborator<'tcx> { + elaborate_predicates(tcx, vec![trait_ref.without_const().to_predicate()]) +} + +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()).collect(); + elaborate_predicates(tcx, predicates) +} + pub fn elaborate_predicates<'tcx>( tcx: TyCtxt<'tcx>, mut predicates: Vec<ty::Predicate<'tcx>>, @@ -98,6 +116,10 @@ pub fn elaborate_predicates<'tcx>( } impl Elaborator<'tcx> { + pub fn filter_to_traits(self) -> FilterToTraits<Self> { + FilterToTraits::new(self) + } + fn elaborate(&mut self, predicate: &ty::Predicate<'tcx>) { let tcx = self.visited.tcx; match *predicate { @@ -223,3 +245,57 @@ impl Iterator for Elaborator<'tcx> { } } } + +/////////////////////////////////////////////////////////////////////////// +// 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() +} + +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() +} + +/////////////////////////////////////////////////////////////////////////// +// Other +/////////////////////////////////////////////////////////////////////////// + +/// 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 = ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> { + type Item = ty::PolyTraitRef<'tcx>; + + fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> { + while let Some(pred) = self.base_iterator.next() { + if let ty::Predicate::Trait(data, _) = pred { + return Some(data.to_poly_trait_ref()); + } + } + None + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let (_, upper) = self.base_iterator.size_hint(); + (0, upper) + } +} diff --git a/src/librustc_trait_selection/traits/util.rs b/src/librustc_trait_selection/traits/util.rs index 6348673dab8..725c41c1e2c 100644 --- a/src/librustc_trait_selection/traits/util.rs +++ b/src/librustc_trait_selection/traits/util.rs @@ -5,270 +5,11 @@ use smallvec::SmallVec; use rustc_data_structures::fx::FxHashSet; use rustc_hir::def_id::DefId; -use rustc_middle::ty::outlives::Component; use rustc_middle::ty::subst::{GenericArg, Subst, SubstsRef}; -use rustc_middle::ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, WithConstness}; +use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt, WithConstness}; use super::{Normalized, Obligation, ObligationCause, PredicateObligation, SelectionContext}; - -fn anonymize_predicate<'tcx>(tcx: TyCtxt<'tcx>, pred: &ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { - match *pred { - ty::Predicate::Trait(ref data, constness) => { - ty::Predicate::Trait(tcx.anonymize_late_bound_regions(data), constness) - } - - ty::Predicate::RegionOutlives(ref data) => { - ty::Predicate::RegionOutlives(tcx.anonymize_late_bound_regions(data)) - } - - ty::Predicate::TypeOutlives(ref data) => { - ty::Predicate::TypeOutlives(tcx.anonymize_late_bound_regions(data)) - } - - ty::Predicate::Projection(ref data) => { - ty::Predicate::Projection(tcx.anonymize_late_bound_regions(data)) - } - - ty::Predicate::WellFormed(data) => ty::Predicate::WellFormed(data), - - ty::Predicate::ObjectSafe(data) => ty::Predicate::ObjectSafe(data), - - ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) => { - ty::Predicate::ClosureKind(closure_def_id, closure_substs, kind) - } - - ty::Predicate::Subtype(ref data) => { - ty::Predicate::Subtype(tcx.anonymize_late_bound_regions(data)) - } - - ty::Predicate::ConstEvaluatable(def_id, substs) => { - ty::Predicate::ConstEvaluatable(def_id, substs) - } - } -} - -struct PredicateSet<'tcx> { - tcx: TyCtxt<'tcx>, - set: FxHashSet<ty::Predicate<'tcx>>, -} - -impl PredicateSet<'tcx> { - fn new(tcx: TyCtxt<'tcx>) -> Self { - Self { tcx, set: Default::default() } - } - - fn insert(&mut self, pred: &ty::Predicate<'tcx>) -> bool { - // We have to be careful here because we want - // - // for<'a> Foo<&'a int> - // - // and - // - // for<'b> Foo<&'b int> - // - // to be considered equivalent. So normalize all late-bound - // regions before we throw things into the underlying set. - self.set.insert(anonymize_predicate(self.tcx, pred)) - } -} - -impl<T: AsRef<ty::Predicate<'tcx>>> Extend<T> for PredicateSet<'tcx> { - fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { - for pred in iter { - self.insert(pred.as_ref()); - } - } -} - -/////////////////////////////////////////////////////////////////////////// -// `Elaboration` iterator -/////////////////////////////////////////////////////////////////////////// - -/// "Elaboration" is the process of identifying all the predicates that -/// are implied by a source predicate. Currently, this basically means -/// walking the "supertraits" and other similar assumptions. For example, -/// 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<ty::Predicate<'tcx>>, - visited: PredicateSet<'tcx>, -} - -pub fn elaborate_trait_ref<'tcx>( - tcx: TyCtxt<'tcx>, - trait_ref: ty::PolyTraitRef<'tcx>, -) -> Elaborator<'tcx> { - elaborate_predicates(tcx, vec![trait_ref.without_const().to_predicate()]) -} - -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()).collect(); - elaborate_predicates(tcx, predicates) -} - -pub fn elaborate_predicates<'tcx>( - tcx: TyCtxt<'tcx>, - mut predicates: Vec<ty::Predicate<'tcx>>, -) -> Elaborator<'tcx> { - let mut visited = PredicateSet::new(tcx); - predicates.retain(|pred| visited.insert(pred)); - Elaborator { stack: predicates, visited } -} - -impl Elaborator<'tcx> { - pub fn filter_to_traits(self) -> FilterToTraits<Self> { - FilterToTraits::new(self) - } - - fn elaborate(&mut self, predicate: &ty::Predicate<'tcx>) { - let tcx = self.visited.tcx; - match *predicate { - ty::Predicate::Trait(ref data, _) => { - // Get predicates declared on the trait. - let predicates = tcx.super_predicates_of(data.def_id()); - - let predicates = predicates - .predicates - .iter() - .map(|(pred, _)| pred.subst_supertrait(tcx, &data.to_poly_trait_ref())); - debug!("super_predicates: data={:?} predicates={:?}", data, predicates.clone()); - - // 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; - let predicates = predicates.filter(|pred| visited.insert(pred)); - - self.stack.extend(predicates); - } - ty::Predicate::WellFormed(..) => { - // Currently, we do not elaborate WF predicates, - // although we easily could. - } - ty::Predicate::ObjectSafe(..) => { - // Currently, we do not elaborate object-safe - // predicates. - } - ty::Predicate::Subtype(..) => { - // Currently, we do not "elaborate" predicates like `X <: Y`, - // though conceivably we might. - } - ty::Predicate::Projection(..) => { - // Nothing to elaborate in a projection predicate. - } - ty::Predicate::ClosureKind(..) => { - // Nothing to elaborate when waiting for a closure's kind to be inferred. - } - ty::Predicate::ConstEvaluatable(..) => { - // Currently, we do not elaborate const-evaluatable - // predicates. - } - ty::Predicate::RegionOutlives(..) => { - // Nothing to elaborate from `'a: 'b`. - } - ty::Predicate::TypeOutlives(ref data) => { - // We know that `T: 'a` for some type `T`. We can - // often elaborate this. For example, if we know that - // `[U]: 'a`, that implies that `U: 'a`. Similarly, if - // we know `&'a U: 'b`, then we know that `'a: 'b` and - // `U: 'b`. - // - // We can basically ignore bound regions here. So for - // example `for<'c> Foo<'a,'c>: 'b` can be elaborated to - // `'a: 'b`. - - // Ignore `for<'a> T: 'a` -- we might in the future - // consider this as evidence that `T: 'static`, but - // I'm a bit wary of such constructions and so for now - // I want to be conservative. --nmatsakis - let ty_max = data.skip_binder().0; - let r_min = data.skip_binder().1; - if r_min.is_late_bound() { - return; - } - - let visited = &mut self.visited; - let mut components = smallvec![]; - tcx.push_outlives_components(ty_max, &mut components); - self.stack.extend( - components - .into_iter() - .filter_map(|component| match component { - Component::Region(r) => { - if r.is_late_bound() { - None - } else { - Some(ty::Predicate::RegionOutlives(ty::Binder::dummy( - ty::OutlivesPredicate(r, r_min), - ))) - } - } - - Component::Param(p) => { - let ty = tcx.mk_ty_param(p.index, p.name); - Some(ty::Predicate::TypeOutlives(ty::Binder::dummy( - ty::OutlivesPredicate(ty, r_min), - ))) - } - - Component::UnresolvedInferenceVariable(_) => None, - - Component::Projection(_) | Component::EscapingProjection(_) => { - // We can probably do more here. This - // corresponds to a case like `<T as - // Foo<'a>>::U: 'b`. - None - } - }) - .filter(|p| visited.insert(p)), - ); - } - } - } -} - -impl Iterator for Elaborator<'tcx> { - type Item = ty::Predicate<'tcx>; - - fn size_hint(&self) -> (usize, Option<usize>) { - (self.stack.len(), None) - } - - fn next(&mut self) -> Option<ty::Predicate<'tcx>> { - // Extract next item from top-most stack frame, if any. - if let Some(pred) = self.stack.pop() { - self.elaborate(&pred); - Some(pred) - } else { - 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() -} - -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() -} +pub use rustc_infer::traits::util::*; /////////////////////////////////////////////////////////////////////////// // `TraitAliasExpander` iterator @@ -450,40 +191,6 @@ impl Iterator for SupertraitDefIds<'tcx> { // Other /////////////////////////////////////////////////////////////////////////// -/// 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 = ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> { - type Item = ty::PolyTraitRef<'tcx>; - - fn next(&mut self) -> Option<ty::PolyTraitRef<'tcx>> { - while let Some(pred) = self.base_iterator.next() { - if let ty::Predicate::Trait(data, _) = pred { - return Some(data.to_poly_trait_ref()); - } - } - None - } - - fn size_hint(&self) -> (usize, Option<usize>) { - let (_, upper) = self.base_iterator.size_hint(); - (0, upper) - } -} - -/////////////////////////////////////////////////////////////////////////// -// Other -/////////////////////////////////////////////////////////////////////////// - /// Instantiate all bound parameters of the impl with the given substs, /// returning the resulting trait ref and all obligations that arise. /// The obligations are closed under normalization. |