Ruby 4.1.0dev (2026-11-19 revision b3e890bf959ffb14f55ecd016717417a62ebd04e)
regexec.c (b3e890bf959ffb14f55ecd016717417a62ebd04e)
1/**********************************************************************
2 regexec.c - Onigmo (Oniguruma-mod) (regular expression library)
3**********************************************************************/
4/*-
5 * Copyright (c) 2002-2018 K.Kosako <sndgk393 AT ybb DOT ne DOT jp>
6 * Copyright (c) 2011-2019 K.Takata <kentkt AT csc DOT jp>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31#include "regint.h"
32
33#ifdef RUBY
34# undef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
35#else
36# define USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
37#endif
38
39#ifndef USE_TOKEN_THREADED_VM
40# ifdef __GNUC__
41# define USE_TOKEN_THREADED_VM 1
42# else
43# define USE_TOKEN_THREADED_VM 0
44# endif
45#endif
46
47#ifdef RUBY
48# define ENC_DUMMY_FLAG (1<<24)
49static inline int
50rb_enc_asciicompat(OnigEncoding enc)
51{
52 return ONIGENC_MBC_MINLEN(enc)==1 && !((enc)->ruby_encoding_index & ENC_DUMMY_FLAG);
53}
54# undef ONIGENC_IS_MBC_ASCII_WORD
55# define ONIGENC_IS_MBC_ASCII_WORD(enc,s,end) \
56 (rb_enc_asciicompat(enc) ? (ISALNUM(*s) || *s=='_') : \
57 onigenc_ascii_is_code_ctype( \
58 ONIGENC_MBC_TO_CODE(enc,s,end),ONIGENC_CTYPE_WORD,enc))
59#endif /* RUBY */
60
61#ifdef USE_CRNL_AS_LINE_TERMINATOR
62# define ONIGENC_IS_MBC_CRNL(enc,p,end) \
63 (ONIGENC_MBC_TO_CODE(enc,p,end) == 13 && \
64 ONIGENC_MBC_TO_CODE(enc,(p+enclen(enc,p,end)),end) == 10)
65# define ONIGENC_IS_MBC_NEWLINE_EX(enc,p,start,end,option,check_prev) \
66 is_mbc_newline_ex((enc),(p),(start),(end),(option),(check_prev))
67static int
68is_mbc_newline_ex(OnigEncoding enc, const UChar *p, const UChar *start,
69 const UChar *end, OnigOptionType option, int check_prev)
70{
71 if (IS_NEWLINE_CRLF(option)) {
72 if (ONIGENC_MBC_TO_CODE(enc, p, end) == 0x0a) {
73 if (check_prev) {
74 const UChar *prev = onigenc_get_prev_char_head(enc, start, p, end);
75 if ((prev != NULL) && ONIGENC_MBC_TO_CODE(enc, prev, end) == 0x0d)
76 return 0;
77 else
78 return 1;
79 }
80 else
81 return 1;
82 }
83 else {
84 const UChar *pnext = p + enclen(enc, p, end);
85 if (pnext < end &&
86 ONIGENC_MBC_TO_CODE(enc, p, end) == 0x0d &&
87 ONIGENC_MBC_TO_CODE(enc, pnext, end) == 0x0a)
88 return 1;
89 if (ONIGENC_IS_MBC_NEWLINE(enc, p, end))
90 return 1;
91 return 0;
92 }
93 }
94 else {
95 return ONIGENC_IS_MBC_NEWLINE(enc, p, end);
96 }
97}
98#else /* USE_CRNL_AS_LINE_TERMINATOR */
99# define ONIGENC_IS_MBC_NEWLINE_EX(enc,p,start,end,option,check_prev) \
100 ONIGENC_IS_MBC_NEWLINE((enc), (p), (end))
101#endif /* USE_CRNL_AS_LINE_TERMINATOR */
102
103#ifdef USE_CAPTURE_HISTORY
104static void history_tree_free(OnigCaptureTreeNode* node);
105
106static void
107history_tree_clear(OnigCaptureTreeNode* node)
108{
109 int i;
110
111 if (IS_NOT_NULL(node)) {
112 for (i = 0; i < node->num_childs; i++) {
113 if (IS_NOT_NULL(node->childs[i])) {
114 history_tree_free(node->childs[i]);
115 }
116 }
117 for (i = 0; i < node->allocated; i++) {
118 node->childs[i] = (OnigCaptureTreeNode* )0;
119 }
120 node->num_childs = 0;
121 node->beg = ONIG_REGION_NOTPOS;
122 node->end = ONIG_REGION_NOTPOS;
123 node->group = -1;
124 xfree(node->childs);
125 node->childs = (OnigCaptureTreeNode** )0;
126 }
127}
128
129static void
130history_tree_free(OnigCaptureTreeNode* node)
131{
132 history_tree_clear(node);
133 xfree(node);
134}
135
136static void
137history_root_free(OnigRegion* r)
138{
139 if (IS_NOT_NULL(r->history_root)) {
140 history_tree_free(r->history_root);
141 r->history_root = (OnigCaptureTreeNode* )0;
142 }
143}
144
145static OnigCaptureTreeNode*
146history_node_new(void)
147{
148 OnigCaptureTreeNode* node;
149
150 node = (OnigCaptureTreeNode* )xmalloc(sizeof(OnigCaptureTreeNode));
151 CHECK_NULL_RETURN(node);
152 node->childs = (OnigCaptureTreeNode** )0;
153 node->allocated = 0;
154 node->num_childs = 0;
155 node->group = -1;
156 node->beg = ONIG_REGION_NOTPOS;
157 node->end = ONIG_REGION_NOTPOS;
158
159 return node;
160}
161
162static int
163history_tree_add_child(OnigCaptureTreeNode* parent, OnigCaptureTreeNode* child)
164{
165# define HISTORY_TREE_INIT_ALLOC_SIZE 8
166
167 if (parent->num_childs >= parent->allocated) {
168 int n, i;
169
170 if (IS_NULL(parent->childs)) {
171 n = HISTORY_TREE_INIT_ALLOC_SIZE;
172 parent->childs =
173 (OnigCaptureTreeNode** )xmalloc(sizeof(OnigCaptureTreeNode*) * n);
174 CHECK_NULL_RETURN_MEMERR(parent->childs);
175 }
176 else {
177 OnigCaptureTreeNode** tmp;
178 n = parent->allocated * 2;
179 tmp =
180 (OnigCaptureTreeNode** )xrealloc(parent->childs,
181 sizeof(OnigCaptureTreeNode*) * n);
182 if (tmp == 0) {
183 history_tree_clear(parent);
184 return ONIGERR_MEMORY;
185 }
186 parent->childs = tmp;
187 }
188 for (i = parent->allocated; i < n; i++) {
189 parent->childs[i] = (OnigCaptureTreeNode* )0;
190 }
191 parent->allocated = n;
192 }
193
194 parent->childs[parent->num_childs] = child;
195 parent->num_childs++;
196 return 0;
197}
198
199static OnigCaptureTreeNode*
200history_tree_clone(OnigCaptureTreeNode* node)
201{
202 int i, r;
203 OnigCaptureTreeNode *clone, *child;
204
205 clone = history_node_new();
206 CHECK_NULL_RETURN(clone);
207
208 clone->beg = node->beg;
209 clone->end = node->end;
210 for (i = 0; i < node->num_childs; i++) {
211 child = history_tree_clone(node->childs[i]);
212 if (IS_NULL(child)) {
213 history_tree_free(clone);
214 return (OnigCaptureTreeNode* )0;
215 }
216 r = history_tree_add_child(clone, child);
217 if (r != 0) {
218 history_tree_free(child);
219 history_tree_free(clone);
220 return (OnigCaptureTreeNode* )0;
221 }
222 }
223
224 return clone;
225}
226
227extern OnigCaptureTreeNode*
228onig_get_capture_tree(OnigRegion* region)
229{
230 return region->history_root;
231}
232#endif /* USE_CAPTURE_HISTORY */
233
234#ifdef USE_MATCH_CACHE
235
236/*
237Glossary for "match cache"
238
239"match cache" or "match cache optimization"
240The `Regexp#match` optimization by using a cache.
241
242"cache opcode"
243A cacheable opcode (e.g. `OP_PUSH`, `OP_REPEAT`, etc).
244It is corresponding to some cache points.
245
246"cache point"
247A cacheable point on matching.
248Usually, one-to-one corresponding between a cache opcode and a cache point exists,
249but cache opcodes between `OP_REPEAT` and `OP_REPEAT_INC` have some corresponding
250cache points depending on repetition counts.
251
252"match cache point"
253A pair of a cache point and a position on an input string.
254We encode a match cache point to an integer value by the following equation:
255"match cache point" = "position on input string" * "total number of cache points" + "cache point"
256
257"match cache buffer"
258A bit-array for memoizing (recording) match cache points once backtracked.
259*/
260
261static OnigPosition count_num_cache_opcodes_inner(
262 const regex_t* reg,
263 MemNumType current_repeat_mem, int lookaround_nesting,
264 UChar** pp, long* num_cache_opcodes_ptr
265)
266{
267 UChar* p = *pp;
268 UChar* pend = reg->p + reg->used;
269 LengthType len;
270 MemNumType repeat_mem;
271 OnigEncoding enc = reg->enc;
272 long num_cache_opcodes = *num_cache_opcodes_ptr;
273 OnigPosition result;
274
275 while (p < pend) {
276 switch (*p++) {
277 case OP_FINISH:
278 case OP_END:
279 break;
280
281 case OP_EXACT1: p++; break;
282 case OP_EXACT2: p += 2; break;
283 case OP_EXACT3: p += 3; break;
284 case OP_EXACT4: p += 4; break;
285 case OP_EXACT5: p += 5; break;
286 case OP_EXACTN:
287 GET_LENGTH_INC(len, p); p += len; break;
288 case OP_EXACTMB2N1: p += 2; break;
289 case OP_EXACTMB2N2: p += 4; break;
290 case OP_EXACTMB2N3: p += 6; break;
291 case OP_EXACTMB2N:
292 GET_LENGTH_INC(len, p); p += len * 2; break;
293 case OP_EXACTMB3N:
294 GET_LENGTH_INC(len, p); p += len * 3; break;
295 case OP_EXACTMBN:
296 {
297 int mb_len;
298 GET_LENGTH_INC(mb_len, p);
299 GET_LENGTH_INC(len, p);
300 p += mb_len * len;
301 }
302 break;
303
304 case OP_EXACT1_IC:
305 len = enclen(enc, p, pend); p += len; break;
306 case OP_EXACTN_IC:
307 GET_LENGTH_INC(len, p); p += len; break;
308
309 case OP_CCLASS:
310 case OP_CCLASS_NOT:
311 p += SIZE_BITSET; break;
312 case OP_CCLASS_MB:
313 case OP_CCLASS_MB_NOT:
314 GET_LENGTH_INC(len, p); p += len; break;
315 case OP_CCLASS_MIX:
316 case OP_CCLASS_MIX_NOT:
317 p += SIZE_BITSET;
318 GET_LENGTH_INC(len, p);
319 p += len;
320 break;
321
322 case OP_ANYCHAR:
323 case OP_ANYCHAR_ML:
324 break;
325 case OP_ANYCHAR_STAR:
326 case OP_ANYCHAR_ML_STAR:
327 num_cache_opcodes++; break;
328 case OP_ANYCHAR_STAR_PEEK_NEXT:
329 case OP_ANYCHAR_ML_STAR_PEEK_NEXT:
330 p++; num_cache_opcodes++; break;
331
332 case OP_WORD:
333 case OP_NOT_WORD:
334 case OP_WORD_BOUND:
335 case OP_NOT_WORD_BOUND:
336 case OP_WORD_BEGIN:
337 case OP_WORD_END:
338 break;
339
340 case OP_ASCII_WORD:
341 case OP_NOT_ASCII_WORD:
342 case OP_ASCII_WORD_BOUND:
343 case OP_NOT_ASCII_WORD_BOUND:
344 case OP_ASCII_WORD_BEGIN:
345 case OP_ASCII_WORD_END:
346 break;
347
348 case OP_BEGIN_BUF:
349 case OP_END_BUF:
350 case OP_BEGIN_LINE:
351 case OP_END_LINE:
352 case OP_SEMI_END_BUF:
353 case OP_BEGIN_POSITION:
354 break;
355
356 case OP_BACKREF1:
357 case OP_BACKREF2:
358 case OP_BACKREFN:
359 case OP_BACKREFN_IC:
360 case OP_BACKREF_MULTI:
361 case OP_BACKREF_MULTI_IC:
362 case OP_BACKREF_WITH_LEVEL:
363 goto impossible;
364
365 case OP_MEMORY_START:
366 case OP_MEMORY_START_PUSH:
367 case OP_MEMORY_END_PUSH:
368 case OP_MEMORY_END_PUSH_REC:
369 case OP_MEMORY_END:
370 case OP_MEMORY_END_REC:
371 p += SIZE_MEMNUM;
372 // A memory (capture) in look-around is found.
373 if (lookaround_nesting != 0) {
374 goto impossible;
375 }
376 break;
377
378 case OP_KEEP:
379 break;
380
381 case OP_FAIL:
382 break;
383 case OP_JUMP:
384 p += SIZE_RELADDR;
385 break;
386 case OP_PUSH:
387 p += SIZE_RELADDR;
388 num_cache_opcodes++;
389 break;
390 case OP_POP:
391 break;
392 case OP_PUSH_OR_JUMP_EXACT1:
393 case OP_PUSH_IF_PEEK_NEXT:
394 p += SIZE_RELADDR + 1; num_cache_opcodes++; break;
395 case OP_REPEAT:
396 case OP_REPEAT_NG:
397 if (current_repeat_mem != -1) {
398 // A nested OP_REPEAT is not yet supported.
399 goto impossible;
400 }
401 GET_MEMNUM_INC(repeat_mem, p);
402 p += SIZE_RELADDR;
403 if (reg->repeat_range[repeat_mem].lower == 0 && reg->repeat_range[repeat_mem].upper == 0) {
404 long dummy_num_cache_opcodes = 0;
405 result = count_num_cache_opcodes_inner(reg, repeat_mem, lookaround_nesting, &p, &dummy_num_cache_opcodes);
406 if (result < 0 || dummy_num_cache_opcodes < 0) {
407 goto fail;
408 }
409 } else {
410 if (reg->repeat_range[repeat_mem].lower == 0) {
411 num_cache_opcodes++;
412 }
413 result = count_num_cache_opcodes_inner(reg, repeat_mem, lookaround_nesting, &p, &num_cache_opcodes);
414 if (result < 0 || num_cache_opcodes < 0) {
415 goto fail;
416 }
417 OnigRepeatRange *repeat_range = &reg->repeat_range[repeat_mem];
418 if (repeat_range->lower < repeat_range->upper) {
419 num_cache_opcodes++;
420 }
421 }
422 break;
423 case OP_REPEAT_INC:
424 case OP_REPEAT_INC_NG:
425 GET_MEMNUM_INC(repeat_mem, p);
426 if (repeat_mem != current_repeat_mem) {
427 // A lone or invalid OP_REPEAT_INC is found.
428 goto impossible;
429 }
430 goto exit;
431 case OP_REPEAT_INC_SG:
432 case OP_REPEAT_INC_NG_SG:
433 goto impossible;
434 case OP_NULL_CHECK_START:
435 p += SIZE_MEMNUM;
436 break;
437 case OP_NULL_CHECK_END:
438 case OP_NULL_CHECK_END_MEMST_PUSH:
439 p += SIZE_MEMNUM;
440 break;
441 case OP_NULL_CHECK_END_MEMST:
442 p += SIZE_MEMNUM;
443 break;
444
445 case OP_PUSH_POS:
446 if (lookaround_nesting < 0) {
447 // A look-around nested in a atomic grouping is found.
448 goto impossible;
449 }
450 result = count_num_cache_opcodes_inner(reg, current_repeat_mem, lookaround_nesting + 1, &p, &num_cache_opcodes);
451 if (result < 0 || num_cache_opcodes < 0) {
452 goto fail;
453 }
454 break;
455 case OP_PUSH_POS_NOT:
456 if (lookaround_nesting < 0) {
457 // A look-around nested in a atomic grouping is found.
458 goto impossible;
459 }
460 p += SIZE_RELADDR;
461 result = count_num_cache_opcodes_inner(reg, current_repeat_mem, lookaround_nesting + 1, &p, &num_cache_opcodes);
462 if (result < 0 || num_cache_opcodes < 0) {
463 goto fail;
464 }
465 break;
466 case OP_PUSH_LOOK_BEHIND_NOT:
467 if (lookaround_nesting < 0) {
468 // A look-around nested in a atomic grouping is found.
469 goto impossible;
470 }
471 p += SIZE_RELADDR;
472 p += SIZE_LENGTH;
473 result = count_num_cache_opcodes_inner(reg, current_repeat_mem, lookaround_nesting + 1, &p, &num_cache_opcodes);
474 if (result < 0 || num_cache_opcodes < 0) {
475 goto fail;
476 }
477 break;
478 case OP_PUSH_STOP_BT:
479 if (lookaround_nesting != 0) {
480 // A nested atomic grouping is found.
481 goto impossible;
482 }
483 result = count_num_cache_opcodes_inner(reg, current_repeat_mem, -1, &p, &num_cache_opcodes);
484 if (result < 0 || num_cache_opcodes < 0) {
485 goto fail;
486 }
487 break;
488 case OP_POP_POS:
489 case OP_FAIL_POS:
490 case OP_FAIL_LOOK_BEHIND_NOT:
491 case OP_POP_STOP_BT:
492 goto exit;
493 case OP_LOOK_BEHIND:
494 p += SIZE_LENGTH;
495 break;
496
497 case OP_PUSH_ABSENT_POS:
498 case OP_ABSENT_END:
499 case OP_ABSENT:
500 goto impossible;
501
502 case OP_CALL:
503 case OP_RETURN:
504 goto impossible;
505
506 case OP_CONDITION:
507 goto impossible;
508
509 case OP_STATE_CHECK_PUSH:
510 case OP_STATE_CHECK_PUSH_OR_JUMP:
511 case OP_STATE_CHECK:
512 case OP_STATE_CHECK_ANYCHAR_STAR:
513 case OP_STATE_CHECK_ANYCHAR_ML_STAR:
514 goto impossible;
515
516 case OP_SET_OPTION_PUSH:
517 case OP_SET_OPTION:
518 p += SIZE_OPTION;
519 break;
520
521 default:
522 goto bytecode_error;
523 }
524 }
525
526exit:
527 *pp = p;
528 *num_cache_opcodes_ptr = num_cache_opcodes;
529 return 0;
530
531fail:
532 *num_cache_opcodes_ptr = num_cache_opcodes;
533 return result;
534
535impossible:
536 *num_cache_opcodes_ptr = NUM_CACHE_OPCODES_IMPOSSIBLE;
537 return 0;
538
539bytecode_error:
540 return ONIGERR_UNDEFINED_BYTECODE;
541}
542
543/* count the total number of cache opcodes for allocating a match cache buffer. */
544static OnigPosition
545count_num_cache_opcodes(const regex_t* reg, long* num_cache_opcodes_ptr)
546{
547 UChar* p = reg->p;
548 *num_cache_opcodes_ptr = 0;
549 OnigPosition result = count_num_cache_opcodes_inner(reg, -1, 0, &p, num_cache_opcodes_ptr);
550 if (result == 0 && *num_cache_opcodes_ptr >= 0 && p != reg->p + reg->used) {
551 return ONIGERR_UNDEFINED_BYTECODE;
552 }
553
554 return result;
555}
556
557static OnigPosition
558init_cache_opcodes_inner(
559 const regex_t* reg,
560 MemNumType current_repeat_mem, int lookaround_nesting,
561 OnigCacheOpcode** cache_opcodes_ptr, UChar** pp, long* num_cache_points_ptr
562)
563{
564 UChar* p = *pp;
565 UChar* pend = reg->p + reg->used;
566 UChar* pbegin;
567 LengthType len;
568 MemNumType repeat_mem;
569 OnigEncoding enc = reg->enc;
570 long cache_point = *num_cache_points_ptr;
571 OnigCacheOpcode *cache_opcodes = *cache_opcodes_ptr;
572 OnigPosition result;
573
574# define INC_CACHE_OPCODES if (cache_opcodes != NULL) {\
575 cache_opcodes->addr = pbegin;\
576 cache_opcodes->cache_point = cache_point;\
577 cache_opcodes->outer_repeat_mem = current_repeat_mem;\
578 cache_opcodes->num_cache_points_at_outer_repeat = 0;\
579 cache_opcodes->num_cache_points_in_outer_repeat = 0;\
580 cache_opcodes->lookaround_nesting = lookaround_nesting;\
581 cache_opcodes->match_addr = NULL;\
582 cache_point += lookaround_nesting != 0 ? 2 : 1;\
583 cache_opcodes++;\
584 }
585
586 while (p < pend) {
587 pbegin = p;
588 switch (*p++) {
589 case OP_FINISH:
590 case OP_END:
591 break;
592
593 case OP_EXACT1: p++; break;
594 case OP_EXACT2: p += 2; break;
595 case OP_EXACT3: p += 3; break;
596 case OP_EXACT4: p += 4; break;
597 case OP_EXACT5: p += 5; break;
598 case OP_EXACTN:
599 GET_LENGTH_INC(len, p); p += len; break;
600 case OP_EXACTMB2N1: p += 2; break;
601 case OP_EXACTMB2N2: p += 4; break;
602 case OP_EXACTMB2N3: p += 6; break;
603 case OP_EXACTMB2N:
604 GET_LENGTH_INC(len, p); p += len * 2; break;
605 case OP_EXACTMB3N:
606 GET_LENGTH_INC(len, p); p += len * 3; break;
607 case OP_EXACTMBN:
608 {
609 int mb_len;
610 GET_LENGTH_INC(mb_len, p);
611 GET_LENGTH_INC(len, p);
612 p += mb_len * len;
613 }
614 break;
615
616 case OP_EXACT1_IC:
617 len = enclen(enc, p, pend); p += len; break;
618 case OP_EXACTN_IC:
619 GET_LENGTH_INC(len, p); p += len; break;
620
621 case OP_CCLASS:
622 case OP_CCLASS_NOT:
623 p += SIZE_BITSET; break;
624 case OP_CCLASS_MB:
625 case OP_CCLASS_MB_NOT:
626 GET_LENGTH_INC(len, p); p += len; break;
627 case OP_CCLASS_MIX:
628 case OP_CCLASS_MIX_NOT:
629 p += SIZE_BITSET;
630 GET_LENGTH_INC(len, p);
631 p += len;
632 break;
633
634 case OP_ANYCHAR:
635 case OP_ANYCHAR_ML:
636 break;
637 case OP_ANYCHAR_STAR:
638 case OP_ANYCHAR_ML_STAR:
639 INC_CACHE_OPCODES;
640 break;
641 case OP_ANYCHAR_STAR_PEEK_NEXT:
642 case OP_ANYCHAR_ML_STAR_PEEK_NEXT:
643 p++;
644 INC_CACHE_OPCODES;
645 break;
646
647 case OP_WORD:
648 case OP_NOT_WORD:
649 case OP_WORD_BOUND:
650 case OP_NOT_WORD_BOUND:
651 case OP_WORD_BEGIN:
652 case OP_WORD_END:
653 break;
654
655 case OP_ASCII_WORD:
656 case OP_NOT_ASCII_WORD:
657 case OP_ASCII_WORD_BOUND:
658 case OP_NOT_ASCII_WORD_BOUND:
659 case OP_ASCII_WORD_BEGIN:
660 case OP_ASCII_WORD_END:
661 break;
662
663 case OP_BEGIN_BUF:
664 case OP_END_BUF:
665 case OP_BEGIN_LINE:
666 case OP_END_LINE:
667 case OP_SEMI_END_BUF:
668 case OP_BEGIN_POSITION:
669 break;
670
671 case OP_BACKREF1:
672 case OP_BACKREF2:
673 case OP_BACKREFN:
674 case OP_BACKREFN_IC:
675 case OP_BACKREF_MULTI:
676 case OP_BACKREF_MULTI_IC:
677 case OP_BACKREF_WITH_LEVEL:
678 goto unexpected_bytecode_error;
679
680 case OP_MEMORY_START:
681 case OP_MEMORY_START_PUSH:
682 case OP_MEMORY_END_PUSH:
683 case OP_MEMORY_END_PUSH_REC:
684 case OP_MEMORY_END:
685 case OP_MEMORY_END_REC:
686 p += SIZE_MEMNUM;
687 if (lookaround_nesting != 0) {
688 goto unexpected_bytecode_error;
689 }
690 break;
691
692 case OP_KEEP:
693 break;
694
695 case OP_FAIL:
696 break;
697 case OP_JUMP:
698 p += SIZE_RELADDR;
699 break;
700 case OP_PUSH:
701 p += SIZE_RELADDR;
702 INC_CACHE_OPCODES;
703 break;
704 case OP_POP:
705 break;
706 case OP_PUSH_OR_JUMP_EXACT1:
707 case OP_PUSH_IF_PEEK_NEXT:
708 p += SIZE_RELADDR + 1;
709 INC_CACHE_OPCODES;
710 break;
711 case OP_REPEAT:
712 case OP_REPEAT_NG:
713 GET_MEMNUM_INC(repeat_mem, p);
714 p += SIZE_RELADDR;
715 if (reg->repeat_range[repeat_mem].lower == 0 && reg->repeat_range[repeat_mem].upper == 0) {
716 long dummy_num_cache_points = 0;
717 OnigCacheOpcode* dummy_cache_opcodes = NULL;
718 result = init_cache_opcodes_inner(reg, repeat_mem, lookaround_nesting, &dummy_cache_opcodes, &p, &dummy_num_cache_points);
719 if (result != 0) {
720 goto fail;
721 }
722 } else {
723 if (reg->repeat_range[repeat_mem].lower == 0) {
724 INC_CACHE_OPCODES;
725 }
726 {
727 long num_cache_points_in_repeat = 0;
728 long num_cache_points_at_repeat = cache_point;
729 OnigCacheOpcode* cache_opcodes_in_repeat = cache_opcodes;
730 result = init_cache_opcodes_inner(reg, repeat_mem, lookaround_nesting, &cache_opcodes, &p, &num_cache_points_in_repeat);
731 if (result != 0) {
732 goto fail;
733 }
734 OnigRepeatRange *repeat_range = &reg->repeat_range[repeat_mem];
735 if (repeat_range->lower < repeat_range->upper) {
736 INC_CACHE_OPCODES;
737 cache_point -= lookaround_nesting != 0 ? 2 : 1;
738 }
739 int repeat_bounds = repeat_range->upper == 0x7fffffff ? 1 : repeat_range->upper - repeat_range->lower;
740 cache_point += num_cache_points_in_repeat * repeat_range->lower + (num_cache_points_in_repeat + (lookaround_nesting != 0 ? 2 : 1)) * repeat_bounds;
741 for (; cache_opcodes_in_repeat < cache_opcodes; cache_opcodes_in_repeat++) {
742 cache_opcodes_in_repeat->num_cache_points_at_outer_repeat = num_cache_points_at_repeat;
743 cache_opcodes_in_repeat->num_cache_points_in_outer_repeat = num_cache_points_in_repeat;
744 }
745 }
746 }
747 break;
748 case OP_REPEAT_INC:
749 case OP_REPEAT_INC_NG:
750 p += SIZE_MEMNUM;
751 goto exit;
752 case OP_REPEAT_INC_SG:
753 case OP_REPEAT_INC_NG_SG:
754 goto unexpected_bytecode_error;
755 case OP_NULL_CHECK_START:
756 p += SIZE_MEMNUM;
757 break;
758 case OP_NULL_CHECK_END:
759 case OP_NULL_CHECK_END_MEMST_PUSH:
760 p += SIZE_MEMNUM;
761 break;
762 case OP_NULL_CHECK_END_MEMST:
763 p += SIZE_MEMNUM;
764 break;
765
766 case OP_PUSH_POS:
767 lookaround:
768 {
769 OnigCacheOpcode* cache_opcodes_in_lookaround = cache_opcodes;
770 result = init_cache_opcodes_inner(reg, current_repeat_mem, lookaround_nesting + 1, &cache_opcodes, &p, &cache_point);
771 if (result != 0) {
772 goto fail;
773 }
774 UChar* match_addr = p - 1;
775 for (; cache_opcodes_in_lookaround < cache_opcodes; cache_opcodes_in_lookaround++) {
776 if (cache_opcodes_in_lookaround->match_addr == NULL) {
777 cache_opcodes_in_lookaround->match_addr = match_addr;
778 }
779 }
780 }
781 break;
782 case OP_PUSH_POS_NOT:
783 p += SIZE_RELADDR;
784 goto lookaround;
785 case OP_PUSH_LOOK_BEHIND_NOT:
786 p += SIZE_RELADDR;
787 p += SIZE_LENGTH;
788 goto lookaround;
789 case OP_PUSH_STOP_BT:
790 {
791 OnigCacheOpcode* cache_opcodes_in_atomic = cache_opcodes;
792 result = init_cache_opcodes_inner(reg, current_repeat_mem, -1, &cache_opcodes, &p, &cache_point);
793 if (result != 0) {
794 goto fail;
795 }
796 UChar* match_addr = p - 1;
797 for (; cache_opcodes_in_atomic < cache_opcodes; cache_opcodes_in_atomic++) {
798 if (cache_opcodes_in_atomic->match_addr == NULL) {
799 cache_opcodes_in_atomic->match_addr = match_addr;
800 }
801 }
802 }
803 break;
804 case OP_POP_POS:
805 case OP_FAIL_POS:
806 case OP_FAIL_LOOK_BEHIND_NOT:
807 case OP_POP_STOP_BT:
808 goto exit;
809 case OP_LOOK_BEHIND:
810 p += SIZE_LENGTH;
811 break;
812
813 case OP_ABSENT_END:
814 case OP_ABSENT:
815 goto unexpected_bytecode_error;
816
817 case OP_CALL:
818 case OP_RETURN:
819 goto unexpected_bytecode_error;
820
821 case OP_CONDITION:
822 goto unexpected_bytecode_error;
823
824 case OP_STATE_CHECK_PUSH:
825 case OP_STATE_CHECK_PUSH_OR_JUMP:
826 case OP_STATE_CHECK:
827 case OP_STATE_CHECK_ANYCHAR_STAR:
828 case OP_STATE_CHECK_ANYCHAR_ML_STAR:
829 goto unexpected_bytecode_error;
830
831 case OP_SET_OPTION_PUSH:
832 case OP_SET_OPTION:
833 p += SIZE_OPTION;
834 break;
835
836 default:
837 goto bytecode_error;
838 }
839 }
840
841exit:
842 *cache_opcodes_ptr = cache_opcodes;
843 *pp = p;
844 *num_cache_points_ptr = cache_point;
845 return 0;
846
847fail:
848 return result;
849
850unexpected_bytecode_error:
851 return ONIGERR_UNEXPECTED_BYTECODE;
852
853bytecode_error:
854 return ONIGERR_UNDEFINED_BYTECODE;
855}
856
857/* collect cache opcodes from the given regex program, and compute the total number of cache points. */
858static OnigPosition
859init_cache_opcodes(const regex_t* reg, OnigCacheOpcode* cache_opcodes_ptr, long* num_cache_points_ptr)
860{
861 UChar* p = reg->p;
862 *num_cache_points_ptr = 0;
863 OnigPosition result = init_cache_opcodes_inner(reg, -1, 0, &cache_opcodes_ptr, &p, num_cache_points_ptr);
864 if (result == 0 && p != reg->p + reg->used) {
865 return ONIGERR_UNDEFINED_BYTECODE;
866 }
867
868 return result;
869}
870#else
871static OnigPosition
872count_num_cache_opcodes(regex_t* reg, long* num_cache_opcodes)
873{
874 *num_cache_opcodes = NUM_CACHE_OPCODES_IMPOSSIBLE;
875 return 0;
876}
877#endif /* USE_MATCH_CACHE */
878
879extern int
880onig_check_linear_time(OnigRegexType* reg)
881{
882 long num_cache_opcodes = 0;
883 count_num_cache_opcodes(reg, &num_cache_opcodes);
884 return num_cache_opcodes != NUM_CACHE_OPCODES_IMPOSSIBLE;
885}
886
887extern void
888onig_region_clear(OnigRegion* region)
889{
890 int i;
891
892 for (i = 0; i < region->num_regs; i++) {
893 region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;
894 }
895#ifdef USE_CAPTURE_HISTORY
896 history_root_free(region);
897#endif
898}
899
900extern int
901onig_region_resize(OnigRegion* region, int n)
902{
903 region->num_regs = n;
904
905 if (n < ONIG_NREGION)
906 n = ONIG_NREGION;
907
908 if (region->allocated == 0) {
909 region->beg = (OnigPosition* )xmalloc(n * sizeof(OnigPosition));
910 if (region->beg == 0)
911 return ONIGERR_MEMORY;
912
913 region->end = (OnigPosition* )xmalloc(n * sizeof(OnigPosition));
914 if (region->end == 0) {
915 xfree(region->beg);
916 return ONIGERR_MEMORY;
917 }
918
919 region->allocated = n;
920 }
921 else if (region->allocated < n) {
922 OnigPosition *tmp;
923
924 region->allocated = 0;
925 tmp = (OnigPosition* )xrealloc(region->beg, n * sizeof(OnigPosition));
926 if (tmp == 0) {
927 xfree(region->beg);
928 xfree(region->end);
929 return ONIGERR_MEMORY;
930 }
931 region->beg = tmp;
932 tmp = (OnigPosition* )xrealloc(region->end, n * sizeof(OnigPosition));
933 if (tmp == 0) {
934 xfree(region->beg);
935 xfree(region->end);
936 return ONIGERR_MEMORY;
937 }
938 region->end = tmp;
939
940 region->allocated = n;
941 }
942
943 return 0;
944}
945
946static int
947onig_region_resize_clear(OnigRegion* region, int n)
948{
949 int r;
950
951 r = onig_region_resize(region, n);
952 if (r != 0) return r;
953 onig_region_clear(region);
954 return 0;
955}
956
957extern int
958onig_region_set(OnigRegion* region, int at, int beg, int end)
959{
960 if (at < 0) return ONIGERR_INVALID_ARGUMENT;
961
962 if (at >= region->allocated) {
963 int r = onig_region_resize(region, at + 1);
964 if (r < 0) return r;
965 }
966
967 region->beg[at] = beg;
968 region->end[at] = end;
969 return 0;
970}
971
972extern void
973onig_region_init(OnigRegion* region)
974{
975 region->num_regs = 0;
976 region->allocated = 0;
977 region->beg = (OnigPosition* )0;
978 region->end = (OnigPosition* )0;
979#ifdef USE_CAPTURE_HISTORY
980 region->history_root = (OnigCaptureTreeNode* )0;
981#endif
982}
983
984extern OnigRegion*
985onig_region_new(void)
986{
987 OnigRegion* r;
988
989 r = (OnigRegion* )xmalloc(sizeof(OnigRegion));
990 if (r)
991 onig_region_init(r);
992 return r;
993}
994
995extern void
996onig_region_free(OnigRegion* r, int free_self)
997{
998 if (r) {
999 if (r->allocated > 0) {
1000 xfree(r->beg);
1001 xfree(r->end);
1002 }
1003#ifdef USE_CAPTURE_HISTORY
1004 history_root_free(r);
1005#endif
1006 if (free_self) {
1007 xfree(r);
1008 }
1009 else {
1010 memset(r, 0, sizeof(OnigRegion));
1011 }
1012 }
1013}
1014
1015extern void
1016onig_region_copy(OnigRegion* to, const OnigRegion* from)
1017{
1018#define RREGC_SIZE (sizeof(int) * from->num_regs)
1019 int i, r;
1020
1021 if (to == from) return;
1022
1023 r = onig_region_resize(to, from->num_regs);
1024 if (r) return;
1025
1026 for (i = 0; i < from->num_regs; i++) {
1027 to->beg[i] = from->beg[i];
1028 to->end[i] = from->end[i];
1029 }
1030 to->num_regs = from->num_regs;
1031
1032#ifdef USE_CAPTURE_HISTORY
1033 history_root_free(to);
1034
1035 if (IS_NOT_NULL(from->history_root)) {
1036 to->history_root = history_tree_clone(from->history_root);
1037 }
1038#endif
1039}
1040
1041
1043#define INVALID_STACK_INDEX -1
1044
1045/* stack type */
1046/* used by normal-POP */
1047#define STK_ALT 0x0001
1048#define STK_LOOK_BEHIND_NOT 0x0002
1049#define STK_POS_NOT 0x0003
1050/* handled by normal-POP */
1051#define STK_MEM_START 0x0100
1052#define STK_MEM_END 0x8200
1053#define STK_REPEAT_INC 0x0300
1054#define STK_STATE_CHECK_MARK 0x1000
1055/* avoided by normal-POP */
1056#define STK_NULL_CHECK_START 0x3000
1057#define STK_NULL_CHECK_END 0x5000 /* for recursive call */
1058#define STK_MEM_END_MARK 0x8400
1059#define STK_POS 0x0500 /* used when POP-POS */
1060#define STK_STOP_BT 0x0600 /* mark for "(?>...)" */
1061#define STK_REPEAT 0x0700
1062#define STK_CALL_FRAME 0x0800
1063#define STK_RETURN 0x0900
1064#define STK_VOID 0x0a00 /* for fill a blank */
1065#define STK_ABSENT_POS 0x0b00 /* for absent */
1066#define STK_ABSENT 0x0c00 /* absent inner loop marker */
1067#define STK_MATCH_CACHE_POINT 0x0d00 /* for the match cache optimization */
1068#define STK_ATOMIC_MATCH_CACHE_POINT 0x0e00
1069
1070/* stack type check mask */
1071#define STK_MASK_POP_USED 0x00ff
1072#define STK_MASK_TO_VOID_TARGET 0x10ff
1073#define STK_MASK_MEM_END_OR_MARK 0x8000 /* MEM_END or MEM_END_MARK */
1074
1075#ifdef USE_MATCH_CACHE
1076#define MATCH_ARG_INIT_MATCH_CACHE(msa) do {\
1077 (msa).match_cache_status = MATCH_CACHE_STATUS_UNINIT;\
1078 (msa).num_fails = 0;\
1079 (msa).num_cache_opcodes = NUM_CACHE_OPCODES_UNINIT;\
1080 (msa).cache_opcodes = (OnigCacheOpcode*)NULL;\
1081 (msa).num_cache_points = 0;\
1082 (msa).match_cache_buf = (uint8_t*)NULL;\
1083} while(0)
1084#define MATCH_ARG_FREE_MATCH_CACHE(msa) do {\
1085 xfree((msa).cache_opcodes);\
1086 xfree((msa).match_cache_buf);\
1087 (msa).cache_opcodes = (OnigCacheOpcode*)NULL;\
1088 (msa).match_cache_buf = (uint8_t*)NULL;\
1089} while(0)
1090#else
1091#define MATCH_ARG_INIT_MATCH_CACHE(msa)
1092#define MATCH_ARG_FREE_MATCH_CACHE(msa)
1093#endif
1094
1095#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
1096# define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start, arg_gpos) do {\
1097 (msa).stack_p = (void* )0;\
1098 (msa).options = (arg_option);\
1099 (msa).region = (arg_region);\
1100 (msa).start = (arg_start);\
1101 (msa).gpos = (arg_gpos);\
1102 (msa).best_len = ONIG_MISMATCH;\
1103 (msa).counter = 0;\
1104 (msa).end_time = 0;\
1105 MATCH_ARG_INIT_MATCH_CACHE(msa);\
1106} while(0)
1107#else
1108# define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start, arg_gpos) do {\
1109 (msa).stack_p = (void* )0;\
1110 (msa).options = (arg_option);\
1111 (msa).region = (arg_region);\
1112 (msa).start = (arg_start);\
1113 (msa).gpos = (arg_gpos);\
1114 (msa).counter = 0;\
1115 (msa).end_time = 0;\
1116 MATCH_ARG_INIT_MATCH_CACHE(msa);\
1117} while(0)
1118#endif
1119
1120#ifdef USE_COMBINATION_EXPLOSION_CHECK
1121
1122# define STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE 16
1123
1124# define STATE_CHECK_BUFF_INIT(msa, str_len, offset, state_num) do { \
1125 if ((state_num) > 0 && str_len >= STATE_CHECK_STRING_THRESHOLD_LEN) {\
1126 unsigned int size = (unsigned int )(((str_len) + 1) * (state_num) + 7) >> 3;\
1127 offset = ((offset) * (state_num)) >> 3;\
1128 if (size > 0 && offset < size && size < STATE_CHECK_BUFF_MAX_SIZE) {\
1129 if (size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) {\
1130 (msa).state_check_buff = (void* )xmalloc(size);\
1131 CHECK_NULL_RETURN_MEMERR((msa).state_check_buff);\
1132 }\
1133 else \
1134 (msa).state_check_buff = (void* )xalloca(size);\
1135 xmemset(((char* )((msa).state_check_buff)+(offset)), 0, \
1136 (size_t )(size - (offset))); \
1137 (msa).state_check_buff_size = size;\
1138 }\
1139 else {\
1140 (msa).state_check_buff = (void* )0;\
1141 (msa).state_check_buff_size = 0;\
1142 }\
1143 }\
1144 else {\
1145 (msa).state_check_buff = (void* )0;\
1146 (msa).state_check_buff_size = 0;\
1147 }\
1148 } while(0)
1149
1150# define MATCH_ARG_FREE(msa) do {\
1151 xfree((msa).stack_p);\
1152 if ((msa).state_check_buff_size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) { \
1153 xfree((msa).state_check_buff);\
1154 }\
1155 MATCH_ARG_FREE_MATCH_CACHE(msa);\
1156} while(0)
1157#else /* USE_COMBINATION_EXPLOSION_CHECK */
1158# define MATCH_ARG_FREE(msa) do {\
1159 xfree((msa).stack_p);\
1160 MATCH_ARG_FREE_MATCH_CACHE(msa);\
1161} while (0)
1162#endif /* USE_COMBINATION_EXPLOSION_CHECK */
1163
1164
1165
1166#define MAX_PTR_NUM 100
1167
1168#define STACK_INIT(alloc_addr, heap_addr, ptr_num, stack_num) do {\
1169 if (ptr_num > MAX_PTR_NUM) {\
1170 alloc_addr = (char* )xmalloc(sizeof(OnigStackIndex) * (ptr_num));\
1171 heap_addr = alloc_addr;\
1172 if (msa->stack_p) {\
1173 stk_alloc = (OnigStackType* )(msa->stack_p);\
1174 stk_base = stk_alloc;\
1175 stk = stk_base;\
1176 stk_end = stk_base + msa->stack_n;\
1177 }\
1178 else {\
1179 stk_alloc = (OnigStackType* )xalloca(sizeof(OnigStackType) * (stack_num));\
1180 stk_base = stk_alloc;\
1181 stk = stk_base;\
1182 stk_end = stk_base + (stack_num);\
1183 }\
1184 }\
1185 else if (msa->stack_p) {\
1186 alloc_addr = (char* )xalloca(sizeof(OnigStackIndex) * (ptr_num));\
1187 heap_addr = NULL;\
1188 stk_alloc = (OnigStackType* )(msa->stack_p);\
1189 stk_base = stk_alloc;\
1190 stk = stk_base;\
1191 stk_end = stk_base + msa->stack_n;\
1192 }\
1193 else {\
1194 alloc_addr = (char* )xalloca(sizeof(OnigStackIndex) * (ptr_num)\
1195 + sizeof(OnigStackType) * (stack_num));\
1196 heap_addr = NULL;\
1197 stk_alloc = (OnigStackType* )(alloc_addr + sizeof(OnigStackIndex) * (ptr_num));\
1198 stk_base = stk_alloc;\
1199 stk = stk_base;\
1200 stk_end = stk_base + (stack_num);\
1201 }\
1202} while(0)
1203
1204#define STACK_SAVE do{\
1205 if (stk_base != stk_alloc) {\
1206 msa->stack_p = stk_base;\
1207 msa->stack_n = stk_end - stk_base; /* TODO: check overflow */\
1208 };\
1209} while(0)
1210
1211static unsigned int MatchStackLimitSize = DEFAULT_MATCH_STACK_LIMIT_SIZE;
1212
1213extern unsigned int
1214onig_get_match_stack_limit_size(void)
1215{
1216 return MatchStackLimitSize;
1217}
1218
1219extern int
1220onig_set_match_stack_limit_size(unsigned int size)
1221{
1222 MatchStackLimitSize = size;
1223 return 0;
1224}
1225
1226static int
1227stack_double(OnigStackType** arg_stk_base, OnigStackType** arg_stk_end,
1228 OnigStackType** arg_stk, OnigStackType* stk_alloc, OnigMatchArg* msa)
1229{
1230 size_t n;
1231 OnigStackType *x, *stk_base, *stk_end, *stk;
1232
1233 stk_base = *arg_stk_base;
1234 stk_end = *arg_stk_end;
1235 stk = *arg_stk;
1236
1237 n = stk_end - stk_base;
1238 if (stk_base == stk_alloc && IS_NULL(msa->stack_p)) {
1239 x = (OnigStackType* )xmalloc(sizeof(OnigStackType) * n * 2);
1240 if (IS_NULL(x)) {
1241 STACK_SAVE;
1242 return ONIGERR_MEMORY;
1243 }
1244 xmemcpy(x, stk_base, n * sizeof(OnigStackType));
1245 n *= 2;
1246 }
1247 else {
1248 unsigned int limit_size = MatchStackLimitSize;
1249 n *= 2;
1250 if (limit_size != 0 && n > limit_size) {
1251 if ((unsigned int )(stk_end - stk_base) == limit_size)
1252 return ONIGERR_MATCH_STACK_LIMIT_OVER;
1253 else
1254 n = limit_size;
1255 }
1256 x = (OnigStackType* )xrealloc(stk_base, sizeof(OnigStackType) * n);
1257 if (IS_NULL(x)) {
1258 STACK_SAVE;
1259 return ONIGERR_MEMORY;
1260 }
1261 }
1262 *arg_stk = x + (stk - stk_base);
1263 *arg_stk_base = x;
1264 *arg_stk_end = x + n;
1265 return 0;
1266}
1267
1268#define STACK_ENSURE(n) do {\
1269 if (stk_end - stk < (n)) {\
1270 int r = stack_double(&stk_base, &stk_end, &stk, stk_alloc, msa);\
1271 if (r != 0) {\
1272 STACK_SAVE;\
1273 xfree(xmalloc_base);\
1274 return r;\
1275 }\
1276 }\
1277} while(0)
1278
1279#define STACK_AT(index) (stk_base + (index))
1280#define GET_STACK_INDEX(stk) ((stk) - stk_base)
1281
1282#define STACK_PUSH_TYPE(stack_type) do {\
1283 STACK_ENSURE(1);\
1284 stk->type = (stack_type);\
1285 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1286 STACK_INC;\
1287} while(0)
1288
1289#define IS_TO_VOID_TARGET(stk) (((stk)->type & STK_MASK_TO_VOID_TARGET) != 0)
1290
1291#ifdef USE_COMBINATION_EXPLOSION_CHECK
1292# define STATE_CHECK_POS(s,snum) \
1293 (((s) - str) * num_comb_exp_check + ((snum) - 1))
1294# define STATE_CHECK_VAL(v,snum) do {\
1295 if (state_check_buff != NULL) {\
1296 ptrdiff_t x = STATE_CHECK_POS(s,snum);\
1297 (v) = state_check_buff[x/8] & (1<<(x%8));\
1298 }\
1299 else (v) = 0;\
1300} while(0)
1301
1302
1303# define ELSE_IF_STATE_CHECK_MARK(stk) \
1304 else if ((stk)->type == STK_STATE_CHECK_MARK) { \
1305 ptrdiff_t x = STATE_CHECK_POS(stk->u.state.pstr, stk->u.state.state_check);\
1306 state_check_buff[x/8] |= (1<<(x%8)); \
1307 }
1308
1309# define STACK_PUSH(stack_type,pat,s,sprev,keep) do {\
1310 STACK_ENSURE(1);\
1311 stk->type = (stack_type);\
1312 stk->u.state.pcode = (pat);\
1313 stk->u.state.pstr = (s);\
1314 stk->u.state.pstr_prev = (sprev);\
1315 stk->u.state.state_check = 0;\
1316 stk->u.state.pkeep = (keep);\
1317 STACK_INC;\
1318} while(0)
1319
1320# define STACK_PUSH_ENSURED(stack_type,pat) do {\
1321 stk->type = (stack_type);\
1322 stk->u.state.pcode = (pat);\
1323 stk->u.state.state_check = 0;\
1324 STACK_INC;\
1325} while(0)
1326
1327# define STACK_PUSH_ALT_WITH_STATE_CHECK(pat,s,sprev,snum,keep) do {\
1328 STACK_ENSURE(1);\
1329 stk->type = STK_ALT;\
1330 stk->u.state.pcode = (pat);\
1331 stk->u.state.pstr = (s);\
1332 stk->u.state.pstr_prev = (sprev);\
1333 stk->u.state.state_check = ((state_check_buff != NULL) ? (snum) : 0);\
1334 stk->u.state.pkeep = (keep);\
1335 STACK_INC;\
1336} while(0)
1337
1338# define STACK_PUSH_STATE_CHECK(s,snum) do {\
1339 if (state_check_buff != NULL) {\
1340 STACK_ENSURE(1);\
1341 stk->type = STK_STATE_CHECK_MARK;\
1342 stk->u.state.pstr = (s);\
1343 stk->u.state.state_check = (snum);\
1344 STACK_INC;\
1345 }\
1346} while(0)
1347
1348#else /* USE_COMBINATION_EXPLOSION_CHECK */
1349
1350# define ELSE_IF_STATE_CHECK_MARK(stk)
1351
1352# define STACK_PUSH(stack_type,pat,s,sprev,keep) do {\
1353 STACK_ENSURE(1);\
1354 stk->type = (stack_type);\
1355 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1356 stk->u.state.pcode = (pat);\
1357 stk->u.state.pstr = (s);\
1358 stk->u.state.pstr_prev = (sprev);\
1359 stk->u.state.pkeep = (keep);\
1360 STACK_INC;\
1361} while(0)
1362
1363# define STACK_PUSH_ENSURED(stack_type,pat) do {\
1364 stk->type = (stack_type);\
1365 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1366 stk->u.state.pcode = (pat);\
1367 STACK_INC;\
1368} while(0)
1369#endif /* USE_COMBINATION_EXPLOSION_CHECK */
1370
1371#define STACK_PUSH_ALT(pat,s,sprev,keep) STACK_PUSH(STK_ALT,pat,s,sprev,keep)
1372#define STACK_PUSH_POS(s,sprev,keep) STACK_PUSH(STK_POS,NULL_UCHARP,s,sprev,keep)
1373#define STACK_PUSH_POS_NOT(pat,s,sprev,keep) STACK_PUSH(STK_POS_NOT,pat,s,sprev,keep)
1374#define STACK_PUSH_ABSENT STACK_PUSH_TYPE(STK_ABSENT)
1375#define STACK_PUSH_STOP_BT STACK_PUSH_TYPE(STK_STOP_BT)
1376#define STACK_PUSH_LOOK_BEHIND_NOT(pat,s,sprev,keep) \
1377 STACK_PUSH(STK_LOOK_BEHIND_NOT,pat,s,sprev,keep)
1378
1379#define STACK_PUSH_REPEAT(id, pat) do {\
1380 STACK_ENSURE(1);\
1381 stk->type = STK_REPEAT;\
1382 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1383 stk->u.repeat.num = (id);\
1384 stk->u.repeat.pcode = (pat);\
1385 stk->u.repeat.count = 0;\
1386 STACK_INC;\
1387} while(0)
1388
1389#define STACK_PUSH_REPEAT_INC(sindex) do {\
1390 STACK_ENSURE(1);\
1391 stk->type = STK_REPEAT_INC;\
1392 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1393 stk->u.repeat_inc.si = (sindex);\
1394 STACK_INC;\
1395} while(0)
1396
1397#define STACK_PUSH_MEM_START(mnum, s) do {\
1398 STACK_ENSURE(1);\
1399 stk->type = STK_MEM_START;\
1400 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1401 stk->u.mem.num = (mnum);\
1402 stk->u.mem.pstr = (s);\
1403 stk->u.mem.start = mem_start_stk[mnum];\
1404 stk->u.mem.end = mem_end_stk[mnum];\
1405 mem_start_stk[mnum] = GET_STACK_INDEX(stk);\
1406 mem_end_stk[mnum] = INVALID_STACK_INDEX;\
1407 STACK_INC;\
1408} while(0)
1409
1410#define STACK_PUSH_MEM_END(mnum, s) do {\
1411 STACK_ENSURE(1);\
1412 stk->type = STK_MEM_END;\
1413 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1414 stk->u.mem.num = (mnum);\
1415 stk->u.mem.pstr = (s);\
1416 stk->u.mem.start = mem_start_stk[mnum];\
1417 stk->u.mem.end = mem_end_stk[mnum];\
1418 mem_end_stk[mnum] = GET_STACK_INDEX(stk);\
1419 STACK_INC;\
1420} while(0)
1421
1422#define STACK_PUSH_MEM_END_MARK(mnum) do {\
1423 STACK_ENSURE(1);\
1424 stk->type = STK_MEM_END_MARK;\
1425 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1426 stk->u.mem.num = (mnum);\
1427 STACK_INC;\
1428} while(0)
1429
1430#define STACK_GET_MEM_START(mnum, k) do {\
1431 int level = 0;\
1432 k = stk;\
1433 while (k > stk_base) {\
1434 k--;\
1435 if ((k->type & STK_MASK_MEM_END_OR_MARK) != 0 \
1436 && k->u.mem.num == (mnum)) {\
1437 level++;\
1438 }\
1439 else if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
1440 if (level == 0) break;\
1441 level--;\
1442 }\
1443 }\
1444} while(0)
1445
1446#define STACK_GET_MEM_RANGE(k, mnum, start, end) do {\
1447 int level = 0;\
1448 while (k < stk) {\
1449 if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
1450 if (level == 0) (start) = k->u.mem.pstr;\
1451 level++;\
1452 }\
1453 else if (k->type == STK_MEM_END && k->u.mem.num == (mnum)) {\
1454 level--;\
1455 if (level == 0) {\
1456 (end) = k->u.mem.pstr;\
1457 break;\
1458 }\
1459 }\
1460 k++;\
1461 }\
1462} while(0)
1463
1464#define STACK_PUSH_NULL_CHECK_START(cnum, s) do {\
1465 STACK_ENSURE(1);\
1466 stk->type = STK_NULL_CHECK_START;\
1467 stk->null_check = (OnigStackIndex)(stk - stk_base);\
1468 stk->u.null_check.num = (cnum);\
1469 stk->u.null_check.pstr = (s);\
1470 STACK_INC;\
1471} while(0)
1472
1473#define STACK_PUSH_NULL_CHECK_END(cnum) do {\
1474 STACK_ENSURE(1);\
1475 stk->type = STK_NULL_CHECK_END;\
1476 stk->null_check = (OnigStackIndex)(stk - stk_base);\
1477 stk->u.null_check.num = (cnum);\
1478 STACK_INC;\
1479} while(0)
1480
1481#define STACK_PUSH_CALL_FRAME(pat) do {\
1482 STACK_ENSURE(1);\
1483 stk->type = STK_CALL_FRAME;\
1484 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1485 stk->u.call_frame.ret_addr = (pat);\
1486 STACK_INC;\
1487} while(0)
1488
1489#define STACK_PUSH_RETURN do {\
1490 STACK_ENSURE(1);\
1491 stk->type = STK_RETURN;\
1492 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1493 STACK_INC;\
1494} while(0)
1495
1496#define STACK_PUSH_ABSENT_POS(start, end) do {\
1497 STACK_ENSURE(1);\
1498 stk->type = STK_ABSENT_POS;\
1499 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1500 stk->u.absent_pos.abs_pstr = (start);\
1501 stk->u.absent_pos.end_pstr = (end);\
1502 STACK_INC;\
1503} while(0)
1504
1505#define STACK_PUSH_MATCH_CACHE_POINT(match_cache_point_index, match_cache_point_mask) do {\
1506 STACK_ENSURE(1);\
1507 stk->type = STK_MATCH_CACHE_POINT;\
1508 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1509 stk->u.match_cache_point.index = (match_cache_point_index);\
1510 stk->u.match_cache_point.mask = (match_cache_point_mask);\
1511 STACK_INC;\
1512} while(0)
1513
1514
1515#ifdef ONIG_DEBUG
1516# define STACK_BASE_CHECK(p, at) \
1517 if ((p) < stk_base) {\
1518 fprintf(stderr, "at %s\n", at);\
1519 goto stack_error;\
1520 }
1521#else
1522# define STACK_BASE_CHECK(p, at)
1523#endif
1524
1525#ifdef ONIG_DEBUG_MATCH_CACHE
1526# define MATCH_CACHE_DEBUG_MEMOIZE(stkp) fprintf(stderr, "MATCH CACHE: memoize (index=%td mask=%d)\n", stkp->u.match_cache_point.index, stkp->u.match_cache_point.mask);
1527#else
1528# define MATCH_CACHE_DEBUG_MEMOIZE(stkp) ((void) 0)
1529#endif
1530
1531#ifdef USE_MATCH_CACHE
1532# define INC_NUM_FAILS msa->num_fails++
1533# define MEMOIZE_MATCH_CACHE_POINT do {\
1534 if (stk->type == STK_MATCH_CACHE_POINT) {\
1535 msa->match_cache_buf[stk->u.match_cache_point.index] |= stk->u.match_cache_point.mask;\
1536 MATCH_CACHE_DEBUG_MEMOIZE(stk);\
1537 }\
1538 else if (stk->type == STK_ATOMIC_MATCH_CACHE_POINT) {\
1539 memoize_extended_match_cache_point(msa->match_cache_buf, stk->u.match_cache_point.index, stk->u.match_cache_point.mask);\
1540 MATCH_CACHE_DEBUG_MEMOIZE(stkp);\
1541 }\
1542 } while(0)
1543# define MEMOIZE_LOOKAROUND_MATCH_CACHE_POINT(stkp) do {\
1544 if (stkp->type == STK_MATCH_CACHE_POINT) {\
1545 stkp->type = STK_VOID;\
1546 memoize_extended_match_cache_point(msa->match_cache_buf, stkp->u.match_cache_point.index, stkp->u.match_cache_point.mask);\
1547 MATCH_CACHE_DEBUG_MEMOIZE(stkp);\
1548 }\
1549 } while(0)
1550# define MEMOIZE_ATOMIC_MATCH_CACHE_POINT do {\
1551 if (stk->type == STK_MATCH_CACHE_POINT) {\
1552 memoize_extended_match_cache_point(msa->match_cache_buf, stk->u.match_cache_point.index, stk->u.match_cache_point.mask);\
1553 MATCH_CACHE_DEBUG_MEMOIZE(stkp);\
1554 }\
1555 } while(0)
1556#else
1557# define INC_NUM_FAILS ((void) 0)
1558# define MEMOIZE_MATCH_CACHE_POINT ((void) 0)
1559# define MEMOIZE_LOOKAROUND_MATCH_CACHE_POINT(stkp) ((void) 0)
1560#endif
1561
1562#define STACK_POP_ONE do {\
1563 stk--;\
1564 STACK_BASE_CHECK(stk, "STACK_POP_ONE"); \
1565} while(0)
1566
1567#define STACK_POP do {\
1568 switch (pop_level) {\
1569 case STACK_POP_LEVEL_FREE:\
1570 while (1) {\
1571 stk--;\
1572 STACK_BASE_CHECK(stk, "STACK_POP"); \
1573 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
1574 ELSE_IF_STATE_CHECK_MARK(stk);\
1575 MEMOIZE_MATCH_CACHE_POINT;\
1576 }\
1577 break;\
1578 case STACK_POP_LEVEL_MEM_START:\
1579 while (1) {\
1580 stk--;\
1581 STACK_BASE_CHECK(stk, "STACK_POP 2"); \
1582 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
1583 else if (stk->type == STK_MEM_START) {\
1584 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1585 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1586 }\
1587 ELSE_IF_STATE_CHECK_MARK(stk);\
1588 MEMOIZE_MATCH_CACHE_POINT;\
1589 }\
1590 break;\
1591 default:\
1592 while (1) {\
1593 stk--;\
1594 STACK_BASE_CHECK(stk, "STACK_POP 3"); \
1595 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
1596 else if (stk->type == STK_MEM_START) {\
1597 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1598 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1599 }\
1600 else if (stk->type == STK_REPEAT_INC) {\
1601 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
1602 }\
1603 else if (stk->type == STK_MEM_END) {\
1604 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1605 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1606 }\
1607 ELSE_IF_STATE_CHECK_MARK(stk);\
1608 MEMOIZE_MATCH_CACHE_POINT;\
1609 }\
1610 break;\
1611 }\
1612} while(0)
1613
1614#define STACK_POP_TIL_POS_NOT do {\
1615 while (1) {\
1616 stk--;\
1617 STACK_BASE_CHECK(stk, "STACK_POP_TIL_POS_NOT"); \
1618 if (stk->type == STK_POS_NOT) break;\
1619 else if (stk->type == STK_MEM_START) {\
1620 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1621 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1622 }\
1623 else if (stk->type == STK_REPEAT_INC) {\
1624 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
1625 }\
1626 else if (stk->type == STK_MEM_END) {\
1627 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1628 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1629 }\
1630 else if (IS_TO_VOID_TARGET(stk)) {\
1631 INC_NUM_FAILS;\
1632 }\
1633 ELSE_IF_STATE_CHECK_MARK(stk);\
1634 MEMOIZE_LOOKAROUND_MATCH_CACHE_POINT(stk);\
1635 }\
1636} while(0)
1637
1638#define STACK_POP_TIL_LOOK_BEHIND_NOT do {\
1639 while (1) {\
1640 stk--;\
1641 STACK_BASE_CHECK(stk, "STACK_POP_TIL_LOOK_BEHIND_NOT"); \
1642 if (stk->type == STK_LOOK_BEHIND_NOT) break;\
1643 else if (stk->type == STK_MEM_START) {\
1644 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1645 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1646 }\
1647 else if (stk->type == STK_REPEAT_INC) {\
1648 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
1649 }\
1650 else if (stk->type == STK_MEM_END) {\
1651 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1652 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1653 }\
1654 ELSE_IF_STATE_CHECK_MARK(stk);\
1655 }\
1656} while(0)
1657
1658#define STACK_POP_TIL_ABSENT do {\
1659 while (1) {\
1660 stk--;\
1661 STACK_BASE_CHECK(stk, "STACK_POP_TIL_ABSENT"); \
1662 if (stk->type == STK_ABSENT) break;\
1663 else if (stk->type == STK_MEM_START) {\
1664 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1665 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1666 }\
1667 else if (stk->type == STK_REPEAT_INC) {\
1668 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
1669 }\
1670 else if (stk->type == STK_MEM_END) {\
1671 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1672 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1673 }\
1674 ELSE_IF_STATE_CHECK_MARK(stk);\
1675 }\
1676} while(0)
1677
1678#define STACK_POP_ABSENT_POS(start, end) do {\
1679 stk--;\
1680 STACK_BASE_CHECK(stk, "STACK_POP_ABSENT_POS"); \
1681 (start) = stk->u.absent_pos.abs_pstr;\
1682 (end) = stk->u.absent_pos.end_pstr;\
1683} while(0)
1684
1685#define STACK_POS_END(k) do {\
1686 k = stk;\
1687 while (1) {\
1688 k--;\
1689 STACK_BASE_CHECK(k, "STACK_POS_END"); \
1690 if (IS_TO_VOID_TARGET(k)) {\
1691 INC_NUM_FAILS;\
1692 k->type = STK_VOID;\
1693 }\
1694 else if (k->type == STK_POS) {\
1695 k->type = STK_VOID;\
1696 break;\
1697 }\
1698 MEMOIZE_LOOKAROUND_MATCH_CACHE_POINT(k);\
1699 }\
1700} while(0)
1701
1702#define STACK_STOP_BT_END do {\
1703 OnigStackType *k = stk;\
1704 while (1) {\
1705 k--;\
1706 STACK_BASE_CHECK(k, "STACK_STOP_BT_END"); \
1707 if (IS_TO_VOID_TARGET(k)) {\
1708 INC_NUM_FAILS;\
1709 k->type = STK_VOID;\
1710 }\
1711 else if (k->type == STK_STOP_BT) {\
1712 k->type = STK_VOID;\
1713 break;\
1714 }\
1715 else if (k->type == STK_MATCH_CACHE_POINT) {\
1716 k->type = STK_ATOMIC_MATCH_CACHE_POINT;\
1717 }\
1718 }\
1719} while(0)
1720
1721#define STACK_STOP_BT_FAIL do {\
1722 while (1) {\
1723 stk--;\
1724 STACK_BASE_CHECK(stk, "STACK_STOP_BT_END"); \
1725 if (stk->type == STK_STOP_BT) {\
1726 stk->type = STK_VOID;\
1727 break;\
1728 }\
1729 MEMOIZE_ATOMIC_MATCH_CACHE_POINT;\
1730 }\
1731} while(0)
1732
1733#define STACK_NULL_CHECK(isnull,id,s) do {\
1734 OnigStackType* k = STACK_AT((stk-1)->null_check)+1;\
1735 while (1) {\
1736 k--;\
1737 STACK_BASE_CHECK(k, "STACK_NULL_CHECK"); \
1738 if (k->type == STK_NULL_CHECK_START) {\
1739 if (k->u.null_check.num == (id)) {\
1740 (isnull) = (k->u.null_check.pstr == (s));\
1741 break;\
1742 }\
1743 }\
1744 }\
1745} while(0)
1746
1747#define STACK_NULL_CHECK_REC(isnull,id,s) do {\
1748 int level = 0;\
1749 OnigStackType* k = STACK_AT((stk-1)->null_check)+1;\
1750 while (1) {\
1751 k--;\
1752 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_REC"); \
1753 if (k->type == STK_NULL_CHECK_START) {\
1754 if (k->u.null_check.num == (id)) {\
1755 if (level == 0) {\
1756 (isnull) = (k->u.null_check.pstr == (s));\
1757 break;\
1758 }\
1759 else level--;\
1760 }\
1761 }\
1762 else if (k->type == STK_NULL_CHECK_END) {\
1763 level++;\
1764 }\
1765 }\
1766} while(0)
1767
1768#define STACK_NULL_CHECK_MEMST(isnull,id,s,reg) do {\
1769 OnigStackType* k = STACK_AT((stk-1)->null_check)+1;\
1770 while (1) {\
1771 k--;\
1772 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST"); \
1773 if (k->type == STK_NULL_CHECK_START) {\
1774 if (k->u.null_check.num == (id)) {\
1775 if (k->u.null_check.pstr != (s)) {\
1776 (isnull) = 0;\
1777 break;\
1778 }\
1779 else {\
1780 UChar* endp;\
1781 (isnull) = 1;\
1782 while (k < stk) {\
1783 if (k->type == STK_MEM_START) {\
1784 if (k->u.mem.end == INVALID_STACK_INDEX) {\
1785 (isnull) = 0; break;\
1786 }\
1787 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
1788 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
1789 else\
1790 endp = (UChar* )k->u.mem.end;\
1791 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
1792 (isnull) = 0; break;\
1793 }\
1794 else if (endp != s) {\
1795 (isnull) = -1; /* empty, but position changed */ \
1796 }\
1797 }\
1798 k++;\
1799 }\
1800 break;\
1801 }\
1802 }\
1803 }\
1804 }\
1805} while(0)
1806
1807#define STACK_NULL_CHECK_MEMST_REC(isnull,id,s,reg) do {\
1808 int level = 0;\
1809 OnigStackType* k = STACK_AT((stk-1)->null_check)+1;\
1810 while (1) {\
1811 k--;\
1812 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST_REC"); \
1813 if (k->type == STK_NULL_CHECK_START) {\
1814 if (k->u.null_check.num == (id)) {\
1815 if (level == 0) {\
1816 if (k->u.null_check.pstr != (s)) {\
1817 (isnull) = 0;\
1818 break;\
1819 }\
1820 else {\
1821 UChar* endp;\
1822 (isnull) = 1;\
1823 while (k < stk) {\
1824 if (k->type == STK_MEM_START) {\
1825 if (k->u.mem.end == INVALID_STACK_INDEX) {\
1826 (isnull) = 0; break;\
1827 }\
1828 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
1829 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
1830 else\
1831 endp = (UChar* )k->u.mem.end;\
1832 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
1833 (isnull) = 0; break;\
1834 }\
1835 else if (endp != s) {\
1836 (isnull) = -1; /* empty, but position changed */ \
1837 }\
1838 }\
1839 k++;\
1840 }\
1841 break;\
1842 }\
1843 }\
1844 else {\
1845 level--;\
1846 }\
1847 }\
1848 }\
1849 else if (k->type == STK_NULL_CHECK_END) {\
1850 if (k->u.null_check.num == (id)) level++;\
1851 }\
1852 }\
1853} while(0)
1854
1855#define STACK_GET_REPEAT(id, k) do {\
1856 int level = 0;\
1857 k = stk;\
1858 while (1) {\
1859 k--;\
1860 STACK_BASE_CHECK(k, "STACK_GET_REPEAT"); \
1861 if (k->type == STK_REPEAT) {\
1862 if (level == 0) {\
1863 if (k->u.repeat.num == (id)) {\
1864 break;\
1865 }\
1866 }\
1867 }\
1868 else if (k->type == STK_CALL_FRAME) level--;\
1869 else if (k->type == STK_RETURN) level++;\
1870 }\
1871} while(0)
1872
1873#define STACK_RETURN(addr) do {\
1874 int level = 0;\
1875 OnigStackType* k = stk;\
1876 while (1) {\
1877 k--;\
1878 STACK_BASE_CHECK(k, "STACK_RETURN"); \
1879 if (k->type == STK_CALL_FRAME) {\
1880 if (level == 0) {\
1881 (addr) = k->u.call_frame.ret_addr;\
1882 break;\
1883 }\
1884 else level--;\
1885 }\
1886 else if (k->type == STK_RETURN)\
1887 level++;\
1888 }\
1889} while(0)
1890
1891
1892#define STRING_CMP(s1,s2,len) do {\
1893 while (len-- > 0) {\
1894 if (*s1++ != *s2++) goto fail;\
1895 }\
1896} while(0)
1897
1898#define STRING_CMP_IC(case_fold_flag,s1,ps2,len,text_end) do {\
1899 if (string_cmp_ic(encode, case_fold_flag, s1, ps2, len, text_end) == 0) \
1900 goto fail; \
1901} while(0)
1902
1903static int string_cmp_ic(OnigEncoding enc, int case_fold_flag,
1904 UChar* s1, UChar** ps2, OnigDistance mblen, const UChar* text_end)
1905{
1906 UChar buf1[ONIGENC_MBC_CASE_FOLD_MAXLEN];
1907 UChar buf2[ONIGENC_MBC_CASE_FOLD_MAXLEN];
1908 UChar *p1, *p2, *end1, *s2;
1909 int len1, len2;
1910
1911 s2 = *ps2;
1912 end1 = s1 + mblen;
1913 while (s1 < end1) {
1914 if (s2 >= text_end) return 0;
1915 len1 = ONIGENC_MBC_CASE_FOLD(enc, case_fold_flag, &s1, text_end, buf1);
1916 len2 = ONIGENC_MBC_CASE_FOLD(enc, case_fold_flag, &s2, text_end, buf2);
1917 if (len1 != len2) return 0;
1918 p1 = buf1;
1919 p2 = buf2;
1920 while (len1-- > 0) {
1921 if (*p1 != *p2) return 0;
1922 p1++;
1923 p2++;
1924 }
1925 }
1926
1927 *ps2 = s2;
1928 return 1;
1929}
1930
1931#define STRING_CMP_VALUE(s1,s2,len,is_fail) do {\
1932 is_fail = 0;\
1933 while (len-- > 0) {\
1934 if (*s1++ != *s2++) {\
1935 is_fail = 1; break;\
1936 }\
1937 }\
1938} while(0)
1939
1940#define STRING_CMP_VALUE_IC(case_fold_flag,s1,ps2,len,text_end,is_fail) do {\
1941 if (string_cmp_ic(encode, case_fold_flag, s1, ps2, len, text_end) == 0) \
1942 is_fail = 1; \
1943 else \
1944 is_fail = 0; \
1945} while(0)
1946
1947
1948#define IS_EMPTY_STR (str == end)
1949#define ON_STR_BEGIN(s) ((s) == str)
1950#define ON_STR_END(s) ((s) == end)
1951#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
1952# define DATA_ENSURE_CHECK1 (s < right_range)
1953# define DATA_ENSURE_CHECK(n) (s + (n) <= right_range)
1954# define DATA_ENSURE(n) if (s + (n) > right_range) goto fail
1955# define DATA_ENSURE_CONTINUE(n) if (s + (n) > right_range) continue
1956# define ABSENT_END_POS right_range
1957#else
1958# define DATA_ENSURE_CHECK1 (s < end)
1959# define DATA_ENSURE_CHECK(n) (s + (n) <= end)
1960# define DATA_ENSURE(n) if (s + (n) > end) goto fail
1961# define DATA_ENSURE_CONTINUE(n) if (s + (n) > end) continue
1962# define ABSENT_END_POS end
1963#endif /* USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE */
1964
1965int onigenc_mbclen_approximate(const OnigUChar* p,const OnigUChar* e, const struct OnigEncodingTypeST* enc);
1966
1967static inline int
1968enclen_approx(OnigEncoding enc, const OnigUChar* p, const OnigUChar* e)
1969{
1970 if (enc->max_enc_len == enc->min_enc_len) {
1971 return (p < e ? enc->min_enc_len : 0);
1972 }
1973 else {
1974 return onigenc_mbclen_approximate(p, e, enc);
1975 }
1976}
1977
1978
1979#ifdef USE_CAPTURE_HISTORY
1980static int
1981make_capture_history_tree(OnigCaptureTreeNode* node, OnigStackType** kp,
1982 OnigStackType* stk_top, UChar* str, regex_t* reg)
1983{
1984 int n, r;
1985 OnigCaptureTreeNode* child;
1986 OnigStackType* k = *kp;
1987
1988 while (k < stk_top) {
1989 if (k->type == STK_MEM_START) {
1990 n = k->u.mem.num;
1991 if (n <= ONIG_MAX_CAPTURE_HISTORY_GROUP &&
1992 BIT_STATUS_AT(reg->capture_history, n) != 0) {
1993 child = history_node_new();
1994 CHECK_NULL_RETURN_MEMERR(child);
1995 child->group = n;
1996 child->beg = k->u.mem.pstr - str;
1997 r = history_tree_add_child(node, child);
1998 if (r != 0) {
1999 history_tree_free(child);
2000 return r;
2001 }
2002 *kp = (k + 1);
2003 r = make_capture_history_tree(child, kp, stk_top, str, reg);
2004 if (r != 0) return r;
2005
2006 k = *kp;
2007 child->end = k->u.mem.pstr - str;
2008 }
2009 }
2010 else if (k->type == STK_MEM_END) {
2011 if (k->u.mem.num == node->group) {
2012 node->end = k->u.mem.pstr - str;
2013 *kp = k;
2014 return 0;
2015 }
2016 }
2017 k++;
2018 }
2019
2020 return 1; /* 1: root node ending. */
2021}
2022#endif /* USE_CAPTURE_HISTORY */
2023
2024#ifdef USE_BACKREF_WITH_LEVEL
2025static int
2026mem_is_in_memp(int mem, int num, UChar* memp)
2027{
2028 int i;
2029 MemNumType m;
2030
2031 for (i = 0; i < num; i++) {
2032 GET_MEMNUM_INC(m, memp);
2033 if (mem == (int )m) return 1;
2034 }
2035 return 0;
2036}
2037
2038static int backref_match_at_nested_level(regex_t* reg,
2039 OnigStackType* top, OnigStackType* stk_base,
2040 int ignore_case, int case_fold_flag,
2041 int nest, int mem_num, UChar* memp, UChar** s, const UChar* send)
2042{
2043 UChar *ss, *p, *pstart, *pend = NULL_UCHARP;
2044 int level;
2045 OnigStackType* k;
2046
2047 level = 0;
2048 k = top;
2049 k--;
2050 while (k >= stk_base) {
2051 if (k->type == STK_CALL_FRAME) {
2052 level--;
2053 }
2054 else if (k->type == STK_RETURN) {
2055 level++;
2056 }
2057 else if (level == nest) {
2058 if (k->type == STK_MEM_START) {
2059 if (mem_is_in_memp(k->u.mem.num, mem_num, memp)) {
2060 pstart = k->u.mem.pstr;
2061 if (pend != NULL_UCHARP) {
2062 if (pend - pstart > send - *s) return 0; /* or goto next_mem; */
2063 p = pstart;
2064 ss = *s;
2065
2066 if (ignore_case != 0) {
2067 if (string_cmp_ic(reg->enc, case_fold_flag,
2068 pstart, &ss, pend - pstart, send) == 0)
2069 return 0; /* or goto next_mem; */
2070 }
2071 else {
2072 while (p < pend) {
2073 if (*p++ != *ss++) return 0; /* or goto next_mem; */
2074 }
2075 }
2076
2077 *s = ss;
2078 return 1;
2079 }
2080 }
2081 }
2082 else if (k->type == STK_MEM_END) {
2083 if (mem_is_in_memp(k->u.mem.num, mem_num, memp)) {
2084 pend = k->u.mem.pstr;
2085 }
2086 }
2087 }
2088 k--;
2089 }
2090
2091 return 0;
2092}
2093#endif /* USE_BACKREF_WITH_LEVEL */
2094
2095
2096#ifdef ONIG_DEBUG_STATISTICS
2097
2098# ifdef _WIN32
2099# include <windows.h>
2100static LARGE_INTEGER ts, te, freq;
2101# define GETTIME(t) QueryPerformanceCounter(&(t))
2102# define TIMEDIFF(te,ts) (unsigned long )(((te).QuadPart - (ts).QuadPart) \
2103 * 1000000 / freq.QuadPart)
2104# else /* _WIN32 */
2105
2106# define USE_TIMEOFDAY
2107
2108# ifdef USE_TIMEOFDAY
2109# ifdef HAVE_SYS_TIME_H
2110# include <sys/time.h>
2111# endif
2112# ifdef HAVE_UNISTD_H
2113# include <unistd.h>
2114# endif
2115static struct timeval ts, te;
2116# define GETTIME(t) gettimeofday(&(t), (struct timezone* )0)
2117# define TIMEDIFF(te,ts) (((te).tv_usec - (ts).tv_usec) + \
2118 (((te).tv_sec - (ts).tv_sec)*1000000))
2119# else /* USE_TIMEOFDAY */
2120# ifdef HAVE_SYS_TIMES_H
2121# include <sys/times.h>
2122# endif
2123static struct tms ts, te;
2124# define GETTIME(t) times(&(t))
2125# define TIMEDIFF(te,ts) ((te).tms_utime - (ts).tms_utime)
2126# endif /* USE_TIMEOFDAY */
2127
2128# endif /* _WIN32 */
2129
2130static int OpCounter[256];
2131static int OpPrevCounter[256];
2132static unsigned long OpTime[256];
2133static int OpCurr = OP_FINISH;
2134static int OpPrevTarget = OP_FAIL;
2135static int MaxStackDepth = 0;
2136
2137# define MOP_IN(opcode) do {\
2138 if (opcode == OpPrevTarget) OpPrevCounter[OpCurr]++;\
2139 OpCurr = opcode;\
2140 OpCounter[opcode]++;\
2141 GETTIME(ts);\
2142} while(0)
2143
2144# define MOP_OUT do {\
2145 GETTIME(te);\
2146 OpTime[OpCurr] += TIMEDIFF(te, ts);\
2147} while(0)
2148
2149extern void
2150onig_statistics_init(void)
2151{
2152 int i;
2153 for (i = 0; i < 256; i++) {
2154 OpCounter[i] = OpPrevCounter[i] = 0; OpTime[i] = 0;
2155 }
2156 MaxStackDepth = 0;
2157# ifdef _WIN32
2158 QueryPerformanceFrequency(&freq);
2159# endif
2160}
2161
2162extern void
2163onig_print_statistics(FILE* f)
2164{
2165 int i;
2166 fprintf(f, " count prev time\n");
2167 for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
2168 fprintf(f, "%8d: %8d: %10lu: %s\n",
2169 OpCounter[i], OpPrevCounter[i], OpTime[i], OnigOpInfo[i].name);
2170 }
2171 fprintf(f, "\nmax stack depth: %d\n", MaxStackDepth);
2172}
2173
2174# define STACK_INC do {\
2175 stk++;\
2176 if (stk - stk_base > MaxStackDepth) \
2177 MaxStackDepth = stk - stk_base;\
2178} while(0)
2179
2180#else /* ONIG_DEBUG_STATISTICS */
2181# define STACK_INC stk++
2182
2183# define MOP_IN(opcode)
2184# define MOP_OUT
2185#endif /* ONIG_DEBUG_STATISTICS */
2186
2187
2188#ifdef ONIG_DEBUG_MATCH
2189static const char *
2190stack_type_str(int stack_type)
2191{
2192 switch (stack_type) {
2193 case STK_ALT: return "Alt ";
2194 case STK_LOOK_BEHIND_NOT: return "LBNot ";
2195 case STK_POS_NOT: return "PosNot";
2196 case STK_MEM_START: return "MemS ";
2197 case STK_MEM_END: return "MemE ";
2198 case STK_REPEAT_INC: return "RepInc";
2199 case STK_STATE_CHECK_MARK: return "StChMk";
2200 case STK_NULL_CHECK_START: return "NulChS";
2201 case STK_NULL_CHECK_END: return "NulChE";
2202 case STK_MEM_END_MARK: return "MemEMk";
2203 case STK_POS: return "Pos ";
2204 case STK_STOP_BT: return "StopBt";
2205 case STK_REPEAT: return "Rep ";
2206 case STK_CALL_FRAME: return "Call ";
2207 case STK_RETURN: return "Ret ";
2208 case STK_VOID: return "Void ";
2209 case STK_ABSENT_POS: return "AbsPos";
2210 case STK_ABSENT: return "Absent";
2211 case STK_MATCH_CACHE_POINT: return "MCache";
2212 default: return " ";
2213 }
2214}
2215#endif
2216#ifdef USE_MATCH_CACHE
2217
2218static long
2219bsearch_cache_opcodes(const OnigCacheOpcode *cache_opcodes, long num_cache_opcodes, const UChar* p)
2220{
2221 long l = 0, r = num_cache_opcodes - 1, m = 0;
2222
2223 while (l <= r) {
2224 m = (l + r) / 2;
2225 if (cache_opcodes[m].addr == p) break;
2226 if (cache_opcodes[m].addr < p) l = m + 1;
2227 else r = m - 1;
2228 }
2229 return m;
2230}
2231
2232static long
2233find_cache_point(regex_t* reg, const OnigCacheOpcode* cache_opcodes, long num_cache_opcodes, const UChar* p, const OnigStackType *stk, const OnigStackIndex *repeat_stk, const OnigCacheOpcode **cache_opcode_ptr)
2234{
2235 long m;
2236 const OnigCacheOpcode* cache_opcode;
2237 const OnigRepeatRange* range;
2238 const OnigStackType *stkp;
2239 int count = 0;
2240 int is_inc = *p == OP_REPEAT_INC || *p == OP_REPEAT_INC_NG;
2241 long cache_point;
2242 long num_cache_points_at_outer_repeat;
2243 long num_cache_points_in_outer_repeat;
2244
2245 m = bsearch_cache_opcodes(cache_opcodes, num_cache_opcodes, p);
2246
2247 if (!(0 <= m && m < num_cache_opcodes && cache_opcodes[m].addr == p)) {
2248 return -1;
2249 }
2250
2251 cache_opcode = &cache_opcodes[m];
2252 *cache_opcode_ptr = &cache_opcodes[m];
2253 cache_point = cache_opcode->cache_point;
2254 if (cache_opcode->outer_repeat_mem == -1) {
2255 return cache_point;
2256 }
2257
2258 num_cache_points_at_outer_repeat = cache_opcode->num_cache_points_at_outer_repeat;
2259 num_cache_points_in_outer_repeat = cache_opcode->num_cache_points_in_outer_repeat;
2260
2261 range = &reg->repeat_range[cache_opcode->outer_repeat_mem];
2262
2263 stkp = &stk[repeat_stk[cache_opcode->outer_repeat_mem]];
2264 count = is_inc ? stkp->u.repeat.count - 1 : stkp->u.repeat.count;
2265
2266 if (count < range->lower) {
2267 return num_cache_points_at_outer_repeat +
2268 num_cache_points_in_outer_repeat * count +
2269 cache_point;
2270 }
2271
2272 if (range->upper == 0x7fffffff) {
2273 return num_cache_points_at_outer_repeat +
2274 num_cache_points_in_outer_repeat * (range->lower - (is_inc ? 1 : 0)) + (is_inc ? 0 : 1) +
2275 cache_point;
2276 }
2277
2278 return num_cache_points_at_outer_repeat +
2279 num_cache_points_in_outer_repeat * (range->lower - 1) +
2280 (num_cache_points_in_outer_repeat + 1) * (count - range->lower + 1) +
2281 cache_point;
2282}
2283
2284static int
2285check_extended_match_cache_point(uint8_t *match_cache_buf, OnigPosition match_cache_point_index, uint8_t match_cache_point_mask)
2286{
2287 if (match_cache_point_mask & 0x80) {
2288 return (match_cache_buf[match_cache_point_index + 1] & 0x01) > 0;
2289 }
2290 else {
2291 return (match_cache_buf[match_cache_point_index] & (match_cache_point_mask << 1)) > 0;
2292 }
2293}
2294
2295static void
2296memoize_extended_match_cache_point(uint8_t *match_cache_buf, OnigPosition match_cache_point_index, uint8_t match_cache_point_mask)
2297{
2298 match_cache_buf[match_cache_point_index] |= match_cache_point_mask;
2299 if (match_cache_point_mask & 0x80) {
2300 match_cache_buf[match_cache_point_index + 1] |= 0x01;
2301 }
2302 else {
2303 match_cache_buf[match_cache_point_index] |= match_cache_point_mask << 1;
2304 }
2305}
2306
2307#endif /* USE_MATCH_CACHE */
2308
2309/* match data(str - end) from position (sstart). */
2310/* if sstart == str then set sprev to NULL. */
2311static OnigPosition
2312match_at(regex_t* reg, const UChar* str, const UChar* end,
2313#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
2314 const UChar* right_range,
2315#endif
2316 const UChar* sstart, UChar* sprev, OnigMatchArg* msa)
2317{
2318 static const UChar FinishCode[] = { OP_FINISH };
2319
2320 int i, num_mem, pop_level;
2321 ptrdiff_t n, best_len;
2322 LengthType tlen, tlen2;
2323 MemNumType mem;
2324 RelAddrType addr;
2325 OnigOptionType option = reg->options;
2326 OnigEncoding encode = reg->enc;
2327 OnigCaseFoldType case_fold_flag = reg->case_fold_flag;
2328 UChar *s, *q, *sbegin;
2329 UChar *p = reg->p;
2330 UChar *pbegin = p;
2331 UChar *pkeep;
2332 char *alloca_base;
2333 char *xmalloc_base = NULL;
2334 OnigStackType *stk_alloc, *stk_base = NULL, *stk, *stk_end;
2335 OnigStackType *stkp; /* used as any purpose. */
2336 OnigStackIndex si;
2337 OnigStackIndex *repeat_stk;
2338 OnigStackIndex *mem_start_stk, *mem_end_stk;
2339#ifdef USE_COMBINATION_EXPLOSION_CHECK
2340 int scv;
2341 unsigned char* state_check_buff = msa->state_check_buff;
2342 int num_comb_exp_check = reg->num_comb_exp_check;
2343#endif
2344
2345#if USE_TOKEN_THREADED_VM
2346# define OP_OFFSET 1
2347# define VM_LOOP JUMP;
2348# define VM_LOOP_END
2349# define CASE(x) L_##x: sbegin = s; OPCODE_EXEC_HOOK;
2350# define DEFAULT L_DEFAULT:
2351# define NEXT sprev = sbegin; JUMP
2352# define JUMP pbegin = p; RB_GNUC_EXTENSION_BLOCK(goto *oplabels[*p++])
2353
2354 RB_GNUC_EXTENSION static const void *oplabels[] = {
2355 &&L_OP_FINISH, /* matching process terminator (no more alternative) */
2356 &&L_OP_END, /* pattern code terminator (success end) */
2357
2358 &&L_OP_EXACT1, /* single byte, N = 1 */
2359 &&L_OP_EXACT2, /* single byte, N = 2 */
2360 &&L_OP_EXACT3, /* single byte, N = 3 */
2361 &&L_OP_EXACT4, /* single byte, N = 4 */
2362 &&L_OP_EXACT5, /* single byte, N = 5 */
2363 &&L_OP_EXACTN, /* single byte */
2364 &&L_OP_EXACTMB2N1, /* mb-length = 2 N = 1 */
2365 &&L_OP_EXACTMB2N2, /* mb-length = 2 N = 2 */
2366 &&L_OP_EXACTMB2N3, /* mb-length = 2 N = 3 */
2367 &&L_OP_EXACTMB2N, /* mb-length = 2 */
2368 &&L_OP_EXACTMB3N, /* mb-length = 3 */
2369 &&L_OP_EXACTMBN, /* other length */
2370
2371 &&L_OP_EXACT1_IC, /* single byte, N = 1, ignore case */
2372 &&L_OP_EXACTN_IC, /* single byte, ignore case */
2373
2374 &&L_OP_CCLASS,
2375 &&L_OP_CCLASS_MB,
2376 &&L_OP_CCLASS_MIX,
2377 &&L_OP_CCLASS_NOT,
2378 &&L_OP_CCLASS_MB_NOT,
2379 &&L_OP_CCLASS_MIX_NOT,
2380
2381 &&L_OP_ANYCHAR, /* "." */
2382 &&L_OP_ANYCHAR_ML, /* "." multi-line */
2383 &&L_OP_ANYCHAR_STAR, /* ".*" */
2384 &&L_OP_ANYCHAR_ML_STAR, /* ".*" multi-line */
2385 &&L_OP_ANYCHAR_STAR_PEEK_NEXT,
2386 &&L_OP_ANYCHAR_ML_STAR_PEEK_NEXT,
2387
2388 &&L_OP_WORD,
2389 &&L_OP_NOT_WORD,
2390 &&L_OP_WORD_BOUND,
2391 &&L_OP_NOT_WORD_BOUND,
2392# ifdef USE_WORD_BEGIN_END
2393 &&L_OP_WORD_BEGIN,
2394 &&L_OP_WORD_END,
2395# else
2396 &&L_DEFAULT,
2397 &&L_DEFAULT,
2398# endif
2399 &&L_OP_ASCII_WORD,
2400 &&L_OP_NOT_ASCII_WORD,
2401 &&L_OP_ASCII_WORD_BOUND,
2402 &&L_OP_NOT_ASCII_WORD_BOUND,
2403# ifdef USE_WORD_BEGIN_END
2404 &&L_OP_ASCII_WORD_BEGIN,
2405 &&L_OP_ASCII_WORD_END,
2406# else
2407 &&L_DEFAULT,
2408 &&L_DEFAULT,
2409# endif
2410
2411 &&L_OP_BEGIN_BUF,
2412 &&L_OP_END_BUF,
2413 &&L_OP_BEGIN_LINE,
2414 &&L_OP_END_LINE,
2415 &&L_OP_SEMI_END_BUF,
2416 &&L_OP_BEGIN_POSITION,
2417
2418 &&L_OP_BACKREF1,
2419 &&L_OP_BACKREF2,
2420 &&L_OP_BACKREFN,
2421 &&L_OP_BACKREFN_IC,
2422 &&L_OP_BACKREF_MULTI,
2423 &&L_OP_BACKREF_MULTI_IC,
2424# ifdef USE_BACKREF_WITH_LEVEL
2425 &&L_OP_BACKREF_WITH_LEVEL, /* \k<xxx+n>, \k<xxx-n> */
2426# else
2427 &&L_DEFAULT,
2428# endif
2429 &&L_OP_MEMORY_START,
2430 &&L_OP_MEMORY_START_PUSH, /* push back-tracker to stack */
2431 &&L_OP_MEMORY_END_PUSH, /* push back-tracker to stack */
2432# ifdef USE_SUBEXP_CALL
2433 &&L_OP_MEMORY_END_PUSH_REC, /* push back-tracker to stack */
2434# else
2435 &&L_DEFAULT,
2436# endif
2437 &&L_OP_MEMORY_END,
2438# ifdef USE_SUBEXP_CALL
2439 &&L_OP_MEMORY_END_REC, /* push marker to stack */
2440# else
2441 &&L_DEFAULT,
2442# endif
2443
2444 &&L_OP_KEEP,
2445
2446 &&L_OP_FAIL, /* pop stack and move */
2447 &&L_OP_JUMP,
2448 &&L_OP_PUSH,
2449 &&L_OP_POP,
2450# ifdef USE_OP_PUSH_OR_JUMP_EXACT
2451 &&L_OP_PUSH_OR_JUMP_EXACT1, /* if match exact then push, else jump. */
2452# else
2453 &&L_DEFAULT,
2454# endif
2455 &&L_OP_PUSH_IF_PEEK_NEXT, /* if match exact then push, else none. */
2456 &&L_OP_REPEAT, /* {n,m} */
2457 &&L_OP_REPEAT_NG, /* {n,m}? (non greedy) */
2458 &&L_OP_REPEAT_INC,
2459 &&L_OP_REPEAT_INC_NG, /* non greedy */
2460 &&L_OP_REPEAT_INC_SG, /* search and get in stack */
2461 &&L_OP_REPEAT_INC_NG_SG, /* search and get in stack (non greedy) */
2462 &&L_OP_NULL_CHECK_START, /* null loop checker start */
2463 &&L_OP_NULL_CHECK_END, /* null loop checker end */
2464# ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
2465 &&L_OP_NULL_CHECK_END_MEMST, /* null loop checker end (with capture status) */
2466# else
2467 &&L_DEFAULT,
2468# endif
2469# ifdef USE_SUBEXP_CALL
2470 &&L_OP_NULL_CHECK_END_MEMST_PUSH, /* with capture status and push check-end */
2471# else
2472 &&L_DEFAULT,
2473# endif
2474
2475 &&L_OP_PUSH_POS, /* (?=...) start */
2476 &&L_OP_POP_POS, /* (?=...) end */
2477 &&L_OP_PUSH_POS_NOT, /* (?!...) start */
2478 &&L_OP_FAIL_POS, /* (?!...) end */
2479 &&L_OP_PUSH_STOP_BT, /* (?>...) start */
2480 &&L_OP_POP_STOP_BT, /* (?>...) end */
2481 &&L_OP_LOOK_BEHIND, /* (?<=...) start (no needs end opcode) */
2482 &&L_OP_PUSH_LOOK_BEHIND_NOT, /* (?<!...) start */
2483 &&L_OP_FAIL_LOOK_BEHIND_NOT, /* (?<!...) end */
2484 &&L_OP_PUSH_ABSENT_POS, /* (?~...) start */
2485 &&L_OP_ABSENT, /* (?~...) start of inner loop */
2486 &&L_OP_ABSENT_END, /* (?~...) end */
2487
2488# ifdef USE_SUBEXP_CALL
2489 &&L_OP_CALL, /* \g<name> */
2490 &&L_OP_RETURN,
2491# else
2492 &&L_DEFAULT,
2493 &&L_DEFAULT,
2494# endif
2495 &&L_OP_CONDITION,
2496
2497# ifdef USE_COMBINATION_EXPLOSION_CHECK
2498 &&L_OP_STATE_CHECK_PUSH, /* combination explosion check and push */
2499 &&L_OP_STATE_CHECK_PUSH_OR_JUMP, /* check ok -> push, else jump */
2500 &&L_OP_STATE_CHECK, /* check only */
2501# else
2502 &&L_DEFAULT,
2503 &&L_DEFAULT,
2504 &&L_DEFAULT,
2505# endif
2506# ifdef USE_COMBINATION_EXPLOSION_CHECK
2507 &&L_OP_STATE_CHECK_ANYCHAR_STAR,
2508 &&L_OP_STATE_CHECK_ANYCHAR_ML_STAR,
2509# else
2510 &&L_DEFAULT,
2511 &&L_DEFAULT,
2512# endif
2513 /* no need: IS_DYNAMIC_OPTION() == 0 */
2514# if 0 /* no need: IS_DYNAMIC_OPTION() == 0 */
2515 &&L_OP_SET_OPTION_PUSH, /* set option and push recover option */
2516 &&L_OP_SET_OPTION /* set option */
2517# else
2518 &&L_DEFAULT,
2519 &&L_DEFAULT
2520# endif
2521 };
2522#else /* USE_TOKEN_THREADED_VM */
2523
2524# define OP_OFFSET 0
2525# define VM_LOOP \
2526 while (1) { \
2527 OPCODE_EXEC_HOOK; \
2528 pbegin = p; \
2529 sbegin = s; \
2530 switch (*p++) {
2531# define VM_LOOP_END } sprev = sbegin; }
2532# define CASE(x) case x:
2533# define DEFAULT default:
2534# define NEXT break
2535# define JUMP continue; break
2536#endif /* USE_TOKEN_THREADED_VM */
2537
2538
2539#ifdef USE_SUBEXP_CALL
2540/* Stack #0 is used to store the pattern itself and used for (?R), \g<0>,
2541 etc. Additional space is required. */
2542# define ADD_NUMMEM 1
2543#else
2544/* Stack #0 not is used. */
2545# define ADD_NUMMEM 0
2546#endif
2547
2548 n = reg->num_repeat + (reg->num_mem + ADD_NUMMEM) * 2;
2549
2550 STACK_INIT(alloca_base, xmalloc_base, n, INIT_MATCH_STACK_SIZE);
2551 pop_level = reg->stack_pop_level;
2552 num_mem = reg->num_mem;
2553 repeat_stk = (OnigStackIndex* )alloca_base;
2554
2555 mem_start_stk = (OnigStackIndex* )(repeat_stk + reg->num_repeat);
2556 mem_end_stk = mem_start_stk + (num_mem + ADD_NUMMEM);
2557 {
2558 OnigStackIndex *pp = mem_start_stk;
2559 for (; pp < repeat_stk + n; pp += 2) {
2560 pp[0] = INVALID_STACK_INDEX;
2561 pp[1] = INVALID_STACK_INDEX;
2562 }
2563 }
2564#ifndef USE_SUBEXP_CALL
2565 mem_start_stk--; /* for index start from 1,
2566 mem_start_stk[1]..mem_start_stk[num_mem] */
2567 mem_end_stk--; /* for index start from 1,
2568 mem_end_stk[1]..mem_end_stk[num_mem] */
2569#endif
2570
2571#ifdef ONIG_DEBUG_MATCH
2572 fprintf(stderr, "match_at: str: %"PRIuPTR" (%p), end: %"PRIuPTR" (%p), start: %"PRIuPTR" (%p), sprev: %"PRIuPTR" (%p)\n",
2573 (uintptr_t )str, str, (uintptr_t )end, end, (uintptr_t )sstart, sstart, (uintptr_t )sprev, sprev);
2574 fprintf(stderr, "size: %d, start offset: %d\n",
2575 (int )(end - str), (int )(sstart - str));
2576 fprintf(stderr, "\n ofs> str stk:type addr:opcode\n");
2577#endif
2578
2579 STACK_PUSH_ENSURED(STK_ALT, (UChar* )FinishCode); /* bottom stack */
2580 best_len = ONIG_MISMATCH;
2581 s = (UChar* )sstart;
2582 pkeep = (UChar* )sstart;
2583
2584
2585#ifdef ONIG_DEBUG_MATCH
2586# define OPCODE_EXEC_HOOK \
2587 if (s) { \
2588 UChar *op, *q, *bp, buf[50]; \
2589 int len; \
2590 op = p - OP_OFFSET; \
2591 fprintf(stderr, "%4"PRIdPTR"> \"", (*op == OP_FINISH) ? (ptrdiff_t )-1 : s - str); \
2592 bp = buf; \
2593 q = s; \
2594 if (*op != OP_FINISH) { /* s may not be a valid pointer if OP_FINISH. */ \
2595 for (i = 0; i < 7 && q < end; i++) { \
2596 len = enclen(encode, q, end); \
2597 while (len-- > 0) *bp++ = *q++; \
2598 } \
2599 if (q < end) { xmemcpy(bp, "...", 3); bp += 3; } \
2600 } \
2601 xmemcpy(bp, "\"", 1); bp += 1; \
2602 *bp = 0; \
2603 fputs((char* )buf, stderr); \
2604 for (i = 0; i < 20 - (bp - buf); i++) fputc(' ', stderr); \
2605 fprintf(stderr, "%4"PRIdPTR":%s %4"PRIdPTR":", \
2606 stk - stk_base - 1, \
2607 (stk > stk_base) ? stack_type_str(stk[-1].type) : " ", \
2608 (op == FinishCode) ? (ptrdiff_t )-1 : op - reg->p); \
2609 onig_print_compiled_byte_code(stderr, op, reg->p+reg->used, NULL, encode); \
2610 fprintf(stderr, "\n"); \
2611 }
2612#else
2613# define OPCODE_EXEC_HOOK ((void) 0)
2614#endif
2615
2616#ifdef USE_MATCH_CACHE
2617#ifdef ONIG_DEBUG_MATCH_CACHE
2618#define MATCH_CACHE_DEBUG fprintf(stderr, "MATCH CACHE: cache %td (p=%p index=%td mask=%d)\n", match_cache_point, pbegin, match_cache_point_index, match_cache_point_mask)
2619#define MATCH_CACHE_DEBUG_HIT fprintf(stderr, "MATCH CACHE: cache hit\n")
2620#else
2621#define MATCH_CACHE_DEBUG ((void) 0)
2622#define MATCH_CACHE_DEBUG_HIT ((void) 0)
2623#endif
2624
2625#define MATCH_CACHE_HIT ((void) 0)
2626
2627# define CHECK_MATCH_CACHE do {\
2628 if (msa->match_cache_status == MATCH_CACHE_STATUS_ENABLED) {\
2629 const OnigCacheOpcode *cache_opcode;\
2630 long cache_point = find_cache_point(reg, msa->cache_opcodes, msa->num_cache_opcodes, pbegin, stk_base, repeat_stk, &cache_opcode);\
2631 if (cache_point >= 0) {\
2632 OnigPosition match_cache_point = msa->num_cache_points * (OnigPosition)(s - str) + cache_point;\
2633 OnigPosition match_cache_point_index = match_cache_point >> 3;\
2634 uint8_t match_cache_point_mask = 1 << (match_cache_point & 7);\
2635 MATCH_CACHE_DEBUG;\
2636 if (msa->match_cache_buf[match_cache_point_index] & match_cache_point_mask) {\
2637 MATCH_CACHE_DEBUG_HIT; MATCH_CACHE_HIT;\
2638 if (cache_opcode->lookaround_nesting == 0) goto fail;\
2639 else if (cache_opcode->lookaround_nesting < 0) {\
2640 if (check_extended_match_cache_point(msa->match_cache_buf, match_cache_point_index, match_cache_point_mask)) {\
2641 STACK_STOP_BT_FAIL;\
2642 goto fail;\
2643 }\
2644 else goto fail;\
2645 }\
2646 else {\
2647 if (check_extended_match_cache_point(msa->match_cache_buf, match_cache_point_index, match_cache_point_mask)) {\
2648 p = cache_opcode->match_addr;\
2649 MOP_OUT;\
2650 JUMP;\
2651 }\
2652 else goto fail;\
2653 }\
2654 }\
2655 STACK_PUSH_MATCH_CACHE_POINT(match_cache_point_index, match_cache_point_mask);\
2656 }\
2657 }\
2658} while (0)
2659#else
2660# define CHECK_MATCH_CACHE ((void) 0)
2661#endif
2662
2663 VM_LOOP {
2664 CASE(OP_END) MOP_IN(OP_END);
2665 n = s - sstart;
2666 if (n > best_len) {
2667 OnigRegion* region;
2668#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
2669 if (IS_FIND_LONGEST(option)) {
2670 if (n > msa->best_len) {
2671 msa->best_len = n;
2672 msa->best_s = (UChar* )sstart;
2673 }
2674 else
2675 goto end_best_len;
2676 }
2677#endif
2678 best_len = n;
2679 region = msa->region;
2680 if (region) {
2681 region->beg[0] = ((pkeep > s) ? s : pkeep) - str;
2682 region->end[0] = s - str;
2683 for (i = 1; i <= num_mem; i++) {
2684 if (mem_end_stk[i] != INVALID_STACK_INDEX) {
2685 if (BIT_STATUS_AT(reg->bt_mem_start, i))
2686 region->beg[i] = STACK_AT(mem_start_stk[i])->u.mem.pstr - str;
2687 else
2688 region->beg[i] = (UChar* )((void* )mem_start_stk[i]) - str;
2689
2690 region->end[i] = (BIT_STATUS_AT(reg->bt_mem_end, i)
2691 ? STACK_AT(mem_end_stk[i])->u.mem.pstr
2692 : (UChar* )((void* )mem_end_stk[i])) - str;
2693 }
2694 else {
2695 region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;
2696 }
2697 }
2698
2699#ifdef USE_CAPTURE_HISTORY
2700 if (reg->capture_history != 0) {
2701 int r;
2702 OnigCaptureTreeNode* node;
2703
2704 if (IS_NULL(region->history_root)) {
2705 region->history_root = node = history_node_new();
2706 CHECK_NULL_RETURN_MEMERR(node);
2707 }
2708 else {
2709 node = region->history_root;
2710 history_tree_clear(node);
2711 }
2712
2713 node->group = 0;
2714 node->beg = ((pkeep > s) ? s : pkeep) - str;
2715 node->end = s - str;
2716
2717 stkp = stk_base;
2718 r = make_capture_history_tree(region->history_root, &stkp,
2719 stk, (UChar* )str, reg);
2720 if (r < 0) {
2721 best_len = r; /* error code */
2722 goto finish;
2723 }
2724 }
2725#endif /* USE_CAPTURE_HISTORY */
2726 } /* if (region) */
2727 } /* n > best_len */
2728
2729#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
2730 end_best_len:
2731#endif
2732 MOP_OUT;
2733
2734 if (IS_FIND_CONDITION(option)) {
2735 if (IS_FIND_NOT_EMPTY(option) && s == sstart) {
2736 best_len = ONIG_MISMATCH;
2737 goto fail; /* for retry */
2738 }
2739 if (IS_FIND_LONGEST(option) && DATA_ENSURE_CHECK1) {
2740 goto fail; /* for retry */
2741 }
2742 }
2743
2744 /* default behavior: return first-matching result. */
2745 goto finish;
2746
2747 CASE(OP_EXACT1) MOP_IN(OP_EXACT1);
2748 DATA_ENSURE(1);
2749 if (*p != *s) goto fail;
2750 p++; s++;
2751 MOP_OUT;
2752 NEXT;
2753
2754 CASE(OP_EXACT1_IC) MOP_IN(OP_EXACT1_IC);
2755 {
2756 int len;
2757 UChar *q, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
2758
2759 DATA_ENSURE(1);
2760 len = ONIGENC_MBC_CASE_FOLD(encode,
2761 /* DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag), */
2762 case_fold_flag,
2763 &s, end, lowbuf);
2764 DATA_ENSURE(0);
2765 if (len != enclen(encode, p, reg->p + reg->used)) goto fail;
2766 q = lowbuf;
2767 while (len-- > 0) {
2768 if (*p != *q) {
2769 goto fail;
2770 }
2771 p++; q++;
2772 }
2773 }
2774 MOP_OUT;
2775 NEXT;
2776
2777 CASE(OP_EXACT2) MOP_IN(OP_EXACT2);
2778 DATA_ENSURE(2);
2779 if (*p != *s) goto fail;
2780 p++; s++;
2781 if (*p != *s) goto fail;
2782 sprev = s;
2783 p++; s++;
2784 MOP_OUT;
2785 JUMP;
2786
2787 CASE(OP_EXACT3) MOP_IN(OP_EXACT3);
2788 DATA_ENSURE(3);
2789 if (*p != *s) goto fail;
2790 p++; s++;
2791 if (*p != *s) goto fail;
2792 p++; s++;
2793 if (*p != *s) goto fail;
2794 sprev = s;
2795 p++; s++;
2796 MOP_OUT;
2797 JUMP;
2798
2799 CASE(OP_EXACT4) MOP_IN(OP_EXACT4);
2800 DATA_ENSURE(4);
2801 if (*p != *s) goto fail;
2802 p++; s++;
2803 if (*p != *s) goto fail;
2804 p++; s++;
2805 if (*p != *s) goto fail;
2806 p++; s++;
2807 if (*p != *s) goto fail;
2808 sprev = s;
2809 p++; s++;
2810 MOP_OUT;
2811 JUMP;
2812
2813 CASE(OP_EXACT5) MOP_IN(OP_EXACT5);
2814 DATA_ENSURE(5);
2815 if (*p != *s) goto fail;
2816 p++; s++;
2817 if (*p != *s) goto fail;
2818 p++; s++;
2819 if (*p != *s) goto fail;
2820 p++; s++;
2821 if (*p != *s) goto fail;
2822 p++; s++;
2823 if (*p != *s) goto fail;
2824 sprev = s;
2825 p++; s++;
2826 MOP_OUT;
2827 JUMP;
2828
2829 CASE(OP_EXACTN) MOP_IN(OP_EXACTN);
2830 GET_LENGTH_INC(tlen, p);
2831 DATA_ENSURE(tlen);
2832 while (tlen-- > 0) {
2833 if (*p++ != *s++) goto fail;
2834 }
2835 sprev = s - 1;
2836 MOP_OUT;
2837 JUMP;
2838
2839 CASE(OP_EXACTN_IC) MOP_IN(OP_EXACTN_IC);
2840 {
2841 int len;
2842 UChar *q, *endp, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
2843
2844 GET_LENGTH_INC(tlen, p);
2845 endp = p + tlen;
2846
2847 while (p < endp) {
2848 sprev = s;
2849 DATA_ENSURE(1);
2850 len = ONIGENC_MBC_CASE_FOLD(encode,
2851 /* DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag), */
2852 case_fold_flag,
2853 &s, end, lowbuf);
2854 DATA_ENSURE(0);
2855 if (len > endp - p) goto fail;
2856 q = lowbuf;
2857 while (len-- > 0) {
2858 if (*p != *q) goto fail;
2859 p++; q++;
2860 }
2861 }
2862 }
2863
2864 MOP_OUT;
2865 JUMP;
2866
2867 CASE(OP_EXACTMB2N1) MOP_IN(OP_EXACTMB2N1);
2868 DATA_ENSURE(2);
2869 if (*p != *s) goto fail;
2870 p++; s++;
2871 if (*p != *s) goto fail;
2872 p++; s++;
2873 MOP_OUT;
2874 NEXT;
2875
2876 CASE(OP_EXACTMB2N2) MOP_IN(OP_EXACTMB2N2);
2877 DATA_ENSURE(4);
2878 if (*p != *s) goto fail;
2879 p++; s++;
2880 if (*p != *s) goto fail;
2881 p++; s++;
2882 sprev = s;
2883 if (*p != *s) goto fail;
2884 p++; s++;
2885 if (*p != *s) goto fail;
2886 p++; s++;
2887 MOP_OUT;
2888 JUMP;
2889
2890 CASE(OP_EXACTMB2N3) MOP_IN(OP_EXACTMB2N3);
2891 DATA_ENSURE(6);
2892 if (*p != *s) goto fail;
2893 p++; s++;
2894 if (*p != *s) goto fail;
2895 p++; s++;
2896 if (*p != *s) goto fail;
2897 p++; s++;
2898 if (*p != *s) goto fail;
2899 p++; s++;
2900 sprev = s;
2901 if (*p != *s) goto fail;
2902 p++; s++;
2903 if (*p != *s) goto fail;
2904 p++; s++;
2905 MOP_OUT;
2906 JUMP;
2907
2908 CASE(OP_EXACTMB2N) MOP_IN(OP_EXACTMB2N);
2909 GET_LENGTH_INC(tlen, p);
2910 DATA_ENSURE(tlen * 2);
2911 while (tlen-- > 0) {
2912 if (*p != *s) goto fail;
2913 p++; s++;
2914 if (*p != *s) goto fail;
2915 p++; s++;
2916 }
2917 sprev = s - 2;
2918 MOP_OUT;
2919 JUMP;
2920
2921 CASE(OP_EXACTMB3N) MOP_IN(OP_EXACTMB3N);
2922 GET_LENGTH_INC(tlen, p);
2923 DATA_ENSURE(tlen * 3);
2924 while (tlen-- > 0) {
2925 if (*p != *s) goto fail;
2926 p++; s++;
2927 if (*p != *s) goto fail;
2928 p++; s++;
2929 if (*p != *s) goto fail;
2930 p++; s++;
2931 }
2932 sprev = s - 3;
2933 MOP_OUT;
2934 JUMP;
2935
2936 CASE(OP_EXACTMBN) MOP_IN(OP_EXACTMBN);
2937 GET_LENGTH_INC(tlen, p); /* mb-len */
2938 GET_LENGTH_INC(tlen2, p); /* string len */
2939 tlen2 *= tlen;
2940 DATA_ENSURE(tlen2);
2941 while (tlen2-- > 0) {
2942 if (*p != *s) goto fail;
2943 p++; s++;
2944 }
2945 sprev = s - tlen;
2946 MOP_OUT;
2947 JUMP;
2948
2949 CASE(OP_CCLASS) MOP_IN(OP_CCLASS);
2950 DATA_ENSURE(1);
2951 if (BITSET_AT(((BitSetRef )p), *s) == 0) goto fail;
2952 p += SIZE_BITSET;
2953 s += enclen(encode, s, end); /* OP_CCLASS can match mb-code. \D, \S */
2954 MOP_OUT;
2955 NEXT;
2956
2957 CASE(OP_CCLASS_MB) MOP_IN(OP_CCLASS_MB);
2958 if (! ONIGENC_IS_MBC_HEAD(encode, s, end)) goto fail;
2959
2960 cclass_mb:
2961 GET_LENGTH_INC(tlen, p);
2962 {
2963 OnigCodePoint code;
2964 UChar *ss;
2965 int mb_len;
2966
2967 DATA_ENSURE(1);
2968 mb_len = enclen_approx(encode, s, end);
2969 DATA_ENSURE(mb_len);
2970 ss = s;
2971 s += mb_len;
2972 code = ONIGENC_MBC_TO_CODE(encode, ss, s);
2973
2974#ifdef PLATFORM_UNALIGNED_WORD_ACCESS
2975 if (! onig_is_in_code_range(p, code)) goto fail;
2976#else
2977 q = p;
2978 ALIGNMENT_RIGHT(q);
2979 if (! onig_is_in_code_range(q, code)) goto fail;
2980#endif
2981 }
2982 p += tlen;
2983 MOP_OUT;
2984 NEXT;
2985
2986 CASE(OP_CCLASS_MIX) MOP_IN(OP_CCLASS_MIX);
2987 DATA_ENSURE(1);
2988 if (ONIGENC_IS_MBC_HEAD(encode, s, end)) {
2989 p += SIZE_BITSET;
2990 goto cclass_mb;
2991 }
2992 else {
2993 if (BITSET_AT(((BitSetRef )p), *s) == 0)
2994 goto fail;
2995
2996 p += SIZE_BITSET;
2997 GET_LENGTH_INC(tlen, p);
2998 p += tlen;
2999 s++;
3000 }
3001 MOP_OUT;
3002 NEXT;
3003
3004 CASE(OP_CCLASS_NOT) MOP_IN(OP_CCLASS_NOT);
3005 DATA_ENSURE(1);
3006 if (BITSET_AT(((BitSetRef )p), *s) != 0) goto fail;
3007 p += SIZE_BITSET;
3008 s += enclen(encode, s, end);
3009 MOP_OUT;
3010 NEXT;
3011
3012 CASE(OP_CCLASS_MB_NOT) MOP_IN(OP_CCLASS_MB_NOT);
3013 DATA_ENSURE(1);
3014 if (! ONIGENC_IS_MBC_HEAD(encode, s, end)) {
3015 s++;
3016 GET_LENGTH_INC(tlen, p);
3017 p += tlen;
3018 goto cc_mb_not_success;
3019 }
3020
3021 cclass_mb_not:
3022 GET_LENGTH_INC(tlen, p);
3023 {
3024 OnigCodePoint code;
3025 UChar *ss;
3026 int mb_len = enclen(encode, s, end);
3027
3028 if (! DATA_ENSURE_CHECK(mb_len)) {
3029 DATA_ENSURE(1);
3030 s = (UChar* )end;
3031 p += tlen;
3032 goto cc_mb_not_success;
3033 }
3034
3035 ss = s;
3036 s += mb_len;
3037 code = ONIGENC_MBC_TO_CODE(encode, ss, s);
3038
3039#ifdef PLATFORM_UNALIGNED_WORD_ACCESS
3040 if (onig_is_in_code_range(p, code)) goto fail;
3041#else
3042 q = p;
3043 ALIGNMENT_RIGHT(q);
3044 if (onig_is_in_code_range(q, code)) goto fail;
3045#endif
3046 }
3047 p += tlen;
3048
3049 cc_mb_not_success:
3050 MOP_OUT;
3051 NEXT;
3052
3053 CASE(OP_CCLASS_MIX_NOT) MOP_IN(OP_CCLASS_MIX_NOT);
3054 DATA_ENSURE(1);
3055 if (ONIGENC_IS_MBC_HEAD(encode, s, end)) {
3056 p += SIZE_BITSET;
3057 goto cclass_mb_not;
3058 }
3059 else {
3060 if (BITSET_AT(((BitSetRef )p), *s) != 0)
3061 goto fail;
3062
3063 p += SIZE_BITSET;
3064 GET_LENGTH_INC(tlen, p);
3065 p += tlen;
3066 s++;
3067 }
3068 MOP_OUT;
3069 NEXT;
3070
3071 CASE(OP_ANYCHAR) MOP_IN(OP_ANYCHAR);
3072 DATA_ENSURE(1);
3073 n = enclen_approx(encode, s, end);
3074 DATA_ENSURE(n);
3075 if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail;
3076 s += n;
3077 MOP_OUT;
3078 NEXT;
3079
3080 CASE(OP_ANYCHAR_ML) MOP_IN(OP_ANYCHAR_ML);
3081 DATA_ENSURE(1);
3082 n = enclen_approx(encode, s, end);
3083 DATA_ENSURE(n);
3084 s += n;
3085 MOP_OUT;
3086 NEXT;
3087
3088 CASE(OP_ANYCHAR_STAR) MOP_IN(OP_ANYCHAR_STAR);
3089 while (DATA_ENSURE_CHECK1) {
3090 CHECK_MATCH_CACHE;
3091 STACK_PUSH_ALT(p, s, sprev, pkeep);
3092 n = enclen_approx(encode, s, end);
3093 DATA_ENSURE(n);
3094 if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail;
3095 sprev = s;
3096 s += n;
3097 }
3098 MOP_OUT;
3099 JUMP;
3100
3101 CASE(OP_ANYCHAR_ML_STAR) MOP_IN(OP_ANYCHAR_ML_STAR);
3102 while (DATA_ENSURE_CHECK1) {
3103 CHECK_MATCH_CACHE;
3104 STACK_PUSH_ALT(p, s, sprev, pkeep);
3105 n = enclen_approx(encode, s, end);
3106 if (n > 1) {
3107 DATA_ENSURE(n);
3108 sprev = s;
3109 s += n;
3110 }
3111 else {
3112 sprev = s;
3113 s++;
3114 }
3115 }
3116 MOP_OUT;
3117 JUMP;
3118
3119 CASE(OP_ANYCHAR_STAR_PEEK_NEXT) MOP_IN(OP_ANYCHAR_STAR_PEEK_NEXT);
3120 while (DATA_ENSURE_CHECK1) {
3121 CHECK_MATCH_CACHE;
3122 if (*p == *s) {
3123 STACK_PUSH_ALT(p + 1, s, sprev, pkeep);
3124 } else {
3125#ifdef USE_MATCH_CACHE
3126 /* We need to increment num_fails here, for invoking a cache optimization correctly. */
3127 /* Actually, the matching will be failed if we use `OP_ANYCHAR_STAR` simply in this case.*/
3128 msa->num_fails++;
3129#endif
3130 }
3131 n = enclen_approx(encode, s, end);
3132 DATA_ENSURE(n);
3133 if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail;
3134 sprev = s;
3135 s += n;
3136 }
3137 p++;
3138 MOP_OUT;
3139 NEXT;
3140
3141 CASE(OP_ANYCHAR_ML_STAR_PEEK_NEXT)MOP_IN(OP_ANYCHAR_ML_STAR_PEEK_NEXT);
3142 while (DATA_ENSURE_CHECK1) {
3143 CHECK_MATCH_CACHE;
3144 if (*p == *s) {
3145 STACK_PUSH_ALT(p + 1, s, sprev, pkeep);
3146 } else {
3147#ifdef USE_MATCH_CACHE
3148 /* We need to increment num_fails here, for invoking a cache optimization correctly. */
3149 /* Actually, the matching will be failed if we use `OP_ANYCHAR_STAR_ML` simply in this case.*/
3150 msa->num_fails++;
3151#endif
3152 }
3153 n = enclen_approx(encode, s, end);
3154 if (n > 1) {
3155 DATA_ENSURE(n);
3156 sprev = s;
3157 s += n;
3158 }
3159 else {
3160 sprev = s;
3161 s++;
3162 }
3163 }
3164 p++;
3165 MOP_OUT;
3166 NEXT;
3167
3168#ifdef USE_COMBINATION_EXPLOSION_CHECK
3169 CASE(OP_STATE_CHECK_ANYCHAR_STAR) MOP_IN(OP_STATE_CHECK_ANYCHAR_STAR);
3170 GET_STATE_CHECK_NUM_INC(mem, p);
3171 while (DATA_ENSURE_CHECK1) {
3172 STATE_CHECK_VAL(scv, mem);
3173 if (scv) goto fail;
3174
3175 STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem, pkeep);
3176 n = enclen_approx(encode, s, end);
3177 DATA_ENSURE(n);
3178 if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail;
3179 sprev = s;
3180 s += n;
3181 }
3182 MOP_OUT;
3183 NEXT;
3184
3185 CASE(OP_STATE_CHECK_ANYCHAR_ML_STAR)
3186 MOP_IN(OP_STATE_CHECK_ANYCHAR_ML_STAR);
3187
3188 GET_STATE_CHECK_NUM_INC(mem, p);
3189 while (DATA_ENSURE_CHECK1) {
3190 STATE_CHECK_VAL(scv, mem);
3191 if (scv) goto fail;
3192
3193 STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem, pkeep);
3194 n = enclen_approx(encode, s, end);
3195 if (n > 1) {
3196 DATA_ENSURE(n);
3197 sprev = s;
3198 s += n;
3199 }
3200 else {
3201 sprev = s;
3202 s++;
3203 }
3204 }
3205 MOP_OUT;
3206 NEXT;
3207#endif /* USE_COMBINATION_EXPLOSION_CHECK */
3208
3209 CASE(OP_WORD) MOP_IN(OP_WORD);
3210 DATA_ENSURE(1);
3211 if (! ONIGENC_IS_MBC_WORD(encode, s, end))
3212 goto fail;
3213
3214 s += enclen(encode, s, end);
3215 MOP_OUT;
3216 NEXT;
3217
3218 CASE(OP_ASCII_WORD) MOP_IN(OP_ASCII_WORD);
3219 DATA_ENSURE(1);
3220 if (! ONIGENC_IS_MBC_ASCII_WORD(encode, s, end))
3221 goto fail;
3222
3223 s += enclen(encode, s, end);
3224 MOP_OUT;
3225 NEXT;
3226
3227 CASE(OP_NOT_WORD) MOP_IN(OP_NOT_WORD);
3228 DATA_ENSURE(1);
3229 if (ONIGENC_IS_MBC_WORD(encode, s, end))
3230 goto fail;
3231
3232 s += enclen(encode, s, end);
3233 MOP_OUT;
3234 NEXT;
3235
3236 CASE(OP_NOT_ASCII_WORD) MOP_IN(OP_NOT_ASCII_WORD);
3237 DATA_ENSURE(1);
3238 if (ONIGENC_IS_MBC_ASCII_WORD(encode, s, end))
3239 goto fail;
3240
3241 s += enclen(encode, s, end);
3242 MOP_OUT;
3243 NEXT;
3244
3245 CASE(OP_WORD_BOUND) MOP_IN(OP_WORD_BOUND);
3246 if (ON_STR_BEGIN(s)) {
3247 DATA_ENSURE(1);
3248 if (! ONIGENC_IS_MBC_WORD(encode, s, end))
3249 goto fail;
3250 }
3251 else if (ON_STR_END(s)) {
3252 if (! ONIGENC_IS_MBC_WORD(encode, sprev, end))
3253 goto fail;
3254 }
3255 else {
3256 if (ONIGENC_IS_MBC_WORD(encode, s, end)
3257 == ONIGENC_IS_MBC_WORD(encode, sprev, end))
3258 goto fail;
3259 }
3260 MOP_OUT;
3261 JUMP;
3262
3263 CASE(OP_ASCII_WORD_BOUND) MOP_IN(OP_ASCII_WORD_BOUND);
3264 if (ON_STR_BEGIN(s)) {
3265 DATA_ENSURE(1);
3266 if (! ONIGENC_IS_MBC_ASCII_WORD(encode, s, end))
3267 goto fail;
3268 }
3269 else if (ON_STR_END(s)) {
3270 if (! ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end))
3271 goto fail;
3272 }
3273 else {
3274 if (ONIGENC_IS_MBC_ASCII_WORD(encode, s, end)
3275 == ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end))
3276 goto fail;
3277 }
3278 MOP_OUT;
3279 JUMP;
3280
3281 CASE(OP_NOT_WORD_BOUND) MOP_IN(OP_NOT_WORD_BOUND);
3282 if (ON_STR_BEGIN(s)) {
3283 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_WORD(encode, s, end))
3284 goto fail;
3285 }
3286 else if (ON_STR_END(s)) {
3287 if (ONIGENC_IS_MBC_WORD(encode, sprev, end))
3288 goto fail;
3289 }
3290 else {
3291 if (ONIGENC_IS_MBC_WORD(encode, s, end)
3292 != ONIGENC_IS_MBC_WORD(encode, sprev, end))
3293 goto fail;
3294 }
3295 MOP_OUT;
3296 JUMP;
3297
3298 CASE(OP_NOT_ASCII_WORD_BOUND) MOP_IN(OP_NOT_ASCII_WORD_BOUND);
3299 if (ON_STR_BEGIN(s)) {
3300 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_ASCII_WORD(encode, s, end))
3301 goto fail;
3302 }
3303 else if (ON_STR_END(s)) {
3304 if (ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end))
3305 goto fail;
3306 }
3307 else {
3308 if (ONIGENC_IS_MBC_ASCII_WORD(encode, s, end)
3309 != ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end))
3310 goto fail;
3311 }
3312 MOP_OUT;
3313 JUMP;
3314
3315#ifdef USE_WORD_BEGIN_END
3316 CASE(OP_WORD_BEGIN) MOP_IN(OP_WORD_BEGIN);
3317 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_WORD(encode, s, end)) {
3318 if (ON_STR_BEGIN(s) || !ONIGENC_IS_MBC_WORD(encode, sprev, end)) {
3319 MOP_OUT;
3320 JUMP;
3321 }
3322 }
3323 goto fail;
3324
3325 CASE(OP_ASCII_WORD_BEGIN) MOP_IN(OP_ASCII_WORD_BEGIN);
3326 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_ASCII_WORD(encode, s, end)) {
3327 if (ON_STR_BEGIN(s) || !ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end)) {
3328 MOP_OUT;
3329 JUMP;
3330 }
3331 }
3332 goto fail;
3333
3334 CASE(OP_WORD_END) MOP_IN(OP_WORD_END);
3335 if (!ON_STR_BEGIN(s) && ONIGENC_IS_MBC_WORD(encode, sprev, end)) {
3336 if (ON_STR_END(s) || !ONIGENC_IS_MBC_WORD(encode, s, end)) {
3337 MOP_OUT;
3338 JUMP;
3339 }
3340 }
3341 goto fail;
3342
3343 CASE(OP_ASCII_WORD_END) MOP_IN(OP_ASCII_WORD_END);
3344 if (!ON_STR_BEGIN(s) && ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end)) {
3345 if (ON_STR_END(s) || !ONIGENC_IS_MBC_ASCII_WORD(encode, s, end)) {
3346 MOP_OUT;
3347 JUMP;
3348 }
3349 }
3350 goto fail;
3351#endif
3352
3353 CASE(OP_BEGIN_BUF) MOP_IN(OP_BEGIN_BUF);
3354 if (! ON_STR_BEGIN(s)) goto fail;
3355 if (IS_NOTBOS(msa->options)) goto fail;
3356
3357 MOP_OUT;
3358 JUMP;
3359
3360 CASE(OP_END_BUF) MOP_IN(OP_END_BUF);
3361 if (! ON_STR_END(s)) goto fail;
3362 if (IS_NOTEOS(msa->options)) goto fail;
3363
3364 MOP_OUT;
3365 JUMP;
3366
3367 CASE(OP_BEGIN_LINE) MOP_IN(OP_BEGIN_LINE);
3368 if (ON_STR_BEGIN(s)) {
3369 if (IS_NOTBOL(msa->options)) goto fail;
3370 MOP_OUT;
3371 JUMP;
3372 }
3373 else if (ONIGENC_IS_MBC_NEWLINE(encode, sprev, end)
3374#ifdef USE_CRNL_AS_LINE_TERMINATOR
3375 && !(IS_NEWLINE_CRLF(option)
3376 && ONIGENC_IS_MBC_CRNL(encode, sprev, end))
3377#endif
3378 && !ON_STR_END(s)) {
3379 MOP_OUT;
3380 JUMP;
3381 }
3382 goto fail;
3383
3384 CASE(OP_END_LINE) MOP_IN(OP_END_LINE);
3385 if (ON_STR_END(s)) {
3386#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3387 if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE_EX(encode, sprev, str, end, option, 1)) {
3388#endif
3389 if (IS_NOTEOL(msa->options)) goto fail;
3390 MOP_OUT;
3391 JUMP;
3392#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3393 }
3394#endif
3395 }
3396 else if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 1)) {
3397 MOP_OUT;
3398 JUMP;
3399 }
3400 goto fail;
3401
3402 CASE(OP_SEMI_END_BUF) MOP_IN(OP_SEMI_END_BUF);
3403 if (ON_STR_END(s)) {
3404#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3405 if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE_EX(encode, sprev, str, end, option, 1)) {
3406#endif
3407 if (IS_NOTEOL(msa->options)) goto fail;
3408 MOP_OUT;
3409 JUMP;
3410#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3411 }
3412#endif
3413 }
3414 else if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 1)) {
3415 UChar* ss = s + enclen(encode, s, end);
3416 if (ON_STR_END(ss)) {
3417 MOP_OUT;
3418 JUMP;
3419 }
3420#ifdef USE_CRNL_AS_LINE_TERMINATOR
3421 else if (IS_NEWLINE_CRLF(option)
3422 && ONIGENC_IS_MBC_CRNL(encode, s, end)) {
3423 ss += enclen(encode, ss, end);
3424 if (ON_STR_END(ss)) {
3425 MOP_OUT;
3426 JUMP;
3427 }
3428 }
3429#endif
3430 }
3431 goto fail;
3432
3433 CASE(OP_BEGIN_POSITION) MOP_IN(OP_BEGIN_POSITION);
3434 if (s != msa->gpos)
3435 goto fail;
3436
3437 MOP_OUT;
3438 JUMP;
3439
3440 CASE(OP_MEMORY_START_PUSH) MOP_IN(OP_MEMORY_START_PUSH);
3441 GET_MEMNUM_INC(mem, p);
3442 STACK_PUSH_MEM_START(mem, s);
3443 MOP_OUT;
3444 JUMP;
3445
3446 CASE(OP_MEMORY_START) MOP_IN(OP_MEMORY_START);
3447 GET_MEMNUM_INC(mem, p);
3448 mem_start_stk[mem] = (OnigStackIndex )((void* )s);
3449 mem_end_stk[mem] = INVALID_STACK_INDEX;
3450 MOP_OUT;
3451 JUMP;
3452
3453 CASE(OP_MEMORY_END_PUSH) MOP_IN(OP_MEMORY_END_PUSH);
3454 GET_MEMNUM_INC(mem, p);
3455 STACK_PUSH_MEM_END(mem, s);
3456 MOP_OUT;
3457 JUMP;
3458
3459 CASE(OP_MEMORY_END) MOP_IN(OP_MEMORY_END);
3460 GET_MEMNUM_INC(mem, p);
3461 mem_end_stk[mem] = (OnigStackIndex )((void* )s);
3462 MOP_OUT;
3463 JUMP;
3464
3465 CASE(OP_KEEP) MOP_IN(OP_KEEP);
3466 pkeep = s;
3467 MOP_OUT;
3468 JUMP;
3469
3470#ifdef USE_SUBEXP_CALL
3471 CASE(OP_MEMORY_END_PUSH_REC) MOP_IN(OP_MEMORY_END_PUSH_REC);
3472 GET_MEMNUM_INC(mem, p);
3473 STACK_GET_MEM_START(mem, stkp); /* should be before push mem-end. */
3474 mem_start_stk[mem] = GET_STACK_INDEX(stkp);
3475 STACK_PUSH_MEM_END(mem, s);
3476 MOP_OUT;
3477 JUMP;
3478
3479 CASE(OP_MEMORY_END_REC) MOP_IN(OP_MEMORY_END_REC);
3480 GET_MEMNUM_INC(mem, p);
3481 mem_end_stk[mem] = (OnigStackIndex )((void* )s);
3482 STACK_GET_MEM_START(mem, stkp);
3483
3484 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3485 mem_start_stk[mem] = GET_STACK_INDEX(stkp);
3486 else
3487 mem_start_stk[mem] = (OnigStackIndex )((void* )stkp->u.mem.pstr);
3488
3489 STACK_PUSH_MEM_END_MARK(mem);
3490 MOP_OUT;
3491 JUMP;
3492#endif
3493
3494 CASE(OP_BACKREF1) MOP_IN(OP_BACKREF1);
3495 mem = 1;
3496 goto backref;
3497
3498 CASE(OP_BACKREF2) MOP_IN(OP_BACKREF2);
3499 mem = 2;
3500 goto backref;
3501
3502 CASE(OP_BACKREFN) MOP_IN(OP_BACKREFN);
3503 GET_MEMNUM_INC(mem, p);
3504 backref:
3505 {
3506 int len;
3507 UChar *pstart, *pend;
3508
3509 /* if you want to remove following line,
3510 you should check in parse and compile time. */
3511 if (mem > num_mem) goto fail;
3512 if (mem_end_stk[mem] == INVALID_STACK_INDEX) goto fail;
3513 if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;
3514
3515 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3516 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
3517 else
3518 pstart = (UChar* )((void* )mem_start_stk[mem]);
3519
3520 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
3521 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
3522 : (UChar* )((void* )mem_end_stk[mem]));
3523 n = pend - pstart;
3524 DATA_ENSURE(n);
3525 sprev = s;
3526 STRING_CMP(pstart, s, n);
3527 while (sprev + (len = enclen_approx(encode, sprev, end)) < s)
3528 sprev += len;
3529
3530 MOP_OUT;
3531 JUMP;
3532 }
3533
3534 CASE(OP_BACKREFN_IC) MOP_IN(OP_BACKREFN_IC);
3535 GET_MEMNUM_INC(mem, p);
3536 {
3537 int len;
3538 UChar *pstart, *pend;
3539
3540 /* if you want to remove following line,
3541 you should check in parse and compile time. */
3542 if (mem > num_mem) goto fail;
3543 if (mem_end_stk[mem] == INVALID_STACK_INDEX) goto fail;
3544 if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;
3545
3546 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3547 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
3548 else
3549 pstart = (UChar* )((void* )mem_start_stk[mem]);
3550
3551 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
3552 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
3553 : (UChar* )((void* )mem_end_stk[mem]));
3554 n = pend - pstart;
3555 DATA_ENSURE(n);
3556 sprev = s;
3557 STRING_CMP_IC(case_fold_flag, pstart, &s, n, end);
3558 while (sprev + (len = enclen_approx(encode, sprev, end)) < s)
3559 sprev += len;
3560
3561 MOP_OUT;
3562 JUMP;
3563 }
3564 NEXT;
3565
3566 CASE(OP_BACKREF_MULTI) MOP_IN(OP_BACKREF_MULTI);
3567 {
3568 int len, is_fail;
3569 UChar *pstart, *pend, *swork;
3570
3571 GET_LENGTH_INC(tlen, p);
3572 for (i = 0; i < tlen; i++) {
3573 GET_MEMNUM_INC(mem, p);
3574
3575 if (mem_end_stk[mem] == INVALID_STACK_INDEX) continue;
3576 if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;
3577
3578 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3579 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
3580 else
3581 pstart = (UChar* )((void* )mem_start_stk[mem]);
3582
3583 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
3584 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
3585 : (UChar* )((void* )mem_end_stk[mem]));
3586 n = pend - pstart;
3587 DATA_ENSURE_CONTINUE(n);
3588 sprev = s;
3589 swork = s;
3590 STRING_CMP_VALUE(pstart, swork, n, is_fail);
3591 if (is_fail) continue;
3592 s = swork;
3593 while (sprev + (len = enclen_approx(encode, sprev, end)) < s)
3594 sprev += len;
3595
3596 p += (SIZE_MEMNUM * (tlen - i - 1));
3597 break; /* success */
3598 }
3599 if (i == tlen) goto fail;
3600 MOP_OUT;
3601 JUMP;
3602 }
3603 NEXT;
3604
3605 CASE(OP_BACKREF_MULTI_IC) MOP_IN(OP_BACKREF_MULTI_IC);
3606 {
3607 int len, is_fail;
3608 UChar *pstart, *pend, *swork;
3609
3610 GET_LENGTH_INC(tlen, p);
3611 for (i = 0; i < tlen; i++) {
3612 GET_MEMNUM_INC(mem, p);
3613
3614 if (mem_end_stk[mem] == INVALID_STACK_INDEX) continue;
3615 if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;
3616
3617 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3618 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
3619 else
3620 pstart = (UChar* )((void* )mem_start_stk[mem]);
3621
3622 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
3623 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
3624 : (UChar* )((void* )mem_end_stk[mem]));
3625 n = pend - pstart;
3626 DATA_ENSURE_CONTINUE(n);
3627 sprev = s;
3628 swork = s;
3629 STRING_CMP_VALUE_IC(case_fold_flag, pstart, &swork, n, end, is_fail);
3630 if (is_fail) continue;
3631 s = swork;
3632 while (sprev + (len = enclen(encode, sprev, end)) < s)
3633 sprev += len;
3634
3635 p += (SIZE_MEMNUM * (tlen - i - 1));
3636 break; /* success */
3637 }
3638 if (i == tlen) goto fail;
3639 MOP_OUT;
3640 JUMP;
3641 }
3642
3643#ifdef USE_BACKREF_WITH_LEVEL
3644 CASE(OP_BACKREF_WITH_LEVEL)
3645 {
3646 int len;
3647 OnigOptionType ic;
3648 LengthType level;
3649
3650 GET_OPTION_INC(ic, p);
3651 GET_LENGTH_INC(level, p);
3652 GET_LENGTH_INC(tlen, p);
3653
3654 sprev = s;
3655 if (backref_match_at_nested_level(reg, stk, stk_base, ic,
3656 case_fold_flag, (int )level, (int )tlen, p, &s, end)) {
3657 while (sprev + (len = enclen(encode, sprev, end)) < s)
3658 sprev += len;
3659
3660 p += (SIZE_MEMNUM * tlen);
3661 }
3662 else
3663 goto fail;
3664
3665 MOP_OUT;
3666 JUMP;
3667 }
3668
3669#endif
3670
3671#if 0 /* no need: IS_DYNAMIC_OPTION() == 0 */
3672 CASE(OP_SET_OPTION_PUSH) MOP_IN(OP_SET_OPTION_PUSH);
3673 GET_OPTION_INC(option, p);
3674 STACK_PUSH_ALT(p, s, sprev, pkeep);
3675 p += SIZE_OP_SET_OPTION + SIZE_OP_FAIL;
3676 MOP_OUT;
3677 JUMP;
3678
3679 CASE(OP_SET_OPTION) MOP_IN(OP_SET_OPTION);
3680 GET_OPTION_INC(option, p);
3681 MOP_OUT;
3682 JUMP;
3683#endif
3684
3685 CASE(OP_NULL_CHECK_START) MOP_IN(OP_NULL_CHECK_START);
3686 GET_MEMNUM_INC(mem, p); /* mem: null check id */
3687 STACK_PUSH_NULL_CHECK_START(mem, s);
3688 MOP_OUT;
3689 JUMP;
3690
3691 CASE(OP_NULL_CHECK_END) MOP_IN(OP_NULL_CHECK_END);
3692 {
3693 int isnull;
3694
3695 GET_MEMNUM_INC(mem, p); /* mem: null check id */
3696 STACK_NULL_CHECK(isnull, mem, s);
3697 if (isnull) {
3698#ifdef ONIG_DEBUG_MATCH
3699 fprintf(stderr, "NULL_CHECK_END: skip id:%d, s:%"PRIuPTR" (%p)\n",
3700 (int )mem, (uintptr_t )s, s);
3701#endif
3702 null_check_found:
3703 /* empty loop founded, skip next instruction */
3704 switch (*p++) {
3705 case OP_JUMP:
3706 case OP_PUSH:
3707 p += SIZE_RELADDR;
3708 break;
3709 case OP_REPEAT_INC:
3710 case OP_REPEAT_INC_NG:
3711 case OP_REPEAT_INC_SG:
3712 case OP_REPEAT_INC_NG_SG:
3713 p += SIZE_MEMNUM;
3714 break;
3715 default:
3716 goto unexpected_bytecode_error;
3717 break;
3718 }
3719 }
3720 }
3721 MOP_OUT;
3722 JUMP;
3723
3724#ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
3725 CASE(OP_NULL_CHECK_END_MEMST) MOP_IN(OP_NULL_CHECK_END_MEMST);
3726 {
3727 int isnull;
3728
3729 GET_MEMNUM_INC(mem, p); /* mem: null check id */
3730 STACK_NULL_CHECK_MEMST(isnull, mem, s, reg);
3731 if (isnull) {
3732# ifdef ONIG_DEBUG_MATCH
3733 fprintf(stderr, "NULL_CHECK_END_MEMST: skip id:%d, s:%"PRIuPTR" (%p)\n",
3734 (int )mem, (uintptr_t )s, s);
3735# endif
3736 if (isnull == -1) goto fail;
3737 goto null_check_found;
3738 }
3739 }
3740 MOP_OUT;
3741 JUMP;
3742#endif
3743
3744#ifdef USE_SUBEXP_CALL
3745 CASE(OP_NULL_CHECK_END_MEMST_PUSH)
3746 MOP_IN(OP_NULL_CHECK_END_MEMST_PUSH);
3747 {
3748 int isnull;
3749
3750 GET_MEMNUM_INC(mem, p); /* mem: null check id */
3751# ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
3752 STACK_NULL_CHECK_MEMST_REC(isnull, mem, s, reg);
3753# else
3754 STACK_NULL_CHECK_REC(isnull, mem, s);
3755# endif
3756 if (isnull) {
3757# ifdef ONIG_DEBUG_MATCH
3758 fprintf(stderr, "NULL_CHECK_END_MEMST_PUSH: skip id:%d, s:%"PRIuPTR" (%p)\n",
3759 (int )mem, (uintptr_t )s, s);
3760# endif
3761 if (isnull == -1) goto fail;
3762 goto null_check_found;
3763 }
3764 else {
3765 STACK_PUSH_NULL_CHECK_END(mem);
3766 }
3767 }
3768 MOP_OUT;
3769 JUMP;
3770#endif
3771
3772 CASE(OP_JUMP) MOP_IN(OP_JUMP);
3773 GET_RELADDR_INC(addr, p);
3774 p += addr;
3775 MOP_OUT;
3776 CHECK_INTERRUPT_IN_MATCH_AT;
3777 JUMP;
3778
3779 CASE(OP_PUSH) MOP_IN(OP_PUSH);
3780 GET_RELADDR_INC(addr, p);
3781 CHECK_MATCH_CACHE;
3782 STACK_PUSH_ALT(p + addr, s, sprev, pkeep);
3783 MOP_OUT;
3784 JUMP;
3785
3786#ifdef USE_COMBINATION_EXPLOSION_CHECK
3787 CASE(OP_STATE_CHECK_PUSH) MOP_IN(OP_STATE_CHECK_PUSH);
3788 GET_STATE_CHECK_NUM_INC(mem, p);
3789 STATE_CHECK_VAL(scv, mem);
3790 if (scv) goto fail;
3791
3792 GET_RELADDR_INC(addr, p);
3793 STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem, pkeep);
3794 MOP_OUT;
3795 JUMP;
3796
3797 CASE(OP_STATE_CHECK_PUSH_OR_JUMP) MOP_IN(OP_STATE_CHECK_PUSH_OR_JUMP);
3798 GET_STATE_CHECK_NUM_INC(mem, p);
3799 GET_RELADDR_INC(addr, p);
3800 STATE_CHECK_VAL(scv, mem);
3801 if (scv) {
3802 p += addr;
3803 }
3804 else {
3805 STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem, pkeep);
3806 }
3807 MOP_OUT;
3808 JUMP;
3809
3810 CASE(OP_STATE_CHECK) MOP_IN(OP_STATE_CHECK);
3811 GET_STATE_CHECK_NUM_INC(mem, p);
3812 STATE_CHECK_VAL(scv, mem);
3813 if (scv) goto fail;
3814
3815 STACK_PUSH_STATE_CHECK(s, mem);
3816 MOP_OUT;
3817 JUMP;
3818#endif /* USE_COMBINATION_EXPLOSION_CHECK */
3819
3820 CASE(OP_POP) MOP_IN(OP_POP);
3821 STACK_POP_ONE;
3822#ifdef USE_MATCH_CACHE
3823 /* We need to increment num_fails here, for invoking a cache optimization correctly, */
3824 /* because Onigmo makes a loop, which is pairwise disjoint to the following set, as atomic. */
3825 msa->num_fails++;
3826#endif
3827 MOP_OUT;
3828 JUMP;
3829
3830#ifdef USE_OP_PUSH_OR_JUMP_EXACT
3831 CASE(OP_PUSH_OR_JUMP_EXACT1) MOP_IN(OP_PUSH_OR_JUMP_EXACT1);
3832 GET_RELADDR_INC(addr, p);
3833 if (*p == *s && DATA_ENSURE_CHECK1) {
3834 p++;
3835 CHECK_MATCH_CACHE;
3836 STACK_PUSH_ALT(p + addr, s, sprev, pkeep);
3837 MOP_OUT;
3838 JUMP;
3839 }
3840 p += (addr + 1);
3841 MOP_OUT;
3842 JUMP;
3843#endif
3844
3845 CASE(OP_PUSH_IF_PEEK_NEXT) MOP_IN(OP_PUSH_IF_PEEK_NEXT);
3846 GET_RELADDR_INC(addr, p);
3847 CHECK_MATCH_CACHE;
3848 if (*p == *s) {
3849 p++;
3850 STACK_PUSH_ALT(p + addr, s, sprev, pkeep);
3851 MOP_OUT;
3852 JUMP;
3853 }
3854 p++;
3855 INC_NUM_FAILS;
3856 MOP_OUT;
3857 JUMP;
3858
3859 CASE(OP_REPEAT) MOP_IN(OP_REPEAT);
3860 {
3861 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3862 GET_RELADDR_INC(addr, p);
3863
3864 STACK_ENSURE(1);
3865 repeat_stk[mem] = GET_STACK_INDEX(stk);
3866 STACK_PUSH_REPEAT(mem, p);
3867
3868 if (reg->repeat_range[mem].lower == 0) {
3869 CHECK_MATCH_CACHE;
3870 STACK_PUSH_ALT(p + addr, s, sprev, pkeep);
3871 }
3872 }
3873 MOP_OUT;
3874 JUMP;
3875
3876 CASE(OP_REPEAT_NG) MOP_IN(OP_REPEAT_NG);
3877 {
3878 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3879 GET_RELADDR_INC(addr, p);
3880
3881 STACK_ENSURE(1);
3882 repeat_stk[mem] = GET_STACK_INDEX(stk);
3883 STACK_PUSH_REPEAT(mem, p);
3884
3885 if (reg->repeat_range[mem].lower == 0) {
3886 CHECK_MATCH_CACHE;
3887 STACK_PUSH_ALT(p, s, sprev, pkeep);
3888 p += addr;
3889 }
3890 }
3891 MOP_OUT;
3892 JUMP;
3893
3894 CASE(OP_REPEAT_INC) MOP_IN(OP_REPEAT_INC);
3895 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3896 si = repeat_stk[mem];
3897 stkp = STACK_AT(si);
3898
3899 repeat_inc:
3900 stkp->u.repeat.count++;
3901 if (stkp->u.repeat.count >= reg->repeat_range[mem].upper) {
3902 /* end of repeat. Nothing to do. */
3903 }
3904 else if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {
3905#ifdef USE_MATCH_CACHE
3906 if (*pbegin == OP_REPEAT_INC) {
3907#undef MATCH_CACHE_HIT
3908#define MATCH_CACHE_HIT stkp->u.repeat.count--;
3909 CHECK_MATCH_CACHE;
3910#undef MATCH_CACHE_HIT
3911#define MATCH_CACHE_HIT ((void) 0)
3912 }
3913#endif
3914 STACK_PUSH_ALT(p, s, sprev, pkeep);
3915 p = STACK_AT(si)->u.repeat.pcode; /* Don't use stkp after PUSH. */
3916 }
3917 else {
3918 p = stkp->u.repeat.pcode;
3919 }
3920 STACK_PUSH_REPEAT_INC(si);
3921 MOP_OUT;
3922 CHECK_INTERRUPT_IN_MATCH_AT;
3923 JUMP;
3924
3925 CASE(OP_REPEAT_INC_SG) MOP_IN(OP_REPEAT_INC_SG);
3926 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3927 STACK_GET_REPEAT(mem, stkp);
3928 si = GET_STACK_INDEX(stkp);
3929 goto repeat_inc;
3930
3931 CASE(OP_REPEAT_INC_NG) MOP_IN(OP_REPEAT_INC_NG);
3932 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3933 si = repeat_stk[mem];
3934 stkp = STACK_AT(si);
3935
3936 repeat_inc_ng:
3937 stkp->u.repeat.count++;
3938 if (stkp->u.repeat.count < reg->repeat_range[mem].upper) {
3939 if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {
3940 UChar* pcode = stkp->u.repeat.pcode;
3941
3942 STACK_PUSH_REPEAT_INC(si);
3943 if (*pbegin == OP_REPEAT_INC_NG) {
3944 CHECK_MATCH_CACHE;
3945 }
3946 STACK_PUSH_ALT(pcode, s, sprev, pkeep);
3947 }
3948 else {
3949 p = stkp->u.repeat.pcode;
3950 STACK_PUSH_REPEAT_INC(si);
3951 }
3952 }
3953 else if (stkp->u.repeat.count == reg->repeat_range[mem].upper) {
3954 STACK_PUSH_REPEAT_INC(si);
3955 }
3956 MOP_OUT;
3957 CHECK_INTERRUPT_IN_MATCH_AT;
3958 JUMP;
3959
3960 CASE(OP_REPEAT_INC_NG_SG) MOP_IN(OP_REPEAT_INC_NG_SG);
3961 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3962 STACK_GET_REPEAT(mem, stkp);
3963 si = GET_STACK_INDEX(stkp);
3964 goto repeat_inc_ng;
3965
3966 CASE(OP_PUSH_POS) MOP_IN(OP_PUSH_POS);
3967 STACK_PUSH_POS(s, sprev, pkeep);
3968 MOP_OUT;
3969 JUMP;
3970
3971 CASE(OP_POP_POS) MOP_IN(OP_POP_POS);
3972 {
3973 STACK_POS_END(stkp);
3974 s = stkp->u.state.pstr;
3975 sprev = stkp->u.state.pstr_prev;
3976 }
3977 MOP_OUT;
3978 JUMP;
3979
3980 CASE(OP_PUSH_POS_NOT) MOP_IN(OP_PUSH_POS_NOT);
3981 GET_RELADDR_INC(addr, p);
3982 STACK_PUSH_POS_NOT(p + addr, s, sprev, pkeep);
3983 MOP_OUT;
3984 JUMP;
3985
3986 CASE(OP_FAIL_POS) MOP_IN(OP_FAIL_POS);
3987 STACK_POP_TIL_POS_NOT;
3988 goto fail;
3989
3990 CASE(OP_PUSH_STOP_BT) MOP_IN(OP_PUSH_STOP_BT);
3991 STACK_PUSH_STOP_BT;
3992 MOP_OUT;
3993 JUMP;
3994
3995 CASE(OP_POP_STOP_BT) MOP_IN(OP_POP_STOP_BT);
3996 STACK_STOP_BT_END;
3997 MOP_OUT;
3998 JUMP;
3999
4000 CASE(OP_LOOK_BEHIND) MOP_IN(OP_LOOK_BEHIND);
4001 GET_LENGTH_INC(tlen, p);
4002 s = (UChar* )ONIGENC_STEP_BACK(encode, str, s, end, (int )tlen);
4003 if (IS_NULL(s)) goto fail;
4004 sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s, end);
4005 MOP_OUT;
4006 JUMP;
4007
4008 CASE(OP_PUSH_LOOK_BEHIND_NOT) MOP_IN(OP_PUSH_LOOK_BEHIND_NOT);
4009 GET_RELADDR_INC(addr, p);
4010 GET_LENGTH_INC(tlen, p);
4011 q = (UChar* )ONIGENC_STEP_BACK(encode, str, s, end, (int )tlen);
4012 if (IS_NULL(q)) {
4013 /* too short case -> success. ex. /(?<!XXX)a/.match("a")
4014 If you want to change to fail, replace following line. */
4015 p += addr;
4016 /* goto fail; */
4017 }
4018 else {
4019 STACK_PUSH_LOOK_BEHIND_NOT(p + addr, s, sprev, pkeep);
4020 s = q;
4021 sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s, end);
4022 }
4023 MOP_OUT;
4024 JUMP;
4025
4026 CASE(OP_FAIL_LOOK_BEHIND_NOT) MOP_IN(OP_FAIL_LOOK_BEHIND_NOT);
4027 STACK_POP_TIL_LOOK_BEHIND_NOT;
4028 goto fail;
4029
4030 CASE(OP_PUSH_ABSENT_POS) MOP_IN(OP_PUSH_ABSENT_POS);
4031 /* Save the absent-start-pos and the original end-pos. */
4032 STACK_PUSH_ABSENT_POS(s, ABSENT_END_POS);
4033 MOP_OUT;
4034 JUMP;
4035
4036 CASE(OP_ABSENT) MOP_IN(OP_ABSENT);
4037 {
4038 const UChar* aend = ABSENT_END_POS;
4039 UChar* absent;
4040 UChar* selfp = p - 1;
4041
4042 STACK_POP_ABSENT_POS(absent, ABSENT_END_POS); /* Restore end-pos. */
4043 GET_RELADDR_INC(addr, p);
4044#ifdef ONIG_DEBUG_MATCH
4045 fprintf(stderr, "ABSENT: s:%p, end:%p, absent:%p, aend:%p\n", s, end, absent, aend);
4046#endif
4047 if ((absent > aend) && (s > absent)) {
4048 /* An empty match occurred in (?~...) at the start point.
4049 * Never match. */
4050 STACK_POP;
4051 goto fail;
4052 }
4053 else if ((s >= aend) && (s > absent)) {
4054 if (s > aend) {
4055 /* Only one (or less) character matched in the last iteration.
4056 * This is not a possible point. */
4057 goto fail;
4058 }
4059 /* All possible points were found. Try matching after (?~...). */
4060 DATA_ENSURE(0);
4061 p += addr;
4062 }
4063 else if (s == end) {
4064 /* At the end of the string, just match with it */
4065 DATA_ENSURE(0);
4066 p += addr;
4067 }
4068 else {
4069 STACK_PUSH_ALT(p + addr, s, sprev, pkeep); /* Push possible point. */
4070 n = enclen(encode, s, end);
4071 STACK_PUSH_ABSENT_POS(absent, ABSENT_END_POS); /* Save the original pos. */
4072 STACK_PUSH_ALT(selfp, s + n, s, pkeep); /* Next iteration. */
4073 STACK_PUSH_ABSENT;
4074 ABSENT_END_POS = aend;
4075 }
4076 }
4077 MOP_OUT;
4078 JUMP;
4079
4080 CASE(OP_ABSENT_END) MOP_IN(OP_ABSENT_END);
4081 /* The pattern inside (?~...) was matched.
4082 * Set the end-pos temporary and go to next iteration. */
4083 if (sprev < ABSENT_END_POS)
4084 ABSENT_END_POS = sprev;
4085#ifdef ONIG_DEBUG_MATCH
4086 fprintf(stderr, "ABSENT_END: end:%p\n", ABSENT_END_POS);
4087#endif
4088 STACK_POP_TIL_ABSENT;
4089 goto fail;
4090
4091#ifdef USE_SUBEXP_CALL
4092 CASE(OP_CALL) MOP_IN(OP_CALL);
4093 GET_ABSADDR_INC(addr, p);
4094 STACK_PUSH_CALL_FRAME(p);
4095 p = reg->p + addr;
4096 MOP_OUT;
4097 JUMP;
4098
4099 CASE(OP_RETURN) MOP_IN(OP_RETURN);
4100 STACK_RETURN(p);
4101 STACK_PUSH_RETURN;
4102 MOP_OUT;
4103 JUMP;
4104#endif
4105
4106 CASE(OP_CONDITION) MOP_IN(OP_CONDITION);
4107 GET_MEMNUM_INC(mem, p);
4108 GET_RELADDR_INC(addr, p);
4109 if ((mem > num_mem) ||
4110 (mem_end_stk[mem] == INVALID_STACK_INDEX) ||
4111 (mem_start_stk[mem] == INVALID_STACK_INDEX)) {
4112 p += addr;
4113 }
4114 MOP_OUT;
4115 JUMP;
4116
4117 CASE(OP_FINISH)
4118 goto finish;
4119
4120 CASE(OP_FAIL)
4121 if (0) {
4122 /* fall */
4123 fail:
4124 MOP_OUT;
4125 }
4126 MOP_IN(OP_FAIL);
4127 STACK_POP;
4128 p = stk->u.state.pcode;
4129 s = stk->u.state.pstr;
4130 sprev = stk->u.state.pstr_prev;
4131 pkeep = stk->u.state.pkeep;
4132
4133#ifdef USE_MATCH_CACHE
4134 if (
4135 msa->match_cache_status != MATCH_CACHE_STATUS_DISABLED &&
4136 ++msa->num_fails >= (OnigPosition)(end - str) * msa->num_cache_opcodes
4137 ) {
4138 if (msa->match_cache_status == MATCH_CACHE_STATUS_UNINIT) {
4139 msa->match_cache_status = MATCH_CACHE_STATUS_INIT;
4140 OnigPosition r = count_num_cache_opcodes(reg, &msa->num_cache_opcodes);
4141 if (r < 0) goto bytecode_error;
4142 }
4143 if (msa->num_cache_opcodes == NUM_CACHE_OPCODES_IMPOSSIBLE || msa->num_cache_opcodes == 0) {
4144 msa->match_cache_status = MATCH_CACHE_STATUS_DISABLED;
4145 goto fail_match_cache;
4146 }
4147 if (msa->num_fails < (OnigPosition)(end - str) * msa->num_cache_opcodes) {
4148 goto fail_match_cache;
4149 }
4150 if (msa->cache_opcodes == NULL) {
4151 msa->match_cache_status = MATCH_CACHE_STATUS_ENABLED;
4152 OnigCacheOpcode* cache_opcodes = (OnigCacheOpcode*)xmalloc(msa->num_cache_opcodes * sizeof(OnigCacheOpcode));
4153 if (cache_opcodes == NULL) {
4154 goto memory_error;
4155 }
4156 OnigPosition r = init_cache_opcodes(reg, cache_opcodes, &msa->num_cache_points);
4157 if (r < 0) {
4158 if (r == ONIGERR_UNEXPECTED_BYTECODE) goto unexpected_bytecode_error;
4159 else goto bytecode_error;
4160 }
4161 msa->cache_opcodes = cache_opcodes;
4162#ifdef ONIG_DEBUG_MATCH_CACHE
4163 fprintf(stderr, "MATCH CACHE: #cache opcodes = %ld\n", msa->num_cache_opcodes);
4164 fprintf(stderr, "MATCH CACHE: #cache points = %ld\n", msa->num_cache_points);
4165 fprintf(stderr, "MATCH CACHE: cache opcodes (%p):\n", msa->cache_opcodes);
4166 for (int i = 0; i < msa->num_cache_opcodes; i++) {
4167 fprintf(stderr, "MATCH CACHE: [%p] cache_point=%ld outer_repeat_mem=%d num_cache_opcodes_at_outer_repeat=%ld num_cache_opcodes_in_outer_repeat=%ld lookaround_nesting=%d match_addr=%p\n", msa->cache_opcodes[i].addr, msa->cache_opcodes[i].cache_point, msa->cache_opcodes[i].outer_repeat_mem, msa->cache_opcodes[i].num_cache_points_at_outer_repeat, msa->cache_opcodes[i].num_cache_points_in_outer_repeat, msa->cache_opcodes[i].lookaround_nesting, msa->cache_opcodes[i].match_addr);
4168 }
4169#endif
4170 }
4171 if (msa->match_cache_buf == NULL) {
4172 size_t length = (end - str) + 1;
4173 size_t num_match_cache_points = (size_t)msa->num_cache_points * length;
4174#ifdef ONIG_DEBUG_MATCH_CACHE
4175 fprintf(stderr, "MATCH CACHE: #match cache points = %zu (length = %zu)\n", num_match_cache_points, length);
4176#endif
4177 /* Overflow check */
4178 if (num_match_cache_points / length != (size_t)msa->num_cache_points) {
4179 goto memory_error;
4180 }
4181 if (num_match_cache_points >= (size_t)PTRDIFF_MAX) {
4182 goto memory_error;
4183 }
4184 size_t match_cache_buf_length = (num_match_cache_points >> 3) + (num_match_cache_points & 7 ? 1 : 0) + 1;
4185 uint8_t* match_cache_buf = (uint8_t*)xmalloc(match_cache_buf_length * sizeof(uint8_t));
4186 if (match_cache_buf == NULL) {
4187 goto memory_error;
4188 }
4189 xmemset(match_cache_buf, 0, match_cache_buf_length * sizeof(uint8_t));
4190 msa->match_cache_buf = match_cache_buf;
4191 }
4192 }
4193 fail_match_cache:
4194#endif
4195
4196#ifdef USE_COMBINATION_EXPLOSION_CHECK
4197 if (stk->u.state.state_check != 0) {
4198 stk->type = STK_STATE_CHECK_MARK;
4199 stk++;
4200 }
4201#endif
4202
4203 MOP_OUT;
4204 CHECK_INTERRUPT_IN_MATCH_AT;
4205 JUMP;
4206
4207 DEFAULT
4208 goto bytecode_error;
4209 } VM_LOOP_END
4210
4211 finish:
4212 STACK_SAVE;
4213 xfree(xmalloc_base);
4214 return best_len;
4215
4216#ifdef ONIG_DEBUG
4217 stack_error:
4218 STACK_SAVE;
4219 xfree(xmalloc_base);
4220 return ONIGERR_STACK_BUG;
4221#endif
4222
4223 bytecode_error:
4224 STACK_SAVE;
4225 xfree(xmalloc_base);
4226 return ONIGERR_UNDEFINED_BYTECODE;
4227
4228 unexpected_bytecode_error:
4229 STACK_SAVE;
4230 xfree(xmalloc_base);
4231 return ONIGERR_UNEXPECTED_BYTECODE;
4232
4233 timeout:
4234 STACK_SAVE;
4235 xfree(xmalloc_base);
4236 return ONIGERR_TIMEOUT;
4237
4238#ifdef USE_MATCH_CACHE
4239 memory_error:
4240 STACK_SAVE;
4241 xfree(xmalloc_base);
4242 return ONIGERR_MEMORY;
4243#endif
4244}
4245
4246
4247static UChar*
4248slow_search(OnigEncoding enc, UChar* target, UChar* target_end,
4249 const UChar* text, const UChar* text_end, UChar* text_range)
4250{
4251 UChar *t, *p, *s, *end;
4252
4253 end = (UChar* )text_end;
4254 end -= target_end - target - 1;
4255 if (end > text_range)
4256 end = text_range;
4257
4258 s = (UChar* )text;
4259
4260 if (enc->max_enc_len == enc->min_enc_len) {
4261 int n = enc->max_enc_len;
4262
4263 while (s < end) {
4264 if (*s == *target) {
4265 p = s + 1;
4266 t = target + 1;
4267 if (target_end == t || memcmp(t, p, target_end - t) == 0)
4268 return s;
4269 }
4270 s += n;
4271 }
4272 return (UChar* )NULL;
4273 }
4274 while (s < end) {
4275 if (*s == *target) {
4276 p = s + 1;
4277 t = target + 1;
4278 if (target_end == t || memcmp(t, p, target_end - t) == 0)
4279 return s;
4280 }
4281 s += enclen(enc, s, text_end);
4282 }
4283
4284 return (UChar* )NULL;
4285}
4286
4287static int
4288str_lower_case_match(OnigEncoding enc, int case_fold_flag,
4289 const UChar* t, const UChar* tend,
4290 const UChar* p, const UChar* end)
4291{
4292 int lowlen;
4293 UChar *q, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
4294
4295 while (t < tend) {
4296 lowlen = ONIGENC_MBC_CASE_FOLD(enc, case_fold_flag, &p, end, lowbuf);
4297 if (tend - t < lowlen) return 0;
4298 q = lowbuf;
4299 while (lowlen > 0) {
4300 if (*t++ != *q++) return 0;
4301 lowlen--;
4302 }
4303 }
4304
4305 return 1;
4306}
4307
4308static UChar*
4309slow_search_ic(OnigEncoding enc, int case_fold_flag,
4310 UChar* target, UChar* target_end,
4311 const UChar* text, const UChar* text_end, UChar* text_range)
4312{
4313 UChar *s, *end;
4314
4315 end = (UChar* )text_end;
4316 end -= target_end - target - 1;
4317 if (end > text_range)
4318 end = text_range;
4319
4320 s = (UChar* )text;
4321
4322 while (s < end) {
4323 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4324 s, text_end))
4325 return s;
4326
4327 s += enclen(enc, s, text_end);
4328 }
4329
4330 return (UChar* )NULL;
4331}
4332
4333static UChar*
4334slow_search_backward(OnigEncoding enc, UChar* target, UChar* target_end,
4335 const UChar* text, const UChar* adjust_text,
4336 const UChar* text_end, const UChar* text_start)
4337{
4338 UChar *t, *p, *s;
4339
4340 s = (UChar* )text_end;
4341 s -= (target_end - target);
4342 if (s > text_start)
4343 s = (UChar* )text_start;
4344 else
4345 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s, text_end);
4346
4347 while (s >= text) {
4348 if (*s == *target) {
4349 p = s + 1;
4350 t = target + 1;
4351 while (t < target_end) {
4352 if (*t != *p++)
4353 break;
4354 t++;
4355 }
4356 if (t == target_end)
4357 return s;
4358 }
4359 s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s, text_end);
4360 }
4361
4362 return (UChar* )NULL;
4363}
4364
4365static UChar*
4366slow_search_backward_ic(OnigEncoding enc, int case_fold_flag,
4367 UChar* target, UChar* target_end,
4368 const UChar* text, const UChar* adjust_text,
4369 const UChar* text_end, const UChar* text_start)
4370{
4371 UChar *s;
4372
4373 s = (UChar* )text_end;
4374 s -= (target_end - target);
4375 if (s > text_start)
4376 s = (UChar* )text_start;
4377 else
4378 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s, text_end);
4379
4380 while (s >= text) {
4381 if (str_lower_case_match(enc, case_fold_flag,
4382 target, target_end, s, text_end))
4383 return s;
4384
4385 s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s, text_end);
4386 }
4387
4388 return (UChar* )NULL;
4389}
4390
4391/* Sunday's quick search applied to a multibyte string */
4392static UChar*
4393bm_search_notrev(regex_t* reg, const UChar* target, const UChar* target_end,
4394 const UChar* text, const UChar* text_end,
4395 const UChar* text_range)
4396{
4397 const UChar *s, *se, *t, *p, *end;
4398 const UChar *tail;
4399 ptrdiff_t skip, tlen1;
4400 OnigEncoding enc = reg->enc;
4401
4402# ifdef ONIG_DEBUG_SEARCH
4403 fprintf(stderr, "bm_search_notrev: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4404 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4405# endif
4406
4407 tail = target_end - 1;
4408 tlen1 = tail - target;
4409 end = text_range;
4410 if (end + tlen1 > text_end)
4411 end = text_end - tlen1;
4412
4413 s = text;
4414
4415 while (s < end) {
4416 p = se = s + tlen1;
4417 t = tail;
4418 while (*p == *t) {
4419 if (t == target) return (UChar* )s;
4420 p--; t--;
4421 }
4422 if (s + 1 >= end) break;
4423 skip = reg->map[se[1]];
4424 t = s;
4425 do {
4426 s += enclen(enc, s, end);
4427 } while ((s - t) < skip && s < end);
4428 }
4429
4430 return (UChar* )NULL;
4431}
4432
4433/* Sunday's quick search */
4434static UChar*
4435bm_search(regex_t* reg, const UChar* target, const UChar* target_end,
4436 const UChar* text, const UChar* text_end, const UChar* text_range)
4437{
4438 const UChar *s, *t, *p, *end;
4439 const UChar *tail;
4440 ptrdiff_t tlen1;
4441
4442# ifdef ONIG_DEBUG_SEARCH
4443 fprintf(stderr, "bm_search: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4444 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4445# endif
4446
4447 tail = target_end - 1;
4448 tlen1 = tail - target;
4449 end = text_range + tlen1;
4450 if (end > text_end)
4451 end = text_end;
4452
4453 s = text + tlen1;
4454 while (s < end) {
4455 p = s;
4456 t = tail;
4457 while (*p == *t) {
4458 if (t == target) return (UChar* )p;
4459 p--; t--;
4460 }
4461 if (s + 1 >= end) break;
4462 s += reg->map[s[1]];
4463 }
4464
4465 return (UChar* )NULL;
4466}
4467
4468/* Sunday's quick search applied to a multibyte string (ignore case) */
4469static UChar*
4470bm_search_notrev_ic(regex_t* reg, const UChar* target, const UChar* target_end,
4471 const UChar* text, const UChar* text_end,
4472 const UChar* text_range)
4473{
4474 const UChar *s, *se, *t, *end;
4475 const UChar *tail;
4476 ptrdiff_t skip, tlen1;
4477 OnigEncoding enc = reg->enc;
4478 int case_fold_flag = reg->case_fold_flag;
4479
4480# ifdef ONIG_DEBUG_SEARCH
4481 fprintf(stderr, "bm_search_notrev_ic: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4482 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4483# endif
4484
4485 tail = target_end - 1;
4486 tlen1 = tail - target;
4487 end = text_range;
4488 if (end + tlen1 > text_end)
4489 end = text_end - tlen1;
4490
4491 s = text;
4492
4493 while (s < end) {
4494 se = s + tlen1;
4495 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4496 s, se + 1))
4497 return (UChar* )s;
4498 if (s + 1 >= end) break;
4499 skip = reg->map[se[1]];
4500 t = s;
4501 do {
4502 s += enclen(enc, s, end);
4503 } while ((s - t) < skip && s < end);
4504 }
4505
4506 return (UChar* )NULL;
4507}
4508
4509/* Sunday's quick search (ignore case) */
4510static UChar*
4511bm_search_ic(regex_t* reg, const UChar* target, const UChar* target_end,
4512 const UChar* text, const UChar* text_end, const UChar* text_range)
4513{
4514 const UChar *s, *p, *end;
4515 const UChar *tail;
4516 ptrdiff_t tlen1;
4517 OnigEncoding enc = reg->enc;
4518 int case_fold_flag = reg->case_fold_flag;
4519
4520# ifdef ONIG_DEBUG_SEARCH
4521 fprintf(stderr, "bm_search_ic: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4522 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4523# endif
4524
4525 tail = target_end - 1;
4526 tlen1 = tail - target;
4527 end = text_range + tlen1;
4528 if (end > text_end)
4529 end = text_end;
4530
4531 s = text + tlen1;
4532 while (s < end) {
4533 p = s - tlen1;
4534 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4535 p, s + 1))
4536 return (UChar* )p;
4537 if (s + 1 >= end) break;
4538 s += reg->map[s[1]];
4539 }
4540
4541 return (UChar* )NULL;
4542}
4543
4544static UChar*
4545map_search(OnigEncoding enc, UChar map[],
4546 const UChar* text, const UChar* text_range, const UChar* text_end)
4547{
4548 const UChar *s = text;
4549
4550 while (s < text_range) {
4551 if (map[*s]) return (UChar* )s;
4552
4553 s += enclen(enc, s, text_end);
4554 }
4555 return (UChar* )NULL;
4556}
4557
4558static UChar*
4559map_search_backward(OnigEncoding enc, UChar map[],
4560 const UChar* text, const UChar* adjust_text,
4561 const UChar* text_start, const UChar* text_end)
4562{
4563 const UChar *s = text_start;
4564
4565 while (s >= text) {
4566 if (map[*s]) return (UChar* )s;
4567
4568 s = onigenc_get_prev_char_head(enc, adjust_text, s, text_end);
4569 }
4570 return (UChar* )NULL;
4571}
4572
4573extern OnigPosition
4574onig_match(regex_t* reg, const UChar* str, const UChar* end, const UChar* at, OnigRegion* region,
4575 OnigOptionType option)
4576{
4577 ptrdiff_t r;
4578 UChar *prev;
4579 OnigMatchArg msa;
4580
4581 MATCH_ARG_INIT(msa, option, region, at, at);
4582#ifdef USE_COMBINATION_EXPLOSION_CHECK
4583 {
4584 ptrdiff_t offset = at - str;
4585 STATE_CHECK_BUFF_INIT(msa, end - str, offset, reg->num_comb_exp_check);
4586 }
4587#endif
4588
4589 if (region) {
4590 r = onig_region_resize_clear(region, reg->num_mem + 1);
4591 }
4592 else
4593 r = 0;
4594
4595 if (r == 0) {
4596 prev = (UChar* )onigenc_get_prev_char_head(reg->enc, str, at, end);
4597 r = match_at(reg, str, end,
4598#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
4599 end,
4600#endif
4601 at, prev, &msa);
4602 }
4603
4604 MATCH_ARG_FREE(msa);
4605 return r;
4606}
4607
4608static int
4609forward_search_range(regex_t* reg, const UChar* str, const UChar* end, UChar* s,
4610 UChar* range, UChar** low, UChar** high, UChar** low_prev)
4611{
4612 UChar *p, *pprev = (UChar* )NULL;
4613 size_t input_len = end - str;
4614
4615#ifdef ONIG_DEBUG_SEARCH
4616 fprintf(stderr, "forward_search_range: str: %"PRIuPTR" (%p), end: %"PRIuPTR" (%p), s: %"PRIuPTR" (%p), range: %"PRIuPTR" (%p)\n",
4617 (uintptr_t )str, str, (uintptr_t )end, end, (uintptr_t )s, s, (uintptr_t )range, range);
4618#endif
4619
4620 if (reg->dmin > input_len) {
4621 return 0;
4622 }
4623
4624 p = s;
4625 if (reg->dmin != 0) {
4626 if ((OnigDistance)(end - p) <= reg->dmin) return 0; /* fail */
4627 if (ONIGENC_IS_SINGLEBYTE(reg->enc)) {
4628 p += reg->dmin;
4629 }
4630 else {
4631 UChar *q = p + reg->dmin;
4632
4633 while (p < q) p += enclen(reg->enc, p, end);
4634 }
4635 }
4636
4637 retry:
4638 switch (reg->optimize) {
4639 case ONIG_OPTIMIZE_EXACT:
4640 p = slow_search(reg->enc, reg->exact, reg->exact_end, p, end, range);
4641 break;
4642 case ONIG_OPTIMIZE_EXACT_IC:
4643 p = slow_search_ic(reg->enc, reg->case_fold_flag,
4644 reg->exact, reg->exact_end, p, end, range);
4645 break;
4646
4647 case ONIG_OPTIMIZE_EXACT_BM:
4648 p = bm_search(reg, reg->exact, reg->exact_end, p, end, range);
4649 break;
4650
4651 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:
4652 p = bm_search_notrev(reg, reg->exact, reg->exact_end, p, end, range);
4653 break;
4654
4655 case ONIG_OPTIMIZE_EXACT_BM_IC:
4656 p = bm_search_ic(reg, reg->exact, reg->exact_end, p, end, range);
4657 break;
4658
4659 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV_IC:
4660 p = bm_search_notrev_ic(reg, reg->exact, reg->exact_end, p, end, range);
4661 break;
4662
4663 case ONIG_OPTIMIZE_MAP:
4664 p = map_search(reg->enc, reg->map, p, range, end);
4665 break;
4666 }
4667
4668 if (p && p < range) {
4669 if ((OnigDistance)(p - s) < reg->dmin) {
4670 retry_gate:
4671 pprev = p;
4672 p += enclen(reg->enc, p, end);
4673 goto retry;
4674 }
4675
4676 if (reg->sub_anchor) {
4677 UChar* prev;
4678
4679 switch (reg->sub_anchor) {
4680 case ANCHOR_BEGIN_LINE:
4681 if (!ON_STR_BEGIN(p)) {
4682 prev = onigenc_get_prev_char_head(reg->enc,
4683 (pprev ? pprev : str), p, end);
4684 if (!ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 0))
4685 goto retry_gate;
4686 }
4687 break;
4688
4689 case ANCHOR_END_LINE:
4690 if (ON_STR_END(p)) {
4691#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
4692 prev = (UChar* )onigenc_get_prev_char_head(reg->enc,
4693 (pprev ? pprev : str), p);
4694 if (prev && ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 1))
4695 goto retry_gate;
4696#endif
4697 }
4698 else if (! ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, p, str, end, reg->options, 1))
4699 goto retry_gate;
4700 break;
4701 }
4702 }
4703
4704 if (reg->dmax == 0) {
4705 *low = p;
4706 if (low_prev) {
4707 if (*low > s)
4708 *low_prev = onigenc_get_prev_char_head(reg->enc, s, p, end);
4709 else
4710 *low_prev = onigenc_get_prev_char_head(reg->enc,
4711 (pprev ? pprev : str), p, end);
4712 }
4713 *high = p;
4714 }
4715 else {
4716 if (reg->dmax != ONIG_INFINITE_DISTANCE) {
4717 if ((OnigDistance)(p - str) < reg->dmax) {
4718 *low = (UChar* )str;
4719 if (low_prev)
4720 *low_prev = onigenc_get_prev_char_head(reg->enc, str, *low, end);
4721 }
4722 else {
4723 *low = p - reg->dmax;
4724 if (*low > s) {
4725 *low = onigenc_get_right_adjust_char_head_with_prev(reg->enc, s,
4726 *low, end, (const UChar** )low_prev);
4727 if (low_prev && IS_NULL(*low_prev))
4728 *low_prev = onigenc_get_prev_char_head(reg->enc,
4729 (pprev ? pprev : s), *low, end);
4730 }
4731 else {
4732 if (low_prev)
4733 *low_prev = onigenc_get_prev_char_head(reg->enc,
4734 (pprev ? pprev : str), *low, end);
4735 }
4736 }
4737 }
4738 /* no needs to adjust *high, *high is used as range check only */
4739 if ((OnigDistance)(p - str) < reg->dmin)
4740 *high = (UChar* )str;
4741 else
4742 *high = p - reg->dmin;
4743 }
4744
4745#ifdef ONIG_DEBUG_SEARCH
4746 fprintf(stderr,
4747 "forward_search_range success: low: %"PRIdPTR", high: %"PRIdPTR", dmin: %"PRIdPTR", dmax: %"PRIdPTR"\n",
4748 *low - str, *high - str, reg->dmin, reg->dmax);
4749#endif
4750 return 1; /* success */
4751 }
4752
4753 return 0; /* fail */
4754}
4755
4756#define BM_BACKWARD_SEARCH_LENGTH_THRESHOLD 100
4757
4758static int
4759backward_search_range(regex_t* reg, const UChar* str, const UChar* end,
4760 UChar* s, const UChar* range, UChar* adjrange,
4761 UChar** low, UChar** high)
4762{
4763 UChar *p;
4764 size_t input_len = end - str;
4765
4766 if (reg->dmin > input_len) {
4767 return 0;
4768 }
4769
4770 p = s;
4771
4772 retry:
4773 switch (reg->optimize) {
4774 case ONIG_OPTIMIZE_EXACT:
4775 exact_method:
4776 p = slow_search_backward(reg->enc, reg->exact, reg->exact_end,
4777 range, adjrange, end, p);
4778 break;
4779
4780 case ONIG_OPTIMIZE_EXACT_IC:
4781 case ONIG_OPTIMIZE_EXACT_BM_IC:
4782 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV_IC:
4783 p = slow_search_backward_ic(reg->enc, reg->case_fold_flag,
4784 reg->exact, reg->exact_end,
4785 range, adjrange, end, p);
4786 break;
4787
4788 case ONIG_OPTIMIZE_EXACT_BM:
4789 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:
4790 goto exact_method;
4791 break;
4792
4793 case ONIG_OPTIMIZE_MAP:
4794 p = map_search_backward(reg->enc, reg->map, range, adjrange, p, end);
4795 break;
4796 }
4797
4798 if (p) {
4799 if (reg->sub_anchor) {
4800 UChar* prev;
4801
4802 switch (reg->sub_anchor) {
4803 case ANCHOR_BEGIN_LINE:
4804 if (!ON_STR_BEGIN(p)) {
4805 prev = onigenc_get_prev_char_head(reg->enc, str, p, end);
4806 if (!ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 0)) {
4807 p = prev;
4808 goto retry;
4809 }
4810 }
4811 break;
4812
4813 case ANCHOR_END_LINE:
4814 if (ON_STR_END(p)) {
4815#ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
4816 prev = onigenc_get_prev_char_head(reg->enc, adjrange, p);
4817 if (IS_NULL(prev)) goto fail;
4818 if (ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 1)) {
4819 p = prev;
4820 goto retry;
4821 }
4822#endif
4823 }
4824 else if (! ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, p, str, end, reg->options, 1)) {
4825 p = onigenc_get_prev_char_head(reg->enc, adjrange, p, end);
4826 if (IS_NULL(p)) goto fail;
4827 goto retry;
4828 }
4829 break;
4830 }
4831 }
4832
4833 if (reg->dmax != ONIG_INFINITE_DISTANCE) {
4834 if ((OnigDistance)(p - str) < reg->dmax)
4835 *low = (UChar* )str;
4836 else
4837 *low = p - reg->dmax;
4838
4839 if (reg->dmin != 0) {
4840 if ((OnigDistance)(p - str) < reg->dmin)
4841 *high = (UChar* )str;
4842 else
4843 *high = p - reg->dmin;
4844 }
4845 else {
4846 *high = p;
4847 }
4848
4849 *high = onigenc_get_right_adjust_char_head(reg->enc, adjrange, *high, end);
4850 }
4851
4852#ifdef ONIG_DEBUG_SEARCH
4853 fprintf(stderr, "backward_search_range: low: %d, high: %d\n",
4854 (int )(*low - str), (int )(*high - str));
4855#endif
4856 return 1; /* success */
4857 }
4858
4859 fail:
4860#ifdef ONIG_DEBUG_SEARCH
4861 fprintf(stderr, "backward_search_range: fail.\n");
4862#endif
4863 return 0; /* fail */
4864}
4865
4866
4867extern OnigPosition
4868onig_search(regex_t* reg, const UChar* str, const UChar* end,
4869 const UChar* start, const UChar* range, OnigRegion* region, OnigOptionType option)
4870{
4871 return onig_search_gpos(reg, str, end, start, start, range, region, option);
4872}
4873
4874extern OnigPosition
4875onig_search_gpos(regex_t* reg, const UChar* str, const UChar* end,
4876 const UChar* global_pos,
4877 const UChar* start, const UChar* range, OnigRegion* region, OnigOptionType option)
4878{
4879 ptrdiff_t r;
4880 UChar *s, *prev;
4881 OnigMatchArg msa;
4882#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
4883 const UChar *orig_start = start;
4884 const UChar *orig_range = range;
4885#endif
4886
4887#ifdef ONIG_DEBUG_SEARCH
4888 fprintf(stderr,
4889 "onig_search (entry point): str: %"PRIuPTR" (%p), end: %"PRIuPTR", start: %"PRIuPTR", range: %"PRIuPTR"\n",
4890 (uintptr_t )str, str, end - str, start - str, range - str);
4891#endif
4892
4893 if (region) {
4894 r = onig_region_resize_clear(region, reg->num_mem + 1);
4895 if (r) goto finish_no_msa;
4896 }
4897
4898 if (start > end || start < str) goto mismatch_no_msa;
4899
4900
4901#ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
4902# ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
4903# define MATCH_AND_RETURN_CHECK(upper_range) \
4904 r = match_at(reg, str, end, (upper_range), s, prev, &msa); \
4905 switch (r) { \
4906 case ONIG_MISMATCH: \
4907 break; \
4908 case ONIGERR_TIMEOUT: \
4909 goto timeout; \
4910 default: \
4911 if (r >= 0) { \
4912 if (! IS_FIND_LONGEST(reg->options)) { \
4913 goto match; \
4914 }\
4915 }\
4916 else goto finish; /* error */ \
4917 }
4918# else
4919# define MATCH_AND_RETURN_CHECK(upper_range) \
4920 r = match_at(reg, str, end, (upper_range), s, prev, &msa); \
4921 switch (r) { \
4922 case ONIG_MISMATCH: \
4923 break; \
4924 case ONIGERR_TIMEOUT: \
4925 goto timeout; \
4926 default: \
4927 if (r >= 0) { \
4928 goto match; \
4929 }\
4930 else goto finish; /* error */ \
4931 }
4932# endif /* USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE */
4933#else
4934# ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
4935# define MATCH_AND_RETURN_CHECK(none) \
4936 r = match_at(reg, str, end, s, prev, &msa);\
4937 switch (r) { \
4938 case ONIG_MISMATCH: \
4939 break; \
4940 case ONIGERR_TIMEOUT: \
4941 goto timeout; \
4942 default: \
4943 if (r >= 0) { \
4944 if (! IS_FIND_LONGEST(reg->options)) { \
4945 goto match; \
4946 } \
4947 } \
4948 else goto finish; /* error */ \
4949 }
4950# else
4951# define MATCH_AND_RETURN_CHECK(none) \
4952 r = match_at(reg, str, end, s, prev, &msa);\
4953 switch (r) { \
4954 case ONIG_MISMATCH: \
4955 break; \
4956 case ONIGERR_TIMEOUT: \
4957 goto timeout; \
4958 default: \
4959 if (r >= 0) { \
4960 goto match; \
4961 } \
4962 else goto finish; /* error */ \
4963 }
4964# endif /* USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE */
4965#endif /* USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE */
4966
4967
4968 /* anchor optimize: resume search range */
4969 if (reg->anchor != 0 && str < end) {
4970 UChar *min_semi_end, *max_semi_end;
4971
4972 if (reg->anchor & ANCHOR_BEGIN_POSITION) {
4973 /* search start-position only */
4974 begin_position:
4975 if (range > start)
4976 {
4977 if (global_pos > start)
4978 {
4979 if (global_pos < range)
4980 range = global_pos + 1;
4981 }
4982 else
4983 range = start + 1;
4984 }
4985 else
4986 range = start;
4987 }
4988 else if (reg->anchor & ANCHOR_BEGIN_BUF) {
4989 /* search str-position only */
4990 if (range > start) {
4991 if (start != str) goto mismatch_no_msa;
4992 range = str + 1;
4993 }
4994 else {
4995 if (range <= str) {
4996 start = str;
4997 range = str;
4998 }
4999 else
5000 goto mismatch_no_msa;
5001 }
5002 }
5003 else if (reg->anchor & ANCHOR_END_BUF) {
5004 min_semi_end = max_semi_end = (UChar* )end;
5005
5006 end_buf:
5007 if ((OnigDistance)(max_semi_end - str) < reg->anchor_dmin)
5008 goto mismatch_no_msa;
5009
5010 if (range > start) {
5011 if ((OnigDistance)(min_semi_end - start) > reg->anchor_dmax) {
5012 start = min_semi_end - reg->anchor_dmax;
5013 if (start < end)
5014 start = onigenc_get_right_adjust_char_head(reg->enc, str, start, end);
5015 }
5016 if ((OnigDistance)(max_semi_end - (range - 1)) < reg->anchor_dmin) {
5017 if ((OnigDistance)(max_semi_end - str + 1) < reg->anchor_dmin)
5018 goto mismatch_no_msa;
5019 else
5020 range = max_semi_end - reg->anchor_dmin + 1;
5021 }
5022
5023 if (start > range) goto mismatch_no_msa;
5024 /* If start == range, match with empty at end.
5025 Backward search is used. */
5026 }
5027 else {
5028 if ((OnigDistance)(min_semi_end - range) > reg->anchor_dmax) {
5029 range = min_semi_end - reg->anchor_dmax;
5030 }
5031 if ((OnigDistance)(max_semi_end - start) < reg->anchor_dmin) {
5032 if ((OnigDistance)(max_semi_end - str) < reg->anchor_dmin)
5033 goto mismatch_no_msa;
5034 else {
5035 start = max_semi_end - reg->anchor_dmin;
5036 start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, start, end);
5037 }
5038 }
5039 if (range > start) goto mismatch_no_msa;
5040 }
5041 }
5042 else if (reg->anchor & ANCHOR_SEMI_END_BUF) {
5043 UChar* pre_end = ONIGENC_STEP_BACK(reg->enc, str, end, end, 1);
5044
5045 max_semi_end = (UChar* )end;
5046 if (ONIGENC_IS_MBC_NEWLINE(reg->enc, pre_end, end)) {
5047 min_semi_end = pre_end;
5048
5049#ifdef USE_CRNL_AS_LINE_TERMINATOR
5050 pre_end = ONIGENC_STEP_BACK(reg->enc, str, pre_end, end, 1);
5051 if (IS_NOT_NULL(pre_end) &&
5052 IS_NEWLINE_CRLF(reg->options) &&
5053 ONIGENC_IS_MBC_CRNL(reg->enc, pre_end, end)) {
5054 min_semi_end = pre_end;
5055 }
5056#endif
5057 if (min_semi_end > str && start <= min_semi_end) {
5058 goto end_buf;
5059 }
5060 }
5061 else {
5062 min_semi_end = (UChar* )end;
5063 goto end_buf;
5064 }
5065 }
5066 else if ((reg->anchor & ANCHOR_ANYCHAR_STAR_ML) && range > start) {
5067 goto begin_position;
5068 }
5069 }
5070 else if (str == end) { /* empty string */
5071 static const UChar address_for_empty_string[] = "";
5072
5073#ifdef ONIG_DEBUG_SEARCH
5074 fprintf(stderr, "onig_search: empty string.\n");
5075#endif
5076
5077 if (reg->threshold_len == 0) {
5078 start = end = str = address_for_empty_string;
5079 s = (UChar* )start;
5080 prev = (UChar* )NULL;
5081
5082 MATCH_ARG_INIT(msa, option, region, start, start);
5083#ifdef USE_COMBINATION_EXPLOSION_CHECK
5084 msa.state_check_buff = (void* )0;
5085 msa.state_check_buff_size = 0; /* NO NEED, for valgrind */
5086#endif
5087 MATCH_AND_RETURN_CHECK(end);
5088 goto mismatch;
5089 }
5090 goto mismatch_no_msa;
5091 }
5092
5093#ifdef ONIG_DEBUG_SEARCH
5094 fprintf(stderr, "onig_search(apply anchor): end: %d, start: %d, range: %d\n",
5095 (int )(end - str), (int )(start - str), (int )(range - str));
5096#endif
5097
5098 MATCH_ARG_INIT(msa, option, region, start, global_pos);
5099#ifdef USE_COMBINATION_EXPLOSION_CHECK
5100 {
5101 ptrdiff_t offset = (MIN(start, range) - str);
5102 STATE_CHECK_BUFF_INIT(msa, end - str, offset, reg->num_comb_exp_check);
5103 }
5104#endif
5105
5106 s = (UChar* )start;
5107 if (range > start) { /* forward search */
5108 if (s > str)
5109 prev = onigenc_get_prev_char_head(reg->enc, str, s, end);
5110 else
5111 prev = (UChar* )NULL;
5112
5113 if (reg->optimize != ONIG_OPTIMIZE_NONE) {
5114 UChar *sch_range, *low, *high, *low_prev;
5115
5116 if (reg->dmax != 0) {
5117 if (reg->dmax == ONIG_INFINITE_DISTANCE)
5118 sch_range = (UChar* )end;
5119 else {
5120 if ((OnigDistance)(end - range) < reg->dmax)
5121 sch_range = (UChar* )end;
5122 else {
5123 sch_range = (UChar* )range + reg->dmax;
5124 }
5125 }
5126 }
5127 else
5128 sch_range = (UChar* )range;
5129
5130 if ((end - start) < reg->threshold_len)
5131 goto mismatch;
5132
5133 if (reg->dmax != ONIG_INFINITE_DISTANCE) {
5134 do {
5135 if (! forward_search_range(reg, str, end, s, sch_range,
5136 &low, &high, &low_prev)) goto mismatch;
5137 if (s < low) {
5138 s = low;
5139 prev = low_prev;
5140 }
5141 while (s <= high) {
5142 MATCH_AND_RETURN_CHECK(orig_range);
5143 prev = s;
5144 s += enclen(reg->enc, s, end);
5145 }
5146 } while (s < range);
5147 goto mismatch;
5148 }
5149 else { /* check only. */
5150 if (! forward_search_range(reg, str, end, s, sch_range,
5151 &low, &high, (UChar** )NULL)) goto mismatch;
5152
5153 if ((reg->anchor & ANCHOR_ANYCHAR_STAR) != 0) {
5154 do {
5155 MATCH_AND_RETURN_CHECK(orig_range);
5156 prev = s;
5157 s += enclen(reg->enc, s, end);
5158
5159 if ((reg->anchor & (ANCHOR_LOOK_BEHIND | ANCHOR_PREC_READ_NOT)) == 0) {
5160 while (!ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 0)
5161 && s < range) {
5162 prev = s;
5163 s += enclen(reg->enc, s, end);
5164 }
5165 }
5166 } while (s < range);
5167 goto mismatch;
5168 }
5169 }
5170 }
5171
5172 do {
5173 MATCH_AND_RETURN_CHECK(orig_range);
5174 prev = s;
5175 s += enclen(reg->enc, s, end);
5176 } while (s < range);
5177
5178 if (s == range) { /* because empty match with /$/. */
5179 MATCH_AND_RETURN_CHECK(orig_range);
5180 }
5181 }
5182 else { /* backward search */
5183 if (reg->optimize != ONIG_OPTIMIZE_NONE) {
5184 UChar *low, *high, *adjrange, *sch_start;
5185 const UChar *min_range;
5186
5187 if (range < end)
5188 adjrange = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, range, end);
5189 else
5190 adjrange = (UChar* )end;
5191
5192 if ((OnigDistance)(end - range) > reg->dmin)
5193 min_range = range + reg->dmin;
5194 else
5195 min_range = end;
5196
5197 if (reg->dmax != ONIG_INFINITE_DISTANCE &&
5198 end - range >= reg->threshold_len) {
5199 do {
5200 if ((OnigDistance)(end - s) > reg->dmax)
5201 sch_start = s + reg->dmax;
5202 else
5203 sch_start = (UChar* )end;
5204
5205 if (backward_search_range(reg, str, end, sch_start, min_range, adjrange,
5206 &low, &high) <= 0)
5207 goto mismatch;
5208
5209 if (s > high)
5210 s = high;
5211
5212 while (s >= low) {
5213 prev = onigenc_get_prev_char_head(reg->enc, str, s, end);
5214 MATCH_AND_RETURN_CHECK(orig_start);
5215 s = prev;
5216 }
5217 } while (s >= range);
5218 goto mismatch;
5219 }
5220 else { /* check only. */
5221 if (end - range < reg->threshold_len) goto mismatch;
5222
5223 if (reg->dmax != 0) {
5224 if (reg->dmax == ONIG_INFINITE_DISTANCE)
5225 sch_start = (UChar* )end;
5226 else {
5227 if ((OnigDistance)(end - s) > reg->dmax) {
5228 sch_start = s + reg->dmax;
5229 sch_start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc,
5230 start, sch_start, end);
5231 } else
5232 sch_start = (UChar* )end;
5233 }
5234 }
5235 else
5236 sch_start = (UChar* )s;
5237
5238 if (backward_search_range(reg, str, end, sch_start, min_range, adjrange,
5239 &low, &high) <= 0) goto mismatch;
5240 }
5241 }
5242
5243 do {
5244 prev = onigenc_get_prev_char_head(reg->enc, str, s, end);
5245 MATCH_AND_RETURN_CHECK(orig_start);
5246 s = prev;
5247 } while (s >= range);
5248 }
5249
5250 mismatch:
5251#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
5252 if (IS_FIND_LONGEST(reg->options)) {
5253 if (msa.best_len >= 0) {
5254 s = msa.best_s;
5255 goto match;
5256 }
5257 }
5258#endif
5259 r = ONIG_MISMATCH;
5260
5261 finish:
5262 MATCH_ARG_FREE(msa);
5263
5264 /* If result is mismatch and no FIND_NOT_EMPTY option,
5265 then the region is not set in match_at(). */
5266 if (IS_FIND_NOT_EMPTY(reg->options) && region) {
5267 onig_region_clear(region);
5268 }
5269
5270#ifdef ONIG_DEBUG
5271 if (r != ONIG_MISMATCH)
5272 fprintf(stderr, "onig_search: error %"PRIdPTRDIFF"\n", r);
5273#endif
5274 return r;
5275
5276 mismatch_no_msa:
5277 r = ONIG_MISMATCH;
5278 finish_no_msa:
5279#ifdef ONIG_DEBUG
5280 if (r != ONIG_MISMATCH)
5281 fprintf(stderr, "onig_search: error %"PRIdPTRDIFF"\n", r);
5282#endif
5283 return r;
5284
5285 match:
5286 MATCH_ARG_FREE(msa);
5287 return s - str;
5288
5289timeout:
5290 MATCH_ARG_FREE(msa);
5291 return ONIGERR_TIMEOUT;
5292}
5293
5294extern OnigPosition
5295onig_scan(regex_t* reg, const UChar* str, const UChar* end,
5296 OnigRegion* region, OnigOptionType option,
5297 int (*scan_callback)(OnigPosition, OnigPosition, OnigRegion*, void*),
5298 void* callback_arg)
5299{
5300 OnigPosition r;
5301 OnigPosition n;
5302 int rs;
5303 const UChar* start;
5304
5305 n = 0;
5306 start = str;
5307 while (1) {
5308 r = onig_search(reg, str, end, start, end, region, option);
5309 if (r >= 0) {
5310 rs = scan_callback(n, r, region, callback_arg);
5311 n++;
5312 if (rs != 0)
5313 return rs;
5314
5315 if (region->end[0] == start - str) {
5316 if (start >= end) break;
5317 start += enclen(reg->enc, start, end);
5318 }
5319 else
5320 start = str + region->end[0];
5321
5322 if (start > end)
5323 break;
5324 }
5325 else if (r == ONIG_MISMATCH) {
5326 break;
5327 }
5328 else { /* error */
5329 return r;
5330 }
5331 }
5332
5333 return n;
5334}
5335
5336extern OnigEncoding
5337onig_get_encoding(const regex_t* reg)
5338{
5339 return reg->enc;
5340}
5341
5342extern OnigOptionType
5343onig_get_options(const regex_t* reg)
5344{
5345 return reg->options;
5346}
5347
5348extern OnigCaseFoldType
5349onig_get_case_fold_flag(const regex_t* reg)
5350{
5351 return reg->case_fold_flag;
5352}
5353
5354extern const OnigSyntaxType*
5355onig_get_syntax(const regex_t* reg)
5356{
5357 return reg->syntax;
5358}
5359
5360extern int
5361onig_number_of_captures(const regex_t* reg)
5362{
5363 return reg->num_mem;
5364}
5365
5366extern int
5367onig_number_of_capture_histories(const regex_t* reg)
5368{
5369#ifdef USE_CAPTURE_HISTORY
5370 int i, n;
5371
5372 n = 0;
5373 for (i = 0; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
5374 if (BIT_STATUS_AT(reg->capture_history, i) != 0)
5375 n++;
5376 }
5377 return n;
5378#else
5379 return 0;
5380#endif
5381}
5382
5383extern void
5384onig_copy_encoding(OnigEncodingType *to, OnigEncoding from)
5385{
5386 *to = *from;
5387}
#define RB_GNUC_EXTENSION
This is expanded to nothing for non-GCC compilers.
Definition defines.h:89
#define xfree
Old name of ruby_xfree.
Definition xmalloc.h:58
#define xrealloc
Old name of ruby_xrealloc.
Definition xmalloc.h:56
#define xmalloc
Old name of ruby_xmalloc.
Definition xmalloc.h:53
int len
Length of the buffer.
Definition io.h:8
Definition win32.h:676