Repository navigation
Horizontal rule processing takes a long time or possibly forever #1055
Description
When I feed in certain strings with lots of "-" characters, it takes incredibly long for the markdown function to return a result. It may not hang forever, but I've been waiting several hours for the library to process about 30 characters.
Here's an example
# python3
Python 3.8.6 (default, Oct 13 2020, 20:37:26)
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import markdown
>>> markdown.markdown("------------------------------hello---------------------")
After several hours the function is still calculating. Here's a stack trace from when I interrupt the computation:
File "<stdin>", line 1, in <module>
File "/usr/local/lib/python3.8/site-packages/markdown/core.py", line 386, in markdown
return md.convert(text)
File "/usr/local/lib/python3.8/site-packages/markdown/core.py", line 263, in convert
root = self.parser.parseDocument(self.lines).getroot()
File "/usr/local/lib/python3.8/site-packages/markdown/blockparser.py", line 90, in parseDocument
self.parseChunk(self.root, '\n'.join(lines))
File "/usr/local/lib/python3.8/site-packages/markdown/blockparser.py", line 105, in parseChunk
self.parseBlocks(parent, text.split('\n\n'))
File "/usr/local/lib/python3.8/site-packages/markdown/blockparser.py", line 122, in parseBlocks
if processor.test(parent, blocks[0]):
File "/usr/local/lib/python3.8/site-packages/markdown/blockprocessors.py", line 504, in test
m = self.SEARCH_RE.search(block)
When I remove enough of the - characters I will eventually get a result, although it can still take a few minutes. markdown.markdown("---------------------------hello-------------------") will actually return a result but it takes about 20-30 seconds.
I'm using version 3.3.2 of the library
Activity
waylan commentedon Oct 24, 2020
I can confirm the long delay. And I can also confirm that reversing the change in #995 removes the problem. Of course, then then reintroduces the bug that fixed. Presumably the regex pattern needs an overhaul.
waylan commentedon Oct 24, 2020
A great explanation of the problem with the expression can be found here: Runaway Regular Expressions: Catastrophic Backtracking. Of course the solution would be to use atomic grouping, except that the
remodule doesn't include support. A few possible solutions:re. We have discussed adopting it before.Avoid catastrophic backtracking in `hr` regex
Avoid catastrophic backtracking in `hr` regex
Avoid catastrophic backtracking in `hr` regex