Variant: универсальный контейнер данных виртуальной машины

Введение

Виртуальная машина SOOT использует стековые фреймы фиксированного размера. Внутри фрейма лежат виртуальные регистры, и каждый регистр — это контейнер Variant, который умеет хранить значение одного из поддерживаемых типов. Эта статья объясняет, почему он устроен именно так и почему типов в нём так мало.

Контейнер на основе union

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

Variant — это как раз такая пара: однобайтовый тег типа плюс анонимный union из трёх вариантов (i64, f64 и void *). С учётом выравнивания на 64-битной платформе контейнер занимает 16 байт. Класс служит оболочкой: он инкапсулирует конструкторы, проверки и преобразования, чтобы весь остальной код не работал с union напрямую. То же самое можно было сделать и без класса, но с ним код проще читать.

Главный вопрос в другом: какие типы должен знать такой контейнер.

Какие типы поддерживать

Сначала я хотела хранить тип в виде CRC32 или CRC64 от его имени. Тогда указатель мог бы нести тип объекта, на который он указывает, а набор типов был бы открытым: добавить новый тип можно, не меняя сам контейнер. Идея казалась изящной, но на практике оказалась тупиковой.

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

Какое-то время система работала именно так. Пройдя этот путь, я сократила количество типов до минимума. Но и минимум пришлось определять осознанно.

Суррогатные типы: идея и отказ от неё

На следующем этапе в контейнере остались типы, которые нужны не вычислениям, а людям: булево значение, идентификатор строки (StringId) и строка. Инструкций для них в виртуальной машине нет. Это «суррогатные» типы: они производны от целого числа или указателя и существуют ради удобства.

Идея не глупая. Когда скрипт возвращает значение в терминал, true и false читаются лучше, чем 1 и 0, строка лучше, чем адрес в памяти, а исходная строка лучше, чем 64-битный хэш. Тег в контейнере давал эту информацию бесплатно.

Но у неё есть изъян: система команд не гарантирует, что тег будет выставлен правильно в ста случаях из ста. Тег String ставится, когда строка загружена из константной области. Но стоит сохранить её в поле структуры и прочитать обратно обычной командой чтения, и в регистре снова окажется простой указатель: команда не знает, что в поле строка. Результат команды сравнения остаётся обычным целым числом, то есть булевым значением он становится только там, где его явно создал нативный код. Идентификатор строки, полученный как результат вычисления, остаётся просто целым числом.

В итоге тип устанавливается в одних случаях и не устанавливается в других. Такая полумера хуже отсутствия типа, потому что вводит в заблуждение: глядя на значение без тега, никто не знает, булево оно или нет, а глядя на значение с тегом, думаешь, что на него можно положиться.

Исправить это можно было бы двумя способами. Первый: ввести в процессор команду «установить тип регистра», тогда сначала загружается значение, а потом ему назначается тип. Это возвращает динамическую типизацию по частям: теги приходится поддерживать везде, а код усложняется. Второй: размножить инструкции, чтобы каждая, которая может положить строку или булево значение в регистр, имела отдельный вариант. Набор команд разрастается, а виртуальная машина усложняется. Оба пути противоречат главной идее проекта: простое решение там, где сложное не окупается.

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

Три типа регистра

Сейчас Variant различает три типа (RuntimeType):

Тип	Что хранится	Примечание
`Int`	знаковое 64-битное целое	сюда относятся булевы значения, символы (`char`) и `StringId`
`Float`	64-битное число с плавающей точкой	значения `f32` при записи расширяются
`Pointer`	указатель на что угодно	тип объекта в нём не хранится; пустое значение — нулевой указатель

Принцип такой: тип живёт в коде, а не в данных. Регистр не знает, что в нём лежит булево значение или идентификатор строки. Это знают инструкции и компилятор. Когда функция проверяет значение на истинность, она проверяет целое число. Когда нативной функции передан StringId, она по своей сигнатуре интерпретирует целое как идентификатор. С указателем на строку то же самое.

Так работают и сами процессоры, и многие виртуальные машины: регистры не размечены, а правильность использования обеспечивает компилятор.

Как показывать значения в терминале

Отказ от суррогатных типов бьёт по отладке: вместо true в терминале теперь 1. Эту потерю можно в основном вернуть на стороне инструментов, не усложняя виртуальную машину.

Статические типы от компилятора. Язык строго типизирован, и компилятор знает тип каждого регистра в каждой точке функции. Эти сведения можно записывать в необязательную отладочную таблицу (регистр, диапазон инструкций, тип), которая в релизной сборке не включается. В REPL всё ещё проще: компилятор знает тип выражения, которое он только что скомпилировал, и результат можно сразу напечатать как true, а не как 1. Типы аргументов нативных функций уже описаны в их сигнатурах.
Предположения для значений без типа. Если типа нет (например, при просмотре сырых регистров), терминал может показать значение вместе с трактовками: 1 (bool: true). Для StringId это надёжно: значение либо находится в таблице строковых идентификаторов, либо нет, а случайное совпадение 64-битного хэша практически невозможно.
Строки. Указатель, лежащий в строковой области модуля или в блоке кучи с заголовком типа строки, можно показать как строку, не добавляя тега в регистр.

Эти механизмы живут в инструментах разработки. Виртуальной машине они ничего не стоят.

Указатели и сборщик мусора

Тип Pointer может указывать на что угодно, и сам контейнер не знает, управляется ли объект сборщиком мусора. Для этого, как рассказано в статье о памяти, у менеджера есть простой предикат: он проверяет, входит ли адрес в единый регион кучи.

Variant не владеет памятью. Его деструктор пуст, копирование поверхностное: после копирования два значения указывают на один и тот же объект. Жизнью объектов управляет сборщик.

Из этого следует правило для тех, кто хранит Variant, в первую очередь для стековых фреймов. При маркировке фрейм должен пройти по своим регистрам и вызвать mark_object для каждого указателя. Различать «свои» и «чужие» указатели при этом не нужно: mark_object сам игнорирует адреса вне кучи. Если пропустить регистр, сборщик освободит объект, на который он указывает.

Строгие геттеры и мягкие конвертеры

У Variant два семейства методов для доступа к значению.

Строгие геттеры (get_i64, get_f64, get_ptr и другие) возвращают значение только если тип совпадает. Иначе они выбрасывают TypeError с указанием ожидаемого и фактического типов. Это защитная проверка: она ловит ошибки программиста в нативном коде.

Мягкие конвертеры (to_int, to_float, to_bool, to_string) пытаются привести значение к нужному виду. Целое превращается в число с плавающей точкой, указатель в булево значение (непустой или пустой), любое значение в строку для вывода. to_string удобен для отладки: любой регистр можно напечатать, не зная заранее его тип, причём указатель выводится адресом в шестнадцатеричном виде. То же умеет форматтер fmt, поэтому в логах значения читаются сразу.

Аргументы нативных функций

Регистры виртуального процессора лежат во фрейме подряд. Это позволяет передавать аргументы нативным функциям без промежуточных контейнеров: достаточно указателя на первый регистр с аргументами и их количества. Нативная функция получает вариативный список значений Variant и преобразует их к нужным типам.

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

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

Возможное расширение: тип basic

Для будущих расширений можно добавить ещё один тип. В системе типов есть базовый тип для RTTI (информации о типе в рантайме), он называется basic. Его отличие от обычной структуры в том, что первое поле хранит идентификатор типа объекта. Идея и дерево типов вдохновлены публично описанной системой типов GOAL и OpenGOAL.

Это даёт две возможности:

Доступ к полям по именам. Он полезен для отладочного вывода, логирования и подобия reflection в C++ коде. Обычный доступ к полям из C++ работает и без этого, потому что структуры скриптов компилируются в заголовок C++. Но информация о типе позволяет искать поля по имени.
Полиморфизм в рантайме. Зная тип объекта, можно вызывать методы по индексу. Теоретически это позволяет написать визитёр для любого типа, даже если тот не был известен на этапе компиляции.

Насколько обе возможности нужны в настоящей игре, пока неясно, но потенциал есть. Если это понадобится, указатель на объект basic станет разновидностью Pointer, а не новым типом регистра.

Что стоит знать

to_c_string() возвращает указатель на внутренний буфер потока. Следующий вызов затирает предыдущий результат, поэтому использовать его можно только немедленно.
Pointer не хранит тип объекта. Что лежит по указателю, определяет контекст.
Булево значение — это целое. Всё, что не ноль, считается истиной.

Выводы

Variant я считаю оптимальным решением для виртуальных регистров. Код получается простым и читаемым, switch крошечный, а данные легко просматривать в отладчике. Тот же контейнер хорошо подходит для передачи аргументов в нативные функции.

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

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

Статус проекта

HWW Portfolio

Software and Hardware Developer