Newbie moving ownership question

Hi everyone. I am new to Rust and struggling to wrap my head around about moving ownership.
I cannot understand why the following works while...

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

type Link = Option<Box<ListNode>>;

fn recursively(head: Link, prev: Link) -> Link {
    if let Some(mut inner_head) = head {
        if let Some(next) = inner_head.next {
            inner_head.next = prev;
            recursively(Some(next), Some(inner_head))
        } else {
            inner_head.next = prev;
            Some(inner_head)
        }
    } else {
        None
    }
}

while it won't work anymore if I move inner_head.next = prev; up and outside the destructuring next block with compilation error:

42 |             if let Some(next) = inner_head.next {
   |                         ---- value moved here
43 |                 Self::recursively(Some(next), Some(inner_head))
   |                                                    ^^^^^^^^^^ value used here after partial move
   |
   = note: move occurs because value has type `std::boxed::Box<data_strucutures::reverse_linked_list::ListNode>`, which does not implement the `Copy` trait

It complains that it was moved at inner_head.next. I don't understand why accessing the field next is kind of a move.

Let's imagine what happens if we take the first branch of the if in each case:

Assignment inside if:

  1. First we take out the value in inner_head.next and assign it the name next.
  2. Next we put a new value into inner_head.next, namely prev.

Assignment outside if:

  1. First we replace the value inner_head.next with prev.
  2. Then we take out the value stored in inner_head.next, (that is, we take out prev).

The second case fails because you try to give ownership of inner_head away when calling recursively, but it's currently in a broken state: One of the fields have been taken out.

1 Like

Note that, independent of ownership, your proposed "optimization" also breaks the algorithm by overwriting the next reference before retrieving it for later use. In release mode the compiler will perform the optimization you meant to achieve on it's own; you don't need to do it.

1 Like

If you're trying to get rid of the double if, the reason you can't is because the base case of the recursion is slightly wrong: when head is empty, you should return prev, not None. That allows you to replace inner_head.next with prev unconditionally in the recursive case. Use mem::replace to get the old value of inner_head.next at the same time so you can pass it down the stack.

use std::mem;

fn recursively(head: Link, prev: Link) -> Link {
    if let Some(mut inner_head) = head {
        let next = mem::replace(&mut inner_head.next, prev);
        recursively(next, Some(inner_head))
    } else {
        prev
    }
}

The behavior of this function is different from your original when head is None and prev is non-None.

2 Likes

Wow. I heard Rust is a strong community and now I am really convinced by the prompt replies.
@alice. Thank you for explaining it. Now I realize I was giving away the ownership of inner_head while the giving action itself is still using the content of the inner_head (i.e. inner_head.next) as it is still inside the if.

@TomP Thank you for pointing it out the compiler will optimize for us eventually. In fact, I'd noticed my "optimization" attempt will break the algo but I am interested in why it complained it was moved anyway. And I think asking it here and help me understand more. And indeed it helps a lot!

1 Like

My approach will reach base case None only when the input head is really a None. Normally, when it reaches the tail of the linked list, it should go to Some(inner_head) and stop recursion there.
But yeah, yours look much more precise :+1: And good to know the mem::replace too! Thanks!

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.