RE2 (software)

RE2 is a software library designed for regular expression matching. Developed by Google, it is notable for its guaranteed linear time complexity in relation to the size of the input string, a characteristic achieved by avoiding backtracking. This distinguishes it from many other popular regular expression engines, which can exhibit exponential time complexity in certain pathological cases, leading to denial-of-service vulnerabilities (ReDoS).

RE2’s linear time guarantee comes at the cost of supporting a somewhat limited set of regular expression features compared to more traditional, backtracking-based engines like PCRE. Specifically, it does not support backreferences or lookbehind assertions. This trade-off prioritizes security and predictable performance over maximal feature completeness.

The library is implemented in C++ and is available as open-source software under the BSD license. Bindings are available for other programming languages, allowing developers to integrate RE2 into a wider range of applications. Its primary use cases involve scenarios where processing untrusted regular expressions is a concern, or where predictable performance is critical for regular expression matching operations.