/* * Secret Labs' Regular Expression Engine * * regular expression matching engine * * partial history: * 1999-10-24 fl  created (based on existing template matcher code) * 2000-03-06 fl  first alpha, sort of * 2000-08-01 fl  fixes for 1.6b1 * 2000-08-07 fl  use PyOS_CheckStack() if available * 2000-09-20 fl  added expand method * 2001-03-20 fl  lots of fixes for 2.1b2 * 2001-04-15 fl  export copyright as Python attribute, not global * 2001-04-28 fl  added __copy__ methods (work in progress) * 2001-05-14 fl  fixes for 1.5.2 compatibility * 2001-07-01 fl  added BIGCHARSET support (from Martin von Loewis) * 2001-10-18 fl  fixed group reset issue (from Matthew Mueller) * 2001-10-20 fl  added split primitive; reenable unicode for 1.6/2.0/2.1 * 2001-10-21 fl  added sub/subn primitive * 2001-10-24 fl  added finditer primitive (for 2.2 only) * 2001-12-07 fl  fixed memory leak in sub/subn (Guido van Rossum) * 2002-11-09 fl  fixed empty sub/subn return type * 2003-04-18 mvl fully support 4-byte codes * 2003-10-17 gn  implemented non recursive scheme * * Copyright (c) 1997-2001 by Secret Labs AB.  All rights reserved. * * This version of the SRE library can be redistributed under CNRI's * Python 1.6 license.  For any other use, please contact Secret Labs * AB (info@pythonware.com). * * 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 static char copyright[] =    " SRE 2.2.2 Copyright (c) 1997-2002 by Secret Labs AB "; #define PY_SSIZE_T_CLEAN #include "Python.h"#include "structmember.h" /* offsetof */ #include "sre.h" #include <ctype.h> /* name of this module, minus the leading underscore */#if !defined(SRE_MODULE)#define SRE_MODULE "sre"#endif #define SRE_PY_MODULE "re" /* defining this one enables tracing */#undef VERBOSE #if PY_VERSION_HEX >= 0x01060000#if PY_VERSION_HEX  < 0x02020000 || defined(Py_USING_UNICODE)/* defining this enables unicode support (default under 1.6a1 and later) */#define HAVE_UNICODE#endif#endif /* -------------------------------------------------------------------- *//* optional features */ /* enables fast searching */#define USE_FAST_SEARCH /* enables aggressive inlining (always on for Visual C) */#undef USE_INLINE /* enables copy/deepcopy handling (work in progress) */#undef USE_BUILTIN_COPY #if PY_VERSION_HEX < 0x01060000#define PyObject_DEL(op) PyMem_DEL((op))#endif /* -------------------------------------------------------------------- */ #if defined(_MSC_VER)#pragma optimize("agtw", on) /* doesn't seem to make much difference... */#pragma warning(disable: 4710) /* who cares if functions are not inlined ;-) *//* fastest possible local call under MSVC */#define LOCAL(type) static __inline type __fastcall#elif defined(USE_INLINE)#define LOCAL(type) static inline type#else#define LOCAL(type) static type#endif /* error codes */#define SRE_ERROR_ILLEGAL -1 /* illegal opcode */#define SRE_ERROR_STATE -2 /* illegal state */#define SRE_ERROR_RECURSION_LIMIT -3 /* runaway recursion */#define SRE_ERROR_MEMORY -9 /* out of memory */ #if defined(VERBOSE)#define TRACE(v) printf v#else#define TRACE(v)#endif /* -------------------------------------------------------------------- *//* search engine state */ /* default character predicates (run sre_chars.py to regenerate tables) */ #define SRE_DIGIT_MASK 1#define SRE_SPACE_MASK 2#define SRE_LINEBREAK_MASK 4#define SRE_ALNUM_MASK 8#define SRE_WORD_MASK 16 /* FIXME: this assumes ASCII.  create tables in init_sre() instead */ static char sre_char_info[128] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 2,2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0,0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25, 25, 25, 25, 25, 25, 25, 25,25, 25, 0, 0, 0, 0, 0, 0, 0, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 0, 0,0, 0, 16, 0, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 0, 0, 0, 0, 0 }; static char sre_char_lower[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,61, 62, 63, 64, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107,108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121,122, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105,106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,120, 121, 122, 123, 124, 125, 126, 127 }; #define SRE_IS_DIGIT(ch)\    ((ch) < 128 ? (sre_char_info[(ch)] & SRE_DIGIT_MASK) : 0)#define SRE_IS_SPACE(ch)\    ((ch) < 128 ? (sre_char_info[(ch)] & SRE_SPACE_MASK) : 0)#define SRE_IS_LINEBREAK(ch)\    ((ch) < 128 ? (sre_char_info[(ch)] & SRE_LINEBREAK_MASK) : 0)#define SRE_IS_ALNUM(ch)\    ((ch) < 128 ? (sre_char_info[(ch)] & SRE_ALNUM_MASK) : 0)#define SRE_IS_WORD(ch)\    ((ch) < 128 ? (sre_char_info[(ch)] & SRE_WORD_MASK) : 0) static unsigned int sre_lower(unsigned int ch){    return ((ch) < 128 ? (unsigned int)sre_char_lower[ch] : ch);} /* locale-specific character predicates *//* !(c & ~N) == (c < N+1) for any unsigned c, this avoids * warnings when c's type supports only numbers < N+1 */#define SRE_LOC_IS_DIGIT(ch) (!((ch) & ~255) ? isdigit((ch)) : 0)#define SRE_LOC_IS_SPACE(ch) (!((ch) & ~255) ? isspace((ch)) : 0)#define SRE_LOC_IS_LINEBREAK(ch) ((ch) == '\n')#define SRE_LOC_IS_ALNUM(ch) (!((ch) & ~255) ? isalnum((ch)) : 0)#define SRE_LOC_IS_WORD(ch) (SRE_LOC_IS_ALNUM((ch)) || (ch) == '_') static unsigned int sre_lower_locale(unsigned int ch){    return ((ch) < 256 ? (unsigned int)tolower((ch)) : ch);} /* unicode-specific character predicates */ #if defined(HAVE_UNICODE) #define SRE_UNI_IS_DIGIT(ch) Py_UNICODE_ISDIGIT((Py_UNICODE)(ch))#define SRE_UNI_IS_SPACE(ch) Py_UNICODE_ISSPACE((Py_UNICODE)(ch))#define SRE_UNI_IS_LINEBREAK(ch) Py_UNICODE_ISLINEBREAK((Py_UNICODE)(ch))#define SRE_UNI_IS_ALNUM(ch) Py_UNICODE_ISALNUM((Py_UNICODE)(ch))#define SRE_UNI_IS_WORD(ch) (SRE_UNI_IS_ALNUM((ch)) || (ch) == '_') static unsigned int sre_lower_unicode(unsigned int ch){    return (unsigned int) Py_UNICODE_TOLOWER((Py_UNICODE)(ch));} #endif LOCAL(int)sre_category(SRE_CODE category, unsigned int ch){    switch (category) {     case SRE_CATEGORY_DIGIT:        return SRE_IS_DIGIT(ch);    case SRE_CATEGORY_NOT_DIGIT:        return !SRE_IS_DIGIT(ch);    case SRE_CATEGORY_SPACE:        return SRE_IS_SPACE(ch);    case SRE_CATEGORY_NOT_SPACE:        return !SRE_IS_SPACE(ch);    case SRE_CATEGORY_WORD:        return SRE_IS_WORD(ch);    case SRE_CATEGORY_NOT_WORD:        return !SRE_IS_WORD(ch);    case SRE_CATEGORY_LINEBREAK:        return SRE_IS_LINEBREAK(ch);    case SRE_CATEGORY_NOT_LINEBREAK:        return !SRE_IS_LINEBREAK(ch);     case SRE_CATEGORY_LOC_WORD:        return SRE_LOC_IS_WORD(ch);    case SRE_CATEGORY_LOC_NOT_WORD:        return !SRE_LOC_IS_WORD(ch); #if defined(HAVE_UNICODE)    case SRE_CATEGORY_UNI_DIGIT:        return SRE_UNI_IS_DIGIT(ch);    case SRE_CATEGORY_UNI_NOT_DIGIT:        return !SRE_UNI_IS_DIGIT(ch);    case SRE_CATEGORY_UNI_SPACE:        return SRE_UNI_IS_SPACE(ch);    case SRE_CATEGORY_UNI_NOT_SPACE:        return !SRE_UNI_IS_SPACE(ch);    case SRE_CATEGORY_UNI_WORD:        return SRE_UNI_IS_WORD(ch);    case SRE_CATEGORY_UNI_NOT_WORD:        return !SRE_UNI_IS_WORD(ch);    case SRE_CATEGORY_UNI_LINEBREAK:        return SRE_UNI_IS_LINEBREAK(ch);    case SRE_CATEGORY_UNI_NOT_LINEBREAK:        return !SRE_UNI_IS_LINEBREAK(ch);#else    case SRE_CATEGORY_UNI_DIGIT:        return SRE_IS_DIGIT(ch);    case SRE_CATEGORY_UNI_NOT_DIGIT:        return !SRE_IS_DIGIT(ch);    case SRE_CATEGORY_UNI_SPACE:        return SRE_IS_SPACE(ch);    case SRE_CATEGORY_UNI_NOT_SPACE:        return !SRE_IS_SPACE(ch);    case SRE_CATEGORY_UNI_WORD:        return SRE_LOC_IS_WORD(ch);    case SRE_CATEGORY_UNI_NOT_WORD:        return !SRE_LOC_IS_WORD(ch);    case SRE_CATEGORY_UNI_LINEBREAK:        return SRE_IS_LINEBREAK(ch);    case SRE_CATEGORY_UNI_NOT_LINEBREAK:        return !SRE_IS_LINEBREAK(ch);#endif    }    return 0;} /* helpers */ static voiddata_stack_dealloc(SRE_STATE* state){    if (state->data_stack) {        PyMem_FREE(state->data_stack);        state->data_stack = NULL;    }    state->data_stack_size = state->data_stack_base = 0;} static intdata_stack_grow(SRE_STATE* state, Py_ssize_t size){    Py_ssize_t minsize, cursize;    minsize = state->data_stack_base+size;    cursize = state->data_stack_size;    if (cursize < minsize) {        void* stack;        cursize = minsize+minsize/4+1024;        TRACE(("allocate/grow stack %d\n", cursize));        stack = PyMem_REALLOC(state->data_stack, cursize);        if (!stack) {            data_stack_dealloc(state);            return SRE_ERROR_MEMORY;        }        state->data_stack = (char *)stack;        state->data_stack_size = cursize;    }    return 0;} /* generate 8-bit version */ #define SRE_CHAR unsigned char#define SRE_AT sre_at#define SRE_COUNT sre_count#define SRE_CHARSET sre_charset#define SRE_INFO sre_info#define SRE_MATCH sre_match#define SRE_MATCH_CONTEXT sre_match_context#define SRE_SEARCH sre_search#define SRE_LITERAL_TEMPLATE sre_literal_template #if defined(HAVE_UNICODE) #define SRE_RECURSIVE#include "_sre.c"#undef SRE_RECURSIVE #undef SRE_LITERAL_TEMPLATE#undef SRE_SEARCH#undef SRE_MATCH#undef SRE_MATCH_CONTEXT#undef SRE_INFO#undef SRE_CHARSET#undef SRE_COUNT#undef SRE_AT#undef SRE_CHAR /* generate 16-bit unicode version */ #define SRE_CHAR Py_UNICODE#define SRE_AT sre_uat#define SRE_COUNT sre_ucount#define SRE_CHARSET sre_ucharset#define SRE_INFO sre_uinfo#define SRE_MATCH sre_umatch#define SRE_MATCH_CONTEXT sre_umatch_context#define SRE_SEARCH sre_usearch#define SRE_LITERAL_TEMPLATE sre_uliteral_template#endif #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 */     Py_ssize_t thisp, thatp;     switch (at) {     case SRE_AT_BEGINNING:    case SRE_AT_BEGINNING_STRING:        return ((void*) ptr == state->beginning);     case SRE_AT_BEGINNING_LINE:        return ((void*) ptr == state->beginning ||                SRE_IS_LINEBREAK((int) ptr[-1]));     case SRE_AT_END:        return (((void*) (ptr+1) == state->end &&                 SRE_IS_LINEBREAK((int) ptr[0])) ||                ((void*) ptr == state->end));     case SRE_AT_END_LINE:        return ((void*) ptr == state->end ||                SRE_IS_LINEBREAK((int) ptr[0]));     case SRE_AT_END_STRING:        return ((void*) ptr == state->end);     case SRE_AT_BOUNDARY:        if (state->beginning == state->end)            return 0;        thatp = ((void*) ptr > state->beginning) ?            SRE_IS_WORD((int) ptr[-1]) : 0;        thisp = ((void*) ptr < state->end) ?            SRE_IS_WORD((int) ptr[0]) : 0;        return thisp != thatp;     case SRE_AT_NON_BOUNDARY:        if (state->beginning == state->end)            return 0;        thatp = ((void*) ptr > state->beginning) ?            SRE_IS_WORD((int) ptr[-1]) : 0;        thisp = ((void*) ptr < state->end) ?            SRE_IS_WORD((int) ptr[0]) : 0;        return thisp == thatp;     case SRE_AT_LOC_BOUNDARY:        if (state->beginning == state->end)            return 0;        thatp = ((void*) ptr > state->beginning) ?            SRE_LOC_IS_WORD((int) ptr[-1]) : 0;        thisp = ((void*) ptr < state->end) ?            SRE_LOC_IS_WORD((int) ptr[0]) : 0;        return thisp != thatp;     case SRE_AT_LOC_NON_BOUNDARY:        if (state->beginning == state->end)            return 0;        thatp = ((void*) ptr > state->beginning) ?            SRE_LOC_IS_WORD((int) ptr[-1]) : 0;        thisp = ((void*) ptr < state->end) ?            SRE_LOC_IS_WORD((int) ptr[0]) : 0;        return thisp == thatp; #if defined(HAVE_UNICODE)    case SRE_AT_UNI_BOUNDARY:        if (state->beginning == state->end)            return 0;        thatp = ((void*) ptr > state->beginning) ?            SRE_UNI_IS_WORD((int) ptr[-1]) : 0;        thisp = ((void*) ptr < state->end) ?            SRE_UNI_IS_WORD((int) ptr[0]) : 0;        return thisp != thatp;     case SRE_AT_UNI_NON_BOUNDARY:        if (state->beginning == state->end)            return 0;        thatp = ((void*) ptr > state->beginning) ?            SRE_UNI_IS_WORD((int) ptr[-1]) : 0;        thisp = ((void*) ptr < state->end) ?            SRE_UNI_IS_WORD((int) ptr[0]) : 0;        return thisp == thatp;#endif     }     return 0;} LOCAL(int)SRE_CHARSET(SRE_CODE* set, SRE_CODE ch){    /* check if character is a member of the given set */     int ok = 1;     for (;;) {        switch (*set++) {         case SRE_OP_FAILURE:            return !ok;         case SRE_OP_LITERAL:            /* <LITERAL> <code> */            if (ch == set[0])                return ok;            set++;            break;         case SRE_OP_CATEGORY:            /* <CATEGORY> <code> */            if (sre_category(set[0], (int) ch))                return ok;            set += 1;            break;         case SRE_OP_CHARSET:            if (sizeof(SRE_CODE) == 2) {                /* <CHARSET> <bitmap> (16 bits per code word) */                if (ch < 256 && (set[ch >> 4] & (1 << (ch & 15))))                    return ok;                set += 16;            }            else {                /* <CHARSET> <bitmap> (32 bits per code word) */                if (ch < 256 && (set[ch >> 5] & (1 << (ch & 31))))                    return ok;                set += 8;            }            break;         case SRE_OP_RANGE:            /* <RANGE> <lower> <upper> */            if (set[0] <= ch && ch <= set[1])                return ok;            set += 2;            break;         case SRE_OP_NEGATE:            ok = !ok;            break;         case SRE_OP_BIGCHARSET:            /* <BIGCHARSET> <blockcount> <256 blockindices> <blocks> */        {            Py_ssize_t count, block;            count = *(set++);             if (sizeof(SRE_CODE) == 2) {                block = ((unsigned char*)set)[ch >> 8];                set += 128;                if (set[block*16 + ((ch & 255)>>4)] & (1 << (ch & 15)))                    return ok;                set += count*16;            }            else {                /* !(c & ~N) == (c < N+1) for any unsigned c, this avoids                 * warnings when c's type supports only numbers < N+1 */                if (!(ch & ~65535))                    block = ((unsigned char*)set)[ch >> 8];                else                    block = -1;                set += 64;                if (block >=0 &&                    (set[block*8 + ((ch & 255)>>5)] & (1 << (ch & 31))))

Lines 1–500 of 3429. Load more