`re` hangs on forever for this pattern

[dg-pb]

Bug report

Bug description:

Text:

with open('./cpython/Tools/ssl/multissltests.py') as f:
    text = f.read()

By doing multiline search on CPython codebase (which works fine):

REG1 = r'''
    (\s*)try\:\n
    (
        (\1)[^\n]*\n
    )*
    (\1)
    else\:\s*if
'''
CMP1 = re.compile(REG1, re.VERBOSE)
CMP1.search(text)

I did one extra addition:

REG2 = r'''
    (\s*)try\:\n
    (
        ((\1)[^\n]*)?\n
    )*
    (\1)
    else\:\s*if
'''
CMP2 = re.compile(REG2, re.VERBOSE)
CMP2.search(text)    # Hangs indefinitely

I minimised regex so that it still hangs. Although it does not make sense anymore, but it seems to be a minimal example propagating this behaviour:

REG3 = r'([^\n]*)*l'
CMP3 = re.compile(REG3)
CMP3.search(text)

CPython versions tested on:

3.12

Operating systems tested on:

macOS

[ZeroIntensity]

I was able to reproduce this, but it only occurs on some strings passed to search. This only happens on the content of multissltests.py, not anything else that I could find.

Also, I'm not too sure that it's hanging indefinitely -- it might just be taking a really long time. I was playing around with the reproducer, and removing some lines appeared to cause the hang at first, but returned after several seconds.

[kingconic1]

sometimes i also have the same problem that it crashes i use threading modul and write the funktion that i wanna run in it and then it didnt crash anymore, so u have to make ur code into a funktion and then run it with threading and then it should work

[dg-pb]

This only happens on the content of multissltests.py

Yup, this is why I added the file as well. I though so too, but the file itself is fairly short one, so I thought there is a high probability that something undesirable is happening here.

[dg-pb]

so u have to make ur code into a funktion and then run it with threading and then it should work

It would be useful to investigate such cases where it only works within a thread. However, this case hangs when run in a thread in the same way.

[tim-one]

Nested quantifiers can very easily lead to exponential-time behavior. This isn't shallow. Jeffrey Friedl's "Mastering Regular Expressions" is a book-length exposition of what's needed to write efficient (in all cases) regexps when using a backtracking implementation (like Python's). Play with this code, and you'll see that adding a single character to a non-matching target string essentially doubles the time to fail to find a match:

import re
from time import perf_counter as now

REG3 = r'([^\n]*)*l'
CMP3 = re.compile(REG3)

text = 'a'
while True:
    start = now()
    CMP3.search(text)
    finish = now()
    print(len(text), finish - start)
    text += 'a'

This took over 2 minutes on my box just now to fail to find a match for 'a' * 30

[ZeroIntensity]

Oh, TIL! Looks like a non-issue then.

[tim-one]

Yes, this should be closed as "not planned". I'm unable to do that.

[serhiy-storchaka]

This is called a "catastrophic backtracking". Very common issue with regular expressions. You should just learn how to recognize a potential catastrophic backtracking in regular expressions and how to rewrite them to avoid it.

[tim-one]

Not so easy. That's why Friedl wrote a book 😉. Even after someone learns how to avoid exponential-time catastrophes in all cases, there remain possibilities for polynomial-time disasters, which don't become screamingly obvious until target strings become longer.

[dg-pb]

Thank you, was afraid that this is the case and apparently it is.

I have just started dipping my toes into this area. Are there any better approaches? E.g. I read that latest milestone was google's re2, which does linear time. Is that correct? Would more radical changes to Python's re be welcome in longer term?

[tim-one]

Huge topic. Better suited to Discourse. There are classic time/space tradeoffs. Linear-time searching may require building data structures that grow to size exponential in the length of the regexp. No easy answers.

https://pypi.org/project/regex/

https://github.com/mrabarnett/mrab-regex

is a better implementation available right now, but for whatever reasons MRAB doesn't want to fold it into the core.

It's also prone to timing disasters, but they're harder to provoke because regex works harder to optimize away common sources of time bombs.