Здравствуйте, меня зовут Дмитрий Карловский и я.. рассекаю на велосипедах.. по бездорожью.. против ветра.. в гору.. на лыжах. И сегодня я приглашаю вас прокатиться со мной вдоль и поперёк текстовых форматов данных и вместе спроектировать идеальный формат.
Я уже рассказывал о нём 5 лет назад, что привело к жарким дебатам, повлёкшим за собой небольшие изменения синтаксиса. Поэтому позвольте рассказать с чистого листа что он представляет из себя на текущий момент.
Спикер \Дмитрий Карловский
Место \PiterJS #47
Время 2020-05-20
Это - расширенная текстовая версия одноимённого выступления на PiterJS#47. Вы можете читать её как статью, либо открыть в интерфейсе проведения презентаций, либо посмотреть видео.
- Проанализировать популярные текстовые форматы данных 💩
- С нуля разработать новый формат без недостатков 👽
- Показать примеры применения нового формата 👾
Сравнивать мы будем 5 форматов.
Формат |
---|
XML |
JSON |
YAML |
TOML |
Tree |
Про первые три не слышал только глухой. А вот два последних для многих - тёмные лошадки. Ну ничего, сегодня я пролью на них свет.
XML - некогда самый популярный формат, можно сказать "технологический стандарт". Но не смотря на всю свою мощь, сейчас он изживает своё, так как является слишком сложным для современного веб-разработчика.
<!DOCTYPE svg
PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"
>
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg version="1.1" xmlns="http://www.w3.org/2000/svg">
<circle r="30" cx="50" cy="50" fill="orange" />
</svg>
На смену XML приходит более простой и дерзкий формат данных - JSON.
{
"name": "example",
"version": "1.0.0",
"description": "example package",
"main": "index.js",
"repository": "https://example.org",
"author": "anonymous",
"license": "MIT"
}
Если вы считаете, что вот он, идеал, то прошу меня заранее извинить, так как далее я буду вас расстраивать.
Кто-то уже пророчит YAML на смену JSON.
Date: 2001-11-23 15:03:17 -5
User: ed
Fatal:
Unknown variable "bar"
Where:
file: TopClass.py
line: 23
code: |
x = MoreObject("345\n")
Благодаря лучшей человекочитаемости он уже обрёл популярность в сфере ручного написания конфигурационных файлов.
Про TOML же мало кто слышал. Однако, взгляните на пример и вам станет ясно, почему я о нём вообще упоминаю.
[servers]
[servers.alpha]
ip = "10.0.0.1"
dc = "eqdc10"
[servers.beta]
ip = "10.0.0.2"
dc = "eqdc10"
Да, это фактически, стандартизированный INI-конфиг, которого покусал JSON. В результате чего он вобрал в себя худшее из обоих миров.
Наконец, в качестве спойлера, позвольте показать вам минимальный не пустой файл в формате Tree, который мы и будем разрабатывать далее.
spoiler
Разные форматы основаны на разных моделях данных. Выбранная модель отвечает на следующие два вопроса.
- Какие данные мы можем записать и прочитать без бубна? 🥁
- Как записывать данные не вписывающиеся в модель? 👠
Ни один формат не способен поддержать всё многообразие типов предметных областей, поэтому неизбежно возникает необходимость упаковки данных в некоторый формат и последующей обратной распаковки.
XML основан на модели типизированных элементов в которых находится один словарь атрибутов и один список вложенных типизированных узлов.
- NodeList
- Element Node (
<br/>
) - Attribute Node (
tabindex="1"
) - Text Node (
Hello, World!
) - CDATA Node (
<![CDATA[ ... ]]>
) - Processing Instruction Node (
<? ... ?>
) - Comment Node (
<!-- ... -->
) - Document Node
- Document Type Node (
<!DOCTYPE html>
)
Это довольно гибкая модель, однако она имеет ряд ограничений: значениями атрибутов могут быть только строки, а вложенный список узлов может быть только один. Не смотря на то, что формат XML и так не самый простой, банальный словарь с поддеревьями в качестве значений требует дополнительных соглашений. Например, такого: некоторые элементы используются для описания ключей в родительском элементе и такие элементы в родительском должны быть лишь в одном экземпляре.
<panel>
<head>Вы уверены?</head>
<body>
<button>Да</button>
<button>Нет</button>
</body>
</panel>
Тут panel
- это компонент, а body
- уже не компонент, а параметр. Ему бы место в атрибутах, да только в атрибуты можно лишь строки помещать и ничего более.
Благодаря пространствам имён, в рамках одного XML документа могут вперемешку идти множество языков, не ломая интерпретацию друг друга.
<xsl:stylesheet
version="1.0"
xmlns="http://www.w3.org/1999/xhtml"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:template match="/">
<html>
<head>
<link rel="stylesheet" href="web.css" />
</head>
<body>
<xsl:apply-templates select="*" />
</body>
</html>
</xsl:template>
</xsl:stylesheet>
Это - очень мощная техника, которой не хватает в более молодых форматах.
Модель JSON основана на том, что всё дерево состоит из не типизированных списков и словарей. Плюс ограниченный набор примитивов в качестве листьев дерева.
- Null
- Boolean
- Number
- String
- Array
- Dictionary
Наивно было бы полагать, что двух типов структурных узлов хватит для всего. Например, возьмём словарь. Ключи в нём не упорядочены, то есть могут возвращаться парсером в любом порядке.
{
"foo": 777,
"bar": 666
}
А если нам нужен словарь с упорядоченными ключами?
[
[ "foo" , 777 ],
[ "bar" , 666 ]
]
Нам пришлось кардинально поменять синтаксис и налепить массивы массивов. А ведь это всего-лишь другой тип словаря.
Ну и самый главный недостаток модели JSON в её нерасширяемости, из-за чего приходится вводить кучу хитрых правил, чтобы упихнуть всё многообразие прикладных типов их отношений. Возьмём для примера запрос к MongoDB, авторы которой решили, что JSON отлично походит на роль языка запросов.
{
"$or": [
{
"sex": "female",
"age": { "$gt": 16 },
},
{
"hobby": {
"$regex": "\\b(?:java|type)script\\b"
}
}
]
}
Мы видим, что парные логические операции OR и AND имеют совершенно различный синтаксис. Предиката равенства катастрофически не хватает, ведь нужны ещё предикаты "больше", "меньше" и даже "соответствует регулярному выражению". И, кстати, сами регулярные выражения не представимы в JSON иначе как в виде строки и соглашения, что если она находится в словаре для ключа с именем "$regexp", то это сериализованная регулярка и при парсинге нужно создать соответствующий объект.
Модель YAML во многом аналогична модели JSON. Разве что тут есть поддержка времени и внутренних ссылок.
- !!null
- !!bool
- !!int
- !!float
- !!str
- !!timestamp
- !!seq
- !!map
- Anchor & Alias
- Document
- TypeTags
Главное преимущество YAML в аннотациях типа, позволяющих объяснять процессору какой алгоритм использовать для распаковки данных.
--- !!omap
- foo: 777
- bar: 666
В данном примере мы говорим парсеру "возьми этот список пар ключ-значение" и преобразуй его в объект OrderedMap (упорядоченный словарь).
Модель TOML как у JSON, но чуть более приземлённая. Например, тут различаются целые и вещественные числа, что важно для компилируемых языков, а так же есть поддержка времени.
- Boolean
- Integer
- Float
- String
- DateTime
- Array
- Dictionary
С расширяемостью же тут всё так же плохо, как и в JSON.
Какой бы набор базовых типов мы ни выбрали, его не хватит для всего. А значит неизбежно потребуется некоторый код упаковки и распаковки. А работать с таким кодом проще всего, когда число разных типов узлов минимально, так как для каждого типа требуется писать отдельную ветку логики. В то же время гибкость требуется максимальная. Поэтому нам хватит всего двух типов узлов.
- Struct Node
- Data Node
Структурные узлы служат для описания иерархии, а узлы данных хранят сырые бинарные данные. Любой узел может хранить в себе список любых других узлов, чем достигается недостижимая в иных форматах гибкость.
Итого, по расширяемости всё очень плохо. Популярные форматы либо расширяемые, но неимоверно переусложнённые, либо простые, но совершенно не расширяемые.
XML | JSON | YAML | TOML | Tree | |
---|---|---|---|---|---|
Расширяемость | ✅ | ❌ | ✅ | ❌ | ✅ |
Число паттернов | 90 | 30 | 210 | 90 | 10 |
Обратите внимание на YAML. Его грамматика насчитывает две сотни паттернов. Он настолько сложен, что вы скорее всего не найдёте ни одной полной и правильной реализации его парсера. Да что уж там, даже два одинаково работающих парсера JSON нужно ещё поискать, а ведь там всего казалось бы 30 паттернов.
Нашей целью же будет создание предельно простого, не допускающего разночтений, но в то же время максимально расширяемого формата.
Наглядность синтаксиса важна при самых различных сценариях работы с форматом: при написании, при ревью кода, при разрешении конфликтов, при отладке, при изучении.
Скорость вашей работы и предсказуемость её результатов напрямую зависит от способа сериализации формата. Однако у некоторых форматов с этим серьёзные проблемы.
XML | JSON | YAML | TOML | Tree | |
---|---|---|---|---|---|
Удобочитаемость | ❌ | ❌ | ✅ | ✅ | ✅ |
XML построен вокруг текста, внутрь которого вкрапляются теги с дополнительной информацией. Пока этой информации не много, всё хорошо, но чем её больше, тем сложнее воспринимать текст, что нивелирует полезность этой фичи.
Привет, Алиса!
Как дела?
Не могла бы ты принести мне сейчас кофе?
<message>
<greeting>
Привет, <a href="http://example.org/user/alice">Алиса</a>!
</greeting>
<body>
<s>Как дела?</s><br/>
Не могла бы ты принести мне
<time datetime="1979-10-14T12:00:00.001-04:00">сейчас</time>
кофе?
</body>
</message>
XML хотя бы поддерживает многострочный текст, а вот JSON, например, этим похвастаться уже не может. Форматы этого типа идут от информационной структуры, в которую уже вкрапляются текстовые и не только текстовые значения.
{ "greetings": "Привет, Алиса!\nКак дела?\nНе могла бы ты принести мне кофе?\n" }
Как правило с пониманием написанного нет никаких проблем. Но YAML тут отличился.
XML | JSON | YAML | TOML | Tree | |
---|---|---|---|---|---|
Однозначный синтаксис | ✅ | ✅ | ❌ | ✅ | ✅ |
a: true # boolean
b: tru # string
c: (-: # error
d: :-) # string
Вот таких приколов в YAML довольно много.
Близкая к читаемости тема - это экранирование. Наличие оного в той или иной мере неизбежно приводит к снижению читаемости. При разработке экранирования стоит иметь ввиду следующие моменты.
- Нужно отличать конструкции формата от собственно данных 😵
- Желательно не терять в наглядности данных 🤓
- Желательно не переусложнять редактирование 🤬
XML - чудесный пример, как делать экранирование не надо.
foo > 0 && foo < 10
Из простого и наглядного текста получается какой-то криптотекст, который приходится мысленно интерпретировать, чтобы понять что тут написано.
<code>foo > 0 && foo < 10</code>
Похожая проблема есть и в JSON, хоть и в меньшей мере. Если вы когда-нибудь писали плагины для подсветки синтаксиса VSCode, то знаете, что грамматики там описываются именно в JSON формате, куда записываются регулярные выражения.
/"[\s\S]*"/
Регулярки и сами по себе не самые наглядные штуки, а заэкранированные и того хуже. Допустить в них ошибку в таких условиях очень просто, а дебажить это не очень-то легко.
"\"[\\s\\S]*\""
В YAML проблему экранирования в целом решили, но какой ценой.
- 5 типов строк 😣
- 4 модификатора обработки пробелов 😥
И всё это вам нужно знать, чтобы правильно прочитать любой YAML файл.
Нет 🤪
Самое удобочитаемое экранирование - это отсутствие экранирования. Поэтому у нас его не будет. Вы возможно подумали, что я сошёл с ума, но чуть позже я покажу, как этого добиться.
Многие форматы поддерживают различные способы форматирования одних и тех же данных. Но это всегда компромисс между размером и удобочитаемостью.
- Читаемое форматирование много весит 🐘
- Компактное форматирование плохо читается 💀
<users>
<user>
<name>Alice</name>
<age>20</age>
</user>
</users>
Если минифицировать XML, то можно сэкономить несколько десятков процентов в размере, но результат получается ещё сложнее читать.
<!-- 13% less -->
<users><user><name>Alice</name><age>20</age></user></users>
{
"users": [
{
"name": "Alice",
"age": 20
}
]
}
С JSON экономия чуть больше, но и читаемость страдает сильнее - вместо закрывающих тегов мы видим вереницу квадратных и фигурных скобочек.
// 30% less
{"users":[{"name":"Alice","age":20}]}
Нет 😲
Наш путь бескомпромиссный - формат должен быть одновременно и предельно компактным, и легко воспринимаемым человеком.
XML | JSON | YAML | TOML | Tree | |
---|---|---|---|---|---|
Читаемый | 195% | 140% | 125% | 110% | 100% |
Минифицированный | 170% | 101% | - | - | - |
Скачать файлы примеров.
Как видите, можно сделать формат, который в читаемом виде весит меньше, чем любой другой, даже если их минифицировать. Весь секрет в том, чтобы читаемость достигалась самой структурой формата, и не требовала дополнительного форматирования, раздувающего объём.
Частая проблема при работе с различными форматами - это бесконечные споры о, казалось бы, мелочах.
- Табы или пробелы? 🤼♂️
- 2 или 4 пробела? 🤼♀️
- возврат каретки нужен? ⚡
- выравнивание делаем? 🤺
- правила линтера/форматера? 🔥
- при сохранении/комите/пуше? 🚧
Эти споры отнимают время и эмоции, но они совершенно бессмысленны. Лучше, если формат будет иметь единые, чётко заданные правила, которые одинаково понимаются любым инструментом и человеком. Поэтому наш формат будет предельно жёстким, без каких-либо вольностей.
Простота, жёсткость и отсутствие экранирования потенциально даёт куда большую возможную скорость обработки.
Например, в JSON, чтобы записать произвольную строку, нужно пройтись по каждому символу и перед определёнными вывести в выходной буфер обратную косую черту. То есть мы даже не можем заранее узнать сколько памяти нам на выделить для выходного буфера. А во время парсинга нужно делать обратную операцию с формированием новой строки. Мы не можем переиспользовать исходный кусок памяти.
serialization: foo\bar => "foo\\bar"
parsing: "foo\\bar" => foo\bar
Когда же у нас нет экранирования, мы можем просто брать куски памяти и как есть отправлять в выходной поток при сериализации, что очень быстро. И наоборот, при парсинге мы можем просто ссылаться на куски исходного буфера и не делать лишних выделений памяти.
Во время парсинга часто теряется информация об исходном расположении получаемых из формата узлов. Например, мы получили JSON, начали его обработку, и где-то в глубине вдруг поняли, что в базе данных у нас нет того пользователя, что указан в файле. В этот момент мы должны показать ошибку, но в тексте этой ошибки мы не можем указать в каком месте какого именно файла она допущена. Всё потому, что эта информация при парсинге теряется. И это весьма распространённая проблема.
XML | JSON | YAML | TOML | Tree | |
---|---|---|---|---|---|
Адрес | ✅ | ❌ | ❌ | ❌ | ✅ |
Позиция | ❌ | ❌ | ❌ | ❌ | ✅ |
Диапазон | ❌ | ❌ | ❌ | ❌ | ✅ |
В XML-узлах есть ссылка на ресурс из которого он получен, но где он в этом ресурсе - ищите глазами. Для решения этой проблемы есть специальные парсеры, которые дают на выходе не массивы и словари, а Абстрактное Синтаксическое Дерево. Но работать с ним уже не так-то просто, да ещё и медленно это дело.
Чтож, информация эта важная, и я предлагаю её не терять. Никогда не терять. Сохранение координат узлов нам ещё пригодится, когда речь пойдёт об AST и сорсмапах.
Бывает, что данных много, а памяти мало, но работать с данными нужно быстро. А бывает, что данные вообще не кончаются. Например, вам нужно непрерывно обрабатывать логи по мере их поступления. В этих случаях спасают возможности по поточной обработке данных.
XML | JSON | YAML | TOML | Tree | |
---|---|---|---|---|---|
Поточная обработка | ❌ | ❌ | ✅ | ✅ | ✅ |
Как видно, самые распространённые форматы не имеют поддержки поточной обработки. Они требуют, чтобы у вас был ровно один завершённый корень документа, иначе - ошибка парсинга. В случае постоянно поступающих данных типа логов, например, дописывать их в документ, сохраняя его корректность - задача не из простых.
Это не значит, что к ним нельзя прикрутить поточную обработку. Например, для XML есть более низкоуровневые SAX парсеры, позволяющие вам работать не с деревом элементов, а с потоком тегов: открылся такой-то тег, пришла строка, закрылся такой-то тег. А для JSON есть целая вязанка протоколов стриминга сообщений. Основная проблема тут в том, что далеко не любой поддерживающий формат инструмент сможет переварить ваши данные без дополнительных телодвижений.
Форматы же поддерживающие поточную обработку, можно легко дополнять дописыванием данных в конец. Можно склеивать несколько потоков данных в один и, наоборот, нарезать на части. Можно обрабатывать по частям, не дожидаясь завершения передачи. И всё это без потери корректности работы с форматом.
Что ж, резюмируя ранее сказанное, давайте сформулируем все требования для нашего нового формата.
- Простота синтаксиса ✌
- Никакого экранирования 🤘
- Никаких вольностей 🤙
- Никакой минификации 👍
- Минимальный размер 👐
- Гарантированная читаемость 🖖
- Поточная обработка 💪
- Точные координаты узлов ☝
Итак, нам нужно создать узел с именем "house". Какой минимальный код для этого нужен?
house
Просто пишем это имя и всё.
А если нам нужен не один узел, а целый список?
house
roof
wall
door
window
floor
Просто пишем их на отдельных строках.
Но что если мы хотим добавить иерархичности и поместить список узлов внутрь первого?
house
roof
wall
door
window
floor
Просто пишем вложенные узлы с табом в качестве отступа. Знакомые с языком Python тут могут заметить похожий подход - использование хорошего стиля форматирования кода в качестве основы синтаксиса, а не опциональной возможности.
Продолжая добавлять отступы мы можем создавать иерархии любой вложенности.
house
roof
wall
door
window
glass
floor
Часто бывают ситуации, когда вложенный узел только один и тогда увеличивать из-за него уровень отступа для всех вложенных в него узлов будет как-то расточительно.
street
house
wall
door
window
Поэтому просто выстраиваем такие узлы в одну линию, разделяя пробелами.
street house wall
window
door
Узлы же записанные с отступом уже вкладываются в последний узел на предыдущей линии.
Когда же нам нужно записать произвольные данные, символы в которых не должны как-то по особому обрабатываться, просто пишем их после обратной косой черты без какого-либо экранирования.
\Любые данные \(^_^)/
Обратная косая черта выбрана для ассоциации с экранированием. Она как бы экранирует весь текст до конца строки. Но, если быть точными, то это скорее не экранирование, а своеобразные кавычки. Обратная косая черта - открывающая, а символ перевода строки - завершающая.
Но как записать всё же многострочный текст содержащий в том числе и символы перевода строки? Всё просто: берём узел данных и помещаем в него список других узлов данных.
\
\Тут 🐱💻
\ много 🐱👓
\ котиков 🐱👤
При запросе строкового содержимого корневого узла данных все вложенные узлы данных будут соединены через символ перевода строки.
Наконец, оба типа узлов мы можем использовать вперемешку в любых комбинациях. Например, опишем некоторого пользователя.
user
name \Jin
age \35
hobby
\kendo 🐱👤
\dance 🕺🏽
\role play 🎭
default
Как видите, всё довольно просто. Для создания самого продвинутого формата данных нам потребовалось всего 2 типа узлов и 4 спецсимвола.
Пока что мы говорили лишь про форматы, то есть про способы сериализации. На их основе уже проектируются языки, добавляющие семантику абстрактным узлам формата.
Формат | Языки |
---|---|
XML | XHTML, SVG, XSLT, ... |
JSON | JSON Schema, json:api, ... |
YAML | yaml.org/type |
TOML | - |
Tree | xml.tree, json.tree, view.tree, ... |
Любой язык - это некоторое подмножество модели данных формата с ограничениями на возможные типы узлов, их взаимное расположение и содержимое.
Далее я покажу несколько примеров таких языков для формата tree.
Язык grammar.tree - предназначен для описания формальных грамматик. К примеру, давайте напишем полную формальную грамматику собственно формата tree.
tree .is .optional .list_of line
line .is .sequence
.optional indent
.optional nodes
new_line
nodes .is .sequence
.optional .list_of struct
.optional data
.with_delimiter space
struct .is .list_of .byte
.except special
data .is .sequence
data_prefix
.optional .list_of .byte
.except new_line
special .is .any_of
new_line
data_prefix
indent
space
new_line .is .byte \0A
indent .is .list_of .byte \09
data_prefix .is .byte \5C
space .is .list_of .byte \20
Как видите, грамматика формата реально предельно простая, что позволяет буквально за час написать парсер на любом языке не прибегая даже к генераторам парсеров.
Читать такую грамматику можно буквально: tree - это опциональный список линий, а линия - это последовательность из опционального отступа, опционального списка узлов и обязательного символа перевода строки. Ну и так далее.
Сравнивая grammar.tree с Расширенной Формой Бэкуса Наура можно обратить внимание, что первый несколько многословен, но понятен и лаконичен, а последний - компактен, но для понимания требует предварительной подготовки, выразительные возможности всё же несколько уступают, а его ориентация на однострочное представление выглядит несколько неуклюже при многострочной записи.
tree .is .optional .list_of line
line .is .sequence
.optional indent
.optional nodes
new_line
nodes .is .sequence
.optional .list_of struct
.optional data
.with_delimiter space
tree = { line };
line = [ indent ],
[ nodes ],
new_line;
nodes = data |
struct,
{ space , struct },
[ space , data ];
Язык xml.tree - это способ представления модели данных XML в tree формате. Из него можно генерировать любого вида XML. И наоборот, любой XML может быть сконвертирован в xml.tree.
! doctype html
html
meta @ charset \utf-8
link
@ href \web.css
@ rel \stylesheet
script @ src \web.js
body
h1 \Procter & Gamble
<!doctype html>
<html>
<meta charset="utf-8" />
<link href="web.css" rel="stylesheet" />
<script src="web.js"></script>
<body>
<h1>Procter & Gamble</div>
</body>
</html>
Было бы классно иметь такую интеграцию в IDE, чтобы открывая любой XML можно было видеть и редактировать его xml.tree представление, но сохранялось бы всё обратно в XML. Это позволило бы больше не ломать глаза об амперсанды и позволило бы работать с XML так же легко и просто, как и, например, с markdown.
А json.tree - это язык для описания модели json.
* user *
name \Jin
age 35
hobby /
\kendo 🐱👤
\dance 🕺🏽
home \C:\users\jin\
{
"user": {
"name": "Jin",
"age": 35,
"hobby": [
"kendo 🐱👤",
"dance 🕺🏽",
],
"home": "C:\\users\\jin\\"
}
}
Нам потребовалось лишь 2 спецсимвола - звёздочка для обозначения словарей и косая черта для обозначения массивов.
Прелесть языков, основанных на таких форматах как XML и Tree в том, что их легко расширять оставаясь в рамках формата. Например, и json, и tree как форматы принципиально не поддерживают комментарии. Но, например, в конфигах комментарии необходимы. Как же быть?
*
# \If disabled will be used platform specific delimiters
# \CRLN on windows and LN on others
unix_delimiters true
В tree мы легко расширили язык под наши нужды, добавив специальный тип узла для комментариев.
{
"unix_delimiters#1": "If disabled will be used platform specific delimiters",
"unix_delimiters#2": "CRLN on windows and LN on others",
"unix_delimiters": true,
}
В JSON же сказывается ограниченность модели, из-за которой приходится писать костыли.
Язык view.tree - используется для композиции компонент в разработанном мной фреймворке $mol.
$my_details $mol_view
sub /
<= Pager $mol_paginator
value?val <=> page?val 0
Тут описан компонент, который владеет другим компонентом и их свойства двусторонне связаны друг с другом. Можете обратить внимание, что внутри view.tree используются в том числе и язык json.tree для описания массивов, словарей, чисел и прочих JSON типов.
Из такого простого и лаконичного кода генерируется довольно развесистый TypeScript класс. Писать его руками можно, но муторно и без иерархии не очень наглядно.
class $my_details extends $mol_view {
sub() { return [ this.Pager() ] }
@ $mol_mem Pager() {
const Pager = new $mol_paginator
Pager.value = val => this.page( val )
return Pager
}
@ $mol_mem page( val = 0 ) {
return val
}
}
Наконец, есть различные API для взаимодействия с форматом из разных языков программирования.
Формат | Языки | API |
---|---|---|
XML | XHTML, SVG, XSLT, ... | DOM, SAX, AST |
JSON | JSON Schema, json:api, ... | Native , AST |
YAML | yaml.org/type | Native , AST |
TOML | - | Native , AST |
Tree | xml.tree, json.tree, ... | AST |
Для XML, например, есть довольно гибкий DOM, а есть низкоуровневый SAX. Форматы, пришедшие ему на смену, в основном возвращают нативные для языка словари, массивы и тд. Правда модель данных JSON не очень хорошо представляется в компилируемых языках, где целые числа и числа с плавающей точкой - это совершенно разные типы. Ну и разумеется для всех языков есть представление в виде Абстрактного Синтаксического Дерева. Правда обычно оно медленное и неудобное. Мы же сделаем это быстрым и удобным, что позволит нам не городить зоопарк несовместимых API.
Возьмём простой JSON файл и засунем его в ASTExplorer.
{
"user": {}
}
{
"type" : "Object",
"children" : [
{
"type" : "Property",
"key" : {
"type": "Identifier",
"value": "user"
}
"value": {
"type": "Object",
"children": []
}
}
]
}
Как видно, AST получился большим и сложным. JSON вообще очень плохо подходит для описания AST. Без специальных утилит с ним работать не очень просто.
Теперь давайте возьмём несколько более сложный tree файл.
user
name \Jin
age 35
hobby
\kendo 🐱👤
\dance 🕺🏽
\role play 🎭
И посмотрим на его AST.
user
name \Jin
age 35
hobby
\kendo 🐱👤
\dance 🕺🏽
\role play 🎭
Так, что-то не так. Это же тот же самый код. А, нет, всё правильно, tree - сам себе AST.
В реализация на TypeScript каждый узел имеет примерно следующий интерфейс.
interface $mol_tree2 {
type: string
value: string
kids: $mol_tree2[]
span: $mol_span
}
Span - это ссылка на серию байт в исходном ресурсе.
interface $mol_span {
uri: string
row: number
col: number
length: number
}
У каждого узла есть методы для создания новых узлов, на его основе. Эти фабрики, создавая новые узлы, просовывает в них span от оригинального узла. Это позволяет даже после десятков преобразований понять с чего всё началось.
interface $mol_tree2 {
struct : ( type , kids )=> $mol_tree2
data : ( value , kids )=> $mol_tree2
list : ( kids )=> $mol_tree2
clone : ( kids )=> $mol_tree2
}
Для примера, возьмём конфиг, найдём в нём пароль и если он не подойдёт - кинем исключение, где будет написано в каком месте какого файла написан неправильный пароль.
const config_path = './config.tree'
const config_text = fs.readFileSync( config_path )
const config = $mol_tree2.fromString( config_text , config_path )
// server auth
// login \root
// password \qwerty
const password = config.select( 'server' , 'auth' , 'password' , '' )
if( !auth( password.text() ) ) {
// AuthError: Wrong password
// \default
// ./config.tree#5:3-11
throw password.error( 'Wrong password' , AuthError )
}
Или другой пример - мы решили, что "auth" неудачное название и нужно заменить его на "credentials". Поэтому мы пишем не сложный скрипт для автоматического рефакторинга:
// server credentials
// login \root
// password \qwerty
const new_config = config.list(
config.hack({
'auth' : ( auth , context )=> [
auth.struct( 'credentials' , auth.hack( context ) ),
] ,
})
)
fs.writeFileSync( config_path , new_config )
И таким образом вы можете легко рефакторить любые языки, основанные на tree формате, без поиска для каждого языка отдельного парсера и разбирательства с тем, как у него происходит работа с AST.
Если вы пользуетесь редактором для которого ещё нет плагина, то это хорошая возможность реализовать его. Сделать это будет проще, чем для любого другого языка.
Опять же, призываю заинтересовавшихся реализовать поддержку в своём любимом языке и попробовать применить его с пользой.
XML | JSON | YAML | TOML | Tree | |
---|---|---|---|---|---|
Размер | 195% | 140% | 125% | 110% | 100% |
Число паттернов | 90 | 30 | 210 | 90 | 10 |
Однозначный синтаксис | ✅ | ✅ | ❌ | ✅ | ✅ |
Удобочитаемость | ❌ | ❌ | ✅ | ✅ | ✅ |
Не нужно экранирование | ❌ | ❌ | ❌ | ❌ | ✅ |
Точные координаты узлов | ❌ | ❌ | ❌ | ❌ | ✅ |
Поточная обработка | ❌ | ❌ | ✅ | ✅ | ✅ |
Расширяемая модель данных | ✅ | ❌ | ✅ | ❌ | ✅ |
Широкая распространённость | ✅ | ✅ | ✅ | ❌ | ❌ |
А теперь давайте пофантазируем, чего ещё интересного можно сделать используя tree формат.
- Запросы к СУБД
- Описание домена
- Логирование
- Общение консольных утилит
- LISP-подобный язык
- Универсальный AST
Помните неуклюжие запросы к MongoDB? Давайте попробуем написать свой SQL:
select
from $users
fetch
@name
@phone
@photo *
@uri
@width
@height
where or
and
@sex = female
@age > 16
@hobby ~ \\b(?:java|type)script\b
В такой форме запрос распарсить - плёвое дело, в отличие от настоящего SQL. Обратите внимание, что на единообразный синтаксис для логических операций и предикатов "равно", "больше" и даже "соответствует регулярке". Кстати, регулярку ведь тоже можно описать в формате tree, что сделает её куда более поддерживаемой.
select
from $users
fetch *
where @hobby ~
word-edge
or
\java
\type
\script
word-edge
Раз уж мы заговорили о базах данных. Примерно так я описываю модель предметной области.
hyoo_api_person
descr \Живой пользователь сервиса
inherit hyoo_api_entity
field
id
descr \Уникальный человекопонятный идентификатор
example \person=jin
key unique
type text
edit author
avatar
descr \Ссылки на аватары
type list hyoo_api_image
edit author
mail
descr \Привязанные имейлы
type set hyoo_api_mail
Из такого формального описания автоматически формируется серверный API, правила ACL, схема СУБД и админка для управления всем этим делом.
Распространённая практика выводить в логи однострочные сообщения. Пока они влезают по ширине в ваш терминал - всё хорошо, но это довольно редкая ситуация. Куда чаще сообщения всё же не влезают и начинают переноситься, превращая поток сообщений в настоящее месиво, которое и глазами сложно прочитать, да и программно обрабатывать их - боль и страдания.
А что если логи сразу выводить в двумерном виде, одновременно легко читаемом как машинами, так и человеком?
193.34.12.132 - - [2011-10-20T12:46:08+04:00] GET /nin-jin/slides/edit/master/t
ree/readme.md HTTP/1.1 200 4435
193.34.12.132 - - [2011-10-20T12:46:09+04:00] GET /nin-jin/slides/edit/master/t
ree/readme.html HTTP/1.1 404 4435
access
ip \193.34.12.132
time \2011-10-20T12:46:08+04:00
method \GET
uri \/nin-jin/slides/edit/master/tree/readme.md
protocol \HTTP/1.1
response \200
size \4435
Можно написать утилиты, которые бы позволили просто и эффективно обрабатывать такие логи. Например, прочитаем лог, отфильтруем по значению одного из полей, выберем из сообщений лишь интересные нам поля и выведем их табличкой.
> cat access.log.tree | pick ip time method uri | table
\193.34.12.132 2011-10-20T12:46:08+04:00 GET /index.html
\193.34.12.132 2011-10-20T12:46:10+04:00 GET /index.css
\193.34.12.132 2011-10-20T12:46:20+04:00 GET /index.js
> cat access.log.tree | filter time >= 2019-09 | pick ip uri | table
\193.34.12.132 /index.html
\193.34.12.132 /index.css
\193.34.12.132 /index.js
У меня есть прототип такой утилиты, который я иногда использую для просмотра логов дев-сервера в реальном времени. Будет классно, если кто-то возьмётся реализовать полный комплект инструментария. А когда будут инструменты, тогда и у разработчиков софта будет мотивация писать логи не как попало, а структурированно.
Можно пойти дальше и не просто писать логи в формате tree, а в принципе продвинуть идею, что вывод любой программы должен быть структурированным. У многих утилит есть флаги для вывода ответа в виде JSON или XML, но человеку читать такой вывод напряжно - приходится переоткрывать выдачу в инструментах наглядного представления, чтобы понять что там возвращается и как этому подступиться. Только представьте себе мир, где выдачу можно прочитать и тут же как-то её преобразовать, не ковыряя маны в поисках нужной комбинации ключей очередной программы.
> git log
commit
message \$mol_style: TS@3.9 compatibility
sha \b1a8f07c839604d0d34430a186246f0c1f71e628
date \2020-05-15T23:24:32+0300
author \nin-jin <sairi-na-tenshi@ya.ru>
commit
message \$mol_regexp: concurent parse ability
sha \be1abfa50542728dd5c156517ea31f469e7fb4d4
date \2020-05-15T23:03:30+0300
author \nin-jin <nin-jin@ya.ru>
> git log | pick date message | table
\2020-05-15T23:24:32+0300 $mol_style: TS@3.9 compatibility
\2020-05-15T23:03:30+0300 $mol_regexp: concurent parse ability
WebAssembly - перспективный ассемблер, опускающийся настолько близко к машине на сколько это возможно без потери портабельности. Для него есть текстовый формат представления, основанный на лисповых s-expressions.
(func $fact (param $x i64) (result i64)
(if $x (result i64)
(i64.eqz
(local.get $x))
(then
(i64.const 1))
(else
(i64.mul
(local.get $x)
(call $fact
(i64.sub
(local.get $x)
(i64.const 1)))))))
Его сложно воспринимать как ни форматируй. К сожалению, именно такого рода код вы будете видеть при дизассемблировании в браузерных девтулзах.
Я сейчас работаю над компилятором в байт коды более наглядного wasm.tree описания.
func
name $fact
param $x i64
result i64
body switch
test i64.eqz local.get $x
then i64.const 1
else i64.mul
local.get $x
call $fact i64.sub
local.get $x
64.const 1
Из этого ассемблера генерится список байт-кодов на языке bin.tree, который уже элементарной функцией перегоняется в бинарник.
00
61
73
6d
01
00
00
00
.
.
.
Когда будет что-то более-менее завершённое - попробую протолкнуть этот синтаксис в качестве WAT2.0. Кому не безразлична судьба WebAssembly - присоединяйтесь к разработке.
На самом деле писать на сыром ассемблере слишком многословно. Поэтому следующим шагом идёт реализация мета-языка, позволяющего расширять язык средствами самого этого же языка. Ядро такого языка должно получиться предельно минималистичным, а все идиомы в него будут подключаться как сторонние библиотеки, написанные на этом же языке.
jack
import wasm
tree func $fact
> $x #8
< #8 switch
test is-zero $x
then #8 1
else mul
$x
$fact sub
$x
#8 1
Грубо говоря, программа на этом языке итеративно модифицирует свой собственный AST таким образом, что на выходе получается wasm-бинарник. Звучит, возможно, пугающе, но благодаря тому, что tree сохраняет координаты исходников, проследить источник ошибки не составляет труда. В репозитории можно глянуть куцый прототип.
Можно пойти ещё дальше и генерировать не wasm байткоды, а прямо таки байткоды целевого процессора, просто добавив ещё один трансформер в пайплайн.
compile pipelines:
jack.tree => wasm.tree =============> bin.tree
jack.tree => wasm.tree => arm.tree => bin.tree
any-dsl.tree => jack.tree => wasm.tree => arm.tree => bin.tree
При этом на любом уровне можно запускать дополнительные трансформеры, которые смогут оптимизировать код, применяя информацию, доступную на соответствующих уровнях абстракции.
optimization midlewares:
jack.tree => jack.tree
wasm.tree => wasm.tree
arm.tree => arm.tree
При этом, напомню, мы не теряем связь с оригинальными исходниками, что позволит выводить адекватные сообщения. А любое промежуточное AST можно всегда сдампить в текст в весьма наглядной форме tree формата.
Опять же, присоединяйтесь к разработке, это может получиться крутая штука на замену LLVM.
Ну и, наконец, мы подошли ко главной мысли этого доклада. Tree - это прям идеальный кандидат на место универсального связующего AST. Вы только посмотрите, какой длинный пусть проходит TypeScript код от исходников до результирующего бандла при сборке на типичном проекте.
code =(P)=> loader =(P)=> compiler =(SP)=> bundler =(SP)=> terser =(S)=> bundle
P - Parse
S - Serialize
И каждый инструмент заново парсит ваши исходники в своё AST, обрабатывает, сериализует и передаёт далее. Если же договориться о едином формате AST, то можно значительно упростить реализацию утилит и снизить накладные расходы на обработку кода.
code =(P)=> loader =====> compiler ======> bundler ======> terser =(S)=> bundle
Даже если часть утилит будут запускаться в отдельных процессах (а значит промежуточная сериализация неизбежна), формат tree позволит передавать AST максимально быстро, за счёт минимальных накладных расходов на парсинг и сериализацию.
Надеюсь мне удалось заразить вас идеями о светлом будущем. Но чтобы его приблизить нам вместе надо над этим поработать. Один я, боюсь, всё это не вытяну. Так что пишите, зовите и не пропадайте.
- Эти слайды: nin-jin/slides/tree
- Всё о Tree: nin-jin/tree.d
- Чат о языках: h_y_o_o
- Связь со мной: nin_jin