RE2 (Regex Engine)

"RE2" is a regular expression library originally written in C++ at Google by Russ Cox and released as open source in 2010. Its design goal is a guaranteed performance bound: matching time is linear in the size of the input, with no possibility of Catastrophic Backtracking. RE2 achieves this by compiling patterns to a nondeterministic finite automaton and then simulating it as a deterministic finite automaton on the fly, an approach descended from Ken Thompson's 1968 Plan 9 grep implementation. The price is feature loss: RE2 does not support backreferences or arbitrary lookaround, because those constructs cannot be expressed in finite automata. Russ Cox ported the same approach to Go's standard regexp package, which shares no code with the C++ RE2 but follows the same syntax and the same linear-time guarantee. Rust's regex crate is built on the same family of ideas. Together these libraries are the canonical "safe by construction" regex stacks: they trade away a few edge-case features in exchange for predictable behavior on adversarial input. RE2's most visible production use is at Cloudflare, which adopted it for its web application firewall after the Cloudflare 2019 Outage showed that a PCRE-style rule with ambiguous quantifiers could take down the entire edge network. Other large deployments include Google's internal search and code infrastructure and a number of language-binding ports such as re2-python. For workloads where untrusted users can submit patterns or where match latency must be bounded, RE2 and its descendants have become the default recommendation.