TeX源代码阅读笔记

最近我因为个人项目的原因开始深入了解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字节，以为最小单位。换而言之，如果直接把定点数当int32_t读，得到的是其所表示值的倍。除此以外，当时各个平台对于对负数的整除和取模运算的实现存在分歧，因此TeX除了几处非核心算法，其余的部分在整除和取模前都检查操作数的正负性。

TeX的定点数计算函数里有很多令人啧啧称奇的操作。例如，以下函数用于近似计算（以下注释是我补的，原文没有解释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长度的最小单位是 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的大小小于，因此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. 控制序列的token本质上对应eqtb表中的一个位置。TeX将对应eqtb下标的控制序列表示为——也被称为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而不需要存储对应的参数编号）——是不是很绕？举个例子，如果定义如下的宏：

```tex \defa#1#2