Why is it impossible to instantiate a data structure due to "overflow while adding drop-check rules"? [duplicate]

Question

Here is a data structure I can write down and which is accepted by the Rust compiler:

pub struct Pair<S, T>(S, T);

pub enum List<T> {
    Nil,
    Cons(T, Box<List<Pair<i32, T>>>),
}

However, I cannot write

let x: List<i32> = List::Nil;

playground

as Rust will complain about an "overflow while adding drop-check rules". Why shouldn't it be possible to instantiate List::Nil?

It should be noted that the following works:

pub struct Pair<S, T>(S, T);

pub enum List<T> {
    Nil,
    Cons(T, Box<List<T>>),
}

fn main() {
    let x: List<i32> = List::Nil;
}

playground

Answer 1

When the type hasn't been instantiated, the compiler is mostly worried about the size of the type being constant and known at compile-time so it can be placed on the stack. The Rust compiler will complain if the type is infinite, and quite often a Box will fix that by creating a level of indirection to a child node, which is also of known size because it boxes its own child too.

This won't work for your type though.

When you instantiate List<T>, the type of the second argument of the Cons variant is:

Box<List<Pair<i32, T>>>

Notice that the inner List has a type argument Pair<i32, T>, not T.

That inner list also has a Cons, whose second argument has type:

Box<List<Pair<i32, Pair<i32, T>>>>

Which has a Cons, whose second argument has type:

Box<List<Pair<i32, Pair<i32, Pair<i32, T>>>>>

And so on.

Now this doesn't exactly explain why you can't use this type. The size of the type will increase linearly with how deeply it is within the List structure. When the list is short (or empty) it doesn't reference any complex types.

Based on the error text, the reason for the overflow is related to drop-checking. The compiler is checking that the type is dropped correctly, and if it comes across another type in the process it will check if that type is dropped correctly too. The problem is that each successive Cons contains a completely new type, which gets bigger the deeper you go, and the compiler has to check if each of these will be dropped correctly. The process will never end.