Pull to refresh

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

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

image 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" }

image

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

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:

image

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

is

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

image

Данное выражение определяет STATEMENT как последовательность из некоторого «выражения», за которым следует символ «точка с запятой».

octet

Совпадает с одним октетом (8 бит) с указанным внутри шестнадцатиричным значением.

image

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

optional

Допускает отсутствие дочернего шаблона.

image

Совпадает либо с двумя байтами: возвращения каретки после которого идёт перевода строки. Либо с одним переводом строки.

any-of

Сопоставится с одним и только одним из дочерних шаблонов.

image

list-of

Позволяет последовательно повторить дочерний шаблон произвольное число раз (но как минимум одно совпадение должно быть).

image

Тут DELIMITER совпадёт с не пустой последовательной группой пробелов.

except

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

image

Тут мы определяем EXPRESSION как произвольное число байт ни один из которых не является «точкой с запятой».

image

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

with-delimiter

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

image

Здесь SCRIPT определён как набор выражений, разделённых заданным символом.

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

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

image

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

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

image

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

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

image

Подробнее о языке xml.tree
Структурные узлы соответствующие QName – элементы. Узлы данных – текстовые узлы.

image

     <html>
        <head>
            <title>Рога & Копыта</title>
        </head>
        <body>
            <h1>Привет!</h1>
            <p>Хочешь, я расскажу тебе сказку?</p>
        </body>
    </html>

Атрибуты представляются как узлы с QName именем, помещённые в узлы с именем «@».

image

    <script type="text/javascript" src="index.js" />

Имена атрибутов повторяться не должны. Значением атрибута является текст, но также внутри может быть и дерево, которое при создании XML должно быть сериализовано в текст.

Вложенные основанные на формате Tree языки помещаются в узел с именем этого языка, который помещается в узел c именем «%». От процессора требуется поддержка используемых языков, иначе он не сможет правильно собрать XML. Вложенные языки сериализуются в строку по своим правилам и вставляются в XML в качестве текстового узла.

image

    <link
        rel="canonical"
        href="/?article=rock%26roll&author=Nin+Jin"
    />

Комментарии помещаются в узел с именем "--". Заметьте, что в комментарий помещается всё поддерево, которое сериализуется по всем правилам xml.tree.

image

    <!--<a href="/">top</a>-->

Инструкции процессору помещаются в узлы с именем "?" и могут содержать как просто какие-то значения, так и пары ключ-значение.

image

    <?xml version="1.0" stanalone="yes" ololo?>

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

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

image

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

Эта структура данных используется языковыми трансляторами в качестве внутреннего представления обрабатываемых ими языков. Программируя на 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 формате:

image

Редактирование других форматов, через 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


Тут в качестве разделителя ключа и значения используется узел с именем ":", а сырые данные предваряются "\".
Tags:форматы данныхстандартыNIHJSONXMLYAMLINITree
Hubs: Programming D
Rating +61
Views 154.4k Add to bookmarks 421
Comments
Comments 629

Popular right now

Администратор баз данных SQL
from 100,000 ₽Сима-лендЕкатеринбург
Системный аналитик
to 250,000 ₽Sportmaster LabСанкт-ПетербургRemote job
системный аналитик ( удаленно)
from 150,000 ₽CifraМоскваRemote job
Ведущий администратор баз данных
from 80,000 ₽ТатнефтьАльметьевск