Technisch artikel

PDFlibPas name trees: cycli, foute /Limits en reuze-leaves

Bouw een PDF waarvan de /Dests name tree een root met twee kinderen heeft. Het eerste kind declareert /Limits [(a) (z)] en zijn /Kids-array wijst rechtstreeks terug naar de root. Het tweede kind bevat de echte entry voor (chapter7), maar zijn limits staan er achterstevoren in: [(z) (a)]. Vraag een tekstboek-name-tree-lookup om chapter7 en hij recursert tot de stack opraakt of meldt "not found" voor een destination waar een viewer heen kan springen. Het hele bestand past in zo'n twee kilobyte, en elk object erin parst schoon

Dat bestand propt drie aparte valkuilen in één structuur: een /Kids-cyclus, een bereik dat een key claimt die hij niet bevat, en een bereik dat nooit iets kan matchen. Een vierde valkuil heeft een veel groter bestand nodig. Zodra één leaf meer dan 32.768 name/value-paren draagt, begint elke code die "welke leaf" en "welke entry" in één 32-bit integer perst naar het verkeerde paar te wijzen. De rest van dit artikel loopt elke valkuil langs, wat een reader ermee hoort te doen, en hoe de Delphi-aanroepen zich gedragen op bestanden die zo gebouwd zijn

Vier PDF-functies die op name trees en number trees rusten

Name trees en number trees dragen elke PDF-functie die een grote key-verzameling aan objecten koppelt, en PDFlibPas, de losLab PDF Library for Delphi, legt er vier bloot via publieke TPDFlib-methoden. ISO 32000-1 §7.9.6 definieert de name tree (string keys, Tabel 36) en §7.9.7 de number tree (integer keys, Tabel 37). Root en tussenliggende nodes dragen /Kids; leaves dragen gesorteerde key/value-paren in /Names of /Nums; elke niet-root-node hoort een /Limits-array van twee elementen te dragen met de kleinste en grootste key eronder

TreeWaar hij huistSpecificatiePDFlibPas lees-API
Named destinations/Dests in de name dictionary§12.3.2.3GetNamedDestination, daarna GetDestPage / GetDestType
Page labels/PageLabels in de catalog (number tree)§12.4.2GetPageLabel
Attachments/EmbeddedFiles in de name dictionary§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
Document-level JavaScript/JavaScript in de name dictionary§7.7.4GlobalJavaScriptCount, GlobalJavaScriptPackageName

Twee rijen verbergen een addertje. Named destinations bestaan ook in een oudere PDF 1.1-vorm, een kaal /Dests-dictionary in de catalog met name objects als keys, en GetNamedDestination controleert eerst dat dictionary en daalt pas daarna af in de PDF 1.2-name tree. De JavaScript-rij heeft een bijna-naamgenoot die iets heel anders leest: GetDocJavaScript geeft scripts terug die aan de documenttriggers in het /AA-dictionary van de catalog hangen (WS, DS, WP, DP, DC), terwijl de benoemde pakketten die bij het openen van een document draaien in de /JavaScript-name tree wonen en door GlobalJavaScriptPackageName worden opgelijst

Al deze structuren komen uit het bestand. De specificatie zegt een schrijver wat hij hoort te produceren, en een reader krijgt toch wat de schrijver, een kapotte incrementele save of een fuzzer er werkelijk in heeft gezet. Dat is dezelfde les als een Pascal-PDF-parser verharden tegen kwaadwillende bestanden, toegepast op boomvorm in plaats van bufferlengtes

Waarom crasht een cyclische /Kids-array een recursieve tree walker?

Een recursieve walker crasht op een cyclische /Kids-array omdat niets in de recursie onthoudt welke nodes al zijn betreden, dus één kinderreferentie naar een voorouder maakt van een eindig bestand een eindeloze afdaling. Een legitieme boom kan dezelfde schade aanrichten zonder enige cyclus: een keten van 4.096 een-kind-nodes diep is geldige syntax die een recursieve reader 4.096 stackframes kost

De mildere variant crasht helemaal niet. Als twee /Kids-entries naar dezelfde leaf wijzen, bezoekt een naïeve enumeratie hem twee keer, dus een attachmenttelling komt hoger terug dan het aantal bestanden in het document en een scriptlijst toont hetzelfde pakket dubbel

PDFlibPas doorloopt beide soorten bomen met een expliciete last-in, first-out-stack op de heap plus een visited set met dictionary-identiteit als key. Een node wordt gemarkeerd zodra hij wordt gepopt. Een cyclische referentie mag even op de stack staan, maar wordt weggegooid zodra hij terugkomt, en elke unieke node vouwt zijn kinderen exact één keer uit. Het totale werk is begrensd door het aantal unieke dictionaries plus de gecombineerde lengte van hun /Kids-arrays; een keten van 4.096 niveaus wordt 4.096 loop-iteraties en 4.096 hash-set-entries

PDFlibPas name tree-traversal waarbij een Kid-array die terugluccht naar de root een recursieve walker doodde met een stack overflow, vervangen sinds v3.539.45 door een expliciete stack en een visited set die nodes markeert bij het poppen, kinderen van rechts naar links pusht en leaves in bestandsvolgorde houdt voor GetPageLabel
Diepte stopt met tellen zodra recursie een lus wordt: een keten van 4.096 niveaus is gewoon 4.096 iteraties en 4.096 hash set-entries

Volgorde is het deel waar mensen het mishebben als ze recursie naar een loop omzetten. Een stack keert om wat je hem voert, dus kinderen moeten van de laatste index naar de eerste worden gepusht; dan popt het linkerkind eerst en komen de leaves in de links-naar-rechts-volgorde tevoorschijn die de producent schreef. Markeren bij pop in plaats van bij push telt om dezelfde reden. Met markeringen bij push en pushes van rechts naar links zou een leaf die op posities 0 en 2 wordt gedeeld door positie 2 worden geclaimd, en zouden zijn entries later verschijnen dan het bestand zegt. Page labels hangen van die volgorde af, zoals de laatste sectie laat zien

Schrijf je zelf boomcode tegen een ander objectmodel, dan is dit de vorm die we aanbevelen. Het nodetype hieronder is met opzet abstract, en beide functies zijn lezerkant-code, geen library-aanroepen

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // leeg op een leaf
    Keys: TArray<string>;      // leaf-keys, gesorteerd door een producent die het netjes doet
    Values: TArray<Integer>;   // parallel aan Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// Eigen helper: /Limits mag alleen snoeien als het een goed gevormd, geordend paar is
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;

// Eigen lookup: expliciete stack, visited set, markeren bij pop
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;                      // cyclus of gedeeld kind: al gezien
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Push van rechts naar links zodat het linkerkind eerst popt
        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;
      // Een misser in deze leaf: blijf zijn siblings poppen
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Een misser in één tak zegt niets over de boom

De meest voorkomende lookup-snelkoppeling pakt het eerste kind waarvan /Limits de key dekt, daalt erin af en kijkt nooit meer naar een sibling. Op een schone boom is dat correct en snel. Op het bestand uit de openingsalinea faalt het: het eerste kind claimt chapter7, leidt terug naar de root, en de zoektocht eindigt met lege handen terwijl de volgende sibling de entry vasthoudt

PDFlibPas stopt niet bij de eerste plausibele tak. De keyed lookup achter GetNamedDestination pusht elk kind waarvan het bereik de key niet uitsluit, en blijft poppen tot hij een match vindt of de stack leeg is. Op een goed gevormde boom met disjuncte bereiken overleeft per niveau hooguit één kind de bereikcontrole, dus de extra kosten zijn nihil. Op een beschadigde boom zijn het een handvol extra nodebezoeken, en het antwoord komt correct terug

Leaves krijgen dezelfde behandeling. ISO 32000-1 eist dat de keys in een /Names-array op bytewaarde gesorteerd zijn, dus probeert de library eerst een binaire zoekactie. Mist die, dan valt hij terug op een lineaire scan van de paren, want een uit volgorde geraakte leaf zou anders een aanwezige key onzichtbaar maken. Voor elke echte misser een lineaire scan betalen is een prijs die we accepteren: lookups naar namen die echt ontbreken zijn zeldzaam, en een valse "not found" op een werkende link kost veel meer dan één extra passage over een leaf

Eén structurele tegenstrijdigheid wordt met weigering afgehandeld. Tabel 36 laat een node /Kids óf /Names dragen, nooit allebei. Een keyed lookup behandelt een node die allebei draagt als misvormd en slaat hem over in plaats van te gokken welke helft de producent bedoelde. Enumeratie van number trees, zoals de walk achter GetPageLabel, is soepeler en volgt /Kids als allebei aanwezig zijn, want een heel bereik laten vallen zou elke pagina erna verkeerd labelen

Waarvoor mag een lezer /Limits vertrouwen?

Een reader mag /Limits vertrouwen om werk over te slaan, en alleen als het paar goed gevormd is; hij mag de entry nooit gebruiken om te concluderen dat een key ontbreekt. Tabel 36 zegt dat tussenliggende en leaf-nodes hem horen te dragen, maar in de praktijk verdwijnt de entry na handmatige edits, staan er getallen in binnen een name tree, of komt hij met verwisselde grenzen binnen. PDFlibPas lost elk van die gevallen op dezelfde manier op, door het kind doorzoekbaar te houden

  • Ontbrekende /Limits: een bereikcontrole die zo'n kind overslaat maakt zijn hele subtree onbereikbaar zodra een producent de entry vergeet, dus het kind wordt doorzocht
  • Verkeerd type of verkeerde lengte, zoals getallen in een name tree of een array van één element: exact afgehandeld als een ontbrekende entry
  • Verwisselde grenzen zoals [(Z) (A)] of [9 0]: geen key voldoet aan Lo <= Key <= Hi als Lo > Hi, dus het paar vertrouwen zou de tak bij elke lookup uitsluiten; een bereik snoeit alleen als zijn ondergrens niet boven zijn bovengrens uitkomt
  • Goed gevormd en geordend: gebruikt om de tak over te slaan, wat ook de reden is dat de entry bestaat
PDFlibPas-regels voor het vertrouwen van een Limits-array in een name tree: een ontbrekend, verkeerd getypt of omgekeerd paar laat het kind sinds v3.539.45 en v3.539.51 doorzoekbaar, en alleen een goed gevormd geordend paar mag de tak snoeien, dus een vijandige Limits kan bezoeken kosten maar kan een bestaande destination niet langer verbergen
Ranges mogen werk overslaan maar beslissen nooit over afwezigheid, want de echte keys in de leaves bepalen de uitkomst van elke lookup

Vanuit de kant van de aanroeper zijn er twee nullen uit elkaar te houden. GetNamedDestination geeft 0 terug als de naam echt ontbreekt en anders een destination-ID. GetDestPage die 0 teruggeeft bij een geldig ID betekent dat de naam bestaat maar zijn doel niet naar een pagina in dit document resolved, wat een andere bugmelding is. GetDestType meldt de weergave als 1 voor XYZ, 2 voor Fit enzovoort tot 8 voor 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;
    // Eerst catalog /Dests (PDF 1.1), dan de /Dests-name tree
    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;

Dit maakt een compacte regressiecheck. Bouw het bestand met twee kinderen uit de openingsalinea, wijs de echte chapter7-entry naar pagina 2 met een /Fit-weergave, en de procedure hoort pagina 2 met weergavetype 2 te printen. Een first-match-lookup print "No destination" omdat het loopende kind de race wint; een lookup die verwisselde bereiken vertrouwt print hetzelfde om de tegenovergestelde reden. Zodra destinations resolven, komen de outline-entries die ernaar wijzen aan bod in PDF-bladwijzer- en annotatie-actions lezen in Delphi

Leaves voorbij 32.768 entries en de ingepakte-index-valkuil

Als code één integer-handle nodig heeft voor "entry N in leaf M", verleidt de voor de hand liggende encoding hem ertoe de leafpositie in de hoge 16 bits van een Integer te proppen en de offset binnen de /Names-array van die leaf in de lage 16 bits. Elk paar kost twee arrayslots. Paarindex 32.768, het 32.769e paar, begint daardoor op offset 65.536, wat $10000 is. Die bit draagt over naar de hoge helft, en de decoder leest hem terug als offset 0 van de volgende leaf

PDFlibPas TPDFNameTree FindIndex-packing waarin een leafpositie en een entry-offset één 32-bit Integer deelden en paar 32768 op offset 65536 begon, zodat de carry naar de hoge helft als offset 0 van de volgende leaf werd gelezen en FindKey of DeleteKey het verkeerde paar aanraakte terwijl HasKey het oneens was
Twee 16-bit waarden in één 32-bit integer kappen stilletjes af op het moment dat een leaf 32.768 paren overschrijdt, een omvang die echte referentiemanuals bereiken

De symptomen hangen van de boomvorm af. Met één leaf is er geen volgende leaf, dus de gedecodeerde handle indexeert voorbij het einde van de leaflijst. Met meerdere leaves landt een find of delete op het eerste paar van de volgende leaf, terwijl een kale key-scan de gevraagde key nog steeds als aanwezig meldt. Bestanden van deze grootte zijn niet exotisch. Een gegenereerde API-referentie met één named destination per symbool passeert 32.768 entries snel, en sommige producenten schrijven ze allemaal in één platte leaf in plaats van de boom te balanceren

PDFlibPas houdt de leafpositie en de entry-offset in twee integers op volledige breedte, zodat geen van beide bij welke leafgrootte dan ook in de ander kan overlopen. Dezelfde reader telt alleen echte string keys. Voor een leaf als [(Valid) 42 123 456] meldt EmbeddedFileCount 1, wordt de numerieke key 123 nooit aangezien voor een lege naam, en geeft een index van 0 of lager een lege string terug uit GetEmbeddedFileStrProperty in plaats van welk object er ook toevallig op volgt. Tag 1 van die functie is de bestandsnaam en tag 2 het MIME-subtype

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // /PageLabels-number tree; bestanden zonder één geven kale paginanummers terug
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles-name tree; indexes zijn 1-based, niet-string keys worden overgeslagen
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // name, MIME subtype
    // /JavaScript-name tree: pakketnamen oplijsten, niets uitvoeren
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Een testbestand van twee pagina's laat de verwachte uitvoer goed zien. Geef zijn /PageLabels-root een /Kids-array die één leaf twee keer oplijst en ook naar de root zelf verwijst, met bereiken voor kleine romeinse cijfers vanaf pagina 1 en decimaal met prefix A- vanaf pagina 2. De audit hoort i en A-1 te printen, elk bereik één keer toegepast. Page labels in zo'n boom schrijven heeft zijn eigen hobbels, die aan bod komen in PDF-page labels herstellen die in /Kids-number trees zitten; AddPageLabels platt een /Kids-root af naar één /Nums-leaf voordat hij insert, met dezelfde cyclusveilige enumeratie

Waar de traversal zijn grenzen trekt

De traversal garandeert terminatie, stabiele volgorde en correcte antwoorden voor elke boom waarvan de echte keys intact zijn. Hij leest een beschadigde boom zoals geschreven en probeert niet te reconstrueren wat de auteur bedoelde, en uit die keuze volgen vijf gevolgen

  • Identiteit, niet inhoud, definieert een node. Twee verschillende dictionaries met identieke entries zijn twee nodes, dus een producent die een leaf kopieert in plaats van ernaar te verwijzen krijgt die entries dubbel
  • Een goed gevormd, geordend /Limits-paar snoeit zelfs als hij fout is. Een bereik dat plausibel liegt, zeg [(a) (m)] boven een leaf die ook (q) bevat, verbergt q. De enige verdediging zou zijn /Limits overal negeren en elke leaf scannen, en op een destination-tree met tienduizenden entries gooit dat de reden weg waarom de entry bestaat. We blijven snoeien
  • Enumeratie behoudt bestandsvolgorde. GetPageLabel doorloopt elk geënumereerd bereik en past de laatste toe waarvan de startindex op of onder de pagina uitkomt, dus een producent die bereiken uit volgorde schrijft krijgt semantiek op bestandsvolgorde, en de walk omdraaien zou pagina 200 de voorwerk-stijl geven
  • Geheugen groeit met unieke nodes en entries. De traversal voegt één lijst en één hash set toe bovenop de geparsde objecten
  • Dubbele keys binnen één leaf resolven deterministisch: de binaire zoekactie geeft het matchende paar terug waarop hij eerst landt, en de lineaire fallback houdt de laatste match die hij scant

Preflight-gereedschap, archiveringssoftware en documentviewers lezen deze bomen voordat er ook maar één pagina wordt gerenderd, wat hen vooraan in de rij zet voor alles wat in een uploadwachtrij aankomt. De boomreaders die hier worden beschreven worden meegeleverd met PDFlibPas, de PDF Library for Delphi, die met zowel Delphi als Free Pascal bouwt