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