Vores ledsagende forklaring om PDF-siderækkefølge dækker grundreglen: visningsrækkefølge kommer fra en dybde-først, venstre-til-højre gennemgang af /Kids-arrays i /Pages-træet, aldrig fra objektnumre. Denne artikel ser på træet fra en anden vinkel — dets form. Hvorfor udsender modne PDF-skrivere (PDF writers) hierarkier af mellemliggende knuder, når et enkelt fladt array ville være fuldt ud lovligt? Hvad ændres der egentlig, når et værktøj udflader eller genopbygger træet? Og hvad sker der, når /Count-bogføringen, der gør hele strukturen hurtig, holder op med at fortælle sandheden?
Fan-out er en præstationsbeslutning
Intet tvinger en skriver til at indlejre (nest). Et 10.000-siders dokument med én rod /Pages-knude og 10.000 bladreferencer i et enkelt /Kids-array overholder specifikationen. PDF-referencen anbefaler ikke desto mindre et balanceret træ til store dokumenter, og mainstream generatorer følger det råd med en beskeden fan-out, typisk et par dusin børn pr. mellemliggende knude
Årsagen er, hvad en fremviser skal læse, før den kan vise noget. Overvej et hop direkte til side 8.214 i den 10.000-siders fil. Med et fladt træ skal fremviseren først parse rodknuden, og den rodknude er et enormt array: med cirka otte bytes pr. indirekte reference, et 80 KB objekt, der skal tokeniseres fra ende til anden, før indgang 8.213 kan løses. Med et balanceret træ med fan-out 32, læser det samme hop roden, sammenligner løbende /Count-totaler for at vælge det rigtige barn, og stiger ned — i alt tre eller fire små ordbøger, hver på et par hundrede bytes. Det er den O(log n) random access, træet er designet til at give, og det er hele grunden til, at /Count findes på mellemliggende knuder: det lader en læser springe et helt undertræ over uden at åbne et enkelt objekt indeni det
Træform fastsætter også omkostningerne ved redigering. En trinvis opdatering, der indsætter én side, skal omskrive hver knude, hvis /Kids eller /Count ændrede sig, hvilket betyder stien fra det nye blads forælder og op til roden. I et balanceret træ er den sti en håndfuld små ordbøger, der er tilføjet til filen. I et fladt træ er "stien" det enkelte gigantiske rod-array, duplikeret fuldt ud ved hver revision. En kontrakt, der går igennem tredive gennemgangs-og-annoterings-cyklusser (review-and-annotate cycles), kan ende med at slæbe tredive erstattede (superseded) kopier af det samme 80 KB array i sin byte-strøm
Indvendige knuder bærer nedarvede egenskaber
Mellemliggende knuder er ikke kun rutning (routing). De fire nedarvelige sideegenskaber — /Resources, /MediaBox, /CropBox og /Rotate — kan hejses (hoisted) over på en hvilken som helst /Pages-knude, hvor de gælder for hvert blad under det, medmindre en efterkommer tilsidesætter (overrides) dem. En skriver, der producerer en rapport med et landskabs-bilag, kan udtrykke det layout i selve træet:
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 >>
endobjObjekter 40 til 42 er næsten tomme. Deres sidestørrelse, rotation og skrifttype-ressourcer ankommer alle ved nedarvning fra knude 7, hvilket holder filen kompakt og selv-vedligeholdende: tilføj en fjerde side under bilagsknuden (the appendix node), og den kommer automatisk ud i landskab (landscape)
Den samme mekanisme skaber den klassiske side-flytnings-fare (page-move hazard). Antag, at et værktøj flytter objekt 40 ind i rapportens krop ved at redigere de to /Kids-arrays og pege /Parent om til knude 6. Flytningen er strukturelt gyldig, men objekt 40 arver nu portræt /MediaBox, ingen rotation og skrifttype /F1 — mens dets indholdsstrøm (content stream) stadig vælger /F2, som ikke længere løses. Siden krymper, af-roterer og mister sin tekst i en enkelt redigering. Robust omarrangerings-kode (reordering code) materialiserer derfor de løste værdier af alle fire nedarvelige egenskaber på side-ordbogen, før den tildeles en ny forælder (reparenting it). Hvis du nogensinde har trukket en side i en editor og set den ændre størrelse eller orientering, er det denne mekanisme, du var vidne til
Udfladning: lovligt, almindeligt, lejlighedsvis dyrt
Masser af værktøjer går den anden vej. Minimale skrivere udsender et enkeltniveaus træ, fordi det er simpelt, og mange flette- og opdelingsværktøjer (merge and split utilities) genopbygger ethvert træ, de læser, til ét fladt /Kids-array, fordi det er ekstra arbejde at generere balanceret struktur, og fladt output er altid i overensstemmelse (conforming). En korrekt genopbygning skal løse nedarvning (inheritance) på samme tid: enhver egenskab, et blad arvede, skal kopieres over på bladet eller hejses til den nye rod, hvis den er ensartet over hele dokumentet — ellers ændrer outputtet geometri på nøjagtig samme måde, som side-flytningstilfældet gør
For typiske dokumenter er udfladning ufarligt. Det gør ondt i stor skala på de to måder, der allerede er beskrevet: rod-arrayet bliver ét stort objekt, som enhver åbning og ethvert sidehop skal parse fuldt ud, og enhver strukturel redigering omskriver det helt. Hvad udfladning ikke ødelægger, er deling gennem indirekte referencer — et fladt træ, hvor alle 10.000 sider peger på det samme /Resources ordbogsobjekt, er stadig deduplikeret. Det eneste, der går tabt, er muligheden for at udelade indgangen (entry) på siden og lade en forfader (ancestor) levere den
Når /Count lyver
/Count er ren bogføring: det skal være lig med antallet af bladsider i knudens undertræ, og intet i filformatet håndhæver det. To korruptionsmønstre står for størstedelen af de løgnagtige tællinger, man ser i naturen
Den første er det forældede (stale) antal, som en trinvis opdatering efterlader. En editor indsætter en side, omskriver den umiddelbare forælder med en ny /Kids og en opdateret /Count, tilføjer (appends) begge til filen — og rører aldrig forfædrene:
% 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] >>
endobjTræet rummer nu ti blade, men roden siger stadig ni. En fremviser, der stoler på roden, rapporterer ni sider i sin sidetæller. En, der bruger indvendige (interior) tællinger til at binær-søge (binary-search) et sidehop, beregner et forkert indeks for hver side efter indsættelsespunktet. En fuld gennemgang finder ti. Tre forskellige svar, én fil
Det andet mønster er antallet, der aldrig kunne være rigtigt: negativt, nul på en udfyldt (populated) knude eller absurd enormt. Disse kommer fra fuzzing, fra transmissionsskader og lejlighedsvis fra aritmetiske fejl i editorer. De er farlige specifikt for kode, der stoler på /Count til allokering — at dimensionere et array fra en /Count på -3 fremkalder (raises) i bedste fald en intervalfejl, og at gøre det fra en /Count på to milliarder er en denial-of-service allokering. Værdien er upålideligt input (untrusted input), ligesom ethvert andet tal i filen
Parsere deler sig i to lejre over alt dette. Strenge forbrugere (strict consumers) — preflight-værktøjer, PDF/A validatorer, arkiv-pipelines — sammenligner /Count mod gennemgangs-resultatet og afviser eller markerer (flag) filen. Interaktive fremvisere er næsten universelt overbærende (lenient): de gennemgår, udleder det rigtige antal og ignorerer stille det gemte, hvilket er præcis grunden til, at en fil med et forældet antal kan cirkulere i årevis uden klager, indtil den møder en strengere parser inde i et automatiseret workflow. Den defensive mellemvej (middle ground) for bibliotekskode er at behandle /Count som et hint — nyttigt til forhåndsallokering og til at springe undertræer over, når det er verificeret — mens man lader gennemgang (traversal) forblive kilden til sandhed
For selve gennemgangs-algoritmen, nedarvnings-opslagsreglerne og katalog-til-blad (catalog-to-leaf) vandringen, start med siderækkefølge-forklaringen (the page ordering explainer). For at se hvordan disse fejltilstande ser ud, når et rigtigt kundedokument når produktionskode, læs siderækkefølge-fejlfindings-casestudiet, som følger en blandede-sider (shuffled-pages) hændelse fra symptom til grundårsag
HotPDF-komponenten håndterer alt dette internt: den gennemgår indlejrede træer af enhver dybde, løser nedarvede egenskaber, når sider kopieres eller flyttes, og verificerer /Count mod faktiske bladantal i stedet for at stole på det, så sideindekser i dets API altid betyder logiske sider