Bug #6366: Regex freezes Ruby

• Status: Rejected
• Assignee: -
• Target version: Ruby 1.8.7
• ruby -v: ruby 1.8.7 (2011-06-30 patchlevel 352) [i686-darwin11.3.0]

[vertis (Luke Chadwick)]

I stumbled across a weird error on Ruby 1.8.7p352, where String.match locks up:

"#^(?:export)?\s*(\w+)=(.)".match(/^(?:export[\s]+)?([\w_])+?=(.*)/)

I had, apparently, pasted a regular expression into a file(bash) that I was testing, and commented it out. I'm assuming I did this to clear my clipboard. I was then running the following match on each line in the file & consistently had the ruby interpreter lockup (not even Ctrl-C was working, though Ctrl-Z did).

I have replicated this on both MacOS (homebrew) and CentOS 6 1.8.7p352, but this doesn't happen in Ruby 1.9.2p0.

[nobu (Nobuyoshi Nakada)]

• Status changed from Open to Rejected

=begin
It's due to the bad regexp.

You should not repeat repetitive operators (({"([\w_]*)+?"})), which causes combinatorial explosion.

Try with (({"([\w_]+?)"})).
=end

[vertis (Luke Chadwick)]

Sure, that works. You're absolutely correct about my regex error.

However, I still think it's a bug. The behaviour should be to fail with an Exception not lockup indefinitely.

[shyouhei (Shyouhei Urabe)]

No, sorry. You cant detect whether your program locks up.

http://en.wikipedia.org/wiki/Halting_problem

[vertis (Luke Chadwick)]

Right, but you could detect bad patterns in the regex like the double repetition. How does Ruby 1.9 NOT freeze?

[nobu (Nobuyoshi Nakada)]

Oniguruma, the regex engine in 1.9, optimizes it in its parser.
But 1.8 doesn't, and has no future.