Build a PDF whose /Dests name tree has a root with two children. The first child declares /Limits [(a) (z)], and its /Kids array points straight back at the root. The second child holds the real entry for (chapter7), but its limits are written backwards: [(z) (a)]. Ask a textbook name-tree lookup for chapter7 and it either recurses until the stack runs out or returns "not found" for a destination that a viewer can jump to. The whole file fits in about two kilobytes, and every object in it parses cleanly
That file packs three separate traps into one structure: a /Kids cycle, a range that claims a key it does not hold, and a range that can never match anything. A fourth trap needs a much bigger file. Once a single leaf carries more than 32,768 name/value pairs, any code that squeezes "which leaf" and "which entry" into one 32-bit integer starts pointing at the wrong pair. The rest of this article walks through each trap, what a reader should do about it, and how the Delphi calls behave on files built this way
Four PDF features that sit on name trees and number trees
Name trees and number trees back every PDF feature that maps a large key set to objects, and PDFlibPas, the losLab PDF Library for Delphi, exposes four of them through public TPDFlib methods. ISO 32000-1 §7.9.6 defines the name tree (string keys, Table 36) and §7.9.7 the number tree (integer keys, Table 37). Root and intermediate nodes carry /Kids; leaves carry sorted key/value pairs in /Names or /Nums; every non-root node is supposed to carry a two-element /Limits array holding the smallest and largest key beneath it
| Tree | Where it lives | Specification | PDFlibPas read API |
|---|---|---|---|
| Named destinations | /Dests in the name dictionary | §12.3.2.3 | GetNamedDestination, then GetDestPage / GetDestType |
| Page labels | /PageLabels in the catalog (number tree) | §12.4.2 | GetPageLabel |
| Attachments | /EmbeddedFiles in the name dictionary | §7.7.4, §7.11.4 | EmbeddedFileCount, GetEmbeddedFileStrProperty |
| Document-level JavaScript | /JavaScript in the name dictionary | §7.7.4 | GlobalJavaScriptCount, GlobalJavaScriptPackageName |
Two rows hide a wrinkle. Named destinations also exist in an older PDF 1.1 form, a plain /Dests dictionary in the catalog keyed by name objects, and GetNamedDestination checks that dictionary first and only then descends the PDF 1.2 name tree. The JavaScript row has a near-namesake that reads something else entirely: GetDocJavaScript returns scripts attached to the document triggers in the catalog /AA dictionary (WS, DS, WP, DP, DC), while the named packages that run when a document opens live in the /JavaScript name tree and are listed by GlobalJavaScriptPackageName
All of these structures come from the file. The specification tells a writer what it shall produce, and a reader still receives whatever the writer, a broken incremental save or a fuzzer actually put there. That is the same lesson as hardening a Pascal PDF parser against malicious files, applied to tree shape instead of buffer lengths
Why does a cyclic /Kids array crash a recursive tree walker?
A recursive walker crashes on a cyclic /Kids array because nothing in the recursion remembers which nodes it has already entered, so one child reference to an ancestor turns a finite file into an endless descent. A legitimate tree can do the same damage without any cycle: a 4,096-level chain of single-child nodes is valid syntax that costs a recursive reader 4,096 stack frames
The milder variant does not crash at all. When two /Kids entries reference the same leaf, a naive enumeration visits it twice, so an attachment count comes back higher than the number of files in the document and a script list shows the same package twice
PDFlibPas walks both kinds of tree with an explicit last-in, first-out stack on the heap plus a visited set keyed by dictionary identity. A node is marked when it is popped. A cyclic reference may sit on the stack for a moment, but it is discarded as soon as it comes back up, and each distinct node expands its children exactly once. Total work is bounded by the number of distinct dictionaries plus the combined length of their /Kids arrays; a 4,096-level chain becomes 4,096 loop iterations and 4,096 hash-set entries
Order is the part people get wrong when they convert recursion into a loop. A stack reverses whatever you feed it, so children have to be pushed from the last index down to the first; then the leftmost child pops first and the leaves come out in the left-to-right order the producer wrote. Marking on pop rather than on push matters for the same reason. With marks on push and right-to-left pushes, a leaf shared by positions 0 and 2 would be claimed by position 2, and its entries would appear later than the file says. Page labels depend on that order, as the last section shows
If you write your own tree code against some other object model, this is the shape we recommend. The node type below is deliberately abstract, and both functions are reader-side code, not library calls
uses
System.Generics.Collections;
type
TTreeNode = class
public
Kids: TArray<TTreeNode>; // empty on a leaf
Keys: TArray<string>; // leaf keys, sorted by a well-behaved producer
Values: TArray<Integer>; // parallel to Keys
HasLimits: Boolean;
LoKey, HiKey: string;
end;
// Your own helper: /Limits may prune only when it is a well-formed, ordered pair
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;
// Your own lookup: explicit stack, visited set, mark on pop
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 or shared child: already seen
Visited.Add(Node, 0);
if Length(Node.Kids) > 0 then
begin
// Push right-to-left so the leftmost kid is popped first
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;
// A miss in this leaf: keep popping its siblings
end;
finally
Visited.Free;
Pending.Free;
end;
end;
A miss in one branch means nothing about the tree
The most common lookup shortcut picks the first child whose /Limits covers the key, descends into it, and never looks at a sibling again. On a clean tree that is correct and fast. On the file from the opening paragraph it fails: the first child claims chapter7, leads back to the root, and the search ends empty-handed while the next sibling holds the entry
PDFlibPas does not stop at the first plausible branch. The keyed lookup behind GetNamedDestination pushes every child whose range does not rule the key out, and it keeps popping until it finds a match or the stack is empty. On a well-formed tree with disjoint ranges, one child at most survives the range check at each level, so the extra cost is nil. On a damaged one it is a handful of extra node visits, and the answer comes back right
Leaves get the same treatment. ISO 32000-1 requires the keys in a /Names array to be sorted by byte value, so the library tries a binary search first. When that misses, it falls back to a linear scan of the pairs, because an out-of-order leaf would otherwise make a present key invisible. Paying for a linear scan on every genuine miss is a cost we accept: lookups for names that are genuinely absent are rare, and a false "not found" on a working link costs far more than one extra pass over a leaf
One structural contradiction is handled by refusal. Table 36 lets a node carry either /Kids or /Names, never both. A keyed lookup treats a node carrying both as malformed and skips it instead of guessing which half the producer meant. Enumeration of number trees, such as the walk behind GetPageLabel, is more lenient and follows /Kids when both are present, since dropping a whole range would mislabel every page after it
What may a reader trust /Limits for?
A reader may trust /Limits to skip work, and only when the pair is well formed; it may never use the entry to conclude that a key is absent. Table 36 says intermediate and leaf nodes shall carry it, yet in practice the entry disappears after hand edits, holds numbers inside a name tree, or arrives with its bounds swapped. PDFlibPas resolves every one of those cases the same way, by keeping the child searchable
- Missing
/Limits: a range check that skips such a child makes its whole subtree unreachable whenever a producer forgets the entry, so the child is searched - Wrong type or wrong length, such as numbers in a name tree or a one-element array: handled exactly like a missing entry
- Reversed bounds such as
[(Z) (A)]or[9 0]: no key satisfiesLo <= Key <= HiwhenLo > Hi, so trusting the pair would exclude the branch for every lookup; a range prunes only when its lower bound does not exceed its upper bound - Well formed and ordered: used to skip the branch, which is what the entry exists for
From the caller's side there are two zeros to tell apart. GetNamedDestination returns 0 when the name really is absent and a destination ID otherwise. GetDestPage returning 0 for a valid ID means the name exists but its target does not resolve to a page in this document, which is a different bug report. GetDestType reports the view as 1 for XYZ, 2 for Fit and so on up to 8 for 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) first, then the /Dests name tree
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;
This makes a compact regression check. Build the two-child file from the opening paragraph, point the real chapter7 entry at page 2 with a /Fit view, and the procedure should print page 2 with view type 2. A first-match lookup prints "No destination" because the looping child wins the race; a lookup that trusts reversed ranges prints the same thing for the opposite reason. Once destinations resolve, the outline entries that point at them are covered in reading PDF bookmark and annotation actions in Delphi
Leaves past 32,768 entries and the packed-index trap
When code needs one integer handle for "entry N in leaf M", the tempting encoding packs the leaf position into the high 16 bits of an Integer and the offset inside that leaf's /Names array into the low 16 bits. Each pair takes two array slots. Pair index 32,768, the 32,769th pair, therefore starts at offset 65,536, which is $10000. That bit carries into the high half, and the decoder reads it back as offset 0 of the next leaf
The symptoms depend on tree shape. With a single leaf there is no next leaf, so the decoded handle indexes past the end of the leaf list. With several leaves, a find or a delete lands on the first pair of the following leaf, while a plain key scan still reports the requested key as present. Files this size are not exotic. A generated API reference with one named destination per symbol crosses 32,768 entries quickly, and some producers write every one of them into a single flat leaf instead of balancing the tree
PDFlibPas keeps the leaf position and the entry offset in two full-width integers, so neither can spill into the other at any leaf size. The same reader counts only genuine string keys. For a leaf such as [(Valid) 42 123 456], EmbeddedFileCount reports 1, the numeric key 123 is never mistaken for an empty name, and an index of 0 or below returns an empty string from GetEmbeddedFileStrProperty instead of whatever object happens to follow. Tag 1 of that function is the file name and tag 2 the MIME subtype
procedure AuditTrees(const FileName: string);
var
Lib: TPDFlib;
I: Integer;
begin
Lib := TPDFlib.Create;
try
if Lib.LoadFromFile(FileName, '') <> 1 then
Exit;
// /PageLabels number tree; files without one return plain page numbers
for I := 1 to Lib.PageCount do
WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
// /EmbeddedFiles name tree; indexes are 1-based, non-string keys skipped
for I := 1 to Lib.EmbeddedFileCount do
WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')'); // name, MIME subtype
// /JavaScript name tree: list package names, execute nothing
for I := 1 to Lib.GlobalJavaScriptCount do
WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
finally
Lib.Free;
end;
end;
A two-page test file shows the expected output well. Give its /PageLabels root a /Kids array that lists one leaf twice and also references the root itself, with ranges for lowercase roman from page 1 and decimal with prefix A- from page 2. The audit should print i and A-1, each range applied once. Writing page labels into a tree like that has its own wrinkles, covered in fixing PDF page labels stored in /Kids number trees; AddPageLabels flattens a /Kids root into a single /Nums leaf before inserting, using the same cycle-safe enumeration
Where the traversal draws its lines
The traversal guarantees termination, stable order and correct answers for any tree whose real keys are intact. It reads a damaged tree as written and does not try to reconstruct what the author intended, and five consequences follow from that choice
- Identity, not content, defines a node. Two distinct dictionaries with identical entries are two nodes, so a producer that copies a leaf instead of referencing it gets those entries twice
- A well-formed, ordered
/Limitspair prunes even when it is wrong. A range that lies plausibly, say[(a) (m)]over a leaf that also holds(q), hidesq. The only defense would be ignoring/Limitseverywhere and scanning every leaf, and on a destination tree with tens of thousands of entries that throws away the reason the entry exists. We keep pruning - Enumeration preserves file order.
GetPageLabelwalks every enumerated range and applies the last one whose start index is at or below the page, so a producer that writes ranges out of order gets file-order semantics, and reversing the walk would hand page 200 the front-matter style - Memory grows with distinct nodes and entries. The traversal adds one list and one hash set on top of the parsed objects
- Duplicate keys inside one leaf resolve deterministically: the binary search returns whichever matching pair it lands on first, and the linear fallback keeps the last match it scans
Preflight tools, archivers and document viewers read these trees before a single page is rendered, which puts them first in line for whatever arrives in an upload queue. The tree readers described here ship with PDFlibPas, the PDF Library for Delphi, which builds with both Delphi and Free Pascal