עצי עמודים ב-PDF: מדוע סדר העמודים אינו סדר האובייקטים

עמוד 1 של PDF אינו אובייקט 1. הבחנה זו היא המקור הנפוץ ביותר לבאגים של עמוד-שגוי-שחולץ במנתחי PDF, והתיקון הוא קריאת המפרט במקום בתי הקובץ

אובייקטים, הפניות והקטלוג

קובץ PDF הוא אוסף של אובייקטים ממוספרים. כל אחד מהם נושא מספר אובייקט ייחודי ומספר דור, הכתוב כ-N G obj כאשר G הוא כמעט תמיד 0 בקבצים שלא עודכנו באופן מצטבר. אובייקטים מפנים זה לזה עם הרישום N G R, כך ש-3 0 R משמעו "הגרסה הנוכחית של אובייקט 3." ה-trailer מצביע לאובייקט קטלוג שורש שרשומת ה-/Pages שלו מובילה לעץ העמודים. כל דבר שניתן לנווט בו ב-PDF מתחיל מהשורש הזה, לא מהבית הראשון של גוף הקובץ

טבלת ההצלבה (או זרם ההצלבה ב-PDF 1.5+) ממפה מספרי אובייקטים להיסטים של קובץ. תפקידה הוא גישה אקראית, לא סידור. כותב שבונה מסמך באופן מצטבר יכול לצרף אובייקטים חדשים בסוף עם מספרים גבוהים יותר בעוד שאובייקטים אלה מקדימים לוגית את הקיימים ברצף העמודים. זה לא פגם; זה מכוון

עץ העמודים (ISO 32000-1 §7.7.3)

רצף העמודים חי בעץ העמודים. קטלוג השורש מכיל הפניית /Pages המצביעה לצומת מסוג /Pages. מערך ה-/Kids של צומת זה מפרט את ילדיו בסדר קריאה. כל ילד הוא או צומת עלה מסוג /Page או צומת ביניים /Pages נוסף המכיל /Kids משלו. עמוד 1 הוא העלה הראשון שאליו מגיעים על ידי חציית עומק-תחילה, משמאל-לימין של מערכי ה-Kids. רשומת ה-/Count על כל צומת ביניים מטמינה (caches) את המספר הכולל של עמודי העלים הצאצאים, כך שקורא יכול לקפוץ לעמוד 500 מבלי ללכת לאורך כל העץ

הנה איך נראה עץ מינימלי בן שלושה עמודים בתחביר PDF גולמי:

16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R  1 0 R  4 0 R]
  /MediaBox [0 0 612 792]
>>
endobj

20 0 obj
<< /Type /Page  /Parent 16 0 R  /Contents 21 0 R  /Resources 22 0 R >>
endobj

1 0 obj
<< /Type /Page  /Parent 16 0 R  /Contents 2 0 R   /Resources 3 0 R >>
endobj

4 0 obj
<< /Type /Page  /Parent 16 0 R  /Contents 5 0 R   /Resources 6 0 R >>
endobj

מערך ה-Kids קורא [20 0 R, 1 0 R, 4 0 R]. עמוד לוגי 1 הוא אובייקט 20, עמוד לוגי 2 הוא אובייקט 1, עמוד לוגי 3 הוא אובייקט 4. כל קוד שמעביר מספרי אובייקטים מ-1 ומעלה ייתקל בהם בסדר 1, 4, 20 וייצר את הרצף עמוד-2, עמוד-3, עמוד-1. המסמך שיתקבל מרונדר בסדר מעורבב שיכול להיראות נורמלי לחלוטין בקורא שעוקב אחר העץ, ושגוי באופן קטסטרופלי בכזה שלא

הורשה

צומתי ביניים יכולים לשאת מאפיינים שצאצאיהם יורשים. הרשומות המורשות הנפוצות ביותר הן /MediaBox (ממדי עמוד), /CropBox, /Resources (גופנים ותמונות), ו-/Rotate. עמוד עלה שמשמיט /MediaBox אינו שבור; הוא אוסף את הערך מאב-הקדם (ancestor) הקרוב ביותר שמגדיר אותו. עמוד שכן מגדיר /MediaBox דורס את כל מה שההורה אומר, עבור העמוד הזה בלבד

זה חשוב עבור ניתוח (parsing). קריאת אובייקט /Page בבידוד והנחה שמאפייניו שלמים תדווח באופן שגוי על ממדים עבור כל עמוד המסתמך על הורשה. קורא נכון הולך בשרשרת ה-/Parent, ואוסף מאפיינים שעוד לא ראה, עד שהוא נעצר בשורש

עצים מקוננים

שום דבר במפרט אינו מגביל את העץ לרמה אחת. מסמך גדול עשוי לקבץ עמודים תחת צומתי ביניים שמתאימים באופן רופף לפרקים:

2 0 obj   % צומת Pages שורש, Count = 8
<< /Type /Pages  /Count 8  /Kids [3 0 R  4 0 R] >>
endobj

3 0 obj   % פרק ראשון, 5 עמודים
<< /Type /Pages  /Parent 2 0 R  /Count 5
   /Kids [10 0 R  11 0 R  12 0 R  13 0 R  14 0 R]
   /MediaBox [0 0 612 792] >>
endobj

4 0 obj   % פרק שני, 3 עמודים
<< /Type /Pages  /Parent 2 0 R  /Count 3
   /Kids [20 0 R  21 0 R  22 0 R]
   /MediaBox [0 0 612 792] >>
endobj

אלגוריתם החצייה הוא זהה: בקר ב-Kids לפי הסדר, בצע רקורסיה לכל צומת /Pages, ואסוף צומתי /Page של עלים. ערכי ה-/Count מאפשרים לקורא לדלג על תת-עץ שלם כאשר הוא קופץ לעמוד שנמצא מעבר לו, ולכן הספירות האלה חייבות להיות מדויקות. חלק מעורכי ה-PDF משלהי שנות ה-90 ותחילת שנות ה-2000 לא חישבו אותן מחדש לאחר עריכות במקום (in-place edits), לכן מנתח הגנתי (defensive parser) מאמת את ה-/Count מול ספירת העלים בפועל במקום לסמוך עליו לצורך הקצאת מערך

איפה זה עולה בפועל

באג סדר-העמודים צץ לרוב בשני תרחישים. הראשון הוא מנתח מותאם אישית שסורק עבור אובייקטים מסוג /Page במקום לעקוב אחר העץ. הוא מוצא כל עמוד, אך בסדר של מספרי אובייקטים, לא בסדר קריאה. התיקון הוא תמיד זהה: התחל מה-trailer, פתור את קטלוג השורש, עקוב אחר /Pages, וחצה מערכי Kids

התרחיש השני הוא קובץ עדכון מצטבר. כאשר עורך PDF מצרף שינויים מבלי לשכתב את כל הקובץ, אובייקטי עמוד חדשים מקבלים מספרי אובייקטים גבוהים בעוד שמערך ה-Kids בעץ המקורי עדיין שולט במיקומם הלוגי. עמוד שהיה במקור אובייקט 5 מוחלף באובייקט חדש 143, אך מערך ה-Kids עכשיו מפנה ל-143 היכן שהפנה בעבר ל-5, כך שהסדר הלוגי נשמר. הליכה לפי מספר אובייקט הייתה שמה את העמוד המחליף במיקום הלא נכון ברצף

מסמכי PDF ליניאריים (מותאמים לאינטרנט) מוסיפים וריאציה שלישית: הקובץ מסודר מחדש פיזית כך שתוכן העמוד הראשון מופיע קרוב לתחילת הקובץ לתצוגה מהירה על חיבור איטי. מבנה עץ העמודים נשאר סמכותי לגבי הסדר, אך טבלת ההצלבה ממפה להיסטים המסודרים מחדש. מנתח שמסתמך על מיקום בקובץ במקום על טבלת ה-xref יקרא בצורה שגויה אפילו את העמוד הראשון של קובץ ליניארי

רכיב ה-HotPDF Component מטפל בחציית עץ העמודים, רזולוציית הורשה, ומיזוג xref של עדכונים מצטברים פנימית. עבודה ישירה עם אובייקטי העמודים שלו משמעותה שסידור מערך ה-Kids כבר מיושם; אינדקסי עמודים ממפים לעמודים לוגיים, לא למספרי אובייקטים