Tvar stromu stránok PDF: vetvenie, sploštenie a integrita /Count

Náš sprievodný článok o poradí stránok v PDF vysvetľuje základné pravidlo: poradie zobrazenia vychádza z prechodu do hĺbky zľava doprava cez polia /Kids v strome /Pages, nikdy z čísiel objektov. Tento článok sa na strom pozerá z iného uhla — na jeho tvar. Prečo vyspelí tvorcovia PDF generujú hierarchie prechodných uzlov, keď by bolo úplne v poriadku použiť jediné ploché pole? Čo sa vlastne zmení, keď nástroj strom sploští alebo prestavia? A čo sa stane, keď účtovníctvo /Count, ktoré robí celú štruktúru rýchlou, prestane hovoriť pravdu

Vetvenie je výkonnostné rozhodnutie

Nič nenúti tvorcu vnárať uzly. Dokument s 10 000 stranami s jedným koreňovým uzlom /Pages a 10 000 odkazmi na listy v jedinom poli /Kids je v súlade so špecifikáciou. PDF Reference napriek tomu odporúča vyvážený strom pre veľké dokumenty a bežné generátory sa touto radou riadia s miernym vetvením, zvyčajne niekoľko desiatok detí na jeden prechodný uzol

Dôvodom je to, čo musí prehliadač prečítať skôr, než čokoľvek zobrazí. Predstavme si skok priamo na stranu 8 214 v tomto súbore s 10 000 stranami. Pri plochom strome musí prehliadač najprv spracovať koreňový uzol, a ten je jedno obrovské pole: pri približne ôsmich bajtoch na nepriamy odkaz ide o 80 KB objekt, ktorý treba tokenizovať od začiatku do konca skôr, než možno rozlíšiť položku 8 213. Pri vyváženom strome s vetvením 32 ten istý skok prečíta koreň, porovná priebežné súčty /Count, aby vybral správne dieťa, a zostupuje — spolu tri alebo štyri malé slovníky, každý s veľkosťou pár sto bajtov. Toto je náhodný prístup so zložitosťou O(log n), na ktorý bol strom navrhnutý, a je to celý dôvod, prečo /Count existuje na prechodných uzloch: umožňuje čítačke preskočiť celý podstrom bez toho, aby otvorila čo i len jediný objekt v ňom

Tvar stromu určuje aj cenu úprav. Prírastková aktualizácia, ktorá vloží jednu stranu, musí prepísať každý uzol, ktorého /Kids alebo /Count sa zmenili, teda cestu od rodiča nového listu až po koreň. Vo vyváženom strome je táto cesta hŕstka malých slovníkov pripojených k súboru. V plochom strome je „cestou“ jediné obrovské koreňové pole, celé duplikované pri každej revízii. Zmluva, ktorá prejde tridsiatimi cyklami pripomienkovania a anotácií, môže v dôsledku toho vo svojom bajtovom prúde ťahať tridsať nahradených kópií toho istého 80 KB poľa

Vnútorné uzly nesú zdedené atribúty

Prechodné uzly nie sú len smerovanie. Štyri dediteľné atribúty stránky — /Resources, /MediaBox, /CropBox a /Rotate — možno umiestniť na ktorýkoľvek uzol /Pages, kde platia pre každý list pod ním, pokiaľ ich potomok neprepíše. Tvorca, ktorý generuje report s prílohou na šírku, môže toto rozloženie vyjadriť priamo v strome:

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   % dodatok: na šírku A4, otočený, s vlastným písmom
<< /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

Objekty 40 až 42 sú takmer prázdne. Ich veľkosť strany, otočenie aj zdroje písiem prichádzajú dedením z uzla 7, čo udržiava súbor kompaktný a samoudržiavajúci sa: pridajte štvrtú stranu pod uzol prílohy a automaticky vyjde na šírku

Ten istý mechanizmus vytvára klasické riziko pri presúvaní strán. Predpokladajme, že nástroj presunie objekt 40 do tela reportu úpravou oboch polí /Kids a zmenou /Parent na uzol 6. Presun je štrukturálne platný, no objekt 40 teraz dedí portrétový /MediaBox, žiadne otočenie a písmo /F1 — zatiaľ čo jeho obsahový prúd stále vyberá /F2, ktoré sa už nedá rozlíšiť. Strana sa jednou úpravou zmenší, prestane byť otočená a stratí svoj text. Robustný kód na zmenu poradia preto pred zmenou rodiča materializuje rozlíšené hodnoty všetkých štyroch dediteľných atribútov do slovníka stránky. Ak ste už niekedy v editore presúvali stranu a sledovali, ako mení veľkosť alebo orientáciu, videli ste práve tento mechanizmus

Sploštenie: legálne, bežné, občas nákladné

Množstvo nástrojov postupuje opačne. Minimalistickí tvorcovia generujú jednoúrovňový strom, pretože je jednoduchý, a mnohé nástroje na zlučovanie a rozdeľovanie prestavajú akýkoľvek načítaný strom do jedného plochého poľa /Kids, pretože generovanie vyváženej štruktúry je práca navyše a ploché výstupy sú vždy v súlade so špecifikáciou. Správna prestavba musí zároveň rozriešiť dedičnosť: každý atribút, ktorý list dedil, treba skopírovať naň, alebo ho preniesť do nového koreňa, ak je jednotný v celom dokumente — inak výstup zmení geometriu presne tak, ako v prípade presunu strany

Pri typických dokumentoch je sploštenie neškodné. Škodí pri väčšom rozsahu, a to dvoma už opísanými spôsobmi: koreňové pole sa stane jedným veľkým objektom, ktorý musí v celku spracovať každé otvorenie aj každý skok na stranu, a každá štrukturálna úprava ho celý prepíše. Sploštenie nezničí zdieľanie cez nepriame odkazy — plochý strom, v ktorom všetkých 10 000 strán ukazuje na ten istý objekt slovníka /Resources, je stále deduplikovaný. Stráca sa len možnosť vynechať položku na stránke a nechať ju doplniť predkom

Keď /Count klame

/Count je čisté účtovníctvo: musí sa rovnať počtu listových strán v podstrome uzla, a nič vo formáte súboru to nevynucuje. Za väčšinu klamlivých počtov, s ktorými sa v praxi stretávame, zodpovedajú dva vzory poškodenia

Prvým je zastaraný počet, ktorý zanechá prírastková aktualizácia. Editor vloží stranu, prepíše najbližšieho rodiča novým /Kids a aktualizovaným /Count, oboje pripojí k súboru — a predkov sa už nikdy nedotkne:

% 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

% Pripojená revízia: jedna strana vložená do strednej vetvy
% 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

Strom teraz obsahuje desať listov, ale koreň stále hovorí deväť. Prehliadač, ktorý dôveruje koreňu, hlási vo svojom počítadle strán deväť strán. Ten, ktorý na binárne vyhľadanie skoku na stranu používa vnútorné počty, vypočíta nesprávny index pre každú stranu za bodom vloženia. Úplný prechod nájde desať. Tri rôzne odpovede, jeden súbor

Druhým vzorom je počet, ktorý nemôže byť nikdy správny: záporný, nulový na obsadenom uzle alebo absurdne obrovský. Pochádzajú z fuzzingu, z poškodenia pri prenose a občas z aritmetických chýb v editoroch. Sú nebezpečné najmä pre kód, ktorý pri alokácii dôveruje /Count — dimenzovanie poľa podľa /Count s hodnotou -3 v najlepšom prípade vyvolá chybu rozsahu a urobiť to isté pri /Count s hodnotou dve miliardy je alokácia typu odopretie služby. Táto hodnota je nedôveryhodný vstup rovnako ako každé iné číslo v súbore

Parsery sa v tomto ohľade delia na dva tábory. Prísni konzumenti — nástroje na preflight, validátory PDF/A, archivačné pipeline — porovnávajú /Count s výsledkom prechodu a súbor odmietnu alebo označia. Interaktívne prehliadače sú takmer vždy benevolentné: prejdú strom, odvodia skutočný počet a uloženú hodnotu potichu ignorujú, čo je presne dôvod, prečo môže súbor so zastaraným počtom kolovať roky bez sťažností, kým nenarazí na prísnejší parser v nejakom automatizovanom pracovnom postupe. Obranným kompromisom pre knižničný kód je zaobchádzať s /Count ako s nápovedou — užitočnou na prealokáciu a na preskakovanie podstromov po overení — pričom zdrojom pravdy zostáva samotný prechod

Samotný algoritmus prechodu, pravidlá vyhľadávania dedičnosti a prechod od katalógu k listu nájdete v článku o poradí stránok. Ako tieto zlyhania vyzerajú, keď sa skutočný dokument zákazníka dostane do produkčného kódu, si prečítajte v prípadovej štúdii ladenia poradia stránok, ktorá sleduje incident s premiešanými stranami od príznaku až po koreňovú príčinu

Komponent HotPDF Delphi Component rieši toto všetko interne: prechádza vnorené stromy ľubovoľnej hĺbky, rozrieši zdedené atribúty pri kopírovaní alebo presúvaní strán a overuje /Count voči skutočnému počtu listov namiesto toho, aby mu dôveroval, takže indexy strán v jeho API vždy znamenajú logické strany