go-ruby-regexp — a pure-Go reimplementation of Onigmo, Ruby's regular-expression engine (backtracking VM, no cgo)

go-ruby-regexp is a pure-Go (no cgo) reimplementation of Onigmo, the regular-expression engine used by Ruby. Go's standard regexp is RE2 — linear-time but without backreferences or lookaround, and with different match semantics — so a byte-compatible Ruby regexp needs a backtracking engine. go-ruby-regexp is that engine: a faithful backtracking VM, hardened against catastrophic backtracking with memoization and a deterministic time/step budget. It is standalone and reusable, and is the regexp backend for go-embedded-ruby. The engine roadmap (Phases 0–4) is complete — backreferences, lookaround, possessive/atomic quantifiers, recursive subexpression calls, \p{…} and POSIX classes, rune-level /i folding, UTF-8 / ASCII-8BIT encodings, and a transparent optimizer prefilter — differential-tested against MRI, 100% coverage, CI green across 6 arches.

Phase 0 — Scanner, parser & VM ready

Onigmo syntax scanner + parser → AST, a bytecode compiler, and a backtracking VM: literals, classes, . * + ? {m,n}, groups, alternation, anchors, with captures.

Phase 1 — Groups & quantifier modes ready

Named groups (?<name>…), backreferences \1 / \k<name>, and every quantifier mode — greedy, lazy *? +? ??, possessive *+ ++ ?+, and atomic groups (?>…).

Phase 2 — Lookaround & calls ready

Lookahead (?=…) (?!…), fixed/bounded-width lookbehind (?<=…) (?<!…), the \G anchor, and recursive subexpression calls \g<name> / \g<0>.

Phase 3 — Unicode & encodings ready

Unicode properties \p{…}, POSIX bracket classes [[:alpha:]], \h / \H, \R, rune-level /i case folding, inline flags (?imx), and UTF-8 / ASCII-8BIT multi-encoding with multibyte class members [é] / [à-ï].

Phase 4 — ReDoS hardening & optimizer ready

(pc, sp) memoization, step budget, recursion cap and a wall-clock WithTimeout; a start-position / interior-literal prefilter (up to ~210× faster); a lazy-NFA + cached-DFA fast path that beats C Onigmo on literal/alternation/structured scans and pulls inner loops to ~1.6–5× of C (email ≈ RE2); a benchmark suite.

Phase 5 — Ruby surface planned

Downstream, not part of this engine module: the full Ruby Regexp / MatchData surface and replacement DSL live in the go-embedded-ruby adapter that consumes this engine.

ready phase complete (exit criteria met, nothing material left)
active in progress (substantial work shipped, phase not yet finished)
planned not started yet

A faithful backtracking VM in pure Go, cgo disabled, so it cross-compiles and embeds anywhere. It implements the Onigmo features RE2 omits — backreferences, lookaround, possessive quantifiers, atomic groups, named groups, subexpression calls — with Ruby's leftmost-first semantics, and is hardened against ReDoS with memoization and a deterministic budget (as Ruby ≥3.2). Validated differentially against Onigmo/MRI. It is a standalone, reusable module and the regexp backend for the sibling org github.com/go-embedded-ruby.