Recursive conditional types seem to hang experience #40369
Description
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;