Rust is overflowing on recursive trait evaluation where it didn't before

[sgrif]

This can be simplified down to the following:

trait MyTrait {
    type Output;
}

impl<T: MyTrait> MyTrait for T {
    type Output = <T as MyTrait>::Output;
}

trait SomeOtherTrait {}

impl<T> SomeOtherTrait for T where T: MyTrait, T::Output: Send {}

fn main() {}

When compiling that program, rust will overflow when it did not on older versions.. Of course that example is contrived, and attempting to use any concrete type there will always overflow. It is simplified from the slightly more realistic example in https://is.gd/XSHLG2, which is simplified from the real world case where I encountered this, which was trying to pull https://github.com/diesel-rs/diesel/blob/f0a75bb/diesel/src/query_dsl/load_dsl.rs#L23-L29 into a separate trait.

The important distinction is that we're now overflowing in a generic context, in cases where there are some concrete types which are valid. Specifically this causes confusing differing behavior between where clauses on methods and where clauses on trait impls. The above code is fine if the where clause is instead on some trait method, as it's no longer evaluated until there's a concrete type that the method is being called on.

I'd actually think that rustc could always avoid overflow here, and instead detect that it's evaluating the same trait impl def for the same type and answer no. The code implies that was the intention. But that's aside the point, this is about a concrete change in behavior.

The issue was first introduced in nightly-2015-08-15. On nightlies prior to that, https://is.gd/vrEvFN would compile successfully. It manifested as an actual stack overflow until nightly-2015-10-29, where it became a proper error (hilariously giving a warning that this warning would become a hard error due to RFC 1214, when it was already hard erroring). I believe this was an unintentional side effect of implementing RFC 1214, as that was merged in on the nightly that introduced the issue.

[sgrif]

It's been over a year, and there's been no reply to this. Some of Diesel's worst error messages result from this issue. It's even become a meme that if you forget an & in the wrong place, you get a pyramid of checking &[[[[[[_]]]]]].

This case has come up again, in a recent Diesel PR. However, we're seeing overflow in cases where it's checking a concrete type, for which the recursive impl should definitively not apply. I've simplified it down to this: https://gist.github.com/sgrif/48bf08a27b3da35a44ac085cada0622c, which should fail to compile with E0277, not an overflow.

The code today has a comment which says "it is important that overflow never be masked". What's especially frustrating here is that it is masked in places that it's convenient for rustc. If the overflow occurred as a result of checking x.method_from_trait(), Rust just assumes "well clearly that trait wasn't meant to apply here". I feel pretty strongly that if it occurs on a trait bound or from UFCS, the same logic of "well clearly that impl wasn't meant to apply to this type" should apply.

[sgrif]

@nikomatsakis If you have some time this week is there any chance I could get you to take a look at this?

[nikomatsakis]

triage: P-medium

@sgrif and I are working on this a bit =)