Repository: rust-lang/rust
Pull request: Revert "`-Znext-solver` Remove the forced ambiguity hack from search graph"

This PR reverts https://github.com/rust-lang/rust/pull/149904 as discussed and requested in https://rust-lang.zulipchat.com/#narrow/channel/326866-t-types.2Fnominated/topic/.23153910.3A.20Significant.20compilation.20time.20regression.20starting.20i.E2.80.A6.

We would like a bit of time to investigate without pressure how https://github.com/rust-lang/rust/pull/149904 caused the compile time regression in https://github.com/rust-lang/rust/issues/153910, and the PR is in beta and release is approaching. When that is better understood, and we e.g. have a fix or decide to eat it, we'd want to re-land the original work.

cc @ShoyuVanilla @lcnr 

Changed files:
filename: compiler/rustc_type_ir/src/search_graph/mod.rs
patch: @@ -926,9 +926,10 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> {
 /// heads from the stack. This may not necessarily mean that we've actually
 /// reached a fixpoint for that cycle head, which impacts the way we rebase
 /// provisional cache entries.
-#[derive(Debug)]
-enum RebaseReason {
+#[derive_where(Debug; X: Cx)]
+enum RebaseReason<X: Cx> {
     NoCycleUsages,
+    Ambiguity(X::AmbiguityInfo),
     Overflow,
     /// We've actually reached a fixpoint.
     ///
@@ -965,7 +966,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D, X> {
         &mut self,
         cx: X,
         stack_entry: &StackEntry<X>,
-        rebase_reason: RebaseReason,
+        rebase_reason: RebaseReason<X>,
     ) {
         let popped_head_index = self.stack.next_index();
         // Rebasing decisions depend only on each provisional entry and the current stack state,
@@ -1046,6 +1047,9 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D, X> {
                         // is not actually equal to the final provisional result. We
                         // need to discard the provisional cache entry in this case.
                         RebaseReason::NoCycleUsages => return false,
+                        RebaseReason::Ambiguity(info) => {
+                            *result = D::propagate_ambiguity(cx, input, info);
+                        }
                         RebaseReason::Overflow => *result = D::fixpoint_overflow_result(cx, input),
                         RebaseReason::ReachedFixpoint(None) => {}
                         RebaseReason::ReachedFixpoint(Some(path_kind)) => {
@@ -1362,6 +1366,27 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D, X> {
                 return EvaluationResult::finalize(stack_entry, encountered_overflow, result);
             }
 
+            // If computing this goal results in ambiguity with no constraints,
+            // we do not rerun it. It's incredibly difficult to get a different
+            // response in the next iteration in this case. These changes would
+            // likely either be caused by incompleteness or can change the maybe
+            // cause from ambiguity to overflow. Returning ambiguity always
+            // preserves soundness and completeness even if the goal is be known
+            // to succeed or fail.
+            //
+            // This prevents exponential blowup affecting multiple major crates.
+            // As we only get to this branch if we haven't yet reached a fixpoint,
+            // we also taint all provisional cache entries which depend on the
+            // current goal.
+            if let Some(info) = D::is_ambiguous_result(result) {
+                self.rebase_provisional_cache_entries(
+                    cx,
+                    &stack_entry,
+                    RebaseReason::Ambiguity(info),
+                );
+                return EvaluationResult::finalize(stack_entry, encountered_overflow, result);
+            };
+
             // If we've reached the fixpoint step limit, we bail with overflow and taint all
             // provisional cache entries which depend on the current goal.
             i += 1;

filename: tests/ui/traits/next-solver/global-where-bound-normalization.rs
patch: @@ -1,45 +0,0 @@
-//@ check-pass
-//@ compile-flags: -Znext-solver
-
-// Regression test for https://github.com/rust-lang/trait-system-refactor-initiative/issues/257.
-
-#![feature(rustc_attrs)]
-#![expect(internal_features)]
-#![rustc_no_implicit_bounds]
-
-pub trait Bound {}
-impl Bound for u8 {}
-
-pub trait Proj {
-    type Assoc;
-}
-impl<U: Bound> Proj for U {
-    type Assoc = U;
-}
-impl Proj for MyField {
-    type Assoc = u8;
-}
-
-// While wf-checking the global bounds of `fn foo`, elaborating this outlives predicate triggered a
-// cycle in the search graph along a particular probe path, which was not an actual solution.
-// That cycle then resulted in a forced false-positive ambiguity due to a performance hack in the
-// search graph and then ended up floundering the root goal evaluation.
-pub trait Field: Proj<Assoc: Bound + 'static> {}
-
-struct MyField;
-impl Field for MyField {}
-
-trait IdReqField {
-    type This;
-}
-impl<F: Field> IdReqField for F {
-    type This = F;
-}
-
-fn foo()
-where
-    <MyField as IdReqField>::This: Field,
-{
-}
-
-fn main() {}