Flattening a nested structure

Question

Looks for wisdom on fixing this borrow-checker/lifetime issue in Rust. I'm trying to flatten a generic nested structure (into an impl Iterator or Vec). It's perhaps a few &s and `s away from working:

fn iter_els(prev_result: Vec<&El>) -> Vec<&El> {
    // Iterate over all elements from a tree, starting at the top-level element.
    let mut result = prev_result.clone();

    for el in prev_result {
        for child in &el.children {
            result.push(&child.clone());
        }
        result.extend(iter_els(&el.children));
    }
    result
}

You'll note that the immediate exception this raises is that iter_els expects a Vec of refs, not a ref itself. When addressing this directly, other issues rear their mischievous heads, as in a game of oxidized, but safe wack-a-mole.

Playground

phimuemue phimuemue · Accepted Answer · 2018-11-25T13:39:51

There are various solutions to this task. One would be to pass the result as an out-parameter to the function:

fn iter_els<'el>(el_top: &'el El, result: &mut Vec<&'el El>) {
    result.push(el_top);
    for el in &el_top.children {
        iter_els(el, result);
    }
}

fn main() {
    // build top_el as you did
    let mut result = Vec::new();
    iter_els(&top_el, &mut result);
    println!("{:?}", result);
}

Adapting your original approach imho results in a more complex implementation:

fn iter_els<'el>(prev_result: &Vec<&'el El>) -> Vec<&'el El> {
    // Iterate over all elements from a tree, starting at the top-level element.
    let mut result = prev_result.clone();

    for el in prev_result {
        for child in &el.children {
            result.push(&child);
        }
        result.extend(iter_els(&el.children.iter().collect()));
    }
    result
}

fn main() {
    // build top_el as you did
    println!("{:?}", iter_els(&vec![&top_el]));
}

Alternatively:

fn iter_els<'el>(prev_result: &'el Vec<El>) -> Vec<&'el El> {
    // Iterate over all elements from a tree, starting at the top-level element.
    let mut result : Vec<_> = prev_result.iter().collect();

    for el in prev_result {
        for child in &el.children {
            result.push(child);
        }
        result.extend(iter_els(&el.children));
    }
    result
}

fn main() {
    // build top_el as you did
    println!("{:?}", iter_els(&vec![top_el]));
}

As you can see, the first approach only operates on an immutable El, and one single result Vec, while the other implementations do not get around clone and collect.

Ideally, you would write a custom Iterator for your tree, but I think this could get quite cumbersome, because this iterator would have to keep track of the current state somehow (maybe can prove me wrong and show that it's actually easy to do).

Flattening a nested structure

1 Answers