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

Herzen

I don't know enough about the compiler to explain why this is causing an infinite loop, but an aside: you should read 'Learning Rust With Entirely Too Many Linked Lists' if you haven't already! Linked lists are deceptively tricky to get right in Rust. – Enteron

What’s the meaning of the pair? Box<List<Pair<i32, T>>> seems like a weird type in Cons. – Ierna

@JoeClay thanks, I'm still at the beginning stages of learning Rust, so this'll help a lot – Herzen

@Ierna This is just a simplified example. I tried to port Haskell's FingerTrees and see how far I can get. – Herzen

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.

Paulinepauling

So basically Rust will compute a (possibly cyclic) dependency graph of types? And I suppose if the graph grows too large, the compiler will complain. Is this due to the implementation of rustc or can this behaviour change in the future? – Herzen

play.rust-lang.org/… It gives the same error. size_of<T> == size_of<Pair<T>> – Gorged

@Gorged Yes, see the explanation at the end that I edited in after. It's not related to the size of the type in bytes, but the relative space required to describe it. – Paulinepauling