PDF.js Source Walkthrough: name_number_tree

Introduction

This is the article in the PDF.js source walkthrough series about name and number trees. It covers src/core/name_number_tree.js (169 lines).

In the PDF specification, a lot of data that is looked up by name or by number is not stored in an ordinary dictionary but in a hierarchical, ordered tree that can reference objects across the file. Typical examples:

• document-level named destinations (/Dests under /Names), mapping names used by bookmarks to page positions;
• attachments (/EmbeddedFiles), mapping file names to file streams;
• document-level JavaScript (/JavaScript), mapping script names to action dictionaries;
• page labels (/PageLabels), mapping page numbers to label styles;
• the parent tree in a structure tree (/ParentTree), mapping structure element numbers to arrays of content items.

These structures come in two kinds: those whose keys are strings are called NameTree, and those whose keys are integers are called NumberTree. The specification treats them in two sections (7.9.6 and 7.9.7), but their node shapes are nearly identical, so PDF.js writes a single base class NameOrNumberTree and then two subclasses of about ten lines each that just fix the key field name.

In one sentence, the module's job is: flatten an ordered tree that may be spread across several indirect objects into a single Map, or perform one binary search for a single key.

Module Overview

name_number_tree.js is short and splits into four parts:

Where it sits in the chain:

Catalog / StructTreeRoot / PDFEditor
  → new NameTree(root, xref)
  → getAll()             (flatten the whole tree into a Map)
  → get(key) / getRaw(key) (single-key binary search)
  → XRef.fetchIfRef      (turn a Ref into the real object)
  → Dict / array / page destination

Version note: This article follows exactly the version of name_number_tree.js in the current repository. The constructor is constructor(root, xref, type) and has only three fields, root, xref and _type; there are no dict, parent or ref parameters, no private #map, no has() method and no "build once lazily, reuse afterwards" cache. getAll traverses again and builds a new Map on every call. The parent / ref cycle detection common in older versions is replaced here by the RefSet inside getAll and the depth cap inside getRaw. Do not apply APIs from other versions you remember when reading the source.

One Tree, Two Kinds of Keys

Start with the tree itself. NameTree and NumberTree nodes come in only two shapes:

1. Interior nodes: they carry a Kids array whose elements are indirect references or dictionaries pointing at child nodes;
2. Leaf nodes: they carry a Names or Nums array laid out as key, value, key, value.

A leaf is just an ordinary array in the source, so a key-value pair is two adjacent elements rather than an object:

// NameTree leaf (illustrative)
{
  Names: ['Alpha', 12, 'Beta', 13];
}
 
// NumberTree leaf (illustrative)
{
  Nums: [0, 12, 1, 13];
}

The PDF specification requires keys to be ordered: NameTree by the byte order of the string in ascending order, NumberTree by numeric value in ascending order. This ordering is not decoration; it is the precondition that lets getRaw perform a binary search.

Both trees share the same node structure; they differ only in the name of the key field. The base class therefore writes all the logic once and each subclass passes in a single string.

The Constructor

The base constructor is only a dozen lines long, but it does two things: refuse direct instantiation and store three fields.

class NameOrNumberTree {
  constructor(root, xref, type) {
    if (
      (typeof PDFJSDev === "undefined" || PDFJSDev.test("TESTING")) &&
      this.constructor === NameOrNumberTree
    ) {
      unreachable("Cannot initialize NameOrNumberTree.");
    }
    this.root = root;
    this.xref = xref;
    this._type = type;
  }

The fields are easy to list:

root is allowed to be a Ref, which matters. Callers usually pull the root out of a parent dictionary with getRaw, for example obj.getRaw("Dests"); what comes back may be 12 0 R rather than an already expanded dictionary. The base class does not rush to dereference it, keeping the Ref as is and handing it to xref.fetchIfRef only during traversal. Construction therefore performs no I/O and cannot throw MissingDataException just because the root lives in a network chunk that has not arrived.

The constructor's self-check only takes effect in test builds: when PDFJSDev.test("TESTING") is true and this.constructor is exactly the base class, it calls unreachable to throw. In production builds that check is preprocessed away, leaving no runtime cost. Its purpose is not to defend against users but to remind maintainers: the base class is not a usable tree, and NameTree or NumberTree must supply _type.

Design note: The constructor parses nothing. root may be a Ref that has not been fetched, and xref is merely stored. The real object retrieval is deferred into getAll and getRaw. As a result new NameTree(...) is a pure in-memory operation that can be created safely at any stage, and exceptions from missing network chunks only surface when data is actually read, where the caller can retry.

Reading Interfaces

The getAll Method

getAll has a straightforward goal: no matter how many levels the tree has or whether its nodes are scattered through object streams, it returns a single Map from key to value.

  getAll(isRaw = false) {
    const map = new Map();
    if (!this.root) {
      return map;
    }
    const xref = this.xref;
    // Reading Name/Number tree.
    const processed = new RefSet();
    if (this.root instanceof Ref) {
      processed.put(this.root);
    }
    const queue = [this.root];
    for (const node of queue) {
      const obj = xref.fetchIfRef(node);
      if (!(obj instanceof Dict)) {
        continue;
      }
      if (obj.has("Kids")) {
        const kids = obj.get("Kids");
        if (!Array.isArray(kids)) {
          continue;
        }
        for (const kid of kids) {
          if (kid instanceof Ref) {
            if (processed.has(kid)) {
              throw new FormatError(`Duplicate entry in "${this._type}" tree.`);
            }
            processed.put(kid);
          }
          queue.push(kid);
        }
        continue;
      }
      const entries = obj.get(this._type);
      if (!Array.isArray(entries)) {
        continue;
      }
      for (let i = 0, ii = entries.length; i < ii; i += 2) {
        map.set(
          isRaw ? entries[i] : xref.fetchIfRef(entries[i]),
          isRaw ? entries[i + 1] : xref.fetchIfRef(entries[i + 1])
        );
      }
    }
    return map;
  }

There are several details in this code worth expanding.

Breadth-first, not recursion

queue is an ordinary array and for (const node of queue) uses the array iterator. The array iterator re-reads length on every step, so nodes appended with queue.push(kid) inside the loop body are visited in later iterations. This is a queue that grows while it is traversed, and it needs no extra index variable.

The traversal order is breadth-first: root, then all of the root's children, then their children. Order does not matter to getAll because the result is a Map, but it does matter to duplicate detection: a Ref that appears a second time along any path is caught by the same processed set.

processed guards duplicates, not cycles

processed is a RefSet and records only nodes that are Refs. If the root is a Ref it is added first; each kid that is a Ref is checked and then added. The second encounter with the same reference throws a FormatError whose message includes _type, so it is easy to tell whether the NameTree or the NumberTree is at fault.

There is no notion of a current path here, only a global set. So it detects not just cycles but also DAG shapes where two different parents point at the same child. The specification forbids sharing tree nodes, and the source chooses to reject it strictly rather than tolerate it and deduplicate afterwards.

If the root is a plain Dict it is not recorded; if some child points back to that root dictionary through a reference, the reference itself is still recorded and checked. Only a pure dictionary cycle with no references at all can slip through, and such a structure cannot be formed through object references in a PDF, so it does not occur in practice.

Interior nodes and leaves

The decision is based on obj.has("Kids"):

The specification's convention is that a node with Kids is always an interior node. The source does not check for malformed nodes that have both Kids and Names; it simply gives Kids priority. That way, even if a file writes an extra leaf field, no entries are collected twice.

The two meanings of isRaw

isRaw decides whether keys and values are dereferenced:

Catalog uses the default false for attachments, destinations and JavaScript; PDFEditor uses true when reading ParentTree and IDTree because it needs to carry references into the edit data unchanged, and the hierarchy must not be lost when the file is written back.

Duplicate keys do not raise an error

processed only checks node references, not the keys inside leaves. If two leaves contain the same key, Map.set silently overwrites and the value visited later wins. The specification forbids duplicate keys, but PDF.js chooses the lenient policy here to avoid paying for an extra Set lookup. Callers that truly need strictness handle it in their own upper layer.

Design note: getAll's fault-tolerance policy is to skip the bad node and keep traversing; only a duplicate reference aborts. It does not try to repair a damaged tree, only to read as much as it can. For a PDF viewer that may receive files from arbitrary producers, that is more practical than invalidating the whole tree because of one bad spot.

The getRaw Method

getRaw handles single-key lookup. It builds no table; instead it performs two layers of binary search along the tree's Limits: first locate the child within Kids that may contain the target key, then find the exact match in the leaf's key-value array.

Layer one: descend along Kids

  getRaw(key) {
    if (!this.root) {
      return null;
    }
    const xref = this.xref;
    let kidsOrEntries = xref.fetchIfRef(this.root);
    let loopCount = 0;
    const MAX_LEVELS = 10;
 
    // Perform a binary search to quickly find the entry that
    // contains the key we are looking for.
    while (kidsOrEntries.has("Kids")) {
      if (++loopCount > MAX_LEVELS) {
        warn(`Search depth limit reached for "${this._type}" tree.`);
        return null;
      }
 
      const kids = kidsOrEntries.get("Kids");
      if (!Array.isArray(kids)) {
        return null;
      }
 
      let l = 0,
        r = kids.length - 1;
      while (l <= r) {
        const m = (l + r) >> 1;
        const kid = xref.fetchIfRef(kids[m]);
        const limits = kid.get("Limits");
 
        if (key < xref.fetchIfRef(limits[0])) {
          r = m - 1;
        } else if (key > xref.fetchIfRef(limits[1])) {
          l = m + 1;
        } else {
          kidsOrEntries = kid;
          break;
        }
      }
      if (l > r) {
        return null;
      }
    }

Limits is an array every non-root node must carry, holding the smallest and largest key of its subtree. The source turns the question of whether the key could be in this child into two comparisons:

After selecting a child, kidsOrEntries = kid and the outer while checks whether that child still has Kids. If it is already a leaf, the loop ends naturally.

MAX_LEVELS = 10 is the depth cap. A specification tree can be arbitrarily deep, but real files are only two or three levels; more than ten levels is almost certainly corruption or a malicious cycle. Unlike getAll, this path does not track visited nodes with a RefSet; it falls back to a fixed limit. The cost is that a legal but unusually deep file returns null; the benefit is that no set has to be maintained on every descent.

After the loop there is an easily overlooked check:

if (l > r) {
  return null;
}

A binary search leaves l and r in a normal relationship only when it found the child and breaks. If the loop ended because l passed r, no child's Limits covered the target key, and kidsOrEntries still points at the previous level, where searching its key-value array would be wrong. This check separates a miss from a hit.

Layer two: binary search inside the leaf

    // If we get here, then we have found the right entry. Now go through the
    // entries in the dictionary until we find the key we're looking for.
    const entries = kidsOrEntries.get(this._type);
    if (Array.isArray(entries)) {
      // Perform a binary search to reduce the lookup time.
      let l = 0,
        r = entries.length - 2;
      while (l <= r) {
        // Check only even indices (0, 2, 4, ...) because the
        // odd indices contain the actual data.
        const tmp = (l + r) >> 1,
          m = tmp + (tmp & 1);
        const currentKey = xref.fetchIfRef(entries[m]);
        if (key < currentKey) {
          r = m - 2;
        } else if (key > currentKey) {
          l = m + 2;
        } else {
          return entries[m + 1];
        }
      }
    }
    return null;
  }

The leaf is a flat array with keys at even indices and values at odd indices. The binary search must run on key indices, so the source first computes a midpoint tmp and then rounds an odd midpoint up to an even index with tmp & 1:

r starts at entries.length - 2, the index of the last key. Shrinking left uses r = m - 2 and shrinking right uses l = m + 2, each time stepping over a key and value pair so that l always lands on an even index.

The return value is the raw entries[m + 1], not dereferenced. That is exactly the dividing line between getRaw and get.

Fault-tolerance differences from getAll

getRaw leaves several spots undefended along its path:

getAll skips bad nodes; getRaw leaves exceptions to the caller. That division is deliberate: bulk reading aims to get as much as possible, single-key reading aims to answer precisely, and the latter must not quietly return a wrong answer. Callers usually handle exceptions in their own try, for example Catalog catches and logs a warning when reading page labels.

Design note: One layer uses Limits to rule out an entire subtree, the other uses the key array to rule out half a leaf. Both are binary searches, but they compare different things: the upper layer compares interval bounds, the lower layer compares individual keys. getRaw therefore never needs to load the whole tree into memory, and query cost is logarithmic in tree depth and fan-out.

The get Method

get is a single line; it passes the result of getRaw to XRef for dereferencing:

  get(key) {
    return this.xref.fetchIfRef(this.getRaw(key));
  }

This design separates lookup from object retrieval. Callers that need to keep the Ref use getRaw, for example the structure tree checking whether the parent tree holds a reference; callers that need the real object use get, for example the structure tree reading the array in ParentTree.

If getRaw returns null, fetchIfRef returns null unchanged, so get's miss value is also null and callers need not distinguish a missing key from an empty value.

The NameTree and NumberTree Subclasses

Together the two subclasses are only ten lines:

class NameTree extends NameOrNumberTree {
  constructor(root, xref) {
    super(root, xref, 'Names');
  }
}
 
class NumberTree extends NameOrNumberTree {
  constructor(root, xref) {
    super(root, xref, 'Nums');
  }
}

They do one thing: fix the leaf field name. All traversal, binary search and fault tolerance live in the base class. This one-base-class-plus-two-constant-subclasses style is clearer than a boolean switch in the base class: _type is used both to fetch the leaf field and to build error messages, with no extra branching.

Key Ordering Semantics: Strings and Numbers

Every comparison in getRaw is written as key < currentKey or key > currentKey. In JavaScript these operators choose a comparison mode based on operand type:

NameTree keys are PDF strings, not Name objects. In memory a PDF string may already have been decoded into a JavaScript string: each character of a single-byte encoding is the original byte value, and each character of UTF-16BE is a 16-bit code unit. For the former, code-unit comparison is exactly byte comparison; for the latter, code-unit comparison sorts by 16-bit units rather than by raw bytes.

This creates an edge case: if a producer sorts UTF-16BE strings by byte order while PDF.js compares by code-unit order, the binary search can take the wrong branch. In practice the vast majority of NameTree keys in real files are ASCII or PDFDocEncoding, so this rarely triggers; even if it does, callers usually have a fallback path that traverses the whole tree and builds a table, as Catalog.destinations does by calling getAll first.

NumberTree has no such problem: its keys are integers, and JavaScript numeric comparison is exactly the comparison the specification requires. Negative numbers and zero sort correctly too.

Design note: The source does not implement its own byte comparison function; it relies directly on JavaScript's < and >. That is correct for nearly every PDF and avoids an encoding conversion per key. In cases where strict byte order really matters, the producer should guarantee the sorting, not the reader re-encode on every comparison.

Cycles and Fault Tolerance

Collecting every guard in the module produces a complete fault-tolerance table:

This table makes an important point: the two read paths in the same module do not use the same fault-tolerance policy. getAll swallows errors where it can; getRaw exposes them where it can. By choosing a method, the caller also chooses complete or precise.

getAll uses RefSet for global deduplication and getRaw uses a depth cap for local protection. The former can detect one child referenced by two parents; the latter can detect descending forever without reaching a leaf. Neither handles out-of-order keys inside a leaf - that is the producer's responsibility, and the reader only performs a binary search on the assumption that keys are ordered.

Where It Sits in the Chain

NameTree and NumberTree are not used directly for page rendering; they serve document-level index structures. The main call sites in the current repository are:

Taking Catalog.destinations as an example, the chain looks like this:

Catalog.#readDests()
  → new NameTree(namesDict.getRaw("Dests"), xref)
  → nameTree.getAll()
  → Map<string, destination array or dictionary>
  → fetchDest(value)
  → page index + coordinates

Note that getRaw("Dests") returns the raw value, which may be a Ref or a dictionary. The NameTree constructor accepts either, and fetchIfRef inside getAll handles them uniformly. That is also why the constructor does not rush to dereference: the shape the caller receives is not fixed.

Conclusion

name_number_tree.js is PDF.js's ordered index layer: downward it dereferences through XRef, upward it offers Catalog, StructTreeRoot and PDFEditor two ways to read, flatten the whole tree and look up a single key.

Where It Sits in the Overall Chain

In one sentence: the parent dictionary provides the root, the base class stores it, getAll flattens the tree into a table, getRaw walks Limits down to a leaf, and get finally turns the reference into an object.

Four Design Principles

1. One base class, two constant subclasses. NameTree and NumberTree have exactly the same node shape and differ only in the leaf field name. The difference collapses into one string in the constructor, so traversal and lookup are written once and error messages can include the type directly.
2. Bulk and single-key reads tolerate faults differently. getAll skips bad nodes and reports only duplicate references, aiming to read as much as possible; getRaw does no extra defending, aiming either to give an exact answer or to let the caller know it failed. The two policies match two use cases and are not forced into one.
3. The ordering assumption is used for lookup, not for table building. getAll does not depend on key order at all; breadth-first collection is enough. getRaw depends on ordered Limits and key arrays and uses two binary searches to reduce lookup to logarithmic time. Table building and lookup each pick the algorithm that suits them.
4. References are preserved until the last moment. The constructor stores the raw root, getRaw returns raw values, and only get calls fetchIfRef. Editors that need the reference structure use getAll(true) or getRaw; catalogs that need real objects use get or the default getAll. The same tree data can serve both consumers.

NameTree and NumberTree produce no page content themselves, but they decide whether many document-level features can be found: bookmark jumps, attachment downloads, page labels, accessibility structure. The next article leaves these index structures and returns to the content stream side to see how a default appearance string is parsed into font size and color.

StreamPDF design principle: anything that can be handled ahead of time is absolutely not deferred to parse time; the server solves all performance problems once. The browser only fetches and renders the data it must.