rust - 在 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

我似乎无法摆脱错误，例如:“无法将不可变的借用内容借用为可变的”和“无法移出借用的内容”。

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

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 函数返回之前存在的值，即 left 和 right 中您需要创建新分支的内容。对相关 match arm 的更改看起来有点像:

&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 个新的盒子，而修改的那个-place 不必这样做。

---

稍微“更好”的版本可能是(内联评论):

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

}