Ο αριθμός αντικειμένου 1 δεν είναι η σελίδα 1. Αυτό το μεμονωμένο γεγονός μπερδεύει περισσότερο κώδικα επεξεργασίας PDF από οποιαδήποτε άλλη πτυχή της μορφής, και για να καταλάβετε γιατί, απαιτείται να κοιτάξετε πέρα από αυτό που σας δείχνει ένα πρόγραμμα προβολής και να μπείτε στο γράφημα αντικειμένων που πραγματικά διαβάζει το πρόγραμμα προβολής
Ένα αρχείο PDF είναι μια συλλογή από αριθμημένα έμμεσα αντικείμενα. Οι σελίδες είναι ανάμεσα σε αυτά τα αντικείμενα, αλλά η ακολουθία εμφάνισής τους δεν έχει καμία σχέση με το πού βρίσκονται στο αρχείο ή ποιους αριθμούς φέρουν. Η σειρά εμφάνισης καθορίζεται εξ ολοκλήρου από το δέντρο /Pages, μια συνδεδεμένη δομή ριζωμένη στον κατάλογο (catalog) του εγγράφου. Εάν αγνοήσετε το δέντρο και σαρώσετε τα αντικείμενα αριθμητικά, θα συναρμολογήσετε σελίδες με λάθος σειρά για ένα σημαντικό μέρος των αρχείων του πραγματικού κόσμου
Το δέντρο σελίδων: τι πραγματικά καθορίζει τη σειρά
Κάθε PDF ξεκινά με έναν κατάλογο εγγράφων (ISO 32000-2 §7.7.2). Ο κατάλογος διατηρεί μια καταχώριση /Pages που δείχνει στον ριζικό κόμβο του δέντρου σελίδων. Αυτός ο ριζικός κόμβος είναι ένα λεξικό με /Type /Pages, έναν πίνακα /Kids από έμμεσες αναφορές (indirect references) και ένα /Count που δίνει το συνολικό πλήθος των σελίδων-φύλλων κάτω από αυτό. Η σειρά εμφάνισης είναι η "κατά βάθος, από αριστερά προς τα δεξιά" (depth-first left-to-right) διάσχιση αυτού του δέντρου, τελεία και παύλα
Ένα ελάχιστο αρχείο τριών σελίδων το κάνει αυτό συγκεκριμένο:
%PDF-1.7
1 0 obj
<< /Type /Catalog /Pages 2 0 R >>
endobj
2 0 obj
<< /Type /Pages /Kids [20 0 R 4 0 R 9 0 R] /Count 3 >>
endobj
% Object 4 is stored third in the file but is page 2 in display order
4 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
/Contents 5 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj
% Object 9 is stored fourth but is page 3
9 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
/Contents 10 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj
% Object 20 is stored last but is page 1; Kids[0] decides, not object number
20 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
/Contents 21 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj
Ο πίνακας /Kids διαβάζει [20 0 R 4 0 R 9 0 R], επομένως το αντικείμενο 20 είναι η σελίδα 1, το αντικείμενο 4 είναι η σελίδα 2 και το αντικείμενο 9 είναι η σελίδα 3. Η αρίθμηση των αντικειμένων είναι άσχετη. Κάθε κώδικας που επαναλαμβάνει τα αντικείμενα με αριθμητική σειρά και συλλέγει αυτά με /Type /Page θα παραγάγει λανθασμένη ακολουθία σε αυτό το αρχείο
Γιατί οι γεννήτριες (generators) παράγουν μη διαδοχικές διατάξεις; Για διάφορους λόγους. Μια βιβλιοθήκη που προεκχωρεί (pre-allocates) αριθμούς αντικειμένων για όλες τις σελίδες πριν γράψει το περιεχόμενό τους, θα τους αριθμήσει με σειρά δημιουργίας, και στη συνέχεια θα γράψει πραγματικά byte με όποια σειρά ταιριάζει στον σειριοποιητή (serializer). Ένα εργαλείο συγχώνευσης που ράβει έγγραφα μεταξύ τους επαναριθμεί αντικείμενα από κάθε έγγραφο προέλευσης για να αποφύγει συγκρούσεις· τα επαναριθμημένα αντικείμενα σελίδας καταλήγουν διάσπαρτα στον συνδυασμένο πίνακα αντικειμένων ενώ ο νέος ριζικός πίνακας /Kids διατηρεί τη σωστή ακολουθία εμφάνισης. Οι σταδιακές ενημερώσεις προσαρτούν νέα αντικείμενα στο τέλος του αρχείου με νέους αριθμούς, επομένως μια σελίδα που προστίθεται ως αναθεώρηση ζει κοντά στο τέλος της ροής byte ακόμα κι αν ανήκει στη θέση 1 της σειράς εμφάνισης
Επίπεδα δέντρα και ένθετα υποδέντρα
Η προδιαγραφή επιτρέπει δύο σχήματα για το δέντρο σελίδων. Οι απλές γεννήτριες παράγουν μια επίπεδη δομή: έναν ριζικό κόμβο /Pages του οποίου ο πίνακας /Kids δεν περιέχει τίποτα άλλο εκτός από αντικείμενα-φύλλα /Page. Αυτό είναι εύκολο να διασχιστεί: βάθος ενός επιπέδου, ένα πέρασμα
Τα μεγάλα έγγραφα χρησιμοποιούν συστηματικά ένα ισορροπημένο δέντρο αντί αυτού. Ο πίνακας /Kids του ριζικού κόμβου /Pages περιέχει ενδιάμεσους κόμβους /Pages, καθένας από τους οποίους με τη σειρά του διατηρεί τον δικό του πίνακα /Kids. Το /Count σε κάθε ενδιάμεσο κόμβο αναφέρει τον συνολικό αριθμό των σελίδων-φύλλων στο υποδέντρο του, ώστε ένας αναγνώστης να μπορεί να παραλείψει ολόκληρα υποδέντρα όταν πηδά σε μια σελίδα ανά ευρετήριο (by index) χωρίς να αναλύσει κάθε αντικείμενο. Ένα έγγραφο 1000 σελίδων δομημένο ως ένα ισορροπημένο δέντρο με 10 σελίδες ανά κόμβο-φύλλο μπορεί να εντοπίσει τη σελίδα 750 με δυαδική αναζήτηση μέσα από τρεις ή τέσσερις αναζητήσεις στο λεξικό (dictionary lookups) αντί να σαρώσει 750 καταχωρίσεις /Kids
Η συνέπεια για τον κώδικα επεξεργασίας: δεν μπορείτε να υποθέσετε ότι το πρώτο επίπεδο του /Kids περιέχει αντικείμενα /Page. Κάθε παιδί πρέπει να ελεγχθεί. Εάν ο /Type του είναι /Pages, επαναλάβετε την αναδρομή (recurse) σε αυτό. Εάν ο /Type του είναι /Page, είναι ένα φύλλο. Η διακοπή στο πρώτο επίπεδο παραλείπει σιωπηλά ολόκληρα υποδέντρα σε οποιοδήποτε έγγραφο όπου η γεννήτρια επέλεξε να τα ενθέσει
Κληρονομημένα χαρακτηριστικά σελίδας
Το δέντρο σελίδων φέρει επίσης έναν μηχανισμό κοινής χρήσης πόρων (resource-sharing). Ορισμένα χαρακτηριστικά σελίδας: τα /MediaBox, /CropBox, /Resources, και /Rotate είναι κληρονομήσιμα (ISO 32000-2 §7.7.3.4). Εάν ένα λεξικό /Page παραλείψει ένα από αυτά, ένας αναγνώστης ανεβαίνει την αλυσίδα /Parent (γονέας) μέχρι να βρει το χαρακτηριστικό ή να φτάσει στη ρίζα. Η τοποθέτηση ενός κοινόχρηστου λεξικού γραμματοσειράς στον ριζικό κόμβο /Pages αντί της αντιγραφής του σε κάθε σελίδα-φύλλο μπορεί να μειώσει αισθητά το μέγεθος του αρχείου για έγγραφα που χρησιμοποιούν τις ίδιες γραμματοσειρές σε όλη τους την έκταση
Ο κανόνας κληρονομικότητας δημιουργεί μια λεπτότητα για τον κώδικα που διαβάζει τις ιδιότητες της σελίδας. Η άμεση ανάγνωση του /MediaBox από ένα αντικείμενο /Page και η αντιμετώπιση ενός κλειδιού που λείπει ως σφάλμα είναι λάθος· το κλειδί μπορεί απλώς να κληρονομηθεί. Ο κώδικας που επιλύει σωστά τη γεωμετρία της σελίδας πρέπει να ακολουθεί την γονική αλυσίδα. Χρειάζεται επίσης μια προστασία κύκλου (cycle guard): ένα κατεστραμμένο αρχείο μπορεί να έχει μια αναφορά /Parent που δείχνει πίσω σε έναν κόμβο που έχει ήδη επισκεφτεί, πράγμα που θα οδηγούσε σε έναν ατέρμονο βρόχο χωρίς έναν έλεγχο για αντικείμενα που έχουν ήδη ελεγχθεί
Ο πίνακας xref και οι ροές διασταυρούμενων αναφορών
Η αναζήτηση έμμεσων αντικειμένων περνάει μέσα από τον πίνακα διασταυρούμενων αναφορών (ή τον διάδοχό του, τη ροή διασταυρούμενων αναφορών που εισήχθη στο PDF 1.5). Το xref αντιστοιχίζει κάθε αριθμό αντικειμένου σε μια μετατόπιση byte (byte offset) μέσα στο αρχείο. Ένας συμβατός αναγνώστης χρησιμοποιεί το xref για να μεταβεί απευθείας σε οποιοδήποτε αντικείμενο· δεν σαρώνει το αρχείο διαδοχικά. Αυτός ο σχεδιασμός τυχαίας πρόσβασης (random-access) είναι που καθιστά δυνατή τη γρήγορη μετάβαση σελίδων: το πρόγραμμα προβολής διαβάζει τον κατάλογο, επιλύει την αναφορά /Pages μέσω του xref, διαβάζει τον ριζικό κόμβο /Pages, επιλύει μια καταχώριση /Kids κ.ο.κ., αγγίζοντας μόνο τα αντικείμενα που χρειάζεται
Οι σταδιακές ενημερώσεις προσθέτουν μια νέα ενότητα xref στο τέλος του αρχείου με ένα τρέιλερ που αλυσοδένεται με την προηγούμενη. Ένα αντικείμενο που ενημερώνεται σε μια αναθεώρηση αποκτά μια νέα καταχώριση στην προσαρτημένη ενότητα xref· τα αρχικά byte παραμένουν στη θέση τους αλλά αντικαθίστανται. Έτσι παραμένουν επαληθεύσιμα τα ψηφιακά υπογεγραμμένα PDF ακόμη και μετά την προσθήκη αναθεωρήσεων σχολίων ή συμπλήρωσης φόρμας: το υπογεγραμμένο εύρος byte δεν αγγίζεται ποτέ, και το νέο περιεχόμενο ζει στην προσαρτημένη ενότητα. Το δέντρο σελίδων μπορεί επίσης να ενημερωθεί, επομένως οι προσθήκες ή διαγραφές σελίδων σε μια αναθεώρηση παράγουν μια νέα ρίζα /Pages με έναν αναθεωρημένο πίνακα /Kids, ενώ το παλιό ριζικό αντικείμενο εξακολουθεί να καταλαμβάνει την αρχική του θέση στο αρχείο
Τι πάει στραβά χωρίς τη διάσχιση του δέντρου
Η λειτουργία αποτυχίας για προσεγγίσεις σάρωσης αντικειμένων (object-scan) είναι αθόρυβη. Το έγγραφο εξόδου φαίνεται εύλογο: έχει τον σωστό αριθμό σελίδων και κάθε σελίδα περιέχει αναγνωρίσιμο περιεχόμενο. Η σειρά είναι απλά λάθος, και είναι λάθος με τρόπο που εξαρτάται από τη γεννήτρια, τον αριθμό των αναθεωρήσεων, και εάν κάποιες σελίδες συγχωνεύτηκαν από εξωτερικές πηγές. Ένα σώμα (corpus) δοκιμαστικών αρχείων που παρήχθησαν από ένα μεμονωμένο εργαλείο μπορεί να περάσει εντελώς (pass)· τα αρχεία από ένα διαφορετικό εργαλείο ή μια ροή εργασίας συγχώνευσης θα αποτύχουν. Αυτή η ασυνέπεια είναι ο λόγος για τον οποίο οι ευρετικές (heuristic) διορθώσεις δεν αντέχουν ποτέ στον χρόνο
Τα αρχεία σταδιακής ενημέρωσης είναι ιδιαίτερα επιρρεπή σε αυτό, επειδή οι σελίδες που προστέθηκαν ή αναδιατάχθηκαν σε μεταγενέστερες αναθεωρήσεις φέρουν υψηλούς αριθμούς αντικειμένων, ενώ η σειρά εμφάνισης ελέγχεται από τον ενημερωμένο πίνακα /Kids. Μια σάρωση που επεξεργάζεται τα αντικείμενα με αριθμητική σειρά θα τοποθετήσει αυτές τις σελίδες με καθυστερημένη αρίθμηση στο τέλος, ανεξάρτητα από το πού λέει το δέντρο ότι ανήκουν
Η διόρθωση δεν είναι περίπλοκη. Ξεκινήστε από τον κατάλογο, επιλύστε την αναφορά /Pages, διασχίστε τον πίνακα /Kids αναδρομικά, και εκπέμψτε τα φύλλα με τη σειρά που τα συναντάτε. Αυτή είναι η σειρά εμφάνισης εξ ορισμού, ανεξάρτητα από τους αριθμούς αντικειμένων, τις μετατοπίσεις byte ή τη δομή του αρχείου. Οι περισσότερες ώριμες βιβλιοθήκες PDF εκθέτουν έναν αριθμό σελίδων και έναν δείκτη πρόσβασης (accessor) στη σελίδα που ήδη το κάνουν αυτό σωστά· ο κίνδυνος βρίσκεται στον κώδικα που παρακάμπτει το μοντέλο σελίδας της βιβλιοθήκης και αγγίζει απευθείας το επίπεδο του αντικειμένου
Μια δομική ανωμαλία που αξίζει να αντιμετωπιστεί ρητά: η τιμή /Count σε έναν ενδιάμεσο κόμβο /Pages μπορεί να είναι λάθος σε κακοσχηματισμένα (malformed) αρχεία. Εάν εμπιστευτείτε το /Count για τον έλεγχο ορίων (bounds checking) και στη συνέχεια σταματήσετε λίγο πριν από την πλήρη διάσχιση, θα παραλείψετε σιωπηλά σελίδες όταν ο αριθμός είναι υποτιμημένος (understated). Η χρήση του /Count μόνο ως ένδειξη απόδοσης για προεκχώρηση χωρητικότητας ή δυαδική αναζήτηση, και η εξαγωγή του πραγματικού αριθμού από τη διάσχιση είναι το ασφαλέστερο μοτίβο για σημαντικά έγγραφα