[Python-bugs-list] [ python-Bugs-405676 ] Quasi hang in RE code

[noreply@sourceforge.net]

Bugs item #405676, was opened at 2001-03-03 09:45
You can respond by visiting: 
http://sourceforge.net/tracker/?func=detail&atid=105470&aid=405676&group_id=5470

Category: Regular Expressions
Group: None
>Status: Closed
>Resolution: Works For Me
Priority: 5
Submitted By: Nobody/Anonymous (nobody)
Assigned to: Fredrik Lundh (effbot)
Summary: Quasi hang in RE code

Initial Comment:
When running the attached .py file with the attached
input file, python will "hang" (after 10 seconds, it
finally does return on my PII-400, but something is
obviously broken) when returning from chop_chunks. GDB
revealed this stack trace, pointing to re code.

The input

(gdb) bt
#0  0x8074b7f in sre_match (state=0xbfffebc8,
pattern=0x8252538, level=3)
    at Modules/_sre.c:671
#1  0x807523f in sre_match (state=0xbfffebc8,
pattern=0x8252536, level=2)
    at Modules/_sre.c:1043
#2  0x8075074 in sre_match (state=0xbfffebc8,
pattern=0x825251a, level=1)
    at Modules/_sre.c:947
#3  0x80754de in sre_search (state=0xbfffebc8,
pattern=0x8252510)
    at Modules/_sre.c:1200
#4  0x8076bb2 in pattern_search (self=0x82524f0,
args=0x822874c, kw=0x0)
    at ./Modules/_sre.c:1616
#5  0x8058a54 in call_cfunction (func=0x823a690,
arg=0x822874c, kw=0x0)
    at Python/ceval.c:2731
#6  0x805898c in call_object (func=0x823a690,
arg=0x822874c, kw=0x0)
    at Python/ceval.c:2703
#7  0x8059100 in do_call (func=0x823a690,
pp_stack=0xbffff04c, na=1, nk=0)
    at Python/ceval.c:3014

This is with

Python 2.1b1 (#1, Mar  3 2001, 12:47:09)
[GCC 2.96 20000731 (Red Hat Linux 7.0)] on linux2
Type "copyright", "credits" or "license" for more
information.


----------------------------------------------------------------------

>Comment By: Fredrik Lundh (effbot)
Date: 2001-07-03 12:56

Message:
Logged In: YES 
user_id=38376

Under 2.1 final, this runs in ~0.3 seconds on my old P2.
Using pre instead of sre cuts this to ~0.2 seconds.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2001-03-03 10:04

Message:
Logged In: YES 
user_id=31435

Assigned to effbot.

Anonymous submitter, you should be aware that the usual 
outcome for one of these is that the regexp turns out to 
have been written in a way that *requires* exponential time 
in some cases.  See Friedl's "Master Regular Expressions" 
(O'Reilly) for details.

Given that that is the usual case, people will be more 
motivated to look at this if you could whittle it down to a 
minimal example (one regexp, one string).

----------------------------------------------------------------------

You can respond by visiting: 
http://sourceforge.net/tracker/?func=detail&atid=105470&aid=405676&group_id=5470