Processing Trees

[JahredLove]

Hey guys,

So, I'm running into a stack overflow issue (the literal one, not the helpful website variety). Essentially, I have a tree of data, similar to this;

#[derive(PartialEq, Debug, Clone)]
pub enum Tree {
    Leaf(String),
    Branch(vec<Tree>),
    Oasis {
        definitely: Tree,
        maybe: Option<Tree>,
    },
}

Now, I need to manipulate the values of this tree. To test this tree, I would do:

    #[test]
    fn test_modify() {
        let mut tests = vec![
            (Tree::Leaf("a"), Tree::Lead("b")),
            (
              Tree::Branch(vec![Tree::Leaf("a")]),
              Tree::Branch(vec![Tree::Leaf("b")]),
            ),
            (
                Tree::Oasis(
                    definitely: Tree::Branch(vec![Tree::Leaf("a")]),
                    maybe: Some(Tree::Branch(vec![Tree::Leaf("a")])),
                }),
                Tree::Oasis(
                    definitely: Tree::Branch(vec![Tree::Leaf("b")]),
                    maybe: Some(Tree::Branch(vec![Tree::Leaf("b")])),
                }),
            ),
        ];

        while !tests.is_empty() {
            let (input, expected) = tests.pop().unwrap();
            let modified = modify(input, Rc::new(RefCell::new(some_modifier_fun)));
            assert_eq!(modified, expected);
        }
    }

The modifier function might look like this:

pub fn modify<P: FnMut(Tree) -> Tree>(node: Tree, modifier: Rc<RefCell<P>>) -> Option<Tree> {
    match node {
        Tree::Branch(mut node) => {
            for i in 0..node.len() {
                let branch_node = node.swap_remove(i);
                if let Some(tree) = modify(branch_node, Rc::clone(&modifier)) {
                    node.insert(i, tree)
                }
            }
            Some((&mut *modifier.borrow_mut())(Tree::Branch(node)))
        }
        Tree::Leaf(node) => {
            if let Some(leaf_node) = modify(node, Rc::clone(&modifier)) {
                Some((&mut *modifier.borrow_mut())(Tree::Leaf(leaf_node)))
            } else {
                None
            }
        }
        Tree::Oasis {
            definitely,
            maybe,
        } => {
            if let Some(def) = modify(definitely, Rc::clone(&modifier)) {
                if maybe.is_some() {
                    if let Some(mb) = modify(maybe.unwrap(), Rc::clone(&modifier)) {
                        Some((&mut *modifier.borrow_mut())(Tree::Oasis {
                               definitely: def,
                               maybe: Some(mb),
                        }))
                   } else {
                        None
                   }
               } else {
                   Some((&mut *modifier.borrow_mut())(Tree::Oasis {
                       definitely: def,
                       maybe: None,
                    }))
                } else {
                    None
                }
            } else {
                None
            }
        }
        _ => Some((&mut *modifier.borrow_mut())(node)),
    }
}

(Please excuse any mistakes. This is freehand)

The problem, here, is that, since the modify function is recursively called to process the tree, I quite quickly hit a stack overflow problem. My question, therefore, is how do I best process a tree such as this?

Many thanks,
JRod