Article technique

Arbres de noms PDFlibPas : cycles, /Limits, feuilles énormes

Construisez un PDF dont l’arbre de noms /Dests a une racine à deux enfants. Le premier enfant déclare /Limits [(a) (z)], et son tableau /Kids pointe droit vers la racine. Le second enfant porte la vraie entrée pour (chapter7), mais ses limites sont écrites à l’envers : [(z) (a)]. Demandez à une recherche d’arbre de noms tirée d’un manuel chapter7 et elle part en récursion jusqu’à épuisement de la pile ou renvoie « introuvable » pour une destination vers laquelle un visualiseur peut sauter. Le fichier entier tient dans environ deux kilooctets, et chaque objet qu’il contient s’analyse proprement

Ce fichier entasse trois pièges distincts dans une seule structure : un cycle /Kids, une plage qui réclame une clé qu’elle ne détient pas, et une plage qui ne peut rien faire correspondre. Un quatrième piège exige un fichier bien plus gros. Dès qu’une seule feuille porte plus de 32 768 paires nom/valeur, tout code qui tasse « quelle feuille » et « quelle entrée » dans un seul entier 32 bits se met à pointer la mauvaise paire. Le reste de l’article passe chaque piège en revue, ce qu’un lecteur devrait en faire, et comment les appels Delphi se comportent sur des fichiers bâtis ainsi

Quatre fonctionnalités PDF qui reposent sur les arbres de noms et de nombres

Les arbres de noms et les arbres de nombres portent chaque fonctionnalité PDF qui associe un grand jeu de clés à des objets, et PDFlibPas, la losLab PDF Library for Delphi, en expose quatre par des méthodes publiques TPDFlib. L’ISO 32000-1 §7.9.6 définit l’arbre de noms (clés chaîne, table 36) et le §7.9.7 l’arbre de nombres (clés entières, table 37). La racine et les nœuds intermédiaires portent /Kids ; les feuilles portent des paires clé/valeur triées dans /Names ou /Nums ; chaque nœud non racine est censé porter un tableau /Limits à deux éléments tenant la plus petite et la plus grande clé en dessous de lui

ArbreOù il se trouveSpécificationAPI de lecture PDFlibPas
Destinations nommées/Dests dans le dictionnaire des noms§12.3.2.3GetNamedDestination, puis GetDestPage / GetDestType
Étiquettes de page/PageLabels dans le catalogue (arbre de nombres)§12.4.2GetPageLabel
Pièces jointes/EmbeddedFiles dans le dictionnaire des noms§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript au niveau document/JavaScript dans le dictionnaire des noms§7.7.4GlobalJavaScriptCount, GlobalJavaScriptPackageName

Deux lignes cachent une rugosité. Les destinations nommées existent aussi sous une forme PDF 1.1 plus ancienne, un simple dictionnaire /Dests dans le catalogue, indexé par des objets nom, et GetNamedDestination consulte ce dictionnaire d’abord et ne descend ensuite que vers l’arbre de noms PDF 1.2. La ligne JavaScript a un quasi homonyme qui lit tout autre chose : GetDocJavaScript renvoie les scripts attachés aux déclencheurs de document dans le dictionnaire /AA du catalogue (WS, DS, WP, DP, DC), tandis que les paquets nommés qui s’exécutent à l’ouverture d’un document vivent dans l’arbre de noms /JavaScript et sont listés par GlobalJavaScriptPackageName

Toutes ces structures viennent du fichier. La spécification dit à un écrivain ce qu’il doit produire, et un lecteur reçoit quand même ce que l’écrivain, une sauvegarde incrémentale cassée ou un fuzzer y a réellement mis. C’est la même leçon que le durcissement d’un analyseur PDF Pascal contre les fichiers malveillants, appliquée à la forme de l’arbre au lieu des longueurs de tampons

Pourquoi un tableau /Kids cyclique plante-t-il un parcours récursif d’arbre ?

Un parcours récursif plante sur un tableau /Kids cyclique parce que rien dans la récursion ne se souvient des nœuds déjà visités, si bien qu’une référence enfant vers un ancêtre transforme un fichier fini en descente sans fin. Un arbre légitime peut faire le même dégât sans aucun cycle : une chaîne de nœuds à enfant unique sur 4 096 niveaux est une syntaxe valide qui coûte à un lecteur récursif 4 096 frames de pile

La variante plus douce ne plante pas du tout. Quand deux entrées /Kids référencent la même feuille, une énumération naïve la visite deux fois, si bien qu’un compte de pièces jointes revient plus haut que le nombre de fichiers du document et qu’une liste de scripts montre le même paquet deux fois

PDFlibPas parcourt les deux sortes d’arbres avec une pile explicite dernier entré, premier sorti sur le tas plus un ensemble de visités indexé par l’identité des dictionnaires. Un nœud est marqué quand il est dépilé. Une référence cyclique peut rester un moment sur la pile, mais elle est écartée dès qu’elle remonte, et chaque nœud distinct déplie ses enfants exactement une fois. Le travail total est borné par le nombre de dictionnaires distincts plus la longueur combinée de leurs tableaux /Kids ; une chaîne de 4 096 niveaux devient 4 096 itérations de boucle et 4 096 entrées d’ensemble de hachage

Parcours d’arbre de noms PDFlibPas : un tableau Kids bouclant vers la racine fait déborder la pile d’un parcours récursif, si bien que PDFlibPas emploie une pile explicite et un ensemble de visités qui marque les nœuds au dépilage, pousse les enfants de droite à gauche et garde les feuilles dans l’ordre du fichier pour GetPageLabel
La profondeur cesse de compter quand la récursion devient une boucle : une chaîne de 4 096 niveaux n’est que 4 096 itérations et 4 096 entrées d’ensemble de hachage

L’ordre est la partie que l’on rate quand on convertit une récursion en boucle. Une pile inverse ce qu’on lui donne, si bien que les enfants doivent être poussés du dernier index vers le premier ; alors l’enfant le plus à gauche est dépilé en premier et les feuilles sortent dans l’ordre de gauche à droite où l’écrivain les a mises. Marquer au dépilage plutôt qu’à l’empilage compte pour la même raison. Avec des marques à l’empilage et des poussées de droite à gauche, une feuille partagée entre les positions 0 et 2 serait revendiquée par la position 2, et ses entrées apparaîtraient plus tard que ne le dit le fichier. Les étiquettes de page dépendent de cet ordre, comme la dernière section le montre

Si vous écrivez votre propre code d’arbre contre un autre modèle objet, voici la forme que nous recommandons. Le type de nœud ci-dessous est délibérément abstrait, et les deux fonctions sont du code côté lecteur, pas des appels de bibliothèque

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // vide sur une feuille
    Keys: TArray<string>;      // clés de feuille, triées par un producteur bien élevé
    Values: TArray<Integer>;   // parallèle à Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// Votre propre helper : /Limits ne peut élaguer que s’il s’agit d’une paire bien formée et ordonnée
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;

// Votre propre recherche : pile explicite, ensemble de visités, marquage au dépilage
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;                      // cycle ou enfant partagé : déjà vu
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Poussez de droite à gauche pour que l’enfant le plus à gauche soit dépilé en premier
        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 raté dans cette feuille : continuez à dépiler ses sœurs
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Un raté dans une branche ne dit rien de l’arbre

Le raccourci de recherche le plus courant prend le premier enfant dont les /Limits couvrent la clé, y descend, et ne regarde plus jamais un frère. Sur un arbre propre c’est correct et rapide. Sur le fichier du paragraphe d’ouverture il échoue : le premier enfant réclame chapter7, ramène vers la racine, et la recherche se termine les mains vides pendant que le frère suivant détient l’entrée

PDFlibPas ne s’arrête pas à la première branche plausible. La recherche à clé derrière GetNamedDestination pousse chaque enfant dont la plage n’exclut pas la clé, et elle continue à dépiler jusqu’à trouver une correspondance ou vider la pile. Sur un arbre bien formé aux plages disjointes, un enfant au plus survit au contrôle de plage à chaque niveau, si bien que le coût supplémentaire est nul. Sur un arbre endommagé, ce sont quelques visites de nœuds de plus, et la réponse revient juste

Les feuilles reçoivent le même traitement. L’ISO 32000-1 exige que les clés d’un tableau /Names soient triées par valeur d’octet, si bien que la bibliothèque tente d’abord une recherche dichotomique. Quand elle rate, elle retombe sur un scan linéaire des paires, parce qu’une feuille désordonnée rendrait autrement invisible une clé pourtant présente. Payer un scan linéaire à chaque raté authentique est un coût que nous acceptons : les recherches de noms réellement absents sont rares, et un « introuvable » faux sur un lien fonctionnel coûte bien plus qu’une passe de plus sur une feuille

Une contradiction structurelle se traite par le refus. La table 36 laisse un nœud porter /Kids ou /Names, jamais les deux. Une recherche à clé traite un nœud portant les deux comme malformé et le saute au lieu de deviner quelle moitié l’écrivain visait. L’énumération des arbres de nombres, comme la marche derrière GetPageLabel, est plus tolérante et suit /Kids quand les deux sont présents, parce qu’abandonner une plage entière étiqueterait faussement chaque page suivante

À quoi un lecteur peut-il faire confiance avec /Limits ?

Un lecteur peut faire confiance à /Limits pour épargner du travail, et seulement quand la paire est bien formée ; il ne peut jamais employer l’entrée pour conclure qu’une clé est absente. La table 36 dit que les nœuds intermédiaires et les feuilles doivent la porter, pourtant en pratique l’entrée disparaît après des éditions à la main, contient des nombres dans un arbre de noms, ou arrive avec ses bornes échangées. PDFlibPas résout chacun de ces cas de la même façon, en gardant l’enfant cherchable

  • /Limits absents : un contrôle de plage qui saute un tel enfant rend tout son sous-arbre inatteignable chaque fois qu’un producteur oublie l’entrée, si bien que l’enfant est cherché
  • Mauvais type ou mauvaise longueur, comme des nombres dans un arbre de noms ou un tableau à un élément : traité exactement comme une entrée manquante
  • Bornes inversées comme [(Z) (A)] ou [9 0] : aucune clé ne satisfait Lo <= Key <= Hi quand Lo > Hi, si bien que faire confiance à la paire exclurait la branche pour toute recherche ; une plage n’élagoue que si sa borne basse ne dépasse pas sa borne haute
  • Bien formée et ordonnée : sert à sauter la branche, ce qui est la raison d’être de l’entrée
Règles PDFlibPas de confiance en un tableau Limits d’arbre de noms : une paire absente, de mauvais type ou inversée laisse l’enfant cherchable, et seule une paire bien formée et ordonnée peut élaguer la branche, si bien qu’un Limits hostile peut coûter des visites mais ne peut pas cacher une destination existante
Les plages peuvent épargner du travail mais ne décident jamais de l’absence, parce que les vraies clés stockées dans les feuilles tranchent chaque recherche

Du côté de l’appelant, il y a deux zéros à distinguer. GetNamedDestination renvoie 0 quand le nom est réellement absent et un identifiant de destination sinon. GetDestPage renvoyant 0 pour un identifiant valide signifie que le nom existe mais que sa cible ne se résout vers aucune page de ce document, ce qui est un autre rapport de bug. GetDestType rapporte la vue comme 1 pour XYZ, 2 pour Fit et ainsi de suite jusqu’à 8 pour 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;
    // /Dests du catalogue (PDF 1.1) d’abord, puis l’arbre de noms /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;

Cela fait un contrôle de régression compact. Construisez le fichier à deux enfants du paragraphe d’ouverture, pointez la vraie entrée chapter7 vers la page 2 avec une vue /Fit, et la procédure devrait imprimer page 2 avec le type de vue 2. Une recherche au premier trouvé imprime « No destination » parce que l’enfant bouclé gagne la course ; une recherche qui fait confiance aux plages inversées imprime la même chose pour la raison opposée. Une fois les destinations résolues, les entrées de signet qui pointent vers elles sont couvertes dans la lecture des actions de signets et d’annotations PDF en Delphi

Feuilles au-delà de 32 768 entrées et le piège de l’index compacté

Quand du code a besoin d’un identifiant entier unique pour « entrée N dans la feuille M », l’encodage tentant tasse la position de feuille dans les 16 bits hauts d’un Integer et l’offset dans le tableau /Names de cette feuille dans les 16 bits bas. Chaque paire prend deux emplacements de tableau. La paire d’index 32 768, soit la 32 769e paire, démarre donc à l’offset 65 536, c’est-à-dire $10000. Ce bit se propage dans la moitié haute, et le décodeur le relit comme l’offset 0 de la feuille suivante

Index d’arbre de noms compacté où une position de feuille et un offset d’entrée partagent un Integer 32 bits et la paire 32768 démarre à l’offset 65536, si bien que la retenue vers la moitié haute se lit comme l’offset 0 de la feuille suivante et une recherche ou suppression touche la mauvaise paire tandis qu’un scan de clés séparé est en désaccord
Deux valeurs de 16 bits dans un entier 32 bits se tronquent en silence dès qu’une feuille dépasse 32 768 paires, une taille que de vrais manuels de référence atteignent

Les symptômes dépendent de la forme de l’arbre. Avec une seule feuille, il n’y a pas de feuille suivante, si bien que l’identifiant décodé indexe au-delà de la fin de la liste de feuilles. Avec plusieurs feuilles, une recherche ou une suppression atterrit sur la première paire de la feuille suivante, tandis qu’un simple scan de clés rapporte toujours la clé demandée comme présente. Des fichiers de cette taille ne sont pas exotiques. Une référence d’API générée avec une destination nommée par symbole dépasse vite 32 768 entrées, et certains producteurs écrivent chacune dans une seule feuille plate au lieu d’équilibrer l’arbre

PDFlibPas garde la position de feuille et l’offset d’entrée dans deux entiers à pleine largeur, si bien que ni l’un ni l’autre ne peut déborder sur l’autre quelle que soit la taille de feuille. Le même lecteur ne compte que les vraies clés chaîne. Pour une feuille comme [(Valid) 42 123 456], EmbeddedFileCount rapporte 1, la clé numérique 123 n’est jamais prise pour un nom vide, et un index de 0 ou en dessous renvoie une chaîne vide depuis GetEmbeddedFileStrProperty au lieu du quelconque objet qui suit. Le tag 1 de cette fonction est le nom de fichier et le tag 2 le sous-type MIME

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // arbre de nombres /PageLabels ; les fichiers sans renvoient des numéros de page simples
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // arbre de noms /EmbeddedFiles ; index à base 1, clés non chaîne sautées
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nom, sous-type MIME
    // arbre de noms /JavaScript : liste les noms de paquets, n’exécute rien
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Un fichier de test à deux pages montre bien la sortie attendue. Donnez à sa racine /PageLabels un tableau /Kids qui liste une feuille deux fois et référence aussi la racine elle-même, avec des plages pour le romain minuscule depuis la page 1 et le décimal préfixé A- depuis la page 2. L’audit devrait imprimer i et A-1, chaque plage appliquée une fois. Écrire des étiquettes de page dans un tel arbre a ses propres rugosités, couvertes dans la réparation des étiquettes de page PDF stockées dans des arbres de nombres /Kids ; AddPageLabels aplatit une racine /Kids en une seule feuille /Nums avant l’insertion, avec la même énumération sûre contre les cycles

Là où le parcours trace ses limites

Le parcours garantit la terminaison, un ordre stable et des réponses justes pour tout arbre dont les vraies clés sont intactes. Il lit un arbre endommagé tel qu’il est écrit et ne tente pas de reconstruire ce que l’auteur visait, et cinq conséquences suivent de ce choix

  • L’identité, pas le contenu, définit un nœud. Deux dictionnaires distincts aux entrées identiques sont deux nœuds, si bien qu’un producteur qui copie une feuille au lieu de la référencer obtient ces entrées deux fois
  • Une paire /Limits bien formée et ordonnée élague même quand elle est fausse. Une plage qui ment de façon plausible, disons [(a) (m)] sur une feuille qui porte aussi (q), cache q. La seule défense serait d’ignorer /Limits partout et de scanner chaque feuille, et sur un arbre de destinations à des dizaines de milliers d’entrées cela jette la raison d’être de l’entrée. Nous gardons l’élagage
  • L’énumération préserve l’ordre du fichier. GetPageLabel parcourt chaque plage énumérée et applique la dernière dont l’index de départ est au plus celui de la page, si bien qu’un producteur qui écrit des plages en désordre obtient une sémantique d’ordre de fichier, et inverser la marche donnerait à la page 200 le style des pages liminaires
  • La mémoire croît avec les nœuds distincts et les entrées. Le parcours ajoute une liste et un ensemble de hachage au-dessus des objets analysés
  • Les clés dupliquées dans une même feuille se résolvent de façon déterministe : la recherche dichotomique renvoie la paire correspondante sur laquelle elle atterrit en premier, et le repli linéaire garde la dernière correspondance qu’il scanne

Les outils de préflight, les archiveurs et les visualiseurs de documents lisent ces arbres avant qu’une seule page ne soit rendue, ce qui les met en première ligne pour tout ce qui arrive dans une file de téléversement. Les lecteurs d’arbres décrits ici se livrent avec PDFlibPas, la PDF Library for Delphi, qui se construit aussi bien avec Delphi qu’avec Free Pascal