How to manage properly ownership with borrowing in Rust?

Question

I'm quite newbie in the Rust world and still not fully understand how ownership/borrowing/lifetime works. I have this example to demonstrate a struggle:

struct Node {
  value: bool,
  next: Option<Box<Node>>
}

fn populate(next: &mut Option<Box<Node>>) -> Option<Node> {
  let node = Node { value: true, next: None };
  let result = Some(Box::new(node));
  *next = result;
  Some(*next.unwrap())
}

fn main() {
  let mut node = Node {
    value: false,
    next: None
  };
  let result = populate(&mut node.next);
  println!("{}", node.unwrap().value);
  println!("{}", result.unwrap().value);
}

I don't understand why move this way works:

fn populate(next: &mut Option<Box<Node>>) -> Option<Node> {
  let node = Node { value: true, next: None };
  let result = Some(Box::new(node));
  // *next = result;
  Some(*result.unwrap() /* *next.unwrap() */)
}

But another way doesn't:

fn populate(next: &mut Option<Box<Node>>) -> Option<Node> {
      let node = Node { value: true, next: None };
      let result = Some(Box::new(node));
      *next = result;
      Some(*(*next.as_ref().unwrap())) // or Some(*next.unwrap())
 }

How to proper transfer ownership (like in example above) without copying but with borrowing mutating next reference (and not adding extra parameters)? I'm still not clear with this part...

score 2 · Accepted Answer · answered May 02 '20 at 14:29

If you want populate to return a reference to the new Node placed inside next, the reference needs to be part of the return type. You can't move (transfer ownership of) the node into next while also returning it; that's not how ownership works:

fn populate(next: &mut Option<Box<Node>>) -> Option<&mut Node> {
//                                            here: ^^^^

You might try to return Some(&mut *next.unwrap()), but that won't work because unwrap takes self by value. Fortunately, there's a convenient function on Option that will take you straight from &mut Option<Box<Node>> to Option<&mut Node>, as_deref_mut:

fn populate(next: &mut Option<Box<Node>>) -> Option<&mut Node> {
    let node = Node {
        value: true,
        next: None,
    };
    *next = Some(Box::new(node));
    next.as_deref_mut()
}

Also read

For the binary trees traversal and deserialisation problem this approach is working. Thanks. — Arsenius, May 03 '20 at 05:00
@Arsenius FWIW I strongly recommend reading through [that final link](https://rust-unofficial.github.io/too-many-lists/) before trying to do anything with recursively defined data structures (trees, lists, graphs) in Rust -- it covers a lot of ownership and borrowing peculiarities that you are likely to encounter and shows ways to work with and around them. Rust is a tricky language to write data structures in, even more so than C in some ways. — trent, May 03 '20 at 12:45

score 2 · Answer 2 · answered May 02 '20 at 14:34

fn populate(next: &mut Option<Box<Node>>) -> Option<Node> {
  let node = Node { value: true, next: None };
  let result = Some(Box::new(node));
  *next = result;
  Some(*result.unwrap() /* *next.unwrap() */)
}

Massaging the code as the compiler suggests may lead to something you wrote. Now, taking it, introducing intermediate variables and annotating types (to see what's going on) gives this:

fn populate2(next: &mut Option<Box<Node>>) -> Option<Node> {
    let node : Node = Node { value: true, next: None };
    let result : Option<Box<Node>> = Some(Box::new(node));
    *next = result;
    let next_as_ref : Option<&Box<Node>> = next.as_ref();
    let next_as_ref_unwrap : &Box<Node> = next_as_ref.unwrap(); 
    let next_as_ref_unwrap_deref : Box<Node> = *next_as_ref_unwrap; // <- error here!
    Some(*next_as_ref_unwrap_deref) // or Some(*next.unwrap())
}

let next_as_ref_unwrap_deref : Box<Node> = *next_as_ref_unwrap; fails, because next_as_ref_unwrap is a borrowed Box<Node>, i.e. a &Box<Node>. Dereferencing (i.e. *) next_as_ref_unwrap tries to move, which cannot be done from a borrowed variable.

The problem is that you have next, which contains (essentially) a Node, however, you want to return a Node. This poses the question: Do you want to return another (i.e. new Node), or do you want to extract (i.e. take) the Node from next and return it. In case you want to take and return it:

fn populate(next: &mut Option<Box<Node>>) -> Option<Node> {
  let node = Node { value: true, next: None };
  let result = Some(Box::new(node));
  *next = result;
  next.take().map(|boxed_node| *boxed_node)
}

The above code compiles, but is - at least - dubious, as it accepts a next that is essentially used as a local variable and made None afterwards (because we take from it).

You probably want to decide what populate actually should do.

Should it modify None? Why the return value Option<None>? Should it return next's old value? (Why return Option<Node> instead of Option<Box<Node>> then?)

Code:

fn populate_returning_old_val(next: &mut Option<Box<Node>>) -> Option<Node> {
  std::mem::replace(
    next,
    Some(Box::new(Node { value: true, next: None }))
  ).take().map(|boxed_node| *boxed_node)
}

The real problem I'm working on is binary trees traversal and deserialisation. When I need preorder and inorder traversal I facing such issue when I was unable to extract existing value.So the answer is yes I need to take Node from next (not create a copy). Maybe example not that good, because real solution too complex and too much code, I just simplified as much as I could but loose meaning Why, but question actually more related to How. Appreciate for assistance anyway. Thanks! — Arsenius, May 03 '20 at 03:29
But does it possible that `node.next.is_some()` and `result.is_some()` both is true? You code examples only works for `node.next.is_some() == true` or `result.is_some() == true` but never true for both. How to solve this? — Arsenius, May 03 '20 at 04:25

How to manage properly ownership with borrowing in Rust?

2 Answers2

Also read