Project

General

Profile

Actions

Bug #22606

open

Lazy zero repeat `x{0,0}?` can match one `x`, and raises "undefined bytecode (bug)" since 4.0

Bug #22606: Lazy zero repeat `x{0,0}?` can match one `x`, and raises "undefined bytecode (bug)" since 4.0

Added by segiddins (Samuel Giddins) about 12 hours ago. Updated about 10 hours ago.

Status:
Open
Assignee:
-
Target version:
-
ruby -v:
ruby 4.0.10 (2026-11-19 revision a704b7cd95) +PRISM [arm64-darwin25]
[ruby-core:127609]

Description

A zero repeat with the lazy modifier, x{0,0}?, is compiled as a loop instead of being dropped like the greedy x{0,0}. This has two visible effects.

1. The quantifier can consume one x

/\Ax{0,0}?x\z/.match("xx")              #=> #<MatchData "xx"> (expected: nil)
/\Ax{0,0}x\z/.match("xx")               #=> nil
/\A\w{0,0}?\w\z/.match?("ab")           #=> true (expected: false)
/\A(\w){0,0}?\w\z/.match("ab")&.to_a    #=> ["ab", "a"] (expected: nil)
/\A(?:ab){0,0}?ab\z/.match?("abab")     #=> true (expected: false)

The search optimizer treats the quantifier as empty, so the wrong match only shows when the first character of the subject also fits what follows the quantifier. For example /\Ax{0,0}?y/.match("xy") is nil.

x{0}? is not affected, because Ruby parses it as (?:x{0})?.

The results are the same on 3.1.7 and 3.4.10, so this part is not a regression.

2. Since 4.0, matching can raise RegexpError

/(?:x{0,0}?a+?)?/.match("")
#=> RegexpError: undefined bytecode (bug): /(?:x{0,0}?a+?)?/ (expected: #<MatchData "">)
/(a)\1{0,0}?|$/.match("")
#=> RegexpError: undefined bytecode (bug): /(a)\1{0,0}?|$/ (expected: #<MatchData "" 1:nil>)
/(?:ab{0,0}?)*/.match("x")
#=> RegexpError: undefined bytecode (bug): /(?:ab{0,0}?)*/ (expected: #<MatchData "">)

Regexp.linear_time?(/(a)\1{0,0}?|$/)    #=> true (expected: false)
Regexp.linear_time?(/(a)\1|$/)          #=> false

4.0.1, 4.0.6, 4.0.9 and 4.0.10 raise. 3.3.10 and 3.4.10 return the expected values.

Cause

compile_quantifier_node (regcomp.c) expands a greedy quantifier with upper == 0 to nothing. A lazy one falls through to compile_range_repeat_node and is emitted as an OP_REPEAT_NG / OP_REPEAT_INC_NG loop with lower == upper == 0:

/^x{0,0}?x$/
0:[begin-line] 1:[repeat-ng:0:5] 8:[exact1:x] 10:[repeat-inc-ng:0] 13:[exact1:x]
15:[end-line] 16:[end]

OP_REPEAT_NG pushes the body as an alternative whenever lower == 0, so the body is tried on backtrack. OP_REPEAT_INC_NG then increments the count to 1, which is neither < upper nor == upper, and execution continues after the loop with the body consumed.

The RegexpError is a regression from 18f8c514ea ("Fix memoization for the /(...){0}/ case", GH-13169). It comes from the match cache setup, not from the matcher executing a bad instruction. For a repeat with lower == 0 && upper == 0, count_num_cache_opcodes_inner (regexec.c) scans the body into a dummy counter. When the body holds an opcode the match cache does not support (OP_REPEAT_INC_NG_SG or a backreference in the examples above), the nested call sets the dummy counter to NUM_CACHE_OPCODES_IMPOSSIBLE and returns 0 without storing the scan position back to *pp. The caller then does goto fail with result == 0, so it returns success with p still inside the program. count_num_cache_opcodes sees p != reg->p + reg->used and returns ONIGERR_UNDEFINED_BYTECODE. match_at raises it on the first backtrack, and onig_check_linear_time ignores the return value.

Patch

Compile any quantifier with upper == 0 that is not referred to by a subexpression call to nothing, as the greedy form already is. No repeat with lower == upper == 0 is emitted after that, so the match cache path above is no longer reached. With this change all the examples in both sections return the expected values on 4.0.10.

--- a/regcomp.c
+++ b/regcomp.c
@@ -1038,6 +1038,9 @@
   else if (qn->upper == 0 && qn->is_referred != 0) { /* /(?<n>..){0}/ */
     len = SIZE_OP_JUMP + tlen;
   }
+  else if (qn->upper == 0) { /* {0} and {0,0}? : never match the body */
+    len = 0;
+  }
   else if (!infinite && qn->greedy &&
            (qn->upper == 1 ||
             IS_EXPAND_LIMIT_OK(tlen + SIZE_OP_PUSH, qn->upper))) {
@@ -1159,6 +1162,9 @@
     if (r) return r;
     r = compile_tree(qn->target, reg);
   }
+  else if (qn->upper == 0) { /* {0} and {0,0}? : never match the body */
+    r = 0;
+  }
   else if (!infinite && qn->greedy &&
            (qn->upper == 1 ||
             IS_EXPAND_LIMIT_OK(tlen + SIZE_OP_PUSH, qn->upper))) {

Separately, the dummy_num_cache_opcodes < 0 case in count_num_cache_opcodes_inner looks like it should goto impossible instead of goto fail ?

Actions

Also available in: PDF Atom