From: Florian Gross <florgro@...>
Date: 2006-07-01T22:43:25+09:00
Subject: Re: Regex Comparison Causing Massive Memory Usage

Xavier Noria wrote:

>> "(?:#{us_ascii}|#{twobytes_utf8}|#{threebytes_utf8}|#{fourbytes_utf8})"
>>  UTF8Regexp = Regexp.new("\\A#{character_utf8}*\\z", nil, "NONE")
> 
> Yeah, looks potentially problematic at first sight.
> 
> In each single byte the engine has up to 3 possible backtracking points 
> that have to be remembered. I don't know details about the UTF-8 
> encoding, but if the alternatives are not exclusive you may wrongly 
> match #{twobytes_utf8} in the first byte to discover at the end of the 
> string the match fails. In that case the engine has to backtrack a 
> zillion times back and forth until it undoes the walked way (potentially 
> a huge tree) and arrives to switch to #{threebytes_utf8} at the 
> beginning, which in turn may fail, etc.

I think in this case you can get away by using (?>...) instead of 
(?:...) in character_utf8. Backtracking makes no sense, because the 
choice is supposed to be unambiguous on a per-character basis. (?>...) 
just tells the RE engine not to backtrack inside. It will skip right 
over the construct.

-- 
http://flgr.0x42.net/