track overflowing goals for overfow errors

5 files changed, 111 insertions, 45 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 6778cb7b7a9..68111c4cc1f 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -22,7 +22,7 @@ use rustc_errors::{Diag, EmissionGuarantee};
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::{DefId, LOCAL_CRATE};
 use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, TyCtxtInferExt};
-use rustc_infer::traits::{util, TraitEngine, TraitEngineExt};
+use rustc_infer::traits::{util, FulfillmentErrorCode, TraitEngine, TraitEngineExt};
 use rustc_middle::traits::query::NoSolution;
 use rustc_middle::traits::solve::{CandidateSource, Certainty, Goal};
 use rustc_middle::traits::specialization_graph::OverlapMode;
@@ -35,6 +35,8 @@ use rustc_span::DUMMY_SP;
 use std::fmt::Debug;
 use std::ops::ControlFlow;
 
+use super::error_reporting::suggest_new_overflow_limit;
+
 /// Whether we do the orphan check relative to this crate or
 /// to some remote crate.
 #[derive(Copy, Clone, Debug)]
@@ -56,6 +58,9 @@ pub struct OverlapResult<'tcx> {
     /// `true` if the overlap might've been permitted before the shift
     /// to universes.
     pub involves_placeholder: bool,
+
+    /// Used in the new solver to suggest increasing the recursion limit.
+    pub overflowing_predicates: Vec<ty::Predicate<'tcx>>,
 }
 
 pub fn add_placeholder_note<G: EmissionGuarantee>(err: &mut Diag<'_, G>) {
@@ -65,6 +70,18 @@ pub fn add_placeholder_note<G: EmissionGuarantee>(err: &mut Diag<'_, G>) {
     );
 }
 
+pub fn suggest_increasing_recursion_limit<'tcx, G: EmissionGuarantee>(
+    tcx: TyCtxt<'tcx>,
+    err: &mut Diag<'_, G>,
+    overflowing_predicates: &[ty::Predicate<'tcx>],
+) {
+    for pred in overflowing_predicates {
+        err.note(format!("overflow evaluating the requirement `{}`", pred));
+    }
+
+    suggest_new_overflow_limit(tcx, err);
+}
+
 #[derive(Debug, Clone, Copy)]
 enum TrackAmbiguityCauses {
     Yes,
@@ -221,11 +238,13 @@ fn overlap<'tcx>(
         ),
     );
 
+    let mut overflowing_predicates = Vec::new();
     if overlap_mode.use_implicit_negative() {
-        if let Some(_failing_obligation) =
-            impl_intersection_has_impossible_obligation(selcx, &obligations)
-        {
-            return None;
+        match impl_intersection_has_impossible_obligation(selcx, &obligations) {
+            IntersectionHasImpossibleObligations::Yes => return None,
+            IntersectionHasImpossibleObligations::No { overflowing_predicates: p } => {
+                overflowing_predicates = p
+            }
         }
     }
 
@@ -261,7 +280,12 @@ fn overlap<'tcx>(
         impl_header = deeply_normalize_for_diagnostics(&infcx, param_env, impl_header);
     }
 
-    Some(OverlapResult { impl_header, intercrate_ambiguity_causes, involves_placeholder })
+    Some(OverlapResult {
+        impl_header,
+        intercrate_ambiguity_causes,
+        involves_placeholder,
+        overflowing_predicates,
+    })
 }
 
 #[instrument(level = "debug", skip(infcx), ret)]
@@ -287,6 +311,19 @@ fn equate_impl_headers<'tcx>(
     result.map(|infer_ok| infer_ok.obligations).ok()
 }
 
+/// The result of [fn impl_intersection_has_impossible_obligation].
+enum IntersectionHasImpossibleObligations<'tcx> {
+    Yes,
+    No {
+        /// With `-Znext-solver=coherence`, some obligations may
+        /// fail if only the user increased the recursion limit.
+        ///
+        /// We return those obligations here and mention them in the
+        /// error message.
+        overflowing_predicates: Vec<ty::Predicate<'tcx>>,
+    },
+}
+
 /// Check if both impls can be satisfied by a common type by considering whether
 /// any of either impl's obligations is not known to hold.
 ///
@@ -308,7 +345,7 @@ fn equate_impl_headers<'tcx>(
 fn impl_intersection_has_impossible_obligation<'a, 'cx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'tcx>,
     obligations: &'a [PredicateObligation<'tcx>],
-) -> Option<PredicateObligation<'tcx>> {
+) -> IntersectionHasImpossibleObligations<'tcx> {
     let infcx = selcx.infcx;
 
     if infcx.next_trait_solver() {
@@ -317,28 +354,42 @@ fn impl_intersection_has_impossible_obligation<'a, 'cx, 'tcx>(
 
         // We only care about the obligations that are *definitely* true errors.
         // Ambiguities do not prove the disjointness of two impls.
-        let mut errors = fulfill_cx.select_where_possible(infcx);
-        errors.pop().map(|err| err.obligation)
+        let errors = fulfill_cx.select_where_possible(infcx);
+        if errors.is_empty() {
+            let overflow_errors = fulfill_cx.collect_remaining_errors(infcx);
+            let overflowing_predicates = overflow_errors
+                .into_iter()
+                .filter(|e| match e.code {
+                    FulfillmentErrorCode::Ambiguity { overflow: Some(true) } => true,
+                    _ => false,
+                })
+                .map(|e| infcx.resolve_vars_if_possible(e.obligation.predicate))
+                .collect();
+            IntersectionHasImpossibleObligations::No { overflowing_predicates }
+        } else {
+            IntersectionHasImpossibleObligations::Yes
+        }
     } else {
-        obligations
-            .iter()
-            .find(|obligation| {
-                // We use `evaluate_root_obligation` to correctly track intercrate
-                // ambiguity clauses. We cannot use this in the new solver.
-                let evaluation_result = selcx.evaluate_root_obligation(obligation);
-
-                match evaluation_result {
-                    Ok(result) => !result.may_apply(),
-                    // If overflow occurs, we need to conservatively treat the goal as possibly holding,
-                    // since there can be instantiations of this goal that don't overflow and result in
-                    // success. This isn't much of a problem in the old solver, since we treat overflow
-                    // fatally (this still can be encountered: <https://github.com/rust-lang/rust/issues/105231>),
-                    // but in the new solver, this is very important for correctness, since overflow
-                    // *must* be treated as ambiguity for completeness.
-                    Err(_overflow) => false,
+        for obligation in obligations {
+            // We use `evaluate_root_obligation` to correctly track intercrate
+            // ambiguity clauses.
+            let evaluation_result = selcx.evaluate_root_obligation(obligation);
+
+            match evaluation_result {
+                Ok(result) => {
+                    if !result.may_apply() {
+                        return IntersectionHasImpossibleObligations::Yes;
+                    }
                 }
-            })
-            .cloned()
+                // If overflow occurs, we need to conservatively treat the goal as possibly holding,
+                // since there can be instantiations of this goal that don't overflow and result in
+                // success. While this isn't much of a problem in the old solver, since we treat overflow
+                // fatally, this still can be encountered: <https://github.com/rust-lang/rust/issues/105231>.
+                Err(_overflow) => {}
+            }
+        }
+
+        IntersectionHasImpossibleObligations::No { overflowing_predicates: Vec::new() }
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
index cbf52ea9e5a..0023fd60287 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
@@ -20,10 +20,9 @@ use crate::traits::{
     SelectionError, SignatureMismatch, TraitNotObjectSafe,
 };
 use rustc_data_structures::fx::{FxHashMap, FxIndexMap};
-use rustc_errors::{
-    codes::*, pluralize, struct_span_code_err, Applicability, Diag, ErrorGuaranteed, FatalError,
-    MultiSpan, StashKey, StringPart,
-};
+use rustc_errors::codes::*;
+use rustc_errors::{pluralize, struct_span_code_err, Applicability, MultiSpan, StringPart};
+use rustc_errors::{Diag, EmissionGuarantee, ErrorGuaranteed, FatalError, StashKey};
 use rustc_hir as hir;
 use rustc_hir::def::{DefKind, Namespace, Res};
 use rustc_hir::def_id::{DefId, LocalDefId};
@@ -62,6 +61,22 @@ pub enum OverflowCause<'tcx> {
     TraitSolver(ty::Predicate<'tcx>),
 }
 
+pub fn suggest_new_overflow_limit<'tcx, G: EmissionGuarantee>(
+    tcx: TyCtxt<'tcx>,
+    err: &mut Diag<'_, G>,
+) {
+    let suggested_limit = match tcx.recursion_limit() {
+        Limit(0) => Limit(2),
+        limit => limit * 2,
+    };
+    err.help(format!(
+        "consider increasing the recursion limit by adding a \
+         `#![recursion_limit = \"{}\"]` attribute to your crate (`{}`)",
+        suggested_limit,
+        tcx.crate_name(LOCAL_CRATE),
+    ));
+}
+
 #[extension(pub trait TypeErrCtxtExt<'tcx>)]
 impl<'tcx> TypeErrCtxt<'_, 'tcx> {
     fn report_fulfillment_errors(
@@ -263,7 +278,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         };
 
         if suggest_increasing_limit {
-            self.suggest_new_overflow_limit(&mut err);
+            suggest_new_overflow_limit(self.tcx, &mut err);
         }
 
         err
@@ -303,19 +318,6 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         );
     }
 
-    fn suggest_new_overflow_limit(&self, err: &mut Diag<'_>) {
-        let suggested_limit = match self.tcx.recursion_limit() {
-            Limit(0) => Limit(2),
-            limit => limit * 2,
-        };
-        err.help(format!(
-            "consider increasing the recursion limit by adding a \
-             `#![recursion_limit = \"{}\"]` attribute to your crate (`{}`)",
-            suggested_limit,
-            self.tcx.crate_name(LOCAL_CRATE),
-        ));
-    }
-
     /// Reports that a cycle was detected which led to overflow and halts
     /// compilation. This is equivalent to `report_overflow_obligation` except
     /// that we can give a more helpful error message (and, in particular,
diff --git a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs
index b329739609c..f5bc6c3ad2c 100644
--- a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs
@@ -39,6 +39,7 @@ pub struct OverlapError<'tcx> {
     pub self_ty: Option<Ty<'tcx>>,
     pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause<'tcx>>,
     pub involves_placeholder: bool,
+    pub overflowing_predicates: Vec<ty::Predicate<'tcx>>,
 }
 
 /// Given the generic parameters for the requested impl, translate it to the generic parameters
@@ -435,6 +436,14 @@ fn report_conflicting_impls<'tcx>(
         if overlap.involves_placeholder {
             coherence::add_placeholder_note(err);
         }
+
+        if !overlap.overflowing_predicates.is_empty() {
+            coherence::suggest_increasing_recursion_limit(
+                tcx,
+                err,
+                &overlap.overflowing_predicates,
+            );
+        }
     }
 
     let msg = DelayDm(|| {
diff --git a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
index f3b77d68922..95db9e2092f 100644
--- a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
+++ b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
@@ -103,6 +103,7 @@ impl<'tcx> Children {
                     self_ty: self_ty.has_concrete_skeleton().then_some(self_ty),
                     intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
                     involves_placeholder: overlap.involves_placeholder,
+                    overflowing_predicates: overlap.overflowing_predicates,
                 }
             };
 
diff --git a/tests/ui/traits/next-solver/coherence-fulfill-overflow.stderr b/tests/ui/traits/next-solver/coherence-fulfill-overflow.stderr
index 406c0ccca97..57cba790b55 100644
--- a/tests/ui/traits/next-solver/coherence-fulfill-overflow.stderr
+++ b/tests/ui/traits/next-solver/coherence-fulfill-overflow.stderr
@@ -5,6 +5,9 @@ LL | impl<T: ?Sized + TwoW> Trait for W<T> {}
    | ------------------------------------- first implementation here
 LL | impl<T: ?Sized + TwoW> Trait for T {}
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<_>>>>>>>>>>>>>>>>>>>>>`
+   |
+   = note: overflow evaluating the requirement `W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<W<_>>>>>>>>>>>>>>>>>>>>>: TwoW`
+   = help: consider increasing the recursion limit by adding a `#![recursion_limit = "20"]` attribute to your crate (`coherence_fulfill_overflow`)
 
 error: aborting due to 1 previous error