diff options
author | TSUYUSATO Kitsune <make.just.on@gmail.com> | 2022-12-14 12:57:14 +0900 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-12-14 12:57:14 +0900 |
commit | fbedadb61f49ba3aaf4f07939b4fc7d0b8f8ac03 (patch) | |
tree | 05f5147da45c55947f220e9e2119b905d97cdab3 | |
parent | fe3cbc61c805a860da3d41253879708ec86b6aa2 (diff) | |
download | ruby-fbedadb61f49ba3aaf4f07939b4fc7d0b8f8ac03.tar.gz |
Add `Regexp.linear_time?` (#6901)
-rw-r--r-- | include/ruby/onigmo.h | 2 | ||||
-rw-r--r-- | re.c | 34 | ||||
-rw-r--r-- | regexec.c | 16 | ||||
-rw-r--r-- | test/ruby/test_regexp.rb | 8 |
4 files changed, 59 insertions, 1 deletions
diff --git a/include/ruby/onigmo.h b/include/ruby/onigmo.h index 348c4ec08f..8d7c601703 100644 --- a/include/ruby/onigmo.h +++ b/include/ruby/onigmo.h @@ -854,6 +854,8 @@ OnigPosition onig_search_gpos(OnigRegex, const OnigUChar* str, const OnigUChar* ONIG_EXTERN OnigPosition onig_match(OnigRegex, const OnigUChar* str, const OnigUChar* end, const OnigUChar* at, OnigRegion* region, OnigOptionType option); ONIG_EXTERN +int onig_check_linear_time(OnigRegex reg); +ONIG_EXTERN OnigRegion* onig_region_new(void); ONIG_EXTERN void onig_region_init(OnigRegion* region); @@ -4194,6 +4194,39 @@ rb_reg_s_union_m(VALUE self, VALUE args) return rb_reg_s_union(self, args); } +/* + * call-seq: + * Regexp.linear_time?(re) + * Regexp.linear_time?(string, options = 0) + * + * Returns +true+ if matching against <tt>re</tt> can be + * done in linear time to the input string. + * + * Regexp.linear_time?(/re/) # => true + * + */ +static VALUE +rb_reg_s_linear_time_p(int argc, VALUE *argv, VALUE self) +{ + VALUE re; + VALUE src, opts = Qundef, n_flag = Qundef, kwargs; + + rb_scan_args(argc, argv, "12:", &src, &opts, &n_flag, &kwargs); + + if (RB_TYPE_P(src, T_REGEXP)) { + re = src; + if (opts != Qnil) { + rb_warn("flags ignored"); + } + } + else { + re = rb_class_new_instance(argc, argv, rb_cRegexp); + } + + rb_reg_check(re); + return RBOOL(onig_check_linear_time(RREGEXP_PTR(re))); +} + /* :nodoc: */ static VALUE rb_reg_init_copy(VALUE copy, VALUE re) @@ -4571,6 +4604,7 @@ Init_Regexp(void) rb_define_singleton_method(rb_cRegexp, "union", rb_reg_s_union_m, -2); rb_define_singleton_method(rb_cRegexp, "last_match", rb_reg_s_last_match, -1); rb_define_singleton_method(rb_cRegexp, "try_convert", rb_reg_s_try_convert, 1); + rb_define_singleton_method(rb_cRegexp, "linear_time?", rb_reg_s_linear_time_p, -1); rb_define_method(rb_cRegexp, "initialize", rb_reg_initialize_m, -1); rb_define_method(rb_cRegexp, "initialize_copy", rb_reg_init_copy, 1); @@ -694,7 +694,21 @@ unexpected_bytecode_error: bytecode_error: return ONIGERR_UNDEFINED_BYTECODE; } -#endif /* USE_MATCH_CACHE */ +#else /* USE_MATCH_CACHE */ +static OnigPosition count_num_cache_opcode(regex_t* reg, long* num, long* table_size) +{ + *num = NUM_CACHE_OPCODE_FAIL; + return 0; +} +#endif + +extern int +onig_check_linear_time(OnigRegexType* reg) +{ + long num = 0, table_size = 0; + count_num_cache_opcode(reg, &num, &table_size); + return num != NUM_CACHE_OPCODE_FAIL; +} extern void onig_region_clear(OnigRegion* region) diff --git a/test/ruby/test_regexp.rb b/test/ruby/test_regexp.rb index a3c1508ff6..20b1dfb986 100644 --- a/test/ruby/test_regexp.rb +++ b/test/ruby/test_regexp.rb @@ -1696,4 +1696,12 @@ class TestRegexp < Test::Unit::TestCase assert_nil(/^a*b?a*$/ =~ "a" * 1000000 + "x") end; end + + def test_linear_time_p + assert_send [Regexp, :linear_time?, /a/] + assert_send [Regexp, :linear_time?, 'a'] + assert_send [Regexp, :linear_time?, 'a', Regexp::IGNORECASE] + assert_not_send [Regexp, :linear_time?, /(a)\1/] + assert_not_send [Regexp, :linear_time?, "(a)\\1"] + end end |