perf: exponential slowdown in flow analysis

[JoostK]

TypeScript Version: 4.1.0-dev.20201015, 4.0.3, 3.9.7

Search Terms: performance, flow analysis

Code

function test(x: boolean): boolean { return x; }

let state = true;

if (state) {
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  // if (state) {}
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
  test(state as any && state);
}

Expected behavior:
Type checking of this single file completes in the order of milliseconds.

A real world example of this issue has been reported in the Angular repo for code generated by the template type checker: angular/angular#39274. Angular has a code generator that emits TypeScript code to typecheck Angular templates.

Actual behavior:

Each additional function invocation is causing the type checking phase to roughly double in time. The above sample takes ~1.8s in the "Check" phase, as reported in the diagnostics report:

Files:               2
Lines:            4447
Nodes:           13457
Identifiers:      5569
Symbols:          2948
Types:              80
Instantiations:      0
Memory used:    30757K
I/O read:        0.00s
I/O write:       0.00s
Parse time:      0.10s
Bind time:       0.04s
Check time:      1.64s
Emit time:       0.00s
Total time:      1.77s

Adding one additional function invocation increases the Check time to ~5.1s:

Files:               2
Lines:            4447
Nodes:           13466
Identifiers:      5572
Symbols:          2948
Types:              80
Instantiations:      0
Memory used:    28699K
I/O read:        0.00s
I/O write:       0.00s
Parse time:      0.10s
Bind time:       0.04s
Check time:      4.97s
Emit time:       0.00s
Total time:      5.10s

Surprisingly, uncommenting the if (state) {} line reduces the check time significantly, but that is not effective once more statements are added.

Removing the as any cast makes it fast, as would removing the test function invocation.

Playground Link:

Terminal reproduction to get insight in timings:

npx typescript@4.1.0-dev.20201015 sample.ts --diagnostics --noEmit --lib es5 --strict --typeRoots []

Source code for sample.ts is found above, under Code.

Related Issues:

A similar state explosion was reported in #35205.

[weswigham]

Oh, well, this seems obvious. We added flow nodes for call expressions in expression statements, so each call adds to the flow depth, and none of the intermediate results are cached in this example, because we only cache on flow assignments. Enabling caching on flow calls like we have for flow assignments will probably fix the poor perf profile here.