Look through group marks in the regex alternation quick check

Feature or enhancement

Proposal:

When the regex engine tries the alternatives of a|b|..., it skips an alternative without entering it if the alternative starts with a literal or a character set that cannot match the current character. But the check only looks at the very first opcode, so alternatives starting with a capturing group — (foo)|(bar), and in particular tokenizer-style patterns (?P<KW>...)|(?P<NUM>...)|... — are never skipped: every mismatching alternative is entered, writes its group mark, fails and backtracks. The same applies to alternatives starting with a repeat with a nonzero minimum, like a+x|b+y.

Extend the quick check to look through MARK ops and into the repeated item of such a repeat. Plain alternations are unaffected: the existing checks are performed first and unchanged.

Benchmarks with realistic patterns, ./python -m timeit, non-PGO release builds:

./python -m timeit -s "import re; m = re.compile('(GET)|(HEAD)|(POST)|(PUT)|(PATCH)|(DELETE)').fullmatch" "m('DELETE')"
./python -m timeit -s "import re; f = re.compile(r'([0-9]+)|([A-Za-z]+)|([ \t]+)').finditer" "for m in f('x1 = 42 + foo'): pass"
./python -m timeit -s "import re; spec = [('NUMBER', r'\d+(?:\.\d*)?'), ('ASSIGN', r':='), ('ID', r'[A-Za-z]+'), ('OP', r'[+\-*/]'), ('NEWLINE', r'\n'), ('SKIP', r'[ \t]+'), ('MISMATCH', r'.')]; f = re.compile('|'.join('(?P<%s>%s)' % p for p in spec)).finditer; line = 'total := total + price * quantity\n'" "for m in f(line): m.lastgroup"
./python -m timeit -s "from string import Template; t = Template('Dear \$name, your order #\$order ships \$date.'); m = {'name':'Ada','order':'1042','date':'Monday'}" "t.substitute(m)"

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Linked PRs

• gh-153170

Beginne damit, die schnelle Prüfung der Alternation der Regex-Engine nachzuverfolgen und zu untersuchen, wie sie MARK ops und Wiederholungen behandelt. Verwende die aufgeführten ./python -m timeit-Befehle, um die Baseline festzulegen und zu überprüfen, dass sich die Ergebnisse des Tokenizers, der Alternation und der anderen Benchmarks verbessern, ohne das Verhalten bei einfachen Alternationen zu ändern; sieh dir gh-153170 auf bereits laufende Arbeiten an.