33OnigCaseFoldType OnigDefaultCaseFoldFlag = ONIGENC_CASE_FOLD_MIN;
35extern OnigCaseFoldType
36onig_get_default_case_fold_flag(
void)
38 return OnigDefaultCaseFoldFlag;
42onig_set_default_case_fold_flag(OnigCaseFoldType case_fold_flag)
44 OnigDefaultCaseFoldFlag = case_fold_flag;
49#ifndef PLATFORM_UNALIGNED_WORD_ACCESS
50static unsigned char PadBuf[WORD_ALIGNMENT_SIZE];
55str_dup(UChar* s, UChar* end)
57 ptrdiff_t
len = end - s;
71swap_node(Node* a, Node* b)
74 c = *a; *a = *b; *b = c;
76 if (NTYPE(a) == NT_STR) {
79 size_t len = sn->end - sn->s;
81 sn->end = sn->s +
len;
85 if (NTYPE(b) == NT_STR) {
88 size_t len = sn->end - sn->s;
90 sn->end = sn->s +
len;
96distance_add(OnigDistance d1, OnigDistance d2)
98 if (d1 == ONIG_INFINITE_DISTANCE || d2 == ONIG_INFINITE_DISTANCE)
99 return ONIG_INFINITE_DISTANCE;
101 if (d1 <= ONIG_INFINITE_DISTANCE - d2)
return d1 + d2;
102 else return ONIG_INFINITE_DISTANCE;
107distance_multiply(OnigDistance d,
int m)
109 if (m == 0)
return 0;
111 if (d < ONIG_INFINITE_DISTANCE / m)
114 return ONIG_INFINITE_DISTANCE;
118bitset_is_empty(BitSetRef bs)
121 for (i = 0; i < BITSET_SIZE; i++) {
122 if (bs[i] != 0)
return 0;
129bitset_on_num(BitSetRef bs)
134 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
135 if (BITSET_AT(bs, i)) n++;
143onig_reg_resize(regex_t *reg)
151 else if (reg->alloc > reg->used) {
152 unsigned char *new_ptr =
xrealloc(reg->p, reg->used);
155 reg->alloc = reg->used;
159 }
while ((reg = reg->chain) != 0);
163onig_bbuf_init(BBuf* buf, OnigDistance size)
170 buf->p = (UChar* )
xmalloc(size);
171 if (IS_NULL(buf->p))
return(ONIGERR_MEMORY);
174 buf->alloc = (
unsigned int )size;
180#ifdef USE_SUBEXP_CALL
188 CHECK_NULL_RETURN_MEMERR(p);
190 uslist->alloc = size;
207 if (uslist->num >= uslist->alloc) {
208 size = uslist->alloc * 2;
210 CHECK_NULL_RETURN_MEMERR(p);
211 uslist->alloc = size;
215 uslist->us[uslist->num].offset = offset;
216 uslist->us[uslist->num].target = node;
224add_opcode(regex_t* reg,
int opcode)
228 if (reg->used > MAX_COMPILED_PROGRAM_SIZE)
229 return ONIGERR_TOO_BIG_COMPILED_PROGRAM;
230 BBUF_ADD1(reg, opcode);
234#ifdef USE_COMBINATION_EXPLOSION_CHECK
236add_state_check_num(regex_t* reg,
int num)
238 StateCheckNumType n = (StateCheckNumType )num;
240 BBUF_ADD(reg, &n, SIZE_STATE_CHECK_NUM);
246add_rel_addr(regex_t* reg,
int addr)
248 RelAddrType ra = (RelAddrType )addr;
250 BBUF_ADD(reg, &ra, SIZE_RELADDR);
255add_abs_addr(regex_t* reg,
int addr)
257 AbsAddrType ra = (AbsAddrType )addr;
259 BBUF_ADD(reg, &ra, SIZE_ABSADDR);
264add_length(regex_t* reg, OnigDistance
len)
266 LengthType l = (LengthType )
len;
268 BBUF_ADD(reg, &l, SIZE_LENGTH);
273add_mem_num(regex_t* reg,
int num)
275 MemNumType n = (MemNumType )num;
277 BBUF_ADD(reg, &n, SIZE_MEMNUM);
283add_pointer(regex_t* reg,
void* addr)
285 PointerType ptr = (PointerType )addr;
287 BBUF_ADD(reg, &ptr, SIZE_POINTER);
293add_option(regex_t* reg, OnigOptionType option)
295 BBUF_ADD(reg, &option, SIZE_OPTION);
300add_opcode_rel_addr(regex_t* reg,
int opcode,
int addr)
304 r = add_opcode(reg, opcode);
306 r = add_rel_addr(reg, addr);
311add_bytes(regex_t* reg, UChar* bytes, OnigDistance
len)
313 BBUF_ADD(reg, bytes,
len);
318add_bitset(regex_t* reg, BitSetRef bs)
320 BBUF_ADD(reg, bs, SIZE_BITSET);
325add_opcode_option(regex_t* reg,
int opcode, OnigOptionType option)
329 r = add_opcode(reg, opcode);
331 r = add_option(reg, option);
335static int compile_length_tree(Node* node, regex_t* reg);
336static int compile_tree(Node* node, regex_t* reg);
339#define IS_NEED_STR_LEN_OP_EXACT(op) \
340 ((op) == OP_EXACTN || (op) == OP_EXACTMB2N ||\
341 (op) == OP_EXACTMB3N || (op) == OP_EXACTMBN || (op) == OP_EXACTN_IC)
344select_str_opcode(
int mb_len, OnigDistance byte_len,
int ignore_case)
347 OnigDistance str_len = roomof(byte_len, mb_len);
351 case 1: op = OP_EXACT1_IC;
break;
352 default: op = OP_EXACTN_IC;
break;
359 case 1: op = OP_EXACT1;
break;
360 case 2: op = OP_EXACT2;
break;
361 case 3: op = OP_EXACT3;
break;
362 case 4: op = OP_EXACT4;
break;
363 case 5: op = OP_EXACT5;
break;
364 default: op = OP_EXACTN;
break;
370 case 1: op = OP_EXACTMB2N1;
break;
371 case 2: op = OP_EXACTMB2N2;
break;
372 case 3: op = OP_EXACTMB2N3;
break;
373 default: op = OP_EXACTMB2N;
break;
390compile_tree_empty_check(Node* node, regex_t* reg,
int empty_info)
393 int saved_num_null_check = reg->num_null_check;
395 if (empty_info != 0) {
396 r = add_opcode(reg, OP_NULL_CHECK_START);
398 r = add_mem_num(reg, reg->num_null_check);
400 reg->num_null_check++;
401 if ((MemNumType)reg->num_null_check <= 0)
return ONIGERR_TOO_MANY_NULL_CHECK;
404 r = compile_tree(node, reg);
407 if (empty_info != 0) {
408 if (empty_info == NQ_TARGET_IS_EMPTY)
409 r = add_opcode(reg, OP_NULL_CHECK_END);
410 else if (empty_info == NQ_TARGET_IS_EMPTY_MEM)
411 r = add_opcode(reg, OP_NULL_CHECK_END_MEMST);
412 else if (empty_info == NQ_TARGET_IS_EMPTY_REC)
413 r = add_opcode(reg, OP_NULL_CHECK_END_MEMST_PUSH);
416 r = add_mem_num(reg, saved_num_null_check);
421#ifdef USE_SUBEXP_CALL
423compile_call(
CallNode* node, regex_t* reg)
427 r = add_opcode(reg, OP_CALL);
429 r = unset_addr_list_add(node->unset_addr_list, BBUF_GET_OFFSET_POS(reg),
432 r = add_abs_addr(reg, 0 );
438compile_tree_n_times(Node* node,
int n, regex_t* reg)
442 for (i = 0; i < n; i++) {
443 r = compile_tree(node, reg);
450add_compile_string_length(UChar* s ARG_UNUSED,
int mb_len, OnigDistance byte_len,
451 regex_t* reg ARG_UNUSED,
int ignore_case)
454 int op = select_str_opcode(mb_len, byte_len, ignore_case);
458 if (op == OP_EXACTMBN)
len += SIZE_LENGTH;
459 if (IS_NEED_STR_LEN_OP_EXACT(op))
462 len += (int )byte_len;
467add_compile_string(UChar* s,
int mb_len, OnigDistance byte_len,
468 regex_t* reg,
int ignore_case)
470 int op = select_str_opcode(mb_len, byte_len, ignore_case);
473 if (op == OP_EXACTMBN)
474 add_length(reg, mb_len);
476 if (IS_NEED_STR_LEN_OP_EXACT(op)) {
477 if (op == OP_EXACTN_IC)
478 add_length(reg, byte_len);
480 add_length(reg, byte_len / mb_len);
483 add_bytes(reg, s, byte_len);
489compile_length_string_node(Node* node, regex_t* reg)
491 int rlen, r,
len, prev_len, blen, ambig;
492 OnigEncoding enc = reg->enc;
497 if (sn->end <= sn->s)
500 ambig = NSTRING_IS_AMBIG(node);
503 prev_len = enclen(enc, p, sn->end);
508 for (; p < sn->end; ) {
509 len = enclen(enc, p, sn->end);
510 if (
len == prev_len || ambig) {
514 r = add_compile_string_length(prev, prev_len, blen, reg, ambig);
522 r = add_compile_string_length(prev, prev_len, blen, reg, ambig);
528compile_length_string_raw_node(
StrNode* sn, regex_t* reg)
530 if (sn->end <= sn->s)
533 return add_compile_string_length(sn->s, 1 , sn->end - sn->s, reg, 0);
537compile_string_node(Node* node, regex_t* reg)
539 int r,
len, prev_len, blen, ambig;
540 OnigEncoding enc = reg->enc;
541 UChar *p, *prev, *end;
545 if (sn->end <= sn->s)
549 ambig = NSTRING_IS_AMBIG(node);
552 prev_len = enclen(enc, p, end);
557 len = enclen(enc, p, end);
558 if (
len == prev_len || ambig) {
562 r = add_compile_string(prev, prev_len, blen, reg, ambig);
572 return add_compile_string(prev, prev_len, blen, reg, ambig);
576compile_string_raw_node(
StrNode* sn, regex_t* reg)
578 if (sn->end <= sn->s)
581 return add_compile_string(sn->s, 1 , sn->end - sn->s, reg, 0);
585add_multi_byte_cclass(BBuf* mbuf, regex_t* reg)
587#ifdef PLATFORM_UNALIGNED_WORD_ACCESS
588 add_length(reg, mbuf->used);
589 return add_bytes(reg, mbuf->p, mbuf->used);
592 UChar* p = BBUF_GET_ADD_ADDRESS(reg) + SIZE_LENGTH;
594 GET_ALIGNMENT_PAD_SIZE(p, pad_size);
595 add_length(reg, mbuf->used + (WORD_ALIGNMENT_SIZE - 1));
596 if (pad_size != 0) add_bytes(reg, PadBuf, pad_size);
598 r = add_bytes(reg, mbuf->p, mbuf->used);
601 pad_size = (WORD_ALIGNMENT_SIZE - 1) - pad_size;
602 if (pad_size != 0) add_bytes(reg, PadBuf, pad_size);
608compile_length_cclass_node(
CClassNode* cc, regex_t* reg)
612 if (IS_NULL(cc->mbuf)) {
613 len = SIZE_OPCODE + SIZE_BITSET;
616 if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {
620 len = SIZE_OPCODE + SIZE_BITSET;
622#ifdef PLATFORM_UNALIGNED_WORD_ACCESS
623 len += SIZE_LENGTH + cc->mbuf->used;
625 len += SIZE_LENGTH + cc->mbuf->used + (WORD_ALIGNMENT_SIZE - 1);
633compile_cclass_node(
CClassNode* cc, regex_t* reg)
637 if (IS_NULL(cc->mbuf)) {
638 if (IS_NCCLASS_NOT(cc))
639 add_opcode(reg, OP_CCLASS_NOT);
641 add_opcode(reg, OP_CCLASS);
643 r = add_bitset(reg, cc->bs);
646 if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {
647 if (IS_NCCLASS_NOT(cc))
648 add_opcode(reg, OP_CCLASS_MB_NOT);
650 add_opcode(reg, OP_CCLASS_MB);
652 r = add_multi_byte_cclass(cc->mbuf, reg);
655 if (IS_NCCLASS_NOT(cc))
656 add_opcode(reg, OP_CCLASS_MIX_NOT);
658 add_opcode(reg, OP_CCLASS_MIX);
660 r = add_bitset(reg, cc->bs);
662 r = add_multi_byte_cclass(cc->mbuf, reg);
670entry_repeat_range(regex_t* reg,
int id,
int lower,
int upper)
672#define REPEAT_RANGE_ALLOC 4
676 if (reg->repeat_range_alloc == 0) {
678 CHECK_NULL_RETURN_MEMERR(p);
679 reg->repeat_range = p;
680 reg->repeat_range_alloc = REPEAT_RANGE_ALLOC;
682 else if (reg->repeat_range_alloc <=
id) {
684 n = reg->repeat_range_alloc + REPEAT_RANGE_ALLOC;
687 CHECK_NULL_RETURN_MEMERR(p);
688 reg->repeat_range = p;
689 reg->repeat_range_alloc = n;
692 p = reg->repeat_range;
696 p[id].upper = (IS_REPEAT_INFINITE(upper) ? 0x7fffffff : upper);
701compile_range_repeat_node(
QtfrNode* qn,
int target_len,
int empty_info,
705 int num_repeat = reg->num_repeat;
707 r = add_opcode(reg, qn->greedy ? OP_REPEAT : OP_REPEAT_NG);
709 r = add_mem_num(reg, num_repeat);
711 if ((MemNumType)reg->num_repeat <= 0)
return ONIGERR_TOO_MANY_RANGE_REPEAT;
713 r = add_rel_addr(reg, target_len + SIZE_OP_REPEAT_INC);
716 r = entry_repeat_range(reg, num_repeat, qn->lower, qn->upper);
719 r = compile_tree_empty_check(qn->target, reg, empty_info);
723#ifdef USE_SUBEXP_CALL
726 IS_QUANTIFIER_IN_REPEAT(qn)) {
727 r = add_opcode(reg, qn->greedy ? OP_REPEAT_INC_SG : OP_REPEAT_INC_NG_SG);
730 r = add_opcode(reg, qn->greedy ? OP_REPEAT_INC : OP_REPEAT_INC_NG);
733 r = add_mem_num(reg, num_repeat);
738is_anychar_star_quantifier(
QtfrNode* qn)
740 if (qn->greedy && IS_REPEAT_INFINITE(qn->upper) &&
741 NTYPE(qn->target) == NT_CANY)
747#define QUANTIFIER_EXPAND_LIMIT_SIZE 50
750#define IS_EXPAND_LIMIT_OK(tlen, n) \
751 ((n) <= 0 || (tlen) <= QUANTIFIER_EXPAND_LIMIT_SIZE / (n))
752#define CKN_ON (ckn > 0)
754#ifdef USE_COMBINATION_EXPLOSION_CHECK
757compile_length_quantifier_node(
QtfrNode* qn, regex_t* reg)
759 int len, mod_tlen, cklen;
761 int infinite = IS_REPEAT_INFINITE(qn->upper);
762 int empty_info = qn->target_empty_info;
763 int tlen = compile_length_tree(qn->target, reg);
765 if (tlen < 0)
return tlen;
767 ckn = ((reg->num_comb_exp_check > 0) ? qn->comb_exp_check_num : 0);
769 cklen = (CKN_ON ? SIZE_STATE_CHECK_NUM: 0);
772 if (NTYPE(qn->target) == NT_CANY) {
773 if (qn->greedy && infinite) {
774 if (IS_NOT_NULL(qn->next_head_exact) && !CKN_ON)
775 return SIZE_OP_ANYCHAR_STAR_PEEK_NEXT + tlen * qn->lower + cklen;
777 return SIZE_OP_ANYCHAR_STAR + tlen * qn->lower + cklen;
782 mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
786 if (infinite && qn->lower <= 1) {
793 len += SIZE_OP_PUSH + cklen + mod_tlen + SIZE_OP_JUMP;
801 len += mod_tlen + SIZE_OP_PUSH + cklen;
804 else if (qn->upper == 0) {
805 if (qn->is_referred != 0)
806 len = SIZE_OP_JUMP + tlen;
810 else if (qn->upper == 1 && qn->greedy) {
811 if (qn->lower == 0) {
813 len = SIZE_OP_STATE_CHECK_PUSH + tlen;
816 len = SIZE_OP_PUSH + tlen;
823 else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) {
824 len = SIZE_OP_PUSH + cklen + SIZE_OP_JUMP + tlen;
827 len = SIZE_OP_REPEAT_INC
828 + mod_tlen + SIZE_OPCODE + SIZE_RELADDR + SIZE_MEMNUM;
830 len += SIZE_OP_STATE_CHECK;
837compile_quantifier_node(
QtfrNode* qn, regex_t* reg)
841 int infinite = IS_REPEAT_INFINITE(qn->upper);
842 int empty_info = qn->target_empty_info;
843 int tlen = compile_length_tree(qn->target, reg);
845 if (tlen < 0)
return tlen;
847 ckn = ((reg->num_comb_exp_check > 0) ? qn->comb_exp_check_num : 0);
849 if (is_anychar_star_quantifier(qn)) {
850 r = compile_tree_n_times(qn->target, qn->lower, reg);
852 if (IS_NOT_NULL(qn->next_head_exact) && !CKN_ON) {
853 if (IS_MULTILINE(reg->options))
854 r = add_opcode(reg, OP_ANYCHAR_ML_STAR_PEEK_NEXT);
856 r = add_opcode(reg, OP_ANYCHAR_STAR_PEEK_NEXT);
859 r = add_state_check_num(reg, ckn);
863 return add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
866 if (IS_MULTILINE(reg->options)) {
867 r = add_opcode(reg, (CKN_ON ?
868 OP_STATE_CHECK_ANYCHAR_ML_STAR
869 : OP_ANYCHAR_ML_STAR));
872 r = add_opcode(reg, (CKN_ON ?
873 OP_STATE_CHECK_ANYCHAR_STAR
878 r = add_state_check_num(reg, ckn);
885 mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
889 if (infinite && qn->lower <= 1) {
891 if (qn->lower == 1) {
892 r = add_opcode_rel_addr(reg, OP_JUMP,
893 (CKN_ON ? SIZE_OP_STATE_CHECK_PUSH : SIZE_OP_PUSH));
898 r = add_opcode(reg, OP_STATE_CHECK_PUSH);
900 r = add_state_check_num(reg, ckn);
902 r = add_rel_addr(reg, mod_tlen + SIZE_OP_JUMP);
905 r = add_opcode_rel_addr(reg, OP_PUSH, mod_tlen + SIZE_OP_JUMP);
908 r = compile_tree_empty_check(qn->target, reg, empty_info);
910 r = add_opcode_rel_addr(reg, OP_JUMP,
911 -(mod_tlen + (
int )SIZE_OP_JUMP
912 + (
int )(CKN_ON ? SIZE_OP_STATE_CHECK_PUSH : SIZE_OP_PUSH)));
915 if (qn->lower == 0) {
916 r = add_opcode_rel_addr(reg, OP_JUMP, mod_tlen);
919 r = compile_tree_empty_check(qn->target, reg, empty_info);
922 r = add_opcode(reg, OP_STATE_CHECK_PUSH_OR_JUMP);
924 r = add_state_check_num(reg, ckn);
926 r = add_rel_addr(reg,
927 -(mod_tlen + (
int )SIZE_OP_STATE_CHECK_PUSH_OR_JUMP));
930 r = add_opcode_rel_addr(reg, OP_PUSH, -(mod_tlen + (
int )SIZE_OP_PUSH));
933 else if (qn->upper == 0) {
934 if (qn->is_referred != 0) {
935 r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
937 r = compile_tree(qn->target, reg);
942 else if (qn->upper == 1 && qn->greedy) {
943 if (qn->lower == 0) {
945 r = add_opcode(reg, OP_STATE_CHECK_PUSH);
947 r = add_state_check_num(reg, ckn);
949 r = add_rel_addr(reg, tlen);
952 r = add_opcode_rel_addr(reg, OP_PUSH, tlen);
957 r = compile_tree(qn->target, reg);
959 else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) {
961 r = add_opcode(reg, OP_STATE_CHECK_PUSH);
963 r = add_state_check_num(reg, ckn);
965 r = add_rel_addr(reg, SIZE_OP_JUMP);
968 r = add_opcode_rel_addr(reg, OP_PUSH, SIZE_OP_JUMP);
972 r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
974 r = compile_tree(qn->target, reg);
977 r = compile_range_repeat_node(qn, mod_tlen, empty_info, reg);
980 r = add_opcode(reg, OP_STATE_CHECK);
982 r = add_state_check_num(reg, ckn);
991compile_length_quantifier_node(
QtfrNode* qn, regex_t* reg)
994 int infinite = IS_REPEAT_INFINITE(qn->upper);
995 int empty_info = qn->target_empty_info;
996 int tlen = compile_length_tree(qn->target, reg);
998 if (tlen < 0)
return tlen;
1001 if (NTYPE(qn->target) == NT_CANY) {
1002 if (qn->greedy && infinite) {
1003 if (IS_NOT_NULL(qn->next_head_exact))
1004 return SIZE_OP_ANYCHAR_STAR_PEEK_NEXT + tlen * qn->lower;
1006 return SIZE_OP_ANYCHAR_STAR + tlen * qn->lower;
1010 if (empty_info != 0)
1011 mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
1016 (qn->lower <= 1 || IS_EXPAND_LIMIT_OK(tlen, qn->lower))) {
1017 if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
1021 len = tlen * qn->lower;
1025#ifdef USE_OP_PUSH_OR_JUMP_EXACT
1026 if (IS_NOT_NULL(qn->head_exact))
1027 len += SIZE_OP_PUSH_OR_JUMP_EXACT1 + mod_tlen + SIZE_OP_JUMP;
1030 if (IS_NOT_NULL(qn->next_head_exact))
1031 len += SIZE_OP_PUSH_IF_PEEK_NEXT + mod_tlen + SIZE_OP_JUMP;
1033 len += SIZE_OP_PUSH + mod_tlen + SIZE_OP_JUMP;
1036 len += SIZE_OP_JUMP + mod_tlen + SIZE_OP_PUSH;
1038 else if (qn->upper == 0 && qn->is_referred != 0) {
1039 len = SIZE_OP_JUMP + tlen;
1041 else if (!infinite && qn->greedy &&
1043 IS_EXPAND_LIMIT_OK(tlen + SIZE_OP_PUSH, qn->upper))) {
1044 len = tlen * qn->lower;
1045 len += (SIZE_OP_PUSH + tlen) * (qn->upper - qn->lower);
1047 else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) {
1048 len = SIZE_OP_PUSH + SIZE_OP_JUMP + tlen;
1051 len = SIZE_OP_REPEAT_INC
1052 + mod_tlen + SIZE_OPCODE + SIZE_RELADDR + SIZE_MEMNUM;
1059compile_quantifier_node(
QtfrNode* qn, regex_t* reg)
1062 int infinite = IS_REPEAT_INFINITE(qn->upper);
1063 int empty_info = qn->target_empty_info;
1064 int tlen = compile_length_tree(qn->target, reg);
1066 if (tlen < 0)
return tlen;
1068 if (is_anychar_star_quantifier(qn)) {
1069 r = compile_tree_n_times(qn->target, qn->lower, reg);
1071 if (IS_NOT_NULL(qn->next_head_exact)) {
1072 if (IS_MULTILINE(reg->options))
1073 r = add_opcode(reg, OP_ANYCHAR_ML_STAR_PEEK_NEXT);
1075 r = add_opcode(reg, OP_ANYCHAR_STAR_PEEK_NEXT);
1077 return add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
1080 if (IS_MULTILINE(reg->options))
1081 return add_opcode(reg, OP_ANYCHAR_ML_STAR);
1083 return add_opcode(reg, OP_ANYCHAR_STAR);
1087 if (empty_info != 0)
1088 mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
1093 (qn->lower <= 1 || IS_EXPAND_LIMIT_OK(tlen, qn->lower))) {
1094 if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
1096#ifdef USE_OP_PUSH_OR_JUMP_EXACT
1097 if (IS_NOT_NULL(qn->head_exact))
1098 r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH_OR_JUMP_EXACT1);
1101 if (IS_NOT_NULL(qn->next_head_exact))
1102 r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH_IF_PEEK_NEXT);
1104 r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH);
1107 r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_JUMP);
1112 r = compile_tree_n_times(qn->target, qn->lower, reg);
1117#ifdef USE_OP_PUSH_OR_JUMP_EXACT
1118 if (IS_NOT_NULL(qn->head_exact)) {
1119 r = add_opcode_rel_addr(reg, OP_PUSH_OR_JUMP_EXACT1,
1120 mod_tlen + SIZE_OP_JUMP);
1122 add_bytes(reg, NSTR(qn->head_exact)->s, 1);
1123 r = compile_tree_empty_check(qn->target, reg, empty_info);
1125 r = add_opcode_rel_addr(reg, OP_JUMP,
1126 -(mod_tlen + (
int )SIZE_OP_JUMP + (
int )SIZE_OP_PUSH_OR_JUMP_EXACT1));
1130 if (IS_NOT_NULL(qn->next_head_exact)) {
1131 r = add_opcode_rel_addr(reg, OP_PUSH_IF_PEEK_NEXT,
1132 mod_tlen + SIZE_OP_JUMP);
1134 add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
1135 r = compile_tree_empty_check(qn->target, reg, empty_info);
1137 r = add_opcode_rel_addr(reg, OP_JUMP,
1138 -(mod_tlen + (
int )SIZE_OP_JUMP + (
int )SIZE_OP_PUSH_IF_PEEK_NEXT));
1141 r = add_opcode_rel_addr(reg, OP_PUSH, mod_tlen + SIZE_OP_JUMP);
1143 r = compile_tree_empty_check(qn->target, reg, empty_info);
1145 r = add_opcode_rel_addr(reg, OP_JUMP,
1146 -(mod_tlen + (
int )SIZE_OP_JUMP + (
int )SIZE_OP_PUSH));
1150 r = add_opcode_rel_addr(reg, OP_JUMP, mod_tlen);
1152 r = compile_tree_empty_check(qn->target, reg, empty_info);
1154 r = add_opcode_rel_addr(reg, OP_PUSH, -(mod_tlen + (
int )SIZE_OP_PUSH));
1157 else if (qn->upper == 0 && qn->is_referred != 0) {
1158 r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
1160 r = compile_tree(qn->target, reg);
1162 else if (!infinite && qn->greedy &&
1164 IS_EXPAND_LIMIT_OK(tlen + SIZE_OP_PUSH, qn->upper))) {
1165 int n = qn->upper - qn->lower;
1167 r = compile_tree_n_times(qn->target, qn->lower, reg);
1170 for (i = 0; i < n; i++) {
1171 r = add_opcode_rel_addr(reg, OP_PUSH,
1172 (n - i) * tlen + (n - i - 1) * SIZE_OP_PUSH);
1174 r = compile_tree(qn->target, reg);
1178 else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) {
1179 r = add_opcode_rel_addr(reg, OP_PUSH, SIZE_OP_JUMP);
1181 r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
1183 r = compile_tree(qn->target, reg);
1186 r = compile_range_repeat_node(qn, mod_tlen, empty_info, reg);
1193compile_length_option_node(
EncloseNode* node, regex_t* reg)
1196 OnigOptionType prev = reg->options;
1198 reg->options = node->option;
1199 tlen = compile_length_tree(node->target, reg);
1200 reg->options = prev;
1202 if (tlen < 0)
return tlen;
1204 if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1205 return SIZE_OP_SET_OPTION_PUSH + SIZE_OP_SET_OPTION + SIZE_OP_FAIL
1206 + tlen + SIZE_OP_SET_OPTION;
1213compile_option_node(
EncloseNode* node, regex_t* reg)
1216 OnigOptionType prev = reg->options;
1218 if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1219 r = add_opcode_option(reg, OP_SET_OPTION_PUSH, node->option);
1221 r = add_opcode_option(reg, OP_SET_OPTION, prev);
1223 r = add_opcode(reg, OP_FAIL);
1227 reg->options = node->option;
1228 r = compile_tree(node->target, reg);
1229 reg->options = prev;
1231 if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1233 r = add_opcode_option(reg, OP_SET_OPTION, prev);
1239compile_length_enclose_node(
EncloseNode* node, regex_t* reg)
1244 if (node->type == ENCLOSE_OPTION)
1245 return compile_length_option_node(node, reg);
1248 tlen = compile_length_tree(node->target, reg);
1249 if (tlen < 0)
return tlen;
1254 switch (node->type) {
1255 case ENCLOSE_MEMORY:
1256#ifdef USE_SUBEXP_CALL
1257 if (IS_ENCLOSE_CALLED(node)) {
1258 len = SIZE_OP_MEMORY_START_PUSH + tlen
1259 + SIZE_OP_CALL + SIZE_OP_JUMP + SIZE_OP_RETURN;
1260 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1261 len += (IS_ENCLOSE_RECURSION(node)
1262 ? SIZE_OP_MEMORY_END_PUSH_REC : SIZE_OP_MEMORY_END_PUSH);
1264 len += (IS_ENCLOSE_RECURSION(node)
1265 ? SIZE_OP_MEMORY_END_REC : SIZE_OP_MEMORY_END);
1267 else if (IS_ENCLOSE_RECURSION(node)) {
1268 len = SIZE_OP_MEMORY_START_PUSH;
1269 len += tlen + (BIT_STATUS_AT(reg->bt_mem_end, node->regnum)
1270 ? SIZE_OP_MEMORY_END_PUSH_REC : SIZE_OP_MEMORY_END_REC);
1275 if (BIT_STATUS_AT(reg->bt_mem_start, node->regnum))
1276 len = SIZE_OP_MEMORY_START_PUSH;
1278 len = SIZE_OP_MEMORY_START;
1280 len += tlen + (BIT_STATUS_AT(reg->bt_mem_end, node->regnum)
1281 ? SIZE_OP_MEMORY_END_PUSH : SIZE_OP_MEMORY_END);
1285 case ENCLOSE_STOP_BACKTRACK:
1289#ifndef USE_MATCH_CACHE
1290 if (IS_ENCLOSE_STOP_BT_SIMPLE_REPEAT(node)) {
1291 QtfrNode* qn = NQTFR(node->target);
1292 tlen = compile_length_tree(qn->target, reg);
1293 if (tlen < 0)
return tlen;
1295 len = tlen * qn->lower
1296 + SIZE_OP_PUSH + tlen + SIZE_OP_POP + SIZE_OP_JUMP;
1300 len = SIZE_OP_PUSH_STOP_BT + tlen + SIZE_OP_POP_STOP_BT;
1301#ifndef USE_MATCH_CACHE
1306 case ENCLOSE_CONDITION:
1307 len = SIZE_OP_CONDITION;
1308 if (NTYPE(node->target) == NT_ALT) {
1309 Node* x = node->target;
1311 tlen = compile_length_tree(NCAR(x), reg);
1312 if (tlen < 0)
return tlen;
1313 len += tlen + SIZE_OP_JUMP;
1314 if (NCDR(x) == NULL)
return ONIGERR_PARSER_BUG;
1316 tlen = compile_length_tree(NCAR(x), reg);
1317 if (tlen < 0)
return tlen;
1319 if (NCDR(x) != NULL)
return ONIGERR_INVALID_CONDITION_PATTERN;
1322 return ONIGERR_PARSER_BUG;
1326 case ENCLOSE_ABSENT:
1327 len = SIZE_OP_PUSH_ABSENT_POS + SIZE_OP_ABSENT + tlen + SIZE_OP_ABSENT_END;
1331 return ONIGERR_TYPE_BUG;
1338static int get_char_length_tree(Node* node, regex_t* reg,
int*
len);
1341compile_enclose_node(
EncloseNode* node, regex_t* reg)
1345 if (node->type == ENCLOSE_OPTION)
1346 return compile_option_node(node, reg);
1348 switch (node->type) {
1349 case ENCLOSE_MEMORY:
1350#ifdef USE_SUBEXP_CALL
1351 if (IS_ENCLOSE_CALLED(node)) {
1352 r = add_opcode(reg, OP_CALL);
1354 node->call_addr = BBUF_GET_OFFSET_POS(reg) + SIZE_ABSADDR + SIZE_OP_JUMP;
1355 node->state |= NST_ADDR_FIXED;
1356 r = add_abs_addr(reg, (
int )node->call_addr);
1358 len = compile_length_tree(node->target, reg);
1360 len += (SIZE_OP_MEMORY_START_PUSH + SIZE_OP_RETURN);
1361 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1362 len += (IS_ENCLOSE_RECURSION(node)
1363 ? SIZE_OP_MEMORY_END_PUSH_REC : SIZE_OP_MEMORY_END_PUSH);
1365 len += (IS_ENCLOSE_RECURSION(node)
1366 ? SIZE_OP_MEMORY_END_REC : SIZE_OP_MEMORY_END);
1368 r = add_opcode_rel_addr(reg, OP_JUMP,
len);
1372 if (BIT_STATUS_AT(reg->bt_mem_start, node->regnum))
1373 r = add_opcode(reg, OP_MEMORY_START_PUSH);
1375 r = add_opcode(reg, OP_MEMORY_START);
1377 r = add_mem_num(reg, node->regnum);
1379 r = compile_tree(node->target, reg);
1381#ifdef USE_SUBEXP_CALL
1382 if (IS_ENCLOSE_CALLED(node)) {
1383 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1384 r = add_opcode(reg, (IS_ENCLOSE_RECURSION(node)
1385 ? OP_MEMORY_END_PUSH_REC : OP_MEMORY_END_PUSH));
1387 r = add_opcode(reg, (IS_ENCLOSE_RECURSION(node)
1388 ? OP_MEMORY_END_REC : OP_MEMORY_END));
1391 r = add_mem_num(reg, node->regnum);
1393 r = add_opcode(reg, OP_RETURN);
1395 else if (IS_ENCLOSE_RECURSION(node)) {
1396 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1397 r = add_opcode(reg, OP_MEMORY_END_PUSH_REC);
1399 r = add_opcode(reg, OP_MEMORY_END_REC);
1401 r = add_mem_num(reg, node->regnum);
1406 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1407 r = add_opcode(reg, OP_MEMORY_END_PUSH);
1409 r = add_opcode(reg, OP_MEMORY_END);
1411 r = add_mem_num(reg, node->regnum);
1415 case ENCLOSE_STOP_BACKTRACK:
1419#ifndef USE_MATCH_CACHE
1420 if (IS_ENCLOSE_STOP_BT_SIMPLE_REPEAT(node)) {
1421 QtfrNode* qn = NQTFR(node->target);
1422 r = compile_tree_n_times(qn->target, qn->lower, reg);
1425 len = compile_length_tree(qn->target, reg);
1428 r = add_opcode_rel_addr(reg, OP_PUSH,
len + SIZE_OP_POP + SIZE_OP_JUMP);
1430 r = compile_tree(qn->target, reg);
1432 r = add_opcode(reg, OP_POP);
1434 r = add_opcode_rel_addr(reg, OP_JUMP,
1435 -((
int )SIZE_OP_PUSH +
len + (
int )SIZE_OP_POP + (
int )SIZE_OP_JUMP));
1439 r = add_opcode(reg, OP_PUSH_STOP_BT);
1441 r = compile_tree(node->target, reg);
1443 r = add_opcode(reg, OP_POP_STOP_BT);
1444#ifndef USE_MATCH_CACHE
1449 case ENCLOSE_CONDITION:
1450 r = add_opcode(reg, OP_CONDITION);
1452 r = add_mem_num(reg, node->regnum);
1455 if (NTYPE(node->target) == NT_ALT) {
1456 Node* x = node->target;
1459 len = compile_length_tree(NCAR(x), reg);
1461 if (NCDR(x) == NULL)
return ONIGERR_PARSER_BUG;
1463 len2 = compile_length_tree(NCAR(x), reg);
1464 if (len2 < 0)
return len2;
1465 if (NCDR(x) != NULL)
return ONIGERR_INVALID_CONDITION_PATTERN;
1468 r = add_rel_addr(reg,
len + SIZE_OP_JUMP);
1470 r = compile_tree(NCAR(x), reg);
1472 r = add_opcode_rel_addr(reg, OP_JUMP, len2);
1475 r = compile_tree(NCAR(x), reg);
1478 return ONIGERR_PARSER_BUG;
1482 case ENCLOSE_ABSENT:
1483 len = compile_length_tree(node->target, reg);
1486 r = add_opcode(reg, OP_PUSH_ABSENT_POS);
1488 r = add_opcode_rel_addr(reg, OP_ABSENT,
len + SIZE_OP_ABSENT_END);
1490 r = compile_tree(node->target, reg);
1492 r = add_opcode(reg, OP_ABSENT_END);
1496 return ONIGERR_TYPE_BUG;
1504compile_length_anchor_node(
AnchorNode* node, regex_t* reg)
1510 tlen = compile_length_tree(node->target, reg);
1511 if (tlen < 0)
return tlen;
1514 switch (node->type) {
1515 case ANCHOR_PREC_READ:
1516 len = SIZE_OP_PUSH_POS + tlen + SIZE_OP_POP_POS;
1518 case ANCHOR_PREC_READ_NOT:
1519 len = SIZE_OP_PUSH_POS_NOT + tlen + SIZE_OP_FAIL_POS;
1521 case ANCHOR_LOOK_BEHIND:
1522 len = SIZE_OP_LOOK_BEHIND + tlen;
1524 case ANCHOR_LOOK_BEHIND_NOT:
1525 len = SIZE_OP_PUSH_LOOK_BEHIND_NOT + tlen + SIZE_OP_FAIL_LOOK_BEHIND_NOT;
1537compile_anchor_node(
AnchorNode* node, regex_t* reg)
1541 switch (node->type) {
1542 case ANCHOR_BEGIN_BUF: r = add_opcode(reg, OP_BEGIN_BUF);
break;
1543 case ANCHOR_END_BUF: r = add_opcode(reg, OP_END_BUF);
break;
1544 case ANCHOR_BEGIN_LINE: r = add_opcode(reg, OP_BEGIN_LINE);
break;
1545 case ANCHOR_END_LINE: r = add_opcode(reg, OP_END_LINE);
break;
1546 case ANCHOR_SEMI_END_BUF: r = add_opcode(reg, OP_SEMI_END_BUF);
break;
1547 case ANCHOR_BEGIN_POSITION: r = add_opcode(reg, OP_BEGIN_POSITION);
break;
1549 case ANCHOR_WORD_BOUND:
1550 if (node->ascii_range) r = add_opcode(reg, OP_ASCII_WORD_BOUND);
1551 else r = add_opcode(reg, OP_WORD_BOUND);
1553 case ANCHOR_NOT_WORD_BOUND:
1554 if (node->ascii_range) r = add_opcode(reg, OP_NOT_ASCII_WORD_BOUND);
1555 else r = add_opcode(reg, OP_NOT_WORD_BOUND);
1557#ifdef USE_WORD_BEGIN_END
1558 case ANCHOR_WORD_BEGIN:
1559 if (node->ascii_range) r = add_opcode(reg, OP_ASCII_WORD_BEGIN);
1560 else r = add_opcode(reg, OP_WORD_BEGIN);
1562 case ANCHOR_WORD_END:
1563 if (node->ascii_range) r = add_opcode(reg, OP_ASCII_WORD_END);
1564 else r = add_opcode(reg, OP_WORD_END);
1567 case ANCHOR_KEEP: r = add_opcode(reg, OP_KEEP);
break;
1569 case ANCHOR_PREC_READ:
1570 r = add_opcode(reg, OP_PUSH_POS);
1572 r = compile_tree(node->target, reg);
1574 r = add_opcode(reg, OP_POP_POS);
1577 case ANCHOR_PREC_READ_NOT:
1578 len = compile_length_tree(node->target, reg);
1580 r = add_opcode_rel_addr(reg, OP_PUSH_POS_NOT,
len + SIZE_OP_FAIL_POS);
1582 r = compile_tree(node->target, reg);
1584 r = add_opcode(reg, OP_FAIL_POS);
1587 case ANCHOR_LOOK_BEHIND:
1590 r = add_opcode(reg, OP_LOOK_BEHIND);
1592 if (node->char_len < 0) {
1593 r = get_char_length_tree(node->target, reg, &n);
1594 if (r)
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
1598 r = add_length(reg, n);
1600 r = compile_tree(node->target, reg);
1604 case ANCHOR_LOOK_BEHIND_NOT:
1607 len = compile_length_tree(node->target, reg);
1608 if (
len < 0)
return ONIGERR_PARSER_BUG;
1609 r = add_opcode_rel_addr(reg, OP_PUSH_LOOK_BEHIND_NOT,
1610 len + SIZE_OP_FAIL_LOOK_BEHIND_NOT);
1612 if (node->char_len < 0) {
1613 r = get_char_length_tree(node->target, reg, &n);
1614 if (r)
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
1618 r = add_length(reg, n);
1620 r = compile_tree(node->target, reg);
1622 r = add_opcode(reg, OP_FAIL_LOOK_BEHIND_NOT);
1627 return ONIGERR_TYPE_BUG;
1635compile_length_tree(Node* node, regex_t* reg)
1644 r = compile_length_tree(NCAR(node), reg);
1645 if (r < 0)
return r;
1647 }
while (IS_NOT_NULL(node = NCDR(node)));
1656 r = compile_length_tree(NCAR(node), reg);
1657 if (r < 0)
return r;
1660 }
while (IS_NOT_NULL(node = NCDR(node)));
1662 r += (SIZE_OP_PUSH + SIZE_OP_JUMP) * (n - 1);
1667 if (NSTRING_IS_RAW(node))
1668 r = compile_length_string_raw_node(NSTR(node), reg);
1670 r = compile_length_string_node(node, reg);
1674 r = compile_length_cclass_node(NCCLASS(node), reg);
1686#ifdef USE_BACKREF_WITH_LEVEL
1687 if (IS_BACKREF_NEST_LEVEL(br)) {
1688 r = SIZE_OPCODE + SIZE_OPTION + SIZE_LENGTH +
1689 SIZE_LENGTH + (SIZE_MEMNUM * br->back_num);
1693 if (br->back_num == 1) {
1694 r = ((!IS_IGNORECASE(reg->options) && br->back_static[0] <= 2)
1695 ? SIZE_OPCODE : (SIZE_OPCODE + SIZE_MEMNUM));
1698 r = SIZE_OPCODE + SIZE_LENGTH + (SIZE_MEMNUM * br->back_num);
1703#ifdef USE_SUBEXP_CALL
1710 r = compile_length_quantifier_node(NQTFR(node), reg);
1714 r = compile_length_enclose_node(NENCLOSE(node), reg);
1718 r = compile_length_anchor_node(NANCHOR(node), reg);
1722 return ONIGERR_TYPE_BUG;
1730compile_tree(Node* node, regex_t* reg)
1738 r = compile_tree(NCAR(node), reg);
1739 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
1747 r = compile_length_tree(NCAR(x), reg);
1748 if (r < 0)
return r;
1750 if (NCDR(x) != NULL) {
1751 len += SIZE_OP_PUSH + SIZE_OP_JUMP;
1753 }
while (IS_NOT_NULL(x = NCDR(x)));
1754 pos = reg->used +
len;
1757 len = compile_length_tree(NCAR(node), reg);
1758 if (
len < 0)
return ONIGERR_PARSER_BUG;
1759 if (IS_NOT_NULL(NCDR(node))) {
1760 r = add_opcode_rel_addr(reg, OP_PUSH,
len + SIZE_OP_JUMP);
1763 r = compile_tree(NCAR(node), reg);
1765 if (IS_NOT_NULL(NCDR(node))) {
1766 len = pos - (reg->used + SIZE_OP_JUMP);
1767 r = add_opcode_rel_addr(reg, OP_JUMP,
len);
1770 }
while (IS_NOT_NULL(node = NCDR(node)));
1775 if (NSTRING_IS_RAW(node))
1776 r = compile_string_raw_node(NSTR(node), reg);
1778 r = compile_string_node(node, reg);
1782 r = compile_cclass_node(NCCLASS(node), reg);
1789 switch (NCTYPE(node)->ctype) {
1790 case ONIGENC_CTYPE_WORD:
1791 if (NCTYPE(node)->ascii_range != 0) {
1792 if (NCTYPE(node)->not != 0) op = OP_NOT_ASCII_WORD;
1793 else op = OP_ASCII_WORD;
1796 if (NCTYPE(node)->not != 0) op = OP_NOT_WORD;
1801 return ONIGERR_TYPE_BUG;
1804 r = add_opcode(reg, op);
1809 if (IS_MULTILINE(reg->options))
1810 r = add_opcode(reg, OP_ANYCHAR_ML);
1812 r = add_opcode(reg, OP_ANYCHAR);
1819#ifdef USE_BACKREF_WITH_LEVEL
1820 if (IS_BACKREF_NEST_LEVEL(br)) {
1821 r = add_opcode(reg, OP_BACKREF_WITH_LEVEL);
1823 r = add_option(reg, (reg->options & ONIG_OPTION_IGNORECASE));
1825 r = add_length(reg, br->nest_level);
1828 goto add_bacref_mems;
1832 if (br->back_num == 1) {
1833 n = br->back_static[0];
1834 if (IS_IGNORECASE(reg->options)) {
1835 r = add_opcode(reg, OP_BACKREFN_IC);
1837 r = add_mem_num(reg, n);
1841 case 1: r = add_opcode(reg, OP_BACKREF1);
break;
1842 case 2: r = add_opcode(reg, OP_BACKREF2);
break;
1844 r = add_opcode(reg, OP_BACKREFN);
1846 r = add_mem_num(reg, n);
1855 if (IS_IGNORECASE(reg->options)) {
1856 r = add_opcode(reg, OP_BACKREF_MULTI_IC);
1859 r = add_opcode(reg, OP_BACKREF_MULTI);
1863#ifdef USE_BACKREF_WITH_LEVEL
1866 r = add_length(reg, br->back_num);
1869 for (i = br->back_num - 1; i >= 0; i--) {
1870 r = add_mem_num(reg, p[i]);
1877#ifdef USE_SUBEXP_CALL
1879 r = compile_call(NCALL(node), reg);
1884 r = compile_quantifier_node(NQTFR(node), reg);
1888 r = compile_enclose_node(NENCLOSE(node), reg);
1892 r = compile_anchor_node(NANCHOR(node), reg);
1897 fprintf(stderr,
"compile_tree: undefined node type %d\n", NTYPE(node));
1905#ifdef USE_NAMED_GROUP
1908noname_disable_map(Node** plink,
GroupNumRemap* map,
int* counter)
1911 Node* node = *plink;
1913 switch (NTYPE(node)) {
1917 r = noname_disable_map(&(NCAR(node)), map, counter);
1918 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
1923 Node** ptarget = &(NQTFR(node)->target);
1924 Node* old = *ptarget;
1925 r = noname_disable_map(ptarget, map, counter);
1926 if (*ptarget != old && NTYPE(*ptarget) == NT_QTFR) {
1927 onig_reduce_nested_quantifier(node, *ptarget);
1935 if (en->type == ENCLOSE_MEMORY) {
1936 if (IS_ENCLOSE_NAMED_GROUP(en)) {
1938 map[en->regnum].new_val = *counter;
1939 en->regnum = *counter;
1941 else if (en->regnum != 0) {
1942 *plink = en->target;
1943 en->target = NULL_NODE;
1944 onig_node_free(node);
1945 r = noname_disable_map(plink, map, counter);
1949 r = noname_disable_map(&(en->target), map, counter);
1954 if (NANCHOR(node)->target)
1955 r = noname_disable_map(&(NANCHOR(node)->target), map, counter);
1966renumber_node_backref(Node* node,
GroupNumRemap* map,
const int num_mem)
1968 int i, pos, n, old_num;
1972 if (! IS_BACKREF_NAME_REF(bn))
1973 return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
1975 old_num = bn->back_num;
1976 if (IS_NULL(bn->back_dynamic))
1977 backs = bn->back_static;
1979 backs = bn->back_dynamic;
1981 for (i = 0, pos = 0; i < old_num; i++) {
1982 if (backs[i] > num_mem)
return ONIGERR_INVALID_BACKREF;
1983 n = map[backs[i]].new_val;
1995renumber_by_map(Node* node,
GroupNumRemap* map,
const int num_mem)
1999 switch (NTYPE(node)) {
2003 r = renumber_by_map(NCAR(node), map, num_mem);
2004 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2007 r = renumber_by_map(NQTFR(node)->target, map, num_mem);
2012 if (en->type == ENCLOSE_CONDITION) {
2013 if (en->regnum > num_mem)
return ONIGERR_INVALID_BACKREF;
2014 en->regnum = map[en->regnum].new_val;
2016 r = renumber_by_map(en->target, map, num_mem);
2021 r = renumber_node_backref(node, map, num_mem);
2025 if (NANCHOR(node)->target)
2026 r = renumber_by_map(NANCHOR(node)->target, map, num_mem);
2037numbered_ref_check(Node* node)
2041 switch (NTYPE(node)) {
2045 r = numbered_ref_check(NCAR(node));
2046 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2049 r = numbered_ref_check(NQTFR(node)->target);
2052 r = numbered_ref_check(NENCLOSE(node)->target);
2056 if (! IS_BACKREF_NAME_REF(NBREF(node)))
2057 return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
2061 if (NANCHOR(node)->target)
2062 r = numbered_ref_check(NANCHOR(node)->target);
2073disable_noname_group_capture(Node** root, regex_t* reg,
ScanEnv* env)
2075 int r, i, pos, counter;
2080 CHECK_NULL_RETURN_MEMERR(map);
2081 for (i = 1; i <= env->num_mem; i++) {
2085 r = noname_disable_map(root, map, &counter);
2086 if (r != 0)
return r;
2088 r = renumber_by_map(*root, map, env->num_mem);
2089 if (r != 0)
return r;
2091 for (i = 1, pos = 1; i <= env->num_mem; i++) {
2092 if (map[i].new_val > 0) {
2093 SCANENV_MEM_NODES(env)[pos] = SCANENV_MEM_NODES(env)[i];
2098 loc = env->capture_history;
2099 BIT_STATUS_CLEAR(env->capture_history);
2100 for (i = 1; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
2101 if (BIT_STATUS_AT(loc, i)) {
2102 BIT_STATUS_ON_AT_SIMPLE(env->capture_history, map[i].new_val);
2106 env->num_mem = env->num_named;
2107 reg->num_mem = env->num_named;
2109 return onig_renumber_name_table(reg, map);
2113#ifdef USE_SUBEXP_CALL
2121 for (i = 0; i < uslist->num; i++) {
2122 en = NENCLOSE(uslist->us[i].target);
2123 if (! IS_ENCLOSE_ADDR_FIXED(en))
return ONIGERR_PARSER_BUG;
2124 addr = en->call_addr;
2125 offset = uslist->us[i].offset;
2127 BBUF_WRITE(reg, offset, &addr, SIZE_ABSADDR);
2133#ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
2135quantifiers_memory_node_info(Node* node)
2139 switch (NTYPE(node)) {
2145 v = quantifiers_memory_node_info(NCAR(node));
2147 }
while (v >= 0 && IS_NOT_NULL(node = NCDR(node)));
2151# ifdef USE_SUBEXP_CALL
2153 if (IS_CALL_RECURSION(NCALL(node))) {
2154 return NQ_TARGET_IS_EMPTY_REC;
2157 r = quantifiers_memory_node_info(NCALL(node)->target);
2164 if (qn->upper != 0) {
2165 r = quantifiers_memory_node_info(qn->target);
2174 case ENCLOSE_MEMORY:
2175 return NQ_TARGET_IS_EMPTY_MEM;
2178 case ENCLOSE_OPTION:
2179 case ENCLOSE_STOP_BACKTRACK:
2180 case ENCLOSE_CONDITION:
2181 case ENCLOSE_ABSENT:
2182 r = quantifiers_memory_node_info(en->target);
2205get_min_match_length(Node* node, OnigDistance *min,
ScanEnv* env)
2211 switch (NTYPE(node)) {
2216 Node** nodes = SCANENV_MEM_NODES(env);
2218 if (br->state & NST_RECURSION)
break;
2220 backs = BACKREFS_P(br);
2221 if (backs[0] > env->num_mem)
return ONIGERR_INVALID_BACKREF;
2222 r = get_min_match_length(nodes[backs[0]], min, env);
2224 for (i = 1; i < br->back_num; i++) {
2225 if (backs[i] > env->num_mem)
return ONIGERR_INVALID_BACKREF;
2226 r = get_min_match_length(nodes[backs[i]], &tmin, env);
2228 if (*min > tmin) *min = tmin;
2233#ifdef USE_SUBEXP_CALL
2235 if (IS_CALL_RECURSION(NCALL(node))) {
2237 if (IS_ENCLOSE_MIN_FIXED(en))
2241 r = get_min_match_length(NCALL(node)->target, min, env);
2247 r = get_min_match_length(NCAR(node), &tmin, env);
2248 if (r == 0) *min += tmin;
2249 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2258 r = get_min_match_length(x, &tmin, env);
2260 if (y == node) *min = tmin;
2261 else if (*min > tmin) *min = tmin;
2262 }
while (r == 0 && IS_NOT_NULL(y = NCDR(y)));
2269 *min = sn->end - sn->s;
2286 if (qn->lower > 0) {
2287 r = get_min_match_length(qn->target, min, env);
2289 *min = distance_multiply(*min, qn->lower);
2298 case ENCLOSE_MEMORY:
2299 if (IS_ENCLOSE_MIN_FIXED(en))
2302 if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
2305 SET_ENCLOSE_STATUS(node, NST_MARK1);
2306 r = get_min_match_length(en->target, min, env);
2307 CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
2310 SET_ENCLOSE_STATUS(node, NST_MIN_FIXED);
2316 case ENCLOSE_OPTION:
2317 case ENCLOSE_STOP_BACKTRACK:
2318 case ENCLOSE_CONDITION:
2319 r = get_min_match_length(en->target, min, env);
2322 case ENCLOSE_ABSENT:
2337get_max_match_length(Node* node, OnigDistance *max,
ScanEnv* env)
2343 switch (NTYPE(node)) {
2346 r = get_max_match_length(NCAR(node), &tmax, env);
2348 *max = distance_add(*max, tmax);
2349 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2354 r = get_max_match_length(NCAR(node), &tmax, env);
2355 if (r == 0 && *max < tmax) *max = tmax;
2356 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2362 *max = sn->end - sn->s;
2367 *max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
2372 *max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
2379 Node** nodes = SCANENV_MEM_NODES(env);
2381 if (br->state & NST_RECURSION) {
2382 *max = ONIG_INFINITE_DISTANCE;
2385 backs = BACKREFS_P(br);
2386 for (i = 0; i < br->back_num; i++) {
2387 if (backs[i] > env->num_mem)
return ONIGERR_INVALID_BACKREF;
2388 r = get_max_match_length(nodes[backs[i]], &tmax, env);
2390 if (*max < tmax) *max = tmax;
2395#ifdef USE_SUBEXP_CALL
2397 if (! IS_CALL_RECURSION(NCALL(node)))
2398 r = get_max_match_length(NCALL(node)->target, max, env);
2400 *max = ONIG_INFINITE_DISTANCE;
2408 if (qn->upper != 0) {
2409 r = get_max_match_length(qn->target, max, env);
2410 if (r == 0 && *max != 0) {
2411 if (! IS_REPEAT_INFINITE(qn->upper))
2412 *max = distance_multiply(*max, qn->upper);
2414 *max = ONIG_INFINITE_DISTANCE;
2424 case ENCLOSE_MEMORY:
2425 if (IS_ENCLOSE_MAX_FIXED(en))
2428 if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
2429 *max = ONIG_INFINITE_DISTANCE;
2431 SET_ENCLOSE_STATUS(node, NST_MARK1);
2432 r = get_max_match_length(en->target, max, env);
2433 CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
2436 SET_ENCLOSE_STATUS(node, NST_MAX_FIXED);
2442 case ENCLOSE_OPTION:
2443 case ENCLOSE_STOP_BACKTRACK:
2444 case ENCLOSE_CONDITION:
2445 r = get_max_match_length(en->target, max, env);
2448 case ENCLOSE_ABSENT:
2462#define GET_CHAR_LEN_VARLEN -1
2463#define GET_CHAR_LEN_TOP_ALT_VARLEN -2
2467get_char_length_tree1(Node* node, regex_t* reg,
int*
len,
int level)
2474 switch (NTYPE(node)) {
2477 r = get_char_length_tree1(NCAR(node), reg, &tlen, level);
2479 *
len = (int )distance_add(*
len, tlen);
2480 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2488 r = get_char_length_tree1(NCAR(node), reg, &tlen, level);
2489 while (r == 0 && IS_NOT_NULL(node = NCDR(node))) {
2490 r = get_char_length_tree1(NCAR(node), reg, &tlen2, level);
2499 r = GET_CHAR_LEN_TOP_ALT_VARLEN;
2501 r = GET_CHAR_LEN_VARLEN;
2513 while (s < sn->end) {
2514 s += enclen(reg->enc, s, sn->end);
2523 if (qn->lower == qn->upper) {
2524 r = get_char_length_tree1(qn->target, reg, &tlen, level);
2526 *
len = (int )distance_multiply(tlen, qn->lower);
2529 r = GET_CHAR_LEN_VARLEN;
2533#ifdef USE_SUBEXP_CALL
2535 if (! IS_CALL_RECURSION(NCALL(node)))
2536 r = get_char_length_tree1(NCALL(node)->target, reg,
len, level);
2538 r = GET_CHAR_LEN_VARLEN;
2555 case ENCLOSE_MEMORY:
2556#ifdef USE_SUBEXP_CALL
2557 if (IS_ENCLOSE_CLEN_FIXED(en))
2558 *
len = en->char_len;
2560 r = get_char_length_tree1(en->target, reg,
len, level);
2562 en->char_len = *
len;
2563 SET_ENCLOSE_STATUS(node, NST_CLEN_FIXED);
2568 case ENCLOSE_OPTION:
2569 case ENCLOSE_STOP_BACKTRACK:
2570 case ENCLOSE_CONDITION:
2571 r = get_char_length_tree1(en->target, reg,
len, level);
2573 case ENCLOSE_ABSENT:
2584 r = GET_CHAR_LEN_VARLEN;
2592get_char_length_tree(Node* node, regex_t* reg,
int*
len)
2594 return get_char_length_tree1(node, reg,
len, 0);
2599is_not_included(Node* x, Node* y, regex_t* reg)
2614 if (NCTYPE(y)->ctype == NCTYPE(x)->ctype &&
2615 NCTYPE(y)->not != NCTYPE(x)->not &&
2616 NCTYPE(y)->ascii_range == NCTYPE(x)->ascii_range)
2626 tmp = x; x = y; y = tmp;
2646 switch (NCTYPE(y)->ctype) {
2647 case ONIGENC_CTYPE_WORD:
2648 if (NCTYPE(y)->not == 0) {
2649 if (IS_NULL(xc->mbuf) && !IS_NCCLASS_NOT(xc)) {
2650 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2651 if (BITSET_AT(xc->bs, i)) {
2652 if (NCTYPE(y)->ascii_range) {
2653 if (IS_CODE_SB_WORD(reg->enc, i))
return 0;
2656 if (ONIGENC_IS_CODE_WORD(reg->enc, i))
return 0;
2665 if (IS_NOT_NULL(xc->mbuf))
return 0;
2666 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2668 if (NCTYPE(y)->ascii_range)
2669 is_word = IS_CODE_SB_WORD(reg->enc, i);
2671 is_word = ONIGENC_IS_CODE_WORD(reg->enc, i);
2673 if (!IS_NCCLASS_NOT(xc)) {
2674 if (BITSET_AT(xc->bs, i))
2678 if (! BITSET_AT(xc->bs, i))
2697 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2698 v = BITSET_AT(xc->bs, i);
2699 if ((v != 0 && !IS_NCCLASS_NOT(xc)) ||
2700 (v == 0 && IS_NCCLASS_NOT(xc))) {
2701 v = BITSET_AT(yc->bs, i);
2702 if ((v != 0 && !IS_NCCLASS_NOT(yc)) ||
2703 (v == 0 && IS_NCCLASS_NOT(yc)))
2707 if ((IS_NULL(xc->mbuf) && !IS_NCCLASS_NOT(xc)) ||
2708 (IS_NULL(yc->mbuf) && !IS_NCCLASS_NOT(yc)))
2727 if (NSTRING_LEN(x) == 0)
2732 switch (NCTYPE(y)->ctype) {
2733 case ONIGENC_CTYPE_WORD:
2734 if (NCTYPE(y)->ascii_range) {
2735 if (ONIGENC_IS_MBC_ASCII_WORD(reg->enc, xs->s, xs->end))
2736 return NCTYPE(y)->not;
2738 return !(NCTYPE(y)->not);
2741 if (ONIGENC_IS_MBC_WORD(reg->enc, xs->s, xs->end))
2742 return NCTYPE(y)->not;
2744 return !(NCTYPE(y)->not);
2756 code = ONIGENC_MBC_TO_CODE(reg->enc, xs->s,
2757 xs->s + ONIGENC_MBC_MAXLEN(reg->enc));
2758 return (onig_is_code_in_cc(reg->enc, code, cc) != 0 ? 0 : 1);
2766 len = NSTRING_LEN(x);
2767 if (
len > NSTRING_LEN(y))
len = NSTRING_LEN(y);
2768 if (NSTRING_IS_AMBIG(x) || NSTRING_IS_AMBIG(y)) {
2773 for (i = 0, p = ys->s, q = xs->s; (OnigDistance )i <
len; i++, p++, q++) {
2774 if (*p != *q)
return 1;
2794get_head_value_node(Node* node,
int exact, regex_t* reg)
2796 Node* n = NULL_NODE;
2798 switch (NTYPE(node)) {
2802#ifdef USE_SUBEXP_CALL
2815 n = get_head_value_node(NCAR(node), exact, reg);
2821 if (sn->end <= sn->s)
2825 NSTRING_IS_RAW(node) || !IS_IGNORECASE(reg->options)) {
2834 if (qn->lower > 0) {
2835#ifdef USE_OP_PUSH_OR_JUMP_EXACT
2836 if (IS_NOT_NULL(qn->head_exact))
2840 n = get_head_value_node(qn->target, exact, reg);
2849 case ENCLOSE_OPTION:
2851 OnigOptionType options = reg->options;
2853 reg->options = NENCLOSE(node)->option;
2854 n = get_head_value_node(NENCLOSE(node)->target, exact, reg);
2855 reg->options = options;
2859 case ENCLOSE_MEMORY:
2860 case ENCLOSE_STOP_BACKTRACK:
2861 case ENCLOSE_CONDITION:
2862 n = get_head_value_node(en->target, exact, reg);
2865 case ENCLOSE_ABSENT:
2872 if (NANCHOR(node)->type == ANCHOR_PREC_READ)
2873 n = get_head_value_node(NANCHOR(node)->target, exact, reg);
2884check_type_tree(Node* node,
int type_mask,
int enclose_mask,
int anchor_mask)
2889 if ((NTYPE2BIT(type) & type_mask) == 0)
2896 r = check_type_tree(NCAR(node), type_mask, enclose_mask,
2898 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2902 r = check_type_tree(NQTFR(node)->target, type_mask, enclose_mask,
2909 if ((en->type & enclose_mask) == 0)
2912 r = check_type_tree(en->target, type_mask, enclose_mask, anchor_mask);
2917 type = NANCHOR(node)->type;
2918 if ((type & anchor_mask) == 0)
2921 if (NANCHOR(node)->target)
2922 r = check_type_tree(NANCHOR(node)->target,
2923 type_mask, enclose_mask, anchor_mask);
2932#ifdef USE_SUBEXP_CALL
2934# define RECURSION_EXIST 1
2935# define RECURSION_INFINITE 2
2938subexp_inf_recursive_check(Node* node,
ScanEnv* env,
int head)
2953 ret = subexp_inf_recursive_check(NCAR(x), env, head);
2954 if (ret < 0 || ret == RECURSION_INFINITE)
return ret;
2957 ret = get_min_match_length(NCAR(x), &min, env);
2958 if (ret != 0)
return ret;
2959 if (min != 0) head = 0;
2961 }
while (IS_NOT_NULL(x = NCDR(x)));
2968 r = RECURSION_EXIST;
2970 ret = subexp_inf_recursive_check(NCAR(node), env, head);
2971 if (ret < 0 || ret == RECURSION_INFINITE)
return ret;
2973 }
while (IS_NOT_NULL(node = NCDR(node)));
2978 r = subexp_inf_recursive_check(NQTFR(node)->target, env, head);
2979 if (r == RECURSION_EXIST) {
2980 if (NQTFR(node)->lower == 0) r = 0;
2988 case ANCHOR_PREC_READ:
2989 case ANCHOR_PREC_READ_NOT:
2990 case ANCHOR_LOOK_BEHIND:
2991 case ANCHOR_LOOK_BEHIND_NOT:
2992 r = subexp_inf_recursive_check(an->target, env, head);
2999 r = subexp_inf_recursive_check(NCALL(node)->target, env, head);
3003 if (IS_ENCLOSE_MARK2(NENCLOSE(node)))
3005 else if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
3006 return (head == 0 ? RECURSION_EXIST : RECURSION_INFINITE);
3008 SET_ENCLOSE_STATUS(node, NST_MARK2);
3009 r = subexp_inf_recursive_check(NENCLOSE(node)->target, env, head);
3010 CLEAR_ENCLOSE_STATUS(node, NST_MARK2);
3022subexp_inf_recursive_check_trav(Node* node,
ScanEnv* env)
3032 r = subexp_inf_recursive_check_trav(NCAR(node), env);
3033 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3037 r = subexp_inf_recursive_check_trav(NQTFR(node)->target, env);
3044 case ANCHOR_PREC_READ:
3045 case ANCHOR_PREC_READ_NOT:
3046 case ANCHOR_LOOK_BEHIND:
3047 case ANCHOR_LOOK_BEHIND_NOT:
3048 r = subexp_inf_recursive_check_trav(an->target, env);
3058 if (IS_ENCLOSE_RECURSION(en)) {
3059 SET_ENCLOSE_STATUS(node, NST_MARK1);
3060 r = subexp_inf_recursive_check(en->target, env, 1);
3061 if (r > 0)
return ONIGERR_NEVER_ENDING_RECURSION;
3062 CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
3064 r = subexp_inf_recursive_check_trav(en->target, env);
3077subexp_recursive_check(Node* node)
3081 switch (NTYPE(node)) {
3085 r |= subexp_recursive_check(NCAR(node));
3086 }
while (IS_NOT_NULL(node = NCDR(node)));
3090 r = subexp_recursive_check(NQTFR(node)->target);
3097 case ANCHOR_PREC_READ:
3098 case ANCHOR_PREC_READ_NOT:
3099 case ANCHOR_LOOK_BEHIND:
3100 case ANCHOR_LOOK_BEHIND_NOT:
3101 r = subexp_recursive_check(an->target);
3108 r = subexp_recursive_check(NCALL(node)->target);
3109 if (r != 0) SET_CALL_RECURSION(node);
3113 if (IS_ENCLOSE_MARK2(NENCLOSE(node)))
3115 else if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
3118 SET_ENCLOSE_STATUS(node, NST_MARK2);
3119 r = subexp_recursive_check(NENCLOSE(node)->target);
3120 CLEAR_ENCLOSE_STATUS(node, NST_MARK2);
3133subexp_recursive_check_trav(Node* node,
ScanEnv* env)
3135# define FOUND_CALLED_NODE 1
3147 ret = subexp_recursive_check_trav(NCAR(node), env);
3148 if (ret == FOUND_CALLED_NODE) r = FOUND_CALLED_NODE;
3149 else if (ret < 0)
return ret;
3150 }
while (IS_NOT_NULL(node = NCDR(node)));
3155 r = subexp_recursive_check_trav(NQTFR(node)->target, env);
3156 if (NQTFR(node)->upper == 0) {
3157 if (r == FOUND_CALLED_NODE)
3158 NQTFR(node)->is_referred = 1;
3166 case ANCHOR_PREC_READ:
3167 case ANCHOR_PREC_READ_NOT:
3168 case ANCHOR_LOOK_BEHIND:
3169 case ANCHOR_LOOK_BEHIND_NOT:
3170 r = subexp_recursive_check_trav(an->target, env);
3180 if (! IS_ENCLOSE_RECURSION(en)) {
3181 if (IS_ENCLOSE_CALLED(en)) {
3182 SET_ENCLOSE_STATUS(node, NST_MARK1);
3183 r = subexp_recursive_check(en->target);
3184 if (r != 0) SET_ENCLOSE_STATUS(node, NST_RECURSION);
3185 CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
3188 r = subexp_recursive_check_trav(en->target, env);
3189 if (IS_ENCLOSE_CALLED(en))
3190 r |= FOUND_CALLED_NODE;
3202setup_subexp_call(Node* node,
ScanEnv* env)
3211 r = setup_subexp_call(NCAR(node), env);
3212 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3217 r = setup_subexp_call(NCAR(node), env);
3218 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3222 r = setup_subexp_call(NQTFR(node)->target, env);
3225 r = setup_subexp_call(NENCLOSE(node)->target, env);
3231 Node** nodes = SCANENV_MEM_NODES(env);
3233 if (cn->group_num != 0) {
3234 int gnum = cn->group_num;
3236# ifdef USE_NAMED_GROUP
3237 if (env->num_named > 0 &&
3238 IS_SYNTAX_BV(env->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
3239 !ONIG_IS_OPTION_ON(env->option, ONIG_OPTION_CAPTURE_GROUP)) {
3240 return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
3243 if (gnum > env->num_mem) {
3244 onig_scan_env_set_error_string(env,
3245 ONIGERR_UNDEFINED_GROUP_REFERENCE, cn->name, cn->name_end);
3246 return ONIGERR_UNDEFINED_GROUP_REFERENCE;
3249# ifdef USE_NAMED_GROUP
3252 cn->target = nodes[cn->group_num];
3253 if (IS_NULL(cn->target)) {
3254 onig_scan_env_set_error_string(env,
3255 ONIGERR_UNDEFINED_NAME_REFERENCE, cn->name, cn->name_end);
3256 return ONIGERR_UNDEFINED_NAME_REFERENCE;
3258 SET_ENCLOSE_STATUS(cn->target, NST_CALLED);
3259 BIT_STATUS_ON_AT(env->bt_mem_start, cn->group_num);
3260 cn->unset_addr_list = env->unset_addr_list;
3262# ifdef USE_NAMED_GROUP
3263# ifdef USE_PERL_SUBEXP_CALL
3264 else if (cn->name == cn->name_end) {
3271 int n = onig_name_to_group_numbers(env->reg, cn->name, cn->name_end,
3274 onig_scan_env_set_error_string(env,
3275 ONIGERR_UNDEFINED_NAME_REFERENCE, cn->name, cn->name_end);
3276 return ONIGERR_UNDEFINED_NAME_REFERENCE;
3279 ! IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME_CALL)) {
3280 onig_scan_env_set_error_string(env,
3281 ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL, cn->name, cn->name_end);
3282 return ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL;
3285 cn->group_num = refs[0];
3298 case ANCHOR_PREC_READ:
3299 case ANCHOR_PREC_READ_NOT:
3300 case ANCHOR_LOOK_BEHIND:
3301 case ANCHOR_LOOK_BEHIND_NOT:
3302 r = setup_subexp_call(an->target, env);
3316#define IN_ALT (1<<0)
3317#define IN_NOT (1<<1)
3318#define IN_REPEAT (1<<2)
3319#define IN_VAR_REPEAT (1<<3)
3320#define IN_CALL (1<<4)
3321#define IN_RECCALL (1<<5)
3322#define IN_LOOK_BEHIND (1<<6)
3329divide_look_behind_alternatives(Node* node)
3331 Node *head, *np, *insert_node;
3333 int anc_type = an->type;
3337 swap_node(node, head);
3339 NANCHOR(head)->target = np;
3342 while ((np = NCDR(np)) != NULL_NODE) {
3343 insert_node = onig_node_new_anchor(anc_type);
3344 CHECK_NULL_RETURN_MEMERR(insert_node);
3345 NANCHOR(insert_node)->target = NCAR(np);
3346 NCAR(np) = insert_node;
3349 if (anc_type == ANCHOR_LOOK_BEHIND_NOT) {
3352 SET_NTYPE(np, NT_LIST);
3353 }
while ((np = NCDR(np)) != NULL_NODE);
3359setup_look_behind(Node* node, regex_t* reg,
ScanEnv* env)
3364 r = get_char_length_tree(an->target, reg, &
len);
3367 else if (r == GET_CHAR_LEN_VARLEN)
3368 r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
3369 else if (r == GET_CHAR_LEN_TOP_ALT_VARLEN) {
3370 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND))
3371 r = divide_look_behind_alternatives(node);
3373 r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
3380next_setup(Node* node, Node* next_node, regex_t* reg)
3386 if (type == NT_QTFR) {
3388 if (qn->greedy && IS_REPEAT_INFINITE(qn->upper)) {
3389#ifdef USE_QTFR_PEEK_NEXT
3390 Node* n = get_head_value_node(next_node, 1, reg);
3392 if (IS_NOT_NULL(n) && NSTR(n)->s[0] !=
'\0') {
3393 qn->next_head_exact = n;
3397 if (qn->lower <= 1) {
3398 int ttype = NTYPE(qn->target);
3399 if (IS_NODE_TYPE_SIMPLE(ttype)) {
3401 x = get_head_value_node(qn->target, 0, reg);
3402 if (IS_NOT_NULL(x)) {
3403 y = get_head_value_node(next_node, 0, reg);
3404 if (IS_NOT_NULL(y) && is_not_included(x, y, reg)) {
3405 Node* en = onig_node_new_enclose(ENCLOSE_STOP_BACKTRACK);
3406 CHECK_NULL_RETURN_MEMERR(en);
3407 SET_ENCLOSE_STATUS(en, NST_STOP_BT_SIMPLE_REPEAT);
3408 swap_node(node, en);
3409 NENCLOSE(node)->target = en;
3416 else if (type == NT_ENCLOSE) {
3418 if (en->type == ENCLOSE_MEMORY && !IS_ENCLOSE_CALLED(en)) {
3428update_string_node_case_fold(regex_t* reg, Node *node)
3430 UChar *p, *end, buf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
3431 UChar *sbuf, *ebuf, *sp;
3433 OnigDistance sbuf_size;
3437 sbuf_size = (end - sn->s) * 2;
3438 sbuf = (UChar* )
xmalloc(sbuf_size);
3439 CHECK_NULL_RETURN_MEMERR(sbuf);
3440 ebuf = sbuf + sbuf_size;
3445 len = ONIGENC_MBC_CASE_FOLD(reg->enc, reg->case_fold_flag, &p, end, buf);
3446 for (i = 0; i <
len; i++) {
3448 UChar* p = (UChar* )
xrealloc(sbuf, sbuf_size * 2);
3451 return ONIGERR_MEMORY;
3454 sp = sbuf + sbuf_size;
3456 ebuf = sbuf + sbuf_size;
3463 r = onig_node_str_set(node, sbuf, sp);
3470expand_case_fold_make_rem_string(Node** rnode, UChar *s, UChar *end,
3476 node = onig_node_new_str(s, end);
3477 if (IS_NULL(node))
return ONIGERR_MEMORY;
3479 r = update_string_node_case_fold(reg, node);
3481 onig_node_free(node);
3485 NSTRING_SET_AMBIG(node);
3486 NSTRING_SET_DONT_GET_OPT_INFO(node);
3497 for (i = 0; i < item_num; i++) {
3498 if (items[i].byte_len != slen) {
3501 if (items[i].code_len != 1) {
3510 UChar *p,
int slen, UChar *end,
3511 regex_t* reg, Node **rnode)
3513 int r, i, j,
len, varlen;
3514 Node *anode, *var_anode, *snode, *xnode, *an;
3515 UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
3517 *rnode = var_anode = NULL_NODE;
3520 for (i = 0; i < item_num; i++) {
3521 if (items[i].byte_len != slen) {
3528 *rnode = var_anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3529 if (IS_NULL(var_anode))
return ONIGERR_MEMORY;
3531 xnode = onig_node_new_list(NULL, NULL);
3532 if (IS_NULL(xnode))
goto mem_err;
3533 NCAR(var_anode) = xnode;
3535 anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3536 if (IS_NULL(anode))
goto mem_err;
3537 NCAR(xnode) = anode;
3540 *rnode = anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3541 if (IS_NULL(anode))
return ONIGERR_MEMORY;
3544 snode = onig_node_new_str(p, p + slen);
3545 if (IS_NULL(snode))
goto mem_err;
3547 NCAR(anode) = snode;
3549 for (i = 0; i < item_num; i++) {
3550 snode = onig_node_new_str(NULL, NULL);
3551 if (IS_NULL(snode))
goto mem_err;
3553 for (j = 0; j < items[i].code_len; j++) {
3554 len = ONIGENC_CODE_TO_MBC(reg->enc, items[i].code[j], buf);
3560 r = onig_node_str_cat(snode, buf, buf +
len);
3561 if (r != 0)
goto mem_err2;
3564 an = onig_node_new_alt(NULL_NODE, NULL_NODE);
3569 if (items[i].byte_len != slen) {
3571 UChar *q = p + items[i].byte_len;
3574 r = expand_case_fold_make_rem_string(&rem, q, end, reg);
3580 xnode = onig_node_list_add(NULL_NODE, snode);
3581 if (IS_NULL(xnode)) {
3583 onig_node_free(rem);
3586 if (IS_NULL(onig_node_list_add(xnode, rem))) {
3588 onig_node_free(xnode);
3589 onig_node_free(rem);
3599 NCDR(var_anode) = an;
3612 onig_node_free(snode);
3615 onig_node_free(*rnode);
3617 return ONIGERR_MEMORY;
3620#define THRESHOLD_CASE_FOLD_ALT_FOR_EXPANSION 8
3623expand_case_fold_string(Node* node, regex_t* reg,
int state)
3625 int r, n,
len, alt_num;
3627 int is_in_look_behind;
3628 UChar *start, *end, *p;
3629 Node *top_root, *root, *snode, *prev_node;
3633 if (NSTRING_IS_AMBIG(node))
return 0;
3639 if (start >= end)
return 0;
3641 is_in_look_behind = (state & IN_LOOK_BEHIND) != 0;
3644 top_root = root = prev_node = snode = NULL_NODE;
3648 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(reg->enc, reg->case_fold_flag,
3655 len = enclen(reg->enc, p, end);
3657 varlen = is_case_fold_variable_len(n, items,
len);
3658 if (n == 0 || varlen == 0 || is_in_look_behind) {
3659 if (IS_NULL(snode)) {
3660 if (IS_NULL(root) && IS_NOT_NULL(prev_node)) {
3661 onig_node_free(top_root);
3662 top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3663 if (IS_NULL(root)) {
3664 onig_node_free(prev_node);
3669 prev_node = snode = onig_node_new_str(NULL, NULL);
3670 if (IS_NULL(snode))
goto mem_err;
3671 if (IS_NOT_NULL(root)) {
3672 if (IS_NULL(onig_node_list_add(root, snode))) {
3673 onig_node_free(snode);
3679 r = onig_node_str_cat(snode, p, p +
len);
3680 if (r != 0)
goto err;
3684 if (alt_num > THRESHOLD_CASE_FOLD_ALT_FOR_EXPANSION)
break;
3686 if (IS_NOT_NULL(snode)) {
3687 r = update_string_node_case_fold(reg, snode);
3689 NSTRING_SET_AMBIG(snode);
3692 if (IS_NULL(root) && IS_NOT_NULL(prev_node)) {
3693 onig_node_free(top_root);
3694 top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3695 if (IS_NULL(root)) {
3696 onig_node_free(prev_node);
3701 r = expand_case_fold_string_alt(n, items, p,
len, end, reg, &prev_node);
3702 if (r < 0)
goto mem_err;
3704 if (IS_NULL(root)) {
3705 top_root = prev_node;
3708 if (IS_NULL(onig_node_list_add(root, prev_node))) {
3709 onig_node_free(prev_node);
3714 root = NCAR(prev_node);
3717 if (IS_NOT_NULL(root)) {
3718 if (IS_NULL(onig_node_list_add(root, prev_node))) {
3719 onig_node_free(prev_node);
3730 if (IS_NOT_NULL(snode)) {
3731 r = update_string_node_case_fold(reg, snode);
3733 NSTRING_SET_AMBIG(snode);
3740 r = expand_case_fold_make_rem_string(&srem, p, end, reg);
3741 if (r != 0)
goto mem_err;
3743 if (IS_NOT_NULL(prev_node) && IS_NULL(root)) {
3744 onig_node_free(top_root);
3745 top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3746 if (IS_NULL(root)) {
3747 onig_node_free(srem);
3748 onig_node_free(prev_node);
3753 if (IS_NULL(root)) {
3757 if (IS_NULL(onig_node_list_add(root, srem))) {
3758 onig_node_free(srem);
3765 top_root = (IS_NOT_NULL(top_root) ? top_root : prev_node);
3766 swap_node(node, top_root);
3767 onig_node_free(top_root);
3774 onig_node_free(top_root);
3779#ifdef USE_COMBINATION_EXPLOSION_CHECK
3781# define CEC_THRES_NUM_BIG_REPEAT 512
3782# define CEC_INFINITE_NUM 0x7fffffff
3784# define CEC_IN_INFINITE_REPEAT (1<<0)
3785# define CEC_IN_FINITE_REPEAT (1<<1)
3786# define CEC_CONT_BIG_REPEAT (1<<2)
3789setup_comb_exp_check(Node* node,
int state,
ScanEnv* env)
3799 r = setup_comb_exp_check(NCAR(node), r, env);
3800 }
while (r >= 0 && IS_NOT_NULL(node = NCDR(node)));
3808 ret = setup_comb_exp_check(NCAR(node), state, env);
3810 }
while (ret >= 0 && IS_NOT_NULL(node = NCDR(node)));
3816 int child_state = state;
3819 Node* target = qn->target;
3822 if (! IS_REPEAT_INFINITE(qn->upper)) {
3823 if (qn->upper > 1) {
3825 child_state |= CEC_IN_FINITE_REPEAT;
3828 if (env->backrefed_mem == 0) {
3829 if (NTYPE(qn->target) == NT_ENCLOSE) {
3831 if (en->type == ENCLOSE_MEMORY) {
3832 if (NTYPE(en->target) == NT_QTFR) {
3834 if (IS_REPEAT_INFINITE(q->upper)
3835 && q->greedy == qn->greedy) {
3836 qn->upper = (qn->lower == 0 ? 1 : qn->lower);
3838 child_state = state;
3847 if (state & CEC_IN_FINITE_REPEAT) {
3848 qn->comb_exp_check_num = -1;
3851 if (IS_REPEAT_INFINITE(qn->upper)) {
3852 var_num = CEC_INFINITE_NUM;
3853 child_state |= CEC_IN_INFINITE_REPEAT;
3856 var_num = qn->upper - qn->lower;
3859 if (var_num >= CEC_THRES_NUM_BIG_REPEAT)
3860 add_state |= CEC_CONT_BIG_REPEAT;
3862 if (((state & CEC_IN_INFINITE_REPEAT) != 0 && var_num != 0) ||
3863 ((state & CEC_CONT_BIG_REPEAT) != 0 &&
3864 var_num >= CEC_THRES_NUM_BIG_REPEAT)) {
3865 if (qn->comb_exp_check_num == 0) {
3866 env->num_comb_exp_check++;
3867 qn->comb_exp_check_num = env->num_comb_exp_check;
3868 if (env->curr_max_regnum > env->comb_exp_max_regnum)
3869 env->comb_exp_max_regnum = env->curr_max_regnum;
3874 r = setup_comb_exp_check(target, child_state, env);
3884 case ENCLOSE_MEMORY:
3886 if (env->curr_max_regnum < en->regnum)
3887 env->curr_max_regnum = en->regnum;
3889 r = setup_comb_exp_check(en->target, state, env);
3894 r = setup_comb_exp_check(en->target, state, env);
3900# ifdef USE_SUBEXP_CALL
3902 if (IS_CALL_RECURSION(NCALL(node)))
3903 env->has_recursion = 1;
3905 r = setup_comb_exp_check(NCALL(node)->target, state, env);
3926setup_tree(Node* node, regex_t* reg,
int state,
ScanEnv* env)
3936 Node* prev = NULL_NODE;
3938 r = setup_tree(NCAR(node), reg, state, env);
3939 if (IS_NOT_NULL(prev) && r == 0) {
3940 r = next_setup(prev, NCAR(node), reg);
3943 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3949 r = setup_tree(NCAR(node), reg, (state | IN_ALT), env);
3950 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3957 if (IS_IGNORECASE(reg->options) && !NSTRING_IS_RAW(node)) {
3958 r = expand_case_fold_string(node, reg, state);
3966#ifdef USE_SUBEXP_CALL
3975 Node** nodes = SCANENV_MEM_NODES(env);
3978 for (i = 0; i < br->back_num; i++) {
3979 if (p[i] > env->num_mem)
return ONIGERR_INVALID_BACKREF;
3980 BIT_STATUS_ON_AT(env->backrefed_mem, p[i]);
3981 BIT_STATUS_ON_AT(env->bt_mem_start, p[i]);
3982#ifdef USE_BACKREF_WITH_LEVEL
3983 if (IS_BACKREF_NEST_LEVEL(br)) {
3984 BIT_STATUS_ON_AT(env->bt_mem_end, p[i]);
3987 SET_ENCLOSE_STATUS(nodes[p[i]], NST_MEM_BACKREFED);
3996 Node* target = qn->target;
3998 if ((state & IN_REPEAT) != 0) {
3999 qn->state |= NST_IN_REPEAT;
4002 if (IS_REPEAT_INFINITE(qn->upper) || qn->upper >= 1) {
4003 r = get_min_match_length(target, &d, env);
4006 qn->target_empty_info = NQ_TARGET_IS_EMPTY;
4007#ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
4008 r = quantifiers_memory_node_info(target);
4011 qn->target_empty_info = r;
4015 r = get_max_match_length(target, &d, env);
4016 if (r == 0 && d == 0) {
4019 if (qn->lower > 1) qn->lower = 1;
4020 if (NTYPE(target) == NT_STR) {
4021 qn->upper = qn->lower = 0;
4029 if (qn->lower != qn->upper)
4030 state |= IN_VAR_REPEAT;
4031 r = setup_tree(target, reg, state, env);
4035#define EXPAND_STRING_MAX_LENGTH 100
4036 if (NTYPE(target) == NT_STR) {
4037 if (qn->lower > 1) {
4038 int i, n = qn->lower;
4039 OnigDistance
len = NSTRING_LEN(target);
4043 np = onig_node_new_str(sn->s, sn->end);
4044 if (IS_NULL(np))
return ONIGERR_MEMORY;
4045 NSTR(np)->flag = sn->flag;
4047 for (i = 1; i < n && (i+1) *
len <= EXPAND_STRING_MAX_LENGTH; i++) {
4048 r = onig_node_str_cat(np, sn->s, sn->end);
4054 if (i < qn->upper || IS_REPEAT_INFINITE(qn->upper)) {
4058 if (! IS_REPEAT_INFINITE(qn->upper))
4061 np1 = onig_node_new_list(np, NULL);
4064 return ONIGERR_MEMORY;
4066 swap_node(np1, node);
4067 np2 = onig_node_list_add(node, np1);
4069 onig_node_free(np1);
4070 return ONIGERR_MEMORY;
4074 swap_node(np, node);
4081#ifdef USE_OP_PUSH_OR_JUMP_EXACT
4082 if (qn->greedy && (qn->target_empty_info != 0)) {
4083 if (NTYPE(target) == NT_QTFR) {
4085 if (IS_NOT_NULL(tqn->head_exact)) {
4086 qn->head_exact = tqn->head_exact;
4087 tqn->head_exact = NULL;
4091 qn->head_exact = get_head_value_node(qn->target, 1, reg);
4103 case ENCLOSE_OPTION:
4105 OnigOptionType options = reg->options;
4106 reg->options = NENCLOSE(node)->option;
4107 r = setup_tree(NENCLOSE(node)->target, reg, state, env);
4108 reg->options = options;
4112 case ENCLOSE_MEMORY:
4113 if ((state & (IN_ALT | IN_NOT | IN_VAR_REPEAT | IN_CALL)) != 0) {
4114 BIT_STATUS_ON_AT(env->bt_mem_start, en->regnum);
4117 if (IS_ENCLOSE_CALLED(en))
4119 if (IS_ENCLOSE_RECURSION(en))
4120 state |= IN_RECCALL;
4121 else if ((state & IN_RECCALL) != 0)
4122 SET_CALL_RECURSION(node);
4123 r = setup_tree(en->target, reg, state, env);
4126 case ENCLOSE_STOP_BACKTRACK:
4128 Node* target = en->target;
4129 r = setup_tree(target, reg, state, env);
4130 if (NTYPE(target) == NT_QTFR) {
4132 if (IS_REPEAT_INFINITE(tqn->upper) && tqn->lower <= 1 &&
4134 int qtype = NTYPE(tqn->target);
4135 if (IS_NODE_TYPE_SIMPLE(qtype))
4136 SET_ENCLOSE_STATUS(node, NST_STOP_BT_SIMPLE_REPEAT);
4142 case ENCLOSE_CONDITION:
4143#ifdef USE_NAMED_GROUP
4144 if (! IS_ENCLOSE_NAME_REF(NENCLOSE(node)) &&
4145 env->num_named > 0 &&
4146 IS_SYNTAX_BV(env->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
4147 !ONIG_IS_OPTION_ON(env->option, ONIG_OPTION_CAPTURE_GROUP)) {
4148 return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
4151 if (NENCLOSE(node)->regnum > env->num_mem)
4152 return ONIGERR_INVALID_BACKREF;
4153 r = setup_tree(NENCLOSE(node)->target, reg, state, env);
4156 case ENCLOSE_ABSENT:
4157 r = setup_tree(NENCLOSE(node)->target, reg, state, env);
4168 case ANCHOR_PREC_READ:
4169 r = setup_tree(an->target, reg, state, env);
4171 case ANCHOR_PREC_READ_NOT:
4172 r = setup_tree(an->target, reg, (state | IN_NOT), env);
4176#define ALLOWED_TYPE_IN_LB \
4177 ( BIT_NT_LIST | BIT_NT_ALT | BIT_NT_STR | BIT_NT_CCLASS | BIT_NT_CTYPE | \
4178 BIT_NT_CANY | BIT_NT_ANCHOR | BIT_NT_ENCLOSE | BIT_NT_QTFR | BIT_NT_CALL )
4180#define ALLOWED_ENCLOSE_IN_LB ( ENCLOSE_MEMORY | ENCLOSE_OPTION )
4181#define ALLOWED_ENCLOSE_IN_LB_NOT ENCLOSE_OPTION
4183#define ALLOWED_ANCHOR_IN_LB \
4184( ANCHOR_LOOK_BEHIND | ANCHOR_LOOK_BEHIND_NOT | ANCHOR_BEGIN_LINE | \
4185 ANCHOR_END_LINE | ANCHOR_BEGIN_BUF | ANCHOR_BEGIN_POSITION | ANCHOR_KEEP | \
4186 ANCHOR_WORD_BOUND | ANCHOR_NOT_WORD_BOUND | \
4187 ANCHOR_WORD_BEGIN | ANCHOR_WORD_END )
4188#define ALLOWED_ANCHOR_IN_LB_NOT \
4189( ANCHOR_LOOK_BEHIND | ANCHOR_LOOK_BEHIND_NOT | ANCHOR_BEGIN_LINE | \
4190 ANCHOR_END_LINE | ANCHOR_BEGIN_BUF | ANCHOR_BEGIN_POSITION | ANCHOR_KEEP | \
4191 ANCHOR_WORD_BOUND | ANCHOR_NOT_WORD_BOUND | \
4192 ANCHOR_WORD_BEGIN | ANCHOR_WORD_END )
4194 case ANCHOR_LOOK_BEHIND:
4196 r = check_type_tree(an->target, ALLOWED_TYPE_IN_LB,
4197 ALLOWED_ENCLOSE_IN_LB, ALLOWED_ANCHOR_IN_LB);
4198 if (r < 0)
return r;
4199 if (r > 0)
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
4200 if (NTYPE(node) != NT_ANCHOR)
goto restart;
4201 r = setup_tree(an->target, reg, (state | IN_LOOK_BEHIND), env);
4202 if (r != 0)
return r;
4203 r = setup_look_behind(node, reg, env);
4207 case ANCHOR_LOOK_BEHIND_NOT:
4209 r = check_type_tree(an->target, ALLOWED_TYPE_IN_LB,
4210 ALLOWED_ENCLOSE_IN_LB_NOT, ALLOWED_ANCHOR_IN_LB_NOT);
4211 if (r < 0)
return r;
4212 if (r > 0)
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
4213 if (NTYPE(node) != NT_ANCHOR)
goto restart;
4214 r = setup_tree(an->target, reg, (state | IN_NOT | IN_LOOK_BEHIND),
4216 if (r != 0)
return r;
4217 r = setup_look_behind(node, reg, env);
4233set_bm_skip(UChar* s, UChar* end, regex_t* reg,
4234 UChar skip[],
int ignore_case)
4236 OnigDistance i,
len;
4237 int clen, flen, n, j, k;
4238 UChar *p, buf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
4240 OnigEncoding enc = reg->enc;
4243 if (
len >= ONIG_CHAR_TABLE_SIZE) {
4245 return ONIGERR_TYPE_BUG;
4249 for (i = 0; i <
len; i += clen) {
4251 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, reg->case_fold_flag,
4253 clen = enclen(enc, p, end);
4255 clen = (int )(end - p);
4257 for (j = 0; j < n; j++) {
4258 if ((items[j].code_len != 1) || (items[j].byte_len != clen)) {
4263 flen = ONIGENC_CODE_TO_MBC(enc, items[j].code[0], buf);
4275 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
4276 skip[i] = (UChar )(
len + 1);
4278 for (i = 0; i <
len; i += clen) {
4281 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, reg->case_fold_flag,
4283 clen = enclen(enc, p, end);
4285 clen = (int )(end - p);
4287 for (j = 0; j < clen; j++) {
4288 skip[s[i + j]] = (UChar )(
len - i - j);
4289 for (k = 0; k < n; k++) {
4290 ONIGENC_CODE_TO_MBC(enc, items[k].code[0], buf);
4291 skip[buf[j]] = (UChar )(
len - i - j);
4307 OnigOptionType options;
4308 OnigCaseFoldType case_fold_flag;
4325 UChar s[OPT_EXACT_MAXLEN];
4333 UChar map[ONIG_CHAR_TABLE_SIZE];
4349map_position_value(OnigEncoding enc,
int i)
4351 static const short int ByteValTable[] = {
4352 5, 1, 1, 1, 1, 1, 1, 1, 1, 10, 10, 1, 1, 10, 1, 1,
4353 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
4354 12, 4, 7, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,
4355 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5,
4356 5, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
4357 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 5, 5, 5,
4358 5, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
4359 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 1
4362 if (i < numberof(ByteValTable)) {
4363 if (i == 0 && ONIGENC_MBC_MINLEN(enc) > 1)
4366 return (
int )ByteValTable[i];
4376 static const short int dist_vals[] = {
4377 1000, 500, 333, 250, 200, 167, 143, 125, 111, 100,
4378 91, 83, 77, 71, 67, 63, 59, 56, 53, 50,
4379 48, 45, 43, 42, 40, 38, 37, 36, 34, 33,
4380 32, 31, 30, 29, 29, 28, 27, 26, 26, 25,
4381 24, 24, 23, 23, 22, 22, 21, 21, 20, 20,
4382 20, 19, 19, 19, 18, 18, 18, 17, 17, 17,
4383 16, 16, 16, 16, 15, 15, 15, 15, 14, 14,
4384 14, 14, 14, 14, 13, 13, 13, 13, 13, 13,
4385 12, 12, 12, 12, 12, 12, 11, 11, 11, 11,
4386 11, 11, 11, 11, 11, 10, 10, 10, 10, 10
4391 if (mm->max == ONIG_INFINITE_DISTANCE)
return 0;
4393 d = mm->max - mm->min;
4394 if (d < numberof(dist_vals))
4396 return (
int )dist_vals[d];
4404 if (v2 <= 0)
return -1;
4405 if (v1 <= 0)
return 1;
4407 v1 *= distance_value(d1);
4408 v2 *= distance_value(d2);
4410 if (v2 > v1)
return 1;
4411 if (v2 < v1)
return -1;
4413 if (d2->min < d1->min)
return 1;
4414 if (d2->min > d1->min)
return -1;
4421 return (a->min == b->min && a->max == b->max) ? 1 : 0;
4426set_mml(
MinMaxLen* mml, OnigDistance min, OnigDistance max)
4435 mml->min = mml->max = 0;
4441 to->min = from->min;
4442 to->max = from->max;
4448 to->min = distance_add(to->min, from->min);
4449 to->max = distance_add(to->max, from->max);
4456 to->min = distance_add(to->min,
len);
4457 to->max = distance_add(to->max,
len);
4464 if (to->min > from->min) to->min = from->min;
4465 if (to->max < from->max) to->max = from->max;
4477 anc->left_anchor = 0;
4478 anc->right_anchor = 0;
4479 anc->head_asserts = 0;
4490 OnigDistance left_len, OnigDistance right_len)
4492 clear_opt_anc_info(to);
4494 to->left_anchor = left->left_anchor;
4495 to->head_asserts = left->head_asserts;
4496 if (left_len == 0) {
4497 int right_left = right->left_anchor;
4499 if ((left->head_asserts & ~ANCHOR_BEGIN_LINE) != 0)
4500 right_left &= ~ANCHOR_ANYCHAR_STAR_MASK;
4501 else if ((left->head_asserts & ANCHOR_BEGIN_LINE) != 0)
4502 right_left &= ~ANCHOR_ANYCHAR_STAR_ML;
4504 to->left_anchor |= right_left;
4505 to->head_asserts |= right->head_asserts;
4508 to->right_anchor = right->right_anchor;
4509 if (right_len == 0) {
4510 to->right_anchor |= left->right_anchor;
4513 to->right_anchor |= (left->right_anchor & ANCHOR_PREC_READ_NOT);
4518is_left_anchor(
int anc)
4520 if (anc == ANCHOR_END_BUF || anc == ANCHOR_SEMI_END_BUF ||
4521 anc == ANCHOR_END_LINE || anc == ANCHOR_PREC_READ ||
4522 anc == ANCHOR_PREC_READ_NOT)
4531 if ((to->left_anchor & anc) != 0)
return 1;
4533 return ((to->right_anchor & anc) != 0 ? 1 : 0);
4539 if (is_left_anchor(anc))
4540 to->left_anchor |= anc;
4542 to->right_anchor |= anc;
4548 if (is_left_anchor(anc))
4549 to->left_anchor &= ~anc;
4551 to->right_anchor &= ~anc;
4557 to->left_anchor &= add->left_anchor;
4558 to->right_anchor &= add->right_anchor;
4559 to->head_asserts |= add->head_asserts;
4565 return (ex->len >= OPT_EXACT_MAXLEN ? 1 : 0);
4571 clear_mml(&ex->mmd);
4572 clear_opt_anc_info(&ex->anc);
4574 ex->ignore_case = -1;
4592 if (to->ignore_case < 0)
4593 to->ignore_case = add->ignore_case;
4594 else if (to->ignore_case != add->ignore_case)
4599 for (i = to->len; p < end; ) {
4600 len = enclen(enc, p, end);
4601 if (i +
len > OPT_EXACT_MAXLEN)
break;
4602 for (j = 0; j <
len && p < end; j++)
4607 to->reach_end = (p == end ? add->reach_end : 0);
4609 concat_opt_anc_info(&tanc, &to->anc, &add->anc, 1, 1);
4610 if (! to->reach_end) tanc.right_anchor = 0;
4611 copy_opt_anc_info(&to->anc, &tanc);
4615concat_opt_exact_info_str(
OptExactInfo* to, UChar* s, UChar* end,
4616 int raw ARG_UNUSED, OnigEncoding enc)
4621 for (i = to->len, p = s; p < end && i < OPT_EXACT_MAXLEN; ) {
4622 len = enclen(enc, p, end);
4623 if (i +
len > OPT_EXACT_MAXLEN)
break;
4624 for (j = 0; j <
len && p < end; j++)
4636 if (add->len == 0 || to->len == 0) {
4637 clear_opt_exact_info(to);
4641 if (! is_equal_mml(&to->mmd, &add->mmd)) {
4642 clear_opt_exact_info(to);
4646 for (i = 0; i < to->len && i < add->len; ) {
4647 if (to->s[i] != add->s[i])
break;
4648 len = enclen(env->enc, to->s + i, to->s + to->len);
4650 for (j = 1; j <
len; j++) {
4651 if (to->s[i+j] != add->s[i+j])
break;
4657 if (! add->reach_end || i < add->
len || i < to->
len) {
4661 if (to->ignore_case < 0)
4662 to->ignore_case = add->ignore_case;
4663 else if (add->ignore_case >= 0)
4664 to->ignore_case |= add->ignore_case;
4666 alt_merge_opt_anc_info(&to->anc, &add->anc);
4667 if (! to->reach_end) to->anc.right_anchor = 0;
4682 copy_opt_exact_info(now, alt);
4685 else if (v1 <= 2 && v2 <= 2) {
4687 v2 = map_position_value(enc, now->s[0]);
4688 v1 = map_position_value(enc, alt->s[0]);
4690 if (now->len > 1) v1 += 5;
4691 if (alt->len > 1) v2 += 5;
4694 if (now->ignore_case <= 0) v1 *= 2;
4695 if (alt->ignore_case <= 0) v2 *= 2;
4697 if (comp_distance_value(&now->mmd, &alt->mmd, v1, v2) > 0)
4698 copy_opt_exact_info(now, alt);
4707 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4708 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4709 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4710 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4711 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4712 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4713 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4714 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4715 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4716 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4717 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4718 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4719 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4720 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4721 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4722 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
4726 xmemcpy(map, &clean_info,
sizeof(
OptMapInfo));
4736add_char_opt_map_info(
OptMapInfo* map, UChar c, OnigEncoding enc)
4738 if (map->map[c] == 0) {
4740 map->value += map_position_value(enc, c);
4745add_char_amb_opt_map_info(
OptMapInfo* map, UChar* p, UChar* end,
4746 OnigEncoding enc, OnigCaseFoldType case_fold_flag)
4749 UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
4752 add_char_opt_map_info(map, p[0], enc);
4754 case_fold_flag = DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag);
4755 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, case_fold_flag, p, end, items);
4756 if (n < 0)
return n;
4758 for (i = 0; i < n; i++) {
4759 ONIGENC_CODE_TO_MBC(enc, items[i].code[0], buf);
4760 add_char_opt_map_info(map, buf[0], enc);
4769 const int z = 1<<15;
4773 if (alt->value == 0) return ;
4774 if (now->value == 0) {
4775 copy_opt_map_info(now, alt);
4779 v1 = z / now->value;
4780 v2 = z / alt->value;
4781 if (comp_distance_value(&now->mmd, &alt->mmd, v1, v2) > 0)
4782 copy_opt_map_info(now, alt);
4788#define COMP_EM_BASE 20
4791 if (m->value <= 0)
return -1;
4793 ve = COMP_EM_BASE * e->len * (e->ignore_case > 0 ? 1 : 2);
4794 vm = COMP_EM_BASE * 5 * 2 / m->value;
4795 return comp_distance_value(&e->mmd, &m->mmd, ve, vm);
4804 if (to->value == 0) return ;
4805 if (add->value == 0 || to->mmd.max < add->mmd.min) {
4806 clear_opt_map_info(to);
4810 alt_merge_mml(&to->mmd, &add->mmd);
4813 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) {
4818 val += map_position_value(enc, i);
4822 alt_merge_opt_anc_info(&to->anc, &add->anc);
4828 copy_mml(&(opt->exb.mmd), mmd);
4829 copy_mml(&(opt->expr.mmd), mmd);
4830 copy_mml(&(opt->map.mmd), mmd);
4836 clear_mml(&opt->len);
4837 clear_opt_anc_info(&opt->anc);
4838 clear_opt_exact_info(&opt->exb);
4839 clear_opt_exact_info(&opt->exm);
4840 clear_opt_exact_info(&opt->expr);
4841 clear_opt_map_info(&opt->map);
4853 int exb_reach, exm_reach;
4856 concat_opt_anc_info(&tanc, &to->anc, &add->anc, to->len.max, add->len.max);
4857 copy_opt_anc_info(&to->anc, &tanc);
4859 if (add->exb.len > 0 && to->len.max == 0) {
4860 concat_opt_anc_info(&tanc, &to->anc, &add->exb.anc,
4861 to->len.max, add->len.max);
4862 copy_opt_anc_info(&add->exb.anc, &tanc);
4865 if (add->map.value > 0 && to->len.max == 0) {
4866 if (add->map.mmd.max == 0)
4867 add->map.anc.left_anchor |= to->anc.left_anchor;
4870 exb_reach = to->exb.reach_end;
4871 exm_reach = to->exm.reach_end;
4873 if (add->len.max != 0)
4874 to->exb.reach_end = to->exm.reach_end = 0;
4876 if (add->exb.len > 0) {
4878 concat_opt_exact_info(&to->exb, &add->exb, enc);
4879 clear_opt_exact_info(&add->exb);
4881 else if (exm_reach) {
4882 concat_opt_exact_info(&to->exm, &add->exb, enc);
4883 clear_opt_exact_info(&add->exb);
4886 select_opt_exact_info(enc, &to->exm, &add->exb);
4887 select_opt_exact_info(enc, &to->exm, &add->exm);
4889 if (to->expr.len > 0) {
4890 if (add->len.max > 0) {
4891 if (to->expr.len > (
int )add->len.max)
4892 to->expr.len = (int )add->len.max;
4894 if (to->expr.mmd.max == 0)
4895 select_opt_exact_info(enc, &to->exb, &to->expr);
4897 select_opt_exact_info(enc, &to->exm, &to->expr);
4900 else if (add->expr.len > 0) {
4901 copy_opt_exact_info(&to->expr, &add->expr);
4904 select_opt_map_info(&to->map, &add->map);
4906 add_mml(&to->len, &add->len);
4912 alt_merge_opt_anc_info (&to->anc, &add->anc);
4913 alt_merge_opt_exact_info(&to->exb, &add->exb, env);
4914 alt_merge_opt_exact_info(&to->exm, &add->exm, env);
4915 alt_merge_opt_exact_info(&to->expr, &add->expr, env);
4916 alt_merge_opt_map_info(env->enc, &to->map, &add->map);
4918 alt_merge_mml(&to->len, &add->len);
4922#define MAX_NODE_OPT_INFO_REF_COUNT 5
4930 clear_node_opt_info(opt);
4931 set_bound_node_opt_info(opt, &env->mmd);
4941 copy_opt_env(&nenv, env);
4943 r = optimize_node_left(NCAR(nd), &nopt, &nenv);
4945 add_mml(&nenv.mmd, &nopt.len);
4946 concat_left_node_opt_info(env->enc, opt, &nopt);
4948 }
while (r == 0 && IS_NOT_NULL(nd = NCDR(nd)));
4958 r = optimize_node_left(NCAR(nd), &nopt, env);
4960 if (nd == node) copy_node_opt_info(opt, &nopt);
4961 else alt_merge_node_opt_info(opt, &nopt, env);
4963 }
while ((r == 0) && IS_NOT_NULL(nd = NCDR(nd)));
4970 OnigDistance slen = sn->end - sn->s;
4971 int is_raw = NSTRING_IS_RAW(node);
4973 if (! NSTRING_IS_AMBIG(node)) {
4974 concat_opt_exact_info_str(&opt->exb, sn->s, sn->end,
4976 opt->exb.ignore_case = 0;
4978 add_char_opt_map_info(&opt->map, *(sn->s), env->enc);
4980 set_mml(&opt->len, slen, slen);
4985 if (NSTRING_IS_DONT_GET_OPT_INFO(node)) {
4986 int n = onigenc_strlen(env->enc, sn->s, sn->end);
4987 max = (OnigDistance )ONIGENC_MBC_MAXLEN_DIST(env->enc) * (OnigDistance)n;
4990 concat_opt_exact_info_str(&opt->exb, sn->s, sn->end,
4992 opt->exb.ignore_case = 1;
4995 r = add_char_amb_opt_map_info(&opt->map, sn->s, sn->end,
4996 env->enc, env->case_fold_flag);
5003 set_mml(&opt->len, slen, max);
5006 if ((OnigDistance )opt->exb.len == slen)
5007 opt->exb.reach_end = 1;
5018 if (IS_NOT_NULL(cc->mbuf) || IS_NCCLASS_NOT(cc)) {
5019 OnigDistance min = ONIGENC_MBC_MINLEN(env->enc);
5020 OnigDistance max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
5022 set_mml(&opt->len, min, max);
5025 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
5026 z = BITSET_AT(cc->bs, i);
5027 if ((z && !IS_NCCLASS_NOT(cc)) || (!z && IS_NCCLASS_NOT(cc))) {
5028 add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
5031 set_mml(&opt->len, 1, 1);
5041 max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
5046 maxcode = NCTYPE(node)->ascii_range ? 0x80 : SINGLE_BYTE_SIZE;
5047 switch (NCTYPE(node)->ctype) {
5048 case ONIGENC_CTYPE_WORD:
5049 if (NCTYPE(node)->not != 0) {
5050 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
5051 if (! ONIGENC_IS_CODE_WORD(env->enc, i) || i >= maxcode) {
5052 add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
5057 for (i = 0; i < maxcode; i++) {
5058 if (ONIGENC_IS_CODE_WORD(env->enc, i)) {
5059 add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
5067 min = ONIGENC_MBC_MINLEN(env->enc);
5069 set_mml(&opt->len, min, max);
5075 OnigDistance min = ONIGENC_MBC_MINLEN(env->enc);
5076 OnigDistance max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
5077 set_mml(&opt->len, min, max);
5082 if ((NANCHOR(node)->type &
5083 ~(ANCHOR_BEGIN_BUF | ANCHOR_BEGIN_POSITION | ANCHOR_KEEP)) != 0)
5084 opt->anc.head_asserts |= NANCHOR(node)->type;
5086 switch (NANCHOR(node)->type) {
5087 case ANCHOR_BEGIN_BUF:
5088 case ANCHOR_BEGIN_POSITION:
5089 case ANCHOR_BEGIN_LINE:
5090 case ANCHOR_END_BUF:
5091 case ANCHOR_SEMI_END_BUF:
5092 case ANCHOR_END_LINE:
5093 case ANCHOR_LOOK_BEHIND:
5094 case ANCHOR_PREC_READ_NOT:
5095 add_opt_anc_info(&opt->anc, NANCHOR(node)->type);
5098 case ANCHOR_PREC_READ:
5102 r = optimize_node_left(NANCHOR(node)->target, &nopt, env);
5104 if (nopt.exb.len > 0)
5105 copy_opt_exact_info(&opt->expr, &nopt.exb);
5106 else if (nopt.exm.len > 0)
5107 copy_opt_exact_info(&opt->expr, &nopt.exm);
5109 opt->expr.reach_end = 0;
5111 if (nopt.map.value > 0)
5112 copy_opt_map_info(&opt->map, &nopt.map);
5117 case ANCHOR_LOOK_BEHIND_NOT:
5126 OnigDistance min, max, tmin, tmax;
5127 Node** nodes = SCANENV_MEM_NODES(env->scan_env);
5130 if (br->state & NST_RECURSION) {
5131 set_mml(&opt->len, 0, ONIG_INFINITE_DISTANCE);
5134 backs = BACKREFS_P(br);
5135 r = get_min_match_length(nodes[backs[0]], &min, env->scan_env);
5137 r = get_max_match_length(nodes[backs[0]], &max, env->scan_env);
5139 for (i = 1; i < br->back_num; i++) {
5140 r = get_min_match_length(nodes[backs[i]], &tmin, env->scan_env);
5142 r = get_max_match_length(nodes[backs[i]], &tmax, env->scan_env);
5144 if (min > tmin) min = tmin;
5145 if (max < tmax) max = tmax;
5147 if (r == 0) set_mml(&opt->len, min, max);
5151#ifdef USE_SUBEXP_CALL
5153 if (IS_CALL_RECURSION(NCALL(node)))
5154 set_mml(&opt->len, 0, ONIG_INFINITE_DISTANCE);
5156 OnigOptionType save = env->options;
5157 env->options = NENCLOSE(NCALL(node)->target)->option;
5158 r = optimize_node_left(NCALL(node)->target, opt, env);
5159 env->options = save;
5167 OnigDistance min, max;
5171 r = optimize_node_left(qn->target, &nopt, env);
5174 if (qn->lower == 0 && IS_REPEAT_INFINITE(qn->upper)) {
5175 if (env->mmd.max == 0 &&
5176 NTYPE(qn->target) == NT_CANY && qn->greedy) {
5177 if (IS_MULTILINE(env->options))
5179 add_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_ML);
5181 add_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR);
5185 if (qn->lower > 0) {
5186 copy_node_opt_info(opt, &nopt);
5187 if (nopt.exb.len > 0) {
5188 if (nopt.exb.reach_end) {
5189 for (i = 2; i <= qn->lower &&
5190 ! is_full_opt_exact_info(&opt->exb); i++) {
5191 concat_opt_exact_info(&opt->exb, &nopt.exb, env->enc);
5193 if (i < qn->lower) {
5194 opt->exb.reach_end = 0;
5199 if (qn->lower != qn->upper) {
5200 opt->exb.reach_end = 0;
5201 opt->exm.reach_end = 0;
5204 opt->exm.reach_end = 0;
5208 min = distance_multiply(nopt.len.min, qn->lower);
5209 if (IS_REPEAT_INFINITE(qn->upper))
5210 max = (nopt.len.max > 0 ? ONIG_INFINITE_DISTANCE : 0);
5212 max = distance_multiply(nopt.len.max, qn->upper);
5214 set_mml(&opt->len, min, max);
5223 case ENCLOSE_OPTION:
5225 OnigOptionType save = env->options;
5227 env->options = en->option;
5228 r = optimize_node_left(en->target, opt, env);
5229 env->options = save;
5233 case ENCLOSE_MEMORY:
5234#ifdef USE_SUBEXP_CALL
5236 if (en->opt_count > MAX_NODE_OPT_INFO_REF_COUNT) {
5237 OnigDistance min, max;
5240 max = ONIG_INFINITE_DISTANCE;
5241 if (IS_ENCLOSE_MIN_FIXED(en)) min = en->min_len;
5242 if (IS_ENCLOSE_MAX_FIXED(en)) max = en->max_len;
5243 set_mml(&opt->len, min, max);
5248 r = optimize_node_left(en->target, opt, env);
5250 if (is_set_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_MASK)) {
5251 if (BIT_STATUS_AT(env->scan_env->backrefed_mem, en->regnum))
5252 remove_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_MASK);
5257 case ENCLOSE_STOP_BACKTRACK:
5258 case ENCLOSE_CONDITION:
5259 r = optimize_node_left(en->target, opt, env);
5262 case ENCLOSE_ABSENT:
5263 set_mml(&opt->len, 0, ONIG_INFINITE_DISTANCE);
5271 fprintf(stderr,
"optimize_node_left: undefined node type %d\n",
5274 r = ONIGERR_TYPE_BUG;
5286 if (e->len == 0)
return 0;
5288 reg->exact = (UChar* )
xmalloc(e->len);
5289 CHECK_NULL_RETURN_MEMERR(reg->exact);
5290 xmemcpy(reg->exact, e->s, e->len);
5291 reg->exact_end = reg->exact + e->len;
5294 ONIGENC_IS_ALLOWED_REVERSE_MATCH(reg->enc, reg->exact, reg->exact_end);
5296 if (e->ignore_case > 0) {
5297 if (e->len >= 3 || (e->len >= 2 && allow_reverse)) {
5298 int orig_len = e->len;
5299 e->len = set_bm_skip(reg->exact, reg->exact_end, reg,
5302 reg->exact_end = reg->exact + e->len;
5303 reg->optimize = (allow_reverse != 0
5304 ? ONIG_OPTIMIZE_EXACT_BM_IC : ONIG_OPTIMIZE_EXACT_BM_NOT_REV_IC);
5314 reg->optimize = ONIG_OPTIMIZE_EXACT_IC;
5318 reg->optimize = ONIG_OPTIMIZE_EXACT_IC;
5322 if (e->len >= 3 || (e->len >= 2 && allow_reverse)) {
5323 set_bm_skip(reg->exact, reg->exact_end, reg,
5325 reg->optimize = (allow_reverse != 0
5326 ? ONIG_OPTIMIZE_EXACT_BM : ONIG_OPTIMIZE_EXACT_BM_NOT_REV);
5329 reg->optimize = ONIG_OPTIMIZE_EXACT;
5333 reg->dmin = e->mmd.min;
5334 reg->dmax = e->mmd.max;
5336 if (reg->dmin != ONIG_INFINITE_DISTANCE) {
5337 reg->threshold_len = (int )(reg->dmin + (reg->exact_end - reg->exact));
5344set_optimize_map_info(regex_t* reg,
OptMapInfo* m)
5348 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
5349 reg->map[i] = m->map[i];
5351 reg->optimize = ONIG_OPTIMIZE_MAP;
5352 reg->dmin = m->mmd.min;
5353 reg->dmax = m->mmd.max;
5355 if (reg->dmin != ONIG_INFINITE_DISTANCE) {
5356 reg->threshold_len = (int )(reg->dmin + 1);
5363 reg->sub_anchor |= anc->left_anchor & ANCHOR_BEGIN_LINE;
5364 reg->sub_anchor |= anc->right_anchor & ANCHOR_END_LINE;
5367#if defined(ONIG_DEBUG_COMPILE) || defined(ONIG_DEBUG_MATCH)
5368static void print_optimize_info(FILE* f, regex_t* reg);
5372set_optimize_info_from_tree(Node* node, regex_t* reg,
ScanEnv* scan_env)
5380 env.options = reg->options;
5381 env.case_fold_flag = reg->case_fold_flag;
5382 env.scan_env = scan_env;
5383 clear_mml(&env.mmd);
5385 r = optimize_node_left(node, &opt, &env);
5388 reg->anchor = opt.anc.left_anchor & (ANCHOR_BEGIN_BUF |
5389 ANCHOR_BEGIN_POSITION | ANCHOR_ANYCHAR_STAR | ANCHOR_ANYCHAR_STAR_ML |
5390 ANCHOR_LOOK_BEHIND);
5392 if ((opt.anc.left_anchor & (ANCHOR_LOOK_BEHIND | ANCHOR_PREC_READ_NOT)) != 0)
5393 reg->anchor &= ~ANCHOR_ANYCHAR_STAR_ML;
5395 reg->anchor |= opt.anc.right_anchor & (ANCHOR_END_BUF | ANCHOR_SEMI_END_BUF |
5396 ANCHOR_PREC_READ_NOT);
5398 if (reg->anchor & (ANCHOR_END_BUF | ANCHOR_SEMI_END_BUF)) {
5399 reg->anchor_dmin = opt.len.min;
5400 reg->anchor_dmax = opt.len.max;
5403 if (opt.exb.len > 0 || opt.exm.len > 0) {
5404 select_opt_exact_info(reg->enc, &opt.exb, &opt.exm);
5405 if (opt.map.value > 0 &&
5406 comp_opt_exact_or_map_info(&opt.exb, &opt.map) > 0) {
5410 r = set_optimize_exact_info(reg, &opt.exb);
5411 set_sub_anchor(reg, &opt.exb.anc);
5414 else if (opt.map.value > 0) {
5416 set_optimize_map_info(reg, &opt.map);
5417 set_sub_anchor(reg, &opt.map.anc);
5420 reg->sub_anchor |= opt.anc.left_anchor & ANCHOR_BEGIN_LINE;
5421 if (opt.len.max == 0)
5422 reg->sub_anchor |= opt.anc.right_anchor & ANCHOR_END_LINE;
5425#if defined(ONIG_DEBUG_COMPILE) || defined(ONIG_DEBUG_MATCH)
5426 print_optimize_info(stderr, reg);
5432clear_optimize_info(regex_t* reg)
5434 reg->optimize = ONIG_OPTIMIZE_NONE;
5436 reg->anchor_dmin = 0;
5437 reg->anchor_dmax = 0;
5438 reg->sub_anchor = 0;
5439 reg->exact_end = (UChar* )NULL;
5440 reg->threshold_len = 0;
5442 reg->exact = (UChar* )NULL;
5447static void print_enc_string(FILE* fp, OnigEncoding enc,
5448 const UChar *s,
const UChar *end)
5450 fprintf(fp,
"\nPATTERN: /");
5452 if (ONIGENC_MBC_MINLEN(enc) > 1) {
5458 code = ONIGENC_MBC_TO_CODE(enc, p, end);
5460 fprintf(fp,
" 0x%04x ", (
int )code);
5463 fputc((
int )code, fp);
5466 p += enclen(enc, p, end);
5471 fputc((
int )*s, fp);
5476 fprintf(fp,
"/ (%s)\n", enc->name);
5480#if defined(ONIG_DEBUG_COMPILE) || defined(ONIG_DEBUG_MATCH)
5482print_distance_range(FILE* f, OnigDistance a, OnigDistance b)
5484 if (a == ONIG_INFINITE_DISTANCE)
5487 fprintf(f,
"(%"PRIuPTR
")", a);
5491 if (b == ONIG_INFINITE_DISTANCE)
5494 fprintf(f,
"(%"PRIuPTR
")", b);
5498print_anchor(FILE* f,
int anchor)
5504 if (anchor & ANCHOR_BEGIN_BUF) {
5505 fprintf(f,
"begin-buf");
5508 if (anchor & ANCHOR_BEGIN_LINE) {
5509 if (q) fprintf(f,
", ");
5511 fprintf(f,
"begin-line");
5513 if (anchor & ANCHOR_BEGIN_POSITION) {
5514 if (q) fprintf(f,
", ");
5516 fprintf(f,
"begin-pos");
5518 if (anchor & ANCHOR_END_BUF) {
5519 if (q) fprintf(f,
", ");
5521 fprintf(f,
"end-buf");
5523 if (anchor & ANCHOR_SEMI_END_BUF) {
5524 if (q) fprintf(f,
", ");
5526 fprintf(f,
"semi-end-buf");
5528 if (anchor & ANCHOR_END_LINE) {
5529 if (q) fprintf(f,
", ");
5531 fprintf(f,
"end-line");
5533 if (anchor & ANCHOR_ANYCHAR_STAR) {
5534 if (q) fprintf(f,
", ");
5536 fprintf(f,
"anychar-star");
5538 if (anchor & ANCHOR_ANYCHAR_STAR_ML) {
5539 if (q) fprintf(f,
", ");
5540 fprintf(f,
"anychar-star-ml");
5547print_optimize_info(FILE* f, regex_t* reg)
5549 static const char* on[] = {
"NONE",
"EXACT",
"EXACT_BM",
"EXACT_BM_NOT_REV",
5551 "EXACT_BM_IC",
"EXACT_BM_NOT_REV_IC" };
5553 fprintf(f,
"optimize: %s\n", on[reg->optimize]);
5554 fprintf(f,
" anchor: "); print_anchor(f, reg->anchor);
5555 if ((reg->anchor & ANCHOR_END_BUF_MASK) != 0)
5556 print_distance_range(f, reg->anchor_dmin, reg->anchor_dmax);
5559 if (reg->optimize) {
5560 fprintf(f,
" sub anchor: "); print_anchor(f, reg->sub_anchor);
5567 fprintf(f,
"exact: [");
5568 for (p = reg->exact; p < reg->exact_end; p++) {
5571 fprintf(f,
"]: length: %"PRIdPTR
"\n", (reg->exact_end - reg->exact));
5573 else if (reg->optimize & ONIG_OPTIMIZE_MAP) {
5576 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
5577 if (reg->map[i]) n++;
5579 fprintf(f,
"map: n=%d\n", n);
5583 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) {
5584 if (reg->map[i] != 0) {
5585 if (c > 0) fputs(
", ", f);
5587 if (ONIGENC_MBC_MAXLEN(reg->enc) == 1 &&
5588 ONIGENC_IS_CODE_PRINT(reg->enc, (OnigCodePoint )i))
5591 fprintf(f,
"%d", i);
5602onig_free_body(regex_t* reg)
5604 if (IS_NOT_NULL(reg)) {
5607 xfree(reg->repeat_range);
5608 onig_free(reg->chain);
5610#ifdef USE_NAMED_GROUP
5611 onig_names_free(reg);
5617onig_free(regex_t* reg)
5619 if (IS_NOT_NULL(reg)) {
5620 onig_free_body(reg);
5626dup_copy(
const void *ptr,
size_t size)
5629 if (IS_NOT_NULL(newptr)) {
5630 memcpy(newptr, ptr, size);
5636onig_reg_copy_body(regex_t* nreg, regex_t* oreg)
5638 if (IS_NOT_NULL(oreg)) {
5641# define COPY_FAILED(mem, size) IS_NULL(nreg->mem = dup_copy(oreg->mem, size))
5643 if (IS_NOT_NULL(oreg->exact)) {
5644 size_t exact_size = oreg->exact_end - oreg->exact;
5645 if (COPY_FAILED(exact, exact_size))
5647 (nreg)->exact_end = (nreg)->exact + exact_size;
5650 if (IS_NOT_NULL(oreg->p)) {
5651 if (COPY_FAILED(p, oreg->alloc))
5654 if (IS_NOT_NULL(oreg->repeat_range)) {
5655 if (COPY_FAILED(repeat_range, oreg->repeat_range_alloc *
sizeof(
OnigRepeatRange)))
5656 goto err_repeat_range;
5658 if (IS_NOT_NULL(oreg->name_table)) {
5659 if (onig_names_copy(nreg, oreg))
5660 goto err_name_table;
5662 if (IS_NOT_NULL(oreg->chain)) {
5663 if (onig_reg_copy(&nreg->chain, oreg->chain))
5670 onig_names_free(nreg);
5672 xfree(nreg->repeat_range);
5679 return ONIGERR_MEMORY;
5685onig_reg_copy(regex_t** nreg, regex_t* oreg)
5687 if (IS_NOT_NULL(oreg)) {
5688 regex_t *reg = *nreg = (regex_t* )
xmalloc(
sizeof(regex_t));
5689 if (IS_NULL(reg))
return ONIGERR_MEMORY;
5691 return onig_reg_copy_body(reg, oreg);
5698onig_memsize(
const regex_t *reg)
5700 size_t size =
sizeof(regex_t);
5701 if (IS_NULL(reg))
return 0;
5702 if (IS_NOT_NULL(reg->p)) size += reg->alloc;
5703 if (IS_NOT_NULL(reg->exact)) size += reg->exact_end - reg->exact;
5704 if (IS_NOT_NULL(reg->repeat_range)) size += reg->repeat_range_alloc *
sizeof(
OnigRepeatRange);
5705 if (IS_NOT_NULL(reg->chain)) size += onig_memsize(reg->chain);
5711onig_region_memsize(
const OnigRegion *regs)
5713 size_t size =
sizeof(*regs);
5714 if (IS_NULL(regs))
return 0;
5715 size += regs->allocated * (
sizeof(*regs->beg) +
sizeof(*regs->end));
5720#define REGEX_TRANSFER(to,from) do {\
5721 onig_free_body(to);\
5722 xmemcpy(to, from, sizeof(regex_t));\
5728onig_transfer(regex_t* to, regex_t* from)
5730 REGEX_TRANSFER(to, from);
5734#ifdef ONIG_DEBUG_COMPILE
5735static void print_compiled_byte_code_list(FILE* f, regex_t* reg);
5737#ifdef ONIG_DEBUG_PARSE_TREE
5738static void print_tree(FILE* f, Node* node);
5743onig_compile(regex_t* reg,
const UChar* pattern,
const UChar* pattern_end,
5746 return onig_compile_ruby(reg, pattern, pattern_end, einfo, NULL, 0);
5752onig_compile_ruby(regex_t* reg,
const UChar* pattern,
const UChar* pattern_end,
5753 OnigErrorInfo* einfo,
const char *sourcefile,
int sourceline)
5756onig_compile(regex_t* reg,
const UChar* pattern,
const UChar* pattern_end,
5760#define COMPILE_INIT_SIZE 20
5763 OnigDistance init_size;
5766#ifdef USE_SUBEXP_CALL
5770 if (IS_NOT_NULL(einfo)) einfo->par = (UChar* )NULL;
5773 scan_env.sourcefile = sourcefile;
5774 scan_env.sourceline = sourceline;
5778 print_enc_string(stderr, reg->enc, pattern, pattern_end);
5781 if (reg->alloc == 0) {
5782 init_size = (pattern_end - pattern) * 2;
5783 if (init_size <= 0) init_size = COMPILE_INIT_SIZE;
5784 r = BBUF_INIT(reg, init_size);
5785 if (r != 0)
goto end;
5791 reg->num_repeat = 0;
5792 reg->num_null_check = 0;
5793 reg->repeat_range_alloc = 0;
5795#ifdef USE_COMBINATION_EXPLOSION_CHECK
5796 reg->num_comb_exp_check = 0;
5799 r = onig_parse_make_tree(&root, pattern, pattern_end, reg, &scan_env);
5800 if (r != 0)
goto err;
5802#ifdef ONIG_DEBUG_PARSE_TREE
5804 fprintf(stderr,
"ORIGINAL PARSE TREE:\n");
5805 print_tree(stderr, root);
5809#ifdef USE_NAMED_GROUP
5811 if (scan_env.num_named > 0 &&
5812 IS_SYNTAX_BV(scan_env.syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
5813 !ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_CAPTURE_GROUP)) {
5814 if (scan_env.num_named != scan_env.num_mem)
5815 r = disable_noname_group_capture(&root, reg, &scan_env);
5817 r = numbered_ref_check(root);
5819 if (r != 0)
goto err;
5823#ifdef USE_SUBEXP_CALL
5824 if (scan_env.num_call > 0) {
5825 r = unset_addr_list_init(&uslist, scan_env.num_call);
5826 if (r != 0)
goto err;
5827 scan_env.unset_addr_list = &uslist;
5828 r = setup_subexp_call(root, &scan_env);
5829 if (r != 0)
goto err_unset;
5830 r = subexp_recursive_check_trav(root, &scan_env);
5831 if (r < 0)
goto err_unset;
5832 r = subexp_inf_recursive_check_trav(root, &scan_env);
5833 if (r != 0)
goto err_unset;
5835 reg->num_call = scan_env.num_call;
5841 r = setup_tree(root, reg, 0, &scan_env);
5842 if (r != 0)
goto err_unset;
5844#ifdef ONIG_DEBUG_PARSE_TREE
5845 print_tree(stderr, root);
5848 reg->capture_history = scan_env.capture_history;
5849 reg->bt_mem_start = scan_env.bt_mem_start;
5850 reg->bt_mem_start |= reg->capture_history;
5851 if (IS_FIND_CONDITION(reg->options))
5852 BIT_STATUS_ON_ALL(reg->bt_mem_end);
5854 reg->bt_mem_end = scan_env.bt_mem_end;
5855 reg->bt_mem_end |= reg->capture_history;
5858#ifdef USE_COMBINATION_EXPLOSION_CHECK
5859 if (scan_env.backrefed_mem == 0
5860# ifdef USE_SUBEXP_CALL
5861 || scan_env.num_call == 0
5864 setup_comb_exp_check(root, 0, &scan_env);
5865# ifdef USE_SUBEXP_CALL
5866 if (scan_env.has_recursion != 0) {
5867 scan_env.num_comb_exp_check = 0;
5871 if (scan_env.comb_exp_max_regnum > 0) {
5873 for (i = 1; i <= scan_env.comb_exp_max_regnum; i++) {
5874 if (BIT_STATUS_AT(scan_env.backrefed_mem, i) != 0) {
5875 scan_env.num_comb_exp_check = 0;
5882 reg->num_comb_exp_check = scan_env.num_comb_exp_check;
5885 clear_optimize_info(reg);
5886#ifndef ONIG_DONT_OPTIMIZE
5887 r = set_optimize_info_from_tree(root, reg, &scan_env);
5888 if (r != 0)
goto err_unset;
5891 if (IS_NOT_NULL(scan_env.mem_nodes_dynamic)) {
5892 xfree(scan_env.mem_nodes_dynamic);
5893 scan_env.mem_nodes_dynamic = (Node** )NULL;
5896 r = compile_tree(root, reg);
5898 r = add_opcode(reg, OP_END);
5899 if (r != 0)
goto err_unset;
5900#ifdef USE_SUBEXP_CALL
5901 if (scan_env.num_call > 0) {
5902 r = unset_addr_list_fix(&uslist, reg);
5903 unset_addr_list_end(&uslist);
5908 if ((reg->num_repeat != 0) || (reg->bt_mem_end != 0))
5909 reg->stack_pop_level = STACK_POP_LEVEL_ALL;
5911 if (reg->bt_mem_start != 0)
5912 reg->stack_pop_level = STACK_POP_LEVEL_MEM_START;
5914 reg->stack_pop_level = STACK_POP_LEVEL_FREE;
5917#ifdef USE_SUBEXP_CALL
5918 else if (scan_env.num_call > 0) {
5919 unset_addr_list_end(&uslist);
5922 onig_node_free(root);
5924#ifdef ONIG_DEBUG_COMPILE
5925# ifdef USE_NAMED_GROUP
5926 onig_print_names(stderr, reg);
5928 print_compiled_byte_code_list(stderr, reg);
5932 onig_reg_resize(reg);
5936#ifdef USE_SUBEXP_CALL
5937 if (scan_env.num_call > 0) {
5938 unset_addr_list_end(&uslist);
5942 if (IS_NOT_NULL(scan_env.error)) {
5943 if (IS_NOT_NULL(einfo)) {
5944 einfo->enc = scan_env.enc;
5945 einfo->par = scan_env.error;
5946 einfo->par_end = scan_env.error_end;
5950 onig_node_free(root);
5951 xfree(scan_env.mem_nodes_dynamic);
5956static int onig_inited = 0;
5959onig_reg_init(regex_t* reg, OnigOptionType option,
5960 OnigCaseFoldType case_fold_flag,
5967 return ONIGERR_INVALID_ARGUMENT;
5969 (reg)->exact = (UChar* )NULL;
5970 (reg)->chain = (regex_t* )NULL;
5971 (reg)->p = (UChar* )NULL;
5972 (reg)->name_table = (
void* )NULL;
5975 if (ONIGENC_IS_UNDEF(enc))
5976 return ONIGERR_DEFAULT_ENCODING_IS_NOT_SET;
5978 if ((option & (ONIG_OPTION_DONT_CAPTURE_GROUP|ONIG_OPTION_CAPTURE_GROUP))
5979 == (ONIG_OPTION_DONT_CAPTURE_GROUP|ONIG_OPTION_CAPTURE_GROUP)) {
5980 return ONIGERR_INVALID_COMBINATION_OF_OPTIONS;
5983 if ((option & ONIG_OPTION_NEGATE_SINGLELINE) != 0) {
5984 option |= syntax->options;
5985 option &= ~ONIG_OPTION_SINGLELINE;
5988 option |= syntax->options;
5991 (reg)->options = option;
5992 (reg)->syntax = syntax;
5993 (reg)->optimize = 0;
5998 (reg)->case_fold_flag = case_fold_flag;
6000 (reg)->timelimit = 0;
6006onig_new_without_alloc(regex_t* reg,
const UChar* pattern,
6007 const UChar* pattern_end, OnigOptionType option, OnigEncoding enc,
6012 r = onig_reg_init(reg, option, ONIGENC_CASE_FOLD_DEFAULT, enc, syntax);
6015 r = onig_compile(reg, pattern, pattern_end, einfo);
6020onig_new(regex_t** reg,
const UChar* pattern,
const UChar* pattern_end,
6021 OnigOptionType option, OnigEncoding enc,
const OnigSyntaxType* syntax,
6024 *reg = (regex_t* )
xmalloc(
sizeof(regex_t));
6025 if (IS_NULL(*reg))
return ONIGERR_MEMORY;
6027 int r = onig_new_without_alloc(*reg, pattern, pattern_end, option, enc, syntax, einfo);
6037onig_initialize(OnigEncoding encodings[] ARG_UNUSED,
int n ARG_UNUSED)
6045 if (onig_inited != 0)
6050#if defined(ONIG_DEBUG_MEMLEAK) && defined(_MSC_VER)
6051 _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
6057#ifdef ONIG_DEBUG_STATISTICS
6058 onig_statistics_init();
6065static OnigEndCallListItemType* EndCallTop;
6067extern void onig_add_end_call(
void (*func)(
void))
6069 OnigEndCallListItemType* item;
6071 item = (OnigEndCallListItemType* )
xmalloc(
sizeof(*item));
6072 if (item == 0) return ;
6074 item->next = EndCallTop;
6081exec_end_call_list(
void)
6083 OnigEndCallListItemType* prev;
6086 while (EndCallTop != 0) {
6087 func = EndCallTop->func;
6091 EndCallTop = EndCallTop->next;
6099 exec_end_call_list();
6101#ifdef ONIG_DEBUG_STATISTICS
6102 onig_print_statistics(stderr);
6105#if defined(ONIG_DEBUG_MEMLEAK) && defined(_MSC_VER)
6106 _CrtDumpMemoryLeaks();
6115onig_is_in_code_range(
const UChar* p, OnigCodePoint code)
6117 OnigCodePoint n, *data;
6118 OnigCodePoint low, high, x;
6120 GET_CODE_POINT(n, p);
6121 data = (OnigCodePoint* )p;
6124 for (low = 0, high = n; low < high; ) {
6125 x = (low + high) >> 1;
6126 if (code > data[x * 2 + 1])
6132 return ((low < n && code >= data[low * 2]) ? 1 : 0);
6136onig_is_code_in_cc_len(
int elen, OnigCodePoint code,
CClassNode* cc)
6140 if (elen > 1 || (code >= SINGLE_BYTE_SIZE)) {
6141 if (IS_NULL(cc->mbuf)) {
6145 found = (onig_is_in_code_range(cc->mbuf->p, code) != 0 ? 1 : 0);
6149 found = (BITSET_AT(cc->bs, code) == 0 ? 0 : 1);
6152 if (IS_NCCLASS_NOT(cc))
6159onig_is_code_in_cc(OnigEncoding enc, OnigCodePoint code,
CClassNode* cc)
6163 if (ONIGENC_MBC_MINLEN(enc) > 1) {
6167 len = ONIGENC_CODE_TO_MBCLEN(enc, code);
6169 return onig_is_code_in_cc_len(
len, code, cc);
6176# define ARG_SPECIAL -1
6178# define ARG_RELADDR 1
6179# define ARG_ABSADDR 2
6180# define ARG_LENGTH 3
6181# define ARG_MEMNUM 4
6182# define ARG_OPTION 5
6183# define ARG_STATE_CHECK 6
6185OnigOpInfoType OnigOpInfo[] = {
6186 { OP_FINISH,
"finish", ARG_NON },
6187 { OP_END,
"end", ARG_NON },
6188 { OP_EXACT1,
"exact1", ARG_SPECIAL },
6189 { OP_EXACT2,
"exact2", ARG_SPECIAL },
6190 { OP_EXACT3,
"exact3", ARG_SPECIAL },
6191 { OP_EXACT4,
"exact4", ARG_SPECIAL },
6192 { OP_EXACT5,
"exact5", ARG_SPECIAL },
6193 { OP_EXACTN,
"exactn", ARG_SPECIAL },
6194 { OP_EXACTMB2N1,
"exactmb2-n1", ARG_SPECIAL },
6195 { OP_EXACTMB2N2,
"exactmb2-n2", ARG_SPECIAL },
6196 { OP_EXACTMB2N3,
"exactmb2-n3", ARG_SPECIAL },
6197 { OP_EXACTMB2N,
"exactmb2-n", ARG_SPECIAL },
6198 { OP_EXACTMB3N,
"exactmb3n" , ARG_SPECIAL },
6199 { OP_EXACTMBN,
"exactmbn", ARG_SPECIAL },
6200 { OP_EXACT1_IC,
"exact1-ic", ARG_SPECIAL },
6201 { OP_EXACTN_IC,
"exactn-ic", ARG_SPECIAL },
6202 { OP_CCLASS,
"cclass", ARG_SPECIAL },
6203 { OP_CCLASS_MB,
"cclass-mb", ARG_SPECIAL },
6204 { OP_CCLASS_MIX,
"cclass-mix", ARG_SPECIAL },
6205 { OP_CCLASS_NOT,
"cclass-not", ARG_SPECIAL },
6206 { OP_CCLASS_MB_NOT,
"cclass-mb-not", ARG_SPECIAL },
6207 { OP_CCLASS_MIX_NOT,
"cclass-mix-not", ARG_SPECIAL },
6208 { OP_ANYCHAR,
"anychar", ARG_NON },
6209 { OP_ANYCHAR_ML,
"anychar-ml", ARG_NON },
6210 { OP_ANYCHAR_STAR,
"anychar*", ARG_NON },
6211 { OP_ANYCHAR_ML_STAR,
"anychar-ml*", ARG_NON },
6212 { OP_ANYCHAR_STAR_PEEK_NEXT,
"anychar*-peek-next", ARG_SPECIAL },
6213 { OP_ANYCHAR_ML_STAR_PEEK_NEXT,
"anychar-ml*-peek-next", ARG_SPECIAL },
6214 { OP_WORD,
"word", ARG_NON },
6215 { OP_NOT_WORD,
"not-word", ARG_NON },
6216 { OP_WORD_BOUND,
"word-bound", ARG_NON },
6217 { OP_NOT_WORD_BOUND,
"not-word-bound", ARG_NON },
6218 { OP_WORD_BEGIN,
"word-begin", ARG_NON },
6219 { OP_WORD_END,
"word-end", ARG_NON },
6220 { OP_ASCII_WORD,
"ascii-word", ARG_NON },
6221 { OP_NOT_ASCII_WORD,
"not-ascii-word", ARG_NON },
6222 { OP_ASCII_WORD_BOUND,
"ascii-word-bound", ARG_NON },
6223 { OP_NOT_ASCII_WORD_BOUND,
"not-ascii-word-bound", ARG_NON },
6224 { OP_ASCII_WORD_BEGIN,
"ascii-word-begin", ARG_NON },
6225 { OP_ASCII_WORD_END,
"ascii-word-end", ARG_NON },
6226 { OP_BEGIN_BUF,
"begin-buf", ARG_NON },
6227 { OP_END_BUF,
"end-buf", ARG_NON },
6228 { OP_BEGIN_LINE,
"begin-line", ARG_NON },
6229 { OP_END_LINE,
"end-line", ARG_NON },
6230 { OP_SEMI_END_BUF,
"semi-end-buf", ARG_NON },
6231 { OP_BEGIN_POSITION,
"begin-position", ARG_NON },
6232 { OP_BACKREF1,
"backref1", ARG_NON },
6233 { OP_BACKREF2,
"backref2", ARG_NON },
6234 { OP_BACKREFN,
"backrefn", ARG_MEMNUM },
6235 { OP_BACKREFN_IC,
"backrefn-ic", ARG_SPECIAL },
6236 { OP_BACKREF_MULTI,
"backref_multi", ARG_SPECIAL },
6237 { OP_BACKREF_MULTI_IC,
"backref_multi-ic", ARG_SPECIAL },
6238 { OP_BACKREF_WITH_LEVEL,
"backref_at_level", ARG_SPECIAL },
6239 { OP_MEMORY_START_PUSH,
"mem-start-push", ARG_MEMNUM },
6240 { OP_MEMORY_START,
"mem-start", ARG_MEMNUM },
6241 { OP_MEMORY_END_PUSH,
"mem-end-push", ARG_MEMNUM },
6242 { OP_MEMORY_END_PUSH_REC,
"mem-end-push-rec", ARG_MEMNUM },
6243 { OP_MEMORY_END,
"mem-end", ARG_MEMNUM },
6244 { OP_MEMORY_END_REC,
"mem-end-rec", ARG_MEMNUM },
6245 { OP_SET_OPTION_PUSH,
"set-option-push", ARG_OPTION },
6246 { OP_SET_OPTION,
"set-option", ARG_OPTION },
6247 { OP_KEEP,
"keep", ARG_NON },
6248 { OP_FAIL,
"fail", ARG_NON },
6249 { OP_JUMP,
"jump", ARG_RELADDR },
6250 { OP_PUSH,
"push", ARG_RELADDR },
6251 { OP_POP,
"pop", ARG_NON },
6252 { OP_PUSH_OR_JUMP_EXACT1,
"push-or-jump-e1", ARG_SPECIAL },
6253 { OP_PUSH_IF_PEEK_NEXT,
"push-if-peek-next", ARG_SPECIAL },
6254 { OP_REPEAT,
"repeat", ARG_SPECIAL },
6255 { OP_REPEAT_NG,
"repeat-ng", ARG_SPECIAL },
6256 { OP_REPEAT_INC,
"repeat-inc", ARG_MEMNUM },
6257 { OP_REPEAT_INC_NG,
"repeat-inc-ng", ARG_MEMNUM },
6258 { OP_REPEAT_INC_SG,
"repeat-inc-sg", ARG_MEMNUM },
6259 { OP_REPEAT_INC_NG_SG,
"repeat-inc-ng-sg", ARG_MEMNUM },
6260 { OP_NULL_CHECK_START,
"null-check-start", ARG_MEMNUM },
6261 { OP_NULL_CHECK_END,
"null-check-end", ARG_MEMNUM },
6262 { OP_NULL_CHECK_END_MEMST,
"null-check-end-memst", ARG_MEMNUM },
6263 { OP_NULL_CHECK_END_MEMST_PUSH,
"null-check-end-memst-push", ARG_MEMNUM },
6264 { OP_PUSH_POS,
"push-pos", ARG_NON },
6265 { OP_POP_POS,
"pop-pos", ARG_NON },
6266 { OP_PUSH_POS_NOT,
"push-pos-not", ARG_RELADDR },
6267 { OP_FAIL_POS,
"fail-pos", ARG_NON },
6268 { OP_PUSH_STOP_BT,
"push-stop-bt", ARG_NON },
6269 { OP_POP_STOP_BT,
"pop-stop-bt", ARG_NON },
6270 { OP_LOOK_BEHIND,
"look-behind", ARG_SPECIAL },
6271 { OP_PUSH_LOOK_BEHIND_NOT,
"push-look-behind-not", ARG_SPECIAL },
6272 { OP_FAIL_LOOK_BEHIND_NOT,
"fail-look-behind-not", ARG_NON },
6273 { OP_PUSH_ABSENT_POS,
"push-absent-pos", ARG_NON },
6274 { OP_ABSENT,
"absent", ARG_RELADDR },
6275 { OP_ABSENT_END,
"absent-end", ARG_NON },
6276 { OP_CALL,
"call", ARG_ABSADDR },
6277 { OP_RETURN,
"return", ARG_NON },
6278 { OP_CONDITION,
"condition", ARG_SPECIAL },
6279 { OP_STATE_CHECK_PUSH,
"state-check-push", ARG_SPECIAL },
6280 { OP_STATE_CHECK_PUSH_OR_JUMP,
"state-check-push-or-jump", ARG_SPECIAL },
6281 { OP_STATE_CHECK,
"state-check", ARG_STATE_CHECK },
6282 { OP_STATE_CHECK_ANYCHAR_STAR,
"state-check-anychar*", ARG_STATE_CHECK },
6283 { OP_STATE_CHECK_ANYCHAR_ML_STAR,
6284 "state-check-anychar-ml*", ARG_STATE_CHECK },
6293 for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
6294 if (opcode == OnigOpInfo[i].opcode)
6295 return OnigOpInfo[i].name;
6301op2arg_type(
int opcode)
6305 for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
6306 if (opcode == OnigOpInfo[i].opcode)
6307 return OnigOpInfo[i].arg_type;
6312# ifdef ONIG_DEBUG_PARSE_TREE
6314Indent(FILE* f,
int indent)
6317 for (i = 0; i < indent; i++) putc(
' ', f);
6322p_string(FILE* f, ptrdiff_t
len, UChar* s)
6325 while (
len-- > 0) { fputc(*s++, f); }
6329p_len_string(FILE* f, LengthType
len,
int mb_len, UChar* s)
6331 int x =
len * mb_len;
6333 fprintf(f,
":%d:",
len);
6334 while (x-- > 0) { fputc(*s++, f); }
6338onig_print_compiled_byte_code(FILE* f, UChar* bp, UChar* bpend, UChar** nextp,
6345 StateCheckNumType scn;
6349 fprintf(f,
"[%s", op2name(*bp));
6350 arg_type = op2arg_type(*bp);
6351 if (arg_type != ARG_SPECIAL) {
6357 GET_RELADDR_INC(addr, bp);
6358 fprintf(f,
":(%s%d)", (addr >= 0) ?
"+" :
"", addr);
6361 GET_ABSADDR_INC(addr, bp);
6362 fprintf(f,
":(%d)", addr);
6365 GET_LENGTH_INC(
len, bp);
6366 fprintf(f,
":%d",
len);
6369 mem = *((MemNumType* )bp);
6371 fprintf(f,
":%d", mem);
6375 OnigOptionType option = *((OnigOptionType* )bp);
6377 fprintf(f,
":%d", option);
6381 case ARG_STATE_CHECK:
6382 scn = *((StateCheckNumType* )bp);
6383 bp += SIZE_STATE_CHECK_NUM;
6384 fprintf(f,
":%d", scn);
6391 case OP_ANYCHAR_STAR_PEEK_NEXT:
6392 case OP_ANYCHAR_ML_STAR_PEEK_NEXT:
6393 p_string(f, 1, bp++);
break;
6395 p_string(f, 2, bp); bp += 2;
break;
6397 p_string(f, 3, bp); bp += 3;
break;
6399 p_string(f, 4, bp); bp += 4;
break;
6401 p_string(f, 5, bp); bp += 5;
break;
6403 GET_LENGTH_INC(
len, bp);
6404 p_len_string(f,
len, 1, bp);
6409 p_string(f, 2, bp); bp += 2;
break;
6411 p_string(f, 4, bp); bp += 4;
break;
6413 p_string(f, 6, bp); bp += 6;
break;
6415 GET_LENGTH_INC(
len, bp);
6416 p_len_string(f,
len, 2, bp);
6420 GET_LENGTH_INC(
len, bp);
6421 p_len_string(f,
len, 3, bp);
6428 GET_LENGTH_INC(mb_len, bp);
6429 GET_LENGTH_INC(
len, bp);
6430 fprintf(f,
":%d:%d:", mb_len,
len);
6432 while (n-- > 0) { fputc(*bp++, f); }
6437 len = enclen(enc, bp, bpend);
6438 p_string(f,
len, bp);
6442 GET_LENGTH_INC(
len, bp);
6443 p_len_string(f,
len, 1, bp);
6448 n = bitset_on_num((BitSetRef )bp);
6450 fprintf(f,
":%d", n);
6454 n = bitset_on_num((BitSetRef )bp);
6456 fprintf(f,
":%d", n);
6460 case OP_CCLASS_MB_NOT:
6461 GET_LENGTH_INC(
len, bp);
6463# ifndef PLATFORM_UNALIGNED_WORD_ACCESS
6466 GET_CODE_POINT(code, q);
6468 fprintf(f,
":%d:%d", (
int )code,
len);
6472 case OP_CCLASS_MIX_NOT:
6473 n = bitset_on_num((BitSetRef )bp);
6475 GET_LENGTH_INC(
len, bp);
6477# ifndef PLATFORM_UNALIGNED_WORD_ACCESS
6480 GET_CODE_POINT(code, q);
6482 fprintf(f,
":%d:%d:%d", n, (
int )code,
len);
6485 case OP_BACKREFN_IC:
6486 mem = *((MemNumType* )bp);
6488 fprintf(f,
":%d", mem);
6491 case OP_BACKREF_MULTI_IC:
6492 case OP_BACKREF_MULTI:
6494 GET_LENGTH_INC(
len, bp);
6495 for (i = 0; i <
len; i++) {
6496 GET_MEMNUM_INC(mem, bp);
6497 if (i > 0) fputs(
", ", f);
6498 fprintf(f,
"%d", mem);
6502 case OP_BACKREF_WITH_LEVEL:
6504 OnigOptionType option;
6507 GET_OPTION_INC(option, bp);
6508 fprintf(f,
":%d", option);
6509 GET_LENGTH_INC(level, bp);
6510 fprintf(f,
":%d", level);
6513 GET_LENGTH_INC(
len, bp);
6514 for (i = 0; i <
len; i++) {
6515 GET_MEMNUM_INC(mem, bp);
6516 if (i > 0) fputs(
", ", f);
6517 fprintf(f,
"%d", mem);
6525 mem = *((MemNumType* )bp);
6527 addr = *((RelAddrType* )bp);
6529 fprintf(f,
":%d:%d", mem, addr);
6533 case OP_PUSH_OR_JUMP_EXACT1:
6534 case OP_PUSH_IF_PEEK_NEXT:
6535 addr = *((RelAddrType* )bp);
6537 fprintf(f,
":(%s%d)", (addr >= 0) ?
"+" :
"", addr);
6542 case OP_LOOK_BEHIND:
6543 GET_LENGTH_INC(
len, bp);
6544 fprintf(f,
":%d",
len);
6547 case OP_PUSH_LOOK_BEHIND_NOT:
6548 GET_RELADDR_INC(addr, bp);
6549 GET_LENGTH_INC(
len, bp);
6550 fprintf(f,
":%d:(%s%d)",
len, (addr >= 0) ?
"+" :
"", addr);
6553 case OP_STATE_CHECK_PUSH:
6554 case OP_STATE_CHECK_PUSH_OR_JUMP:
6555 scn = *((StateCheckNumType* )bp);
6556 bp += SIZE_STATE_CHECK_NUM;
6557 addr = *((RelAddrType* )bp);
6559 fprintf(f,
":%d:(%s%d)", scn, (addr >= 0) ?
"+" :
"", addr);
6563 GET_MEMNUM_INC(mem, bp);
6564 GET_RELADDR_INC(addr, bp);
6565 fprintf(f,
":%d:(%s%d)", mem, (addr >= 0) ?
"+" :
"", addr);
6569 fprintf(stderr,
"onig_print_compiled_byte_code: undefined code %d\n",
6574 if (nextp) *nextp = bp;
6577# ifdef ONIG_DEBUG_COMPILE
6579print_compiled_byte_code_list(FILE* f, regex_t* reg)
6583 UChar* end = reg->p + reg->used;
6585 fprintf(f,
"code length: %d", reg->used);
6591 fprintf(f,
"\n%ld:", bp - reg->p);
6593 fprintf(f,
" %ld:", bp - reg->p);
6594 onig_print_compiled_byte_code(f, bp, end, &bp, reg->enc);
6601# ifdef ONIG_DEBUG_PARSE_TREE
6603print_indent_tree(FILE* f, Node* node,
int indent)
6605 int i,
type, container_p = 0;
6610 if (IS_NULL(node)) {
6611 fprintf(f,
"ERROR: null node!!!\n");
6619 if (NTYPE(node) == NT_LIST)
6620 fprintf(f,
"<list:%"PRIxPTR
">\n", (intptr_t )node);
6622 fprintf(f,
"<alt:%"PRIxPTR
">\n", (intptr_t )node);
6624 print_indent_tree(f, NCAR(node), indent + add);
6625 while (IS_NOT_NULL(node = NCDR(node))) {
6626 if (NTYPE(node) != type) {
6627 fprintf(f,
"ERROR: list/alt right is not a cons. %d\n", NTYPE(node));
6630 print_indent_tree(f, NCAR(node), indent + add);
6635 fprintf(f,
"<string%s:%"PRIxPTR
">",
6636 (NSTRING_IS_RAW(node) ?
"-raw" :
""), (intptr_t )node);
6637 for (p = NSTR(node)->s; p < NSTR(node)->end; p++) {
6638 if (*p >= 0x20 && *p < 0x7f)
6641 fprintf(f,
" 0x%02x", *p);
6647 fprintf(f,
"<cclass:%"PRIxPTR
">", (intptr_t )node);
6648 if (IS_NCCLASS_NOT(NCCLASS(node))) fputs(
"not ", f);
6649 if (NCCLASS(node)->mbuf) {
6650 BBuf* bbuf = NCCLASS(node)->mbuf;
6651 OnigCodePoint* data = (OnigCodePoint* )bbuf->p;
6652 OnigCodePoint* end = (OnigCodePoint* )(bbuf->p + bbuf->used);
6653 fprintf(f,
"%d", *data++);
6654 for (; data < end; data+=2) {
6656 fprintf(f,
"%04x-%04x", data[0], data[1]);
6662 fprintf(f,
"<ctype:%"PRIxPTR
"> ", (intptr_t )node);
6663 switch (NCTYPE(node)->ctype) {
6664 case ONIGENC_CTYPE_WORD:
6665 if (NCTYPE(node)->not != 0)
6666 fputs(
"not word", f);
6672 fprintf(f,
"ERROR: undefined ctype.\n");
6678 fprintf(f,
"<anychar:%"PRIxPTR
">", (intptr_t )node);
6682 fprintf(f,
"<anchor:%"PRIxPTR
"> ", (intptr_t )node);
6683 switch (NANCHOR(node)->type) {
6684 case ANCHOR_BEGIN_BUF: fputs(
"begin buf", f);
break;
6685 case ANCHOR_END_BUF: fputs(
"end buf", f);
break;
6686 case ANCHOR_BEGIN_LINE: fputs(
"begin line", f);
break;
6687 case ANCHOR_END_LINE: fputs(
"end line", f);
break;
6688 case ANCHOR_SEMI_END_BUF: fputs(
"semi end buf", f);
break;
6689 case ANCHOR_BEGIN_POSITION: fputs(
"begin position", f);
break;
6691 case ANCHOR_WORD_BOUND: fputs(
"word bound", f);
break;
6692 case ANCHOR_NOT_WORD_BOUND: fputs(
"not word bound", f);
break;
6693# ifdef USE_WORD_BEGIN_END
6694 case ANCHOR_WORD_BEGIN: fputs(
"word begin", f);
break;
6695 case ANCHOR_WORD_END: fputs(
"word end", f);
break;
6697 case ANCHOR_PREC_READ: fputs(
"prec read", f); container_p = TRUE;
break;
6698 case ANCHOR_PREC_READ_NOT: fputs(
"prec read not", f); container_p = TRUE;
break;
6699 case ANCHOR_LOOK_BEHIND: fputs(
"look_behind", f); container_p = TRUE;
break;
6700 case ANCHOR_LOOK_BEHIND_NOT: fputs(
"look_behind_not",f); container_p = TRUE;
break;
6701 case ANCHOR_KEEP: fputs(
"keep",f);
break;
6704 fprintf(f,
"ERROR: undefined anchor type.\n");
6714 fprintf(f,
"<backref:%"PRIxPTR
">", (intptr_t )node);
6715 for (i = 0; i < br->back_num; i++) {
6716 if (i > 0) fputs(
", ", f);
6717 fprintf(f,
"%d", p[i]);
6722# ifdef USE_SUBEXP_CALL
6726 fprintf(f,
"<call:%"PRIxPTR
">", (intptr_t )node);
6727 p_string(f, cn->name_end - cn->name, cn->name);
6733 fprintf(f,
"<quantifier:%"PRIxPTR
">{%d,%d}%s\n", (intptr_t )node,
6734 NQTFR(node)->lower, NQTFR(node)->upper,
6735 (NQTFR(node)->greedy ?
"" :
"?"));
6736 print_indent_tree(f, NQTFR(node)->target, indent + add);
6740 fprintf(f,
"<enclose:%"PRIxPTR
"> ", (intptr_t )node);
6741 switch (NENCLOSE(node)->type) {
6742 case ENCLOSE_OPTION:
6743 fprintf(f,
"option:%d", NENCLOSE(node)->option);
6745 case ENCLOSE_MEMORY:
6746 fprintf(f,
"memory:%d", NENCLOSE(node)->regnum);
6748 case ENCLOSE_STOP_BACKTRACK:
6749 fprintf(f,
"stop-bt");
6751 case ENCLOSE_CONDITION:
6752 fprintf(f,
"condition:%d", NENCLOSE(node)->regnum);
6754 case ENCLOSE_ABSENT:
6755 fprintf(f,
"absent");
6762 print_indent_tree(f, NENCLOSE(node)->target, indent + add);
6766 fprintf(f,
"print_indent_tree: undefined node type %d\n", NTYPE(node));
6770 if (type != NT_LIST && type != NT_ALT && type != NT_QTFR &&
6774 if (container_p) print_indent_tree(f, NANCHOR(node)->target, indent + add);
6780print_tree(FILE* f, Node* node)
6782 print_indent_tree(f, node, 0);
#define xfree
Old name of ruby_xfree.
#define xrealloc
Old name of ruby_xrealloc.
#define xmalloc
Old name of ruby_xmalloc.
int len
Length of the buffer.
VALUE type(ANYARGS)
ANYARGS-ed function type.