Auto merge of #107507 - BoxyUwU:deferred_projection_equality, r=lcnr

Implement `deferred_projection_equality` for erica solver

Somewhat of a revival of #96912. When relating projections now emit an `AliasEq` obligation instead of attempting to determine equality of projections that may not be as normalized as possible (i.e. because of lazy norm, or just containing inference variables that prevent us from resolving an impl). Only do this when the new solver is enabled

9 files changed, 159 insertions, 0 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
index c1936b7dbe4..a55b984fd63 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -73,6 +73,11 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
                                         MismatchedProjectionTypes { err: TypeError::Mismatch },
                                     )
                                 }
+                                ty::PredicateKind::AliasEq(_, _) => {
+                                    FulfillmentErrorCode::CodeProjectionError(
+                                        MismatchedProjectionTypes { err: TypeError::Mismatch },
+                                    )
+                                }
                                 ty::PredicateKind::Subtype(pred) => {
                                     let (a, b) = infcx.instantiate_binder_with_placeholders(
                                         goal.predicate.kind().rebind((pred.a, pred.b)),
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 9f092b6018f..e56588c58bd 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -42,6 +42,8 @@ mod trait_goals;
 
 pub use fulfill::FulfillmentCtxt;
 
+use self::infcx_ext::InferCtxtExt;
+
 /// A goal is a statement, i.e. `predicate`, we want to prove
 /// given some assumptions, i.e. `param_env`.
 ///
@@ -81,6 +83,21 @@ pub struct Response<'tcx> {
     pub certainty: Certainty,
 }
 
+trait CanonicalResponseExt {
+    fn has_no_inference_or_external_constraints(&self) -> bool;
+}
+
+impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> {
+    fn has_no_inference_or_external_constraints(&self) -> bool {
+        // so that we get a compile error when regions are supported
+        // so this code can be checked for being correct
+        let _: () = self.value.external_constraints.regions;
+
+        self.value.var_values.is_identity()
+            && self.value.external_constraints.opaque_types.is_empty()
+    }
+}
+
 #[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
 pub enum Certainty {
     Yes,
@@ -302,6 +319,9 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
                 ty::PredicateKind::TypeWellFormedFromEnv(..) => {
                     bug!("TypeWellFormedFromEnv is only used for Chalk")
                 }
+                ty::PredicateKind::AliasEq(lhs, rhs) => {
+                    self.compute_alias_eq_goal(Goal { param_env, predicate: (lhs, rhs) })
+                }
             }
         } else {
             let kind = self.infcx.instantiate_binder_with_placeholders(kind);
@@ -398,6 +418,63 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
             None => self.make_canonical_response(Certainty::AMBIGUOUS),
         }
     }
+
+    #[instrument(level = "debug", skip(self), ret)]
+    fn compute_alias_eq_goal(
+        &mut self,
+        goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>)>,
+    ) -> QueryResult<'tcx> {
+        let tcx = self.tcx();
+
+        let evaluate_normalizes_to = |ecx: &mut EvalCtxt<'_, 'tcx>, alias, other| {
+            debug!("evaluate_normalizes_to(alias={:?}, other={:?})", alias, other);
+            let r = ecx.infcx.probe(|_| {
+                let (_, certainty) = ecx.evaluate_goal(goal.with(
+                    tcx,
+                    ty::Binder::dummy(ty::ProjectionPredicate {
+                        projection_ty: alias,
+                        term: other,
+                    }),
+                ))?;
+                ecx.make_canonical_response(certainty)
+            });
+            debug!("evaluate_normalizes_to(..) -> {:?}", r);
+            r
+        };
+
+        if goal.predicate.0.is_infer() || goal.predicate.1.is_infer() {
+            bug!(
+                "`AliasEq` goal with an infer var on lhs or rhs which should have been instantiated"
+            );
+        }
+
+        match (
+            goal.predicate.0.to_alias_term_no_opaque(tcx),
+            goal.predicate.1.to_alias_term_no_opaque(tcx),
+        ) {
+            (None, None) => bug!("`AliasEq` goal without an alias on either lhs or rhs"),
+            (Some(alias), None) => evaluate_normalizes_to(self, alias, goal.predicate.1),
+            (None, Some(alias)) => evaluate_normalizes_to(self, alias, goal.predicate.0),
+            (Some(alias_lhs), Some(alias_rhs)) => {
+                debug!("compute_alias_eq_goal: both sides are aliases");
+
+                let mut candidates = Vec::with_capacity(3);
+
+                // Evaluate all 3 potential candidates for the alias' being equal
+                candidates.push(evaluate_normalizes_to(self, alias_lhs, goal.predicate.1));
+                candidates.push(evaluate_normalizes_to(self, alias_rhs, goal.predicate.0));
+                candidates.push(self.infcx.probe(|_| {
+                    debug!("compute_alias_eq_goal: alias defids are equal, equating substs");
+                    let nested_goals = self.infcx.eq(goal.param_env, alias_lhs, alias_rhs)?;
+                    self.evaluate_all_and_make_canonical_response(nested_goals)
+                }));
+
+                debug!(?candidates);
+
+                self.try_merge_responses(candidates.into_iter())
+            }
+        }
+    }
 }
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
@@ -449,6 +526,43 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     ) -> QueryResult<'tcx> {
         self.evaluate_all(goals).and_then(|certainty| self.make_canonical_response(certainty))
     }
+
+    fn try_merge_responses(
+        &mut self,
+        responses: impl Iterator<Item = QueryResult<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        let candidates = responses.into_iter().flatten().collect::<Box<[_]>>();
+
+        if candidates.is_empty() {
+            return Err(NoSolution);
+        }
+
+        // FIXME(-Ztreat-solver=next): We should instead try to find a `Certainty::Yes` response with
+        // a subset of the constraints that all the other responses have.
+        let one = candidates[0];
+        if candidates[1..].iter().all(|resp| resp == &one) {
+            return Ok(one);
+        }
+
+        if let Some(response) = candidates.iter().find(|response| {
+            response.value.certainty == Certainty::Yes
+                && response.has_no_inference_or_external_constraints()
+        }) {
+            return Ok(response.clone());
+        }
+
+        let certainty = candidates.iter().fold(Certainty::AMBIGUOUS, |certainty, response| {
+            certainty.unify_and(response.value.certainty)
+        });
+        // FIXME(-Ztrait-solver=next): We should take the intersection of the constraints on all the
+        // responses and use that for the constraints of this ambiguous response.
+        let response = self.make_canonical_response(certainty);
+        if let Ok(response) = &response {
+            assert!(response.has_no_inference_or_external_constraints());
+        }
+
+        response
+    }
 }
 
 #[instrument(level = "debug", skip(infcx), ret)]
diff --git a/compiler/rustc_trait_selection/src/traits/auto_trait.rs b/compiler/rustc_trait_selection/src/traits/auto_trait.rs
index 948632ccc6c..6a840704e86 100644
--- a/compiler/rustc_trait_selection/src/traits/auto_trait.rs
+++ b/compiler/rustc_trait_selection/src/traits/auto_trait.rs
@@ -823,14 +823,17 @@ impl<'tcx> AutoTraitFinder<'tcx> {
                         _ => return false,
                     }
                 }
+
                 // There's not really much we can do with these predicates -
                 // we start out with a `ParamEnv` with no inference variables,
                 // and these don't correspond to adding any new bounds to
                 // the `ParamEnv`.
                 ty::PredicateKind::WellFormed(..)
+                | ty::PredicateKind::AliasEq(..)
                 | ty::PredicateKind::ObjectSafe(..)
                 | ty::PredicateKind::ClosureKind(..)
                 | ty::PredicateKind::Subtype(..)
+                // FIXME(generic_const_exprs): you can absolutely add this as a where clauses
                 | ty::PredicateKind::ConstEvaluatable(..)
                 | ty::PredicateKind::Coerce(..)
                 | ty::PredicateKind::TypeWellFormedFromEnv(..) => {}
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/method_chain.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/method_chain.rs
index ba9ee57d409..9474c70cb53 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/method_chain.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/method_chain.rs
@@ -1,5 +1,7 @@
 use crate::infer::InferCtxt;
 
+use rustc_infer::infer::ObligationEmittingRelation;
+use rustc_infer::traits::PredicateObligations;
 use rustc_middle::ty::error::TypeError;
 use rustc_middle::ty::relate::{self, Relate, RelateResult, TypeRelation};
 use rustc_middle::ty::{self, Ty, TyCtxt};
@@ -88,3 +90,16 @@ impl<'a, 'tcx> TypeRelation<'tcx> for CollectAllMismatches<'a, 'tcx> {
         Ok(a.rebind(self.relate(a.skip_binder(), b.skip_binder())?))
     }
 }
+
+impl<'tcx> ObligationEmittingRelation<'tcx> for CollectAllMismatches<'_, 'tcx> {
+    fn register_obligations(&mut self, _obligations: PredicateObligations<'tcx>) {
+        // FIXME(deferred_projection_equality)
+    }
+
+    fn register_predicates(
+        &mut self,
+        _obligations: impl IntoIterator<Item = impl ty::ToPredicate<'tcx>>,
+    ) {
+        // FIXME(deferred_projection_equality)
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
index cf1e05ada47..4867855c2ae 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -1278,6 +1278,11 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> {
                         span,
                         "TypeWellFormedFromEnv predicate should only exist in the environment"
                     ),
+
+                    ty::PredicateKind::AliasEq(..) => span_bug!(
+                        span,
+                        "AliasEq predicate should never be the predicate cause of a SelectionError"
+                    ),
                 }
             }
 
diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs
index 3adc1e62e0d..19d47d33f67 100644
--- a/compiler/rustc_trait_selection/src/traits/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs
@@ -328,6 +328,9 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> {
                 ty::PredicateKind::TypeWellFormedFromEnv(..) => {
                     bug!("TypeWellFormedFromEnv is only used for Chalk")
                 }
+                ty::PredicateKind::AliasEq(..) => {
+                    bug!("AliasEq is only used for new solver")
+                }
             },
             Some(pred) => match pred {
                 ty::PredicateKind::Clause(ty::Clause::Trait(data)) => {
@@ -594,6 +597,9 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> {
                 ty::PredicateKind::TypeWellFormedFromEnv(..) => {
                     bug!("TypeWellFormedFromEnv is only used for Chalk")
                 }
+                ty::PredicateKind::AliasEq(..) => {
+                    bug!("AliasEq is only used for new solver")
+                }
             },
         }
     }
diff --git a/compiler/rustc_trait_selection/src/traits/object_safety.rs b/compiler/rustc_trait_selection/src/traits/object_safety.rs
index bafa2981a87..977446894e7 100644
--- a/compiler/rustc_trait_selection/src/traits/object_safety.rs
+++ b/compiler/rustc_trait_selection/src/traits/object_safety.rs
@@ -327,6 +327,8 @@ fn predicate_references_self<'tcx>(
             // possible alternatives.
             if data.projection_ty.substs[1..].iter().any(has_self_ty) { Some(sp) } else { None }
         }
+        ty::PredicateKind::AliasEq(..) => bug!("`AliasEq` not allowed as assumption"),
+
         ty::PredicateKind::WellFormed(..)
         | ty::PredicateKind::ObjectSafe(..)
         | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(..))
@@ -334,6 +336,7 @@ fn predicate_references_self<'tcx>(
         | ty::PredicateKind::ClosureKind(..)
         | ty::PredicateKind::Subtype(..)
         | ty::PredicateKind::Coerce(..)
+        // FIXME(generic_const_exprs): this can mention `Self`
         | ty::PredicateKind::ConstEvaluatable(..)
         | ty::PredicateKind::ConstEquate(..)
         | ty::PredicateKind::Ambiguous
@@ -368,6 +371,7 @@ fn generics_require_sized_self(tcx: TyCtxt<'_>, def_id: DefId) -> bool {
             | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(..))
             | ty::PredicateKind::ConstEvaluatable(..)
             | ty::PredicateKind::ConstEquate(..)
+            | ty::PredicateKind::AliasEq(..)
             | ty::PredicateKind::Ambiguous
             | ty::PredicateKind::TypeWellFormedFromEnv(..) => false,
         }
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 984d6fde268..45c4811321a 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -991,6 +991,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 ty::PredicateKind::TypeWellFormedFromEnv(..) => {
                     bug!("TypeWellFormedFromEnv is only used for chalk")
                 }
+                ty::PredicateKind::AliasEq(..) => {
+                    bug!("AliasEq is only used for new solver")
+                }
                 ty::PredicateKind::Ambiguous => Ok(EvaluatedToAmbig),
             }
         })
diff --git a/compiler/rustc_trait_selection/src/traits/wf.rs b/compiler/rustc_trait_selection/src/traits/wf.rs
index 7c5e147a950..1136b70a0b9 100644
--- a/compiler/rustc_trait_selection/src/traits/wf.rs
+++ b/compiler/rustc_trait_selection/src/traits/wf.rs
@@ -187,6 +187,9 @@ pub fn predicate_obligations<'tcx>(
         ty::PredicateKind::TypeWellFormedFromEnv(..) => {
             bug!("TypeWellFormedFromEnv is only used for Chalk")
         }
+        ty::PredicateKind::AliasEq(..) => {
+            bug!("We should only wf check where clauses and `AliasEq` is not a `Clause`")
+        }
     }
 
     wf.normalize(infcx)
@@ -928,6 +931,7 @@ pub(crate) fn required_region_bounds<'tcx>(
                 | ty::PredicateKind::ConstEvaluatable(..)
                 | ty::PredicateKind::ConstEquate(..)
                 | ty::PredicateKind::Ambiguous
+                | ty::PredicateKind::AliasEq(..)
                 | ty::PredicateKind::TypeWellFormedFromEnv(..) => None,
                 ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate(
                     ref t,