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; re-enable 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
 * 2013-02-04 mrab added fullmatch primitive
 *
 * 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.
 */

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

#include"Python.h"
#include"pycore_critical_section.h"// Py_BEGIN_CRITICAL_SECTION
#include"pycore_dict.h"// _PyDict_Next()
#include"pycore_long.h"// _PyLong_GetZero()
#include"pycore_moduleobject.h"// _PyModule_GetState()

#include"sre.h"// SRE_CODE

#include<ctype.h>// tolower(), toupper(), isalnum()

#defineSRE_CODE_BITS (8 * sizeof(SRE_CODE))

// On macOS, use the wide character ctype API using btowc()
#if defined(__APPLE__)
# defineUSE_CTYPE_WINT_T
#endif

staticintsre_isalnum(unsigned intch) {
#ifdefUSE_CTYPE_WINT_T
return (unsigned int)iswalnum(btowc((int)ch));
#else
return (unsigned int)isalnum((int)ch);
#endif
}

staticunsigned intsre_tolower(unsigned intch) {
#ifdefUSE_CTYPE_WINT_T
return (unsigned int)towlower(btowc((int)ch));
#else
return (unsigned int)tolower((int)ch);
#endif
}

staticunsigned intsre_toupper(unsigned intch) {
#ifdefUSE_CTYPE_WINT_T
return (unsigned int)towupper(btowc((int)ch));
#else
return (unsigned int)toupper((int)ch);
#endif
}

/* Defining this one controls tracing:
 * 0 -- disabled
 * 1 -- only if the DEBUG flag set
 * 2 -- always
 */
#ifndefVERBOSE
# defineVERBOSE 0
#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
#else
#defineLOCAL(type) static inline 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 */

#ifVERBOSE==0
# defineINIT_TRACE(state)
# defineDO_TRACE 0
# defineTRACE(v)
#elifVERBOSE==1
# defineINIT_TRACE(state) int _debug = (state)->debug
# defineDO_TRACE (_debug)
# defineTRACE(v) do { \
 if (_debug) { \
 printf v; \
 } \
 } while (0)
#elifVERBOSE==2
# defineINIT_TRACE(state)
# defineDO_TRACE 1
# defineTRACE(v) printf v
#else
# error VERBOSE must be 0, 1 or 2
#endif

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

#defineSRE_IS_DIGIT(ch)\
 ((ch) <= '9' && Py_ISDIGIT(ch))
#defineSRE_IS_SPACE(ch)\
 ((ch) <= ' ' && Py_ISSPACE(ch))
#defineSRE_IS_LINEBREAK(ch)\
 ((ch) == '\n')
#defineSRE_IS_WORD(ch)\
 ((ch) <= 'z' && (Py_ISALNUM(ch) || (ch) == '_'))

staticunsigned intsre_lower_ascii(unsigned intch)
{
return ((ch) <128 ? Py_TOLOWER(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_ALNUM(ch) (!((ch) & ~255) ? sre_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)sre_tolower((ch)) : ch);
}

staticunsigned intsre_upper_locale(unsigned intch)
{
return ((ch) <256 ? (unsigned int)sre_toupper((ch)) : ch);
}

/* unicode-specific character predicates */

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

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

staticunsigned intsre_upper_unicode(unsigned intch)
{
return (unsigned int) Py_UNICODE_TOUPPER(ch);
}

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

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);
 }
return0;
}

LOCAL(int)
char_loc_ignore(SRE_CODEpattern, SRE_CODEch)
{
returnch==pattern
|| (SRE_CODE) sre_lower_locale(ch) ==pattern
|| (SRE_CODE) sre_upper_locale(ch) ==pattern;
}


/* 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)
{
INIT_TRACE(state);
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 %zd\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;
}

/* memory pool functions for SRE_REPEAT, this can avoid memory
 leak when SRE(match) function terminates abruptly.
 state->repeat_pool_used is a doubly-linked list, so that we
 can remove a SRE_REPEAT node from it.
 state->repeat_pool_unused is a singly-linked list, we put/get
 node at the head. */
staticSRE_REPEAT*
repeat_pool_malloc(SRE_STATE*state)
{
SRE_REPEAT*repeat;

if (state->repeat_pool_unused) {
/* remove from unused pool (singly-linked list) */
repeat=state->repeat_pool_unused;
state->repeat_pool_unused=repeat->pool_next;
 }
else {
repeat=PyMem_Malloc(sizeof(SRE_REPEAT));
if (!repeat) {
returnNULL;
 }
 }

/* add to used pool (doubly-linked list) */
SRE_REPEAT*temp=state->repeat_pool_used;
if (temp) {
temp->pool_prev=repeat;
 }
repeat->pool_prev=NULL;
repeat->pool_next=temp;
state->repeat_pool_used=repeat;

returnrepeat;
}

staticvoid
repeat_pool_free(SRE_STATE*state, SRE_REPEAT*repeat)
{
SRE_REPEAT*prev=repeat->pool_prev;
SRE_REPEAT*next=repeat->pool_next;

/* remove from used pool (doubly-linked list) */
if (prev) {
prev->pool_next=next;
 }
else {
state->repeat_pool_used=next;
 }
if (next) {
next->pool_prev=prev;
 }

/* add to unused pool (singly-linked list) */
repeat->pool_next=state->repeat_pool_unused;
state->repeat_pool_unused=repeat;
}

staticvoid
repeat_pool_clear(SRE_STATE*state)
{
/* clear used pool */
SRE_REPEAT*next=state->repeat_pool_used;
state->repeat_pool_used=NULL;
while (next) {
SRE_REPEAT*temp=next;
next=temp->pool_next;
PyMem_Free(temp);
 }

/* clear unused pool */
next=state->repeat_pool_unused;
state->repeat_pool_unused=NULL;
while (next) {
SRE_REPEAT*temp=next;
next=temp->pool_next;
PyMem_Free(temp);
 }
}

/* generate 8-bit version */

#defineSRE_CHAR Py_UCS1
#defineSIZEOF_SRE_CHAR 1
#defineSRE(F) sre_ucs1_##F
#include"sre_lib.h"

/* generate 16-bit unicode version */

#defineSRE_CHAR Py_UCS2
#defineSIZEOF_SRE_CHAR 2
#defineSRE(F) sre_ucs2_##F
#include"sre_lib.h"

/* generate 32-bit unicode version */

#defineSRE_CHAR Py_UCS4
#defineSIZEOF_SRE_CHAR 4
#defineSRE(F) sre_ucs4_##F
#include"sre_lib.h"

/* -------------------------------------------------------------------- */
/* factories and destructors */

/* module state */
typedefstruct {
PyTypeObject*Pattern_Type;
PyTypeObject*Match_Type;
PyTypeObject*Scanner_Type;
PyTypeObject*Template_Type;
PyObject*compile_template; // reference to re._compile_template
} _sremodulestate;

static_sremodulestate*
get_sre_module_state(PyObject*m)
{
_sremodulestate*state= (_sremodulestate*)_PyModule_GetState(m);
assert(state);
returnstate;
}

staticstructPyModuleDefsremodule;
#defineget_sre_module_state_by_class(cls) \
 (get_sre_module_state(PyType_GetModule(cls)))

/* see sre.h for object declarations */
staticPyObject*pattern_new_match(_sremodulestate*, PatternObject*, SRE_STATE*, Py_ssize_t);
staticPyObject*pattern_scanner(_sremodulestate*, PatternObject*, PyObject*, Py_ssize_t, Py_ssize_t);

/*[clinic input]
module _sre
class _sre.SRE_Pattern "PatternObject *" "get_sre_module_state_by_class(tp)->Pattern_Type"
class _sre.SRE_Match "MatchObject *" "get_sre_module_state_by_class(tp)->Match_Type"
class _sre.SRE_Scanner "ScannerObject *" "get_sre_module_state_by_class(tp)->Scanner_Type"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=fe2966e32b66a231]*/

/*[clinic input]
_sre.getcodesize -> int
[clinic start generated code]*/

staticint
_sre_getcodesize_impl(PyObject*module)
/*[clinic end generated code: output=e0db7ce34a6dd7b1 input=bd6f6ecf4916bb2b]*/
{
returnsizeof(SRE_CODE);
}

/*[clinic input]
_sre.ascii_iscased -> bool

 character: int
 /

[clinic start generated code]*/

staticint
_sre_ascii_iscased_impl(PyObject*module, intcharacter)
/*[clinic end generated code: output=4f454b630fbd19a2 input=9f0bd952812c7ed3]*/
{
unsigned intch= (unsigned int)character;
returnch<128&&Py_ISALPHA(ch);
}

/*[clinic input]
_sre.unicode_iscased -> bool

 character: int
 /

[clinic start generated code]*/

staticint
_sre_unicode_iscased_impl(PyObject*module, intcharacter)
/*[clinic end generated code: output=9c5ddee0dc2bc258 input=51e42c3b8dddb78e]*/
{
unsigned intch= (unsigned int)character;
returnch!=sre_lower_unicode(ch) ||ch!=sre_upper_unicode(ch);
}

/*[clinic input]
_sre.ascii_tolower -> int

 character: int
 /

[clinic start generated code]*/

staticint
_sre_ascii_tolower_impl(PyObject*module, intcharacter)
/*[clinic end generated code: output=228294ed6ff2a612 input=272c609b5b61f136]*/
{
returnsre_lower_ascii(character);
}

/*[clinic input]
_sre.unicode_tolower -> int

 character: int
 /

[clinic start generated code]*/

staticint
_sre_unicode_tolower_impl(PyObject*module, intcharacter)
/*[clinic end generated code: output=6422272d7d7fee65 input=91d708c5f3c2045a]*/
{
returnsre_lower_unicode(character);
}

LOCAL(void)
state_reset(SRE_STATE*state)
{
/* state->mark will be set to 0 in SRE_OP_MARK dynamically. */
/*memset(state->mark, 0, sizeof(*state->mark) * SRE_MARK_SIZE);*/

state->lastmark=-1;
state->lastindex=-1;

state->repeat=NULL;

data_stack_dealloc(state);
}

staticconstvoid*
getstring(PyObject*string, Py_ssize_t*p_length,
int*p_isbytes, int*p_charsize,
Py_buffer*view)
{
/* given a python object, return a data pointer, a length (in
 characters), and a character size. return NULL if the object
 is not a string (or not compatible) */

/* Unicode objects do not support the buffer API. So, get the data
 directly instead. */
if (PyUnicode_Check(string)) {
*p_length=PyUnicode_GET_LENGTH(string);
*p_charsize=PyUnicode_KIND(string);
*p_isbytes=0;
returnPyUnicode_DATA(string);
 }

/* get pointer to byte string buffer */
if (PyObject_GetBuffer(string, view, PyBUF_SIMPLE) !=0) {
PyErr_Format(PyExc_TypeError, "expected string or bytes-like "
"object, got '%.200s'", Py_TYPE(string)->tp_name);
returnNULL;
 }

*p_length=view->len;
*p_charsize=1;
*p_isbytes=1;

if (view->buf==NULL) {
PyErr_SetString(PyExc_ValueError, "Buffer is NULL");
PyBuffer_Release(view);
view->buf=NULL;
returnNULL;
 }
returnview->buf;
}

LOCAL(PyObject*)
state_init(SRE_STATE*state, PatternObject*pattern, PyObject*string,
Py_ssize_tstart, Py_ssize_tend)
{
/* prepare state object */

Py_ssize_tlength;
intisbytes, charsize;
constvoid*ptr;

memset(state, 0, sizeof(SRE_STATE));

state->mark=PyMem_New(constvoid*, pattern->groups*2);
if (!state->mark) {
PyErr_NoMemory();
 goto err;
 }
state->lastmark=-1;
state->lastindex=-1;

state->buffer.buf=NULL;
ptr=getstring(string, &length, &isbytes, &charsize, &state->buffer);
if (!ptr)
 goto err;

if (isbytes&&pattern->isbytes==0) {
PyErr_SetString(PyExc_TypeError,
"cannot use a string pattern on a bytes-like object");
 goto err;
 }
if (!isbytes&&pattern->isbytes>0) {
PyErr_SetString(PyExc_TypeError,
"cannot use a bytes pattern on a string-like object");
 goto err;
 }

/* adjust boundaries */
if (start<0)
start=0;
elseif (start>length)
start=length;

if (end<0)
end=0;
elseif (end>length)
end=length;

state->isbytes=isbytes;
state->charsize=charsize;
state->match_all=0;
state->must_advance=0;
state->debug= ((pattern->flags&SRE_FLAG_DEBUG) !=0);

state->beginning=ptr;

state->start= (void*) ((char*) ptr+start*state->charsize);
state->end= (void*) ((char*) ptr+end*state->charsize);

state->string=Py_NewRef(string);
state->pos=start;
state->endpos=end;

#ifdefPy_DEBUG
state->fail_after_count=pattern->fail_after_count;
state->fail_after_exc=pattern->fail_after_exc; // borrowed ref
#endif

returnstring;
err:
/* We add an explicit cast here because MSVC has a bug when
 compiling C code where it believes that `const void**` cannot be
 safely casted to `void*`, see bpo-39943 for details. */
PyMem_Free((void*) state->mark);
state->mark=NULL;
if (state->buffer.buf)
PyBuffer_Release(&state->buffer);
returnNULL;
}

LOCAL(void)
state_fini(SRE_STATE*state)
{
if (state->buffer.buf)
PyBuffer_Release(&state->buffer);
Py_XDECREF(state->string);
data_stack_dealloc(state);
/* See above PyMem_Del for why we explicitly cast here. */
PyMem_Free((void*) state->mark);
state->mark=NULL;
/* SRE_REPEAT pool */
repeat_pool_clear(state);
}

/* calculate offset from start of string */
#defineSTATE_OFFSET(state, member)\
 (((char*)(member) - (char*)(state)->beginning) / (state)->charsize)

LOCAL(PyObject*)
getslice(intisbytes, constvoid*ptr,
PyObject*string, Py_ssize_tstart, Py_ssize_tend)
{
if (isbytes) {
if (PyBytes_CheckExact(string) &&
start==0&&end==PyBytes_GET_SIZE(string)) {
returnPy_NewRef(string);
 }
returnPyBytes_FromStringAndSize(
 (constchar*)ptr+start, end-start);
 }
else {
returnPyUnicode_Substring(string, start, end);
 }
}

LOCAL(PyObject*)
state_getslice(SRE_STATE*state, Py_ssize_tindex, PyObject*string, intempty)
{
Py_ssize_ti, j;

index= (index-1) *2;

if (string==Py_None||index >= state->lastmark|| !state->mark[index] || !state->mark[index+1]) {
if (empty)
/* want empty string */
i=j=0;
else {
Py_RETURN_NONE;
 }
 } else {
i=STATE_OFFSET(state, state->mark[index]);
j=STATE_OFFSET(state, state->mark[index+1]);

/* check wrong span */
if (i>j) {
PyErr_SetString(PyExc_SystemError,
"The span of capturing group is wrong,"
" please report a bug for the re module.");
returnNULL;
 }
 }

returngetslice(state->isbytes, state->beginning, string, i, j);
}

staticvoid
pattern_error(Py_ssize_tstatus)
{
switch (status) {
caseSRE_ERROR_RECURSION_LIMIT:
/* This error code seems to be unused. */
PyErr_SetString(
PyExc_RecursionError,
"maximum recursion limit exceeded"
 );
break;
caseSRE_ERROR_MEMORY:
PyErr_NoMemory();
break;
caseSRE_ERROR_INTERRUPTED:
/* An exception has already been raised, so let it fly */
break;
default:
/* other error codes indicate compiler/engine bugs */
PyErr_SetString(
PyExc_RuntimeError,
"internal error in regular expression engine"
 );
 }
}

staticint
pattern_traverse(PatternObject*self, visitprocvisit, void*arg)
{
Py_VISIT(Py_TYPE(self));
Py_VISIT(self->groupindex);
Py_VISIT(self->indexgroup);
Py_VISIT(self->pattern);
#ifdefPy_DEBUG
Py_VISIT(self->fail_after_exc);
#endif
return0;
}

staticint
pattern_clear(PatternObject*self)
{
Py_CLEAR(self->groupindex);
Py_CLEAR(self->indexgroup);
Py_CLEAR(self->pattern);
#ifdefPy_DEBUG
Py_CLEAR(self->fail_after_exc);
#endif
return0;
}

staticvoid
pattern_dealloc(PatternObject*self)
{
PyTypeObject*tp=Py_TYPE(self);

PyObject_GC_UnTrack(self);
if (self->weakreflist!=NULL) {
PyObject_ClearWeakRefs((PyObject*) self);
 }
 (void)pattern_clear(self);
tp->tp_free(self);
Py_DECREF(tp);
}

LOCAL(Py_ssize_t)
sre_match(SRE_STATE*state, SRE_CODE*pattern)
{
if (state->charsize==1)
returnsre_ucs1_match(state, pattern, 1);
if (state->charsize==2)
returnsre_ucs2_match(state, pattern, 1);
assert(state->charsize==4);
returnsre_ucs4_match(state, pattern, 1);
}

LOCAL(Py_ssize_t)
sre_search(SRE_STATE*state, SRE_CODE*pattern)
{
if (state->charsize==1)
returnsre_ucs1_search(state, pattern);
if (state->charsize==2)
returnsre_ucs2_search(state, pattern);
assert(state->charsize==4);
returnsre_ucs4_search(state, pattern);
}

/*[clinic input]
_sre.SRE_Pattern.match

 cls: defining_class
 /
 string: object
 pos: Py_ssize_t = 0
 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize

Matches zero or more characters at the beginning of the string.
[clinic start generated code]*/

staticPyObject*
_sre_SRE_Pattern_match_impl(PatternObject*self, PyTypeObject*cls,
PyObject*string, Py_ssize_tpos,
Py_ssize_tendpos)
/*[clinic end generated code: output=ec6208ea58a0cca0 input=4bdb9c3e564d13ac]*/
{
_sremodulestate*module_state=get_sre_module_state_by_class(cls);
SRE_STATEstate;
Py_ssize_tstatus;
PyObject*match;

if (!state_init(&state, self, string, pos, endpos))
returnNULL;

INIT_TRACE(&state);
state.ptr=state.start;

TRACE(("|%p|%p|MATCH\n", PatternObject_GetCode(self), state.ptr));

status=sre_match(&state, PatternObject_GetCode(self));

TRACE(("|%p|%p|END\n", PatternObject_GetCode(self), state.ptr));
if (PyErr_Occurred()) {
state_fini(&state);
returnNULL;
 }

match=pattern_new_match(module_state, self, &state, status);
state_fini(&state);
returnmatch;
}

/*[clinic input]
_sre.SRE_Pattern.fullmatch

 cls: defining_class
 /
 string: object
 pos: Py_ssize_t = 0
 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize

Matches against all of the string.
[clinic start generated code]*/

staticPyObject*
_sre_SRE_Pattern_fullmatch_impl(PatternObject*self, PyTypeObject*cls,
PyObject*string, Py_ssize_tpos,
Py_ssize_tendpos)
/*[clinic end generated code: output=625b75b027ef94da input=50981172ab0fcfdd]*/
{
_sremodulestate*module_state=get_sre_module_state_by_class(cls);
SRE_STATEstate;
Py_ssize_tstatus;
PyObject*match;

if (!state_init(&state, self, string, pos, endpos))
returnNULL;

INIT_TRACE(&state);
state.ptr=state.start;

TRACE(("|%p|%p|FULLMATCH\n", PatternObject_GetCode(self), state.ptr));

state.match_all=1;
status=sre_match(&state, PatternObject_GetCode(self));

TRACE(("|%p|%p|END\n", PatternObject_GetCode(self), state.ptr));
if (PyErr_Occurred()) {
state_fini(&state);
returnNULL;
 }

match=pattern_new_match(module_state, self, &state, status);
state_fini(&state);
returnmatch;
}

/*[clinic input]
_sre.SRE_Pattern.search

 cls: defining_class
 /
 string: object
 pos: Py_ssize_t = 0
 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize

Scan through string looking for a match, and return a corresponding match object instance.

Return None if no position in the string matches.
[clinic start generated code]*/

staticPyObject*
_sre_SRE_Pattern_search_impl(PatternObject*self, PyTypeObject*cls,
PyObject*string, Py_ssize_tpos,
Py_ssize_tendpos)
/*[clinic end generated code: output=bd7f2d9d583e1463 input=afa9afb66a74a4b3]*/
{
_sremodulestate*module_state=get_sre_module_state_by_class(cls);
SRE_STATEstate;
Py_ssize_tstatus;
PyObject*match;

if (!state_init(&state, self, string, pos, endpos))
returnNULL;

INIT_TRACE(&state);
TRACE(("|%p|%p|SEARCH\n", PatternObject_GetCode(self), state.ptr));

status=sre_search(&state, PatternObject_GetCode(self));

TRACE(("|%p|%p|END\n", PatternObject_GetCode(self), state.ptr));

if (PyErr_Occurred()) {
state_fini(&state);
returnNULL;
 }

match=pattern_new_match(module_state, self, &state, status);
state_fini(&state);
returnmatch;
}

/*[clinic input]
_sre.SRE_Pattern.findall

 string: object
 pos: Py_ssize_t = 0
 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize

Return a list of all non-overlapping matches of pattern in string.
[clinic start generated code]*/

staticPyObject*
_sre_SRE_Pattern_findall_impl(PatternObject*self, PyObject*string,
Py_ssize_tpos, Py_ssize_tendpos)
/*[clinic end generated code: output=f4966baceea60aca input=5b6a4ee799741563]*/
{
SRE_STATEstate;
PyObject*list;
Py_ssize_tstatus;
Py_ssize_ti, b, e;

if (!state_init(&state, self, string, pos, endpos))
returnNULL;

list=PyList_New(0);
if (!list) {
state_fini(&state);
returnNULL;
 }

while (state.start <= state.end) {

PyObject*item;

state_reset(&state);

state.ptr=state.start;

status=sre_search(&state, PatternObject_GetCode(self));
if (PyErr_Occurred())
 goto error;

if (status <= 0) {
if (status==0)
break;
pattern_error(status);
 goto error;
 }

/* don't bother to build a match object */
switch (self->groups) {
case0:
b=STATE_OFFSET(&state, state.start);
e=STATE_OFFSET(&state, state.ptr);
item=getslice(state.isbytes, state.beginning,
string, b, e);
if (!item)
 goto error;
break;
case1:
item=state_getslice(&state, 1, string, 1);
if (!item)
 goto error;
break;
default:
item=PyTuple_New(self->groups);
if (!item)
 goto error;
for (i=0; i<self->groups; i++) {
PyObject*o=state_getslice(&state, i+1, string, 1);
if (!o) {
Py_DECREF(item);
 goto error;
 }
PyTuple_SET_ITEM(item, i, o);
 }
break;
 }

status=PyList_Append(list, item);
Py_DECREF(item);
if (status<0)
 goto error;

state.must_advance= (state.ptr==state.start);
state.start=state.ptr;
 }

state_fini(&state);
returnlist;

error:
Py_DECREF(list);
state_fini(&state);
returnNULL;

}

/*[clinic input]
_sre.SRE_Pattern.finditer

 cls: defining_class
 /
 string: object
 pos: Py_ssize_t = 0
 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize