use alias-relate to structurally normalize in the solver

7 files changed, 83 insertions, 92 deletions

diff --git a/compiler/rustc_hir_typeck/src/lib.rs b/compiler/rustc_hir_typeck/src/lib.rs
index 6d343b3d05e..629c2f2a971 100644
--- a/compiler/rustc_hir_typeck/src/lib.rs
+++ b/compiler/rustc_hir_typeck/src/lib.rs
@@ -304,6 +304,8 @@ fn typeck_with_fallback<'tcx>(
 
     let typeck_results = fcx.resolve_type_vars_in_body(body);
 
+    // We clone the defined opaque types during writeback in the new solver
+    // because we have to use them during normalization.
     let _ = fcx.infcx.take_opaque_types();
 
     // Consistency check our TypeckResults instance can hold all ItemLocalIds
diff --git a/compiler/rustc_hir_typeck/src/writeback.rs b/compiler/rustc_hir_typeck/src/writeback.rs
index 26279098d9e..d84bce09ecb 100644
--- a/compiler/rustc_hir_typeck/src/writeback.rs
+++ b/compiler/rustc_hir_typeck/src/writeback.rs
@@ -564,6 +564,12 @@ impl<'cx, 'tcx> WritebackCx<'cx, 'tcx> {
     fn visit_opaque_types(&mut self) {
         // We clone the opaques instead of stealing them here as they are still used for
         // normalization in the next generation trait solver.
+        //
+        // FIXME(-Znext-solver): Opaque types defined after this would simply get dropped
+        // at the end of typeck. While this seems unlikely to happen in practice this
+        // should still get fixed. Either by preventing writeback from defining new opaque
+        // types or by using this function at the end of writeback and running it as a
+        // fixpoint.
         let opaque_types = self.fcx.infcx.clone_opaque_types();
         for (opaque_type_key, decl) in opaque_types {
             let hidden_type = self.resolve(decl.hidden_type, &decl.hidden_type.span);
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
index 999367e7589..81be5c09164 100644
--- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs
+++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
@@ -21,10 +21,9 @@
 //! `NormalizesTo` goal, at which point the opaque is actually defined.
 
 use super::{EvalCtxt, GoalSource};
-use rustc_infer::infer::DefineOpaqueTypes;
 use rustc_infer::traits::query::NoSolution;
 use rustc_middle::traits::solve::{Certainty, Goal, QueryResult};
-use rustc_middle::ty;
+use rustc_middle::ty::{self, Ty};
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
     #[instrument(level = "debug", skip(self), ret)]
@@ -79,7 +78,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     }
 
     // FIXME: This needs a name that reflects that it's okay to bottom-out with an inference var.
-    /// Normalize the `term` to equate it later. This does not define opaque types.
+    /// Normalize the `term` to equate it later.
     #[instrument(level = "debug", skip(self, param_env), ret)]
     fn try_normalize_term(
         &mut self,
@@ -88,10 +87,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) -> Result<Option<ty::Term<'tcx>>, NoSolution> {
         match term.unpack() {
             ty::TermKind::Ty(ty) => {
-                // We do no define opaque types here but instead do so in `relate_rigid_alias_or_opaque`.
-                Ok(self
-                    .try_normalize_ty_recur(param_env, DefineOpaqueTypes::No, 0, ty)
-                    .map(Into::into))
+                Ok(self.try_normalize_ty_recur(param_env, 0, ty).map(Into::into))
             }
             ty::TermKind::Const(_) => {
                 if let Some(alias) = term.to_alias_ty(self.tcx()) {
@@ -108,4 +104,35 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             }
         }
     }
+
+    fn try_normalize_ty_recur(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        depth: usize,
+        ty: Ty<'tcx>,
+    ) -> Option<Ty<'tcx>> {
+        if !self.tcx().recursion_limit().value_within_limit(depth) {
+            return None;
+        }
+
+        let ty::Alias(_, alias) = *ty.kind() else {
+            return Some(ty);
+        };
+
+        match self.commit_if_ok(|this| {
+            let normalized_ty = this.next_ty_infer();
+            let normalizes_to_goal = Goal::new(
+                this.tcx(),
+                param_env,
+                ty::NormalizesTo { alias, term: normalized_ty.into() },
+            );
+            this.add_goal(GoalSource::Misc, normalizes_to_goal);
+            this.try_evaluate_added_goals()?;
+            let ty = this.resolve_vars_if_possible(normalized_ty);
+            Ok(this.try_normalize_ty_recur(param_env, depth + 1, ty))
+        }) {
+            Ok(ty) => ty,
+            Err(NoSolution) => Some(ty),
+        }
+    }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 6833d2ae330..733c415ead5 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -276,11 +276,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         &mut self,
         goal: Goal<'tcx, G>,
     ) -> Vec<Candidate<'tcx>> {
-        let Some(normalized_self_ty) =
-            self.try_normalize_ty(goal.param_env, goal.predicate.self_ty())
+        let Ok(normalized_self_ty) =
+            self.structurally_normalize_ty(goal.param_env, goal.predicate.self_ty())
         else {
-            debug!("overflow while evaluating self type");
-            return self.forced_ambiguity(MaybeCause::Overflow);
+            return vec![];
         };
 
         if normalized_self_ty.is_ty_var() {
@@ -635,19 +634,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             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 });
-                }
+        // Recurse on the self type of the projection.
+        match self.structurally_normalize_ty(goal.param_env, alias_ty.self_ty()) {
+            Ok(next_self_ty) => {
+                self.assemble_alias_bound_candidates_recur(next_self_ty, goal, candidates)
             }
+            Err(NoSolution) => {}
         }
     }
 
@@ -857,19 +849,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         let tcx = self.tcx();
         let result = self.probe_misc_candidate("coherence unknowable").enter(|ecx| {
             let trait_ref = goal.predicate.trait_ref(tcx);
-            #[derive(Debug)]
-            struct Overflow;
-            let lazily_normalize_ty = |ty| match ecx.try_normalize_ty(goal.param_env, ty) {
-                Some(ty) => Ok(ty),
-                None => Err(Overflow),
-            };
+            let lazily_normalize_ty = |ty| ecx.structurally_normalize_ty(goal.param_env, ty);
 
-            match coherence::trait_ref_is_knowable(tcx, trait_ref, lazily_normalize_ty) {
-                Err(Overflow) => {
-                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW)
-                }
-                Ok(Ok(())) => Err(NoSolution),
-                Ok(Err(_)) => {
+            match coherence::trait_ref_is_knowable(tcx, trait_ref, lazily_normalize_ty)? {
+                Ok(()) => Err(NoSolution),
+                Err(_) => {
                     ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
                 }
             }
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 2331931b7b7..94a3cef8ad1 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -15,14 +15,13 @@
 //! about it on zulip.
 use rustc_hir::def_id::DefId;
 use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues};
-use rustc_infer::infer::DefineOpaqueTypes;
 use rustc_infer::traits::query::NoSolution;
 use rustc_middle::infer::canonical::CanonicalVarInfos;
 use rustc_middle::traits::solve::{
     CanonicalResponse, Certainty, ExternalConstraintsData, Goal, GoalSource, IsNormalizesToHack,
     QueryResult, Response,
 };
-use rustc_middle::ty::{self, Ty, TyCtxt, UniverseIndex};
+use rustc_middle::ty::{self, AliasRelationDirection, Ty, TyCtxt, UniverseIndex};
 use rustc_middle::ty::{
     CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate,
 };
@@ -266,49 +265,32 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         Ok(self.make_ambiguous_response_no_constraints(maybe_cause))
     }
 
-    /// Normalize a type when it is structually matched on.
+    /// Normalize a type for when it is structurally matched on.
     ///
-    /// In nearly all cases this function must be used before matching on a type.
+    /// This function is necessary in nearly all cases before matching on a type.
     /// Not doing so is likely to be incomplete and therefore unsound during
     /// coherence.
-    #[instrument(level = "debug", skip(self), ret)]
-    fn try_normalize_ty(
-        &mut self,
-        param_env: ty::ParamEnv<'tcx>,
-        ty: Ty<'tcx>,
-    ) -> Option<Ty<'tcx>> {
-        self.try_normalize_ty_recur(param_env, DefineOpaqueTypes::Yes, 0, ty)
-    }
-
-    fn try_normalize_ty_recur(
+    fn structurally_normalize_ty(
         &mut self,
         param_env: ty::ParamEnv<'tcx>,
-        define_opaque_types: DefineOpaqueTypes,
-        depth: usize,
         ty: Ty<'tcx>,
-    ) -> Option<Ty<'tcx>> {
-        if !self.tcx().recursion_limit().value_within_limit(depth) {
-            return None;
-        }
-
-        let ty::Alias(_, alias) = *ty.kind() else {
-            return Some(ty);
-        };
-
-        match self.commit_if_ok(|this| {
-            let normalized_ty = this.next_ty_infer();
-            let normalizes_to_goal = Goal::new(
-                this.tcx(),
+    ) -> Result<Ty<'tcx>, NoSolution> {
+        if let ty::Alias(..) = ty.kind() {
+            let normalized_ty = self.next_ty_infer();
+            let alias_relate_goal = Goal::new(
+                self.tcx(),
                 param_env,
-                ty::NormalizesTo { alias, term: normalized_ty.into() },
+                ty::PredicateKind::AliasRelate(
+                    ty.into(),
+                    normalized_ty.into(),
+                    AliasRelationDirection::Equate,
+                ),
             );
-            this.add_goal(GoalSource::Misc, normalizes_to_goal);
-            this.try_evaluate_added_goals()?;
-            let ty = this.resolve_vars_if_possible(normalized_ty);
-            Ok(this.try_normalize_ty_recur(param_env, define_opaque_types, depth + 1, ty))
-        }) {
-            Ok(ty) => ty,
-            Err(NoSolution) => Some(ty),
+            self.add_goal(GoalSource::Misc, alias_relate_goal);
+            self.try_evaluate_added_goals()?;
+            Ok(self.resolve_vars_if_possible(normalized_ty))
+        } else {
+            Ok(ty)
         }
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs
index b5d1aa06e4e..356c3776c04 100644
--- a/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs
+++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/opaques.rs
@@ -58,21 +58,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                     }
                 }
 
-                let expected = match self.try_normalize_ty(goal.param_env, expected) {
-                    Some(ty) => {
-                        if ty.is_ty_var() {
-                            return self.evaluate_added_goals_and_make_canonical_response(
-                                Certainty::AMBIGUOUS,
-                            );
-                        } else {
-                            ty
-                        }
-                    }
-                    None => {
-                        return self
-                            .evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW);
-                    }
-                };
+                let expected = self.structurally_normalize_ty(goal.param_env, expected)?;
+                if expected.is_ty_var() {
+                    return self
+                        .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
+                }
 
                 // Otherwise, define a new opaque type
                 self.insert_hidden_type(opaque_type_key, goal.param_env, expected)?;
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index 32b46c7ac44..50de483add1 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -581,11 +581,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             let a_ty = goal.predicate.self_ty();
             // We need to normalize the b_ty since it's matched structurally
             // in the other functions below.
-            let b_ty = match ecx
-                .try_normalize_ty(goal.param_env, goal.predicate.trait_ref.args.type_at(1))
-            {
-                Some(b_ty) => b_ty,
-                None => return vec![misc_candidate(ecx, Certainty::OVERFLOW)],
+            let Ok(b_ty) = ecx.structurally_normalize_ty(
+                goal.param_env,
+                goal.predicate.trait_ref.args.type_at(1),
+            ) else {
+                return vec![];
             };
 
             let goal = goal.with(ecx.tcx(), (a_ty, b_ty));