Would someone explain this line of code? (mem::replace)

I'm trying to learn Rust. I've read the Rust Book and I've written a few small programs. But I recently started going through this site which talks about how to create linked lists with Rust: Introduction - Learning Rust With Entirely Too Many Linked Lists and I read everything and typed in the code along the way and got an app working. Now I'm trying to understand every single line and there is one that just doesn't make sense:

use std::mem;

type Link = Option<Box<Node>>;

struct Node {
    elem: i32,
    next: Link,
}

struct List {
    head: Link,
}

impl List {
    fn new() -> Self {
        List { head: None }
    }

    fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            // What does this mem::replace line do???
            next: mem::replace(&mut self.head, None)
        });

        self.head = Some(new_node)
    }

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

fn main() {
    let mut list = List::new();

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

    loop {
        let p = list.pop();

        match p {
            Some(value) => println!("{}", value),
            None => break
        }
    }
}

Assuming this is the first iteration I think self.head will be None which may be where I'm going wrong, because I thought mem::replace would replace the value of self.head with None...but it already is None is it not? In which case the next iteration would become None. How does it ever get a real value?

The mem::replace(&mut self.head, None) does indeed put None into self.head, returning the previous value of self.head so that it can be placed into the next field of the newly constructed new_node. The new_node is then assigned to self.head, so that is how it gets its value.

Taking the case you raised of starting from an empty list, we initially have that self.head == None. None then gets replaced with None, so self.head is still none and we have new_elem == Node { elem: 1, next: None } (ignoring the Box for a moment). That then becomes the head (and only element) of the list. Future calls to push() then create additional elements that chain onto that, themselves becoming the head of the list.

1 Like

It's odd to see that line using replace directly, because replacing with None is usually spelled Option::take -- they're exactly the same, see https://doc.rust-lang.org/1.33.0/src/core/option.rs.html#847-849 -- and the pop method is using .take().

3 Likes

looks like OPs code might be a mixture of different pieces of code in that book.The relevant page is

Option - Learning Rust With Entirely Too Many Linked Lists

It does of course explain the existence of take and that it's doing the same as the replace. The relevant / last version of the push method would be

    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    } 

Edit: At an earlier point

Push - Learning Rust With Entirely Too Many Linked Lists

the book also explains what mem::replace does.

[…] We need some way to get the head without Rust noticing that it's gone. For advice, we turn to infamous Rust Hacker Indiana Jones:

Ah yes, Indy suggests the mem::replace maneuver. This incredibly useful function lets us steal a value out of a borrow by replacing it with another value.

1 Like

Taking the case you raised of starting from an empty list, we initially have that self.head == None . None then gets replaced with None , so self.head is still none and we have new_elem == Node { elem: 1, next: None } (ignoring the Box for a moment). That then becomes the head (and only element) of the list. Future calls to push() then create additional elements that chain onto that, themselves becoming the head of the list.

Oh, OK, I think I see now. I don't think I understood that each new node would become the new head. It makes a little more sense now.

looks like OPs code might be a mixture of different pieces of code in that book.The relevant page is

That is correct, sorry. I got to a point where I had enough code to get things working, and I wanted to pause for a moment and try and get an understanding of where I was at. Right now the list only supports integers, but the tutorial goes on to describe how to make it generic which I have not gotten to yet.

Thank you all for your time, I really appreciate it. I think I'm slowly coming along.

Right on the next line:

self.head = Some(new_node);