From: Bill Kelly <billk@...>
Date: 2002-09-18T09:15:24+09:00
Subject: Re: Regular expression bug, or feature?

> I've got a strange feeling that this is one of those little bits of
> knowledge known to everybody except people who think they know
> something about regular expressions knows... but here goes:
> 
> I have a regular expression and a string which cause Ruby to hang. 
> Try this:
> 
> src='<hosted class="com.firsthop.mg.gui.Servlet" product="TestSuite"
> classpath'
> src =~ /^<((?:[\w:][-\w\d.]*:)?[\w:][-\w\d.]*)\s*((((["']).*?\5)|[^\/'">]*)*?)(\/)?>/mu
> 
> Notice that there's a CR between %q{"TestSuite"} and %q{classpath}.
> 
> This hangs on at least Ruby 1.6.5 and 1.6.7 -- one of those 100% CPU,
> never return hangs.

Try: src=%Q{<h c="c" p="T"\nc}

Ruby should process it almost instantly...

Then try: src=%Q{<h c="c" p="T"\nccccccccccccccccc}

It may take several seconds...

Append a few more characters and it'll take a loooooooonng time ;)

> Is this a known problem with Ruby, or should I file a bug report?
> 
> I've checked this in Perl; it doesn't match, of course, but neither
> does it hang.

I think your nested (...*)*'s are causing exponential backtracking 
trying to find a match.  (Or in the case of the non-greedy one, "forward-
tracking" :)

Perl, I've read, incorporates a number of optimizations to try to
recognize and shortcut patterns like that... But one can outwit its
shortcuts presumably pretty easily.

According to Pickaxe, Ruby supports the (?>) extension... It's useful
in construction expressions where you want to prevent backtracking from
occurring when parts of the expression don't match.

HTH,

Bill