From: Hugh Sasse <hgs@...>
Date: 2006-07-19T20:49:45+09:00
Subject: Re: Regular-Expressions Problem/Bug

---559023410-1804928587-1153309524=:1443
Content-Type: MULTIPART/MIXED; BOUNDARY="-559023410-1804928587-1153309524=:1443"

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

---559023410-1804928587-1153309524=:1443
Content-Type: TEXT/PLAIN; CHARSET=X-UNKNOWN
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Wed, 19 Jul 2006, Reto Schuettel wrote:

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

so you need the brackets....
>=20
        [...]
>  4. ...  And a '#' at the end of the prompt #

Is the prompt at the end of what you are looking for, or does text
follow the prompt?
        [...]
> | # "x" * length + "ABC" + "y" * 10=20
> | -> 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.
>=20
> After some experiments I could even simplify the problem:
> LENGTH =3D 20000
> text =3D "x" * LENGTH + "ABC" + "y" * 10
> re =3D /(.*)ABC[y]#/
> -> takes forever...

which is similar.
>=20
> I'm not sure if this is a problem of the ruby RE-implementation=20
> or if this a problem of RE in general (Keyword: back-tracking). Some

Yes, it's backtracking.  Hence my question above.  Try
  re =3D /(.*)ABC[y]#$/
if the prompt is the last thing you are looking for.  That will
seriously help, because it is saying "If there's no # at the end of
the string. give up now."

that [y]# looks odd to me -- do you mean
  re =3D /(.*)ABC[y]*#$/
And you might want to try out *? since you have 2 stars in that case.
That would make it non-greedy.  And having a character class [] with=20
only one char in it looks odd too.  Maybe you need a non-capturing bracket
instead =20
  re =3D /(.*?)ABC(?:y*?)#$/

> tests with Perl showed to me that Perl usually reacts better to such
> regular-expressions.

Concrete examples and timings might be of use to the regexp developers,
but a statement like the above makes it hard to test improvements.
I don't develop the RE code in Ruby, so you'll need to wait for=20
someone who does to show interest in this detail.
>=20
> Attached is a short test-program.
>=20
> Regards,
> Reto Sch=FCttel
>=20
---559023410-1804928587-1153309524=:1443--
---559023410-1804928587-1153309524=:1443--