Номер объекта 1 — это не страница 1. Один только этот факт ломает больше кода обработки PDF, чем любая другая часть формата, а причина проявляется лишь когда вы перестаёте смотреть на то, что рисует просмотрщик, и начинаете смотреть на граф объектов, который просмотрщик реально читает
Файл PDF — это набор нумерованных косвенных объектов. Каждый несёт номер объекта и номер поколения, а другие объекты указывают на него ссылкой вида N G R — 3 0 R означает текущую версию объекта 3. Страницы — такие же объекты, как любые другие, но где они лежат в файле и какие номера носят, о порядке показа не говорит ничего. Порядок задаёт дерево /Pages. Просканируйте объекты по номерам — и для изрядной доли реальных файлов соберёте страницы не в той последовательности
Дерево — ещё и место, где живёт немало менее очевидного поведения. Его форма решает, как быстро просмотрщик допрыгнет до страницы 8 214, внутренние узлы тихо передают размер страницы и шрифты листьям под собой, а итоги /Count, делающие всю структуру быстрой, ничем не принуждаются. Пройдёмся по всем трём, начав с самого порядка
Порядок задаёт дерево страниц
У каждого PDF есть каталог документа (ISO 32000-2 §7.7.2), и запись /Pages каталога указывает на корневой узел дерева страниц. Корень — это словарь с /Type /Pages, массивом /Kids из косвенных ссылок и /Count, дающим число листовых страниц под ним. Порядок показа — обход этого дерева в глубину слева направо. Вот и всё правило
Минимальный трёхстраничный файл делает это конкретным:
%PDF-1.7
1 0 obj
<< /Type /Catalog /Pages 2 0 R >>
endobj
2 0 obj
<< /Type /Pages /Kids [20 0 R 4 0 R 9 0 R] /Count 3 >>
endobj
% Объект 4 лежит в файле третьим, но является страницей 2 в порядке показа
4 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
/Contents 5 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj
% Объект 9 лежит четвёртым, но является страницей 3
9 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
/Contents 10 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj
% Объект 20 лежит последним, но является страницей 1; решает Kids[0], а не номер объекта
20 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
/Contents 21 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj
Массив /Kids читается как [20 0 R 4 0 R 9 0 R], поэтому объект 20 — страница 1, объект 4 — страница 2, а объект 9 — страница 3. Код, итерирующий объекты по номерам и собирающий всё с /Type /Page, ошибётся на этом файле. Хуже того — вывод всё ещё выглядит правдоподобно: верное число страниц, узнаваемое содержимое на каждой, неверная последовательность
Генераторы выдают такие раскладки по обычным причинам. Библиотека, резервирующая номера объектов для всех страниц заранее, нумерует их в порядке создания, а байты пишет в том порядке, как удобнее её сериализатору. Инструмент слияния перенумеровывает объекты из каждого исходного документа, чтобы избежать коллизий, — объекты страниц оказываются рассыпаны по объединённой таблице объектов, пока новый корневой массив /Kids держит правильную последовательность. А инкрементальные обновления дописывают новые объекты в конец файла со свежими номерами, так что страница, добавленная ревизией, живёт ближе к концу байтового потока, даже если ей положено быть позицией 1
Последний случай и кусает. Корпус тестов, произведённый одним инструментом, может проходить целиком, а потом файлы из слияния или документы, пережившие пару ревизий, выходят перетасованными. Эвристики не держат, потому что сбой зависит от генератора и истории правок файла. Настоящее исправление короткое: стартуйте от каталога, разрешите /Pages, рекурсивно идите по /Kids и выдавайте листья в порядке встречи. Наше расследование отладки порядка страниц проходит ровно этот симптом через ошибочный диагноз к первопричине, с кодом рекурсивного обхода и шагами qpdf для проверки результата
Разветвление — решение о производительности
Спецификация разрешает две формы. Простые генераторы выдают плоское дерево — один корневой узел /Pages, чей /Kids держит одни лишь листья /Page. Ничто не принуждает к вложенности, и 10 000-страничный документ с 10 000 ссылками на листья в одном массиве конформен. Справочник по PDF тем не менее рекомендует сбалансированное дерево для больших документов, и основные генераторы следуют совету со скромным разветвлением — обычно несколько десятков потомков на промежуточный узел, где у каждого промежуточного узла свои /Kids и свой /Count
Причина — в том, что просмотрщик обязан прочитать, прежде чем показать хоть что-то. Возьмём прыжок прямо к странице 8 214 того самого 10 000-страничного файла. С плоским деревом просмотрщик сначала разбирает корень, а корень — один огромный массив: при примерно восьми байтах на косвенную ссылку это объект на 80 КБ, который надо токенизировать от начала до конца, прежде чем разрешится запись 8 213. Со сбалансированным деревом разветвления 32 тот же прыжок читает корень, сверяет текущие итоги /Count, выбирая нужного ребёнка, и спускается. Три-четыре маленьких словаря, по несколько сотен байтов каждый. Тот произвольный доступ O(log n), ради которого дерево и проектировалось, — и вся причина существования /Count на промежуточных узлах: читатель может пропустить целое поддерево, не открыв внутри него ни одного объекта
Форма дерева также определяет стоимость редактирования. Инкрементное обновление, которое вставляет одну страницу, должно переписать каждый узел, чьи /Kids или /Count изменились, то есть путь от родителя нового листа вверх к корню. В сбалансированном дереве этот путь представляет собой горстку небольших словарей, добавляемых в файл. В плоском дереве «путь» — это единый гигантский корневой массив, полностью дублируемый при каждой ревизии. Контракт, проходящий через тридцать циклов рецензирования и аннотирования, может в конечном итоге потянуть за собой тридцать заменённых копий одного и того же массива размером 80 КБ в своём потоке байтов
Для обрабатывающего кода у вложенности есть более прямое следствие. Нельзя предполагать, что первый уровень /Kids содержит страницы, поэтому каждый ребёнок проверяется: /Type /Pages — значит рекурсируем, /Type /Page — значит лист. Код, останавливающийся на первом уровне, работает на каждом плоском файле, какой встретит, а потом молча роняет целые поддеревья, как только какой-то генератор решит вложиться
Внутренние узлы несут наследуемые атрибуты
Промежуточные узлы делают больше, чем маршрутизацию. Четыре атрибута страницы наследуемы (ISO 32000-2 §7.7.3.4): /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 нет ключа /MediaBox, и это совершенно законно — читатель, трактующий отсутствующий ключ как уродливый ввод, отвергнет валидные файлы. Поиску приходится подниматься по цепочке /Parent, пока не найдётся запись или не кончится корень. Тому подъёму нужен цикл-страж. Битый файл может нести ссылку /Parent обратно на уже посещённый узел, и без множества посещённых объектов поиск крутится вечно
Тот же механизм создает классическую опасность перемещения страниц. Предположим, инструмент перемещает объект 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 для выделения памяти — определение размера массива из /Count, равного -3, вызывает ошибку диапазона в лучшем случае, а выполнение того же самого из /Count в два миллиарда — это выделение, вызывающее отказ в обслуживании. Значение является ненадежным вводом, как и любое другое число в файле
Парсеры по всему этому делятся на два лагеря. Строгие потребители — инструменты предварительной проверки, валидаторы PDF/A, архивные конвейеры — сравнивают /Count с результатом обхода и отвергают или помечают файл. Интерактивные просмотрщики почти поголовно снисходительны: они обходят, выводят реальное количество и молча игнорируют сохранённое — именно поэтому файл с устаревшим счётчиком может циркулировать годами без жалоб, пока не встретит более строгий парсер внутри какого-нибудь автоматизированного процесса. Для библиотечного кода мы считаем правильным дефолтом золотую середину: использовать /Count как подсказку для предварительного выделения и для пропуска поддеревьев — но только после проверки, — оставляя обход источником истины
В продакшене эти сбои редко объявляются проблемами дерева. Они выглядят как перетасованные страницы, пропавшая страница в конце слияния или страница, сменившая размер или ориентацию после переупорядочивания. Расследование отладки прослеживает один такой отчёт сквозь дерево. Для окружающей анатомии файла (объекты, таблицы кросс-ссылок, trailers) отправная точка — обзор структуры PDF-файла
Компонент HotPDF внутренне справляется со всем этим: он обходит вложенные деревья любой глубины, разрешает унаследованные атрибуты при копировании или перемещении страниц и сверяет /Count с фактическим количеством конечных элементов, вместо того чтобы доверять ему, поэтому индексы страниц в его API всегда означают логические страницы