Regex with the backreference to a non-greedy group fails unexpectedly

[Frimaire]

Bug report

Bug description:

Hello,

There is a problem in the regex module. The regular expression with the backreference to a non-greedy group fails (matches nothing) on some inputs unexpectedly.

For example:

import re

r1 = re.compile('(a+)+\\1')
print(r1.search('a' * 28))
# OK, matches the whole string

r2 = re.compile('(a+)+?\\1')
print(r2.search('a' * 28))
# runs very slowly and eventually returns None

This problem seems to exist even in Python 2.7, which has been fixed in a version of Python 3.11. Since version 3.9 is still under maintenance, would this problem be fixed in the following release? (or is the pull request about this problem accepted?)

Thank You!

CPython versions tested on:

3.9

Operating systems tested on:

Linux, Windows

[hugovk]

I can reproduce on macOS with Python 3.9 and 3.10, but 3.11-3.14 match the whole string quickly.

3.9-3.11 are only receiving security updates, whereas 3.12+ get bug fixes:

https://devguide.python.org/versions/

I don't think this is a security issue? I recommend upgrading to a newer Python version.

[wjssz]

I tested. It was fixed in PR #12427, the change for JUMP_REPEAT_ONE_2.

You can use regex module, it has no known bug. Just:

import regex as re

[ericvsmith]

I don't think this is a security issue, and we can close this.