Bug #22606
openLazy zero repeat `x{0,0}?` can match one `x`, and raises "undefined bytecode (bug)" since 4.0
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 ?
Updated by mame (Yusuke Endoh) about 10 hours ago
Thank you! Your patch looks good to me, so I opened a pull request with it: https://github.com/ruby/ruby/pull/20018
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.