时间戳

首页 > 解决方案 > TS：在描述状态机的类型中不允许循环

typescript - TS：在描述状态机的类型中不允许循环

问题描述

我在我的应用程序中作为状态机实现了一个多步骤过程，并创建了表示可能状态转换的类型：

enum ProcessStep {
  STEP_1,
  STEP_2a,
  STEP_2b,
  STEP_3
}
type ValidNextStep<Step extends ProcessStep> = {
  [ProcessStep.STEP_1]:
    | ProcessStep.STEP_2a
    | ProcessStep.STEP_2b;
  [ProcessStep.STEP_2a]: ProcessStep.STEP_3;
  [ProcessStep.STEP_2b]: ProcessStep.STEP_3;
  [ProcessStep.STEP_3]: never;
}[Step]

但我想知道我是否在这个图中创建了一个循环，即是否ProcessStep.STEP_3可以转换回ProcessStep.STEP_2a.

如何在类型级别建立这种不变量？似乎很难，因为默认情况下类型别名不允许循环引用。

标签： typescriptrecursiontypesdirected-acyclic-graphs

解决方案

哇我喜欢这个问题。我不确定仅使用类型系统是否有一种干净或正确的方法来做到这一点。

这是一种不干净且可能不正确的方法：强制类型系统进行计算，为每个状态启动状态机并运行大量步骤。如果每个可能的结束状态都是never，那么就没有循环。否则，要么有循环，要么你的图中有一些非常长的非循环路径。

M想象一下，您有一个扩展的对象类型Record<keyof M, keyof M>，这意味着 的值M也是 的键M。这描述了一个状态机（你的定义中有这样的类型，ValidNextStep但是你通过索引它来破坏它......别担心，我们可以将它重建为{ [K in ProcessStep]: ValidNextStep<K> }）。对于您的任何键K，M您可以计算M[K]一步，或M[M[K]]两步，或M[M[M[K]]]三步等。

我们可以非常快速地组合这些操作以获得疯狂的步骤数：

type TwoSteps<M extends Record<keyof M, keyof M>> = { [K in keyof M]: M[M[K]] };
type FourSteps<M extends Record<keyof M, keyof M>> = TwoSteps<TwoSteps<M>>;
type SixteenSteps<M extends Record<keyof M, keyof M>> = FourSteps<FourSteps<M>>;
type TwoHundredFiftySixSteps<M extends Record<keyof M, keyof M>> = SixteenSteps<
  SixteenSteps<M>
>;

在没有编译器对我大喊大叫的情况下，这是我所能做到的。

然后，如果检测到循环（或很长的路径），我们可以创建一个导致编译器错误的见证类型：

type NoCycles<
  N extends never = TwoHundredFiftySixSteps<
    { [K in ProcessStep]: ValidNextStep<K> }
  >[ProcessStep]
> = true;

这对于您的原始定义很好ValidNextStep，但是如果我们将其更改为以下内容：

type ValidNextStep<Step extends ProcessStep> = {
  [ProcessStep.STEP_1]: ProcessStep.STEP_2a | ProcessStep.STEP_2b;
  [ProcessStep.STEP_2a]: ProcessStep.STEP_3;
  [ProcessStep.STEP_2b]: ProcessStep.STEP_3;
  [ProcessStep.STEP_3]: ProcessStep.STEP_2a; // oops
}[Step];

然后NoCycles定义产生以下错误：

// Type 'ProcessStep.STEP_2a | ProcessStep.STEP_3' does not satisfy the constraint 'never'.

这表明在机器运行 256 步后，它仍然可能处于STEP_2a或STEP_3，这表示一个循环。

这是一个好主意吗？可能不是......不能保证它是正确的，它可能会给编译器带来比保证更大的压力。但我不知道我有多努力去尝试找到更好的东西。使用通用语言，您会尝试找到一些有效的算法来检测循环，但 TypeScript 中的类型系统不太可能具有足够的表现力来实现它。

因此，使用它需要您自担风险，祝您好运！

链接到代码

推荐阅读