Форма на дървото на PDF страници: Разгръщане, изравняване и цялост на /Count

Нашето съпътстващо обяснение за реда на PDF страниците покрива основното правило: редът на показване идва от обхождане в дълбочина от ляво надясно на масивите /Kids в дървото /Pages, никога от номера на обекти. Тази статия разглежда дървото от различен ъгъл — неговата форма. Защо зрелите генератори на PDF извеждат йерархии от междинни възли, когато един плосък масив би бил напълно законен? Какво всъщност се променя, когато даден инструмент изравнява (flattens) или възстановява дървото? И какво се случва, когато счетоводството на /Count, което прави цялата структура бърза, спре да казва истината

Разгръщането (fan-out) е решение за производителност

Нищо не принуждава генератора да влага. Документ от 10 000 страници с един коренен възел /Pages и 10 000 листови препратки в един масив /Kids отговаря на спецификацията. Въпреки това PDF Reference препоръчва балансирано дърво за големи документи и масовите генератори следват този съвет със скромно разгръщане, обикновено няколко десетки деца (kids) на междинен възел

Причината е какво трябва да прочете програмата за преглед, преди да може да покаже нещо. Обмислете скок направо към страница 8 214 от този файл с 10 000 страници. С плоска структура на дървото програмата за преглед първо трябва да анализира коренния възел, а този коренен възел е един огромен масив: при приблизително осем байта на непряка препратка, обект от 80 KB, който трябва да бъде токенизиран от край до край, преди запис 8 213 да може да бъде разрешен. С балансирано дърво с разгръщане от 32, същият скок чете корена, сравнява текущите общи суми на /Count, за да избере правилното дете, и се спуска надолу - общо три или четири малки речника, всеки по няколкостотин байта. Това е случайният достъп O(log n), който дървото е проектирано да осигури, и това е цялата причина, поради която /Count съществува в междинните възли: той позволява на четеца да прескочи цяло поддърво, без да отваря нито един обект вътре в него

Формата на дървото също така определя цената на редактирането. Инкрементална актуализация, която вмъква една страница, трябва да пренапише всеки възел, чиито /Kids или /Count са се променили, което означава пътя от родителя на новото листо до корена. В балансирано дърво този път е шепа малки речници, добавени към файла. В плоско дърво "пътят" е единственият гигантски коренен масив, дублиран изцяло при всяка ревизия. Договор, който преминава през тридесет цикъла на преглед и анотиране, може в крайна сметка да влачи тридесет заместени копия на същия 80 KB масив в своя поток от байтове

Вътрешните възли носят наследени атрибути

Междинните възли не са само маршрутизиране. Четирите наследяеми атрибута на страницата - /Resources, /MediaBox, /CropBox и /Rotate - могат да бъдат издигнати на който и да е възел /Pages, където те се прилагат към всяко листо под него, освен ако потомък не ги отмени. Генератор, създаващ доклад с пейзажно приложение, може да изрази това оформление в самото дърво:

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, което поддържа файла компактен и самоподдържащ се: добавете четвърта страница под възела на приложението и тя автоматично излиза пейзажно

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

Изравняване: законно, често срещано, понякога скъпо

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

За типичните документи изравняването (flattening) е безобидно. То вреди при мащабиране по двата вече описани начина: коренният масив се превръща в един голям обект, който всяко отваряне и всеки скок на страница трябва да анализират изцяло, и всяка структурна редакция го пренаписва целия. Това, което изравняването не унищожава, е споделянето чрез непреки препратки — плоско дърво, в което всички 10 000 страници сочат към един и същ обект-речник /Resources, все още е дедупликирано. Губи се само възможността да се остави записът извън страницата и да се позволи на някой предшественик да го предостави

Когато /Count лъже

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

Първият е остарялата бройка, оставена от инкрементална актуализация. Даден редактор вмъква страница, пренаписва непосредствения родител с нов /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

Дървото сега съдържа десет листа, но коренът все още казва девет. Програма за преглед, която вярва на корена, отчита девет страници в брояча на страниците. Такава, която използва вътрешни бройки, за да търси двоично при скок на страница, изчислява грешен индекс за всяка страница след точката на вмъкване. Пълното обхождане намира десет. Три различни отговора, един файл

Вторият модел е бройката, която никога не би могла да бъде вярна: отрицателна, нула във възел с население или абсурдно огромна. Те идват от мъх (fuzzing), от повреди при предаването и понякога от аритметични грешки в редакторите. Те са опасни конкретно за код, който се доверява на /Count за заделяне на памет - оразмеряването на масив от /Count -3 поражда грешка в диапазона в най-добрия случай, а извършването на това от /Count от два милиарда е заделяне на памет с отказ от услуга (denial-of-service). Стойността е ненадежден вход, както всяко друго число във файла

Парсерите се разделят на два лагера по отношение на всичко това. Строгите потребители - инструменти за предварителна проверка (preflight), валидатори на PDF/A, архивни конвейери - сравняват /Count с резултата от обхождането и отхвърлят или маркират файла. Интерактивните програми за преглед са почти универсално снизходителни: те обхождат, извличат реалния брой и безшумно игнорират съхранения, което е точно причината, поради която файл с остарял брой може да циркулира с години без оплакване, докато не срещне по-строг парсер в някакъв автоматизиран работен процес. Защитната средна позиция за библиотечния код е да се третира /Count като подсказка - полезна за предварително заделяне на памет и за прескачане на поддървета, след като бъде проверена - като същевременно обхождането остава източник на истината

За самия алгоритъм на обхождане, правилата за търсене при наследяване и обхождането от каталога до листата, започнете с обяснението за реда на страниците. За това как изглеждат тези режими на отказ, когато реален документ на клиент достигне до производствен код, прочетете казусното проучване за отстраняване на грешки в реда на страниците, което проследява инцидент с разбъркани страници от симптом до основна причина

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