27

I'm writing a linked list to wrap my head around Rust lifetimes, ownership and references. I have the following code:

pub struct LinkedList {
    head: Option<Box<LinkedListNode>>,
}

pub struct LinkedListNode {
    next: Option<Box<LinkedListNode>>,
}

impl LinkedList {
    pub fn new() -> LinkedList {
        LinkedList { head: None }
    }

    pub fn prepend_value(&mut self) {
        let mut new_node = LinkedListNode { next: None };

        match self.head {
            Some(ref head) => new_node.next = Some(*head),
            None => new_node.next = None,
        };

        self.head = Some(Box::new(new_node));
    }
}

fn main() {}

But I am getting the following compilation error:

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:18:52
   |
18 |             Some(ref head) => new_node.next = Some(*head),
   |                                                    ^^^^^ cannot move out of borrowed content

Newer versions of Rust have a slightly different error:

error[E0507]: cannot move out of `*head` which is behind a shared reference
  --> src/main.rs:18:52
   |
18 |             Some(ref head) => new_node.next = Some(*head),
   |                                                    ^^^^^ move occurs because `*head` has type `std::boxed::Box<LinkedListNode>`, which does not implement the `Copy` trait

I'm thinking that the head node must currently be owned by self, which is the linked list. When I assign it to new_node.next, there is probably a change of ownership that will happen.

I would rather not clone the value if possible as that seems wasteful. I don't want to just "borrow" it for the duration of the function. I really want to transfer its ownership.

How do I do that?

I have already looked at cannot move out of borrowed content when unwrapping a member variable in a &mut self method and Cannot move out of borrowed content / cannot move out of behind a shared reference.

I tried removing the match arm as suggested in the accepted answer in one of those questions and defining next in the creation of the new LinkedListNode, but I get the same error message.

I have successfully added an append method which takes a LinkedListNode to add to the end of the list.

1

1 Answer 1

52

Cannot move out of borrowed content when trying to transfer ownership

At a high-level, this is against-the-grain for Rust. You cannot transfer ownership of something borrowed because you don't own it. You shouldn't borrow my car (&Car) and then give it to the first person you see on the street! This is still true even if I lend you my car and allow you to make changes to it (&mut Car).

You cannot move head out of a &self at all because you cannot mutate the value.

You cannot move head out of a &mut self because this would leave the LinkedList struct in an inconsistent state - one of the fields would have an undefined value. This is a core measure of Rust's safety guarantees.

In general, you will need to follow something from How can I swap in a new value for a field in a mutable reference to a structure? to replace the existing value.

In this case, you can use Option::take. This will leave the variable where it is, changing it in-place to a None and returning the previous value. You can then use that value to build the new head of the list:

pub fn prepend_value(&mut self) {
    let head = self.head.take();
    self.head = Some(Box::new(LinkedListNode { next: head }));
}

A more generic solution is to take ownership of the struct instead of borrowing it. This allows you to do whatever you want to it. Note that we take self by-value, not by-reference:

pub fn prepend_value(mut self) -> LinkedList {
    self.head = Some(Box::new(LinkedListNode { next: self.head }));
    self
} 
3
  • Which of the two solutions would you say is more idiomatic code?
    – Gilles
    Commented Feb 2, 2015 at 15:23
  • 1
    Since you have a Node and a wrapper List, I'd probably use the version with take; I think people understand &mut self more than self. If the list was just composed of the Nodes, you'd have to use the self version. I'd probably annotate it as #[must_use] as well, to help guide users.
    – Shepmaster
    Commented Feb 2, 2015 at 15:28
  • @Shepmaster Thank you soooo much, I had no idea take was used like this.
    – Gabu
    Commented Aug 6, 2021 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.