(деревья синтаксиса) рекурсивно итерации над деревьями снизу вверх с текущей нисходящей дорогой

Question

У меня есть abstract syntax tree, который мне нужен для повторения. AST генерируется lemon port to PHP.

Теперь «нормально», я хотел бы сделать это с совершенно новой и блестящей (PHP 5.3.1) SPL классов, и это будет выглядеть следующим образом:

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

На самом деле, это то, что я уже выполняющий в другой части кода, который определяет грубый тип всего дерева (т. е. может быть назначение, условие и т. д.). Теперь подробности в сторону, единственная важная вещь - итерация выполнена RecursiveIteratorIterator :: SELF_FIRST, то есть сверху вниз.

Возвращаясь к моей проблеме, мне нужно выполнить итерацию снизу вверх по AST, то есть что-то вроде RecursiveIteratorIterator :: CHILD_FIRST, чтобы сделать некоторые замены и оптимизации в дереве.

Проблема в том, что эти операции должны быть контекстно-зависимыми, то есть мне нужен путь до текущего узла. И так как я хочу итерации снизу вверх, я не могу иметь это с RecursiveIteratorIterator.

Хорошо подумайте об этом на секунду. Я хочу повторить снизу вверх и иметь контекст сверху вниз (стек) текущего узла на каждой итерации. Технически это должно быть возможно, так как RecursiveIteratorIterator должен сначала перейти к хвосту дерева, чтобы итератировать назад. По пути к хвосту он может кэшировать текущую позицию и просто выталкивать элементы, возвращаясь из рекурсии.

Это ключевое слово: caching. Вот почему я подозреваю, что это должно быть возможно с другим классом SPL: RecursiveCachingIterator.

Вопрос в следующем: действительно ли возможно? Если да, то как?

Я пытаюсь решить некоторые проблемы с помощью кода, но безуспешно, и документации недостаточно. Действительно, действительно мало.

Кто найдет самое элегантное решение для этого, используя SPL, шляпы выключены! Вы - гуру PHP!

PS: в случае, если это не ясно, я ищу столько SPL (повторно) использования в качестве возможного. Я знаю, что могу написать свои собственные рекурсивные функции с помощью специального стека, не нужно напоминать мне об этом.

Answer 1

Мне удалось заставить его работать, наследуя RecursiveIteratorIterator и управляя стеком в :: endChildren() и :: callGetChildren соответственно. Может быть, это поможет кому-то. Шляпы от меня :-)