ambiguity on inductive cycles

[lcnr]

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

---

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]

as this now matches the behavior of the old solver, closing in favor of #114