Chyby poradia stránok PDF v HotPDF: Fyzická verzus logická štruktúra

Symptóm sa prejavil v utilite na kopírovanie stránok postavenej na komponentu HotPDF Component: požiadavka na stranu 1 z trojstranového dokumentu konzistentne vracala stranu 2. Kontrola indexovacej logiky neodhalila žiadnu chybu. Volanie používalo logický index od 0, aritmetika bola správna, okrajové podmienky boli v poriadku. Napriek tomu bol zakaždým vygenerovaný nesprávny výsledok.

Chyba nebola v samotnom kóde na kopírovanie. Problém bol v tom, ako HotPDF zostavoval svoje interné pole stránok pri načítavaní súboru.

Dve usporiadania, jeden zdroj zmätku

Súbor PDF je kolekcia nepriamych objektov, z ktorých každý je identifikovaný číslom objektu. Štruktúra súboru nekladie žiadne požiadavky na to, aby tieto čísla odrážali poradie čítania. Objekt 1 môže obsahovať stranu 2, objekt 20 môže obsahovať stranu 1. To, čo skutočne definuje poradie čítania, je strom stránok: hierarchia slovníkov /Pages, ktorých polia /Kids uvádzajú odkazy na strany v sekvencii, v akej ich má prehliadač zobraziť (ISO 32000-1 §7.7.3).

Dokument, ktorý vyvolal túto chybu, mal nasledujúcu štruktúru stromu stránok:

{ Pages tree root, object 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { logical page 1 }
         1 0 R    { logical page 2 }
         4 0 R]   { logical page 3 }
>>
endobj

Súbor náhodou uvádzal objekt 1 a objekt 4 pred objektom 20 v bajtovom prúde. Akýkoľvek parser, ktorý by prechádzal nepriame objekty v poradí súboru a zapisoval ich do PageArr podľa toho, ako našiel slovníky typu stránky, by skončil s objektom 1 na indexe 0, objektom 4 na indexe 1 a objektom 20 na indexe 2. Logická strana 1 sa tak ocitne na pozícii PageArr[2]. Požiadavka na index strany 0 potom vráti logickú stranu 2.

A presne to robili obe interné cesty parsovania v HotPDF. Tradičná cesta, používaná pre súbory PDF 1.3/1.4, aj moderná cesta, používaná pre dokumenty s prúdmi objektov (PDF 1.5+), zostavovali PageArr prechádzaním nepriamych objektov vo fyzickom poradí súboru namiesto sledovania reťazca /Kids.

Potvrdenie hypotézy

Pred akýmkoľvek zásahom do kódu bolo potrebné tento nesúlad dokázať. Nástroj príkazového riadka qpdf to výrazne zjednodušuje:

{ shell }
qpdf --show-pages input.pdf
{ Output reveals Kids order: 20 0 R, then 1 0 R, then 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Shows the Pages dictionary with /Kids in reading order }

Samostatné extrahovanie každej stránky a kontrola veľkostí súborov potvrdili toto mapovanie: PageArr[0] vrátil obsah patriaci logickej strane 2 a PageArr[2] obsahoval logickú stranu 1. Tento kruhový posun bol jasným dôkazom. Vysvetľovalo to tiež, prečo sa problém objavoval v rôznych zdrojových dokumentoch: vyvolalo ho akékoľvek PDF, kde mali objekty neskorších strán náhodou nižšie čísla objektov ako predchádzajúca logická stránka.

Existuje jednoduchý dôvod, prečo PDF končia v takomto stave. Prírastkové ukladanie (incremental saves) pripája aktualizované objekty s novými číslami objektov, pričom staré sloty v tabuľke krížových odkazov necháva ukazovať nikam. Editory, ktoré pridávajú obálku, ju vložia s vysokým číslom objektu bez ohľadu na jej pozíciu v poli Kids. Niektoré generátory jednoducho zapisujú stránky v poradí, ktoré je výhodné pre prúdové posielanie obsahu, a nie podľa logického poradia stránok. Formát PDF od nich nič iné nevyžaduje.

Oprava: sledovanie poľa Kids

Správnym prístupom je zostaviť PageArr prechádzaním reťazca /Kids od koreňa katalógu, nie skenovaním nepriamych objektov. Po tom, čo obe parsovacie cesty dokončia svoj úvodný prechod, krok dodatočného spracovania usporiada logické poradie:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Locate root /Pages dictionary via FRootIndex }
  PagesObj := FindPagesRootFromCatalog;
  if PagesObj = nil then Exit;

  KidsIndex := PagesObj.FindValue('Kids');
  if KidsIndex < 0 then Exit;
  KidsArray := THPDFArrayObject(PagesObj.GetIndexedItem(KidsIndex));

  SetLength(NewPageArr, KidsArray.Items.Count);
  PageIndex := 0;

  for I := 0 to KidsArray.Items.Count - 1 do
  begin
    RefObj     := THPDFLink(KidsArray.GetIndexedItem(I));
    PageObjNum := RefObj.Value.ObjectNumber;

    Found := False;
    for J := 0 to Length(PageArr) - 1 do
    begin
      if PageArr[J].PageLink.ObjectNumber = PageObjNum then
      begin
        NewPageArr[PageIndex] := PageArr[J];
        Inc(PageIndex);
        Found := True;
        Break;
      end;
    end;
    { Non-page Kids (intermediate /Pages nodes) produce no match; skip }
  end;

  if PageIndex > 0 then
  begin
    SetLength(PageArr, PageIndex);
    for I := 0 to PageIndex - 1 do
      PageArr[I] := NewPageArr[I];
  end;
end;

Volanie sa vloží na koniec každej cesty parsovania, po tom, čo boli všetky objekty katalogizované, ale ešte pred vykonaním akejkoľvek operácie so stránkami:

{ Traditional path }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Modern path (object streams) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

Krok preusporiadania má zložitosť O(n * m), kde n je počet položiek Kids a m je aktuálna dĺžka poľa PageArr. Pre akýkoľvek dokument s plochým stromom stránok (všetky listy na hĺbke 1, čo pokrýva drvivú väčšinu reálnych PDF) majú obe hodnoty rovnakú veľkosť a réžia je zanedbateľná. Hlboko vnorené stromy stránok vyžadujú rekurzívny prechod namiesto tu ukázaného jednoúrovňového prístupu; produkčná implementácia rieši tento prípad samostatne.

Použitie CopyPageFromDocument po oprave

S implementovanou metódou ReorderPageArrByPagesTree fungujú logické indexy stránok podľa očakávania. Vyššia metóda CopyPageFromDocument prevezme logický index od 0 a skopíruje správnu stranu do cieľového dokumentu:

var
  Source, Dest: THotPDF;
begin
  Source := THotPDF.Create(nil);
  Dest   := THotPDF.Create(nil);
  try
    Source.LoadFromFile('source.pdf');

    Dest.FileName := 'extracted.pdf';
    Dest.BeginDoc;

    { Copy logical page 0 (first page the user sees) }
    Dest.CopyPageFromDocument(Source, 0, 0);

    Dest.EndDoc;
  finally
    Source.Free;
    Dest.Free;
  end;
end;

Metóda CopyPageFromDocument interne zisťuje poradie v strome stránok namiesto toho, aby sa spoliehala na surový index PageArr, so správa sa správne aj v dokumentoch, kde sa fyzické a logické poradie líšia. Pre dávkové operácie prijíma metóda InsertPagesFromDocument pole logických indexov a kopíruje ich v jednom prechode.

Čo to hovorí o parsovaní PDF

Špecifikácia PDF hovorí jasne: logické poradie stránok je definované poľom /Kids stromu stránok, nie číslami objektov alebo bajtovými posunmi (ISO 32000-1 §7.7.3.2). Akýkoľvek parser, ktorý ako skratku používa iné usporiadanie, vyprodukuje správne výsledky pri väčšine dokumentov, pretože väčšina generátorov zapisuje stránky v prirodzenom poradí a priraďuje im sekvenčné čísla objektov. Chyba zostáva skrytá, kým niekto nenačíta PDF, ktoré bolo prírastkovo upravované, reorganizované iným nástrojom alebo vygenerované softvérom, ktorý zvolil odlišnú štruktúru.

Testovanie iba na vlastnoručne vygenerovaných súboroch PDF túto triedu problémov úplne obchádza. Oprava regresie poradia stránok preto vyžaduje sadu testovacích dokumentov z rôznych zdrojov: prírastkové ukladania, naskenované dokumenty s vloženými obálkami, PDF vytvorené nástrojmi, ktoré inak linearizujú alebo optimalizujú graf objektov. Dokument, ktorý pôvodnú chybu vyvolal, by mal natrvalo zostať v regresnej sade testov.

Stránka HotPDF Component popisuje celé rozhranie API pre operácie so stránkami, vrátane metód CopyPageFromDocument, InsertPagesFromDocument a MovePage.