Technical Article

PDFlibPas Name Trees: Cycles, Bad Limits and Huge Leaves

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

TreeWhere it livesSpecificationPDFlibPas read API
Named destinations/Dests in the name dictionary§12.3.2.3GetNamedDestination, then GetDestPage / GetDestType
Page labels/PageLabels in the catalog (number tree)§12.4.2GetPageLabel
Attachments/EmbeddedFiles in the name dictionary§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
Document-level JavaScript/JavaScript in the name dictionary§7.7.4GlobalJavaScriptCount, 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

PDFlibPas name tree traversal: a Kids array looping back to the root overflows the stack of a recursive walker, so PDFlibPas uses an explicit stack and a visited set that marks nodes on pop, pushes children right-to-left and keeps leaves in file order for GetPageLabel
Depth stops mattering when recursion becomes a loop: a 4,096-level chain is just 4,096 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 satisfies Lo <= Key <= Hi when Lo > 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
PDFlibPas rules for trusting a name tree Limits array: a missing, wrong-typed or reversed pair leaves the child searchable, and only a well-formed ordered pair may prune the branch, so a hostile Limits can cost visits but cannot hide an existing destination
Ranges may skip work but never decide absence, because the real keys stored in the leaves decide the outcome of every lookup

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

Packed name tree index where a leaf position and an entry offset share one 32-bit Integer and pair 32768 starts at offset 65536, so the carry into the high half reads as offset 0 of the next leaf and a find or delete touches the wrong pair while a separate key scan disagrees
Two 16-bit values in one 32-bit integer truncate silently the moment a leaf crosses 32,768 pairs, a size real reference manuals reach

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 /Limits pair prunes even when it is wrong. A range that lies plausibly, say [(a) (m)] over a leaf that also holds (q), hides q. The only defence would be ignoring /Limits everywhere 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. GetPageLabel walks 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