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`

1 files changed, 24 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 => {}
         }