Создать тип кортежа, представляющий объединение путей через рекурсивную структуру объекта

Question

Ниже приведена пара шаблонных бизнес-типов, разработанных для представления составных и атомарных состояний c соответственно.

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>;

В моем приложении эти типы будут составлены для создания древовидных структур соединения и атома c состояний. Вот пример такого типа:

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

Что я хотел бы сделать sh, так это создать объединение кортежей для представления возможных «путей», подразумеваемых типом MyStateChart. Возможные пути - это кортежи, такие как:

1. ['cs0'] - допустимый путь для CompoundState может проходить или не проходить в потомки.
2. ['cs0', 'cs1'] - То же, что и выше, нам не «нужно» перемещаться к конечным узлам.
3. ['cs0', 'cs1', 'as1'] - Полная глубина
4. ['cs0', 'cs1', 'as2'] - Полная глубина

В (в основном Неудачная попытка достичь этого, я выбрал два подхода:

Подход 1:

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>;

Это создает тип, который действительно близок к тому, что я хочу, но я не могу 'flatten':

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

Подход 2:

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 в своем комментарии , эта проблема решается тем же подходом, что и ответ на этот вопрос .

Вот что это выглядит как примененный к упомянутой проблеме:

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"]