Homomorphic mapped types with arrays doesn't work well with recursive arrays

[juhort]

Acknowledgement

• I acknowledge that issues using this template may be closed without further explanation at the maintainer's discretion.

Comment

Consider this homomorphic mapped type:

type DeepReadonly<T> = { readonly [P in keyof T]: DeepReadonly<T[P]> };

Now, consider its instantiation with a recursive type:

type StringNode = string | { node: StringNode };

type T1 = DeepReadonly<StringNode>;
//   ^? type T1 = string | DeepReadonly<{ node: StringNode; }>

const t1: T1 = { node: { node: 'A' } };

Everything works fine. Playground: https://tsplay.dev/wRDrQm.

However, if the type is instantiated with an array, I start getting "Type instantiation is excessively deep and possibly infinite" error.

type StringNode = string | StringNode[];

type T1 = DeepReadonly<StringNode>;
// errors

Updating the implementation to this makes the error go away, but this doesn't work with tuples.

type DeepReadonly<T> =
  T extends ReadonlyArray<infer V>
    ? ReadonlyArray<DeepReadonly<V>>
    : { readonly [P in keyof T]: DeepReadonly<T[P]> };

type StringNode = string | StringNode[];

type T1 = DeepReadonly<StringNode>;

const t1: T1 = [['foo']];

type StringNodeTuple = string | [StringNodeTuple];

type T2 = DeepReadonly<StringNode>;

const t2: T2 = [['foo', 'bar']]; // doesn't error

If the mapped type works with objects it should have worked with arrays as well. Is there something that I am missing?

[Benjamin-Dobell]

The homomorphism isn't useful for arrays, so another work-around is:

type DeepReadonly<T> = { readonly [P in (string | number | symbol) & keyof T]: DeepReadonly<T[P]> };
type StringNode = string | StringNode[];
type T1 = DeepReadonly<StringNode>;

Granted, for objects homomorphism (i.e. the retained optionality) is useful, so I don't know if this alone is enough to achieve what you want.

Why does this work? Honestly, I don't know. At this point I've easily spent weeks of my life fighting with "Type instantiation is excessively deep and possibly infinite." errors 😅 — usually the kind that show up with incremental compilation (watch) but don't show up with full builds.

[juhort]

@Benjamin-Dobell

The homomorphism isn't useful for arrays

I'd say it's very useful for arrays, I'd almost always want the structure, optional and rest elements to be preserved.

type DeepReadonly<T> = { readonly [P in (string | number | symbol) & keyof T]: DeepReadonly<T[P]> };

type T1 = DeepReadonly<[string, number]>; // breaks
//   ^? type T1 = { readonly [x: number]: DeepReadonly<string | number>; readonly [Symbol.iterator]: DeepRea…

T1 should have simply been readonly [string, number], which is why homomorphism is useful.

At this point I've easily spent weeks of my life fighting with "Type instantiation is excessively deep and possibly infinite." errors 😅 — usually the kind that show up with incremental compilation (watch) but don't show up with full builds.

In my experience the "Type instantiation is excessively deep and possibly infinite." error has always made sense.

[Benjamin-Dobell]

Fair enough. Well, in that case you can try with the type:

type DeepReadonly<T> = T extends [infer A, ...infer Rest]
    ? readonly [DeepReadonly<A>, ...(Rest extends never[] ? [] : DeepReadonly<Rest>)]
    : T extends Array<infer A>
        ? ReadonlyArray<DeepReadonly<A>>
        : { readonly [K in keyof T]: DeepReadonly<T[K]> };

It'll "work", but if you check out the type of T1 it ought to be reasonably clear why this an infinitely recursive type. Honestly, it probably shouldn't work.

https://www.typescriptlang.org/play/?ts=5.8.3#code/C4TwDgpgBAIhFgEoQIYBMD2A7ANiAPACoB8UAvFIVBAB7ARZoDOUA2gJZYBmEATlAEEANFAB04zj37ImwALoBYAFBRVUAPxReqTLhBs4CZOmx58A4iPGiAFDODU6DZlCwQAbn1ZyNbHwC5YeCQdUwJ7YgBKRRU1QKpaekYWAV5eFAJJPkFiZTV832NdPFT0gkMQkz1zYlzYgqhAgG8tUL02AGkoTigAawgQDC5KOUCKorCiVg65UgBfAG5lZVBIKABlYF5OAHMAOQw0aApZbawdqAAfDa3dg6PvJaVV6E2z-cOIAHkAIwArchQU67K5QFpYT6BN53T6-AGLZbPcDQQgARkB4zaZmh53uEGIT2UAGNsLIoMBUfF0RRWKwAORcDAYOlyOSEpFrHEfI6EACuYBwxyBt3OoK5eL5Aogj0RL0oACYMcEJtVWMDziJ1TtZuySVgycB5fFFTSGUy6SI6T8ULwWeyAPT2qAAAWATAAtLRIETgJ60hheMTSQ5gABmY2A+mM5mW622y1eiA+6j+21s2XIyhwpVGLEEcWw-4ExF6g1w+LZijgyFg1w1ukCOlQObNp5AA

[juhort]

@Benjamin-Dobell There are errors in your example.

1. type StringNodeTuple = string | StringNodeTuple[]; should be type StringNodeTuple = string | [StringNodeTuple];

2. type T2 = DeepReadonly<[string, string]>; should be type T2 = DeepReadonly<StringNodeTuple>;

Once you fix the above two you'll get the "Type instantiation is excessively deep and possibly infinite." error.

[Benjamin-Dobell]

@Benjamin-Dobell There are errors in your example.

1. `type StringNodeTuple = string | StringNodeTuple[];` should be `type StringNodeTuple = string | [StringNodeTuple];`

I was using the type you gave in your initial post. Although, I'm not sure practically what you're trying to achieve.

Isn't the intent here that you want to be able to use this utility type to convert some type, likely a literal, recursively to be readonly so that the receiver doesn't mutate it?

Something like? https://www.typescriptlang.org/play/?ts=5.8.3#code/C4TwDgpgBAIhFgEoQIYBMD2A7ANiAPACoB8UAvFIVBAB7ARZoDOUA2gJZYBmEATlAEEANFAB04zj37ImwALoBYAFBRVUAPxReqTLhBs4CZOmx58A4iPGiAFDODU6DZlCwQAbn1ZyNbHwC5YeCQdUwJ7YgBKRRU1QKpaekYWAV5eFAJJPkFiZTV832NdPFT0gkMQkz1zYlzYgqhAgG8tUL02AGkoTigAawgQDC5KOUCKorCiVg65UgBfAG5lZaVQSFgUYBQAZWBeAFcAY2B97XIoJry1FGarhoAjQKx9gFt7rzkl+qhFu6hDwKsWS8TgAcxEwLBnz+aFu33yTAwLwgwAAFmDAvcMBgcKgsF98r9vmAUNosMB1GNNjs9kcTtovkTlFx9lhjuxsFAAO7YYAAWX2W3oAE0MKddvsuFwiI4ki4YNTdgdjqcIMQbDcgkY2mYSJELn9lHMVjzyQKhRBReKTlKbJdvpr7Q1VI82ABGEQAJjkQj+c193wBbAA5OjgyJg2i+BBgz6YXDnVBEci0RioLSIAHCVm1CSycAE87HX9E67WB6oN6cw1-SW1EHWKH2OGoJHUdHY9WCrCDfDncmUeisKDAhmu4S-UbIsogA

Don't get me wrong, it'd be nice if TypeScript better handled recursion. I'm just proposing some workarounds in the meantime.

[juhort]

I was using the type you gave in your initial post. Although, I'm not sure practically what you're trying to achieve.

My bad, I fixed it, it should be type StringNodeTuple = string | [StringNodeTuple];.

Isn't the intent here that you want to be able to use this utility type to convert some type, likely a literal, recursively to be readonly so that the receiver doesn't mutate it?

I want DeepReadonly to work with recursive tuples, and I want to do it in a homomorphic way i.e., I want to preserve the tuple structure, optional elements, rest element.

[juhort]

@Benjamin-Dobell And the DataStructure in your example is a recursive object, for recursive objects just simply having a homomorphic mapped type works (refer example below). It's only in the case of recursive arrays/tuples that the homomorphic mapped type doesn't work.

type DeepReadonly<T> = { readonly [K in keyof T]: DeepReadonly<T[K]> };


type DataStructure = {
    a: {
        b: number[];
    };
    c: [string, string];
    d: {
        something: boolean;
    };
    parent?: DataStructure;
};

function wontMutateYourStuff<T extends DataStructure>(a: DeepReadonly<T>) {
    
}

wontMutateYourStuff({
    a: {
        b: [1, 2],
    },
    c: ['hi', 'there'],
    d: {
        something: true,
    },
    parent: {
        a: {
            b: [1, 2],
        },
        c: ['hi', 'there'],
        d: {
            something: true,
        }
    }
})

Playground

[Benjamin-Dobell]

Gotcha. Not that I would recommend this for a real codebase. But there are (questionable) strategies to restrict the recursion:

type DeepReadonly<T, DepthStack extends never[] = []> = DepthStack extends { length: 30 }
    ? T
    : { readonly [K in keyof T]: DeepReadonly<T[K], [never, ...DepthStack]> };

https://www.typescriptlang.org/play/?ts=5.8.3#code/C4TwDgpgBAIhFgEoQIYBMD2A7ANiAPACoA0sCwAFgMrAoDGA1lBAB7ARZoDOUWEAbhABOAbQC6UALxRxAPilkwlGvSat2nHgG8oODgHNKALigBmAAxQAvgFgAUFEdQA-FEL2nUEzqGpMuEBkAaSgASywoBggQDAAzNzETOARkdGw8IhEgsVIRPkEhUgA6ErglalpGMXkrAG57e1BIKBohcP0AOQw0aGkuYDasfSgAHxlW9q6esXq7RvBoQgBGBWSkP3SCCaGpiFlZoA

Of course. Your request seems very reasonable to me.

[juhort]

@Benjamin-Dobell Yeah, you can add a depth check, but if the mapped type works for objects, it should work for arrays as well.

Let's wait for somebody from the team to get back on this.

[Andarist]

I can't now find the exact comment made by Anders - but I distinctly remember him saying this could be changed/improved (the conversation happend in a different context but still).

Mapped types are eagerly instantiating element types when iterating over arrays/tuples. This is nice because the output is an array/tuple type and the compiler doesn't have to special-case those instantiations, thanks to that (they don't have to be represented in a different way internally). But this leads to a number of differences (like this one) between mapped types applied to object and array/tuple types.