Если кратко, то цель: компилятор некоторого подмножества языка Си на C++, который работает в compile-time. Компиляция будет происходить в кастомный байт-код для дальнейшего выполнения в ВМ уже в рантайме.

Я уже когда-то писал компилятор Си в compile-time, но я его забросил из-за того, насколько сложен он для меня стал. Там не было ни парсера, ни внятного лексера (я ещё даже не знал, что это такое), а код сразу компилировался в ассемблер x86_64.

Зачем это всё вообще надо? На этот вопрос я не отвечу. Но попытаюсь привести некоторые преимущества, которые может дать этот подход:

  • код компилятора не занимает места в бинарнике,

  • время тратить на компиляцию в рантайме тоже не надо,

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

А главное ещё не забыть про минусы. Куда же без них?

  • Никаких оптимизаций. Компиляторы на них потратили десятилетия, а какой-нибудь LLVM в constexpr я точно не протащу. Хотя если написать полностью интерпретатор в constexpr, а затем запустить LLVM в compile-time… На этом хоть очередную шизостатью пиши, но боже упаси.

  • Хотрелоад (или же замена скрипта в рантайме). О нём и речи не идёт, учитывая, что скрипт компилируется в compile-time и вшивается намертво в бинарник. Поддержку этой фичи, конечно, можно сделать, если постараться, но это не в списке задач.

Обходим ограничения constexpr

В C++ 20 разрешили динамически выделять память в compile-time и пользоваться std::vector, что очень сильно расширяет наши возможности. Но есть одно очень важное но: ничего из этого нельзя выносить в рантайм. То есть нельзя написать constexpr std::vector<int> data = makeData();, оно не будет компилироваться. Поэтому нужно городить костыли.

Передаём строки в шаблонах

К сожалению, хоть в Комитете многое и разрешили делать в compile-time, но передавать строки без костылей нам так и не дали. Но это очень легко обходтится, вещь, думаю, довольно известная.

template<std::size_t N>  
struct const_string {  
  constexpr const_string() = default;  
  
  // implicit-конструктор, который позволяет творить нехорошие вещи
  constexpr const_string(const char (&str)[N]) {
    std::copy_n(str, N, value);  
  }  
  
  constexpr operator std::string_view() const {  
    return {value, value + N - 1};  
  }  
  
  char value[N]{};  
  const std::size_t length = N;  
};

// используем так:
template<const_string str>
auto very_smart_function(...) { /* ... */ }

Вытаскиваем массивы из compile-time

Это оказалось не очень сложно, но готового объяснения в Интернете, как с const_string, я не нашёл.

Чтобы вытащить std::vector<T> из constexpr, нужно его как-то преобразовать в std::array<T, N>. Проблема в том, что нельзя просто написать std::array<T, myVector.size()>, т.к. myVector.size() не будет константным значением. Значит его нужно сделать константным.

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

// data_getter - наша лямбда
template<auto data_getter>
constexpr auto to_array() {  
  using value_type = typename decltype(data_getter())::value_type;  
  constexpr static std::size_t size = data_getter().size();  
  
  // Создаём статический массив с "динамическим" размером,
  // копируем туда все данные из вектора
  std::array<value_type, size> out;  
  auto in = data_getter();  
  for (std::size_t i = 0; i < size; ++i) {  
    out[i] = in[i];  
  }  
  return out; // профит
}

template<const_string str>
constexpr auto lex() {
	constexpr static auto data_getter = [] constexpr {
		// .lex() возвращает вектор токенов
		return lexer{static_cast<std::string_view>(str)}.lex();
	};
	// Данные успешно вытащены в рантайм =D
	return to_array<data_getter>();
}

Выводим ошибки

Для вывода ошибок во время компиляции в C++ есть static_assert, который позволяет нам вывести свою собственную ошибку. Но по стандарту (до C++ 26) это обязательно должен быть литерал.

constexpr auto parse() {
	// Так можно
	static_assert(false, "Expected ';'");
	
	// Так нельзя (до C++ 26)
	std::size_t line = 5;
	static_assert(false, "Expected ';' at line " + to_string(line));
}

Хотелось бы, чтобы мой проект не требовал C++ 26, поэтому я сделал ещё один костыль. Сформированная строка превращается в массив (а точнее в const_string через такой же трюк как в to_array), а затем передаётся как параметр шаблона в ErrorMessage, который всегда вызывает ошибку компиляции. В итоге компилятор вынужден вывести полное имя шаблона, в которое будет включён текст ошибки. Правда, длина текста там ограничена, но, думаю, что это можно решить через несколько ErrorMessage… Боже упаси такое читать в консоли.

template<const_string Msg>  
struct ErrorMessage {  
  static_assert(false, "Check the template parameter for details");  
};

template<auto err_getter>  
consteval auto report_error() -> void {
// поддержка C++ 26
#ifdef KORKA_FEATURE_FORMATTED_STATIC_ASSERT  
    static_assert(false, to_string(err_getter()));  
#else  
    constexpr auto msg = const_string_from_string_view<[] { return to_string(err_getter()); }>();  
    std::ignore = ErrorMessage<msg>{};    
#endif
}

Чтобы вы этого ужаса не видели, покажу вывод ошибки в C++ 26

error: static assertion failed: Lexer Error: Unterminated string at line 12

Маппим сигнатуры к именам

В обычных плюсах все уже привыкли к std::unordered_map<string, value_t> и стандартным и нестандартным (привет, Boost!) контейнерам. Но мне понадобилась таблица, ключом которой была бы строка, а значением - тип данных. И проблема в том, что в C++ типы - не объекты, их нельзя положить в словарик :(.

Поэтому встречайте очередной костыль.

template<auto, class>
struct signature_mapper;

// function_info_getter принимает индекс на функцию, а Is... 
// содержат все возможные индексы, которые мы раскрываем через ...
template<auto function_info_getter, std::size_t... Is>
struct signature_mapper<
function_info_getter,
std::index_sequence<Is...>
> {
	// Функция хэша
	consteval static auto hash(auto &&v) -> std::size_t {
		return frozen::elsa<std::string_view>{}(v, 0);
	}
	
	// Функция, перегруженная множеством уникальных типов, основанных на хэше имени функции
	constexpr static auto _overloaded = overloaded{
		(
			[](unique_type<hash(function_info_getter(Is).name)>)
			-> const_function_info_to_signature_t<[] { return function_info_getter(Is); }> * {
				return nullptr;
			}
		)...
	};
	
	// Извлечение типа из перегруженной функции
	template<const_string name>
	using get_signature_t = std::remove_pointer_t<decltype(
		_overloaded(
			unique_type<hash(name)>{}
		)
	)>;

};

Тут мы используем всем знакомый overloaded, но уже во зло. В общем, один тип наследуется от нескольких лямбд, которые принимают пустой уникальный тип unique_type<hash>, который служит нашим “ключом”, и возвращает указатель на нужный нам тип.

// Пример того, во что превращается mapper после раскрытия пакета параметров
struct overloaded : lambda1, lambda2, lambda3 {
    using lambda1::operator();
    using lambda2::operator();
    using lambda3::operator();
};

// Где каждая лямбда выглядит примерно так
auto lambda_fib = [](unique_type<hash("fib")>) -> signature_of_fib* { 
    return nullptr; 
};

Когда мы вызываем overloaded(uniquetype<hash(name)>()), бедный компилятор должен разрешить нашу перегрузку. Он ищет среди всех операторов () тот, чей аргумент совпадает с нашим хэшем. А мы этот тип просто берём и извлекаем.

Этот “механизм” используется для извлечения функций из скрипта в нативный C++.

constexpr auto script_fib = compile_result.function<"fib">();

Биндинги из плюсов в наш скриптовой язык

А вот это была самая изнурительная для меня часть. А вообще как изнурительная, я пару вечеров думал, писал код, пока одним утром всё не получилось. Проблема была в том, что я хотел сделать красивый API, который невозможно было бы реализовать в рамках текущих стандартов C++ (возможно, в 26-м можно, но я его не смотрел).

Я хотел писать так:

auto func() -> void;
auto foo(int) -> int;

// Примерно так
constexpr auto bindings = korka::make_bindings<
	"func", func,
	"foo", foo
>();

// Или так
constexpr auto bindings = korka::make_bindings(
	"func", func,
	"foo", foo
);

constexpr auto script_fib = compile_result.function<"fib">();Но в итоге все эти варианты оказалось реализовать невозможно. Почему?

В C++ нельзя просто так передать строку в template <auto ...args>. Нам необходим тип const_string (костыль из начала статьи). Не получится смешивать типы в одном пакете параметров variadic args так, чтобы компилятор сам догадался, что первый аргумент - строка, второй - функция. Шаблоны требуют явности, и попытка написать универсальный парсер просто невозможно.

В варианте №2 невозможно вытащить функцию в рантайм. И вот хоть лбом ты тресни, но не получится. У функций могут быть разные сигнатуры, а их все нужно привести к одному типу, а ещё враппер сделать. reinterpretet_cast<void*>(&func) сделать нельзя.

В итоге я пришёл к этому:

constexpr auto bindings = korka::make_bindings(    korka::wrap<fib>("cpp_fib"),    korka::wrap<print_n>("print_n")  );

Не так элегантно, как планировалось, но всё ещё неплохо. У wrap очень простой код:

// тип функции-враппера (её будет вызывать ВМ)
using vm_external_function_type = void(vm::context_base &context);

// инфа для компилятора
template<class Signature>  
struct wrapped_function {  
  using signature_t = Signature;  
  
  vm_external_function_type &external_func;  
  std::string_view name;  
};

template<auto func>  
consteval auto wrap(std::string_view name) {  
  return wrapped_function<std::decay_t<decltype(func)>>{  
    binding_wrapper<func>,  
    name  
  };  
}

Самое интересное скрыто внутри binding_wrapper<func>. Полный код приводить я не буду, потому что ещё не описал саму виртуальную машину, где всё будет исполняться, но если кратко, то binding_wrapper смотрит на сигнатуру функции, генерит код, который достаёт аргументы из ВМ, вызывает нативную функцию, а затем кладёт обратно в ВМ результат.

Компилятор и виртульная машина

Теперь самое вкусное. Компиляторы я до этого ни разу не писал (то, что я упомянул в самом начале статьи, не считается), поэтому делал его по самым первым поисковым результатам, что мне выдал гугл.

Я разделил компилятор на три модуля:

  • лексер - бьём текст на токены;

  • парсер - строим по токенам дерево;

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

В целом, думаю, что стоило вообще это всё вместить в один класс через какую-нибудь композицию, но уже поздновато как-то.

Лексер

Работает просто и примитивно. Просто пытаемся выцепить токены в цикле, пока не дойдём до конца файла.

constexpr auto scan_token() -> std::optional<std::expected<lex_token, error_t>> {  
  char c = advance();  
  switch (c) {  
    case '{':  
      return make_token(lex_kind::kOpenBrace);  
    case '}':  
      return make_token(lex_kind::kCloseBrace);  
    case '(':  
      return make_token(lex_kind::kOpenParenthesis);  
    case ')':
    // ...
      
	case ' ':  
	case '\r':  
	case '\t':  
	  // Ignore whitespace  
	  return std::nullopt;
	  
	// ...
	  
	default:  
	  if (is_digit(c)) {  
	    return scan_number();  
	  } else if (is_alpha(c)) {  
	    return scan_identifier();  
      }
  }
}

Парсер

Тут уже чуть интереснее. Нам нужно строить AST, а если по-русски, то абстрактное синтаксическое дерево. И это дерево нужно как-то представить. Обычный подход с классом Node, который держит указатели на другие Node, вряд ли подойдёт, потому что это constexpr. Так можно написать, и оно даже будет работать, но вынести дерево в рантайм уже не получится. Поэтому проще всего использовать простой советский std::vector<Node>, где ноды будут хранить индексы друг на друга внутри этого массива.

Такой подход ещё повышает кэш-локальность данных для процессора, правда, сомневаюсь, что он эту локальность вообще увидит, учитывая, что всё выполняется в compile-time.

Парсер у меня рекурсивный, то есть во время парсинга одного выражения, мы можем начать парсить другое. Вот небольшой фрагмент:

constexpr auto parse_statement() -> parse_result {  
  auto tok = peek();  
  if (!tok) return make_error("Unexpected end of input");  
  
  switch (tok->kind) {  
    case lex_kind::kOpenBrace: return parse_compound_stmt();    // { ... }
    case lex_kind::kIf:        return parse_if_statement();     // if (...) ...;
    case lex_kind::kWhile:     return parse_while_statement();  // while (...) ...;
    case lex_kind::kReturn:    return parse_return_statement(); // return ...;
    default:                   return parse_expression_stmt();  // ...;
  }  
}

constexpr auto parse_return_statement() -> parse_result {  
  if (!match(lex_kind::kReturn)) return make_error("Expected 'return'");  
  
  index_t expr_idx = empty_node; // empty_node = -1 
  if (auto next = peek(); next && next->kind != lex_kind::kSemicolon) {  
    auto expr = parse_expression(); // очередной спуск, теперь парсим выражения
    if (!expr) return std::unexpected{expr.error()};  
    expr_idx = *expr;  
  }  
  
  if (!match(lex_kind::kSemicolon)) return make_error("Expected ';' after return");  
  return m_pool.add(stmt_return{expr_idx});  
}

parse_return_statement спускается в parse_expression, который спускается уже в parse_assigment, который спускается в parse_logical_or, который… Ну, вы поняли. На этом также основан приоритет операторов.

Его величество Компилятор (+ анализатор)

В этом моменте я немного схитрил.

Прежде чем начинать писать компилятор, нужно знать под какую архитектуру мы пишем. Будь то x86, ARM или вообще JVM.

Изначально, когда я писал подобный проект, я планировал генерировать сырой ассемблер для x86 (последние Clang и GCC поддерживают constexpr std::string_view в asm("...") ), но если честно, писать кодогенератор для зоопарка инструкций x86 в constexpr - прямой путь в дурку.

Да и к тому же, если мы будем использовать более старую версию компилятора, то никакого asm со с генерированными строками не будет. А если сгенерить сразу голые машинные инструкции, то их тоже выполнить толком кроссплатформенно не получится, так как сработает DEP (Data Execution Prevention). Придётся вызывать платформозависимые mmap или VirtualAlloc, выделять память, копировать туда код… И всё, прощай кроссплатформенность, привет антивирусник (если мы соберём прогу на винде), который убьёт наш бинарник за такие фокусы с памятью.

Так в чём же я “схитрил”? Я создал свою архитектуру, которая будет выполняться в виртуальной машине. Стековой машине.

Почему именно стековая? Для неё оказалось невероятно легко генерировать код. Если вы делаете регистровую архитектуру (как в процессорах или в Lua), то придётся писать алгоритмы распределения регистров (я был на митапе по плюсам в ИТМО, там эта задача разбиралась; это сложно). А в стековой всё в разы проще.

Если нужно сложить А и Б, то мы делаем следующее:

  1. Кладём в стек значение А.

  2. Кладём в стек значение Б.

  3. Вызываем инструкцию сложения. Она берёт два значения со стека и кладёт в него сумму.

В итоге у меня получился следующий набор инструкций:

enum class op_code : char {
  // Загружают со стека или на стек значения из locals (хранилище переменных)
  lload, lsave,  
  
  i64_const, // Кладёт на стек константу
  
  // Математические
  i64_add, i64_sub, i64_mul, i64_div,  
  
  // Сравнение, кладёт 1, если два значения на стеке равны
  i64_cmp,  
  
  jmp, // прыжок по смещению к нужной инструкции 
  jmpz, // условный прыжок, если на стеке 0, то прыгает
  
  call, // вызов функции
  ret, // возврат из функции
  
  trap, // вызов нативной C++-функции
};

Так, а что насчёт анализатора, что был в заголовке?

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

Надо помнить, что я довольно ленивый, а constexpr всё-таки не резиновый. Делать отдельный проход по дереву мне не хотелось. Поэтому мой компилятор совмещает эти две функции: семантический анализ и кодогенерацию.

Обычно это называют Single-Pass Compilation (однопроходной компиляцией), но она у меня не совсем однопроходная, так как лексер и парсер обособлены, поэтому мой подход гибридный.

Компилятор рекурсивно спускается по дереву и делает две вещи:

  1. Проверяет семантику: “была ли объявлена переменная, какой её тип” - до того, как мы пытаёмся её сложить. Совпадают ли типы при вызове функции? Есть ли вообще такая функция? И тому подобное.

  2. Генерирует байт-код: если проверки прошли, то он сразу же пишет соответствующие байты инструкций в выходной std::vector<std::byte> (который мы потом элегантно вытащим через to_array).

В итоге мы получаем готовый, семантически проверенный и абсолютно безопасный (давайте притворимся, что я не наделал ошибок в коде компилятора), который остаётся только скормить виртуальной машине.

Так что в итоге?

Давайте посмотрим на то, как выглядит итоговый API моей несчастной библиотеки (назовём её Korka).

Вот пример кода, где мы используем биндинги (типобезопасность 100%, стандартом клянусь):

// Наши нативные функции C++
auto fib(std::int64_t n) -> std::int64_t {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
}

auto print_n(std::int64_t n) -> void {
  std::cout << n << '\n';
}

// Код скрипта
constexpr char code[] = R"(
  int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + cpp_fib(n-2);
  }

  void print_fib(int n) {
    int result = fib(n);
    print_n(result);
    return;
  }
)";

// Создаем биндинги
constexpr auto bindings = korka::make_bindings(
  korka::wrap<fib>("cpp_fib"),
  korka::wrap<print_n>("print_n")
);

// Компилируем в компайл-тайме
constexpr auto compile_result = korka::compile<code, &bindings>();

// Получаем адреса функций в сгенерированном байт-коде (+ сигнатуры)
constexpr auto script_fib = compile_result.function<"fib">();
constexpr auto script_print_fib = compile_result.function<"print_fib">();

int main() {
  // Инициализируем ВМ
  korka::vm::context ctx{compile_result.bytes, bindings};

  // Вызываем функцию fib, которая возвращает int64_t
  auto result = ctx.call(script_fib, 12L);
  std::cout << "fib(12) = " << result << '\n'; // выводит 144

  // Вызываем print_fib
  ctx.call(script_print_fib, 16L); // выводит 987
  
  return 0;
}

Та-да! Оно полностью компилируется и работает.

Небольшой анализ

Ради интереса решил сравнит с другими скриптовыми языками. Ведь красивый API это хорошо, но стоила ли игра свеч с точки зрения производительности? Поэтому предлагаю сравнить Korka с Python и Lua.

В качестве бенчмарка использовалось рекурсивное вычисление 16-го числа Фибоначчи. Тестировал на собранном из хлама сервере с Xeon E5-2689 (3,6 ГГц). Замерял два этапа:

  • время инициализации - от начала инициализации языка до готовности выполнять вычисления;

  • время выполнения 100 000 итераций алгоритма.

Язык

Время инициализации

Время выполнения (100 000 итераций)

С (Korka)

7,61 мкс

15 668,5 мс

Python 3

45 163,48 мкс

7 962,5 мс

Lua

149,52 мкс

8 775,1 мс

Результаты не особо утешительные, но оно и понятно почему.

Korka стартует в 20 раз быстрее чем Lua и почти в 6000 раз быстрее Python. Объяснить это легко, потому что в это время Lua и Python должны прочитать скрипт, скомпилировать его в свой байт-код, подготовить всю необходимую память (включая Garbage Collector) и остальное. Пока Korka нужно всего лишь выделить стек.

Очевидно, что если заранее скомпилировать код на Lua и Python в байт-код, то результаты у них будут лучше.

В рантайме видно, что Korka медленее примерно в 2 раза. Чудес не произошло. Потому что моя ВМ это просто наивный интерпретатор, написанный за один вечер, в ней отсутствуют JIT-компиляция, регистровая архитектура (она априори быстрее) и прочие оптимизации, которые в Python и Lua вылизывались годами.

Вывод

Я написал полноценный (почти) компилятор C, который работает в constexpr. Зачем? Непонятно. Тем более, что это уже делали, см. constexpr-8cc. Но там нет биндингов и кросс-платформенности.

Исходный код проекта доступен на GitHub (ахтунг, код страшный). Буду рад критике и комментам.