_sre.c

/*
 * 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.
 */

#ifndefSRE_RECURSIVE

staticcharcopyright[] =
" SRE 2.2.2 Copyright (c) 1997-2002 by Secret Labs AB ";

#definePY_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)
#defineSRE_MODULE "sre"
#endif

#defineSRE_PY_MODULE "re"

/* defining this one enables tracing */
#undef VERBOSE

#ifPY_VERSION_HEX >= 0x01060000
#ifPY_VERSION_HEX<0x02020000|| defined(Py_USING_UNICODE)
/* defining this enables unicode support (default under 1.6a1 and later) */
#defineHAVE_UNICODE
#endif
#endif

/* -------------------------------------------------------------------- */
/* optional features */

/* enables fast searching */
#defineUSE_FAST_SEARCH

/* enables aggressive inlining (always on for Visual C) */
#undef USE_INLINE

/* enables copy/deepcopy handling (work in progress) */
#undef USE_BUILTIN_COPY

#ifPY_VERSION_HEX<0x01060000
#definePyObject_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 */
#defineLOCAL(type) static __inline type __fastcall
#elif defined(USE_INLINE)
#defineLOCAL(type) static inline type
#else
#defineLOCAL(type) static type
#endif

/* error codes */
#defineSRE_ERROR_ILLEGAL -1 /* illegal opcode */
#defineSRE_ERROR_STATE -2 /* illegal state */
#defineSRE_ERROR_RECURSION_LIMIT -3 /* runaway recursion */
#defineSRE_ERROR_MEMORY -9 /* out of memory */
#defineSRE_ERROR_INTERRUPTED -10 /* signal handler raised exception */

#if defined(VERBOSE)
#defineTRACE(v) printf v
#else
#defineTRACE(v)
#endif

/* -------------------------------------------------------------------- */
/* search engine state */

/* default character predicates (run sre_chars.py to regenerate tables) */

#defineSRE_DIGIT_MASK 1
#defineSRE_SPACE_MASK 2
#defineSRE_LINEBREAK_MASK 4
#defineSRE_ALNUM_MASK 8
#defineSRE_WORD_MASK 16

/* FIXME: this assumes ASCII. create tables in init_sre() instead */

staticcharsre_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 };

staticcharsre_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 };

#defineSRE_IS_DIGIT(ch)\
 ((ch) < 128 ? (sre_char_info[(ch)] & SRE_DIGIT_MASK) : 0)
#defineSRE_IS_SPACE(ch)\
 ((ch) < 128 ? (sre_char_info[(ch)] & SRE_SPACE_MASK) : 0)
#defineSRE_IS_LINEBREAK(ch)\
 ((ch) < 128 ? (sre_char_info[(ch)] & SRE_LINEBREAK_MASK) : 0)
#defineSRE_IS_ALNUM(ch)\
 ((ch) < 128 ? (sre_char_info[(ch)] & SRE_ALNUM_MASK) : 0)
#defineSRE_IS_WORD(ch)\
 ((ch) < 128 ? (sre_char_info[(ch)] & SRE_WORD_MASK) : 0)

staticunsigned intsre_lower(unsigned intch)
{
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 */
#defineSRE_LOC_IS_DIGIT(ch) (!((ch) & ~255) ? isdigit((ch)) : 0)
#defineSRE_LOC_IS_SPACE(ch) (!((ch) & ~255) ? isspace((ch)) : 0)
#defineSRE_LOC_IS_LINEBREAK(ch) ((ch) == '\n')
#defineSRE_LOC_IS_ALNUM(ch) (!((ch) & ~255) ? isalnum((ch)) : 0)
#defineSRE_LOC_IS_WORD(ch) (SRE_LOC_IS_ALNUM((ch)) || (ch) == '_')

staticunsigned intsre_lower_locale(unsigned intch)
{
return ((ch) <256 ? (unsigned int)tolower((ch)) : ch);
}

/* unicode-specific character predicates */

#if defined(HAVE_UNICODE)

#defineSRE_UNI_IS_DIGIT(ch) Py_UNICODE_ISDECIMAL((Py_UNICODE)(ch))
#defineSRE_UNI_IS_SPACE(ch) Py_UNICODE_ISSPACE((Py_UNICODE)(ch))
#defineSRE_UNI_IS_LINEBREAK(ch) Py_UNICODE_ISLINEBREAK((Py_UNICODE)(ch))
#defineSRE_UNI_IS_ALNUM(ch) Py_UNICODE_ISALNUM((Py_UNICODE)(ch))
#defineSRE_UNI_IS_WORD(ch) (SRE_UNI_IS_ALNUM((ch)) || (ch) == '_')

staticunsigned intsre_lower_unicode(unsigned intch)
{
return (unsigned int) Py_UNICODE_TOLOWER((Py_UNICODE)(ch));
}

#endif

LOCAL(int)
sre_category(SRE_CODEcategory, unsigned intch)
{
switch (category) {

caseSRE_CATEGORY_DIGIT:
returnSRE_IS_DIGIT(ch);
caseSRE_CATEGORY_NOT_DIGIT:
return !SRE_IS_DIGIT(ch);
caseSRE_CATEGORY_SPACE:
returnSRE_IS_SPACE(ch);
caseSRE_CATEGORY_NOT_SPACE:
return !SRE_IS_SPACE(ch);
caseSRE_CATEGORY_WORD:
returnSRE_IS_WORD(ch);
caseSRE_CATEGORY_NOT_WORD:
return !SRE_IS_WORD(ch);
caseSRE_CATEGORY_LINEBREAK:
returnSRE_IS_LINEBREAK(ch);
caseSRE_CATEGORY_NOT_LINEBREAK:
return !SRE_IS_LINEBREAK(ch);

caseSRE_CATEGORY_LOC_WORD:
returnSRE_LOC_IS_WORD(ch);
caseSRE_CATEGORY_LOC_NOT_WORD:
return !SRE_LOC_IS_WORD(ch);

#if defined(HAVE_UNICODE)
caseSRE_CATEGORY_UNI_DIGIT:
returnSRE_UNI_IS_DIGIT(ch);
caseSRE_CATEGORY_UNI_NOT_DIGIT:
return !SRE_UNI_IS_DIGIT(ch);
caseSRE_CATEGORY_UNI_SPACE:
returnSRE_UNI_IS_SPACE(ch);
caseSRE_CATEGORY_UNI_NOT_SPACE:
return !SRE_UNI_IS_SPACE(ch);
caseSRE_CATEGORY_UNI_WORD:
returnSRE_UNI_IS_WORD(ch);
caseSRE_CATEGORY_UNI_NOT_WORD:
return !SRE_UNI_IS_WORD(ch);
caseSRE_CATEGORY_UNI_LINEBREAK:
returnSRE_UNI_IS_LINEBREAK(ch);
caseSRE_CATEGORY_UNI_NOT_LINEBREAK:
return !SRE_UNI_IS_LINEBREAK(ch);
#else
caseSRE_CATEGORY_UNI_DIGIT:
returnSRE_IS_DIGIT(ch);
caseSRE_CATEGORY_UNI_NOT_DIGIT:
return !SRE_IS_DIGIT(ch);
caseSRE_CATEGORY_UNI_SPACE:
returnSRE_IS_SPACE(ch);
caseSRE_CATEGORY_UNI_NOT_SPACE:
return !SRE_IS_SPACE(ch);
caseSRE_CATEGORY_UNI_WORD:
returnSRE_LOC_IS_WORD(ch);
caseSRE_CATEGORY_UNI_NOT_WORD:
return !SRE_LOC_IS_WORD(ch);
caseSRE_CATEGORY_UNI_LINEBREAK:
returnSRE_IS_LINEBREAK(ch);
caseSRE_CATEGORY_UNI_NOT_LINEBREAK:
return !SRE_IS_LINEBREAK(ch);
#endif
 }
return0;
}

/* helpers */

staticvoid
data_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;
}

staticint
data_stack_grow(SRE_STATE*state, Py_ssize_tsize)
{
Py_ssize_tminsize, 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 %"PY_FORMAT_SIZE_T"d\n", cursize));
stack=PyMem_REALLOC(state->data_stack, cursize);
if (!stack) {
data_stack_dealloc(state);
returnSRE_ERROR_MEMORY;
 }
state->data_stack= (char*)stack;
state->data_stack_size=cursize;
 }
return0;
}

/* generate 8-bit version */

#defineSRE_CHAR unsigned char
#defineSRE_AT sre_at
#defineSRE_COUNT sre_count
#defineSRE_CHARSET sre_charset
#defineSRE_INFO sre_info
#defineSRE_MATCH sre_match
#defineSRE_MATCH_CONTEXT sre_match_context
#defineSRE_SEARCH sre_search
#defineSRE_LITERAL_TEMPLATE sre_literal_template

#if defined(HAVE_UNICODE)

#defineSRE_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 */

#defineSRE_CHAR Py_UNICODE
#defineSRE_AT sre_uat
#defineSRE_COUNT sre_ucount
#defineSRE_CHARSET sre_ucharset
#defineSRE_INFO sre_uinfo
#defineSRE_MATCH sre_umatch
#defineSRE_MATCH_CONTEXT sre_umatch_context
#defineSRE_SEARCH sre_usearch
#defineSRE_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_CODEat)
{
/* check if pointer is at given position */

Py_ssize_tthisp, thatp;

switch (at) {

caseSRE_AT_BEGINNING:
caseSRE_AT_BEGINNING_STRING:
return ((void*) ptr==state->beginning);

caseSRE_AT_BEGINNING_LINE:
return ((void*) ptr==state->beginning||
SRE_IS_LINEBREAK((int) ptr[-1]));

caseSRE_AT_END:
return (((SRE_CHAR*)state->end-ptr==1&&
SRE_IS_LINEBREAK((int) ptr[0])) ||
 ((void*) ptr==state->end));

caseSRE_AT_END_LINE:
return ((void*) ptr==state->end||
SRE_IS_LINEBREAK((int) ptr[0]));

caseSRE_AT_END_STRING:
return ((void*) ptr==state->end);

caseSRE_AT_BOUNDARY:
if (state->beginning==state->end)
return0;
thatp= ((void*) ptr>state->beginning) ?
SRE_IS_WORD((int) ptr[-1]) : 0;
thisp= ((void*) ptr<state->end) ?
SRE_IS_WORD((int) ptr[0]) : 0;
returnthisp!=thatp;

caseSRE_AT_NON_BOUNDARY:
if (state->beginning==state->end)
return0;
thatp= ((void*) ptr>state->beginning) ?
SRE_IS_WORD((int) ptr[-1]) : 0;
thisp= ((void*) ptr<state->end) ?
SRE_IS_WORD((int) ptr[0]) : 0;
returnthisp==thatp;

caseSRE_AT_LOC_BOUNDARY:
if (state->beginning==state->end)
return0;
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;
returnthisp!=thatp;

caseSRE_AT_LOC_NON_BOUNDARY:
if (state->beginning==state->end)
return0;
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;
returnthisp==thatp;

#if defined(HAVE_UNICODE)
caseSRE_AT_UNI_BOUNDARY:
if (state->beginning==state->end)
return0;
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;
returnthisp!=thatp;

caseSRE_AT_UNI_NON_BOUNDARY:
if (state->beginning==state->end)
return0;
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;
returnthisp==thatp;
#endif

 }

return0;
}

LOCAL(int)
SRE_CHARSET(SRE_CODE*set, SRE_CODEch)
{
/* check if character is a member of the given set */

intok=1;

for (;;) {
switch (*set++) {

caseSRE_OP_FAILURE:
return !ok;

caseSRE_OP_LITERAL:
/* <LITERAL> <code> */
if (ch==set[0])
returnok;
set++;
break;

caseSRE_OP_CATEGORY:
/* <CATEGORY> <code> */
if (sre_category(set[0], (int) ch))
returnok;
set+=1;
break;

caseSRE_OP_CHARSET:
if (sizeof(SRE_CODE) ==2) {
/* <CHARSET> <bitmap> (16 bits per code word) */
if (ch<256&& (set[ch >> 4] & (1 << (ch&15))))
returnok;
set+=16;
 }
else {
/* <CHARSET> <bitmap> (32 bits per code word) */
if (ch<256&& (set[ch >> 5] & (1u << (ch&31))))
returnok;
set+=8;
 }
break;

caseSRE_OP_RANGE:
/* <RANGE> <lower> <upper> */
if (set[0] <= ch&&ch <= set[1])
returnok;
set+=2;
break;

caseSRE_OP_NEGATE:
ok= !ok;
break;

caseSRE_OP_BIGCHARSET:
/* <BIGCHARSET> <blockcount> <256 blockindices> <blocks> */
 {
Py_ssize_tcount, 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)))
returnok;
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)] & (1u << (ch&31))))
returnok;
set+=count*8;
 }
break;
 }

default:
/* internal error -- there's not much we can do about it
 here, so let's just pretend it didn't match... */
return0;
 }
 }
}

LOCAL(Py_ssize_t) SRE_MATCH(SRE_STATE*state, SRE_CODE*pattern);

LOCAL(Py_ssize_t)
SRE_COUNT(SRE_STATE*state, SRE_CODE*pattern, Py_ssize_tmaxcount)
{
SRE_CODEchr;
SRE_CHAR*ptr= (SRE_CHAR*)state->ptr;
SRE_CHAR*end= (SRE_CHAR*)state->end;
Py_ssize_ti;

/* adjust end */
if (maxcount<end-ptr&&maxcount!=SRE_MAXREPEAT)
end=ptr+maxcount;

switch (pattern[0]) {

caseSRE_OP_IN:
/* repeated set */
TRACE(("|%p|%p|COUNT IN\n", pattern, ptr));
while (ptr<end&&SRE_CHARSET(pattern+2, *ptr))
ptr++;
break;

caseSRE_OP_ANY:
/* repeated dot wildcard. */
TRACE(("|%p|%p|COUNT ANY\n", pattern, ptr));
while (ptr<end&& !SRE_IS_LINEBREAK(*ptr))
ptr++;
break;

caseSRE_OP_ANY_ALL:
/* repeated dot wildcard. skip to the end of the target
 string, and backtrack from there */
TRACE(("|%p|%p|COUNT ANY_ALL\n", pattern, ptr));
ptr=end;
break;

caseSRE_OP_LITERAL:
/* repeated literal */
chr=pattern[1];
TRACE(("|%p|%p|COUNT LITERAL %d\n", pattern, ptr, chr));
while (ptr<end&& (SRE_CODE) *ptr==chr)
ptr++;
break;

caseSRE_OP_LITERAL_IGNORE:
/* repeated literal */
chr=pattern[1];
TRACE(("|%p|%p|COUNT LITERAL_IGNORE %d\n", pattern, ptr, chr));
while (ptr<end&& (SRE_CODE) state->lower(*ptr) ==chr)
ptr++;
break;

caseSRE_OP_NOT_LITERAL:
/* repeated non-literal */
chr=pattern[1];
TRACE(("|%p|%p|COUNT NOT_LITERAL %d\n", pattern, ptr, chr));
while (ptr<end&& (SRE_CODE) *ptr!=chr)
ptr++;
break;

caseSRE_OP_NOT_LITERAL_IGNORE:
/* repeated non-literal */
chr=pattern[1];
TRACE(("|%p|%p|COUNT NOT_LITERAL_IGNORE %d\n", pattern, ptr, chr));
while (ptr<end&& (SRE_CODE) state->lower(*ptr) !=chr)
ptr++;
break;

default:
/* repeated single character pattern */
TRACE(("|%p|%p|COUNT SUBPATTERN\n", pattern, ptr));
while ((SRE_CHAR*) state->ptr<end) {
i=SRE_MATCH(state, pattern);
if (i<0)
returni;
if (!i)
break;
 }
TRACE(("|%p|%p|COUNT %"PY_FORMAT_SIZE_T"d\n", pattern, ptr,
 (SRE_CHAR*) state->ptr-ptr));
return (SRE_CHAR*) state->ptr-ptr;
 }

TRACE(("|%p|%p|COUNT %"PY_FORMAT_SIZE_T"d\n", pattern, ptr,
ptr- (SRE_CHAR*) state->ptr));
returnptr- (SRE_CHAR*) state->ptr;
}

#if0/* not used in this release */
LOCAL(int)
SRE_INFO(SRE_STATE*state, SRE_CODE*pattern)
{
/* check if an SRE_OP_INFO block matches at the current position.
 returns the number of SRE_CODE objects to skip if successful, 0
 if no match */

SRE_CHAR*end=state->end;
SRE_CHAR*ptr=state->ptr;
Py_ssize_ti;

/* check minimal length */
if (pattern[3] && (end-ptr) <pattern[3])
return0;

/* check known prefix */
if (pattern[2] &SRE_INFO_PREFIX&&pattern[5] >1) {
/* <length> <skip> <prefix data> <overlap data> */
for (i=0; i<pattern[5]; i++)
if ((SRE_CODE) ptr[i] !=pattern[7+i])
return0;
returnpattern[0] +2*pattern[6];
 }
returnpattern[0];
}
#endif

/* The macros below should be used to protect recursive SRE_MATCH()
 * calls that *failed* and do *not* return immediately (IOW, those
 * that will backtrack). Explaining:
 *
 * - Recursive SRE_MATCH() returned true: that's usually a success
 * (besides atypical cases like ASSERT_NOT), therefore there's no
 * reason to restore lastmark;
 *
 * - Recursive SRE_MATCH() returned false but the current SRE_MATCH()
 * is returning to the caller: If the current SRE_MATCH() is the
 * top function of the recursion, returning false will be a matching
 * failure, and it doesn't matter where lastmark is pointing to.
 * If it's *not* the top function, it will be a recursive SRE_MATCH()
 * failure by itself, and the calling SRE_MATCH() will have to deal
 * with the failure by the same rules explained here (it will restore
 * lastmark by itself if necessary);
 *
 * - Recursive SRE_MATCH() returned false, and will continue the
 * outside 'for' loop: must be protected when breaking, since the next
 * OP could potentially depend on lastmark;
 *
 * - Recursive SRE_MATCH() returned false, and will be called again
 * inside a local for/while loop: must be protected between each
 * loop iteration, since the recursive SRE_MATCH() could do anything,
 * and could potentially depend on lastmark.
 *
 * For more information, check the discussion at SF patch #712900.
 */
#defineLASTMARK_SAVE() \
 do { \
 ctx->lastmark = state->lastmark; \
 ctx->lastindex = state->lastindex; \
 } while (0)
#defineLASTMARK_RESTORE() \
 do { \
 state->lastmark = ctx->lastmark; \
 state->lastindex = ctx->lastindex; \
 } while (0)

#defineRETURN_ERROR(i) do { return i; } while(0)
#defineRETURN_FAILURE do { ret = 0; goto exit; } while(0)
#defineRETURN_SUCCESS do { ret = 1; goto exit; } while(0)

#defineRETURN_ON_ERROR(i) \
 do { if (i < 0) RETURN_ERROR(i); } while (0)
#defineRETURN_ON_SUCCESS(i) \
 do { RETURN_ON_ERROR(i); if (i > 0) RETURN_SUCCESS; } while (0)
#defineRETURN_ON_FAILURE(i) \
 do { RETURN_ON_ERROR(i); if (i == 0) RETURN_FAILURE; } while (0)

#defineSFY(x) #x

#defineDATA_STACK_ALLOC(state, type, ptr) \
do { \
 alloc_pos = state->data_stack_base; \
 TRACE(("allocating %s in %" PY_FORMAT_SIZE_T "d " \
 "(%" PY_FORMAT_SIZE_T "d)\n", \
 SFY(type), alloc_pos, sizeof(type))); \
 if (sizeof(type) > state->data_stack_size - alloc_pos) { \
 int j = data_stack_grow(state, sizeof(type)); \
 if (j < 0) return j; \
 if (ctx_pos != -1) \
 DATA_STACK_LOOKUP_AT(state, SRE_MATCH_CONTEXT, ctx, ctx_pos); \
 } \
 ptr = (type*)(state->data_stack+alloc_pos); \
 state->data_stack_base += sizeof(type); \
} while (0)

#defineDATA_STACK_LOOKUP_AT(state, type, ptr, pos) \
do { \
 TRACE(("looking up %s at %" PY_FORMAT_SIZE_T "d\n", SFY(type), pos)); \
 ptr = (type*)(state->data_stack+pos); \
} while (0)

#defineDATA_STACK_PUSH(state, data, size) \
do { \
 TRACE(("copy data in %p to %" PY_FORMAT_SIZE_T "d " \
 "(%" PY_FORMAT_SIZE_T "d)\n", \
 data, state->data_stack_base, size)); \
 if (size > state->data_stack_size - state->data_stack_base) { \
 int j = data_stack_grow(state, size); \
 if (j < 0) return j; \
 if (ctx_pos != -1) \
 DATA_STACK_LOOKUP_AT(state, SRE_MATCH_CONTEXT, ctx, ctx_pos); \
 } \
 memcpy(state->data_stack+state->data_stack_base, data, size); \
 state->data_stack_base += size; \
} while (0)

#defineDATA_STACK_POP(state, data, size, discard) \
do { \
 TRACE(("copy data to %p from %" PY_FORMAT_SIZE_T "d " \
 "(%" PY_FORMAT_SIZE_T "d)\n", \
 data, state->data_stack_base-size, size)); \
 memcpy(data, state->data_stack+state->data_stack_base-size, size); \
 if (discard) \
 state->data_stack_base -= size; \
} while (0)

#defineDATA_STACK_POP_DISCARD(state, size) \
do { \
 TRACE(("discard data from %" PY_FORMAT_SIZE_T "d " \
 "(%" PY_FORMAT_SIZE_T "d)\n", \
 state->data_stack_base-size, size)); \
 state->data_stack_base -= size; \
} while(0)

#defineDATA_PUSH(x) \
 DATA_STACK_PUSH(state, (x), sizeof(*(x)))
#defineDATA_POP(x) \
 DATA_STACK_POP(state, (x), sizeof(*(x)), 1)
#defineDATA_POP_DISCARD(x) \
 DATA_STACK_POP_DISCARD(state, sizeof(*(x)))
#defineDATA_ALLOC(t,p) \
 DATA_STACK_ALLOC(state, t, p)
#defineDATA_LOOKUP_AT(t,p,pos) \
 DATA_STACK_LOOKUP_AT(state,t,p,pos)

#defineMARK_PUSH(lastmark) \
 do if (lastmark > 0) { \
 i = lastmark; /* ctx->lastmark may change if reallocated */ \
DATA_STACK_PUSH(state, state->mark, (i+1)*sizeof(void*)); \
 } while (0)
#defineMARK_POP(lastmark) \
 do if (lastmark > 0) { \
 DATA_STACK_POP(state, state->mark, (lastmark+1)*sizeof(void*), 1); \
 } while (0)
#defineMARK_POP_KEEP(lastmark) \
 do if (lastmark > 0) { \
 DATA_STACK_POP(state, state->mark, (lastmark+1)*sizeof(void*), 0); \
 } while (0)
#defineMARK_POP_DISCARD(lastmark) \
 do if (lastmark > 0) { \
 DATA_STACK_POP_DISCARD(state, (lastmark+1)*sizeof(void*)); \
 } while (0)

#defineJUMP_NONE 0
#defineJUMP_MAX_UNTIL_1 1
#defineJUMP_MAX_UNTIL_2 2
#defineJUMP_MAX_UNTIL_3 3
#defineJUMP_MIN_UNTIL_1 4
#defineJUMP_MIN_UNTIL_2 5
#defineJUMP_MIN_UNTIL_3 6
#defineJUMP_REPEAT 7
#defineJUMP_REPEAT_ONE_1 8
#defineJUMP_REPEAT_ONE_2 9
#defineJUMP_MIN_REPEAT_ONE 10
#defineJUMP_BRANCH 11
#defineJUMP_ASSERT 12
#defineJUMP_ASSERT_NOT 13

#defineDO_JUMP(jumpvalue, jumplabel, nextpattern) \
 DATA_ALLOC(SRE_MATCH_CONTEXT, nextctx); \
 nextctx->last_ctx_pos = ctx_pos; \
 nextctx->jump = jumpvalue; \
 nextctx->pattern = nextpattern; \
 ctx_pos = alloc_pos; \
 ctx = nextctx; \
 goto entrance; \
 jumplabel: \
 while (0) /* gcc doesn't like labels at end of scopes */ \

typedefstruct {
Py_ssize_tlast_ctx_pos;
Py_ssize_tjump;
SRE_CHAR*ptr;
SRE_CODE*pattern;
Py_ssize_tcount;
Py_ssize_tlastmark;
Py_ssize_tlastindex;
union {
SRE_CODEchr;
SRE_REPEAT*rep;
 } u;
} SRE_MATCH_CONTEXT;

/* check if string matches the given pattern. returns <0 for
 error, 0 for failure, and 1 for success */
LOCAL(Py_ssize_t)
SRE_MATCH(SRE_STATE*state, SRE_CODE*pattern)
{
SRE_CHAR*end= (SRE_CHAR*)state->end;
Py_ssize_talloc_pos, ctx_pos=-1;
Py_ssize_ti, ret=0;
Py_ssize_tjump;
unsigned intsigcount=0;

SRE_MATCH_CONTEXT*ctx;
SRE_MATCH_CONTEXT*nextctx;

TRACE(("|%p|%p|ENTER\n", pattern, state->ptr));

DATA_ALLOC(SRE_MATCH_CONTEXT, ctx);
ctx->last_ctx_pos=-1;
ctx->jump=JUMP_NONE;
ctx->pattern=pattern;
ctx_pos=alloc_pos;

entrance:

ctx->ptr= (SRE_CHAR*)state->ptr;

if (ctx->pattern[0] ==SRE_OP_INFO) {
/* optimization info block */
/* <INFO> <1=skip> <2=flags> <3=min> ... */
if (ctx->pattern[3] && (Py_uintptr_t)(end-ctx->ptr) <ctx->pattern[3]) {
TRACE(("reject (got %"PY_FORMAT_SIZE_T"d chars, "
"need %"PY_FORMAT_SIZE_T"d)\n",
 (end-ctx->ptr), (Py_ssize_t) ctx->pattern[3]));
RETURN_FAILURE;
 }
ctx->pattern+=ctx->pattern[1] +1;
 }

for (;;) {
++sigcount;
if ((0== (sigcount&0xfff)) &&PyErr_CheckSignals())
RETURN_ERROR(SRE_ERROR_INTERRUPTED);

switch (*ctx->pattern++) {

caseSRE_OP_MARK:
/* set mark */
/* <MARK> <gid> */
TRACE(("|%p|%p|MARK %d\n", ctx->pattern,
ctx->ptr, ctx->pattern[0]));
i=ctx->pattern[0];
if (i&1)
state->lastindex=i/2+1;
if (i>state->lastmark) {
/* state->lastmark is the highest valid index in the
 state->mark array. If it is increased by more than 1,
 the intervening marks must be set to NULL to signal
 that these marks have not been encountered. */
Py_ssize_tj=state->lastmark+1;
while (j<i)
state->mark[j++] =NULL;
state->lastmark=i;
 }
state->mark[i] =ctx->ptr;
ctx->pattern++;
break;

caseSRE_OP_LITERAL:
/* match literal string */
/* <LITERAL> <code> */
TRACE(("|%p|%p|LITERAL %d\n", ctx->pattern,
ctx->ptr, *ctx->pattern));
if (ctx->ptr >= end|| (SRE_CODE) ctx->ptr[0] !=ctx->pattern[0])
RETURN_FAILURE;
ctx->pattern++;
ctx->ptr++;
break;

caseSRE_OP_NOT_LITERAL:
/* match anything that is not literal character */
/* <NOT_LITERAL> <code> */
TRACE(("|%p|%p|NOT_LITERAL %d\n", ctx->pattern,
ctx->ptr, *ctx->pattern));
if (ctx->ptr >= end|| (SRE_CODE) ctx->ptr[0] ==ctx->pattern[0])
RETURN_FAILURE;
ctx->pattern++;
ctx->ptr++;
break;

caseSRE_OP_SUCCESS:
/* end of pattern */
TRACE(("|%p|%p|SUCCESS\n", ctx->pattern, ctx->ptr));
state->ptr=ctx->ptr;
RETURN_SUCCESS;

caseSRE_OP_AT:
/* match at given position */
/* <AT> <code> */
TRACE(("|%p|%p|AT %d\n", ctx->pattern, ctx->ptr, *ctx->pattern));
if (!SRE_AT(state, ctx->ptr, *ctx->pattern))
RETURN_FAILURE;
ctx->pattern++;
break;

caseSRE_OP_CATEGORY:
/* match at given category */
/* <CATEGORY> <code> */
TRACE(("|%p|%p|CATEGORY %d\n", ctx->pattern,
ctx->ptr, *ctx->pattern));
if (ctx->ptr >= end|| !sre_category(ctx->pattern[0], ctx->ptr[0]))
RETURN_FAILURE;
ctx->pattern++;
ctx->ptr++;
break;

caseSRE_OP_ANY:
/* match anything (except a newline) */
/* <ANY> */
TRACE(("|%p|%p|ANY\n", ctx->pattern, ctx->ptr));
if (ctx->ptr >= end||SRE_IS_LINEBREAK(ctx->ptr[0]))
RETURN_FAILURE;
ctx->ptr++;
break;

caseSRE_OP_ANY_ALL:
/* match anything */
/* <ANY_ALL> */
TRACE(("|%p|%p|ANY_ALL\n", ctx->pattern, ctx->ptr));
if (ctx->ptr >= end)
RETURN_FAILURE;
ctx->ptr++;
break;

caseSRE_OP_IN:
/* match set member (or non_member) */
/* <IN> <skip> <set> */
TRACE(("|%p|%p|IN\n", ctx->pattern, ctx->ptr));
if (ctx->ptr >= end|| !SRE_CHARSET(ctx->pattern+1, *ctx->ptr))
RETURN_FAILURE;
ctx->pattern+=ctx->pattern[0];
ctx->ptr++;
break;

caseSRE_OP_LITERAL_IGNORE:
TRACE(("|%p|%p|LITERAL_IGNORE %d\n",
ctx->pattern, ctx->ptr, ctx->pattern[0]));
if (ctx->ptr >= end||
state->lower(*ctx->ptr) !=state->lower(*ctx->pattern))
RETURN_FAILURE;
ctx->pattern++;
ctx->ptr++;
break;

caseSRE_OP_NOT_LITERAL_IGNORE:
TRACE(("|%p|%p|NOT_LITERAL_IGNORE %d\n",
ctx->pattern, ctx->ptr, *ctx->pattern));
if (ctx->ptr >= end||
state->lower(*ctx->ptr) ==state->lower(*ctx->pattern))
RETURN_FAILURE;
ctx->pattern++;
ctx->ptr++;
break;

caseSRE_OP_IN_IGNORE:
TRACE(("|%p|%p|IN_IGNORE\n", ctx->pattern, ctx->ptr));
if (ctx->ptr >= end
|| !SRE_CHARSET(ctx->pattern+1,
 (SRE_CODE)state->lower(*ctx->ptr)))
RETURN_FAILURE;
ctx->pattern+=ctx->pattern[0];
ctx->ptr++;
break;

caseSRE_OP_JUMP:
caseSRE_OP_INFO:
/* jump forward */
/* <JUMP> <offset> */
TRACE(("|%p|%p|JUMP %d\n", ctx->pattern,
ctx->ptr, ctx->pattern[0]));
ctx->pattern+=ctx->pattern[0];
break;

caseSRE_OP_BRANCH:
/* alternation */
/* <BRANCH> <0=skip> code <JUMP> ... <NULL> */
TRACE(("|%p|%p|BRANCH\n", ctx->pattern, ctx->ptr));
LASTMARK_SAVE();
ctx->u.rep=state->repeat;
if (ctx->u.rep)
MARK_PUSH(ctx->lastmark);
for (; ctx->pattern[0]; ctx->pattern+=ctx->pattern[0]) {
if (ctx->pattern[1] ==SRE_OP_LITERAL&&