מאמר ההסבר המשלים שלנו על סדר העמודים ב-PDF מסביר את כלל היסוד: סדר התצוגה מגיע מחציית עומק-תחילה, משמאל-לימין, של מערכי /Kids בעץ /Pages, ולעולם לא ממספרי אובייקטים. המאמר הזה בוחן את העץ מזווית אחרת — הצורה שלו. מדוע כותבי PDF בשלים מפיקים היררכיות של צמתי ביניים כאשר מערך שטוח יחיד היה תקף לחלוטין? מה בעצם משתנה כשכלי משטח או בונה מחדש את העץ? ומה קורה כאשר הנהלת החשבונות של /Count, שהופכת את כל המבנה למהיר, מפסיקה לומר את האמת
פיצול (fan-out) הוא החלטת ביצועים
שום דבר לא מחייב כותב לקנן צמתים. מסמך בן 10,000 עמודים עם צומת /Pages שורש יחיד ו-10,000 הפניות עלים במערך /Kids יחיד תואם למפרט. עם זאת, ה-PDF Reference ממליץ על עץ מאוזן למסמכים גדולים, ומחוללים מרכזיים פועלים לפי עצה זו עם fan-out צנוע, בדרך כלל כמה עשרות ילדים לכל צומת ביניים
הסיבה נעוצה במה שקורא חייב לקרוא לפני שהוא יכול להציג משהו. נבחן קפיצה ישירה לעמוד 8,214 באותו קובץ בן 10,000 עמודים. עם עץ שטוח, הקורא חייב תחילה לנתח את צומת השורש, וצומת השורש הזה הוא מערך ענק אחד: בערך שמונה בתים להפניה עקיפה, אובייקט של 80 KB שחייב לעבור טוקניזציה מקצה לקצה לפני שניתן לפתור את הערך 8,213. עם עץ מאוזן בעל fan-out של 32, אותה קפיצה קוראת את השורש, משווה סכומי /Count מצטברים כדי לבחור את הילד הנכון, ויורדת — שלושה או ארבעה מילונים קטנים בסך הכול, כל אחד כמה מאות בתים. זו גישת ה-O(log n) האקראית שהעץ תוכנן לספק, וזו הסיבה המלאה לכך ש-/Count קיים בצמתי ביניים: הוא מאפשר לקורא לדלג על תת-עץ שלם מבלי לפתוח אף אובייקט בתוכו
צורת העץ גם קובעת את עלות העריכה. עדכון מצטבר שמוסיף עמוד אחד חייב לשכתב כל צומת שה-/Kids או ה-/Count שלו השתנה, כלומר את הנתיב מההורה של העלה החדש ועד השורש. בעץ מאוזן, הנתיב הזה הוא חופן מילונים קטנים שמצורפים לקובץ. בעץ שטוח, ה"נתיב" הוא מערך השורש הענק היחיד, המשוכפל במלואו בכל גרסה. חוזה שעובר שלושים מחזורי סקירה והערות עשוי להסתיים בגרירת שלושים עותקים מיושנים של אותו מערך בגודל 80 KB בזרם הבתים שלו
צמתי פנים נושאים תכונות בירושה
צמתי ביניים אינם רק ניתוב. ארבע תכונות העמוד הניתנות לירושה — /Resources, /MediaBox, /CropBox ו-/Rotate — יכולות להיות ממוקמות על כל צומת /Pages, שם הן חלות על כל עלה מתחתיו אלא אם צאצא דורס אותן. כותב שמפיק דוח עם נספח לרוחב יכול לבטא את הפריסה הזו בעץ עצמו:
5 0 obj % שורש המסמך
<< /Type /Pages /Count 6 /Kids [6 0 R 7 0 R] >>
endobj
6 0 obj % גוף הדוח: A4 לאורך, גופן הגוף
<< /Type /Pages /Parent 5 0 R /Count 3
/Kids [30 0 R 31 0 R 32 0 R]
/MediaBox [0 0 595 842]
/Resources << /Font << /F1 8 0 R >> >> >>
endobj
7 0 obj % נספח: A4 לרוחב, מסובב, עם גופן משלו
<< /Type /Pages /Parent 5 0 R /Count 3
/Kids [40 0 R 41 0 R 42 0 R]
/MediaBox [0 0 842 595] /Rotate 90
/Resources << /Font << /F2 9 0 R >> >> >>
endobj
40 0 obj % עמוד הנספח: יורש גודל, סיבוב, גופנים
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobjהאובייקטים 40 עד 42 כמעט ריקים. גודל העמוד, הסיבוב ומשאבי הגופן שלהם כולם מגיעים בירושה מצומת 7, מה שמשמר את הקובץ קומפקטי ותחזוקה-עצמית: הוספת עמוד רביעי תחת צומת הנספח תצא לרוחב באופן אוטומטי
אותו מנגנון יוצר את סכנת ההעברה הקלאסית של עמודים. נניח שכלי מעביר את אובייקט 40 לגוף הדוח על ידי עריכת שני מערכי /Kids והפניית /Parent מחדש לצומת 6. ההעברה תקפה מבחינה מבנית, אך אובייקט 40 כעת יורש את /MediaBox לאורך, ללא סיבוב, ואת הגופן /F1 — בעוד שזרם התוכן שלו עדיין בוחר ב-/F2, שכבר לא נפתר. העמוד מתכווץ, מאבד את הסיבוב, ומאבד את הטקסט שלו בעריכה אחת. לכן קוד סידור מחדש חסין ממחיש את הערכים הפתורים של כל ארבע התכונות הניתנות לירושה על מילון העמוד לפני שינוי ההורה שלו. אם אי פעם גררת עמוד בעורך וראית אותו משנה גודל או כיוון, זהו המנגנון שראית
שיטוח: חוקי, נפוץ, לעיתים יקר
כלים רבים הולכים בכיוון ההפוך. כותבים מינימליים מפיקים עץ ברמה אחת מכיוון שזה פשוט, וכלי מיזוג ופיצול רבים בונים מחדש כל עץ שהם קוראים למערך /Kids שטוח אחד, מכיוון שיצירת מבנה מאוזן היא עבודה נוספת ופלט שטוח תמיד תואם. בנייה מחדש נכונה חייבת לפתור את הירושה במקביל: כל תכונה שעלה ירש חייבת להיות מועתקת לעלה, או להתרומם לשורש החדש אם היא אחידה בכל המסמך — אחרת הפלט משנה את הגיאומטריה בדיוק כפי שקורה במקרה של העברת עמוד
עבור מסמכים טיפוסיים, שיטוח אינו מזיק. הוא כואב בקנה מידה גדול, בשתי הדרכים שכבר תוארו: מערך השורש הופך לאובייקט גדול אחד שכל פתיחה וכל קפיצת עמוד חייבים לנתח במלואו, וכל עריכה מבנית משכתבת אותו כולו. מה ששיטוח לא הורס הוא שיתוף באמצעות הפניות עקיפות — עץ שטוח שבו כל 10,000 העמודים מצביעים על אותו אובייקט מילון /Resources עדיין מבוטל-כפילויות. מה שאבד הוא רק האפשרות להשמיט את הערך מהעמוד ולתת לאב-קדמון לספק אותו
כאשר /Count משקר
/Count הוא הנהלת חשבונות טהורה: הוא חייב להיות שווה למספר עמודי העלים בתת-העץ של הצומת, ושום דבר בפורמט הקובץ לא אוכף זאת. שני דפוסי שחיתות מהווים את רוב הספירות המשקרות שנראות בשטח
הראשון הוא הספירה המיושנת שנותרת מעדכון מצטבר. עורך מוסיף עמוד, שוכתב את ההורה המיידי עם /Kids חדש ו-/Count מעודכן, מצרף את שניהם לקובץ — ולעולם לא נוגע באבות-הקדמונים:
% גרסה מקורית
12 0 obj
<< /Type /Pages /Count 9 /Kids [13 0 R 14 0 R 15 0 R] >>
endobj
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 3
/Kids [50 0 R 51 0 R 52 0 R] >>
endobj
% גרסה מצורפת: עמוד אחד הוכנס לענף האמצעי.
% אובייקט 14 הוחלף; אובייקט 12 לעולם לא נכתב מחדש
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 4
/Kids [50 0 R 51 0 R 90 0 R 52 0 R] >>
endobjהעץ מכיל כעת עשרה עלים, אך השורש עדיין אומר תשעה. קורא שסומך על השורש מדווח תשעה עמודים במונה שלו. קורא שמשתמש בספירות פנימיות כדי לבצע חיפוש בינארי לקפיצת עמוד מחשב אינדקס שגוי לכל עמוד שאחרי נקודת ההוספה. חצייה מלאה מוצאת עשרה. שלוש תשובות שונות, קובץ אחד
הדפוס השני הוא הספירה שלעולם לא יכולה להיות נכונה: שלילית, אפס בצומת מאוכלס, או ענקית באופן אבסורדי. אלה מגיעות מ-fuzzing, מנזק בהעברה, ולעיתים משגיאות אריתמטיות בעורכים. הן מסוכנות במיוחד לקוד שסומך על /Count להקצאה — קביעת גודל מערך מתוך /Count של -3 גורמת במקרה הטוב לשגיאת טווח, ועשיית זאת מתוך /Count של שני מיליארד היא הקצאה שגורמת למניעת שירות. הערך הוא קלט לא מהימן, כמו כל מספר אחר בקובץ
מנתחים מתחלקים לשני מחנות סביב כל זה. צרכנים קפדניים — כלי preflight, מאמתי PDF/A, צינורות ארכיון — משווים את /Count לתוצאת החצייה ודוחים או מסמנים את הקובץ. מציגים אינטראקטיביים כמעט תמיד סלחניים: הם חוצים, נגזרים את הספירה האמיתית, ומתעלמים בשקט מהערך המאוחסן, וזו בדיוק הסיבה שקובץ עם ספירה מיושנת יכול להסתובב שנים ללא תלונה עד שהוא נתקל במנתח קפדני יותר בתוך זרימת עבודה אוטומטית כלשהי. האמצע ההגנתי עבור קוד ספרייה הוא להתייחס אל /Count כרמז — שימושי להקצאה מוקדמת, ולדילוג על תת-עצים לאחר אימות — תוך שהחצייה נשארת מקור האמת
עבור אלגוריתם החצייה עצמו, כללי חיפוש הירושה, וההליכה מהקטלוג ועד העלה, התחל עם מאמר ההסבר על סדר העמודים. כדי לראות איך מצבי הכשל האלה נראים כאשר מסמך אמיתי של לקוח מגיע לקוד ייצור, קרא את מקרה הבוחן של דיבוג סדר העמודים, שעוקב אחר תקרית עמודים מעורבבים מהתסמין ועד הסיבה השורשית
רכיב ה-HotPDF Delphi Component מטפל בכל זה באופן פנימי: הוא חוצה עצים מקוננים בכל עומק, פותר תכונות בירושה כאשר עמודים מועתקים או מועברים, ומאמת את /Count מול ספירת העלים בפועל במקום לסמוך עליו, כך שאינדקסי עמודים ב-API שלו תמיד משמעם עמודים לוגיים