Repository: rust
Issue: Resolving recursive traits with type parameters requires exponential memory in certain cases
Labels: C-enhancement,A-trait-system,I-compiletime,T-compiler,I-compilemem,T-types,fixed-by-next-solver

This is an extremely niche case, but after asking about it on the rust community Discord I was told I should open an issue. 

When trying to compile this code, the memory use (and compile time) increases exponentially with the nesting depth of `I`:

```rust
trait Op<S, T> {
    type Result;
}

impl<
    I: Op<(), A>,
    J: Op<(), (F, (F, R)), Result = A>,
    S: Op<(), I::Result>,
    A, F, R
> Op<S, (F, R)> for (I, J) {
    type Result = S::Result;
}

impl<S, T> Op<S, T> for () {
    type Result = T;
}

type I<T> = (T, ());

type Ty = I<I<I<I<I<I<I<I<I<I<()>>>>>>>>>>;

// nesting `I` more times causes exponential increase in compile time and memory usage
// about 13 is where it becomes noticeable
type Test = <I<I<I<Ty>>> as Op<(), (u8, i8)>>::Result;

fn main() {
    // force the compiler to actually evaluate Test and show an error message
    // with the type of Test
    println!("{}", Test::default().push(1));
}
```
The actual amount of work the compiler is doing should not be growing exponentially. We can see this by doing the work in 2 parts:
```rust
// we break the 13 level deep nesting into 7 and 6
// <I<I<I<I<I<I<I<()>>>>>>> as Op<(), (u8, i8)>>::Result
// finding this took almost no time or memory
type O = (u8, (u8, (u8, (u8, (u8, (u8, (u8, (u8, i8))))))));

// resolving this takes almost no time or memory
type Test = <I<I<I<I<I<I<()>>>>>> as Op<(), O>>::Result;
```
Recursive trait implementations that do generate exponentially large types generally cause the compiler to hang with memory increasing very slowly, however with this I was able to use all 16GB of RAM and 8GM of swap on my computer in about 5 minutes.

The reason I think this is a bug and not just a general limitation of Rust is that re writing the code to not use traits with type parameters causes the memory use to grow linearly instead. This code does exactly the same as the original example, except replacing `T as Op<U, S>` with `(T, U, S) as Op`:

```rust
trait Op {
    type Result;
}

impl<I, J, S, F, R, A, C, D> Op for ((I, J), S, (F, R)) where
    (J, (), (F, (F, R))): Op<Result = A>,
    (I, (), A): Op<Result = C>,
    (S, (), C): Op<Result = D>,
{
    type Result = D;
}

impl<S, T> Op for ((), S, T) {
    type Result = T;
}

type I<T> = (T, ());

type Ty = I<I<I<I<I<I<I<I<I<I<()>>>>>>>>>>;

type Test = <(I<I<I<Ty>>>, (), (u8, i8)) as Op>::Result;

fn main() {
    println!("{}", Test::default().push(1));
}
```
This is surprising, since I thought that this was basically how traits with type parameters were handled by the compiler.

I have done some testing, and even small changes cause this behavior to not happen. Note that while these are identical to the original example for this type, they don't behave exactly the same for some other types:
```rust
trait Op<T> {
    type Result;
}

impl<
    I: Op<A>,
    J: Op<(F, (F, R)), Result = A>,
    A,
    F, R,
> Op<(F, R)> for (I, J) {
    type Result = I::Result;
}

impl<T> Op<T> for () {
    type Result = T;
}

type I<T> = (T, ());

type Ty = I<I<I<I<I<I<I<I<I<I<()>>>>>>>>>>;

type Test = <I<I<I<Ty>>> as Op<(u8, i8)>>::Result;

fn main() {
    println!("{}", Test::default().push(1));
}
```

```rust
trait Op<S, T> {
    type Result;
}

impl<
    I: Op<(), (F, (F, R))>,
    S: Op<(), I::Result>,
    J, F, R
> Op<S, (F, R)> for (I, J) {
    type Result = S::Result;
}

impl<S, T> Op<S, T> for () {
    type Result = T;
}

type I<T> = (T, ());

type Ty = I<I<I<I<I<I<I<I<I<I<()>>>>>>>>>>;

type Test = <I<I<I<Ty>>> as Op<(), (u8, i8)>>::Result;

fn main() {
    println!("{}", Test::default().push(1));
}
```

```rust
trait Op<S, T> {
    type Result;
}

impl<
    I: Op<(), J::Result>,
    J: Op<(), (F, (F, R))>,
    S: Op<(), I::Result>,
    F, R
> Op<S, (F, R)> for (I, J) {
    type Result = S::Result;
}

impl<S, T> Op<S, T> for () {
    type Result = T;
}

type I<T> = (T, ());

type Ty = I<I<I<I<I<I<I<I<I<I<()>>>>>>>>>>;

type Test = <I<I<I<Ty>>> as Op<(), (u8, i8)>>::Result;

fn main() {
    println!("{}", Test::default().push(1));
}
```