diff options
Diffstat (limited to 'src/librustc_infer/traits/util.rs')
| -rw-r--r-- | src/librustc_infer/traits/util.rs | 461 |
1 files changed, 56 insertions, 405 deletions
diff --git a/src/librustc_infer/traits/util.rs b/src/librustc_infer/traits/util.rs index 1dca01b3468..55bea57f3e2 100644 --- a/src/librustc_infer/traits/util.rs +++ b/src/librustc_infer/traits/util.rs @@ -1,18 +1,15 @@ -use rustc_errors::DiagnosticBuilder; -use rustc_span::Span; use smallvec::smallvec; -use smallvec::SmallVec; -use rustc::ty::outlives::Component; -use rustc::ty::subst::{GenericArg, Subst, SubstsRef}; -use rustc::ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, WithConstness}; +use crate::traits::{Obligation, ObligationCause, PredicateObligation}; use rustc_data_structures::fx::FxHashSet; -use rustc_hir as hir; -use rustc_hir::def_id::DefId; - -use super::{Normalized, Obligation, ObligationCause, PredicateObligation, SelectionContext}; +use rustc_middle::ty::outlives::Component; +use rustc_middle::ty::{self, ToPolyTraitRef, ToPredicate, TyCtxt, WithConstness}; +use rustc_span::Span; -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) @@ -55,7 +52,7 @@ struct PredicateSet<'tcx> { impl PredicateSet<'tcx> { fn new(tcx: TyCtxt<'tcx>) -> Self { - Self { tcx: tcx, set: Default::default() } + Self { tcx, set: Default::default() } } fn insert(&mut self, pred: &ty::Predicate<'tcx>) -> bool { @@ -92,7 +89,7 @@ impl<T: AsRef<ty::Predicate<'tcx>>> Extend<T> for PredicateSet<'tcx> { /// 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>>, + stack: Vec<PredicateObligation<'tcx>>, visited: PredicateSet<'tcx>, } @@ -100,24 +97,44 @@ 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()]) + elaborate_predicates(tcx, std::iter::once(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(); + let predicates = trait_refs.map(|trait_ref| trait_ref.without_const().to_predicate()); elaborate_predicates(tcx, predicates) } pub fn elaborate_predicates<'tcx>( tcx: TyCtxt<'tcx>, - mut predicates: Vec<ty::Predicate<'tcx>>, + predicates: impl Iterator<Item = ty::Predicate<'tcx>>, +) -> Elaborator<'tcx> { + let obligations = + predicates.into_iter().map(|predicate| predicate_obligation(predicate, None)).collect(); + elaborate_obligations(tcx, obligations) +} + +pub fn elaborate_obligations<'tcx>( + tcx: TyCtxt<'tcx>, + mut obligations: Vec<PredicateObligation<'tcx>>, ) -> Elaborator<'tcx> { let mut visited = PredicateSet::new(tcx); - predicates.retain(|pred| visited.insert(pred)); - Elaborator { stack: predicates, visited } + obligations.retain(|obligation| visited.insert(&obligation.predicate)); + Elaborator { stack: obligations, visited } +} + +fn predicate_obligation<'tcx>( + predicate: ty::Predicate<'tcx>, + span: Option<Span>, +) -> PredicateObligation<'tcx> { + let mut cause = ObligationCause::dummy(); + if let Some(span) = span { + cause.span = span; + } + Obligation { cause, param_env: ty::ParamEnv::empty(), recursion_depth: 0, predicate } } impl Elaborator<'tcx> { @@ -125,27 +142,29 @@ impl Elaborator<'tcx> { FilterToTraits::new(self) } - fn elaborate(&mut self, predicate: &ty::Predicate<'tcx>) { + fn elaborate(&mut self, obligation: &PredicateObligation<'tcx>) { let tcx = self.visited.tcx; - match *predicate { + match obligation.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()); + let obligations = predicates.predicates.into_iter().map(|(pred, span)| { + predicate_obligation( + pred.subst_supertrait(tcx, &data.to_poly_trait_ref()), + Some(*span), + ) + }); + debug!("super_predicates: data={:?}", data); // 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)); + let obligations = obligations.filter(|o| visited.insert(&o.predicate)); - self.stack.extend(predicates); + self.stack.extend(obligations); } ty::Predicate::WellFormed(..) => { // Currently, we do not elaborate WF predicates, @@ -226,7 +245,8 @@ impl Elaborator<'tcx> { None } }) - .filter(|p| visited.insert(p)), + .filter(|p| visited.insert(p)) + .map(|p| predicate_obligation(p, None)), ); } } @@ -234,17 +254,17 @@ impl Elaborator<'tcx> { } impl Iterator for Elaborator<'tcx> { - type Item = ty::Predicate<'tcx>; + type Item = PredicateObligation<'tcx>; fn size_hint(&self) -> (usize, Option<usize>) { (self.stack.len(), None) } - fn next(&mut self) -> Option<ty::Predicate<'tcx>> { + fn next(&mut self) -> Option<Self::Item> { // Extract next item from top-most stack frame, if any. - if let Some(pred) = self.stack.pop() { - self.elaborate(&pred); - Some(pred) + if let Some(obligation) = self.stack.pop() { + self.elaborate(&obligation); + Some(obligation) } else { None } @@ -272,182 +292,6 @@ pub fn transitive_bounds<'tcx>( } /////////////////////////////////////////////////////////////////////////// -// `TraitAliasExpander` iterator -/////////////////////////////////////////////////////////////////////////// - -/// "Trait alias expansion" is the process of expanding a sequence of trait -/// references into another sequence by transitively following all trait -/// aliases. e.g. If you have bounds like `Foo + Send`, a trait alias -/// `trait Foo = Bar + Sync;`, and another trait alias -/// `trait Bar = Read + Write`, then the bounds would expand to -/// `Read + Write + Sync + Send`. -/// Expansion is done via a DFS (depth-first search), and the `visited` field -/// is used to avoid cycles. -pub struct TraitAliasExpander<'tcx> { - tcx: TyCtxt<'tcx>, - stack: Vec<TraitAliasExpansionInfo<'tcx>>, -} - -/// Stores information about the expansion of a trait via a path of zero or more trait aliases. -#[derive(Debug, Clone)] -pub struct TraitAliasExpansionInfo<'tcx> { - pub path: SmallVec<[(ty::PolyTraitRef<'tcx>, Span); 4]>, -} - -impl<'tcx> TraitAliasExpansionInfo<'tcx> { - fn new(trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self { - Self { path: smallvec![(trait_ref, span)] } - } - - /// Adds diagnostic labels to `diag` for the expansion path of a trait through all intermediate - /// trait aliases. - pub fn label_with_exp_info( - &self, - diag: &mut DiagnosticBuilder<'_>, - top_label: &str, - use_desc: &str, - ) { - diag.span_label(self.top().1, top_label); - if self.path.len() > 1 { - for (_, sp) in self.path.iter().rev().skip(1).take(self.path.len() - 2) { - diag.span_label(*sp, format!("referenced here ({})", use_desc)); - } - } - diag.span_label( - self.bottom().1, - format!("trait alias used in trait object type ({})", use_desc), - ); - } - - pub fn trait_ref(&self) -> &ty::PolyTraitRef<'tcx> { - &self.top().0 - } - - pub fn top(&self) -> &(ty::PolyTraitRef<'tcx>, Span) { - self.path.last().unwrap() - } - - pub fn bottom(&self) -> &(ty::PolyTraitRef<'tcx>, Span) { - self.path.first().unwrap() - } - - fn clone_and_push(&self, trait_ref: ty::PolyTraitRef<'tcx>, span: Span) -> Self { - let mut path = self.path.clone(); - path.push((trait_ref, span)); - - Self { path } - } -} - -pub fn expand_trait_aliases<'tcx>( - tcx: TyCtxt<'tcx>, - trait_refs: impl IntoIterator<Item = (ty::PolyTraitRef<'tcx>, Span)>, -) -> TraitAliasExpander<'tcx> { - let items: Vec<_> = trait_refs - .into_iter() - .map(|(trait_ref, span)| TraitAliasExpansionInfo::new(trait_ref, span)) - .collect(); - TraitAliasExpander { tcx, stack: items } -} - -impl<'tcx> TraitAliasExpander<'tcx> { - /// If `item` is a trait alias and its predicate has not yet been visited, then expands `item` - /// to the definition, pushes the resulting expansion onto `self.stack`, and returns `false`. - /// Otherwise, immediately returns `true` if `item` is a regular trait, or `false` if it is a - /// trait alias. - /// The return value indicates whether `item` should be yielded to the user. - fn expand(&mut self, item: &TraitAliasExpansionInfo<'tcx>) -> bool { - let tcx = self.tcx; - let trait_ref = item.trait_ref(); - let pred = trait_ref.without_const().to_predicate(); - - debug!("expand_trait_aliases: trait_ref={:?}", trait_ref); - - // Don't recurse if this bound is not a trait alias. - let is_alias = tcx.is_trait_alias(trait_ref.def_id()); - if !is_alias { - return true; - } - - // Don't recurse if this trait alias is already on the stack for the DFS search. - let anon_pred = anonymize_predicate(tcx, &pred); - if item.path.iter().rev().skip(1).any(|(tr, _)| { - anonymize_predicate(tcx, &tr.without_const().to_predicate()) == anon_pred - }) { - return false; - } - - // Get components of trait alias. - let predicates = tcx.super_predicates_of(trait_ref.def_id()); - - let items = predicates.predicates.iter().rev().filter_map(|(pred, span)| { - pred.subst_supertrait(tcx, &trait_ref) - .to_opt_poly_trait_ref() - .map(|trait_ref| item.clone_and_push(trait_ref, *span)) - }); - debug!("expand_trait_aliases: items={:?}", items.clone()); - - self.stack.extend(items); - - false - } -} - -impl<'tcx> Iterator for TraitAliasExpander<'tcx> { - type Item = TraitAliasExpansionInfo<'tcx>; - - fn size_hint(&self) -> (usize, Option<usize>) { - (self.stack.len(), None) - } - - fn next(&mut self) -> Option<TraitAliasExpansionInfo<'tcx>> { - while let Some(item) = self.stack.pop() { - if self.expand(&item) { - return Some(item); - } - } - None - } -} - -/////////////////////////////////////////////////////////////////////////// -// Iterator over def-IDs of supertraits -/////////////////////////////////////////////////////////////////////////// - -pub struct SupertraitDefIds<'tcx> { - tcx: TyCtxt<'tcx>, - stack: Vec<DefId>, - visited: FxHashSet<DefId>, -} - -pub fn supertrait_def_ids(tcx: TyCtxt<'_>, trait_def_id: DefId) -> SupertraitDefIds<'_> { - SupertraitDefIds { - tcx, - stack: vec![trait_def_id], - visited: Some(trait_def_id).into_iter().collect(), - } -} - -impl Iterator for SupertraitDefIds<'tcx> { - type Item = DefId; - - fn next(&mut self) -> Option<DefId> { - let def_id = self.stack.pop()?; - let predicates = self.tcx.super_predicates_of(def_id); - let visited = &mut self.visited; - self.stack.extend( - predicates - .predicates - .iter() - .filter_map(|(pred, _)| pred.to_opt_poly_trait_ref()) - .map(|trait_ref| trait_ref.def_id()) - .filter(|&super_def_id| visited.insert(super_def_id)), - ); - Some(def_id) - } -} - -/////////////////////////////////////////////////////////////////////////// // Other /////////////////////////////////////////////////////////////////////////// @@ -463,12 +307,12 @@ impl<I> FilterToTraits<I> { } } -impl<'tcx, I: Iterator<Item = ty::Predicate<'tcx>>> Iterator for FilterToTraits<I> { +impl<'tcx, I: Iterator<Item = PredicateObligation<'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 { + while let Some(obligation) = self.base_iterator.next() { + if let ty::Predicate::Trait(data, _) = obligation.predicate { return Some(data.to_poly_trait_ref()); } } @@ -480,196 +324,3 @@ impl<'tcx, I: Iterator<Item = ty::Predicate<'tcx>>> Iterator for FilterToTraits< (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. -pub fn impl_trait_ref_and_oblig<'a, 'tcx>( - selcx: &mut SelectionContext<'a, 'tcx>, - param_env: ty::ParamEnv<'tcx>, - impl_def_id: DefId, - impl_substs: SubstsRef<'tcx>, -) -> (ty::TraitRef<'tcx>, Vec<PredicateObligation<'tcx>>) { - let impl_trait_ref = selcx.tcx().impl_trait_ref(impl_def_id).unwrap(); - let impl_trait_ref = impl_trait_ref.subst(selcx.tcx(), impl_substs); - let Normalized { value: impl_trait_ref, obligations: normalization_obligations1 } = - super::normalize(selcx, param_env, ObligationCause::dummy(), &impl_trait_ref); - - let predicates = selcx.tcx().predicates_of(impl_def_id); - let predicates = predicates.instantiate(selcx.tcx(), impl_substs); - let Normalized { value: predicates, obligations: normalization_obligations2 } = - super::normalize(selcx, param_env, ObligationCause::dummy(), &predicates); - let impl_obligations = - predicates_for_generics(ObligationCause::dummy(), 0, param_env, &predicates); - - let impl_obligations: Vec<_> = impl_obligations - .into_iter() - .chain(normalization_obligations1) - .chain(normalization_obligations2) - .collect(); - - (impl_trait_ref, impl_obligations) -} - -/// See [`super::obligations_for_generics`]. -pub fn predicates_for_generics<'tcx>( - cause: ObligationCause<'tcx>, - recursion_depth: usize, - param_env: ty::ParamEnv<'tcx>, - generic_bounds: &ty::InstantiatedPredicates<'tcx>, -) -> Vec<PredicateObligation<'tcx>> { - debug!("predicates_for_generics(generic_bounds={:?})", generic_bounds); - - generic_bounds - .predicates - .iter() - .map(|&predicate| Obligation { - cause: cause.clone(), - recursion_depth, - param_env, - predicate, - }) - .collect() -} - -pub fn predicate_for_trait_ref<'tcx>( - cause: ObligationCause<'tcx>, - param_env: ty::ParamEnv<'tcx>, - trait_ref: ty::TraitRef<'tcx>, - recursion_depth: usize, -) -> PredicateObligation<'tcx> { - Obligation { - cause, - param_env, - recursion_depth, - predicate: trait_ref.without_const().to_predicate(), - } -} - -pub fn predicate_for_trait_def( - tcx: TyCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, - cause: ObligationCause<'tcx>, - trait_def_id: DefId, - recursion_depth: usize, - self_ty: Ty<'tcx>, - params: &[GenericArg<'tcx>], -) -> PredicateObligation<'tcx> { - let trait_ref = - ty::TraitRef { def_id: trait_def_id, substs: tcx.mk_substs_trait(self_ty, params) }; - predicate_for_trait_ref(cause, param_env, trait_ref, recursion_depth) -} - -/// Casts a trait reference into a reference to one of its super -/// traits; returns `None` if `target_trait_def_id` is not a -/// supertrait. -pub fn upcast_choices( - tcx: TyCtxt<'tcx>, - source_trait_ref: ty::PolyTraitRef<'tcx>, - target_trait_def_id: DefId, -) -> Vec<ty::PolyTraitRef<'tcx>> { - if source_trait_ref.def_id() == target_trait_def_id { - return vec![source_trait_ref]; // Shortcut the most common case. - } - - supertraits(tcx, source_trait_ref).filter(|r| r.def_id() == target_trait_def_id).collect() -} - -/// Given a trait `trait_ref`, returns the number of vtable entries -/// that come from `trait_ref`, excluding its supertraits. Used in -/// computing the vtable base for an upcast trait of a trait object. -pub fn count_own_vtable_entries(tcx: TyCtxt<'tcx>, trait_ref: ty::PolyTraitRef<'tcx>) -> usize { - let mut entries = 0; - // Count number of methods and add them to the total offset. - // Skip over associated types and constants. - for trait_item in tcx.associated_items(trait_ref.def_id()).in_definition_order() { - if trait_item.kind == ty::AssocKind::Method { - entries += 1; - } - } - entries -} - -/// Given an upcast trait object described by `object`, returns the -/// index of the method `method_def_id` (which should be part of -/// `object.upcast_trait_ref`) within the vtable for `object`. -pub fn get_vtable_index_of_object_method<N>( - tcx: TyCtxt<'tcx>, - object: &super::VtableObjectData<'tcx, N>, - method_def_id: DefId, -) -> usize { - // Count number of methods preceding the one we are selecting and - // add them to the total offset. - // Skip over associated types and constants. - let mut entries = object.vtable_base; - for trait_item in tcx.associated_items(object.upcast_trait_ref.def_id()).in_definition_order() { - if trait_item.def_id == method_def_id { - // The item with the ID we were given really ought to be a method. - assert_eq!(trait_item.kind, ty::AssocKind::Method); - return entries; - } - if trait_item.kind == ty::AssocKind::Method { - entries += 1; - } - } - - bug!("get_vtable_index_of_object_method: {:?} was not found", method_def_id); -} - -pub fn closure_trait_ref_and_return_type( - tcx: TyCtxt<'tcx>, - fn_trait_def_id: DefId, - self_ty: Ty<'tcx>, - sig: ty::PolyFnSig<'tcx>, - tuple_arguments: TupleArgumentsFlag, -) -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>)> { - let arguments_tuple = match tuple_arguments { - TupleArgumentsFlag::No => sig.skip_binder().inputs()[0], - TupleArgumentsFlag::Yes => tcx.intern_tup(sig.skip_binder().inputs()), - }; - let trait_ref = ty::TraitRef { - def_id: fn_trait_def_id, - substs: tcx.mk_substs_trait(self_ty, &[arguments_tuple.into()]), - }; - ty::Binder::bind((trait_ref, sig.skip_binder().output())) -} - -pub fn generator_trait_ref_and_outputs( - tcx: TyCtxt<'tcx>, - fn_trait_def_id: DefId, - self_ty: Ty<'tcx>, - sig: ty::PolyGenSig<'tcx>, -) -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>, Ty<'tcx>)> { - let trait_ref = ty::TraitRef { - def_id: fn_trait_def_id, - substs: tcx.mk_substs_trait(self_ty, &[sig.skip_binder().resume_ty.into()]), - }; - ty::Binder::bind((trait_ref, sig.skip_binder().yield_ty, sig.skip_binder().return_ty)) -} - -pub fn impl_is_default(tcx: TyCtxt<'_>, node_item_def_id: DefId) -> bool { - match tcx.hir().as_local_hir_id(node_item_def_id) { - Some(hir_id) => { - let item = tcx.hir().expect_item(hir_id); - if let hir::ItemKind::Impl { defaultness, .. } = item.kind { - defaultness.is_default() - } else { - false - } - } - None => tcx.impl_defaultness(node_item_def_id).is_default(), - } -} - -pub fn impl_item_is_final(tcx: TyCtxt<'_>, assoc_item: &ty::AssocItem) -> bool { - assoc_item.defaultness.is_final() && !impl_is_default(tcx, assoc_item.container.id()) -} - -pub enum TupleArgumentsFlag { - Yes, - No, -} |