最近我因为个人项目的原因开始深入了解 TeX。虽然 The TeXbook 和 TeX By Topic 两本书都很详尽地记述了 TeX 的运行机制机制，但读来仍然有一种雾里看花，知其然而不知其所以然的感觉。要清晰了解一个程序的行为，终究没有比直接阅读其源代码更好的方法了。好在 Knuth 一开始就公开了 TeX 的源代码并附上了非常完善的注释。然而无论如何，40 年前的古董级代码理解起来也绝非易事，所以我想还是开一篇文章记录一下吧。这篇文章基本按照 TeX The Program 里面的章节顺序，对每一章略过细节进行简要的概述，其目的主要是帮助我回忆。当然，既然发在了博客上，我也希望我的笔记能够帮到也对 TeX 内部实现感兴趣的同好。

本文假定读者对于 TeX 的基本机制有比较充分的了解（指通读过 The TeXbook）。换而言之，对于诸如如何定义宏，\edef 和 \def 的区别，什么是 horizontal mode，什么是 glue 等话题，我不会在这篇文章中做出过多的解释。Knuth 花了一整本书解释这些概念，你指望我一个半吊子在一片博客文章里就解释清楚？笑死，根本不可能。

TeX 的奇妙基本架构

TeX 是用 WEB 语言编写的。WEB 语言遵循 Knuth 提出的 “文学编程 /literate programming” 的范式，夹杂文档和代码，可以看作是当今学术界常用的 Jupyter Notebook 的前身（当然，一个很大的区别是如今一个 notebook 不会超过 20 个 cell，但 TeX 有 1300 多个……）。文档部分基于 TeX，代码基于类 Pascal（之所以说 “类”，是因为当时 Pascal 的标准化还没完成）。如此一来，一个 tex.web 源文件，用 tangle 提取代码可以得到一份 Pascal 源文件用于构建程序本身，用 weave 提取文档则可以得到一份 TeX 源文件，编译成所谓的 TeX The Program。在后文中我会使用形如 TTP100 的记号表示 TeX The Program 某节的内容。

为了增加可读性，TeX 源代码中每一个 “cell” 包含的代码都不超过一页纸（通常更是不超过 20 行），对于比较长的函数，Knuth 会把一部分逻辑分离到其他 “cell” 中去并在原地插入引用。tangle 提取代码的过程本质上就是把基于这些引用对代码块进行重排。除此以外，Knuth 还通过 WEB 定义了一部分宏，这部分宏的替换也是由 tangle 在生成代码的时候完成的。

如果粗略地看，TeX 的源代码是非常模块化的，但是实际上却未必然。后一章定义的宏可能只是前几章某个宏的别名，导致对一个模块的修改可能会导致意想不到的结果， 又或者是虽然抽象出来了一些可以复用的函数，但是这些函数接口的形式极大地约束了实现的方案，导致事实上灵活性的缺失。模块化的设计势必包含一定的抽象，而抽象都伴随这一定的代价。在 TeX 开发的时代系统资源相当受限，语言标准缺失，各种 infrastructure 也不成熟，效率和兼容性是第一目标，因此代码设计成这样是可以理解的 —— 只是苦了像我一样被现代开发范式惯坏的后来者。

TeX 的奇妙字符串处理

TeX 实现了自己的一套极具特色的动态储存字符串的方案。 简单来说，TeX 有一个巨大的静态分配的 char 数组 str_pool，以及一个元素递增的下标数组 str_start。TeX 给每个字符串赋予一个编号。编号 s 的字符串存储于 str_pool 下标中的 str_start[s] 以及 str_start[s + 1] 之间。以下 C 伪代码可以将 TeX 的字符串转换为 C 风格的字符串：

char *texstr_to_cstr(uint16_t s) {
    size_t len = str_start[s + 1] - str_start[s];
    char *ret = malloc(len + 1);
    memcpy(ret, str_pool + str_start[s], len);
    ret[len] = 0;
    return ret;
}

在运行过程中，TeX 会维护 pool_ptr 和 str_ptr 两个变量，分别表示 str_pool 中最小可用的下标以及最小的可用的字符串编号。新建一个字符串大概是这样的：

uint16_t cstr_to_texstr(char *s) {
    size_t len = strlen(s);
    assert(str_start[str_ptr] == pool_ptr);
    memcpy(str_pool + str_start[str_ptr], s, len);
    str_start[++str_ptr] = pool_ptr += len;
    return str_ptr - 1;
}

当然，实际上 TeX 在构建新字符串的时候是逐字符添加的，pool_ptr 也是逐步递增。这又涉及到很多骚操作（例如 append 字符之后还能 flush 吐出来等等），在此略过。TeX 有两个比较字符串的方法，str_eq_buf 比较一个内部字符串和一个 char* 是否相等；str_eq_str 比较两个内部字符串是否相等。

此外，TeX 源代码中的所有字符串字面量，会在 WEB TANGLE 的时候被抽取到一个编译器的 string pool 里作为 str_pool 的基础，原地只会留下对应字符串的编号。所以在源代码里的字符串字面量，其实都是整数类型。

TeX 的奇妙算术

还是时代的原因，TeX 问世时 IEEE754 还没有出，当时各型机器、各个编译器上对于浮点数的算术运算都遵循不同的标准。因此，TeX 为了规避这种不确定性，很大一部分计算都基于其自身定义的定点数 ——Knuth 称之为 scaled number。定点数长 4 字节，以 \(2^{-16}\) 为最小单位。换而言之，如果直接把定点数当 int32_t 读，得到的是其所表示值的 \(2^{16}\) 倍。除此以外，当时各个平台对于对负数的整除和取模运算的实现存在分歧，因此 TeX 除了几处非核心算法，其余的部分在整除和取模前都检查操作数的正负性。

TeX 的定点数计算函数里有很多令人啧啧称奇的操作。例如，以下函数用于近似计算 \(100(t/s)^3\)（以下注释是我补的，原文没有解释 7230584 和 1663497 两个 magic number 的由来）。

typedef int16_t scaled;
const int16_t inf_bad = 10000;
int16_t badness(scaled t, scaled s) {
    if (t == 0) return 0;
    if (s <= 0) return inf_bad;
    int r; // 近似于 2⁶ * ³√100 * t /s
    // 297³ ≈ 100 * 2¹⁸
    // 如果 t > 7230584 则 t * 297 >= 2147483647 会溢出
    if (t <= 7230584) r = (t * 297) / s;
    // 此时 t >= 7230585，如果 s / 297 < 1663497 / 297 = 5601 的话，
    // t / (s / 297) >= 1291，此时（见下）一定会 return inf_bad
    // 除法很慢，所以如果具体结果不重要就不要做
    else if (s >= 1663497) r = t / (s / 297);
    else r = t;
    // 如果 r > 1290，则 r * r * r  + (1 << 17) 会溢出
    if (r > 1290) return inf_bad;
    return (r * r * r + (1 << 17)) >> 18;
}

可以看到，代码非常细致地考察了溢出的可能性，全程整数计算避免了浮点的不确定性，s >= 1663497 这个条件更是在一定情况下避免了耗时的除法运算 —— 非常有 Knuth 的风格。

TeX 内部存储长度的单位是 pt，格式自然是定点数。1 inch 是 72.27 pt。因此，所有 TeX 长度的最小单位是 \(\frac1{72.27}\cdot2^{-16}=\frac{1}{4736286.72}\) inch。

除此以外，TeX 还有一个数据类型称作 glue_ratio，等同于一个 32 位浮点数。它只有一个使用场景：在将一个 list 固化成一个 box 之后，存储 list 内部 glue 的伸缩比。因为 box 的大小是已经决定的了，此时精度问题不会对 TeX 的行为产生任何影响。

typedef float glue_ratio;

TeX 的奇妙内存分配

不出所料，TeX 也不会调用系统接口进行内存分配，而是自带一个很大的数组 mem 并在此基础上进行伪・动态内存分配（如此说来，当今 OIer 颇有 Knuth 之遗风）。TeX 内存分配的基本单位是 4 字节的 memory_word。memory_word 可以视作一个 union，有 6 种打开方式，具体如下（命名较原文有所更改）：

union memory_word { // 假设没有 memory alignment padding
    int32_t int_; 
    scaled sc;
    glue_ratio gr;
    // h: halfword, q: quarterword
    struct { int16_t lh; int16_t rh; } hh;
    struct { int8_t b0; int8_t b1; int16_t rh; } qqh;
    struct { int8_t b0; int8_t b1; int8_t b2; int8_t b3; } qqqq;
};

mem 的大小小于 \(2^{16}\)，因此 TeX 中的指针是一个 16 位无符号整数。

typedef uint16_t pointer;

mem 分为上下两部分。高地址区向下拓展，存储单 word 的数据结构；低地址区向上拓展（且通常一次拓展 1000 words），存储至少两 word 的数据结构。二者的边界分别由全局变量 hi_mem_min 和 lo_mem_max 标记。如果两者重叠则宣告内存饱和。

高地址区的维护基于单向链表。每个未分配的 word 都有一半用于存储下一个未分配 word 的地址：

#define info(p) mem[p].hh.lh
#define link(p) mem[p].hh.lh

全局变量 avail 始终指向链表头。因此，avail，link(avail)，link(link(avail)) 等就表示了所有待分配的地址。在分配时从头弹出，在释放时也从头插入，若内存不够则 avail = --hi_mem_min。

低地址区的维护基于双向链表，就是比较标准的做法了，TAOCP 里有写，在此不赘述（原文：TTP124）。有意思的一点是维护低地址区时不会维护已分配数据结构的大小，后者是释放函数 free_node(ptr, size) 的参数。

TeX 的奇妙数据结构

众所周知，TeX 中的一切最后都会变成 box（成盒）。TeX 在程序中使用一对 type tag 的组合来区分不同类型的 box。

#define type(x) mem[x].qqh.b0
#define subtype(x) mem[x].qqh.b1

这些信息已经占去了半个 word 的空间。注意到一个 box 在任意时刻只会在一个 list 当中（Rust ownership mechanism 并感），于是 Knuth 机制地利用另外半个 word 存储一个 box 的后继，即 link(x) 表示在处理 box x 之后下一个 box 的地址。不得不说，链表真的在 TeX 中被玩出了花。

因此，每个 box 的第一个字节都是它的 “元信息”—— 那么这么说每个 box 至少都占用两 word 吗？

也并不是，Knuth 考虑了 TeX 中最最常见的一种 box—— 由单个字符表示的 char box。Knuth 发现如果用 type(x) 表示一个 char box 的字体编号，再用 subtype(x) 表示它对应的字符，那么一个 char box 就能塞进一个 word 里面！

#define font type
#define character subtype

既然 type 已经被挪作他用了，如何知道一个 box 是 char box 还是其他类型呢？注意到 char box 一定被分配到高地址区，其他更复杂的 box 都在低地址区，于是只要判断指针是不是 >= hi_mem_min 就行了。

不得不说，TeX 在内存的使用上面堪称锱铢必较。按照一个字段的取值范围选择最小适用的数据类型固然能让数据结构更紧凑，但是也限制了拓展的可能性。例如，如果指针类型只有 2 字节，那如果哪一天 TeX 的需要管理超过 65536 个内存单元时应当如何？这就是 TeX 源代码的时代局限性。

对于一个 hbox/vbox，TeX 定义如下：

struct hbox_node { // sizeof(hbox_node) == 7;
    memory_word meta; // type tag = 0
    scaled width;
    scaled depth;
    scaled height;
    scaled shift_amount; // 对于 hbox 是下沉，对于 vbox 是右移
    uint8_t glue_sign; // box 内所有 glue 的伸缩状态
    uint8_t glue_order; // box 内 glue 的阶数 —— 和 fil, fill, filll 有关，暂时看不明白
    pointer list; // box 内的内容
    glue_ratio glue_set; // box 内所有 glue 的伸缩比
};
enum { // glue_sign 的取值
    NORMAL = 0,
    STRETCHING = 1,
    SHRINKING = 2,
}; 

还有一个 box 的类型和 hbox 和 vbox 很相似，称为 unset box，即 halign 或 valign 环境中大小未定，但是一定会和其他 box 对齐的 box（详见 TTP159）。

除了 char box 以及上面的 hbox/vbox，TeX 还有很多种类型的 box，但数据结构布局的基本思想大同小异，在此也不赘述了（详见 TTP140 左右）。最后记录一下 glue box。为了节约内存，TeX 的 glue box 本质上是一个引用计数的指针，指向一个单独分配的 glue specification。

struct glue_node { // sizeof(glue_node) == 2;
    memory_word meta; // type tag = 10, subtype 有点意思，详见 TTP149
    pointer glue_ptr; // 指向 glue specification
    pointer leader_ptr; // 如果这个 glue 是一个 leader，指向 leader 的内容
};
struct glue_spec { // sizeof(glue_spec) == 4;
    uint8_t stretch_order; // stretch 的阶数
    uint8_t shrink_order;
    uint16_t ref_count; // 引用计数
    scaled width;
    scaled stretch;
    scaled shrink;
};
enum { // xxx_order 的取值
    // NORMAL = 0, 在上面已经定义过了
    FIL = 1,
    FILL = 2,
    FILLL = 3,
}

这是 TeX 中第一次出现引用计数。在后面，引用计数还会一次又一次地出现。

TeX 的奇妙 command code

TeX 给每一类 primitive 固定了一个 command code。具体不详细展开了，详见 TTP207。

我个人认为给每一个 primitive 集中地，显式地指定一个整数的 command code 是不利于系统的可拓展性的 —— 即使 primitive 内部使用整数 command code 进行比较与匹配，command code 的分配也应该由程序完成。我说这话自然有站着说话不腰疼之嫌。这些 command code 孤立着看怎么样不好说，容我看完后续章节之后再来回顾。

TeX 的奇妙模式嵌套

The TeXbook 有提到，TeX 总共有六个模式：(restricted) horizontal，(internal) vertical，和 (inline) math。在程序中，这六个模式对应六个整数常量。horizontal，vertical 和 display math 对应的常量为正，对应的 restricted mode 的常量为前者的相反数 —— 如此一来通过取绝对值就能判断一个模式的基本类型。 而且三个 mode code 不是简单的 1，2，3，而是间隔 max_command（即上节 command code 的最大值）。如此一来，mode code 与 command code 之和就将模式和 primitive 的二元组一一映射到不同的整数。这在 TeX 的 “big switch” 中有大用。

任何一个时刻 TeX 的运行状态都是若干个这样模式的嵌套。这种嵌套在程序中自然通过栈来维护，栈中存储如下数据结构：

struct list_state_record {
    int16_t mode; // 不确定是不是 int16_t，原文中的 Pascal 有通过数据范围指定类型的方式，C 没有
    pointer head; // 指向该模式正在构建的 list 的链表头
    pointer tail; // 指向该模式正在构建的 list 的链表尾
    int prev_graf; // 对应 \prefgraf，即已经当前段落断行完毕的行数
    int mode_line; // 当前 mode 的起始行数
    memory_word aux; // 辅助信息
};

TeX 的奇妙字典 ——eqtb

我们终于迎来了一个在 TeX 中具有核心意义的巨大数据结构 ——eqtb 表。eqtb 是 equivalent table 的简写，存储了每一个符号（包括 control sequence，token register，counter 等）的含义。eqtb 是一个分为六部分的巨大数组，每个部分占据连续的一段下标区间，从小到大分别为：

1. 字符宏（active character，即 cat code 13）的定义；
2. 多字符控制序列（control sequence）的定义（基础是一个哈希表）；
3. Glue 的定义，例如 \baselineskip；
4. 局部变量，包括 catcode，box register，字体等；
5. 数字参数，例如断行负权（hyphenation penalty）；
6. 大小（dimension），例如 hsize。

数组的每一个元素是一个 memory_word。重定义如下

struct equivalent { // 布局等同于 memory_word
    int8_t type; // 定义类型 —— 是一个宏？一个 primitive？一个 counter？一个 token list？
    int8_t level; // 被定义时 TeX 的局部域的嵌套级数，基于以下常数：
    // level_zero 是未定义，level_one 是全局，level_one + 1 是全局一下一个 group 内，以此类推
    int16_t equiv; // 定义，可以是一个指针，也可以表示一个字体编号，取决于 type
}

其中 equiv 和 type 的意义都不难理解，但是 level 字段却出乎我的意料。按照当下的套路，如果需要存储或解析一个符号在多重嵌套作用域中的绑定，常见的方法是存一个帧栈并在解析符号时自顶向下查找。虽然这种思路很符合直觉，其弊端是需要在栈中为每一个作用域存储一个符号表。这在一切数据结构都要造轮子的时代显然增加了代码的复杂性。TeX 的 level 字段则更像是把这些表拍扁成一块，在一定程度上节约了内存。但是现在想来，这样的设计无法独立存储或引用一个局部作用域 —— 这对于 lexical scoping 是必须的。TeX 的 dynamic scoping 究竟是喂屎还是特性一直有争论，在语言设计层面也有很多种解释。现在看来，除了语言设计的考量，内部的代码实现也不由得 TeX 不搞 dynamic scoping。

哦对了，还有一点需要注意的是，eqtb 最后两个区域数据本身就占用 4 字节，这就把 type 和 level 的空间挤掉了。type 对于整数或者 glue 确实是不需要的，但是 level 得找个办法保留。TeX 的解决方案是对于后两个区额外开辟一个辅助数组 xeq_level，下标范围对应 eqtb 后两区，专门用于存储 level。

TTP 原文中 eqtb 一章有足足 20 多页长，覆盖了 TeX 的每一个内部参数（因为这些参数都要在这里集中 register），细节很多也很杂。如果要概览 TeX 所有的 primitive 类型或者所有的内部 glue 以及内部参数，这一章会是一个不错的切入点。

TeX 的奇妙哈希表

eqtb 是一个数组，其下标是一个一定范围内的整数；控制序列是一个字符串。将字符串映射到控制一个整数区间，自然要用到哈希表。TeX 的哈希表实现基于 TAOCP 的 “coalescing list” 算法，定义如下辅助数据结构：

struct {
    uint16_t text; // 指向字符串的编号，如果该位置未存值则为 0
    uint16_t next; // 指向链表的下一个 entry，如果该位置未存值或位于链表尾则为 0
} hash[/* 下标从 hash_base 到 undefined_control_sequence - 1,
    对应 eqtb 第 2 区的下标区间 */];
uint16_t hash_used; // 一个递减的指针，hash 中所有下标不小于 hash_used 的都存了值了

把哈希表的每一个 entry 定义为一个链表是常规操作，但 coalescing list 将链表本身也嵌在哈希表中，进一步节约了内存，就非常有意思了。在这个哈希表中查找以及插入的步骤如下：

uint16_t query_or_insert(char *s, bool allow_insert) {
    uint16_t p = compute_hash(s) + hash_base;
    bool found = false;
    size_t len = strlen(s);
    while true {
        if (hash[p].text > 0 
            && length(hash[p].text) == len
            && str_eq_buf(hash[p].text, s))  // 如果找到了则直接返回
            return p;
        if (!hash[p].next) { // 链表到头了还没找到
            if (!allow_insert)
                return undefined_control_sequence;
            // 开始把 s 接在 p 后面插入哈希表
            // 先找到一个还未存值的位置存入 hash_used
            do { hash_used--; } while (!hash[hash_used].text);
            // 把 p 的后继设定为 hash_used
            hash[p].next = hash_used;
            p = hash_used;
            hash[p].text = cstr_to_texstr(s);
            return p;
        }
        p = hash[p].next;
    }
}

哈希算法比较朴素：

uint16_t compute_hash(char *s) {
    uint16_t hash = *s++;
    while (*s) {
        hash = ((hash << 1) + (*s++)) % HASH_PRIME;
    }
    return h;
}

Knuth 说根据理论分析，HASH_PRIME 应当取表大小的 85% 左右，这样每次成功查找平均只要 probe（这个比较好的翻译是什么？试查？）小于两次。Knuth 还给出了文献的链接，但是我最近比较忙没有时间看，目前暂且先相信 Knuth 的 handwaving。（我早就听说哈希表是基础数据结构中特性最不好分析的，自己最近又没什么时间，估计要等到上 6.046 的时候才能真正扎实地过一遍）。

TeX 的奇妙栈存

在上上节写到，TeX 全局就一张 eqtb 表。那它是如何实现赋值类操作的局部作用域的呢？答案是在局部域内赋值时，用一个特殊的栈 save_stack 存储原来的值。如此一来，在当前局部作用域结束的时候就可以通过出栈的方式回退赋值操作。

save_stack 定义如下：

struct {
    uint8_t type; 
    uint8_t level; 
    uint16_t index; 
} save_stack[...];
uint16_t save_ptr; // save_stack [save_ptr - 1] 是栈顶
enum { // type 的取值
    RESTORE_OLD_VALUE,
    RESTORE_ZERO,
    INSERT_TOKEN,
    LEVEL_BOUNDARY,
}

可以看到 save_stack 当中有 4 种可能的元素类型：

1. RESTORE_OLD_VALUE 适用于内部作用域赋值覆盖外部已定义对象的情况。此时被覆盖的对象对应的 eqtb 下标为 index，且在出栈回退时，该元素底下的一个元素应当视作被覆盖的原值 —— 注意到，eqtb 和 save_stack 的元素的内存布局都与 memory_word 相同，因此就有往栈里存 eqtb 的东西的奇怪操作。
2. RESTORE_ZERO 适用于内部作用域赋值外部未定义对象的情况。此时局部创建对象对应的 eqtb 下标为 index，在出栈时，eqtb[index] 应当被置为和 eqtb[undefined_control_sequence] 一样的内容（说人话就是回归未定义的状态）。
3. INSERT_TOKEN 用于在 grouping 结束之后追加 token 的情况 —— 即 \aftergroup。此时 index 表示要追加的 token（虽然还没有写到，但 TeX 用一个 16 位整数编码一个 token）。
4. LEVEL_BOUNDARY 顾名思义，用于标记每一个 level 的 “边界”。注意到在一个作用域里面会往 save_stack 里面塞东西的数量是不确定的。如何在回退的时候只回退刚刚退出的那个作用域对应的修改呢？这就是这个 type 的用途。LEVEL_BOUNDARY 在进入一个作用域的时候第一个入栈，并在离开作用域逐个出栈的过程中作为终止的标记。换而言之 LEVEL_BOUNDARY 之上的就是当前作用域的所有修改。LEVEL_BOUNDARY 元素的 level 字段标记上一层作用域的 “类型”，next 字段指向上一层作用域的 LEVEL_BOUNDARY 在栈中的下标。

什么是作用域类型呢？除了最简单的靠 {..} 创造作用域以外，能够创建作用域的语法构造有很多，如 \hbox、\begingroup\endgroup 等。不同类型的作用域终止条件不同，退出之后需要额外进行的操作也不同，因此需要记忆。TeX 使用 cur_group 这一全局变量维护当前作用域的 group code，上面几层的 group code 正如上面所说的那样以类链表的形式存在 save_stack 的 LEVEL_BOUNDARY 节点里面。

骚操作又来了，如果创造作用域的命令有参数，那该参数也会入栈并处于新作用域对应 LEVEL_BOUNDARY 的底部。一个例子是 \hbox to 100px { ... } 那这个 100px 就会先于 LEVEL_BOUNDARY 入栈。这样在出栈回退过后这个保存了的参数马上就能用。Knuth 不要什么都往栈里放啊喂。

还要注意的是，用 \global 修饰的全局赋值不需要回退。因此，在试图回退的时候需要检查此时 eqtb 里面对应项的 level。如果是 level_one，那么说明最近的一次赋值是全局的，要放弃回退。

除此以外，因为 TeX 内部有很多引用计数的结构，如 token list，glue specification，par shape 等。这些数据结构在赋值的时候和回退的时候需要额外处理，旧的值该回收的要回收，这让 save_stack 上面的操作逻辑稍微复杂了一点。

TeX 的奇妙 token list

Token list 是 TeX 的另一大核心数据结构。而在解释 token list 之前，自然要先了解 TeX 是如何表示一个 token 的。TeX 将 token 分为两类：

1. “字符型” 的 token 是 catcode 和单个字符的组合。TeX 将其表示为 \(2^8 \cdot\text{catcode}+\text{char code}\)。
2. 控制序列的 token 本质上对应 eqtb 表中的一个位置。TeX 将对应 eqtb 下标 \(p\) 的控制序列表示为 \(\left(2^{12}-1\right) + p\) —— \(\left(2^{12} - 1\right)\) 也被称为 cs_token_flag。

如此一来，每个 token 都可以映射为一个 16 位的正整数。接下来自然是 TeX 的常规操作：把 token 塞到一个 memory word 中，空出来的 16 位正好指向下一个 token 的地址。因此，token list 的本质还是一个单向链表。

除了来自源文件的 token，TeX 还有两个特殊的 token：match 和 end_match。这两个在存储宏定义的时候会用到。具体来说，TeX 很神奇地将宏的参数格式和替换宏体存在一个 token list 里面。end_match 是参数部分和宏体的分界，而 match 则代表宏参数格式中的参数本身（因为参数格式中参数的编号总是递增的，所以只需要存储 match 而不需要存储对应的参数编号）—— 是不是很绕？举个例子，如果定义如下的宏：

\def\mac a#1#2 \b {#1\−a ##1#2 #2}

那么 TeX 会为这个宏创建以下的 token list：

[letter('a'), match, match, spacer, ctrl("b"), end_match, // end_match 前面的是参数格式
 out_param(1), ctrl("-"), letter('a'), spacer, mac_param, 
 out_param(2), spacer, out_param(2)]

TeX 的奇妙输入状态栈

好嘞，final week 一过，继续更新。

从这一章开始，TTP 开始介绍 TeX 的输入例程。所谓 “输入例程（input routine）”，即 TeX 从文件中读取字符，再从字符转化为 token 的过程，其逻辑起始于基本的文件操作，汇聚并终结于 get_next 这一函数，被 Knuth 形象地称为 TeX 的眼睛或嘴巴。

介绍一个算法，变量或状态是一个自然的切入点：任意时刻 TeX 输入例程的状态是由哪些变量决定的呢？

简单地想象一下，不难想到 TeX 应该有一个文件指针，存储系统的文件句柄；有一个读取位置的指针，指向当前读取的字符；有一个变量，记录 scanner 当前的状态…… 这个思路总体是不错的，如果仅仅是如此，Knuth 大可不必专门开辟一章。

输入状态的复杂性来源于 \input 这一特殊的内部命令。当 TeX 读到 \input，它就必须暂存和当前文件相关的所有输入状态、打开新的文件、然后从头开始；当这一新文件读取完毕，TeX 又需要恢复到读取 \input 时的状态来继续读取上级文件后面的内容。套娃的里面可以有更多的套娃，\input 的文件里可以含有更多的 \input。这个需求显然指向了一个数据结构 —— 栈。确实，TeX 内部的 input_stack 就是用来存储一级级打开的文件的状态（Knuth 称之为 “input state”）的。 一个文件的 input state 包括以下 6 个字段：

struct input_state {
    uint8_t scanner_state;
    uint16_t name;
    uint16_t start;
    uint16_t limit;
    uint16_t loc;
    uint8_t index;
}

1. scanner_state 顾名思义，保存了当时 scanner 的状态，有 new_line，mid_line 和 skip_blanks 三种可能。关于 scanner 的状态和具体的转移逻辑可以参考 TeX By Topic 的第 2 章。
2. name 是一个指向 str_pool 中字符串的指针 /id，表示文件名。如果是从终端输入，则该字段为 0。
3. start 表示文件的当前行在 buffer 中的起始位置。什么是 buffer？TeX 是按行读取文件的，读取的一行都会暂时缓存在 buffer 这个全局字符数组里。buffer 里面可以同时包含来自多个文件的好几行，因此需要 start 字段进行区分。（考虑以下情形：文件 A 的某一行是... \input B.tex ...，TeX 将其缓存在 buffer 的下标 0 到 \(a\) 处；然后 TeX 在处理这一行的时候发现要打开文件 B，那就可以把 B 的第一行存在 buffer 下标 \(a+1\) 往后的位置。这样一来，在 B 文件读取完毕 TeX 回到文件 A 的时候原来的行缓存还在）
4. limit 表示文件的当前行在 buffer 中的结束位置。
5. loc 表示下一个字符在 buffer 中的下标。
6. index 记录在 buffer 中，该 input state 对应的文件的当前行下还压了多少行（回到上面的例子，对应文件 B 的每一行下都压着文件 A 的那一行）。

这些字段 Knuth 在原文中花了很多篇幅去解释，我想了想可能还是画图更为直观，不妨考虑如下情形：用户在终端内输入了 \input A，然后文件 A 里面某一行包含了 \input B，图中所示即 TeX 在读取 B 内容的时候 input_stack 的情况。

但是事情远没有那么简单。因为对于 TeX 来说，下一个 token 既可以来自文件，也可以来自一个 token list。Input stack 需要把两种情况都考虑到，而我们上面只介绍了一种。Knuth 发挥了那个资源受限年代程序员的传统艺能 —— 复用结构体。事实上我对上面六个字段的解释是不全面的：scanner_state 并不是只有三个取值，它还可以取到一个隐藏值 token_list。如果一个 input state 的 scanner_state 是 token_list，那么就说明这个 input state 表示一个来自 token list 的输入而非文件输入。此时，start 字段指向 token list 的起始节点；name 变成了正在展开的控制序列在 eqtb 中的位置；index 字段被重命名为 token_type，表示当前 token list 的类型（是表示一个宏的参数，还是一个宏的主体，还是 \everypar，还是来自一个 token list 寄存器……）；假如这个 token list 是一个宏的展开，limit 字段被重命名为 param_start，指向 param_stack 当中当前宏参数列表的起始位置。

最后的最后，这里需要展开讲讲 TeX 的 \outer 机制。\outer 修饰的宏不能出现在其他宏的参数中（即只能在最外层直接调用）。显式声明 \outer 的目的是让 TeX 在括号错配中不断 look ahead 的过程中有一个明确的停止点，使得错误恢复的过程更加稳健。正如 Knuth 所说，outer macros 本质上把一个文件分成了若干个相对对立的 sub-files。现在来看，\outer 是一个十足的鸡肋，TeX Stack Exchange 上有人直言 Knuth 就不应该整出 \outer 这个玩意，而且放眼 LaTeX 也几乎没有人使用 \outer。但是和 \outer 有关的代码却是四处可见，不可不谈的。TeX 定义了一个全局变量称为 scannner_status，记录某一时刻 TeX 输入例程的状态，这个状态和之前的 scanner_state 不一样，后者可以看作是更偏围观的，前者更加宏观：

enum {
    NORMAL, // 默认状态
    SKIPPING, // 类似 \iffalse ...<这里的状态>... \fi
    DEFINING, // 类似 \def\foo <这里的状态>{... < 或这里的状态>... }
    MATCHING, // 类似 \foo {<这里的状态>}
    ALIGNING, // 类似 \halign {<这里的状态>}
    ABSORBING // 类似 \iftrue ... <这里的状态> ... \fi
} scanner_state;

显然，在遇到一个 outer macro 的时候，只有 NORMAL 和 SKIPPING 状态是正常的；在文件尾，合理的状态只有 NORMAL。其他状态多多少少都说明前面有一个大括号错配了，因此 TeX 会调用 runaway 函数进行报错（我们非常熟悉的 “runaway arguments …” 错误就是 runaway 函数输出的）。

这一部分的逻辑非常复杂，我觉得没看过原文的读者读我上面的概述还是免不了一头雾水。我已经尽力而为，希望进一步搞清楚的读者只能去看原文了。这里推荐 TTP 311 关于 show_context 的代码。TeX 的代码的一个优点就是有很多这种调试用的过程可以把复杂变量代表的状态 pretty print 出来，因此通过看这些过程的代码，对照 print 的内容，对于这些变量的意义就能有一个大致的了解。

TeX 的奇妙 get_next

正如前文所言，get_next 是 TeX 输入例程的核心，这个函数是如此重要，其逻辑又是如此复杂，以至于 Knuth 为其专辟一章。get_next 没有任何参数也不返回任何值，而是通过修改以下三个全局变量来将结果传递给调用方（非常有历史感的作法！）：

1. cur_chr 存储当前单字符 token 的字符编码或者当前控制序列（包括 active character）在 eqtb 中的 equiv 字段。
2. cur_cmd 存储当前单字符 token 的 catcode 或者当前控制序列（包括 active character）在 eqtb 中的 type 字段。
3. cur_cs 存储当前控制序列在 eqtb 中的下标，如果当前 token 不是控制序列则值为 0。

get_next 的复杂之处还体现在它是根据上一节的 input state 来决定读取的行为，即它既从能文件中读取 token，也能从 token list 中读取下一个 token。从文件中读 token 自然涉及到一个 tokenization 的过程，TeX tokenization 的状态机的代码就在此处。从 token list 中读取 token 的过程中需要特判 \noexpand—— 作为一个很特殊的 primitive，\noexpand 的实现也在这里。

除此以外，TeX 还有一个全局变量 cur_tok。按照上文一节 token list 的编码方式，这一个变量就可以表示一个 token（也可以看作是 cur_chr 和 cur_cmd 的合体）。cur_tok 主要与 back_input 函数连用。后者通过在 input stack 最顶端插入一个只包含 cur_tok 的 token list 来把 cur_tok 表示的 token “放回” 输入流中（换而言之，下一次 get_next 就会返回该 token）—— 这一用法在错误恢复过程中非常多见。

get_next 只会设置上面三个全局变量而不会设置 cur_tok。为了在调用 get_next 的同时顺便设置 cur_tok，Knuth 定义了一个 get_token 函数作为 get_next 的简单封装：

void get_token(void) {
    no_new_control_sequence = false; // TeX 默认不允许在 tokenization 的过程中新定义控制序列
    get_next();
    no_new_control_sequence = true;
    // 按照上文 token list 一节提到的规则将 cur_cs、cur_chr、cur_cmd 三个变量整合成 cur_tok
    cur_tok = cur_cs ? cs_token_flag + cur_cs : (cur_cmd << 8) | cur_chr;
}

TeX 的奇妙 expand

接下来介绍的是 TeX 的展开 token 的过程。这个过程主要通过 expand 函数实现。expand 会将 input stream 中的第一个 token（即调用 get_next 得到的 token）进行一次展开，并把展开的结果放回到 input stream 里面，从而使下一次对 get_next 的调用返回展开后的第一个 token。对于 TeX 而言，可以展开的 token 大致可以分为三大类：

1. 第一类是宏。此时 expand 会调用 macro_call 按照我们熟知的规则进行宏展开。
2. 第二类是非宏但可展开的 primitive，细分如下：

   1. \...mark—— 用于插入标记（这个命令比较冷门，一般要和 output routine 的代码合用，但是现在基本没有人手写 output routine……）
   2. \expandafter—— 用于展开顺序的调整。
   3. \noexpand—— 用于抑制展开。
   4. \csname...\endcsname—— 用于动态构建复杂的控制序列。
   5. \input—— 展开的效果就是在 input stack 上面入栈一个新文件。
   6. \if 等条件语句 —— 此时 expand 调用 conditionals，具体内容在后续章节。
   7. \fi 或者 \else—— 见后续章节。
   8. \the ...—— 此时 expand 调用 ins_the_toks，具体内容在后续章节。
   9. “conversion primitives”—— 我目前也不是很明白，expand 此时调用 conv_toks，具体内容在后续章节。
3. \halign 或者 \valign 中单元格格式模板部分的结束 ——TeX 称之为 endv（可能的原因是在 The TeXbook 中有提到，TeX 内部把模板#以前的部分称为 u，以后的部分称为 v，因此 endv 就是整个模板结束的意思）

将 expand 和 get_next 结合起来，就是 TeX 中的 get_x_token 函数，这个函数会不断地展开 input stream 中的第一个 token 直至不能展开为止（expand 只是展开一次）。

void get_x_token(void) {
    // Knuth 主张合理地使用 goto 有益无害，所以各种 label 和 goto 也成了 TeX 中一常见的风景了。
    while (1) {
        get_next();
        // cur_cmd <= max_command 就是指当前 token 不是一个控制序列。
        // 靠巧妙地定义常数值从而可以通过数值大小比较判断大类关系，这是 Knuth 的传统艺能，不能不品尝。
        if (cur_cmd <= max_command) break;
        // 上面 “非宏但是可展开的 primitive” 对应的 cur_cmd 介于 max_command 和 call 之间。
        // 因此 cur_cmd >= call 对应宏和模板结束的情况。
        if (cur_cmd >= call) {
            if (cur_cmd < end_template) macro_call();
            else {
                cur_cs = frozen_endv;
                cur_cmd = endv;
                break;
            }
        } else expand();
        // expand 其实已经包含了上面 if 中的两种情况。Knuth 把上面两个分支单独摘出来是因为这样可以
        // 省下一次函数跳转的开销，程序就能更快。人工内联函数与人脑分支预测也是 TeX 的传统艺能。
        // 换而言之，上面这个大 if 其实就等同于一句 expand ();
    }
    // 同 get_token。
    cur_tok = cur_cs ? cs_token_flag + cur_cs : (cur_cmd << 8) | cur_chr;
}

未完待续

这篇笔记的成文比我预想得艰难得多，甚至较阅读 Knuth 的代码本身更有挑战性。难点恰恰在于语言。我可以很爽快地断言，如果我一开始决定用英文写这篇文章，这篇文章的难度至少能够降低 70%。我以前对于国内学术书籍的翻译一直是颇有微词的，读来总觉得狗屁不通，还不如直接读原文爽快。直到尝试着写这篇笔记，方才知道自己以往是站着说话不腰疼。我每次写完一段一节都会重读数遍，很多时候无论怎么修改一种别扭感总是挥之不去，让人十分沮丧，至此方知学术翻译之艰难。我不相信英语作为技术文档的一种载体有其独到的优点，但也我不得不承认，在第一印象是英语的情况下，将专有名词直译成母语后反而变得更加拗口而陌生了。很多第一眼觉得很直觉很好翻的英语表达方式，真的翻译起来也会发现直译不通顺而需要绞尽脑汁地意译。我曾经觉得对于中国人，用中文写的文章一定比英文文章要好读。写这篇笔记的煎熬让我对这一论点产生了一定的动摇 —— 语言终究只是表意的工具，大约我之前的确有点偏激吧。