Персистентность, фасады и красно-зеленые деревья в Roslyn
На ранних стадиях дизайна проекта Roslyn мы решили, что основной структурой данной, с которой будут иметь дело разработчики при анализе кода, будет синтаксическое дерево (syntax tree). Таким образом, одной из самых сложных задач на ранних стадиях дизайна было определение того, как мы будем реализовывать узлы синтаксического дерева, и какую информацию они будут предлагать пользователю. Мы хотели получить структуру данных со следующими характеристиками:
- Неизменяемость.
- Древовидное представление.
- Простой доступ к родительским узлам из дочерних.
- Возможность получения соответствия между узлом дерева и смещением символа в тексте.
- Персистентность (persistent).
Под персистентностью (persistence) я понимаю возможность повторного использования большей части существующих узлов дерева при редактировании текста в текстовом буфере. Как мы много раз обсуждали, поскольку узлы являются неизменяемыми, то ничто не мешает использовать их повторно. Нам нужно это для обеспечения высокой производительности; мы не можем повторно анализировать огромные куски текста каждый раз при нажатии на кнопку. Нам нужно выполнить повторный разбор и лексический анализ только тех участков дерева, которые подверглись изменениям во время редактирования (*), поскольку мы обычно выполняем эту операцию между всеми нажатиями клавиш.
Когда вы попытаетесь собрать все пять вышеописанных характеристик в одну структуру данных, вы сразу же столкнетесь с проблемами:
- Как вы вообще собираетесь создавать узлы дерева? Родительский и дочерний узлы ссылаются друг на друга и неизменяемы, какой из них нужно создавать первым?
- Предположим, вы решили эту задачу: как вы обеспечите персистентность? Вы не можете повторно использовать дочерний узел с другим родительским узлом, поскольку вам придется сказать ему, что у него теперь новый родительский узел. Но дочерний узел является неизменяемым.
- Предположим, вы смогли решить и эту задачу: при добавлении нового символа в редактируемый буфер, абсолютная позиция каждого узла, соответствующего некоторой позиции, после данного символа изменяется. Это сильно усложняет создание персистентной структуры данных, поскольку любое изменение может изменить значение большинства узлов!
Но в команде Roslyn мы постоянно делает невозможные вещи. На самом деле, мы сделали невозможное, храня два разобранных дерева. «Зеленое» дерево является неизменяемым, персистентным, не содержит ссылки на родительский узел, построено «снизу вверх» и каждый узел отслеживает ширину, а не абсолютное положение. При редактировании мы перестраиваем только часть зеленого дерева, измененного во время редактирования, что обычно занимает порядка O(log n) времени разбора узлов всего дерева.
«Красное» дерево является изменяемым фасадом, построенным вокруг зеленого дерева; оно строится «сверху вниз» по требованию и выбрасывается при каждом редактировании. Оно вычисляет родительские ссылки, создавая их по требованию по мере спуска вниз по дереву. Оно создает абсолютное положение, вычисляя его по значениям ширины, опять-таки, по мере спуска вниз.
Вы, как пользователь Roslyn API видите только красное дерево, а зеленое дерево является лишь деталью реализации. (И если вы посмотрите в отладчике на внутреннее состояние разобранного узла, то на самом деле вы увидите ссылку на другой разобранный узел другого типа; это узел зеленого дерева.)
Эти деревья названы «красно/зелеными» чисто случайно, поскольку маркеры именно такого цвета мы использовали для рисования структур данных во время встреч по дизайну. Никакого другого значения в этих цветах нет.
Преимущество такого подхода заключается в том, что мы добились всех требуемых характеристик: неизменяемости, персистентности, наличия ссылок на родительские узлы и т.д. Обратная сторона этого решения заключается в ее сложности и может потреблять много памяти, если «красные» фасады будут становиться слишком большими. Сейчас мы экспериментируем, можем ли мы уменьшить некоторые из этих затрат не потеряв основных преимуществ.
(*) Определение того, к каким частям дерева это относится, является довольно сложной темой; возможно, я напишу об этом позже. Например, если вы добавляете к объявлению метода ключевое слово «async», то это может привести к тому, что анализ «await(foo);» в теле метода изменится, и вместо вызова метода будет использоваться контекстное ключевое слово await.