Overflow in checking recursive trait requirements with specialization #80700
Description
The issue
I'm making a small type-level program that computes the last element of a type-level list. Compiler is rustc 1.51.0-nightly (80184183b 2021-01-03). This program works correctly:
struct Nil;
struct Cons<Head, Tail>(std::marker::PhantomData<(Head, Tail)>);
trait GetLast {
type Output;
}
impl<Head> GetLast for Cons<Head, Nil> {
type Output = Nil;
}
impl<Head, Head2, Tail2> GetLast for Cons<Head, Cons<Head2, Tail2>>
where Cons<Head2, Tail2>: GetLast {
type Output = <Cons<Head2, Tail2> as GetLast>::Output;
}My goal is to turn GetLast into a higher-order type function, via the family pattern and GATs.
#![feature(generic_associated_types)]
trait Family {
type Func<T>;
}
struct GetLastFamily;
impl Family for GetLastFamily {
type Func<T> = <T as GetLast>::Output;
}However, this code doesn't compile unless GetLast is implemented for all types T. So I'm trying to use specialization to achieve this:
#![feature(specialization)]
struct Error;
impl<T> GetLast for T {
default type Output = Error;
}Then the compiler returns the error:
error[E0275]: overflow evaluating the requirement `Cons<_, _>: GetLast`
|
= help: consider adding a `#![recursion_limit="256"]` attribute to your crate (`test`)
= note: required because of the requirements on the impl of `GetLast` for `Cons<_, Cons<_, _>>`
= note: 127 redundant requirements hidden
= note: required because of the requirements on the impl of `GetLast` for `Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, Cons<_, _>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
I tried increasing the recursion limit, but rustc just eventually segfaults.
An undesirable fix
I determined that if I change the logic of the GetLast impls, then I can get the code to compile. Specifically, rather than enforcing Cons<Head, Nil> and Cons<Head, Cons<Head2, Tail2>> to be distinct types, I can make the latter also a default type.
impl<Head> GetLast for Cons<Head, Nil> {
type Output = Nil;
}
impl<Head, Tail> GetLast for Cons<Head, Tail>
where Tail: GetLast {
default type Output = <Tail as GetLast>::Output;
}However, I'd like to avoid this solution because my goal is to produce an automated translation from a high-level language, and this default trickery isn't straightforward.
I recognize this issue is using two unstable features (GATs and specialization), so it's not surprising that this didn't work. But I wanted to raise the issue in case it helps solve an issue in specialization phase.