How does ownership of variables work between iterations?

user_5756583 0
Viewed 84

I am trying to learn rust and thought of implementing a linked list as a practice problem to understand Ownership/Borrow concepts and I am having a hard time.

The push method of LinkedList should work as:

t = 0 | root: None | push 5
t = 1 | root: { value: 5, next: None } | push 6
t = 2 | root: { value: 5, next: { value: 6, None } } |

Here's the code trying to do the same:

#[derive(Debug, Clone)]
struct Node {
  value: u32,
  next: Option<Box<Node>>,
}

impl Node {
  fn new(value: u32) -> Node {
    Node { value, next: None }
  }
}

#[derive(Debug, Clone)]
struct LinkedList {
  root: Option<Box<Node>>,
}

impl LinkedList {
  fn new(node: Option<Box<Node>>) -> LinkedList {
    LinkedList { root: node }
  }

  fn push(self, node: Option<Box<Node>>) {
    let maybe_node = self.root;

    loop {
      match maybe_node {
        Some(tail_node) => {  // use of moved value. std::boxed::Box<Node> doesn't implement copy trait. --- (1)
          if tail_node.next.is_none() {
            tail_node.next = node; // tail_node is not mutable. --- (2)
            break;
          };
        }
        _ => (),
      }
    }
  }
}

fn main() {
  let mut node = Node::new(0);
  let linked_list = LinkedList::new(Some(Box::new(node)));

  for number in 1..5 {
    node = Node::new(number);
    linked_list.push(Some(Box::new(node))); // move occurs. Value moved here in a previous iteration --- (3)
  }
  println!("{:?}", linked_list);
}

I don't understand the "move occurs" errors (1, 3) it isn't clear to me where the value moved? It appears iterations are causing the ownership to change but I can't see how.

Also, the error (2) Is my implementation the best way?

rust
1 Answers

In Rust there two ways is which ownership is handled, and that is either move semantic or borrow semantic. Here are some rules to go about understanding it.

The first rule is that each piece of data can have only a single owner at same time. If you assign some variable to some other variable, then you effectively move the data, and the data becomes owned by new owner.

The second rule is that if you have some data, which is owned by someone, but you would like to read it, then you can borrow it. Borrowing is essentially obtaining a reference to data, which is owned by someone else.

Now back to your problem. In your function declaration you have declared the first parameter as self


fn push(self, node: Option<Box<Node>>) {
   let maybe_node = self.root;

   loop {
     match maybe_node {
       Some(tail_node) => {  // use of moved value. std::boxed::Box<Node> doesn't implement copy trait. --- (1)
         if tail_node.next.is_none() {
           tail_node.next = node; // tail_node is not mutable. --- (2)
           break;
         };
       }
       _ => (),
     }
   }
 }

this essentially means that when you call your function you are taking the ownership of self, and thus you are invalidating any previous owner. What happens in the loop is that in the first iteration the value is moved into the function and is no longer owned by linked_list. In second iteration you again try to access the data, but it is no longer valid, since it was moved into the function.

To circumvent your problem you will need to declare your function as follows:

 fn push(&mut self, node: Option<Box<Node>>) {
    let maybe_node = self.root;

    loop {
      match maybe_node {
        Some(tail_node) => {  // use of moved value. std::boxed::Box<Node> doesn't implement copy trait. --- (1)
          if tail_node.next.is_none() {
            tail_node.next = node; // tail_node is not mutable. --- (2)
            break;
          };
        }
        _ => (),
      }
    }
  }

With declaration above you are saying that you are borrowing self, and that you would like to make changes to it ( that is the reason we have &mut and not just & ).

For more details please refer to the chapter about ownership in Rust book.

user_104773230
Related