Compiler hangs with large JS file with --allowJs

[RyanHow]

TypeScript Version: typescript@3.2.0-dev.20181117

Search Terms:
Compiler hangs large file

Code
wget --no-check-certificate https://raw.githubusercontent.com/hyperledger/composer-concerto/4e0a9aa990fb065d9eedb54e7086473054b0015a/lib/introspect/parser.js
tsc --allowJs --outDir out-tsc parser.js

Expected behavior:
It completes and writes some output, or some errors

Actual behavior:
It hangs indefinitely

Related Issues:
#17033

[weswigham]

Generated by PEG.js 0.10.0.

Oh no.

Only 560 KB

Oh, ok.

Our own checker is 2MB, so this is most assuredly some kind of poor performance edgecase, and I'd wager in control flow analysis, since the file is filled with code like this:

      peg$c1 = peg$anyExpectation(),
      peg$c2 = peg$otherExpectation("whitespace"),
      peg$c3 = "\t",
      peg$c4 = peg$literalExpectation("\t", false),
      peg$c5 = "\x0B",
      peg$c6 = peg$literalExpectation("\x0B", false),
      peg$c7 = "\f",
      peg$c8 = peg$literalExpectation("\f", false),
      peg$c9 = " ",
      peg$c10 = peg$literalExpectation(" ", false),
      peg$c11 = "\xA0",
      peg$c12 = peg$literalExpectation("\xA0", false),
      peg$c13 = "\uFEFF",
      peg$c14 = peg$literalExpectation("\uFEFF", false),
      peg$c15 = /^[\n\r\u2028\u2029]/,
      peg$c16 = peg$classExpectation(["\n", "\r", "\u2028", "\u2029"], false, false),
      peg$c17 = peg$otherExpectation("end of line"),
      peg$c18 = "\n",
      peg$c19 = peg$literalExpectation("\n", false),
      peg$c20 = "\r\n",
      peg$c21 = peg$literalExpectation("\r\n", false),
      peg$c22 = "\r",
      peg$c23 = peg$literalExpectation("\r", false),
      peg$c24 = "\u2028",
      peg$c25 = peg$literalExpectation("\u2028", false),
      peg$c26 = "\u2029",
      peg$c27 = peg$literalExpectation("\u2029", false),
      peg$c28 = peg$otherExpectation("comment"),
      peg$c29 = "/*",
      peg$c30 = peg$literalExpectation("/*", false),
      peg$c31 = "*/",
      peg$c32 = peg$literalExpectation("*/", false),
      peg$c33 = "//",
      peg$c34 = peg$literalExpectation("//", false),
      peg$c35 = function(name) { return name; },
      peg$c36 = peg$otherExpectation("identifier"),

which we've mined for perf bugs of specific forms in the past.

[rictic]

I've got a repro in under 4KB! I was able to track down at one of the problematic code patterns that PEG.js generates. I had a full bug typed out when I found this one:

TypeScript Version: 3.5.0-dev.20190521

Code

With code that looks like the following:

let s0 = Boolean(Math.random()),
  s1 = Boolean(Math.random()),
  s2 = Boolean(Math.random()),
  s3 = Boolean(Math.random()),
  s4 = Boolean(Math.random()),
  s5 = Boolean(Math.random()),
  s6 = Boolean(Math.random()),
  s7 = Boolean(Math.random()),
  s8 = Boolean(Math.random()),
  s9 = Boolean(Math.random());

if (s8 === s1) {
  if (s9 === s7) {
    if (s9 === s4) {
    }
  }
  if (s3 === s6) {
    if (s4 === s9) {
      if (s5 === s7) {
        if (s6 === s6) {
        }
      }
    }
    if (s0 === s0) {
      if (s5 === s9) {
      }
    }
    if (s9 === s0) {
    }
  }
  // etc...
}

Behavior:

The TypeScript compiler will grind on programs with this shape, using 100% CPU. It won't use much memory, and will eventually terminate, but depending on the number of if statements it could take a prohibitively long time.

A full repro (and a short program to generate programs with this shape) can be found at https://github.com/rictic/tsc_hang_from_if_statements

Playground Link (fair warning, will start a web worker that will use 100% of a CPU core)