re2

RE2 is an efficient and principled regular expression library originally developed at Google in 2006. Its primary design goal is safety, ensuring that it can handle regular expressions from untrusted users without risk of catastrophic backtracking or denial-of-service attacks. Unlike traditional engines like PCRE, Perl, or Python's re module, RE2 guarantees that the match time is linear in the length of the input string. Key characteristics include: - **Safety**: RE2 avoids recursion and limits memory usage via a configurable budget, failing gracefully if exhausted. This prevents stack overflows and exponential runtime issues common in backtracking engines. - **Performance**: While not always faster than other engines on simple patterns due to parallel evaluation overhead, it provides consistent performance on complex expressions by evaluating alternatives in parallel rather than sequentially. - **Syntax Support**: In default Perl mode, it accepts most Perl operators but excludes those requiring backtracking (e.g., backreferences, look-around assertions). In POSIX mode, it supports standard POSIX (egrep) syntax with leftmost-longest matching. - **Unicode Handling**: RE2 operates on Unicode code points directly and does not perform normalization. Users must normalize input and patterns beforehand if needed. The library is implemented in C++ and requires a C++17 compiler and the Abseil library. It can be built using GNU make, CMake, or Bazel. Although native to C++, official wrappers exist for Python (`google-re2`), and community ports are available for Node.js, Java (RE2J), JavaScript (RE2JS), D, Erlang, OCaml, Perl, R, Ruby, and WebAssembly. Other languages like Go and Rust offer similar libraries following RE2's principles but do not share code with it.