Project

General

Profile

Actions

Feature #19194

closed

Add Regexp.linear_time?

Added by make_now_just (Hiroya Fujinami) about 1 year ago. Updated about 1 year ago.

Status:
Closed
Target version:
[ruby-dev:52014]

Description

I suggest adding a new method named Regexp.linear_time? to check if matching against a given regexp can be completed in linear time by the optimization introduced in #19104 (GitHub PR #6486).

This method was discussed in #19104. I'm not sure the name is best.

Example

Regexp.linear_time?(/a/)        # => true
Regexp.linear_time?(/(a|a)*\1/) # => false, because this uses a back-reference.

# This can accept a regexp source string and flags like `Regexp.new`.
Regexp.linear_time?('a')                     # => true
Regexp.linear_time?('a', Regexp::IGNORECASE) # => true

For example, this method is useful for implementing a Rubocop rule to check a regexp is ReDoS safe.

Implementation

Implementation is done at GitHub PR #6901.
See the details there.

Updated by mame (Yusuke Endoh) about 1 year ago

@make_now just Thank you!

I would like to propose @make_now_just (Hiroya Fujinami) as a committer. He has made a great improvement to the Regexp engine. Ruby's Regexp engine is in a state of its own fork from onigmo, and he is a valuable person who can maintain it. @matz (Yukihiro Matsumoto) What do you think?

Note: I have spoken directly with @make_now_just (Hiroya Fujinami) and he has agreed with my proposal to a committer, and I am proposing it.

Updated by matz (Yukihiro Matsumoto) about 1 year ago

Accepted.

Matz.

Updated by matz (Yukihiro Matsumoto) about 1 year ago

Also accepted to nominate him a committer.

Matz.

Actions #4

Updated by hsbt (Hiroshi SHIBATA) about 1 year ago

  • Target version set to 3.2

Updated by make_now_just (Hiroya Fujinami) about 1 year ago

Thank you for accepting the change and nominating me to a committer. I welcome this nomination.

Updated by hsbt (Hiroshi SHIBATA) about 1 year ago

  • Status changed from Open to Assigned
  • Assignee set to make_now_just (Hiroya Fujinami)

I added write permission to @make_now_just (Hiroya Fujinami) now. Can you apply this by yourself?

Updated by make_now_just (Hiroya Fujinami) about 1 year ago

@hsbt (Hiroshi SHIBATA) Sorry, I'm not sure what "apply" means. May I merge the pull request on GitHub?

Updated by hsbt (Hiroshi SHIBATA) about 1 year ago

May I merge the pull request on GitHub?

Yes, you can merge it. I meant commit and push to master branch directly or merge pull-request.

Updated by hsbt (Hiroshi SHIBATA) about 1 year ago

  • Status changed from Assigned to Closed

Updated by jnchito (Junichi Ito) about 1 year ago

I feel it would be more natural if it was defined as instance method:

/a/.linear_time?
Regexp.new('a').linear_time?

Is there any reason for class method?

Actions

Also available in: Atom PDF

Like1
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like1