Monte um PDF cuja name tree /Dests tem uma raiz com dois filhos. O primeiro filho declara /Limits [(a) (z)], e o array /Kids dele aponta direto de volta para a raiz. O segundo filho guarda a entrada real de (chapter7), mas os limits dele estão escritos ao contrário: [(z) (a)]. Pergunte a uma lookup de name tree de livro didático por chapter7 e ela ou recursa até a stack acabar, ou retorna "não encontrado" para um destino que um viewer consegue alcançar. O arquivo inteiro cabe em cerca de dois kilobytes, e todo objeto nele parseia limpo
Esse arquivo embarca três armadilhas separadas numa estrutura só: um ciclo de /Kids, uma faixa que alega uma key que não guarda, e uma faixa que nunca pode casar com nada. Uma quarta armadilha precisa de um arquivo bem maior. Quando uma única leaf carrega mais de 32.768 pares name/value, qualquer código que comprima "qual leaf" e "qual entrada" num único inteiro de 32 bits começa a apontar para o par errado. O resto deste artigo percorre cada armadilha, o que um reader deve fazer a respeito, e como as chamadas Delphi se comportam em arquivos montados assim
Quatro features PDF que se apoiam em name trees e number trees
Name trees e number trees sustentam toda feature PDF que mapeia um conjunto grande de keys para objetos, e o PDFlibPas, a PDF Library for Delphi da losLab, expõe quatro delas por métodos públicos de TPDFlib. O ISO 32000-1 §7.9.6 define a name tree (keys string, Table 36) e o §7.9.7 a number tree (keys inteiras, Table 37). Raiz e nós intermediários carregam /Kids; leaves carregam pares key/value ordenados em /Names ou /Nums; todo nó não raiz deveria carregar um array /Limits de dois elementos segurando a menor e a maior key abaixo dele
| Árvore | Onde vive | Especificação | API de leitura do PDFlibPas |
|---|---|---|---|
| Named destinations | /Dests no name dictionary | §12.3.2.3 | GetNamedDestination, depois GetDestPage / GetDestType |
| Page labels | /PageLabels no catalog (number tree) | §12.4.2 | GetPageLabel |
| Attachments | /EmbeddedFiles no name dictionary | §7.7.4, §7.11.4 | EmbeddedFileCount, GetEmbeddedFileStrProperty |
| JavaScript de nível de documento | /JavaScript no name dictionary | §7.7.4 | GlobalJavaScriptCount, GlobalJavaScriptPackageName |
Duas linhas escondem uma ruga. Named destinations também existem numa forma mais velha do PDF 1.1, um dicionário /Dests simples no catalog chaveado por name objects, e o GetNamedDestination confere esse dicionário primeiro e só depois desce a name tree do PDF 1.2. A linha de JavaScript tem um quase homônimo que lê outra coisa completamente: o GetDocJavaScript retorna scripts anexados aos document triggers no dicionário /AA do catalog (WS, DS, WP, DP, DC), enquanto os named packages que rodam quando um documento abre vivem na name tree /JavaScript e são listados pelo GlobalJavaScriptPackageName
Todas essas estruturas vêm do arquivo. A especificação diz a um writer o que ele deve produzir, e um reader ainda recebe o que quer que o writer, um incremental save quebrado ou um fuzzer tenham realmente posto lá. É a mesma lição de endurecer um parser PDF Pascal contra arquivos maliciosos, aplicada à forma da árvore em vez de comprimentos de buffer
Por que um array /Kids cíclico crasha um tree walker recursivo?
Um walker recursivo crasha num array /Kids cíclico porque nada na recursão lembra quais nós ele já entrou, então uma referência de filho a um ancestral transforma um arquivo finito numa descida sem fim. Uma árvore legítima pode causar o mesmo dano sem ciclo nenhum: uma cadeia de 4.096 níveis de nós de filho único é sintaxe válida que custa a um reader recursivo 4.096 stack frames
A variante mais branda nem crasha. Quando duas entradas /Kids referenciam a mesma leaf, uma enumeração ingênua a visita duas vezes, então uma contagem de attachments volta maior que o número de arquivos no documento e uma lista de scripts mostra o mesmo pacote duas vezes
O PDFlibPas caminha nos dois tipos de árvore com uma stack explícita last-in, first-out no heap mais um visited set chaveado pela identidade do dicionário. Um nó é marcado quando é retirado da stack. Uma referência cíclica pode ficar na stack por um momento, mas é descartada assim que volta para cima, e cada nó distinto expande os filhos dele exatamente uma vez. O trabalho total é limitado pelo número de dicionários distintos mais o comprimento combinado dos arrays /Kids deles; uma cadeia de 4.096 níveis vira 4.096 iterações de loop e 4.096 entradas de hash set
A ordem é a parte em que as pessoas erram ao converter recursão em loop. Uma stack inverte o que você põe nela, então os filhos precisam ser empurrados do último índice para baixo até o primeiro; assim o filho mais à esquerda sai da stack primeiro e as leaves saem na ordem da esquerda para a direita em que o producer as escreveu. Marcar ao retirar da stack em vez de ao empurrar importa pelo mesmo motivo. Com marcas ao empurrar e pushes da direita para a esquerda, uma leaf compartilhada pelas posições 0 e 2 seria reivindicada pela posição 2, e as entradas dela apareceriam depois do que o arquivo diz. Page labels dependem dessa ordem, como a última seção mostra
Se você escrever o seu próprio código de árvore contra algum outro object model, esta é a forma que recomendamos. O tipo de nó abaixo é deliberadamente abstrato, e as duas funções são código do lado do reader, não chamadas de library
uses
System.Generics.Collections;
type
TTreeNode = class
public
Kids: TArray<TTreeNode>; // vazio numa leaf
Keys: TArray<string>; // keys da leaf, ordenadas por um producer bem comportado
Values: TArray<Integer>; // paralelo a Keys
HasLimits: Boolean;
LoKey, HiKey: string;
end;
// Helper seu: /Limits só pode podar quando é um par bem formado e ordenado
function LimitsExclude(Node: TTreeNode; const Key: string): Boolean;
begin
Result := Node.HasLimits and (Node.LoKey <= Node.HiKey) and
((Key < Node.LoKey) or (Key > Node.HiKey));
end;
// Lookup sua: stack explícita, visited set, marca ao retirar da stack
function FindValue(Root: TTreeNode; const Key: string;
out Value: Integer): Boolean;
var
Pending: TList<TTreeNode>;
Visited: TDictionary<TTreeNode, Byte>;
Node: TTreeNode;
I: Integer;
begin
Result := False;
Value := 0;
if Root = nil then
Exit;
Pending := TList<TTreeNode>.Create;
Visited := TDictionary<TTreeNode, Byte>.Create;
try
Pending.Add(Root);
while Pending.Count > 0 do
begin
Node := Pending[Pending.Count - 1];
Pending.Delete(Pending.Count - 1);
if Visited.ContainsKey(Node) then
Continue; // ciclo ou filho compartilhado: já visto
Visited.Add(Node, 0);
if Length(Node.Kids) > 0 then
begin
// Empurre da direita para a esquerda para que o filho mais à esquerda saia primeiro
for I := High(Node.Kids) downto 0 do
if (Node.Kids[I] <> nil) and not LimitsExclude(Node.Kids[I], Key) then
Pending.Add(Node.Kids[I]);
end
else
for I := 0 to High(Node.Keys) do
if (Node.Keys[I] = Key) and (I <= High(Node.Values)) then
begin
Value := Node.Values[I];
Exit(True);
end;
// Um miss nesta leaf: continue retirando os siblings dela
end;
finally
Visited.Free;
Pending.Free;
end;
end;
Um miss num ramo não diz nada sobre a árvore
O atalho de lookup mais comum escolhe o primeiro filho cujo /Limits cobre a key, desce nele, e nunca mais olha um sibling. Numa árvore limpa isso é correto e rápido. No arquivo do parágrafo de abertura falha: o primeiro filho alega chapter7, leva de volta à raiz, e a busca termina de mãos vazias enquanto o próximo sibling guarda a entrada
O PDFlibPas não para no primeiro ramo plausível. A lookup por key por trás do GetNamedDestination empurra todo filho cuja faixa não exclua a key, e continua retirando da stack até achar um match ou a stack esvaziar. Numa árvore bem formada com faixas disjuntas, no máximo um filho sobrevive à checagem de faixa em cada nível, então o custo extra é nulo. Numa árvore danificada são um punhado de visitas extras de nó, e a resposta volta certa
Leaves recebem o mesmo tratamento. O ISO 32000-1 exige que as keys num array /Names estejam ordenadas por valor de byte, então a library tenta uma binary search primeiro. Quando ela erra, cai para um scan linear dos pares, porque uma leaf fora de ordem faria uma key presente ficar invisível. Pagar um scan linear em todo miss genuíno é um custo que aceitamos: lookups por nomes genuinamente ausentes são raros, e um "não encontrado" falso num link funcional custa muito mais que uma passada extra sobre uma leaf
Uma contradição estrutural é tratada com recusa. A Table 36 permite que um nó carregue /Kids ou /Names, nunca os dois. Uma lookup por key trata um nó carregando os dois como malformado e o pula em vez de adivinhar qual metade o producer queria. A enumeração de number trees, como a caminhada por trás do GetPageLabel, é mais tolerante e segue /Kids quando ambos estão presentes, já que descartar uma faixa inteira rotularia errado toda página depois dela
Para que um reader pode confiar no /Limits?
Um reader pode confiar no /Limits para pular trabalho, e só quando o par é bem formado; ele nunca pode usar a entrada para concluir que uma key está ausente. A Table 36 diz que nós intermediários e leaves devem carregá-la, mas na prática a entrada desaparece depois de edições à mão, segura números dentro de uma name tree, ou chega com os bounds trocados. O PDFlibPas resolve cada um desses casos do mesmo jeito, mantendo o filho pesquisável
/Limitsausente: uma checagem de faixa que pula tal filho torna a subtree inteira dele inalcançável sempre que um producer esquece a entrada, então o filho é pesquisado- Tipo errado ou comprimento errado, como números numa name tree ou um array de um elemento: tratado exatamente como uma entrada ausente
- Bounds invertidos como
[(Z) (A)]ou[9 0]: nenhuma key satisfazLo <= Key <= HiquandoLo > Hi, então confiar no par excluiria o ramo para toda lookup; uma faixa só poda quando o bound inferior dela não excede o superior - Bem formado e ordenado: usado para pular o ramo, que é para isso que a entrada existe
Do lado do caller há dois zeros para distinguir. O GetNamedDestination retorna 0 quando o nome realmente está ausente e um destination ID caso contrário. GetDestPage retornando 0 para um ID válido significa que o nome existe mas o alvo dele não resolve para uma página neste documento, o que é um bug report diferente. O GetDestType reporta a view como 1 para XYZ, 2 para Fit e assim por diante até 8 para FitBV
uses
PDFlibrary;
procedure LookUpDestination(const FileName, DestName: string);
var
Lib: TPDFlib;
DestID, Page: Integer;
begin
Lib := TPDFlib.Create;
try
if Lib.LoadFromFile(FileName, '') <> 1 then
begin
WriteLn('Load failed, error ', Lib.LastErrorCode);
Exit;
end;
// Catalog /Dests (PDF 1.1) primeiro, depois a name tree /Dests
DestID := Lib.GetNamedDestination(DestName);
if DestID = 0 then
begin
WriteLn('No destination named ', DestName);
Exit;
end;
Page := Lib.GetDestPage(DestID);
if Page = 0 then
WriteLn(DestName, ' exists but does not resolve to a page')
else
WriteLn(DestName, ' -> page ', Page,
', view type ', Lib.GetDestType(DestID)); // 1 = XYZ, 2 = Fit ...
finally
Lib.Free;
end;
end;
Isso forma uma checagem de regressão compacta. Monte o arquivo de dois filhos do parágrafo de abertura, aponte a entrada real de chapter7 para a página 2 com uma view /Fit, e o procedimento deve imprimir página 2 com view type 2. Uma lookup de primeiro match imprime "No destination" porque o filho que faz loop vence a corrida; uma lookup que confia em faixas invertidas imprime o mesmo pelo motivo oposto. Depois que os destinations resolvem, as entradas de outline que apontam para eles são cobertas em ler ações de bookmark e annotation PDF no Delphi
Leaves além de 32.768 entradas e a armadilha do packed index
Quando o código precisa de um handle inteiro para "entrada N na leaf M", a codificação tentadora empacota a posição da leaf nos 16 bits altos de um Integer e o offset dentro do array /Names dessa leaf nos 16 bits baixos. Cada par ocupa dois slots de array. O par índice 32.768, o par 32.769º, portanto começa no offset 65.536, que é $10000. Esse bit transborda para a metade alta, e o decoder o lê de volta como offset 0 da leaf seguinte
Os sintomas dependem da forma da árvore. Com uma única leaf não há leaf seguinte, então o handle decodificado indexa além do fim da lista de leaves. Com várias leaves, um find ou um delete pousa no primeiro par da leaf seguinte, enquanto um scan simples por key ainda reporta a key pedida como presente. Arquivos desse tamanho não são exóticos. Uma referência de API gerada com um named destination por symbol cruza 32.768 entradas rápido, e alguns producers escrevem todas elas numa única leaf achatada em vez de balancear a árvore
O PDFlibPas mantém a posição da leaf e o offset da entrada em dois inteiros de largura plena, então nenhum pode vazar para o outro em qualquer tamanho de leaf. O mesmo reader conta só keys string genuínas. Para uma leaf como [(Valid) 42 123 456], o EmbeddedFileCount reporta 1, a key numérica 123 nunca é confundida com um nome vazio, e um índice de 0 ou abaixo retorna string vazia do GetEmbeddedFileStrProperty em vez de qualquer objeto que por acaso venha depois. A tag 1 dessa função é o file name e a tag 2 o subtipo MIME
procedure AuditTrees(const FileName: string);
var
Lib: TPDFlib;
I: Integer;
begin
Lib := TPDFlib.Create;
try
if Lib.LoadFromFile(FileName, '') <> 1 then
Exit;
// number tree /PageLabels; arquivos sem uma retornam números de página simples
for I := 1 to Lib.PageCount do
WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
// name tree /EmbeddedFiles; índices são 1-based, keys não string puladas
for I := 1 to Lib.EmbeddedFileCount do
WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')'); // nome, subtipo MIME
// name tree /JavaScript: lista package names, não executa nada
for I := 1 to Lib.GlobalJavaScriptCount do
WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
finally
Lib.Free;
end;
end;
Um arquivo de teste de duas páginas mostra o output esperado bem. Dê à raiz /PageLabels dele um array /Kids que liste uma leaf duas vezes e também referencie a raiz ela mesma, com faixas para romano minúsculo a partir da página 1 e decimal com prefixo A- a partir da página 2. A auditoria deve imprimir i e A-1, cada faixa aplicada uma vez. Escrever page labels numa árvore assim tem rugas próprias, cobertas em consertar page labels PDF armazenadas em number trees /Kids; o AddPageLabels achata uma raiz /Kids numa única leaf /Nums antes de inserir, usando a mesma enumeração segura contra ciclos
Onde a travessia traça as linhas dela
A travessia garante terminação, ordem estável e respostas corretas para qualquer árvore cujas keys reais estejam intactas. Ela lê uma árvore danificada como escrita e não tenta reconstruir o que o autor pretendia, e cinco consequências seguem dessa escolha
- Identidade, não conteúdo, define um nó. Dois dicionários distintos com entradas idênticas são dois nós, então um producer que copia uma leaf em vez de referenciá-la recebe as entradas dela duas vezes
- Um par
/Limitsbem formado e ordenado poda mesmo quando está errado. Uma faixa que mente plausivelmente, digamos[(a) (m)]sobre uma leaf que também guarda(q), esconde oq. A única defesa seria ignorar/Limitsem toda parte e escanear cada leaf, e numa destination tree com dezenas de milhares de entradas isso joga fora a razão de a entrada existir. Mantemos a poda - A enumeração preserva a ordem do arquivo. O
GetPageLabelcaminha por toda faixa enumerada e aplica a última cujo índice de início esteja na página ou abaixo dela, então um producer que escreve faixas fora de ordem recebe semântica de ordem de arquivo, e inverter a caminhada entregaria à página 200 o estilo de front matter - A memória cresce com nós e entradas distintos. A travessia adiciona uma lista e um hash set sobre os objetos parseados
- Keys duplicadas dentro de uma leaf resolvem deterministicamente: a binary search retorna o par que casar em que ela pousar primeiro, e o fallback linear mantém o último match que escanear
Ferramentas de preflight, archivers e document readers leem essas árvores antes de uma única página ser renderizada, o que os põe na frente da fila para o que quer que chegue numa fila de upload. Os tree readers descritos aqui vêm com o PDFlibPas, a PDF Library for Delphi, que builda tanto com Delphi quanto com Free Pascal