How to consume and replace a value in an &mut ref

Question

This question already has answers here:

How can I swap in a new value for a field in a mutable reference to a structure? (2 answers)

Closed 2 years ago.

Sometimes I run into a problem where, due to implementation details that should be invisible to the user, I need to "destroy" a &mut and replace it in-memory. This typically ends up happening in recursive methods or IntoIterator implementations on recursive structures. It typically follows the form of:

fn create_something(self);

pub fn do_something(&mut self) {
    // What you want to do
    *self = self.create_something();
}

One example that I happened to have in my current project is in a KD Tree I've written, when I "remove" a node, instead of doing logic to rearrange the children, I just destructure the node I need to remove and rebuild it from the values in its subtrees:

// Some recursive checks to identify is this is our node above this

if let Node{point, left, right} = mem::replace(self, Sentinel) {
    let points = left.into_iter().chain(right.into_iter()).collect();
    (*self) = KDNode::new(points);

    Some(point)
} else {
    None
}

Another more in-depth example is the IntoIterator for this KDTree, which has to move a curr value out of the iterator, test it, and then replace it:

// temporarily swap self.curr with a dummy value so we can
// move out of it
let tmp = mem::replace(&mut self.curr, (Sentinel,Left));

match tmp {
    // If the next node is a Sentinel, that means the
    // "real" next node was either the parent, or we're done
    (Sentinel,_) => {
        if self.stack.is_empty() {
            None
        } else {
            self.curr = self.stack.pop().expect("Could not pop iterator parent stack");
            self.next()
        }
    }
    // If the next node is to yield the current node,
    // then the next node is it's right child's leftmost
    // descendent. We only "load" the right child, and lazily
    // evaluate to its left child next iteration.
    (Node{box right,point,..},Me) => {
        self.curr = (right,Left);

        Some(point)
    },
    // Left is an instruction to lazily find this node's left-most
    // non-sentinel child, so we recurse down, pushing the parents on the
    // stack as we go, and then say that our next node is our right child.
    // If this child doesn't exist, then it will be taken care of by the Sentinel
    // case next call.
    (curr @ Node{..},Left) => {
        let mut curr = curr;
        let mut left = get_left(&mut curr);

        while !left.is_sentinel() {
            self.stack.push((curr,Me));
            curr = left;
            left = get_left(&mut curr);
        }

        let (right,point) = get_right_point(curr);
        self.curr = (right, Left);
        Some(point)
    }

As you can see, my current method is to just use mem::replace with a dummy value, and then just overwrite the dummy value later. However, I don't like this for several reasons:

• In some cases, there's no suitable dummy value. This is especially true if there's no public/easy way to construct a "zero value" for one or more of your struct members (e.g. what if the struct held a MutexGuard?). If the member you need to dummy-replace is in another module (or crate), you may be bound by difficult constraints of its construction that are undesireable when trying to build a dummy type.
• The struct may be rather large, in which case doing more moves than is necessary may be undesirable (in practice, this is unlikely to be a big problem, admittedly).
• It just "feels" unclean, since the "move" is technically more of an "update". In fact, the simplest example might be something like *self = self.next.do_something() which will still have problems.

In some cases, such as that first remove snippet I showed, you could perhaps more cleanly represent it as a fn do_something(self) -> Self, but in other cases such as the IntoIterator example this can't be done because you're constrained by the trait definition.

Is there any better, cleaner way to do this sort of in-place update?

Answer 1

In any case we'll need assignment, mem::replace, mem::swap, or something like that. Because given a &mut reference to an object there is no way to move this object (or any of it's fields) out without replacing it's memory area with something valid, as long as Rust forbids references to uninitialized memory.

As for dummy values for replacement, you can always make them yourself for any type by using some wrapper type. For example, I often use Option for this purpose, where Some(T) is the value of type T, and None acts as dummy. This is what I mean:

struct Tree<T>(Option<Node<T>>);
enum Node<T> {
    Leaf(T),
    Children(Vec<Tree<T>>),
}

impl<T> Tree<T> where T: PartialEq {
    fn remove(&mut self, value: &T) {
        match self.0.take() {
            Some(Node::Leaf(ref leaf_value)) if leaf_value == value =>
                (),
            node @ Some(Node::Leaf(..)) =>
                *self = Tree(node),
            Some(Node::Children(node_children)) => {
                let children: Vec<_> =
                    node_children
                        .into_iter()
                        .filter_map(|mut tree| { tree.remove(value); tree.0 })
                        .map(|node| Tree(Some(node)))
                        .collect();
                if !children.is_empty() {
                    *self = Tree(Some(Node::Children(children)));
                }
            },
            None =>
                panic!("something went wrong"),
        }
    }
}

playground link