skip to content

How do possessive quantifiers and atomic groups prevent catastrophic backtracking in Java?

level: seniorimportance: should knowfreq 40%

answer

  1. possessive = greedy + never give back
  2. X++, X*+, X?+, X{m,n}+
  3. atomic group (?>...) discards internal backtracking
  4. a++ == (?>a+)
  5. can change matches — re-test legit inputs

basics

~20 s

Possessive quantifiers (a++, a*+) and atomic groups ((?>...)) tell the engine: match as much as you can and never give any of it back. Removing those give-back choice points stops the exponential re-trying that causes the blowup.

solid answer

~50 s

Catastrophic backtracking happens because greedy quantifiers leave choice points the engine can return to. Java supports two constructs that throw those choice points away. A possessive quantifier — `a++`, `a*+`, `a?+`, `a{m,n}+` — matches greedily and then refuses to backtrack into that match. An atomic group `(?>...)` does the same for a whole subexpression: once it matches, its internal backtracking state is discarded. The effect is that when a later part of the pattern fails, the engine cannot un-consume those characters to try a different split, so it fails immediately instead of exploring an exponential number of combinations. The trade-off is semantic: possessive/atomic matching can refuse matches that a greedy version would have found, because it won't give characters back. You must verify the pattern still accepts the strings it should. Used correctly, e.g. `(a+)+` rewritten as `(?>a+)+` or `a++`, it converts exponential worst-case time to linear.

code

java · 25 lines
java
import java.util.regex.Pattern;

class PossessiveDemo {
    // Catastrophic: nested greedy quantifiers, exponential on a failing tail.
    static final Pattern VULNERABLE = Pattern.compile("(a+)+$");

    // Fixed: possessive '++' freezes the inner match -> linear time, same accepts.
    static final Pattern SAFE = Pattern.compile("a++$");

    public static void main(String[] args) {
        String evil = "a".repeat(35) + "X"; // long matching prefix, then a breaker

        // VULNERABLE.matcher(evil).matches();  // would spin for a very long time

        long start = System.nanoTime();
        boolean matched = SAFE.matcher(evil).matches(); // returns ~instantly
        long ms = (System.nanoTime() - start) / 1_000_000;
        System.out.println("safe matched=" + matched + " in " + ms + "ms");

        // Caution: possessive can change semantics.
        // ".*+b" never matches "aab" because .*+ won't give the 'b' back.
        System.out.println(Pattern.matches(".*+b", "aab")); // false
        System.out.println(Pattern.matches(".*b",  "aab")); // true
    }
}

go deeper

for a junior

Recognizes that ++ and (?>...) are 'safe' regex constructs and would copy a known-good fixed pattern.

for a middle

Can apply possessive quantifiers to a flagged pattern and knows they 'don't give characters back', though may not yet predict semantic changes.

for a senior

Explains the choice-point mechanism, rewrites (a+)+ to a++/(?>a+)+, and verifies the rewrite preserves the intended accept/reject behavior.

for a principal

Knows the equivalence a++ == (?>a+), reasons about when possessive matching is provably safe (no overlap with what follows), and codifies safe-rewrite patterns plus tests into shared validation libraries.

## The root cause recap A **greedy quantifier** (`a+`, `a*`) grabs as many characters as it can, but keeps a record so it can **give characters back** (backtrack) if a later part of the pattern needs them. Each give-back is a **choice point**. Catastrophic backtracking is the engine exploring exponentially many combinations of these give-backs on a failing input. The fix family: **remove the give-back ability** where it isn't needed, so a failure can't spawn a retry. ## Possessive quantifiers Java (since 1.4) supports **possessive quantifiers** by appending `+` to a quantifier: - `X*+` — zero or more, possessive - `X++` — one or more, possessive - `X?+` — zero or one, possessive - `X{m,n}+` — bounded, possessive Semantics: match **greedily**, then **never backtrack** into this match. Once `a++` has consumed all the a's, it will *not* release any of them even if the rest of the pattern fails. The match either works with that maximal consumption or the whole thing fails — fast. Contrast the three flavors: - **Greedy** `a+` — take all, give back as needed. - **Lazy/reluctant** `a+?` — take as few as possible, take more as needed. (Lazy does NOT cure ReDoS; it just changes the search order and can still blow up.) - **Possessive** `a++` — take all, give back **nothing**. ## Atomic groups An **atomic (non-backtracking) group** is written `(?>...)`. Whatever it matches is **locked in**: once the group finishes, all backtracking positions *inside* it are discarded. It is the group-level equivalent of a possessive quantifier and lets you make a multi-token subexpression non-backtracking. In fact `a++` is equivalent to `(?>a+)`. ## Why this kills the blowup In `(a+)+` on `"aaaa...X"`, the exponential cost comes from re-dividing the run of a's between the inner `a+` and the outer `+`. If you write `(?>a+)+` or use `a++`, the inner consumption is frozen the first time, so there is exactly **one** division to try. When `X` fails, the engine has nowhere to backtrack to — it fails in linear time instead of exponential. ## The catch: semantics can change Possessive/atomic matching can make a pattern reject strings a greedy version would accept, precisely because it won't give characters back to satisfy a later token. Example: `".*+b"` against `"aab"` **fails**, because `.*+` swallows the whole string including the `b` and won't release it, so there's nothing left for `b`. The greedy `".*b"` would give the `b` back and match. So you can't blindly possessive-ify everything: you apply it where the quantified subexpression and what follows it **cannot overlap** (so giving back was never going to help anyway), which is exactly the ReDoS-prone case. Always re-run your accept/reject tests after the change. ## Practical rewriting recipe 1. Find nested/overlapping quantifiers: `(x+)+`, `(x*)*`, `(\s*\s*)`. 2. Make the inner repetition possessive or wrap it atomically: `(a+)+` → `(?:a++)` / `a++`; `(\s*)*` → `\s*+`. 3. Re-run the test suite of strings that SHOULD and SHOULD NOT match — confirm behavior is unchanged for legitimate inputs. 4. Re-test the previously catastrophic input to confirm it now fails fast. ## First-principles summary Backtracking needs give-back choice points. Possessive quantifiers (`X++`, `X*+`, …) and atomic groups (`(?>…)`) discard those choice points, so a later failure can't trigger re-exploration — exponential becomes linear. Apply them where backtracking couldn't have helped anyway, and always re-verify that legitimate strings still match.

  • Is a++ equivalent to any atomic-group form?
    Yes — a++ is exactly (?>a+). The possessive quantifier is shorthand for wrapping the greedy match in an atomic, non-backtracking group.
  • Does making a quantifier lazy (a+?) instead of greedy fix catastrophic backtracking?
    No. Lazy quantifiers only change the order in which alternatives are tried; the same exponential set of alternatives still exists, so a near-miss input can still blow up. Possessive/atomic actually removes the alternatives.

saying these in an interview costs you the question

  • Confusing possessive (X++) with lazy/reluctant (X+?) — lazy does NOT fix ReDoS
  • Assuming possessive quantifiers never change which strings match (they can)
  • Thinking atomic groups are a Java extension you can't use (Java supports (?>...))
  • Possessive-ifying every quantifier blindly and breaking legitimate matches

context

resolving links…