From: Robert Klemme <shortcutter@...>
Date: 2006-05-24T16:09:32+09:00
Subject: Re: String.scan hangs in some cases?

2006/5/24, Bill Kelly <billk@cts.com>:
> From: "Daniel Berger" <djberg96@gmail.com>
> > Wes Gamble wrote:
> >> Has anyone ever see a call to String.scan (the "regular" form, not the
> >> block form) just hang when processing a string?
> >>
> >> If so, any insight into how that might happen?
> >>
> >> Thanks,
> >> Wes
> >>
> >
> > Got an example you can share that demonstrates the problem?
> >
> > Maybe the string is huge?  Maybe there's a recursive lookup happening of
> > some kind?  Dunno without more detail.
>
> I'm guessing exponential backtracking when the expression doesn't match.
>
> For ex:
>
> x = "x" * 1000
> x << "ab"
> x =~ /x*x*a/       # matches quickly
> x =~ /x*x*b/       # "hangs" trying exponential combinations with backtracking

Yes, that's a property of NFA based regular expression engines.  Some
patterns have awful runtime characteristics because of the
backtracking.  Without looking too close at your patter I guess in
this case it's caused by having "x*" twice in your RX - not very
useful anyway.  If you are interested in more detail I recommend
reading "Mastering Regular Expressions":

http://www.amazon.com/gp/product/0596002890/

Kind regards

robert

-- 
Have a look: http://www.flickr.com/photos/fussel-foto/