ادغام سریع PDF در Delphi: جابه‌جایی مرجع‌ها در سطح byte

چسباندن PDFها باید از نظر تئوری ارزان باشد. content pageها از قبل چیده شده‌اند، fontها از قبل embed شده‌اند، imageها از قبل فشرده شده‌اند. در اصل merge فقط bookkeeping است: objectها را دوباره شماره‌گذاری کنید تا فضای شماره‌گذاری دو file با هم collide نکند، page treeها را به هم بدوزید، cross-reference table را تعمیر کنید، و بنویسید. در عمل بیشتر merge code این ارزانی را دور می‌ریزد. برای هر object در هر input file یک parse کامل به یک object tree tokenized انجام می‌دهد، چند indirect reference را mutate می‌کند، و بعد tree را دوباره به bytes serialize می‌کند. parse و reserialize دو نیمهٔ پرهزینه‌اند، و برای اکثریت قریب به اتفاق objectها چیزی تولید می‌کنند که از نظر bytes تقریباً همان چیزی است که وارد شده بود

PDFlibPas یک موتور PDF بومی Object Pascal برای Delphi و C++Builder است، و fast merge path آن وجود دارد تا هرجا که به‌طور قابل‌اثبات امن باشد این رفت‌وبرگشت را حذف کند. ایده باریک است اما در مجموعه‌های بزرگ document واقعاً اثر دارد: برای یک non-stream object تغییرنکرده، bytes اصلی source را verbatim بردارید و فقط یک بازنویسی در سطح byte روی indirect referenceهایی که در خود دارد انجام دهید، و هر N G R را به (N+Offset) G R تبدیل کنید. هیچ tokenizerای، هیچ object treeی، هیچ serializerی در کار نیست. این مقاله توضیح می‌دهد این shortcut کجا مجاز است، machine stateای که بازنویسی byte را بدون خراب‌کردن چیزی انجام می‌دهد چیست، چرا merge bookmarkها به مکانیزم کاملاً متفاوتی نیاز داشت، و چگونه مسیر merge معمولی هم‌زمان از quadratic به linear بازسازی شد

چرا object renumbering هزینهٔ واقعی merge است

هر PDF فضای شماره‌گذاری object خودش را دارد. file A object 1، object 2 و همین‌طور ادامه دارد؛ file B هم object 1، object 2 و همین‌طور ادامه دارد. نمی‌توانید objectهای B را بدون تغییر وارد file A کنید، چون شماره‌ها collide می‌کنند و هر indirect reference داخل B حالا به object اشتباه resolve می‌شود. راه‌حل یک offset است: اگر A تا تعداد object Offset می‌رسد، آن‌وقت object N در B به object N+Offset در output تبدیل می‌شود، و هر reference N G R که هرجای objectهای B ظاهر شود باید به (N+Offset) G R جابه‌جا شود تا match کند

این جابه‌جایی تمام کار معنایی merge body است. page tree fixupها و AcroForm merge ویرایش‌های کوچک و bounded روی تعداد کمی object هستند. کار عمده بازنویسی referenceها در هزاران object است، و روش ساده‌لوحانه برای انجامش این است که هر object را parse کنید تا referenceها را به‌شکل ساختاری پیدا کنید. fast merge در PDFlibPas MergeFileListFast دیدگاه opposite را اتخاذ می‌کند: referenceها در bytes خام هم قابل پیدا شدن هستند، اگر در contextهایی که یک sequenceِ digit-space-digit-space-R وجود دارد نیست یک reference، دقت کنید. parse را حذف کنید، در place shift کنید، و هزینهٔ per-object به یک scan خطی تنها از bytesی فرو می‌ریزد که در هر صورت قرار بود copy شوند

وقتی استفاده دوباره از source bytes به‌طور قابل‌اثبات امن است

مسیر byte فقط وقتی گرفته می‌شود که هر سه شرط برای objectی که از document بعدی کپی می‌شود برقرار باشند. شکست هر کدام object را به مسیر کامل decode-and-reserialize برمی‌گرداند، پس correctness همیشه از speed جلوتر است:

Doc2.IsChangedObject(X) False است. اگر merge engine قبلاً object را در memory mutate کرده باشد (مثلاً page objectی که /Parent آن دوباره هدف‌گیری شده باشد)، tree داخل memory منبع truth است و bytes اصلی stale هستند. فقط objectهای untouched صلاحیت دارند
source bytes هیچ stream keywordی ندارند. body یک stream object با bytes binary opaque در قاب stream/endstream framing می‌شود، و یک scan سادهٔ reference روی دادهٔ stream فشرده یا encrypted به‌راحتی patternهایی را «پیدا» و خراب می‌کند که شبیه reference هستند. stream objectها مسیر اصلیِ stream-aware را حفظ می‌کنند
source bytes نه /StructTreeRoot را دارند و نه /StructElem. در fast profile tree structure tagged-PDF به‌جای merge شدن، drop می‌شود، پس آن objectها باید از مسیر decode عبور کنند تا engine بتواند عمداً آن‌ها را null کند

تصمیم در loop کپی per-object زندگی می‌کند. وقتی هر سه check پاس شوند، bytes object مستقیم به ShiftIndRefsInSource می‌روند و بعد به writer؛ در غیر این صورت bytes دور ریخته می‌شوند و object با GetObject rebuilt می‌شود، با ShiftIndRef shifted می‌شود، و serialize می‌شود. ساختار آن branch ارزش دیدن دارد، چون ترتیب checkها همان چیزی است که آن را امن نگه می‌دارد:

ObjectData := '';
if not Doc2.IsChangedObject(X) then
begin
  ObjectData := FastMergeObjectSource(Reader2, X);
  if (PLPos('stream', ObjectData) > 0) or
     ((not PreserveStructTree) and (PLPos('/StructTreeRoot', ObjectData) > 0)) or
     ((not PreserveStructTree) and (PLPos('/StructElem', ObjectData) > 0)) then
    ObjectData := ''                                  // fall back to decode
  else
    ObjectData := ShiftIndRefsInSource(ObjectData, Offset);
end;

if ObjectData <> '' then
  Writer.AddObject(X + Offset, Doc2.GetGenNum(X), ObjectData)
else
begin
  Obj := Doc2.GetObject(X, TempStruct);              // full parse path
  // ... null out struct-tree objects, ShiftIndRef, Obj.Output ...
end;

یک ObjectData خالی نشانهٔ آن است که مسیر byte object را رد کرده است. آن sentinel واحد مسیر fast و slow را از drift کردن بازمی‌دارد: دقیقاً یک جا تصمیم می‌دهد، و دقیقاً یک fallback

منطق جابه‌جایی مرجع‌ها و edge caseهای آن

بازنویسی byteای indirect referenceها deceptively آسان است که اشتباه انجام شود، چون R و runهای رقم در همه‌جای یک PDF object در contextهایی ظاهر می‌شوند که reference نیستند. ShiftIndRefsInSource یک scanner کوچک دست‌نویس است که bytes را یک بار می‌گردد و فقط وقتی یک number را بازنویسی می‌کند که پس از آن، با whitespace PDF بین tokenها، یک number دیگر و سپس یک R delimiter بیاید. exitهای ارزان اول می‌آیند: اگر offset صفر باشد یا source خالی باشد، bytes بدون ورود به scanner اصلاً دست‌نخورده برگردانده می‌شوند

درستی scanner به تشخیص contextهایی تکیه دارد که در آن‌ها یک sequence شبیه reference باید دست‌نخورده بماند. این‌ها boundaryهایی هستند که آسان‌ترین جا برای جا انداختن‌اند، و هر کدام صریحاً handle می‌شود:

Literal stringها که با ( و ) جدا می‌شوند، verbatim copy می‌شوند، در حالی که nesting depth track می‌شود و backslash escape رعایت می‌شود تا یک پرانتز escape‌شده depth count را به‌هم نزند. یک string مثل (see object 3 0 R for details) یک pattern مرجعِ کتابی را حمل می‌کند که در واقع فقط prose است، و باید byte-for-byte زنده بماند
Hexadecimal stringها که با < و > جدا می‌شوند، بدون تفسیر عبور داده می‌شوند. bytes 52 درون یک hex string کد ASCII برای R هستند، و یک scanner که payload هگز را متن حساب کند می‌تواند یک reference خیالی بسازد. opening << یک dictionary اول تشخیص داده می‌شود تا dictionary با hex string اشتباه گرفته نشود
Name objectها که با / شروع می‌شوند، کامل consume می‌شوند، از slash تا whitespace یا delimiter بعدی. بدون این، یک name مثل /R (یک resource key رایج) می‌تواند به‌عنوان R یک reference خوانده شود
Commentها که با % شروع می‌شوند تا انتهای line می‌روند و به‌عنوان text opaque نادیده گرفته می‌شوند
آزمون number-then-R سخت‌گیرانه است. یک reference فقط وقتی recognized می‌شود که N whitespace G whitespace R با R با whitespace، delimiter، یا end of input خاتمه یافته باشد. اگر generation number گم باشد، یا یک R با یک letter دنبال شود، digits بدون تغییر emitted می‌شوند. این همان چیزی است که integer داخل /Length 1234 و چهار number یک MediaBox را از این‌که بی‌صدا افزایش داده شوند محافظت می‌کند

هستهٔ آن آزمون سخت‌گیرانه تقریباً دقیقاً مثل جملهٔ specification خوانده می‌شود:

if (P <= N) and (Source[P] = 'R') and
   ((P = N) or PLIsPdfWhite(Source[P + 1]) or PLIsPdfDelimiter(Source[P + 1])) then
  Obj1 := PLStrToIntDef(PLCopy(Source, I, E1 - I), -1);

if Obj1 >= 0 then
begin
  AppendStr(PLIntToStr(Obj1 + Offset));   // shifted object number
  AppendBytes(E1, P - E1);                 // original whitespace + generation
  AppendBytes(P, 1);                       // the 'R'
end;

فقط object number بازنویسی می‌شود؛ generation number و همان whitespace اصلیِ بین tokenها بدون تغییر عبور داده می‌شوند، پس output به‌جز همان integerی که باید عوض می‌شد byte-identical با input است. این دقت تمام point کار است - چیزی است که reuse از source bytes را معادل با یک reserialize کامل می‌کند، نه فقط نزدیک به آن. رفتار با مجموعه‌ای متمرکز از unit testها پوشش داده شده که referenceهای ساده، reference داخل arrayها، numberهای غیرreference، literal stringها، hex stringها، و generation numberهای غیرصفر با یک offset اعمال‌شده را exercise می‌کنند

چرا bookmarkها نمی‌توانستند از AppendOutline reuse کنند

Merging multiple documents' bookmarks into one outline tree looks like a job for the existing AppendOutline helper, which already knows how to graft one document's top-level bookmarks onto another's. It is the wrong tool here, and the reason is a subtle layering mismatch. AppendOutline یک ChangeObject آخرین bookmark سطح بالا را با پیمایش reader روی bytes file اصلی پیدا می‌کند. اما fast merge ویرایش‌هایش را در یک buffer object جدید از طریق /Count stages می‌کند؛ reader هرگز آن ویرایش‌ها را نمی‌بیند. سه document یا بیشتر که chain شوند، هر append دوباره آخرین bookmark اصلی document اول را به جدیدترین document re-point می‌کند، بنابراین bookmarkهای documentهای میانی از chain خارج می‌شوند - فقط

تجمعی درست می‌ماند، و همین bug را تا وقتی کسی panel bookmark را باز نکند، آسان برای miss کردن می‌کند./Countfast path آن را با یک تزریق دو مرحله‌ای و مبتنی بر metadata حل می‌کند که هرگز reader را دوباره walk نمی‌کند. یک pass اول روی همهٔ inputها برای هر document root object outline و generation numberها، اولین و آخرین شمارهٔ bookmark سطح بالا، و /Parent ریشه را جمع می‌کند. از آن summary، code شمارهٔ object جهانیِ هر linkی را که لازم دارد forge کند محاسبه می‌کند - هر document top-level /Prev به root مشترک، /Next bookmark اول به آخرین bookmark document قبلی، /Count bookmark آخر به اولین bookmark document بعدی - با استفاده از arithmetic خالص شمارهٔ object. پشت این کار یک constraint ترتیب write وجود دارد: objectهای document اول قبل از آن‌که حتی document بعدی باز شود نوشته می‌شوند، بنابراین همهٔ editهای outline document اول (root /Last و /Next bookmark قدیمیِ آخر) باید به‌صورت arithmeticی قابل بیان باشند که به document بعدی نیاز نداشته باشد. editهای هر document بعدی بعد از open شدن اما قبل از نوشته شدن در place اعمال می‌شوند، و بنابراین از همان pathِ change-object عبور می‌کنند

invariant هم‌راستاسازی offset که همه‌چیز را به هم وصل می‌کند

هم reference shift و هم bookmark injection به یک invariant arithmetic وابسته‌اند، و این fragileترین فرض در کل design است. یک reference که به یک document بعدی inject شده به‌صورت هدف منهای Offset آن document نوشته می‌شود، تا وقتی object بعداً با ShiftIndRef(Offset) شیفت داده شد، value روی number جهانیِ موردنظر بیفتد. document اول Offset = 0 می‌گیرد و از شماره‌های جهانی مستقیم استفاده می‌کند. برای این‌که آن subtraction درست باشد، sequence offset جاری که هنگام injection استفاده می‌شود باید با sequence offsetی که objectها نهایتاً با آن نوشته می‌شوند match کند

این کار می‌کند، به‌خاطر یک property از نحوهٔ کار merge page و form: AddPages, AddFields, و AddFieldFonts فقط objectهای موجود document اول را modify می‌کنند - آن‌ها هرگز object جدید اضافه نمی‌کنند. بنابراین object count document اول در مرحلهٔ page-merge ثابت می‌ماند، و offset هر document بعدی (مجموع object count همهٔ documentهای قبلی) از injection تا write-out پایدار می‌ماند. این را بشکنید - یک stage وارد کنید که وسط merge یک object جدید بسازد - و هر reference page و bookmark پایین‌دست به تعداد objectهایی که اضافه کرده‌اید off خواهد بود. invariant آرام است، اما باربرِ اصلی است

سه entry point روی یک engine

fast path forkی از merge code نیست. در همان خط کار، byte-level engine به یک routine داخلی واحد، MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode)، factor شد، و public APIها wrapperهای نازکی شدند که دو flag را انتخاب می‌کنند:

MergeFileListFast engine را با خاموش بودن structure-tree preservation صدا می‌زند - leanest path، با drop کردن tagged-PDF tree تا byte route روی بیشترین objectها اعمال شود
MergeFileList آن را با preservation روشن صدا می‌زند، تا structure tree زنده بماند و نتیجه یک tagged PDF قابل‌استفاده بماند. این مسیر معمولی هم bookmark و form merging چندdocumentی را به ارث می‌برد
MergeFileListStrict strict mode را روشن می‌کند: pass اول metadata در اولین inputی که merge تمیز گزارش نمی‌کند متوقف می‌شود، بنابراین فقط documentهایی که قبل از file بد جمع شده‌اند شامل می‌شوند، نه این‌که file بد را رد کند و ادامه دهد

ادغام کردن pathها همچنین اجازه داد merge معمولی از یک loop دوتایی O(N²) - file یک و دو را merge کن، نتیجه را با سه merge کن، و همین‌طور ادامه بده، و accumulator در حال رشد را در هر گام دوباره parse کن - به یک pass خطی واحد که هر input را یک بار باز می‌کند، بازسازی شود. دو entry point قدیمیِ دو-file و دو-stream، MergeFiles و MergeStreams، دست‌نخورده‌اند و برای callerهایی که واقعاً یک pairwise merge می‌خواهند در دسترس باقی می‌مانند

یک note صادقانه دربارهٔ رفتار structure-tree، چون test suite را گیر انداخت. drop در fast path کامل نیست: reference catalog document اول به /StructTreeRoot را حذف می‌کند، اما خود object structure-tree هنوز به‌صورت orphan نوشته می‌شود. بنابراین bytes خروجی fast هنوز رشتهٔ /StructTreeRoot را دارند، و شما نمی‌توانید با جست‌وجوی آن رشته fast را از ordinary output تشخیص دهید - تفاوت واقعی این است که آیا catalog هنوز به structure tree می‌رسد یا نه، و همین تعیین می‌کند که file هنوز یک tagged PDF قابل navigation هست یا نه

وقتی باید سراغ کدام path بروید

byte path یک optimizationِ throughput برای assembling تعداد زیادی document است وقتی به نگه‌داشتن structure tree tagged-PDF نیاز ندارید - report bundling، statement runها، batch concatenation. در اندازه‌گیری روی mergeهای تکراریِ مجموعه‌های input متوسط تا بزرگ، byte reuse حدود چهار تا سیزده درصد از wall-clock time کم کرد بسته به object mix، بدون هیچ failure تازه‌ای روی inputهای کوچک یا malformed، چون هر objectی که scanner نتواند امن بودنش را ثابت کند به parse کامل fallback می‌کند. اگر برای accessibility به structure tree intact نیاز دارید، مسیر merge معمولیِ tagged-PDF را استفاده کنید که آن را حفظ می‌کند؛ و اگر با fileهای تکِ خیلی بزرگ به‌جای تعداد زیادی input کار می‌کنید، byte-copy techniqueهایی که در مقالهٔ همراه دربارهٔ ادغام و split PDF بزرگ با دسترسی مستقیم به فایل همان فلسفهٔ «bytes را کپی کن، از object tree کامل دوری کن» را در مقیاس file اعمال می‌کنند

رویه‌های merge و variantهای fast و strict آن بخشی از PDFlibPas Delphi PDF Library هستند، و مستنداتش مرجع کامل file-list API و گزینه‌های merge توصیف‌شده در اینجا را در خود دارند