CODEWITHSUNDEEP
rust
Slugger
Slugger

Reputation: 675

Moving something that is in scope of a reference when those references will go out of scope immediately after the move

I am learning Rust coming from a C++ background. I am writing a parser that reads valid formulas such as 12 x (y - 4) and puts them in an abstract syntax tree (AST). I use an enum to store the possible nodes in the AST as you can see in the (heavily simplified) code. I ran into a problem. I want to simplify the expression -(-(12)) for instance by moving the 12, not copying. In general the 12 may be replaced by a deep AST. Currently I identify the situation in the function simplify( .. ) but it wont compile.

I do know why it doesn't compile: The node I'm trying to move (i.e. the 12 in my example) is still in scope as a reference from in the match clause so this is exactly rust preventing me from a possible problem with references. But in my case I know this is what I want, and moreover I exit the function right after I do the moving in the line *node = **child;, so the earlier references will go out of scope right there.

Is there an idiomatic Rust-esque type of way to solve this problem? I would really rather not copy the double--negated subtree.

#[derive(Debug)]
enum Node {
    Num(i32),
    UnaryMinus(Box<Node>),
}

use Node::*;

fn simplify(node: &mut Node) {
    match &node {
        Num(_) => (),
        UnaryMinus(inner) => match &**inner {
            Num(_) => (),
            UnaryMinus(child) => {
                // cannot move out of `**child` which is behind a shared reference
                *node = **child;
                return;
            }
        },
    }
}

fn main() {
    let double_minus = UnaryMinus(Box::new(UnaryMinus(Box::new(Num(12)))));
}

Upvotes: 1

Views: 134

Answers (1)

isaactfa
isaactfa

Reputation: 6651

There are two problems here: The error you're getting concretely is because you're matching against &**inner instead of &mut **inner. It's never okay to move out of a shared reference, but there are circumstances (which we'll see) when it's okay to move out of a mutable one.

With that fixed, you will get the same error just about mutable references. That's because you can't move out of a mutable reference just because you know you're the only one holding it. A move leaves its source uninitialized, and a reference, mutable or shared, to uninitialized memory is never okay. You'll have to leave something in that memory that you're moving out of. You can do that with std::mem::swap. It takes two mutable references and swaps out the contents.

Now, one could obviously try to call std::mem::swap(node, &mut child) but this won't work simply because node is already mutably borrowed in the match expression and you can't mutably borrow something twice.

Moreover, this would leak memory as you now have a reference cycle where node -> inner -> node. This, although perfectly valid to do in Rust, usually isn't what you want.

Instead you'll need some sort of dummy that you can put in child's place. Some simple variant of your enum that can be safely dropped by inner once it gets dropped. In this example that could be Node::Num(0):

#[derive(Debug)]
enum Node {
    Num(i32),
    UnaryMinus(Box<Node>),
}

// This is just to verify that everything gets dropped properly
// and we don't leak any memory
impl Drop for Node {
    fn drop(&mut self) {
        println!("dropping {:?}", self);
    }
}

use Node::*;

fn simplify(node: &mut Node) {
    // `placeholder` will be our dummy
    let (mut can_simplify, mut placeholder) = (false, Num(0));
    match node {
        Num(_) => (),
        // we'll need to borrow `child` mutably later, so we have to
        // match on `&mut **inner` not `&**inner`
        UnaryMinus(inner) => match &mut **inner {
            Num(_) => (),
            UnaryMinus(ref mut child) => {
                // move the contents of `child` into `placeholder` and vice versa
                std::mem::swap(&mut placeholder, child);
                can_simplify = true;
            }
        },
    }
    if can_simplify {
        // now we can safely move into `node`
        *node = placeholder;
        // you could skip the conditional if all other, non-simplifying
        // branches return before this statement
    }
}

fn main() {
    let mut double_minus = UnaryMinus(Box::new(UnaryMinus(Box::new(Num(12)))));
    simplify(&mut double_minus);
    println!("{:?}", double_minus);
}

Upvotes: 2

Related Questions