Regexp (Onigmo)

Ruby's regular expression engine is Onigmo — a fork of the Oniguruma library, vendored in this repo as regcomp.c/regexec.c/regparse.c/regenc.c and friends. It's a Perl-compatible NFA backtracker with explicit support for Ruby's M17N encodings.

Purpose

• Compile Regexp objects from source patterns.
• Match patterns against Strings while respecting their encoding.
• Provide MatchData with named groups, captures, and pre/post strings.
• Support every Ruby regex feature: lookahead, lookbehind, character classes, named captures, backreferences, atomic groups, possessive quantifiers, \K, \g, conditional patterns.

Files

File	Purpose
regcomp.c	Compiles a parsed regex into an internal bytecode. ~167 KB.
regexec.c	Runs the bytecode against an input. ~152 KB.
regparse.c	Parses regex source into a tree. ~173 KB.
regparse.h	Parser AST and helpers.
regenc.c	Generic encoding helpers used by the engine.
regenc.h	Encoding interface for the engine.
regerror.c	Error message formatting.
regsyntax.c	The regex syntax/dialect tables (Ruby, Perl, GNU, POSIX).
regint.h	Internal types and macros (~34 KB header).
re.c	Ruby-level Regexp and MatchData classes. ~137 KB.
enc/<name>.c	Per-encoding character classification tables consumed by the engine.

Architecture

graph LR
    src["/.../ pattern"] -->|regparse| ast[Regex AST]
    ast -->|regcomp| ops["Onigmo bytecode\n(opcode + operand stream)"]
    ops -->|regexec| match["Match against String\n+ encoding"]
    match --> result["OnigRegion → rb_match_t → MatchData"]

Parse

regparse.c::onig_parse_make_tree consumes the pattern source byte-by-byte, dispatching on metacharacters and producing a tree of Nodes (alternation, repetition, group, character class, anchor, backref, etc.). Encoding-aware character class decoding (e.g., \p{Hiragana}) consults the tables from enc/<name>.c.

Compile

regcomp.c::onig_compile walks the AST and emits a packed bytecode (OnigOpType enum in regint.h). Sample opcodes:

• OP_ANYCHAR_STAR — greedy .*
• OP_PUSH — set up an alternative
• OP_REPEAT — repetition with min/max
• OP_BACKREF1 to OP_BACKREF_MULTI — backreferences
• OP_LOOK_BEHIND — lookbehind
• OP_FAIL — backtrack

The compiler also computes:

• The anchor map (start anchor, end anchor, line anchor, etc.).
• The must-match byte set: characters that must appear in any match. Used by the optimiser to fail fast on impossible inputs.
• The prefix if the regex starts with a literal — accelerates Boyer-Moore-like skip.

Execute

regexec.c::onig_match runs the bytecode against the input. The engine is an NFA backtracker:

• A stack of choice points (STK_REPEAT, STK_ALT, STK_LOOK_BEHIND, ...).
• A linear bytecode pointer that advances on match.
• On OP_FAIL, pop the most recent choice point and rewind.

To prevent runaway backtracking on adversarial patterns, the engine has:

• A search limit (env var: RUBY_RE_TIMEOUT from Ruby 3.2+) that aborts a match after a timeout.
• Inline caching of repetition counts to detect catastrophic backtracking earlier.

Encoding awareness

Every Regexp is constructed with an Encoding:

/abc/u   # UTF-8
/abc/n   # ASCII-8BIT
/abc/s   # Windows-31J
/abc/e   # EUC-JP
/abc/    # depends on source file encoding (UTF-8 by default)

Compilation builds character class bitmaps using the encoding's UCD tables. Execution decodes the input using the encoding's mbc_to_code callback. Mismatched encodings raise Encoding::CompatibilityError at match time.

Ruby-level surface

re.c wraps the engine for Ruby:

• Regexp.new(src, opts) → calls onig_compile.
• Regexp#match(str) → calls onig_search and wraps the resulting region as MatchData.
• String#=~, String#scan, String#sub, String#gsub, String#split — all route to the engine.
• Regexp.last_match, $~, $1...$9, $&, $``, $'— pseudo-globals backed byMatchData`.

In Ruby 4.x, all Regexp instances are frozen by default (see NEWS.md). Subclasses of Regexp remain mutable for backward compatibility.

Timeout protection

Regexp.timeout = 1.0  # seconds
"a" * 30000 =~ /(a+)+b/  # would otherwise hang
# raises Regexp::TimeoutError after 1s

re.c::rb_reg_timeout_p checks the deadline at every backtrack. The default is nil (no timeout); set globally via Regexp.timeout= or per-instance via Regexp.new(src, timeout: 1.0).

Optimisations

• Boyer-Moore prefix search for patterns with a literal prefix.
• Memoization of repetition states to detect duplicate work.
• Fast paths for common ASCII patterns that bypass full encoding decode.
• Cache of compiled regexes inside literals (each /foo/ literal compiles once per source location).

Origin and divergence

Onigmo (Onigmo ≈ Oniguruma + "Mo" for Mathematics or extra power) forked from Oniguruma around 2010 to add Ruby-specific features:

• \g<name> named subroutine calls.
• (?<name>...) named groups (Oniguruma also supports this).
• (?(cond)yes|no) conditional patterns.
• Atomic groups, possessive quantifiers.

The bundled copy is occasionally synced from upstream; local edits are mostly bug fixes plus the Ruby integration shim in re.c.

Entry points for modification

• New regex feature: extend regparse.c to recognise the syntax, regcomp.c to emit bytecode, regexec.c to interpret it. Add tests to test/ruby/test_regexp.rb and spec/ruby/core/regexp/.
• Performance fix in matching: regexec.c::match_at is the inner loop. Profile with --yjit-stats and the regex benchmarks under benchmark/regex/.
• Encoding-related bug: enc/<name>.c for the table; regparse.c::fetch_token for tokenisation.

See encoding.md for M17N background and core-classes/string-and-symbol.md for String#=~ etc.