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
| Tree | Waar hij huist | Specificatie | PDFlibPas lees-API |
|---|---|---|---|
| Named destinations | /Dests in de name dictionary | §12.3.2.3 | GetNamedDestination, daarna GetDestPage / GetDestType |
| Page labels | /PageLabels in de catalog (number tree) | §12.4.2 | GetPageLabel |
| Attachments | /EmbeddedFiles in de name dictionary | §7.7.4, §7.11.4 | EmbeddedFileCount, GetEmbeddedFileStrProperty |
| Document-level JavaScript | /JavaScript in de name dictionary | §7.7.4 | GlobalJavaScriptCount, 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
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 aanLo <= Key <= HialsLo > 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
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
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, verbergtq. De enige verdediging zou zijn/Limitsoveral 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.
GetPageLabeldoorloopt 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