Artigo Técnico

Name trees PDFlibPas: ciclos, /Limits e folhas gigantes

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

ÁrvoreOnde viveEspecificaçãoAPI de leitura do PDFlibPas
Named destinations/Dests no name dictionary§12.3.2.3GetNamedDestination, depois GetDestPage / GetDestType
Page labels/PageLabels no catalog (number tree)§12.4.2GetPageLabel
Attachments/EmbeddedFiles no name dictionary§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript de nível de documento/JavaScript no name dictionary§7.7.4GlobalJavaScriptCount, 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

Travessia de name tree do PDFlibPas: um array Kids que volta para a raiz estoura a stack de um walker recursivo, então o PDFlibPas usa uma stack explícita e um visited set que marca nós ao retirar da stack, empurra filhos da direita para a esquerda e mantém leaves em ordem de arquivo para o GetPageLabel
Profundidade para de importar quando a recursão vira um loop: uma cadeia de 4.096 níveis é só 4.096 iterações 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

  • /Limits ausente: 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 satisfaz Lo <= Key <= Hi quando Lo > 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
Regras do PDFlibPas para confiar num array Limits de name tree: um par ausente, de tipo errado ou invertido deixa o filho pesquisável, e só um par bem formado e ordenado pode podar o ramo, então um Limits hostil pode custar visitas mas não pode esconder um destination existente
Faixas podem pular trabalho mas nunca decidem ausência, porque as keys reais armazenadas nas leaves decidem o resultado de toda lookup

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

Packed index de name tree em que uma posição de leaf e um offset de entrada dividem um Integer de 32 bits e o par 32768 começa no offset 65536, então o carry para a metade alta lê como offset 0 da leaf seguinte e um find ou delete toca o par errado enquanto um scan separado por key discorda
Dois valores de 16 bits num inteiro de 32 bits truncam silenciosamente no momento em que uma leaf cruza 32.768 pares, um tamanho que manuais de referência reais alcançam

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 /Limits bem 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 o q. A única defesa seria ignorar /Limits em 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 GetPageLabel caminha 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