Bauen Sie ein PDF, dessen /Dests-Name-Tree eine Wurzel mit zwei Kindern hat. Das erste Kind deklariert /Limits [(a) (z)], und sein /Kids-Array zeigt direkt zurück auf die Wurzel. Das zweite Kind hält den echten Eintrag für (chapter7), aber seine Limits stehen verdreht drin: [(z) (a)]. Fragt man einen Lehrbuch-Name-Tree-Lookup nach chapter7, rekursiert er entweder, bis der Stack alle ist, oder liefert „nicht gefunden" für eine Destination, zu der ein Viewer springen kann. Die ganze Datei passt in rund zwei Kilobyte, und jedes Objekt darin parst sauber
Diese Datei packt drei getrennte Fallen in eine Struktur: einen /Kids-Zyklus, eine Range, die einen Schlüssel für sich beansprucht, den sie nicht hält, und eine Range, die nie auf irgendetwas passen kann. Eine vierte Falle braucht eine deutlich größere Datei. Sobald ein einzelnes Blatt mehr als 32.768 Name-Wert-Paare trägt, zeigt jeder Code, der „welches Blatt" und „welcher Eintrag" in einen 32-Bit-Integer quetscht, aufs falsche Paar. Der Rest des Artikels geht jede Falle durch, was ein Reader dagegen tun sollte, und wie sich die Delphi-Aufrufe auf so gebauten Dateien verhalten
Vier PDF-Features, die auf Name Trees und Number Trees sitzen
Name Trees und Number Trees tragen jedes PDF-Feature, das eine große Schlüsselmenge auf Objekte abbildet, und PDFlibPas, die losLab PDF Library for Delphi, legt vier davon über öffentliche TPDFlib-Methoden offen. ISO 32000-1 §7.9.6 definiert den Name Tree (String-Schlüssel, Table 36) und §7.9.7 den Number Tree (Integer-Schlüssel, Table 37). Wurzel und innere Knoten tragen /Kids; Blätter tragen sortierte Schlüssel-Wert-Paare in /Names oder /Nums; jeder Nicht-Wurzel-Knoten soll ein zweielementiges /Limits-Array mit dem kleinsten und größten Schlüssel darunter tragen
| Tree | Wo er lebt | Spezifikation | PDFlibPas-Lese-API |
|---|---|---|---|
| Named Destinations | /Dests im Name-Dictionary | §12.3.2.3 | GetNamedDestination, dann GetDestPage / GetDestType |
| Page Labels | /PageLabels im Katalog (Number Tree) | §12.4.2 | GetPageLabel |
| Attachments | /EmbeddedFiles im Name-Dictionary | §7.7.4, §7.11.4 | EmbeddedFileCount, GetEmbeddedFileStrProperty |
| Dokument-Level-JavaScript | /JavaScript im Name-Dictionary | §7.7.4 | GlobalJavaScriptCount, GlobalJavaScriptPackageName |
Zwei Zeilen verbergen eine Kleinigkeit. Named Destinations existieren auch in der älteren PDF-1.1-Form, ein schlichtes /Dests-Dictionary im Katalog, mit Name-Objekten als Schlüsseln, und GetNamedDestination prüft dieses Dictionary zuerst und steigt erst danach in den PDF-1.2-Name-Tree hinab. Die JavaScript-Zeile hat einen fast gleichnamigen Zwilling, der etwas ganz anderes liest: GetDocJavaScript liefert die Skripte an den Dokument-Triggern im /AA-Dictionary des Katalogs (WS, DS, WP, DP, DC), während die benannten Pakete, die beim Öffnen eines Dokuments laufen, im /JavaScript-Name-Tree leben und GlobalJavaScriptPackageName sie auflistet
All diese Strukturen kommen aus der Datei. Die Spezifikation sagt einem Schreiber, was er erzeugen soll, und ein Reader bekommt trotzdem, was der Schreiber, ein kaputtes inkrementelles Save oder ein Fuzzer tatsächlich hineingelegt haben. Das ist dieselbe Lektion wie bei Härtung eines Pascal-PDF-Parsers gegen bösartige Dateien, angewandt auf Baumform statt Buffer-Längen
Warum lässt ein zyklisches /Kids-Array einen rekursiven Tree-Walker abstürzen?
Ein rekursiver Walker stürzt an einem zyklischen /Kids-Array ab, weil nichts in der Rekursion daran erinnert, welche Knoten er schon betreten hat — eine einzige Kind-Referenz auf einen Vorfahren macht also aus einer endlichen Datei einen endlosen Abstieg. Ein legitimer Baum kann denselben Schaden ganz ohne Zyklus anrichten: Eine Kette aus 4.096 Einzelkind-Knoten ist gültige Syntax und kostet einen rekursiven Reader 4.096 Stack-Frames
Die mildere Variante stürzt gar nicht ab. Verweisen zwei /Kids-Einträge auf dasselbe Blatt, besucht eine naive Aufzählung es zweimal, eine Attachment-Zählung kommt also höher zurück als die Dateianzahl im Dokument, und eine Skript-Liste zeigt dasselbe Paket doppelt
PDFlibPas durchläuft beide Baumarten mit einem expliziten Last-in-first-out-Stack auf dem Heap plus einem Visited-Set über die Dictionary-Identität. Ein Knoten wird beim Pop markiert. Eine zyklische Referenz darf kurz auf dem Stack sitzen, wird aber spätestens beim Wiederauftauchen verworfen, und jeder unterschiedliche Knoten expandiert seine Kinder genau einmal. Die Gesamtarbeit ist durch die Anzahl der verschiedenen Dictionarys plus die Gesamtlänge ihrer /Kids-Arrays begrenzt; eine 4.096-Ebenen-Kette wird zu 4.096 Schleifeniterationen und 4.096 Hash-Set-Einträgen
Die Reihenfolge ist der Teil, den Leute vermasseln, wenn sie Rekursion in eine Schleife verwandeln. Ein Stack dreht alles um, was man ihm gibt, also müssen Kinder vom letzten Index abwärts bis zum ersten gepusht werden; dann poppt das linkeste Kind zuerst und die Blätter kommen in der Links-nach-rechts-Reihenfolge heraus, in der der Produzent sie schrieb. Beim Pop statt beim Push zu markieren zählt aus demselben Grund. Mit Markierung beim Push und Right-to-left-Pushes würde ein Blatt, das die Positionen 0 und 2 teilen, von Position 2 beansprucht, und seine Einträge erschienen später, als die Datei es sagt. Page Labels hängen an dieser Reihenfolge, wie der letzte Abschnitt zeigt
Schreiben Sie Ihren eigenen Baum-Code gegen ein anderes Objektmodell, ist dies die Form, die wir empfehlen. Der Knotentyp unten ist bewusst abstrakt gehalten, und beide Funktionen sind Reader-seitiger Code, keine Bibliotheksaufrufe
uses
System.Generics.Collections;
type
TTreeNode = class
public
Kids: TArray<TTreeNode>; // leer bei einem Blatt
Keys: TArray<string>; // Blattschlüssel, sortiert von einem sauber arbeitenden Produzenten
Values: TArray<Integer>; // parallel zu Keys
HasLimits: Boolean;
LoKey, HiKey: string;
end;
// Eigener Helfer: /Limits darf nur beschneiden, wenn es ein wohlgeformtes, geordnetes Paar ist
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;
// Eigenes Lookup: expliziter Stack, Visited-Set, Markierung beim 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; // Zyklus oder geteiltes Kind: schon gesehen
Visited.Add(Node, 0);
if Length(Node.Kids) > 0 then
begin
// Von rechts nach links pushen, damit das linkeste Kind zuerst gepoppt wird
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;
// Ein Fehlschlag in diesem Blatt: Geschwister weiter poppen
end;
finally
Visited.Free;
Pending.Free;
end;
end;
Ein Fehlschlag in einem Zweig sagt nichts über den Baum
Der häufigste Lookup-Shortcut wählt das erste Kind, dessen /Limits den Schlüssel abdeckt, steigt hinein und schaut sich Geschwister nie wieder an. Auf einem sauberen Baum ist das korrekt und schnell. Auf der Datei aus dem Eingangsabschnitt failt es: Das erste Kind beansprucht chapter7, führt zurück zur Wurzel, und die Suche endet mit leeren Händen, während das nächste Geschwisterkind den Eintrag hält
PDFlibPas hält nicht am ersten plausiblen Zweig. Der keyed Lookup hinter GetNamedDestination pusht jedes Kind, dessen Range den Schlüssel nicht ausschließt, und poppt weiter, bis ein Match gefunden ist oder der Stack leer ist. Auf einem wohlgeformten Baum mit disjunkten Rängen überlebt pro Ebene höchstens ein Kind den Range-Check, die Extrakosten sind also null. Auf einem beschädigten sind es eine Handvoll zusätzliche Knotenbesuche, und die Antwort kommt richtig zurück
Blätter bekommen dieselbe Behandlung. ISO 32000-1 verlangt, dass die Schlüssel eines /Names-Arrays nach Bytewert sortiert sind, die Bibliothek probiert also zuerst eine binäre Suche. Miss die, fällt sie auf einen linearen Scan der Paare zurück, denn ein außer der Reihe sortiertes Blatt würde einen vorhandenen Schlüssel sonst unsichtbar machen. Den linearen Scan bei jedem echten Fehlschlag mitzubezahlen ist ein Preis, den wir akzeptieren: Lookups nach wirklich abwesenden Namen sind selten, und ein falsches „nicht gefunden" auf einem funktionierenden Link kostet weit mehr als ein Extra-Durchlauf durch ein Blatt
Ein struktureller Widerspruch wird durch Zurückweisung abgehandelt. Table 36 lässt einen Knoten entweder /Kids oder /Names tragen, nie beides. Ein keyed Lookup behandelt einen Knoten mit beidem als missgestaltet und überspringt ihn, statt zu raten, welche Hälfte der Produzent meinte. Die Aufzählung von Number Trees, etwa der Lauf hinter GetPageLabel, ist nachsichtiger und folgt /Kids, wenn beide vorhanden sind, denn eine ganze Range wegfallen zu lassen würde jede Seite danach falsch labeln
Wofür darf ein Leser /Limits vertrauen?
Ein Reader darf /Limits vertrauen, um Arbeit zu überspringen, und auch das nur bei einem wohlgeformten Paar; benutzen darf er den Eintrag nie, um daraus zu schließen, ein Schlüssel sei abwesend. Table 36 schreibt vor, dass innere Knoten und Blätter ihn tragen, in der Praxis verschwindet der Eintrag nach Hand-Edits, hält Zahlen innerhalb eines Name Trees oder kommt mit vertauschten Grenzen an. PDFlibPas löst jeden dieser Fälle gleich, indem es das Kind durchsuchbar hält
- Fehlendes
/Limits: Ein Range-Check, der so ein Kind überspringt, macht seinen ganzen Teilbaum unerreichbar, sobald ein Produzent den Eintrag vergisst — das Kind wird durchsucht - Falscher Typ oder falsche Länge, etwa Zahlen in einem Name Tree oder ein Array mit nur einem Element: wird exakt wie ein fehlender Eintrag behandelt
- Vertauschte Grenzen wie
[(Z) (A)]oder[9 0]: Kein Schlüssel erfülltLo <= Key <= Hi, wennLo > Hi, dem Paar zu vertrauen würde den Zweig also bei jedem Lookup ausschließen; eine Range beschneidet nur, wenn ihre untere Grenze ihre obere nicht übersteigt - Wohlgeformt und geordnet: dient zum Überspringen des Zweigs, dafür existiert der Eintrag
Von der Aufruferseite gibt es zwei Nullen auseinanderzuhalten. GetNamedDestination liefert 0, wenn der Name wirklich abwesend ist, sonst eine Destination-ID. GetDestPage mit 0 für eine gültige ID heißt: Der Name existiert, aber sein Ziel löst sich zu keiner Seite dieses Dokuments auf — das ist eine andere Fehlermeldung. GetDestType meldet die Ansicht als 1 für XYZ, 2 für Fit und so weiter bis 8 für 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;
// Katalog-/Dests (PDF 1.1) zuerst, dann der /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;
Das ergibt einen kompakten Regressionstest. Bauen Sie die Zweikinder-Datei aus dem Eingangsabschnitt, zeigen Sie den echten chapter7-Eintrag auf Seite 2 mit einer /Fit-Ansicht, und die Prozedur sollte Seite 2 mit Ansichtstyp 2 drucken. Ein Ersttreffer-Lookup druckt „No destination", weil das loopende Kind das Rennen gewinnt; ein Lookup, das vertauschten Rängen vertraut, druckt dasselbe aus dem entgegengesetzten Grund. Sobald Destinationen sich auflösen, sind die Outline-Einträge, die auf sie zeigen, in PDF-Lesezeichen- und Annotations-Actions in Delphi lesen abgedeckt
Blätter jenseits von 32.768 Einträgen und die gepackte-Index-Falle
Braucht Code einen Integer-Handle für „Eintrag N in Blatt M", packt die verführende Kodierung die Blattposition in die hohen 16 Bits eines Integer und den Offset im /Names-Array dieses Blatts in die niedrigen 16 Bits. Jedes Paar belegt zwei Array-Slots. Paar-Index 32.768, das 32.769te Paar, beginnt also bei Offset 65.536, was $10000 ist. Dieses Bit trägt in die hohe Hälfte, und der Dekoder liest es als Offset 0 des nächsten Blatts zurück
Die Symptome hängen von der Baumform ab. Bei einem einzelnen Blatt gibt es kein nächstes Blatt, der dekodierte Handle indiziert also hinter das Ende der Blattliste. Bei mehreren Blättern landet ein Find oder ein Delete auf dem ersten Paar des folgenden Blatts, während ein schlichter Schlüssel-Scan den angefragten Schlüssel weiterhin als vorhanden meldet. Dateien dieser Größe sind nicht exotisch. Eine generierte API-Referenz mit einer Named Destination pro Symbol übersteigt 32.768 Einträge schnell, und manche Produzenten schreiben jeden davon in ein einziges flaches Blatt, statt den Baum zu balancieren
PDFlibPas hält Blattposition und Eintrags-Offset in zwei Integern voller Breite, keiner kann also bei keiner Blattgröße in den anderen überlaufen. Derselbe Reader zählt nur echte String-Schlüssel. Für ein Blatt wie [(Valid) 42 123 456] meldet EmbeddedFileCount 1, der numerische Schlüssel 123 wird nie für einen leeren Namen gehalten, und ein Index von 0 oder darunter liefert aus GetEmbeddedFileStrProperty einen leeren String statt des Objekts, das zufällig folgt. Tag 1 dieser Funktion ist der Dateiname, Tag 2 der MIME-Subtyp
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; Dateien ohne einen liefern schlichte Seitennummern
for I := 1 to Lib.PageCount do
WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
// /EmbeddedFiles-Name-Tree; Indizes sind 1-basiert, Nicht-String-Schlüssel übersprungen
for I := 1 to Lib.EmbeddedFileCount do
WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')'); // Name, MIME-Subtyp
// /JavaScript-Name-Tree: Paketnamen auflisten, nichts ausführen
for I := 1 to Lib.GlobalJavaScriptCount do
WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
finally
Lib.Free;
end;
end;
Eine Testdatei mit zwei Seiten zeigt die erwartete Ausgabe gut. Geben Sie ihrer /PageLabels-Wurzel ein /Kids-Array, das ein Blatt zweimal listet und zusätzlich die Wurzel selbst referenziert, mit Ranges für Kleinbuchstaben-römisch ab Seite 1 und Dezimal mit Präfix A- ab Seite 2. Der Audit sollte i und A-1 drucken, jede Range einmal angewandt. Page Labels in so einen Baum zu schreiben hat eigene Tücken, abgedeckt in PDF-Seiten-Labels reparieren, die in /Kids-Number-Trees liegen; AddPageLabels flacht eine /Kids-Wurzel vor dem Einfügen zu einem einzelnen /Nums-Blatt ab, mit derselben zyklussicheren Aufzählung
Wo der Durchlauf seine Grenzen zieht
Der Durchlauf garantiert Terminierung, stabile Reihenfolge und richtige Antworten für jeden Baum, dessen echte Schlüssel intakt sind. Er liest einen beschädigten Baum, wie er geschrieben ist, und versucht nicht zu rekonstruieren, was der Autor gemeint hätte; fünf Konsequenzen folgen aus dieser Wahl
- Identität, nicht Inhalt, definiert einen Knoten. Zwei verschiedene Dictionarys mit identischen Einträgen sind zwei Knoten; ein Produzent, der ein Blatt kopiert statt es zu referenzieren, bekommt diese Einträge also doppelt
- Ein wohlgeformtes, geordnetes
/Limits-Paar beschneidet, selbst wenn es falsch liegt. Eine Range, die plausibel lügt, etwa[(a) (m)]über einem Blatt, das auch(q)hält, verstecktq. Die einzige Verteidigung wäre,/Limitsüberall zu ignorieren und jedes Blatt zu scannen, und auf einem Destination-Tree mit Zehntausenden Einträgen wirft das genau den Grund weg, warum der Eintrag existiert. Wir beschneiden weiter - Aufzählung erhält Dateireihenfolge.
GetPageLabelläuft über jede aufzählte Range und wendet die letzte an, deren Startindex auf oder unter der Seite liegt; ein Produzent, der Ränge außer der Reihe schreibt, bekommt also Dateireihenfolgen-Semantik, und ein umgedrehter Lauf würde Seite 200 den Vorspann-Stil geben - Speicher wächst mit verschiedenen Knoten und Einträgen. Der Durchlauf legt eine Liste und ein Hash-Set über die geparsten Objekte
- Doppelte Schlüssel in einem Blatt lösen sich deterministisch auf: Die binäre Suche liefert das erste passende Paar, auf das sie trifft, und der lineare Fallback behält den letzten gescannten Treffer
Preflight-Tools, Archivierer und Dokument-Viewer lesen diese Trees, bevor eine einzige Seite gerendert wird — sie stehen also zuerst in der Schlange für alles, was in einer Upload-Queue ankommt. Die hier beschriebenen Tree-Reader kommen mit PDFlibPas, the PDF Library for Delphi, das sowohl mit Delphi als auch mit Free Pascal baut