Изменение узла в дереве в 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 рука выглядит как:

&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)
    }
};

(NB. Порядок операций немного странный, это так же, как let new_val = match node { ... }; *node = new_val;.)

Однако это дороже, чем делать, как я писал выше, поскольку для нового нужно выделить 2 новых поля. Branchв то время как тот, который изменяет на месте, не должен делать это.

---

Немного "более приятная" версия может быть (встроенные комментарии):

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

}