Mesclagem Rápida de PDF no Delphi

Concatenar PDFs parece que deveria ser algo simples. O conteúdo da página já está estruturado, as fontes já estão incorporadas, as imagens já estão compactadas. Em princípio, uma mesclagem é apenas contabilidade: renumerar os objetos para que os espaços de numeração dos dois arquivos parem de colidir, juntar as árvores de páginas, corrigir a tabela de referência cruzada e gravar. Na prática, a maioria dos códigos de mesclagem descarta essa simplicidade. Para cada objeto em cada arquivo de entrada, ele executa uma análise completa em uma árvore de objetos tokenizados, altera algumas referências indiretas e, em seguida, serializa a árvore de volta em bytes. A análise e a resserialização são as metades caras e, para a grande maioria dos objetos, elas produzem uma sequência de bytes quase idêntica à que entrou

O PDFlibPas é um mecanismo PDF em Object Pascal nativo para Delphi e C++Builder, e seu caminho de mesclagem rápida existe para ignorar esse ciclo onde quer que seja comprovadamente seguro. A ideia é restrita, mas compensa em conjuntos inteiros de documentos: para um objeto que não é de fluxo e que não foi modificado, pega-se os bytes de origem originais textualmente e faz-se uma única reescrita em nível de byte das referências indiretas que eles contêm, transformando cada N G R em (N+Offset) G R. Sem tokenizador, sem árvore de objetos, sem serializador. Este artigo detalha onde esse atalho é legal, a máquina de estados do analisador que executa a reescrita de bytes sem corromper nada, por que a mesclagem de favoritos precisou de um mecanismo totalmente diferente e como o caminho de mesclagem comum foi reconstruído de quadrático para linear ao mesmo tempo

Por que a renumeração de objetos é o custo real de uma mesclagem

Cada PDF possui seu próprio espaço de numeração de objetos. O arquivo A tem o objeto 1, o objeto 2, e assim por diante; o arquivo B tem seu próprio objeto 1, objeto 2, e assim por diante. Você não pode simplesmente soltar os objetos do arquivo B no arquivo A sem alterações, porque os números colidiriam e cada referência indireta dentro do arquivo B agora se resolveria para o objeto errado. A solução é um deslocamento: se o arquivo A termina na contagem de objetos Offset, então o objeto N do arquivo B se torna o objeto N+Offset na saída, e cada referência N G R que aparece em qualquer lugar dentro dos objetos do arquivo B deve ser deslocada para (N+Offset) G R para corresponder

Esse deslocamento é todo o trabalho semântico de mesclar o corpo. As correções da árvore de páginas e a mesclagem do AcroForm são edições pequenas e limitadas em um punhado de objetos. O trabalho em massa é reescrever referências em milhares de objetos, e a maneira ingênua de fazer isso é analisar cada objeto para que você possa encontrar as referências estruturalmente. A função MergeFileListFast do PDFlibPas adota a visão oposta: as referências também podem ser encontradas nos bytes brutos, desde que você tome cuidado com os contextos em que uma sequência de dígito-espaço-dígito-espaço-R não é uma referência. Ignore a análise, desloque no local, e o custo por objeto entra em colapso para uma única varredura linear de bytes que você já iria copiar de qualquer maneira

Quando a reutilização de bytes de origem é comprovadamente segura

O caminho do byte só é seguido quando três condições são válidas para o objeto sendo copiado de um documento subsequente. A falha em qualquer uma delas envia o objeto de volta pelo caminho completo de decodificação e resserialização, portanto a correção sempre vence a velocidade:

Doc2.IsChangedObject(X) é False. Se o mecanismo de mesclagem já alterou o objeto na memória (um objeto de página cujo /Parent foi apontado novamente, por exemplo), a árvore na memória é a fonte da verdade e os bytes originais estão desatualizados. Apenas objetos intactos se qualificam
Os bytes de origem não contêm a palavra-chave stream. O corpo de um objeto de fluxo é um binário opaco delimitado por stream/endstream, e uma varredura de referência ingênua sobre dados de fluxo compactados ou criptografados encontraria alegremente e corromperia padrões de bytes que se parecem com referências. Objetos de fluxo mantêm o caminho original ciente do fluxo
Os bytes de origem não contêm nem /StructTreeRoot nem /StructElem. No perfil rápido, a árvore de estrutura do PDF etiquetado (tagged PDF) é descartada em vez de mesclada, portanto esses objetos devem passar pelo caminho de decodificação onde o mecanismo pode anulá-los deliberadamente

A decisão reside no loop de cópia por objeto. Quando todas as três verificações passam, os bytes do objeto vão direto para ShiftIndRefsInSource e depois para o gravador; caso contrário, os bytes são descartados e o objeto é reconstruído com GetObject, deslocado com ShiftIndRef e serializado. Vale a pena ver a estrutura dessa ramificação, pois a ordem das verificações é o que a mantém segura:

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;

Um ObjectData vazio é o sinal de que o caminho do byte recusou o objeto. Essa única sentinela evita que as rotas rápidas e lentas se distanciem: existe exatamente um lugar que decide e exatamente uma alternativa de fallback

A máquina de estados de deslocamento de referência e seus casos de borda

Uma reescrita de bytes de referências indiretas é enganosamente fácil de errar, porque R e sequências de dígitos aparecem por todo o objeto PDF em contextos que não são referências. O ShiftIndRefsInSource é um pequeno analisador escrito à mão que varre os bytes uma vez e só reescreve um número quando este é seguido, com espaço em branco de PDF entre os tokens, por outro número e então um delimitador R. As saídas rápidas vêm primeiro: se o deslocamento for zero ou a origem estiver vazia, os bytes são retornados intactos sem sequer entrar no analisador

A correção do analisador reside no reconhecimento dos contextos onde uma sequência com formato de referência deve ser deixada em paz. Esses são os limites mais fáceis de perder, e cada um é tratado explicitamente:

Strings literais delimitadas por ( e ) são copiadas textualmente, rastreando a profundidade de aninhamento e respeitando o caractere de escape de barra invertida para que um parêntese com escape não desregule a contagem de profundidade. Uma string como (see object 3 0 R for details) contém um padrão de referência clássico que na verdade é apenas prosa, e deve sobreviver byte a byte
Strings hexadecimais delimitadas por < e > são repassadas sem interpretação. Os bytes 52 dentro de uma string hexadecimal são o código ASCII para R, e um analisador que tratasse a carga útil hexadecimal como texto poderia fabricar uma referência fantasma. A abertura << de um dicionário é detectada primeiro para que um dicionário não seja confundido com uma string hexadecimal
Objetos de nome que começam com / são consumidos por inteiro, da barra até o próximo espaço em branco ou delimitador. Sem isso, um nome como /R (uma chave de recurso comum) poderia ser lido como o R de uma referência
Comentários introduzidos por % estendem-se até o final da linha e são ignorados como texto opaco
O teste de número-seguido-por-R é rigoroso. Uma referência só é reconhecida como N espaço em branco G espaço em branco R com o R terminado por espaço em branco, um delimitador ou fim da entrada. Se o número de geração estiver faltando, ou se um R for seguido por uma letra, os dígitos são emitidos inalterados. Isso é o que protege o inteiro em /Length 1234 e os quatro números de um MediaBox de serem incrementados silenciosamente

O coração desse teste rigoroso é lido quase exatamente como a frase de especificação o descreve:

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;

Apenas o número do objeto é reescrito; o número de geração e o espaçamento em branco original exato entre os tokens são copiados, de modo que a saída é byte-idêntica à de entrada, exceto pelo único inteiro que teve de mudar. Essa precisão é todo o objetivo — é o que torna a reutilização de bytes de origem equivalente a uma resserialização completa, e não apenas próxima a ela. O comportamento é coberto por um conjunto focado de testes unitários que exercitam referências simples, referências dentro de arrays, números que não são referências, strings literais, strings hexadecimais e números de geração diferentes de zero com um deslocamento aplicado

Por que os favoritos não puderam reutilizar o AppendOutline

Mesclar os favoritos de múltiplos documentos em uma árvore de contorno única parece ser um trabalho para o auxiliar AppendOutline existente, que já sabe como enxertar os favoritos de nível superior de um documento em outro. No entanto, é a ferramenta errada aqui, e o motivo é um sutil descompasso de camadas. O AppendOutline localiza o último favorito de nível superior atual varrendo o leitor sobre os bytes originais do arquivo. Mas a mesclagem rápida prepara suas edições em um buffer de novos objetos através de ChangeObject; o leitor nunca vê essas edições. Ao encadear três ou mais documentos, cada anexo aponta novamente o último favorito original do primeiro documento para o documento mais recente, de modo que todos os favoritos dos documentos intermediários caem da cadeia — apenas o /Count cumulativo permanece correto, o que torna o bug fácil de passar despercebido até que alguém abra o painel de favoritos

O invariante de alinhamento de deslocamento que une tudo

Tanto o deslocamento de referência quanto a injeção de favoritos dependem de um invariante aritmético, e essa é a suposição mais frágil em todo o projeto. Uma referência injetada em um documento subsequente é escrita como o número do objeto global de destino menos o Offset daquele documento, de modo que quando o objeto for posteriormente deslocado por ShiftIndRef(Offset) o valor termine no número global pretendido. O primeiro documento recebe Offset = 0 e usa números globais diretamente. Para que essa subtração seja correta, a sequência de deslocamento em execução usada durante a injeção deve corresponder à sequência de deslocamento usada quando os objetos são finalmente gravados

E corresponde, devido a uma propriedade de como as mesclagens de página e formulário funcionam: AddPages, AddFields e AddFieldFonts apenas modificam os objetos existentes do primeiro documento — eles nunca adicionam novos. Portanto, a contagem de objetos do primeiro documento permanece inalterada durante a etapa de mesclagem de páginas, e o deslocamento de cada documento subsequente (a soma das contagens de objetos de todos os documentos precedentes) permanece estável desde a injeção até a gravação. Se quebrar isso — introduzir uma etapa que crie um novo objeto no meio da mesclagem — cada referência de página e favorito posterior estaria incorreta pela contagem de objetos que você adicionou. O invariante é silencioso, mas é estrutural

Três pontos de entrada sobre um único mecanismo

O caminho rápido não é uma ramificação (fork) do código de mesclagem. Na mesma linha de trabalho, o mecanismo em nível de byte foi fatorado em uma única rotina interna, MergeFileListInternal(ListName, OutputFileName, PreserveStructTree, StrictMode), e as APIs públicas tornaram-se wrappers finos que escolhem dois sinalizadores:

O MergeFileListFast chama o mecanismo com a preservação da árvore de estrutura desativada — o caminho mais enxuto, descartando a árvore do PDF etiquetado para que a rota de bytes se aplique à maioria dos objetos
O MergeFileList chama o mecanismo com a preservação ativada, para que a árvore de estrutura sobreviva e o resultado continue sendo um PDF etiquetado utilizável. Este caminho comum também herda a mesclagem de favoritos e formulários de múltiplos documentos
O MergeFileListStrict ativa o modo estrito: a primeira passagem de metadados para na primeira entrada que não relata uma mesclagem limpa, de modo que apenas os documentos coletados antes do arquivo problemático são incluídos, em vez de pular o arquivo com erro e continuar

A união dos caminhos também permitiu que a mesclagem comum fosse reconstruída de um loop par a par O(N²) — mesclar os arquivos um e dois, mesclar esse resultado com o três, e assim por diante, analisando novamente o acumulador crescente a cada passo — para uma única passagem linear que abre cada entrada uma única vez. Os dois pontos de entrada antigos de dois arquivos e dois fluxos, MergeFiles and MergeStreams, permanecem intocados e continuam disponíveis para chamadores que genuinamente desejam uma mesclagem par a par

Uma nota honesta sobre o comportamento da árvore de estrutura, porque isso afetou a suíte de testes. O "descarte" do caminho rápido não é total: ele remove a referência de catálogo do primeiro documento para o /StructTreeRoot, mas o próprio objeto da árvore de estrutura ainda é gravado como órfão. Portanto, os bytes da saída rápida ainda contêm a string /StructTreeRoot, e você não pode distinguir a saída rápida da comum simplesmente procurando por essa string — a verdadeira diferença é se o catálogo ainda alcança a árvore de estrutura, o que determina se o arquivo ainda é um PDF etiquetado navegável

Quando recorrer a qual caminho

O caminho de byte é uma otimização de taxa de transferência (throughput) para a montagem de muitos documentos onde você não precisa da preservação da árvore de estrutura de PDF etiquetado — agrupamento de relatórios, execuções de extratos, concatenação em lote. Medido em mesclagens repetidas de conjuntos de entradas de médio a grande porte, a reutilização de bytes reduziu cerca de quatro a treze por cento do tempo de relógio, dependendo da mistura de objetos, sem novas falhas em entradas pequenas ou malformadas, porque qualquer objeto que o analisador não possa comprovar segurança retorna para a análise completa. Se você precisa da árvore de estrutura intacta para acessibilidade, use o caminho comum de mesclagem PDF etiquetado, que a preserva; e se você estiver trabalhando com arquivos individuais muito grandes em vez de muitas entradas, as técnicas de cópia de bytes descritas no artigo complementar sobre mesclagem e divisão de PDFs grandes com acesso direto ao arquivo aplicam a mesma filosofia de "copiar bytes, evitar a árvore de objetos completa" em escala de arquivo

As rotinas de mesclagem e suas variantes rápidas e estritas fazem parte da Biblioteca PDF PDFlibPas Delphi, cuja documentação traz a referência completa para a API de lista de arquivos e as opções de mesclagem descritas aqui

Mesclagem Rápida de PDF no Delphi: Deslocamento de Referência em Nível de Byte