Repository navigation
Medium size regexp crashes python #45501
Description
| BPO | 1160 |
|---|---|
| Nosy | @gvanrossum, @akuchling, @pitrou, @ezio-melotti, @serhiy-storchaka |
| Files |
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 2012-11-20.21:39:45.145>
created_at = <Date 2007-09-13.08:00:56.917>
labels = ['expert-regex', 'easy', 'type-bug']
title = 'Medium size regexp crashes python'
updated_at = <Date 2012-11-20.21:39:45.144>
user = 'https://bugs.python.org/ostkamp'bugs.python.org fields:
activity = <Date 2012-11-20.21:39:45.144>
actor = 'pitrou'
assignee = 'none'
closed = True
closed_date = <Date 2012-11-20.21:39:45.145>
closer = 'pitrou'
components = ['Regular Expressions']
creation = <Date 2007-09-13.08:00:56.917>
creator = 'ostkamp'
dependencies = []
files = ['27957', '27958', '27959']
hgrepos = []
issue_num = 1160
keywords = ['patch', 'easy']
message_count = 21.0
messages = ['55885', '55916', '56098', '59775', '62143', '65651', '72319', '73781', '94192', '94233', '95187', '95221', '95320', '99151', '163863', '164372', '164391', '175382', '176029', '176030', '176031']
nosy_count = 17.0
nosy_names = ['gvanrossum', 'effbot', 'akuchling', 'pitrou', 'ostkamp', 'rsc', 'timehorse', 'mathieu.clabaut', 'gpolo', 'ezio.melotti', 'greg@gregdetre.co.uk', 'mrabarnett', 'adi', 'johnsonm', 'kristall', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue1160'
versions = ['Python 2.7', 'Python 3.2']
Activity
ostkamp commentedon Sep 13, 2007
Hello,
a medium size regular expression crashes Python 2.5.1 as follows:
This is apparently caused by some code in Modules/_sre.c and
Modules/sre.h as follows:
An 'unsigned int' value is unnecessarily squeezed into an 'unsigned
short' field defined in sre.h:
On all systems I'm working on (SuSE Linux SLES 9, Solaris 8 etc.) the
else case of the ifdef applies which chooses 'unsigned short'.
I don't understand the relationship between 'unicode' and what is
apparently the size of the regular expression stack here.
Some experiments have shown that changing the 'unsigned short' to
'unsigned long' and rebuilding Python fixes the problem.
Here is a test program to reproduce the error:
Regards
Guido
gvanrossum commentedon Sep 14, 2007
/F?
effbot commentedon Sep 23, 2007
Well, I'm not sure 81k qualifies as "medium sized", really. If you look
at the size distribution for typical RE:s (which are usually
handwritten, not machine generated), that's one or two orders of
magnitude larger than "medium".
(And even if this was guaranteed to work on all Python builds, my guess
is that performance would be pretty bad compared to a using a minimal RE
and checking potential matches against a set. The "|" operator is
mostly O(N), not O(1).)
As for fixing this, the "byte code" used by the RE engine uses a word
size equal to the Unicode character size (sizeof(Py_UNICODE)) for the
given platform. I don't think it would be that hard to set it to 32
bits also on platforms using 16-bit Unicode characters (if anyone would
like to experiment, just set SRE_CODE to "unsigned long" in sre.h and
see what happens when you run the test suite).
akuchling commentedon Jan 12, 2008
Trying effbot's suggested experiment is easy, at least, and would
provide useful info. If it fails, then fixing this bug might be difficult.
gpolo commentedon Feb 7, 2008
I tried Frederik's solution against trunk and it works. I compiled
python with ucs2 so it is surely setting SRE_CODE to unsigned long.
Before this change I got the same exception as pointed by Guido Ostkamp.
greggregdetrecouk commentedon Apr 20, 2008
Dear all,
I've just switched from linux to a mac, and I'm suddenly starting to
experience this issue with a machine-generated regexp that I depend on.
Are there any plans to fix this in a future version of python?
Thank you,
Greg
adi commentedon Sep 2, 2008
Is there any progress on this bug? I am currently considering
maintaining a branch of 2.5.2 which includes the patch suggested by effbot.
timehorse commentedon Sep 25, 2008
It seems that changing the size type of the Regular Expression Byte-code
is a nice quick-fix, even though it doubles the size of a pattern. It
may have the added benefit that most machine architectures available
today are at least partially, if not fully, 32-bit oriented so that
retrieving op codes may in fact be faster if we make this change. OTOH,
it implies something interesting IMHO with the repeat count limits we
currently have. Repeat counts can be explicitly set up to 65534 times
because 65535, being the largest number you can express in a 16-bit
unsigned integer, is currently reserved to mean Infinite. It seems to
me this is a great opportunity to set that limit to (unsigned long)-1,
since that repeat count is incredibly large.
OTOH, if size is an issue, we could change the way sizes are expressed
in the Regexp Op Codes (typically in skip counts) to be 15-bit, with the
Most Significant Bit being reserved for 'extended' expressions. In this
way, a value of 0xFFFFFFFF could be expressed as:
0xFFFF 0xFFFF 0x0003
Of course, parsing number in this form is a pain, to say the least, and
unlike in Python, the C-library would not play nicely if someone tried
to express a number that could not fit into what the architecture
defined an int to be. Plus, there is the problem of how you express
Infinite with this scheme. The advantage though would be we don't have
to change the op-code size and these 'extended' counts would be very
rare indeed.
Over all, I'm more of an Occam's Razor fan in that the simplest solution
is probably the best: just change the op-code size to unsigned long
(which, on SOME architectures would actually make it 64-bits!) and
define the 'Infinite' constant as (unsigned long)-1. Mind you, I prefer
defining the constant in Python, not C, and it would be hard for Python
to determine that particular value being that Python is meant to be 'the
same' regardless of the underlying architecture, but that's another issue.
Anyway, as 2.6 is in Beta, this will have to wait for Python 2.7 / 3.1,
and so I will add an item to bpo-2636 with respect to it.
kristall commentedon Oct 17, 2009
aloha,
I also use large RE's. re.compile() worked fine under python2.6 (OS
ubuntu-linux). After moving the code to python3.0 I get the same error
as ostkamp did. Under 3.1 also. Under 3.1 I tried to the fix that
ostkamp described (setting 'short' to 'long' in Modules/sre.h) and
rebuild python, but still the error occurs. I want to change to 3.x
since my variables contain german text with Umlauten (ä, ö, ü etc.) and
its pain to work with unicode under 2.x. Is there anything else I can
try, or is there a planned date when this bug will be fixed. I am
thankful in advance for any help.
kristall
pitrou commentedon Oct 19, 2009
Kristall, can you post the troublesome regular expression?
johnsonm commentedon Nov 13, 2009
I also ran into this issue, and dealt with it as suggested here by
changing to sets. Because I have underlying code that has to deal both
with small hand-crafted regular expressions and arbitrarily-large
machine-generated sets of paths, I subclassed set and implemented the
match and search methods in my subclass so that the underlying code
would work both against the hand-generated regular expressions and the
machine-generated sets of paths. Hope this helps someone else who runs
into this restriction.
ezio-melotti commentedon Nov 14, 2009
Michael, can you provide the regex or even better a testcase that shows
the problem?
johnsonm commentedon Nov 16, 2009
The test case at the top of this issue reproduces just fine; if you are
looking for a different test case you'll have to specify what you don't
like about it so that it's clear what you are looking for.
I don't think there's any mystery about this issue; it seems perfectly
well understood. I commented merely to encourage others who run into
this issue to consider one way of using sets if they are running into
the same case I was, in which I was trying to use a regular expression
to match a candidate string against a large set of exact matches.
I was doing this because the initial purpose of the interface I was
working with was to allow small, hand-specified regular expressions;
this interface was later additionally wrapped in code that automatically
created regular expressions for this interface originally (and still
also) intended for use with hand-crafted regular expressions. That's
why the interface was not originally crafted to use sets, and why it was
not appropriate to simply change the interface to use sets. However, my
interface also allows passing a callable which resolves the object at
the time of use, and so I merely passed a reference to a method which
returned an object derived from set but which implemented the match and
search methods.
If you REALLY want a simpler reproducer, this does it for me in the
restricted case (i.e., not using UCS4 encoding):
import re
r = re.compile('|'.join(('%d'%x for x in range(7000))))
But I really don't think that additional test cases are a barrier here.
Again, my goal was merely to suggest an easy way to use sets as a
replacement for regexps, for machine-generated regexps intended to match
against exact strings; subclass set and add necessary methods such as
search and/or match.
mrabarnett commentedon Feb 10, 2010
As stated in msg73781, this is being addressed in issue bpo-2636.
My regex module handles the test case without complaint:
pitrou commentedon Jun 24, 2012
This has probably been fixed in 3.3 in c67b7e0c818a.
serhiy-storchaka commentedon Jun 30, 2012
Then the issue may be closed?
pitrou commentedon Jun 30, 2012
Well, it's still present in 2.7 and 3.2 (assuming we consider it's important enough to fix).
serhiy-storchaka commentedon Nov 11, 2012
If we will considered it's important enough to fix, here are patches.
python-dev commentedon Nov 20, 2012
New changeset 10314c9b7c5a by Antoine Pitrou in branch '2.7':
Issue bpo-1160: Fix compiling large regular expressions on UCS2 builds.
http://hg.python.org/cpython/rev/10314c9b7c5a
python-dev commentedon Nov 20, 2012
New changeset a3579d766fb6 by Antoine Pitrou in branch '3.2':
Issue bpo-1160: Fix compiling large regular expressions on UCS2 builds.
http://hg.python.org/cpython/rev/a3579d766fb6
New changeset 8b73a069ae4f by Antoine Pitrou in branch '3.3':
Merge test from issue bpo-1160.
http://hg.python.org/cpython/rev/8b73a069ae4f
New changeset 10c1f9e05f4f by Antoine Pitrou in branch 'default':
Merge test from issue bpo-1160.
http://hg.python.org/cpython/rev/10c1f9e05f4f
pitrou commentedon Nov 20, 2012
I've committed the patch to 3.2 and 2.7, and added the test to 3.3 and default. Thank you!