Kształt drzewa stron PDF: rozgałęzianie, spłaszczanie i integralność /Count

Nasz towarzyszący artykuł o kolejności stron PDF omawia podstawową zasadę: kolejność wyświetlania wynika z przechodzenia w głąb, od lewej do prawej, po tablicach /Kids w drzewie /Pages, nigdy z numerów obiektów. Ten artykuł patrzy na drzewo z innej strony — na jego kształt. Dlaczego dojrzałe generatory PDF tworzą hierarchie węzłów pośrednich, skoro pojedyncza płaska tablica byłaby całkowicie zgodna ze specyfikacją? Co właściwie się zmienia, gdy narzędzie spłaszcza lub odbudowuje drzewo? I co się dzieje, gdy księgowanie /Count, które sprawia, że cała struktura jest szybka, przestaje mówić prawdę

Rozgałęzianie to decyzja wydajnościowa

Nic nie zmusza generatora do zagnieżdżania. Dokument o 10 000 stron z jednym korzeniowym węzłem /Pages i 10 000 odwołaniami do liści w pojedynczej tablicy /Kids jest zgodny ze specyfikacją. PDF Reference mimo to zaleca zrównoważone drzewo dla dużych dokumentów, a główne generatory stosują się do tej rady z umiarkowanym rozgałęzieniem, zwykle po kilkadziesiąt dzieci na węzeł pośredni

Powodem jest to, co przeglądarka musi przeczytać, zanim cokolwiek pokaże. Rozważ przeskok wprost do strony 8214 tego pliku o 10 000 stron. Przy płaskim drzewie przeglądarka musi najpierw sparsować węzeł korzeniowy, a ten węzeł korzeniowy to jedna ogromna tablica: przy około ośmiu bajtach na odwołanie pośrednie jest to obiekt o rozmiarze 80 KB, który trzeba stokenizować od początku do końca, zanim wpis 8213 może zostać rozwiązany. Przy zrównoważonym drzewie o rozgałęzieniu 32 ten sam przeskok czyta korzeń, porównuje bieżące sumy /Count, aby wybrać właściwe dziecko, i schodzi w dół — łącznie trzy lub cztery małe słowniki, każdy po kilkaset bajtów. To jest dostęp swobodny o złożoności O(log n), do zapewnienia którego drzewo zostało zaprojektowane, i jest to cały powód, dla którego /Count istnieje w węzłach pośrednich: pozwala czytnikowi pominąć całe poddrzewo bez otwierania ani jednego obiektu wewnątrz niego

Kształt drzewa wyznacza również koszt edycji. Aktualizacja przyrostowa, która wstawia jedną stronę, musi przepisać każdy węzeł, którego /Kids lub /Count uległy zmianie, co oznacza ścieżkę od rodzica nowego liścia w górę do korzenia. W zrównoważonym drzewie ta ścieżka to garstka małych słowników dołączonych do pliku. W płaskim drzewie „ścieżka” to pojedyncza gigantyczna tablica korzeniowa, powielana w całości przy każdej rewizji. Umowa, która przechodzi przez trzydzieści cykli recenzji i adnotacji, może w efekcie ciągnąć w swoim strumieniu bajtów trzydzieści zastąpionych kopii tej samej tablicy o rozmiarze 80 KB

Węzły wewnętrzne przenoszą atrybuty dziedziczone

Węzły pośrednie nie służą tylko do trasowania. Cztery dziedziczne atrybuty strony — /Resources, /MediaBox, /CropBox i /Rotate — mogą zostać wyniesione do dowolnego węzła /Pages, gdzie odnoszą się do każdego liścia pod nim, chyba że potomek je nadpisze. Generator tworzący raport z załącznikiem w orientacji poziomej może wyrazić ten układ w samym drzewie:

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

Obiekty od 40 do 42 są niemal puste. Ich rozmiar strony, obrót i zasoby czcionek docierają w drodze dziedziczenia z węzła 7, co utrzymuje plik zwarty i samoutrzymujący się: dodaj czwartą stronę pod węzłem załącznika, a wyjdzie ona automatycznie w orientacji poziomej

Ten sam mechanizm tworzy klasyczne zagrożenie przy przenoszeniu stron. Załóżmy, że narzędzie przenosi obiekt 40 do treści raportu, edytując dwie tablice /Kids i przekierowując /Parent na węzeł 6. Przeniesienie jest strukturalnie poprawne, a jednak obiekt 40 dziedziczy teraz pionowy /MediaBox, brak obrotu i czcionkę /F1 — podczas gdy jego strumień treści nadal wybiera /F2, która już się nie rozwiązuje. Strona kurczy się, przestaje być obrócona i traci swój tekst w jednej edycji. Solidny kod zmieniający kolejność materializuje więc rozwiązane wartości wszystkich czterech dziedzicznych atrybutów na słowniku strony przed zmianą jej rodzica. Jeśli kiedykolwiek przeciągnąłeś stronę w edytorze i patrzyłeś, jak zmienia rozmiar lub orientację, to właśnie ten mechanizm widziałeś

Spłaszczanie: legalne, powszechne, czasem kosztowne

Mnóstwo narzędzi działa w drugą stronę. Minimalistyczne generatory tworzą drzewo jednopoziomowe, bo to proste, a wiele narzędzi do łączenia i dzielenia przebudowuje dowolne odczytane drzewo w jedną płaską tablicę /Kids, ponieważ generowanie zrównoważonej struktury to dodatkowa praca, a płaskie wyjście jest zawsze zgodne. Poprawna przebudowa musi jednocześnie rozwiązać dziedziczenie: każdy atrybut, który liść dziedziczył, trzeba skopiować na liść albo wynieść do nowego korzenia, jeśli jest jednolity w całym dokumencie — w przeciwnym razie wyjście zmienia geometrię dokładnie tak, jak w przypadku przenoszenia strony

Dla typowych dokumentów spłaszczanie jest nieszkodliwe. Szkodzi przy skali, na dwa już opisane sposoby: tablica korzeniowa staje się jednym dużym obiektem, który każde otwarcie i każdy przeskok strony muszą sparsować w całości, a każda edycja strukturalna przepisuje ją w całości. Czego spłaszczanie nie niszczy, to współdzielenie przez odwołania pośrednie — płaskie drzewo, w którym wszystkie 10 000 stron wskazuje ten sam obiekt słownika /Resources, wciąż jest zdeduplikowane. Traci się jedynie opcję pominięcia wpisu na stronie i pozostawienia go przodkowi do dostarczenia

Gdy /Count kłamie

/Count to czyste księgowanie: musi być równe liczbie stron-liści w poddrzewie węzła, a nic w formacie pliku tego nie wymusza. Dwa wzorce uszkodzeń odpowiadają za większość kłamliwych liczników spotykanych w praktyce

Pierwszy to nieaktualny licznik pozostawiony przez aktualizację przyrostową. Edytor wstawia stronę, przepisuje bezpośredniego rodzica z nowym /Kids i zaktualizowanym /Count, dołącza oba do pliku — i nigdy nie tyka przodków:

% 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

Drzewo trzyma teraz dziesięć liści, ale korzeń nadal mówi dziewięć. Przeglądarka, która ufa korzeniowi, raportuje w swoim liczniku stron dziewięć stron. Ta, która używa liczników wewnętrznych do wyszukiwania binarnego przeskoku strony, oblicza błędny indeks dla każdej strony po punkcie wstawienia. Pełne przejście znajduje dziesięć. Trzy różne odpowiedzi, jeden plik

Drugi wzorzec to licznik, który nigdy nie mógł być poprawny: ujemny, zerowy na zapełnionym węźle albo absurdalnie wielki. Biorą się one z fuzzingu, z uszkodzeń transmisji, a czasem z błędów arytmetycznych w edytorach. Są niebezpieczne szczególnie dla kodu, który ufa /Count przy alokacji — wymiarowanie tablicy na podstawie /Count równego -3 w najlepszym razie zgłasza błąd zakresu, a zrobienie tego przy /Count równym dwa miliardy to alokacja typu odmowa usługi. Ta wartość to niezaufane wejście, jak każda inna liczba w pliku

Parsery dzielą się na dwa obozy w tej całej sprawie. Ścisłe konsumenty — narzędzia preflight, walidatory PDF/A, potoki archiwalne — porównują /Count z wynikiem przejścia i odrzucają lub oznaczają plik. Interaktywne przeglądarki są niemal powszechnie pobłażliwe: przechodzą drzewo, wyprowadzają rzeczywistą liczbę i po cichu ignorują tę zapisaną, co jest dokładnie powodem, dla którego plik z nieaktualnym licznikiem może krążyć latami bez skargi, aż spotka bardziej rygorystyczny parser wewnątrz jakiegoś zautomatyzowanego przepływu pracy. Defensywny złoty środek dla kodu bibliotecznego to traktowanie /Count jako wskazówki — przydatnej do prealokacji i do pomijania poddrzew po zweryfikowaniu — pozostawiając przejście drzewa jako źródło prawdy

Po sam algorytm przechodzenia, reguły wyszukiwania dziedziczenia oraz przejście od katalogu do liścia, zacznij od artykułu o kolejności stron. Aby zobaczyć, jak te tryby awarii wyglądają, gdy prawdziwy dokument klienta trafia do kodu produkcyjnego, przeczytaj studium przypadku debugowania kolejności stron, które śledzi incydent z pomieszanymi stronami od objawu do przyczyny źródłowej

HotPDF Component radzi sobie z tym wszystkim wewnętrznie: przechodzi zagnieżdżone drzewa o dowolnej głębokości, rozwiązuje dziedziczone atrybuty, gdy strony są kopiowane lub przenoszone, i weryfikuje /Count względem rzeczywistej liczby liści zamiast mu ufać, więc indeksy stron w jego API zawsze oznaczają strony logiczne