Ramsay Leung修改

2025-06-01 02:00:00

1 前言

前天刚写完《软件设计的哲学》，满脑子还萦绕着模块耦合和接口抽象， 结果昨天就撞上一个现实中的“设计陷阱”——一次耗时数小时却无解的「退货」噩梦。

今天趁着周末，决定把这场荒诞遭遇拆解出来，既当吐槽，也当案例分析.

2 来龙去脉

前段时间搬了家，自然就需要重新办理宽带，一直用的是 Telus 家的家庭宽带服务，他们家的宽带服务也支持从一个住址迁移到另外一个住址, 就预约了 Telus 技术人员上门安装。

技术人员上门安装完宽带之后，就需要测试一下 WI-FI 能否正常使用，就问我们的路由器在哪，他接上处理一下。

问题就来了：

我们的路由器之前是舍友设置的，还不是常见的一体路由器，而是分体式路由器，有三个不同的组件。

而舍友在搬完家后就回国休假了，我还真不知道怎么搞这路由器，各个接口尝试了小半个小时也没反应，师傅也没见识过，自然也不晓得弄。

这个又是一个非常经典的软件开发问题：

「在我的机器上能跑，换个环境就挂了」

但是一直没网也不是办法，然后师傅建议我可以把他随身带的 Telus 路由器买下来，等我舍友回来后把网络设置好，再把路由器还回来，Telus支持30天无理由退货。

听起来也只能这么搞了。

舍友休了几周假回来之后，几分钟不到，很快就把这个路由器就设置起来了:

剩下的就是把路由器还给 Telus, 已经过了几周，30天的免责退货时间所剩不多了。

3 退货流程

因为设备不是通过网购买的，没法直接在网上退单，也不是门店买的，无法直接拿去门店退，退货的流程是打电话给 Telus 的客服，问他们要退货指引。

我就给 Telus 的客服打电话，解释清楚情况后，客服说给我账户对应的邮箱发个邮件，里面有指引和退货码，我需要去 Canada Post（加拿大邮政）把路由器寄回去。

电话里客服说已经给我发邮件了，但是我说没有收到（此处为后面埋下伏笔），于是我提供另外一个邮箱，成功收到了。

因为 Canada Post 最近在为涨薪闹罢工，客服提到我需要去另外一家快递公司 Purolator 寄快递。

剩下要做就是把路由器打包，然后寄出来(这么容易就好了), 再把快递单号告知 Telus, 退货流程就算结束了。

4 坑来了

4.1 邮政罢工

因为加拿大邮政罢工，所以只能去 Purolator 寄，但是去到 Purolator后，人家反馈:

你这个退货码是给加拿大邮政的，我们不认哦，你要给个我们家的退货码。

我只能去再打电话给 Telus 客服要退货码，花费了15分钟，终于打通了，解释完一番之后，他们说给我的邮箱发了新的 Puralator 退货码，我等了一分钟，说没有收到，然后让给我另外的一个邮箱也发一次指引，还是没有收到，然后客服说邮件会在24-48小时内到达..

但挂电话后再等了一个小时还是没有收到.

4.2 邮箱收不到email

只能再打电话给 Telus 的客服，又等了10几分钟终于接通了，这次换了个客服，这位客服说我们不支持 Purolator，你可以等加拿大邮政罢工结束之后再寄。

我也很无语，怎么你们的回复还不一致的，就和客服说，我怎么知道罢工什么时候结束呢，30天马上就要到了嘛。

客服说，的确很有道理，这样吧，你可以去尝试使用用加拿大邮政寄下，然后我把情况记录一下，到时超过30天也可以免责退款。

然后我追问到，那罢工结束时退货也是用相同的退货码么？这个退货码有过期时间么？邮件没写哦。

客服说，那以防万一，我再给你邮箱发个新的退货码吧。

我着实是怕了，不知道为什么一直没有收到邮件，就让客服把我账号对应的邮箱地址读出来, 客服就把我邮箱的逐个地址读出来。

前面部分听着没问题嘛，我还在寻思是什么问题，只是听着听着，怎么我邮箱还有我不认识的部分，就打开 Telus 的APP 修改, 然后被气得差点要吐血了:

我的邮箱地址是 [email protected], 然后为了标记不同的公司，我用了《两个鲜为人知的Gmail地址技巧》 提到的加号技巧来注册 Telus 账号:

[email protected]

之前用了一年多还是好好的，不然我也无法注册和验证邮箱成功。

但是现在 Telus 作了变更，直接把邮箱地址中的加号去掉了，变成了 [email protected], 变成一个完全不同的邮箱, 肯定是不可能收到邮件的。

花费了近一下午，打了5-6次电话，和不同的客服沟通和练习口语，最后的结果就是隔天再去加拿大邮政试试，不行就等他们罢工结束再寄。

5 糟糕设计的代价

这次经历虽然令人沮丧，但也印证了软件工程的一条铁律：

糟糕的设计最终会让所有人付出代价——无论是用户还是开发者。

讽刺的是，人们总希望通过「学习别人的错误」来避免踩坑，但现实中，我们往往被迫为别人的设计缺陷买单。

5.1 单点故障与「Happy Path」陷阱

电话退货这个操作虽然看似落后，但是总体来说还是可以用的，在不出问题的前提下。

Telus 的退货流程设计暴露了一个典型的系统脆弱性：

强依赖单一服务提供商（Canada Post） ，且未设计降级方案（如备用物流或线下门店退货）。

这种「Happy Path Only」的思维，本质上是对分布式系统设计原则的违背：

任何外部服务都可能失败，而系统必须对此容错。

让快递直接成为业务系统的「单点」故障，只考虑 Happy Path, 没有考虑异常场景，甚至发过来的退货邮件指引，都可以看出他们是把 Canada Post 写死在邮件。

5.2 向后兼容性：一个被忽视的底线

退货强依赖加拿大邮政这个还可以说成是产品设计的问题，但是直接把我邮箱地址给改掉这个，就一定是程序员的锅了。

此外，我的邮箱地址在 APP 中显示的是 [email protected], 只有在修改邮箱地址的时候，才会显示出 [email protected] 这也是我一直没有发现的原因。

但最令人匪夷所思的是邮箱地址的非兼容性变更：系统直接静默移除了存量用户邮箱中的加号:

[email protected] -> [email protected] ，导致邮件发送失败。

这种粗暴的修改方式违反了最基本的向后兼容性原则，而问题的暴露方式（APP显示与修改界面不一致）进一步说明：

其系统内部还存在的数据状态不一致性问题

合理的变更方式应该是：

1. 增量控制：
   • 禁止新用户注册或修改时使用特殊符号，但保留存量数据, 保证增量用户地址正确
   • 存量用户修改邮箱地址时，禁止使用带特殊符号的邮箱地址
2. 存量迁移：
   • 通过离线数仓，查询出所有带特殊符号的邮箱地址，通过异步任务批量通知受影响用户（避免阻塞主流程）
   • 提供自动清理特殊符号的“一键修复”功能（需用户确认）。
3. 监控兜底：
   • 建立异常邮箱地址的监控或者报表，直到存量问题归零。

虽然这做法非常繁琐，但是却可以保证系统升级绝对不影响用户。

系统设计与维护就是如此：开始做的时候成本很低，越到后期成本越高。

6 个人感悟

除去别人的设计错误之外，我还有些额外的个人感悟:

虽然 Gmail 支持邮箱地址中增加一个 + 这样的功能，但是并不是所有的公司都支持这特性的，重要的邮件还是不能使用这个「奇技淫巧」。

此外，我另外提供的邮箱也无法收到邮件，可能是我的邮箱太长了，导致客服没有拼对我的邮箱，所以最好还是准备一个短的，包含数字的备用邮箱地址，方便电话沟通时提供给对方。

整个故事再次印证了《软件设计的哲学》中的道理：

所有偷懒的设计，终将以更高的成本偿还

当然, 谁来还就是后话了

公号同步更新，欢迎关注👻

2025-05-30 15:39:00

1 前言

知道这本书是因为在 Hacker News 上有人提问：你读过最好的技术书是什么 ¹?

最高赞的书是 Design Data Intensive Application(DDIA, 即《数据密集型应用系统设计》²), 我觉得 DDIA 也担得起这个赞誉，然后最高赞的回答顺势提到了 A Philosophy Of Software Design ³, 想来能与 DDIA 齐名的书，肯定不会差得哪里去。

作者是 John Ousterhout, 斯坦福大学的教授，TCL 编程语言的创造者(Redis 的初始化版本就是用 TCL 写的)，共识算法 Raft 的作者之一.

这本书并不厚，全书只有200多页，读起来也并不费劲。

而这本书的主旨，开篇就点出来了:

This book is about how to design software systems to minimize their complexity.

本书讲述如何设计软件系统以最小化其复杂度

而软件工程的本质就是如何管理复杂度，全书围绕如何降低软件复杂性提出的思考和解决方案， 主要围绕抽象，异常，文档，一致性，设计原则这五个方向。

许多原则我看着都深有共鸣，尤其在设计过相当多的系统之后，犯过许多错误之后，才会意识到这些原则的重要之处。

很多原则看上去说的和没说一样，但只有踩过坑，实践起来都知道是金科玉律, 除了道出「软件设计」的真谛之外, 这本书其他论点也可谓字字珠玑.

关于谨慎暴露过多的配置给用户，尽量让程序动态计算各种参数值，尽量提供默认参数。

开发软件时，开发者主动承担一些额外痛苦，从而减少用户的痛苦。

When developing a module, look for opportunities to take a little bit of extra suffering upon yourself in order to reduce the suffering of your users.

关于接口设计的原则:

模块拥有简单的接口比简单的实现更重要。

it’s more important for a module to have simple interface than a simple implementation

关于异常处理的洞见:

解决问题的最好方式是避免出现问题。

The best way to eliminate exception handling complexity is to define your APIs so that there are no exceptions to handle: define errors out of existence

归根结底，减少 Bug 的最佳方法是让软件更简单(少即是多)

Overall, the best way to reduce bugs is to make software simpler.

2 抽象

所谓的抽象，用我自己的话来说的就是把复杂的东西简单地呈现出来。

2.1 模块深度

为了直观地感受一个模块设计是否足够抽象，作者提出一个模块深度的概念:

矩形的表层长度即是接口的复杂程度，而矩形的面积代表模块实现的功能，好的模块应该是深的(deep), 这意味着它有简单的接口，但是内部有复杂且丰富的实现.

例如 Unix 的文件读写接口:

1
2
3
4
5
6
7
8
9

int open(const char* path, int flags, mode_t permissions);

ssize_t read(int fd, void* buffer, size_t count);

ssize_t write(int fd, const void* buffer, size_t count);

off_t lseek(int fd, off_t offset, int referencePosition);

int close(int fd);

接口非常简单，但是其内部的实现可能需要成千上万行的代码， 需要支持文件目录的读写，文件权限，读写缓冲区，磁盘读写等等功能，这就是「深的」模块。

与其相反的就是浅的模块(shallow), 接口很复杂，但是功能却很简单。

2.2 信息的漏与藏

实现抽象的关键手段就是辨别出信息的重要程度，对于不重要的信息，就要对用户隐藏起来，关键的信息，就要暴露给用户, 实现「去粗存精，开箱即用」。

一个典型的例子就是参数配置，把参数暴露给用户，除非用户非常熟悉这个系统，不然他也不知道怎么算， 不需要用户关注的参数就提供默认值，能程序动态计算就由程序自己来算.

我很反感的一种设计就是引入一个配置系统，系统的运行参数都要由工程师配置，美其名是提供灵活度。

但这不仅引入额外的系统依赖（须知复杂度的根源就来自依赖与不明确），还大大增加了的运维成本， 更何况这样的配置还无法自适应，换种机型又要重新配置，导致配置越来越复杂。

除非是业务的黑名单或者白名单，系统的运行参数能用默认的就用默认，能动态计算就动态计算。

想想TCP/IP 的重试延迟时长如果不是动态计算，那么配置什么值比较合适，网络畅通和网络延迟又该是什么值， 开始恢复时和开始堵塞时又应该是什么值的呢?

3 异常

异常处理是系统复杂度的关键来源之一，异常就是一种特殊的分支，系统为了处理特殊 case难免需要写很多额外的逻辑。

而作者提出的降低异常处理来系统复杂度影响的方法，就是优化设计，减少必须处理异常的地方。

解决一个问题最好的方法是避免其发生，听起来很空洞或者是很不可思议，作者举出来的例子就是 Java 的 substring(int beginIndex, int endIndex) 用于截取子字符串的接口, 如果 endIndex 超出字符长度，Java 就会抛出一个 IndexOutOfBoundException, 调用方就是需要考虑越界的问题。

但是如果 Java 的 substring 接口本身可以像 Python 那样支持越界，返回一个空字符串，那么调用方就完全不需要考虑越界导致的异常

另外一个例子是作者设计的TCL脚本中的 unset 指令，原意是用来删除一个变量，因为他最初的设想是变量如果不存在，用户不可能调用 unset 的，那么当 unset 操作的变量不存在，那么就会抛出异常。

但是很多用户就是用 unset 来清理可能被初始化或者未初始化的变量，现在的设计就意味用户还需要包一层 try/catch 才能使用 unset.

意识到这个设计错误之后，作者对 unset 的语义作了稍微的修正，用 unset 来确保指定的变量不再存在(如果变量本身不存在，那么它什么都不需要做)

更经典的例子就是 Windows 下面删除一个文件，相信使用过 Windows 的朋友尝试删除文件时都会遇到这样的弹窗：「文件已被打开，无法删除，请重试」

用户只能费尽心思去找打开这个文件的进程，然后把它杀掉再尝试删除，甚至只能通过关机重启来尝试删除文件。

但是 Unix 的处理方式就更优雅，它允许用户删除已经被其他进程打开的文件，它会对该文件做标记，让用户看来它已经被删除了，但是在打开它的进程结束前文件对应的数据都会一直存在。

只有在进程结束后，文件数据才会被删除掉，这样用户在删除文件时就不需要担心文件是否被使用。

通过优化以上的设计，减少需要用户处理的异常，这也是一个「去粗留精」的过程, 减少用户需要感知的内容。

4 注释

本书用了好几个章节来介绍文档与注释的重要性，命名的重要性，如何写好注释和起好名字。

好的文档可以大幅改善一个系统的设计，因为文档的作用就是把「对用户重要的，但是无法直接从代码中得知的关键信息告知用户」, 相当于帮用户把一个系统的关键信息给找出来。

不是有这么一句话： 程序员都讨厌写文档，但是更痛恨其他程序员不写文档。

而注释就是离源码最近的文档.

程序员不写注释的借口大概有这么几个（可惜它们都是不成立的）, 常见的借口与它们不成立的原因可见:

4.1 好的代码是自解释的

如果用户必须阅读方法源码才能使用它，那就没有抽象，你相当于把实现的所有复杂度都直接暴露给用户。

若想通过抽象隐藏复杂性，注释必不可少

4.2 我没有时间写注释

如果你一直把写代码的优先级置于写注释之上，那么你会一直没有时间写注释， 因为一个项目结束之后总会有新的项目到来，如果你一直把写注释的优先级放在代码之后，那么你永远都不会去写注释。

写注释实际并不需要那么多的时间

4.3 注释都会过期的啦

注释虽然难免会过期，但是保持与代码一致也并不会花费太多时间。

只有大幅需要修改代码时才需要更新注释，更何况，只有每次都不更新注释，注释才会难免过期

4.4 我见过的注释都很烂，我为啥还要写

别人的注释写得不好，那不正说明你可以写出好的注释嘛。

不能用别人的低标准来要求自己嘛。

4.5 注释的原则

说起接口注释和文档，我一直觉得我描述下接口功能和使用场景，已经比绝大多数的同行做得好了。

在和现在的 L7 大佬一起工作之后，着实被他的文档所震撼。

不知道是因为其对代码质量和文档都有非常高的要求，还是读博士时训练出来的写作能力， 其对接口的功能，使用场景以及异常的描述都非常详尽，甚至包括代码使用示例，质量与 JDK 源码的注释不相上下, 原来真的有程序员花这么多精力写代码注释的。

4.5.1 注释应当描述代码中不明显的内容

注释应当描述代码中不明显的内容,

简单来说，就是要描述代码为什么要这么做，而不是描述代码是怎么做的，这相当于是把代码换成注释再写一次。

4.5.2 注释先行

很多程序员都习惯在写完代码之后才写注释，作者反其道而行， 作者推荐在定义完函数或者模块接口之后，不要马上动手写实现， 而是在这个时候在接口上把接口注释写下来，这相当于是在脑海把模块的设计再过一次。

写完代码再写注释，设计思路已经记不大清了，脑中更多的是实现细节，既容易把实现写成注释，又容易陷入「写完代码就不写注释」的陷阱。

5 一致性

前文提到，系统的复杂度来自于两个方面「依赖」与「不明确」， 而「一致性」就是让系统的行为更加清晰明确。

它意味着相似的事情以相似的方式处理，不同的事情以不同的方式处理。

即所谓的「规圆矩方」，通过规范约束降低随意性，以及「一法通，万法通」，统一模式提升可维护性，让行为可预期。

一个系统的一致性一般体现在以下方面：

1. 命名(驼峰还是下划线)
2. 代码风格(缩进，空格还是tab)
3. 设计模式(使用特定的设计模式解决特定的问题)

当然，还有通过「一致性」降低系统复杂度，走得比较极端的:

之前还在微信支付的时候，除上述的要求外，还要求后端只能使用一种语言(C++, Golang/JavaScript就别想了), 存储组件只能使用微信内部研发的KV(使用MySql需要向总经理申请)等等的要求.

6 设计原则

6.1 通用设计

好的设计应该是通用的，优先采用通用设计而非特殊场景的定制化方案，这个是减少复杂度和改善软件系统的根本原则。

过度定制通常是成为软件复杂度增加的首要诱因。

通用设计可以降低系统的整体复杂度(更少处理特殊分支的逻辑), 更深的模块(接口简单，功能丰富), 隐藏非关键信息.

文中提到的例子就是文本编辑器的文字插入与删除操作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 反例：过度定制（绑定特殊场景）, 实现删除键功能
class TextEditor {
    void handleBackspaceKey() { // 耦合UI事件
        if (cursorPosition > 0) {
            text.deleteCharAt(cursorPosition - 1);
            cursorPosition--;
        }
    }
}

// 正例：通用设计（解耦核心逻辑）
class Text {
    void delete(int start, int end) { // 纯文本操作
        content.delete(start, end);
    }
}

class UI {
    void onBackspacePressed() {
        text.delete(cursor.position(), cursor.position() + 1); // 调用通用API
        cursor.moveLeft();
    }
}

通过 delete(int start, int end) 既可以实现删除键功能，也可以实现选中并删除的功能。

6.2 性能

在设计系统的时候，一般不需要太多地考虑性能的问题，因为简单，通用的系统要做性能优化通常都是比较容易； 相反而言，深度定制的系统因为耦合了定义逻辑，要优化性能并没有那么容易。

6.3 设计两次

Design it twice

因为很难一次就把事情做到极致, 那就再来一次, 设计时把能想到的选项都列下来.

反直觉的是，第一直觉通常不是最优的, 所以不要只考虑一种设计方案，无论它看起来多么合理，多对比下其他方案总没有害处的。

只用第一直觉的方案，其实你是在低估自己的潜力，你错失了找到更好方案的机会。

这也是我在写设计方案时候的做法，把自己能想到的，和同事讨论出来的所有方案都写上，然后分析各种方案的优劣, 最好的方案可能并不在原有方案列表里面，而是其中几个方案的合体。

6.4 大局观

做任何事都要有大局观, 编程也不例外，战略编程优于战术编程(Strategic Programming over Tactical Programming);

虽然我们一直说「又不是不能跑」，但是我们对代码的要求，不能是「能跑就行啦」.

再者就是要和扁鹊他大哥治病一样，把功夫都做在前期，防范于未然，修补错误成本往往也越往后越高，病入膏肓之后，扁鹊来了也要提桶跑路:

治不了，等死吧，告辞

7 代码整洁之道vs软件设计哲学

本书的作者对《代码整洁之道》(Clean Code)⁴ 的作者(Robert C. Martin, 即 Uncle Bob)的诸多观点作了反驳

7.1 函数拆分

比如关于什么时候应该拆分一个函数，Uncle Bob 的观点是，基于函数的代码行数，一个函数需要相当短，甚至10行都有太长了。

Uncle Bob 原话:

In the book Clean Code1, Robert Martin argues that functions should be broken up on length alone. He says that functions should be extremely short, and that even 10 lines is too long.

而本书作者 John 的观点是: 每个函数应只做一件事，并完整地做好

函数的接口应当简洁，这样调用者无需记住大量信息就能正确使用它。

函数应当具备深度：其接口应远比实现更简单。如果一个函数满足以上所有特性，那么它的长度通常并不重要。

除非能让整个系统更简单，否则不应拆分函数

7.2 文档注释

Uncle Bob 认为需要给函数「注释始终是一种失败(Comments are always failures)」

如果我们的编程语言足够富有表现力，或者如果我们有能力用好这些语言来传达意图，那么我们就不太需要注释——甚至可能完全不需要.

注释的正确用途，是弥补我们无法用代码清晰表达的缺陷……注释始终是一种失败

If our programming languages were expressive enough, or if we had the talent to subtly wield those languages to express our intent, we would not need comments very much — perhaps not at all.

he proper use of comments is to compensate for our failure to express ourselves in code…. Comments are always failures.

而 John 的观点是

但注释并非失败的表现。

它们提供的信息与代码截然不同，而这些信息目前无法通过代码本身来表达。

注释的作用之一，正是让人无需阅读代码即可理解其含义

甚至直接反驳其观点:

I worry that Martin’s philosophy encourages a bad attitude in programmers, where they avoid comments so as not to seem like failures.

7.3 网上对线

所以也难怪 Uncle Bob 和 John Ousterhout 几个月前直接在网上论坛来了一次 对线 (辩论) ⁵

然后有看热闹不嫌事大的播主，把两人邀请到直播上，让他们直接面对面再来了一次对线

对应的Youtube视频: https://www.youtube.com/watch?v=3Vlk6hCWBw0

两位的书我都看过，我个人的感觉是《代码整洁之道》更适合入门的工程师，它可以教你如何写出好的「代码片段」； 而《软件设计的哲学》更适合需要做系统设计的工程师，它指导你如何设计好的「软件」。

考虑到两位作者的背景和作品，我可以说两位的差别可以说是 以编程为生的人与以写编程相关的东西为生的人

8 总结

全书读完，我觉得《软件设计的哲学》绝对是配得上最好的技术书籍之一的赞誉。

但是不同的人读起来可能会有不同的感觉，其中的许多原则真的是做过设计，踩过坑才会有所共鸣, 否则会觉得其泛泛其谈。

当然，我也不是完全同意书中的所有观点的。

比如书中提到的会导致代码意图不「明显」的其中一种做法是声明的类型与初始化的类型不一致的情况:

1
2
3
4
5

private List<Message> incomingMessageList;

...

incomingMessageList = new ArrayList<Message>();

上面声明的是 List<Message>, 实际使用的 ArrayList<Message>, 这可能会误导用户，因为意图不清晰，阅读代码的人可能不确定是否需要使用 List 或者 ArrayList, 最好是声明和初始化都换成相同的类型。

但是 List 是接口, ArrayList 是接口的具体实现，这个就是非常标准的面向对象编程中的多态，这并不什么问题。

但瑕不掩瑜，全书读完，把书盖上后，我有种齿颊留香, 余音绕梁的感觉，书里有很多「熟悉的味道」，总是让我想起经手过的项目中种种的好代码和「坏」代码.

公号同步更新，欢迎关注👻

2025-04-21 09:18:00

项目 GitHub 地址: Build Manager

1 前言

以 C 语言为例，一个程序通常由多个源文件 .c 组成, 每个源文件需要先编译成目标文件 .o, 再链接成最终的可执行文件。

如果只改动了其中一个源文件的内容，理想情况只需要重新编译并重新链接改动文件，而非从头构建整个项目(所谓的增量编译)。

但是如果手动管理这些依赖关系，随着源文件的增多，很容易就会变得无法维护。

类似的问题在软件开发中比比皆是，以我们此前实现的「模板引擎」为例，如果我们正使用静态网站生成器来构建个人博客(Hugo 或者 Jekyll), 当我们修改了某篇文章时，系统只需要重新生成该页面，而不必重新编译整个网站。

但如果我们调整了调整了网站的模板，那么所有依赖该模板的页面都需要重新渲染，而手动处理这些依赖关系既繁琐又容易出错。

因此我们需要一个构建工具(build tool或者叫 build maanger).

2 需求

构建工具的核心理念就是自动化上述的操作：

1. 定义依赖关系, 比如 main.o 依赖于 main.c 和 header.h
2. 检测变更，可以通过时间戳或者内容的哈希来判断文件是否「过时」
3. 按需执行，只重新生成受影响的目标

从经典的 make, 到现代构建系统如 Bazel, 尽管它们的实现方式各异，但是基本都遵循着这一思路。

所以我们会参考 make, 从零实现一个类 make 的构建工具，核心功能包括：

1. 构建规则(rule)：描述目标(target), 依赖(dependency)和生成命令(recipe)
2. 依赖图(DAG): 避免循环依赖并确定构建顺序
3. 增量编译：仅重新生成「过期」的目标
4. 变量与通配符（如 @TARGET 和 % ） 以提高灵活性.

3 设计

3.1 构建规则

构建工具的输入是一系列的规则，每个规则必需包含三个关键要素，分别是：

1. 目标，即构建命令生成的最终结果
2. 依赖，即目标依赖于哪些文件
3. 生成命令：具体的命令，用于描述如何将依赖生成出目标。

以 make 的规则文件 Makefile 举例:

1
2

target: dependencies
    recipe

以一个 C 语言程序的构建规则为例:

1
2

hello: utils.c main.c utils.h
        gcc main.c utils.c -o hello

其中 hello 是构建目标， utils.c main.c utils.h 是多个依赖文件, gcc main.c utils.c -o hello 是生成命令.

Makefile 是 make 专属的配置文件格式，我们可以使用 JSON 或者 YAML 作为配置文件，避免重复造轮子，只要要表达列表和嵌套关系。

那么为什么 make 不使用 JSON 或者 YAML 作为配置文件呢？因为 make 被造出来的时候(1976年)，JSON 和 YAML 离诞生还有几十年呢.

3.2 依赖图

以前学数据结构的时候，难免会觉得图(graph) 这个数据结构真的没有什么用，除了刷题和面试会被问到.

但是在开发这个构建工具的时候，会发现图是必不可少的数据结构，准确来说是有向无环图(directed acyclic graph, DAG).

在构建工具中，每个构建规则（target: dependencies）定义了文件之间的依赖关系，这些关系天然形成一个有向无环图（DAG）。

例如：

• A 依赖于 B 和 C（ A → B, A → C ）
• B 依赖于 D（ B → D ）

此时，*构建顺序必须满足依赖的先后关系*：D 必须在 B 之前构建，B 和 C 必须在 A 之前构建。

而拓扑排序的作用，正是将图中的节点排序，保证每个节点在其依赖之后被执行。

而如果依赖图中存在环（例如 A → B → A），拓扑排序会失败.

拓扑排序的经典算法有 Kahn 算法(基于入度)与 DFS 算法, 以 Kahn 算法为例, 步骤如下:

1. 先初始化一个队列，存入所有入度(in degree)为0的节点（无依赖节点）
2. 依次处理队列中的节点，并将其人图中「移除」，更新后续节点的入度
3. 若最终未处理所有节点，则说明存在环

我曾经写过一篇关于拓扑排序的英文博客，有兴趣可以移步阅读.

3.3 过期检测

增量编译的关键是仅重建「过期 」的目标，那么要怎么找到「过期」的目标呢？

最简单方式就是使用时间来作为判断标准，假如我们的源文件在上一次构建之后发生了修改， 那么我们就可以认为其对应的目标「过期」了，需要重新构建。

那么我们就需要记录上一次是什么时候构建的，然后再把文件最近的修改时间(last modification timestamp)作为比较, 用额外的文件来记录也太繁琐了，为此我们可以取一下巧：

把目标的生成时间作为上一次的构建时间，那么只要依赖的 last modification timestamp 大于目标的 last modification timestamp, 那么我们就可以认为其「过期」了。

这个就是 make 的实现方式，但是时间并不是总是可靠的，尤其是在网络环境下。

所以像 bazel 这样的现代构建系统，使用的就是源文件的哈希值来作为比较的标识： 即文件内容哈希值发生了变化，那么就认为发生内容变更，目标「过期」，需要重新生成。

3.4 设计模式

上文已经提到，我们构建工具的核心功能是解析构建规则, 构建依赖图，增量编译，变量与通配符匹配，那么我们可以很容易地写出对应的实现原型:

1
2
3
4

loadConfig(): rules
buildGraph(rules): graph
variableExpand(graph)
incrementalBuild(graph)

那么要如何实现上面的原型呢？在面向对象的编程思路里，要不使用继承，或者是组合，而两者对应的设计模式分别对应模板方法(Template Method) 与 策略模式 (Strategy Pattern)

模板方法的核心思想是继承与流程固化，在父类中定义算法的整体骨架（不可变的执行流程），将某些步骤的具体实现延迟到子类，通过 继承 扩展行为。

而策略模式核心思想是组合 + 运行时替换，将算法的每个可变部分抽象为独立策略（接口），通过 组合 的方式注入到主类中。

System Design By Example 原书使用的是模板方法，其实现可谓是充分展示了继承的不足：紧耦合，新增功能需要创建新子类，导致类爆炸，各种类变量在继承链传递，真的是无法维护，最后甚至「丧心病狂」地实现了八层继承，真的是完美诠释了 Fragile base class 的 code smell.

在体现到维护与扩展 template method 代码的痛苦之后，我最终选择了策略模式，因为其可以实现不同策略之间的松耦合，每个策略可以独立修改和扩展，不影响其他组件；易于测试，每个策略可被单独测试。

此外，构建工具需求可能会很多样，比如支持不同的增量编译算法（时间戳与内容哈希），支持不同的配置格式(Makefile/JSON/YAML), 策略模式不需要改写核心代码即可支持这些变体，并且支持不同策略的组合。

为了方便对比两者实现的差别，我把 template method 和 strategy pattern 的实现都保留了。

3.5 自动变量

make 支持在 Makefile 中使用自动变量(Automatic Variables)来指代目标或者依赖，而无需显示将目标或者依赖名写出来，其变量含义如下:

假设目标是 output: main.o utils.o

这些自动变量可以极大简化 Makefile 的编写，避免重复输入文件名, 只不过 $@ 这样的格式有点难以理解，我们可以定义自己的自动变量:

4 实现

在介绍完设计细节，实现就没有太多需要提及的内容，根据入口函数以及单元测试就能理解个七七八八了。

5 示例

假设我们的 src 目录有如下的文件:

1
2
3
4
5
6

> tree src
src
├── Makefile
├── main.c
├── utils.c
└── utils.h

main.c 内容如下:

1
2
3
4
5
6

#include "utils.h"

int main() {
  print_message("Hello from Makefile!");
  return 0;
}

Makefile 的内容如下:

1
2
3
4
5
6
7
8

hello: utils.c main.c utils.h
        gcc main.c utils.c -o hello
varexpand_hello: utils.c main.c
        gcc $^ -o $@
clean:
        rm -f hello
cleanvar:
        rm -rf varexpand_hello

通过 hello 和 varexpand_hello 目标可分别生成 hello 与 varexpand_hello 的目标文件:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

> make hello
gcc main.c utils.c -o hello

> ./hello
Message: Hello from Makefile!

> make varexpand_hello
gcc utils.c main.c -o varexpand_hello

> ./varexpand_hello
Message: Hello from Makefile!

与 Makefile 相同含义的构建规则 build_c_app.yml 如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

- target: hello
  depends:
  - src/utils.c
  - src/utils.h
  - src/main.c
  recipes:
  - "gcc src/main.c src/utils.c -o hello"
- target: varexpand_hello
  depends:
  - src/utils.c
  - src/main.c
  recipes:
  - "gcc @DEPENDENCIES -o @TARGET"
- target: clean
  depends: []
  recipes:
  - "rm -rf hello"
- target: cleanvar
  depends: []
  recipes:
  - "rm -rf varexpand_hello"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

> npx tsx driver.ts build_c_app.yml # 未指定目标，构建第一个目标，对齐 make
gcc src/main.c src/utils.c -o hello

> npx tsx driver.ts build_c_app.yml hello # 生成 hello
target: hello is up to date, skipping execute the recipe

> ./hello
Message: Hello from Makefile!

> npx tsx driver.ts build_c_app.yml varexpand_hello # 生成 varexpand_hello
gcc src/utils.c src/main.c -o varexpand_hello

> ./varexpand_hello
Message: Hello from Makefile!

测试增量编译，重新构建 hello 目标

1
2

> npx tsx driver.ts build_c_app.yml hello
target: hello is up to date, skipping execute the recipe

修改 main.c 源码:

1
2
3
4
5
6

#include "utils.h"

int main() {
  print_message("Hello from build_c_app.yml!");
  return 0;
}

重新编译及运行 hello 目标:

1
2
3
4
5

> npx tsx driver.ts build_c_app.yml hello
gcc src/main.c src/utils.c -o hello

> ./hello
Message: Hello from build_c_app.yml!

6 总结

终于又造了一个轮子，完成了这个类 make 的构建工具:

除了核心的依赖管理和增量编译，还实现了自动变量替换(如 @TARGET)、通配符规则和策略模式的灵活扩展。

写到这里总会忍不住地想起Unix的 KISS 原则, 即 Keep it simple, stupid, 复杂的工具往往由简单的概念组合而成

回到本系列的目录

7 参考

• https://third-bit.com/sdxjs/build-manager/

2025-04-15 13:59:00

项目 GitHub 地址: Page Template

1 前言

在现代网站开发里，内容与表现的分离已经成为基本准则(Separation of content and presentation), 比如 HTML 就是负责内容展现，而 CSS 就是负责页面的样式。

而手动更新和编写 HTML 也是一件费时费力并且容易出错的工作，尤其是需要同时修改多个页面的时候， 因此有聪明的程序员就发明了名为静态网页生成器(static site generator)的技术，可以按需生成网页。

事实上，互联网上的大多数页面都是通过某种形式的静态网页生成器生成出来的。

而静态网页生成器的核心就是「模板引擎」，在过去三十年，诞生过无数的模板引擎， 甚至有位加拿大的程序员为了更方便记录谁访问了他的简历，他还发明了一门编程语言来做模板引擎的活，这就是「世界上最好的编程语言：PHP」。

PHP 可以算是 Web时代的王者之一，凭借着 LAMP(Linux, Apache, MySql, PHP) 架构不断开疆扩土，攻城掠地，而PHP本身也不断有新的框架被造出来，为谁是最好的「模板引擎」打得头破血流。

虽然关于「模板引擎」的战争至今仍未停歇，但细分下来，「模板引擎」可以分成三个主要的流派：

1.1 嵌入式语法

在 Markdown/HTML 这样的标识语言里面嵌入编程语言，使用 <% %> 等符号来标记代码与文本内容，其中的代表包括 Javascript 的 EJS, Ruby 的 ERB, 以及 Python 的 Jinja:

1
2
3
4

<!-- 用特殊标记混合JavaScript与HTML -->
<% if (user) { %>
  <h1><%= user.name %></h1>
<% } %>

其优点就是可以直接使用嵌入的编程语言，功能强大，学习成本低，缺点就是模板很容易变成混杂内容和逻辑的「屎山」代码

1.2 自定义语法

不嵌入现成的编程语言，而是自己开发一套 mini 编程语言，或者叫 DSL(domain specifc language), 代表有 GitHub Page 用到的 Jekyll, 还有 Golang 开发的著名静态网页生成器 Hugo, 都是使用自定义的语法：

1
2
3
4

{% comment %} 自创模板语法 {% endcomment %}
{% for post in posts %}
  {{ post.title | truncate: 30 }}
{% endfor %}

优点就是语法简洁，缺点就是发展下去，可以又是自己造了一个新的编程语言，功能还不如通用的编程语言强大

1.3 HTML指令

不再在 HTML 中嵌入编程语言或DSL，取而代之的是直接给 HTML 定义特定的属性，不同的属性代表不同的含义，但是使用的还是标准 HTML.

最著名的就是 Vuejs:

1
2
3
4

<!-- 用特殊属性实现逻辑 -->
<div v-if="user">
  <h1>{{ user.name }}</h1>
</div>

优点是保持HTML的合法性与简洁，不需要额外的 parser, 缺点就是指令功能受限，不如内嵌编程语言强大，生态工具较少, 灵活性差。

本文的模板引擎就会以这个流派为范式进行开发。

1.4 特例之PHP

分析完三种流派，就会奇怪 PHP 究竟是属于哪个流派呢？

1
2
3
4
5
6

<h1><?php echo $title; ?></h1>
<ul>
  <?php foreach ($items as $item) { ?>
    <li><?php echo $item; ?></li>
  <?php } ?>
</ul>

其实 PHP 本质就是流派二，只是这门专门用于「模板引擎」的 mini 语言，最后演化成了一门专门的编程语言，只是这个编程语言最擅长的还是网页开发，即是做「模板引擎」。

所以 PHP 是从流派二演化成流派一。

2 目标

可能不是所有的朋友都了解 Vue，所以在设计我们的模板引擎之前，先来明确一下需求与目标(scope).

假设我们有如下的 JSON 数据:

1
2
3

{
    names: ['Johnson', 'Vaughan', 'Jackson']
}

如果有如下的模板:

1
2
3
4
5
6
7
8

<html>
  <body>
    <p>Expect three items</p>
    <ul z-loop="item:names">
      <li><span z-var="item"/></li>
    </ul>
  </body>
</html>

那么 names 就会被赋值给 item, 然后每一个变量都会被展开成 <span>{item}</span>, 所以上面的模板就会被展开成:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

<html>
  <body>
    <p>Expect three items</p>
    <ul>
      <li><span>Johnson</span></li>
      <li><span>Vaughan</span></li>
      <li><span>Jackson</span></li>
    </ul>
  </body>
</html>

而不同的指令会有不同的效果，如上的 z-loop 就是遍历一个数组，而 z-if 就是判断一个变量是否为 true, 为 true 则输出，否则则不输出.

如有数据:

1
2
3
4

{
    "showThis": true,
    "doNotShowThis": false
}

和模板:

1
2
3
4
5
6

<html>
  <body>
    <p z-if="showThis">This should be shown.</p>
    <p z-if="doNotShowThis">This should <em>not</em> be shown.</p>
  </body>
</html>

就会被渲染成:

1
2
3
4
5

<html>
  <body>
    <p>This should be shown.</p>
  </body>
</html>

我们可以先支持以下的指令集:

3 设计思路

3.1 stack frame

模板引擎的核心是将「数据」+「模板」渲染成页面，那么数据要如何保存呢？以什么数据结构和变量形式来处理呢？

最简单的方式肯定就是使用全局变量的 HashMap 来保存所有的变量，但是如果存在两个同名的变量，那么 HashMap 这种数据结构就不适用。

更何况，可变的全局变量可谓是万恶之源，不知道有多少 bug 都是源自可变的全局变量。

在编译原理，保存变量的标准做法就是使用 stack frame, 每次进入一个函数就创建一个新的栈(stack), 每次函数调用都有自己的独立的栈，可以理解成每个栈就是一个 HashMap, 而每创建一个栈就是向 List 里面 push 一个新的 HashMap, 同一个函数里面不能有同名的变量，那能保证栈里面的值是唯一。

谈及变量和 stack frame, 编程语言中有个 作用域(scoping) 的概念, 定义了变量会怎么被程序访问到。

主要有两种作用域，分别被称为：

词法作用域(Lexical/Static Scoping): 在编译时就将变量给解析确定了下来，大部分编程语言使用的都是语法作用域，比如 Javascript, C/C++, Rust, Golang, Swift, Java 这个名单还可以很长.

因为其性能更优，并且行为是相当明确的，不需要分析运行时代码再来确定，如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

let x = 10; // 全局变量

function foo() {
  console.log(x); // 词法作用域，问题绑定全局变量 x
}

function bar() {
  let x = 20; // 局部变量，不会影响 foo 中的 x
  foo(); // 调用 foo(), 仍然需要访问全局变量
}

foo(); // 输出: 10 (全局变量)
bar(); // 输出: 10 (还是全局变量，而非局部变量)

另外一种作用域是动态作用域(Dynamic Scoping): 在运行时通过遍历调用栈来确定变量的值，现在已经很少有编程语言使用了，比如是 Perl4, Bash, 或者是 Emacs Lisp:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#!/bin/bash

x="global"

foo() {
  echo "$x"  # x 的值取决于谁来调用 `foo`, 运行时决定
}

bar() {
  local x="local"  # 动态作用域: 会影响 foo 的值
  foo
}

foo  # 输出: "global" (x 是全局变量)
bar  # 输出: "local"  (x 是 bar 函数的局部变量)

也就是 foo 中 x 的值还取决于调用方的栈，因为在 bar 里面调用 foo 时， bash 解释器会把 bar 的栈一并传给 foo, 所以 foo 就以最近栈中 x 的值为准。

这种作用域实现方式虽然简单，但是对于程序员 debug 来说简直是噩梦，所以在现代编程语言基本绝迹了。

话虽如此，但是对于模板引擎而言，动态作用域却是主流选择，主要是因为：

1. 模板的特性需求：循环/条件语句需要运行时创建临时变量
2. 隔离性要求：避免不同模板间的变量污染
3. 异常处理：未定义变量可返回 undefined/null 而非报错

因此我们的模板引擎也会使用动态作用域来保存变量，即 List<HashMap<String, String>> 的数据结构.

3.2 vistor pattern

确定好如何保存变量之后，下一个问题就是如何遍历并且生成模板。

解析HTML之后生成的是 DOM(Document Object Model) 结构, 本质是多叉树遍历，按照指令处理栈的变量，然后再把 HTML 输出, 如下:

1
2
3
4
5
6
7
8

function traverse(node) {
  if (node.type === 'text') console.log(node.data);
  else {
    console.log(`<${node.name}>`);
    node.children.forEach(traverse);
    console.log(`</${node.name}>`);
  }
}

实现是很简单，但是我们把「遍历逻辑」和「不同指令对应的逻辑」耦合在一起了，很难维护。

并且我们现在只支持4个指令，或者未来要增加其他指令，只要在 traverse 里面再增加 if-else 逻辑，基本没有扩展性。

所以我们需要优化的点就是，把「遍历逻辑」和「指令逻辑」分开，这样就易于我们扩展新指令。

要解耦，想想有啥设计模式合适，遍寻23种设计模式，访问者(Vistor)模式 就很合适用来做解耦遍历逻辑和指令逻辑.

不了解 Vistor 模式的同学可以先看下这篇文章, 而Rust 非常著名的序列化框架 Serde 就通过 Vistor 模式可以让用户自定义如何序列化或反序列化某种类型的数据。

3.3 接口设计

既然选定了 Vistor 模式，那么就让我们来设计具体的接口。

Vistor 接口类，接受某个 DOM 元素作为根节点，然后通过 walk 函数遍历给定的节点，或者节点为空则遍历根节点:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import { Node, NodeWithChildren } from "domhandler"
export abstract class Visitor {
  private root: Node;
  constructor(root: Node) {
    this.root = root;
  }

  walk(node: Node = null) {
    if (node === null) {
      node = this.root
    }

    if (this.open(node)) {
      node.children.forEach(child => {
        this.walk(child)
    });
    }
    this.close(node);
  }

  // handler to be called when first arrive at a node
  abstract open(node: Node): boolean;

  // handler to be called when finished with a node
  abstract close(node: Node): void;
}

其中的 open 函数用于在进入一个节点时被调用，相当于是在前序位置被调用，返回值来表现是否需要遍历其子节点；而 close 函数在离开一个节点前，即相当于后序位置被调用。

关于二叉树的前序位置和后序位置，可见这篇讲解二叉树算法的文章

Vistor 算法里面的关键即是实现「遍历逻辑」与「每个节点处理逻辑」的解耦，遍历逻辑我们已经实现在 Vistor 基类了，现在就需要实现一个具体的子类来表示节点的处理逻辑:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

export enum HandlerType {
  If = 'z-if',
  Loop = 'z-loop',
  Num = 'z-num',
  Var = 'z-var',
}

const HANDLERS: Record<HandlerType, NodeHandler> = {
  [HandlerType.If]: new IfHandler(),
  [HandlerType.Loop]: new LoopHandler(),
  [HandlerType.Num]: new NumHandler(),
  [HandlerType.Var]: new VarHandler(),
}

export class Expander extends Visitor {
  public env: Env;
  private handlers: Record<HandlerType, NodeHandler>
  private result: string[]
  constructor(root: Node, vars: Object) {
    super(root);
    this.env = new Env(vars);
    this.handlers = HANDLERS;
    this.result = [];
  }

  open(node: Node): boolean {
    if (node.type === 'text') {
      const textNode = node as Text;
      this.output(textNode.data);
      return false;
    } else if (this.hasHandler(node as Element)) {
      return this.getHandler(node as Element).open(this, node);
    } else {
      this.showTag(node as Element, false);
      return true;
    }
  }

  close(node: Node): boolean {
    if (node.type === 'text') {
      return;
    }
    if (node.type === 'tag' && this.hasHandler(node as Element)) {
      this.getHandler(node as Element).close(this, node);
    } else {
      this.showTag(node as Element, true);
    }
  }

  // 判断是否有 z-* 属性对应的指令处理器
  hasHandler(node: Element): boolean {
    for (const name in node.attribs) {
      if (name in this.handlers) {
        return true;
      }
    }
    return false;
  }

  getHandler(node: Element) {
    const possible = Object.keys(node.attribs)
      .filter(name => name in this.handlers)
    assert(possible.length === 1, 'Should be exactly one handler');
    return this.handlers[possible[0]];
  }

  // 将 tag 标签及属性输出到 output 去，但排除 `z-` 开头的指令
  showTag(node: Element, closing: boolean) {}

  output(text: string) {
    this.result.push((text === undefined) ? 'UNDEF' : text);
  }

Expander 的逻辑也并不复杂，每次遍历到一个 DOM 元素的时候，通过元素类似执行对应的操作，如果是 z- 开头的指令，就看下能否找到对应指令的处理器:

仔细观察代码会发现，不同的指令对应的处理器实现了 NodeHandler 接口，定义在前序位置和后序位置处理节点的逻辑，并按指令名保存在 HANDLER 中：

1
2
3
4

export interface NodeHandler {
  open(expander: Expander, node: Element): boolean;
  close(expander: Expander, node: Element): void;
}

这就意味着，如果需要增加一个新的指令，该指令处理器只需要实现 NodeHandler 接口，并添加到 HANDLER 即可，不需要改动其他的已有代码，我们就实现了「遍历逻辑」与「指令逻辑」的解耦。

4 实现

4.1 支持的指令集

不同的指令集的差别只是如何实现 open 和 close 逻辑，我就不一一赘述了，已支持的指令集及实现列表如下：

4.2 示例

假设有数据如下:

1
2
3
4
5
6
7
8

const vars = {
    "firstVariable": "firstValue",
    "secondVariable": "secondValue",
    "variableName": "variableValue",
    "showThis": true,
    "doNotShowThis": false,
    "names": ["Johnson", "Vaughan", "Jackson"]
};

4.2.1 z-num

1
2
3
4
5

<html>
  <body>
    <p><span z-num="123"/></p>
  </body>
</html>

模板展开如下：

1
2
3
4
5

<html>
  <body>
    <p><span>123</span></p>
  </body>
</html>

4.2.2 z-var

1
2
3
4
5

<html>
  <body>
    <p><span z-var="variableName"/></p>
  </body>
</html>

模板展开如下：

1
2
3
4
5

<html>
  <body>
    <p><span>variableValue</span></p>
  </body>
</html>

4.2.3 z-if

1
2
3
4
5
6

<html>
  <body>
    <p z-if="showThis">This should be shown.</p>
    <p z-if="doNotShowThis">This should <em>not</em> be shown.</p>
  </body>
</html>

模板展开如下：

1
2
3
4
5
6

<html>
  <body>
    <p>This should be shown.</p>

  </body>
</html>

4.2.4 z-loop

1
2
3
4
5
6
7
8

<html>
  <body>
    <p>Expect three items</p>
    <ul z-loop="item:names">
      <li><span z-var="item"/></li>
    </ul>
  </body>
</html>

模板展开如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

<html>
  <body>
    <p>Expect three items</p>
    <ul>
      <li><span>Johnson</span></li>

      <li><span>Vaughan</span></li>

      <li><span>Jackson</span></li>
    </ul>
  </body>
</html>

4.2.5 z-include

1
2
3
4
5
6

<html>
  <body>
    <p><span z-var="variableName"/></p>
    <div z-include="simple.html"></div>
  </body>
</html>

simple.html :

1
2
3
4

<div>
  <p>First</p>
  <p>Second</p>
</div>

模板展开如下：

1
2
3
4
5
6
7
8
9

<html>
  <body>
    <p><span>variableValue</span></p>
    <div>
  <p>First</p>
  <p>Second</p>
</div>
  </body>
  </html>

更多的示例可见

5 总结

模板引擎的本质，是帮我们把重复的页面结构抽离出来，而内容与表现的分离(Separation of content and presentation)，可以让我们以数据来填充变化的内容。

这是程序员对「Don’t Repeat Yourself」原则最直观的践行。

三十年来，开发者们创造了无数种实现方案，但核心思路始终围绕着前文提到的三种基本模式。

如今即便在最流行的 Vue 或 React 框架中，无论你写的是 JSX 或是 v-* 指令，背后的思路仍万变不离其宗，本质上仍在沿用模板引擎的思想。

而这种「结构复用，数据驱动」的理念，也早已成为Web开发的根基。

回到本系列的目录

6 参考

• https://refactoring.guru/design-patterns/visitor
• https://serde.rs/impl-deserialize.html
• https://third-bit.com/sdxjs/page-templates/

2025-04-10 14:08:00

1 缘起

在《软件那些事儿》播客采访听众故事的系列里面，有一期名为《No.502 跟35岁的程序员聊聊比特币》¹ 长达三个多小时的播客，主人公分享自己与比特币的故事，还谈到其在2020年卖房买比特币的故事。

既钦佩这位仁兄知行合一的投资理念，也羡慕他卖房买比特币的财力，胆识与机遇。

这位同行在节目结束前分享了一本名为《过河卒》²的书籍，其作者戴习为是文革前就读于中国科技大学电子系的高材生。

为什么他会在聊比特币故事的播客节目中提及这位书呢？

因为比特币的作者中本聪的第一封已知公开的邮件³，即讨论比特币白皮书草稿的邮件，就是发给戴习为之子，戴维 ⁴的:

戴维的项目 b-money ⁵与比特币有诸多的相似之处，甚至可以称为比特币的雏形, 所以中本聪在白本书中引用了 b-money , 原文:

I was very interested to read your b-money page. I’m getting ready to release a paper that expands on your ideas into a complete working system.

而戴维是著名的密码学专家，在大一的时候就写出了被诸多公司和开源项目使用的支持多种加密算法的C++加密库 Cryptocpp ⁶

虽然错过了买比特币的致富之路，但是多读点书，多学点知识终究是不会晚的，所以对《过河卒》这本书产生了浓厚的兴趣，不到一周就读完了。

2 太平洋两岸

2.1 年少时分

戴习为（下文称老戴）生于1947年，比共和国还要年长2岁，其祖父为武汉名医， 父亲亦师承其父，学得一手好医术，又学过高能物理，还是少数能扣操流利英语和日语的人材，母亲为中学教师。

老戴说起来是湖北人，但实际并没有在湖北生活过，满月不久就随父母迁居湖南长沙, 到1956年，老戴独自一人离开了父母，到北京投奔了奶奶。

年少时的老戴对一切都充满好奇心，9岁的时候，他决定做一个属于自己的矿石收音机， 费尽九牛二虎之力终于成功，当他在自制的收音机里面听到《杨家将》的评书时，心中那份得意就别提了。

初中时候，老戴通过杂志，自制了一台有两个直流电子管的再生式便携式收音机， 不久后他凭借同龄人中明显的技术优势考进了北海公园内的中国少年科技馆，拥有了帝王才可免费享用的北海公园。

1964年，毛主席再次发出以阶级斗争为纲的路线指引，教育界在批判了1962年，1963年以「智育第一」的错误招生倾向后， 提出了1964年的高考招生要优先选拔工人，贫下中农的子弟，教育要为无产阶级政治服务。

而对那些非红五类家庭出身的考生而言，如果又不是党团员， 那么他们只有表现得格外优秀才可能赢得本属于你的权利。

而对于家境殷实的老戴家庭而言，虽然没有被打为「地主阶级」之类的黑五类，但也被毕业鉴定上写上了「学习目的不明确」的标语。

但偏偏不信邪的老戴除了刻苦学习，还把目标放在了中国科技大学，因为班主任每次和他谈话结束都要加句： 「像你这样的表现科技大学能收你吗？」，在当时，中科大专业设置和毕业后的去向对家庭出身的要求要比清华，北大更苛刻。

发榜之后，他如愿考上了中国科技大学的电子系，1964年的中科大，含金量可见一斑。

2.2 大学时光

在中科大读了两年大学之后，阅读了各种书籍之后，文革爆发。

在文革初期，红卫兵们流行「大串联」，即大中学生红卫兵组织或个人为主体，在全国范围内免费乘车，接待（食宿）， 互相串联，交流和宣传造反的活动。

但老戴作为「逍遥派」，对政治活动并没有太多兴趣，他却利用了「大串联」的机会，游历起了祖国的大江南北： 从北京到广州，从广州到杭州，再从杭州到上海。

又尝试过「星火燎原」之行，从北京步行到上海。

2.3 走进社会

毕业之后，老戴和其同学兼女友被分配到商丘的军队参军两年，而后复业在商丘无线电厂参加了三年工作, 机缘巧合之下被调至中科院天文台，参加天文台的建设。

后来，为了解决北京户口问题，老戴与妻子借调到了新组建的科学院空间科学技术中心， 没想到困扰无数北漂的户口问题，在上世纪七十年代的时候，也同样困扰着像老戴之样的高材生。

老戴在任期间，陪同妻子，完成了新部门「地面部」的搭建，并出色地完成密云遥感卫星地面接收站的选址与建设，至今仍发光发热。

1977年，中国恢复了高考，1978年，中国恢复了研究生招考，1979年，第一批留学生选派出国。

1981年，时年34岁，担任快视课题组组长的老戴决定出国，申请了东北大学应用数学系公派自费的博士，并「幸运」被录取。

2.4 留学美利坚

仅身揣20美元的老戴，在美国举目无亲的老戴，登上飞往美国的飞机。

按照老戴的说法，像他这一拨在举国上下一穷二白的大旗下长大的一代，没钱的好处就是做任何决定时，钱的分量也不重。

他在波士顿的第一晚，是在美国「派出所」的沙发上度过了，虽然东北大学减免了学费，但并未提供任何的生活费的。

因此在「朋友的朋友的朋友」的介绍下， 老戴在名为「杭州楼」的餐馆后来做起了包食住，无工资的工作，过上了白天上课读书，晚上工作帮厨的生活, 老戴称之为「洋插队」.

34岁的老戴在东北大学攻读博士，先在应用数学系研究数学，后转向计算机系，研究并行计算，但历经4年都未有突破性进展， 也未有影响力的论文发表，老戴陷入进退两难的局面。

因此39岁的时候，老戴不想再等待了，于东北大学博士缀学, 重新步入社会，自个刨食。

2.5 创业种种

老戴先是与朋友合伙，为华人公司定制中文系统，却不料受朋友坑骗，公司破产，还牵涉到一桩官司；

后来老戴与一名博士合并开发并行电脑，但历时一年未果，最后净身离开；后又与朋友合作于加拿大，结果不欢而散。

鉴于种种与人合作的失败经历，老戴决定自己单干，开发模式识别系统，用于电脑识别手写的文字与语音，后被仅此于IBM的第二大电脑公司 DEC 赏识，重金招募至麾下。

90年代，PC电脑风起云涌，日新月异，以Window + Intel 的Wintel 联盟强势崛起，以小型机为主的 DEC 不得不裁员应对，老戴也恰逢时分，离开 DEC，创立自己的 DTech 公司单干，专注手写文字与语音识别。

而当时华尔街正吹起了「笔电脑」的风，使用「笔」作为输入设备的电脑，而识别输入文字自然成为「笔电脑」必不可少的功能，老戴的 DTech 凭借其技术优势，成为了「风口上的猪」，苹果，微软，IBM纷纷递来橄榄枝。

最后，在比尔盖茨的亲自决策下，以「x位数」的价格收购了 DTech, 老戴也就顺势入职微软，成为总经理，后来领导了打赢IBM与苹果的笔电脑战役。

虽然老戴未透露「x位数」的具体数额，但是相信肯定是超过千万美元级别，90年代的千万美元也足以一辈子生活富足无忧了。

在1994年，比尔盖茨首次访华，老戴作为唯一的随员相随，陪同比尔盖茨会见了中国相关的领导人。

3 感悟

3.1 将相本无种，书成自有神

读完老戴的同事，让我总是会想起之前读的一本书：《走出戈壁》：从沙漠苦力到常青藤教授 ⁷, 作者从小学未毕业戈壁的苦力，一直努力到成为常青藤的教授，老戴也是类似的经历。

虽然努力并不一定能成功，毕竟汗水，才华，运气都是成功不可或缺的因素，但是没有能力，机会即使飞到你面前，你也无法抓住。

读完全书，令我印象深刻的是两件关于读书的事:

1970年，在河南商丘无线电厂工作的老戴，工作之余，仍不忘学习，不断收集在那个时代与那个环境能够找到的新技术书籍， 不久，一门新的技术「数字电路与计算机」开始吸引并迷住了老戴。

作为一个学习过程，老戴争取机会，在一个与河南省的轻工技术研究所合作改造商丘市一个玻璃瓶厂的程序控制的工程中， 担当了数字电子技术这一部分的技术骨干，并出色完成了这一项目。

从此，老戴从一个学习模拟电子技术的工程师开始走进了数字时代。

在1988年，老戴在并行公司创业失败离开时，他充满了苦涩，他开始怀疑自己，对自己的命运是否期许过高，他不断地问自己， 或许他是那只在田地里不断掰玉米的狗熊? 是那只饶有兴致在水中捞着月亮的猴子?

他想起自己在美国学了4年的数学，学习了并行计算机的理论与算法，他还想起了自己在1976年唐山大地震的时候， 他还住在北京地震棚时，苦读过一番的《数字图像处理》，《傅里叶光学》与《模式识别理论》​。

他决定凭借曾经苦读的知识，使用模式识别来识别手写文字与语音, 最终成就了 DTech 公司.

「狐狸固然吃不到高架上的葡萄，但它可以在矮架上种上一棵」，来自「吃不了葡萄说葡萄酸」故事的启发。

3.2 家庭的影响

对于老戴的成功，其努力自然不容置喙, 但是我现在越发觉得个人的成就不仅和个人的努力及才华相关，还与其家庭息息相关，环境对个人成长太重要了。

古人也是类似的看法，不然孟母又何必三迁呢。

而作为被中本聪引用的论文作者戴维(下称小戴)，身为中国第一代程序员的父母对其影响不可谓不大。

小戴80年代就能接触并学习编程，以至于在小学时期，就能帮一个台湾来美的研究生做数据结构的作业；

初二时，小戴与大多数孩子一样，开始了暑假打工生涯，不同的是，在其他同龄人只能选择在社区送报纸，擦洗车之类的工作时。

小戴跑到了妈妈正在工作的，一个为全球几大石油公司提供油井数据分析的石油软件公司当程序员。

小戴用C语言写了一个子程序：

将公司软件产品中正在使用的，因不同类的客户机器而使用的不同格式的浮点数据转换成IEEE规定的标准格式浮点数据， 使本公司产品与其他公司产品的数据衔接更方便。

高一时，小戴即被学生推荐到哈佛大学计算机系选修课程，并计入学分，被由中学（实际是州政府）支付学费， 理论上，小戴可以在高中毕业的同时在哈佛大学毕业，类似国内的少年班。

在高中毕业后，小戴非常轻松地被华盛顿州立大学的计算机系录取，华大的计算系可以在全美排前十的。

小戴在大一的时候，用 C++ 实现了一个涵盖已公开发表过的主要加密与解密算法的软件库， 成为北美第一个被全民共享，而已至今仍被全世界（包括中国）广泛使用的加解密算法库。

读过计算机专业的同学应该听过一句名言：不要实现你自己的加解密算法库（和共识算法库），因为非常难实现正确，一旦出问题后果又非常严重。

所以小戴的水平可想而知。

3.3 大厂感悟

书中还有不少篇幅是描写在微软的工作体验，这让我这个从毕业起就在国内外大厂后辈非常有感悟，其实都是一样的。

微软有着非常好的员工福利，有着委托给星级酒店的食堂，弹性的上下班时间， 有非常优美的园区，非常自由和充满活力的文化氛围。

除不考勤上下班时间之外，公司还从早10点到下午2点，每一小时一趟的班车，在园区内与园区边设备豪华的健身俱乐部间穿梭。

公司支付健身的一切费用，员工可游泳，或网球……，活动筋骨，锻炼身体;一年四季，或小组，或大组，或整个公司，三日一小宴，五日一大宴。

美食美酒，Party不断; 新上影的电影、热门棒球赛、NBA篮球赛、橄榄球大赛、歌星演唱会，公司赠票给员工全家，请你务必赏光。

一年三百六十五天，公司开满了各式各样的进修课程，鼓励诸位踊跃参加。

如诸位能大体上不影响日常工作，而学校又肯收你，读博士、读硕士，公司均乐于为你支付学费。

听起来真是神仙过的日子。

甚至过年的时候包下了几百英亩的地方来搞年会，把加拿大马术队，奥林匹克跳伞队也请过来表演。

但是公司终究不是疗养院，公司更不可能养大爷，任务已经明确了，只是为了让工程师们能赶上 milestone (也就是 deadline)

好酒好饭无非是让你上阵时精力充沛、生龙活虎罢了。就如同那第一流的奶牛场，请你听音乐，给你做按摩，为的是请你多出牛奶。

更何况，羊毛出自羊身上，微软给的薪资只有同期硅谷同行的一半略多，直到现在也是如此，也难怪人送外号「花生厂」(薪水相对较低的戏称).

而弹性上下班，就可以加班不给加班费了。

更何况，现在不流行给奶牛弹音乐，做按摩来多产奶了，现在流行用鞭子抽奶牛，还威胁奶牛，不多产奶就以绩效差把你开了，让你自生自灭。

对于 milestone, 弹性加班之类的「资本主义把戏」，我是再熟悉不过了。

我在微信支付 ⁸的时候，微信支付推行的是所谓的「精益迭代」研发模式， 大意每两周作为一个周期，把任务拆分到能两周内完成的颗粒度， 在第二周的周五进行「复盘」，由领导（或是经理，或是总监）开会对着需求单与工程师逐个核对进度。

也就意味着每两周就有一次 deadline, 完成这两周的任务并不能影响下一个两周的任务的轮转，迭代总是周而复始，直到你被滚动的车轮碾碎。

任务太大怎么办，总能拆小的，两周总要交付什么东西的。

没有完成怎么办？不用担心，你总可以想办法完成的, 不然要怎么向领导交待呢, 这些都是数据和指标。

这样洗礼了三年后，现在无论多少任务，都有种羽扇纶巾，谈笑间，需求灰飞烟灭的淡定从容了。

3.4 Better than before

老戴通过自己的经历告诉我们:

无论是白人，黑人，黄种人，无论在农村还是城市，也无论是出生在穷家还是富户，追求成功的人们，只要你努力，只要你执着，做得到的。

社会对成功的定义往往固化,「出将入相」「成名成家」「腰缠万贯」，但「将相本无种」，真正的成功，是超越昨天的自己。

过好每一个今天，就是通往成功的路。 立足当下，辨明方向，踮起脚尖，哪怕只比昨天前进一寸。

这或许像「鸡汤」，但真理往往朴素，从翻开一本书、迈出第一步开始，让身体或思想始终在路上。

秉持「Better than before」的信念，「卒子」一步步向前，直到跨过那条「河」，化身为「车」.

如卒过河，日拱一卒，终有一日，平凡亦可蜕变为非凡。

推荐阅读

• 旅加经历
  • 这些年走过的路：从广州到温哥华
  • 加拿大之初体验
  • 登陆加拿大一年后的体会
  • 夏日捕蟹记
• 历史思考
  • 为什么梦想买不起，故乡回不去
  • 闲聊写作的好处
  • 金榜题名之后
• 工具流分享
  • 简明写作指南
  • 我的写作流
  • 我的画图流：画图工具与技巧分享
  • 我的搜索流：高效搜索经验分享
  • 最好的学习方式：费曼学习法(Feynman Technique)
  • 系统思考：既见树木，又见森林
• 职场思考
  • 编程十年的感悟
  • 那些年，我从微信支付学到的东西
  • 杂谈AI取代程序员

公号同步更新，欢迎关注👻

2025-03-16 02:01:00

项目 GitHub 地址: Regex

1 前言

所谓的正则表达式，指的是由一系列字符和特殊字符组成的模式，用于描述要匹配的文本。

最开始是一位叫 Stephen Cole Kleene 的数学家用被他称为 Regular Events 的数学表达式来描述这一模型，在 1968 年，由C语言之父 Ken Tompson 将这个表达式引入到行编辑器 QED, 随后是 Unix 上的编辑器 ed (vi 的前身) ，并最终引入到 grep.

我一直很好奇正则表达式 (regular expression, 即 Regex ) 是怎么实现的，自正则表达式被引入编程语言之后 之后，可谓说有字符串的地方就基本有正则表达式。

想起个关于 Regex 的经典笑话:

程序员A：我有个问题，想用正则表达式解决。

程序员B：现在你有两个问题了。

2 需求

完整版本的正则表达式非常复杂，我们的实现不会覆盖所有的规则，所以先来看下我们要支持的正则表达式规则：

虽然这五条原则看起来不是很多，但是已经覆盖日常开发绝大多数的场景了。

比如 ^ab*c 就意味着匹配以 a 开头，并且0到无数个的 b, 再接一个字符 c, 所以它能匹配: ac, abc 以及 abbbbbc

3 初始版本

根据上面的需求，可以使用40行不到的代码就实现一个简单的递归版本的正则表达式引擎：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

export const match = (pattern: string, text: string): boolean => {
  // '^' at start of pattern matches start of next.
  if (pattern[0] === '^') {
    return matchHere(pattern, 1, text, 0);
  }

  // Try all possible starting points for pattern.
  let iText = 0;
  do {
    if (matchHere(pattern, 0, text, iText)) {
      return true;
    }
    iText += 1;
  } while (iText < text.length);

  // Nothing worked.
  return false;
}

const matchHere = (pattern: string, patternIndex: number, text: string, textIndex: number) => {
  // There is no more pattern to match.
  if (patternIndex === pattern.length) {
    return true;
  }

  // '$' at end of pattern matches end of text.
  if ((patternIndex === (pattern.length - 1)) && (pattern[patternIndex] === '$') && (textIndex === text.length)) {
    return true;
  }

  // '*' following current character means zero or more.
  if (((pattern.length - patternIndex) > 1) && (pattern[patternIndex + 1] === '*')) {
    // Try matching zero occurences(skip the current char and the '*')
    if (matchHere(pattern, patternIndex + 2, text, textIndex)) {
      return true;
    }

    // Try matching one or more occurences
    while ((textIndex < text.length) && (pattern[patternIndex] === '.' || text[textIndex] === pattern[patternIndex])) {
      // Try to match the rest of pattern after consuming this
      // character
      if (matchHere(pattern, patternIndex + 2, text, textIndex + 1)) {
        return true;
      }
      textIndex += 1;
    }
    // if there is any match, it will return early in the while loop,
    // so when reach this statement, it means nothing found.
    return false;
  }

  // Match a single chacater.
  if (textIndex < text.length && (pattern[patternIndex] === '.') || (pattern[patternIndex] === text[textIndex])) {
    return matchHere(pattern, patternIndex + 1, text, textIndex + 1);
  }

  // Nothing worked.
  return false;
}

实现思路如下图:

好的，我们的正则表达式引擎完工了，正则表达式看起来也没有那么难嘛。

只是用是能用的，但是看起来不同含义的字符都耦合在 matchHere 函数了，想要支持新的字符匹配(例如 +, 或者 | )很难扩展。

4 面向对象版本

4.1 接口

再来思考一下版本1的问题:

我们把不同模式的符号都耦合在同一个函数中。

在讨论解耦方式之前，先来观察下每个模式的共同点，以便我们抽象接口。

以最简单的 ^c 模式为例，我们需要将 c 与给定的文本 abc 和 cde 作比较，首先匹配第一个字符，如果匹配失败(如 abc)，则直接结束； 如果匹配第一个字符成功（=cde=）, 那么就匹配剩余的其他字符, 直到模式匹配结束.

那么对于精确匹配字符的模式 Literal 而言，入参就是字符 c 和文本 text, 返回结果就是true/false, 用来表示是否匹配成功.

1

const literal_match = (pattern: string, text: string): boolean => {}

如果不同的模式匹配都使用这个函数签名的话，每次匹配之后，都需要把剩下需要匹配的文本给复制出来，频繁拷贝字符串可能会导致性能开销很大。

我们可以做个小优化, 通过下标 start 来指定需要匹配的文本, 就可以在不同的模式中都只使用同一份的字符串，避免了多次拷贝的开销。

而返回结果也不再是 boolean, 而是下一个模式需要匹配的下标。

比如 ^c 来匹配 cde ，匹配成功之后就返回 1, 就意味着下个模式从 1, 也就是 d 开始匹配.

那匹配失败要怎么表示？这个也很简单，返回一个不合法的下标，比如 -1 即可，那么我们的模式的函数接口就变成:

1

const literal_match = (pattern: string, text: string, index: number): number => {}

4.2 模板设计模式

既然版本一提到了 matchHere 实现耦合在一起，那么有什么方式可以实现解耦呢？

其中的一个经典解决方式就是面向对象编程(Object Oriented Programming)，这也是面向对象编程的设计初衷。

既然前面实现的缺点是不同的模式耦合在一起，那么我们可以把每种模式实现成一个函数或者一个类，然后再通过某种模式给组合起来。

既然用到 OOP, 那么自然少不了设计模式了。如果使用一种模式表示成一个类，那么会是哪种设计模式呢？

要不就是策略模式(strategy):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class ConcreteAlgorithm : IAlgorithm
{
    void DoAlgorithm(int datum) {...}
}

class Strategy
{
    Strategy(IAlgorithm algo) {...}

    void run(int datum) { this->algo.DoAlgorithm(datum); }
}

要么就是模板方法(template method):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class ConcreteAlgorithm : AbstractTemplate
{
    void DoAlgorithm(int datum) {...}
}

class AbstractTemplate
{
    void run(int datum) { DoAlgorithm(datum); }

    virtual void DoAlgorithm() = 0; // abstract
}

看起来好像都可以，那不如就使用模板方式吧。

4.3 单向链表

那么就让我们来定义个基类 RegexBase :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

export const INVALID_INDEX = -1;
export abstract class RegexBase {
  // index to continue matching at or -1 indicating that matching failed
  abstract _match(text: string, start: number): number;
  abstract rest: RegexBase;

  match(text: string): boolean {
    // check if the pattern matches at the start of the string
    if (this._match(text, 0) !== INVALID_INDEX) {
      return true;
    }
    for (let i = 1; i < text.length; i += 1) {
      if (this._match(text, i) !== undefined) {
        return true;
      }
    }
    return false;
  }
}

细看之下, 函数签名与我们上文讨论的有所不同，那是因为我们把模式 pattern 作为每个模式类的成员变量了，就不需要显式定义在 _match 函数中了。

再来看下我们精确匹配字符的 Lit 模式类的实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class RegexLit extends RegexBase {
  private chars: string;
  rest: RegexBase
  constructor(chars: string, rest: RegexBase | null = null) {
    super()
    this.chars = chars;
    this.rest = rest;
  }

  _match(text: string, start: number): number {
    const nextIndex = start + this.chars.length;
    if (nextIndex > text.length) {
      return INVALID_INDEX;
    }

    if (text.slice(start, nextIndex) !== this.chars) {
      return INVALID_INDEX;
    }

    if (this.rest === null) {
      return nextIndex;
    }

    return this.rest._match(text, nextIndex);
  }
}

实现很简单, 但 rest 又是什么呢?

还是以 ^c 为例, 现在改复杂一点, 模式变成 ^cd 来匹配 cde ，模式 ^c 匹配完 c 之后, 就要使用剩下的模式(rest) d 来匹配剩下的文本 de, 剩下的模式可能也会再包含剩下的模式，用来匹配再被剩下的文本，依此类推.

相当于 rest 就是指向下一个模式类的单向指针，用来表示下一个模式需要匹配剩余的文本，直到所有的模式匹配完成，即 rest 指针指向 null

所以模式 cde 就可以表示成 Lit('c', Lit('d', Lit('e')))

而所有的模式组合在一起，本质就是一条单向链条，而正则表达式就是判断是否存在依次匹配链表中所有模式的文本。

4.4 Any 模式

Any 模式即 * 匹配 0到任意个前一个字符，与其类似的还有 Plus 模式，即 + 匹配1到任意个前一个字符字符；以及 ? 表示匹配0到1个前一个字符，Any算是最有代表性和最难实现的模式。

即 a*b 表示可以匹配0到任意个 a ，再匹配一个 b , 所以 b, ab, aaaaaab 它都可以匹配上。

那么问题就来了，既然它可以匹配0到任意个字符，那么匹配的时候我要匹配几个字符呢？

理论上有 N 个的可能性, N = 待匹配文本 text 的长度。

既然不知道要匹配几个字符，那不如我们把所有可能性都穷举一次呗，而这种穷举算法，则被称为是回溯算法(backtracking)

我们知道穷举的上界是 N(N=len(text)), 下界是 0, 那么是从 0 穷举到 N, 还是从 N 穷举到 0 呢？

两种方法都可以解决问题，计算机科学家们还给这两种做法起了个洋气的名字， N -> 0, 因为是先开始匹配所有的字符，所以就被称为贪婪匹配 greedy(eager) matching.

而从 0 -> N, 因为是从0开始，所以又被称为是惰性匹配 lazy matching。

从性能的角度来说，是 lazy matching 更优，因为它尽可能地去掉了不必要的匹配了。

我们可以先来看下贪婪匹配的实现，再看下惰性匹配：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class RegexAny extends RegexBase {
  private child: RegexBase;
  private rest: RegexBase;

  constructor(child: RegexBase, rest: RegexBase | null) {
    super();
    this.child = child;
    this.rest = rest;
  }

  _match(text: string, start: number): number | null {
    const maxPossible = text.length - start;
    for (let num = maxPossible; num >= 0; num -= 1) {
      const afterMany = this._matchMany(text, start, num);
      if (afterMany !== undefined) {
        return afterMany;
      }
    }
    return undefined;
  }

  _matchMany(text: string, start: number, num: number) {
    for (let i = 0; i < num; i += 1) {
      start = this.child._match(text, start);
      if (start === undefined) {
        return undefined;
      }
    }

    if (this.rest !== null) {
      return this.rest._match(text, start);
    }
    return start;
  }
}

a*b 会被解析成, Any(Lit('a'), Lit('b')), 因为 * 表示匹配0到任意个前一个字符，前一个字符还可能另外一种模式，所以我们可以把前一个字符也解析成模式，作为 child 传入到 Any.

_matchMany 是从 start 匹配到 start+num 位置，看是否匹配，而 maxPossible 表示当前剩余文本中可能的最大匹配次数.

以 text = "aab", start = 0, pattern = a*b 为例， maxPossible = len(text) = 3,

1. 第一轮尝试(num=3):

   • 尝试匹配 3 个 a -> 失败(只有 2 个 a)

2. 第二轮尝试(num=2):

   • 匹配 2 个 =a=(位置 0->1->2)
   • 然后匹配 rest(b 在位置 2->3): 成功！
   • 返回 3

   

以及使用模式 a*ab 来匹配文本 ab 的过程:

4.5 支持的模式

每种模式对应一个单独的类之后，再通过 rest 指针进行关联，现在的实现就非常易于扩展了，我们可以很容易地支持其他的模式，具体列表如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

describe('Regex testsuite', () => {
    it.each([
        ['a', 'a', true, Lit('a')],
        ['b', 'a', false, Lit('b')],
        ['ab', 'ba', false, Lit('ab')],
        ['^a', 'ab', true, Start(Lit('a'))],
        ['^b', 'ab', false, Start(Lit('b'))],
        ['a$', 'ab', false, Lit('a', End())],
        ['a$', 'ba', true, Lit('a', End())],
        ['a*', '', true, Any(Lit('a'))],
        ['a*', 'baac', true, Any(Lit('a'))],
        ['ab*c', 'ac', true, Lit('a', Any(Lit('b'), Lit('c')))],
        ['ab*c', 'acc', true, Lit('a', Any(Lit('b'), Lit('c')))],
        ['ab*c', 'abc', true, Lit('a', Any(Lit('b'), Lit('c')))],
        ['ab*c', 'abbbc', true, Lit('a', Any(Lit('b'), Lit('c')))],
        ['ab*c', 'abxc', false, Lit('a', Any(Lit('b'), Lit('c')))],
        ['ab*c', 'ac', true, Lit('a', LazyAny(Lit('b'), Lit('c')))],
        ['ab*c', 'acc', true, Lit('a', LazyAny(Lit('b'), Lit('c')))],
        ['ab*', 'ab', true, Lit('a', LazyAny(Lit('b')))],
        ['ab+c', 'ac', false, Lit('a', Plus(Lit('b'), Lit('c')))],
        ['ab+c', 'abc', true, Lit('a', Plus(Lit('b'), Lit('c')))],
        ['a(b|c)d', 'xabdy', true, Lit('a', Alt(Lit('b'), Lit('c'), Lit('d')))],
        ['a(b|c)d', 'xabady', false, Lit('a', Alt(Lit('b'), Lit('c'), Lit('d')))],
        ['ab?c', 'abc', true, Lit('a', Opt(Lit('b'), Lit('c')))],
        ['ab?c', 'acc', true, Lit('a', Opt(Lit('b'), Lit('c')))],
        ['ab?c', 'a', false, Lit('a', Opt(Lit('b'), Lit('c')))],
        ["[abcd]", 'a', true, CharClass([Lit('a'), Lit('b'), Lit('c'), Lit('d')])],
        ["[abcd]", 'ab', true, CharClass([Lit('a'), Lit('b'), Lit('c'), Lit('d')])],
        ["[abcd]", 'xhy', false, CharClass([Lit('a'), Lit('b'), Lit('c'), Lit('d')])],
        ["c[abcd]", 'c', false, Lit('c', CharClass([Lit('a'), Lit('b'), Lit('c'), Lit('d')]))],
    ])('Regex base test ("%s" "%s" "%p")', (_pattern, text, expected, matcher) => {
        const actual = matcher.match(text);
        expect(actual).toBe(expected);
    })
});

顺便一提的是，这种相同的验证逻辑, 但是输入多个不同的参数以验证不同case的做法，叫做 Parameterized Test

我在《测试技能进阶系列》的第二篇也曾经介绍过： Parameterized Tests

这样我们就完成了一个功能较完整的正则表达式引擎了。

5 表达式解析

虽然我们已经完成了一个正则表达式引擎，只不过我们平时用表达式是 a*bc ，现在要写成 Any(Lit('a'), Lib('b', Lib('c'))) 多个类的实例也太烦琐了。

让我们再来分析下正则表达式，以 ^(a|b|$)*z$ 为例，以任意数量的 a, b, 或 $ 开头, 再紧接一个 z, 然后结束。

我们可以创建一个树来表达这个表达式:

在考虑如何把表达式变成上面那棵树之前，我们可以先从最简单的步骤开始：分割字符串

正如物理学家给不可再分的元素称之为「原子」(atom), 计算机科学家也给不可再分割的文本起了一个名字，称之为 token, 类似 a, b, $, * 这些都是 token，而把文本切分成 token 的过程，即为 tokenize 。

不同的token可能代表不同的含义，像 a, b, c 这类，所以它们的值不同，但是它们都可以被称为字面量(Literal), 而像 *, +, |, (, ) 这样的字符又各种其代表的含义, 如:

1
2
3
4
5
6

const SYMBOL_TOKEN_TYPE_MAP = {
  '*': TokenKind.Any,
  '|': TokenKind.Alt,
  '(': TokenKind.GroupStart,
  ')': TokenKind.GroupEnd,
}

定义好 token 类型之后， tokenize 跃然纸上了：

直接按照字符作匹配，如果能匹配上的就是特殊类型的 Token ，不然就是字面量:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

export interface Token {
  kind: TokenKind,
  location: number
  value?: string,
}

export const tokenize = (text: string) => {
  const result: Token[] = [];
  for (let i = 0; i < text.length; i += 1) {
    const c = text[i]
    if (c in SIMPLE) {
      result.push({ kind: SIMPLE[c], location: i });
    } else if ((c === '^') && (i === 0)) {
      result.push({ kind: TokenKind.Start, location: i });
    } else if ((c === '$') && (i === (text.length - 1))) {
      result.push({ kind: TokenKind.End, location: i });
    } else {
      result.push({ kind: TokenKind.Lit, location: i, value: c });
    }
  }
  return result;
}

^(a|b|$)*z$ 就会被解析成如下的结果:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

[
  {
    "kind": "Start",
    "location": 0
  },
  {
    "kind": "GroupStart",
    "location": 1
  },
  {
    "kind": "Lit",
    "location": 2,
    "value": "a"
  },
  {
    "kind": "Alt",
    "location": 3
  },
  {
    "kind": "Lit",
    "location": 4,
    "value": "b"
  },
  {
    "kind": "Alt",
    "location": 5
  },
  {
    "kind": "Lit",
    "location": 6,
    "value": "$"
  },
  {
    "kind": "GroupEnd",
    "location": 7
  },
  {
    "kind": "Any",
    "location": 8
  },
  {
    "kind": "Lit",
    "location": 9,
    "value": "z"
  },
  {
    "kind": "End",
    "location": 10
  }
]

6 组装抽象语法树

tokenize 的结果是一个包含 Token 的列表，我们要如何组装成树状数据结构呢？

顺带一提，这树状数据结构全称是抽象语法树(Abstract syntax tree, AST), 是一种用来表示程序结构的数据结构，如:

我们可以分情况来讨论，因为不同的模式有不同的组装方式，组装完之后的 AST 的输出是一个 output, 包含组装后的 token 列表:

对于表达式 a, 我们可以创建一个 Lit 类型的 token (为了便于理解，「创建」指创建一个 token, 然后插入到 output.)

对于表达式 a* 呢？我们可以先创建一个 Lit('a') 的 token, 当遇到 * 时，因为 * 表示匹配0至任意的前一个字符, 所以我们可以创建一个 Any 类型的 token, 然后把 output 最后一个元素 pop 出来，作为 Any 的 child 元素.

对于表达式 (ab), 情况就变得复杂一些: 当遇到 ( 括号的时候，我们可以创建一个 Group ，但是问题在于，我们不知道这个 Group 什么时候结束，即不知道什么时候才会遇上 ).

所以我们需要换种解决思路：当遇到 (, 创建一个 GroupStart 类型的 token, 然后再继续处理 a, b, 当遇到 ) 时，创建一个 Group 类型的 token, 然后一直调用 pop 函数直到把 GroupStart 也 pop 出来, 然后把过程中 pop 出来的 token 都当作是 Group 的 children 列表，而 GroupStart 相当于起到一个标记符的作用。

这种思路就自动处理了 (a*) 和 (a(b*)c) 的差异:

对于表达式 a|b, 我们是否可以参考 Any 的做法呢?

遇到 a 的时候先创建一个 Lit('a'), 遇到 | 时再创建一个 Alt, 然后把 Lit('a') 从 output pop 出来作为 left 节点， 再遇到下一个字符 b 的时候，再把 Alt 从 output pop 出来，把 b 作为 right 节点。

听起来没问题，但是上面的算法无法正确解析 a|b*, 它表示匹配一个 a 或者是任意数量的 b, 但是我们的做法会把它解析成 (a|b)*, 即任意数量的 a 或 b.

更合理的做法是先部分组装 Alt 的 left 节点，等解析完所有字符之后，再重新解析一次，把 right 节点给组装上。

以 a|b* 为例子:

1. 创建一个 Lit('a') token
2. 当遇到 | 的时候，创建一个 Alt, 并将 Lit('a') pop 出来作为 left 节点
3. 创建一个 Lit('b') token
4. 创建一个 Any token, 并将 Lit('b') pop 出来作为 child 节点.
5. 当解析完所有字符后, 再遍历一次 output, 如果遇到 Alt token, 那么就把它的下一个 token (即 Any) 作为它的 right 节点.

实现代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

export const parse = (text: string) => {
  const result: Token[] = [];
  const allTokens = tokenize(text);
  for (let i = 0; i < allTokens.length; i += 1) {
    const token = allTokens[i];
    const isLast = i === allTokens.length - 1;
    handle(result, token, isLast);
  }
  return compress(result);
}

const handle = (result: Token[], token: Token, isLast: boolean) => {
  if (token.kind === TokenKind.Lit) {
    result.push(token);
  } else if (token.kind === TokenKind.Start) {
    assert(result.length === 0, 'Should not have start token after other tokens');
    result.push(token);
  } else if (token.kind === TokenKind.End) {
    assert(isLast, `Should not have end token before other tokens`);
    result.push(token);
  } else if (token.kind === TokenKind.GroupStart) {
    result.push(token);
  } else if (token.kind === TokenKind.GroupEnd) {
    result.push(groupEnd(result, token));
  } else if (token.kind === TokenKind.Any) {
    assert(result.length > 0, `No Operand for '*' (location ${token.location})`);
    token.child = result.pop();
    result.push(token)
  } else if (token.kind === TokenKind.Alt) {
    assert(result.length > 0, `No Operand for '|' (location ${token.location})`);
    token.left = result.pop();
    token.right = null;
    result.push(token)
  } else {
    assert(false, `UNIMPLEMENTED`);
  }
}

const groupEnd = (result: Token[], token: Token): Token => {
  const group: Token = {
    kind: TokenKind.Group,
    location: null,
    end: token.location,
    children: []
  };

  while (true) {
    assert(result.length > 0, `Unmatched end parenthesis (location ${token.location})`);
    const child = result.pop();
    if (child.kind === TokenKind.GroupStart) {
      group.location = child.location;
      break;
    }
    group.children.unshift(child);
  }
  return group;
}

// go through the output list to fill in the right side of Alts:
const compress = (raw: Token[]) => {
  const cooked: Token[] = [];
  while (raw.length > 0) {
    const token = raw.pop();
    if (token.kind === TokenKind.Alt) {
      assert(cooked.length > 0, `No right operand for alt (location ${token.location})`);
      token.right = cooked.shift();
    }
    cooked.unshift(token);
  }
  return cooked;
}