diff options
Diffstat (limited to 'compiler')
6 files changed, 207 insertions, 123 deletions
diff --git a/compiler/rustc_ast_lowering/src/lib.rs b/compiler/rustc_ast_lowering/src/lib.rs index dc427f607f5..4ef9c7607be 100644 --- a/compiler/rustc_ast_lowering/src/lib.rs +++ b/compiler/rustc_ast_lowering/src/lib.rs @@ -1092,24 +1092,22 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> { // Piggy-back on the `impl Trait` context to figure out the correct behavior. let desugar_kind = match itctx { - // We are in the return position: - // - // fn foo() -> impl Iterator<Item: Debug> - // - // so desugar to - // - // fn foo() -> impl Iterator<Item = impl Debug> - ImplTraitContext::ReturnPositionOpaqueTy { .. } - | ImplTraitContext::TypeAliasesOpaqueTy { .. } => DesugarKind::ImplTrait, - - // We are in the argument position, but within a dyn type: + // in an argument, RPIT, or TAIT, if we are within a dyn type: // // fn foo(x: dyn Iterator<Item: Debug>) // - // so desugar to + // then desugar to: // // fn foo(x: dyn Iterator<Item = impl Debug>) - ImplTraitContext::Universal if self.is_in_dyn_type => DesugarKind::ImplTrait, + // + // This is because dyn traits must have all of their associated types specified. + ImplTraitContext::ReturnPositionOpaqueTy { .. } + | ImplTraitContext::TypeAliasesOpaqueTy { .. } + | ImplTraitContext::Universal + if self.is_in_dyn_type => + { + DesugarKind::ImplTrait + } ImplTraitContext::Disallowed(position) if self.is_in_dyn_type => { DesugarKind::Error(position) diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index 3b9515e1670..81c0cfea85a 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -548,7 +548,27 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal: Goal<'tcx, G>, candidates: &mut Vec<Candidate<'tcx>>, ) { - let alias_ty = match goal.predicate.self_ty().kind() { + let () = self.probe(|_| ProbeKind::NormalizedSelfTyAssembly).enter(|ecx| { + ecx.assemble_alias_bound_candidates_recur(goal.predicate.self_ty(), goal, candidates); + }); + } + + /// For some deeply nested `<T>::A::B::C::D` rigid associated type, + /// we should explore the item bounds for all levels, since the + /// `associated_type_bounds` feature means that a parent associated + /// type may carry bounds for a nested associated type. + /// + /// If we have a projection, check that its self type is a rigid projection. + /// If so, continue searching by recursively calling after normalization. + // FIXME: This may recurse infinitely, but I can't seem to trigger it without + // hitting another overflow error something. Add a depth parameter needed later. + fn assemble_alias_bound_candidates_recur<G: GoalKind<'tcx>>( + &mut self, + self_ty: Ty<'tcx>, + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + let (kind, alias_ty) = match *self_ty.kind() { ty::Bool | ty::Char | ty::Int(_) @@ -573,13 +593,27 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::Param(_) | ty::Placeholder(..) | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) - | ty::Alias(ty::Inherent, _) - | ty::Alias(ty::Weak, _) | ty::Error(_) => return, - ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) - | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"), - // Excluding IATs and type aliases here as they don't have meaningful item bounds. - ty::Alias(ty::Projection | ty::Opaque, alias_ty) => alias_ty, + ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) | ty::Bound(..) => { + bug!("unexpected self type for `{goal:?}`") + } + + ty::Infer(ty::TyVar(_)) => { + // If we hit infer when normalizing the self type of an alias, + // then bail with ambiguity. We should never encounter this on + // the *first* iteration of this recursive function. + if let Ok(result) = + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + { + candidates.push(Candidate { source: CandidateSource::AliasBound, result }); + } + return; + } + + ty::Alias(kind @ (ty::Projection | ty::Opaque), alias_ty) => (kind, alias_ty), + ty::Alias(ty::Inherent | ty::Weak, _) => { + unreachable!("Weak and Inherent aliases should have been normalized away already") + } }; for assumption in @@ -587,9 +621,28 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { { match G::consider_alias_bound_candidate(self, goal, assumption) { Ok(result) => { - candidates.push(Candidate { source: CandidateSource::AliasBound, result }) + candidates.push(Candidate { source: CandidateSource::AliasBound, result }); + } + Err(NoSolution) => {} + } + } + + if kind != ty::Projection { + return; + } + + match self.try_normalize_ty(goal.param_env, alias_ty.self_ty()) { + // Recurse on the self type of the projection. + Some(next_self_ty) => { + self.assemble_alias_bound_candidates_recur(next_self_ty, goal, candidates); + } + // Bail if we overflow when normalizing, adding an ambiguous candidate. + None => { + if let Ok(result) = + self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW) + { + candidates.push(Candidate { source: CandidateSource::AliasBound, result }); } - Err(NoSolution) => (), } } } diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs index d271a0ea33b..95f833372fb 100644 --- a/compiler/rustc_trait_selection/src/traits/project.rs +++ b/compiler/rustc_trait_selection/src/traits/project.rs @@ -40,6 +40,7 @@ use rustc_middle::ty::{self, Term, ToPredicate, Ty, TyCtxt}; use rustc_span::symbol::sym; use std::collections::BTreeMap; +use std::ops::ControlFlow; pub use rustc_middle::traits::Reveal; @@ -1614,32 +1615,44 @@ fn assemble_candidates_from_trait_def<'cx, 'tcx>( candidate_set: &mut ProjectionCandidateSet<'tcx>, ) { debug!("assemble_candidates_from_trait_def(..)"); + let mut ambiguous = false; + selcx.for_each_item_bound( + obligation.predicate.self_ty(), + |selcx, clause, _| { + let Some(clause) = clause.as_projection_clause() else { + return ControlFlow::Continue(()); + }; - let tcx = selcx.tcx(); - // Check whether the self-type is itself a projection. - // If so, extract what we know from the trait and try to come up with a good answer. - let bounds = match *obligation.predicate.self_ty().kind() { - // Excluding IATs and type aliases here as they don't have meaningful item bounds. - ty::Alias(ty::Projection | ty::Opaque, ref data) => { - tcx.item_bounds(data.def_id).instantiate(tcx, data.args) - } - ty::Infer(ty::TyVar(_)) => { - // If the self-type is an inference variable, then it MAY wind up - // being a projected type, so induce an ambiguity. - candidate_set.mark_ambiguous(); - return; - } - _ => return, - }; + let is_match = + selcx.infcx.probe(|_| selcx.match_projection_projections(obligation, clause, true)); - assemble_candidates_from_predicates( - selcx, - obligation, - candidate_set, - ProjectionCandidate::TraitDef, - bounds.iter(), - true, + match is_match { + ProjectionMatchesProjection::Yes => { + candidate_set.push_candidate(ProjectionCandidate::TraitDef(clause)); + + if !obligation.predicate.has_non_region_infer() { + // HACK: Pick the first trait def candidate for a fully + // inferred predicate. This is to allow duplicates that + // differ only in normalization. + return ControlFlow::Break(()); + } + } + ProjectionMatchesProjection::Ambiguous => { + candidate_set.mark_ambiguous(); + } + ProjectionMatchesProjection::No => {} + } + + ControlFlow::Continue(()) + }, + // `ProjectionCandidateSet` is borrowed in the above closure, + // so just mark ambiguous outside of the closure. + || ambiguous = true, ); + + if ambiguous { + candidate_set.mark_ambiguous(); + } } /// In the case of a trait object like diff --git a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs index d056dd51f50..27dbe0351da 100644 --- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs +++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs @@ -6,13 +6,16 @@ //! //! [rustc dev guide]:https://rustc-dev-guide.rust-lang.org/traits/resolution.html#candidate-assembly +use std::ops::ControlFlow; + use hir::def_id::DefId; use hir::LangItem; +use rustc_data_structures::fx::FxHashSet; use rustc_hir as hir; use rustc_infer::traits::ObligationCause; use rustc_infer::traits::{Obligation, PolyTraitObligation, SelectionError}; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; -use rustc_middle::ty::{self, Ty, TypeVisitableExt}; +use rustc_middle::ty::{self, ToPolyTraitRef, Ty, TypeVisitableExt}; use crate::traits; use crate::traits::query::evaluate_obligation::InferCtxtExt; @@ -158,11 +161,50 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { _ => return, } - let result = self - .infcx - .probe(|_| self.match_projection_obligation_against_definition_bounds(obligation)); + self.infcx.probe(|_| { + let poly_trait_predicate = self.infcx.resolve_vars_if_possible(obligation.predicate); + let placeholder_trait_predicate = + self.infcx.enter_forall_and_leak_universe(poly_trait_predicate); + debug!(?placeholder_trait_predicate); + + // The bounds returned by `item_bounds` may contain duplicates after + // normalization, so try to deduplicate when possible to avoid + // unnecessary ambiguity. + let mut distinct_normalized_bounds = FxHashSet::default(); + self.for_each_item_bound::<!>( + placeholder_trait_predicate.self_ty(), + |selcx, bound, idx| { + let Some(bound) = bound.as_trait_clause() else { + return ControlFlow::Continue(()); + }; + if bound.polarity() != placeholder_trait_predicate.polarity { + return ControlFlow::Continue(()); + } - candidates.vec.extend(result.into_iter().map(|idx| ProjectionCandidate(idx))); + selcx.infcx.probe(|_| { + match selcx.match_normalize_trait_ref( + obligation, + bound.to_poly_trait_ref(), + placeholder_trait_predicate.trait_ref, + ) { + Ok(None) => { + candidates.vec.push(ProjectionCandidate(idx)); + } + Ok(Some(normalized_trait)) + if distinct_normalized_bounds.insert(normalized_trait) => + { + candidates.vec.push(ProjectionCandidate(idx)); + } + _ => {} + } + }); + + ControlFlow::Continue(()) + }, + // On ambiguity. + || candidates.ambiguous = true, + ); + }); } /// Given an obligation like `<SomeTrait for T>`, searches the obligations that the caller diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs index f0c49253dbd..42074f4a079 100644 --- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs +++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs @@ -162,20 +162,26 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.infcx.enter_forall_and_leak_universe(trait_predicate).trait_ref; let placeholder_self_ty = placeholder_trait_predicate.self_ty(); let placeholder_trait_predicate = ty::Binder::dummy(placeholder_trait_predicate); - let (def_id, args) = match *placeholder_self_ty.kind() { - // Excluding IATs and type aliases here as they don't have meaningful item bounds. - ty::Alias(ty::Projection | ty::Opaque, ty::AliasTy { def_id, args, .. }) => { - (def_id, args) - } - _ => bug!("projection candidate for unexpected type: {:?}", placeholder_self_ty), - }; - let candidate_predicate = - tcx.item_bounds(def_id).map_bound(|i| i[idx]).instantiate(tcx, args); + let candidate_predicate = self + .for_each_item_bound( + placeholder_self_ty, + |_, clause, clause_idx| { + if clause_idx == idx { + ControlFlow::Break(clause) + } else { + ControlFlow::Continue(()) + } + }, + || unreachable!(), + ) + .break_value() + .expect("expected to index into clause that exists"); let candidate = candidate_predicate .as_trait_clause() .expect("projection candidate is not a trait predicate") .map_bound(|t| t.trait_ref); + let mut obligations = Vec::new(); let candidate = normalize_with_depth_to( self, @@ -194,8 +200,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { .map_err(|_| Unimplemented) })?); - if let ty::Alias(ty::Projection, ..) = placeholder_self_ty.kind() { - let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, args); + // FIXME(compiler-errors): I don't think this is needed. + if let ty::Alias(ty::Projection, alias_ty) = placeholder_self_ty.kind() { + let predicates = tcx.predicates_of(alias_ty.def_id).instantiate_own(tcx, alias_ty.args); for (predicate, _) in predicates { let normalized = normalize_with_depth_to( self, diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs index 5befff5372a..ac6cfcdeb59 100644 --- a/compiler/rustc_trait_selection/src/traits/select/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs @@ -52,6 +52,7 @@ use std::cell::{Cell, RefCell}; use std::cmp; use std::fmt::{self, Display}; use std::iter; +use std::ops::ControlFlow; pub use rustc_middle::traits::select::*; use rustc_middle::ty::print::with_no_trimmed_paths; @@ -1592,71 +1593,41 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { self.infcx.selection_cache.insert((param_env, pred), dep_node, candidate); } - /// Matches a predicate against the bounds of its self type. - /// - /// Given an obligation like `<T as Foo>::Bar: Baz` where the self type is - /// a projection, look at the bounds of `T::Bar`, see if we can find a - /// `Baz` bound. We return indexes into the list returned by - /// `tcx.item_bounds` for any applicable bounds. - #[instrument(level = "debug", skip(self), ret)] - fn match_projection_obligation_against_definition_bounds( + /// Looks at the item bounds of the projection or opaque type. + /// If this is a nested rigid projection, such as + /// `<<T as Tr1>::Assoc as Tr2>::Assoc`, consider the item bounds + /// on both `Tr1::Assoc` and `Tr2::Assoc`, since we may encounter + /// relative bounds on both via the `associated_type_bounds` feature. + pub(super) fn for_each_item_bound<T>( &mut self, - obligation: &PolyTraitObligation<'tcx>, - ) -> smallvec::SmallVec<[usize; 2]> { - let poly_trait_predicate = self.infcx.resolve_vars_if_possible(obligation.predicate); - let placeholder_trait_predicate = - self.infcx.enter_forall_and_leak_universe(poly_trait_predicate); - debug!(?placeholder_trait_predicate); - - let tcx = self.infcx.tcx; - let (def_id, args) = match *placeholder_trait_predicate.trait_ref.self_ty().kind() { - ty::Alias(ty::Projection | ty::Opaque, ty::AliasTy { def_id, args, .. }) => { - (def_id, args) - } - _ => { - span_bug!( - obligation.cause.span, - "match_projection_obligation_against_definition_bounds() called \ - but self-ty is not a projection: {:?}", - placeholder_trait_predicate.trait_ref.self_ty() - ); - } - }; - let bounds = tcx.item_bounds(def_id).instantiate(tcx, args); + mut self_ty: Ty<'tcx>, + mut for_each: impl FnMut(&mut Self, ty::Clause<'tcx>, usize) -> ControlFlow<T, ()>, + on_ambiguity: impl FnOnce(), + ) -> ControlFlow<T, ()> { + let mut idx = 0; + loop { + let (kind, alias_ty) = match *self_ty.kind() { + ty::Alias(kind @ (ty::Projection | ty::Opaque), alias_ty) => (kind, alias_ty), + ty::Infer(ty::TyVar(_)) => { + on_ambiguity(); + return ControlFlow::Continue(()); + } + _ => return ControlFlow::Continue(()), + }; - // The bounds returned by `item_bounds` may contain duplicates after - // normalization, so try to deduplicate when possible to avoid - // unnecessary ambiguity. - let mut distinct_normalized_bounds = FxHashSet::default(); + for bound in + self.tcx().item_bounds(alias_ty.def_id).instantiate(self.tcx(), alias_ty.args) + { + for_each(self, bound, idx)?; + idx += 1; + } - bounds - .iter() - .enumerate() - .filter_map(|(idx, bound)| { - let bound_predicate = bound.kind(); - if let ty::ClauseKind::Trait(pred) = bound_predicate.skip_binder() { - let bound = bound_predicate.rebind(pred.trait_ref); - if self.infcx.probe(|_| { - match self.match_normalize_trait_ref( - obligation, - bound, - placeholder_trait_predicate.trait_ref, - ) { - Ok(None) => true, - Ok(Some(normalized_trait)) - if distinct_normalized_bounds.insert(normalized_trait) => - { - true - } - _ => false, - } - }) { - return Some(idx); - } - } - None - }) - .collect() + if kind == ty::Projection { + self_ty = alias_ty.self_ty(); + } else { + return ControlFlow::Continue(()); + } + } } /// Equates the trait in `obligation` with trait bound. If the two traits |