Type checker hangs on recursive type with arrays

[judofyr]

TypeScript Version: 4.1.2

Search Terms:

Code

type BuildTuple<L extends number, T extends any[] = [any]> = 
    T['length'] extends L ? T : BuildTuple<L, [...T, ...T]>;

type A = BuildTuple<3>

Expected behavior:

The type checker completes in a reasonable time, either by succeeding or by reporting "Type instantiation is excessively deep and possibly infinite".

Actual behavior:

The type checker just hangs.

Playground Link:

https://www.typescriptlang.org/play?ts=4.1.2#code/C4TwDgpgBAQgrgSwDYBMAqcxIgHgDJQQAewEAdigM5RlwC2ARhAE4A0UahJ5VUAhmRABtALpQAvFCECQIgHwSoAKCiqOQgOTYyAc2AALDWOKkK1AgH4OUAFyxEqDFlx52QgHSe07T+7TyAbiUlUEgoAEFFeGR0TGwcAGY5JSA

[andrewbranch]

Hmm, so the problem is that every time we instantiate the false type, the length of the T argument doubles because of the two spreads. The instantiation depth limit is 50, which means by the time we hit it, we’re dealing with a tuple with length 2⁵⁰ ≈ 1.13×10¹⁵, which is a pretty long tuple. (I assume this does eventually terminate by running out of memory, but didn’t feel like sticking around to see how long that takes.)

Should there just be a limit on how many elements we’ll try to spread into a tuple? If we hit that limit, do we issue an error or create an array instead?