Perf cliff when computing a base constraint of a circular mapped type

[Andarist]

Bug Report

🔎 Search Terms

constraint, perf cliff, mapped type

🕗 Version & Regression Information

• This is the behavior in every version I tried

⏯ Playground Link

Playground link with relevant code

💻 Code

// extracted from a more reasonable repro that was tokenizing a "design system"-like theme object
type Values<T> = T[keyof T];

type TokenizeSlow<Theme> = Values<{
  [K in keyof Theme]: `${Theme[K] extends any
    ? string
    : TokenizeSlow<Theme[K]>}`;
}>;

export function createThemeSlow<T>(theme: T) {
  return { getTokenSlow: (token: TokenizeSlow<T>) => {} };
}

🙁 Actual behavior

Type-checking of the generic TokenizeSlow is, well, slow. Of course, this is just a single type but it also doesn't look overly complex and the amount of work that it is done by the compiler to typecheck it is suboptimal.

Executed with --extendedDiagnostics:

Files:                         100
Lines of Library:            27420
Lines of Definitions:        40372
Lines of TypeScript:            12
Lines of JavaScript:             0
Lines of JSON:                   0
Lines of Other:                  0
Nodes of Library:           118506
Nodes of Definitions:       107643
Nodes of TypeScript:            67
Nodes of JavaScript:             0
Nodes of JSON:                   0
Nodes of Other:                  0
Identifiers:                 79714
Symbols:                     50487
Types:                         189
Instantiations:            4084069
Memory used:                96309K
Assignability cache size:        6
Identity cache size:             0
Subtype cache size:              0
Strict subtype cache size:       0
I/O Read time:               0.03s
Parse time:                  1.08s
ResolveTypeReference time:   0.02s
ResolveModule time:          0.03s
Program time:                1.24s
Bind time:                   0.40s
Check time:                  0.44s
printTime time:              0.00s
Emit time:                   0.00s
Total time:                  2.08s

Where the important part is the Check time metric. If we rewrite this single type slightly then we can get the Check time to smth like 0.02s.

We can see here how the whole thing goes kinda crazy through extensive & deep instantiateTypeWithAlias cycle~. The whole CPU profile can be seen here - tokenize_slow_cpu_profile.tar.gz.

The part of the problem is that in here TypeScript tries to check if the conditional type (Theme[K] extends any ? string : TokenizeSlow<Theme[K]>) is assignable to something that can be interpolated into a template literal (if it is assignable to templateConstraintType). To do that it tries to get the base constraint of this conditional type and goes haywire when trying to analyze TokenizeSlow<Theme[K]>, starting from substituteIndexedMappedType with:

objectType // { [K in keyof Theme[K]]: `${Theme[K][K] extends any ? string : TokenizeSlow<Theme[K][K]>}`; }
index // keyof Theme[K]

and on the next "iteration" in the same substituteIndexedMappedType:

objectType // { [K in keyof Theme[K][keyof Theme[K]][keyof Theme[K]]]: `${Theme[K][keyof Theme[K]][keyof Theme[K]][K] extends any ? string : TokenizeSlow<Theme[K][keyof Theme[K]][keyof Theme[K]][K]>}`; }
index // keyof Theme[K][keyof Theme[K]][keyof Theme[K]]

It continues instantiating this thing at least a couple of times, to a type that I don't dare copy-pasting here 😉 . That alone might not be a problem but perhaps this is the stage at which an optimization could be introduced to recognize that instantiating this Values with recursive keyof Theme[K] etc doesn't make sense. If for Values the substitution could happen here once then we'd probably see a good perf win here.

[ahejlsberg]

I looked into this and it turns out we have a logic error in substituteIndexedMappedType where we instantiate an already instantiated type which, in this particular example, generates an enormous amount of useless work. It's a trivial fix, I'll put up a PR.