مقاله همراه ما درباره ترتیب صفحات PDF قانون پایه را توضیح میدهد: ترتیب نمایش از پیمایش depth-first از چپ به راست روی آرایههای /Kids در درخت /Pages میآید، نه از شماره اشیاء. این مقاله به همان درخت از زاویهای دیگر نگاه میکند: شکل آن. چرا نویسندگان بالغ PDF وقتی یک آرایه تخت هم از نظر استاندارد کاملاً مجاز است، سلسلهمراتبی از گرههای میانی تولید میکنند؟ وقتی ابزاری درخت را flatten یا rebuild میکند دقیقاً چه چیزی عوض میشود؟ و وقتی bookkeeping مربوط به /Count که کل ساختار را سریع نگه میدارد دیگر حقیقت را نمیگوید چه رخ میدهد
Fan-out یک تصمیم عملکردی است
هیچ چیز نویسنده را مجبور به تو در تو کردن درخت نمیکند. یک سند 10000 صفحهای با یک گره ریشه /Pages و 10000 ارجاع برگ در یک آرایه واحد /Kids با استاندارد سازگار است. با این حال PDF Reference برای اسناد بزرگ درخت متوازن را توصیه میکند و تولیدکنندههای اصلی هم همین توصیه را با fan-out نسبتاً کم، معمولاً چند ده فرزند برای هر گره میانی، دنبال میکنند
دلیلش این است که نمایشگر پیش از نشان دادن هر چیزی چه چیزهایی باید بخواند. فرض کنید کاربر مستقیماً به صفحه 8214 در آن فایل 10000 صفحهای میپرد. در درخت تخت، نمایشگر اول باید گره ریشه را parse کند و آن گره ریشه یک آرایه عظیم است: با تقریب هشت بایت برای هر ارجاع غیرمستقیم، یک شیء 80 کیلوبایتی که باید از ابتدا تا انتها tokenized شود تا ورودی 8213 قابل resolve باشد. با یک درخت متوازن با fan-out برابر 32، همان پرش فقط ریشه را میخواند، مجموعهای جاری /Count را مقایسه میکند تا فرزند درست را پیدا کند و پایین میرود، یعنی در مجموع سه یا چهار دیکشنری کوچک، هرکدام در حد چندصد بایت. این همان دسترسی تصادفی O(log n) است که درخت برای آن طراحی شده و دقیقاً دلیل وجود /Count در گرههای میانی هم همین است: reader میتواند بدون باز کردن حتی یک شیء داخل زیردرخت، کل آن زیردرخت را رد کند
شکل درخت هزینه ویرایش را هم تعیین میکند. یک بهروزرسانی افزایشی که یک صفحه درج میکند باید هر گرهی را که /Kids یا /Count آن تغییر کرده بازنویسی کند، یعنی مسیر از والد برگ جدید تا ریشه. در یک درخت متوازن این مسیر فقط چند دیکشنری کوچک است که به فایل append میشوند. در یک درخت تخت، تمام این مسیر همان آرایه عظیم ریشه است که در هر بازبینی کامل دوباره تکرار میشود. قراردادی که سی چرخه بازبینی و annotate شدن را پشت سر بگذارد ممکن است در جریان بایت خود سی نسخه منسوخ از همان آرایه 80 کیلوبایتی را حمل کند
گرههای داخلی ویژگیهای موروثی را حمل میکنند
گرههای میانی فقط برای مسیریابی نیستند. چهار ویژگی موروثی صفحه، یعنی /Resources، /MediaBox، /CropBox و /Rotate، میتوانند روی هر گره /Pages قرار بگیرند و در این صورت روی همه برگهای زیر آن اعمال میشوند، مگر اینکه یکی از فرزندان آنها را override کند. نویسندهای که گزارشی با پیوست landscape تولید میکند میتواند همان چیدمان را در خود درخت بیان کند:
5 0 obj % document root
<< /Type /Pages /Count 6 /Kids [6 0 R 7 0 R] >>
endobj
6 0 obj % report body: portrait A4, body font
<< /Type /Pages /Parent 5 0 R /Count 3
/Kids [30 0 R 31 0 R 32 0 R]
/MediaBox [0 0 595 842]
/Resources << /Font << /F1 8 0 R >> >> >>
endobj
7 0 obj % appendix: landscape A4, rotated, its own font
<< /Type /Pages /Parent 5 0 R /Count 3
/Kids [40 0 R 41 0 R 42 0 R]
/MediaBox [0 0 842 595] /Rotate 90
/Resources << /Font << /F2 9 0 R >> >> >>
endobj
40 0 obj % appendix page: inherits size, rotation, fonts
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobjاشیای 40 تا 42 تقریباً خالی هستند. اندازه صفحه، چرخش و منابع فونت آنها همگی از طریق ارثبری از گره 7 میرسند و همین فایل را فشرده و خودنگهدار میکند: اگر صفحه چهارمی زیر گره پیوست اضافه کنید، بهطور خودکار landscape خواهد شد
همین سازوکار همان خطر کلاسیک جابهجایی صفحه را ایجاد میکند. فرض کنید ابزاری شیء 40 را با ویرایش دو آرایه /Kids و تغییر دادن /Parent به گره 6 به بدنه گزارش منتقل کند. این جابهجایی از نظر ساختاری معتبر است، اما حالا شیء 40، /MediaBox پرتره، بدون چرخش و فونت /F1 را به ارث میبرد، در حالی که content stream آن هنوز /F2 را انتخاب میکند که دیگر resolve نمیشود. صفحه در یک ویرایش هم کوچک میشود، هم دیگر چرخیده نیست و هم متنش را از دست میدهد. بنابراین کد بازآرایی مقاوم پیش از reparent کردن صفحه، مقادیر resolve شده هر چهار ویژگی موروثی را روی دیکشنری صفحه materialize میکند. اگر تا به حال در یک ویرایشگر صفحهای را drag کردهاید و دیدهاید اندازه یا جهتش عوض میشود، همین سازوکار را دیدهاید
Flattening: قانونی، رایج و گاهی پرهزینه
ابزارهای زیادی دقیقاً در جهت برعکس حرکت میکنند. نویسندههای مینیمال یک درخت تکسطحی تولید میکنند چون ساده است و بسیاری از ابزارهای merge و split هر درختی را که میخوانند به یک آرایه تخت /Kids بازسازی میکنند، چون ساختن یک ساختار متوازن کار اضافی میخواهد و خروجی تخت همیشه با استاندارد سازگار است. یک بازسازی درست باید ارثبری را همزمان resolve کند: هر ویژگیای که یک برگ از پدر خود به ارث میبرد باید یا روی خود برگ کپی شود یا اگر در کل سند یکسان است روی ریشه جدید hoist شود، وگرنه هندسه خروجی دقیقاً مثل حالت جابهجایی صفحه تغییر میکند
برای اسناد معمولی flatten کردن بیضرر است. آسیب آن در مقیاس بالا و در همان دو شکلی است که گفتیم: آرایه ریشه به یک شیء بزرگ تبدیل میشود که هر بار باز کردن سند و هر پرش صفحه باید آن را کامل parse کند و هر ویرایش ساختاری هم آن را بهطور کامل بازنویسی میکند. چیزی که flatten کردن از بین نمیبرد اشتراک از طریق ارجاعهای غیرمستقیم است؛ درخت تختی که هر 10000 صفحه آن به یک شیء دیکشنری /Resources مشترک اشاره میکنند، هنوز deduplicated باقی میماند. چیزی که از دست میرود فقط این امکان است که آن ورودی روی صفحه غایب باشد و یک ancestor آن را تأمین کند
وقتی /Count دروغ میگوید
/Count صرفاً bookkeeping است: باید برابر با تعداد صفحههای برگ در زیردرخت گره باشد و هیچ بخشی از قالب فایل آن را enforce نمیکند. دو الگوی خرابی بیشترین سهم را در /Countهای دروغگویی دارند که در عمل دیده میشوند
اولی شمارش کهنهای است که بعد از یک بهروزرسانی افزایشی جا مانده است. یک ویرایشگر صفحهای را درج میکند، والد بلافصل را با /Kids جدید و /Count بهروز بازنویسی میکند، هر دو را به فایل append میکند و هیچوقت به اجداد دست نمیزند:
% Original revision
12 0 obj
<< /Type /Pages /Count 9 /Kids [13 0 R 14 0 R 15 0 R] >>
endobj
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 3
/Kids [50 0 R 51 0 R 52 0 R] >>
endobj
% Appended revision: one page inserted into the middle branch.
% Object 14 is superseded; object 12 is never rewritten
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 4
/Kids [50 0 R 51 0 R 90 0 R 52 0 R] >>
endobjحالا درخت ده برگ دارد، اما ریشه هنوز میگوید نه تا. نمایشگری که به ریشه اعتماد کند، شمارنده صفحه را نه نشان میدهد. نمایشی که از شمارشهای داخلی برای binary-search پرش صفحه استفاده کند، برای هر صفحه بعد از نقطه درج، اندیس اشتباه حساب میکند. یک پیمایش کامل عدد ده را پیدا میکند. سه پاسخ متفاوت، یک فایل
الگوی دوم شمارشی است که اصلاً نمیتواند درست باشد: منفی، صفر روی گرهی که جمعیت دارد یا بهطرز مضحکی بزرگ. اینها از fuzzing، خرابی انتقال و گاهی از باگهای حسابی در ویرایشگرها میآیند. خطر آنها بهویژه برای کدی است که برای تخصیص حافظه به /Count اعتماد میکند؛ ساختن آرایه از روی /Count برابر با 3- در بهترین حالت range error میدهد و همین کار با /Count برابر با دو میلیارد به تخصیص denial-of-service ختم میشود. این مقدار مثل هر عدد دیگری در فایل، ورودی غیرقابلاعتماد است
parserها در برابر این وضعیت به دو اردوگاه تقسیم میشوند. مصرفکنندههای سختگیر، یعنی preflight toolها، validatorهای PDF/A و pipelineهای آرشیوی، /Count را با نتیجه پیمایش مقایسه میکنند و فایل را رد یا flag میکنند. نمایشگرهای تعاملی تقریباً همگی lenient هستند: پیمایش میکنند، تعداد واقعی را به دست میآورند و مقدار ذخیرهشده را بیسروصدا نادیده میگیرند. دقیقاً به همین دلیل است که فایلِ دارای شمارش کهنه میتواند سالها بیاعتراض دستبهدست شود تا وقتی به parser سختگیرتری در یک workflow خودکار برسد. موضع دفاعی میانی برای کد کتابخانه این است که /Count را یک hint در نظر بگیرید، مفید برای پیشتخصیص و برای رد کردن زیردرختها پس از راستیآزمایی، اما پیمایش را منبع حقیقت باقی بگذارید
برای خود الگوریتم پیمایش، قواعد resolve ارثبری و حرکت از catalog به برگ، از مقاله توضیحی ترتیب صفحات شروع کنید. برای اینکه این حالتهای خرابی وقتی یک سند واقعی مشتری به کد تولید میرسد چه شکلی پیدا میکنند، مطالعه موردی اشکالزدایی ترتیب صفحات را بخوانید که یک رخداد shuffled pages را از نشانه اولیه تا ریشه علت دنبال میکند
HotPDF Component همه اینها را بهصورت داخلی مدیریت میکند: درختهای تو در تو با هر عمقی را پیمایش میکند، هنگام کپی یا جابهجایی صفحه ویژگیهای موروثی را resolve میکند و بهجای اعتماد به /Count آن را با تعداد واقعی برگها تطبیق میدهد، بنابراین اندیس صفحه در API آن همیشه به صفحه منطقی اشاره میکند