Bug #5038
closedRuby 1.9.2 stops on some Regular Expressions
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
Updated by JEG2 (James Gray) almost 13 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.
Updated by naruse (Yui NARUSE) almost 13 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
Updated by Anonymous almost 13 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-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