ЦеНеБлог

Дерево замість XML

Сьогодні XML — один із найрозповсюдженіх форматів даних, в який можна втиснути будь-яку структуру. Та чи бездоганний він?

По-перше, закриваючі теги. XML вимагає їх завжди — або у вигляді окремого тега наприкінці тіла, або у вигляді знаку «/» перед закінченням одинарного тега. XML — не HTML, де закриваючі теги часто необов'язкові (хоча й бажані), і місце закінчення тіла для кожного з тегів визначається по-різному. Повторення імені тега XML при його закритті — надлишкове, можна було б обійтися чимось назразок </>, але XML ставить перед собою задачу сумісності з HTML — звідси й цей надлишковий синтаксис. Втім, надлишковість XML — дрібниця в порівнянні з тим, що увесь блок даних має бути охоплений зовнішнім тегом, який сам по собі не несе майже ніякої важливої інформації. До чого це веде на практиці? В XML-файл не можна дописувати дані вкінці — тільки переписувати увесь файл. XML непридатний для ведення логів (хоча окремий запис логу може мати XML-подібну структуру).

По-друге, необхідність використовувати позначення замість деяких символів у тексті. А якщо текст (дані) сам містить фрагменти XML чи HTML (котрі теж можуть містити цитування XML)? Тоді символи можуть піддаватись багаторазовій обробці (з кожним вкладенням усе більше):

<br/>
&lt;br/&gt;
&amp;lt;br/&amp;gt;
&amp;amp;lt;br/&amp;amp;gt;
(далі зростання відбувається в арифметичній прогресії).

Взагалі, будь-які ескейп-символи при багаторазовому цитуванні виглядатимуть страшно. Pascal:

п'ять
'п''ять'
'''п''''ять'''
'''''''п''''''''ять'''''''

Хоча й два апострофи виглядають лаконічніше, ніж &quot; &lt; чи &amp;, подальше зростання їх кількості відбувається в геометричній прогресії — після певної кількості самоцитувань паскалеподібна символьна константа виглядатиме страшніше, ніж XML.
Не краще виглядає й стиль C / C++ / Java / C# / PHP (можна продовжити — розробники мов програмування люблять повторювати синтаксис С з усіма його плюсами й мінусами):

"text"
"\"text\""
"\"\\\"text\\\"\""

Загалом, те ж саме, що й у паскалі, але тепер нам доводиться чергувати два типи спецсимволів. Свого часу мені довелось спостерігати глюк, пов'язаний з тим, що PHP й MySQL не зовсім однаково здійснюють слеш-шифрування й його розшифрування — ще одна дірка для хакерів.

В ідеалі, розмір цитованого рядка має при кожному вкладенні зростати в арифметичній прогресії (тобто, кількість додаткових знаків має бути фіксованою). Хороший приклад для наслідування — формат, прийнятий в електронному листуванні:

Я пишу тобі листа
>Я пишу тобі листа
>>Я пишу тобі листа
>>>Я пишу тобі листа

Як бачимо, текст при кожному цитуванні збільшується лише на один символ на рядок. При цьому в самому рядку можуть бути які-завгодно символи — при цитуванні вони не дублюються. Чи не ідеально?

Взагалі, приблизно те ж саме можна було б зробити й за допомогою пробільних відступів, але суттєвим недоліком пробілу є його нечитабильність. Око людини — не лінійка. Ми не можемо на око визначити кількість пробілів, якщо їх достатньо багато. Тим більше, пробіли можуть змішуватися з символами табуляції, довжина яких може відрізнятись у будь-яких двох текстових редакторах.

Чого нам не вистачає? Скажімо, можливості розбивати довгі рядки на частини. Зробімо це:

> Довгий довгий довгий довгий
* довгий довгий довгий
* довгий довгий довгий
* довгий довгий довгий
* довгий довгий довгий
* довгий довгий довгий
* довгий довгий рядок
> А це вже наступний рядок.

Продовження рядка будемо маркувати не знаком „>“, а зірочкою. Для чого це нам? Скажімо, для збереження тексту, в якому кожен рядок відповідає абзацу.

Крім того, ми хочемо розширити можливості синтаксису поштових цитат, доповнивши його іменованими структурними елементами. Наприклад:

Root
+-Node1
+-Node2
! +-Node2_1
! ! >text text text text
! ! >text text text
! +-Node2_2
! . +-Element
! . +-Element
+-Node3

Таким чином, ми підійшли до питання, винесеного в заголовок: псевдографічне дерево для опису структурованих даних. Це не просто псевдографіка, а мова з чітко визначеними синтаксичними елементами:
ідентифікатор з літер і цифр — початок блоку даних (структури чи тексту),
„+-“ — вхід у підпорядкований вузол,
„! “ та „. “ — префікс рядка опису вмісту підпорядкованого елементу. Обидва знаки супроводжуються наступним пробілом. Їх функції ідентичні, обидва варіанти взаємозамінні, але крапку бажано писати лише перед елементами останньої структури з описуваного вузла, щоб візуально підкреслити закінчення «гілки».

Ми отримали мову зі зручною структурою, легкою для читання. Це основа синтаксису дерева. Далі підуть додаткові елементи.

Є дещо, в чому ця мова програє перед XML: можливість вставляти блоки тексту без попередньої обробки (з деякими обмеженнями). Виправляємось:

Префіксний варіант:

Node
+-Node
! +-Node
! ! +-Data
! ! ! > text....
! ! ! > text....
! ! ! > text....
! ! ! > text....
! ! ! > text....
+-Node
+-Node

еквівалентний наступному:

Node
+-Node
! +-Node
! ! +-Data
=Label
 text.... 
 text.... 
 text.... 
 text.... 
 text.... 
=Label
+-Node
+-Node

Label — мітка в вигляді довільної послідовності символів. Рядок з ідентичною міткою відмічає кінець тексту.

Приблизно те ж саме можна зробити і для вкладених структур:

Node
+-Node
! +-Node
! ! +-Substructure
! ! ! +-Element1
! ! ! +-Element2
! ! ! ! +-Element3
! ! ! +-Element4
! ! ! . >text....
! ! ! . >text....

можна замінити на:

Node
+-Node
! +-Node
! ! +-Substructure
-Label
Element1 
Element2 
+-Element3 
Element4 
>text.... 
>text... 
-Label

Менш наглядно, але в деяких випадках дуже зручно.

Ще декілька дрібниць. Елемент, що містить у собі лише один рядок даних, можна описати скорочено:

Element:text text text

або

Element="text text text"

Якщо ж короткий текст треба розбити на кілька рядків, це можна зробити наступним чином:

Element="Row 1"/"row 2"/"row 3"

Структури, що складаються з однорядкових елементів, також можна записати однорядково:

Node(A="aaa" B="bbb" C(D="ddd" E="eee") F="fff")

можна розписати як:

Node
+-A
! >aaa
+-B
! >bbb
+-C
! +-D="ddd"
! +-E:eee
+-F="fff"
  

Крім того, в одному елементі структури можна комбінувати всі перераховані вище засоби синтаксису:

root
+-node="row 1"/"row 2"
! >row 3
! +-attr="value" (A="aaa")
! +-attr (B="bbb" C="ccc")
! ! >text
! ! >text
! ! "text"/"text"
! >row 4
=****=
row 5
row 6
=****=
! >row 7
+-node:text
. >text
. >text  

Таким чином, кожен елемент може містити одночасно i текстову інформацію, і структуровані дані. При цьому має значення лише збереження послідовності рядків, тоді як структурні елементи можуть розміщуватись у довільному порядку.

Також можна додати коментарі в стилі С++:

Root//Основа дерева
+-Node//Вузол з текстом
! > text
! >text
! //Кінець вузла
//Коментар між рядків
+-Node//Структура
. +-Element
. +-Element

Коментарі можуть з'являтись у будь-якому рядку, крім текстових рядків без лапóк. Їх можна розміщувати як окремий рядок, після префіксу вкладеності структури (в обох випадках, увесь рядок з коментарем ігнорується) чи наприкінці рядка (тоді ігнорується лише коментар).

XML усе ще має ряд об'єктивних переваг перед деревом:

• Існуючі програми та бібліотеки, що працюють з XML — головна перевага. Неважко написати текстовий аналізатор для дерева, але ми все одно не зможемо його ніде використати, окрім власних програм, тоді як XML вже є широко використовуваним стандартом.
• Компактність при високому рівні вкладеності структури — замість префіксів для кожного рядка, XML вистачає відкриваючого та закриваючого тегів на цілий блок. Втім, якщо теги супроводжуються пробільними відступами для підвищення читабельності, компактність перестає бути перевагою.
• Відсутність проблем сумісності між різними операційними системами: символьні коди закінчення рядка реалізовані в них по-різному, тому багаторядковий текст з одніє ОС може сприйматись як суцільний рядок в іншій. XML здебільшого ігнорує розбивку тексту на рядки. При написанні аналізатора для дерева слід урахувати цю особливість.
• Засоби для позначення символів, відсутніх у поточному наборі (напр., &#1234; — Ӓ ). Це актуально для восьмирозрядних таблиць символів, але не має великого значення для utf-8.
• Для роботи з XML вам нема потреби самостійно писати увесь код аналізатора — простіше використати готові бібліотеки, тоді як мова-дерево ще не має навіть назви, не кажучи вже про якісь програмні заготовки. Ви можете або самостійно втілити цю ідею в життя, або почекати, коли у мене дійдуть до цього руки, і я опублікую свої розробки на сторінках ЦеНеБлогу.
• XML простіше редагувати, ніж дерево (використання безпрефіксних блоків частково усуває цю проблему, але найкращим варіантом буде створення спеціалізованого текстового редактора для деревовидних структур).