PDF oldal sorrendi hibák a HotPDF-ben: Fizikai kontra logikai struktúra

A tünet egy oldalmásoló segédprogramban (page-copying utility) jelentkezett, amely a HotPDF Component tetejére épült: egy háromoldalas dokumentum 1. oldalának kérése következetesen a 2. oldalt hozta létre. Az indexelési logika (indexing logic) ellenőrzése nem talált semmi hibát. A hívás 0-alapú logikai indexet használt, az aritmetika helyes volt, a peremfeltételek (boundary conditions) rendben voltak. Mégis minden alkalommal rossz oldal jött ki

A hiba egyáltalán nem a másoló kódjában volt. Abban volt, ahogyan a HotPDF felépítette a belső oldaltömbjét (internal page array) a fájl betöltésekor

Két sorrend, egyetlen forrása a zűrzavarnak

Egy PDF-fájl indirekt objektumok gyűjteménye, mindegyik egy objektum számmal (object number) azonosítva. A fájlstruktúra nem kötelezi ezeket a számokat az olvasási sorrend (reading order) tükrözésére. Az 1. objektum tartalmazhatja a 2. oldalt; a 20. objektum tartalmazhatja az 1. oldalt. Ami valójában meghatározza az olvasási sorrendet, az az oldalfa (page tree): /Pages szótárak hierarchiája, amelyek /Kids tömbjei abban a sorrendben sorolják fel az oldal hivatkozásokat, ahogy a megjelenítőnek (viewer) meg kellene jelenítenie őket (ISO 32000-1 §7.7.3)

A hibát kiváltó dokumentum a következő oldalfa struktúrával rendelkezett:

{ Az oldalfa gyökere, 16. objektum }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { 1. logikai oldal }
         1 0 R    { 2. logikai oldal }
         4 0 R]   { 3. logikai oldal }
>>
endobj

A fájl történetesen az 1. objektumot és a 4. objektumot sorolta fel a 20. objektum előtt a bájtfolyamban (byte stream). Bármelyik elemző (parser), amely a fájl sorrendjében iterált az indirekt objektumokon, és bepecsételte őket egy PageArr-be, amint oldal típusú (page-type) szótárakat talált, az 1. objektummal a 0. indexen, a 4. objektummal az 1. indexen és a 20. objektummal a 2. indexen kötne ki. Az 1. logikai oldal a PageArr[2]-n ül. A 0. oldalindex kérése ehelyett a 2. logikai oldalt hozza be

Pontosan ezt csinálta a HotPDF mindkét belső elemzési útvonala (internal parsing paths). A hagyományos útvonal, amelyet a PDF 1.3/1.4 fájlokhoz használnak, és a modern útvonal, amelyet az objektum-folyam (object-stream) dokumentumokhoz (PDF 1.5+) használnak, mindegyike a PageArr felépítését az indirekt objektumok fizikai fájl sorrendben történő végigjárásával (walking) végezte ahelyett, hogy követte volna a /Kids láncot

A hipotézis megerősítése

Mielőtt bármilyen javításhoz hozzáérnénk, az eltérést (mismatch) be kellett bizonyítani, nem pedig feltételezni. A qpdf parancssori eszköz ezt egyszerűvé teszi:

{ shell }
qpdf --show-pages input.pdf
{ A kimenet felfedi a Kids sorrendet: 20 0 R, majd 1 0 R, majd 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Megmutatja a Pages szótárat a /Kids elemmel olvasási sorrendben }

Az egyes oldalak egyenkénti kinyerése (extracting) és a fájlméretek ellenőrzése megerősítette a leképezést (mapping): amit a PageArr[0] létrehozott, az a 2. logikai oldalhoz tartozó tartalom volt, és a PageArr[2] tartotta az 1. logikai oldalt. A körkörös eltolás (circular shift) volt a döntő bizonyíték (smoking gun). Ez azt is megmagyarázta, hogy a probléma miért jelentkezett több különböző forrásdokumentumnál (source documents): bármilyen PDF, ahol az oldal objektumok történetesen alacsonyabb objektum számmal rendelkeztek, mint egy korábbi logikai oldal, kiváltaná ezt

Van egy egyértelmű oka annak, hogy a PDF-ek ebbe az állapotba kerülnek. Az inkrementális mentések (incremental saves) a frissített objektumokat új objektum számokkal fűzik hozzá, üresen hagyva a régi helyeket a kereszthivatkozási táblában (cross-reference table), amelyek sehova sem mutatnak. Azok a szerkesztők, amelyek fedőlapot (cover page) adnak hozzá, magas objektum számmal illesztik be azt, függetlenül attól, hogy hol helyezkedik el a Kids tömbben. Egyes generátorok egyszerűen olyan sorrendben írják az oldalakat, amely kényelmes a tartalomfolyam (content streaming) számára, nem pedig a logikai oldalsorrendben. A PDF formátum nem követeli meg tőlük, hogy másképp tegyék

A javítás: kövesse a Kids tömböt

A helyes megközelítés az, hogy a PageArr-t a katalógus (catalog) gyökerétől kiindulva a /Kids lánc végigjárásával építsük fel, ne pedig az indirekt objektumok beolvasásával. Miután mindkét elemzési útvonal (parsing paths) befejezte a kezdeti menetét (initial pass), egy utófeldolgozási lépés (post-processing step) feloldja a logikai sorrendet:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { A gyökér /Pages szótár megkeresése az FRootIndex segítségével }
  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;
    { A nem oldal Kids (közbenső /Pages csomópontok) nem adnak egyezést; kihagyás }
  end;

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

A hívás minden elemzési útvonal végén történik, miután minden objektum katalogizálva lett, de mielőtt bármilyen oldal műveletet kiszolgálnának:

{ Hagyományos útvonal }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Modern útvonal (objektum folyamok) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

Az újrarendezési lépés (reorder step) O(n * m) összetettségű, ahol n a Kids száma és m az aktuális PageArr hossza, de minden lapos oldalfával (flat page tree - minden levél 1. mélységben, ami lefedi a való világ PDF-jeinek túlnyomó többségét) rendelkező dokumentum esetében mindkettő azonos érték, és a költség elhanyagolható. A mélyen beágyazott (deeply nested) oldalfák az itt bemutatott egyszintű megközelítés helyett rekurzív végigjárást igényelnek; az éles (production) implementáció ezt az esetet külön kezeli

A CopyPageFromDocument használata a javítás után

A ReorderPageArrByPagesTree a helyén van, így a logikai oldalindexek (logical page indices) a várt módon működnek. A magasabb szintű CopyPageFromDocument egy 0-alapú logikai indexet vesz fel, és bemásolja a megfelelő oldalt a cél dokumentumba (destination document):

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

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

    { A 0. logikai oldal másolása (az első oldal, amit a felhasználó lát) }
    Dest.CopyPageFromDocument(Source, 0, 0);

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

A CopyPageFromDocument belsőleg lekérdezi az oldalfa sorrendjét (page tree order) ahelyett, hogy a nyers (raw) PageArr indexre támaszkodna, így helyesen viselkedik még az olyan dokumentumokkal szemben is, ahol a fizikai és a logikai sorrend eltér (diverge). Kötegelt műveletekhez (batch operations) az InsertPagesFromDocument elfogadja a logikai indexek tömbjét, és egy menetben másolja őket

Mit árul el ez a PDF elemzésről (parsing)

A PDF specifikáció egyértelmű: a logikai oldal sorrendet az oldalfa /Kids tömbje határozza meg, nem pedig az objektum számok vagy a bájt eltolások (ISO 32000-1 §7.7.3.2). Bármelyik elemző (parser), amely parancsikonként (shortcut) más sorrendet használ, helyes eredményeket fog produkálni az általa látott dokumentumok többségén, mert a legtöbb generátor természetes sorrendben írja az oldalakat, és szekvenciális objektum számokat rendel hozzájuk. A hiba addig rejtőzik, amíg valaki be nem tölt egy PDF-et, amelyet inkrementálisan szerkesztettek, egy másik eszköz átszervezett, vagy olyan szoftver generált, amely más elrendezést választott

A kizárólag saját generálású PDF-eken végzett tesztelés teljesen kihagyja ezt a probléma osztályt (class of problem). Egy oldal sorrend regresszió (page ordering regression) javításához ezért különböző forrásokból származó dokumentumok (corpus of documents) szükségesek: inkrementális mentések, beillesztett fedőlapokkal rendelkező beolvasott dokumentumok, valamint olyan eszközök által készített PDF-ek, amelyek másképp linearizálják vagy optimalizálják az objektum gráfot (object graph). Egy dokumentumnak, amely kiváltotta az eredeti hibát, tartósan a regressziós csomagban (regression suite) kell maradnia

A HotPDF Component oldala lefedi a teljes API-t az oldal műveletekhez (page operations), beleértve a CopyPageFromDocument, az InsertPagesFromDocument és a MovePage függvényeket