Too many lists drop

I am reading and coding (and thoroughly enjoying the humor) through the Learning Rust with Entirely Too Many Linked Lists book.

However, I tried to extract functionality into a pop_node() method as suggested here. While the test still passes, I am not sure if the list actually gets dropped. I don't have a robust enough understanding of Rust's semantics around moving/dropping to be sure.

I saw this thread and looked at the testdrop crate, but I quickly realized that it only works for generic types where you can give the type a testdrop::Item to manage. My list isn't generic, it is of i32.

Is it in fact doing what I want and dropping the item, or did I miss something? And how should I go about thinking about this question, and which steps can I follow to figure it out on my own next time?

Code:

// Inside `impl List`
    fn pop_node(&mut self) -> Link {
        mem::replace(&mut self.head, Link::Empty)
    }

impl Drop for List {
    fn drop(&mut self) {
        while let Link::More(_) = self.pop_node() {}
    }
}

You could try it with leak sanitizer. The feature isn't stablized yet, but it is there.

I'm unfortunately on a Windows machine...

I don't think this does what you want. Imagine this on a list of 3 elements, 1, 2, 3.

First, drop is called.

In the first call to pop_node, self.head is replaced with Link::Empty. Then you're returning the old value of self.head, which should be More(Node { 1, Node { 2, More(Node { 3, Empty}) }) }.

Then back in drop, it does indeed match Link::More, so you continue the loop. But your while let just deconstructs it, assigning the inner value (Node { 1, Node { 2, More(Node { 3, Empty}) }) to _. As you aren't doing anything special to drop this, the compiler will drop it automatically - we will enter Node::drop, and then enter the recursive drop cycle the author describes!

Then, after dropping all of the nodes in the list, we try to run pop_node() again. But since we replaced self.head with Link::Empty the first time, it now just returns Link::Empty, and we quite the loop.

With this implementation, you will only loop once inside List::drop, and you'll still get the recursive dropping that the custom drop is necessary to avoid. It will drop everything, but could overflow the stack (as described in your link).

1 Like

For the sake of clarification, do note that, if you _had no explicit Drop impl on your List (the one using Boxes for its Link type), you would have:

fn main ()
{
    let mut list = List::new();
    (0 .. 6).map(PrintOnDrop).for_each(|i| list.push(i));
    while let Some(elem) = list.pop() {
        println!("> {}", elem.0);
        if elem.0 == 3 { break; }
    }
    println!();
    // drop(list);
}

outputting:

Deallocating 0x555b9345aae0
> 5
Dropping 5 at 0x7fff4b1fee1c

Deallocating 0x555b9345aac0
> 4
Dropping 4 at 0x7fff4b1fee1c

Deallocating 0x555b9345aaa0
> 3
Dropping 3 at 0x7fff4b1fee1c

Dropping 2 at 0x555b9345aa80
Dropping 1 at 0x555b9345aa60
Dropping 0 at 0x555b9345aa40
Deallocating 0x555b9345aa40
Deallocating 0x555b9345aa60
Deallocating 0x555b9345aa80

From this, we observe that:

  • all the (remaining) elements / nodes are automagically dropped, thanks to the nice properties of destructors and ownership;

  • the nodes are, however, deallocated in reverse order, meaning that there is indeed some form of stack / recursion going on, so a list with too many elements would blow up the stack

but by adding:

    impl<Elem> Drop for List<Elem> {
        fn drop (self: &'_ mut List<Elem>)
        {
            // replace `self.head` with an empty Link to no-op the inherent drop glue
            let mut this: Link<Elem> = mem::take(&mut self.head);
    
            while let Link::Cons(mut boxed_node) = this {
                this = mem::take(&mut boxed_node.next);
                // drop(boxed_node)
            }
        }
    }

we do get:

Deallocating 0x55e51b13bae0
> 5
Dropping 5 at 0x7ffc0fdf94ec

Deallocating 0x55e51b13bac0
> 4
Dropping 4 at 0x7ffc0fdf94ec

Deallocating 0x55e51b13baa0
> 3
Dropping 3 at 0x7ffc0fdf94ec

Dropping 2 at 0x55e51b13ba80
Deallocating 0x55e51b13ba80
Dropping 1 at 0x55e51b13ba60
Deallocating 0x55e51b13ba60
Dropping 0 at 0x55e51b13ba40
Deallocating 0x55e51b13ba40

which avoids overflowing the stack as before.


Now, regarding your code, @daboross is right:

on its first iteration does pop the head of the list, but it will stop there, as the second iteration will not yield a Link::More but a Link::Empty instead: in between, the whole list is dropped by the inherent drop glue from Box, in a recursive fashion.

What you intended to do is rather something like:

// have `fn pop_node(self: &'_ mut Link)` rather than `&'_ mut List`,
// since you always have _one_ list but many links/nodes.
impl Link {
    // The popped node will always have an _Empty_ `next` link.
    fn pop_node (self: &'_ mut Link)
      -> Link
    {
        let next = mem::replace(&mut self.next, Link::Empty);
        mem::replace(&mut self, next)
    }
}

impl Drop for List {
    fn drop (self: &'_ mut List)
    {
        let link: &'_ mut Link = &mut self.head;
        while let Link::More(_) = link.pop_node() {}
    }
}
5 Likes

I've finally looked at this again, and I came up with the following on my own:

impl Drop for List {
    fn drop(&mut self) {
        while let Link::More(_) = self.pop_node() {}
    }
}

impl List {
    fn pop_node(&mut self) -> Link {
        let next = match &mut self.head {
            Link::Empty => Link::Empty,
            Link::More(node) => mem::replace(&mut node.next, Link::Empty),
        };
        mem::replace(&mut self.head, next)
    }
}

It seems similar, but I'm not sure. I think it does keep the list's head a Link::More(_) so there's no stack blowup going on. Do I miss something?

2 Likes

Yep, that works too :+1:

2 Likes

Sorry for posting in drips and drabs...

I've revisited the "An OK stack" chapter as well now. It's very similar to the previous one, except that it uses Option and its methods instead of rolling our own Option-like enum and implementing all functionality by hand. However, my pop_node() implementation is causing me to wonder if I can simplify it via some methods on Option I missed in my scouring of the docs. Below follows the suggested answer which doesn't implement pop_node():

pub fn pop(&mut self) -> Option<T> {
    self.head.take().map(|node| {
        self.head = node.next;
        node.elem
    })
}

fn drop(&mut self) {
    let mut cur_link = self.head.take();
    while let Some(mut boxed_node) = cur_link {
        cur_link = boxed_node.next.take();
    }
}

Here is my implementation of pop(), pop_node() and drop():

pub fn pop(&mut self) -> Option<T> {
    self.pop_node().map(|node| node.elem)
}

fn pop_node(&mut self) -> Link<T> {
    let next = self.head.as_mut().map(|node| mem::replace(&mut node.next, None)).unwrap_or(None);
    mem::replace(&mut self.head, next)
}

fn drop(&mut self) {
    while let Some(_) = self.pop_node() {}
}

Another question: I tried the following:

fn pop_node(&mut self) -> Link<T> {
    mem::replace(&mut self.head, self.head.as_mut().map(|node| mem::replace(&mut node.next, None)).unwrap_or(None))
}

but I get

error[E0499]: cannot borrow `self.head` as mutable more than once at a time
  --> src\second.rs:32:38
   |
32 |         mem::replace(&mut self.head, self.head.as_mut().map(|node| mem::replace(&mut node.next, None)).unwrap_or(None))
   |         ------------ --------------  ^^^^^^^^^ second mutable borrow occurs
 here
   |         |            |
   |         |            first mutable borrow occurs here
   |         first borrow later used by call

error: aborting due to previous error

For more information about this error, try `rustc --explain E0499`.
error[E0499]: cannot borrow `self.head` as mutable more than once at a time
  --> src\second.rs:32:38
   |
32 |         mem::replace(&mut self.head, self.head.as_mut().map(|node| mem::replace(&mut node.next, None)).unwrap_or(None))
   |         ------------ --------------  ^^^^^^^^^ second mutable borrow occurs
 here
   |         |            |
   |         |            first mutable borrow occurs here
   |         first borrow later used by call

error: could not compile `lists`.

To learn more, run the command again with --verbose.
warning: build failed, waiting for other jobs to finish...
error: aborting due to previous error

For more information about this error, try `rustc --explain E0499`.
error: could not compile `lists`.

To learn more, run the command again with --verbose.

Is this case, where the second parameter's borrow ends before the first parameter's will be needed something that Polonius can understand? I get it is probably extremely difficult to handle this case correctly and it isn't really a problem, I'm just curious...

Found an answer in the next chapter :man_facepalming::

let next = self.head.as_mut().and_then(|node| mem::replace(&mut node.next, None))

It still doesn't allow me to put the expression directly into the function call as parameter.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.