Красно-зеленые деревья: обзор

Полгода назад я начал копаться в исходном коде Roslyn, чтобы понять, что такое красно-зелёные деревья. Ниже — моя выжимка, то, что я хотел бы прочесть тогда.

Есть статья Persistence, Facades and Roslyn’s Red-Green Trees , которая довольно кратко, но ёмко описывает концепцию. Однако даже после её прочтения многое осталось непонятным, поэтому я ушёл в исходники Roslyn.

Глобальная архитектура рослина

Давайте для начала кое-что уясним, архитектура Roslyn такова, что она старается поддерживать два языка, поэтому там абстрактная нода SyntaxNode, если бы Roslyn был только для C#, то, скорее всего, методов и свойств RawKind, CreateSeparator не было бы.

Все эти абстракции не привязаны ни к C#, ни к VB.

Что такое красное нода

Красная нода сама по себе иммутабельная, и содержит минимум информации о синтаксисе, по сути красная нода это SyntaxTree + родитель если есть + абсолютная позиция в тексте + Зеленая нода

То есть все данные о синтаксисе хранятся в зеленой ноде, не в красной, красная лишь «выводит их на публику», и из-за этого красная нода занимает относительно меньше памяти, чем зелёная.

Красные ноды (как и зелёные) иммутабельны, но их иммутабельность — не для кэширования, а для параллельных анализаторов: любой SyntaxNode безопасно читать из нескольких потоков.

Да, именно красные ноды не кэшируются и не переиспользуются, и изменение даже одного символа приводит к перестройке всего красного дерева целиком — вот так радикально, но дальше вы увидите, что в этом нет ничего страшного.

Любой метод, «модифицирующий» красную ноду, на деле ­создаёт новый экземпляр с обновлёнными параметрами; исходная нода остаётся неизменной.

Допустим, вы создали следующий код:

var left  = SyntaxFactory.IdentifierName("a"); var right = SyntaxFactory.IdentifierName("b"); var sum   = SyntaxFactory.BinaryExpression(     SyntaxKind.AddExpression,     left,     SyntaxFactory.Token(SyntaxKind.PlusToken),     right);

left != sum.Left — это два разных объекта: разные родители, позиции, и даже разные деревья.

SyntaxToken и SyntaxTrivia

По сути, эти структуры тоже относятся к красным нодам, но с нюансом: экземпляр может и не знать о своём красном дереве. Проще говоря, SyntaxToken бывает двух видов:

• Есть связь с красным деревом:
  родительская красная нода + абсолютная позиция + индекс (о нём поговорим позже) + соответствующая зелёная нода;

• Нет связи:
  только зелёная нода.

SyntaxTrivia устроен так:

SyntaxToken + зелёная нода + позиция + индекс (подробности об индексе — позже).

Зачем вводить отдельные структуры? Любая красная нода содержит ссылку на дерево; если вы создадите узел через SyntaxFactory.BinaryExpression, у него уже будет собственное дерево. Заводить такое дерево, например, для каждой запятой — абсурд, с SyntaxTrivia ситуация аналогична.

Справедливости ради, деревья вычисляются лениво: если нет закэшированной ссылки, поиск идёт вверх по иерархии до первой ноды, у которой дерево уже построено; если и там не находится — создаётся новое дерево.

Зелёные ноды

Вся магия творится здесь: по сути, красные ноды — это лишь удобная «обёртка» вокруг зелёных, поэтому всё, что есть у зелёной ноды, доступно и красной.

Что есть у зелёной ноды? Ну… проще сказать, чего у неё нет.

Зелёные ноды (как и красные) иммутабельны. В отличие от красных, по зелёным нодам можно двигаться только вниз: они ничего не знают о своих родителях. У зелёных нод нет абсолютной позиции — только ширина (количество символов, которые они покрывают; например, if — два символа).

Зелёные ноды кэшируются и переиспользуются. С большой вероятностью (≈ 95 %) все ключевые слова (for, if, var, int, async, await и т. д.) представлены одной и той же зелёной нодой. Для каждого TokenWithWellKnownText (токенов, чей текст заранее известен — кавычки, знаки «+», «-», ключевые слова) создаётся пять вариантов зелёных нод:

Что такое elastic trivia

Это специальная «резиновая» вставка, которую форматировщик IDE может заменить подходящим отступом/новой строкой во время автоматического форматирования. Она нужна генераторам кода: можно сгенерировать AST без лишних пробелов, а потом доверить форматирование Roslyn.

таким образом, если вы напишете стандартный if

if (...)

парсер возьмёт уже кешированную зелёную ноду для if (тот самый токен с одним пробелом после). Но если вы напишете, например, так:

if // бегите я чокнутный (...) // или так for /* саня ты в порядке ? */ (...)

парсер создаст новый экземпляр зелёной ноды вместо того, чтобы переиспользовать кешированную.

В отличие от красного дерева, где при изменении даже одного символа перестраивается всё дерево целиком, с зелёным деревом ситуация мягче: по-прежнему создаётся новое зелёное дерево, но оно переиспользует примерно 99 % зелёных нод из предыдущей версии.

Зелёные ноды порождают красные. У них есть метод
abstract RedNode CreateRed(RedNode? parent, int position)
(RedNode — это SyntaxNode; я пишу так для ясности).

У зелёных нод есть собственная фабрика — GreenSyntaxFactory
(в исходниках она называется просто SyntaxFactory). Логика работы:

1. Проверяет, есть ли уже кешированная нода.

2. Если есть — возвращает её.

3. Если нет — создаёт новую и пытается закешировать.

Фабрика красных нод устроена так:

1. Проверяет входные данные на валидность.

2. Извлекает из красных объектов (SyntaxNode, SyntaxToken, SyntaxTrivia) соответствующие зелёные ноды.

3. Вызывает зелёную фабрику.

4. Оборачивает полученную зелёную ноду в красную.

Обратите внимание: зелёная фабрика ничего не проверяет и полностью доверяет вызывающему коду. Это принцип всей «зелёной» инфраструктуры — максимальная эффективность. Поэтому на зелёной стороне Roslyn почти нельзя встретить throw: обычным разработчикам она недоступна и не входит в Public API, так что внутри можно писать как угодно. В production-версии Roslyn исключения бросает только «красная» сторона.

Пример обёртывания: BinaryExpressionSyntax

Давайте рассмотрим на примере, что именно я имею в виду, когда говорю, что красная нода — это обёртка над зелёной. Ниже — немного упрощённый псевдокод:

public sealed partial class BinaryExpressionSyntax : ExpressionSyntax {     // Ленивые (!) красные дочерние узлы     internal ExpressionSyntax? _left;     internal ExpressionSyntax? _right;      internal BinaryExpressionSyntax(GreenBinaryExpressionSyntax green,                                     RedNode? parent,                                     int position)         : base(green, parent, position) { }      internal BinaryExpressionSyntax(GreenBinaryExpressionSyntax green,                                     int position,                                     SyntaxTree syntaxTree)         : base(green, position, syntaxTree) { }      // Удобный «каст» к конкретному виду зелёной ноды     internal new GreenBinaryExpressionSyntax Green =>         System.Runtime.CompilerServices.Unsafe.As<GreenBinaryExpressionSyntax>(base.Green);      // Получаем красное представление левого выражения     public ExpressionSyntax Left  => GetRed(ref _left, 0)!;      // OperatorToken изначально зелёный ― оборачиваем его в SyntaxToken     public SyntaxToken OperatorToken =>         new(Parent, Green.OperatorToken, GetChildPosition(1), GetChildIndex(1));      // Красное представление правого выражения     public ExpressionSyntax Right => GetRed(ref _right, 2)!;      // Навигация по дочерним узлам     public override RedNode? GetNodeSlot(int index) =>         index switch         {             0 => GetRed(ref _left, 0)!,             // Элемент c индексом 1 ― это `OperatorToken`             2 => GetRed(ref _right, 2)!,             _ => null         }; }  internal sealed partial class GreenBinaryExpressionSyntax : GreenExpressionSyntax {     // Истинные «носители» данных     public readonly GreenExpressionSyntax Left;     public readonly GreenSyntaxToken      OperatorToken;     public readonly GreenExpressionSyntax Right;      public GreenBinaryExpressionSyntax(GreenExpressionSyntax left,                                        GreenSyntaxToken operatorToken,                                        GreenExpressionSyntax right,                                        DiagnosticInfo[]? diagnostics = null,                                        SyntaxAnnotation[]? annotations = null)         : base(SyntaxKind.None, diagnostics, annotations)     {         Left          = left;         OperatorToken = operatorToken;         Right         = right;     }      public override GreenNode? GetSlot(int index) =>         index switch         {             0 => Left,             1 => OperatorToken,             2 => Right,             _ => null         };      public override RedNode CreateRed(RedNode? parent, int position) =>         new BinaryExpressionSyntax(this, parent, position); } 

Как видно, зелёная нода ― настоящий хранитель данных; красная лишь выводит их наружу.

Как работает GetRed

protected T? GetRed<T>(ref T? field, int slot) where T : RedNode {     var result = field;      if (result == null)     {         var green = this.Green.GetSlot(slot);         if (green != null)         {             Interlocked.CompareExchange(                 ref field,                 (T)green.CreateRed(this, GetChildPosition(slot)),                 comparand: null);              result = field;         }     }      return result; }

GetRed выполняет ленивое оборачивание дочерней зелёной ноды в красную:

1. Проверяем кеш. Если красная нода уже создана (field != null), просто возвращаем её.

2. Берём зелёную ноду. Метод Green.GetSlot(slot) даёт ссылку на нужного «зелёного» ребёнка.

3. Создаём красную обёртку. Вызов green.CreateRed(...) строит красный узел, зная родителя и абсолютную позицию.

4. Фиксируем результат потокобезопасно. Interlocked.CompareExchange гарантирует, что в многопоточном окружении все потоки увидят один и тот же объект.

5. Возвращаем ссылку (либо null, если дочернего узла нет).

Структура зелёных нод

RawKind

Зелёные ноды в Roslyn предельно оптимизированы. Первый показатель этой оптимизации — поле RawKind.

Зачем оно нужно? Это самый дешёвый способ узнать тип узла: проверка по целому числу быстрее, чем писать node is BinaryExpressionSyntax.

• Свойство объявлено как int (32 бита):

  public int RawKind { get; }

• На деле оно ссылается на поле _kind размером ushort (16 бит), что экономит память.

Если открыть SyntaxKind.cs, то видно, что перечисление C# начинается с 8193. Сначала кросс-язычные индексы (ListKind). Затем первые ≈ 800 значений заняты VB-специфичными SyntaxKind.vb, и лишь потом C#. Почему именно с 13-го бита? Да кто его знает, может так удобнее разделить два языка единой таблицей, типа вон если 13 бит активен значит это c#.

SlotCount

Каждая зелёная нода состоит из фиксированного числа «дочерних» слотов. Свойство SlotCount говорит, сколько их.

Важно: у подавляющего большинства узлов (≈ 99 %) количество слотов фиксировано для самого типа. Например, у FieldDeclarationSyntax их всегда четыре — даже если какие-то из позиций пусты. Лишь у немногих «особых» узлов это число может меняться, поэтому вычисляется во время выполнения с помощью GetSlotCount(): на этапе компиляции точное значение неизвестно.

Пример — FieldDeclarationSyntax:

[Attribute] public int a;

• AttributeLists

• Modifiers

• VariableDeclaration (int a)

• SemicolonToken

Всего 4 слота. А если мы сократим объявление до

int a;

атрибутов и модификаторов нет, но индексы слотов сохраняются:

internal readonly GreenNode? attributeLists; internal readonly GreenNode? modifiers; internal readonly VariableDeclarationSyntax declaration; internal readonly SyntaxToken semicolonToken;  internal override GreenNode? GetSlot(int index) => index switch {     0 => attributeLists,     1 => modifiers,     2 => declaration,     3 => semicolonToken,     _ => null }; 

Пустые позиции возвращают null, но счёт идёт тем же индексом.

Как упакован SlotCount

Поле _data внутри каждой зелёной ноды хранит множество битов. Четыре младших бита отведены именно под количество слотов:

1. Берутся последние 4 бита.

2. Если значение = 15 (SlotCountTooLarge), вызывается виртуальный GetSlotCount() — это случается лишь у редких узлов, где слотов > 15.

3. Иначе число возвращается напрямую.

Есть и «облегчённое» свойство SmallSlotCount, которое без проверок читает те же 4 бита. Оно никогда не вызывает виртуальный метод — поэтому быстрее обычного SlotCount. Такой микро-оптимизацией Roslyn пользуется повсеместно :-).

Флаги

Мы узнали, что четыре младших бита в поле _data отводятся под SlotCount. Что же содержится в остальных 12? Оставшиеся 12 битов поля _data занимают логические флаги, которые Roslyn хранит прямо в каждой зелёной ноде. Привет всем байтодрочерам.

Всего флагов десять; оставшиеся два бита пока зарезервированы.

Наследуемые флаги

Семь из перечисленных флагов «поднимаются» вверх по дереву. Если у дочерней зелёной ноды, скажем, ContainsAnnotations == true, то этот бит устанавливается у родителя, у родителя родителя и так далее до корня. Roslyn делает это побитовой операцией OR при присоединении дочернего узла.

InheritMask =    IsNotMissing    | ContainsAnnotations    | ContainsAttributes    | ContainsDiagnostics    | ContainsDirectives    | ContainsSkippedText    | ContainsStructuredTrivia

FullWidth

FullWidth — это суммарная длина зелёной ноды в символах:

FullWidth = Width              // «тело» узла           + LeadingTriviaWidth  // пробелы/комментарии слева (leading)           + TrailingTriviaWidth // пробелы/комментарии справа (trailing) 

Поле хранится как uint (32 бита). В итоге внутренний «пакет» данных зелёной ноды выглядит так:

Итого: 64 бита (8 байт) на служебную информацию — минимум, позволяющий Roslyn одновременно знать тип узла, его размер, набор диагностических/структурных маркеров и количество дочерних слотов.

«Виртуальные» флаги

У базового класса GreenNode есть несколько виртуальных свойств-флагов, которые переопределяются в специализированных типах:

public virtual bool IsStructuredTrivia            => false; public virtual bool IsDirective                   => false; public virtual bool IsToken                       => false; public virtual bool IsTrivia                      => false; public virtual bool IsSkippedTokensTrivia         => false; public virtual bool IsDocumentationCommentTrivia  => false;

• Если IsTrivia (или один из его подвидов [IsStructuredTrivia, IsDirective, IsSkippedTokensTrivia, IsDocumentationCommentTrivia] ) возвращает true, красная сторона оборачивает такую зелёную ноду в SyntaxTrivia.

• Если IsToken == true, зелёная нода превращается в красный SyntaxToken.

«Виртуальные» флаги не занимают памяти на уровне объекта: это просто методы, которые компилятор может даже встроить, так что дополнительной нагрузки на память нет.

Green SyntaxList

GreenSyntaxList — единственный зелёный узел, у которого количество слотов реально может меняться. Но и он устроен не так уж просто.

Так же GreenSyntaxList кроссязычный, то есть он используется как в Vb так и в c#.

Красные обёртки

Зелёный список превращается либо в красный SyntaxList, либо в SeparatedSyntaxList (та же структура, но с разделителями — запятые, точки с запятой и т. д.).

Микро-списки (≤ 3 детей)

Если у списка ≤ 3 элементов, фабрика GreenSyntaxList.List(…) создаёт специализированные классы и пытается их кешировать:

Средние списки (4 – 9 детей) — WithManyChildren

Если детей от 4 до 9 фабрика отдаёт WithManyChildren:

public static GreenSyntaxList List(GreenNode[] children) {     return children.Length < 10          ? new WithManyChildren(children)          : new WithLotsOfChildren(children); }

Секрет: класс не переопределяет GetSlotOffset и FindSlotIndexContainingOffset — линейный проход по 4–9 элементам выполняется за наносекунды и не требует доп.памяти.

Большие списки (≥ 10 детей) — WithLotsOfChildren

Для действительно крупных коллекций создаётся WithLotsOfChildren, который заранее вычисляет массив префиксных смещений _childOffsets:

private readonly int[] _childOffsets;  public override int GetSlotOffset(int index)          // O(1)     => _childOffsets[index];  public override int FindSlotIndexContainingOffset(int offset) // O(log N)     => _childOffsets.BinarySearchUpperBound(offset) - 1;  // базовые реализации  public virtual int FindSlotIndexContainingOffset(int offset) // O(N)  {     Debug.Assert(0 <= offset && offset < FullWidth);      int i;     var accumulatedWidth = 0;      for (i = 0; ; i++)     {         Debug.Assert(i < SlotCount);         var child = GetSlot(i);         if (child != null)         {             accumulatedWidth += child.FullWidth;             if (offset < accumulatedWidth)             {                 break;             }         }     }      return i; }   public virtual int GetSlotOffset(int index) // O(i) {     var offset = 0;     for (var i = 0; i < index; i++)     {         var child = GetSlot(i);          if (child != null)         {             offset += child.FullWidth;         }     }      return offset; }

Префиксные суммы считаются один раз в конструкторе, затем позволяют мгновенно переходить от позиции в тексте к нужному элементу списка и обратно. На длинных списках (argument list, where-клауз и т. д.) это даёт заметный выигрыш.

Почему не использовали тот же приём в WithManyChildren?
Для 4–9 узлов массив int[n] добавил бы 24–40 байт, а выигрыш почти не чувствуется. Roslyn предпочёл GC-дружелюбие вместо гипер-оптимизации там, где она не нужна.

Заключение

Roslyn делит обязанности:

• Зелёные ноды — крошечные, кэшируемые и неизменяемые «кирпичи» AST.

• Красные ноды — удобные обёртки: дают родителя, позицию и дружественный API IDE; создаются лениво, сразу после запроса, и не тянут память после правок.

• Битовая упаковка и ступенчатые списки держат весь объектный парк сверхкомпактным.

Именно эта смесь экономии и удобства позволяет компилятору и IDE работать интерактивно даже в гигантских решениях.