From: Daniel Martin <martin@...>
Date: 2007-01-26T05:23:31+09:00
Subject: Re: Regexp and string halts ruby

Ricardo Ramalho <ricardo-g-ramalho@telecom.pt> writes:

> /^((?:\s*.+[;=][^,]*,?)+)$/ =~ " pid=934, time=478611,
> command=TMQFORWARD, args=-C dom=ccaApp -g 650 -i 4278 -u pthp68 -U
> /home1/eclprp/logs/tx/ULOG -m 0 -- -i 10 -t 600 -q AW02,AW02S TMQFORWARD
> -C dom=ccaApp -g 650 -i 4278 -u pthp68 -U /home1/eclprp/logs/tx/ULOG -m
> 0 -- -i 10 -t 600 -q AW02, "

It is possible to write a regular expression that takes exponential
time to confirm that there's no match.  This is not really anything
too new.  You can do similar things to Python and to Perl too,
although with Perl you have to try significantly harder since 5.6.
(There's some code in there that detects certain exponential-time
matching patterns and adjusts behavior)

You can simplify your example to:

  /(?:.+=[^,]*,?)+$/ =~ "x=x,x" * 12

Which will complete on my machine, albeit very slowly.  Increasing the
number much more will get you what appears to be a hang.  

Note that if the regular expression you gave were to match the string,
then this regular expression should also match:

/(?:\s*.+[;=][^,]*,?)$/

Consider this a "prerequisite" to your match - if this doesn't match,
then there's no way your full expression could match your input.  In
your code, one thing you could do is check against this short
expression first, and only if that matches then check against the long
expression.

However, it may be much more productive simply to rewrite your
expression as:

/^((?:\s*.+[;=][^,]*,)*(?:\s*.+[;=][^,]*,?))$/

I've expanded out your (?:blah)+ into a (?:blah)*(?:blah), and (most
importantly!) I've removed the "?" after the "," in the first clause,
on the assumption that the comma is optional only on the last piece in
the line.  With that change, ruby no longer goes nuts trying to match
this regular expression.

-- 
s=%q(  Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1]       )
       puts "s=%q(#{s})",s.map{|i|i}[1]