Linear-time regular expression matching

Deep dive

How it works

Parts:

• Parser — pattern to a syntax tree; rejects backreferences and look-around.
• Compiler — tree to a small NFA program: Char, Any, Split(a,b) (both branches live), Jmp, Match (Thompson 1968; Cox's virtual-machine form).
• State-set simulator (Pike VM) — set of live program counters, one step per byte; per-thread capture slots give captures.
• Lazy DFA — memo table (state set, byte) to next state set, built during search, bounded cache.
• Prefilter — required literal found by SIMD search or Aho-Corasick before any automaton runs.

1. Parse and compile once to O(m) instructions.
2. Closure: from a counter follow Jmp and Split to the Char/Any/Match instructions; mark each counter once per step, so the set stays within m.
3. Step: for each live Char c or Any that accepts the byte, add the closure of pc + 1 to the next set.
4. Search: add the closure of instruction 0 at every offset; full match: at offset 0 only.
5. Accept when Match is live (full match: only at the end).
6. Lazy DFA: key the set by its sorted counters; on a cache miss do steps 2-3 once and store the result. Later visits cost one table load.
7. Cache full: clear it and rebuild from the current state; if clears are too frequent, drop the DFA and use the step-3 simulation.
8. Captures: find the span with the DFA, then run the state-set engine on the span only.

a(b|c)*d  ->  0 Char a      4 Jmp 6         set after "a": closure(1) = {3:b, 5:c, 7:d}
              1 Split 2,7   5 Char c        set after "ab": closure(4) = {3:b, 5:c, 7:d}
              2 Split 3,5   6 Jmp 1         same set -> one DFA state, reused
              3 Char b      7 Char d  8 Match

Code

Parser for literals, ., |, *, +, ? and groups; NFA compiler; state-set and backtracking matchers; the test checks they agree on 40,000 random pattern/text pairs, full match and search.

use Inst::*;
pub enum Inst { Char(u8), Any, Split(usize, usize), Jmp(usize), Match }
enum Ast { Lit(u8), Any, Cat(Vec<Ast>), Alt(Box<Ast>, Box<Ast>), Rep(Box<Ast>, u8) }
// alt := cat ('|' cat)* ; cat := (atom [*+?]*)+ ; atom := byte | '.' | '(' alt ')'
fn alt(s: &[u8], i: &mut usize) -> Option<Ast> {
    let mut l = cat(s, i)?;
    while s.get(*i) == Some(&b'|') { *i += 1; l = Ast::Alt(Box::new(l), Box::new(cat(s, i)?)); }
    Some(l)
}
fn cat(s: &[u8], i: &mut usize) -> Option<Ast> {
    let mut v = vec![];
    while let Some(&c) = s.get(*i) {
        if c == b'|' || c == b')' { break; }
        *i += 1;
        let mut a = match c {
            b'(' => { let a = alt(s, i)?; if s.get(*i) != Some(&b')') { return None; } *i += 1; a }
            b'*' | b'+' | b'?' => return None,
            b'.' => Ast::Any,
            _ => Ast::Lit(c),
        };
        while let Some(&q @ (b'*' | b'+' | b'?')) = s.get(*i) { *i += 1; a = Ast::Rep(Box::new(a), q); }
        v.push(a);
    }
    if v.is_empty() { None } else { Some(Ast::Cat(v)) }
}
fn emit(a: &Ast, p: &mut Vec<Inst>) {
    match a {
        Ast::Lit(c) => p.push(Char(*c)),
        Ast::Any => p.push(Any),
        Ast::Cat(v) => v.iter().for_each(|x| emit(x, p)),
        Ast::Alt(x, y) => { // L: split L+1, M+1 ; x ; M: jmp end ; y
            let l = p.len(); p.push(Split(0, 0)); emit(x, p);
            let m = p.len(); p.push(Jmp(0)); emit(y, p);
            p[l] = Split(l + 1, m + 1); p[m] = Jmp(p.len());
        }
        Ast::Rep(x, b'+') => { let l = p.len(); emit(x, p); p.push(Split(l, p.len() + 1)); }
        Ast::Rep(x, op) => { // L: split L+1, end ; x ; (star only: jmp L)
            let l = p.len(); p.push(Split(0, 0)); emit(x, p);
            if *op == b'*' { p.push(Jmp(l)); }
            p[l] = Split(l + 1, p.len());
        }
    }
}
pub fn compile(re: &str) -> Option<Vec<Inst>> {
    let (s, mut i, mut p) = (re.as_bytes(), 0, vec![]);
    emit(&alt(s, &mut i)?, &mut p); p.push(Match);
    if i == s.len() { Some(p) } else { None } // stray ')' left over
}
/// State-set simulation, O(|p|*|s|).
pub fn pike(p: &[Inst], s: &[u8], full: bool) -> bool {
    let mut mark = vec![usize::MAX; p.len()]; // mark[pc] == step: already in this step's set
    let (mut cur, mut next) = (vec![], vec![]);
    fn add(p: &[Inst], mark: &mut [usize], set: &mut Vec<usize>, step: usize, pc: usize) {
        let mut stack = vec![pc]; // follow Jmp/Split; keep Char/Any/Match
        while let Some(pc) = stack.pop() {
            if mark[pc] == step { continue; }
            mark[pc] = step;
            match p[pc] { Jmp(t) => stack.push(t), Split(a, b) => stack.extend([b, a]), _ => set.push(pc) }
        }
    }
    for i in 0..=s.len() {
        if !full || i == 0 { add(p, &mut mark, &mut cur, i, 0); } // search: start anywhere
        if cur.iter().any(|&pc| matches!(p[pc], Match)) && (!full || i == s.len()) { return true; }
        if i == s.len() { return false; }
        next.clear();
        for &pc in &cur {
            if matches!(p[pc], Any) || matches!(p[pc], Char(c) if c == s[i]) { add(p, &mut mark, &mut next, i + 1, pc + 1); }
        }
        std::mem::swap(&mut cur, &mut next);
    }
    unreachable!()
}
/// Backtracking: exponential in the worst case.
pub fn backtrack(p: &[Inst], s: &[u8], full: bool) -> bool {
    fn go(p: &[Inst], s: &[u8], mut pc: usize, mut i: usize, seen: &mut [usize], full: bool) -> bool {
        loop {
            match p[pc] {
                Char(c) if i < s.len() && s[i] == c => { pc += 1; i += 1; }
                Any if i < s.len() => { pc += 1; i += 1; }
                Char(_) | Any => return false,
                Jmp(t) => pc = t,
                Match => return !full || i == s.len(),
                Split(a, b) => {
                    if seen[pc] == i { return false; } // empty loop
                    let old = std::mem::replace(&mut seen[pc], i);
                    let r = go(p, s, a, i, seen, full) || go(p, s, b, i, seen, full);
                    seen[pc] = old;
                    return r;
                }
            }
        }
    }
    (0..=if full { 0 } else { s.len() }).any(|st| go(p, s, 0, st, &mut vec![usize::MAX; p.len()], full))
}
#[test]
fn engines_agree() {
    fn rnd(r: &mut u64) -> u32 { *r ^= *r << 13; *r ^= *r >> 7; *r ^= *r << 17; (*r >> 33) as u32 }
    fn gen(r: &mut u64, d: u32) -> String {
        match if d == 0 { rnd(r) % 3 } else { rnd(r) % 8 } {
            0 => "a".into(), 1 => "b".into(), 2 => ".".into(),
            3 | 4 => gen(r, d - 1) + &gen(r, d - 1),
            5 => format!("({}|{})", gen(r, d - 1), gen(r, d - 1)),
            _ => format!("({}){}", gen(r, d - 1), ["*", "+", "?"][rnd(r) as usize % 3]),
        }
    }
    let mut r = 0x9E3779B97F4A7C15u64;
    for _ in 0..5000 {
        let re = gen(&mut r, 4);
        let p = compile(&re).unwrap();
        for _ in 0..8 {
            let s: Vec<u8> = (0..rnd(&mut r) % 7).map(|_| b"ab"[rnd(&mut r) as usize % 2]).collect();
            for full in [true, false] { assert_eq!(pike(&p, &s, full), backtrack(&p, &s, full), "{re} {s:?}"); }
        }
    }
    let p = compile("a(b|c)*d").unwrap();
    assert!(pike(&p, b"xabcbd", false) && !pike(&p, b"xabcbd", true));
    assert!(compile("a|").is_none() && compile("(a").is_none() && compile("*a").is_none());
}

Complexity and constants

• Compile O(m); simulation O(m·n) time, O(m) space. Backtracking is exponential, not bounded by m·n.
• Measured on this Mac (Apple M4 Pro, rustc 1.99.1 --release, single thread, load average about 4, one run each), full match of a?ⁿaⁿ against aⁿ with the code above:

• The fixed pattern (a|aa)*b against aⁿ: backtracking 0.27 ms at n=20, 578 ms at n=36; state set 92 µs for 10³ bytes, 87 ms for 10⁶ (linear, about 87 ns/byte). Cox's article reports Perl needing over sixty seconds at n=29.
• A lazy-DFA step is a table load; each new state costs an NFA step, so it wins when states repeat.

Efficiency

• Cost: this code, 9-instruction NFA, M4 Pro: about 87 ns per byte, unoptimised (allocates a stack per closure); bound: set bookkeeping. RE2's source comment puts building a DFA state on every byte at about 0.2 MB/s against about 2 MB/s for its NFA (old, order of).
• Levers:
  • lazy DFA over NFA simulation — at most one state built per byte searched (regex-automata docs) — no captures or Unicode word boundaries in this pass
  • literal prefilter or pure-literal bypass — a literal or small literal set may need no automaton (regex-automata docs) — patterns with a required literal
  • captures only on the match span (regex-automata docs) — when groups are requested
  • cache size — a cache that is too small is reset often and slows search (regex-automata docs) — large Unicode classes
  • memory budget — RE2 limits memory and fails gracefully (RE2 README) — untrusted patterns
• Naive → standard → state of the art:
  • backtracking · exponential worst case
  • state-set simulation · O(m·n), about 87 ns/byte here
  • prefilter + lazy DFA + NFA fallback · O(n) once cached; Hyperscan for large pattern sets

Implementation notes

• Cache fallback. RE2 resets a full state cache and, if it computed a state for fewer than about every 10 bytes, fails the DFA so the NFA takes over (re2/dfa.cc; RE2::Set cannot fall back). regex-automata resets the cache and can be configured to give up after a minimum number of clears.
• Empty loops. (a*)*: per-step marking stops them; a backtracker needs the seen guard.

Pitfalls

• Backtracking engine on attacker-supplied input: Cloudflare's 2 July 2019 outage (27 minutes) came from one WAF rule whose pattern backtracked enormously and exhausted CPU (post-mortem).
• Full DFA compile: exponential in time and memory in the worst case; compile lazily or cap states.
• One lazy-DFA cache shared by threads: it is mutable scratch space, keep one per thread.
• Unicode word boundaries and large Unicode classes defeat or bloat the DFA path.

Variants and alternatives

In production

ripgrep (Rust regex); RE2; Go regexp; Hyperscan/Vectorscan in packet inspection signature sets.

Implementations

Sources

• K. Thompson, Regular expression search algorithm, Communications of the ACM 11(6), 1968, pp. 419-422. paper
• R. Cox, Regular Expression Matching Can Be Simple And Fast. article · Regular Expression Matching: the Virtual Machine Approach. article · Regular Expression Matching in the Wild. article · Regular Expression Matching with a Trigram Index. article
• regex-automata docs (hybrid, meta). docs · code; RE2 README and re2/dfa.cc. code
• X. Wang et al., Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs, NSDI 2019. paper
• J. Graham-Cumming, Details of the Cloudflare outage on July 2, 2019. post
• J. C. Davis, C. A. Coghlan, F. Servant, D. Lee, The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale, ESEC/FSE 2018, pp. 246-256. paper
• PCRE2 pcre2matching docs; Go regexp docs