Regex Engines, in depth: backtracking versus Thompson-style matching, a working Pike VM with captures, how RE2 and Rust regex compose strategies, and leaving ReDoS behind

Two families of engine

A backtracker is a depth-first search over choices. At a|b, x* or y? it picks the preferred branch, pushes the other on a stack, and continues; on failure it pops and resumes. The code is small and every feature is easy: backreferences just compare against the text an earlier group captured, lookaround runs a sub-match. The cost is that the number of paths can be exponential in the input length.

A Thompson-style engine is a breadth-first search. It keeps the set of NFA states that could be active after each input character and advances all of them together. Since the set has at most m states for a pattern of size m, the work is O(m times n) for n characters, whatever the pattern and input. The price is that features which need memory of what was matched, chiefly backreferences, cannot be expressed. Here is the difference in practice:

import re, time

for n in range(18, 25):
    t = time.perf_counter()
    re.fullmatch(r"(a+)+b", "a" * n)          # no 'b': every split of the a's is tried
    print(n, f"{time.perf_counter() - t:.3f}s")
# Each extra 'a' roughly doubles the time on a backtracking engine.

The nested quantifier gives the backtracker exponentially many ways to divide the a characters between inner and outer loops, and it must try all of them before concluding there is no b. The Pike VM below answers the same question for 30 characters in well under a millisecond.

The Pike VM: Thompson simulation with captures

Rob Pike's VM extends Thompson simulation with captures. Each thread is a program counter plus its own array of capture positions. Threads live in a list kept in priority order, and the seen set ensures that when two threads reach the same instruction at the same position, only the first, higher-priority one survives. That rule does two jobs: it bounds the list at the program size, which gives the linear-time guarantee, and it reproduces the leftmost-first choice a backtracker would make, because a backtracker would also explore the higher-priority thread first.

def parse(p):
    """Literals, '.', '|', '*', '+', '?' and capturing groups -> (tree, group count)."""
    pos, groups = 0, 0

    def alt():
        nonlocal pos
        left = cat()
        while pos < len(p) and p[pos] == "|":
            pos += 1
            left = ("alt", left, cat())
        return left

    def cat():
        items = []
        while pos < len(p) and p[pos] not in "|)":
            items.append(repeat())
        return ("cat", items)

    def repeat():
        nonlocal pos
        node = atom()
        while pos < len(p) and p[pos] in "*+?":
            node = ({"*": "star", "+": "plus", "?": "quest"}[p[pos]], node)
            pos += 1
        return node

    def atom():
        nonlocal pos, groups
        ch = p[pos]; pos += 1
        if ch == "(":
            groups += 1; g = groups
            inner = alt(); pos += 1          # consume ')'
            return ("group", g, inner)
        return ("any",) if ch == "." else ("char", ch)

    return alt(), groups


def compile_regex(pattern):
    """Thompson-style program. Instructions: char c | any | split x y | jmp x | save k | match."""
    tree, ngroups = parse(pattern)
    prog = []

    def emit(*ins):
        prog.append(list(ins))
        return len(prog) - 1

    def gen(n):
        kind = n[0]
        if kind in ("char", "any"):
            emit(*n)
        elif kind == "cat":
            for child in n[1]:
                gen(child)
        elif kind == "group":
            emit("save", 2 * n[1]); gen(n[2]); emit("save", 2 * n[1] + 1)
        elif kind == "alt":
            s = emit("split", len(prog) + 1, None); gen(n[1])
            j = emit("jmp", None); prog[s][2] = len(prog); gen(n[2]); prog[j][1] = len(prog)
        elif kind == "star":
            s = emit("split", len(prog) + 1, None); gen(n[1])
            emit("jmp", s); prog[s][2] = len(prog)
        elif kind == "plus":
            start = len(prog); gen(n[1]); emit("split", start, len(prog) + 1)
        elif kind == "quest":
            s = emit("split", len(prog) + 1, None); gen(n[1]); prog[s][2] = len(prog)

    emit("save", 0); gen(tree); emit("save", 1); emit("match")
    return prog, ngroups


def pike_fullmatch(prog, ngroups, text):
    """Anchored leftmost-first match with captures, O(len(prog) * len(text)) time."""
    def add(threads, seen, pc, caps, i):
        if pc in seen:
            return                       # a higher-priority thread already owns this pc
        seen.add(pc)
        op = prog[pc]
        if op[0] == "jmp":
            add(threads, seen, op[1], caps, i)
        elif op[0] == "split":
            add(threads, seen, op[1], caps, i)   # preferred branch first
            add(threads, seen, op[2], caps, i)
        elif op[0] == "save":
            caps = caps[:]; caps[op[1]] = i
            add(threads, seen, pc + 1, caps, i)
        else:
            threads.append((pc, caps))   # char, any or match: waits for input

    clist = []
    add(clist, set(), 0, [None] * (2 * ngroups + 2), 0)
    for i, ch in enumerate(text):
        nlist, seen = [], set()
        for pc, caps in clist:           # clist is kept in priority order
            op = prog[pc]
            if op[0] == "any" or (op[0] == "char" and op[1] == ch):
                add(nlist, seen, pc + 1, caps, i + 1)
        clist = nlist
    for pc, caps in clist:
        if prog[pc][0] == "match":
            return [(caps[2 * g], caps[2 * g + 1]) for g in range(ngroups + 1)]
    return None

The parser is plain recursive descent with no error handling, so feed it only valid patterns. Tested against Python re.fullmatch on 30,000 random pattern and input pairs over a, b, ., this VM agreed on every match decision and overall span.

Trace (a+)+b on aaa to see why it cannot blow up. The program is save 0, save 2, char a, split 2 4, save 3, split 1 6, char b, save 1, match: the inner + loops back to char a, the outer + loops back to save 2, and both loops end at the same char a instruction. After each a, the closure from the new position reaches char a along several paths (continue the inner loop, or close the group and reopen it), but the seen set admits only the first, so the list holds one thread waiting on char a and one waiting on char b. The list never grows with the input. A backtracker explores each of those paths separately and the count doubles per character. At the end of input no thread sits on match, so the answer is no match, after work proportional to three characters times the program size.

Real engines add unanchored search (seed a new lowest-priority thread at each position until a match is found), character classes, assertions such as word boundaries, and copy-on-write capture arrays so save does not allocate per thread.

Which match is correct: leftmost-first versus leftmost-longest

Engines also disagree on which match is correct. Perl-style engines, and the Pike VM above, use leftmost-first semantics: among matches starting at the leftmost position, take the one the preferred branches produce. POSIX specifies leftmost-longest: take the longest overall match, and resolve subgroups by further longest rules.

Run (a|ab)(c|bcd)(d*) on abcd. Both semantics match all four characters, but leftmost-first takes a for the first group, because it is the first alternative, then bcd and an empty third group. POSIX prefers the longest first group, ab, then c and d. A capture-and-replace rule ported from a POSIX tool such as sed -E to a Perl-style library can therefore extract different fields from the same line with no error. The one-liner a|ab on ab shows the overall difference: a under leftmost-first, ab under leftmost-longest.

Go offers a longest-match mode (CompilePOSIX and Longest), and RE2 has a similar option, but read the fine print: Go documents that among equally long leftmost matches it picks the one a backtracking search would find first, not the POSIX subexpression choice. So longest mode turns a|ab into ab yet still yields a, bcd and an empty group in the example above. Check what your engine documents before trusting a port.

Meta engines: how RE2 and Rust regex choose a strategy

No single algorithm is fastest for every pattern, so production linear-time engines are really meta-engines that pick per pattern and per search:

1. Prefilter. Extract literals every match must contain, such as ERROR in ERROR [0-9]+, and scan for them with memchr or a SIMD multi-substring search. Most of the text is skipped without touching an automaton. For many fixed strings at once, Aho-Corasick is the underlying tool.
2. Lazy DFA. A DFA does one table lookup per byte, but building it fully can take exponential space. A lazy DFA builds states on demand and caches them; RE2 and Rust regex fall back to NFA simulation if the cache is cleared too often. A forward scan finds where a match ends, a scan with the reversed pattern finds where it starts.
3. Capture engine on the found span. If the caller wants groups, run a one-pass DFA when the pattern is unambiguous enough, a bounded backtracker (which records visited state and position pairs in a bitset so it never repeats work) when the span is short, and the Pike VM otherwise.

RE2 names these stages DFA, OnePass, BitState and NFA; Rust's regex-automata crate exposes them as lazy DFA (hybrid), one-pass DFA, bounded backtracker and PikeVM under a meta regex. The design point is that users write one pattern and get near-DFA speed on common searches and linear worst-case time on all of them.

Features that force backtracking, and the mitigations

Two feature groups separate the families. Backreferences such as matching a repeated word are not regular; matching with them is NP-hard in general, so linear engines omit them. Lookaround is regular in principle but complicates automata, and RE2, Go and Rust regex leave it out. If a pattern needs either, do that part in code: match the regular part, then check the condition on the captured text.

Backtracking engines have grown mitigations rather than guarantees. Atomic groups and possessive quantifiers, available in PCRE and Java and added to Python re in 3.11, stop the engine backtracking into a sub-match, which fixes a pattern like (a+)+b when written (?>a+)+b. .NET 7 added a RegexOptions.NonBacktracking mode with a linear-time guarantee, and V8 has an experimental linear-time engine behind a flag. Where both engines are available, the linear one is the safe default for untrusted input.

Operating regexes in production

Regex denial of service (ReDoS) is an operational risk with a history: a single backtracking pattern in a WAF rule took down Cloudflare's network in July 2019 by pinning CPUs worldwide, and Stack Overflow had an outage in 2016 when a whitespace-trimming pattern met a post with a very long run of spaces. Both had patterns with overlapping quantifiers and inputs nobody had tested.

• Untrusted patterns or untrusted input: use a linear-time engine. This covers user-defined search filters, log routing rules and WAF rules.
• Must stay on a backtracker: set a match timeout where the platform provides one (.NET does), cap input length, and lint patterns for nested or overlapping quantifiers in CI.
• Migrating: inventory every pattern, flag those using backreferences or lookaround, then run old and new engines side by side on production traffic in shadow mode, comparing match decisions and capture spans. Differences are usually leftmost-first versus leftmost-longest, Unicode class definitions, or how . treats newlines.
• Measure compile cost. Linear engines spend more at compile time; compile once and cache, and bound the DFA cache memory per regex.

Trade-offs

Failure modes

• Nested quantifiers on a backtracker. (a+)+, (a|a)*, (.*,)*: exponential on a near-miss input.
• Silent semantic drift. A port between leftmost-first and leftmost-longest engines changes captured fields without an error.
• Testing only matching inputs. Catastrophic cases are inputs that almost match; fuzz with near-misses.
• Compiling per call. Linear engines compile slowly; recompiling in a hot loop wipes out their advantage.
• Unbounded DFA memory. Many patterns times large caches; set the cache limit and watch for fallback to the slower NFA path.

What to do next

1. Run the timing snippet against your own language runtime to see which family it uses.
2. Grep your codebase and configuration for patterns applied to untrusted input; move them to a linear engine or add timeouts and length caps.
3. Add a CI lint for nested and overlapping quantifiers.
4. Implement the Pike VM above, add unanchored search, and test it against your standard library with random patterns.
5. Before any migration, run both engines in shadow and diff match spans and groups.
6. Read the string matching article to see the substring searches that prefilters use.