How to prevent a recursive conditional from being infinite in TypeScript?

user_154765 0
Viewed 130

I'm looking to model a tree of nodes in TypeScript, where some are "element" nodes and some are "text" nodes (like in the DOM). This can be expressed as:

type Text = { text: string }
type Element = { children: Node[] }
type Node = Element | Text

And then I'm trying to write a TypeScript utility that can get the types of any potential descendant nodes that occur in the tree. Which I can write as:

type Descendants<N extends Node> = N extends { children: Array<infer T> } 
    ? T extends Node 
        ? T | Descendants<T> 
        : never 
    : never

Given a set of custom nodes:

type Paragraph = { children: Text[] }
type Quote = { children: Paragraph[] }

All of these work:

Descendants<Quote>     // Text | Paragraph
Descendants<Paragraph> // Text
Descendants<Text>      // never

But these both fail:

Descendants<Element>
// Type instantiation is excessively deep and possibly infinite. (2589)

Descendants<Node>
// Type instantiation is excessively deep and possibly infinite. (2589)

Ideally it should return Element | Text.

I understand that TypeScript errors out because it thinks it's recursing infinitely. But is there a way to write this helper such that it works with the generic Element (or Node) types still?

Here is a TypeScript Playground link.

typescript
1 Answers

If you add a type parameter Visited to represent the union of already visited types, you can use an extra conditional to avoid traversing those types:

type DescendantsPrim<Visited, N extends Node> =
  N extends { children: Array<infer T> } 
  ? T extends Node 
    ? T extends Visited
      ? never 
      : T | DescendantsPrim<Visited | T, T> 
    : never 
  : never

For the definition of Descendents you can use never for the Visited parameter as it is the neutral element of | (i.e. T | never = T):

type Descendants<N extends Node> = DescendantsPrim<never, N>

This will infer the following types:

type A = Descendants<Quote>     // Paragraph | Text
type B = Descendants<Paragraph> // { text: string }
type C = Descendants<Text>      // never
type D = Descendants<Element>   // Element | Text
type E = Descendants<Node>      // Element | Text

TypeScript playground

user_57701320
Related