Closed
Description
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