MoreRSS

site iconRamsay Leung修改

博客 编程 开源 世界 加拿大
软件工程师，蚂蚁金服 - 微信 - AWS，使用Emacs 与Linux 
RSS: https://ramsayleung.github.io/zh/index.xml
请复制 RSS 到你的阅读器，或快速订阅到 :

Inoreader Feedly Follow Feedbin Local Reader

Ramsay Leung的 RSS 预览

重新造轮子系列(六)：构建工具

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

变量 含义 示例
% 通配符, 表示匹配任意非空字符串，通常用于模式规则（Pattern Rules）中 %.o: %.c 匹配任意 .c 文件生成 .o
$@ 目标文件名 output
$^ 所有依赖文件 main.o utils.o
$< 第一个依赖文件 main.o

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

我们的自动变量 make 变量 含义
% % 通配符, 表示匹配任意非空字符串
@TARGET $@ 目标文件名
@DEPENDENCIES $^ 所有依赖文件
@DEP[0] $< 第一个依赖文件
@DEP[n-1] 第 n 个依赖文件

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 参考

重新造轮子系列(五)：模板引擎

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>

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

指令集 含义
z-loop 循环遍历数组生成元素内容
z-if 条件渲染，值为false时移除元素
z-var 将变量值输出到元素内容
z-num 直接输出数字值到元素内容

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 逻辑，我就不一一赘述了，已支持的指令集及实现列表如下：

指令 作用 实现
z-if 条件渲染，值为false时移除元素 z-if.ts
z-include 引入外部HTML文件内容 z-include.ts
z-iteration 数字迭代，生成序列内容 z-iteration.ts
z-literal 保留元素原始属性不解析 z-literal.ts
z-loop 循环遍历数组生成元素内容 z-loop.ts
z-num 直接输出数字值到元素内容 z-num.ts
z-snippet 定义可复用的HTML片段 z-snippet.ts
z-trace 打印变量值到控制台（调试用） z-trace.ts
z-var 将变量值输出到元素内容 z-var.ts

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 参考

《过河卒》: 比特币雏形之父之父的故事

2025-04-10 14:08:00

1 缘起

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

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

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

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

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

戴维的项目 b-money 5与比特币有诸多的相似之处，甚至可以称为比特币的雏形, 所以中本聪在白本书中引用了 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 6

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

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 将相本无种，书成自有神

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

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

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

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

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

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

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

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

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

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

3.2 家庭的影响

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 大厂感悟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 Better than before

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

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

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

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

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

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

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

推荐阅读

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

  1. https://podcasts.apple.com/us/podcast/no-502-%E8%B7%9F35%E5%B2%81%E7%9A%84%E7%A8%8B%E5%BA%8F%E5%91%98%E8%81%8A%E8%81%8A%E6%AF%94%E7%89%B9%E5%B8%81/id1147186605?i=1000697534091 ↩︎

  2. https://book.douban.com/subject/1106247/ ↩︎

  3. https://www.bitcoin.com/satoshi-archive/emails/wei-dai/1/ ↩︎

  4. http://www.weidai.com/ ↩︎

  5. http://www.weidai.com/bmoney.txt ↩︎

  6. https://cryptopp.com/ ↩︎

  7. https://ramsayleung.github.io/zh/post/2024/%E8%B5%B0%E5%87%BA%E6%88%88%E5%A3%81/ ↩︎

  8. https://ramsayleung.github.io/zh/post/2023/%E4%BB%8E%E5%BE%AE%E4%BF%A1%E6%94%AF%E4%BB%98%E7%A6%BB%E7%BA%BF_%E6%88%91%E5%B8%A6%E8%B5%B0%E4%BA%86%E4%BB%80%E4%B9%88/ ↩︎

重新造轮子系列(四)：正则表达式引擎

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 需求

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

含义 字符
任意的字符 c c
任意的单个字符 .
匹配开头的字符 ^
匹配结尾的字符 $
匹配零个或多个的字符 *

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

比如 ^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 指针进行关联，现在的实现就非常易于扩展了，我们可以很容易地支持其他的模式，具体列表如下：

含义 字符 例子 对应实现
任意的字符 c c c 匹配字符c Lit
任意的单个字符 . . 匹配任意字符
匹配开头的字符 ^ ^c 匹配以 c 开头的字符串 Start
匹配结尾的字符 $ c$ 匹配以 c 结尾的字符串 End
匹配零个或多个的字符 * a* 匹配0-任意个a的字符串, 贪婪匹配 GreedyAny
匹配零个或多个的字符 * a* 匹配0-任意个a的字符串, 惰性匹配 LazyAny
匹配一个或多个的字符 + a+ 匹配1-任意个a的字符串 Plus
匹配零个或一个的字符 ? a? 匹配0-1个a的字符串 Opt
多选一匹配 ❘ a❘b 匹配a或b的字符串 Alt
序列匹配 () (ab) 匹配 ab 的字符串 Group
匹配方括号内的任意单个字符 [] [abcd] 匹配a或b或c或d的字符串 CharClass 
 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;
}

对于表达式 a|(bc), 输出的 AST 如下:

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

[
    {
        kind: TokenKind.Alt, location: 1, left: {
            kind: TokenKind.Lit, location: 0, value: 'a'
        },
        right: {
            kind: TokenKind.Group, location: 2, end: 5,
            children: [
                { kind: TokenKind.Lit, location: 3, value: 'b' },
                { kind: TokenKind.Lit, location: 4, value: 'c' },
            ]
        }
    },
]

7 实例化

既然抽象语法树 AST 已经就绪了，我们就差最后一步了，把 AST 转变为我们的类实例.

还记得上文提到过, 不同的模式对应不同的类，然后通过 rest 指针指向下一个模式类，以此串成一个链表。

那么我们对于 output 这个包含多个 token 的列表，我们可以抽象成两个 token, 当前 token 和下一个 token:

假如我们有函数 f 可以把当前 token 初始化对应的模式类，我们只需要再把剩下的 token 列表初始化成 rest, 那么 rest 要怎么初始化呢？

只需要再调用 f 即可.

这不就是递归嘛! 是的，通过递归就很简单地把实例化也实现出来了:

 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

export const compile = (text: string): RegexBase => {
  const tokens: Token[] = parse(text);
  return createObjectByAST(tokens);
}

// return instances of classes derived from RegexBase by abstract syntax tree
const createObjectByAST = (tokens: Token[]): RegexBase | null => {
  if (tokens.length === 0) {
    return null;
  }
  const token = tokens.shift();
  if (token.kind === TokenKind.Lit) {
    return Lit(token.value, createObjectByAST(tokens));
  } else if (token.kind === TokenKind.Start) {
    return Start(createObjectByAST(tokens));
  } else if (token.kind === TokenKind.End) {
    assert(tokens.length === 0, `Should not have end token before other tokens`);
    return End();
  } else if (token.kind === TokenKind.Alt) {
    return Alt(createObjectByAST([token.left]), createObjectByAST([token.right]), createObjectByAST(tokens));
  } else if (token.kind === TokenKind.Group) {
    return Group(token.children.map((childToken) => createObjectByAST([childToken])), createObjectByAST(tokens));
  } else if (token.kind === TokenKind.Any) {
    return Any(createObjectByAST([token.child]), createObjectByAST(tokens));
  } else {
    assert(false, `UNKNOWN token type ${token.kind}`);
  }
}

8 总结

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

it.each([
  ['a', 'a', true, Lit('a')],
  ['^a', 'ab', true, Start(Lit('a'))],
  ['a$', 'ab', false, Lit('a', End())],
  ['a*', 'baac', true, Any(Lit('a'))],
  ['ab+c', 'abc', true, Lit('a', Plus(Lit('b'), Lit('c')))],
  ['ab+c', 'abxc', false, Lit('a', Plus(Lit('b'), Lit('c')))],
  ['(ab)|(cd)', 'xaby', true, Alt(Group([Lit('a'), Lit('b')]), Group([Lit('c'), Lit('d')]))],
  ['a(b|c)d', 'xabdy', true, Lit('a', Group([Alt(Lit('b'), Lit('c'))], Lit('d')))],
  ['ab?c', 'ac', true, Lit('a', Opt(Lit('b'), Lit('c')))],
  ['ab?c', 'acc', true, Lit('a', Opt(Lit('b'), Lit('c')))],
  ["[abcd]c", 'ac', true, CharClass([Lit('a'), Lit('b'), Lit('c'), Lit('d')], Lit('c'))],
  ["c[abcd]", 'c', false, Lit('c', CharClass([Lit('a'), Lit('b'), Lit('c'), Lit('d')]))],
])('parse, compile and matcher test ("%s" "%s" "%p")', (pattern, text, expected, expectedMatcher) => {
  const actualMatcher = compile(pattern);
  expect(actualMatcher).toStrictEqual(expectedMatcher);
  const actual = actualMatcher.match(text);
  expect(actual).toBe(expected);
})

大功告成，终于将所有的功能都组装起来实现这个正则表达式引擎了, 除去前文提到的功能之外，还实现了 \* 转义特殊字符， [xya] 匹配 x, y, z 其中任意字符，以及 *? 实现惰性匹配的功能。

完整功能集的测试 case 可见 parser_test.ts

日常使用正则表达式的场景非常多，因为其强大的功能和表达能力，总会下意识觉得很难实现（当然，高性能的完整版本的确是非常有挑战性的）。

但是当自己把正则表达式引擎这个轮子拆开，再重新造一个出来之后，才感悟到：

「没有启程的路才会遥不可及」，很多时候，困难只是我们给自己设下的心理障碍。

回到本系列的目录

9 参考

重新造轮子系列(三): HTML Selector

2025-03-16 01:53:00

项目 GitHub 地址: Selector 1

1 前言

以前写爬虫的时候，必不可少的一个工具就是 HTML selector, 就是用于匹配指定的 HTML 标签。

毕竟爬虫的本质就是找出需要的标签里面的内容，然后解析出来。

而 selector 主要有两个流派，一个是 CSS selector 2, 另外一个是 XPath selector 3 ,本质都是通过某种语法来匹配指定的标签，区别只是一个用的是 CSS 的语法，另外一个是 XML 语法.

这次我们就来写个基于 CSS 语法的 Selector, 来深入理解下 HTML 的 DOM 模型

2 DOM

写过前端的朋友应该都知道，前端代码主要是由所谓的三剑客组成的：HTML + CSS + JavaScript, 其中的三剑客各司其职，相互配合。

HTML 负责内容展示, CSS 负责布局和样式，而 JavaScript 是负责用户与页面之间的动态交互。

而对于如下的 HTML 代码：

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

<html>
  <head>
    <title>Example</title>
  </head>
  <body>
    <h1>Title</h1>
    <blockquote id="important">
      <p>Opening</p>
      <p>Explanation</p>
      <p class="highlight">Warning</p>
    </blockquote>
    <p>Closing</p>
  </body>
</html>

浏览器会将其进行解析，并生成名为 Document Object Model(DOM) 的数据结构，听着好像很玄乎，但本质就是一棵多叉树 (Multiway Tree):

知道 DOM 是多叉树, 我们就可以写出简化版本 DOM 的数据结构了：

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

export interface DomNode {
    type: string;
    name?: string;
    attribs?: {
        id?: string;
        class?: string;
        [key: string]: string | undefined;
    };
    children?: DomNode[];
    data?: string;
    parent?: DomNode;
}

一个节点可能有多个子节点 (children?) 或者一个父节点 (parent?), 也可能都没有，所以标记成 ?(optional);

一个节点可能有多个属性 attribs.

而节点的=type= 可能是 tag, text, comment, script, style, 而对于 text 和 comment 类型的节点， name 也是为空的.

这个 DOM 结构只是我们的简化版本，完整的 DOM 还有很多的属性和回调函数，详情可以查看文档： Document Object Model (DOM)

3 BFS vs DFS

理解到 DOM 的本质是个多叉树之后，我们很快就能意识到， selector 本质也就是遍历多叉树，找到符合要求的所有节点, 比如按 tag 名来匹配，按 id 来匹配，按 class 来匹配等等。

而用于遍历多叉树的常用算法就是广度优先搜索(Breadth First Search, BFS)和深度优先搜索(Depth First Search, DFS)

通常来说，BFS 和 DFS 都能完成多叉树遍历，时间复杂度也是相同的，BFS通常使用一个 queue 来记录遍历待节点，所以会使用更多的内存，但是能找到最短路径；而 DFS 通常使用递归，如果遇到个循环图，就会 StackOverflow，无法找到结果。

因为我们明确知道 DOM 是个多叉树（有向无环图），所以我们就使用 DFS 来遍历查找。

4 Strategy 设计模式

分析好问题之后，我们的实现也差不多能出来了, 按 tag 名来匹配，无非是 domNode.name === tagName; 按 class 来匹配, 即 domNode.attribs.class=== class.

为了解耦和易于扩展，我们可以使用个策略设计模式(Strategy Design Pattern 4).

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

interface Selector {
    match(node: DomNode): boolean;
}

const findByTagName = (tag: string): Selector => ({
    match: (node: DomNode): boolean => {
        return node.name.toLowerCase() === tag.toLowerCase()
    }
});

const findById = (id: string): Selector => ({
    match: (node: DomNode): boolean => {
        return node.attribs.id === id;
    }
})

const findByClass = (clazz: string): Selector => ({
    match: (node: DomNode): boolean => {
        return node.attribs.class === clazz;
    }
});

然后遍历节点的时候，只需要判断 Selector 是否符合要求，而具体的匹配条件则由 selector 决定:

1
2
3

const isMatch = (node: DomNode, selectors: Selector[]): boolean => {
    return selectors.every(selector => selector.match(node));
}

这样的话，要增加一个根据属性keyValue值的匹配条件也是非常容易的, 如 div[align=center], 即匹配属性 align 和value 为 center:

1
2
3
4
5

const findByAttributes = (key: string, value: string): Selector => ({
    match: (node: DomNode): boolean => {
        return node.attribs[key] === value;
    }
})

5 测试验证

DFS + Strategy design pattern 就实现了一个基础的 CSS Selector, 我们自然需要测试验证下是否正确:

 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('HTML selector testsuite', () => {
    const HTML = `<main>
  <p>text of first p</p>
  <p id="id-01">text of p#id-01</p>
  <p id="id-02">text of p#id-02</p>
  <p class="class-03">text of p.class-03</p>
  <div>
    <p>text of div / p</p>
    <p id="id-04">text of div / p#id-04</p>
    <p class="class-05">text of div / p.class-05</p>
    <p class="class-06">should not be found</p>
  </div>
  <div id="id-07">
    <p>text of div#id-07 / p</p>
    <p class="class-06">text of div#id-07 / p.class-06</p>
  </div>
</main>`

    it.each([
        ['p', 'text of first p'],
        ['p#id-01', 'text of p#id-01'],
        ['p#id-02', 'text of p#id-02'],
        ['p.class-03', 'text of p.class-03'],
        ['div p', 'text of div / p'],
        ['div p#id-04', 'text of div / p#id-04'],
        ['div p.class-05', 'text of div / p.class-05'],
        ['div#id-07 p', 'text of div#id-07 / p'],
        ['div#id-07 p.class-06', 'text of div#id-07 / p.class-06']
    ])('test select %s %s', async (selector, expected) => {
        const doc = htmlparser2.parseDOM(HTML)[0];
        const node = select(doc, selector);
        const actual = getText(node);
        expect(actual).toBe(expected);
    })
})

使用 Jest 框架编写了如上的单元测试用例， unit test 都通过了，完工.

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

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

6 总结

这个简单的 CSS Selector 全部代码仅有 103 行, 但麻雀虽小，五脏俱全，功能还是齐备的:

1
2
3
4
5
6
7
8

> tokei simple-selectors.ts
===============================================================================
Language            Files        Lines         Code     Comments       Blanks
===============================================================================
TypeScript              1          131          103            9           19
===============================================================================
Total                   1          131          103            9           19
===============================================================================

所以标题也可以修改成 100 行代码实现一个简单的 CSS Selector :)

如果细看实现，还是有不少的优化之处的，比如 parseSelector 函数可以实现得更优雅些，以便进一步扩展支持其他的语法。

另外就是目前支持的都是所有 selector 完全匹配的情况，即 and, 但是目前不支持 or 的功能，即类如: h1,h2,h3, 可以匹配 h1, h2, 或者 h3.

如果想要看下较完整版本的 CSS Selector, 可以看下我六年多前我用 C++ 实现的版本, 实现从字符串解析并生成 DOM, 再实现 CSS 解析器，纯正的 OOP 风味。

当时初学 C++, 这个算是我早期写得比较大的 C++17 项目，核心代码大概1000行，还有几百行的单元测试。

现在再翻看自己的代码，会惊讶于当时自己代码写的工整，可谓是有板有眼，像极了书法初学者写的楷书。

这本砖头书读过, 其他的C++书籍, 如, , 也读过, 感觉不把书中的内容实践下, 很容易遗忘。

但是日常的工作内容并不会涉及底层网络服务, 一切底层细节内容都被框架给包掉了, 开发的主力语言是Java, 也不会使用到C++.

因此决定创造个机会实践下这些知识，最终决定只用C/C++内置函数库实现。

的确所有工具都是用C/C++内置函数库实现的，甚至测试框架还是自己用宏实现的.

只是我未曾想到的是，写了这段话后不足一年，C++就成为了我下一家公司干活的主力语言; 而现在，我又在重新写 Java, 着实是「白衣苍狗」。

回到本系列的目录

  1. https://github.com/ramsayleung/reinvent/tree/master/html_selector ↩︎

  2. https://developer.mozilla.org/en-US/docs/Web/CSS/CSS_selectors ↩︎

  3. https://developer.mozilla.org/en-US/docs/Web/XML/XPath/Guides ↩︎

  4. https://refactoring.guru/design-patterns/strategy ↩︎

重新造轮子系列(二)：文件备份

2025-03-03 03:57:00

项目 GitHub 地址: File Backup

1 前言

既然我们已经有单元测试框架来测试软件了，我们肯定不想已经写好的代码丢失掉。

对于重要的文件，一个必不可少的功能肯定是备份, 这样在丢失文件之后可以重新恢复。

今天我们就来写个简单的文件备份软件，类似 Git 这样的版本系统可以当作是高级版本的文件系统，因为它还支持切换到不同版本，对比版本间的差异等等功能，而我们不打算实现一个版本管理系统，只实现基础的文件备份功能。

2 实现思路

2.1 校验文件是否变更

我们不可能备份都将所有的文件备份一次，这样做效率太低了，我们应该只备份发生变更的文件，那么如何高效地判断文件是否发生变更呢？

最简单粗暴的方式是把文件读取出来，然后与以备份的文件作对比，但是这样的效率太低，并且算法复杂度是: O(N), 即运行时间是随着文件内容增长而增长的，文件越长，对比越慢。

最优算法的复杂度是 O(1), 我们希望可以通过常数时间内比较完文件内容。

我们可以使用 密码哈希算法(Cryptographic hash algorithms), 来实现判断文件是否发生变更，它有两个显著的特征:

  1. hash 函数的结果是定长，不会因输入变化而增加或减少
  2. 只要输入的任意bit生成变更， hash 函数生成的结果都会不一样

因此我们可以将文件的内容使用密码哈希函数如 sha1 来hash, 通过比较两次的哈希结果是否一致来判断文件是否发生变更。

2.2 判断文件是否被备份

判断文件是否被备份就很直接了，只需要看下当前文件是否在目标路径存在。

再结合上文提到的，只备份内容发生变更的文件，那么我们可以使用哈希函数的结果作为目标路径的备份文件名。

假设有文件 src/a.txt, 它的文件内容的哈希结果是 86f7e437faa5a7fce15d1ddcb9eaeaea377667b8, 那么我们使用哈希值作为文件名备份到 dst, 即 dst/86f7e437faa5a7fce15d1ddcb9eaeaea377667b8.

对于文件 a.txt, 只需要判断 dst 是否存在 86f7e437faa5a7fce15d1ddcb9eaeaea377667b8, 就知道 a.txt 是否被备份;

更巧妙的是，如果的 a.txt 文件内容发生变化，那么它的哈希值就一定不再会是 86f7e437faa5a7fce15d1ddcb9eaeaea377667b8 那么查找文件不存在，也可以当作是未备份，直接重新备份。

下面的序列图就是low level design:

2.3 性能优化

备份涉及到非常多的文件IO操作，而IO恰恰就是 Nodejs 最擅长的领域, 毕竟曾经的 NodeJS 还有个项目叫做 io.js.

NodeJS 的异步IO是基于 libuv, 但是我们不需要支持使用 libuv 的API, 只需要把文件相关的操作封装在 Promise 里面，NodeJS就会帮我们在处理底层的 IO 调度, 尽可能地并发处理IO, 避免阻塞.

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

export const hashExisting = (rootDir: string): Promise<PathHashPair[]> => {
    const pattern = `${rootDir}/**/*`;
    return new Promise((resolve, reject) => {
        glob(pattern)
            .then(matches => Promise.all(
                matches.map(path => statPath(path))
            ))
            .then((pairs: PathStatPair[]) => pairs.filter(
                ([path, stat]) => stat.isFile()))
            .then((pairs: PathStatPair[]) => Promise.all(
                pairs.map(([path, stat]) => readPath(path))))
            .then((pairs: PathContentPair[]) => Promise.all(
                pairs.map(([path, content]) => hashPath(path, content))
            ))
            .then((pairs: PathHashPair[]) => resolve(pairs))
            .catch(err => reject(err))
    })
}

更多关于 Promise 的内容，可以查看这本书，它的解释非常到位.

2.4 测试文件系统

备份文件的设计我们已经分析和实现完了，接下来肯定是需要编写单元测试来测试我们的函数的，我们的文件备份涉及到非常多的文件操作，免不了要和文件系统打交道，包括创建文件，查找文件等等。

单元测试的其中一个原则就是要尽量屏蔽掉外部系统的依赖，以保证我们只聚焦在测试功能本身，文件系统的读写更像是集成测试需要做的事情, 各种操作也很容易把文件目录结构给搞乱，导致单元测试失败。

所以我们希望可以使用一个 mock object 来把文件系统 mock 掉，mock-fs 这个库做的就是这样的事情, 它可以把程序中的文件操作都 mock 掉，实际操作的是内存对象而非文件系统.

我们就可以在每个单元测试运行时，任意构造任何想要的文件目录，并且保证文件操作都是在操纵内存对象， 而不会直接作用到文件系统，保证单元测试的相互隔离。

 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

import mock from 'mock-fs'

describe('checks for pre-existing hashes using mock filesystem', () => {
    beforeEach(() => {
        mock({
            'bck-0-csv-0': {},
            'bck-1-csv-1': {
                '0001.csv': 'alpha.js,abcd1234',
                'abcd1234.bck': 'alpha.js content'
            },
            'bck-4-csv-2': {
                '0001.csv': ['alpha.js,abcd1234',
                             'beta.txt,bcde2345'].join('\n'),
                '3024.csv': ['alpha.js,abcd1234',
                             'gamma.png,3456cdef',
                             'subdir/renamed.txt,bcde2345'].join('\n'),
                '3456cdef.bck': 'gamma.png content',
                'abcd1234.bck': 'alpha content',
                'bcde2345.bck': 'beta.txt became subdir/renamed.txt'
            }
        })
    })

    afterEach(() => {
        mock.restore()
    })
})

上面的代码就构造出下如下的文件目录：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

├── bck-0-csv-0
├── bck-1-csv-1
│   ├── 0001.csv
│   └── abcd1234.bck
└── bck-4-csv-2
├── 0001.csv
├── 3028.csv
├── 3456cdef.bck
├── abcd1234.bck
└── bcde2345.bck

3 使用示例

 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

> tree .
.
├── backup.ts
├── check-existing-files.ts
├── hash-existing-promise.ts
├── main.ts
├── manifest.ts
├── reinvent_file_backup.org
├── run-hash-existing-promise.ts
├── stream-copy.ts
└── test
    ├── bck-0-csv-0
    ├── bck-1-csv-1
    │   ├── 0001.csv
    │   └── abcd1234.bck
    ├── bck-4-csv-2
    │   ├── 0001.csv
    │   ├── 3028.csv
    │   ├── 3456cdef.bck
    │   ├── abcd1234.bck
    │   └── bcde2345.bck
    ├── test-backup.js
    ├── test-find-mock.js
    └── test-find.js

5 directories, 18 files

> npx tsx main.ts -s . -d /tmp/backup -f json -v
[INFO] Destination directory ensured: /tmp/backup
[INFO] Starting backup from '.' to '/tmp/backup'
[INFO] Copied 8 files from /Users/ramsayleung/code/javascript/reinvent/file_backup to /tmp/backup
Backup completed in: 15.96ms
Backup completed successfully!

> ls -alrt /tmp/backup
total 88
drwxrwxrwt  23 root         wheel   736  2 Mar 17:06 ..
-rw-r--r--@  1 ramsayleung  wheel  1056  2 Mar 21:02 6bd385393bd0e4a4f9a3b68eea500b88165033b1.bck
-rw-r--r--@  1 ramsayleung  wheel  1649  2 Mar 21:02 8b0bc65c42ca2ae9095bb1c340844080f2f054da.bck
-rw-r--r--@  1 ramsayleung  wheel  9795  2 Mar 21:02 464240b6ef1f03652fefc56152039c0f8d105cfe.bck
-rw-r--r--@  1 ramsayleung  wheel   636  2 Mar 21:02 d0f548d134e99f1fcc2d1c81e1371f48d9f3ca0c.bck
-rw-r--r--@  1 ramsayleung  wheel   182  2 Mar 21:02 7fa1b33f68d734b406ddb58e3f85f199851393db.bck
-rw-r--r--@  1 ramsayleung  wheel   666  2 Mar 21:02 369034de6e5b7ee0e867c6cfca66eab59f834447.bck
-rw-r--r--@  1 ramsayleung  wheel  2533  2 Mar 21:02 02d5c238d29f9e49d2a1f525e7db5f420a654a3f.bck
-rw-r--r--@  1 ramsayleung  wheel  3512  2 Mar 21:02 964c0245a5d8cb217d64d794952c80ddf2aecca8.bck
drwxr-xr-x@ 11 ramsayleung  wheel   352  2 Mar 21:02 .
-rw-r--r--@  1 ramsayleung  wheel  1030  2 Mar 21:02 0000000000.json

为什么 file_backup 目录里面有 18 个文件，只备份了8个文件呢？因为 test 目录里面所有的文件都是空的，所以备份时就跳过了。

4 总结

我们就完成了一个文件备份软件的开发，功能当然还非常简单，还有非常多优化的空间，比如现在 src 目录的所有文件都会被平铺到 dst 目录，如果我们可以保存目录结构，那么就更好用了。

另外，使用哈希函数值作为文件名的确很巧妙，但是对于用户而已，如果不逐个打开文件，根本不知道哪个文件是对应哪个源文件等等。

如果想要实现一个更健壮易用的备份文件，可以参考下关于这 rsync 系列的文章 , rsync 是Linux 上非常流行的增量备份的文件，不仅可以备份本地文件，更可以把文件备份把远程服务器，非常强大。

回到本系列的目录

5 参考