PDF.js 源码解读: name_number_tree

前言

这是 PDF.js 源码解读系列中关于「名称树与数字树」的一篇，介绍 src/core/name_number_tree.js（169 行）。

在 PDF 规范里，很多「按名字查」或「按编号查」的数据并不放在普通字典里，而是放在一种分层、有序、可跨对象引用的树结构中。典型例子是：

• 文档级命名目标（/Names 下的 /Dests），把书签里的名字映射到页面位置；
• 附件（/EmbeddedFiles），把文件名映射到文件流；
• 文档级 JavaScript（/JavaScript），把脚本名映射到动作字典；
• 页面标签（/PageLabels），把页码映射到标签样式；
• 结构树里的父节点表（/ParentTree），把结构元素编号映射到内容项数组。

这些结构分两种：键是字符串的叫 NameTree，键是整数的叫 NumberTree。两者在规范里是两节（7.9.6 与 7.9.7），但节点形态几乎一样，所以 PDF.js 只写了一个基类 NameOrNumberTree，再用两个十行左右的子类把「键的名字」定下来。

一句话概括这个模块的职责：把一棵可能分散在多个间接对象里的有序树，压平成一张 Map，或者按单个键做一次二分查找。

模块总览

name_number_tree.js 很短，可以切成四块：

它在整条链路里的位置：

Catalog / StructTreeRoot / PDFEditor
  → new NameTree(root, xref)
  → getAll()             （整棵树压平成 Map）
  → get(key) / getRaw(key) （单键二分查找）
  → XRef.fetchIfRef      （把 Ref 换成真实对象）
  → Dict / 数组 / 页面目标

版本说明：本篇严格按当前仓库这一版 name_number_tree.js 讲解。构造函数是 constructor(root, xref, type)，只有三个字段 root、xref、_type；没有 dict、parent、ref 参数，也没有私有字段 #map、has() 方法或「惰性构建一次、之后复用」的缓存。getAll 每次调用都会重新遍历并新建 Map。旧版本里常见的 parent / ref 循环检测，在本版被 getAll 内的 RefSet 与 getRaw 内的深度上限取代。读源码时不要套用记忆里的其它版本 API。

一棵树，两种键

先看树本身。NameTree 与 NumberTree 的节点只有两种形态：

1. 中间节点：带 Kids 数组，数组元素是子节点的间接引用或字典；
2. 叶子节点：带 Names 或 Nums 数组，数组按「键、值、键、值」交替排列。

叶子在源码里就是一个普通数组，所以一对键值只是相邻的两个元素，而不是对象：

// NameTree 叶子（示意）
{
  Names: ['Alpha', 12, 'Beta', 13];
}
 
// NumberTree 叶子（示意）
{
  Nums: [0, 12, 1, 13];
}

PDF 规范要求键有序：NameTree 按字符串的字节序升序，NumberTree 按数值升序。这个「有序」不是装饰，而是 getRaw 能做二分查找的前提。

两种树共享同一套节点结构，差异只在「键字段叫什么」。因此基类把所有逻辑写一次，子类只传一个字符串。

构造函数

基类的构造函数只有十几行，却做了两件事：拒绝被直接实例化，以及保存三个字段。

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;
  }

字段的含义可以直接列出来：

root 允许是 Ref，这一点很关键。调用方通常从父字典里用 getRaw 取出根，例如 obj.getRaw("Dests")，拿到的可能是 12 0 R，而不是已经展开的字典。基类不急着解引用，而是把 Ref 原样保存，等遍历时再交给 xref.fetchIfRef。这样构造本身没有 I/O，也不会因为根节点在缺失的网络分块里而抛出 MissingDataException。

构造函数的自检只在测试构建里生效：PDFJSDev.test("TESTING") 为真，并且 this.constructor 正好是基类本身时，调用 unreachable 抛错。生产构建里这个判断会被预处理掉，运行时没有额外开销。它的目的不是防御使用者，而是提醒维护者：基类不是一个可用的树，必须由 NameTree 或 NumberTree 给出 _type。

设计要点：构造函数不做任何解析。root 可以是一个尚未取回的 Ref，xref 也只是保存引用。真正的取对象动作被推迟到 getAll 与 getRaw 内部。这样一来，new NameTree(...) 是纯内存操作，可以在任何阶段安全创建；而网络分块的异常只会在真正读取时冒泡，交给上层重试。

读取接口

getAll 方法

getAll 的目标很直接：不管树有几层、节点是不是散落在对象流里，最后都返回一张「键 → 值」的 Map。

  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;
  }

这段代码有几个值得展开的细节。

广度优先，而不是递归

queue 是一个普通数组，for (const node of queue) 用的是数组迭代器。数组迭代器每一步都会重新读取 length，所以循环体里 queue.push(kid) 追加的节点会在后续迭代中被访问到。这是一个「边遍历边扩容」的队列，不需要额外的索引变量。

它遍历的顺序是广度优先：先根，再根的所有孩子，再孩子的孩子。对 getAll 来说顺序不重要，因为结果是一张 Map；但对重复检测来说顺序有意义——同一个 Ref 不论从哪条路径第二次出现，都会被同一个 processed 抓住。

processed 防的是「重复」，不是「环」

processed 的类型是 RefSet，只在节点是 Ref 时记录。根节点如果是 Ref，先放进去；每个 kid 如果是 Ref，先查再放。第二次遇到同一个引用，直接抛 FormatError，消息里带上 _type，便于定位是 NameTree 还是 NumberTree。

这里没有「当前路径」的概念，只有一个全局集合。因此它检测的不只是环，还包括「两个不同父节点指向同一个孩子」这种 DAG 结构。规范不允许树节点被共享，源码选择严格拒绝，而不是容忍后再去重。

如果根节点是直接的 Dict，它不会被记录；如果某个孩子又指回这个根字典（通过引用），引用本身仍然会被记录并检测。只有「完全没有引用的纯字典环」才可能绕过检测，而这种结构在 PDF 里无法通过对象引用形成，实际不会出现。

中间节点与叶子节点

判断依据是 obj.has("Kids")：

「有 Kids 就一定是中间节点」是规范的约定。源码没有检查「既有 Kids 又有 Names」这种畸形节点，而是让 Kids 优先。这样即使文件里多写了一个叶子字段，也不会重复收集。

isRaw 的两种语义

isRaw 决定键和值要不要解引用：

Catalog 的附件、目标、JavaScript 读取都用默认的 false；PDFEditor 读取 ParentTree 与 IDTree 时用 true，因为它要把引用原样带进编辑数据，后续写回文件时不能丢层级。

重复键不会报错

processed 只检查节点引用，不检查叶子里的键。如果两个叶子出现同一个键，Map.set 会静默覆盖，后遍历到的值获胜。规范禁止重复键，但 PDF.js 在这里选择了「不额外付出一次 Set 查询」的宽松策略。真正需要严格性的调用方，会在自己的上层逻辑里处理。

设计要点：getAll 的容错策略是「跳过坏节点，继续遍历」，只有重复引用会中断。它不追求把损坏的树修好，而是保证能读的部分都读出来。对一个可能来自任意生成器的 PDF 阅读器来说，这比「一处坏掉整棵树作废」更实用。

getRaw 方法

getRaw 负责单键查找。它不建表，而是沿着树的 Limits 做两层二分：先在 Kids 里找到可能包含目标键的孩子，再在叶子的键值数组里找到精确匹配。

第一层：沿 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 是每个非根节点必须携带的数组，两个元素分别是该子树的最小键与最大键。源码用它把「键是否可能在这个孩子里」变成两次比较：

选中孩子后，kidsOrEntries = kid，外层 while 继续检查这个孩子是否还有 Kids。如果它已经是叶子，循环自然结束。

MAX_LEVELS = 10 是深度上限。规范的树可以任意深，但正常文件的深度只有两三层；超过十层基本可以判定是损坏或恶意的环形结构。这里没有像 getAll 那样用 RefSet 记录访问过的节点，而是用固定上限兜底。代价是：如果文件合法但异常地深，会返回 null；收益是：不需要在每次下探时维护一个集合。

循环结束后有一个容易忽略的判断：

if (l > r) {
  return null;
}

二分查找只有在「找到并 break」时才会让 l 与 r 保持正常关系。如果循环是因为 l 越过 r 而结束，说明没有任何孩子的 Limits 覆盖目标键，此时 kidsOrEntries 还停留在上一层，不能继续在它的键值数组里查找。这个判断把「没找到」与「找到」区分开。

第二层：叶子内二分

    // 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;
  }

叶子是扁平数组，键在偶数下标，值在奇数下标。二分查找必须在「键下标」上进行，所以源码先算出中点 tmp，再用 tmp & 1 把奇数中点向上取整到偶数：

r 的初值是 entries.length - 2，也就是最后一个键的下标。向左收缩时 r = m - 2，向右收缩时 l = m + 2，每次跨过「键 + 值」两个槽位，保证 l 始终落在偶数下标上。

返回的是 entries[m + 1] 原值，不做解引用。这正是 getRaw 与 get 的分界线。

与 getAll 的容错差异

getRaw 的路径上有几处没有防御：

getAll 遇到坏节点会跳过，getRaw 则把异常留给调用方。这是有意的分工：批量读取用于「尽量多拿」，单键读取用于「精确回答」，后者不应该悄悄返回错误答案。调用方通常在自己的 try 里处理异常，例如 Catalog 读取页面标签时会捕获并记录警告。

设计要点：一层用 Limits 排除整棵子树，一层用键数组排除半个叶子。两层都是二分，但比较对象不同：上层比较的是区间边界，下层比较的是单个键。getRaw 因此不需要把整棵树读进内存，查询成本与树的深度和每层节点数成对数关系。

get 方法

get 只有一行，它把 getRaw 的结果交给 XRef 解引用：

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

这个设计把「查找」与「取对象」分开。需要保留 Ref 的调用方用 getRaw，例如结构树在判断父节点表里存的是不是引用；需要真实对象的调用方用 get，例如结构树在读取 ParentTree 的数组。

如果 getRaw 返回 null，fetchIfRef 会原样返回 null，所以 get 的未命中值也是 null，调用方不需要区分「键不存在」与「值为空」。

NameTree 与 NumberTree 子类

两个子类加起来只有十行：

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

它们只做一件事：把叶子字段名固定下来。所有遍历、二分、容错逻辑都在基类里。这种「一个基类 + 两个常量子类」的写法，比在基类里用布尔开关区分类型更清晰：_type 同时用于取叶子字段和拼错误消息，不需要额外的分支。

键序语义：字符串与数值

getRaw 里所有比较都写成 key < currentKey 或 key > currentKey。这两个运算符在 JavaScript 里会按操作数类型选择比较方式：

NameTree 的键是 PDF 字符串，不是 Name 对象。PDF 字符串在内存里可能已经被解码成 JavaScript 字符串：单字节编码的每个字符就是原始字节值，UTF-16BE 的每个字符是一个 16 位码元。对前者，码元比较与字节比较完全一致；对后者，码元比较相当于按 16 位单元排序，而不是按原始字节排序。

这带来一个边界情况：如果生成器把 UTF-16BE 字符串按字节序排序，而 PDF.js 按码元序比较，二分查找可能走错分支。实际文件里 NameTree 的键绝大多数是 ASCII 或 PDFDocEncoding，这个问题很少触发；即使触发，调用方通常还有「遍历整棵树再建表」的兜底路径，例如 Catalog.destinations 就是先 getAll 再查表。

NumberTree 没有这个问题：键是整数，JavaScript 的数值比较就是规范要求的数值比较。负数和零也能正确排序。

设计要点：源码没有自己实现字节比较函数，而是直接依赖 JavaScript 的 < 与 >。这在绝大多数 PDF 上是正确的，也避免了为每个键做一次编码转换。真正需要严格字节序的场景，应该由生成器保证排序，而不是由阅读器在每次比较时重新编码。

循环与容错

把模块里所有的保护点集中起来，可以得到一张完整的容错表：

这张表说明了一个重要事实：同一个模块的两种读取路径，容错策略并不一致。getAll 尽量吞掉错误，getRaw 尽量暴露错误。使用者在选择方法时，实际上也在选择「要完整还是精确」。

getAll 用 RefSet 做全局去重，getRaw 用深度上限做局部保护。前者能发现「同一个孩子被两个父亲引用」，后者能发现「一直往下走不到叶子」。两者都不处理「叶子内部键乱序」——那是规范生成方的责任，阅读器只负责按有序假设做二分。

在链路中的位置

NameTree 与 NumberTree 不是给页面渲染直接用的，它们服务于文档级的索引结构。当前仓库里的主要调用点：

以 Catalog.destinations 为例，链路是这样的：

Catalog.#readDests()
  → new NameTree(namesDict.getRaw("Dests"), xref)
  → nameTree.getAll()
  → Map<字符串, 目标数组或字典>
  → fetchDest(value)
  → 页面索引 + 坐标

注意 getRaw("Dests") 取的是原始值，可能是 Ref，也可能是字典。NameTree 的构造函数两种都接受，getAll 里的 fetchIfRef 会统一处理。这也是为什么构造函数不急着解引用：调用方拿到的形态并不固定。

总结

name_number_tree.js 是 PDF.js 的有序索引层：向下通过 XRef 解引用，向上给 Catalog、StructTreeRoot、PDFEditor 提供「整棵压平」与「单键查找」两种读取方式。

它在整条链路中的位置

用一句话串起来：父字典给出根，基类保存根，getAll 把树压成表，getRaw 沿 Limits 找到叶子，get 最后把引用换成对象。

四条设计原则

1. 一个基类，两个常量子类。NameTree 与 NumberTree 的节点形态完全一致，差异只有叶子字段名。把差异收敛成构造函数里的一个字符串，遍历与查找逻辑只写一次，错误消息也能直接带上类型。
2. 全量与单键分开容错。getAll 跳过坏节点、只对重复引用报错，目标是「能读多少读多少」；getRaw 不做多余防御，目标是「要么给准确答案，要么让调用方知道失败」。两种策略对应两种使用场景，不强行统一。
3. 有序假设只用于查找，不用于建表。getAll 完全不依赖键序，广度优先收集即可；getRaw 依赖 Limits 与键数组有序，用两层二分把查找压到对数级。建表与查找各自选择最合适的算法。
4. 引用保留到最后一刻。构造函数保存 root 原值，getRaw 返回原始值，get 才调用 fetchIfRef。需要引用结构的编辑器用 getAll(true) 或 getRaw，需要真实对象的目录用 get / 默认 getAll，同一份树数据可以服务两种消费者。

NameTree 与 NumberTree 本身不产生任何页面内容，但它们决定了很多「文档级功能」能不能被找到：书签跳转、附件下载、页面标签、无障碍结构。下一篇会离开这些索引结构，回到内容流一侧，看默认外观字符串如何被解析成字号与颜色。

StreamPDF 的设计原则: 能前置处理的绝对不放到解析的时候才做, 由服务端一次解决所有性能问题. 浏览器只获取&渲染必须数据.