[ruby-core:116871] [Ruby master Bug#20284] Regexp::TimeoutError is not triggered by a specific Regexp
Issue #20284 has been reported by jbeschi (jacopo beschi). ---------------------------------------- Bug #20284: Regexp::TimeoutError is not triggered by a specific Regexp https://bugs.ruby-lang.org/issues/20284 * Author: jbeschi (jacopo beschi) * Status: Open * Priority: Normal * ruby -v: 3.3.0 * Backport: 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN, 3.3: UNKNOWN ---------------------------------------- I've noticed that the Regexp::TimeoutError is not triggered for this Regexp: ```ruby 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 ``` -- https://bugs.ruby-lang.org/
Issue #20284 has been updated by mame (Yusuke Endoh). 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. ---------------------------------------- Bug #20284: Regexp::TimeoutError is not triggered by a specific Regexp https://bugs.ruby-lang.org/issues/20284#change-106908 * Author: jbeschi (jacopo beschi) * Status: Feedback * Priority: Normal * ruby -v: 3.3.0 * Backport: 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN, 3.3: UNKNOWN ---------------------------------------- I've noticed that the Regexp::TimeoutError is not triggered for this Regexp: ```ruby 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 ``` -- https://bugs.ruby-lang.org/
Issue #20284 has been updated by jbeschi (jacopo beschi). 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. ---------------------------------------- Bug #20284: Regexp::TimeoutError is not triggered by a specific Regexp https://bugs.ruby-lang.org/issues/20284#change-106909 * Author: jbeschi (jacopo beschi) * Status: Feedback * Priority: Normal * ruby -v: 3.3.0 * Backport: 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN, 3.3: UNKNOWN ---------------------------------------- I've noticed that the Regexp::TimeoutError is not triggered for this Regexp: ```ruby 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 ``` -- https://bugs.ruby-lang.org/
participants (2)
-
jbeschi (jacopo beschi) -
mame (Yusuke Endoh)