Ramsay Leung的 RSS 预览

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

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 来说简直是噩梦，所以在现代编程语言基本绝迹了。

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

模板的特性需求：循环/条件语句需要运行时创建临时变量
隔离性要求：避免不同模板间的变量污染
异常处理：未定义变量可返回 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岁的程序员聊聊比特币》¹ 长达三个多小时的播客，主人公分享自己与比特币的故事，还谈到其在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」的信念，「卒子」一步步向前，直到跨过那条「河」，化身为「车」.

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

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,

第一轮尝试(num=3):
- 尝试匹配 3 个 a -> 失败(只有 2 个 a)
第二轮尝试(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* 为例子:

创建一个 Lit('a') token
当遇到 | 的时候，创建一个 Alt, 并将 Lit('a') pop 出来作为 left 节点
创建一个 Lit('b') token
创建一个 Any token, 并将 Lit('b') pop 出来作为 child 节点.
当解析完所有字符后, 再遍历一次 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 前言

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

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

而 selector 主要有两个流派，一个是 CSS selector ², 另外一个是 XPath selector ³ ,本质都是通过某种语法来匹配指定的标签，区别只是一个用的是 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 ⁴).

 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, 着实是「白衣苍狗」。

回到本系列的目录

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

2025-03-03 03:57:00

项目 GitHub 地址: File Backup

1 前言

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

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

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

2 实现思路

2.1 校验文件是否变更

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

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

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

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

hash 函数的结果是定长，不会因输入变化而增加或减少
只要输入的任意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 参考

软件工程师的软技能指北（六）：谈薪篇

2025-02-18 07:06:00

1 目录

2 前言

打了这么多年工，要说最后悔和最遗憾的是什么，「拿到 Offer 之后没有好好和 HR 谈薪资绝对算是（甚至没有之一）」。

如果说面试前的简历准备，刷题，面试中应付面试官的各种提问以及面试之外的学习与积累是一场马拉松比赛的话，那么拿到 Offer 就意味着你已经成功完成征程的前九十九步了，而商谈薪资待遇就是最后一步，亦是最关键的一步。

如果这一步没有做好，前面的九十九步无论多完美都等于白费了，可谓是令人痛惜。

谈得成功的话，可能一年工资就多了一辆车了（至于是五菱MINI 还是保时捷911就看实力了）。

3 认知

回想我之前曾经关于「谈薪资」的错误认知，可谓是非常经典，可惜当初没有师长可以为我指正。

3.1 学生思维

刚毕业时的「这是家大公司，我是来学东西的，开什么薪资都可以」, 这个可以算是典型的「学生思维」，甚至出发点就是错的。

工作的根本目的就是「为了赚钱养活自己，过上更好的生活」，而不是去企业里面学习，「学习新本领」也只是「打工赚钱」的副产品而已。

经历过各种残酷的「末位淘汰」后我就发现，企业招「应届生」进去也不是因为看中你潜力大啥的，而是需要你这个年龄段的员工，企业也有各种政府下达的就业指标，而招你进去也不是让你学东西的，而是让你干活的。

最明显的佐证就是，我所经历过的大公司每年的「末位淘汰」会有很多的应届生被打低绩效，毕竟刚出校门的学生在能力，经验等方面是肯定是不如老员工的。

「末位淘汰」从来都不是激励你学习的，而是让你多干活的。

既然公司招聘员工是为了公司利益的最大化，员工自然就要最大化自己的利益。

3.2 心理负担

不要把公司 拟人化 ，不要觉得和公司「谈判」不好，因此产生心理负担，公司只是众多利益相关的人组成的共同体而已。

3.3 不愿意承担风险

诚然, 现在整体就业大环境肯定不如2010-2020年的黄金十年，各种裁员降薪的消息层出不穷, 但如果持有「能找到个工作就不错了，还谈什么薪资」的认知，可能很难去HR谈薪资, 毕竟你潜意识就已经选择接受 Offer, 除非是 HR 的报价是远低于你的底线.

须知，收益永远是风险挂钩的，你永远不可能有高收益，零风险的投资标的。

3.4 默认公平幻想

「工资由能力决定，相信公司会公平对待，肯定可以拿到对应的薪资，不需要自己去谈」

我曾经也持有种这样的「幻想」，以为凭借面试的表现折服了面试官，他自己会帮我争取, 甚至给我一个好的薪资.

首先，在较大的公司，面试官都是无法决定或者甚至知道薪资的，会有专门的 HR 团队来和你的谈判薪资的；

其次，你也很难期望面试官能把技术面试的结果如实呈现给非技术出身的 HR.

总而言之，「有枣子没枣子打一棒就好了」，争取了不一定要有，但是不争取绝对不会有人给你加工资的.

4 风险收益分析

我用博弈论模型来简单分析下分析公司和求职者的策略互动过程中风险与收益, 用收益矩阵来表示双方的选择和收益。

假设公司有三种策略:

接受谈薪（给更高薪资）
拒绝谈薪（维持原 Offer）
撤回 Offer

求职者也有三种策略:

不谈
温和谈判
强硬谈判

分析策略:

不谈薪（保守策略）
- 公司不会撤回 Offer，但求职者没有额外收益。
温和谈判（合理博弈）
- 60% 机会加薪 5W，40% 机会薪资不变，公司很少会撤回 Offer（5%）。
强硬谈判（高风险高回报）
- 50% 机会加薪 10W，30% 机会薪资不变，但 20% 可能失去 Offer。

收益矩阵:

	公司接受 (+5W)	公司拒绝 (0W)	公司撤回 (-5W)
不谈 (30W)	30W	30W	30W
温和谈判 (35W)	35W(60%)	30W(40%)	30W(5%)
强硬谈判 (40W)	40W (50%)	30W (30%)	5W (20%)

纳什均衡:

如果求职者选择温和谈判，公司最优策略是接受或拒绝，而非撤回 Offer，因为撤回 Offer 也意味着公司损失招聘成本。
如果求职者选择强硬谈判，公司可能更倾向于撤回 Offer，因为不愿承担过高的薪资成本。
温和谈判是最优策略，因为它在风险和收益之间达到了较好的平衡, 既有提升空间，又降低 Offer 撤回风险.

也就是对于求职者来说，如果你选择谈判，谈判失败，你的结果大概率也是接受原 Offer而已，而一旦谈判成功，你将会获得额外的收益。

可以说在接 Offer 谈判时 风险低, 收益中, 甚至高 , 而不谈薪是最保守的策略，但也是收益最低的.

5 公司的策略

公司的终极目的肯定是为了创造营收，而在招聘中直接目的是希望可以招到想要的，能干活的员工。

每个职位肯定都是有级别，不同级别有不同的工资范围，但是级别只是定义了上下限，拿到上限和下限之间可谓有天渊之别。而且，绝大部分职位，都不会给上限工资，人人都给上限，工资预算肯定超标了。

HR 给你 offer 数字之前，要考虑几个因素:

公司招人有预算，能用低价招到的，就肯定不会出高价
你可能会讨价还价，所以不能直接给上限，要留有提价的余地
如果工资太低，你可能一怒之下就拒了。

6 求职者的手牌

虽然求职者与公司谈判过程中处于相对弱势地位，但是这并不意味着我们完全没有牌可打，所以我们要利用好手上的牌。

6.1 公司内部的助力

说起来可能难以置信，虽然求职者可能与公司的人还毫无联系，但是求职者会在公司内有相当的助力，因为基本上你接触到的公司每个人都是想你接 offer 的.

对于公司来说，在你身上已经花费了相当的成本，HR 筛选简历，安排面试官面试，2-4轮的面试，都要花费面试官与HR时间的，公司付给员工工资，这些时间都是要算钱的。

而一旦你拒绝，这些花费的时间成本都会成为沉没成本。

对于 HR 来说，她们也是有考核指标的，招聘人数也是她们的考核指标，所以她们也有强烈的动机尽快招到人。

而对于招聘你的团队老板来说，肯定是希望赶紧招到人来干活的，工资多少他不关心，反正出的又不是他的钱。

所以这些人都是希望你能接 offer 的潜在助力。

6.2 多拿Offer

拿到多个的 offer，这个会成为你和 HR 谈判的最大底气，你就不会担心谈崩了，这家给不了，了不起去下家；如果多个公司愿意相互竞价，你就能渔翁得利，利益最大化。

对于公司来说，肯定是希望招到能力强，能干活的候选人，但是怎么去量化能力强呢，即便候选人通过了面试，也不能说明他们能力一定能胜任。

但是如果你能通过多个公司的面试，对于HR来说，相当你额外再通过了十几二十轮的面试，从概率来说，你是没能力的候选人的机率大大降低，既然大家都说你好，那么他们就有更强烈的意愿与你洽谈。

6.3 薪资是底牌

上文提到，公司的策略是希望以尽量低的薪资来招到人，那么两个非常重要的参考标准：

一个就是别的公司给你开的工资，另外一个就是你现在的工资,

假如你现在的工资是20W 一年, 那我就只给你加个20%, 最多给加个30%, 既然你20W都愿意干，为什么我要开高价.

所以你现在的薪资就是你的底牌, 千万不要给人看到, 不然就定死上限了。

不然你拿了一次低工资，后面次次跳槽都要拿低工资，凭什么呢？真的是闻者伤心。

所以HR问你的时候，不要正面回答，尽量模糊化，以此争取最大利益。

比如HR换个问法，问你的预期薪资是多少？

这个问题非常坑，相当于给自己划定上限，如果你回答30W, 她就绝对不可能给你40W, 你可以回答说：我心里没个具体数字，但我对任何有竞争力的 offer 持开放态度.

一定要给的话，就给个模糊的范围, 比如阿里P7的水平吧。

7 谈判的手段

7.1 表达强烈的兴趣

“你想加入这家公司"这个前提是一切谈判的基础。

如果你表现出对加入这家公司兴趣寥廖, 那么即使你强如 Linus Torvalds, 也不会有HR会想和你谈薪资的，因为这个注定是不会有结果，她们当然也不会浪费时间。

所以你需要表示出对这家公司有强烈兴趣，无论是文化，工作方式，业务或者技术栈都与你非常契合，而你加入公司目前唯一的障碍就是没有拿到满意的薪资，这样HR才会非常乐意来为你争取。

你总要创造些条件给 HR, 她们才能为你争取更多。

所以无论你是否对这家公司感兴趣，起码你在谈薪资阶段都要表现出强烈的兴趣。

7.2 少说多听

求职者在谈薪资过程中是处于相对弱势的地位的，所以在谈判过程中要多听少说，因为你的底牌不能被她们套出来，说得越多，不经意间漏出来的可能就越大。

而在电话中，当对方HR 试探性给出一个报价后，你都不要太快回应或者表达出来，因为对面的大概率也是谈判的老手，如果你表现得很欣喜, 那么她们就知道这个已经比你的底线要高了.

所以当听到报价之后，你可以适当地保持沉默，表示犹豫，然后让她们进一步加码, 即使她们不加码，你也用沉默表达了对报价的不满意.

7.3 多个公司竞价

如果只向一个公司谈 offer, 最多两轮，可能就到了摊牌的时刻了。

只有能让多个公司竞价，你才能让你的「未来雇主们」卷起来，实现利益最大化, 另外其他公司的报价也可以成为的谈薪资的底价.

比如你工资是20W, 你想要30W, 公司的HR就会挑战你，说你这30W 太高了，他们给不来, 其实也是换种说法说你不值30W.

但是如果A公司给了你30W, 那么你就有底气问 B 公司要高于30W 的薪资, 毕竟这是市场对你的认可.

假设B 公司给了你35W, 那么你就可以回头向A 公司说，你拿到个35W 的offer, 让A公司提高下标准, A 公司可能给到个37W,

然后你再回到 B 公司说:

我真的很想加入贵公司，和你们一起工作，只是A公司给了37W, 着实很为难，我真的很加入你们, 你们可以再匹配一下嘛?

B 如果能给到40W, 再把同样的话和A 说一次, 两家公司工作竞价两次, 就相当于谈了4次了.

如果手握两家以上公司的 offer, 那么这个可以再用到其他公司身上，所以这个就要求你要在差不多的时间拿到全部的 offer.

7.4 不要当场答应

无论 HR 给你的报价多么诱人，又或者这个是你梦寐以求的公司，都不要当场答应下来，万一其他公司给你更好的报价呢，当场答应而后又反悔给人的印象太不好了, 要给自己留有余地。

如果 HR 要你马上给出答案，你也可以这样回应:

我非常珍惜贵公司提供的这个机会，我也非常希望加入贵公司，但是我意识到这个机会会对我的职业生涯产生重大影响，我希望可以和家人商量之后再下决定。

8 总结

几轮谈薪之后, 你可能拿到满意或者仍然不满意的报价，你就可以根据自己的诉求选择公司了。

你不一定会选钱最多的，可能你还会考虑公司前景，职业前景，工作强度等因素，但是起码选择之后你不会因没有为争取更高的收入进行谈判而后悔。

此外，这个可能是你在这家公司最容易调薪的一次了。

一旦你加入公司之后，你就会受限于绩效，级别，部门业绩等各种限制，再也不会有打几通电话, 发几封邮件就能涨薪的美事了。

所以，从这个角度来说，谈薪资的电话可能是你最应该打，且性价比最高的电话(大概率也没有之一)

9 参考

https://www.healthyhacker.com/2019/07/13/more-money-please/ (一个我很喜欢的播客的主持人分享他自己谈薪资的过程)
https://www.1point3acres.com/bbs/thread-286214-1-1.html (一亩三分地版主分享求职如何跟公司讨价还价)
https://podcasts.apple.com/us/podcast/no-477-%E6%88%91%E8%AE%A4%E8%AF%86%E7%9A%84%E6%9C%80%E5%8E%89%E5%AE%B3%E7%9A%84%E5%88%9D%E4%B8%AD%E6%AF%95%E4%B8%9A%E7%94%9F-%E5%8A%AA%E5%8A%9B%E5%B7%A5%E4%BD%9C-%E5%AD%98%E9%92%B1-%E7%95%99%E5%AD%A6-%E8%AF%BB%E4%B9%A6-%E7%BB%A7%E7%BB%AD%E5%8A%AA%E5%8A%9B%E5%B7%A5%E4%BD%9C/id1147186605?i=1000676154793(忽软忽硬电台采访，这位同行在下家要求出具薪资证明的时候，请财务吃饭，直接将工资x2再打印出来，叹为观止)

Ramsay Leung修改