typescript - 通过递归对象结构生成表示路径联合的元组类型

Question

下面是几个模板化的“业务”类型，分别用于表示复合状态和原子状态。

interface CompoundState<TName extends string, TChildren extends { [key: string]: AnyCompoundState | AnyAtomicState }> {
  type: 'parent'
  name: TName,
  children: TChildren,
};

type AnyCompoundState = CompoundState<string, { [key: string]: AnyCompoundState | AnyAtomicState }>;

interface AtomicState<TName extends string> {
  type: 'child',
  name: TName,
}

type AnyAtomicState = AtomicState<string>;

在我的应用程序中，这些类型将被组合以产生复合和原子状态的树状结构。这是此类类型的示例:

type MyStateChart = CompoundState<'cs0', {
  cs1: CompoundState<'cs1', {
    as1: AtomicState<'as1'>,
    as2: AtomicState<'as2'>,
  }>
}>;

我想要完成的是生成一个元组联合来表示 MyStateChart 类型隐含的可能“路径”。可能的路径是元组，例如:

1. ['cs0'] - CompoundState 的有效路径可能遍历也可能不遍历子代。
2. ['cs0', 'cs1'] - 同上，我们“不需要”遍历到叶节点。
3. ['cs0', 'cs1', 'as1'] - 全深度
4. ['cs0', 'cs1', 'as2'] - 全深度

在一次(大部分)失败的尝试中，我采用了两种方法:

方法一:

type PathA<TNode extends AnyCompoundState | AnyAtomicState> = TNode extends AnyCompoundState
  ? {
    [K in keyof TNode['children']]: [TNode['name']] | [TNode['name'], PathA<TNode['children'][K]>]
  }[keyof TNode['children']]
  : [TNode['name']]

// Produces a type represented by nested tuple unions. I have been unable to 'flatten' this into distinct, fully-realized tuples
type TestPathA = PathA<MyStateChart>;

这会产生一个非常接近我想要但我无法“展平”的类型:

type TestPathA = ["cs0"] | ["cs0", ["cs1"] | ["cs1", ["l1"]] | ["cs1", ["l2"]]]

方法二:

type Cons<H, T extends unknown[]> = ((h: H, ...tail: T) => unknown) extends ((...args: infer U) => unknown) ? U : never;

// Approach B: Approach that I hoped would work but complains with:
type PathB<TNode extends AnyCompoundState | AnyAtomicState> = TNode extends AnyCompoundState
  ? {
    [K in keyof TNode['children']]: [TNode['name']] | Cons<TNode['name'], PathB<TNode['children'][K]>>
  }[keyof TNode['children']]
  : [TNode['name']]

type TestPathB = PathB<MyStateChart>;

这种方法似乎是无界的，TypeScript 编译器会提示:

"Type instantiation is excessively deep and possibly infinite.(2589)"

我能实现我想要的吗？如果是怎么办？

---

TypeScript Playground

Answer 1

正如@jcalz 在 his comment 中指出的那样，此问题已通过 the answer for this question 中采用的相同方法解决。 .

下面是它应用于上述问题的样子:

type Cons<H, T> = T extends readonly any[] ?
  ((h: H, ...t: T) => void) extends ((...r: infer R) => void) ? R : never
  : never;

type Prev = [never, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
  11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...0[]]

type Paths<T extends AnyAtomicState | AnyCompoundState, D extends number = 10> = [D] extends [never] ? never : T extends AnyCompoundState ?
  { [K in keyof T['children']]-?: [T['name']] | (Paths<T['children'][K], Prev[D]> extends infer P ?
    P extends [] ? never : Cons<T['name'], P> : never
  ) }[keyof T['children']]
  : [T['name']];

type TestC = Paths<MyStateChart>;

产生以下类型:

type TestC = ["cs0"] | ["cs0", "cs1"] | ["cs0", "cs1", "l1"] | ["cs0", "cs1", "l2"]