باگ‌های ترتیب صفحه PDF در HotPDF: ساختار فیزیکی در برابر منطقی

این علامت در یک ابزار کاربردی کپی صفحه که بر روی HotPDF Component ساخته شده بود ظاهر شد: درخواست صفحه 1 از یک سند سه‌صفحه‌ای به طور مداوم صفحه 2 را تولید می‌کرد. بررسی منطق نمایه‌سازی (indexing) هیچ چیز اشتباهی پیدا نکرد. فراخوانی از یک نمایه منطقی مبتنی بر صفر استفاده می‌کرد، محاسبات صحیح بود و شرایط مرزی خوب بود. با این حال هر بار صفحه اشتباه بیرون می‌آمد

باگ اصلاً در کد کپی کردن نبود. باگ در نحوه ساختن آرایه صفحه داخلی خود HotPDF هنگام بارگیری فایل بود

دو ترتیب‌بندی، یک منبع سردرگمی

یک فایل PDF مجموعه‌ای از اشیاء غیرمستقیم است که هر کدام با یک شماره شیء شناسایی می‌شوند. ساختار فایل هیچ الزامی بر این شماره‌ها تحمیل نمی‌کند تا ترتیب خواندن را منعکس کنند. شیء 1 می‌تواند صفحه 2 را نگه دارد؛ شیء 20 می‌تواند صفحه 1 را نگه دارد. آنچه در واقع ترتیب خواندن را تعریف می‌کند درخت صفحه است: سلسله مراتبی از دیکشنری‌های /Pages که آرایه‌های /Kids آن‌ها ارجاع‌های صفحه را در دنباله‌ای لیست می‌کنند که یک نمایشگر باید آن‌ها را نمایش دهد (ISO 32000-1 §7.7.3)

سندی که این باگ را ایجاد کرد دارای این ساختار درخت صفحه بود:

{ Pages tree root, object 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { logical page 1 }
         1 0 R    { logical page 2 }
         4 0 R]   { logical page 3 }
>>
endobj

به طور اتفاقی، فایل، شیء 1 و شیء 4 را قبل از شیء 20 در جریان بایت (byte stream) لیست کرده بود. هر تجزیه‌کننده‌ای که اشیاء غیرمستقیم را به ترتیب فایل فیزیکی تکرار کند و با یافتن دیکشنری‌های نوع صفحه آن‌ها را در یک 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
{ Output reveals Kids order: 20 0 R, then 1 0 R, then 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Shows the Pages dictionary with /Kids in reading order }

استخراج تک‌تک صفحات و بررسی اندازه فایل‌ها این نگاشت را تأیید کرد: آنچه PageArr[0] تولید کرد، محتوای متعلق به صفحه منطقی 2 بود و PageArr[2] صفحه منطقی 1 را نگه داشت. جابجایی دایره‌ای دلیل اصلی قضیه بود. این همچنین توضیح داد که چرا مشکل در چندین سند منبع مختلف ظاهر شد: هر PDF که در آن اشیاء صفحه به طور اتفاقی شماره شیء کمتری نسبت به صفحه منطقی قبلی داشتند، این مشکل را راه‌اندازی می‌کرد

یک دلیل سرراست وجود دارد که چرا PDFها در این حالت به پایان می‌رسند. ذخیره‌سازی‌های افزایشی (incremental saves) اشیاء به‌روزرسانی‌شده را با شماره اشیاء جدید الحاق می‌کنند و اسلات‌های قدیمی در جدول ارجاع متقاطع (cross-reference table) را رها می‌کنند تا به هیچ‌کجا اشاره نکنند. ویرایشگرهایی که یک صفحه جلد اضافه می‌کنند، بدون توجه به موقعیت آن در آرایه Kids، آن را با یک شماره شیء بالا وارد می‌سازند. برخی از تولیدکننده‌ها به سادگی صفحات را به ترتیبی می‌نویسند که برای جریان محتوا مناسب است به جای اینکه بر اساس دنباله منطقی صفحه باشد. فرمت PDF آن‌ها را ملزم به انجام غیر از این نمی‌کند

اصلاح: آرایه Kids را دنبال کنید

رویکرد صحیح ساختن PageArr با پیمایش زنجیره /Kids از ریشه کاتالوگ است، نه با اسکن اشیاء غیرمستقیم. پس از اینکه هر دو مسیر تجزیه پاس اولیه خود را تکمیل کردند، یک مرحله پس‌پردازش ترتیب منطقی را حل می‌کند:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Locate root /Pages dictionary via 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;
    { Non-page Kids (intermediate /Pages nodes) produce no match; skip }
  end;

  if PageIndex > 0 then
  begin
    SetLength(PageArr, PageIndex);
    for I := 0 to PageIndex - 1 do
      PageArr[I] := NewPageArr[I];
  end;
end;

این فراخوانی در پایان هر مسیر تجزیه وارد می‌شود، پس از آنکه تمام اشیاء فهرست‌بندی شدند اما قبل از اینکه به عملیات صفحه‌ای سرویس داده شود:

{ Traditional path }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Modern path (object streams) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

مرحله تغییر ترتیب O(n * m) است که در آن n تعداد Kids و m طول فعلی PageArr است، اما برای هر سندی با یک درخت صفحه مسطح (همه برگ‌ها در عمق 1، که اکثریت قریب به اتفاق PDFهای دنیای واقعی را پوشش می‌دهد) هر دو مقدار یکسانی دارند و هزینه ناچیز است. درختان صفحه‌ای که عمیقاً تودرتو هستند به جای رویکرد تک‌سطحی نشان داده شده در اینجا، به یک پیمایش بازگشتی نیاز دارند؛ پیاده‌سازی تولید با این مورد جداگانه برخورد می‌کند

استفاده از CopyPageFromDocument پس از اصلاح

با قرارگیری ReorderPageArrByPagesTree در جای خود، اندیس‌های صفحه منطقی همان‌طور که انتظار می‌رود کار می‌کنند. تابع سطح بالاتر CopyPageFromDocument یک اندیس منطقی مبتنی بر صفر را می‌پذیرد و صفحه صحیح را در سند مقصد کپی می‌کند:

var
  Source, Dest: THotPDF;
begin
  Source := THotPDF.Create(nil);
  Dest   := THotPDF.Create(nil);
  try
    Source.LoadFromFile('source.pdf');

    Dest.FileName := 'extracted.pdf';
    Dest.BeginDoc;

    { Copy logical page 0 (first page the user sees) }
    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). هر تجزیه‌کننده‌ای که از یک ترتیب‌بندی متفاوت به عنوان میانبر استفاده کند، نتایج صحیحی روی اکثر اسنادی که می‌بیند تولید خواهد کرد، زیرا اکثر تولیدکننده‌ها صفحات را به ترتیب طبیعی می‌نویسند و شماره اشیاء متوالی اختصاص می‌دهند. این باگ پنهان می‌ماند تا زمانی که شخصی PDFی را بارگیری کند که به صورت افزایشی ویرایش شده است، توسط ابزار دیگری سازماندهی مجدد شده باشد، یا توسط نرم‌افزاری تولید شده است که چیدمان متفاوتی را انتخاب کرده باشد

آزمایش کردن فقط در برابر PDFهای خود-تولیدشده، این دسته از مشکل را به طور کامل از دست می‌دهد. اصلاح یک پسرفت (regression) ترتیب صفحه، بنابراین به یک پیکره از اسناد از منابع متنوع نیاز دارد: ذخیره‌سازی‌های افزایشی، اسناد اسکن‌شده با صفحات جلد واردشده، PDFهای تولیدشده توسط ابزارهایی که گراف شیء را به صورت متفاوت خطی‌سازی یا بهینه‌سازی می‌کنند. سندی که باگ اصلی را فعال کرده است باید به طور دائم در مجموعه تست (regression suite) باقی بماند

صفحه HotPDF Component کل API را برای عملیات صفحه، از جمله CopyPageFromDocument، InsertPagesFromDocument و MovePage پوشش می‌دهد