Possessive quantifiers and atomic groups

One pattern for a list of numeric ids, ^(?:\d+,?)+$, needed 1,572,864 turns of PCRE2’s matching loop to refuse twenty digits with a stray character at the end, and the same pattern with two extra plus signs needed 4. Both answer every valid list the same way. The two extra signs are possessive quantifierspossessive quantifier: A quantifier with an extra plus sign, such as x*+, x++, x?+ or x{m,n}+, that matches as much as a greedy one and then keeps it: it saves no shorter run, so a failure later in the pattern never makes it give characters back., the simplest way to tell an engine that a repetition is final.

The sections below walk through what a possessive quantifier and an atomic groupatomic group: A group written (?>...) that keeps the first match its own pattern finds: a failure later in the pattern cannot backtrack into it to make it try another way. x++ means the same as (?>x+). throw away, count the work they save with PCRE2’s own counters, show the cases where they change the answer rather than the speed, and end with the lookahead that gives JavaScript the same effect without the syntax.

A quantifier that keeps everything it took

Take the subject aaa and two patterns that look almost the same: a+a and a++a. The first matches all three characters. The second matches nothing at all. A plain greedy quantifiergreedy quantifier: A quantifier in its usual form, such as * or {2,5}, which repeats its atom as many times as it can and gives repetitions back one at a time only when the rest of the pattern cannot match otherwise. More in “Greedy and lazy quantifiers” takes as much as it can and then, if the rest of the pattern fails, hands characters back one at a time; this is backtrackingbacktracking: How a backtracking engine reacts to a failure: it returns to its most recent choice point, restores the text position it had there, and tries the next alternative. More in “How an engine finds a match, step by step”, and every position it could return to is a choice pointchoice point: A place in a pattern with more than one way to go on, such as an alternation. The engine takes the first way and saves the others so it can come back to them. More in “How an engine finds a match, step by step” the engine has to remember. A possessive quantifier takes as much as it can and keeps no such positions, so a failure after it ends the attempt at that starting point.

Step through both walks on the same three characters, and watch the single moment where they part:

The possessive forms are written with one extra plus sign after the quantifier: a*+, a++, a?+ and a{3,5}+. The three tabs below run the same five pairs in CPython, in PHP and in PCRE2, and all three agree: a++a and a*+a find nothing in aaa, while a++b still matches aaab, because there the characters the quantifier kept are followed by the character the pattern wants next.

"""What a possessive quantifier keeps, in CPython 3.14.8 (possessive forms need 3.11 or later).

Each pair runs the same subject through a plain quantifier and its possessive form, so the only difference in a
line is the extra + after the quantifier. 'no match' means re.search found nothing at all.
"""

import re

PAIRS = [
    (r"a+a", r"a++a", "aaa"),
    (r"a*a", r"a*+a", "aaa"),
    (r"a+b", r"a++b", "aaab"),
    (r"a{3,5}aa", r"a{3,5}+aa", "aaaaaa"),
    (r'"[^"]*"', r'"[^"]*+"', 'say "yes" twice'),
]


def found(pattern: str, subject: str) -> str:
    """The matched text as a quoted string, or 'no match'."""
    hit = re.search(pattern, subject)
    return repr(hit.group(0)) if hit else "no match"


print("subject            pattern      match        possessive   match")
print("-" * 68)
for plain, possessive, subject in PAIRS:
    print(f"{subject!r:18} {plain:12} {found(plain, subject):12} {possessive:12} {found(possessive, subject)}")

print()
print("The possessive forms are the atomic groups of the same items:")
for possessive, atomic in [(r"a*+", r"(?>a*)"), (r"a++", r"(?>a+)"), (r"a?+", r"(?>a?)"), (r"a{3,5}+", r"(?>a{3,5})")]:
    same = found(possessive + "a", "aaa") == found(atomic + "a", "aaa")
    print(f"  {possessive + 'a':12} and {atomic + 'a':14} give the same answer on 'aaa': {same}")

subject            pattern      match        possessive   match
--------------------------------------------------------------------
'aaa'              a+a          'aaa'        a++a         no match
'aaa'              a*a          'aaa'        a*+a         no match
'aaab'             a+b          'aaab'       a++b         'aaab'
'aaaaaa'           a{3,5}aa     'aaaaaa'     a{3,5}+aa    no match
'say "yes" twice'  "[^"]*"      '"yes"'      "[^"]*+"     '"yes"'

The possessive forms are the atomic groups of the same items:
  a*+a         and (?>a*)a        give the same answer on 'aaa': True
  a++a         and (?>a+)a        give the same answer on 'aaa': True
  a?+a         and (?>a?)a        give the same answer on 'aaa': True
  a{3,5}+a     and (?>a{3,5})a    give the same answer on 'aaa': True

<?php
// The same pairs in PHP 8.5.11, whose preg functions call the PCRE2 library that ships with it. Only the version
// number of that library is printed, never its release date.

$pairs = [
    ['/a+a/', '/a++a/', 'aaa'],
    ['/a*a/', '/a*+a/', 'aaa'],
    ['/a+b/', '/a++b/', 'aaab'],
    ['/a{3,5}aa/', '/a{3,5}+aa/', 'aaaaaa'],
    ['/"[^"]*"/', '/"[^"]*+"/', 'say "yes" twice'],
];

/** The matched text in quotes, or 'no match'. */
function found(string $pattern, string $subject): string
{
    return preg_match($pattern, $subject, $hit) === 1 ? "'{$hit[0]}'" : 'no match';
}

printf("PHP %s with PCRE2 %s\n\n", PHP_VERSION, strtok(PCRE_VERSION, ' '));
foreach ($pairs as [$plain, $possessive, $subject]) {
    printf("%-18s %-12s %-12s %-12s %s\n", "'{$subject}'", $plain, found($plain, $subject), $possessive, found($possessive, $subject));
}

PHP 8.5.11 with PCRE2 10.44

'aaa'              /a+a/        'aaa'        /a++a/       no match
'aaa'              /a*a/        'aaa'        /a*+a/       no match
'aaab'             /a+b/        'aaab'       /a++b/       'aaab'
'aaaaaa'           /a{3,5}aa/   'aaaaaa'     /a{3,5}+aa/  no match
'say "yes" twice'  /"[^"]*"/    '"yes"'      /"[^"]*+"/   '"yes"'

"""The same pairs in PCRE2 10.49, run through pcre2test.

pcre2test prints each pattern line, each indented subject under it, and then " 0:" with the text the pattern matched,
or "No match". The no_auto_possess modifier is used here so that each pattern runs exactly as it is written: without
it PCRE2 would make some of these quantifiers possessive on its own.
"""

from pcre2_session import run

run(r'''
# a plain + gives characters back, so the last a of the pattern finds one
/a+a/no_auto_possess
    aaa

# the possessive ++ keeps all three a characters, and the last a has nothing left
/a++a/no_auto_possess
    aaa

/a*a/no_auto_possess
    aaa

/a*+a/no_auto_possess
    aaa

# nothing is given back here either, but b follows the a characters, so the match stands
/a++b/no_auto_possess
    aaab

/a{3,5}aa/no_auto_possess
    aaaaaa

/a{3,5}+aa/no_auto_possess
    aaaaaa

# a quoted field: the class cannot match the closing quote, so keeping everything is safe
/"[^"]*+"/no_auto_possess
    say "yes" twice
''')

$ pcre2test -q patterns.txt   (PCRE2 10.49)
# a plain + gives characters back, so the last a of the pattern finds one
/a+a/no_auto_possess
    aaa
 0: aaa

# the possessive ++ keeps all three a characters, and the last a has nothing left
/a++a/no_auto_possess
    aaa
No match

/a*a/no_auto_possess
    aaa
 0: aaa

/a*+a/no_auto_possess
    aaa
No match

# nothing is given back here either, but b follows the a characters, so the match stands
/a++b/no_auto_possess
    aaab
 0: aaab

/a{3,5}aa/no_auto_possess
    aaaaaa
 0: aaaaaa

/a{3,5}+aa/no_auto_possess
    aaaaaa
No match

# a quoted field: the class cannot match the closing quote, so keeping everything is safe
/"[^"]*+"/no_auto_possess
    say "yes" twice
 0: "yes"

"""Runs a script of patterns and subjects through pcre2test, the test program of the PCRE2 10.49 library, and prints
what it printed.

pcre2test reads a pattern line such as /a.b/ (with modifiers after the closing slash, for example /a.b/dotall,utf),
then one subject per indented line, and prints each subject with " 0:" and the matched text (" 1:" and on for groups)
or "No match". A line starting with # is a comment and is printed as it is. Escapes in a subject such as \\r, \\n or
\\x{2028} stand for those characters (pcre2test's own subject escapes), so invisible characters can be tested.

The script is given in the example file itself, so the example's run record changes whenever the script does:

    from pcre2_session import run
    run(r'''
    /a.b/
        a\\rb
    ''')

The version banner and its release date are not printed (pcre2test -q); the session checks the version itself and
stops if this computer's pcre2test is not PCRE2 10.49, so a record never shows another version's behaviour.
"""

import re
import subprocess
import sys
import tempfile
from pathlib import Path

VERSION = "10.49"
_CANDIDATES = ("/opt/homebrew/bin/pcre2test", "/usr/local/bin/pcre2test")
_ENV = {"PATH": "/usr/bin:/bin", "LC_ALL": "C.UTF-8", "LANG": "C.UTF-8", "TZ": "UTC"}


def _tool() -> str:
    for candidate in _CANDIDATES:
        if Path(candidate).is_file():
            return candidate
    sys.exit("pcre2test (PCRE2 10.49) was not found")


def _check_version(tool: str) -> None:
    first = subprocess.run([tool, "-C"], capture_output=True, text=True, env=_ENV).stdout.splitlines()[:1]
    found = re.match(r"PCRE2 version (\S+)", first[0]) if first else None
    if not found or found.group(1) != VERSION:
        sys.exit(f"this session needs PCRE2 {VERSION}, found: {first[0] if first else 'nothing'}")


def run(script: str) -> None:
    """Prints the pcre2test transcript of the script (patterns, subjects and results)."""
    tool = _tool()
    _check_version(tool)
    lines = script.strip("\n").splitlines()
    text = "\n".join(_dedent(lines)) + "\n"
    with tempfile.TemporaryDirectory() as folder:
        source = Path(folder) / "patterns.txt"
        source.write_text(text, encoding="utf-8")
        done = subprocess.run([tool, "-q", str(source)], capture_output=True, text=True, encoding="utf-8", env=_ENV)
    print(f"$ pcre2test -q patterns.txt   (PCRE2 {VERSION})")
    sys.stdout.write(done.stdout)
    if done.stderr:
        sys.stdout.write(done.stderr)
    if done.returncode != 0:
        print(f"[exit status {done.returncode}]")
    sys.stdout.flush()


def _dedent(lines: list[str]) -> list[str]:
    """Removes the indentation the whole script shares, so it can sit indented inside a Python call."""
    widths = [len(line) - len(line.lstrip(" ")) for line in lines if line.strip()]
    cut = min(widths) if widths else 0
    return [line[cut:] for line in lines]

The last pair is the one worth copying: a quoted field written as "[^"]*+" keeps every character of "yes" and still matches, because the class inside it can never reach the closing quote. The Python tab also checks the equivalence the documentation states, that x*+ means the same as the atomic group (?>x*), by asking both forms about aaa and comparing their answers.

Atomic groups lock up a whole group

A possessive quantifier needs a quantifier to attach to. When the part to lock up has none, PCRE2’s and Python’s answer is (?>...), which matches the text its own pattern matches first and then refuses to be re-entered.

The clearest case is a group of alternatives. (?:in|inch)es matches inches: the group takes in, the rest of the pattern fails on ch, the engine returns and tries inch, and the match succeeds. Write the same group as (?>in|inch)es and there is no match at all, because the group keeps in and the alternatives behind it are gone. Turn the alternatives round, (?>inch|in)es, and the match is back: inside an atomic group, the order of the alternatives decides the outcome.

"""What an atomic group (?>...) locks up, in CPython 3.14.8 (atomic groups need 3.11 or later).

An atomic group holds whatever its own pattern matched first and never tries another way, so the order of the
alternatives inside it decides what the rest of the pattern sees.
"""

import re

CASES = [
    (r"(?:in|inch)es", "inches"),
    (r"(?>in|inch)es", "inches"),
    (r"(?>inch|in)es", "inches"),
    (r"(?:a|ab)c", "abc"),
    (r"(?>a|ab)c", "abc"),
    (r"(?>a|ab)bc", "abc"),
]


def found(pattern: str, subject: str) -> str:
    """The matched text as a quoted string, or 'no match'."""
    hit = re.search(pattern, subject)
    return repr(hit.group(0)) if hit else "no match"


for pattern, subject in CASES:
    print(f"{pattern:16} on {subject!r:10} -> {found(pattern, subject)}")

print()
print("One atomic group around a repeated group, on four id lists:")
weak = r"^(?:\d+,?)+$"
locked = r"^(?>(?:\d+,?)+)$"
for subject in ["1,2,3,4", "1234", "12,,3", "1,2,3x"]:
    answers = [bool(re.search(p, subject)) for p in (weak, locked)]
    print(f"  {subject!r:10} plain: {answers[0]!s:5} atomic: {answers[1]!s:5} same answer: {answers[0] == answers[1]}")

(?:in|inch)es    on 'inches'   -> 'inches'
(?>in|inch)es    on 'inches'   -> no match
(?>inch|in)es    on 'inches'   -> 'inches'
(?:a|ab)c        on 'abc'      -> 'abc'
(?>a|ab)c        on 'abc'      -> no match
(?>a|ab)bc       on 'abc'      -> 'abc'

One atomic group around a repeated group, on four id lists:
  '1,2,3,4'  plain: True  atomic: True  same answer: True
  '1234'     plain: True  atomic: True  same answer: True
  '12,,3'    plain: False atomic: False same answer: True
  '1,2,3x'   plain: False atomic: False same answer: True

"""Atomic groups in PCRE2 10.49, through pcre2test, with the alphabetic form PCRE2 also accepts.

The pattern lines are run with no_auto_possess, so each one behaves exactly as written. (*atomic:...) is PCRE2's
longer spelling of (?>...); both lock up what the group matched first.
"""

from pcre2_session import run

run(r'''
/(?:in|inch)es/no_auto_possess
    inches

# the group keeps "in", and the rest of the pattern meets "ch"
/(?>in|inch)es/no_auto_possess
    inches

# the same group with its alternatives the other way round
/(?>inch|in)es/no_auto_possess
    inches

# the alphabetic spelling of the same construct
/(*atomic:inch|in)es/no_auto_possess
    inches

# an atomic group around a repeated group: the id list still matches
/^(?>(?:\d+,?)+)$/no_auto_possess
    1,2,3,4
    12,,3
''')

$ pcre2test -q patterns.txt   (PCRE2 10.49)
/(?:in|inch)es/no_auto_possess
    inches
 0: inches

# the group keeps "in", and the rest of the pattern meets "ch"
/(?>in|inch)es/no_auto_possess
    inches
No match

# the same group with its alternatives the other way round
/(?>inch|in)es/no_auto_possess
    inches
 0: inches

# the alphabetic spelling of the same construct
/(*atomic:inch|in)es/no_auto_possess
    inches
 0: inches

# an atomic group around a repeated group: the id list still matches
/^(?>(?:\d+,?)+)$/no_auto_possess
    1,2,3,4
 0: 1,2,3,4
    12,,3
No match

The second half of each run wraps a whole repeated group, ^(?>(?:\d+,?)+)$, and asks it about four id lists. Every answer is the one the plain pattern gave, because the group covers everything between the two anchors: once it has matched as far as it can, there is nothing left for the rest of the pattern to want. PCRE2 accepts a longer spelling of the same construct, (*atomic:...), which the last-but-one block of its tab records.

PCRE2’s documentation puts it plainly: the two forms carry no difference in meaning, though a possessive quantifier may run slightly faster. Read the table in the other direction too, as the last row does: an atomic group covers cases a possessive quantifier cannot reach.

Counting the work a lock saves

Here is a pattern somebody might write for a list of numeric ids with optional commas: ^(?:\d+,?)+$. It is a repeated group holding a repetition, and that shape is where the work explodes. Each digit can belong to the inner \d+ or start a new turn of the outer group, so the number of ways to split a line doubles with every digit, and a line that cannot match is only refused after every split has been tried.

PCRE2 counts that work itself. Its match limit caps the turns the engine takes round its matching loop, and pcre2test can search for the smallest limit under which an attempt still completes, so the printed number is the work the attempt needed rather than a time that would differ on every machine. The run below asks for that number on four lengths of a line of digits that ends in a character no id list allows:

r"""How much work three forms of one pattern need, counted by PCRE2 10.49 itself.

The subject modifier find_limits_noheap makes pcre2test run the match again and again, lowering the match limit and
the depth limit until the attempt stops completing, and print the smallest values that still work. The match limit
counts the turns PCRE2 takes round its matching loop, so the printed number is the work the attempt needed: a
backtracking count, not a time.

The pattern is one somebody might write for a list of numeric ids with optional commas. \[1]{n} in a subject line is
pcre2test's way of writing n copies of the character 1, and the x at the end is the character that makes the list
invalid, so every form must answer "No match".
"""

from pcre2_session import run

run(r'''
# as written: a repeated group inside a repeated group
/^(?:\d+,?)+$/
    \[1]{8}x\=find_limits_noheap
    \[1]{12}x\=find_limits_noheap
    \[1]{16}x\=find_limits_noheap
    \[1]{20}x\=find_limits_noheap
    1,2,3,4\=find_limits_noheap

# both quantifiers made possessive
/^(?:\d++,?)++$/
    \[1]{8}x\=find_limits_noheap
    \[1]{20}x\=find_limits_noheap
    1,2,3,4\=find_limits_noheap

# the original pattern wrapped in one atomic group
/^(?>(?:\d+,?)+)$/
    \[1]{20}x\=find_limits_noheap
    1,2,3,4\=find_limits_noheap
''')

$ pcre2test -q patterns.txt   (PCRE2 10.49)
# as written: a repeated group inside a repeated group
/^(?:\d+,?)+$/
    \[1]{8}x\=find_limits_noheap
Minimum match limit = 384
Minimum depth limit = 10
No match
    \[1]{12}x\=find_limits_noheap
Minimum match limit = 6144
Minimum depth limit = 14
No match
    \[1]{16}x\=find_limits_noheap
Minimum match limit = 98304
Minimum depth limit = 18
No match
    \[1]{20}x\=find_limits_noheap
Minimum match limit = 1572864
Minimum depth limit = 22
No match
    1,2,3,4\=find_limits_noheap
Minimum match limit = 9
Minimum depth limit = 9
 0: 1,2,3,4

# both quantifiers made possessive
/^(?:\d++,?)++$/
    \[1]{8}x\=find_limits_noheap
Minimum match limit = 4
Minimum depth limit = 3
No match
    \[1]{20}x\=find_limits_noheap
Minimum match limit = 4
Minimum depth limit = 3
No match
    1,2,3,4\=find_limits_noheap
Minimum match limit = 7
Minimum depth limit = 3
 0: 1,2,3,4

# the original pattern wrapped in one atomic group
/^(?>(?:\d+,?)+)$/
    \[1]{20}x\=find_limits_noheap
Minimum match limit = 5
Minimum depth limit = 5
No match
    1,2,3,4\=find_limits_noheap
Minimum match limit = 10
Minimum depth limit = 10
 0: 1,2,3,4

Every four digits multiply the plain pattern’s work by sixteen, while the possessive form stays at 4 turns whatever the length, because no split is ever tried twice. The depth limit, which measures how deep the engine’s own stack of saved positions goes, follows the same split: 22 against 3 at twenty digits. On a valid list, 1,2,3,4, the plain pattern needs 9 turns, the possessive one 7 and the version wrapped in a single atomic group 10, and all three match.

PCRE2 possessifies some quantifiers by itself

Before you reach for a plus sign, it is worth knowing that one engine has already done part of the work. Auto-possessificationauto-possessification: A step PCRE2 takes while compiling a pattern: where the item after a quantifier cannot match what that quantifier repeats, it makes the quantifier possessive by itself. (*NO_AUTO_POSSESS) switches it off. is a step PCRE2 takes while compiling a pattern: where the item after a quantifier cannot possibly match what the quantifier repeats, it makes that quantifier possessive on its own, because coming back could not help.

\d+x is such a pattern, since x is not a digit. The run below puts it on forty copies of one digit, first as PCRE2 compiles it by default and then with that step switched off:

r"""PCRE2 10.49 making a quantifier possessive on its own, and the same pattern with that step switched off.

Both lines run /\d+x/ on forty copies of the digit 1, which cannot match. no_start_optimize is on in both, so the
first run is not skipped by the separate check for a required character, and the two numbers can be compared.
no_auto_possess switches off the step that rewrites \d+x as \d++x.

find_limits_noheap prints the smallest match limit and depth limit under which the attempt still completes, so the
match limit is the number of turns PCRE2 took round its matching loop.
"""

from pcre2_session import run

run(r'''
# PCRE2 decides for itself that \d+ need not give anything back, because x is not a digit
/\d+x/no_start_optimize
    \[1]{40}\=find_limits_noheap

# the same pattern with that decision switched off: one turn of the loop per digit given back
/\d+x/no_start_optimize,no_auto_possess
    \[1]{40}\=find_limits_noheap

# writing the possessive quantifier by hand gives what PCRE2 already did
/\d++x/no_start_optimize,no_auto_possess
    \[1]{40}\=find_limits_noheap

# a quantifier whose own characters can follow it is never possessified: \s+ may give a newline back to $
/\s+$/no_start_optimize
    \[ ]{40}x\=find_limits_noheap

/\s++$/no_start_optimize
    \[ ]{40}x\=find_limits_noheap
''')

$ pcre2test -q patterns.txt   (PCRE2 10.49)
# PCRE2 decides for itself that \d+ need not give anything back, because x is not a digit
/\d+x/no_start_optimize
    \[1]{40}\=find_limits_noheap
Minimum match limit = 2
Minimum depth limit = 2
No match

# the same pattern with that decision switched off: one turn of the loop per digit given back
/\d+x/no_start_optimize,no_auto_possess
    \[1]{40}\=find_limits_noheap
Minimum match limit = 41
Minimum depth limit = 3
No match

# writing the possessive quantifier by hand gives what PCRE2 already did
/\d++x/no_start_optimize,no_auto_possess
    \[1]{40}\=find_limits_noheap
Minimum match limit = 2
Minimum depth limit = 2
No match

# a quantifier whose own characters can follow it is never possessified: \s+ may give a newline back to $
/\s+$/no_start_optimize
    \[ ]{40}x\=find_limits_noheap
Minimum match limit = 41
Minimum depth limit = 3
No match

/\s++$/no_start_optimize
    \[ ]{40}x\=find_limits_noheap
Minimum match limit = 2
Minimum depth limit = 2
No match

Two turns of the matching loop become 41 when the step is off: one turn for each digit handed back. Writing \d++x by hand gives exactly the two turns of the default, which is the point of the step. The last pair shows where it cannot help: \s+$ keeps its 41 turns, because $ may stand before a final newline and a newline is white space, so the repetition really might have to give one character back. Written as \s++$ the same pattern takes 2.

Rewriting a pattern without changing its answers

A lock is not a performance setting; it is a change to the pattern’s meaning that often happens to be faster. The honest way to apply one is to decide which lines must be accepted and which refused, then ask both patterns about every line. The run below does that with a function that reports each line where the two disagree:

"""A check that compares a pattern with its possessive rewrite on a fixed list of lines, in CPython 3.14.8.

Rewriting a quantifier as possessive is safe only when the new pattern accepts and refuses exactly the same text.
The agree() function answers that with no timing at all: it asks both patterns about every line and reports where
they disagree. Lines a parser must accept and lines it must refuse are both in each list.
"""

import re

SETTINGS = ["rows=20;page=2;", "rows=20;page=2", "rows=20", "rows=;page=2", "rows 20;", ""]
QUOTED = ['"yes"', 'say "yes" twice', '"yes" and "no"', '"unterminated', 'no quotes at all']


def agree(before: str, after: str, lines: list[str]) -> bool:
    """Prints the two patterns, every line on which they differ, and whether they agreed everywhere."""
    print(f"  {before}  ->  {after}")
    same = True
    for line in lines:
        answers = (bool(re.search(before, line)), bool(re.search(after, line)))
        if answers[0] != answers[1]:
            same = False
            print(f"    differs on {line!r}: before {answers[0]}, after {answers[1]}")
    print(f"    same answers on all {len(lines)} lines: {same}")
    return same


print("A settings line, with both quantifiers made possessive:")
agree(r"^(?:\w+=\w+;?)+$", r"^(?:\w++=\w++;?)++$", SETTINGS)

print()
print("A quoted field, rewritten in two ways:")
agree(r'"[^"]*"', r'"[^"]*+"', QUOTED)
agree(r'".*"', r'".*+"', QUOTED)

print()
print("What the second rewrite does to one line:")
for pattern in [r'".*"', r'".*+"', r'"[^"]*+"']:
    hit = re.search(pattern, '"yes" and "no"')
    got = repr(hit.group(0)) if hit else "no match"
    print(f"  {pattern:12} on the line with two quoted words -> {got}")

A settings line, with both quantifiers made possessive:
  ^(?:\w+=\w+;?)+$  ->  ^(?:\w++=\w++;?)++$
    same answers on all 6 lines: True

A quoted field, rewritten in two ways:
  "[^"]*"  ->  "[^"]*+"
    same answers on all 5 lines: True
  ".*"  ->  ".*+"
    differs on '"yes"': before True, after False
    differs on 'say "yes" twice': before True, after False
    differs on '"yes" and "no"': before True, after False
    same answers on all 5 lines: False

What the second rewrite does to one line:
  ".*"         on the line with two quoted words -> '"yes" and "no"'
  ".*+"        on the line with two quoted words -> no match
  "[^"]*+"     on the line with two quoted words -> '"yes"'

The settings pattern ^(?:\w+=\w+;?)+$ and its possessive form agree on all six lines, so the rewrite is safe. The quoted field shows both outcomes side by side: "[^"]*" keeps its five answers when it becomes "[^"]*+", while ".*" rewritten as ".*+" loses three of them, since . happily matches a quote and the locked repetition runs to the end of the line and never gives the closing quote back.

That rule is also why a check like this one belongs in your test file next to the pattern. It costs a list of lines, it fails on the version that changed its answers, and it passes on the version that only changed its cost.

Which flavours accept them, and what the others do

Both forms came from Perl’s family of engines, so a flavourflavour: A particular regular-expression syntax and feature set, such as ECMAScript, Python re, PCRE2 or RE2; a pattern is written for one of them. More in “What a regular expression is and where it runs” built on a different model may not have them at all. The runs of this page cover JavaScript, Python, PHP, PCRE2 and Go; the Java, Ruby and Perl rows follow each flavour’s own documentation, since no program of theirs runs on this page.

Python’s two features arrived together in 3.11, so a pattern with either form stops an older interpreter at compile time. Ruby’s documentation states that its brace quantifiers have no possessive form, which leaves (?>x{3,5}) as the way to write one there. JavaScript refuses every form, and so does Go, which needs none: its search follows every way at once, so a repeated group inside a repeated group never makes it re-try a split, and its documentation promises a running time that grows in proportion to the length of the input.

// What JavaScript does with a possessive quantifier and an atomic group. Only the error's name is printed, because
// the wording of a message differs between engines; the name is the part the language fixes.
// Press Edit, add a pattern of your own to TRIED, and run it again.

const TRIED = ['a++b', 'a*+a', 'a?+a', 'a{3,5}+aa', '(?>a+)a', '(*atomic:a+)a'];

for (const source of TRIED) {
  let answer;
  try {
    new RegExp(source);
    answer = 'compiled';
  } catch (error) {
    answer = error.name;
  }
  console.log(`new RegExp(${JSON.stringify(source)}) -> ${answer}`);
}

// The forms that do compile: a plain quantifier, a plain group, and the lookahead with a backreference.
console.log('');
for (const source of ['a+a', '(?:a|ab)c', '(?=(a+))\\1a']) {
  let answer;
  try {
    new RegExp(source);
    answer = 'compiled';
  } catch (error) {
    answer = error.name;
  }
  console.log(`new RegExp(${JSON.stringify(source)}) -> ${answer}`);
}

new RegExp("a++b") -> SyntaxError
new RegExp("a*+a") -> SyntaxError
new RegExp("a?+a") -> SyntaxError
new RegExp("a{3,5}+aa") -> SyntaxError
new RegExp("(?>a+)a") -> SyntaxError
new RegExp("(*atomic:a+)a") -> SyntaxError

new RegExp("a+a") -> compiled
new RegExp("(?:a|ab)c") -> compiled
new RegExp("(?=(a+))\\1a") -> compiled

// Go's regexp package follows RE2 syntax, which has neither possessive quantifiers nor atomic groups. Each pattern
// is compiled and the error, if any, is printed. The last lines run the pattern RE2 does accept.
package main

import (
	"fmt"
	"regexp"
	"strings"
)

func main() {
	for _, pattern := range []string{`a++b`, `a*+a`, `a{3,5}+aa`, `(?>a+)a`, `(?:a|ab)c`} {
		if _, err := regexp.Compile(pattern); err != nil {
			fmt.Printf("%-12s -> %v\n", pattern, err)
		} else {
			fmt.Printf("%-12s -> compiled\n", pattern)
		}
	}

	// RE2 needs none of them: it walks every way at once, so a repeated group inside a repeated group is safe.
	ids := regexp.MustCompile(`^(?:\d+,?)+$`)
	for _, subject := range []string{"1,2,3,4", "12,,3", strings.Repeat("1", 24) + "x"} {
		fmt.Printf("%-28q -> %t\n", subject, ids.MatchString(subject))
	}
}

a++b         -> error parsing regexp: invalid nested repetition operator: `++`
a*+a         -> error parsing regexp: invalid nested repetition operator: `*+`
a{3,5}+aa    -> error parsing regexp: invalid nested repetition operator: `{3,5}+`
(?>a+)a      -> error parsing regexp: invalid or unsupported Perl syntax: `(?>`
(?:a|ab)c    -> compiled
"1,2,3,4"                    -> true
"12,,3"                      -> false
"111111111111111111111111x"  -> false

The JavaScript run prints SyntaxError for all six spellings, in V8 and in its browser twin alike; the error’s name is printed rather than its message, because the wording differs between engines. Go names the construct it refused: a nested repetition operator for the possessive forms, unsupported Perl syntax for (?>. Its last three lines put the plain id pattern to work, and the 25-character line that cannot match is refused at once with no lock at all.

Which way to lock a repetition up depends on the engine and on the pattern. Answer the three questions below and watch the options that do not fit drop out:

In short: write the possessive form where the engine accepts it and one quantifier covers the part to lock, use (?>...) for anything larger, and write a more precise pattern whenever the repetition has a clear end character, because that keeps the answers as well as the cost.

JavaScript has no possessive form, but its lookahead is atomic

The missing syntax does not mean the effect is out of reach. In ECMA-262 a lookahead settles on the first way its inner pattern fits where it stands, and the engine never returns into a finished lookahead to look for another fit. A lookahead that captures what it matched, followed by a backreference to that capture, therefore behaves like an atomic group: the lookahead finds its one answer, and the backreference matches the same text for real.

The shape is (?=(X))\1 in place of (?>X). The run below puts it beside the plain forms on the subjects of this lesson, then on a list of ids:

// JavaScript's own way to lock a repetition up: a lookahead that captures what it matched, and a backreference
// that matches the same text again. The lookahead is never re-entered, so the capture cannot be adjusted later.
// Press Edit, put your own list in SUBJECTS, and run it again.

const PAIRS = [
  ['plain repetition', /^(a+)a$/, 'aaa'],
  ['locked repetition', /^(?=(a+))\1a$/, 'aaa'],
  ['plain group', /^(?:a|ab)c$/, 'abc'],
  ['locked group', /^(?=(a|ab))\1c$/, 'abc'],
];

for (const [label, pattern, subject] of PAIRS) {
  console.log(`${label.padEnd(18)} ${String(pattern).padEnd(20)} on ${JSON.stringify(subject)} -> ${pattern.test(subject)}`);
}

// The same answers on a list of ids, with the repetition locked up.
const plain = /^(?:\d+,?)+$/;
const locked = /^(?=((?:\d+,?)+))\1$/;
const SUBJECTS = ['1,2,3,4', '1234', '1,2,', '12,,3', '1,2,3x', ''];

console.log('');
let agree = true;
for (const subject of SUBJECTS) {
  const a = plain.test(subject);
  const b = locked.test(subject);
  agree = agree && a === b;
  console.log(`  ${JSON.stringify(subject).padEnd(10)} plain: ${String(a).padEnd(6)} locked: ${String(b).padEnd(6)} same answer: ${a === b}`);
}
console.log(`same answer on all ${SUBJECTS.length} subjects: ${agree}`);

// One id list of 24 digits that no comma can save, timed coarsely: the numbers of a single run are left out, because
// they differ on every machine, and only the two thresholds are printed.
const bad = `${'1'.repeat(24)}x`;
let started = Date.now();
plain.test(bad);
const plainMs = Date.now() - started;
started = Date.now();
locked.test(bad);
const lockedMs = Date.now() - started;
console.log('');
console.log(`on ${bad.length} characters that cannot match: the plain pattern took over 20 ms: ${plainMs > 20}`);
console.log(`the locked pattern took under 10 ms: ${lockedMs < 10}`);

plain repetition   /^(a+)a$/            on "aaa" -> true
locked repetition  /^(?=(a+))\1a$/      on "aaa" -> false
plain group        /^(?:a|ab)c$/        on "abc" -> true
locked group       /^(?=(a|ab))\1c$/    on "abc" -> false

  "1,2,3,4"  plain: true   locked: true   same answer: true
  "1234"     plain: true   locked: true   same answer: true
  "1,2,"     plain: true   locked: true   same answer: true
  "12,,3"    plain: false  locked: false  same answer: true
  "1,2,3x"   plain: false  locked: false  same answer: true
  ""         plain: false  locked: false  same answer: true
same answer on all 6 subjects: true

on 25 characters that cannot match: the plain pattern took over 20 ms: true
the locked pattern took under 10 ms: true

/^(a+)a$/ matches aaa and /^(?=(a+))\1a$/ does not, exactly as a++a does not in Python; /^(?=(a|ab))\1c$/ refuses abc just as (?>a|ab)c does. On six id lists the locked pattern gives every answer the plain one gave, and on a line of 24 digits that cannot match it is the plain pattern that takes over 20 milliseconds while the locked one stays under 10, in both engines. Press Edit, put your own lines in SUBJECTS, and run it again.

TC39’s proposal-regexp-atomic-operators repository proposes atomic operators for JavaScript, but the language itself has no such syntax, so a pattern written today needs the lookahead. Since the trick rests on a backreference, it is unavailable in RE2 engines, which have neither backreferences nor lookahead.

Practise: three patterns to lock up

The exercise gives you three patterns from a parser that reads its own log lines, each with a list of lines it must accept and a list it must refuse. Rewrite each one so that every answer stays the same and no split is ever tried twice: with possessive quantifiers or an atomic group in Python, and with the lookahead and backreference in JavaScript. The sample tests check both the answers and the construct.

// Three patterns of a log reader. Each one works and each one tries every way of splitting a line before it refuses
// one. Rewrite all three so that they keep their answers and lock their repetition up.
//
// JavaScript refuses a++ and (?>...), so the lock is a lookahead that captures what it matched, followed by a
// backreference to that capture: (?=(X))\1 in place of (?>X).

export const PATTERNS = {
  // a list of ids: digits with optional commas
  ids: '^(?:\\d+,?)+$',
  // name=value pairs with optional semicolons
  settings: '^(?:\\w+=\\w+;?)+$',
  // one quoted field that may hold a backslash escape
  quoted: '^"(?:[^"\\\\]|\\\\.)*"$',
};

/** Whether the named pattern accepts the line. */
export function accepts(name, line) {
  return new RegExp(PATTERNS[name]).test(line);
}

import { test, assert } from 'mysmartcopilot:test';
import { PATTERNS, accepts } from './patterns.mjs';

const LINES = {
  ids: {
    accept: ['1', '12,34', '1,2,3', '1,2,', '007,8'],
    refuse: ['', '1,,2', '1,2,x', 'a,1', ',1'],
  },
  settings: {
    accept: ['rows=20', 'rows=20;', 'rows=20;page=2', 'a=1;b=2;'],
    refuse: ['', 'rows=;page=2', 'rows 20;', '=20;', 'rows=20;;'],
  },
  quoted: {
    accept: ['""', '"yes"', '"say \\"yes\\""', '"a;b=c"'],
    refuse: ['', 'yes', '"unterminated', '"yes" twice', '"yes"x'],
  },
};

// A lock in JavaScript: a lookahead that captures, and a backreference to that capture.
const LOCKED = /\(\?=\([\s\S]*\)\)[\s\S]*\\[1-9]/;

for (const [name, lines] of Object.entries(LINES)) {
  test(`${name}: every line that was accepted is still accepted`, () => {
    for (const line of lines.accept) {
      assert.equal(accepts(name, line), true, `${name} should accept ${JSON.stringify(line)}`);
    }
  });

  test(`${name}: every line that was refused is still refused`, () => {
    for (const line of lines.refuse) {
      assert.equal(accepts(name, line), false, `${name} should refuse ${JSON.stringify(line)}`);
    }
  });

  test(`${name}: the repetition is locked up`, () => {
    const source = PATTERNS[name];
    assert.ok(typeof source === 'string' && source.length > 0, `PATTERNS.${name} should be a pattern string`);
    assert.ok(
      LOCKED.test(source),
      `${name} still has nothing to stop the engine re-trying a split: use (?=(X))\\1 around the repetition`,
    );
  });
}

test('each pattern still compiles on its own', () => {
  for (const name of Object.keys(LINES)) {
    const built = new RegExp(PATTERNS[name]);
    assert.ok(built instanceof RegExp, `${name} should compile`);
  }
});

"""Three patterns of a log reader. Each one works and each one tries every way of splitting a line before it refuses
one. Rewrite all three so that they keep their answers and lock their repetition up.

Python 3.11 and later accept possessive quantifiers (*+, ++, ?+) and atomic groups ((?>...)); either form counts as
a lock here.
"""

import re

PATTERNS = {
    # a list of ids: digits with optional commas
    "ids": r"^(?:\d+,?)+$",
    # name=value pairs with optional semicolons
    "settings": r"^(?:\w+=\w+;?)+$",
    # one quoted field that may hold a backslash escape
    "quoted": r'^"(?:[^"\\]|\\.)*"$',
}


def accepts(name: str, line: str) -> bool:
    """Whether the named pattern accepts the line."""
    return re.search(PATTERNS[name], line) is not None

"""Sample tests for the three patterns: the same answers as before, and a lock in each pattern."""

import re

from patterns import PATTERNS, accepts

LINES = {
    "ids": {
        "accept": ["1", "12,34", "1,2,3", "1,2,", "007,8"],
        "refuse": ["", "1,,2", "1,2,x", "a,1", ",1"],
    },
    "settings": {
        "accept": ["rows=20", "rows=20;", "rows=20;page=2", "a=1;b=2;"],
        "refuse": ["", "rows=;page=2", "rows 20;", "=20;", "rows=20;;"],
    },
    "quoted": {
        "accept": ['""', '"yes"', '"say \\"yes\\""', '"a;b=c"'],
        "refuse": ["", "yes", '"unterminated', '"yes" twice', '"yes"x'],
    },
}

# A lock in Python: a possessive quantifier, or an atomic group.
LOCKED = re.compile(r"(?:\*\+|\+\+|\?\+|\}\+|\(\?>)")


def test_accepted_lines_are_still_accepted():
    for name, lines in LINES.items():
        for line in lines["accept"]:
            assert accepts(name, line) is True, f"{name} should accept {line!r}"


def test_refused_lines_are_still_refused():
    for name, lines in LINES.items():
        for line in lines["refuse"]:
            assert accepts(name, line) is False, f"{name} should refuse {line!r}"


def test_every_pattern_carries_a_lock():
    for name in LINES:
        source = PATTERNS[name]
        assert isinstance(source, str) and source, f"PATTERNS[{name!r}] should be a pattern string"
        assert LOCKED.search(source), (
            f"{name} still has nothing to stop the engine re-trying a split: "
            "use a possessive quantifier or an atomic group"
        )


def test_every_pattern_still_compiles():
    for name in LINES:
        assert re.compile(PATTERNS[name]) is not None, f"{name} should compile"

Now put the seven ideas to the test. The check below picks the one you handle least well and asks about that first, with a word on every choice the moment you pick it:

Interview questions

Warm-up: what does the second plus sign in \d++ do, and when does it change what a pattern matches?

It makes the repetition final. \d+ matches as many digits as it can and remembers every shorter run it could fall back to; \d++ matches the same digits and remembers nothing, so if the rest of the pattern fails, the engine gives up at that starting point instead of handing digits back. The answer changes whenever the characters after the repetition are ones the repetition itself could have matched: a*+a never matches aaa, because a*+ keeps all three. When the next part of the pattern is outside what the repetition matches, as in \d++x or "[^"]*+", the accepted text is identical and only the work changes. x++ is a shorter spelling of the atomic group (?>x+), and Python has had both since 3.11.

Two questions go further, one on a pattern that has to be made cheap without changing what it accepts, and one on the same fix in a browser. Settle on your own opening move for each, and see where its page begins:

Key takeaways

• A possessive quantifier matches as much as a greedy one and then throws away every position the engine could come back to, so a++a and a*+a find nothing in aaa while a+a matches all three characters.
• An atomic group (?>...) does the same for anything inside it, which is how a group of alternatives is locked: (?>in|inch)es refuses inches, and (?>inch|in)es accepts it.
• The work saved grows with the input: PCRE2 needed 1,572,864 turns of its matching loop to refuse twenty digits with the plain pattern and 4 with the possessive one, and both matched every valid list.
• PCRE2 makes some quantifiers possessive while compiling, so \d+x already costs 2 turns instead of 41, but \s+$ cannot be treated that way because a newline is white space.
• A rewrite is safe only when both patterns answer the same way on a list of lines you choose: "[^"]*+" keeps its answers and ".*+" loses three of them.
• JavaScript and Go refuse both forms; in JavaScript the lookahead and backreference (?=(X))\1 give the same effect, while Go needs no lock because it re-tries nothing.