Inductive cycles are treated as ambiguous in new solver, failure in old solver

[compiler-errors]

Minimized from #113895 (interval-map):

use std::borrow::Borrow;
use std::cmp::Ordering;
use std::marker::PhantomData;

#[derive(PartialEq, Default)]
pub(crate) struct Interval<T>(PhantomData<T>);

impl<T, Q> PartialEq<Q> for Interval<T>
where
    T: Borrow<Q>,
    Q: ?Sized + PartialOrd,
{
    fn eq(&self, other: &Q) -> bool {
        true
    }
}

impl<T, Q> PartialOrd<Q> for Interval<T>
where
    T: Borrow<Q>,
    Q: ?Sized + PartialOrd,
{
    fn partial_cmp(&self, other: &Q) -> Option<Ordering> {
        None
    }
}

This code passes in the old solver, fails in the new solver.

That's because when checking if the PartialEq impls overlap (one from the Derive and one from the manual impl), we check if any of the predicates fail hold. This means we try checking Interval<?1>: PartialOrd<Interval<?1>>, which ends up being an inductive cycle with itself. Inductive cycles are treated as not holding in the old solver, since they are evaluated to EvaluatedToRecur. Meanwhile, inductive cycles in the new trait solver are treated as ambiguous.

[lcnr]

forgot this this issue can also be used in coherence :/ anyways, already have #20, so moved the example to that issue