Feil i PDF-siderekkefølge i HotPDF: Fysisk vs logisk struktur

Symptomet dukket opp i et verktøy for sidekopiering bygget oppå HotPDF Component: å be om side 1 fra et tre-siders dokument produserte konsekvent side 2. Ved å sjekke indekseringslogikken fant jeg ingenting galt. Kallet brukte en 0-basert logisk indeks, aritmetikken var riktig, grensebetingelsene (boundary conditions) var i orden. Likevel kom feil side ut hver gang

Feilen lå ikke i kopieringskoden i det hele tatt. Den lå i hvordan HotPDF bygde sin interne side-array under innlasting av filen

To rekkefølger, én kilde til forvirring

En PDF-fil er en samling av indirekte objekter, hver identifisert med et objektnummer. Filstrukturen pålegger ingen forpliktelse om at disse numrene reflekterer leserekkefølgen. Objekt 1 kan inneholde side 2; objekt 20 kan inneholde side 1. Det som faktisk definerer leserekkefølgen er sidetreet: et hierarki av /Pages-ordbøker der /Kids-arrayer lister opp sidereferanser i den sekvensen en seer (viewer) skal vise dem (ISO 32000-1 §7.7.3)

Dokumentet som utløste feilen, hadde denne sidetrestrukturen:

{ 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

Filen hadde tilfeldigvis listet opp objekt 1 og objekt 4 før objekt 20 i bytestrømmen (byte stream). Enhver parser som itererte gjennom indirekte objekter i fil-rekkefølge, og stemplet (stamped) dem inn i en PageArr etter hvert som den fant side-type (page-type) ordbøker, ville ende opp med objekt 1 på indeks 0, objekt 4 på indeks 1, og objekt 20 på indeks 2. Logisk side 1 sitter på PageArr[2]. Å spørre etter side-indeks 0 henter logisk side 2 i stedet

Det er nøyaktig hva begge av HotPDF sine interne parserveier gjorde. Den tradisjonelle banen (the traditional path), brukt for PDF 1.3/1.4-filer, og den moderne banen (modern path), brukt for objektstrøm-dokumenter (PDF 1.5+), bygde hver sin PageArr ved å gå gjennom indirekte objekter i fysisk fil-rekkefølge (file order), i stedet for å følge /Kids-kjeden (chain)

Bekrefte hypotesen

Før man rørte noen retting (fix), måtte avviket bevises snarere enn antas. Kommandolinjeverktøyet qpdf (command-line tool) gjør dette rett frem:

{ 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 }

Å trekke ut hver side individuelt og sjekke filstørrelser bekreftet kartleggingen (the mapping): hva PageArr[0] produserte, var innholdet som tilhørte logisk side 2, og PageArr[2] holdt logisk side 1. Det sirkulære skiftet (the circular shift) var det fellende beviset (smoking gun). Dette forklarte også hvorfor problemet dukket opp på tvers av flere forskjellige kildedokumenter (source documents): enhver PDF der sideobjekter tilfeldigvis hadde lavere objektnumre enn en tidligere logisk side, ville utløse det

Det er en rett frem årsak til at PDF-er ender opp i denne tilstanden. Inkrementelle lagringer legger til (appends) oppdaterte objekter med nye objektnumre, og lar de gamle plassene i kryssreferansetabellen peke ut i ingensteds (nowhere). Redigeringsprogrammer som legger til en forside, setter den inn med et høyt objektnummer uavhengig av dens posisjon i Kids-arrayen. Noen generatorer skriver rett og slett ut sider i en rekkefølge som er praktisk for innholdsstrømming (content streaming) fremfor logisk sidesekvens. PDF-formatet krever ikke at de gjør noe annet

Løsningen: følg Kids-arrayen

Den riktige tilnærmingen er å bygge PageArr ved å gå /Kids-kjeden fra katalog-roten (catalog root), ikke ved å skanne indirekte objekter. Etter at begge parserveiene (parsing paths) har fullført sin innledende gjennomgang, vil et etterbehandlingstrinn (post-processing step) oppløse (resolves) den logiske rekkefølgen:

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;

Kallet legges inn ved slutten av hver parservei (parsing path), etter at alle objekter har blitt katalogisert, men før noen sideoperasjon blir betjent (serviced):

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

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

Omorganiserings-trinnet (the reorder step) er O(n * m) hvor n er Kids-tellingen (the Kids count) og m er gjeldende PageArr-lengde, men for ethvert dokument med et flatt sidetre (alle blader (leaves) på dybde 1, noe som dekker det overveldende flertallet av virkelige (real-world) PDF-er) er begge den samme verdien og kostnaden er neglisjerbar. Dypt nøstede sidetrær krever en rekursiv gangsti (recursive walk) fremfor en-nivå-tilnærmingen vist her; produksjonsimplementasjonen håndterer det tilfellet separat

Bruke CopyPageFromDocument etter rettelsen

Med ReorderPageArrByPagesTree på plass, fungerer logiske sideindekser som forventet. CopyPageFromDocument på et høyere nivå tar en 0-basert logisk indeks og kopierer den riktige siden inn i destinasjonsdokumentet:

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;

CopyPageFromDocument spør internt etter sidetre-rekkefølgen fremfor å stole på den rå PageArr-indeksen, så den oppfører seg korrekt selv mot dokumenter der fysisk og logisk rekkefølge avviker. For batch-operasjoner aksepterer InsertPagesFromDocument en array (liste) med logiske indekser og kopierer dem i én gjennomkjøring (pass)

Hva dette avslører om PDF-parsing

PDF-spesifikasjonen er eksplisitt: logisk siderekkefølge er definert av /Kids-arrayen i sidetreet, ikke av objektnumre eller byte-forskyvninger (byte offsets) (ISO 32000-1 §7.7.3.2). Enhver parser som bruker en annen ordning som en snarvei, vil produsere riktige resultater på majoriteten av dokumenter den ser, fordi de fleste generatorer skriver sider i naturlig rekkefølge og tildeler sekvensielle objektnumre. Feilen gjemmer seg inntil noen laster inn en PDF som ble inkrementelt redigert, omorganisert av et annet verktøy, eller generert av programvare som valgte en annen layout

Testkjøring kun mot selvgenererte PDF-er overser denne klassen av problemer fullstendig. Rettelsen (the fix) for en regresjon (regression) i siderekkefølge trenger derfor et korpus (corpus) av dokumenter fra varierende kilder: inkrementelle lagringer, skannede dokumenter med innsatte forsider, PDF-er produsert av verktøy som lineariserer eller optimerer objektgrafen ulikt. Et dokument som utløste den opprinnelige feilen, bør forbli i regresjonssuiten (regression suite) permanent

HotPDF Component-siden dekker hele API-et for sideoperasjoner, inkludert CopyPageFromDocument, InsertPagesFromDocument, og MovePage