Hello,

a medium size regular expression crashes Python 2.5.1 as follows:

Traceback (most recent call last):
  File "./regtest.py", line 14, in <module>
    m = rematch(pats)
  File "./regtest.py", line 12, in rematch
    return re.compile(pat).match
  File "/export/home/ostkamp/local/lib/python2.5/re.py", line 180, in
compile
    return _compile(pattern, flags)
  File "/export/home/ostkamp/local/lib/python2.5/re.py", line 231, in
_compile
    p = sre_compile.compile(pattern, flags)
  File "/export/home/ostkamp/local/lib/python2.5/sre_compile.py", line
530, in compile
    groupindex, indexgroup
OverflowError: regular expression code size limit exceeded


This is apparently caused by some code in Modules/_sre.c and
Modules/sre.h as follows:

        self->code[i] = (SRE_CODE) value;
        if ((unsigned long) self->code[i] != value) {
            PyErr_SetString(PyExc_OverflowError,
                            "regular expression code size limit exceeded");
            break;
        }

An 'unsigned int' value is unnecessarily squeezed into an 'unsigned
short' field defined in sre.h:

#ifdef Py_UNICODE_WIDE
#define SRE_CODE Py_UCS4
#else
#define SRE_CODE unsigned short
#endif

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:

#!/usr/bin/env python
import re, random, sys
def randhexstring():
    return "".join(["%04x" % random.randint(0, 0xffff) for x in range(20)])
pats = [randhexstring() for x in range(1000)]
def rematch(pats):
    pat = '(?:%s)' % '|'.join(pats)
    return re.compile(pat).match
m = rematch(pats)
count = 0
for s in pats * 100:
    if m(s):
        count += 1
print count



Regards

Guido

/F?

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).

Trying effbot's suggested experiment is easy, at least, and would
provide useful info.  If it fails, then fixing this bug might be difficult.

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.

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

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.

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 Issue 2636 with respect to it.

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

Kristall, can you post the troublesome regular expression?

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.

Michael, can you provide the regex or even better a testcase that shows
the problem?

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.

As stated in msg73781, this is being addressed in issue #2636.

My regex module handles the test case without complaint:

>>> import regex
>>> r = regex.compile('|'.join('%d'%x for x in range(7000)))
>>> r.match("1000")
<_regex.REGEX_Match object at 0x015D2920>
>>> r.match("6999")
<_regex.REGEX_Match object at 0x016DDC20>

This has probably been fixed in 3.3 in c67b7e0c818a.

> This has probably been fixed in 3.3 in c67b7e0c818a.

Then the issue may be closed?

> Then the issue may be closed?

Well, it's still present in 2.7 and 3.2 (assuming we consider it's important enough to fix).

If we will considered it's important enough to fix, here are patches.

New changeset 10314c9b7c5a by Antoine Pitrou in branch '2.7':
Issue #1160: Fix compiling large regular expressions on UCS2 builds.
http://hg.python.org/cpython/rev/10314c9b7c5a

New changeset a3579d766fb6 by Antoine Pitrou in branch '3.2':
Issue #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 #1160.
http://hg.python.org/cpython/rev/8b73a069ae4f

New changeset 10c1f9e05f4f by Antoine Pitrou in branch 'default':
Merge test from issue #1160.
http://hg.python.org/cpython/rev/10c1f9e05f4f

I've committed the patch to 3.2 and 2.7, and added the test to 3.3 and default. Thank you!