3.335. 状态机设计

name: state-machine-design description: 设计和实现状态机的方法

这个skill指导如何设计和实现的状态机，包括在设计中如何判断是否应该用状态机解决问题。它用于你决定要设计或者实现一个状态机的时候，决定是否继续推理下去，并在推理的时候构建完整的推理模型，并在编码的时候无遗漏地实现被推理的模型。

3.335.1. 什么时候使用状态机

如果你的设计清晰地反映出输入有限类别的刺激，改变内部有限的状态，根据每种不同的内部状态，而系统的响应根据内部状态的不同，使用独立的处理逻辑。这个设计就值得使用状态机进行建模和编码。

如果系统的响应可以被简单的计算过程描述，只是参数的不同，则不应该使用状态机建模。

如果最终推理出来，状态只有两个，请考虑这是否只是个开关：如果可以明确把刺激分成“开关”和“其他请求”两类，如果可以，这就是一个开关，不需要做状态机建模。

比如外部刺激是a，内部状态是x，应激等于f(a, x)，这不需要状态机建模。广义上x也是一种内部状态，但这种状态只是某种固定范式的参数，这不需要状态机建模去处理。只有内部状态有限，而且每种状态需要不同的处理范式的时候，才需要进行状态机管理。比如：:

switch(x):
case 1 -> f(a)
case 2 -> g(a)
case 3 -> h(a)

这时，内部状态x只有有限的状态（1, 2, 3），输出则需要完全不同的算法（f, g, h），这种情况才需要使用状态机建模。

定义状态机首先必须明确定义如下三个要素：

这三者的数量都应该有限，否则状态机就没有意义了，状态机设计和推理的目的，都是为了减少和穷举这三者的组合可能性。如果可能性空间大到我们无法穷举的程度，状态机建模就失败了。

如前所述，计算机系统，比如程序，内部包含了无数的存储装置，这些都可以认为是一种状态，但当我们进行状态机建模的时候，我们只建模其中关键的切面，主要为了区分程序分支，如果某个变量在任何情况下都用同一个处理范式，这些变量就不是状态机建模的状态，而是处理范式中的一个变量。

在定义状态，外部刺激和内部响应列表后，我们应该穷举在每个状态下，在所有外部刺激造成的两个后果：

请注意这里的核心是“穷举”，任何状态，我们都必须推理在任何刺激下的后果。即使这种响应是“拒绝”，因为拒绝也是一种后果：这个后果新的状态是新的状态，而响应是“拒绝”或者“无响应”。完成所有可能性的穷举，才完成一个状态机的定义和推理。

状态机可以通过状态变迁图进行表述，也可以把异常处理一类的迁移独立用列表表述。但这些都是描述上的增强，不改变状态机推理的核心方法。

建模状态机进行建模最终就是为了校验我们有没有少考虑什么情况进行处理。在使用状态机前，要校验状态机的如下方面：

在任何一个状态上，是否已经定义任何一种刺激的响应。这些定义不一定都在状态变迁图上。比如我们可能定义“任何状态遇到复位消息都恢复到初始状态，并记录日志”，这里实际上定义了所有状态对于“复位消息”，都迁移到“原始状态”，并产生“记录日志”这个响应。这成组定义了某类刺激的响应。这也是一种定义，不能认为状态变迁图中没有描述就是没有了。
如果某些状态切换条件，总和另一个状态变量结合才能做出判断，那么这里必然发生了状态交织，必须合并这两个状态，重新推理整个状态机。否则，这个状态机肯定没有实现穷举，建模也失败了。
结合具体功能判断，状态机是否有可能在某种刺激组合之下，陷入某个无法恢复的状态，导致系统功能失效。
穷举的规范产物是**状态×刺激矩阵**：每个状态占一行，每种刺激占一列，每个格子写明“新状态 / 响应 / 非法→复位”。状态变迁图只是这个矩阵的可视化，不能替代矩阵做穷举校验——图天然倾向于只画“主要”迁移，会漏掉自环、非法集和复位，而矩阵里的空格一眼可见。穷举校验时应该对照矩阵逐格核对，而不是盯着变迁图。

如果校验失败，应该重新建模状态机，或者告知用户校验出来的问题，在取得一致才能继续下去。

在把状态机实现为代码，要注意如下要素：

如果可能，尽量使用唯一的变量表示状态，变量在用于状态机切换判断的时候，只能取状态机建模时定义的有限状态
每次进行状态切换都要和状态机建模的穷举进行动态对比，发现不在建模中的切换，要有手段进行报告。
实现的时候要保证所有状态迁移，响应构成一个有序的线索。也就是说，不能正在做某个响应或者切换的时候，接收新的外部刺激。这可以通过单线程处理刺激检查，响应和切换实现，或者通过锁或者原子操作避免多线程的行为并行化。

一个代码实现可能包含多个独立的状态机，但通常我们主要建模核心状态机，而其他状态机或者和核心状态机正交，或者是核心状态机的子状态机，用于主状态机的某个状态下的独立切换管理。