Overflow in checking recursive trait requirements with specialization

# 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:

```rust
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](http://smallcultfollowing.com/babysteps/blog/2016/11/03/associated-type-constructors-part-2-family-traits/) and GATs.

```rust
#![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:

```rust
#![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.

```rust
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](https://github.com/willcrichton/tyrade) 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.

Navigation Menu

Uh oh!

Uh oh!

Overflow in checking recursive trait requirements with specialization #80700

The issue

An undesirable fix

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Uh oh!

Uh oh!

Overflow in checking recursive trait requirements with specialization #80700

Description

The issue

An undesirable fix

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions