This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: finditer stuck in infinite loop
Type: Stage:
Components: Regular Expressions Versions: Python 2.5
process
Status: closed Resolution: duplicate
Dependencies: Superseder:
Assigned To: niemeyer Nosy List: Rhamphoryncus, georg.brandl, migues, niemeyer
Priority: normal Keywords:

Created on 2007-02-16 19:11 by migues, last changed 2022-04-11 14:56 by admin. This issue is now closed.

Files
File name Uploaded Description Edit
INFINITELOOP.ZIP migues, 2007-02-16 19:11
Messages (4)
msg31282 - (view) Author: Milan (migues) Date: 2007-02-16 19:11
Using iterator on Match Object results in infinite unbreakable loop. Attached is sample script and sample file.

My OS: Win XP Pro.

msg31283 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2007-02-22 10:44
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..
msg31284 - (view) Author: Adam Olsen (Rhamphoryncus) Date: 2007-02-22 10:45
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))
msg31285 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2007-02-22 11:59
I'd say this is a duplicate of #1662581.
History
Date User Action Args
2022-04-11 14:56:22adminsetgithub: 44589
2007-02-16 19:11:18miguescreate