A kapcsolódó cikkünk a PDF oldalsorrendről tárgyalja az alapszabályt: a megjelenítési sorrend a /Pages fa /Kids tömbjeinek mélységi, balról jobbra történő bejárásából adódik, sosem az objektumszámokból. Ez a cikk más szemszögből vizsgálja a fát: az alakját. Miért állítanak elő az érett PDF-írók köztes csomópontokból álló hierarchiákat, amikor egyetlen lapos tömb is teljesen szabályos lenne? Mi változik valójában, amikor egy eszköz lapítja vagy újraépíti a fát? És mi történik, amikor a /Count nyilvántartás, amely az egész szerkezetet gyorssá teszi, megszűnik igazat mondani
Az elágazás teljesítménydöntés
Semmi sem kényszeríti az írót beágyazásra. Egy 10 000 oldalas dokumentum, amelynek egyetlen gyökér /Pages csomópontja és 10 000 levélhivatkozása van egyetlen /Kids tömbben, megfelel a specifikációnak. A PDF Reference mégis kiegyensúlyozott fát javasol nagy dokumentumokhoz, és a mértékadó generátorok ezt a tanácsot mérsékelt elágazással követik, jellemzően néhány tucat gyermekkel köztes csomópontonként
Az ok abban rejlik, amit egy megjelenítőnek el kell olvasnia, mielőtt bármit is megjeleníthetne. Vegyük azt az esetet, amikor közvetlenül a 10 000 oldalas fájl 8214. oldalára ugrunk. Lapos fa esetén a megjelenítőnek először a gyökércsomópontot kell elemeznie, ez pedig egyetlen hatalmas tömb: hozzávetőleg nyolc bájt indirekt hivatkozásonként, egy 80 KB-os objektum, amelyet végig kell tokenizálni, mielőtt a 8213. bejegyzés feloldható lenne. Egy 32-es elágazású, kiegyensúlyozott fánál ugyanez az ugrás beolvassa a gyökeret, összehasonlítja a futó /Count összegeket a megfelelő gyermek kiválasztásához, majd lejjebb lép — összesen három vagy négy kis szótár, egyenként néhány száz bájt. Ez az O(log n) véletlen elérés, amelyre a fát tervezték, és pontosan emiatt létezik a /Count a köztes csomópontokon: lehetővé teszi, hogy az olvasó átugorjon egy egész részfát anélkül, hogy egyetlen benne lévő objektumot is megnyitna
A fa alakja a szerkesztés költségét is meghatározza. Egy inkrementális frissítés, amely beszúr egy oldalt, minden olyan csomópontot újra kell írjon, amelynek /Kids vagy /Count értéke megváltozott, vagyis az új levél szülőjétől a gyökérig vezető utat. Kiegyensúlyozott fában ez az út néhány kis szótár, amelyet a fájlhoz fűznek. Lapos fában az „út” maga az egyetlen óriási gyökértömb, amelyet minden revízió teljes egészében megkettőz. Egy szerződés, amely harminc felülvizsgálati és jegyzetelési ciklusán megy keresztül, végül harminc elavult másolatát cipelheti ugyanannak a 80 KB-os tömbnek a bájtfolyamában
A belső csomópontok örökölt attribútumokat hordoznak
A köztes csomópontok nem csupán az irányítást szolgálják. A négy örökölhető oldalattribútum — a /Resources, a /MediaBox, a /CropBox és a /Rotate — bármely /Pages csomópontra felhelyezhető, ahol minden alatta lévő levélre vonatkozik, hacsak egy leszármazott felül nem írja azokat. Egy fekvő tájolású függelékkel rendelkező jelentést előállító író magában a fában fejezheti ki ezt az elrendezést:
5 0 obj % dokumentum gyökere
<< /Type /Pages /Count 6 /Kids [6 0 R 7 0 R] >>
endobj
6 0 obj % jelentés törzse: álló A4, törzsbetűtípus
<< /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 % függelék: fekvő A4, elforgatva, saját betűtípus
<< /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 % függelék oldala: örökli a méretet, forgatást, betűtípusokat
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobjA 40–42. objektumok szinte üresek. Az oldalméretük, forgatásuk és betűtípus-erőforrásaik mind öröklés útján érkeznek a 7. csomóponttól, ami tömörré és önfenntartóvá teszi a fájlt: adjunk hozzá egy negyedik oldalt a függelék csomópontja alá, és az automatikusan fekvő tájolású lesz
Ugyanez a mechanizmus okozza a klasszikus oldalmozgatási veszélyt. Tegyük fel, hogy egy eszköz a 40. objektumot a jelentés törzsébe mozgatja a két /Kids tömb szerkesztésével és a /Parent átirányításával a 6. csomópontra. A mozgatás szerkezetileg érvényes, mégis a 40. objektum most az álló /MediaBox-ot, forgatás nélküli állapotot és az /F1 betűtípust örökli — miközben a tartalomfolyama továbbra is az /F2-t választja, amely már nem oldható fel. Az oldal egyetlen szerkesztéssel összezsugorodik, visszaforog, és elveszíti a szövegét. A robusztus átrendező kód ezért az összes négy örökölhető attribútum feloldott értékét rögzíti az oldal szótárában, mielőtt újra szülőt rendelne hozzá. Ha valaha is húzott már egy oldalt egy szerkesztőben, és látta, hogy megváltozik a mérete vagy a tájolása, akkor ezt a mechanizmust tapasztalta
Lapítás: szabályos, gyakori, néha költséges
Sok eszköz az ellenkező irányba megy. A minimalista írók egyszintű fát állítanak elő, mert ez egyszerű, és számos egyesítő és szétválasztó segédprogram bármilyen beolvasott fát egyetlen lapos /Kids tömbbé épít újra, mivel a kiegyensúlyozott szerkezet előállítása plusz munka, a lapos kimenet pedig mindig szabályos. A helyes újraépítésnek egyúttal fel kell oldania az öröklődést is: minden attribútumot, amelyet a levél örökölt, át kell másolni a levélre, vagy fel kell emelni az új gyökérbe, ha az egységes az egész dokumentumban — különben a kimenet pontosan úgy változtatja meg a geometriát, mint az oldalmozgatás esete
Tipikus dokumentumoknál a lapítás ártalmatlan. Nagy méretnél viszont árt, a már ismertetett két módon: a gyökértömb egyetlen nagy objektummá válik, amelyet minden megnyitásnak és minden oldalugrásnak teljesen elemeznie kell, és minden szerkezeti szerkesztés teljesen újraírja azt. Amit a lapítás nem tesz tönkre, az az indirekt hivatkozások általi megosztás — egy lapos fa, amelyben mind a 10 000 oldal ugyanarra a /Resources szótárobjektumra mutat, továbbra is deduplikált marad. Ami elvész, az csupán a lehetőség, hogy a bejegyzést kihagyjuk az oldalról, és hagyjuk, hogy egy ős szolgáltassa azt
Amikor a /Count hazudik
A /Count tiszta nyilvántartás: meg kell egyeznie a csomópont részfájában lévő levéloldalak számával, és a fájlformátumban semmi sem kényszeríti ki ezt. Két sérülési minta felel a valóságban látott hazug számlálók többségéért
Az első az inkrementális frissítés által hátrahagyott elavult számláló. Egy szerkesztő beszúr egy oldalt, új /Kids tömbbel és frissített /Count értékkel újraírja a közvetlen szülőt, mindkettőt hozzáfűzi a fájlhoz — és sosem nyúl az ősökhöz:
% Eredeti revízió
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
% Hozzáfűzött revízió: egy oldal beszúrva a középső ágba.
% A 14. objektum lecserélődött; a 12. objektumot sosem írják újra
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 4
/Kids [50 0 R 51 0 R 90 0 R 52 0 R] >>
endobjA fa most tíz levelet tartalmaz, de a gyökér még mindig kilencet mond. Az a megjelenítő, amely megbízik a gyökérben, kilenc oldalt jelent az oldalszámlálójában. Az, amelyik a belső számlálókat bináris kereséshez használja egy oldalugráshoz, minden, a beszúrási pont utáni oldalnál hibás indexet számít ki. Egy teljes bejárás tízet talál. Három különböző válasz, egyetlen fájl
A második minta az a számláló, amely sosem lehetne helyes: negatív, nulla egy feltöltött csomóponton, vagy abszurd módon hatalmas. Ezek fuzzingból, átviteli sérülésből, és időnként szerkesztők aritmetikai hibáiból erednek. Kifejezetten veszélyesek az olyan kódra, amely megbízik a /Count értékében az allokációhoz — egy tömb méretezése egy -3-as /Count alapján legjobb esetben tartományhibát vált ki, egy kétmilliárdos /Count alapján történő allokáció pedig szolgáltatásmegtagadási támadást okoz. Az érték megbízhatatlan bemenet, mint a fájl minden más száma
Az elemzők ebben a kérdésben két táborra oszlanak. A szigorú fogyasztók — preflight eszközök, PDF/A validátorok, archiválási folyamatok — összehasonlítják a /Count értéket a bejárás eredményével, és elutasítják vagy megjelölik a fájlt. Az interaktív megjelenítők szinte kivétel nélkül megengedők: bejárják a fát, levezetik a valódi számlálót, és csendben figyelmen kívül hagyják a tárolt értéket, ami pontosan az oka annak, hogy egy elavult számlálójú fájl évekig keringhet panasz nélkül, amíg egy szigorúbb elemzővel nem találkozik valamelyik automatizált munkafolyamatban. A könyvtári kód számára a védekező középút az, hogy a /Count értéket tippként kezeljük — hasznos az előzetes allokációhoz és a részfa átugrásához, miután ellenőrizték —, miközben a bejárás marad az igazság forrása
Magához a bejárási algoritmushoz, az öröklődés-keresési szabályokhoz és a katalógustól a levélig tartó bejáráshoz kezdje az oldalsorrend-magyarázóval. Hogy ezek a hibamódok hogyan néznek ki, amikor egy valódi ügyféldokumentum eléri a termelési kódot, olvassa el az oldalsorrend-hibakeresési esettanulmányt, amely egy összekevert oldalú incidenst követ végig a tünettől a kiváltó okig
A HotPDF Delphi Component mindezt belsőleg kezeli: bármilyen mélységű beágyazott fákat bejár, feloldja az örökölt attribútumokat oldalak másolásakor vagy mozgatásakor, és a tényleges levélszámok alapján ellenőrzi a /Count értéket ahelyett, hogy megbízna benne, így az API-jában szereplő oldalindexek mindig logikai oldalakat jelentenek