Классы TreeProcessor и TreeRebuilder

В библиотеке Ob51.Compiler.dll в пространстве имён Ob51.Compiler.InternalTree определены классы, производные от класса ProgramNode. Из их экземпляров строятся деревья – внутренние представления программ в компиляторе.

А в пространстве имён Ob51.Compiler.InternalTree.Processing есть 2 класса – TreeProcessor и TreeRebuilder. Они предназначены для обработки этих деревьев.

TreeProcessor

Класс TreeProcessor предназначен для восходящего обхода дерева. Он может менять дерево, но не приспособлен для удаления или замены узлов, не подходит он и для создания нового дерева на основе уже существующего.

Правила

TreeProcessor – это коллекция правил. Каждое правило – экземпляр класса, производного от TreeProcessor.Rule (их всех можно перечислить через IEnumerable<TreeProcessor.Rule>, то есть оператором foreach).

Правила содержат:

• свойство TypeToApplyTo, указывающее, к какому классу из Ob51.Compiler.InternalTree данное правило применимо. Это должен быть класс, производный от Ob51.Compiler.InternalTree.ProgramNode. Правило будет применимо к узлам дерева данного класса или любого класса, производного от него.
• метод virtual bool IsApplicableTo(ProgramNode node), проверяющий применимость правила к данному конкретному узлу дерева. Этот метод задаёт дополнительные условия сверх TypeToApplyTo, по которым решается, можно применять к узлу данное правило или нельзя.
• метод abstract ProgramNode Apply(ProgramNode input, IList<ProgramNode> childApplyResults), выполняющий применение правила к узлу дерева input. При этом результаты применения правил к детям input передаются в параметре childApplyResults.

Выполнение метода Apply считается применением правила к узлу input. Результат выполнения – ссылка на некоторый другой узел дерева. Эта ссылка передаётся правилам, применяемым к вышележащим узлам дерева.

Т.к. метод Apply – абстрактный, то и Rule – абстрактный класс, а реально в TreeProcessor могут помещаться только экземпляры классов, производных от Rule. Некоторые такие классы определены в самом TreeProcessor:

• IdentityRule, у которого Apply возвращает input как свой результат.
• DelegatingRule, экземпляры которого передают всю функциональность IsApplicableTo и Apply заданным делегатам, т.е. DelegatingRule позволяет создавать совершенно новые правила без наследования новых классов от Rule.

По умолчанию после создания TreeProcessor содержит единственное правило – экземпляр IdentityRule. Это позволяет добавлять правила только для отдельных конкретных классов узлов, все остальные будут обрабатываться по умолчанию без всяких изменений. Новые правила добавляются методами AddRule.

Обход дерева

Обработку дерева выполняет метод TreeProcessor.Process. Он принимает ссылку на корневой узел дерева и работает так:

1. Рекурсивно обрабатываются все поддеревья под корнем.
2. По свойствам TreeToApplyTo в данном экземпляре TreeProcessor ищутся правила, применимые к классу корня или к его предку. Из найденных выбираются те, у которых класс TreeToApplyTo – самый специфичный, то есть ниже всех по иерархии наследования.
3. Для каждого из правил, найденных на предыдущем шаге, вызывается его метод IsApplicableTo, параметром ему передаётся корень. Правила, возвращающие false, отбрасываются.
   Из оставшихся выбирается правило, добавленное в TreeProcessor последним.
4. В результате предыдущих шагов найдено либо одно правило, применимое к корню, либо ни одного. Если ни одного, то набор правил в TreeProcessor не может обработать данное дерево, и бросается исключение TreeProcessor.UnparseableTreeException.
   Если же одно применимое правило найдено, то оно применяется (вызывается его метод Apply). Результат Apply есть результат Process.

Таким образом, можно считать, что TreeProcessor выполняет восходящий обход дерева, применяя к каждому из узлов подходящее правило, пока не окажется, что всё дерево обработано (успех) или что подходящих правил нет (ошибка).

TreeRebuilder

Класс TreeRebuilder основан на TreeProcessor и тоже выполняет восходящий обход дерева, но он предназначен для существенной правки дерева или для создания нового дерева на основе старого.

Замена ссылок

TreeRebuilder обрабатывает 2 набора узлов в целом и для каждого правила: входные и выходные. Входные узлы – это все узлы входного дерева, и только они. Выходные узлы – узлы, возвращаемые правилами при применении. Из выходных узлов TreeRebuilder составляет выходное дерево.

Чтобы упростить при этом правила, TreeRebuilder запоминает отображение входных узлов в выходные, построенное применением правил. Кроме того, для каждого узла через reflection TreeRebuilder находит все поля и свойства, ссылающиеся на входные узлы, и заменяет эти ссылки ссылками на соответствующие выходные узлы.

Правила

TreeRebuilder – коллекция правил, аналогичная TreeProcessor. Правила TreeRebuilder обязательно наследуются от абстрактного класса TreeRebuilder.Rule и отличаются от правил TreeProcessor. Правила TreeProcessor нельзя использовать в TreeRebuilder, и наоборот.

Сразу после создания TreeRebuilder не содержит ни одного правила.

Правила содержат:

• свойство TypeToApplyTo, аналогичное правилам TreeProcessor.
• метод virtual bool IsApplicableTo(ProgramNode node), аналогичный правилам TreeProcessor.
• метод virtual ProgramNode RebuildNode(ProgramNode input, IList<ProgramNode> childApplyResults), возвращающий выходной узел по заданному входному (и результатам обработки его детей).
• метод abstract ProgramNode Apply(ProgramNode input, ProgramNode output, IList<ProgramNode> childApplyResults, out bool mapLinksFromOldToNew), применяющий правило к входному узлу и результату работы RebuildNode.

При применении правила сначала вызывается RebuildNode, который создаёт или как-то определяет выходной узел по входному input. По умолчанию TreeRebuilder.Rule.RebuildNode создаёт копию input вызовом ProgramNode.ShallowClone.

Метод Apply в параметре output принимает результат работы RebuildNode. Из узла output и результатов обработки поддеревьев в childApplyResults Apply должен составить поддерево выходного дерева, корень которого соответствует input. Корень этого выходного поддерева Apply должен вернуть как результат применения правила.

Обход дерева

Обход дерева выполняется так же, как и в TreeProcessor, за исключением двух моментов.

Во-первых, Apply имеет несколько иные параметры, и для инициализации одного из них при применении правила перед Apply вызывается RebuildNode.

Во-вторых, соответствие между входными узлами и результатами применения к ним правил запоминается внутри TreeRebuilder во время работы метода Process. А в конце его работы ссылки в выходных узлах переправляются так, чтобы указывать в выходное дерево вместо входного. Это поведение управляется выходным параметром mapLinksFromOldToNew метода Apply. Если он устанавливается в true, в данном узле выполняется замена ссылок, если в false – нет.

Возможны 2 основных применения TreeRebuilder:

1. Правка дерева. При этом множество выходных узлов частично (или даже полностью) совпадает со множеством входных.
   В этом случае RebuildNode возвращает те же узлы, что даются ему на вход, в Apply input==output, и всё, что делает Apply – исправляет тот узел, к которому применяется.
2. Построение нового дерева. Множество выходных узлов не пересекается со множеством входных.
   В этом случае RebuildNode копирует входной узел в новый узел (поведение по умолчанию), в Apply input!=output, и Apply, помимо правки узла output, должен заново составить поддерево, добавляя в output детей на основе списка childApplyResults.

Готовые правила

В TreeRebuilder реализованы следующие готовые к использованию классы правил:

• DelegatingRule, аналогичный одноименному в TreeProcessor.
• IdentityRule – правило, аналогичное одноимённому из TreeRebuilder, предназначено для обхода существующего дерева. В зависимости от настроек, оно либо вообще не меняет входной узел, возвращая его как выходной, либо только заново перестраивает список его детей. Перестройка списка детей удаляет из output всех детей и добавляет в него те узлы из childApplyResults, которые ещё не добавлены ни в какое дерево. По умолчанию перестройка списка детей выполняется, её можно выключить в конструкторе при создании правила.
• CloneRule – правило, создающее эквивалентную копию входного дерева. Его RebuildNode копирует узел, к которому оно применяется, а Apply добавляет childApplyResults как детей к копии и устанавливает mapLinksFromOldToNew в true, задействуя замену ссылок.

На основе TreeRebuilder и CloneRule реализован метод ProgramNode.Clone.