https://bugs.ruby-lang.org/https://bugs.ruby-lang.org/favicon.ico?17113305112014-04-02T22:21:36ZRuby Issue Tracking SystemRuby master - Bug #9694: Bad regexp hangs rubyhttps://bugs.ruby-lang.org/issues/9694?journal_id=460452014-04-02T22:21:36Zrafaelfranca (Rafael França)rafael@franca.dev
<ul></ul><p>I tried to reproduce with your script and could not:</p>
<pre><code>$ ruby -v
ruby 2.1.1p76 (2014-02-24 revision 45161) [x86_64-darwin13.0]
$ cat foo.rb
str = ('a' * ARGV[0].to_i) + '?'
re = /(\w)$/
re.match(str)
$ time ruby foo.rb 14
real 0m0.134s
user 0m0.075s
sys 0m0.050s
$ time ruby foo.rb 15
real 0m0.145s
user 0m0.082s
sys 0m0.054s
$ time ruby foo.rb 16
real 0m0.137s
user 0m0.076s
sys 0m0.052s
$ time ruby foo.rb 50
real 0m0.142s
user 0m0.080s
sys 0m0.053s
</code></pre>
<p>What is the environment you are running?</p> Ruby master - Bug #9694: Bad regexp hangs rubyhttps://bugs.ruby-lang.org/issues/9694?journal_id=460462014-04-02T22:34:43Zgergoerdosi (Gergo Erdosi)gergo@gergoerdosi.com
<ul></ul><p>For some reason the regex is not displayed correctly. I'm able to reproduce the reported issue (see the correct regex below):</p>
<pre><code>$ cat test.rb
str = ('a' * ARGV[0].to_i) + '?'
re = /(\w*)*$/
re.match(str)
$ time ruby test.rb 14
real 0m1.179s
user 0m1.128s
sys 0m0.004s
$ time ruby test.rb 15
real 0m3.568s
user 0m3.419s
sys 0m0.020s
$ time ruby test.rb 16
real 0m10.767s
user 0m10.276s
sys 0m0.067s
</code></pre> Ruby master - Bug #9694: Bad regexp hangs rubyhttps://bugs.ruby-lang.org/issues/9694?journal_id=460482014-04-03T02:42:16Zshyouhei (Shyouhei Urabe)shyouhei@ruby-lang.org
<ul></ul><p>Ruby's regexp engine is NP-complete. It's ultimately impossible to guarantee<br>
regexp matches to run fast (if you don't think so please send us a proof). It<br>
might be possible to warn your specific bad regexp, but in general it's also<br>
impossible to tell which regexp is bad and which isn't. That's the Halintg<br>
problem <a href="http://en.wikipedia.org/wiki/Halting_problem" class="external">http://en.wikipedia.org/wiki/Halting_problem</a> .</p>
<p>So, in short, there is (at least believed to be) no ultimate solution. All what<br>
might be possible is to find a reasonable compromise. For instance python does<br>
not detect that shorter one:</p>
<pre><code class="python syntaxhl" data-language="python"><span class="n">zsh</span> <span class="o">%</span> <span class="n">python</span>
<span class="n">Python</span> <span class="mf">2.7</span><span class="p">.</span><span class="mi">5</span><span class="o">+</span> <span class="p">(</span><span class="n">default</span><span class="p">,</span> <span class="n">Feb</span> <span class="mi">27</span> <span class="mi">2014</span><span class="p">,</span> <span class="mi">19</span><span class="p">:</span><span class="mi">37</span><span class="p">:</span><span class="mi">08</span><span class="p">)</span>
<span class="p">[</span><span class="n">GCC</span> <span class="mf">4.8</span><span class="p">.</span><span class="mi">1</span><span class="p">]</span> <span class="n">on</span> <span class="n">linux2</span>
<span class="n">Type</span> <span class="sh">"</span><span class="s">help</span><span class="sh">"</span><span class="p">,</span> <span class="sh">"</span><span class="s">copyright</span><span class="sh">"</span><span class="p">,</span> <span class="sh">"</span><span class="s">credits</span><span class="sh">"</span> <span class="ow">or</span> <span class="sh">"</span><span class="s">license</span><span class="sh">"</span> <span class="k">for</span> <span class="n">more</span> <span class="n">information</span><span class="p">.</span>
<span class="o">>>></span> <span class="kn">import</span> <span class="n">re</span>
<span class="o">>>></span> <span class="n">re</span><span class="p">.</span><span class="nf">compile</span><span class="p">(</span><span class="sa">r</span><span class="sh">'</span><span class="s">(\w*)*$</span><span class="sh">'</span><span class="p">)</span>
<span class="o"><</span><span class="n">_sre</span><span class="p">.</span><span class="n">SRE_Pattern</span> <span class="nb">object</span> <span class="n">at</span> <span class="mh">0x1dee030</span><span class="o">></span>
<span class="o">>>></span>
</code></pre> Ruby master - Bug #9694: Bad regexp hangs rubyhttps://bugs.ruby-lang.org/issues/9694?journal_id=460642014-04-03T15:59:38Zmxposed (Nikolay Markov)nikolai.markov@icloud.com
<ul></ul><p>Rafael, i'm sorry, the bad regexp is not displaying properly, something is obviously wrong with my formatting. Gergo reproduced it same as i have it.</p>
<p>Urabe, do you know how Perl does that? Also, i'll be grateful for the link to regexp sources in ruby</p> Ruby master - Bug #9694: Bad regexp hangs rubyhttps://bugs.ruby-lang.org/issues/9694?journal_id=460712014-04-04T11:19:56Zshyouhei (Shyouhei Urabe)shyouhei@ruby-lang.org
<ul></ul><p>Nikolay Markov wrote:</p>
<blockquote>
<p>Urabe, do you know how Perl does that? Also, i'll be grateful for the link to regexp sources in ruby</p>
</blockquote>
<p>Don't know anything about perl's. Ruby's regexp engine is called Onigmo: <a href="https://github.com/k-takata/Onigmo" class="external">https://github.com/k-takata/Onigmo</a></p> Ruby master - Bug #9694: Bad regexp hangs rubyhttps://bugs.ruby-lang.org/issues/9694?journal_id=793122019-07-11T22:27:04Zjeremyevans0 (Jeremy Evans)merch-redmine@jeremyevans.net
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li></ul>