New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Regular expressions with 0 to 65536 repetitions raises OverflowError #57378
Comments
Regular expressions with 0 to 65536 repetitions and above makes Python crash with a "OverflowError: regular expression code size limit exceeded" exception. Tested and confirmed this with versions 2.7.1 and 3.2.2. C:\Python27>python.exe
Python 2.7.1 (r271:86832, Nov 27 2010, 18:30:46) [MSC v.1500 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> re.search('(?s)\A.{0,65535}test', 'test')
<_sre.SRE_Match object at 0x00B4E4B8>
>>> re.search('(?s)\A.{0,65536}test', 'test')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "C:\Python27\lib\re.py", line 142, in search
return _compile(pattern, flags).search(string)
File "C:\Python27\lib\re.py", line 243, in _compile
p = sre_compile.compile(pattern, flags)
File "C:\Python27\lib\sre_compile.py", line 523, in compile
groupindex, indexgroup
OverflowError: regular expression code size limit exceeded
>>>
C:\Python32>python.exe
Python 3.2.2 (default, Sep 4 2011, 09:51:08) [MSC v.1500 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> re.search('(?s)\A.{0,65535}test', 'test')
<_sre.SRE_Match object at 0x00A6F250>
>>> re.search('(?s)\A.{0,65536}test', 'test')
Traceback (most recent call last):
File "C:\Python32\lib\functools.py", line 176, in wrapper
result = cache[key]
KeyError: (<class 'str'>, '(?s)\\A.{0,65536}test', 0)
During handling of the above exception, another exception occurred:
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "C:\Python32\lib\re.py", line 158, in search
return _compile(pattern, flags).search(string)
File "C:\Python32\lib\re.py", line 255, in _compile
return _compile_typed(type(pattern), pattern, flags)
File "C:\Python32\lib\functools.py", line 180, in wrapper
result = user_function(*args, **kwds)
File "C:\Python32\lib\re.py", line 267, in _compile_typed
return sre_compile.compile(pattern, flags)
File "C:\Python32\lib\sre_compile.py", line 514, in compile
groupindex, indexgroup
OverflowError: regular expression code size limit exceeded
>>> |
I might be missing something, but what's the issue? 65535 is the limit, and doing 65536 gives a clear overflow exception (no crash). |
The quantifiers use 65535 to represent no upper limit, so ".{0,65535}" is equivalent to ".*". For example: >>> re.match(".*", "x" * 100000).span()
(0, 100000)
>>> re.match(".{0,65535}", "x" * 100000).span()
(0, 100000) but: >>> re.match(".{0,65534}", "x" * 100000).span()
(0, 65534) |
So if I understand correctly, the maximum of 65535 repetitions is by design? Have tried a workaround by repeating the repetitions by placing it inside a capturing group, which is perfectly legal with Perl regular expressions: $mystring = "test";
if($mystring =~ m/^(.{0,32766}){0,3}test/s) { print "Yes\n"; }
(32766 being the max repetitions in Perl) Unfortunately, in Python this does not work and raises a "nothing to repeat" sre_constants error: This, however works, which yields 65536 repetitions of DOTALL: In the end this solves my problem sort or less, but requires extra logic in my script and complicates stuff unnecessary. A suggestion might be to make repetitions of repeats possible? |
The limit is an implementation detail. The pattern is compiled into codes which are then interpreted, and it just happens that the codes are (usually) 16 bits, giving a range of 0..65535, but it uses 65535 to represent no limit and doesn't warn if you actually write 65535. There's an alternative regex implementation here: |
Issue bpo-13914 has been marked as a duplicate of this issue. |
Matthew, do you think this should be documented somewhere or that the behavior should be changed (e.g. raising a warning when 65535 is used)? |
Ideally, it should raise an exception (or a warning) because the behaviour is unexpected. |
Now RuntimeError is raised in this case. Here is a patch, which:
|
IMHO, I don't think that MAXREPEAT should be defined in sre_constants.py _and_ SRE_MAXREPEAT defined in sre_constants.h. (In the latter case, why is it in decimal?) I think that it should be defined in one place, namely sre_constants.h, perhaps as: #define SRE_MAXREPEAT ~(SRE_CODE)0 and then imported into sre_constants.py. That'll reduce the chance of an inadvertent mismatch, and it's the C code that's imposing the limit to the number of repeats, not the Python code. |
Because SRE_MAXREPEAT is generated (as all sre_constants.h) from I agree, that SRE_MAXREPEAT is imposed by the C code limitation and it will be |
Patch updated for addressing Ezio's and Matthew's comments. MAXREPEAT now defined in the C code. It lowered to 2G on 32-bit platform to fit repetition numbers into Py_ssize_t. The condition for raising of an exception now more complex: if the repetition number overflows Py_ssize_t it means the same as an infinity bound and in this case an exception is not raised (i.e. it never raised on 32-bit platform). Tests added. |
Patch updated for addressing Ezio's comments. Tests simplified and optimized a little as Ezio suggested. Added a test for implementation dependent behavior (I hope it will gone away at some day). |
Here are patches for 2.7, 3.2 and updated patch for 3.3+ |
New changeset c1b3d25882ca by Serhiy Storchaka in branch '2.7': New changeset 472a7c652cbd by Serhiy Storchaka in branch '3.2': New changeset b78c321ee9a5 by Serhiy Storchaka in branch '3.3': New changeset ca0307905cd7 by Serhiy Storchaka in branch 'default': |
I have committed simplified patches. They don't change an exception type from OverflowError to re.error (but an error message now is more helpful) and don't made the code clever enough to not raise an exception when a repetition number is exceeded sys.maxsize. |
Some third-party modules (e.g. epydoc) refer to sre_constants.MAXREPEAT. |
Thank you for report, Arfrever. I'll see how epydoc uses MAXREPEAT. Maybe it requires larger changes. |
New changeset a80ea934da9a by Serhiy Storchaka in branch '2.7': New changeset a6231ed7bff4 by Serhiy Storchaka in branch '3.2': New changeset 88c04657c9f1 by Serhiy Storchaka in branch '3.3': New changeset 3dd5be5c4794 by Serhiy Storchaka in branch 'default': |
I see (under Windows) the same symptoms as reported for Debian under http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=704084. Python refuses to start. 2.7.4.rc1 Windows 32-bit. |
"Python refuses to start. 2.7.4.rc1 Windows 32-bit." Oh oh. I reopen the issue and set its priority to release blocker. |
"Python refuses to start." is not a very good description.
|
@georg, the referenced Debian issue (http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=704084) already contains the stack. |
And this happens when you simply start Python, not executing any code? Can you start with "python -S", then do "import _sre", and see if it has a _sre.MAXREPEAT attribute? |
IIRC a few days ago I've seen a similar issue and the cause was that they did something wrong while porting the rc to Debian, but I don't remember the details. If I'm not mistaken they also fixed it shortly after. |
Just tested with 2.7.4rc1 32bit on Windows 7; no problem here. I suspect your 2.7.4rc1 install picks up a python27.dll from an earlier version. |
Sorry for passing on my confusion, and thanks for your help! There was indeed an old python.dll lying in one of the places Windows likes to put DLLs. Deleting it resolved the problem. Thanks again and sorry to use your valuable time. |
Thanks for the confirmation! |
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:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: