From: Reto Schuettel <reto-ruby-core@...>
Date: 2006-07-19T20:23:45+09:00
Subject: Regular-Expressions Problem/Bug

--tKW2IUtsqtDRztdT
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit

Hi 

I've experienced a rather strange problem with regular-expressions
recently. I used a RE to capture some input from a cisco-device, like:

 1. Everything up to...   (.*)
 2. ... Beginning of the prompt  'switch-123'
 3. ... variable middle part of the prompt [a-zA-Z0-9_-]+
 4. ...  And a '#' at the end of the prompt #

      1___2__3_4
-->  /(.*)ABC.*#/

Except to one case this RE worked quite well: 

| length = 20000
| 
| # "x" * length + "ABC" + "y" * 10 + "#" 
| -> matches immediately, return true
| 
| # "x" * length + "XYZ" + "y" * 10 + "#" 
| -> matches immediately, return false. Please note that the tag 'ABC'
| isn't in the string
| 
| # "x" * length + "ABC" + "y" * 10 
| -> takes forever (if LENGHT is big enough), as you can see here the tag
| 'ABC' occurred, but the ending of the second variable part hasn't.

After some experiments I could even simplify the problem:
LENGTH = 20000
text = "x" * LENGTH + "ABC" + "y" * 10
re = /(.*)ABC[y]#/
-> takes forever...

I'm not sure if this is a problem of the ruby RE-implementation 
or if this a problem of RE in general (Keyword: back-tracking). Some
tests with Perl showed to me that Perl usually reacts better to such
regular-expressions.

Attached is a short test-program.

Regards,
Reto Sch�ttel

--tKW2IUtsqtDRztdT
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: attachment; filename="re.rb"

LENGTH = 20000

var1 = "x" * LENGTH + "ABC" + "y" * 10 + "#"
var2 = "x" * LENGTH + "XYZ" + "y" * 10 
var3 = "x" * LENGTH + "ABC" + "y" * 10 

re = /(.*)ABC.*#/

[var1, var2, var3].each do |text|
  puts re =~ text ? "true" : "false"
end


--tKW2IUtsqtDRztdT--