在Rust中更改树中的节点

Question

我正在尝试编写一个函数，给定一个树结构，返回该树的副本但在特定索引处更改了一个节点。以下是我的代码：

#[derive(Clone)]
pub enum Node {
    Value(u32),
    Branch(u32, Box<Node>, Box<Node>),
}

fn main() {
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3)));
    zero_node(&root, 2);
}

pub fn zero_node (tree: &Node, node_index: u8) -> Node {

    let mut new_tree = tree.clone();

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 {
        if (node_index == node_count) {
            match node {
                &mut Node::Value(_) => { *node = Node::Value(0); },
                &mut Node::Branch(_, ref mut left, ref mut right) => { *node = Node::Branch(0, *left, *right);  }
            }
            node_count
        } else {
            match node {
                &mut Node::Value(val) => {1},
                &mut Node::Branch(_, ref mut left, ref mut right) => {
                    let count_left = zero_rec(&**left, node_count + 1, node_index);
                    let count_right = zero_rec(&**right, node_count + 1 + count_left, node_index);
                    count_left + count_right + 1
                }
            }
        }
    }

    zero_rec(&new_tree, 0, node_index);

    new_tree

}

http://is.gd/YdIm0g

我似乎无法摆脱 "cannot borrow immutable borrowed content as mutable" 和 "cannot move out of borrowed content" 这样的错误。

我可以从原始数据开始创建新的树，并在过程中修改一个节点。但是我想了解如何通过borrow checker来解决这个问题。

- Jackson Pauls

Answer 1

这段代码可以编译：

#[derive(Clone)]
pub enum Node {
    Value(u32),
    Branch(u32, Box<Node>, Box<Node>),
}

fn main() {
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3)));
    zero_node(&root, 2);
}

pub fn zero_node (tree: &Node, node_index: u8) -> Node {

    let mut new_tree = tree.clone();

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 {
        if node_index == node_count {
            match node {
                &mut Node::Value(ref mut val) => { *val = 0; },
                &mut Node::Branch(ref mut val, _, _) => { *val = 0; }
            }
            node_count
        } else {
            match node {
                &mut Node::Value(_) => {1},
                &mut Node::Branch(_, ref mut left, ref mut right) => {
                    let count_left = zero_rec(&mut **left, node_count + 1, node_index);
                    let count_right = zero_rec(&mut **right, node_count + 1 + count_left, node_index);
                    count_left + count_right + 1
                }
            }
        }
    }

    zero_rec(&mut new_tree, 0, node_index);

    new_tree

}

我所做的更改包括：

• &new_tree → &mut new_tree 和 &**left → &mut **left 等等：创建一个可变引用的方式是使用&mut运算符（即必须使用mut）。通过传递可变引用而不是不可变引用，可以解决“无法将不可变借用内容作为可变”错误。
• 将node_index == node_count分支更改为直接修改值，而不是尝试原地覆盖。这通过根本没有进行任何移动来解决“无法移动租借内容”的错误。

实际上，可以通过精心使用std::mem::replace来进行覆盖，以交换新值（例如，使用Value(0)，因为它很便宜）到left和right引用中。 replace函数返回之前存在的值，即你需要创建新分支的left和right中的内容。下面是对相关match分支的修改：

&mut Node::Branch(_, ref mut left, ref mut right) => { 
    let l = mem::replace(left, Box::new(Node::Value(0)));
    let r = mem::replace(right, Box::new(Node::Value(0)));
    *node = Node::Branch(0, l , r); 
}

(在文件顶部添加use std::mem;后。)

但是它遇到了一个新的错误：

<anon>:25:9: 25:39 error: cannot assign to `*node` because it is borrowed
<anon>:25                   *node = Node::Branch(0, l , r); 
                            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<anon>:22:26: 22:38 note: borrow of `*node` occurs here
<anon>:22               &mut Node::Branch(_, ref mut left, ref mut right) => { 
                                             ^~~~~~~~~~~~

left和right的值是指向node旧内容的指针，因此对于编译器来说（目前），覆盖node将使这些指针失效，并导致使用它们的任何进一步代码都被破坏（当然，我们可以看到它们都不再被使用，但编译器还没有注意到这样的事情）。幸运的是，有一个简单的解决方案：两个match分支都将node设置为一个新值，所以我们可以使用match计算出新值，然后在执行计算后将node设置为该新值：

*node = match node {
    &mut Node::Value(_) => Node::Value(0),
    &mut Node::Branch(_, ref mut left, ref mut right) => { 
        let l = mem::replace(left, Box::new(Node::Value(0)));
        let r = mem::replace(right, Box::new(Node::Value(0)));
        Node::Branch(0, l , r)
    }
};

(注意，操作顺序有点奇怪，与let new_val = match node {...}; *node = new_val;相同。)

然而，这比我上面写的方式更昂贵，因为它必须为新的Branch分配2个新的盒子，而原地修改的那个不必这样做。

---

稍微“更好”的版本可能是（注释内联）：

#[derive(Clone, Show)]
pub enum Node {
    Value(u32),
    Branch(u32, Box<Node>, Box<Node>),
}

fn main() {
    let root = Node::Branch(1, Box::new(Node::Value(2)), Box::new(Node::Value(3)));
    let root = zero_node(root, 2);

    println!("{:?}", root);
}

// Taking `tree` by value (i.e. not by reference, &) possibly saves on
// `clone`s: the user of `zero_node can transfer ownership (with no
// deep cloning) if they no longer need their tree.
//
// Alternatively, it is more flexible for the caller if it takes 
// `&mut Node` and returns () as it avoids them having to be careful 
// to avoid moving out of borrowed data.
pub fn zero_node (mut tree: Node, node_index: u8) -> Node {

    fn zero_rec (node : &mut Node, node_count : u8, node_index : u8) -> u8 {
        if node_index == node_count {
            // dereferencing once avoids having to repeat &mut a lot
            match *node {
                // it is legal to match on multiple patterns, if they bind the same
                // names with the same types
                Node::Value(ref mut val) | 
                    Node::Branch(ref mut val, _, _) => { *val = 0; },
            }
            node_count
        } else {
            match *node {
                Node::Value(_) => 1,
                Node::Branch(_, ref mut left, ref mut right) => {
                    let count_left = zero_rec(&mut **left, node_count + 1, node_index);
                    let count_right = zero_rec(&mut **right, node_count + 1 + count_left, node_index);
                    count_left + count_right + 1
                }
            }
        }
    }

    zero_rec(&mut tree, 0, node_index);

    tree

}

- huon