Adding Fredrik Lundh's _sre.c module and its header files.
NOTE: THIS IS VERY ROUGH ALPHA CODE!
diff --git a/Modules/_sre.c b/Modules/_sre.c
new file mode 100644
index 0000000..8af876f
--- /dev/null
+++ b/Modules/_sre.c
@@ -0,0 +1,1453 @@
+/* -*- Mode: C; tab-width: 4 -*-
+ *
+ * Secret Labs' Regular Expression Engine
+ * $Id$
+ *
+ * simple regular expression matching engine
+ *
+ * partial history:
+ * 99-10-24 fl created (bits and pieces from the template matcher)
+ * 99-11-13 fl added categories, branching, and more (0.2)
+ * 99-11-16 fl some tweaks to compile on non-Windows platforms
+ * 99-12-18 fl non-literals, generic maximizing repeat (0.3)
+ * 99-02-28 fl tons of changes (not all to the better ;-) (0.4)
+ * 99-03-06 fl first alpha, sort of (0.5)
+ * 99-03-14 fl removed most compatibility stuff (0.6)
+ *
+ * Copyright (c) 1997-2000 by Secret Labs AB. All rights reserved.
+ *
+ * This code can only be used for 1.6 alpha testing. All other use
+ * require explicit permission from Secret Labs AB.
+ *
+ * Portions of this engine have been developed in cooperation with
+ * CNRI. Hewlett-Packard provided funding for 1.6 integration and
+ * other compatibility work.
+ */
+
+#ifndef SRE_RECURSIVE
+
+char copyright[] = " SRE 0.6 Copyright (c) 1997-2000 by Secret Labs AB ";
+
+#include "Python.h"
+
+#include "sre.h"
+
+#include "unicodeobject.h"
+
+#if defined(HAVE_LIMITS_H)
+#include <limits.h>
+#else
+#define INT_MAX 2147483647
+#endif
+
+#include <ctype.h> /* temporary hack */
+
+/* defining this one enables tracing */
+#undef DEBUG
+
+#ifdef WIN32 /* FIXME: <fl> don't assume Windows == MSVC */
+#pragma optimize("agtw", on) /* doesn't seem to make much difference... */
+/* fastest possible local call under MSVC */
+#define LOCAL(type) static __inline type __fastcall
+#else
+#define LOCAL(type) static type
+#endif
+
+/* error codes */
+#define SRE_ERROR_ILLEGAL -1 /* illegal opcode */
+#define SRE_ERROR_MEMORY -9 /* out of memory */
+
+#ifdef DEBUG
+#define TRACE(v) printf v
+#define PTR(ptr) ((SRE_CHAR*) (ptr) - (SRE_CHAR*) state->beginning)
+#else
+#define TRACE(v)
+#endif
+
+#define SRE_CODE unsigned short /* unsigned short or larger */
+
+typedef struct {
+ /* string pointers */
+ void* ptr; /* current position (also end of current slice) */
+ void* beginning; /* start of original string */
+ void* start; /* start of current slice */
+ void* end; /* end of original string */
+ /* character size */
+ int charsize;
+ /* registers */
+ int marks;
+ void* mark[64]; /* FIXME: <fl> should be dynamically allocated! */
+ /* FIXME */
+ /* backtracking stack */
+ void** stack;
+ int stacksize;
+ int stackbase;
+} SRE_STATE;
+
+#if 1 /* FIXME: <fl> fix this one! */
+#define SRE_TO_LOWER Py_UNICODE_TOLOWER
+#define SRE_IS_DIGIT Py_UNICODE_ISDIGIT
+#define SRE_IS_SPACE Py_UNICODE_ISSPACE
+#define SRE_IS_ALNUM(ch) ((ch) < 256 ? isalnum((ch)) : 0)
+#else
+#define SRE_TO_LOWER(ch) ((ch) < 256 ? tolower((ch)) : ch)
+#define SRE_IS_DIGIT(ch) ((ch) < 256 ? isdigit((ch)) : 0)
+#define SRE_IS_SPACE(ch) ((ch) < 256 ? isspace((ch)) : 0)
+#define SRE_IS_ALNUM(ch) ((ch) < 256 ? isalnum((ch)) : 0)
+#endif
+
+#define SRE_IS_WORD(ch) (SRE_IS_ALNUM((ch)) || (ch) == '_')
+
+LOCAL(int)
+sre_category(SRE_CODE category, unsigned int ch)
+{
+ switch (category) {
+ case 'd':
+ return SRE_IS_DIGIT(ch);
+ case 'D':
+ return !SRE_IS_DIGIT(ch);
+ case 's':
+ return SRE_IS_SPACE(ch);
+ case 'S':
+ return !SRE_IS_SPACE(ch);
+ case 'w':
+ return SRE_IS_WORD(ch);
+ case 'W':
+ return !SRE_IS_WORD(ch);
+ }
+ return 0;
+}
+
+/* helpers */
+
+LOCAL(int)
+_stack_free(SRE_STATE* state)
+{
+ if (state->stack) {
+ TRACE(("release stack\n"));
+ free(state->stack);
+ state->stack = NULL;
+ }
+ state->stacksize = 0;
+ return 0;
+}
+
+static int /* shouldn't be LOCAL */
+_stack_extend(SRE_STATE* state, int lo, int hi)
+{
+ void** stack;
+ int stacksize;
+
+ /* grow the stack to a suitable size; we need at least lo entries,
+ at most hi entries. if for some reason hi is lower than lo, lo
+ wins */
+
+ stacksize = state->stacksize;
+
+ if (stacksize == 0) {
+ /* create new stack */
+ stacksize = 512;
+ if (stacksize < lo)
+ stacksize = lo;
+ else if (stacksize > hi)
+ stacksize = hi;
+ TRACE(("allocate stack %d\n", stacksize));
+ stack = malloc(sizeof(void*) * stacksize);
+ } else {
+ /* grow the stack (typically by a factor of two) */
+ while (stacksize < lo)
+ stacksize = 2 * stacksize;
+ /* FIXME: <fl> could trim size if it's larger than lo, and
+ much larger than hi */
+ TRACE(("grow stack to %d\n", stacksize));
+ stack = realloc(state->stack, sizeof(void*) * stacksize);
+ }
+
+ if (!stack) {
+ _stack_free(state);
+ return SRE_ERROR_MEMORY;
+ }
+
+ state->stack = stack;
+ state->stacksize = stacksize;
+
+ return 0;
+}
+
+/* set things up for the 8-bit version */
+
+#define SRE_CHAR unsigned char
+#define SRE_AT sre_at
+#define SRE_MEMBER sre_member
+#define SRE_MATCH sre_match
+#define SRE_SEARCH sre_search
+#define SRE_RECURSIVE
+
+#include "_sre.c"
+
+#undef SRE_RECURSIVE
+#undef SRE_SEARCH
+#undef SRE_MATCH
+#undef SRE_MEMBER
+#undef SRE_AT
+#undef SRE_CHAR
+
+/* set things up for the 16-bit unicode version */
+
+#define SRE_CHAR Py_UNICODE
+#define SRE_AT sre_uat
+#define SRE_MEMBER sre_umember
+#define SRE_MATCH sre_umatch
+#define SRE_SEARCH sre_usearch
+
+#endif /* SRE_RECURSIVE */
+
+/* -------------------------------------------------------------------- */
+/* String matching engine */
+
+/* the following section is compiled twice, with different character
+ settings */
+
+LOCAL(int)
+SRE_AT(SRE_STATE* state, SRE_CHAR* ptr, SRE_CODE at)
+{
+ /* check if pointer is at given position. return 1 if so, 0
+ otherwise */
+
+ int this, that;
+
+ switch (at) {
+ case 'a':
+ /* beginning */
+ return (ptr == state->beginning);
+ case 'z':
+ /* end */
+ return (ptr == state->end);
+ case 'b':
+ /* word boundary */
+ if (state->beginning == state->end)
+ return 0;
+ that = ((void*) ptr > state->beginning) ?
+ SRE_IS_WORD((int) ptr[-1]) : 0;
+ this = ((void*) ptr < state->end) ?
+ SRE_IS_WORD((int) ptr[0]) : 0;
+ return this != that;
+ case 'B':
+ /* word non-boundary */
+ if (state->beginning == state->end)
+ return 0;
+ that = ((void*) ptr > state->beginning) ?
+ SRE_IS_WORD((int) ptr[-1]) : 0;
+ this = ((void*) ptr < state->end) ?
+ SRE_IS_WORD((int) ptr[0]) : 0;
+ return this == that;
+ }
+
+ return 0;
+}
+
+LOCAL(int)
+SRE_MEMBER(SRE_CODE* set, SRE_CHAR ch)
+{
+ /* check if character is a member of the given set. return 1 if
+ so, 0 otherwise */
+
+ int ok = 1;
+
+ for (;;) {
+ switch (*set++) {
+
+ case SRE_OP_NEGATE:
+ ok = !ok;
+ break;
+
+ case SRE_OP_FAILURE:
+ return !ok;
+
+ case SRE_OP_LITERAL:
+ if (ch == (SRE_CHAR) set[0])
+ return ok;
+ set++;
+ break;
+
+ case SRE_OP_RANGE:
+ if ((SRE_CHAR) set[0] <= ch && ch <= (SRE_CHAR) set[1])
+ return ok;
+ set += 2;
+ break;
+
+ case SRE_OP_CATEGORY:
+ if (sre_category(set[0], (int) ch))
+ return ok;
+ set += 1;
+ break;
+
+ default:
+ /* FIXME: internal error */
+ return 0;
+ }
+ }
+}
+
+LOCAL(int)
+SRE_MATCH(SRE_STATE* state, SRE_CODE* pattern)
+{
+ /* check if string matches the given pattern. returns -1 for
+ error, 0 for failure, and 1 for success */
+
+ SRE_CHAR* end = state->end;
+ SRE_CHAR* ptr = state->ptr;
+ int stacksize;
+ int stackbase;
+ int i, count;
+
+ for (;;) {
+
+ TRACE(("[%p]\n", pattern));
+
+ switch (*pattern++) {
+
+ case SRE_OP_FAILURE:
+ /* immediate failure */
+ TRACE(("%8d: failure\n", PTR(ptr)));
+ return 0;
+
+ case SRE_OP_SUCCESS:
+ /* end of pattern */
+ TRACE(("%8d: success\n", PTR(ptr)));
+ state->ptr = ptr;
+ return 1;
+
+ case SRE_OP_AT:
+ /* match at given position */
+ TRACE(("%8d: match at \\%c\n", PTR(ptr), *pattern));
+ if (!SRE_AT(state, ptr, *pattern))
+ return 0;
+ pattern++;
+ break;
+
+ case SRE_OP_LITERAL:
+ /* match literal character */
+ /* args: <code> */
+ TRACE(("%8d: literal %c\n", PTR(ptr), (SRE_CHAR) *pattern));
+ if (ptr >= end || *ptr != (SRE_CHAR) *pattern)
+ return 0;
+ pattern++;
+ ptr++;
+ break;
+
+ case SRE_OP_NOT_LITERAL:
+ /* match anything that is not literal character */
+ /* args: <code> */
+ TRACE(("%8d: literal not %c\n", PTR(ptr), (SRE_CHAR) *pattern));
+ if (ptr >= end || *ptr == (SRE_CHAR) *pattern)
+ return 0;
+ pattern++;
+ ptr++;
+ break;
+
+ case SRE_OP_ANY:
+ /* match anything */
+ TRACE(("%8d: any\n", PTR(ptr)));
+ if (ptr >= end)
+ return 0;
+ ptr++;
+ break;
+
+ case SRE_OP_IN:
+ /* match set member (or non_member) */
+ /* args: <skip> <set> */
+ TRACE(("%8d: set %c\n", PTR(ptr), *ptr));
+ if (ptr >= end || !SRE_MEMBER(pattern + 1, *ptr))
+ return 0;
+ pattern += pattern[0];
+ ptr++;
+ break;
+
+ case SRE_OP_GROUP:
+ /* match backreference */
+ i = pattern[0];
+ {
+ /* FIXME: optimize size! */
+ SRE_CHAR* p = (SRE_CHAR*) state->mark[i+i];
+ SRE_CHAR* e = (SRE_CHAR*) state->mark[i+i+1];
+ if (!p || !e || e < p)
+ return 0;
+ while (p < e) {
+ if (ptr >= end || *ptr != *p)
+ return 0;
+ p++; ptr++;
+ }
+ }
+ pattern++;
+ break;
+
+ case SRE_OP_LITERAL_IGNORE:
+ TRACE(("%8d: literal lower(%c)\n", PTR(ptr), (SRE_CHAR) *pattern));
+ if (ptr >= end || SRE_TO_LOWER(*ptr) != (SRE_CHAR) *pattern)
+ return 0;
+ pattern++;
+ ptr++;
+ break;
+
+ case SRE_OP_NOT_LITERAL_IGNORE:
+ TRACE(("%8d: literal not lower(%c)\n", PTR(ptr),
+ (SRE_CHAR) *pattern));
+ if (ptr >= end || SRE_TO_LOWER(*ptr) == (SRE_CHAR) *pattern)
+ return 0;
+ pattern++;
+ ptr++;
+ break;
+
+ case SRE_OP_IN_IGNORE:
+ TRACE(("%8d: set lower(%c)\n", PTR(ptr), *ptr));
+ if (ptr >= end
+ || !SRE_MEMBER(pattern+1, (SRE_CHAR) SRE_TO_LOWER(*ptr)))
+ return 0;
+ pattern += pattern[0];
+ ptr++;
+ break;
+
+ case SRE_OP_MARK:
+ /* set mark */
+ /* args: <mark> */
+ TRACE(("%8d: set mark(%d)\n", PTR(ptr), pattern[0]));
+ state->mark[pattern[0]] = ptr;
+ pattern++;
+ break;
+
+ case SRE_OP_JUMP:
+ /* jump forward */
+ /* args: <skip> */
+ TRACE(("%8d: jump +%d\n", PTR(ptr), pattern[0]));
+ pattern += pattern[0];
+ break;
+
+ case SRE_OP_CALL:
+ /* match subpattern, without backtracking */
+ /* args: <skip> <pattern> */
+ TRACE(("%8d: match subpattern\n", PTR(ptr)));
+ state->ptr = ptr;
+ if (!SRE_MATCH(state, pattern + 1))
+ return 0;
+ pattern += pattern[0];
+ ptr = state->ptr;
+ break;
+
+ case SRE_OP_MAX_REPEAT_ONE:
+
+ /* match repeated sequence (maximizing regexp). this
+ variant only works if the repeated item is exactly one
+ character wide, and we're not already collecting
+ backtracking points. for other cases, use the
+ MAX_REPEAT operator instead */
+
+ /* args: <skip> <min> <max> <step> */
+
+ TRACE(("%8d: max repeat one {%d,%d}\n", PTR(ptr),
+ pattern[1], pattern[2]));
+
+ count = 0;
+
+ if (pattern[3] == SRE_OP_ANY) {
+ /* repeated wildcard. skip to the end of the target
+ string, and backtrack from there */
+ /* FIXME: must look for line endings */
+ if (ptr + pattern[1] > end)
+ return 0; /* cannot match */
+ count = pattern[2];
+ if (count > end - ptr)
+ count = end - ptr;
+ ptr += count;
+
+ } else if (pattern[3] == SRE_OP_LITERAL) {
+ /* repeated literal */
+ SRE_CHAR chr = (SRE_CHAR) pattern[4];
+ while (count < (int) pattern[2]) {
+ if (ptr >= end || *ptr != chr)
+ break;
+ ptr++;
+ count++;
+ }
+
+ } else if (pattern[3] == SRE_OP_LITERAL_IGNORE) {
+ /* repeated literal */
+ SRE_CHAR chr = (SRE_CHAR) pattern[4];
+ while (count < (int) pattern[2]) {
+ if (ptr >= end || (SRE_CHAR) SRE_TO_LOWER(*ptr) != chr)
+ break;
+ ptr++;
+ count++;
+ }
+
+ } else if (pattern[3] == SRE_OP_NOT_LITERAL) {
+ /* repeated non-literal */
+ SRE_CHAR chr = (SRE_CHAR) pattern[4];
+ while (count < (int) pattern[2]) {
+ if (ptr >= end || *ptr == chr)
+ break;
+ ptr++;
+ count++;
+ }
+
+ } else if (pattern[3] == SRE_OP_NOT_LITERAL_IGNORE) {
+ /* repeated non-literal */
+ SRE_CHAR chr = (SRE_CHAR) pattern[4];
+ while (count < (int) pattern[2]) {
+ if (ptr >= end || (SRE_CHAR) SRE_TO_LOWER(*ptr) == chr)
+ break;
+ ptr++;
+ count++;
+ }
+
+ } else if (pattern[3] == SRE_OP_IN) {
+ /* repeated set */
+ while (count < (int) pattern[2]) {
+ if (ptr >= end || !SRE_MEMBER(pattern + 5, *ptr))
+ break;
+ ptr++;
+ count++;
+ }
+
+ } else {
+ /* repeated single character pattern */
+ state->ptr = ptr;
+ while (count < (int) pattern[2]) {
+ i = SRE_MATCH(state, pattern + 3);
+ if (i < 0)
+ return i;
+ if (i == 0)
+ break;
+ count++;
+ }
+ state->ptr = ptr;
+ ptr += count;
+ }
+
+ /* when we arrive here, count contains the number of
+ matches, and ptr points to the tail of the target
+ string. check if the rest of the pattern matches, and
+ backtrack if not. */
+
+ /* FIXME: <fl> this is a mess. fix it! */
+
+ TRACE(("%8d: repeat %d found\n", PTR(ptr), count));
+
+ if (count < (int) pattern[1])
+ return 0;
+
+ if (pattern[pattern[0]] == SRE_OP_SUCCESS) {
+ /* tail is empty. we're finished */
+ TRACE(("%8d: tail is empty\n", PTR(ptr)));
+ state->ptr = ptr;
+ return 1;
+
+ } else if (pattern[pattern[0]] == SRE_OP_LITERAL) {
+ /* tail starts with a literal. we can speed things up
+ by skipping positions where the rest of the pattern
+ cannot possibly match */
+ SRE_CHAR chr = (SRE_CHAR) pattern[pattern[0]+1];
+ TRACE(("%8d: tail is literal %d\n", PTR(ptr), chr));
+ for (;;) {
+ TRACE(("%8d: scan for tail match\n", PTR(ptr)));
+ while (count >= (int) pattern[1] &&
+ (ptr >= end || *ptr != chr)) {
+ ptr--;
+ count--;
+ }
+ TRACE(("%8d: check tail\n", PTR(ptr)));
+ if (count < (int) pattern[1])
+ break;
+ state->ptr = ptr;
+ i = SRE_MATCH(state, pattern + pattern[0]);
+ if (i > 0) {
+ TRACE(("%8d: repeat %d picked\n", PTR(ptr), count));
+ return 1;
+ }
+ TRACE(("%8d: BACKTRACK\n", PTR(ptr)));
+ ptr--;
+ count--;
+ }
+
+ } else {
+ TRACE(("%8d: tail is pattern\n", PTR(ptr)));
+ while (count >= (int) pattern[1]) {
+ state->ptr = ptr;
+ i = SRE_MATCH(state, pattern + pattern[0]);
+ if (i > 0) {
+ TRACE(("%8d: repeat %d picked\n", PTR(ptr), count));
+ return 1;
+ }
+ TRACE(("%8d: BACKTRACK\n", PTR(ptr)));
+ ptr--;
+ count--;
+ }
+ }
+ return 0; /* failure! */
+
+/* ----------------------------------------------------------------------- */
+/* FIXME: the following section is just plain broken */
+
+ case SRE_OP_MAX_REPEAT:
+ /* match repeated sequence (maximizing regexp). repeated
+ group should end with a MAX_UNTIL code */
+
+ TRACE(("%8d: max repeat %d %d\n", PTR(ptr),
+ pattern[1], pattern[2]));
+
+ count = 0;
+ state->ptr = ptr;
+
+ /* FIXME: <fl> umm. what about matching the minimum
+ number of items before starting to collect backtracking
+ positions? */
+
+ stackbase = state->stackbase;
+
+ while (count < (int) pattern[2]) {
+ /* store current position on the stack */
+ TRACE(("%8d: push mark at index %d\n", PTR(ptr), count));
+ if (stackbase + count >= state->stacksize) {
+ i = _stack_extend(state, stackbase + count + 1,
+ stackbase + pattern[2]);
+ if (i < 0)
+ return i;
+ }
+ state->stack[stackbase + count] = ptr;
+ /* check if we can match another item */
+ state->stackbase += count + 1;
+ i = SRE_MATCH(state, pattern + 3);
+ state->stackbase = stackbase; /* rewind */
+ if (i != 2)
+ break;
+ if (state->ptr == ptr) {
+ /* if the match was successful but empty, set the
+ count to max and terminate the scanning loop */
+ stacksize = count; /* actual size of stack */
+ count = (int) pattern[2];
+ goto check_tail; /* FIXME: <fl> eliminate goto */
+ }
+ count++;
+ ptr = state->ptr;
+
+ }
+
+ stacksize = count; /* actual number of entries on the stack */
+
+ check_tail:
+
+ /* when we get here, count is the number of matches,
+ stacksize is the number of match points on the stack
+ (usually same as count, but it might be smaller) and
+ ptr points to the tail. */
+
+ if (count < (int) pattern[1])
+ return 0;
+
+ /* make sure that rest of the expression matches. if it
+ doesn't, backtrack */
+
+ TRACE(("%8d: repeat %d found (stack size = %d)\n", PTR(ptr),
+ count, stacksize + 1));
+
+ TRACE(("%8d: tail is pattern\n", PTR(ptr)));
+
+ /* hope for the best */
+ state->ptr = ptr;
+ state->stackbase += stacksize + 1;
+ i = SRE_MATCH(state, pattern + pattern[0]);
+ state->stackbase = stackbase;
+ if (i > 0) {
+ TRACE(("%8d: repeat %d picked\n", PTR(ptr), count));
+ return 1;
+ }
+
+ /* backtrack! */
+ while (count >= (int) pattern[1]) {
+ ptr = state->stack[stackbase + (count < stacksize ? count : stacksize)];
+ state->ptr = ptr;
+ count--;
+ TRACE(("%8d: BACKTRACK\n", PTR(ptr)));
+ state->stackbase += stacksize + 1;
+ i = SRE_MATCH(state, pattern + pattern[0]);
+ state->stackbase = stackbase;
+ if (i > 0) {
+ TRACE(("%8d: repeat %d picked\n", PTR(ptr), count));
+ return 1;
+ }
+ }
+ return 0; /* failure! */
+
+ case SRE_OP_MAX_UNTIL:
+ /* match repeated sequence (maximizing regexp). repeated
+ group should end with a MAX_UNTIL code */
+
+ TRACE(("%8d: max until\n", PTR(ptr)));
+ state->ptr = ptr;
+ return 2; /* always succeeds, for now... */
+
+/* end of totally broken section */
+/* ----------------------------------------------------------------------- */
+
+ case SRE_OP_MIN_REPEAT:
+ /* match repeated sequence (minimizing regexp) */
+ TRACE(("%8d: min repeat %d %d\n", PTR(ptr),
+ pattern[1], pattern[2]));
+ count = 0;
+ state->ptr = ptr;
+ /* match minimum number of items */
+ while (count < (int) pattern[1]) {
+ i = SRE_MATCH(state, pattern + 3);
+ if (i <= 0)
+ return i;
+ count++;
+ }
+ /* move forward until the tail matches. */
+ while (count <= (int) pattern[2]) {
+ ptr = state->ptr;
+ i = SRE_MATCH(state, pattern + pattern[0]);
+ if (i > 0) {
+ TRACE(("%8d: repeat %d picked\n", PTR(ptr), count));
+ return 1;
+ }
+ TRACE(("%8d: BACKTRACK\n", PTR(ptr)));
+ state->ptr = ptr; /* backtrack */
+ i = SRE_MATCH(state, pattern + 3);
+ if (i <= 0)
+ return i;
+ count++;
+ }
+ return 0; /* failure! */
+
+ case SRE_OP_MIN_UNTIL:
+ /* end of repeat group */
+ TRACE(("%8d: min until\n", PTR(ptr)));
+ state->ptr = ptr;
+ return 2; /* always succeeds, for now... */
+
+ case SRE_OP_BRANCH:
+ /* match one of several subpatterns */
+ /* format: <branch> <size> <head> ... <null> <tail> */
+ TRACE(("%8d: branch\n", PTR(ptr)));
+ while (*pattern) {
+ if (pattern[1] != SRE_OP_LITERAL ||
+ (ptr < end && *ptr == (SRE_CHAR) pattern[2])) {
+ TRACE(("%8d: branch check\n", PTR(ptr)));
+ state->ptr = ptr;
+ i = SRE_MATCH(state, pattern + 1);
+ if (i > 0) {
+ TRACE(("%8d: branch succeeded\n", PTR(ptr)));
+ return 1;
+ }
+ }
+ pattern += *pattern;
+ }
+ TRACE(("%8d: branch failed\n", PTR(ptr)));
+ return 0; /* failure! */
+
+ case SRE_OP_REPEAT:
+ /* TEMPLATE: match repeated sequence (no backtracking) */
+ /* format: <repeat> <skip> <min> <max> */
+ TRACE(("%8d: repeat %d %d\n", PTR(ptr), pattern[1], pattern[2]));
+ count = 0;
+ state->ptr = ptr;
+ while (count < (int) pattern[2]) {
+ i = SRE_MATCH(state, pattern + 3);
+ if (i <= 0)
+ break;
+ count++;
+ }
+ if (count <= (int) pattern[1])
+ return 0;
+ TRACE(("%8d: repeat %d matches\n", PTR(ptr), count));
+ pattern += pattern[0];
+ ptr = state->ptr;
+ break;
+
+ default:
+ return SRE_ERROR_ILLEGAL;
+ }
+ }
+}
+
+LOCAL(int)
+SRE_SEARCH(SRE_STATE* state, SRE_CODE* pattern)
+{
+ SRE_CHAR* ptr = state->start;
+ SRE_CHAR* end = state->end;
+ int status = 0;
+
+ /* FIXME: <fl> add IGNORE cases (or implement full ASSERT support? */
+
+ if (pattern[0] == SRE_OP_LITERAL) {
+ /* pattern starts with a literal */
+ SRE_CHAR chr = (SRE_CHAR) pattern[1];
+ for (;;) {
+ while (ptr < end && *ptr != chr)
+ ptr++;
+ if (ptr == end)
+ return 0;
+ TRACE(("%8d: search found literal\n", PTR(ptr)));
+ state->start = ptr;
+ state->ptr = ++ptr;
+ status = SRE_MATCH(state, pattern + 2);
+ if (status != 0)
+ break;
+ }
+
+ } else if (pattern[0] == SRE_OP_IN) {
+ /* pattern starts with a set */
+ for (;;) {
+ /* format: <in> <skip> <data> */
+ while (ptr < end && !SRE_MEMBER(pattern + 2, *ptr))
+ ptr++;
+ if (ptr == end)
+ return 0;
+ TRACE(("%8d: search found set\n", PTR(ptr)));
+ state->start = ptr;
+ state->ptr = ++ptr;
+ status = SRE_MATCH(state, pattern + pattern[1] + 1);
+ if (status != 0)
+ break;
+ }
+
+ } else
+ while (ptr <= end) {
+ TRACE(("%8d: search\n", PTR(ptr)));
+ state->start = state->ptr = ptr++;
+ status = SRE_MATCH(state, pattern);
+ if (status != 0)
+ break;
+ }
+
+ return status;
+}
+
+#ifndef SRE_RECURSIVE
+
+/* -------------------------------------------------------------------- */
+/* factories and destructors */
+
+/* see sre.h for object declarations */
+
+staticforward PyTypeObject Pattern_Type;
+staticforward PyTypeObject Match_Type;
+
+static PyObject *
+_compile(PyObject* self_, PyObject* args)
+{
+ /* "compile" pattern descriptor to pattern object */
+
+ PatternObject* self;
+
+ PyObject* pattern;
+ PyObject* code;
+ int groups = 0;
+ PyObject* groupindex = NULL;
+ if (!PyArg_ParseTuple(args, "OO!|iO", &pattern,
+ &PyString_Type, &code, &groups, &groupindex))
+ return NULL;
+
+ self = PyObject_NEW(PatternObject, &Pattern_Type);
+ if (self == NULL)
+ return NULL;
+
+ Py_INCREF(pattern);
+ self->pattern = pattern;
+
+ Py_INCREF(code);
+ self->code = code;
+
+ self->groups = groups;
+
+ Py_XINCREF(groupindex);
+ self->groupindex = groupindex;
+
+ return (PyObject*) self;
+}
+
+static PyObject *
+_getcodesize(PyObject* self_, PyObject* args)
+{
+ return Py_BuildValue("i", sizeof(SRE_CODE));
+}
+
+static PyObject*
+_pattern_new_match(PatternObject* pattern, SRE_STATE* state,
+ PyObject* string, int status)
+{
+ /* create match object (from state object) */
+
+ MatchObject* match;
+ int i, j;
+
+ TRACE(("status = %d\n", status));
+
+ if (status > 0) {
+
+ /* create match object (with room for extra group marks) */
+ match = PyObject_NEW_VAR(MatchObject, &Match_Type, 2*pattern->groups);
+ if (match == NULL)
+ return NULL;
+
+ Py_INCREF(pattern);
+ match->pattern = pattern;
+
+ Py_INCREF(string);
+ match->string = string;
+
+ match->groups = pattern->groups+1;
+
+ /* group zero */
+ match->mark[0] = ((char*) state->start -
+ (char*) state->beginning) / state->charsize;
+ match->mark[1] = ((char*) state->ptr -
+ (char*) state->beginning) / state->charsize;
+
+ /* fill in the rest of the groups */
+ for (i = j = 0; i < pattern->groups; i++, j+=2)
+ if (state->mark[j] != NULL && state->mark[j+1] != NULL) {
+ match->mark[j+2] = ((char*) state->mark[j] -
+ (char*) state->beginning) / state->charsize;
+ match->mark[j+3] = ((char*) state->mark[j+1] -
+ (char*) state->beginning) / state->charsize;
+ } else
+ match->mark[j+2] = match->mark[j+3] = -1; /* undefined */
+
+ return (PyObject*) match;
+
+ } else if (status < 0) {
+
+ /* internal error */
+ PyErr_SetString(
+ PyExc_RuntimeError, "internal error in regular expression engine"
+ );
+ return NULL;
+
+ }
+
+ Py_INCREF(Py_None);
+ return Py_None;
+}
+
+/* -------------------------------------------------------------------- */
+/* pattern methods */
+
+LOCAL(PyObject*)
+_setup(SRE_STATE* state, PyObject* args)
+{
+ /* prepare state object */
+
+ PyBufferProcs *buffer;
+ int i, count;
+ void* ptr;
+
+ PyObject* string;
+ int start = 0;
+ int end = INT_MAX;
+ if (!PyArg_ParseTuple(args, "O|ii", &string, &start, &end))
+ return NULL;
+
+ /* get pointer to string buffer */
+ buffer = string->ob_type->tp_as_buffer;
+ if (!buffer || !buffer->bf_getreadbuffer || !buffer->bf_getsegcount ||
+ buffer->bf_getsegcount(string, NULL) != 1) {
+ PyErr_SetString(PyExc_TypeError, "expected read-only buffer");
+ return NULL;
+ }
+
+ /* determine buffer size */
+ count = buffer->bf_getreadbuffer(string, 0, &ptr);
+ if (count < 0) {
+ /* sanity check */
+ PyErr_SetString(PyExc_TypeError, "buffer has negative size");
+ return NULL;
+ }
+
+ /* determine character size */
+ state->charsize = (PyUnicode_Check(string) ? sizeof(Py_UNICODE) : 1);
+
+ count /= state->charsize;
+
+ /* adjust boundaries */
+ if (start < 0)
+ start = 0;
+ else if (start > count)
+ start = count;
+
+ if (end < 0)
+ end = 0;
+ else if (end > count)
+ end = count;
+
+ state->beginning = ptr;
+
+ state->start = (void*) ((char*) ptr + start * state->charsize);
+ state->end = (void*) ((char*) ptr + end * state->charsize);
+
+ /* FIXME: dynamic! */
+ for (i = 0; i < 64; i++)
+ state->mark[i] = NULL;
+
+ state->stack = NULL;
+ state->stackbase = 0;
+ state->stacksize = 0;
+
+ return string;
+}
+
+static void
+_pattern_dealloc(PatternObject* self)
+{
+ Py_XDECREF(self->code);
+ Py_XDECREF(self->pattern);
+ Py_XDECREF(self->groupindex);
+ PyMem_DEL(self);
+}
+
+static PyObject*
+_pattern_match(PatternObject* self, PyObject* args)
+{
+ SRE_STATE state;
+ PyObject* string;
+ int status;
+
+ string = _setup(&state, args);
+ if (!string)
+ return NULL;
+
+ state.ptr = state.start;
+
+ if (state.charsize == 1) {
+ status = sre_match(&state, PatternObject_GetCode(self));
+ } else {
+ status = sre_umatch(&state, PatternObject_GetCode(self));
+ }
+
+ _stack_free(&state);
+
+ return _pattern_new_match(self, &state, string, status);
+}
+
+static PyObject*
+_pattern_search(PatternObject* self, PyObject* args)
+{
+ SRE_STATE state;
+ PyObject* string;
+ int status;
+
+ string = _setup(&state, args);
+ if (!string)
+ return NULL;
+
+ if (state.charsize == 1) {
+ status = sre_search(&state, PatternObject_GetCode(self));
+ } else {
+ status = sre_usearch(&state, PatternObject_GetCode(self));
+ }
+
+ _stack_free(&state);
+
+ return _pattern_new_match(self, &state, string, status);
+}
+
+static PyObject*
+_pattern_findall(PatternObject* self, PyObject* args)
+{
+ /* FIXME: not sure about the semantics here. this is good enough
+ for SXP, though... */
+
+ SRE_STATE state;
+ PyObject* string;
+ PyObject* list;
+ int status;
+
+ string = _setup(&state, args);
+ if (!string)
+ return NULL;
+
+ list = PyList_New(0);
+
+ while (state.start < state.end) {
+
+ PyObject* item;
+
+ state.ptr = state.start;
+
+ if (state.charsize == 1) {
+ status = sre_match(&state, PatternObject_GetCode(self));
+ } else {
+ status = sre_umatch(&state, PatternObject_GetCode(self));
+ }
+
+ if (status >= 0) {
+
+ if (status == 0)
+ state.ptr = (void*) ((char*) state.start + 1);
+
+ item = PySequence_GetSlice(
+ string,
+ ((char*) state.start - (char*) state.beginning),
+ ((char*) state.ptr - (char*) state.beginning));
+ if (!item)
+ goto error;
+ if (PyList_Append(list, item) < 0)
+ goto error;
+
+ state.start = state.ptr;
+
+ } else {
+
+ /* internal error */
+ PyErr_SetString(
+ PyExc_RuntimeError,
+ "internal error in regular expression engine"
+ );
+ goto error;
+
+ }
+ }
+
+ _stack_free(&state);
+
+ return list;
+
+error:
+ _stack_free(&state);
+ return NULL;
+
+}
+
+static PyMethodDef _pattern_methods[] = {
+ {"match", (PyCFunction) _pattern_match, 1},
+ {"search", (PyCFunction) _pattern_search, 1},
+ {"findall", (PyCFunction) _pattern_findall, 1},
+ {NULL, NULL}
+};
+
+static PyObject*
+_pattern_getattr(PatternObject* self, char* name)
+{
+ PyObject* res;
+
+ res = Py_FindMethod(_pattern_methods, (PyObject*) self, name);
+
+ if (res)
+ return res;
+
+ PyErr_Clear();
+
+ /* attributes */
+ if (!strcmp(name, "pattern")) {
+ Py_INCREF(self->pattern);
+ return self->pattern;
+ }
+
+ PyErr_SetString(PyExc_AttributeError, name);
+ return NULL;
+}
+
+statichere PyTypeObject Pattern_Type = {
+ PyObject_HEAD_INIT(NULL)
+ 0, "Pattern", sizeof(PatternObject), 0,
+ (destructor)_pattern_dealloc, /*tp_dealloc*/
+ 0, /*tp_print*/
+ (getattrfunc)_pattern_getattr, /*tp_getattr*/
+};
+
+/* -------------------------------------------------------------------- */
+/* match methods */
+
+static void
+_match_dealloc(MatchObject* self)
+{
+ Py_XDECREF(self->string);
+ Py_DECREF(self->pattern);
+ PyMem_DEL(self);
+}
+
+static PyObject*
+getslice_by_index(MatchObject* self, int index)
+{
+ if (index < 0 || index >= self->groups) {
+ /* raise IndexError if we were given a bad group number */
+ PyErr_SetString(
+ PyExc_IndexError,
+ "no such group"
+ );
+ return NULL;
+ }
+
+ if (self->string == Py_None || self->mark[index+index] < 0) {
+ /* return None if the string or group is undefined */
+ Py_INCREF(Py_None);
+ return Py_None;
+ }
+
+ return PySequence_GetSlice(
+ self->string, self->mark[index+index], self->mark[index+index+1]
+ );
+}
+
+static PyObject*
+getslice(MatchObject* self, PyObject* index)
+{
+ if (!PyInt_Check(index) && self->pattern->groupindex != NULL) {
+ /* FIXME: resource leak? */
+ index = PyObject_GetItem(self->pattern->groupindex, index);
+ if (!index)
+ return NULL;
+ }
+
+ if (PyInt_Check(index))
+ return getslice_by_index(self, (int) PyInt_AS_LONG(index));
+
+ return getslice_by_index(self, -1); /* signal error */
+}
+
+static PyObject*
+_match_group(MatchObject* self, PyObject* args)
+{
+ PyObject* result;
+ int i, size;
+
+ size = PyTuple_GET_SIZE(args);
+
+ switch (size) {
+ case 0:
+ result = getslice(self, Py_False); /* force error */
+ break;
+ case 1:
+ result = getslice(self, PyTuple_GET_ITEM(args, 0));
+ break;
+ default:
+ /* fetch multiple items */
+ result = PyTuple_New(size);
+ if (!result)
+ return NULL;
+ for (i = 0; i < size; i++) {
+ PyObject* item = getslice(self, PyTuple_GET_ITEM(args, i));
+ if (!item) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ PyTuple_SET_ITEM(result, i, item);
+ }
+ break;
+ }
+ return result;
+}
+
+static PyObject*
+_match_groups(MatchObject* self, PyObject* args)
+{
+ PyObject* result;
+ int index;
+
+ result = PyTuple_New(self->groups-1);
+ if (!result)
+ return NULL;
+
+ for (index = 1; index < self->groups; index++) {
+ PyObject* item;
+ /* FIXME: <fl> handle default! */
+ item = getslice_by_index(self, index);
+ if (!item) {
+ Py_DECREF(result);
+ return NULL;
+ }
+ PyTuple_SET_ITEM(result, index-1, item);
+ }
+
+ return result;
+}
+
+static PyObject*
+_match_groupdict(MatchObject* self, PyObject* args)
+{
+ PyObject* result;
+ PyObject* keys;
+ int index;
+
+ result = PyDict_New();
+ if (!result)
+ return NULL;
+ if (!self->pattern->groupindex)
+ return result;
+
+ keys = PyMapping_Keys(self->pattern->groupindex);
+ if (!keys)
+ return NULL;
+
+ for (index = 0; index < PySequence_Length(keys); index++) {
+ PyObject* key;
+ PyObject* item;
+ key = PySequence_GetItem(keys, index);
+ if (!key) {
+ Py_DECREF(keys);
+ Py_DECREF(result);
+ return NULL;
+ }
+ item = getslice(self, key);
+ if (!item) {
+ Py_DECREF(key);
+ Py_DECREF(keys);
+ Py_DECREF(result);
+ return NULL;
+ }
+ /* FIXME: <fl> this can fail, right? */
+ PyDict_SetItem(result, key, item);
+ }
+
+ Py_DECREF(keys);
+
+ return result;
+}
+
+static PyObject*
+_match_start(MatchObject* self, PyObject* args)
+{
+ int index = 0;
+ if (!PyArg_ParseTuple(args, "|i", &index))
+ return NULL;
+
+ if (index < 0 || index >= self->groups) {
+ PyErr_SetString(
+ PyExc_IndexError,
+ "no such group"
+ );
+ return NULL;
+ }
+
+ if (self->mark[index*2] < 0) {
+ Py_INCREF(Py_None);
+ return Py_None;
+ }
+
+ return Py_BuildValue("i", self->mark[index*2]);
+}
+
+static PyObject*
+_match_end(MatchObject* self, PyObject* args)
+{
+ int index = 0;
+ if (!PyArg_ParseTuple(args, "|i", &index))
+ return NULL;
+
+ if (index < 0 || index >= self->groups) {
+ PyErr_SetString(
+ PyExc_IndexError,
+ "no such group"
+ );
+ return NULL;
+ }
+
+ if (self->mark[index*2] < 0) {
+ Py_INCREF(Py_None);
+ return Py_None;
+ }
+
+ return Py_BuildValue("i", self->mark[index*2+1]);
+}
+
+static PyObject*
+_match_span(MatchObject* self, PyObject* args)
+{
+ int index = 0;
+ if (!PyArg_ParseTuple(args, "|i", &index))
+ return NULL;
+
+ if (index < 0 || index >= self->groups) {
+ PyErr_SetString(
+ PyExc_IndexError,
+ "no such group"
+ );
+ return NULL;
+ }
+
+ if (self->mark[index*2] < 0) {
+ Py_INCREF(Py_None);
+ return Py_None;
+ }
+
+ return Py_BuildValue("ii", self->mark[index*2], self->mark[index*2+1]);
+}
+
+static PyMethodDef _match_methods[] = {
+ {"group", (PyCFunction) _match_group, 1},
+ {"start", (PyCFunction) _match_start, 1},
+ {"end", (PyCFunction) _match_end, 1},
+ {"span", (PyCFunction) _match_span, 1},
+ {"groups", (PyCFunction) _match_groups, 1},
+ {"groupdict", (PyCFunction) _match_groupdict, 1},
+ {NULL, NULL}
+};
+
+static PyObject*
+_match_getattr(MatchObject* self, char* name)
+{
+ PyObject* res;
+
+ res = Py_FindMethod(_match_methods, (PyObject*) self, name);
+ if (res)
+ return res;
+
+ PyErr_Clear();
+
+ /* attributes! */
+ if (!strcmp(name, "string")) {
+ Py_INCREF(self->string);
+ return self->string;
+ }
+ if (!strcmp(name, "regs"))
+ /* FIXME: should return the whole list! */
+ return Py_BuildValue("((i,i))", self->mark[0], self->mark[1]);
+ if (!strcmp(name, "re")) {
+ Py_INCREF(self->pattern);
+ return (PyObject*) self->pattern;
+ }
+ if (!strcmp(name, "groupindex") && self->pattern->groupindex) {
+ Py_INCREF(self->pattern->groupindex);
+ return self->pattern->groupindex;
+ }
+ if (!strcmp(name, "pos"))
+ return Py_BuildValue("i", 0); /* FIXME */
+ if (!strcmp(name, "endpos"))
+ return Py_BuildValue("i", 0); /* FIXME */
+
+ PyErr_SetString(PyExc_AttributeError, name);
+ return NULL;
+}
+
+/* FIXME: implement setattr("string", None) as a special case (to
+ detach the associated string, if any */
+
+statichere PyTypeObject Match_Type = {
+ PyObject_HEAD_INIT(NULL)
+ 0, "Match",
+ sizeof(MatchObject), /* size of basic object */
+ sizeof(int), /* space for group item */
+ (destructor)_match_dealloc, /*tp_dealloc*/
+ 0, /*tp_print*/
+ (getattrfunc)_match_getattr, /*tp_getattr*/
+};
+
+static PyMethodDef _functions[] = {
+ {"compile", _compile, 1},
+ {"getcodesize", _getcodesize, 1},
+ {NULL, NULL}
+};
+
+void
+#ifdef WIN32
+__declspec(dllexport)
+#endif
+init_sre()
+{
+ /* Patch object types */
+ Pattern_Type.ob_type = Match_Type.ob_type = &PyType_Type;
+
+ Py_InitModule("_sre", _functions);
+}
+
+#endif
diff --git a/Modules/sre.h b/Modules/sre.h
new file mode 100644
index 0000000..2936b05
--- /dev/null
+++ b/Modules/sre.h
@@ -0,0 +1,38 @@
+/*
+ * Secret Labs' Regular Expression Engine
+ * $Id$
+ *
+ * simple regular expression matching engine
+ *
+ * Copyright (c) 1997-2000 by Secret Labs AB. All rights reserved.
+ *
+ * See the _sre.c file for information on usage and redistribution.
+ */
+
+#ifndef SRE_INCLUDED
+#define SRE_INCLUDED
+
+#include "sre_constants.h"
+
+/* Python objects */
+
+typedef struct {
+ PyObject_HEAD
+ PyObject* code; /* link to the code string object */
+ PyObject* pattern; /* link to the pattern source (or None) */
+ int groups;
+ PyObject* groupindex;
+} PatternObject;
+
+#define PatternObject_GetCode(o) ((void*) PyString_AS_STRING((o)->code))
+
+typedef struct {
+ PyObject_HEAD
+ PyObject* string; /* link to the target string */
+ PatternObject* pattern; /* link to the regex (pattern) object */
+ int groups; /* number of groups (start/end marks) */
+ int mark[2];
+} MatchObject;
+
+#endif
+
diff --git a/Modules/sre_constants.h b/Modules/sre_constants.h
new file mode 100644
index 0000000..6b940d3
--- /dev/null
+++ b/Modules/sre_constants.h
@@ -0,0 +1,27 @@
+/* generated by sre_constants.py */
+#define SRE_OP_FAILURE 0
+#define SRE_OP_SUCCESS 1
+#define SRE_OP_ANY 2
+#define SRE_OP_ASSERT 3
+#define SRE_OP_AT 4
+#define SRE_OP_BRANCH 5
+#define SRE_OP_CALL 6
+#define SRE_OP_CATEGORY 7
+#define SRE_OP_GROUP 8
+#define SRE_OP_GROUP_IGNORE 9
+#define SRE_OP_IN 10
+#define SRE_OP_IN_IGNORE 11
+#define SRE_OP_JUMP 12
+#define SRE_OP_LITERAL 13
+#define SRE_OP_LITERAL_IGNORE 14
+#define SRE_OP_MARK 15
+#define SRE_OP_MAX_REPEAT 16
+#define SRE_OP_MAX_UNTIL 17
+#define SRE_OP_MAX_REPEAT_ONE 18
+#define SRE_OP_MIN_REPEAT 19
+#define SRE_OP_MIN_UNTIL 20
+#define SRE_OP_NOT_LITERAL 21
+#define SRE_OP_NOT_LITERAL_IGNORE 22
+#define SRE_OP_NEGATE 23
+#define SRE_OP_RANGE 24
+#define SRE_OP_REPEAT 25