Stabla stranica u PDF-u: Zašto redoslijed stranica nije isto što i redoslijed objekata

Naš prateći tekst o redoslijedu PDF stranica pokriva osnovno pravilo: redoslijed prikaza proizlazi iz obilaska nizova /Kids u stablu /Pages u dubinu i slijeva nadesno, nikada iz brojeva objekata. Ovaj članak gleda stablo iz drugog kuta — gleda mu oblik. Zašto zreli PDF pisci ispisuju hijerarhije međučvorova kada bi jedan ravan niz bio posve legalan? Što se zapravo mijenja kada alat izravna ili iznova izgradi stablo? I što se događa kada /Count knjigovodstvo, koje cijelu strukturu čini brzom, prestane govoriti istinu

Razgranavanje je odluka o performansama

Ništa ne prisiljava pisca na ugnježđivanje. Dokument od 10.000 stranica s jednim korijenskim /Pages čvorom i 10.000 referenci na listove u jednom jedinom /Kids nizu u skladu je sa specifikacijom. PDF Reference ipak za velike dokumente preporučuje uravnoteženo stablo, a mainstream generatori taj savjet slijede uz skroman fan-out, obično nekoliko desetaka djece po međučvoru

Razlog je u onome što preglednik mora pročitati prije nego što išta može prikazati. Zamislite skok ravno na stranicu 8.214 te datoteke od 10.000 stranica. S ravnim stablom preglednik prvo mora raščlaniti korijenski čvor, a taj je korijenski čvor jedan golem niz: pri otprilike osam bajtova po neizravnoj referenci, objekt od 80 KB koji se mora tokenizirati od početka do kraja prije nego što se unos 8.213 uopće može razriješiti. S uravnoteženim stablom fan-outa 32 isti skok čita korijen, uspoređuje tekuće /Count zbrojeve da odabere pravo dijete i spušta se — ukupno tri ili četiri mala rječnika, svaki od nekoliko stotina bajtova. To je onaj O(log n) nasumični pristup zbog kojeg je stablo i osmišljeno, i to je cijeli razlog zašto /Count postoji na međučvorovima: čitatelju omogućuje da preskoči cijelo podstablo bez otvaranja i jednog objekta u njemu

Oblik stabla određuje i cijenu uređivanja. Inkrementalno ažuriranje koje umetne jednu stranicu mora prepisati svaki čvor kojem se promijenio /Kids ili /Count, dakle cijeli put od roditelja novog lista do korijena. U uravnoteženom stablu taj je put šačica malih rječnika dopisanih na kraj datoteke. U ravnom stablu taj je "put" onaj jedan divovski korijenski niz, dupliciran u cijelosti pri svakoj reviziji. Ugovor koji prođe kroz trideset ciklusa pregleda i anotiranja može u svom toku bajtova vući trideset zamijenjenih kopija istog niza od 80 KB

Unutarnji čvorovi nose naslijeđene atribute

Međučvorovi nisu samo usmjeravanje. Četiri nasljediva atributa stranice — /Resources, /MediaBox, /CropBox i /Rotate — mogu se podići na bilo koji /Pages čvor, gdje vrijede za svaki list ispod njega osim ako ih potomak ne nadjača. Pisac koji radi izvještaj s pejzažnim dodatkom taj raspored može izraziti u samom stablu:

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   % dodatak: pejzažni A4, zakrenut, s vlastitim fontom
<< /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

Objekti 40 do 42 gotovo su prazni. Veličina stranice, rotacija i font resursi svi im stižu nasljeđivanjem od čvora 7, što datoteku drži kompaktnom i samoodrživom: dodajte četvrtu stranicu pod čvor dodatka i ona ispadne pejzažna sama od sebe

Isti mehanizam stvara klasičnu opasnost pri premještanju stranica. Recimo da alat premjesti objekt 40 u tijelo izvještaja uređivanjem dvaju /Kids nizova i preusmjeravanjem /Parent na čvor 6. Premještanje je strukturno valjano, a objekt 40 sada ipak nasljeđuje portretni /MediaBox, nikakvu rotaciju i font /F1 — dok njegov content stream i dalje bira /F2, koji se više ne razrješava. Stranica se smanji, izgubi rotaciju i ostane bez teksta, i to jednim jedinim uređivanjem. Zato robustan kod za preslagivanje prije presađivanja materijalizira razriješene vrijednosti sva četiri nasljediva atributa na rječnik stranice. Ako ste ikada u uređivaču povukli stranicu i gledali kako mijenja veličinu ili orijentaciju, upravo ste ovaj mehanizam vidjeli na djelu

Izravnavanje: legalno, uobičajeno, povremeno skupo

Mnogi alati idu u suprotnom smjeru. Minimalni pisci ispisuju jednorazinsko stablo jer je jednostavno, a mnogi uslužni programi za spajanje i dijeljenje bilo koje pročitano stablo iznova izgrade u jedan ravan /Kids niz, jer je generiranje uravnotežene strukture dodatan posao, a ravan izlaz uvijek je sukladan. Ispravna ponovna izgradnja mora istodobno razriješiti nasljeđivanje: svaki atribut koji je list nasljeđivao mora se prekopirati na taj list ili podići na novi korijen ako je jednak kroz cijeli dokument — inače izlaz mijenja geometriju točno onako kako to čini slučaj s premještanjem stranice

Za tipične dokumente izravnavanje je bezopasno. Boli tek u velikom mjerilu, na dva već opisana načina: korijenski niz postaje jedan velik objekt koji svako otvaranje i svaki skok na stranicu mora raščlaniti u cijelosti, a svako strukturno uređivanje prepisuje ga cijelog. Ono što izravnavanje ne uništava jest dijeljenje kroz neizravne reference — ravno stablo u kojem svih 10.000 stranica pokazuje na isti objekt /Resources rječnika i dalje je deduplicirano. Gubi se samo mogućnost da se unos izostavi sa stranice i prepusti pretku da ga isporuči

Kad /Count laže

/Count je čisto knjigovodstvo: mora biti jednak broju listova u podstablu tog čvora, a ništa u formatu datoteke to ne provodi. Dva obrasca oštećenja odgovorna su za većinu lažnih brojača koji se viđaju u divljini

Prvi je zastarjeli brojač koji za sobom ostavi inkrementalno ažuriranje. Uređivač umetne stranicu, prepiše neposrednog roditelja s novim /Kids i ažuriranim /Count, oboje dopiše na kraj datoteke — i pretke nikad ne dotakne:

% 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

% Dodana revizija: jedna stranica umetnuta je u srednju granu
% 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

Stablo sada drži deset listova, ali korijen i dalje kaže devet. Preglednik koji vjeruje korijenu prijavit će devet stranica u svom brojaču. Onaj koji unutarnje brojače koristi za binarno pretraživanje pri skoku na stranicu izračunat će pogrešan indeks za svaku stranicu iza točke umetanja. Potpun obilazak nalazi deset. Tri različita odgovora, jedna datoteka

Drugi obrazac je brojač koji nikada nije mogao biti ispravan: negativan, nula na popunjenom čvoru ili apsurdno velik. Takvi dolaze iz fuzzinga, iz oštećenja u prijenosu i povremeno iz aritmetičkih grešaka u uređivačima. Opasni su specifično za kod koji vjeruje /Count pri alokaciji — dimenzioniranje niza iz /Count od -3 u najboljem slučaju podiže range error, a isto to iz /Count od dvije milijarde je alokacija koja obara uslugu. Ta je vrijednost nepouzdan ulaz, kao i svaki drugi broj u datoteci

Parseri se oko svega ovoga dijele u dva tabora. Strogi potrošači — preflight alati, PDF/A validatori, arhivski cjevovodi — uspoređuju /Count s rezultatom obilaska pa datoteku odbiju ili označe. Interaktivni preglednici gotovo su listom popustljivi: obiđu stablo, izvedu stvaran broj i pohranjeni tiho ignoriraju, i upravo zato datoteka sa zastarjelim brojačem može godinama kružiti bez ijedne pritužbe dok ne naleti na stroži parser unutar nekog automatiziranog toka. Defenzivna sredina za kod knjižnice jest tretirati /Count kao natuknicu — korisnu za predalokaciju i za preskakanje podstabla nakon provjere — a izvor istine ostaviti obilasku

Za sam algoritam obilaska, pravila traženja naslijeđenih vrijednosti i put od kataloga do lista, počnite s objašnjenjem redoslijeda stranica. Za to kako ovi načini otkazivanja izgledaju kada stvaran dokument kupca stigne do produkcijskog koda, pročitajte studiju slučaja o debugiranju redoslijeda stranica, koja prati incident s izmiješanim stranicama od simptoma do korijenskog uzroka

HotPDF Delphi Component sve ovo rješava interno: obilazi ugniježđena stabla bilo koje dubine, razrješava naslijeđene atribute kada se stranice kopiraju ili premještaju i provjerava /Count u odnosu na stvaran broj listova umjesto da mu vjeruje, pa indeksi stranica u njegovom API-ju uvijek znače logičke stranice