Typescript: Recursive conditional types seem to hang experience

[DanielRosenwasser]

https://en.wikipedia.org/wiki/Collatz_conjecture

So the following does not hang TypeScript nightly

type Unary = ReadonlyArray<1>;
type UZero = [];

type UIncr<U extends Unary> = [1, ...U];
type UDecr<U extends Unary> = U extends UIncr<infer U1> ? U1 : never;

type UOne = UIncr<UZero>;

type Collatz<T extends Unary> = T extends UOne ? UOne : HailstoneHelper<T, UZero, T>;

type TimesThreePlusOne<T extends Unary> = UIncr<[...T, ...T, ...T]>;
type HailstoneHelper<Orig extends Unary, HalfAccum extends Unary, Curr extends Unary> =
    Curr extends UZero ? HalfAccum :
    Curr extends UOne ? Collatz<TimesThreePlusOne<Orig>> :
    Collatz<HailstoneHelper<Orig, UIncr<HalfAccum>, UDecr<UDecr<Curr>>>>;
//  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Type instantiation is excessively deep and possibly infinite.(2589)

But introducing a trailing conditional type will cause the following example to seemingly never end:

type Unary = ReadonlyArray<1>;
type UZero = [];

type UIncr<U extends Unary> = [1, ...U];
type UDecr<U extends Unary> = U extends UIncr<infer U1> ? U1 : never;

type UOne = UIncr<UZero>;

type Collatz<T extends Unary> = T extends UOne ? UOne : HailstoneHelper<T, UZero, T>;

type TimesThreePlusOne<T extends Unary> = UIncr<[...T, ...T, ...T]>;
type HailstoneHelper<Orig extends Unary, HalfAccum extends Unary, Curr extends Unary> =
    Curr extends UZero ? HalfAccum :
    Curr extends UOne ? Collatz<TimesThreePlusOne<Orig>> :
    Curr extends [any, any, ...any[]] ? Collatz<HailstoneHelper<Orig, UIncr<HalfAccum>, UDecr<UDecr<Curr>>> :
    never;

Playground link

[ahejlsberg]

Just took a quick look. It appears we're making bunches of _very_ large tuple types, as in >250,000 elements. We should probably have a limiter in place to cut off the madness at 10,000 elements or so.

[ahejlsberg]

Actually, doesn't look like it was large tuple types, but rather large type caches I was looking at. Anyways, your seemingly never ending example actually does end after about a minute on my machine:

t.ts:15:41 - error TS2589: Type instantiation is excessively deep and possibly infinite.

15     Curr extends [any, any, ...any[]] ? Collatz<HailstoneHelper<Orig, UIncr<HalfAccum>, UDecr<UDecr<Curr>>>> :
                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Found 1 error.

Files:                6
Lines:            24890
Nodes:           112786
Identifiers:      41026
Symbols:          33488
Types:          1675473
Instantiations: 5000043
Memory used:    379488K
I/O read:         0.00s
I/O write:        0.00s
Parse time:       0.34s
Bind time:        0.14s
Check time:      57.77s
Emit time:        0.01s
Total time:      58.26s

Also, according to Wikipedia

Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems."[8] He also offered US$500 for its solution.[9] Jeffrey Lagarias in 2010 claimed that based only on known information about this problem, "this is an extraordinarily difficult problem, completely out of reach of present day mathematics."[10]

What makes you think our type checker will do better? 😉

[DanielRosenwasser]

I will edit the Wikipedia article appropriately:

Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems."[8] He also offered US$500 for its solution.[9] Jeffrey Lagarias in 2010 claimed that based only on known information about this problem, "this is an extraordinarily difficult problem, completely out of reach of present day mathematics."[10] In 2020, Anders Hejlsberg said of the conjecture, "Type instantiation is excessively deep and possibly infinite."

[ahejlsberg]

@DanielRosenwasser So when do I get my $500?

[ahejlsberg]

Marking this as working as intended. It is indeed possible to write types that take a very long time to resolve and/or relate.