An optimizing compiler for JavaScript regular expressions

Modern regex languages have evolved significantly from traditional regular expressions, incorporating features that complicate the matching process. Many modern regex engines, including JavaScript’s, use a backtracking algorithm that can exhibit exponential complexity, leading to vulnerabilities such as Regular Expression Denial of Service (ReDoS) attacks. While some approaches demonstrate that a large subset of these regex patterns can be executed in linear time, existing linear-time engines for JavaScript are generally two orders of magnitude slower on average compared to their backtracking counterparts. This performance gap hinders widespread adoption, highlighting the need for fasteron average solutions. This report introduces Rawr, an optimizing compiler that translates a subset of JavaScript’s regular expressions into WebAssembly (Wasm). The resulting Wasm code executes in linear time and outperforms the current linear engine of V8.