How get a union of descendant names with a recursive generic type?-CodePudding

I have a type object of nodes, many of which specify other nodes as children. For example:

type Nodes = {
  a: {
    children: ["b"]
  },
  b: {
    children: ["c"]
  },
  c: {
    children: []
  }
}

I'm trying to create a generic type, something like type DescendantName<T extends keyof Nodes> = ... that produces a union of the descendant names of Nodes[T], such that DescendantName<"a"> produces "b" | "c".

I tried a straightforward recursive syntax but got a circularity type error:

type DescendantName<T extends keyof Nodes> = Nodes[T]["children"][number] | DescendantName<Nodes[T]["children"][number]>
// Type alias 'DescendantName' circularly references itself. ts(2456)

Can anyone tell me how to make a working generic type like this?

CodePudding user response：

I was able to get the following to work. I think the key is making sure to only do the recursive call if the child node type is a key of Nodes.

Here's the playground link.

type Nodes = {
  a: {
    children: ["b"]
  },
  b: {
    children: ["c"]
  },
  c: {
    children: []
  }
}

type DescendantName<T extends keyof Nodes> = Nodes[T]["children"][number] | ChildNodes<Nodes[T]["children"][number]>;
type ChildNodes<T> = T extends keyof Nodes ? DescendantName<T> : never;

const test: DescendantName<"a"> = "b"

CodePudding user response：

Here is the one-liner version

type DescendantName<T extends keyof Nodes> = Nodes[T]["children"][number] extends never 
    ? never 
    : Nodes[T]["children"][number] | DescendantName<Nodes[T]["children"][number]>

Typescript Playground Link

There are a few other "Features" to this implementation that may or may not be what you are looking for:

It will throw an error if there is an invalid child node in children

type Nodes = {
  a: {
    children: ["b"]
  },
  b: {
    children: ["c"]
  },
  c: {
    children: ["d"] // "d" is not in Nodes
  }
}

type DescendantName<T extends keyof Nodes> = Nodes[T]["children"][number] extends never 
    ? never 
    : Nodes[T]["children"][number] | DescendantName<Nodes[T]["children"][number]>
// Type 'Nodes[T]["children"][number]' does not satisfy the constraint 'keyof Nodes'.
//   Type '"b" | "c" | "d"' is not assignable to type 'keyof Nodes'.
//     Type '"d"' is not assignable to type 'keyof Nodes'.(2344)

It will also throw an error if there is a loop

type Nodes = {
  a: {
    children: ["b"]
  },
  b: {
    children: ["c"]
  },
  c: {
    children: ["a"] // a -> b -> c -> a -> and so on...
  }
}

type DescendantName<T extends keyof Nodes> = Nodes[T]["children"][number] extends never 
    ? never 
    : Nodes[T]["children"][number] | DescendantName<Nodes[T]["children"][number]>


type AllDecendantNames = DescendantName<"a">
// Type instantiation is excessively deep and possibly infinite.(2589)