normalize in `trait_ref_is_knowable` in new solver

10 files changed, 214 insertions, 83 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 1391b51e67f..3750b3750bf 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -316,6 +316,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         self.assemble_param_env_candidates(goal, &mut candidates);
 
+        self.assemble_coherence_unknowable_candidates(goal, &mut candidates);
+
         candidates
     }
 
@@ -363,10 +365,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         self.assemble_object_bound_candidates(goal, &mut candidates);
 
-        self.assemble_coherence_unknowable_candidates(goal, &mut candidates);
-
         self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates, num_steps);
-
         candidates
     }
 
@@ -877,26 +876,43 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         goal: Goal<'tcx, G>,
         candidates: &mut Vec<Candidate<'tcx>>,
     ) {
+        let tcx = self.tcx();
         match self.solver_mode() {
             SolverMode::Normal => return,
-            SolverMode::Coherence => {
-                let trait_ref = goal.predicate.trait_ref(self.tcx());
-                match coherence::trait_ref_is_knowable(self.tcx(), trait_ref) {
-                    Ok(()) => {}
-                    Err(_) => match self
-                        .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
-                    {
-                        Ok(result) => candidates.push(Candidate {
-                            source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
-                            result,
-                        }),
-                        // FIXME: This will be reachable at some point if we're in
-                        // `assemble_candidates_after_normalizing_self_ty` and we get a
-                        // universe error. We'll deal with it at this point.
-                        Err(NoSolution) => bug!("coherence candidate resulted in NoSolution"),
-                    },
+            SolverMode::Coherence => {}
+        };
+
+        let result = self.probe_candidate("coherence unknowable").enter(|ecx| {
+            let trait_ref = goal.predicate.trait_ref(tcx);
+
+            #[derive(Debug)]
+            enum FailureKind {
+                Overflow,
+                NoSolution(NoSolution),
+            }
+            let lazily_normalize_ty = |ty| match ecx.try_normalize_ty(goal.param_env, ty) {
+                Ok(Some(ty)) => Ok(ty),
+                Ok(None) => Err(FailureKind::Overflow),
+                Err(e) => Err(FailureKind::NoSolution(e)),
+            };
+
+            match coherence::trait_ref_is_knowable(tcx, trait_ref, lazily_normalize_ty) {
+                Err(FailureKind::Overflow) => {
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW)
+                }
+                Err(FailureKind::NoSolution(NoSolution)) | Ok(Ok(())) => Err(NoSolution),
+                Ok(Err(_)) => {
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                 }
             }
+        });
+
+        match result {
+            Ok(result) => candidates.push(Candidate {
+                source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
+                result,
+            }),
+            Err(NoSolution) => {}
         }
     }
 
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 63d4a38119f..75a99f799a2 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -283,6 +283,37 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
         Ok(self.make_ambiguous_response_no_constraints(maybe_cause))
     }
+
+    /// Normalize a type when it is structually matched on.
+    ///
+    /// For self types this is generally already handled through
+    /// `assemble_candidates_after_normalizing_self_ty`, so anything happening
+    /// in [`EvalCtxt::assemble_candidates_via_self_ty`] does not have to normalize
+    /// the self type. It is required when structurally matching on any other
+    /// arguments of a trait goal, e.g. when assembling builtin unsize candidates.
+    fn try_normalize_ty(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        mut ty: Ty<'tcx>,
+    ) -> Result<Option<Ty<'tcx>>, NoSolution> {
+        for _ in 0..self.local_overflow_limit() {
+            let ty::Alias(_, projection_ty) = *ty.kind() else {
+                return Ok(Some(ty));
+            };
+
+            let normalized_ty = self.next_ty_infer();
+            let normalizes_to_goal = Goal::new(
+                self.tcx(),
+                param_env,
+                ty::ProjectionPredicate { projection_ty, term: normalized_ty.into() },
+            );
+            self.add_goal(normalizes_to_goal);
+            self.try_evaluate_added_goals()?;
+            ty = self.resolve_vars_if_possible(normalized_ty);
+        }
+
+        Ok(None)
+    }
 }
 
 fn response_no_constraints_raw<'tcx>(
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index db80b62d8a2..ee6f1686b82 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -448,7 +448,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             // We need to normalize the b_ty since it's matched structurally
             // in the other functions below.
             let b_ty = match ecx
-                .normalize_non_self_ty(goal.predicate.trait_ref.args.type_at(1), goal.param_env)
+                .try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1))
             {
                 Ok(Some(b_ty)) => b_ty,
                 Ok(None) => return vec![misc_candidate(ecx, Certainty::OVERFLOW)],
@@ -927,41 +927,4 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         let candidates = self.assemble_and_evaluate_candidates(goal);
         self.merge_candidates(candidates)
     }
-
-    /// Normalize a non-self type when it is structually matched on when solving
-    /// a built-in goal.
-    ///
-    /// This is handled already through `assemble_candidates_after_normalizing_self_ty`
-    /// for the self type, but for other goals, additional normalization of other
-    /// arguments may be needed to completely implement the semantics of the trait.
-    ///
-    /// This is required when structurally matching on any trait argument that is
-    /// not the self type.
-    fn normalize_non_self_ty(
-        &mut self,
-        mut ty: Ty<'tcx>,
-        param_env: ty::ParamEnv<'tcx>,
-    ) -> Result<Option<Ty<'tcx>>, NoSolution> {
-        if !matches!(ty.kind(), ty::Alias(..)) {
-            return Ok(Some(ty));
-        }
-
-        for _ in 0..self.local_overflow_limit() {
-            let ty::Alias(_, projection_ty) = *ty.kind() else {
-                return Ok(Some(ty));
-            };
-
-            let normalized_ty = self.next_ty_infer();
-            let normalizes_to_goal = Goal::new(
-                self.tcx(),
-                param_env,
-                ty::ProjectionPredicate { projection_ty, term: normalized_ty.into() },
-            );
-            self.add_goal(normalizes_to_goal);
-            self.try_evaluate_added_goals()?;
-            ty = self.resolve_vars_if_possible(normalized_ty);
-        }
-
-        Ok(None)
-    }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 19d5baa30ec..e56af586ed8 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -452,22 +452,23 @@ fn prove_negated_obligation<'tcx>(
 /// This both checks whether any downstream or sibling crates could
 /// implement it and whether an upstream crate can add this impl
 /// without breaking backwards compatibility.
-#[instrument(level = "debug", skip(tcx), ret)]
-pub fn trait_ref_is_knowable<'tcx>(
+#[instrument(level = "debug", skip(tcx, lazily_normalize_ty), ret)]
+pub fn trait_ref_is_knowable<'tcx, E: Debug>(
     tcx: TyCtxt<'tcx>,
     trait_ref: ty::TraitRef<'tcx>,
-) -> Result<(), Conflict> {
+    mut lazily_normalize_ty: impl FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
+) -> Result<Result<(), Conflict>, E> {
     if Some(trait_ref.def_id) == tcx.lang_items().fn_ptr_trait() {
         // The only types implementing `FnPtr` are function pointers,
         // so if there's no impl of `FnPtr` in the current crate,
         // then such an impl will never be added in the future.
-        return Ok(());
+        return Ok(Ok(()));
     }
 
-    if orphan_check_trait_ref(trait_ref, InCrate::Remote).is_ok() {
+    if orphan_check_trait_ref(trait_ref, InCrate::Remote, &mut lazily_normalize_ty)?.is_ok() {
         // A downstream or cousin crate is allowed to implement some
         // substitution of this trait-ref.
-        return Err(Conflict::Downstream);
+        return Ok(Err(Conflict::Downstream));
     }
 
     if trait_ref_is_local_or_fundamental(tcx, trait_ref) {
@@ -476,7 +477,7 @@ pub fn trait_ref_is_knowable<'tcx>(
         // allowed to implement a substitution of this trait ref, which
         // means impls could only come from dependencies of this crate,
         // which we already know about.
-        return Ok(());
+        return Ok(Ok(()));
     }
 
     // This is a remote non-fundamental trait, so if another crate
@@ -487,10 +488,10 @@ pub fn trait_ref_is_knowable<'tcx>(
     // and if we are an intermediate owner, then we don't care
     // about future-compatibility, which means that we're OK if
     // we are an owner.
-    if orphan_check_trait_ref(trait_ref, InCrate::Local).is_ok() {
-        Ok(())
+    if orphan_check_trait_ref(trait_ref, InCrate::Local, &mut lazily_normalize_ty)?.is_ok() {
+        Ok(Ok(()))
     } else {
-        Err(Conflict::Upstream)
+        Ok(Err(Conflict::Upstream))
     }
 }
 
@@ -526,7 +527,7 @@ pub fn orphan_check(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Result<(), OrphanChe
         return Ok(());
     }
 
-    orphan_check_trait_ref(trait_ref, InCrate::Local)
+    orphan_check_trait_ref::<!>(trait_ref, InCrate::Local, |ty| Ok(ty)).unwrap()
 }
 
 /// Checks whether a trait-ref is potentially implementable by a crate.
@@ -615,11 +616,12 @@ pub fn orphan_check(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Result<(), OrphanChe
 ///
 /// Note that this function is never called for types that have both type
 /// parameters and inference variables.
-#[instrument(level = "trace", ret)]
-fn orphan_check_trait_ref<'tcx>(
+#[instrument(level = "trace", skip(lazily_normalize_ty), ret)]
+fn orphan_check_trait_ref<'tcx, E: Debug>(
     trait_ref: ty::TraitRef<'tcx>,
     in_crate: InCrate,
-) -> Result<(), OrphanCheckErr<'tcx>> {
+    lazily_normalize_ty: impl FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
+) -> Result<Result<(), OrphanCheckErr<'tcx>>, E> {
     if trait_ref.has_infer() && trait_ref.has_param() {
         bug!(
             "can't orphan check a trait ref with both params and inference variables {:?}",
@@ -627,9 +629,10 @@ fn orphan_check_trait_ref<'tcx>(
         );
     }
 
-    let mut checker = OrphanChecker::new(in_crate);
-    match trait_ref.visit_with(&mut checker) {
+    let mut checker = OrphanChecker::new(in_crate, lazily_normalize_ty);
+    Ok(match trait_ref.visit_with(&mut checker) {
         ControlFlow::Continue(()) => Err(OrphanCheckErr::NonLocalInputType(checker.non_local_tys)),
+        ControlFlow::Break(OrphanCheckEarlyExit::NormalizationFailure(err)) => return Err(err),
         ControlFlow::Break(OrphanCheckEarlyExit::ParamTy(ty)) => {
             // Does there exist some local type after the `ParamTy`.
             checker.search_first_local_ty = true;
@@ -642,34 +645,39 @@ fn orphan_check_trait_ref<'tcx>(
             }
         }
         ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(_)) => Ok(()),
-    }
+    })
 }
 
-struct OrphanChecker<'tcx> {
+struct OrphanChecker<'tcx, F> {
     in_crate: InCrate,
     in_self_ty: bool,
+    lazily_normalize_ty: F,
     /// Ignore orphan check failures and exclusively search for the first
     /// local type.
     search_first_local_ty: bool,
     non_local_tys: Vec<(Ty<'tcx>, bool)>,
 }
 
-impl<'tcx> OrphanChecker<'tcx> {
-    fn new(in_crate: InCrate) -> Self {
+impl<'tcx, F, E> OrphanChecker<'tcx, F>
+where
+    F: FnOnce(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
+{
+    fn new(in_crate: InCrate, lazily_normalize_ty: F) -> Self {
         OrphanChecker {
             in_crate,
             in_self_ty: true,
+            lazily_normalize_ty,
             search_first_local_ty: false,
             non_local_tys: Vec::new(),
         }
     }
 
-    fn found_non_local_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<OrphanCheckEarlyExit<'tcx>> {
+    fn found_non_local_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<OrphanCheckEarlyExit<'tcx, E>> {
         self.non_local_tys.push((t, self.in_self_ty));
         ControlFlow::Continue(())
     }
 
-    fn found_param_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<OrphanCheckEarlyExit<'tcx>> {
+    fn found_param_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<OrphanCheckEarlyExit<'tcx, E>> {
         if self.search_first_local_ty {
             ControlFlow::Continue(())
         } else {
@@ -685,18 +693,28 @@ impl<'tcx> OrphanChecker<'tcx> {
     }
 }
 
-enum OrphanCheckEarlyExit<'tcx> {
+enum OrphanCheckEarlyExit<'tcx, E> {
+    NormalizationFailure(E),
     ParamTy(Ty<'tcx>),
     LocalTy(Ty<'tcx>),
 }
 
-impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for OrphanChecker<'tcx> {
-    type BreakTy = OrphanCheckEarlyExit<'tcx>;
+impl<'tcx, F, E> TypeVisitor<TyCtxt<'tcx>> for OrphanChecker<'tcx, F>
+where
+    F: FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
+{
+    type BreakTy = OrphanCheckEarlyExit<'tcx, E>;
     fn visit_region(&mut self, _r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
         ControlFlow::Continue(())
     }
 
     fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+        // Need to lazily normalize here in with `-Ztrait-solver=next-coherence`.
+        let ty = match (self.lazily_normalize_ty)(ty) {
+            Ok(ty) => ty,
+            Err(err) => return ControlFlow::Break(OrphanCheckEarlyExit::NormalizationFailure(err)),
+        };
+
         let result = match *ty.kind() {
             ty::Bool
             | ty::Char
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 4371b6c1239..840980da30d 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -1457,7 +1457,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // bound regions.
         let trait_ref = predicate.skip_binder().trait_ref;
 
-        coherence::trait_ref_is_knowable(self.tcx(), trait_ref)
+        coherence::trait_ref_is_knowable::<!>(self.tcx(), trait_ref, |ty| Ok(ty)).unwrap()
     }
 
     /// Returns `true` if the global caches can be used.
diff --git a/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-norm-overflow.rs b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-norm-overflow.rs
new file mode 100644
index 00000000000..b39ae0333ad
--- /dev/null
+++ b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-norm-overflow.rs
@@ -0,0 +1,20 @@
+// compile-flags: -Ztrait-solver=next
+
+// Coherence should handle overflow while normalizing for
+// `trait_ref_is_knowable` correctly.
+
+trait Overflow {
+    type Assoc;
+}
+impl<T> Overflow for T {
+    type Assoc = <T as Overflow>::Assoc;
+}
+
+
+trait Trait {}
+impl<T: Copy> Trait for T {}
+struct LocalTy;
+impl Trait for <LocalTy as Overflow>::Assoc {}
+//~^ ERROR conflicting implementations of trait `Trait` for type `<LocalTy as Overflow>::Assoc`
+
+fn main() {}
diff --git a/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-norm-overflow.stderr b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-norm-overflow.stderr
new file mode 100644
index 00000000000..5d5f325e4b4
--- /dev/null
+++ b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-norm-overflow.stderr
@@ -0,0 +1,12 @@
+error[E0119]: conflicting implementations of trait `Trait` for type `<LocalTy as Overflow>::Assoc`
+  --> $DIR/trait_ref_is_knowable-norm-overflow.rs:17:1
+   |
+LL | impl<T: Copy> Trait for T {}
+   | ------------------------- first implementation here
+LL | struct LocalTy;
+LL | impl Trait for <LocalTy as Overflow>::Assoc {}
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `<LocalTy as Overflow>::Assoc`
+
+error: aborting due to previous error
+
+For more information about this error, try `rustc --explain E0119`.
diff --git a/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-1.rs b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-1.rs
new file mode 100644
index 00000000000..c38e3baf5b4
--- /dev/null
+++ b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-1.rs
@@ -0,0 +1,22 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+
+trait Id {
+    type Assoc;
+}
+impl<T> Id for T {
+    type Assoc = T;
+}
+
+
+// Coherence should be able to reason that `<LocalTy as Id>::Assoc: Copy`
+// does not hold.
+//
+// See https://github.com/rust-lang/trait-system-refactor-initiative/issues/51
+// for more details.
+trait Trait {}
+impl<T: Copy> Trait for T {}
+struct LocalTy;
+impl Trait for <LocalTy as Id>::Assoc {}
+
+fn main() {}
diff --git a/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-2.rs b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-2.rs
new file mode 100644
index 00000000000..2d53266db09
--- /dev/null
+++ b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-2.rs
@@ -0,0 +1,25 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+
+use std::future::{Future, IntoFuture};
+use std::pin::Pin;
+
+// We check that this does not overlap with the following impl from std:
+//     impl<P> Future for Pin<P> where P: DerefMut, <P as Deref>::Target: Future { .. }
+// This should fail because we know ` <&mut Value as Deref>::Target: Future` not to hold.
+// For this to work we have to normalize in the `trait_ref_is_knowable` check as we
+// otherwise add an ambiguous candidate here.
+//
+// See https://github.com/rust-lang/trait-system-refactor-initiative/issues/51
+// for more details.
+struct Value;
+impl<'a> IntoFuture for Pin<&'a mut Value> {
+    type Output = ();
+    type IntoFuture = Pin<Box<dyn Future<Output = ()> + Send>>;
+
+    fn into_future(self) -> Self::IntoFuture {
+        todo!()
+    }
+}
+
+fn main() {}
diff --git a/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-3.rs b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-3.rs
new file mode 100644
index 00000000000..2f27de4e4f4
--- /dev/null
+++ b/tests/ui/traits/new-solver/coherence/trait_ref_is_knowable-normalization-3.rs
@@ -0,0 +1,24 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+
+trait Id {
+    type Assoc;
+}
+impl<T> Id for T {
+    type Assoc = T;
+}
+
+
+// Coherence should be able to reason that `(): PartialEq<<T as Id>::Assoc>>`
+// does not hold.
+//
+// See https://github.com/rust-lang/trait-system-refactor-initiative/issues/51
+// for more details.
+trait Trait {}
+impl<T> Trait for T
+where
+    (): PartialEq<T> {}
+struct LocalTy;
+impl Trait for <LocalTy as Id>::Assoc {}
+
+fn main() {}