Quadratic behavior when parsing smart quotes
Opened this issue · 4 comments
Reproduce with:
python3 -c 'print("\x27x " * 30000 + "\x27\"x" * 30000)' |\
time build/src/cmark --smart >/dev/null
After unquoting, this input looks like
'x 'x 'x 'x 'x '"x'"x'"x'"x'"x
This also works with emphasis:
python3 -c 'print("\"x " * 30000 + "\"_x" * 30000)' |\
time build/src/cmark --smart >/dev/null
When matching a pair of smart quotes, we currently don't remove delimiters (emphasis or other smart quotes) between the quotes. This can lead to quadratic behavior when processing deeply nested quotes interspersed with emphasis or different quotes.
A simple way to fix this issue is to delete delimiters between smart quotes but this changes the parsing rules. Another, more complicated approach is to handle single quotes, double quotes and emphasis in separate lists.
This is the only remaining issue with quadratic complexity in the parser that I could find with a specialized fuzzer similar to the "quadratic" fuzzers in cmark-gfm. Note that there are still some issues in the serializers.
I think removing delims between the quotes makes sense (not sure why I didn't do that originally?).
Here's an example how removing delimiters between quotes changes parsing results:
Before:
% echo "'a _b' c_ d" |build/src/cmark --smart
<p>‘a <em>b’ c</em> d</p>
After (the underscore between quotes will be ignored):
% echo "'a _b' c_ d" |build/src/cmark --smart
<p>‘a _b’ c_ d</p>
I also noticed that smart quotes are always converted even if no matching pair is found.
I guess the question is whether we want to treat smart quotes as at the same precedence level as _ and *, or as having a lower precedence level.
Since it's an extension, this isn't decided one way or the other by the spec.
I suppose one could argue that spec'd behavior should take precedence, so that smart quotes should have a lower precedence level. Not sure how strong that is.
In any case, these are corner cases; it's hard to imagine this would affect anything serious.
Other than the commonmark-hs smart quotes extension, most implementations don't do that.
- markdown-it with typographer seems to just have emphasis bind tighter. Notice that the first single quote is a straight quote.
- While pandoc commonmark_x does have smart quotes bind tighter than emphasis, classic pandoc-flavored markdown allows them to overlap, producing
‘a <em>b’ c</em> d. - pulldown-cmark tracks smart quotes separately from emphasis, so the spans they delimit can overlap with emphasis, producing the same result as pandoc-flavored.
- hugo 0.119 also allows them to overlap, also producing the same result as pandoc-flavored and pulldown-cmark.