Prevent recursion limit when using ".*?xxx"

[dgallion]

BPO	401612
Nosy	@tim-one
Files	None: None

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2001-01-14.23:20:45.000>
created_at = <Date 2000-09-23.04:06:02.000>
labels = ['extension-modules']
title = 'Prevent recursion limit when using ".*?xxx"'
updated_at = <Date 2001-01-14.23:20:45.000>
user = 'https://bugs.python.org/dgallion'

bugs.python.org fields:

activity = <Date 2001-01-14.23:20:45.000>
actor = 'effbot'
assignee = 'effbot'
closed = True
closed_date = None
closer = None
components = ['Extension Modules']
creation = <Date 2000-09-23.04:06:02.000>
creator = 'dgallion'
dependencies = []
files = ['2827']
hgrepos = []
issue_num = 401612
keywords = ['patch']
message_count = 4.0
messages = ['34410', '34411', '34412', '34413']
nosy_count = 3.0
nosy_names = ['tim.peters', 'effbot', 'dgallion']
pr_nums = []
priority = 'normal'
resolution = None
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue401612'
versions = []

[dgallion]

[dgallion]

This pattern fails with sre:
>>> re.match("(?s){.*?}","{"+' '*17000+"}")
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "E:\pythonWinCVS\python\dist\src\lib\sre.py", line 44, in match
    return _compile(pattern, flags).match(string)
RuntimeError: maximum recursion limit exceeded

The same pattern with even a much larger search buffer works fine on 1.52

This patch optimizes the case ".*?" and avoids the recursion limit.

After the patch:
>>> import re
>>> re.findall('ab.*?bc', 'abababbc')
['abababbc']
>>> re.findall('ab??bc', 'abababbc')
['abbc']
>>> re.sub("(?s){.*?}","","{"+' '*19047+"}")
''
>>> re.match("(?s){.*?}","{"+' '*16048+"}")
<SRE_Match object at 007E4490>
>>> import test.test_re
Running tests on re.search and re.match
Running tests on re.sub
Running tests on symbolic references
Running tests on re.subn
Running tests on re.split
Running tests on re.findall
Running tests on re.match
Running tests on re.escape
Pickling a RegexObject instance
Test engine limitations
maximum recursion limit exceeded
Running re_tests test suite
>>>

[tim-one]

Assigned to Fredrik.

dgallion, please resubmit a context diff. Straight diffs aren't accepted (they're too brittle).

[effbot]

I've adapted a variant of this patch.

Not 100% sure this approach works in all cases, but it has survived all tests I've thrown at it.