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

[nobody]

Bugs #405676, was updated on 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: Open
Priority: 5
Submitted By: Nobody/Anonymous
Assigned to: Fredrik Lundh
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: Tim Peters
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