Excessive instantiation depth with fluent chaining API

[andrewbranch]

@amcasey reduced a perf complaint from https://github.com/glideapps/glide-code-columns/blob/master/src/columns/as-array.ts to this playground:

class Col<TParams> {
    public withRequiredPrimitiveParam<TName extends string>(name: TName) {
        return undefined! as Col<
            TParams & { readonly [K in TName]: any }
        >;
    }
}

new Col()
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value")
    .withRequiredPrimitiveParam("value") // Hits stack limit

Each additional chain results in a new instantiation of Col with an additional { value: any } intersected with the previous instantiation’s type argument. These intersections don’t seem to get simplified for some reason—hovering the third call in the chain yields the quick info

(method) Col<{ readonly value: any; } & { readonly value: any; }>.withRequiredPrimitiveParam<"value">(name: "value"): Col<{
    readonly value: any;
} & {
    readonly value: any;
} & {
    readonly value: any;
}>

Working with a more realistic simplification of the source, @amcasey measured type instantiations as a function of calls in the chain:

It seems that the function is the same even for this dead simple reproduction where each call after the first doesn’t meaningfully change the return type since we max out at the same number of calls, and it’s not obvious to me why that pattern is exponential.

[amcasey]

In the original repro, you only need src/columns/as-array.ts (with duplicated calls) and src/glide.ts. Dropping the declarations supported by imports in glide.ts has no effect.

[ahejlsberg]

First, the easy workaround:

class Col<TParams> {
    public withRequiredPrimitiveParam<TName extends string>(name: TName) {
        return undefined! as Col<
            TParams & Record<TName, any>
        >;
    }
}

Basically, replace { readonly [K in TName]: any } with Record<TName, any>. What's the difference? Well, in order to maximally reuse instantiations of anonymous object types we determine which in-scope type parameters are possibly referenced within the object type and then create a map keyed by the type IDs for which the type parameters are instantiated. The object type only references TName, so that should be the only type parameter contributing to the key. However, it is hard for us to prove that TParams isn't referenced because there is intervening non-type-declaration code between the object type and the declaration of TParams. For example, there could be a local type that references TParams and a reference to that local type in the anonymous object type. For that reason, we view TParams as possibly referenced and include it in the instantiation key map. That in turn causes all the instantiations to look different to us, so we keep manufacturing new ones, making more and more types until we eventually hit our governor.

If we instead write Record<TName, any>, we effectively remove TParams from scope and all the instantiations collapse to a single cached type.

I'll think about ways we can be smarter about concluding that type parameters aren't referenced, but it's not trivial.

[fatcerberus]

Doesn't Record<TName, any> expand to { [K in TName]: any }, though? Since Record is defined as a type alias (AFAIK), equational reasoning seems to suggest the same limitations should apply...

[ahejlsberg]

Doesn't Record<TName, any> expand to { [K in TName]: any }, though?

Yes, they are structurally identical. But they are still represented as two distinct type instances in the type checker (specifically, two distinct instances of the ObjectType type), and intersections only deduplicate types with the same object identity. When we use Record<K, T>, the instantiation cache is keyed by the type identities used for K and T. In the example there, that means all instantiations for the same TName are shared. But when we use { [K in TName]: any }, the instantiation cache is keyed by the type identities used for TParams and TName. And the fact that we can't exclude TParams is what causes the problem.

[fatcerberus]

Ah, thanks. I had assumed that type aliases worked like macros and were always expanded in-place.

[schani]

Thank you so much for the workaround!

[amcasey]

Confirmed that the mitigation works in my unreduced original repro.

@schani How does the editor feel in the real-world usage?

[schani]

In the small repo linked to above it's super fast now. In our big proprietary repo performance is definitely improved, but still sluggish. This was just one source of slowdown.

[Feirell]

If you want to have a isolated example, with the generated trace files, have a look at an identical issue: https://github.com/microsoft/TypeScript/issues/46840 . It is somewhat more bloated but has the same underlying issue and the solution from @ahejlsberg works and brings the check time from 50s down to 0.25s.

Thank you very much!

[rotu]

This seems to have been fixed somewhere between 5.0.4 and 5.1.6 The intersection still grows with each chained call, but inference no longer fails with "Type instantiation is excessively deep and possibly infinite."