Typescript infinite recursion reasoning

Question

Check this typescript 4.2 snippet I found somewhere (playground here):

type BlackMagic<T> = { [K in keyof T]: BlackMagic<T[K]> }

declare const foo: BlackMagic<{q: string}>;
declare const str: BlackMagic<string>;
declare const num: BlackMagic<12>;

I can't wrap my head around it. How does TS handle this? How is it not stuck in an infinite recursion? Specifically, in the case of str and num, hovering over the variables shows that TS is resolving the types to just string and 12. How's that even happening?

Answer 1

You would get stuck in an infinite recursion if your type included BlackMagic<T> with the same T, but here we are applying the utility type BlackMagic to a different value T[K].

type BlackMagic<T> = { [K in keyof T]: BlackMagic<T[K]> }

This type says that BlackMagic<T> is an object where the keys are the keys of T and the values are a BlackMagic mapped version of the values of T.

---

The BlackMagic type doesn't actually do anything in your examples your examples str and num.

If T is a primitive type instead of an object then BlackMagic<T> is just T itself. This is the standard behavior for utility types which are mapped types. For example Partial<12> is just 12. This behavior is explained in the FAQ Common "Bugs" That Aren't Bugs

Mapped types declared as { [ K in keyof T ]: U } where T is a type parameter are known as homomorphic mapped types, which means that the mapped type is a structure preserving function of T. When type parameter T is instantiated with a primitive type the mapped type evaluates to the same primitive.

---

foo: BlackMagic<{q: string}> will actually do some mapping, but it's only one level deep. BlackMagic<{q: string}> becomes {q: BlackMagic<string>}. We just saw that BlackMagic<string> is string, so the type next becomes {q: string}.

Answer 2

As Linda explains, the reason why there's no infinite recursion is that when a homomorphic mapped type is applied to a primitive type it evaluates to that primitive type. Still, it's interesting to see what happens with a non-homomorphic mapped type. To define a non-homomorphic type, you can declare an identity type I such that I<'key1' | 'key2'> = 'key1' | 'key2', using a conditional type:

type I<T> = T extends infer S ? S : T

By taking the keys from I<keyof T> instead of keyof T, you can define a simple non-recursive and non-homomorphic type:

type NonHomomorphicMap<T> = {[K in I<keyof T>]: 42}

and apply it to a bunch of other types:

type TestObject = NonHomomorphicMap<{q: string}> // {q: 42}
type TestString = NonHomomorphicMap<string>      // {[x: number]: 42, toString: 42, charAt: 42, ...}
type TestNum = NonHomomorphicMap<12>             // {toString: 42, toFixed: 42, toExponential: 42, toPrecision: 42, valueOf: 42, toLocaleString: 42}
type TestFun = NonHomomorphicMap<() => number>   // {}

For string and 12 the type now evaluates to an object type with keys for all the methods on string and number, and an [x: number] index signature for string.

Interestingly, functions are not treated as primitive types, but as objects without keys, so NonHomomorphicMap<() => any> equals {}. This also happens with homomorphic mapped types (i.e. BlackMagic<() => any> equals {}), so BlackMagic is not identity.

It's also possible to make a recursive non-homomorphic type similar to BlackMagic, but to see the full type on hover you need a Normalize type that fully evaluates all recursive occurrences:

type Normalize<T> =
  T extends Function
  ? T
  : T extends infer S ? {[K in keyof S]: S[K]} : never

Now a non-homomorphic BlackMagic counterpart can be defined as:

type BadMagic<T> = Normalize<{
    [K in I<keyof T>]: K extends keyof T ? BadMagic<T[K]> : never
}>

Besides using Normalize and I, there's also an extra conditional K extends keyof T as TypeScript can't infer that the result of applying I can still index T. This does not affect the behavior though.

Applying BadMagic to the sample types yields

type TestObject = BadMagic<{q: string}> // {q: {[x: number]: {[x: number]: BadMagic<string>,...}, toString: {}, charAt: {}, ...}}
type TestString = BadMagic<string>      // {[x: number]: {[x: number]: {[x: number]: BadMagic<string>, ...}, toString: {}, charAt: {}, ...}, toString: {}, charAt: {}, ...}
type TestNum = BadMagic<12>             // {toString: {}, toFixed: {}, toExponential: {}, toPrecision: {}, valueOf: {}, toLocaleString: {}}
type TestFun = BadMagic<() => any>      // {}

Most of the recursion ends at methods that turn into {}, but if you look at BadMagic<string> you can see there is in fact some "infinite" recursion, as the [x: number] property on strings is itself a string. Basically, you have

BadMagic<string> = {
  [x: number]: {
    [x: number]: {
      [x: number]: BadMagic<string>, // "infinite"
      ...
    },
    ...
  },
  toString: {},
  charAt: {},
  ...
}

TypeScript playground