(árvores de sintaxe) iterando recursivamente sobre árvores de baixo para cima com o caminho atual de cima para baixo

Question

eu tenho um árvore de sintaxe abstrata que preciso iterar.O AST é gerado pelo porta limão para PHP.

Agora, "normalmente", eu faria isso com as classes SPL novíssimas e brilhantes (PHP 5.3.1), e ficaria assim:

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

Na verdade, é isso que já estou fazendo em outra parte do código que determina um tipo aproximado de toda a árvore (ou seja, pode ser uma atribuição, uma condição, etc).Deixando os detalhes de lado, a única coisa importante é que a iteração seja feita RecursiveIteratorIterator::SELF_FIRST, ou seja, de cima para baixo.

Voltando ao meu problema, preciso iterar o AST de baixo para cima, ou seja, algo como RecursiveIteratorIterator::CHILD_FIRST, para fazer algumas substituições e otimizações na árvore.

O problema é que essas operações precisam estar cientes do contexto, ou seja,Preciso do caminho até o nó atual.E como quero iterar de baixo para cima, não posso fazer isso com RecursiveIteratorIterator.

Bem, pense nisso por um segundo.Quero iterar de baixo para cima e ter o contexto de cima para baixo (uma pilha) do nó atual, em cada iteração.Tecnicamente deveria ser possível, já que RecursiveIteratorIterator deve primeiro ir até a cauda da árvore, para iterar para trás.No caminho para a cauda, ​​ele poderia armazenar em cache a posição atual e simplesmente exibir elementos à medida que retorna da recursão.

Agora, esta é uma palavra-chave: cache.É por isso que suspeito que isso deveria ser possível com outra classe SPL:RecursiveCachingIterator.

A questão é:é realmente possível?Se sim, como?

Tenho tentado resolver alguns códigos, sem sucesso, e a documentação é escassa.Realmente, muito escasso.

Quem encontrar a solução mais elegante para isso usando SPL, tire o chapéu!Você é um guru do PHP!

PS:caso não esteja claro, estou procurando tanto SPL (ré)uso possível.Eu sei que poderia escrever minhas próprias funções recursivas com uma pilha personalizada, não há necessidade de me lembrar disso.

Answer 1

Consegui fazê-lo funcionar herdando RecursiveIteratorIterator e gerenciando a pilha em ::endChildren() e ::callGetChildren respectivamente.Talvez isso ajude alguém.Tiro o chapéu para mim mesmo :-)