From: "mame (Yusuke Endoh) via ruby-core" Date: 2026-11-19T09:07:23+00:00 Subject: [ruby-core:127620] [Ruby Bug#22606] Lazy zero repeat `x{0,0}?` can match one `x`, and raises "undefined bytecode (bug)" since 4.0 Issue #22606 has been updated by mame (Yusuke Endoh). Thank you! Your patch looks good to me, so I opened a pull request with it: https://github.com/ruby/ruby/pull/20018 > ``` > Regexp.linear_time?(/(a)\1{0,0}?|$/) #=> true (expected: false) > ``` Note that `Regexp.linear_time?(/(a)\1{0,0}?|$/)` is true with the patch, not false. I think this is fine because `\1` is never executed, but let's discuss it if this is not what you intended. ---------------------------------------- Bug #22606: Lazy zero repeat `x{0,0}?` can match one `x`, and raises "undefined bytecode (bug)" since 4.0 https://bugs.ruby-lang.org/issues/22606#change-120139 * Author: segiddins (Samuel Giddins) * Status: Open * ruby -v: ruby 4.0.10 (2026-11-19 revision a704b7cd95) +PRISM [arm64-darwin25] * Backport: 3.3: UNKNOWN, 3.4: UNKNOWN, 4.0: UNKNOWN ---------------------------------------- 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` ```ruby /\Ax{0,0}?x\z/.match("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` ```ruby /(?:x{0,0}?a+?)?/.match("") #=> RegexpError: undefined bytecode (bug): /(?:x{0,0}?a+?)?/ (expected: #) /(a)\1{0,0}?|$/.match("") #=> RegexpError: undefined bytecode (bug): /(a)\1{0,0}?|$/ (expected: #) /(?:ab{0,0}?)*/.match("x") #=> RegexpError: undefined bytecode (bug): /(?:ab{0,0}?)*/ (expected: #) 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. ```diff --- a/regcomp.c +++ b/regcomp.c @@ -1038,6 +1038,9 @@ else if (qn->upper == 0 && qn->is_referred != 0) { /* /(?..){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` ? -- https://bugs.ruby-lang.org/ ______________________________________________ ruby-core mailing list -- ruby-core@ml.ruby-lang.org To unsubscribe send an email to ruby-core-leave@ml.ruby-lang.org ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/