1 /**********************************************************************
2 regexec.c - Onigmo (Oniguruma-mod) (regular expression library)
3 **********************************************************************/
5 * Copyright (c) 2002-2008 K.Kosako <sndgk393 AT ybb DOT ne DOT jp>
6 * Copyright (c) 2011-2016 K.Takata <kentkt AT csc DOT jp>
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
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.
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
34 # undef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
36 # define USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
39 #ifndef USE_TOKEN_THREADED_VM
41 # define USE_TOKEN_THREADED_VM 1
43 # define USE_TOKEN_THREADED_VM 0
48 # define ENC_DUMMY_FLAG (1<<24)
50 rb_enc_asciicompat(OnigEncoding enc
)
52 return ONIGENC_MBC_MINLEN(enc
)==1 && !((enc
)->ruby_encoding_index
& ENC_DUMMY_FLAG
);
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))
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))
68 is_mbc_newline_ex(OnigEncoding enc
, const UChar
*p
, const UChar
*start
,
69 const UChar
*end
, OnigOptionType option
, int check_prev
)
71 if (IS_NEWLINE_CRLF(option
)) {
72 if (ONIGENC_MBC_TO_CODE(enc
, p
, end
) == 0x0a) {
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)
84 const UChar
*pnext
= p
+ enclen(enc
, p
, end
);
86 ONIGENC_MBC_TO_CODE(enc
, p
, end
) == 0x0d &&
87 ONIGENC_MBC_TO_CODE(enc
, pnext
, end
) == 0x0a)
89 if (ONIGENC_IS_MBC_NEWLINE(enc
, p
, end
))
95 return ONIGENC_IS_MBC_NEWLINE(enc
, p
, end
);
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 */
103 #ifdef USE_CAPTURE_HISTORY
104 static void history_tree_free(OnigCaptureTreeNode
* node
);
107 history_tree_clear(OnigCaptureTreeNode
* node
)
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
]);
117 for (i
= 0; i
< node
->allocated
; i
++) {
118 node
->childs
[i
] = (OnigCaptureTreeNode
* )0;
120 node
->num_childs
= 0;
121 node
->beg
= ONIG_REGION_NOTPOS
;
122 node
->end
= ONIG_REGION_NOTPOS
;
125 node
->childs
= (OnigCaptureTreeNode
** )0;
130 history_tree_free(OnigCaptureTreeNode
* node
)
132 history_tree_clear(node
);
137 history_root_free(OnigRegion
* r
)
139 if (IS_NOT_NULL(r
->history_root
)) {
140 history_tree_free(r
->history_root
);
141 r
->history_root
= (OnigCaptureTreeNode
* )0;
145 static OnigCaptureTreeNode
*
146 history_node_new(void)
148 OnigCaptureTreeNode
* node
;
150 node
= (OnigCaptureTreeNode
* )xmalloc(sizeof(OnigCaptureTreeNode
));
151 CHECK_NULL_RETURN(node
);
152 node
->childs
= (OnigCaptureTreeNode
** )0;
154 node
->num_childs
= 0;
156 node
->beg
= ONIG_REGION_NOTPOS
;
157 node
->end
= ONIG_REGION_NOTPOS
;
163 history_tree_add_child(OnigCaptureTreeNode
* parent
, OnigCaptureTreeNode
* child
)
165 # define HISTORY_TREE_INIT_ALLOC_SIZE 8
167 if (parent
->num_childs
>= parent
->allocated
) {
170 if (IS_NULL(parent
->childs
)) {
171 n
= HISTORY_TREE_INIT_ALLOC_SIZE
;
173 (OnigCaptureTreeNode
** )xmalloc(sizeof(OnigCaptureTreeNode
*) * n
);
174 CHECK_NULL_RETURN_MEMERR(parent
->childs
);
177 OnigCaptureTreeNode
** tmp
;
178 n
= parent
->allocated
* 2;
180 (OnigCaptureTreeNode
** )xrealloc(parent
->childs
,
181 sizeof(OnigCaptureTreeNode
*) * n
);
183 history_tree_clear(parent
);
184 return ONIGERR_MEMORY
;
186 parent
->childs
= tmp
;
188 for (i
= parent
->allocated
; i
< n
; i
++) {
189 parent
->childs
[i
] = (OnigCaptureTreeNode
* )0;
191 parent
->allocated
= n
;
194 parent
->childs
[parent
->num_childs
] = child
;
195 parent
->num_childs
++;
199 static OnigCaptureTreeNode
*
200 history_tree_clone(OnigCaptureTreeNode
* node
)
203 OnigCaptureTreeNode
*clone
, *child
;
205 clone
= history_node_new();
206 CHECK_NULL_RETURN(clone
);
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;
216 r
= history_tree_add_child(clone
, child
);
218 history_tree_free(child
);
219 history_tree_free(clone
);
220 return (OnigCaptureTreeNode
* )0;
227 extern OnigCaptureTreeNode
*
228 onig_get_capture_tree(OnigRegion
* region
)
230 return region
->history_root
;
232 #endif /* USE_CAPTURE_HISTORY */
234 #ifdef USE_MATCH_CACHE
237 Glossary for "match cache"
239 "match cache" or "match cache optimization"
240 The `Regexp#match` optimization by using a cache.
243 A cachable opcode (e.g. `OP_PUSH`, `OP_REPEAT`, etc).
244 It is corresponding to some cache points.
247 A cachable point on matching.
248 Usually, one-to-one corresponding between a cache opcode and a cache point exists,
249 but cache opcodes between `OP_REPEAT` and `OP_REPEAT_INC` have some corresponding
250 cache points depending on repetition counts.
253 A pair of a cache point and a position on an input string.
254 We 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"
258 A bit-array for memoizing (recording) match cache points once backtracked.
261 static OnigPosition
count_num_cache_opcodes_inner(
263 MemNumType current_repeat_mem
, int lookaround_nesting
,
264 UChar
** pp
, long* num_cache_opcodes_ptr
268 UChar
* pend
= reg
->p
+ reg
->used
;
270 MemNumType repeat_mem
;
271 OnigEncoding enc
= reg
->enc
;
272 long num_cache_opcodes
= *num_cache_opcodes_ptr
;
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;
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;
292 GET_LENGTH_INC(len
, p
); p
+= len
* 2; break;
294 GET_LENGTH_INC(len
, p
); p
+= len
* 3; break;
298 GET_LENGTH_INC(mb_len
, p
);
299 GET_LENGTH_INC(len
, p
);
305 len
= enclen(enc
, p
, pend
); p
+= len
; break;
307 GET_LENGTH_INC(len
, p
); p
+= len
; break;
311 p
+= SIZE_BITSET
; break;
313 case OP_CCLASS_MB_NOT
:
314 GET_LENGTH_INC(len
, p
); p
+= len
; break;
316 case OP_CCLASS_MIX_NOT
:
318 GET_LENGTH_INC(len
, p
);
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;
335 case OP_NOT_WORD_BOUND
:
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
:
352 case OP_SEMI_END_BUF
:
353 case OP_BEGIN_POSITION
:
360 case OP_BACKREF_MULTI
:
361 case OP_BACKREF_MULTI_IC
:
362 case OP_BACKREF_WITH_LEVEL
:
365 case OP_MEMORY_START
:
366 case OP_MEMORY_START_PUSH
:
367 case OP_MEMORY_END_PUSH
:
368 case OP_MEMORY_END_PUSH_REC
:
370 case OP_MEMORY_END_REC
:
372 // A memory (capture) in look-around is found.
373 if (lookaround_nesting
!= 0) {
392 case OP_PUSH_OR_JUMP_EXACT1
:
393 case OP_PUSH_IF_PEEK_NEXT
:
394 p
+= SIZE_RELADDR
+ 1; num_cache_opcodes
++; break;
397 if (current_repeat_mem
!= -1) {
398 // A nested OP_REPEAT is not yet supported.
401 GET_MEMNUM_INC(repeat_mem
, p
);
403 if (reg
->repeat_range
[repeat_mem
].lower
== 0) {
406 result
= count_num_cache_opcodes_inner(reg
, repeat_mem
, lookaround_nesting
, &p
, &num_cache_opcodes
);
407 if (result
< 0 || num_cache_opcodes
< 0) {
411 OnigRepeatRange
*repeat_range
= ®
->repeat_range
[repeat_mem
];
412 if (repeat_range
->lower
< repeat_range
->upper
) {
418 case OP_REPEAT_INC_NG
:
419 GET_MEMNUM_INC(repeat_mem
, p
);
420 if (repeat_mem
!= current_repeat_mem
) {
421 // A lone or invalid OP_REPEAT_INC is found.
425 case OP_REPEAT_INC_SG
:
426 case OP_REPEAT_INC_NG_SG
:
428 case OP_NULL_CHECK_START
:
431 case OP_NULL_CHECK_END
:
432 case OP_NULL_CHECK_END_MEMST_PUSH
:
435 case OP_NULL_CHECK_END_MEMST
:
440 if (lookaround_nesting
< 0) {
441 // A look-around nested in a atomic grouping is found.
444 result
= count_num_cache_opcodes_inner(reg
, current_repeat_mem
, lookaround_nesting
+ 1, &p
, &num_cache_opcodes
);
445 if (result
< 0 || num_cache_opcodes
< 0) {
449 case OP_PUSH_POS_NOT
:
450 if (lookaround_nesting
< 0) {
451 // A look-around nested in a atomic grouping is found.
455 result
= count_num_cache_opcodes_inner(reg
, current_repeat_mem
, lookaround_nesting
+ 1, &p
, &num_cache_opcodes
);
456 if (result
< 0 || num_cache_opcodes
< 0) {
460 case OP_PUSH_LOOK_BEHIND_NOT
:
461 if (lookaround_nesting
< 0) {
462 // A look-around nested in a atomic grouping is found.
467 result
= count_num_cache_opcodes_inner(reg
, current_repeat_mem
, lookaround_nesting
+ 1, &p
, &num_cache_opcodes
);
468 if (result
< 0 || num_cache_opcodes
< 0) {
472 case OP_PUSH_STOP_BT
:
473 if (lookaround_nesting
!= 0) {
474 // A nested atomic grouping is found.
477 result
= count_num_cache_opcodes_inner(reg
, current_repeat_mem
, -1, &p
, &num_cache_opcodes
);
478 if (result
< 0 || num_cache_opcodes
< 0) {
484 case OP_FAIL_LOOK_BEHIND_NOT
:
491 case OP_PUSH_ABSENT_POS
:
503 case OP_STATE_CHECK_PUSH
:
504 case OP_STATE_CHECK_PUSH_OR_JUMP
:
506 case OP_STATE_CHECK_ANYCHAR_STAR
:
507 case OP_STATE_CHECK_ANYCHAR_ML_STAR
:
510 case OP_SET_OPTION_PUSH
:
522 *num_cache_opcodes_ptr
= num_cache_opcodes
;
526 *num_cache_opcodes_ptr
= num_cache_opcodes
;
530 *num_cache_opcodes_ptr
= NUM_CACHE_OPCODES_IMPOSSIBLE
;
534 return ONIGERR_UNDEFINED_BYTECODE
;
537 /* count the total number of cache opcodes for allocating a match cache buffer. */
539 count_num_cache_opcodes(const regex_t
* reg
, long* num_cache_opcodes_ptr
)
542 *num_cache_opcodes_ptr
= 0;
543 OnigPosition result
= count_num_cache_opcodes_inner(reg
, -1, 0, &p
, num_cache_opcodes_ptr
);
544 if (result
== 0 && *num_cache_opcodes_ptr
>= 0 && p
!= reg
->p
+ reg
->used
) {
545 return ONIGERR_UNDEFINED_BYTECODE
;
552 init_cache_opcodes_inner(
554 MemNumType current_repeat_mem
, int lookaround_nesting
,
555 OnigCacheOpcode
** cache_opcodes_ptr
, UChar
** pp
, long* num_cache_points_ptr
559 UChar
* pend
= reg
->p
+ reg
->used
;
562 MemNumType repeat_mem
;
563 OnigEncoding enc
= reg
->enc
;
564 long cache_point
= *num_cache_points_ptr
;
565 OnigCacheOpcode
*cache_opcodes
= *cache_opcodes_ptr
;
568 # define INC_CACHE_OPCODES do {\
569 cache_opcodes->addr = pbegin;\
570 cache_opcodes->cache_point = cache_point;\
571 cache_opcodes->outer_repeat_mem = current_repeat_mem;\
572 cache_opcodes->num_cache_points_at_outer_repeat = 0;\
573 cache_opcodes->num_cache_points_in_outer_repeat = 0;\
574 cache_opcodes->lookaround_nesting = lookaround_nesting;\
575 cache_opcodes->match_addr = NULL;\
576 cache_point += lookaround_nesting != 0 ? 2 : 1;\
587 case OP_EXACT1
: p
++; break;
588 case OP_EXACT2
: p
+= 2; break;
589 case OP_EXACT3
: p
+= 3; break;
590 case OP_EXACT4
: p
+= 4; break;
591 case OP_EXACT5
: p
+= 5; break;
593 GET_LENGTH_INC(len
, p
); p
+= len
; break;
594 case OP_EXACTMB2N1
: p
+= 2; break;
595 case OP_EXACTMB2N2
: p
+= 4; break;
596 case OP_EXACTMB2N3
: p
+= 6; break;
598 GET_LENGTH_INC(len
, p
); p
+= len
* 2; break;
600 GET_LENGTH_INC(len
, p
); p
+= len
* 3; break;
604 GET_LENGTH_INC(mb_len
, p
);
605 GET_LENGTH_INC(len
, p
);
611 len
= enclen(enc
, p
, pend
); p
+= len
; break;
613 GET_LENGTH_INC(len
, p
); p
+= len
; break;
617 p
+= SIZE_BITSET
; break;
619 case OP_CCLASS_MB_NOT
:
620 GET_LENGTH_INC(len
, p
); p
+= len
; break;
622 case OP_CCLASS_MIX_NOT
:
624 GET_LENGTH_INC(len
, p
);
631 case OP_ANYCHAR_STAR
:
632 case OP_ANYCHAR_ML_STAR
:
635 case OP_ANYCHAR_STAR_PEEK_NEXT
:
636 case OP_ANYCHAR_ML_STAR_PEEK_NEXT
:
644 case OP_NOT_WORD_BOUND
:
650 case OP_NOT_ASCII_WORD
:
651 case OP_ASCII_WORD_BOUND
:
652 case OP_NOT_ASCII_WORD_BOUND
:
653 case OP_ASCII_WORD_BEGIN
:
654 case OP_ASCII_WORD_END
:
661 case OP_SEMI_END_BUF
:
662 case OP_BEGIN_POSITION
:
669 case OP_BACKREF_MULTI
:
670 case OP_BACKREF_MULTI_IC
:
671 case OP_BACKREF_WITH_LEVEL
:
672 goto unexpected_bytecode_error
;
674 case OP_MEMORY_START
:
675 case OP_MEMORY_START_PUSH
:
676 case OP_MEMORY_END_PUSH
:
677 case OP_MEMORY_END_PUSH_REC
:
679 case OP_MEMORY_END_REC
:
681 if (lookaround_nesting
!= 0) {
682 goto unexpected_bytecode_error
;
700 case OP_PUSH_OR_JUMP_EXACT1
:
701 case OP_PUSH_IF_PEEK_NEXT
:
702 p
+= SIZE_RELADDR
+ 1;
707 GET_MEMNUM_INC(repeat_mem
, p
);
709 if (reg
->repeat_range
[repeat_mem
].lower
== 0) {
713 long num_cache_points_in_repeat
= 0;
714 long num_cache_points_at_repeat
= cache_point
;
715 OnigCacheOpcode
* cache_opcodes_in_repeat
= cache_opcodes
;
716 result
= init_cache_opcodes_inner(reg
, repeat_mem
, lookaround_nesting
, &cache_opcodes
, &p
, &num_cache_points_in_repeat
);
720 OnigRepeatRange
*repeat_range
= ®
->repeat_range
[repeat_mem
];
721 if (repeat_range
->lower
< repeat_range
->upper
) {
723 cache_point
-= lookaround_nesting
!= 0 ? 2 : 1;
725 int repeat_bounds
= repeat_range
->upper
== 0x7fffffff ? 1 : repeat_range
->upper
- repeat_range
->lower
;
726 cache_point
+= num_cache_points_in_repeat
* repeat_range
->lower
+ (num_cache_points_in_repeat
+ (lookaround_nesting
!= 0 ? 2 : 1)) * repeat_bounds
;
727 for (; cache_opcodes_in_repeat
< cache_opcodes
; cache_opcodes_in_repeat
++) {
728 cache_opcodes_in_repeat
->num_cache_points_at_outer_repeat
= num_cache_points_at_repeat
;
729 cache_opcodes_in_repeat
->num_cache_points_in_outer_repeat
= num_cache_points_in_repeat
;
734 case OP_REPEAT_INC_NG
:
737 case OP_REPEAT_INC_SG
:
738 case OP_REPEAT_INC_NG_SG
:
739 goto unexpected_bytecode_error
;
740 case OP_NULL_CHECK_START
:
743 case OP_NULL_CHECK_END
:
744 case OP_NULL_CHECK_END_MEMST_PUSH
:
747 case OP_NULL_CHECK_END_MEMST
:
754 OnigCacheOpcode
* cache_opcodes_in_lookaround
= cache_opcodes
;
755 result
= init_cache_opcodes_inner(reg
, current_repeat_mem
, lookaround_nesting
+ 1, &cache_opcodes
, &p
, &cache_point
);
759 UChar
* match_addr
= p
- 1;
760 for (; cache_opcodes_in_lookaround
< cache_opcodes
; cache_opcodes_in_lookaround
++) {
761 if (cache_opcodes_in_lookaround
->match_addr
== NULL
) {
762 cache_opcodes_in_lookaround
->match_addr
= match_addr
;
767 case OP_PUSH_POS_NOT
:
770 case OP_PUSH_LOOK_BEHIND_NOT
:
774 case OP_PUSH_STOP_BT
:
776 OnigCacheOpcode
* cache_opcodes_in_atomic
= cache_opcodes
;
777 result
= init_cache_opcodes_inner(reg
, current_repeat_mem
, -1, &cache_opcodes
, &p
, &cache_point
);
781 UChar
* match_addr
= p
- 1;
782 for (; cache_opcodes_in_atomic
< cache_opcodes
; cache_opcodes_in_atomic
++) {
783 if (cache_opcodes_in_atomic
->match_addr
== NULL
) {
784 cache_opcodes_in_atomic
->match_addr
= match_addr
;
791 case OP_FAIL_LOOK_BEHIND_NOT
:
800 goto unexpected_bytecode_error
;
804 goto unexpected_bytecode_error
;
807 goto unexpected_bytecode_error
;
809 case OP_STATE_CHECK_PUSH
:
810 case OP_STATE_CHECK_PUSH_OR_JUMP
:
812 case OP_STATE_CHECK_ANYCHAR_STAR
:
813 case OP_STATE_CHECK_ANYCHAR_ML_STAR
:
814 goto unexpected_bytecode_error
;
816 case OP_SET_OPTION_PUSH
:
827 *cache_opcodes_ptr
= cache_opcodes
;
829 *num_cache_points_ptr
= cache_point
;
835 unexpected_bytecode_error
:
836 return ONIGERR_UNEXPECTED_BYTECODE
;
839 return ONIGERR_UNDEFINED_BYTECODE
;
842 /* collect cache opcodes from the given regex program, and compute the total number of cache points. */
844 init_cache_opcodes(const regex_t
* reg
, OnigCacheOpcode
* cache_opcodes_ptr
, long* num_cache_points_ptr
)
847 *num_cache_points_ptr
= 0;
848 OnigPosition result
= init_cache_opcodes_inner(reg
, -1, 0, &cache_opcodes_ptr
, &p
, num_cache_points_ptr
);
849 if (result
== 0 && p
!= reg
->p
+ reg
->used
) {
850 return ONIGERR_UNDEFINED_BYTECODE
;
857 count_num_cache_opcodes(regex_t
* reg
, long* num_cache_opcodes
)
859 *num_cache_opcodes
= NUM_CACHE_OPCODES_IMPOSSIBLE
;
862 #endif /* USE_MATCH_CACHE */
865 onig_check_linear_time(OnigRegexType
* reg
)
867 long num_cache_opcodes
= 0;
868 count_num_cache_opcodes(reg
, &num_cache_opcodes
);
869 return num_cache_opcodes
!= NUM_CACHE_OPCODES_IMPOSSIBLE
;
873 onig_region_clear(OnigRegion
* region
)
877 for (i
= 0; i
< region
->num_regs
; i
++) {
878 region
->beg
[i
] = region
->end
[i
] = ONIG_REGION_NOTPOS
;
880 #ifdef USE_CAPTURE_HISTORY
881 history_root_free(region
);
886 onig_region_resize(OnigRegion
* region
, int n
)
888 region
->num_regs
= n
;
890 if (n
< ONIG_NREGION
)
893 if (region
->allocated
== 0) {
894 region
->beg
= (OnigPosition
* )xmalloc(n
* sizeof(OnigPosition
));
895 if (region
->beg
== 0)
896 return ONIGERR_MEMORY
;
898 region
->end
= (OnigPosition
* )xmalloc(n
* sizeof(OnigPosition
));
899 if (region
->end
== 0) {
901 return ONIGERR_MEMORY
;
904 region
->allocated
= n
;
906 else if (region
->allocated
< n
) {
909 region
->allocated
= 0;
910 tmp
= (OnigPosition
* )xrealloc(region
->beg
, n
* sizeof(OnigPosition
));
914 return ONIGERR_MEMORY
;
917 tmp
= (OnigPosition
* )xrealloc(region
->end
, n
* sizeof(OnigPosition
));
921 return ONIGERR_MEMORY
;
925 region
->allocated
= n
;
932 onig_region_resize_clear(OnigRegion
* region
, int n
)
936 r
= onig_region_resize(region
, n
);
937 if (r
!= 0) return r
;
938 onig_region_clear(region
);
943 onig_region_set(OnigRegion
* region
, int at
, int beg
, int end
)
945 if (at
< 0) return ONIGERR_INVALID_ARGUMENT
;
947 if (at
>= region
->allocated
) {
948 int r
= onig_region_resize(region
, at
+ 1);
952 region
->beg
[at
] = beg
;
953 region
->end
[at
] = end
;
958 onig_region_init(OnigRegion
* region
)
960 region
->num_regs
= 0;
961 region
->allocated
= 0;
962 region
->beg
= (OnigPosition
* )0;
963 region
->end
= (OnigPosition
* )0;
964 #ifdef USE_CAPTURE_HISTORY
965 region
->history_root
= (OnigCaptureTreeNode
* )0;
970 onig_region_new(void)
974 r
= (OnigRegion
* )xmalloc(sizeof(OnigRegion
));
981 onig_region_free(OnigRegion
* r
, int free_self
)
984 if (r
->allocated
> 0) {
988 #ifdef USE_CAPTURE_HISTORY
989 history_root_free(r
);
995 memset(r
, 0, sizeof(OnigRegion
));
1001 onig_region_copy(OnigRegion
* to
, const OnigRegion
* from
)
1003 #define RREGC_SIZE (sizeof(int) * from->num_regs)
1006 if (to
== from
) return;
1008 r
= onig_region_resize(to
, from
->num_regs
);
1011 for (i
= 0; i
< from
->num_regs
; i
++) {
1012 to
->beg
[i
] = from
->beg
[i
];
1013 to
->end
[i
] = from
->end
[i
];
1015 to
->num_regs
= from
->num_regs
;
1017 #ifdef USE_CAPTURE_HISTORY
1018 history_root_free(to
);
1020 if (IS_NOT_NULL(from
->history_root
)) {
1021 to
->history_root
= history_tree_clone(from
->history_root
);
1028 #define INVALID_STACK_INDEX -1
1031 /* used by normal-POP */
1032 #define STK_ALT 0x0001
1033 #define STK_LOOK_BEHIND_NOT 0x0002
1034 #define STK_POS_NOT 0x0003
1035 /* handled by normal-POP */
1036 #define STK_MEM_START 0x0100
1037 #define STK_MEM_END 0x8200
1038 #define STK_REPEAT_INC 0x0300
1039 #define STK_STATE_CHECK_MARK 0x1000
1040 /* avoided by normal-POP */
1041 #define STK_NULL_CHECK_START 0x3000
1042 #define STK_NULL_CHECK_END 0x5000 /* for recursive call */
1043 #define STK_MEM_END_MARK 0x8400
1044 #define STK_POS 0x0500 /* used when POP-POS */
1045 #define STK_STOP_BT 0x0600 /* mark for "(?>...)" */
1046 #define STK_REPEAT 0x0700
1047 #define STK_CALL_FRAME 0x0800
1048 #define STK_RETURN 0x0900
1049 #define STK_VOID 0x0a00 /* for fill a blank */
1050 #define STK_ABSENT_POS 0x0b00 /* for absent */
1051 #define STK_ABSENT 0x0c00 /* absent inner loop marker */
1052 #define STK_MATCH_CACHE_POINT 0x0d00 /* for the match cache optimization */
1053 #define STK_ATOMIC_MATCH_CACHE_POINT 0x0e00
1055 /* stack type check mask */
1056 #define STK_MASK_POP_USED 0x00ff
1057 #define STK_MASK_TO_VOID_TARGET 0x10ff
1058 #define STK_MASK_MEM_END_OR_MARK 0x8000 /* MEM_END or MEM_END_MARK */
1060 #ifdef USE_MATCH_CACHE
1061 #define MATCH_ARG_INIT_MATCH_CACHE(msa) do {\
1062 (msa).match_cache_status = MATCH_CACHE_STATUS_UNINIT;\
1063 (msa).num_fails = 0;\
1064 (msa).num_cache_opcodes = NUM_CACHE_OPCODES_UNINIT;\
1065 (msa).cache_opcodes = (OnigCacheOpcode*)NULL;\
1066 (msa).num_cache_points = 0;\
1067 (msa).match_cache_buf = (uint8_t*)NULL;\
1069 #define MATCH_ARG_FREE_MATCH_CACHE(msa) do {\
1070 xfree((msa).cache_opcodes);\
1071 xfree((msa).match_cache_buf);\
1072 (msa).cache_opcodes = (OnigCacheOpcode*)NULL;\
1073 (msa).match_cache_buf = (uint8_t*)NULL;\
1076 #define MATCH_ARG_INIT_MATCH_CACHE(msa)
1077 #define MATCH_ARG_FREE_MATCH_CACHE(msa)
1080 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
1081 # define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start, arg_gpos) do {\
1082 (msa).stack_p = (void* )0;\
1083 (msa).options = (arg_option);\
1084 (msa).region = (arg_region);\
1085 (msa).start = (arg_start);\
1086 (msa).gpos = (arg_gpos);\
1087 (msa).best_len = ONIG_MISMATCH;\
1089 (msa).end_time = 0;\
1090 MATCH_ARG_INIT_MATCH_CACHE(msa);\
1093 # define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start, arg_gpos) do {\
1094 (msa).stack_p = (void* )0;\
1095 (msa).options = (arg_option);\
1096 (msa).region = (arg_region);\
1097 (msa).start = (arg_start);\
1098 (msa).gpos = (arg_gpos);\
1100 (msa).end_time = 0;\
1101 MATCH_ARG_INIT_MATCH_CACHE(msa);\
1105 #ifdef USE_COMBINATION_EXPLOSION_CHECK
1107 # define STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE 16
1109 # define STATE_CHECK_BUFF_INIT(msa, str_len, offset, state_num) do { \
1110 if ((state_num) > 0 && str_len >= STATE_CHECK_STRING_THRESHOLD_LEN) {\
1111 unsigned int size = (unsigned int )(((str_len) + 1) * (state_num) + 7) >> 3;\
1112 offset = ((offset) * (state_num)) >> 3;\
1113 if (size > 0 && offset < size && size < STATE_CHECK_BUFF_MAX_SIZE) {\
1114 if (size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) {\
1115 (msa).state_check_buff = (void* )xmalloc(size);\
1116 CHECK_NULL_RETURN_MEMERR((msa).state_check_buff);\
1119 (msa).state_check_buff = (void* )xalloca(size);\
1120 xmemset(((char* )((msa).state_check_buff)+(offset)), 0, \
1121 (size_t )(size - (offset))); \
1122 (msa).state_check_buff_size = size;\
1125 (msa).state_check_buff = (void* )0;\
1126 (msa).state_check_buff_size = 0;\
1130 (msa).state_check_buff = (void* )0;\
1131 (msa).state_check_buff_size = 0;\
1135 # define MATCH_ARG_FREE(msa) do {\
1136 xfree((msa).stack_p);\
1137 if ((msa).state_check_buff_size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) { \
1138 xfree((msa).state_check_buff);\
1140 MATCH_ARG_FREE_MATCH_CACHE(msa);\
1142 #else /* USE_COMBINATION_EXPLOSION_CHECK */
1143 # define MATCH_ARG_FREE(msa) do {\
1144 xfree((msa).stack_p);\
1145 MATCH_ARG_FREE_MATCH_CACHE(msa);\
1147 #endif /* USE_COMBINATION_EXPLOSION_CHECK */
1151 #define MAX_PTR_NUM 100
1153 #define STACK_INIT(alloc_addr, heap_addr, ptr_num, stack_num) do {\
1154 if (ptr_num > MAX_PTR_NUM) {\
1155 alloc_addr = (char* )xmalloc(sizeof(OnigStackIndex) * (ptr_num));\
1156 heap_addr = alloc_addr;\
1157 if (msa->stack_p) {\
1158 stk_alloc = (OnigStackType* )(msa->stack_p);\
1159 stk_base = stk_alloc;\
1161 stk_end = stk_base + msa->stack_n;\
1163 stk_alloc = (OnigStackType* )xalloca(sizeof(OnigStackType) * (stack_num));\
1164 stk_base = stk_alloc;\
1166 stk_end = stk_base + (stack_num);\
1168 } else if (msa->stack_p) {\
1169 alloc_addr = (char* )xalloca(sizeof(OnigStackIndex) * (ptr_num));\
1171 stk_alloc = (OnigStackType* )(msa->stack_p);\
1172 stk_base = stk_alloc;\
1174 stk_end = stk_base + msa->stack_n;\
1177 alloc_addr = (char* )xalloca(sizeof(OnigStackIndex) * (ptr_num)\
1178 + sizeof(OnigStackType) * (stack_num));\
1180 stk_alloc = (OnigStackType* )(alloc_addr + sizeof(OnigStackIndex) * (ptr_num));\
1181 stk_base = stk_alloc;\
1183 stk_end = stk_base + (stack_num);\
1187 #define STACK_SAVE do{\
1188 if (stk_base != stk_alloc) {\
1189 msa->stack_p = stk_base;\
1190 msa->stack_n = stk_end - stk_base; /* TODO: check overflow */\
1194 static unsigned int MatchStackLimitSize
= DEFAULT_MATCH_STACK_LIMIT_SIZE
;
1197 onig_get_match_stack_limit_size(void)
1199 return MatchStackLimitSize
;
1203 onig_set_match_stack_limit_size(unsigned int size
)
1205 MatchStackLimitSize
= size
;
1210 stack_double(OnigStackType
** arg_stk_base
, OnigStackType
** arg_stk_end
,
1211 OnigStackType
** arg_stk
, OnigStackType
* stk_alloc
, OnigMatchArg
* msa
)
1214 OnigStackType
*x
, *stk_base
, *stk_end
, *stk
;
1216 stk_base
= *arg_stk_base
;
1217 stk_end
= *arg_stk_end
;
1220 n
= stk_end
- stk_base
;
1221 if (stk_base
== stk_alloc
&& IS_NULL(msa
->stack_p
)) {
1222 x
= (OnigStackType
* )xmalloc(sizeof(OnigStackType
) * n
* 2);
1225 return ONIGERR_MEMORY
;
1227 xmemcpy(x
, stk_base
, n
* sizeof(OnigStackType
));
1231 unsigned int limit_size
= MatchStackLimitSize
;
1233 if (limit_size
!= 0 && n
> limit_size
) {
1234 if ((unsigned int )(stk_end
- stk_base
) == limit_size
)
1235 return ONIGERR_MATCH_STACK_LIMIT_OVER
;
1239 x
= (OnigStackType
* )xrealloc(stk_base
, sizeof(OnigStackType
) * n
);
1242 return ONIGERR_MEMORY
;
1245 *arg_stk
= x
+ (stk
- stk_base
);
1247 *arg_stk_end
= x
+ n
;
1251 #define STACK_ENSURE(n) do {\
1252 if (stk_end - stk < (n)) {\
1253 int r = stack_double(&stk_base, &stk_end, &stk, stk_alloc, msa);\
1256 xfree(xmalloc_base);\
1262 #define STACK_AT(index) (stk_base + (index))
1263 #define GET_STACK_INDEX(stk) ((stk) - stk_base)
1265 #define STACK_PUSH_TYPE(stack_type) do {\
1267 stk->type = (stack_type);\
1268 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1272 #define IS_TO_VOID_TARGET(stk) (((stk)->type & STK_MASK_TO_VOID_TARGET) != 0)
1274 #ifdef USE_COMBINATION_EXPLOSION_CHECK
1275 # define STATE_CHECK_POS(s,snum) \
1276 (((s) - str) * num_comb_exp_check + ((snum) - 1))
1277 # define STATE_CHECK_VAL(v,snum) do {\
1278 if (state_check_buff != NULL) {\
1279 ptrdiff_t x = STATE_CHECK_POS(s,snum);\
1280 (v) = state_check_buff[x/8] & (1<<(x%8));\
1286 # define ELSE_IF_STATE_CHECK_MARK(stk) \
1287 else if ((stk)->type == STK_STATE_CHECK_MARK) { \
1288 ptrdiff_t x = STATE_CHECK_POS(stk->u.state.pstr, stk->u.state.state_check);\
1289 state_check_buff[x/8] |= (1<<(x%8)); \
1292 # define STACK_PUSH(stack_type,pat,s,sprev,keep) do {\
1294 stk->type = (stack_type);\
1295 stk->u.state.pcode = (pat);\
1296 stk->u.state.pstr = (s);\
1297 stk->u.state.pstr_prev = (sprev);\
1298 stk->u.state.state_check = 0;\
1299 stk->u.state.pkeep = (keep);\
1303 # define STACK_PUSH_ENSURED(stack_type,pat) do {\
1304 stk->type = (stack_type);\
1305 stk->u.state.pcode = (pat);\
1306 stk->u.state.state_check = 0;\
1310 # define STACK_PUSH_ALT_WITH_STATE_CHECK(pat,s,sprev,snum,keep) do {\
1312 stk->type = STK_ALT;\
1313 stk->u.state.pcode = (pat);\
1314 stk->u.state.pstr = (s);\
1315 stk->u.state.pstr_prev = (sprev);\
1316 stk->u.state.state_check = ((state_check_buff != NULL) ? (snum) : 0);\
1317 stk->u.state.pkeep = (keep);\
1321 # define STACK_PUSH_STATE_CHECK(s,snum) do {\
1322 if (state_check_buff != NULL) {\
1324 stk->type = STK_STATE_CHECK_MARK;\
1325 stk->u.state.pstr = (s);\
1326 stk->u.state.state_check = (snum);\
1331 #else /* USE_COMBINATION_EXPLOSION_CHECK */
1333 # define ELSE_IF_STATE_CHECK_MARK(stk)
1335 # define STACK_PUSH(stack_type,pat,s,sprev,keep) do {\
1337 stk->type = (stack_type);\
1338 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1339 stk->u.state.pcode = (pat);\
1340 stk->u.state.pstr = (s);\
1341 stk->u.state.pstr_prev = (sprev);\
1342 stk->u.state.pkeep = (keep);\
1346 # define STACK_PUSH_ENSURED(stack_type,pat) do {\
1347 stk->type = (stack_type);\
1348 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1349 stk->u.state.pcode = (pat);\
1352 #endif /* USE_COMBINATION_EXPLOSION_CHECK */
1354 #define STACK_PUSH_ALT(pat,s,sprev,keep) STACK_PUSH(STK_ALT,pat,s,sprev,keep)
1355 #define STACK_PUSH_POS(s,sprev,keep) STACK_PUSH(STK_POS,NULL_UCHARP,s,sprev,keep)
1356 #define STACK_PUSH_POS_NOT(pat,s,sprev,keep) STACK_PUSH(STK_POS_NOT,pat,s,sprev,keep)
1357 #define STACK_PUSH_ABSENT STACK_PUSH_TYPE(STK_ABSENT)
1358 #define STACK_PUSH_STOP_BT STACK_PUSH_TYPE(STK_STOP_BT)
1359 #define STACK_PUSH_LOOK_BEHIND_NOT(pat,s,sprev,keep) \
1360 STACK_PUSH(STK_LOOK_BEHIND_NOT,pat,s,sprev,keep)
1362 #define STACK_PUSH_REPEAT(id, pat) do {\
1364 stk->type = STK_REPEAT;\
1365 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1366 stk->u.repeat.num = (id);\
1367 stk->u.repeat.pcode = (pat);\
1368 stk->u.repeat.count = 0;\
1372 #define STACK_PUSH_REPEAT_INC(sindex) do {\
1374 stk->type = STK_REPEAT_INC;\
1375 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1376 stk->u.repeat_inc.si = (sindex);\
1380 #define STACK_PUSH_MEM_START(mnum, s) do {\
1382 stk->type = STK_MEM_START;\
1383 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1384 stk->u.mem.num = (mnum);\
1385 stk->u.mem.pstr = (s);\
1386 stk->u.mem.start = mem_start_stk[mnum];\
1387 stk->u.mem.end = mem_end_stk[mnum];\
1388 mem_start_stk[mnum] = GET_STACK_INDEX(stk);\
1389 mem_end_stk[mnum] = INVALID_STACK_INDEX;\
1393 #define STACK_PUSH_MEM_END(mnum, s) do {\
1395 stk->type = STK_MEM_END;\
1396 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1397 stk->u.mem.num = (mnum);\
1398 stk->u.mem.pstr = (s);\
1399 stk->u.mem.start = mem_start_stk[mnum];\
1400 stk->u.mem.end = mem_end_stk[mnum];\
1401 mem_end_stk[mnum] = GET_STACK_INDEX(stk);\
1405 #define STACK_PUSH_MEM_END_MARK(mnum) do {\
1407 stk->type = STK_MEM_END_MARK;\
1408 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1409 stk->u.mem.num = (mnum);\
1413 #define STACK_GET_MEM_START(mnum, k) do {\
1416 while (k > stk_base) {\
1418 if ((k->type & STK_MASK_MEM_END_OR_MARK) != 0 \
1419 && k->u.mem.num == (mnum)) {\
1422 else if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
1423 if (level == 0) break;\
1429 #define STACK_GET_MEM_RANGE(k, mnum, start, end) do {\
1432 if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
1433 if (level == 0) (start) = k->u.mem.pstr;\
1436 else if (k->type == STK_MEM_END && k->u.mem.num == (mnum)) {\
1439 (end) = k->u.mem.pstr;\
1447 #define STACK_PUSH_NULL_CHECK_START(cnum, s) do {\
1449 stk->type = STK_NULL_CHECK_START;\
1450 stk->null_check = (OnigStackIndex)(stk - stk_base);\
1451 stk->u.null_check.num = (cnum);\
1452 stk->u.null_check.pstr = (s);\
1456 #define STACK_PUSH_NULL_CHECK_END(cnum) do {\
1458 stk->type = STK_NULL_CHECK_END;\
1459 stk->null_check = (OnigStackIndex)(stk - stk_base);\
1460 stk->u.null_check.num = (cnum);\
1464 #define STACK_PUSH_CALL_FRAME(pat) do {\
1466 stk->type = STK_CALL_FRAME;\
1467 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1468 stk->u.call_frame.ret_addr = (pat);\
1472 #define STACK_PUSH_RETURN do {\
1474 stk->type = STK_RETURN;\
1475 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1479 #define STACK_PUSH_ABSENT_POS(start, end) do {\
1481 stk->type = STK_ABSENT_POS;\
1482 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1483 stk->u.absent_pos.abs_pstr = (start);\
1484 stk->u.absent_pos.end_pstr = (end);\
1488 #define STACK_PUSH_MATCH_CACHE_POINT(match_cache_point_index, match_cache_point_mask) do {\
1490 stk->type = STK_MATCH_CACHE_POINT;\
1491 stk->null_check = stk == stk_base ? 0 : (stk-1)->null_check;\
1492 stk->u.match_cache_point.index = (match_cache_point_index);\
1493 stk->u.match_cache_point.mask = (match_cache_point_mask);\
1499 # define STACK_BASE_CHECK(p, at) \
1500 if ((p) < stk_base) {\
1501 fprintf(stderr, "at %s\n", at);\
1505 # define STACK_BASE_CHECK(p, at)
1508 #ifdef ONIG_DEBUG_MATCH_CACHE
1509 # define MATCH_CACHE_DEBUG_MEMOIZE(stkp) fprintf(stderr, "MATCH CACHE: memoize (index=%ld mask=%d)\n", stkp->u.match_cache_point.index, stkp->u.match_cache_point.mask);
1511 # define MATCH_CACHE_DEBUG_MEMOIZE(stkp) ((void) 0)
1514 #ifdef USE_MATCH_CACHE
1515 # define INC_NUM_FAILS msa->num_fails++
1516 # define MEMOIZE_MATCH_CACHE_POINT do {\
1517 if (stk->type == STK_MATCH_CACHE_POINT) {\
1518 msa->match_cache_buf[stk->u.match_cache_point.index] |= stk->u.match_cache_point.mask;\
1519 MATCH_CACHE_DEBUG_MEMOIZE(stk);\
1520 } else if (stk->type == STK_ATOMIC_MATCH_CACHE_POINT) {\
1521 memoize_extended_match_cache_point(msa->match_cache_buf, stk->u.match_cache_point.index, stk->u.match_cache_point.mask);\
1522 MATCH_CACHE_DEBUG_MEMOIZE(stkp);\
1525 # define MEMOIZE_LOOKAROUND_MATCH_CACHE_POINT(stkp) do {\
1526 if (stkp->type == STK_MATCH_CACHE_POINT) {\
1527 stkp->type = STK_VOID;\
1528 memoize_extended_match_cache_point(msa->match_cache_buf, stkp->u.match_cache_point.index, stkp->u.match_cache_point.mask);\
1529 MATCH_CACHE_DEBUG_MEMOIZE(stkp);\
1532 # define MEMOIZE_ATOMIC_MATCH_CACHE_POINT do {\
1533 if (stk->type == STK_MATCH_CACHE_POINT) {\
1534 memoize_extended_match_cache_point(msa->match_cache_buf, stk->u.match_cache_point.index, stk->u.match_cache_point.mask);\
1535 MATCH_CACHE_DEBUG_MEMOIZE(stkp);\
1539 # define INC_NUM_FAILS ((void) 0)
1540 # define MEMOIZE_MATCH_CACHE_POINT ((void) 0)
1541 # define MEMOIZE_LOOKAROUND_MATCH_CACHE_POINT ((void) 0)
1544 #define STACK_POP_ONE do {\
1546 STACK_BASE_CHECK(stk, "STACK_POP_ONE"); \
1549 #define STACK_POP do {\
1550 switch (pop_level) {\
1551 case STACK_POP_LEVEL_FREE:\
1554 STACK_BASE_CHECK(stk, "STACK_POP"); \
1555 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
1556 ELSE_IF_STATE_CHECK_MARK(stk);\
1557 MEMOIZE_MATCH_CACHE_POINT;\
1560 case STACK_POP_LEVEL_MEM_START:\
1563 STACK_BASE_CHECK(stk, "STACK_POP 2"); \
1564 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
1565 else if (stk->type == STK_MEM_START) {\
1566 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1567 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1569 ELSE_IF_STATE_CHECK_MARK(stk);\
1570 MEMOIZE_MATCH_CACHE_POINT;\
1576 STACK_BASE_CHECK(stk, "STACK_POP 3"); \
1577 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
1578 else if (stk->type == STK_MEM_START) {\
1579 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1580 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1582 else if (stk->type == STK_REPEAT_INC) {\
1583 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
1585 else if (stk->type == STK_MEM_END) {\
1586 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1587 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1589 ELSE_IF_STATE_CHECK_MARK(stk);\
1590 MEMOIZE_MATCH_CACHE_POINT;\
1596 #define STACK_POP_TIL_POS_NOT do {\
1599 STACK_BASE_CHECK(stk, "STACK_POP_TIL_POS_NOT"); \
1600 if (stk->type == STK_POS_NOT) break;\
1601 else if (stk->type == STK_MEM_START) {\
1602 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1603 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1605 else if (stk->type == STK_REPEAT_INC) {\
1606 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
1608 else if (stk->type == STK_MEM_END) {\
1609 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1610 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1612 else if (IS_TO_VOID_TARGET(stk)) {\
1615 ELSE_IF_STATE_CHECK_MARK(stk);\
1616 MEMOIZE_LOOKAROUND_MATCH_CACHE_POINT(stk);\
1620 #define STACK_POP_TIL_LOOK_BEHIND_NOT do {\
1623 STACK_BASE_CHECK(stk, "STACK_POP_TIL_LOOK_BEHIND_NOT"); \
1624 if (stk->type == STK_LOOK_BEHIND_NOT) break;\
1625 else if (stk->type == STK_MEM_START) {\
1626 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1627 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1629 else if (stk->type == STK_REPEAT_INC) {\
1630 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
1632 else if (stk->type == STK_MEM_END) {\
1633 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1634 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1636 ELSE_IF_STATE_CHECK_MARK(stk);\
1640 #define STACK_POP_TIL_ABSENT do {\
1643 STACK_BASE_CHECK(stk, "STACK_POP_TIL_ABSENT"); \
1644 if (stk->type == STK_ABSENT) break;\
1645 else if (stk->type == STK_MEM_START) {\
1646 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1647 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1649 else if (stk->type == STK_REPEAT_INC) {\
1650 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
1652 else if (stk->type == STK_MEM_END) {\
1653 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
1654 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
1656 ELSE_IF_STATE_CHECK_MARK(stk);\
1660 #define STACK_POP_ABSENT_POS(start, end) do {\
1662 STACK_BASE_CHECK(stk, "STACK_POP_ABSENT_POS"); \
1663 (start) = stk->u.absent_pos.abs_pstr;\
1664 (end) = stk->u.absent_pos.end_pstr;\
1667 #define STACK_POS_END(k) do {\
1671 STACK_BASE_CHECK(k, "STACK_POS_END"); \
1672 if (IS_TO_VOID_TARGET(k)) {\
1674 k->type = STK_VOID;\
1676 else if (k->type == STK_POS) {\
1677 k->type = STK_VOID;\
1680 MEMOIZE_LOOKAROUND_MATCH_CACHE_POINT(k);\
1684 #define STACK_STOP_BT_END do {\
1685 OnigStackType *k = stk;\
1688 STACK_BASE_CHECK(k, "STACK_STOP_BT_END"); \
1689 if (IS_TO_VOID_TARGET(k)) {\
1691 k->type = STK_VOID;\
1693 else if (k->type == STK_STOP_BT) {\
1694 k->type = STK_VOID;\
1697 else if (k->type == STK_MATCH_CACHE_POINT) {\
1698 k->type = STK_ATOMIC_MATCH_CACHE_POINT;\
1703 #define STACK_STOP_BT_FAIL do {\
1706 STACK_BASE_CHECK(stk, "STACK_STOP_BT_END"); \
1707 if (stk->type == STK_STOP_BT) {\
1708 stk->type = STK_VOID;\
1711 MEMOIZE_ATOMIC_MATCH_CACHE_POINT;\
1715 #define STACK_NULL_CHECK(isnull,id,s) do {\
1716 OnigStackType* k = STACK_AT((stk-1)->null_check)+1;\
1719 STACK_BASE_CHECK(k, "STACK_NULL_CHECK"); \
1720 if (k->type == STK_NULL_CHECK_START) {\
1721 if (k->u.null_check.num == (id)) {\
1722 (isnull) = (k->u.null_check.pstr == (s));\
1729 #define STACK_NULL_CHECK_REC(isnull,id,s) do {\
1731 OnigStackType* k = STACK_AT((stk-1)->null_check)+1;\
1734 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_REC"); \
1735 if (k->type == STK_NULL_CHECK_START) {\
1736 if (k->u.null_check.num == (id)) {\
1738 (isnull) = (k->u.null_check.pstr == (s));\
1744 else if (k->type == STK_NULL_CHECK_END) {\
1750 #define STACK_NULL_CHECK_MEMST(isnull,id,s,reg) do {\
1751 OnigStackType* k = STACK_AT((stk-1)->null_check)+1;\
1754 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST"); \
1755 if (k->type == STK_NULL_CHECK_START) {\
1756 if (k->u.null_check.num == (id)) {\
1757 if (k->u.null_check.pstr != (s)) {\
1765 if (k->type == STK_MEM_START) {\
1766 if (k->u.mem.end == INVALID_STACK_INDEX) {\
1767 (isnull) = 0; break;\
1769 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
1770 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
1772 endp = (UChar* )k->u.mem.end;\
1773 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
1774 (isnull) = 0; break;\
1776 else if (endp != s) {\
1777 (isnull) = -1; /* empty, but position changed */ \
1789 #define STACK_NULL_CHECK_MEMST_REC(isnull,id,s,reg) do {\
1791 OnigStackType* k = STACK_AT((stk-1)->null_check)+1;\
1794 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST_REC"); \
1795 if (k->type == STK_NULL_CHECK_START) {\
1796 if (k->u.null_check.num == (id)) {\
1798 if (k->u.null_check.pstr != (s)) {\
1806 if (k->type == STK_MEM_START) {\
1807 if (k->u.mem.end == INVALID_STACK_INDEX) {\
1808 (isnull) = 0; break;\
1810 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
1811 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
1813 endp = (UChar* )k->u.mem.end;\
1814 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
1815 (isnull) = 0; break;\
1817 else if (endp != s) {\
1818 (isnull) = -1; /* empty, but position changed */ \
1831 else if (k->type == STK_NULL_CHECK_END) {\
1832 if (k->u.null_check.num == (id)) level++;\
1837 #define STACK_GET_REPEAT(id, k) do {\
1842 STACK_BASE_CHECK(k, "STACK_GET_REPEAT"); \
1843 if (k->type == STK_REPEAT) {\
1845 if (k->u.repeat.num == (id)) {\
1850 else if (k->type == STK_CALL_FRAME) level--;\
1851 else if (k->type == STK_RETURN) level++;\
1855 #define STACK_RETURN(addr) do {\
1857 OnigStackType* k = stk;\
1860 STACK_BASE_CHECK(k, "STACK_RETURN"); \
1861 if (k->type == STK_CALL_FRAME) {\
1863 (addr) = k->u.call_frame.ret_addr;\
1868 else if (k->type == STK_RETURN)\
1874 #define STRING_CMP(s1,s2,len) do {\
1875 while (len-- > 0) {\
1876 if (*s1++ != *s2++) goto fail;\
1880 #define STRING_CMP_IC(case_fold_flag,s1,ps2,len,text_end) do {\
1881 if (string_cmp_ic(encode, case_fold_flag, s1, ps2, len, text_end) == 0) \
1885 static int string_cmp_ic(OnigEncoding enc
, int case_fold_flag
,
1886 UChar
* s1
, UChar
** ps2
, OnigDistance mblen
, const UChar
* text_end
)
1888 UChar buf1
[ONIGENC_MBC_CASE_FOLD_MAXLEN
];
1889 UChar buf2
[ONIGENC_MBC_CASE_FOLD_MAXLEN
];
1890 UChar
*p1
, *p2
, *end1
, *s2
;
1896 len1
= ONIGENC_MBC_CASE_FOLD(enc
, case_fold_flag
, &s1
, text_end
, buf1
);
1897 len2
= ONIGENC_MBC_CASE_FOLD(enc
, case_fold_flag
, &s2
, text_end
, buf2
);
1898 if (len1
!= len2
) return 0;
1901 while (len1
-- > 0) {
1902 if (*p1
!= *p2
) return 0;
1912 #define STRING_CMP_VALUE(s1,s2,len,is_fail) do {\
1914 while (len-- > 0) {\
1915 if (*s1++ != *s2++) {\
1916 is_fail = 1; break;\
1921 #define STRING_CMP_VALUE_IC(case_fold_flag,s1,ps2,len,text_end,is_fail) do {\
1922 if (string_cmp_ic(encode, case_fold_flag, s1, ps2, len, text_end) == 0) \
1929 #define IS_EMPTY_STR (str == end)
1930 #define ON_STR_BEGIN(s) ((s) == str)
1931 #define ON_STR_END(s) ((s) == end)
1932 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
1933 # define DATA_ENSURE_CHECK1 (s < right_range)
1934 # define DATA_ENSURE_CHECK(n) (s + (n) <= right_range)
1935 # define DATA_ENSURE(n) if (s + (n) > right_range) goto fail
1936 # define DATA_ENSURE_CONTINUE(n) if (s + (n) > right_range) continue
1937 # define ABSENT_END_POS right_range
1939 # define DATA_ENSURE_CHECK1 (s < end)
1940 # define DATA_ENSURE_CHECK(n) (s + (n) <= end)
1941 # define DATA_ENSURE(n) if (s + (n) > end) goto fail
1942 # define DATA_ENSURE_CONTINUE(n) if (s + (n) > end) continue
1943 # define ABSENT_END_POS end
1944 #endif /* USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE */
1946 int onigenc_mbclen_approximate(const OnigUChar
* p
,const OnigUChar
* e
, const struct OnigEncodingTypeST
* enc
);
1949 enclen_approx(OnigEncoding enc
, const OnigUChar
* p
, const OnigUChar
* e
)
1951 if (enc
->max_enc_len
== enc
->min_enc_len
) {
1952 return (p
< e
? enc
->min_enc_len
: 0);
1955 return onigenc_mbclen_approximate(p
, e
, enc
);
1960 #ifdef USE_CAPTURE_HISTORY
1962 make_capture_history_tree(OnigCaptureTreeNode
* node
, OnigStackType
** kp
,
1963 OnigStackType
* stk_top
, UChar
* str
, regex_t
* reg
)
1966 OnigCaptureTreeNode
* child
;
1967 OnigStackType
* k
= *kp
;
1969 while (k
< stk_top
) {
1970 if (k
->type
== STK_MEM_START
) {
1972 if (n
<= ONIG_MAX_CAPTURE_HISTORY_GROUP
&&
1973 BIT_STATUS_AT(reg
->capture_history
, n
) != 0) {
1974 child
= history_node_new();
1975 CHECK_NULL_RETURN_MEMERR(child
);
1977 child
->beg
= k
->u
.mem
.pstr
- str
;
1978 r
= history_tree_add_child(node
, child
);
1980 history_tree_free(child
);
1984 r
= make_capture_history_tree(child
, kp
, stk_top
, str
, reg
);
1985 if (r
!= 0) return r
;
1988 child
->end
= k
->u
.mem
.pstr
- str
;
1991 else if (k
->type
== STK_MEM_END
) {
1992 if (k
->u
.mem
.num
== node
->group
) {
1993 node
->end
= k
->u
.mem
.pstr
- str
;
2001 return 1; /* 1: root node ending. */
2003 #endif /* USE_CAPTURE_HISTORY */
2005 #ifdef USE_BACKREF_WITH_LEVEL
2007 mem_is_in_memp(int mem
, int num
, UChar
* memp
)
2012 for (i
= 0; i
< num
; i
++) {
2013 GET_MEMNUM_INC(m
, memp
);
2014 if (mem
== (int )m
) return 1;
2019 static int backref_match_at_nested_level(regex_t
* reg
,
2020 OnigStackType
* top
, OnigStackType
* stk_base
,
2021 int ignore_case
, int case_fold_flag
,
2022 int nest
, int mem_num
, UChar
* memp
, UChar
** s
, const UChar
* send
)
2024 UChar
*ss
, *p
, *pstart
, *pend
= NULL_UCHARP
;
2031 while (k
>= stk_base
) {
2032 if (k
->type
== STK_CALL_FRAME
) {
2035 else if (k
->type
== STK_RETURN
) {
2038 else if (level
== nest
) {
2039 if (k
->type
== STK_MEM_START
) {
2040 if (mem_is_in_memp(k
->u
.mem
.num
, mem_num
, memp
)) {
2041 pstart
= k
->u
.mem
.pstr
;
2042 if (pend
!= NULL_UCHARP
) {
2043 if (pend
- pstart
> send
- *s
) return 0; /* or goto next_mem; */
2047 if (ignore_case
!= 0) {
2048 if (string_cmp_ic(reg
->enc
, case_fold_flag
,
2049 pstart
, &ss
, pend
- pstart
, send
) == 0)
2050 return 0; /* or goto next_mem; */
2054 if (*p
++ != *ss
++) return 0; /* or goto next_mem; */
2063 else if (k
->type
== STK_MEM_END
) {
2064 if (mem_is_in_memp(k
->u
.mem
.num
, mem_num
, memp
)) {
2065 pend
= k
->u
.mem
.pstr
;
2074 #endif /* USE_BACKREF_WITH_LEVEL */
2077 #ifdef ONIG_DEBUG_STATISTICS
2080 # include <windows.h>
2081 static LARGE_INTEGER ts
, te
, freq
;
2082 # define GETTIME(t) QueryPerformanceCounter(&(t))
2083 # define TIMEDIFF(te,ts) (unsigned long )(((te).QuadPart - (ts).QuadPart) \
2084 * 1000000 / freq.QuadPart)
2087 # define USE_TIMEOFDAY
2089 # ifdef USE_TIMEOFDAY
2090 # ifdef HAVE_SYS_TIME_H
2091 # include <sys/time.h>
2093 # ifdef HAVE_UNISTD_H
2094 # include <unistd.h>
2096 static struct timeval ts
, te
;
2097 # define GETTIME(t) gettimeofday(&(t), (struct timezone* )0)
2098 # define TIMEDIFF(te,ts) (((te).tv_usec - (ts).tv_usec) + \
2099 (((te).tv_sec - (ts).tv_sec)*1000000))
2100 # else /* USE_TIMEOFDAY */
2101 # ifdef HAVE_SYS_TIMES_H
2102 # include <sys/times.h>
2104 static struct tms ts
, te
;
2105 # define GETTIME(t) times(&(t))
2106 # define TIMEDIFF(te,ts) ((te).tms_utime - (ts).tms_utime)
2107 # endif /* USE_TIMEOFDAY */
2109 # endif /* _WIN32 */
2111 static int OpCounter
[256];
2112 static int OpPrevCounter
[256];
2113 static unsigned long OpTime
[256];
2114 static int OpCurr
= OP_FINISH
;
2115 static int OpPrevTarget
= OP_FAIL
;
2116 static int MaxStackDepth
= 0;
2118 # define MOP_IN(opcode) do {\
2119 if (opcode == OpPrevTarget) OpPrevCounter[OpCurr]++;\
2121 OpCounter[opcode]++;\
2125 # define MOP_OUT do {\
2127 OpTime[OpCurr] += TIMEDIFF(te, ts);\
2131 onig_statistics_init(void)
2134 for (i
= 0; i
< 256; i
++) {
2135 OpCounter
[i
] = OpPrevCounter
[i
] = 0; OpTime
[i
] = 0;
2139 QueryPerformanceFrequency(&freq
);
2144 onig_print_statistics(FILE* f
)
2147 fprintf(f
, " count prev time\n");
2148 for (i
= 0; OnigOpInfo
[i
].opcode
>= 0; i
++) {
2149 fprintf(f
, "%8d: %8d: %10lu: %s\n",
2150 OpCounter
[i
], OpPrevCounter
[i
], OpTime
[i
], OnigOpInfo
[i
].name
);
2152 fprintf(f
, "\nmax stack depth: %d\n", MaxStackDepth
);
2155 # define STACK_INC do {\
2157 if (stk - stk_base > MaxStackDepth) \
2158 MaxStackDepth = stk - stk_base;\
2161 #else /* ONIG_DEBUG_STATISTICS */
2162 # define STACK_INC stk++
2164 # define MOP_IN(opcode)
2166 #endif /* ONIG_DEBUG_STATISTICS */
2169 #ifdef ONIG_DEBUG_MATCH
2171 stack_type_str(int stack_type
)
2173 switch (stack_type
) {
2174 case STK_ALT
: return "Alt ";
2175 case STK_LOOK_BEHIND_NOT
: return "LBNot ";
2176 case STK_POS_NOT
: return "PosNot";
2177 case STK_MEM_START
: return "MemS ";
2178 case STK_MEM_END
: return "MemE ";
2179 case STK_REPEAT_INC
: return "RepInc";
2180 case STK_STATE_CHECK_MARK
: return "StChMk";
2181 case STK_NULL_CHECK_START
: return "NulChS";
2182 case STK_NULL_CHECK_END
: return "NulChE";
2183 case STK_MEM_END_MARK
: return "MemEMk";
2184 case STK_POS
: return "Pos ";
2185 case STK_STOP_BT
: return "StopBt";
2186 case STK_REPEAT
: return "Rep ";
2187 case STK_CALL_FRAME
: return "Call ";
2188 case STK_RETURN
: return "Ret ";
2189 case STK_VOID
: return "Void ";
2190 case STK_ABSENT_POS
: return "AbsPos";
2191 case STK_ABSENT
: return "Absent";
2192 case STK_MATCH_CACHE_POINT
: return "MCache";
2193 default: return " ";
2197 #ifdef USE_MATCH_CACHE
2200 bsearch_cache_opcodes(const OnigCacheOpcode
*cache_opcodes
, long num_cache_opcodes
, const UChar
* p
)
2202 long l
= 0, r
= num_cache_opcodes
- 1, m
= 0;
2206 if (cache_opcodes
[m
].addr
== p
) break;
2207 if (cache_opcodes
[m
].addr
< p
) l
= m
+ 1;
2214 find_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
)
2217 const OnigCacheOpcode
* cache_opcode
;
2218 const OnigRepeatRange
* range
;
2219 const OnigStackType
*stkp
;
2221 int is_inc
= *p
== OP_REPEAT_INC
|| *p
== OP_REPEAT_INC_NG
;
2223 long num_cache_points_at_outer_repeat
;
2224 long num_cache_points_in_outer_repeat
;
2226 m
= bsearch_cache_opcodes(cache_opcodes
, num_cache_opcodes
, p
);
2228 if (!(0 <= m
&& m
< num_cache_opcodes
&& cache_opcodes
[m
].addr
== p
)) {
2232 cache_opcode
= &cache_opcodes
[m
];
2233 *cache_opcode_ptr
= &cache_opcodes
[m
];
2234 cache_point
= cache_opcode
->cache_point
;
2235 if (cache_opcode
->outer_repeat_mem
== -1) {
2239 num_cache_points_at_outer_repeat
= cache_opcode
->num_cache_points_at_outer_repeat
;
2240 num_cache_points_in_outer_repeat
= cache_opcode
->num_cache_points_in_outer_repeat
;
2242 range
= ®
->repeat_range
[cache_opcode
->outer_repeat_mem
];
2244 stkp
= &stk
[repeat_stk
[cache_opcode
->outer_repeat_mem
]];
2245 count
= is_inc
? stkp
->u
.repeat
.count
- 1 : stkp
->u
.repeat
.count
;
2247 if (count
< range
->lower
) {
2248 return num_cache_points_at_outer_repeat
+
2249 num_cache_points_in_outer_repeat
* count
+
2253 if (range
->upper
== 0x7fffffff) {
2254 return num_cache_points_at_outer_repeat
+
2255 num_cache_points_in_outer_repeat
* (range
->lower
- (is_inc
? 1 : 0)) + (is_inc
? 0 : 1) +
2259 return num_cache_points_at_outer_repeat
+
2260 num_cache_points_in_outer_repeat
* (range
->lower
- 1) +
2261 (num_cache_points_in_outer_repeat
+ 1) * (count
- range
->lower
+ 1) +
2265 static int check_extended_match_cache_point(uint8_t *match_cache_buf
, long match_cache_point_index
, uint8_t match_cache_point_mask
) {
2266 if (match_cache_point_mask
& 0x80) {
2267 return (match_cache_buf
[match_cache_point_index
+ 1] & 0x01) > 0;
2269 return (match_cache_buf
[match_cache_point_index
] & (match_cache_point_mask
<< 1)) > 0;
2273 static void memoize_extended_match_cache_point(uint8_t *match_cache_buf
, long match_cache_point_index
, uint8_t match_cache_point_mask
) {
2274 match_cache_buf
[match_cache_point_index
] |= match_cache_point_mask
;
2275 if (match_cache_point_mask
& 0x80) {
2276 match_cache_buf
[match_cache_point_index
+ 1] |= 0x01;
2278 match_cache_buf
[match_cache_point_index
] |= match_cache_point_mask
<< 1;
2282 #endif /* USE_MATCH_CACHE */
2284 /* match data(str - end) from position (sstart). */
2285 /* if sstart == str then set sprev to NULL. */
2287 match_at(regex_t
* reg
, const UChar
* str
, const UChar
* end
,
2288 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
2289 const UChar
* right_range
,
2291 const UChar
* sstart
, UChar
* sprev
, OnigMatchArg
* msa
)
2293 static const UChar FinishCode
[] = { OP_FINISH
};
2295 int i
, num_mem
, pop_level
;
2296 ptrdiff_t n
, best_len
;
2297 LengthType tlen
, tlen2
;
2300 OnigOptionType option
= reg
->options
;
2301 OnigEncoding encode
= reg
->enc
;
2302 OnigCaseFoldType case_fold_flag
= reg
->case_fold_flag
;
2303 UChar
*s
, *q
, *sbegin
;
2308 char *xmalloc_base
= NULL
;
2309 OnigStackType
*stk_alloc
, *stk_base
= NULL
, *stk
, *stk_end
;
2310 OnigStackType
*stkp
; /* used as any purpose. */
2312 OnigStackIndex
*repeat_stk
;
2313 OnigStackIndex
*mem_start_stk
, *mem_end_stk
;
2314 #ifdef USE_COMBINATION_EXPLOSION_CHECK
2316 unsigned char* state_check_buff
= msa
->state_check_buff
;
2317 int num_comb_exp_check
= reg
->num_comb_exp_check
;
2320 #if USE_TOKEN_THREADED_VM
2321 # define OP_OFFSET 1
2322 # define VM_LOOP JUMP;
2323 # define VM_LOOP_END
2324 # define CASE(x) L_##x: sbegin = s; OPCODE_EXEC_HOOK;
2325 # define DEFAULT L_DEFAULT:
2326 # define NEXT sprev = sbegin; JUMP
2327 # define JUMP pbegin = p; RB_GNUC_EXTENSION_BLOCK(goto *oplabels[*p++])
2329 RB_GNUC_EXTENSION
static const void *oplabels
[] = {
2330 &&L_OP_FINISH
, /* matching process terminator (no more alternative) */
2331 &&L_OP_END
, /* pattern code terminator (success end) */
2333 &&L_OP_EXACT1
, /* single byte, N = 1 */
2334 &&L_OP_EXACT2
, /* single byte, N = 2 */
2335 &&L_OP_EXACT3
, /* single byte, N = 3 */
2336 &&L_OP_EXACT4
, /* single byte, N = 4 */
2337 &&L_OP_EXACT5
, /* single byte, N = 5 */
2338 &&L_OP_EXACTN
, /* single byte */
2339 &&L_OP_EXACTMB2N1
, /* mb-length = 2 N = 1 */
2340 &&L_OP_EXACTMB2N2
, /* mb-length = 2 N = 2 */
2341 &&L_OP_EXACTMB2N3
, /* mb-length = 2 N = 3 */
2342 &&L_OP_EXACTMB2N
, /* mb-length = 2 */
2343 &&L_OP_EXACTMB3N
, /* mb-length = 3 */
2344 &&L_OP_EXACTMBN
, /* other length */
2346 &&L_OP_EXACT1_IC
, /* single byte, N = 1, ignore case */
2347 &&L_OP_EXACTN_IC
, /* single byte, ignore case */
2353 &&L_OP_CCLASS_MB_NOT
,
2354 &&L_OP_CCLASS_MIX_NOT
,
2356 &&L_OP_ANYCHAR
, /* "." */
2357 &&L_OP_ANYCHAR_ML
, /* "." multi-line */
2358 &&L_OP_ANYCHAR_STAR
, /* ".*" */
2359 &&L_OP_ANYCHAR_ML_STAR
, /* ".*" multi-line */
2360 &&L_OP_ANYCHAR_STAR_PEEK_NEXT
,
2361 &&L_OP_ANYCHAR_ML_STAR_PEEK_NEXT
,
2366 &&L_OP_NOT_WORD_BOUND
,
2367 # ifdef USE_WORD_BEGIN_END
2375 &&L_OP_NOT_ASCII_WORD
,
2376 &&L_OP_ASCII_WORD_BOUND
,
2377 &&L_OP_NOT_ASCII_WORD_BOUND
,
2378 # ifdef USE_WORD_BEGIN_END
2379 &&L_OP_ASCII_WORD_BEGIN
,
2380 &&L_OP_ASCII_WORD_END
,
2390 &&L_OP_SEMI_END_BUF
,
2391 &&L_OP_BEGIN_POSITION
,
2397 &&L_OP_BACKREF_MULTI
,
2398 &&L_OP_BACKREF_MULTI_IC
,
2399 # ifdef USE_BACKREF_WITH_LEVEL
2400 &&L_OP_BACKREF_WITH_LEVEL
, /* \k<xxx+n>, \k<xxx-n> */
2404 &&L_OP_MEMORY_START
,
2405 &&L_OP_MEMORY_START_PUSH
, /* push back-tracker to stack */
2406 &&L_OP_MEMORY_END_PUSH
, /* push back-tracker to stack */
2407 # ifdef USE_SUBEXP_CALL
2408 &&L_OP_MEMORY_END_PUSH_REC
, /* push back-tracker to stack */
2413 # ifdef USE_SUBEXP_CALL
2414 &&L_OP_MEMORY_END_REC
, /* push marker to stack */
2421 &&L_OP_FAIL
, /* pop stack and move */
2425 # ifdef USE_OP_PUSH_OR_JUMP_EXACT
2426 &&L_OP_PUSH_OR_JUMP_EXACT1
, /* if match exact then push, else jump. */
2430 &&L_OP_PUSH_IF_PEEK_NEXT
, /* if match exact then push, else none. */
2431 &&L_OP_REPEAT
, /* {n,m} */
2432 &&L_OP_REPEAT_NG
, /* {n,m}? (non greedy) */
2434 &&L_OP_REPEAT_INC_NG
, /* non greedy */
2435 &&L_OP_REPEAT_INC_SG
, /* search and get in stack */
2436 &&L_OP_REPEAT_INC_NG_SG
, /* search and get in stack (non greedy) */
2437 &&L_OP_NULL_CHECK_START
, /* null loop checker start */
2438 &&L_OP_NULL_CHECK_END
, /* null loop checker end */
2439 # ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
2440 &&L_OP_NULL_CHECK_END_MEMST
, /* null loop checker end (with capture status) */
2444 # ifdef USE_SUBEXP_CALL
2445 &&L_OP_NULL_CHECK_END_MEMST_PUSH
, /* with capture status and push check-end */
2450 &&L_OP_PUSH_POS
, /* (?=...) start */
2451 &&L_OP_POP_POS
, /* (?=...) end */
2452 &&L_OP_PUSH_POS_NOT
, /* (?!...) start */
2453 &&L_OP_FAIL_POS
, /* (?!...) end */
2454 &&L_OP_PUSH_STOP_BT
, /* (?>...) start */
2455 &&L_OP_POP_STOP_BT
, /* (?>...) end */
2456 &&L_OP_LOOK_BEHIND
, /* (?<=...) start (no needs end opcode) */
2457 &&L_OP_PUSH_LOOK_BEHIND_NOT
, /* (?<!...) start */
2458 &&L_OP_FAIL_LOOK_BEHIND_NOT
, /* (?<!...) end */
2459 &&L_OP_PUSH_ABSENT_POS
, /* (?~...) start */
2460 &&L_OP_ABSENT
, /* (?~...) start of inner loop */
2461 &&L_OP_ABSENT_END
, /* (?~...) end */
2463 # ifdef USE_SUBEXP_CALL
2464 &&L_OP_CALL
, /* \g<name> */
2472 # ifdef USE_COMBINATION_EXPLOSION_CHECK
2473 &&L_OP_STATE_CHECK_PUSH
, /* combination explosion check and push */
2474 &&L_OP_STATE_CHECK_PUSH_OR_JUMP
, /* check ok -> push, else jump */
2475 &&L_OP_STATE_CHECK
, /* check only */
2481 # ifdef USE_COMBINATION_EXPLOSION_CHECK
2482 &&L_OP_STATE_CHECK_ANYCHAR_STAR
,
2483 &&L_OP_STATE_CHECK_ANYCHAR_ML_STAR
,
2488 /* no need: IS_DYNAMIC_OPTION() == 0 */
2489 # if 0 /* no need: IS_DYNAMIC_OPTION() == 0 */
2490 &&L_OP_SET_OPTION_PUSH
, /* set option and push recover option */
2491 &&L_OP_SET_OPTION
/* set option */
2497 #else /* USE_TOKEN_THREADED_VM */
2499 # define OP_OFFSET 0
2506 # define VM_LOOP_END } sprev = sbegin; }
2507 # define CASE(x) case x:
2508 # define DEFAULT default:
2510 # define JUMP continue; break
2511 #endif /* USE_TOKEN_THREADED_VM */
2514 #ifdef USE_SUBEXP_CALL
2515 /* Stack #0 is used to store the pattern itself and used for (?R), \g<0>,
2516 etc. Additional space is required. */
2517 # define ADD_NUMMEM 1
2519 /* Stack #0 not is used. */
2520 # define ADD_NUMMEM 0
2523 n
= reg
->num_repeat
+ (reg
->num_mem
+ ADD_NUMMEM
) * 2;
2525 STACK_INIT(alloca_base
, xmalloc_base
, n
, INIT_MATCH_STACK_SIZE
);
2526 pop_level
= reg
->stack_pop_level
;
2527 num_mem
= reg
->num_mem
;
2528 repeat_stk
= (OnigStackIndex
* )alloca_base
;
2530 mem_start_stk
= (OnigStackIndex
* )(repeat_stk
+ reg
->num_repeat
);
2531 mem_end_stk
= mem_start_stk
+ (num_mem
+ ADD_NUMMEM
);
2533 OnigStackIndex
*pp
= mem_start_stk
;
2534 for (; pp
< repeat_stk
+ n
; pp
+= 2) {
2535 pp
[0] = INVALID_STACK_INDEX
;
2536 pp
[1] = INVALID_STACK_INDEX
;
2539 #ifndef USE_SUBEXP_CALL
2540 mem_start_stk
--; /* for index start from 1,
2541 mem_start_stk[1]..mem_start_stk[num_mem] */
2542 mem_end_stk
--; /* for index start from 1,
2543 mem_end_stk[1]..mem_end_stk[num_mem] */
2546 #ifdef ONIG_DEBUG_MATCH
2547 fprintf(stderr
, "match_at: str: %"PRIuPTR
" (%p), end: %"PRIuPTR
" (%p), start: %"PRIuPTR
" (%p), sprev: %"PRIuPTR
" (%p)\n",
2548 (uintptr_t )str
, str
, (uintptr_t )end
, end
, (uintptr_t )sstart
, sstart
, (uintptr_t )sprev
, sprev
);
2549 fprintf(stderr
, "size: %d, start offset: %d\n",
2550 (int )(end
- str
), (int )(sstart
- str
));
2551 fprintf(stderr
, "\n ofs> str stk:type addr:opcode\n");
2554 STACK_PUSH_ENSURED(STK_ALT
, (UChar
* )FinishCode
); /* bottom stack */
2555 best_len
= ONIG_MISMATCH
;
2556 s
= (UChar
* )sstart
;
2557 pkeep
= (UChar
* )sstart
;
2560 #ifdef ONIG_DEBUG_MATCH
2561 # define OPCODE_EXEC_HOOK \
2563 UChar *op, *q, *bp, buf[50]; \
2565 op = p - OP_OFFSET; \
2566 fprintf(stderr, "%4"PRIdPTR"> \"", (*op == OP_FINISH) ? (ptrdiff_t )-1 : s - str); \
2569 if (*op != OP_FINISH) { /* s may not be a valid pointer if OP_FINISH. */ \
2570 for (i = 0; i < 7 && q < end; i++) { \
2571 len = enclen(encode, q, end); \
2572 while (len-- > 0) *bp++ = *q++; \
2574 if (q < end) { xmemcpy(bp, "...", 3); bp += 3; } \
2576 xmemcpy(bp, "\"", 1); bp += 1; \
2578 fputs((char* )buf, stderr); \
2579 for (i = 0; i < 20 - (bp - buf); i++) fputc(' ', stderr); \
2580 fprintf(stderr, "%4"PRIdPTR":%s %4"PRIdPTR":", \
2581 stk - stk_base - 1, \
2582 (stk > stk_base) ? stack_type_str(stk[-1].type) : " ", \
2583 (op == FinishCode) ? (ptrdiff_t )-1 : op - reg->p); \
2584 onig_print_compiled_byte_code(stderr, op, reg->p+reg->used, NULL, encode); \
2585 fprintf(stderr, "\n"); \
2588 # define OPCODE_EXEC_HOOK ((void) 0)
2591 #ifdef USE_MATCH_CACHE
2592 #ifdef ONIG_DEBUG_MATCH_CACHE
2593 #define MATCH_CACHE_DEBUG fprintf(stderr, "MATCH CACHE: cache %ld (p=%p index=%ld mask=%d)\n", match_cache_point, pbegin, match_cache_point_index, match_cache_point_mask)
2594 #define MATCH_CACHE_DEBUG_HIT fprintf(stderr, "MATCH CACHE: cache hit\n")
2596 #define MATCH_CACHE_DEBUG ((void) 0)
2597 #define MATCH_CACHE_DEBUG_HIT ((void) 0)
2600 #define MATCH_CACHE_HIT ((void) 0)
2602 # define CHECK_MATCH_CACHE do {\
2603 if (msa->match_cache_status == MATCH_CACHE_STATUS_ENABLED) {\
2604 const OnigCacheOpcode *cache_opcode;\
2605 long cache_point = find_cache_point(reg, msa->cache_opcodes, msa->num_cache_opcodes, pbegin, stk_base, repeat_stk, &cache_opcode);\
2606 if (cache_point >= 0) {\
2607 long match_cache_point = msa->num_cache_points * (long)(s - str) + cache_point;\
2608 long match_cache_point_index = match_cache_point >> 3;\
2609 uint8_t match_cache_point_mask = 1 << (match_cache_point & 7);\
2611 if (msa->match_cache_buf[match_cache_point_index] & match_cache_point_mask) {\
2612 MATCH_CACHE_DEBUG_HIT; MATCH_CACHE_HIT;\
2613 if (cache_opcode->lookaround_nesting == 0) goto fail;\
2614 else if (cache_opcode->lookaround_nesting < 0) {\
2615 if (check_extended_match_cache_point(msa->match_cache_buf, match_cache_point_index, match_cache_point_mask)) {\
2616 STACK_STOP_BT_FAIL;\
2620 if (check_extended_match_cache_point(msa->match_cache_buf, match_cache_point_index, match_cache_point_mask)) {\
2621 p = cache_opcode->match_addr;\
2627 STACK_PUSH_MATCH_CACHE_POINT(match_cache_point_index, match_cache_point_mask);\
2632 # define CHECK_MATCH_CACHE ((void) 0)
2636 CASE(OP_END) MOP_IN(OP_END);
2640 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
2641 if (IS_FIND_LONGEST(option)) {
2642 if (n > msa->best_len) {
2644 msa->best_s = (UChar* )sstart;
2651 region = msa->region;
2653 region->beg[0] = ((pkeep > s) ? s : pkeep) - str;
2654 region->end[0] = s - str;
2655 for (i = 1; i <= num_mem; i++) {
2656 if (mem_end_stk[i] != INVALID_STACK_INDEX) {
2657 if (BIT_STATUS_AT(reg->bt_mem_start, i))
2658 region->beg[i] = STACK_AT(mem_start_stk[i])->u.mem.pstr - str;
2660 region->beg[i] = (UChar* )((void* )mem_start_stk[i]) - str;
2662 region->end[i] = (BIT_STATUS_AT(reg->bt_mem_end, i)
2663 ? STACK_AT(mem_end_stk[i])->u.mem.pstr
2664 : (UChar* )((void* )mem_end_stk[i])) - str;
2667 region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;
2671 #ifdef USE_CAPTURE_HISTORY
2672 if (reg->capture_history != 0) {
2674 OnigCaptureTreeNode* node;
2676 if (IS_NULL(region->history_root)) {
2677 region->history_root = node = history_node_new();
2678 CHECK_NULL_RETURN_MEMERR(node);
2681 node = region->history_root;
2682 history_tree_clear(node);
2686 node->beg = ((pkeep > s) ? s : pkeep) - str;
2687 node->end = s - str;
2690 r = make_capture_history_tree(region->history_root, &stkp,
2691 stk, (UChar* )str, reg);
2693 best_len = r; /* error code */
2697 #endif /* USE_CAPTURE_HISTORY */
2699 } /* n > best_len */
2701 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
2706 if (IS_FIND_CONDITION(option)) {
2707 if (IS_FIND_NOT_EMPTY(option) && s == sstart) {
2708 best_len = ONIG_MISMATCH;
2709 goto fail; /* for retry */
2711 if (IS_FIND_LONGEST(option) && DATA_ENSURE_CHECK1) {
2712 goto fail; /* for retry */
2716 /* default behavior: return first-matching result. */
2720 CASE(OP_EXACT1) MOP_IN(OP_EXACT1);
2722 if (*p != *s) goto fail;
2727 CASE(OP_EXACT1_IC) MOP_IN(OP_EXACT1_IC);
2730 UChar *q, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
2733 len = ONIGENC_MBC_CASE_FOLD(encode,
2734 /* DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag), */
2749 CASE(OP_EXACT2) MOP_IN(OP_EXACT2);
2751 if (*p != *s) goto fail;
2753 if (*p != *s) goto fail;
2759 CASE(OP_EXACT3) MOP_IN(OP_EXACT3);
2761 if (*p != *s) goto fail;
2763 if (*p != *s) goto fail;
2765 if (*p != *s) goto fail;
2771 CASE(OP_EXACT4) MOP_IN(OP_EXACT4);
2773 if (*p != *s) goto fail;
2775 if (*p != *s) goto fail;
2777 if (*p != *s) goto fail;
2779 if (*p != *s) goto fail;
2785 CASE(OP_EXACT5) MOP_IN(OP_EXACT5);
2787 if (*p != *s) goto fail;
2789 if (*p != *s) goto fail;
2791 if (*p != *s) goto fail;
2793 if (*p != *s) goto fail;
2795 if (*p != *s) goto fail;
2801 CASE(OP_EXACTN) MOP_IN(OP_EXACTN);
2802 GET_LENGTH_INC(tlen, p);
2804 while (tlen-- > 0) {
2805 if (*p++ != *s++) goto fail;
2811 CASE(OP_EXACTN_IC) MOP_IN(OP_EXACTN_IC);
2814 UChar *q, *endp, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
2816 GET_LENGTH_INC(tlen, p);
2822 len = ONIGENC_MBC_CASE_FOLD(encode,
2823 /* DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag), */
2829 if (*p != *q) goto fail;
2838 CASE(OP_EXACTMB2N1) MOP_IN(OP_EXACTMB2N1);
2840 if (*p != *s) goto fail;
2842 if (*p != *s) goto fail;
2847 CASE(OP_EXACTMB2N2) MOP_IN(OP_EXACTMB2N2);
2849 if (*p != *s) goto fail;
2851 if (*p != *s) goto fail;
2854 if (*p != *s) goto fail;
2856 if (*p != *s) goto fail;
2861 CASE(OP_EXACTMB2N3) MOP_IN(OP_EXACTMB2N3);
2863 if (*p != *s) goto fail;
2865 if (*p != *s) goto fail;
2867 if (*p != *s) goto fail;
2869 if (*p != *s) goto fail;
2872 if (*p != *s) goto fail;
2874 if (*p != *s) goto fail;
2879 CASE(OP_EXACTMB2N) MOP_IN(OP_EXACTMB2N);
2880 GET_LENGTH_INC(tlen, p);
2881 DATA_ENSURE(tlen * 2);
2882 while (tlen-- > 0) {
2883 if (*p != *s) goto fail;
2885 if (*p != *s) goto fail;
2892 CASE(OP_EXACTMB3N) MOP_IN(OP_EXACTMB3N);
2893 GET_LENGTH_INC(tlen, p);
2894 DATA_ENSURE(tlen * 3);
2895 while (tlen-- > 0) {
2896 if (*p != *s) goto fail;
2898 if (*p != *s) goto fail;
2900 if (*p != *s) goto fail;
2907 CASE(OP_EXACTMBN) MOP_IN(OP_EXACTMBN);
2908 GET_LENGTH_INC(tlen, p); /* mb-len */
2909 GET_LENGTH_INC(tlen2, p); /* string len */
2912 while (tlen2-- > 0) {
2913 if (*p != *s) goto fail;
2920 CASE(OP_CCLASS) MOP_IN(OP_CCLASS);
2922 if (BITSET_AT(((BitSetRef )p), *s) == 0) goto fail;
2924 s += enclen(encode, s, end); /* OP_CCLASS can match mb-code. \D, \S */
2928 CASE(OP_CCLASS_MB) MOP_IN(OP_CCLASS_MB);
2929 if (! ONIGENC_IS_MBC_HEAD(encode, s, end)) goto fail;
2932 GET_LENGTH_INC(tlen, p);
2939 mb_len = enclen_approx(encode, s, end);
2940 DATA_ENSURE(mb_len);
2943 code = ONIGENC_MBC_TO_CODE(encode, ss, s);
2945 #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
2946 if (! onig_is_in_code_range(p, code)) goto fail;
2950 if (! onig_is_in_code_range(q, code)) goto fail;
2957 CASE(OP_CCLASS_MIX) MOP_IN(OP_CCLASS_MIX);
2959 if (ONIGENC_IS_MBC_HEAD(encode, s, end)) {
2964 if (BITSET_AT(((BitSetRef )p), *s) == 0)
2968 GET_LENGTH_INC(tlen, p);
2975 CASE(OP_CCLASS_NOT) MOP_IN(OP_CCLASS_NOT);
2977 if (BITSET_AT(((BitSetRef )p), *s) != 0) goto fail;
2979 s += enclen(encode, s, end);
2983 CASE(OP_CCLASS_MB_NOT) MOP_IN(OP_CCLASS_MB_NOT);
2985 if (! ONIGENC_IS_MBC_HEAD(encode, s, end)) {
2987 GET_LENGTH_INC(tlen, p);
2989 goto cc_mb_not_success;
2993 GET_LENGTH_INC(tlen, p);
2997 int mb_len = enclen(encode, s, end);
2999 if (! DATA_ENSURE_CHECK(mb_len)) {
3003 goto cc_mb_not_success;
3008 code = ONIGENC_MBC_TO_CODE(encode, ss, s);
3010 #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
3011 if (onig_is_in_code_range(p, code)) goto fail;
3015 if (onig_is_in_code_range(q, code)) goto fail;
3024 CASE(OP_CCLASS_MIX_NOT) MOP_IN(OP_CCLASS_MIX_NOT);
3026 if (ONIGENC_IS_MBC_HEAD(encode, s, end)) {
3031 if (BITSET_AT(((BitSetRef )p), *s) != 0)
3035 GET_LENGTH_INC(tlen, p);
3042 CASE(OP_ANYCHAR) MOP_IN(OP_ANYCHAR);
3044 n = enclen_approx(encode, s, end);
3046 if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail;
3051 CASE(OP_ANYCHAR_ML) MOP_IN(OP_ANYCHAR_ML);
3053 n = enclen_approx(encode, s, end);
3059 CASE(OP_ANYCHAR_STAR) MOP_IN(OP_ANYCHAR_STAR);
3060 while (DATA_ENSURE_CHECK1) {
3062 STACK_PUSH_ALT(p, s, sprev, pkeep);
3063 n = enclen_approx(encode, s, end);
3065 if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail;
3072 CASE(OP_ANYCHAR_ML_STAR) MOP_IN(OP_ANYCHAR_ML_STAR);
3073 while (DATA_ENSURE_CHECK1) {
3075 STACK_PUSH_ALT(p, s, sprev, pkeep);
3076 n = enclen_approx(encode, s, end);
3090 CASE(OP_ANYCHAR_STAR_PEEK_NEXT) MOP_IN(OP_ANYCHAR_STAR_PEEK_NEXT);
3091 while (DATA_ENSURE_CHECK1) {
3094 STACK_PUSH_ALT(p + 1, s, sprev, pkeep);
3096 #ifdef USE_MATCH_CACHE
3097 /* We need to increment num_fails here, for invoking a cache optimization correctly. */
3098 /* Actually, the matching will be failed if we use `OP_ANYCHAR_STAR` simply in this case.*/
3102 n = enclen_approx(encode, s, end);
3104 if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail;
3112 CASE(OP_ANYCHAR_ML_STAR_PEEK_NEXT)MOP_IN(OP_ANYCHAR_ML_STAR_PEEK_NEXT);
3113 while (DATA_ENSURE_CHECK1) {
3116 STACK_PUSH_ALT(p + 1, s, sprev, pkeep);
3118 #ifdef USE_MATCH_CACHE
3119 /* We need to increment num_fails here, for invoking a cache optimization correctly. */
3120 /* Actually, the matching will be failed if we use `OP_ANYCHAR_STAR_ML` simply in this case.*/
3124 n = enclen_approx(encode, s, end);
3139 #ifdef USE_COMBINATION_EXPLOSION_CHECK
3140 CASE(OP_STATE_CHECK_ANYCHAR_STAR) MOP_IN(OP_STATE_CHECK_ANYCHAR_STAR);
3141 GET_STATE_CHECK_NUM_INC(mem, p);
3142 while (DATA_ENSURE_CHECK1) {
3143 STATE_CHECK_VAL(scv, mem);
3146 STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem, pkeep);
3147 n = enclen_approx(encode, s, end);
3149 if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 0)) goto fail;
3156 CASE(OP_STATE_CHECK_ANYCHAR_ML_STAR)
3157 MOP_IN(OP_STATE_CHECK_ANYCHAR_ML_STAR);
3159 GET_STATE_CHECK_NUM_INC(mem, p);
3160 while (DATA_ENSURE_CHECK1) {
3161 STATE_CHECK_VAL(scv, mem);
3164 STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem, pkeep);
3165 n = enclen_approx(encode, s, end);
3178 #endif /* USE_COMBINATION_EXPLOSION_CHECK */
3180 CASE(OP_WORD) MOP_IN(OP_WORD);
3182 if (! ONIGENC_IS_MBC_WORD(encode, s, end))
3185 s += enclen(encode, s, end);
3189 CASE(OP_ASCII_WORD) MOP_IN(OP_ASCII_WORD);
3191 if (! ONIGENC_IS_MBC_ASCII_WORD(encode, s, end))
3194 s += enclen(encode, s, end);
3198 CASE(OP_NOT_WORD) MOP_IN(OP_NOT_WORD);
3200 if (ONIGENC_IS_MBC_WORD(encode, s, end))
3203 s += enclen(encode, s, end);
3207 CASE(OP_NOT_ASCII_WORD) MOP_IN(OP_NOT_ASCII_WORD);
3209 if (ONIGENC_IS_MBC_ASCII_WORD(encode, s, end))
3212 s += enclen(encode, s, end);
3216 CASE(OP_WORD_BOUND) MOP_IN(OP_WORD_BOUND);
3217 if (ON_STR_BEGIN(s)) {
3219 if (! ONIGENC_IS_MBC_WORD(encode, s, end))
3222 else if (ON_STR_END(s)) {
3223 if (! ONIGENC_IS_MBC_WORD(encode, sprev, end))
3227 if (ONIGENC_IS_MBC_WORD(encode, s, end)
3228 == ONIGENC_IS_MBC_WORD(encode, sprev, end))
3234 CASE(OP_ASCII_WORD_BOUND) MOP_IN(OP_ASCII_WORD_BOUND);
3235 if (ON_STR_BEGIN(s)) {
3237 if (! ONIGENC_IS_MBC_ASCII_WORD(encode, s, end))
3240 else if (ON_STR_END(s)) {
3241 if (! ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end))
3245 if (ONIGENC_IS_MBC_ASCII_WORD(encode, s, end)
3246 == ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end))
3252 CASE(OP_NOT_WORD_BOUND) MOP_IN(OP_NOT_WORD_BOUND);
3253 if (ON_STR_BEGIN(s)) {
3254 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_WORD(encode, s, end))
3257 else if (ON_STR_END(s)) {
3258 if (ONIGENC_IS_MBC_WORD(encode, sprev, end))
3262 if (ONIGENC_IS_MBC_WORD(encode, s, end)
3263 != ONIGENC_IS_MBC_WORD(encode, sprev, end))
3269 CASE(OP_NOT_ASCII_WORD_BOUND) MOP_IN(OP_NOT_ASCII_WORD_BOUND);
3270 if (ON_STR_BEGIN(s)) {
3271 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_ASCII_WORD(encode, s, end))
3274 else if (ON_STR_END(s)) {
3275 if (ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end))
3279 if (ONIGENC_IS_MBC_ASCII_WORD(encode, s, end)
3280 != ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end))
3286 #ifdef USE_WORD_BEGIN_END
3287 CASE(OP_WORD_BEGIN) MOP_IN(OP_WORD_BEGIN);
3288 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_WORD(encode, s, end)) {
3289 if (ON_STR_BEGIN(s) || !ONIGENC_IS_MBC_WORD(encode, sprev, end)) {
3297 CASE(OP_ASCII_WORD_BEGIN) MOP_IN(OP_ASCII_WORD_BEGIN);
3298 if (DATA_ENSURE_CHECK1 && ONIGENC_IS_MBC_ASCII_WORD(encode, s, end)) {
3299 if (ON_STR_BEGIN(s) || !ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end)) {
3307 CASE(OP_WORD_END) MOP_IN(OP_WORD_END);
3308 if (!ON_STR_BEGIN(s) && ONIGENC_IS_MBC_WORD(encode, sprev, end)) {
3309 if (ON_STR_END(s) || !ONIGENC_IS_MBC_WORD(encode, s, end)) {
3317 CASE(OP_ASCII_WORD_END) MOP_IN(OP_ASCII_WORD_END);
3318 if (!ON_STR_BEGIN(s) && ONIGENC_IS_MBC_ASCII_WORD(encode, sprev, end)) {
3319 if (ON_STR_END(s) || !ONIGENC_IS_MBC_ASCII_WORD(encode, s, end)) {
3328 CASE(OP_BEGIN_BUF) MOP_IN(OP_BEGIN_BUF);
3329 if (! ON_STR_BEGIN(s)) goto fail;
3330 if (IS_NOTBOS(msa->options)) goto fail;
3335 CASE(OP_END_BUF) MOP_IN(OP_END_BUF);
3336 if (! ON_STR_END(s)) goto fail;
3337 if (IS_NOTEOS(msa->options)) goto fail;
3342 CASE(OP_BEGIN_LINE) MOP_IN(OP_BEGIN_LINE);
3343 if (ON_STR_BEGIN(s)) {
3344 if (IS_NOTBOL(msa->options)) goto fail;
3348 else if (ONIGENC_IS_MBC_NEWLINE(encode, sprev, end)
3349 #ifdef USE_CRNL_AS_LINE_TERMINATOR
3350 && !(IS_NEWLINE_CRLF(option)
3351 && ONIGENC_IS_MBC_CRNL(encode, sprev, end))
3353 && !ON_STR_END(s)) {
3360 CASE(OP_END_LINE) MOP_IN(OP_END_LINE);
3361 if (ON_STR_END(s)) {
3362 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3363 if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE_EX(encode, sprev, str, end, option, 1)) {
3365 if (IS_NOTEOL(msa->options)) goto fail;
3368 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3372 else if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 1)) {
3379 CASE(OP_SEMI_END_BUF) MOP_IN(OP_SEMI_END_BUF);
3380 if (ON_STR_END(s)) {
3381 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3382 if (IS_EMPTY_STR || !ONIGENC_IS_MBC_NEWLINE_EX(encode, sprev, str, end, option, 1)) {
3384 if (IS_NOTEOL(msa->options)) goto fail;
3387 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3391 else if (ONIGENC_IS_MBC_NEWLINE_EX(encode, s, str, end, option, 1)) {
3392 UChar* ss = s + enclen(encode, s, end);
3393 if (ON_STR_END(ss)) {
3397 #ifdef USE_CRNL_AS_LINE_TERMINATOR
3398 else if (IS_NEWLINE_CRLF(option)
3399 && ONIGENC_IS_MBC_CRNL(encode, s, end)) {
3400 ss += enclen(encode, ss, end);
3401 if (ON_STR_END(ss)) {
3411 CASE(OP_BEGIN_POSITION) MOP_IN(OP_BEGIN_POSITION);
3418 CASE(OP_MEMORY_START_PUSH) MOP_IN(OP_MEMORY_START_PUSH);
3419 GET_MEMNUM_INC(mem, p);
3420 STACK_PUSH_MEM_START(mem, s);
3424 CASE(OP_MEMORY_START) MOP_IN(OP_MEMORY_START);
3425 GET_MEMNUM_INC(mem, p);
3426 mem_start_stk[mem] = (OnigStackIndex )((void* )s);
3427 mem_end_stk[mem] = INVALID_STACK_INDEX;
3431 CASE(OP_MEMORY_END_PUSH) MOP_IN(OP_MEMORY_END_PUSH);
3432 GET_MEMNUM_INC(mem, p);
3433 STACK_PUSH_MEM_END(mem, s);
3437 CASE(OP_MEMORY_END) MOP_IN(OP_MEMORY_END);
3438 GET_MEMNUM_INC(mem, p);
3439 mem_end_stk[mem] = (OnigStackIndex )((void* )s);
3443 CASE(OP_KEEP) MOP_IN(OP_KEEP);
3448 #ifdef USE_SUBEXP_CALL
3449 CASE(OP_MEMORY_END_PUSH_REC) MOP_IN(OP_MEMORY_END_PUSH_REC);
3450 GET_MEMNUM_INC(mem, p);
3451 STACK_GET_MEM_START(mem, stkp); /* should be before push mem-end. */
3452 mem_start_stk[mem] = GET_STACK_INDEX(stkp);
3453 STACK_PUSH_MEM_END(mem, s);
3457 CASE(OP_MEMORY_END_REC) MOP_IN(OP_MEMORY_END_REC);
3458 GET_MEMNUM_INC(mem, p);
3459 mem_end_stk[mem] = (OnigStackIndex )((void* )s);
3460 STACK_GET_MEM_START(mem, stkp);
3462 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3463 mem_start_stk[mem] = GET_STACK_INDEX(stkp);
3465 mem_start_stk[mem] = (OnigStackIndex )((void* )stkp->u.mem.pstr);
3467 STACK_PUSH_MEM_END_MARK(mem);
3472 CASE(OP_BACKREF1) MOP_IN(OP_BACKREF1);
3477 CASE(OP_BACKREF2) MOP_IN(OP_BACKREF2);
3482 CASE(OP_BACKREFN) MOP_IN(OP_BACKREFN);
3483 GET_MEMNUM_INC(mem, p);
3487 UChar *pstart, *pend;
3489 /* if you want to remove following line,
3490 you should check in parse and compile time. */
3491 if (mem > num_mem) goto fail;
3492 if (mem_end_stk[mem] == INVALID_STACK_INDEX) goto fail;
3493 if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;
3495 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3496 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
3498 pstart = (UChar* )((void* )mem_start_stk[mem]);
3500 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
3501 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
3502 : (UChar* )((void* )mem_end_stk[mem]));
3506 STRING_CMP(pstart, s, n);
3507 while (sprev + (len = enclen_approx(encode, sprev, end)) < s)
3514 CASE(OP_BACKREFN_IC) MOP_IN(OP_BACKREFN_IC);
3515 GET_MEMNUM_INC(mem, p);
3518 UChar *pstart, *pend;
3520 /* if you want to remove following line,
3521 you should check in parse and compile time. */
3522 if (mem > num_mem) goto fail;
3523 if (mem_end_stk[mem] == INVALID_STACK_INDEX) goto fail;
3524 if (mem_start_stk[mem] == INVALID_STACK_INDEX) goto fail;
3526 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3527 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
3529 pstart = (UChar* )((void* )mem_start_stk[mem]);
3531 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
3532 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
3533 : (UChar* )((void* )mem_end_stk[mem]));
3537 STRING_CMP_IC(case_fold_flag, pstart, &s, n, end);
3538 while (sprev + (len = enclen_approx(encode, sprev, end)) < s)
3546 CASE(OP_BACKREF_MULTI) MOP_IN(OP_BACKREF_MULTI);
3549 UChar *pstart, *pend, *swork;
3551 GET_LENGTH_INC(tlen, p);
3552 for (i = 0; i < tlen; i++) {
3553 GET_MEMNUM_INC(mem, p);
3555 if (mem_end_stk[mem] == INVALID_STACK_INDEX) continue;
3556 if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;
3558 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3559 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
3561 pstart = (UChar* )((void* )mem_start_stk[mem]);
3563 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
3564 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
3565 : (UChar* )((void* )mem_end_stk[mem]));
3567 DATA_ENSURE_CONTINUE(n);
3570 STRING_CMP_VALUE(pstart, swork, n, is_fail);
3571 if (is_fail) continue;
3573 while (sprev + (len = enclen_approx(encode, sprev, end)) < s)
3576 p += (SIZE_MEMNUM * (tlen - i - 1));
3577 break; /* success */
3579 if (i == tlen) goto fail;
3585 CASE(OP_BACKREF_MULTI_IC) MOP_IN(OP_BACKREF_MULTI_IC);
3588 UChar *pstart, *pend, *swork;
3590 GET_LENGTH_INC(tlen, p);
3591 for (i = 0; i < tlen; i++) {
3592 GET_MEMNUM_INC(mem, p);
3594 if (mem_end_stk[mem] == INVALID_STACK_INDEX) continue;
3595 if (mem_start_stk[mem] == INVALID_STACK_INDEX) continue;
3597 if (BIT_STATUS_AT(reg->bt_mem_start, mem))
3598 pstart = STACK_AT(mem_start_stk[mem])->u.mem.pstr;
3600 pstart = (UChar* )((void* )mem_start_stk[mem]);
3602 pend = (BIT_STATUS_AT(reg->bt_mem_end, mem)
3603 ? STACK_AT(mem_end_stk[mem])->u.mem.pstr
3604 : (UChar* )((void* )mem_end_stk[mem]));
3606 DATA_ENSURE_CONTINUE(n);
3609 STRING_CMP_VALUE_IC(case_fold_flag, pstart, &swork, n, end, is_fail);
3610 if (is_fail) continue;
3612 while (sprev + (len = enclen(encode, sprev, end)) < s)
3615 p += (SIZE_MEMNUM * (tlen - i - 1));
3616 break; /* success */
3618 if (i == tlen) goto fail;
3623 #ifdef USE_BACKREF_WITH_LEVEL
3624 CASE(OP_BACKREF_WITH_LEVEL)
3630 GET_OPTION_INC(ic, p);
3631 GET_LENGTH_INC(level, p);
3632 GET_LENGTH_INC(tlen, p);
3635 if (backref_match_at_nested_level(reg, stk, stk_base, ic,
3636 case_fold_flag, (int )level, (int )tlen, p, &s, end)) {
3637 while (sprev + (len = enclen(encode, sprev, end)) < s)
3640 p += (SIZE_MEMNUM * tlen);
3651 #if 0 /* no need: IS_DYNAMIC_OPTION() == 0 */
3652 CASE(OP_SET_OPTION_PUSH) MOP_IN(OP_SET_OPTION_PUSH);
3653 GET_OPTION_INC(option, p);
3654 STACK_PUSH_ALT(p, s, sprev, pkeep);
3655 p += SIZE_OP_SET_OPTION + SIZE_OP_FAIL;
3659 CASE(OP_SET_OPTION) MOP_IN(OP_SET_OPTION);
3660 GET_OPTION_INC(option, p);
3665 CASE(OP_NULL_CHECK_START) MOP_IN(OP_NULL_CHECK_START);
3666 GET_MEMNUM_INC(mem, p); /* mem: null check id */
3667 STACK_PUSH_NULL_CHECK_START(mem, s);
3671 CASE(OP_NULL_CHECK_END) MOP_IN(OP_NULL_CHECK_END);
3675 GET_MEMNUM_INC(mem, p); /* mem: null check id */
3676 STACK_NULL_CHECK(isnull, mem, s);
3678 #ifdef ONIG_DEBUG_MATCH
3679 fprintf(stderr, "NULL_CHECK_END: skip id:%d, s:%"PRIuPTR" (%p)\n",
3680 (int )mem, (uintptr_t )s, s);
3683 /* empty loop founded, skip next instruction */
3690 case OP_REPEAT_INC_NG:
3691 case OP_REPEAT_INC_SG:
3692 case OP_REPEAT_INC_NG_SG:
3696 goto unexpected_bytecode_error;
3704 #ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
3705 CASE(OP_NULL_CHECK_END_MEMST) MOP_IN(OP_NULL_CHECK_END_MEMST);
3709 GET_MEMNUM_INC(mem, p); /* mem: null check id */
3710 STACK_NULL_CHECK_MEMST(isnull, mem, s, reg);
3712 # ifdef ONIG_DEBUG_MATCH
3713 fprintf(stderr, "NULL_CHECK_END_MEMST: skip id:%d, s:%"PRIuPTR" (%p)\n",
3714 (int )mem, (uintptr_t )s, s);
3716 if (isnull == -1) goto fail;
3717 goto null_check_found;
3724 #ifdef USE_SUBEXP_CALL
3725 CASE(OP_NULL_CHECK_END_MEMST_PUSH)
3726 MOP_IN(OP_NULL_CHECK_END_MEMST_PUSH);
3730 GET_MEMNUM_INC(mem, p); /* mem: null check id */
3731 # ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
3732 STACK_NULL_CHECK_MEMST_REC(isnull, mem, s, reg);
3734 STACK_NULL_CHECK_REC(isnull, mem, s);
3737 # ifdef ONIG_DEBUG_MATCH
3738 fprintf(stderr, "NULL_CHECK_END_MEMST_PUSH: skip id:%d, s:%"PRIuPTR" (%p)\n",
3739 (int )mem, (uintptr_t )s, s);
3741 if (isnull == -1) goto fail;
3742 goto null_check_found;
3745 STACK_PUSH_NULL_CHECK_END(mem);
3752 CASE(OP_JUMP) MOP_IN(OP_JUMP);
3753 GET_RELADDR_INC(addr, p);
3756 CHECK_INTERRUPT_IN_MATCH_AT;
3759 CASE(OP_PUSH) MOP_IN(OP_PUSH);
3760 GET_RELADDR_INC(addr, p);
3762 STACK_PUSH_ALT(p + addr, s, sprev, pkeep);
3766 #ifdef USE_COMBINATION_EXPLOSION_CHECK
3767 CASE(OP_STATE_CHECK_PUSH) MOP_IN(OP_STATE_CHECK_PUSH);
3768 GET_STATE_CHECK_NUM_INC(mem, p);
3769 STATE_CHECK_VAL(scv, mem);
3772 GET_RELADDR_INC(addr, p);
3773 STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem, pkeep);
3777 CASE(OP_STATE_CHECK_PUSH_OR_JUMP) MOP_IN(OP_STATE_CHECK_PUSH_OR_JUMP);
3778 GET_STATE_CHECK_NUM_INC(mem, p);
3779 GET_RELADDR_INC(addr, p);
3780 STATE_CHECK_VAL(scv, mem);
3785 STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem, pkeep);
3790 CASE(OP_STATE_CHECK) MOP_IN(OP_STATE_CHECK);
3791 GET_STATE_CHECK_NUM_INC(mem, p);
3792 STATE_CHECK_VAL(scv, mem);
3795 STACK_PUSH_STATE_CHECK(s, mem);
3798 #endif /* USE_COMBINATION_EXPLOSION_CHECK */
3800 CASE(OP_POP) MOP_IN(OP_POP);
3802 #ifdef USE_MATCH_CACHE
3803 /* We need to increment num_fails here, for invoking a cache optimization correctly, */
3804 /* because Onigmo makes a loop, which is pairwise disjoint to the following set, as atomic. */
3810 #ifdef USE_OP_PUSH_OR_JUMP_EXACT
3811 CASE(OP_PUSH_OR_JUMP_EXACT1) MOP_IN(OP_PUSH_OR_JUMP_EXACT1);
3812 GET_RELADDR_INC(addr, p);
3813 if (*p == *s && DATA_ENSURE_CHECK1) {
3816 STACK_PUSH_ALT(p + addr, s, sprev, pkeep);
3825 CASE(OP_PUSH_IF_PEEK_NEXT) MOP_IN(OP_PUSH_IF_PEEK_NEXT);
3826 GET_RELADDR_INC(addr, p);
3830 STACK_PUSH_ALT(p + addr, s, sprev, pkeep);
3839 CASE(OP_REPEAT) MOP_IN(OP_REPEAT);
3841 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3842 GET_RELADDR_INC(addr, p);
3845 repeat_stk[mem] = GET_STACK_INDEX(stk);
3846 STACK_PUSH_REPEAT(mem, p);
3848 if (reg->repeat_range[mem].lower == 0) {
3850 STACK_PUSH_ALT(p + addr, s, sprev, pkeep);
3856 CASE(OP_REPEAT_NG) MOP_IN(OP_REPEAT_NG);
3858 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3859 GET_RELADDR_INC(addr, p);
3862 repeat_stk[mem] = GET_STACK_INDEX(stk);
3863 STACK_PUSH_REPEAT(mem, p);
3865 if (reg->repeat_range[mem].lower == 0) {
3867 STACK_PUSH_ALT(p, s, sprev, pkeep);
3874 CASE(OP_REPEAT_INC) MOP_IN(OP_REPEAT_INC);
3875 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3876 si = repeat_stk[mem];
3877 stkp = STACK_AT(si);
3880 stkp->u.repeat.count++;
3881 if (stkp->u.repeat.count >= reg->repeat_range[mem].upper) {
3882 /* end of repeat. Nothing to do. */
3884 else if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {
3885 #ifdef USE_MATCH_CACHE
3886 if (*pbegin == OP_REPEAT_INC) {
3887 #undef MATCH_CACHE_HIT
3888 #define MATCH_CACHE_HIT stkp->u.repeat.count--;
3890 #undef MATCH_CACHE_HIT
3891 #define MATCH_CACHE_HIT ((void) 0)
3894 STACK_PUSH_ALT(p, s, sprev, pkeep);
3895 p = STACK_AT(si)->u.repeat.pcode; /* Don't use stkp after PUSH. */
3898 p = stkp->u.repeat.pcode;
3900 STACK_PUSH_REPEAT_INC(si);
3902 CHECK_INTERRUPT_IN_MATCH_AT;
3905 CASE(OP_REPEAT_INC_SG) MOP_IN(OP_REPEAT_INC_SG);
3906 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3907 STACK_GET_REPEAT(mem, stkp);
3908 si = GET_STACK_INDEX(stkp);
3912 CASE(OP_REPEAT_INC_NG) MOP_IN(OP_REPEAT_INC_NG);
3913 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3914 si = repeat_stk[mem];
3915 stkp = STACK_AT(si);
3918 stkp->u.repeat.count++;
3919 if (stkp->u.repeat.count < reg->repeat_range[mem].upper) {
3920 if (stkp->u.repeat.count >= reg->repeat_range[mem].lower) {
3921 UChar* pcode = stkp->u.repeat.pcode;
3923 STACK_PUSH_REPEAT_INC(si);
3924 if (*pbegin == OP_REPEAT_INC_NG) {
3927 STACK_PUSH_ALT(pcode, s, sprev, pkeep);
3930 p = stkp->u.repeat.pcode;
3931 STACK_PUSH_REPEAT_INC(si);
3934 else if (stkp->u.repeat.count == reg->repeat_range[mem].upper) {
3935 STACK_PUSH_REPEAT_INC(si);
3938 CHECK_INTERRUPT_IN_MATCH_AT;
3941 CASE(OP_REPEAT_INC_NG_SG) MOP_IN(OP_REPEAT_INC_NG_SG);
3942 GET_MEMNUM_INC(mem, p); /* mem: OP_REPEAT ID */
3943 STACK_GET_REPEAT(mem, stkp);
3944 si = GET_STACK_INDEX(stkp);
3948 CASE(OP_PUSH_POS) MOP_IN(OP_PUSH_POS);
3949 STACK_PUSH_POS(s, sprev, pkeep);
3953 CASE(OP_POP_POS) MOP_IN(OP_POP_POS);
3955 STACK_POS_END(stkp);
3956 s = stkp->u.state.pstr;
3957 sprev = stkp->u.state.pstr_prev;
3962 CASE(OP_PUSH_POS_NOT) MOP_IN(OP_PUSH_POS_NOT);
3963 GET_RELADDR_INC(addr, p);
3964 STACK_PUSH_POS_NOT(p + addr, s, sprev, pkeep);
3968 CASE(OP_FAIL_POS) MOP_IN(OP_FAIL_POS);
3969 STACK_POP_TIL_POS_NOT;
3973 CASE(OP_PUSH_STOP_BT) MOP_IN(OP_PUSH_STOP_BT);
3978 CASE(OP_POP_STOP_BT) MOP_IN(OP_POP_STOP_BT);
3983 CASE(OP_LOOK_BEHIND) MOP_IN(OP_LOOK_BEHIND);
3984 GET_LENGTH_INC(tlen, p);
3985 s = (UChar* )ONIGENC_STEP_BACK(encode, str, s, end, (int )tlen);
3986 if (IS_NULL(s)) goto fail;
3987 sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s, end);
3991 CASE(OP_PUSH_LOOK_BEHIND_NOT) MOP_IN(OP_PUSH_LOOK_BEHIND_NOT);
3992 GET_RELADDR_INC(addr, p);
3993 GET_LENGTH_INC(tlen, p);
3994 q = (UChar* )ONIGENC_STEP_BACK(encode, str, s, end, (int )tlen);
3996 /* too short case -> success. ex. /(?<!XXX)a/.match("a")
3997 If you want to change to fail, replace following line. */
4002 STACK_PUSH_LOOK_BEHIND_NOT(p + addr, s, sprev, pkeep);
4004 sprev = (UChar* )onigenc_get_prev_char_head(encode, str, s, end);
4009 CASE(OP_FAIL_LOOK_BEHIND_NOT) MOP_IN(OP_FAIL_LOOK_BEHIND_NOT);
4010 STACK_POP_TIL_LOOK_BEHIND_NOT;
4014 CASE(OP_PUSH_ABSENT_POS) MOP_IN(OP_PUSH_ABSENT_POS);
4015 /* Save the absent-start-pos and the original end-pos. */
4016 STACK_PUSH_ABSENT_POS(s, ABSENT_END_POS);
4020 CASE(OP_ABSENT) MOP_IN(OP_ABSENT);
4022 const UChar* aend = ABSENT_END_POS;
4024 UChar* selfp = p - 1;
4026 STACK_POP_ABSENT_POS(absent, ABSENT_END_POS); /* Restore end-pos. */
4027 GET_RELADDR_INC(addr, p);
4028 #ifdef ONIG_DEBUG_MATCH
4029 fprintf(stderr, "ABSENT: s:%p, end:%p, absent:%p, aend:%p\n", s, end, absent, aend);
4031 if ((absent > aend) && (s > absent)) {
4032 /* An empty match occurred in (?~...) at the start point.
4037 else if ((s >= aend) && (s > absent)) {
4039 /* Only one (or less) character matched in the last iteration.
4040 * This is not a possible point. */
4043 /* All possible points were found. Try matching after (?~...). */
4047 else if (s == end) {
4048 /* At the end of the string, just match with it */
4053 STACK_PUSH_ALT(p + addr, s, sprev, pkeep); /* Push possible point. */
4054 n = enclen(encode, s, end);
4055 STACK_PUSH_ABSENT_POS(absent, ABSENT_END_POS); /* Save the original pos. */
4056 STACK_PUSH_ALT(selfp, s + n, s, pkeep); /* Next iteration. */
4058 ABSENT_END_POS = aend;
4064 CASE(OP_ABSENT_END) MOP_IN(OP_ABSENT_END);
4065 /* The pattern inside (?~...) was matched.
4066 * Set the end-pos temporary and go to next iteration. */
4067 if (sprev < ABSENT_END_POS)
4068 ABSENT_END_POS = sprev;
4069 #ifdef ONIG_DEBUG_MATCH
4070 fprintf(stderr, "ABSENT_END: end:%p\n", ABSENT_END_POS);
4072 STACK_POP_TIL_ABSENT;
4076 #ifdef USE_SUBEXP_CALL
4077 CASE(OP_CALL) MOP_IN(OP_CALL);
4078 GET_ABSADDR_INC(addr, p);
4079 STACK_PUSH_CALL_FRAME(p);
4084 CASE(OP_RETURN) MOP_IN(OP_RETURN);
4091 CASE(OP_CONDITION) MOP_IN(OP_CONDITION);
4092 GET_MEMNUM_INC(mem, p);
4093 GET_RELADDR_INC(addr, p);
4094 if ((mem > num_mem) ||
4095 (mem_end_stk[mem] == INVALID_STACK_INDEX) ||
4096 (mem_start_stk[mem] == INVALID_STACK_INDEX)) {
4114 p = stk->u.state.pcode;
4115 s = stk->u.state.pstr;
4116 sprev = stk->u.state.pstr_prev;
4117 pkeep = stk->u.state.pkeep;
4119 #ifdef USE_MATCH_CACHE
4121 msa->match_cache_status != MATCH_CACHE_STATUS_DISABLED &&
4122 ++msa->num_fails >= (long)(end - str) * msa->num_cache_opcodes
4124 if (msa->match_cache_status == MATCH_CACHE_STATUS_UNINIT) {
4125 msa->match_cache_status = MATCH_CACHE_STATUS_INIT;
4126 OnigPosition r = count_num_cache_opcodes(reg, &msa->num_cache_opcodes);
4127 if (r < 0) goto bytecode_error;
4129 if (msa->num_cache_opcodes == NUM_CACHE_OPCODES_IMPOSSIBLE || msa->num_cache_opcodes == 0) {
4130 msa->match_cache_status = MATCH_CACHE_STATUS_DISABLED;
4131 goto fail_match_cache;
4133 if (msa->num_fails < (long)(end - str) * msa->num_cache_opcodes) {
4134 goto fail_match_cache;
4136 if (msa->cache_opcodes == NULL) {
4137 msa->match_cache_status = MATCH_CACHE_STATUS_ENABLED;
4138 OnigCacheOpcode* cache_opcodes = (OnigCacheOpcode*)xmalloc(msa->num_cache_opcodes * sizeof(OnigCacheOpcode));
4139 if (cache_opcodes == NULL) {
4140 return ONIGERR_MEMORY;
4142 OnigPosition r = init_cache_opcodes(reg, cache_opcodes, &msa->num_cache_points);
4144 if (r == ONIGERR_UNEXPECTED_BYTECODE) goto unexpected_bytecode_error;
4145 else goto bytecode_error;
4147 msa->cache_opcodes = cache_opcodes;
4148 #ifdef ONIG_DEBUG_MATCH_CACHE
4149 fprintf(stderr, "MATCH CACHE: #cache opcodes = %ld\n", msa->num_cache_opcodes);
4150 fprintf(stderr, "MATCH CACHE: #cache points = %ld\n", msa->num_cache_points);
4151 fprintf(stderr, "MATCH CACHE: cache opcodes (%p):\n", msa->cache_opcodes);
4152 for (int i = 0; i < msa->num_cache_opcodes; i++) {
4153 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);
4157 if (msa->match_cache_buf == NULL) {
4158 size_t length = (end - str) + 1;
4159 size_t num_match_cache_points = (size_t)msa->num_cache_points * length;
4160 #ifdef ONIG_DEBUG_MATCH_CACHE
4161 fprintf(stderr, "MATCH CACHE: #match cache points = %ld (length = %zu)\n", num_match_cache_points, length);
4163 /* Overflow check */
4164 if (num_match_cache_points / length != (size_t)msa->num_cache_points) {
4165 return ONIGERR_MEMORY;
4167 if (num_match_cache_points >= LONG_MAX_LIMIT) {
4168 return ONIGERR_MEMORY;
4170 size_t match_cache_buf_length = (num_match_cache_points >> 3) + (num_match_cache_points & 7 ? 1 : 0) + 1;
4171 uint8_t* match_cache_buf = (uint8_t*)xmalloc(match_cache_buf_length * sizeof(uint8_t));
4172 if (match_cache_buf == NULL) {
4173 return ONIGERR_MEMORY;
4175 xmemset(match_cache_buf, 0, match_cache_buf_length * sizeof(uint8_t));
4176 msa->match_cache_buf = match_cache_buf;
4182 #ifdef USE_COMBINATION_EXPLOSION_CHECK
4183 if (stk->u.state.state_check != 0) {
4184 stk->type = STK_STATE_CHECK_MARK;
4190 CHECK_INTERRUPT_IN_MATCH_AT;
4194 goto bytecode_error;
4199 xfree(xmalloc_base);
4205 xfree(xmalloc_base);
4206 return ONIGERR_STACK_BUG;
4211 xfree(xmalloc_base);
4212 return ONIGERR_UNDEFINED_BYTECODE;
4214 unexpected_bytecode_error:
4216 xfree(xmalloc_base);
4217 return ONIGERR_UNEXPECTED_BYTECODE;
4220 xfree(xmalloc_base);
4221 if (stk_base != stk_alloc || IS_NOT_NULL(msa->stack_p))
4223 HANDLE_REG_TIMEOUT_IN_MATCH_AT;
4228 slow_search(OnigEncoding enc, UChar* target, UChar* target_end,
4229 const UChar* text, const UChar* text_end, UChar* text_range)
4231 UChar *t, *p, *s, *end;
4233 end = (UChar* )text_end;
4234 end -= target_end - target - 1;
4235 if (end > text_range)
4240 if (enc->max_enc_len == enc->min_enc_len) {
4241 int n = enc->max_enc_len;
4244 if (*s == *target) {
4247 if (target_end == t || memcmp(t, p, target_end - t) == 0)
4252 return (UChar* )NULL;
4255 if (*s == *target) {
4258 if (target_end == t || memcmp(t, p, target_end - t) == 0)
4261 s += enclen(enc, s, text_end);
4264 return (UChar* )NULL;
4268 str_lower_case_match(OnigEncoding enc, int case_fold_flag,
4269 const UChar* t, const UChar* tend,
4270 const UChar* p, const UChar* end)
4273 UChar *q, lowbuf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
4276 lowlen = ONIGENC_MBC_CASE_FOLD(enc, case_fold_flag, &p, end, lowbuf);
4278 while (lowlen > 0) {
4279 if (*t++ != *q++) return 0;
4288 slow_search_ic(OnigEncoding enc, int case_fold_flag,
4289 UChar* target, UChar* target_end,
4290 const UChar* text, const UChar* text_end, UChar* text_range)
4294 end = (UChar* )text_end;
4295 end -= target_end - target - 1;
4296 if (end > text_range)
4302 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4306 s += enclen(enc, s, text_end);
4309 return (UChar* )NULL;
4313 slow_search_backward(OnigEncoding enc, UChar* target, UChar* target_end,
4314 const UChar* text, const UChar* adjust_text,
4315 const UChar* text_end, const UChar* text_start)
4319 s = (UChar* )text_end;
4320 s -= (target_end - target);
4322 s = (UChar* )text_start;
4324 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s, text_end);
4327 if (*s == *target) {
4330 while (t < target_end) {
4335 if (t == target_end)
4338 s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s, text_end);
4341 return (UChar* )NULL;
4345 slow_search_backward_ic(OnigEncoding enc, int case_fold_flag,
4346 UChar* target, UChar* target_end,
4347 const UChar* text, const UChar* adjust_text,
4348 const UChar* text_end, const UChar* text_start)
4352 s = (UChar* )text_end;
4353 s -= (target_end - target);
4355 s = (UChar* )text_start;
4357 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(enc, adjust_text, s, text_end);
4360 if (str_lower_case_match(enc, case_fold_flag,
4361 target, target_end, s, text_end))
4364 s = (UChar* )onigenc_get_prev_char_head(enc, adjust_text, s, text_end);
4367 return (UChar* )NULL;
4370 #ifndef USE_SUNDAY_QUICK_SEARCH
4371 /* Boyer-Moore-Horspool search applied to a multibyte string */
4373 bm_search_notrev(regex_t* reg, const UChar* target, const UChar* target_end,
4374 const UChar* text, const UChar* text_end,
4375 const UChar* text_range)
4377 const UChar *s, *se, *t, *p, *end;
4379 ptrdiff_t skip, tlen1;
4381 # ifdef ONIG_DEBUG_SEARCH
4382 fprintf(stderr, "bm_search_notrev: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4383 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4386 tail = target_end - 1;
4387 tlen1 = tail - target;
4389 if (end + tlen1 > text_end)
4390 end = text_end - tlen1;
4394 if (IS_NULL(reg->int_map)) {
4399 if (t == target) return (UChar* )s;
4402 skip = reg->map[*se];
4405 s += enclen(reg->enc, s, end);
4406 } while ((s - t) < skip && s < end);
4410 # if OPT_EXACT_MAXLEN >= ONIG_CHAR_TABLE_SIZE
4415 if (t == target) return (UChar* )s;
4418 skip = reg->int_map[*se];
4421 s += enclen(reg->enc, s, end);
4422 } while ((s - t) < skip && s < end);
4427 return (UChar* )NULL;
4430 /* Boyer-Moore-Horspool search */
4432 bm_search(regex_t* reg, const UChar* target, const UChar* target_end,
4433 const UChar* text, const UChar* text_end, const UChar* text_range)
4435 const UChar *s, *t, *p, *end;
4438 # ifdef ONIG_DEBUG_SEARCH
4439 fprintf(stderr, "bm_search: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4440 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4443 end = text_range + (target_end - target) - 1;
4447 tail = target_end - 1;
4448 s = text + (target_end - target) - 1;
4449 if (IS_NULL(reg->int_map)) {
4453 # ifdef ONIG_DEBUG_SEARCH
4454 fprintf(stderr, "bm_search_loop: pos: %"PRIdPTR" %s\n",
4455 (intptr_t )(s - text), s);
4458 if (t == target) return (UChar* )p;
4464 else { /* see int_map[] */
4465 # if OPT_EXACT_MAXLEN >= ONIG_CHAR_TABLE_SIZE
4470 if (t == target) return (UChar* )p;
4473 s += reg->int_map[*s];
4477 return (UChar* )NULL;
4480 /* Boyer-Moore-Horspool search applied to a multibyte string (ignore case) */
4482 bm_search_notrev_ic(regex_t* reg, const UChar* target, const UChar* target_end,
4483 const UChar* text, const UChar* text_end,
4484 const UChar* text_range)
4486 const UChar *s, *se, *t, *end;
4488 ptrdiff_t skip, tlen1;
4489 OnigEncoding enc = reg->enc;
4490 int case_fold_flag = reg->case_fold_flag;
4492 # ifdef ONIG_DEBUG_SEARCH
4493 fprintf(stderr, "bm_search_notrev_ic: text: %d (%p), text_end: %d (%p), text_range: %d (%p)\n",
4494 (int )text, text, (int )text_end, text_end, (int )text_range, text_range);
4497 tail = target_end - 1;
4498 tlen1 = tail - target;
4500 if (end + tlen1 > text_end)
4501 end = text_end - tlen1;
4505 if (IS_NULL(reg->int_map)) {
4508 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4511 skip = reg->map[*se];
4514 s += enclen(reg->enc, s, end);
4515 } while ((s - t) < skip && s < end);
4519 # if OPT_EXACT_MAXLEN >= ONIG_CHAR_TABLE_SIZE
4522 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4525 skip = reg->int_map[*se];
4528 s += enclen(reg->enc, s, end);
4529 } while ((s - t) < skip && s < end);
4534 return (UChar* )NULL;
4537 /* Boyer-Moore-Horspool search (ignore case) */
4539 bm_search_ic(regex_t* reg, const UChar* target, const UChar* target_end,
4540 const UChar* text, const UChar* text_end, const UChar* text_range)
4542 const UChar *s, *p, *end;
4544 OnigEncoding enc = reg->enc;
4545 int case_fold_flag = reg->case_fold_flag;
4547 # ifdef ONIG_DEBUG_SEARCH
4548 fprintf(stderr, "bm_search_ic: text: %d (%p), text_end: %d (%p), text_range: %d (%p)\n",
4549 (int )text, text, (int )text_end, text_end, (int )text_range, text_range);
4552 end = text_range + (target_end - target) - 1;
4556 tail = target_end - 1;
4557 s = text + (target_end - target) - 1;
4558 if (IS_NULL(reg->int_map)) {
4560 p = s - (target_end - target) + 1;
4561 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4567 else { /* see int_map[] */
4568 # if OPT_EXACT_MAXLEN >= ONIG_CHAR_TABLE_SIZE
4570 p = s - (target_end - target) + 1;
4571 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4574 s += reg->int_map[*s];
4578 return (UChar* )NULL;
4581 #else /* USE_SUNDAY_QUICK_SEARCH */
4583 /* Sunday's quick search applied to a multibyte string */
4585 bm_search_notrev(regex_t* reg, const UChar* target, const UChar* target_end,
4586 const UChar* text, const UChar* text_end,
4587 const UChar* text_range)
4589 const UChar *s, *se, *t, *p, *end;
4591 ptrdiff_t skip, tlen1;
4592 OnigEncoding enc = reg->enc;
4594 # ifdef ONIG_DEBUG_SEARCH
4595 fprintf(stderr, "bm_search_notrev: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4596 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4599 tail = target_end - 1;
4600 tlen1 = tail - target;
4602 if (end + tlen1 > text_end)
4603 end = text_end - tlen1;
4607 if (IS_NULL(reg->int_map)) {
4612 if (t == target) return (UChar* )s;
4615 if (s + 1 >= end) break;
4616 skip = reg->map[se[1]];
4619 s += enclen(enc, s, end);
4620 } while ((s - t) < skip && s < end);
4624 # if OPT_EXACT_MAXLEN >= ONIG_CHAR_TABLE_SIZE
4629 if (t == target) return (UChar* )s;
4632 if (s + 1 >= end) break;
4633 skip = reg->int_map[se[1]];
4636 s += enclen(enc, s, end);
4637 } while ((s - t) < skip && s < end);
4642 return (UChar* )NULL;
4645 /* Sunday's quick search */
4647 bm_search(regex_t* reg, const UChar* target, const UChar* target_end,
4648 const UChar* text, const UChar* text_end, const UChar* text_range)
4650 const UChar *s, *t, *p, *end;
4654 # ifdef ONIG_DEBUG_SEARCH
4655 fprintf(stderr, "bm_search: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4656 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4659 tail = target_end - 1;
4660 tlen1 = tail - target;
4661 end = text_range + tlen1;
4666 if (IS_NULL(reg->int_map)) {
4671 if (t == target) return (UChar* )p;
4674 if (s + 1 >= end) break;
4675 s += reg->map[s[1]];
4678 else { /* see int_map[] */
4679 # if OPT_EXACT_MAXLEN >= ONIG_CHAR_TABLE_SIZE
4684 if (t == target) return (UChar* )p;
4687 if (s + 1 >= end) break;
4688 s += reg->int_map[s[1]];
4692 return (UChar* )NULL;
4695 /* Sunday's quick search applied to a multibyte string (ignore case) */
4697 bm_search_notrev_ic(regex_t* reg, const UChar* target, const UChar* target_end,
4698 const UChar* text, const UChar* text_end,
4699 const UChar* text_range)
4701 const UChar *s, *se, *t, *end;
4703 ptrdiff_t skip, tlen1;
4704 OnigEncoding enc = reg->enc;
4705 int case_fold_flag = reg->case_fold_flag;
4707 # ifdef ONIG_DEBUG_SEARCH
4708 fprintf(stderr, "bm_search_notrev_ic: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4709 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4712 tail = target_end - 1;
4713 tlen1 = tail - target;
4715 if (end + tlen1 > text_end)
4716 end = text_end - tlen1;
4720 if (IS_NULL(reg->int_map)) {
4723 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4726 if (s + 1 >= end) break;
4727 skip = reg->map[se[1]];
4730 s += enclen(enc, s, end);
4731 } while ((s - t) < skip && s < end);
4735 # if OPT_EXACT_MAXLEN >= ONIG_CHAR_TABLE_SIZE
4738 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4741 if (s + 1 >= end) break;
4742 skip = reg->int_map[se[1]];
4745 s += enclen(enc, s, end);
4746 } while ((s - t) < skip && s < end);
4751 return (UChar* )NULL;
4754 /* Sunday's quick search (ignore case) */
4756 bm_search_ic(regex_t* reg, const UChar* target, const UChar* target_end,
4757 const UChar* text, const UChar* text_end, const UChar* text_range)
4759 const UChar *s, *p, *end;
4762 OnigEncoding enc = reg->enc;
4763 int case_fold_flag = reg->case_fold_flag;
4765 # ifdef ONIG_DEBUG_SEARCH
4766 fprintf(stderr, "bm_search_ic: text: %"PRIuPTR" (%p), text_end: %"PRIuPTR" (%p), text_range: %"PRIuPTR" (%p)\n",
4767 (uintptr_t )text, text, (uintptr_t )text_end, text_end, (uintptr_t )text_range, text_range);
4770 tail = target_end - 1;
4771 tlen1 = tail - target;
4772 end = text_range + tlen1;
4777 if (IS_NULL(reg->int_map)) {
4780 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4783 if (s + 1 >= end) break;
4784 s += reg->map[s[1]];
4787 else { /* see int_map[] */
4788 # if OPT_EXACT_MAXLEN >= ONIG_CHAR_TABLE_SIZE
4791 if (str_lower_case_match(enc, case_fold_flag, target, target_end,
4794 if (s + 1 >= end) break;
4795 s += reg->int_map[s[1]];
4799 return (UChar* )NULL;
4801 #endif /* USE_SUNDAY_QUICK_SEARCH */
4803 #ifdef USE_INT_MAP_BACKWARD
4805 set_bm_backward_skip(UChar* s, UChar* end, OnigEncoding enc ARG_UNUSED,
4810 if (IS_NULL(*skip)) {
4811 *skip = (int* )xmalloc(sizeof(int) * ONIG_CHAR_TABLE_SIZE);
4812 if (IS_NULL(*skip)) return ONIGERR_MEMORY;
4815 len = (int )(end - s);
4816 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
4819 for (i = len - 1; i > 0; i--)
4826 bm_search_backward(regex_t* reg, const UChar* target, const UChar* target_end,
4827 const UChar* text, const UChar* adjust_text,
4828 const UChar* text_end, const UChar* text_start)
4830 const UChar *s, *t, *p;
4832 s = text_end - (target_end - target);
4836 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, adjust_text, s, text_end);
4841 while (t < target_end && *p == *t) {
4844 if (t == target_end)
4847 s -= reg->int_map_backward[*s];
4848 s = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, adjust_text, s, text_end);
4851 return (UChar* )NULL;
4856 map_search(OnigEncoding enc, UChar map[],
4857 const UChar* text, const UChar* text_range, const UChar* text_end)
4859 const UChar *s = text;
4861 while (s < text_range) {
4862 if (map[*s]) return (UChar* )s;
4864 s += enclen(enc, s, text_end);
4866 return (UChar* )NULL;
4870 map_search_backward(OnigEncoding enc, UChar map[],
4871 const UChar* text, const UChar* adjust_text,
4872 const UChar* text_start, const UChar* text_end)
4874 const UChar *s = text_start;
4877 if (map[*s]) return (UChar* )s;
4879 s = onigenc_get_prev_char_head(enc, adjust_text, s, text_end);
4881 return (UChar* )NULL;
4885 onig_match(regex_t* reg, const UChar* str, const UChar* end, const UChar* at, OnigRegion* region,
4886 OnigOptionType option)
4892 MATCH_ARG_INIT(msa, option, region, at, at);
4893 #ifdef USE_COMBINATION_EXPLOSION_CHECK
4895 ptrdiff_t offset = at - str;
4896 STATE_CHECK_BUFF_INIT(msa, end - str, offset, reg->num_comb_exp_check);
4901 r = onig_region_resize_clear(region, reg->num_mem + 1);
4907 prev = (UChar* )onigenc_get_prev_char_head(reg->enc, str, at, end);
4908 r = match_at(reg, str, end,
4909 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
4915 MATCH_ARG_FREE(msa);
4920 forward_search_range(regex_t* reg, const UChar* str, const UChar* end, UChar* s,
4921 UChar* range, UChar** low, UChar** high, UChar** low_prev)
4923 UChar *p, *pprev = (UChar* )NULL;
4924 size_t input_len = end - str;
4926 #ifdef ONIG_DEBUG_SEARCH
4927 fprintf(stderr, "forward_search_range: str: %"PRIuPTR" (%p), end: %"PRIuPTR" (%p), s: %"PRIuPTR" (%p), range: %"PRIuPTR" (%p)\n",
4928 (uintptr_t )str, str, (uintptr_t )end, end, (uintptr_t )s, s, (uintptr_t )range, range);
4931 if (reg->dmin > input_len) {
4936 if (reg->dmin > 0) {
4937 if (ONIGENC_IS_SINGLEBYTE(reg->enc)) {
4941 UChar *q = p + reg->dmin;
4943 if (q >= end) return 0; /* fail */
4944 while (p < q) p += enclen(reg->enc, p, end);
4949 switch (reg->optimize) {
4950 case ONIG_OPTIMIZE_EXACT:
4951 p = slow_search(reg->enc, reg->exact, reg->exact_end, p, end, range);
4953 case ONIG_OPTIMIZE_EXACT_IC:
4954 p = slow_search_ic(reg->enc, reg->case_fold_flag,
4955 reg->exact, reg->exact_end, p, end, range);
4958 case ONIG_OPTIMIZE_EXACT_BM:
4959 p = bm_search(reg, reg->exact, reg->exact_end, p, end, range);
4962 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:
4963 p = bm_search_notrev(reg, reg->exact, reg->exact_end, p, end, range);
4966 case ONIG_OPTIMIZE_EXACT_BM_IC:
4967 p = bm_search_ic(reg, reg->exact, reg->exact_end, p, end, range);
4970 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV_IC:
4971 p = bm_search_notrev_ic(reg, reg->exact, reg->exact_end, p, end, range);
4974 case ONIG_OPTIMIZE_MAP:
4975 p = map_search(reg->enc, reg->map, p, range, end);
4979 if (p && p < range) {
4980 if (p - reg->dmin < s) {
4983 p += enclen(reg->enc, p, end);
4987 if (reg->sub_anchor) {
4990 switch (reg->sub_anchor) {
4991 case ANCHOR_BEGIN_LINE:
4992 if (!ON_STR_BEGIN(p)) {
4993 prev = onigenc_get_prev_char_head(reg->enc,
4994 (pprev ? pprev : str), p, end);
4995 if (!ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 0))
5000 case ANCHOR_END_LINE:
5001 if (ON_STR_END(p)) {
5002 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
5003 prev = (UChar* )onigenc_get_prev_char_head(reg->enc,
5004 (pprev ? pprev : str), p);
5005 if (prev && ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 1))
5009 else if (! ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, p, str, end, reg->options, 1))
5015 if (reg->dmax == 0) {
5019 *low_prev = onigenc_get_prev_char_head(reg->enc, s, p, end);
5021 *low_prev = onigenc_get_prev_char_head(reg->enc,
5022 (pprev ? pprev : str), p, end);
5026 if (reg->dmax != ONIG_INFINITE_DISTANCE) {
5027 if (p < str + reg->dmax) {
5028 *low = (UChar* )str;
5030 *low_prev = onigenc_get_prev_char_head(reg->enc, str, *low, end);
5033 *low = p - reg->dmax;
5035 *low = onigenc_get_right_adjust_char_head_with_prev(reg->enc, s,
5036 *low, end, (const UChar** )low_prev);
5037 if (low_prev && IS_NULL(*low_prev))
5038 *low_prev = onigenc_get_prev_char_head(reg->enc,
5039 (pprev ? pprev : s), *low, end);
5043 *low_prev = onigenc_get_prev_char_head(reg->enc,
5044 (pprev ? pprev : str), *low, end);
5049 /* no needs to adjust *high, *high is used as range check only */
5050 *high = p - reg->dmin;
5052 #ifdef ONIG_DEBUG_SEARCH
5054 "forward_search_range success: low: %"PRIdPTR", high: %"PRIdPTR", dmin: %"PRIdPTR", dmax: %"PRIdPTR"\n",
5055 *low - str, *high - str, reg->dmin, reg->dmax);
5057 return 1; /* success */
5060 return 0; /* fail */
5063 #define BM_BACKWARD_SEARCH_LENGTH_THRESHOLD 100
5066 backward_search_range(regex_t* reg, const UChar* str, const UChar* end,
5067 UChar* s, const UChar* range, UChar* adjrange,
5068 UChar** low, UChar** high)
5071 size_t input_len = end - str;
5073 if (reg->dmin > input_len) {
5081 switch (reg->optimize) {
5082 case ONIG_OPTIMIZE_EXACT:
5084 p = slow_search_backward(reg->enc, reg->exact, reg->exact_end,
5085 range, adjrange, end, p);
5088 case ONIG_OPTIMIZE_EXACT_IC:
5089 case ONIG_OPTIMIZE_EXACT_BM_IC:
5090 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV_IC:
5091 p = slow_search_backward_ic(reg->enc, reg->case_fold_flag,
5092 reg->exact, reg->exact_end,
5093 range, adjrange, end, p);
5096 case ONIG_OPTIMIZE_EXACT_BM:
5097 case ONIG_OPTIMIZE_EXACT_BM_NOT_REV:
5098 #ifdef USE_INT_MAP_BACKWARD
5099 if (IS_NULL(reg->int_map_backward)) {
5101 if (s - range < BM_BACKWARD_SEARCH_LENGTH_THRESHOLD)
5104 r = set_bm_backward_skip(reg->exact, reg->exact_end, reg->enc,
5105 &(reg->int_map_backward));
5108 p = bm_search_backward(reg, reg->exact, reg->exact_end, range, adjrange,
5115 case ONIG_OPTIMIZE_MAP:
5116 p = map_search_backward(reg->enc, reg->map, range, adjrange, p, end);
5121 if (reg->sub_anchor) {
5124 switch (reg->sub_anchor) {
5125 case ANCHOR_BEGIN_LINE:
5126 if (!ON_STR_BEGIN(p)) {
5127 prev = onigenc_get_prev_char_head(reg->enc, str, p, end);
5128 if (!ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 0)) {
5135 case ANCHOR_END_LINE:
5136 if (ON_STR_END(p)) {
5137 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
5138 prev = onigenc_get_prev_char_head(reg->enc, adjrange, p);
5139 if (IS_NULL(prev)) goto fail;
5140 if (ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 1)) {
5146 else if (! ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, p, str, end, reg->options, 1)) {
5147 p = onigenc_get_prev_char_head(reg->enc, adjrange, p, end);
5148 if (IS_NULL(p)) goto fail;
5155 /* no needs to adjust *high, *high is used as range check only */
5156 if (reg->dmax != ONIG_INFINITE_DISTANCE) {
5157 *low = p - reg->dmax;
5158 *high = p - reg->dmin;
5159 *high = onigenc_get_right_adjust_char_head(reg->enc, adjrange, *high, end);
5162 #ifdef ONIG_DEBUG_SEARCH
5163 fprintf(stderr, "backward_search_range: low: %d, high: %d\n",
5164 (int )(*low - str), (int )(*high - str));
5166 return 1; /* success */
5170 #ifdef ONIG_DEBUG_SEARCH
5171 fprintf(stderr, "backward_search_range: fail.\n");
5173 return 0; /* fail */
5178 onig_search(regex_t* reg, const UChar* str, const UChar* end,
5179 const UChar* start, const UChar* range, OnigRegion* region, OnigOptionType option)
5181 return onig_search_gpos(reg, str, end, start, start, range, region, option);
5185 onig_search_gpos(regex_t* reg, const UChar* str, const UChar* end,
5186 const UChar* global_pos,
5187 const UChar* start, const UChar* range, OnigRegion* region, OnigOptionType option)
5192 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
5193 const UChar *orig_start = start;
5194 const UChar *orig_range = range;
5197 #ifdef ONIG_DEBUG_SEARCH
5199 "onig_search (entry point): str: %"PRIuPTR" (%p), end: %"PRIuPTR", start: %"PRIuPTR", range: %"PRIuPTR"\n",
5200 (uintptr_t )str, str, end - str, start - str, range - str);
5204 r = onig_region_resize_clear(region, reg->num_mem + 1);
5205 if (r) goto finish_no_msa;
5208 if (start > end || start < str) goto mismatch_no_msa;
5211 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
5212 # ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
5213 # define MATCH_AND_RETURN_CHECK(upper_range) \
5214 r = match_at(reg, str, end, (upper_range), s, prev, &msa); \
5215 if (r != ONIG_MISMATCH) {\
5217 if (! IS_FIND_LONGEST(reg->options)) {\
5221 else goto finish; /* error */ \
5224 # define MATCH_AND_RETURN_CHECK(upper_range) \
5225 r = match_at(reg, str, end, (upper_range), s, prev, &msa); \
5226 if (r != ONIG_MISMATCH) {\
5230 else goto finish; /* error */ \
5232 # endif /* USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE */
5234 # ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
5235 # define MATCH_AND_RETURN_CHECK(none) \
5236 r = match_at(reg, str, end, s, prev, &msa);\
5237 if (r != ONIG_MISMATCH) {\
5239 if (! IS_FIND_LONGEST(reg->options)) {\
5243 else goto finish; /* error */ \
5246 # define MATCH_AND_RETURN_CHECK(none) \
5247 r = match_at(reg, str, end, s, prev, &msa);\
5248 if (r != ONIG_MISMATCH) {\
5252 else goto finish; /* error */ \
5254 # endif /* USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE */
5255 #endif /* USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE */
5258 /* anchor optimize: resume search range */
5259 if (reg->anchor != 0 && str < end) {
5260 UChar *min_semi_end, *max_semi_end;
5262 if (reg->anchor & ANCHOR_BEGIN_POSITION) {
5263 /* search start-position only */
5267 if (global_pos > start)
5269 if (global_pos < range)
5270 range = global_pos + 1;
5278 else if (reg->anchor & ANCHOR_BEGIN_BUF) {
5279 /* search str-position only */
5280 if (range > start) {
5281 if (start != str) goto mismatch_no_msa;
5290 goto mismatch_no_msa;
5293 else if (reg->anchor & ANCHOR_END_BUF) {
5294 min_semi_end = max_semi_end = (UChar* )end;
5297 if ((OnigDistance )(max_semi_end - str) < reg->anchor_dmin)
5298 goto mismatch_no_msa;
5300 if (range > start) {
5301 if ((OnigDistance )(min_semi_end - start) > reg->anchor_dmax) {
5302 start = min_semi_end - reg->anchor_dmax;
5304 start = onigenc_get_right_adjust_char_head(reg->enc, str, start, end);
5306 if ((OnigDistance )(max_semi_end - (range - 1)) < reg->anchor_dmin) {
5307 range = max_semi_end - reg->anchor_dmin + 1;
5310 if (start > range) goto mismatch_no_msa;
5311 /* If start == range, match with empty at end.
5312 Backward search is used. */
5315 if ((OnigDistance )(min_semi_end - range) > reg->anchor_dmax) {
5316 range = min_semi_end - reg->anchor_dmax;
5318 if ((OnigDistance )(max_semi_end - start) < reg->anchor_dmin) {
5319 start = max_semi_end - reg->anchor_dmin;
5320 start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, start, end);
5322 if (range > start) goto mismatch_no_msa;
5325 else if (reg->anchor & ANCHOR_SEMI_END_BUF) {
5326 UChar* pre_end = ONIGENC_STEP_BACK(reg->enc, str, end, end, 1);
5328 max_semi_end = (UChar* )end;
5329 if (ONIGENC_IS_MBC_NEWLINE(reg->enc, pre_end, end)) {
5330 min_semi_end = pre_end;
5332 #ifdef USE_CRNL_AS_LINE_TERMINATOR
5333 pre_end = ONIGENC_STEP_BACK(reg->enc, str, pre_end, end, 1);
5334 if (IS_NOT_NULL(pre_end) &&
5335 IS_NEWLINE_CRLF(reg->options) &&
5336 ONIGENC_IS_MBC_CRNL(reg->enc, pre_end, end)) {
5337 min_semi_end = pre_end;
5340 if (min_semi_end > str && start <= min_semi_end) {
5345 min_semi_end = (UChar* )end;
5349 else if ((reg->anchor & ANCHOR_ANYCHAR_STAR_ML)) {
5350 goto begin_position;
5353 else if (str == end) { /* empty string */
5354 static const UChar address_for_empty_string[] = "";
5356 #ifdef ONIG_DEBUG_SEARCH
5357 fprintf(stderr, "onig_search: empty string.\n");
5360 if (reg->threshold_len == 0) {
5361 start = end = str = address_for_empty_string;
5363 prev = (UChar* )NULL;
5365 MATCH_ARG_INIT(msa, option, region, start, start);
5366 #ifdef USE_COMBINATION_EXPLOSION_CHECK
5367 msa.state_check_buff = (void* )0;
5368 msa.state_check_buff_size = 0; /* NO NEED, for valgrind */
5370 MATCH_AND_RETURN_CHECK(end);
5373 goto mismatch_no_msa;
5376 #ifdef ONIG_DEBUG_SEARCH
5377 fprintf(stderr, "onig_search(apply anchor): end: %d, start: %d, range: %d\n",
5378 (int )(end - str), (int )(start - str), (int )(range - str));
5381 MATCH_ARG_INIT(msa, option, region, start, global_pos);
5382 #ifdef USE_COMBINATION_EXPLOSION_CHECK
5384 ptrdiff_t offset = (MIN(start, range) - str);
5385 STATE_CHECK_BUFF_INIT(msa, end - str, offset, reg->num_comb_exp_check);
5390 if (range > start) { /* forward search */
5392 prev = onigenc_get_prev_char_head(reg->enc, str, s, end);
5394 prev = (UChar* )NULL;
5396 if (reg->optimize != ONIG_OPTIMIZE_NONE) {
5397 UChar *sch_range, *low, *high, *low_prev;
5399 sch_range = (UChar* )range;
5400 if (reg->dmax != 0) {
5401 if (reg->dmax == ONIG_INFINITE_DISTANCE)
5402 sch_range = (UChar* )end;
5404 sch_range += reg->dmax;
5405 if (sch_range > end) sch_range = (UChar* )end;
5409 if ((end - start) < reg->threshold_len)
5412 if (reg->dmax != ONIG_INFINITE_DISTANCE) {
5414 if (! forward_search_range(reg, str, end, s, sch_range,
5415 &low, &high, &low_prev)) goto mismatch;
5421 MATCH_AND_RETURN_CHECK(orig_range);
5423 s += enclen(reg->enc, s, end);
5425 } while (s < range);
5428 else { /* check only. */
5429 if (! forward_search_range(reg, str, end, s, sch_range,
5430 &low, &high, (UChar** )NULL)) goto mismatch;
5432 if ((reg->anchor & ANCHOR_ANYCHAR_STAR) != 0) {
5434 MATCH_AND_RETURN_CHECK(orig_range);
5436 s += enclen(reg->enc, s, end);
5438 if ((reg->anchor & (ANCHOR_LOOK_BEHIND | ANCHOR_PREC_READ_NOT)) == 0) {
5439 while (!ONIGENC_IS_MBC_NEWLINE_EX(reg->enc, prev, str, end, reg->options, 0)
5442 s += enclen(reg->enc, s, end);
5445 } while (s < range);
5452 MATCH_AND_RETURN_CHECK(orig_range);
5454 s += enclen(reg->enc, s, end);
5455 } while (s < range);
5457 if (s == range) { /* because empty match with /$/. */
5458 MATCH_AND_RETURN_CHECK(orig_range);
5461 else { /* backward search */
5462 if (reg->optimize != ONIG_OPTIMIZE_NONE) {
5463 UChar *low, *high, *adjrange, *sch_start;
5466 adjrange = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc, str, range, end);
5468 adjrange = (UChar* )end;
5470 if (reg->dmax != ONIG_INFINITE_DISTANCE &&
5471 (end - range) >= reg->threshold_len) {
5473 sch_start = s + reg->dmax;
5474 if (sch_start > end) sch_start = (UChar* )end;
5475 if (backward_search_range(reg, str, end, sch_start, range, adjrange,
5483 prev = onigenc_get_prev_char_head(reg->enc, str, s, end);
5484 MATCH_AND_RETURN_CHECK(orig_start);
5487 } while (s >= range);
5490 else { /* check only. */
5491 if ((end - range) < reg->threshold_len) goto mismatch;
5494 if (reg->dmax != 0) {
5495 if (reg->dmax == ONIG_INFINITE_DISTANCE)
5496 sch_start = (UChar* )end;
5498 sch_start += reg->dmax;
5499 if (sch_start > end) sch_start = (UChar* )end;
5501 sch_start = ONIGENC_LEFT_ADJUST_CHAR_HEAD(reg->enc,
5502 start, sch_start, end);
5505 if (backward_search_range(reg, str, end, sch_start, range, adjrange,
5506 &low, &high) <= 0) goto mismatch;
5511 prev = onigenc_get_prev_char_head(reg->enc, str, s, end);
5512 MATCH_AND_RETURN_CHECK(orig_start);
5514 } while (s >= range);
5518 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
5519 if (IS_FIND_LONGEST(reg->options)) {
5520 if (msa.best_len >= 0) {
5529 MATCH_ARG_FREE(msa);
5531 /* If result is mismatch and no FIND_NOT_EMPTY option,
5532 then the region is not set in match_at(). */
5533 if (IS_FIND_NOT_EMPTY(reg->options) && region) {
5534 onig_region_clear(region);
5538 if (r != ONIG_MISMATCH)
5539 fprintf(stderr, "onig_search: error %"PRIdPTRDIFF"\n", r);
5547 if (r != ONIG_MISMATCH)
5548 fprintf(stderr, "onig_search: error %"PRIdPTRDIFF"\n", r);
5553 MATCH_ARG_FREE(msa);
5558 onig_scan(regex_t* reg, const UChar* str, const UChar* end,
5559 OnigRegion* region, OnigOptionType option,
5560 int (*scan_callback)(OnigPosition, OnigPosition, OnigRegion*, void*),
5571 r = onig_search(reg, str, end, start, end, region, option);
5573 rs = scan_callback(n, r, region, callback_arg);
5578 if (region->end[0] == start - str) {
5579 if (start >= end) break;
5580 start += enclen(reg->enc, start, end);
5583 start = str + region->end[0];
5588 else if (r == ONIG_MISMATCH) {
5600 onig_get_encoding(const regex_t* reg)
5605 extern OnigOptionType
5606 onig_get_options(const regex_t* reg)
5608 return reg->options;
5611 extern OnigCaseFoldType
5612 onig_get_case_fold_flag(const regex_t* reg)
5614 return reg->case_fold_flag;
5617 extern const OnigSyntaxType*
5618 onig_get_syntax(const regex_t* reg)
5624 onig_number_of_captures(const regex_t* reg)
5626 return reg->num_mem;
5630 onig_number_of_capture_histories(const regex_t* reg)
5632 #ifdef USE_CAPTURE_HISTORY
5636 for (i = 0; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
5637 if (BIT_STATUS_AT(reg->capture_history, i) != 0)
5647 onig_copy_encoding(OnigEncodingType *to, OnigEncoding from)