Инкрементальный парсер на c#

Ура, вот и добрались мы до того момента, зачем мы вообще использовали рослиновкскую модель дерева. В прошлый раз мы дошли до того момента, когда .akbura файл уже можно разобрать в lossless syntax tree: лексер читает токены, парсер собирает state, param, inject, useEffect, command, markup, inline Akcss и C# fragments. Это уже похоже на настоящий язык, но для IDE этого мало.

1. Создаём синтаксис

2. Пишем парсер

3. Собираем блендер

4. Добавляем семантику

5. Диагностика

6. Интегрируем Language Server Protocol и делаем поддержку в Visual Studio

7. Генерируем код

Зачем нужен блендер

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

Пользователь не открывает файл один раз и не нажимает кнопку Parse. Он печатает. Потом стирает. Потом снова печатает. Иногда меняется один символ в середине файла:

state int count = 0;

Например, стало так:

state int total = 0;

С точки зрения полного парсера это новый текст. Значит можно снова пройти весь файл от первого символа до последнего. Но если в файле тысяча компонентов, markup на несколько экранов, inline Akcss и куча C# blocks, получается странная картина: пользователь изменил count, а мы заново строим всё дерево.

В обычном compiler pipeline это может быть приемлемо. В IDE это быстро начинает мешать. Подсветка, diagnostics, completion, semantic model — всё это завязано на частое обновление дерева. Поэтому хочется использовать старое дерево и пересобрать только ту часть, которую реально затронуло изменение.

Вот здесь появляется блендер.

Идея блендера простая: парсер всё ещё хочет линейный поток. Он не хочет думать, откуда пришёл следующий элемент. Раньше источник был один — лексер. Теперь источников два:

старое syntax tree  => можно переиспользовать старые узлы и токены
новый SourceText    => нужно заново лексить изменённые места

Блендер стоит между парсером, лексером и старым деревом. Парсер спрашивает: дай следующий токен или node. Блендер смотрит на позицию, смотрит на изменения и решает:

если старый узел безопасен => вернуть старый узел
если место изменилось      => прочитать свежий token из lexer-а

Поэтому название довольно удачное. Он действительно смешивает старый поток синтаксиса и новый поток токенов.

TextChangeRange

Начинается всё с TextChangeRange. Это тип из Roslyn. Он говорит, какой диапазон старого текста был заменён и какой длины стал новый кусок.

Упрощённо:

var change = new TextChangeRange(
    new TextSpan(start: 10, length: 5),
    newLength: 8);

Это значит:

в старом тексте с позиции 10 было 5 символов
в новом тексте на этом месте теперь 8 символов

Важно, что TextChangeRange хранит span в координатах старого текста. А парсер читает новый текст. Значит нам постоянно нужно сопоставлять old positions и new positions.

Простейший пример:

old: state count = 0;
new: state counter = 0;

Мы заменили count на counter. Старый кусок длиной 5, новый длиной 7. После этого все старые позиции справа от изменения сдвинулись на +2.

Вот это смещение в блендере хранится как _changeDelta.

private readonly int _changeDelta;

Если изменение одно, всё выглядит просто:

newPosition = oldPosition + changeDelta

Если изменений несколько, их можно свернуть:

var collapsed = TextChangeRange.Collapse(changes);

На первом этапе этого достаточно. Да и к тому же сами Roslyn сделали так же. Это кстати немного удивляет, что они до сих пор не выполнели эту тудушку, видимо слишком сложно ее реализовать, ну или просто нет смысла так как их инкрементальный парсер и так достаточно быстр.

В текущей реализации Blender принимает старое дерево и набор изменений:

public Blender(
    Lexer lexer,
    AkburaSyntax oldTree,
    IEnumerable<TextChangeRange> changes)
{
    _lexer = lexer;
    _changes = ImmutableStack<TextChangeRange>.Empty;

    if (changes != null)
    {
        var collapsed = TextChangeRange.Collapse(changes);
        _changes = _changes.Push(ExtendToAffectedRange(oldTree, collapsed));
    }

    if (oldTree == null)
    {
        _oldTreeCursor = default;
        _newPosition = lexer.TextWindow.Position;
    }
    else
    {
        _oldTreeCursor = new Cursor(oldTree).MoveToFirstChild();
        _newPosition = 0;
    }

    _changeDelta = 0;
}

ExtendToAffectedRange пока почти ничего не расширяет. В Roslyn ExtendToAffectedRange устроен сложнее, потому что C# grammar имеет много мест, где изменение одного символа может поменять смысл соседнего токена или конструкции. В Akbura на этом этапе я оставил консервативную модель. Если есть сомнение, проще не переиспользовать узел. Главная цель первой версии — получить архитектуру, которую потом можно расширять.

BlendedNode

Парсер может попросить у блендера две разные вещи:

1. дай следующий токен

2. дай следующий reusable node

Поэтому нужен маленький контейнер, который умеет вернуть либо старую красную-ноду, либо токен.

В Akbura он выглядит так:

internal readonly struct BlendedNode
{
    public readonly AkburaSyntax? Node;
    public readonly SyntaxToken Token;
    public readonly Blender Blender;

    public BlendedNode(AkburaSyntax? node, SyntaxToken token, Blender blender)
    {
        Node = node;
        Token = token;
        Blender = blender;
    }
}

Здесь нет сложной логики. Это просто результат чтения.

Если Node != null, блендер смог взять кусок из старого дерева. Например, целый GreenStateDeclarationSyntax или GreenMarkupRootSyntax.

Если пришёл Token, значит старый узел не подошёл, и блендер прочитал новый токен из лексера.

Третье поле — Blender. Это важная часть.

Blender сделан иммутабельным. Когда мы читаем элемент, старый блендер не мутируется наружу. Вместо этого результат возвращает новый блендер, который уже знает следующую позицию, следующий cursor и следующий change state.

Поэтому чтение выглядит так:

var first = blender.ReadToken(Lexer.LexerMode.TopLevel);
var second = first.Blender.ReadToken(Lexer.LexerMode.TopLevel);

Это очень удобно для тестов. Можно явно видеть, что следующий шаг делается от состояния, которое вернул предыдущий шаг.

Cursor

Чтобы переиспользовать старое дерево, его нужно как-то обходить. Можно было бы каждый раз искать узел по позиции через tree APIs, но это быстро станет дорого. Блендер читает поток слева направо, поэтому и старое дерево удобно обходить слева направо.

Для этого есть Blender.Cursor.

internal readonly struct Cursor
{
    private readonly SyntaxNodeOrToken _current;
    private readonly PathNode? _parent;
    private readonly int _indexInParent;
}

Cursor начинается с root:

public Cursor(AkburaSyntax root)
    : this(new SyntaxNodeOrToken(root), parent: null, indexInParent: 0)
{
}

Но сам root нам обычно не нужен. Парсер не будет переиспользовать весь AkburaDocumentSyntax целиком в первой версии. Поэтому при создании блендера, курсор сразу двигается к первому child:

_oldTreeCursor = new Cursor(oldTree).MoveToFirstChild();

MoveToFirstChild

MoveToFirstChild пытается спуститься внутрь текущей node:

public Cursor MoveToFirstChild()
{
    if (IsFinished || !_current.AsNode(out var node))
    {
        return MoveToNextSibling();
    }

    var children = node.ChildNodesAndTokens();
    if (TryGetFirstNonZeroWidthChild(children, out var child, out var childIndex))
    {
        return new Cursor(
            child,
            new PathNode(_current, _parent, _indexInParent, children),
            childIndex);
    }

    return MoveToNextSibling();
}

Здесь есть несколько деталей.

Во-первых, cursor работает с red tree, потому что позиции удобнее брать именно от red nodes и токенов. Green tree хранит ширину, но не хранит абсолютную позицию в файле. А блендер постоянно сравнивает старые позиции с новыми.

Во-вторых, cursor пропускает zero-width children. В syntax tree часто бывают missing-токены. Например, парсер ожидал ;, не нашёл его и создал missing semicolon-токен шириной 0. Для обычного дерева это полезно: структура остаётся полной. Для потока переиспользования такие элементы могут мешать. Они не занимают места в тексте, поэтому cursor их пропускает.

Исключение EndOfFileToken:

private static bool IsNonZeroWidthOrIsEndOfFile(SyntaxNodeOrToken nodeOrToken)
{
    var underlying = nodeOrToken.UnderlyingNode;
    return underlying != null &&
           (underlying.FullWidth > 0 ||
            underlying.Kind == SyntaxKind.EndOfFileToken);
}

EOF тоже zero-width, но это реальный токен конца потока.

MoveToNextSibling

Когда текущий узел прочитан, нужно перейти к соседу:

public Cursor MoveToNextSibling()
{
    if (IsFinished)
    {
        return default;
    }

    var parent = _parent;
    if (parent == null)
    {
        return default;
    }

    if (TryGetNextNonZeroWidthChild(
            parent.Children,
            _indexInParent + 1,
            out var sibling,
            out var siblingIndex))
    {
        return new Cursor(sibling, parent, siblingIndex);
    }

    return MoveToParent().MoveToNextSibling();
}

Если sibling есть, всё просто. Если sibling-а нет, cursor поднимается к родителю и ищет следующего соседа уже у него.

Именно поэтому cursor хранит PathNode:

private sealed class PathNode
{
    public readonly SyntaxNodeOrToken NodeOrToken;
    public readonly PathNode? Parent;
    public readonly int IndexInParent;
    public readonly ChildSyntaxList Children;
}

Это маленький стек родителей. Он нужен, чтобы двигаться по дереву без рекурсивного обходчика и без повторного поиска пути от root.

MoveToParent

Иногда блендер спускается слишком глубоко и потом должен подняться. Например, когда он искал первый токен внутри node или когда MoveToReusableNode хочет найти самый крупный безопасный узел.

public Cursor MoveToParent()
{
    if (IsFinished)
    {
        return default;
    }

    var parent = _parent;
    if (parent == null)
    {
        return default;
    }

    return new Cursor(parent.NodeOrToken, parent.Parent, parent.IndexInParent);
}

Сама операция простая, потому что путь уже сохранён.

Reader

Cursor только ходит по старому дереву. Решение, читать старое дерево или новый лексер, принимает Blender.Reader.

Внешний Blender почти ничего не делает сам:

public BlendedNode ReadNode(Lexer.LexerMode mode)
{
    return ReadNodeOrToken(mode, asToken: false);
}

public BlendedNode ReadToken(Lexer.LexerMode mode)
{
    return ReadNodeOrToken(mode, asToken: true);
}

public BlendedNode ReadFreshToken(Lexer.LexerMode mode)
{
    var reader = new Reader(this);
    return reader.ReadFreshToken(mode);
}

Он создаёт Reader, reader делает работу и возвращает новый Blender внутри BlendedNode.

У reader-а есть mutable поля:

private struct Reader
{
    private Lexer _lexer;
    private Cursor _oldTreeCursor;
    private ImmutableStack<TextChangeRange> _changes;
    private int _newPosition;
    private int _changeDelta;
}

Внутри одного чтения удобно мутировать состояние. Наружу это состояние возвращается как новый Blender:

private Blender CreateBlender()
{
    return new Blender(
        _lexer,
        _oldTreeCursor,
        _changes,
        _newPosition,
        _changeDelta);
}

ReadNodeOrToken

Главный метод reader-а выглядит так:

public BlendedNode ReadNodeOrToken(Lexer.LexerMode mode, bool asToken)
{
    SkipPastChanges();
    if (!IsWithinCurrentChangeInNewText(_newPosition))
    {
        SkipOldTreePastNewPosition();
    }

    if (TryReadOldNodeOrToken(mode, asToken, out var blended))
    {
        return blended;
    }

    if (!asToken)
    {
        return default;
    }

    _oldTreeCursor = MoveToFirstToken(_oldTreeCursor);
    return ReadNewToken(mode);
}

Порядок такой:

1. убрать изменения, которые уже остались позади

2. подвинуть old cursor до текущей new position

3. попробовать взять старый node или токен

4. если нужен токен и старый токен не подошёл, прочитать свежий токен из лексера

Если парсер попросил node, а старый node не подошёл, reader возвращает default. Это значит: reusable node сейчас нет, парсер должен пойти обычным путём и читать токены.

Если парсер попросил токен, он всегда должен получить токен. Поэтому fallback идёт в лексер.

SkipPastChanges

Когда _newPosition уже ушла правее текущего изменения, change можно выкинуть из стека:

private void SkipPastChanges()
{
    while (!_changes.IsEmpty)
    {
        var change = _changes.Peek();
        var newEnd = change.Span.Start + _changeDelta + change.NewLength;
        if (_newPosition < newEnd)
        {
            break;
        }

        _changes = _changes.Pop();
        _changeDelta += change.NewLength - change.Span.Length;
    }
}

Именно здесь обновляется _changeDelta.

Допустим, старый кусок был длиной 5, новый стал длиной 7. После прохождения этого изменения delta станет +2. Все старые позиции правее изменения теперь должны сравниваться с новыми позициями с этим сдвигом.

IsWithinCurrentChangeInNewText

Проверка изменённой области считается в координатах нового текста:

private bool IsWithinCurrentChangeInNewText(int position)
{
    if (_changes.IsEmpty)
    {
        return false;
    }

    var change = _changes.Peek();
    var newStart = change.Span.Start + _changeDelta;
    var newEnd = change.Span.Start + _changeDelta + change.NewLength;
    return position >= newStart && position < newEnd;
}

Если текущая позиция внутри changed range, старое дерево использовать нельзя. Даже если там случайно лежит похожий токен, его нельзя брать: текст поменялся.

TryReadOldNodeOrToken

Это сердце блендера:

private bool TryReadOldNodeOrToken(
    Lexer.LexerMode mode,
    bool asToken,
    out BlendedNode blended)
{
    if (IsWithinCurrentChangeInNewText(_newPosition))
    {
        blended = default;
        return false;
    }

    var cursor = asToken
        ? MoveToFirstToken(_oldTreeCursor)
        : MoveToReusableNode(_oldTreeCursor);

    if (cursor.IsFinished)
    {
        blended = default;
        return false;
    }

    var nodeOrToken = cursor.Current;
    var oldSpan = nodeOrToken.FullSpan;
    var expectedNewPosition = oldSpan.Start + _changeDelta;

    if (expectedNewPosition != _newPosition ||
        IntersectsNextChange(oldSpan) ||
        !CanReuse(nodeOrToken, asToken))
    {
        blended = default;
        return false;
    }

    _newPosition += nodeOrToken.FullSpan.Length;
    _oldTreeCursor = cursor;
    _oldTreeCursor = MoveOldTreePast(_newPosition);
    _lexer.TextWindow.Reset(_newPosition);

    blended = asToken
        ? new BlendedNode(null, nodeOrToken.AsToken(), CreateBlender())
        : new BlendedNode(nodeOrToken.AsNode(), default, CreateBlender());
    return true;
}

Сначала reader выбирает, что искать:

asToken == true   => спуститься до первого token
asToken == false  => найти reusable node

Потом проверяет позицию.

var expectedNewPosition = oldSpan.Start + _changeDelta;

Если старый узел после учёта delta должен начинаться не там, где сейчас стоит reader, значит он не подходит. Такое бывает после вставки/удаление, когда cursor ещё не догнал новое положение.

Дальше проверяется пересечение со следующим change:

IntersectsNextChange(oldSpan)

Если старый узел хотя бы частично пересекается с изменением, его нельзя переиспользовать целиком. Нужно разобрать заново хотя бы эту область.

И наконец CanReuse.

ReadNewToken

Когда старый node или токен не подходит, reader идёт в лексер:

private BlendedNode ReadNewToken(Lexer.LexerMode mode)
{
    _lexer.TextWindow.Reset(_newPosition);

    var position = _lexer.TextWindow.Position;
    var token = _lexer.Lex(mode);
    var nextCursor = IsWithinCurrentChangeInNewText(position)
        ? _oldTreeCursor
        : MoveOldTreePast(position + token.FullWidth);

    _oldTreeCursor = nextCursor;
    _newPosition += token.FullWidth;

    return new BlendedNode(
        null,
        new SyntaxToken(parent: null, token: token, position: position, index: 0),
        CreateBlender());
}

Тут видно, почему FullWidth так важен. Если токен или node неправильно считает ширину, блендер начнёт двигаться не туда. Сначала это выглядит как маленький сдвиг на один пробел, а потом парсер внезапно начинает видеть state int after 1;; или похожие чудеса.

Поэтому позже в тесты добавилась проверка:

Assert.Equal(code.Length, syntax.FullWidth);

ToFullString() проверяет текст. FullWidth проверяет внутреннюю математику дерева. И как оказался около 8 нод у меня не правильно читали ширину, это не было проблемой раньше, но как только добрались до блендера “спящие” баги пробудились.

Правила переиспользование

Переиспользование старого дерева — это не просто оптимизация. Это ещё и риск. Если взять старый узел там, где текст уже поменялся или где старое дерево было ошибочным, можно получить дерево, которое не соответствует новому тексту.

Поэтому правила лучше делать строгими.

В Akbura сейчас проверка начинается так:

private static bool CanReuse(SyntaxNodeOrToken nodeOrToken, bool asToken)
{
    if (ContainsDiagnosticsOrSkippedText(nodeOrToken.RequiredUnderlyingNode))
    {
        return false;
    }

    return asToken
        ? nodeOrToken.IsToken
        : nodeOrToken.IsNode;
}

Самое важное:

1. узлы с diagnostics не переиспользуем

2. узлы со skipped text не переиспользуем

3. изменённый диапазон не переиспользуем

4. тип запрошенного элемента должен совпадать: токен или node

Diagnostics и skipped text

Если старый парсер что-то восстановил через diagnostics, такой узел лучше разобрать заново. В IDE пользователь часто печатает код в невалидном состоянии. Если мы начнём агрессивно переиспользовать сломанные куски, можно зафиксировать старую ошибку и не увидеть, что пользователь её уже исправил.

Проверка выглядит так:

private static bool ContainsDiagnosticsOrSkippedText(GreenNode node)
{
    if (node.Kind == SyntaxKind.InlineExpressionSyntax)
    {
        return ContainsInvalidInlineExpression(Unsafe.As<GreenInlineExpressionSyntax>(node));
    }

    if (node.Kind is SyntaxKind.CSharpExpressionSyntax or
        SyntaxKind.CSharpTypeSyntax or
        SyntaxKind.CSharpParameterListSyntax or
        SyntaxKind.CSharpArgumentListSyntax)
    {
        return false;
    }

    if (node.ContainsSkippedText)
    {
        return true;
    }

    if (!node.ContainsDiagnostics)
    {
        return false;
    }

    return ContainsDiagnosticsOrSkippedTextSlow(node);
}

Здесь есть важное исключение для C# raw nodes. Akbura хранит C# fragments как CSharpRawToken / CSharpExpressionSyntax / CSharpTypeSyntax. Внутри них могут быть Roslyn diagnostics, но на уровне Akbura это не всегда значит, что нужно запретить reuse. Семантическая проверка C# будет отдельной историей.

Режим лексера

Ещё один инвариант — режим лексера.

Akbura-парсер постоянно переключает лексер:

1. TopLevel
2. InAkcss
3. InInlineExpression
4. InExpressionUntilSemicolon
5. InTypeName
6. InCSharpParameterList
...

Один и тот же текст может читаться по-разному в разных режимах. Например, внутри C# expression лексер не должен читать Akbura markup как обычный top-level member. Поэтому блендер принимает Lexer.LexerMode mode в каждом чтении:

public BlendedNode ReadToken(Lexer.LexerMode mode)

Если нужно fallback-нуться на свежий токен, reader вызывает лексер именно в этом режиме:

var token = _lexer.Lex(mode);

Подключаем блендер к парсеру

Теперь нужно встроить блендер в парсер. В обычном режиме парсер работает как раньше. В инкрементальном режиме он получает старое дерево и changes.

Конструктор выглядит так:

public Parser(
    Lexer lexer,
    CancellationToken cancellationToken,
    AkburaDocumentSyntax? oldTree,
    IEnumerable<TextChangeRange>? changes)
    : this(lexer, cancellationToken)
{
    if (oldTree == null)
    {
        return;
    }

    _isIncremental = true;
    _blender = new Blender(lexer, oldTree, changes);
    _blendersBeforeToken = s_blendersBeforeTokenPool.Allocate();
}

Если oldTree == null, парсер остаётся обычным.

В обычном парсере пайплайн токена примерно такой:

CurrentToken / PeekToken => cached token array => lexer.Lex(mode)
EatToken                => consume current token
ReturnToken             => откатить token offset и TextWindow

В инкрементальном источник токенов меняется. Новый токен приходит через блендер:

private void AddNewBlendedToken()
{
    var beforeToken = _blender;
    var blended = _blender.ReadFreshToken(_mode);
    _blender = blended.Blender;

    AddLexedToken((GreenSyntaxToken)blended.Token.RequiredNode);
    _blendersBeforeToken![_tokenCount - 1] = beforeToken;
}

Здесь сохраняется блендер перед чтением токена. Это нужно для ReturnToken.

ReturnToken

Парсер иногда заглядывает вперёд, потом понимает, что пошёл не туда, и возвращает токен назад. В обычном режиме можно откатить TextWindow. В инкрементальном режиме нужно откатить ещё и блендер стейт.

Поэтому перед каждым токеном хранится блендер:

private static readonly ObjectPool<Blender[]> s_blendersBeforeTokenPool =
    new(() => new Blender[CachedTokenArraySize]);

private Blender[]? _blendersBeforeToken;

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

FastPeekToken

Ещё одна похожая деталь — fast peek.

В обычном режиме можно быстро посмотреть следующий токен через лексер и вернуть TextWindow назад. В инкрементальном режиме нужно сделать то же самое, но через блендер:

private GreenSyntaxToken FastPeekBlendedToken()
{
    var savedPosition = _lexer.TextWindow.Position;
    var blended = _blender.ReadFreshToken(_mode);
    _lexer.TextWindow.Reset(savedPosition);
    return (GreenSyntaxToken)blended.Token.RequiredNode;
}

Блендер сам здесь не сохраняется в парсере, потому что метод только смотрит. Важно вернуть TextWindow, потому что ReadFreshToken может сходить в лексер.

Постепенный инкрементальный парсинг

Самый простой способ начать инкрементальный парсинг, это переиспользовать только top-level members.

Например:

using System;
state int count = 0;
<TextBlock Text="Hello"/>

Если изменился только count, то using System; и markup root можно переиспользовать целиком. Это уже даёт выигрыш на больших файлах.

В парсере это выглядит так:

private bool TryEatReusableTopLevelMember(out GreenAkTopLevelMemberSyntax member)
{
    member = null!;

    if (!CanReadIncrementalNodeOrToken())
    {
        return false;
    }

    var blended = _blender.ReadNode(_mode);
    if (blended.Node is not AkTopLevelMemberSyntax node ||
        !CanReuseTopLevelMember(node.Green))
    {
        return false;
    }

    _blender = blended.Blender;
    _prevTokenTrailingTrivia = ((GreenSyntaxToken?)node.Green.GetLastTerminal())?.GetTrailingTrivia();
    member = node.Green;
    return true;
}

Это первая большая победа: парсер может не читать токены для целой top-level конструкции.

Но потом быстро становится понятно, что переиспользовать только top-level мало. Если изменился атрибут внутри большого markup root, весь root будет пересобран. Поэтому следующий шаг это икрементальный парсер для отдельных конструкций.

State

state небольшой, и его удобно сделать инкрементальным на уровне слотов:

state int count = 0;

Если изменилось только имя, можно переиспользовать keyword, type, equals, initializer и semicolon.

private bool TryParseIncrementalStateDeclaration(out GreenStateDeclarationSyntax state)
{
    state = null!;

    if (!CanReadIncrementalNodeOrToken() ||
        !TryReadIncrementalToken(SyntaxKind.StateKeyword, out var stateKeyword))
    {
        return false;
    }

    var type = ParseIncrementalCSharpTypeOrNull();
    var name = ParseIncrementalIdentifierName();
    var equals = ReadRequiredIncrementalToken(SyntaxKind.EqualsToken);
    var initializer = ParseIncrementalStateInitializer();
    var semicolon = ReadRequiredIncrementalToken(SyntaxKind.SemicolonToken);

    state = GreenSyntaxFactory.StateDeclarationSyntax(
        stateKeyword,
        type,
        name,
        equals,
        initializer,
        semicolon);
    return true;
}

Здесь каждый кусок сам пытается reuse-иться. Если не получилось, читается свежий токен.

Command и inject

command и inject устроены так же:

inject ILogger<DashboardPage> log;
command Task Refresh(int userId);

Для них инкрементальный парсер читает отдельные slots:

keyword
type / return type
name
parameters
semicolon

C# parts пока можно парсить грубо: если C# type или parameter list изменились, пересобрать этот кусок через Roslyn SyntaxFactory.Parse.... Главное, что Akbura-обвязка уже умеет реюзить соседние части.

Markup

Markup даёт самый большой выигрыш.

Представим большой компонент:

<StackPanel class="card" gap-4 p-4>
    <TextBlock Text="Dashboard"/>
    <Input bind:Value={Search}/>
    <Button OnClick={count++}>Open</Button>
    <TaskList Items={tasks}/>
</StackPanel>

Если пользователь поменял Dashboard на Tasks, full reparse пересоберёт весь root. Инкрементальный парсер может пересобрать только attribute value или text literal, а соседние attributes и child elements взять из старого дерева.

Поэтому инкрементальный парсер markup работает на нескольких уровнях:

MarkupRootSyntax
MarkupElementSyntax
MarkupStartTagSyntax
MarkupEndTagSyntax
MarkupAttributeSyntax
MarkupContentSyntax
InlineExpressionSyntax

На каждом уровне парсер сначала пробует reuse-ить старый node:

if (TryReadReusableIncrementalNode<GreenMarkupElementSyntax>(out var element))
{
    return element;
}

Если node пересекается с changed range, парсер идёт глубже и собирает его из частей. Так outer element может быть новым, но его неизменённые child attributes или body items останутся старыми объектами.

Именно поэтому benchmark по markup выглядит особенно хорошо: большой markup root содержит много независимых children, и изменение одного attribute не требует пересобирать весь список.

Inline Akcss

Inline Akcss тоже хорошо ложится на инкрементальную модель:

@akcss {
    .card {
        Background: White;
    }

    @utilities {
        .gap-(double value) {
            RowGap: value * Spacing;
        }
    }
}

Там есть top-level members, body members, selectors, utility parameters и assignments. Всё это похоже на маленький отдельный язык внутри Akbura.

Инкрементальный парсер для Akcss использует тот же принцип:

попробовать reusable node
если не получилось, разобрать children
C# expressions внутри assignments читать отдельным helper-ом

Здесь важно не забывать переключать режим лексера в InAkcss, иначе @if, .card, utility selectors и обычная Akbura top-level grammar начнут мешать друг другу.

CSharpBlockSyntax

C# blocks в Akbura необычные. Внутри блока может быть обычный C# statement и markup:

if(isOpen)
{
    Console.WriteLine("Panel opened");
    <TextBlock Text="Opened!"/>
}

Поэтому CSharpBlockSyntax хранит список AkTopLevelMember, а не просто C# tokens.

Для инкрементального парсинга первая версия делает простые случаи:

если изменился один raw C# token, пересобрать только его
если изменился nested markup, дать markup инкрементальному парсеру сделать свою работу
если блок не затронут, переиспользовать его целиком

C# parts сложнее, потому что внутри сидит Roslyn. Идеально хотелось бы попросить Roslyn репарснусть кусок syntax node с TextChangeRange. Но такого публичного удобного API для общего случая нет. Поэтому на первом этапе достаточно аккуратно обновлять raw-токен и не пытаться угадать все C# grammar cases. Сначала думал что мне поможет SyntaxTree.WithChangedText(SourceText), но увы и ах, так как CSharp блоки у нас не полноценное синтаксическое дерево, то каждый раз создаеться лениво новое, и судя по бенчмаркам если использвать метод SyntaxTree.WithChangedText(SourceText), это будет медленее на 20%, чем просто полный репарс всего кода.

Тесты

Для блендера тесты нужны на нескольких уровнях.

Первый уровень это Cursor.

Cursor должен правильно ходить по дереву:

var cursor = new Blender.Cursor(root);
var first = cursor.MoveToFirstChild();

Проверяется, что он попадает в нужные node или токен, пропускает zero-width элементы и умеет переходить к sibling.

Второй уровень это Reader.

Например, без изменений reader должен брать tokens из старого дерева:

const string code = "state count = 0;";
using var lexer = new Lexer(SourceText.From(code));
var oldTree = ParseRoot(code);
var blender = new Blender(lexer, oldTree, changes: null);

var first = blender.ReadToken(Lexer.LexerMode.TopLevel);

Assert.Null(first.Node);
Assert.Equal(SyntaxKind.StateKeyword, first.Token.Kind);
Assert.Equal("state ", first.Token.ToFullString());

А внутри changed range он должен читать свежий токен:

const string oldCode = "state count = 0;";
const string newCode = "param count = 0;";
var change = new TextChangeRange(
    new TextSpan(0, "state".Length),
    "param".Length);

var blender = new Blender(lexer, oldTree, [change]);
var first = blender.ReadToken(Lexer.LexerMode.TopLevel);

Assert.Equal(SyntaxKind.ParamKeyword, first.Token.Kind);

Третий уровень это тесты парсера.

Самые важные проверки:

Assert.Equal(code, syntax.ToFullString());
Assert.Equal(code.Length, syntax.FullWidth);

ToFullString() ловит потерю текста. FullWidth ловит сдвиги cursor-а и неправильный учёт ширины. Это оказалось очень полезно: такие проверки сразу нашли несколько мест, где generated nodes или raw tokens неверно считали ширину.

Ещё один важный тест — realistic invalid multi-edit.

Сценарий примерно такой:

oldCode корректный
newCode содержит несколько изменений
часть изменений делает код невалидным
инкрементальный парсер должен сохранить весь текст
и переиспользовать большую часть старого дерева

В этом тесте одновременно затрагиваются:

переименование символа
большая вставка
удаление валидной секции
удаление секции так, чтобы синтаксис стал инвалидным
вставка инвалидного кода
markup
akcss
CSharpBlockSyntax
raw C# fragments

Проверка reuse выглядит по смыслу так:

var treeReuseRatio = GetReusableSyntaxNodeRatio(oldSyntax, incremental);
Assert.True(treeReuseRatio >= 0.95);

Это не значит, что каждое изменение всегда будет переиспользовать 95% дерева. Это конкретный большой реалистичного кейса, где большая часть файла не менялась. Для него такой порог полезен: если случайно сломать reuse и начать пересобирать всё дерево, тест сразу упадёт.

Бенчмарки

Без бенчмарка инкрементальный легко обмануть. Можно написать очень умный код, который переиспользует дерево, но тратит столько времени на поиск переиспользуемых нод, что полный репарсинг окажется быстрее.

Так и было на промежуточных версиях. Особенно с C# blocks: инкрементальный парсер сначала оказался медленнее полного репарсинга. Причина была в лишнем обходе дерева и слишком дорогой проверке переиспользуемых нод.

После оптимизаций “реалистичный” бенчмарк стал выглядеть куда приятнее:

Method	Mean	Error	StdDev	Ratio	RatioSD	Gen0	Gen1	Allocated	Alloc Ratio
FullReparseAfterRealisticInvalidEdit	16,456.2 us	242.01 us	202.09 us	1.00	0.02	1062.5000	375.0000	6790.3 KB	1.00
IncrementalParseAfterRealisticInvalidEdit	293.7 us	2.54 us	2.49 us	0.02	0.00	23.9258	3.9063	153.69 KB	0.02

То есть инкрементальный парсер в этом сценарии примерно в десятки раз быстрее и сильно меньше аллоцирует.

Markup benchmark особенно показательный:

Method	ChildCount	Mean	Error	StdDev	Ratio	RatioSD	Gen0	Gen1	Gen2	Allocated	Alloc Ratio
FullParseAfterMarkupEdit	40	1,019.04 us	20.167 us	39.808 us	1.00	0.05	68.3594	17.5781	0.9766	495.04 KB	1.00
IncrementalParseAfterMarkupEdit	40	34.20 us	0.446 us	0.395 us	0.03	0.00	9.3994	1.1597	-	57.87 KB	0.12
FullParseAfterMarkupEdit	200	6,230.84 us	116.679 us	204.354 us	1.00	0.05	39.0625	15.6250	7.8125	2411.15 KB	1.00
IncrementalParseAfterMarkupEdit	200	80.32 us	1.592 us	2.911 us	0.01	0.00	15.8691	1.7090	-	97.94 KB	0.04
FullParseAfterMarkupEdit	1000	26,286.78 us	355.715 us	315.332 us	1.00	0.02	218.7500	125.0000	93.7500	11686.09 KB	1.00
IncrementalParseAfterMarkupEdit	1000	342.71 us	6.809 us	16.573 us	0.01	0.00	46.8750	6.8359	-	291.11 KB	0.02

Там выигрыш огромный, потому что markup дерево широкое: много атрибутов, много детей, много независимых элементов. Блендер и инкрементальный парсер как раз хорошо работают на таких структурах.

C# block benchmark скромнее. Это ожидаемо. C# raw fragments хуже подходят для slot-level reuse, потому что внутри них спрятан другой язык. Но даже там удалось сделать инкрементальный парсер быстрее full reparse в больших сценариях.

Method	StatementCount	Mean	Error	StdDev	Median	Ratio	RatioSD	Gen0	Gen1	Allocated	Alloc Ratio
FullParseAfterCSharpBlockEdit	40	32.59 us	0.640 us	0.978 us	32.08 us	1.00	0.04	9.4604	2.5024	58.17 KB	1.00
IncrementalParseAfterCSharpBlockEdit	40	13.62 us	0.258 us	0.241 us	13.53 us	0.42	0.01	6.9885	0.8698	42.93 KB	0.74
FullParseAfterCSharpBlockEdit	200	113.77 us	2.267 us	4.029 us	112.48 us	1.00	0.05	17.8223	1.4648	110.42 KB	1.00
IncrementalParseAfterCSharpBlockEdit	200	37.00 us	0.721 us	1.011 us	36.59 us	0.33	0.01	7.9346	0.9766	48.79 KB	0.44
FullParseAfterCSharpBlockEdit	1000	493.72 us	9.835 us	15.312 us	485.26 us	1.00	0.04	69.3359	28.3203	432.38 KB	1.00
IncrementalParseAfterCSharpBlockEdit	1000	149.73 us	2.957 us	4.859 us	147.43 us	0.30	0.01	11.9629	1.4648	74.15 KB	0.17

Итог

В этой части появился первый настоящий слой инкрементального парсера.

Мы добавили Blender, который умеет смешивать старое синтаксическое дереов и свежие токены из лексера. Добавили Cursor, который ходит по старому дереву через SyntaxNodeOrToken. Добавили Reader, который учитывает TextChangeRange, _changeDelta, changed ranges и правила безопасного reuse.

После этого парсер получил инкрементальный конструктор и начал читать токены через блендер. Сначала реюз был только на top-level members, потом появились более мелкие инкрементальный парсер для state, command, inject, markup, inline Akcss и CSharpBlockSyntax.

Следующий шаг — семантика. Syntax tree уже есть, инкрементальный парсинг уже работает, текст сохраняется через ToFullString(), ширина контролируется через FullWidth, а парсер умеет жить в IDE-режиме. Теперь можно начать отвечать на вопросы посложнее: что означает state, как связывается bind, как найти компонент, как проверить command, и как всё это превратить в рабочую модель языка. И как это еще все связать с кусками c# кода.