Eliah-Lakhin/script-system-design.md

## script-system-design.md

      
    Raw
  

              script-system-design.md
            
          
    Встраиваемый скриптовый языка для Rust

Компиляторы системных языков программирования, таких как C, С++, D, Rust, порождают ассемблерный код программы, приближенный к вычислительной модели самой системы, на которой выполняется ассемблер. Эти компиляторы способны статически глубоко анализировать исходный код программы, и создают исполняемые модули с минимальными накладными расходами по производительности в сравнении с не-системными языками программирования с более абстрактной вычислительной моделью. Например, в сравнении со скриптовыми языками вроде JavaScript и Python, или в сравнении с классическими JIT-компилируемыми языками, такими как Java и C#.
Системные языки программирования подходят для таких задач, в которых важна вычислительная производительность создаваемой программы. Практическим недостатком системных языков программирования, с точки зрения удобства разработки, является низкая скорость компиляции, поскольку глубокий статический анализ исходного кода это, как правило, ресурсозатратная задача.
Кроме того, бывают такие задачи, в которых часть системы должна быть высокопроизводительной и статически скомпилированной, а другая часть должна быть динамически конфигурируемой в режиме исполнения. Например, движок компьютерной игры должен обладать высокой вычислительной производительностью и минимальными накладными расходами времени исполнения, но пользовтель игры должен обладать возможностью разрабатывать плагины к игре, кодируя их в реальном времени, без необходимости пересборки всей системы компьютерной игры.
На практике эта задача решается с помощью встраиваемых скриптовых языков. Программист создаёт API на системном языке программирования (на хост-системе), и затем "экспортирует" этот интерфейс в скриптовый язык, на котором пользователь системы может строить высокоуровневые мини-программы с использованием предоставленного API во время работы хост-системы. Примером такого встраиваемого языка для C и C++ является Lua. В Rust экосистеме так же есть ряд решений похожего типа.
Среди существующих встраиваемых языков для Rust можно выделить два ключевых недостатка:

Существенная несовместимость семантики скриптового языка и семантики хост-системы(семантики Rust-а).
Несовместимость модели памяти скриптового языка с моделью памяти хост-системы.

На практике разработчик хост-системы вынужден адаптировать семантику экспортируемого API под особенности той или иной скриптовой системы. Это делается либо путём написания адаптированного API поверх существующего API, либо путём форсирования особенностей семантики скриптового языка внутри реализации хост-системы. Первый путь требует дополнительных регулярных трудозатрат по поддержке адаптационного слоя. Второй путь ограничивает возможности хост-системы. Кроме того, во втором случае создаваемое хост-API становится жёстко завязанным на особенности конкретного скриптового языка, что ограничивает возможности использования этого API в других проектах, написанных на том же системном языке хост-системы. То есть создаваемое хост-API становится неуниверсальным.
Целью моего проекта является создание динамического встраиваемого языка программирования для Rust, минимизирующего перечисленные проблем.
Итак, создаваемый язык должен обладать следующими свойствами:

Вносимые в исходный код скрипта изменения применяются в режиме реального времени, и не требуют перекомпиляции всей хост-системы.
Производительность(как по времени, так и по памяти) скриптовой системы не является критически важным фактором.
Разработчик API хост-системы должен обладать возможностью экспортировать создаваемый интерфейс на Rust в скрипт-систему более-менее как есть, без необходимости адаптации как модели памяти Rust под скрипт-систему, так и сигнатур экспортируемых Rust конструкций. И на стороне скрипт-системы пользователь скрипта должен обладать возможностью свободно, динамически и бесшовно манипулировать объектами, полученными, как из хост-системы, так и создаваемыми внутри скрипта.

Синтаксис скрипт-языка

Синтаксис скрипт-языка пока окончательно не определён. Но, в целом, это будет язык, семантически похожий на JavaScript, то есть императивный скриптовый язык со следующими особенностями:

Все функции, объявленные внутри скрипта, являются первородными объектами, и поддерживают замыкание на внешний контекст.
Ответственность за выбор типа передачи данных по ссылке или по значению лежат на скриптовой системе. Пользователь манипулирует памятью достаточно свободно.
Отсутствие статической типизации. Типы данных вычисляются в момент исполнения.
Отсутствие динамического приведение типов. Все типы данных разрешаются в момент исполнения однозначным образом, и не могут быть приведены в последствии.
Многомодульность.
Поддержка многопоточного исполнения.
Минималистичный синтаксис.
Отсутствие встроенной семантики. Вся базовая семантика скрипт-системы, вплоть до примитивных типов и операторов, не является встроенной, и определяется конкретной конфигурацией хост-системы.
Визуально синтаксис скрипта относится к категории C-подобных языков(таких как C, Rust, C#, JavaScript).

let a = 10;

let func = fn(b) {
    return a + b;
};

func(20); // 30

a = 15;

func(20); // 35

a = "foo"; // Ошибка времени исполнения. Переменная "a" содержит числовое значение, а не строку текста.

Не смотря на то, что в языке будет отсутствовать динамическое приведение типов на уровне синтаксиса, разработчик хост-системы может экспортировать в скрипт-систему конструкции и типы данных, которые сами по себе будут обладать динамическими свойствами. Например, представим, что на стороне хост-системы(на Rust-е) мы реализовали подобие произвольного JSON объекта с помощью конструкций HashMap и Vec, и на стороне хост-системы API этого объекта позволяет перестраивать этот объект свободно. Тогда и на стороне скрипт-системы мы сможем свободно манипулировать таким экспортированным объектом.
Система экспорта API хост-системы

В хост-системе разработчик API использует атрибутный макрос для экспорта конкретных конструкций Rust программы. Данный макрос осуществляет интроспекцию элемента программы, и записывает метаданные интроспекции в статический глобальный "скрипт-пакет" текущего крейта Rust-а. При запуске скрипт-системы пользователь указывает список крейтов, в которых был осущестлён экспорт, и из которых runtime-система скрипта собирает и анализирует всю метаинформацию всех скрипт-пакетов, и запускает runtime скрипта.
Атрибутный макрос не меняет содержимое экспортируемого элемента. Таким образом Rust-программа остаётся в неизменном виде с точки зрения разработчика Rust-а.
#[export]
pub struct Foo { // Этот тип данных будет известен скрипт-системе.
    pub a: usize, // Это поле будет доступно для чтения и записи в скрипт-системе.
    b: f64, // Это поле не будет доступно в скрипт-системе(оно остаётся приватным).
}

#[export]
impl Foo {
    // Эта функция будет доступна в скрипт-системе, как метод объекта Foo.
    // Она будет принимать аргумент по иммутабельной ссылке и возвращать результат по значению.
    pub fn get_a_plus_10(&self) -> usize {
        self.a + 10
    }

    // Эта функция будет доступна в скрипт-системе, как метод объекта Foo.
    // Она будет принимать аргумент по мутабельной ссылке и возвращать мутабельную ссылку(в данном случае на сам объект).
    pub fn b_plus_2(&mut self) -> &mut Self {
        self.b += 2;

        self
    }

    // Эта функция не будет доступна в скрипт-системе, так как мы явно указали, что её не нужно экспортировать.
    #[export(exclude)]
    pub fn bar(&self) {}
}

Из хост-системы с помощью атрибутного макроса можно экспортировать:

Структурные типы(struct).
Вариантные типы(enum).
Статические переменные(static).
Обычные функции(fn).
Ассоциированные элементы типа(impl).
Имплементации трейтов(impl Trait for).

Разработчик хост-системы может экспортировать типы данных и функции с generic-параметрами, заведомо и явно указав возможные варианты этих параметров. В этом случае макрос осуществит ограниченную мономорфизацию экспортируемых сигнатур.
#[export]
struct Foo<#[export(A, B, C)] T> { // Скрипт-системе будут известны три типа: Foo<A>, Foo<B>, Foo<C>. 
    t: T
}

Разработчик хост-системы может экспортировать только синхронизируемые(Send+Sync) типы со статическим временем жизни(то есть без лайфтаймов, или со статическими лайфтаймами).
#[export]
struct Foo<#[export('static)] 'a> { // Скрипт-системе будут известен тип: Foo<'static>. 
    t: &'a usize
}

При экспорте функций с сигнатурой, в которой присутствуют ссылки с неявным временем жизни, время жизни будет интерпретировано в соответствии с elide-правилами Rust:
#[export]
// Будет проинтерпретировано как fn foo<'x, 'y, 'z>(a: &'x usize, b: &'y usize, c: &'z usuze) -> &'x usize 
fn foo(a: &usize, b: &usize, c: &usuze) -> &usize {}

Разработчик хост-системы не может экспортировать сигнатуры с явным временем жизни, за исключением статических лайфтаймов.
#[export]
// Будет проинтерпретировано как fn foo(a: &'static usize, b: &'static usize) -> &'static usize 
fn foo<#[export('static)] 'a, #[export('static)] 'b>(a: &'a usize, b: &'b usize) -> &'b usize {}

Экспортируемые функции могут принимать другие функции. В этом случае на стороне скрипт-системы в экспортируемые функции можно будет передавать анонимные функции, объявленные внутри скрипта.
#[export]
fn foo(a: impl Fn(usize) -> usize) {}

//// на стороне скрипта:
//
// let callback = fn(a) { a + 1 };
//
// foo(callback);

Разработчик хост-системы может экспортировать асинхронные функции. В этом случае вызов асинхронного кода на стороне скрипт-системы будет исполнен runtime-системой с использованием указанного futures-runtime. Например, с помощью Tokio.
#[export]
async fn foo() {}

//// на стороне скрипта:
//
// let future = foo(); // Делает tokio::spawn(foo());
//
// future.await(); // "блокирует" выполнение текущего контекста исполнения до момент завершения future. 

Предложенная модель экспорта обладает рядом ограничений, но, в целом, она позволяет экспортировать широкий спектр возможных Rust API в неизменном виде, и в определенной степени является "золотой серединой" в поиске баланса между семантикой Rust и семантикой динамического скриптового языка.
С учётом того, что атрибутные макросы применяются непосредственно на экспортируемый объект Rust программы, трудозатраты по обслуживанию системы экспорта всегда локализованы, и могут происходить относительно бесшовно по мере дальнейшей разработки экспортируемого API.
Модель памяти

На стороне хост-системы компилятор Rust относительно использования ссылок требует соблюдения двух условий:

Ссылка не должна пережить время жизни объекта.
Если в программе есть активная мутабельная ссылка на объект, на этот объект не должно быть других активных ссылок.

Для соблюдения этих двух правил в ряде скрипт-языков используется система подсчёта ссылок с шаблоном внутренней мутабельности на каждый динамический атомарный объект. Например, для каждого атомарного объекта скрипта мы можем использовать ячейку памяти типа Rc<RefCell<dyn Any>>(или Arc<RwLock<dyn Any + Send + Sync>).
У этого подхода есть два недостатка:


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


С помощью этого подхода проблематично выразить обычный call-chain:
// Если мы будем клонировать каждое поле, то запишем число не в объект "foo", а в клон поля "c".
foo.a.b.c = 10;

// Если bar() и baz() были функциями builder-а, принимающими "&mut self", и возвращающие "&mut Self",
// мы нарушим семантику использования этого builder-а.
foo.bar().baz();


В своём решении я предлагаю следующий подход.
Все данные, управляемые скрипт-системой, будут лежать в куче. То есть у нас не будет какой-либо формы стека памяти в runtime-системе скрипта в явном виде.
У нас будет "универсальный" клонируемый объект Cell, который осуществляет подсчёт ссылок на данные в куче одного из двух типов:

Данные созданные в скрипте.
Указатели на данные, полученные из хост-системы.

К данным, созданным в скрипте относятся данные, полученные по значению из результата выполнения хост-функций. Такие данные сразу кладутся в кучу, и в объекте Cell будет храниться ссылка на эти данные в куче. При уничтожении последнего экземпляра Cell, данные из кучи освобождаются. В этом смысле Cell работает как обычный Rc/Arc.
В соответствии с правилами экспорта(с elide правилами Rust), ссылки, полученные из хост-функций, могли произойти только из ссылки переданной в первый аргумент функции("аргумент-получатель"). В свою очередь ссылка объекта-получателя могла произойти только из иного экземпляра Cell(других объектов в скрипт-системе нет).
fn new_a() -> A {...}
fn foo(a: &A) -> &B {...}

//// на стороне скрипта:
//
// // "new_a" возвращает данные по значению. Создаём для них Cell, кладём его в "a".
// let a = new_a();
//
// // Берём иммутабельную ссылку на данные из Cell "a".
// // Получаем ссылку &B, время жизни которой завязано на Cell "a".
// // Создаём для ссылки &B новый Cell, и кладём его в "b". 
// let b = foo(a);

Когда мы создаём Cell для ссылки, мы кладём в него указатель, полученный из этой ссылки, и так же кладём в него Cell аргумента-получателя, время жизни которого определяет время жизни ссылки. Таким образом указатель внутри Cell, созданной для этой ссылки, не переживёт Cell аргумента-получателя, породившего ссылку.
Другими словами, если в Rust ссылки "тянутся" за объектами, владеющими данными, то в скриптовой системе наоборот ссылки тянут за собой объекты, владующие данными. Данный подход позволяет соблюсти первое правило Rust("Ссылка не должна пережить время жизни объекта").
Второе правило Rust(про мутабельность доступа) требует организовать контроль по дереференсингу указателей обратно в ссылки.
Отметим следующие обстоятельства относительно модели памяти Rust в контексте интерпретации Miri-машины, которые мы должны учесть при дереференсе указателей.

Для каждого указателя(полученного, например, из ссылки) Miri присваивает тег, определяющий происхождение этого указателя(мутабельная или иммутабельная ссылка).
Для каждой области памяти Miri ведёт учёт стека тегов, которые могут появляться по мере создания новых ссылок на память.
Дереференс указателей в ссылки приводит к инвалидации стека тегов. Если после одной опреации инвалидации какой-нибудь из тегов в стеке исчезнит, то дереференсинг указателя, связанного с этим тегом, будет считаться неопределенным поведением.
Модель обработки стека области памяти Miri-машины периодически меняется и совершенствуется, но, в целом, мы можем опираться на обычные нормальные правила безопасного кода Rust при организации модели памяти скрипт-системы.

В конкретной runtime-сессии скрипт-системы существует глобальный реестр всех указателей. При создании новой Cell(независимо от её типа), указатель этой Cell автоматически регистрируется в данном реестр. При уничтожении последнего экземпляра Cell, связанного с конкретным указателем, указатель в реестре дерегистрируется.
Реестр представляет собой распределенную хеш-таблицу, ключами которой являются указатели, значениями данные об использовании конкретного указателя. Доступ к реестру осуществляется конкурентно(и может происходить из разных потоков). Из соображений оптимизации реестр разбит на непересекающиеся куски таким образом, что мутабельный конкурентный доступ к разным кускам реестра минимизирует случаи блокировки одним потоком другого. Кроме того, сам мутабельный доступ к реестру, как правило, происходит очень ограниченноое время(только при дерегистрации старых и регистрации действительно новых Cell).
Значениями реестра являются метаданные о текущем использовании конкретного указателя. Есть четыре вида использования указателя:

Из указателя получена иммутабельная ссылка.
Из указателя получена мутабельная ссылка.
Из указателя получен иммутабельный place (l-value в терминах C).
Из указателя получен мутабельный place (l-value в терминах C).

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

Если на указатель есть мутабельная ссылка, другие виды доступа отсутствуют.
Если на указатель есть иммутабельная ссылка, доступ к мутабельному place отсутствует.
Может быть не более одной мутабельной ссылки.
Любые другие конфигурации допустимы. В частности, допустимо одновременное получение мутабельного и иммутабельного place на указатель, поскольку такой вид доступа не дереференсит указатель, и это считается допустимым использованием в соответствии со спецификацией Rust.

Для каждого из четырёх видов доступа Объект Метаданных ведёт учёт стека "пользователей" по конкретному виду доступа(организованный в виде Slab-структуры). С точки зрения правил доступа имеет значение только количество занимаемых в стеке слотов(вернее факт наличия или отсутствия занятых слотов конкретного стека). При успешной выдаче конкретного вида доступа в стек записывается метаинформация о позиции в исходном коде скрипта, в котором этот доступ был запрошен. Благодаря этому в случае провала запроса на доступ, пользователь скрипта получает информативное сообщение об ошибке о том, в каком именно месте кода произошёл конфликт доступа к данным.
По завершении использования указателя по полученному разрешению, Cell освобождает это разрешение в соответствующем стеке Объекта Метаданных.
Доступ ко всем четырём стекам Объекта Метаданных осуществляется совместно, и защищено отдельным мьютексом(независящим от хеш-таблицы Реестра). Таким образом нарушение связанности Объекта Метаданных при гонке доступа из разных потоков невозможно.
Следует отметить, что представленная модель не является паттерном синхронизации данных при доступе из разных потоков. Если один поток получает мутабальеную ссылку к данным, то другой поток при попытке получении, например, иммутабельной ссылки, не будет заблокирован, вместо этого произойдёт runtime-ошибка доступа. Для организации синхронизации доступа между потоками разработчик хост-системы может экспортировать и предоставить пользователю скрипт-системы отдельные интерфейсы синхронизации(например, API с объектами-семафорами).
Помимо получения контроля за ссылками(первые два вида доступа) модель так же контролирует получения places указателей(вторые два вида доступа). Это сделано с целью эмуляции Rust Non-Lexical Lifetimes.
struct Foo { a: usize, b: usize }

fn two_muts(a: &mut usize, b: &mut usize) {}

let mut foo = Foo { a: 100, b: 200 };

// NLL позволяет получить мутабельный доступ к разным полям структуры одновременно,
// не получая при этом мутабельный доступ к самому объекту.
two_muts(&mut foo.a, &mut foo.b);


Rust(и Miri в частности) не позволяет получить одновременный мутабельный доступ к полям структуры через мутабельный(или иммутабельный) дереференсинг самого объекта. Попытка такого доступа является неопределённым поведением. С другой стороны, используя только первые два вида доступа через Объект Метаданных мы так же не сможем получить такой доступ одновременно к двум полям через мутабельную ссылку на саму структуру, поскольку правила доступа Объекта Метаданных не позволяют получить более одной мутабельной ссылки на саму структуру.
Однако Rust позволяет получить указатели на поля структуры путём взятия place(l-value в терминах C), и минуя дереференсинг указателя на сам объект(использя addr_of! и addr_of_mut!). В этом случае из Объекта Метаданных мы можем получить мутабельный доступ на place указателя в любом количестве(правила доступа Объекта Метаданных это позволяют в случае отсутствия ссылок на указатель). С другой стороны, получив мутабельный place, и создав из него Cell для указателя на поле самой структуры, мы в качестве происхождения указателя на поле сохраняем и place на саму структуру, тем самым препятствуя одновременному получению, например, мутабельной ссылки на структуру и мутабельной ссылки на её поле одновременно.
Последний аспект модели, о котором необходимо упомянуть, это проблема эвалюации аргументов функции с точки зрения типа мутабельности ссылок.
В Rust, как правило, выражения интерпретируются от аргументов к функциям. Сначала интерпретируются сами аргументы, потом в зависимости от типов аргументов Rust осуществляет поиск соответствующих функций по полученной сигнатуре. Существенным для Rust являются типы данных выражений аргументов, и типы захвата(передача по значению, передача по иммутабельной ссылке, передача по мутабельной ссылке). По этой причине в коде Rust требуется использовать оператор взятия по ссылке явным образом:
fn foo(by_val: usize, by_ref: &usize, by_mut: &mut usize);

let a = 100usize;
let b = 200usize;
let mut c = 300usize;

// Раст трубет явного использования оператора взятия по ссылке.
foo(a, &b, &mut c);

// Так писать нельзя:
//
// foo(a, b, c)

В скрипт-системе резолюция функций осуществляется только по типам данных аргументов(без учёта ссылок). В этом смысле скрипт-система не позволяет экспортировать две функции с одинаковым именем и одинаковым набором аргументов по типам, на разным типом доступа к аргументам. Это ограничение на практике несущественно, поскольку мы редко создаём хост-API с таким пересечением.
В объекте Cell хранится метаинформация о типе данных, который он хранит, и её достаточно для резолюции экспортированных функций в процессе интерпретации вызова функций в скрипте.
По этой причине, в частности, в Cell хранятся не ссылки, а сами указатели(с метаинформацией об их мутабельности), которые превращаются в ссылке в момент доступа к Cell по правилам доступа Объекта Метаданных, и по типу мутабельности указателей.
Поскольку Cell разграничивает мутабельные и иммутабельные указатели(которые могут иметь разное происхождение с точки зрения Miri-машины) при доступе к полям структур в Cell для соответствующего поля сохраняется одновременно и мутабельный и иммутабельный указатель, полученный через place указатель структуры. Специализация такой Cell на мутабельную или иммутабельную ссылку происходит в момент дереференсинга Cell для аргумента соответствующей хост-функции.
(C) Илья Лахин 2023.