13.01.2020 03:22
Mercury13 54 3800 Источник


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


  • будет расширяться, и существенно (отпадают уровни и сохранения большинства игр: после пары патчей бросаем игру и пишем новую);
  • тем не менее программа не рассчитывает на то, чтобы быть стандартом (отпадает LibreOffice). То есть по формату сохранения она должна быть совместима только с собой-старой и собой-новой;
  • все её данные надо держать одномоментно в памяти; СУБД типа SQLite не даёт каких-то преимуществ (отпадают базы переписки в почте или мессенджере);
  • но файл сохранения будет очень велик (отпадают программы фотопроявки вроде Lightroom, где документ — это всего лишь положения сотни-другой ползунков: мелочь по сравнению с 40-мегабайтным RAW);
  • нет нужды в ручной корректировке файлов (отпадает пользовательский интерфейс типа «файл конфигурации», присущий, например, серверу Apache).

Таких программ на самом деле немало. Это AutoCAD, Photoshop, Microsoft Office (будем честными: даже пытаясь протащить его через ISO, «мелкомягкие» рассчитывали, что он будет совместим в первую очередь с самим собой).


И для простоты добавим ещё одно требование, которое отбросит все три этих программы, но довольно реалистичное (ему отвечают Windows 10 и куча программ помельче).


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

Я долго искал программу, которая отвечает всем этим требованиям, и наконец нашёл: Inkscape. Несмотря на то, что её файлы основаны на стандарте SVG, половина всей информации лежит в расширениях SVG — пространствах имён «sodipodi» и «inkscape».


В первой части постараюсь обойтись без программирования, зато объясню парочку важных концепций.


Собственно, у нас есть такие возможные форматы для хранения информации.


Формат первый. XML


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


[+] Много стандартного инструментария.
[+] Оптимальный выбор, если мы храним размеченный текст.
[±] Можно (хотя и тяжело) редактировать файл вручную.
[?] Разбор может занимать много времени — от 20 до 95% всего времени загрузки. Эту неоптимальность даже обозвали «налогом на угловые скобки». По опыту загрузки (не полной) XLSX собственными силами: раззиповка — 0,3 с, разбор XML — 1,1 с, остальное — 0,6 с.
[?] Программировать своими силами очень опасно, возможны незаметные ошибки.
[?] Зачастую избыточен.
[?] Если в программе есть огромные массивы из малюсеньких объектов (звуковые волны, картинки, матрицы чисел), их приходится сохранять не-XML’ными мерами. Посмотрите, например, как хранятся кривые в SVG:


<polygon id="Star-1" stroke="#979797" stroke-width="3" fill="#F8E81C"
            points="99 154 40 185 51 119 4 73 69 64 99 3 128 64 194 73 147 119 158 185 " />

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


Каким образом? Я знаю четыре подхода к чтению XML: на callback’ах (SAX), на потоках (StAX), на сопрограммах и DOM. А также два подхода к записи XML: прямая запись тэг за тэгом и DOM.


Чтение на callback’ах даёт сложный и путаный код, напоминающий конечный автомат. DOM расходует памяти в разы больше, чем структура предметной области. Сопрограммы — сложное дело и есть не везде. Так что наш выбор — чтение на потоках, запись тэг за тэгом. В обоих случаях расходуется пренебрежимо мало памяти, так что автоматически выполняется моё обещание не грузить громадину.


На языках, где мы управляем памятью вручную (Си), у потокового парсера есть ещё одна полезная черта. Управление памятью действует как унитазный бачок — потихоньку заполняется, мгновенно сливается — потому в самых быстрых из них действует собственное управление памятью. К сожалению, не получается добиться столь впечатляющей скорости, как в DOM (прежде чем выйти из функции getThing, надо «подобрать концы»). Так что у меня лично получилось (на Си++) сделать потоковый парсер в 2,5 раза медленнее, чем у рекордсмена PugiXML. Но это уже замечательный результат: научился грузить огромный XLSX втрое быстрее, чем Excel.


Формат второй. XML-лайты


«XML-лайтами» я называю языки наподобие XML, в которых единицы смысла — это строки текстового файла (иногда также агрегаты из нескольких строк). Наиболее известный — YAML.


name: Mark McGwire
accomplishment: >
  Mark set a major league
  home run record in 1998.
stats: |
  65 Home Runs
  0.278 Batting Average

Много лет назад, не накопав хорошего XML-инструментария для Delphi, за полдня я придумал XML-лайт с тупым названием Multilevel. Правда, тогда по неопытности работал только с DOM-разбором.


{ MULTILEVEL
  Format=McJoy
  Noise=10
  { AXES
    { AXIS
      Index=2
      Name=Тормоз
      Type=Analog
      Neutral=65535
      Threshold=25
    }
    { AXIS
      Index=3
      Type=Analog
      Neutral=32895
      Threshold=25
    }
  }
}

[+] Достаточно быстры.
[+] Редактируются вручную.
[±] Думаю, можно подобрать подходящий формат для огромных массивов из малюсеньких объектов.
[±] Легко запрограммировать своими силами.
[?] Даже если формат известный, вроде YAML, велика вероятность, что найдутся только DOM-подобные механизмы.
[?] Малопригодны для размеченного текста (и то придётся специально продумывать подходящий формат).


Формат третий. Двоичные XML-подобные коды


XML — формат текстовый. Но ничего не стоит перевести его в двоичный вид. Вот наобум придуманный XML-подобный двоичный формат (порядок байтов для наглядности взят Motorola):


89 AB CD EF    ; заголовок
00 01          ; блок с кодом 1
00 00 00 03    ; длина блока (=3)
AA BB CC       ; данные
80 02          ; каталог с кодом 2 (бит 80 00 означает «подкаталог», поля длины нет)
    00 03                      ; блок с кодом 3
    00 00 00 08                ; длина блока (=8)
    AA BB CC DD EE FF 00 11    ; данные
00 00          ; конец подкаталога

На XML бы это выглядело так.


<data>
  <block opcode="1">AA BB CC</block>
  <dir opcode="2">
    <block opcode="3">AA BB CC DD EE FF 00 11</block>
  </dir>
</data>

Я не открываю Америку, формат BIFF из Microsoft Office существует лет тридцать. Компания облажалась в двух местах: 1) Формат не иерархический, что сильно мешает дробить блоки; 2) блок ограничен 64 килобайтами, что решается вторым, третьим и т.д. блоком CONTINUE.


Недавно для целей медиаконтейнера Matroska сделали язык EBML — тот же XML, но двоичный. Конкретно с ним не знаком.


[+] Крайне быстры.
[+] Тэги, скорее всего, будут достаточно коротки, чтобы размеченный текст отнял даже меньше места в файле, чем в памяти.
[±] Легко запрограммировать своими силами.
[±] Огромные массивы из малюсеньких объектов можно сохранять как есть, в двоичном виде.
[?] Ручному редактированию не подлежат, для отладки потребуется программа-дампер.


Прочие форматы (и их недостатки)


Эти форматы лучше даже не рассматривать.


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


Любые сериализации через рефлексию (встроенные в Java, Delphi, C#). Годятся только для задач, где большая совместимость не нужна (уровни и сохранения игр, файлы настроек). Если вам удастся задействовать рефлексию и сэкономить строки — вы молодец, но программа не должна полагаться только на неё.


UPD. Чем плоха рефлексия? Костылями при серьёзных изменениях структуры файла.


SQLite продвигает свой формат БД как формат документа. По-моему, из-за сложностей программирования с ним имеет смысл работать именно как с СУБД.


JSON несколько проще в программировании, чем XML, но всё равно сложен. Плюс затруднено потоковое считывание: JSON различает объекты и массивы, и синтаксис JS говорит, что от перестановки атрибутов результат не меняется.


{  // объект
   "address": {   // объект
       "streetAddress": "Московское ш., 101, кв.101",
       "city": "Ленинград",
       "postalCode": 101101
   },
   "phoneNumbers": [  // массив
       "812 123-1234",
       "916 123-4567"
   ],
   "firstName": "Иван",  // хотелось бы их иметь в начале
   "lastName": "Иванов"
}

Хотя JSON подсказывает нам одну важную идею. А именно…


Идея 1. Или последовательность, или коллекция


Нашу жизнь очень сильно упростят два важных требования.


Любой тэг должен быть или последовательностью тэгов/блоков, или коллекцией тэгов/блоков. Объясню, что это такое.


  • Последовательность — это когда каждый сын повторяется не более одного раза и знает своё место. При этом возможны необязательные или взаимоисключающие.
    • В терминах регулярных выражений — что угодно без дублей и операции «повторить». Например, AB [C] (D | [E]F) G.
    • Неизвестные тэги, замеченные в последовательности, пропускаются.
    • Пример: тэг <html> будет последовательностью из <head> и <body>.
  • Коллекция — это повтор тэгов из какого-то ограниченного набора, с предельно простыми правилами взаимодействия друг с другом. Что-то вроде (A|B|C)*.
    • Неизвестные тэги, замеченные в коллекции, пропускаются или вызывают ошибку по желанию программиста.
    • Пример: тэг <body> будет коллекцией из (почти) всех возможных тэгов HTML. Тэг <tr> содержит только <td> и <th>.

Примечание. Я понимаю, что в HTML оба этих тэга, td и th, можно использовать как непарные, браузер разберётся. Но давайте будем считать, что имеем дело с XHTML и эти тэги парные.


А вот совершенно не подходит под нашу модель тэг table. В официальной документации он описан как [caption], [title], [summary], ( col* | colgroup* ), (( [thead], [tfoot], tbody+ ) | ( tr+ )) — не похоже ни на коллекцию, ни на последовательность. Я понимаю разработчиков: HTML-то пишется в первую очередь руками. Но в машиночитаемом формате лучше так не делать.


Делая коллекцию дочкой коллекции, надо чётко осознавать риски. Тэг table в одном из вариантов будет коллекцией тэгов tr. А он, в свою очередь, коллекция из td и th. Если вдруг, случись что, в tr появится какой-нибудь тэг tx, с большой вероятностью оборвётся совместимость.


Как бы мы переписали нашу несчастную таблицу под машинное сохранение?


table :== [caption] [title] [summary] [cols|colgroups] [thead] [tfoot] (tbodies|tbody)
cols :== col+
colgroups :== colgroup+
tbodies :== tbody+
thead, tfoot, tbody :== tr+
tr :== (td|th)+

Но при этом мы чётко понимаем, что внутри коллекции tbody находится коллекция tr. Но таблица — она двухмерная, и крайне мала вероятность, что внутри tr вставят что-то не являющееся клеткой таблицы — так что закрываем на это глаза.


А вот в нашем простом иерархически-двоичном формате так нельзя. Причина в том, что у тэга XML есть атрибуты, куда, если что, можно закинуть немножко информации. А у каталога двоичного формата нет ничего — потому в этот самый tr не впишешь никаких новых данных: ни стиля, ни соответствия электронного документа и бумажного источника… Потому приходится полностью исключать коллекции в коллекциях.


thead, tfoot, tbody :== trs
trs :== tr+
tr :== tds
tds :== (td|th)+

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


<table caption="xxx" />
<table><caption>xxx</caption></table>

Второй лучше — больше места для расширения. Может, вы когда-нибудь станете оформлять части заголовка жирным и курсивом. А может, будут два заголовка (например, в начале таблицы и в продолжении, если её разорвало на две страницы). Кто знает?


Впрочем, <table class="myTable" /> вполне себе катит: ссылка на стиль — свойство, заголовок, висящий где-то на мониторе — сущность.


Идея 2. Extend, upgrade, break. Или расширить, модернизировать, порвать


Какую бы мы ни придумали конструкцию — когда-нибудь мы из неё вырастем. Пусть у нас редактор простейших уровней, например, для Super Mario. Изначально там был один «мир» (скажем, лес). Делаем так, чтобы были два, три и больше миров. Как это будет выглядеть в XML?


БЫЛО:
<tileset />

СТАЛО:
<tilesets>
  <tileset />
  <tileset />
  <tileset />
</tilesets>

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


(название намеренно сделано похожим на Microsoft’овское Embrace/Extend/Extinguish, да и суть та же).


Расширить: программа пишет старый формат, если в игре один мир, и в новый, если много.


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


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


Идея 3. Работая с текстовыми файлами, используйте нейтральную локаль


Разрешите процитировать IT Happens:


«Странно», — подумал я, но девочка из ПФР оставила ман в сто страниц А4. Решив начать по-хорошему, я сел и стал его вдумчиво курить. Где-то на 40-й странице я наткнулся на указание сменить стандартный разделитель целой и дробной частей в винде на запятую, иначе программа не будет работать. Открыл, смотрю — ага, всё верно. Сменил на точку — программа ФОМС заработала, но перестала работать программа ПФР, выдавая всю ту же ошибку сохранения данных. Теперь пожилая женщина-кадровик обучена переключать разделитель, а я проникся небывалой нежностью к отечественным программистам.

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


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


<program name="MyProgram" savedWith="1.1.1.42" fullyCompatibleWith="1.1.1.40" partlyCompatibleWith="1.1.1.25" />

Цифру partlyCompatibleWith поднимаем до текущей, когда делаем extend или break в чём-то важном. Можно её устанавливать умно в зависимости от того, сохраняли мы в старом формате или нет. Цифру fullyCompatibleWith поднимаем, когда добавляем любой тэг.


Если файл загружен программой версии меньше 25, вывести: «Настоятельно рекомендуем обновить программу. Есть вероятность, что важные данные потеряны».


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


Если файл загружен какой-то очень новой программой, чей partlyCompatibleWith больше 42, тоже можно что-то вывести.


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


Также в новых версиях программы можно хранить чёрный список версий, которые часто падают или портят файлы — если замечено, что savedWith в чёрном списке, тоже что-то вывести.