Tvar stromu stránek PDF: Rozvětvení, zploštění a integrita /Count

Náš doprovodný vysvětlující článek o uspořádání stránek PDF pokrývá základní pravidlo: pořadí zobrazení pochází z průchodu stromem /Pages přes pole /Kids do hloubky zleva doprava, nikdy z čísel objektů. Tento článek se dívá na strom z jiného úhlu — na jeho tvar. Proč vyspělé zapisovače PDF produkují hierarchie mezilehlých uzlů, když by jedno ploché pole bylo naprosto legální? Co se ve skutečnosti změní, když nástroj strom zploští nebo přestaví? A co se stane, když účetnictví /Count, které celou strukturu zrychluje, přestane říkat pravdu

Rozvětvení je rozhodnutí o výkonu

Nic nenutí zapisovač vnořovat. 10 000stránkový dokument s jedním kořenovým uzlem /Pages a 10 000 odkazy na listy v jediném poli /Kids vyhovuje specifikaci. Referenční příručka PDF přesto doporučuje vyvážený strom pro velké dokumenty a mainstreamové generátory se této rady drží se skromným rozvětvením, obvykle několik desítek potomků na mezilehlý uzel

Důvodem je to, co musí prohlížeč přečíst, než může cokoliv ukázat. Zvažte skok přímo na stranu 8 214 tohoto 10 000stránkového souboru. S plochým stromem musí prohlížeč nejprve analyzovat kořenový uzel, a tento kořenový uzel je jedno obrovské pole: při zhruba osmi bajtech na nepřímý odkaz jde o objekt o velikosti 80 KB, který musí být od konce ke konci tokenizován, než může být vyřešen záznam 8 213. S vyváženým stromem o rozvětvení 32 přečte stejný skok kořen, porovná průběžné součty /Count, aby vybral správného potomka, a sestoupí — celkově tři nebo čtyři malé slovníky, každý o několika stovkách bajtů. To je náhodný přístup O(log n), který měl strom poskytovat, a je to jediný důvod, proč existuje /Count na mezilehlých uzlech: umožňuje čtečce přeskočit celý podstrom bez otevření jediného objektu uvnitř něj

Tvar stromu také určuje náklady na editaci. Inkrementální aktualizace, která vloží jednu stránku, musí přepsat každý uzel, jehož /Kids nebo /Count se změnil, což znamená cestu od rodiče nového listu nahoru ke kořeni. Ve vyváženém stromu je tato cesta hrstkou malých slovníků připojených k souboru. V plochém stromu je "cestou" jediné gigantické kořenové pole, duplikované v plném rozsahu při každé revizi. Smlouva, která projde třiceti cykly kontroly a anotací, může nakonec v proudu bajtů táhnout třicet nahrazených kopií stejného pole o velikosti 80 KB

Vnitřní uzly nesou zděděné atributy

Mezilehlé uzly neslouží jen ke směrování. Čtyři dědičné atributy stránky — /Resources, /MediaBox, /CropBox a /Rotate — mohou být vytaženy na jakýkoliv uzel /Pages, kde se uplatní na každý list pod ním, pokud je potomek nepřepíše. Zapisovač produkující zprávu s přílohou na šířku může vyjádřit toto rozložení v samotném stromu:

5 0 obj   % kořen dokumentu
<< /Type /Pages /Count 6 /Kids [6 0 R  7 0 R] >>
endobj

6 0 obj   % tělo zprávy: A4 na výšku, tělový 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   % příloha: A4 na šířku, otočeno, vlastní 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  % strana přílohy: dědí velikost, otočení, fonty
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

Objekty 40 až 42 jsou téměř prázdné. Jejich velikost stránky, otočení a prostředky písem, to vše přichází dědičností z uzlu 7, což udržuje soubor kompaktní a samoúdržbový: přidejte čtvrtou stranu pod uzel přílohy a automaticky vyjde na šířku

Stejný mechanismus vytváří klasické riziko při přesunu stránek. Předpokládejme, že nástroj přesune objekt 40 do těla zprávy úpravou dvou polí /Kids a přesměrováním /Parent na uzel 6. Přesun je strukturálně platný, ale objekt 40 teď zdědí /MediaBox na výšku, žádné otočení a font /F1 — zatímco jeho proud obsahu stále vybírá /F2, který se už nedaří vyřešit. Stránka se zmenší, odrotuje a ztratí text v jediné úpravě. Robustní kód pro změnu pořadí proto před změnou rodiče materializuje vyřešené hodnoty všech čtyř dědičných atributů do slovníku stránky. Pokud jste někdy v editoru táhli stránku a sledovali, jak mění velikost nebo orientaci, byli jste svědky tohoto mechanismu

Zploštění: legální, běžné, občas drahé

Spousta nástrojů jde opačným směrem. Minimalistické zapisovače produkují jednoúrovňový strom, protože je jednoduchý, a mnohé nástroje na slučování a rozdělování přestaví jakýkoliv strom, který přečtou, do jednoho plochého pole /Kids, protože generování vyvážené struktury je práce navíc a plochý výstup je vždy vyhovující. Správná přestavba musí zároveň vyřešit dědičnost: každý atribut, který list dědil, musí být do něj zkopírován, nebo vytažen do nového kořene, pokud je jednotný v celém dokumentu — jinak výstup změní geometrii přesně tak jako v případě přesunu stránek

Pro typické dokumenty je zploštění neškodné. Bolí to v měřítku, oběma už popsanými způsoby: kořenové pole se stane jedním velkým objektem, který musí být v plném rozsahu analyzován při každém otevření a každém skoku na stránku, a každá strukturální úprava jej přepíše celý. Co zploštění nezničí, je sdílení prostřednictvím nepřímých odkazů — plochý strom, ve kterém všech 10 000 stránek odkazuje na stejný objekt slovníku /Resources, je stále deduplikován. Ztrácí se pouze možnost vynechat záznam na stránce a nechat jej dodat předkem

Když /Count lže

/Count je čisté účetnictví: musí se rovnat počtu listových stránek v podstromu uzlu a formát souboru toto nijak nevynucuje. Dva vzorce poškození jsou příčinou většiny lživých počtů pozorovaných v praxi

Prvním je neaktuální počet zanechaný inkrementální aktualizací. Editor vloží stránku, přepíše bezprostředního rodiče s novým /Kids a aktualizovaným /Count, připojí oba k souboru — a nikdy se nedotkne předků:

% Původní revize
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

% Připojená revize: jedna strana vložena do prostřední větve.
% Objekt 14 je nahrazen; objekt 12 není nikdy přepsán
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

Strom má teď deset listů, ale kořen stále říká devět. Prohlížeč, který důvěřuje kořeni, ohlásí ve svém počítadle stránek devět stran. Ten, který používá vnitřní počty k binárnímu vyhledávání pro skok na stránku, spočítá po bodu vložení špatný index u každé stránky. Úplný průchod jich najde deset. Tři různé odpovědi, jeden soubor

Druhý vzorec je počet, který by nikdy nemohl být správný: záporný, nulový na obydleném uzlu, nebo absurdně velký. Ty pocházejí z fuzzingu, z poškození při přenosu a občas z aritmetických chyb v editorech. Jsou nebezpečné zejména pro kód, který důvěřuje /Count pro alokaci — dimenzování pole podle /Count s hodnotou -3 vyvolá v lepším případě chybu rozsahu, a učinit totéž z /Count ve výši dvou miliard je alokace ve stylu odepření služby (denial-of-service). Hodnota je nedůvěryhodný vstup, jako každé jiné číslo v souboru

Analyzátory se kvůli tomu dělí na dva tábory. Striktní konzumenti — nástroje pro předtiskovou přípravu, validátory PDF/A, archivační pipelines — porovnávají /Count oproti výsledku průchodu a soubor odmítnou nebo označí. Interaktivní prohlížeče jsou téměř plošně tolerantní: projdou, odvodí skutečný počet a tiše ignorují ten uložený, což je přesně důvod, proč může soubor s neaktuálním počtem léta bez stížností cirkulovat, dokud nenarazí na striktnější analyzátor v nějakém automatizovaném pracovním postupu. Defenzivní střední cestou pro kód knihoven je považovat /Count za nápovědu — užitečnou pro předběžnou alokaci a pro přeskočení podstromu po ověření — zatímco nechat průchod, aby zůstal zdrojem pravdy

Co se týče samotného algoritmu průchodu, pravidel vyhledávání dědičnosti a procházení od katalogu k listu, začněte s vysvětlením uspořádání stránek. Chcete-li zjistit, jak tyto režimy selhání vypadají, když se reálný dokument zákazníka dostane do produkčního kódu, přečtěte si případovou studii ladění pořadí stránek, která sleduje incident zamíchaných stránek od symptomu až k základní příčině

Komponenta HotPDF to všechno řeší interně: prochází vnořené stromy jakékoliv hloubky, řeší zděděné atributy, když jsou stránky kopírovány nebo přesouvány, a ověřuje /Count proti skutečným počtům listů namísto toho, aby jim důvěřovala, takže indexy stránek v jejím API vždy znamenají logické stránky