From: Bill Kelly <billk@...>
Date: 2006-05-24T17:13:24+09:00
Subject: Re: String.scan hangs in some cases?

From: "Robert Klemme" <shortcutter@googlemail.com>
> 2006/5/24, Bill Kelly <billk@cts.com>:
> >
> > 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.

Thanks :)  We haven't seen the OP's regexp yet; I was just
offering the above as an example of what can cause the
hanging he described.


Regards,

Bill