Auto merge of #114023 - compiler-errors:coinductive-cycle-lint, r=lcnr

Warn on inductive cycle in coherence leading to impls being considered not overlapping

This PR implements a `coinductive_overlap_in_coherence` lint (#114040), which warns users against cases where two impls are considered **not** to overlap during coherence due to an inductive cycle disproving one of the predicates after unifying the two impls.

Cases where this lint fires will become an overlap error if we ever move to coinduction, so I'd like to make this a warning to avoid having more crates take advantage of this behavior in the mean time. Also, since the new trait solver treats inductive cycles as ambiguity, not an error, this is a blocker for landing the new trait solver in coherence.

10 files changed, 252 insertions, 54 deletions

diff --git a/compiler/rustc_lint_defs/src/builtin.rs b/compiler/rustc_lint_defs/src/builtin.rs
index 3747e562cec..96c31a90da8 100644
--- a/compiler/rustc_lint_defs/src/builtin.rs
+++ b/compiler/rustc_lint_defs/src/builtin.rs
@@ -3366,6 +3366,7 @@ declare_lint_pass! {
         BYTE_SLICE_IN_PACKED_STRUCT_WITH_DERIVE,
         CENUM_IMPL_DROP_CAST,
         COHERENCE_LEAK_CHECK,
+        COINDUCTIVE_OVERLAP_IN_COHERENCE,
         CONFLICTING_REPR_HINTS,
         CONST_EVALUATABLE_UNCHECKED,
         CONST_ITEM_MUTATION,
@@ -4423,6 +4424,44 @@ declare_lint! {
 }
 
 declare_lint! {
+    /// The `coinductive_overlap_in_coherence` lint detects impls which are currently
+    /// considered not overlapping, but may be considered to overlap if support for
+    /// coinduction is added to the trait solver.
+    ///
+    /// ### Example
+    ///
+    /// ```rust,compile_fail
+    /// #![deny(coinductive_overlap_in_coherence)]
+    ///
+    /// trait CyclicTrait {}
+    /// impl<T: CyclicTrait> CyclicTrait for T {}
+    ///
+    /// trait Trait {}
+    /// impl<T: CyclicTrait> Trait for T {}
+    /// // conflicting impl with the above
+    /// impl Trait for u8 {}
+    /// ```
+    ///
+    /// {{produces}}
+    ///
+    /// ### Explanation
+    ///
+    /// We have two choices for impl which satisfy `u8: Trait`: the blanket impl
+    /// for generic `T`, and the direct impl for `u8`. These two impls nominally
+    /// overlap, since we can infer `T = u8` in the former impl, but since the where
+    /// clause `u8: CyclicTrait` would end up resulting in a cycle (since it depends
+    /// on itself), the blanket impl is not considered to hold for `u8`. This will
+    /// change in a future release.
+    pub COINDUCTIVE_OVERLAP_IN_COHERENCE,
+    Warn,
+    "impls that are not considered to overlap may be considered to \
+    overlap in the future",
+    @future_incompatible = FutureIncompatibleInfo {
+        reference: "issue #114040 <https://github.com/rust-lang/rust/issues/114040>",
+    };
+}
+
+declare_lint! {
     /// The `unknown_diagnostic_attributes` lint detects unrecognized diagnostic attributes.
     ///
     /// ### Example
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index 48aa25dba6d..377dd82a00e 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -238,7 +238,7 @@ pub struct ImplHeader<'tcx> {
     pub impl_def_id: DefId,
     pub self_ty: Ty<'tcx>,
     pub trait_ref: Option<TraitRef<'tcx>>,
-    pub predicates: Vec<Predicate<'tcx>>,
+    pub predicates: Vec<(Predicate<'tcx>, Span)>,
 }
 
 #[derive(Copy, Clone, PartialEq, Eq, Debug, TypeFoldable, TypeVisitable)]
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index e56af586ed8..5746781ae35 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -7,7 +7,7 @@
 use crate::infer::outlives::env::OutlivesEnvironment;
 use crate::infer::InferOk;
 use crate::traits::outlives_bounds::InferCtxtExt as _;
-use crate::traits::select::IntercrateAmbiguityCause;
+use crate::traits::select::{IntercrateAmbiguityCause, TreatInductiveCycleAs};
 use crate::traits::util::impl_subject_and_oblig;
 use crate::traits::SkipLeakCheck;
 use crate::traits::{
@@ -24,6 +24,7 @@ use rustc_middle::traits::DefiningAnchor;
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::visit::{TypeVisitable, TypeVisitableExt};
 use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor};
+use rustc_session::lint::builtin::COINDUCTIVE_OVERLAP_IN_COHERENCE;
 use rustc_span::symbol::sym;
 use rustc_span::DUMMY_SP;
 use std::fmt::Debug;
@@ -151,14 +152,16 @@ fn with_fresh_ty_vars<'cx, 'tcx>(
             .predicates_of(impl_def_id)
             .instantiate(tcx, impl_args)
             .iter()
-            .map(|(c, _)| c.as_predicate())
+            .map(|(c, s)| (c.as_predicate(), s))
             .collect(),
     };
 
-    let InferOk { value: mut header, obligations } =
-        selcx.infcx.at(&ObligationCause::dummy(), param_env).normalize(header);
+    let InferOk { value: mut header, obligations } = selcx
+        .infcx
+        .at(&ObligationCause::dummy_with_span(tcx.def_span(impl_def_id)), param_env)
+        .normalize(header);
 
-    header.predicates.extend(obligations.into_iter().map(|o| o.predicate));
+    header.predicates.extend(obligations.into_iter().map(|o| (o.predicate, o.cause.span)));
     header
 }
 
@@ -207,16 +210,76 @@ fn overlap<'tcx>(
     let equate_obligations = equate_impl_headers(selcx.infcx, &impl1_header, &impl2_header)?;
     debug!("overlap: unification check succeeded");
 
-    if overlap_mode.use_implicit_negative()
-        && impl_intersection_has_impossible_obligation(
-            selcx,
-            param_env,
-            &impl1_header,
-            impl2_header,
-            equate_obligations,
-        )
-    {
-        return None;
+    if overlap_mode.use_implicit_negative() {
+        for mode in [TreatInductiveCycleAs::Ambig, TreatInductiveCycleAs::Recur] {
+            if let Some(failing_obligation) = selcx.with_treat_inductive_cycle_as(mode, |selcx| {
+                impl_intersection_has_impossible_obligation(
+                    selcx,
+                    param_env,
+                    &impl1_header,
+                    &impl2_header,
+                    &equate_obligations,
+                )
+            }) {
+                if matches!(mode, TreatInductiveCycleAs::Recur) {
+                    let first_local_impl = impl1_header
+                        .impl_def_id
+                        .as_local()
+                        .or(impl2_header.impl_def_id.as_local())
+                        .expect("expected one of the impls to be local");
+                    infcx.tcx.struct_span_lint_hir(
+                        COINDUCTIVE_OVERLAP_IN_COHERENCE,
+                        infcx.tcx.local_def_id_to_hir_id(first_local_impl),
+                        infcx.tcx.def_span(first_local_impl),
+                        format!(
+                            "implementations {} will conflict in the future",
+                            match impl1_header.trait_ref {
+                                Some(trait_ref) => {
+                                    let trait_ref = infcx.resolve_vars_if_possible(trait_ref);
+                                    format!(
+                                        "of `{}` for `{}`",
+                                        trait_ref.print_only_trait_path(),
+                                        trait_ref.self_ty()
+                                    )
+                                }
+                                None => format!(
+                                    "for `{}`",
+                                    infcx.resolve_vars_if_possible(impl1_header.self_ty)
+                                ),
+                            },
+                        ),
+                        |lint| {
+                            lint.note(
+                                "impls that are not considered to overlap may be considered to \
+                                overlap in the future",
+                            )
+                            .span_label(
+                                infcx.tcx.def_span(impl1_header.impl_def_id),
+                                "the first impl is here",
+                            )
+                            .span_label(
+                                infcx.tcx.def_span(impl2_header.impl_def_id),
+                                "the second impl is here",
+                            );
+                            if !failing_obligation.cause.span.is_dummy() {
+                                lint.span_label(
+                                    failing_obligation.cause.span,
+                                    format!(
+                                        "`{}` may be considered to hold in future releases, \
+                                        causing the impls to overlap",
+                                        infcx
+                                            .resolve_vars_if_possible(failing_obligation.predicate)
+                                    ),
+                                );
+                            }
+                            lint
+                        },
+                    );
+                }
+
+                return None;
+            }
+        }
     }
 
     // We toggle the `leak_check` by using `skip_leak_check` when constructing the
@@ -284,40 +347,30 @@ fn impl_intersection_has_impossible_obligation<'cx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'tcx>,
     param_env: ty::ParamEnv<'tcx>,
     impl1_header: &ty::ImplHeader<'tcx>,
-    impl2_header: ty::ImplHeader<'tcx>,
-    obligations: PredicateObligations<'tcx>,
-) -> bool {
+    impl2_header: &ty::ImplHeader<'tcx>,
+    obligations: &PredicateObligations<'tcx>,
+) -> Option<PredicateObligation<'tcx>> {
     let infcx = selcx.infcx;
 
-    let obligation_guaranteed_to_fail = move |obligation: &PredicateObligation<'tcx>| {
-        if infcx.next_trait_solver() {
-            infcx.evaluate_obligation(obligation).map_or(false, |result| !result.may_apply())
-        } else {
-            // We use `evaluate_root_obligation` to correctly track
-            // intercrate ambiguity clauses. We do not need this in the
-            // new solver.
-            selcx.evaluate_root_obligation(obligation).map_or(
-                false, // Overflow has occurred, and treat the obligation as possibly holding.
-                |result| !result.may_apply(),
-            )
-        }
-    };
-
-    let opt_failing_obligation = [&impl1_header.predicates, &impl2_header.predicates]
+    [&impl1_header.predicates, &impl2_header.predicates]
         .into_iter()
         .flatten()
-        .map(|&predicate| {
-            Obligation::new(infcx.tcx, ObligationCause::dummy(), param_env, predicate)
+        .map(|&(predicate, span)| {
+            Obligation::new(infcx.tcx, ObligationCause::dummy_with_span(span), param_env, predicate)
+        })
+        .chain(obligations.into_iter().cloned())
+        .find(|obligation: &PredicateObligation<'tcx>| {
+            if infcx.next_trait_solver() {
+                infcx.evaluate_obligation(obligation).map_or(false, |result| !result.may_apply())
+            } else {
+                // We use `evaluate_root_obligation` to correctly track intercrate
+                // ambiguity clauses. We cannot use this in the new solver.
+                selcx.evaluate_root_obligation(obligation).map_or(
+                    false, // Overflow has occurred, and treat the obligation as possibly holding.
+                    |result| !result.may_apply(),
+                )
+            }
         })
-        .chain(obligations)
-        .find(obligation_guaranteed_to_fail);
-
-    if let Some(failing_obligation) = opt_failing_obligation {
-        debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
-        true
-    } else {
-        false
-    }
 }
 
 /// Check if both impls can be satisfied by a common type by considering whether
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 2bd2b081157..19385e2d7f2 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -118,6 +118,8 @@ pub struct SelectionContext<'cx, 'tcx> {
     /// policy. In essence, canonicalized queries need their errors propagated
     /// rather than immediately reported because we do not have accurate spans.
     query_mode: TraitQueryMode,
+
+    treat_inductive_cycle: TreatInductiveCycleAs,
 }
 
 // A stack that walks back up the stack frame.
@@ -198,6 +200,27 @@ enum BuiltinImplConditions<'tcx> {
     Ambiguous,
 }
 
+#[derive(Copy, Clone)]
+pub enum TreatInductiveCycleAs {
+    /// This is the previous behavior, where `Recur` represents an inductive
+    /// cycle that is known not to hold. This is not forwards-compatible with
+    /// coinduction, and will be deprecated. This is the default behavior
+    /// of the old trait solver due to back-compat reasons.
+    Recur,
+    /// This is the behavior of the new trait solver, where inductive cycles
+    /// are treated as ambiguous and possibly holding.
+    Ambig,
+}
+
+impl From<TreatInductiveCycleAs> for EvaluationResult {
+    fn from(treat: TreatInductiveCycleAs) -> EvaluationResult {
+        match treat {
+            TreatInductiveCycleAs::Ambig => EvaluatedToUnknown,
+            TreatInductiveCycleAs::Recur => EvaluatedToRecur,
+        }
+    }
+}
+
 impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     pub fn new(infcx: &'cx InferCtxt<'tcx>) -> SelectionContext<'cx, 'tcx> {
         SelectionContext {
@@ -205,9 +228,26 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             freshener: infcx.freshener(),
             intercrate_ambiguity_causes: None,
             query_mode: TraitQueryMode::Standard,
+            treat_inductive_cycle: TreatInductiveCycleAs::Recur,
         }
     }
 
+    // Sets the `TreatInductiveCycleAs` mode temporarily in the selection context
+    pub fn with_treat_inductive_cycle_as<T>(
+        &mut self,
+        treat_inductive_cycle: TreatInductiveCycleAs,
+        f: impl FnOnce(&mut Self) -> T,
+    ) -> T {
+        // Should be executed in a context where caching is disabled,
+        // otherwise the cache is poisoned with the temporary result.
+        assert!(self.is_intercrate());
+        let treat_inductive_cycle =
+            std::mem::replace(&mut self.treat_inductive_cycle, treat_inductive_cycle);
+        let value = f(self);
+        self.treat_inductive_cycle = treat_inductive_cycle;
+        value
+    }
+
     pub fn with_query_mode(
         infcx: &'cx InferCtxt<'tcx>,
         query_mode: TraitQueryMode,
@@ -719,7 +759,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                 stack.update_reached_depth(stack_arg.1);
                                 return Ok(EvaluatedToOk);
                             } else {
-                                return Ok(EvaluatedToRecur);
+                                return Ok(self.treat_inductive_cycle.into());
                             }
                         }
                         return Ok(EvaluatedToOk);
@@ -837,7 +877,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                             }
                         }
                         ProjectAndUnifyResult::FailedNormalization => Ok(EvaluatedToAmbig),
-                        ProjectAndUnifyResult::Recursive => Ok(EvaluatedToRecur),
+                        ProjectAndUnifyResult::Recursive => Ok(self.treat_inductive_cycle.into()),
                         ProjectAndUnifyResult::MismatchedProjectionTypes(_) => Ok(EvaluatedToErr),
                     }
                 }
@@ -1151,7 +1191,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 Some(EvaluatedToOk)
             } else {
                 debug!("evaluate_stack --> recursive, inductive");
-                Some(EvaluatedToRecur)
+                Some(self.treat_inductive_cycle.into())
             }
         } else {
             None
diff --git a/tests/ui/coherence/warn-when-cycle-is-error-in-coherence.rs b/tests/ui/coherence/warn-when-cycle-is-error-in-coherence.rs
new file mode 100644
index 00000000000..01f7d6ce901
--- /dev/null
+++ b/tests/ui/coherence/warn-when-cycle-is-error-in-coherence.rs
@@ -0,0 +1,35 @@
+#![deny(coinductive_overlap_in_coherence)]
+
+use std::borrow::Borrow;
+use std::cmp::Ordering;
+use std::marker::PhantomData;
+
+#[derive(PartialEq, Default)]
+pub(crate) struct Interval<T>(PhantomData<T>);
+
+// This impl overlaps with the `derive` unless we reject the nested
+// `Interval<?1>: PartialOrd<Interval<?1>>` candidate which results
+// in a - currently inductive - cycle.
+impl<T, Q> PartialEq<Q> for Interval<T>
+//~^ ERROR implementations of `PartialEq<Interval<_>>` for `Interval<_>` will conflict in the future
+//~| WARN this was previously accepted by the compiler but is being phased out
+where
+    T: Borrow<Q>,
+    Q: ?Sized + PartialOrd,
+{
+    fn eq(&self, _: &Q) -> bool {
+        true
+    }
+}
+
+impl<T, Q> PartialOrd<Q> for Interval<T>
+where
+    T: Borrow<Q>,
+    Q: ?Sized + PartialOrd,
+{
+    fn partial_cmp(&self, _: &Q) -> Option<Ordering> {
+        None
+    }
+}
+
+fn main() {}
diff --git a/tests/ui/coherence/warn-when-cycle-is-error-in-coherence.stderr b/tests/ui/coherence/warn-when-cycle-is-error-in-coherence.stderr
new file mode 100644
index 00000000000..f315ba82130
--- /dev/null
+++ b/tests/ui/coherence/warn-when-cycle-is-error-in-coherence.stderr
@@ -0,0 +1,23 @@
+error: implementations of `PartialEq<Interval<_>>` for `Interval<_>` will conflict in the future
+  --> $DIR/warn-when-cycle-is-error-in-coherence.rs:13:1
+   |
+LL | #[derive(PartialEq, Default)]
+   |          --------- the second impl is here
+...
+LL | impl<T, Q> PartialEq<Q> for Interval<T>
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the first impl is here
+...
+LL |     Q: ?Sized + PartialOrd,
+   |                 ---------- `Interval<_>: PartialOrd` may be considered to hold in future releases, causing the impls to overlap
+   |
+   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
+   = note: for more information, see issue #114040 <https://github.com/rust-lang/rust/issues/114040>
+   = note: impls that are not considered to overlap may be considered to overlap in the future
+note: the lint level is defined here
+  --> $DIR/warn-when-cycle-is-error-in-coherence.rs:1:9
+   |
+LL | #![deny(coinductive_overlap_in_coherence)]
+   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to previous error
+
diff --git a/tests/ui/traits/issue-105231.rs b/tests/ui/traits/issue-105231.rs
index 74c7afd6b9e..bb2b13664ba 100644
--- a/tests/ui/traits/issue-105231.rs
+++ b/tests/ui/traits/issue-105231.rs
@@ -1,9 +1,9 @@
-//~ ERROR overflow evaluating the requirement `A<A<A<A<A<A<A<...>>>>>>>: Send`
 struct A<T>(B<T>);
 //~^ ERROR recursive types `A` and `B` have infinite size
 struct B<T>(A<A<T>>);
 trait Foo {}
 impl<T> Foo for T where T: Send {}
+//~^ ERROR overflow evaluating the requirement `A<A<A<A<A<A<A<...>>>>>>>: Send`
 impl Foo for B<u8> {}
 
 fn main() {}
diff --git a/tests/ui/traits/issue-105231.stderr b/tests/ui/traits/issue-105231.stderr
index fe20c47c57a..76a71067353 100644
--- a/tests/ui/traits/issue-105231.stderr
+++ b/tests/ui/traits/issue-105231.stderr
@@ -1,5 +1,5 @@
 error[E0072]: recursive types `A` and `B` have infinite size
-  --> $DIR/issue-105231.rs:2:1
+  --> $DIR/issue-105231.rs:1:1
    |
 LL | struct A<T>(B<T>);
    | ^^^^^^^^^^^ ---- recursive without indirection
@@ -15,10 +15,14 @@ LL ~ struct B<T>(Box<A<A<T>>>);
    |
 
 error[E0275]: overflow evaluating the requirement `A<A<A<A<A<A<A<...>>>>>>>: Send`
+  --> $DIR/issue-105231.rs:5:28
+   |
+LL | impl<T> Foo for T where T: Send {}
+   |                            ^^^^
    |
    = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`issue_105231`)
 note: required because it appears within the type `B<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<A<u8>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
-  --> $DIR/issue-105231.rs:4:8
+  --> $DIR/issue-105231.rs:3:8
    |
 LL | struct B<T>(A<A<T>>);
    |        ^
diff --git a/tests/ui/traits/solver-cycles/cycle-via-builtin-auto-trait-impl.rs b/tests/ui/traits/solver-cycles/cycle-via-builtin-auto-trait-impl.rs
index d37943b929a..206ab07898b 100644
--- a/tests/ui/traits/solver-cycles/cycle-via-builtin-auto-trait-impl.rs
+++ b/tests/ui/traits/solver-cycles/cycle-via-builtin-auto-trait-impl.rs
@@ -1,4 +1,3 @@
-//~ ERROR overflow
 // A regression test for #111729 checking that we correctly
 // track recursion depth for obligations returned by confirmation.
 use std::panic::RefUnwindSafe;
@@ -15,6 +14,7 @@ struct RootDatabase {
 }
 
 impl<T: RefUnwindSafe> Database for T {
+    //~^ ERROR overflow
     type Storage = SalsaStorage;
 }
 impl Database for RootDatabase {
diff --git a/tests/ui/traits/solver-cycles/cycle-via-builtin-auto-trait-impl.stderr b/tests/ui/traits/solver-cycles/cycle-via-builtin-auto-trait-impl.stderr
index 8f9ce3ef1e9..4123a8199a0 100644
--- a/tests/ui/traits/solver-cycles/cycle-via-builtin-auto-trait-impl.stderr
+++ b/tests/ui/traits/solver-cycles/cycle-via-builtin-auto-trait-impl.stderr
@@ -1,13 +1,17 @@
 error[E0275]: overflow evaluating the requirement `Runtime<RootDatabase>: RefUnwindSafe`
+  --> $DIR/cycle-via-builtin-auto-trait-impl.rs:16:9
+   |
+LL | impl<T: RefUnwindSafe> Database for T {
+   |         ^^^^^^^^^^^^^
    |
    = help: consider increasing the recursion limit by adding a `#![recursion_limit = "256"]` attribute to your crate (`cycle_via_builtin_auto_trait_impl`)
 note: required because it appears within the type `RootDatabase`
-  --> $DIR/cycle-via-builtin-auto-trait-impl.rs:13:8
+  --> $DIR/cycle-via-builtin-auto-trait-impl.rs:12:8
    |
 LL | struct RootDatabase {
    |        ^^^^^^^^^^^^
 note: required for `RootDatabase` to implement `Database`
-  --> $DIR/cycle-via-builtin-auto-trait-impl.rs:17:24
+  --> $DIR/cycle-via-builtin-auto-trait-impl.rs:16:24
    |
 LL | impl<T: RefUnwindSafe> Database for T {
    |         -------------  ^^^^^^^^     ^