Hangup in regexp-matching

Hangup in regexp-matching

[Marek Kubica]

[-- Attachment #1: Type: text/plain, Size: 900 bytes --]

Hi,

I do a bit regexp-matching in my log analyzer but found out that the
Regexp engine chokes on some input (see attached file). It just takes
100% CPU time and never returns.

I thought that I might have hit some obscure O(2^n) problem of FAs, I
tried the same thing in Python and it worked immediately:

>>> s = "20:15 < foobar> \"Bei den Programmiersprachen rechnet er für
die nächsten zehn Jahre mit keinen neuen Entwicklungen, da es mit
zu viel Aufwand verbunden sei, neue Sprachen in den Markt zu
drücken. So wird die Programmierwelt auch in zehn Jahren noch aus
Java und C++ bestehen. Den funktionalen Sprachen erteilt er eine
Absage: \"Ihr Problem ist, dass sich damit zwar komplizierte
Abläufe einfach darstellen lassen, dass aber leider einfache Dinge
zu"
>>> import re 
>>> re.findall("[A-~]{1,16}\\+\\+", s)
['C++']

Any ideas what is happening?

regards,
Marek

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: regexhang.scm --]
[-- Type: text/x-scheme, Size: 567 bytes --]

(use-modules (ice-9 regex))
(define s "20:15 < foobar> \"Bei den Programmiersprachen rechnet er für die nächsten zehn Jahre mit keinen neuen Entwicklungen, da es mit zu viel Aufwand verbunden sei, neue Sprachen in den Markt zu drücken. So wird die Programmierwelt auch in zehn Jahren noch aus Java und C++ bestehen. Den funktionalen Sprachen erteilt er eine Absage: \"Ihr Problem ist, dass sich damit zwar komplizierte Abläufe einfach darstellen lassen, dass aber leider einfache Dinge zu")
(define add (make-regexp "[A-~]{1,16}\\+\\+"))
(list-matches add s)

Re: Hangup in regexp-matching

[Linas Vepstas]

Wild guess:  a unicode/utf-8 problem?

Which version of guile is this?

--linas

2010/12/18 Marek Kubica <marek@xivilization.net>:
> Hi,
>
> I do a bit regexp-matching in my log analyzer but found out that the
> Regexp engine chokes on some input (see attached file). It just takes
> 100% CPU time and never returns.
>
> I thought that I might have hit some obscure O(2^n) problem of FAs, I
> tried the same thing in Python and it worked immediately:
>
>>>> s = "20:15 < foobar> \"Bei den Programmiersprachen rechnet er für
> die nächsten zehn Jahre mit keinen neuen Entwicklungen, da es mit
> zu viel Aufwand verbunden sei, neue Sprachen in den Markt zu
> drücken. So wird die Programmierwelt auch in zehn Jahren noch aus
> Java und C++ bestehen. Den funktionalen Sprachen erteilt er eine
> Absage: \"Ihr Problem ist, dass sich damit zwar komplizierte
> Abläufe einfach darstellen lassen, dass aber leider einfache Dinge
> zu"
>>>> import re
>>>> re.findall("[A-~]{1,16}\\+\\+", s)
> ['C++']
>
> Any ideas what is happening?
>
> regards,
> Marek
>

Re: Hangup in regexp-matching

[Andy Wingo]

On Mon 20 Dec 2010 20:03, Linas Vepstas <linasvepstas@gmail.com> writes:

> Wild guess:  a unicode/utf-8 problem?

I think this is the case, as the regexp completes immediately for me
without problems in 1.9.14 / git.

> Which version of guile is this?

This problem should be present only in the 1.9 series, and only up to
1.9.13. 1.9.14 has it fixed i think.

Andy
-- 
http://wingolog.org/