Tree — убийца JSON, XML, YAML и иже с ними

Здравствуйте, меня зовут Дмитрий Карловский и я… много думал. Думал я о том, что не так с XML и почему его в последнее время променяли, на бестолковый JSON. Результатом этих измышлений стал новый стандарт формат данных, который вобрал в себя гибкость XML, простоту JSON и наглядность YAML.

Tree — двумерный бинарно-безопасный формат представления структурированных данных. Легко читаемый как человеком так и компьютером. Простой, компактный, быстрый, выразительный и расширяемый. Сравнивая его с другими популярными форматами, можно составить следующую сравнительную таблицу:

Больше — лучше	JSON	XML	YAML	INI	Tree
Человекопонятность	3	1	4	5	5
Удобство редактирования	3	1	4	5	5
Произвольная иерархия	3	3	3	1	5
Простота реализации	3	2	1	5	5
Скорость парсинга/сериализации	3	1	1	5	5
Размер в сериализованном виде	3	1	4	5	5
Поддержка поточной обработки	0	0	5	5	5
Бинарная безопасность	3	0	0	0	5
Распространённость	5	5	3	3	0
Поддержка редакторами	5	5	3	5	1
Поддержка языками программирования	5	5	3	5	1

Сравнение форматов

Человекопонятность

JSON и XML позволяют произвольно форматировать вывод пробелами и переносами строк. Однако, часто по различным причинам (основные — меньший объём, проще реализация) их форматируют в одну строку и тогда они становятся крайне не читаемыми.

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

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

Кроме того, JSON не поддерживает многострочные тексты — они всегда представляются в виде одной строки, со специальной escape-последовательностью вместо переводов строк.

{ "description" : "Hello, Alice!\nHow do you do?" }

С другой стороны, XML позволяет внедрять свои тэги внутрь текста, что наглядно для простой разметки типа «выделение жирным», но сложная разметка типа «гиперссылка» даёт резко противоположный эффект.

<greeting>
    Hello, <b>Alice</b>!<br/>
    How do you do?
</greeting>

<greeting>
    Hello, <a href="http://example.org/user/alice?ref=xe3o7rubvo283xb">Alice</a>!<br/>
    How do you do?
</greeting>

Если текст содержит «специальные символы», то их приходится экранировать escape-последовательностями. В XML эти последовательности особенно громоздки и ненаглядны. А вот в Tree, наоборот, экранирование не требуется вовсе.

<title>"Rock&roll" = life</title>

{ "title" : "\"Rock&roll\" = life" }

Удобство редактирования

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

Произвольная иерархия

INI имеет жёстко ограниченную глубину иерархии.

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

JSON и YAML для создания иерархий предлагают «списки» и «мапки». Не все структуры данных хорошо представимы с их помощью. Например, различные AST, где имена узлов могут повторяться и порядок следования которых важен.

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

Простота реализации

JSON

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

XML

Довольно сложная грамматика (90 паттернов), которая могла бы быть куда проще, если бы не требование совместимости с sgml.

YAML

Крайне сложная грамматика (210 паттернов). Нужно быть очень терпеливым человеком, чтобы реализовать все нюансы, и потратить много человекочасов, чтобы избавиться ото всех багов.

INI

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

Tree

Очень простая грамматика (10 паттернов), что, однако, не мешает описывать с его помощью произвольные иерархические структуры.

Скорость парсинга/сериализации

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

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

Tree помимо простой грамматики имеет ещё одно существенное преимущество — отсутствие необходимости в экранировании и разэкранировании спецсимволов.

Размер в сериализованном виде

Примеры файлов на разных языках: github.com/nin-jin/tree.d/tree/master/formats

Как видно, существенно больше всех места занимает XML, даже если его минифицировать. JSON в читабельном виде и YAML где-то по середине. А самые компактные — INI, Tree и минифицированный в одну строку JSON.

Поддержка поточной обработки

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

В случае XML и JSON такой возможности нет — документ с обрезанным концом или дополнительными данными в конце, является невалидным.

Бинарная безопасность

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

Распространённость

XML довольно продолжительное время был в тренде, так что нашёл применение во множестве мест. Сейчас уверенными темпами популярность набирает JSON, благодаря своей простоте, но ценой некоторой потери гибкости. INI за счёт своей ограниченности применялся лишь для различных конфигов, но сейчас замещается более гибкими форматами. YAML остаётся довольно нишевым форматом ввиду своей переусложнённости, хотя и снискал некоторую популярность у любителей «писать меньше, делать больше, а потом хоть трава не расти». Tree пока ещё вначале пути и надеюсь не в конце.

Поддержка редакторами

XML и JSON благодаря своей популярности поддерживаются везде. Над поддержкой YAML многие разработчики редакторов просто не видят целесообразности заморачиваться. INI настолько прост, что для него никакой особой поддержки и не нужно. С Tree в принципе та же картина, но есть один плагин к IDEA о котором будет рассказано далее.

Поддержка языками программирования

Тут в целом та же ситуация, что и с поддержкой редакторами. Разве что для Tree есть две реализации — на языках D и TypeScript/JavaScript.

Подробнее о Tree

Уровни представления

• Уровень формата. Определяет базовую модель данных и представление её в сериализованном виде.
• Уровень языка. Определяет семантику узлов и представление их в отличных от Tree форматах.
• Уровень приложения. Определяет API для взаимодействия с моделью данных Tree.

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

Модель Tree крайне проста — есть только один тип узлов, и каждый узел имеет: имя, значение, список дочерних узлов. Имя и значение являются взаимоисключающими, так что условно все узлы можно разделить на 3 типа:
• Имена — узлы с непустым именем и пустым значением. Используются для именования поддеревьев. В имени не может быть пробельных символов, символа перевода строки и символа равенства.
• Значения — узлы с пустым именем. Используются для хранения значений. Единственное ограничение на значения — они не могут содержать символ перевода строки.
• Коллекции — узлы с пустым именем и значением, но не пустым списком дочерних узлов. Используются для работы со списком узлов как с одним узлом. В результате парсинга возвращается именно коллекция, содержащая список корневых узлов.

В Tree нет комментариев или инструкций процессору, знакомых нам из XML. Нет списков или мапок из JSON и YAML. Нет специального синтаксиса для секций, как в INI. Однако они и не только они могут быть введены в языках, основанных на формате Tree.

Строковое представление

Tree-файл состоит из набора строк, разделённых символом перевода строки (0x0D). Каждая строка начинается с некоторого количества символов табуляции, показывающих какой из предков является родителем первого узла в строке. И далее идёт список узлов разделённых пробелами. Каждый следующий при парсинге вкладывается в предыдущий. Узлы-имена представляются просто своим именем. Узлы-значения – значением, предварёнными символом равенства.
В одной строке может быть произвольное число узлов-имён, но узел-значение может быть только один, причём самым последним. Значение может содержать абсолютно любые символы за исключением символа перевода строки. Когда нужно поместить произвольные бинарные данные – их предварительно надо разбить по символу перевода строки на несколько узлов-значений. А при приведении дерева к строке именованные узлы будут отброшены, а данные из узлов-значений будут выведены как есть и между ними будут вставлены переводы строк.
Наличие табуляции в строке означает, что первый узел в этой строке должен быть вложен в последний узел последней строки имеющей табуляцию на один меньше.

По сухому описанию довольно сложно ухватить суть, так, что далее будет множество наглядных иллюстраций…

Примеры применения Tree в разных областях

Контекстно свободные грамматики

Хоть формат Tree и не является контекстно свободным, но разбить на лексемы его можно по сравнительно не сложной контекстно свободной грамматике, которую можно выразить тоже в формате Tree:

Лог доступа к веб-серверу

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

Поток сообщений от сервера в чате

Специальный разделитель "---" говорит клиенту о том, что завершилась пересылка очередной порции данных и можно приступать к её обработке.

Вёрстка статической веб-страницы

Специальный DSL на базе Tree позволяет лаконично описывать XML любой сложности. Трансформер из xml.tree в xml понимает специальные узлы «@», «!» и «?» формируя атрибуты, комментарии и инструкции процессору.

Дамп реляционной базы данных

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

Абстрактное Синтаксическое Дерево

Эта структура данных используется языковыми трансляторами в качестве внутреннего представления обрабатываемых ими языков. Программируя на NodeJS велик соблазн использовать в качестве AST — некоторое подмножество JSON.

Например, у нас есть следующий исходник на JS:

function getEl( id ){
	return document.getElementById( id )
}

Интуитивно кажется, что AST должен выглядеть как-то так:

[
	{ "function": {
		"name": "getEl",
		"args": [ "id" ],
		"body": [
			{ "return": [
				{ "get": "document" },
				{ "call": {
					"name": "getElementById",
					"args": [
					 	{ "get": "id" }
					]
				}}
			]}
		]
	}}
]

Однако, это довольно не удобный для работы формат, так как чтобы узнать тип узла нужно проитерироваться по его свойствам и взять имя первого собственного свойства. Поэтому, чаще можно встретить формат типа такого, где первый элемент списка содержит тип узла, остальные — различный набор параметров специфичный для этого типа:

[ [ "function",
    "getEl",
    [ "id" ],
    [ "return",
      [ [ "get",
          "document" ],
        [ "call",
          "getElementById",
          [ "get", "id" ]
        ]
      ]
    ]
  ]
]

А теперь сравните с реализацией в Tree формате:

Редактирование других форматов, через Tree представление

Основная фишка модели данных Tree заключается в том, что она позволяет описывать почти любые другие модели данных. Например, модель данных XML — это сильно усечённая модель данных Tree.

Что это значит? А значит это, что многие форматы могут быть транслированы в некоторое подмножество Tree и обратно без потерь. То есть, вместо того, чтобы редактировать, например, XML как он есть, редактор может налету преобразовать его в xml.tree язык, позволив пользователю редактировать его в более удобной и наглядной форме, а при сохранении, делать обратное преобразование и сохранять именно XML.

Структурированный UNIX-трубопровод

Суть проблематики и вариант решения с использованием JSON можно почерпнуть из статьи "JSON pipes в шелле". Вкратце: в linux все команды выводят результат в неструктурированном ориентированном на человека виде, что затрудняет компоновку их друг с другом. Там предлагается использовать JSON, который привносит структуру, но ухудшает читаемость и производительность. Формат Tree в этом случае может привнести структуру практически не теряя ни в читаемости, ни в производительности.

Язык декларативного программирования

Формат Tree мог бы решить основную проблему языка Lisp — неимоверное число скобочек. Если в Lisp всё описывается как списки, то в языке на основе Tree — всё есть деревья. Точно также программа представляла бы из себя некий AST, который мог бы модифицировать сам себя для создания DSL на все случаи жизни, достигая максимальной выразительности.

Эталонная реализация

На языке D парсинг занимает не более 50 строк, а сериализация — 20. Простейший язык запросов — 15. Итого, чуть более 100 строк занимает минимально необходимый функционал: github.com/nin-jin/tree.d

Парсинг:

    string data = cast(string) read( "path/to/file.tree" ); // read from file
    Tree tree = Tree.parse( data , "http://example.org/source/uri" ); // parse to tree

Глубокие запросы:

    Tree userNames = tree.select( "user name" ); // returns name-nodes
    Tree userNamesValues = tree.select( "user name " ); // returns value-nodes

Работа с узлами:

    string name = userNames[0].name; // get node name
    string stringValue = userNames[0].value; // get value as string with "\n" as delimiter
    uint intValue =  userNames[0].value!uint; // get value converted from string to another type

    Tree[] childs = tree.childs; // get child nodes array
    string uri = tree.uri; // get uri like "http://example.org/source/uri#3:2"

Сериализация:

    string data = tree.toString(); // returns string representation of tree
    tree.pipe( stdout ); // prints tree to output buffer

Поддержка редакторами

В данный момент есть лишь плагин подсветки синтаксиса Tree к IDEA, но он понимает только базовые конструкции формата, описанные выше. Для языков на базе Tree нужно будет сделать отдельные плагины или же один, но расширяемый с помощью схем.

Кроме того, Alex222 буквально за вечер написал плагин к SynWrite

Заключение

Надеюсь мне удалось заразить вас идеей использования замечательного формата Tree. Рассказывайте о нём другим. Пишите библиотеки на используемых вами языках. Внедряйте хотя бы опциональную его поддержку в ваши приложения. Ищите ему новые применения — уверен их ещё много. И тогда у него будет шанс на выживание в современном мире Трендо Ориентированного Программирования.

Обновление от 2016-09-11

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

Например:

! City : table
	ID : field
		type : int 11
		null : false
		unique : true
	Name : field
		type : char 35
		null : true
		unique : false
City
	ID : 1
	Name : \Kabul
City
	ID : 4079
	Name : \Rafah
City
	ID : 23023
	Name : \Moscow

Тут в качестве разделителя ключа и значения используется узел с именем ":", а сырые данные предваряются "\".