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

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


Regards,

Bill