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

首先追蹤 regex engine 的 alternation quick check，以及它如何處理 MARK ops 和 repeats。使用列出的 ./python -m timeit 命令建立基準線，並驗證 tokenizer、alternation 以及其他 benchmark 的結果有所改善，同時不改變 plain-alternation 的行為；查看 gh-153170，了解已經在進行的工作。