Branch data Line data Source code
1 : : /*
2 : : * Secret Labs' Regular Expression Engine
3 : : *
4 : : * regular expression matching engine
5 : : *
6 : : * Copyright (c) 1997-2001 by Secret Labs AB. All rights reserved.
7 : : *
8 : : * See the sre.c file for information on usage and redistribution.
9 : : */
10 : :
11 : : /* String matching engine */
12 : :
13 : : /* This file is included three times, with different character settings */
14 : :
15 : : LOCAL(int)
16 : 78314136 : SRE(at)(SRE_STATE* state, const SRE_CHAR* ptr, SRE_CODE at)
17 : : {
18 : : /* check if pointer is at given position */
19 : :
20 : : Py_ssize_t thisp, thatp;
21 : :
22 [ + + + + : 78314136 : switch (at) {
+ + + + +
+ + - ]
23 : :
24 : 257508 : case SRE_AT_BEGINNING:
25 : : case SRE_AT_BEGINNING_STRING:
26 : 257508 : return ((void*) ptr == state->beginning);
27 : :
28 : 3974686 : case SRE_AT_BEGINNING_LINE:
29 [ + + ]: 7918805 : return ((void*) ptr == state->beginning ||
30 [ + + ]: 3944119 : SRE_IS_LINEBREAK((int) ptr[-1]));
31 : :
32 : 5532070 : case SRE_AT_END:
33 : 5539336 : return (((SRE_CHAR *)state->end - ptr == 1 &&
34 [ + + + + ]: 11063978 : SRE_IS_LINEBREAK((int) ptr[0])) ||
35 [ + + ]: 5531908 : ((void*) ptr == state->end));
36 : :
37 : 397572 : case SRE_AT_END_LINE:
38 [ + + ]: 790609 : return ((void*) ptr == state->end ||
39 [ + + ]: 393037 : SRE_IS_LINEBREAK((int) ptr[0]));
40 : :
41 : 7008391 : case SRE_AT_END_STRING:
42 : 7008391 : return ((void*) ptr == state->end);
43 : :
44 : 44 : case SRE_AT_BOUNDARY:
45 [ - + ]: 44 : if (state->beginning == state->end)
46 : 0 : return 0;
47 : 88 : thatp = ((void*) ptr > state->beginning) ?
48 [ + + + - : 44 : SRE_IS_WORD((int) ptr[-1]) : 0;
+ + - + ]
49 : 88 : thisp = ((void*) ptr < state->end) ?
50 [ + + + - : 44 : SRE_IS_WORD((int) ptr[0]) : 0;
+ + - + ]
51 : 44 : return thisp != thatp;
52 : :
53 : 40 : case SRE_AT_NON_BOUNDARY:
54 [ - + ]: 40 : if (state->beginning == state->end)
55 : 0 : return 0;
56 : 80 : thatp = ((void*) ptr > state->beginning) ?
57 [ + + + - : 40 : SRE_IS_WORD((int) ptr[-1]) : 0;
+ + - + ]
58 : 80 : thisp = ((void*) ptr < state->end) ?
59 [ + - + - : 40 : SRE_IS_WORD((int) ptr[0]) : 0;
+ + - + ]
60 : 40 : return thisp == thatp;
61 : :
62 : 28 : case SRE_AT_LOC_BOUNDARY:
63 [ - + ]: 28 : if (state->beginning == state->end)
64 : 0 : return 0;
65 : 56 : thatp = ((void*) ptr > state->beginning) ?
66 [ + + + + : 28 : SRE_LOC_IS_WORD((int) ptr[-1]) : 0;
- + # # ]
67 : 56 : thisp = ((void*) ptr < state->end) ?
68 [ + + + + : 28 : SRE_LOC_IS_WORD((int) ptr[0]) : 0;
- + # # ]
69 : 28 : return thisp != thatp;
70 : :
71 : 25 : case SRE_AT_LOC_NON_BOUNDARY:
72 [ - + ]: 25 : if (state->beginning == state->end)
73 : 0 : return 0;
74 : 50 : thatp = ((void*) ptr > state->beginning) ?
75 [ + + + + : 25 : SRE_LOC_IS_WORD((int) ptr[-1]) : 0;
- + # # ]
76 : 50 : thisp = ((void*) ptr < state->end) ?
77 [ + - + + : 25 : SRE_LOC_IS_WORD((int) ptr[0]) : 0;
- + # # ]
78 : 25 : return thisp == thatp;
79 : :
80 : 61143695 : case SRE_AT_UNI_BOUNDARY:
81 [ + + ]: 61143695 : if (state->beginning == state->end)
82 : 1 : return 0;
83 : 122287388 : thatp = ((void*) ptr > state->beginning) ?
84 [ + + + + : 61143694 : SRE_UNI_IS_WORD((int) ptr[-1]) : 0;
+ + ]
85 : 122287388 : thisp = ((void*) ptr < state->end) ?
86 [ + + + + : 61143694 : SRE_UNI_IS_WORD((int) ptr[0]) : 0;
+ + ]
87 : 61143694 : return thisp != thatp;
88 : :
89 : 77 : case SRE_AT_UNI_NON_BOUNDARY:
90 [ + + ]: 77 : if (state->beginning == state->end)
91 : 1 : return 0;
92 : 152 : thatp = ((void*) ptr > state->beginning) ?
93 [ + + + + : 76 : SRE_UNI_IS_WORD((int) ptr[-1]) : 0;
- + ]
94 : 152 : thisp = ((void*) ptr < state->end) ?
95 [ + + + + : 76 : SRE_UNI_IS_WORD((int) ptr[0]) : 0;
- + ]
96 : 76 : return thisp == thatp;
97 : :
98 : : }
99 : :
100 : 0 : return 0;
101 : : }
102 : :
103 : : LOCAL(int)
104 : 115696343 : SRE(charset)(SRE_STATE* state, const SRE_CODE* set, SRE_CODE ch)
105 : : {
106 : : /* check if character is a member of the given set */
107 : :
108 : 115696343 : int ok = 1;
109 : :
110 : : for (;;) {
111 [ + + + + : 210640717 : switch (*set++) {
+ + + +
- ]
112 : :
113 : 77690799 : case SRE_OP_FAILURE:
114 : 77690799 : return !ok;
115 : :
116 : 18584080 : case SRE_OP_LITERAL:
117 : : /* <LITERAL> <code> */
118 [ + + ]: 18584080 : if (ch == set[0])
119 : 918210 : return ok;
120 : 17665870 : set++;
121 : 17665870 : break;
122 : :
123 : 40840579 : case SRE_OP_CATEGORY:
124 : : /* <CATEGORY> <code> */
125 [ + + ]: 40840579 : if (sre_category(set[0], (int) ch))
126 : 28398059 : return ok;
127 : 12442520 : set++;
128 : 12442520 : break;
129 : :
130 : 19199817 : case SRE_OP_CHARSET:
131 : : /* <CHARSET> <bitmap> */
132 [ + + ]: 19199817 : if (ch < 256 &&
133 [ + + ]: 19198475 : (set[ch/SRE_CODE_BITS] & (1u << (ch & (SRE_CODE_BITS-1)))))
134 : 5157924 : return ok;
135 : 14041893 : set += 256/SRE_CODE_BITS;
136 : 14041893 : break;
137 : :
138 : 46677721 : case SRE_OP_RANGE:
139 : : /* <RANGE> <lower> <upper> */
140 [ + + + + ]: 46677721 : if (set[0] <= ch && ch <= set[1])
141 : 3527779 : return ok;
142 : 43149942 : set += 2;
143 : 43149942 : break;
144 : :
145 : 4 : case SRE_OP_RANGE_UNI_IGNORE:
146 : : /* <RANGE_UNI_IGNORE> <lower> <upper> */
147 : : {
148 : : SRE_CODE uch;
149 : : /* ch is already lower cased */
150 [ + - + + ]: 4 : if (set[0] <= ch && ch <= set[1])
151 : 2 : return ok;
152 : 2 : uch = sre_upper_unicode(ch);
153 [ + - + - ]: 2 : if (set[0] <= uch && uch <= set[1])
154 : 2 : return ok;
155 : 0 : set += 2;
156 : 0 : break;
157 : : }
158 : :
159 : 7643470 : case SRE_OP_NEGATE:
160 : 7643470 : ok = !ok;
161 : 7643470 : break;
162 : :
163 : 4247 : case SRE_OP_BIGCHARSET:
164 : : /* <BIGCHARSET> <blockcount> <256 blockindices> <blocks> */
165 : : {
166 : : Py_ssize_t count, block;
167 : 4247 : count = *(set++);
168 : :
169 [ + - ]: 4247 : if (ch < 0x10000u)
170 : 4247 : block = ((unsigned char*)set)[ch >> 8];
171 : : else
172 : 0 : block = -1;
173 : 4247 : set += 256/sizeof(SRE_CODE);
174 [ + - ]: 4247 : if (block >=0 &&
175 : 4247 : (set[(block * 256 + (ch & 255))/SRE_CODE_BITS] &
176 [ + + ]: 4247 : (1u << (ch & (SRE_CODE_BITS-1)))))
177 : 3568 : return ok;
178 : 679 : set += count * (256/SRE_CODE_BITS);
179 : 679 : break;
180 : : }
181 : :
182 : 0 : default:
183 : : /* internal error -- there's not much we can do about it
184 : : here, so let's just pretend it didn't match... */
185 : 0 : return 0;
186 : : }
187 : : }
188 : : }
189 : :
190 : : LOCAL(int)
191 : 80 : SRE(charset_loc_ignore)(SRE_STATE* state, const SRE_CODE* set, SRE_CODE ch)
192 : : {
193 : : SRE_CODE lo, up;
194 : 80 : lo = sre_lower_locale(ch);
195 [ + + ]: 80 : if (SRE(charset)(state, set, lo))
196 : 63 : return 1;
197 : :
198 : 17 : up = sre_upper_locale(ch);
199 [ + + + + ]: 17 : return up != lo && SRE(charset)(state, set, up);
200 : : }
201 : :
202 : : LOCAL(Py_ssize_t) SRE(match)(SRE_STATE* state, const SRE_CODE* pattern, int toplevel);
203 : :
204 : : LOCAL(Py_ssize_t)
205 : 29817240 : SRE(count)(SRE_STATE* state, const SRE_CODE* pattern, Py_ssize_t maxcount)
206 : : {
207 : : SRE_CODE chr;
208 : : SRE_CHAR c;
209 : 29817240 : const SRE_CHAR* ptr = (const SRE_CHAR *)state->ptr;
210 : 29817240 : const SRE_CHAR* end = (const SRE_CHAR *)state->end;
211 : : Py_ssize_t i;
212 : :
213 : : /* adjust end */
214 [ + + + - ]: 29817240 : if (maxcount < end - ptr && maxcount != SRE_MAXREPEAT)
215 : 10893887 : end = ptr + maxcount;
216 : :
217 [ + + + + : 29817240 : switch (pattern[0]) {
+ + + + -
+ - + ]
218 : :
219 : 20274000 : case SRE_OP_IN:
220 : : /* repeated set */
221 : : TRACE(("|%p|%p|COUNT IN\n", pattern, ptr));
222 [ + + + + ]: 60184479 : while (ptr < end && SRE(charset)(state, pattern + 2, *ptr))
223 : 39910479 : ptr++;
224 : 20274000 : break;
225 : :
226 : 463429 : case SRE_OP_ANY:
227 : : /* repeated dot wildcard. */
228 : : TRACE(("|%p|%p|COUNT ANY\n", pattern, ptr));
229 [ + + + + ]: 5620367 : while (ptr < end && !SRE_IS_LINEBREAK(*ptr))
230 : 5156938 : ptr++;
231 : 463429 : break;
232 : :
233 : 35575 : case SRE_OP_ANY_ALL:
234 : : /* repeated dot wildcard. skip to the end of the target
235 : : string, and backtrack from there */
236 : : TRACE(("|%p|%p|COUNT ANY_ALL\n", pattern, ptr));
237 : 35575 : ptr = end;
238 : 35575 : break;
239 : :
240 : 9020438 : case SRE_OP_LITERAL:
241 : : /* repeated literal */
242 : 9020438 : chr = pattern[1];
243 : : TRACE(("|%p|%p|COUNT LITERAL %d\n", pattern, ptr, chr));
244 : 9020438 : c = (SRE_CHAR) chr;
245 : : #if SIZEOF_SRE_CHAR < 4
246 [ + - ]: 9020013 : if ((SRE_CODE) c != chr)
247 : : ; /* literal can't match: doesn't fit in char width */
248 : : else
249 : : #endif
250 [ + + + + ]: 9464915 : while (ptr < end && *ptr == c)
251 : 444477 : ptr++;
252 : 9020438 : break;
253 : :
254 : 71 : case SRE_OP_LITERAL_IGNORE:
255 : : /* repeated literal */
256 : 71 : chr = pattern[1];
257 : : TRACE(("|%p|%p|COUNT LITERAL_IGNORE %d\n", pattern, ptr, chr));
258 [ + + + + ]: 143 : while (ptr < end && (SRE_CODE) sre_lower_ascii(*ptr) == chr)
259 : 72 : ptr++;
260 : 71 : break;
261 : :
262 : 3178 : case SRE_OP_LITERAL_UNI_IGNORE:
263 : : /* repeated literal */
264 : 3178 : chr = pattern[1];
265 : : TRACE(("|%p|%p|COUNT LITERAL_UNI_IGNORE %d\n", pattern, ptr, chr));
266 [ + + + + ]: 3557 : while (ptr < end && (SRE_CODE) sre_lower_unicode(*ptr) == chr)
267 : 379 : ptr++;
268 : 3178 : break;
269 : :
270 : 74 : case SRE_OP_LITERAL_LOC_IGNORE:
271 : : /* repeated literal */
272 : 74 : chr = pattern[1];
273 : : TRACE(("|%p|%p|COUNT LITERAL_LOC_IGNORE %d\n", pattern, ptr, chr));
274 [ + + + + ]: 148 : while (ptr < end && char_loc_ignore(chr, *ptr))
275 : 74 : ptr++;
276 : 74 : break;
277 : :
278 : 19834 : case SRE_OP_NOT_LITERAL:
279 : : /* repeated non-literal */
280 : 19834 : chr = pattern[1];
281 : : TRACE(("|%p|%p|COUNT NOT_LITERAL %d\n", pattern, ptr, chr));
282 : 19834 : c = (SRE_CHAR) chr;
283 : : #if SIZEOF_SRE_CHAR < 4
284 [ - + ]: 19834 : if ((SRE_CODE) c != chr)
285 : 0 : ptr = end; /* literal can't match: doesn't fit in char width */
286 : : else
287 : : #endif
288 [ + + + + ]: 198900 : while (ptr < end && *ptr != c)
289 : 179066 : ptr++;
290 : 19834 : break;
291 : :
292 : 0 : case SRE_OP_NOT_LITERAL_IGNORE:
293 : : /* repeated non-literal */
294 : 0 : chr = pattern[1];
295 : : TRACE(("|%p|%p|COUNT NOT_LITERAL_IGNORE %d\n", pattern, ptr, chr));
296 [ # # # # ]: 0 : while (ptr < end && (SRE_CODE) sre_lower_ascii(*ptr) != chr)
297 : 0 : ptr++;
298 : 0 : break;
299 : :
300 : 8 : case SRE_OP_NOT_LITERAL_UNI_IGNORE:
301 : : /* repeated non-literal */
302 : 8 : chr = pattern[1];
303 : : TRACE(("|%p|%p|COUNT NOT_LITERAL_UNI_IGNORE %d\n", pattern, ptr, chr));
304 [ + + + + ]: 20 : while (ptr < end && (SRE_CODE) sre_lower_unicode(*ptr) != chr)
305 : 12 : ptr++;
306 : 8 : break;
307 : :
308 : 0 : case SRE_OP_NOT_LITERAL_LOC_IGNORE:
309 : : /* repeated non-literal */
310 : 0 : chr = pattern[1];
311 : : TRACE(("|%p|%p|COUNT NOT_LITERAL_LOC_IGNORE %d\n", pattern, ptr, chr));
312 [ # # # # ]: 0 : while (ptr < end && !char_loc_ignore(chr, *ptr))
313 : 0 : ptr++;
314 : 0 : break;
315 : :
316 : 633 : default:
317 : : /* repeated single character pattern */
318 : : TRACE(("|%p|%p|COUNT SUBPATTERN\n", pattern, ptr));
319 [ + + ]: 3920 : while ((SRE_CHAR*) state->ptr < end) {
320 : 3552 : i = SRE(match)(state, pattern, 0);
321 [ - + ]: 3552 : if (i < 0)
322 : 0 : return i;
323 [ + + ]: 3552 : if (!i)
324 : 265 : break;
325 : : }
326 : : TRACE(("|%p|%p|COUNT %zd\n", pattern, ptr,
327 : : (SRE_CHAR*) state->ptr - ptr));
328 : 633 : return (SRE_CHAR*) state->ptr - ptr;
329 : : }
330 : :
331 : : TRACE(("|%p|%p|COUNT %zd\n", pattern, ptr,
332 : : ptr - (SRE_CHAR*) state->ptr));
333 : 29816607 : return ptr - (SRE_CHAR*) state->ptr;
334 : : }
335 : :
336 : : /* The macros below should be used to protect recursive SRE(match)()
337 : : * calls that *failed* and do *not* return immediately (IOW, those
338 : : * that will backtrack). Explaining:
339 : : *
340 : : * - Recursive SRE(match)() returned true: that's usually a success
341 : : * (besides atypical cases like ASSERT_NOT), therefore there's no
342 : : * reason to restore lastmark;
343 : : *
344 : : * - Recursive SRE(match)() returned false but the current SRE(match)()
345 : : * is returning to the caller: If the current SRE(match)() is the
346 : : * top function of the recursion, returning false will be a matching
347 : : * failure, and it doesn't matter where lastmark is pointing to.
348 : : * If it's *not* the top function, it will be a recursive SRE(match)()
349 : : * failure by itself, and the calling SRE(match)() will have to deal
350 : : * with the failure by the same rules explained here (it will restore
351 : : * lastmark by itself if necessary);
352 : : *
353 : : * - Recursive SRE(match)() returned false, and will continue the
354 : : * outside 'for' loop: must be protected when breaking, since the next
355 : : * OP could potentially depend on lastmark;
356 : : *
357 : : * - Recursive SRE(match)() returned false, and will be called again
358 : : * inside a local for/while loop: must be protected between each
359 : : * loop iteration, since the recursive SRE(match)() could do anything,
360 : : * and could potentially depend on lastmark.
361 : : *
362 : : * For more information, check the discussion at SF patch #712900.
363 : : */
364 : : #define LASTMARK_SAVE() \
365 : : do { \
366 : : ctx->lastmark = state->lastmark; \
367 : : ctx->lastindex = state->lastindex; \
368 : : } while (0)
369 : : #define LASTMARK_RESTORE() \
370 : : do { \
371 : : state->lastmark = ctx->lastmark; \
372 : : state->lastindex = ctx->lastindex; \
373 : : } while (0)
374 : :
375 : : #define RETURN_ERROR(i) do { return i; } while(0)
376 : : #define RETURN_FAILURE do { ret = 0; goto exit; } while(0)
377 : : #define RETURN_SUCCESS do { ret = 1; goto exit; } while(0)
378 : :
379 : : #define RETURN_ON_ERROR(i) \
380 : : do { if (i < 0) RETURN_ERROR(i); } while (0)
381 : : #define RETURN_ON_SUCCESS(i) \
382 : : do { RETURN_ON_ERROR(i); if (i > 0) RETURN_SUCCESS; } while (0)
383 : : #define RETURN_ON_FAILURE(i) \
384 : : do { RETURN_ON_ERROR(i); if (i == 0) RETURN_FAILURE; } while (0)
385 : :
386 : : #define DATA_STACK_ALLOC(state, type, ptr) \
387 : : do { \
388 : : alloc_pos = state->data_stack_base; \
389 : : TRACE(("allocating %s in %zd (%zd)\n", \
390 : : Py_STRINGIFY(type), alloc_pos, sizeof(type))); \
391 : : if (sizeof(type) > state->data_stack_size - alloc_pos) { \
392 : : int j = data_stack_grow(state, sizeof(type)); \
393 : : if (j < 0) return j; \
394 : : if (ctx_pos != -1) \
395 : : DATA_STACK_LOOKUP_AT(state, SRE(match_context), ctx, ctx_pos); \
396 : : } \
397 : : ptr = (type*)(state->data_stack+alloc_pos); \
398 : : state->data_stack_base += sizeof(type); \
399 : : } while (0)
400 : :
401 : : #define DATA_STACK_LOOKUP_AT(state, type, ptr, pos) \
402 : : do { \
403 : : TRACE(("looking up %s at %zd\n", Py_STRINGIFY(type), pos)); \
404 : : ptr = (type*)(state->data_stack+pos); \
405 : : } while (0)
406 : :
407 : : #define DATA_STACK_PUSH(state, data, size) \
408 : : do { \
409 : : TRACE(("copy data in %p to %zd (%zd)\n", \
410 : : data, state->data_stack_base, size)); \
411 : : if (size > state->data_stack_size - state->data_stack_base) { \
412 : : int j = data_stack_grow(state, size); \
413 : : if (j < 0) return j; \
414 : : if (ctx_pos != -1) \
415 : : DATA_STACK_LOOKUP_AT(state, SRE(match_context), ctx, ctx_pos); \
416 : : } \
417 : : memcpy(state->data_stack+state->data_stack_base, data, size); \
418 : : state->data_stack_base += size; \
419 : : } while (0)
420 : :
421 : : /* We add an explicit cast to memcpy here because MSVC has a bug when
422 : : compiling C code where it believes that `const void**` cannot be
423 : : safely casted to `void*`, see bpo-39943 for details. */
424 : : #define DATA_STACK_POP(state, data, size, discard) \
425 : : do { \
426 : : TRACE(("copy data to %p from %zd (%zd)\n", \
427 : : data, state->data_stack_base-size, size)); \
428 : : memcpy((void*) data, state->data_stack+state->data_stack_base-size, size); \
429 : : if (discard) \
430 : : state->data_stack_base -= size; \
431 : : } while (0)
432 : :
433 : : #define DATA_STACK_POP_DISCARD(state, size) \
434 : : do { \
435 : : TRACE(("discard data from %zd (%zd)\n", \
436 : : state->data_stack_base-size, size)); \
437 : : state->data_stack_base -= size; \
438 : : } while(0)
439 : :
440 : : #define DATA_PUSH(x) \
441 : : DATA_STACK_PUSH(state, (x), sizeof(*(x)))
442 : : #define DATA_POP(x) \
443 : : DATA_STACK_POP(state, (x), sizeof(*(x)), 1)
444 : : #define DATA_POP_DISCARD(x) \
445 : : DATA_STACK_POP_DISCARD(state, sizeof(*(x)))
446 : : #define DATA_ALLOC(t,p) \
447 : : DATA_STACK_ALLOC(state, t, p)
448 : : #define DATA_LOOKUP_AT(t,p,pos) \
449 : : DATA_STACK_LOOKUP_AT(state,t,p,pos)
450 : :
451 : : #define MARK_PUSH(lastmark) \
452 : : do if (lastmark >= 0) { \
453 : : size_t _marks_size = (lastmark+1) * sizeof(void*); \
454 : : DATA_STACK_PUSH(state, state->mark, _marks_size); \
455 : : } while (0)
456 : : #define MARK_POP(lastmark) \
457 : : do if (lastmark >= 0) { \
458 : : size_t _marks_size = (lastmark+1) * sizeof(void*); \
459 : : DATA_STACK_POP(state, state->mark, _marks_size, 1); \
460 : : } while (0)
461 : : #define MARK_POP_KEEP(lastmark) \
462 : : do if (lastmark >= 0) { \
463 : : size_t _marks_size = (lastmark+1) * sizeof(void*); \
464 : : DATA_STACK_POP(state, state->mark, _marks_size, 0); \
465 : : } while (0)
466 : : #define MARK_POP_DISCARD(lastmark) \
467 : : do if (lastmark >= 0) { \
468 : : size_t _marks_size = (lastmark+1) * sizeof(void*); \
469 : : DATA_STACK_POP_DISCARD(state, _marks_size); \
470 : : } while (0)
471 : :
472 : : #define JUMP_NONE 0
473 : : #define JUMP_MAX_UNTIL_1 1
474 : : #define JUMP_MAX_UNTIL_2 2
475 : : #define JUMP_MAX_UNTIL_3 3
476 : : #define JUMP_MIN_UNTIL_1 4
477 : : #define JUMP_MIN_UNTIL_2 5
478 : : #define JUMP_MIN_UNTIL_3 6
479 : : #define JUMP_REPEAT 7
480 : : #define JUMP_REPEAT_ONE_1 8
481 : : #define JUMP_REPEAT_ONE_2 9
482 : : #define JUMP_MIN_REPEAT_ONE 10
483 : : #define JUMP_BRANCH 11
484 : : #define JUMP_ASSERT 12
485 : : #define JUMP_ASSERT_NOT 13
486 : : #define JUMP_POSS_REPEAT_1 14
487 : : #define JUMP_POSS_REPEAT_2 15
488 : : #define JUMP_ATOMIC_GROUP 16
489 : :
490 : : #define DO_JUMPX(jumpvalue, jumplabel, nextpattern, toplevel_) \
491 : : ctx->pattern = pattern; \
492 : : ctx->ptr = ptr; \
493 : : DATA_ALLOC(SRE(match_context), nextctx); \
494 : : nextctx->pattern = nextpattern; \
495 : : nextctx->toplevel = toplevel_; \
496 : : nextctx->jump = jumpvalue; \
497 : : nextctx->last_ctx_pos = ctx_pos; \
498 : : pattern = nextpattern; \
499 : : ctx_pos = alloc_pos; \
500 : : ctx = nextctx; \
501 : : goto entrance; \
502 : : jumplabel: \
503 : : pattern = ctx->pattern; \
504 : : ptr = ctx->ptr;
505 : :
506 : : #define DO_JUMP(jumpvalue, jumplabel, nextpattern) \
507 : : DO_JUMPX(jumpvalue, jumplabel, nextpattern, ctx->toplevel)
508 : :
509 : : #define DO_JUMP0(jumpvalue, jumplabel, nextpattern) \
510 : : DO_JUMPX(jumpvalue, jumplabel, nextpattern, 0)
511 : :
512 : : typedef struct {
513 : : Py_ssize_t count;
514 : : union {
515 : : SRE_CODE chr;
516 : : SRE_REPEAT* rep;
517 : : } u;
518 : : int lastmark;
519 : : int lastindex;
520 : : const SRE_CODE* pattern;
521 : : const SRE_CHAR* ptr;
522 : : int toplevel;
523 : : int jump;
524 : : Py_ssize_t last_ctx_pos;
525 : : } SRE(match_context);
526 : :
527 : : #define MAYBE_CHECK_SIGNALS \
528 : : do { \
529 : : if ((0 == (++sigcount & 0xfff)) && PyErr_CheckSignals()) { \
530 : : RETURN_ERROR(SRE_ERROR_INTERRUPTED); \
531 : : } \
532 : : } while (0)
533 : :
534 : : #ifdef HAVE_COMPUTED_GOTOS
535 : : #ifndef USE_COMPUTED_GOTOS
536 : : #define USE_COMPUTED_GOTOS 1
537 : : #endif
538 : : #elif defined(USE_COMPUTED_GOTOS) && USE_COMPUTED_GOTOS
539 : : #error "Computed gotos are not supported on this compiler."
540 : : #else
541 : : #undef USE_COMPUTED_GOTOS
542 : : #define USE_COMPUTED_GOTOS 0
543 : : #endif
544 : :
545 : : #if USE_COMPUTED_GOTOS
546 : : #define TARGET(OP) TARGET_ ## OP
547 : : #define DISPATCH \
548 : : do { \
549 : : MAYBE_CHECK_SIGNALS; \
550 : : goto *sre_targets[*pattern++]; \
551 : : } while (0)
552 : : #else
553 : : #define TARGET(OP) case OP
554 : : #define DISPATCH goto dispatch
555 : : #endif
556 : :
557 : : /* check if string matches the given pattern. returns <0 for
558 : : error, 0 for failure, and 1 for success */
559 : : LOCAL(Py_ssize_t)
560 : 77981869 : SRE(match)(SRE_STATE* state, const SRE_CODE* pattern, int toplevel)
561 : : {
562 : 77981869 : const SRE_CHAR* end = (const SRE_CHAR *)state->end;
563 : 77981869 : Py_ssize_t alloc_pos, ctx_pos = -1;
564 : 77981869 : Py_ssize_t ret = 0;
565 : : int jump;
566 : 77981869 : unsigned int sigcount=0;
567 : :
568 : : SRE(match_context)* ctx;
569 : : SRE(match_context)* nextctx;
570 : :
571 : : TRACE(("|%p|%p|ENTER\n", pattern, state->ptr));
572 : :
573 [ + + - + : 77981869 : DATA_ALLOC(SRE(match_context), ctx);
- + ]
574 : 77981869 : ctx->last_ctx_pos = -1;
575 : 77981869 : ctx->jump = JUMP_NONE;
576 : 77981869 : ctx->toplevel = toplevel;
577 : 77981869 : ctx_pos = alloc_pos;
578 : :
579 : : #if USE_COMPUTED_GOTOS
580 : : #include "sre_targets.h"
581 : : #endif
582 : :
583 : 220222995 : entrance:
584 : :
585 : : ; // Fashion statement.
586 : 298204864 : const SRE_CHAR *ptr = (SRE_CHAR *)state->ptr;
587 : :
588 [ + + ]: 298204864 : if (pattern[0] == SRE_OP_INFO) {
589 : : /* optimization info block */
590 : : /* <INFO> <1=skip> <2=flags> <3=min> ... */
591 [ + + + + ]: 8318623 : if (pattern[3] && (uintptr_t)(end - ptr) < pattern[3]) {
592 : : TRACE(("reject (got %zd chars, need %zd)\n",
593 : : end - ptr, (Py_ssize_t) pattern[3]));
594 : 58805 : RETURN_FAILURE;
595 : : }
596 : 8259818 : pattern += pattern[1] + 1;
597 : : }
598 : :
599 : : #if USE_COMPUTED_GOTOS
600 [ + + - + ]: 298146059 : DISPATCH;
601 : : #else
602 : : dispatch:
603 : : MAYBE_CHECK_SIGNALS;
604 : : switch (*pattern++)
605 : : #endif
606 : : {
607 : :
608 : 151778278 : TARGET(SRE_OP_MARK):
609 : : /* set mark */
610 : : /* <MARK> <gid> */
611 : : TRACE(("|%p|%p|MARK %d\n", pattern,
612 : : ptr, pattern[0]));
613 : : {
614 : 151778278 : int i = pattern[0];
615 [ + + ]: 151778278 : if (i & 1)
616 : 37601247 : state->lastindex = i/2 + 1;
617 [ + + ]: 151778278 : if (i > state->lastmark) {
618 : : /* state->lastmark is the highest valid index in the
619 : : state->mark array. If it is increased by more than 1,
620 : : the intervening marks must be set to NULL to signal
621 : : that these marks have not been encountered. */
622 : 142564919 : int j = state->lastmark + 1;
623 [ + + ]: 751415489 : while (j < i)
624 : 608850570 : state->mark[j++] = NULL;
625 : 142564919 : state->lastmark = i;
626 : : }
627 : 151778278 : state->mark[i] = ptr;
628 : : }
629 : 151778278 : pattern++;
630 [ + + - + ]: 151778278 : DISPATCH;
631 : :
632 : 60618005 : TARGET(SRE_OP_LITERAL):
633 : : /* match literal string */
634 : : /* <LITERAL> <code> */
635 : : TRACE(("|%p|%p|LITERAL %d\n", pattern,
636 : : ptr, *pattern));
637 [ + + + + ]: 60618005 : if (ptr >= end || (SRE_CODE) ptr[0] != pattern[0])
638 : 46312725 : RETURN_FAILURE;
639 : 14305280 : pattern++;
640 : 14305280 : ptr++;
641 [ + + - + ]: 14305280 : DISPATCH;
642 : :
643 : 142 : TARGET(SRE_OP_NOT_LITERAL):
644 : : /* match anything that is not literal character */
645 : : /* <NOT_LITERAL> <code> */
646 : : TRACE(("|%p|%p|NOT_LITERAL %d\n", pattern,
647 : : ptr, *pattern));
648 [ + + + + ]: 142 : if (ptr >= end || (SRE_CODE) ptr[0] == pattern[0])
649 : 5 : RETURN_FAILURE;
650 : 137 : pattern++;
651 : 137 : ptr++;
652 [ - + - - ]: 137 : DISPATCH;
653 : :
654 : 8296633 : TARGET(SRE_OP_SUCCESS):
655 : : /* end of pattern */
656 : : TRACE(("|%p|%p|SUCCESS\n", pattern, ptr));
657 [ + + ]: 8296633 : if (ctx->toplevel &&
658 [ + + + + ]: 7844123 : ((state->match_all && ptr != state->end) ||
659 [ + + + + ]: 7844025 : (state->must_advance && ptr == state->start)))
660 : : {
661 : 19312 : RETURN_FAILURE;
662 : : }
663 : 8277321 : state->ptr = ptr;
664 : 8277321 : RETURN_SUCCESS;
665 : :
666 : 78314136 : TARGET(SRE_OP_AT):
667 : : /* match at given position */
668 : : /* <AT> <code> */
669 : : TRACE(("|%p|%p|AT %d\n", pattern, ptr, *pattern));
670 [ + + ]: 78314136 : if (!SRE(at)(state, ptr, *pattern))
671 : 62999661 : RETURN_FAILURE;
672 : 15314475 : pattern++;
673 [ - + - - ]: 15314475 : DISPATCH;
674 : :
675 : 0 : TARGET(SRE_OP_CATEGORY):
676 : : /* match at given category */
677 : : /* <CATEGORY> <code> */
678 : : TRACE(("|%p|%p|CATEGORY %d\n", pattern,
679 : : ptr, *pattern));
680 [ # # # # ]: 0 : if (ptr >= end || !sre_category(pattern[0], ptr[0]))
681 : 0 : RETURN_FAILURE;
682 : 0 : pattern++;
683 : 0 : ptr++;
684 [ # # # # ]: 0 : DISPATCH;
685 : :
686 : 151739 : TARGET(SRE_OP_ANY):
687 : : /* match anything (except a newline) */
688 : : /* <ANY> */
689 : : TRACE(("|%p|%p|ANY\n", pattern, ptr));
690 [ + + + + ]: 151739 : if (ptr >= end || SRE_IS_LINEBREAK(ptr[0]))
691 : 1208 : RETURN_FAILURE;
692 : 150531 : ptr++;
693 [ - + - - ]: 150531 : DISPATCH;
694 : :
695 : 684 : TARGET(SRE_OP_ANY_ALL):
696 : : /* match anything */
697 : : /* <ANY_ALL> */
698 : : TRACE(("|%p|%p|ANY_ALL\n", pattern, ptr));
699 [ + + ]: 684 : if (ptr >= end)
700 : 5 : RETURN_FAILURE;
701 : 679 : ptr++;
702 [ - + - - ]: 679 : DISPATCH;
703 : :
704 : 10120171 : TARGET(SRE_OP_IN):
705 : : /* match set member (or non_member) */
706 : : /* <IN> <skip> <set> */
707 : : TRACE(("|%p|%p|IN\n", pattern, ptr));
708 [ + + + + ]: 20232872 : if (ptr >= end ||
709 : 10112701 : !SRE(charset)(state, pattern + 1, *ptr))
710 : 7280164 : RETURN_FAILURE;
711 : 2840007 : pattern += pattern[0];
712 : 2840007 : ptr++;
713 [ + + - + ]: 2840007 : DISPATCH;
714 : :
715 : 945 : TARGET(SRE_OP_LITERAL_IGNORE):
716 : : TRACE(("|%p|%p|LITERAL_IGNORE %d\n",
717 : : pattern, ptr, pattern[0]));
718 [ + + ]: 945 : if (ptr >= end ||
719 [ + + ]: 939 : sre_lower_ascii(*ptr) != *pattern)
720 : 644 : RETURN_FAILURE;
721 : 301 : pattern++;
722 : 301 : ptr++;
723 [ - + - - ]: 301 : DISPATCH;
724 : :
725 : 208558 : TARGET(SRE_OP_LITERAL_UNI_IGNORE):
726 : : TRACE(("|%p|%p|LITERAL_UNI_IGNORE %d\n",
727 : : pattern, ptr, pattern[0]));
728 [ + + ]: 208558 : if (ptr >= end ||
729 [ + + ]: 115423 : sre_lower_unicode(*ptr) != *pattern)
730 : 104591 : RETURN_FAILURE;
731 : 103967 : pattern++;
732 : 103967 : ptr++;
733 [ - + - - ]: 103967 : DISPATCH;
734 : :
735 : 347 : TARGET(SRE_OP_LITERAL_LOC_IGNORE):
736 : : TRACE(("|%p|%p|LITERAL_LOC_IGNORE %d\n",
737 : : pattern, ptr, pattern[0]));
738 [ + + ]: 347 : if (ptr >= end
739 [ + + ]: 339 : || !char_loc_ignore(*pattern, *ptr))
740 : 91 : RETURN_FAILURE;
741 : 256 : pattern++;
742 : 256 : ptr++;
743 [ - + - - ]: 256 : DISPATCH;
744 : :
745 : 0 : TARGET(SRE_OP_NOT_LITERAL_IGNORE):
746 : : TRACE(("|%p|%p|NOT_LITERAL_IGNORE %d\n",
747 : : pattern, ptr, *pattern));
748 [ # # ]: 0 : if (ptr >= end ||
749 [ # # ]: 0 : sre_lower_ascii(*ptr) == *pattern)
750 : 0 : RETURN_FAILURE;
751 : 0 : pattern++;
752 : 0 : ptr++;
753 [ # # # # ]: 0 : DISPATCH;
754 : :
755 : 1 : TARGET(SRE_OP_NOT_LITERAL_UNI_IGNORE):
756 : : TRACE(("|%p|%p|NOT_LITERAL_UNI_IGNORE %d\n",
757 : : pattern, ptr, *pattern));
758 [ + - ]: 1 : if (ptr >= end ||
759 [ - + ]: 1 : sre_lower_unicode(*ptr) == *pattern)
760 : 0 : RETURN_FAILURE;
761 : 1 : pattern++;
762 : 1 : ptr++;
763 [ - + - - ]: 1 : DISPATCH;
764 : :
765 : 8 : TARGET(SRE_OP_NOT_LITERAL_LOC_IGNORE):
766 : : TRACE(("|%p|%p|NOT_LITERAL_LOC_IGNORE %d\n",
767 : : pattern, ptr, *pattern));
768 [ + - ]: 8 : if (ptr >= end
769 [ + + ]: 8 : || char_loc_ignore(*pattern, *ptr))
770 : 5 : RETURN_FAILURE;
771 : 3 : pattern++;
772 : 3 : ptr++;
773 [ - + - - ]: 3 : DISPATCH;
774 : :
775 : 982 : TARGET(SRE_OP_IN_IGNORE):
776 : : TRACE(("|%p|%p|IN_IGNORE\n", pattern, ptr));
777 [ + + ]: 982 : if (ptr >= end
778 [ + + ]: 977 : || !SRE(charset)(state, pattern+1,
779 : 977 : (SRE_CODE)sre_lower_ascii(*ptr)))
780 : 216 : RETURN_FAILURE;
781 : 766 : pattern += pattern[0];
782 : 766 : ptr++;
783 [ - + - - ]: 766 : DISPATCH;
784 : :
785 : 36068 : TARGET(SRE_OP_IN_UNI_IGNORE):
786 : : TRACE(("|%p|%p|IN_UNI_IGNORE\n", pattern, ptr));
787 [ + + ]: 36068 : if (ptr >= end
788 [ + + ]: 31213 : || !SRE(charset)(state, pattern+1,
789 : 31209 : (SRE_CODE)sre_lower_unicode(*ptr)))
790 : 18033 : RETURN_FAILURE;
791 : 18035 : pattern += pattern[0];
792 : 18035 : ptr++;
793 [ - + - - ]: 18035 : DISPATCH;
794 : :
795 : 80 : TARGET(SRE_OP_IN_LOC_IGNORE):
796 : : TRACE(("|%p|%p|IN_LOC_IGNORE\n", pattern, ptr));
797 [ + - ]: 80 : if (ptr >= end
798 [ + + ]: 80 : || !SRE(charset_loc_ignore)(state, pattern+1, *ptr))
799 : 11 : RETURN_FAILURE;
800 : 69 : pattern += pattern[0];
801 : 69 : ptr++;
802 [ - + - - ]: 69 : DISPATCH;
803 : :
804 : 37714446 : TARGET(SRE_OP_JUMP):
805 : 37714446 : TARGET(SRE_OP_INFO):
806 : : /* jump forward */
807 : : /* <JUMP> <offset> */
808 : : TRACE(("|%p|%p|JUMP %d\n", pattern,
809 : : ptr, pattern[0]));
810 : 37714446 : pattern += pattern[0];
811 [ + + - + ]: 37714446 : DISPATCH;
812 : :
813 : 120524873 : TARGET(SRE_OP_BRANCH):
814 : : /* alternation */
815 : : /* <BRANCH> <0=skip> code <JUMP> ... <NULL> */
816 : : TRACE(("|%p|%p|BRANCH\n", pattern, ptr));
817 : 120524873 : LASTMARK_SAVE();
818 [ + + ]: 120524873 : if (state->repeat)
819 [ + + + + : 6139221 : MARK_PUSH(ctx->lastmark);
- + + - ]
820 [ + + ]: 1037559310 : for (; pattern[0]; pattern += pattern[0]) {
821 [ + + + + ]: 933685370 : if (pattern[1] == SRE_OP_LITERAL &&
822 : 741394339 : (ptr >= end ||
823 [ + + ]: 741394339 : (SRE_CODE) *ptr != pattern[2]))
824 : 731049417 : continue;
825 [ + + + + ]: 202635953 : if (pattern[1] == SRE_OP_IN &&
826 [ + + ]: 45047231 : (ptr >= end ||
827 : 45047231 : !SRE(charset)(state, pattern + 3,
828 : 45044667 : (SRE_CODE) *ptr)))
829 : 43343244 : continue;
830 : 159292709 : state->ptr = ptr;
831 [ + + - + : 159292709 : DO_JUMP(JUMP_BRANCH, jump_branch, pattern+1);
+ - ]
832 [ + + ]: 159292709 : if (ret) {
833 [ + + ]: 16650933 : if (state->repeat)
834 [ + + ]: 23173 : MARK_POP_DISCARD(ctx->lastmark);
835 [ - + ]: 16650933 : RETURN_ON_ERROR(ret);
836 : 16650933 : RETURN_SUCCESS;
837 : : }
838 [ + + ]: 142641776 : if (state->repeat)
839 [ + + ]: 2604335 : MARK_POP_KEEP(ctx->lastmark);
840 : 142641776 : LASTMARK_RESTORE();
841 : : }
842 [ + + ]: 103873940 : if (state->repeat)
843 [ + + ]: 6116048 : MARK_POP_DISCARD(ctx->lastmark);
844 : 103873940 : RETURN_FAILURE;
845 : :
846 : 29374618 : TARGET(SRE_OP_REPEAT_ONE):
847 : : /* match repeated sequence (maximizing regexp) */
848 : :
849 : : /* this operator only works if the repeated item is
850 : : exactly one character wide, and we're not already
851 : : collecting backtracking points. for other cases,
852 : : use the MAX_REPEAT operator */
853 : :
854 : : /* <REPEAT_ONE> <skip> <1=min> <2=max> item <SUCCESS> tail */
855 : :
856 : : TRACE(("|%p|%p|REPEAT_ONE %d %d\n", pattern, ptr,
857 : : pattern[1], pattern[2]));
858 : :
859 [ + + ]: 29374618 : if ((Py_ssize_t) pattern[1] > end - ptr)
860 : 11869 : RETURN_FAILURE; /* cannot match */
861 : :
862 : 29362749 : state->ptr = ptr;
863 : :
864 : 29362749 : ret = SRE(count)(state, pattern+3, pattern[2]);
865 [ - + ]: 29362749 : RETURN_ON_ERROR(ret);
866 : 29362749 : DATA_LOOKUP_AT(SRE(match_context), ctx, ctx_pos);
867 : 29362749 : ctx->count = ret;
868 : 29362749 : ptr += ctx->count;
869 : :
870 : : /* when we arrive here, count contains the number of
871 : : matches, and ptr points to the tail of the target
872 : : string. check if the rest of the pattern matches,
873 : : and backtrack if not. */
874 : :
875 [ + + ]: 29362749 : if (ctx->count < (Py_ssize_t) pattern[1])
876 : 5858499 : RETURN_FAILURE;
877 : :
878 [ + + ]: 23504250 : if (pattern[pattern[0]] == SRE_OP_SUCCESS &&
879 [ + + ]: 299138 : ptr == state->end &&
880 [ + + + + : 133222 : !(ctx->toplevel && state->must_advance && ptr == state->start))
- + ]
881 : : {
882 : : /* tail is empty. we're finished */
883 : 129543 : state->ptr = ptr;
884 : 129543 : RETURN_SUCCESS;
885 : : }
886 : :
887 : 23374707 : LASTMARK_SAVE();
888 [ + + ]: 23374707 : if (state->repeat)
889 [ + + + + : 4508921 : MARK_PUSH(ctx->lastmark);
- + + - ]
890 : :
891 [ + + ]: 23374707 : if (pattern[pattern[0]] == SRE_OP_LITERAL) {
892 : : /* tail starts with a literal. skip positions where
893 : : the rest of the pattern cannot possibly match */
894 : 7474749 : ctx->u.chr = pattern[pattern[0]+1];
895 : : for (;;) {
896 [ + + + + ]: 18759872 : while (ctx->count >= (Py_ssize_t) pattern[1] &&
897 [ + + ]: 12112698 : (ptr >= end || *ptr != ctx->u.chr)) {
898 : 11227877 : ptr--;
899 : 11227877 : ctx->count--;
900 : : }
901 [ + + ]: 7531995 : if (ctx->count < (Py_ssize_t) pattern[1])
902 : 6635829 : break;
903 : 896166 : state->ptr = ptr;
904 [ + + - + : 896166 : DO_JUMP(JUMP_REPEAT_ONE_1, jump_repeat_one_1,
+ - ]
905 : : pattern+pattern[0]);
906 [ + + ]: 896166 : if (ret) {
907 [ + + ]: 838920 : if (state->repeat)
908 [ + + ]: 12313 : MARK_POP_DISCARD(ctx->lastmark);
909 [ - + ]: 838920 : RETURN_ON_ERROR(ret);
910 : 838920 : RETURN_SUCCESS;
911 : : }
912 [ + + ]: 57246 : if (state->repeat)
913 [ + + ]: 389 : MARK_POP_KEEP(ctx->lastmark);
914 : 57246 : LASTMARK_RESTORE();
915 : :
916 : 57246 : ptr--;
917 : 57246 : ctx->count--;
918 : : }
919 [ + + ]: 6635829 : if (state->repeat)
920 [ + + ]: 56014 : MARK_POP_DISCARD(ctx->lastmark);
921 : : } else {
922 : : /* general case */
923 [ + + ]: 30273115 : while (ctx->count >= (Py_ssize_t) pattern[1]) {
924 : 25668795 : state->ptr = ptr;
925 [ + + - + : 25668795 : DO_JUMP(JUMP_REPEAT_ONE_2, jump_repeat_one_2,
+ - ]
926 : : pattern+pattern[0]);
927 [ + + ]: 25668795 : if (ret) {
928 [ + + ]: 11295638 : if (state->repeat)
929 [ + + ]: 459727 : MARK_POP_DISCARD(ctx->lastmark);
930 [ - + ]: 11295638 : RETURN_ON_ERROR(ret);
931 : 11295638 : RETURN_SUCCESS;
932 : : }
933 [ + + ]: 14373157 : if (state->repeat)
934 [ + + ]: 7479411 : MARK_POP_KEEP(ctx->lastmark);
935 : 14373157 : LASTMARK_RESTORE();
936 : :
937 : 14373157 : ptr--;
938 : 14373157 : ctx->count--;
939 : : }
940 [ + + ]: 4604320 : if (state->repeat)
941 [ + + ]: 3980867 : MARK_POP_DISCARD(ctx->lastmark);
942 : : }
943 : 11240149 : RETURN_FAILURE;
944 : :
945 : 140052 : TARGET(SRE_OP_MIN_REPEAT_ONE):
946 : : /* match repeated sequence (minimizing regexp) */
947 : :
948 : : /* this operator only works if the repeated item is
949 : : exactly one character wide, and we're not already
950 : : collecting backtracking points. for other cases,
951 : : use the MIN_REPEAT operator */
952 : :
953 : : /* <MIN_REPEAT_ONE> <skip> <1=min> <2=max> item <SUCCESS> tail */
954 : :
955 : : TRACE(("|%p|%p|MIN_REPEAT_ONE %d %d\n", pattern, ptr,
956 : : pattern[1], pattern[2]));
957 : :
958 [ + + ]: 140052 : if ((Py_ssize_t) pattern[1] > end - ptr)
959 : 4 : RETURN_FAILURE; /* cannot match */
960 : :
961 : 140048 : state->ptr = ptr;
962 : :
963 [ + + ]: 140048 : if (pattern[1] == 0)
964 : 133273 : ctx->count = 0;
965 : : else {
966 : : /* count using pattern min as the maximum */
967 : 6775 : ret = SRE(count)(state, pattern+3, pattern[1]);
968 [ - + ]: 6775 : RETURN_ON_ERROR(ret);
969 : 6775 : DATA_LOOKUP_AT(SRE(match_context), ctx, ctx_pos);
970 [ + + ]: 6775 : if (ret < (Py_ssize_t) pattern[1])
971 : : /* didn't match minimum number of times */
972 : 2 : RETURN_FAILURE;
973 : : /* advance past minimum matches of repeat */
974 : 6773 : ctx->count = ret;
975 : 6773 : ptr += ctx->count;
976 : : }
977 : :
978 [ + + ]: 140046 : if (pattern[pattern[0]] == SRE_OP_SUCCESS &&
979 [ + - ]: 4 : !(ctx->toplevel &&
980 [ + + - + ]: 4 : ((state->match_all && ptr != state->end) ||
981 [ - + - - ]: 2 : (state->must_advance && ptr == state->start))))
982 : : {
983 : : /* tail is empty. we're finished */
984 : 2 : state->ptr = ptr;
985 : 2 : RETURN_SUCCESS;
986 : :
987 : : } else {
988 : : /* general case */
989 : 140044 : LASTMARK_SAVE();
990 [ + + ]: 140044 : if (state->repeat)
991 [ + + - + : 78 : MARK_PUSH(ctx->lastmark);
- - - - ]
992 : :
993 : 140044 : while ((Py_ssize_t)pattern[2] == SRE_MAXREPEAT
994 [ + + + + ]: 586107 : || ctx->count <= (Py_ssize_t)pattern[2]) {
995 : 586104 : state->ptr = ptr;
996 [ - + - - : 586104 : DO_JUMP(JUMP_MIN_REPEAT_ONE,jump_min_repeat_one,
- - ]
997 : : pattern+pattern[0]);
998 [ + + ]: 586104 : if (ret) {
999 [ + + ]: 138432 : if (state->repeat)
1000 [ + + ]: 70 : MARK_POP_DISCARD(ctx->lastmark);
1001 [ - + ]: 138432 : RETURN_ON_ERROR(ret);
1002 : 138432 : RETURN_SUCCESS;
1003 : : }
1004 [ + + ]: 447672 : if (state->repeat)
1005 [ + + ]: 3031 : MARK_POP_KEEP(ctx->lastmark);
1006 : 447672 : LASTMARK_RESTORE();
1007 : :
1008 : 447672 : state->ptr = ptr;
1009 : 447672 : ret = SRE(count)(state, pattern+3, 1);
1010 [ - + ]: 447672 : RETURN_ON_ERROR(ret);
1011 : 447672 : DATA_LOOKUP_AT(SRE(match_context), ctx, ctx_pos);
1012 [ + + ]: 447672 : if (ret == 0)
1013 : 1609 : break;
1014 : : assert(ret == 1);
1015 : 446063 : ptr++;
1016 : 446063 : ctx->count++;
1017 : : }
1018 [ + + ]: 1612 : if (state->repeat)
1019 [ + - ]: 8 : MARK_POP_DISCARD(ctx->lastmark);
1020 : : }
1021 : 1612 : RETURN_FAILURE;
1022 : :
1023 : 46 : TARGET(SRE_OP_POSSESSIVE_REPEAT_ONE):
1024 : : /* match repeated sequence (maximizing regexp) without
1025 : : backtracking */
1026 : :
1027 : : /* this operator only works if the repeated item is
1028 : : exactly one character wide, and we're not already
1029 : : collecting backtracking points. for other cases,
1030 : : use the MAX_REPEAT operator */
1031 : :
1032 : : /* <POSSESSIVE_REPEAT_ONE> <skip> <1=min> <2=max> item <SUCCESS>
1033 : : tail */
1034 : :
1035 : : TRACE(("|%p|%p|POSSESSIVE_REPEAT_ONE %d %d\n", pattern,
1036 : : ptr, pattern[1], pattern[2]));
1037 : :
1038 [ + + ]: 46 : if (ptr + pattern[1] > end) {
1039 : 2 : RETURN_FAILURE; /* cannot match */
1040 : : }
1041 : :
1042 : 44 : state->ptr = ptr;
1043 : :
1044 : 44 : ret = SRE(count)(state, pattern + 3, pattern[2]);
1045 [ - + ]: 44 : RETURN_ON_ERROR(ret);
1046 : 44 : DATA_LOOKUP_AT(SRE(match_context), ctx, ctx_pos);
1047 : 44 : ctx->count = ret;
1048 : 44 : ptr += ctx->count;
1049 : :
1050 : : /* when we arrive here, count contains the number of
1051 : : matches, and ptr points to the tail of the target
1052 : : string. check if the rest of the pattern matches,
1053 : : and fail if not. */
1054 : :
1055 : : /* Test for not enough repetitions in match */
1056 [ + + ]: 44 : if (ctx->count < (Py_ssize_t) pattern[1]) {
1057 : 4 : RETURN_FAILURE;
1058 : : }
1059 : :
1060 : : /* Update the pattern to point to the next op code */
1061 : 40 : pattern += pattern[0];
1062 : :
1063 : : /* Let the tail be evaluated separately and consider this
1064 : : match successful. */
1065 [ + + ]: 40 : if (*pattern == SRE_OP_SUCCESS &&
1066 [ + + ]: 27 : ptr == state->end &&
1067 [ + + + + : 11 : !(ctx->toplevel && state->must_advance && ptr == state->start))
- + ]
1068 : : {
1069 : : /* tail is empty. we're finished */
1070 : 9 : state->ptr = ptr;
1071 : 9 : RETURN_SUCCESS;
1072 : : }
1073 : :
1074 : : /* Attempt to match the rest of the string */
1075 [ - + - - ]: 31 : DISPATCH;
1076 : :
1077 : 9692797 : TARGET(SRE_OP_REPEAT):
1078 : : /* create repeat context. all the hard work is done
1079 : : by the UNTIL operator (MAX_UNTIL, MIN_UNTIL) */
1080 : : /* <REPEAT> <skip> <1=min> <2=max>
1081 : : <3=repeat_index> item <UNTIL> tail */
1082 : : TRACE(("|%p|%p|REPEAT %d %d\n", pattern, ptr,
1083 : : pattern[1], pattern[2]));
1084 : :
1085 : : /* install new repeat context */
1086 : : /* TODO(https://github.com/python/cpython/issues/67877): Fix this
1087 : : * potential memory leak. */
1088 : 9692797 : ctx->u.rep = (SRE_REPEAT*) PyObject_Malloc(sizeof(*ctx->u.rep));
1089 [ - + ]: 9692797 : if (!ctx->u.rep) {
1090 : : PyErr_NoMemory();
1091 : 0 : RETURN_FAILURE;
1092 : : }
1093 : 9692797 : ctx->u.rep->count = -1;
1094 : 9692797 : ctx->u.rep->pattern = pattern;
1095 : 9692797 : ctx->u.rep->prev = state->repeat;
1096 : 9692797 : ctx->u.rep->last_ptr = NULL;
1097 : 9692797 : state->repeat = ctx->u.rep;
1098 : :
1099 : 9692797 : state->ptr = ptr;
1100 [ + + - + : 9692797 : DO_JUMP(JUMP_REPEAT, jump_repeat, pattern+pattern[0]);
+ - ]
1101 : 9692797 : state->repeat = ctx->u.rep->prev;
1102 : 9692797 : PyObject_Free(ctx->u.rep);
1103 : :
1104 [ + + ]: 9692797 : if (ret) {
1105 [ - + ]: 1196961 : RETURN_ON_ERROR(ret);
1106 : 1196961 : RETURN_SUCCESS;
1107 : : }
1108 : 8495836 : RETURN_FAILURE;
1109 : :
1110 : 13218839 : TARGET(SRE_OP_MAX_UNTIL):
1111 : : /* maximizing repeat */
1112 : : /* <REPEAT> <skip> <1=min> <2=max> item <MAX_UNTIL> tail */
1113 : :
1114 : : /* FIXME: we probably need to deal with zero-width
1115 : : matches in here... */
1116 : :
1117 : 13218839 : ctx->u.rep = state->repeat;
1118 [ - + ]: 13218839 : if (!ctx->u.rep)
1119 : 0 : RETURN_ERROR(SRE_ERROR_STATE);
1120 : :
1121 : 13218839 : state->ptr = ptr;
1122 : :
1123 : 13218839 : ctx->count = ctx->u.rep->count+1;
1124 : :
1125 : : TRACE(("|%p|%p|MAX_UNTIL %zd\n", pattern,
1126 : : ptr, ctx->count));
1127 : :
1128 [ + + ]: 13218839 : if (ctx->count < (Py_ssize_t) ctx->u.rep->pattern[1]) {
1129 : : /* not enough matches */
1130 : 26950 : ctx->u.rep->count = ctx->count;
1131 [ - + - - : 26950 : DO_JUMP(JUMP_MAX_UNTIL_1, jump_max_until_1,
- - ]
1132 : : ctx->u.rep->pattern+3);
1133 [ + + ]: 26950 : if (ret) {
1134 [ - + ]: 4454 : RETURN_ON_ERROR(ret);
1135 : 4454 : RETURN_SUCCESS;
1136 : : }
1137 : 22496 : ctx->u.rep->count = ctx->count-1;
1138 : 22496 : state->ptr = ptr;
1139 : 22496 : RETURN_FAILURE;
1140 : : }
1141 : :
1142 [ + + ]: 13191889 : if ((ctx->count < (Py_ssize_t) ctx->u.rep->pattern[2] ||
1143 [ - + ]: 2505778 : ctx->u.rep->pattern[2] == SRE_MAXREPEAT) &&
1144 [ + + ]: 10686111 : state->ptr != ctx->u.rep->last_ptr) {
1145 : : /* we may have enough matches, but if we can
1146 : : match another item, do so */
1147 : 10686096 : ctx->u.rep->count = ctx->count;
1148 : 10686096 : LASTMARK_SAVE();
1149 [ + + + + : 10686096 : MARK_PUSH(ctx->lastmark);
- + + - ]
1150 : : /* zero-width match protection */
1151 [ + + - + : 10686096 : DATA_PUSH(&ctx->u.rep->last_ptr);
+ - ]
1152 : 10686096 : ctx->u.rep->last_ptr = state->ptr;
1153 [ + + - + : 10686096 : DO_JUMP(JUMP_MAX_UNTIL_2, jump_max_until_2,
+ - ]
1154 : : ctx->u.rep->pattern+3);
1155 : 10686096 : DATA_POP(&ctx->u.rep->last_ptr);
1156 [ + + ]: 10686096 : if (ret) {
1157 [ + + ]: 563513 : MARK_POP_DISCARD(ctx->lastmark);
1158 [ - + ]: 563513 : RETURN_ON_ERROR(ret);
1159 : 563513 : RETURN_SUCCESS;
1160 : : }
1161 [ + + ]: 10122583 : MARK_POP(ctx->lastmark);
1162 : 10122583 : LASTMARK_RESTORE();
1163 : 10122583 : ctx->u.rep->count = ctx->count-1;
1164 : 10122583 : state->ptr = ptr;
1165 : : }
1166 : :
1167 : : /* cannot match more repeated items here. make sure the
1168 : : tail matches */
1169 : 12628376 : state->repeat = ctx->u.rep->prev;
1170 [ + + - + : 12628376 : DO_JUMP(JUMP_MAX_UNTIL_3, jump_max_until_3, pattern);
+ - ]
1171 : 12628376 : state->repeat = ctx->u.rep; // restore repeat before return
1172 : :
1173 [ - + + + ]: 12628376 : RETURN_ON_SUCCESS(ret);
1174 : 11431465 : state->ptr = ptr;
1175 : 11431465 : RETURN_FAILURE;
1176 : :
1177 : 70135 : TARGET(SRE_OP_MIN_UNTIL):
1178 : : /* minimizing repeat */
1179 : : /* <REPEAT> <skip> <1=min> <2=max> item <MIN_UNTIL> tail */
1180 : :
1181 : 70135 : ctx->u.rep = state->repeat;
1182 [ - + ]: 70135 : if (!ctx->u.rep)
1183 : 0 : RETURN_ERROR(SRE_ERROR_STATE);
1184 : :
1185 : 70135 : state->ptr = ptr;
1186 : :
1187 : 70135 : ctx->count = ctx->u.rep->count+1;
1188 : :
1189 : : TRACE(("|%p|%p|MIN_UNTIL %zd %p\n", pattern,
1190 : : ptr, ctx->count, ctx->u.rep->pattern));
1191 : :
1192 [ + + ]: 70135 : if (ctx->count < (Py_ssize_t) ctx->u.rep->pattern[1]) {
1193 : : /* not enough matches */
1194 : 32 : ctx->u.rep->count = ctx->count;
1195 [ - + - - : 32 : DO_JUMP(JUMP_MIN_UNTIL_1, jump_min_until_1,
- - ]
1196 : : ctx->u.rep->pattern+3);
1197 [ + + ]: 32 : if (ret) {
1198 [ - + ]: 26 : RETURN_ON_ERROR(ret);
1199 : 26 : RETURN_SUCCESS;
1200 : : }
1201 : 6 : ctx->u.rep->count = ctx->count-1;
1202 : 6 : state->ptr = ptr;
1203 : 6 : RETURN_FAILURE;
1204 : : }
1205 : :
1206 : : /* see if the tail matches */
1207 : 70103 : state->repeat = ctx->u.rep->prev;
1208 : :
1209 : 70103 : LASTMARK_SAVE();
1210 [ + + ]: 70103 : if (state->repeat)
1211 [ + + - + : 32 : MARK_PUSH(ctx->lastmark);
- - - - ]
1212 : :
1213 [ + + - + : 70103 : DO_JUMP(JUMP_MIN_UNTIL_2, jump_min_until_2, pattern);
+ - ]
1214 : 70103 : SRE_REPEAT *repeat_of_tail = state->repeat;
1215 : 70103 : state->repeat = ctx->u.rep; // restore repeat before return
1216 : :
1217 [ + + ]: 70103 : if (ret) {
1218 [ + + ]: 50 : if (repeat_of_tail)
1219 [ + + ]: 16 : MARK_POP_DISCARD(ctx->lastmark);
1220 [ - + ]: 50 : RETURN_ON_ERROR(ret);
1221 : 50 : RETURN_SUCCESS;
1222 : : }
1223 [ + + ]: 70053 : if (repeat_of_tail)
1224 [ + + ]: 16 : MARK_POP(ctx->lastmark);
1225 : 70053 : LASTMARK_RESTORE();
1226 : :
1227 : 70053 : state->ptr = ptr;
1228 : :
1229 [ + + ]: 70053 : if ((ctx->count >= (Py_ssize_t) ctx->u.rep->pattern[2]
1230 [ - + ]: 2 : && ctx->u.rep->pattern[2] != SRE_MAXREPEAT) ||
1231 [ + + ]: 70051 : state->ptr == ctx->u.rep->last_ptr)
1232 : 5 : RETURN_FAILURE;
1233 : :
1234 : 70048 : ctx->u.rep->count = ctx->count;
1235 : : /* zero-width match protection */
1236 [ - + - - : 70048 : DATA_PUSH(&ctx->u.rep->last_ptr);
- - ]
1237 : 70048 : ctx->u.rep->last_ptr = state->ptr;
1238 [ - + - - : 70048 : DO_JUMP(JUMP_MIN_UNTIL_3,jump_min_until_3,
- - ]
1239 : : ctx->u.rep->pattern+3);
1240 : 70048 : DATA_POP(&ctx->u.rep->last_ptr);
1241 [ + + ]: 70048 : if (ret) {
1242 [ - + ]: 70030 : RETURN_ON_ERROR(ret);
1243 : 70030 : RETURN_SUCCESS;
1244 : : }
1245 : 18 : ctx->u.rep->count = ctx->count-1;
1246 : 18 : state->ptr = ptr;
1247 : 18 : RETURN_FAILURE;
1248 : :
1249 : 37 : TARGET(SRE_OP_POSSESSIVE_REPEAT):
1250 : : /* create possessive repeat contexts. */
1251 : : /* <POSSESSIVE_REPEAT> <skip> <1=min> <2=max> pattern
1252 : : <SUCCESS> tail */
1253 : : TRACE(("|%p|%p|POSSESSIVE_REPEAT %d %d\n", pattern,
1254 : : ptr, pattern[1], pattern[2]));
1255 : :
1256 : : /* Set the global Input pointer to this context's Input
1257 : : pointer */
1258 : 37 : state->ptr = ptr;
1259 : :
1260 : : /* Initialize Count to 0 */
1261 : 37 : ctx->count = 0;
1262 : :
1263 : : /* Check for minimum required matches. */
1264 [ + + ]: 57 : while (ctx->count < (Py_ssize_t)pattern[1]) {
1265 : : /* not enough matches */
1266 [ - + - - : 20 : DO_JUMP0(JUMP_POSS_REPEAT_1, jump_poss_repeat_1,
- - ]
1267 : : &pattern[3]);
1268 [ + - ]: 20 : if (ret) {
1269 [ - + ]: 20 : RETURN_ON_ERROR(ret);
1270 : 20 : ctx->count++;
1271 : : }
1272 : : else {
1273 : 0 : state->ptr = ptr;
1274 : 0 : RETURN_FAILURE;
1275 : : }
1276 : : }
1277 : :
1278 : : /* Clear the context's Input stream pointer so that it
1279 : : doesn't match the global state so that the while loop can
1280 : : be entered. */
1281 : 37 : ptr = NULL;
1282 : :
1283 : : /* Keep trying to parse the <pattern> sub-pattern until the
1284 : : end is reached, creating a new context each time. */
1285 : 37 : while ((ctx->count < (Py_ssize_t)pattern[2] ||
1286 [ + + - + ]: 64 : (Py_ssize_t)pattern[2] == SRE_MAXREPEAT) &&
1287 [ + + ]: 53 : state->ptr != ptr) {
1288 : : /* Save the Capture Group Marker state into the current
1289 : : Context and back up the current highest number
1290 : : Capture Group marker. */
1291 : 52 : LASTMARK_SAVE();
1292 [ + + - + : 52 : MARK_PUSH(ctx->lastmark);
- - - - ]
1293 : :
1294 : : /* zero-width match protection */
1295 : : /* Set the context's Input Stream pointer to be the
1296 : : current Input Stream pointer from the global
1297 : : state. When the loop reaches the next iteration,
1298 : : the context will then store the last known good
1299 : : position with the global state holding the Input
1300 : : Input Stream position that has been updated with
1301 : : the most recent match. Thus, if state's Input
1302 : : stream remains the same as the one stored in the
1303 : : current Context, we know we have successfully
1304 : : matched an empty string and that all subsequent
1305 : : matches will also be the empty string until the
1306 : : maximum number of matches are counted, and because
1307 : : of this, we could immediately stop at that point and
1308 : : consider this match successful. */
1309 : 52 : ptr = state->ptr;
1310 : :
1311 : : /* We have not reached the maximin matches, so try to
1312 : : match once more. */
1313 [ - + - - : 52 : DO_JUMP0(JUMP_POSS_REPEAT_2, jump_poss_repeat_2,
- - ]
1314 : : &pattern[3]);
1315 : :
1316 : : /* Check to see if the last attempted match
1317 : : succeeded. */
1318 [ + + ]: 52 : if (ret) {
1319 : : /* Drop the saved highest number Capture Group
1320 : : marker saved above and use the newly updated
1321 : : value. */
1322 [ + + ]: 27 : MARK_POP_DISCARD(ctx->lastmark);
1323 [ - + ]: 27 : RETURN_ON_ERROR(ret);
1324 : :
1325 : : /* Success, increment the count. */
1326 : 27 : ctx->count++;
1327 : : }
1328 : : /* Last attempted match failed. */
1329 : : else {
1330 : : /* Restore the previously saved highest number
1331 : : Capture Group marker since the last iteration
1332 : : did not match, then restore that to the global
1333 : : state. */
1334 [ + + ]: 25 : MARK_POP(ctx->lastmark);
1335 : 25 : LASTMARK_RESTORE();
1336 : :
1337 : : /* We have sufficient matches, so exit loop. */
1338 : 25 : break;
1339 : : }
1340 : : }
1341 : :
1342 : : /* Evaluate Tail */
1343 : : /* Jump to end of pattern indicated by skip, and then skip
1344 : : the SUCCESS op code that follows it. */
1345 : 37 : pattern += pattern[0] + 1;
1346 : 37 : ptr = state->ptr;
1347 [ - + - - ]: 37 : DISPATCH;
1348 : :
1349 : 219 : TARGET(SRE_OP_ATOMIC_GROUP):
1350 : : /* Atomic Group Sub Pattern */
1351 : : /* <ATOMIC_GROUP> <skip> pattern <SUCCESS> tail */
1352 : : TRACE(("|%p|%p|ATOMIC_GROUP\n", pattern, ptr));
1353 : :
1354 : : /* Set the global Input pointer to this context's Input
1355 : : pointer */
1356 : 219 : state->ptr = ptr;
1357 : :
1358 : : /* Evaluate the Atomic Group in a new context, terminating
1359 : : when the end of the group, represented by a SUCCESS op
1360 : : code, is reached. */
1361 : : /* Group Pattern begins at an offset of 1 code. */
1362 [ - + - - : 219 : DO_JUMP0(JUMP_ATOMIC_GROUP, jump_atomic_group,
- - ]
1363 : : &pattern[1]);
1364 : :
1365 : : /* Test Exit Condition */
1366 [ - + ]: 219 : RETURN_ON_ERROR(ret);
1367 : :
1368 [ + + ]: 219 : if (ret == 0) {
1369 : : /* Atomic Group failed to Match. */
1370 : 67 : state->ptr = ptr;
1371 : 67 : RETURN_FAILURE;
1372 : : }
1373 : :
1374 : : /* Evaluate Tail */
1375 : : /* Jump to end of pattern indicated by skip, and then skip
1376 : : the SUCCESS op code that follows it. */
1377 : 152 : pattern += pattern[0];
1378 : 152 : ptr = state->ptr;
1379 [ - + - - ]: 152 : DISPATCH;
1380 : :
1381 : 2195 : TARGET(SRE_OP_GROUPREF):
1382 : : /* match backreference */
1383 : : TRACE(("|%p|%p|GROUPREF %d\n", pattern,
1384 : : ptr, pattern[0]));
1385 : : {
1386 : 2195 : int groupref = pattern[0] * 2;
1387 [ - + ]: 2195 : if (groupref >= state->lastmark) {
1388 : 0 : RETURN_FAILURE;
1389 : : } else {
1390 : 2195 : SRE_CHAR* p = (SRE_CHAR*) state->mark[groupref];
1391 : 2195 : SRE_CHAR* e = (SRE_CHAR*) state->mark[groupref+1];
1392 [ + + + - : 2195 : if (!p || !e || e < p)
- + ]
1393 : 6 : RETURN_FAILURE;
1394 [ + + ]: 2826 : while (p < e) {
1395 [ + + + + ]: 2491 : if (ptr >= end || *ptr != *p)
1396 : 1854 : RETURN_FAILURE;
1397 : 637 : p++;
1398 : 637 : ptr++;
1399 : : }
1400 : : }
1401 : : }
1402 : 335 : pattern++;
1403 [ - + - - ]: 335 : DISPATCH;
1404 : :
1405 : 6 : TARGET(SRE_OP_GROUPREF_IGNORE):
1406 : : /* match backreference */
1407 : : TRACE(("|%p|%p|GROUPREF_IGNORE %d\n", pattern,
1408 : : ptr, pattern[0]));
1409 : : {
1410 : 6 : int groupref = pattern[0] * 2;
1411 [ - + ]: 6 : if (groupref >= state->lastmark) {
1412 : 0 : RETURN_FAILURE;
1413 : : } else {
1414 : 6 : SRE_CHAR* p = (SRE_CHAR*) state->mark[groupref];
1415 : 6 : SRE_CHAR* e = (SRE_CHAR*) state->mark[groupref+1];
1416 [ + - + - : 6 : if (!p || !e || e < p)
- + ]
1417 : 0 : RETURN_FAILURE;
1418 [ + + ]: 13 : while (p < e) {
1419 [ + + + + ]: 19 : if (ptr >= end ||
1420 : 9 : sre_lower_ascii(*ptr) != sre_lower_ascii(*p))
1421 : 3 : RETURN_FAILURE;
1422 : 7 : p++;
1423 : 7 : ptr++;
1424 : : }
1425 : : }
1426 : : }
1427 : 3 : pattern++;
1428 [ - + - - ]: 3 : DISPATCH;
1429 : :
1430 : 101 : TARGET(SRE_OP_GROUPREF_UNI_IGNORE):
1431 : : /* match backreference */
1432 : : TRACE(("|%p|%p|GROUPREF_UNI_IGNORE %d\n", pattern,
1433 : : ptr, pattern[0]));
1434 : : {
1435 : 101 : int groupref = pattern[0] * 2;
1436 [ - + ]: 101 : if (groupref >= state->lastmark) {
1437 : 0 : RETURN_FAILURE;
1438 : : } else {
1439 : 101 : SRE_CHAR* p = (SRE_CHAR*) state->mark[groupref];
1440 : 101 : SRE_CHAR* e = (SRE_CHAR*) state->mark[groupref+1];
1441 [ + - + - : 101 : if (!p || !e || e < p)
- + ]
1442 : 0 : RETURN_FAILURE;
1443 [ + + ]: 198 : while (p < e) {
1444 [ + + + + ]: 239 : if (ptr >= end ||
1445 : 111 : sre_lower_unicode(*ptr) != sre_lower_unicode(*p))
1446 : 31 : RETURN_FAILURE;
1447 : 97 : p++;
1448 : 97 : ptr++;
1449 : : }
1450 : : }
1451 : : }
1452 : 70 : pattern++;
1453 [ - + - - ]: 70 : DISPATCH;
1454 : :
1455 : 6 : TARGET(SRE_OP_GROUPREF_LOC_IGNORE):
1456 : : /* match backreference */
1457 : : TRACE(("|%p|%p|GROUPREF_LOC_IGNORE %d\n", pattern,
1458 : : ptr, pattern[0]));
1459 : : {
1460 : 6 : int groupref = pattern[0] * 2;
1461 [ - + ]: 6 : if (groupref >= state->lastmark) {
1462 : 0 : RETURN_FAILURE;
1463 : : } else {
1464 : 6 : SRE_CHAR* p = (SRE_CHAR*) state->mark[groupref];
1465 : 6 : SRE_CHAR* e = (SRE_CHAR*) state->mark[groupref+1];
1466 [ + - + - : 6 : if (!p || !e || e < p)
- + ]
1467 : 0 : RETURN_FAILURE;
1468 [ + + ]: 13 : while (p < e) {
1469 [ + + + + ]: 19 : if (ptr >= end ||
1470 : 9 : sre_lower_locale(*ptr) != sre_lower_locale(*p))
1471 : 3 : RETURN_FAILURE;
1472 : 7 : p++;
1473 : 7 : ptr++;
1474 : : }
1475 : : }
1476 : : }
1477 : 3 : pattern++;
1478 [ - + - - ]: 3 : DISPATCH;
1479 : :
1480 : 30 : TARGET(SRE_OP_GROUPREF_EXISTS):
1481 : : TRACE(("|%p|%p|GROUPREF_EXISTS %d\n", pattern,
1482 : : ptr, pattern[0]));
1483 : : /* <GROUPREF_EXISTS> <group> <skip> codeyes <JUMP> codeno ... */
1484 : : {
1485 : 30 : int groupref = pattern[0] * 2;
1486 [ + + ]: 30 : if (groupref >= state->lastmark) {
1487 : 8 : pattern += pattern[1];
1488 [ - + - - ]: 8 : DISPATCH;
1489 : : } else {
1490 : 22 : SRE_CHAR* p = (SRE_CHAR*) state->mark[groupref];
1491 : 22 : SRE_CHAR* e = (SRE_CHAR*) state->mark[groupref+1];
1492 [ + + + - : 22 : if (!p || !e || e < p) {
- + ]
1493 : 7 : pattern += pattern[1];
1494 [ - + - - ]: 7 : DISPATCH;
1495 : : }
1496 : : }
1497 : : }
1498 : 15 : pattern += 2;
1499 [ - + - - ]: 15 : DISPATCH;
1500 : :
1501 : 306271 : TARGET(SRE_OP_ASSERT):
1502 : : /* assert subpattern */
1503 : : /* <ASSERT> <skip> <back> <pattern> */
1504 : : TRACE(("|%p|%p|ASSERT %d\n", pattern,
1505 : : ptr, pattern[1]));
1506 [ + + ]: 306271 : if (ptr - (SRE_CHAR *)state->beginning < (Py_ssize_t)pattern[1])
1507 : 2862 : RETURN_FAILURE;
1508 : 303409 : state->ptr = ptr - pattern[1];
1509 [ + + - + : 303409 : DO_JUMP0(JUMP_ASSERT, jump_assert, pattern+2);
+ - ]
1510 [ - + + + ]: 303409 : RETURN_ON_FAILURE(ret);
1511 : 222649 : pattern += pattern[0];
1512 [ - + - - ]: 222649 : DISPATCH;
1513 : :
1514 : 301322 : TARGET(SRE_OP_ASSERT_NOT):
1515 : : /* assert not subpattern */
1516 : : /* <ASSERT_NOT> <skip> <back> <pattern> */
1517 : : TRACE(("|%p|%p|ASSERT_NOT %d\n", pattern,
1518 : : ptr, pattern[1]));
1519 [ + + ]: 301322 : if (ptr - (SRE_CHAR *)state->beginning >= (Py_ssize_t)pattern[1]) {
1520 : 301119 : state->ptr = ptr - pattern[1];
1521 : 301119 : LASTMARK_SAVE();
1522 [ + + ]: 301119 : if (state->repeat)
1523 [ + + + + : 264828 : MARK_PUSH(ctx->lastmark);
- + + - ]
1524 : :
1525 [ + + - + : 301119 : DO_JUMP0(JUMP_ASSERT_NOT, jump_assert_not, pattern+2);
+ - ]
1526 [ + + ]: 301119 : if (ret) {
1527 [ + + ]: 25152 : if (state->repeat)
1528 [ + + ]: 22517 : MARK_POP_DISCARD(ctx->lastmark);
1529 [ - + ]: 25152 : RETURN_ON_ERROR(ret);
1530 : 25152 : RETURN_FAILURE;
1531 : : }
1532 [ + + ]: 275967 : if (state->repeat)
1533 [ + + ]: 242311 : MARK_POP(ctx->lastmark);
1534 : 275967 : LASTMARK_RESTORE();
1535 : : }
1536 : 276170 : pattern += pattern[0];
1537 [ + + - + ]: 276170 : DISPATCH;
1538 : :
1539 : 0 : TARGET(SRE_OP_FAILURE):
1540 : : /* immediate failure */
1541 : : TRACE(("|%p|%p|FAILURE\n", pattern, ptr));
1542 : 0 : RETURN_FAILURE;
1543 : :
1544 : : #if !USE_COMPUTED_GOTOS
1545 : : default:
1546 : : #endif
1547 : : // Also any unused opcodes:
1548 : 0 : TARGET(SRE_OP_RANGE_UNI_IGNORE):
1549 : 0 : TARGET(SRE_OP_SUBPATTERN):
1550 : 0 : TARGET(SRE_OP_RANGE):
1551 : 0 : TARGET(SRE_OP_NEGATE):
1552 : 0 : TARGET(SRE_OP_BIGCHARSET):
1553 : 0 : TARGET(SRE_OP_CHARSET):
1554 : : TRACE(("|%p|%p|UNKNOWN %d\n", pattern, ptr,
1555 : : pattern[-1]));
1556 : 0 : RETURN_ERROR(SRE_ERROR_ILLEGAL);
1557 : :
1558 : : }
1559 : :
1560 : 52011673 : exit:
1561 : 298204864 : ctx_pos = ctx->last_ctx_pos;
1562 : 298204864 : jump = ctx->jump;
1563 : 298204864 : DATA_POP_DISCARD(ctx);
1564 [ + + ]: 298204864 : if (ctx_pos == -1)
1565 : 77981869 : return ret;
1566 : 220222995 : DATA_LOOKUP_AT(SRE(match_context), ctx, ctx_pos);
1567 : :
1568 [ + + + + : 220222995 : switch (jump) {
+ + + + +
+ + + + +
+ + - - ]
1569 : 10686096 : case JUMP_MAX_UNTIL_2:
1570 : : TRACE(("|%p|%p|JUMP_MAX_UNTIL_2\n", pattern, ptr));
1571 : 10686096 : goto jump_max_until_2;
1572 : 12628376 : case JUMP_MAX_UNTIL_3:
1573 : : TRACE(("|%p|%p|JUMP_MAX_UNTIL_3\n", pattern, ptr));
1574 : 12628376 : goto jump_max_until_3;
1575 : 70103 : case JUMP_MIN_UNTIL_2:
1576 : : TRACE(("|%p|%p|JUMP_MIN_UNTIL_2\n", pattern, ptr));
1577 : 70103 : goto jump_min_until_2;
1578 : 70048 : case JUMP_MIN_UNTIL_3:
1579 : : TRACE(("|%p|%p|JUMP_MIN_UNTIL_3\n", pattern, ptr));
1580 : 70048 : goto jump_min_until_3;
1581 : 159292709 : case JUMP_BRANCH:
1582 : : TRACE(("|%p|%p|JUMP_BRANCH\n", pattern, ptr));
1583 : 159292709 : goto jump_branch;
1584 : 26950 : case JUMP_MAX_UNTIL_1:
1585 : : TRACE(("|%p|%p|JUMP_MAX_UNTIL_1\n", pattern, ptr));
1586 : 26950 : goto jump_max_until_1;
1587 : 32 : case JUMP_MIN_UNTIL_1:
1588 : : TRACE(("|%p|%p|JUMP_MIN_UNTIL_1\n", pattern, ptr));
1589 : 32 : goto jump_min_until_1;
1590 : 20 : case JUMP_POSS_REPEAT_1:
1591 : : TRACE(("|%p|%p|JUMP_POSS_REPEAT_1\n", pattern, ptr));
1592 : 20 : goto jump_poss_repeat_1;
1593 : 52 : case JUMP_POSS_REPEAT_2:
1594 : : TRACE(("|%p|%p|JUMP_POSS_REPEAT_2\n", pattern, ptr));
1595 : 52 : goto jump_poss_repeat_2;
1596 : 9692797 : case JUMP_REPEAT:
1597 : : TRACE(("|%p|%p|JUMP_REPEAT\n", pattern, ptr));
1598 : 9692797 : goto jump_repeat;
1599 : 896166 : case JUMP_REPEAT_ONE_1:
1600 : : TRACE(("|%p|%p|JUMP_REPEAT_ONE_1\n", pattern, ptr));
1601 : 896166 : goto jump_repeat_one_1;
1602 : 25668795 : case JUMP_REPEAT_ONE_2:
1603 : : TRACE(("|%p|%p|JUMP_REPEAT_ONE_2\n", pattern, ptr));
1604 : 25668795 : goto jump_repeat_one_2;
1605 : 586104 : case JUMP_MIN_REPEAT_ONE:
1606 : : TRACE(("|%p|%p|JUMP_MIN_REPEAT_ONE\n", pattern, ptr));
1607 : 586104 : goto jump_min_repeat_one;
1608 : 219 : case JUMP_ATOMIC_GROUP:
1609 : : TRACE(("|%p|%p|JUMP_ATOMIC_GROUP\n", pattern, ptr));
1610 : 219 : goto jump_atomic_group;
1611 : 303409 : case JUMP_ASSERT:
1612 : : TRACE(("|%p|%p|JUMP_ASSERT\n", pattern, ptr));
1613 : 303409 : goto jump_assert;
1614 : 301119 : case JUMP_ASSERT_NOT:
1615 : : TRACE(("|%p|%p|JUMP_ASSERT_NOT\n", pattern, ptr));
1616 : 301119 : goto jump_assert_not;
1617 : 0 : case JUMP_NONE:
1618 : : TRACE(("|%p|%p|RETURN %zd\n", pattern,
1619 : : ptr, ret));
1620 : 0 : break;
1621 : : }
1622 : :
1623 : 0 : return ret; /* should never get here */
1624 : : }
1625 : :
1626 : : /* need to reset capturing groups between two SRE(match) callings in loops */
1627 : : #define RESET_CAPTURE_GROUP() \
1628 : : do { state->lastmark = state->lastindex = -1; } while (0)
1629 : :
1630 : : LOCAL(Py_ssize_t)
1631 : 3095652 : SRE(search)(SRE_STATE* state, SRE_CODE* pattern)
1632 : : {
1633 : 3095652 : SRE_CHAR* ptr = (SRE_CHAR *)state->start;
1634 : 3095652 : SRE_CHAR* end = (SRE_CHAR *)state->end;
1635 : 3095652 : Py_ssize_t status = 0;
1636 : 3095652 : Py_ssize_t prefix_len = 0;
1637 : 3095652 : Py_ssize_t prefix_skip = 0;
1638 : 3095652 : SRE_CODE* prefix = NULL;
1639 : 3095652 : SRE_CODE* charset = NULL;
1640 : 3095652 : SRE_CODE* overlap = NULL;
1641 : 3095652 : int flags = 0;
1642 : :
1643 [ - + ]: 3095652 : if (ptr > end)
1644 : 0 : return 0;
1645 : :
1646 [ + - ]: 3095652 : if (pattern[0] == SRE_OP_INFO) {
1647 : : /* optimization info block */
1648 : : /* <INFO> <1=skip> <2=flags> <3=min> <4=max> <5=prefix info> */
1649 : :
1650 : 3095652 : flags = pattern[2];
1651 : :
1652 [ + + + + ]: 3095652 : if (pattern[3] && end - ptr < (Py_ssize_t)pattern[3]) {
1653 : : TRACE(("reject (got %u chars, need %u)\n",
1654 : : (unsigned int)(end - ptr), pattern[3]));
1655 : 861538 : return 0;
1656 : : }
1657 [ + + ]: 2234114 : if (pattern[3] > 1) {
1658 : : /* adjust end point (but make sure we leave at least one
1659 : : character in there, so literal search will work) */
1660 : 1965139 : end -= pattern[3] - 1;
1661 [ - + ]: 1965139 : if (end <= ptr)
1662 : 0 : end = ptr;
1663 : : }
1664 : :
1665 [ + + ]: 2234114 : if (flags & SRE_INFO_PREFIX) {
1666 : : /* pattern starts with a known prefix */
1667 : : /* <length> <skip> <prefix data> <overlap data> */
1668 : 105765 : prefix_len = pattern[5];
1669 : 105765 : prefix_skip = pattern[6];
1670 : 105765 : prefix = pattern + 7;
1671 : 105765 : overlap = prefix + prefix_len - 1;
1672 [ + + ]: 2128349 : } else if (flags & SRE_INFO_CHARSET)
1673 : : /* pattern starts with a character from a known set */
1674 : : /* <charset> */
1675 : 91404 : charset = pattern + 5;
1676 : :
1677 : 2234114 : pattern += 1 + pattern[1];
1678 : : }
1679 : :
1680 : : TRACE(("prefix = %p %zd %zd\n",
1681 : : prefix, prefix_len, prefix_skip));
1682 : : TRACE(("charset = %p\n", charset));
1683 : :
1684 [ + + ]: 2234114 : if (prefix_len == 1) {
1685 : : /* pattern starts with a literal character */
1686 : 41993 : SRE_CHAR c = (SRE_CHAR) prefix[0];
1687 : : #if SIZEOF_SRE_CHAR < 4
1688 [ - + ]: 41982 : if ((SRE_CODE) c != prefix[0])
1689 : 0 : return 0; /* literal can't match: doesn't fit in char width */
1690 : : #endif
1691 : 41993 : end = (SRE_CHAR *)state->end;
1692 : 41993 : state->must_advance = 0;
1693 [ + + ]: 55734 : while (ptr < end) {
1694 [ + + ]: 895906 : while (*ptr != c) {
1695 [ + + ]: 875212 : if (++ptr >= end)
1696 : 35019 : return 0;
1697 : : }
1698 : : TRACE(("|%p|%p|SEARCH LITERAL\n", pattern, ptr));
1699 : 20694 : state->start = ptr;
1700 : 20694 : state->ptr = ptr + prefix_skip;
1701 [ + + ]: 20694 : if (flags & SRE_INFO_LITERAL)
1702 : 245 : return 1; /* we got all of it */
1703 : 20449 : status = SRE(match)(state, pattern + 2*prefix_skip, 0);
1704 [ + + ]: 20449 : if (status != 0)
1705 : 6708 : return status;
1706 : 13741 : ++ptr;
1707 : 13741 : RESET_CAPTURE_GROUP();
1708 : : }
1709 : 21 : return 0;
1710 : : }
1711 : :
1712 [ + + ]: 2192121 : if (prefix_len > 1) {
1713 : : /* pattern starts with a known prefix. use the overlap
1714 : : table to skip forward as fast as we possibly can */
1715 : 63772 : Py_ssize_t i = 0;
1716 : :
1717 : 63772 : end = (SRE_CHAR *)state->end;
1718 [ - + ]: 63772 : if (prefix_len > end - ptr)
1719 : 0 : return 0;
1720 : : #if SIZEOF_SRE_CHAR < 4
1721 [ + + ]: 427671 : for (i = 0; i < prefix_len; i++)
1722 [ - + ]: 363902 : if ((SRE_CODE)(SRE_CHAR) prefix[i] != prefix[i])
1723 : 0 : return 0; /* literal can't match: doesn't fit in char width */
1724 : : #endif
1725 [ + - ]: 114606 : while (ptr < end) {
1726 : 114606 : SRE_CHAR c = (SRE_CHAR) prefix[0];
1727 [ + + ]: 2954087 : while (*ptr++ != c) {
1728 [ + + ]: 2862277 : if (ptr >= end)
1729 : 22796 : return 0;
1730 : : }
1731 [ + + ]: 91810 : if (ptr >= end)
1732 : 406 : return 0;
1733 : :
1734 : 91404 : i = 1;
1735 : 91404 : state->must_advance = 0;
1736 : : do {
1737 [ + + ]: 328394 : if (*ptr == (SRE_CHAR) prefix[i]) {
1738 [ + + ]: 280201 : if (++i != prefix_len) {
1739 [ - + ]: 236744 : if (++ptr >= end)
1740 : 0 : return 0;
1741 : 236744 : continue;
1742 : : }
1743 : : /* found a potential match */
1744 : : TRACE(("|%p|%p|SEARCH SCAN\n", pattern, ptr));
1745 : 43457 : state->start = ptr - (prefix_len - 1);
1746 : 43457 : state->ptr = ptr - (prefix_len - prefix_skip - 1);
1747 [ + + ]: 43457 : if (flags & SRE_INFO_LITERAL)
1748 : 3657 : return 1; /* we got all of it */
1749 : 39800 : status = SRE(match)(state, pattern + 2*prefix_skip, 0);
1750 [ + + ]: 39800 : if (status != 0)
1751 : 36757 : return status;
1752 : : /* close but no cigar -- try again */
1753 [ + + ]: 3043 : if (++ptr >= end)
1754 : 156 : return 0;
1755 : 2887 : RESET_CAPTURE_GROUP();
1756 : : }
1757 : 51080 : i = overlap[i];
1758 [ + + ]: 287824 : } while (i != 0);
1759 : : }
1760 : 0 : return 0;
1761 : : }
1762 : :
1763 [ + + ]: 2128349 : if (charset) {
1764 : : /* pattern starts with a character from a known set */
1765 : 91404 : end = (SRE_CHAR *)state->end;
1766 : 91404 : state->must_advance = 0;
1767 : : for (;;) {
1768 [ + + + + ]: 914622 : while (ptr < end && !SRE(charset)(state, charset, *ptr))
1769 : 801196 : ptr++;
1770 [ + + ]: 113426 : if (ptr >= end)
1771 : 36740 : return 0;
1772 : : TRACE(("|%p|%p|SEARCH CHARSET\n", pattern, ptr));
1773 : 76686 : state->start = ptr;
1774 : 76686 : state->ptr = ptr;
1775 : 76686 : status = SRE(match)(state, pattern, 0);
1776 [ + + ]: 76686 : if (status != 0)
1777 : 54664 : break;
1778 : 22022 : ptr++;
1779 : 22022 : RESET_CAPTURE_GROUP();
1780 : : }
1781 : : } else {
1782 : : /* general case */
1783 : : assert(ptr <= end);
1784 : : TRACE(("|%p|%p|SEARCH\n", pattern, ptr));
1785 : 2036945 : state->start = state->ptr = ptr;
1786 : 2036945 : status = SRE(match)(state, pattern, 1);
1787 : 2036945 : state->must_advance = 0;
1788 [ + + + + ]: 2036945 : if (status == 0 && pattern[0] == SRE_OP_AT &&
1789 [ + + ]: 1884081 : (pattern[1] == SRE_AT_BEGINNING ||
1790 [ + + ]: 1880605 : pattern[1] == SRE_AT_BEGINNING_STRING))
1791 : : {
1792 : 3677 : state->start = state->ptr = ptr = end;
1793 : 3677 : return 0;
1794 : : }
1795 [ + + + + ]: 69519082 : while (status == 0 && ptr < end) {
1796 : 67485814 : ptr++;
1797 : 67485814 : RESET_CAPTURE_GROUP();
1798 : : TRACE(("|%p|%p|SEARCH\n", pattern, ptr));
1799 : 67485814 : state->start = state->ptr = ptr;
1800 : 67485814 : status = SRE(match)(state, pattern, 0);
1801 : : }
1802 : : }
1803 : :
1804 : 2087932 : return status;
1805 : : }
1806 : :
1807 : : #undef SRE_CHAR
1808 : : #undef SIZEOF_SRE_CHAR
1809 : : #undef SRE
1810 : :
1811 : : /* vim:ts=4:sw=4:et
1812 : : */
|
