Bug #5038: Ruby 1.9.2 stops on some Regular Expressions

• Status: Rejected
• Assignee: -
• Target version: -
• ruby -v: ruby 1.9.2p290 (2011-07-09 revision 32553) [i686-linux]

[docolabs (Bob Ambartsumov)]

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

[JEG2 (James Gray)]

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.

[naruse (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

I put #{} into your Issue and got nil

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

----- Original Message -----
From: "Yui NARUSE" [e-mail]
To: [e-mail]
Sent: Sunday, July 17, 2011 10:47:13 AM
Subject: [ruby-core:38142] [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