Project

General

Profile

Actions

Bug #20284

closed

Regexp::TimeoutError is not triggered by a specific Regexp

Added by jbeschi (jacopo beschi) 9 months ago. Updated 9 months ago.

Status:
Feedback
Assignee:
-
Target version:
-
[ruby-core:116871]

Description

I've noticed that the Regexp::TimeoutError is not triggered for this Regexp:

jacopo-37s-mb 3.3.0 ~ cat fail.rb
require 'benchmark'

p RUBY_DESCRIPTION
Regexp.timeout = 0.1
puts "Regexp.timeout: #{Regexp.timeout}"
re = /((a|aa)+)+b/
10.times do
  p Benchmark.realtime { re.match?("a" * 900000000) }
end
jacopo-37s-mb 3.3.0 ~ ruby fail.rb
"ruby 3.3.0 (2023-12-25 revision 5124f9ac75) [arm64-darwin22]"
Regexp.timeout: 0.1
1.1425850000232458
1.0082139987498522
1.064377998933196
1.0745620001107454
1.0647990014404058
1.6172770000994205
1.396629998460412
1.2450549993664026
1.3292079996317625
1.5961690004915

Updated by mame (Yusuke Endoh) 9 months ago

  • Status changed from Open to Feedback

Thanks for the report.

This takes a long time in the preprocessing part before regexp matching. I think this process is O(n) for the length n of the input string. Since Regexp.timeout= is a countermeasure against super-linear behavior, I feel this is not a big deal. And frankly, I can't think of a good idea to fix it.

It is also known that the timeout do not work for very large regexps that contain no instruction that checks timeouts. Maybe I should update the documentation?

Let me know if anyone has a nice idea to fix it.

Updated by jbeschi (jacopo beschi) 9 months ago

mame (Yusuke Endoh) wrote in #note-1:

Thanks for the report.

This takes a long time in the preprocessing part before regexp matching. I think this process is O(n) for the length n of the input string. Since Regexp.timeout= is a countermeasure against super-linear behavior, I feel this is not a big deal. And frankly, I can't think of a good idea to fix it.

It is also known that the timeout do not work for very large regexps that contain no instruction that checks timeouts. Maybe I should update the documentation?

Let me know if anyone has a nice idea to fix it.

Got it, makes complete sense. A note in the docs about it would be helpful though.

Actions

Also available in: Atom PDF

Like1
Like0Like0