Artykuł techniczny

Drzewa nazw PDFlibPas: cykle, złe Limits i ogromne liście

Zbuduj PDF, którego drzewo nazw /Dests ma korzeń z dwoma dziećmi. Pierwsze dziecko deklaruje /Limits [(a) (z)], a jego tablica /Kids wskazuje wprost z powrotem na korzeń. Drugie dziecko trzyma prawdziwy wpis dla (chapter7), ale jego limity są zapisane na odwrót: [(z) (a)]. Zapytaj podręcznikowy lookup drzewa nazw o chapter7, a on albo rekursuje się, aż stack się skończy, albo zwraca „nie znaleziono” dla celu, do którego przeglądarka potrafi skoczyć. Cały plik mieści się w około dwóch kilobajtach i każdy obiekt w nim parsuje się czysto

Ten plik pakuje trzy osobne pułapki w jedną strukturę: cykl /Kids, zakres obiecujący klucz, którego nie trzyma, i zakres, który nie może niczego dopasować nigdy. Czwarta pułapka potrzebuje dużo większego pliku. Gdy pojedynczy liść niesie ponad 32 768 par nazwa/wartość, każdy kod, który wciśnie „który liść” i „który wpis” w jeden integer 32-bitowy, zaczyna wskazywać na złą parę. Reszta artykułu przechodzi przez każdą pułapkę, to, co czytelnik powinien z nią zrobić, i jak wywołania Delphi zachowują się na plikach zbudowanych tak jak tu

Cztery funkcje PDF, które siedzą na drzewach nazw i drzewach liczb

Drzewa nazw i drzewa liczb podpierają każdą funkcję PDF, która mapuje duży zbiór kluczy na obiekty, a PDFlibPas, biblioteka losLab PDF Library for Delphi, wystawia cztery z nich przez publiczne metody TPDFlib. ISO 32000-1 §7.9.6 definiuje drzewo nazw (klucze stringowe, Tabela 36), a §7.9.7 drzewo liczb (klucze integerowe, Tabela 37). Korzeń i węzły pośrednie niosą /Kids; liście niosą posortowane pary klucz/wartość w /Names albo /Nums; każdy węzeł nie-korzeń ma rzekomo nieść dwuelementową tablicę /Limits z najmniejszym i największym kluczem pod spodem

DrzewoGdzie mieszkaSpecyfikacjaAPI odczytu w PDFlibPas
Nazwane cele/Dests w słowniku nazw§12.3.2.3GetNamedDestination, potem GetDestPage / GetDestType
Etykiety stron/PageLabels w katalogu (drzewo liczb)§12.4.2GetPageLabel
Załączniki/EmbeddedFiles w słowniku nazw§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript na poziomie dokumentu/JavaScript w słowniku nazw§7.7.4GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dwa wiersze kryją haczyk. Nazwane cele istnieją też w starszej formie z PDF 1.1 — zwykły słownik /Dests w katalogu kluczowany obiektami nazw — a GetNamedDestination sprawdza najpierw ten słownik i dopiero potem schodzi po drzewie nazw z PDF 1.2. Wiersz JavaScript ma imiennika, który czyta coś zupełnie innego: GetDocJavaScript zwraca skrypty przypięte do wyzwalaczy dokumentu w słowniku /AA katalogu (WS, DS, WP, DP, DC), podczas gdy nazwane pakiety odpalane przy otwarciu dokumentu mieszkają w drzewie nazw /JavaScript i są wypisywane przez GlobalJavaScriptPackageName

Wszystkie te struktury pochodzą z pliku. Specyfikacja mówi piszącemu, co ma wyprodukować, a czytelnik i tak dostaje to, co koder, zepsuty zapis przyrostowy albo fuzzer faktycznie tam zostawili. To ta sama lekcja co hartowanie pascalowego parsera PDF przeciw złośliwym plikom, zastosowana do kształtu drzewa zamiast długości buforów

Dlaczego cykliczna tablica /Kids wywala rekurencyjnego obchodziacza drzewa?

Rekurencyjny obchodziacz wywala się na cyklicznej tablicy /Kids, bo nic w rekursji nie pamięta, które węzły już odwiedziła, więc jedna referencja dziecka na przodka zamienia skończony plik w bezkońcowy zstęp. Legalne drzewo potrafi narobić tych samych szkód bez żadnego cyklu: łańcuch 4096 poziomów węzłów z pojedynczym dzieckiem to poprawna składnia, która kosztuje rekurencyjnego czytelnika 4096 ramek stacka

Łagodniejszy wariant w ogóle nie wywala. Gdy dwa wpisy /Kids wskazują ten sam liść, naiwna enumeracja odwiedza go dwa razy, więc licznik załączników wraca wyższy niż liczba plików w dokumencie, a lista skryptów pokazuje ten sam pakiet podwójnie

PDFlibPas obchodzi oba rodzaje drzew jawnym stackiem LIFO na heapie plus zbiorem odwiedzonych kluczowanym tożsamością słownika. Węzeł jest znacznikowany w chwili zdjęcia ze stacka. Cykliczna referencja może posiedzieć na stacku chwilę, ale jest wyrzucana, jak tylko wraca na wierzch, a każdy odrębny węzeł rozwija swoje dzieci dokładnie raz. Cała praca jest ograniczona przez liczbę odrębnych słowników plus łączną długość ich tablic /Kids; łańcuch 4096 poziomów staje się 4096 iteracjami pętli i 4096 wpisami hash-setu

Przejście drzewa nazw w PDFlibPas: tablica Kids zapętlająca się z powrotem do korzenia przelewa stack rekurencyjnego obchodziacza, więc PDFlibPas używa jawnego stacka i zbioru odwiedzonych, który znacznikuje węzły przy zdjęciu, pcha dzieci od prawej do lewej i trzyma liście w kolejności z pliku dla GetPageLabel
Głębokość przestaje mieć znaczenie, gdy rekursja staje się pętlą: łańcuch 4096 poziomów to po prostu 4096 iteracji i 4096 wpisów hash setu

Kolejność to część, którą ludzie gubią przy zamianie rekursji w pętlę. Stack odwraca cokolwiek mu podasz, więc dzieci trzeba pchać od ostatniego indeksu do pierwszego; wtedy lewe dziecko zdjęte zostaje pierwsze, a liście wychodzą w kolejności od lewej do prawej, którą zapisał producent. Znacznikowanie przy zdjęciu zamiast przy pchnięciu ma znaczenie z tego samego powodu. Przy znacznikach na pchnięciu i pchnięciach od prawej do lewej liść wspólny dla pozycji 0 i 2 zostałby zapisany na pozycję 2, a jego wpisy pojawiłyby się później, niż mówi plik. Etykiety stron zależą od tej kolejności, jak pokazuje ostatnia sekcja

Jeśli piszesz własny kod drzewa przeciw innemu modelowi obiektów, to jest kształt, który rekomendujemy. Typ węzła poniżej jest celowo abstrakcyjny, a obie funkcje to kod po stronie czytelnika, nie wywołania biblioteki

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // pusta w liściu
    Keys: TArray<string>;      // klucze liścia, posortowane przez grzecznego producenta
    Values: TArray<Integer>;   // równoległe do Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// Twój własny helper: /Limits może przycinać tylko, gdy jest dobrze uformowaną, uporządkowaną parą
function LimitsExclude(Node: TTreeNode; const Key: string): Boolean;
begin
  Result := Node.HasLimits and (Node.LoKey <= Node.HiKey) and
    ((Key < Node.LoKey) or (Key > Node.HiKey));
end;

// Twój własny lookup: jawny stack, zbiór odwiedzonych, znacznik przy zdjęciu
function FindValue(Root: TTreeNode; const Key: string;
  out Value: Integer): Boolean;
var
  Pending: TList<TTreeNode>;
  Visited: TDictionary<TTreeNode, Byte>;
  Node: TTreeNode;
  I: Integer;
begin
  Result := False;
  Value := 0;
  if Root = nil then
    Exit;
  Pending := TList<TTreeNode>.Create;
  Visited := TDictionary<TTreeNode, Byte>.Create;
  try
    Pending.Add(Root);
    while Pending.Count > 0 do
    begin
      Node := Pending[Pending.Count - 1];
      Pending.Delete(Pending.Count - 1);
      if Visited.ContainsKey(Node) then
        Continue;                      // cykl albo wspólne dziecko: już widziane
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Pchaj od prawej do lewej, żeby lewe dziecko zdjęte było pierwsze
        for I := High(Node.Kids) downto 0 do
          if (Node.Kids[I] <> nil) and not LimitsExclude(Node.Kids[I], Key) then
            Pending.Add(Node.Kids[I]);
      end
      else
        for I := 0 to High(Node.Keys) do
          if (Node.Keys[I] = Key) and (I <= High(Node.Values)) then
          begin
            Value := Node.Values[I];
            Exit(True);
          end;
      // Pudło w tym liściu: dalej zdejmuje rodzeństwo
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Pudło w jednej gałęzi nie znaczy nic o drzewie

Najczęstszy skrót lookupa bierze pierwsze dziecko, którego /Limits pokrywa klucz, schodzi w nie i nigdy więcej nie patrzy na rodzeństwo. Na czystym drzewie to poprawne i szybkie. Na pliku z akapitu otwierającego pada: pierwsze dziecko obiecujące chapter7 prowadzi z powrotem do korzenia, a szukanie kończy z pustymi rękami, podczas gdy następne rodzeństwo trzyma wpis

PDFlibPas nie staje przy pierwszej wiarygodnej gałęzi. Keyed lookup za GetNamedDestination pcha każde dziecko, którego zakres nie wyklucza klucza, i zdejmuje dalej ze stacka, aż znajdzie dopasowanie albo stack się opróżni. Na dobrze uformowanym drzewie z rozłącznymi zakresami co najwyżej jedno dziecko przeżywa kontrolę zakresu na każdym poziomie, więc dodatkowy koszt to zero. Na uszkodzonym to garść dodatkowych odwiedzin węzłów, a odpowiedź wraca właściwa

Liście dostają to samo traktowanie. ISO 32000-1 wymaga, by klucze w tablicy /Names były posortowane po wartości bajtów, więc biblioteka próbuje najpierw wyszukiwania binarnego. Gdy ono pudłuje, spada na liniowe przemiatanie par, bo liść w złej kolejności uczyniłby obecnym klucz niewidzialnym. Płacenie za przemiatanie liniowe przy każdym prawdziwym pudle to koszt, który akceptujemy: lookupy po nazwach naprawdę nieobecnych są rzadkie, a fałszywe „nie znaleziono” na działającym łączu kosztuje daleko więcej niż jeden dodatkowy przebieg po liściu

Jedną sprzeczność strukturalną załatwia odmowa. Tabela 36 pozwala węzłowi nieść albo /Kids, albo /Names, nigdy oba. Keyed lookup traktuje węzeł niosący oba jako zniekształcony i go pomija, zamiast zgadywać, którą połowę producent miał na myśli. Enumeracja drzew liczb, jak obchód za GetPageLabel, jest łagodniejsza i przy obecności oba idzie za /Kids, bo zrzucenie całego zakresu błędnie oetykietowałoby każdą stronę po nim

Do czego czytelnik może ufać /Limits?

Czytelnik może ufać /Limits do pomijania pracy i tylko, gdy para jest dobrze uformowana; nigdy nie może użyć wpisu do wniosku, że klucz jest nieobecny. Tabela 36 mówi, że węzły pośrednie i liście mają go nieść, ale w praktyce wpis znika po ręcznych edycjach, trzyma liczby wewnątrz drzewa nazw albo przychodzi z zamienionymi granicami. PDFlibPas rozwiązuje każdy z tych przypadków tak samo: dziecko pozostaje przeszukiwalne

  • Brakujące /Limits: kontrola zakresu pomijająca takie dziecko czyniłaby całe jego poddrzewo nieosiągalnym, gdy tylko producent zapomni wpisu, więc dziecko jest przeszukiwane
  • Zły typ albo zła długość, jak liczby w drzewie nazw albo tablica jednoelementowa: obsługiwane dokładnie jak brakujący wpis
  • Odwrócone granice jak [(Z) (A)] albo [9 0]: żaden klucz nie spełnia Lo <= Key <= Hi przy Lo > Hi, więc ufaj tej parze a wykluczysz gałąź dla każdego lookupa; zakres przycina tylko, gdy jego dolna granica nie przekracza górnej
  • Dobrze uformowana i uporządkowana: używana do pomijania gałęzi — po to wpis istnieje
Reguły PDFlibPas dla ufania tablicy Limits drzewa nazw: para brakująca, złego typu albo odwrócona zostawia dziecko przeszukiwalne, a tylko dobrze uformowana, uporządkowana para może przyciąć gałąź, więc wrogi Limits może kosztować odwiedziny, ale nie może ukryć istniejącego celu
Zakresy mogą pomijać pracę, ale nigdy nie rozstrzygają nieobecności, bo o wyniku każdego lookupa rozstrzygają prawdziwe klucze zapisane w liściach

Ze strony wołającego są dwa zera do rozróżnienia. GetNamedDestination zwraca 0, gdy nazwy naprawdę nie ma, a inaczej ID celu. GetDestPage zwracające 0 przy ważnym ID znaczy, że nazwa istnieje, ale jej cel nie rozwiązuje się do strony w tym dokumencie — to inne zgłoszenie błędu. GetDestType donosi widok jako 1 dla XYZ, 2 dla Fit i tak dalej po 8 dla FitBV

uses
  PDFlibrary;

procedure LookUpDestination(const FileName, DestName: string);
var
  Lib: TPDFlib;
  DestID, Page: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
    begin
      WriteLn('Load failed, error ', Lib.LastErrorCode);
      Exit;
    end;
    // Najpierw katalogowy /Dests (PDF 1.1), potem drzewo nazw /Dests
    DestID := Lib.GetNamedDestination(DestName);
    if DestID = 0 then
    begin
      WriteLn('No destination named ', DestName);
      Exit;
    end;
    Page := Lib.GetDestPage(DestID);
    if Page = 0 then
      WriteLn(DestName, ' exists but does not resolve to a page')
    else
      WriteLn(DestName, ' -> page ', Page,
        ', view type ', Lib.GetDestType(DestID));  // 1 = XYZ, 2 = Fit ...
  finally
    Lib.Free;
  end;
end;

To składa się w zwarty test regresyjny. Zbuduj plik z dwoma dziećmi z akapitu otwierającego, skieruj prawdziwy wpis chapter7 na stronę 2 z widokiem /Fit, a procedura powinna wydrukować stronę 2 z typem widoku 2. Lookup pierwszego dopasowania wydrukuje „No destination”, bo zapętlone dziecko wygrywa wyścig; lookup ufający odwróconym zakresom wydrukuje to samo z odwrotnego powodu. Gdy cele się rozwiązują, wpisy konspektu wskazujące na nie są omówione w czytaniu akcji zakładek i adnotacji PDF w Delphi

Liście ponad 32 768 wpisów i pułapka pakowanego indeksu

Gdy kod potrzebuje jednego integerowego uchwytu dla „wpis N w liściu M”, kuszące kodowanie pakuje pozycję liścia w górne 16 bitów Integer, a offset wewnątrz tablicy /Names tego liścia w dolne 16 bitów. Każda para bierze dwa sloty tablicy. Para o indeksie 32 768 — trzydziesta dwie tysiące siedemdziesiąta dziewiąta — zaczyna więc na offsecie 65 536, czyli $10000. Ten bit przenosi się do górnej połowy, a dekoder czyta go z powrotem jako offset 0 następnego liścia

Pakowany indeks drzewa nazw, gdzie pozycja liścia i offset wpisu dzielą jeden 32-bitowy Integer, a para 32768 startuje na offsecie 65536, więc carry do górnej połowy czyta się jako offset 0 następnego liścia i find albo delete dotyka złej pary, podczas gdy osobne skanowanie kluczy się nie zgadza
Dwie wartości 16-bitowe w jednym integerze 32-bitowym obcinają się po cichu w chwili, gdy liść przekroczy 32 768 par — rozmiar, jaki realne podręczniki referencyjne osiągają

Objawy zależą od kształtu drzewa. Przy pojedynczym liściu nie ma następnego liścia, więc zdekodowany uchwyt indeksuje za koniec listy liści. Przy kilku liściach find albo delete ląduje na pierwszej parze następnego liścia, podczas gdy gołe skanowanie kluczy nadal donosi żądany klucz jako obecny. Pliki tego rozmiaru nie są egzotyczne. Generowana referencja API z jednym nazwanym celem na symbol przekracza 32 768 wpisów szybko, a niektórzy producenci zapisują wszystkie do jednego płaskiego liścia zamiast balansować drzewo

PDFlibPas trzyma pozycję liścia i offset wpisu w dwóch integerach pełnej szerokości, więc żadne nie może się przelewać do drugiego przy jakimkolwiek rozmiarze liścia. Ten sam czytelnik liczy wyłącznie prawdziwe klucze stringowe. Dla liścia takiego jak [(Valid) 42 123 456] EmbeddedFileCount donosi 1, klucz numeryczny 123 nigdy nie zostaje wzięty za pustą nazwę, a indeks 0 albo niższy zwraca pusty string z GetEmbeddedFileStrProperty zamiast cokolwiek obiektu, który akurat idzie dalej. Tag 1 tej funkcji to nazwa pliku, a tag 2 podtyp MIME

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // drzewo liczb /PageLabels; pliki bez niego zwracają gołe numery stron
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // drzewo nazw /EmbeddedFiles; indeksy od 1, klucze nie-stringowe pomijane
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nazwa, podtyp MIME
    // drzewo nazw /JavaScript: wypisz nazwy pakietów, nic nie wykonuj
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Testowy plik dwustronicowy pokazuje oczekiwane wyjście dobrze. Daj jego korzeniowi /PageLabels tablicę /Kids, która wypisuje jeden liść dwa razy i wskazuje też sam korzeń, z zakresami dla małych rzymskich od strony 1 i dziesiętnych z prefiksem A- od strony 2. Audyt powinien wydrukować i i A-1, każdy zakres nałożony raz. Zapisywanie etykiet stron do takiego drzewa ma własne haczyki, omówione w naprawianiu etykiet stron PDF przechowanych w drzewach liczb /Kids; AddPageLabels spłaszcza korzeń /Kids do pojedynczego liścia /Nums przed wstawieniem, używając tej samej enumeracji bezpiecznej wobec cykli

Gdzie przejście wytycza swoje granice

Przejście gwarantuje zakończenie, stabilną kolejność i poprawne odpowiedzi dla każdego drzewa, którego prawdziwe klucze są nietknięte. Czyta uszkodzone drzewo tak, jak zapisano, i nie próbuje rekonstruować intencji autora, a z tego wyboru płynie pięć konsekwencji

  • Tożsamość, nie treść, definiuje węzeł. Dwa odrębne słowniki o identycznych wpisach to dwa węzły, więc producent kopiujący liść zamiast go referencjonować dostaje te wpisy dwa razy
  • Dobrze uformowana, uporządkowana para /Limits przycina nawet, gdy jest zła. Zakres kłamiący wiarygodnie, powiedzmy [(a) (m)] nad liściem, który trzyma też (q), ukrywa q. Jedyną obroną byłoby ignorowanie /Limits wszędzie i przemiatanie każdego liścia, a na drzewie celów z dziesiątkami tysięcy wpisów to wyrzuca powód istnienia wpisu. Przycinamy dalej
  • Enumeracja zachowuje kolejność z pliku. GetPageLabel obchodzi każdy enumerowany zakres i nakłada ostatni, którego indeks startowy jest na poziomie strony albo poniżej, więc producent zapisujący zakresy w złej kolejności dostaje semantykę kolejności z pliku, a odwrócenie obchodu wręczyłoby stronie 200 styl przedmowy
  • Pamięć rośnie z liczbą odrębnych węzłów i wpisów. Przejście dokłada jedną listę i jeden hash set ponad sparsowane obiekty
  • Zdublowane klucze wewnątrz jednego liścia rozwiązują się deterministycznie: wyszukiwanie binarne zwraca tę pasującą parę, na którą najpierw trafi, a liniowy fallback zatrzymuje ostatnie dopasowanie, które przemiatą

Narzędzia preflight, archiwizery i przeglądarki dokumentów czytają te drzewa, zanim zostanie wyrenderowana choć jedna strona, co stawia je pierwsze w kolejce na cokolwiek przyjdzie z uploadu. Czytniki drzew opisane tu są dostarczane z PDFlibPas, biblioteką PDF Library for Delphi, która buduje i z Delphi, i z Free Pascal