Как индексация строк изменила систему типов HydraScript

В HydraScript мне понадобились две привычные операции со строками: получить длину и обратиться по индексу. Массивы уже умели и то и другое. Чтобы научить этому строки, нужно было поправить несколько мест в семантическом анализаторе: каждое по-своему решало, что разрешено делать с типом.

Заодно появился повод разобраться, почему эти правила оказались именно там. Тип строки в интерпретаторе был, а за списком доступных ему операций приходилось идти в обработчики разных выражений. Добавляешь возможность строке, а её поведение собираешь по всему анализатору.

HydraScript — мой интерпретируемый язык, написанный на C#. В нём статическая типизация, поэтому несовместимые операции нужно отсеять до исполнения. Для поддержки text[index] мало достать символ из .NET-строки: анализатор должен понять, допустимо ли выражение и какой у него тип.

Разверните строку пожалуйста

Мне хотелось решить стандартную задачу собеседований на своём языке таким способом:

let str = "string"
let i = ~str - 1
let revStr: string
while (i >= 0) {
    revStr = revStr + str[i]
    i = i - 1
}
>>> revStr

Из непривычного синтаксиса здесь ~ для получения длины и >>> для вывода. У переменных есть значения по умолчанию, поэтому revStr изначально содержит пустую строку. Результат:

gnirts

Индексация строки тоже возвращает строку. Отдельный тип char для такого примера не нужен.

В старом семантическом анализаторе поддерживаемые унарные операции были перечислены явно:

return visitable.Operator switch
{
    "-" when eType.Equals(number) => number,
    "!" when eType.Equals(boolean) => boolean,
    "~" when eType is ArrayType => number,
    _ => throw new UnsupportedOperation(
        visitable.Segment, eType, visitable.Operator)
};

У индексации был собственный пропускной режим:

if (prevType is not ArrayType arrayType)
    throw new NonAccessibleType(prevType);

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

Можно было дописать проверки на строки и получить работающую возможность. Только каждый визитор по-прежнему должен был узнавать конкретные типы и помнить, что они поддерживают. Даже ответ на вопрос «что можно делать со строкой?» требовал экскурсии по анализатору.

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

Интерфейс оператора

Получился такой интерфейс:

public interface IOperator
{
    public IReadOnlyList<string> Values { get; }

    public bool TryGetResultType(
        OperationDescriptor operation,
        out Type resultType);
}

public record struct OperationDescriptor(
    string Operator,
    IReadOnlyList<Type> OperandTypes);

Здесь Type принадлежит системе типов HydraScript, к .NET-рефлексии он отношения не имеет.

От имени IOperator можно ожидать метод, который складывает числа или склеивает строки. Но на этом этапе значений операндов ещё нет. Анализатору достаточно установить, что выражение вида string[number] допустимо и даёт строку. С этой информацией уже можно продолжать проверку выражения, в которое оно вложено.

Отдельная реализация для каждого символа тоже не понадобилась. HydraScript поддерживает для конкатенации строк и +, и ++, поэтому одно правило перечисляет их в Values. Унарные операции, бинарные и индексация укладываются в общий контракт с разным составом операндов.

Это внутренняя точка расширения C#-реализации. Синтаксис для пользовательской перегрузки операторов в HydraScript от появления интерфейса не возникает.

Тип наконец описывает свои операции

С готовыми правилами строковый тип выглядит так:

public sealed class StringType() :
    Type(
        "string",
        [
            default(StringConcatOperator),
            default(LengthOperator),
            default(IndexOperator)
        ])
{
    public static readonly StringType Instance = new();
}

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

Сама регистрация ещё не делает выражение корректным. Наличие + у строки определяет, к какому правилу обратиться. Это правило всё равно должно отвергнуть операнды вроде string + boolean.

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

Реализация IndexOperator

Можно было завести флаг IsIndexable. Первую проверку он бы закрыл, но анализатору всё ещё пришлось бы разбираться с результатом. У строки и массива он по-разному связан с исходным типом.

Для массива результат зависит от типа элемента. Если вернуть анализатору только «да» или «нет», ему снова придётся проверять конкретный тип. Возвращая тип результата, можно вынести правило целиком.

В IndexOperator за совместимость и результат отвечают два фрагмента:

if (operation.OperandTypes is not
    [
        StringType or ArrayType,
        NumberType or NullableType { Type: NumberType }
    ])
    return false;

resultType = operation.OperandTypes[0] switch
{
    StringType => StringType.Instance,
    ArrayType arrayType => arrayType.Type,
    _ => "undefined"
};

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

LengthOperator тоже можно использовать совместно. Строка и массив представлены разными типами, но длина у обоих имеет тип number.

Pattern matching при таком устройстве никуда не исчезает. Меня вполне устраивает небольшой switch, описывающий одну операцию. Не устраивала необходимость разыскивать связанные правила по визиторам каждый раз, когда у типа появлялась новая возможность.

Ошибками по-прежнему занимается анализатор

Переносить весь семантический анализ в систему типов не нужно. Правилу совместимости незачем знать об узлах AST, позициях в исходном коде и оформлении сообщений об ошибках.

Общий алгоритм проверки к этому моменту уже сложился в коде. Визиторы разбирали типы операндов, проверяли допустимость операции и возвращали тип результата, только каждый делал это своим набором if и switch. Когда я стал выносить эти частные случаи, одинаковые шаги стали видны сами собой. IOperator позволил выразить их явно и оставить в визиторе общий порядок проверки.

Визитор бинарного выражения использует новый контракт так:

if (!lType.TryGetOperator(visitable.Operator, out var @operator))
    throw new UnsupportedOperation(
        visitable.Segment, lType, visitable.Operator);

var operation = new OperationDescriptor(
    visitable.Operator,
    OperandTypes: [lType, rType]);

if (!@operator.TryGetResultType(operation, out var resultType))
    throw new IncompatibleTypesOfOperands(
        visitable.Segment,
        left: lType,
        right: rType);

Для двух случаев отказа нужны разные сообщения. Выражение ~42 требует от числа операции, которую оно вообще не поддерживает. У строки индексация есть, но индекс true для неё не подходит. Раздельные поиск и проверка позволяют сохранить это различие.

Визитор также знает, где именно встретилось ошибочное выражение. Этот контекст остаётся под рукой, а передавать участки исходного кода в каждую реализацию оператора не приходится. Визитор индексации устроен аналогично и обращается к prevType.TryGetOperator("[]", ...).

Виртуальной машине тоже нужна реализация

От IOperator анализатор получает тип результата. Для исполнения нужно само значение. Сгенерированная инструкция IndexRead доходит до этой ветки в инструкции Simple виртуальной машины:

"[]" when lValue is string @string =>
    @string.Substring(Convert.ToInt32(rValue), 1),

У оператора длины ~ уже была своя история. Он изначально появился для массивов, которые в виртуальной машине представлены списками List<object>. Анализатор разрешал ~ для ArrayType и определял результат как number. На исполнении достаточно было взять Count:

"~" => ((List<object>)value!).Count,

Когда я добавлял операции со строками, этот же оператор подошёл и для их длины. В системе типов появился общий LengthOperator для строк и массивов, а в виртуальной машине я разделил ветку на два случая: list.Count и @string.Length.

Но в этой реализации пряталась ошибка, общая для обоих случаев. Count и Length возвращают int, а арифметические операции в виртуальной машине приводят операнды к double. Пока длина попадала в арифметику, различие сглаживалось преобразованием. При проверке равенства оно вылезло наружу. Вот пример, на котором обнаружился баг:

let i = 0
const s = "abcdef"
const sLen = ~s
while (i < sLen) {
    if (i + 1 == sLen)
        >>> "i is 5"
    i = i + 1
}

Цикл доходил до конца, но сообщение не появлялось. На последней итерации слева от == получалось 6 в виде double, а справа оставалось 6 в виде int. Виртуальная машина хранила оба значения как object и сравнивала через Equals(lValue, rValue). Для такого сравнения упакованные double и int не равны. При этом условие i == sLen - 1 срабатывало: вычитание тоже возвращало double, и на нужной итерации типы значений совпадали.

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

"~" when value is List<object> list => Convert.ToDouble(list.Count),
"~" when value is string @string => Convert.ToDouble(@string.Length),

После этого пример выводит i is 5; именно такой сценарий стал регрессионным тестом. Для семантического анализатора и до исправления с обеих сторон сравнивались значения типа number. Ошибка была в том, как виртуальная машина представляла эти значения средствами C#. Одного правильного ответа от IOperator для корректного исполнения оказалось недостаточно.

У примера с разворотом строки есть и другое ограничение. Индексация извлекает одну кодовую единицу UTF-16. С ASCII всё получится, но при развороте произвольного Unicode-текста такой цикл может разорвать суррогатную пару или графему. Числовой индекс также может выйти за границы строки.

Стоило ли заводить ещё один интерфейс

Кода стало больше: реализации операторов, регистрации, дескриптор и поиск. Ради того, чтобы спрятать трёхстрочный switch, я бы всё это не затевал.

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

С IOperator я открываю StringType, вижу поддерживаемые семейства операций и перехожу к нужному правилу. Если меняется индексация, я знаю, где искать. Для меня это более убедительная причина завести интерфейс, чем количество веток, которые удалось убрать из визитора.

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