Parsing emphasis takes quadratic time

[rlidwka]

A bug was reported in markdown-it:
markdown-it/markdown-it#583

Similar thing exists here, just for more complex pattern.

This takes 1 second (as well as multiple other similar combinations):

$ node -e 'console.log("*_* _".repeat(40000))' | time ./commonmark > /dev/null
1.12user 0.10system 0:00.72elapsed 169%CPU (0avgtext+0avgdata 150168maxresident)k
0inputs+0outputs (0major+32913minor)pagefaults 0swaps

But this one takes 45 seconds (progressively worse with more data):

$ node -e 'console.log("*_* _ ".repeat(40000))' | time ./commonmark > /dev/null
45.13user 0.17system 0:44.73elapsed 101%CPU (0avgtext+0avgdata 152156maxresident)k
0inputs+0outputs (0major+37771minor)pagefaults 0swaps

Expected result is <em>_</em> _ <em>_</em> _ <em>_</em> _ <em>_</em> _ <em>_</em>, and I suspect the issue is with _ character in between emphases trying to be paired with every single previous one.

I don't know at the moment how or whether it can be fixed.

[jgm]

Note: cmark does NOT have this problem (nor does jgm/commonmark-hs).

[jgm]

I think this is the same as commonmark/cmark#178
which was fixed by
commonmark/cmark@a8d5bd4

It should be possible to port this commit to commonmark.js, which otherwise follows cmark's algorithm exactly.

[jgm]

I backported the fix to cmark#178, but that didn't fix this case.
Hm.