Project

General

Profile

Actions
Copy link

Feature #19194

closed

Add Regexp.linear_time?

Feature #19194: Add Regexp.linear_time?

Added by make_now_just (Hiroya Fujinami) almost 3 years ago. Updated almost 3 years ago.

Status:
Closed
Assignee:
make_now_just (Hiroya Fujinami)
Target version:
3.2
[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.

Actions
Copy link

Also available in: PDF Atom