Degenerate compiler performance when processing large unions

[nomcopter]

TypeScript Version: 3.9.0-dev.20200328

Search Terms: large union, performance, indexed access

Code

type BigUnion = {
  name: '1';
  children: BigUnion[];
} | {
  name: '2';
  children: BigUnion[];
  // 1000 more .......
} | {
  name: '1003';
  children: BigUnion[];
};

type DiscriminateUnion<T, K extends keyof T, V extends T[K]> = T extends Record<K, V> ? T : never;

type WithName<T extends BigUnion['name']> = DiscriminateUnion<BigUnion, 'name', T>;

type ChildrenOf<T extends BigUnion> = T['children'][number];

export function makeThing<T extends BigUnion['name']>(
  name: T,
  children: ChildrenOf<WithName<T>>[] = [],
) { }

Expected behavior:
It compiles reasonably quickly.

Note: This happens even when children is not a recursive reference. In my project children is an array of specific subtypes of BigUnion but it is closed source.

Actual behavior:
It takes over 90s to compile on a 2019 Macbook Pro using node or the playground link.

  % tsc --noEmit --diagnostics --extendedDiagnostics --generateCpuProfile out.prof simple.ts
Files:                           6
Lines:                       27987
Nodes:                      122358
Identifiers:                 44171
Symbols:                     32200
Types:                       19618
Memory used:               234674K
Assignability cache size:  2055962
Identity cache size:             0
Subtype cache size:              0
Strict subtype cache size:       0
I/O Read time:               0.01s
Parse time:                  0.30s
Program time:                0.32s
Bind time:                   0.15s
Check time:                 97.49s
Total time:                 97.95s
✨  Done in 98.49s.

cpuprofile.prof.zip

Playground Link: Playground Link

Related Issues: #29350

[weswigham]

Ohhh, 86.44% of total time spent in getRegularTypeOfLiteralType? Yeah, that sounds degenerate. Looks like we don't cache that calculation, so we're re-iterating over the massive union every time.

[nomcopter]

Thanks for a quick fix - clever optimizations!