Vorm van de PDF-paginaboom: Fan-Out, Flattening en /Count-integriteit

Onze begeleidende uitleg over PDF-paginavolgorde behandelt de basisregel: de weergavevolgorde komt voort uit een depth-first, van-links-naar-rechts doorloop van de /Kids-arrays in de /Pages-boom, nooit uit objectnummers. Dit artikel bekijkt de boom vanuit een andere hoek: de vorm ervan. Waarom geven volwassen PDF-schrijvers hiërarchieën van tussenliggende knooppunten af wanneer één enkele vlakke array volkomen legaal zou zijn? Wat verandert er daadwerkelijk wanneer een tool de boom plat maakt of herbouwt? En wat gebeurt er wanneer de /Count-boekhouding, die de hele structuur snel maakt, stopt met het vertellen van de waarheid?

Fan-out is een beslissing over prestaties

Niets dwingt een schrijver om te nesten. Een document van 10.000 pagina's met één root /Pages-knooppunt en 10.000 bladreferenties (leaf references) in een enkele /Kids-array voldoet aan de specificatie. De PDF Reference raadt desondanks een gebalanceerde boom aan voor grote documenten, en mainstream generatoren volgen dat advies met een bescheiden fan-out, meestal een paar dozijn kinderen per tussenliggend knooppunt.

De reden ligt in wat een viewer moet lezen voordat hij iets kan laten zien. Overweeg een sprong rechtstreeks naar pagina 8.214 van dat bestand van 10.000 pagina's. Bij een vlakke boom moet de viewer eerst het rootknooppunt parsen, en dat rootknooppunt is één enorme array: met ongeveer acht bytes per indirecte referentie is dit een object van 80 KB dat van begin tot eind moet worden getokeniseerd voordat invoer 8.213 kan worden opgelost. Met een gebalanceerde boom met een fan-out van 32 leest dezelfde sprong de root, vergelijkt actuele /Count-totalen om het juiste kind te kiezen, en daalt af — in totaal drie of vier kleine woordenboeken, elk een paar honderd bytes groot. Dat is de O(log n) random-access die de boom moest bieden, en het is de enige reden dat /Count bestaat op tussenliggende knooppunten: het stelt een reader in staat om een volledige subboom over te slaan zonder er een enkel object in te openen.

De vorm van de boom bepaalt ook de bewerkingskosten. Een incrementele update die één pagina invoegt, moet elk knooppunt herschrijven waarvan de /Kids of /Count is gewijzigd. Dat betekent het pad van de ouder van het nieuwe blad tot aan de root. In een gebalanceerde boom is dat pad een handvol kleine woordenboeken die aan het bestand worden toegevoegd. In een vlakke boom is het "pad" de enige enorme root-array, die bij elke revisie volledig wordt gedupliceerd. Een contract dat dertig beoordelings- en annotatiecycli doorloopt, kan zo dertig vervangen kopieën van dezelfde 80 KB-array in zijn bytestream meeslepen.

Binnenste knooppunten dragen geërfde attributen

Tussenliggende knooppunten zijn niet louter voor routing. De vier overerfbare pagina-attributen — /Resources, /MediaBox, /CropBox en /Rotate — kunnen naar elk willekeurig /Pages-knooppunt worden gehesen, waar ze van toepassing zijn op elk blaadje eronder, tenzij een afstammeling ze overschrijft. Een schrijver die een rapport produceert met een liggende (landscape) bijlage, kan die lay-out in de boom zelf uitdrukken:

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

Objecten 40 tot en met 42 zijn vrijwel leeg. Hun paginagrootte, rotatie en lettertypebronnen worden allemaal geërfd van knooppunt 7. Dit houdt het bestand compact en zelfonderhoudend: voeg een vierde pagina toe onder de appendixknoop en deze wordt automatisch in liggende (landscape) stand weergegeven.

Ditzelfde mechanisme creëert het klassieke gevaar van pagina's verplaatsen. Stel dat een tool object 40 verplaatst naar de hoofdtekst (report body) van het rapport door de twee /Kids-arrays te bewerken en /Parent te laten wijzen naar knooppunt 6. De verplaatsing is structureel geldig, maar object 40 erft nu de staande (portrait) /MediaBox, geen rotatie en lettertype /F1 — terwijl de content-stream nog steeds /F2 selecteert, wat niet langer opgelost kan worden. De pagina krimpt, ont-roteert en verliest zijn tekst in één enkele bewerking. Robuuste herschikkingscode (reordering code) materialiseert daarom de opgeloste waarden van alle vier de overerfbare attributen op het paginawoordenboek voordat het opnieuw aan een ouder (reparenting) wordt gekoppeld. Als u ooit een pagina in een editor heeft gesleept en zag dat deze van grootte of oriëntatie veranderde, is dit het mechanisme dat u daar aan het werk zag.

Afvlakken (Flattening): legaal, gebruikelijk, soms duur

Genoeg tools doen het tegenovergestelde. Minimale schrijvers geven een boom van één niveau af omdat het eenvoudig is. Veel hulpprogramma's voor samenvoegen (merge) en splitsen bouwen de boom die ze inlezen om tot één vlakke /Kids-array, omdat het genereren van een gebalanceerde structuur extra werk is en een vlakke uitvoer (flat output) altijd conform de standaard is. Een correcte herbouw (rebuild) moet de overerving gelijktijdig oplossen: elk attribuut dat een blad erfde, moet naar het blad gekopieerd worden, of naar de nieuwe root worden gehesen als het overal in het document uniform is. Gebeurt dit niet, dan verandert de geometrie van de uitvoer precies op dezelfde manier als bij het verplaatsen van de pagina.

Voor typische documenten is het afvlakken (flattening) onschadelijk. Het schaadt wel op grote schaal, op de twee manieren die we al hebben beschreven: de root-array wordt één groot object dat bij elke opening en elke paginasprong volledig geparseerd moet worden. Elke structurele bewerking moet het in zijn geheel herschrijven. Wat afvlakking niet vernietigt, is het delen via indirecte referenties — een vlakke boom waarin alle 10.000 pagina's naar hetzelfde /Resources-woordenboekobject wijzen, is nog steeds gededupliceerd. Wat verloren gaat, is alleen de mogelijkheid om de invoer van de pagina weg te laten en een voorouder (ancestor) deze te laten aanleveren.

Wanneer /Count liegt

/Count is pure boekhouding: het moet gelijk zijn aan het aantal bladpagina's in de subboom van het knooppunt, en niets in het bestandsformaat dwingt dat af. Twee corruptiepatronen zijn verantwoordelijk voor de meeste van de liegende tellers (counts) die in het wild (in de praktijk) worden gezien.

De eerste is de verouderde (stale) telling die achterblijft door een incrementele update. Een editor voegt een pagina in, herschrijft de directe ouder (immediate parent) met een nieuwe /Kids en een bijgewerkte /Count, en voegt beide toe aan het bestand — maar raakt de voorouders (ancestors) nooit aan:

% 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

De boom bevat nu tien bladeren, maar de root zegt nog steeds negen. Een viewer die de root vertrouwt, meldt negen pagina's in de paginateller. Een viewer die interne tellingen (interior counts) gebruikt om binair te zoeken voor een paginasprong, berekent een verkeerde index voor elke pagina na het invoegpunt. Een volledige doorloop (traversal) vindt er tien. Drie verschillende antwoorden, in één bestand.

Het tweede patroon is de telling die onmogelijk juist kan zijn: negatief, nul bij een bevolkte knoop (populated node), of absurd groot. Deze zijn afkomstig van fuzzing, van transmissieschade en af en toe van rekenfouten in editors. Ze zijn specifiek gevaarlijk voor code die /Count vertrouwt voor geheugentoewijzing (allocation) — de grootte van een array bepalen met een /Count van -3 veroorzaakt in het beste geval een bereikfout (range error), en hetzelfde doen met een /Count van twee miljard resulteert in een denial-of-service-toewijzing. De waarde is onvertrouwde invoer, net als elk ander getal in het bestand.

Parsers vallen hierbij uiteen in twee kampen. Strikte consumenten — preflight-tools, PDF/A-validators, archiveringspijplijnen — vergelijken /Count met het resultaat van de doorloop en weigeren of markeren (flag) het bestand. Interactieve viewers zijn bijna universeel soepel (lenient): ze doorlopen de boom, bepalen de echte telling, en negeren stilzwijgend de opgeslagen telling. Dit is precies de reden waarom een bestand met een verouderde telling jarenlang zonder klachten kan circuleren totdat het een striktere parser tegenkomt in een of andere geautomatiseerde workflow. De defensieve middenweg voor bibliotheekcode is om /Count als een hint te beschouwen — nuttig voor pre-allocatie en voor het overslaan van subbomen na verificatie — terwijl de boomdoorloop (traversal) de bron van de waarheid blijft.

Voor het traversale algoritme zelf, de opzoekregels voor overerving en de loop van catalogus naar blad (catalog-to-leaf walk), begint u met de uitleg over paginavolgorde. Om te zien hoe deze storingsmodi (failure modes) eruitzien wanneer een echt klantdocument in productiecode terechtkomt, leest u de casestudy over het debuggen van de paginavolgorde, die een incident met door elkaar gegooide pagina's volgt van symptoom tot oorzaak (root cause).

De HotPDF-component handelt dit allemaal intern af: het doorloopt geneste bomen van elke willekeurige diepte, lost geërfde attributen op wanneer pagina's worden gekopieerd of verplaatst, en verifieert /Count met actuele blad-tellingen (leaf counts) in plaats van het te vertrouwen. Hierdoor betekenen pagina-indices in de bijbehorende API altijd logische pagina's.