Nested series of assignments takes ~quadratic time to parse

[tchetwin]

TypeScript Version: 3.5.0-dev.20190409 (also 3.4.2)

Search Terms: nested, parsePossibleParenthesizedArrowFunctionExpressionHead

Code

a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=a.a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a

Alternate test bench:

const ts = require("typescript");
const source = `a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=(a=a.a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a).a`;

ts.transpileModule(source, {});

Expected behavior:

Parses in a timely manner.

Actual behavior:

tsc takes 5 seconds, and this time increases ~quadratically as the repetition is increased. In our case this quickly grew to hours.

Playground Link:

Playground (Warning, this is a little intense and might hang the browser)

Related Issues:

Not that I could find

Some investigation:

Looking at profile output, it looks like the following might be happening:

• Arrive at first (
• Could be a parenthesized arrow function (based on (a=...)
• Pursue that theory, start consuming first default assigned property
• Arrive at second (
• Could be a parenthesized arrow function (based on (a=...)
• Repeat until we finally reach the middle, realise there was no arrow function, backtrack
• We now know the outermost set of parens wasn't an arrow, but an assignment
• Arrive at second ( (again)
• Repeat the whole process

But, why?:

Received output of this style from terser (formerly uglify-es) from original code of the form:

str = str.replace("a", "b");
str = str.replace("c", "b");

We happen to need to do some AST based post-processing.

[jakebailey]

This was fixed by #32640; #31987 turned out to be a duplicate of this issue (and has effectively the same test case).