normalizes-to rework rigid alias handling

7 files changed, 77 insertions, 99 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 a3274fb4011..23fe88b1680 100644
--- a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
@@ -797,11 +797,12 @@ where
     /// treat the alias as rigid.
     ///
     /// See trait-system-refactor-initiative#124 for more details.
-    #[instrument(level = "debug", skip(self), ret)]
+    #[instrument(level = "debug", skip(self, inject_normalize_to_rigid_candidate), ret)]
     pub(super) fn merge_candidates(
         &mut self,
         proven_via: Option<TraitGoalProvenVia>,
         candidates: Vec<Candidate<I>>,
+        inject_normalize_to_rigid_candidate: impl FnOnce(&mut EvalCtxt<'_, D>) -> QueryResult<I>,
     ) -> QueryResult<I> {
         let Some(proven_via) = proven_via else {
             // We don't care about overflow. If proving the trait goal overflowed, then
@@ -818,13 +819,27 @@ where
             // FIXME(const_trait_impl): should this behavior also be used by
             // constness checking. Doing so is *at least theoretically* breaking,
             // see github.com/rust-lang/rust/issues/133044#issuecomment-2500709754
-            TraitGoalProvenVia::ParamEnv | TraitGoalProvenVia::AliasBound => candidates
-                .iter()
-                .filter(|c| {
-                    matches!(c.source, CandidateSource::AliasBound | CandidateSource::ParamEnv(_))
-                })
-                .map(|c| c.result)
-                .collect(),
+            TraitGoalProvenVia::ParamEnv | TraitGoalProvenVia::AliasBound => {
+                let mut candidates_from_env: Vec<_> = candidates
+                    .iter()
+                    .filter(|c| {
+                        matches!(
+                            c.source,
+                            CandidateSource::AliasBound | CandidateSource::ParamEnv(_)
+                        )
+                    })
+                    .map(|c| c.result)
+                    .collect();
+
+                // If the trait goal has been proven by using the environment, we want to treat
+                // aliases as rigid if there are no applicable projection bounds in the environment.
+                if candidates_from_env.is_empty() {
+                    if let Ok(response) = inject_normalize_to_rigid_candidate(self) {
+                        candidates_from_env.push(response);
+                    }
+                }
+                candidates_from_env
+            }
             TraitGoalProvenVia::Misc => candidates.iter().map(|c| c.result).collect(),
         };
 
diff --git a/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs b/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs
index eb398e8724d..0b61c368d8e 100644
--- a/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/effect_goals.rs
@@ -405,6 +405,6 @@ where
                 goal.with(ecx.cx(), goal.predicate.trait_ref);
             ecx.compute_trait_goal(trait_goal)
         })?;
-        self.merge_candidates(proven_via, candidates)
+        self.merge_candidates(proven_via, candidates, |_ecx| Err(NoSolution))
     }
 }
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 1d0ec7b45ca..e3d16719e28 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
@@ -30,75 +30,26 @@ where
     ) -> QueryResult<I> {
         self.set_is_normalizes_to_goal();
         debug_assert!(self.term_is_fully_unconstrained(goal));
-        let normalize_result = self
-            .probe(|&result| ProbeKind::TryNormalizeNonRigid { result })
-            .enter(|this| this.normalize_at_least_one_step(goal));
-
-        match normalize_result {
-            Ok(res) => Ok(res),
-            Err(NoSolution) => {
-                self.probe(|&result| ProbeKind::RigidAlias { result }).enter(|this| {
-                    let Goal { param_env, predicate: NormalizesTo { alias, term } } = goal;
-                    this.add_rigid_constraints(param_env, alias)?;
-                    this.relate_rigid_alias_non_alias(param_env, alias, ty::Invariant, term)?;
-                    this.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-                })
-            }
-        }
-    }
-
-    /// Register any obligations that are used to validate that an alias should be
-    /// treated as rigid.
-    ///
-    /// An alias may be considered rigid if it fails normalization, but we also don't
-    /// want to consider aliases that are not well-formed to be rigid simply because
-    /// they fail normalization.
-    ///
-    /// For example, some `<T as Trait>::Assoc` where `T: Trait` does not hold, or an
-    /// opaque type whose hidden type doesn't actually satisfy the opaque item bounds.
-    fn add_rigid_constraints(
-        &mut self,
-        param_env: I::ParamEnv,
-        rigid_alias: ty::AliasTerm<I>,
-    ) -> Result<(), NoSolution> {
-        let cx = self.cx();
-        match rigid_alias.kind(cx) {
-            // Projections are rigid only if their trait ref holds,
-            // and the GAT where-clauses hold.
-            ty::AliasTermKind::ProjectionTy | ty::AliasTermKind::ProjectionConst => {
-                let trait_ref = rigid_alias.trait_ref(cx);
-                self.add_goal(GoalSource::AliasWellFormed, Goal::new(cx, param_env, trait_ref));
-                Ok(())
-            }
-            ty::AliasTermKind::OpaqueTy => {
-                if self.opaque_type_is_rigid(rigid_alias.def_id) {
-                    Ok(())
-                } else {
-                    Err(NoSolution)
-                }
-            }
-            // FIXME(generic_const_exprs): we would need to support generic consts here
-            ty::AliasTermKind::UnevaluatedConst => Err(NoSolution),
-            // Inherent and weak types are never rigid. This type must not be well-formed.
-            ty::AliasTermKind::WeakTy | ty::AliasTermKind::InherentTy => Err(NoSolution),
-        }
-    }
-
-    /// Normalize the given alias by at least one step. If the alias is rigid, this
-    /// returns `NoSolution`.
-    #[instrument(level = "trace", skip(self), ret)]
-    fn normalize_at_least_one_step(&mut self, goal: Goal<I, NormalizesTo<I>>) -> QueryResult<I> {
         let cx = self.cx();
         match goal.predicate.alias.kind(cx) {
             ty::AliasTermKind::ProjectionTy | ty::AliasTermKind::ProjectionConst => {
                 let candidates = self.assemble_and_evaluate_candidates(goal);
+                let trait_ref = goal.predicate.alias.trait_ref(cx);
                 let (_, proven_via) =
                     self.probe(|_| ProbeKind::ShadowedEnvProbing).enter(|ecx| {
-                        let trait_goal: Goal<I, ty::TraitPredicate<I>> =
-                            goal.with(cx, goal.predicate.alias.trait_ref(cx));
+                        let trait_goal: Goal<I, ty::TraitPredicate<I>> = goal.with(cx, trait_ref);
                         ecx.compute_trait_goal(trait_goal)
                     })?;
-                self.merge_candidates(proven_via, candidates)
+                self.merge_candidates(proven_via, candidates, |ecx| {
+                    ecx.probe(|&result| ProbeKind::RigidAlias { result }).enter(|this| {
+                        this.structurally_instantiate_normalizes_to_term(
+                            goal,
+                            goal.predicate.alias,
+                        );
+                        this.add_goal(GoalSource::AliasWellFormed, goal.with(cx, trait_ref));
+                        this.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                    })
+                })
             }
             ty::AliasTermKind::InherentTy => self.normalize_inherent_associated_type(goal),
             ty::AliasTermKind::OpaqueTy => self.normalize_opaque_type(goal),
@@ -120,6 +71,17 @@ where
         self.eq(goal.param_env, goal.predicate.term, term)
             .expect("expected goal term to be fully unconstrained");
     }
+
+    /// Unlike `instantiate_normalizes_to_term` this instantiates the expected term
+    /// with a rigid alias. Using this is pretty much always wrong.
+    pub fn structurally_instantiate_normalizes_to_term(
+        &mut self,
+        goal: Goal<I, NormalizesTo<I>>,
+        term: ty::AliasTerm<I>,
+    ) {
+        self.relate_rigid_alias_non_alias(goal.param_env, term, ty::Invariant, goal.predicate.term)
+            .expect("expected goal term to be fully unconstrained");
+    }
 }
 
 impl<D, I> assembly::GoalKind<D> for NormalizesTo<I>
@@ -850,12 +812,14 @@ where
                 todo!("discr subgoal...")
             }
 
-            // We do not call `Ty::discriminant_ty` on alias, param, or placeholder
-            // types, which return `<self_ty as DiscriminantKind>::Discriminant`
-            // (or ICE in the case of placeholders). Projecting a type to itself
-            // is never really productive.
+            // Given an alias, parameter, or placeholder we add an impl candidate normalizing to a rigid
+            // alias. In case there's a where-bound further constraining this alias it is preferred over
+            // this impl candidate anyways. It's still a bit scuffed.
             ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => {
-                return Err(NoSolution);
+                return ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
+                    ecx.structurally_instantiate_normalizes_to_term(goal, goal.predicate.alias);
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                });
             }
 
             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
@@ -902,12 +866,14 @@ where
                 todo!()
             }
 
-            // We do not call `Ty::async_destructor_ty` on alias, param, or placeholder
-            // types, which return `<self_ty as AsyncDestruct>::AsyncDestructor`
-            // (or ICE in the case of placeholders). Projecting a type to itself
-            // is never really productive.
+            // Given an alias, parameter, or placeholder we add an impl candidate normalizing to a rigid
+            // alias. In case there's a where-bound further constraining this alias it is preferred over
+            // this impl candidate anyways. It's still a bit scuffed.
             ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => {
-                return Err(NoSolution);
+                return ecx.probe_builtin_trait_candidate(BuiltinImplSource::Misc).enter(|ecx| {
+                    ecx.structurally_instantiate_normalizes_to_term(goal, goal.predicate.alias);
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                });
             }
 
             ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_))
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 26a8a22d77e..60c20762a30 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
@@ -35,14 +35,15 @@ where
                 self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)
             }
             TypingMode::Analysis { defining_opaque_types } => {
-                let Some(def_id) = opaque_ty.def_id.as_local() else {
-                    return Err(NoSolution);
+                let Some(def_id) = opaque_ty
+                    .def_id
+                    .as_local()
+                    .filter(|&def_id| defining_opaque_types.contains(&def_id))
+                else {
+                    self.structurally_instantiate_normalizes_to_term(goal, goal.predicate.alias);
+                    return self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
                 };
 
-                if !defining_opaque_types.contains(&def_id) {
-                    return Err(NoSolution);
-                }
-
                 // FIXME: This may have issues when the args contain aliases...
                 match uses_unique_placeholders_ignoring_regions(self.cx(), opaque_ty.args) {
                     Err(NotUniqueParam::NotParam(param)) if param.is_non_region_infer() => {
@@ -97,15 +98,16 @@ where
                 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             }
             TypingMode::PostBorrowckAnalysis { defined_opaque_types } => {
-                let Some(def_id) = opaque_ty.def_id.as_local() else {
-                    return Err(NoSolution);
+                let Some(def_id) = opaque_ty
+                    .def_id
+                    .as_local()
+                    .filter(|&def_id| defined_opaque_types.contains(&def_id))
+                else {
+                    self.structurally_instantiate_normalizes_to_term(goal, goal.predicate.alias);
+                    return self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes);
                 };
 
-                if !defined_opaque_types.contains(&def_id) {
-                    return Err(NoSolution);
-                }
-
-                let actual = cx.type_of(opaque_ty.def_id).instantiate(cx, opaque_ty.args);
+                let actual = cx.type_of(def_id.into()).instantiate(cx, opaque_ty.args);
                 // FIXME: Actually use a proper binder here instead of relying on `ReErased`.
                 //
                 // This is also probably unsound or sth :shrug:
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 9f4ee54bd4c..9fbc1d64d74 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -300,7 +300,6 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
                         inspect::ProbeKind::NormalizedSelfTyAssembly
                         | inspect::ProbeKind::UnsizeAssembly
                         | inspect::ProbeKind::Root { .. }
-                        | inspect::ProbeKind::TryNormalizeNonRigid { .. }
                         | inspect::ProbeKind::TraitCandidate { .. }
                         | inspect::ProbeKind::OpaqueTypeStorageLookup { .. }
                         | inspect::ProbeKind::RigidAlias { .. } => {
@@ -325,7 +324,6 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
             // We add a candidate even for the root evaluation if there
             // is only one way to prove a given goal, e.g. for `WellFormed`.
             inspect::ProbeKind::Root { result }
-            | inspect::ProbeKind::TryNormalizeNonRigid { result }
             | inspect::ProbeKind::TraitCandidate { source: _, result }
             | inspect::ProbeKind::OpaqueTypeStorageLookup { result }
             | inspect::ProbeKind::RigidAlias { result } => {
diff --git a/compiler/rustc_trait_selection/src/solve/select.rs b/compiler/rustc_trait_selection/src/solve/select.rs
index b0b6274907d..4437fc5b029 100644
--- a/compiler/rustc_trait_selection/src/solve/select.rs
+++ b/compiler/rustc_trait_selection/src/solve/select.rs
@@ -175,8 +175,7 @@ fn to_selection<'tcx>(
                 span_bug!(span, "didn't expect to select an unknowable candidate")
             }
         },
-        ProbeKind::TryNormalizeNonRigid { result: _ }
-        | ProbeKind::NormalizedSelfTyAssembly
+        ProbeKind::NormalizedSelfTyAssembly
         | ProbeKind::UnsizeAssembly
         | ProbeKind::UpcastProjectionCompatibility
         | ProbeKind::OpaqueTypeStorageLookup { result: _ }
diff --git a/compiler/rustc_type_ir/src/solve/inspect.rs b/compiler/rustc_type_ir/src/solve/inspect.rs
index d0e618dc6f9..18fb71dd290 100644
--- a/compiler/rustc_type_ir/src/solve/inspect.rs
+++ b/compiler/rustc_type_ir/src/solve/inspect.rs
@@ -111,8 +111,6 @@ pub enum ProbeStep<I: Interner> {
 pub enum ProbeKind<I: Interner> {
     /// The root inference context while proving a goal.
     Root { result: QueryResult<I> },
-    /// Trying to normalize an alias by at least one step in `NormalizesTo`.
-    TryNormalizeNonRigid { result: QueryResult<I> },
     /// Probe entered when normalizing the self ty during candidate assembly
     NormalizedSelfTyAssembly,
     /// A candidate for proving a trait or alias-relate goal.