Parsing '[ (]([ (]([ (]([ (](...' takes quadratic time

[mity]

$ time py -c 'print("[ (](" * 10000)' | ./cmark >/dev/null
real    0m0.232s
user    0m0.030s
sys     0m0.000s

$ time py -c 'print("[ (](" * 40000)' | ./cmark >/dev/null
real    0m2.168s
user    0m0.000s
sys     0m0.045s

$ time py -c 'print("[ (](" * 80000)' | ./cmark >/dev/null
real    0m8.278s
user    0m0.016s
sys     0m0.046s

(Originally reported by @andersk for MD4C in mity/md4c#57 but applies to Cmark too.)

[mity]

In MD4C, it was fixed by mity/md4c@966b8e3.

See the specs:

A link title consists of either

• a sequence of zero or more characters between straight double-quote characters ("), including a " character only if it is backslash-escaped, or
• a sequence of zero or more characters between straight single-quote characters ('), including a ' character only if it is backslash-escaped, or
• a sequence of zero or more characters between matching parentheses ((...)), including a ) character only if it is backslash-escaped.

Imho the 3rd option has to be updated to disallow also (. Otherwise, given this test case, you have to scan till the end of the input for every part of the input pattern, leading to O(n^2). Furthermore allowing it leads to very unreadable and unintuitive behavior:

$ echo '[x](url (crazy_title())' | ./cmark
<p><a href="url" title="crazy_title(">x</a></p>

[mity]

This was also already touched here: commonmark/commonmark-spec#526

[jgm]

Fixed by 9f7d0a6