ржавый ящик с эго-деревом: циклы с изменяемыми заимствованиями внутри рекурсии

Question

Я использую версию 0.6.0 ящика с эго-деревом, и я не уверен, как пройти через изменяемые узлы. Ниже приведен надуманный пример, но он иллюстрирует мои намерения. Операция append(&mut self) может рассматриваться как простой заполнитель для любой другой функции, которая также требует изменяемой ссылки.

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

Я понимаю, что компилятор говорит мне, что изменяемая ссылка не может использоваться после ее использования (после> = 2-й итерации), но я не знаю, какой шаблон использовать вместо нее.

Я получаю ошибку:

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

Код для воспроизведения ошибки:

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

Answer 1

Вы можете сделать это, используя стек:

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

С:

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

Будет выведено:

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" } }