עצי Name ב-PDFlibPas: מעגלים, /Limits פגומים ועלים ענקיים

PDFlibPas, ה-PDF Library for Delphi של losLab, הולכת על עצי Name ועצי number של PDF עם מחסנית מפורשת וקבוצת visited מאז v3.539.45, כך ש-/Kids מעגלי, ילדים משותפים ועצים בעומק אלפי רמות כבר לא מרוקנים את מחסנית הקריאות ולא משכפלים רשומות. מאז v3.539.51 זוג /Limits חסר, פגום או הפוך לעולם לא מסתיר ענף שמחזיק את המפתח. יעדים בעלי שם, תוויות עמודים, קבצים מצורפים ו-JavaScript ברמת מסמך נקראים כולם דרך שני נתיבי הקוד האלה, מה שהופך אותם לחלק ממשטח התקיפה של כל PDF שלא ייצרתם בעצמכם

הטריגר נדיר שהוא אקזוטי. fuzzer, העלאה עוינת או שמירה מצטברת פגומה כותבים רשומת /Kids שמצביעה בחזרה על אב, ו-walker רקורסיבי מת עם stack overflow על קובץ בן שני קילובייטים. הכישלון השקט יותר הוא לוקאפ שסומך על מערך /Limits שבור ומדווח "לא נמצא" עבור יעד שנמצא שם בגלוי

איפה עצי Name ועצי number מופיעים בתוך PDF?

עצי Name ועצי number מופיעים בכל מקום שבו PDF ממפה קבוצה גדולה של מפתחות לאובייקטים, ו-PDFlibPas קוראת לפחות ארבעה מהם דרך APIs ציבוריים. ISO 32000-1 §7.9.6 מגדיר את עץ ה-Name (מפתחות מחרוזת, Table 36) ו-§7.9.7 את עץ ה-number (מפתחות שלמים, Table 37). שניהם עצים בקירוב מאוזנים ששורשם וצמתי הביניים שלהם נושאים /Kids, עליהם נושאים את זוגות המפתח/ערך הממוינים ב-/Names או /Nums, וצמתים שאינם שורש נושאים מערך /Limits בן שני אלמנטים עם המפתח הקטן והגדול ביותר מתחתיהם

עץ	היכן הוא שוכן	מפרט	API קריאה של PDFlibPas
יעדים בעלי שם	/Dests במילון השמות	§12.3.2.3	GetNamedDestination, ואז GetDestPage / GetDestType
תוויות עמודים	/PageLabels בקטלוג (עץ number)	§12.4.2	GetPageLabel
קבצים מצורפים	/EmbeddedFiles במילון השמות	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript ברמת מסמך	/JavaScript במילון השמות	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

שני פרטים בטבלה הזאת קל לפספס. ליעדים בעלי שם יש גם צורה ישנה מ-PDF 1.1, מילון /Dests פשוט בקטלוג עם מפתחות של אובייקטי name, ו-GetNamedDestination בודק את המילון הזה קודם לפני שהוא יורד אל עץ ה-Name של PDF 1.2. ו-GetDocJavaScript בכלל אינו קורא עצי Name: הוא מחזיר את הסקריפטים המחוברים לטריגרי מסמך במילון ה-/AA של הקטלוג (WS, DS, WP, DP, DC), בזמן שחבילות הסקריפט בעלות השם שרצות כשמסמך נפתח חיות בעץ ה-Name של /JavaScript

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

למה מערך /Kids מעגלי מפיל walker רקורסיבי של עץ?

מערך /Kids מעגלי מפיל walker רקורסיבי כי שום דבר ברקורסיה לא שם לב שהוא כבר ראה צומת, ולכן ילד שמפנה אל אביו שלו הופך קובץ סופי לירידה אינסופית. לפני v3.539.45, NameTreeLookup, NumTreeLookup, EnumNumTree ו-TPDFNameTree.ProcessNode הפנימי קראו לעצמם פעם אחת לכל ילד. הפניה עצמית אחת הייתה מספיקה כדי לסיים את התהליך, ועץ לגיטימי אבל עמוק מאוד יכול היה לעשות את אותו הדבר בלי שום מעגל

וריאנט מתון יותר משחית תוצאות במקום לקרוס. כששתי רשומות /Kids מפנות אל אותו עלה, מנייה תמימה מבקרת בו פעמיים, ומניין קבצים מצורפים או רשימת חבילות סקריפט מדווח רשומות שלא קיימות

התיקון מחליף את הרקורסיה במחסנית מפורשת של אחרון-נכנס-ראשון-יוצא על ה-heap ובקבוצת visited שמאונדקסת לפי זהות מילון. צומת מסומן כשהוא נשלף, לא כשהוא נדחף, כך שהפניה מעגלית רשאית לשבת על המחסנית זמן קצר אבל נזרקת ברגע שהיא עולה בחזרה. כל צומת נבדל מרחיב את ילדיו בדיוק פעם אחת, מה שחוסם את העבודה הכוללת במספר המילונים הנבדלים בתוספת האורך הכולל של מערכי ה-/Kids שלהם. עומק מפסיק להיות רלוונטי: שרשרת בת 4,096 רמות היא פשוט 4,096 איטרציות של לולאה ו-4,096 רשומות ב-hash set

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

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // ריק בעלה
    Keys: TArray<string>;      // מפתחות עלה, ממוינים על ידי מפיק מתנהג היטב
    Values: TArray<Integer>;   // מקביל ל-Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// /Limits הוא רמז: רק זוג תקין וממוין רשאי לגזום ענף
function LimitsExclude(Node: TTreeNode; const Key: string): Boolean;
begin
  Result := Node.HasLimits and (Node.LoKey <= Node.HiKey) and
    ((Key < Node.LoKey) or (Key > Node.HiKey));
end;

function FindValue(Root: TTreeNode; const Key: string;
  out Value: Integer): Boolean;
var
  Pending: TList<TTreeNode>;
  Visited: TDictionary<TTreeNode, Byte>;
  Node: TTreeNode;
  I: Integer;
begin
  Result := False;
  Value := 0;
  if Root = nil then
    Exit;
  Pending := TList<TTreeNode>.Create;
  Visited := TDictionary<TTreeNode, Byte>.Create;
  try
    Pending.Add(Root);
    while Pending.Count > 0 do
    begin
      Node := Pending[Pending.Count - 1];
      Pending.Delete(Pending.Count - 1);
      if Visited.ContainsKey(Node) then
        Continue;                      // מעגל או ילד משותף: כבר ראינו
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // דוחפים מימין לשמאל כדי שהילד השמאלי יישלף ראשון
        for I := High(Node.Kids) downto 0 do
          if (Node.Kids[I] <> nil) and not LimitsExclude(Node.Kids[I], Key) then
            Pending.Add(Node.Kids[I]);
      end
      else
        for I := 0 to High(Node.Keys) do
          if (Node.Keys[I] = Key) and (I <= High(Node.Values)) then
          begin
            Value := Node.Values[I];
            Exit(True);
          end;
      // החטאה בעלה הזה אינה פסק דין: ממשיכים לשלוף אחים
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

למה לוקאפ לא יכול לעצור בענף התואם הראשון?

לוקאפ לא יכול לעצור בענף הראשון שהטווח שלו תואם, כי טווחי /Limits בקובץ אמיתי יכולים להתחפף או לשקר, והענף שתובע את המפתח אינו בהכרח הענף שמחזיק אותו. הלוקאפים שלפני v3.539.45 הגדירו דגל Found על הילד הראשון שה-/Limits שלו כיסה את המפתח, ירדו אליו, ולא הביטו עוד באח אחר. אם אותו ילד התברר כריק, מיושן או לולאה חזרה אל השורש, התשובה הייתה nil, גם כשהאח הבא ממש החזיק את המפתח

FindTreeValue המכתב מחדש, שתומך עכשיו גם ב-NameTreeLookup וגם ב-NumTreeLookup, דוחף כל ילד שהטווח שלו אינו מוציא את המפתח וממשיך לשלוף עד שהוא מוצא התאמה או מרוקן את המחסנית. החטאה בתוך עלה אחד היא רק החטאה בתוך עלה אחד. בעץ תקין זה לא עולה דבר; בעץ פגום זה עולה כמה ביקורי צמתים נוספים ומחזיר את התשובה הנכונה

חיפוש העלה נאמן לאותה פילוסופיה. ISO 32000-1 דורש שהמפתחות במערך /Names ימוינו לפי ערך בייט, ולכן העלה נחפש קודם בחיפוש בינארי. אם זה נכשל, PDFlibPas נופלת בחזרה לסריקה ליניארית של הזוגות, כי עלה שאינו ממוין אחרת היה הופך מפתח קיים לבלתי נראה. מיון הוא fast path, לא מסנן

הלוקאפ גם מסרב לנחש מול סתירה מבנית אחת. Table 36 מרשה לצומת לשאת או /Kids או /Names, לעולם לא את שניהם, ונתיב הלוקאפ מתייחס לצומת שנושא את שניהם בתור פגום ומדלג עליו במקום לבחור פרשנות אחת. נתיבי מנייה כמו EnumNumTree סלחניים יותר והולכים אחרי /Kids כששניהם נוכחים

בשביל מה רשאי קורא לסמוך על /Limits?

קורא רשאי לסמוך על /Limits רק כדי לדלג על עבודה, לעולם לא כדי להכריע שמפתח נעדר, ורק כשהזוג תקין. Table 36 אומר שצמתי ביניים ועלים צריכים לשאת /Limits בתור מערך בן שני אלמנטים של המפתח הקטן והגדול ביותר, אבל בפועל הרשומה נעלמת אחרי עריכות יד, מחזיקה מספרים בתוך עץ Name, או מגיעה עם גבולותיה מוחלפים. PDFlibPas v3.539.45 ו-v3.539.51 מכריעות כל מקרה באותו אופן: אם הטווח לא ניתן לקריאה בתור זוג ממוין מהסוג הנכון, הילד נשאר ניתן לחיפוש

• /Limits חסר: בדיקת הטווח הישנה החזירה False והילד דולג כליל, כך שמפיק ששכח את הרשומה הפך את כל תת-העץ שלו לבלתי נגיש. מאז v3.539.45 הילד נחפש
• סוג שגוי או אורך שגוי, כמו מספרים בתוך עץ Name או מערך של אלמנט אחד: מטופל בדיוק כמו רשומה חסרה מאז v3.539.45
• גבולות הפוכים כמו [(Z) (A)] או [9 0]: v3.539.45 עדיין השתמשה בהם, ואף מפתח לא יכול לעמוד בתנאי Lo <= Key <= Hi כש-Lo > Hi, ולכן הענף נשלל עבור כל לוקאפ. מאז v3.539.51 טווח מנוצל לגיזום רק כשהגבול התחתון שלו אינו חורג מהעליון
• תקין, ממוין ונכון: מנוצל כדי לדלג על הענף, וזו כל סיבת הקיום של הרשומה

המפתחות האמיתיים מכריעים את התוצאה בכל מקרה. /Limits עוין יכול לגרום ל-PDFlibPas לבקר ביותר צמתים מהנחוץ, אבל אחד פגום כבר לא יכול לגרום ליעד קיים להיעלם. מצד הקורא שום דבר לא משתנה: GetNamedDestination מחזיר 0 כשהשם באמת נעדר ומזהה יעד אחרת, ופונקציות היעד לוקחות משם את ההמשך

uses
  PDFlibrary;

procedure LookUpDestination(const FileName, DestName: string);
var
  Lib: TPDFlib;
  DestID: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
    begin
      WriteLn('Load failed, error ', Lib.LastErrorCode);
      Exit;
    end;
    // /Dests של הקטלוג (PDF 1.1) קודם, ואז עץ ה-/Dests
    DestID := Lib.GetNamedDestination(DestName);
    if DestID = 0 then
      WriteLn('No destination named ', DestName)
    else if Lib.GetDestPage(DestID) = 0 then
      WriteLn(DestName, ' exists but does not resolve to a page')
    else
      WriteLn(DestName, ' -> page ', Lib.GetDestPage(DestID),
        ', view type ', Lib.GetDestType(DestID));  // 1 = XYZ, 2 = Fit ...
  finally
    Lib.Free;
  end;
end;

מול קובץ שנבנה ביד שבו שורש ה-/Dests מחזיק ילד אחד שחוזר בלולאה אל השורש תחת טווח [(a) (z)] וילד שני שמחזיק את הרשומה האמיתית תחת limits הפוכים של [(z) (a)], הפרוצדורה הזאת פותרת את היעד לעמוד 2 עם סוג תצוגה 2 (Fit). לפני v3.539.45 אותו לוקאפ החזיר 0, כי הילד המעגלי תבע את המפתח ראשון והחיפוש מעולם לא הגיע אל אחיו; v3.539.45 לבדה עדיין החזירה 0, כי הטווח ההפוך שלל את העלה האמיתי. אם אחר כך קוראים את ה-outline שמצביע על היעדים האלה, המאמר הנלווה על קריאת פעולות סימניות והערות ב-PDF ב-Delphi מכסה את צד הפעולות

איך עלה עם 32,769 שמות שבר את TPDFNameTree?

עלה עם 32,769 זוגות שם/ערך שבר את TPDFNameTree כי ה-FindIndex הפנימי שלו ארז שני מספרים בתוך Integer אחד בן 32 ביט: מיקום העלה ברשימת המערכים הפנימית בחצי הגבוה של 16 ביט והיסט הרשומה בתוך מערך ה-/Names של אותו עלה בחצי הנמוך. כל זוג תופס שני תאי מערך, ולכן הזוג ה-32,769, אינדקס זוג 32,768, מתחיל בהיסט 65,536, שהוא $10000. הערך הזה נושא מחאה אל החצי הגבוה, והמפענח קרא אותו חזרה בתור היסט 0 בעלה הבא

TPDFNameTree היא המחלקה שמאחורי קבצים מצורפים, חבילות JavaScript גלובליות וכתיבת יעדים בעלי שם, מה שהופך את ההשלכות למוחשיות. בעץ בעל עלה יחיד אין עלה הבא, ולכן FindKey ו-DeleteKey אינדקסו מעבר לסוף רשימת העלים; בעץ מרובה עלים הן החזירו או מחקו את הזוג הראשון של העלה הבא במקום הזוג המבוקש. במקביל HasKey הריצה סריקה משלה ודיווחה שהמפתח קיים, כך שהמחלקה סתרה את עצמה. מדריך ייחוס שנוצר אוטומטית עם יעד בעל שם אחד לכל סימן API חוצה 32,768 רשומות בלי להתאמץ, וחלק מהמפיקים כותבים את כולן לעלה שטוח אחד

מאז v3.539.45, FindIndex מחזירה את אינדקס המערך דרך פרמטר out נפרד ואת היסט הרשומה המלא בתור תוצאתה, כך שאף ערך לא נחתך. אותה מהדורה ההדקה שני שכנים. KeyName סופרת ומחזירה עכשיו רק מפתחות מחרוזת אמיתיים ומחזירה מחרוזת ריקה עבור אינדקס 0 או מתחת, בזמן שקודם היא יצקה כל אובייקט שבא אחרי מפתח לא תקין. HasKey כבר לא מתייחסת למפתח מספרי או לא תקין אחר בתור שם ריק. עבור עלה כמו [(Valid) 42 123 456], HasKey('') היא עכשיו False ו-KeyName(2) מחזירה מחרוזת ריקה

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // עץ number של /PageLabels; קבצים בלי אחד מחזירים מספרי עמוד פשוטים
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // עץ ה-/EmbeddedFiles; אינדקסים מבוססי 1, מפתחות לא-מחרוזתיים נדלגים
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // שם, סוג MIME
    // עץ ה-/JavaScript: מפרטים שמות חבילות, לא מריצים כלום
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

על אותו קובץ שנבנה ביד, שבו שורש ה-/PageLabels מפרט עלה אחד פעמיים ומפנה אל עצמו, הביקורת הזאת מדפיסה i ו-A-1 עבור שני העמודים, כל טווח פעם אחת, ואת חבילת הסקריפט הבודדת מתוך עץ /JavaScript שגם הוא מצביע חזרה על שורשו. צד הכתיבה של תוויות עמודים יש לו היסטוריה משלו עם שורשי /Kids, שמכוסה ב-תיקון תוויות עמודי PDF האגורות בעצי number מסוג /Kids; AddPageLabels משטח שורש כזה לפני הכנסה, והיא נשענת על אותה מניית EnumNumTree שתוארה כאן

מה החיזוק הזה עדיין לא מערב?

החיזוק מערב סיום, סדר יציב ותוצאות נכונות עבור עצים שהמפתחות האמיתיים שלהם שלמים; הוא לא גורם לעץ פגום להתכוון למה שמחברו התכוון. כמה מגבלות שוות היכרות לפני שבונים עליו

• קבוצת ה-visited עובדת לפי זהות אובייקט. שני מילונים נבדלים עם תוכן זהה הם שני צמתים, ולכן מפיק שמעתיק עלה במקום להפנות אליו עדיין מניב רשומות כפולות
• /Limits תקין, ממוין אבל שגוי עדיין גוזם. קורא שמשתמש בטווחים בתור אופטימיזציה לא יכול גם להיות חסין מול טווח שמשקר באופן משכנע; החלופה היחידה היא להתעלם מ-/Limits כליל ולסרוק כל עלה
• המנייה משמרת סדר קובץ אבל לא ממיינת. GetPageLabel מיישמת את הטווח המנוי האחרון בעמוד או מתחתיו, כך שמפיק שכותב טווחים שלא בסדר מקבל סמנטיקה של סדר-קובץ
• הזיכרון גדל עם מספר הצמתים והרשומות הנבדלים. ההליכה מוסיפה רשימה ו-hash set, שום דבר מעבר, אבל עץ Name של 100 MB נשאר עץ Name של 100 MB גם אחרי הפרסור
• מפתחות כפולים בתוך עלה אחד אינם מדווחים. החיפוש הבינארי מחזיר את כל זוג תואם שהוא פוגע בו ראשון; ה-fallback הליניארי שומר את ההתאמה האחרונה שהוא סורק

עזר זריז: קריאת עצי PDF מקבצים לא מהימנים

• שדרגו ל-v3.539.45 ומעלה להליכה בטוחת-מעגלים ובטוחת-מחסנית על עצי Name ועצי number, ול-v3.539.51 ומעלה כך ש-/Limits הפוכים כבר לא מסתירים מפתחות
• מתייחסים ל-GetNamedDestination שמחזיר 0 בתור "נעדר", ול-GetDestPage שמחזיר 0 בתור "קיים אך בלתי שמיש"
• משתמשים ב-GlobalJavaScriptCount וב-GlobalJavaScriptPackageName עבור עץ ה-Name של /JavaScript; GetDocJavaScript קורא במקום זאת את טריגרי ה-/AA של הקטלוג
• מאנדקסים קבצים מצורפים וחבילות סקריפט מ-1 ועד המניין שהספרייה מדווחת; מפתחות לא תקינים אינם נספרים
• בקוד העצים שלכם, מסמנים צמתים כמבוקרים בשליפה, דוחפים ילדים בסדר הפוך, ומרשים ל-/Limits לגזום רק כשהוא זוג מסוג תקין וממוין

כלי pre-flight, ארכיונאים וצופים קוראים את העצים האלה לפני שעמוד כלשהו מרונדר, ולכן הם חייבים לשרוד כל מה שמגיע בתור העלאות. קוראי העצים שתוארו למעלה מגיעים עם PDFlibPas, ה-PDF Library for Delphi, שמתקמפלת גם עם Delphi וגם עם Free Pascal