34 #ifdef USE_CRNL_AS_LINE_TERMINATOR
35 #define ONIGENC_IS_MBC_CRNL(enc,p,end) \
36 (ONIGENC_MBC_TO_CODE(enc,p,end) == 13 && \
37 ONIGENC_IS_MBC_NEWLINE(enc,(p+enclen(enc,p)),end))
40 #ifdef USE_CAPTURE_HISTORY
51 history_tree_free(node->
childs[i]);
67 history_tree_clear(node);
81 history_node_new(
void)
100 #define HISTORY_TREE_INIT_ALLOC_SIZE 8
106 n = HISTORY_TREE_INIT_ALLOC_SIZE;
117 for (i = parent->
allocated; i < n; i++) {
134 clone = history_node_new();
140 child = history_tree_clone(node->
childs[i]);
142 history_tree_free(clone);
145 history_tree_add_child(clone, child);
163 for (i = 0; i < region->
num_regs; i++) {
166 #ifdef USE_CAPTURE_HISTORY
167 history_root_free(region);
180 region->
beg = (
int* )
xmalloc(n *
sizeof(
int));
181 if (region->
beg == 0)
184 region->
end = (
int* )
xmalloc(n *
sizeof(
int));
185 if (region->
end == 0) {
196 tmp = (
int* )
xrealloc(region->
beg, n *
sizeof(
int));
203 tmp = (
int* )
xrealloc(region->
end, n *
sizeof(
int));
210 if (region->
beg == 0 || region->
end == 0)
225 if (r != 0)
return r;
240 region->
beg[at] = beg;
241 region->
end[at] = end;
250 region->
beg = (
int* )0;
251 region->
end = (
int* )0;
275 #ifdef USE_CAPTURE_HISTORY
276 history_root_free(r);
278 if (free_self)
xfree(r);
285 #define RREGC_SIZE (sizeof(int) * from->num_regs)
288 if (to == from)
return;
291 for (i = 0; i < from->
num_regs; i++) {
297 #ifdef USE_CAPTURE_HISTORY
298 history_root_free(to);
308 #define INVALID_STACK_INDEX -1
312 #define STK_ALT 0x0001
313 #define STK_LOOK_BEHIND_NOT 0x0002
314 #define STK_POS_NOT 0x0003
316 #define STK_MEM_START 0x0100
317 #define STK_MEM_END 0x8200
318 #define STK_REPEAT_INC 0x0300
319 #define STK_STATE_CHECK_MARK 0x1000
321 #define STK_NULL_CHECK_START 0x3000
322 #define STK_NULL_CHECK_END 0x5000
323 #define STK_MEM_END_MARK 0x8400
324 #define STK_POS 0x0500
325 #define STK_STOP_BT 0x0600
326 #define STK_REPEAT 0x0700
327 #define STK_CALL_FRAME 0x0800
328 #define STK_RETURN 0x0900
329 #define STK_VOID 0x0a00
332 #define STK_MASK_POP_USED 0x00ff
333 #define STK_MASK_TO_VOID_TARGET 0x10ff
334 #define STK_MASK_MEM_END_OR_MARK 0x8000
336 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
337 #define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start) do {\
338 (msa).stack_p = (void* )0;\
339 (msa).options = (arg_option);\
340 (msa).region = (arg_region);\
341 (msa).start = (arg_start);\
342 (msa).best_len = ONIG_MISMATCH;\
345 #define MATCH_ARG_INIT(msa, arg_option, arg_region, arg_start) do {\
346 (msa).stack_p = (void* )0;\
347 (msa).options = (arg_option);\
348 (msa).region = (arg_region);\
349 (msa).start = (arg_start);\
353 #ifdef USE_COMBINATION_EXPLOSION_CHECK
355 #define STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE 16
357 #define STATE_CHECK_BUFF_INIT(msa, str_len, offset, state_num) do { \
358 if ((state_num) > 0 && str_len >= STATE_CHECK_STRING_THRESHOLD_LEN) {\
359 unsigned int size = (unsigned int )(((str_len) + 1) * (state_num) + 7) >> 3;\
360 offset = ((offset) * (state_num)) >> 3;\
361 if (size > 0 && offset < size && size < STATE_CHECK_BUFF_MAX_SIZE) {\
362 if (size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) {\
363 (msa).state_check_buff = (void* )xmalloc(size);\
364 CHECK_NULL_RETURN_MEMERR((msa).state_check_buff);\
367 (msa).state_check_buff = (void* )xalloca(size);\
368 xmemset(((char* )((msa).state_check_buff)+(offset)), 0, \
369 (size_t )(size - (offset))); \
370 (msa).state_check_buff_size = size;\
373 (msa).state_check_buff = (void* )0;\
374 (msa).state_check_buff_size = 0;\
378 (msa).state_check_buff = (void* )0;\
379 (msa).state_check_buff_size = 0;\
383 #define MATCH_ARG_FREE(msa) do {\
384 if ((msa).stack_p) xfree((msa).stack_p);\
385 if ((msa).state_check_buff_size >= STATE_CHECK_BUFF_MALLOC_THRESHOLD_SIZE) { \
386 if ((msa).state_check_buff) xfree((msa).state_check_buff);\
390 #define MATCH_ARG_FREE(msa) if ((msa).stack_p) xfree((msa).stack_p)
395 #define STACK_INIT(alloc_addr, ptr_num, stack_num) do {\
397 alloc_addr = (char* )xalloca(sizeof(char*) * (ptr_num));\
398 stk_alloc = (OnigStackType* )(msa->stack_p);\
399 stk_base = stk_alloc;\
401 stk_end = stk_base + msa->stack_n;\
404 alloc_addr = (char* )xalloca(sizeof(char*) * (ptr_num)\
405 + sizeof(OnigStackType) * (stack_num));\
406 stk_alloc = (OnigStackType* )(alloc_addr + sizeof(char*) * (ptr_num));\
407 stk_base = stk_alloc;\
409 stk_end = stk_base + (stack_num);\
413 #define STACK_SAVE do{\
414 if (stk_base != stk_alloc) {\
415 msa->stack_p = stk_base;\
416 msa->stack_n = stk_end - stk_base; \
431 MatchStackLimitSize =
size;
442 stk_base = *arg_stk_base;
443 stk_end = *arg_stk_end;
446 n = stk_end - stk_base;
459 if (limit_size != 0 && n > limit_size) {
460 if ((
unsigned int )(stk_end - stk_base) == limit_size)
471 *arg_stk = x + (stk - stk_base);
473 *arg_stk_end = x + n;
477 #define STACK_ENSURE(n) do {\
478 if (stk_end - stk < (n)) {\
479 int r = stack_double(&stk_base, &stk_end, &stk, stk_alloc, msa);\
480 if (r != 0) { STACK_SAVE; return r; } \
484 #define STACK_AT(index) (stk_base + (index))
485 #define GET_STACK_INDEX(stk) ((stk) - stk_base)
487 #define STACK_PUSH_TYPE(stack_type) do {\
489 stk->type = (stack_type);\
493 #define IS_TO_VOID_TARGET(stk) (((stk)->type & STK_MASK_TO_VOID_TARGET) != 0)
495 #ifdef USE_COMBINATION_EXPLOSION_CHECK
496 #define STATE_CHECK_POS(s,snum) \
497 (((s) - str) * num_comb_exp_check + ((snum) - 1))
498 #define STATE_CHECK_VAL(v,snum) do {\
499 if (state_check_buff != NULL) {\
500 int x = STATE_CHECK_POS(s,snum);\
501 (v) = state_check_buff[x/8] & (1<<(x%8));\
507 #define ELSE_IF_STATE_CHECK_MARK(stk) \
508 else if ((stk)->type == STK_STATE_CHECK_MARK) { \
509 int x = STATE_CHECK_POS(stk->u.state.pstr, stk->u.state.state_check);\
510 state_check_buff[x/8] |= (1<<(x%8)); \
513 #define STACK_PUSH(stack_type,pat,s,sprev) do {\
515 stk->type = (stack_type);\
516 stk->u.state.pcode = (pat);\
517 stk->u.state.pstr = (s);\
518 stk->u.state.pstr_prev = (sprev);\
519 stk->u.state.state_check = 0;\
523 #define STACK_PUSH_ENSURED(stack_type,pat) do {\
524 stk->type = (stack_type);\
525 stk->u.state.pcode = (pat);\
526 stk->u.state.state_check = 0;\
530 #define STACK_PUSH_ALT_WITH_STATE_CHECK(pat,s,sprev,snum) do {\
532 stk->type = STK_ALT;\
533 stk->u.state.pcode = (pat);\
534 stk->u.state.pstr = (s);\
535 stk->u.state.pstr_prev = (sprev);\
536 stk->u.state.state_check = ((state_check_buff != NULL) ? (snum) : 0);\
540 #define STACK_PUSH_STATE_CHECK(s,snum) do {\
541 if (state_check_buff != NULL) {\
543 stk->type = STK_STATE_CHECK_MARK;\
544 stk->u.state.pstr = (s);\
545 stk->u.state.state_check = (snum);\
552 #define ELSE_IF_STATE_CHECK_MARK(stk)
554 #define STACK_PUSH(stack_type,pat,s,sprev) do {\
556 stk->type = (stack_type);\
557 stk->u.state.pcode = (pat);\
558 stk->u.state.pstr = (s);\
559 stk->u.state.pstr_prev = (sprev);\
563 #define STACK_PUSH_ENSURED(stack_type,pat) do {\
564 stk->type = (stack_type);\
565 stk->u.state.pcode = (pat);\
570 #define STACK_PUSH_ALT(pat,s,sprev) STACK_PUSH(STK_ALT,pat,s,sprev)
571 #define STACK_PUSH_POS(s,sprev) STACK_PUSH(STK_POS,NULL_UCHARP,s,sprev)
572 #define STACK_PUSH_POS_NOT(pat,s,sprev) STACK_PUSH(STK_POS_NOT,pat,s,sprev)
573 #define STACK_PUSH_STOP_BT STACK_PUSH_TYPE(STK_STOP_BT)
574 #define STACK_PUSH_LOOK_BEHIND_NOT(pat,s,sprev) \
575 STACK_PUSH(STK_LOOK_BEHIND_NOT,pat,s,sprev)
577 #define STACK_PUSH_REPEAT(id, pat) do {\
579 stk->type = STK_REPEAT;\
580 stk->u.repeat.num = (id);\
581 stk->u.repeat.pcode = (pat);\
582 stk->u.repeat.count = 0;\
586 #define STACK_PUSH_REPEAT_INC(sindex) do {\
588 stk->type = STK_REPEAT_INC;\
589 stk->u.repeat_inc.si = (sindex);\
593 #define STACK_PUSH_MEM_START(mnum, s) do {\
595 stk->type = STK_MEM_START;\
596 stk->u.mem.num = (mnum);\
597 stk->u.mem.pstr = (s);\
598 stk->u.mem.start = mem_start_stk[mnum];\
599 stk->u.mem.end = mem_end_stk[mnum];\
600 mem_start_stk[mnum] = GET_STACK_INDEX(stk);\
601 mem_end_stk[mnum] = INVALID_STACK_INDEX;\
605 #define STACK_PUSH_MEM_END(mnum, s) do {\
607 stk->type = STK_MEM_END;\
608 stk->u.mem.num = (mnum);\
609 stk->u.mem.pstr = (s);\
610 stk->u.mem.start = mem_start_stk[mnum];\
611 stk->u.mem.end = mem_end_stk[mnum];\
612 mem_end_stk[mnum] = GET_STACK_INDEX(stk);\
616 #define STACK_PUSH_MEM_END_MARK(mnum) do {\
618 stk->type = STK_MEM_END_MARK;\
619 stk->u.mem.num = (mnum);\
623 #define STACK_GET_MEM_START(mnum, k) do {\
626 while (k > stk_base) {\
628 if ((k->type & STK_MASK_MEM_END_OR_MARK) != 0 \
629 && k->u.mem.num == (mnum)) {\
632 else if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
633 if (level == 0) break;\
639 #define STACK_GET_MEM_RANGE(k, mnum, start, end) do {\
642 if (k->type == STK_MEM_START && k->u.mem.num == (mnum)) {\
643 if (level == 0) (start) = k->u.mem.pstr;\
646 else if (k->type == STK_MEM_END && k->u.mem.num == (mnum)) {\
649 (end) = k->u.mem.pstr;\
657 #define STACK_PUSH_NULL_CHECK_START(cnum, s) do {\
659 stk->type = STK_NULL_CHECK_START;\
660 stk->u.null_check.num = (cnum);\
661 stk->u.null_check.pstr = (s);\
665 #define STACK_PUSH_NULL_CHECK_END(cnum) do {\
667 stk->type = STK_NULL_CHECK_END;\
668 stk->u.null_check.num = (cnum);\
672 #define STACK_PUSH_CALL_FRAME(pat) do {\
674 stk->type = STK_CALL_FRAME;\
675 stk->u.call_frame.ret_addr = (pat);\
679 #define STACK_PUSH_RETURN do {\
681 stk->type = STK_RETURN;\
687 #define STACK_BASE_CHECK(p, at) \
688 if ((p) < stk_base) {\
689 fprintf(stderr, "at %s\n", at);\
693 #define STACK_BASE_CHECK(p, at)
696 #define STACK_POP_ONE do {\
698 STACK_BASE_CHECK(stk, "STACK_POP_ONE"); \
701 #define STACK_POP do {\
702 switch (pop_level) {\
703 case STACK_POP_LEVEL_FREE:\
706 STACK_BASE_CHECK(stk, "STACK_POP"); \
707 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
708 ELSE_IF_STATE_CHECK_MARK(stk);\
711 case STACK_POP_LEVEL_MEM_START:\
714 STACK_BASE_CHECK(stk, "STACK_POP 2"); \
715 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
716 else if (stk->type == STK_MEM_START) {\
717 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
718 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
720 ELSE_IF_STATE_CHECK_MARK(stk);\
726 STACK_BASE_CHECK(stk, "STACK_POP 3"); \
727 if ((stk->type & STK_MASK_POP_USED) != 0) break;\
728 else if (stk->type == STK_MEM_START) {\
729 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
730 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
732 else if (stk->type == STK_REPEAT_INC) {\
733 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
735 else if (stk->type == STK_MEM_END) {\
736 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
737 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
739 ELSE_IF_STATE_CHECK_MARK(stk);\
745 #define STACK_POP_TIL_POS_NOT do {\
748 STACK_BASE_CHECK(stk, "STACK_POP_TIL_POS_NOT"); \
749 if (stk->type == STK_POS_NOT) break;\
750 else if (stk->type == STK_MEM_START) {\
751 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
752 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
754 else if (stk->type == STK_REPEAT_INC) {\
755 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
757 else if (stk->type == STK_MEM_END) {\
758 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
759 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
761 ELSE_IF_STATE_CHECK_MARK(stk);\
765 #define STACK_POP_TIL_LOOK_BEHIND_NOT do {\
768 STACK_BASE_CHECK(stk, "STACK_POP_TIL_LOOK_BEHIND_NOT"); \
769 if (stk->type == STK_LOOK_BEHIND_NOT) break;\
770 else if (stk->type == STK_MEM_START) {\
771 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
772 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
774 else if (stk->type == STK_REPEAT_INC) {\
775 STACK_AT(stk->u.repeat_inc.si)->u.repeat.count--;\
777 else if (stk->type == STK_MEM_END) {\
778 mem_start_stk[stk->u.mem.num] = stk->u.mem.start;\
779 mem_end_stk[stk->u.mem.num] = stk->u.mem.end;\
781 ELSE_IF_STATE_CHECK_MARK(stk);\
785 #define STACK_POS_END(k) do {\
789 STACK_BASE_CHECK(k, "STACK_POS_END"); \
790 if (IS_TO_VOID_TARGET(k)) {\
793 else if (k->type == STK_POS) {\
800 #define STACK_STOP_BT_END do {\
801 OnigStackType *k = stk;\
804 STACK_BASE_CHECK(k, "STACK_STOP_BT_END"); \
805 if (IS_TO_VOID_TARGET(k)) {\
808 else if (k->type == STK_STOP_BT) {\
815 #define STACK_NULL_CHECK(isnull,id,s) do {\
816 OnigStackType* k = stk;\
819 STACK_BASE_CHECK(k, "STACK_NULL_CHECK"); \
820 if (k->type == STK_NULL_CHECK_START) {\
821 if (k->u.null_check.num == (id)) {\
822 (isnull) = (k->u.null_check.pstr == (s));\
829 #define STACK_NULL_CHECK_REC(isnull,id,s) do {\
831 OnigStackType* k = stk;\
834 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_REC"); \
835 if (k->type == STK_NULL_CHECK_START) {\
836 if (k->u.null_check.num == (id)) {\
838 (isnull) = (k->u.null_check.pstr == (s));\
844 else if (k->type == STK_NULL_CHECK_END) {\
850 #define STACK_NULL_CHECK_MEMST(isnull,id,s,reg) do {\
851 OnigStackType* k = stk;\
854 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST"); \
855 if (k->type == STK_NULL_CHECK_START) {\
856 if (k->u.null_check.num == (id)) {\
857 if (k->u.null_check.pstr != (s)) {\
865 if (k->type == STK_MEM_START) {\
866 if (k->u.mem.end == INVALID_STACK_INDEX) {\
867 (isnull) = 0; break;\
869 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
870 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
872 endp = (UChar* )k->u.mem.end;\
873 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
874 (isnull) = 0; break;\
876 else if (endp != s) {\
889 #define STACK_NULL_CHECK_MEMST_REC(isnull,id,s,reg) do {\
891 OnigStackType* k = stk;\
894 STACK_BASE_CHECK(k, "STACK_NULL_CHECK_MEMST_REC"); \
895 if (k->type == STK_NULL_CHECK_START) {\
896 if (k->u.null_check.num == (id)) {\
898 if (k->u.null_check.pstr != (s)) {\
906 if (k->type == STK_MEM_START) {\
907 if (k->u.mem.end == INVALID_STACK_INDEX) {\
908 (isnull) = 0; break;\
910 if (BIT_STATUS_AT(reg->bt_mem_end, k->u.mem.num))\
911 endp = STACK_AT(k->u.mem.end)->u.mem.pstr;\
913 endp = (UChar* )k->u.mem.end;\
914 if (STACK_AT(k->u.mem.start)->u.mem.pstr != endp) {\
915 (isnull) = 0; break;\
917 else if (endp != s) {\
931 else if (k->type == STK_NULL_CHECK_END) {\
932 if (k->u.null_check.num == (id)) level++;\
937 #define STACK_GET_REPEAT(id, k) do {\
942 STACK_BASE_CHECK(k, "STACK_GET_REPEAT"); \
943 if (k->type == STK_REPEAT) {\
945 if (k->u.repeat.num == (id)) {\
950 else if (k->type == STK_CALL_FRAME) level--;\
951 else if (k->type == STK_RETURN) level++;\
955 #define STACK_RETURN(addr) do {\
957 OnigStackType* k = stk;\
960 STACK_BASE_CHECK(k, "STACK_RETURN"); \
961 if (k->type == STK_CALL_FRAME) {\
963 (addr) = k->u.call_frame.ret_addr;\
968 else if (k->type == STK_RETURN)\
974 #define STRING_CMP(s1,s2,len) do {\
976 if (*s1++ != *s2++) goto fail;\
980 #define STRING_CMP_IC(case_fold_flag,s1,ps2,len,text_end) do {\
981 if (string_cmp_ic(encode, case_fold_flag, s1, ps2, len, text_end) == 0) \
990 UChar *p1, *p2, *end1, *s2;
998 if (len1 != len2)
return 0;
1001 while (len1-- > 0) {
1002 if (*p1 != *p2)
return 0;
1012 #define STRING_CMP_VALUE(s1,s2,len,is_fail) do {\
1014 while (len-- > 0) {\
1015 if (*s1++ != *s2++) {\
1016 is_fail = 1; break;\
1021 #define STRING_CMP_VALUE_IC(case_fold_flag,s1,ps2,len,text_end,is_fail) do {\
1022 if (string_cmp_ic(encode, case_fold_flag, s1, ps2, len, text_end) == 0) \
1029 #define IS_EMPTY_STR (str == end)
1030 #define ON_STR_BEGIN(s) ((s) == str)
1031 #define ON_STR_END(s) ((s) == end)
1032 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
1033 #define DATA_ENSURE_CHECK1 (s < right_range)
1034 #define DATA_ENSURE_CHECK(n) (s + (n) <= right_range)
1035 #define DATA_ENSURE(n) if (s + (n) > right_range) goto fail
1037 #define DATA_ENSURE_CHECK1 (s < end)
1038 #define DATA_ENSURE_CHECK(n) (s + (n) <= end)
1039 #define DATA_ENSURE(n) if (s + (n) > end) goto fail
1043 #ifdef USE_CAPTURE_HISTORY
1052 while (k < stk_top) {
1057 child = history_node_new();
1060 child->
beg = (int )(k->
u.
mem.pstr - str);
1061 r = history_tree_add_child(node, child);
1062 if (r != 0)
return r;
1064 r = make_capture_history_tree(child, kp, stk_top, str, reg);
1065 if (r != 0)
return r;
1068 child->
end = (int )(k->
u.
mem.pstr - str);
1073 node->
end = (int )(k->
u.
mem.pstr - str);
1085 #ifdef USE_BACKREF_WITH_LEVEL
1086 static int mem_is_in_memp(
int mem,
int num,
UChar* memp)
1091 for (i = 0; i < num; i++) {
1093 if (mem == (
int )m)
return 1;
1098 static int backref_match_at_nested_level(
regex_t* reg
1100 ,
int ignore_case,
int case_fold_flag
1110 while (k >= stk_base) {
1117 else if (level == nest) {
1119 if (mem_is_in_memp(k->
u.
mem.num, mem_num, memp)) {
1120 pstart = k->
u.
mem.pstr;
1122 if (pend - pstart > send - *s)
return 0;
1126 if (ignore_case != 0) {
1128 pstart, &ss, (
int )(pend - pstart), send) == 0)
1133 if (*p++ != *ss++)
return 0;
1143 if (mem_is_in_memp(k->
u.
mem.num, mem_num, memp)) {
1144 pend = k->
u.
mem.pstr;
1156 #ifdef ONIG_DEBUG_STATISTICS
1158 #define USE_TIMEOFDAY
1160 #ifdef USE_TIMEOFDAY
1161 #ifdef HAVE_SYS_TIME_H
1162 #include <sys/time.h>
1164 #ifdef HAVE_UNISTD_H
1168 #define GETTIME(t) gettimeofday(&(t), (struct timezone* )0)
1169 #define TIMEDIFF(te,ts) (((te).tv_usec - (ts).tv_usec) + \
1170 (((te).tv_sec - (ts).tv_sec)*1000000))
1172 #ifdef HAVE_SYS_TIMES_H
1173 #include <sys/times.h>
1175 static struct tms ts, te;
1176 #define GETTIME(t) times(&(t))
1177 #define TIMEDIFF(te,ts) ((te).tms_utime - (ts).tms_utime)
1180 static int OpCounter[256];
1181 static int OpPrevCounter[256];
1182 static unsigned long OpTime[256];
1184 static int OpPrevTarget =
OP_FAIL;
1185 static int MaxStackDepth = 0;
1187 #define MOP_IN(opcode) do {\
1188 if (opcode == OpPrevTarget) OpPrevCounter[OpCurr]++;\
1190 OpCounter[opcode]++;\
1194 #define MOP_OUT do {\
1196 OpTime[OpCurr] += TIMEDIFF(te, ts);\
1200 onig_statistics_init(
void)
1203 for (i = 0; i < 256; i++) {
1204 OpCounter[
i] = OpPrevCounter[
i] = 0; OpTime[
i] = 0;
1210 onig_print_statistics(
FILE* f)
1213 fprintf(f,
" count prev time\n");
1214 for (i = 0; OnigOpInfo[
i].opcode >= 0; i++) {
1215 fprintf(f,
"%8d: %8d: %10ld: %s\n",
1216 OpCounter[i], OpPrevCounter[i], OpTime[i], OnigOpInfo[i].
name);
1218 fprintf(f,
"\nmax stack depth: %d\n", MaxStackDepth);
1221 #define STACK_INC do {\
1223 if (stk - stk_base > MaxStackDepth) \
1224 MaxStackDepth = stk - stk_base;\
1228 #define STACK_INC stk++
1230 #define MOP_IN(opcode)
1250 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
1251 const UChar* right_range,
1257 int i, num_mem, best_len, pop_level;
1265 UChar *s, *q, *sbegin;
1273 #ifdef USE_COMBINATION_EXPLOSION_CHECK
1275 unsigned char* state_check_buff = msa->state_check_buff;
1286 mem_end_stk = mem_start_stk + num_mem;
1291 for (i = 1; i <= num_mem; i++) {
1295 #ifdef ONIG_DEBUG_MATCH
1296 fprintf(stderr,
"match_at: str: %"PRIdPTR
", end: %"PRIdPTR
", start: %"PRIdPTR
", sprev: %"PRIdPTR
"\n",
1298 fprintf(stderr,
"size: %d, start offset: %d\n",
1299 (
int )(end - str), (
int )(sstart - str));
1304 s = (
UChar* )sstart;
1306 #ifdef ONIG_DEBUG_MATCH
1310 fprintf(stderr,
"%4d> \"", (
int )(s - str));
1312 for (i = 0, q = s; i < 7 && q < end; i++) {
1313 len =
enclen(encode, q, end);
1314 while (len-- > 0) *bp++ = *q++;
1316 if (q < end) {
xmemcpy(bp,
"...\"", 4); bp += 4; }
1317 else {
xmemcpy(bp,
"\"", 1); bp += 1; }
1319 fputs((
char* )buf, stderr);
1320 for (i = 0; i < 20 - (bp -
buf); i++) fputc(
' ', stderr);
1322 fprintf(stderr,
"\n");
1332 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
1345 #ifdef USE_POSIX_API_REGION_OPTION
1349 rmt[0].
rm_so = sstart - str;
1350 rmt[0].
rm_eo = s - str;
1351 for (i = 1; i <= num_mem; i++) {
1354 rmt[i].rm_so =
STACK_AT(mem_start_stk[i])->u.mem.pstr - str;
1356 rmt[
i].
rm_so = (
UChar* )((
void* )(mem_start_stk[
i])) - str;
1359 ?
STACK_AT(mem_end_stk[i])->u.mem.pstr
1360 : (
UChar* )((
void* )mem_end_stk[
i])) - str;
1369 region->
beg[0] = (int)(sstart - str);
1370 region->
end[0] = (int)(s - str);
1371 for (i = 1; i <= num_mem; i++) {
1374 ?
STACK_AT(mem_start_stk[i])->u.mem.pstr - str
1375 : (
UChar* )((
void* )mem_start_stk[
i]) - str);
1377 ?
STACK_AT(mem_end_stk[i])->u.mem.pstr - str
1378 : (
UChar* )((
void* )mem_end_stk[
i]) - str);
1385 #ifdef USE_CAPTURE_HISTORY
1396 history_tree_clear(node);
1400 node->
beg = sstart - str;
1401 node->
end = s - str;
1404 r = make_capture_history_tree(region->
history_root, &stkp,
1405 stk, (
UChar* )str, reg);
1412 #ifdef USE_POSIX_API_REGION_OPTION
1418 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
1440 if (*p != *s)
goto fail;
1443 if (*p != *s++)
goto fail;
1473 if (*p != *s)
goto fail;
1475 if (*p != *s)
goto fail;
1484 if (*p != *s)
goto fail;
1486 if (*p != *s)
goto fail;
1488 if (*p != *s)
goto fail;
1497 if (*p != *s)
goto fail;
1499 if (*p != *s)
goto fail;
1501 if (*p != *s)
goto fail;
1503 if (*p != *s)
goto fail;
1512 if (*p != *s)
goto fail;
1514 if (*p != *s)
goto fail;
1516 if (*p != *s)
goto fail;
1518 if (*p != *s)
goto fail;
1520 if (*p != *s)
goto fail;
1530 while (tlen-- > 0) {
1531 if (*p++ != *s++)
goto fail;
1556 if (*p != *q)
goto fail;
1568 if (*p != *s)
goto fail;
1570 if (*p != *s)
goto fail;
1577 if (*p != *s)
goto fail;
1579 if (*p != *s)
goto fail;
1582 if (*p != *s)
goto fail;
1584 if (*p != *s)
goto fail;
1592 if (*p != *s)
goto fail;
1594 if (*p != *s)
goto fail;
1596 if (*p != *s)
goto fail;
1598 if (*p != *s)
goto fail;
1601 if (*p != *s)
goto fail;
1603 if (*p != *s)
goto fail;
1612 while (tlen-- > 0) {
1613 if (*p != *s)
goto fail;
1615 if (*p != *s)
goto fail;
1626 while (tlen-- > 0) {
1627 if (*p != *s)
goto fail;
1629 if (*p != *s)
goto fail;
1631 if (*p != *s)
goto fail;
1644 while (tlen2-- > 0) {
1645 if (*p != *s)
goto fail;
1657 s +=
enclen(encode, s, end);
1672 mb_len =
enclen(encode, s, end);
1678 #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
1712 s +=
enclen(encode, s, end);
1722 goto cc_mb_not_success;
1730 int mb_len =
enclen(encode, s, end);
1736 goto cc_mb_not_success;
1743 #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
1784 mb_len =
enclen(encode, s, end);
1796 n =
enclen(encode, s, end);
1805 n =
enclen(encode, s, end);
1814 n =
enclen(encode, s, end);
1826 n =
enclen(encode, s, end);
1845 n =
enclen(encode, s, end);
1860 n =
enclen(encode, s, end);
1875 #ifdef USE_COMBINATION_EXPLOSION_CHECK
1879 STATE_CHECK_VAL(scv, mem);
1882 STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem);
1883 n =
enclen(encode, s, end);
1897 STATE_CHECK_VAL(scv, mem);
1900 STACK_PUSH_ALT_WITH_STATE_CHECK(p, s, sprev, mem);
1901 n =
enclen(encode, s, end);
1921 s +=
enclen(encode, s, end);
1930 s +=
enclen(encode, s, end);
1971 #ifdef USE_WORD_BEGIN_END
2022 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
2028 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
2036 #ifdef USE_CRNL_AS_LINE_TERMINATOR
2037 else if (ONIGENC_IS_MBC_CRNL(encode, s, end)) {
2047 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
2053 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
2062 #ifdef USE_CRNL_AS_LINE_TERMINATOR
2063 else if (ONIGENC_IS_MBC_CRNL(encode, s, end)) {
2065 ss += enclen(encode, ss);
2076 if (s != msa->
start)
2111 #ifdef USE_SUBEXP_CALL
2152 UChar *pstart, *pend;
2156 if (mem > num_mem)
goto fail;
2161 pstart =
STACK_AT(mem_start_stk[mem])->u.mem.pstr;
2163 pstart = (
UChar* )((
void* )mem_start_stk[mem]);
2166 ?
STACK_AT(mem_end_stk[mem])->u.mem.pstr
2167 : (
UChar* )((
void* )mem_end_stk[mem]));
2172 while (sprev + (len =
enclen(encode, sprev, end)) < s)
2184 UChar *pstart, *pend;
2188 if (mem > num_mem)
goto fail;
2193 pstart =
STACK_AT(mem_start_stk[mem])->u.mem.pstr;
2195 pstart = (
UChar* )((
void* )mem_start_stk[mem]);
2198 ?
STACK_AT(mem_end_stk[mem])->u.mem.pstr
2199 : (
UChar* )((
void* )mem_end_stk[mem]));
2204 while (sprev + (len =
enclen(encode, sprev, end)) < s)
2215 UChar *pstart, *pend, *swork;
2218 for (i = 0; i < tlen; i++) {
2225 pstart =
STACK_AT(mem_start_stk[mem])->u.mem.pstr;
2227 pstart = (
UChar* )((
void* )mem_start_stk[mem]);
2230 ?
STACK_AT(mem_end_stk[mem])->u.mem.pstr
2231 : (
UChar* )((
void* )mem_end_stk[mem]));
2237 if (is_fail)
continue;
2239 while (sprev + (len =
enclen(encode, sprev, end)) < s)
2245 if (i == tlen)
goto fail;
2254 UChar *pstart, *pend, *swork;
2257 for (i = 0; i < tlen; i++) {
2264 pstart =
STACK_AT(mem_start_stk[mem])->u.mem.pstr;
2266 pstart = (
UChar* )((
void* )mem_start_stk[mem]);
2269 ?
STACK_AT(mem_end_stk[mem])->u.mem.pstr
2270 : (
UChar* )((
void* )mem_end_stk[mem]));
2276 if (is_fail)
continue;
2278 while (sprev + (len =
enclen(encode, sprev, end)) < s)
2284 if (i == tlen)
goto fail;
2290 #ifdef USE_BACKREF_WITH_LEVEL
2302 if (backref_match_at_nested_level(reg, stk, stk_base, ic
2303 , case_fold_flag, (
int )level, (
int )tlen, p, &s, end)) {
2304 while (sprev + (len =
enclen(encode, sprev, end)) < s)
2349 #ifdef ONIG_DEBUG_MATCH
2350 fprintf(stderr,
"NULL_CHECK_END: skip id:%d, s:%"PRIdPTR
"\n",
2367 goto unexpected_bytecode_error;
2376 #ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
2384 #ifdef ONIG_DEBUG_MATCH
2385 fprintf(stderr,
"NULL_CHECK_END_MEMST: skip id:%d, s:%"PRIdPTR
"\n",
2388 if (isnull == -1)
goto fail;
2389 goto null_check_found;
2397 #ifdef USE_SUBEXP_CALL
2404 #ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
2410 #ifdef ONIG_DEBUG_MATCH
2411 fprintf(stderr,
"NULL_CHECK_END_MEMST_PUSH: skip id:%d, s:%"PRIdPTR
"\n",
2414 if (isnull == -1)
goto fail;
2415 goto null_check_found;
2441 #ifdef USE_COMBINATION_EXPLOSION_CHECK
2444 STATE_CHECK_VAL(scv, mem);
2448 STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem);
2456 STATE_CHECK_VAL(scv, mem);
2461 STACK_PUSH_ALT_WITH_STATE_CHECK(p + addr, s, sprev, mem);
2469 STATE_CHECK_VAL(scv, mem);
2472 STACK_PUSH_STATE_CHECK(s, mem);
2547 si = repeat_stk[mem];
2577 si = repeat_stk[mem];
2619 sprev = stkp->
u.
state.pstr_prev;
2682 #ifdef USE_SUBEXP_CALL
2710 sprev = stk->
u.
state.pstr_prev;
2712 #ifdef USE_COMBINATION_EXPLOSION_CHECK
2713 if (stk->
u.
state.state_check != 0) {
2724 goto bytecode_error;
2744 unexpected_bytecode_error:
2756 end = (
UChar* )text_end;
2757 end -= target_end - target - 1;
2758 if (end > text_range)
2767 if (*s == *target) {
2770 if (target_end == t ||
memcmp(t, p, target_end - t) == 0)
2778 if (*s == *target) {
2781 if (target_end == t ||
memcmp(t, p, target_end - t) == 0)
2784 s +=
enclen(enc, s, text_end);
2801 while (lowlen > 0) {
2802 if (*t++ != *q++)
return 0;
2817 end = (
UChar* )text_end;
2818 end -= target_end - target - 1;
2819 if (end > text_range)
2829 s +=
enclen(enc, s, text_end);
2838 const UChar* text_end,
const UChar* text_start)
2842 s = (
UChar* )text_end;
2843 s -= (target_end - target);
2845 s = (
UChar* )text_start;
2850 if (*s == *target) {
2853 while (t < target_end) {
2858 if (t == target_end)
2871 const UChar* text_end,
const UChar* text_start)
2875 s = (
UChar* )text_end;
2876 s -= (target_end - target);
2878 s = (
UChar* )text_start;
2884 target, target_end, s, text_end))
2896 const UChar* text_range)
2898 const UChar *s, *se, *t, *
p, *end;
2900 ptrdiff_t skip, tlen1;
2902 #ifdef ONIG_DEBUG_SEARCH
2903 fprintf(stderr,
"bm_search_notrev: text: %"PRIuPTR
", text_end: %"PRIuPTR
", text_range: %"PRIuPTR
"\n",
2904 text, text_end, text_range);
2907 tail = target_end - 1;
2908 tlen1 = tail - target;
2910 if (end + tlen1 > text_end)
2911 end = text_end - tlen1;
2920 if (t == target)
return (
UChar* )s;
2923 skip = reg->
map[*se];
2927 }
while ((s - t) < skip && s < end);
2935 if (t == target)
return (
UChar* )s;
2942 }
while ((s - t) < skip && s < end);
2953 const UChar *s, *t, *
p, *end;
2956 #ifdef ONIG_DEBUG_SEARCH
2957 fprintf(stderr,
"bm_search: text: %"PRIuPTR
", text_end: %"PRIuPTR
", text_range: %"PRIuPTR
"\n",
2958 text, text_end, text_range);
2961 end = text_range + (target_end - target) - 1;
2965 tail = target_end - 1;
2966 s = text + (target_end - target) - 1;
2971 #ifdef ONIG_DEBUG_SEARCH
2972 fprintf(stderr,
"bm_search_loop: pos: %d %s\n",
2973 (
int)(s - text), s);
2976 if (t == target)
return (
UChar* )
p;
2987 if (t == target)
return (
UChar* )
p;
3008 len = (int)(end - s);
3012 for (i = len - 1; i > 0; i--)
3021 const UChar* text_end,
const UChar* text_start)
3025 s = text_end - (target_end - target);
3034 while (t < target_end && *p == *t) {
3037 if (t == target_end)
3051 const UChar *s = text;
3053 while (s < text_range) {
3054 if (map[*s])
return (
UChar* )s;
3056 s +=
enclen(enc, s, text_end);
3064 const UChar* text_start,
const UChar* text_end)
3066 const UChar *s = text_start;
3069 if (map[*s])
return (
UChar* )s;
3084 #if defined(USE_RECOMPILE_API) && defined(USE_MULTI_THREAD_SYSTEM)
3110 #ifdef USE_COMBINATION_EXPLOSION_CHECK
3112 int offset = at - str;
3118 #ifdef USE_POSIX_API_REGION_OPTION
3130 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
3147 #ifdef ONIG_DEBUG_SEARCH
3148 fprintf(stderr,
"forward_search_range: str: %"PRIuPTR
", end: %"PRIuPTR
", s: %"PRIuPTR
", range: %"PRIuPTR
"\n",
3149 str, end, s, range);
3153 if (reg->
dmin > 0) {
3159 while (p < q) p +=
enclen(reg->
enc, p, end);
3186 if (p && p < range) {
3187 if (p - reg->
dmin < s) {
3201 (pprev ? pprev : str), p, end);
3209 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3211 (pprev ? pprev : str),
p);
3217 #ifdef USE_CRNL_AS_LINE_TERMINATOR
3218 && ! ONIGENC_IS_MBC_CRNL(reg->
enc, p, end)
3226 if (reg->
dmax == 0) {
3233 (pprev ? pprev : str), p, end);
3238 *low = p - reg->
dmax;
3241 *low, end, (
const UChar** )low_prev);
3242 if (low_prev &&
IS_NULL(*low_prev))
3244 (pprev ? pprev : s), *low, end);
3249 (pprev ? pprev : str), *low, end);
3254 *high = p - reg->
dmin;
3256 #ifdef ONIG_DEBUG_SEARCH
3258 "forward_search_range success: low: %d, high: %d, dmin: %d, dmax: %d\n",
3259 (
int )(*low - str), (
int )(*high - str), reg->
dmin, reg->
dmax);
3270 #define BM_BACKWARD_SEARCH_LENGTH_THRESHOLD 100
3288 range, adjrange, end, p);
3294 range, adjrange, end, p);
3333 #ifndef USE_NEWLINE_AT_END_OF_STRING_HAS_EMPTY_LINE
3343 #ifdef USE_CRNL_AS_LINE_TERMINATOR
3344 && ! ONIGENC_IS_MBC_CRNL(reg->
enc, p, end)
3357 *low = p - reg->
dmax;
3358 *high = p - reg->
dmin;
3362 #ifdef ONIG_DEBUG_SEARCH
3363 fprintf(stderr,
"backward_search_range: low: %d, high: %d\n",
3364 (
int )(*low - str), (
int )(*high - str));
3370 #ifdef ONIG_DEBUG_SEARCH
3371 fprintf(stderr,
"backward_search_range: fail.\n");
3384 const UChar *orig_start = start;
3385 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
3389 #if defined(USE_RECOMPILE_API) && defined(USE_MULTI_THREAD_SYSTEM)
3414 #ifdef ONIG_DEBUG_SEARCH
3416 "onig_search (entry point): str: %"PRIuPTR
", end: %"PRIuPTR
", start: %"PRIuPTR
", range: %"PRIuPTR
"\n",
3417 str, end - str, start - str, range - str);
3421 #ifdef USE_POSIX_API_REGION_OPTION
3426 if (r)
goto finish_no_msa;
3429 if (start > end || start < str)
goto mismatch_no_msa;
3432 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
3433 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
3434 #define MATCH_AND_RETURN_CHECK(upper_range) \
3435 r = match_at(reg, str, end, (upper_range), s, prev, &msa); \
3436 if (r != ONIG_MISMATCH) {\
3438 if (! IS_FIND_LONGEST(reg->options)) {\
3445 #define MATCH_AND_RETURN_CHECK(upper_range) \
3446 r = match_at(reg, str, end, (upper_range), s, prev, &msa); \
3447 if (r != ONIG_MISMATCH) {\
3455 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
3456 #define MATCH_AND_RETURN_CHECK(none) \
3457 r = match_at(reg, str, end, s, prev, &msa);\
3458 if (r != ONIG_MISMATCH) {\
3460 if (! IS_FIND_LONGEST(reg->options)) {\
3467 #define MATCH_AND_RETURN_CHECK(none) \
3468 r = match_at(reg, str, end, s, prev, &msa);\
3469 if (r != ONIG_MISMATCH) {\
3480 if (reg->
anchor != 0 && str < end) {
3481 UChar *min_semi_end, *max_semi_end;
3493 if (range > start) {
3494 if (start != str)
goto mismatch_no_msa;
3503 goto mismatch_no_msa;
3507 min_semi_end = max_semi_end = (
UChar* )end;
3511 goto mismatch_no_msa;
3513 if (range > start) {
3523 if (start > range)
goto mismatch_no_msa;
3535 if (range > start)
goto mismatch_no_msa;
3541 max_semi_end = (
UChar* )end;
3543 min_semi_end = pre_end;
3545 #ifdef USE_CRNL_AS_LINE_TERMINATOR
3548 ONIGENC_IS_MBC_CRNL(reg->
enc, pre_end, end)) {
3549 min_semi_end = pre_end;
3552 if (min_semi_end > str && start <= min_semi_end) {
3557 min_semi_end = (
UChar* )end;
3563 goto begin_position;
3567 else if (str == end) {
3568 static const UChar address_for_empty_string[] =
"";
3570 #ifdef ONIG_DEBUG_SEARCH
3571 fprintf(stderr,
"onig_search: empty string.\n");
3575 start = end = str = address_for_empty_string;
3580 #ifdef USE_COMBINATION_EXPLOSION_CHECK
3581 msa.state_check_buff = (
void* )0;
3582 msa.state_check_buff_size = 0;
3587 goto mismatch_no_msa;
3590 #ifdef ONIG_DEBUG_SEARCH
3591 fprintf(stderr,
"onig_search(apply anchor): end: %d, start: %d, range: %d\n",
3592 (
int )(end - str), (
int )(start - str), (
int )(range - str));
3596 #ifdef USE_COMBINATION_EXPLOSION_CHECK
3598 int offset = (
MIN(start, range) - str);
3604 if (range > start) {
3611 UChar *sch_range, *low, *high, *low_prev;
3613 sch_range = (
UChar* )range;
3614 if (reg->
dmax != 0) {
3616 sch_range = (
UChar* )end;
3618 sch_range += reg->
dmax;
3619 if (sch_range > end) sch_range = (
UChar* )end;
3629 &low, &high, &low_prev))
goto mismatch;
3639 }
while (s < range);
3644 &low, &high, (
UChar** )
NULL))
goto mismatch;
3651 }
while (s < range);
3661 }
while (s < range);
3668 #ifdef USE_MATCH_RANGE_MUST_BE_INSIDE_OF_SPECIFIED_RANGE
3669 if (orig_start < end)
3670 orig_start +=
enclen(reg->
enc, orig_start, end);
3674 UChar *low, *high, *adjrange, *sch_start;
3679 adjrange = (
UChar* )end;
3684 sch_start = s + reg->
dmax;
3685 if (sch_start > end) sch_start = (
UChar* )end;
3698 }
while (s >= range);
3705 if (reg->
dmax != 0) {
3707 sch_start = (
UChar* )end;
3709 sch_start += reg->
dmax;
3710 if (sch_start > end) sch_start = (
UChar* )end;
3713 start, sch_start, end);
3717 &low, &high) <= 0)
goto mismatch;
3725 }
while (s >= range);
3729 #ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE
3746 #ifdef USE_POSIX_API_REGION_OPTION
3755 fprintf(stderr,
"onig_search: error %d\n", r);
3765 fprintf(stderr,
"onig_search: error %d\n", r);
3808 #ifdef USE_CAPTURE_HISTORY