Iterative tree parsing in Rust

Question

Suppose we have a tree:

#[derive(Default, Debug, PartialEq, Eq)]
struct Tree {
    children: Vec<Tree>,
}

And we want to build it from a list of bools where true is like an open tag and false is like a close tag in XML. I.e. [true, true, false, true, false, false] is

root -> node -> node
            `-> node

We can easily parse this recursively like this:

fn read_tree_recursive<'a>(tags: &mut impl Iterator<Item=&'a bool>) -> Tree {
    let mut tree = Tree::default();
    while let Some(&tag) = tags.next() {
        if tag {
            tree.children.push(read_tree_recursive(tags));
        } else {
            break;
        }
    }
    tree
}

Here is some test code:

fn main() {
    assert_eq!(
        read_tree_recursive(&mut [true, true, false, true, false, false].iter()),
        Tree {
            children: vec![
                Tree {
                    children: vec![
                        Tree::default(),
                        Tree::default(),
                    ],
                }
            ],
        },
    );
}

But how do you do this iteratively? In any other language you'd make a stack of pointers on the heap something like this:

fn read_tree_iterative(tags: &[bool]) -> Tree {
    let mut root = Tree::default();
    let tree_stack: Vec<&mut Tree> = vec![&mut root];

    for &tag in tags {
        if tag {
            tree_stack.last().unwrap().children.push(Tree::default());
            tree_stack.push(tree_stack.last().unwrap().children.last_mut().unwrap());
        } else {
            tree_stack.pop();
        }
    }
    root
}

Unfortunately this doesn't work in Rust because Rust can't know that we're only ever mutating tree_stack.last(). The recursive version uses function calls to enforce that, but obviously it has the downsides that come with recursion.

Is there a good way around this other than resorting to RefCell? Unfortunately Rust doesn't have become so TCO isn't a good option either.

Answer 1

You can simply store owned values in your stack and add them to the children when you pop them from the stack:

fn read_tree_iterative<'a> (tags: &mut impl Iterator<Item=&'a bool>) -> Tree {
    let mut stack = Vec::new();
    let mut last = Tree::default();
    
    for &tag in tags {
        if tag {
            stack.push (last);
            last = Tree::default();
        } else {
            let mut parent = stack.pop().unwrap();
            parent.children.push (last);
            last = parent;
        }
    }
    last
}

Playground