fix `NormalizesTo` proof tree issue

4 files changed, 177 insertions, 52 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 1c13446213b..00fe9bc12b5 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -14,6 +14,7 @@ use rustc_ast_ir::visit::VisitorResult;
 use rustc_infer::infer::resolve::EagerResolver;
 use rustc_infer::infer::type_variable::TypeVariableOrigin;
 use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, InferOk};
+use rustc_infer::traits::{TraitEngine, TraitEngineExt};
 use rustc_macros::extension;
 use rustc_middle::infer::unify_key::ConstVariableOrigin;
 use rustc_middle::traits::query::NoSolution;
@@ -22,9 +23,10 @@ use rustc_middle::traits::solve::{Certainty, Goal};
 use rustc_middle::traits::ObligationCause;
 use rustc_middle::ty;
 use rustc_middle::ty::TypeFoldable;
-use rustc_span::Span;
+use rustc_span::{Span, DUMMY_SP};
 
 use crate::solve::eval_ctxt::canonical;
+use crate::solve::FulfillmentCtxt;
 use crate::solve::{EvalCtxt, GoalEvaluationKind, GoalSource};
 use crate::solve::{GenerateProofTree, InferCtxtEvalExt};
 
@@ -37,7 +39,52 @@ pub struct InspectGoal<'a, 'tcx> {
     depth: usize,
     orig_values: Vec<ty::GenericArg<'tcx>>,
     goal: Goal<'tcx, ty::Predicate<'tcx>>,
-    evaluation: inspect::CanonicalGoalEvaluation<'tcx>,
+    result: Result<Certainty, NoSolution>,
+    evaluation_kind: inspect::CanonicalGoalEvaluationKind<'tcx>,
+    /// The expected term of a `NormalizesTo` goal. It gets
+    /// replaced with an unconstrained inference variable when
+    /// computing `NormalizesTo` goals and we return the nested
+    /// goals to the caller, who also equates the actual term
+    /// with the expected.
+    ///
+    /// This is an implementation detail of the trait solver and
+    /// not something we want to leak to users. We therefore
+    /// treat `NormalizesTo` goals as if they apply the expected
+    /// type at the end of each candidate.
+    normalizes_to_term_hack: Option<NormalizesToTermHack<'tcx>>,
+}
+
+#[derive(Copy, Clone)]
+struct NormalizesToTermHack<'tcx> {
+    term: ty::Term<'tcx>,
+    unconstrained_term: ty::Term<'tcx>,
+}
+
+impl<'tcx> NormalizesToTermHack<'tcx> {
+    fn relate(
+        self,
+        infcx: &InferCtxt<'tcx>,
+        span: Span,
+        param_env: ty::ParamEnv<'tcx>,
+    ) -> Result<Certainty, NoSolution> {
+        infcx
+            .at(&ObligationCause::dummy_with_span(span), param_env)
+            .eq(DefineOpaqueTypes::Yes, self.term, self.unconstrained_term)
+            .map_err(|_| NoSolution)
+            .and_then(|InferOk { value: (), obligations }| {
+                let mut fulfill_cx = FulfillmentCtxt::new(infcx);
+                fulfill_cx.register_predicate_obligations(infcx, obligations);
+                if fulfill_cx.select_where_possible(infcx).is_empty() {
+                    if fulfill_cx.pending_obligations().is_empty() {
+                        Ok(Certainty::Yes)
+                    } else {
+                        Ok(Certainty::AMBIGUOUS)
+                    }
+                } else {
+                    Err(NoSolution)
+                }
+            })
+    }
 }
 
 pub struct InspectCandidate<'a, 'tcx> {
@@ -115,42 +162,47 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
             self.final_state,
         );
 
+        if let Some(term_hack) = self.goal.normalizes_to_term_hack {
+            // FIXME: We ignore the expected term of `NormalizesTo` goals
+            // when computing the result of its candidates. This is
+            // scuffed.
+            let _ = term_hack.relate(infcx, span, param_env);
+        }
+
         instantiated_goals
             .into_iter()
-            .map(|goal| {
-                let proof_tree = match goal.predicate.kind().no_bound_vars() {
-                    Some(ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term })) => {
-                        let unconstrained_term = match term.unpack() {
-                            ty::TermKind::Ty(_) => infcx
-                                .next_ty_var(TypeVariableOrigin { param_def_id: None, span })
-                                .into(),
-                            ty::TermKind::Const(ct) => infcx
-                                .next_const_var(
-                                    ct.ty(),
-                                    ConstVariableOrigin { param_def_id: None, span },
-                                )
-                                .into(),
-                        };
-                        let goal = goal
-                            .with(infcx.tcx, ty::NormalizesTo { alias, term: unconstrained_term });
-                        let proof_tree =
-                            EvalCtxt::enter_root(infcx, GenerateProofTree::Yes, |ecx| {
-                                ecx.evaluate_goal_raw(
-                                    GoalEvaluationKind::Root,
-                                    GoalSource::Misc,
-                                    goal,
-                                )
-                            })
-                            .1;
-                        let InferOk { value: (), obligations: _ } = infcx
-                            .at(&ObligationCause::dummy_with_span(span), param_env)
-                            .eq(DefineOpaqueTypes::Yes, term, unconstrained_term)
-                            .unwrap();
-                        proof_tree
-                    }
-                    _ => infcx.evaluate_root_goal(goal, GenerateProofTree::Yes).1,
-                };
-                InspectGoal::new(infcx, self.goal.depth + 1, proof_tree.unwrap())
+            .map(|goal| match goal.predicate.kind().no_bound_vars() {
+                Some(ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term })) => {
+                    let unconstrained_term = match term.unpack() {
+                        ty::TermKind::Ty(_) => infcx
+                            .next_ty_var(TypeVariableOrigin { param_def_id: None, span })
+                            .into(),
+                        ty::TermKind::Const(ct) => infcx
+                            .next_const_var(
+                                ct.ty(),
+                                ConstVariableOrigin { param_def_id: None, span },
+                            )
+                            .into(),
+                    };
+                    let goal =
+                        goal.with(infcx.tcx, ty::NormalizesTo { alias, term: unconstrained_term });
+                    let proof_tree = EvalCtxt::enter_root(infcx, GenerateProofTree::Yes, |ecx| {
+                        ecx.evaluate_goal_raw(GoalEvaluationKind::Root, GoalSource::Misc, goal)
+                    })
+                    .1;
+                    InspectGoal::new(
+                        infcx,
+                        self.goal.depth + 1,
+                        proof_tree.unwrap(),
+                        Some(NormalizesToTermHack { term, unconstrained_term }),
+                    )
+                }
+                _ => InspectGoal::new(
+                    infcx,
+                    self.goal.depth + 1,
+                    infcx.evaluate_root_goal(goal, GenerateProofTree::Yes).1.unwrap(),
+                    None,
+                ),
             })
             .collect()
     }
@@ -172,7 +224,7 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
     }
 
     pub fn result(&self) -> Result<Certainty, NoSolution> {
-        self.evaluation.result.map(|c| c.value.certainty)
+        self.result
     }
 
     fn candidates_recur(
@@ -229,11 +281,11 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
 
     pub fn candidates(&'a self) -> Vec<InspectCandidate<'a, 'tcx>> {
         let mut candidates = vec![];
-        let last_eval_step = match self.evaluation.kind {
+        let last_eval_step = match self.evaluation_kind {
             inspect::CanonicalGoalEvaluationKind::Overflow
             | inspect::CanonicalGoalEvaluationKind::CycleInStack
             | inspect::CanonicalGoalEvaluationKind::ProvisionalCacheHit => {
-                warn!("unexpected root evaluation: {:?}", self.evaluation);
+                warn!("unexpected root evaluation: {:?}", self.evaluation_kind);
                 return vec![];
             }
             inspect::CanonicalGoalEvaluationKind::Evaluation { revisions } => {
@@ -262,17 +314,33 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
         candidates.pop().filter(|_| candidates.is_empty())
     }
 
-    fn new(infcx: &'a InferCtxt<'tcx>, depth: usize, root: inspect::GoalEvaluation<'tcx>) -> Self {
+    fn new(
+        infcx: &'a InferCtxt<'tcx>,
+        depth: usize,
+        root: inspect::GoalEvaluation<'tcx>,
+        normalizes_to_term_hack: Option<NormalizesToTermHack<'tcx>>,
+    ) -> Self {
         let inspect::GoalEvaluation { uncanonicalized_goal, kind, evaluation } = root;
-        match kind {
-            inspect::GoalEvaluationKind::Root { orig_values } => InspectGoal {
-                infcx,
-                depth,
-                orig_values,
-                goal: uncanonicalized_goal.fold_with(&mut EagerResolver::new(infcx)),
-                evaluation,
-            },
-            inspect::GoalEvaluationKind::Nested { .. } => unreachable!(),
+        let inspect::GoalEvaluationKind::Root { orig_values } = kind else { unreachable!() };
+
+        let result = evaluation.result.and_then(|ok| {
+            if let Some(term_hack) = normalizes_to_term_hack {
+                infcx
+                    .probe(|_| term_hack.relate(infcx, DUMMY_SP, uncanonicalized_goal.param_env))
+                    .map(|certainty| ok.value.certainty.unify_with(certainty))
+            } else {
+                Ok(ok.value.certainty)
+            }
+        });
+
+        InspectGoal {
+            infcx,
+            depth,
+            orig_values,
+            goal: uncanonicalized_goal.fold_with(&mut EagerResolver::new(infcx)),
+            result,
+            evaluation_kind: evaluation.kind,
+            normalizes_to_term_hack,
         }
     }
 }
@@ -299,6 +367,6 @@ impl<'tcx> InferCtxt<'tcx> {
     ) -> V::Result {
         let (_, proof_tree) = self.evaluate_root_goal(goal, GenerateProofTree::Yes);
         let proof_tree = proof_tree.unwrap();
-        visitor.visit_goal(&InspectGoal::new(self, 0, proof_tree))
+        visitor.visit_goal(&InspectGoal::new(self, 0, proof_tree, None))
     }
 }
diff --git a/tests/ui/specialization/specialization-overlap-projection.stderr b/tests/ui/specialization/specialization-overlap-projection.current.stderr
index 708c0817fd9..a69826fa96b 100644
--- a/tests/ui/specialization/specialization-overlap-projection.stderr
+++ b/tests/ui/specialization/specialization-overlap-projection.current.stderr
@@ -1,5 +1,5 @@
 warning: the feature `specialization` is incomplete and may not be safe to use and/or cause compiler crashes
-  --> $DIR/specialization-overlap-projection.rs:7:12
+  --> $DIR/specialization-overlap-projection.rs:10:12
    |
 LL | #![feature(specialization)]
    |            ^^^^^^^^^^^^^^
diff --git a/tests/ui/specialization/specialization-overlap-projection.next.stderr b/tests/ui/specialization/specialization-overlap-projection.next.stderr
new file mode 100644
index 00000000000..ab040193fa4
--- /dev/null
+++ b/tests/ui/specialization/specialization-overlap-projection.next.stderr
@@ -0,0 +1,49 @@
+warning: the feature `specialization` is incomplete and may not be safe to use and/or cause compiler crashes
+  --> $DIR/specialization-overlap-projection.rs:10:12
+   |
+LL | #![feature(specialization)]
+   |            ^^^^^^^^^^^^^^
+   |
+   = note: see issue #31844 <https://github.com/rust-lang/rust/issues/31844> for more information
+   = help: consider using `min_specialization` instead, which is more stable and complete
+   = note: `#[warn(incomplete_features)]` on by default
+
+error[E0119]: conflicting implementations of trait `Foo` for type `u32`
+  --> $DIR/specialization-overlap-projection.rs:28:1
+   |
+LL | impl Foo for u32 {}
+   | ---------------- first implementation here
+LL | impl Foo for <u8 as Assoc>::Output {}
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `u32`
+
+error[E0119]: conflicting implementations of trait `Foo` for type `u32`
+  --> $DIR/specialization-overlap-projection.rs:30:1
+   |
+LL | impl Foo for u32 {}
+   | ---------------- first implementation here
+...
+LL | impl Foo for <u16 as Assoc>::Output {}
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `u32`
+
+error[E0282]: type annotations needed
+  --> $DIR/specialization-overlap-projection.rs:17:27
+   |
+LL |     default type Output = bool;
+   |                           ^^^^ cannot infer type for associated type `<T as Assoc>::Output`
+
+error[E0282]: type annotations needed
+  --> $DIR/specialization-overlap-projection.rs:21:35
+   |
+LL | impl Assoc for u8 { type Output = u8; }
+   |                                   ^^ cannot infer type for associated type `<u8 as Assoc>::Output`
+
+error[E0282]: type annotations needed
+  --> $DIR/specialization-overlap-projection.rs:23:36
+   |
+LL | impl Assoc for u16 { type Output = u16; }
+   |                                    ^^^ cannot infer type for associated type `<u16 as Assoc>::Output`
+
+error: aborting due to 5 previous errors; 1 warning emitted
+
+Some errors have detailed explanations: E0119, E0282.
+For more information about an error, try `rustc --explain E0119`.
diff --git a/tests/ui/specialization/specialization-overlap-projection.rs b/tests/ui/specialization/specialization-overlap-projection.rs
index 66951b9d50c..78e75f623c4 100644
--- a/tests/ui/specialization/specialization-overlap-projection.rs
+++ b/tests/ui/specialization/specialization-overlap-projection.rs
@@ -1,4 +1,7 @@
-//@ check-pass
+//@ revisions: current next
+//@ ignore-compare-mode-next-solver (explicit revisions)
+//@[next] compile-flags: -Znext-solver
+//@[current] check-pass
 
 // Test that impls on projected self types can resolve overlap, even when the
 // projections involve specialization, so long as the associated type is
@@ -12,14 +15,19 @@ trait Assoc {
 
 impl<T> Assoc for T {
     default type Output = bool;
+    //[next]~^ ERROR type annotations needed
 }
 
 impl Assoc for u8 { type Output = u8; }
+//[next]~^ ERROR type annotations needed
 impl Assoc for u16 { type Output = u16; }
+//[next]~^ ERROR type annotations needed
 
 trait Foo {}
 impl Foo for u32 {}
 impl Foo for <u8 as Assoc>::Output {}
+//[next]~^ ERROR conflicting implementations of trait `Foo` for type `u32`
 impl Foo for <u16 as Assoc>::Output {}
+//[next]~^ ERROR conflicting implementations of trait `Foo` for type `u32`
 
 fn main() {}