diff options
Diffstat (limited to 'compiler')
7 files changed, 199 insertions, 291 deletions
diff --git a/compiler/rustc_hir_analysis/src/hir_ty_lowering/dyn_compatibility.rs b/compiler/rustc_hir_analysis/src/hir_ty_lowering/dyn_compatibility.rs index 71a5727ed6c..72ad190df7e 100644 --- a/compiler/rustc_hir_analysis/src/hir_ty_lowering/dyn_compatibility.rs +++ b/compiler/rustc_hir_analysis/src/hir_ty_lowering/dyn_compatibility.rs @@ -4,13 +4,12 @@ use rustc_errors::struct_span_code_err; use rustc_hir as hir; use rustc_hir::def::{DefKind, Res}; use rustc_lint_defs::builtin::UNUSED_ASSOCIATED_TYPE_BOUNDS; -use rustc_middle::span_bug; use rustc_middle::ty::fold::BottomUpFolder; use rustc_middle::ty::{ self, DynKind, ExistentialPredicateStableCmpExt as _, Ty, TyCtxt, TypeFoldable, TypeVisitableExt, Upcast, }; -use rustc_span::{DUMMY_SP, ErrorGuaranteed, Span}; +use rustc_span::{ErrorGuaranteed, Span}; use rustc_trait_selection::error_reporting::traits::report_dyn_incompatibility; use rustc_trait_selection::traits::{self, hir_ty_lowering_dyn_compatibility_violations}; use rustc_type_ir::elaborate::ClauseWithSupertraitSpan; @@ -30,16 +29,16 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { &self, span: Span, hir_id: hir::HirId, - hir_trait_bounds: &[hir::PolyTraitRef<'tcx>], + hir_bounds: &[hir::PolyTraitRef<'tcx>], lifetime: &hir::Lifetime, representation: DynKind, ) -> Ty<'tcx> { let tcx = self.tcx(); + let dummy_self = tcx.types.trait_object_dummy_self; - let mut bounds = Bounds::default(); + let mut user_written_bounds = Bounds::default(); let mut potential_assoc_types = Vec::new(); - let dummy_self = self.tcx().types.trait_object_dummy_self; - for trait_bound in hir_trait_bounds.iter().rev() { + for trait_bound in hir_bounds.iter() { if let hir::BoundPolarity::Maybe(_) = trait_bound.modifiers.polarity { continue; } @@ -53,92 +52,67 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { hir::BoundConstness::Never, hir::BoundPolarity::Positive, dummy_self, - &mut bounds, + &mut user_written_bounds, PredicateFilter::SelfOnly, ) { potential_assoc_types.extend(cur_potential_assoc_types); } } - let mut trait_bounds = vec![]; - let mut projection_bounds = vec![]; - for (pred, span) in bounds.clauses() { - let bound_pred = pred.kind(); - match bound_pred.skip_binder() { - ty::ClauseKind::Trait(trait_pred) => { - assert_eq!(trait_pred.polarity, ty::PredicatePolarity::Positive); - trait_bounds.push((bound_pred.rebind(trait_pred.trait_ref), span)); - } - ty::ClauseKind::Projection(proj) => { - projection_bounds.push((bound_pred.rebind(proj), span)); - } - ty::ClauseKind::TypeOutlives(_) => { - // Do nothing, we deal with regions separately - } - ty::ClauseKind::RegionOutlives(_) - | ty::ClauseKind::ConstArgHasType(..) - | ty::ClauseKind::WellFormed(_) - | ty::ClauseKind::ConstEvaluatable(_) - | ty::ClauseKind::HostEffect(..) => { - span_bug!(span, "did not expect {pred} clause in object bounds"); - } - } - } - - // Expand trait aliases recursively and check that only one regular (non-auto) trait - // is used and no 'maybe' bounds are used. - let expanded_traits = - traits::expand_trait_aliases(tcx, trait_bounds.iter().map(|&(a, b)| (a, b))); - - let (mut auto_traits, regular_traits): (Vec<_>, Vec<_>) = - expanded_traits.partition(|i| tcx.trait_is_auto(i.trait_ref().def_id())); + let (trait_bounds, mut projection_bounds) = + traits::expand_trait_aliases(tcx, user_written_bounds.clauses()); + let (regular_traits, mut auto_traits): (Vec<_>, Vec<_>) = trait_bounds + .into_iter() + .partition(|(trait_ref, _)| !tcx.trait_is_auto(trait_ref.def_id())); + // We don't support empty trait objects. + if regular_traits.is_empty() && auto_traits.is_empty() { + let guar = + self.report_trait_object_with_no_traits_error(span, user_written_bounds.clauses()); + return Ty::new_error(tcx, guar); + } // We don't support >1 principal if regular_traits.len() > 1 { let guar = self.report_trait_object_addition_traits_error(®ular_traits); return Ty::new_error(tcx, guar); } - // We don't support empty trait objects. - if regular_traits.is_empty() && auto_traits.is_empty() { - let guar = self.report_trait_object_with_no_traits_error(span, &trait_bounds); - return Ty::new_error(tcx, guar); - } // Don't create a dyn trait if we have errors in the principal. - if let Err(guar) = trait_bounds.error_reported() { + if let Err(guar) = regular_traits.error_reported() { return Ty::new_error(tcx, guar); } // Check that there are no gross dyn-compatibility violations; // most importantly, that the supertraits don't contain `Self`, // to avoid ICEs. - for item in ®ular_traits { - let violations = - hir_ty_lowering_dyn_compatibility_violations(tcx, item.trait_ref().def_id()); - if !violations.is_empty() { - let reported = report_dyn_incompatibility( - tcx, - span, - Some(hir_id), - item.trait_ref().def_id(), - &violations, - ) - .emit(); - return Ty::new_error(tcx, reported); + for (clause, span) in user_written_bounds.clauses() { + if let Some(trait_pred) = clause.as_trait_clause() { + let violations = + hir_ty_lowering_dyn_compatibility_violations(tcx, trait_pred.def_id()); + if !violations.is_empty() { + let reported = report_dyn_incompatibility( + tcx, + span, + Some(hir_id), + trait_pred.def_id(), + &violations, + ) + .emit(); + return Ty::new_error(tcx, reported); + } } } - let mut needed_associated_types = FxIndexSet::default(); - - let principal_span = regular_traits.first().map_or(DUMMY_SP, |info| info.bottom().1); - let regular_traits_refs_spans = trait_bounds - .into_iter() - .filter(|(trait_ref, _)| !tcx.trait_is_auto(trait_ref.def_id())); + let principal_trait = regular_traits.into_iter().next(); - for (base_trait_ref, original_span) in regular_traits_refs_spans { - let base_pred: ty::Predicate<'tcx> = base_trait_ref.upcast(tcx); + let mut needed_associated_types = FxIndexSet::default(); + if let Some((principal_trait, spans)) = &principal_trait { + let pred: ty::Predicate<'tcx> = (*principal_trait).upcast(tcx); for ClauseWithSupertraitSpan { pred, supertrait_span } in - traits::elaborate(tcx, [ClauseWithSupertraitSpan::new(base_pred, original_span)]) - .filter_only_self() + traits::elaborate(tcx, [ClauseWithSupertraitSpan::new( + pred, + *spans.last().unwrap(), + )]) + .filter_only_self() { debug!("observing object predicate `{pred:?}`"); @@ -179,7 +153,7 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { // } // ``` // - // Here, the user could theoretically write `dyn MyTrait<Output = X>`, + // Here, the user could theoretically write `dyn MyTrait<MyOutput = X>`, // but actually supporting that would "expand" to an infinitely-long type // `fix $ τ → dyn MyTrait<MyOutput = X, Output = <τ as MyTrait>::MyOutput`. // @@ -188,12 +162,12 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { // the discussion in #56288 for alternatives. if !references_self { // Include projections defined on supertraits. - projection_bounds.push((pred, original_span)); + projection_bounds.push((pred, supertrait_span)); } self.check_elaborated_projection_mentions_input_lifetimes( pred, - original_span, + *spans.first().unwrap(), supertrait_span, ); } @@ -202,11 +176,13 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { } } - // `dyn Trait<Assoc = Foo>` desugars to (not Rust syntax) `dyn Trait where <Self as Trait>::Assoc = Foo`. - // So every `Projection` clause is an `Assoc = Foo` bound. `associated_types` contains all associated - // types's `DefId`, so the following loop removes all the `DefIds` of the associated types that have a - // corresponding `Projection` clause - for (projection_bound, span) in &projection_bounds { + // `dyn Trait<Assoc = Foo>` desugars to (not Rust syntax) `dyn Trait where + // <Self as Trait>::Assoc = Foo`. So every `Projection` clause is an + // `Assoc = Foo` bound. `needed_associated_types` contains all associated + // types that we expect to be provided by the user, so the following loop + // removes all the associated types that have a corresponding `Projection` + // clause, either from expanding trait aliases or written by the user. + for &(projection_bound, span) in &projection_bounds { let def_id = projection_bound.item_def_id(); let trait_ref = tcx.anonymize_bound_vars( projection_bound.map_bound(|p| p.projection_term.trait_ref(tcx)), @@ -216,17 +192,17 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { tcx.emit_node_span_lint( UNUSED_ASSOCIATED_TYPE_BOUNDS, hir_id, - *span, - crate::errors::UnusedAssociatedTypeBounds { span: *span }, + span, + crate::errors::UnusedAssociatedTypeBounds { span }, ); } } if let Err(guar) = self.check_for_required_assoc_tys( - principal_span, + principal_trait.as_ref().map_or(smallvec![], |(_, spans)| spans.clone()), needed_associated_types, potential_assoc_types, - hir_trait_bounds, + hir_bounds, ) { return Ty::new_error(tcx, guar); } @@ -236,32 +212,36 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { // We remove duplicates by inserting into a `FxHashSet` to avoid re-ordering // the bounds let mut duplicates = FxHashSet::default(); - auto_traits.retain(|i| duplicates.insert(i.trait_ref().def_id())); - debug!(?regular_traits); + auto_traits.retain(|(trait_pred, _)| duplicates.insert(trait_pred.def_id())); + + debug!(?principal_trait); debug!(?auto_traits); // Erase the `dummy_self` (`trait_object_dummy_self`) used above. - let existential_trait_refs = regular_traits.iter().map(|i| { - i.trait_ref().map_bound(|trait_ref: ty::TraitRef<'tcx>| { + let principal_trait_ref = principal_trait.map(|(trait_pred, spans)| { + trait_pred.map_bound(|trait_pred| { + let trait_ref = trait_pred.trait_ref; + assert_eq!(trait_pred.polarity, ty::PredicatePolarity::Positive); assert_eq!(trait_ref.self_ty(), dummy_self); + let span = *spans.first().unwrap(); + // Verify that `dummy_self` did not leak inside default type parameters. This // could not be done at path creation, since we need to see through trait aliases. let mut missing_type_params = vec![]; - let mut references_self = false; let generics = tcx.generics_of(trait_ref.def_id); let args: Vec<_> = trait_ref .args .iter() .enumerate() - .skip(1) // Remove `Self` for `ExistentialPredicate`. + // Skip `Self` + .skip(1) .map(|(index, arg)| { if arg == dummy_self.into() { let param = &generics.own_params[index]; missing_type_params.push(param.name); Ty::new_misc_error(tcx).into() } else if arg.walk().any(|arg| arg == dummy_self.into()) { - references_self = true; let guar = self.dcx().span_delayed_bug( span, "trait object trait bounds reference `Self`", @@ -273,8 +253,7 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { }) .collect(); - let span = i.bottom().1; - let empty_generic_args = hir_trait_bounds.iter().any(|hir_bound| { + let empty_generic_args = hir_bounds.iter().any(|hir_bound| { hir_bound.trait_ref.path.res == Res::Def(DefKind::Trait, trait_ref.def_id) && hir_bound.span.contains(span) }); @@ -285,26 +264,11 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { empty_generic_args, ); - if references_self { - let def_id = i.bottom().0.def_id(); - struct_span_code_err!( - self.dcx(), - i.bottom().1, - E0038, - "the {} `{}` cannot be made into an object", - tcx.def_descr(def_id), - tcx.item_name(def_id), - ) - .with_note( - rustc_middle::traits::DynCompatibilityViolation::SupertraitSelf( - smallvec![], - ) - .error_msg(), - ) - .emit(); - } - - ty::ExistentialTraitRef::new(tcx, trait_ref.def_id, args) + ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef::new( + tcx, + trait_ref.def_id, + args, + )) }) }); @@ -327,21 +291,24 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { b.projection_term = replace_dummy_self_with_error(tcx, b.projection_term, guar); } - ty::ExistentialProjection::erase_self_ty(tcx, b) + ty::ExistentialPredicate::Projection(ty::ExistentialProjection::erase_self_ty( + tcx, b, + )) }) }); - let regular_trait_predicates = existential_trait_refs - .map(|trait_ref| trait_ref.map_bound(ty::ExistentialPredicate::Trait)); - let auto_trait_predicates = auto_traits.into_iter().map(|trait_ref| { - ty::Binder::dummy(ty::ExistentialPredicate::AutoTrait(trait_ref.trait_ref().def_id())) + let auto_trait_predicates = auto_traits.into_iter().map(|(trait_pred, _)| { + assert_eq!(trait_pred.polarity(), ty::PredicatePolarity::Positive); + assert_eq!(trait_pred.self_ty().skip_binder(), dummy_self); + + ty::Binder::dummy(ty::ExistentialPredicate::AutoTrait(trait_pred.def_id())) }); + // N.b. principal, projections, auto traits // FIXME: This is actually wrong with multiple principals in regards to symbol mangling - let mut v = regular_trait_predicates - .chain( - existential_projections.map(|x| x.map_bound(ty::ExistentialPredicate::Projection)), - ) + let mut v = principal_trait_ref + .into_iter() + .chain(existential_projections) .chain(auto_trait_predicates) .collect::<SmallVec<[_; 8]>>(); v.sort_by(|a, b| a.skip_binder().stable_cmp(tcx, &b.skip_binder())); diff --git a/compiler/rustc_hir_analysis/src/hir_ty_lowering/errors.rs b/compiler/rustc_hir_analysis/src/hir_ty_lowering/errors.rs index 7a3d921f00e..5d751a25080 100644 --- a/compiler/rustc_hir_analysis/src/hir_ty_lowering/errors.rs +++ b/compiler/rustc_hir_analysis/src/hir_ty_lowering/errors.rs @@ -11,7 +11,7 @@ use rustc_hir::def_id::DefId; use rustc_middle::bug; use rustc_middle::ty::print::{PrintPolyTraitRefExt as _, PrintTraitRefExt as _}; use rustc_middle::ty::{ - self, AdtDef, Binder, GenericParamDefKind, TraitRef, Ty, TyCtxt, TypeVisitableExt, + self, AdtDef, GenericParamDefKind, Ty, TyCtxt, TypeVisitableExt, suggest_constraining_type_param, }; use rustc_session::parse::feature_err; @@ -19,8 +19,9 @@ use rustc_span::edit_distance::find_best_match_for_name; use rustc_span::{BytePos, DUMMY_SP, Ident, Span, Symbol, kw, sym}; use rustc_trait_selection::error_reporting::traits::report_dyn_incompatibility; use rustc_trait_selection::traits::{ - FulfillmentError, TraitAliasExpansionInfo, dyn_compatibility_violations_for_assoc_item, + FulfillmentError, dyn_compatibility_violations_for_assoc_item, }; +use smallvec::SmallVec; use crate::errors::{ self, AssocItemConstraintsNotAllowedHere, ManualImplementation, MissingTypeParams, @@ -720,7 +721,7 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { /// emit a generic note suggesting using a `where` clause to constraint instead. pub(crate) fn check_for_required_assoc_tys( &self, - principal_span: Span, + spans: SmallVec<[Span; 1]>, missing_assoc_types: FxIndexSet<(DefId, ty::PolyTraitRef<'tcx>)>, potential_assoc_types: Vec<usize>, trait_bounds: &[hir::PolyTraitRef<'_>], @@ -729,6 +730,8 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { return Ok(()); } + let principal_span = *spans.first().unwrap(); + let tcx = self.tcx(); // FIXME: This logic needs some more care w.r.t handling of conflicts let missing_assoc_types: Vec<_> = missing_assoc_types @@ -1124,29 +1127,36 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { pub fn report_trait_object_addition_traits_error( &self, - regular_traits: &Vec<TraitAliasExpansionInfo<'_>>, + regular_traits: &Vec<(ty::PolyTraitPredicate<'tcx>, SmallVec<[Span; 1]>)>, ) -> ErrorGuaranteed { - let first_trait = ®ular_traits[0]; - let additional_trait = ®ular_traits[1]; + // we use the last span to point at the traits themselves, + // and all other preceding spans are trait alias expansions. + let (&first_span, first_alias_spans) = regular_traits[0].1.split_last().unwrap(); + let (&second_span, second_alias_spans) = regular_traits[1].1.split_last().unwrap(); let mut err = struct_span_code_err!( self.dcx(), - additional_trait.bottom().1, + *regular_traits[1].1.first().unwrap(), E0225, "only auto traits can be used as additional traits in a trait object" ); - additional_trait.label_with_exp_info( - &mut err, - "additional non-auto trait", - "additional use", - ); - first_trait.label_with_exp_info(&mut err, "first non-auto trait", "first use"); + err.span_label(first_span, "first non-auto trait"); + for &alias_span in first_alias_spans { + err.span_label(alias_span, "first non-auto trait comes from this alias"); + } + err.span_label(second_span, "additional non-auto trait"); + for &alias_span in second_alias_spans { + err.span_label(alias_span, "second non-auto trait comes from this alias"); + } err.help(format!( "consider creating a new trait with all of these as supertraits and using that \ trait here instead: `trait NewTrait: {} {{}}`", regular_traits .iter() // FIXME: This should `print_sugared`, but also needs to integrate projection bounds... - .map(|t| t.trait_ref().print_only_trait_path().to_string()) + .map(|(pred, _)| pred + .map_bound(|pred| pred.trait_ref) + .print_only_trait_path() + .to_string()) .collect::<Vec<_>>() .join(" + "), )); @@ -1161,14 +1171,14 @@ impl<'tcx> dyn HirTyLowerer<'tcx> + '_ { pub fn report_trait_object_with_no_traits_error( &self, span: Span, - trait_bounds: &Vec<(Binder<'tcx, TraitRef<'tcx>>, Span)>, + user_written_clauses: impl IntoIterator<Item = (ty::Clause<'tcx>, Span)>, ) -> ErrorGuaranteed { let tcx = self.tcx(); - let trait_alias_span = trait_bounds - .iter() - .map(|&(trait_ref, _)| trait_ref.def_id()) - .find(|&trait_ref| tcx.is_trait_alias(trait_ref)) - .map(|trait_ref| tcx.def_span(trait_ref)); + let trait_alias_span = user_written_clauses + .into_iter() + .filter_map(|(clause, _)| clause.as_trait_clause()) + .find(|trait_ref| tcx.is_trait_alias(trait_ref.def_id())) + .map(|trait_ref| tcx.def_span(trait_ref.def_id())); self.dcx().emit_err(TraitObjectDeclaredWithNoTraits { span, trait_alias_span }) } diff --git a/compiler/rustc_hir_typeck/src/method/probe.rs b/compiler/rustc_hir_typeck/src/method/probe.rs index 116765325a9..b9d1f93bfb8 100644 --- a/compiler/rustc_hir_typeck/src/method/probe.rs +++ b/compiler/rustc_hir_typeck/src/method/probe.rs @@ -1,6 +1,5 @@ use std::cell::{Cell, RefCell}; use std::cmp::max; -use std::iter; use std::ops::Deref; use rustc_data_structures::fx::FxHashSet; @@ -1009,11 +1008,11 @@ impl<'a, 'tcx> ProbeContext<'a, 'tcx> { if self.tcx.is_trait_alias(trait_def_id) { // For trait aliases, recursively assume all explicitly named traits are relevant - for expansion in traits::expand_trait_aliases( - self.tcx, - iter::once((ty::Binder::dummy(trait_ref), self.span)), - ) { - let bound_trait_ref = expansion.trait_ref(); + for (bound_trait_pred, _) in + traits::expand_trait_aliases(self.tcx, [(trait_ref.upcast(self.tcx), self.span)]).0 + { + assert_eq!(bound_trait_pred.polarity(), ty::PredicatePolarity::Positive); + let bound_trait_ref = bound_trait_pred.map_bound(|pred| pred.trait_ref); for item in self.impl_or_trait_item(bound_trait_ref.def_id()) { if !self.has_applicable_self(&item) { self.record_static_candidate(CandidateSource::Trait( diff --git a/compiler/rustc_trait_selection/src/error_reporting/traits/mod.rs b/compiler/rustc_trait_selection/src/error_reporting/traits/mod.rs index cd4f77bb4cf..592aee24ccc 100644 --- a/compiler/rustc_trait_selection/src/error_reporting/traits/mod.rs +++ b/compiler/rustc_trait_selection/src/error_reporting/traits/mod.rs @@ -437,7 +437,8 @@ pub fn report_dyn_incompatibility<'tcx>( tcx.dcx(), span, E0038, - "the trait `{}` cannot be made into an object", + "the {} `{}` cannot be made into an object", + tcx.def_descr(trait_def_id), trait_str ); err.span_label(span, format!("`{trait_str}` cannot be made into an object")); diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs index da16a742099..7a485419444 100644 --- a/compiler/rustc_trait_selection/src/traits/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/mod.rs @@ -66,9 +66,9 @@ pub use self::specialize::{ }; pub use self::structural_normalize::StructurallyNormalizeExt; pub use self::util::{ - BoundVarReplacer, PlaceholderReplacer, TraitAliasExpander, TraitAliasExpansionInfo, elaborate, - expand_trait_aliases, impl_item_is_final, supertraits, - transitive_bounds_that_define_assoc_item, upcast_choices, with_replaced_escaping_bound_vars, + BoundVarReplacer, PlaceholderReplacer, elaborate, expand_trait_aliases, impl_item_is_final, + supertraits, transitive_bounds_that_define_assoc_item, upcast_choices, + with_replaced_escaping_bound_vars, }; use crate::error_reporting::InferCtxtErrorExt; use crate::infer::outlives::env::OutlivesEnvironment; diff --git a/compiler/rustc_trait_selection/src/traits/util.rs b/compiler/rustc_trait_selection/src/traits/util.rs index da1045b664a..c9fb2a757e1 100644 --- a/compiler/rustc_trait_selection/src/traits/util.rs +++ b/compiler/rustc_trait_selection/src/traits/util.rs @@ -1,162 +1,85 @@ -use std::collections::BTreeMap; +use std::collections::{BTreeMap, VecDeque}; -use rustc_data_structures::fx::FxIndexMap; -use rustc_errors::Diag; +use rustc_data_structures::fx::{FxHashSet, FxIndexMap}; use rustc_hir::def_id::DefId; use rustc_infer::infer::InferCtxt; pub use rustc_infer::traits::util::*; use rustc_middle::bug; use rustc_middle::ty::{ - self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, Upcast, + self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, }; use rustc_span::Span; use smallvec::{SmallVec, smallvec}; use tracing::debug; -/////////////////////////////////////////////////////////////////////////// -// `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 Diag<'_>, - top_label: &'static 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})")); - } - } - if self.top().1 != self.bottom().1 { - // When the trait object is in a return type these two spans match, we don't want - // redundant labels. - 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 } - } -} - +/// Return the trait and projection predicates that come from eagerly expanding the +/// trait aliases in the list of clauses. For each trait predicate, record a stack +/// of spans that trace from the user-written trait alias bound. For projection predicates, +/// just record the span of the projection itself. +/// +/// For trait aliases, we don't deduplicte the predicates, since we currently do not +/// consider duplicated traits as a single trait for the purposes of our "one trait principal" +/// restriction; however, for projections we do deduplicate them. +/// +/// ```rust,ignore (fails) +/// trait Bar {} +/// trait Foo = Bar + Bar; +/// +/// let not_object_safe: dyn Foo; // bad, two `Bar` principals. +/// ``` pub fn expand_trait_aliases<'tcx>( tcx: TyCtxt<'tcx>, - trait_refs: impl Iterator<Item = (ty::PolyTraitRef<'tcx>, Span)>, -) -> TraitAliasExpander<'tcx> { - let items: Vec<_> = - trait_refs.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.upcast(tcx); - - 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.upcast(tcx)) == anon_pred) - { - return false; - } - - // Get components of trait alias. - let predicates = tcx.explicit_super_predicates_of(trait_ref.def_id()); - debug!(?predicates); - - let items = predicates.skip_binder().iter().rev().filter_map(|(pred, span)| { - pred.instantiate_supertrait(tcx, trait_ref) - .as_trait_clause() - .map(|trait_ref| item.clone_and_push(trait_ref.map_bound(|t| t.trait_ref), *span)) - }); - debug!("expand_trait_aliases: items={:?}", items.clone().collect::<Vec<_>>()); - - 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); + clauses: impl IntoIterator<Item = (ty::Clause<'tcx>, Span)>, +) -> ( + Vec<(ty::PolyTraitPredicate<'tcx>, SmallVec<[Span; 1]>)>, + Vec<(ty::PolyProjectionPredicate<'tcx>, Span)>, +) { + let mut trait_preds = vec![]; + let mut projection_preds = vec![]; + let mut seen_projection_preds = FxHashSet::default(); + + let mut queue: VecDeque<_> = clauses.into_iter().map(|(p, s)| (p, smallvec![s])).collect(); + + while let Some((clause, spans)) = queue.pop_front() { + match clause.kind().skip_binder() { + ty::ClauseKind::Trait(trait_pred) => { + if tcx.is_trait_alias(trait_pred.def_id()) { + queue.extend( + tcx.explicit_super_predicates_of(trait_pred.def_id()) + .iter_identity_copied() + .map(|(clause, span)| { + let mut spans = spans.clone(); + spans.push(span); + ( + clause.instantiate_supertrait( + tcx, + clause.kind().rebind(trait_pred.trait_ref), + ), + spans, + ) + }), + ); + } else { + trait_preds.push((clause.kind().rebind(trait_pred), spans)); + } } + ty::ClauseKind::Projection(projection_pred) => { + let projection_pred = clause.kind().rebind(projection_pred); + if !seen_projection_preds.insert(tcx.anonymize_bound_vars(projection_pred)) { + continue; + } + projection_preds.push((projection_pred, *spans.last().unwrap())); + } + ty::ClauseKind::RegionOutlives(..) + | ty::ClauseKind::TypeOutlives(..) + | ty::ClauseKind::ConstArgHasType(_, _) + | ty::ClauseKind::WellFormed(_) + | ty::ClauseKind::ConstEvaluatable(_) + | ty::ClauseKind::HostEffect(..) => {} } - None } + + (trait_preds, projection_preds) } /////////////////////////////////////////////////////////////////////////// diff --git a/compiler/rustc_type_ir/src/visit.rs b/compiler/rustc_type_ir/src/visit.rs index 71c3646498b..3213638afb2 100644 --- a/compiler/rustc_type_ir/src/visit.rs +++ b/compiler/rustc_type_ir/src/visit.rs @@ -47,6 +47,7 @@ use std::ops::ControlFlow; use rustc_ast_ir::visit::VisitorResult; use rustc_ast_ir::{try_visit, walk_visitable_list}; use rustc_index::{Idx, IndexVec}; +use smallvec::SmallVec; use thin_vec::ThinVec; use crate::data_structures::Lrc; @@ -192,6 +193,13 @@ impl<I: Interner, T: TypeVisitable<I>> TypeVisitable<I> for ThinVec<T> { } } +impl<I: Interner, T: TypeVisitable<I>, const N: usize> TypeVisitable<I> for SmallVec<[T; N]> { + fn visit_with<V: TypeVisitor<I>>(&self, visitor: &mut V) -> V::Result { + walk_visitable_list!(visitor, self.iter()); + V::Result::output() + } +} + // `TypeFoldable` isn't impl'd for `&[T]`. It doesn't make sense in the general // case, because we can't return a new slice. But note that there are a couple // of trivial impls of `TypeFoldable` for specific slice types elsewhere. |