Python 3.11 `re.compile` raises SRE code error for valid regex.

[Waszker]

Bug report

Following regex causes re.compile() to raise RuntimeError: invalid SRE code:

   re.compile(
        r"(?P<h>^([01][0-9]|2[0-3]))"
        r"((?P<m>([0-5][0-9]))?"
        r"(?(5)(?P<s>([0-5][0-9]|60))?)"
        r"(?(7)(\.(?P<ms>([0-9]{1,6})?))?))$"
    )

Your environment

Python 3.11

• CPython versions tested on: 3.11
• Operating system and architecture: Linux (docker image as well as virtualenv)

I've checked and this hasn't been an issue in all previous Python interpreter versions, starting from 3.6 (the oldest I've checked).
What's more the regex is correctly recognized and does not cause any issues in other regexp implementations, e.g. the online tool https://regex101.com/

I've already asked about this on mailing list and confirmed that this is a bug.

@serhiy-storchaka has confirmed that the case for this bug has already been found.

• PR: [3.11] gh-98740: Fix validation of conditional expressions in RE (GH-98764) #99045

• PR: [3.10] gh-98740: Fix validation of conditional expressions in RE (GH-98764) #99046

[hroncok]

I've bisected this to f703c96

[serhiy-storchaka]

The simplified example is:

re.compile('()()()()()()()(?(1)()?)')

It is caused by the fundamental flaw in the RE validation code which checks whether the last word in the "then" branch of the conditional expression matches opcode JUMP which was 16 in 3.10 and below and becomes 15 in 3.11. Unfortunately it matches the value of the argument of other opcode ("MARK 15") which means the end of the 8th capturing group.

The bug is not new. Even simpler example for 3.11 is:

re.compile(r'()(?(1)\x0f?)')

and for 3.10 and below:

re.compile(r'()(?(1)\x10?)')

No matter what is the value of the JUMP opcode, there is always an example which fails.

The solution of this issue will not be easy and may require changing semantic of some opcodes.