Possessive Quantifiers — *+ ++ ?+

Disable backtracking for this quantifier

Possessive quantifiers — written as *+, ++, ?+, {n,m}+ — match like greedy, but once they've consumed something, they REFUSE to give it back. No backtracking through this quantifier.

This sounds restrictive, but it's the secret to writing fast, ReDoS-safe patterns. Backtracking is what makes regex slow on adversarial input. Disable backtracking on the parts where you know backtracking won't help, and the engine flies.

The performance win

Pattern a+b against aaaaaaa: greedy a+ grabs all 7 a's, then can't match b, backtracks one a at a time (7 attempts) before failing. Possessive a++b: grabs all 7 a's, can't match b, refuses to backtrack, fails immediately. Same result, much less work.

For ReDoS protection (Track 8), this is everything. Patterns like (a+)+b are exponential because a+ can backtrack into the outer +. Make it possessive — (a++)+b — and it's linear.

Flavor support

Possessive quantifiers exist in PCRE, Java, Ruby (1.9+), .NET (5+). They don't exist in Python's re (use regex module which adds them) or in JavaScript. RE2 doesn't backtrack at all, so it doesn't need them.

If your engine doesn't support possessive, the equivalent is the atomic group (?>...), covered in Track 8.

Code

Possessive quantifiers (PCRE/Java/Ruby)·text

# In Java
Pattern.matches("a++b", "aaaaaaa")  // false, no backtracking attempted

# In PHP/PCRE
preg_match('/a++b/', 'aaaaaaa')  // 0

# In Python (need third-party 'regex' library, not built-in 're')
import regex
regex.findall(r'a++b', 'aaaaaaa')  # []  — fails fast

# Atomic group equivalent — works in Python re too
import re
re.findall(r'(?>a+)b', 'aaaaaaa')  # if your re supports atomic groups

# Performance difference visible on large input
# 'a' * 30 + 'X'  — adversarial input
# (a+)+ → exponential time, may hang for minutes
# (a++)+ → linear time, fails immediately

Possessive Quantifiers — *+ ++ ?+

Disable backtracking for this quantifier

The performance win

Flavor support

Code

External links

Exercise

Progress

Comments 0