TSServer hangs when using recursive types on tuples and pressing ","

[AlCalzone]

Disclaimer: This is probably not intended use of the type system but it might show an underlying issue so I still report it.

TypeScript Version: 3.1.0-dev.20180802

Search Terms: recursive conditional type tuple freeze

Code
While experimenting with the examples found in #24897 (comment), I noticed some weird behavior when it comes to recursive types. Apparently tail recursion on type members seems to work, which means it can be used to create crazy types like Reverse:

/**
 * Returns the first item's type in a tuple
 */
export type Head<T extends any[]> =
	T extends [infer H, ...any[]] ? H : never;

/**
 * Returns all but the first item's type in a tuple/array
 */
export type Tail<T extends any[]> =
	((...args: T) => any) extends ((head: any, ...tail: infer R) => any) ? R : never;

/**
 * Returns the given tuple/array with the item type prepended to it
 */
export type Unshift<List extends any[], Item> =
	((first: Item, ...rest: List) => any) extends ((...list: infer R) => any) ? R : never;

/** Reverses the given list */
export type Reverse<List extends any[]> = _Reverse<List, []>;

export type _Reverse<Source extends any[], Result extends any[] = []> = {
	// If the source list is empty, return the result
	1: Result,
	// else prepend the head of source to the result list and
	// continue recursion with the tail of the source
	0: _Reverse<Tail<Source>, Unshift<Result, Head<Source>>>,
}[Source extends [] ? 1 : 0];

When opening a file where that type is used, VSCode's Intellisense shows the correct type after a minor delay:

type Foo = Reverse<[1, 2, 3]>; // [3, 2, 1]
const f: Foo = [2, 1]; // error: 2 is not assignable to 3

After adding a comma after the 3 in the recursive type, TSServers comes to a halt (1 core with full CPU usage).

type Foo = Reverse<[1, 2, 3,]>; // FREEZE

However, if I paste a comma and a number from somewhere else in a single operation, it works just fine:

type Foo = Reverse<[1, 2, 3,4]>; // ",4" pasted from somewhere => all good!

The same thing happens when changing a type to this recursive type

// start here
type Foo = [1, 2, 3];
// change to this:
type Foo = Reverse<[1, 2, 3]; // broken

but not doing it in this order:

// start here
type Foo = [1, 2, 3];
// change to this:
type Foo = <[1, 2, 3]>;
// then to this:
type Foo = Reverse<[1, 2, 3]>; // all good!

Related Issues: #24897

[ghost]

Reproduced in a fourslash test:

/// <reference path='fourslash.ts'/>

////type Tail<T extends any[]> =
////	((...args: T) => any) extends ((head: any, ...tail: infer R) => any) ? R : never;
////
////type Reverse<List extends any[]> = _Reverse<List, []>;
////
////type _Reverse<Source extends any[], Result extends any[] = []> = {
////	1: Result,
////	0: _Reverse<Tail<Source>, 0>,
////}[Source extends [] ? 1 : 0];
////
////type Foo = Reverse<[0,/**/]>;

verify.signatureHelp({
    marker: "",
    text: "?",
});

[AlCalzone]

Potentially relevant: While the process hangs, its RAM usage continues to rise - as if its building some infinite signature help or something like that.

[KiaraGrouwstra]

afaik TS did do stuff on trailing comma for Intellisense purposes... not sure what's happening here though.

[AlCalzone]

I might have a clue whats going on behind the scenes. Using [email protected] and the following code:

/**
 * Returns the length of an array or tuple
 */
export type LengthOf<T extends any[]> = T["length"];

/**
 * Returns the logarithm to the base 2 of the (L + 1)
 */
export type Magnitude<L> =
	number extends L ? never : (
		L extends 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 ?
		L extends 0 | 1 | 2 | 3 ?
		L extends 0 | 1 ?
		L extends 0 ?
		0 : 1 : 2 : 3 : 4
	);

// Drop the first N items of T
type Drop1<T extends any[]> = ((...args: T) => void) extends ((a1: any, ...rest: infer R) => void) ? R : never;
type Drop2<T extends any[]> = ((...args: T) => void) extends ((a1: any, a2: any, ...rest: infer R) => void) ? R : never;
type Drop4<T extends any[]> = ((...args: T) => void) extends ((a1: any, a2: any, a3: any, a4: any, ...rest: infer R) => void) ? R : never;
type Drop8<T extends any[]> = ((...args: T) => void) extends ((a1: any, a2: any, a3: any, a4: any, a5: any, a6: any, a7: any, a8: any, ...rest: infer R) => void) ? R : never;

// Take the first N items of T1, reverse them and prepend them to T2
type ConcatReverse1<T1 extends any[], T2 extends any[]> = ((a1: T1[0], ...rest: T2) => void) extends ((...args: infer R) => void) ? R : never;
type ConcatReverse2<T1 extends any[], T2 extends any[]> = ((a2: T1[1], a1: T1[0], ...rest: T2) => void) extends ((...args: infer R) => void) ? R : never;
type ConcatReverse4<T1 extends any[], T2 extends any[]> = ((a4: T1[3], a3: T1[2], a2: T1[1], a1: T1[0], ...rest: T2) => void) extends ((...args: infer R) => void) ? R : never;
type ConcatReverse8<T1 extends any[], T2 extends any[]> = ((a8: T1[7], a7: T1[6], a6: T1[5], a5: T1[4], a4: T1[3], a3: T1[2], a2: T1[1], a1: T1[0], ...rest: T2) => void) extends ((...args: infer R) => void) ? R : never;

export type ConcatReverse<
	T1 extends any[], T2 extends any[]=[]
	> = {
		0: T2,
		// depending on the length of T1, take the first half of T1,
		// and prepend it to T2 in a reversed order
		1: ConcatReverse<Drop1<T1>, ConcatReverse1<T1, T2>>,
		2: ConcatReverse<Drop2<T1>, ConcatReverse2<T1, T2>>,
		3: ConcatReverse<Drop4<T1>, ConcatReverse4<T1, T2>>,
		4: ConcatReverse<Drop8<T1>, ConcatReverse8<T1, T2>>,
	}[Magnitude<T1["length"]>];

/**
 * Reverses the given list
 * WARNING: Use at your own risk, this might crash TypeScript
 */
export type Reverse<T extends any[]> = ConcatReverse<T>;

type DropLast<
	T extends any[],
	U extends any[] = Reverse<T>, // error here, but it works!
	V extends any[] = Drop1<U>,
	W extends any[] = Reverse<V>
> = W;
type Foo = DropLast<[1, 2, 3, 4, 5]>;

Intellisense shows an error on the two lines using Reverse<>:

Apparently, a huge type is generated behind the scenes even without any parameters being provided

[AlCalzone]

Update: Using [email protected], the original code no longer completely freezes the language server. It's still incredibly slow, but works.

[AlCalzone]

@sheetalkamat @RyanCavanaugh
Do you consider this as fixed? If so, what about the HUGE type generated in my last example? That does not seem intended. Should I open another issue for that?

[sheetalkamat]

with typescript@next there is no huge type generated that I can repro with your example.

[AlCalzone]

That seems to be because ConcatReverse is now never (using today's typescript@next).

When replacing the now no longer functional version of that type with a naive implementation that just loops the tuple, there is still a large type generated without any passed type arguments. Although it is not as huge as it used to be:

export type Unshift<List extends any[], Item> =
	((first: Item, ...rest: List) => any) extends ((...list: infer R) => any) ? R : never;

type ReverseNaive<
	Source extends any[], Target extends any[]=[],
	L extends number = LengthOf<Source>,
	Left extends any[]= Drop1<Source>,
	Right extends any[]= Unshift<Target, Source[0]>,
	> = {
		0: Target,
		1: ReverseNaive<Left, Right>,
	}[Source["length"] extends 0 ? 0 : 1];

type DropLast<
	T extends any[],
	U extends any[]= ReverseNaive<T>, // error here, but it works!
	V extends any[]= Drop1<U>,
	W extends any[]= ReverseNaive<V>
	> = W;