Debian Codegraph @

Modules/_sre/sre.c

raw
1 /*
2 * Secret Labs' Regular Expression Engine
3 *
4 * regular expression matching engine
5 *
6 * partial history:
7 * 1999-10-24 fl created (based on existing template matcher code)
8 * 2000-03-06 fl first alpha, sort of
9 * 2000-08-01 fl fixes for 1.6b1
10 * 2000-08-07 fl use PyOS_CheckStack() if available
11 * 2000-09-20 fl added expand method
12 * 2001-03-20 fl lots of fixes for 2.1b2
13 * 2001-04-15 fl export copyright as Python attribute, not global
14 * 2001-04-28 fl added __copy__ methods (work in progress)
15 * 2001-05-14 fl fixes for 1.5.2 compatibility
16 * 2001-07-01 fl added BIGCHARSET support (from Martin von Loewis)
17 * 2001-10-18 fl fixed group reset issue (from Matthew Mueller)
18 * 2001-10-20 fl added split primitive; re-enable unicode for 1.6/2.0/2.1
19 * 2001-10-21 fl added sub/subn primitive
20 * 2001-10-24 fl added finditer primitive (for 2.2 only)
21 * 2001-12-07 fl fixed memory leak in sub/subn (Guido van Rossum)
22 * 2002-11-09 fl fixed empty sub/subn return type
23 * 2003-04-18 mvl fully support 4-byte codes
24 * 2003-10-17 gn implemented non recursive scheme
25 * 2013-02-04 mrab added fullmatch primitive
26 *
27 * Copyright (c) 1997-2001 by Secret Labs AB. All rights reserved.
28 *
29 * This version of the SRE library can be redistributed under CNRI's
30 * Python 1.6 license. For any other use, please contact Secret Labs
31 * AB ([email protected]).
32 *
33 * Portions of this engine have been developed in cooperation with
34 * CNRI. Hewlett-Packard provided funding for 1.6 integration and
35 * other compatibility work.
36 */
37
38 static const char copyright[] =
39 " SRE 2.2.2 Copyright (c) 1997-2002 by Secret Labs AB ";
40
41 #include "Python.h"
42 #include "pycore_critical_section.h" // Py_BEGIN_CRITICAL_SECTION
43 #include "pycore_dict.h" // _PyDict_Next()
44 #include "pycore_long.h" // _PyLong_GetZero()
45 #include "pycore_moduleobject.h" // _PyModule_GetState()
46 #include "pycore_unicodeobject.h" // _PyUnicode_Copy
47 #include "pycore_weakref.h" // FT_CLEAR_WEAKREFS()
48
49 #include "sre.h" // SRE_CODE
50
51 #include <ctype.h> // tolower(), toupper(), isalnum()
52
53 #define SRE_CODE_BITS (8 * sizeof(SRE_CODE))
54
55 // On macOS, use the wide character ctype API using btowc()
56 #if defined(__APPLE__)
57 # define USE_CTYPE_WINT_T
58 #endif
59
60 static int sre_isalnum(unsigned int ch) {
61 #ifdef USE_CTYPE_WINT_T
62 return (unsigned int)iswalnum(btowc((int)ch));
63 #else
64 return (unsigned int)isalnum((int)ch);
65 #endif
66 }
67
68 static unsigned int sre_tolower(unsigned int ch) {
69 #ifdef USE_CTYPE_WINT_T
70 return (unsigned int)towlower(btowc((int)ch));
71 #else
72 return (unsigned int)tolower((int)ch);
73 #endif
74 }
75
76 static unsigned int sre_toupper(unsigned int ch) {
77 #ifdef USE_CTYPE_WINT_T
78 return (unsigned int)towupper(btowc((int)ch));
79 #else
80 return (unsigned int)toupper((int)ch);
81 #endif
82 }
83
84 /* Defining this one controls tracing:
85 * 0 -- disabled
86 * 1 -- only if the DEBUG flag set
87 * 2 -- always
88 */
89 #ifndef VERBOSE
90 # define VERBOSE 0
91 #endif
92
93 /* -------------------------------------------------------------------- */
94
95 #if defined(_MSC_VER) && !defined(__clang__)
96 #pragma optimize("agtw", on) /* doesn't seem to make much difference... */
97 #pragma warning(disable: 4710) /* who cares if functions are not inlined ;-) */
98 /* fastest possible local call under MSVC */
99 #define LOCAL(type) static __inline type __fastcall
100 #else
101 #define LOCAL(type) static inline type
102 #endif
103
104 /* error codes */
105 #define SRE_ERROR_ILLEGAL -1 /* illegal opcode */
106 #define SRE_ERROR_STATE -2 /* illegal state */
107 #define SRE_ERROR_RECURSION_LIMIT -3 /* runaway recursion */
108 #define SRE_ERROR_MEMORY -9 /* out of memory */
109 #define SRE_ERROR_INTERRUPTED -10 /* signal handler raised exception */
110
111 #if VERBOSE == 0
112 # define INIT_TRACE(state)
113 # define DO_TRACE 0
114 # define TRACE(v)
115 #elif VERBOSE == 1
116 # define INIT_TRACE(state) int _debug = (state)->debug
117 # define DO_TRACE (_debug)
118 # define TRACE(v) do { \
119 if (_debug) { \
120 printf v; \
121 } \
122 } while (0)
123 #elif VERBOSE == 2
124 # define INIT_TRACE(state)
125 # define DO_TRACE 1
126 # define TRACE(v) printf v
127 #else
128 # error VERBOSE must be 0, 1 or 2
129 #endif
130
131 /* -------------------------------------------------------------------- */
132 /* search engine state */
133
134 #define SRE_IS_DIGIT(ch)\
135 ((ch) <= '9' && Py_ISDIGIT(ch))
136 #define SRE_IS_SPACE(ch)\
137 ((ch) <= ' ' && Py_ISSPACE(ch))
138 #define SRE_IS_LINEBREAK(ch)\
139 ((ch) == '\n')
140 #define SRE_IS_WORD(ch)\
141 ((ch) <= 'z' && (Py_ISALNUM(ch) || (ch) == '_'))
142
143 static unsigned int sre_lower_ascii(unsigned int ch)
144 {
145 return ((ch) < 128 ? Py_TOLOWER(ch) : ch);
146 }
147
148 /* locale-specific character predicates */
149 /* !(c & ~N) == (c < N+1) for any unsigned c, this avoids
150 * warnings when c's type supports only numbers < N+1 */
151 #define SRE_LOC_IS_ALNUM(ch) (!((ch) & ~255) ? sre_isalnum((ch)) : 0)
152 #define SRE_LOC_IS_WORD(ch) (SRE_LOC_IS_ALNUM((ch)) || (ch) == '_')
153
154 static unsigned int sre_lower_locale(unsigned int ch)
155 {
156 return ((ch) < 256 ? (unsigned int)sre_tolower((ch)) : ch);
157 }
158
159 static unsigned int sre_upper_locale(unsigned int ch)
160 {
161 return ((ch) < 256 ? (unsigned int)sre_toupper((ch)) : ch);
162 }
163
164 /* unicode-specific character predicates */
165
166 #define SRE_UNI_IS_DIGIT(ch) Py_UNICODE_ISDECIMAL(ch)
167 #define SRE_UNI_IS_SPACE(ch) Py_UNICODE_ISSPACE(ch)
168 #define SRE_UNI_IS_LINEBREAK(ch) Py_UNICODE_ISLINEBREAK(ch)
169 #define SRE_UNI_IS_ALNUM(ch) Py_UNICODE_ISALNUM(ch)
170 #define SRE_UNI_IS_WORD(ch) (SRE_UNI_IS_ALNUM(ch) || (ch) == '_')
171
172 static unsigned int sre_lower_unicode(unsigned int ch)
173 {
174 return (unsigned int) Py_UNICODE_TOLOWER(ch);
175 }
176
177 static unsigned int sre_upper_unicode(unsigned int ch)
178 {
179 return (unsigned int) Py_UNICODE_TOUPPER(ch);
180 }
181
182 LOCAL(int)
183 sre_category(SRE_CODE category, unsigned int ch)
184 {
185 switch (category) {
186
187 case SRE_CATEGORY_DIGIT:
188 return SRE_IS_DIGIT(ch);
189 case SRE_CATEGORY_NOT_DIGIT:
190 return !SRE_IS_DIGIT(ch);
191 case SRE_CATEGORY_SPACE:
192 return SRE_IS_SPACE(ch);
193 case SRE_CATEGORY_NOT_SPACE:
194 return !SRE_IS_SPACE(ch);
195 case SRE_CATEGORY_WORD:
196 return SRE_IS_WORD(ch);
197 case SRE_CATEGORY_NOT_WORD:
198 return !SRE_IS_WORD(ch);
199 case SRE_CATEGORY_LINEBREAK:
200 return SRE_IS_LINEBREAK(ch);
201 case SRE_CATEGORY_NOT_LINEBREAK:
202 return !SRE_IS_LINEBREAK(ch);
203
204 case SRE_CATEGORY_LOC_WORD:
205 return SRE_LOC_IS_WORD(ch);
206 case SRE_CATEGORY_LOC_NOT_WORD:
207 return !SRE_LOC_IS_WORD(ch);
208
209 case SRE_CATEGORY_UNI_DIGIT:
210 return SRE_UNI_IS_DIGIT(ch);
211 case SRE_CATEGORY_UNI_NOT_DIGIT:
212 return !SRE_UNI_IS_DIGIT(ch);
213 case SRE_CATEGORY_UNI_SPACE:
214 return SRE_UNI_IS_SPACE(ch);
215 case SRE_CATEGORY_UNI_NOT_SPACE:
216 return !SRE_UNI_IS_SPACE(ch);
217 case SRE_CATEGORY_UNI_WORD:
218 return SRE_UNI_IS_WORD(ch);
219 case SRE_CATEGORY_UNI_NOT_WORD:
220 return !SRE_UNI_IS_WORD(ch);
221 case SRE_CATEGORY_UNI_LINEBREAK:
222 return SRE_UNI_IS_LINEBREAK(ch);
223 case SRE_CATEGORY_UNI_NOT_LINEBREAK:
224 return !SRE_UNI_IS_LINEBREAK(ch);
225 }
226 return 0;
227 }
228
229 LOCAL(int)
230 char_loc_ignore(SRE_CODE pattern, SRE_CODE ch)
231 {
232 return ch == pattern
233 || (SRE_CODE) sre_lower_locale(ch) == pattern
234 || (SRE_CODE) sre_upper_locale(ch) == pattern;
235 }
236
237
238 /* helpers */
239
240 static void
241 data_stack_dealloc(SRE_STATE* state)
242 {
243 if (state->data_stack) {
244 PyMem_Free(state->data_stack);
245 state->data_stack = NULL;
246 }
247 state->data_stack_size = state->data_stack_base = 0;
248 }
249
250 static int
251 data_stack_grow(SRE_STATE* state, Py_ssize_t size)
252 {
253 INIT_TRACE(state);
254 Py_ssize_t minsize, cursize;
255 minsize = state->data_stack_base+size;
256 cursize = state->data_stack_size;
257 if (cursize < minsize) {
258 void* stack;
259 cursize = minsize+minsize/4+1024;
260 TRACE(("allocate/grow stack %zd\n", cursize));
261 stack = PyMem_Realloc(state->data_stack, cursize);
262 if (!stack) {
263 data_stack_dealloc(state);
264 return SRE_ERROR_MEMORY;
265 }
266 state->data_stack = (char *)stack;
267 state->data_stack_size = cursize;
268 }
269 return 0;
270 }
271
272 /* memory pool functions for SRE_REPEAT, this can avoid memory
273 leak when SRE(match) function terminates abruptly.
274 state->repeat_pool_used is a doubly-linked list, so that we
275 can remove a SRE_REPEAT node from it.
276 state->repeat_pool_unused is a singly-linked list, we put/get
277 node at the head. */
278 static SRE_REPEAT *
279 repeat_pool_malloc(SRE_STATE *state)
280 {
281 SRE_REPEAT *repeat;
282
283 if (state->repeat_pool_unused) {
284 /* remove from unused pool (singly-linked list) */
285 repeat = state->repeat_pool_unused;
286 state->repeat_pool_unused = repeat->pool_next;
287 }
288 else {
289 repeat = PyMem_Malloc(sizeof(SRE_REPEAT));
290 if (!repeat) {
291 return NULL;
292 }
293 }
294
295 /* add to used pool (doubly-linked list) */
296 SRE_REPEAT *temp = state->repeat_pool_used;
297 if (temp) {
298 temp->pool_prev = repeat;
299 }
300 repeat->pool_prev = NULL;
301 repeat->pool_next = temp;
302 state->repeat_pool_used = repeat;
303
304 return repeat;
305 }
306
307 static void
308 repeat_pool_free(SRE_STATE *state, SRE_REPEAT *repeat)
309 {
310 SRE_REPEAT *prev = repeat->pool_prev;
311 SRE_REPEAT *next = repeat->pool_next;
312
313 /* remove from used pool (doubly-linked list) */
314 if (prev) {
315 prev->pool_next = next;
316 }
317 else {
318 state->repeat_pool_used = next;
319 }
320 if (next) {
321 next->pool_prev = prev;
322 }
323
324 /* add to unused pool (singly-linked list) */
325 repeat->pool_next = state->repeat_pool_unused;
326 state->repeat_pool_unused = repeat;
327 }
328
329 static void
330 repeat_pool_clear(SRE_STATE *state)
331 {
332 /* clear used pool */
333 SRE_REPEAT *next = state->repeat_pool_used;
334 state->repeat_pool_used = NULL;
335 while (next) {
336 SRE_REPEAT *temp = next;
337 next = temp->pool_next;
338 PyMem_Free(temp);
339 }
340
341 /* clear unused pool */
342 next = state->repeat_pool_unused;
343 state->repeat_pool_unused = NULL;
344 while (next) {
345 SRE_REPEAT *temp = next;
346 next = temp->pool_next;
347 PyMem_Free(temp);
348 }
349 }
350
351 /* generate 8-bit version */
352
353 #define SRE_CHAR Py_UCS1
354 #define SIZEOF_SRE_CHAR 1
355 #define SRE(F) sre_ucs1_##F
356 #include "sre_lib.h"
357
358 /* generate 16-bit unicode version */
359
360 #define SRE_CHAR Py_UCS2
361 #define SIZEOF_SRE_CHAR 2
362 #define SRE(F) sre_ucs2_##F
363 #include "sre_lib.h"
364
365 /* generate 32-bit unicode version */
366
367 #define SRE_CHAR Py_UCS4
368 #define SIZEOF_SRE_CHAR 4
369 #define SRE(F) sre_ucs4_##F
370 #include "sre_lib.h"
371
372 /* -------------------------------------------------------------------- */
373 /* factories and destructors */
374
375 /* module state */
376 typedef struct {
377 PyTypeObject *Pattern_Type;
378 PyTypeObject *Match_Type;
379 PyTypeObject *Scanner_Type;
380 PyTypeObject *Template_Type;
381 PyObject *compile_template; // reference to re._compile_template
382 } _sremodulestate;
383
384 static _sremodulestate *
385 get_sre_module_state(PyObject *m)
386 {
387 _sremodulestate *state = (_sremodulestate *)_PyModule_GetState(m);
388 assert(state);
389 return state;
390 }
391
392 static struct PyModuleDef sremodule;
393 #define get_sre_module_state_by_class(cls) \
394 (get_sre_module_state(PyType_GetModule(cls)))
395
396 /* see sre.h for object declarations */
397 static PyObject*pattern_new_match(_sremodulestate *, PatternObject*, SRE_STATE*, Py_ssize_t);
398 static PyObject *pattern_scanner(_sremodulestate *, PatternObject *, PyObject *, Py_ssize_t, Py_ssize_t);
399
400 #define _PatternObject_CAST(op) ((PatternObject *)(op))
401 #define _MatchObject_CAST(op) ((MatchObject *)(op))
402 #define _TemplateObject_CAST(op) ((TemplateObject *)(op))
403 #define _ScannerObject_CAST(op) ((ScannerObject *)(op))
404
405 /*[clinic input]
406 module _sre
407 class _sre.SRE_Pattern "PatternObject *" "get_sre_module_state_by_class(tp)->Pattern_Type"
408 class _sre.SRE_Match "MatchObject *" "get_sre_module_state_by_class(tp)->Match_Type"
409 class _sre.SRE_Scanner "ScannerObject *" "get_sre_module_state_by_class(tp)->Scanner_Type"
410 [clinic start generated code]*/
411 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=fe2966e32b66a231]*/
412
413 /*[clinic input]
414 _sre.getcodesize -> int
415 [clinic start generated code]*/
416
417 static int
418 _sre_getcodesize_impl(PyObject *module)
419 /*[clinic end generated code: output=e0db7ce34a6dd7b1 input=bd6f6ecf4916bb2b]*/
420 {
421 return sizeof(SRE_CODE);
422 }
423
424 /*[clinic input]
425 _sre.ascii_iscased -> bool
426
427 character: int
428 /
429
430 [clinic start generated code]*/
431
432 static int
433 _sre_ascii_iscased_impl(PyObject *module, int character)
434 /*[clinic end generated code: output=4f454b630fbd19a2 input=9f0bd952812c7ed3]*/
435 {
436 unsigned int ch = (unsigned int)character;
437 return ch < 128 && Py_ISALPHA(ch);
438 }
439
440 /*[clinic input]
441 _sre.unicode_iscased -> bool
442
443 character: int
444 /
445
446 [clinic start generated code]*/
447
448 static int
449 _sre_unicode_iscased_impl(PyObject *module, int character)
450 /*[clinic end generated code: output=9c5ddee0dc2bc258 input=51e42c3b8dddb78e]*/
451 {
452 unsigned int ch = (unsigned int)character;
453 return ch != sre_lower_unicode(ch) || ch != sre_upper_unicode(ch);
454 }
455
456 /*[clinic input]
457 _sre.ascii_tolower -> int
458
459 character: int
460 /
461
462 [clinic start generated code]*/
463
464 static int
465 _sre_ascii_tolower_impl(PyObject *module, int character)
466 /*[clinic end generated code: output=228294ed6ff2a612 input=272c609b5b61f136]*/
467 {
468 return sre_lower_ascii(character);
469 }
470
471 /*[clinic input]
472 _sre.unicode_tolower -> int
473
474 character: int
475 /
476
477 [clinic start generated code]*/
478
479 static int
480 _sre_unicode_tolower_impl(PyObject *module, int character)
481 /*[clinic end generated code: output=6422272d7d7fee65 input=91d708c5f3c2045a]*/
482 {
483 return sre_lower_unicode(character);
484 }
485
486 LOCAL(void)
487 state_reset(SRE_STATE* state)
488 {
489 /* state->mark will be set to 0 in SRE_OP_MARK dynamically. */
490 /*memset(state->mark, 0, sizeof(*state->mark) * SRE_MARK_SIZE);*/
491
492 state->lastmark = -1;
493 state->lastindex = -1;
494
495 state->repeat = NULL;
496
497 data_stack_dealloc(state);
498 }
499
500 static const void*
501 getstring(PyObject* string, Py_ssize_t* p_length,
502 int* p_isbytes, int* p_charsize,
503 Py_buffer *view)
504 {
505 /* given a python object, return a data pointer, a length (in
506 characters), and a character size. return NULL if the object
507 is not a string (or not compatible) */
508
509 /* Unicode objects do not support the buffer API. So, get the data
510 directly instead. */
511 if (PyUnicode_Check(string)) {
512 *p_length = PyUnicode_GET_LENGTH(string);
513 *p_charsize = PyUnicode_KIND(string);
514 *p_isbytes = 0;
515 return PyUnicode_DATA(string);
516 }
517
518 /* get pointer to byte string buffer */
519 if (PyObject_GetBuffer(string, view, PyBUF_SIMPLE) != 0) {
520 PyErr_Format(PyExc_TypeError, "expected string or bytes-like "
521 "object, got '%.200s'", Py_TYPE(string)->tp_name);
522 return NULL;
523 }
524
525 *p_length = view->len;
526 *p_charsize = 1;
527 *p_isbytes = 1;
528
529 if (view->buf == NULL) {
530 PyErr_SetString(PyExc_ValueError, "Buffer is NULL");
531 PyBuffer_Release(view);
532 view->buf = NULL;
533 return NULL;
534 }
535 return view->buf;
536 }
537
538 LOCAL(PyObject*)
539 state_init(SRE_STATE* state, PatternObject* pattern, PyObject* string,
540 Py_ssize_t start, Py_ssize_t end)
541 {
542 /* prepare state object */
543
544 Py_ssize_t length;
545 int isbytes, charsize;
546 const void* ptr;
547
548 memset(state, 0, sizeof(SRE_STATE));
549
550 state->mark = PyMem_New(const void *, pattern->groups * 2);
551 if (!state->mark) {
552 PyErr_NoMemory();
553 goto err;
554 }
555 state->lastmark = -1;
556 state->lastindex = -1;
557
558 state->buffer.buf = NULL;
559 ptr = getstring(string, &length, &isbytes, &charsize, &state->buffer);
560 if (!ptr)
561 goto err;
562
563 if (isbytes && pattern->isbytes == 0) {
564 PyErr_SetString(PyExc_TypeError,
565 "cannot use a string pattern on a bytes-like object");
566 goto err;
567 }
568 if (!isbytes && pattern->isbytes > 0) {
569 PyErr_SetString(PyExc_TypeError,
570 "cannot use a bytes pattern on a string-like object");
571 goto err;
572 }
573
574 /* adjust boundaries */
575 if (start < 0)
576 start = 0;
577 else if (start > length)
578 start = length;
579
580 if (end < 0)
581 end = 0;
582 else if (end > length)
583 end = length;
584
585 state->isbytes = isbytes;
586 state->charsize = charsize;
587 state->match_all = 0;
588 state->must_advance = 0;
589 state->debug = ((pattern->flags & SRE_FLAG_DEBUG) != 0);
590
591 state->beginning = ptr;
592
593 state->start = (void*) ((char*) ptr + start * state->charsize);
594 state->end = (void*) ((char*) ptr + end * state->charsize);
595
596 state->string = Py_NewRef(string);
597 state->pos = start;
598 state->endpos = end;
599
600 #ifdef Py_DEBUG
601 state->fail_after_count = pattern->fail_after_count;
602 state->fail_after_exc = pattern->fail_after_exc; // borrowed ref
603 #endif
604
605 return string;
606 err:
607 /* We add an explicit cast here because MSVC has a bug when
608 compiling C code where it believes that `const void**` cannot be
609 safely casted to `void*`, see bpo-39943 for details. */
610 PyMem_Free((void*) state->mark);
611 state->mark = NULL;
612 if (state->buffer.buf)
613 PyBuffer_Release(&state->buffer);
614 return NULL;
615 }
616
617 LOCAL(void)
618 state_fini(SRE_STATE* state)
619 {
620 if (state->buffer.buf)
621 PyBuffer_Release(&state->buffer);
622 Py_XDECREF(state->string);
623 data_stack_dealloc(state);
624 /* See above PyMem_Free() for why we explicitly cast here. */
625 PyMem_Free((void*) state->mark);
626 state->mark = NULL;
627 /* SRE_REPEAT pool */
628 repeat_pool_clear(state);
629 }
630
631 /* calculate offset from start of string */
632 #define STATE_OFFSET(state, member)\
633 (((char*)(member) - (char*)(state)->beginning) / (state)->charsize)
634
635 LOCAL(PyObject*)
636 getslice(int isbytes, const void *ptr,
637 PyObject* string, Py_ssize_t start, Py_ssize_t end)
638 {
639 if (isbytes) {
640 if (PyBytes_CheckExact(string) &&
641 start == 0 && end == PyBytes_GET_SIZE(string)) {
642 return Py_NewRef(string);
643 }
644 return PyBytes_FromStringAndSize(
645 (const char *)ptr + start, end - start);
646 }
647 else {
648 return PyUnicode_Substring(string, start, end);
649 }
650 }
651
652 LOCAL(PyObject*)
653 state_getslice(SRE_STATE* state, Py_ssize_t index, PyObject* string, int empty)
654 {
655 Py_ssize_t i, j;
656
657 index = (index - 1) * 2;
658
659 if (string == Py_None || index >= state->lastmark || !state->mark[index] || !state->mark[index+1]) {
660 if (empty)
661 /* want empty string */
662 i = j = 0;
663 else {
664 Py_RETURN_NONE;
665 }
666 } else {
667 i = STATE_OFFSET(state, state->mark[index]);
668 j = STATE_OFFSET(state, state->mark[index+1]);
669
670 /* check wrong span */
671 if (i > j) {
672 PyErr_SetString(PyExc_SystemError,
673 "The span of capturing group is wrong,"
674 " please report a bug for the re module.");
675 return NULL;
676 }
677 }
678
679 return getslice(state->isbytes, state->beginning, string, i, j);
680 }
681
682 static void
683 pattern_error(Py_ssize_t status)
684 {
685 switch (status) {
686 case SRE_ERROR_RECURSION_LIMIT:
687 /* This error code seems to be unused. */
688 PyErr_SetString(
689 PyExc_RecursionError,
690 "maximum recursion limit exceeded"
691 );
692 break;
693 case SRE_ERROR_MEMORY:
694 PyErr_NoMemory();
695 break;
696 case SRE_ERROR_INTERRUPTED:
697 /* An exception has already been raised, so let it fly */
698 break;
699 default:
700 /* other error codes indicate compiler/engine bugs */
701 PyErr_SetString(
702 PyExc_RuntimeError,
703 "internal error in regular expression engine"
704 );
705 }
706 }
707
708 static int
709 pattern_traverse(PyObject *op, visitproc visit, void *arg)
710 {
711 PatternObject *self = _PatternObject_CAST(op);
712 Py_VISIT(Py_TYPE(self));
713 Py_VISIT(self->groupindex);
714 Py_VISIT(self->indexgroup);
715 Py_VISIT(self->pattern);
716 #ifdef Py_DEBUG
717 Py_VISIT(self->fail_after_exc);
718 #endif
719 return 0;
720 }
721
722 static int
723 pattern_clear(PyObject *op)
724 {
725 PatternObject *self = _PatternObject_CAST(op);
726 Py_CLEAR(self->groupindex);
727 Py_CLEAR(self->indexgroup);
728 Py_CLEAR(self->pattern);
729 #ifdef Py_DEBUG
730 Py_CLEAR(self->fail_after_exc);
731 #endif
732 return 0;
733 }
734
735 static void
736 pattern_dealloc(PyObject *self)
737 {
738 PyTypeObject *tp = Py_TYPE(self);
739 PyObject_GC_UnTrack(self);
740 FT_CLEAR_WEAKREFS(self, _PatternObject_CAST(self)->weakreflist);
741 (void)pattern_clear(self);
742 tp->tp_free(self);
743 Py_DECREF(tp);
744 }
745
746 LOCAL(Py_ssize_t)
747 sre_match(SRE_STATE* state, SRE_CODE* pattern)
748 {
749 if (state->charsize == 1)
750 return sre_ucs1_match(state, pattern, 1);
751 if (state->charsize == 2)
752 return sre_ucs2_match(state, pattern, 1);
753 assert(state->charsize == 4);
754 return sre_ucs4_match(state, pattern, 1);
755 }
756
757 LOCAL(Py_ssize_t)
758 sre_search(SRE_STATE* state, SRE_CODE* pattern)
759 {
760 if (state->charsize == 1)
761 return sre_ucs1_search(state, pattern);
762 if (state->charsize == 2)
763 return sre_ucs2_search(state, pattern);
764 assert(state->charsize == 4);
765 return sre_ucs4_search(state, pattern);
766 }
767
768 /*[clinic input]
769 _sre.SRE_Pattern.match
770
771 cls: defining_class
772 /
773 string: object
774 pos: Py_ssize_t = 0
775 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize
776
777 Matches zero or more characters at the beginning of the string.
778 [clinic start generated code]*/
779
780 static PyObject *
781 _sre_SRE_Pattern_match_impl(PatternObject *self, PyTypeObject *cls,
782 PyObject *string, Py_ssize_t pos,
783 Py_ssize_t endpos)
784 /*[clinic end generated code: output=ec6208ea58a0cca0 input=4bdb9c3e564d13ac]*/
785 {
786 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
787 SRE_STATE state;
788 Py_ssize_t status;
789 PyObject *match;
790
791 if (!state_init(&state, self, string, pos, endpos))
792 return NULL;
793
794 INIT_TRACE(&state);
795 state.ptr = state.start;
796
797 TRACE(("|%p|%p|MATCH\n", PatternObject_GetCode(self), state.ptr));
798
799 status = sre_match(&state, PatternObject_GetCode(self));
800
801 TRACE(("|%p|%p|END\n", PatternObject_GetCode(self), state.ptr));
802 if (PyErr_Occurred()) {
803 state_fini(&state);
804 return NULL;
805 }
806
807 match = pattern_new_match(module_state, self, &state, status);
808 state_fini(&state);
809 return match;
810 }
811
812 /*[clinic input]
813 _sre.SRE_Pattern.fullmatch
814
815 cls: defining_class
816 /
817 string: object
818 pos: Py_ssize_t = 0
819 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize
820
821 Matches against all of the string.
822 [clinic start generated code]*/
823
824 static PyObject *
825 _sre_SRE_Pattern_fullmatch_impl(PatternObject *self, PyTypeObject *cls,
826 PyObject *string, Py_ssize_t pos,
827 Py_ssize_t endpos)
828 /*[clinic end generated code: output=625b75b027ef94da input=50981172ab0fcfdd]*/
829 {
830 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
831 SRE_STATE state;
832 Py_ssize_t status;
833 PyObject *match;
834
835 if (!state_init(&state, self, string, pos, endpos))
836 return NULL;
837
838 INIT_TRACE(&state);
839 state.ptr = state.start;
840
841 TRACE(("|%p|%p|FULLMATCH\n", PatternObject_GetCode(self), state.ptr));
842
843 state.match_all = 1;
844 status = sre_match(&state, PatternObject_GetCode(self));
845
846 TRACE(("|%p|%p|END\n", PatternObject_GetCode(self), state.ptr));
847 if (PyErr_Occurred()) {
848 state_fini(&state);
849 return NULL;
850 }
851
852 match = pattern_new_match(module_state, self, &state, status);
853 state_fini(&state);
854 return match;
855 }
856
857 /*[clinic input]
858 _sre.SRE_Pattern.search
859
860 cls: defining_class
861 /
862 string: object
863 pos: Py_ssize_t = 0
864 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize
865
866 Scan through string looking for a match, and return a corresponding match object instance.
867
868 Return None if no position in the string matches.
869 [clinic start generated code]*/
870
871 static PyObject *
872 _sre_SRE_Pattern_search_impl(PatternObject *self, PyTypeObject *cls,
873 PyObject *string, Py_ssize_t pos,
874 Py_ssize_t endpos)
875 /*[clinic end generated code: output=bd7f2d9d583e1463 input=afa9afb66a74a4b3]*/
876 {
877 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
878 SRE_STATE state;
879 Py_ssize_t status;
880 PyObject *match;
881
882 if (!state_init(&state, self, string, pos, endpos))
883 return NULL;
884
885 INIT_TRACE(&state);
886 TRACE(("|%p|%p|SEARCH\n", PatternObject_GetCode(self), state.ptr));
887
888 status = sre_search(&state, PatternObject_GetCode(self));
889
890 TRACE(("|%p|%p|END\n", PatternObject_GetCode(self), state.ptr));
891
892 if (PyErr_Occurred()) {
893 state_fini(&state);
894 return NULL;
895 }
896
897 match = pattern_new_match(module_state, self, &state, status);
898 state_fini(&state);
899 return match;
900 }
901
902 /*[clinic input]
903 _sre.SRE_Pattern.findall
904
905 string: object
906 pos: Py_ssize_t = 0
907 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize
908
909 Return a list of all non-overlapping matches of pattern in string.
910 [clinic start generated code]*/
911
912 static PyObject *
913 _sre_SRE_Pattern_findall_impl(PatternObject *self, PyObject *string,
914 Py_ssize_t pos, Py_ssize_t endpos)
915 /*[clinic end generated code: output=f4966baceea60aca input=5b6a4ee799741563]*/
916 {
917 SRE_STATE state;
918 PyObject* list;
919 Py_ssize_t status;
920 Py_ssize_t i, b, e;
921
922 if (!state_init(&state, self, string, pos, endpos))
923 return NULL;
924
925 list = PyList_New(0);
926 if (!list) {
927 state_fini(&state);
928 return NULL;
929 }
930
931 while (state.start <= state.end) {
932
933 PyObject* item;
934
935 state_reset(&state);
936
937 state.ptr = state.start;
938
939 status = sre_search(&state, PatternObject_GetCode(self));
940 if (PyErr_Occurred())
941 goto error;
942
943 if (status <= 0) {
944 if (status == 0)
945 break;
946 pattern_error(status);
947 goto error;
948 }
949
950 /* don't bother to build a match object */
951 switch (self->groups) {
952 case 0:
953 b = STATE_OFFSET(&state, state.start);
954 e = STATE_OFFSET(&state, state.ptr);
955 item = getslice(state.isbytes, state.beginning,
956 string, b, e);
957 if (!item)
958 goto error;
959 break;
960 case 1:
961 item = state_getslice(&state, 1, string, 1);
962 if (!item)
963 goto error;
964 break;
965 default:
966 item = PyTuple_New(self->groups);
967 if (!item)
968 goto error;
969 for (i = 0; i < self->groups; i++) {
970 PyObject* o = state_getslice(&state, i+1, string, 1);
971 if (!o) {
972 Py_DECREF(item);
973 goto error;
974 }
975 PyTuple_SET_ITEM(item, i, o);
976 }
977 break;
978 }
979
980 status = PyList_Append(list, item);
981 Py_DECREF(item);
982 if (status < 0)
983 goto error;
984
985 state.must_advance = (state.ptr == state.start);
986 state.start = state.ptr;
987 }
988
989 state_fini(&state);
990 return list;
991
992 error:
993 Py_DECREF(list);
994 state_fini(&state);
995 return NULL;
996
997 }
998
999 /*[clinic input]
1000 _sre.SRE_Pattern.finditer
1001
1002 cls: defining_class
1003 /
1004 string: object
1005 pos: Py_ssize_t = 0
1006 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize
1007
1008 Return an iterator over all non-overlapping matches for the RE pattern in string.
1009
1010 For each match, the iterator returns a match object.
1011 [clinic start generated code]*/
1012
1013 static PyObject *
1014 _sre_SRE_Pattern_finditer_impl(PatternObject *self, PyTypeObject *cls,
1015 PyObject *string, Py_ssize_t pos,
1016 Py_ssize_t endpos)
1017 /*[clinic end generated code: output=1791dbf3618ade56 input=812e332a4848cbaf]*/
1018 {
1019 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
1020 PyObject* scanner;
1021 PyObject* search;
1022 PyObject* iterator;
1023
1024 scanner = pattern_scanner(module_state, self, string, pos, endpos);
1025 if (!scanner)
1026 return NULL;
1027
1028 search = PyObject_GetAttrString(scanner, "search");
1029 Py_DECREF(scanner);
1030 if (!search)
1031 return NULL;
1032
1033 iterator = PyCallIter_New(search, Py_None);
1034 Py_DECREF(search);
1035
1036 return iterator;
1037 }
1038
1039 /*[clinic input]
1040 _sre.SRE_Pattern.scanner
1041
1042 cls: defining_class
1043 /
1044 string: object
1045 pos: Py_ssize_t = 0
1046 endpos: Py_ssize_t(c_default="PY_SSIZE_T_MAX") = sys.maxsize
1047
1048 [clinic start generated code]*/
1049
1050 static PyObject *
1051 _sre_SRE_Pattern_scanner_impl(PatternObject *self, PyTypeObject *cls,
1052 PyObject *string, Py_ssize_t pos,
1053 Py_ssize_t endpos)
1054 /*[clinic end generated code: output=f70cd506112f1bd9 input=2e487e5151bcee4c]*/
1055 {
1056 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
1057
1058 return pattern_scanner(module_state, self, string, pos, endpos);
1059 }
1060
1061 /*[clinic input]
1062 _sre.SRE_Pattern.split
1063
1064 string: object
1065 maxsplit: Py_ssize_t = 0
1066
1067 Split string by the occurrences of pattern.
1068 [clinic start generated code]*/
1069
1070 static PyObject *
1071 _sre_SRE_Pattern_split_impl(PatternObject *self, PyObject *string,
1072 Py_ssize_t maxsplit)
1073 /*[clinic end generated code: output=7ac66f381c45e0be input=1eeeb10dafc9947a]*/
1074 {
1075 SRE_STATE state;
1076 PyObject* list;
1077 PyObject* item;
1078 Py_ssize_t status;
1079 Py_ssize_t n;
1080 Py_ssize_t i;
1081 const void* last;
1082
1083 assert(self->codesize != 0);
1084
1085 if (!state_init(&state, self, string, 0, PY_SSIZE_T_MAX))
1086 return NULL;
1087
1088 list = PyList_New(0);
1089 if (!list) {
1090 state_fini(&state);
1091 return NULL;
1092 }
1093
1094 n = 0;
1095 last = state.start;
1096
1097 while (!maxsplit || n < maxsplit) {
1098
1099 state_reset(&state);
1100
1101 state.ptr = state.start;
1102
1103 status = sre_search(&state, PatternObject_GetCode(self));
1104 if (PyErr_Occurred())
1105 goto error;
1106
1107 if (status <= 0) {
1108 if (status == 0)
1109 break;
1110 pattern_error(status);
1111 goto error;
1112 }
1113
1114 /* get segment before this match */
1115 item = getslice(state.isbytes, state.beginning,
1116 string, STATE_OFFSET(&state, last),
1117 STATE_OFFSET(&state, state.start)
1118 );
1119 if (!item)
1120 goto error;
1121 status = PyList_Append(list, item);
1122 Py_DECREF(item);
1123 if (status < 0)
1124 goto error;
1125
1126 /* add groups (if any) */
1127 for (i = 0; i < self->groups; i++) {
1128 item = state_getslice(&state, i+1, string, 0);
1129 if (!item)
1130 goto error;
1131 status = PyList_Append(list, item);
1132 Py_DECREF(item);
1133 if (status < 0)
1134 goto error;
1135 }
1136
1137 n = n + 1;
1138 state.must_advance = (state.ptr == state.start);
1139 last = state.start = state.ptr;
1140
1141 }
1142
1143 /* get segment following last match (even if empty) */
1144 item = getslice(state.isbytes, state.beginning,
1145 string, STATE_OFFSET(&state, last), state.endpos
1146 );
1147 if (!item)
1148 goto error;
1149 status = PyList_Append(list, item);
1150 Py_DECREF(item);
1151 if (status < 0)
1152 goto error;
1153
1154 state_fini(&state);
1155 return list;
1156
1157 error:
1158 Py_DECREF(list);
1159 state_fini(&state);
1160 return NULL;
1161
1162 }
1163
1164 static PyObject *
1165 compile_template(_sremodulestate *module_state,
1166 PatternObject *pattern, PyObject *template)
1167 {
1168 /* delegate to Python code */
1169 PyObject *func = FT_ATOMIC_LOAD_PTR(module_state->compile_template);
1170 if (func == NULL) {
1171 func = PyImport_ImportModuleAttrString("re", "_compile_template");
1172 if (func == NULL) {
1173 return NULL;
1174 }
1175 #ifdef Py_GIL_DISABLED
1176 PyObject *other_func = NULL;
1177 if (!_Py_atomic_compare_exchange_ptr(&module_state->compile_template, &other_func, func)) {
1178 Py_DECREF(func);
1179 func = other_func;
1180 }
1181 #else
1182 Py_XSETREF(module_state->compile_template, func);
1183 #endif
1184 }
1185
1186 PyObject *args[] = {(PyObject *)pattern, template};
1187 PyObject *result = PyObject_Vectorcall(func, args, 2, NULL);
1188
1189 if (result == NULL && PyErr_ExceptionMatches(PyExc_TypeError)) {
1190 /* If the replacement string is unhashable (e.g. bytearray),
1191 * convert it to the basic type (str or bytes) and repeat. */
1192 if (PyUnicode_Check(template) && !PyUnicode_CheckExact(template)) {
1193 PyErr_Clear();
1194 template = _PyUnicode_Copy(template);
1195 }
1196 else if (PyObject_CheckBuffer(template) && !PyBytes_CheckExact(template)) {
1197 PyErr_Clear();
1198 template = PyBytes_FromObject(template);
1199 }
1200 else {
1201 return NULL;
1202 }
1203 if (template == NULL) {
1204 return NULL;
1205 }
1206 args[1] = template;
1207 result = PyObject_Vectorcall(func, args, 2, NULL);
1208 Py_DECREF(template);
1209 }
1210
1211 if (result != NULL && Py_TYPE(result) != module_state->Template_Type) {
1212 PyErr_Format(PyExc_RuntimeError,
1213 "the result of compiling a replacement string is %.200s",
1214 Py_TYPE(result)->tp_name);
1215 Py_DECREF(result);
1216 return NULL;
1217 }
1218 return result;
1219 }
1220
1221 static PyObject *expand_template(TemplateObject *, MatchObject *); /* Forward */
1222
1223 static PyObject*
1224 pattern_subx(_sremodulestate* module_state,
1225 PatternObject* self,
1226 PyObject* ptemplate,
1227 PyObject* string,
1228 Py_ssize_t count,
1229 Py_ssize_t subn)
1230 {
1231 SRE_STATE state;
1232 PyObject* list;
1233 PyObject* joiner;
1234 PyObject* item;
1235 PyObject* filter;
1236 PyObject* match;
1237 const void* ptr;
1238 Py_ssize_t status;
1239 Py_ssize_t n;
1240 Py_ssize_t i, b, e;
1241 int isbytes, charsize;
1242 enum {LITERAL, TEMPLATE, CALLABLE} filter_type;
1243 Py_buffer view;
1244
1245 if (PyCallable_Check(ptemplate)) {
1246 /* sub/subn takes either a function or a template */
1247 filter = Py_NewRef(ptemplate);
1248 filter_type = CALLABLE;
1249 } else {
1250 /* if not callable, check if it's a literal string */
1251 int literal;
1252 view.buf = NULL;
1253 ptr = getstring(ptemplate, &n, &isbytes, &charsize, &view);
1254 if (ptr) {
1255 if (charsize == 1)
1256 literal = memchr(ptr, '\\', n) == NULL;
1257 else
1258 literal = PyUnicode_FindChar(ptemplate, '\\', 0, n, 1) == -1;
1259 } else {
1260 PyErr_Clear();
1261 literal = 0;
1262 }
1263 if (view.buf)
1264 PyBuffer_Release(&view);
1265 if (literal) {
1266 filter = Py_NewRef(ptemplate);
1267 filter_type = LITERAL;
1268 } else {
1269 /* not a literal; hand it over to the template compiler */
1270 filter = compile_template(module_state, self, ptemplate);
1271 if (!filter)
1272 return NULL;
1273
1274 assert(Py_TYPE(filter) == module_state->Template_Type);
1275 if (Py_SIZE(filter) == 0) {
1276 Py_SETREF(filter,
1277 Py_NewRef(((TemplateObject *)filter)->literal));
1278 filter_type = LITERAL;
1279 }
1280 else {
1281 filter_type = TEMPLATE;
1282 }
1283 }
1284 }
1285
1286 if (!state_init(&state, self, string, 0, PY_SSIZE_T_MAX)) {
1287 Py_DECREF(filter);
1288 return NULL;
1289 }
1290
1291 list = PyList_New(0);
1292 if (!list) {
1293 Py_DECREF(filter);
1294 state_fini(&state);
1295 return NULL;
1296 }
1297
1298 n = i = 0;
1299
1300 while (!count || n < count) {
1301
1302 state_reset(&state);
1303
1304 state.ptr = state.start;
1305
1306 status = sre_search(&state, PatternObject_GetCode(self));
1307 if (PyErr_Occurred())
1308 goto error;
1309
1310 if (status <= 0) {
1311 if (status == 0)
1312 break;
1313 pattern_error(status);
1314 goto error;
1315 }
1316
1317 b = STATE_OFFSET(&state, state.start);
1318 e = STATE_OFFSET(&state, state.ptr);
1319
1320 if (i < b) {
1321 /* get segment before this match */
1322 item = getslice(state.isbytes, state.beginning,
1323 string, i, b);
1324 if (!item)
1325 goto error;
1326 status = PyList_Append(list, item);
1327 Py_DECREF(item);
1328 if (status < 0)
1329 goto error;
1330
1331 }
1332
1333 if (filter_type != LITERAL) {
1334 /* pass match object through filter */
1335 match = pattern_new_match(module_state, self, &state, 1);
1336 if (!match)
1337 goto error;
1338 if (filter_type == TEMPLATE) {
1339 item = expand_template((TemplateObject *)filter,
1340 (MatchObject *)match);
1341 }
1342 else {
1343 assert(filter_type == CALLABLE);
1344 item = PyObject_CallOneArg(filter, match);
1345 }
1346 Py_DECREF(match);
1347 if (!item)
1348 goto error;
1349 } else {
1350 /* filter is literal string */
1351 item = Py_NewRef(filter);
1352 }
1353
1354 /* add to list */
1355 if (item != Py_None) {
1356 status = PyList_Append(list, item);
1357 Py_DECREF(item);
1358 if (status < 0)
1359 goto error;
1360 }
1361
1362 i = e;
1363 n = n + 1;
1364 state.must_advance = (state.ptr == state.start);
1365 state.start = state.ptr;
1366 }
1367
1368 /* get segment following last match */
1369 if (i < state.endpos) {
1370 item = getslice(state.isbytes, state.beginning,
1371 string, i, state.endpos);
1372 if (!item)
1373 goto error;
1374 status = PyList_Append(list, item);
1375 Py_DECREF(item);
1376 if (status < 0)
1377 goto error;
1378 }
1379
1380 state_fini(&state);
1381
1382 Py_DECREF(filter);
1383
1384 /* convert list to single string (also removes list) */
1385 joiner = getslice(state.isbytes, state.beginning, string, 0, 0);
1386 if (!joiner) {
1387 Py_DECREF(list);
1388 return NULL;
1389 }
1390 if (PyList_GET_SIZE(list) == 0) {
1391 Py_DECREF(list);
1392 item = joiner;
1393 }
1394 else {
1395 if (state.isbytes)
1396 item = PyBytes_Join(joiner, list);
1397 else
1398 item = PyUnicode_Join(joiner, list);
1399 Py_DECREF(joiner);
1400 Py_DECREF(list);
1401 if (!item)
1402 return NULL;
1403 }
1404
1405 if (subn)
1406 return Py_BuildValue("Nn", item, n);
1407
1408 return item;
1409
1410 error:
1411 Py_DECREF(list);
1412 state_fini(&state);
1413 Py_DECREF(filter);
1414 return NULL;
1415
1416 }
1417
1418 /*[clinic input]
1419 _sre.SRE_Pattern.sub
1420
1421 cls: defining_class
1422 /
1423 repl: object
1424 string: object
1425 count: Py_ssize_t = 0
1426
1427 Return the string obtained by replacing the leftmost non-overlapping occurrences of pattern in string by the replacement repl.
1428 [clinic start generated code]*/
1429
1430 static PyObject *
1431 _sre_SRE_Pattern_sub_impl(PatternObject *self, PyTypeObject *cls,
1432 PyObject *repl, PyObject *string, Py_ssize_t count)
1433 /*[clinic end generated code: output=4be141ab04bca60d input=d8d1d4ac2311a07c]*/
1434 {
1435 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
1436
1437 return pattern_subx(module_state, self, repl, string, count, 0);
1438 }
1439
1440 /*[clinic input]
1441 _sre.SRE_Pattern.subn
1442
1443 cls: defining_class
1444 /
1445 repl: object
1446 string: object
1447 count: Py_ssize_t = 0
1448
1449 Return the tuple (new_string, number_of_subs_made) found by replacing the leftmost non-overlapping occurrences of pattern with the replacement repl.
1450 [clinic start generated code]*/
1451
1452 static PyObject *
1453 _sre_SRE_Pattern_subn_impl(PatternObject *self, PyTypeObject *cls,
1454 PyObject *repl, PyObject *string,
1455 Py_ssize_t count)
1456 /*[clinic end generated code: output=da02fd85258b1e1f input=8b78a65b8302e58d]*/
1457 {
1458 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
1459
1460 return pattern_subx(module_state, self, repl, string, count, 1);
1461 }
1462
1463 /*[clinic input]
1464 _sre.SRE_Pattern.__copy__
1465
1466 [clinic start generated code]*/
1467
1468 static PyObject *
1469 _sre_SRE_Pattern___copy___impl(PatternObject *self)
1470 /*[clinic end generated code: output=85dedc2db1bd8694 input=a730a59d863bc9f5]*/
1471 {
1472 return Py_NewRef(self);
1473 }
1474
1475 /*[clinic input]
1476 _sre.SRE_Pattern.__deepcopy__
1477
1478 memo: object
1479 /
1480
1481 [clinic start generated code]*/
1482
1483 static PyObject *
1484 _sre_SRE_Pattern___deepcopy___impl(PatternObject *self, PyObject *memo)
1485 /*[clinic end generated code: output=75efe69bd12c5d7d input=a465b1602f997bed]*/
1486 {
1487 return Py_NewRef(self);
1488 }
1489
1490 #ifdef Py_DEBUG
1491 /*[clinic input]
1492 _sre.SRE_Pattern._fail_after
1493
1494 count: int
1495 exception: object
1496 /
1497
1498 For debugging.
1499 [clinic start generated code]*/
1500
1501 static PyObject *
1502 _sre_SRE_Pattern__fail_after_impl(PatternObject *self, int count,
1503 PyObject *exception)
1504 /*[clinic end generated code: output=9a6bf12135ac50c2 input=ef80a45c66c5499d]*/
1505 {
1506 self->fail_after_count = count;
1507 Py_INCREF(exception);
1508 Py_XSETREF(self->fail_after_exc, exception);
1509 Py_RETURN_NONE;
1510 }
1511 #endif /* Py_DEBUG */
1512
1513 static PyObject *
1514 pattern_repr(PyObject *self)
1515 {
1516 static const struct {
1517 const char *name;
1518 int value;
1519 } flag_names[] = {
1520 {"re.IGNORECASE", SRE_FLAG_IGNORECASE},
1521 {"re.LOCALE", SRE_FLAG_LOCALE},
1522 {"re.MULTILINE", SRE_FLAG_MULTILINE},
1523 {"re.DOTALL", SRE_FLAG_DOTALL},
1524 {"re.UNICODE", SRE_FLAG_UNICODE},
1525 {"re.VERBOSE", SRE_FLAG_VERBOSE},
1526 {"re.DEBUG", SRE_FLAG_DEBUG},
1527 {"re.ASCII", SRE_FLAG_ASCII},
1528 };
1529
1530 PatternObject *obj = _PatternObject_CAST(self);
1531 PyObject *result = NULL;
1532 PyObject *flag_items;
1533 size_t i;
1534 int flags = obj->flags;
1535
1536 /* Omit re.UNICODE for valid string patterns. */
1537 if (obj->isbytes == 0 &&
1538 (flags & (SRE_FLAG_LOCALE|SRE_FLAG_UNICODE|SRE_FLAG_ASCII)) ==
1539 SRE_FLAG_UNICODE)
1540 flags &= ~SRE_FLAG_UNICODE;
1541
1542 flag_items = PyList_New(0);
1543 if (!flag_items)
1544 return NULL;
1545
1546 for (i = 0; i < Py_ARRAY_LENGTH(flag_names); i++) {
1547 if (flags & flag_names[i].value) {
1548 PyObject *item = PyUnicode_FromString(flag_names[i].name);
1549 if (!item)
1550 goto done;
1551
1552 if (PyList_Append(flag_items, item) < 0) {
1553 Py_DECREF(item);
1554 goto done;
1555 }
1556 Py_DECREF(item);
1557 flags &= ~flag_names[i].value;
1558 }
1559 }
1560 if (flags) {
1561 PyObject *item = PyUnicode_FromFormat("0x%x", flags);
1562 if (!item)
1563 goto done;
1564
1565 if (PyList_Append(flag_items, item) < 0) {
1566 Py_DECREF(item);
1567 goto done;
1568 }
1569 Py_DECREF(item);
1570 }
1571
1572 if (PyList_Size(flag_items) > 0) {
1573 PyObject *flags_result;
1574 PyObject *sep = PyUnicode_FromString("|");
1575 if (!sep)
1576 goto done;
1577 flags_result = PyUnicode_Join(sep, flag_items);
1578 Py_DECREF(sep);
1579 if (!flags_result)
1580 goto done;
1581 result = PyUnicode_FromFormat("re.compile(%.200R, %S)",
1582 obj->pattern, flags_result);
1583 Py_DECREF(flags_result);
1584 }
1585 else {
1586 result = PyUnicode_FromFormat("re.compile(%.200R)", obj->pattern);
1587 }
1588
1589 done:
1590 Py_DECREF(flag_items);
1591 return result;
1592 }
1593
1594 PyDoc_STRVAR(pattern_doc, "Compiled regular expression object.");
1595
1596 /* PatternObject's 'groupindex' method. */
1597 static PyObject *
1598 pattern_groupindex(PyObject *op, void *Py_UNUSED(ignored))
1599 {
1600 PatternObject *self = _PatternObject_CAST(op);
1601 if (self->groupindex == NULL)
1602 return PyDict_New();
1603 return PyDictProxy_New(self->groupindex);
1604 }
1605
1606 static int _validate(PatternObject *self); /* Forward */
1607
1608 /*[clinic input]
1609 _sre.compile
1610
1611 pattern: object
1612 flags: int
1613 code: object(subclass_of='&PyList_Type')
1614 groups: Py_ssize_t
1615 groupindex: object(subclass_of='&PyDict_Type')
1616 indexgroup: object(subclass_of='&PyTuple_Type')
1617
1618 [clinic start generated code]*/
1619
1620 static PyObject *
1621 _sre_compile_impl(PyObject *module, PyObject *pattern, int flags,
1622 PyObject *code, Py_ssize_t groups, PyObject *groupindex,
1623 PyObject *indexgroup)
1624 /*[clinic end generated code: output=ef9c2b3693776404 input=0a68476dbbe5db30]*/
1625 {
1626 /* "compile" pattern descriptor to pattern object */
1627
1628 _sremodulestate *module_state = get_sre_module_state(module);
1629 PatternObject* self;
1630 Py_ssize_t i, n;
1631
1632 n = PyList_GET_SIZE(code);
1633 /* coverity[ampersand_in_size] */
1634 self = PyObject_GC_NewVar(PatternObject, module_state->Pattern_Type, n);
1635 if (!self)
1636 return NULL;
1637 self->weakreflist = NULL;
1638 self->pattern = NULL;
1639 self->groupindex = NULL;
1640 self->indexgroup = NULL;
1641 #ifdef Py_DEBUG
1642 self->fail_after_count = -1;
1643 self->fail_after_exc = NULL;
1644 #endif
1645
1646 self->codesize = n;
1647
1648 for (i = 0; i < n; i++) {
1649 PyObject *o = PyList_GET_ITEM(code, i);
1650 unsigned long value = PyLong_AsUnsignedLong(o);
1651 if (value == (unsigned long)-1 && PyErr_Occurred()) {
1652 break;
1653 }
1654 self->code[i] = (SRE_CODE) value;
1655 if ((unsigned long) self->code[i] != value) {
1656 PyErr_SetString(PyExc_OverflowError,
1657 "regular expression code size limit exceeded");
1658 break;
1659 }
1660 }
1661 PyObject_GC_Track(self);
1662
1663 if (PyErr_Occurred()) {
1664 Py_DECREF(self);
1665 return NULL;
1666 }
1667
1668 if (pattern == Py_None) {
1669 self->isbytes = -1;
1670 }
1671 else {
1672 Py_ssize_t p_length;
1673 int charsize;
1674 Py_buffer view;
1675 view.buf = NULL;
1676 if (!getstring(pattern, &p_length, &self->isbytes,
1677 &charsize, &view)) {
1678 Py_DECREF(self);
1679 return NULL;
1680 }
1681 if (view.buf)
1682 PyBuffer_Release(&view);
1683 }
1684
1685 self->pattern = Py_NewRef(pattern);
1686
1687 self->flags = flags;
1688
1689 self->groups = groups;
1690
1691 if (PyDict_GET_SIZE(groupindex) > 0) {
1692 self->groupindex = Py_NewRef(groupindex);
1693 if (PyTuple_GET_SIZE(indexgroup) > 0) {
1694 self->indexgroup = Py_NewRef(indexgroup);
1695 }
1696 }
1697
1698 if (!_validate(self)) {
1699 Py_DECREF(self);
1700 return NULL;
1701 }
1702
1703 return (PyObject*) self;
1704 }
1705
1706 /*[clinic input]
1707 _sre.template
1708
1709 pattern: object
1710 template: object(subclass_of="&PyList_Type")
1711 A list containing interleaved literal strings (str or bytes) and group
1712 indices (int), as returned by re._parser.parse_template():
1713 [literal1, group1, ..., literalN, groupN]
1714 /
1715
1716 [clinic start generated code]*/
1717
1718 static PyObject *
1719 _sre_template_impl(PyObject *module, PyObject *pattern, PyObject *template)
1720 /*[clinic end generated code: output=d51290e596ebca86 input=af55380b27f02942]*/
1721 {
1722 /* template is a list containing interleaved literal strings (str or bytes)
1723 * and group indices (int), as returned by _parser.parse_template:
1724 * [literal1, group1, literal2, ..., literalN].
1725 */
1726 _sremodulestate *module_state = get_sre_module_state(module);
1727 TemplateObject *self = NULL;
1728 Py_ssize_t n = PyList_GET_SIZE(template);
1729 if ((n & 1) == 0 || n < 1) {
1730 goto bad_template;
1731 }
1732 n /= 2;
1733 self = PyObject_GC_NewVar(TemplateObject, module_state->Template_Type, n);
1734 if (!self)
1735 return NULL;
1736 self->chunks = 1 + 2*n;
1737 self->literal = Py_NewRef(PyList_GET_ITEM(template, 0));
1738 for (Py_ssize_t i = 0; i < n; i++) {
1739 Py_ssize_t index = PyLong_AsSsize_t(PyList_GET_ITEM(template, 2*i+1));
1740 if (index == -1 && PyErr_Occurred()) {
1741 Py_SET_SIZE(self, i);
1742 Py_DECREF(self);
1743 return NULL;
1744 }
1745 if (index < 0) {
1746 Py_SET_SIZE(self, i);
1747 goto bad_template;
1748 }
1749 self->items[i].index = index;
1750
1751 PyObject *literal = PyList_GET_ITEM(template, 2*i+2);
1752 // Skip empty literals.
1753 if ((PyUnicode_Check(literal) && !PyUnicode_GET_LENGTH(literal)) ||
1754 (PyBytes_Check(literal) && !PyBytes_GET_SIZE(literal)))
1755 {
1756 literal = NULL;
1757 self->chunks--;
1758 }
1759 self->items[i].literal = Py_XNewRef(literal);
1760 }
1761 PyObject_GC_Track(self);
1762 return (PyObject*) self;
1763
1764 bad_template:
1765 PyErr_SetString(PyExc_TypeError, "invalid template");
1766 Py_XDECREF(self);
1767 return NULL;
1768 }
1769
1770 /* -------------------------------------------------------------------- */
1771 /* Code validation */
1772
1773 /* To learn more about this code, have a look at the _compile() function in
1774 Lib/sre_compile.py. The validation functions below checks the code array
1775 for conformance with the code patterns generated there.
1776
1777 The nice thing about the generated code is that it is position-independent:
1778 all jumps are relative jumps forward. Also, jumps don't cross each other:
1779 the target of a later jump is always earlier than the target of an earlier
1780 jump. IOW, this is okay:
1781
1782 J---------J-------T--------T
1783 \ \_____/ /
1784 \______________________/
1785
1786 but this is not:
1787
1788 J---------J-------T--------T
1789 \_________\_____/ /
1790 \____________/
1791
1792 It also helps that SRE_CODE is always an unsigned type.
1793 */
1794
1795 /* Defining this one enables tracing of the validator */
1796 #undef VVERBOSE
1797
1798 /* Trace macro for the validator */
1799 #if defined(VVERBOSE)
1800 #define VTRACE(v) printf v
1801 #else
1802 #define VTRACE(v) do {} while(0) /* do nothing */
1803 #endif
1804
1805 /* Report failure */
1806 #define FAIL do { VTRACE(("FAIL: %d\n", __LINE__)); return -1; } while (0)
1807
1808 /* Extract opcode, argument, or skip count from code array */
1809 #define GET_OP \
1810 do { \
1811 VTRACE(("%p: ", code)); \
1812 if (code >= end) FAIL; \
1813 op = *code++; \
1814 VTRACE(("%lu (op)\n", (unsigned long)op)); \
1815 } while (0)
1816 #define GET_ARG \
1817 do { \
1818 VTRACE(("%p= ", code)); \
1819 if (code >= end) FAIL; \
1820 arg = *code++; \
1821 VTRACE(("%lu (arg)\n", (unsigned long)arg)); \
1822 } while (0)
1823 #define GET_SKIP_ADJ(adj) \
1824 do { \
1825 VTRACE(("%p= ", code)); \
1826 if (code >= end) FAIL; \
1827 skip = *code; \
1828 VTRACE(("%lu (skip to %p)\n", \
1829 (unsigned long)skip, code+skip)); \
1830 if (skip-adj > (uintptr_t)(end - code)) \
1831 FAIL; \
1832 code++; \
1833 } while (0)
1834 #define GET_SKIP GET_SKIP_ADJ(0)
1835
1836 static int
1837 _validate_charset(SRE_CODE *code, SRE_CODE *end)
1838 {
1839 /* Some variables are manipulated by the macros above */
1840 SRE_CODE op;
1841 SRE_CODE arg;
1842 SRE_CODE offset;
1843 int i;
1844
1845 while (code < end) {
1846 GET_OP;
1847 switch (op) {
1848
1849 case SRE_OP_NEGATE:
1850 break;
1851
1852 case SRE_OP_LITERAL:
1853 GET_ARG;
1854 break;
1855
1856 case SRE_OP_RANGE:
1857 case SRE_OP_RANGE_UNI_IGNORE:
1858 GET_ARG;
1859 GET_ARG;
1860 break;
1861
1862 case SRE_OP_CHARSET:
1863 offset = 256/SRE_CODE_BITS; /* 256-bit bitmap */
1864 if (offset > (uintptr_t)(end - code))
1865 FAIL;
1866 code += offset;
1867 break;
1868
1869 case SRE_OP_BIGCHARSET:
1870 GET_ARG; /* Number of blocks */
1871 offset = 256/sizeof(SRE_CODE); /* 256-byte table */
1872 if (offset > (uintptr_t)(end - code))
1873 FAIL;
1874 /* Make sure that each byte points to a valid block */
1875 for (i = 0; i < 256; i++) {
1876 if (((unsigned char *)code)[i] >= arg)
1877 FAIL;
1878 }
1879 code += offset;
1880 offset = arg * (256/SRE_CODE_BITS); /* 256-bit bitmap times arg */
1881 if (offset > (uintptr_t)(end - code))
1882 FAIL;
1883 code += offset;
1884 break;
1885
1886 case SRE_OP_CATEGORY:
1887 GET_ARG;
1888 switch (arg) {
1889 case SRE_CATEGORY_DIGIT:
1890 case SRE_CATEGORY_NOT_DIGIT:
1891 case SRE_CATEGORY_SPACE:
1892 case SRE_CATEGORY_NOT_SPACE:
1893 case SRE_CATEGORY_WORD:
1894 case SRE_CATEGORY_NOT_WORD:
1895 case SRE_CATEGORY_LINEBREAK:
1896 case SRE_CATEGORY_NOT_LINEBREAK:
1897 case SRE_CATEGORY_LOC_WORD:
1898 case SRE_CATEGORY_LOC_NOT_WORD:
1899 case SRE_CATEGORY_UNI_DIGIT:
1900 case SRE_CATEGORY_UNI_NOT_DIGIT:
1901 case SRE_CATEGORY_UNI_SPACE:
1902 case SRE_CATEGORY_UNI_NOT_SPACE:
1903 case SRE_CATEGORY_UNI_WORD:
1904 case SRE_CATEGORY_UNI_NOT_WORD:
1905 case SRE_CATEGORY_UNI_LINEBREAK:
1906 case SRE_CATEGORY_UNI_NOT_LINEBREAK:
1907 break;
1908 default:
1909 FAIL;
1910 }
1911 break;
1912
1913 default:
1914 FAIL;
1915
1916 }
1917 }
1918
1919 return 0;
1920 }
1921
1922 /* Returns 0 on success, -1 on failure, and 1 if the last op is JUMP. */
1923 static int
1924 _validate_inner(SRE_CODE *code, SRE_CODE *end, Py_ssize_t groups)
1925 {
1926 /* Some variables are manipulated by the macros above */
1927 SRE_CODE op;
1928 SRE_CODE arg;
1929 SRE_CODE skip;
1930
1931 VTRACE(("code=%p, end=%p\n", code, end));
1932
1933 if (code > end)
1934 FAIL;
1935
1936 while (code < end) {
1937 GET_OP;
1938 switch (op) {
1939
1940 case SRE_OP_MARK:
1941 /* We don't check whether marks are properly nested; the
1942 sre_match() code is robust even if they don't, and the worst
1943 you can get is nonsensical match results. */
1944 GET_ARG;
1945 if (arg >= 2 * (size_t)groups) {
1946 VTRACE(("arg=%d, groups=%d\n", (int)arg, (int)groups));
1947 FAIL;
1948 }
1949 break;
1950
1951 case SRE_OP_LITERAL:
1952 case SRE_OP_NOT_LITERAL:
1953 case SRE_OP_LITERAL_IGNORE:
1954 case SRE_OP_NOT_LITERAL_IGNORE:
1955 case SRE_OP_LITERAL_UNI_IGNORE:
1956 case SRE_OP_NOT_LITERAL_UNI_IGNORE:
1957 case SRE_OP_LITERAL_LOC_IGNORE:
1958 case SRE_OP_NOT_LITERAL_LOC_IGNORE:
1959 GET_ARG;
1960 /* The arg is just a character, nothing to check */
1961 break;
1962
1963 case SRE_OP_SUCCESS:
1964 case SRE_OP_FAILURE:
1965 /* Nothing to check; these normally end the matching process */
1966 break;
1967
1968 case SRE_OP_AT:
1969 GET_ARG;
1970 switch (arg) {
1971 case SRE_AT_BEGINNING:
1972 case SRE_AT_BEGINNING_STRING:
1973 case SRE_AT_BEGINNING_LINE:
1974 case SRE_AT_END:
1975 case SRE_AT_END_LINE:
1976 case SRE_AT_END_STRING:
1977 case SRE_AT_BOUNDARY:
1978 case SRE_AT_NON_BOUNDARY:
1979 case SRE_AT_LOC_BOUNDARY:
1980 case SRE_AT_LOC_NON_BOUNDARY:
1981 case SRE_AT_UNI_BOUNDARY:
1982 case SRE_AT_UNI_NON_BOUNDARY:
1983 break;
1984 default:
1985 FAIL;
1986 }
1987 break;
1988
1989 case SRE_OP_ANY:
1990 case SRE_OP_ANY_ALL:
1991 /* These have no operands */
1992 break;
1993
1994 case SRE_OP_IN:
1995 case SRE_OP_IN_IGNORE:
1996 case SRE_OP_IN_UNI_IGNORE:
1997 case SRE_OP_IN_LOC_IGNORE:
1998 GET_SKIP;
1999 /* Stop 1 before the end; we check the FAILURE below */
2000 if (_validate_charset(code, code+skip-2))
2001 FAIL;
2002 if (code[skip-2] != SRE_OP_FAILURE)
2003 FAIL;
2004 code += skip-1;
2005 break;
2006
2007 case SRE_OP_INFO:
2008 {
2009 /* A minimal info field is
2010 <INFO> <1=skip> <2=flags> <3=min> <4=max>;
2011 If SRE_INFO_PREFIX or SRE_INFO_CHARSET is in the flags,
2012 more follows. */
2013 SRE_CODE flags, i;
2014 SRE_CODE *newcode;
2015 GET_SKIP;
2016 newcode = code+skip-1;
2017 GET_ARG; flags = arg;
2018 GET_ARG;
2019 GET_ARG;
2020 /* Check that only valid flags are present */
2021 if ((flags & ~(SRE_INFO_PREFIX |
2022 SRE_INFO_LITERAL |
2023 SRE_INFO_CHARSET)) != 0)
2024 FAIL;
2025 /* PREFIX and CHARSET are mutually exclusive */
2026 if ((flags & SRE_INFO_PREFIX) &&
2027 (flags & SRE_INFO_CHARSET))
2028 FAIL;
2029 /* LITERAL implies PREFIX */
2030 if ((flags & SRE_INFO_LITERAL) &&
2031 !(flags & SRE_INFO_PREFIX))
2032 FAIL;
2033 /* Validate the prefix */
2034 if (flags & SRE_INFO_PREFIX) {
2035 SRE_CODE prefix_len;
2036 GET_ARG; prefix_len = arg;
2037 GET_ARG;
2038 /* Here comes the prefix string */
2039 if (prefix_len > (uintptr_t)(newcode - code))
2040 FAIL;
2041 code += prefix_len;
2042 /* And here comes the overlap table */
2043 if (prefix_len > (uintptr_t)(newcode - code))
2044 FAIL;
2045 /* Each overlap value should be < prefix_len */
2046 for (i = 0; i < prefix_len; i++) {
2047 if (code[i] >= prefix_len)
2048 FAIL;
2049 }
2050 code += prefix_len;
2051 }
2052 /* Validate the charset */
2053 if (flags & SRE_INFO_CHARSET) {
2054 if (_validate_charset(code, newcode-1))
2055 FAIL;
2056 if (newcode[-1] != SRE_OP_FAILURE)
2057 FAIL;
2058 code = newcode;
2059 }
2060 else if (code != newcode) {
2061 VTRACE(("code=%p, newcode=%p\n", code, newcode));
2062 FAIL;
2063 }
2064 }
2065 break;
2066
2067 case SRE_OP_BRANCH:
2068 {
2069 SRE_CODE *target = NULL;
2070 for (;;) {
2071 GET_SKIP;
2072 if (skip == 0)
2073 break;
2074 /* Stop 2 before the end; we check the JUMP below */
2075 if (_validate_inner(code, code+skip-3, groups))
2076 FAIL;
2077 code += skip-3;
2078 /* Check that it ends with a JUMP, and that each JUMP
2079 has the same target */
2080 GET_OP;
2081 if (op != SRE_OP_JUMP)
2082 FAIL;
2083 GET_SKIP;
2084 if (target == NULL)
2085 target = code+skip-1;
2086 else if (code+skip-1 != target)
2087 FAIL;
2088 }
2089 if (code != target)
2090 FAIL;
2091 }
2092 break;
2093
2094 case SRE_OP_REPEAT_ONE:
2095 case SRE_OP_MIN_REPEAT_ONE:
2096 case SRE_OP_POSSESSIVE_REPEAT_ONE:
2097 {
2098 SRE_CODE min, max;
2099 GET_SKIP;
2100 GET_ARG; min = arg;
2101 GET_ARG; max = arg;
2102 if (min > max)
2103 FAIL;
2104 if (max > SRE_MAXREPEAT)
2105 FAIL;
2106 if (_validate_inner(code, code+skip-4, groups))
2107 FAIL;
2108 code += skip-4;
2109 GET_OP;
2110 if (op != SRE_OP_SUCCESS)
2111 FAIL;
2112 }
2113 break;
2114
2115 case SRE_OP_REPEAT:
2116 case SRE_OP_POSSESSIVE_REPEAT:
2117 {
2118 SRE_CODE op1 = op, min, max;
2119 GET_SKIP;
2120 GET_ARG; min = arg;
2121 GET_ARG; max = arg;
2122 if (min > max)
2123 FAIL;
2124 if (max > SRE_MAXREPEAT)
2125 FAIL;
2126 if (_validate_inner(code, code+skip-3, groups))
2127 FAIL;
2128 code += skip-3;
2129 GET_OP;
2130 if (op1 == SRE_OP_POSSESSIVE_REPEAT) {
2131 if (op != SRE_OP_SUCCESS)
2132 FAIL;
2133 }
2134 else {
2135 if (op != SRE_OP_MAX_UNTIL && op != SRE_OP_MIN_UNTIL)
2136 FAIL;
2137 }
2138 }
2139 break;
2140
2141 case SRE_OP_ATOMIC_GROUP:
2142 {
2143 GET_SKIP;
2144 if (_validate_inner(code, code+skip-2, groups))
2145 FAIL;
2146 code += skip-2;
2147 GET_OP;
2148 if (op != SRE_OP_SUCCESS)
2149 FAIL;
2150 }
2151 break;
2152
2153 case SRE_OP_GROUPREF:
2154 case SRE_OP_GROUPREF_IGNORE:
2155 case SRE_OP_GROUPREF_UNI_IGNORE:
2156 case SRE_OP_GROUPREF_LOC_IGNORE:
2157 GET_ARG;
2158 if (arg >= (size_t)groups)
2159 FAIL;
2160 break;
2161
2162 case SRE_OP_GROUPREF_EXISTS:
2163 /* The regex syntax for this is: '(?(group)then|else)', where
2164 'group' is either an integer group number or a group name,
2165 'then' and 'else' are sub-regexes, and 'else' is optional. */
2166 GET_ARG;
2167 if (arg >= (size_t)groups)
2168 FAIL;
2169 GET_SKIP_ADJ(1);
2170 code--; /* The skip is relative to the first arg! */
2171 /* There are two possibilities here: if there is both a 'then'
2172 part and an 'else' part, the generated code looks like:
2173
2174 GROUPREF_EXISTS
2175 <group>
2176 <skipyes>
2177 ...then part...
2178 JUMP
2179 <skipno>
2180 (<skipyes> jumps here)
2181 ...else part...
2182 (<skipno> jumps here)
2183
2184 If there is only a 'then' part, it looks like:
2185
2186 GROUPREF_EXISTS
2187 <group>
2188 <skip>
2189 ...then part...
2190 (<skip> jumps here)
2191
2192 There is no direct way to decide which it is, and we don't want
2193 to allow arbitrary jumps anywhere in the code; so we just look
2194 for a JUMP opcode preceding our skip target.
2195 */
2196 VTRACE(("then part:\n"));
2197 int rc = _validate_inner(code+1, code+skip-1, groups);
2198 if (rc == 1) {
2199 VTRACE(("else part:\n"));
2200 code += skip-2; /* Position after JUMP, at <skipno> */
2201 GET_SKIP;
2202 rc = _validate_inner(code, code+skip-1, groups);
2203 }
2204 if (rc)
2205 FAIL;
2206 code += skip-1;
2207 break;
2208
2209 case SRE_OP_ASSERT:
2210 case SRE_OP_ASSERT_NOT:
2211 GET_SKIP;
2212 GET_ARG; /* 0 for lookahead, width for lookbehind */
2213 code--; /* Back up over arg to simplify math below */
2214 /* Stop 1 before the end; we check the SUCCESS below */
2215 if (_validate_inner(code+1, code+skip-2, groups))
2216 FAIL;
2217 code += skip-2;
2218 GET_OP;
2219 if (op != SRE_OP_SUCCESS)
2220 FAIL;
2221 break;
2222
2223 case SRE_OP_JUMP:
2224 if (code + 1 != end)
2225 FAIL;
2226 VTRACE(("JUMP: %d\n", __LINE__));
2227 return 1;
2228
2229 default:
2230 FAIL;
2231
2232 }
2233 }
2234
2235 VTRACE(("okay\n"));
2236 return 0;
2237 }
2238
2239 static int
2240 _validate_outer(SRE_CODE *code, SRE_CODE *end, Py_ssize_t groups)
2241 {
2242 if (groups < 0 || (size_t)groups > SRE_MAXGROUPS ||
2243 code >= end || end[-1] != SRE_OP_SUCCESS)
2244 FAIL;
2245 return _validate_inner(code, end-1, groups);
2246 }
2247
2248 static int
2249 _validate(PatternObject *self)
2250 {
2251 if (_validate_outer(self->code, self->code+self->codesize, self->groups))
2252 {
2253 PyErr_SetString(PyExc_RuntimeError, "invalid SRE code");
2254 return 0;
2255 }
2256 else
2257 VTRACE(("Success!\n"));
2258 return 1;
2259 }
2260
2261 /* -------------------------------------------------------------------- */
2262 /* match methods */
2263
2264 static int
2265 match_traverse(PyObject *op, visitproc visit, void *arg)
2266 {
2267 MatchObject *self = _MatchObject_CAST(op);
2268 Py_VISIT(Py_TYPE(self));
2269 Py_VISIT(self->string);
2270 Py_VISIT(self->regs);
2271 Py_VISIT(self->pattern);
2272 return 0;
2273 }
2274
2275 static int
2276 match_clear(PyObject *op)
2277 {
2278 MatchObject *self = _MatchObject_CAST(op);
2279 Py_CLEAR(self->string);
2280 Py_CLEAR(self->regs);
2281 Py_CLEAR(self->pattern);
2282 return 0;
2283 }
2284
2285 static void
2286 match_dealloc(PyObject *self)
2287 {
2288 PyTypeObject *tp = Py_TYPE(self);
2289 PyObject_GC_UnTrack(self);
2290 (void)match_clear(self);
2291 tp->tp_free(self);
2292 Py_DECREF(tp);
2293 }
2294
2295 static PyObject*
2296 match_getslice_by_index(MatchObject* self, Py_ssize_t index, PyObject* def)
2297 {
2298 Py_ssize_t length;
2299 int isbytes, charsize;
2300 Py_buffer view;
2301 PyObject *result;
2302 const void* ptr;
2303 Py_ssize_t i, j;
2304
2305 assert(0 <= index && index < self->groups);
2306 index *= 2;
2307
2308 if (self->string == Py_None || self->mark[index] < 0) {
2309 /* return default value if the string or group is undefined */
2310 return Py_NewRef(def);
2311 }
2312
2313 ptr = getstring(self->string, &length, &isbytes, &charsize, &view);
2314 if (ptr == NULL)
2315 return NULL;
2316
2317 i = self->mark[index];
2318 j = self->mark[index+1];
2319 i = Py_MIN(i, length);
2320 j = Py_MIN(j, length);
2321 result = getslice(isbytes, ptr, self->string, i, j);
2322 if (isbytes && view.buf != NULL)
2323 PyBuffer_Release(&view);
2324 return result;
2325 }
2326
2327 static Py_ssize_t
2328 match_getindex(MatchObject* self, PyObject* index)
2329 {
2330 Py_ssize_t i;
2331
2332 if (index == NULL)
2333 /* Default value */
2334 return 0;
2335
2336 if (PyIndex_Check(index)) {
2337 i = PyNumber_AsSsize_t(index, NULL);
2338 }
2339 else {
2340 i = -1;
2341
2342 if (self->pattern->groupindex) {
2343 index = PyDict_GetItemWithError(self->pattern->groupindex, index);
2344 if (index && PyLong_Check(index)) {
2345 i = PyLong_AsSsize_t(index);
2346 }
2347 }
2348 }
2349 if (i < 0 || i >= self->groups) {
2350 /* raise IndexError if we were given a bad group number */
2351 if (!PyErr_Occurred()) {
2352 PyErr_SetString(PyExc_IndexError, "no such group");
2353 }
2354 return -1;
2355 }
2356
2357 // Check that i*2 cannot overflow to make static analyzers happy
2358 assert((size_t)i <= SRE_MAXGROUPS);
2359 return i;
2360 }
2361
2362 static PyObject*
2363 match_getslice(MatchObject* self, PyObject* index, PyObject* def)
2364 {
2365 Py_ssize_t i = match_getindex(self, index);
2366
2367 if (i < 0) {
2368 return NULL;
2369 }
2370
2371 return match_getslice_by_index(self, i, def);
2372 }
2373
2374 /*[clinic input]
2375 _sre.SRE_Match.expand
2376
2377 template: object
2378
2379 Return the string obtained by doing backslash substitution on the string template, as done by the sub() method.
2380 [clinic start generated code]*/
2381
2382 static PyObject *
2383 _sre_SRE_Match_expand_impl(MatchObject *self, PyObject *template)
2384 /*[clinic end generated code: output=931b58ccc323c3a1 input=4bfdb22c2f8b146a]*/
2385 {
2386 _sremodulestate *module_state = get_sre_module_state_by_class(Py_TYPE(self));
2387 PyObject *filter = compile_template(module_state, self->pattern, template);
2388 if (filter == NULL) {
2389 return NULL;
2390 }
2391 PyObject *result = expand_template((TemplateObject *)filter, self);
2392 Py_DECREF(filter);
2393 return result;
2394 }
2395
2396 static PyObject*
2397 match_group(PyObject *op, PyObject* args)
2398 {
2399 MatchObject *self = _MatchObject_CAST(op);
2400 PyObject* result;
2401 Py_ssize_t i, size;
2402
2403 size = PyTuple_GET_SIZE(args);
2404
2405 switch (size) {
2406 case 0:
2407 result = match_getslice(self, _PyLong_GetZero(), Py_None);
2408 break;
2409 case 1:
2410 result = match_getslice(self, PyTuple_GET_ITEM(args, 0), Py_None);
2411 break;
2412 default:
2413 /* fetch multiple items */
2414 result = PyTuple_New(size);
2415 if (!result)
2416 return NULL;
2417 for (i = 0; i < size; i++) {
2418 PyObject* item = match_getslice(
2419 self, PyTuple_GET_ITEM(args, i), Py_None
2420 );
2421 if (!item) {
2422 Py_DECREF(result);
2423 return NULL;
2424 }
2425 PyTuple_SET_ITEM(result, i, item);
2426 }
2427 break;
2428 }
2429 return result;
2430 }
2431
2432 static PyObject*
2433 match_getitem(PyObject *op, PyObject* name)
2434 {
2435 MatchObject *self = _MatchObject_CAST(op);
2436 return match_getslice(self, name, Py_None);
2437 }
2438
2439 /*[clinic input]
2440 _sre.SRE_Match.groups
2441
2442 default: object = None
2443 Is used for groups that did not participate in the match.
2444
2445 Return a tuple containing all the subgroups of the match, from 1.
2446 [clinic start generated code]*/
2447
2448 static PyObject *
2449 _sre_SRE_Match_groups_impl(MatchObject *self, PyObject *default_value)
2450 /*[clinic end generated code: output=daf8e2641537238a input=bb069ef55dabca91]*/
2451 {
2452 PyObject* result;
2453 Py_ssize_t index;
2454
2455 result = PyTuple_New(self->groups-1);
2456 if (!result)
2457 return NULL;
2458
2459 for (index = 1; index < self->groups; index++) {
2460 PyObject* item;
2461 item = match_getslice_by_index(self, index, default_value);
2462 if (!item) {
2463 Py_DECREF(result);
2464 return NULL;
2465 }
2466 PyTuple_SET_ITEM(result, index-1, item);
2467 }
2468
2469 return result;
2470 }
2471
2472 /*[clinic input]
2473 _sre.SRE_Match.groupdict
2474
2475 default: object = None
2476 Is used for groups that did not participate in the match.
2477
2478 Return a dictionary containing all the named subgroups of the match, keyed by the subgroup name.
2479 [clinic start generated code]*/
2480
2481 static PyObject *
2482 _sre_SRE_Match_groupdict_impl(MatchObject *self, PyObject *default_value)
2483 /*[clinic end generated code: output=29917c9073e41757 input=0ded7960b23780aa]*/
2484 {
2485 PyObject *result;
2486 PyObject *key;
2487 PyObject *value;
2488 Py_ssize_t pos = 0;
2489 Py_hash_t hash;
2490
2491 result = PyDict_New();
2492 if (!result || !self->pattern->groupindex)
2493 return result;
2494
2495 Py_BEGIN_CRITICAL_SECTION(self->pattern->groupindex);
2496 while (_PyDict_Next(self->pattern->groupindex, &pos, &key, &value, &hash)) {
2497 int status;
2498 Py_INCREF(key);
2499 value = match_getslice(self, key, default_value);
2500 if (!value) {
2501 Py_DECREF(key);
2502 Py_CLEAR(result);
2503 goto exit;
2504 }
2505 status = _PyDict_SetItem_KnownHash(result, key, value, hash);
2506 Py_DECREF(value);
2507 Py_DECREF(key);
2508 if (status < 0) {
2509 Py_CLEAR(result);
2510 goto exit;
2511 }
2512 }
2513 exit:;
2514 Py_END_CRITICAL_SECTION();
2515
2516 return result;
2517 }
2518
2519 /*[clinic input]
2520 _sre.SRE_Match.start -> Py_ssize_t
2521
2522 group: object(c_default="NULL") = 0
2523 /
2524
2525 Return index of the start of the substring matched by group.
2526 [clinic start generated code]*/
2527
2528 static Py_ssize_t
2529 _sre_SRE_Match_start_impl(MatchObject *self, PyObject *group)
2530 /*[clinic end generated code: output=3f6e7f9df2fb5201 input=ced8e4ed4b33ee6c]*/
2531 {
2532 Py_ssize_t index = match_getindex(self, group);
2533
2534 if (index < 0) {
2535 return -1;
2536 }
2537
2538 /* mark is -1 if group is undefined */
2539 return self->mark[index*2];
2540 }
2541
2542 /*[clinic input]
2543 _sre.SRE_Match.end -> Py_ssize_t
2544
2545 group: object(c_default="NULL") = 0
2546 /
2547
2548 Return index of the end of the substring matched by group.
2549 [clinic start generated code]*/
2550
2551 static Py_ssize_t
2552 _sre_SRE_Match_end_impl(MatchObject *self, PyObject *group)
2553 /*[clinic end generated code: output=f4240b09911f7692 input=1b799560c7f3d7e6]*/
2554 {
2555 Py_ssize_t index = match_getindex(self, group);
2556
2557 if (index < 0) {
2558 return -1;
2559 }
2560
2561 /* mark is -1 if group is undefined */
2562 return self->mark[index*2+1];
2563 }
2564
2565 LOCAL(PyObject*)
2566 _pair(Py_ssize_t i1, Py_ssize_t i2)
2567 {
2568 PyObject* pair;
2569 PyObject* item;
2570
2571 pair = PyTuple_New(2);
2572 if (!pair)
2573 return NULL;
2574
2575 item = PyLong_FromSsize_t(i1);
2576 if (!item)
2577 goto error;
2578 PyTuple_SET_ITEM(pair, 0, item);
2579
2580 item = PyLong_FromSsize_t(i2);
2581 if (!item)
2582 goto error;
2583 PyTuple_SET_ITEM(pair, 1, item);
2584
2585 return pair;
2586
2587 error:
2588 Py_DECREF(pair);
2589 return NULL;
2590 }
2591
2592 /*[clinic input]
2593 _sre.SRE_Match.span
2594
2595 group: object(c_default="NULL") = 0
2596 /
2597
2598 For match object m, return the 2-tuple (m.start(group), m.end(group)).
2599 [clinic start generated code]*/
2600
2601 static PyObject *
2602 _sre_SRE_Match_span_impl(MatchObject *self, PyObject *group)
2603 /*[clinic end generated code: output=f02ae40594d14fe6 input=8fa6014e982d71d4]*/
2604 {
2605 Py_ssize_t index = match_getindex(self, group);
2606
2607 if (index < 0) {
2608 return NULL;
2609 }
2610
2611 /* marks are -1 if group is undefined */
2612 return _pair(self->mark[index*2], self->mark[index*2+1]);
2613 }
2614
2615 static PyObject*
2616 match_regs(MatchObject* self)
2617 {
2618 PyObject* regs;
2619 PyObject* item;
2620 Py_ssize_t index;
2621
2622 regs = PyTuple_New(self->groups);
2623 if (!regs)
2624 return NULL;
2625
2626 for (index = 0; index < self->groups; index++) {
2627 item = _pair(self->mark[index*2], self->mark[index*2+1]);
2628 if (!item) {
2629 Py_DECREF(regs);
2630 return NULL;
2631 }
2632 PyTuple_SET_ITEM(regs, index, item);
2633 }
2634
2635 self->regs = Py_NewRef(regs);
2636
2637 return regs;
2638 }
2639
2640 /*[clinic input]
2641 _sre.SRE_Match.__copy__
2642
2643 [clinic start generated code]*/
2644
2645 static PyObject *
2646 _sre_SRE_Match___copy___impl(MatchObject *self)
2647 /*[clinic end generated code: output=a779c5fc8b5b4eb4 input=3bb4d30b6baddb5b]*/
2648 {
2649 return Py_NewRef(self);
2650 }
2651
2652 /*[clinic input]
2653 _sre.SRE_Match.__deepcopy__
2654
2655 memo: object
2656 /
2657
2658 [clinic start generated code]*/
2659
2660 static PyObject *
2661 _sre_SRE_Match___deepcopy___impl(MatchObject *self, PyObject *memo)
2662 /*[clinic end generated code: output=2b657578eb03f4a3 input=779d12a31c2c325e]*/
2663 {
2664 return Py_NewRef(self);
2665 }
2666
2667 PyDoc_STRVAR(match_doc,
2668 "The result of re.match() and re.search().\n\
2669 Match objects always have a boolean value of True.");
2670
2671 PyDoc_STRVAR(match_group_doc,
2672 "group([group1, ...]) -> str or tuple.\n\
2673 Return subgroup(s) of the match by indices or names.\n\
2674 For 0 returns the entire match.");
2675
2676 static PyObject *
2677 match_lastindex_get(PyObject *op, void *Py_UNUSED(ignored))
2678 {
2679 MatchObject *self = _MatchObject_CAST(op);
2680 if (self->lastindex >= 0)
2681 return PyLong_FromSsize_t(self->lastindex);
2682 Py_RETURN_NONE;
2683 }
2684
2685 static PyObject *
2686 match_lastgroup_get(PyObject *op, void *Py_UNUSED(ignored))
2687 {
2688 MatchObject *self = _MatchObject_CAST(op);
2689 if (self->pattern->indexgroup &&
2690 self->lastindex >= 0 &&
2691 self->lastindex < PyTuple_GET_SIZE(self->pattern->indexgroup))
2692 {
2693 PyObject *result = PyTuple_GET_ITEM(self->pattern->indexgroup,
2694 self->lastindex);
2695 return Py_NewRef(result);
2696 }
2697 Py_RETURN_NONE;
2698 }
2699
2700 static PyObject *
2701 match_regs_get(PyObject *op, void *Py_UNUSED(ignored))
2702 {
2703 MatchObject *self = _MatchObject_CAST(op);
2704 if (self->regs) {
2705 return Py_NewRef(self->regs);
2706 } else
2707 return match_regs(self);
2708 }
2709
2710 static PyObject *
2711 match_repr(PyObject *op)
2712 {
2713 MatchObject *self = _MatchObject_CAST(op);
2714 PyObject *result;
2715 PyObject *group0 = match_getslice_by_index(self, 0, Py_None);
2716 if (group0 == NULL)
2717 return NULL;
2718 result = PyUnicode_FromFormat(
2719 "<%s object; span=(%zd, %zd), match=%.50R>",
2720 Py_TYPE(self)->tp_name,
2721 self->mark[0], self->mark[1], group0);
2722 Py_DECREF(group0);
2723 return result;
2724 }
2725
2726
2727 static PyObject*
2728 pattern_new_match(_sremodulestate* module_state,
2729 PatternObject* pattern,
2730 SRE_STATE* state,
2731 Py_ssize_t status)
2732 {
2733 /* create match object (from state object) */
2734
2735 MatchObject* match;
2736 Py_ssize_t i, j;
2737 char* base;
2738 int n;
2739
2740 if (status > 0) {
2741
2742 /* create match object (with room for extra group marks) */
2743 /* coverity[ampersand_in_size] */
2744 match = PyObject_GC_NewVar(MatchObject,
2745 module_state->Match_Type,
2746 2*(pattern->groups+1));
2747 if (!match)
2748 return NULL;
2749
2750 Py_INCREF(pattern);
2751 match->pattern = pattern;
2752
2753 match->string = Py_NewRef(state->string);
2754
2755 match->regs = NULL;
2756 match->groups = pattern->groups+1;
2757
2758 /* fill in group slices */
2759
2760 base = (char*) state->beginning;
2761 n = state->charsize;
2762
2763 match->mark[0] = ((char*) state->start - base) / n;
2764 match->mark[1] = ((char*) state->ptr - base) / n;
2765
2766 for (i = j = 0; i < pattern->groups; i++, j+=2)
2767 if (j+1 <= state->lastmark && state->mark[j] && state->mark[j+1]) {
2768 match->mark[j+2] = ((char*) state->mark[j] - base) / n;
2769 match->mark[j+3] = ((char*) state->mark[j+1] - base) / n;
2770
2771 /* check wrong span */
2772 if (match->mark[j+2] > match->mark[j+3]) {
2773 PyErr_SetString(PyExc_SystemError,
2774 "The span of capturing group is wrong,"
2775 " please report a bug for the re module.");
2776 Py_DECREF(match);
2777 return NULL;
2778 }
2779 } else
2780 match->mark[j+2] = match->mark[j+3] = -1; /* undefined */
2781
2782 match->pos = state->pos;
2783 match->endpos = state->endpos;
2784
2785 match->lastindex = state->lastindex;
2786
2787 PyObject_GC_Track(match);
2788 return (PyObject*) match;
2789
2790 } else if (status == 0) {
2791
2792 /* no match */
2793 Py_RETURN_NONE;
2794
2795 }
2796
2797 /* internal error */
2798 pattern_error(status);
2799 return NULL;
2800 }
2801
2802
2803 /* -------------------------------------------------------------------- */
2804 /* scanner methods (experimental) */
2805
2806 static int
2807 scanner_traverse(PyObject *op, visitproc visit, void *arg)
2808 {
2809 ScannerObject *self = _ScannerObject_CAST(op);
2810 Py_VISIT(Py_TYPE(self));
2811 Py_VISIT(self->pattern);
2812 return 0;
2813 }
2814
2815 static int
2816 scanner_clear(PyObject *op)
2817 {
2818 ScannerObject *self = _ScannerObject_CAST(op);
2819 Py_CLEAR(self->pattern);
2820 return 0;
2821 }
2822
2823 static void
2824 scanner_dealloc(PyObject *self)
2825 {
2826 PyTypeObject *tp = Py_TYPE(self);
2827 PyObject_GC_UnTrack(self);
2828 ScannerObject *scanner = _ScannerObject_CAST(self);
2829 state_fini(&scanner->state);
2830 (void)scanner_clear(self);
2831 tp->tp_free(self);
2832 Py_DECREF(tp);
2833 }
2834
2835 static int
2836 scanner_begin(ScannerObject* self)
2837 {
2838 #ifdef Py_GIL_DISABLED
2839 int was_executing = _Py_atomic_exchange_int(&self->executing, 1);
2840 #else
2841 int was_executing = self->executing;
2842 self->executing = 1;
2843 #endif
2844 if (was_executing) {
2845 PyErr_SetString(PyExc_ValueError,
2846 "regular expression scanner already executing");
2847 return 0;
2848 }
2849 return 1;
2850 }
2851
2852 static void
2853 scanner_end(ScannerObject* self)
2854 {
2855 assert(FT_ATOMIC_LOAD_INT_RELAXED(self->executing));
2856 FT_ATOMIC_STORE_INT(self->executing, 0);
2857 }
2858
2859 /*[clinic input]
2860 _sre.SRE_Scanner.match
2861
2862 cls: defining_class
2863 /
2864
2865 [clinic start generated code]*/
2866
2867 static PyObject *
2868 _sre_SRE_Scanner_match_impl(ScannerObject *self, PyTypeObject *cls)
2869 /*[clinic end generated code: output=6e22c149dc0f0325 input=b5146e1f30278cb7]*/
2870 {
2871 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
2872 SRE_STATE* state = &self->state;
2873 PyObject* match;
2874 Py_ssize_t status;
2875
2876 if (!scanner_begin(self)) {
2877 return NULL;
2878 }
2879 if (state->start == NULL) {
2880 scanner_end(self);
2881 Py_RETURN_NONE;
2882 }
2883
2884 state_reset(state);
2885
2886 state->ptr = state->start;
2887
2888 status = sre_match(state, PatternObject_GetCode(self->pattern));
2889 if (PyErr_Occurred()) {
2890 scanner_end(self);
2891 return NULL;
2892 }
2893
2894 match = pattern_new_match(module_state, self->pattern,
2895 state, status);
2896
2897 if (status == 0)
2898 state->start = NULL;
2899 else {
2900 state->must_advance = (state->ptr == state->start);
2901 state->start = state->ptr;
2902 }
2903
2904 scanner_end(self);
2905 return match;
2906 }
2907
2908
2909 /*[clinic input]
2910 _sre.SRE_Scanner.search
2911
2912 cls: defining_class
2913 /
2914
2915 [clinic start generated code]*/
2916
2917 static PyObject *
2918 _sre_SRE_Scanner_search_impl(ScannerObject *self, PyTypeObject *cls)
2919 /*[clinic end generated code: output=23e8fc78013f9161 input=056c2d37171d0bf2]*/
2920 {
2921 _sremodulestate *module_state = get_sre_module_state_by_class(cls);
2922 SRE_STATE* state = &self->state;
2923 PyObject* match;
2924 Py_ssize_t status;
2925
2926 if (!scanner_begin(self)) {
2927 return NULL;
2928 }
2929 if (state->start == NULL) {
2930 scanner_end(self);
2931 Py_RETURN_NONE;
2932 }
2933
2934 state_reset(state);
2935
2936 state->ptr = state->start;
2937
2938 status = sre_search(state, PatternObject_GetCode(self->pattern));
2939 if (PyErr_Occurred()) {
2940 scanner_end(self);
2941 return NULL;
2942 }
2943
2944 match = pattern_new_match(module_state, self->pattern,
2945 state, status);
2946
2947 if (status == 0)
2948 state->start = NULL;
2949 else {
2950 state->must_advance = (state->ptr == state->start);
2951 state->start = state->ptr;
2952 }
2953
2954 scanner_end(self);
2955 return match;
2956 }
2957
2958 static PyObject *
2959 pattern_scanner(_sremodulestate *module_state,
2960 PatternObject *self,
2961 PyObject *string,
2962 Py_ssize_t pos,
2963 Py_ssize_t endpos)
2964 {
2965 ScannerObject* scanner;
2966
2967 /* create scanner object */
2968 scanner = PyObject_GC_New(ScannerObject, module_state->Scanner_Type);
2969 if (!scanner)
2970 return NULL;
2971 scanner->pattern = NULL;
2972 scanner->executing = 0;
2973
2974 /* create search state object */
2975 if (!state_init(&scanner->state, self, string, pos, endpos)) {
2976 Py_DECREF(scanner);
2977 return NULL;
2978 }
2979
2980 Py_INCREF(self);
2981 scanner->pattern = self;
2982
2983 PyObject_GC_Track(scanner);
2984 return (PyObject*) scanner;
2985 }
2986
2987 /* -------------------------------------------------------------------- */
2988 /* template methods */
2989
2990 static int
2991 template_traverse(PyObject *op, visitproc visit, void *arg)
2992 {
2993 TemplateObject *self = _TemplateObject_CAST(op);
2994 Py_VISIT(Py_TYPE(self));
2995 Py_VISIT(self->literal);
2996 for (Py_ssize_t i = 0, n = Py_SIZE(self); i < n; i++) {
2997 Py_VISIT(self->items[i].literal);
2998 }
2999 return 0;
3000 }
3001
3002 static int
3003 template_clear(PyObject *op)
3004 {
3005 TemplateObject *self = _TemplateObject_CAST(op);
3006 Py_CLEAR(self->literal);
3007 for (Py_ssize_t i = 0, n = Py_SIZE(self); i < n; i++) {
3008 Py_CLEAR(self->items[i].literal);
3009 }
3010 return 0;
3011 }
3012
3013 static void
3014 template_dealloc(PyObject *self)
3015 {
3016 PyTypeObject *tp = Py_TYPE(self);
3017 PyObject_GC_UnTrack(self);
3018 (void)template_clear(self);
3019 tp->tp_free(self);
3020 Py_DECREF(tp);
3021 }
3022
3023 static PyObject *
3024 expand_template(TemplateObject *self, MatchObject *match)
3025 {
3026 if (Py_SIZE(self) == 0) {
3027 return Py_NewRef(self->literal);
3028 }
3029
3030 PyObject *result = NULL;
3031 Py_ssize_t count = 0; // the number of non-empty chunks
3032 /* For small number of strings use a buffer allocated on the stack,
3033 * otherwise use a list object. */
3034 PyObject *buffer[10];
3035 PyObject **out = buffer;
3036 PyObject *list = NULL;
3037 if (self->chunks > (int)Py_ARRAY_LENGTH(buffer) ||
3038 !PyUnicode_Check(self->literal))
3039 {
3040 list = PyList_New(self->chunks);
3041 if (!list) {
3042 return NULL;
3043 }
3044 out = &PyList_GET_ITEM(list, 0);
3045 }
3046
3047 out[count++] = Py_NewRef(self->literal);
3048 for (Py_ssize_t i = 0; i < Py_SIZE(self); i++) {
3049 Py_ssize_t index = self->items[i].index;
3050 if (index >= match->groups) {
3051 PyErr_SetString(PyExc_IndexError, "no such group");
3052 goto cleanup;
3053 }
3054 PyObject *item = match_getslice_by_index(match, index, Py_None);
3055 if (item == NULL) {
3056 goto cleanup;
3057 }
3058 if (item != Py_None) {
3059 out[count++] = Py_NewRef(item);
3060 }
3061 Py_DECREF(item);
3062
3063 PyObject *literal = self->items[i].literal;
3064 if (literal != NULL) {
3065 out[count++] = Py_NewRef(literal);
3066 }
3067 }
3068
3069 if (PyUnicode_Check(self->literal)) {
3070 result = _PyUnicode_JoinArray(&_Py_STR(empty), out, count);
3071 }
3072 else {
3073 Py_SET_SIZE(list, count);
3074 result = PyBytes_Join((PyObject *)&_Py_SINGLETON(bytes_empty), list);
3075 }
3076
3077 cleanup:
3078 if (list) {
3079 Py_DECREF(list);
3080 }
3081 else {
3082 for (Py_ssize_t i = 0; i < count; i++) {
3083 Py_DECREF(out[i]);
3084 }
3085 }
3086 return result;
3087 }
3088
3089
3090 static Py_hash_t
3091 pattern_hash(PyObject *op)
3092 {
3093 PatternObject *self = _PatternObject_CAST(op);
3094
3095 Py_hash_t hash, hash2;
3096
3097 hash = PyObject_Hash(self->pattern);
3098 if (hash == -1) {
3099 return -1;
3100 }
3101
3102 hash2 = Py_HashBuffer(self->code, sizeof(self->code[0]) * self->codesize);
3103 hash ^= hash2;
3104
3105 hash ^= self->flags;
3106 hash ^= self->isbytes;
3107 hash ^= self->codesize;
3108
3109 if (hash == -1) {
3110 hash = -2;
3111 }
3112 return hash;
3113 }
3114
3115 static PyObject*
3116 pattern_richcompare(PyObject *lefto, PyObject *righto, int op)
3117 {
3118 PyTypeObject *tp = Py_TYPE(lefto);
3119 _sremodulestate *module_state = get_sre_module_state_by_class(tp);
3120 PatternObject *left, *right;
3121 int cmp;
3122
3123 if (op != Py_EQ && op != Py_NE) {
3124 Py_RETURN_NOTIMPLEMENTED;
3125 }
3126
3127 if (!Py_IS_TYPE(righto, module_state->Pattern_Type))
3128 {
3129 Py_RETURN_NOTIMPLEMENTED;
3130 }
3131
3132 if (lefto == righto) {
3133 /* a pattern is equal to itself */
3134 return PyBool_FromLong(op == Py_EQ);
3135 }
3136
3137 left = (PatternObject *)lefto;
3138 right = (PatternObject *)righto;
3139
3140 cmp = (left->flags == right->flags
3141 && left->isbytes == right->isbytes
3142 && left->codesize == right->codesize);
3143 if (cmp) {
3144 /* Compare the code and the pattern because the same pattern can
3145 produce different codes depending on the locale used to compile the
3146 pattern when the re.LOCALE flag is used. Don't compare groups,
3147 indexgroup nor groupindex: they are derivated from the pattern. */
3148 cmp = (memcmp(left->code, right->code,
3149 sizeof(left->code[0]) * left->codesize) == 0);
3150 }
3151 if (cmp) {
3152 cmp = PyObject_RichCompareBool(left->pattern, right->pattern,
3153 Py_EQ);
3154 if (cmp < 0) {
3155 return NULL;
3156 }
3157 }
3158 if (op == Py_NE) {
3159 cmp = !cmp;
3160 }
3161 return PyBool_FromLong(cmp);
3162 }
3163
3164 #include "clinic/sre.c.h"
3165
3166 static PyMethodDef pattern_methods[] = {
3167 _SRE_SRE_PATTERN_MATCH_METHODDEF
3168 _SRE_SRE_PATTERN_FULLMATCH_METHODDEF
3169 _SRE_SRE_PATTERN_SEARCH_METHODDEF
3170 _SRE_SRE_PATTERN_SUB_METHODDEF
3171 _SRE_SRE_PATTERN_SUBN_METHODDEF
3172 _SRE_SRE_PATTERN_FINDALL_METHODDEF
3173 _SRE_SRE_PATTERN_SPLIT_METHODDEF
3174 _SRE_SRE_PATTERN_FINDITER_METHODDEF
3175 _SRE_SRE_PATTERN_SCANNER_METHODDEF
3176 _SRE_SRE_PATTERN___COPY___METHODDEF
3177 _SRE_SRE_PATTERN___DEEPCOPY___METHODDEF
3178 _SRE_SRE_PATTERN__FAIL_AFTER_METHODDEF
3179 {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS,
3180 PyDoc_STR("See PEP 585")},
3181 {NULL, NULL}
3182 };
3183
3184 static PyGetSetDef pattern_getset[] = {
3185 {"groupindex", pattern_groupindex, NULL,
3186 "A dictionary mapping group names to group numbers."},
3187 {NULL} /* Sentinel */
3188 };
3189
3190 #define PAT_OFF(x) offsetof(PatternObject, x)
3191 static PyMemberDef pattern_members[] = {
3192 {"pattern", _Py_T_OBJECT, PAT_OFF(pattern), Py_READONLY,
3193 "The pattern string from which the RE object was compiled."},
3194 {"flags", Py_T_INT, PAT_OFF(flags), Py_READONLY,
3195 "The regex matching flags."},
3196 {"groups", Py_T_PYSSIZET, PAT_OFF(groups), Py_READONLY,
3197 "The number of capturing groups in the pattern."},
3198 {"__weaklistoffset__", Py_T_PYSSIZET, offsetof(PatternObject, weakreflist), Py_READONLY},
3199 {NULL} /* Sentinel */
3200 };
3201
3202 static PyType_Slot pattern_slots[] = {
3203 {Py_tp_dealloc, pattern_dealloc},
3204 {Py_tp_repr, pattern_repr},
3205 {Py_tp_hash, pattern_hash},
3206 {Py_tp_doc, (void *)pattern_doc},
3207 {Py_tp_richcompare, pattern_richcompare},
3208 {Py_tp_methods, pattern_methods},
3209 {Py_tp_members, pattern_members},
3210 {Py_tp_getset, pattern_getset},
3211 {Py_tp_traverse, pattern_traverse},
3212 {Py_tp_clear, pattern_clear},
3213 {0, NULL},
3214 };
3215
3216 static PyType_Spec pattern_spec = {
3217 .name = "re.Pattern",
3218 .basicsize = sizeof(PatternObject),
3219 .itemsize = sizeof(SRE_CODE),
3220 .flags = (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_IMMUTABLETYPE |
3221 Py_TPFLAGS_DISALLOW_INSTANTIATION | Py_TPFLAGS_HAVE_GC),
3222 .slots = pattern_slots,
3223 };
3224
3225 static PyMethodDef match_methods[] = {
3226 {"group", match_group, METH_VARARGS, match_group_doc},
3227 _SRE_SRE_MATCH_START_METHODDEF
3228 _SRE_SRE_MATCH_END_METHODDEF
3229 _SRE_SRE_MATCH_SPAN_METHODDEF
3230 _SRE_SRE_MATCH_GROUPS_METHODDEF
3231 _SRE_SRE_MATCH_GROUPDICT_METHODDEF
3232 _SRE_SRE_MATCH_EXPAND_METHODDEF
3233 _SRE_SRE_MATCH___COPY___METHODDEF
3234 _SRE_SRE_MATCH___DEEPCOPY___METHODDEF
3235 {"__class_getitem__", Py_GenericAlias, METH_O|METH_CLASS,
3236 PyDoc_STR("See PEP 585")},
3237 {NULL, NULL}
3238 };
3239
3240 static PyGetSetDef match_getset[] = {
3241 {"lastindex", match_lastindex_get, NULL,
3242 "The integer index of the last matched capturing group."},
3243 {"lastgroup", match_lastgroup_get, NULL,
3244 "The name of the last matched capturing group."},
3245 {"regs", match_regs_get, NULL, NULL},
3246 {NULL}
3247 };
3248
3249 #define MATCH_OFF(x) offsetof(MatchObject, x)
3250 static PyMemberDef match_members[] = {
3251 {"string", _Py_T_OBJECT, MATCH_OFF(string), Py_READONLY,
3252 "The string passed to match() or search()."},
3253 {"re", _Py_T_OBJECT, MATCH_OFF(pattern), Py_READONLY,
3254 "The regular expression object."},
3255 {"pos", Py_T_PYSSIZET, MATCH_OFF(pos), Py_READONLY,
3256 "The index into the string at which the RE engine started looking for a match."},
3257 {"endpos", Py_T_PYSSIZET, MATCH_OFF(endpos), Py_READONLY,
3258 "The index into the string beyond which the RE engine will not go."},
3259 {NULL}
3260 };
3261
3262 /* FIXME: implement setattr("string", None) as a special case (to
3263 detach the associated string, if any */
3264 static PyType_Slot match_slots[] = {
3265 {Py_tp_dealloc, match_dealloc},
3266 {Py_tp_repr, match_repr},
3267 {Py_tp_doc, (void *)match_doc},
3268 {Py_tp_methods, match_methods},
3269 {Py_tp_members, match_members},
3270 {Py_tp_getset, match_getset},
3271 {Py_tp_traverse, match_traverse},
3272 {Py_tp_clear, match_clear},
3273
3274 /* As mapping.
3275 *
3276 * Match objects do not support length or assignment, but do support
3277 * __getitem__.
3278 */
3279 {Py_mp_subscript, match_getitem},
3280
3281 {0, NULL},
3282 };
3283
3284 static PyType_Spec match_spec = {
3285 .name = "re.Match",
3286 .basicsize = sizeof(MatchObject),
3287 .itemsize = sizeof(Py_ssize_t),
3288 .flags = (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_IMMUTABLETYPE |
3289 Py_TPFLAGS_DISALLOW_INSTANTIATION | Py_TPFLAGS_HAVE_GC),
3290 .slots = match_slots,
3291 };
3292
3293 static PyMethodDef scanner_methods[] = {
3294 _SRE_SRE_SCANNER_MATCH_METHODDEF
3295 _SRE_SRE_SCANNER_SEARCH_METHODDEF
3296 {NULL, NULL}
3297 };
3298
3299 #define SCAN_OFF(x) offsetof(ScannerObject, x)
3300 static PyMemberDef scanner_members[] = {
3301 {"pattern", _Py_T_OBJECT, SCAN_OFF(pattern), Py_READONLY},
3302 {NULL} /* Sentinel */
3303 };
3304
3305 static PyType_Slot scanner_slots[] = {
3306 {Py_tp_dealloc, scanner_dealloc},
3307 {Py_tp_methods, scanner_methods},
3308 {Py_tp_members, scanner_members},
3309 {Py_tp_traverse, scanner_traverse},
3310 {Py_tp_clear, scanner_clear},
3311 {0, NULL},
3312 };
3313
3314 static PyType_Spec scanner_spec = {
3315 .name = "_sre.SRE_Scanner",
3316 .basicsize = sizeof(ScannerObject),
3317 .flags = (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_IMMUTABLETYPE |
3318 Py_TPFLAGS_DISALLOW_INSTANTIATION | Py_TPFLAGS_HAVE_GC),
3319 .slots = scanner_slots,
3320 };
3321
3322 static PyType_Slot template_slots[] = {
3323 {Py_tp_dealloc, template_dealloc},
3324 {Py_tp_traverse, template_traverse},
3325 {Py_tp_clear, template_clear},
3326 {0, NULL},
3327 };
3328
3329 static PyType_Spec template_spec = {
3330 .name = "_sre.SRE_Template",
3331 .basicsize = sizeof(TemplateObject),
3332 .itemsize = sizeof(((TemplateObject *)0)->items[0]),
3333 .flags = (Py_TPFLAGS_DEFAULT | Py_TPFLAGS_IMMUTABLETYPE |
3334 Py_TPFLAGS_DISALLOW_INSTANTIATION | Py_TPFLAGS_HAVE_GC),
3335 .slots = template_slots,
3336 };
3337
3338 static PyMethodDef _functions[] = {
3339 _SRE_COMPILE_METHODDEF
3340 _SRE_TEMPLATE_METHODDEF
3341 _SRE_GETCODESIZE_METHODDEF
3342 _SRE_ASCII_ISCASED_METHODDEF
3343 _SRE_UNICODE_ISCASED_METHODDEF
3344 _SRE_ASCII_TOLOWER_METHODDEF
3345 _SRE_UNICODE_TOLOWER_METHODDEF
3346 {NULL, NULL}
3347 };
3348
3349 static int
3350 sre_traverse(PyObject *module, visitproc visit, void *arg)
3351 {
3352 _sremodulestate *state = get_sre_module_state(module);
3353
3354 Py_VISIT(state->Pattern_Type);
3355 Py_VISIT(state->Match_Type);
3356 Py_VISIT(state->Scanner_Type);
3357 Py_VISIT(state->Template_Type);
3358 Py_VISIT(state->compile_template);
3359
3360 return 0;
3361 }
3362
3363 static int
3364 sre_clear(PyObject *module)
3365 {
3366 _sremodulestate *state = get_sre_module_state(module);
3367
3368 Py_CLEAR(state->Pattern_Type);
3369 Py_CLEAR(state->Match_Type);
3370 Py_CLEAR(state->Scanner_Type);
3371 Py_CLEAR(state->Template_Type);
3372 Py_CLEAR(state->compile_template);
3373
3374 return 0;
3375 }
3376
3377 static void
3378 sre_free(void *module)
3379 {
3380 sre_clear((PyObject *)module);
3381 }
3382
3383 #define CREATE_TYPE(m, type, spec) \
3384 do { \
3385 type = (PyTypeObject *)PyType_FromModuleAndSpec(m, spec, NULL); \
3386 if (type == NULL) { \
3387 goto error; \
3388 } \
3389 } while (0)
3390
3391 #define ADD_ULONG_CONSTANT(module, name, value) \
3392 do { \
3393 if (PyModule_Add(module, name, PyLong_FromUnsignedLong(value)) < 0) { \
3394 goto error; \
3395 } \
3396 } while (0)
3397
3398 static int
3399 sre_exec(PyObject *m)
3400 {
3401 _sremodulestate *state;
3402
3403 /* Create heap types */
3404 state = get_sre_module_state(m);
3405 CREATE_TYPE(m, state->Pattern_Type, &pattern_spec);
3406 CREATE_TYPE(m, state->Match_Type, &match_spec);
3407 CREATE_TYPE(m, state->Scanner_Type, &scanner_spec);
3408 CREATE_TYPE(m, state->Template_Type, &template_spec);
3409
3410 if (PyModule_AddIntConstant(m, "MAGIC", SRE_MAGIC) < 0) {
3411 goto error;
3412 }
3413
3414 if (PyModule_AddIntConstant(m, "CODESIZE", sizeof(SRE_CODE)) < 0) {
3415 goto error;
3416 }
3417
3418 ADD_ULONG_CONSTANT(m, "MAXREPEAT", SRE_MAXREPEAT);
3419 ADD_ULONG_CONSTANT(m, "MAXGROUPS", SRE_MAXGROUPS);
3420
3421 if (PyModule_AddStringConstant(m, "copyright", copyright) < 0) {
3422 goto error;
3423 }
3424
3425 return 0;
3426
3427 error:
3428 return -1;
3429 }
3430
3431 static PyModuleDef_Slot sre_slots[] = {
3432 {Py_mod_exec, sre_exec},
3433 {Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED},
3434 {Py_mod_gil, Py_MOD_GIL_NOT_USED},
3435 {0, NULL},
3436 };
3437
3438 static struct PyModuleDef sremodule = {
3439 .m_base = PyModuleDef_HEAD_INIT,
3440 .m_name = "_sre",
3441 .m_size = sizeof(_sremodulestate),
3442 .m_methods = _functions,
3443 .m_slots = sre_slots,
3444 .m_traverse = sre_traverse,
3445 .m_free = sre_free,
3446 .m_clear = sre_clear,
3447 };
3448
3449 PyMODINIT_FUNC
3450 PyInit__sre(void)
3451 {
3452 return PyModuleDef_Init(&sremodule);
3453 }
3454
3455 /* vim:ts=4:sw=4:et
3456 */