tsc / language server hangs with complex type aliases

[Nathan-Fenner]

TypeScript Version: 2.4.2

Code

Originally, trying to abuse the type system to create guaranteed-balanced AVL trees. Found out that language server used with vscode would just hang or crash, so I reduced it slightly, and tried running it through tsc:

type NonNeg = {sign: "0"} | {sign: "+", pred: NonNeg}
type NonPos = {sign: "0"} | {sign: "-", succ: NonPos}
type Int = {sign: "0"} | {sign: "+", pred: NonNeg} | {sign: "-", succ: NonPos}

type Succ<N extends Int> = {"0": {sign:"+", pred:{sign:"0"}}, "+" :{sign:"+", pred:N}, "-": N["succ"]}[N["sign"]];
type Pred<N extends Int> = {"0": {sign:"-", succ:{sign:"0"}}, "-" :{sign:"-", succ:N}, "+": N["pred"]}[N["sign"]];

type Zero = {sign: "0"};

type Empty<N extends Int> = {z: {}, s: never, n: never}[N["value"]] & {type: "empty", level: Zero};
type Even<N extends Int> = {type: "even", left: AVL<Pred<N>>, right: AVL<Pred<N>>, value: number, level: N};
type LeftHeavy<N extends Int> = {type: "left-heavy", left: AVL<Pred<N>>, right: AVL<Pred<Pred<N>>>, value: number, level: N};
type RightHeavy<N extends Int> = {type: "right-heavy", left: AVL<Pred<Pred<N>>>, right: AVL<Pred<N>>, value: number, level: N};

type AVL<N extends Int> = Even<N> | LeftHeavy<N> | RightHeavy<N> | Empty<N>

// note: this function is mostly nonsensical, but it appears to be the cause of the problem
function find<N extends Int>(x: number, tree: AVL<N>): void {
    if (tree.type == "empty") {
        return;
    }
    find(x, tree.left);
}

Expected behavior:

Accept, probably (assuming I made no mistakes), but a compile error would be fine too.

Actual behavior:

tsc hangs for a couple minutes minutes, then prints a stack trace indicating that v8 ran out of memory:

<--- Last few GCs --->

[71249:0x103801600]    94152 ms: Mark-sweep 1401.9 (1582.3) -> 1401.9 (1554.3) MB, 1944.7 / 0.0 ms  (+ 0.0 ms in 0 steps since start of marking, biggest step 0.0 ms, walltime since start of marking 1945 ms) last resort 
[71249:0x103801600]    96016 ms: Mark-sweep 1401.9 (1554.3) -> 1401.9 (1554.3) MB, 1863.1 / 0.0 ms  last resort 


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x36703af9bbd9 <JS Object>
    1: set [native collection.js:~247] [pc=0x86dbef1a89a](this=0x3db4171451b1 <a Map with map 0x2fd6c9514319>,p=0x227e7acccf51 <String[15]: 1771856,1771870>,x=1)
    2: /* anonymous */ [/usr/local/lib/node_modules/typescript/lib/tsc.js:978] [pc=0x86dbef0f2c9](this=0x9de99b0a1e1 <JS Global Object>,value=1,key=0x227e7acccf51 <String[15]: 1771856,1771870>)
    3: arguments adaptor frame: 3->2
    ...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: node::Abort() [/usr/local/bin/node]
 2: node::FatalException(v8::Isolate*, v8::Local<v8::Value>, v8::Local<v8::Message>) [/usr/local/bin/node]
 3: v8::Utils::ReportOOMFailure(char const*, bool) [/usr/local/bin/node]
 4: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/usr/local/bin/node]
 5: v8::internal::Factory::NewFixedArray(int, v8::internal::PretenureFlag) [/usr/local/bin/node]
 6: v8::internal::OrderedHashTable<v8::internal::OrderedHashMap, v8::internal::JSMapIterator, 2>::Allocate(v8::internal::Isolate*, int, v8::internal::PretenureFlag) [/usr/local/bin/node]
 7: v8::internal::OrderedHashTable<v8::internal::OrderedHashMap, v8::internal::JSMapIterator, 2>::Rehash(v8::internal::Handle<v8::internal::OrderedHashMap>, int) [/usr/local/bin/node]
 8: v8::internal::Runtime_MapGrow(int, v8::internal::Object**, v8::internal::Isolate*) [/usr/local/bin/node]
 9: 0x86dbea840bd
10: 0x86dbef1a89a
11: 0x86dbef0f2c9
12: 0x86dbea86bbb
13: 0x86dbef09cab
Abort trap: 6

[Nathan-Fenner]

Note: I found a bug in my code (this is still a compiler bug because tsc shouldn't crash) but I notice that fixing it causes TSC to start producing reasonable errors:

// causes compiler crash in above
type Empty<N extends Int> = {z: {}, s: never, n: never}[N["value"]] & {type: "empty", level: Zero};

should actually be

// tsc spits out type error
type Empty<N extends Int> = {"0": {}, "+": never, "-": never}[N["value"]] & {type: "empty", level: Zero};

[sandersn]

Note that this example doesn't have any mapped types in it, only indexed access types (N["value"])