I've been working on a new implementation of the re module. The details
are at http://bugs.python.org/issue2636, specifically from
http://bugs.python.org/issue2636#msg90954. I've included a .pyd file for
Python 2.6 on Windows if you want to try it out.

I'm interested in how fast it is generally, compared with the current re
module, but especially when faced with those 'pathological' regular
expressions which seem to take a long time to finish, for example:

     re.search(r"^(.+|D)*A$", "x" * 25 + "B")

which on my PC (1.8GHz) takes 18.98secs with the re module but <0.01secs
with this new implementation.

I could test it with pytextile, i've a bunch of texts to bench and
compare.

Did you announce it on the unladen-swallow list ? They wanted to hack on
RE also...

For Linux (which I don't have) you'll need to use _regex.h and _regex.c
to compile to _regex.so instead of _regex.pyd.

from distutils.core import setup, Extension

setup(name='regex',
    version='1.0',
    py_modules = ['regex'],
    ext_modules=[Extension('_regex', ['_regex.c'])],
)

Also, you need to copy "unicodedata_db.h" from the "Modules" directory
of the Python source tree to your working directory, since this file
apparently is not installed into the include directory of a Python
installation.

I get an error for Python 2.5 on Mac OS X 10.4 and Linux though. Seems
that the module is not compatible with Python 2.5.

_regex.c: In function 'getstring':
_regex.c:2425: error: invalid type argument of '->'
_regex.c: In function 'getstring':
_regex.c:2425: error: invalid type argument of '->'
lipo: can't figure out the architecture type of: /var/tmp//
ccT3oDXD.out
error: command 'gcc' failed with exit status 1

resp. on Linux:

_regex.c: In function 'getstring':
_regex.c:2425: warning: implicit declaration of function 'Py_TYPE'
_regex.c:2425: error: invalid type argument of '->'
_regex.c: In function 'get_match_replacement':
_regex.c:2900: warning: implicit declaration of function
'PyLong_AsSsize_t'
error: command 'gcc' failed with exit status 1

With the official Python 2.6 distribution for Mac OS X it works.

So, i would like if it's not too much work for you.

 From here http://bugs.python.org/issue1721518 I knocked up this.

import time
import re
import regex

s = "Add.1, 2020 and Add.1, 2021-2023, 2025, 2028 and 2029 and Add.1) R"
r = "(?:\s|,|and|Add\S*?|Parts?|\([^\)]*\)|[IV\-\d]+)*$"
t0 = time.clock()
print regex.search(r, s)
t1 = time.clock()
print "time", t1 - t0

print "It's going to crash"
t0 = time.clock()
print re.search(r, s)
t1 = time.clock()
print "It hasn't crashed time", t1 - t0

Output shows a slight change in timing:).

<_regex.RE_Match object at 0x0243A1A0>
time 0.00279001940191
It's going to crash
<_sre.SRE_Match object at 0x024396B0>
It hasn't crashed time 98.4238155967

HTH.

--
Kindest regards.

If you're extending/changing the interface, there are a couple of sore
points in the current implementation I'd love to see addressed:

- findall/finditer doesn't find overlapping matches.  Sometimes you
really *do* want to know all possible matches, even if they overlap.
This comes up in bioinformatics, for example.

- split won't split on empty patterns, e.g. empty lookahead patterns.
This means that it can't be used for a whole class of interesting
cases.  This has been discussed previously:

    http://bugs.python.org/issue3262
    http://bugs.python.org/issue852532
    http://bugs.python.org/issue988761

- It'd be nice to have a version of split that generates the parts
(one by one) rather than returning the whole list.

- Repeated subgroup match information is not available.  That is, for
a match like this

    re.match('(.){3}', 'xyz')

there's no way to discover that the subgroup first matched 'x', then
matched 'y', and finally matched 'z'.  Here is one past proposal
(mine), perhaps over-complex, to address this problem:

    http://mail.python.org/pipermail/python-dev/2004-August/047238.html

My intuition, though, is that the basic idea should be fairly simple
to implement, at least for a depth-first matcher.  The repeated match
subgroups are already being discovered, it's just that they're not
being saved, so there's no way to report them out once a complete
match is found.  If some trail of breadcrumbs were pushed onto a stack
during the DFS, it could be traced at the end.  And the whole thing
might not even been that expensive to do.

The hardest parts about this, in my mind, are figuring out how to
report the repeated matches out in a useful form (hence all that
detail in the proposal), and getting users to understand that using
this feature *could* suck up a lot of memory, if they're not careful.

As always, it's possible that my intuition is totally wrong.  Plus I'm
not sure how this would work out in the breadth-first case.

I have Python 2.6.2 on ubuntu 9.04

with ggc-4.3:
gcc -pthread -fno-strict-aliasing -DNDEBUG -g -fwrapv -O2 -Wall -
Wstrict-prototypes -fPIC -I/usr/include/python2.6 -c _regex.c -o
build/temp.linux-i686-2.6/_regex.o
_regex.c: In Funktion »bmatch_context«:
_regex.c:1462: Fehler: Als Erhöhungsoperand wird L-Wert erfordert
_regex.c:1470: Fehler: Als Erhöhungsoperand wird L-Wert erfordert
_regex.c:1478: Fehler: Als Verringerungsoperand wird L-Wert erfordert

with gcc-4.4:
gcc-4.4 -fno-strict-aliasing -DNDEBUG -g -fwrapv -O2 -Wall -Wstrict-
prototypes -fPIC -I/usr/include/python2.6 -c _regex.c -o
build/temp.linux-i686-2.6/_regex.o
_regex.c: In function ‘bmatch_context’:
_regex.c:1462: error: lvalue required as increment operand
_regex.c:1470: error: lvalue required as increment operand
_regex.c:1478: error: lvalue required as decrement operand

notebook:~/kmj/src$ LANG=C python setup.py  build
running build
running build_py
running build_ext
building '_regex' extension
gcc -pthread -fno-strict-aliasing -DNDEBUG -g -fwrapv -O2 -Wall -
Wstrict-prototypes -fPIC -I/usr/include/python2.6 -c _regex.c -o
build/temp.linux-i686-2.6/_regex.o
_regex.c: In function 'bmatch_context':
_regex.c:1462: error: lvalue required as increment operand
_regex.c:1470: error: lvalue required as increment operand
_regex.c:1478: error: lvalue required as decrement operand
_regex.c:1487: error: lvalue required as decrement operand
_regex.c:1593: error: lvalue required as increment operand
_regex.c:1606: error: lvalue required as decrement operand
_regex.c:1616: error: lvalue required as increment operand
_regex.c:1625: error: lvalue required as increment operand
_regex.c:1634: error: lvalue required as decrement operand
_regex.c:1643: error: lvalue required as decrement operand
_regex.c:2036: error: lvalue required as increment operand
_regex.c:2047: error: lvalue required as increment operand
_regex.c:2059: error: lvalue required as decrement operand
_regex.c:2070: error: lvalue required as decrement operand
_regex.c:2316: error: lvalue required as increment operand
In file included from _regex.c:2431:
_regex.c: In function 'umatch_context':
_regex.c:1462: error: lvalue required as increment operand
_regex.c:1470: error: lvalue required as increment operand
_regex.c:1478: error: lvalue required as decrement operand
_regex.c:1487: error: lvalue required as decrement operand
_regex.c:1593: error: lvalue required as increment operand
_regex.c:1606: error: lvalue required as decrement operand
_regex.c:1616: error: lvalue required as increment operand
_regex.c:1625: error: lvalue required as increment operand
_regex.c:1634: error: lvalue required as decrement operand
_regex.c:1643: error: lvalue required as decrement operand
_regex.c:2036: error: lvalue required as increment operand
_regex.c:2047: error: lvalue required as increment operand
_regex.c:2059: error: lvalue required as decrement operand
_regex.c:2070: error: lvalue required as decrement operand
_regex.c:2316: error: lvalue required as increment operand
error: command 'gcc' failed with exit status 1

     ++(RE_CHAR*)context->text_ptr

but not about:

     ++info->repeat.count

(search -fnon-lvalue-assign)

so I did the conversion mentioned there. This works:

--- _regex.c    2009-07-29 11:34:00.000000000 +0200
+++ n   2009-07-30 15:15:22.000000000 +0200
@@ -1459,7 +1459,7 @@
             if (text_ptr < (RE_CHAR*)context->slice_end && text_ptr[0] != '\n')
               {
                 context->node = node->next_1;
-                ++(RE_CHAR*)context->text_ptr;
+                ++*(RE_CHAR**)&context->text_ptr;
             } else
                 context = reject_context(state, context);
             break;