أشجار الأسماء في PDFlibPas: دورات و Limits وأوراق عملاقة

تمشي PDFlibPas، مكتبة PDF من losLab لـ Delphi، في أشجار أسماء PDF وأشجار الأعداد بمكدّس صريح ومجموعة زيارات منذ v3.539.45، فبقيت دورات /Kids والبنات المشتركة والأشجار بعمق آلاف المستويات لم تعد تستنزف مكدّس النداءات ولا تكرر المدخلات. ومنذ v3.539.51 لم يعد زوج /Limits مفقوداً أو مشوهاً أو معكوساً يخفي فرعاً يحمل المفتاح. فالوجهات المسماة وعناوين الصفحات والمرفقات و JavaScript على مستوى المستند كلها تقرأ عبر مسارَي الكود هذين، وهذا يجعلهما جزءاً من سطح هجوم أي PDF لم تنتجه أنت

والمُحِدّ نادراً ما يكون غريباً. فأداة fuzzing أو تحميل معادٍ أو حفظ تدريجي معطوب يكتب مدخل /Kids يشير عائداً إلى سلف، ومالش تكراري يموت بفيضان مكدّس على ملف من كيلوبايتين. والفشل الأهدأ بحث يثق بمصفوفة /Limits مكسورة فيبلّغ "غير موجود" عن وجهة باينة تماماً

أين تظهر أشجار الأسماء وأشجار الأعداد في PDF؟

تظهر أشجار الأسماء وأشجار الأعداد أينما داها PDF بين مجموعة كبيرة من المفاتيح وكائنات، وتقرأ PDFlibPas أربعاً منها على الأقل عبر APIs عامة. يعرّف ISO 32000-1 §7.9.6 شجرة الأسماء (مفاتيح سلاسل، الجدول 36) و §7.9.7 شجرة الأعداد (مفاتيح أعداد صحيحة، الجدول 37). وكلتاهما شجرتان شبه متوازنتين تحمل الجذور والعقد الوسيطة /Kids، وتحمل الأوراق أزواج مفتاح/قيمة مرتبة في /Names أو /Nums، وتحمل العقد غير الجذرية مصفوفة /Limits من عنصرين بأصغر مفاتيحها وأكبرها تحتها

الشجرة	مكانها	المواصفة	API القراءة في PDFlibPas
الوجهات المسماة	/Dests في قاموس الأسماء	§12.3.2.3	GetNamedDestination ثم GetDestPage / GetDestType
عناوين الصفحات	/PageLabels في الكتالوج (شجرة أعداد)	§12.4.2	GetPageLabel
المرفقات	/EmbeddedFiles في قاموس الأسماء	§7.7.4، §7.11.4	EmbeddedFileCount، GetEmbeddedFileStrProperty
JavaScript على مستوى المستند	/JavaScript في قاموس الأسماء	§7.7.4	GlobalJavaScriptCount، GlobalJavaScriptPackageName

تفصيلان في ذلك الجدول يسهل فواتهما. للوجهات المسماة صيغة أقدم من PDF 1.1 أيضاً، قاموس /Dests عادي في الكتالوج مفتاحه كائنات أسماء، ويفحص GetNamedDestination ذلك القاموس أولاً قبل هبوطه في شجرة أسماء PDF 1.2. و GetDocJavaScript ليست قارئة شجرة أسماء أصلاً: إنها تعيد السكربتات المرفقة بمُطلِقات المستند في قاموس /AA بالكتالوج ‏(WS، DS، WP، DP، DC)، بينما تسكن حزم السكربتات المسماة التي تعمل عند فتح مستند في شجرة أسماء /JavaScript

وكل بايت من تلك البنى يأتي من الملف. فالمواصفة تقول ماذا يجب أن ينتج الكاتب؛ ولا تستطيع أن تمنع قارئاً من تلقي شيء آخر، وهو الدرس نفسه وراء تحصين محلل PDF بلغة Pascal ضد الملفات الخبيثة، مطبقاً هنا على شكل الشجرة بدل أحجام المخازن

لماذا تُسقط مصفوفة /Kids دورية مالشَاً تكرارياً للشجرة؟

تُسقط مصفوفة /Kids دورية مالشاً تكرارياً لأن شيئاً في العودية لا يلاحظ أنه قابل عقدة من قبل، فسليلة تشير إلى سلفها تحوّل ملفاً محدوداً إلى هبوط لا نهائي. قبل v3.539.45 كانت NameTreeLookup و NumTreeLookup و EnumNumTree و TPDFNameTree.ProcessNode الداخلية تستدعي نفسها مرة لكل سليلة. وكانت إحالة ذاتية واحدة كافية لإنهاء العملية، وكانت شجرة مشروعة عميقة جداً تستطيع الشيء نفسه دون أي دورة

وصرْف أخف يفسد النتائج بدل أن يُسقط. حين تشير مدخلا /Kids إلى الورقة ذاتها، تزورها عدّ ساذجة مرتين، فيبلّغ عدّاد مرفقات أو قائمة حزم سكربتات عن مدخلات غير موجودة

ويستبدل الإصلاح العودية بمكدّس صريح من نوع آخر يدخل أولاً يخرج أخيراً على الكومة، ومجموعة زيارات مفتاحها هوية القاموس. تُعلَّم العقدة عند سحبها لا عند ضغطها، فيمكن أن يجلس مرجع دوري على المكدّس قليلاً لكنه يُرمى لحظة صعوده. وكل عقدة مميزة توسّع بناتها مرة واحدة بالضبط، وهو ما يحدّ العمل الكلي بعدد القواميس المميزة زائد الطول الكلي لمصفوفات /Kids فيها. فيتوقف العمق عن الاعتبار: سلسلة من 4,096 مستوى مجرد 4,096 دورة حلقة و 4,096 مدخلاً في مجموعة hash

لكن الترتيب ما زال مهماً، وعلى تغذية المكدّس بالمقلوب ليحفظ. تُضغط البنات من آخر فهرس نزولاً إلى الأول، فتُسحب البنة اليسرى أولاً وتخرج الأوراق بترتيب اليسار إلى اليمين نفسه الذي كتبه المنتِج. ويعتمد 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 إلى مسح خطي للأزواج، لأن ورقة خارج الترتيب كانت ستُخفي مفتاحاً موجوداً. فالترتيب طريق سريع لا مصفاة

كما يمتنع البحث عن التخمين عند تناقض بنيوي واحد. يسمح الجدول 36 لعقدة بحمل /Kids أو /Names لا الاثنين أبداً، ويعامل مسار البحث العقدة الحاملة للاثنين بوصفها مشوهة ويتخطاها بدل اختيار تفسير من الاثنين. أما مسارات العدّ مثل EnumNumTree فهي أكثر تسامحاً وتتبع /Kids حين يكون الاثنان موجودين

لماذا يجوز للقارئ أن يثق بـ /Limits؟

يجوز للقارئ أن يثق بـ /Limits في تخطي العمل فقط، لا في حكم غياب مفتاح أبداً، وفقط حين يكون الزوج حسن التكوين. يقول الجدول 36 إن العقد الوسيطة والأوراق يجب أن تحمل /Limits مصفوفةً من عنصرين بأصغر المفاتيح وأكبرها، لكن عملياً يختفي المدخل بعد تحريرات يدوية، أو يحمل أرقاماً في شجرة أسماء، أو يصل حدّاه معكوسين. تسوّى PDFlibPas v3.539.45 و v3.539.51 كل حالة بالطريقة نفسها: إن لم يمكن قراءة المدى زوجاً مرتباً من النوع الصحيح فتبقى السليلة قابلة للبحث

• /Limits مفقودة: كان فحص المدى القديم يعيد False وتُتخطى السليلة كلياً، فمنتج نسي المدخل جعل شجرته الفرعية كلها لا تُبلَغ إليها. ومنذ v3.539.45 تُبحث السليلة
• نوع خاطئ أو طول خاطئ، أرقام في شجرة أسماء أو مصفوفة بعنصر واحد: تعامل تماماً كمدخل مفقود منذ 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 الذي يشير إلى هذه الوجهات فالمقالة المرافقة عن قراءة إجراءات الإشارات المرجعية و annotations في PDF بلغة Delphi تغطي جانب الإجراءات

كيف كسرت ورقة بـ 32,769 اسماً الصنف TPDFNameTree؟

كسرت ورقة بـ 32,769 زوج اسم/قيمة الصنفَ TPDFNameTree لأن FindIndex الداخلية عنده تحزم رقمين في Integer واحد ذي ‏32-بت: موضع الورقة في قائمة المصفوفات الداخلية في النصف العلوي ‏16-بت، وإزاحة المدخل داخل مصفوفة /Names لتلك الورقة في النصف السفلي ‏16-بت. ويحتل كل زوج خانتين من المصفوفة، فالزوج رقم 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;
    // شجرة أعداد ‏/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 المخزنة في أشجار أعداد /Kids؛ فـ AddPageLabels تسطّح ذلك الجذر قبل الإدراج، وتعتمد على عدّ EnumNumTree نفسه الموصوف هنا

ما الذي لا يضمنه هذا التحصين بعد؟

يضمن التحصين التوقفاً والترتيب المستقر والنتائج الصحيحة لأشجار مفاتيحها الحقيقية سليمة؛ وهو لا يجعل شجرة تالفة تعني ما قصده مؤلفها. وثمة حدود يستحق معرفتها قبل أن تبنِ عليه

• تعمل مجموعة الزيارات بهوية الكائن. قاموسان مميزان بمحتوى متطابق عقدتان، فمنتج ينسخ ورقة بدل الإشارة إليها ما زال ينتج مدخلات مكررة
• تقوم /Limits حسنة التكوين ومرتبة لكن خاطئة بالتقليص مع ذلك. قارئ يستخدم المدوات تحسيناً لا يستطيع أن يكون محصناً من مدى يكذب مقنعاً؛ والبديل الوحيد تجاهل /Limits كلياً ومسح كل ورقة
• يحفظ العدّ ترتيب الملف لكنه لا يفرز. يطبق GetPageLabel آخر نطاق معدود عند الصفحة أو تحتها، فمنتج يكتب المدوات خارج الترتيب يحصل على دلالات ترتيب الملف
• تنمو الذاكرة بعدد العقد والمدخلات المميزة. يضيف الاجتياز قائمة ومجموعة hash لا أكثر، لكن شجرة أسماء بحجم 100 MB تبقى شجرة أسماء بحجم 100 MB بعد التحليل
• لا تُبلَّغ المفاتيح المكررة داخل ورقة واحدة. يعيد البحث الثنائي أول زوج مطابق يصطدم به؛ والمسح الخطي الاحتياطي يبقي آخر تطابق يمسحه

مرجع سريع: قراءة أشجار PDF من ملفات غير موثوقة

• رقِّ إلى v3.539.45 أو أحدث لاجتياز آمن ضد الدورات وآمن ضد المكدّس لأشجار الأسماء وأشجار الأعداد، وإلى v3.539.51 أو أحدث حتى لا تخفي /Limits المعكوسة مفاتيح بعد الآن
• عامل إعادة GetNamedDestination القيمة 0 بوصفها "غائباً"، وإعادة GetDestPage القيمة 0 بوصفها "موجودة لكن غير صالحة للاستخدام"
• استخدم GlobalJavaScriptCount و GlobalJavaScriptPackageName لشجرة أسماء /JavaScript؛ أما GetDocJavaScript فتقرئ مُطلِقات /AA في الكتالوج بدلاً منها
• فهرس المرفقات وحزم السكربتات من 1 إلى العدد الذي تبلّغه المكتبة؛ المفاتيح غير الصالحة لا تُعَدّ
• في كود شجرك أنت، علِّم العقد زيارتها عند السحب، واضغط البنات بالمقلوب، ودع /Limits تُقلّص فقط حين تكون زوجاً مرتباً حسن النوع

أدوات الفحص المسبق والمؤرشفات والعارضات تقرأ هذه الأشجار قبل عرض أي صفحة، فعليها أن تنجو من أي شيء يصل في طابور تحميل. وقارئات الأشجار الموصوفة أعلاه تصل مع ‏PDFlibPas، مكتبة PDF لـ Delphi، التي تُبنى بكل من Delphi و Free Pascal