Horizontal rule processing takes a long time or possibly forever

[ADeeds]

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

[waylan]

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]

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 re module doesn't include support. A few possible solutions:

1. According to this StackOverflow answer, you can fake it with a zero-width lookahead and named back reference.
2. The regex lib supports atomic grouping and is backward compatible with re. We have discussed adopting it before.