PDF stabla stranica: Zašto redosled stranica nije redosled objekata

Prateći tekst o redosledu PDF stranica objašnjava osnovno pravilo: redosled prikaza dolazi iz obilaska nizova /Kids u stablu /Pages po dubini, sleva nadesno, a nikada iz brojeva objekata. Ovaj članak posmatra stablo iz drugog ugla — njegov oblik. Zašto zreli PDF pisači stvaraju hijerarhije međučvorova kada bi jedan ravan niz bio potpuno dozvoljen? Šta se menja kada alat izravna ili ponovo izgradi stablo? I šta se dešava kada evidencija /Count, koja strukturu čini brzom, prestane da govori istinu

Širina grananja je odluka o performansama

Ništa ne primorava pisač da koristi ugnježđavanje. Dokument od 10.000 stranica sa jednim korenskim čvorom /Pages i 10.000 referenci listova u jednom nizu /Kids usklađen je sa specifikacijom. PDF Reference ipak preporučuje uravnoteženo stablo za velike dokumente, a uobičajeni generatori prate tu preporuku umerenom širinom grananja, najčešće sa nekoliko desetina dece po međučvoru

Razlog je količina podataka koju čitač mora da obradi pre prikaza. Zamislite direktan skok na stranicu 8.214 dokumenta od 10.000 stranica. Kod ravnog stabla čitač prvo parsira korenski čvor, jedan ogroman niz: pri približno osam bajtova po indirektnoj referenci to je objekat od oko 80 KB koji mora biti tokenizovan do kraja pre razrešavanja unosa 8.213. Kod uravnoteženog stabla širine 32 isti skok čita koren, poredi tekuće zbirove /Count da izabere odgovarajuće dete i silazi kroz ukupno tri ili četiri mala rečnika od po nekoliko stotina bajtova. To je O(log n) nasumični pristup za koji je stablo projektovano i ceo razlog postojanja /Count na međučvorovima: čitač može preskočiti celo podstablo bez otvaranja ijednog objekta u njemu

Oblik stabla određuje i cenu izmena. Inkrementalno ažuriranje koje umeće jednu stranicu mora ponovo da upiše svaki čvor čiji su se /Kids ili /Count promenili, odnosno putanju od roditelja novog lista do korena. U uravnoteženom stablu ta putanja je nekoliko malih rečnika dodatih na kraj datoteke. U ravnom stablu putanja je jedan ogroman korenski niz koji se u celini duplira u svakoj reviziji. Ugovor koji prođe kroz trideset ciklusa pregleda i anotiranja može tako nositi trideset zastarelih kopija istog niza od 80 KB

Međučvorovi nose nasleđene atribute

Međučvorovi nisu samo rutiranje. Četiri naslediva atributa stranice — /Resources, /MediaBox, /CropBox i /Rotate — mogu biti postavljena na bilo koji čvor /Pages, gde važe za svaki list ispod njega dok ih potomak ne nadjača. Pisač izveštaja sa pejzažnim dodatkom može taj raspored izraziti samim stablom:

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

Objekti 40 do 42 gotovo su prazni. Veličina stranice, rotacija i resursi fonta dolaze nasleđivanjem iz čvora 7, pa datoteka ostaje kompaktna i laka za održavanje: dodata četvrta stranica ispod čvora dodatka automatski postaje pejzažna

Isti mehanizam stvara klasičnu zamku pri pomeranju stranice. Pretpostavimo da alat premesti objekat 40 u telo izveštaja izmenom dva niza /Kids i promenom /Parent na čvor 6. Pomeranje je strukturno važeće, ali objekat 40 sada nasleđuje portretnu vrednost /MediaBox, nema rotaciju i dobija font /F1, dok njegov tok sadržaja i dalje bira /F2, koji se više ne može razrešiti. Stranica se smanjuje, gubi rotaciju i tekst u jednoj izmeni. Robustan kod za promenu redosleda zato pre promene roditelja upisuje razrešene vrednosti sva četiri naslediva atributa u rečnik stranice. Ako ste ikada prevukli stranicu u uređivaču i gledali kako joj se menjaju veličina ili orijentacija, videli ste upravo ovaj mehanizam

Izravnavanje je dozvoljeno, uobičajeno i ponekad skupo

Mnogi alati rade u suprotnom smeru. Minimalni pisači emituju stablo sa jednim nivoom jer je jednostavno, a mnogi alati za spajanje i deljenje ponovo grade pročitano stablo u jedan ravan niz /Kids, pošto uravnotežena struktura zahteva dodatni rad, dok je ravan izlaz uvek usklađen. Ispravna ponovna izgradnja mora istovremeno da razreši nasleđivanje: svaki atribut koji je list nasleđivao mora biti kopiran na list ili podignut na novi koren ako je isti u celom dokumentu. U suprotnom se geometrija izlaza menja kao u slučaju pomeranja stranice

Za uobičajene dokumente izravnavanje je bezazleno. Na velikoj skali šteti na dva već opisana načina: korenski niz postaje jedan veliki objekat koji svako otvaranje i svaki skok na stranicu moraju u celini da parsiraju, a svaka strukturna izmena ga ponovo ispisuje. Izravnavanje ne uništava deljenje preko indirektnih referenci — ravno stablo u kojem svih 10.000 stranica pokazuje na isti objekat rečnika /Resources i dalje je deduplikovano. Gubi se samo mogućnost da se unos izostavi sa stranice i prepusti pretku

Kada /Count laže

/Count je čisto knjigovodstvo: mora biti jednak broju listova stranica u podstablu čvora, ali ništa u formatu datoteke to ne nameće. Dva obrasca oštećenja objašnjavaju većinu netačnih vrednosti koje se sreću u praksi

Prvi je zastareli broj posle inkrementalnog ažuriranja. Uređivač ubaci stranicu, ponovo upiše neposrednog roditelja sa novim /Kids i ažuriranim /Count, doda oba objekta u datoteku, ali ne izmeni pretke:

% 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

Stablo sada ima deset listova, ali koren i dalje kaže devet. Čitač koji veruje korenu prikazuje devet stranica. Čitač koji koristi unutrašnje brojeve za binarnu pretragu skoka izračunava pogrešan indeks za svaku stranicu posle mesta umetanja. Potpuni obilazak pronalazi deset. Tri odgovora u jednoj datoteci

Drugi obrazac je broj koji nikada nije mogao biti ispravan: negativan, nula na popunjenom čvoru ili apsurdno velik. Takve vrednosti potiču od fuzzing-a, oštećenja pri prenosu i povremenih aritmetičkih grešaka u uređivačima. Posebno su opasne za kod koji veruje /Count pri alokaciji — niz veličine /Count -3 u najboljem slučaju izaziva grešku opsega, a vrednost od dve milijarde pokušava alokaciju pogodnu za uskraćivanje usluge. Ta vrednost je nepouzdan ulaz kao i svaki drugi broj u datoteci

Parseri se dele u dva tabora. Strogi potrošači — preflight alati, PDF/A validatori i arhivski cevovodi — porede /Count sa rezultatom obilaska i odbacuju ili označavaju datoteku. Interaktivni čitači su gotovo uvek tolerantni: obilaze stablo, izvode stvaran broj i tiho zanemaruju zapisanu vrednost. Zato datoteka sa zastarelim brojem može godinama kružiti bez problema dok ne stigne do strožeg parsera u automatizovanom toku. Odbrambeni pristup za biblioteku jeste tretirati /Count kao nagoveštaj, koristan za predalokaciju i preskakanje podstabla tek nakon provere, dok obilazak ostaje izvor istine

Za sam algoritam obilaska, pravila traženja nasleđivanja i prolaz od kataloga do lista pogledajte tekst o redosledu stranica. Za izgled ovih grešaka kada stvarni korisnički dokument stigne u produkcioni kod pogledajte studiju slučaja otklanjanja greške redosleda stranica, koja prati incident sa izmešanim stranicama od simptoma do osnovnog uzroka

HotPDF Component sve ovo obrađuje interno: obilazi ugnježđena stabla bilo koje dubine, razrešava nasleđene atribute pri kopiranju ili pomeranju stranica i proverava /Count prema stvarnom broju listova umesto da mu veruje, pa indeksi stranica u njegovom API-ju uvek označavaju logičke stranice