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
| Arbre | Où il se trouve | Spécification | API de lecture PDFlibPas |
|---|---|---|---|
| Destinations nommées | /Dests dans le dictionnaire des noms | §12.3.2.3 | GetNamedDestination, puis GetDestPage / GetDestType |
| Étiquettes de page | /PageLabels dans le catalogue (arbre de nombres) | §12.4.2 | GetPageLabel |
| Pièces jointes | /EmbeddedFiles dans le dictionnaire des noms | §7.7.4, §7.11.4 | EmbeddedFileCount, GetEmbeddedFileStrProperty |
| JavaScript au niveau document | /JavaScript dans le dictionnaire des noms | §7.7.4 | GlobalJavaScriptCount, 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
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
/Limitsabsents : 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 satisfaitLo <= Key <= HiquandLo > 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
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
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
/Limitsbien 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), cacheq. La seule défense serait d’ignorer/Limitspartout 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.
GetPageLabelparcourt 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