Unexpected stack overflow when creating linked list

Question

I've been trying to find my way around Rust a bit by expanding the linked list example provided by the Rust tutorial

I've written a constructor that converts a generic vector into a linked list, but using it causes a stack overflow if the vector is sufficiently large. This is confusing to me because I thought the linked list was created on the heap, since each element in the list has an owned box containing the next element.

Rust is the first language I've used where I've had to worry about memory management so I'm a bit lost. An explanation would be appreciated, a solution doubly so. Thanks!

My code truncated to the relevant gubbins only:

use std::mem::swap;

enum ListItem<T> { 
    Node(T, Box<ListItem<T>>), 
    Cap 
}

impl <T> ListItem<T> {
    fn append(&mut self, x: T) {
        match *self {
            Node(_, ref mut a@box Cap) => *a = box Node(x, box Cap),
            Node(_, ref mut a@box Node(_, _)) => a.append(x),
            Cap => {
                let mut n = Node(x, box Cap);
                swap(&mut n, self);
            }
        };
    }
}

impl <T: Clone> ListItem<T> {
    fn new_from_vec(x: &mut Vec<T>) -> ListItem<T>{
        let mut l = Cap;
        for v in x.iter() {
            l.append((*v).clone());
        }
        return l;
    }
}

fn main() {
    let mut v: Vec<int> = vec![];

    for n in range(1i, 500001) {
        v.push(n);
    }

    println!("Done creating vector.");

    let x = ListItem::new_from_vec(&mut v);

    println!("Done creating linked list.");
}

It prints Done creating vector., but then prints task '<main>' has overflowed its stack before getting to the next println!.

Answer 1

A stack-overflow is generally a sign of a recursion going too deep. If you look carefully at your code you might spot the recursion:

impl <T> ListItem<T> {
    fn append(&mut self, x: T) {
        match *self {
            Node(_, ref mut a@box Cap) => *a = box Node(x, box Cap),
            Node(_, ref mut a@box Node(_, _)) => a.append(x),       // <---
            Cap => {
                let mut n = Node(x, box Cap);
                swap(&mut n, self);
            }
        };
    }
}

This means that for each element already in list, you create a new function frame on the stack (unless the compiler optimizes it out), which for a sufficient number of elements will overflow the stack deterministically.

To avoid the overflow, you could switch to an iterative version (with a loop).

Answer 2

Unfortunately Rust does not do tail call optimizations which means you can't rely on recursion for iteration heavy operations.

According to this ticket it seems unlikely that they will add this feature in the future.

I'm afraid you have to convert your code into a regular loop.