PDF-Seitenbäume: Warum Seitenreihenfolge nicht Objektreihenfolge ist

Seite 1 eines PDFs ist nicht Objekt 1. Diese Unterscheidung ist die häufigste Quelle für „falsche Seite extrahiert“-Bugs in PDF-Parsern, und die Lösung ist, die Spezifikation zu lesen statt die Dateibytes

Objekte, Referenzen und der Katalog

Eine PDF-Datei ist eine Sammlung nummerierter Objekte. Jedes trägt eine eindeutige Objektnummer und eine Generationsnummer, geschrieben als N G obj, wobei G in Dateien ohne inkrementelle Updates fast immer 0 ist. Objekte referenzieren einander mit der Notation N G R, 3 0 R bedeutet also „die aktuelle Version von Objekt 3“. Der Trailer zeigt auf ein Wurzelkatalogobjekt, dessen /Pages-Eintrag zum Seitenbaum führt. Alles Navigierbare in einem PDF beginnt bei dieser Wurzel, nicht beim ersten Byte des Datei-Bodys

Die Querverweistabelle (oder der Querverweis-Stream in PDF 1.5+) bildet Objektnummern auf Datei-Offsets ab. Ihre Aufgabe ist wahlfreier Zugriff, nicht Ordnung. Ein Writer, der ein Dokument inkrementell aufbaut, kann neue Objekte mit höheren Nummern ans Ende anhängen, während diese Objekte in der Seitenabfolge logisch vor bestehenden liegen. Das ist kein Defekt; es ist Absicht

Der Seitenbaum (ISO 32000-1 §7.7.3)

Die Seitenabfolge lebt im Seitenbaum. Der Wurzelkatalog enthält eine /Pages-Referenz, die auf einen Knoten vom Typ /Pages zeigt. Das /Kids-Array dieses Knotens listet seine Kinder in Lesereihenfolge. Jedes Kind ist entweder ein Blattknoten vom Typ /Page oder ein weiterer /Pages-Zwischenknoten mit eigenem /Kids. Seite 1 ist das erste Blatt, das eine Tiefensuche von links nach rechts durch die Kids-Arrays erreicht. Der /Count-Eintrag an jedem Zwischenknoten cached die Gesamtzahl der Nachfahren-Blattseiten, damit ein Viewer zu Seite 500 springen kann, ohne den ganzen Baum abzulaufen

So sieht ein minimaler Drei-Seiten-Baum in roher PDF-Syntax aus:

16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R  1 0 R  4 0 R]
  /MediaBox [0 0 612 792]
>>
endobj

20 0 obj
<< /Type /Page  /Parent 16 0 R  /Contents 21 0 R  /Resources 22 0 R >>
endobj

1 0 obj
<< /Type /Page  /Parent 16 0 R  /Contents 2 0 R   /Resources 3 0 R >>
endobj

4 0 obj
<< /Type /Page  /Parent 16 0 R  /Contents 5 0 R   /Resources 6 0 R >>
endobj

Das Kids-Array liest sich [20 0 R, 1 0 R, 4 0 R]. Logische Seite 1 ist Objekt 20, logische Seite 2 ist Objekt 1, logische Seite 3 ist Objekt 4. Jeder Code, der Objektnummern ab 1 aufwärts iteriert, trifft sie in der Reihenfolge 1, 4, 20 an und erzeugt die Abfolge Seite-2, Seite-3, Seite-1. Das resultierende Dokument rendert in gemischter Reihenfolge, was in einem Viewer, der dem Baum folgt, völlig normal aussehen kann — und katastrophal falsch in einem, der es nicht tut

Vererbung

Zwischenknoten können Eigenschaften tragen, die ihre Nachfahren erben. Die häufigsten vererbten Einträge sind /MediaBox (Seitenmaße), /CropBox, /Resources (Schriften und Bilder) und /Rotate. Eine Blattseite, die /MediaBox weglässt, ist nicht kaputt; sie übernimmt den Wert vom nächstgelegenen Vorfahrknoten, der ihn definiert. Eine Seite, die /MediaBox definiert, überschreibt das, was der Elternknoten sagt — nur für diese Seite

Das zählt beim Parsen. Ein /Page-Objekt isoliert zu lesen und anzunehmen, seine Eigenschaften seien vollständig, meldet für jede Seite, die auf Vererbung baut, falsche Maße. Ein korrekter Reader läuft die /Parent-Kette entlang, sammelt noch nicht gesehene Eigenschaften ein und hält an der Wurzel an

Verschachtelte Bäume

Nichts in der Spezifikation beschränkt den Baum auf eine einzige Ebene. Ein großes Dokument könnte Seiten unter Zwischenknoten gruppieren, die grob Kapiteln entsprechen:

2 0 obj   % root Pages node, Count = 8
<< /Type /Pages  /Count 8  /Kids [3 0 R  4 0 R] >>
endobj

3 0 obj   % first chapter, 5 pages
<< /Type /Pages  /Parent 2 0 R  /Count 5
   /Kids [10 0 R  11 0 R  12 0 R  13 0 R  14 0 R]
   /MediaBox [0 0 612 792] >>
endobj

4 0 obj   % second chapter, 3 pages
<< /Type /Pages  /Parent 2 0 R  /Count 3
   /Kids [20 0 R  21 0 R  22 0 R]
   /MediaBox [0 0 612 792] >>
endobj

Der Traversierungsalgorithmus ist derselbe: Kids der Reihe nach besuchen, in jeden /Pages-Knoten rekursieren, /Page-Blattknoten einsammeln. Die /Count-Werte erlauben einem Viewer, einen ganzen Teilbaum zu überspringen, wenn er zu einer dahinterliegenden Seite springt — weshalb diese Zähler stimmen müssen. Manche PDF-Editoren aus den späten 1990ern und frühen 2000ern berechneten sie nach In-Place-Bearbeitungen nicht neu, ein defensiver Parser verifiziert /Count also gegen die tatsächliche Blattzahl, statt ihm bei der Array-Allokation zu vertrauen

Wo das in der Praxis auftaucht

Der Seitenreihenfolge-Bug zeigt sich am häufigsten in zwei Szenarien. Das erste ist ein eigener Parser, der nach Objekten vom Typ /Page scannt, statt dem Baum zu folgen. Er findet jede Seite, aber in Objektnummern-Reihenfolge, nicht in Lesereihenfolge. Die Lösung ist immer dieselbe: beim Trailer beginnen, den Wurzelkatalog auflösen, /Pages folgen und die Kids-Arrays traversieren

Das zweite Szenario ist eine Datei mit inkrementellen Updates. Wenn ein PDF-Editor Änderungen anhängt, ohne die ganze Datei neu zu schreiben, erhalten neue Seitenobjekte hohe Objektnummern, während das Kids-Array im ursprünglichen Baum weiterhin ihre logische Position bestimmt. Eine Seite, die ursprünglich Objekt 5 war, wird durch ein neues Objekt 143 ersetzt, aber das Kids-Array referenziert nun 143, wo es früher 5 referenzierte, die logische Reihenfolge bleibt also erhalten. Ein Durchlauf nach Objektnummer würde die Ersatzseite an die falsche Position der Abfolge setzen

Linearisierte (weboptimierte) PDFs fügen eine dritte Variante hinzu: Die Datei ist physisch so umgeordnet, dass der Inhalt der ersten Seite nahe dem Dateianfang liegt, für schnelle Anzeige über eine langsame Verbindung. Die Seitenbaumstruktur bleibt für die Reihenfolge maßgeblich, aber die Querverweistabelle bildet auf die umgeordneten Offsets ab. Ein Parser, der sich auf die Dateiposition statt auf die Xref-Tabelle verlässt, liest selbst die erste Seite einer linearisierten Datei falsch

Die HotPDF Component handhabt Seitenbaum-Traversierung, Vererbungsauflösung und das Zusammenführen von Xref-Abschnitten aus inkrementellen Updates intern. Wer direkt mit ihren Seitenobjekten arbeitet, hat die Kids-Array-Ordnung bereits angewendet; Seitenindizes bilden auf logische Seiten ab, nicht auf Objektnummern