Project

General

Profile

Actions

Bug #19467

closed

Some linear_time regexp does not match in linear time

Added by tompng (tomoya ishida) over 1 year ago. Updated over 1 year ago.

Status:
Closed
Target version:
-
ruby -v:
ruby 3.3.0dev (2023-02-17T18:10:16Z master c3bae033eb) [x86_64-linux]
[ruby-core:112594]

Description

Regexp.linear_time?(/\A.*a.*x\z/) #=> true but it does not match in linear time

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

Updated by hsbt (Hiroshi SHIBATA) over 1 year ago

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

Updated by make_now_just (Hiroya Fujinami) over 1 year ago

  • Status changed from Assigned to Closed

Applied in changeset git|e22c4e8877677ff90805e4a4dcbdef80f4220136.


[Bug #19467] correct cache points and counting failure on OP_ANYCHAR_STAR_PEEK_NEXT (#7454)

Actions #3

Updated by hsbt (Hiroshi SHIBATA) over 1 year ago

  • Backport changed from 2.7: UNKNOWN, 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN to 2.7: DONTNEED, 3.0: DONTNEED, 3.1: DONTNEED, 3.2: REQUIRED

Updated by naruse (Yui NARUSE) over 1 year ago

  • 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.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0