Текстовое представление объектов

Почему XML и JSON – плохо, и как сделать хорошо.

Краткое резюме:

• XML, JSON, YAML, SDL – плохо пригодны для описания произвольных иерархий типизированных объектов.
• Но теперь у нас есть альтернативный формат CatML:
• простой,
• интуитивно понятный,
• не допускающий неоднозначности,
• удобный для парсинга,
• кодирующий и строго типизированные данные,
• кодирующий перекрестные ссылки,
• кодирующий глобально именованные объекты и ссылки на них.
• Можно прямо сейчас скачать и использовать его енкодер и декодер для Java, который поддерживает:
• сериализацию объектов
• и DOM-like способ доступа.
• Java-библиотека занимает около 1 тыс. строк и может легко портироваться на любой язык.

Скачать Библиотеку энкодера и декодера CatML

Цели

Время от времени нам приходится представлять иерархии объектов в виде текстов, например:

• для отладки, чтобы выводить в лог внутренности программы,
• для передачи данных по сети, если религия запрещает бинарные форматы,
• для сохранения документов в файлы (по крайней мере, пока нет более правильного решения)

Аналоги

Какие форматы может предложить нам индус-три-я?

• XML – недавний фаворит. Сегодня форсится, пожалуй, только Misrosoft-ом и их приспешниками.
• JSON – набирающий популярность формат, уши которого растут из JavaScript. От XML отличается более вменяемым синтаксисом.
• YAML – самый удобочитаемый из перечисленных форматов. Тем не менее людей понимающих и использующих его очень мало.
• SDL – XML с фигурными скобками.

Критика

Перечисленные форматы имеют несколько проблем, которые делают их плохо пригодными для представления иерархий объектов. Кроме очевидного фатального недостатка
Рассмотрим их на паре простых примеров:

Допустим, у нас есть такие структуры данных (псевдокод):

class Point {
   int x, y;
}
class Polygon {
   String name;
   Point[] points;
}

...и такие объекты – полигон с тремя точками:

Polygon
name “a test one”
points:
   Point
   x 42
   y 12

   Point
   x 0
   y 100

   Point
   x 100
   y 100

Как они могут быть представлены в XML

<polygon name="a test one">
  <points>
     <point x="42" y="12"/>
     <point x="0" y="100"/>
     <point x="100" y="100"/>
  </points>
</polygon>

Они же в JSON

{  “type”: “Polygon”,
   “name”: “A test one”,
   “points”:[
       { “type”: “Point”, “x”: 42,  “y”: 12 },
       { “type”: “Point”, “x”: 0,   “y”: 100 },
       { “type”: “Point”, “x”: 100, “y”: 100 },
   ]
}

И они же в YAML

!Polygon
name: a test one
points:
  - !Point
    x: 42
    y: 100
  - !Point
    x: 42
    y: 100
  - !Point
    x: 42
    y: 100

Сразу видны косяки XML

• Неоднозначность кодирования: поля объектов могут храниться и в виде вложенных нод - «points» или атрибутов «name, x, y» (при этом одни должны быть примитивных типов).
• Еще одна неоднозначность — нода может кодировать и объект “Point” и поле “points”.
• Из примитивных типов данных есть только текст: x=“42”.
• Обилие синтаксического мусора.

Недостатки JSON:

• Нет синтаксиса для задания типа объекта. Тип — это просто одно из произвольно назначенных на эту роль полей,
• Обилие синтаксического мусора.

Недостатки YAML

• Как и в XML, один и тот элемент может быть закодирован множеством разных способов, что усложняет парсеры и создает неоднозначности (чтение текстового представления во внутренние объекты и последующая запись создадут два разных текста).
• Как и в JSON, YAML кодирует вложенные друг в друга мапы и массивы, а не объекты, поэтому тип приходится задавать как один из атрибутов. Существуют расширения, позволяющие указывать тип в виде !<Имя типа>. Но эти расширения мало где поддерживаются.
• Текстовые значения не отделяются от объектов, поэтому работают сложные не очевидные правила типизации и множество разных способов искейпинга текста.

Перекрестные ссылки

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

//
// Форма имеет массив кнопок и ссылку на текущую сфокусированную кнопку.
//
class Form{
    Button[] buttons;
    Button focused;
}
//
// Кнопка имеет текст надписи и ссылку на форму, к которой она принадлежит.
//
class Button{
    String caption;
    Form form;
}

Допустим у нас есть такой набор объектов:

Form.confirmation
buttons:
    Button.buttonOk
    caption ”OK”
    form=confirmation

    Button
    caption ”Cancel”
    form=confirmation
focused=buttonOk

В этом примере я пометил несколько объектов идентификаторами (buttonOk и confirmation), чтобы обозначить ссылки на них из других объектов. Например, форма ссылается своим полем “focused” на одну из кнопок, а кнопки ссылаются на форму своими полями form.
Чтобы обозначить, что значением является перекрестная ссылка, я использовал нотацию “=имя”

Как с представлением этих объектов справятся наши подопытные форматы?
В XML нет специального представления для перекрестных ссылок. Там принято использовать пару атрибутов id/idref для связывания объектов.

<Form id='confirmation'>
   <form_buttons>
      <Button id='buttonOk'>
          <button_caption value='OK'/>
          <button_form idref='confirmation'/>
      </Button>
      <Button>
          <button_caption value='Cancel'/>
          <button_form idref='confirmation'/>
      </Button>
   </form_buttons>
   <form_focused idref='buttonOk'/>
</Form>

Приложение должно самостоятельно обрабатывать эти атрибуты и создавать ссылки.

JSON вообще не умеют кодировать перекрестные ссылки, поэтому он отпадает.
YAML имеет синтаксис &refname *refname для установления ссылок, но, к сожалению, парсер превращает ссылки в копии объектов. Поэтому в JSON и YAML, можно воспользоваться подходом XML – ввести особые атрибуты, которые в отдельном проходе внутри приложения будут превращаться в ссылки.

Итог сравнения:

Мейнстрим-языки разметки непригодны для представления иерархий объектов.
По следующим причинам:

• Отсутствие представления перекрестных ссылок
• Недостаток типизации примитивных типов (кроме JSON и SDL)
• Отсутствие типизации узлов дерева (Кроме XML и SDL)
• Перегруженный синтаксис, усложняющий инструментарий, делающий трансляцию неоднозначной.

CatML

Как может выглядеть формат, свободный от перечисленных недостатков
Мы сохраняем объекты, у которых должен быть:

• тип,
• опциональный идентификатор,
• набор полей.

Выберем самый простой синтаксис:

ИмяТипа.необязательный_идентификатор
имя_поля1 значение
имя_поля2 значение
...
имя_поляN значение

Например

point
x 10
y 42

Тип поля однозначно выводится из инициализирующего зачения:

Целое число	знаковое число в десятичной записи	42
Строка	символы в кавычках с java-искейпингом	”aaa\n\u0430”
Вложенный объект	Описание объекта, при этом имя типа и идентификатор находятся на той же строке, а список полей — на следующих строках с отступом.	Rectangle origin Point x 10 y 20 size Point x 100 y 200
Ссылка на существующий объект	«=» и имя объекта. Null-ссылка обозначается именем "_".	focused= buttonOk
Массив всего перечисленного.	":" и необязательный идентификатор затем с новой строки с отступом следуют описания элементов массива, если элементами являются объекты, между ними добавляется одна пустая строка.	names: "qwer" "asdf" points: Point x 1 y 2 Point x 100 y 200 items: =buttonOk =buttonCancel

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

По правде говоря, все примеры в этом тексте были даны как раз в этой нотации.

Данный формат:

• Прост
• Однозначен
• Интуитивен
• Строго типизирован
• Позволяет описывать произвольные иерархии объектов, а не только деревья.
• Не имеет зарезервированных слов, использует минимум спецсимволов "=:."
• Имеет префиксную структуру, его парсер будет однопроходным без возвратов.

Внутреннее представление

Если используемый язык программирования имеет хоть какую-то типизацию, появляется вопрос, в каком режиме показывать программе результаты парсинга:
Можно создать реальные экземпляры классов приложения, например, если в тексте встретились типы Form, Button, Point, декодер формата создаст экземпляры этих классов и заполнит из поля значениями, присутствующими в файле. Это называется сериализацией и десериализацией.
А можно загрузить разбираемый файл в некие универсальные структуры данных — комбинации словарей и массивов, и позволить приложению обходить и изменять эти структуры данных, получать и дополнять информацию об их типах. Это - загрузка в универсальную модель документа (DOM).

Оба подхода имеют право на жизнь.
Сериализация позволяет с минимальными усилиями сохранять и восстанавливать объекты программы, передавать их по сети и записывать в детализированные логи, но требует чтобы файл содержал только конкретные поддерживаемые приложением типы данных, с жестко заданным набором и типами полей.
Универсальная модель документа (DOM) позволяет загружать и обрабатывать файлы произвольной структуры, но используемые объекты не будут родными для приложения.

Могут существовать и другие решения. Например, сериализация с ограничением состава допустимых типов данных и допустимых полей (из соображения безопасности). Или комбинирование сериализации и универсальной DOM, при котором среди универсальных узлов будут встречаться реальные объекты приложения.

Библиотека использует простой универсальный интерфейс доступа к данным (interface Dom).
В библиотеке присутствуют две реализации этого интерфейса

• VarioDom – универсальная модель документа,
• JavaDom – десериализация с помощью рефлексии.

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

Пример использования

Используем библиотеку для сериализации/десериализации.

// Допустим, у нас есть такие типы данных:
class Point {
    int x, y;
}
class Polygon {
    String name;
    WeakReference<Polygon> peer;
    List<Point> points = new ArrayList<Point>();
}

// прочитаем из файла объекты
JavaDom dom = new JavaDom();
Polygon p = (Polygon)CatReader.parseFile(dom, new StringReader(
    "Polygon\n"+
    "name \"Test text\"\n"+
    "points:\n"+
    "   Point\n"+
    "   x 1\n"+
    "   y 42\n"));

// изменим
p.points.add(new Point());
p.peer = new WeakReference<Polygon>(p);

// запишем обратно
CatWriter.encode(dom, p, new OutputStreamWriter(System.out));

Результат работы программы

Polygon.L0
name "Test text"
peer=L0
points:
    Point
    x 1
    y 42

    Point
    x 0
    y 0

Используем библиотеку для работы с универсальным DOM.

// Этот объект обеспечивает доступ к метаинформации и данным
VarioDom dom = new VarioDom();

// Парсим текст и формируем универсальные DOM структуры
Object root = CatReader.parseFile(dom, new StringReader(
    "Form\n"+
    "title\"Test text\"\n"+
    "x 42\n"+
    "y 10\n"+
    "widths:\n"+
    "  10\n"+
    "  20\n"));

// Получаем тип корневого элемента
StructInfo rootType = dom.getType(root);
System.out.println("object of type " + rootType.getName());

// Получаем список имен полей и их значения
for (int i = 0; i < rootType.getFieldsCount(); i++) {
    FieldInfo fieldType = rootType.get(i);
    System.out.print("field " + fieldType.getName() + " ->");
    for (int j = 0; j < fieldType.getCount(root); j++)
        System.out.print(" " + fieldType.get(root, j));
    System.out.println();
}

// ...Изменяем поля
rootType.get("title").set(root, 0, "Another title");

// ...Создаем новые типы данных
StructInfo pointType = dom.getOrCreateStruct("Point");
FieldInfo pointX = pointType.getOrCreate("x");
FieldInfo pointY = pointType.getOrCreate("y");

// ...Создаем экземпляры этих типов
Object p = pointType.create();
pointX.set(p, 10);
pointY.set(p, 20);

// К существующим типам можно добавлять новые поля
FieldInfo newField = rootType.getOrCreate("pos");
newField.set(root, p);

// ... и создавать перекрестные ссылки
FieldInfo xrefField = rootType.getOrCreate("peerLink");
xrefField.set(root, new WeakReference(root));

// Закодируем обратно в текст.
CatWriter.encode(dom, root, new OutputStreamWriter(System.out));

Результат работы программы

object of type Form
field title -> Test text
field x -> 42
field y -> 10
field widths -> 10 20

Form.L0
title "Another title"
x 42
y 10
widths:
   10
   20
pos Point
   x 10
   y 20
peerLink=L0

Глобальные имена

Каждый DOM позволяет давать объектам имена.
При сохранении в текстовый формат эти объекты будут помечены этими именами с приписанной в начале точкой.
При чтении текстового формата все имена с точкой будут занесены в DOM, чтобы приложение могло обращаться к ним по именам.
При описании weak-ссылки имя тоже может начинаться с точки, в этом случае имя ищется в DOM, а не в текущем тексте.

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

Тут: BinaryCatML описан бинарный формат, который:

• компактен
• быстр в кодировании и парсинге
• однозначно конвертируется в текстовый CatML и обратно.

Скачать Библиотеку энкодера и декодера CatML на Java
Весь код в этом блоге выпускается под лицензией CC0.