rustc hangs on a non-regular ADT

[matklad]

This will keep CPU on 100% while slowly eating all the memory:

struct S<T> {
    a: Option<Box<S<(T, T)>>>,
    b: T,
}

fn main() {
    S { a: None, b: 0i32 };
}

It's interesting that if I don't try to construct an instance of S, the program will compile just fine.

1.11.0 stable and 1.13.0 nightly are affected.

[TimNN]

Using a one element tuple ((T,)) produces the following error:

error[E0320]: overflow while adding drop-check rules for S<i32>
 --> <anon>:7:5
  |
7 |     S { a: None, b: 0i32 };
  |     ^^^^^^^^^^^^^^^^^^^^^^
  |
note: overflowed on struct S field a type: std::option::Option<Box<S<((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((i32,),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),)>>>
 --> <anon>:7:5
  |
7 |     S { a: None, b: 0i32 };
  |     ^^^^^^^^^^^^^^^^^^^^^^

error[E0320]: overflow while adding drop-check rules for std::option::Option<Box<S<(i32,)>>>
 --> <anon>:7:12
  |
7 |     S { a: None, b: 0i32 };
  |            ^^^^
  |
note: overflowed on enum std::option::Option variant Some field 0 type: Box<S<((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((i32,),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),),)>>
 --> <anon>:7:12
  |
7 |     S { a: None, b: 0i32 };
  |            ^^^^

error: aborting due to 2 previous errors

[TimNN]

So the problem here seems to be, that due to the two element tuple, the type is growing exponentially and will probably consume all available ram long before the recursion limit has been reached.

For those interested, here's a (truncated) log file: https://gist.github.com/4ea8b6207bd2b66e0899d90f8e30dfb7

[isabelmu]

I'm not sure, but it's possible that the underlying problem of issue 4363, infinite type generation, was never addressed. @nikomatsakis mentioned the possible need for an additional admission test for types in this comment from 2013. At the time the compiler was checking whether types are 'representable' (is the size finite?), 'instantiable' (can we write a finite-length instantiating expression?), but not whether they were 'monomorphizable' (will a finite amount of nested types be generated?).

I think such an is_monomorphizable check should catch this problem.

[Mark-Simulacrum]

Closing.

error[E0320]: overflow while adding drop-check rules for S<i32>
 --> test.rs:7:5
  |
7 |     S { a: None, b: 0i32 };
  |     ^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: overflowed on i32

error[E0320]: overflow while adding drop-check rules for std::option::Option<std::boxed::Box<S<(i32, i32)>>>
 --> test.rs:7:12
  |
7 |     S { a: None, b: 0i32 };
  |            ^^^^
  |
  = note: overflowed on i32

error: aborting due to 2 previous errors