The previous recipe explains the difference between greedy and lazy quantifiers, and how they backtrack. In some situations, this backtracking is unnecessary.

‹d+› uses a greedy quantifier, and ‹d+?› uses a lazy quantifier. They both match the same thing: an integer. Given the same subject text, both will find the exact same matches. Any backtracking that is done is unnecessary. Rewrite this regular expression to explicitly eliminate all backtracking, making the regular expression more efficient.

d++

The easiest solution is to use a possessive quantifier. But it is supported only in a few recent regex flavors.

(?>d+)

An atomic group provides exactly the same functionality, using a slightly less readable syntax. Support for atomic grouping is more widespread than support for possessive quantifiers.

JavaScript and Python do not support possessive quantifiers or atomic grouping. There is no way to eliminate needless backtracking with these two regex flavors.

A possessive quantifier is similar to a greedy quantifier: it tries to repeat as many times as possible. The difference is that a possessive quantifier will never give back, not even when giving back is the only way that the remainder of the regular expression could match. Possessive quantifiers do not keep backtracking positions.

You can make any quantifier possessive by placing a plus sign after it. For example, ‹*+›, ‹++›, ‹?+›, and ‹{7,42}+› are all possessive quantifiers.

Possessive quantifiers are supported by Java 4 and later, the first Java release to include the java.util.regex package. All versions of PCRE discussed in this book (version 4 to 7) support possessive quantifiers. Perl supports them starting with Perl 5.10. Classic Ruby regular expressions do not support possessive quantifiers, but the Oniguruma engine, which is the default in Ruby 1.9, does support them.

Wrapping a greedy quantifier inside an atomic group has the exact same effect as using a possessive quantifier. When the regex engine exits the atomic group, all backtracking positions remembered by quantifiers and alternation inside the group are thrown away. The syntax is ‹(?>⋯)›, where ‹⋯› is any regular expression. An atomic group is essentially a noncapturing group, with the extra job of refusing to backtrack. The question mark is not a quantifier; the opening bracket simply consists of the three characters ‹(?>›.

When you apply the regex ‹d++› (possessive) to 123abc 456, ‹› matches at the start of the subject, and ‹d++› matches 123. So far, this is no different from what ‹d+› (greedy) would do. But then the second ‹› fails to match between 3 and a.

The possessive quantifier did not store any backtracking positions. Since there are no other quantifiers or alternation in this regular expression, there are no further options to try when the second word boundary fails. The regex engine immediately declares failure for the match attempt starting at 1.

The regex engine does attempt the regex starting at the next character positions in the string, and using a possessive quantifier does not change that. If the regex must match the whole subject, use anchors, as discussed in Recipe 2.5. Eventually, the regex engine will attempt the regex starting at the 4 and find the match 456.

The difference with the greedy quantifier is that when the second ‹› fails during the first match attempt, the greedy quantifier will backtrack. The regex engine will then (needlessly) test ‹› between 2 and 3, and between 1 and 2.

The matching process using atomic grouping is essentially the same. When you apply the regex ‹(?>d+)› (possessive) to 123abc 456, the word boundary matches at the start of the subject. The regex engine enters the atomic group, and ‹d+› matches 123. Now the engine exits the atomic group. At this point, the backtracking positions remembered by ‹d+› are thrown away. When the second ‹› fails, the regex engine is left without any further options, causing the match attempt to fail immediately. As with the possessive quantifier, eventually 456 will be found.

We describe the possessive quantifier as failing to remember backtracking positions, and the atomic group as throwing them away. This makes it easier to understand the matching process, but don’t get hung up on the difference, as it may not even exist in the regex flavor you’re working with. In many flavors, ‹x++› is merely syntactic sugar for ‹(?>x+)›, and both are implemented in exactly the same way. Whether the engine never remembers backtracking positions or throws them away later is irrelevant for the final outcome of the match attempt.

Where possessive quantifiers and atomic grouping differ is that a possessive quantifier applies only to a single regular expression token, whereas an atomic group can wrap a whole regular expression.

‹w++d++› and ‹(?>w+d+)› are not the same at all. ‹w++d++›, which is the same as ‹(?>w+)(?>d+)›, will not match abc123. ‹w++› matches abc123 entirely. Then, the regex engine attempts ‹d++› at the end of the subject text. Since there are no further characters that can be matched, ‹d++› fails. Without any remembered backtracking positions, the match attempt fails.

‹(?>w+d+)› has two greedy quantifiers inside the same atomic group. Within the atomic group, backtracking occurs normally. Backtracking positions are thrown away only when the engine exits the whole group. When the subject is abc123, ‹w+› matches abc123. The greedy quantifier does remember backtracking positions. When ‹d+› fails to match, ‹w+› gives up one character. ‹d+› then matches 3. Now, the engine exits the atomic group, throwing away all backtracking positions remembered for ‹w+› and ‹d+›. Since the end of the regex has been reached, this doesn’t really make any difference. An overall match is found.

If the end had not been reached, as in ‹(?>w+d+)d+›, we would be in the same situation as with ‹w++d++›. The second ‹d+› has nothing left to match at the end of the subject. Since the backtracking positions were thrown away, the regex engine can only declare failure.

Possessive quantifiers and atomic grouping don’t just optimize regular expressions. They can alter the matches found by a regular expression by eliminating those that would be reached through backtracking.

This recipe shows how to use possessive quantifiers and atomic grouping to make minor optimizations, which may not even show any difference in benchmarks. The next recipe will showcase how atomic grouping can make a dramatic difference.

Recipe 2.12 shows the different alternation operators supported by regular expressions.

Recipe 2.15 explains how to make sure the regex engine doesn’t needlessly try different ways of matching a group.