Rollup merge of #112076 - compiler-errors:bidirectional-alias-eq, r=lcnr

Fall back to bidirectional normalizes-to if no subst-relate candidate in alias-relate goal

Sometimes we get into the case where the choice of normalizes-to branch in alias-relate are both valid, but we cannot make a choice of which one to take because they are different -- either returning equivalent but permuted region constraints, or equivalent opaque type definitions but differing modulo normalization.

In this case, we can make progress by considering a fourth candidate where we compute both normalizes-to branches together and canonicalize that as a response. This is essentially the AND intersection of both normalizes-to branches. In an ideal world, we'd be returning something more like the OR intersection of both branches, but we have no way of representing that either for regions (maybe eventually) or opaques (don't see that happening ever).

This is incomplete, so like the subst-relate fallback it's only considered outside of coherence. But it doesn't seem like a dramatic strengthening of inference or anything, and is useful for helping opaque type inference succeed when the hidden type is a projection.

## Example

Consider the goal - `AliasRelate(Tait, <[i32; 32] as IntoIterator>::IntoIter)`.

We have three ways of currently solving this goal:
1. SubstRelate - fails because we can't directly equate the substs of different alias kinds.
2. NormalizesToRhs - `Tait normalizes-to <[i32; 32] as IntoIterator>::IntoIter`
    * Ends up infering opaque definition - `Tait := <[i32; 32] as IntoIterator>::IntoIter`
3. NormalizesToLhs - `<[i32; 32] as IntoIterator>::IntoIter normalizes-to Tait`
    * Find impl candidate, substitute the associated type - `std::array::IntoIter<i32, 32>`
    * Equate `std::array::IntoIter<i32, 32>` and `Tait`
        * Ends up infering opaque definition - `Tait := std::array::IntoIter<i32, 32>`

The problem here is that 2 and 3 are essentially both valid, since we have aliases that normalize on both sides, but due to lazy norm, they end up inferring different opaque type definitions that are only equal *after* normalizing them further.

---

r? `@lcnr`

5 files changed, 269 insertions, 136 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
new file mode 100644
index 00000000000..66a4d36a1e5
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
@@ -0,0 +1,195 @@
+use super::{EvalCtxt, SolverMode};
+use rustc_infer::traits::query::NoSolution;
+use rustc_middle::traits::solve::{Certainty, Goal, QueryResult};
+use rustc_middle::ty;
+
+/// We may need to invert the alias relation direction if dealing an alias on the RHS.
+#[derive(Debug)]
+enum Invert {
+    No,
+    Yes,
+}
+
+impl<'tcx> EvalCtxt<'_, 'tcx> {
+    #[instrument(level = "debug", skip(self), ret)]
+    pub(super) fn compute_alias_relate_goal(
+        &mut self,
+        goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>, ty::AliasRelationDirection)>,
+    ) -> QueryResult<'tcx> {
+        let tcx = self.tcx();
+        let Goal { param_env, predicate: (lhs, rhs, direction) } = goal;
+        if lhs.is_infer() || rhs.is_infer() {
+            bug!(
+                "`AliasRelate` goal with an infer var on lhs or rhs which should have been instantiated"
+            );
+        }
+
+        match (lhs.to_alias_ty(tcx), rhs.to_alias_ty(tcx)) {
+            (None, None) => bug!("`AliasRelate` goal without an alias on either lhs or rhs"),
+
+            // RHS is not a projection, only way this is true is if LHS normalizes-to RHS
+            (Some(alias_lhs), None) => self.assemble_normalizes_to_candidate(
+                param_env,
+                alias_lhs,
+                rhs,
+                direction,
+                Invert::No,
+            ),
+
+            // LHS is not a projection, only way this is true is if RHS normalizes-to LHS
+            (None, Some(alias_rhs)) => self.assemble_normalizes_to_candidate(
+                param_env,
+                alias_rhs,
+                lhs,
+                direction,
+                Invert::Yes,
+            ),
+
+            (Some(alias_lhs), Some(alias_rhs)) => {
+                debug!("both sides are aliases");
+
+                let mut candidates = Vec::new();
+                // LHS normalizes-to RHS
+                candidates.extend(self.assemble_normalizes_to_candidate(
+                    param_env,
+                    alias_lhs,
+                    rhs,
+                    direction,
+                    Invert::No,
+                ));
+                // RHS normalizes-to RHS
+                candidates.extend(self.assemble_normalizes_to_candidate(
+                    param_env,
+                    alias_rhs,
+                    lhs,
+                    direction,
+                    Invert::Yes,
+                ));
+                // Relate via substs
+                let subst_relate_response = self
+                    .assemble_subst_relate_candidate(param_env, alias_lhs, alias_rhs, direction);
+                candidates.extend(subst_relate_response);
+                debug!(?candidates);
+
+                if let Some(merged) = self.try_merge_responses(&candidates) {
+                    Ok(merged)
+                } else {
+                    // When relating two aliases and we have ambiguity, we prefer
+                    // relating the generic arguments of the aliases over normalizing
+                    // them. This is necessary for inference during typeck.
+                    //
+                    // As this is incomplete, we must not do so during coherence.
+                    match self.solver_mode() {
+                        SolverMode::Normal => {
+                            if let Ok(subst_relate_response) = subst_relate_response {
+                                Ok(subst_relate_response)
+                            } else if let Ok(bidirectional_normalizes_to_response) = self
+                                .assemble_bidirectional_normalizes_to_candidate(
+                                    param_env, lhs, rhs, direction,
+                                )
+                            {
+                                Ok(bidirectional_normalizes_to_response)
+                            } else {
+                                self.flounder(&candidates)
+                            }
+                        }
+                        SolverMode::Coherence => self.flounder(&candidates),
+                    }
+                }
+            }
+        }
+    }
+
+    #[instrument(level = "debug", skip(self), ret)]
+    fn assemble_normalizes_to_candidate(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        alias: ty::AliasTy<'tcx>,
+        other: ty::Term<'tcx>,
+        direction: ty::AliasRelationDirection,
+        invert: Invert,
+    ) -> QueryResult<'tcx> {
+        self.probe(|ecx| {
+            ecx.normalizes_to_inner(param_env, alias, other, direction, invert)?;
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        })
+    }
+
+    fn normalizes_to_inner(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        alias: ty::AliasTy<'tcx>,
+        other: ty::Term<'tcx>,
+        direction: ty::AliasRelationDirection,
+        invert: Invert,
+    ) -> Result<(), NoSolution> {
+        let other = match direction {
+            // This is purely an optimization.
+            ty::AliasRelationDirection::Equate => other,
+
+            ty::AliasRelationDirection::Subtype => {
+                let fresh = self.next_term_infer_of_kind(other);
+                let (sub, sup) = match invert {
+                    Invert::No => (fresh, other),
+                    Invert::Yes => (other, fresh),
+                };
+                self.sub(param_env, sub, sup)?;
+                fresh
+            }
+        };
+        self.add_goal(Goal::new(
+            self.tcx(),
+            param_env,
+            ty::Binder::dummy(ty::ProjectionPredicate { projection_ty: alias, term: other }),
+        ));
+
+        Ok(())
+    }
+
+    fn assemble_subst_relate_candidate(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        alias_lhs: ty::AliasTy<'tcx>,
+        alias_rhs: ty::AliasTy<'tcx>,
+        direction: ty::AliasRelationDirection,
+    ) -> QueryResult<'tcx> {
+        self.probe(|ecx| {
+            match direction {
+                ty::AliasRelationDirection::Equate => {
+                    ecx.eq(param_env, alias_lhs, alias_rhs)?;
+                }
+                ty::AliasRelationDirection::Subtype => {
+                    ecx.sub(param_env, alias_lhs, alias_rhs)?;
+                }
+            }
+
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        })
+    }
+
+    fn assemble_bidirectional_normalizes_to_candidate(
+        &mut self,
+        param_env: ty::ParamEnv<'tcx>,
+        lhs: ty::Term<'tcx>,
+        rhs: ty::Term<'tcx>,
+        direction: ty::AliasRelationDirection,
+    ) -> QueryResult<'tcx> {
+        self.probe(|ecx| {
+            ecx.normalizes_to_inner(
+                param_env,
+                lhs.to_alias_ty(ecx.tcx()).unwrap(),
+                rhs,
+                direction,
+                Invert::No,
+            )?;
+            ecx.normalizes_to_inner(
+                param_env,
+                rhs.to_alias_ty(ecx.tcx()).unwrap(),
+                lhs,
+                direction,
+                Invert::Yes,
+            )?;
+            ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+        })
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 56a254d9c07..f4c29c837b8 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -20,6 +20,7 @@ use rustc_middle::ty::{
     CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate,
 };
 
+mod alias_relate;
 mod assembly;
 mod canonicalize;
 mod eval_ctxt;
@@ -155,142 +156,6 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
     }
 
     #[instrument(level = "debug", skip(self), ret)]
-    fn compute_alias_relate_goal(
-        &mut self,
-        goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>, ty::AliasRelationDirection)>,
-    ) -> QueryResult<'tcx> {
-        let tcx = self.tcx();
-        // We may need to invert the alias relation direction if dealing an alias on the RHS.
-        #[derive(Debug)]
-        enum Invert {
-            No,
-            Yes,
-        }
-        let evaluate_normalizes_to =
-            |ecx: &mut EvalCtxt<'_, 'tcx>, alias, other, direction, invert| {
-                let span = tracing::span!(
-                    tracing::Level::DEBUG,
-                    "compute_alias_relate_goal(evaluate_normalizes_to)",
-                    ?alias,
-                    ?other,
-                    ?direction,
-                    ?invert
-                );
-                let _enter = span.enter();
-                let result = ecx.probe(|ecx| {
-                    let other = match direction {
-                        // This is purely an optimization.
-                        ty::AliasRelationDirection::Equate => other,
-
-                        ty::AliasRelationDirection::Subtype => {
-                            let fresh = ecx.next_term_infer_of_kind(other);
-                            let (sub, sup) = match invert {
-                                Invert::No => (fresh, other),
-                                Invert::Yes => (other, fresh),
-                            };
-                            ecx.sub(goal.param_env, sub, sup)?;
-                            fresh
-                        }
-                    };
-                    ecx.add_goal(goal.with(
-                        tcx,
-                        ty::Binder::dummy(ty::ProjectionPredicate {
-                            projection_ty: alias,
-                            term: other,
-                        }),
-                    ));
-                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-                });
-                debug!(?result);
-                result
-            };
-
-        let (lhs, rhs, direction) = goal.predicate;
-
-        if lhs.is_infer() || rhs.is_infer() {
-            bug!(
-                "`AliasRelate` goal with an infer var on lhs or rhs which should have been instantiated"
-            );
-        }
-
-        match (lhs.to_alias_ty(tcx), rhs.to_alias_ty(tcx)) {
-            (None, None) => bug!("`AliasRelate` goal without an alias on either lhs or rhs"),
-
-            // RHS is not a projection, only way this is true is if LHS normalizes-to RHS
-            (Some(alias_lhs), None) => {
-                evaluate_normalizes_to(self, alias_lhs, rhs, direction, Invert::No)
-            }
-
-            // LHS is not a projection, only way this is true is if RHS normalizes-to LHS
-            (None, Some(alias_rhs)) => {
-                evaluate_normalizes_to(self, alias_rhs, lhs, direction, Invert::Yes)
-            }
-
-            (Some(alias_lhs), Some(alias_rhs)) => {
-                debug!("both sides are aliases");
-
-                let mut candidates = Vec::new();
-                // LHS normalizes-to RHS
-                candidates.extend(evaluate_normalizes_to(
-                    self,
-                    alias_lhs,
-                    rhs,
-                    direction,
-                    Invert::No,
-                ));
-                // RHS normalizes-to RHS
-                candidates.extend(evaluate_normalizes_to(
-                    self,
-                    alias_rhs,
-                    lhs,
-                    direction,
-                    Invert::Yes,
-                ));
-                // Relate via substs
-                let subst_relate_response = self.probe(|ecx| {
-                    let span = tracing::span!(
-                        tracing::Level::DEBUG,
-                        "compute_alias_relate_goal(relate_via_substs)",
-                        ?alias_lhs,
-                        ?alias_rhs,
-                        ?direction
-                    );
-                    let _enter = span.enter();
-
-                    match direction {
-                        ty::AliasRelationDirection::Equate => {
-                            ecx.eq(goal.param_env, alias_lhs, alias_rhs)?;
-                        }
-                        ty::AliasRelationDirection::Subtype => {
-                            ecx.sub(goal.param_env, alias_lhs, alias_rhs)?;
-                        }
-                    }
-
-                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-                });
-                candidates.extend(subst_relate_response);
-                debug!(?candidates);
-
-                if let Some(merged) = self.try_merge_responses(&candidates) {
-                    Ok(merged)
-                } else {
-                    // When relating two aliases and we have ambiguity, we prefer
-                    // relating the generic arguments of the aliases over normalizing
-                    // them. This is necessary for inference during typeck.
-                    //
-                    // As this is incomplete, we must not do so during coherence.
-                    match (self.solver_mode(), subst_relate_response) {
-                        (SolverMode::Normal, Ok(response)) => Ok(response),
-                        (SolverMode::Normal, Err(NoSolution)) | (SolverMode::Coherence, _) => {
-                            self.flounder(&candidates)
-                        }
-                    }
-                }
-            }
-        }
-    }
-
-    #[instrument(level = "debug", skip(self), ret)]
     fn compute_const_arg_has_type_goal(
         &mut self,
         goal: Goal<'tcx, (ty::Const<'tcx>, Ty<'tcx>)>,
diff --git a/tests/ui/traits/new-solver/tait-eq-proj-2.rs b/tests/ui/traits/new-solver/tait-eq-proj-2.rs
new file mode 100644
index 00000000000..99a3d02bd1a
--- /dev/null
+++ b/tests/ui/traits/new-solver/tait-eq-proj-2.rs
@@ -0,0 +1,21 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+
+#![feature(type_alias_impl_trait)]
+
+// Similar to tests/ui/traits/new-solver/tait-eq-proj.rs
+// but check the alias-sub relation in the other direction.
+
+type Tait = impl Iterator<Item = impl Sized>;
+
+fn mk<T>() -> T { todo!() }
+
+fn a() {
+    let x: Tait = mk();
+    let mut array = mk();
+    let mut z = IntoIterator::into_iter(array);
+    z = x;
+    array = [0i32; 32];
+}
+
+fn main() {}
diff --git a/tests/ui/traits/new-solver/tait-eq-proj.rs b/tests/ui/traits/new-solver/tait-eq-proj.rs
new file mode 100644
index 00000000000..01141b2819a
--- /dev/null
+++ b/tests/ui/traits/new-solver/tait-eq-proj.rs
@@ -0,0 +1,35 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+
+#![feature(type_alias_impl_trait)]
+
+type Tait = impl Iterator<Item = impl Sized>;
+
+/*
+
+Consider the goal - AliasRelate(Tait, <[i32; 32] as IntoIterator>::IntoIter)
+which is registered on the line above.
+
+A. SubstRelate - fails (of course).
+
+B. NormalizesToRhs - Tait normalizes-to <[i32; 32] as IntoIterator>::IntoIter
+    * infer definition - Tait := <[i32; 32] as IntoIterator>::IntoIter
+
+C. NormalizesToLhs - <[i32; 32] as IntoIterator>::IntoIter normalizes-to Tait
+    * Find impl candidate, after substitute - std::array::IntoIter<i32, 32>
+    * Equate std::array::IntoIter<i32, 32> and Tait
+        * infer definition - Tait := std::array::IntoIter<i32, 32>
+
+B and C are not equal, but they are equivalent modulo normalization.
+
+We get around this by evaluating both the NormalizesToRhs and NormalizesToLhs
+goals together. Essentially:
+    A alias-relate B if A normalizes-to B and B normalizes-to A.
+
+*/
+
+fn a() {
+    let _: Tait = IntoIterator::into_iter([0i32; 32]);
+}
+
+fn main() {}
diff --git a/tests/ui/traits/new-solver/tait-eq-tait.rs b/tests/ui/traits/new-solver/tait-eq-tait.rs
new file mode 100644
index 00000000000..532c4c39bd4
--- /dev/null
+++ b/tests/ui/traits/new-solver/tait-eq-tait.rs
@@ -0,0 +1,17 @@
+// compile-flags: -Ztrait-solver=next
+// check-pass
+
+// Not exactly sure if this is the inference behavior we *want*,
+// but it is a side-effect of the lazy normalization of TAITs.
+
+#![feature(type_alias_impl_trait)]
+
+type Tait = impl Sized;
+type Tait2 = impl Sized;
+
+fn mk<T>() -> T { todo!() }
+
+fn main() {
+    let x: Tait = 1u32;
+    let y: Tait2 = x;
+}