How can I change a reference to an owned value without clone?

user_4418836 0
Viewed 6986

I'm practicing Rust concepts that I've learned while reading The Book. I've been able to iterate over my List enum by copying the Box and assigning the list to the copied box, but intuitively, I feel like there must be a way to just "make it point to the next pointer in line".

If I attempt to do this without bx.clone(), like so: self.list = **bx, I get "cannot move out of **bx which is behind a mutable reference." Which means that I need it to be owned, but I can't get an owned bx because I need to move it as a reference when I dereference it in the if let.

Is it possible or advisable to move the reference without copying it?

#[derive(Clone)]
enum List {
    Cons(u32, Box<List>),
    Nil,
}
struct ListHolder {
    list: List,
}

impl Iterator for ListHolder {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        if let Cons(num, bx) = &mut self.list {
            let val = *num;
            self.list = *bx.clone(); // This is the key line
            Some(val)
        } else {
            None
        }
    }
}

use List::*;

fn main() {
    let list_inst = ListHolder {
        list: Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil)))))),
    };
    for i in list_inst.into_iter() {
        println!("{}", i); // Prints 1, 2, 3 as expected
    }
}
rust
1 Answers

I think the key issue with your mental model is that you're thinking of Box<T> as simply a pointer. Rust references (and most smart pointers like Box<T>) are not merely pointers, but valid pointers. That is, there are no null references and references must always point to valid data at all times.

When we try to do self.list = **bx;, we're moving the data from bx to self.list. However, bx doesn't own its data. When the mutable borrow bx ends, the actual owner is going to be holding invalid data.

So what do we do? The simplest way is what's sometimes called Jones' Trick where we switch out the data in bx for some dummy value. Now the actual owner of the data in bx won't be holding invalid data. So how do we do this? This is the purview of the function std::mem::replace which takes a mutable reference and a value and replaces the data behind the mutable reference with that value, returning what was behind the mutable reference before (including ownership!). That's exactly what we want to do here with self.list = std::mem::replace(&mut **bx, List::Nil). Again, List::Nil is just some dummy data; any List at all would work exactly the same.

enum List {
    Cons(u32, Box<List>),
    Nil,
}
struct ListHolder {
    list: List,
}

impl Iterator for ListHolder {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        if let Cons(num, bx) = &mut self.list {
            let val = *num;
            self.list = std::mem::replace(&mut **bx, List::Nil); // This is the key line
            Some(val)
        } else {
            None
        }
    }
}

use List::*;

fn main() {
    let list_inst = ListHolder {
        list: Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil)))))),
    };
    for i in list_inst.into_iter() {
        println!("{}", i); // Prints 1, 2, 3 as expected
    }
}

(playground)

To be slightly more idiomatic, instead of &mut **bx, we could simply use bx.as_mut() to get a mutable reference from the box. Also, the into_iter call on list_inst is unnecessary since ListHolder already implements Iterator so it doesn't need to be turned into one. You may also be wondering about num and val and why we still have to make a temporary variable for that.

The reason is that this value is still just a reference and we don't have owned access to the owner (self.list). That means we have to make a copy of it to return. u32 implements Copy so this isn't really a problem, but if you tried to make the linked list generic in the type of its elements, it simply wouldn't work. let val = *num; is the same kind of "moving out of borrowed content" that we couldn't do before.

The solution is to use std::mem::replace to get ownership not just of the data behind bx, but of the whole list. So if we use std::mem::replace(&mut self.list, List::Nil) before destructuring, self.list will be replaced with a dummy value and we'll have ownership of the actual list, including both the value and the tail of the list. This also means that we can just have self.list = *bx, as I'm sure you originally wanted.

impl Iterator for ListHolder {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        if let Cons(num, bx) = std::mem::replace(&mut self.list, List::Nil) {
            self.list = *bx;
            Some(num)
        } else {
            None
        }
    }
}

(playground)

The upshot is now you can make the list generic with hardly any effort.

If you want to learn more about how Rust's ownership model affects the implementation of linked lists, you can do no better than the excellent series Learn Rust With Entirely Too Many Linked Lists. The series covers everything here in detail as well as many variations.

user_46392730
Related