Σφάλματα Σειράς Σελίδων PDF στο HotPDF: Φυσική εναντίον Λογικής Δομής

Το σύμπτωμα εμφανίστηκε σε ένα βοηθητικό πρόγραμμα αντιγραφής σελίδων που κατασκευάστηκε πάνω στο HotPDF Component: ζητώντας τη σελίδα 1 ενός εγγράφου τριών σελίδων, παρήγαγε σταθερά τη σελίδα 2. Ο έλεγχος της λογικής δεικτοδότησης (indexing) δεν βρήκε τίποτα λάθος. Η κλήση χρησιμοποιούσε έναν λογικό δείκτη με βάση το 0, η αριθμητική ήταν σωστή, οι οριακές συνθήκες ήταν εντάξει. Ωστόσο, η λάθος σελίδα έβγαινε κάθε φορά

Το σφάλμα (bug) δεν ήταν καθόλου στον κώδικα αντιγραφής. Ήταν στον τρόπο με τον οποίο το HotPDF κατασκεύαζε τον εσωτερικό του πίνακα σελίδων κατά τη φόρτωση του αρχείου

Δύο ταξινομήσεις, μία πηγή σύγχυσης

Ένα αρχείο PDF είναι μια συλλογή από έμμεσα (indirect) αντικείμενα, το καθένα προσδιορίζεται από έναν αριθμό αντικειμένου. Η δομή του αρχείου δεν επιβάλλει καμία υποχρέωση σε αυτούς τους αριθμούς να αντικατοπτρίζουν τη σειρά ανάγνωσης. Το Αντικείμενο 1 μπορεί να περιέχει τη σελίδα 2. Το Αντικείμενο 20 μπορεί να περιέχει τη σελίδα 1. Αυτό που πραγματικά ορίζει τη σειρά ανάγνωσης είναι το page tree: μια ιεραρχία λεξικών /Pages των οποίων οι πίνακες /Kids παραθέτουν τις αναφορές σελίδων με τη σειρά που ένα πρόγραμμα προβολής (viewer) θα πρέπει να τις εμφανίζει (ISO 32000-1 §7.7.3)

Το έγγραφο που προκάλεσε το σφάλμα είχε αυτήν τη δομή page tree:

{ ρίζα του δέντρου Pages, αντικείμενο 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { λογική σελίδα 1 }
         1 0 R    { λογική σελίδα 2 }
         4 0 R]   { λογική σελίδα 3 }
>>
endobj

Το αρχείο έτυχε να παραθέτει το αντικείμενο 1 και το αντικείμενο 4 πριν από το αντικείμενο 20 στο byte stream. Οποιοσδήποτε αναλυτής (parser) που επαναλάμβανε (iterated) τα έμμεσα αντικείμενα με τη σειρά του αρχείου και τα τοποθετούσε σε ένα PageArr καθώς έβρισκε λεξικά τύπου σελίδας θα κατέληγε με το αντικείμενο 1 στο ευρετήριο 0, το αντικείμενο 4 στο ευρετήριο 1 και το αντικείμενο 20 στο ευρετήριο 2. Η λογική σελίδα 1 βρίσκεται στο PageArr[2]. Το να ζητήσετε το ευρετήριο σελίδας 0 φέρνει αντ' αυτού τη λογική σελίδα 2

Αυτό ακριβώς έκαναν και οι δύο εσωτερικές διαδρομές ανάλυσης (parsing paths) του HotPDF. Η παραδοσιακή διαδρομή, που χρησιμοποιείται για αρχεία PDF 1.3/1.4, και η σύγχρονη διαδρομή, που χρησιμοποιείται για έγγραφα object-stream (PDF 1.5+), η καθεμία κατασκεύαζε το PageArr διασχίζοντας τα έμμεσα αντικείμενα με τη φυσική σειρά του αρχείου αντί να ακολουθεί την αλυσίδα /Kids

Επιβεβαιώνοντας την υπόθεση

Πριν αγγίξουμε οποιαδήποτε διόρθωση, η αναντιστοιχία έπρεπε να αποδειχθεί αντί να υποτεθεί. Το εργαλείο γραμμής εντολών qpdf το καθιστά απλό:

{ κέλυφος (shell) }
qpdf --show-pages input.pdf
{ Η έξοδος αποκαλύπτει τη σειρά Kids: 20 0 R, μετά 1 0 R, μετά 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Δείχνει το λεξικό Pages με το /Kids σε σειρά ανάγνωσης }

Η εξαγωγή κάθε σελίδας ξεχωριστά και ο έλεγχος των μεγεθών των αρχείων επιβεβαίωσαν τη χαρτογράφηση: αυτό που παρήγαγε το PageArr[0] ήταν το περιεχόμενο που ανήκε στη λογική σελίδα 2, και το PageArr[2] περιείχε τη λογική σελίδα 1. Η κυκλική μετατόπιση (circular shift) ήταν η αδιάσειστη απόδειξη (smoking gun). Αυτό εξηγούσε επίσης γιατί το πρόβλημα εμφανιζόταν σε πολλά διαφορετικά έγγραφα προέλευσης: οποιοδήποτε PDF όπου τα αντικείμενα σελίδας έτυχε να έχουν μικρότερους αριθμούς αντικειμένου από μια προγενέστερη λογική σελίδα θα το προκαλούσε

Υπάρχει ένας απλός λόγος για τον οποίο τα PDF καταλήγουν σε αυτήν την κατάσταση. Οι αυξητικές αποθηκεύσεις (incremental saves) προσαρτούν τα ενημερωμένα αντικείμενα με νέους αριθμούς αντικειμένων, αφήνοντας τις παλιές θέσεις στον πίνακα cross-reference να δείχνουν στο πουθενά. Οι editors που προσθέτουν μια σελίδα εξωφύλλου την εισάγουν με υψηλό αριθμό αντικειμένου, ανεξάρτητα από τη θέση της στον πίνακα Kids. Ορισμένες γεννήτριες (generators) απλώς γράφουν σελίδες με μια σειρά που είναι βολική για τη ροή περιεχομένου (content streaming) και όχι με τη λογική ακολουθία σελίδων. Η μορφή PDF δεν απαιτεί από αυτούς να κάνουν διαφορετικά

Η διόρθωση: ακολουθήστε τον πίνακα Kids

Η σωστή προσέγγιση είναι να κατασκευάσετε το PageArr διασχίζοντας την αλυσίδα /Kids από τη ρίζα (root) του catalog, και όχι σαρώνοντας έμμεσα αντικείμενα. Αφού και οι δύο διαδρομές ανάλυσης ολοκληρώσουν το αρχικό τους πέρασμα, ένα βήμα μετεπεξεργασίας (post-processing) επιλύει τη λογική σειρά:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Εντοπισμός του λεξικού ρίζας /Pages μέσω του 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;
    { Τα Kids που δεν είναι σελίδες (ενδιάμεσοι κόμβοι /Pages) δεν παράγουν καμία αντιστοιχία. παράλειψη }
  end;

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

Η κλήση μπαίνει στο τέλος κάθε διαδρομής ανάλυσης, αφού όλα τα αντικείμενα έχουν καταχωρηθεί (catalogued), αλλά πριν εξυπηρετηθεί οποιαδήποτε λειτουργία σελίδας:

{ Παραδοσιακή διαδρομή }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Σύγχρονη διαδρομή (object streams) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

Το βήμα αναδιάταξης είναι O(n * m) όπου n είναι το πλήθος Kids και m είναι το τρέχον μήκος του PageArr, αλλά για οποιοδήποτε έγγραφο με ένα επίπεδο (flat) page tree (όλα τα φύλλα (leaves) σε βάθος 1, το οποίο καλύπτει τη συντριπτική πλειοψηφία των πραγματικών PDF) και τα δύο έχουν την ίδια τιμή και το κόστος είναι αμελητέο. Τα βαθιά ένθετα page trees απαιτούν έναν αναδρομικό περίπατο (recursive walk) αντί της προσέγγισης ενός επιπέδου που φαίνεται εδώ. Η υλοποίηση παραγωγής χειρίζεται αυτήν την περίπτωση ξεχωριστά

Χρησιμοποιώντας το CopyPageFromDocument μετά τη διόρθωση

Με το ReorderPageArrByPagesTree στη θέση του, οι λογικοί δείκτες σελίδας λειτουργούν όπως αναμένεται. Το CopyPageFromDocument υψηλότερου επιπέδου παίρνει έναν λογικό δείκτη με βάση το 0 και αντιγράφει τη σωστή σελίδα στο έγγραφο προορισμού:

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

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

    { Αντιγραφή λογικής σελίδας 0 (η πρώτη σελίδα που βλέπει ο χρήστης) }
    Dest.CopyPageFromDocument(Source, 0, 0);

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

Το CopyPageFromDocument ερωτά εσωτερικά τη σειρά του page tree αντί να βασίζεται στον ωμό (raw) δείκτη PageArr, επομένως συμπεριφέρεται σωστά ακόμη και σε έγγραφα όπου η φυσική και η λογική σειρά αποκλίνουν. Για ομαδικές λειτουργίες (batch operations), το InsertPagesFromDocument δέχεται έναν πίνακα (array) λογικών δεικτών και τους αντιγράφει με ένα πέρασμα

Τι αποκαλύπτει αυτό για την ανάλυση (parsing) του PDF

Η προδιαγραφή του PDF είναι ρητή: η λογική σειρά σελίδων ορίζεται από τον πίνακα /Kids του page tree, όχι από αριθμούς αντικειμένων ή byte offsets (ISO 32000-1 §7.7.3.2). Οποιοσδήποτε αναλυτής που χρησιμοποιεί διαφορετική ταξινόμηση ως συντόμευση θα παραγάγει σωστά αποτελέσματα στην πλειοψηφία των εγγράφων που βλέπει, επειδή οι περισσότερες γεννήτριες (generators) γράφουν τις σελίδες με τη φυσική σειρά και εκχωρούν διαδοχικούς αριθμούς αντικειμένων. Το σφάλμα (bug) κρύβεται μέχρι κάποιος να φορτώσει ένα PDF που υποβλήθηκε σε αυξητική (incremental) επεξεργασία, αναδιοργανώθηκε από κάποιο άλλο εργαλείο ή δημιουργήθηκε από λογισμικό που επέλεξε διαφορετική διάταξη

Ο έλεγχος (testing) μόνο έναντι PDF που δημιουργούνται από το ίδιο το λογισμικό χάνει εντελώς αυτήν την κατηγορία προβλήματος. Η διόρθωση για μια παλινδρόμηση (regression) στη σειρά των σελίδων επομένως χρειάζεται ένα σώμα εγγράφων από διάφορες πηγές: αυξητικές αποθηκεύσεις (incremental saves), σαρωμένα έγγραφα με σελίδες εξωφύλλου που έχουν εισαχθεί, PDF που παράγονται από εργαλεία που γραμμικοποιούν (linearize) ή βελτιστοποιούν (optimize) το γράφημα αντικειμένων (object graph) διαφορετικά. Ένα έγγραφο που προκάλεσε το αρχικό σφάλμα θα πρέπει να παραμείνει στη σουίτα παλινδρόμησης (regression suite) μόνιμα

Η σελίδα HotPDF Component καλύπτει το πλήρες API για λειτουργίες σελίδων, συμπεριλαμβανομένων των CopyPageFromDocument, InsertPagesFromDocument, και MovePage