[ruby-core:112594] [Ruby master Bug#19467] Some linear_time regexp does not match in linear time
Issue #19467 has been reported by tompng (tomoya ishida). ---------------------------------------- Bug #19467: Some linear_time regexp does not match in linear time https://bugs.ruby-lang.org/issues/19467 * Author: tompng (tomoya ishida) * Status: Open * Priority: Normal * ruby -v: ruby 3.3.0dev (2023-02-17T18:10:16Z master c3bae033eb) [x86_64-linux] * Backport: 2.7: UNKNOWN, 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN ---------------------------------------- `Regexp.linear_time?(/\A.*a.*x\z/) #=> true` but it does not match in linear time ~~~ruby Regexp.linear_time? /\A(.*a.*)x\z/ #=> true /\A(.*a.*)x\z/ =~ 'a'*100000+'y' #=> nil, processing time: 0.016995s Regexp.linear_time? /\A.*a.*x\z/ #=> true /\A.*a.*x\z/ =~ 'a'*100000+'y' #=> nil, processing time: 21.479335s ~~~ -- https://bugs.ruby-lang.org/
Issue #19467 has been updated by hsbt (Hiroshi SHIBATA). Status changed from Open to Assigned Assignee set to make_now_just (Hiroya Fujinami) ---------------------------------------- Bug #19467: Some linear_time regexp does not match in linear time https://bugs.ruby-lang.org/issues/19467#change-102043 * Author: tompng (tomoya ishida) * Status: Assigned * Priority: Normal * Assignee: make_now_just (Hiroya Fujinami) * ruby -v: ruby 3.3.0dev (2023-02-17T18:10:16Z master c3bae033eb) [x86_64-linux] * Backport: 2.7: UNKNOWN, 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN ---------------------------------------- `Regexp.linear_time?(/\A.*a.*x\z/) #=> true` but it does not match in linear time ~~~ruby Regexp.linear_time? /\A(.*a.*)x\z/ #=> true /\A(.*a.*)x\z/ =~ 'a'*100000+'y' #=> nil, processing time: 0.016995s Regexp.linear_time? /\A.*a.*x\z/ #=> true /\A.*a.*x\z/ =~ 'a'*100000+'y' #=> nil, processing time: 21.479335s ~~~ -- https://bugs.ruby-lang.org/
Issue #19467 has been updated by naruse (Yui NARUSE). Backport changed from 2.7: DONTNEED, 3.0: DONTNEED, 3.1: DONTNEED, 3.2: REQUIRED to 2.7: DONTNEED, 3.0: DONTNEED, 3.1: DONTNEED, 3.2: DONE ruby_3_2 4b4087dce318570f9f9c05e14900325b499fb632 merged revision(s) e22c4e8877677ff90805e4a4dcbdef80f4220136. ---------------------------------------- Bug #19467: Some linear_time regexp does not match in linear time https://bugs.ruby-lang.org/issues/19467#change-102502 * Author: tompng (tomoya ishida) * Status: Closed * Priority: Normal * Assignee: make_now_just (Hiroya Fujinami) * ruby -v: ruby 3.3.0dev (2023-02-17T18:10:16Z master c3bae033eb) [x86_64-linux] * Backport: 2.7: DONTNEED, 3.0: DONTNEED, 3.1: DONTNEED, 3.2: DONE ---------------------------------------- `Regexp.linear_time?(/\A.*a.*x\z/) #=> true` but it does not match in linear time ~~~ruby Regexp.linear_time? /\A(.*a.*)x\z/ #=> true /\A(.*a.*)x\z/ =~ 'a'*100000+'y' #=> nil, processing time: 0.016995s Regexp.linear_time? /\A.*a.*x\z/ #=> true /\A.*a.*x\z/ =~ 'a'*100000+'y' #=> nil, processing time: 21.479335s ~~~ -- https://bugs.ruby-lang.org/
participants (3)
-
hsbt (Hiroshi SHIBATA) -
naruse (Yui NARUSE) -
tompng (tomoya ishida)