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;
230check_compiled_program_size(regex_t* reg, OnigDistance add_len)
232 if (reg->used > MAX_COMPILED_PROGRAM_SIZE ||
233 add_len > (OnigDistance )(MAX_COMPILED_PROGRAM_SIZE - reg->used))
234 return ONIGERR_TOO_BIG_COMPILED_PROGRAM;
239add_opcode(regex_t* reg,
int opcode)
241 int r = check_compiled_program_size(reg, 1);
243 BBUF_ADD1(reg, opcode);
247#ifdef USE_COMBINATION_EXPLOSION_CHECK
249add_state_check_num(regex_t* reg,
int num)
251 StateCheckNumType n = (StateCheckNumType )num;
253 BBUF_ADD(reg, &n, SIZE_STATE_CHECK_NUM);
259add_rel_addr(regex_t* reg,
int addr)
261 RelAddrType ra = (RelAddrType )addr;
263 BBUF_ADD(reg, &ra, SIZE_RELADDR);
268add_abs_addr(regex_t* reg,
int addr)
270 AbsAddrType ra = (AbsAddrType )addr;
272 BBUF_ADD(reg, &ra, SIZE_ABSADDR);
277add_length(regex_t* reg, OnigDistance
len)
279 LengthType l = (LengthType )
len;
281 BBUF_ADD(reg, &l, SIZE_LENGTH);
286add_mem_num(regex_t* reg,
int num)
288 MemNumType n = (MemNumType )num;
290 BBUF_ADD(reg, &n, SIZE_MEMNUM);
296add_pointer(regex_t* reg,
void* addr)
298 PointerType
ptr = (PointerType )addr;
300 BBUF_ADD(reg, &
ptr, SIZE_POINTER);
306add_option(regex_t* reg, OnigOptionType option)
308 BBUF_ADD(reg, &option, SIZE_OPTION);
313add_opcode_rel_addr(regex_t* reg,
int opcode,
int addr)
317 r = add_opcode(reg, opcode);
319 r = add_rel_addr(reg, addr);
324add_bytes(regex_t* reg, UChar* bytes, OnigDistance
len)
326 int r = check_compiled_program_size(reg,
len);
328 BBUF_ADD(reg, bytes,
len);
333add_bitset(regex_t* reg, BitSetRef bs)
335 int r = check_compiled_program_size(reg, SIZE_BITSET);
337 BBUF_ADD(reg, bs, SIZE_BITSET);
342add_opcode_option(regex_t* reg,
int opcode, OnigOptionType option)
346 r = add_opcode(reg, opcode);
348 r = add_option(reg, option);
352static int compile_length_tree(Node* node, regex_t* reg);
353static int compile_tree(Node* node, regex_t* reg);
356#define IS_NEED_STR_LEN_OP_EXACT(op) \
357 ((op) == OP_EXACTN || (op) == OP_EXACTMB2N ||\
358 (op) == OP_EXACTMB3N || (op) == OP_EXACTMBN || (op) == OP_EXACTN_IC)
361select_str_opcode(
int mb_len, OnigDistance byte_len,
int ignore_case)
364 OnigDistance str_len = roomof(byte_len, mb_len);
368 case 1: op = OP_EXACT1_IC;
break;
369 default: op = OP_EXACTN_IC;
break;
376 case 1: op = OP_EXACT1;
break;
377 case 2: op = OP_EXACT2;
break;
378 case 3: op = OP_EXACT3;
break;
379 case 4: op = OP_EXACT4;
break;
380 case 5: op = OP_EXACT5;
break;
381 default: op = OP_EXACTN;
break;
387 case 1: op = OP_EXACTMB2N1;
break;
388 case 2: op = OP_EXACTMB2N2;
break;
389 case 3: op = OP_EXACTMB2N3;
break;
390 default: op = OP_EXACTMB2N;
break;
407compile_tree_empty_check(Node* node, regex_t* reg,
int empty_info)
410 int saved_num_null_check = reg->num_null_check;
412 if (empty_info != 0) {
413 r = add_opcode(reg, OP_NULL_CHECK_START);
415 r = add_mem_num(reg, reg->num_null_check);
417 reg->num_null_check++;
418 if ((MemNumType)reg->num_null_check <= 0)
return ONIGERR_TOO_MANY_NULL_CHECK;
421 r = compile_tree(node, reg);
424 if (empty_info != 0) {
425 if (empty_info == NQ_TARGET_IS_EMPTY)
426 r = add_opcode(reg, OP_NULL_CHECK_END);
427 else if (empty_info == NQ_TARGET_IS_EMPTY_MEM)
428 r = add_opcode(reg, OP_NULL_CHECK_END_MEMST);
429 else if (empty_info == NQ_TARGET_IS_EMPTY_REC)
430 r = add_opcode(reg, OP_NULL_CHECK_END_MEMST_PUSH);
433 r = add_mem_num(reg, saved_num_null_check);
438#ifdef USE_SUBEXP_CALL
440compile_call(
CallNode* node, regex_t* reg)
444 r = add_opcode(reg, OP_CALL);
446 r = unset_addr_list_add(node->unset_addr_list, BBUF_GET_OFFSET_POS(reg),
449 r = add_abs_addr(reg, 0 );
455compile_tree_n_times(Node* node,
int n, regex_t* reg)
459 for (i = 0; i < n; i++) {
460 r = compile_tree(node, reg);
467add_compile_string_length(UChar* s ARG_UNUSED,
int mb_len, OnigDistance byte_len,
468 regex_t* reg ARG_UNUSED,
int ignore_case)
471 int op = select_str_opcode(mb_len, byte_len, ignore_case);
475 if (op == OP_EXACTMBN)
len += SIZE_LENGTH;
476 if (IS_NEED_STR_LEN_OP_EXACT(op))
479 len += (int )byte_len;
484add_compile_string(UChar* s,
int mb_len, OnigDistance byte_len,
485 regex_t* reg,
int ignore_case)
488 int op = select_str_opcode(mb_len, byte_len, ignore_case);
489 r = add_opcode(reg, op);
492 if (op == OP_EXACTMBN) {
493 r = add_length(reg, mb_len);
497 if (IS_NEED_STR_LEN_OP_EXACT(op)) {
498 if (op == OP_EXACTN_IC)
499 r = add_length(reg, byte_len);
501 r = add_length(reg, byte_len / mb_len);
505 return add_bytes(reg, s, byte_len);
510compile_length_string_node(Node* node, regex_t* reg)
512 int rlen, r,
len, prev_len, blen, ambig;
513 OnigEncoding enc = reg->enc;
518 if (sn->end <= sn->s)
521 ambig = NSTRING_IS_AMBIG(node);
524 prev_len = enclen(enc, p, sn->end);
529 for (; p < sn->end; ) {
530 len = enclen(enc, p, sn->end);
531 if (
len == prev_len || ambig) {
535 r = add_compile_string_length(prev, prev_len, blen, reg, ambig);
543 r = add_compile_string_length(prev, prev_len, blen, reg, ambig);
549compile_length_string_raw_node(
StrNode* sn, regex_t* reg)
551 if (sn->end <= sn->s)
554 return add_compile_string_length(sn->s, 1 , sn->end - sn->s, reg, 0);
558compile_string_node(Node* node, regex_t* reg)
560 int r,
len, prev_len, blen, ambig;
561 OnigEncoding enc = reg->enc;
562 UChar *p, *prev, *end;
566 if (sn->end <= sn->s)
570 ambig = NSTRING_IS_AMBIG(node);
573 prev_len = enclen(enc, p, end);
578 len = enclen(enc, p, end);
579 if (
len == prev_len || ambig) {
583 r = add_compile_string(prev, prev_len, blen, reg, ambig);
593 return add_compile_string(prev, prev_len, blen, reg, ambig);
597compile_string_raw_node(
StrNode* sn, regex_t* reg)
599 if (sn->end <= sn->s)
602 return add_compile_string(sn->s, 1 , sn->end - sn->s, reg, 0);
606add_multi_byte_cclass(BBuf* mbuf, regex_t* reg)
608#ifdef PLATFORM_UNALIGNED_WORD_ACCESS
609 int r = add_length(reg, mbuf->used);
611 return add_bytes(reg, mbuf->p, mbuf->used);
614 UChar* p = BBUF_GET_ADD_ADDRESS(reg) + SIZE_LENGTH;
616 GET_ALIGNMENT_PAD_SIZE(p, pad_size);
617 r = add_length(reg, mbuf->used + (WORD_ALIGNMENT_SIZE - 1));
620 r = add_bytes(reg, PadBuf, pad_size);
624 r = add_bytes(reg, mbuf->p, mbuf->used);
628 pad_size = (WORD_ALIGNMENT_SIZE - 1) - pad_size;
629 if (pad_size != 0) r = add_bytes(reg, PadBuf, pad_size);
635compile_length_cclass_node(
CClassNode* cc, regex_t* reg)
639 if (IS_NULL(cc->mbuf)) {
640 len = SIZE_OPCODE + SIZE_BITSET;
643 if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {
647 len = SIZE_OPCODE + SIZE_BITSET;
649#ifdef PLATFORM_UNALIGNED_WORD_ACCESS
650 len += SIZE_LENGTH + cc->mbuf->used;
652 len += SIZE_LENGTH + cc->mbuf->used + (WORD_ALIGNMENT_SIZE - 1);
660compile_cclass_node(
CClassNode* cc, regex_t* reg)
664 if (IS_NULL(cc->mbuf)) {
665 if (IS_NCCLASS_NOT(cc))
666 r = add_opcode(reg, OP_CCLASS_NOT);
668 r = add_opcode(reg, OP_CCLASS);
671 r = add_bitset(reg, cc->bs);
674 if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {
675 if (IS_NCCLASS_NOT(cc))
676 r = add_opcode(reg, OP_CCLASS_MB_NOT);
678 r = add_opcode(reg, OP_CCLASS_MB);
681 r = add_multi_byte_cclass(cc->mbuf, reg);
684 if (IS_NCCLASS_NOT(cc))
685 r = add_opcode(reg, OP_CCLASS_MIX_NOT);
687 r = add_opcode(reg, OP_CCLASS_MIX);
690 r = add_bitset(reg, cc->bs);
692 r = add_multi_byte_cclass(cc->mbuf, reg);
700entry_repeat_range(regex_t* reg,
int id,
int lower,
int upper)
702#define REPEAT_RANGE_ALLOC 4
706 if (reg->repeat_range_alloc == 0) {
708 CHECK_NULL_RETURN_MEMERR(p);
709 reg->repeat_range = p;
710 reg->repeat_range_alloc = REPEAT_RANGE_ALLOC;
712 else if (reg->repeat_range_alloc <=
id) {
714 n = reg->repeat_range_alloc + REPEAT_RANGE_ALLOC;
717 CHECK_NULL_RETURN_MEMERR(p);
718 reg->repeat_range = p;
719 reg->repeat_range_alloc = n;
722 p = reg->repeat_range;
726 p[id].upper = (IS_REPEAT_INFINITE(upper) ? 0x7fffffff : upper);
731compile_range_repeat_node(
QtfrNode* qn,
int target_len,
int empty_info,
735 int num_repeat = reg->num_repeat;
737 r = add_opcode(reg, qn->greedy ? OP_REPEAT : OP_REPEAT_NG);
739 r = add_mem_num(reg, num_repeat);
741 if ((MemNumType)reg->num_repeat <= 0)
return ONIGERR_TOO_MANY_RANGE_REPEAT;
743 r = add_rel_addr(reg, target_len + SIZE_OP_REPEAT_INC);
746 r = entry_repeat_range(reg, num_repeat, qn->lower, qn->upper);
749 r = compile_tree_empty_check(qn->target, reg, empty_info);
753#ifdef USE_SUBEXP_CALL
756 IS_QUANTIFIER_IN_REPEAT(qn)) {
757 r = add_opcode(reg, qn->greedy ? OP_REPEAT_INC_SG : OP_REPEAT_INC_NG_SG);
760 r = add_opcode(reg, qn->greedy ? OP_REPEAT_INC : OP_REPEAT_INC_NG);
763 r = add_mem_num(reg, num_repeat);
768is_anychar_star_quantifier(
QtfrNode* qn)
770 if (qn->greedy && IS_REPEAT_INFINITE(qn->upper) &&
771 NTYPE(qn->target) == NT_CANY)
777#define QUANTIFIER_EXPAND_LIMIT_SIZE 50
780#define IS_EXPAND_LIMIT_OK(tlen, n) \
781 ((n) <= 0 || (tlen) <= QUANTIFIER_EXPAND_LIMIT_SIZE / (n))
782#define CKN_ON (ckn > 0)
784#ifdef USE_COMBINATION_EXPLOSION_CHECK
787compile_length_quantifier_node(
QtfrNode* qn, regex_t* reg)
789 int len, mod_tlen, cklen;
791 int infinite = IS_REPEAT_INFINITE(qn->upper);
792 int empty_info = qn->target_empty_info;
793 int tlen = compile_length_tree(qn->target, reg);
795 if (tlen < 0)
return tlen;
797 ckn = ((reg->num_comb_exp_check > 0) ? qn->comb_exp_check_num : 0);
799 cklen = (CKN_ON ? SIZE_STATE_CHECK_NUM: 0);
802 if (NTYPE(qn->target) == NT_CANY) {
803 if (qn->greedy && infinite) {
804 if (IS_NOT_NULL(qn->next_head_exact) && !CKN_ON)
805 return SIZE_OP_ANYCHAR_STAR_PEEK_NEXT + tlen * qn->lower + cklen;
807 return SIZE_OP_ANYCHAR_STAR + tlen * qn->lower + cklen;
812 mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
816 if (infinite && qn->lower <= 1) {
823 len += SIZE_OP_PUSH + cklen + mod_tlen + SIZE_OP_JUMP;
831 len += mod_tlen + SIZE_OP_PUSH + cklen;
834 else if (qn->upper == 0) {
835 if (qn->is_referred != 0)
836 len = SIZE_OP_JUMP + tlen;
840 else if (qn->upper == 1 && qn->greedy) {
841 if (qn->lower == 0) {
843 len = SIZE_OP_STATE_CHECK_PUSH + tlen;
846 len = SIZE_OP_PUSH + tlen;
853 else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) {
854 len = SIZE_OP_PUSH + cklen + SIZE_OP_JUMP + tlen;
857 len = SIZE_OP_REPEAT_INC
858 + mod_tlen + SIZE_OPCODE + SIZE_RELADDR + SIZE_MEMNUM;
860 len += SIZE_OP_STATE_CHECK;
867compile_quantifier_node(
QtfrNode* qn, regex_t* reg)
871 int infinite = IS_REPEAT_INFINITE(qn->upper);
872 int empty_info = qn->target_empty_info;
873 int tlen = compile_length_tree(qn->target, reg);
875 if (tlen < 0)
return tlen;
877 ckn = ((reg->num_comb_exp_check > 0) ? qn->comb_exp_check_num : 0);
879 if (is_anychar_star_quantifier(qn)) {
880 r = compile_tree_n_times(qn->target, qn->lower, reg);
882 if (IS_NOT_NULL(qn->next_head_exact) && !CKN_ON) {
883 if (IS_MULTILINE(reg->options))
884 r = add_opcode(reg, OP_ANYCHAR_ML_STAR_PEEK_NEXT);
886 r = add_opcode(reg, OP_ANYCHAR_STAR_PEEK_NEXT);
889 r = add_state_check_num(reg, ckn);
893 return add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
896 if (IS_MULTILINE(reg->options)) {
897 r = add_opcode(reg, (CKN_ON ?
898 OP_STATE_CHECK_ANYCHAR_ML_STAR
899 : OP_ANYCHAR_ML_STAR));
902 r = add_opcode(reg, (CKN_ON ?
903 OP_STATE_CHECK_ANYCHAR_STAR
908 r = add_state_check_num(reg, ckn);
915 mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
919 if (infinite && qn->lower <= 1) {
921 if (qn->lower == 1) {
922 r = add_opcode_rel_addr(reg, OP_JUMP,
923 (CKN_ON ? SIZE_OP_STATE_CHECK_PUSH : SIZE_OP_PUSH));
928 r = add_opcode(reg, OP_STATE_CHECK_PUSH);
930 r = add_state_check_num(reg, ckn);
932 r = add_rel_addr(reg, mod_tlen + SIZE_OP_JUMP);
935 r = add_opcode_rel_addr(reg, OP_PUSH, mod_tlen + SIZE_OP_JUMP);
938 r = compile_tree_empty_check(qn->target, reg, empty_info);
940 r = add_opcode_rel_addr(reg, OP_JUMP,
941 -(mod_tlen + (
int )SIZE_OP_JUMP
942 + (
int )(CKN_ON ? SIZE_OP_STATE_CHECK_PUSH : SIZE_OP_PUSH)));
945 if (qn->lower == 0) {
946 r = add_opcode_rel_addr(reg, OP_JUMP, mod_tlen);
949 r = compile_tree_empty_check(qn->target, reg, empty_info);
952 r = add_opcode(reg, OP_STATE_CHECK_PUSH_OR_JUMP);
954 r = add_state_check_num(reg, ckn);
956 r = add_rel_addr(reg,
957 -(mod_tlen + (
int )SIZE_OP_STATE_CHECK_PUSH_OR_JUMP));
960 r = add_opcode_rel_addr(reg, OP_PUSH, -(mod_tlen + (
int )SIZE_OP_PUSH));
963 else if (qn->upper == 0) {
964 if (qn->is_referred != 0) {
965 r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
967 r = compile_tree(qn->target, reg);
972 else if (qn->upper == 1 && qn->greedy) {
973 if (qn->lower == 0) {
975 r = add_opcode(reg, OP_STATE_CHECK_PUSH);
977 r = add_state_check_num(reg, ckn);
979 r = add_rel_addr(reg, tlen);
982 r = add_opcode_rel_addr(reg, OP_PUSH, tlen);
987 r = compile_tree(qn->target, reg);
989 else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) {
991 r = add_opcode(reg, OP_STATE_CHECK_PUSH);
993 r = add_state_check_num(reg, ckn);
995 r = add_rel_addr(reg, SIZE_OP_JUMP);
998 r = add_opcode_rel_addr(reg, OP_PUSH, SIZE_OP_JUMP);
1002 r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
1004 r = compile_tree(qn->target, reg);
1007 r = compile_range_repeat_node(qn, mod_tlen, empty_info, reg);
1010 r = add_opcode(reg, OP_STATE_CHECK);
1012 r = add_state_check_num(reg, ckn);
1021compile_length_quantifier_node(
QtfrNode* qn, regex_t* reg)
1024 int infinite = IS_REPEAT_INFINITE(qn->upper);
1025 int empty_info = qn->target_empty_info;
1026 int tlen = compile_length_tree(qn->target, reg);
1028 if (tlen < 0)
return tlen;
1031 if (NTYPE(qn->target) == NT_CANY) {
1032 if (qn->greedy && infinite) {
1033 if (IS_NOT_NULL(qn->next_head_exact))
1034 return SIZE_OP_ANYCHAR_STAR_PEEK_NEXT + tlen * qn->lower;
1036 return SIZE_OP_ANYCHAR_STAR + tlen * qn->lower;
1040 if (empty_info != 0)
1041 mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
1046 (qn->lower <= 1 || IS_EXPAND_LIMIT_OK(tlen, qn->lower))) {
1047 if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
1051 len = tlen * qn->lower;
1055#ifdef USE_OP_PUSH_OR_JUMP_EXACT
1056 if (IS_NOT_NULL(qn->head_exact))
1057 len += SIZE_OP_PUSH_OR_JUMP_EXACT1 + mod_tlen + SIZE_OP_JUMP;
1060 if (IS_NOT_NULL(qn->next_head_exact))
1061 len += SIZE_OP_PUSH_IF_PEEK_NEXT + mod_tlen + SIZE_OP_JUMP;
1063 len += SIZE_OP_PUSH + mod_tlen + SIZE_OP_JUMP;
1066 len += SIZE_OP_JUMP + mod_tlen + SIZE_OP_PUSH;
1068 else if (qn->upper == 0 && qn->is_referred != 0) {
1069 len = SIZE_OP_JUMP + tlen;
1071 else if (!infinite && qn->greedy &&
1073 IS_EXPAND_LIMIT_OK(tlen + SIZE_OP_PUSH, qn->upper))) {
1074 len = tlen * qn->lower;
1075 len += (SIZE_OP_PUSH + tlen) * (qn->upper - qn->lower);
1077 else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) {
1078 len = SIZE_OP_PUSH + SIZE_OP_JUMP + tlen;
1081 len = SIZE_OP_REPEAT_INC
1082 + mod_tlen + SIZE_OPCODE + SIZE_RELADDR + SIZE_MEMNUM;
1089compile_quantifier_node(
QtfrNode* qn, regex_t* reg)
1092 int infinite = IS_REPEAT_INFINITE(qn->upper);
1093 int empty_info = qn->target_empty_info;
1094 int tlen = compile_length_tree(qn->target, reg);
1096 if (tlen < 0)
return tlen;
1098 if (is_anychar_star_quantifier(qn)) {
1099 r = compile_tree_n_times(qn->target, qn->lower, reg);
1101 if (IS_NOT_NULL(qn->next_head_exact)) {
1102 if (IS_MULTILINE(reg->options))
1103 r = add_opcode(reg, OP_ANYCHAR_ML_STAR_PEEK_NEXT);
1105 r = add_opcode(reg, OP_ANYCHAR_STAR_PEEK_NEXT);
1107 return add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
1110 if (IS_MULTILINE(reg->options))
1111 return add_opcode(reg, OP_ANYCHAR_ML_STAR);
1113 return add_opcode(reg, OP_ANYCHAR_STAR);
1117 if (empty_info != 0)
1118 mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
1123 (qn->lower <= 1 || IS_EXPAND_LIMIT_OK(tlen, qn->lower))) {
1124 if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
1126#ifdef USE_OP_PUSH_OR_JUMP_EXACT
1127 if (IS_NOT_NULL(qn->head_exact))
1128 r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH_OR_JUMP_EXACT1);
1131 if (IS_NOT_NULL(qn->next_head_exact))
1132 r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH_IF_PEEK_NEXT);
1134 r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH);
1137 r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_JUMP);
1142 r = compile_tree_n_times(qn->target, qn->lower, reg);
1147#ifdef USE_OP_PUSH_OR_JUMP_EXACT
1148 if (IS_NOT_NULL(qn->head_exact)) {
1149 r = add_opcode_rel_addr(reg, OP_PUSH_OR_JUMP_EXACT1,
1150 mod_tlen + SIZE_OP_JUMP);
1152 r = add_bytes(reg, NSTR(qn->head_exact)->s, 1);
1154 r = compile_tree_empty_check(qn->target, reg, empty_info);
1156 r = add_opcode_rel_addr(reg, OP_JUMP,
1157 -(mod_tlen + (
int )SIZE_OP_JUMP + (
int )SIZE_OP_PUSH_OR_JUMP_EXACT1));
1161 if (IS_NOT_NULL(qn->next_head_exact)) {
1162 r = add_opcode_rel_addr(reg, OP_PUSH_IF_PEEK_NEXT,
1163 mod_tlen + SIZE_OP_JUMP);
1165 r = add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
1167 r = compile_tree_empty_check(qn->target, reg, empty_info);
1169 r = add_opcode_rel_addr(reg, OP_JUMP,
1170 -(mod_tlen + (
int )SIZE_OP_JUMP + (
int )SIZE_OP_PUSH_IF_PEEK_NEXT));
1173 r = add_opcode_rel_addr(reg, OP_PUSH, mod_tlen + SIZE_OP_JUMP);
1175 r = compile_tree_empty_check(qn->target, reg, empty_info);
1177 r = add_opcode_rel_addr(reg, OP_JUMP,
1178 -(mod_tlen + (
int )SIZE_OP_JUMP + (
int )SIZE_OP_PUSH));
1182 r = add_opcode_rel_addr(reg, OP_JUMP, mod_tlen);
1184 r = compile_tree_empty_check(qn->target, reg, empty_info);
1186 r = add_opcode_rel_addr(reg, OP_PUSH, -(mod_tlen + (
int )SIZE_OP_PUSH));
1189 else if (qn->upper == 0 && qn->is_referred != 0) {
1190 r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
1192 r = compile_tree(qn->target, reg);
1194 else if (!infinite && qn->greedy &&
1196 IS_EXPAND_LIMIT_OK(tlen + SIZE_OP_PUSH, qn->upper))) {
1197 int n = qn->upper - qn->lower;
1199 r = compile_tree_n_times(qn->target, qn->lower, reg);
1202 for (i = 0; i < n; i++) {
1203 r = add_opcode_rel_addr(reg, OP_PUSH,
1204 (n - i) * tlen + (n - i - 1) * SIZE_OP_PUSH);
1206 r = compile_tree(qn->target, reg);
1210 else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) {
1211 r = add_opcode_rel_addr(reg, OP_PUSH, SIZE_OP_JUMP);
1213 r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
1215 r = compile_tree(qn->target, reg);
1218 r = compile_range_repeat_node(qn, mod_tlen, empty_info, reg);
1225compile_length_option_node(
EncloseNode* node, regex_t* reg)
1228 OnigOptionType prev = reg->options;
1230 reg->options = node->option;
1231 tlen = compile_length_tree(node->target, reg);
1232 reg->options = prev;
1234 if (tlen < 0)
return tlen;
1236 if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1237 return SIZE_OP_SET_OPTION_PUSH + SIZE_OP_SET_OPTION + SIZE_OP_FAIL
1238 + tlen + SIZE_OP_SET_OPTION;
1245compile_option_node(
EncloseNode* node, regex_t* reg)
1248 OnigOptionType prev = reg->options;
1250 if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1251 r = add_opcode_option(reg, OP_SET_OPTION_PUSH, node->option);
1253 r = add_opcode_option(reg, OP_SET_OPTION, prev);
1255 r = add_opcode(reg, OP_FAIL);
1259 reg->options = node->option;
1260 r = compile_tree(node->target, reg);
1261 reg->options = prev;
1263 if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1265 r = add_opcode_option(reg, OP_SET_OPTION, prev);
1271compile_length_enclose_node(
EncloseNode* node, regex_t* reg)
1276 if (node->type == ENCLOSE_OPTION)
1277 return compile_length_option_node(node, reg);
1280 tlen = compile_length_tree(node->target, reg);
1281 if (tlen < 0)
return tlen;
1286 switch (node->type) {
1287 case ENCLOSE_MEMORY:
1288#ifdef USE_SUBEXP_CALL
1289 if (IS_ENCLOSE_CALLED(node)) {
1290 len = SIZE_OP_MEMORY_START_PUSH + tlen
1291 + SIZE_OP_CALL + SIZE_OP_JUMP + SIZE_OP_RETURN;
1292 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1293 len += (IS_ENCLOSE_RECURSION(node)
1294 ? SIZE_OP_MEMORY_END_PUSH_REC : SIZE_OP_MEMORY_END_PUSH);
1296 len += (IS_ENCLOSE_RECURSION(node)
1297 ? SIZE_OP_MEMORY_END_REC : SIZE_OP_MEMORY_END);
1299 else if (IS_ENCLOSE_RECURSION(node)) {
1300 len = SIZE_OP_MEMORY_START_PUSH;
1301 len += tlen + (BIT_STATUS_AT(reg->bt_mem_end, node->regnum)
1302 ? SIZE_OP_MEMORY_END_PUSH_REC : SIZE_OP_MEMORY_END_REC);
1307 if (BIT_STATUS_AT(reg->bt_mem_start, node->regnum))
1308 len = SIZE_OP_MEMORY_START_PUSH;
1310 len = SIZE_OP_MEMORY_START;
1312 len += tlen + (BIT_STATUS_AT(reg->bt_mem_end, node->regnum)
1313 ? SIZE_OP_MEMORY_END_PUSH : SIZE_OP_MEMORY_END);
1317 case ENCLOSE_STOP_BACKTRACK:
1321#ifndef USE_MATCH_CACHE
1322 if (IS_ENCLOSE_STOP_BT_SIMPLE_REPEAT(node)) {
1323 QtfrNode* qn = NQTFR(node->target);
1324 tlen = compile_length_tree(qn->target, reg);
1325 if (tlen < 0)
return tlen;
1327 len = tlen * qn->lower
1328 + SIZE_OP_PUSH + tlen + SIZE_OP_POP + SIZE_OP_JUMP;
1332 len = SIZE_OP_PUSH_STOP_BT + tlen + SIZE_OP_POP_STOP_BT;
1333#ifndef USE_MATCH_CACHE
1338 case ENCLOSE_CONDITION:
1339 len = SIZE_OP_CONDITION;
1340 if (NTYPE(node->target) == NT_ALT) {
1341 Node* x = node->target;
1343 tlen = compile_length_tree(NCAR(x), reg);
1344 if (tlen < 0)
return tlen;
1345 len += tlen + SIZE_OP_JUMP;
1346 if (NCDR(x) == NULL)
return ONIGERR_PARSER_BUG;
1348 tlen = compile_length_tree(NCAR(x), reg);
1349 if (tlen < 0)
return tlen;
1351 if (NCDR(x) != NULL)
return ONIGERR_INVALID_CONDITION_PATTERN;
1354 return ONIGERR_PARSER_BUG;
1358 case ENCLOSE_ABSENT:
1359 len = SIZE_OP_PUSH_ABSENT_POS + SIZE_OP_ABSENT + tlen + SIZE_OP_ABSENT_END;
1363 return ONIGERR_TYPE_BUG;
1370static int get_char_length_tree(Node* node, regex_t* reg,
int*
len);
1373compile_enclose_node(
EncloseNode* node, regex_t* reg)
1377 if (node->type == ENCLOSE_OPTION)
1378 return compile_option_node(node, reg);
1380 switch (node->type) {
1381 case ENCLOSE_MEMORY:
1382#ifdef USE_SUBEXP_CALL
1383 if (IS_ENCLOSE_CALLED(node)) {
1384 r = add_opcode(reg, OP_CALL);
1386 node->call_addr = BBUF_GET_OFFSET_POS(reg) + SIZE_ABSADDR + SIZE_OP_JUMP;
1387 node->state |= NST_ADDR_FIXED;
1388 r = add_abs_addr(reg, (
int )node->call_addr);
1390 len = compile_length_tree(node->target, reg);
1392 len += (SIZE_OP_MEMORY_START_PUSH + SIZE_OP_RETURN);
1393 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1394 len += (IS_ENCLOSE_RECURSION(node)
1395 ? SIZE_OP_MEMORY_END_PUSH_REC : SIZE_OP_MEMORY_END_PUSH);
1397 len += (IS_ENCLOSE_RECURSION(node)
1398 ? SIZE_OP_MEMORY_END_REC : SIZE_OP_MEMORY_END);
1400 r = add_opcode_rel_addr(reg, OP_JUMP,
len);
1404 if (BIT_STATUS_AT(reg->bt_mem_start, node->regnum))
1405 r = add_opcode(reg, OP_MEMORY_START_PUSH);
1407 r = add_opcode(reg, OP_MEMORY_START);
1409 r = add_mem_num(reg, node->regnum);
1411 r = compile_tree(node->target, reg);
1413#ifdef USE_SUBEXP_CALL
1414 if (IS_ENCLOSE_CALLED(node)) {
1415 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1416 r = add_opcode(reg, (IS_ENCLOSE_RECURSION(node)
1417 ? OP_MEMORY_END_PUSH_REC : OP_MEMORY_END_PUSH));
1419 r = add_opcode(reg, (IS_ENCLOSE_RECURSION(node)
1420 ? OP_MEMORY_END_REC : OP_MEMORY_END));
1423 r = add_mem_num(reg, node->regnum);
1425 r = add_opcode(reg, OP_RETURN);
1427 else if (IS_ENCLOSE_RECURSION(node)) {
1428 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1429 r = add_opcode(reg, OP_MEMORY_END_PUSH_REC);
1431 r = add_opcode(reg, OP_MEMORY_END_REC);
1433 r = add_mem_num(reg, node->regnum);
1438 if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1439 r = add_opcode(reg, OP_MEMORY_END_PUSH);
1441 r = add_opcode(reg, OP_MEMORY_END);
1443 r = add_mem_num(reg, node->regnum);
1447 case ENCLOSE_STOP_BACKTRACK:
1451#ifndef USE_MATCH_CACHE
1452 if (IS_ENCLOSE_STOP_BT_SIMPLE_REPEAT(node)) {
1453 QtfrNode* qn = NQTFR(node->target);
1454 r = compile_tree_n_times(qn->target, qn->lower, reg);
1457 len = compile_length_tree(qn->target, reg);
1460 r = add_opcode_rel_addr(reg, OP_PUSH,
len + SIZE_OP_POP + SIZE_OP_JUMP);
1462 r = compile_tree(qn->target, reg);
1464 r = add_opcode(reg, OP_POP);
1466 r = add_opcode_rel_addr(reg, OP_JUMP,
1467 -((
int )SIZE_OP_PUSH +
len + (
int )SIZE_OP_POP + (
int )SIZE_OP_JUMP));
1471 r = add_opcode(reg, OP_PUSH_STOP_BT);
1473 r = compile_tree(node->target, reg);
1475 r = add_opcode(reg, OP_POP_STOP_BT);
1476#ifndef USE_MATCH_CACHE
1481 case ENCLOSE_CONDITION:
1482 r = add_opcode(reg, OP_CONDITION);
1484 r = add_mem_num(reg, node->regnum);
1487 if (NTYPE(node->target) == NT_ALT) {
1488 Node* x = node->target;
1491 len = compile_length_tree(NCAR(x), reg);
1493 if (NCDR(x) == NULL)
return ONIGERR_PARSER_BUG;
1495 len2 = compile_length_tree(NCAR(x), reg);
1496 if (len2 < 0)
return len2;
1497 if (NCDR(x) != NULL)
return ONIGERR_INVALID_CONDITION_PATTERN;
1500 r = add_rel_addr(reg,
len + SIZE_OP_JUMP);
1502 r = compile_tree(NCAR(x), reg);
1504 r = add_opcode_rel_addr(reg, OP_JUMP, len2);
1507 r = compile_tree(NCAR(x), reg);
1510 return ONIGERR_PARSER_BUG;
1514 case ENCLOSE_ABSENT:
1515 len = compile_length_tree(node->target, reg);
1518 r = add_opcode(reg, OP_PUSH_ABSENT_POS);
1520 r = add_opcode_rel_addr(reg, OP_ABSENT,
len + SIZE_OP_ABSENT_END);
1522 r = compile_tree(node->target, reg);
1524 r = add_opcode(reg, OP_ABSENT_END);
1528 return ONIGERR_TYPE_BUG;
1536compile_length_anchor_node(
AnchorNode* node, regex_t* reg)
1542 tlen = compile_length_tree(node->target, reg);
1543 if (tlen < 0)
return tlen;
1546 switch (node->type) {
1547 case ANCHOR_PREC_READ:
1548 len = SIZE_OP_PUSH_POS + tlen + SIZE_OP_POP_POS;
1550 case ANCHOR_PREC_READ_NOT:
1551 len = SIZE_OP_PUSH_POS_NOT + tlen + SIZE_OP_FAIL_POS;
1553 case ANCHOR_LOOK_BEHIND:
1554 len = SIZE_OP_LOOK_BEHIND + tlen;
1556 case ANCHOR_LOOK_BEHIND_NOT:
1557 len = SIZE_OP_PUSH_LOOK_BEHIND_NOT + tlen + SIZE_OP_FAIL_LOOK_BEHIND_NOT;
1569compile_anchor_node(
AnchorNode* node, regex_t* reg)
1573 switch (node->type) {
1574 case ANCHOR_BEGIN_BUF: r = add_opcode(reg, OP_BEGIN_BUF);
break;
1575 case ANCHOR_END_BUF: r = add_opcode(reg, OP_END_BUF);
break;
1576 case ANCHOR_BEGIN_LINE: r = add_opcode(reg, OP_BEGIN_LINE);
break;
1577 case ANCHOR_END_LINE: r = add_opcode(reg, OP_END_LINE);
break;
1578 case ANCHOR_SEMI_END_BUF: r = add_opcode(reg, OP_SEMI_END_BUF);
break;
1579 case ANCHOR_BEGIN_POSITION: r = add_opcode(reg, OP_BEGIN_POSITION);
break;
1581 case ANCHOR_WORD_BOUND:
1582 if (node->ascii_range) r = add_opcode(reg, OP_ASCII_WORD_BOUND);
1583 else r = add_opcode(reg, OP_WORD_BOUND);
1585 case ANCHOR_NOT_WORD_BOUND:
1586 if (node->ascii_range) r = add_opcode(reg, OP_NOT_ASCII_WORD_BOUND);
1587 else r = add_opcode(reg, OP_NOT_WORD_BOUND);
1589#ifdef USE_WORD_BEGIN_END
1590 case ANCHOR_WORD_BEGIN:
1591 if (node->ascii_range) r = add_opcode(reg, OP_ASCII_WORD_BEGIN);
1592 else r = add_opcode(reg, OP_WORD_BEGIN);
1594 case ANCHOR_WORD_END:
1595 if (node->ascii_range) r = add_opcode(reg, OP_ASCII_WORD_END);
1596 else r = add_opcode(reg, OP_WORD_END);
1599 case ANCHOR_KEEP: r = add_opcode(reg, OP_KEEP);
break;
1601 case ANCHOR_PREC_READ:
1602 r = add_opcode(reg, OP_PUSH_POS);
1604 r = compile_tree(node->target, reg);
1606 r = add_opcode(reg, OP_POP_POS);
1609 case ANCHOR_PREC_READ_NOT:
1610 len = compile_length_tree(node->target, reg);
1612 r = add_opcode_rel_addr(reg, OP_PUSH_POS_NOT,
len + SIZE_OP_FAIL_POS);
1614 r = compile_tree(node->target, reg);
1616 r = add_opcode(reg, OP_FAIL_POS);
1619 case ANCHOR_LOOK_BEHIND:
1622 r = add_opcode(reg, OP_LOOK_BEHIND);
1624 if (node->char_len < 0) {
1625 r = get_char_length_tree(node->target, reg, &n);
1626 if (r)
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
1630 r = add_length(reg, n);
1632 r = compile_tree(node->target, reg);
1636 case ANCHOR_LOOK_BEHIND_NOT:
1639 len = compile_length_tree(node->target, reg);
1640 if (
len < 0)
return ONIGERR_PARSER_BUG;
1641 r = add_opcode_rel_addr(reg, OP_PUSH_LOOK_BEHIND_NOT,
1642 len + SIZE_OP_FAIL_LOOK_BEHIND_NOT);
1644 if (node->char_len < 0) {
1645 r = get_char_length_tree(node->target, reg, &n);
1646 if (r)
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
1650 r = add_length(reg, n);
1652 r = compile_tree(node->target, reg);
1654 r = add_opcode(reg, OP_FAIL_LOOK_BEHIND_NOT);
1659 return ONIGERR_TYPE_BUG;
1667compile_length_tree(Node* node, regex_t* reg)
1676 r = compile_length_tree(NCAR(node), reg);
1677 if (r < 0)
return r;
1679 if (
len > (
int )MAX_COMPILED_PROGRAM_SIZE)
1680 return ONIGERR_TOO_BIG_COMPILED_PROGRAM;
1681 }
while (IS_NOT_NULL(node = NCDR(node)));
1688 r = compile_length_tree(NCAR(node), reg);
1689 if (r < 0)
return r;
1691 if (IS_NOT_NULL(NCDR(node)))
1692 len += SIZE_OP_PUSH + SIZE_OP_JUMP;
1693 if (
len > (
int )MAX_COMPILED_PROGRAM_SIZE)
1694 return ONIGERR_TOO_BIG_COMPILED_PROGRAM;
1695 }
while (IS_NOT_NULL(node = NCDR(node)));
1700 if (NSTRING_IS_RAW(node))
1701 r = compile_length_string_raw_node(NSTR(node), reg);
1703 r = compile_length_string_node(node, reg);
1707 r = compile_length_cclass_node(NCCLASS(node), reg);
1719#ifdef USE_BACKREF_WITH_LEVEL
1720 if (IS_BACKREF_NEST_LEVEL(br)) {
1721 r = SIZE_OPCODE + SIZE_OPTION + SIZE_LENGTH +
1722 SIZE_LENGTH + (SIZE_MEMNUM * br->back_num);
1726 if (br->back_num == 1) {
1727 r = ((!IS_IGNORECASE(reg->options) && br->back_static[0] <= 2)
1728 ? SIZE_OPCODE : (SIZE_OPCODE + SIZE_MEMNUM));
1731 r = SIZE_OPCODE + SIZE_LENGTH + (SIZE_MEMNUM * br->back_num);
1736#ifdef USE_SUBEXP_CALL
1743 r = compile_length_quantifier_node(NQTFR(node), reg);
1747 r = compile_length_enclose_node(NENCLOSE(node), reg);
1751 r = compile_length_anchor_node(NANCHOR(node), reg);
1755 return ONIGERR_TYPE_BUG;
1759 if (r > (
int )MAX_COMPILED_PROGRAM_SIZE)
1760 return ONIGERR_TOO_BIG_COMPILED_PROGRAM;
1765compile_tree(Node* node, regex_t* reg)
1773 r = compile_tree(NCAR(node), reg);
1774 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
1782 r = compile_length_tree(NCAR(x), reg);
1783 if (r < 0)
return r;
1785 if (NCDR(x) != NULL) {
1786 len += SIZE_OP_PUSH + SIZE_OP_JUMP;
1788 if (
len > (
int )MAX_COMPILED_PROGRAM_SIZE)
1789 return ONIGERR_TOO_BIG_COMPILED_PROGRAM;
1790 }
while (IS_NOT_NULL(x = NCDR(x)));
1791 pos = reg->used +
len;
1794 len = compile_length_tree(NCAR(node), reg);
1795 if (
len < 0)
return ONIGERR_PARSER_BUG;
1796 if (IS_NOT_NULL(NCDR(node))) {
1797 r = add_opcode_rel_addr(reg, OP_PUSH,
len + SIZE_OP_JUMP);
1800 r = compile_tree(NCAR(node), reg);
1802 if (IS_NOT_NULL(NCDR(node))) {
1803 len = pos - (reg->used + SIZE_OP_JUMP);
1804 r = add_opcode_rel_addr(reg, OP_JUMP,
len);
1807 }
while (IS_NOT_NULL(node = NCDR(node)));
1812 if (NSTRING_IS_RAW(node))
1813 r = compile_string_raw_node(NSTR(node), reg);
1815 r = compile_string_node(node, reg);
1819 r = compile_cclass_node(NCCLASS(node), reg);
1826 switch (NCTYPE(node)->ctype) {
1827 case ONIGENC_CTYPE_WORD:
1828 if (NCTYPE(node)->ascii_range != 0) {
1829 if (NCTYPE(node)->not != 0) op = OP_NOT_ASCII_WORD;
1830 else op = OP_ASCII_WORD;
1833 if (NCTYPE(node)->not != 0) op = OP_NOT_WORD;
1838 return ONIGERR_TYPE_BUG;
1841 r = add_opcode(reg, op);
1846 if (IS_MULTILINE(reg->options))
1847 r = add_opcode(reg, OP_ANYCHAR_ML);
1849 r = add_opcode(reg, OP_ANYCHAR);
1856#ifdef USE_BACKREF_WITH_LEVEL
1857 if (IS_BACKREF_NEST_LEVEL(br)) {
1858 r = add_opcode(reg, OP_BACKREF_WITH_LEVEL);
1860 r = add_option(reg, (reg->options & ONIG_OPTION_IGNORECASE));
1862 r = add_length(reg, br->nest_level);
1865 goto add_bacref_mems;
1869 if (br->back_num == 1) {
1870 n = br->back_static[0];
1871 if (IS_IGNORECASE(reg->options)) {
1872 r = add_opcode(reg, OP_BACKREFN_IC);
1874 r = add_mem_num(reg, n);
1878 case 1: r = add_opcode(reg, OP_BACKREF1);
break;
1879 case 2: r = add_opcode(reg, OP_BACKREF2);
break;
1881 r = add_opcode(reg, OP_BACKREFN);
1883 r = add_mem_num(reg, n);
1892 if (IS_IGNORECASE(reg->options)) {
1893 r = add_opcode(reg, OP_BACKREF_MULTI_IC);
1896 r = add_opcode(reg, OP_BACKREF_MULTI);
1900#ifdef USE_BACKREF_WITH_LEVEL
1903 r = add_length(reg, br->back_num);
1906 for (i = br->back_num - 1; i >= 0; i--) {
1907 r = add_mem_num(reg, p[i]);
1914#ifdef USE_SUBEXP_CALL
1916 r = compile_call(NCALL(node), reg);
1921 r = compile_quantifier_node(NQTFR(node), reg);
1925 r = compile_enclose_node(NENCLOSE(node), reg);
1929 r = compile_anchor_node(NANCHOR(node), reg);
1934 fprintf(stderr,
"compile_tree: undefined node type %d\n", NTYPE(node));
1942#ifdef USE_NAMED_GROUP
1945noname_disable_map(Node** plink,
GroupNumRemap* map,
int* counter)
1948 Node* node = *plink;
1950 switch (NTYPE(node)) {
1954 r = noname_disable_map(&(NCAR(node)), map, counter);
1955 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
1960 Node** ptarget = &(NQTFR(node)->target);
1961 Node* old = *ptarget;
1962 r = noname_disable_map(ptarget, map, counter);
1963 if (*ptarget != old && NTYPE(*ptarget) == NT_QTFR) {
1964 onig_reduce_nested_quantifier(node, *ptarget);
1972 if (en->type == ENCLOSE_MEMORY) {
1973 if (IS_ENCLOSE_NAMED_GROUP(en)) {
1975 map[en->regnum].new_val = *counter;
1976 en->regnum = *counter;
1978 else if (en->regnum != 0) {
1979 *plink = en->target;
1980 en->target = NULL_NODE;
1981 onig_node_free(node);
1982 r = noname_disable_map(plink, map, counter);
1986 r = noname_disable_map(&(en->target), map, counter);
1991 if (NANCHOR(node)->target)
1992 r = noname_disable_map(&(NANCHOR(node)->target), map, counter);
2003renumber_node_backref(Node* node,
GroupNumRemap* map,
const int num_mem)
2005 int i, pos, n, old_num;
2009 if (! IS_BACKREF_NAME_REF(bn))
2010 return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
2012 old_num = bn->back_num;
2013 if (IS_NULL(bn->back_dynamic))
2014 backs = bn->back_static;
2016 backs = bn->back_dynamic;
2018 for (i = 0, pos = 0; i < old_num; i++) {
2019 if (backs[i] > num_mem)
return ONIGERR_INVALID_BACKREF;
2020 n = map[backs[i]].new_val;
2032renumber_by_map(Node* node,
GroupNumRemap* map,
const int num_mem)
2036 switch (NTYPE(node)) {
2040 r = renumber_by_map(NCAR(node), map, num_mem);
2041 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2044 r = renumber_by_map(NQTFR(node)->target, map, num_mem);
2049 if (en->type == ENCLOSE_CONDITION) {
2050 if (en->regnum > num_mem)
return ONIGERR_INVALID_BACKREF;
2051 en->regnum = map[en->regnum].new_val;
2053 r = renumber_by_map(en->target, map, num_mem);
2058 r = renumber_node_backref(node, map, num_mem);
2062 if (NANCHOR(node)->target)
2063 r = renumber_by_map(NANCHOR(node)->target, map, num_mem);
2074numbered_ref_check(Node* node)
2078 switch (NTYPE(node)) {
2082 r = numbered_ref_check(NCAR(node));
2083 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2086 r = numbered_ref_check(NQTFR(node)->target);
2089 r = numbered_ref_check(NENCLOSE(node)->target);
2093 if (! IS_BACKREF_NAME_REF(NBREF(node)))
2094 return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
2098 if (NANCHOR(node)->target)
2099 r = numbered_ref_check(NANCHOR(node)->target);
2110disable_noname_group_capture(Node** root, regex_t* reg,
ScanEnv* env)
2112 int r, i, pos, counter;
2117 CHECK_NULL_RETURN_MEMERR(map);
2118 for (i = 1; i <= env->num_mem; i++) {
2122 r = noname_disable_map(root, map, &counter);
2123 if (r != 0)
return r;
2125 r = renumber_by_map(*root, map, env->num_mem);
2126 if (r != 0)
return r;
2128 for (i = 1, pos = 1; i <= env->num_mem; i++) {
2129 if (map[i].new_val > 0) {
2130 SCANENV_MEM_NODES(env)[pos] = SCANENV_MEM_NODES(env)[i];
2135 loc = env->capture_history;
2136 BIT_STATUS_CLEAR(env->capture_history);
2137 for (i = 1; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
2138 if (BIT_STATUS_AT(loc, i)) {
2139 BIT_STATUS_ON_AT_SIMPLE(env->capture_history, map[i].new_val);
2143 env->num_mem = env->num_named;
2144 reg->num_mem = env->num_named;
2146 return onig_renumber_name_table(reg, map);
2150#ifdef USE_SUBEXP_CALL
2158 for (i = 0; i < uslist->num; i++) {
2159 en = NENCLOSE(uslist->us[i].target);
2160 if (! IS_ENCLOSE_ADDR_FIXED(en))
return ONIGERR_PARSER_BUG;
2161 addr = en->call_addr;
2162 offset = uslist->us[i].offset;
2164 BBUF_WRITE(reg, offset, &addr, SIZE_ABSADDR);
2170#ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
2172quantifiers_memory_node_info(Node* node)
2176 switch (NTYPE(node)) {
2182 v = quantifiers_memory_node_info(NCAR(node));
2184 }
while (v >= 0 && IS_NOT_NULL(node = NCDR(node)));
2188# ifdef USE_SUBEXP_CALL
2190 if (IS_CALL_RECURSION(NCALL(node))) {
2191 return NQ_TARGET_IS_EMPTY_REC;
2194 r = quantifiers_memory_node_info(NCALL(node)->target);
2201 if (qn->upper != 0) {
2202 r = quantifiers_memory_node_info(qn->target);
2211 case ENCLOSE_MEMORY:
2212 return NQ_TARGET_IS_EMPTY_MEM;
2215 case ENCLOSE_OPTION:
2216 case ENCLOSE_STOP_BACKTRACK:
2217 case ENCLOSE_CONDITION:
2218 case ENCLOSE_ABSENT:
2219 r = quantifiers_memory_node_info(en->target);
2242get_min_match_length(Node* node, OnigDistance *min,
ScanEnv* env)
2248 switch (NTYPE(node)) {
2253 Node** nodes = SCANENV_MEM_NODES(env);
2255 if (br->state & NST_RECURSION)
break;
2257 backs = BACKREFS_P(br);
2258 if (backs[0] > env->num_mem)
return ONIGERR_INVALID_BACKREF;
2259 r = get_min_match_length(nodes[backs[0]], min, env);
2261 for (i = 1; i < br->back_num; i++) {
2262 if (backs[i] > env->num_mem)
return ONIGERR_INVALID_BACKREF;
2263 r = get_min_match_length(nodes[backs[i]], &tmin, env);
2265 if (*min > tmin) *min = tmin;
2270#ifdef USE_SUBEXP_CALL
2272 if (IS_CALL_RECURSION(NCALL(node))) {
2274 if (IS_ENCLOSE_MIN_FIXED(en))
2278 r = get_min_match_length(NCALL(node)->target, min, env);
2284 r = get_min_match_length(NCAR(node), &tmin, env);
2285 if (r == 0) *min += tmin;
2286 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2295 r = get_min_match_length(x, &tmin, env);
2297 if (y == node) *min = tmin;
2298 else if (*min > tmin) *min = tmin;
2299 }
while (r == 0 && IS_NOT_NULL(y = NCDR(y)));
2306 *min = sn->end - sn->s;
2323 if (qn->lower > 0) {
2324 r = get_min_match_length(qn->target, min, env);
2326 *min = distance_multiply(*min, qn->lower);
2335 case ENCLOSE_MEMORY:
2336 if (IS_ENCLOSE_MIN_FIXED(en))
2339 if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
2342 SET_ENCLOSE_STATUS(node, NST_MARK1);
2343 r = get_min_match_length(en->target, min, env);
2344 CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
2347 SET_ENCLOSE_STATUS(node, NST_MIN_FIXED);
2353 case ENCLOSE_OPTION:
2354 case ENCLOSE_STOP_BACKTRACK:
2355 case ENCLOSE_CONDITION:
2356 r = get_min_match_length(en->target, min, env);
2359 case ENCLOSE_ABSENT:
2374get_max_match_length(Node* node, OnigDistance *max,
ScanEnv* env)
2380 switch (NTYPE(node)) {
2383 r = get_max_match_length(NCAR(node), &tmax, env);
2385 *max = distance_add(*max, tmax);
2386 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2391 r = get_max_match_length(NCAR(node), &tmax, env);
2392 if (r == 0 && *max < tmax) *max = tmax;
2393 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2399 *max = sn->end - sn->s;
2404 *max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
2409 *max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
2416 Node** nodes = SCANENV_MEM_NODES(env);
2418 if (br->state & NST_RECURSION) {
2419 *max = ONIG_INFINITE_DISTANCE;
2422 backs = BACKREFS_P(br);
2423 for (i = 0; i < br->back_num; i++) {
2424 if (backs[i] > env->num_mem)
return ONIGERR_INVALID_BACKREF;
2425 r = get_max_match_length(nodes[backs[i]], &tmax, env);
2427 if (*max < tmax) *max = tmax;
2432#ifdef USE_SUBEXP_CALL
2434 if (! IS_CALL_RECURSION(NCALL(node)))
2435 r = get_max_match_length(NCALL(node)->target, max, env);
2437 *max = ONIG_INFINITE_DISTANCE;
2445 if (qn->upper != 0) {
2446 r = get_max_match_length(qn->target, max, env);
2447 if (r == 0 && *max != 0) {
2448 if (! IS_REPEAT_INFINITE(qn->upper))
2449 *max = distance_multiply(*max, qn->upper);
2451 *max = ONIG_INFINITE_DISTANCE;
2461 case ENCLOSE_MEMORY:
2462 if (IS_ENCLOSE_MAX_FIXED(en))
2465 if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
2466 *max = ONIG_INFINITE_DISTANCE;
2468 SET_ENCLOSE_STATUS(node, NST_MARK1);
2469 r = get_max_match_length(en->target, max, env);
2470 CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
2473 SET_ENCLOSE_STATUS(node, NST_MAX_FIXED);
2479 case ENCLOSE_OPTION:
2480 case ENCLOSE_STOP_BACKTRACK:
2481 case ENCLOSE_CONDITION:
2482 r = get_max_match_length(en->target, max, env);
2485 case ENCLOSE_ABSENT:
2499#define GET_CHAR_LEN_VARLEN -1
2500#define GET_CHAR_LEN_TOP_ALT_VARLEN -2
2504get_char_length_tree1(Node* node, regex_t* reg,
int*
len,
int level)
2511 switch (NTYPE(node)) {
2514 r = get_char_length_tree1(NCAR(node), reg, &tlen, level);
2516 *
len = (int )distance_add(*
len, tlen);
2517 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2525 r = get_char_length_tree1(NCAR(node), reg, &tlen, level);
2526 while (r == 0 && IS_NOT_NULL(node = NCDR(node))) {
2527 r = get_char_length_tree1(NCAR(node), reg, &tlen2, level);
2536 r = GET_CHAR_LEN_TOP_ALT_VARLEN;
2538 r = GET_CHAR_LEN_VARLEN;
2550 while (s < sn->end) {
2551 s += enclen(reg->enc, s, sn->end);
2560 if (qn->lower == qn->upper) {
2561 r = get_char_length_tree1(qn->target, reg, &tlen, level);
2563 *
len = (int )distance_multiply(tlen, qn->lower);
2566 r = GET_CHAR_LEN_VARLEN;
2570#ifdef USE_SUBEXP_CALL
2572 if (! IS_CALL_RECURSION(NCALL(node)))
2573 r = get_char_length_tree1(NCALL(node)->target, reg,
len, level);
2575 r = GET_CHAR_LEN_VARLEN;
2592 case ENCLOSE_MEMORY:
2593#ifdef USE_SUBEXP_CALL
2594 if (IS_ENCLOSE_CLEN_FIXED(en))
2595 *
len = en->char_len;
2597 r = get_char_length_tree1(en->target, reg,
len, level);
2599 en->char_len = *
len;
2600 SET_ENCLOSE_STATUS(node, NST_CLEN_FIXED);
2605 case ENCLOSE_OPTION:
2606 case ENCLOSE_STOP_BACKTRACK:
2607 case ENCLOSE_CONDITION:
2608 r = get_char_length_tree1(en->target, reg,
len, level);
2610 case ENCLOSE_ABSENT:
2621 r = GET_CHAR_LEN_VARLEN;
2629get_char_length_tree(Node* node, regex_t* reg,
int*
len)
2631 return get_char_length_tree1(node, reg,
len, 0);
2636is_not_included(Node* x, Node* y, regex_t* reg)
2651 if (NCTYPE(y)->ctype == NCTYPE(x)->ctype &&
2652 NCTYPE(y)->not != NCTYPE(x)->not &&
2653 NCTYPE(y)->ascii_range == NCTYPE(x)->ascii_range)
2663 tmp = x; x = y; y = tmp;
2683 switch (NCTYPE(y)->ctype) {
2684 case ONIGENC_CTYPE_WORD:
2685 if (NCTYPE(y)->not == 0) {
2686 if (IS_NULL(xc->mbuf) && !IS_NCCLASS_NOT(xc)) {
2687 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2688 if (BITSET_AT(xc->bs, i)) {
2689 if (NCTYPE(y)->ascii_range) {
2690 if (IS_CODE_SB_WORD(reg->enc, i))
return 0;
2693 if (ONIGENC_IS_CODE_WORD(reg->enc, i))
return 0;
2702 if (IS_NOT_NULL(xc->mbuf))
return 0;
2703 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2705 if (NCTYPE(y)->ascii_range)
2706 is_word = IS_CODE_SB_WORD(reg->enc, i);
2708 is_word = ONIGENC_IS_CODE_WORD(reg->enc, i);
2710 if (!IS_NCCLASS_NOT(xc)) {
2711 if (BITSET_AT(xc->bs, i))
2715 if (! BITSET_AT(xc->bs, i))
2734 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2735 v = BITSET_AT(xc->bs, i);
2736 if ((v != 0 && !IS_NCCLASS_NOT(xc)) ||
2737 (v == 0 && IS_NCCLASS_NOT(xc))) {
2738 v = BITSET_AT(yc->bs, i);
2739 if ((v != 0 && !IS_NCCLASS_NOT(yc)) ||
2740 (v == 0 && IS_NCCLASS_NOT(yc)))
2744 if ((IS_NULL(xc->mbuf) && !IS_NCCLASS_NOT(xc)) ||
2745 (IS_NULL(yc->mbuf) && !IS_NCCLASS_NOT(yc)))
2764 if (NSTRING_LEN(x) == 0)
2769 switch (NCTYPE(y)->ctype) {
2770 case ONIGENC_CTYPE_WORD:
2771 if (NCTYPE(y)->ascii_range) {
2772 if (ONIGENC_IS_MBC_ASCII_WORD(reg->enc, xs->s, xs->end))
2773 return NCTYPE(y)->not;
2775 return !(NCTYPE(y)->not);
2778 if (ONIGENC_IS_MBC_WORD(reg->enc, xs->s, xs->end))
2779 return NCTYPE(y)->not;
2781 return !(NCTYPE(y)->not);
2793 code = ONIGENC_MBC_TO_CODE(reg->enc, xs->s,
2794 xs->s + ONIGENC_MBC_MAXLEN(reg->enc));
2795 return (onig_is_code_in_cc(reg->enc, code, cc) != 0 ? 0 : 1);
2803 len = NSTRING_LEN(x);
2804 if (
len > NSTRING_LEN(y))
len = NSTRING_LEN(y);
2805 if (NSTRING_IS_AMBIG(x) || NSTRING_IS_AMBIG(y)) {
2810 for (i = 0, p = ys->s, q = xs->s; (OnigDistance )i <
len; i++, p++, q++) {
2811 if (*p != *q)
return 1;
2831get_head_value_node(Node* node,
int exact, regex_t* reg)
2833 Node* n = NULL_NODE;
2835 switch (NTYPE(node)) {
2839#ifdef USE_SUBEXP_CALL
2852 n = get_head_value_node(NCAR(node), exact, reg);
2858 if (sn->end <= sn->s)
2862 NSTRING_IS_RAW(node) || !IS_IGNORECASE(reg->options)) {
2871 if (qn->lower > 0) {
2872#ifdef USE_OP_PUSH_OR_JUMP_EXACT
2873 if (IS_NOT_NULL(qn->head_exact))
2877 n = get_head_value_node(qn->target, exact, reg);
2886 case ENCLOSE_OPTION:
2888 OnigOptionType options = reg->options;
2890 reg->options = NENCLOSE(node)->option;
2891 n = get_head_value_node(NENCLOSE(node)->target, exact, reg);
2892 reg->options = options;
2896 case ENCLOSE_MEMORY:
2897 case ENCLOSE_STOP_BACKTRACK:
2898 case ENCLOSE_CONDITION:
2899 n = get_head_value_node(en->target, exact, reg);
2902 case ENCLOSE_ABSENT:
2909 if (NANCHOR(node)->type == ANCHOR_PREC_READ)
2910 n = get_head_value_node(NANCHOR(node)->target, exact, reg);
2921check_type_tree(Node* node,
int type_mask,
int enclose_mask,
int anchor_mask)
2926 if ((NTYPE2BIT(type) & type_mask) == 0)
2933 r = check_type_tree(NCAR(node), type_mask, enclose_mask,
2935 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2939 r = check_type_tree(NQTFR(node)->target, type_mask, enclose_mask,
2946 if ((en->type & enclose_mask) == 0)
2949 r = check_type_tree(en->target, type_mask, enclose_mask, anchor_mask);
2954 type = NANCHOR(node)->type;
2955 if ((type & anchor_mask) == 0)
2958 if (NANCHOR(node)->target)
2959 r = check_type_tree(NANCHOR(node)->target,
2960 type_mask, enclose_mask, anchor_mask);
2969#ifdef USE_SUBEXP_CALL
2971# define RECURSION_EXIST 1
2972# define RECURSION_INFINITE 2
2975subexp_inf_recursive_check(Node* node,
ScanEnv* env,
int head)
2990 ret = subexp_inf_recursive_check(NCAR(x), env, head);
2991 if (ret < 0 || ret == RECURSION_INFINITE)
return ret;
2994 ret = get_min_match_length(NCAR(x), &min, env);
2995 if (ret != 0)
return ret;
2996 if (min != 0) head = 0;
2998 }
while (IS_NOT_NULL(x = NCDR(x)));
3005 r = RECURSION_EXIST;
3007 ret = subexp_inf_recursive_check(NCAR(node), env, head);
3008 if (ret < 0 || ret == RECURSION_INFINITE)
return ret;
3010 }
while (IS_NOT_NULL(node = NCDR(node)));
3015 r = subexp_inf_recursive_check(NQTFR(node)->target, env, head);
3016 if (r == RECURSION_EXIST) {
3017 if (NQTFR(node)->lower == 0) r = 0;
3025 case ANCHOR_PREC_READ:
3026 case ANCHOR_PREC_READ_NOT:
3027 case ANCHOR_LOOK_BEHIND:
3028 case ANCHOR_LOOK_BEHIND_NOT:
3029 r = subexp_inf_recursive_check(an->target, env, head);
3036 r = subexp_inf_recursive_check(NCALL(node)->target, env, head);
3040 if (IS_ENCLOSE_MARK2(NENCLOSE(node)))
3042 else if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
3043 return (head == 0 ? RECURSION_EXIST : RECURSION_INFINITE);
3045 SET_ENCLOSE_STATUS(node, NST_MARK2);
3046 r = subexp_inf_recursive_check(NENCLOSE(node)->target, env, head);
3047 CLEAR_ENCLOSE_STATUS(node, NST_MARK2);
3059subexp_inf_recursive_check_trav(Node* node,
ScanEnv* env)
3069 r = subexp_inf_recursive_check_trav(NCAR(node), env);
3070 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3074 r = subexp_inf_recursive_check_trav(NQTFR(node)->target, env);
3081 case ANCHOR_PREC_READ:
3082 case ANCHOR_PREC_READ_NOT:
3083 case ANCHOR_LOOK_BEHIND:
3084 case ANCHOR_LOOK_BEHIND_NOT:
3085 r = subexp_inf_recursive_check_trav(an->target, env);
3095 if (IS_ENCLOSE_RECURSION(en)) {
3096 SET_ENCLOSE_STATUS(node, NST_MARK1);
3097 r = subexp_inf_recursive_check(en->target, env, 1);
3098 if (r > 0)
return ONIGERR_NEVER_ENDING_RECURSION;
3099 CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
3101 r = subexp_inf_recursive_check_trav(en->target, env);
3114subexp_recursive_check(Node* node)
3118 switch (NTYPE(node)) {
3122 r |= subexp_recursive_check(NCAR(node));
3123 }
while (IS_NOT_NULL(node = NCDR(node)));
3127 r = subexp_recursive_check(NQTFR(node)->target);
3134 case ANCHOR_PREC_READ:
3135 case ANCHOR_PREC_READ_NOT:
3136 case ANCHOR_LOOK_BEHIND:
3137 case ANCHOR_LOOK_BEHIND_NOT:
3138 r = subexp_recursive_check(an->target);
3145 r = subexp_recursive_check(NCALL(node)->target);
3146 if (r != 0) SET_CALL_RECURSION(node);
3150 if (IS_ENCLOSE_MARK2(NENCLOSE(node)))
3152 else if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
3155 SET_ENCLOSE_STATUS(node, NST_MARK2);
3156 r = subexp_recursive_check(NENCLOSE(node)->target);
3157 CLEAR_ENCLOSE_STATUS(node, NST_MARK2);
3170subexp_recursive_check_trav(Node* node,
ScanEnv* env)
3172# define FOUND_CALLED_NODE 1
3184 ret = subexp_recursive_check_trav(NCAR(node), env);
3185 if (ret == FOUND_CALLED_NODE) r = FOUND_CALLED_NODE;
3186 else if (ret < 0)
return ret;
3187 }
while (IS_NOT_NULL(node = NCDR(node)));
3192 r = subexp_recursive_check_trav(NQTFR(node)->target, env);
3193 if (NQTFR(node)->upper == 0) {
3194 if (r == FOUND_CALLED_NODE)
3195 NQTFR(node)->is_referred = 1;
3203 case ANCHOR_PREC_READ:
3204 case ANCHOR_PREC_READ_NOT:
3205 case ANCHOR_LOOK_BEHIND:
3206 case ANCHOR_LOOK_BEHIND_NOT:
3207 r = subexp_recursive_check_trav(an->target, env);
3217 if (! IS_ENCLOSE_RECURSION(en)) {
3218 if (IS_ENCLOSE_CALLED(en)) {
3219 SET_ENCLOSE_STATUS(node, NST_MARK1);
3220 r = subexp_recursive_check(en->target);
3221 if (r != 0) SET_ENCLOSE_STATUS(node, NST_RECURSION);
3222 CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
3225 r = subexp_recursive_check_trav(en->target, env);
3226 if (IS_ENCLOSE_CALLED(en))
3227 r |= FOUND_CALLED_NODE;
3239setup_subexp_call(Node* node,
ScanEnv* env)
3248 r = setup_subexp_call(NCAR(node), env);
3249 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3254 r = setup_subexp_call(NCAR(node), env);
3255 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3259 r = setup_subexp_call(NQTFR(node)->target, env);
3262 r = setup_subexp_call(NENCLOSE(node)->target, env);
3268 Node** nodes = SCANENV_MEM_NODES(env);
3270 if (cn->group_num != 0) {
3271 int gnum = cn->group_num;
3273# ifdef USE_NAMED_GROUP
3274 if (env->num_named > 0 &&
3275 IS_SYNTAX_BV(env->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
3276 !ONIG_IS_OPTION_ON(env->option, ONIG_OPTION_CAPTURE_GROUP)) {
3277 return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
3280 if (gnum > env->num_mem) {
3281 onig_scan_env_set_error_string(env,
3282 ONIGERR_UNDEFINED_GROUP_REFERENCE, cn->name, cn->name_end);
3283 return ONIGERR_UNDEFINED_GROUP_REFERENCE;
3286# ifdef USE_NAMED_GROUP
3289 cn->target = nodes[cn->group_num];
3290 if (IS_NULL(cn->target)) {
3291 onig_scan_env_set_error_string(env,
3292 ONIGERR_UNDEFINED_NAME_REFERENCE, cn->name, cn->name_end);
3293 return ONIGERR_UNDEFINED_NAME_REFERENCE;
3295 SET_ENCLOSE_STATUS(cn->target, NST_CALLED);
3296 BIT_STATUS_ON_AT(env->bt_mem_start, cn->group_num);
3297 cn->unset_addr_list = env->unset_addr_list;
3299# ifdef USE_NAMED_GROUP
3300# ifdef USE_PERL_SUBEXP_CALL
3301 else if (cn->name == cn->name_end) {
3308 int n = onig_name_to_group_numbers(env->reg, cn->name, cn->name_end,
3311 onig_scan_env_set_error_string(env,
3312 ONIGERR_UNDEFINED_NAME_REFERENCE, cn->name, cn->name_end);
3313 return ONIGERR_UNDEFINED_NAME_REFERENCE;
3316 ! IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME_CALL)) {
3317 onig_scan_env_set_error_string(env,
3318 ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL, cn->name, cn->name_end);
3319 return ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL;
3322 cn->group_num = refs[0];
3335 case ANCHOR_PREC_READ:
3336 case ANCHOR_PREC_READ_NOT:
3337 case ANCHOR_LOOK_BEHIND:
3338 case ANCHOR_LOOK_BEHIND_NOT:
3339 r = setup_subexp_call(an->target, env);
3353#define IN_ALT (1<<0)
3354#define IN_NOT (1<<1)
3355#define IN_REPEAT (1<<2)
3356#define IN_VAR_REPEAT (1<<3)
3357#define IN_CALL (1<<4)
3358#define IN_RECCALL (1<<5)
3359#define IN_LOOK_BEHIND (1<<6)
3366divide_look_behind_alternatives(Node* node)
3368 Node *head, *np, *insert_node;
3370 int anc_type = an->type;
3374 swap_node(node, head);
3376 NANCHOR(head)->target = np;
3379 while ((np = NCDR(np)) != NULL_NODE) {
3380 insert_node = onig_node_new_anchor(anc_type);
3381 CHECK_NULL_RETURN_MEMERR(insert_node);
3382 NANCHOR(insert_node)->target = NCAR(np);
3383 NCAR(np) = insert_node;
3386 if (anc_type == ANCHOR_LOOK_BEHIND_NOT) {
3389 SET_NTYPE(np, NT_LIST);
3390 }
while ((np = NCDR(np)) != NULL_NODE);
3396setup_look_behind(Node* node, regex_t* reg,
ScanEnv* env)
3401 r = get_char_length_tree(an->target, reg, &
len);
3404 else if (r == GET_CHAR_LEN_VARLEN)
3405 r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
3406 else if (r == GET_CHAR_LEN_TOP_ALT_VARLEN) {
3407 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND))
3408 r = divide_look_behind_alternatives(node);
3410 r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
3417next_setup(Node* node, Node* next_node, regex_t* reg)
3423 if (type == NT_QTFR) {
3425 if (qn->greedy && IS_REPEAT_INFINITE(qn->upper)) {
3426#ifdef USE_QTFR_PEEK_NEXT
3427 Node* n = get_head_value_node(next_node, 1, reg);
3429 if (IS_NOT_NULL(n) && NSTR(n)->s[0] !=
'\0') {
3430 qn->next_head_exact = n;
3434 if (qn->lower <= 1) {
3435 int ttype = NTYPE(qn->target);
3436 if (IS_NODE_TYPE_SIMPLE(ttype)) {
3438 x = get_head_value_node(qn->target, 0, reg);
3439 if (IS_NOT_NULL(x)) {
3440 y = get_head_value_node(next_node, 0, reg);
3441 if (IS_NOT_NULL(y) && is_not_included(x, y, reg)) {
3442 Node* en = onig_node_new_enclose(ENCLOSE_STOP_BACKTRACK);
3443 CHECK_NULL_RETURN_MEMERR(en);
3444 SET_ENCLOSE_STATUS(en, NST_STOP_BT_SIMPLE_REPEAT);
3445 swap_node(node, en);
3446 NENCLOSE(node)->target = en;
3453 else if (type == NT_ENCLOSE) {
3455 if (en->type == ENCLOSE_MEMORY && !IS_ENCLOSE_CALLED(en)) {
3465update_string_node_case_fold(regex_t* reg, Node *node)
3467 UChar *p, *end, buf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
3468 UChar *sbuf, *ebuf, *sp;
3470 OnigDistance sbuf_size;
3474 sbuf_size = (end - sn->s) * 2;
3475 sbuf = (UChar* )
xmalloc(sbuf_size);
3476 CHECK_NULL_RETURN_MEMERR(sbuf);
3477 ebuf = sbuf + sbuf_size;
3482 len = ONIGENC_MBC_CASE_FOLD(reg->enc, reg->case_fold_flag, &p, end, buf);
3483 for (i = 0; i <
len; i++) {
3485 UChar* p = (UChar* )
xrealloc(sbuf, sbuf_size * 2);
3488 return ONIGERR_MEMORY;
3491 sp = sbuf + sbuf_size;
3493 ebuf = sbuf + sbuf_size;
3500 r = onig_node_str_set(node, sbuf, sp);
3507expand_case_fold_make_rem_string(Node** rnode, UChar *s, UChar *end,
3513 node = onig_node_new_str(s, end);
3514 if (IS_NULL(node))
return ONIGERR_MEMORY;
3516 r = update_string_node_case_fold(reg, node);
3518 onig_node_free(node);
3522 NSTRING_SET_AMBIG(node);
3523 NSTRING_SET_DONT_GET_OPT_INFO(node);
3534 for (i = 0; i < item_num; i++) {
3535 if (items[i].byte_len != slen) {
3538 if (items[i].code_len != 1) {
3547 UChar *p,
int slen, UChar *end,
3548 regex_t* reg, Node **rnode)
3550 int r, i, j,
len, varlen;
3551 Node *anode, *var_anode, *snode, *xnode, *an;
3552 UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
3554 *rnode = var_anode = NULL_NODE;
3557 for (i = 0; i < item_num; i++) {
3558 if (items[i].byte_len != slen) {
3565 *rnode = var_anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3566 if (IS_NULL(var_anode))
return ONIGERR_MEMORY;
3568 xnode = onig_node_new_list(NULL, NULL);
3569 if (IS_NULL(xnode))
goto mem_err;
3570 NCAR(var_anode) = xnode;
3572 anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3573 if (IS_NULL(anode))
goto mem_err;
3574 NCAR(xnode) = anode;
3577 *rnode = anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3578 if (IS_NULL(anode))
return ONIGERR_MEMORY;
3581 snode = onig_node_new_str(p, p + slen);
3582 if (IS_NULL(snode))
goto mem_err;
3584 NCAR(anode) = snode;
3586 for (i = 0; i < item_num; i++) {
3587 snode = onig_node_new_str(NULL, NULL);
3588 if (IS_NULL(snode))
goto mem_err;
3590 for (j = 0; j < items[i].code_len; j++) {
3591 len = ONIGENC_CODE_TO_MBC(reg->enc, items[i].code[j], buf);
3597 r = onig_node_str_cat(snode, buf, buf +
len);
3598 if (r != 0)
goto mem_err2;
3601 an = onig_node_new_alt(NULL_NODE, NULL_NODE);
3606 if (items[i].byte_len != slen) {
3608 UChar *q = p + items[i].byte_len;
3611 r = expand_case_fold_make_rem_string(&rem, q, end, reg);
3617 xnode = onig_node_list_add(NULL_NODE, snode);
3618 if (IS_NULL(xnode)) {
3620 onig_node_free(rem);
3623 if (IS_NULL(onig_node_list_add(xnode, rem))) {
3625 onig_node_free(xnode);
3626 onig_node_free(rem);
3636 NCDR(var_anode) = an;
3649 onig_node_free(snode);
3652 onig_node_free(*rnode);
3654 return ONIGERR_MEMORY;
3657#define THRESHOLD_CASE_FOLD_ALT_FOR_EXPANSION 8
3660expand_case_fold_string(Node* node, regex_t* reg,
int state)
3662 int r, n,
len, alt_num;
3664 int is_in_look_behind;
3665 UChar *start, *end, *p;
3666 Node *top_root, *root, *snode, *prev_node;
3670 if (NSTRING_IS_AMBIG(node))
return 0;
3676 if (start >= end)
return 0;
3678 is_in_look_behind = (state & IN_LOOK_BEHIND) != 0;
3681 top_root = root = prev_node = snode = NULL_NODE;
3685 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(reg->enc, reg->case_fold_flag,
3692 len = enclen(reg->enc, p, end);
3694 varlen = is_case_fold_variable_len(n, items,
len);
3695 if (n == 0 || varlen == 0 || is_in_look_behind) {
3696 if (IS_NULL(snode)) {
3697 if (IS_NULL(root) && IS_NOT_NULL(prev_node)) {
3698 onig_node_free(top_root);
3699 top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3700 if (IS_NULL(root)) {
3701 onig_node_free(prev_node);
3706 prev_node = snode = onig_node_new_str(NULL, NULL);
3707 if (IS_NULL(snode))
goto mem_err;
3708 if (IS_NOT_NULL(root)) {
3709 if (IS_NULL(onig_node_list_add(root, snode))) {
3710 onig_node_free(snode);
3716 r = onig_node_str_cat(snode, p, p +
len);
3717 if (r != 0)
goto err;
3721 if (alt_num > THRESHOLD_CASE_FOLD_ALT_FOR_EXPANSION)
break;
3723 if (IS_NOT_NULL(snode)) {
3724 r = update_string_node_case_fold(reg, snode);
3726 NSTRING_SET_AMBIG(snode);
3729 if (IS_NULL(root) && IS_NOT_NULL(prev_node)) {
3730 onig_node_free(top_root);
3731 top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3732 if (IS_NULL(root)) {
3733 onig_node_free(prev_node);
3738 r = expand_case_fold_string_alt(n, items, p,
len, end, reg, &prev_node);
3739 if (r < 0)
goto mem_err;
3741 if (IS_NULL(root)) {
3742 top_root = prev_node;
3745 if (IS_NULL(onig_node_list_add(root, prev_node))) {
3746 onig_node_free(prev_node);
3751 root = NCAR(prev_node);
3754 if (IS_NOT_NULL(root)) {
3755 if (IS_NULL(onig_node_list_add(root, prev_node))) {
3756 onig_node_free(prev_node);
3767 if (IS_NOT_NULL(snode)) {
3768 r = update_string_node_case_fold(reg, snode);
3770 NSTRING_SET_AMBIG(snode);
3777 r = expand_case_fold_make_rem_string(&srem, p, end, reg);
3778 if (r != 0)
goto mem_err;
3780 if (IS_NOT_NULL(prev_node) && IS_NULL(root)) {
3781 onig_node_free(top_root);
3782 top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3783 if (IS_NULL(root)) {
3784 onig_node_free(srem);
3785 onig_node_free(prev_node);
3790 if (IS_NULL(root)) {
3794 if (IS_NULL(onig_node_list_add(root, srem))) {
3795 onig_node_free(srem);
3802 top_root = (IS_NOT_NULL(top_root) ? top_root : prev_node);
3803 swap_node(node, top_root);
3804 onig_node_free(top_root);
3811 onig_node_free(top_root);
3816#ifdef USE_COMBINATION_EXPLOSION_CHECK
3818# define CEC_THRES_NUM_BIG_REPEAT 512
3819# define CEC_INFINITE_NUM 0x7fffffff
3821# define CEC_IN_INFINITE_REPEAT (1<<0)
3822# define CEC_IN_FINITE_REPEAT (1<<1)
3823# define CEC_CONT_BIG_REPEAT (1<<2)
3826setup_comb_exp_check(Node* node,
int state,
ScanEnv* env)
3836 r = setup_comb_exp_check(NCAR(node), r, env);
3837 }
while (r >= 0 && IS_NOT_NULL(node = NCDR(node)));
3845 ret = setup_comb_exp_check(NCAR(node), state, env);
3847 }
while (ret >= 0 && IS_NOT_NULL(node = NCDR(node)));
3853 int child_state = state;
3856 Node* target = qn->target;
3859 if (! IS_REPEAT_INFINITE(qn->upper)) {
3860 if (qn->upper > 1) {
3862 child_state |= CEC_IN_FINITE_REPEAT;
3865 if (env->backrefed_mem == 0) {
3866 if (NTYPE(qn->target) == NT_ENCLOSE) {
3868 if (en->type == ENCLOSE_MEMORY) {
3869 if (NTYPE(en->target) == NT_QTFR) {
3871 if (IS_REPEAT_INFINITE(q->upper)
3872 && q->greedy == qn->greedy) {
3873 qn->upper = (qn->lower == 0 ? 1 : qn->lower);
3875 child_state = state;
3884 if (state & CEC_IN_FINITE_REPEAT) {
3885 qn->comb_exp_check_num = -1;
3888 if (IS_REPEAT_INFINITE(qn->upper)) {
3889 var_num = CEC_INFINITE_NUM;
3890 child_state |= CEC_IN_INFINITE_REPEAT;
3893 var_num = qn->upper - qn->lower;
3896 if (var_num >= CEC_THRES_NUM_BIG_REPEAT)
3897 add_state |= CEC_CONT_BIG_REPEAT;
3899 if (((state & CEC_IN_INFINITE_REPEAT) != 0 && var_num != 0) ||
3900 ((state & CEC_CONT_BIG_REPEAT) != 0 &&
3901 var_num >= CEC_THRES_NUM_BIG_REPEAT)) {
3902 if (qn->comb_exp_check_num == 0) {
3903 env->num_comb_exp_check++;
3904 qn->comb_exp_check_num = env->num_comb_exp_check;
3905 if (env->curr_max_regnum > env->comb_exp_max_regnum)
3906 env->comb_exp_max_regnum = env->curr_max_regnum;
3911 r = setup_comb_exp_check(target, child_state, env);
3921 case ENCLOSE_MEMORY:
3923 if (env->curr_max_regnum < en->regnum)
3924 env->curr_max_regnum = en->regnum;
3926 r = setup_comb_exp_check(en->target, state, env);
3931 r = setup_comb_exp_check(en->target, state, env);
3937# ifdef USE_SUBEXP_CALL
3939 if (IS_CALL_RECURSION(NCALL(node)))
3940 env->has_recursion = 1;
3942 r = setup_comb_exp_check(NCALL(node)->target, state, env);
3963setup_tree(Node* node, regex_t* reg,
int state,
ScanEnv* env)
3973 Node* prev = NULL_NODE;
3975 r = setup_tree(NCAR(node), reg, state, env);
3976 if (IS_NOT_NULL(prev) && r == 0) {
3977 r = next_setup(prev, NCAR(node), reg);
3980 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3986 r = setup_tree(NCAR(node), reg, (state | IN_ALT), env);
3987 }
while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3994 if (IS_IGNORECASE(reg->options) && !NSTRING_IS_RAW(node)) {
3995 r = expand_case_fold_string(node, reg, state);
4003#ifdef USE_SUBEXP_CALL
4012 Node** nodes = SCANENV_MEM_NODES(env);
4015 for (i = 0; i < br->back_num; i++) {
4016 if (p[i] > env->num_mem)
return ONIGERR_INVALID_BACKREF;
4017 BIT_STATUS_ON_AT(env->backrefed_mem, p[i]);
4018 BIT_STATUS_ON_AT(env->bt_mem_start, p[i]);
4019#ifdef USE_BACKREF_WITH_LEVEL
4020 if (IS_BACKREF_NEST_LEVEL(br)) {
4021 BIT_STATUS_ON_AT(env->bt_mem_end, p[i]);
4024 SET_ENCLOSE_STATUS(nodes[p[i]], NST_MEM_BACKREFED);
4033 Node* target = qn->target;
4035 if ((state & IN_REPEAT) != 0) {
4036 qn->state |= NST_IN_REPEAT;
4039 if (IS_REPEAT_INFINITE(qn->upper) || qn->upper >= 1) {
4040 r = get_min_match_length(target, &d, env);
4043 qn->target_empty_info = NQ_TARGET_IS_EMPTY;
4044#ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
4045 r = quantifiers_memory_node_info(target);
4048 qn->target_empty_info = r;
4052 r = get_max_match_length(target, &d, env);
4053 if (r == 0 && d == 0) {
4056 if (qn->lower > 1) qn->lower = 1;
4057 if (NTYPE(target) == NT_STR) {
4058 qn->upper = qn->lower = 0;
4066 if (qn->lower != qn->upper)
4067 state |= IN_VAR_REPEAT;
4068 r = setup_tree(target, reg, state, env);
4072#define EXPAND_STRING_MAX_LENGTH 100
4073 if (NTYPE(target) == NT_STR) {
4074 if (qn->lower > 1) {
4075 int i, n = qn->lower;
4076 OnigDistance
len = NSTRING_LEN(target);
4080 np = onig_node_new_str(sn->s, sn->end);
4081 if (IS_NULL(np))
return ONIGERR_MEMORY;
4082 NSTR(np)->flag = sn->flag;
4084 for (i = 1; i < n && (i+1) *
len <= EXPAND_STRING_MAX_LENGTH; i++) {
4085 r = onig_node_str_cat(np, sn->s, sn->end);
4091 if (i < qn->upper || IS_REPEAT_INFINITE(qn->upper)) {
4095 if (! IS_REPEAT_INFINITE(qn->upper))
4098 np1 = onig_node_new_list(np, NULL);
4101 return ONIGERR_MEMORY;
4103 swap_node(np1, node);
4104 np2 = onig_node_list_add(node, np1);
4106 onig_node_free(np1);
4107 return ONIGERR_MEMORY;
4111 swap_node(np, node);
4118#ifdef USE_OP_PUSH_OR_JUMP_EXACT
4119 if (qn->greedy && (qn->target_empty_info != 0)) {
4120 if (NTYPE(target) == NT_QTFR) {
4122 if (IS_NOT_NULL(tqn->head_exact)) {
4123 qn->head_exact = tqn->head_exact;
4124 tqn->head_exact = NULL;
4128 qn->head_exact = get_head_value_node(qn->target, 1, reg);
4140 case ENCLOSE_OPTION:
4142 OnigOptionType options = reg->options;
4143 reg->options = NENCLOSE(node)->option;
4144 r = setup_tree(NENCLOSE(node)->target, reg, state, env);
4145 reg->options = options;
4149 case ENCLOSE_MEMORY:
4150 if ((state & (IN_ALT | IN_NOT | IN_VAR_REPEAT | IN_CALL)) != 0) {
4151 BIT_STATUS_ON_AT(env->bt_mem_start, en->regnum);
4154 if (IS_ENCLOSE_CALLED(en))
4156 if (IS_ENCLOSE_RECURSION(en))
4157 state |= IN_RECCALL;
4158 else if ((state & IN_RECCALL) != 0)
4159 SET_CALL_RECURSION(node);
4160 r = setup_tree(en->target, reg, state, env);
4163 case ENCLOSE_STOP_BACKTRACK:
4165 Node* target = en->target;
4166 r = setup_tree(target, reg, state, env);
4167 if (NTYPE(target) == NT_QTFR) {
4169 if (IS_REPEAT_INFINITE(tqn->upper) && tqn->lower <= 1 &&
4171 int qtype = NTYPE(tqn->target);
4172 if (IS_NODE_TYPE_SIMPLE(qtype))
4173 SET_ENCLOSE_STATUS(node, NST_STOP_BT_SIMPLE_REPEAT);
4179 case ENCLOSE_CONDITION:
4180#ifdef USE_NAMED_GROUP
4181 if (! IS_ENCLOSE_NAME_REF(NENCLOSE(node)) &&
4182 env->num_named > 0 &&
4183 IS_SYNTAX_BV(env->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
4184 !ONIG_IS_OPTION_ON(env->option, ONIG_OPTION_CAPTURE_GROUP)) {
4185 return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
4188 if (NENCLOSE(node)->regnum > env->num_mem)
4189 return ONIGERR_INVALID_BACKREF;
4190 r = setup_tree(NENCLOSE(node)->target, reg, state, env);
4193 case ENCLOSE_ABSENT:
4194 r = setup_tree(NENCLOSE(node)->target, reg, state, env);
4205 case ANCHOR_PREC_READ:
4206 r = setup_tree(an->target, reg, state, env);
4208 case ANCHOR_PREC_READ_NOT:
4209 r = setup_tree(an->target, reg, (state | IN_NOT), env);
4213#define ALLOWED_TYPE_IN_LB \
4214 ( BIT_NT_LIST | BIT_NT_ALT | BIT_NT_STR | BIT_NT_CCLASS | BIT_NT_CTYPE | \
4215 BIT_NT_CANY | BIT_NT_ANCHOR | BIT_NT_ENCLOSE | BIT_NT_QTFR | BIT_NT_CALL )
4217#define ALLOWED_ENCLOSE_IN_LB ( ENCLOSE_MEMORY | ENCLOSE_OPTION )
4218#define ALLOWED_ENCLOSE_IN_LB_NOT ENCLOSE_OPTION
4220#define ALLOWED_ANCHOR_IN_LB \
4221( ANCHOR_LOOK_BEHIND | ANCHOR_LOOK_BEHIND_NOT | ANCHOR_BEGIN_LINE | \
4222 ANCHOR_END_LINE | ANCHOR_BEGIN_BUF | ANCHOR_BEGIN_POSITION | ANCHOR_KEEP | \
4223 ANCHOR_WORD_BOUND | ANCHOR_NOT_WORD_BOUND | \
4224 ANCHOR_WORD_BEGIN | ANCHOR_WORD_END )
4225#define ALLOWED_ANCHOR_IN_LB_NOT \
4226( ANCHOR_LOOK_BEHIND | ANCHOR_LOOK_BEHIND_NOT | ANCHOR_BEGIN_LINE | \
4227 ANCHOR_END_LINE | ANCHOR_BEGIN_BUF | ANCHOR_BEGIN_POSITION | ANCHOR_KEEP | \
4228 ANCHOR_WORD_BOUND | ANCHOR_NOT_WORD_BOUND | \
4229 ANCHOR_WORD_BEGIN | ANCHOR_WORD_END )
4231 case ANCHOR_LOOK_BEHIND:
4233 r = check_type_tree(an->target, ALLOWED_TYPE_IN_LB,
4234 ALLOWED_ENCLOSE_IN_LB, ALLOWED_ANCHOR_IN_LB);
4235 if (r < 0)
return r;
4236 if (r > 0)
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
4237 if (NTYPE(node) != NT_ANCHOR)
goto restart;
4238 r = setup_tree(an->target, reg, (state | IN_LOOK_BEHIND), env);
4239 if (r != 0)
return r;
4240 r = setup_look_behind(node, reg, env);
4244 case ANCHOR_LOOK_BEHIND_NOT:
4246 r = check_type_tree(an->target, ALLOWED_TYPE_IN_LB,
4247 ALLOWED_ENCLOSE_IN_LB_NOT, ALLOWED_ANCHOR_IN_LB_NOT);
4248 if (r < 0)
return r;
4249 if (r > 0)
return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
4250 if (NTYPE(node) != NT_ANCHOR)
goto restart;
4251 r = setup_tree(an->target, reg, (state | IN_NOT | IN_LOOK_BEHIND),
4253 if (r != 0)
return r;
4254 r = setup_look_behind(node, reg, env);
4270set_bm_skip(UChar* s, UChar* end, regex_t* reg,
4271 UChar skip[],
int** int_skip,
int ignore_case)
4273 OnigDistance i,
len;
4274 int clen, flen, n, j, k;
4275 UChar *p, buf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
4277 OnigEncoding enc = reg->enc;
4280 if (
len < ONIG_CHAR_TABLE_SIZE) {
4282 for (i = 0; i <
len; i += clen) {
4284 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, reg->case_fold_flag,
4286 clen = enclen(enc, p, end);
4288 clen = (int )(end - p);
4290 for (j = 0; j < n; j++) {
4291 if ((items[j].code_len != 1) || (items[j].byte_len != clen)) {
4296 flen = ONIGENC_CODE_TO_MBC(enc, items[j].code[0], buf);
4309 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
4310 skip[i] = (UChar )(
len + 1);
4312 for (i = 0; i <
len; i += clen) {
4315 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, reg->case_fold_flag,
4317 clen = enclen(enc, p, end);
4319 clen = (int )(end - p);
4321 for (j = 0; j < clen; j++) {
4322 skip[s[i + j]] = (UChar )(
len - i - j);
4323 for (k = 0; k < n; k++) {
4324 ONIGENC_CODE_TO_MBC(enc, items[k].code[0], buf);
4325 skip[buf[j]] = (UChar )(
len - i - j);
4331# if OPT_EXACT_MAXLEN < ONIG_CHAR_TABLE_SIZE
4333 return ONIGERR_TYPE_BUG;
4335 if (IS_NULL(*int_skip)) {
4336 *int_skip = (
int* )
xmalloc(
sizeof(
int) * ONIG_CHAR_TABLE_SIZE);
4337 if (IS_NULL(*int_skip))
return ONIGERR_MEMORY;
4339 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) (*int_skip)[i] = (int )(
len + 1);
4342 for (i = 0; i <
len; i += clen) {
4345 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, reg->case_fold_flag,
4347 clen = enclen(enc, p, end);
4349 clen = (int )(end - p);
4351 for (j = 0; j < n; j++) {
4352 if ((items[j].code_len != 1) || (items[j].byte_len != clen))
4354 flen = ONIGENC_CODE_TO_MBC(enc, items[j].code[0], buf[j]);
4358 for (j = 0; j < clen; j++) {
4359 (*int_skip)[s[i + j]] = (int )(
len - i - j);
4360 for (k = 0; k < n; k++) {
4361 (*int_skip)[buf[k][j]] = (int )(
len - i - j);
4378 OnigOptionType options;
4379 OnigCaseFoldType case_fold_flag;
4396 UChar s[OPT_EXACT_MAXLEN];
4404 UChar map[ONIG_CHAR_TABLE_SIZE];
4420map_position_value(OnigEncoding enc,
int i)
4422 static const short int ByteValTable[] = {
4423 5, 1, 1, 1, 1, 1, 1, 1, 1, 10, 10, 1, 1, 10, 1, 1,
4424 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
4425 12, 4, 7, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,
4426 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5,
4427 5, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
4428 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 5, 5, 5,
4429 5, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
4430 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 1
4433 if (i < numberof(ByteValTable)) {
4434 if (i == 0 && ONIGENC_MBC_MINLEN(enc) > 1)
4437 return (
int )ByteValTable[i];
4447 static const short int dist_vals[] = {
4448 1000, 500, 333, 250, 200, 167, 143, 125, 111, 100,
4449 91, 83, 77, 71, 67, 63, 59, 56, 53, 50,
4450 48, 45, 43, 42, 40, 38, 37, 36, 34, 33,
4451 32, 31, 30, 29, 29, 28, 27, 26, 26, 25,
4452 24, 24, 23, 23, 22, 22, 21, 21, 20, 20,
4453 20, 19, 19, 19, 18, 18, 18, 17, 17, 17,
4454 16, 16, 16, 16, 15, 15, 15, 15, 14, 14,
4455 14, 14, 14, 14, 13, 13, 13, 13, 13, 13,
4456 12, 12, 12, 12, 12, 12, 11, 11, 11, 11,
4457 11, 11, 11, 11, 11, 10, 10, 10, 10, 10
4462 if (mm->max == ONIG_INFINITE_DISTANCE)
return 0;
4464 d = mm->max - mm->min;
4465 if (d < numberof(dist_vals))
4467 return (
int )dist_vals[d];
4475 if (v2 <= 0)
return -1;
4476 if (v1 <= 0)
return 1;
4478 v1 *= distance_value(d1);
4479 v2 *= distance_value(d2);
4481 if (v2 > v1)
return 1;
4482 if (v2 < v1)
return -1;
4484 if (d2->min < d1->min)
return 1;
4485 if (d2->min > d1->min)
return -1;
4492 return (a->min == b->min && a->max == b->max) ? 1 : 0;
4497set_mml(
MinMaxLen* mml, OnigDistance min, OnigDistance max)
4506 mml->min = mml->max = 0;
4512 to->min = from->min;
4513 to->max = from->max;
4519 to->min = distance_add(to->min, from->min);
4520 to->max = distance_add(to->max, from->max);
4527 to->min = distance_add(to->min,
len);
4528 to->max = distance_add(to->max,
len);
4535 if (to->min > from->min) to->min = from->min;
4536 if (to->max < from->max) to->max = from->max;
4548 anc->left_anchor = 0;
4549 anc->right_anchor = 0;
4550 anc->head_asserts = 0;
4561 OnigDistance left_len, OnigDistance right_len)
4563 clear_opt_anc_info(to);
4565 to->left_anchor = left->left_anchor;
4566 to->head_asserts = left->head_asserts;
4567 if (left_len == 0) {
4568 int right_left = right->left_anchor;
4570 if ((left->head_asserts & ~ANCHOR_BEGIN_LINE) != 0)
4571 right_left &= ~ANCHOR_ANYCHAR_STAR_MASK;
4572 else if ((left->head_asserts & ANCHOR_BEGIN_LINE) != 0)
4573 right_left &= ~ANCHOR_ANYCHAR_STAR_ML;
4575 to->left_anchor |= right_left;
4576 to->head_asserts |= right->head_asserts;
4579 to->right_anchor = right->right_anchor;
4580 if (right_len == 0) {
4581 to->right_anchor |= left->right_anchor;
4584 to->right_anchor |= (left->right_anchor & ANCHOR_PREC_READ_NOT);
4589is_left_anchor(
int anc)
4591 if (anc == ANCHOR_END_BUF || anc == ANCHOR_SEMI_END_BUF ||
4592 anc == ANCHOR_END_LINE || anc == ANCHOR_PREC_READ ||
4593 anc == ANCHOR_PREC_READ_NOT)
4602 if ((to->left_anchor & anc) != 0)
return 1;
4604 return ((to->right_anchor & anc) != 0 ? 1 : 0);
4610 if (is_left_anchor(anc))
4611 to->left_anchor |= anc;
4613 to->right_anchor |= anc;
4619 if (is_left_anchor(anc))
4620 to->left_anchor &= ~anc;
4622 to->right_anchor &= ~anc;
4628 to->left_anchor &= add->left_anchor;
4629 to->right_anchor &= add->right_anchor;
4630 to->head_asserts |= add->head_asserts;
4636 return (ex->len >= OPT_EXACT_MAXLEN ? 1 : 0);
4642 clear_mml(&ex->mmd);
4643 clear_opt_anc_info(&ex->anc);
4645 ex->ignore_case = -1;
4663 if (to->ignore_case < 0)
4664 to->ignore_case = add->ignore_case;
4665 else if (to->ignore_case != add->ignore_case)
4670 for (i = to->len; p < end; ) {
4671 len = enclen(enc, p, end);
4672 if (i +
len > OPT_EXACT_MAXLEN)
break;
4673 for (j = 0; j <
len && p < end; j++)
4678 to->reach_end = (p == end ? add->reach_end : 0);
4680 concat_opt_anc_info(&tanc, &to->anc, &add->anc, 1, 1);
4681 if (! to->reach_end) tanc.right_anchor = 0;
4682 copy_opt_anc_info(&to->anc, &tanc);
4686concat_opt_exact_info_str(
OptExactInfo* to, UChar* s, UChar* end,
4687 int raw ARG_UNUSED, OnigEncoding enc)
4692 for (i = to->len, p = s; p < end && i < OPT_EXACT_MAXLEN; ) {
4693 len = enclen(enc, p, end);
4694 if (i +
len > OPT_EXACT_MAXLEN)
break;
4695 for (j = 0; j <
len && p < end; j++)
4707 if (add->len == 0 || to->len == 0) {
4708 clear_opt_exact_info(to);
4712 if (! is_equal_mml(&to->mmd, &add->mmd)) {
4713 clear_opt_exact_info(to);
4717 for (i = 0; i < to->len && i < add->len; ) {
4718 if (to->s[i] != add->s[i])
break;
4719 len = enclen(env->enc, to->s + i, to->s + to->len);
4721 for (j = 1; j <
len; j++) {
4722 if (to->s[i+j] != add->s[i+j])
break;
4728 if (! add->reach_end || i < add->
len || i < to->
len) {
4732 if (to->ignore_case < 0)
4733 to->ignore_case = add->ignore_case;
4734 else if (add->ignore_case >= 0)
4735 to->ignore_case |= add->ignore_case;
4737 alt_merge_opt_anc_info(&to->anc, &add->anc);
4738 if (! to->reach_end) to->anc.right_anchor = 0;
4753 copy_opt_exact_info(now, alt);
4756 else if (v1 <= 2 && v2 <= 2) {
4758 v2 = map_position_value(enc, now->s[0]);
4759 v1 = map_position_value(enc, alt->s[0]);
4761 if (now->len > 1) v1 += 5;
4762 if (alt->len > 1) v2 += 5;
4765 if (now->ignore_case <= 0) v1 *= 2;
4766 if (alt->ignore_case <= 0) v2 *= 2;
4768 if (comp_distance_value(&now->mmd, &alt->mmd, v1, v2) > 0)
4769 copy_opt_exact_info(now, alt);
4778 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4779 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4780 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4781 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4782 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4783 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4784 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4785 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4786 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4787 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4788 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4789 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4790 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4791 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4792 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4793 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
4797 xmemcpy(map, &clean_info,
sizeof(
OptMapInfo));
4807add_char_opt_map_info(
OptMapInfo* map, UChar c, OnigEncoding enc)
4809 if (map->map[c] == 0) {
4811 map->value += map_position_value(enc, c);
4816add_char_amb_opt_map_info(
OptMapInfo* map, UChar* p, UChar* end,
4817 OnigEncoding enc, OnigCaseFoldType case_fold_flag)
4820 UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
4823 add_char_opt_map_info(map, p[0], enc);
4825 case_fold_flag = DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag);
4826 n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, case_fold_flag, p, end, items);
4827 if (n < 0)
return n;
4829 for (i = 0; i < n; i++) {
4830 ONIGENC_CODE_TO_MBC(enc, items[i].code[0], buf);
4831 add_char_opt_map_info(map, buf[0], enc);
4840 const int z = 1<<15;
4844 if (alt->value == 0) return ;
4845 if (now->value == 0) {
4846 copy_opt_map_info(now, alt);
4850 v1 = z / now->value;
4851 v2 = z / alt->value;
4852 if (comp_distance_value(&now->mmd, &alt->mmd, v1, v2) > 0)
4853 copy_opt_map_info(now, alt);
4859#define COMP_EM_BASE 20
4862 if (m->value <= 0)
return -1;
4864 ve = COMP_EM_BASE * e->len * (e->ignore_case > 0 ? 1 : 2);
4865 vm = COMP_EM_BASE * 5 * 2 / m->value;
4866 return comp_distance_value(&e->mmd, &m->mmd, ve, vm);
4875 if (to->value == 0) return ;
4876 if (add->value == 0 || to->mmd.max < add->mmd.min) {
4877 clear_opt_map_info(to);
4881 alt_merge_mml(&to->mmd, &add->mmd);
4884 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) {
4889 val += map_position_value(enc, i);
4893 alt_merge_opt_anc_info(&to->anc, &add->anc);
4899 copy_mml(&(opt->exb.mmd), mmd);
4900 copy_mml(&(opt->expr.mmd), mmd);
4901 copy_mml(&(opt->map.mmd), mmd);
4907 clear_mml(&opt->len);
4908 clear_opt_anc_info(&opt->anc);
4909 clear_opt_exact_info(&opt->exb);
4910 clear_opt_exact_info(&opt->exm);
4911 clear_opt_exact_info(&opt->expr);
4912 clear_opt_map_info(&opt->map);
4924 int exb_reach, exm_reach;
4927 concat_opt_anc_info(&tanc, &to->anc, &add->anc, to->len.max, add->len.max);
4928 copy_opt_anc_info(&to->anc, &tanc);
4930 if (add->exb.len > 0 && to->len.max == 0) {
4931 concat_opt_anc_info(&tanc, &to->anc, &add->exb.anc,
4932 to->len.max, add->len.max);
4933 copy_opt_anc_info(&add->exb.anc, &tanc);
4936 if (add->map.value > 0 && to->len.max == 0) {
4937 if (add->map.mmd.max == 0)
4938 add->map.anc.left_anchor |= to->anc.left_anchor;
4941 exb_reach = to->exb.reach_end;
4942 exm_reach = to->exm.reach_end;
4944 if (add->len.max != 0)
4945 to->exb.reach_end = to->exm.reach_end = 0;
4947 if (add->exb.len > 0) {
4949 concat_opt_exact_info(&to->exb, &add->exb, enc);
4950 clear_opt_exact_info(&add->exb);
4952 else if (exm_reach) {
4953 concat_opt_exact_info(&to->exm, &add->exb, enc);
4954 clear_opt_exact_info(&add->exb);
4957 select_opt_exact_info(enc, &to->exm, &add->exb);
4958 select_opt_exact_info(enc, &to->exm, &add->exm);
4960 if (to->expr.len > 0) {
4961 if (add->len.max > 0) {
4962 if (to->expr.len > (
int )add->len.max)
4963 to->expr.len = (int )add->len.max;
4965 if (to->expr.mmd.max == 0)
4966 select_opt_exact_info(enc, &to->exb, &to->expr);
4968 select_opt_exact_info(enc, &to->exm, &to->expr);
4971 else if (add->expr.len > 0) {
4972 copy_opt_exact_info(&to->expr, &add->expr);
4975 select_opt_map_info(&to->map, &add->map);
4977 add_mml(&to->len, &add->len);
4983 alt_merge_opt_anc_info (&to->anc, &add->anc);
4984 alt_merge_opt_exact_info(&to->exb, &add->exb, env);
4985 alt_merge_opt_exact_info(&to->exm, &add->exm, env);
4986 alt_merge_opt_exact_info(&to->expr, &add->expr, env);
4987 alt_merge_opt_map_info(env->enc, &to->map, &add->map);
4989 alt_merge_mml(&to->len, &add->len);
4993#define MAX_NODE_OPT_INFO_REF_COUNT 5
5001 clear_node_opt_info(opt);
5002 set_bound_node_opt_info(opt, &env->mmd);
5012 copy_opt_env(&nenv, env);
5014 r = optimize_node_left(NCAR(nd), &nopt, &nenv);
5016 add_mml(&nenv.mmd, &nopt.len);
5017 concat_left_node_opt_info(env->enc, opt, &nopt);
5019 }
while (r == 0 && IS_NOT_NULL(nd = NCDR(nd)));
5029 r = optimize_node_left(NCAR(nd), &nopt, env);
5031 if (nd == node) copy_node_opt_info(opt, &nopt);
5032 else alt_merge_node_opt_info(opt, &nopt, env);
5034 }
while ((r == 0) && IS_NOT_NULL(nd = NCDR(nd)));
5041 OnigDistance slen = sn->end - sn->s;
5042 int is_raw = NSTRING_IS_RAW(node);
5044 if (! NSTRING_IS_AMBIG(node)) {
5045 concat_opt_exact_info_str(&opt->exb, sn->s, sn->end,
5047 opt->exb.ignore_case = 0;
5049 add_char_opt_map_info(&opt->map, *(sn->s), env->enc);
5051 set_mml(&opt->len, slen, slen);
5056 if (NSTRING_IS_DONT_GET_OPT_INFO(node)) {
5057 int n = onigenc_strlen(env->enc, sn->s, sn->end);
5058 max = (OnigDistance )ONIGENC_MBC_MAXLEN_DIST(env->enc) * (OnigDistance)n;
5061 concat_opt_exact_info_str(&opt->exb, sn->s, sn->end,
5063 opt->exb.ignore_case = 1;
5066 r = add_char_amb_opt_map_info(&opt->map, sn->s, sn->end,
5067 env->enc, env->case_fold_flag);
5074 set_mml(&opt->len, slen, max);
5077 if ((OnigDistance )opt->exb.len == slen)
5078 opt->exb.reach_end = 1;
5089 if (IS_NOT_NULL(cc->mbuf) || IS_NCCLASS_NOT(cc)) {
5090 OnigDistance min = ONIGENC_MBC_MINLEN(env->enc);
5091 OnigDistance max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
5093 set_mml(&opt->len, min, max);
5096 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
5097 z = BITSET_AT(cc->bs, i);
5098 if ((z && !IS_NCCLASS_NOT(cc)) || (!z && IS_NCCLASS_NOT(cc))) {
5099 add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
5102 set_mml(&opt->len, 1, 1);
5112 max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
5117 maxcode = NCTYPE(node)->ascii_range ? 0x80 : SINGLE_BYTE_SIZE;
5118 switch (NCTYPE(node)->ctype) {
5119 case ONIGENC_CTYPE_WORD:
5120 if (NCTYPE(node)->not != 0) {
5121 for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
5122 if (! ONIGENC_IS_CODE_WORD(env->enc, i) || i >= maxcode) {
5123 add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
5128 for (i = 0; i < maxcode; i++) {
5129 if (ONIGENC_IS_CODE_WORD(env->enc, i)) {
5130 add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
5138 min = ONIGENC_MBC_MINLEN(env->enc);
5140 set_mml(&opt->len, min, max);
5146 OnigDistance min = ONIGENC_MBC_MINLEN(env->enc);
5147 OnigDistance max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
5148 set_mml(&opt->len, min, max);
5153 if ((NANCHOR(node)->type &
5154 ~(ANCHOR_BEGIN_BUF | ANCHOR_BEGIN_POSITION | ANCHOR_KEEP)) != 0)
5155 opt->anc.head_asserts |= NANCHOR(node)->type;
5157 switch (NANCHOR(node)->type) {
5158 case ANCHOR_BEGIN_BUF:
5159 case ANCHOR_BEGIN_POSITION:
5160 case ANCHOR_BEGIN_LINE:
5161 case ANCHOR_END_BUF:
5162 case ANCHOR_SEMI_END_BUF:
5163 case ANCHOR_END_LINE:
5164 case ANCHOR_LOOK_BEHIND:
5165 case ANCHOR_PREC_READ_NOT:
5166 add_opt_anc_info(&opt->anc, NANCHOR(node)->type);
5169 case ANCHOR_PREC_READ:
5173 r = optimize_node_left(NANCHOR(node)->target, &nopt, env);
5175 if (nopt.exb.len > 0)
5176 copy_opt_exact_info(&opt->expr, &nopt.exb);
5177 else if (nopt.exm.len > 0)
5178 copy_opt_exact_info(&opt->expr, &nopt.exm);
5180 opt->expr.reach_end = 0;
5182 if (nopt.map.value > 0)
5183 copy_opt_map_info(&opt->map, &nopt.map);
5188 case ANCHOR_LOOK_BEHIND_NOT:
5197 OnigDistance min, max, tmin, tmax;
5198 Node** nodes = SCANENV_MEM_NODES(env->scan_env);
5201 if (br->state & NST_RECURSION) {
5202 set_mml(&opt->len, 0, ONIG_INFINITE_DISTANCE);
5205 backs = BACKREFS_P(br);
5206 r = get_min_match_length(nodes[backs[0]], &min, env->scan_env);
5208 r = get_max_match_length(nodes[backs[0]], &max, env->scan_env);
5210 for (i = 1; i < br->back_num; i++) {
5211 r = get_min_match_length(nodes[backs[i]], &tmin, env->scan_env);
5213 r = get_max_match_length(nodes[backs[i]], &tmax, env->scan_env);
5215 if (min > tmin) min = tmin;
5216 if (max < tmax) max = tmax;
5218 if (r == 0) set_mml(&opt->len, min, max);
5222#ifdef USE_SUBEXP_CALL
5224 if (IS_CALL_RECURSION(NCALL(node)))
5225 set_mml(&opt->len, 0, ONIG_INFINITE_DISTANCE);
5227 OnigOptionType save = env->options;
5228 env->options = NENCLOSE(NCALL(node)->target)->option;
5229 r = optimize_node_left(NCALL(node)->target, opt, env);
5230 env->options = save;
5238 OnigDistance min, max;
5242 r = optimize_node_left(qn->target, &nopt, env);
5245 if (qn->lower == 0 && IS_REPEAT_INFINITE(qn->upper)) {
5246 if (env->mmd.max == 0 &&
5247 NTYPE(qn->target) == NT_CANY && qn->greedy) {
5248 if (IS_MULTILINE(env->options))
5250 add_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_ML);
5252 add_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR);
5256 if (qn->lower > 0) {
5257 copy_node_opt_info(opt, &nopt);
5258 if (nopt.exb.len > 0) {
5259 if (nopt.exb.reach_end) {
5260 for (i = 2; i <= qn->lower &&
5261 ! is_full_opt_exact_info(&opt->exb); i++) {
5262 concat_opt_exact_info(&opt->exb, &nopt.exb, env->enc);
5264 if (i < qn->lower) {
5265 opt->exb.reach_end = 0;
5270 if (qn->lower != qn->upper) {
5271 opt->exb.reach_end = 0;
5272 opt->exm.reach_end = 0;
5275 opt->exm.reach_end = 0;
5279 min = distance_multiply(nopt.len.min, qn->lower);
5280 if (IS_REPEAT_INFINITE(qn->upper))
5281 max = (nopt.len.max > 0 ? ONIG_INFINITE_DISTANCE : 0);
5283 max = distance_multiply(nopt.len.max, qn->upper);
5285 set_mml(&opt->len, min, max);
5294 case ENCLOSE_OPTION:
5296 OnigOptionType save = env->options;
5298 env->options = en->option;
5299 r = optimize_node_left(en->target, opt, env);
5300 env->options = save;
5304 case ENCLOSE_MEMORY:
5305#ifdef USE_SUBEXP_CALL
5307 if (en->opt_count > MAX_NODE_OPT_INFO_REF_COUNT) {
5308 OnigDistance min, max;
5311 max = ONIG_INFINITE_DISTANCE;
5312 if (IS_ENCLOSE_MIN_FIXED(en)) min = en->min_len;
5313 if (IS_ENCLOSE_MAX_FIXED(en)) max = en->max_len;
5314 set_mml(&opt->len, min, max);
5319 r = optimize_node_left(en->target, opt, env);
5321 if (is_set_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_MASK)) {
5322 if (BIT_STATUS_AT(env->scan_env->backrefed_mem, en->regnum))
5323 remove_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_MASK);
5328 case ENCLOSE_STOP_BACKTRACK:
5329 case ENCLOSE_CONDITION:
5330 r = optimize_node_left(en->target, opt, env);
5333 case ENCLOSE_ABSENT:
5334 set_mml(&opt->len, 0, ONIG_INFINITE_DISTANCE);
5342 fprintf(stderr,
"optimize_node_left: undefined node type %d\n",
5345 r = ONIGERR_TYPE_BUG;
5357 if (e->len == 0)
return 0;
5359 reg->exact = (UChar* )
xmalloc(e->len);
5360 CHECK_NULL_RETURN_MEMERR(reg->exact);
5361 xmemcpy(reg->exact, e->s, e->len);
5362 reg->exact_end = reg->exact + e->len;
5365 ONIGENC_IS_ALLOWED_REVERSE_MATCH(reg->enc, reg->exact, reg->exact_end);
5367 if (e->ignore_case > 0) {
5368 if (e->len >= 3 || (e->len >= 2 && allow_reverse)) {
5369 int orig_len = e->len;
5370 e->len = set_bm_skip(reg->exact, reg->exact_end, reg,
5371 reg->map, &(reg->int_map), 1);
5373 reg->exact_end = reg->exact + e->len;
5374 reg->optimize = (allow_reverse != 0
5375 ? ONIG_OPTIMIZE_EXACT_BM_IC : ONIG_OPTIMIZE_EXACT_BM_NOT_REV_IC);
5385 reg->optimize = ONIG_OPTIMIZE_EXACT_IC;
5389 reg->optimize = ONIG_OPTIMIZE_EXACT_IC;
5393 if (e->len >= 3 || (e->len >= 2 && allow_reverse)) {
5394 set_bm_skip(reg->exact, reg->exact_end, reg,
5395 reg->map, &(reg->int_map), 0);
5396 reg->optimize = (allow_reverse != 0
5397 ? ONIG_OPTIMIZE_EXACT_BM : ONIG_OPTIMIZE_EXACT_BM_NOT_REV);
5400 reg->optimize = ONIG_OPTIMIZE_EXACT;
5404 reg->dmin = e->mmd.min;
5405 reg->dmax = e->mmd.max;
5407 if (reg->dmin != ONIG_INFINITE_DISTANCE) {
5408 reg->threshold_len = (int )(reg->dmin + (reg->exact_end - reg->exact));
5415set_optimize_map_info(regex_t* reg,
OptMapInfo* m)
5419 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
5420 reg->map[i] = m->map[i];
5422 reg->optimize = ONIG_OPTIMIZE_MAP;
5423 reg->dmin = m->mmd.min;
5424 reg->dmax = m->mmd.max;
5426 if (reg->dmin != ONIG_INFINITE_DISTANCE) {
5427 reg->threshold_len = (int )(reg->dmin + 1);
5434 reg->sub_anchor |= anc->left_anchor & ANCHOR_BEGIN_LINE;
5435 reg->sub_anchor |= anc->right_anchor & ANCHOR_END_LINE;
5438#if defined(ONIG_DEBUG_COMPILE) || defined(ONIG_DEBUG_MATCH)
5439static void print_optimize_info(FILE* f, regex_t* reg);
5443set_optimize_info_from_tree(Node* node, regex_t* reg,
ScanEnv* scan_env)
5451 env.options = reg->options;
5452 env.case_fold_flag = reg->case_fold_flag;
5453 env.scan_env = scan_env;
5454 clear_mml(&env.mmd);
5456 r = optimize_node_left(node, &opt, &env);
5459 reg->anchor = opt.anc.left_anchor & (ANCHOR_BEGIN_BUF |
5460 ANCHOR_BEGIN_POSITION | ANCHOR_ANYCHAR_STAR | ANCHOR_ANYCHAR_STAR_ML |
5461 ANCHOR_LOOK_BEHIND);
5463 if ((opt.anc.left_anchor & (ANCHOR_LOOK_BEHIND | ANCHOR_PREC_READ_NOT)) != 0)
5464 reg->anchor &= ~ANCHOR_ANYCHAR_STAR_ML;
5466 reg->anchor |= opt.anc.right_anchor & (ANCHOR_END_BUF | ANCHOR_SEMI_END_BUF |
5467 ANCHOR_PREC_READ_NOT);
5469 if (reg->anchor & (ANCHOR_END_BUF | ANCHOR_SEMI_END_BUF)) {
5470 reg->anchor_dmin = opt.len.min;
5471 reg->anchor_dmax = opt.len.max;
5474 if (opt.exb.len > 0 || opt.exm.len > 0) {
5475 select_opt_exact_info(reg->enc, &opt.exb, &opt.exm);
5476 if (opt.map.value > 0 &&
5477 comp_opt_exact_or_map_info(&opt.exb, &opt.map) > 0) {
5481 r = set_optimize_exact_info(reg, &opt.exb);
5482 set_sub_anchor(reg, &opt.exb.anc);
5485 else if (opt.map.value > 0) {
5487 set_optimize_map_info(reg, &opt.map);
5488 set_sub_anchor(reg, &opt.map.anc);
5491 reg->sub_anchor |= opt.anc.left_anchor & ANCHOR_BEGIN_LINE;
5492 if (opt.len.max == 0)
5493 reg->sub_anchor |= opt.anc.right_anchor & ANCHOR_END_LINE;
5496#if defined(ONIG_DEBUG_COMPILE) || defined(ONIG_DEBUG_MATCH)
5497 print_optimize_info(stderr, reg);
5503clear_optimize_info(regex_t* reg)
5505 reg->optimize = ONIG_OPTIMIZE_NONE;
5507 reg->anchor_dmin = 0;
5508 reg->anchor_dmax = 0;
5509 reg->sub_anchor = 0;
5510 reg->exact_end = (UChar* )NULL;
5511 reg->threshold_len = 0;
5513 reg->exact = (UChar* )NULL;
5518static void print_enc_string(FILE* fp, OnigEncoding enc,
5519 const UChar *s,
const UChar *end)
5521 fprintf(fp,
"\nPATTERN: /");
5523 if (ONIGENC_MBC_MINLEN(enc) > 1) {
5529 code = ONIGENC_MBC_TO_CODE(enc, p, end);
5531 fprintf(fp,
" 0x%04x ", (
int )code);
5534 fputc((
int )code, fp);
5537 p += enclen(enc, p, end);
5542 fputc((
int )*s, fp);
5547 fprintf(fp,
"/ (%s)\n", enc->name);
5551#if defined(ONIG_DEBUG_COMPILE) || defined(ONIG_DEBUG_MATCH)
5553print_distance_range(FILE* f, OnigDistance a, OnigDistance b)
5555 if (a == ONIG_INFINITE_DISTANCE)
5558 fprintf(f,
"(%"PRIuPTR
")", a);
5562 if (b == ONIG_INFINITE_DISTANCE)
5565 fprintf(f,
"(%"PRIuPTR
")", b);
5569print_anchor(FILE* f,
int anchor)
5575 if (anchor & ANCHOR_BEGIN_BUF) {
5576 fprintf(f,
"begin-buf");
5579 if (anchor & ANCHOR_BEGIN_LINE) {
5580 if (q) fprintf(f,
", ");
5582 fprintf(f,
"begin-line");
5584 if (anchor & ANCHOR_BEGIN_POSITION) {
5585 if (q) fprintf(f,
", ");
5587 fprintf(f,
"begin-pos");
5589 if (anchor & ANCHOR_END_BUF) {
5590 if (q) fprintf(f,
", ");
5592 fprintf(f,
"end-buf");
5594 if (anchor & ANCHOR_SEMI_END_BUF) {
5595 if (q) fprintf(f,
", ");
5597 fprintf(f,
"semi-end-buf");
5599 if (anchor & ANCHOR_END_LINE) {
5600 if (q) fprintf(f,
", ");
5602 fprintf(f,
"end-line");
5604 if (anchor & ANCHOR_ANYCHAR_STAR) {
5605 if (q) fprintf(f,
", ");
5607 fprintf(f,
"anychar-star");
5609 if (anchor & ANCHOR_ANYCHAR_STAR_ML) {
5610 if (q) fprintf(f,
", ");
5611 fprintf(f,
"anychar-star-ml");
5618print_optimize_info(FILE* f, regex_t* reg)
5620 static const char* on[] = {
"NONE",
"EXACT",
"EXACT_BM",
"EXACT_BM_NOT_REV",
5622 "EXACT_BM_IC",
"EXACT_BM_NOT_REV_IC" };
5624 fprintf(f,
"optimize: %s\n", on[reg->optimize]);
5625 fprintf(f,
" anchor: "); print_anchor(f, reg->anchor);
5626 if ((reg->anchor & ANCHOR_END_BUF_MASK) != 0)
5627 print_distance_range(f, reg->anchor_dmin, reg->anchor_dmax);
5630 if (reg->optimize) {
5631 fprintf(f,
" sub anchor: "); print_anchor(f, reg->sub_anchor);
5638 fprintf(f,
"exact: [");
5639 for (p = reg->exact; p < reg->exact_end; p++) {
5642 fprintf(f,
"]: length: %"PRIdPTR
"\n", (reg->exact_end - reg->exact));
5644 else if (reg->optimize & ONIG_OPTIMIZE_MAP) {
5647 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
5648 if (reg->map[i]) n++;
5650 fprintf(f,
"map: n=%d\n", n);
5654 for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) {
5655 if (reg->map[i] != 0) {
5656 if (c > 0) fputs(
", ", f);
5658 if (ONIGENC_MBC_MAXLEN(reg->enc) == 1 &&
5659 ONIGENC_IS_CODE_PRINT(reg->enc, (OnigCodePoint )i))
5662 fprintf(f,
"%d", i);
5673onig_free_body(regex_t* reg)
5675 if (IS_NOT_NULL(reg)) {
5678 xfree(reg->int_map);
5679 xfree(reg->int_map_backward);
5680 xfree(reg->repeat_range);
5681 onig_free(reg->chain);
5683#ifdef USE_NAMED_GROUP
5684 onig_names_free(reg);
5690onig_free(regex_t* reg)
5692 if (IS_NOT_NULL(reg)) {
5693 onig_free_body(reg);
5699dup_copy(
const void *
ptr,
size_t size)
5702 if (IS_NOT_NULL(newptr)) {
5703 memcpy(newptr,
ptr, size);
5709onig_reg_copy(regex_t** nreg, regex_t* oreg)
5711 if (IS_NOT_NULL(oreg)) {
5712 regex_t *reg = *nreg = (regex_t* )
xmalloc(
sizeof(regex_t));
5713 if (IS_NULL(reg))
return ONIGERR_MEMORY;
5717# define COPY_FAILED(mem, size) IS_NULL(reg->mem = dup_copy(reg->mem, size))
5719 if (IS_NOT_NULL(reg->exact)) {
5720 size_t exact_size = reg->exact_end - reg->exact;
5721 if (COPY_FAILED(exact, exact_size))
5723 (reg)->exact_end = (reg)->exact + exact_size;
5726 if (IS_NOT_NULL(reg->int_map)) {
5727 if (COPY_FAILED(int_map,
sizeof(
int) * ONIG_CHAR_TABLE_SIZE))
5730 if (IS_NOT_NULL(reg->int_map_backward)) {
5731 if (COPY_FAILED(int_map_backward,
sizeof(
int) * ONIG_CHAR_TABLE_SIZE))
5732 goto err_int_map_backward;
5734 if (IS_NOT_NULL(reg->p)) {
5735 if (COPY_FAILED(p, reg->alloc))
5738 if (IS_NOT_NULL(reg->repeat_range)) {
5739 if (COPY_FAILED(repeat_range, reg->repeat_range_alloc *
sizeof(
OnigRepeatRange)))
5740 goto err_repeat_range;
5742 if (IS_NOT_NULL(reg->name_table)) {
5743 if (onig_names_copy(reg, oreg))
5744 goto err_name_table;
5746 if (IS_NOT_NULL(reg->chain)) {
5747 if (onig_reg_copy(®->chain, reg->chain))
5754 onig_names_free(reg);
5756 xfree(reg->repeat_range);
5760 xfree(reg->int_map_backward);
5761 err_int_map_backward:
5762 xfree(reg->int_map);
5767 return ONIGERR_MEMORY;
5774onig_memsize(
const regex_t *reg)
5776 size_t size =
sizeof(regex_t);
5777 if (IS_NULL(reg))
return 0;
5778 if (IS_NOT_NULL(reg->p)) size += reg->alloc;
5779 if (IS_NOT_NULL(reg->exact)) size += reg->exact_end - reg->exact;
5780 if (IS_NOT_NULL(reg->int_map)) size +=
sizeof(int) * ONIG_CHAR_TABLE_SIZE;
5781 if (IS_NOT_NULL(reg->int_map_backward)) size +=
sizeof(int) * ONIG_CHAR_TABLE_SIZE;
5782 if (IS_NOT_NULL(reg->repeat_range)) size += reg->repeat_range_alloc *
sizeof(
OnigRepeatRange);
5783 if (IS_NOT_NULL(reg->chain)) size += onig_memsize(reg->chain);
5789onig_region_memsize(
const OnigRegion *regs)
5791 size_t size =
sizeof(*regs);
5792 if (IS_NULL(regs))
return 0;
5793 size += regs->allocated * (
sizeof(*regs->beg) +
sizeof(*regs->end));
5798#define REGEX_TRANSFER(to,from) do {\
5799 onig_free_body(to);\
5800 xmemcpy(to, from, sizeof(regex_t));\
5806onig_transfer(regex_t* to, regex_t* from)
5808 REGEX_TRANSFER(to, from);
5812#ifdef ONIG_DEBUG_COMPILE
5813static void print_compiled_byte_code_list(FILE* f, regex_t* reg);
5815#ifdef ONIG_DEBUG_PARSE_TREE
5816static void print_tree(FILE* f, Node* node);
5821onig_compile(regex_t* reg,
const UChar* pattern,
const UChar* pattern_end,
5824 return onig_compile_ruby(reg, pattern, pattern_end, einfo, NULL, 0);
5830onig_compile_ruby(regex_t* reg,
const UChar* pattern,
const UChar* pattern_end,
5831 OnigErrorInfo* einfo,
const char *sourcefile,
int sourceline)
5834onig_compile(regex_t* reg,
const UChar* pattern,
const UChar* pattern_end,
5838#define COMPILE_INIT_SIZE 20
5841 OnigDistance init_size;
5844#ifdef USE_SUBEXP_CALL
5848 if (IS_NOT_NULL(einfo)) {
5849 einfo->enc = reg->enc;
5850 einfo->par = (UChar* )NULL;
5851 einfo->par_end = (UChar* )NULL;
5855 scan_env.sourcefile = sourcefile;
5856 scan_env.sourceline = sourceline;
5860 print_enc_string(stderr, reg->enc, pattern, pattern_end);
5863 if (reg->alloc == 0) {
5864 init_size = (pattern_end - pattern) * 2;
5865 if (init_size <= 0) init_size = COMPILE_INIT_SIZE;
5866 r = BBUF_INIT(reg, init_size);
5867 if (r != 0)
goto end;
5873 reg->num_repeat = 0;
5874 reg->num_null_check = 0;
5875 reg->repeat_range_alloc = 0;
5877#ifdef USE_COMBINATION_EXPLOSION_CHECK
5878 reg->num_comb_exp_check = 0;
5881 r = onig_parse_make_tree(&root, pattern, pattern_end, reg, &scan_env);
5882 if (r != 0)
goto err;
5884#ifdef ONIG_DEBUG_PARSE_TREE
5886 fprintf(stderr,
"ORIGINAL PARSE TREE:\n");
5887 print_tree(stderr, root);
5891#ifdef USE_NAMED_GROUP
5893 if (scan_env.num_named > 0 &&
5894 IS_SYNTAX_BV(scan_env.syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
5895 !ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_CAPTURE_GROUP)) {
5896 if (scan_env.num_named != scan_env.num_mem)
5897 r = disable_noname_group_capture(&root, reg, &scan_env);
5899 r = numbered_ref_check(root);
5901 if (r != 0)
goto err;
5905#ifdef USE_SUBEXP_CALL
5906 if (scan_env.num_call > 0) {
5907 r = unset_addr_list_init(&uslist, scan_env.num_call);
5908 if (r != 0)
goto err;
5909 scan_env.unset_addr_list = &uslist;
5910 r = setup_subexp_call(root, &scan_env);
5911 if (r != 0)
goto err_unset;
5912 r = subexp_recursive_check_trav(root, &scan_env);
5913 if (r < 0)
goto err_unset;
5914 r = subexp_inf_recursive_check_trav(root, &scan_env);
5915 if (r != 0)
goto err_unset;
5917 reg->num_call = scan_env.num_call;
5923 r = setup_tree(root, reg, 0, &scan_env);
5924 if (r != 0)
goto err_unset;
5926#ifdef ONIG_DEBUG_PARSE_TREE
5927 print_tree(stderr, root);
5930 reg->capture_history = scan_env.capture_history;
5931 reg->bt_mem_start = scan_env.bt_mem_start;
5932 reg->bt_mem_start |= reg->capture_history;
5933 if (IS_FIND_CONDITION(reg->options))
5934 BIT_STATUS_ON_ALL(reg->bt_mem_end);
5936 reg->bt_mem_end = scan_env.bt_mem_end;
5937 reg->bt_mem_end |= reg->capture_history;
5940#ifdef USE_COMBINATION_EXPLOSION_CHECK
5941 if (scan_env.backrefed_mem == 0
5942# ifdef USE_SUBEXP_CALL
5943 || scan_env.num_call == 0
5946 setup_comb_exp_check(root, 0, &scan_env);
5947# ifdef USE_SUBEXP_CALL
5948 if (scan_env.has_recursion != 0) {
5949 scan_env.num_comb_exp_check = 0;
5953 if (scan_env.comb_exp_max_regnum > 0) {
5955 for (i = 1; i <= scan_env.comb_exp_max_regnum; i++) {
5956 if (BIT_STATUS_AT(scan_env.backrefed_mem, i) != 0) {
5957 scan_env.num_comb_exp_check = 0;
5964 reg->num_comb_exp_check = scan_env.num_comb_exp_check;
5967 clear_optimize_info(reg);
5968#ifndef ONIG_DONT_OPTIMIZE
5969 r = set_optimize_info_from_tree(root, reg, &scan_env);
5970 if (r != 0)
goto err_unset;
5973 if (IS_NOT_NULL(scan_env.mem_nodes_dynamic)) {
5974 xfree(scan_env.mem_nodes_dynamic);
5975 scan_env.mem_nodes_dynamic = (Node** )NULL;
5978 r = compile_tree(root, reg);
5980 r = add_opcode(reg, OP_END);
5981 if (r != 0)
goto err_unset;
5982#ifdef USE_SUBEXP_CALL
5983 if (scan_env.num_call > 0) {
5984 r = unset_addr_list_fix(&uslist, reg);
5985 unset_addr_list_end(&uslist);
5990 if ((reg->num_repeat != 0) || (reg->bt_mem_end != 0))
5991 reg->stack_pop_level = STACK_POP_LEVEL_ALL;
5993 if (reg->bt_mem_start != 0)
5994 reg->stack_pop_level = STACK_POP_LEVEL_MEM_START;
5996 reg->stack_pop_level = STACK_POP_LEVEL_FREE;
5999#ifdef USE_SUBEXP_CALL
6000 else if (scan_env.num_call > 0) {
6001 unset_addr_list_end(&uslist);
6004 onig_node_free(root);
6006#ifdef ONIG_DEBUG_COMPILE
6007# ifdef USE_NAMED_GROUP
6008 onig_print_names(stderr, reg);
6010 print_compiled_byte_code_list(stderr, reg);
6014 onig_reg_resize(reg);
6018#ifdef USE_SUBEXP_CALL
6019 if (scan_env.num_call > 0) {
6020 unset_addr_list_end(&uslist);
6024 if (IS_NOT_NULL(scan_env.error)) {
6025 if (IS_NOT_NULL(einfo)) {
6026 einfo->enc = scan_env.enc;
6027 einfo->par = scan_env.error;
6028 einfo->par_end = scan_env.error_end;
6032 onig_node_free(root);
6033 xfree(scan_env.mem_nodes_dynamic);
6038static int onig_inited = 0;
6041onig_reg_init(regex_t* reg, OnigOptionType option,
6042 OnigCaseFoldType case_fold_flag,
6049 return ONIGERR_INVALID_ARGUMENT;
6051 (reg)->exact = (UChar* )NULL;
6052 (reg)->int_map = (
int* )NULL;
6053 (reg)->int_map_backward = (
int* )NULL;
6054 (reg)->chain = (regex_t* )NULL;
6055 (reg)->p = (UChar* )NULL;
6056 (reg)->name_table = (
void* )NULL;
6059 if (ONIGENC_IS_UNDEF(enc))
6060 return ONIGERR_DEFAULT_ENCODING_IS_NOT_SET;
6062 if ((option & (ONIG_OPTION_DONT_CAPTURE_GROUP|ONIG_OPTION_CAPTURE_GROUP))
6063 == (ONIG_OPTION_DONT_CAPTURE_GROUP|ONIG_OPTION_CAPTURE_GROUP)) {
6064 return ONIGERR_INVALID_COMBINATION_OF_OPTIONS;
6067 if ((option & ONIG_OPTION_NEGATE_SINGLELINE) != 0) {
6068 option |= syntax->options;
6069 option &= ~ONIG_OPTION_SINGLELINE;
6072 option |= syntax->options;
6075 (reg)->options = option;
6076 (reg)->syntax = syntax;
6077 (reg)->optimize = 0;
6082 (reg)->case_fold_flag = case_fold_flag;
6084 (reg)->timelimit = 0;
6090onig_new_without_alloc(regex_t* reg,
const UChar* pattern,
6091 const UChar* pattern_end, OnigOptionType option, OnigEncoding enc,
6096 r = onig_reg_init(reg, option, ONIGENC_CASE_FOLD_DEFAULT, enc, syntax);
6099 r = onig_compile(reg, pattern, pattern_end, einfo);
6104onig_new(regex_t** reg,
const UChar* pattern,
const UChar* pattern_end,
6105 OnigOptionType option, OnigEncoding enc,
const OnigSyntaxType* syntax,
6108 *reg = (regex_t* )
xmalloc(
sizeof(regex_t));
6109 if (IS_NULL(*reg))
return ONIGERR_MEMORY;
6111 int r = onig_new_without_alloc(*reg, pattern, pattern_end, option, enc, syntax, einfo);
6121onig_initialize(OnigEncoding encodings[] ARG_UNUSED,
int n ARG_UNUSED)
6129 if (onig_inited != 0)
6134#if defined(ONIG_DEBUG_MEMLEAK) && defined(_MSC_VER)
6135 _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
6141#ifdef ONIG_DEBUG_STATISTICS
6142 onig_statistics_init();
6149static OnigEndCallListItemType* EndCallTop;
6151extern void onig_add_end_call(
void (*func)(
void))
6153 OnigEndCallListItemType* item;
6155 item = (OnigEndCallListItemType* )
xmalloc(
sizeof(*item));
6156 if (item == 0) return ;
6158 item->next = EndCallTop;
6165exec_end_call_list(
void)
6167 OnigEndCallListItemType* prev;
6170 while (EndCallTop != 0) {
6171 func = EndCallTop->func;
6175 EndCallTop = EndCallTop->next;
6183 exec_end_call_list();
6185#ifdef ONIG_DEBUG_STATISTICS
6186 onig_print_statistics(stderr);
6189#if defined(ONIG_DEBUG_MEMLEAK) && defined(_MSC_VER)
6190 _CrtDumpMemoryLeaks();
6199onig_is_in_code_range(
const UChar* p, OnigCodePoint code)
6201 OnigCodePoint n, *data;
6202 OnigCodePoint low, high, x;
6204 GET_CODE_POINT(n, p);
6205 data = (OnigCodePoint* )p;
6208 for (low = 0, high = n; low < high; ) {
6209 x = (low + high) >> 1;
6210 if (code > data[x * 2 + 1])
6216 return ((low < n && code >= data[low * 2]) ? 1 : 0);
6220onig_is_code_in_cc_len(
int elen, OnigCodePoint code,
CClassNode* cc)
6224 if (elen > 1 || (code >= SINGLE_BYTE_SIZE)) {
6225 if (IS_NULL(cc->mbuf)) {
6229 found = (onig_is_in_code_range(cc->mbuf->p, code) != 0 ? 1 : 0);
6233 found = (BITSET_AT(cc->bs, code) == 0 ? 0 : 1);
6236 if (IS_NCCLASS_NOT(cc))
6243onig_is_code_in_cc(OnigEncoding enc, OnigCodePoint code,
CClassNode* cc)
6247 if (ONIGENC_MBC_MINLEN(enc) > 1) {
6251 len = ONIGENC_CODE_TO_MBCLEN(enc, code);
6253 return onig_is_code_in_cc_len(
len, code, cc);
6260# define ARG_SPECIAL -1
6262# define ARG_RELADDR 1
6263# define ARG_ABSADDR 2
6264# define ARG_LENGTH 3
6265# define ARG_MEMNUM 4
6266# define ARG_OPTION 5
6267# define ARG_STATE_CHECK 6
6269OnigOpInfoType OnigOpInfo[] = {
6270 { OP_FINISH,
"finish", ARG_NON },
6271 { OP_END,
"end", ARG_NON },
6272 { OP_EXACT1,
"exact1", ARG_SPECIAL },
6273 { OP_EXACT2,
"exact2", ARG_SPECIAL },
6274 { OP_EXACT3,
"exact3", ARG_SPECIAL },
6275 { OP_EXACT4,
"exact4", ARG_SPECIAL },
6276 { OP_EXACT5,
"exact5", ARG_SPECIAL },
6277 { OP_EXACTN,
"exactn", ARG_SPECIAL },
6278 { OP_EXACTMB2N1,
"exactmb2-n1", ARG_SPECIAL },
6279 { OP_EXACTMB2N2,
"exactmb2-n2", ARG_SPECIAL },
6280 { OP_EXACTMB2N3,
"exactmb2-n3", ARG_SPECIAL },
6281 { OP_EXACTMB2N,
"exactmb2-n", ARG_SPECIAL },
6282 { OP_EXACTMB3N,
"exactmb3n" , ARG_SPECIAL },
6283 { OP_EXACTMBN,
"exactmbn", ARG_SPECIAL },
6284 { OP_EXACT1_IC,
"exact1-ic", ARG_SPECIAL },
6285 { OP_EXACTN_IC,
"exactn-ic", ARG_SPECIAL },
6286 { OP_CCLASS,
"cclass", ARG_SPECIAL },
6287 { OP_CCLASS_MB,
"cclass-mb", ARG_SPECIAL },
6288 { OP_CCLASS_MIX,
"cclass-mix", ARG_SPECIAL },
6289 { OP_CCLASS_NOT,
"cclass-not", ARG_SPECIAL },
6290 { OP_CCLASS_MB_NOT,
"cclass-mb-not", ARG_SPECIAL },
6291 { OP_CCLASS_MIX_NOT,
"cclass-mix-not", ARG_SPECIAL },
6292 { OP_ANYCHAR,
"anychar", ARG_NON },
6293 { OP_ANYCHAR_ML,
"anychar-ml", ARG_NON },
6294 { OP_ANYCHAR_STAR,
"anychar*", ARG_NON },
6295 { OP_ANYCHAR_ML_STAR,
"anychar-ml*", ARG_NON },
6296 { OP_ANYCHAR_STAR_PEEK_NEXT,
"anychar*-peek-next", ARG_SPECIAL },
6297 { OP_ANYCHAR_ML_STAR_PEEK_NEXT,
"anychar-ml*-peek-next", ARG_SPECIAL },
6298 { OP_WORD,
"word", ARG_NON },
6299 { OP_NOT_WORD,
"not-word", ARG_NON },
6300 { OP_WORD_BOUND,
"word-bound", ARG_NON },
6301 { OP_NOT_WORD_BOUND,
"not-word-bound", ARG_NON },
6302 { OP_WORD_BEGIN,
"word-begin", ARG_NON },
6303 { OP_WORD_END,
"word-end", ARG_NON },
6304 { OP_ASCII_WORD,
"ascii-word", ARG_NON },
6305 { OP_NOT_ASCII_WORD,
"not-ascii-word", ARG_NON },
6306 { OP_ASCII_WORD_BOUND,
"ascii-word-bound", ARG_NON },
6307 { OP_NOT_ASCII_WORD_BOUND,
"not-ascii-word-bound", ARG_NON },
6308 { OP_ASCII_WORD_BEGIN,
"ascii-word-begin", ARG_NON },
6309 { OP_ASCII_WORD_END,
"ascii-word-end", ARG_NON },
6310 { OP_BEGIN_BUF,
"begin-buf", ARG_NON },
6311 { OP_END_BUF,
"end-buf", ARG_NON },
6312 { OP_BEGIN_LINE,
"begin-line", ARG_NON },
6313 { OP_END_LINE,
"end-line", ARG_NON },
6314 { OP_SEMI_END_BUF,
"semi-end-buf", ARG_NON },
6315 { OP_BEGIN_POSITION,
"begin-position", ARG_NON },
6316 { OP_BACKREF1,
"backref1", ARG_NON },
6317 { OP_BACKREF2,
"backref2", ARG_NON },
6318 { OP_BACKREFN,
"backrefn", ARG_MEMNUM },
6319 { OP_BACKREFN_IC,
"backrefn-ic", ARG_SPECIAL },
6320 { OP_BACKREF_MULTI,
"backref_multi", ARG_SPECIAL },
6321 { OP_BACKREF_MULTI_IC,
"backref_multi-ic", ARG_SPECIAL },
6322 { OP_BACKREF_WITH_LEVEL,
"backref_at_level", ARG_SPECIAL },
6323 { OP_MEMORY_START_PUSH,
"mem-start-push", ARG_MEMNUM },
6324 { OP_MEMORY_START,
"mem-start", ARG_MEMNUM },
6325 { OP_MEMORY_END_PUSH,
"mem-end-push", ARG_MEMNUM },
6326 { OP_MEMORY_END_PUSH_REC,
"mem-end-push-rec", ARG_MEMNUM },
6327 { OP_MEMORY_END,
"mem-end", ARG_MEMNUM },
6328 { OP_MEMORY_END_REC,
"mem-end-rec", ARG_MEMNUM },
6329 { OP_SET_OPTION_PUSH,
"set-option-push", ARG_OPTION },
6330 { OP_SET_OPTION,
"set-option", ARG_OPTION },
6331 { OP_KEEP,
"keep", ARG_NON },
6332 { OP_FAIL,
"fail", ARG_NON },
6333 { OP_JUMP,
"jump", ARG_RELADDR },
6334 { OP_PUSH,
"push", ARG_RELADDR },
6335 { OP_POP,
"pop", ARG_NON },
6336 { OP_PUSH_OR_JUMP_EXACT1,
"push-or-jump-e1", ARG_SPECIAL },
6337 { OP_PUSH_IF_PEEK_NEXT,
"push-if-peek-next", ARG_SPECIAL },
6338 { OP_REPEAT,
"repeat", ARG_SPECIAL },
6339 { OP_REPEAT_NG,
"repeat-ng", ARG_SPECIAL },
6340 { OP_REPEAT_INC,
"repeat-inc", ARG_MEMNUM },
6341 { OP_REPEAT_INC_NG,
"repeat-inc-ng", ARG_MEMNUM },
6342 { OP_REPEAT_INC_SG,
"repeat-inc-sg", ARG_MEMNUM },
6343 { OP_REPEAT_INC_NG_SG,
"repeat-inc-ng-sg", ARG_MEMNUM },
6344 { OP_NULL_CHECK_START,
"null-check-start", ARG_MEMNUM },
6345 { OP_NULL_CHECK_END,
"null-check-end", ARG_MEMNUM },
6346 { OP_NULL_CHECK_END_MEMST,
"null-check-end-memst", ARG_MEMNUM },
6347 { OP_NULL_CHECK_END_MEMST_PUSH,
"null-check-end-memst-push", ARG_MEMNUM },
6348 { OP_PUSH_POS,
"push-pos", ARG_NON },
6349 { OP_POP_POS,
"pop-pos", ARG_NON },
6350 { OP_PUSH_POS_NOT,
"push-pos-not", ARG_RELADDR },
6351 { OP_FAIL_POS,
"fail-pos", ARG_NON },
6352 { OP_PUSH_STOP_BT,
"push-stop-bt", ARG_NON },
6353 { OP_POP_STOP_BT,
"pop-stop-bt", ARG_NON },
6354 { OP_LOOK_BEHIND,
"look-behind", ARG_SPECIAL },
6355 { OP_PUSH_LOOK_BEHIND_NOT,
"push-look-behind-not", ARG_SPECIAL },
6356 { OP_FAIL_LOOK_BEHIND_NOT,
"fail-look-behind-not", ARG_NON },
6357 { OP_PUSH_ABSENT_POS,
"push-absent-pos", ARG_NON },
6358 { OP_ABSENT,
"absent", ARG_RELADDR },
6359 { OP_ABSENT_END,
"absent-end", ARG_NON },
6360 { OP_CALL,
"call", ARG_ABSADDR },
6361 { OP_RETURN,
"return", ARG_NON },
6362 { OP_CONDITION,
"condition", ARG_SPECIAL },
6363 { OP_STATE_CHECK_PUSH,
"state-check-push", ARG_SPECIAL },
6364 { OP_STATE_CHECK_PUSH_OR_JUMP,
"state-check-push-or-jump", ARG_SPECIAL },
6365 { OP_STATE_CHECK,
"state-check", ARG_STATE_CHECK },
6366 { OP_STATE_CHECK_ANYCHAR_STAR,
"state-check-anychar*", ARG_STATE_CHECK },
6367 { OP_STATE_CHECK_ANYCHAR_ML_STAR,
6368 "state-check-anychar-ml*", ARG_STATE_CHECK },
6377 for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
6378 if (opcode == OnigOpInfo[i].opcode)
6379 return OnigOpInfo[i].name;
6385op2arg_type(
int opcode)
6389 for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
6390 if (opcode == OnigOpInfo[i].opcode)
6391 return OnigOpInfo[i].arg_type;
6396# ifdef ONIG_DEBUG_PARSE_TREE
6398Indent(FILE* f,
int indent)
6401 for (i = 0; i < indent; i++) putc(
' ', f);
6406p_string(FILE* f, ptrdiff_t
len, UChar* s)
6409 while (
len-- > 0) { fputc(*s++, f); }
6413p_len_string(FILE* f, LengthType
len,
int mb_len, UChar* s)
6415 int x =
len * mb_len;
6417 fprintf(f,
":%d:",
len);
6418 while (x-- > 0) { fputc(*s++, f); }
6422onig_print_compiled_byte_code(FILE* f, UChar* bp, UChar* bpend, UChar** nextp,
6429 StateCheckNumType scn;
6433 fprintf(f,
"[%s", op2name(*bp));
6434 arg_type = op2arg_type(*bp);
6435 if (arg_type != ARG_SPECIAL) {
6441 GET_RELADDR_INC(addr, bp);
6442 fprintf(f,
":(%s%d)", (addr >= 0) ?
"+" :
"", addr);
6445 GET_ABSADDR_INC(addr, bp);
6446 fprintf(f,
":(%d)", addr);
6449 GET_LENGTH_INC(
len, bp);
6450 fprintf(f,
":%d",
len);
6453 mem = *((MemNumType* )bp);
6455 fprintf(f,
":%d", mem);
6459 OnigOptionType option = *((OnigOptionType* )bp);
6461 fprintf(f,
":%d", option);
6465 case ARG_STATE_CHECK:
6466 scn = *((StateCheckNumType* )bp);
6467 bp += SIZE_STATE_CHECK_NUM;
6468 fprintf(f,
":%d", scn);
6475 case OP_ANYCHAR_STAR_PEEK_NEXT:
6476 case OP_ANYCHAR_ML_STAR_PEEK_NEXT:
6477 p_string(f, 1, bp++);
break;
6479 p_string(f, 2, bp); bp += 2;
break;
6481 p_string(f, 3, bp); bp += 3;
break;
6483 p_string(f, 4, bp); bp += 4;
break;
6485 p_string(f, 5, bp); bp += 5;
break;
6487 GET_LENGTH_INC(
len, bp);
6488 p_len_string(f,
len, 1, bp);
6493 p_string(f, 2, bp); bp += 2;
break;
6495 p_string(f, 4, bp); bp += 4;
break;
6497 p_string(f, 6, bp); bp += 6;
break;
6499 GET_LENGTH_INC(
len, bp);
6500 p_len_string(f,
len, 2, bp);
6504 GET_LENGTH_INC(
len, bp);
6505 p_len_string(f,
len, 3, bp);
6512 GET_LENGTH_INC(mb_len, bp);
6513 GET_LENGTH_INC(
len, bp);
6514 fprintf(f,
":%d:%d:", mb_len,
len);
6516 while (n-- > 0) { fputc(*bp++, f); }
6521 len = enclen(enc, bp, bpend);
6522 p_string(f,
len, bp);
6526 GET_LENGTH_INC(
len, bp);
6527 p_len_string(f,
len, 1, bp);
6532 n = bitset_on_num((BitSetRef )bp);
6534 fprintf(f,
":%d", n);
6538 n = bitset_on_num((BitSetRef )bp);
6540 fprintf(f,
":%d", n);
6544 case OP_CCLASS_MB_NOT:
6545 GET_LENGTH_INC(
len, bp);
6547# ifndef PLATFORM_UNALIGNED_WORD_ACCESS
6550 GET_CODE_POINT(code, q);
6552 fprintf(f,
":%d:%d", (
int )code,
len);
6556 case OP_CCLASS_MIX_NOT:
6557 n = bitset_on_num((BitSetRef )bp);
6559 GET_LENGTH_INC(
len, bp);
6561# ifndef PLATFORM_UNALIGNED_WORD_ACCESS
6564 GET_CODE_POINT(code, q);
6566 fprintf(f,
":%d:%d:%d", n, (
int )code,
len);
6569 case OP_BACKREFN_IC:
6570 mem = *((MemNumType* )bp);
6572 fprintf(f,
":%d", mem);
6575 case OP_BACKREF_MULTI_IC:
6576 case OP_BACKREF_MULTI:
6578 GET_LENGTH_INC(
len, bp);
6579 for (i = 0; i <
len; i++) {
6580 GET_MEMNUM_INC(mem, bp);
6581 if (i > 0) fputs(
", ", f);
6582 fprintf(f,
"%d", mem);
6586 case OP_BACKREF_WITH_LEVEL:
6588 OnigOptionType option;
6591 GET_OPTION_INC(option, bp);
6592 fprintf(f,
":%d", option);
6593 GET_LENGTH_INC(level, bp);
6594 fprintf(f,
":%d", level);
6597 GET_LENGTH_INC(
len, bp);
6598 for (i = 0; i <
len; i++) {
6599 GET_MEMNUM_INC(mem, bp);
6600 if (i > 0) fputs(
", ", f);
6601 fprintf(f,
"%d", mem);
6609 mem = *((MemNumType* )bp);
6611 addr = *((RelAddrType* )bp);
6613 fprintf(f,
":%d:%d", mem, addr);
6617 case OP_PUSH_OR_JUMP_EXACT1:
6618 case OP_PUSH_IF_PEEK_NEXT:
6619 addr = *((RelAddrType* )bp);
6621 fprintf(f,
":(%s%d)", (addr >= 0) ?
"+" :
"", addr);
6626 case OP_LOOK_BEHIND:
6627 GET_LENGTH_INC(
len, bp);
6628 fprintf(f,
":%d",
len);
6631 case OP_PUSH_LOOK_BEHIND_NOT:
6632 GET_RELADDR_INC(addr, bp);
6633 GET_LENGTH_INC(
len, bp);
6634 fprintf(f,
":%d:(%s%d)",
len, (addr >= 0) ?
"+" :
"", addr);
6637 case OP_STATE_CHECK_PUSH:
6638 case OP_STATE_CHECK_PUSH_OR_JUMP:
6639 scn = *((StateCheckNumType* )bp);
6640 bp += SIZE_STATE_CHECK_NUM;
6641 addr = *((RelAddrType* )bp);
6643 fprintf(f,
":%d:(%s%d)", scn, (addr >= 0) ?
"+" :
"", addr);
6647 GET_MEMNUM_INC(mem, bp);
6648 GET_RELADDR_INC(addr, bp);
6649 fprintf(f,
":%d:(%s%d)", mem, (addr >= 0) ?
"+" :
"", addr);
6653 fprintf(stderr,
"onig_print_compiled_byte_code: undefined code %d\n",
6658 if (nextp) *nextp = bp;
6661# ifdef ONIG_DEBUG_COMPILE
6663print_compiled_byte_code_list(FILE* f, regex_t* reg)
6667 UChar* end = reg->p + reg->used;
6669 fprintf(f,
"code length: %d", reg->used);
6675 fprintf(f,
"\n%ld:", bp - reg->p);
6677 fprintf(f,
" %ld:", bp - reg->p);
6678 onig_print_compiled_byte_code(f, bp, end, &bp, reg->enc);
6685# ifdef ONIG_DEBUG_PARSE_TREE
6687print_indent_tree(FILE* f, Node* node,
int indent)
6689 int i,
type, container_p = 0;
6694 if (IS_NULL(node)) {
6695 fprintf(f,
"ERROR: null node!!!\n");
6703 if (NTYPE(node) == NT_LIST)
6704 fprintf(f,
"<list:%"PRIxPTR
">\n", (intptr_t )node);
6706 fprintf(f,
"<alt:%"PRIxPTR
">\n", (intptr_t )node);
6708 print_indent_tree(f, NCAR(node), indent + add);
6709 while (IS_NOT_NULL(node = NCDR(node))) {
6710 if (NTYPE(node) != type) {
6711 fprintf(f,
"ERROR: list/alt right is not a cons. %d\n", NTYPE(node));
6714 print_indent_tree(f, NCAR(node), indent + add);
6719 fprintf(f,
"<string%s:%"PRIxPTR
">",
6720 (NSTRING_IS_RAW(node) ?
"-raw" :
""), (intptr_t )node);
6721 for (p = NSTR(node)->s; p < NSTR(node)->end; p++) {
6722 if (*p >= 0x20 && *p < 0x7f)
6725 fprintf(f,
" 0x%02x", *p);
6731 fprintf(f,
"<cclass:%"PRIxPTR
">", (intptr_t )node);
6732 if (IS_NCCLASS_NOT(NCCLASS(node))) fputs(
"not ", f);
6733 if (NCCLASS(node)->mbuf) {
6734 BBuf* bbuf = NCCLASS(node)->mbuf;
6735 OnigCodePoint* data = (OnigCodePoint* )bbuf->p;
6736 OnigCodePoint* end = (OnigCodePoint* )(bbuf->p + bbuf->used);
6737 fprintf(f,
"%d", *data++);
6738 for (; data < end; data+=2) {
6740 fprintf(f,
"%04x-%04x", data[0], data[1]);
6746 fprintf(f,
"<ctype:%"PRIxPTR
"> ", (intptr_t )node);
6747 switch (NCTYPE(node)->ctype) {
6748 case ONIGENC_CTYPE_WORD:
6749 if (NCTYPE(node)->not != 0)
6750 fputs(
"not word", f);
6756 fprintf(f,
"ERROR: undefined ctype.\n");
6762 fprintf(f,
"<anychar:%"PRIxPTR
">", (intptr_t )node);
6766 fprintf(f,
"<anchor:%"PRIxPTR
"> ", (intptr_t )node);
6767 switch (NANCHOR(node)->type) {
6768 case ANCHOR_BEGIN_BUF: fputs(
"begin buf", f);
break;
6769 case ANCHOR_END_BUF: fputs(
"end buf", f);
break;
6770 case ANCHOR_BEGIN_LINE: fputs(
"begin line", f);
break;
6771 case ANCHOR_END_LINE: fputs(
"end line", f);
break;
6772 case ANCHOR_SEMI_END_BUF: fputs(
"semi end buf", f);
break;
6773 case ANCHOR_BEGIN_POSITION: fputs(
"begin position", f);
break;
6775 case ANCHOR_WORD_BOUND: fputs(
"word bound", f);
break;
6776 case ANCHOR_NOT_WORD_BOUND: fputs(
"not word bound", f);
break;
6777# ifdef USE_WORD_BEGIN_END
6778 case ANCHOR_WORD_BEGIN: fputs(
"word begin", f);
break;
6779 case ANCHOR_WORD_END: fputs(
"word end", f);
break;
6781 case ANCHOR_PREC_READ: fputs(
"prec read", f); container_p = TRUE;
break;
6782 case ANCHOR_PREC_READ_NOT: fputs(
"prec read not", f); container_p = TRUE;
break;
6783 case ANCHOR_LOOK_BEHIND: fputs(
"look_behind", f); container_p = TRUE;
break;
6784 case ANCHOR_LOOK_BEHIND_NOT: fputs(
"look_behind_not",f); container_p = TRUE;
break;
6785 case ANCHOR_KEEP: fputs(
"keep",f);
break;
6788 fprintf(f,
"ERROR: undefined anchor type.\n");
6798 fprintf(f,
"<backref:%"PRIxPTR
">", (intptr_t )node);
6799 for (i = 0; i < br->back_num; i++) {
6800 if (i > 0) fputs(
", ", f);
6801 fprintf(f,
"%d", p[i]);
6806# ifdef USE_SUBEXP_CALL
6810 fprintf(f,
"<call:%"PRIxPTR
">", (intptr_t )node);
6811 p_string(f, cn->name_end - cn->name, cn->name);
6817 fprintf(f,
"<quantifier:%"PRIxPTR
">{%d,%d}%s\n", (intptr_t )node,
6818 NQTFR(node)->lower, NQTFR(node)->upper,
6819 (NQTFR(node)->greedy ?
"" :
"?"));
6820 print_indent_tree(f, NQTFR(node)->target, indent + add);
6824 fprintf(f,
"<enclose:%"PRIxPTR
"> ", (intptr_t )node);
6825 switch (NENCLOSE(node)->type) {
6826 case ENCLOSE_OPTION:
6827 fprintf(f,
"option:%d", NENCLOSE(node)->option);
6829 case ENCLOSE_MEMORY:
6830 fprintf(f,
"memory:%d", NENCLOSE(node)->regnum);
6832 case ENCLOSE_STOP_BACKTRACK:
6833 fprintf(f,
"stop-bt");
6835 case ENCLOSE_CONDITION:
6836 fprintf(f,
"condition:%d", NENCLOSE(node)->regnum);
6838 case ENCLOSE_ABSENT:
6839 fprintf(f,
"absent");
6846 print_indent_tree(f, NENCLOSE(node)->target, indent + add);
6850 fprintf(f,
"print_indent_tree: undefined node type %d\n", NTYPE(node));
6854 if (type != NT_LIST && type != NT_ALT && type != NT_QTFR &&
6858 if (container_p) print_indent_tree(f, NANCHOR(node)->target, indent + add);
6864print_tree(FILE* f, Node* node)
6866 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.
char * ptr
Pointer to the underlying memory region, of at least capa bytes.
int len
Length of the buffer.
VALUE type(ANYARGS)
ANYARGS-ed function type.