在 Rust 中更改树中的节点

Question

我正在尝试编写一个函数，给定一个树结构，returns 该树的一个副本，但节点在特定索引处发生了更改。这是我目前所拥有的：

#[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"。

我可以在原始树的基础上从头开始创建新树，并在此过程中更改一个节点。但我想了解如何在与借用检查器的战斗中获胜。

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 T 引用的方法是使用 &mut运算符（即 mut 是必需的）。这通过传递可变引用而不是不可变引用来修复 cannot borrow immutable borrowed content as mutable 错误
更改 node_index == node_count 分支以直接改变值，而不是尝试就地覆盖。这通过根本不做任何移动来修复 cannot move out of borrowed content 错误。

覆盖实际上可以通过仔细使用 std::mem::replace 来实现，将新值（例如 Value(0) 换成 left 和 right 参考文献。 replace 函数 returns 以前存在的值，即正是 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 个新盒子，而那个就地修改不必这样做。

稍微 "nicer" 的版本可能是（内联评论）：

#[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

}

在 Rust 中更改树中的节点

Changing a node in a tree in Rust

rust

borrow-checker