Parsing >>>>>>… takes quadratic time and eventually crashes with recursion error

[andersk]

>>> import markdown, timeit
>>> num, dur = timeit.Timer(lambda: markdown.markdown(">" * 100)).autorange(); dur / num
0.004344235559692607
>>> num, dur = timeit.Timer(lambda: markdown.markdown(">" * 200)).autorange(); dur / num
0.016907797248859425
>>> num, dur = timeit.Timer(lambda: markdown.markdown(">" * 300)).autorange(); dur / num
0.05682634799741208
>>> markdown.markdown(">" * 331)
…
RecursionError: maximum recursion depth exceeded while calling a Python object

Same results in 3.0.1 and master.

[waylan]

I'm curious where this is coming from. My recollection was that we ignore > unless we first have <.

In any event as per the discussion in #789, I don't care about the performance issue. But we should address the RecursionError.

[facelessuser]

This might be related to block quotes if I had to guess.

[waylan]

Ah, right, infinently nested block quotes. Except that they require a space. The token is [greaterthan][space] together. Without the space, the blockquote processor should ignore it.

[andersk]

I’m not sure which specification you aim to follow (if any), but both Markdown.pl and CommonMark agree that the space after > is optional in the blockquote syntax. In any event, the same behavior can be observed with > > > > > > ….

[mitya57]

Python-Markdown does not require a space between >s too:

>>> print(markdown.markdown(">>>foo"))
<blockquote>
<blockquote>
<blockquote>
<p>foo</p>
</blockquote>
</blockquote>
</blockquote>

[waylan]

Sorry. I guess I mis-rembered that. So yeah, infinitely nested blockquotes.

I'm not sure how to address this. When the block parser refactor in 2.0 was done, I removed most of the recursion, but there are a few places it remains. And those few locations in the code will only ever hit the recursion limit with contrived input. On the one hand I want to say: " don't do that" but I realize it is untrusted users who are the problem here.

I don't think we can just not support this contrived input. As it turns out, most implementations handle this pretty consistently with shorter strings of >s. Although, they do start to diverge with longer strings (I did not check every iteration to find where the divergence starts).

[MythicManiac]

A simple option could be to allow for maximum nesting depth setting (if that's not already the case somewhere). I can't immediately think of any use cases for over 300 nested block quotes, unless you render your work email chains into markdown for some reason.

Though I suppose that still leaves the issue if your maximum depth is above the recursion error threshold

[waylan]

I can't immediately think of any use cases for over 300 nested block quotes, unless you render your work email chains into markdown for some reason.

This is the problem. Years ago (before GitHub even existed) we got a bunch of bug reports because someone was trying to pass plaintext version of the complete works of Shakespeare through our parser. The document was not Markdown formatted and we were hitting recursion limits due to the weird syntax.

Additionally, we promise our users that we won't crash their server. If a random user can submit plain text to your site and that crashes your server, you won't want to use our lib anymore. Therefore, we must always assume the worst sorts of input. Sometimes that means things are less performant in the simple case. Its a tradeoff.

[waylan]

A simple option could be to allow for maximum nesting depth setting

As I understand it, on different systems Python's maximum recursion depth may be different based on the available resources. If someone has a valid need for a higher nesting depth, then that should just work for them with no need to adjust a setting. I think perhaps the solution is to catch the RecursionError and simply return the unparsed levels as plan text. That ensures the maximum level of nesting possible is always supported and avoids an error being raised.

The down side is that things get really slow before the error is raised. But that is a tradeoff I'm willing to make when the user is trying to parse contrived input.

[MythicManiac]

I'm not sure how impactful can the latency grow in reality, but it might be worth adding an optional setting regardless in case your normal use cases don't consist of immense nesting levels. Making it enabled by default might not be necessary, though I personally wouldn't mind that either.

I'd gladly limit the maximum recursion depth to say, 30 or even 20 even, because I'm rendering user input and if someone exceeds that they're either doing something stupid or trying to abuse the system. So at least for my use case it would make far more sense to restrict max depth rather than continuing indefinitely until a recursion error, given the performance impact it has.