PDF-Seitenbäume: Fan-Out, Abflachen und /Count-Integrität

Unser begleitender Artikel zur PDF-Seitenreihenfolge behandelt die Grundregel: Die Anzeigereihenfolge ergibt sich aus einem Tiefendurchlauf von links nach rechts durch die /Kids-Arrays im /Pages-Baum, niemals aus Objektnummern. Dieser Artikel betrachtet den Baum aus einer anderen Perspektive — seine Form. Warum erzeugen ausgereifte PDF-Writer Hierarchien aus Zwischenknoten, wenn ein einziges flaches Array vollkommen zulässig wäre? Was ändert sich tatsächlich, wenn ein Tool den Baum abflacht oder neu aufbaut? Und was passiert, wenn die /Count-Buchführung, die die ganze Struktur schnell macht, aufhört, die Wahrheit zu sagen

Fan-Out ist eine Performance-Entscheidung

Nichts zwingt einen Writer zur Verschachtelung. Ein Dokument mit 10.000 Seiten, einem einzigen Wurzel-/Pages-Knoten und 10.000 Blattverweisen in einem einzigen /Kids-Array entspricht der Spezifikation. Die PDF-Referenz empfiehlt dennoch einen ausbalancierten Baum für große Dokumente, und gängige Generatoren folgen diesem Rat mit einem moderaten Fan-Out, typischerweise ein paar Dutzend Kinder pro Zwischenknoten

Der Grund liegt darin, was ein Viewer lesen muss, bevor er überhaupt etwas anzeigen kann. Nehmen wir einen direkten Sprung zu Seite 8.214 dieser 10.000-Seiten-Datei. Bei einem flachen Baum muss der Viewer zunächst den Wurzelknoten parsen, und dieser Wurzelknoten ist ein einziges riesiges Array: bei rund acht Byte pro indirekter Referenz ein 80-KB-Objekt, das vollständig tokenisiert werden muss, bevor Eintrag 8.213 aufgelöst werden kann. Bei einem ausbalancierten Baum mit Fan-Out 32 liest derselbe Sprung die Wurzel, vergleicht laufende /Count-Summen, um das richtige Kind auszuwählen, und steigt ab — insgesamt drei oder vier kleine Dictionaries, jedes nur wenige hundert Byte groß. Das ist der O(log n)-Direktzugriff, für den der Baum entworfen wurde, und es ist der ganze Grund, warum /Count an Zwischenknoten existiert: Er erlaubt einem Reader, einen kompletten Teilbaum zu überspringen, ohne auch nur ein einziges Objekt darin zu öffnen

Die Baumform bestimmt auch die Kosten des Bearbeitens. Ein inkrementelles Update, das eine Seite einfügt, muss jeden Knoten neu schreiben, dessen /Kids oder /Count sich geändert hat — also den Pfad vom Elternknoten des neuen Blatts bis zur Wurzel. In einem ausbalancierten Baum ist dieser Pfad eine Handvoll kleiner Dictionaries, die an die Datei angehängt werden. In einem flachen Baum ist der „Pfad" das einzige riesige Wurzel-Array, das bei jeder Revision vollständig dupliziert wird. Ein Vertrag, der dreißig Prüf- und Kommentierungszyklen durchläuft, kann am Ende dreißig überholte Kopien desselben 80-KB-Arrays in seinem Byte-Strom mitschleppen

Innere Knoten tragen vererbte Attribute

Zwischenknoten dienen nicht nur der Weiterleitung. Die vier vererbbaren Seitenattribute — /Resources, /MediaBox, /CropBox und /Rotate — können auf jeden /Pages-Knoten gehoben werden, wo sie für jedes darunterliegende Blatt gelten, sofern kein Nachfahre sie überschreibt. Ein Writer, der einen Bericht mit einem Anhang im Querformat erzeugt, kann dieses Layout direkt im Baum ausdrücken:

5 0 obj   % Dokumentwurzel
<< /Type /Pages /Count 6 /Kids [6 0 R  7 0 R] >>
endobj

6 0 obj   % Berichtskörper: Hochformat A4, Fließtextschrift
<< /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   % Anhang: Querformat A4, gedreht, eigene Schrift
<< /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  % Anhangseite: erbt Größe, Drehung, Schriften
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

Die Objekte 40 bis 42 sind fast leer. Ihre Seitengröße, Drehung und Schriftressourcen kommen alle durch Vererbung von Knoten 7, was die Datei kompakt und selbstwartend hält: Fügt man eine vierte Seite unter dem Anhangsknoten hinzu, kommt sie automatisch im Querformat heraus

Derselbe Mechanismus erzeugt die klassische Gefahr beim Verschieben von Seiten. Angenommen, ein Tool verschiebt Objekt 40 in den Berichtskörper, indem es die beiden /Kids-Arrays bearbeitet und /Parent auf Knoten 6 umbiegt. Die Verschiebung ist strukturell gültig, doch Objekt 40 erbt nun die Hochformat-/MediaBox, keine Drehung und die Schrift /F1 — während sein Content-Stream weiterhin /F2 auswählt, das sich nicht mehr auflösen lässt. Die Seite schrumpft, verliert ihre Drehung und ihren Text in einer einzigen Bearbeitung. Robuster Umordnungscode materialisiert daher die aufgelösten Werte aller vier vererbbaren Attribute auf dem Seiten-Dictionary, bevor er es neu verankert. Wer schon einmal eine Seite in einem Editor gezogen und dabei ihre Größe oder Ausrichtung sich ändern gesehen hat, hat genau diesen Mechanismus beobachtet

Abflachen: legal, üblich, gelegentlich teuer

Viele Tools gehen den umgekehrten Weg. Minimale Writer erzeugen einen einstufigen Baum, weil das einfach ist, und viele Zusammenführungs- und Aufteilungswerkzeuge bauen jeden gelesenen Baum in ein einziges flaches /Kids-Array um, weil das Erzeugen einer ausbalancierten Struktur zusätzliche Arbeit ist und flache Ausgabe immer konform ist. Ein korrekter Neuaufbau muss dabei gleichzeitig die Vererbung auflösen: Jedes Attribut, das ein Blatt geerbt hat, muss auf das Blatt kopiert oder — falls im ganzen Dokument einheitlich — auf die neue Wurzel gehoben werden, sonst verändert die Ausgabe die Geometrie genau wie im Fall des Seitenverschiebens

Bei typischen Dokumenten ist das Abflachen harmlos. Es schadet erst in großem Maßstab, auf die beiden bereits beschriebenen Arten: Das Wurzel-Array wird zu einem großen Objekt, das jedes Öffnen und jeder Seitensprung vollständig parsen muss, und jede strukturelle Bearbeitung schreibt es komplett neu. Was das Abflachen nicht zerstört, ist die Deduplizierung über indirekte Referenzen — ein flacher Baum, in dem alle 10.000 Seiten auf dasselbe /Resources-Dictionary-Objekt zeigen, bleibt weiterhin dedupliziert. Verloren geht nur die Möglichkeit, den Eintrag auf der Seite wegzulassen und ihn von einem Vorfahren liefern zu lassen

Wenn /Count lügt

/Count ist reine Buchführung: Er muss der Anzahl der Blattseiten im Teilbaum des Knotens entsprechen, und nichts im Dateiformat erzwingt das. Zwei Beschädigungsmuster erklären die meisten der in freier Wildbahn beobachteten lügenden Zähler

Das erste ist der veraltete Zähler, der von einem inkrementellen Update zurückgelassen wird. Ein Editor fügt eine Seite ein, schreibt den unmittelbaren Elternknoten mit neuem /Kids und aktualisiertem /Count neu, hängt beides an die Datei an — und rührt die Vorfahren nie an:

% Ursprüngliche 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

% Angehängte Revision: eine Seite wurde in den mittleren Zweig eingefügt.
% Objekt 14 wird ersetzt; Objekt 12 wird nie neu geschrieben
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

Der Baum enthält jetzt zehn Blätter, aber die Wurzel sagt weiterhin neun. Ein Viewer, der der Wurzel vertraut, meldet neun Seiten in seiner Seitenanzeige. Einer, der innere Zähler für eine binäre Suche beim Seitensprung nutzt, berechnet für jede Seite nach dem Einfügepunkt einen falschen Index. Ein vollständiger Durchlauf findet zehn. Drei verschiedene Antworten, eine Datei

Das zweite Muster ist der Zähler, der niemals richtig sein konnte: negativ, null bei einem gefüllten Knoten oder absurd riesig. Diese stammen aus Fuzzing, aus Übertragungsschäden und gelegentlich aus Rechenfehlern in Editoren. Sie sind speziell für Code gefährlich, der /Count für die Allokation vertraut — ein Array anhand eines /Count von -3 zu dimensionieren, löst bestenfalls einen Bereichsfehler aus, und dasselbe mit einem /Count von zwei Milliarden zu tun, ist eine Denial-of-Service-Allokation. Der Wert ist nicht vertrauenswürdige Eingabe, wie jede andere Zahl in der Datei

Parser teilen sich hier in zwei Lager. Strikte Konsumenten — Preflight-Tools, PDF/A-Validatoren, Archivierungspipelines — vergleichen /Count mit dem Ergebnis des Durchlaufs und weisen die Datei zurück oder markieren sie. Interaktive Viewer sind fast durchweg tolerant: Sie durchlaufen den Baum, ermitteln den tatsächlichen Zähler und ignorieren den gespeicherten Wert stillschweigend — genau deshalb kann eine Datei mit veraltetem Zähler jahrelang unbeanstandet kursieren, bis sie in einem automatisierten Workflow auf einen strikteren Parser trifft. Der defensive Mittelweg für Bibliothekscode ist, /Count als Hinweis zu behandeln — nützlich für die Vorabreservierung und, sobald verifiziert, für das Überspringen von Teilbäumen — während der Durchlauf die maßgebliche Quelle bleibt

Für den Traversierungsalgorithmus selbst, die Regeln zur Vererbungssuche und den Weg vom Katalog zum Blatt beginnen Sie mit dem Artikel zur Seitenreihenfolge. Wie sich diese Fehlerbilder anfühlen, wenn ein echtes Kundendokument produktiven Code erreicht, zeigt die Debugging-Fallstudie zur Seitenreihenfolge, die einen Vorfall mit vertauschten Seiten vom Symptom bis zur Ursache verfolgt

Die HotPDF Delphi Component übernimmt all das intern: Sie durchläuft verschachtelte Bäume beliebiger Tiefe, löst vererbte Attribute auf, wenn Seiten kopiert oder verschoben werden, und verifiziert /Count gegen die tatsächliche Blattzahl, statt ihm zu vertrauen, sodass Seitenindizes in ihrer API immer logische Seiten bedeuten