Fix replacing supertrait aliases in ReplaceProjectionWith

10 files changed, 238 insertions, 68 deletions

diff --git a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
index ee000b11748..83b2465d05a 100644
--- a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
@@ -92,16 +92,20 @@ where
             let ty::Dynamic(bounds, _, _) = goal.predicate.self_ty().kind() else {
                 panic!("expected object type in `probe_and_consider_object_bound_candidate`");
             };
-            ecx.add_goals(
-                GoalSource::ImplWhereBound,
-                structural_traits::predicates_for_object_candidate(
-                    ecx,
-                    goal.param_env,
-                    goal.predicate.trait_ref(cx),
-                    bounds,
-                ),
-            );
-            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+            match structural_traits::predicates_for_object_candidate(
+                ecx,
+                goal.param_env,
+                goal.predicate.trait_ref(cx),
+                bounds,
+            ) {
+                Ok(requirements) => {
+                    ecx.add_goals(GoalSource::ImplWhereBound, requirements);
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                }
+                Err(_) => {
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
+                }
+            }
         })
     }
 
diff --git a/compiler/rustc_next_trait_solver/src/solve/assembly/structural_traits.rs b/compiler/rustc_next_trait_solver/src/solve/assembly/structural_traits.rs
index c2fb592c3f3..46ec8897fa5 100644
--- a/compiler/rustc_next_trait_solver/src/solve/assembly/structural_traits.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/assembly/structural_traits.rs
@@ -5,9 +5,10 @@ use derive_where::derive_where;
 use rustc_type_ir::data_structures::HashMap;
 use rustc_type_ir::inherent::*;
 use rustc_type_ir::lang_items::TraitSolverLangItem;
+use rustc_type_ir::solve::inspect::ProbeKind;
 use rustc_type_ir::{
-    self as ty, Interner, Movability, Mutability, TypeFoldable, TypeFolder, TypeSuperFoldable,
-    Upcast as _, elaborate,
+    self as ty, FallibleTypeFolder, Interner, Movability, Mutability, TypeFoldable,
+    TypeSuperFoldable, Upcast as _, elaborate,
 };
 use rustc_type_ir_macros::{TypeFoldable_Generic, TypeVisitable_Generic};
 use tracing::instrument;
@@ -822,7 +823,7 @@ pub(in crate::solve) fn const_conditions_for_destruct<I: Interner>(
 /// impl Baz for dyn Foo<Item = Ty> {}
 /// ```
 ///
-/// However, in order to make such impls well-formed, we need to do an
+/// However, in order to make such impls non-cyclical, we need to do an
 /// additional step of eagerly folding the associated types in the where
 /// clauses of the impl. In this example, that means replacing
 /// `<Self as Foo>::Bar` with `Ty` in the first impl.
@@ -833,11 +834,11 @@ pub(in crate::solve) fn const_conditions_for_destruct<I: Interner>(
 // normalize eagerly here. See https://github.com/lcnr/solver-woes/issues/9
 // for more details.
 pub(in crate::solve) fn predicates_for_object_candidate<D, I>(
-    ecx: &EvalCtxt<'_, D>,
+    ecx: &mut EvalCtxt<'_, D>,
     param_env: I::ParamEnv,
     trait_ref: ty::TraitRef<I>,
     object_bounds: I::BoundExistentialPredicates,
-) -> Vec<Goal<I, I::Predicate>>
+) -> Result<Vec<Goal<I, I::Predicate>>, Ambiguous>
 where
     D: SolverDelegate<Interner = I>,
     I: Interner,
@@ -871,72 +872,130 @@ where
             .extend(cx.item_bounds(associated_type_def_id).iter_instantiated(cx, trait_ref.args));
     }
 
-    let mut replace_projection_with = HashMap::default();
+    let mut replace_projection_with: HashMap<_, Vec<_>> = HashMap::default();
     for bound in object_bounds.iter() {
         if let ty::ExistentialPredicate::Projection(proj) = bound.skip_binder() {
+            // FIXME: We *probably* should replace this with a dummy placeholder,
+            // b/c don't want to replace literal instances of this dyn type that
+            // show up in the bounds, but just ones that come from substituting
+            // `Self` with the dyn type.
             let proj = proj.with_self_ty(cx, trait_ref.self_ty());
-            let old_ty = replace_projection_with.insert(proj.def_id(), bound.rebind(proj));
-            assert_eq!(
-                old_ty,
-                None,
-                "{:?} has two generic parameters: {:?} and {:?}",
-                proj.projection_term,
-                proj.term,
-                old_ty.unwrap()
-            );
+            replace_projection_with.entry(proj.def_id()).or_default().push(bound.rebind(proj));
         }
     }
 
-    let mut folder =
-        ReplaceProjectionWith { ecx, param_env, mapping: replace_projection_with, nested: vec![] };
-    let folded_requirements = requirements.fold_with(&mut folder);
+    let mut folder = ReplaceProjectionWith {
+        ecx,
+        param_env,
+        self_ty: trait_ref.self_ty(),
+        mapping: &replace_projection_with,
+        nested: vec![],
+    };
 
-    folder
+    let requirements = requirements.try_fold_with(&mut folder)?;
+    Ok(folder
         .nested
         .into_iter()
-        .chain(folded_requirements.into_iter().map(|clause| Goal::new(cx, param_env, clause)))
-        .collect()
+        .chain(requirements.into_iter().map(|clause| Goal::new(cx, param_env, clause)))
+        .collect())
 }
 
-struct ReplaceProjectionWith<'a, D: SolverDelegate<Interner = I>, I: Interner> {
-    ecx: &'a EvalCtxt<'a, D>,
+struct ReplaceProjectionWith<'a, 'b, I: Interner, D: SolverDelegate<Interner = I>> {
+    ecx: &'a mut EvalCtxt<'b, D>,
     param_env: I::ParamEnv,
-    mapping: HashMap<I::DefId, ty::Binder<I, ty::ProjectionPredicate<I>>>,
+    self_ty: I::Ty,
+    mapping: &'a HashMap<I::DefId, Vec<ty::Binder<I, ty::ProjectionPredicate<I>>>>,
     nested: Vec<Goal<I, I::Predicate>>,
 }
 
-impl<D: SolverDelegate<Interner = I>, I: Interner> TypeFolder<I>
-    for ReplaceProjectionWith<'_, D, I>
+impl<D, I> ReplaceProjectionWith<'_, '_, I, D>
+where
+    D: SolverDelegate<Interner = I>,
+    I: Interner,
+{
+    fn projection_may_match(
+        &mut self,
+        source_projection: ty::Binder<I, ty::ProjectionPredicate<I>>,
+        target_projection: ty::AliasTerm<I>,
+    ) -> bool {
+        source_projection.item_def_id() == target_projection.def_id
+            && self
+                .ecx
+                .probe(|_| ProbeKind::ProjectionCompatibility)
+                .enter(|ecx| -> Result<_, NoSolution> {
+                    let source_projection = ecx.instantiate_binder_with_infer(source_projection);
+                    ecx.eq(self.param_env, source_projection.projection_term, target_projection)?;
+                    ecx.try_evaluate_added_goals()
+                })
+                .is_ok()
+    }
+
+    /// Try to replace an alias with the term present in the projection bounds of the self type.
+    /// Returns `Ok<None>` if this alias is not eligible to be replaced, or bail with
+    /// `Err(Ambiguous)` if it's uncertain which projection bound to replace the term with due
+    /// to multiple bounds applying.
+    fn try_eagerly_replace_alias(
+        &mut self,
+        alias_term: ty::AliasTerm<I>,
+    ) -> Result<Option<I::Term>, Ambiguous> {
+        if alias_term.self_ty() != self.self_ty {
+            return Ok(None);
+        }
+
+        let Some(replacements) = self.mapping.get(&alias_term.def_id) else {
+            return Ok(None);
+        };
+
+        // This is quite similar to the `projection_may_match` we use in unsizing,
+        // but here we want to unify a projection predicate against an alias term
+        // so we can replace it with the the projection predicate's term.
+        let mut matching_projections = replacements
+            .iter()
+            .filter(|source_projection| self.projection_may_match(**source_projection, alias_term));
+        let Some(replacement) = matching_projections.next() else {
+            // This shouldn't happen.
+            panic!("could not replace {alias_term:?} with term from from {:?}", self.self_ty);
+        };
+        // FIXME: This *may* have issues with duplicated projections.
+        if matching_projections.next().is_some() {
+            // If there's more than one projection that we can unify here, then we
+            // need to stall until inference constrains things so that there's only
+            // one choice.
+            return Err(Ambiguous);
+        }
+
+        let replacement = self.ecx.instantiate_binder_with_infer(*replacement);
+        self.nested.extend(
+            self.ecx
+                .eq_and_get_goals(self.param_env, alias_term, replacement.projection_term)
+                .expect("expected to be able to unify goal projection with dyn's projection"),
+        );
+
+        Ok(Some(replacement.term))
+    }
+}
+
+/// Marker for bailing with ambiguity.
+pub(crate) struct Ambiguous;
+
+impl<D, I> FallibleTypeFolder<I> for ReplaceProjectionWith<'_, '_, I, D>
+where
+    D: SolverDelegate<Interner = I>,
+    I: Interner,
 {
+    type Error = Ambiguous;
+
     fn cx(&self) -> I {
         self.ecx.cx()
     }
 
-    fn fold_ty(&mut self, ty: I::Ty) -> I::Ty {
+    fn try_fold_ty(&mut self, ty: I::Ty) -> Result<I::Ty, Ambiguous> {
         if let ty::Alias(ty::Projection, alias_ty) = ty.kind() {
-            if let Some(replacement) = self.mapping.get(&alias_ty.def_id) {
-                // We may have a case where our object type's projection bound is higher-ranked,
-                // but the where clauses we instantiated are not. We can solve this by instantiating
-                // the binder at the usage site.
-                let proj = self.ecx.instantiate_binder_with_infer(*replacement);
-                // FIXME: Technically this equate could be fallible...
-                self.nested.extend(
-                    self.ecx
-                        .eq_and_get_goals(
-                            self.param_env,
-                            alias_ty,
-                            proj.projection_term.expect_ty(self.ecx.cx()),
-                        )
-                        .expect(
-                            "expected to be able to unify goal projection with dyn's projection",
-                        ),
-                );
-                proj.term.expect_ty()
-            } else {
-                ty.super_fold_with(self)
+            if let Some(term) = self.try_eagerly_replace_alias(alias_ty.into())? {
+                return Ok(term.expect_ty());
             }
-        } else {
-            ty.super_fold_with(self)
         }
+
+        ty.try_super_fold_with(self)
     }
 }
diff --git a/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs
index 9262da2906d..409af8568d7 100644
--- a/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/trait_goals.rs
@@ -944,7 +944,7 @@ where
              target_projection: ty::Binder<I, ty::ExistentialProjection<I>>| {
                 source_projection.item_def_id() == target_projection.item_def_id()
                     && ecx
-                        .probe(|_| ProbeKind::UpcastProjectionCompatibility)
+                        .probe(|_| ProbeKind::ProjectionCompatibility)
                         .enter(|ecx| -> Result<_, NoSolution> {
                             ecx.enter_forall(target_projection, |ecx, target_projection| {
                                 let source_projection =
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 48a05ad29fb..24b87000e32 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -292,7 +292,7 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
                 inspect::ProbeStep::NestedProbe(ref probe) => {
                     match probe.kind {
                         // These never assemble candidates for the goal we're trying to solve.
-                        inspect::ProbeKind::UpcastProjectionCompatibility
+                        inspect::ProbeKind::ProjectionCompatibility
                         | inspect::ProbeKind::ShadowedEnvProbing => continue,
 
                         inspect::ProbeKind::NormalizedSelfTyAssembly
@@ -314,8 +314,10 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
         }
 
         match probe.kind {
-            inspect::ProbeKind::UpcastProjectionCompatibility
-            | inspect::ProbeKind::ShadowedEnvProbing => bug!(),
+            inspect::ProbeKind::ProjectionCompatibility
+            | inspect::ProbeKind::ShadowedEnvProbing => {
+                bug!()
+            }
 
             inspect::ProbeKind::NormalizedSelfTyAssembly | inspect::ProbeKind::UnsizeAssembly => {}
 
diff --git a/compiler/rustc_trait_selection/src/solve/select.rs b/compiler/rustc_trait_selection/src/solve/select.rs
index 4437fc5b029..4fdaf740287 100644
--- a/compiler/rustc_trait_selection/src/solve/select.rs
+++ b/compiler/rustc_trait_selection/src/solve/select.rs
@@ -177,7 +177,7 @@ fn to_selection<'tcx>(
         },
         ProbeKind::NormalizedSelfTyAssembly
         | ProbeKind::UnsizeAssembly
-        | ProbeKind::UpcastProjectionCompatibility
+        | ProbeKind::ProjectionCompatibility
         | ProbeKind::OpaqueTypeStorageLookup { result: _ }
         | ProbeKind::Root { result: _ }
         | ProbeKind::ShadowedEnvProbing
diff --git a/compiler/rustc_type_ir/src/solve/inspect.rs b/compiler/rustc_type_ir/src/solve/inspect.rs
index 18fb71dd290..b10641b287d 100644
--- a/compiler/rustc_type_ir/src/solve/inspect.rs
+++ b/compiler/rustc_type_ir/src/solve/inspect.rs
@@ -118,10 +118,12 @@ pub enum ProbeKind<I: Interner> {
     /// Used in the probe that wraps normalizing the non-self type for the unsize
     /// trait, which is also structurally matched on.
     UnsizeAssembly,
-    /// During upcasting from some source object to target object type, used to
-    /// do a probe to find out what projection type(s) may be used to prove that
-    /// the source type upholds all of the target type's object bounds.
-    UpcastProjectionCompatibility,
+    /// Used to do a probe to find out what projection type(s) match a given
+    /// alias bound or projection predicate. For trait upcasting, this is used
+    /// to prove that the source type upholds all of the target type's object
+    /// bounds. For object type bounds, this is used when eagerly replacing
+    /// supertrait aliases.
+    ProjectionCompatibility,
     /// Looking for param-env candidates that satisfy the trait ref for a projection.
     ShadowedEnvProbing,
     /// Try to unify an opaque type with an existing key in the storage.
diff --git a/tests/ui/traits/next-solver/supertrait-alias-1.rs b/tests/ui/traits/next-solver/supertrait-alias-1.rs
new file mode 100644
index 00000000000..579a44677c2
--- /dev/null
+++ b/tests/ui/traits/next-solver/supertrait-alias-1.rs
@@ -0,0 +1,22 @@
+//@ compile-flags: -Znext-solver
+//@ check-pass
+
+// Regression test for <https://github.com/rust-lang/trait-system-refactor-initiative/issues/171>.
+// Tests that we don't try to replace `<V as Super>::Output` when replacing projections in the
+// required bounds for `dyn Trait`, b/c `V` is not relevant to the dyn type, which we were
+// previously encountering b/c we were walking into the existential projection bounds of the dyn
+// type itself.
+
+pub trait Trait: Super {}
+
+pub trait Super {
+    type Output;
+}
+
+fn bound<T: Trait + ?Sized>() {}
+
+fn visit_simd_operator<V: Super + ?Sized>() {
+    bound::<dyn Trait<Output = <V as Super>::Output>>();
+}
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/supertrait-alias-2.rs b/tests/ui/traits/next-solver/supertrait-alias-2.rs
new file mode 100644
index 00000000000..a0f3e038dca
--- /dev/null
+++ b/tests/ui/traits/next-solver/supertrait-alias-2.rs
@@ -0,0 +1,25 @@
+//@ compile-flags: -Znext-solver
+//@ check-pass
+
+// Regression test for <https://github.com/rust-lang/trait-system-refactor-initiative/issues/171>.
+// Tests that we don't try to replace `<T as Other>::Assoc` when replacing projections in the
+// required bounds for `dyn Foo`, b/c `T` is not relevant to the dyn type, which we were
+// encountering when walking through the elaborated supertraits of `dyn Foo`.
+
+trait Other<X> {}
+
+trait Foo<T: Foo<T>>: Other<<T as Foo<T>>::Assoc> {
+    type Assoc;
+}
+
+impl<T> Foo<T> for T {
+    type Assoc = ();
+}
+
+impl<T: ?Sized> Other<()> for T {}
+
+fn is_foo<T: Foo<()> + ?Sized>() {}
+
+fn main() {
+    is_foo::<dyn Foo<(), Assoc = ()>>();
+}
diff --git a/tests/ui/traits/next-solver/supertrait-alias-3.rs b/tests/ui/traits/next-solver/supertrait-alias-3.rs
new file mode 100644
index 00000000000..78182bbc415
--- /dev/null
+++ b/tests/ui/traits/next-solver/supertrait-alias-3.rs
@@ -0,0 +1,32 @@
+//@ compile-flags: -Znext-solver
+//@ check-pass
+
+// Regression test for <https://github.com/rust-lang/trait-system-refactor-initiative/issues/171>.
+// Exercises a case where structural equality is insufficient when replacing projections in a dyn's
+// bounds. In this case, the bound will contain `<Self as Super<<i32 as Mirror>:Assoc>::Assoc`, but
+// the existential projections from the dyn will have `<Self as Super<i32>>::Assoc` because as an
+// optimization we eagerly normalize aliases in goals.
+
+trait Other<T> {}
+impl<T> Other<T> for T {}
+
+trait Super<T> {
+    type Assoc;
+}
+
+trait Mirror {
+    type Assoc;
+}
+impl<T> Mirror for T {
+    type Assoc = T;
+}
+
+trait Foo<A, B>: Super<<A as Mirror>::Assoc, Assoc = A> {
+    type FooAssoc: Other<<Self as Super<<A as Mirror>::Assoc>>::Assoc>;
+}
+
+fn is_foo<F: Foo<T, U> + ?Sized, T, U>() {}
+
+fn main() {
+    is_foo::<dyn Foo<i32, u32, FooAssoc = i32>, _, _>();
+}
diff --git a/tests/ui/traits/next-solver/supertrait-alias-4.rs b/tests/ui/traits/next-solver/supertrait-alias-4.rs
new file mode 100644
index 00000000000..919a768fcf2
--- /dev/null
+++ b/tests/ui/traits/next-solver/supertrait-alias-4.rs
@@ -0,0 +1,24 @@
+//@ compile-flags: -Znext-solver
+//@ check-pass
+
+// Exercises the ambiguity that comes from replacing the associated types within the bounds
+// that are required for a `impl Trait for dyn Trait` built-in object impl to hold.
+
+trait Sup<T> {
+    type Assoc;
+}
+
+trait Foo<A, B>: Sup<A, Assoc = A> + Sup<B, Assoc = B> {
+    type Other: Bar<<Self as Sup<A>>::Assoc>;
+}
+
+trait Bar<T> {}
+impl Bar<i32> for () {}
+
+fn foo<A, B>(x: &(impl Foo<A, B> + ?Sized)) {}
+
+fn main() {
+    let x: &dyn Foo<_, _, Other = ()> = todo!();
+    foo(x);
+    let y: &dyn Foo<i32, u32, Other = ()> = x;
+}