Atomic Groups — (?>...)

The 'commit and don't look back' group

An atomic group (?>...) matches like a normal group, BUT once it succeeds, the engine refuses to backtrack into it. Whatever it consumed is locked in. The engine moves forward; if the rest of the pattern fails, it doesn't try alternatives inside the atomic group.

Why this matters

Backtracking inside loops is the source of all catastrophic regex performance. (\w+)*X against a long string of word characters with no X at the end will try every possible split of the input among the iterations of \w+ — exponential.

Make the inner group atomic: (?>\w+)*X. Now once \w+ grabs everything it can, the engine doesn't try to give characters back. Fails immediately, linear time.

Engine support

Python re: Atomic groups added in Python 3.11. Earlier versions: install third-party regex.
PCRE, Perl, Java, Ruby, .NET: Supported.
JavaScript: Not supported (yet).
RE2/Go: Doesn't backtrack at all, so doesn't need atomic groups.

Mental model

Atomic groups are how you tell the engine "once you've matched this, don't second-guess yourself." Use them whenever a pattern's inner section won't have a valid alternative match if the first one fails — which is almost always for things like "one or more digits," "one or more word characters," "the rest of this line."

Code

Atomic groups vs vanilla·python

import re

# Vanilla — engine will backtrack inside (\w+)*
# This is the canonical ReDoS shape
# re.search(r'(\w+)*X', 'a' * 30)  # would hang for many seconds

# Atomic — refuses to backtrack into (?>\w+)
# Python 3.11+
import sys
if sys.version_info >= (3, 11):
    re.search(r'(?>\w+)*X', 'a' * 30)  # fails immediately

# Practical: extract until end-of-line, no backtracking
# Vanilla
re.match(r'(\w+)\s+(\w+)', 'hello world')

# Atomic — same result, faster on adversarial input
if sys.version_info >= (3, 11):
    re.match(r'(?>\w+)\s+(?>\w+)', 'hello world')

# When the next thing in the pattern fails, atomic wins big
# Match digits followed by 'kg', failing fast on bad input
for _ in range(100000):
    re.search(r'\d+kg', '1234567890123456789' * 100)  # slow due to backtracking
# vs
if sys.version_info >= (3, 11):
    for _ in range(100000):
        re.search(r'(?>\d+)kg', '1234567890123456789' * 100)  # fast

Atomic Groups — (?>...)

The 'commit and don't look back' group

Why this matters

Engine support

Mental model

Code

External links

Exercise

Progress

Comments 0