Forma arborelui de pagini PDF: ramificare, aplatizare și integritatea /Count

Articolul nostru complementar despre ordinea paginilor PDF acoperă regula de bază: ordinea de afișare provine dintr-o parcurgere în adâncime, de la stânga la dreapta, a tablourilor /Kids din arborele /Pages, niciodată din numerele obiectelor. Acest articol privește arborele dintr-un unghi diferit — forma sa. De ce generatoarele PDF mature produc ierarhii de noduri intermediare atunci când un singur tablou plat ar fi perfect valid? Ce se schimbă de fapt când un instrument aplatizează sau reconstruiește arborele? Și ce se întâmplă când evidența /Count, care face ca întreaga structură să fie rapidă, încetează să mai spună adevărul

Ramificarea este o decizie de performanță

Nimic nu obligă un generator să imbrice noduri. Un document de 10.000 de pagini cu un singur nod /Pages rădăcină și 10.000 de referințe frunză într-un singur tablou /Kids respectă specificația. Cu toate acestea, PDF Reference recomandă un arbore echilibrat pentru documente mari, iar generatoarele consacrate urmează acest sfat cu o ramificare modestă, de obicei câteva zeci de copii per nod intermediar

Motivul este ceea ce trebuie să citească un vizualizator înainte de a putea afișa ceva. Luați în considerare un salt direct la pagina 8.214 din acel fișier de 10.000 de pagini. Cu un arbore plat, vizualizatorul trebuie mai întâi să analizeze nodul rădăcină, iar acel nod rădăcină este un tablou uriaș: la aproximativ opt octeți per referință indirectă, un obiect de 80 KB care trebuie tokenizat integral înainte ca intrarea 8.213 să poată fi rezolvată. Cu un arbore echilibrat cu ramificare 32, același salt citește rădăcina, compară totalurile /Count curente pentru a alege copilul corect și coboară — în total trei sau patru dicționare mici, fiecare de câteva sute de octeți. Acesta este accesul aleatoriu O(log n) pentru care a fost proiectat arborele și este exact motivul pentru care /Count există pe nodurile intermediare: permite unui cititor să sară peste un întreg subarbore fără să deschidă niciun obiect din interiorul lui

Forma arborelui stabilește și costul editării. O actualizare incrementală care inserează o pagină trebuie să rescrie fiecare nod al cărui /Kids sau /Count s-a schimbat, adică traseul de la părintele noii frunze până la rădăcină. Într-un arbore echilibrat, acel traseu înseamnă câteva dicționare mici adăugate la fișier. Într-un arbore plat, „traseul” este chiar tabloul rădăcină uriaș, duplicat integral la fiecare revizie. Un contract care trece prin treizeci de cicluri de revizuire și adnotare poate ajunge să care treizeci de copii depășite ale aceluiași tablou de 80 KB în fluxul său de octeți

Nodurile interioare poartă atribute moștenite

Nodurile intermediare nu servesc doar la rutare. Cele patru atribute de pagină moștenibile — /Resources, /MediaBox, /CropBox și /Rotate — pot fi ridicate pe orice nod /Pages, unde se aplică fiecărei frunze de dedesubt, cu excepția cazului în care un descendent le suprascrie. Un generator care produce un raport cu o anexă în format vedere poate exprima acest aspect chiar în arbore:

5 0 obj   % rădăcina documentului
<< /Type /Pages /Count 6 /Kids [6 0 R  7 0 R] >>
endobj

6 0 obj   % corpul raportului: A4 portret, font de bază
<< /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   % anexă: A4 vedere, rotită, font propriu
<< /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  % pagină din anexă: moștenește dimensiunea, rotația, fonturile
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

Obiectele 40 până la 42 sunt aproape goale. Dimensiunea paginii, rotația și resursele de fonturi ajung toate prin moștenire de la nodul 7, ceea ce menține fișierul compact și autonom: adăugați o a patra pagină sub nodul anexei și aceasta va apărea automat în format vedere

Același mecanism creează pericolul clasic al mutării paginilor. Să presupunem că un instrument mută obiectul 40 în corpul raportului, editând cele două tablouri /Kids și repunctând /Parent către nodul 6. Mutarea este valabilă din punct de vedere structural, totuși obiectul 40 moștenește acum /MediaBox portret, nicio rotație și fontul /F1 — în timp ce fluxul său de conținut încă selectează /F2, care nu mai poate fi rezolvat. Pagina se micșorează, își pierde rotația și pierde textul într-o singură editare. Codul robust de reordonare, prin urmare, materializează valorile rezolvate ale tuturor celor patru atribute moștenibile pe dicționarul paginii înainte de a-i schimba părintele. Dacă ați tras vreodată o pagină într-un editor și ați văzut-o schimbându-și dimensiunea sau orientarea, acesta este mecanismul pe care l-ați observat

Aplatizarea: legală, obișnuită, ocazional costisitoare

Multe instrumente merg în direcția opusă. Generatoarele minimale produc un arbore cu un singur nivel pentru că e simplu, iar multe utilitare de îmbinare și divizare reconstruiesc orice arbore citesc într-un singur tablou /Kids plat, deoarece generarea unei structuri echilibrate înseamnă muncă suplimentară, iar o ieșire plată este întotdeauna conformă. O reconstrucție corectă trebuie să rezolve moștenirea în același timp: fiecare atribut pe care o frunză îl moștenea trebuie copiat pe frunză sau ridicat la noua rădăcină dacă este uniform pe tot documentul — altfel rezultatul schimbă geometria exact așa cum o face cazul mutării paginii

Pentru documentele obișnuite, aplatizarea este inofensivă. Devine problematică la scară mare, în cele două moduri deja descrise: tabloul rădăcină devine un singur obiect mare pe care fiecare deschidere și fiecare salt de pagină trebuie să îl analizeze integral, iar fiecare editare structurală îl rescrie în întregime. Ce nu distruge aplatizarea este partajarea prin referințe indirecte — un arbore plat în care toate cele 10.000 de pagini indică același obiect dicționar /Resources rămâne în continuare dedublat. Ce se pierde este doar opțiunea de a lăsa intrarea în afara paginii și de a permite unui strămoș să o furnizeze

Când /Count minte

/Count este evidență pură: trebuie să fie egal cu numărul de pagini frunză din subarborele nodului, iar nimic din formatul de fișier nu impune asta. Două tipare de corupție explică majoritatea numerelor mincinoase întâlnite în practică

Primul este numărul învechit, lăsat în urmă de o actualizare incrementală. Un editor inserează o pagină, rescrie părintele imediat cu un nou /Kids și un /Count actualizat, adaugă ambele la fișier — și nu atinge niciodată strămoșii:

% Revizia originală
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

% Revizie adăugată: o pagină inserată în ramura din mijloc.
% Obiectul 14 este înlocuit; obiectul 12 nu este niciodată rescris
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

Arborele conține acum zece frunze, dar rădăcina încă spune nouă. Un vizualizator care are încredere în rădăcină raportează nouă pagini în contorul său de pagini. Unul care folosește numerele interioare pentru a face o căutare binară la un salt de pagină calculează un indice greșit pentru fiecare pagină de după punctul de inserare. O parcurgere completă găsește zece. Trei răspunsuri diferite, un singur fișier

Al doilea tipar este numărul care nu ar fi putut fi niciodată corect: negativ, zero pe un nod populat sau absurd de mare. Acestea provin din fuzzing, din deteriorări în timpul transmiterii și, ocazional, din erori aritmetice în editoare. Sunt periculoase în special pentru codul care are încredere în /Count pentru alocare — dimensionarea unui tablou pe baza unui /Count de -3 provoacă, în cel mai bun caz, o eroare de interval, iar făcând acest lucru pentru un /Count de două miliarde înseamnă o alocare de tip denial-of-service. Valoarea este o intrare nesigură, ca orice alt număr din fișier

Analizoarele se împart în două tabere în privința tuturor acestora. Consumatorii stricți — instrumentele de preflight, validatoarele PDF/A, fluxurile de arhivare — compară /Count cu rezultatul parcurgerii și resping sau semnalează fișierul. Vizualizatoarele interactive sunt aproape universal permisive: parcurg arborele, deduc numărul real și ignoră tacit valoarea stocată, motiv pentru care un fișier cu un număr învechit poate circula ani de zile fără nicio plângere, până întâlnește un analizor mai strict într-un flux de lucru automatizat. Calea de mijloc defensivă pentru codul de bibliotecă este să trateze /Count ca pe un indiciu — util pentru prealocare și pentru sărirea subarborilor odată verificat — lăsând totuși parcurgerea ca sursă de adevăr

Pentru algoritmul de parcurgere propriu-zis, regulile de căutare a moștenirii și traseul de la catalog la frunză, începeți cu articolul explicativ despre ordinea paginilor. Pentru cum arată aceste moduri de eșec atunci când un document real al unui client ajunge în codul de producție, citiți studiul de caz de depanare a ordinii paginilor, care urmărește un incident cu pagini amestecate de la simptom până la cauza principală

Componenta HotPDF gestionează toate acestea intern: parcurge arbori imbricați de orice adâncime, rezolvă atributele moștenite atunci când paginile sunt copiate sau mutate și verifică /Count față de numărul real de frunze în loc să aibă încredere în el, astfel încât indicii de pagină din API-ul său înseamnă întotdeauna pagini logice