fn match_fresh_trait_refs removal

[lcnr]

The old solver eagerly detects unbounded recursion and forces the affected goals to be ambiguous. This check forces some goals which would not recurse to ambiguity as well. These goals now correctly result in NoSolution.

https://github.com/rust-lang/rust/blob/b14fd2359f47fb9a14bbfe55359db4bb3af11861/compiler/rustc_trait_selection/src/traits/select/mod.rs#L1172-L1211.

This test fails with ambiguity with old solver due to multiple candidates, and successfully compiles with new:

trait Trait<T, DUMMY> {}
struct W<T>(T);
// To pass coherence.
trait IsNotI32 {}

// This impl does not hold but gets forced as ambiguous due to
// `fn match_fresh_trait_refs`.
impl<T, DUMMY> Trait<T, DUMMY> for W<T>
where
    DUMMY: IsNotI32,
    W<u32>: Trait<i32, DUMMY> {}

// This impl holds.
impl Trait<u32, i32> for W<u32> {}
    

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

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

Removing this check does worsen performance by not as eagerly detecting overflow. However, correctly tracking the stack dependent behavior for this check would probably have a far greater performance impact.

---

This check prevents typenum from reaching the recursion limit in the old solver, cc #56

[aliemjay]

a simplified example I made for rust-lang/rust#114249

trait Trait<X> {}

// This impl does not hold.
impl<X> Trait<X> for Box<u32> where Box<u16>: Trait<X> {}

// This impl holds.
impl Trait<()> for Box<u8> {}

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

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

[lcnr]

This means coherence allows slightly more code: https://rust.godbolt.org/z/ne69PeWzE

trait Trait<T, DUMMY> {}
struct W<T>(T);
// To pass coherence.
trait IsNotI32 {}

// This impl does not hold but gets forced as ambiguous due to
// `fn match_fresh_trait_refs`.
impl<T, DUMMY> Trait<W<T>, W<DUMMY>> for W<T>
where
    DUMMY: IsNotI32,
    W<u32>: Trait<W<i32>, W<DUMMY>> {}

// This impl holds.
impl Trait<W<u32>, W<i32>> for W<u32> {}

trait IsNotU32 {}
impl IsNotU32 for i32 {}
impl IsNotU32 for u16 {}

trait Common<U, V> {}
impl<T, U, DUMMY> Common<W<U>, W<DUMMY>> for T
where
    T: Trait<W<U>, W<DUMMY>>,
    U: IsNotU32,
{}

// Overlaps with old solver, compiles with new
trait DoesNotOverlap<U, DUMMY> {}
impl<T, U, DUMMY> DoesNotOverlap<U, DUMMY> for T
where
    T: Common<W<U>, W<DUMMY>>,
{}

impl<T, U, DUMMY> DoesNotOverlap<U, DUMMY> for W<T> {}

fn main() {}

should have started with @aliemjay's example to have something which is at least somewhat readable