Why does my iterative implementation of drop for a linked list still cause a stack overflow?

Question

I am following Learning Rust With Entirely Too Many Linked Lists to write my first program in Rust. I changed the program to:

use std::mem;

#[derive(Debug)]
pub enum List {
    Nil,
    More(Box<Node>),
}

#[derive(Debug)]
pub struct Node {
    val: i32,
    next: List
}

impl List {
    pub fn new() -> Self {
        List::Nil
    }

    pub fn insert(&mut self, v : i32) {
        let old_head = mem::replace(&mut *self, List::Nil);
        let new_head = List::More(Box::new(Node { val : v, next: old_head}));
        *self = new_head
    }

    pub fn remove(&mut self) -> Option<i32> {
        match mem::replace(&mut *self, List::Nil) {
            List::Nil => {
                None
            },
            List::More(ref mut boxed_node) => {
                let result = Some(boxed_node.val);
                *self = mem::replace(&mut boxed_node.next, List::Nil);
                result
            }
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut head = mem::replace(&mut *self, List::Nil);

        while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
            head = mem::replace(&mut node.next, List::Nil);
        }
    }
}

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let mut list = List::new();
        list.insert(7);
        assert_eq!(Some(7), list.remove());
        assert_eq!(None, list.remove());

        list.insert(1);
        list.insert(2);
        list.insert(3);

        assert_eq!(Some(3), list.remove());
        assert_eq!(Some(2), list.remove());
        assert_eq!(Some(1), list.remove());
        assert_eq!(None, list.remove());
    }

    #[test]
    fn drop_long_list() {
        let mut list = List::new();
        for i in 1..100000 {
            list.insert(i);
        }
    }
}

Both of my tests are failing with a stack overflow in drop. Is it because of *self in RHS?

I don't know what is happening with let mut head = mem::replace(&mut *self, List::Nil);.

My understanding is:

1. It sets List::Nil in self.
2. Puts original value of self in head.

Is *self doing something more?

I also tried this version of drop:

impl Drop for List {
    fn drop(&mut self) {
        let mut head = mem::replace(self, List::Nil);

        while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
            head = mem::replace(&mut node.next, List::Nil);
        }
    }
}

Another try:

impl Drop for List {
    fn drop(&mut self) {
        while true {
            match self {
                &mut List::Nil => break,
                &mut List::More(ref mut node) => {
                    *self = mem::replace(&mut node.next, List::Nil)
                }
            }
        }
    }
}

error[E0506]: cannot assign to `*self` because it is borrowed
  --> src\list.rs:48:21
   |
47 |                 &mut List::More(ref mut node) => {
   |                                 ------------ borrow of `*self` occurs here
48 |                     *self = mem::replace(&mut node.next, List::Nil)
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `*self` occurs here

Answer 1

Whenever you write recursive (or iterative) code, you need to have a stopping condition. Your code doesn't, so it loops forever.

---

Producing a MCVE of your problem is always a good start:

use std::mem;

#[derive(Debug)]
pub enum List {
    Nil,
    More(Box<List>),
}

impl Drop for List {
    fn drop(&mut self) {
        let mut head = mem::replace(self, List::Nil);

        while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
            head = mem::replace(node, List::Nil);
        }
    }
}

#[test]
fn basics() {
    List::Nil;
}

Then annotate the code to see where it's recurring:

fn drop(&mut self) {
    eprintln!("1");
    let mut head = mem::replace(self, List::Nil);
    eprintln!("2");
    while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
        eprintln!("3");
        head = mem::replace(node, List::Nil);
        eprintln!("4");
    }
    eprintln!("5");
}

This prints out

1
2
1
2

so delete everything after that:

fn drop(&mut self) {
    eprintln!("1");
    let mut head = mem::replace(self, List::Nil);
    eprintln!("2");
}

Why does this cause infinite recursion? You've defined it so that in order to drop List, you have to create a new List, which in turn needs to be dropped, which creates a new List, which...

Add a stopping condition:

fn drop(&mut self) {
    if let List::Nil = *self { return }

    let mut head = mem::replace(self, List::Nil);

    while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
        head = mem::replace(node, List::Nil);
    }
}

No more infinite recursion.

Then expand back out to the original and try again. It works for this test case, but not for List::More(Box::new(List::Nil)) so we shrink it back:

fn drop(&mut self) {
    eprintln!("1");
    if let List::Nil = *self { return }
    eprintln!("2");
    let mut head = mem::replace(&mut *self, List::Nil);
    eprintln!("3");
    while let List::More(ref mut node) = mem::replace(&mut head, List::Nil) {
        eprintln!("4");
        head = mem::replace(node, List::Nil);
        eprintln!("5");
    }
    eprintln!("6");
}

1
2
3
4
1
5
1
2
3
4
1
5

The problem now is that when we re-assign head, the value we are overwriting needs to be dropped, which triggers the recursion again.

Fixing this is complicated. Like, surprisingly so. You ready for this?

impl Drop for List {
    fn drop(&mut self) {
        match *self {
            List::Nil => return,
            List::More(ref more) => {
                if let List::Nil = **more {
                    return;
                }
            }
        }

        let mut head = mem::replace(self, List::Nil);

        while let List::More(ref mut next) = {head} {
            head = mem::replace(next, List::Nil);
        }
    }
}

This now has two stopping conditions:

1. Nil
2. More(Nil)

In every other case, we iteratively convert the More(x) into a More(Nil), which is handled by the stopping condition. That means that we only have a single depth of recursion: for each value that is dropped when the previous value of head goes out of scope when it is replaced.

---

For your original code:

impl Drop for List {
    fn drop(&mut self) {
        match *self {
            List::Nil => return,
            List::More(ref more) => {
                if let List::Nil = more.next {
                    return;
                }
            }
        }

        let mut head = mem::replace(self, List::Nil);

        while let List::More(ref mut node) = {head} {
            head = mem::replace(&mut node.next, List::Nil);
        }
    }
}

---

In the original tutorial you linked, this isn't a problem because the definition of List::drop doesn't modify self at all so it's not self-recursive:

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);
        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
        }
    }
}

Answer 2

You are getting a stack overflow because your drop function is infinitely recursive.

The code below:

let mut head = mem::replace(self, List::Nil);

Stores a List object in head, which will be dropped at the end of the scope. This means that, while you are dropping, you create a new list which also needs to be dropped. Repeat this enough times and you get a stack overflow.

Note: in the tutorial you linked, they use let mut cur_link = mem::replace(&mut self.head, Link::Empty) to avoid recursion.