PDF-sivujärjestyksen (Page Order) bugit (Bugs) HotPDF:ssä: Fyysinen (Physical) vs (vs) looginen (Logical) rakenne (Structure)

Oire (symptom) ilmeni (showed up in) sivujen kopiointiohjelmassa (page-copying utility built on top of), joka (utility built on top of) oli (built on top of) rakennettu (built on top of) HotPDF Componentin päälle: pyytämällä kolmisivuisen (three-page) asiakirjan sivua 1 tuotettiin jatkuvasti (consistently produced) sivu 2. Indeksointilogiikan (indexing logic found nothing wrong) tarkistaminen ei paljastanut mitään vikaa (found nothing wrong). Kutsu (call was using a) käytti (using a) nollapohjaista loogista (0-based logical index) indeksiä (index), aritmetiikka oli oikein, ja (and) reunaehdot (boundary conditions were fine) olivat (were) kunnossa (fine). Silti väärä (wrong) sivu tuli (came out) ulos (out) joka kerta (every time)

Bugi ei (bug was not in the) ollut lainkaan (at all) kopiointikoodissa (copying code at all). Se oli siinä (in how HotPDF was building its), kuinka HotPDF rakensi (was building its) sisäistä (internal page array when) sivutaulukkoaan (page array when) ladatessaan (when loading the file) tiedostoa (file)

Kaksi järjestystä, yksi sekaannuksen (confusion) lähde (source of)

PDF-tiedosto (PDF file) on (is a) kokoelma (collection of) epäsuoria objekteja (indirect objects, each identified by an), joista jokainen tunnistetaan (identified by an) objektinumerolla (object number). Tiedostorakenne (file structure imposes no obligation on those) ei aseta (imposes no obligation on those) noille numeroille (numbers to reflect reading) mitään (no obligation on those numbers to reflect reading) velvollisuutta (obligation on those) heijastaa (reflect reading) lukujärjestystä (reading order). Objekti (Object 1 can hold) 1 voi pitää sisällään sivun (page 2) 2; objekti 20 voi pitää sisällään sivun (page 1) 1. Se, mikä todella määrittää lukujärjestyksen, on sivupuu (page tree): /Pages -sanakirjojen (dictionaries whose) hierarkia, joiden (whose) /Kids-taulukot (arrays list page references in the sequence a) luettelevat sivuviittaukset siinä (in the) järjestyksessä (sequence a), jossa katseluohjelman tulisi näyttää (should display them) ne (them) (ISO 32000-1 §7.7.3)

Bugin laukaisseella (triggering the bug) asiakirjalla oli (had this page tree structure) tällainen (this) sivupuun rakenne (page tree structure):

{ Pages-puun (Pages tree root, object) juuri (root, object), objekti 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { looginen (logical page) sivu 1 }
         1 0 R    { looginen sivu (logical page) 2 }
         4 0 R]   { looginen (logical page) sivu 3 }
>>
endobj

Tiedosto (file) sattui (happened to list object) luettelemaan (list) objektin (object 1 and object) 1 ja (and) objektin (object) 4 ennen (before) objektia 20 tavuvirrassa (byte stream). Mikä (Any) tahansa (Any parser that iterated through indirect) jäsennin (parser that), joka kävisi epäsuoria (indirect) objekteja läpi (iterated through) tiedoston (file order and stamped them into a) järjestyksessä ja löisi (stamped them into a) ne PageArr-taulukkoon sitä (as it found page-type) mukaa kun (as it found) se löytäisi sivutyyppisiä (page-type dictionaries would end up with) sanakirjoja (dictionaries would end up with), päätyisi tilanteeseen, jossa (would end up with) objekti (object 1 at index) 1 on (at index) indeksissä (index) 0, objekti 4 indeksissä 1 ja objekti 20 indeksissä 2. Looginen (Logical) sivu 1 istuu kohdassa (sits at) PageArr[2]. Sivuindeksin (Asking for page index) 0 pyytäminen (Asking for page index) hakeekin (fetches) sen sijaan (instead) loogisen sivun 2

Tätä (That is exactly what both of) täsmälleen molemmat HotPDF:n (HotPDF's internal parsing paths were doing) sisäiset jäsennysreitit (parsing paths) tekivät (were doing). Perinteinen reitti (traditional path, used for), jota käytetään (used for) PDF 1.3/1.4 -tiedostoissa, ja moderni (modern) reitti, jota käytetään objektivirta-asiakirjoissa (object-stream documents) (PDF 1.5+), rakensivat (each built) kumpikin PageArr-taulukon käymällä epäsuoria objekteja (indirect objects in) läpi fyysisessä tiedostojärjestyksessä (physical file order rather than following the) sen sijaan (rather than following the), että (that) ne olisivat seuranneet /Kids-ketjua

Hypoteesin vahvistaminen (Confirming the)

Ennen minkään (touching any fix) korjauksen koskemista (touching any), epäsuhta piti todistaa (proven rather than assumed) olettamisen sijaan (rather than assumed). qpdf-komentorivityökalu (command-line tool makes this straightforward) tekee tästä (this straightforward) suoraviivaista:

{ komentotulkki (shell) }
qpdf --show-pages input.pdf
{ Tuloste (Output reveals) paljastaa (reveals) Kids-järjestyksen: 20 0 R, sitten (then) 1 0 R, sitten (then) 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Näyttää Pages-sanakirjan (Shows the Pages dictionary with), jossa /Kids on lukujärjestyksessä }

Jokaisen (Extracting each page individually and checking file sizes confirmed the) sivun erottaminen erikseen ja (and) tiedostokokojen tarkistaminen (checking file sizes) vahvisti (confirmed the) kartoituksen (mapping): se (what) mitä PageArr[0] tuotti (produced was the content belonging to), oli (was the) sisältö (content), joka (that) kuului (belonging to) loogiselle (logical page) sivulle 2, ja PageArr[2] piti (held logical page) sisällään loogisen (logical page) sivun 1. Kiertävä (circular shift was the) siirtymä (shift was the) oli savuava (smoking gun) ase (gun). Tämä (This also explained why the problem appeared across multiple different) selitti myös sen (also explained why the), miksi ongelma ilmeni useissa erilaisissa lähdeasiakirjoissa: mikä (any PDF where page objects happened to have) tahansa PDF, jossa sivuobjekteilla (page objects) sattui (happened to have) olemaan pienemmät (lower object numbers than an) objektinumerot (object numbers) kuin (than an) aikaisemmalla (earlier) loogisella (logical page would trigger it) sivulla, laukaisisi sen (would trigger it)

On (There is a straightforward reason PDFs end up in this state) olemassa suoraviivainen syy siihen, miksi PDF-tiedostot päätyvät tähän tilaan. Inkrementaaliset (Incremental) tallennukset liittävät (append updated) päivitetyt (updated objects with) objektit (objects with) uusilla (new) objektinumeroilla (object numbers), jättäen vanhat (leaving the old slots in the) paikat ristiviittaustaulukossa osoittamaan (pointing nowhere) ei-minnekään (nowhere). Muokkausohjelmat, jotka (that) lisäävät kansilehden, syöttävät (insert it with a high) sen (it) korkealla (high) objektinumerolla riippumatta (regardless of its position in the) sen sijainnista (position in the) Kids-taulukossa. Jotkut generaattorit (generators simply write) kirjoittavat (write) sivut (pages in an order convenient for) yksinkertaisesti (simply) järjestyksessä (order convenient for), joka on kätevä (convenient for) sisällön virtautukselle (content streaming rather than logical), ei loogisessa sivujärjestyksessä. PDF-muoto (format) ei (does not require them to do otherwise) vaadi (require them to do) niitä toimimaan toisin (otherwise)

Korjaus (fix): seuraa Kids-taulukkoa

Oikea tapa on (is to build) rakentaa (build) PageArr käymällä läpi /Kids-ketju hakemiston juuresta (catalog root, not by), ei skannaamalla epäsuoria (indirect objects) objekteja. Kun molemmat (After both parsing paths complete their) jäsennysreitit (parsing paths complete their) ovat suorittaneet (complete their) alkuperäisen (initial pass) läpikulkunsa, jälkikäsittelyvaihe (post-processing step resolves the) ratkaisee (resolves the) loogisen (logical order) järjestyksen:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Paikanna (Locate root /Pages dictionary via) juuren /Pages-sanakirja FRootIndexin kautta (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;
    { Ei-sivu (Non-page Kids) Kids (väli- /Pages-solmut (intermediate /Pages nodes produce no match; skip)) eivät (produce no) tuota (produce) osumaa (match); ohita (skip) }
  end;

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

Kutsu sijoitetaan jokaisen jäsennysreitin (parsing path, after all) loppuun (end of each), sen jälkeen (after) kun (all) kaikki objektit (objects have been catalogued but before any) on (have been) luetteloitu (catalogued), mutta ennen (before any) kuin yhtään sivutoimintoa (page operation is serviced) on palvelettu (serviced):

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

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

Uudelleenjärjestämisvaihe (reorder step is) on O(n * m), missä n on Kids-määrä (count) ja m on nykyisen PageArr-taulukon pituus, mutta mille (but for any document with a flat page tree) tahansa asiakirjalle (document), jolla on (with a flat page tree) litteä sivupuu (kaikki (all leaves at depth 1, which covers the) lehdet (leaves) syvyydellä (depth) 1, mikä (which covers the) kattaa (covers the) ylivoimaisen enemmistön reaalimaailman (overwhelming majority of real-world) PDF-tiedostoista), molemmat ovat sama arvo (same value and the cost is) ja (and the cost is) kustannus (cost) on olematon (negligible). Syvälle sisäkkäiset (Deeply nested page trees require a) sivupuut vaativat rekursiivisen läpikulun (recursive walk rather than the) tässä (here) esitetyn yksitasoisen lähestymistavan (single-level approach shown) sijaan (rather than the); tuotantototeutus käsittelee tämän (that case separately) tapauksen (case) erikseen (separately)

CopyPageFromDocument-funktion käyttö korjauksen (fix) jälkeen

ReorderPageArrByPagesTree-korjauksen ollessa paikallaan, loogiset (logical page indices work as expected) sivuindeksit toimivat (work) odotetusti (expected). Ylemmän (higher-level) tason CopyPageFromDocument ottaa (takes a) nollapohjaisen loogisen indeksin ja kopioi (copies the) oikean (correct page into the) sivun (page) kohdeasiakirjaan (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;

    { Kopioi (Copy logical page) looginen (logical page) sivu 0 (ensimmäinen (first) sivu, jonka (page the) käyttäjä (user) näkee) }
    Dest.CopyPageFromDocument(Source, 0, 0);

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

CopyPageFromDocument kysyy (queries the page tree order rather than) sisäisesti sivupuun järjestystä (page tree order) sen sijaan (rather than relying on the), että (that) se (it) luottaisi (relying on the) raakaan PageArr-indeksiin, joten (so it) se käyttäytyy oikein (correctly even against documents where) jopa sellaisia asiakirjoja vastaan (documents where physical and logical order diverge), joissa (where) fyysinen ja (and) looginen järjestys eroavat (diverge). Erätoimintoja varten (For batch operations, InsertPagesFromDocument accepts an) InsertPagesFromDocument hyväksyy (accepts an) taulukon (array of) loogisia indeksejä (logical indices and) ja kopioi ne yhdellä (one) kertaa (pass)

Mitä tämä paljastaa (reveals about) PDF-jäsennyksestä (parsing)

PDF-määritys on selkeä (explicit): loogisen (logical) sivujärjestyksen määrittää sivupuun (page tree) /Kids-taulukko, eivät (not by) objektinumerot tai (or) tavusiirtymät (byte offsets) (ISO 32000-1 §7.7.3.2). Mikä (Any) tahansa (Any parser that uses a different) jäsennin, joka käyttää erilaista järjestystä oikotienä (shortcut), tuottaa (will produce) oikeita (correct results on the) tuloksia enemmistöllä sen (majority of documents it sees, because most) näkemistä asiakirjoista (documents), koska useimmat generaattorit (most generators write pages in the) kirjoittavat sivut (pages) luonnollisessa järjestyksessä (natural order and assign sequential) ja määrittävät (assign) peräkkäiset objektinumerot (sequential object numbers). Bugi piiloutuu, kunnes (until) joku lataa PDF:n, jota on muokattu (edited) inkrementaalisesti, jonka (which) jokin muu työkalu on järjestänyt (reorganized by another tool, or) uudelleen (reorganized), tai jonka ohjelmisto (software that chose a) on (is) luonut valitsemalla (chose a) erilaisen asettelun

Pelkkä itse (self-generated) luotujen (generated) PDF-tiedostojen testaaminen missaa tämän ongelmaluokan kokonaan (entirely). Sivujärjestysregression (page ordering regression therefore needs a) korjaus (fix for a) vaatiikin (needs a) korpuksen erilaisista (varied) lähteistä (sources) peräisin olevia (from) asiakirjoja (documents): inkrementaalisia tallennuksia (incremental saves, scanned documents with inserted), skannattuja (scanned) asiakirjoja (documents), joihin (with) on (inserted) lisätty kansilehtiä (cover pages), ja PDF-tiedostoja, jotka (PDFs produced by tools that linearize or) on (are) tuotettu työkaluilla, jotka (that) linearisoivat tai optimoivat (optimize the) objektikaavion (object graph) eri tavalla (differently). Asiakirjan (document that triggered the), joka (that) laukaisi (triggered the) alkuperäisen (original) bugin (bug), tulisi pysyä (should stay in the) regressiopaketissa (regression suite) pysyvästi (permanently)

HotPDF Component -sivu (page) kattaa koko API:n sivutoiminnoille (page operations), mukaan (including) lukien CopyPageFromDocument, InsertPagesFromDocument ja MovePage