Средство проверки заимствований не позволяет возвращать изменяемую ссылку из функции обхода дерева

Мне нужно найти узел с максимальным значением в дереве, предполагая, что значения подузла всегда больше, чем значение узла-владельца, а затем изменить его:

#[derive(Debug)]
struct Node {
    val: usize,
    nodes: Vec<Node>,
}

fn find_max(node: &mut Node, val: usize) -> Option<&mut Node> {
    if node.val < val {
        return None;
    }
    let mut max_val = node.val;
    let mut max: Option<&mut Node> = Some(node);
    for n in &mut node.nodes {
        if let Some(m) = find_max(n, max_val) {
            max_val = m.val;
            max = Some(m);
        }
    }
    max
}

fn main() {
    let mut root = Node {
        val: 1,
        nodes: vec![
            Node {
                val: 2,
                nodes: vec![],
            },
            Node {
                val: 3,
                nodes: vec![
                    Node {
                        val: 4,
                        nodes: vec![],
                    },
                ],
            },
        ],
    };
    println!("{:?}", find_max(&mut root, 0));
}

Средство проверки заимствований возвращает эту ошибку:

error[E0499]: cannot borrow `node.nodes` as mutable more than once at a time
  --> src/main.rs:13:19
   |
12 |     let mut max: Option<&mut Node> = Some(node);
   |                                           ---- first mutable borrow occurs here
13 |     for n in &mut node.nodes {
   |                   ^^^^^^^^^^ second mutable borrow occurs here
...
20 | }
   | - first borrow ends here

Если я удалю mut из find_max, это сработает, но я не понимаю, как мне вернуть изменяемую ссылку из find_max.

Важно то, что сам find_max ничего не меняет. Он просто ищет подходящий узел.


rust borrow-checker borrowing
person Michael Ilyin    schedule 24.10.2017    source источник
comment
Возможный дубликат Получение изменяемой ссылки путем повторения рекурсивной структуры   -  person Jimmy    schedule 24.10.2017
comment
Другой похожий вопрос, который может дать вам необходимое понимание: stackoverflow.com/questions/29711348/   -  person Jimmy    schedule 24.10.2017
comment
@JimmyCuadra, нет, оба эти случая здесь не применимы. Мы не можем переместить node, потому что в некоторых случаях нам нужно его вернуть. И мы не можем использовать индексы, потому что существует несколько векторов.   -  person red75prime    schedule 24.10.2017
comment
Я почти уверен, что в вашем коде тоже есть логическая ошибка: вы не можете прервать работу на раннем этапе на узле, чтобы найти максимум, если дочерние узлы имеют большие значения! Если значения становятся меньше в дочерних узлах, ваш подход в порядке (но это не то, что вы сказали).   -  person Stefan    schedule 24.10.2017

Ответы (3)


arrow_upward
4
arrow_downward

Необязательно использовать unsafe:

fn find_max(node: &mut Node, val: usize) -> Option<&mut Node> {
    if node.val < val {
        return None;
    }

    if node.nodes.is_empty() {
        return Some(node);
    }

    let mut max_val = node.val;
    let mut max = None;
    for n in &mut node.nodes {
        if let Some(m) = find_max(n, max_val) {
            max_val = m.val;
            max = Some(m);
        }
    }
    max
}
person Shepmaster    schedule 24.10.2017

arrow_upward
0
arrow_downward

Кажется, это один из редких случаев, когда unsafe оправдано.

Обычный подход в таких случаях - заменить изменяемую ссылку неизменной ссылкой и использовать внутреннюю изменчивость. Но в этом случае нам нужно borrow() RefCell рекурсивно и каким-то образом поддерживать их в рабочем состоянии даже после возврата из функции.

Принимая во внимание, что проблема вызвана не внутренней небезопасностью операции, а ограничением средства проверки заимствований Rust, имеет смысл использовать unsafe. Имейте в виду, что, хотя я достаточно уверен, что следующий код безопасен, лучше дождаться комментариев или другого решения.

fn find_max(node: &mut Node, val: usize) -> Option<&mut Node> {
    if node.val < val {
        return None;
    }
    let mut max = None;
    let mut max_val = node.val;
    // keep reference around as a pointer
    let node_ptr = node as *mut Node;
    // `{ node }` moves the reference instead of reborrowing it
    // so we can recreate it later with no risk of undefined behavior
    for n in &mut { node }.nodes {
        if let Some(m) = find_max(n, max_val) {
            max_val = m.val;
            max = Some(m);
        }
    }
    max.or_else(
        // the closure is executed only when `max == None`
        // and `node` was moved out earlier in `{node}`
        // therefore there's no active mutable references reachable thru recreated reference
        // function signature ensures that lifetime of the returned reference is ok
        // thus we can safely recreate the same mutable reference we received in `node`
        || unsafe { node_ptr.as_mut() }
    )
}
person red75prime    schedule 24.10.2017

arrow_upward
-2
arrow_downward

U может использовать * вместо & mut для deref. Но [Node] не имеет постоянного размера, известного во время компиляции

person user8805531    schedule 24.10.2017
comment
Похоже, у вашего сообщения есть проблемы с форматированием. Пожалуйста, посмотрите и при необходимости отредактируйте. - person Mathieu VIALES; 24.10.2017