PDF-sidetreform: Utbredelse, utflating og /Count-integritet

Vår ledsagerartikkel om PDF-siderekkefølge dekker grunnregelen: visningsrekkefølgen kommer fra en dybde-først, venstre-til-høyre-gjennomgang av /Kids-matrisene i /Pages-treet, aldri fra objektnumre. Denne artikkelen ser på treet fra en annen vinkel — formen. Hvorfor sender modne PDF-skrivere ut hierarkier av mellomliggende noder når en enkelt flat matrise ville vært helt lovlig? Hva endres egentlig når et verktøy flater ut eller bygger om treet? Og hva skjer når /Count-bokføringen som gjør hele strukturen rask, slutter å fortelle sannheten

Utbredelse (Fan-out) er en ytelsesbeslutning

Ingenting tvinger en skriver til å neste. Et dokument på 10 000 sider med én rot-/Pages-node og 10 000 bladreferanser i én enkelt /Kids-matrise er i samsvar med spesifikasjonen. PDF-referansen anbefaler likevel et balansert tre for store dokumenter, og vanlige generatorer følger det rådet med en beskjeden utbredelse, typisk et par dusin barn per mellomnode

Årsaken er hva et visningsprogram må lese før det kan vise noe. Tenk deg et hopp rett til side 8 214 i den 10 000-siders filen. Med et flatt tre må visningsprogrammet først tolke rotnoden, og den rotnoden er én enorm matrise: med omtrent åtte byte per indirekte referanse, et objekt på 80 KB som må symboliseres ende til ende før oppføring 8 213 kan løses opp. Med et balansert tre med utbredelse 32, leser det samme hoppet roten, sammenligner løpende /Count-totaler for å velge riktig barn, og går nedover — tre eller fire små ordbøker totalt, hver på noen få hundre byte. Det er O(log n) tilfeldig tilgang treet ble designet for å gi, og det er hele grunnen til at /Count eksisterer på mellomnoder: det lar en leser hoppe over et helt undertre uten å åpne et eneste objekt inni det

Treformen setter også kostnaden for redigering. En inkrementell oppdatering som setter inn én side, må skrive om hver node hvis /Kids eller /Count endret seg, noe som betyr banen fra det nye bladets forelder opp til roten. I et balansert tre er den banen en håndfull små ordbøker lagt til filen. I et flatt tre er "banen" den ene gigantiske rotmatrisen, duplisert i sin helhet ved hver revisjon. En kontrakt som går gjennom tretti gjennomgang-og-annoteringssykluser kan ende opp med å dra med seg tretti erstattede kopier av den samme 80 KB-matrisen i bytestrømmen sin

Interiørnoder bærer arvede attributter

Mellomnoder er ikke bare ruting. De fire arvelige sideattributtene — /Resources, /MediaBox, /CropBox og /Rotate — kan løftes opp til enhver /Pages-node, der de gjelder for hvert blad under den, med mindre en etterkommer overstyrer dem. En skriver som produserer en rapport med et landskapsvedlegg, kan uttrykke det oppsettet i selve treet:

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

Objektene 40 til 42 er nesten tomme. Deres sidestørrelse, rotasjon og skrifttyperessurser ankommer alle via arv fra node 7, som holder filen kompakt og selvvedlikeholdende: legg til en fjerde side under vedleggsnoden, og den kommer automatisk ut i landskap

Den samme mekanismen skaper den klassiske sideflyttingsfaren. Anta at et verktøy flytter objekt 40 inn i rapportkroppen ved å redigere de to /Kids-matrisene og peke om /Parent til node 6. Flyttingen er strukturelt gyldig, men objekt 40 arver nå portrett-/MediaBox, ingen rotasjon, og skrifttype /F1 — mens innholdsstrømmen fortsatt velger /F2, som ikke lenger kan løses opp. Siden krymper, av-roterer og mister teksten sin i én enkelt redigering. Robust omorganiseringskode materialiserer derfor de oppløste verdiene av alle fire arvelige attributter på sideordboken før den får ny forelder. Hvis du noen gang har dratt en side i et redigeringsprogram og sett den endre størrelse eller orientering, er dette mekanismen du var vitne til

Utflating (Flattening): lovlig, vanlig, av og til dyrt

Mange verktøy går motsatt vei. Minimale skrivere sender ut et enkeltnivåtre fordi det er enkelt, og mange sammenslåings- og splittingsverktøy bygger om ethvert tre de leser til én flat /Kids-matrise, fordi å generere balansert struktur er ekstra arbeid og flat utdata er alltid i samsvar med spesifikasjonen. En riktig gjenoppbygging må løse opp arv samtidig: hvert attributt et blad arvet, må kopieres til bladet, eller løftes opp til den nye roten hvis det er ensartet på tvers av dokumentet — ellers endrer utdataene geometri akkurat slik sideflyttingstilfellet gjør

For typiske dokumenter er utflating ufarlig. Det gjør vondt i stor skala, på de to måtene som allerede er beskrevet: rotmatrisen blir ett stort objekt som enhver åpning og ethvert sidehopp må tolke i sin helhet, og enhver strukturell redigering skriver den om i sin helhet. Det utflating ikke ødelegger, er deling gjennom indirekte referanser — et flatt tre der alle 10 000 sider peker på samme /Resources-ordbokobjekt, er fortsatt deduplisert. Det som går tapt er bare muligheten til å utelate oppføringen fra siden og la en forfader levere den

Når /Count lyver

/Count er ren bokføring: den må være lik antall bladsider i nodens undertre, og ingenting i filformatet håndhever det. To korrupsjonsmønstre står for de fleste av de løgnaktige tellingene som sees i naturen

Den første er den gamle tellingen etterlatt av en inkrementell oppdatering. Et redigeringsprogram setter inn en side, skriver om den umiddelbare forelderen med en ny /Kids og en oppdatert /Count, legger begge til filen — og rører aldri forfedrene:

% 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

Treet inneholder nå ti blader, men roten sier fortsatt ni. Et visningsprogram som stoler på roten, rapporterer ni sider i sidetelleren sin. Et som bruker interiørtellinger til å binærsøke et sidehopp, beregner feil indeks for hver side etter innsettingspunktet. En full traversering finner ti. Tre forskjellige svar, én fil

Det andre mønsteret er tellingen som aldri kan være riktig: negativ, null på en befolket node, eller absurd stor. Disse kommer fra fuzzing, fra overføringsskader, og av og til fra aritmetiske feil i redigeringsprogrammer. De er farlige spesielt for kode som stoler på /Count for allokering — å dimensjonere en matrise fra en /Count på -3 utløser i beste fall en områdefeil, og å gjøre det fra en /Count på to milliarder er en denial-of-service-allokering. Verdien er uklarert inndata, akkurat som alle andre tall i filen

Parsere deler seg i to leirer angående alt dette. Strenge konsumenter — preflight-verktøy, PDF/A-validatorer, arkivpipelines — sammenligner /Count mot traverseringsresultatet og avviser eller flagger filen. Interaktive visningsprogrammer er nesten universelt milde: de traverserer, utleder den virkelige tellingen og ignorerer stille den lagrede, som er nøyaktig grunnen til at en fil med en gammel telling kan sirkulere i årevis uten klage før den møter en strengere parser inne i en automatisert arbeidsflyt. Den defensive mellomtingen for bibliotekkode er å behandle /Count som et hint — nyttig for forhåndsallokering, og for undertrehopping når den er verifisert — samtidig som traversering forblir kilden til sannhet

For selve traverseringsalgoritmen, oppslagsreglene for arv, og katalog-til-blad-vandringen, start med artikkelen om siderekkefølge. For hvordan disse feilmodusene ser ut når et ekte kundedokument når produksjonskode, les casestudien om feilsøking av siderekkefølge, som følger en hendelse med stokkede sider fra symptom til rotårsak

HotPDF-komponenten håndterer alt dette internt: den traverserer nestede trær av hvilken som helst dybde, løser opp arvede attributter når sider kopieres eller flyttes, og verifiserer /Count mot faktiske bladantall i stedet for å stole på det, slik at sideindekser i dens API alltid betyr logiske sider