איסוף גרוסה ב-PDF ב-Delphi: Mark and Sweep

מחיקת עמוד מ-PDF אינה מוחקת את הגופנים, התמונות או זרמי התוכן שלו. losLab PDF Library משחזר את השטח הזה באמצעות אספן מסוג mark-sweep שעובר על גרף האובייקטים קדימה החל מה-roots של ה-trailer, ומסיר כל אובייקט עקיף שאף דבר לא מגיע אליו. הוא רץ בשמירה מלאה (full save), הוא כבוי כברירת מחדל, והוא מחזיר את מספר האובייקטים שהוסרו

מדוע מחיקת עמודי PDF לא מקטינה את הקובץ?

מפני שמחיקת עמוד היא עריכת הפניות (reference edit), לא פעולת אחסון. DeletePages(StartPage, PageCount) מנתק אובייקטי עמוד מעץ העמודים ומתקן את רשומות ה-outline שהצביעו עליהם. מה שהוא לא יכול לעשות הוא להחליט שתוכנית הגופן, זרם התוכן והתמונה XObject ששימשו את אותם עמודים כעת מתים, כי ברגע המחיקה שום דבר בקובץ לא רושם מי עוד אולי מצביע עליהם. אותם אובייקטים נשארים ברשימת אובייקטי המסמך, ושמירה מלאה כותבת את כולם בחזרה. התוצאה היא התלונה שפותחת את רוב שרשורי התמיכה הללו: לקוח מוחק תשעים אחוז מהעמודים, שומר, והקובץ מצטמצם בשני אחוזים בלבד. גרוע מזה, הדליפה מצטברת. טוענים, מוחקים, שומרים, טוענים שוב, מוחקים שוב, שומרים שוב, והקובץ גדל באופן מונוטוני בעוד מספר העמודים יורד. זו בעיה שונה מזו שנפתרת על ידי font subsetting וה-downsampling של תמונות, שמקטינים אובייקטים חיים. כאן האובייקטים אינם גדולים מדי — הם פשוט כבר לא חלק מהמסמך

ה-root set הוא ה-trailer, לא עץ העמודים

לגרף האובייקטים של PDF אין שדה הפניה הפוכה. הפורמט אינו מגדיר reference count ואינו מגדיר רשימת back-pointer, והמפתחות /Parent שכן קיימים שייכים למבנים ספציפיים כמו עץ העמודים, לא לגרף האובייקטים כמכלול. שום דבר באובייקט עקיף לא מספר לך מי מצביע עליו, כך שלשאלה "האם מישהו עדיין משתמש באובייקט 47" יש בדיוק תשובה אחת: לעבור קדימה משורש ידוע ולראות אם מגיעים אליו. זו הסיבה שהאספן ב-losLab PDF Library הוא אספן mark-sweep ולא סכימת refcount

ה-roots מגיעים מה-trailer של הקובץ (ISO 32000-1 §7.5.5). שלושה מפתחות נושאים אותם: /Root, ה-document catalog מ-§7.7.2 שממנו תלויים עץ העמודים, ה-names, ה-outlines, ה-AcroForm וה-metadata; /Info, מילון המידע על המסמך; ו-/Encrypt, מילון ההצפנה. שני המפתחות הנותרים של ה-trailer הם הסחות דעת. /ID הוא מערך של שני byte strings, ו-/Prev הוא byte offset שלם לחלק ה-cross-reference הקודם. אף אחד מהם אינו הפניה עקיפה, כך שאף אחד מהם לא תורם root. losLab PDF Library מכניס לתור את כל מילון ה-trailer במקום שלושה מפתחות בשם, מה שלא עולה דבר ושומר בחיים כל הרחבת trailer פרטית

המעבר עצמו הוא איטרטיבי ולא רקורסיבי. כשהמעבר פוגש הפניה עקיפה הוא רושם רק את מספר האובייקט ואת ה-generation, מסמן את החריץ המתאים ודוחף אותו לתור FIFO במקום לפענח מיד, מה שמשאיר עצי עמודים עמוקים ושרשראות outline ארוכות מחוץ למחסנית הקריאות ומונע פענוח כפול של אותו אובייקט. מילונים ישירים, מערכים ומילוני stream נכנסים לתור שני המוגן על ידי סט "ביקרנו בו", כי מסמכים אמיתיים מכילים מעגלים אמיתיים: /Parent של עמוד מצביע חזרה לצומת עץ העמודים שלו, ופריטי outline משורשרים דרך /Prev ו-/Next בשני הכיוונים. מספרי generation הם חלק מההתאמה, לא קישוט. הפניה נפתרת רק כאשר מספר האובייקט וה-generation שניהם מסכימים; הפניה למספר שקיים ב-generation אחר מטופלת כ-null object שהמפרט מחייב, לעולם לא כקשת חיה

כיצד מפעילים garbage collection בשמירה?

איסוף הגרוסה הוא opt-in ושייך לרשומת אפשרויות השמירה. ברירת המחדל היא False כי האספן הוא מעבר הרסני על גרף האובייקטים ואף ספרייה לא צריכה למחוק אובייקטים בשקט מבלי שהקורא ביקש ממנה לבחון אותם

var
  Pdf: TPDFlib;
  Opt: TPDFlibSaveOptions;
begin
  Pdf := TPDFlib.Create;
  try
    if Pdf.LoadFromFile('report-500pages.pdf', '') <> 1 then
      Exit;
    Pdf.DeletePages(11, 490);          // keep the first ten pages

    FillChar(Opt, SizeOf(Opt), 0);
    Opt.CompressContent := True;
    Opt.CompressFonts := True;
    Opt.OptimizeContentStreams := True;
    Opt.PackObjectStreams := True;
    Opt.GarbageCollect := True;        // drop everything the pages left behind
    Pdf.SaveToFileOptions('report-10pages.pdf', Opt);
  finally
    Pdf.Free;
  end;
end;

שתי נקודות כניסה נוספות מגיעות לאותו אספן. SetGarbageCollect(1) מגדירה את הדגל על המסמך הנבחר כך ש-SaveToFile רגילה מכבדת אותו, ו-GarbageCollectObjects מריצה את המעבר מיידית ומחזירה את מספר האובייקטים העקיפים היתומים שהוסרו. הצורה המיידית היא זו שכדאי להשתמש בה כשרוצים מספר לתעד או לבדוק ב-assert, וכדאי לבדוק אותו, כי ערך שלילי אינו ספירה

var
  Removed: Integer;
begin
  Pdf.DeletePages(11, 490);
  Removed := Pdf.GarbageCollectObjects;
  if Removed < 0 then
    // The graph could not be fully decoded. Nothing was swept and the
    // document is unchanged; save it without GC or reject the input.
    LogWarning('object graph incomplete, GC skipped')
  else
    LogInfo(Format('reclaimed %d orphaned objects', [Removed]));
end;

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

מה שובר אספן PDF נאיבי?

שני פרטים, ושניהם נכשלים בשקט ולא בקול. הראשון הוא object streams. החל מ-PDF 1.5 אובייקט שאינו stream יכול לחיות דחוס בתוך מכולת /ObjStm (§7.5.7), ורשומת ה-cross-reference שלו היא רשומת type 2 שמציינת את המכולה בתוספת אינדקס בתוכה. אובייקט דחוס לכן נגיש רק דרך המכולה שלו. אם מסמנים את החבר אך מנקים את המכולה כי שום דבר לא הפנה אליה כאובייקט מסמך, נוצר קובץ שה-xref שלו מצביע לתוך אובייקט שכבר לא קיים. המכולה היא אחסון מבני, לא נתוני מסמך, ולכן היא לעולם לא מופיעה כקשת בגרף האובייקטים שעוברים עליו. losLab PDF Library מטפל בכך על ידי ניתוק כל חבר דחוס ששרד מהמכולה המקורית שלו לפני שהמכולות נעלמות, ולאחר מכן השמירה אורזת מחדש את השורדים לתוך object streams חדשים. הפרט השני הוא מה בעצם אובייקט stream מפנה אליו. הבייטים אינם חלק מהגרף. זרם תוכן שמצייר טקסט עם /F1 12 Tf מציין גופן לפי שם משאב, ואותו שם נפתר דרך מילון ה-/Resources של העמוד, כך שקשת הנגישות עוברת עמוד → /Resources → /Font → אובייקט הגופן, לעולם לא דרך תוכן ה-stream. ההפניות היחידות שתורם stream מגיעות מהמילון שלו, שבו /Length, /Filter ו-/DecodeParms כולם רשאים להיות עקיפים. אספן שמנתח בייטים של stream בחיפוש אחר הפניות עושה עבודה יקרה לחינם; אספן שמדלג על מילוני stream מאבד את אובייקט ה-length ומשחית את הקובץ

מה קורה למספרי האובייקטים שמשוחררים

הם הופכים לרשומות פנויות, והם לא נעשים שימוש חוזר באותה שמירה. המעבר עובר על רשימת האובייקטים בסדר יורד כך שהמחיקות נשארות יציבות מבחינת אינדקס, בונה מחדש את אינדקס החיפוש פעם אחת בסוף במקום אחרי כל הסרה, ולכל אובייקט שהוסר רושם את המספר ברשימה הפנויה עם ה-generation שלו מוגדל באחד, בדיוק כפי ש-§7.5.4 מציין עבור רשומה שאולי תשמש מחדש בעתיד. generation שכבר עומד על 65535 נשאר שם, ומסמן את המספר הזה כפרוש לצמיתות. מספרי האובייקטים אינם נדחסים (compacted) בכוונה. אחרי איסוף הקובץ שומר על חורים: אובייקט 12 יכול להיות פנוי בעוד 13 ו-14 בשימוש, ו-/Size של ה-trailer עדיין מדווח את המספר הגבוה ביותר פלוס אחד ולא את מספר השורדים בפועל. זה חוקי ונורמלי. מספור מחדש היה חוסך כמה בייטים בטבלת ה-cross-reference והיה מחייב לכתוב מחדש כל הפניה במסמך, וזה סוג השינוי שבשקט פוסל כל דבר שמחזיק מספרי אובייקט מבחוץ. הגודל שמתקבל בחזרה מגיע מגופי האובייקטים, לא מטבלת ה-xref

מתי אסור להריץ את האספן

לעולם לא בעדכון מצטבר (incremental update). האספן מוגבל לשמירות מלאות והדגל פשוט לא נקרא כשהמסמך מתעדכן בהוספה, וזו לא מגבלה שצריך לעקוף. עדכון מצטבר (§7.5.6) משאיר את הבייטים המקוריים ללא שינוי ומוסיף חלק cross-reference חדש המשורשר לקודם דרך /Prev. כל גרסה קודמת עדיין מצביעה על האובייקטים שתמיד הצביעה עליהם, כך שאובייקט שאינו נגיש בגרסה הנוכחית נגיש מאוד בגרסה ישנה יותר. מחיקתו הייתה שוברת כל גרסה חוץ מהאחרונה, והמכניקה של הסיבה לכך מוסברת במאמר על עדכונים מצטברים ושמירות במצב append. אותו היגיון פוסל גם איסוף גרוסה על מסמך חתום, כי הכתיבה המחדש המלאה שמאפשרת את האיסוף היא בעצמה מה שפוסל את החתימה

כדאי גם להיות ברור לגבי מה שהאיסוף אינו. הוא אינו sanitizer. האספן מסיר אובייקטים ששום דבר לא מפנה אליהם; אין לו דעה על כך שהתוכן שלהם היה רגיש, ואובייקט שעדיין מופנה אליו נשאר מה שהיה. אם המטרה היא להפוך מידע לבלתי בר-שחזור ולא להקטין את הקובץ, גרף האובייקטים הוא השכבה הלא נכונה, וredaction ברמת ההוראות וניקוי מסמכים הוא הנכון. השניים דווקא משתלבים היטב באותו סדר: תחילה redact ו-sanitise, ואז לאסוף, כך שהאובייקטים שה-redaction ניתק אכן עוזבים את הקובץ. אותו צימוד קיים גם ב-API של ניקוי משאבים, שבו העברת אפשרות ה-garbage-collect גורמת לניקוי להריץ איסוף לאחר מכן ולדווח על היתומים שהוסרו ב-OrphanObjectsRemoved

הרגל אחרון שכדאי לאמץ. תעדו את ערך ההחזרה של GarbageCollectObjects בכל job אצווה שמבצע את מחיקות העמודים שלכם, וצפו בו לאורך כמה שבועות של מסמכים אמיתיים. אפס בקובץ שרק חתכתם לחצי משמעו שמשהו במעלה הזרם עדיין מחזיק הפניה שלא ציפיתם לה, בדרך כלל רשומת name tree, יעד outline או שדה AcroForm ששרד את העמוד שאליו היה מחובר. האספן הוא הדיבאגר הזול ביותר לנגישות שתמצאו אי פעם, כי הוא עונה על השאלה שפורמט ה-PDF עצמו מסרב לענות עליה

אספן הגרוסה, רשומת אפשרויות השמירה וה-API של ניקוי המשאבים המתוארים כאן הם חלק מ-losLab PDF Library עבור Delphi ו-C++Builder, שדף המוצר שלו נושא את הפניית צינור השמירה המלאה כולל האינטראקציה בין האיסוף, אריזת ה-object-stream וה-linearization