באגים של סדר דפי PDF ב-HotPDF: מבנה פיזי לעומת לוגי

התסמין הופיע בכלי שירות להעתקת דפים שנבנה על גבי רכיב HotPDF Component: בקשת דף 1 של מסמך בן שלושה דפים הפיקה בעקביות את דף 2. בדיקת לוגיקת האינדקס לא מצאה שום דבר חריג. הקריאה השתמשה באינדקס לוגי מבוסס 0, האריתמטיקה הייתה נכונה, תנאי הקצה היו בסדר. ובכל זאת הדף השגוי יצא בכל פעם

הבאג כלל לא היה בקוד ההעתקה. הוא היה באופן שבו HotPDF בנה את מערך הדפים הפנימי שלו בעת טעינת הקובץ

שני סדרים, מקור אחד לבלבול

קובץ PDF הוא אוסף של אובייקטים עקיפים (indirect objects), שכל אחד מהם מזוהה על ידי מספר אובייקט. מבנה הקובץ אינו מטיל כל חובה על מספרים אלה לשקף את סדר הקריאה. אובייקט 1 יכול להחזיק את דף 2; אובייקט 20 יכול להחזיק את דף 1. מה שבאמת מגדיר את סדר הקריאה הוא עץ הדפים: היררכיה של מילוני /Pages שמערכי ה-/Kids שלהם רושמים הפניות לדפים ברצף שמציג אמור להציג אותם (ISO 32000-1 §7.7.3)

למסמך שעורר את הבאג היה מבנה עץ הדפים הזה:

{ שורש עץ הדפים, אובייקט 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 בזרם הבתים. כל מנתח (parser) שעבר על אובייקטים עקיפים לפי סדר הקובץ והחתים אותם לתוך PageArr ככל שמצא מילונים מסוג דף, היה מסיים עם אובייקט 1 באינדקס 0, אובייקט 4 באינדקס 1, ואובייקט 20 באינדקס 2. דף לוגי 1 יושב ב-PageArr[2]. בקשה של אינדקס דף 0 מביאה במקום זאת את דף לוגי 2

זה בדיוק מה ששני נתיבי הניתוח הפנימיים של HotPDF עשו. הנתיב המסורתי, המשמש לקובצי PDF 1.3/1.4, והנתיב המודרני, המשמש למסמכי זרם אובייקטים (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. ההזזה המעגלית הייתה האקדח המעשן. זה גם הסביר מדוע הבעיה הופיעה במספר רב של מסמכי מקור שונים: כל PDF שבו אובייקטי דפים היו במקרה בעלי מספרי אובייקט נמוכים יותר מדף לוגי מוקדם יותר, יעורר זאת

יש סיבה פשוטה לכך שקובצי PDF מסיימים במצב זה. שמירות מצטברות (Incremental saves) מצרפות אובייקטים מעודכנים עם מספרי אובייקטים חדשים, ומשאירות את המשבצות הישנות בטבלת ההפניות המקושרות (cross-reference) מצביעות לשום מקום. עורכים שמוסיפים דף שער מכניסים אותו עם מספר אובייקט גבוה ללא קשר למיקומו במערך ה-Kids. חלק מהמחוללים (generators) פשוט כותבים דפים בסדר שנוח להזרמת תוכן במקום ברצף הדפים הלוגי. פורמט ה-PDF אינו דורש מהם לעשות אחרת

התיקון: מעקב אחר מערך ה-Kids

הגישה הנכונה היא לבנות את PageArr על ידי מעבר לאורך שרשרת ה-/Kids משורש הקטלוג, ולא על ידי סריקת אובייקטים עקיפים. לאחר ששני נתיבי הניתוח מסיימים את המעבר הראשוני שלהם, שלב של עיבוד לאחר-מעשה (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;

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

{ נתיב מסורתי }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ נתיב מודרני (זרמי אובייקטים) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

שלב הסידור מחדש הוא O(n * m) כאשר n הוא ספירת ה-Kids ו-m הוא אורך ה-PageArr הנוכחי, אך עבור כל מסמך בעל עץ דפים שטוח (כל העלים בעומק 1, מה שמכסה את הרוב המכריע של קובצי PDF בעולם האמיתי) שניהם בעלי אותו ערך והעלות זניחה. עצי דפים מקוננים עמוקות דורשים מעבר רקורסיבי במקום הגישה החד-שלבית המוצגת כאן; יישום הייצור (production implementation) מטפל במקרה זה בנפרד

שימוש ב-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 מתשאלת באופן פנימי את סדר עץ הדפים במקום להסתמך על אינדקס PageArr הגולמי, כך שהיא מתנהגת כראוי גם מול מסמכים שבהם הסדר הפיזי והלוגי חלוקים זה על זה. עבור פעולות אצווה, InsertPagesFromDocument מקבל מערך של אינדקסים לוגיים ומעתיק אותם במעבר אחד

מה זה חושף על ניתוח PDF

מפרט ה-PDF מפורש: סדר דפים לוגי מוגדר על ידי מערך /Kids של עץ הדפים, לא על ידי מספרי אובייקטים או היסטים של בתים (ISO 32000-1 §7.7.3.2). כל מנתח (parser) שמשתמש בסדר שונה כקיצור דרך יפיק תוצאות נכונות ברוב המסמכים שהוא יראה, מכיוון שרוב המחוללים כותבים דפים בסדר הטבעי ומקצים מספרי אובייקטים ברצף. הבאג מסתתר עד שמישהו טוען PDF שנערך בצורה מצטברת, שארגנו אותו מחדש כלי אחר, או שנוצר על ידי תוכנה שבחרה בפריסה שונה

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

דף רכיב HotPDF Component מכסה את ה-API המלא לפעולות דף, כולל CopyPageFromDocument, InsertPagesFromDocument ו-MovePage