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');
}
}
| input |
1.5-3 KB |
3-6 KB |
6-12 KB |
12 KB |
'- *'.repeat(n) (n = 500..4000) |
311 ms |
1205 ms (x3.9) |
5238 ms (x4.3) |
19517 ms (x3.7) |
'+ _'.repeat(n) |
332 ms |
995 ms (x3.0) |
4001 ms (x4.0) |
15726 ms (x3.9) |
'*x *x '.repeat(n) (n = 500..2000) |
893 ms |
4111 ms (x4.6) |
15993 ms (x3.9) |
|
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.
Marked version: 18.0.13 (also
mainat 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):'- *'.repeat(n)(n = 500..4000)'+ _'.repeat(n)'*x *x '.repeat(n)(n = 500..2000)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-profon'- *'.repeat(2000): ~2.4 s of ~3.9 s is self time inTokenizer.emStrong, the rest is GC and theemStrongRDelim*regex. Each unmatched opener runs thewhile ((match = endReg.exec(maskedSrc)) !== null)loop over all remaining delimiters (adding todelimTotalfor every later left delimiter, and doing a[...rDelim].lengthspread per iteration) and only gives up at the end of the string. Withmunmatched delimiters that ism^2 / 2iterations, 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% 3rule andmidRun), 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 toemStrong/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.parsewith 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.