Typescript: Compiler hangs or crashes by a few code

[falsandtru]

I believe TypeScript must not hang by the following small code.

TypeScript Version: 2.1.0-dev.20160819

Code

export class Sequence<a, z> {
  constructor(
    cons: (z: z, cons: (a?: a, z?: z) => Sequence.Data<a, z>) => Sequence.Data<a, z>,
    memory?: Map<number, Sequence.Data<a, z>>
  ) {
  }
}
export namespace Sequence {
  export type Data<a, z> = [a, z];
  export namespace Data {
    export function cons<a, z>(a?: a, b?: z): Sequence.Data<a, z> {
      switch (arguments.length) {
        case 0:
          return <Sequence.Data<a, z>>[];
        case 1:
          return <Sequence.Data<a, z>><any[]>[a];
        case 2:
          return <Sequence.Data<a, z>>[a, b];
        default:
          throw Sequence.Exception.invalidConsError(arguments);
      }
    }
  }
  export type Thunk<a> = [a, Iterator<a>, number];
  export namespace Thunk {
    export function value<a>(thunk: Thunk<a>): a {
      return thunk[0];
    }
    export function iterator<a>(thunk: Thunk<a>): Iterator<a> {
      return thunk[1];
    }
    export function index<a>(thunk: Thunk<a>): number {
      return thunk[2];
    }
  }
  export type Iterator<a> = () => Thunk<a>;
  export namespace Iterator {
    export const done: Sequence.Iterator<any> = () => <Sequence.Thunk<any>>[void 0, done, -1];
    export function when<a, b>(
      thunk: Thunk<a>,
      caseDone: (thunk: Thunk<a>) => b,
      caseIterable: (thunk: Thunk<a>, recur: () => b) => b
    ): b {
      return Sequence.isIterable(thunk)
        ? caseIterable(thunk, () => when(Thunk.iterator(thunk)(), caseDone, caseIterable))
        : caseDone(thunk);
    }
  }
  export function isIterable(thunk: Thunk<any>): boolean {
    return Thunk.iterator(thunk) !== Iterator.done;
  }
  export namespace Exception {
    export function invalidConsError(args: IArguments): TypeError {
      console.error(args, args.length, args[0], args[1]);
      return new TypeError(`Spica: Sequence: Invalid parameters of cons.`);
    }
    export function invalidDataError(data: Sequence.Data<any, any>): TypeError {
      console.error(data);
      return new TypeError(`Spica: Sequence: Invalid data.`);
    }
    export function invalidThunkError(thunk: Sequence.Thunk<any>): TypeError {
      console.error(thunk);
      return new TypeError(`Spica: Sequence: Invalid thunk.`);
    }
  }
}

Expected behavior:

It can compile quickly.

Actual behavior:

Too slow. In my actual case, compiler will be crashed.

$ $(npm bin)/tsc --noEmit -t es5 --lib es6,dom --diagnostics src/lib/monad/sequence/core.ts
Files:              13
Lines:           20588
Nodes:          102533
Identifiers:     37365
Symbols:       1679795
Types:          787098
Memory used:  1285938K
I/O read:        0.03s
I/O write:       0.00s
Parse time:      0.91s
Bind time:       0.67s
Check time:     94.28s
Emit time:       0.00s
Total time:     95.87s

[falsandtru]

Simplified:

export namespace Sequence {
  export type Thunk<a> = [a, Iterator<a>, number];
  export namespace Thunk {
    export function iterator<a>(thunk: Thunk<a>): Iterator<a> {
      return thunk[1];
    }
  }
  export type Iterator<a> = () => Thunk<a>;
  export namespace Iterator {
    export function when<a, b>(
      thunk: Thunk<a>,
      caseIterable: (thunk: Thunk<a>, recur: () => b) => b
    ): b {
      return caseIterable(thunk, () => when(Thunk.iterator(thunk)(), caseIterable));
    }
  }
}

$ $(npm bin)/tsc --noEmit --lib es5 --diagnostics index.ts
Files:               2
Lines:            4151
Nodes:            8826
Identifiers:      3393
Symbols:         86136
Types:           45086
Memory used:   109002K
I/O read:        0.00s
I/O write:       0.00s
Parse time:      0.28s
Bind time:       0.11s
Check time:      3.61s
Emit time:       0.00s
Total time:      4.00s

$ $(npm bin)/tsc --noEmit --lib es6 --diagnostics index.ts
Files:              12
Lines:            5938
Nodes:           13157
Identifiers:      5200
Symbols:       1584898
Types:          774716
Memory used:  1208546K
I/O read:        0.03s
I/O write:       0.00s
Parse time:      0.35s
Bind time:       0.12s
Check time:     94.00s
Emit time:       0.00s
Total time:     94.47s

-Memory used:   109002K
+Memory used:  1208546K
-Check time:      3.61s
+Check time:     94.00s

@sandersn @DanielRosenwasser @mhegazy @ahejlsberg Can you take a look?

[DanielRosenwasser]

Is this just in a recent nightly that you see the regression, or when you change from --lib es5 to --lib es6?

As a heads up, --lib es6 does not include the ES5 lib implicitly. I suspect some property was short-circuiting some deep structural comparisons in the ES5 lib. Can you let me know what the results are if you run with the following?

tsc --noEmit --lib "es5,es6" --diagnostics index.ts

[falsandtru]

@DanielRosenwasser Thanks for the reply! I tried, but

$ node_modules/.bin/tsc --noEmit --lib es5,es6 --diagnostics index.ts
Files:              12
Lines:            5938
Nodes:           13157
Identifiers:      5200
Symbols:       1584898
Types:          774716
Memory used:  1159921K
I/O read:        0.02s
I/O write:       0.00s
Parse time:      0.31s
Bind time:       0.14s
Check time:     91.73s
Emit time:       0.00s
Total time:     92.18s

Is this just in a recent nightly that you see the regression, or when you change from --lib es5 to --lib es6?

I believe I'm testing correctly. Could you repro that?

[DanielRosenwasser]

Confirmed - introducing ES6 libs or using --target es6 makes checking take an incredibly long time. This issue is present in the beta, so I'm not sure how far back it started.

[falsandtru]

Confirmed - introducing ES6 libs or using --target es6 makes checking take an incredibly long time.

Yes! Yes! Thanks!

I'm not sure how far back it started.

Then I investigate nightlies.

[falsandtru]

Found. It published at 1.9.0-dev.20160521-1.0.

$ npm i [email protected]
$ node_modules/.bin/tsc --noEmit --lib es6 --diagnostics src/lib/monad/sequence/core.ts

<--- Last few GCs --->

  124539 ms: Mark-sweep 1319.4 (1440.5) -> 1319.0 (1440.5) MB, 3472.0 / 0 ms [allocation failure] [GC in old space requested].
  127882 ms: Mark-sweep 1319.0 (1440.5) -> 1319.1 (1440.5) MB, 3343.0 / 0 ms [allocation failure] [GC in old space requested].
  131378 ms: Mark-sweep 1319.1 (1440.5) -> 1319.0 (1440.5) MB, 3496.0 / 0 ms [last resort gc].
  135005 ms: Mark-sweep 1319.0 (1440.5) -> 1319.1 (1437.5) MB, 3627.0 / 0 ms [last resort gc].


<--- JS stacktrace --->

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

Security context: 000003AAC61C9E51 <JS Object>
    1: objectTypeRelatedTo [.\node_modules\typescript\lib\tsc.js:~17269] [pc=000003B3D492745B] (this=000003AAC61E14D1 <JS Global Object>,source=0000021FCF8AD171 <a Type with map 000002A99DA64EF9>,originalSource=0000021FCF8AD171 <a Type with map 000002A99DA64EF9>,target=000001B2DB5635A9 <a Type with map 000002A99DA5F121>,reportErrors=000003AAC6104299 <false>)
...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory

$ npm i [email protected]
$ node_modules/.bin/tsc --noEmit --lib es6 --diagnostics src/lib/monad/sequence/core.ts
Files:              12
Lines:            5793
Nodes:           12961
Identifiers:      5112
Symbols:         14874
Types:            5804
Memory used:    31043K
I/O read:        0.05s
I/O write:       0.00s
Parse time:      0.37s
Bind time:       0.23s
Check time:      0.91s
Emit time:       0.00s
Total time:      1.51s

[DanielRosenwasser]

Thanks for tracking that down @falsandtru!

[DanielRosenwasser]

8705 seems to be the only thing that was merged in on May 20th (the day before the regression was published in a nightly).

[ahejlsberg]

I took a look, and the issue appears to be that we _always_ structurally compare tuple types. For references to the same generic type we always first compare the type arguments, but we don't have logic in place to do the same for tuple types. That leads to an explosion of structural type comparisons. It becomes an issue with --lib es6 because that introduces a member on Array<T> that contains a tuple type in its signature.

We've had several issues related to tuples and I'm thinking a better implementation approach would be to automatically synthesize Tuple_N<A, B, C, ...> extends Array<A | B | C | ...> { 0: A, 1: B, 2: C, ... } interface types and then use normal type references to handle the instantiations. That should eliminate almost all of the special casing we currently have. I will think about this some more.

[ahejlsberg]

@falsandtru @DanielRosenwasser Fix available in #10466.

[falsandtru]

@ahejlsberg Thanks for the fix! It works well.