Hi
I have an abstract syntax tree which I need to iterate. The AST is generated
by the lemon port to PHP, found in PEAR.
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),
\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 in a RecursiveIteratorIterator::SELF_FIRST manner, 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, starting at the root. And since I want to
iterate bottom-up, I can't have that with RecursiveIteratorIterator, at
least not with it alone.
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(I assume), in order to iterate it
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.
So I'm looking for **as much SPL (re)usage as possible**. I know I could
write my own recursive functions with a custom stack.
A small PoC would be welcome.
Thanks
--
Flavius Aspra
