Exponential compilation slowdown with property accessors and conditional types

[alexfoxgill]

Apologies, I have had to break from the template in order to describe this issue since it is not easily reproduced in a simple demo.

TypeScript Version: 3.0.3, 3.2.2, 3.3.0-dev.20190110

Search Terms: compilation performance, generic property accessor, conditional types

Code

So far in investigating this issue I have identified this code block as the culprit, due to this commit

export type PropOverloads<D extends Dimensionality, S extends Structure, A, B, Params extends {}> = {
  <K1 extends keyof B>(key: K1)
    : Composable.ComposeResult<A, B[K1], Params, D, Dimensionality.Single, S, Structure.Select>

  <K1 extends keyof B, K2 extends keyof B[K1]>(k1: K1, k2: K2)
    : Composable.ComposeResult<A, B[K1][K2], Params, D, Dimensionality.Single, S, Structure.Select>

  <K1 extends keyof B, K2 extends keyof B[K1], K3 extends keyof B[K1][K2]>(k1: K1, k2: K2, k3: K3)
    : Composable.ComposeResult<A, B[K1][K2][K3], Params, D, Dimensionality.Single, S, Structure.Select>

  <K1 extends keyof B, K2 extends keyof B[K1], K3 extends keyof B[K1][K2], K4 extends keyof B[K1][K2][K3]>(k1: K1, k2: K2, k3: K3, k4: K4)
    : Composable.ComposeResult<A, B[K1][K2][K3][K4], Params, D, Dimensionality.Single, S, Structure.Select>
}

"Supporting" code:

export enum Dimensionality {
  Single = "single",
  Maybe = "maybe"
}

export namespace Dimensionality {
  export type Highest<T extends Dimensionality, U extends Dimensionality> =
    Dimensionality extends T ? never
    : Dimensionality extends U ? never
    : Dimensionality.Maybe extends (T | U) ? Dimensionality.Maybe
    : Dimensionality.Single extends (T | U) ? Dimensionality.Single
    : never
}

export enum Structure {
  Get = "get",
  Select = "select",
  Convert = "convert"
}

export namespace Structure {
  export type Narrowest<T extends Structure, U extends Structure> =
    Structure extends T ? never
    : Structure extends U ? never
    : Structure.Get extends (T | U) ? Structure.Get
    : Structure.Select extends (T | U) ? Structure.Select
    : Structure.Convert extends (T | U) ? Structure.Convert
    : never
}

export type Composable<A, B, Params extends {}> =
  | Get<A, B, Params>
  | MaybeGet<A, B, Params>
  | Selector<A, B, Params>
  | MaybeSelector<A, B, Params>
  | Converter<A, B, Params>
  | MaybeConverter<A, B, Params>

export type ShapeResult<D1 extends Dimensionality, D2 extends Dimensionality, S1 extends Structure, S2 extends Structure> =
  Shape<Dimensionality.Highest<D1, D2>, Structure.Narrowest<S1, S2>>

export type ComposeResult<A, B, P extends {}, D1 extends Dimensionality, D2 extends Dimensionality, S1 extends Structure, S2 extends Structure> =
  Extract<Composable<A, B, P>, ShapeResult<D1, D2, S1, S2>>

Expected behavior: A compilation time of ~3 seconds, akin to the previous commit

Actual behavior: A compilation time of ~80 seconds

Related Issues: none that I could find

---

Output of tsc --diagnostics

Before this change, in the previous commit:

Symbols:      121139
Types:         67276
Memory used: 131777K
Check time:    2.36s
Total time:    3.19s

After this change:

Symbols:     1313985
Types:        788655
Memory used: 911104K
Check time:   78.97s
Total time:   79.67s

Without the 4-argument overload:

Symbols:     1085472
Types:        650274
Memory used: 763202K
Check time:   45.22s
Total time:   45.97s

With only the 1- and 2-argument overloads:

Symbols:      868055
Types:        522824
Memory used: 619599K
Check time:   27.51s
Total time:   28.21s

With only the 1-argument overload:

Symbols:      651404
Types:        399632
Memory used: 499634K
Check time:   16.01s
Total time:   16.68s

I am not really sure how to narrow this down to a particular problem or debug the compilation time; I only notice that the number of types and symbols increases hugely with just a single method interface

[alexfoxgill]

I have continued investigating and I believe the issue is related to a combination of:

• conditional types
• union types
• indexed accessors

---

I have reduced the problem slightly, ignoring the S and D parameters - they were seemingly not related:

export type PropResult<A, B, P> =
| Get<A, B, P>
| MaybeGet<A, B, P>
| Selector<A, B, P>
| MaybeSelector<A, B, P>
| Converter<A, B, P>
| MaybeConverter<A, B, P>

export type PropOverloads<A, B, P extends {}> = {
  <K1 extends keyof B>(key: K1)
    : PropResult<A, B[K1], P>
  <K1 extends keyof B, K2 extends keyof B[K1]>(key: K1, k2: K2)
    : PropResult<A, B[K1][K2], P>
  <K1 extends keyof B, K2 extends keyof B[K1], K3 extends keyof B[K1][K2]>(key: K1, k2: K2, k3: K3)
    : PropResult<A, B[K1][K2][K3], P>
  <K1 extends keyof B, K2 extends keyof B[K1], K3 extends keyof B[K1][K2], K4 extends keyof B[K1][K2][K3]>(key: K1, k2: K2, k3: K3, k4: K4)
    : PropResult<A, B[K1][K2][K3][K4], P>
}

Symbols:     1564987
Types:        730086
Memory used: 926248K
Check time:   63.81s

However, when you replace the P parameter from Get and MaybeGet with {}, the performance issue vanishes:

export type PropResult<A, B, P> =
| Get<A, B, {}>
| MaybeGet<A, B, {}>
| Selector<A, B, P>
| MaybeSelector<A, B, P>
| Converter<A, B, P>
| MaybeConverter<A, B, P>

export type PropOverloads<A, B, P extends {}> = {
  <K1 extends keyof B>(key: K1)
    : PropResult<A, B[K1], P>
  <K1 extends keyof B, K2 extends keyof B[K1]>(key: K1, k2: K2)
    : PropResult<A, B[K1][K2], P>
  <K1 extends keyof B, K2 extends keyof B[K1], K3 extends keyof B[K1][K2]>(key: K1, k2: K2, k3: K3)
    : PropResult<A, B[K1][K2][K3], P>
  <K1 extends keyof B, K2 extends keyof B[K1], K3 extends keyof B[K1][K2], K4 extends keyof B[K1][K2][K3]>(key: K1, k2: K2, k3: K3, k4: K4)
    : PropResult<A, B[K1][K2][K3][K4], P>
}

Symbols:      227749
Types:         89955
Memory used: 182114K
Check time:    2.28s

What is special about Get and MaybeGet? They are conditional types, predicated on P:

export type GetSignature<A, B, Params extends {}> =
  {} extends Params
  ? (a: A) => B
  : (a: A, params: Params) => B

export type Get<A, B, Params extends {} = {}> = GetSignature<A, B, Params> & {
  ...
}

[alexfoxgill]

@weswigham do you think you'll be able to assign someone to help out with this?

[alexfoxgill]

Further investigation reveals that removing the ifDefined property on Get and MaybeGet also eliminates the performance problem.

  ...
  ifDefined: IfDefinedOverloads<Dimensionality.Single, Structure.Get, A, B, Params>
  ...

export type IfOptional<T, U> = undefined extends T ? U : null extends T ? U : never

export type IfDefinedOverloads<D extends Dimensionality, S extends Structure, A, B, Params extends {}> = IfOptional<B, {
  (): Composable.ComposeResult<A, Exclude<B, null | undefined>, Params, D, Dimensionality.Maybe, S, Structure.Convert>
  (defaultValue: B): Composable.ComposeResult<A, Exclude<B, null | undefined>, Params, D, Dimensionality.Single, S, Structure.Convert>
}>

It's specifically the Exclude<B, null | undefined> that causes the problem here. Replacing with B also eliminates the slowdown.

I guess what is happening is that the compiler expands the indexed accessor and this creates some combinatorial explosion with the multiple conditional types?