[ python-Bugs-1661745 ] finditer stuck in infinite loop

[SourceForge.net]

Bugs item #1661745, was opened at 2007-02-16 19:11
Message generated for change (Comment added) made by gbrandl
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1661745&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Regular Expressions
Group: Python 2.5
>Status: Closed
>Resolution: Duplicate
Priority: 5
Private: No
Submitted By: Milan (migues)
Assigned to: Gustavo Niemeyer (niemeyer)
Summary: finditer stuck in infinite loop

Initial Comment:
Using iterator on Match Object results in infinite unbreakable loop. Attached is sample script and sample file.

My OS: Win XP Pro.



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

>Comment By: Georg Brandl (gbrandl)
Date: 2007-02-22 11:59

Message:
Logged In: YES 
user_id=849994
Originator: NO

I'd say this is a duplicate of #1662581.

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

Comment By: Adam Olsen (rhamphoryncus)
Date: 2007-02-22 10:45

Message:
Logged In: YES 
user_id=12364
Originator: NO

Nope, won't let me attach a file.  Pasted instead:

#!/usr/bin/env python
import re
from timeit import Timer

reexpr = re.compile(r"(.+\n?)+?((\.\n)|(\n\n))")

def test(count):
    text = '%s.%s.' % ('x' * count, 'x' * count)
    for m in reexpr.finditer(text):
        pass

for count in range(21):
    print '%2i: %20.10f' % (count,
        Timer('test(%i)' % count, "from __main__ import
test").timeit(number=1))


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

Comment By: Adam Olsen (rhamphoryncus)
Date: 2007-02-22 10:44

Message:
Logged In: YES 
user_id=12364
Originator: NO

I've rewritten the test case.  It's not an infinite loop but rather
exponential runtime based on the length of the string.  Matching on a
string of 'x.x.', increasing the length of the left x or right x by one
doubles the runtime.  Increasing both quadruples it.

 0:         0.0000350475
 1:         0.0000259876
 2:         0.0000669956
 3:         0.0002369881
 4:         0.0009140968
 5:         0.0038359165
 6:         0.0148119926
 7:         0.0732769966
 8:         0.2570281029
 9:         0.9819128513
10:         3.9152498245
11:        16.4304330349
12:        64.8596510887
13:       264.2261950970

I'm not a re guru though, so I don't know if this is a real bug or just
one of those special cases re is prone to.

Now I just need to find out how to attach my file, SF doesn't want to let
me..

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

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