Обзор архитектуры SOOT

Оглавление

• Обзор архитектуры SOOT
  • Оглавление
  • Введение
  • Происхождение
  • Система типов и интерпретатор
  • Метапрограммирование
  • Виртуальная машина
    • Устройство виртуальной машины
  • Формат файла
  • Итог

Введение

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

Название SOOT («сажа») расшифровывается как Scriptable Object-Oriented Toolkit — отражает характер проекта. Он развивался неровно и далёк от совершенства тех систем, которые его вдохновили: OpenGOAL и скриптовых систем Naughty Dog. В этом смысле его можно назвать грязным, но без негативной коннотации. Зато он честный: это попытка сделать своё, по собственным принципам, изучая чужие решения и открытый код и не перенося чужой проект целиком. Отсюда и название: работа грязная, но честная. Виртуальная машина называется Carbon («углерод»), чтобы отличать её от компилятора. Названия связаны по смыслу: сажа состоит в основном из углерода.

Независимость проекта. SOOT — самостоятельный проект. Он не связан с Naughty Dog, Sony Interactive Entertainment и авторами OpenGOAL. Это не копия и не форк чужого проекта: архитектура и реализация разработаны мной, а идеи основаны на публично доступных материалах (докладах, статьях, документации) и на изучении открытого кода OpenGOAL. В отдельных местах используются фрагменты кода OpenGOAL, который распространяется как открытый проект. Названия игр и проектов принадлежат их правообладателям и упоминаются только для того, чтобы объяснить источники вдохновения. Прямая совместимость с этими проектами не является целью SOOT.

Происхождение

Проект начался с идеи сделать компилятор для игровой разработки. К тому времени я уже изучила значительный объём публично доступных материалов о скриптовых системах в играх Naughty Dog. Из этих материалов следовало, что в ранних играх студии использовался Lisp-подобный язык со своим подходом к компиляции игрового кода, а в более поздних проектах скрипты исполнялись на виртуальной машине, которая давала контроль над исполнением.

Проект SOOT запускался несколько раз на разных языках программирования. Каждый раз, когда уже был какой-то результат, он упирался в очередной крупный рефакторинг, на который не хватало сил и времени, и работа полностью останавливалась.

Система типов и интерпретатор

Отдельный этап — система типов. Это низкоуровневая библиотека, которая хранит метаинформацию о типах и наследовании. Её основные принципы согласуются с подходами, публично описанными для GOAL и OpenGOAL, но реализация моя собственная.

Систему типов я писала несколько раз: на Racket, Common Lisp и Go. Версия на Go оказалась самой удачной с практической точки зрения и была использована в коммерческих проектах. Она заметно отличается от остальных версий, потому что предназначена для сетевого взаимодействия проекта на Unity с backend на Linux.

После этой работы получилось сделать несколько выводов:

• Программирование на Common Lisp оказалось самым комфортным, а время разработки на нём минимальным.
• Go по комфорту и темпу разработки был очень близок к Common Lisp.
• Работа на Racket оказалась не слишком продуктивной: много багов, несовершенная документация, и отсутствие поддержки.

Спустя какое-то время, проанализировав результаты, я решила написать интерпретатор Lisp с нуля. Я хотела пройти этот путь самостоятельно и разобраться, как всё работает, опираясь только на публичные описания. Поэтому скриптовый Lisp в SOOT — собственная реализация, и она заметно отличается от других известных реализаций. Отладка местами была достаточно сложной.

После этого версию на Go я переписала на C++, и она стала ближе к той системе типов, которая нужна компилятору.

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

Метапрограммирование

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

После этого проект снова был заморожен. Через какое-то время метапрограммирование было удалено из интерпретатора, а компилятор переписан на C++. Интерпретатор и система типов при этом сохранились в том виде, в котором они уже были реализованы.

Виртуальная машина

Здесь SOOT заметно расходится с OpenGOAL. Насколько известно из публичных описаний, компилятор GOAL и OpenGOAL порождает код для процессора, то есть машинный код для конкретных платформ. SOOT генерирует код для виртуальной машины по трём причинам:

1. Это проще.
2. Из публичных докладов Naughty Dog известно, что в более поздних проектах студии скрипты исполнялись на виртуальной машине, и этот вариант показался мне самым привлекательным.
3. Код виртуальной машины потом легче транслировать в код для конкретного процессора.

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

Виртуальная машина SOOT вдохновлена подходом, описанным в публичных материалах о скриптовой системе The Last of Us (TLOU), но является самостоятельной разработкой. Цели воспроизвести ту систему не было, поэтому отличия существенные. Насколько можно судить по публичным описаниям, они такие:

• В TLOU используется чисто процедурное программирование, а в SOOT есть ещё и объектно-ориентированное.
• В TLOU данные (структуры) и исполняемая логика (state-script, то есть скрипты, описывающие конечные автоматы) чётко разделены. Декларации state-script организованы в динамическом стиле, как список имён и значений, а доступ к полям идёт через нативные функции get и set. Нативные функции расширяют язык и написаны на C++, например print и format. В SOOT state-script компилируются в структуры, а доступ к полям выполняется по смещениям.

Устройство виртуальной машины

Код операции занимает один байт. Остальные 24 бита отведены под операнды (два или три, в зависимости от инструкции), поэтому все инструкции имеют фиксированный размер 32 бита. Это трёхоперандная виртуальная машина: её инструкции работают с виртуальными регистрами, расположенными в stack frame.

• Каждый StackFrame имеет указатель на родительский, и кадры образуют дерево.
• StackFrame имеет фиксированный размер, поэтому его удобно размещать в пуле объектов (object pool).
• Каждый StackFrame хранит состояние исполнения виртуальной машины, поэтому одновременно служит и замыканием (closure), и продолжением (continuation).

Формат файла

Файл содержит заголовок и перечень дефиниций, у каждой из которых есть имя и тип. Структура формата концептуально напоминает бинарные скриптовые файлы, о которых рассказывают публичные материалы по играм Naughty Dog, но формат SOOT собственный и совместимости с ними не предполагает.

Кроме того, файл хранит информацию о каждом типе: имена полей, отступы и размеры структур, таблицы vtable и states. Говорить, хорошее ли это решение, пока рано. Зато оно оказалось проще: к тому моменту компиляция структур и их методов уже существовала, и state-script стал одним из вариантов структур.

Имена и имена типов представлены в файле значениями CRC64, а соответствующие им строки сохраняются в отдельный sidbase-файл. Среди дефиниций могут быть lambda-функции, типы, конечные автоматы, экземпляры структур и другие сущности. В конце файла находятся строковые литералы и неименованные экземпляры структур. Локальные литералы сохраняются в конце каждой lambda-функции.

Итог

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

Компилятор SOOT адаптирован под собственную виртуальную машину и под исполнение её кода в игровом движке. Такой вариант даёт контроль над исполнением кода и оставляет возможность в дальнейшем транслировать его в код конкретного процессора: во время работы программы или статической кросс-компиляцией.

Кроме того, компилятор SOOT сочетает объектно-ориентированное программирование и высокоуровневые конструкции вроде state-script для описания игровой логики. Язык ориентирован на программирование анимации.

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