Bug: Recursive generic union type synonyms cause poor compiler performance

[benjamin-hodgson]

TypeScript Version: 1.8.10 and 2.1.0-dev.20160818

Code

type T<A> = { a: TSynonym<A> }
          | { b: TSynonym<A> }
          | { c: TSynonym<A> }
          //| { d: TSynonym<A> }
type TSynonym<A> = T<A>

function f<A>(): T<A> {
    return g<A>()
}
function g<A>(): T<A> {
    // return h<A>()
}
function h<A>(): T<A> {

}

Expected behavior:
Type error, in a reasonable length of time (because g and h do not return a value).

Actual behavior:
This example takes over 7 seconds to (fail to) compile on my machine (a new, maxed-out MacBook Pro) and peaks at over 400MB of memory. Uncommenting the fourth line of T's declaration causes the compiler to crash with an out-of-memory error after about a minute. Uncommenting the call to h doubles the compilation time to 14 seconds and increases peak memory usage to over 1GB.

Removing TSynonym (so that the body of T uses T directly), or removing all the generic types, improves the performance significantly.

My guess is that the type-checker is recursively expanding the definitions of T and TSynonym when it tries to type-check the functions, resulting in a very large quantity of nested union types.

Here is the output of tsc with the --diagnostics flag:

Files:               2
Lines:           19030
Nodes:           98142
Identifiers:     35533
Symbols:        354868
Types:          755366
Memory used:   611459K
I/O read:        0.00s
I/O write:       0.00s
Parse time:      0.14s
Bind time:       0.10s
Check time:      6.73s
Emit time:       0.00s
Total time:      6.97s

[kpreisser]

Hi,

this issue can still be reproduced with current master (9afb07d). On my machine, the example takes 8 seconds to compile, and if the fourth line is commented out, node crashes with "JavaScript heap out of memory".

[mhegazy]

looks like a duplicate of the same underlying issue in #10759.

Anonymous types are not cached when doing generic instantiations, causing a lot of these to happen than there should be. the work around is to use named types. e.g.:

interface A<T> {
    a: TSynonym<T>
}
interface B<T> {
    b: TSynonym<T>
}
interface C<T> {
    c: TSynonym<T>
}
interface D<T> {
    d: TSynonym<T>
}
type T<V> = A<V> | B<V> | C<V> | D<V>;
type TSynonym<A> = T<A>

function f<A>(): T<A> {
    return g<A>()
}
function g<A>(): T<A> {
     return h<A>()
}
function h<A>(): T<A> {

}

[ahejlsberg]

This has been fixed by the type alias instantiation caching logic that was added in #12114. The OP example now type checks in effectively zero time.