purere2 0.1.0

RE2 in pure Python: linear-time, ReDoS-safe regular expressions - no C extension, no backtracking

purere2

RE2 in pure Python: linear-time, ReDoS-safe regular expressions — no C extension, no backtracking.

Python's built-in re (like PCRE and Perl) backtracks, so a pattern like (a+)+$ against a non-matching string can run for years on a few dozen characters — the classic ReDoS denial-of-service. purere2 compiles every pattern to an NFA and runs it with a Pike VM, so matching is always linear in the input and no pattern can blow up. That guarantee is exactly why RE2 exists — and why it has no backreferences or lookaround.

pip install purere2

import purere2

# linear time: this returns instantly; re.search would hang for minutes
purere2.search(r"(a+)+$", "a" * 50 + "!")          # None, in microseconds

purere2.search(r"(\w+)@(\w+)", "x@y").groups()      # ('x', 'y')
purere2.findall(r"\d{4}-\d\d-\d\d", "2026-06-19")   # ['2026-06-19']

The API mirrors the common subset of the stdlib re module (compile, search, match, fullmatch, finditer, findall, sub, subn, split, flags I/M/S, named groups), so it is close to a drop-in replacement for running untrusted or LLM-generated patterns safely.

Why pure Python

google-re2 and pyre2 already wrap RE2 — but they need the RE2 C++ library (and a compiler, or a matching binary wheel). There was no pure Python RE2, even though RE2/J (Java) and RE2JS (JavaScript) have existed for years. purere2 is the missing one: zero dependencies, zero binaries, runs anywhere Python runs — Pyodide/WASM, AWS Lambda, locked-down sandboxes — exactly where you most want to run a pattern you don't trust.

The trade-off, stated honestly: on ordinary patterns purere2 is slower than the C-backed re (a pure-Python NFA can't beat a C engine). Its value is safety and portability, not raw speed — use it where a pattern is untrusted, or where a C extension isn't an option, not as a blanket re replacement.

Verified against the real RE2

Conformance is differential, the same way purefzf checks itself against the fzf binary: random RE2 patterns and inputs are run through both purere2 and google-re2 and compared byte-for-byte. Across 150,000+ random checks, agreement is ~99.996%; the residue is one documented edge (a lazy quantifier nested in a greedy loop) — see EXPECTED_DIVERGENCES.md. The conformance test locks that level, so any regression fails CI. There is also a ReDoS-safety suite of patterns that hang stdlib re and must finish in milliseconds here.

Supported syntax (v0.1)

Literals, ., character classes [...] with ranges / negation / POSIX [[:alpha:]], perl classes \d \w \s (ASCII, per RE2) and negations, anchors ^ $ \A \z \b \B, groups (...) / (?:...) / (?P<name>...), alternation |, quantifiers * + ? {m} {m,n} greedy and lazy, inline flags (?i) (?m) (?s) and scoped (?i:...), escapes including \xHH / \x{...}.

Intentionally absent (this is what makes it safe): backreferences and lookaround. (a)\1 raises RegexError. Deferred to a later version: Unicode property classes \p{...} and full Unicode case folding.

License

MIT