21.05.2020 21:27
nin-jin 22 2200 Источник

Здравствуйте, меня зовут Дмитрий Карловский и я… рассекаю на велосипедах… по бездорожью… против ветра… в гору… на лыжах. И сегодня я приглашаю вас прокатиться со мной вдоль и поперёк текстовых форматов данных и вместе спроектировать идеальный формат.


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


Спикер \Дмитрий Карловский
Место \PiterJS #47
Время 2020-05-20

Это — расширенная текстовая версия одноимённого выступления на PiterJS#47. Вы можете читать её как статью, либо открыть в интерфейсе проведения презентаций, либо посмотреть видео.


План


  • Проанализировать популярные текстовые форматы данных
  • С нуля разработать новый формат без недостатков
  • Показать примеры применения нового формата

Форматы


Сравнивать мы будем 5 форматов.


Формат
XML
JSON
YAML
TOML
Tree

Про первые три не слышал только глухой. А вот два последних для многих — тёмные лошадки. Ну ничего, сегодня я пролью на них свет.


Пример XML


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>

Пример JSON


На смену XML приходит более простой и дерзкий формат данных — JSON.


{
    "name": "example",
    "version": "1.0.0",
    "description": "example package",
    "main": "index.js",
    "repository": "https://example.org",
    "author": "anonymous",
    "license": "MIT"
}

Если вы считаете, что вот он, идеал, то прошу меня заранее извинить, так как далее я буду вас расстраивать.


Пример YAML


Кто-то уже пророчит 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


Про TOML же мало кто слышал. Однако, взгляните на пример и вам станет ясно, почему я о нём вообще упоминаю.


[servers]

[servers.alpha]
ip = "10.0.0.1"
dc = "eqdc10"

[servers.beta]
ip = "10.0.0.2"
dc = "eqdc10"

Да, это фактически, стандартизированный INI-конфиг, которого покусал JSON. В результате чего он вобрал в себя худшее из обоих миров.


Пример Tree


Наконец, в качестве спойлера, позвольте показать вам минимальный не пустой файл в формате Tree, который мы и будем разрабатывать далее.


spoiler

Модели данных


Разные форматы основаны на разных моделях данных. Выбранная модель отвечает на следующие два вопроса.


  • Какие данные мы можем записать и прочитать без бубна?
  • Как записывать данные не вписывающиеся в модель?

Ни один формат не способен поддержать всё многообразие типов предметных областей, поэтому неизбежно возникает необходимость упаковки данных в некоторый формат и последующей обратной распаковки.


Модель XML


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


Это довольно гибкая модель, однако она имеет ряд ограничений: значениями атрибутов могут быть только строки, а вложенный список узлов может быть только один. Не смотря на то, что формат XML и так не самый простой, банальный словарь с поддеревьями в качестве значений требует дополнительных соглашений. Например, такого: некоторые элементы используются для описания ключей в родительском элементе и такие элементы в родительском должны быть лишь в одном экземпляре.


<panel>
    <head>Вы уверены?</head>
    <body>
        <button>Да</button>
        <button>Нет</button>
    </body>
</panel>

Тут panel — это компонент, а body — уже не компонент, а параметр. Ему бы место в атрибутах, да только в атрибуты можно лишь строки помещать и ничего более.


Расширяемость модели XML


Благодаря пространствам имён, в рамках одного 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


Модель JSON основана на том, что всё дерево состоит из не типизированных списков и словарей. Плюс ограниченный набор примитивов в качестве листьев дерева.


  • Null
  • Boolean
  • Number
  • String
  • Array
  • Dictionary

Недостатки модели JSON


Наивно было бы полагать, что двух типов структурных узлов хватит для всего. Например, возьмём словарь. Ключи в нём не упорядочены, то есть могут возвращаться парсером в любом порядке.


{
    "foo": 777,
    "bar": 666
}

А если нам нужен словарь с упорядоченными ключами?


[
    [ "foo" , 777 ],
    [ "bar" , 666 ]
]

Нам пришлось кардинально поменять синтаксис и налепить массивы массивов. А ведь это всего-лишь другой тип словаря.


Нерасширяемость модели JSON


Ну и самый главный недостаток модели JSON в её нерасширяемости, из-за чего приходится вводить кучу хитрых правил, чтобы упихнуть всё многообразие прикладных типов их отношений. Возьмём для примера запрос к MongoDB, авторы которой решили, что JSON отлично походит на роль языка запросов.


{
    "$or": [
        {
            "sex": "female",
            "age": { "$gt": 16 },
        },
        {
            "hobby": {
                "$regex": "\\b(?:java|type)script\\b"
            }
        }
    ]
}

Мы видим, что парные логические операции OR и AND имеют совершенно различный синтаксис. Предиката равенства катастрофически не хватает, ведь нужны ещё предикаты "больше", "меньше" и даже "соответствует регулярному выражению". И, кстати, сами регулярные выражения не представимы в JSON иначе как в виде строки и соглашения, что если она находится в словаре для ключа с именем "$regexp", то это сериализованная регулярка и при парсинге нужно создать соответствующий объект.


Модель YAML


Модель YAML во многом аналогична модели JSON. Разве что тут есть поддержка времени и внутренних ссылок.


  • !!null
  • !!bool
  • !!int
  • !!float
  • !!str
  • !!timestamp
  • !!seq
  • !!map
  • Anchor & Alias
  • Document
  • TypeTags

Расширяемость модели YAML


Главное преимущество YAML в аннотациях типа, позволяющих объяснять процессору какой алгоритм использовать для распаковки данных.


--- !!omap
- foo: 777
- bar: 666

В данном примере мы говорим парсеру "возьми этот список пар ключ-значение" и преобразуй его в объект OrderedMap (упорядоченный словарь).


Модель TOML


Модель TOML как у JSON, но чуть более приземлённая. Например, тут различаются целые и вещественные числа, что важно для компилируемых языков, а так же есть поддержка времени.


  • Boolean
  • Integer
  • Float
  • String
  • DateTime
  • Array
  • Dictionary

С расширяемостью же тут всё так же плохо, как и в JSON.


Модель Tree


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


  • Struct Node
  • Data Node

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


Расширяемость модели


Итого, по расширяемости всё очень плохо. Популярные форматы либо расширяемые, но неимоверно переусложнённые, либо простые, но совершенно не расширяемые.


XML JSON YAML TOML Tree
Расширяемость + - + - +
Число паттернов 90 30 210 90 10

Обратите внимание на YAML. Его грамматика насчитывает две сотни паттернов. Он настолько сложен, что вы скорее всего не найдёте ни одной полной и правильной реализации его парсера. Да что уж там, даже два одинаково работающих парсера JSON нужно ещё поискать, а ведь там всего казалось бы 30 паттернов.


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


Удобочитаемость


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


Скорость вашей работы и предсказуемость её результатов напрямую зависит от способа сериализации формата. Однако у некоторых форматов с этим серьёзные проблемы.


XML JSON YAML TOML Tree
Удобочитаемость - - + + +

Удобочитаемость XML


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>

Удобочитаемость JSON


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


{ "greetings": "Привет, Алиса!\nКак дела?\nНе могла бы ты принести мне кофе?\n" }

Строгость


Как правило с пониманием написанного нет никаких проблем. Но YAML тут отличился.


XML JSON YAML TOML Tree
Однозначный синтаксис + + - + +

Нестрогость YAML


a: true # boolean
b: tru  # string
c: (-:  # error
d: :-)  # string

Вот таких приколов в YAML довольно много.


Экранирование


Близкая к читаемости тема — это экранирование. Наличие оного в той или иной мере неизбежно приводит к снижению читаемости. При разработке экранирования стоит иметь ввиду следующие моменты.


  • Нужно отличать конструкции формата от собственно данных
  • Желательно не терять в наглядности данных
  • Желательно не переусложнять редактирование

Экранирование в XML


XML — чудесный пример, как делать экранирование не надо.


foo > 0 && foo < 10

Из простого и наглядного текста получается какой-то криптотекст, который приходится мысленно интерпретировать, чтобы понять что тут написано.


`foo &gt; 0 &amp;&amp; foo &lt; 10`

Экранирование в JSON


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


/"[\s\S]*"/

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


"\"[\\s\\S]*\""

Экранирование в YAML


В YAML проблему экранирования в целом решили, но какой ценой.


  • 5 типов строк
  • 4 модификатора обработки пробелов

И всё это вам нужно знать, чтобы правильно прочитать любой YAML файл.


Экранирование в Tree


Нет

Самое удобочитаемое экранирование — это отсутствие экранирования. Поэтому у нас его не будет. Вы возможно подумали, что я сошёл с ума, но чуть позже я покажу, как этого добиться.


Минификация


Многие форматы поддерживают различные способы форматирования одних и тех же данных. Но это всегда компромисс между размером и удобочитаемостью.


  • Читаемое форматирование много весит
  • Компактное форматирование плохо читается

Минификация XML


<users>
    <user>
        <name>Alice</name>
        <age>20</age>
    </user>
</users>

Если минифицировать XML, то можно сэкономить несколько десятков процентов в размере, но результат получается ещё сложнее читать.


<!-- 13% less -->
<users><user><name>Alice</name><age>20</age></user></users>

Минификация JSON


{
    "users": [
        {
            "name": "Alice",
            "age": 20
        }
    ]
}

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


// 30% less
{"users":[{"name":"Alice","age":20}]}

Минификация Tree


Нет

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


Статистика по минификации


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 есть целая вязанка протоколов стриминга сообщений. Основная проблема тут в том, что далеко не любой поддерживающий формат инструмент сможет переварить ваши данные без дополнительных телодвижений.


Форматы же поддерживающие поточную обработку, можно легко дополнять дописыванием данных в конец. Можно склеивать несколько потоков данных в один и, наоборот, нарезать на части. Можно обрабатывать по частям, не дожидаясь завершения передачи. И всё это без потери корректности работы с форматом.


Формат Tree


Что ж, резюмируя ранее сказанное, давайте сформулируем все требования для нашего нового формата.


  • Простота синтаксиса
  • Никакого экранирования
  • Никаких вольностей
  • Никакой минификации
  • Минимальный размер
  • Гарантированная читаемость
  • Поточная обработка
  • Точные координаты узлов

Просто tree-узел


Итак, нам нужно создать узел с именем "house". Какой минимальный код для этого нужен? 


house

Просто пишем это имя и всё.


Список tree-узлов


А если нам нужен не один узел, а целый список?


house
roof
wall
door
window
floor

Просто пишем их на отдельных строках.


Вложение tree-узлов


Но что если мы хотим добавить иерархичности и поместить список узлов внутрь первого?


house
    roof
    wall
    door
    window
    floor

Просто пишем вложенные узлы с табом в качестве отступа. Знакомые с языком Python тут могут заметить похожий подход — использование хорошего стиля форматирования кода в качестве основы синтаксиса, а не опциональной возможности.


Глубокая tree-иерархия


Продолжая добавлять отступы мы можем создавать иерархии любой вложенности.


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


Язык 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 vs EBNF


Сравнивая 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 vs XML


Язык 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 &amp; Gamble</div>
    </body>

</html>

Было бы классно иметь такую интеграцию в IDE, чтобы открывая любой XML можно было видеть и редактировать его xml.tree представление, но сохранялось бы всё обратно в XML. Это позволило бы больше не ломать глаза об амперсанды и позволило бы работать с XML так же легко и просто, как и, например, с markdown.


Язык json.tree vs JSON


А 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 спецсимвола — звёздочка для обозначения словарей и косая черта для обозначения массивов.


Расширения json.tree


Прелесть языков, основанных на таких форматах как 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 vs TypeScript


Язык 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 для взаимодействия с форматом из разных языков программирования.


Формат Языки 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 AST


Возьмём простой JSON файл и засунем его в ASTExplorer.


{
  "user": {}
}

{
    "type" : "Object",
    "children" : [
        {
            "type" : "Property",
            "key" : {
                "type": "Identifier",
                "value": "user"
            }
            "value": {
                "type": "Object",
                "children": []
            }
        }
    ]
}

Как видно, AST получился большим и сложным. JSON вообще очень плохо подходит для описания AST. Без специальных утилит с ним работать не очень просто.


AST Tree


Теперь давайте возьмём несколько более сложный tree файл.


user
    name \Jin
    age 35
    hobby
        \kendo 
        \dance 
        \role play

И посмотрим на его AST.


user
    name \Jin
    age 35
    hobby
        \kendo 
        \dance 
        \role play

Так, что-то не так. Это же тот же самый код. А, нет, всё правильно, tree — сам себе AST.


Свойства узла Tree


В реализация на 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
}

Производные Tree узлы


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


interface $mol_tree2 {
    struct : ( type , kids )=> $mol_tree2
    data : ( value , kids )=> $mol_tree2
    list : ( kids )=> $mol_tree2
    clone : ( kids )=> $mol_tree2
}

Сообщения об ошибках в Tree


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


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 )
}

Обработка Tree


Или другой пример — мы решили, что "auth" неудачное название и нужно заменить его на "credentials". Поэтому мы пишем не сложный скрипт для автоматического рефакторинга:


//  server credentials
//      login \root
//      password \qwerty
const new_config = config.list(
    input.hack({

        'auth' : ( tree , context )=> [
            tree.struct( 'credentials' , tree.hack( context ) ),
        ] ,

        '' : ( tree , context )=> [
            tree.clone( tree.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

sql.tree — запросы к СУБД


Помните неуклюжие запросы к 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

domain.tree — описание домена


Раз уж мы заговорили о базах данных. Примерно так я описываю модель предметной области.


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, схема СУБД и админка для управления всем этим делом.


Логи


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



access.log.tree — структурированные логи


А что если логи сразу выводить в двумерном виде, одновременно легко читаемом как машинами, так и человеком?


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

tree-tools — CLI утилиты обработки деревьев


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


> 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 как протокол общения


Можно пойти дальше и не просто писать логи в формате 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

WAT


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 — ассемблер без мишуры


Я сейчас работаю над компилятором в байт коды более наглядного 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.tree — LISP без скобочек


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


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 сохраняет координаты исходников, проследить источник ошибки не составляет труда. В репозитории можно глянуть куцый прототип.


$mol_jack


Упраздняя LLVM


Можно пойти ещё дальше и генерировать не 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.


Единый AST чтобы править всеми


Ну и, наконец, мы подошли ко главной мысли этого доклада. 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 максимально быстро, за счёт минимальных накладных расходов на парсинг и сериализацию.


Куда пойти, куда податься


Надеюсь мне удалось заразить вас идеями о светлом будущем. Но чтобы его приблизить нам вместе надо над этим поработать. Один я, боюсь, всё это не вытяну. Так что пишите, зовите и не пропадайте.