TopolearnChoosing an engine with guarantees is the robust fix for untrusted patterns and huge inputs.
A regular expression without backreferences can be compiled into a finite automaton: states connected by character transitions.
- A Thompson NFA has a small number of states, one per pattern element. Instead of trying one path and backtracking, the matcher tracks the set of all states the automaton could be in, advancing them together for each input character. The cost is at most O(pattern size x input size), with no exponential blow-up.
- A DFA precomputes, for each set of NFA states, where every input byte leads. Matching is then one table lookup per byte, the fastest possible, but the number of DFA states can grow exponentially, so engines build them lazily and cap the cache (grep and RE2 do this).
What you lose: backreferences (they need memory of captured text) and, in RE2, Go and Rust, lookarounds. Capturing groups are possible with extra machinery (tagged NFAs, a one-pass or bounded-backtracking engine for small inputs), which is why sub-match extraction is slower than a yes/no test in those libraries.
Leftmost-first semantics like Perl's can be simulated by giving NFA threads priorities, which RE2 and Rust do, so most patterns behave identically apart from the missing features.
Use these engines when patterns or inputs are untrusted, or inputs are very large; use a backtracking engine when you genuinely need its extra features.
Example
// Go: regexp is RE2-based, linear time
package main
import (
"fmt"
"regexp"
"strings"
)
func main() {
evil := regexp.MustCompile(`^(\w+\s?)*$`) // exponential in backtracking engines
s := strings.Repeat("a", 50000) + "!"
fmt.Println(evil.MatchString(s)) // false, returns in milliseconds
_, err := regexp.Compile(`(\w)\1`)
fmt.Println(err) // error parsing regexp: invalid escape sequence: `\1`
re := regexp.MustCompile(`(?P<k>\w+)=(?P<v>\d+)`)
fmt.Println(re.FindStringSubmatch("x=42")) // [x=42 x 42]
}Remember
- NFA simulation tracks all possible states at once: linear time, no backtracking
- DFAs are faster but built lazily because they can blow up in size
- RE2, Go and Rust trade backreferences and lookarounds for guaranteed speed
Watch out for
- Porting a pattern with backreferences to Go and having it fail to compile at run time with MustCompile.