rust ego-tree crate: loops with mutable borrows inside a recursion

Question

I am using version 0.6.0 of the ego-tree crate, and I am not sure how to traverse mutable nodes. The following is a contrived example, but it illustrates my intent. The append(&mut self) operation may be seen as an easy placeholder for any other function which also takes a mutable reference.

The basic problem is that I do not understand how to conceptually traverse the sibling nodes given the mutable reference that is consumed each time a new sibling is requested.

I understand that the compiler is telling me that the mutable reference cannot be used after it is consumed (upon the >= 2nd iteration), but I do not know what pattern to use instead.

The error I receive is:

error[E0597]: `sibling` does not live long enough
  --> src/main.rs:15:35
   |
12 |             while !sibling_mut.is_none() {
   |                    ----------- borrow used here, in later iteration of loop
...
15 |                     sibling_mut = sibling.next_sibling();
   |                                   ^^^^^^^ borrowed value does not live long enough
16 |                 }
   |                 - `sibling` dropped here while still borrowed

The code to reproduce the error:

use ego_tree::{tree, NodeMut, Tree};

/// Traverse the tree and insert a sibling after the node specified by `data`
fn traverse(node: &mut Option<NodeMut<String>>) {
    match node {
        None => {
            println!("done traversing a level");
            return;
        }
        Some(n) => {
            let mut sibling_mut = n.next_sibling();
            while !sibling_mut.is_none() {
                if let Some(mut sibling) = sibling_mut {
                    sibling.append("x".into());
                    sibling_mut = sibling.next_sibling();
                }
            }
            traverse(&mut None);
        }
    }
}

fn main() {
    let mut tree = build_simple_tree();
    traverse(&mut Some(tree.root_mut()));
}

fn build_simple_tree() -> Tree<String> {
    tree! {
        "a".into() => {
            "b".into(),
            "c".into(),
            "d".into(),
        }
    }
}

My quick idea is that you cannot do this because ego-tree has (for some reason) tied the lifetime of the return value of next_sibling to the preceding node. Once that node goes out of scope (such as when you overwrite it in the loop), any references become invalid. In my XML crate, I avoid this by having nodes maintain references to the document value, not other nodes. — Shepmaster

Stargateur Stargateur · Accepted Answer · 2019-05-23T01:09:45

You could do this by using the stack:

/// Traverse the tree and insert a sibling after the node specified by `data`
fn traverse(node: Option<NodeMut<String>>) {
    match node {
        None => {
            println!("done traversing a level");
            return;
        }
        Some(mut n) => {
            traverse(n.first_child());
            n.append("x".into());
            traverse(n.next_sibling());
        }
    }
}

With:

fn main() {
    let mut tree = build_simple_tree();
    println!("{:#?}", tree);
    traverse(Some(tree.root_mut()));
    println!("{:#?}", tree);
}

This will output:

Tree { "a" => { "b", "c", "d" } }
done traversing a level
done traversing a level
done traversing a level
done traversing a level
done traversing a level
Tree { "a" => { "b" => { "x" }, "c" => { "x" }, "d" => { "x" }, "x" } }

rust ego-tree crate: loops with mutable borrows inside a recursion

1 Answers