Revisit regex engine for RegexFullMatch reference implementation (RE2 spec compliance)

Background

The ONNX spec for RegexFullMatch mandates that pattern follows RE2 syntax, which guarantees linear-time matching. That's still the documented requirement today:

• onnx/defs/text/defs.cc:40 — "[RE2] regex syntax is used."
• onnx/defs/text/defs.cc:46 — "This must be valid RE2 syntax."
• Same wording in the generated docs/Operators.md and docs/Changelog.md.

The reference implementation (onnx/reference/ops/op_regex_full_match.py) currently uses Python's stdlib re module instead, which is a backtracking engine with different performance characteristics than RE2's linear-time guarantee for some pattern shapes. This was a deliberate call in #7083: at the time, google-re2's Python bindings had no official Windows wheels, no Python 3.13 support, and weren't on conda-forge for Windows — real blockers for a project that has to build on Linux/macOS/Windows via both pip and pixi/conda.

Notably, the Python-3.13 wheel issue that #7083 pointed to (google/re2#516) was closed on 2025-07-28 — about four weeks after #7083 merged. It seems worth checking whether the ecosystem has moved further since and re-evaluating our options. Opening this for discussion rather than presupposing an answer.

Options surveyed

Option	Verdict
google-re2 (official bindings, published from google/re2's own python/ dir)	Verified directly against PyPI's file listing: the current release (1.1.20251105, uploaded 2025-11-05) ships win32/win_amd64/win_arm64 wheels for CPython 3.10–3.14, alongside macOS and manylinux wheels, on both PyPI and conda-forge. google/re2#516 (the Python 3.13 wheel issue) is closed. Most spec-faithful option (true RE2 syntax + guarantee), but needs to be re-validated in our own CI (pip + pixi, all three OSes) before we commit.
re2 (a different, unrelated PyPI package — easy to confuse with the above)	Last released Feb 2019, and its own docs say it silently falls back to Python's re for any pattern it can't handle — which quietly reintroduces backtracking behavior. Avoid; flagging mainly so nobody picks this by name confusion.
sarnold/google-re2 (small GitHub repo, 2 stars, 0 forks)	Same underlying bindings as the official package above (its own README says the source lives in a branch of google/re2), packaged under the same PyPI name. Last pushed 2022-07-10 — four years stale. A legacy/parallel distribution path, not a distinct alternative; no reason to prefer it over the actively-released upstream.
rure / rure-python (Rust regex crate bindings)	Correct algorithmic guarantee (finite-automata, linear-time — confirmed via the regex crate's own crates.io description). But rure's last PyPI release was 0.2.2 in October 2019, with wheels only for macOS and manylinux (Linux) — no Windows wheel was ever published.
regex-rust (PyPI, from spyoungtech/regexrs)	Actively pushed to as recently as 2026-05, but the README's own "Status" section says: "Mostly incomplete and likely very buggy. I am using this mostly as an exercise in creating and distributing Python extensions using Rust and PyO3... If you're looking for a complete and performant regex library for Python today, see the regex project on PyPI." Not production-ready by the maintainer's own account — and it points at the same regex package listed below.
regress (Rust regress crate bindings)	Actively maintained, excellent Windows wheel support (py3.10–3.14, MIT). But its own upstream README is explicit: "regress is a backtracking regular expression engine... It makes fewer guarantees than the regex crate but it enables more syntactic features, such as backreferences and lookaround assertions." No linear-time guarantee, and it implements ECMA-262 syntax rather than RE2. Doesn't actually solve the problem despite looking attractive on maintenance/platform grounds.
regex-rs (Rust regex crate bindings, circuitsacul/regex-rs)	Same right-algorithm/dead-packaging pattern as rure: last PyPI release 2023-07-08, repo last pushed 2024-01-08, 4 stars, and wheels stop at Python 3.12 — no 3.13/3.14.
real-regex (RECHE23/real-regex, C++20 engine)	Worth watching, not adopting yet. Claims linear-time matching with bounded lookarounds (RE2 and Rust regex both drop lookarounds to stay linear-time; this one keeps them), and is strict-by-default — rejects unsupported constructs with an error rather than silently falling back to backtracking (avoiding the trap the unrelated re2 package falls into). Has Windows wheels. But the repo was created 2026-06-13 — under a month old at the time of writing, one contributor, 1 star, 0 forks. Too new to bet a widely-used spec's reference implementation on regardless of how disciplined its engineering looks.
Keep re, add regex's (Matthew Barnett's module) native timeout=	regex is a near-drop-in superset of re with a built-in timeout parameter on match/fullmatch/search that raises an exception once exceeded — checked internally, not signal-based, so it works on Windows and in threads. Actively maintained (releases as recent as this month) with Windows wheels for 3.10–3.14. Doesn't give RE2's linear-time guarantee (still backtracking under the hood), but turns an unbounded hang into a bounded, catchable failure — solves the availability problem without a syntax-dialect change. Worth noting CPython itself is discussing adding the same timeout= to stdlib re, but that's an unmerged proposal, not available today.
Portable subprocess/worker timeout around stdlib re	No new dependency, but real per-call overhead if process-based; a thread-based version can't actually kill a runaway match, only stop waiting on it.
Static pattern vetting/blocklist before compiling	Cheap, but fragile — bypassable and prone to false positives on legitimate patterns using nested quantifiers. Not recommended as a standalone fix.
Keep re as-is, document the gap	Lowest engineering cost: explicitly document that ReferenceEvaluator isn't a hardened sandbox for arbitrary pattern values, rather than implying a spec-level guarantee we don't provide.

Constraints to keep in mind

• Must build/install cleanly on Linux, macOS, and Windows, via both pip and pixi/conda (per project norms).
• Prefer not to introduce a dependency with a track record of going unmaintained — we've been here once already with google-re2.
• Whatever we land on should keep the docs vendor/engine-neutral — the spec calls for RE2 syntax, not a specific implementation.

Opening this for discussion rather than a PR, since the right tradeoff depends on how much weight we want to put on strict spec conformance vs. dependency risk vs. implementation complexity.