Bug #5038

Ruby 1.9.2 stops on some Regular Expressions

Added by Bob Ambartsumov almost 4 years ago. Updated almost 4 years ago.

[ruby-core:38137]
Status:Rejected
Priority:Normal
Assignee:-
ruby -v:ruby 1.9.2p290 (2011-07-09 revision 32553) [i686-linux] Backport:

Description

Code to reproduce:

n = 50
st = "Phone" + " "n + "Fax"
st.match(/(.+\s)
email/i)

nil is expected
The execution stops on match, or enters some endless loop. CPU load is high.
Works as expected when not using /i (case-insensitive)
Works as expected on smaller n (<20)
Takes about 5 seconds to execute on n=30

History

#1 Updated by James Gray almost 4 years ago

Your regular expression is exponential, with a repeater (+) inside a repeater (*). It requires the regex engine to do a ton of backtracking, creating the seemingly endless loop. A lot of languages would choke on an expression like that.

#2 Updated by Yui NARUSE almost 4 years ago

  • Status changed from Open to Rejected

It is limitation of the spec which uses NFA regexp engine.
see also http://swtch.com/~rsc/regexp/regexp1.html

#3 Updated by Anonymous almost 4 years ago

I put #{} into your Issue and got nil

n = 50
st = "Phone" + " "#{n} + "Fax"
st.match(/(.+\s)
email/i)

----- Original Message -----
From: "Yui NARUSE" naruse@airemix.jp
To: ruby-core@ruby-lang.org
Sent: Sunday, July 17, 2011 10:47:13 AM
Subject: [Ruby 1.9 - Bug #5038][Rejected] Ruby 1.9.2 stops on some Regular Expressions

Issue #5038 has been updated by Yui NARUSE.

Status changed from Open to Rejected

It is limitation of the spec which uses NFA regexp engine.
see also http://swtch.com/~rsc/regexp/regexp1.html


Bug #5038: Ruby 1.9.2 stops on some Regular Expressions
http://redmine.ruby-lang.org/issues/5038

Author: Bob Ambartsumov
Status: Rejected
Priority: Normal
Assignee:
Category:
Target version:
ruby -v: ruby 1.9.2p290 (2011-07-09 revision 32553) [i686-linux]

# Code to reproduce:
n = 50
st = "Phone" + " "n + "Fax"
st.match(/(.+\s)
email/i)

nil is expected
The execution stops on match, or enters some endless loop. CPU load is high.
Works as expected when not using /i (case-insensitive)
Works as expected on smaller n (<20)
Takes about 5 seconds to execute on n=30

--
http://redmine.ruby-lang.org

Also available in: Atom PDF