Linked list stack overflow

Question

Consider this simple linked list implementation:

enum Cons<T> {
    Empty,
    Cons(T, Box<Cons<T>>),
}

fn main() {
    let mut list = Cons::Empty;
    for i in 1..1_000_000 {
        list = Cons::Cons(i, Box::new(list));
    }
    println!("Hello, world!");
}

^Playground

Why does it overflow the stack?

Answer 1

It overflows the stack on trying to drop list. The drop glue generated by Rust simply drops all fields in order, so it's going to look something like this (pseudo-code):

match self {
    Self::Empty => {},
    Self::Cons(a, b) => {
        Drop::drop(&mut a);
        Drop::drop(&mut b);
    }
}

The call Drop::drop(&mut b); is going to recurse to this same drop code (indirectly through Box's drop code), and it will continue to recurse 1,000,000 times in order to drop the entire list. Though, note that it will actually create 2,000,000 stack frames as Cons's drop glue and Box's drop implementation are going to call each other. This overflows the stack. (Note that tailcall optimization can't even be performed, because b is a box -- the box needs to be destroyed after the inner Cons is dropped.)

Fixing this seems straightforward but requires a few hacks since you can't move out of values that implement Drop.

The basic approach is to implement Drop manually and recursively drop the structure using iteration instead of recursive function calls. To help with this, we can create a method that will "steal" an existing Cons<T> leaving it Empty. We can use this to pull the Cons<T> value out of the box without actually moving it out as far as Rust is concerned.

impl<T> Cons<T> {
    pub fn take(&mut self) -> Cons<T> {
        std::mem::replace(self, Self::Empty)
    }
}

Easy enough. Now we can implement Drop around this method.

Notably, we have to check for the non-recursive cases first (self is Empty or is a Cons whose box is also Empty) to avoid accidental infinite recursion¹. Once we know we have at least one level of recursion, we can simply loop forward in the structure, take()-ing the next item into our iteration variable:

impl<T> Drop for Cons<T> {
    fn drop(&mut self) {
        match self {
            Self::Empty => return,
            Self::Cons(_, boxed) if matches!(**boxed, Self::Empty) => return,
            _ => {}
        };

        let mut v = self.take();

        while let Self::Cons(_, boxed) = &mut v {
            v = boxed.take();
        }
    }
}

Now, whenever Rust's generated drop glue gets ahold of a Cons value, it will always either be Empty or be a Cons whose box is Empty.

---

¹ The line let mut v = self.take(); will cause infinite recursion of our drop() implementation if we don't first check for the terminating cases. It will unconditionally create a new Cons<T> value, which must be dropped, but drop() will then unconditionally create another Cons<T> when it tries to drop that one. The match block detects the terminating cases to avoid creating a new Cons<T> when Rust's own drop glue will correctly handle the value without recursing more than once.