Bad perf case: Lots of delimiters that can close but no openers

[robinst]

1. Paste the text from this gist into dingus.
2. It takes about 1.3 seconds to parse
3. Paste the text a second time (append, so that the input is doubled in size)
4. It takes 6 to 13 seconds to parse or even longer

The test input is a_ (a, underscore, space) repeated 20000 times. The problem seems to be that in processEmphasis, for each potential closer, the opener is searched all the way back to the stack bottom.

Maybe it could be improved by removing a closer after not finding a corresponding opener iff the closer can not be an opener, so as to not have to check it again. Not sure if this is correct in all cases though or if there are other worst case inputs (need to think about it more).

[jgm]

Thanks for bringing this to my attention. Your proposed
solution works. I've implemented this in cmark and added
some tests to "pathological tests."

Still TODO: implement in commonmark.js. This should
be straightforward with the cmark change as a guide.

[robinst]

Thanks 👍. Just found another case that's related: "[ a_" * 20000. The opening delimiter for the link only gets removed at the end, slowing down the search for a matching opener for the emphasis closers.

[robinst]

And another case is this: "*a_ " * 20000

[jgm]

I have now fixed all of these problems in cmark. TODO: commonmark.js.