Auto-possessify greedy repeats in regular expressions

Feature or enhancement

Proposal

Make the re compiler turn a greedy repeat into a possessive one when this cannot change what the pattern matches: when the repeated atom and every character that can possibly follow the repeat are provably disjoint, backtracking into the repeat is always futile, so a+b can be compiled as if it were a++b. PCRE2 performs the same optimization under the name "auto-possessification".

This is a pure compile-time transform: the POSSESSIVE_REPEAT opcodes exist since Python 3.11, and the analysis only fires when it can prove disjointness, so any imprecision can only cost an optimization, never change a match result.

The main benefit is failing or backtracking-heavy matches whose repeat is followed by a character set or category: the existing REPEAT_ONE fast path only covers literal tails, so for example \d+\. or \w+\s currently backtrack character by character. Measured speedups are 2.2–4.5× on such failing matches, ~~and some patterns with catastrophic backtracking are defused as a side effect~~ (though this is an optimization, not a security fix). Correction: where disjointness is provable, every give-back already fails at the first following atom, so this removes only a constant factor; the catastrophic nested-repeat patterns like (a+)+b are among the possible extensions below.

It also composes with the character class set operations (gh-152100): a repeat of a difference class that excludes its follower, such as [\w--\d]+\d, becomes possessive.

I have a working implementation validated by a differential fuzzer and will open a PR.

This is only a first step: the initial implementation is deliberately conservative, covering repeats of single-character atoms and of rigid multi-atom bodies, with the follower analysis traversing group boundaries, alternations, anchors and atomic groups. It can be extended later, for example to alternation bodies with pairwise-disjoint first characters, to word-boundary and lookahead followers, and to repeats of groups (the (a+)+b class).

Has this already been discussed elsewhere?

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

Linked PRs

gh-153044: Auto-possessify greedy repeats with a disjoint continuation #153048

pythongh-153044: Note the flag-context invariant of the complement rule

I surveyed the compiled literal regexes of the stdlib and of several regex-heavy projects (Pygments harvested by instantiating all 598 lexers). Of the patterns containing a greedy repeat, the share where at least one repeat becomes possessive:

corpus	possessified / candidates	rate
stdlib (`Lib/`, except `test_re`)	260 / 301	86%
docutils	39 / 47	83%
Django	27 / 33	82%
Pygments (9065 unique patterns)	4578 / 5632	81%
packaging	16 / 20	80%
setuptools	66 / 85	78%
Sphinx	69 / 90	77%
requests	7 / 9	78%
urllib3	7 / 8	88%
Jinja2	12 / 14	86%
dateutil	3 / 3	100%
soupsieve	12 / 18	67%

So the optimization applies to roughly four out of five real-world patterns with greedy repeats.

Fine idea! I'm unclear on where the claimed speedups come from, though. It's been standard practice "forever" to advise crafting regexps so that all possible follow-sets are disjoint. Which is likely why the pattern is so common.

But when that's so, backtracking a character a time can happen, but never goes on to resume heavy searching because there was only one possible branch to follow to begin with. That's linear-time backtracking at worst: "only backward, never forward again". Which seems to rule out catastrophic time behavior in fails-to-match cases (which is why that advice was given to begin with).

So are these speedups on "organic" (naturally occurring in real life) cases, or contrived ones?

Examples would help more than words 😉.

This is possible exactly because the repeat and the follower are disjoint. \w+\d cannot be possesified.

The speedup claim came from fuzzing. Example with real world pattern:

$ python3 -m timeit -s 'import re; p = re.compile(r"\$\(([A-Za-z][A-Za-z0-9_]*)\)"); s = "$(" + "a"*20000' 'p.match(s)'
5000 loops, best of 5: 73 usec per loop
$ python3 -m timeit -s 'import re; p = re.compile(r"\$\(([A-Za-z][A-Za-z0-9_]*+)\)"); s = "$(" + "a"*20000' 'p.match(s)'
20000 loops, best of 5: 14.9 usec per loop

This is 5x speedup, larger than claimed, because benchmarks were performed on the debug build -- it only shows 4x speed up.

"defuses some catastrophic backtracking" was overclaim, this was left for follow-ups, the current PR does not do it.

@mrabarnett

BTW, the third-party module regex also performs auto-possesisation. It may be not so deep, or deeper than in the proposed PR. @mrabarnett, you may find something interesting in the tricks used in this PR and follow-ups.

Candidates for the follow-ups (by their value for the real code): ① lazy after + group-repeat followers ([ \t]*(\r\n|\r|\n)?$, (\{%)(-?\s*)(filter)(\s+)(…)), ② \b uniform-wordness (\w+\b), ③ assertion transparency (^([ ]*)(?=\S)), ④ gc universe (\p{Lu}+\p{Z}), ⑤ disjoint-first alternation bodies ((ab|cd)+x). Then I will try to do something with most common examples of catastrophic backtracking.

pythongh-153044: Cap the size of a follower set

Cool! I had tried simpler examples, and saw much more modest speed gains in non-matching cases. Like

$ py -m timeit -s "import re;p=re.compile(r'\d+k');s='8'*1000000" "p.match(s)"
50 loops, best of 5: 5.84 msec per loop

$ py -m timeit -s "import re;p=re.compile(r'\d++k');s='8'*1000000" "p.match(s)"
50 loops, best of 5: 4.17 msec per loop

Which is more like what I expected from skipping (just!) linear-time "one way" backtracking.

YMMV, of course, and it's clear that yours is varying a lot 😉.

It depends on the cost of the backtrack and the follower check. Use more costly check (\d+(?:k|foo), \d+(?=k)¹) or add a group ((\d+)k) and observe the difference.

Not yet auto-possessified. ↩

pythongh-153044: Test each follower-set growth guard at its limit

pythongh-153044: Bound the follower-scan recursion

Thanks! Makes sense. I'm not familiar with our implementation. In the limit, a DFA picks the next state based solely on the next character to match, and never backtracks - but at the potential cost of constructing an exponential number of compile-time states. I tried a careful non-catastrophic regexp to match Python string literals (bounded by a double quote on each end). Follow sets are disjoint, burt there is a choice to make depending on whether the next character is a backslash (consume it and the next character) or double quote (rhw string literal ends)) or neither (consume it). In long nan-matching cases, adding possessive quantifiers sped it by a factor of 10. Impressive!

pythongh-153044: Drop the int(flags) conversion

pythongh-153044: Memoize the disjointness analysis

Navigation Menu

Repository navigation

Auto-possessify greedy repeats in regular expressions #153044

Feature or enhancement

Proposal

Has this already been discussed elsewhere?

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Auto-possessify greedy repeats in regular expressions #153044

Description

Feature or enhancement

Proposal

Has this already been discussed elsewhere?

Linked PRs

Activity

serhiy-storchaka commented on Jul 4, 2026

tim-one commented on Jul 5, 2026

serhiy-storchaka commented on Jul 5, 2026

serhiy-storchaka commented on Jul 5, 2026

tim-one commented on Jul 5, 2026

serhiy-storchaka commented on Jul 5, 2026

Footnotes

tim-one commented on Jul 5, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions