Type instantiation is excessively deep with PartialRecursive & recursive list type

[idoros]

TypeScript Version: 3.7.2 (and nightly/next)

Search Terms:

• Type instantiation is excessively deep and possibly infinite

Code

type Json =
    | string
    | number
    | boolean
    | null
    | { [property: string]: Json } // recursive  object doesn't cause any issues
    | Json[] // removing the list option resolves the issue

type PartialRecursive<T> = T extends object
    ? { [K in keyof T]?: PartialRecursive<T[K]> }
    : T

interface Data {
    value: Json
}

function acceptData(param: PartialRecursive<Data>) {}

const data = {} as Data
acceptData(data) // error TS2589: Type instantiation is excessively deep and possibly infinite.

Expected behavior:
Value field should be valid as both the type itself is already inferred as the Data type and the entire type is optional

Actual behavior:
The recursive list type causes an infinite (or excessive) calculation that fails.

Playground Link:

• 3.7.2
• nightly
• recursive list vs object

Related Issues:

• “Type instantiation is excessively deep and possibly infinite” but only in a large codebase #34933
• 3.6 regression: error TS2321: Excessive stack depth comparing types 'Function<?>' and 'Function<?>'. #33132

[jcalz]

Related: #33050, which introduced the ability to write type Json = ... | Json[] instead of requiring an intervening interface like type Json = ... | JsonArray; interface JsonArray extends Array<Json> {}.

[idoros]

Looking at this some more I noticed that the problem is in my own (probably copied from somewhere) PartialRecursive type that doesn't handle Array types.

This fixes my case:

type PartialRecursive<T> = T extends object
    ? T extends Array<infer U> ? PartialRecursive<U>[]
    : { [K in keyof T]?: PartialRecursive<T[K]> }
    : T

[jcalz]

I wouldn't be so quick to dismiss this; since TypeScript 3.1, mapped array/tuple types have been supported so you shouldn't have to special-case arrays like that. Indeed, the pre-TS-3.7 way of typing Json does not have this problem with your original PartialRecursive:

type Json =
    | string
    | number
    | boolean
    | null
    | { [property: string]: Json }
    | JsonArray

interface JsonArray extends Array<Json> {}

type PartialRecursive<T> = T extends object
    ? { [K in keyof T]?: PartialRecursive<T[K]> }
    : T

interface Data {
    value: Json
}

function acceptData(param: PartialRecursive<Data>) {}

const data = {} as Data
acceptData(data) // no error

Playground link

So whatever's going on here isn't what I'd call a problem with recursive mapped types. I don't know if this is a compiler bug / design limitation / working as intended, but I'm still interested in seeing what an official word here would be.

[idoros]

Re-opening, feel free to close if this works as expected

[ahejlsberg]

This is effectively a design limitation.

When a homomorphic mapped type is applied to an array type, we obtain the element type of the array and apply the mapped type's template type to that. This is done eagerly, which effectively causes a circularity when the type being mapped is itself circular.

As mentioned above, the original example works when an array case is added to the conditional type:

type PartialRecursive<T> = 
    T extends (infer U)[] ? PartialRecursive<U>[] :
    T extends object ? { [K in keyof T]?: PartialRecursive<T[K]> } :
    T;

Here, PartialRecursive<U>[] is represented internally as a deferred type reference, and this saves us from the eager circularity problem. We could consider doing something similar for the case of applying a mapped type to an array type, but I don't think it is super important given that we have a very reasonable workaround.