Rejit: A Pure-Python Regex Engine Immune to ReDoS

Rejit is a from-scratch regex engine written in pure Python that guarantees linear-time matching, making catastrophic backtracking (ReDoS) structurally impossible. Instead of the backtracking approach used by Python's re module, it compiles patterns into a small bytecode program and simulates the resulting NFA breadth-first as a Pike VM, visiting each state at most once per input position. On the classic pathological pattern (a+)+$, re's runtime explodes exponentially while rejit stays flat at a few hundred milliseconds even on 40,000-character inputs.

Correctness is validated against Python's own re module as an oracle: a fuzzer generates tens of thousands of random patterns and strings and checks agreement on fullmatch, search, span/captures, and finditer semantics, with zero failures across more than 90,000 cases. Patterns that make re itself hang are excluded from oracle comparison and covered instead by deterministic linear-time tests.

The trade-off is expressiveness: rejit supports only regular-language constructs (no backreferences, no lookaround, no named groups or inline flags) and uses ASCII-only class semantics equivalent to re.ASCII. It targets Python 3.10+, has zero dependencies, and is MIT licensed — a practical reference for engineers who need to handle untrusted regex input safely.