1 : /**********************************************************************
2 : regexec.c - Oniguruma (regular expression library)
3 : **********************************************************************/
4 : /*-
5 : * Copyright (c) 2002-2009 K.Kosako <sndgk393 AT ybb DOT ne DOT jp>
6 : * All rights reserved.
7 : *
8 : * Redistribution and use in source and binary forms, with or without
9 : * modification, are permitted provided that the following conditions
10 : * are met:
11 : * 1. Redistributions of source code must retain the above copyright
12 : * notice, this list of conditions and the following disclaimer.
13 : * 2. Redistributions in binary form must reproduce the above copyright
14 : * notice, this list of conditions and the following disclaimer in the
15 : * documentation and/or other materials provided with the distribution.
16 : *
17 : * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 : * SUCH DAMAGE.
28 : */
29 :
30 : #include "regint.h"
31 :
32 : #ifdef USE_CRNL_AS_LINE_TERMINATOR
33 : #define ONIGENC_IS_MBC_CRNL(enc,p,end) \
34 : (ONIGENC_MBC_TO_CODE(enc,p,end) == 13 && \
35 : ONIGENC_IS_MBC_NEWLINE(enc,(p+enc_len(enc,p)),end))
36 : #endif
37 :
38 : #ifdef USE_CAPTURE_HISTORY
39 : static void history_tree_free(OnigCaptureTreeNode* node);
40 :
41 : static void
42 : history_tree_clear(OnigCaptureTreeNode* node)
43 0 : {
44 : int i;
45 :
46 0 : if (IS_NOT_NULL(node)) {
47 0 : for (i = 0; i < node->num_childs; i++) {
48 0 : if (IS_NOT_NULL(node->childs[i])) {
49 0 : history_tree_free(node->childs[i]);
50 : }
51 : }
52 0 : for (i = 0; i < node->allocated; i++) {
53 0 : node->childs[i] = (OnigCaptureTreeNode* )0;
54 : }
55 0 : node->num_childs = 0;
56 0 : node->beg = ONIG_REGION_NOTPOS;
57 0 : node->end = ONIG_REGION_NOTPOS;
58 0 : node->group = -1;
59 : }
60 0 : }
61 :
62 : static void
63 : history_tree_free(OnigCaptureTreeNode* node)
64 0 : {
65 0 : history_tree_clear(node);
66 0 : xfree(node);
67 0 : }
68 :
69 : static void
70 : history_root_free(OnigRegion* r)
71 1665 : {
72 1665 : if (IS_NOT_NULL(r->history_root)) {
73 0 : history_tree_free(r->history_root);
74 0 : r->history_root = (OnigCaptureTreeNode* )0;
75 : }
76 1665 : }
77 :
78 : static OnigCaptureTreeNode*
79 : history_node_new()
80 0 : {
81 : OnigCaptureTreeNode* node;
82 :
83 0 : node = (OnigCaptureTreeNode* )xmalloc(sizeof(OnigCaptureTreeNode));
84 0 : CHECK_NULL_RETURN(node);
85 0 : node->childs = (OnigCaptureTreeNode** )0;
86 0 : node->allocated = 0;
87 0 : node->num_childs = 0;
88 0 : node->group = -1;
89 0 : node->beg = ONIG_REGION_NOTPOS;
90 0 : node->end = ONIG_REGION_NOTPOS;
91 :
92 0 : return node;
93 : }
94 :
95 : static int
96 : history_tree_add_child(OnigCaptureTreeNode* parent, OnigCaptureTreeNode* child)
97 0 : {
98 : #define HISTORY_TREE_INIT_ALLOC_SIZE 8
99 :
100 0 : if (parent->num_childs >= parent->allocated) {
101 : int n, i;
102 :
103 0 : if (IS_NULL(parent->childs)) {
104 0 : n = HISTORY_TREE_INIT_ALLOC_SIZE;
105 0 : parent->childs =
106 : (OnigCaptureTreeNode** )xmalloc(sizeof(OnigCaptureTreeNode*) * n);
107 : }
108 : else {
109 0 : n = parent->allocated * 2;
110 0 : parent->childs =
111 : (OnigCaptureTreeNode** )xrealloc(parent->childs,
112 : sizeof(OnigCaptureTreeNode*) * n);
113 : }
114 0 : CHECK_NULL_RETURN_VAL(parent->childs, ONIGERR_MEMORY);
115 0 : for (i = parent->allocated; i < n; i++) {
116 0 : parent->childs[i] = (OnigCaptureTreeNode* )0;
117 : }
118 0 : parent->allocated = n;
119 : }
120 :
121 0 : parent->childs[parent->num_childs] = child;
122 0 : parent->num_childs++;
123 0 : return 0;
124 : }
125 :
126 : static OnigCaptureTreeNode*
127 : history_tree_clone(OnigCaptureTreeNode* node)
128 0 : {
129 : int i;
130 : OnigCaptureTreeNode *clone, *child;
131 :
132 0 : clone = history_node_new();
133 0 : CHECK_NULL_RETURN(clone);
134 :
135 0 : clone->beg = node->beg;
136 0 : clone->end = node->end;
137 0 : for (i = 0; i < node->num_childs; i++) {
138 0 : child = history_tree_clone(node->childs[i]);
139 0 : if (IS_NULL(child)) {
140 0 : history_tree_free(clone);
141 0 : return (OnigCaptureTreeNode* )0;
142 : }
143 0 : history_tree_add_child(clone, child);
144 : }
145 :
146 0 : return clone;
147 : }
148 :
149 : extern OnigCaptureTreeNode*
150 : onig_get_capture_tree(OnigRegion* region)
151 0 : {
152 0 : return region->history_root;
153 : }
154 : #endif /* USE_CAPTURE_HISTORY */
155 :
156 : extern void
157 : onig_region_clear(OnigRegion* region)
158 762 : {
159 : int i;
160 :
161 1666 : for (i = 0; i < region->num_regs; i++) {
162 904 : region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;
163 : }
164 : #ifdef USE_CAPTURE_HISTORY
165 762 : history_root_free(region);
166 : #endif
167 762 : }
168 :
169 : extern int
170 : onig_region_resize(OnigRegion* region, int n)
171 762 : {
172 762 : region->num_regs = n;
173 :
174 762 : if (n < ONIG_NREGION)
175 762 : n = ONIG_NREGION;
176 :
177 762 : if (region->allocated == 0) {
178 762 : region->beg = (int* )xmalloc(n * sizeof(int));
179 762 : region->end = (int* )xmalloc(n * sizeof(int));
180 :
181 762 : if (region->beg == 0 || region->end == 0)
182 0 : return ONIGERR_MEMORY;
183 :
184 762 : region->allocated = n;
185 : }
186 0 : else if (region->allocated < n) {
187 0 : region->beg = (int* )xrealloc(region->beg, n * sizeof(int));
188 0 : region->end = (int* )xrealloc(region->end, n * sizeof(int));
189 :
190 0 : if (region->beg == 0 || region->end == 0)
191 0 : return ONIGERR_MEMORY;
192 :
193 0 : region->allocated = n;
194 : }
195 :
196 762 : return 0;
197 : }
198 :
199 : extern int
200 : onig_region_resize_clear(OnigRegion* region, int n)
201 762 : {
202 : int r;
203 :
204 762 : r = onig_region_resize(region, n);
205 762 : if (r != 0) return r;
206 762 : onig_region_clear(region);
207 762 : return 0;
208 : }
209 :
210 : extern int
211 : onig_region_set(OnigRegion* region, int at, int beg, int end)
212 0 : {
213 0 : if (at < 0) return ONIGERR_INVALID_ARGUMENT;
214 :
215 0 : if (at >= region->allocated) {
216 0 : int r = onig_region_resize(region, at + 1);
217 0 : if (r < 0) return r;
218 : }
219 :
220 0 : region->beg[at] = beg;
221 0 : region->end[at] = end;
222 0 : return 0;
223 : }
224 :
225 : extern void
226 : onig_region_init(OnigRegion* region)
227 371 : {
228 371 : region->num_regs = 0;
229 371 : region->allocated = 0;
230 371 : region->beg = (int* )0;
231 371 : region->end = (int* )0;
232 371 : region->history_root = (OnigCaptureTreeNode* )0;
233 371 : }
234 :
235 : extern OnigRegion*
236 : onig_region_new()
237 371 : {
238 : OnigRegion* r;
239 :
240 371 : r = (OnigRegion* )xmalloc(sizeof(OnigRegion));
241 371 : onig_region_init(r);
242 371 : return r;
243 : }
244 :
245 : extern void
246 : onig_region_free(OnigRegion* r, int free_self)
247 903 : {
248 903 : if (r) {
249 903 : if (r->allocated > 0) {
250 761 : if (r->beg) xfree(r->beg);
251 761 : if (r->end) xfree(r->end);
252 761 : r->allocated = 0;
253 : }
254 : #ifdef USE_CAPTURE_HISTORY
255 903 : history_root_free(r);
256 : #endif
257 903 : if (free_self) xfree(r);
258 : }
259 903 : }
260 :
261 : extern void
262 : onig_region_copy(OnigRegion* to, OnigRegion* from)
263 0 : {
264 : #define RREGC_SIZE (sizeof(int) * from->num_regs)
265 : int i;
266 :
267 0 : if (to == from) return;
268 :
269 0 : if (to->allocated == 0) {
270 0 : if (from->num_regs > 0) {
271 0 : to->beg = (int* )xmalloc(RREGC_SIZE);
272 0 : to->end = (int* )xmalloc(RREGC_SIZE);
273 0 : to->allocated = from->num_regs;
274 : }
275 : }
276 0 : else if (to->allocated < from->num_regs) {
277 0 : to->beg = (int* )xrealloc(to->beg, RREGC_SIZE);
278 0 : to->end = (int* )xrealloc(to->end, RREGC_SIZE);
279 0 : to->allocated = from->num_regs;
280 : }
281 :
282 0 : for (i = 0; i < from->num_regs; i++) {
283 0 : to->beg[i] = from->beg[i];
284 0 : to->end[i] = from->end[i];
285 : }
286 0 : to->num_regs = from->num_regs;
287 :
288 : #ifdef USE_CAPTURE_HISTORY
289 0 : history_root_free(to);
290 :
291 0 : if (IS_NOT_NULL(from->history_root)) {
292 0 : to->history_root = history_tree_clone(from->history_root);
293 : }
294 : #endif
295 : }
296 :
297 :
298 : /** stack **/
299 : #define INVALID_STACK_INDEX -1
300 : typedef long StackIndex;
301 :
302 : typedef struct _StackType {
303 : unsigned int type;
304 : union {
305 : struct {
306 : UChar *pcode; /* byte code position */
307 : UChar *pstr; /* string position */
308 : UChar *pstr_prev; /* previous char position of pstr */
309 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
310 : unsigned int state_check;
311 : #endif
312 : } state;
313 : struct {
314 : int count; /* for OP_REPEAT_INC, OP_REPEAT_INC_NG */
315 : UChar *pcode; /* byte code position (head of repeated target) */
316 : int num; /* repeat id */
317 : } repeat;
318 : struct {
319 : StackIndex si; /* index of stack */
320 : } repeat_inc;
321 : struct {
322 : int num; /* memory num */
323 : UChar *pstr; /* start/end position */
324 : /* Following information is setted, if this stack type is MEM-START */
325 : StackIndex start; /* prev. info (for backtrack "(...)*" ) */
326 : StackIndex end; /* prev. info (for backtrack "(...)*" ) */
327 : } mem;
328 : struct {
329 : int num; /* null check id */
330 : UChar *pstr; /* start position */
331 : } null_check;
332 : #ifdef USE_SUBEXP_CALL
333 : struct {
334 : UChar *ret_addr; /* byte code position */
335 : int num; /* null check id */
336 : UChar *pstr; /* string position */
337 : } call_frame;
338 : #endif
339 : } u;
340 : } StackType;
341 :
342 : /* stack type */
343 : /* used by normal-POP */
344 : #define STK_ALT 0x0001
345 : #define STK_LOOK_BEHIND_NOT 0x0002
346 : #define STK_POS_NOT 0x0003
347 : /* handled by normal-POP */
348 : #define STK_MEM_START 0x0100
349 : #define STK_MEM_END 0x8200
350 : #define STK_REPEAT_INC 0x0300
351 : #define STK_STATE_CHECK_MARK 0x1000
352 : /* avoided by normal-POP */
353 : #define STK_NULL_CHECK_START 0x3000
354 : #define STK_NULL_CHECK_END 0x5000 /* for recursive call */
355 : #define STK_MEM_END_MARK 0x8400
356 : #define STK_POS 0x0500 /* used when POP-POS */
357 : #define STK_STOP_BT 0x0600 /* mark for "(?>...)" */
358 : #define STK_REPEAT 0x0700
359 : #define STK_CALL_FRAME 0x0800
360 : #define STK_RETURN 0x0900
361 : #define STK_VOID 0x0a00 /* for fill a blank */
362 :
363 : /* stack type check mask */
364 : #define STK_MASK_POP_USED 0x00ff
365 : #define STK_MASK_TO_VOID_TARGET 0x10ff
366 : #define STK_MASK_MEM_END_OR_MARK 0x8000 /* MEM_END or MEM_END_MARK */
367 :
368 : typedef struct {
369 : void* stack_p;
370 : int stack_n;
371 : OnigOptionType options;
372 : OnigRegion* region;
373 : const UChar* start; /* search start position (for \G: BEGIN_POSITION) */
374 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
375 : void* state_check_buff;
376 : int state_check_buff_size;
377 : #endif
378 : } MatchArg;
379 :
380 : #define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start) do {\
381 : (msa).stack_p = (void* )0;\
382 : (msa).options = (arg_option);\
383 : (msa).region = (arg_region);\
384 : (msa).start = (arg_start);\
385 : } while (0)
386 :
387 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
388 :
389 : #define STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE 16
390 :
391 : #define STATE_CHECK_BUFF_INIT(msa, str_len, state_num) do { \
392 : (msa).state_check_buff = (void* )0;\
393 : (msa).state_check_buff_size = 0;\
394 : if ((state_num) > 0 && str_len >= STATE_CHECK_STRING_THRESHOLD_LEN) {\
395 : int size = ((int )((str_len) + 1) * (state_num) + 7) / 8;\
396 : (msa).state_check_buff_size = size; \
397 : if (size > 0 && size < STATE_CHECK_BUFF_MAX_SIZE) {\
398 : if (size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) \
399 : (msa).state_check_buff = (void* )xmalloc(size);\
400 : else \
401 : (msa).state_check_buff = (void* )xalloca(size);\
402 : xmemset((msa).state_check_buff, 0, (size_t )size);\
403 : }\
404 : }\
405 : } while (0)
406 :
407 : #define MATCH_ARG_FREE(msa) do {\
408 : if ((msa).stack_p) xfree((msa).stack_p);\
409 : if ((msa).state_check_buff_size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) { \
410 : if ((msa).state_check_buff) xfree((msa).state_check_buff);\
411 : }\
412 : } while (0);
413 : #else
414 : #define STATE_CHECK_BUFF_INIT(msa, str_len, state_num)
415 : #define MATCH_ARG_FREE(msa) if ((msa).stack_p) xfree((msa).stack_p)
416 : #endif
417 :
418 :
419 :
420 : #define STACK_INIT(alloc_addr, ptr_num, stack_num) do {\
421 : if (msa->stack_p) {\
422 : alloc_addr = (char* )xalloca(sizeof(char*) * (ptr_num));\
423 : stk_alloc = (StackType* )(msa->stack_p);\
424 : stk_base = stk_alloc;\
425 : stk = stk_base;\
426 : stk_end = stk_base + msa->stack_n;\
427 : }\
428 : else {\
429 : alloc_addr = (char* )xalloca(sizeof(char*) * (ptr_num)\
430 : + sizeof(StackType) * (stack_num));\
431 : stk_alloc = (StackType* )(alloc_addr + sizeof(char*) * (ptr_num));\
432 : stk_base = stk_alloc;\
433 : stk = stk_base;\
434 : stk_end = stk_base + (stack_num);\
435 : }\
436 : } while(0)
437 :
438 : #define STACK_SAVE do{\
439 : if (stk_base != stk_alloc) {\
440 : msa->stack_p = stk_base;\
441 : msa->stack_n = stk_end - stk_base;\
442 : };\
443 : } while(0)
444 :
445 : static unsigned int MatchStackLimitSize = DEFAULT_MATCH_STACK_LIMIT_SIZE;
446 :
447 : extern unsigned int
448 : onig_get_match_stack_limit_size(void)
449 0 : {
450 0 : return MatchStackLimitSize;
451 : }
452 :
453 : extern int
454 : onig_set_match_stack_limit_size(unsigned int size)
455 0 : {
456 0 : MatchStackLimitSize = size;
457 0 : return 0;
458 : }
459 :
460 : static int
461 : stack_double(StackType** arg_stk_base, StackType** arg_stk_end,
462 : StackType** arg_stk, StackType* stk_alloc, MatchArg* msa)
463 0 : {
464 : unsigned int n;
465 : StackType *x, *stk_base, *stk_end, *stk;
466 :
467 0 : stk_base = *arg_stk_base;
468 0 : stk_end = *arg_stk_end;
469 0 : stk = *arg_stk;
470 :
471 0 : n = stk_end - stk_base;
472 0 : if (stk_base == stk_alloc && IS_NULL(msa->stack_p)) {
473 0 : x = (StackType* )xmalloc(sizeof(StackType) * n * 2);
474 0 : if (IS_NULL(x)) {
475 0 : STACK_SAVE;
476 0 : return ONIGERR_MEMORY;
477 : }
478 0 : xmemcpy(x, stk_base, n * sizeof(StackType));
479 0 : n *= 2;
480 : }
481 : else {
482 0 : n *= 2;
483 0 : if (MatchStackLimitSize != 0 && n > MatchStackLimitSize) {
484 0 : if ((unsigned int )(stk_end - stk_base) == MatchStackLimitSize)
485 0 : return ONIGERR_MATCH_STACK_LIMIT_OVER;
486 : else
487 0 : n = MatchStackLimitSize;
488 : }
489 0 : x = (StackType* )xrealloc(stk_base, sizeof(StackType) * n);
490 0 : if (IS_NULL(x)) {
491 0 : STACK_SAVE;
492 0 : return ONIGERR_MEMORY;
493 : }
494 : }
495 0 : *arg_stk = x + (stk - stk_base);
496 0 : *arg_stk_base = x;
497 0 : *arg_stk_end = x + n;
498 0 : return 0;
499 : }
500 :
501 : #define STACK_ENSURE(n) do {\
502 : if (stk_end - stk < (n)) {\
503 : int r = stack_double(&stk_base, &stk_end, &stk, stk_alloc, msa);\
504 : if (r != 0) { STACK_SAVE; return r; } \
505 : }\
506 : } while(0)
507 :
508 : #define STACK_AT(index) (stk_base + (index))
509 : #define GET_STACK_INDEX(stk) ((stk) - stk_base)
510 :
511 : #define STACK_PUSH_TYPE(stack_type) do {\
512 : STACK_ENSURE(1);\
513 : stk->type = (stack_type);\
514 : STACK_INC;\
515 : } while(0)
516 :
517 : #define IS_TO_VOID_TARGET(stk) (((stk)->type & STK_MASK_TO_VOID_TARGET) != 0)
518 :
519 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
520 : #define STATE_CHECK_POS(s,snum) \
521 : (((s) - str) * num_comb_exp_check + ((snum) - 1))
522 : #define STATE_CHECK_VAL(v,snum) do {\
523 : if (state_check_buff != NULL) {\
524 : int x = STATE_CHECK_POS(s,snum);\
525 : (v) = state_check_buff[x/8] & (1<<(x%8));\
526 : }\
527 : else (v) = 0;\
528 : } while(0)
529 :
530 :
531 : #define ELSE_IF_STATE_CHECK_MARK(stk) \
532 : else if ((stk)->type == STK_STATE_CHECK_MARK) { \
533 : int x = STATE_CHECK_POS(stk->u.state.pstr, stk->u.state.state_check);\
534 : state_check_buff[x/8] |= (1<<(x%8)); \
535 : }
536 :
537 : #define STACK_PUSH(stack_type,pat,s,sprev) do {\
538 : STACK_ENSURE(1);\
539 : stk->type = (stack_type);\
540 : stk->u.state.pcode = (pat);\
541 : stk->u.state.pstr = (s);\
542 : stk->u.state.pstr_prev = (sprev);\
543 : stk->u.state.state_check = 0;\
544 : STACK_INC;\
545 : } while(0)
546 :
547 : #define STACK_PUSH_ENSURED(stack_type,pat) do {\
548 : stk->type = (stack_type);\
549 : stk->u.state.pcode = (pat);\
550 : stk->u.state.state_check = 0;\
551 : STACK_INC;\
552 : } while(0)
553 :
554 : #define STACK_PUSH_ALT_WITH_STATE_CHECK(pat,s,sprev,snum) do {\
555 : STACK_ENSURE(1);\
556 : stk->type = STK_ALT;\
557 : stk->u.state.pcode = (pat);\
558 : stk->u.state.pstr = (s);\
559 : stk->u.state.pstr_prev = (sprev);\
560 : stk->u.state.state_check = ((state_check_buff != NULL) ? (snum) : 0);\
561 : STACK_INC;\
562 : } while(0)
563 :
564 : #define STACK_PUSH_STATE_CHECK(s,snum) do {\
565 : if (state_check_buff != NULL) {\
566 : STACK_ENSURE(1);\
567 : stk->type = STK_STATE_CHECK_MARK;\
568 : stk->u.state.pstr = (s);\
569 : stk->u.state.state_check = (snum);\
570 : STACK_INC;\
571 : }\
572 : } while(0)
573 :
574 : #else /* USE_COMBINATION_EXPLOSION_CHECK */
575 :
576 : #define ELSE_IF_STATE_CHECK_MARK(stk)
577 :
578 : #define STACK_PUSH(stack_type,pat,s,sprev) do {\
579 : STACK_ENSURE(1);\
580 : stk->type = (stack_type);\
581 : stk->u.state.pcode = (pat);\
582 : stk->u.state.pstr = (s);\
583 : stk->u.state.pstr_prev = (sprev);\
584 : STACK_INC;\
585 : } while(0)
586 :
587 : #define STACK_PUSH_ENSURED(stack_type,pat) do {\
588 : stk->type = (stack_type);\
589 : stk->u.state.pcode = (pat);\
590 : STACK_INC;\
591 : } while(0)
592 : #endif /* USE_COMBINATION_EXPLOSION_CHECK */
593 :
594 : #define STACK_PUSH_ALT(pat,s,sprev) STACK_PUSH(STK_ALT,pat,s,sprev)
595 : #define STACK_PUSH_POS(s,sprev) STACK_PUSH(STK_POS,NULL_UCHARP,s,sprev)
596 : #define STACK_PUSH_POS_NOT(pat,s,sprev) STACK_PUSH(STK_POS_NOT,pat,s,sprev)
597 : #define STACK_PUSH_STOP_BT STACK_PUSH_TYPE(STK_STOP_BT)
598 : #define STACK_PUSH_LOOK_BEHIND_NOT(pat,s,sprev) \
599 : STACK_PUSH(STK_LOOK_BEHIND_NOT,pat,s,sprev)
600 :
601 : #define STACK_PUSH_REPEAT(id, pat) do {\
602 : STACK_ENSURE(1);\
603 : stk->type = STK_REPEAT;\
604 : stk->u.repeat.num = (id);\
605 : stk->u.repeat.pcode = (pat);\
606 : stk->u.repeat.count = 0;\
607 : STACK_INC;\
608 : } while(0)
609 :
610 : #define STACK_PUSH_REPEAT_INC(sindex) do {\
611 : STACK_ENSURE(1);\
612 : stk->type = STK_REPEAT_INC;\
613 : stk->u.repeat_inc.si = (sindex);\
614 : STACK_INC;\
615 : } while(0)
616 :
617 : #define STACK_PUSH_MEM_START(mnum, s) do {\
618 : STACK_ENSURE(1);\
619 : stk->type = STK_MEM_START;\
620 : stk->u.mem.num = (mnum);\
621 : stk->u.mem.pstr = (s);\
622 : stk->u.mem.start = mem_start_stk[mnum];\
623 : stk->u.mem.end = mem_end_stk[mnum];\
624 : mem_start_stk[mnum] = GET_STACK_INDEX(stk);\
625 : mem_end_stk[mnum] = INVALID_STACK_INDEX;\
626 : STACK_INC;\
627 : } while(0)
628 :
629 : #define STACK_PUSH_MEM_END(mnum, s) do {\
630 : STACK_ENSURE(1);\
631 : stk->type = STK_MEM_END;\
632 : stk->u.mem.num = (mnum);\
633 : stk->u.mem.pstr = (s);\
634 : stk->u.mem.start = mem_start_stk[mnum];\
635 : stk->u.mem.end = mem_end_stk[mnum];\
636 : mem_end_stk[mnum] = GET_STACK_INDEX(stk);\
637 : STACK_INC;\
638 : } while(0)
639 :
640 : #define STACK_PUSH_MEM_END_MARK(mnum) do {\
641 : STACK_ENSURE(1);\
642 : stk->type = STK_MEM_END_MARK;\
643 : stk->u.mem.num = (mnum);\
644 : STACK_INC;\
645 : } while(0)
646 :
647 : #define STACK_GET_MEM_START(mnum, k) do {\
648 : int level = 0;\
649 : k = stk;\
650 : while (k > stk_base) {\
651 : k--;\
652 : if ((k->type & STK_MASK_MEM_END_OR_MARK) != 0 \
653 : && k->u.mem.num == (mnum)) {\
654 : level++;\
655 : }\
656 : else if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
657 : if (level == 0) break;\
658 : level--;\
659 : }\
660 : }\
661 : } while (0)
662 :
663 : #define STACK_GET_MEM_RANGE(k, mnum, start, end) do {\
664 : int level = 0;\
665 : while (k < stk) {\
666 : if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
667 : if (level == 0) (start) = k->u.mem.pstr;\
668 : level++;\
669 : }\
670 : else if (k->type == STK_MEM_END && k->u.mem.num == (mnum)) {\
671 : level--;\
672 : if (level == 0) {\
673 : (end) = k->u.mem.pstr;\
674 : break;\
675 : }\
676 : }\
677 : k++;\
678 : }\
679 : } while (0)
680 :
681 : #define STACK_PUSH_NULL_CHECK_START(cnum, s) do {\
682 : STACK_ENSURE(1);\
683 : stk->type = STK_NULL_CHECK_START;\
684 : stk->u.null_check.num = (cnum);\
685 : stk->u.null_check.pstr = (s);\
686 : STACK_INC;\
687 : } while(0)
688 :
689 : #define STACK_PUSH_NULL_CHECK_END(cnum) do {\
690 : STACK_ENSURE(1);\
691 : stk->type = STK_NULL_CHECK_END;\
692 : stk->u.null_check.num = (cnum);\
693 : STACK_INC;\
694 : } while(0)
695 :
696 : #define STACK_PUSH_CALL_FRAME(pat) do {\
697 : STACK_ENSURE(1);\
698 : stk->type = STK_CALL_FRAME;\
699 : stk->u.call_frame.ret_addr = (pat);\
700 : STACK_INC;\
701 : } while(0)
702 :
703 : #define STACK_PUSH_RETURN do {\
704 : STACK_ENSURE(1);\
705 : stk->type = STK_RETURN;\
706 : STACK_INC;\
707 : } while(0)
708 :
709 :
710 : #ifdef ONIG_DEBUG
711 : #define STACK_BASE_CHECK(p, at) \
712 : if ((p) < stk_base) {\
713 : fprintf(stderr, "at %s\n", at);\
714 : goto stack_error;\
715 : }
716 : #else
717 : #define STACK_BASE_CHECK(p, at)
718 : #endif
719 :
720 : #define STACK_POP_ONE do {\
721 : stk--;\
722 : STACK_BASE_CHECK(stk, "STACK_POP_ONE"); \
723 : } while(0)
724 :
725 : #define STACK_POP do {\
726 : switch (pop_level) {\
727 : case STACK_POP_LEVEL_FREE:\
728 : while (1) {\
729 : stk--;\
730 : STACK_BASE_CHECK(stk, "STACK_POP"); \
731 : if ((stk->type & STK_MASK_POP_USED) != 0) break;\
732 : ELSE_IF_STATE_CHECK_MARK(stk);\
733 : }\
734 : break;\
735 : case STACK_POP_LEVEL_MEM_START:\
736 : while (1) {\
737 : stk--;\
738 : STACK_BASE_CHECK(stk, "STACK_POP 2"); \
739 : if ((stk->type & STK_MASK_POP_USED) != 0) break;\
740 : else if (stk->type == STK_MEM_START) {\
741 : mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
742 : mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
743 : }\
744 : ELSE_IF_STATE_CHECK_MARK(stk);\
745 : }\
746 : break;\
747 : default:\
748 : while (1) {\
749 : stk--;\
750 : STACK_BASE_CHECK(stk, "STACK_POP 3"); \
751 : if ((stk->type & STK_MASK_POP_USED) != 0) break;\
752 : else if (stk->type == STK_MEM_START) {\
753 : mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
754 : mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
755 : }\
756 : else if (stk->type == STK_REPEAT_INC) {\
757 : STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
758 : }\
759 : else if (stk->type == STK_MEM_END) {\
760 : mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
761 : mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
762 : }\
763 : ELSE_IF_STATE_CHECK_MARK(stk);\
764 : }\
765 : break;\
766 : }\
767 : } while(0)
768 :
769 : #define STACK_POP_TIL_POS_NOT do {\
770 : while (1) {\
771 : stk--;\
772 : STACK_BASE_CHECK(stk, "STACK_POP_TIL_POS_NOT"); \
773 : if (stk->type == STK_POS_NOT) break;\
774 : else if (stk->type == STK_MEM_START) {\
775 : mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
776 : mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
777 : }\
778 : else if (stk->type == STK_REPEAT_INC) {\
779 : STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
780 : }\
781 : else if (stk->type == STK_MEM_END) {\
782 : mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
783 : mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
784 : }\
785 : ELSE_IF_STATE_CHECK_MARK(stk);\
786 : }\
787 : } while(0)
788 :
789 : #define STACK_POP_TIL_LOOK_BEHIND_NOT do {\
790 : while (1) {\
791 : stk--;\
792 : STACK_BASE_CHECK(stk, "STACK_POP_TIL_LOOK_BEHIND_NOT"); \
793 : if (stk->type == STK_LOOK_BEHIND_NOT) break;\
794 : else if (stk->type == STK_MEM_START) {\
795 : mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
796 : mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
797 : }\
798 : else if (stk->type == STK_REPEAT_INC) {\
799 : STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
800 : }\
801 : else if (stk->type == STK_MEM_END) {\
802 : mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
803 : mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
804 : }\
805 : ELSE_IF_STATE_CHECK_MARK(stk);\
806 : }\
807 : } while(0)
808 :
809 : #define STACK_POS_END(k) do {\
810 : k = stk;\
811 : while (1) {\
812 : k--;\
813 : STACK_BASE_CHECK(k, "STACK_POS_END"); \
814 : if (IS_TO_VOID_TARGET(k)) {\
815 : k->type = STK_VOID;\
816 : }\
817 : else if (k->type == STK_POS) {\
818 : k->type = STK_VOID;\
819 : break;\
820 : }\
821 : }\
822 : } while(0)
823 :
824 : #define STACK_STOP_BT_END do {\
825 : StackType *k = stk;\
826 : while (1) {\
827 : k--;\
828 : STACK_BASE_CHECK(k, "STACK_STOP_BT_END"); \
829 : if (IS_TO_VOID_TARGET(k)) {\
830 : k->type = STK_VOID;\
831 : }\
832 : else if (k->type == STK_STOP_BT) {\
833 : k->type = STK_VOID;\
834 : break;\
835 : }\
836 : }\
837 : } while(0)
838 :
839 : #define STACK_NULL_CHECK(isnull,id,s) do {\
840 : StackType* k = stk;\
841 : while (1) {\
842 : k--;\
843 : STACK_BASE_CHECK(k, "STACK_NULL_CHECK"); \
844 : if (k->type == STK_NULL_CHECK_START) {\
845 : if (k->u.null_check.num == (id)) {\
846 : (isnull) = (k->u.null_check.pstr == (s));\
847 : break;\
848 : }\
849 : }\
850 : }\
851 : } while(0)
852 :
853 : #define STACK_NULL_CHECK_REC(isnull,id,s) do {\
854 : int level = 0;\
855 : StackType* k = stk;\
856 : while (1) {\
857 : k--;\
858 : STACK_BASE_CHECK(k, "STACK_NULL_CHECK_REC"); \
859 : if (k->type == STK_NULL_CHECK_START) {\
860 : if (k->u.null_check.num == (id)) {\
861 : if (level == 0) {\
862 : (isnull) = (k->u.null_check.pstr == (s));\
863 : break;\
864 : }\
865 : else level--;\
866 : }\
867 : }\
868 : else if (k->type == STK_NULL_CHECK_END) {\
869 : level++;\
870 : }\
871 : }\
872 : } while(0)
873 :
874 : #define STACK_NULL_CHECK_MEMST(isnull,id,s,reg) do {\
875 : StackType* k = stk;\
876 : while (1) {\
877 : k--;\
878 : STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST"); \
879 : if (k->type == STK_NULL_CHECK_START) {\
880 : if (k->u.null_check.num == (id)) {\
881 : if (k->u.null_check.pstr != (s)) {\
882 : (isnull) = 0;\
883 : break;\
884 : }\
885 : else {\
886 : UChar* endp;\
887 : (isnull) = 1;\
888 : while (k < stk) {\
889 : if (k->type == STK_MEM_START) {\
890 : if (k->u.mem.end == INVALID_STACK_INDEX) {\
891 : (isnull) = 0; break;\
892 : }\
893 : if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
894 : endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
895 : else\
896 : endp = (UChar* )k->u.mem.end;\
897 : if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
898 : (isnull) = 0; break;\
899 : }\
900 : else if (endp != s) {\
901 : (isnull) = -1; /* empty, but position changed */ \
902 : }\
903 : }\
904 : k++;\
905 : }\
906 : break;\
907 : }\
908 : }\
909 : }\
910 : }\
911 : } while(0)
912 :
913 : #define STACK_NULL_CHECK_MEMST_REC(isnull,id,s,reg) do {\
914 : int level = 0;\
915 : StackType* k = stk;\
916 : while (1) {\
917 : k--;\
918 : STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST_REC"); \
919 : if (k->type == STK_NULL_CHECK_START) {\
920 : if (k->u.null_check.num == (id)) {\
921 : if (level == 0) {\
922 : if (k->u.null_check.pstr != (s)) {\
923 : (isnull) = 0;\
924 : break;\
925 : }\
926 : else {\
927 : UChar* endp;\
928 : (isnull) = 1;\
929 : while (k < stk) {\
930 : if (k->type == STK_MEM_START) {\
931 : if (k->u.mem.end == INVALID_STACK_INDEX) {\
932 : (isnull) = 0; break;\
933 : }\
934 : if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
935 : endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
936 : else\
937 : endp = (UChar* )k->u.mem.end;\
938 : if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
939 : (isnull) = 0; break;\
940 : }\
941 : else if (endp != s) {\
942 : (isnull) = -1; /* empty, but position changed */ \
943 : }\
944 : }\
945 : k++;\
946 : }\
947 : break;\
948 : }\
949 : }\
950 : else {\
951 : level--;\
952 : }\
953 : }\
954 : }\
955 : else if (k->type == STK_NULL_CHECK_END) {\
956 : if (k->u.null_check.num == (id)) level++;\
957 : }\
958 : }\
959 : } while(0)
960 :
961 : #define STACK_GET_REPEAT(id, k) do {\
962 : int level = 0;\
963 : k = stk;\
964 : while (1) {\
965 : k--;\
966 : STACK_BASE_CHECK(k, "STACK_GET_REPEAT"); \
967 : if (k->type == STK_REPEAT) {\
968 : if (level == 0) {\
969 : if (k->u.repeat.num == (id)) {\
970 : break;\
971 : }\
972 : }\
973 : }\
974 : else if (k->type == STK_CALL_FRAME) level--;\
975 : else if (k->type == STK_RETURN) level++;\
976 : }\
977 : } while (0)
978 :
979 : #define STACK_RETURN(addr) do {\
980 : int level = 0;\
981 : StackType* k = stk;\
982 : while (1) {\
983 : k--;\
984 : STACK_BASE_CHECK(k, "STACK_RETURN"); \
985 : if (k->type == STK_CALL_FRAME) {\
986 : if (level == 0) {\
987 : (addr) = k->u.call_frame.ret_addr;\
988 : break;\
989 : }\
990 : else level--;\
991 : }\
992 : else if (k->type == STK_RETURN)\
993 : level++;\
994 : }\
995 : } while(0)
996 :
997 :
998 : #define STRING_CMP(s1,s2,len) do {\
999 : while (len-- > 0) {\
1000 : if (*s1++ != *s2++) goto fail;\
1001 : }\
1002 : } while(0)
1003 :
1004 : #define STRING_CMP_IC(ambig_flag,s1,ps2,len) do {\
1005 : if (string_cmp_ic(encode, ambig_flag, s1, ps2, len) == 0) \
1006 : goto fail; \
1007 : } while(0)
1008 :
1009 : static int string_cmp_ic(OnigEncoding enc, int ambig_flag,
1010 : UChar* s1, UChar** ps2, int mblen)
1011 0 : {
1012 : UChar buf1[ONIGENC_MBC_NORMALIZE_MAXLEN];
1013 : UChar buf2[ONIGENC_MBC_NORMALIZE_MAXLEN];
1014 : UChar *p1, *p2, *end, *s2, *end2;
1015 : int len1, len2;
1016 :
1017 0 : s2 = *ps2;
1018 0 : end = s1 + mblen;
1019 0 : end2 = s2 + mblen;
1020 0 : while (s1 < end) {
1021 0 : len1 = ONIGENC_MBC_TO_NORMALIZE(enc, ambig_flag, &s1, end, buf1);
1022 0 : len2 = ONIGENC_MBC_TO_NORMALIZE(enc, ambig_flag, &s2, end2, buf2);
1023 0 : if (len1 != len2) return 0;
1024 0 : p1 = buf1;
1025 0 : p2 = buf2;
1026 0 : while (len1-- > 0) {
1027 0 : if (*p1 != *p2) return 0;
1028 0 : p1++;
1029 0 : p2++;
1030 : }
1031 : }
1032 :
1033 0 : *ps2 = s2;
1034 0 : return 1;
1035 : }
1036 :
1037 : #define STRING_CMP_VALUE(s1,s2,len,is_fail) do {\
1038 : is_fail = 0;\
1039 : while (len-- > 0) {\
1040 : if (*s1++ != *s2++) {\
1041 : is_fail = 1; break;\
1042 : }\
1043 : }\
1044 : } while(0)
1045 :
1046 : #define STRING_CMP_VALUE_IC(ambig_flag,s1,ps2,len,is_fail) do {\
1047 : if (string_cmp_ic(encode, ambig_flag, s1, ps2, len) == 0) \
1048 : is_fail = 1; \
1049 : else \
1050 : is_fail = 0; \
1051 : } while(0)
1052 :
1053 :
1054 : #define ON_STR_BEGIN(s) ((s) == str)
1055 : #define ON_STR_END(s) ((s) == end)
1056 : #define IS_EMPTY_STR (str == end)
1057 :
1058 : #define DATA_ENSURE(n) \
1059 : if (s + (n) > end) goto fail
1060 :
1061 : #define DATA_ENSURE_CHECK(n) (s + (n) <= end)
1062 :
1063 : #ifdef USE_CAPTURE_HISTORY
1064 : static int
1065 : make_capture_history_tree(OnigCaptureTreeNode* node, StackType** kp,
1066 : StackType* stk_top, UChar* str, regex_t* reg)
1067 0 : {
1068 : int n, r;
1069 : OnigCaptureTreeNode* child;
1070 0 : StackType* k = *kp;
1071 :
1072 0 : while (k < stk_top) {
1073 0 : if (k->type == STK_MEM_START) {
1074 0 : n = k->u.mem.num;
1075 0 : if (n <= ONIG_MAX_CAPTURE_HISTORY_GROUP &&
1076 : BIT_STATUS_AT(reg->capture_history, n) != 0) {
1077 0 : child = history_node_new();
1078 0 : CHECK_NULL_RETURN_VAL(child, ONIGERR_MEMORY);
1079 0 : child->group = n;
1080 0 : child->beg = (int )(k->u.mem.pstr - str);
1081 0 : r = history_tree_add_child(node, child);
1082 0 : if (r != 0) return r;
1083 0 : *kp = (k + 1);
1084 0 : r = make_capture_history_tree(child, kp, stk_top, str, reg);
1085 0 : if (r != 0) return r;
1086 :
1087 0 : k = *kp;
1088 0 : child->end = (int )(k->u.mem.pstr - str);
1089 : }
1090 : }
1091 0 : else if (k->type == STK_MEM_END) {
1092 0 : if (k->u.mem.num == node->group) {
1093 0 : node->end = (int )(k->u.mem.pstr - str);
1094 0 : *kp = k;
1095 0 : return 0;
1096 : }
1097 : }
1098 0 : k++;
1099 : }
1100 :
1101 0 : return 1; /* 1: root node ending. */
1102 : }
1103 : #endif
1104 :
1105 : #ifdef USE_BACKREF_AT_LEVEL
1106 : static int mem_is_in_memp(int mem, int num, UChar* memp)
1107 0 : {
1108 : int i;
1109 : MemNumType m;
1110 :
1111 0 : for (i = 0; i < num; i++) {
1112 0 : GET_MEMNUM_INC(m, memp);
1113 0 : if (mem == (int )m) return 1;
1114 : }
1115 0 : return 0;
1116 : }
1117 :
1118 : static int backref_match_at_nested_level(regex_t* reg
1119 : , StackType* top, StackType* stk_base
1120 : , int ignore_case, int ambig_flag
1121 : , int nest, int mem_num, UChar* memp, UChar** s, const UChar* send)
1122 0 : {
1123 0 : UChar *ss, *p, *pstart, *pend = NULL_UCHARP;
1124 : int level;
1125 : StackType* k;
1126 :
1127 0 : level = 0;
1128 0 : k = top;
1129 0 : k--;
1130 0 : while (k >= stk_base) {
1131 0 : if (k->type == STK_CALL_FRAME) {
1132 0 : level--;
1133 : }
1134 0 : else if (k->type == STK_RETURN) {
1135 0 : level++;
1136 : }
1137 0 : else if (level == nest) {
1138 0 : if (k->type == STK_MEM_START) {
1139 0 : if (mem_is_in_memp(k->u.mem.num, mem_num, memp)) {
1140 0 : pstart = k->u.mem.pstr;
1141 0 : if (pend != NULL_UCHARP) {
1142 0 : if (pend - pstart > send - *s) return 0; /* or goto next_mem; */
1143 0 : p = pstart;
1144 0 : ss = *s;
1145 :
1146 0 : if (ignore_case != 0) {
1147 0 : if (string_cmp_ic(reg->enc, ambig_flag,
1148 : pstart, &ss, (int )(pend - pstart)) == 0)
1149 0 : return 0; /* or goto next_mem; */
1150 : }
1151 : else {
1152 0 : while (p < pend) {
1153 0 : if (*p++ != *ss++) return 0; /* or goto next_mem; */
1154 : }
1155 : }
1156 :
1157 0 : *s = ss;
1158 0 : return 1;
1159 : }
1160 : }
1161 : }
1162 0 : else if (k->type == STK_MEM_END) {
1163 0 : if (mem_is_in_memp(k->u.mem.num, mem_num, memp)) {
1164 0 : pend = k->u.mem.pstr;
1165 : }
1166 : }
1167 : }
1168 0 : k--;
1169 : }
1170 :
1171 0 : return 0;
1172 : }
1173 : #endif /* USE_BACKREF_AT_LEVEL */
1174 :
1175 :
1176 : #ifdef RUBY_PLATFORM
1177 :
1178 : typedef struct {
1179 : int state;
1180 : regex_t* reg;
1181 : MatchArg* msa;
1182 : StackType* stk_base;
1183 : } TrapEnsureArg;
1184 :
1185 : static VALUE
1186 : trap_ensure(VALUE arg)
1187 : {
1188 : TrapEnsureArg* ta = (TrapEnsureArg* )arg;
1189 :
1190 : if (ta->state == 0) { /* trap_exec() is not normal return */
1191 : ONIG_STATE_DEC_THREAD(ta->reg);
1192 : if (! IS_NULL(ta->msa->stack_p) && ta->stk_base != ta->msa->stack_p)
1193 : xfree(ta->stk_base);
1194 :
1195 : MATCH_ARG_FREE(*(ta->msa));
1196 : }
1197 :
1198 : return Qnil;
1199 : }
1200 :
1201 : static VALUE
1202 : trap_exec(VALUE arg)
1203 : {
1204 : TrapEnsureArg* ta;
1205 :
1206 : rb_trap_exec();
1207 :
1208 : ta = (TrapEnsureArg* )arg;
1209 : ta->state = 1; /* normal return */
1210 : return Qnil;
1211 : }
1212 :
1213 : extern void
1214 : onig_exec_trap(regex_t* reg, MatchArg* msa, StackType* stk_base)
1215 : {
1216 : VALUE arg;
1217 : TrapEnsureArg ta;
1218 :
1219 : ta.state = 0;
1220 : ta.reg = reg;
1221 : ta.msa = msa;
1222 : ta.stk_base = stk_base;
1223 : arg = (VALUE )(&ta);
1224 : rb_ensure(trap_exec, arg, trap_ensure, arg);
1225 : }
1226 :
1227 : #define CHECK_INTERRUPT_IN_MATCH_AT do {\
1228 : if (rb_trap_pending) {\
1229 : if (! rb_prohibit_interrupt) {\
1230 : onig_exec_trap(reg, msa, stk_base);\
1231 : }\
1232 : }\
1233 : } while (0)
1234 : #else
1235 : #define CHECK_INTERRUPT_IN_MATCH_AT
1236 : #endif /* RUBY_PLATFORM */
1237 :
1238 : #ifdef ONIG_DEBUG_STATISTICS
1239 :
1240 : #define USE_TIMEOFDAY
1241 :
1242 : #ifdef USE_TIMEOFDAY
1243 : #ifdef HAVE_SYS_TIME_H
1244 : #include <sys/time.h>
1245 : #endif
1246 : #ifdef HAVE_UNISTD_H
1247 : #include <unistd.h>
1248 : #endif
1249 : static struct timeval ts, te;
1250 : #define GETTIME(t) gettimeofday(&(t), (struct timezone* )0)
1251 : #define TIMEDIFF(te,ts) (((te).tv_usec - (ts).tv_usec) + \
1252 : (((te).tv_sec - (ts).tv_sec)*1000000))
1253 : #else
1254 : #ifdef HAVE_SYS_TIMES_H
1255 : #include <sys/times.h>
1256 : #endif
1257 : static struct tms ts, te;
1258 : #define GETTIME(t) times(&(t))
1259 : #define TIMEDIFF(te,ts) ((te).tms_utime - (ts).tms_utime)
1260 : #endif
1261 :
1262 : static int OpCounter[256];
1263 : static int OpPrevCounter[256];
1264 : static unsigned long OpTime[256];
1265 : static int OpCurr = OP_FINISH;
1266 : static int OpPrevTarget = OP_FAIL;
1267 : static int MaxStackDepth = 0;
1268 :
1269 : #define STAT_OP_IN(opcode) do {\
1270 : if (opcode == OpPrevTarget) OpPrevCounter[OpCurr]++;\
1271 : OpCurr = opcode;\
1272 : OpCounter[opcode]++;\
1273 : GETTIME(ts);\
1274 : } while (0)
1275 :
1276 : #define STAT_OP_OUT do {\
1277 : GETTIME(te);\
1278 : OpTime[OpCurr] += TIMEDIFF(te, ts);\
1279 : } while (0)
1280 :
1281 : #ifdef RUBY_PLATFORM
1282 :
1283 : /*
1284 : * :nodoc:
1285 : */
1286 : static VALUE onig_stat_print()
1287 : {
1288 : onig_print_statistics(stderr);
1289 : return Qnil;
1290 : }
1291 : #endif
1292 :
1293 : extern void onig_statistics_init()
1294 : {
1295 : int i;
1296 : for (i = 0; i < 256; i++) {
1297 : OpCounter[i] = OpPrevCounter[i] = 0; OpTime[i] = 0;
1298 : }
1299 : MaxStackDepth = 0;
1300 :
1301 : #ifdef RUBY_PLATFORM
1302 : rb_define_global_function("onig_stat_print", onig_stat_print, 0);
1303 : #endif
1304 : }
1305 :
1306 : extern void
1307 : onig_print_statistics(FILE* f)
1308 : {
1309 : int i;
1310 : fprintf(f, " count prev time\n");
1311 : for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
1312 : fprintf(f, "%8d: %8d: %10ld: %s\n",
1313 : OpCounter[i], OpPrevCounter[i], OpTime[i], OnigOpInfo[i].name);
1314 : }
1315 : fprintf(f, "\nmax stack depth: %d\n", MaxStackDepth);
1316 : }
1317 :
1318 : #define STACK_INC do {\
1319 : stk++;\
1320 : if (stk - stk_base > MaxStackDepth) \
1321 : MaxStackDepth = stk - stk_base;\
1322 : } while (0)
1323 :
1324 : #else
1325 : #define STACK_INC stk++
1326 :
1327 : #define STAT_OP_IN(opcode)
1328 : #define STAT_OP_OUT
1329 : #endif
1330 :
1331 : extern int
1332 : onig_is_in_code_range(const UChar* p, OnigCodePoint code)
1333 435 : {
1334 : OnigCodePoint n, *data;
1335 : OnigCodePoint low, high, x;
1336 :
1337 435 : GET_CODE_POINT(n, p);
1338 435 : data = (OnigCodePoint* )p;
1339 435 : data++;
1340 :
1341 3031 : for (low = 0, high = n; low < high; ) {
1342 2161 : x = (low + high) >> 1;
1343 2161 : if (code > data[x * 2 + 1])
1344 1172 : low = x + 1;
1345 : else
1346 989 : high = x;
1347 : }
1348 :
1349 435 : return ((low < n && code >= data[low * 2]) ? 1 : 0);
1350 : }
1351 :
1352 : static int
1353 : is_code_in_cc(int enclen, OnigCodePoint code, CClassNode* cc)
1354 280 : {
1355 : int found;
1356 :
1357 398 : if (enclen > 1 || (code >= SINGLE_BYTE_SIZE)) {
1358 118 : if (IS_NULL(cc->mbuf)) {
1359 59 : found = 0;
1360 : }
1361 : else {
1362 59 : found = (onig_is_in_code_range(cc->mbuf->p, code) != 0 ? 1 : 0);
1363 : }
1364 : }
1365 : else {
1366 162 : found = (BITSET_AT(cc->bs, code) == 0 ? 0 : 1);
1367 : }
1368 :
1369 280 : if (IS_CCLASS_NOT(cc))
1370 65 : return !found;
1371 : else
1372 215 : return found;
1373 : }
1374 :
1375 : extern int
1376 : onig_is_code_in_cc(OnigEncoding enc, OnigCodePoint code, CClassNode* cc)
1377 127 : {
1378 : int len;
1379 :
1380 127 : if (ONIGENC_MBC_MINLEN(enc) > 1) {
1381 0 : len = 2;
1382 : }
1383 : else {
1384 127 : len = ONIGENC_CODE_TO_MBCLEN(enc, code);
1385 : }
1386 127 : return is_code_in_cc(len, code, cc);
1387 : }
1388 :
1389 :
1390 : /* matching region of POSIX API */
1391 : typedef int regoff_t;
1392 :
1393 : typedef struct {
1394 : regoff_t rm_so;
1395 : regoff_t rm_eo;
1396 : } posix_regmatch_t;
1397 :
1398 : /* match data(str - end) from position (sstart). */
1399 : /* if sstart == str then set sprev to NULL. */
1400 : static int
1401 : match_at(regex_t* reg, const UChar* str, const UChar* end, const UChar* sstart,
1402 : UChar* sprev, MatchArg* msa)
1403 752 : {
1404 : static UChar FinishCode[] = { OP_FINISH };
1405 :
1406 : int i, n, num_mem, best_len, pop_level;
1407 : LengthType tlen, tlen2;
1408 : MemNumType mem;
1409 : RelAddrType addr;
1410 752 : OnigOptionType option = reg->options;
1411 752 : OnigEncoding encode = reg->enc;
1412 752 : OnigAmbigType ambig_flag = reg->ambig_flag;
1413 : UChar *s, *q, *sbegin;
1414 752 : UChar *p = reg->p;
1415 : char *alloca_base;
1416 : StackType *stk_alloc, *stk_base, *stk, *stk_end;
1417 : StackType *stkp; /* used as any purpose. */
1418 : StackIndex si;
1419 : StackIndex *repeat_stk;
1420 : StackIndex *mem_start_stk, *mem_end_stk;
1421 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
1422 : int scv;
1423 752 : unsigned char* state_check_buff = msa->state_check_buff;
1424 752 : int num_comb_exp_check = reg->num_comb_exp_check;
1425 : #endif
1426 752 : n = reg->num_repeat + reg->num_mem * 2;
1427 :
1428 752 : STACK_INIT(alloca_base, n, INIT_MATCH_STACK_SIZE);
1429 752 : pop_level = reg->stack_pop_level;
1430 752 : num_mem = reg->num_mem;
1431 752 : repeat_stk = (StackIndex* )alloca_base;
1432 :
1433 752 : mem_start_stk = (StackIndex* )(repeat_stk + reg->num_repeat);
1434 752 : mem_end_stk = mem_start_stk + num_mem;
1435 752 : mem_start_stk--; /* for index start from 1,
1436 : mem_start_stk[1]..mem_start_stk[num_mem] */
1437 752 : mem_end_stk--; /* for index start from 1,
1438 : mem_end_stk[1]..mem_end_stk[num_mem] */
1439 869 : for (i = 1; i <= num_mem; i++) {
1440 117 : mem_start_stk[i] = mem_end_stk[i] = INVALID_STACK_INDEX;
1441 : }
1442 :
1443 : #ifdef ONIG_DEBUG_MATCH
1444 : fprintf(stderr, "match_at: str: %d, end: %d, start: %d, sprev: %d\n",
1445 : (int )str, (int )end, (int )sstart, (int )sprev);
1446 : fprintf(stderr, "size: %d, start offset: %d\n",
1447 : (int )(end - str), (int )(sstart - str));
1448 : #endif
1449 :
1450 752 : STACK_PUSH_ENSURED(STK_ALT, FinishCode); /* bottom stack */
1451 752 : best_len = ONIG_MISMATCH;
1452 752 : s = (UChar* )sstart;
1453 : while (1) {
1454 : #ifdef ONIG_DEBUG_MATCH
1455 : {
1456 : UChar *q, *bp, buf[50];
1457 : int len;
1458 : fprintf(stderr, "%4d> \"", (int )(s - str));
1459 : bp = buf;
1460 : for (i = 0, q = s; i < 7 && q < end; i++) {
1461 : len = enc_len(encode, q);
1462 : while (len-- > 0) *bp++ = *q++;
1463 : }
1464 : if (q < end) { xmemcpy(bp, "...\"", 4); bp += 4; }
1465 : else { xmemcpy(bp, "\"", 1); bp += 1; }
1466 : *bp = 0;
1467 : fputs(buf, stderr);
1468 : for (i = 0; i < 20 - (bp - buf); i++) fputc(' ', stderr);
1469 : onig_print_compiled_byte_code(stderr, p, NULL, encode);
1470 : fprintf(stderr, "\n");
1471 : }
1472 : #endif
1473 :
1474 5155 : sbegin = s;
1475 5155 : switch (*p++) {
1476 : case OP_END: STAT_OP_IN(OP_END);
1477 535 : n = s - sstart;
1478 535 : if (n > best_len) {
1479 535 : OnigRegion* region = msa->region;
1480 535 : best_len = n;
1481 535 : if (region) {
1482 : #ifdef USE_POSIX_REGION_OPTION
1483 533 : if (IS_POSIX_REGION(msa->options)) {
1484 0 : posix_regmatch_t* rmt = (posix_regmatch_t* )region;
1485 :
1486 0 : rmt[0].rm_so = sstart - str;
1487 0 : rmt[0].rm_eo = s - str;
1488 0 : for (i = 1; i <= num_mem; i++) {
1489 0 : if (mem_end_stk[i] != INVALID_STACK_INDEX) {
1490 0 : if (BIT_STATUS_AT(reg->bt_mem_start, i))
1491 0 : rmt[i].rm_so = STACK_AT(mem_start_stk[i])->u.mem.pstr - str;
1492 : else
1493 0 : rmt[i].rm_so = (UChar* )((void* )(mem_start_stk[i])) - str;
1494 :
1495 0 : rmt[i].rm_eo = (BIT_STATUS_AT(reg->bt_mem_end, i)
1496 : ? STACK_AT(mem_end_stk[i])->u.mem.pstr
1497 : : (UChar* )((void* )mem_end_stk[i])) - str;
1498 : }
1499 : else {
1500 0 : rmt[i].rm_so = rmt[i].rm_eo = ONIG_REGION_NOTPOS;
1501 : }
1502 : }
1503 : }
1504 : else {
1505 : #endif /* USE_POSIX_REGION_OPTION */
1506 533 : region->beg[0] = sstart - str;
1507 533 : region->end[0] = s - str;
1508 649 : for (i = 1; i <= num_mem; i++) {
1509 116 : if (mem_end_stk[i] != INVALID_STACK_INDEX) {
1510 116 : if (BIT_STATUS_AT(reg->bt_mem_start, i))
1511 3 : region->beg[i] = STACK_AT(mem_start_stk[i])->u.mem.pstr - str;
1512 : else
1513 113 : region->beg[i] = (UChar* )((void* )mem_start_stk[i]) - str;
1514 :
1515 116 : region->end[i] = (BIT_STATUS_AT(reg->bt_mem_end, i)
1516 : ? STACK_AT(mem_end_stk[i])->u.mem.pstr
1517 : : (UChar* )((void* )mem_end_stk[i])) - str;
1518 : }
1519 : else {
1520 0 : region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;
1521 : }
1522 : }
1523 :
1524 : #ifdef USE_CAPTURE_HISTORY
1525 533 : if (reg->capture_history != 0) {
1526 : int r;
1527 : OnigCaptureTreeNode* node;
1528 :
1529 0 : if (IS_NULL(region->history_root)) {
1530 0 : region->history_root = node = history_node_new();
1531 0 : CHECK_NULL_RETURN_VAL(node, ONIGERR_MEMORY);
1532 : }
1533 : else {
1534 0 : node = region->history_root;
1535 0 : history_tree_clear(node);
1536 : }
1537 :
1538 0 : node->group = 0;
1539 0 : node->beg = sstart - str;
1540 0 : node->end = s - str;
1541 :
1542 0 : stkp = stk_base;
1543 0 : r = make_capture_history_tree(region->history_root, &stkp,
1544 : stk, (UChar* )str, reg);
1545 0 : if (r < 0) {
1546 0 : best_len = r; /* error code */
1547 0 : goto finish;
1548 : }
1549 : }
1550 : #endif /* USE_CAPTURE_HISTORY */
1551 : #ifdef USE_POSIX_REGION_OPTION
1552 : } /* else IS_POSIX_REGION() */
1553 : #endif
1554 : } /* if (region) */
1555 : } /* n > best_len */
1556 : STAT_OP_OUT;
1557 :
1558 535 : if (IS_FIND_CONDITION(option)) {
1559 0 : if (IS_FIND_NOT_EMPTY(option) && s == sstart) {
1560 0 : best_len = ONIG_MISMATCH;
1561 0 : goto fail; /* for retry */
1562 : }
1563 0 : if (IS_FIND_LONGEST(option) && s < end) {
1564 0 : goto fail; /* for retry */
1565 : }
1566 : }
1567 :
1568 : /* default behavior: return first-matching result. */
1569 535 : goto finish;
1570 : break;
1571 :
1572 : case OP_EXACT1: STAT_OP_IN(OP_EXACT1);
1573 : #if 0
1574 : DATA_ENSURE(1);
1575 : if (*p != *s) goto fail;
1576 : p++; s++;
1577 : #endif
1578 157 : if (*p != *s++) goto fail;
1579 88 : DATA_ENSURE(0);
1580 88 : p++;
1581 : STAT_OP_OUT;
1582 88 : break;
1583 :
1584 : case OP_EXACT1_IC: STAT_OP_IN(OP_EXACT1_IC);
1585 : {
1586 : int len;
1587 : UChar *q, *ss, *sp, lowbuf[ONIGENC_MBC_NORMALIZE_MAXLEN];
1588 :
1589 0 : DATA_ENSURE(1);
1590 0 : ss = s;
1591 0 : sp = p;
1592 :
1593 0 : exact1_ic_retry:
1594 0 : len = ONIGENC_MBC_TO_NORMALIZE(encode, ambig_flag, &s, end, lowbuf);
1595 0 : DATA_ENSURE(0);
1596 0 : q = lowbuf;
1597 0 : while (len-- > 0) {
1598 0 : if (*p != *q) {
1599 : #if 1
1600 0 : if ((ambig_flag & ONIGENC_AMBIGUOUS_MATCH_COMPOUND) != 0) {
1601 0 : ambig_flag &= ~ONIGENC_AMBIGUOUS_MATCH_COMPOUND;
1602 0 : s = ss;
1603 0 : p = sp;
1604 0 : goto exact1_ic_retry;
1605 : }
1606 : else
1607 0 : goto fail;
1608 : #else
1609 : goto fail;
1610 : #endif
1611 : }
1612 0 : p++; q++;
1613 : }
1614 : }
1615 : STAT_OP_OUT;
1616 0 : break;
1617 :
1618 : case OP_EXACT2: STAT_OP_IN(OP_EXACT2);
1619 123 : DATA_ENSURE(2);
1620 116 : if (*p != *s) goto fail;
1621 52 : p++; s++;
1622 52 : if (*p != *s) goto fail;
1623 44 : sprev = s;
1624 44 : p++; s++;
1625 : STAT_OP_OUT;
1626 44 : continue;
1627 : break;
1628 :
1629 : case OP_EXACT3: STAT_OP_IN(OP_EXACT3);
1630 12 : DATA_ENSURE(3);
1631 10 : if (*p != *s) goto fail;
1632 9 : p++; s++;
1633 9 : if (*p != *s) goto fail;
1634 9 : p++; s++;
1635 9 : if (*p != *s) goto fail;
1636 9 : sprev = s;
1637 9 : p++; s++;
1638 : STAT_OP_OUT;
1639 9 : continue;
1640 : break;
1641 :
1642 : case OP_EXACT4: STAT_OP_IN(OP_EXACT4);
1643 6 : DATA_ENSURE(4);
1644 6 : if (*p != *s) goto fail;
1645 6 : p++; s++;
1646 6 : if (*p != *s) goto fail;
1647 6 : p++; s++;
1648 6 : if (*p != *s) goto fail;
1649 6 : p++; s++;
1650 6 : if (*p != *s) goto fail;
1651 6 : sprev = s;
1652 6 : p++; s++;
1653 : STAT_OP_OUT;
1654 6 : continue;
1655 : break;
1656 :
1657 : case OP_EXACT5: STAT_OP_IN(OP_EXACT5);
1658 1 : DATA_ENSURE(5);
1659 1 : if (*p != *s) goto fail;
1660 1 : p++; s++;
1661 1 : if (*p != *s) goto fail;
1662 1 : p++; s++;
1663 1 : if (*p != *s) goto fail;
1664 1 : p++; s++;
1665 1 : if (*p != *s) goto fail;
1666 1 : p++; s++;
1667 1 : if (*p != *s) goto fail;
1668 1 : sprev = s;
1669 1 : p++; s++;
1670 : STAT_OP_OUT;
1671 1 : continue;
1672 : break;
1673 :
1674 : case OP_EXACTN: STAT_OP_IN(OP_EXACTN);
1675 6 : GET_LENGTH_INC(tlen, p);
1676 6 : DATA_ENSURE(tlen);
1677 36 : while (tlen-- > 0) {
1678 29 : if (*p++ != *s++) goto fail;
1679 : }
1680 3 : sprev = s - 1;
1681 : STAT_OP_OUT;
1682 3 : continue;
1683 : break;
1684 :
1685 : case OP_EXACTN_IC: STAT_OP_IN(OP_EXACTN_IC);
1686 : {
1687 : int len;
1688 : UChar *ss, *sp, *q, *endp, lowbuf[ONIGENC_MBC_NORMALIZE_MAXLEN];
1689 :
1690 1 : GET_LENGTH_INC(tlen, p);
1691 1 : endp = p + tlen;
1692 :
1693 4 : while (p < endp) {
1694 2 : sprev = s;
1695 2 : DATA_ENSURE(1);
1696 2 : ss = s;
1697 2 : sp = p;
1698 :
1699 2 : exactn_ic_retry:
1700 2 : len = ONIGENC_MBC_TO_NORMALIZE(encode, ambig_flag, &s, end, lowbuf);
1701 2 : DATA_ENSURE(0);
1702 2 : q = lowbuf;
1703 6 : while (len-- > 0) {
1704 2 : if (*p != *q) {
1705 : #if 1
1706 0 : if ((ambig_flag & ONIGENC_AMBIGUOUS_MATCH_COMPOUND) != 0) {
1707 0 : ambig_flag &= ~ONIGENC_AMBIGUOUS_MATCH_COMPOUND;
1708 0 : s = ss;
1709 0 : p = sp;
1710 0 : goto exactn_ic_retry;
1711 : }
1712 : else
1713 0 : goto fail;
1714 : #else
1715 : goto fail;
1716 : #endif
1717 : }
1718 2 : p++; q++;
1719 : }
1720 : }
1721 : }
1722 :
1723 : STAT_OP_OUT;
1724 1 : continue;
1725 : break;
1726 :
1727 : case OP_EXACTMB2N1: STAT_OP_IN(OP_EXACTMB2N1);
1728 80 : DATA_ENSURE(2);
1729 69 : if (*p != *s) goto fail;
1730 42 : p++; s++;
1731 42 : if (*p != *s) goto fail;
1732 34 : p++; s++;
1733 : STAT_OP_OUT;
1734 34 : break;
1735 :
1736 : case OP_EXACTMB2N2: STAT_OP_IN(OP_EXACTMB2N2);
1737 0 : DATA_ENSURE(4);
1738 0 : if (*p != *s) goto fail;
1739 0 : p++; s++;
1740 0 : if (*p != *s) goto fail;
1741 0 : p++; s++;
1742 0 : sprev = s;
1743 0 : if (*p != *s) goto fail;
1744 0 : p++; s++;
1745 0 : if (*p != *s) goto fail;
1746 0 : p++; s++;
1747 : STAT_OP_OUT;
1748 0 : continue;
1749 : break;
1750 :
1751 : case OP_EXACTMB2N3: STAT_OP_IN(OP_EXACTMB2N3);
1752 0 : DATA_ENSURE(6);
1753 0 : if (*p != *s) goto fail;
1754 0 : p++; s++;
1755 0 : if (*p != *s) goto fail;
1756 0 : p++; s++;
1757 0 : if (*p != *s) goto fail;
1758 0 : p++; s++;
1759 0 : if (*p != *s) goto fail;
1760 0 : p++; s++;
1761 0 : sprev = s;
1762 0 : if (*p != *s) goto fail;
1763 0 : p++; s++;
1764 0 : if (*p != *s) goto fail;
1765 0 : p++; s++;
1766 : STAT_OP_OUT;
1767 0 : continue;
1768 : break;
1769 :
1770 : case OP_EXACTMB2N: STAT_OP_IN(OP_EXACTMB2N);
1771 0 : GET_LENGTH_INC(tlen, p);
1772 0 : DATA_ENSURE(tlen * 2);
1773 0 : while (tlen-- > 0) {
1774 0 : if (*p != *s) goto fail;
1775 0 : p++; s++;
1776 0 : if (*p != *s) goto fail;
1777 0 : p++; s++;
1778 : }
1779 0 : sprev = s - 2;
1780 : STAT_OP_OUT;
1781 0 : continue;
1782 : break;
1783 :
1784 : case OP_EXACTMB3N: STAT_OP_IN(OP_EXACTMB3N);
1785 14 : GET_LENGTH_INC(tlen, p);
1786 14 : DATA_ENSURE(tlen * 3);
1787 42 : while (tlen-- > 0) {
1788 20 : if (*p != *s) goto fail;
1789 18 : p++; s++;
1790 18 : if (*p != *s) goto fail;
1791 18 : p++; s++;
1792 18 : if (*p != *s) goto fail;
1793 18 : p++; s++;
1794 : }
1795 10 : sprev = s - 3;
1796 : STAT_OP_OUT;
1797 10 : continue;
1798 : break;
1799 :
1800 : case OP_EXACTMBN: STAT_OP_IN(OP_EXACTMBN);
1801 0 : GET_LENGTH_INC(tlen, p); /* mb-len */
1802 0 : GET_LENGTH_INC(tlen2, p); /* string len */
1803 0 : tlen2 *= tlen;
1804 0 : DATA_ENSURE(tlen2);
1805 0 : while (tlen2-- > 0) {
1806 0 : if (*p != *s) goto fail;
1807 0 : p++; s++;
1808 : }
1809 0 : sprev = s - tlen;
1810 : STAT_OP_OUT;
1811 0 : continue;
1812 : break;
1813 :
1814 : case OP_CCLASS: STAT_OP_IN(OP_CCLASS);
1815 660 : DATA_ENSURE(1);
1816 651 : if (BITSET_AT(((BitSetRef )p), *s) == 0) goto fail;
1817 569 : p += SIZE_BITSET;
1818 569 : s += enc_len(encode, s); /* OP_CCLASS can match mb-code. \D, \S */
1819 : STAT_OP_OUT;
1820 569 : break;
1821 :
1822 : case OP_CCLASS_MB: STAT_OP_IN(OP_CCLASS_MB);
1823 93 : if (! ONIGENC_IS_MBC_HEAD(encode, s)) goto fail;
1824 :
1825 329 : cclass_mb:
1826 329 : GET_LENGTH_INC(tlen, p);
1827 : {
1828 : OnigCodePoint code;
1829 : UChar *ss;
1830 : int mb_len;
1831 :
1832 329 : DATA_ENSURE(1);
1833 329 : mb_len = enc_len(encode, s);
1834 329 : DATA_ENSURE(mb_len);
1835 329 : ss = s;
1836 329 : s += mb_len;
1837 329 : code = ONIGENC_MBC_TO_CODE(encode, ss, s);
1838 :
1839 : #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
1840 329 : if (! onig_is_in_code_range(p, code)) goto fail;
1841 : #else
1842 : q = p;
1843 : ALIGNMENT_RIGHT(q);
1844 : if (! onig_is_in_code_range(q, code)) goto fail;
1845 : #endif
1846 : }
1847 182 : p += tlen;
1848 : STAT_OP_OUT;
1849 182 : break;
1850 :
1851 : case OP_CCLASS_MIX: STAT_OP_IN(OP_CCLASS_MIX);
1852 526 : DATA_ENSURE(1);
1853 502 : if (ONIGENC_IS_MBC_HEAD(encode, s)) {
1854 260 : p += SIZE_BITSET;
1855 260 : goto cclass_mb;
1856 : }
1857 : else {
1858 242 : if (BITSET_AT(((BitSetRef )p), *s) == 0)
1859 135 : goto fail;
1860 :
1861 107 : p += SIZE_BITSET;
1862 107 : GET_LENGTH_INC(tlen, p);
1863 107 : p += tlen;
1864 107 : s++;
1865 : }
1866 : STAT_OP_OUT;
1867 107 : break;
1868 :
1869 : case OP_CCLASS_NOT: STAT_OP_IN(OP_CCLASS_NOT);
1870 5 : DATA_ENSURE(1);
1871 5 : if (BITSET_AT(((BitSetRef )p), *s) != 0) goto fail;
1872 4 : p += SIZE_BITSET;
1873 4 : s += enc_len(encode, s);
1874 : STAT_OP_OUT;
1875 4 : break;
1876 :
1877 : case OP_CCLASS_MB_NOT: STAT_OP_IN(OP_CCLASS_MB_NOT);
1878 0 : DATA_ENSURE(1);
1879 0 : if (! ONIGENC_IS_MBC_HEAD(encode, s)) {
1880 0 : s++;
1881 0 : GET_LENGTH_INC(tlen, p);
1882 0 : p += tlen;
1883 0 : goto cc_mb_not_success;
1884 : }
1885 :
1886 0 : cclass_mb_not:
1887 0 : GET_LENGTH_INC(tlen, p);
1888 : {
1889 : OnigCodePoint code;
1890 : UChar *ss;
1891 0 : int mb_len = enc_len(encode, s);
1892 :
1893 0 : if (s + mb_len > end) {
1894 0 : DATA_ENSURE(1);
1895 0 : s = (UChar* )end;
1896 0 : p += tlen;
1897 0 : goto cc_mb_not_success;
1898 : }
1899 :
1900 0 : ss = s;
1901 0 : s += mb_len;
1902 0 : code = ONIGENC_MBC_TO_CODE(encode, ss, s);
1903 :
1904 : #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
1905 0 : if (onig_is_in_code_range(p, code)) goto fail;
1906 : #else
1907 : q = p;
1908 : ALIGNMENT_RIGHT(q);
1909 : if (onig_is_in_code_range(q, code)) goto fail;
1910 : #endif
1911 : }
1912 0 : p += tlen;
1913 :
1914 0 : cc_mb_not_success:
1915 : STAT_OP_OUT;
1916 0 : break;
1917 :
1918 : case OP_CCLASS_MIX_NOT: STAT_OP_IN(OP_CCLASS_MIX_NOT);
1919 0 : DATA_ENSURE(1);
1920 0 : if (ONIGENC_IS_MBC_HEAD(encode, s)) {
1921 0 : p += SIZE_BITSET;
1922 0 : goto cclass_mb_not;
1923 : }
1924 : else {
1925 0 : if (BITSET_AT(((BitSetRef )p), *s) != 0)
1926 0 : goto fail;
1927 :
1928 0 : p += SIZE_BITSET;
1929 0 : GET_LENGTH_INC(tlen, p);
1930 0 : p += tlen;
1931 0 : s++;
1932 : }
1933 : STAT_OP_OUT;
1934 0 : break;
1935 :
1936 : case OP_CCLASS_NODE: STAT_OP_IN(OP_CCLASS_NODE);
1937 : {
1938 : OnigCodePoint code;
1939 : void *node;
1940 : int mb_len;
1941 : UChar *ss;
1942 :
1943 157 : DATA_ENSURE(1);
1944 153 : GET_POINTER_INC(node, p);
1945 153 : mb_len = enc_len(encode, s);
1946 153 : ss = s;
1947 153 : s += mb_len;
1948 153 : DATA_ENSURE(0);
1949 153 : code = ONIGENC_MBC_TO_CODE(encode, ss, s);
1950 153 : if (is_code_in_cc(mb_len, code, node) == 0) goto fail;
1951 : }
1952 : STAT_OP_OUT;
1953 85 : break;
1954 :
1955 : case OP_ANYCHAR: STAT_OP_IN(OP_ANYCHAR);
1956 0 : DATA_ENSURE(1);
1957 0 : n = enc_len(encode, s);
1958 0 : DATA_ENSURE(n);
1959 0 : if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;
1960 0 : s += n;
1961 : STAT_OP_OUT;
1962 0 : break;
1963 :
1964 : case OP_ANYCHAR_ML: STAT_OP_IN(OP_ANYCHAR_ML);
1965 94 : DATA_ENSURE(1);
1966 94 : n = enc_len(encode, s);
1967 94 : DATA_ENSURE(n);
1968 94 : s += n;
1969 : STAT_OP_OUT;
1970 94 : break;
1971 :
1972 : case OP_ANYCHAR_STAR: STAT_OP_IN(OP_ANYCHAR_STAR);
1973 20 : while (s < end) {
1974 18 : STACK_PUSH_ALT(p, s, sprev);
1975 18 : n = enc_len(encode, s);
1976 18 : DATA_ENSURE(n);
1977 18 : if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;
1978 18 : sprev = s;
1979 18 : s += n;
1980 : }
1981 : STAT_OP_OUT;
1982 1 : break;
1983 :
1984 : case OP_ANYCHAR_ML_STAR: STAT_OP_IN(OP_ANYCHAR_ML_STAR);
1985 5 : while (s < end) {
1986 1 : STACK_PUSH_ALT(p, s, sprev);
1987 1 : n = enc_len(encode, s);
1988 1 : if (n > 1) {
1989 0 : DATA_ENSURE(n);
1990 0 : sprev = s;
1991 0 : s += n;
1992 : }
1993 : else {
1994 1 : sprev = s;
1995 1 : s++;
1996 : }
1997 : }
1998 : STAT_OP_OUT;
1999 2 : break;
2000 :
2001 : case OP_ANYCHAR_STAR_PEEK_NEXT: STAT_OP_IN(OP_ANYCHAR_STAR_PEEK_NEXT);
2002 0 : while (s < end) {
2003 0 : if (*p == *s) {
2004 0 : STACK_PUSH_ALT(p + 1, s, sprev);
2005 : }
2006 0 : n = enc_len(encode, s);
2007 0 : DATA_ENSURE(n);
2008 0 : if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;
2009 0 : sprev = s;
2010 0 : s += n;
2011 : }
2012 0 : p++;
2013 : STAT_OP_OUT;
2014 0 : break;
2015 :
2016 : case OP_ANYCHAR_ML_STAR_PEEK_NEXT:STAT_OP_IN(OP_ANYCHAR_ML_STAR_PEEK_NEXT);
2017 219 : while (s < end) {
2018 203 : if (*p == *s) {
2019 21 : STACK_PUSH_ALT(p + 1, s, sprev);
2020 : }
2021 203 : n = enc_len(encode, s);
2022 203 : if (n >1) {
2023 0 : DATA_ENSURE(n);
2024 0 : sprev = s;
2025 0 : s += n;
2026 : }
2027 : else {
2028 203 : sprev = s;
2029 203 : s++;
2030 : }
2031 : }
2032 8 : p++;
2033 : STAT_OP_OUT;
2034 8 : break;
2035 :
2036 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
2037 : case OP_STATE_CHECK_ANYCHAR_STAR: STAT_OP_IN(OP_STATE_CHECK_ANYCHAR_STAR);
2038 0 : GET_STATE_CHECK_NUM_INC(mem, p);
2039 0 : while (s < end) {
2040 0 : STATE_CHECK_VAL(scv, mem);
2041 0 : if (scv) goto fail;
2042 :
2043 0 : STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem);
2044 0 : n = enc_len(encode, s);
2045 0 : DATA_ENSURE(n);
2046 0 : if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) goto fail;
2047 0 : sprev = s;
2048 0 : s += n;
2049 : }
2050 : STAT_OP_OUT;
2051 0 : break;
2052 :
2053 : case OP_STATE_CHECK_ANYCHAR_ML_STAR:
2054 : STAT_OP_IN(OP_STATE_CHECK_ANYCHAR_ML_STAR);
2055 :
2056 13 : GET_STATE_CHECK_NUM_INC(mem, p);
2057 241 : while (s < end) {
2058 218 : STATE_CHECK_VAL(scv, mem);
2059 218 : if (scv) goto fail;
2060 :
2061 215 : STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem);
2062 215 : n = enc_len(encode, s);
2063 215 : if (n > 1) {
2064 8 : DATA_ENSURE(n);
2065 8 : sprev = s;
2066 8 : s += n;
2067 : }
2068 : else {
2069 207 : sprev = s;
2070 207 : s++;
2071 : }
2072 : }
2073 : STAT_OP_OUT;
2074 10 : break;
2075 : #endif /* USE_COMBINATION_EXPLOSION_CHECK */
2076 :
2077 : case OP_WORD: STAT_OP_IN(OP_WORD);
2078 46 : DATA_ENSURE(1);
2079 46 : if (! ONIGENC_IS_MBC_WORD(encode, s, end))
2080 7 : goto fail;
2081 :
2082 39 : s += enc_len(encode, s);
2083 : STAT_OP_OUT;
2084 39 : break;
2085 :
2086 : case OP_NOT_WORD: STAT_OP_IN(OP_NOT_WORD);
2087 17 : DATA_ENSURE(1);
2088 17 : if (ONIGENC_IS_MBC_WORD(encode, s, end))
2089 15 : goto fail;
2090 :
2091 2 : s += enc_len(encode, s);
2092 : STAT_OP_OUT;
2093 2 : break;
2094 :
2095 : case OP_WORD_BOUND: STAT_OP_IN(OP_WORD_BOUND);
2096 2 : if (ON_STR_BEGIN(s)) {
2097 2 : DATA_ENSURE(1);
2098 2 : if (! ONIGENC_IS_MBC_WORD(encode, s, end))
2099 0 : goto fail;
2100 : }
2101 0 : else if (ON_STR_END(s)) {
2102 0 : if (! ONIGENC_IS_MBC_WORD(encode, sprev, end))
2103 0 : goto fail;
2104 : }
2105 : else {
2106 0 : if (ONIGENC_IS_MBC_WORD(encode, s, end)
2107 : == ONIGENC_IS_MBC_WORD(encode, sprev, end))
2108 0 : goto fail;
2109 : }
2110 : STAT_OP_OUT;
2111 2 : continue;
2112 : break;
2113 :
2114 : case OP_NOT_WORD_BOUND: STAT_OP_IN(OP_NOT_WORD_BOUND);
2115 4 : if (ON_STR_BEGIN(s)) {
2116 2 : if (DATA_ENSURE_CHECK(1) && ONIGENC_IS_MBC_WORD(encode, s, end))
2117 2 : goto fail;
2118 : }
2119 2 : else if (ON_STR_END(s)) {
2120 0 : if (ONIGENC_IS_MBC_WORD(encode, sprev, end))
2121 0 : goto fail;
2122 : }
2123 : else {
2124 2 : if (ONIGENC_IS_MBC_WORD(encode, s, end)
2125 : != ONIGENC_IS_MBC_WORD(encode, sprev, end))
2126 0 : goto fail;
2127 : }
2128 : STAT_OP_OUT;
2129 2 : continue;
2130 : break;
2131 :
2132 : #ifdef USE_WORD_BEGIN_END
2133 : case OP_WORD_BEGIN: STAT_OP_IN(OP_WORD_BEGIN);
2134 0 : if (DATA_ENSURE_CHECK(1) && ONIGENC_IS_MBC_WORD(encode, s, end)) {
2135 0 : if (ON_STR_BEGIN(s) || !ONIGENC_IS_MBC_WORD(encode, sprev, end)) {
2136 : STAT_OP_OUT;
2137 : continue;
2138 : }
2139 : }
2140 0 : goto fail;
2141 : break;
2142 :
2143 : case OP_WORD_END: STAT_OP_IN(OP_WORD_END);
2144 0 : if (!ON_STR_BEGIN(s) && ONIGENC_IS_MBC_WORD(encode, sprev, end)) {
2145 0 : if (ON_STR_END(s) || !ONIGENC_IS_MBC_WORD(encode, s, end)) {
2146 : STAT_OP_OUT;
2147 : continue;
2148 : }
2149 : }
2150 0 : goto fail;
2151 : break;
2152 : #endif
2153 :
2154 : case OP_BEGIN_BUF: STAT_OP_IN(OP_BEGIN_BUF);
2155 8 : if (! ON_STR_BEGIN(s)) goto fail;
2156 :
2157 : STAT_OP_OUT;
2158 7 : continue;
2159 : break;
2160 :
2161 : case OP_END_BUF: STAT_OP_IN(OP_END_BUF);
2162 18 : if (! ON_STR_END(s)) goto fail;
2163 :
2164 : STAT_OP_OUT;
2165 10 : continue;
2166 : break;
2167 :
2168 : case OP_BEGIN_LINE: STAT_OP_IN(OP_BEGIN_LINE);
2169 0 : if (ON_STR_BEGIN(s)) {
2170 0 : if (IS_NOTBOL(msa->options)) goto fail;
2171 : STAT_OP_OUT;
2172 0 : continue;
2173 : }
2174 0 : else if (ONIGENC_IS_MBC_NEWLINE(encode, sprev, end) && !ON_STR_END(s)) {
2175 : STAT_OP_OUT;
2176 0 : continue;
2177 : }
2178 0 : goto fail;
2179 : break;
2180 :
2181 : case OP_END_LINE: STAT_OP_IN(OP_END_LINE);
2182 12 : if (ON_STR_END(s)) {
2183 : #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
2184 : if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE(encode, sprev, end)) {
2185 : #endif
2186 12 : if (IS_NOTEOL(msa->options)) goto fail;
2187 : STAT_OP_OUT;
2188 12 : continue;
2189 : #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
2190 : }
2191 : #endif
2192 : }
2193 0 : else if (ONIGENC_IS_MBC_NEWLINE(encode, s, end)) {
2194 : STAT_OP_OUT;
2195 0 : continue;
2196 : }
2197 : #ifdef USE_CRNL_AS_LINE_TERMINATOR
2198 : else if (ONIGENC_IS_MBC_CRNL(encode, s, end)) {
2199 : STAT_OP_OUT;
2200 : continue;
2201 : }
2202 : #endif
2203 0 : goto fail;
2204 : break;
2205 :
2206 : case OP_SEMI_END_BUF: STAT_OP_IN(OP_SEMI_END_BUF);
2207 0 : if (ON_STR_END(s)) {
2208 : #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
2209 : if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE(encode, sprev, end)) {
2210 : #endif
2211 0 : if (IS_NOTEOL(msa->options)) goto fail; /* Is it needed? */
2212 : STAT_OP_OUT;
2213 0 : continue;
2214 : #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
2215 : }
2216 : #endif
2217 : }
2218 0 : else if (ONIGENC_IS_MBC_NEWLINE(encode, s, end) &&
2219 : ON_STR_END(s + enc_len(encode, s))) {
2220 : STAT_OP_OUT;
2221 0 : continue;
2222 : }
2223 : #ifdef USE_CRNL_AS_LINE_TERMINATOR
2224 : else if (ONIGENC_IS_MBC_CRNL(encode, s, end)) {
2225 : UChar* ss = s + enc_len(encode, s);
2226 : if (ON_STR_END(ss + enc_len(encode, ss))) {
2227 : STAT_OP_OUT;
2228 : continue;
2229 : }
2230 : }
2231 : #endif
2232 0 : goto fail;
2233 : break;
2234 :
2235 : case OP_BEGIN_POSITION: STAT_OP_IN(OP_BEGIN_POSITION);
2236 0 : if (s != msa->start)
2237 0 : goto fail;
2238 :
2239 : STAT_OP_OUT;
2240 0 : continue;
2241 : break;
2242 :
2243 : case OP_MEMORY_START_PUSH: STAT_OP_IN(OP_MEMORY_START_PUSH);
2244 9 : GET_MEMNUM_INC(mem, p);
2245 9 : STACK_PUSH_MEM_START(mem, s);
2246 : STAT_OP_OUT;
2247 9 : continue;
2248 : break;
2249 :
2250 : case OP_MEMORY_START: STAT_OP_IN(OP_MEMORY_START);
2251 195 : GET_MEMNUM_INC(mem, p);
2252 195 : mem_start_stk[mem] = (StackIndex )((void* )s);
2253 : STAT_OP_OUT;
2254 195 : continue;
2255 : break;
2256 :
2257 : case OP_MEMORY_END_PUSH: STAT_OP_IN(OP_MEMORY_END_PUSH);
2258 0 : GET_MEMNUM_INC(mem, p);
2259 0 : STACK_PUSH_MEM_END(mem, s);
2260 : STAT_OP_OUT;
2261 0 : continue;
2262 : break;
2263 :
2264 : case OP_MEMORY_END: STAT_OP_IN(OP_MEMORY_END);
2265 132 : GET_MEMNUM_INC(mem, p);
2266 132 : mem_end_stk[mem] = (StackIndex )((void* )s);
2267 : STAT_OP_OUT;
2268 132 : continue;
2269 : break;
2270 :
2271 : #ifdef USE_SUBEXP_CALL
2272 : case OP_MEMORY_END_PUSH_REC: STAT_OP_IN(OP_MEMORY_END_PUSH_REC);
2273 0 : GET_MEMNUM_INC(mem, p);
2274 0 : STACK_GET_MEM_START(mem, stkp); /* should be before push mem-end. */
2275 0 : STACK_PUSH_MEM_END(mem, s);
2276 0 : mem_start_stk[mem] = GET_STACK_INDEX(stkp);
2277 : STAT_OP_OUT;
2278 0 : continue;
2279 : break;
2280 :
2281 : case OP_MEMORY_END_REC: STAT_OP_IN(OP_MEMORY_END_REC);
2282 0 : GET_MEMNUM_INC(mem, p);
2283 0 : mem_end_stk[mem] = (StackIndex )((void* )s);
2284 0 : STACK_GET_MEM_START(mem, stkp);
2285 :
2286 0 : if (BIT_STATUS_AT(reg->bt_mem_start, mem))
2287 0 : mem_start_stk[mem] = GET_STACK_INDEX(stkp);
2288 : else
2289 0 : mem_start_stk[mem] = (StackIndex )((void* )stkp->u.mem.pstr);
2290 :
2291 0 : STACK_PUSH_MEM_END_MARK(mem);
2292 : STAT_OP_OUT;
2293 0 : continue;
2294 : break;
2295 : #endif
2296 :
2297 : case OP_BACKREF1: STAT_OP_IN(OP_BACKREF1);
2298 0 : mem = 1;
2299 0 : goto backref;
2300 : break;
2301 :
2302 : case OP_BACKREF2: STAT_OP_IN(OP_BACKREF2);
2303 0 : mem = 2;
2304 0 : goto backref;
2305 : break;
2306 :
2307 : case OP_BACKREFN: STAT_OP_IN(OP_BACKREFN);
2308 0 : GET_MEMNUM_INC(mem, p);
2309 0 : backref:
2310 : {
2311 : int len;
2312 : UChar *pstart, *pend;
2313 :
2314 : /* if you want to remove following line,
2315 : you should check in parse and compile time. */
2316 0 : if (mem > num_mem) goto fail;
2317 0 : if (mem_end_stk[mem] == INVALID_STACK_INDEX) goto fail;
2318 0 : if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;
2319 :
2320 0 : if (BIT_STATUS_AT(reg->bt_mem_start, mem))
2321 0 : pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
2322 : else
2323 0 : pstart = (UChar* )((void* )mem_start_stk[mem]);
2324 :
2325 0 : pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
2326 : ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
2327 : : (UChar* )((void* )mem_end_stk[mem]));
2328 0 : n = pend - pstart;
2329 0 : DATA_ENSURE(n);
2330 0 : sprev = s;
2331 0 : STRING_CMP(pstart, s, n);
2332 0 : while (sprev + (len = enc_len(encode, sprev)) < s)
2333 0 : sprev += len;
2334 :
2335 : STAT_OP_OUT;
2336 0 : continue;
2337 : }
2338 : break;
2339 :
2340 : case OP_BACKREFN_IC: STAT_OP_IN(OP_BACKREFN_IC);
2341 0 : GET_MEMNUM_INC(mem, p);
2342 : {
2343 : int len;
2344 : UChar *pstart, *pend;
2345 :
2346 : /* if you want to remove following line,
2347 : you should check in parse and compile time. */
2348 0 : if (mem > num_mem) goto fail;
2349 0 : if (mem_end_stk[mem] == INVALID_STACK_INDEX) goto fail;
2350 0 : if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;
2351 :
2352 0 : if (BIT_STATUS_AT(reg->bt_mem_start, mem))
2353 0 : pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
2354 : else
2355 0 : pstart = (UChar* )((void* )mem_start_stk[mem]);
2356 :
2357 0 : pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
2358 : ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
2359 : : (UChar* )((void* )mem_end_stk[mem]));
2360 0 : n = pend - pstart;
2361 0 : DATA_ENSURE(n);
2362 0 : sprev = s;
2363 0 : STRING_CMP_IC(ambig_flag, pstart, &s, n);
2364 0 : while (sprev + (len = enc_len(encode, sprev)) < s)
2365 0 : sprev += len;
2366 :
2367 : STAT_OP_OUT;
2368 0 : continue;
2369 : }
2370 : break;
2371 :
2372 : case OP_BACKREF_MULTI: STAT_OP_IN(OP_BACKREF_MULTI);
2373 : {
2374 : int len, is_fail;
2375 : UChar *pstart, *pend, *swork;
2376 :
2377 0 : GET_LENGTH_INC(tlen, p);
2378 0 : for (i = 0; i < tlen; i++) {
2379 0 : GET_MEMNUM_INC(mem, p);
2380 :
2381 0 : if (mem_end_stk[mem] == INVALID_STACK_INDEX) continue;
2382 0 : if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;
2383 :
2384 0 : if (BIT_STATUS_AT(reg->bt_mem_start, mem))
2385 0 : pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
2386 : else
2387 0 : pstart = (UChar* )((void* )mem_start_stk[mem]);
2388 :
2389 0 : pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
2390 : ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
2391 : : (UChar* )((void* )mem_end_stk[mem]));
2392 0 : n = pend - pstart;
2393 0 : DATA_ENSURE(n);
2394 0 : sprev = s;
2395 0 : swork = s;
2396 0 : STRING_CMP_VALUE(pstart, swork, n, is_fail);
2397 0 : if (is_fail) continue;
2398 0 : s = swork;
2399 0 : while (sprev + (len = enc_len(encode, sprev)) < s)
2400 0 : sprev += len;
2401 :
2402 0 : p += (SIZE_MEMNUM * (tlen - i - 1));
2403 0 : break; /* success */
2404 : }
2405 0 : if (i == tlen) goto fail;
2406 : STAT_OP_OUT;
2407 0 : continue;
2408 : }
2409 : break;
2410 :
2411 : case OP_BACKREF_MULTI_IC: STAT_OP_IN(OP_BACKREF_MULTI_IC);
2412 : {
2413 : int len, is_fail;
2414 : UChar *pstart, *pend, *swork;
2415 :
2416 0 : GET_LENGTH_INC(tlen, p);
2417 0 : for (i = 0; i < tlen; i++) {
2418 0 : GET_MEMNUM_INC(mem, p);
2419 :
2420 0 : if (mem_end_stk[mem] == INVALID_STACK_INDEX) continue;
2421 0 : if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;
2422 :
2423 0 : if (BIT_STATUS_AT(reg->bt_mem_start, mem))
2424 0 : pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
2425 : else
2426 0 : pstart = (UChar* )((void* )mem_start_stk[mem]);
2427 :
2428 0 : pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
2429 : ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
2430 : : (UChar* )((void* )mem_end_stk[mem]));
2431 0 : n = pend - pstart;
2432 0 : DATA_ENSURE(n);
2433 0 : sprev = s;
2434 0 : swork = s;
2435 0 : STRING_CMP_VALUE_IC(ambig_flag, pstart, &swork, n, is_fail);
2436 0 : if (is_fail) continue;
2437 0 : s = swork;
2438 0 : while (sprev + (len = enc_len(encode, sprev)) < s)
2439 0 : sprev += len;
2440 :
2441 0 : p += (SIZE_MEMNUM * (tlen - i - 1));
2442 0 : break; /* success */
2443 : }
2444 0 : if (i == tlen) goto fail;
2445 : STAT_OP_OUT;
2446 0 : continue;
2447 : }
2448 : break;
2449 :
2450 : #ifdef USE_BACKREF_AT_LEVEL
2451 : case OP_BACKREF_AT_LEVEL:
2452 : {
2453 : int len;
2454 : OnigOptionType ic;
2455 : LengthType level;
2456 :
2457 0 : GET_OPTION_INC(ic, p);
2458 0 : GET_LENGTH_INC(level, p);
2459 0 : GET_LENGTH_INC(tlen, p);
2460 :
2461 0 : sprev = s;
2462 0 : if (backref_match_at_nested_level(reg, stk, stk_base, ic, ambig_flag
2463 : , (int )level, (int )tlen, p, &s, end)) {
2464 0 : while (sprev + (len = enc_len(encode, sprev)) < s)
2465 0 : sprev += len;
2466 :
2467 0 : p += (SIZE_MEMNUM * tlen);
2468 : }
2469 : else
2470 0 : goto fail;
2471 :
2472 : STAT_OP_OUT;
2473 0 : continue;
2474 : }
2475 :
2476 : break;
2477 : #endif
2478 :
2479 : case OP_SET_OPTION_PUSH: STAT_OP_IN(OP_SET_OPTION_PUSH);
2480 0 : GET_OPTION_INC(option, p);
2481 0 : STACK_PUSH_ALT(p, s, sprev);
2482 0 : p += SIZE_OP_SET_OPTION + SIZE_OP_FAIL;
2483 : STAT_OP_OUT;
2484 0 : continue;
2485 : break;
2486 :
2487 : case OP_SET_OPTION: STAT_OP_IN(OP_SET_OPTION);
2488 0 : GET_OPTION_INC(option, p);
2489 : STAT_OP_OUT;
2490 0 : continue;
2491 : break;
2492 :
2493 : case OP_NULL_CHECK_START: STAT_OP_IN(OP_NULL_CHECK_START);
2494 0 : GET_MEMNUM_INC(mem, p); /* mem: null check id */
2495 0 : STACK_PUSH_NULL_CHECK_START(mem, s);
2496 : STAT_OP_OUT;
2497 0 : continue;
2498 : break;
2499 :
2500 : case OP_NULL_CHECK_END: STAT_OP_IN(OP_NULL_CHECK_END);
2501 : {
2502 : int isnull;
2503 :
2504 0 : GET_MEMNUM_INC(mem, p); /* mem: null check id */
2505 0 : STACK_NULL_CHECK(isnull, mem, s);
2506 0 : if (isnull) {
2507 : #ifdef ONIG_DEBUG_MATCH
2508 : fprintf(stderr, "NULL_CHECK_END: skip id:%d, s:%d\n",
2509 : (int )mem, (int )s);
2510 : #endif
2511 0 : null_check_found:
2512 : /* empty loop founded, skip next instruction */
2513 0 : switch (*p++) {
2514 : case OP_JUMP:
2515 : case OP_PUSH:
2516 0 : p += SIZE_RELADDR;
2517 0 : break;
2518 : case OP_REPEAT_INC:
2519 : case OP_REPEAT_INC_NG:
2520 : case OP_REPEAT_INC_SG:
2521 : case OP_REPEAT_INC_NG_SG:
2522 0 : p += SIZE_MEMNUM;
2523 0 : break;
2524 : default:
2525 0 : goto unexpected_bytecode_error;
2526 : break;
2527 : }
2528 : }
2529 : }
2530 : STAT_OP_OUT;
2531 0 : continue;
2532 : break;
2533 :
2534 : #ifdef USE_INFINITE_REPEAT_MONOMANIAC_MEM_STATUS_CHECK
2535 : case OP_NULL_CHECK_END_MEMST: STAT_OP_IN(OP_NULL_CHECK_END_MEMST);
2536 : {
2537 : int isnull;
2538 :
2539 0 : GET_MEMNUM_INC(mem, p); /* mem: null check id */
2540 0 : STACK_NULL_CHECK_MEMST(isnull, mem, s, reg);
2541 0 : if (isnull) {
2542 : #ifdef ONIG_DEBUG_MATCH
2543 : fprintf(stderr, "NULL_CHECK_END_MEMST: skip id:%d, s:%d\n",
2544 : (int )mem, (int )s);
2545 : #endif
2546 0 : if (isnull == -1) goto fail;
2547 0 : goto null_check_found;
2548 : }
2549 : }
2550 : STAT_OP_OUT;
2551 0 : continue;
2552 : break;
2553 : #endif
2554 :
2555 : #ifdef USE_SUBEXP_CALL
2556 : case OP_NULL_CHECK_END_MEMST_PUSH:
2557 : STAT_OP_IN(OP_NULL_CHECK_END_MEMST_PUSH);
2558 : {
2559 : int isnull;
2560 :
2561 0 : GET_MEMNUM_INC(mem, p); /* mem: null check id */
2562 : #ifdef USE_INFINITE_REPEAT_MONOMANIAC_MEM_STATUS_CHECK
2563 0 : STACK_NULL_CHECK_MEMST_REC(isnull, mem, s, reg);
2564 : #else
2565 : STACK_NULL_CHECK_REC(isnull, mem, s);
2566 : #endif
2567 0 : if (isnull) {
2568 : #ifdef ONIG_DEBUG_MATCH
2569 : fprintf(stderr, "NULL_CHECK_END_MEMST_PUSH: skip id:%d, s:%d\n",
2570 : (int )mem, (int )s);
2571 : #endif
2572 0 : if (isnull == -1) goto fail;
2573 0 : goto null_check_found;
2574 : }
2575 : else {
2576 0 : STACK_PUSH_NULL_CHECK_END(mem);
2577 : }
2578 : }
2579 : STAT_OP_OUT;
2580 0 : continue;
2581 : break;
2582 : #endif
2583 :
2584 : case OP_JUMP: STAT_OP_IN(OP_JUMP);
2585 1034 : GET_RELADDR_INC(addr, p);
2586 1034 : p += addr;
2587 : STAT_OP_OUT;
2588 : CHECK_INTERRUPT_IN_MATCH_AT;
2589 1034 : continue;
2590 : break;
2591 :
2592 : case OP_PUSH: STAT_OP_IN(OP_PUSH);
2593 626 : GET_RELADDR_INC(addr, p);
2594 626 : STACK_PUSH_ALT(p + addr, s, sprev);
2595 : STAT_OP_OUT;
2596 626 : continue;
2597 : break;
2598 :
2599 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
2600 : case OP_STATE_CHECK_PUSH: STAT_OP_IN(OP_STATE_CHECK_PUSH);
2601 230 : GET_STATE_CHECK_NUM_INC(mem, p);
2602 230 : STATE_CHECK_VAL(scv, mem);
2603 230 : if (scv) goto fail;
2604 :
2605 230 : GET_RELADDR_INC(addr, p);
2606 230 : STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem);
2607 : STAT_OP_OUT;
2608 230 : continue;
2609 : break;
2610 :
2611 : case OP_STATE_CHECK_PUSH_OR_JUMP: STAT_OP_IN(OP_STATE_CHECK_PUSH_OR_JUMP);
2612 0 : GET_STATE_CHECK_NUM_INC(mem, p);
2613 0 : GET_RELADDR_INC(addr, p);
2614 0 : STATE_CHECK_VAL(scv, mem);
2615 0 : if (scv) {
2616 0 : p += addr;
2617 : }
2618 : else {
2619 0 : STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem);
2620 : }
2621 : STAT_OP_OUT;
2622 0 : continue;
2623 : break;
2624 :
2625 : case OP_STATE_CHECK: STAT_OP_IN(OP_STATE_CHECK);
2626 0 : GET_STATE_CHECK_NUM_INC(mem, p);
2627 0 : STATE_CHECK_VAL(scv, mem);
2628 0 : if (scv) goto fail;
2629 :
2630 0 : STACK_PUSH_STATE_CHECK(s, mem);
2631 : STAT_OP_OUT;
2632 0 : continue;
2633 : break;
2634 : #endif /* USE_COMBINATION_EXPLOSION_CHECK */
2635 :
2636 : case OP_POP: STAT_OP_IN(OP_POP);
2637 81 : STACK_POP_ONE;
2638 : STAT_OP_OUT;
2639 81 : continue;
2640 : break;
2641 :
2642 : case OP_PUSH_OR_JUMP_EXACT1: STAT_OP_IN(OP_PUSH_OR_JUMP_EXACT1);
2643 0 : GET_RELADDR_INC(addr, p);
2644 0 : if (*p == *s && DATA_ENSURE_CHECK(1)) {
2645 0 : p++;
2646 0 : STACK_PUSH_ALT(p + addr, s, sprev);
2647 : STAT_OP_OUT;
2648 0 : continue;
2649 : }
2650 0 : p += (addr + 1);
2651 : STAT_OP_OUT;
2652 0 : continue;
2653 : break;
2654 :
2655 : case OP_PUSH_IF_PEEK_NEXT: STAT_OP_IN(OP_PUSH_IF_PEEK_NEXT);
2656 0 : GET_RELADDR_INC(addr, p);
2657 0 : if (*p == *s) {
2658 0 : p++;
2659 0 : STACK_PUSH_ALT(p + addr, s, sprev);
2660 : STAT_OP_OUT;
2661 0 : continue;
2662 : }
2663 0 : p++;
2664 : STAT_OP_OUT;
2665 0 : continue;
2666 : break;
2667 :
2668 : case OP_REPEAT: STAT_OP_IN(OP_REPEAT);
2669 : {
2670 5 : GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
2671 5 : GET_RELADDR_INC(addr, p);
2672 :
2673 5 : STACK_ENSURE(1);
2674 5 : repeat_stk[mem] = GET_STACK_INDEX(stk);
2675 5 : STACK_PUSH_REPEAT(mem, p);
2676 :
2677 5 : if (reg->repeat_range[mem].lower == 0) {
2678 0 : STACK_PUSH_ALT(p + addr, s, sprev);
2679 : }
2680 : }
2681 : STAT_OP_OUT;
2682 5 : continue;
2683 : break;
2684 :
2685 : case OP_REPEAT_NG: STAT_OP_IN(OP_REPEAT_NG);
2686 : {
2687 0 : GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
2688 0 : GET_RELADDR_INC(addr, p);
2689 :
2690 0 : STACK_ENSURE(1);
2691 0 : repeat_stk[mem] = GET_STACK_INDEX(stk);
2692 0 : STACK_PUSH_REPEAT(mem, p);
2693 :
2694 0 : if (reg->repeat_range[mem].lower == 0) {
2695 0 : STACK_PUSH_ALT(p, s, sprev);
2696 0 : p += addr;
2697 : }
2698 : }
2699 : STAT_OP_OUT;
2700 0 : continue;
2701 : break;
2702 :
2703 : case OP_REPEAT_INC: STAT_OP_IN(OP_REPEAT_INC);
2704 25 : GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
2705 25 : si = repeat_stk[mem];
2706 25 : stkp = STACK_AT(si);
2707 :
2708 25 : repeat_inc:
2709 25 : stkp->u.repeat.count++;
2710 25 : if (stkp->u.repeat.count >= reg->repeat_range[mem].upper) {
2711 : /* end of repeat. Nothing to do. */
2712 : }
2713 21 : else if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {
2714 3 : STACK_PUSH_ALT(p, s, sprev);
2715 3 : p = STACK_AT(si)->u.repeat.pcode; /* Don't use stkp after PUSH. */
2716 : }
2717 : else {
2718 18 : p = stkp->u.repeat.pcode;
2719 : }
2720 25 : STACK_PUSH_REPEAT_INC(si);
2721 : STAT_OP_OUT;
2722 : CHECK_INTERRUPT_IN_MATCH_AT;
2723 25 : continue;
2724 : break;
2725 :
2726 : case OP_REPEAT_INC_SG: STAT_OP_IN(OP_REPEAT_INC_SG);
2727 0 : GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
2728 0 : STACK_GET_REPEAT(mem, stkp);
2729 0 : si = GET_STACK_INDEX(stkp);
2730 0 : goto repeat_inc;
2731 : break;
2732 :
2733 : case OP_REPEAT_INC_NG: STAT_OP_IN(OP_REPEAT_INC_NG);
2734 0 : GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
2735 0 : si = repeat_stk[mem];
2736 0 : stkp = STACK_AT(si);
2737 :
2738 0 : repeat_inc_ng:
2739 0 : stkp->u.repeat.count++;
2740 0 : if (stkp->u.repeat.count < reg->repeat_range[mem].upper) {
2741 0 : if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {
2742 0 : UChar* pcode = stkp->u.repeat.pcode;
2743 :
2744 0 : STACK_PUSH_REPEAT_INC(si);
2745 0 : STACK_PUSH_ALT(pcode, s, sprev);
2746 : }
2747 : else {
2748 0 : p = stkp->u.repeat.pcode;
2749 0 : STACK_PUSH_REPEAT_INC(si);
2750 : }
2751 : }
2752 0 : else if (stkp->u.repeat.count == reg->repeat_range[mem].upper) {
2753 0 : STACK_PUSH_REPEAT_INC(si);
2754 : }
2755 : STAT_OP_OUT;
2756 : CHECK_INTERRUPT_IN_MATCH_AT;
2757 0 : continue;
2758 : break;
2759 :
2760 : case OP_REPEAT_INC_NG_SG: STAT_OP_IN(OP_REPEAT_INC_NG_SG);
2761 0 : GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
2762 0 : STACK_GET_REPEAT(mem, stkp);
2763 0 : si = GET_STACK_INDEX(stkp);
2764 0 : goto repeat_inc_ng;
2765 : break;
2766 :
2767 : case OP_PUSH_POS: STAT_OP_IN(OP_PUSH_POS);
2768 0 : STACK_PUSH_POS(s, sprev);
2769 : STAT_OP_OUT;
2770 0 : continue;
2771 : break;
2772 :
2773 : case OP_POP_POS: STAT_OP_IN(OP_POP_POS);
2774 : {
2775 0 : STACK_POS_END(stkp);
2776 0 : s = stkp->u.state.pstr;
2777 0 : sprev = stkp->u.state.pstr_prev;
2778 : }
2779 : STAT_OP_OUT;
2780 0 : continue;
2781 : break;
2782 :
2783 : case OP_PUSH_POS_NOT: STAT_OP_IN(OP_PUSH_POS_NOT);
2784 0 : GET_RELADDR_INC(addr, p);
2785 0 : STACK_PUSH_POS_NOT(p + addr, s, sprev);
2786 : STAT_OP_OUT;
2787 0 : continue;
2788 : break;
2789 :
2790 : case OP_FAIL_POS: STAT_OP_IN(OP_FAIL_POS);
2791 0 : STACK_POP_TIL_POS_NOT;
2792 0 : goto fail;
2793 : break;
2794 :
2795 : case OP_PUSH_STOP_BT: STAT_OP_IN(OP_PUSH_STOP_BT);
2796 0 : STACK_PUSH_STOP_BT;
2797 : STAT_OP_OUT;
2798 0 : continue;
2799 : break;
2800 :
2801 : case OP_POP_STOP_BT: STAT_OP_IN(OP_POP_STOP_BT);
2802 0 : STACK_STOP_BT_END;
2803 : STAT_OP_OUT;
2804 0 : continue;
2805 : break;
2806 :
2807 : case OP_LOOK_BEHIND: STAT_OP_IN(OP_LOOK_BEHIND);
2808 0 : GET_LENGTH_INC(tlen, p);
2809 0 : s = (UChar* )ONIGENC_STEP_BACK(encode, str, s, (int )tlen);
2810 0 : if (IS_NULL(s)) goto fail;
2811 0 : sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s);
2812 : STAT_OP_OUT;
2813 0 : continue;
2814 : break;
2815 :
2816 : case OP_PUSH_LOOK_BEHIND_NOT: STAT_OP_IN(OP_PUSH_LOOK_BEHIND_NOT);
2817 0 : GET_RELADDR_INC(addr, p);
2818 0 : GET_LENGTH_INC(tlen, p);
2819 0 : q = (UChar* )ONIGENC_STEP_BACK(encode, str, s, (int )tlen);
2820 0 : if (IS_NULL(q)) {
2821 : /* too short case -> success. ex. /(?<!XXX)a/.match("a")
2822 : If you want to change to fail, replace following line. */
2823 0 : p += addr;
2824 : /* goto fail; */
2825 : }
2826 : else {
2827 0 : STACK_PUSH_LOOK_BEHIND_NOT(p + addr, s, sprev);
2828 0 : s = q;
2829 0 : sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s);
2830 : }
2831 : STAT_OP_OUT;
2832 0 : continue;
2833 : break;
2834 :
2835 : case OP_FAIL_LOOK_BEHIND_NOT: STAT_OP_IN(OP_FAIL_LOOK_BEHIND_NOT);
2836 0 : STACK_POP_TIL_LOOK_BEHIND_NOT;
2837 0 : goto fail;
2838 : break;
2839 :
2840 : #ifdef USE_SUBEXP_CALL
2841 : case OP_CALL: STAT_OP_IN(OP_CALL);
2842 0 : GET_ABSADDR_INC(addr, p);
2843 0 : STACK_PUSH_CALL_FRAME(p);
2844 0 : p = reg->p + addr;
2845 : STAT_OP_OUT;
2846 0 : continue;
2847 : break;
2848 :
2849 : case OP_RETURN: STAT_OP_IN(OP_RETURN);
2850 0 : STACK_RETURN(p);
2851 0 : STACK_PUSH_RETURN;
2852 : STAT_OP_OUT;
2853 0 : continue;
2854 : break;
2855 : #endif
2856 :
2857 : case OP_FINISH:
2858 217 : goto finish;
2859 : break;
2860 :
2861 734 : fail:
2862 : STAT_OP_OUT;
2863 : /* fall */
2864 : case OP_FAIL: STAT_OP_IN(OP_FAIL);
2865 734 : STACK_POP;
2866 734 : p = stk->u.state.pcode;
2867 734 : s = stk->u.state.pstr;
2868 734 : sprev = stk->u.state.pstr_prev;
2869 :
2870 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
2871 734 : if (stk->u.state.state_check != 0) {
2872 245 : stk->type = STK_STATE_CHECK_MARK;
2873 245 : stk++;
2874 : }
2875 : #endif
2876 :
2877 : STAT_OP_OUT;
2878 734 : continue;
2879 : break;
2880 :
2881 : default:
2882 0 : goto bytecode_error;
2883 :
2884 : } /* end of switch */
2885 1225 : sprev = sbegin;
2886 4403 : } /* end of while(1) */
2887 :
2888 752 : finish:
2889 752 : STACK_SAVE;
2890 752 : return best_len;
2891 :
2892 : #ifdef ONIG_DEBUG
2893 : stack_error:
2894 : STACK_SAVE;
2895 : return ONIGERR_STACK_BUG;
2896 : #endif
2897 :
2898 0 : bytecode_error:
2899 0 : STACK_SAVE;
2900 0 : return ONIGERR_UNDEFINED_BYTECODE;
2901 :
2902 0 : unexpected_bytecode_error:
2903 0 : STACK_SAVE;
2904 0 : return ONIGERR_UNEXPECTED_BYTECODE;
2905 : }
2906 :
2907 :
2908 : static UChar*
2909 : slow_search(OnigEncoding enc, UChar* target, UChar* target_end,
2910 : const UChar* text, const UChar* text_end, UChar* text_range)
2911 47 : {
2912 : UChar *t, *p, *s, *end;
2913 :
2914 47 : end = (UChar* )text_end;
2915 47 : end -= target_end - target - 1;
2916 47 : if (end > text_range)
2917 0 : end = text_range;
2918 :
2919 47 : s = (UChar* )text;
2920 :
2921 368 : while (s < end) {
2922 308 : if (*s == *target) {
2923 48 : p = s + 1;
2924 48 : t = target + 1;
2925 123 : while (t < target_end) {
2926 41 : if (*t != *p++)
2927 14 : break;
2928 27 : t++;
2929 : }
2930 48 : if (t == target_end)
2931 34 : return s;
2932 : }
2933 274 : s += enc_len(enc, s);
2934 : }
2935 :
2936 13 : return (UChar* )NULL;
2937 : }
2938 :
2939 : static int
2940 : str_lower_case_match(OnigEncoding enc, int ambig_flag,
2941 : const UChar* t, const UChar* tend,
2942 : const UChar* p, const UChar* end)
2943 1 : {
2944 : int lowlen;
2945 : UChar *q, lowbuf[ONIGENC_MBC_NORMALIZE_MAXLEN];
2946 : const UChar* tsave;
2947 : const UChar* psave;
2948 :
2949 1 : tsave = t;
2950 1 : psave = p;
2951 :
2952 1 : retry:
2953 4 : while (t < tend) {
2954 2 : lowlen = ONIGENC_MBC_TO_NORMALIZE(enc, ambig_flag, &p, end, lowbuf);
2955 2 : q = lowbuf;
2956 6 : while (lowlen > 0) {
2957 2 : if (*t++ != *q++) {
2958 0 : if ((ambig_flag & ONIGENC_AMBIGUOUS_MATCH_COMPOUND) != 0) {
2959 0 : ambig_flag &= ~ONIGENC_AMBIGUOUS_MATCH_COMPOUND;
2960 0 : t = tsave;
2961 0 : p = psave;
2962 0 : goto retry;
2963 : }
2964 : else
2965 0 : return 0;
2966 : }
2967 2 : lowlen--;
2968 : }
2969 : }
2970 :
2971 1 : return 1;
2972 : }
2973 :
2974 : static UChar*
2975 : slow_search_ic(OnigEncoding enc, int ambig_flag,
2976 : UChar* target, UChar* target_end,
2977 : const UChar* text, const UChar* text_end, UChar* text_range)
2978 1 : {
2979 : UChar *s, *end;
2980 :
2981 1 : end = (UChar* )text_end;
2982 1 : end -= target_end - target - 1;
2983 1 : if (end > text_range)
2984 0 : end = text_range;
2985 :
2986 1 : s = (UChar* )text;
2987 :
2988 2 : while (s < end) {
2989 1 : if (str_lower_case_match(enc, ambig_flag, target, target_end, s, text_end))
2990 1 : return s;
2991 :
2992 0 : s += enc_len(enc, s);
2993 : }
2994 :
2995 0 : return (UChar* )NULL;
2996 : }
2997 :
2998 : static UChar*
2999 : slow_search_backward(OnigEncoding enc, UChar* target, UChar* target_end,
3000 : const UChar* text, const UChar* adjust_text,
3001 : const UChar* text_end, const UChar* text_start)
3002 0 : {
3003 : UChar *t, *p, *s;
3004 :
3005 0 : s = (UChar* )text_end;
3006 0 : s -= (target_end - target);
3007 0 : if (s > text_start)
3008 0 : s = (UChar* )text_start;
3009 : else
3010 0 : s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s);
3011 :
3012 0 : while (s >= text) {
3013 0 : if (*s == *target) {
3014 0 : p = s + 1;
3015 0 : t = target + 1;
3016 0 : while (t < target_end) {
3017 0 : if (*t != *p++)
3018 0 : break;
3019 0 : t++;
3020 : }
3021 0 : if (t == target_end)
3022 0 : return s;
3023 : }
3024 0 : s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s);
3025 : }
3026 :
3027 0 : return (UChar* )NULL;
3028 : }
3029 :
3030 : static UChar*
3031 : slow_search_backward_ic(OnigEncoding enc, int ambig_flag,
3032 : UChar* target, UChar* target_end,
3033 : const UChar* text, const UChar* adjust_text,
3034 : const UChar* text_end, const UChar* text_start)
3035 0 : {
3036 : UChar *s;
3037 :
3038 0 : s = (UChar* )text_end;
3039 0 : s -= (target_end - target);
3040 0 : if (s > text_start)
3041 0 : s = (UChar* )text_start;
3042 : else
3043 0 : s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s);
3044 :
3045 0 : while (s >= text) {
3046 0 : if (str_lower_case_match(enc, ambig_flag,
3047 : target, target_end, s, text_end))
3048 0 : return s;
3049 :
3050 0 : s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s);
3051 : }
3052 :
3053 0 : return (UChar* )NULL;
3054 : }
3055 :
3056 : static UChar*
3057 : bm_search_notrev(regex_t* reg, const UChar* target, const UChar* target_end,
3058 : const UChar* text, const UChar* text_end,
3059 : const UChar* text_range)
3060 2 : {
3061 : const UChar *s, *se, *t, *p, *end;
3062 : const UChar *tail;
3063 : int skip, tlen1;
3064 :
3065 : #ifdef ONIG_DEBUG_SEARCH
3066 : fprintf(stderr, "bm_search_notrev: text: %d, text_end: %d, text_range: %d\n",
3067 : (int )text, (int )text_end, (int )text_range);
3068 : #endif
3069 :
3070 2 : tail = target_end - 1;
3071 2 : tlen1 = tail - target;
3072 2 : end = text_range;
3073 2 : if (end + tlen1 > text_end)
3074 2 : end = text_end - tlen1;
3075 :
3076 2 : s = text;
3077 :
3078 2 : if (IS_NULL(reg->int_map)) {
3079 4 : while (s < end) {
3080 2 : p = se = s + tlen1;
3081 2 : t = tail;
3082 12 : while (t >= target && *p == *t) {
3083 8 : p--; t--;
3084 : }
3085 2 : if (t < target) return (UChar* )s;
3086 :
3087 0 : skip = reg->map[*se];
3088 0 : t = s;
3089 : do {
3090 0 : s += enc_len(reg->enc, s);
3091 0 : } while ((s - t) < skip && s < end);
3092 : }
3093 : }
3094 : else {
3095 0 : while (s < end) {
3096 0 : p = se = s + tlen1;
3097 0 : t = tail;
3098 0 : while (t >= target && *p == *t) {
3099 0 : p--; t--;
3100 : }
3101 0 : if (t < target) return (UChar* )s;
3102 :
3103 0 : skip = reg->int_map[*se];
3104 0 : t = s;
3105 : do {
3106 0 : s += enc_len(reg->enc, s);
3107 0 : } while ((s - t) < skip && s < end);
3108 : }
3109 : }
3110 :
3111 0 : return (UChar* )NULL;
3112 : }
3113 :
3114 : static UChar*
3115 : bm_search(regex_t* reg, const UChar* target, const UChar* target_end,
3116 : const UChar* text, const UChar* text_end, const UChar* text_range)
3117 75 : {
3118 : const UChar *s, *t, *p, *end;
3119 : const UChar *tail;
3120 :
3121 75 : end = text_range + (target_end - target) - 1;
3122 75 : if (end > text_end)
3123 74 : end = text_end;
3124 :
3125 75 : tail = target_end - 1;
3126 75 : s = text + (target_end - target) - 1;
3127 75 : if (IS_NULL(reg->int_map)) {
3128 290 : while (s < end) {
3129 180 : p = s;
3130 180 : t = tail;
3131 505 : while (t >= target && *p == *t) {
3132 145 : p--; t--;
3133 : }
3134 180 : if (t < target) return (UChar* )(p + 1);
3135 140 : s += reg->map[*s];
3136 : }
3137 : }
3138 : else { /* see int_map[] */
3139 0 : while (s < end) {
3140 0 : p = s;
3141 0 : t = tail;
3142 0 : while (t >= target && *p == *t) {
3143 0 : p--; t--;
3144 : }
3145 0 : if (t < target) return (UChar* )(p + 1);
3146 0 : s += reg->int_map[*s];
3147 : }
3148 : }
3149 35 : return (UChar* )NULL;
3150 : }
3151 :
3152 : static int
3153 : set_bm_backward_skip(UChar* s, UChar* end, OnigEncoding enc, int** skip)
3154 :
3155 0 : {
3156 : int i, len;
3157 :
3158 0 : if (IS_NULL(*skip)) {
3159 0 : *skip = (int* )xmalloc(sizeof(int) * ONIG_CHAR_TABLE_SIZE);
3160 0 : if (IS_NULL(*skip)) return ONIGERR_MEMORY;
3161 : }
3162 :
3163 0 : len = end - s;
3164 0 : for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
3165 0 : (*skip)[i] = len;
3166 :
3167 0 : for (i = len - 1; i > 0; i--)
3168 0 : (*skip)[s[i]] = i;
3169 :
3170 0 : return 0;
3171 : }
3172 :
3173 : static UChar*
3174 : bm_search_backward(regex_t* reg, const UChar* target, const UChar* target_end,
3175 : const UChar* text, const UChar* adjust_text,
3176 : const UChar* text_end, const UChar* text_start)
3177 0 : {
3178 : const UChar *s, *t, *p;
3179 :
3180 0 : s = text_end - (target_end - target);
3181 0 : if (text_start < s)
3182 0 : s = text_start;
3183 : else
3184 0 : s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, adjust_text, s);
3185 :
3186 0 : while (s >= text) {
3187 0 : p = s;
3188 0 : t = target;
3189 0 : while (t < target_end && *p == *t) {
3190 0 : p++; t++;
3191 : }
3192 0 : if (t == target_end)
3193 0 : return (UChar* )s;
3194 :
3195 0 : s -= reg->int_map_backward[*s];
3196 0 : s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, adjust_text, s);
3197 : }
3198 :
3199 0 : return (UChar* )NULL;
3200 : }
3201 :
3202 : static UChar*
3203 : map_search(OnigEncoding enc, UChar map[],
3204 : const UChar* text, const UChar* text_range)
3205 462 : {
3206 462 : const UChar *s = text;
3207 :
3208 1609 : while (s < text_range) {
3209 1069 : if (map[*s]) return (UChar* )s;
3210 :
3211 685 : s += enc_len(enc, s);
3212 : }
3213 78 : return (UChar* )NULL;
3214 : }
3215 :
3216 : static UChar*
3217 : map_search_backward(OnigEncoding enc, UChar map[],
3218 : const UChar* text, const UChar* adjust_text,
3219 : const UChar* text_start)
3220 0 : {
3221 0 : const UChar *s = text_start;
3222 :
3223 0 : while (s >= text) {
3224 0 : if (map[*s]) return (UChar* )s;
3225 :
3226 0 : s = onigenc_get_prev_char_head(enc, adjust_text, s);
3227 : }
3228 0 : return (UChar* )NULL;
3229 : }
3230 :
3231 : extern int
3232 : onig_match(regex_t* reg, const UChar* str, const UChar* end, const UChar* at, OnigRegion* region,
3233 : OnigOptionType option)
3234 4 : {
3235 : int r;
3236 : UChar *prev;
3237 : MatchArg msa;
3238 :
3239 : #if defined(USE_RECOMPILE_API) && defined(USE_MULTI_THREAD_SYSTEM)
3240 : start:
3241 : THREAD_ATOMIC_START;
3242 : if (ONIG_STATE(reg) >= ONIG_STATE_NORMAL) {
3243 : ONIG_STATE_INC(reg);
3244 : if (IS_NOT_NULL(reg->chain) && ONIG_STATE(reg) == ONIG_STATE_NORMAL) {
3245 : onig_chain_reduce(reg);
3246 : ONIG_STATE_INC(reg);
3247 : }
3248 : }
3249 : else {
3250 : int n;
3251 :
3252 : THREAD_ATOMIC_END;
3253 : n = 0;
3254 : while (ONIG_STATE(reg) < ONIG_STATE_NORMAL) {
3255 : if (++n > THREAD_PASS_LIMIT_COUNT)
3256 : return ONIGERR_OVER_THREAD_PASS_LIMIT_COUNT;
3257 : THREAD_PASS;
3258 : }
3259 : goto start;
3260 : }
3261 : THREAD_ATOMIC_END;
3262 : #endif /* USE_RECOMPILE_API && USE_MULTI_THREAD_SYSTEM */
3263 :
3264 4 : MATCH_ARG_INIT(msa, option, region, at);
3265 4 : STATE_CHECK_BUFF_INIT(msa, end - str, reg->num_comb_exp_check);
3266 :
3267 4 : if (region
3268 : #ifdef USE_POSIX_REGION_OPTION
3269 : && !IS_POSIX_REGION(option)
3270 : #endif
3271 : ) {
3272 0 : r = onig_region_resize_clear(region, reg->num_mem + 1);
3273 : }
3274 : else
3275 4 : r = 0;
3276 :
3277 4 : if (r == 0) {
3278 4 : prev = (UChar* )onigenc_get_prev_char_head(reg->enc, str, at);
3279 4 : r = match_at(reg, str, end, at, prev, &msa);
3280 : }
3281 :
3282 4 : MATCH_ARG_FREE(msa);
3283 : ONIG_STATE_DEC_THREAD(reg);
3284 4 : return r;
3285 : }
3286 :
3287 : static int
3288 : forward_search_range(regex_t* reg, const UChar* str, const UChar* end, UChar* s,
3289 : UChar* range, UChar** low, UChar** high, UChar** low_prev)
3290 587 : {
3291 587 : UChar *p, *pprev = (UChar* )NULL;
3292 :
3293 : #ifdef ONIG_DEBUG_SEARCH
3294 : fprintf(stderr, "forward_search_range: str: %d, end: %d, s: %d, range: %d\n",
3295 : (int )str, (int )end, (int )s, (int )range);
3296 : #endif
3297 :
3298 587 : p = s;
3299 587 : if (reg->dmin > 0) {
3300 12 : if (ONIGENC_IS_SINGLEBYTE(reg->enc)) {
3301 1 : p += reg->dmin;
3302 : }
3303 : else {
3304 11 : UChar *q = p + reg->dmin;
3305 11 : while (p < q) p += enc_len(reg->enc, p);
3306 : }
3307 : }
3308 :
3309 587 : retry:
3310 587 : switch (reg->optimize) {
3311 : case ONIG_OPTIMIZE_EXACT:
3312 47 : p = slow_search(reg->enc, reg->exact, reg->exact_end, p, end, range);
3313 47 : break;
3314 : case ONIG_OPTIMIZE_EXACT_IC:
3315 1 : p = slow_search_ic(reg->enc, reg->ambig_flag,
3316 : reg->exact, reg->exact_end, p, end, range);
3317 1 : break;
3318 :
3319 : case ONIG_OPTIMIZE_EXACT_BM:
3320 75 : p = bm_search(reg, reg->exact, reg->exact_end, p, end, range);
3321 75 : break;
3322 :
3323 : case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:
3324 2 : p = bm_search_notrev(reg, reg->exact, reg->exact_end, p, end, range);
3325 2 : break;
3326 :
3327 : case ONIG_OPTIMIZE_MAP:
3328 462 : p = map_search(reg->enc, reg->map, p, range);
3329 : break;
3330 : }
3331 :
3332 587 : if (p && p < range) {
3333 461 : if (p - reg->dmin < s) {
3334 0 : retry_gate:
3335 0 : pprev = p;
3336 0 : p += enc_len(reg->enc, p);
3337 0 : goto retry;
3338 : }
3339 :
3340 461 : if (reg->sub_anchor) {
3341 : UChar* prev;
3342 :
3343 0 : switch (reg->sub_anchor) {
3344 : case ANCHOR_BEGIN_LINE:
3345 0 : if (!ON_STR_BEGIN(p)) {
3346 0 : prev = onigenc_get_prev_char_head(reg->enc,
3347 : (pprev ? pprev : str), p);
3348 0 : if (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end))
3349 0 : goto retry_gate;
3350 : }
3351 0 : break;
3352 :
3353 : case ANCHOR_END_LINE:
3354 0 : if (ON_STR_END(p)) {
3355 0 : prev = (UChar* )onigenc_get_prev_char_head(reg->enc,
3356 : (pprev ? pprev : str), p);
3357 0 : if (prev && ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end))
3358 0 : goto retry_gate;
3359 : }
3360 0 : else if (! ONIGENC_IS_MBC_NEWLINE(reg->enc, p, end)
3361 : #ifdef USE_CRNL_AS_LINE_TERMINATOR
3362 : && ! ONIGENC_IS_MBC_CRNL(reg->enc, p, end)
3363 : #endif
3364 : )
3365 0 : goto retry_gate;
3366 : break;
3367 : }
3368 : }
3369 :
3370 461 : if (reg->dmax == 0) {
3371 434 : *low = p;
3372 434 : if (low_prev) {
3373 434 : if (*low > s)
3374 170 : *low_prev = onigenc_get_prev_char_head(reg->enc, s, p);
3375 : else
3376 264 : *low_prev = onigenc_get_prev_char_head(reg->enc,
3377 : (pprev ? pprev : str), p);
3378 : }
3379 : }
3380 : else {
3381 27 : if (reg->dmax != ONIG_INFINITE_DISTANCE) {
3382 10 : *low = p - reg->dmax;
3383 10 : if (*low > s) {
3384 1 : *low = onigenc_get_right_adjust_char_head_with_prev(reg->enc, s,
3385 : *low, (const UChar** )low_prev);
3386 1 : if (low_prev && IS_NULL(*low_prev))
3387 1 : *low_prev = onigenc_get_prev_char_head(reg->enc,
3388 : (pprev ? pprev : s), *low);
3389 : }
3390 : else {
3391 9 : if (low_prev)
3392 9 : *low_prev = onigenc_get_prev_char_head(reg->enc,
3393 : (pprev ? pprev : str), *low);
3394 : }
3395 : }
3396 : }
3397 : /* no needs to adjust *high, *high is used as range check only */
3398 461 : *high = p - reg->dmin;
3399 :
3400 : #ifdef ONIG_DEBUG_SEARCH
3401 : fprintf(stderr,
3402 : "forward_search_range success: low: %d, high: %d, dmin: %d, dmax: %d\n",
3403 : (int )(*low - str), (int )(*high - str), reg->dmin, reg->dmax);
3404 : #endif
3405 461 : return 1; /* success */
3406 : }
3407 :
3408 126 : return 0; /* fail */
3409 : }
3410 :
3411 : static int set_bm_backward_skip P_((UChar* s, UChar* end, OnigEncoding enc,
3412 : int** skip));
3413 :
3414 : #define BM_BACKWARD_SEARCH_LENGTH_THRESHOLD 100
3415 :
3416 : static int
3417 : backward_search_range(regex_t* reg, const UChar* str, const UChar* end,
3418 : UChar* s, const UChar* range, UChar* adjrange,
3419 : UChar** low, UChar** high)
3420 0 : {
3421 : int r;
3422 : UChar *p;
3423 :
3424 0 : range += reg->dmin;
3425 0 : p = s;
3426 :
3427 0 : retry:
3428 0 : switch (reg->optimize) {
3429 : case ONIG_OPTIMIZE_EXACT:
3430 0 : exact_method:
3431 0 : p = slow_search_backward(reg->enc, reg->exact, reg->exact_end,
3432 : range, adjrange, end, p);
3433 0 : break;
3434 :
3435 : case ONIG_OPTIMIZE_EXACT_IC:
3436 0 : p = slow_search_backward_ic(reg->enc, reg->ambig_flag,
3437 : reg->exact, reg->exact_end,
3438 : range, adjrange, end, p);
3439 0 : break;
3440 :
3441 : case ONIG_OPTIMIZE_EXACT_BM:
3442 : case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:
3443 0 : if (IS_NULL(reg->int_map_backward)) {
3444 0 : if (s - range < BM_BACKWARD_SEARCH_LENGTH_THRESHOLD)
3445 0 : goto exact_method;
3446 :
3447 0 : r = set_bm_backward_skip(reg->exact, reg->exact_end, reg->enc,
3448 : &(reg->int_map_backward));
3449 0 : if (r) return r;
3450 : }
3451 0 : p = bm_search_backward(reg, reg->exact, reg->exact_end, range, adjrange,
3452 : end, p);
3453 0 : break;
3454 :
3455 : case ONIG_OPTIMIZE_MAP:
3456 0 : p = map_search_backward(reg->enc, reg->map, range, adjrange, p);
3457 : break;
3458 : }
3459 :
3460 0 : if (p) {
3461 0 : if (reg->sub_anchor) {
3462 : UChar* prev;
3463 :
3464 0 : switch (reg->sub_anchor) {
3465 : case ANCHOR_BEGIN_LINE:
3466 0 : if (!ON_STR_BEGIN(p)) {
3467 0 : prev = onigenc_get_prev_char_head(reg->enc, str, p);
3468 0 : if (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end)) {
3469 0 : p = prev;
3470 0 : goto retry;
3471 : }
3472 : }
3473 0 : break;
3474 :
3475 : case ANCHOR_END_LINE:
3476 0 : if (ON_STR_END(p)) {
3477 0 : prev = onigenc_get_prev_char_head(reg->enc, adjrange, p);
3478 0 : if (IS_NULL(prev)) goto fail;
3479 0 : if (ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end)) {
3480 0 : p = prev;
3481 0 : goto retry;
3482 : }
3483 : }
3484 0 : else if (! ONIGENC_IS_MBC_NEWLINE(reg->enc, p, end)
3485 : #ifdef USE_CRNL_AS_LINE_TERMINATOR
3486 : && ! ONIGENC_IS_MBC_CRNL(reg->enc, p, end)
3487 : #endif
3488 : ) {
3489 0 : p = onigenc_get_prev_char_head(reg->enc, adjrange, p);
3490 0 : if (IS_NULL(p)) goto fail;
3491 0 : goto retry;
3492 : }
3493 : break;
3494 : }
3495 : }
3496 :
3497 : /* no needs to adjust *high, *high is used as range check only */
3498 0 : if (reg->dmax != ONIG_INFINITE_DISTANCE) {
3499 0 : *low = p - reg->dmax;
3500 0 : *high = p - reg->dmin;
3501 0 : *high = onigenc_get_right_adjust_char_head(reg->enc, adjrange, *high);
3502 : }
3503 :
3504 : #ifdef ONIG_DEBUG_SEARCH
3505 : fprintf(stderr, "backward_search_range: low: %d, high: %d\n",
3506 : (int )(*low - str), (int )(*high - str));
3507 : #endif
3508 0 : return 1; /* success */
3509 : }
3510 :
3511 0 : fail:
3512 : #ifdef ONIG_DEBUG_SEARCH
3513 : fprintf(stderr, "backward_search_range: fail.\n");
3514 : #endif
3515 0 : return 0; /* fail */
3516 : }
3517 :
3518 :
3519 : extern int
3520 : onig_search(regex_t* reg, const UChar* str, const UChar* end,
3521 : const UChar* start, const UChar* range, OnigRegion* region, OnigOptionType option)
3522 762 : {
3523 : int r;
3524 : UChar *s, *prev;
3525 : MatchArg msa;
3526 762 : const UChar *orig_start = start;
3527 :
3528 : #if defined(USE_RECOMPILE_API) && defined(USE_MULTI_THREAD_SYSTEM)
3529 : start:
3530 : THREAD_ATOMIC_START;
3531 : if (ONIG_STATE(reg) >= ONIG_STATE_NORMAL) {
3532 : ONIG_STATE_INC(reg);
3533 : if (IS_NOT_NULL(reg->chain) && ONIG_STATE(reg) == ONIG_STATE_NORMAL) {
3534 : onig_chain_reduce(reg);
3535 : ONIG_STATE_INC(reg);
3536 : }
3537 : }
3538 : else {
3539 : int n;
3540 :
3541 : THREAD_ATOMIC_END;
3542 : n = 0;
3543 : while (ONIG_STATE(reg) < ONIG_STATE_NORMAL) {
3544 : if (++n > THREAD_PASS_LIMIT_COUNT)
3545 : return ONIGERR_OVER_THREAD_PASS_LIMIT_COUNT;
3546 : THREAD_PASS;
3547 : }
3548 : goto start;
3549 : }
3550 : THREAD_ATOMIC_END;
3551 : #endif /* USE_RECOMPILE_API && USE_MULTI_THREAD_SYSTEM */
3552 :
3553 : #ifdef ONIG_DEBUG_SEARCH
3554 : fprintf(stderr,
3555 : "onig_search (entry point): str: %d, end: %d, start: %d, range: %d\n",
3556 : (int )str, (int )(end - str), (int )(start - str), (int )(range - str));
3557 : #endif
3558 :
3559 762 : if (region
3560 : #ifdef USE_POSIX_REGION_OPTION
3561 : && !IS_POSIX_REGION(option)
3562 : #endif
3563 : ) {
3564 762 : r = onig_region_resize_clear(region, reg->num_mem + 1);
3565 762 : if (r) goto finish_no_msa;
3566 : }
3567 :
3568 762 : if (start > end || start < str) goto mismatch_no_msa;
3569 :
3570 : #define MATCH_AND_RETURN_CHECK \
3571 : r = match_at(reg, str, end, s, prev, &msa);\
3572 : if (r != ONIG_MISMATCH) {\
3573 : if (r >= 0) goto match;\
3574 : goto finish; /* error */ \
3575 : }
3576 :
3577 : /* anchor optimize: resume search range */
3578 781 : if (reg->anchor != 0 && str < end) {
3579 : UChar* semi_end;
3580 :
3581 26 : if (reg->anchor & ANCHOR_BEGIN_POSITION) {
3582 : /* search start-position only */
3583 11 : begin_position:
3584 11 : if (range > start)
3585 9 : range = start + 1;
3586 : else
3587 2 : range = start;
3588 : }
3589 26 : else if (reg->anchor & ANCHOR_BEGIN_BUF) {
3590 : /* search str-position only */
3591 9 : if (range > start) {
3592 9 : if (start != str) goto mismatch_no_msa;
3593 7 : range = str + 1;
3594 : }
3595 : else {
3596 0 : if (range <= str) {
3597 0 : start = str;
3598 0 : range = str;
3599 : }
3600 : else
3601 0 : goto mismatch_no_msa;
3602 : }
3603 : }
3604 17 : else if (reg->anchor & ANCHOR_END_BUF) {
3605 6 : semi_end = (UChar* )end;
3606 :
3607 6 : end_buf:
3608 6 : if ((OnigDistance )(semi_end - str) < reg->anchor_dmin)
3609 0 : goto mismatch_no_msa;
3610 :
3611 6 : if (range > start) {
3612 4 : if ((OnigDistance )(semi_end - start) > reg->anchor_dmax) {
3613 1 : start = semi_end - reg->anchor_dmax;
3614 1 : if (start < end)
3615 1 : start = onigenc_get_right_adjust_char_head(reg->enc, str, start);
3616 : else { /* match with empty at end */
3617 0 : start = onigenc_get_prev_char_head(reg->enc, str, end);
3618 : }
3619 : }
3620 4 : if ((OnigDistance )(semi_end - (range - 1)) < reg->anchor_dmin) {
3621 2 : range = semi_end - reg->anchor_dmin + 1;
3622 : }
3623 :
3624 4 : if (start >= range) goto mismatch_no_msa;
3625 : }
3626 : else {
3627 2 : if ((OnigDistance )(semi_end - range) > reg->anchor_dmax) {
3628 0 : range = semi_end - reg->anchor_dmax;
3629 : }
3630 2 : if ((OnigDistance )(semi_end - start) < reg->anchor_dmin) {
3631 0 : start = semi_end - reg->anchor_dmin;
3632 0 : start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, start);
3633 0 : if (range > start) goto mismatch_no_msa;
3634 : }
3635 : }
3636 : }
3637 11 : else if (reg->anchor & ANCHOR_SEMI_END_BUF) {
3638 0 : UChar* pre_end = ONIGENC_STEP_BACK(reg->enc, str, end, 1);
3639 :
3640 0 : if (ONIGENC_IS_MBC_NEWLINE(reg->enc, pre_end, end)) {
3641 0 : semi_end = pre_end;
3642 0 : if (semi_end > str && start <= semi_end) {
3643 0 : goto end_buf;
3644 : }
3645 : }
3646 : else {
3647 0 : semi_end = (UChar* )end;
3648 0 : goto end_buf;
3649 : }
3650 : }
3651 11 : else if ((reg->anchor & ANCHOR_ANYCHAR_STAR_ML)) {
3652 11 : goto begin_position;
3653 : }
3654 : }
3655 731 : else if (str == end) { /* empty string */
3656 : static const UChar* address_for_empty_string = (UChar* )"";
3657 :
3658 : #ifdef ONIG_DEBUG_SEARCH
3659 : fprintf(stderr, "onig_search: empty string.\n");
3660 : #endif
3661 :
3662 25 : if (reg->threshold_len == 0) {
3663 0 : start = end = str = address_for_empty_string;
3664 0 : s = (UChar* )start;
3665 0 : prev = (UChar* )NULL;
3666 :
3667 0 : MATCH_ARG_INIT(msa, option, region, start);
3668 : #ifdef USE_COMBINATION_EXPLOSION_CHECK
3669 0 : msa.state_check_buff = (void* )0;
3670 0 : msa.state_check_buff_size = 0;
3671 : #endif
3672 0 : MATCH_AND_RETURN_CHECK;
3673 0 : goto mismatch;
3674 : }
3675 25 : goto mismatch_no_msa;
3676 : }
3677 :
3678 : #ifdef ONIG_DEBUG_SEARCH
3679 : fprintf(stderr, "onig_search(apply anchor): end: %d, start: %d, range: %d\n",
3680 : (int )(end - str), (int )(start - str), (int )(range - str));
3681 : #endif
3682 :
3683 730 : MATCH_ARG_INIT(msa, option, region, orig_start);
3684 730 : STATE_CHECK_BUFF_INIT(msa, end - str, reg->num_comb_exp_check);
3685 :
3686 730 : s = (UChar* )start;
3687 730 : if (range > start) { /* forward search */
3688 676 : if (s > str)
3689 390 : prev = onigenc_get_prev_char_head(reg->enc, str, s);
3690 : else
3691 286 : prev = (UChar* )NULL;
3692 :
3693 676 : if (reg->optimize != ONIG_OPTIMIZE_NONE) {
3694 : UChar *sch_range, *low, *high, *low_prev;
3695 :
3696 602 : sch_range = (UChar* )range;
3697 602 : if (reg->dmax != 0) {
3698 29 : if (reg->dmax == ONIG_INFINITE_DISTANCE)
3699 18 : sch_range = (UChar* )end;
3700 : else {
3701 11 : sch_range += reg->dmax;
3702 11 : if (sch_range > end) sch_range = (UChar* )end;
3703 : }
3704 : }
3705 :
3706 602 : if ((end - start) < reg->threshold_len)
3707 15 : goto mismatch;
3708 :
3709 587 : if (reg->dmax != ONIG_INFINITE_DISTANCE) {
3710 : do {
3711 569 : if (! forward_search_range(reg, str, end, s, sch_range,
3712 125 : &low, &high, &low_prev)) goto mismatch;
3713 444 : if (s < low) {
3714 171 : s = low;
3715 171 : prev = low_prev;
3716 : }
3717 888 : while (s <= high) {
3718 444 : MATCH_AND_RETURN_CHECK;
3719 0 : prev = s;
3720 0 : s += enc_len(reg->enc, s);
3721 : }
3722 0 : } while (s < range);
3723 0 : goto mismatch;
3724 : }
3725 : else { /* check only. */
3726 18 : if (! forward_search_range(reg, str, end, s, sch_range,
3727 1 : &low, &high, (UChar** )NULL)) goto mismatch;
3728 :
3729 17 : if ((reg->anchor & ANCHOR_ANYCHAR_STAR) != 0) {
3730 : do {
3731 0 : MATCH_AND_RETURN_CHECK;
3732 0 : prev = s;
3733 0 : s += enc_len(reg->enc, s);
3734 :
3735 0 : while (!ONIGENC_IS_MBC_NEWLINE(reg->enc, prev, end) && s < range) {
3736 0 : prev = s;
3737 0 : s += enc_len(reg->enc, s);
3738 : }
3739 0 : } while (s < range);
3740 0 : goto mismatch;
3741 : }
3742 : }
3743 : }
3744 :
3745 : do {
3746 292 : MATCH_AND_RETURN_CHECK;
3747 208 : prev = s;
3748 208 : s += enc_len(reg->enc, s);
3749 208 : } while (s < range);
3750 :
3751 7 : if (s == range) { /* because empty match with /$/. */
3752 7 : MATCH_AND_RETURN_CHECK;
3753 : }
3754 : }
3755 : else { /* backward search */
3756 54 : if (reg->optimize != ONIG_OPTIMIZE_NONE) {
3757 : UChar *low, *high, *adjrange, *sch_start;
3758 :
3759 49 : if (range < end)
3760 0 : adjrange = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, range);
3761 : else
3762 49 : adjrange = (UChar* )end;
3763 :
3764 49 : if (reg->dmax != ONIG_INFINITE_DISTANCE &&
3765 : (end - range) >= reg->threshold_len) {
3766 : do {
3767 0 : sch_start = s + reg->dmax;
3768 0 : if (sch_start > end) sch_start = (UChar* )end;
3769 0 : if (backward_search_range(reg, str, end, sch_start, range, adjrange,
3770 : &low, &high) <= 0)
3771 0 : goto mismatch;
3772 :
3773 0 : if (s > high)
3774 0 : s = high;
3775 :
3776 0 : while (s >= low) {
3777 0 : prev = onigenc_get_prev_char_head(reg->enc, str, s);
3778 0 : MATCH_AND_RETURN_CHECK;
3779 0 : s = prev;
3780 : }
3781 0 : } while (s >= range);
3782 0 : goto mismatch;
3783 : }
3784 : else { /* check only. */
3785 49 : if ((end - range) < reg->threshold_len) goto mismatch;
3786 :
3787 0 : sch_start = s;
3788 0 : if (reg->dmax != 0) {
3789 0 : if (reg->dmax == ONIG_INFINITE_DISTANCE)
3790 0 : sch_start = (UChar* )end;
3791 : else {
3792 0 : sch_start += reg->dmax;
3793 0 : if (sch_start > end) sch_start = (UChar* )end;
3794 : else
3795 0 : sch_start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc,
3796 : start, sch_start);
3797 : }
3798 : }
3799 0 : if (backward_search_range(reg, str, end, sch_start, range, adjrange,
3800 0 : &low, &high) <= 0) goto mismatch;
3801 : }
3802 : }
3803 :
3804 : do {
3805 5 : prev = onigenc_get_prev_char_head(reg->enc, str, s);
3806 5 : MATCH_AND_RETURN_CHECK;
3807 0 : s = prev;
3808 0 : } while (s >= range);
3809 : }
3810 :
3811 197 : mismatch:
3812 197 : r = ONIG_MISMATCH;
3813 :
3814 197 : finish:
3815 197 : MATCH_ARG_FREE(msa);
3816 : ONIG_STATE_DEC_THREAD(reg);
3817 :
3818 : /* If result is mismatch and no FIND_NOT_EMPTY option,
3819 : then the region is not setted in match_at(). */
3820 197 : if (IS_FIND_NOT_EMPTY(reg->options) && region
3821 : #ifdef USE_POSIX_REGION_OPTION
3822 : && !IS_POSIX_REGION(option)
3823 : #endif
3824 : ) {
3825 0 : onig_region_clear(region);
3826 : }
3827 :
3828 : #ifdef ONIG_DEBUG
3829 : if (r != ONIG_MISMATCH)
3830 : fprintf(stderr, "onig_search: error %d\n", r);
3831 : #endif
3832 197 : return r;
3833 :
3834 32 : mismatch_no_msa:
3835 32 : r = ONIG_MISMATCH;
3836 32 : finish_no_msa:
3837 : ONIG_STATE_DEC_THREAD(reg);
3838 : #ifdef ONIG_DEBUG
3839 : if (r != ONIG_MISMATCH)
3840 : fprintf(stderr, "onig_search: error %d\n", r);
3841 : #endif
3842 32 : return r;
3843 :
3844 533 : match:
3845 : ONIG_STATE_DEC_THREAD(reg);
3846 533 : MATCH_ARG_FREE(msa);
3847 533 : return s - str;
3848 : }
3849 :
3850 : extern OnigEncoding
3851 : onig_get_encoding(regex_t* reg)
3852 0 : {
3853 0 : return reg->enc;
3854 : }
3855 :
3856 : extern OnigOptionType
3857 : onig_get_options(regex_t* reg)
3858 0 : {
3859 0 : return reg->options;
3860 : }
3861 :
3862 : extern OnigAmbigType
3863 : onig_get_ambig_flag(regex_t* reg)
3864 0 : {
3865 0 : return reg->ambig_flag;
3866 : }
3867 :
3868 : extern OnigSyntaxType*
3869 : onig_get_syntax(regex_t* reg)
3870 0 : {
3871 0 : return reg->syntax;
3872 : }
3873 :
3874 : extern int
3875 : onig_number_of_captures(regex_t* reg)
3876 0 : {
3877 0 : return reg->num_mem;
3878 : }
3879 :
3880 : extern int
3881 : onig_number_of_capture_histories(regex_t* reg)
3882 0 : {
3883 : #ifdef USE_CAPTURE_HISTORY
3884 : int i, n;
3885 :
3886 0 : n = 0;
3887 0 : for (i = 0; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
3888 0 : if (BIT_STATUS_AT(reg->capture_history, i) != 0)
3889 0 : n++;
3890 : }
3891 0 : return n;
3892 : #else
3893 : return 0;
3894 : #endif
3895 : }
3896 :
3897 : extern void
3898 : onig_copy_encoding(OnigEncoding to, OnigEncoding from)
3899 0 : {
3900 0 : *to = *from;
3901 0 : }
3902 :
|
