This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
RE2 is a software library which implements a regular expression engine via finite-state machines using automata theory, in contrast to almost all other regular expression libraries, which use backtracking implementations. It provides a C++ interface.
| Original author(s) | |
|---|---|
| Initial release | March 11, 2010[1] |
| Stable release | 2021-04-01
/ April 1, 2021[2] |
| Repository | |
| Written in | C++ |
| Operating system | Cross-platform |
| Type | Pattern matching library |
| License | BSD |
| Website | github |
RE2 was implemented and used by Google. The library uses an "on-the-fly" deterministic finite-state automaton algorithm based on Ken Thompson's Plan 9 grep.[3]
Comparison to PCRE
editRE2 generally compares to Perl Compatible Regular Expressions (PCRE) in performance. For certain regular expression operators like | (the operator for alternation or logical disjunction) it exceeds PCRE. On the other hand, unlike PCRE which supports features such as backreferences, RE2 is only able to recognize regular languages due to its construction using the Thompson DFA[3] algorithm. It is also slightly slower than PCRE for parenthetic capturing operations.
PCRE can use a large recursive stack with corresponding high memory usage and result in exponential runtime on certain patterns. In contrast, RE2 uses a fixed stack size and guarantees that its runtime increases linearly (not exponentially) with the size of the input. The maximum memory allocated with RE2 is configurable.
RE2 has a slightly smaller set of features than PCRE, but has very predictable run-time and a maximum memory allotment. This can make it more suitable for use in server applications, which require boundaries on memory usage and computational time. PCRE, on the other hand supports more features such as lookarounds, backreferences and recursion, but has unpredictable runtime and memory usage which can grow unbounded.
Adoption
editUse in Google products
editRE2 is used by Google products like Gmail, Google Documents and Google Sheets.[4] See GitHub for a documentation of the syntax: RE2 syntax.
In Google Sheets, it is used in the functions RegexMatch(), RegexReplace(), RegexExtract() and the find and replace feature. RegexExtract(), does not use grouping.
The built-in "regexp" package uses the same patterns and implementation as RE2, though it is written in Go.[5] This is unsurprising, given Go's background from Google and common staff from the Plan 9 team.
Related libraries
editThe RE2 algorithm has been rewritten in Rust as the package "regex". CloudFlare's web application firewall uses this package because the RE2 algorithm is immune to ReDoS.[6]
Russ Cox also wrote RE1, an earlier regular expression based on a bytecode interpreter.[7] OpenResty uses a RE1 fork called "sregex".[8]
See also
editReferences
edit- ^ Cox, Russ (March 11, 2010). "RE2: a principled approach to regular expression matching". Google Open Source Blog. Retrieved 2020-05-29.
- ^ "Releases". Github. Retrieved 2021-05-03.
- ^ a b Cox, Russ. "Regular Expression Matching in the Wild". swtch.com.
- ^ "Search and use find and replace". Retrieved 24 March 2020.
- ^ "regexp package - regexp - Go Packages". Retrieved 8 Nov 2024.
- ^ "Making the WAF 40% faster". The Cloudflare Blog. 1 July 2020.
- ^ "Regular Expression Matching: the Virtual Machine Approach". swtch.com.
- ^ "openresty/sregex: A non-backtracking NFA/DFA-based Perl-compatible regex engine matching on large data streams". OpenResty. 6 February 2024.