Почему "+=" сложнее реализовать, чем "+": опыт HydraScript

Мой язык программирования HydraScript, написанный на C#, уже умел выполнять такой код:

let x = 10
x = x + 1
>>> x

Получаем 11. >>> — это оператор вывода. Присваивание работает, сложение работает. Захотелось добавить привычное сокращение:

let x = 10
x += 1
>>> x

Результат должен остаться тем же — 11. Зачем учить весь компилятор ещё одной операции, если всё необходимое у него уже есть? Можно прямо в парсере превратить x += 1 в дерево для x = x + 1.

Эта часть уместилась в несколько строк. Основная работа досталась методу Clone().

Откуда берётся второй x

В записи x = x + 1 парсер встречает x дважды и создаёт два узла. Переменная одна, но места в абстрактном синтаксическом дереве разные:

Цель присваивания в HydraScript представлена узлом MemberExpression. У обычной переменной цепочка обращений к членам пуста, а для чтения внутри сложения достаточно IdentifierReference.

В записи с += у меня всего один x. Второе вхождение, из которого будет читаться значение, нужно создать самостоятельно. Такое преобразование называют desugaring: удобный синтаксис разворачивается в конструкции, которые компилятор уже поддерживает.

Лексер объединяет операторы присваивания под токеном Assign, поэтому изменение остаётся в разборе присваивания:

var assign = Expect("Assign");
var source = assign.Value is "="
    ? Expression()
    : new BinaryExpression(
        lhs.Empty() ? lhs.Id.Clone() : lhs.Clone(),
        assign.Value[..^1],
        Expression());
return new AssignmentExpression(lhs, source)
    { Segment = assign.Segment };

Отбрасываем последний = и получаем бинарный оператор. Это работает и для ++=, который в HydraScript превращается в ++. Одним преобразованием закрываем сразу несколько операторов.

А теперь уберите отсюда Clone() — и вся идея развалится.

Один узел, два родителя

Самое очевидное решение — передать одну и ту же левую часть в оба выражения. Вот так делать нельзя:

var source = new BinaryExpression(lhs, "+", rhs);
var assignment = new AssignmentExpression(lhs, source);

C# ничего против не имеет. Зато у моего AST есть правило: у узла не может быть двух родителей.

public IAbstractSyntaxTreeNode? Parent { get; internal set; }

Конструкторы выражений устанавливают эту связь, когда присоединяют дочерние узлы. В неправильном варианте сначала lhs забирает себе бинарное выражение. Затем присваивание перезаписывает lhs.Parent. Если идти вниз по дочерним узлам, lhs окажется в обеих ветвях. Если подняться от него к родителю, обратный путь останется только для одной.

И дело не только в красоте графа объектов. Узлы получают область видимости от родителя:

Scope = Parent?.Scope ?? Scope.Empty;

Метод ChildOf<T>() тоже ищет нужный узел вверх по этим ссылкам. Последующие проходы рассчитывают, что узел знает своё место в дереве.

Если переиспользовать только lhs.Id, ничего не изменится: идентификатор уже принадлежит MemberExpression из цели присваивания. Для каждого вхождения x нужен отдельный синтаксический объект, хотя оба в итоге будут ссылаться на одну переменную.

Копирование быстро становится рекурсивным

У идентификатора копировать особо нечего:

public override IdentifierReference Clone() => new(Name);

Сложности начинаются с того, что может оказаться внутри цели присваивания. Индекс массива бывает сложением, вызовом функции или ещё одним обращением к члену. Новый внешний объект с общими дочерними узлами оставит тот же конфликт владельцев на уровень глубже.

Поэтому Clone() появился в контракте Expression:

public abstract Expression Clone();

Каждое выражение само знает, как воссоздать свой синтаксис. Например, BinaryExpression:

public override BinaryExpression Clone() =>
    new(Left.Clone(), Operator, Right.Clone());

Собирать копию через конструкторы удобно: они уже умеют связывать дочерние узлы с новым родителем. У вызовов подход тот же — копируются выражение обращения к члену и аргументы.

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

За целью присваивания прячется целая цепочка

Теперь возьмём такое выражение:

obj.arr[index].x += 1

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

MemberExpression.AccessChain — это LinkedList<AccessExpression>. Учесть нужно две системы связей: связи самого списка и отношения между объектами AST, которые в нём лежат. Для AccessExpression предыдущее обращение одновременно является родителем:

public AccessExpression? Prev => Parent as AccessExpression;

protected AccessExpression(AccessExpression? prev)
{
    if (prev is not null)
    {
        Parent = prev;
        prev.Next = this;
    }
}

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

Для обращения по индексу это выглядит так:

public override IndexAccess Clone() =>
    new(Index.Clone(), Prev?.Clone());

DotAccess делает то же самое для идентификатора свойства. Рекурсивный вызов сначала воссоздаёт предшественника, поэтому конструктор получает уже новый узел, к которому можно присоединиться. К моменту возврата из клонирования хвоста новая цепочка обращений уже готова.

Остаётся собрать эти узлы в список внутри MemberExpression.Clone():

public override MemberExpression Clone()
{
    var clonedAccessChain = new LinkedList<AccessExpression>();
    var clonedTail = AccessChain.Last?.Value.Clone();
    while (clonedTail != null)
    {
        clonedAccessChain.AddFirst(clonedTail);
        clonedTail = clonedTail.Prev;
    }
    return new MemberExpression(Id.Clone(), clonedAccessChain);
}

Рекурсия и цикл здесь решают разные части задачи. Рекурсия создаёт узлы и их связи, цикл собирает их в контейнер. Поскольку идём от хвоста, AddFirst сохраняет исходный порядок обращений. Если ещё раз вызывать клонирование внутри цикла, получим лишние копии предшественников.

Новый MemberExpression становится родителем скопированного корневого идентификатора и первого обращения. Теперь все связи остаются внутри своей копии выражения.

Для проверки такого копирования пригодился Graphviz: можно сравнить представления деревьев, предварительно убрав идентификаторы узлов, а отдельно проверить ссылки. Представленный синтаксис должен пережить копирование, а объекты, которым он принадлежит, — стать независимыми.

Вернёмся к дополнительному знаку равенства

После всей этой работы с деревом пользователь языка получает следующее:

let obj = { arr: [{ x: 10; }]; }
let index = 0
obj.arr[index].x += 1
>>> obj.arr[index].x

Выведется 11.

Семантический анализатор и генератор инструкций получают знакомые узлы присваивания и бинарного выражения. Для проверки типов и генерации инструкций подходят уже существующие обработчики.

Именно поэтому я и начал с x = x + 1: большая часть реализации уже была готова. Не хватало способа поставить цель присваивания в два места так, чтобы две ветви не делили один объект. Ради сокращённой записи в языке пришлось сделать полноценное клонирование дерева выражений.

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

Ещё я веду Telegram канал StepOne, куда выкладываю много интересного контента о программировании на C#, даю карьерные советы, рассказываю истории из личного опыта и раскрываю все тайны IT‑индустрии!