eden li
10/5/2006 8:47:00 AM
It's a perfectly valid regex that happens to run in exponential time if
the regex engine that tries to run it isn't smart about backtracking
(it appears, in this case, Perl and Ruby 1.9 are, Ruby 1.8 is not, and
Python is smart enough to reject it because it knows its regex engine
can't handle it).
However, the point of my post is not the regex. What I was trying to
find out was why Ruby seems to block threads whenever a regex is
running. I just gave an example that would fit into one line.
I run a batch of regexes on a batch of input on a regular basis, and I
want some way to catch an exponential regex if I happen to accidentally
write one. Right now it appears there's no way to do this in Ruby 1.8.
... or is there?
MonkeeSage wrote:
> eden li wrote:
> > irb(main):001:0> Timeout.timeout 5 do ("a"*300)+"b" =~ /^(a*)*$/ end
>
> Hmm...is that a valid expression? Capture "a" zero or more times, and
> then repeat that capture zero or more times?! What exactly does that
> mean?
>
> perl5 runs it but finds no match:
>
> ("a" x 300) . "b" =~ /^(a*)*$/
>
> python spits out an error:
>
> import re
> s = ("a"*300)+"b"
> re.search(r'^(a*)*$', s)
>
> # ...
> # raise error, v # invalid expression
> # sre_constants.error: nothing to repeat
>
> And ruby 1.9. runs it but finds no match (same as perl).
>
> So I think that the expresion is broken and ruby 1.8 has a bug.
>
> Regards,
> Jordan