Re: [ ruby-Bugs-1156 ] Infinite loop in gsub

Hi --

On Sun, 5 Dec 2004 [e-mail] wrote:

> Bugs item #1156, was opened at 2004-12-04 20:53
> You can respond by visiting: 
> http://rubyforge.org/tracker/?func=detail&atid=1698&aid=1156&group_id=426
> 
> Category: None
> Group: None
> Status: Open
> Resolution: None
> Priority: 5
> Submitted By: Andrew Eland (andreweland)
> Assigned to: Nobody (None)
> Summary: Infinite loop in gsub
> 
> Initial Comment:
> In certain situations, gsub gets stuck in an endless loop. Running the attached script reproduces the problem.
> 

I believe it isn't actually infinite, just very, very long.  It's also
not gsub-specific.  Try the following and you'll see how the time
mounts up:

  require 'benchmark'
  include Benchmark
  
  str = "abcdefghijklmnopqrstuvwxyz"
  
  bm do |x|
    str.scan(/./).reverse.each do |char|
      x.report { /(.*)+#{char}/.match(str).to_a }
    end
  end

I'm *almost* up to the task of tracking the backtracking... :-)  but
the general idea is that the regex engine has to travel to the end of
the string, fail, backtrack, and so on.  This takes less time for the
characters near the end of the string, and much longer for those near
the beginning.  

I think this is what's happening in your example.  


David

-- 
David A. Black
[e-mail]