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