Summary

An inline toggle (?imx) encloses the rest of the group it stands in, alternatives and all, and this engine split its alternation one level too high, so an alternative written after a toggle matched on its own. Fixing that gives the parser a second way to recurse, so how deep a pattern may nest is bounded here too.

Changes

An alternation after an inline toggle split one level too high

Onigmo wraps everything after the toggle, alternatives included, into one group under the new options, so a(?i)b|c is a(?i:b|c): parse_exp()'s "option only" branch hands the remainder to parse_subexp(), which is the alternation level. compile_atom() set c->flags and returned to compile_seq(), so the | split at the level the toggle was written at, a(?i)b|c being (?:a(?i)b)|c, and the c matched with no a before it:

/a(?i)b|c/ =~ "c"         # CRuby: nil, mruby: 0
/(a(?i)b|c)d/ =~ "acd"    # CRuby: 0,   mruby: 1
/x(a(?i)b|c)d/ =~ "xacd"  # CRuby: 0,   mruby: nil

The options themselves reached the right atoms either way, which is why the divergence showed only in the shape of the alternation. A toggle-off leaked alike, /a(?-i)b|c/i leaving the c case-sensitive, and so did (?x), whose free-spacing side already agreed.

The toggle arm now compiles that remainder with compile_alt() under the new flags and restores them after. compile_alt() consumes every | and stops at the group's ) or the end of the pattern, which is where the arm's caller already expects the parse point, so what follows is unchanged: the enclosing compile_seq() finds its terminator, mrb_re_compile() still refuses a stray ) at top level, (?i)* is still target of repeat operator is not specified, and capture numbering does not move.

The parser had no bound on its own recursion

compile_alt() calls compile_seq() calls compile_quantified() calls compile_atom(), whose group, lookaround, atomic and inline-option arms call compile_alt() again, so the parser recurses once per nesting level. Nothing counted the levels, and a deep enough pattern ran off the C stack: a pattern of 50000 nested (?: was a SIGSEGV rather than an error. That is pre-existing, but the change above gives the toggle a second way there, since (?i) now opens a level where before it set a flag and returned, so the bound belongs in this PR.

compile_alt(), the one entry the recursion passes through, now counts levels and refuses past MRB_REGEXP_PARSE_DEPTH_LIMIT with parse depth limit over, CRuby's message for the same refusal. Every construct that opens a level counts, the toggle among them, as Onigmo counts them: 4096 nested (?: and 4096 nested (?i) are refused alike there, which is independent confirmation of the tree this parser now builds.

The default is 4096, Onigmo's ONIG_MAX_PARSE_DEPTH, so a pattern is refused exactly where CRuby refuses it, 4095 levels compiling and 4096 raising on both. What that costs is stack. A level takes 560 bytes on a 64-bit gcc -O2 build, 528 at -Os and 592 on the clang -O3 build measured here, which is compile_alt()'s frame plus compile_seq()'s as -fstack-usage reports them, the rest inlining into the two. Measured as the deepest nesting that survives a given ulimit -s, that is:

So the deepest pattern the default accepts spends some 2.4 MiB, and so does a deeper one before being refused, since the count is reached at the bottom of the recursion. A build on a smaller stack than that has to lower the limit or keep the crash it exists to prevent; the header and the README both say so, with the -fstack-usage recipe for measuring a build's own per-level figure. The right-hand column is a third of the stack, the compiler not being the only thing standing on it. Nesting this deep is not what a written pattern does, a handful of levels being ordinary and dozens unusual, so a build that sets 128 still takes every pattern anyone writes and gives up only the CRuby-exact refusal point. Regexp::PARSE_DEPTH_LIMIT reads the value back, as Regexp::STACK_LIMIT and Regexp::STEP_LIMIT read theirs.

That trade, a CRuby-exact refusal point against a stack cost a small-stack build must opt out of, is the one choice in this PR a build can be asked to revisit.

The refusal needs a build that can reach it

Reaching a limit costs the stack that limit stands for, so the test skips a build whose limit stands above 512: at the default a pattern descends some 2.4 MiB before being refused, which is more stack than a Windows thread has at all, and no test may spend what the limit exists to keep a pattern from spending.

Nothing else could lift that skip. Which platforms could pay 2.4 MiB is not a question the test can ask: mruby defines no RUBY_PLATFORM, the one signal it has tells Windows from the rest through File::ALT_SEPARATOR, and Cosmopolitan, which runs the suite and whose main stack is smaller than a POSIX host's, is not distinguishable from Linux by it. So a build sets a limit a test may reach instead, which is what the ascii-ctype build now does at 512, some 300 KiB. That build already exists to give an mruby-regexp refusal a home, what /i answers where the build has no folding table, and the depth a pattern may nest is not what ASCII classification is about, so the two do not tread on each other. It rides along there rather than in a build of its own so the matrix runs no extra pass.

Behaviour

Three things an existing pattern can notice.

An alternative after a toggle now wants what precedes the toggle, which is the fix: the three rows above, and a toggle-off and an (?x) alike.

A pattern nested past the limit raises RegexpError where it used to crash or compile. At the default that is 4096 levels or more, where CRuby raises the same error; a build that lowers the limit moves the point.

Three patterns in a 4000-pattern toggle fuzz now reach step limit over (MRB_REGEXP_STEP_LIMIT) where they used to answer. All three are nested quantified alternations carrying a toggle in nearly every sequence; splitting inside the toggle's scope rather than at the level above changes what the search retries, so the same step limit is reached by a different walk. CRuby answers nil for all three, and two of them answered wrongly here before. A control run of 124,000 cases over patterns with no toggle in them answers identically before and after.

Size

.text of bin/mruby, size -A, for the five builds of build_config/ci/gcc-clang.rb, master and this branch built at the same path in an empty build directory:

Two objects account for it: re_compile.o .text grows by 560, 448, 432, 560 and 112 bytes down that column, and regexp.o by 48, 48, 48, 48 and 80 for the new constant. The ascii-ctype row also carries the MRB_REGEXP_PARSE_DEPTH_LIMIT=512 this PR gives that build, which changes one constant.

For a build that carries the gem on flash, re_compile.o .text at -Os grows by 50 bytes under gcc (13,863 to 13,913) and 56 under clang (15,638 to 15,694), against some 87 KiB for the whole gem. RAM is one uint32_t on re_compiler, which lives on the C stack for the duration of a compile; no heap allocation changes. The C stack per nesting level is what it was under gcc, 560 bytes at -O2 and 528 at -Os, and under clang -Os (480); at clang -O3 it goes from 376 to 592, clang no longer folding compile_seq() into the level. What changed everywhere is that (?i) now opens a level of its own.

Testing

• rake test on the default config at each of the three commits: 0 KO, 0 crash.
• MRUBY_CONFIG=build_config/ci/gcc-clang.rb rake test, all five builds: 0 KO, 0 crash. The depth assertions run in ascii-ctype and skip in the other four.
• The same suite at MRB_REGEXP_PARSE_DEPTH_LIMIT of 48, 512, 1024 and 4096: green at each, the refusal asked at the first two and skipped at the last two, for a plain group, a scoped option group, a lookahead, an atomic group and a toggle. The range guard rejects 0, -1 and 2000000 at compile time.
• A differential run of 4000 toggle-heavy patterns against 15 subjects each, master and this branch against CRuby 4.0.6. Of the 14,760 answers that parted from CRuby, 14,750 agree now. The ten that still part part the same way when (?i: is written where the toggle stands, so they are not about the toggle's scope: /[BA]*(?i:A)/ =~ "A" is nil in CRuby and 0 here on master too, and /((|b[ab])+[aB])+/ =~ "aB" parts with no option anywhere in it.
• A control differential run of 124,000 cases over patterns with no toggle: master and this branch answer identically, byte for byte.
• The crash and its absence, on the binaries built above:

$ master/bin/mruby -e 'Regexp.new("(?:" * 50000 + "a" + ")" * 50000)'
Segmentation fault (core dumped)

$ branch/bin/mruby -e 'Regexp.new("(?:" * 50000 + "a" + ")" * 50000)'
trace (most recent call last):
        [1] -e:1
-e:1:in initialize: parse depth limit over: /(?:(?:(?:...  (RegexpError)

$ (ulimit -s 1024; master/bin/mruby -e 'Regexp.new("(?:" * 5000 + "a" + ")" * 5000)')
Segmentation fault (core dumped)

$ (ulimit -s 1024; ascii-ctype/bin/mruby -e 'Regexp.new("(?:" * 5000 + "a" + ")" * 5000)')
-e:1:in initialize: parse depth limit over: /(?:(?:(?:...  (RegexpError)

(the ascii-ctype build is the one that sets the limit to 512; the error echoes the whole pattern, elided here.)

Environment

cxx_abi links through clang++; the other four link through clang. The compile line of re_compile.c in each build, with -MMD -c, the -I paths and -o dropped:

# bintest
clang -std=gnu99 -g -O3 -Wall -Wundef -Werror-implicit-function-declaration -Wwrite-strings -Wzero-length-array -DMRB_GC_FIXED_ARENA -DMRBGEM_MRUBY_REGEXP_VERSION=0.0.0 -DMRB_USE_BIGINT -DMRB_USE_COMPLEX -DHAVE_MRUBY_ENCODING_GEM -DMRB_UTF8_STRING -DHAVE_MRUBY_IO_GEM -DMRB_USE_RATIONAL -DHAVE_MRUBY_REGEXP_GEM -DMRB_USE_SET -DMRB_USE_TASK_SCHEDULER -DMRB_USE_DEBUG_HOOK

# ascii-ctype
clang -std=gnu99 -g -O3 -Wall -Wundef -Werror-implicit-function-declaration -Wwrite-strings -Wzero-length-array -DMRB_USE_ASCII_CTYPE -DMRB_REGEXP_PARSE_DEPTH_LIMIT=512 -DMRBGEM_MRUBY_REGEXP_VERSION=0.0.0 -DMRB_USE_BIGINT -DMRB_USE_COMPLEX -DHAVE_MRUBY_ENCODING_GEM -DMRB_UTF8_STRING -DHAVE_MRUBY_IO_GEM -DMRB_USE_RATIONAL -DHAVE_MRUBY_REGEXP_GEM -DMRB_USE_SET -DMRB_USE_TASK_SCHEDULER

# byte-string
clang -std=gnu99 -g -O3 -Wall -Wundef -Werror-implicit-function-declaration -Wwrite-strings -Wzero-length-array -DMRBGEM_MRUBY_REGEXP_VERSION=0.0.0 -DMRB_USE_BIGINT -DMRB_USE_COMPLEX -DHAVE_MRUBY_IO_GEM -DMRB_USE_RATIONAL -DHAVE_MRUBY_REGEXP_GEM -DMRB_USE_SET -DMRB_USE_TASK_SCHEDULER

# cxx_abi
clang -g -O3 -Wall -Wundef -Wwrite-strings -Wzero-length-array -x c++ -std=gnu++03 -DMRB_GC_FIXED_ARENA -DMRBGEM_MRUBY_REGEXP_VERSION=0.0.0 -DMRB_USE_CXX_EXCEPTION -DMRB_USE_CXX_ABI -DMRB_USE_BIGINT -DMRB_USE_COMPLEX -DHAVE_MRUBY_ENCODING_GEM -DMRB_UTF8_STRING -DHAVE_MRUBY_IO_GEM -DMRB_USE_RATIONAL -DHAVE_MRUBY_REGEXP_GEM -DMRB_USE_SET -DMRB_USE_TASK_SCHEDULER

# full-debug
clang -std=gnu99 -g -O3 -Wall -Wundef -Werror-implicit-function-declaration -Wwrite-strings -Wzero-length-array -g3 -O0 -DMRB_GC_STRESS -DMRB_USE_DEBUG_HOOK -DMRBGEM_MRUBY_REGEXP_VERSION=0.0.0 -DMRB_DEBUG -DMRB_USE_BIGINT -DMRB_USE_COMPLEX -DHAVE_MRUBY_ENCODING_GEM -DMRB_UTF8_STRING -DHAVE_MRUBY_IO_GEM -DMRB_USE_RATIONAL -DHAVE_MRUBY_REGEXP_GEM -DMRB_USE_SET -DMRB_USE_TASK_SCHEDULER

Summary by CodeRabbit

• New Features

  • Added a configurable regular-expression parser depth limit, defaulting to 4096.
  • Exposed the limit through Regexp::PARSE_DEPTH_LIMIT.
  • Patterns exceeding the configured limit now raise RegexpError.

• Bug Fixes

  • Improved handling and scoping of inline regular-expression options across alternatives and nested expressions.

• Documentation

  • Documented configuration, supported values, counted constructs, and stack-sizing guidance.

• Tests

  • Added coverage for parser-depth limits, inline options, lookarounds, atomic groups, and invalid quantifier usage.