Auto merge of #144732 - lcnr:ignore-shadowed-impls, r=compiler-errors

dont assemble shadowed impl candidates

Fixes https://github.com/rust-lang/trait-system-refactor-initiative/issues/109.

I've originally intended to fix this by supporting lazy reevaluation when rerunning cycles. This ended up being really difficult, see https://github.com/lcnr/search_graph for my notes used while working on this. It is also insufficient for the `rayon-hang-2.rs` test as we end up with goals which we need to rerun for all combinations of provisional results. While landing such an optimization in the future may still be desirable, it is very difficult and insufficient to fix these hangs. Also see the relevant [zulip thread](https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/rustc-rayon.20hang/near/527850058).

I was previously opposed to avoiding assembling shadowed impls as it may prevent future improvements in this area, cc rust-lang/rust#141226. Going to track this and the reasoning behind it in https://github.com/rust-lang/trait-system-refactor-initiative/issues/226.

r? `@BoxyUwU` `@compiler-errors`

3 files changed, 105 insertions, 3 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 b2d40146348..b75da23cdac 100644
--- a/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
+++ b/compiler/rustc_next_trait_solver/src/solve/assembly/mod.rs
@@ -21,7 +21,7 @@ use crate::delegate::SolverDelegate;
 use crate::solve::inspect::ProbeKind;
 use crate::solve::{
     BuiltinImplSource, CandidateSource, CanonicalResponse, Certainty, EvalCtxt, Goal, GoalSource,
-    MaybeCause, NoSolution, ParamEnvSource, QueryResult,
+    MaybeCause, NoSolution, ParamEnvSource, QueryResult, has_no_inference_or_external_constraints,
 };
 
 enum AliasBoundKind {
@@ -395,9 +395,30 @@ where
 
         match assemble_from {
             AssembleCandidatesFrom::All => {
-                self.assemble_impl_candidates(goal, &mut candidates);
                 self.assemble_builtin_impl_candidates(goal, &mut candidates);
-                self.assemble_object_bound_candidates(goal, &mut candidates);
+                // For performance we only assemble impls if there are no candidates
+                // which would shadow them. This is necessary to avoid hangs in rayon,
+                // see trait-system-refactor-initiative#109 for more details.
+                //
+                // We always assemble builtin impls as trivial builtin impls have a higher
+                // priority than where-clauses.
+                //
+                // We only do this if any such candidate applies without any constraints
+                // as we may want to weaken inference guidance in the future and don't want
+                // to worry about causing major performance regressions when doing so.
+                // See trait-system-refactor-initiative#226 for some ideas here.
+                if TypingMode::Coherence == self.typing_mode()
+                    || !candidates.iter().any(|c| {
+                        matches!(
+                            c.source,
+                            CandidateSource::ParamEnv(ParamEnvSource::NonGlobal)
+                                | CandidateSource::AliasBound
+                        ) && has_no_inference_or_external_constraints(c.result)
+                    })
+                {
+                    self.assemble_impl_candidates(goal, &mut candidates);
+                    self.assemble_object_bound_candidates(goal, &mut candidates);
+                }
             }
             AssembleCandidatesFrom::EnvAndBounds => {}
         }
diff --git a/tests/ui/traits/next-solver/cycles/rayon-hang-1.rs b/tests/ui/traits/next-solver/cycles/rayon-hang-1.rs
new file mode 100644
index 00000000000..61e1f1b200f
--- /dev/null
+++ b/tests/ui/traits/next-solver/cycles/rayon-hang-1.rs
@@ -0,0 +1,32 @@
+//@ compile-flags: -Znext-solver
+//@ check-pass
+
+// A regression test for trait-system-refactor-initiative#109.
+
+trait ParallelIterator: Sized {
+    type Item;
+}
+trait IntoParallelIterator {
+    type Iter: ParallelIterator<Item = Self::Item>;
+    type Item;
+}
+impl<T: ParallelIterator> IntoParallelIterator for T {
+    type Iter = T;
+    type Item = T::Item;
+}
+
+macro_rules! multizip_impls {
+    ($($T:ident),+) => {
+       fn foo<$( $T, )+>() where
+        $(
+            $T: IntoParallelIterator,
+            $T::Iter: ParallelIterator,
+        )+
+            ($( $T, )+): IntoParallelIterator<Item = ($( $T::Item, )+)>,
+        {}
+    }
+}
+
+multizip_impls! { A, B, C, D, E, F, G, H, I, J, K, L }
+
+fn main() {}
diff --git a/tests/ui/traits/next-solver/cycles/rayon-hang-2.rs b/tests/ui/traits/next-solver/cycles/rayon-hang-2.rs
new file mode 100644
index 00000000000..bb5d8335dd6
--- /dev/null
+++ b/tests/ui/traits/next-solver/cycles/rayon-hang-2.rs
@@ -0,0 +1,49 @@
+//@ compile-flags: -Znext-solver
+//@ check-pass
+
+// A regression test for trait-system-refactor-initiative#109.
+// Unlike `rayon-hang-1.rs` the cycles in this test are not
+// unproductive, which causes the `AliasRelate` goal when trying
+// to apply where-clauses to only error in the second iteration.
+//
+// This makes the exponential blowup to be significantly harder
+// to avoid.
+
+trait ParallelIterator: Sized {
+    type Item;
+}
+
+trait IntoParallelIteratorIndir {
+    type Iter: ParallelIterator<Item = Self::Item>;
+    type Item;
+}
+impl<I> IntoParallelIteratorIndir for I
+where
+    Box<I>: IntoParallelIterator,
+{
+    type Iter = <Box<I> as IntoParallelIterator>::Iter;
+    type Item = <Box<I> as IntoParallelIterator>::Item;
+}
+trait IntoParallelIterator {
+    type Iter: ParallelIterator<Item = Self::Item>;
+    type Item;
+}
+impl<T: ParallelIterator> IntoParallelIterator for T {
+    type Iter = T;
+    type Item = T::Item;
+}
+
+macro_rules! multizip_impls {
+    ($($T:ident),+) => {
+       fn foo<'a, $( $T, )+>() where
+        $(
+            $T: IntoParallelIteratorIndir,
+            $T::Iter: ParallelIterator,
+        )+
+        {}
+    }
+}
+
+multizip_impls! { A, B, C, D, E, F, G, H, I, J, K, L }
+
+fn main() {}