Форма дерева страниц PDF: Разветвление, уплощение и целостность /Count

В нашей статье о порядке страниц PDF рассматривается основное правило: порядок отображения исходит из обхода массивов /Kids в дереве /Pages в глубину слева направо, а не из номеров объектов. В этой статье рассматривается дерево с другого ракурса — его формы. Почему зрелые генераторы PDF создают иерархии промежуточных узлов, когда единый плоский массив был бы совершенно законным? Что на самом деле меняется, когда инструмент уплощает или перестраивает дерево? И что происходит, когда бухгалтерский учет /Count, который делает всю структуру быстрой, перестает говорить правду

Разветвление — это решение для повышения производительности

Ничто не заставляет генератор создавать вложения. 10 000-страничный документ с одним корневым узлом /Pages и 10 000 ссылками на конечные элементы в одном массиве /Kids соответствует спецификации. Тем не менее, Справочник по PDF рекомендует сбалансированное дерево для больших документов, и основные генераторы следуют этому совету со скромным разветвлением, обычно несколько десятков потомков на промежуточный узел

Причина заключается в том, что программа просмотра должна прочитать, прежде чем она сможет что-либо показать. Рассмотрим переход прямо к странице 8 214 этого 10 000-страничного файла. С плоским деревом программа просмотра сначала должна разобрать корневой узел, и этот корневой узел представляет собой один огромный массив: примерно восемь байтов на косвенную ссылку, объект размером 80 КБ, который должен быть токенизирован от начала до конца, прежде чем можно будет разрешить запись 8 213. Сбалансированное дерево с разветвлением 32 для того же перехода читает корень, сравнивает текущие итоги /Count, чтобы выбрать правильный дочерний элемент, и спускается вниз — всего три или четыре небольших словаря, каждый из которых занимает несколько сотен байтов. Это произвольный доступ O(log n), для обеспечения которого и было разработано дерево, и это единственная причина существования /Count на промежуточных узлах: оно позволяет читателю пропустить целое поддерево, не открывая внутри него ни одного объекта

Форма дерева также определяет стоимость редактирования. Инкрементное обновление, которое вставляет одну страницу, должно переписать каждый узел, чьи /Kids или /Count изменились, то есть путь от родителя нового листа вверх к корню. В сбалансированном дереве этот путь представляет собой горстку небольших словарей, добавляемых в файл. В плоском дереве «путь» — это единый гигантский корневой массив, полностью дублируемый при каждой ревизии. Контракт, проходящий через тридцать циклов рецензирования и аннотирования, может в конечном итоге потянуть за собой тридцать замененных копий одного и того же массива размером 80 КБ в своем потоке байтов

Внутренние узлы несут наследуемые атрибуты

Промежуточные узлы — это не просто маршрутизация. Четыре наследуемых атрибута страницы — /Resources, /MediaBox, /CropBox и /Rotate — могут быть подняты на любой узел /Pages, где они применяются к каждому листу под ним, если только потомок не переопределит их. Генератор, создающий отчет с альбомным приложением, может выразить этот макет в самом дереве:

5 0 obj   % корень документа
<< /Type /Pages /Count 6 /Kids [6 0 R  7 0 R] >>
endobj

6 0 obj   % тело отчета: книжная A4, основной шрифт
<< /Type /Pages /Parent 5 0 R /Count 3
   /Kids [30 0 R  31 0 R  32 0 R]
   /MediaBox [0 0 595 842]
   /Resources << /Font << /F1 8 0 R >> >> >>
endobj

7 0 obj   % приложение: альбомная A4, повернутая, свой собственный шрифт
<< /Type /Pages /Parent 5 0 R /Count 3
   /Kids [40 0 R  41 0 R  42 0 R]
   /MediaBox [0 0 842 595] /Rotate 90
   /Resources << /Font << /F2 9 0 R >> >> >>
endobj

40 0 obj  % страница приложения: наследует размер, вращение, шрифты
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

Объекты с 40 по 42 почти пустые. Их размер страницы, вращение и ресурсы шрифтов поступают по наследованию от узла 7, что делает файл компактным и самоподдерживающимся: добавьте четвертую страницу под узел приложения, и она автоматически станет альбомной

Тот же механизм создает классическую опасность перемещения страниц. Предположим, инструмент перемещает объект 40 в тело отчета путем редактирования двух массивов /Kids и перенаправления /Parent на узел 6. Перемещение является структурно правильным, однако объект 40 теперь наследует книжный /MediaBox, отсутствие вращения и шрифт /F1 — в то время как его поток контента по-прежнему выбирает /F2, который больше не разрешается. Страница сжимается, отменяет вращение и теряет свой текст за одно редактирование. Поэтому надежный код переупорядочения материализует разрешенные значения всех четырех наследуемых атрибутов в словаре страниц перед переназначением родителя. Если вы когда-либо перетаскивали страницу в редакторе и наблюдали, как она меняет размер или ориентацию, это тот самый механизм, свидетелем которого вы стали

Уплощение: законно, часто встречается, иногда дорого

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

Для типичных документов уплощение безвредно. Оно вредит при масштабировании, двумя способами, описанными ранее: корневой массив становится одним большим объектом, который каждое открытие и каждый переход на страницу должен полностью парсить, и каждое структурное редактирование переписывает его целиком. Чего уплощение не разрушает, так это совместное использование через косвенные ссылки — плоское дерево, в котором все 10 000 страниц указывают на один и тот же объект словаря /Resources, по-прежнему дедуплицируется. Теряется только возможность не включать запись на страницу и позволить предку предоставить ее

Когда /Count лжет

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

Первый - это устаревший счетчик, оставленный инкрементным обновлением. Редактор вставляет страницу, переписывает непосредственного родителя с новым /Kids и обновленным /Count, добавляет их оба в файл — и никогда не прикасается к предкам:

% Исходная редакция
12 0 obj
<< /Type /Pages /Count 9 /Kids [13 0 R  14 0 R  15 0 R] >>
endobj

14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 3
   /Kids [50 0 R  51 0 R  52 0 R] >>
endobj

% Добавленная редакция: одна страница вставлена в среднюю ветку.
% Объект 14 заменен; объект 12 никогда не переписывается
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 4
   /Kids [50 0 R  51 0 R  90 0 R  52 0 R] >>
endobj

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

Второй шаблон - это счетчик, который никогда не мог быть правильным: отрицательный, ноль на заполненном узле или абсурдно огромный. Они возникают из-за фаззинга, повреждений при передаче и иногда из-за арифметических ошибок в редакторах. Они опасны в первую очередь для кода, который доверяет /Count для выделения памяти — определение размера массива из /Count, равного -3, вызывает ошибку диапазона в лучшем случае, а выполнение того же самого из /Count в два миллиарда - это выделение, вызывающее отказ в обслуживании. Значение является ненадежным вводом, как и любое другое число в файле

Парсеры разделяются на два лагеря по поводу всего этого. Строгие потребители — инструменты предварительной проверки, валидаторы PDF/A, архивные конвейеры — сравнивают /Count с результатом обхода и отклоняют или помечают файл. Интерактивные программы просмотра почти повсеместно снисходительны: они выполняют обход, извлекают реальное количество и молча игнорируют сохраненное, именно поэтому файл с устаревшим счетчиком может циркулировать годами без жалоб, пока не встретится с более строгим парсером внутри какого-либо автоматизированного рабочего процесса. Оборонительная золотая середина для библиотечного кода - это относиться к /Count как к подсказке — полезной для предварительного выделения и для пропуска поддеревьев после проверки — при этом позволяя обходу оставаться источником истины

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

Компонент HotPDF внутренне справляется со всем этим: он обходит вложенные деревья любой глубины, разрешает унаследованные атрибуты при копировании или перемещении страниц и сверяет /Count с фактическим количеством конечных элементов, вместо того чтобы доверять ему, поэтому индексы страниц в его API всегда означают логические страницы