Полгода назад я начал копаться в исходном коде 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 работать интерактивно даже в гигантских решениях.