有限状态机入门Finite State Machines

1从一台闸机开始

页面顶部那台闸机就是一个完整的有限状态机。它由四样东西组成：

• 状态（state）：闸机此刻的情况。只有两种：锁定、解锁。任何时刻它只处于其中一种。
• 事件（event）：外界发生的事。只有两种：刷卡、通过。
• 转移（transition）：规则，形式是“在某个状态下遇到某个事件，就变成某个状态”。闸机一共有 4 条。
• 初始状态（initial state）：一开始所处的状态。闸机是锁定。

要判断闸机下一步变成什么，只需要知道两件事：它现在的状态，和刚刚发生的事件。之前刷过多少次卡、过了多少人，都不需要知道。这是状态机最重要的性质：当前状态已经包含了决定下一步所需的全部信息。

“有限”指的是状态的数量有限。闸机有 2 种状态，后面要讲的订单有 7 种，TCP 连接有 11 种，都是有限的。

2五个要素

教科书里的写法更紧凑。一个确定性有限状态机由五样东西组成：

“确定性”的意思是：同一个状态遇到同一个事件，结果只有一个。与它相对的是非确定性有限状态机（NFA），它允许同一个输入有多个去向。两者的能力相同，任何 NFA 都能改写成等价的确定性状态机，只是状态可能变多。写业务代码时用到的几乎都是确定性的。

“转移函数”这个名字值得记住。它是一个纯函数：给它当前状态和事件，它返回下一个状态。第 6 节写代码的时候，整个状态机的核心就是这一个函数。

3状态图和转移表

同一个状态机有两种等价的写法。状态图用圆圈表示状态，用带箭头的线表示转移，线旁边标事件名，适合给人看。转移表把状态排成行、事件排成列，格子里填下一个状态，适合检查，也适合直接写成代码。闸机的转移表是这样的：

状态图有几个通用的画法约定：

• 一个没有起点的箭头，指向初始状态。
• 双层圆圈表示终态。在识别器里它叫接受状态，意思是“停在这里算通过”；在订单这类业务对象里，它表示生命周期到此结束。接受状态之后还可以继续转移，业务对象的终态则没有出去的转移。
• 从一个状态出发又回到它自己的箭头叫自环，表示这个事件不改变状态。

转移表有一个状态图没有的好处：空格子藏不住。闸机有 2 个状态、2 个事件，表格就有 4 个格子，每个格子都要回答“这时候该怎么办”。画图的时候很容易漏掉“锁定时有人硬闯”这种情况，填表的时候漏不掉。

4为什么需要它：三个布尔值的八种组合

不用状态机的代码通常是这样的：用几个布尔变量拼出“现在是什么情况”。以一个加载数据的页面为例：

let isLoading = false;
let isError = false;
let hasData = false;

三个布尔值有 8 种组合，但这个页面真正有意义的情况只有 4 种。拨动下面的开关，看看多出来的那几种是什么。

多出来的组合不会自己消失。每多写一个 if，都要想一想它在这些组合下会不会出错；每次改状态，都要记得把三个变量同时改对。漏掉一次，页面就可能同时显示加载动画和错误提示。

状态机的做法是换一个问题。不问“这三个变量分别是真是假”，而问“页面现在处于哪一种情况”。把有意义的情况一个一个起名字，用一个变量保存：

let status = 'idle'; // 'idle' | 'loading' | 'success' | 'failure'

4 个值对应 4 种情况，不存在不可能的组合。这个思路有一句常被引用的话：让非法状态无法表示（make illegal states unrepresentable）。

5识别器：正则表达式背后的状态机

状态机的一个经典用途，是判断一串输入是否符合某种格式。做法是：从初始状态出发，每读一个字符做一次转移；全部读完之后，如果停在接受状态就接受，否则拒绝。

下面这个状态机识别十进制数：至少一位数字，后面可以跟一个小数点和至少一位数字。按 JavaScript 的正则语义，它和 ^[0-9]+(\.[0-9]+)?$ 接受的字符串完全相同。

有三点值得注意：

• “整数”和“小数”是接受状态，画成双圈。读完 12. 停在“小数点后”，它不是接受状态，所以拒绝：小数点后面还缺数字。
• 右边的“死状态”也叫陷阱状态：一旦进入就出不来，后面读到什么都不会改变结果。
• 状态机不能回头看，也不需要回头看。它不记得读过哪些字符，只记得自己现在在哪个状态。

它和正则表达式的关系

这不是巧合。计算理论里有一个基本结论：能用正则表达式描述的语言，和能用有限状态机识别的语言，是同一批，叫正则语言。把正则表达式编译成状态机再执行，是实现正则引擎的一种经典做法。

现实中的正则引擎做法不完全一样。Go 的 regexp 包、Rust 的 regex 库和 RE2 基于自动机实现，匹配时间与输入长度成线性关系。JavaScript、Python、Java 的引擎使用回溯算法，支持反向引用这类超出正则语言的功能，代价是个别表达式遇到特定输入会非常慢。

它做不到什么

有限状态机的全部记忆就是“现在在哪个状态”，而状态的数量是固定的，所以它没法数任意大的数。判断括号是否配对就做不到：嵌套可以任意深，需要记住还有几个左括号没有闭合，这个数没有上限。这类问题要给状态机加一个栈，叫下推自动机。HTML、JSON 和编程语言的语法都允许任意深的嵌套，至少需要一个栈，所以不能只靠正则表达式来解析。

6写成代码：三种写法

现在把闸机写成代码。不管用哪种写法，核心都是转移函数：输入当前状态和事件，返回下一个状态。

写法一：switch

function transition(state, event) {
  switch (state) {
    case 'locked':
      return event === 'CARD' ? 'unlocked' : 'locked';
    case 'unlocked':
      return event === 'PASS' ? 'locked' : 'unlocked';
    default:
      throw new Error(`Unknown state: ${state}`);
  }
}

这种写法直接，适合状态很少的情况。缺点是规则散在控制流里，状态一多就很难一眼看全，也没有办法把规则拿出来画图或者生成文档。

写法二：转移表

const turnstile = {
  initial: 'locked',
  states: {
    locked:   { CARD: 'unlocked', PASS: 'locked' },
    unlocked: { CARD: 'unlocked', PASS: 'locked' },
  },
};

function transition(machine, state, event) {
  // An event with no entry leaves the state unchanged.
  return machine.states[state][event] ?? state;
}

let state = turnstile.initial;                // 'locked'
state = transition(turnstile, state, 'CARD'); // 'unlocked'
state = transition(turnstile, state, 'PASS'); // 'locked'

规则变成了一份数据。转移函数只有一行，而且不会随着状态机变复杂而变长。这份数据可以直接画成状态图、渲染成表格，也可以遍历出所有路径来写测试。这个页面上闸机、识别器和订单的状态图和转移表，都是从这样的数据生成的。

注意 transition 是一个纯函数：它不修改任何东西，只返回新的状态。把 machine 固定下来之后，它的形状就是 (state, event) => state，和 React 的 useReducer、Redux 的 reducer 一样。会写 reducer，就已经会写状态机的核心了。Redux 把这里的事件叫 action，它和第 7 节要讲的“动作”不是一回事。

写法三：让类型系统帮忙检查

状态经常要带数据：成功的时候有结果，失败的时候有错误信息。在 TypeScript 里，可以用可辨识联合（discriminated union）把每种状态和它的数据绑在一起：

type FetchState =
  | { status: 'idle' }
  | { status: 'loading' }
  | { status: 'success'; data: string[] }
  | { status: 'failure'; error: string };

type FetchEvent =
  | { type: 'FETCH' }
  | { type: 'RESOLVE'; data: string[] }
  | { type: 'REJECT'; error: string }
  | { type: 'RETRY' };

function reduce(state: FetchState, event: FetchEvent): FetchState {
  switch (state.status) {
    case 'idle':
      return event.type === 'FETCH' ? { status: 'loading' } : state;
    case 'loading':
      if (event.type === 'RESOLVE') return { status: 'success', data: event.data };
      if (event.type === 'REJECT') return { status: 'failure', error: event.error };
      return state;
    case 'failure':
      return event.type === 'RETRY' ? { status: 'loading' } : state;
    case 'success':
      return state;
  }
}

这样写有两个好处。data 只存在于 success 状态，在其它状态下访问它，编译不过。开启 strict 时，switch 漏掉一个状态，编译器也会报错，因为函数有一条路径没有返回值。第 4 节说的那些不可能的组合，在这里连写都写不出来。

7动作、守卫和上下文

到现在为止，状态机只会变状态。真实的程序还要做事：发请求、写数据库、更新界面。状态机把这些叫动作（action），并且规定了它们挂在什么地方：

• 转移动作：发生某一次转移的时候执行。
• 进入动作（entry）和退出动作（exit）：进入或者离开某个状态的时候执行，不管是从哪条转移来的。

第二个概念是守卫（guard）：给转移加一个条件，条件成立才允许这次转移。

第三个是上下文（context），也叫扩展状态：状态之外的数据，比如已经重试了几次。如果把“重试了 0 次、1 次、2 次、3 次”都画成独立的状态，图会迅速膨胀。把次数放进上下文，状态图保持不变，由守卫去读它。

下面是一个带重试的请求：失败之后可以重试，最多三次。

const fetchMachine = {
  initial: 'idle',
  context: { retries: 0 },
  states: {
    idle: {
      on: { FETCH: { target: 'loading' } },
    },
    loading: {
      entry: 'startRequest',
      on: {
        RESOLVE: { target: 'success' },
        REJECT: { target: 'failure' },
      },
    },
    failure: {
      on: {
        RETRY: {
          target: 'loading',
          guard: context => context.retries < 3,
          update: context => ({ retries: context.retries + 1 }),
        },
      },
    },
    success: {},
  },
};

// Returns the next snapshot and the names of the actions the caller should run.
function send(machine, snapshot, event) {
  const rule = machine.states[snapshot.state].on?.[event];
  const allowed = rule && (!rule.guard || rule.guard(snapshot.context));
  if (!allowed) return { ...snapshot, actions: [] };

  const context = rule.update ? rule.update(snapshot.context) : snapshot.context;
  const entry = machine.states[rule.target].entry;
  return { state: rule.target, context, actions: entry ? [entry] : [] };
}

let snapshot = { state: fetchMachine.initial, context: fetchMachine.context };
snapshot = send(fetchMachine, snapshot, 'FETCH');  // loading, actions: ['startRequest']
snapshot = send(fetchMachine, snapshot, 'REJECT'); // failure
snapshot = send(fetchMachine, snapshot, 'RETRY');  // loading, retries: 1

分工很清楚：状态回答“现在处于哪种情况”，上下文保存数量和内容，守卫决定能不能走，动作负责做事。send 本身仍然是纯函数，它不执行动作，只把该执行的动作名交还给调用方。副作用被限制在动作里，转移规则就仍然是一份可以检查的数据。

8实战：订单状态机

把这些放到一个常见的业务对象上。一张订单从创建到结束有 7 种状态，可能发生 6 种事件。下面的按钮在任何状态下都可以点，试试在不合适的时候点会怎样。

可以看到几件事：

• 非法操作不需要到处写 if 去防。“已发货的订单不能再支付”不是某个接口里的一行判断，而是转移表里一个写着“没有转移”的格子。
• 双圈的 3 个状态是终态，没有任何出去的转移，订单的生命周期到此结束。
• “申请退款”从两个状态出发，都到“退款中”。同一个事件在不同状态下可以去同一个地方，也可以去不同的地方，或者根本不被接受。
• 事件不一定来自用户的点击。支付平台的回调、定时任务发现订单超时未支付，也都是事件。

放到后端时有一个实用的做法：状态存成一个字段，所有修改都经过转移函数，更新数据库时把“当前状态必须是我以为的那个”作为条件。两个请求同时到达时，只有一个能成功。

UPDATE orders SET status = 'shipped'
WHERE id = 42 AND status = 'paid';
-- 0 rows affected: another request moved the order first.

9状态多了怎么办：层次和并行

扁平的状态机有一个著名的问题，叫状态爆炸。如果一个系统有两组互不相干的情况，比如播放器的“播放 / 暂停”和“有声 / 静音”，扁平的画法要把它们两两组合：2 × 2 = 4 个状态。再加一组“窗口 / 全屏”，就是 8 个。每多一组这样的二选一，状态数就翻一倍，转移线增加得更快。

1987 年，David Harel 提出了 Statecharts，给状态机加了几样东西来解决这个问题。今天的 UML 状态机图和 XState 这类库都源自它。

• 层次（嵌套状态）：一个状态里面可以再包含一个子状态机。定义在父状态上的转移，对所有子状态都有效。
• 并行状态：几组互相独立的子状态机同时运行，各管各的。两组分别有 3 个和 4 个状态时，扁平的画法需要 12 个状态，并行的画法只要 7 个。
• 历史状态：离开一个父状态再回来时，回到上次离开时所在的子状态。

下面用一个播放器对比层次的效果。播放器开机后有停止、播放、暂停三个状态，任何时候都可以关机。

用库来写是这个样子，下面是 XState 第 5 版的写法：

import { createMachine, createActor } from 'xstate';

const player = createMachine({
  id: 'player',
  initial: 'on',
  states: {
    on: {
      initial: 'stopped',
      on: { POWER: 'off' }, // one rule covers every child state
      states: {
        stopped: { on: { PLAY: 'playing' } },
        playing: { on: { PAUSE: 'paused', STOP: 'stopped' } },
        paused: { on: { PLAY: 'playing' } },
      },
    },
    off: { type: 'final' },
  },
});

const actor = createActor(player).start();
actor.send({ type: 'PLAY' });
console.log(actor.getSnapshot().value); // { on: 'playing' }
actor.send({ type: 'POWER' });
console.log(actor.getSnapshot().value); // 'off'

不必一开始就用库。几个状态、十来条转移，一张转移表加一个二十行的函数就够了。等你发现自己在手写嵌套、并行或者延时转移的时候，再换成库。

10什么时候用，什么时候不用

适合用的情况

• 对象有明确的生命周期：订单、工单、审批流、订阅、网络连接。
• 界面有几种互斥的模式：加载中、成功、失败；表单的编辑中、提交中、已提交；多步向导。
• 协议和解析：按顺序处理输入，前面的输入决定后面的输入怎么解释。
• 代码里出现了几个互相制约的布尔标志。

不适合用的情况

• 没有模式之分的纯数据。一个计数器、一个列表，直接存值就行。
• 情况的数量随数据增长。“购物车里有 n 件商品”不应该是 n 个状态，数量应当放进上下文。
• 需要无限记忆的识别问题。嵌套结构要用栈或者解析器。

常见误区

误区：状态机就是一个 status 字段

字段只是存储。状态机还包括“哪些转移是允许的”这张表。没有这张表，任何代码都可以把字段改成任何值。

误区：状态分得越细越好

状态只用来区分行为不同的情况。数量、内容这类数据放进上下文。

误区：事件就是“把状态设成某个值”

事件描述发生了什么，比如“支付成功”，而不是命令状态机变成什么。接下来去哪儿，由转移表决定。

误区：非法操作在界面上把按钮禁用就行了

界面只是入口之一。回调、重试、并发请求都会绕过界面，规则要守在转移函数里。

误区：用了状态机就不会有 bug

它保证的是程序只走画出来的路径。路径本身画错了，它不管。

11小测验

九道选择题，点选项立刻看到答案和解释。

1. 小测验需要启用 JavaScript 才能作答。

附术语表与下一步

没有匹配的术语。换一个关键词试试。

下一步

• 挑手头一个布尔标志很多的组件，或者一张带 status 字段的表，给它画一张转移表，看看有几个格子是没有人想过的。
• 读 XState 文档里介绍状态机和 Statecharts 的部分，或者 Harel 1987 年的论文 Statecharts: A Visual Formalism for Complex Systems。
• 想深入理论，可以读 Sipser 的《计算理论导引》第 1 章，讲有限自动机和正则语言。