A pure-Ruby regular expression engine called exreg uses a Thompson-style NFA virtual machine to prevent ReDoS attacks caused by catastrophic backtracking. Unlike traditional backtracking engines like Onigmo, it simulates all possible paths in parallel, ensuring linear execution time. The implementation includes a parser, compiler, and VM with custom binary formats for Unicode support, specialized data structures like USet and ByteSet for efficient codepoint handling, and simplified encoding that treats strings as UTF-8 byte arrays. Future enhancements could include JIT compilation and backtracking support for advanced features.
Sort: