The Pike VM and pattern compiler were exporting bare names like
`re_compile`, `re_exec`, `re_free`, `re_is_word_char`, `re_utf8_charlen`,
`re_utf8_decode`. `re_exec` in particular collides with the obsolete
BSD libc function of the same name (still present on FreeBSD/NetBSD
base), so embedding mruby alongside platform regex could surface a
link-time symbol clash.
Rename all six entry points to `mrb_re_*` to keep the gem's external
symbols inside mruby's namespace. Source file names and the public
header path are unchanged.
Refs #6858.
Co-authored-by: Claude <noreply@anthropic.com>
first_set_walk returned TRUE when it reached RE_MATCH via epsilon
transitions, but that's exactly the case where the optimization is
wrong: an empty-matchable pattern can start matching at any position,
including bytes that aren't in the computed first-byte set. The
skip-ahead loop in pike_vm then advanced past valid empty-match
positions, producing a match at the wrong offset (e.g. /a?/.match("b")
reported the empty match at index 1 instead of 0).
Co-authored-by: Claude <noreply@anthropic.com>
insert_inst was incrementing every offset >= pos, but an offset equal to
pos already points to the new instruction's slot -- bumping it shifts
the target onto whatever code got displaced (typically the body of the
quantified atom). For patterns like /a?b?/ the SPLIT for `a?` then
landed on `CHAR 'b'` instead of the new SPLIT for `b?`, so the "skip a"
thread tried to consume 'b' and died, and both atoms failed to match
zero characters at once.
Fixes#6853.
Co-authored-by: Claude <noreply@anthropic.com>
regexp_init() called re_compile() before setting @source / @flags
IVs, so a Regexp that survived a compile-time exception (e.g. picked
up via ObjectSpace.each_object after `Regexp.new("(")` raised) was
left with no @source. obj.hash then dereferenced nil through
mrb_str_hash() and crashed.
Set the IVs before re_compile(), and make regexp_hash / regexp_eql
defensive against a non-String @source so Regexp.allocate.hash also
behaves.
Co-authored-by: Claude <noreply@anthropic.com>
Inside `[...]`, `\b` denotes U+0008 (backspace) -- the same as
MRI/Onigmo and PCRE. parse_escape() was missing the case, so
the backslash was dropped and the bare letter `b` was inserted
into the class. `[\b]` therefore matched every `b` instead of
backspace.
Add `case 'b': return '\b';` to parse_escape(). The function
is only reached from the character-class body and range
endpoints; the top-level dispatcher emits RE_WBOUND for `\b`
before falling through, so the word-boundary semantics outside
`[...]` are unchanged.
Reported by Sam Ruby in matz/spinel#632; same engine bug
affects both spinel and mruby.
Co-authored-by: Claude <noreply@anthropic.com>
The RE_BACKREF execution path read `captures[group * 2]` and
`captures[group * 2 + 1]` without verifying that the group
index fit in the allocated captures array. A pattern like
`/\1/` (no capture group, but a backreference to group 1) is
accepted by the compiler and lands in execution with `ncap = 2`
(only group 0 slots) and an instruction asking for group 1 --
a 4-byte read past the end of the allocation.
Reported by ClusterFuzz testcase
clusterfuzz-testcase-minimized-mruby_fuzzer-5474946829844480.
Add `if (group * 2 + 1 >= ncap) return FALSE;` ahead of the
captures access, mirroring the bounds guard already present in
RE_SAVE. The compiler's permissive `\<digit>` handling stays
unchanged; the runtime now treats a reference to a non-existent
group as a non-match rather than UB.
Co-authored-by: Claude <noreply@anthropic.com>
The backtracking engine recurses via C function calls at RE_SPLIT,
RE_SPLITNG, RE_SAVE, RE_LOOKAHEAD, RE_NEG_LOOKAHEAD, RE_LOOKBEHIND,
and RE_NEG_LOOKBEHIND. Patterns like `(?=)+` make the engine
recurse without consuming input, exhausting the C stack and
triggering SIGSEGV long before MRB_REGEXP_STEP_LIMIT is reached
(each recursion charges only ~1 step, but each frame costs ~150
bytes of stack).
Reported by ClusterFuzz testcase
clusterfuzz-testcase-minimized-mruby_fuzzer-4653331195953152.
Add an integer recursion-depth counter passed alongside the step
counter, and abort the current branch with FALSE when it exceeds
MRB_REGEXP_RECURSION_LIMIT (default 1000, configurable like
STEP_LIMIT). Legitimate patterns nest only a few levels;
pathological inputs bail without crashing the VM.
Co-authored-by: Claude <noreply@anthropic.com>
re_compile stored raw pointers into the pattern source in
pat->named_captures[i].name. Two ways this could dangle:
- With /x, the source was c.stripped, freed at end of compile.
Later reads (regexp construction, MatchData[:name] lookup) hit
freed memory.
- Without /x, the pointer aliased the input string's RSTRING_PTR.
Mutating that string after Regexp.new could re-buffer it, leaving
name dangling.
Allocate one arena buffer per regexp (only when num_named > 0) and
copy all names in. Common-case regexps without named captures pay
zero bytes.
Reported by OSS-Fuzz (testcase 5695283416858624).
Co-authored-by: Claude <noreply@anthropic.com>
`class String; def split` in mruby-regexp/mrblib/string_regexp.rb
replaced the C-defined String#split rather than overriding it, so
the in-Ruby `return super if pattern.nil?` paths raised
NoMethodError for any `"x".split(...)` call once mruby-regexp was
loaded (the default full-core production binary).
The regression wasn't caught by the test suite because per-gem
tests run under mrb_open_core() with only the gem's dep_list, so
the broken override is never visible from test/t/string.rb
(mruby-test, not mruby-regexp).
Add `alias __split split` at the top of the override class body,
which captures the C-defined method, and change the Ruby override
to delegate via `__split(pattern, limit)` for non-regexp fallback
paths. Add a bintest under mruby-bin-mruby that runs through
bin/mruby (full gem load) to catch this regression class.
Co-authored-by: Claude <noreply@anthropic.com>
Two related bugs uncovered by OSS-Fuzz testcase 6692915710853120:
1. add_class allowed unbounded growth of c->classes. Class IDs are
stored in re_inst.a (uint8_t), so any ID >= 256 silently aliases
another class via the cast at emit sites. Worse, c->class_capa
(uint16_t) overflows on doubling past 32768 -> 0, then
mrb_realloc(..., 0) returns NULL, and the next memset(&c->classes[id])
segfaults at NULL+offset. Cap with RE_MAX_CLASSES = 256 (the encoding
limit) and raise via compile_error past that.
2. Once the crash is fixed, the testcase exposes a leak of
c->named_captures: compile_error frees c->code, c->classes, and
c->stripped (commit 3f321f09bc) but missed named_captures. Add it
to the same cleanup block.
Reported by OSS-Fuzz (clusterfuzz testcase 6692915710853120).
Co-authored-by: Claude <noreply@anthropic.com>
parse_quantifier read digits via min = min * 10 + d with no upper
bound, allowing patterns like /a{1111558833}/ to overflow int and
trigger signed-integer-overflow UB. Even without UB, the value
flows into compile_quantified's emit loop where it would attempt
to emit a billion copies of the atom.
Add RE_MAX_REPEAT = 32768 (the largest value that still fits in
re_inst.offset, the uint16_t jump field) and reject quantifiers
beyond that during parsing via compile_error. Apply the same cap
to the max field.
Reported by OSS-Fuzz (clusterfuzz testcase 6152367367323648).
Co-authored-by: Claude <noreply@anthropic.com>
compile_error is the chokepoint for all regex-compile errors;
mrb_raisef longjmps out of re_compile, abandoning the stack-local
re_compiler struct. Three connected bugs:
1. Memory leak: c->code and c->classes (grown by emit/add_class
via mrb_realloc) were never freed before raising, leaking on
any compile error like /[/. c->stripped was already cleaned up
here for the same reason; the other two buffers were missed.
2. Use-after-free: c->src aliases c->stripped when RE_FLAG_EXTENDED
is set, but the original code freed c->stripped before passing
c->src to mrb_raisef's "%s" formatter. Format the message into
an mrb_value first (mruby's GC-managed string survives the
longjmp), then free, then raise.
3. Heap-buffer-overflow: strip_extended returns a non-NUL-terminated
buffer of size len. Even with format-before-free, "%s" called
strlen and read past the buffer end. Use mruby's %l directive
which takes an explicit (char*, size_t) and avoids strlen.
Reported by OSS-Fuzz (clusterfuzz testcase 5394267353972736).
Co-authored-by: Claude <noreply@anthropic.com>
The first-byte bitmap (bm[16]) is intentionally ASCII-only
(include/re_internal.h:75 documents it as 128 bits / ASCII), and
the matcher at re_exec.c:39 short-circuits for bytes >= 128. But
first_set_walk's RE_CHAR case wrote bm[a >> 3] without checking
a, overflowing the 16-byte stack buffer for any pattern
containing a byte >= 128.
When a >= 128, return FALSE so compute_first_set marks the filter
unusable, matching the bail-out pattern already used for RE_NCLASS
and RE_ANY. The pattern still compiles and matches; only the
first-byte optimization is skipped.
Reported by OSS-Fuzz (clusterfuzz testcase 4909069193510912).
Co-authored-by: Claude <noreply@anthropic.com>
The mrb_match_data struct stores `source` and `regexp` as plain
mrb_value members of a C-allocated struct, which the GC does not
scan. Under MRB_GC_STRESS the source string could be collected
while the MatchData was still alive, causing md[0] to read freed
memory (observed as "\xff\xff\xff").
Also stash source and regexp as instance variables on the MatchData
object so they remain reachable via the object's iv_tbl during GC.
The C struct members continue to provide fast direct access, and
no other call sites need to change.
Co-authored-by: Claude <noreply@anthropic.com>
Pre-allocate visited array and thread lists at compile time and
reuse them across re_exec calls. A cache_in_use flag detects
re-entrancy and falls back to malloc when needed.
Eliminates 3 malloc + 3 free per NFA execution for the common
non-re-entrant case. Combined with the literal fast path, brings
literal match? from 4.7x to 2.5x vs CRuby.
Co-authored-by: Claude <noreply@anthropic.com>
Pure literal patterns (/hello/, /abc/) are detected at compile
time and matched using memchr+memcmp directly, completely
bypassing Pike VM setup (no malloc, no visited array, no thread
lists). Engine-only time drops from ~400ns to ~80ns.
Co-authored-by: Claude <noreply@anthropic.com>
Move the match loop for non-block gsub, sub, and scan from Ruby
to C. Key improvements:
- re_exec called directly in a loop without MatchData per match
- MatchData created only once (for $~ of the last match)
- Replacement \-escapes processed in C (apply_replacement)
- No intermediate string objects for pre_match/post_match
- Block variants remain in Ruby to avoid VM callbacks
Performance improvement (vs CRuby ratio):
gsub simple: 5.0x -> 2.9x
scan words: 5.8x -> 1.9x
Co-authored-by: Claude <noreply@anthropic.com>
Compute a 128-bit bitmap of bytes that could start a match.
For patterns like /cat|dog|fox/ the bitmap contains only {b,c,d,f},
skipping positions where no alternative can match. For /\d+/ only
{'0'-'9'} are set.
Used when no literal prefix is available (alternation, character
class patterns). Falls back gracefully when too many bytes match.
Key improvements vs CRuby ratio:
alternation miss: 9.5x -> 3.6x
\d+ medium string: 3.0x -> 1.4x
Co-authored-by: Claude <noreply@anthropic.com>
Move pool_copy inside each match condition so captures are only
copied for threads that advance to the next step, skipping the
copy for non-matching threads.
Co-authored-by: Claude <noreply@anthropic.com>
Extract the leading literal bytes from compiled bytecode and use
memchr + memcmp to skip positions where the prefix cannot match.
Both Pike VM and backtracking engine benefit.
For /needle/ in a 2006-char string: 29x faster (1.97s -> 0.07s),
now on par with CRuby/Oniguruma.
Co-authored-by: Claude <noreply@anthropic.com>
The flag is set not only for non-greedy quantifiers but also for
lookahead, lookbehind, and backreferences. The new name accurately
reflects its purpose: indicating that the backtracking engine is
required instead of the Pike VM.
Co-authored-by: Claude <noreply@anthropic.com>
Same pattern as the earlier gsub fix: collect parts in an array
and join at the end instead of repeated string concatenation.
Co-authored-by: Claude <noreply@anthropic.com>
Replace fixed RE_MAX_CAPTURES*2 (256 bytes) stack array with
malloc sized to actual pat->num_captures*2. Consistent with
the Pike VM's dynamic ncap-sized pool.
Co-authored-by: Claude <noreply@anthropic.com>
Both methods had identical loop bodies, differing only in the
starting group index (1 vs 0). Extracted matchdata_to_ary()
with a from parameter.
Co-authored-by: Claude <noreply@anthropic.com>
Regexp#match and Regexp#=~ shared most of their logic (get pattern,
execute, create MatchData, set globals). Extracted into exec_match()
internal function. Regexp#=~ now calls exec_match() and reads the
match position from the returned MatchData.
Co-authored-by: Claude <noreply@anthropic.com>
The pattern of reading @flags IV and converting to uint32_t was
repeated in 6 methods. Consolidated into a single helper function.
Co-authored-by: Claude <noreply@anthropic.com>
Add (?<=...) positive and (?<!...) negative lookbehind support.
The sub-pattern must have a fixed byte length (no quantifiers or
alternation), computed at compile time and stored in the instruction.
At execution time, the engine backs up by that many bytes and runs
the sub-pattern forward. Maximum lookbehind length is 255 bytes.
Co-authored-by: Claude <noreply@anthropic.com>
Collect replacement parts in an array and join at the end instead
of repeated string += which creates intermediate string objects.
Co-authored-by: Claude <noreply@anthropic.com>
When match? calls re_exec with captures=NULL, the Pike VM now
skips all capture pool operations: no pool_copy, no RE_SAVE
writes, no pool compaction. Only a single dummy pool slot is
allocated. This significantly reduces work for boolean matching.
Co-authored-by: Claude <noreply@anthropic.com>
Pre-intern the $1-$9 symbols on first use instead of calling
mrb_intern_cstr (which computes strlen + hash) on every match.
Co-authored-by: Claude <noreply@anthropic.com>
Major changes to the NFA execution engine:
- Thread captures stored in a flat pool sized to actual ncap
(e.g. 4 ints for 1 capture group vs 64 fixed), dramatically
reducing per-thread copy cost
- Generation counter for visited[] eliminates per-step memset
of the entire bytecode-length array
- Pool compaction between steps reclaims dead thread slots
- Backtracking engine also uses dynamic ncap-sized captures
Co-authored-by: Claude <noreply@anthropic.com>
Internal flags (MULTILINE=2, DOTALL=4, EXTENDED=8) differ from
Ruby constants (EXTENDED=2, MULTILINE=4). Convert in C instead
of returning raw internal flags. Also add Regexp#casefold?.
Co-authored-by: Claude <noreply@anthropic.com>
The x flag ignores unescaped whitespace and #comments in patterns,
making complex regexps more readable. Whitespace inside character
classes [...] remains literal. Implemented as a preprocessing step
that strips whitespace/comments before compilation.
Co-authored-by: Claude <noreply@anthropic.com>
Two regexps are equal when they have the same source and flags.
Hash is computed from source string hash mixed with flags.
Co-authored-by: Claude <noreply@anthropic.com>
Regexp#to_s now returns (?flags:source) format (e.g. "(?i:abc)")
instead of the /source/flags format used by Regexp#inspect.
Co-authored-by: Claude <noreply@anthropic.com>
- $1-$9 global variables set by Regexp#match and Regexp#=~
- $1-$9 cleared to nil on match failure
- add mruby-regexp to stdlib.gembox (auto-included in standard builds)
- remove duplicate gem entry from host-debug.rb
Co-authored-by: Claude <noreply@anthropic.com>
implement positive and negative lookahead in the backtracking engine:
- (?=pattern): succeeds if pattern matches at current position
without consuming characters
- (?!pattern): succeeds if pattern does NOT match at current position
new bytecodes RE_LOOKAHEAD and RE_NEG_LOOKAHEAD implemented in
the backtracking engine via nested bt_match calls.
Co-authored-by: Claude <noreply@anthropic.com>
support named capture groups in patterns:
- compiler parses (?<name>...) syntax and builds name table
- MatchData#[:name] and MatchData#["name"] access by name
- MatchData#named_captures returns {name => value} hash
- Regexp#named_captures returns {name => group_number} hash
- named captures stored in mrb_regexp_pattern for GC safety
Co-authored-by: Claude <noreply@anthropic.com>
non-greedy patterns now correctly match the shortest possible
string. patterns with non-greedy quantifiers are dispatched to
the backtracking engine which naturally handles non-greedy
semantics.
the Pike VM continues to be used for purely greedy patterns
(O(n*m) guarantee).
Co-authored-by: Claude <noreply@anthropic.com>
add a recursive backtracking engine that handles \1-\9
backreferences. the Pike VM (NFA) is used for patterns without
backreferences; patterns with backreferences automatically
fall back to the backtracking engine.
the backtracking engine has a step limit (MRB_REGEXP_STEP_LIMIT,
default 1M) to prevent ReDoS on pathological patterns.
also adds SAVE backtracking (save/restore capture positions on
failed branches) for correct submatch tracking.
Co-authored-by: Claude <noreply@anthropic.com>
add tests for: empty pattern, nested captures, word boundary \b,
non-capturing groups (?:), sub/gsub with block, scan with captures,
split with regexp, case/when with regexp, date reformatting.
known limitation: non-greedy quantifiers (*?, +?) currently behave
as greedy. needs match priority tracking (TODO for Phase 2).
Co-authored-by: Claude <noreply@anthropic.com>
- /regex/ literal syntax now works (compiler generates Regexp.compile)
- Regexp#match and Regexp#=~ set $~ global variable
- Regexp.last_match(n) for accessing capture groups
- Regexp.compile as alias for Regexp.new
- Regexp#options
Co-authored-by: Claude <noreply@anthropic.com>
Yukihiro "Matz" Matsumoto