Ядро FTS, переписанное на flang

В каталоге flang/core/ лежат четыре файла на самом flang общим объёмом около 390 КБ (398 618 байт, 4573 строки). Это ядро FTS — лексер, парсер, вычислитель утилит и печать JSON, — переписанное с TypeScript на язык, который сам живёт в этом же репозитории.

Оговорка сразу: эта глава переписывалась дважды за одну ночь. В первой редакции парсер на flang не брал скобочный диалект FTS и сходился с эталоном на 53 моделях из 56; через час долг закрыли, и стало 56 из 56. Числа ниже — вторые.

Цель сформулирована в первой строке flang/core/SPEC.md:

переписать ядро FTS (сейчас src/*.ts, 3155 строк) на flang, чтобы печатать его в C и получить нативный fts без Node — и дальше в остальные целевые языки.

То есть кодогенерация (глава «Кодогенерация») здесь не самоцель, а средство: если ядро написано на flang, а flang печатается в C, то fts становится нативным бинарником.

Почему это стало возможно только сейчас

Ответ объясняет, зачем flang вообще понадобился. В репозитории есть файл tools/ftsc/self/meta.fts с записанным ограничением:

в ядре FTS строка является типом поля, но не значением, над которым можно вычислять

Парсер — это вычисления над строками. Поэтому ядро FTS нельзя было написать на самом FTS. flang снимает ровно это ограничение: строки в нём данные.

Так что core/ — не демонстрация возможностей, а тест на состоятельность замысла. Язык создавался, чтобы на нём можно было написать инструментарий FTS; core/ проверяет, получилось ли.

Что написано

Мы проверили это запуском — flang check на каждом файле возвращает valid: true и ни одной функции с total: false. Считать при этом надо аккуратно: check показывает функции уже после связывания модулей, поэтому у parser.flang в ответе 280 функций — свои 208 плюс 41 из лексера и 31 из печати JSON.

300 функций, все с доказанным завершением. Для языка, чей анализ тотальности отвергает даже рекурсию n − 1, это не само собой разумеется — см. ниже про цену. За час до нашей сверки в лексере было 34 функции, а в парсере 131: разбор скобочного диалекта прибавил к ядру почти сотню функций и тысячу строк.

Файлы связаны импортом: parser.flang использует «Лексер FTS» и «Печать JSON», evaluate.flang — «Печать JSON». То самое связывание модулей, ради которого появился link.mjs (глава «Стандартная библиотека»).

Слои и границы

текст .fts ──[лексер]──> список «Токен» ──[парсер]──> «Документ»
                                                          │
                                        ┌─────────────────┴───────────────┐
                                   [вычислитель]                     [печать JSON]
                              значение / диагностика            строка, байт в байт
                                                                  как у ядра на TS

Правило границ жёсткое: «Никакой слой не разбирает текст повторно и не заглядывает внутрь чужого слоя». Стыкуются слои только через типы, объявленные в контракте:

тип «Токен»
  вариант ОтступБольше
  вариант ОтступМеньше
  вариант КонецСтроки
  вариант Имя содержит текст: строка
  вариант Строка содержит текст: строка
  вариант Число содержит значение: число
  вариант Знак содержит текст: строка
  вариант Конец

Два последних варианта — Строка и Знак — появились в контракте вместе с разбором скобочного диалекта, и оба обязательные, а не косметические. Знак нужен, потому что без него { прилипало к соседнему слову и structure B { давало два токена вместо трёх. Строка — потому что ядро на TypeScript различает kind: "identifier" и kind: "string": «да» в ёлочках это признак, "да" в обычных кавычках — строка, и слить их значило бы разойтись с эталоном.

Тот же коммит уточнил и разбор точки: она режется только там, где слово не является числом. 10.5 остаётся одним токеном, Individual.isHuman — тремя, «ровно там же, где останавливается регулярное выражение числа в ядре».

Критерий готовности

Вот это стоит перенять независимо от того, интересен ли вам flang.

Ядро считается верным не тогда, когда проходят его собственные тесты, а когда на всех .fts репозитория старое ядро на TS и новое на flang дают побайтово совпадающий JSON — включая коды и тексты диагностик.

Дифференциальная сверка против существующей реализации вместо собственного набора тестов. Своя тестовая база проверяет то, о чём подумал автор; сверка с работающим предшественником проверяет всё, что предшественник умеет, включая поведение, о котором никто не помнит.

Результаты записаны по слоям, и записаны с указанием того, что не сошлось:

• Печать JSON: 56 моделей, ноль расхождений с JSON.stringify(compile(…)).
• Вычислитель: 20 документов, 24 утилиты, 11 180 входов, ноль расхождений — «совпадают и значения (по Object.is, до последнего бита), и коды диагностик».
• Парсер: сквозная сверка текст → лексер → парсер → печать JSON — 56 моделей из 56, ноль расхождений, обе поверхности. Диагностики сверены отдельно: на 34 намеренно сломанных моделях отступной поверхности и на 13 моделях скобочной совпадают и код, и текст сообщения.
• Мост совместимости (compat.mjs, не на flang): 19 593 входа, ноль расхождений.

Ещё за час до нашей сверки в этом месте стояло «53 из 56»: три модели были написаны скобками, и парсер честно отвечал FTS_UNSUPPORTED_SURFACE, а тест закреплял это как долг. Такая формулировка была здоровее, чем округление до «работает», — и, судя по тому, что долг закрыли ближайшим коммитом, она же оказалась и полезнее. Записанный долг видно; «работает» не видно никому.

Как удалось остаться в тотальном классе

Никакой магии — те же приёмы, что в стандартной библиотеке (глава «Тотальность»), только применённые к настоящему компилятору.

Лексер. Обход строки по символам заменён на разделить плюс свёртка. Стек отступов — список чисел, поэтому закрытие нескольких уровней сразу становится рекурсией по хвосту стека, а не по числу. В контракте записано, что именно это сняло «единственное место, где напрашивалась бы рекурсия по числу».

Печать JSON. Экранирование строки сворачивается по таблице из 34 замен, каждая через разделить и соединить.

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

Парсер. Самое неожиданное: рекурсивного спуска по потоку токенов нет — и это верно для обеих поверхностей FTS, по одной и той же причине. «Остаток потока стал короче» анализ завершаемости частью значения не считает, поэтому курсор по потоку в тотальном классе не выражается вовсе.

Отступная поверхность разбирается тремя свёртками: поток режется на строки, строки собираются в группы «заголовок и всё, что глубже», и только потом каждая строка разбирается по первым словам — это разбор формы фиксированной длины. Рекурсия осталась в пяти вспомогательных функциях («Пропустить слова», «Взять слова», «Начинается словами», «Позиция слов», «Заменить слова»), и всюду это рекурсия по хвосту списка на одной и той же позиции аргумента.

Скобочная поверхность — та, что появилась последним коммитом, — спуск всё-таки использует, но не по потоку, а по дереву. Поток свёрткой сворачивается в «Узел» (стек открытых скобок, строки режутся тут же), и дальше поддерево — это поле варианта, а строка группы — элемент списка, то есть строго меньшая часть того же значения. Взаимная рекурсия там появилась («Утверждение из узлов» ↔ «Шаг тела утверждения» и три функции разбора произвольного значения), и в каждом цикле убывает первый аргумент — та самая единая позиция на каждом ребре, которой требует totality.mjs (глава «Тотальность»).

Это, пожалуй, лучшая иллюстрация того, зачем нужен был анализ тотальности. Ограничение не запретило написать парсер со спуском — оно заставило спускаться по структуре, а не по позиции в потоке. Ровно та же программа, но убывание в ней стало видимым.

Долги, записанные честно

Раздел «Долги» в flang/core/SPEC.md занимает больше половины файла. Долг определён как «либо место, где не поставлен признак тотальная, либо расхождение с ядром на TS, о котором знают и которое пока оставлено». Несколько примеров:

• Нормализация NFC не выполняется. Ядро зовёт String.normalize на каждом имени, а в flang такой встроенной формы нет — «её нельзя выразить ни через „разделить“, ни через „подстрока“». Пока все модели репозитория в NFC, расхождение ненаблюдаемо.
• Одинокий суррогат не экранируется. Отличить суррогат нечем: нет формы «код символа». Долг закрывается не в json.flang, а в builtins.mjs. Отдельно отмечено, что закреплён тест с именем «известный долг: одинокий суррогат не экранируется» — «именно затем, чтобы закрытие долга не прошло молча».
• Экспоненциальная запись числа считается именем. Лексер на flang следует букве контракта, а регулярное выражение ядра шире. «Расширять придётся вместе с разделом 1, а не вместо него».
• executeUtility и сводка testUtilities не реализованы — им нужен «Документ» целиком, а слой видит только утилиту.
• Имя-неидентификатор печатается неполно. ts_compat ядра переводит такое имя в FTS_ и коды его символов шестнадцатеричными (FTS_4c_6f_79…), а формы «код символа» в языке нет — тот же долг, что у одинокого суррогата. В этой ветке остаётся один префикс. Долг новый: он записан тем же коммитом, который закрыл скобочный разбор, и снабжён тестом «известный долг», чтобы закрытие не прошло молча.

Список долгов живой в обе стороны — за один коммит три позиции из него ушли (склейка имён в кавычках переехала из парсера в лексер и унесла с собой семь функций; документ, начатый не с той строки, стал давать FTS_EXPECTED_KEYWORD как у ядра; «да» в кавычках перестало быть неотличимым от признака да), а одна добавилась. Это нормальный режим работы, а не признак неблагополучия: долг здесь — единица учёта, а не жалоба.

И один долг, который стоит привести как пример нормальной инженерной честности:

Скаляр — сумма типов, а не строка. В первой редакции этого файла скаляр был записан как строка, и печать JSON это сразу опровергла: 5, "5" и да дают три разные строки JSON, а по текстовому представлению их не различить. Ошибка контракта, найденная слоем печати.

Ошибка контракта, найденная нижним слоем, записана в контракт вместе с тем, как её нашли.

Насколько это самохостинг

Строго говоря — пока нет. Переписано ядро FTS, а не компилятор flang: лексер, парсер, типы, тотальность и бэкенды самого flang по-прежнему на JavaScript (flang/src/*.mjs). Самохостинг назван в бэкенде C как направление — «первый шаг к самохостингу: компилятор flang, написанный на flang, соберётся через C», — но шаг это первый, а не последний.

Что действительно сделано: показано, что на flang пишется настоящий парсер настоящего языка — обе поверхности, целиком в тотальном классе, с побайтовым совпадением вывода с существующей реализацией на всех 56 моделях корпуса. Для суточного языка этого более чем достаточно, чтобы считать замысел проверенным.

Если будете сверяться с корневым README.md, учтите: там всё ещё написано «the legacy braced dialect is not parsed (53 of 56 corpus models round-trip byte-for-byte; the other three are braced)». README переписали в 00:29 UTC, скобочный разбор закрыли в 00:54 — README отстал на двадцать четыре минуты. Верить надо flang/core/SPEC.md и прогону тестов.

Дальше — глава «Чего в языке пока нет»: проверенный перечень недостающего.