ambiguity on inductive cycles

[lcnr]

We now always fail with ambiguity on inductive cycles, even in the old solver rust-lang/rust#118649

---

The old solver returns EvaluatedToRecur on inductive cycles which allows candidates with such cycles to be dropped, allowing the following example to compile:

trait Trait<T> {}

impl<T> Trait<u32> for T
where
    T: Trait<u32> {}
impl Trait<i32> for () {}

fn impls_trait<T: Trait<U>, U>() {}

fn main() {
    impls_trait::<(), _>();
}

more importantly, this affects coherence, e.g. interval-map:

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 an inductive cycle rn.
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
    }
}

Returning NoSolution in the new solver would be unsound because the cycle may be with different inference variables due to canonicalization. For coinductive cycles we rerun the goal and continuously update the provisional result. Doing so for inductive cycles as well is non-trivial so I would like to ideally avoid it.

The new solver instead treats inductive cycles as overflow, meaning that the above test fails. This will end up breaking anyways once we change traits to be coinductive by default. It therefore seems desirable to prevent people from relying on that behavior as soon as possible.

[lcnr]

@compiler-errors tried to also change this outside of coherence, resulting in 21 crater regressions apparently rust-lang/rust#116494

we should minimize the affected crates and FCP merge this in the old solver, this should simplify the regression to the new solver

[lcnr]

since rust-lang/rust#118649 this is now the default behavior in coherence, even with the old solver, still affects trait solving outside of it