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

Наша супутня стаття-пояснення щодо порядку сторінок PDF охоплює основне правило: порядок відображення походить від обходу масивів /Kids у дереві /Pages у глибину зліва направо, і ніколи не від номерів об'єктів. Ця стаття розглядає дерево під іншим кутом — його форму. Чому зрілі PDF-генератори створюють ієрархії проміжних вузлів, коли один плоский масив був би абсолютно законним? Що насправді змінюється, коли інструмент робить дерево плоским (flattens) або перебудовує його? І що відбувається, коли облік /Count, який робить усю структуру швидкою, перестає показувати правду

Розгалуження (Fan-out) — це рішення щодо продуктивності

Нічого не змушує генератор робити вкладення. 10 000-сторінковий документ з одним кореневим вузлом /Pages та 10 000 посилань на листки в єдиному масиві /Kids відповідає специфікації. Утім, посібник з PDF рекомендує збалансоване дерево для великих документів, і основні генератори дотримуються цієї поради зі скромним розгалуженням (fan-out), зазвичай кілька десятків дітей на проміжний вузол

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

Форма дерева також встановлює вартість редагування. Поступове оновлення (incremental update), яке вставляє одну сторінку, має переписати кожен вузол, чий /Kids або /Count змінився, тобто шлях від батьківського елемента нового листка до кореня. У збалансованому дереві цей шлях — це кілька невеликих словників, доданих до файлу. У плоскому дереві "шлях" — це один гігантський кореневий масив, який повністю дублюється на кожній ревізії. Контракт, який проходить через тридцять циклів перегляду й анотування, може в кінцевому підсумку тягнути за собою тридцять замінених копій того самого масиву розміром 80 КБ у своєму потоці байтів

Внутрішні вузли несуть успадковані атрибути

Проміжні вузли — це не лише маршрутизація. Чотири успадковуваних атрибути сторінки — /Resources, /MediaBox, /CropBox і /Rotate — можуть бути підняті (hoisted) на будь-який вузол /Pages, де вони застосовуються до кожного листка під ним, якщо нащадок їх не перевизначає. Програма зчитування (writer), що створює звіт з альбомним (landscape) додатком, може виразити цей макет у самому дереві:

5 0 obj   % document root
<< /Type /Pages /Count 6 /Kids [6 0 R  7 0 R] >>
endobj

6 0 obj   % report body: portrait A4, body font
<< /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   % appendix: landscape A4, rotated, its own font
<< /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  % appendix page: inherits size, rotation, fonts
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

Об'єкти з 40 по 42 майже порожні. Їхній розмір сторінки, обертання та ресурси шрифтів надходять через успадкування від вузла 7, що робить файл компактним і таким, що підтримує сам себе (self-maintaining): додайте четверту сторінку до вузла додатка, і вона автоматично стане альбомною

Цей самий механізм створює класичну небезпеку переміщення сторінки. Припустимо, інструмент переміщує об'єкт 40 до тіла звіту, редагуючи два масиви /Kids і перенаправляючи /Parent на вузол 6. Це переміщення структурно правильне, однак об'єкт 40 тепер успадковує портретний /MediaBox, без обертання, та шрифт /F1 — у той час, як його потік вмісту все ще вибирає /F2, який більше не визначається. Сторінка зменшується, втрачає обертання і втрачає свій текст в одному редагуванні. Тому надійний код перевпорядкування (reordering code) матеріалізує дозволені (resolved) значення всіх чотирьох успадковуваних атрибутів у словник сторінки перед тим, як змінити її батьківський елемент (reparenting). Якщо ви коли-небудь перетягували сторінку в редакторі і спостерігали, як вона змінює розмір або орієнтацію, це той самий механізм, свідком якого ви стали

Сплощення (Flattening): законне, поширене, іноді дороге

Багато інструментів ідуть іншим шляхом. Мінімальні генератори створюють однорівневе дерево, оскільки воно просте, а багато утиліт об'єднання та розділення (merge and split) перебудовують будь-яке дерево, яке вони зчитують, в один плоский масив /Kids, тому що створення збалансованої структури — це додаткова робота, а плоский вивід (flat output) завжди відповідає стандарту. Правильна перебудова (rebuild) має одночасно дозволяти (resolve) успадкування: кожен атрибут, який листок успадковував, повинен бути скопійований у листок або піднятий (hoisted) до нового кореня, якщо він однаковий у всьому документі — інакше вивід змінить геометрію точно так само, як у випадку переміщення сторінки

Для типових документів сплощення нешкідливе. Це завдає шкоди у масштабі, у двох аспектах, які вже описані: кореневий масив стає одним великим об'єктом, який має повністю аналізуватися під час кожного відкриття і кожного переходу на сторінку, а кожне структурне редагування переписує його цілком. Чого сплощення не знищує, так це спільного використання через непрямі посилання — плоске дерево, в якому всі 10 000 сторінок вказують на той самий об'єкт словника /Resources, залишається дедуплікованим (deduplicated). Втрачається лише можливість не вказувати запис на сторінці й дозволити предку надати його

Коли /Count бреше

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

Перший — це застарілий (stale) підрахунок, залишений поступовим оновленням. Редактор вставляє сторінку, переписує безпосереднього батька з новим /Kids і оновленим /Count, додає їх до файлу — і ніколи не чіпає предків:

% Original revision
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

% Appended revision: one page inserted into the middle branch.
% Object 14 is superseded; object 12 is never rewritten
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

Дерево тепер містить десять листків, але корінь усе ще говорить про дев'ять. Програма перегляду, яка довіряє кореню, повідомляє про дев'ять сторінок у своєму лічильнику сторінок. Та, що використовує внутрішні підрахунки для бінарного пошуку при переході на сторінку, обчислює неправильний індекс для кожної сторінки після точки вставки. Повний обхід (full traversal) знаходить десять. Три різні відповіді, один файл

Другий шаблон — це підрахунок, який ніколи не міг бути правильним: від'ємний, нульовий на заповненому вузлі або абсурдно великий. Це виникає через фазинг (fuzzing), пошкодження під час передачі та іноді через арифметичні помилки в редакторах. Вони небезпечні саме для коду, який довіряє /Count для розподілу пам'яті (allocation) — визначення розміру масиву з /Count, що дорівнює -3, у кращому випадку викликає помилку діапазону (range error), а виконання цього для /Count у два мільярди є відмовою в обслуговуванні через розподіл пам'яті (denial-of-service allocation). Це значення — недовірені вхідні дані, як і будь-яке інше число у файлі

Синтаксичні аналізатори (Parsers) розділяються на два табори стосовно цього всього. Суворі (Strict) споживачі — інструменти попередньої перевірки (preflight), валідатори PDF/A, архівні конвеєри (archival pipelines) — порівнюють /Count із результатом обходу та відхиляють (reject) або позначають (flag) файл. Інтерактивні програми перегляду майже завжди м'які (lenient): вони роблять обхід, виводять реальний підрахунок і непомітно ігнорують збережений, саме тому файл із застарілим підрахунком може циркулювати роками без скарг, доки не зустрінеться зі суворішим аналізатором у якомусь автоматизованому робочому процесі. Захисною золотою серединою для бібліотечного коду є розгляд /Count як підказки — корисної для попереднього виділення пам'яті та для пропуску піддерев після перевірки — залишаючи обхід (traversal) джерелом істини

Для самого алгоритму обходу, правил пошуку успадкування (inheritance lookup rules) та проходження від каталогу до листка (catalog-to-leaf walk) почніть із пояснення порядку сторінок. Для того, щоб побачити, як виглядають ці режими збоїв, коли реальний клієнтський документ потрапляє до робочого коду, прочитайте приклад налагодження порядку сторінок, який відстежує інцидент із перемішаними сторінками від симптому до першопричини (root cause)

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