emStrong is quadratic in the number of unmatched emphasis delimiters (12 KB input takes ~16 s) #4099

Marked version: 18.0.13 (also main at 4eb2d97)

Markdown flavor: n/a (default / GFM)

Description

Parsing time grows quadratically with the number of unmatched * / _ delimiters, so a small, crafted input freezes the parser. A 12 KB document takes about 16-19 seconds on my machine (Windows 11, Node 24; the machine was under some load, so treat absolute numbers loosely, but the growth rate is the point):

import { marked } from 'marked';

for (const unit of ['- *', '+ _', '*x *x ']) {
  for (const n of [500, 1000, 2000, 4000]) {
    const src = unit.repeat(n);
    const t = performance.now();
    marked.parse(src);
    console.log(JSON.stringify(unit), src.length + 'B', Math.round(performance.now() - t) + 'ms');
  }
}

Every doubling of the input multiplies the time by about 4. Similar inputs made of 1.*, 1)_, * _, - _ and so on behave the same way, so it is the emphasis handling rather than the list rule. The same shape without list markers (' *_'.repeat(n)) is also quadratic.

Where the time goes

node --cpu-prof on '- *'.repeat(2000): ~2.4 s of ~3.9 s is self time in Tokenizer.emStrong, the rest is GC and the emStrongRDelim* regex. Each unmatched opener runs the while ((match = endReg.exec(maskedSrc)) !== null) loop over all remaining delimiters (adding to delimTotal for every later left delimiter, and doing a [...rDelim].length spread per iteration) and only gives up at the end of the string. With m unmatched delimiters that is m^2 / 2 iterations, and none of the work is shared between openers.

I looked for a small fix and did not find one that is clearly safe: whether a later opener can succeed depends on the running delimTotal (including the % 3 rule and midRun), so failure of an earlier opener does not imply failure of a later one. The usual linear solution is the CommonMark reference algorithm (a delimiter stack with "openers_bottom" per delimiter type/length), which would be a bigger change to emStrong / inlineTokens. If there is a preferred direction (a cheap early-exit such as "no right-flanking delimiter of this kind left in the string", constant-factor cleanups in the loop, or the delimiter-stack approach) I am happy to try a PR.

Expectation

Parse time roughly linear in input size, like other inputs of that size (the 'a_' and plain '*' inputs of the same length parse in a few ms).

Result

Seconds of CPU per 10 KB, growing 4x per doubling.

Related earlier reports were fixed the same way as regex backtracking (#3916, #3917, #4013, #4014, #4090); I did not find an existing issue for emphasis delimiters.

_{Found by fuzzing marked.parse with generated delimiter patterns and timing each in a worker thread. I drafted this report with AI assistance (Claude Code) and reproduced the numbers above myself.}