Rollup merge of #140402 - lcnr:normalizes-to-certainty-yes, r=compiler-errors

only return nested goals for `Certainty::Yes`

Ambiguous `NormalizesTo` goals can otherwise repeatedly add the same nested goals to the parent.

r? ```@compiler-errors```

3 files changed, 66 insertions, 32 deletions

diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs
index 04f80a056f9..dded84f6768 100644
--- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/canonical.rs
@@ -81,12 +81,19 @@ where
     ///   the values inferred while solving the instantiated goal.
     /// - `external_constraints`: additional constraints which aren't expressible
     ///   using simple unification of inference variables.
+    ///
+    /// This takes the `shallow_certainty` which represents whether we're confident
+    /// that the final result of the current goal only depends on the nested goals.
+    ///
+    /// In case this is `Certainy::Maybe`, there may still be additional nested goals
+    /// or inference constraints required for this candidate to be hold. The candidate
+    /// always requires all already added constraints and nested goals.
     #[instrument(level = "trace", skip(self), ret)]
     pub(in crate::solve) fn evaluate_added_goals_and_make_canonical_response(
         &mut self,
-        certainty: Certainty,
+        shallow_certainty: Certainty,
     ) -> QueryResult<I> {
-        self.inspect.make_canonical_response(certainty);
+        self.inspect.make_canonical_response(shallow_certainty);
 
         let goals_certainty = self.try_evaluate_added_goals()?;
         assert_eq!(
@@ -103,26 +110,29 @@ where
             NoSolution
         })?;
 
-        // When normalizing, we've replaced the expected term with an unconstrained
-        // inference variable. This means that we dropped information which could
-        // have been important. We handle this by instead returning the nested goals
-        // to the caller, where they are then handled.
-        //
-        // As we return all ambiguous nested goals, we can ignore the certainty returned
-        // by `try_evaluate_added_goals()`.
-        let (certainty, normalization_nested_goals) = match self.current_goal_kind {
-            CurrentGoalKind::NormalizesTo => {
-                let goals = std::mem::take(&mut self.nested_goals);
-                if goals.is_empty() {
-                    assert!(matches!(goals_certainty, Certainty::Yes));
+        let (certainty, normalization_nested_goals) =
+            match (self.current_goal_kind, shallow_certainty) {
+                // When normalizing, we've replaced the expected term with an unconstrained
+                // inference variable. This means that we dropped information which could
+                // have been important. We handle this by instead returning the nested goals
+                // to the caller, where they are then handled. We only do so if we do not
+                // need to recompute the `NormalizesTo` goal afterwards to avoid repeatedly
+                // uplifting its nested goals. This is the case if the `shallow_certainty` is
+                // `Certainty::Yes`.
+                (CurrentGoalKind::NormalizesTo, Certainty::Yes) => {
+                    let goals = std::mem::take(&mut self.nested_goals);
+                    // As we return all ambiguous nested goals, we can ignore the certainty
+                    // returned by `self.try_evaluate_added_goals()`.
+                    if goals.is_empty() {
+                        assert!(matches!(goals_certainty, Certainty::Yes));
+                    }
+                    (Certainty::Yes, NestedNormalizationGoals(goals))
                 }
-                (certainty, NestedNormalizationGoals(goals))
-            }
-            CurrentGoalKind::Misc | CurrentGoalKind::CoinductiveTrait => {
-                let certainty = certainty.unify_with(goals_certainty);
-                (certainty, NestedNormalizationGoals::empty())
-            }
-        };
+                _ => {
+                    let certainty = shallow_certainty.unify_with(goals_certainty);
+                    (certainty, NestedNormalizationGoals::empty())
+                }
+            };
 
         if let Certainty::Maybe(cause @ MaybeCause::Overflow { .. }) = certainty {
             // If we have overflow, it's probable that we're substituting a type
diff --git a/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs
index 87faf99ced6..b030af48381 100644
--- a/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/mod.rs
@@ -6,7 +6,7 @@ mod opaque_types;
 use rustc_type_ir::fast_reject::DeepRejectCtxt;
 use rustc_type_ir::inherent::*;
 use rustc_type_ir::lang_items::TraitSolverLangItem;
-use rustc_type_ir::{self as ty, Interner, NormalizesTo, Upcast as _};
+use rustc_type_ir::{self as ty, Interner, NormalizesTo, PredicateKind, Upcast as _};
 use tracing::instrument;
 
 use crate::delegate::SolverDelegate;
@@ -227,13 +227,21 @@ where
                 Ok(Some(target_item_def_id)) => target_item_def_id,
                 Ok(None) => {
                     match ecx.typing_mode() {
-                        // In case the associated item is hidden due to specialization, we have to
-                        // return ambiguity this would otherwise be incomplete, resulting in
-                        // unsoundness during coherence (#105782).
+                        // In case the associated item is hidden due to specialization,
+                        // normalizing this associated item is always ambiguous. Treating
+                        // the associated item as rigid would be incomplete and allow for
+                        // overlapping impls, see #105782.
+                        //
+                        // As this ambiguity is unavoidable we emit a nested ambiguous
+                        // goal instead of using `Certainty::AMBIGUOUS`. This allows us to
+                        // return the nested goals to the parent `AliasRelate` goal. This
+                        // would be relevant if any of the nested goals refer to the `term`.
+                        // This is not the case here and we only prefer adding an ambiguous
+                        // nested goal for consistency.
                         ty::TypingMode::Coherence => {
-                            return ecx.evaluate_added_goals_and_make_canonical_response(
-                                Certainty::AMBIGUOUS,
-                            );
+                            ecx.add_goal(GoalSource::Misc, goal.with(cx, PredicateKind::Ambiguous));
+                            return ecx
+                                .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
                         }
                         // Outside of coherence, we treat the associated item as rigid instead.
                         ty::TypingMode::Analysis { .. }
@@ -260,10 +268,20 @@ where
                 // treat it as rigid.
                 if cx.impl_self_is_guaranteed_unsized(impl_def_id) {
                     match ecx.typing_mode() {
+                        // Trying to normalize such associated items is always ambiguous
+                        // during coherence to avoid cyclic reasoning. See the example in
+                        // tests/ui/traits/trivial-unsized-projection-in-coherence.rs.
+                        //
+                        // As this ambiguity is unavoidable we emit a nested ambiguous
+                        // goal instead of using `Certainty::AMBIGUOUS`. This allows us to
+                        // return the nested goals to the parent `AliasRelate` goal. This
+                        // would be relevant if any of the nested goals refer to the `term`.
+                        // This is not the case here and we only prefer adding an ambiguous
+                        // nested goal for consistency.
                         ty::TypingMode::Coherence => {
-                            return ecx.evaluate_added_goals_and_make_canonical_response(
-                                Certainty::AMBIGUOUS,
-                            );
+                            ecx.add_goal(GoalSource::Misc, goal.with(cx, PredicateKind::Ambiguous));
+                            return ecx
+                                .evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
                         }
                         ty::TypingMode::Analysis { .. }
                         | ty::TypingMode::Borrowck { .. }
diff --git a/compiler/rustc_next_trait_solver/src/solve/normalizes_to/opaque_types.rs b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/opaque_types.rs
index ee439f1b3d0..df3ad1e468b 100644
--- a/compiler/rustc_next_trait_solver/src/solve/normalizes_to/opaque_types.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/normalizes_to/opaque_types.rs
@@ -3,6 +3,7 @@
 
 use rustc_index::bit_set::GrowableBitSet;
 use rustc_type_ir::inherent::*;
+use rustc_type_ir::solve::GoalSource;
 use rustc_type_ir::{self as ty, Interner, TypingMode, fold_regions};
 
 use crate::delegate::SolverDelegate;
@@ -31,7 +32,12 @@ where
                     goal.param_env,
                     expected,
                 );
-                self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
+                // Trying to normalize an opaque type during coherence is always ambiguous.
+                // We add a nested ambiguous goal here instead of using `Certainty::AMBIGUOUS`.
+                // This allows us to return the nested goals to the parent `AliasRelate` goal.
+                // This can then allow nested goals to fail after we've constrained the `term`.
+                self.add_goal(GoalSource::Misc, goal.with(cx, ty::PredicateKind::Ambiguous));
+                self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             }
             TypingMode::Analysis { defining_opaque_types_and_generators } => {
                 let Some(def_id) = opaque_ty