Artículo técnico

Name trees en PDFlibPas: ciclos y Limits que esconden claves

Arme un PDF cuyo name tree de /Dests tenga un root con dos hijos. El primer hijo declara /Limits [(a) (z)], y su array /Kids apunta directo de vuelta al root. El segundo hijo carga la entrada real de (chapter7), pero sus límites están escritos al revés: [(z) (a)]. Pídale a una búsqueda de name tree de libro de texto chapter7 y o recursa hasta agotar el stack o devuelve "no encontrado" para un destino al que un visor puede saltar. El archivo completo cabe en unos dos kilobytes, y cada objeto en él parsea limpio

Ese archivo mete tres trampas separadas en una sola estructura: un ciclo de /Kids, un rango que reclama una clave que no tiene, y un rango que jamás puede coincidir con nada. Una cuarta trampa necesita un archivo mucho más grande. En cuanto una sola hoja carga más de 32,768 pares nombre/valor, cualquier código que meta "qué hoja" y "qué entrada" en un solo entero de 32 bits empieza a apuntar al par equivocado. El resto de este artículo recorre cada trampa, lo que debería hacer un reader al respecto, y cómo se comportan las llamadas Delphi en archivos armados así

Cuatro features de PDF que descansan en name trees y number trees

Los name trees y number trees sostienen toda feature de PDF que mapea un set grande de claves a objetos, y PDFlibPas, la PDF Library de losLab para Delphi, expone cuatro de ellas mediante métodos públicos de TPDFlib. ISO 32000-1 §7.9.6 define el name tree (claves de cadena, Table 36) y §7.9.7 el number tree (claves enteras, Table 37). Los nodos root e intermedios cargan /Kids; las hojas cargan pares clave/valor ordenados en /Names o /Nums; se espera que todo nodo que no sea root cargue un array /Limits de dos elementos con la clave menor y la mayor debajo de él

ÁrbolDónde viveEspecificaciónAPI de lectura de PDFlibPas
Named destinations/Dests en el diccionario de nombres§12.3.2.3GetNamedDestination, luego GetDestPage / GetDestType
Page labels/PageLabels en el catálogo (number tree)§12.4.2GetPageLabel
Attachments/EmbeddedFiles en el diccionario de nombres§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript de documento/JavaScript en el diccionario de nombres§7.7.4GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dos filas esconden un detalle. Los named destinations también existen en una forma PDF 1.1 más vieja, un diccionario /Dests plano en el catálogo indexado por objetos de nombre, y GetNamedDestination revisa ese diccionario primero y solo después baja por el name tree PDF 1.2. La fila de JavaScript tiene un casi homónimo que lee otra cosa por completo: GetDocJavaScript devuelve scripts adjuntos a los triggers del documento en el diccionario /AA del catálogo (WS, DS, WP, DP, DC), mientras que los paquetes nombrados que corren cuando se abre un documento viven en el name tree /JavaScript y los lista GlobalJavaScriptPackageName

Todas estas estructuras vienen del archivo. La especificación le dice a un writer qué debe producir, y un reader igual recibe lo que el writer, un incremental save dañado o un fuzzer pusieron ahí. Es la misma lección que endurecer un parser PDF en Pascal contra archivos maliciosos, aplicada a la forma del árbol en vez de a longitudes de buffer

¿Por qué un array /Kids cíclico tumba a un walker de árbol recursivo?

Un walker recursivo se estrella contra un array /Kids cíclico porque nada en la recursión recuerda qué nodos ya entró, así que una referencia de hijo a un ancestro convierte un archivo finito en un descenso sin fin. Un árbol legítimo puede hacer el mismo daño sin ciclo alguno: una cadena de 4,096 niveles de nodos de un solo hijo es sintaxis válida que le cuesta a un reader recursivo 4,096 frames de stack

La variante más leve ni se estrella. Cuando dos entradas /Kids referencian la misma hoja, una enumeración ingenua la visita dos veces, así que un conteo de attachments regresa más alto que la cantidad de archivos del documento y una lista de scripts muestra el mismo package dos veces

PDFlibPas recorre ambos tipos de árbol con un stack explícito last-in, first-out en el heap más un set de visitados indexado por identidad de diccionario. Un nodo se marca cuando sale del stack. Una referencia cíclica puede pasar un momento en el stack, pero se descarta en cuanto vuelve a subir, y cada diccionario distinto expande sus hijos exactamente una vez. El trabajo total queda acotado por la cantidad de diccionarios distintos más la longitud combinada de sus arrays /Kids; una cadena de 4,096 niveles se vuelve 4,096 iteraciones de bucle y 4,096 entradas de hash set

Recorrido de name tree en PDFlibPas: un array Kids que regresa al root desborda el stack de un walker recursivo, así que PDFlibPas usa un stack explícito y un set de visitados que marca nodos al sacarlos del stack, empuja hijos de derecha a izquierda y conserva las hojas en orden de archivo para GetPageLabel
La profundidad deja de importar cuando la recursión se vuelve bucle: una cadena de 4,096 niveles son solo 4,096 iteraciones y 4,096 entradas de hash set

El orden es la parte donde la gente se equivoca al convertir recursión en bucle. Un stack invierte lo que usted le meta, así que los hijos hay que empujarlos del último índice al primero; entonces el hijo más a la izquierda sale primero y las hojas salen en el orden izquierda-derecha en que el productor las escribió. Marcar al sacar y no al empujar importa por la misma razón. Con marcas al empujar y empujes de derecha a izquierda, una hoja compartida por las posiciones 0 y 2 quedaría reclamada por la posición 2, y sus entradas aparecerían más tarde de lo que dice el archivo. Los page labels dependen de ese orden, como muestra la última sección

Si escribe su propio código de árboles contra otro modelo de objetos, esta es la forma que recomendamos. El tipo de nodo de abajo es deliberadamente abstracto, y ambas funciones son código del lado del reader, no llamadas de la librería

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // vacío en una hoja
    Keys: TArray<string>;      // claves de hoja, ordenadas por un productor que se porta bien
    Values: TArray<Integer>;   // paralelo a Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// Helper suyo: /Limits solo puede podar cuando es un par bien formado y 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;

// Búsqueda suya: stack explícito, set de visitados, marca al sacar
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 o hijo compartido: ya visto
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Empuje de derecha a izquierda para que el hijo izquierdo salga primero
        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;
      // Un fallo en esta hoja: siga sacando a sus hermanos
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Un fallo en una rama no dice nada del árbol

El atajo de búsqueda más común elige el primer hijo cuyo /Limits cubre la clave, baja por él, y jamás vuelve a mirar a un hermano. En un árbol limpio eso es correcto y rápido. En el archivo del párrafo inicial falla: el primer hijo reclama chapter7, regresa al root, y la búsqueda termina con las manos vacías mientras el siguiente hermano tiene la entrada

PDFlibPas no se detiene en la primera rama plausible. La búsqueda con clave detrás de GetNamedDestination empuja a todo hijo cuyo rango no descarte la clave, y sigue sacando del stack hasta encontrar coincidencia o vaciarlo. En un árbol bien formado con rangos disjuntos, a lo sumo un hijo sobrevive el chequeo de rango en cada nivel, así que el costo extra es nulo. En uno dañado son unas cuantas visitas de nodo extra, y la respuesta regresa bien

Las hojas reciben el mismo tratamiento. ISO 32000-1 exige que las claves de un array /Names estén ordenadas por valor de byte, así que la librería prueba primero una búsqueda binaria. Cuando falla, recurre a un barrido lineal de los pares, porque una hoja desordenada haría invisible una clave presente. Pagar un barrido lineal en cada fallo genuino es un costo que aceptamos: las búsquedas de nombres realmente ausentes son raras, y un "no encontrado" falso sobre un link funcional cuesta mucho más que una pasada extra sobre una hoja

Una contradicción estructural se maneja con rechazo. La Table 36 permite que un nodo cargue /Kids o /Names, jamás ambos. Una búsqueda con clave trata un nodo que carga ambos como malformado y lo salta en vez de adivinar qué mitad quiso el productor. La enumeración de number trees, como el recorrido detrás de GetPageLabel, es más tolerante y sigue /Kids cuando ambos están presentes, porque descartar un rango entero desetiquetaría todas las páginas posteriores

¿En qué puede confiar un reader respecto de /Limits?

Un reader puede confiar en /Limits para saltarse trabajo, y solo cuando el par está bien formado; jamás puede usar la entrada para concluir que una clave está ausente. La Table 36 dice que los nodos intermedios y hoja deben cargarla, pero en la práctica la entrada desaparece tras ediciones a mano, guarda números dentro de un name tree, o llega con sus cotas invertidas. PDFlibPas resuelve cada uno de esos casos de la misma manera, manteniendo al hijo buscable

  • /Limits ausente: un chequeo de rango que salte a tal hijo deja todo su subárbol inalcanzable cada vez que un productor olvida la entrada, así que el hijo se busca
  • Tipo equivocado o longitud equivocada, como números en un name tree o un array de un elemento: se maneja exactamente igual que una entrada ausente
  • Cotas invertidas como [(Z) (A)] o [9 0]: ninguna clave satisface Lo <= Key <= Hi cuando Lo > Hi, así que confiar en el par excluiría la rama para toda búsqueda; un rango solo poda cuando su cota inferior no excede la superior
  • Bien formado y ordenado: se usa para saltar la rama, que es para lo que existe la entrada
Reglas de PDFlibPas para confiar en un array Limits de un name tree: un par ausente, de tipo equivocado o invertido deja al hijo buscable, y solo un par bien formado y ordenado puede podar la rama, así que un Limits hostil puede costar visitas pero no puede esconder un destino existente
Los rangos pueden ahorrar trabajo pero jamás deciden ausencia, porque las claves reales guardadas en las hojas deciden el resultado de cada búsqueda

Del lado del llamador hay dos ceros que distinguir. GetNamedDestination devuelve 0 cuando el nombre realmente está ausente y un ID de destino en cualquier otro caso. Que GetDestPage devuelva 0 para un ID válido significa que el nombre existe pero su objetivo no resuelve a una página de este documento, lo que es un reporte de bug distinto. GetDestType reporta la vista como 1 para XYZ, 2 para Fit y así hasta 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;
    // Primero el /Dests del catálogo (PDF 1.1), luego el 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;

Esto arma un chequeo de regresión compacto. Construya el archivo de dos hijos del párrafo inicial, apunte la entrada real de chapter7 a la página 2 con vista /Fit, y el procedimiento debería imprimir página 2 con tipo de vista 2. Una búsqueda de primera coincidencia imprime "No destination" porque el hijo que hace loop gana la carrera; una búsqueda que confía en rangos invertidos imprime lo mismo por la razón contraria. Una vez que los destinos resuelven, las entradas de outline que apuntan a ellos están cubiertas en leer acciones de bookmarks y anotaciones PDF en Delphi

Hojas con más de 32,768 entradas y la trampa del índice empaquetado

Cuando el código necesita un entero como handle para "entrada N en la hoja M", la codificación tentadora empaqueta la posición de la hoja en los 16 bits altos de un Integer y el offset dentro del array /Names de esa hoja en los 16 bits bajos. Cada par ocupa dos slots del array. El índice de par 32,768, el par número 32,769, arranca por lo tanto en el offset 65,536, que es $10000. Ese bit se arrastra a la mitad alta, y el decodificador lo lee de vuelta como offset 0 de la siguiente hoja

Índice de name tree empaquetado donde una posición de hoja y un offset de entrada comparten un Integer de 32 bits y el par 32768 arranca en el offset 65536, así que el acarreo a la mitad alta se lee como offset 0 de la siguiente hoja y una búsqueda o un borrado tocan el par equivocado mientras un barrido de claves aparte discrepa
Dos valores de 16 bits en un entero de 32 bits se truncan en silencio en el momento en que una hoja cruza 32,768 pares, un tamaño que alcanzan los manuales de referencia reales

Los síntomas dependen de la forma del árbol. Con una sola hoja no hay siguiente hoja, así que el handle decodificado indexa más allá del final de la lista de hojas. Con varias hojas, una búsqueda o un borrado caen en el primer par de la hoja siguiente, mientras que un barrido plano de claves sigue reportando la clave pedida como presente. Archivos de este tamaño no son exóticos. Una referencia de API generada con un named destination por símbolo cruza 32,768 entradas rápido, y algunos productores escriben todas en una sola hoja plana en vez de balancear el árbol

PDFlibPas guarda la posición de hoja y el offset de entrada en dos enteros de ancho completo, así que ninguno puede derramarse en el otro con cualquier tamaño de hoja. El mismo reader cuenta solo claves de cadena genuinas. Para una hoja como [(Valid) 42 123 456], EmbeddedFileCount reporta 1, la clave numérica 123 jamás se confunde con un nombre vacío, y un índice de 0 o menos devuelve una cadena vacía de GetEmbeddedFileStrProperty en vez del objeto que resulte seguir. El tag 1 de esa función es el nombre del archivo y el tag 2 el 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 de /PageLabels; los archivos sin uno devuelven números de página planos
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Name tree de /EmbeddedFiles; índices desde 1, claves no cadena se saltan
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nombre, subtipo MIME
    // Name tree de /JavaScript: lista nombres de packages, no ejecuta nada
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Un archivo de prueba de dos páginas muestra bien la salida esperada. Dele a su root de /PageLabels un array /Kids que liste una hoja dos veces y que además referencie al root mismo, con rangos de romanos en minúscula desde la página 1 y decimales con prefijo A- desde la página 2. La auditoría debería imprimir i y A-1, cada rango aplicado una vez. Escribir page labels en un árbol así tiene sus propias arrugas, cubiertas en arreglar page labels PDF guardados en number trees /Kids; AddPageLabels aplana un root /Kids en una sola hoja /Nums antes de insertar, con la misma enumeración segura ante ciclos

Dónde traza sus líneas el recorrido

El recorrido garantiza terminación, orden estable y respuestas correctas para cualquier árbol cuyas claves reales estén intactas. Lee un árbol dañado tal como está escrito y no intenta reconstruir lo que el autor quiso, y de esa decisión se siguen cinco consecuencias

  • La identidad, no el contenido, define a un nodo. Dos diccionarios distintos con entradas idénticas son dos nodos, así que un productor que copie una hoja en vez de referenciarla recibe esas entradas dos veces
  • Un par /Limits bien formado y ordenado poda aunque esté equivocado. Un rango que miente de forma plausible, digamos [(a) (m)] sobre una hoja que también guarda (q), esconde a q. La única defensa sería ignorar /Limits por todas partes y barrer cada hoja, y en un árbol de destinos con decenas de miles de entradas eso bota la razón de ser de la entrada. Seguimos podando
  • La enumeración preserva el orden del archivo. GetPageLabel recorre cada rango enumerado y aplica el último cuyo índice de inicio esté en o debajo de la página, así que un productor que escriba rangos desordenados recibe semántica de orden de archivo, y revertir el recorrido le entregaría a la página 200 el estilo de preliminares
  • La memoria crece con los nodos y entradas distintos. El recorrido agrega una lista y un hash set encima de los objetos parseados
  • Las claves duplicadas dentro de una hoja se resuelven de forma determinista: la búsqueda binaria devuelve el par coincidente en el que caiga primero, y el fallback lineal conserva la última coincidencia que barra

Las herramientas de preflight, los archivadores y los visores de documentos leen estos árboles antes de renderizar la primera página, lo que los pone primeros en la fila para lo que llegue en una cola de subidas. Los readers de árboles descritos aquí se distribuyen con PDFlibPas, la PDF Library para Delphi, que compila tanto con Delphi como con Free Pascal