Borrow checker doesn't allow returning a mutable reference from tree traversal function

Question

I need to find the node with maximal value in tree, assuming that subnode's values are always larger than value of owning node, and then modify it:

#[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));
}

The borrow checker returns this error:

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

If I remove mut from find_max, it works, but I don't see how can I return a mutable reference from find_max.

The important thing is that find_max itself doesn't modify anything. It just searches for an appropriate node.

Answer 1

It is not required to use 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
}

Answer 2

It seems to be one of rare cases when unsafe is justified.

The usual approach in such cases is to replace mutable reference with immutable reference and use interior mutability. But in this case we need to borrow() RefCells recursively and somehow keep them alive even after function returns.

Taking into account that the problem is caused not by inherent unsafety of the operation, but by a limitation of Rust's borrow checker, it makes sense to use unsafe. Keep in mind that while I reasonably sure that the following code is safe, it's better to wait for comments or another solution.

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() }
    )
}

Answer 3

U can use * instead &mut to deref .but [Node] does not have a constant size known at compile-time