data structures - `cannot move out of dereference of `&mut`-pointer` while building a sorted linked list

Question

So, I'm learning Rust and decided to build a sorted linked list. Everything looks nice until I reach the add method, here's the code:

struct NodeItem<'a, V:'a + Ord> {
  value : V,
  next : Box<Option<NodeItem<'a,V>>> // '
}

impl <'a, V:'a + Ord> NodeItem<'a,V> { // '

  fn new(value : V) -> NodeItem<'a,V> { // '
    NodeItem { value : value, next : box None }
  }

  fn add(&mut self, value : V) {

    match self.value.cmp(&value) {
      Less => {
        self.next = box Some(NodeItem {value: self.value, next : self.next });
        self.value = value;
      },
      Equal | Greater => {
        match *self.next {
          Some(ref mut next) => next.add(value),
          None => self.next = box Some(NodeItem::new(value)),
        }
      },
    }

  }

}

The compiler complains with:

/home/mauricio/projects/rust/data_structures/src/lists/mod.rs:16:47: 16:51 error: cannot move out of dereference of `&mut`-pointer
/home/mauricio/projects/rust/data_structures/src/lists/mod.rs:16         self.next = box Some(NodeItem {value: self.value, next : self.next });
                                                                                                               ^~~~
/home/mauricio/projects/rust/data_structures/src/lists/mod.rs:16:66: 16:70 error: cannot move out of dereference of `&mut`-pointer
/home/mauricio/projects/rust/data_structures/src/lists/mod.rs:16         self.next = box Some(NodeItem {value: self.value, next : self.next });

What is exactly the problem here? I understand that I am moving a reference somewhere else, but shouldn't the lifetime parameters show that these items have a related "life"?

This is using the nightly from 21/12/14.

Answer 1

Here's a similar example:

enum E { Hello }
struct A(E);

fn main() {
    let mut a = A(E::Hello);
    let b = &mut a;
    let c = b.0;
}

And the errors:

<anon>:7:13: 7:14 error: cannot move out of dereference of `&mut`-pointer
<anon>:7     let c = b.0;
                     ^
<anon>:7:9: 7:10 note: attempting to move value to here
<anon>:7     let c = b.0;
                 ^
<anon>:7:9: 7:10 help: to prevent the move, use `ref c` or `ref mut c` to capture value by reference
<anon>:7     let c = b.0;
                 ^

Note that the compiler tells you how to prevent the error in this case.

The problem is that your self.value is not Copyable. That means that when you assign it, you are moving it out of the NodeItem (self), thus leaving it no longer fully defined! This would be a bad thing, so Rust prevents you from doing it.

You have to decide what the right way of fixing your problem is. The easiest is to ensure that T is copyable (or maybe Cloneable, depending on your data). However, you probably don't want to be copying your data all around. I would investigate changing your code to prevent copying the node around and just updating entries. You may need to use something like swap.

Where I take all the fun out of exploring a new language

#[derive(Debug)]
struct Node<T> {
    v: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Node<T> {
    fn new(v: T) -> Node<T> { Node { v: v, next: None } }

    fn push_front(self, head: T) -> Node<T> {
        Node {
            v: head,
            next: Some(Box::new(self)),
        }
    }

    fn push_back(&mut self, tail: T) {
        match self.next {
            Some(ref mut next) => next.push_back(tail), 
            None => self.next = Some(Box::new(Node::new(tail))),
        }
    }

    fn push_after(&mut self, v: T) {
        let old_next = self.next.take();

        let new_next = Node {
            v: v,
            next: old_next,
        };

        self.next = Some(Box::new(new_next));
    }
}

fn main() {
    let mut n = Node::new(2u8);
    n.push_back(3u8);
    let mut n = n.push_front(0u8);
    n.push_after(1u8);

    println!("{:?}", n);
}