Szybkie łączenie PDF w Delphi: przesuwanie referencji na

Konkatenacja PDF-ów brzmi jak coś, co powinno być tanie. Zawartość stron jest już ułożona, fonty są już osadzone, obrazy już skompresowane. W teorii merge to tylko księgowość: ponumerować obiekty tak, aby przestrzenie numeracji dwóch plików przestały się zderzać, zszyć drzewa stron, poprawić tabelę cross-reference i zapisać wynik. W praktyce większość implementacji merge wyrzuca tę taniość przez okno. Dla każdego obiektu w każdym pliku wejściowym wykonuje pełny parse do tokenizowanego drzewa obiektów, modyfikuje kilka referencji pośrednich, a potem serializuje drzewo z powrotem do bajtów. Parse i reserialize są drogimi połówkami całego procesu, a dla ogromnej większości obiektów produkują sekwencję bajtów prawie identyczną z tym, co weszło

PDFlibPas to natywny silnik PDF w Object Pascal dla Delphi i C++Builder, a jego szybka ścieżka merge istnieje po to, by pominąć ten pełny cykl wszędzie tam, gdzie można to bezpiecznie udowodnić. Pomysł jest wąski, ale opłaca się na całych zestawach dokumentów: dla niemodyfikowanego obiektu, który nie jest strumieniem, weź oryginalne bajty źródłowe bez zmian i wykonaj jedno przepisanie na poziomie bajtów dla zawartych w nim referencji pośrednich, zamieniając każde N G R na (N+Offset) G R. Bez tokenizer, bez drzewa obiektów, bez serializer. Ten artykuł przechodzi przez to, gdzie taki skrót jest legalny, jak działa parser state machine wykonujący przepisanie bajtów bez korumpowania czegokolwiek, dlaczego merge zakładek wymagało zupełnie innego mechanizmu i jak równocześnie przebudowano zwykłą ścieżkę merge z kwadratowej na liniową

Dlaczego prawdziwym kosztem merge jest renumeracja obiektów

Każdy PDF niesie własną przestrzeń numeracji obiektów. Plik A ma obiekt 1, obiekt 2 i tak dalej, plik B ma własny obiekt 1, obiekt 2 i tak dalej. Nie możesz wrzucić obiektów B do pliku A bez zmian, bo numery by się zderzyły, a każda referencja pośrednia wewnątrz B zaczęłaby wskazywać na zły obiekt. Naprawą jest offset: jeśli A kończy się na liczbie obiektów Offset, to obiekt N z B staje się obiektem N+Offset w wyniku, a każda referencja N G R pojawiająca się gdziekolwiek w obiektach B musi zostać przesunięta do (N+Offset) G R, aby wszystko się zgadzało

To przesunięcie jest całym semantycznym zadaniem przy merge korpusu pliku. Poprawki w drzewie stron i merge AcroForm to małe, ograniczone edycje na kilku obiektach. Zasadnicza robota polega na przepisywaniu referencji w tysiącach obiektów, a naiwny sposób to parsowanie każdego obiektu, aby znajdować te referencje strukturalnie. MergeFileListFast w PDFlibPas przyjmuje podejście odwrotne: referencje da się znaleźć również w surowych bajtach, jeśli tylko ostrożnie obchodzisz się z kontekstami, w których sekwencja cyfra-spacja-cyfra-spacja-R nie jest referencją. Pomiń parse, przesuń wszystko in place, a koszt per obiekt sprowadza się do jednego liniowego przebiegu po bajtach, które i tak zamierzałeś kopiować

Kiedy ponowne użycie bajtów źródłowych jest dowodliwie bezpieczne

Ścieżka bajtowa jest wybierana tylko wtedy, gdy dla obiektu kopiowanego z kolejnego dokumentu jednocześnie spełnione są trzy warunki. Jeśli zawiedzie choć jeden z nich, obiekt wraca na pełną ścieżkę decode-and-reserialize, więc poprawność zawsze wygrywa z szybkością:

Doc2.IsChangedObject(X) ma wartość False. Jeśli silnik merge już zmodyfikował obiekt w pamięci, na przykład obiekt strony, którego /Parent zostało przepięte, to drzewo w pamięci jest źródłem prawdy, a oryginalne bajty są już nieaktualne. Kwalifikują się tylko obiekty nietknięte
Bajty źródłowe nie zawierają słowa stream. Ciało obiektu strumieniowego jest nieprzezroczystym binarnym blokiem otoczonym przez stream/endstream, a naiwny skan referencji nad skompresowanymi albo zaszyfrowanymi danymi strumienia z radością „odkryłby” i uszkodził wzorce bajtów wyglądające jak referencje. Obiekty strumieniowe zostają na oryginalnej ścieżce świadomej strumieni
Bajty źródłowe nie zawierają ani /StructTreeRoot, ani /StructElem. W szybkim profilu tagged PDF structure tree jest porzucane zamiast mergowane, więc takie obiekty muszą przejść przez ścieżkę decode, gdzie silnik może je celowo wyzerować

Ta decyzja zapada w pętli kopiowania per obiekt. Gdy wszystkie trzy kontrole przejdą, bajty obiektu trafiają prosto do ShiftIndRefsInSource, a potem do writer; w przeciwnym razie bajty są odrzucane, a obiekt odbudowywany przy użyciu GetObject, przesuwany przez ShiftIndRef i serializowany. Strukturę tego rozgałęzienia warto zobaczyć, bo to właśnie kolejność kontroli utrzymuje wszystko w bezpieczeństwie:

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;

Puste ObjectData jest sygnałem, że ścieżka bajtowa odrzuciła obiekt. Ten pojedynczy sentinel utrzymuje szybkie i wolne ścieżki w zbieżności: istnieje dokładnie jedno miejsce podejmujące decyzję i dokładnie jeden fallback

State machine do przesuwania referencji i jego przypadki brzegowe

Przepisanie referencji pośrednich na poziomie bajtów jest zdradliwie łatwe do zepsucia, ponieważ R oraz ciągi cyfr pojawiają się wszędzie w obiekcie PDF także w kontekstach, które nie są referencjami. ShiftIndRefsInSource to niewielki ręcznie napisany skaner, który przechodzi po bajtach jeden raz i przepisuje liczbę tylko wtedy, gdy po niej, z odstępami PDF whitespace między tokenami, następuje druga liczba, a potem separator R. Tanie wyjścia pojawiają się najpierw: jeśli offset wynosi zero albo źródło jest puste, bajty są zwracane bez zmian, bez wchodzenia do skanera

Poprawność skanera opiera się na rozpoznawaniu kontekstów, w których sekwencję wyglądającą jak referencja trzeba zostawić w spokoju. To granice, które najłatwiej przeoczyć, i każda z nich jest obsługiwana jawnie:

Literal strings ograniczone przez ( oraz ) są kopiowane dosłownie, z pilnowaniem głębokości zagnieżdżenia i respektowaniem backslash escape, tak aby escapowany nawias nie rozstroił licznika głębokości. String taki jak (see object 3 0 R for details) zawiera książkowy wzorzec referencji, który w rzeczywistości jest po prostu tekstem, i musi przetrwać bajt w bajt
Hexadecimal strings ograniczone przez < oraz > są przepuszczane bez interpretacji. Bajty 52 wewnątrz stringu heksadecymalnego to kod ASCII dla R, a skaner traktujący payload hex jako tekst mógłby wyprodukować fantomową referencję. Otwarcie << słownika jest wykrywane najpierw, aby nie pomylić słownika ze stringiem heksadecymalnym
Name objects zaczynające się od / są konsumowane w całości, od ukośnika do kolejnego whitespace albo separatora. Bez tego nazwa taka jak /R, czyli częsty klucz zasobu, mogłaby zostać odczytana jako R referencji
Comments wprowadzane przez % biegną do końca linii i są pomijane jako nieprzezroczysty tekst
Test liczba-potem-R jest rygorystyczny. Referencja jest rozpoznawana tylko jako N whitespace G whitespace R z R zakończonym przez whitespace, separator albo koniec wejścia. Jeśli brakuje generation number albo R jest kontynuowane literą, cyfry są wypisywane bez zmian. To właśnie chroni integer w /Length 1234 oraz cztery liczby w MediaBox przed cichym inkrementowaniem

Sedno tego rygorystycznego testu czyta się niemal dokładnie tak, jak opisuje to zdanie w specyfikacji:

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;

Przepisywany jest tylko numer obiektu, generation number oraz dokładny oryginalny whitespace między tokenami są kopiowane dalej, dzięki czemu wyjście jest bajtowo identyczne z wejściem z wyjątkiem jednego integera, który naprawdę musiał się zmienić. Ta precyzja jest tu całym sednem, bo właśnie ona sprawia, że ponowne użycie bajtów źródłowych jest równoważne pełnemu reserialize, a nie tylko do niego zbliżone. Zachowanie jest pokryte skupionym zestawem testów jednostkowych sprawdzających gołe referencje, referencje w tablicach, liczby niebędące referencjami, literal strings, hex strings oraz niezerowe generation numbers z zastosowanym offset

Dlaczego zakładki nie mogły ponownie użyć AppendOutline

Merge zakładek z wielu dokumentów do jednego drzewa outline wygląda jak robota dla istniejącej funkcji AppendOutline, która już wie, jak doszczepić zakładki najwyższego poziomu jednego dokumentu do drugiego. Tutaj to jednak złe narzędzie, a powodem jest subtelna niezgodność warstw. AppendOutline znajduje bieżącą ostatnią zakładkę najwyższego poziomu, przechodząc czytnikiem po oryginalnych bajtach pliku. Ale szybki merge etapuje swoje edycje w buforze new-objects przez ChangeObject; reader nigdy tych edycji nie widzi. Połącz trzy lub więcej dokumentów i każdy append przepina oryginalną ostatnią zakładkę pierwszego dokumentu na najnowszy dokument, więc wszystkie zakładki dokumentów pośrednich wypadają z łańcucha — poprawne pozostaje tylko skumulowane /Count, co sprawia, że błąd łatwo przeoczyć, dopóki ktoś nie otworzy panelu zakładek

Szybka ścieżka rozwiązuje to dwuetapowym, sterowanym metadanymi wstrzyknięciem, które nigdy ponownie nie przechodzi przez reader. Pierwszy przebieg po wszystkich wejściach zbiera dla każdego dokumentu numer obiektu korzenia outline i generation number, numery pierwszej i ostatniej zakładki najwyższego poziomu oraz /Count korzenia. Na podstawie tego podsumowania kod oblicza globalne numery obiektów dla każdego linku, który musi wykonać — /Parent każdej zakładki najwyższego poziomu dokumentu do wspólnego korzenia, /Prev pierwszej zakładki do ostatniej zakładki poprzedniego dokumentu, /Next ostatniej zakładki do pierwszej zakładki kolejnego dokumentu — wyłącznie przez arytmetykę numerów obiektów. Stoi za tym ograniczenie kolejności zapisu: obiekty pierwszego dokumentu są wypisywane jeszcze zanim otworzy się którykolwiek kolejny dokument, więc wszystkie edycje outline pierwszego dokumentu, root /Count oraz /Last, a także /Next starej ostatniej zakładki, muszą dać się wyrazić jako arytmetyka niewymagająca trzymania późniejszego dokumentu w ręku. Edycje każdego kolejnego dokumentu są stosowane in place po jego otwarciu, ale przed zapisaniem, więc wychodzą tą samą ścieżką change object

Inwariant zgodności offsetów, który spina to w całość

Zarówno przesuwanie referencji, jak i wstrzykiwanie zakładek zależą od jednego inwariantu arytmetycznego i to jest najbardziej kruche założenie w całym projekcie. Referencja wstrzykiwana do kolejnego dokumentu jest zapisywana jako docelowy globalny numer obiektu minus Offset tego dokumentu, tak aby gdy obiekt zostanie później przesunięty przez ShiftIndRef(Offset), wartość trafiła w zamierzony numer globalny. Pierwszy dokument dostaje Offset = 0 i używa numerów globalnych bezpośrednio. Aby to odejmowanie było poprawne, bieżąca sekwencja offsetów używana podczas wstrzykiwania musi zgadzać się z sekwencją offsetów używaną przy ostatecznym wypisywaniu obiektów

Tak właśnie jest z powodu własności działania merge stron i formularzy: AddPages, AddFields oraz AddFieldFonts modyfikują tylko istniejące obiekty pierwszego dokumentu — nigdy nie dodają nowych. Dlatego liczba obiektów w pierwszym dokumencie nie zmienia się podczas etapu merge stron, a offset każdego kolejnego dokumentu, suma liczby obiektów wszystkich poprzednich dokumentów, pozostaje stabilny od wstrzyknięcia aż po zapis. Złam to, wprowadzając etap tworzący nowy obiekt w środku merge, a każda referencja do strony i zakładki dalej w dół przesunie się o liczbę dodanych obiektów. Inwariant jest cichy, ale dźwiga cały ciężar

Trzy punkty wejścia nad jednym silnikiem

Szybka ścieżka nie jest forkiem kodu merge. W ramach tej samej pracy silnik bajtowy został wyodrębniony do jednej wewnętrznej procedury MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), a publiczne API stały się cienkimi wrapperami wybierającymi dwa flagi:

MergeFileListFast wywołuje silnik z wyłączonym zachowaniem structure tree — to najlżejsza ścieżka, porzucająca drzewo tagged PDF, aby droga bajtowa mogła objąć jak najwięcej obiektów
MergeFileList wywołuje go z zachowaniem włączonym, dzięki czemu structure tree przetrwa, a wynik pozostaje użytecznym tagged PDF. Ta zwykła ścieżka dziedziczy także merge zakładek i formularzy dla wielu dokumentów
MergeFileListStrict włącza strict mode: pierwszy przebieg metadanych zatrzymuje się na pierwszym wejściu, które nie raportuje czystego merge, więc uwzględniane są tylko dokumenty zebrane przed złym plikiem, zamiast pomijać zły plik i iść dalej

Złożenie ścieżek w jedno pozwoliło również przebudować zwykły merge z parowej pętli O(N²), czyli merge pliku pierwszego z drugim, potem tego wyniku z trzecim i tak dalej, z ponownym parsowaniem rosnącego akumulatora na każdym kroku, do pojedynczego liniowego przebiegu otwierającego każde wejście tylko raz. Dwa długo istniejące punkty wejścia, dla dwóch plików i dwóch strumieni, MergeFiles oraz MergeStreams, pozostają nietknięte i nadal są dostępne dla wywołujących, którzy rzeczywiście potrzebują pairwise merge

Jedna uczciwa uwaga o zachowaniu structure tree, bo ugryzło to zestaw testów. „Drop” w szybkiej ścieżce nie jest całkowity: usuwa referencję katalogu pierwszego dokumentu do /StructTreeRoot, ale sam obiekt structure tree nadal jest wypisywany jako sierota. Dlatego bajty szybkiego wyjścia nadal zawierają string /StructTreeRoot i nie da się odróżnić szybkiego wyjścia od zwykłego przez samo szukanie tego stringu — prawdziwa różnica polega na tym, czy katalog nadal sięga do structure tree, bo to właśnie decyduje, czy plik nadal jest nawigowalnym tagged PDF

Kiedy sięgać po którą ścieżkę

Ścieżka bajtowa to optymalizacja przepustowości przy składaniu wielu dokumentów, gdy nie potrzebujesz zachowania tagged PDF structure tree, na przykład przy pakietowaniu raportów, przebiegach wyciągów albo batch concatenation. W pomiarach na powtarzanych merge średnich i dużych zestawów wejściowych ponowne użycie bajtów obcinało mniej więcej od czterech do trzynastu procent czasu ściennego, zależnie od mieszanki obiektów, bez wprowadzania nowych awarii dla małych albo uszkodzonych wejść, ponieważ każdy obiekt, którego skaner nie potrafił uznać za bezpieczny, wracał do pełnego parse. Jeśli natomiast potrzebujesz nienaruszonego structure tree ze względów dostępności, użyj zwykłej ścieżki merge tagged PDF, która je zachowuje; a jeśli pracujesz raczej z pojedynczymi bardzo dużymi plikami niż z wieloma wejściami, techniki kopiowania bajtów opisane w tekście uzupełniającym o merge i split dużych PDF z bezpośrednim dostępem do pliku stosują tę samą filozofię „kopiuj bajty, unikaj pełnego drzewa obiektów” w skali całego pliku

Procedury merge oraz ich szybkie i rygorystyczne warianty są częścią PDFlibPas Delphi PDF Library, której dokumentacja zawiera pełne odniesienie do file-list API i opcji merge opisanych tutaj

Szybkie łączenie PDF w Delphi: przesuwanie referencji na poziomie bajtów