Skip to content

What a backreference costs

One line: A backreference takes the pattern outside what a finite automaton can represent, so an engine that offers one must backtrack — and backtracking has no upper bound you can reason about from the pattern's size.

Level: 301 · you are choosing an engine, or you have a request timing out

Keywords on this page: \1 · (?>…) · *+ · * + ? — Topics: Performance · Choosing an engine

This is the lesson behind every "why doesn't Go/Rust support backreferences?" question. The answer is not that nobody implemented it.

The theory, in three sentences

A classical regular expression describes a regular language, and every regular language can be recognised by a finite automaton: one pass over the subject, no memory beyond the current state, time proportional to the subject's length.

(\w+) \1 is not a regular language. Recognising it needs the engine to remember arbitrary text and compare it later, which is exactly what a finite automaton cannot do.

So an engine with backreferences has to search: try an alternative, and on failure go back and try another. Deciding whether a pattern with backreferences matches is NP-complete in general — a result from Aho's chapter on pattern matching — and in everyday terms that means a pattern a few characters long can take longer than the age of the universe on a subject of forty characters.

The measurement

^(a+)+$ is the classic demonstration. The nesting gives a backtracker exponentially many ways to split a run of as between the inner and outer repetitions, and a subject that fails — one ! at the end — forces it to try all of them.

Go's RE2 does not care

Verified output of backtracking_go.go — regenerated by tools/run_examples.py, never hand-typed.

match = false over 5001 characters
finished in under 100ms: true
with a backreference: error parsing regexp: invalid escape sequence: `\1`

Five thousand characters, answered immediately, because the automaton has no choices to regret. The second line of that output is the price: hand RE2 a backreference and it refuses to compile the pattern at all.

Rust, where you can see both sides

Verified output of backtracking_rs_sh.sh — regenerated by tools/run_examples.py, never hand-typed.

regex:       ^(a+)+$          -> false (one pass, always)
fancy-regex: ^(a+)+$          -> Ok(false) (delegated to regex)
fancy-regex: ^(a+)+\1$        -> Error executing regex: Max limit for backtracking count exceeded

Three results in three lines, and the middle one is the subtle part:

  • regex answers ^(a+)+$ in one pass. Its guarantee is structural, not a matter of how clever the pattern looks.
  • fancy-regex gives the same answer, just as fast, because a pattern with no backreference and no lookaround is handed straight to regex. You pay for the backtracker only when you use it.
  • Add \1 and there is nothing to delegate. The whole match must be backtracked, the search explodes, and fancy-regex stops itself: Max limit for backtracking count exceeded.

That last line is the shape of a good failure. The engine counts its steps and gives up with an error you can catch, rather than holding a thread for an hour.

What the other engines do instead

Engine On a catastrophic pattern
Go regexp, Rust regex Cannot happen — the feature that causes it does not exist.
Rust fancy-regex Backtrack limit, returned as Err.
PCRE2 (so ABAP's PCRE) A match limit and a depth limit; the call returns an error rather than hanging.
Perl Runs. Some patterns are optimised away, many are not.
Python re Runs. Since 3.11, atomic groups and possessive quantifiers let you cut the search.
Java Runs. Pattern has no built-in limit, which is why ReDoS advisories so often name Java services.
JavaScript Runs, on the thread that serves your users.

"Runs" is the dangerous cell. A pattern that is fine on your test data and exponential on one hostile input is a denial-of-service vulnerability with a name — ReDoS — and it is reached by a text field, not a shell.

How to not get bitten

  1. Prefer an engine with a guarantee for anything that touches untrusted input. In Rust that means reaching for fancy-regex deliberately, not by default. In Go the choice was made for you.
  2. Anchor, and make alternatives mutually exclusive. Most catastrophic patterns contain a nested quantifier over something that can match the same text two ways — (a+)+, (a|a)*, (\s*|\t)+.
  3. Use an atomic group or a possessive quantifier where the engine has them: (?>a+)+ and a++ both tell the engine "having matched this, never give it back". Python has had both since 3.11; Perl, PCRE2, Java and Ruby have had them for years; JavaScript has neither. Read what they do to the match before reaching for one — the change is not only to the speed.
  4. Set a limit if the engine offers one, and treat hitting it as a bug report about the pattern.
  5. Do the comparison in the host language. The Go example in what a backreference is matches two groups and compares them in Go — never exponential, and obvious to read.

Try it

  1. Run ^(a+)+$ against "a" * n + "!" in Python for n = 20, 22, 24, timing each. The jump from "instant" to "I should stop this" is usually between 22 and 30, on any machine.
  2. Now add one character: ^(?>a+)+$. Time it again.
  3. Ask your engine for ^(a+)+\1$ and find out whether you get an error, an answer, or a hung process.

See also