purere2 0.1.2

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.

Speed, stated honestly. purere2 compiles each pattern to a lazy DFA (built on the fly, like RE2's own) so that for a plain recognizer — no capture groups, no ^ $ \b — every character is a memoized table lookup. On common patterns this makes it competitive with, and often faster than, the C-backed google-re2 binding, because purere2 stays in-process while the binding pays Python↔C overhead on every call. It is still slower than the stdlib re (a C engine with no FFI cost) on patterns re can handle. Capture groups and assertions fall back to a Pike VM, which is slower but always linear.

Measured on a 124 KB corpus (python tools/bench.py); your numbers will vary:

pattern	purere2	stdlib re	google-re2
\w+ (findall)	31 ms	2.4 ms	43 ms
[a-z_]+[0-9]*	25 ms	1.6 ms	31 ms
alpha|bravo|…	14 ms	0.7 ms	9 ms
(\w+)@(\w+)\.(\w+)	74 ms	3.8 ms	6 ms

The point is not to beat re — it can't. The point is safety and portability: run an untrusted or LLM-generated pattern with a guaranteed linear-time bound, anywhere Python runs, with no C extension.

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