Exponential compilation time for recursive data structures implementing traits with associated types.

[VFLashM]

I stumbled upon a case when recursive data structures implementing traits with associated types cause exponential compilation time and memory consumption.

Example is a bit complicated, but quite fragile. I couldn't simplify it further.
Looks like associated type is a required prerequisite for exponential behavior.

I did some basic profiling and it seems that slowdown is caused by exponential growth of obligation forest.

Code

Following code hangs the compiler:

use std::marker::PhantomData;

// Trait with associated type.
trait Trait<T> {
    type AssocType;
    fn foo(&self, a: T) -> T;
}

// End of recursion.
impl<T> Trait<T> for () {
    type AssocType = i32;
    fn foo(&self, a: T) -> T { a }
}

// Recursive struct. Nested type implements trait.
struct NestingStruct<T, SubStruct: Trait<T>>(
    SubStruct,
    PhantomData<T>,
);

impl<T, SubStruct> Trait<T> for NestingStruct<T, SubStruct> where
    SubStruct: Trait<T, AssocType=i32>,
{
    type AssocType = i32;
    fn foo(&self, a: T) -> T { self.0.foo(a) }
}

fn main() {
    let t = ();

    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    // No noticeable slowdown here.

    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    // Ten iterations take less than a second.

    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    // Fifteen iterations take several seconds on my machine.

    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    // Twenty iterations take several minutes.

    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    let t = NestingStruct(t, PhantomData);
    // Each consequent iteration doubles compilation time.
    // I believe it would take several hours to compile next block.

    println!("Hello {}", t.foo(1));
}

Meta

Bug exists in both stable and nightly.

rustc +nightly --verbose --version:

rustc 1.48.0-nightly (e599b53e6 2020-09-24)
binary: rustc
commit-hash: e599b53e67ddd197a09a3d8720eed872df481aa0
commit-date: 2020-09-24
host: x86_64-pc-windows-msvc
release: 1.48.0-nightly
LLVM version: 11.0