Artículo técnico

Árboles de nombres PDFlibPas: ciclos, Limits y hojas enormes

Construya un PDF cuyo name tree /Dests tiene una raíz con dos hijos. El primer hijo declara /Limits [(a) (z)], y su array /Kids apunta directo de vuelta a la raíz. El segundo hijo sostiene la entrada real de (chapter7), pero sus límites están escritos al revés: [(z) (a)]. Pida a una búsqueda de name tree de manual la clave chapter7 y o recursiona hasta que la pila se agota o devuelve "no encontrado" para un destino al que un visor puede saltar. El archivo entero cabe en unos dos kilobytes, y cada objeto en él parsea limpiamente

Ese archivo mete tres trampas separadas en una estructura: un ciclo de /Kids, un rango que reclama una clave que no sostiene, y un rango que jamás puede casar con nada. Una cuarta trampa necesita un archivo mucho más grande. En cuanto una única hoja lleva más de 32.768 pares nombre/valor, cualquier código que apriete "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, qué debería hacer un lector al respecto, y cómo se comportan las llamadas Delphi en archivos construidos así

Cuatro funcionalidades PDF que se apoyan en name trees y number trees

Los name trees y number trees sostienen cada funcionalidad PDF que mapea un gran conjunto de claves a objetos, y PDFlibPas, la PDF Library de losLab para Delphi, expone cuatro de ellas a través de métodos públicos de TPDFlib. ISO 32000-1 §7.9.6 define el name tree (claves de tipo string, tabla 36) y §7.9.7 el number tree (claves enteras, tabla 37). Los nodos raíz e intermedios llevan /Kids; las hojas llevan pares clave/valor ordenados en /Names o /Nums; se supone que cada nodo no raíz lleva un array /Limits de dos elementos con la clave menor y la mayor por debajo

Á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
Adjuntos/EmbeddedFiles en el diccionario de nombres§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript a nivel de documento/JavaScript en el diccionario de nombres§7.7.4GlobalJavaScriptCount, GlobalJavaScriptPackageName

Dos filas esconden un detalle. Las named destinations existen también en una forma antigua de PDF 1.1, un diccionario /Dests plano en el catálogo indexado por objetos de nombre, y GetNamedDestination comprueba ese diccionario primero y solo después desciende por el name tree de PDF 1.2. La fila de JavaScript tiene un casi homónimo que lee otra cosa por completo: GetDocJavaScript devuelve los scripts colgados de los triggers de documento en el diccionario /AA del catálogo (WS, DS, WP, DP, DC), mientras que los paquetes con nombre que corren al abrir 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 escritor qué debe producir, y un lector aun así recibe lo que el escritor, un incremental save roto o un fuzzer pusieron allí de verdad. Es la misma lección que endurecer un parser PDF Pascal frente a archivos maliciosos, aplicada a la forma del árbol en lugar de a las longitudes de buffer

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

Un caminante recursivo se estrella contra un array /Kids cíclico porque nada en la recursión recuerda qué nodos ya ha entrado, 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 lector recursivo 4.096 frames de pila

La variante más suave ni siquiera se estrella. Cuando dos entradas /Kids referencian la misma hoja, una enumeración ingenua la visita dos veces, así que un recuento de adjuntos vuelve más alto que el número de archivos del documento y una lista de scripts muestra el mismo paquete dos veces

PDFlibPas recorre ambos tipos de árbol con una pila explícita de último en entrar, primero en salir sobre el heap más un conjunto de visitados indexado por identidad de diccionario. Un nodo se marca cuando se saca. Una referencia cíclica puede pasar un momento en la pila, pero se descarta en cuanto vuelve a subir, y cada nodo distinto expande a sus hijos exactamente una vez. El trabajo total queda acotado por el número de diccionarios distintos más la longitud combinada de sus arrays /Kids; una cadena de 4.096 niveles se convierte en 4.096 iteraciones de bucle y 4.096 entradas de hash set

Recorrido de name tree en PDFlibPas: un array Kids que vuelve a la raíz desborda la pila de un caminante recursivo, así que PDFlibPas usa una pila explícita y un conjunto de visitados que marca nodos al sacarlos, mete los hijos de derecha a izquierda y mantiene las hojas en orden de archivo para GetPageLabel
La profundidad deja de importar cuando la recursión se convierte en un bucle: una cadena de 4.096 niveles son 4.096 iteraciones y 4.096 entradas de hash set

El orden es la parte que la gente hace mal cuando convierte la recursión en un bucle. Una pila invierte lo que usted le meta, así que los hijos tienen que meterse desde el último índice hasta el primero; entonces el hijo más a la izquierda sale primero y las hojas aparecen en el orden de izquierda a derecha que escribió el productor. Marcar al sacar en lugar de al meter importa por la misma razón. Con marcas al meter y metidas de derecha a izquierda, una hoja compartida por las posiciones 0 y 2 serí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 usted 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 de lado lector, no llamadas de la biblioteca

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 bien educado
    Values: TArray<Integer>;   // paralelo a Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// Su propio ayudante: /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;

// Su propia búsqueda: pila explícita, conjunto 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
        // Mete de derecha a izquierda para que el hijo más a la izquierda 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 significa nada sobre el árbol

El atajo de búsqueda más común escoge el primer hijo cuyo /Limits cubre la clave, desciende 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, lleva de vuelta a la raíz, y la búsqueda acaba con las manos vacías mientras el siguiente hermano sostiene la entrada

PDFlibPas no se detiene en la primera rama plausible. La búsqueda por clave detrás de GetNamedDestination mete cada hijo cuyo rango no descarta la clave, y sigue sacando hasta encontrar una coincidencia o vaciar la pila. En un árbol bien formado con rangos disjuntos, a lo sumo un hijo sobrevive al check de rango en cada nivel, así que el coste extra es nulo. En uno dañado son un puñado de visitas de nodo extra, y la respuesta vuelve correcta

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 biblioteca prueba primero una búsqueda binaria. Cuando esa falla, recae en un barrido lineal de los pares, porque una hoja desordenada volvería invisible una clave presente. Pagar un barrido lineal en cada fallo genuino es un coste que aceptamos: las búsquedas de nombres que de verdad están ausentes son raras, y un "no encontrado" falso sobre un enlace que funciona cuesta mucho más que una pasada extra sobre una hoja

Una contradicción estructural se maneja con rechazo. La tabla 36 deja que un nodo lleve /Kids o /Names, nunca ambos. Una búsqueda por clave trata un nodo que lleva ambos como malformado y lo salta en lugar 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 cada página posterior

¿En qué puede fiarse un lector de /Limits?

Un lector puede fiarse de /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 tabla 36 dice que los nodos intermedios y las hojas deben llevarla, pero en la práctica la entrada desaparece tras ediciones a mano, contiene números dentro de un name tree, o llega con sus cotas intercambiadas. PDFlibPas resuelve cada uno de esos casos de la misma manera, manteniendo al hijo buscable

  • /Limits ausente: un check de rango que salta semejante hijo deja todo su subárbol inalcanzable siempre que un productor olvide 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 trata exactamente como una entrada ausente
  • Cotas invertidas como [(Z) (A)] o [9 0]: ninguna clave cumple Lo <= Key <= Hi cuando Lo > Hi, así que fiarse del par excluiría la rama para toda búsqueda; un rango solo poda cuando su cota inferior no supera a su cota superior
  • Bien formado y ordenado: se usa para saltarse la rama, que es para lo que existe la entrada
Reglas de PDFlibPas para fiarse de 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 saltarse trabajo pero jamás deciden la ausencia, porque las claves reales guardadas en las hojas deciden el desenlace de cada búsqueda

Desde el lado de quien llama hay dos ceros que distinguir. GetNamedDestination devuelve 0 cuando el nombre de verdad está ausente y un ID de destino en caso contrario. Un GetDestPage que devuelve 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 /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 hace un check 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 una 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 en bucle gana la carrera; una búsqueda que se fía de 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 marcadores y anotaciones PDF en Delphi

Hojas de más de 32.768 entradas y la trampa del índice empaquetado

Cuando el código necesita un manejador entero para "la entrada N de 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 posiciones de array. El par de índice 32.768, el par 32.769, empieza por tanto en el offset 65.536, que es $10000. Ese bit arrastra a la mitad alta, y el decodificador lo lee de vuelta como offset 0 de la hoja siguiente

Í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 empieza en el offset 65536, de modo que el arrastre a la mitad alta se lee como offset 0 de la hoja siguiente y un find o un delete tocan el par equivocado mientras un barrido de claves separado discrepa
Dos valores de 16 bits en un entero de 32 bits truncan en silencio en cuanto una hoja cruza los 32.768 pares, un tamaño que alcanzan manuales de referencia reales

Los síntomas dependen de la forma del árbol. Con una sola hoja no hay hoja siguiente, así que el manejador decodificado indexa más allá del final de la lista de hojas. Con varias hojas, un find o un delete aterrizan en el primer par de la hoja siguiente, mientras que un barrido de claves plano sigue reportando la clave solicitada como presente. Los archivos de este tamaño no son exóticos. Un manual de API generado con una named destination por símbolo cruza las 32.768 entradas rápido, y algunos productores escriben todas en una única hoja plana en lugar de equilibrar el árbol

PDFlibPas guarda la posición de la hoja y el offset de la entrada en dos enteros de ancho completo, así que ninguno puede derramarse en el otro con ningún tamaño de hoja. El mismo lector cuenta solo claves de tipo string 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 desde GetEmbeddedFileStrProperty en lugar del objeto que resulte seguir. El tag 1 de esa función es el nombre de 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 /PageLabels; los archivos sin él devuelven números de página planos
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // name tree /EmbeddedFiles; índices 1-based, claves no string saltadas
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nombre, tipo MIME
    // name tree /JavaScript: liste nombres de paquetes, no ejecute 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. Déle a su raíz /PageLabels un array /Kids que liste una hoja dos veces y referencie también a la raíz misma, con rangos de romanos en minúsculas desde la página 1 y decimal 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 los page labels PDF guardados en number trees /Kids; AddPageLabels aplana una raíz /Kids en una única hoja /Nums antes de insertar, usando la misma enumeración a salvo de 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 pretendía, y cinco consecuencias se siguen de esa elección

  • La identidad, no el contenido, define un nodo. Dos diccionarios distintos con entradas idénticas son dos nodos, así que un productor que copie una hoja en lugar de referenciarla obtiene esas entradas dos veces
  • Un par /Limits bien formado y ordenado poda incluso cuando está mal. Un rango que mienta de forma plausible, digamos [(a) (m)] sobre una hoja que también sostiene (q), esconde la q. La única defensa sería ignorar /Limits en todas partes y barrer cada hoja, y en un árbol de destinos con decenas de miles de entradas eso tira por la borda 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 la página o por debajo, así que un productor que escriba rangos desordenados recibe semántica de orden de archivo, e invertir el recorrido entregaría a la página 200 el estilo del preliminar
  • La memoria crece con los nodos y entradas distintos. El recorrido añade una lista y un hash set sobre los objetos parseados
  • Las claves duplicadas dentro de una hoja se resuelven de forma determinista: la búsqueda binaria devuelve el primer par coincidente que pisa, y el fallback lineal conserva el último que barre

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