Beginner question: can you move a Box<T> and take a reference to the struct it points to simultaneously?

help
1

I've been going through the tutorial Learn Rust With Entirely Too Many Linked Lists. I know rolling your own singly-linked list code isn't idiomatic, I'm just trying to get more familiar with the borrow checking rules.

I wanted to expand on the singly-linked list interface by implementing Clone for the list. It uses a private function in the implementation called copy_list. This is basically me translating what I'd write in C to Rust: indirect would be a pointer to a pointer to the node, and the whole loop, store through it to update the last next pointer of the list. Translating it to Rust leads to this:

impl<T: Clone> Clone for List<T> {
    fn clone(&self) -> Self {
        List { 
            head: copy_list(&self.head),
            length: self.length
        }
    }
}

fn copy_list<T: Clone>(list_node: &Option<Box<Node<T>>>) -> Option<Box<Node<T>>> {
    let mut new_list: Option<Box<Node<T>>> = None;
    let mut indirect = &mut new_list;

    let mut current = list_node;
    while let Some(node) = current {
        let new_node = Box::new(Node {
            data: node.data.clone(),
            next: None,
        });
        
        // Preconditions: 
        // - new_node owns the new node
        // - indirect points to the last next pointer of the list
 
        *indirect = Some(new_node);
        let tmp: &mut Node<T> = indirect.as_mut().unwrap();
        indirect = &mut tmp.next;

        // Doesn't work because new_node is moved out of
        //*indirect = Some(new_node);
        //indirect = &mut new_node.next;
        
        // Postconditions:
        // - new_node has been moved from
        // - indirect points to what was the address of new_node.next

        current = &node.next;
    }

    new_list
}

However, I noticed I couldn't get rid of the .unwrap() no matter what I did. I can't refer to new_node.next, even though it's the right type, due to having moved out of it, and so that leaves using indirect, even though it's a &mut Option<Box<Node<T>>>, using .unwrap() because it's known to refer to a Some(p) at that point. I feel like there could maybe be a way to do this all in one go, and I'm just not familiar enough with Rust's standard library.

Is that the case? Or is this just something you can't do? That's really my main question, I guess.

I have this saved on the Rust Playground, with the copy_list function being all the way at the bottom.

I guess you could also just rewrite the function and do something like:

impl<T: Clone> Clone for List<T> {
    fn clone(&self) -> Self {
        let mut list = List::<T>::new();
        for n in self.iter() {
            list.push(n.clone());
        }
        list.reverse();
        list
    }
}

Completely sidestepping the need for a pointer to a pointer. I did the same thing to implement the .reverse() method when I couldn't figure out a way to get the three-pointer loop you'd write in another language to work with the borrow checker, instead just making another list and moving each node into it, then moving the list into *self at the end, which works just as well.

2

Short version, you can use Option::insert to do the assign and unwrap without the additional possible cost.

1 Like
3

Oh, I see, like this:

let tmp = indirect.insert(new_node);
indirect = &mut tmp.next;

Or in just one line:

indirect = &mut indirect.insert(new_node).next;

Thanks for directing me to that method! I guess my question is answered, then.

1 Like
4

This is tangential, but I also got the three-pointer reversal function to work, just for future reference I guess. The problem was that I had to do std::mem::replace explicitly rather than call p.next.replace(prev) in this case. Actually, you don't need even three pointers here (just a cur and a prev rather than a cur and a prev and a next).

fn reverse_list<T>(head: Option<Box<Node<T>>>) -> Option<Box<Node<T>>> {
    let mut prev = None;
    let mut cur = head;
    while let Some(mut p) = cur {
        cur = std::mem::replace(&mut p.next, prev);
        prev = Some(p);
    }
    prev
}

impl<T> List<T> {
    // functions...
    pub fn reverse(&mut self) {
        self.head = reverse_list(self.head.take());
    }
    // more functions...
}