Produce tuple type representing the union of paths through a recursive object structure

Question

Below are a couple of templated 'business' types designed to represent compound and atomic states, respectively.

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

In my application, these types will be composed to produce tree-like structures of compound and atomic states. Here is an example of such a type:

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

What I would like to accomplish is to produce a union of tuples to represent possible 'paths' implied by the type MyStateChart. Possible paths are tuples such as:

['cs0'] - A valid path for a CompoundState may or may not traverse into children.
['cs0', 'cs1'] - Same as above, we don't 'need' to traverse to leaf nodes.
['cs0', 'cs1', 'as1'] - Full depth
['cs0', 'cs1', 'as2'] - Full depth

In a (mostly) failed attempt at achieving this, I took two approaches:

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

This produces a type like which is really close to what I want but that I'm unable to 'flatten':

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

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

This approach appears to be unbounded and the TypeScript compiler complains with:

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

Can I achieve what I'm looking for? If so how?

TypeScript Playground

Possible duplicate of [Typescript: deep keyof of a nested object](https://stackoverflow.com/questions/58434389/typescript-deep-keyof-of-a-nested-object) — jcalz, Apr 27 '20 at 13:38
@jcalz you're absolutely right! Thank you so much for linking that. I'm not super versed in proper SO practice, but I will attempt to post an answer based on the linked post. — Geoff Goodman, Apr 27 '20 at 13:49
@jcalz any ideas what the same question would look like if instead of children being a mapped object, they were simply defines as a union type? — Geoff Goodman, Apr 27 '20 at 14:47
As in `TChildren extends AnyCompoundState | AnyAtomicState`? Then I'd write `type ToObj = { [K in T['name']]: Extract extends CompoundState ? ToObj ~~: never };` and then `Paths>`. I'd be happy to write up an answer somewhere for delicious internet points, if you can point me to an actual question (since this one is not using a union)~~ — jcalz, Apr 27 '20 at 15:23

score 2 · Accepted Answer · answered Apr 27 '20 at 13:52

As pointed out by @jcalz in his comment, this problem is solved by the same approach taken in the answer for this question.

Here's what it looks like applied to the mentioned problem:

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

Produces the following type:

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

Produce tuple type representing the union of paths through a recursive object structure

1 Answers1