Tail recursive evaluation of conditional types #45711

ahejlsberg · 2021-09-03T15:37:19Z

In #45025 we increased the type instantiation depth limit from 50 to 500. We've subsequently seen multiple examples of stack overflows occurring during compilation of programs containing non-terminating types, particularly when the compiler is used in browser hosted environments (where, apparently, in some cases the call stack limit is lower than in Node.js). It is clear that 500 is too high of a limit, so in this PR we lower the maximum to 100.

There are legitimate cases where evaluation of recursive conditional types needs more than 100 iterations to complete. For that reason, this PR implements tail recursive evaluation of conditional types. Specifically, when a conditional type ends in another (or, through recursion, another instantiation of the same) conditional type, the compiler now performs type resolution in a loop that consumes no extra call stack. We permit evaluation of such types to loop 1000 times before we consider the type non-terminating and issue an error.

The following conditional type is tail recursive:

type Trim<S extends string> =
    S extends ` ${infer T}` ? Trim<T> :
    S extends `${infer T} ` ? Trim<T> :
    S;

Previously, resolution of instantiations of this type would error for string literals containing more than 25 blanks. We now permit strings with up to 1000 blanks.

Conditional types that aren't tail recursive generally can be written in a tail recursive form by introducing an "accumulator". For example, this type, which extracts a union of the characters in a string, isn't tail recursive (because it recurs through a union type)

type GetChars<S> =
    S extends `${infer Char}${infer Rest}` ? Char | GetChars<Rest> : never;

but this rewritten form is

type GetChars<S> = GetCharsRec<S, never>;
type GetCharsRec<S, Acc> =
    S extends `${infer Char}${infer Rest}` ? GetCharsRec<Rest, Char | Acc> : Acc;

Some additional examples of tail recursive conditional types:

type Reverse<T> = any[] extends T ? T : ReverseRec<T, []>;
type ReverseRec<T, Acc extends unknown[]> =
    T extends [infer Head, ...infer Tail] ? ReverseRec<Tail, [Head, ...Acc]> : Acc;
type T1 = Reverse<[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]>;
type TupleOf<T, N extends number> = number extends N ? T[] : TupleOfRec<T, N, []>;
type TupleOfRec<T, N extends number, Acc extends unknown[]> =
    Acc["length"] extends N ? Acc : TupleOfRec<T, N, [T, ...Acc]>;
type T2 = TupleOf<any, 200>;

The examples above previously would error in "Type instantiation is excessively deep and possibly infinite", but now succeed.

…antiation depth limit to 100

ahejlsberg · 2021-09-03T15:44:42Z

@typescript-bot test this
@typescript-bot user test this
@typescript-bot run dt
@typescript-bot perf test this

typescript-bot · 2021-09-03T15:44:44Z

Heya @ahejlsberg, I've started to run the parallelized Definitely Typed test suite on this PR at 093f76a. You can monitor the build here.

typescript-bot · 2021-09-03T15:44:44Z

Heya @ahejlsberg, I've started to run the extended test suite on this PR at 093f76a. You can monitor the build here.

typescript-bot · 2021-09-03T15:44:44Z

Heya @ahejlsberg, I've started to run the parallelized community code test suite on this PR at 093f76a. You can monitor the build here.

typescript-bot · 2021-09-03T15:44:44Z

Heya @ahejlsberg, I've started to run the perf test suite on this PR at 093f76a. You can monitor the build here.

Update: The results are in!

weswigham

It'd be nice if we could kinda automatically do the "extract to an accumulator" thing you suggest in the OP, so people didn't need to write their conditionals with such structure in mind; but this seems good.

typescript-bot · 2021-09-03T16:18:23Z

The user suite test run you requested has finished and failed. I've opened a PR with the baseline diff from master.

typescript-bot · 2021-09-03T16:20:30Z

@ahejlsberg
The results of the perf run you requested are in!

Here they are:

Comparison Report - main..45711

_Metric	_main	₄₅₇₁₁	_Delta	_Best	_Worst
_{Angular - node (v10.16.3, x64)}
_{Memory used}	_{351,611k (± 0.03%)}	_{351,552k (± 0.02%)}	_{-59k (- 0.02%)}	_351,375k	_351,666k
_{Parse Time}	_{1.91s (± 0.30%)}	_{1.90s (± 0.49%)}	_{-0.00s (- 0.26%)}	_1.88s	_1.92s
_{Bind Time}	_{0.85s (± 0.40%)}	_{0.85s (± 0.70%)}	_{+0.00s (+ 0.23%)}	_0.84s	_0.87s
_{Check Time}	_{5.39s (± 0.41%)}	_{5.40s (± 0.32%)}	_{+0.01s (+ 0.15%)}	_5.36s	_5.43s
_{Emit Time}	_{5.83s (± 0.42%)}	_{5.84s (± 0.45%)}	_{+0.01s (+ 0.17%)}	_5.79s	_5.91s
_{Total Time}	_{13.97s (± 0.25%)}	_{13.99s (± 0.27%)}	_{+0.02s (+ 0.11%)}	_13.93s	_14.10s
_{Compiler-Unions - node (v10.16.3, x64)}
_{Memory used}	_{203,474k (± 0.03%)}	_{203,450k (± 0.03%)}	_{-24k (- 0.01%)}	_203,353k	_203,620k
_{Parse Time}	_{0.78s (± 0.85%)}	_{0.78s (± 0.87%)}	_{+0.00s (+ 0.51%)}	_0.77s	_0.80s
_{Bind Time}	_{0.52s (± 1.13%)}	_{0.52s (± 1.28%)}	_{-0.00s (- 0.19%)}	_0.51s	_0.54s
_{Check Time}	_{7.82s (± 0.42%)}	_{7.80s (± 0.42%)}	_{-0.02s (- 0.26%)}	_7.75s	_7.91s
_{Emit Time}	_{2.44s (± 0.51%)}	_{2.43s (± 1.06%)}	_{-0.01s (- 0.25%)}	_2.40s	_2.53s
_{Total Time}	_{11.56s (± 0.42%)}	_{11.54s (± 0.39%)}	_{-0.02s (- 0.15%)}	_11.47s	_11.65s
_{Monaco - node (v10.16.3, x64)}
_{Memory used}	_{340,659k (± 0.02%)}	_{340,634k (± 0.02%)}	_{-25k (- 0.01%)}	_340,472k	_340,811k
_{Parse Time}	_{1.45s (± 0.69%)}	_{1.45s (± 0.67%)}	_{+0.00s (+ 0.07%)}	_1.43s	_1.47s
_{Bind Time}	_{0.75s (± 0.87%)}	_{0.75s (± 0.40%)}	_{0.00s ( 0.00%)}	_0.74s	_0.75s
_{Check Time}	_{5.44s (± 0.37%)}	_{5.40s (± 0.45%)}	_{-0.04s (- 0.68%)}	_5.36s	_5.48s
_{Emit Time}	_{3.17s (± 0.78%)}	_{3.15s (± 0.58%)}	_{-0.02s (- 0.63%)}	_3.11s	_3.18s
_{Total Time}	_{10.80s (± 0.32%)}	_{10.75s (± 0.34%)}	_{-0.05s (- 0.50%)}	_10.67s	_10.82s
_{TFS - node (v10.16.3, x64)}
_{Memory used}	_{304,028k (± 0.01%)}	_{304,024k (± 0.03%)}	_{-4k (- 0.00%)}	_303,780k	_304,176k
_{Parse Time}	_{1.18s (± 0.52%)}	_{1.19s (± 0.57%)}	_{+0.01s (+ 0.59%)}	_1.18s	_1.21s
_{Bind Time}	_{0.72s (± 0.95%)}	_{0.71s (± 1.06%)}	_{-0.00s (- 0.14%)}	_0.70s	_0.73s
_{Check Time}	_{4.92s (± 0.56%)}	_{4.94s (± 0.62%)}	_{+0.03s (+ 0.53%)}	_4.86s	_4.99s
_{Emit Time}	_{3.31s (± 1.05%)}	_{3.37s (± 1.96%)}	_{+0.06s (+ 1.72%)}	_3.25s	_3.52s
_{Total Time}	_{10.12s (± 0.45%)}	_{10.21s (± 0.71%)}	_{+0.09s (+ 0.86%)}	_10.08s	_10.40s
_{material-ui - node (v10.16.3, x64)}
_{Memory used}	_{469,942k (± 0.01%)}	_{469,793k (± 0.01%)}	_{-149k (- 0.03%)}	_469,715k	_469,940k
_{Parse Time}	_{1.73s (± 0.40%)}	_{1.73s (± 0.43%)}	_{+0.01s (+ 0.46%)}	_1.72s	_1.75s
_{Bind Time}	_{0.66s (± 0.55%)}	_{0.67s (± 0.51%)}	_{+0.01s (+ 1.36%)}	_0.67s	_0.68s
_{Check Time}	_{14.15s (± 0.27%)}	_{14.35s (± 0.65%)}	_{+0.20s (+ 1.43%)}	_14.16s	_14.60s
_{Emit Time}	_{0.00s (± 0.00%)}	_{0.00s (± 0.00%)}	_{0.00s ( NaN%)}	_0.00s	_0.00s
_{Total Time}	_{16.54s (± 0.24%)}	_{16.76s (± 0.58%)}	_{+0.22s (+ 1.31%)}	_16.56s	_17.01s
_{Angular - node (v12.1.0, x64)}
_{Memory used}	_{329,584k (± 0.03%)}	_{329,534k (± 0.02%)}	_{-49k (- 0.01%)}	_329,365k	_329,668k
_{Parse Time}	_{1.88s (± 0.62%)}	_{1.88s (± 0.48%)}	_{-0.00s (- 0.21%)}	_1.85s	_1.89s
_{Bind Time}	_{0.83s (± 0.44%)}	_{0.84s (± 0.80%)}	_{+0.00s (+ 0.24%)}	_0.82s	_0.85s
_{Check Time}	_{5.22s (± 0.52%)}	_{5.22s (± 0.39%)}	_{+0.01s (+ 0.10%)}	_5.19s	_5.28s
_{Emit Time}	_{6.05s (± 0.49%)}	_{6.13s (± 1.46%)}	_{+0.08s (+ 1.32%)}	_6.04s	_6.47s
_{Total Time}	_{13.98s (± 0.31%)}	_{14.07s (± 0.71%)}	_{+0.08s (+ 0.59%)}	_13.94s	_14.41s
_{Compiler-Unions - node (v12.1.0, x64)}
_{Memory used}	_{191,013k (± 0.02%)}	_{190,985k (± 0.03%)}	_{-28k (- 0.01%)}	_190,894k	_191,166k
_{Parse Time}	_{0.78s (± 0.83%)}	_{0.78s (± 0.88%)}	_{-0.01s (- 0.77%)}	_0.76s	_0.79s
_{Bind Time}	_{0.52s (± 1.13%)}	_{0.53s (± 1.09%)}	_{+0.01s (+ 1.15%)}	_0.52s	_0.54s
_{Check Time}	_{7.37s (± 0.58%)}	_{7.39s (± 0.72%)}	_{+0.02s (+ 0.22%)}	_7.31s	_7.50s
_{Emit Time}	_{2.47s (± 1.18%)}	_{2.45s (± 0.78%)}	_{-0.02s (- 0.61%)}	_2.42s	_2.51s
_{Total Time}	_{11.15s (± 0.49%)}	_{11.15s (± 0.57%)}	_{0.00s ( 0.00%)}	_11.04s	_11.28s
_{Monaco - node (v12.1.0, x64)}
_{Memory used}	_{323,734k (± 0.01%)}	_{323,779k (± 0.02%)}	_{+45k (+ 0.01%)}	_323,576k	_323,859k
_{Parse Time}	_{1.43s (± 0.51%)}	_{1.43s (± 0.85%)}	_{+0.00s (+ 0.21%)}	_1.41s	_1.46s
_{Bind Time}	_{0.72s (± 0.47%)}	_{0.73s (± 0.92%)}	_{+0.00s (+ 0.55%)}	_0.71s	_0.74s
_{Check Time}	_{5.26s (± 0.43%)}	_{5.28s (± 0.37%)}	_{+0.03s (+ 0.49%)}	_5.23s	_5.31s
_{Emit Time}	_{3.19s (± 0.67%)}	_{3.19s (± 0.78%)}	_{-0.00s (- 0.06%)}	_3.15s	_3.25s
_{Total Time}	_{10.60s (± 0.35%)}	_{10.63s (± 0.30%)}	_{+0.03s (+ 0.30%)}	_10.54s	_10.69s
_{TFS - node (v12.1.0, x64)}
_{Memory used}	_{288,714k (± 0.02%)}	_{288,785k (± 0.02%)}	_{+71k (+ 0.02%)}	_288,664k	_288,910k
_{Parse Time}	_{1.20s (± 0.77%)}	_{1.21s (± 0.93%)}	_{+0.01s (+ 0.75%)}	_1.19s	_1.24s
_{Bind Time}	_{0.70s (± 0.71%)}	_{0.70s (± 0.97%)}	_{+0.01s (+ 1.29%)}	_0.69s	_0.72s
_{Check Time}	_{4.83s (± 0.41%)}	_{4.87s (± 0.53%)}	_{+0.04s (+ 0.81%)}	_4.82s	_4.92s
_{Emit Time}	_{3.37s (± 0.55%)}	_{3.40s (± 0.83%)}	_{+0.03s (+ 0.77%)}	_3.34s	_3.48s
_{Total Time}	_{10.10s (± 0.32%)}	_{10.18s (± 0.55%)}	_{+0.08s (+ 0.82%)}	_10.05s	_10.34s
_{material-ui - node (v12.1.0, x64)}
_{Memory used}	_{448,462k (± 0.07%)}	_{448,419k (± 0.05%)}	_{-43k (- 0.01%)}	_447,608k	_448,684k
_{Parse Time}	_{1.72s (± 0.47%)}	_{1.73s (± 0.50%)}	_{+0.00s (+ 0.29%)}	_1.71s	_1.75s
_{Bind Time}	_{0.65s (± 0.86%)}	_{0.65s (± 0.91%)}	_{+0.01s (+ 0.93%)}	_0.64s	_0.67s
_{Check Time}	_{12.78s (± 0.53%)}	_{12.97s (± 0.89%)}	_{+0.19s (+ 1.50%)}	_12.76s	_13.24s
_{Emit Time}	_{0.00s (± 0.00%)}	_{0.00s (± 0.00%)}	_{0.00s ( NaN%)}	_0.00s	_0.00s
_{Total Time}	_{15.15s (± 0.46%)}	_{15.36s (± 0.78%)}	_{+0.20s (+ 1.34%)}	_15.16s	_15.63s
_{Angular - node (v14.15.1, x64)}
_{Memory used}	_{328,115k (± 0.01%)}	_{328,111k (± 0.01%)}	_{-4k (- 0.00%)}	_328,022k	_328,206k
_{Parse Time}	_{1.91s (± 0.70%)}	_{1.90s (± 0.52%)}	_{-0.01s (- 0.37%)}	_1.88s	_1.92s
_{Bind Time}	_{0.88s (± 1.13%)}	_{0.88s (± 0.41%)}	_{+0.00s (+ 0.45%)}	_0.88s	_0.89s
_{Check Time}	_{5.29s (± 0.46%)}	_{5.28s (± 0.47%)}	_{-0.01s (- 0.13%)}	_5.21s	_5.33s
_{Emit Time}	_{6.22s (± 0.87%)}	_{6.22s (± 0.78%)}	_{-0.01s (- 0.10%)}	_6.12s	_6.30s
_{Total Time}	_{14.30s (± 0.55%)}	_{14.29s (± 0.49%)}	_{-0.02s (- 0.11%)}	_14.11s	_14.39s
_{Compiler-Unions - node (v14.15.1, x64)}
_{Memory used}	_{192,165k (± 0.48%)}	_{192,487k (± 0.38%)}	_{+321k (+ 0.17%)}	_189,506k	_192,910k
_{Parse Time}	_{0.81s (± 0.76%)}	_{0.81s (± 0.58%)}	_{+0.00s (+ 0.12%)}	_0.80s	_0.82s
_{Bind Time}	_{0.55s (± 1.08%)}	_{0.56s (± 0.53%)}	_{+0.00s (+ 0.54%)}	_0.55s	_0.56s
_{Check Time}	_{7.50s (± 0.50%)}	_{7.54s (± 0.71%)}	_{+0.04s (+ 0.52%)}	_7.42s	_7.65s
_{Emit Time}	_{2.45s (± 0.58%)}	_{2.46s (± 0.56%)}	_{+0.01s (+ 0.45%)}	_2.43s	_2.49s
_{Total Time}	_{11.31s (± 0.44%)}	_{11.37s (± 0.50%)}	_{+0.06s (+ 0.51%)}	_11.26s	_11.52s
_{Monaco - node (v14.15.1, x64)}
_{Memory used}	_{322,544k (± 0.00%)}	_{322,548k (± 0.01%)}	_{+4k (+ 0.00%)}	_322,489k	_322,578k
_{Parse Time}	_{1.49s (± 0.98%)}	_{1.49s (± 0.61%)}	_{+0.00s (+ 0.27%)}	_1.47s	_1.51s
_{Bind Time}	_{0.75s (± 0.40%)}	_{0.76s (± 0.66%)}	_{+0.00s (+ 0.40%)}	_0.75s	_0.77s
_{Check Time}	_{5.21s (± 0.61%)}	_{5.24s (± 0.27%)}	_{+0.03s (+ 0.58%)}	_5.22s	_5.28s
_{Emit Time}	_{3.22s (± 0.63%)}	_{3.22s (± 0.65%)}	_{0.00s ( 0.00%)}	_3.16s	_3.26s
_{Total Time}	_{10.67s (± 0.46%)}	_{10.71s (± 0.27%)}	_{+0.04s (+ 0.34%)}	_10.61s	_10.75s
_{TFS - node (v14.15.1, x64)}
_{Memory used}	_{287,699k (± 0.01%)}	_{287,695k (± 0.00%)}	_{-5k (- 0.00%)}	_287,669k	_287,707k
_{Parse Time}	_{1.26s (± 1.13%)}	_{1.25s (± 2.11%)}	_{-0.01s (- 0.48%)}	_1.21s	_1.34s
_{Bind Time}	_{0.72s (± 0.80%)}	_{0.76s (± 4.49%)}	_{+0.04s (+ 5.28%)}	_0.71s	_0.83s
_{Check Time}	_{4.86s (± 0.54%)}	_{4.87s (± 0.68%)}	_{+0.01s (+ 0.14%)}	_4.79s	_4.92s
_{Emit Time}	_{3.46s (± 1.01%)}	_{3.46s (± 0.88%)}	_{-0.00s (- 0.14%)}	_3.40s	_3.53s
_{Total Time}	_{10.30s (± 0.40%)}	_{10.34s (± 0.60%)}	_{+0.03s (+ 0.33%)}	_10.20s	_10.44s
_{material-ui - node (v14.15.1, x64)}
_{Memory used}	_{447,023k (± 0.00%)}	_{446,915k (± 0.01%)}	_{-108k (- 0.02%)}	_446,870k	_446,976k
_{Parse Time}	_{1.76s (± 0.47%)}	_{1.77s (± 0.62%)}	_{+0.02s (+ 0.97%)}	_1.75s	_1.80s
_{Bind Time}	_{0.68s (± 0.87%)}	_{0.69s (± 0.94%)}	_{+0.01s (+ 1.02%)}	_0.68s	_0.71s
_{Check Time}	_{12.90s (± 0.53%)}	_{13.19s (± 0.49%)}	_{+0.29s (+ 2.27%)}	_13.00s	_13.34s
_{Emit Time}	_{0.00s (± 0.00%)}	_{0.00s (± 0.00%)}	_{0.00s ( NaN%)}	_0.00s	_0.00s
_{Total Time}	_{15.34s (± 0.50%)}	_{15.66s (± 0.42%)}	_{+0.32s (+ 2.09%)}	_15.47s	_15.78s

System

_{Machine Name}	_ts-ci-ubuntu
_Platform	_{linux 4.4.0-210-generic}
_Architecture	_x64
_{Available Memory}	_{16 GB}
_{Available Memory}	_{9 GB}
_CPUs	_{4 × Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz}

Hosts

node (v10.16.3, x64)
node (v12.1.0, x64)
node (v14.15.1, x64)

Scenarios

Angular - node (v10.16.3, x64)
Angular - node (v12.1.0, x64)
Angular - node (v14.15.1, x64)
Compiler-Unions - node (v10.16.3, x64)
Compiler-Unions - node (v12.1.0, x64)
Compiler-Unions - node (v14.15.1, x64)
Monaco - node (v10.16.3, x64)
Monaco - node (v12.1.0, x64)
Monaco - node (v14.15.1, x64)
TFS - node (v10.16.3, x64)
TFS - node (v12.1.0, x64)
TFS - node (v14.15.1, x64)
material-ui - node (v10.16.3, x64)
material-ui - node (v12.1.0, x64)
material-ui - node (v14.15.1, x64)

_Benchmark	_Name	_Iterations
_Current	₄₅₇₁₁	₁₀
_Baseline	_main	₁₀

Developer Information:

Download Benchmark

DanielRosenwasser · 2021-09-03T17:23:58Z

I can't tell how much of this in the noise, but the check time on material-ui does seem like it's taken a hit across all versions.

ahejlsberg · 2021-09-04T21:39:32Z

@typescript-bot perf test this

typescript-bot · 2021-09-04T21:39:34Z

Heya @ahejlsberg, I've started to run the perf test suite on this PR at a4224d6. You can monitor the build here.

Update: The results are in!

typescript-bot · 2021-09-04T22:15:20Z

@ahejlsberg
The results of the perf run you requested are in!

Here they are:

Comparison Report - main..45711

_Metric	_main	₄₅₇₁₁	_Delta	_Best	_Worst
_{Angular - node (v10.16.3, x64)}
_{Memory used}	_{351,498k (± 0.02%)}	_{351,568k (± 0.02%)}	_{+70k (+ 0.02%)}	_351,360k	_351,643k
_{Parse Time}	_{1.90s (± 0.34%)}	_{1.91s (± 0.68%)}	_{+0.01s (+ 0.63%)}	_1.89s	_1.94s
_{Bind Time}	_{0.85s (± 0.76%)}	_{0.86s (± 0.69%)}	_{+0.01s (+ 0.94%)}	_0.85s	_0.87s
_{Check Time}	_{5.40s (± 0.45%)}	_{5.41s (± 0.37%)}	_{+0.01s (+ 0.24%)}	_5.36s	_5.47s
_{Emit Time}	_{5.83s (± 0.29%)}	_{5.86s (± 0.64%)}	_{+0.03s (+ 0.55%)}	_5.77s	_5.95s
_{Total Time}	_{13.97s (± 0.26%)}	_{14.04s (± 0.38%)}	_{+0.07s (+ 0.48%)}	_13.88s	_14.14s
_{Compiler-Unions - node (v10.16.3, x64)}
_{Memory used}	_{203,519k (± 0.04%)}	_{203,445k (± 0.03%)}	_{-74k (- 0.04%)}	_203,329k	_203,611k
_{Parse Time}	_{0.78s (± 0.85%)}	_{0.79s (± 0.89%)}	_{+0.01s (+ 1.15%)}	_0.77s	_0.80s
_{Bind Time}	_{0.52s (± 1.43%)}	_{0.52s (± 1.66%)}	_{-0.00s (- 0.19%)}	_0.51s	_0.54s
_{Check Time}	_{7.84s (± 0.50%)}	_{7.89s (± 0.64%)}	_{+0.05s (+ 0.66%)}	_7.76s	_7.99s
_{Emit Time}	_{2.44s (± 0.70%)}	_{2.46s (± 0.74%)}	_{+0.02s (+ 0.61%)}	_2.42s	_2.49s
_{Total Time}	_{11.58s (± 0.37%)}	_{11.65s (± 0.54%)}	_{+0.07s (+ 0.60%)}	_11.51s	_11.77s
_{Monaco - node (v10.16.3, x64)}
_{Memory used}	_{340,627k (± 0.03%)}	_{340,619k (± 0.02%)}	_{-9k (- 0.00%)}	_340,464k	_340,827k
_{Parse Time}	_{1.45s (± 0.90%)}	_{1.46s (± 0.46%)}	_{+0.01s (+ 0.76%)}	_1.44s	_1.47s
_{Bind Time}	_{0.75s (± 1.07%)}	_{0.75s (± 0.60%)}	_{0.00s ( 0.00%)}	_0.74s	_0.76s
_{Check Time}	_{5.44s (± 0.60%)}	_{5.41s (± 0.72%)}	_{-0.03s (- 0.50%)}	_5.31s	_5.49s
_{Emit Time}	_{3.16s (± 0.86%)}	_{3.16s (± 1.04%)}	_{+0.01s (+ 0.25%)}	_3.11s	_3.26s
_{Total Time}	_{10.79s (± 0.44%)}	_{10.78s (± 0.29%)}	_{-0.01s (- 0.05%)}	_10.71s	_10.86s
_{TFS - node (v10.16.3, x64)}
_{Memory used}	_{303,979k (± 0.03%)}	_{304,033k (± 0.02%)}	_{+55k (+ 0.02%)}	_303,923k	_304,196k
_{Parse Time}	_{1.18s (± 0.59%)}	_{1.18s (± 0.31%)}	_{+0.00s (+ 0.25%)}	_1.18s	_1.19s
_{Bind Time}	_{0.71s (± 0.52%)}	_{0.71s (± 0.69%)}	_{-0.00s (- 0.14%)}	_0.71s	_0.73s
_{Check Time}	_{4.92s (± 0.65%)}	_{4.93s (± 0.43%)}	_{+0.01s (+ 0.20%)}	_4.89s	_4.97s
_{Emit Time}	_{3.32s (± 1.36%)}	_{3.32s (± 1.45%)}	_{+0.00s (+ 0.06%)}	_3.22s	_3.43s
_{Total Time}	_{10.13s (± 0.60%)}	_{10.15s (± 0.56%)}	_{+0.01s (+ 0.13%)}	_10.00s	_10.28s
_{material-ui - node (v10.16.3, x64)}
_{Memory used}	_{469,920k (± 0.02%)}	_{469,714k (± 0.01%)}	_{-207k (- 0.04%)}	_469,641k	_469,788k
_{Parse Time}	_{1.73s (± 0.70%)}	_{1.74s (± 0.61%)}	_{+0.01s (+ 0.35%)}	_1.72s	_1.76s
_{Bind Time}	_{0.66s (± 0.45%)}	_{0.67s (± 0.67%)}	_{+0.01s (+ 0.91%)}	_0.66s	_0.68s
_{Check Time}	_{14.19s (± 0.63%)}	_{14.44s (± 0.92%)}	_{+0.25s (+ 1.76%)}	_14.17s	_14.71s
_{Emit Time}	_{0.00s (± 0.00%)}	_{0.00s (± 0.00%)}	_{0.00s ( NaN%)}	_0.00s	_0.00s
_{Total Time}	_{16.59s (± 0.55%)}	_{16.85s (± 0.85%)}	_{+0.26s (+ 1.56%)}	_16.57s	_17.15s
_{Angular - node (v12.1.0, x64)}
_{Memory used}	_{329,562k (± 0.02%)}	_{329,438k (± 0.08%)}	_{-124k (- 0.04%)}	_328,468k	_329,679k
_{Parse Time}	_{1.89s (± 0.82%)}	_{1.89s (± 0.77%)}	_{+0.00s (+ 0.05%)}	_1.86s	_1.92s
_{Bind Time}	_{0.84s (± 0.95%)}	_{0.84s (± 0.79%)}	_{+0.00s (+ 0.12%)}	_0.83s	_0.86s
_{Check Time}	_{5.25s (± 0.64%)}	_{5.28s (± 0.93%)}	_{+0.03s (+ 0.50%)}	_5.14s	_5.34s
_{Emit Time}	_{6.08s (± 0.55%)}	_{6.11s (± 0.53%)}	_{+0.03s (+ 0.54%)}	_6.02s	_6.17s
_{Total Time}	_{14.06s (± 0.43%)}	_{14.12s (± 0.57%)}	_{+0.06s (+ 0.43%)}	_13.92s	_14.24s
_{Compiler-Unions - node (v12.1.0, x64)}
_{Memory used}	_{190,701k (± 0.32%)}	_{190,839k (± 0.13%)}	_{+137k (+ 0.07%)}	_190,261k	_191,234k
_{Parse Time}	_{0.78s (± 0.77%)}	_{0.78s (± 0.85%)}	_{+0.00s (+ 0.52%)}	_0.77s	_0.80s
_{Bind Time}	_{0.54s (± 0.92%)}	_{0.53s (± 0.84%)}	_{-0.00s (- 0.75%)}	_0.53s	_0.55s
_{Check Time}	_{7.41s (± 0.69%)}	_{7.42s (± 0.79%)}	_{+0.01s (+ 0.18%)}	_7.26s	_7.54s
_{Emit Time}	_{2.46s (± 1.08%)}	_{2.47s (± 0.92%)}	_{+0.01s (+ 0.61%)}	_2.43s	_2.53s
_{Total Time}	_{11.17s (± 0.46%)}	_{11.20s (± 0.59%)}	_{+0.03s (+ 0.26%)}	_11.02s	_11.35s
_{Monaco - node (v12.1.0, x64)}
_{Memory used}	_{323,777k (± 0.02%)}	_{323,810k (± 0.02%)}	_{+33k (+ 0.01%)}	_323,637k	_323,961k
_{Parse Time}	_{1.43s (± 0.61%)}	_{1.44s (± 0.77%)}	_{+0.01s (+ 0.63%)}	_1.42s	_1.46s
_{Bind Time}	_{0.73s (± 0.50%)}	_{0.73s (± 0.41%)}	_{+0.01s (+ 0.83%)}	_0.73s	_0.74s
_{Check Time}	_{5.30s (± 0.34%)}	_{5.32s (± 0.75%)}	_{+0.02s (+ 0.38%)}	_5.23s	_5.43s
_{Emit Time}	_{3.19s (± 0.71%)}	_{3.19s (± 0.63%)}	_{-0.01s (- 0.22%)}	_3.15s	_3.24s
_{Total Time}	_{10.65s (± 0.16%)}	_{10.68s (± 0.60%)}	_{+0.02s (+ 0.23%)}	_10.52s	_10.83s
_{TFS - node (v12.1.0, x64)}
_{Memory used}	_{288,768k (± 0.02%)}	_{288,762k (± 0.02%)}	_{-6k (- 0.00%)}	_288,621k	_288,915k
_{Parse Time}	_{1.21s (± 0.72%)}	_{1.22s (± 0.83%)}	_{+0.01s (+ 0.66%)}	_1.20s	_1.24s
_{Bind Time}	_{0.71s (± 1.36%)}	_{0.70s (± 1.18%)}	_{-0.00s (- 0.56%)}	_0.69s	_0.72s
_{Check Time}	_{4.87s (± 0.49%)}	_{4.87s (± 0.29%)}	_{+0.01s (+ 0.12%)}	_4.85s	_4.90s
_{Emit Time}	_{3.39s (± 1.13%)}	_{3.38s (± 0.61%)}	_{-0.01s (- 0.32%)}	_3.32s	_3.42s
_{Total Time}	_{10.17s (± 0.63%)}	_{10.17s (± 0.25%)}	_{+0.00s (+ 0.04%)}	_10.10s	_10.23s
_{material-ui - node (v12.1.0, x64)}
_{Memory used}	_{448,584k (± 0.02%)}	_{448,412k (± 0.06%)}	_{-172k (- 0.04%)}	_447,378k	_448,617k
_{Parse Time}	_{1.72s (± 0.62%)}	_{1.73s (± 0.64%)}	_{+0.01s (+ 0.64%)}	_1.70s	_1.75s
_{Bind Time}	_{0.65s (± 0.90%)}	_{0.65s (± 1.02%)}	_{+0.01s (+ 0.93%)}	_0.63s	_0.66s
_{Check Time}	_{12.85s (± 0.43%)}	_{13.00s (± 0.75%)}	_{+0.15s (+ 1.14%)}	_12.79s	_13.19s
_{Emit Time}	_{0.00s (± 0.00%)}	_{0.00s (± 0.00%)}	_{0.00s ( NaN%)}	_0.00s	_0.00s
_{Total Time}	_{15.22s (± 0.32%)}	_{15.38s (± 0.66%)}	_{+0.16s (+ 1.08%)}	_15.15s	_15.59s
_{Angular - node (v14.15.1, x64)}
_{Memory used}	_{328,088k (± 0.01%)}	_{328,103k (± 0.01%)}	_{+15k (+ 0.00%)}	_328,050k	_328,149k
_{Parse Time}	_{1.90s (± 0.73%)}	_{1.91s (± 0.64%)}	_{+0.01s (+ 0.63%)}	_1.89s	_1.94s
_{Bind Time}	_{0.88s (± 0.51%)}	_{0.88s (± 0.93%)}	_{+0.00s (+ 0.11%)}	_0.87s	_0.91s
_{Check Time}	_{5.30s (± 0.76%)}	_{5.32s (± 0.67%)}	_{+0.02s (+ 0.32%)}	_5.24s	_5.43s
_{Emit Time}	_{6.22s (± 0.72%)}	_{6.18s (± 0.70%)}	_{-0.04s (- 0.71%)}	_6.11s	_6.31s
_{Total Time}	_{14.30s (± 0.51%)}	_{14.29s (± 0.54%)}	_{-0.01s (- 0.09%)}	_14.18s	_14.55s
_{Compiler-Unions - node (v14.15.1, x64)}
_{Memory used}	_{191,742k (± 0.55%)}	_{192,190k (± 0.49%)}	_{+448k (+ 0.23%)}	_189,614k	_192,907k
_{Parse Time}	_{0.81s (± 0.92%)}	_{0.81s (± 0.45%)}	_{-0.00s (- 0.12%)}	_0.80s	_0.81s
_{Bind Time}	_{0.56s (± 0.85%)}	_{0.56s (± 0.99%)}	_{+0.01s (+ 0.90%)}	_0.55s	_0.58s
_{Check Time}	_{7.55s (± 0.61%)}	_{7.55s (± 0.52%)}	_{-0.00s (- 0.03%)}	_7.49s	_7.68s
_{Emit Time}	_{2.48s (± 1.01%)}	_{2.46s (± 0.82%)}	_{-0.02s (- 0.73%)}	_2.41s	_2.49s
_{Total Time}	_{11.39s (± 0.32%)}	_{11.37s (± 0.48%)}	_{-0.02s (- 0.16%)}	_11.27s	_11.54s
_{Monaco - node (v14.15.1, x64)}
_{Memory used}	_{322,540k (± 0.00%)}	_{322,541k (± 0.00%)}	_{+1k (+ 0.00%)}	_322,511k	_322,563k
_{Parse Time}	_{1.48s (± 0.68%)}	_{1.49s (± 0.67%)}	_{+0.00s (+ 0.20%)}	_1.47s	_1.51s
_{Bind Time}	_{0.76s (± 0.66%)}	_{0.76s (± 0.99%)}	_{+0.00s (+ 0.26%)}	_0.75s	_0.78s
_{Check Time}	_{5.23s (± 0.43%)}	_{5.23s (± 0.51%)}	_{+0.01s (+ 0.13%)}	_5.19s	_5.29s
_{Emit Time}	_{3.21s (± 0.69%)}	_{3.24s (± 1.03%)}	_{+0.02s (+ 0.72%)}	_3.18s	_3.31s
_{Total Time}	_{10.68s (± 0.34%)}	_{10.72s (± 0.42%)}	_{+0.03s (+ 0.32%)}	_10.63s	_10.82s
_{TFS - node (v14.15.1, x64)}
_{Memory used}	_{287,700k (± 0.01%)}	_{287,713k (± 0.01%)}	_{+13k (+ 0.00%)}	_287,663k	_287,761k
_{Parse Time}	_{1.26s (± 2.81%)}	_{1.26s (± 2.13%)}	_{+0.00s (+ 0.24%)}	_1.21s	_1.33s
_{Bind Time}	_{0.73s (± 1.27%)}	_{0.73s (± 1.11%)}	_{+0.00s (+ 0.27%)}	_0.72s	_0.75s
_{Check Time}	_{4.87s (± 0.35%)}	_{4.91s (± 0.46%)}	_{+0.04s (+ 0.76%)}	_4.84s	_4.97s
_{Emit Time}	_{3.47s (± 0.77%)}	_{3.49s (± 0.84%)}	_{+0.02s (+ 0.72%)}	_3.43s	_3.57s
_{Total Time}	_{10.32s (± 0.42%)}	_{10.38s (± 0.43%)}	_{+0.07s (+ 0.65%)}	_10.27s	_10.46s
_{material-ui - node (v14.15.1, x64)}
_{Memory used}	_{447,030k (± 0.01%)}	_{446,950k (± 0.00%)}	_{-80k (- 0.02%)}	_446,922k	_446,990k
_{Parse Time}	_{1.76s (± 0.48%)}	_{1.77s (± 0.33%)}	_{+0.01s (+ 0.63%)}	_1.76s	_1.78s
_{Bind Time}	_{0.69s (± 0.58%)}	_{0.69s (± 0.49%)}	_{+0.00s (+ 0.29%)}	_0.69s	_0.70s
_{Check Time}	_{13.02s (± 0.60%)}	_{13.13s (± 0.71%)}	_{+0.12s (+ 0.88%)}	_12.87s	_13.26s
_{Emit Time}	_{0.00s (± 0.00%)}	_{0.00s (± 0.00%)}	_{0.00s ( NaN%)}	_0.00s	_0.00s
_{Total Time}	_{15.47s (± 0.50%)}	_{15.59s (± 0.59%)}	_{+0.13s (+ 0.83%)}	_15.33s	_15.72s

System

_{Machine Name}	_ts-ci-ubuntu
_Platform	_{linux 4.4.0-210-generic}
_Architecture	_x64
_{Available Memory}	_{16 GB}
_{Available Memory}	_{9 GB}
_CPUs	_{4 × Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz}

Hosts

node (v10.16.3, x64)
node (v12.1.0, x64)
node (v14.15.1, x64)

Scenarios

Angular - node (v10.16.3, x64)
Angular - node (v12.1.0, x64)
Angular - node (v14.15.1, x64)
Compiler-Unions - node (v10.16.3, x64)
Compiler-Unions - node (v12.1.0, x64)
Compiler-Unions - node (v14.15.1, x64)
Monaco - node (v10.16.3, x64)
Monaco - node (v12.1.0, x64)
Monaco - node (v14.15.1, x64)
TFS - node (v10.16.3, x64)
TFS - node (v12.1.0, x64)
TFS - node (v14.15.1, x64)
material-ui - node (v10.16.3, x64)
material-ui - node (v12.1.0, x64)
material-ui - node (v14.15.1, x64)

_Benchmark	_Name	_Iterations
_Current	₄₅₇₁₁	₁₀
_Baseline	_main	₁₀

Developer Information:

Download Benchmark

ahejlsberg · 2021-09-08T22:41:24Z

Changed the tail recursion logic to bypass caching since it is effectively just computing temporary results. There's still a slight slowdown in material-ui (<1%), but generally I think not caching in the tail recursion loop is the best approach.

mgreenw · 2021-09-24T13:49:18Z

@ahejlsberg Thanks for this work! Using 4.4.3, I just hit the instantiationDepth === 50 limit (literally just 50, nothing above that) on a project I am working on.

Because it is possible / even likely to hit this depth limit of 50 with tuple types and template literal types in 4.4, I'm wondering if it would be possible to backport the instantiationDepth === 100 limit to a new patch release of 4.4 without including this tail recursive evaluation strategy This would mitigate the issue until 4.5 is released with this new (awesome) work. Let me know if you think this would be possible / a good idea. Thanks!

- TypeScript currently permits up to 1000 recursive loops. - See: microsoft/TypeScript#45711

ahejlsberg added 2 commits September 2, 2021 10:10

Implement tail-recursion for conditional types and lower general inst…

1610e19

…antiation depth limit to 100

Add tests

093f76a

typescript-bot assigned ahejlsberg Sep 3, 2021

typescript-bot added Author: Team For Uncommitted Bug PR for untriaged, rejected, closed or missing bug labels Sep 3, 2021

ahejlsberg requested review from andrewbranch, DanielRosenwasser and weswigham September 3, 2021 15:39

ahejlsberg added this to the TypeScript 4.5.0 milestone Sep 3, 2021

weswigham approved these changes Sep 3, 2021

View reviewed changes

typescript-bot mentioned this pull request Sep 3, 2021

🤖 User test baselines have changed for tailRecursiveConditionals typescript-bot/TypeScript#204

Open

DanielRosenwasser mentioned this pull request Sep 3, 2021

Design Meeting Notes, 9/3/2021 #45718

Closed

nandorojo mentioned this pull request Sep 4, 2021

Support dotted path notation millsp/ts-toolbelt#154

Closed

Skip caching for tail recursive temporary conditional types

a4224d6

ahejlsberg merged commit b9eeb74 into main Sep 8, 2021

ahejlsberg deleted the tailRecursiveConditionals branch September 8, 2021 22:42

renovate bot mentioned this pull request Sep 23, 2021

fix(deps): update dependency ts-pattern to v3.3.3 natelindev/vlepo#118

Merged

1 task

nandorojo mentioned this pull request Sep 27, 2021

Custom theme-based TypeScript Intellisense nandorojo/dripsy#6

Closed

renovate bot mentioned this pull request Oct 1, 2021

Update dependency ts-pattern to v3.3.3 taneba/fullstack-graphql-app#98

Merged

1 task

somebody1234 mentioned this pull request Oct 3, 2021

2257 - MinusOne type-challenges/type-challenges#2563

Open

This was referenced Oct 3, 2021

flag to customize type instantiation depth limit #46180

Closed

rewrite recursive conditional types to be tail-recursive millsp/ts-toolbelt#255

Open

rewrite recursive conditional types to be tail-recursive millsp/ts-toolbelt#256

Draft

getTobiasNielsen mentioned this pull request Oct 6, 2021

[Bug]: Regression: TS2589: Type instantiation is excessively deep and possibly infinite react-hook-form/react-hook-form#6679

Closed

1 task

timkendall mentioned this pull request Nov 5, 2021

TypeScript 4.5 Recursive type tail recursion timkendall/tql#86

Closed

samchon mentioned this pull request Nov 25, 2021

Critical change from the TypeScript@4.5 samchon/safe-typeorm#46

Closed

renovate bot mentioned this pull request Dec 11, 2021

chore(deps): update dependency ts-pattern to v3 strong-roots-capital/od#87

Merged

1 task

crazyones110 mentioned this pull request Dec 21, 2021

Feature request: Ability to parse a stringified number on type-level #47141

Closed

5 tasks

renovate bot mentioned this pull request Apr 2, 2022

chore(deps): update dependency ts-pattern to v4 strong-roots-capital/percentage-change#42

Merged

1 task

swimmie0 mentioned this pull request May 17, 2022

531 - String to Union swimmie0/type-challenges#1

Open

zhaoyao91 mentioned this pull request Nov 18, 2022

2257 - MinusOne with 2 versions and explanatations type-challenges/type-challenges#19437

Open

MajorLift added a commit to MajorLift/type-challenges that referenced this pull request Jan 6, 2023

test: input of length 999

8892219

- TypeScript currently permits up to 1000 recursive loops. - See: microsoft/TypeScript#45711

MajorLift mentioned this pull request Jan 6, 2023

test: 00651-hard-length-of-string-2 input of length 999 type-challenges/type-challenges#21603

Merged

Dragon-Hatcher mentioned this pull request Jun 24, 2023

Increase type instantiation depth limit #45025

Merged

deathemperor mentioned this pull request Jan 30, 2024

Increase tail-recursive conditional types from 50 to 1000 for variables 0no-co/gql.tada#46

Closed

ENvironmentSet mentioned this pull request Feb 10, 2024

Tail recursion optimization limit 999 may be manipulated #49459

Open

buqiyuan mentioned this pull request Feb 14, 2024

Type instantiation is excessively deep and possibly infinite nestjs/nest#13210

Closed

15 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Tail recursive evaluation of conditional types #45711

Tail recursive evaluation of conditional types #45711

ahejlsberg commented Sep 3, 2021 •

edited

Loading

Uh oh!

ahejlsberg commented Sep 3, 2021

Uh oh!

typescript-bot commented Sep 3, 2021 •

edited

Loading

Uh oh!

typescript-bot commented Sep 3, 2021 •

edited

Loading

Uh oh!

typescript-bot commented Sep 3, 2021 •

edited

Loading

Uh oh!

typescript-bot commented Sep 3, 2021 •

edited

Loading

Uh oh!

weswigham left a comment

Uh oh!

typescript-bot commented Sep 3, 2021

Uh oh!

typescript-bot commented Sep 3, 2021

Uh oh!

DanielRosenwasser commented Sep 3, 2021

Uh oh!

ahejlsberg commented Sep 4, 2021

Uh oh!

typescript-bot commented Sep 4, 2021 •

edited

Loading

Uh oh!

typescript-bot commented Sep 4, 2021

Uh oh!

ahejlsberg commented Sep 8, 2021

Uh oh!

mgreenw commented Sep 24, 2021 •

edited

Loading

Uh oh!

Uh oh!

Tail recursive evaluation of conditional types #45711

Tail recursive evaluation of conditional types #45711

Conversation

ahejlsberg commented Sep 3, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ahejlsberg commented Sep 3, 2021

Uh oh!

typescript-bot commented Sep 3, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

typescript-bot commented Sep 3, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

typescript-bot commented Sep 3, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

typescript-bot commented Sep 3, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

weswigham left a comment

Choose a reason for hiding this comment

Uh oh!

typescript-bot commented Sep 3, 2021

Uh oh!

typescript-bot commented Sep 3, 2021

Uh oh!

DanielRosenwasser commented Sep 3, 2021

Uh oh!

ahejlsberg commented Sep 4, 2021

Uh oh!

typescript-bot commented Sep 4, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

typescript-bot commented Sep 4, 2021

Uh oh!

ahejlsberg commented Sep 8, 2021

Uh oh!

mgreenw commented Sep 24, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

ahejlsberg commented Sep 3, 2021 •

edited

Loading

typescript-bot commented Sep 3, 2021 •

edited

Loading

typescript-bot commented Sep 3, 2021 •

edited

Loading

typescript-bot commented Sep 3, 2021 •

edited

Loading

typescript-bot commented Sep 3, 2021 •

edited

Loading

typescript-bot commented Sep 4, 2021 •

edited

Loading

mgreenw commented Sep 24, 2021 •

edited

Loading