(syntax trees) recursively iterating over trees bottom-up with current top-down path

Question

Hi

I have an abstract syntax tree which I need to iterate. The AST is generated by the lemon port to PHP.

Now "normally", I'd do it with the brand new and shiny (PHP 5.3.1) SPL classes, and it would look like this:

$it = new \RecursiveIteratorIterator(
  new \RecursiveArrayIterator($ast['rule']),
  \RecursiveIteratorIterator::SELF_FIRST);

Actually, that's what I'm already doing in another part of the code which determinates a rough type of the entire tree (i.e it can be an assignment, a condition, etc). Now details aside, the only important thing is the iteration is done RecursiveIteratorIterator::SELF_FIRST, that is, top-down.

Going back to my problem, I need to iterate the AST bottom-up, that is, something like RecursiveIteratorIterator::CHILD_FIRST, in order to do some substitutions and optimizations in the tree.

The problem is, these operations need to be context-aware, i.e. I need the path down to the current node. And since I want to iterate bottom-up, I can't have that with RecursiveIteratorIterator.

Well think about it for a second. I want to iterate bottom-up and have the top-down context (a stack) of the current node, at each iteration. Technically it should be possible, since RecursiveIteratorIterator must first go to the tail of the tree, in order to iterate backwards. In its way to the tail, it could cache the current position, and simply pop out elements as it returns back from recursion.

Now this is a keyword: caching. This is why I suspect it should be possible with another SPL class: RecursiveCachingIterator.

The question is: is it really possible? If yes, how?

I've been trying to puzzle around with some code, without success, and the documentation is scarce. Really, really scarce.

Whoever finds the most elegant solution to this using SPL, hats off! You're a PHP guru!

PS: in case it's not clear, I'm looking for as much SPL (re)usage as possible. I know I could write my own recursive functions with a custom stack, no need to remember me about that.

Answer 1

I have managed to get it working by inheriting RecursiveIteratorIterator and managing the stack in ::endChildren() and ::callGetChildren respectively. Maybe this will help someone. Hats off to myself :-)