[Python-bugs-list] [Bug #115696] sre RuntimeError when .*? matches >16K string

[noreply@sourceforge.net]

Bug #115696, was updated on 2000-Sep-29 19:47
Here is a current snapshot of the bug.

Project: Python
Category: Modules
Status: Open
Resolution: None
Bug Group: None
Priority: 6
Summary: sre RuntimeError when .*? matches >16K string

Details: The following code (run under WinNT):

    sre.search('x.*?z', 'x%sx' % ("y" * 16037,))

raises "RuntimeError: maximum recursion limit exceeded".

sre doesn't seem to be able to do a minimal match across more than ~16K characters. I think pcre can match something like 2**32 characters, so this is an area where the sre behavior deviates radically from pcre. I have lots of code that breaks with this limit. Yikes! Can something be done?

While trying to come up with the magic number of characters that cause a minimal match to fail, I ran this interactive session 
(I'm not sure if this means anything or if it's a quirk of the interactive interpreter.)

C:\>python
Python 2.0b2 (#6, Sep 26 2000, 14:59:21) [MSC 32 bit (Intel)] on win32
Type "copyright", "credits" or "license" for more information.

>>> import sre

>>> sre.search('x.*?x', 'x%sx' % ('@'*16035,))
<SRE_Match object at 009D7FC0>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16036,))
<SRE_Match object at 009D7040>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16037,))      <-- first failure
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "D:\Python20\lib\sre.py", line 47, in search
    return _compile(pattern, flags).search(string)
RuntimeError: maximum recursion limit exceeded

>>> sre.search('x.*?x', 'x%sx' % ('@'*16037,))      <-- now it works (?!)
<SRE_Match object at 009D7630>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16038,))
<SRE_Match object at 009D7040>

>>>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16166,))
<SRE_Match object at 009D7A60>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16167,))  <-- here it fails again
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "D:\Python20\lib\sre.py", line 47, in search
    return _compile(pattern, flags).search(string)
RuntimeError: maximum recursion limit exceeded

>>> sre.search('x.*?x', 'x%sx' % ('@'*16167,))  <-- continues to fail
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "D:\Python20\lib\sre.py", line 47, in search
    return _compile(pattern, flags).search(string)
RuntimeError: maximum recursion limit exceeded



Follow-Ups:

Date: 2000-Sep-30 21:19
By: gvanrossum

Comment:
Any comments, Fredrik???
-------------------------------------------------------

For detailed info, follow this link:
http://sourceforge.net/bugs/?func=detailbug&bug_id=115696&group_id=5470