xref: /PHP-7.1/ext/mbstring/oniguruma/regcomp.c (revision 31f59e1f)
1 /**********************************************************************
2   regcomp.c -  Oniguruma (regular expression library)
3 **********************************************************************/
4 /*-
5  * Copyright (c) 2002-2013  K.Kosako  <sndgk393 AT ybb DOT ne DOT jp>
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  */
29 
30 #include "regparse.h"
31 
32 OnigCaseFoldType OnigDefaultCaseFoldFlag = ONIGENC_CASE_FOLD_MIN;
33 
34 extern OnigCaseFoldType
onig_get_default_case_fold_flag(void)35 onig_get_default_case_fold_flag(void)
36 {
37   return OnigDefaultCaseFoldFlag;
38 }
39 
40 extern int
onig_set_default_case_fold_flag(OnigCaseFoldType case_fold_flag)41 onig_set_default_case_fold_flag(OnigCaseFoldType case_fold_flag)
42 {
43   OnigDefaultCaseFoldFlag = case_fold_flag;
44   return 0;
45 }
46 
47 
48 #ifndef PLATFORM_UNALIGNED_WORD_ACCESS
49 static unsigned char PadBuf[WORD_ALIGNMENT_SIZE];
50 #endif
51 
52 static UChar*
str_dup(UChar * s,UChar * end)53 str_dup(UChar* s, UChar* end)
54 {
55   int len = end - s;
56 
57   if (len > 0) {
58     UChar* r = (UChar* )xmalloc(len + 1);
59     CHECK_NULL_RETURN(r);
60     xmemcpy(r, s, len);
61     r[len] = (UChar )0;
62     return r;
63   }
64   else return NULL;
65 }
66 
67 static void
swap_node(Node * a,Node * b)68 swap_node(Node* a, Node* b)
69 {
70   Node c;
71   c = *a; *a = *b; *b = c;
72 
73   if (NTYPE(a) == NT_STR) {
74     StrNode* sn = NSTR(a);
75     if (sn->capa == 0) {
76       int len = sn->end - sn->s;
77       sn->s   = sn->buf;
78       sn->end = sn->s + len;
79     }
80   }
81 
82   if (NTYPE(b) == NT_STR) {
83     StrNode* sn = NSTR(b);
84     if (sn->capa == 0) {
85       int len = sn->end - sn->s;
86       sn->s   = sn->buf;
87       sn->end = sn->s + len;
88     }
89   }
90 }
91 
92 static OnigDistance
distance_add(OnigDistance d1,OnigDistance d2)93 distance_add(OnigDistance d1, OnigDistance d2)
94 {
95   if (d1 == ONIG_INFINITE_DISTANCE || d2 == ONIG_INFINITE_DISTANCE)
96     return ONIG_INFINITE_DISTANCE;
97   else {
98     if (d1 <= ONIG_INFINITE_DISTANCE - d2) return d1 + d2;
99     else return ONIG_INFINITE_DISTANCE;
100   }
101 }
102 
103 static OnigDistance
distance_multiply(OnigDistance d,int m)104 distance_multiply(OnigDistance d, int m)
105 {
106   if (m == 0) return 0;
107 
108   if (d < ONIG_INFINITE_DISTANCE / m)
109     return d * m;
110   else
111     return ONIG_INFINITE_DISTANCE;
112 }
113 
114 static int
bitset_is_empty(BitSetRef bs)115 bitset_is_empty(BitSetRef bs)
116 {
117   int i;
118   for (i = 0; i < (int )BITSET_SIZE; i++) {
119     if (bs[i] != 0) return 0;
120   }
121   return 1;
122 }
123 
124 #ifdef ONIG_DEBUG
125 static int
bitset_on_num(BitSetRef bs)126 bitset_on_num(BitSetRef bs)
127 {
128   int i, n;
129 
130   n = 0;
131   for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
132     if (BITSET_AT(bs, i)) n++;
133   }
134   return n;
135 }
136 #endif
137 
138 extern int
onig_bbuf_init(BBuf * buf,int size)139 onig_bbuf_init(BBuf* buf, int size)
140 {
141   if (size <= 0) {
142     size   = 0;
143     buf->p = NULL;
144   }
145   else {
146     buf->p = (UChar* )xmalloc(size);
147     if (IS_NULL(buf->p)) return(ONIGERR_MEMORY);
148   }
149 
150   buf->alloc = size;
151   buf->used  = 0;
152   return 0;
153 }
154 
155 
156 #ifdef USE_SUBEXP_CALL
157 
158 static int
unset_addr_list_init(UnsetAddrList * uslist,int size)159 unset_addr_list_init(UnsetAddrList* uslist, int size)
160 {
161   UnsetAddr* p;
162 
163   p = (UnsetAddr* )xmalloc(sizeof(UnsetAddr)* size);
164   CHECK_NULL_RETURN_MEMERR(p);
165   uslist->num   = 0;
166   uslist->alloc = size;
167   uslist->us    = p;
168   return 0;
169 }
170 
171 static void
unset_addr_list_end(UnsetAddrList * uslist)172 unset_addr_list_end(UnsetAddrList* uslist)
173 {
174   if (IS_NOT_NULL(uslist->us))
175     xfree(uslist->us);
176 }
177 
178 static int
unset_addr_list_add(UnsetAddrList * uslist,int offset,struct _Node * node)179 unset_addr_list_add(UnsetAddrList* uslist, int offset, struct _Node* node)
180 {
181   UnsetAddr* p;
182   int size;
183 
184   if (uslist->num >= uslist->alloc) {
185     size = uslist->alloc * 2;
186     p = (UnsetAddr* )xrealloc(uslist->us, sizeof(UnsetAddr) * size);
187     CHECK_NULL_RETURN_MEMERR(p);
188     uslist->alloc = size;
189     uslist->us    = p;
190   }
191 
192   uslist->us[uslist->num].offset = offset;
193   uslist->us[uslist->num].target = node;
194   uslist->num++;
195   return 0;
196 }
197 #endif /* USE_SUBEXP_CALL */
198 
199 
200 static int
add_opcode(regex_t * reg,int opcode)201 add_opcode(regex_t* reg, int opcode)
202 {
203   BBUF_ADD1(reg, opcode);
204   return 0;
205 }
206 
207 #ifdef USE_COMBINATION_EXPLOSION_CHECK
208 static int
add_state_check_num(regex_t * reg,int num)209 add_state_check_num(regex_t* reg, int num)
210 {
211   StateCheckNumType n = (StateCheckNumType )num;
212 
213   BBUF_ADD(reg, &n, SIZE_STATE_CHECK_NUM);
214   return 0;
215 }
216 #endif
217 
218 static int
add_rel_addr(regex_t * reg,int addr)219 add_rel_addr(regex_t* reg, int addr)
220 {
221   RelAddrType ra = (RelAddrType )addr;
222 
223   BBUF_ADD(reg, &ra, SIZE_RELADDR);
224   return 0;
225 }
226 
227 static int
add_abs_addr(regex_t * reg,int addr)228 add_abs_addr(regex_t* reg, int addr)
229 {
230   AbsAddrType ra = (AbsAddrType )addr;
231 
232   BBUF_ADD(reg, &ra, SIZE_ABSADDR);
233   return 0;
234 }
235 
236 static int
add_length(regex_t * reg,int len)237 add_length(regex_t* reg, int len)
238 {
239   LengthType l = (LengthType )len;
240 
241   BBUF_ADD(reg, &l, SIZE_LENGTH);
242   return 0;
243 }
244 
245 static int
add_mem_num(regex_t * reg,int num)246 add_mem_num(regex_t* reg, int num)
247 {
248   MemNumType n = (MemNumType )num;
249 
250   BBUF_ADD(reg, &n, SIZE_MEMNUM);
251   return 0;
252 }
253 
254 static int
add_pointer(regex_t * reg,void * addr)255 add_pointer(regex_t* reg, void* addr)
256 {
257   PointerType ptr = (PointerType )addr;
258 
259   BBUF_ADD(reg, &ptr, SIZE_POINTER);
260   return 0;
261 }
262 
263 static int
add_option(regex_t * reg,OnigOptionType option)264 add_option(regex_t* reg, OnigOptionType option)
265 {
266   BBUF_ADD(reg, &option, SIZE_OPTION);
267   return 0;
268 }
269 
270 static int
add_opcode_rel_addr(regex_t * reg,int opcode,int addr)271 add_opcode_rel_addr(regex_t* reg, int opcode, int addr)
272 {
273   int r;
274 
275   r = add_opcode(reg, opcode);
276   if (r) return r;
277   r = add_rel_addr(reg, addr);
278   return r;
279 }
280 
281 static int
add_bytes(regex_t * reg,UChar * bytes,int len)282 add_bytes(regex_t* reg, UChar* bytes, int len)
283 {
284   BBUF_ADD(reg, bytes, len);
285   return 0;
286 }
287 
288 static int
add_bitset(regex_t * reg,BitSetRef bs)289 add_bitset(regex_t* reg, BitSetRef bs)
290 {
291   BBUF_ADD(reg, bs, SIZE_BITSET);
292   return 0;
293 }
294 
295 static int
add_opcode_option(regex_t * reg,int opcode,OnigOptionType option)296 add_opcode_option(regex_t* reg, int opcode, OnigOptionType option)
297 {
298   int r;
299 
300   r = add_opcode(reg, opcode);
301   if (r) return r;
302   r = add_option(reg, option);
303   return r;
304 }
305 
306 static int compile_length_tree(Node* node, regex_t* reg);
307 static int compile_tree(Node* node, regex_t* reg);
308 
309 
310 #define IS_NEED_STR_LEN_OP_EXACT(op) \
311    ((op) == OP_EXACTN    || (op) == OP_EXACTMB2N ||\
312     (op) == OP_EXACTMB3N || (op) == OP_EXACTMBN  || (op) == OP_EXACTN_IC)
313 
314 static int
select_str_opcode(int mb_len,int str_len,int ignore_case)315 select_str_opcode(int mb_len, int str_len, int ignore_case)
316 {
317   int op;
318 
319   if (ignore_case) {
320     switch (str_len) {
321     case 1:  op = OP_EXACT1_IC; break;
322     default: op = OP_EXACTN_IC; break;
323     }
324   }
325   else {
326     switch (mb_len) {
327     case 1:
328       switch (str_len) {
329       case 1:  op = OP_EXACT1; break;
330       case 2:  op = OP_EXACT2; break;
331       case 3:  op = OP_EXACT3; break;
332       case 4:  op = OP_EXACT4; break;
333       case 5:  op = OP_EXACT5; break;
334       default: op = OP_EXACTN; break;
335       }
336       break;
337 
338     case 2:
339       switch (str_len) {
340       case 1:  op = OP_EXACTMB2N1; break;
341       case 2:  op = OP_EXACTMB2N2; break;
342       case 3:  op = OP_EXACTMB2N3; break;
343       default: op = OP_EXACTMB2N;  break;
344       }
345       break;
346 
347     case 3:
348       op = OP_EXACTMB3N;
349       break;
350 
351     default:
352       op = OP_EXACTMBN;
353       break;
354     }
355   }
356   return op;
357 }
358 
359 static int
compile_tree_empty_check(Node * node,regex_t * reg,int empty_info)360 compile_tree_empty_check(Node* node, regex_t* reg, int empty_info)
361 {
362   int r;
363   int saved_num_null_check = reg->num_null_check;
364 
365   if (empty_info != 0) {
366     r = add_opcode(reg, OP_NULL_CHECK_START);
367     if (r) return r;
368     r = add_mem_num(reg, reg->num_null_check); /* NULL CHECK ID */
369     if (r) return r;
370     reg->num_null_check++;
371   }
372 
373   r = compile_tree(node, reg);
374   if (r) return r;
375 
376   if (empty_info != 0) {
377     if (empty_info == NQ_TARGET_IS_EMPTY)
378       r = add_opcode(reg, OP_NULL_CHECK_END);
379     else if (empty_info == NQ_TARGET_IS_EMPTY_MEM)
380       r = add_opcode(reg, OP_NULL_CHECK_END_MEMST);
381     else if (empty_info == NQ_TARGET_IS_EMPTY_REC)
382       r = add_opcode(reg, OP_NULL_CHECK_END_MEMST_PUSH);
383 
384     if (r) return r;
385     r = add_mem_num(reg, saved_num_null_check); /* NULL CHECK ID */
386   }
387   return r;
388 }
389 
390 #ifdef USE_SUBEXP_CALL
391 static int
compile_call(CallNode * node,regex_t * reg)392 compile_call(CallNode* node, regex_t* reg)
393 {
394   int r;
395 
396   r = add_opcode(reg, OP_CALL);
397   if (r) return r;
398   r = unset_addr_list_add(node->unset_addr_list, BBUF_GET_OFFSET_POS(reg),
399                           node->target);
400   if (r) return r;
401   r = add_abs_addr(reg, 0 /*dummy addr.*/);
402   return r;
403 }
404 #endif
405 
406 static int
compile_tree_n_times(Node * node,int n,regex_t * reg)407 compile_tree_n_times(Node* node, int n, regex_t* reg)
408 {
409   int i, r;
410 
411   for (i = 0; i < n; i++) {
412     r = compile_tree(node, reg);
413     if (r) return r;
414   }
415   return 0;
416 }
417 
418 static int
add_compile_string_length(UChar * s ARG_UNUSED,int mb_len,int str_len,regex_t * reg ARG_UNUSED,int ignore_case)419 add_compile_string_length(UChar* s ARG_UNUSED, int mb_len, int str_len,
420                           regex_t* reg ARG_UNUSED, int ignore_case)
421 {
422   int len;
423   int op = select_str_opcode(mb_len, str_len, ignore_case);
424 
425   len = SIZE_OPCODE;
426 
427   if (op == OP_EXACTMBN)  len += SIZE_LENGTH;
428   if (IS_NEED_STR_LEN_OP_EXACT(op))
429     len += SIZE_LENGTH;
430 
431   len += mb_len * str_len;
432   return len;
433 }
434 
435 static int
add_compile_string(UChar * s,int mb_len,int str_len,regex_t * reg,int ignore_case)436 add_compile_string(UChar* s, int mb_len, int str_len,
437                    regex_t* reg, int ignore_case)
438 {
439   int op = select_str_opcode(mb_len, str_len, ignore_case);
440   add_opcode(reg, op);
441 
442   if (op == OP_EXACTMBN)
443     add_length(reg, mb_len);
444 
445   if (IS_NEED_STR_LEN_OP_EXACT(op)) {
446     if (op == OP_EXACTN_IC)
447       add_length(reg, mb_len * str_len);
448     else
449       add_length(reg, str_len);
450   }
451 
452   add_bytes(reg, s, mb_len * str_len);
453   return 0;
454 }
455 
456 
457 static int
compile_length_string_node(Node * node,regex_t * reg)458 compile_length_string_node(Node* node, regex_t* reg)
459 {
460   int rlen, r, len, prev_len, slen, ambig;
461   OnigEncoding enc = reg->enc;
462   UChar *p, *prev;
463   StrNode* sn;
464 
465   sn = NSTR(node);
466   if (sn->end <= sn->s)
467     return 0;
468 
469   ambig = NSTRING_IS_AMBIG(node);
470 
471   p = prev = sn->s;
472   SAFE_ENC_LEN(enc, p, sn->end, prev_len);
473   p += prev_len;
474   slen = 1;
475   rlen = 0;
476 
477   for (; p < sn->end; ) {
478     SAFE_ENC_LEN(enc, p, sn->end, len);
479     if (len == prev_len) {
480       slen++;
481     }
482     else {
483       r = add_compile_string_length(prev, prev_len, slen, reg, ambig);
484       rlen += r;
485       prev = p;
486       slen = 1;
487       prev_len = len;
488     }
489     p += len;
490   }
491   r = add_compile_string_length(prev, prev_len, slen, reg, ambig);
492   rlen += r;
493   return rlen;
494 }
495 
496 static int
compile_length_string_raw_node(StrNode * sn,regex_t * reg)497 compile_length_string_raw_node(StrNode* sn, regex_t* reg)
498 {
499   if (sn->end <= sn->s)
500     return 0;
501 
502   return add_compile_string_length(sn->s, 1 /* sb */, sn->end - sn->s, reg, 0);
503 }
504 
505 static int
compile_string_node(Node * node,regex_t * reg)506 compile_string_node(Node* node, regex_t* reg)
507 {
508   int r, len, prev_len, slen, ambig;
509   OnigEncoding enc = reg->enc;
510   UChar *p, *prev, *end;
511   StrNode* sn;
512 
513   sn = NSTR(node);
514   if (sn->end <= sn->s)
515     return 0;
516 
517   end = sn->end;
518   ambig = NSTRING_IS_AMBIG(node);
519 
520   p = prev = sn->s;
521   SAFE_ENC_LEN(enc, p, end, prev_len);
522   p += prev_len;
523   slen = 1;
524 
525   for (; p < end; ) {
526     SAFE_ENC_LEN(enc, p, end, len);
527     if (len == prev_len) {
528       slen++;
529     }
530     else {
531       r = add_compile_string(prev, prev_len, slen, reg, ambig);
532       if (r) return r;
533 
534       prev  = p;
535       slen  = 1;
536       prev_len = len;
537     }
538 
539     p += len;
540   }
541   return add_compile_string(prev, prev_len, slen, reg, ambig);
542 }
543 
544 static int
compile_string_raw_node(StrNode * sn,regex_t * reg)545 compile_string_raw_node(StrNode* sn, regex_t* reg)
546 {
547   if (sn->end <= sn->s)
548     return 0;
549 
550   return add_compile_string(sn->s, 1 /* sb */, sn->end - sn->s, reg, 0);
551 }
552 
553 static int
add_multi_byte_cclass(BBuf * mbuf,regex_t * reg)554 add_multi_byte_cclass(BBuf* mbuf, regex_t* reg)
555 {
556 #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
557   add_length(reg, mbuf->used);
558   return add_bytes(reg, mbuf->p, mbuf->used);
559 #else
560   int r, pad_size;
561   UChar* p = BBUF_GET_ADD_ADDRESS(reg) + SIZE_LENGTH;
562 
563   GET_ALIGNMENT_PAD_SIZE(p, pad_size);
564   add_length(reg, mbuf->used + (WORD_ALIGNMENT_SIZE - 1));
565   if (pad_size != 0) add_bytes(reg, PadBuf, pad_size);
566 
567   r = add_bytes(reg, mbuf->p, mbuf->used);
568 
569   /* padding for return value from compile_length_cclass_node() to be fix. */
570   pad_size = (WORD_ALIGNMENT_SIZE - 1) - pad_size;
571   if (pad_size != 0) add_bytes(reg, PadBuf, pad_size);
572   return r;
573 #endif
574 }
575 
576 static int
compile_length_cclass_node(CClassNode * cc,regex_t * reg)577 compile_length_cclass_node(CClassNode* cc, regex_t* reg)
578 {
579   int len;
580 
581   if (IS_NCCLASS_SHARE(cc)) {
582     len = SIZE_OPCODE + SIZE_POINTER;
583     return len;
584   }
585 
586   if (IS_NULL(cc->mbuf)) {
587     len = SIZE_OPCODE + SIZE_BITSET;
588   }
589   else {
590     if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {
591       len = SIZE_OPCODE;
592     }
593     else {
594       len = SIZE_OPCODE + SIZE_BITSET;
595     }
596 #ifdef PLATFORM_UNALIGNED_WORD_ACCESS
597     len += SIZE_LENGTH + cc->mbuf->used;
598 #else
599     len += SIZE_LENGTH + cc->mbuf->used + (WORD_ALIGNMENT_SIZE - 1);
600 #endif
601   }
602 
603   return len;
604 }
605 
606 static int
compile_cclass_node(CClassNode * cc,regex_t * reg)607 compile_cclass_node(CClassNode* cc, regex_t* reg)
608 {
609   int r;
610 
611   if (IS_NCCLASS_SHARE(cc)) {
612     add_opcode(reg, OP_CCLASS_NODE);
613     r = add_pointer(reg, cc);
614     return r;
615   }
616 
617   if (IS_NULL(cc->mbuf)) {
618     if (IS_NCCLASS_NOT(cc))
619       add_opcode(reg, OP_CCLASS_NOT);
620     else
621       add_opcode(reg, OP_CCLASS);
622 
623     r = add_bitset(reg, cc->bs);
624   }
625   else {
626     if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {
627       if (IS_NCCLASS_NOT(cc))
628         add_opcode(reg, OP_CCLASS_MB_NOT);
629       else
630         add_opcode(reg, OP_CCLASS_MB);
631 
632       r = add_multi_byte_cclass(cc->mbuf, reg);
633     }
634     else {
635       if (IS_NCCLASS_NOT(cc))
636         add_opcode(reg, OP_CCLASS_MIX_NOT);
637       else
638         add_opcode(reg, OP_CCLASS_MIX);
639 
640       r = add_bitset(reg, cc->bs);
641       if (r) return r;
642       r = add_multi_byte_cclass(cc->mbuf, reg);
643     }
644   }
645 
646   return r;
647 }
648 
649 static int
entry_repeat_range(regex_t * reg,int id,int lower,int upper)650 entry_repeat_range(regex_t* reg, int id, int lower, int upper)
651 {
652 #define REPEAT_RANGE_ALLOC  4
653 
654   OnigRepeatRange* p;
655 
656   if (reg->repeat_range_alloc == 0) {
657     p = (OnigRepeatRange* )xmalloc(sizeof(OnigRepeatRange) * REPEAT_RANGE_ALLOC);
658     CHECK_NULL_RETURN_MEMERR(p);
659     reg->repeat_range = p;
660     reg->repeat_range_alloc = REPEAT_RANGE_ALLOC;
661   }
662   else if (reg->repeat_range_alloc <= id) {
663     int n;
664     n = reg->repeat_range_alloc + REPEAT_RANGE_ALLOC;
665     p = (OnigRepeatRange* )xrealloc(reg->repeat_range,
666                                     sizeof(OnigRepeatRange) * n);
667     CHECK_NULL_RETURN_MEMERR(p);
668     reg->repeat_range = p;
669     reg->repeat_range_alloc = n;
670   }
671   else {
672     p = reg->repeat_range;
673   }
674 
675   p[id].lower = lower;
676   p[id].upper = (IS_REPEAT_INFINITE(upper) ? 0x7fffffff : upper);
677   return 0;
678 }
679 
680 static int
compile_range_repeat_node(QtfrNode * qn,int target_len,int empty_info,regex_t * reg)681 compile_range_repeat_node(QtfrNode* qn, int target_len, int empty_info,
682                           regex_t* reg)
683 {
684   int r;
685   int num_repeat = reg->num_repeat;
686 
687   r = add_opcode(reg, qn->greedy ? OP_REPEAT : OP_REPEAT_NG);
688   if (r) return r;
689   r = add_mem_num(reg, num_repeat); /* OP_REPEAT ID */
690   reg->num_repeat++;
691   if (r) return r;
692   r = add_rel_addr(reg, target_len + SIZE_OP_REPEAT_INC);
693   if (r) return r;
694 
695   r = entry_repeat_range(reg, num_repeat, qn->lower, qn->upper);
696   if (r) return r;
697 
698   r = compile_tree_empty_check(qn->target, reg, empty_info);
699   if (r) return r;
700 
701   if (
702 #ifdef USE_SUBEXP_CALL
703       reg->num_call > 0 ||
704 #endif
705       IS_QUANTIFIER_IN_REPEAT(qn)) {
706     r = add_opcode(reg, qn->greedy ? OP_REPEAT_INC_SG : OP_REPEAT_INC_NG_SG);
707   }
708   else {
709     r = add_opcode(reg, qn->greedy ? OP_REPEAT_INC : OP_REPEAT_INC_NG);
710   }
711   if (r) return r;
712   r = add_mem_num(reg, num_repeat); /* OP_REPEAT ID */
713   return r;
714 }
715 
716 static int
is_anychar_star_quantifier(QtfrNode * qn)717 is_anychar_star_quantifier(QtfrNode* qn)
718 {
719   if (qn->greedy && IS_REPEAT_INFINITE(qn->upper) &&
720       NTYPE(qn->target) == NT_CANY)
721     return 1;
722   else
723     return 0;
724 }
725 
726 #define QUANTIFIER_EXPAND_LIMIT_SIZE   50
727 #define CKN_ON   (ckn > 0)
728 
729 #ifdef USE_COMBINATION_EXPLOSION_CHECK
730 
731 static int
compile_length_quantifier_node(QtfrNode * qn,regex_t * reg)732 compile_length_quantifier_node(QtfrNode* qn, regex_t* reg)
733 {
734   int len, mod_tlen, cklen;
735   int ckn;
736   int infinite = IS_REPEAT_INFINITE(qn->upper);
737   int empty_info = qn->target_empty_info;
738   int tlen = compile_length_tree(qn->target, reg);
739 
740   if (tlen < 0) return tlen;
741 
742   ckn = ((reg->num_comb_exp_check > 0) ? qn->comb_exp_check_num : 0);
743 
744   cklen = (CKN_ON ? SIZE_STATE_CHECK_NUM: 0);
745 
746   /* anychar repeat */
747   if (NTYPE(qn->target) == NT_CANY) {
748     if (qn->greedy && infinite) {
749       if (IS_NOT_NULL(qn->next_head_exact) && !CKN_ON)
750         return SIZE_OP_ANYCHAR_STAR_PEEK_NEXT + tlen * qn->lower + cklen;
751       else
752         return SIZE_OP_ANYCHAR_STAR + tlen * qn->lower + cklen;
753     }
754   }
755 
756   if (empty_info != 0)
757     mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
758   else
759     mod_tlen = tlen;
760 
761   if (infinite && qn->lower <= 1) {
762     if (qn->greedy) {
763       if (qn->lower == 1)
764 	len = SIZE_OP_JUMP;
765       else
766 	len = 0;
767 
768       len += SIZE_OP_PUSH + cklen + mod_tlen + SIZE_OP_JUMP;
769     }
770     else {
771       if (qn->lower == 0)
772 	len = SIZE_OP_JUMP;
773       else
774 	len = 0;
775 
776       len += mod_tlen + SIZE_OP_PUSH + cklen;
777     }
778   }
779   else if (qn->upper == 0) {
780     if (qn->is_refered != 0) /* /(?<n>..){0}/ */
781       len = SIZE_OP_JUMP + tlen;
782     else
783       len = 0;
784   }
785   else if (qn->upper == 1 && qn->greedy) {
786     if (qn->lower == 0) {
787       if (CKN_ON) {
788 	len = SIZE_OP_STATE_CHECK_PUSH + tlen;
789       }
790       else {
791 	len = SIZE_OP_PUSH + tlen;
792       }
793     }
794     else {
795       len = tlen;
796     }
797   }
798   else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) { /* '??' */
799     len = SIZE_OP_PUSH + cklen + SIZE_OP_JUMP + tlen;
800   }
801   else {
802     len = SIZE_OP_REPEAT_INC
803         + mod_tlen + SIZE_OPCODE + SIZE_RELADDR + SIZE_MEMNUM;
804     if (CKN_ON)
805       len += SIZE_OP_STATE_CHECK;
806   }
807 
808   return len;
809 }
810 
811 static int
compile_quantifier_node(QtfrNode * qn,regex_t * reg)812 compile_quantifier_node(QtfrNode* qn, regex_t* reg)
813 {
814   int r, mod_tlen;
815   int ckn;
816   int infinite = IS_REPEAT_INFINITE(qn->upper);
817   int empty_info = qn->target_empty_info;
818   int tlen = compile_length_tree(qn->target, reg);
819 
820   if (tlen < 0) return tlen;
821 
822   ckn = ((reg->num_comb_exp_check > 0) ? qn->comb_exp_check_num : 0);
823 
824   if (is_anychar_star_quantifier(qn)) {
825     r = compile_tree_n_times(qn->target, qn->lower, reg);
826     if (r) return r;
827     if (IS_NOT_NULL(qn->next_head_exact) && !CKN_ON) {
828       if (IS_MULTILINE(reg->options))
829 	r = add_opcode(reg, OP_ANYCHAR_ML_STAR_PEEK_NEXT);
830       else
831 	r = add_opcode(reg, OP_ANYCHAR_STAR_PEEK_NEXT);
832       if (r) return r;
833       if (CKN_ON) {
834 	r = add_state_check_num(reg, ckn);
835 	if (r) return r;
836       }
837 
838       return add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
839     }
840     else {
841       if (IS_MULTILINE(reg->options)) {
842 	r = add_opcode(reg, (CKN_ON ?
843 			       OP_STATE_CHECK_ANYCHAR_ML_STAR
844 			     : OP_ANYCHAR_ML_STAR));
845       }
846       else {
847 	r = add_opcode(reg, (CKN_ON ?
848 			       OP_STATE_CHECK_ANYCHAR_STAR
849 			     : OP_ANYCHAR_STAR));
850       }
851       if (r) return r;
852       if (CKN_ON)
853 	r = add_state_check_num(reg, ckn);
854 
855       return r;
856     }
857   }
858 
859   if (empty_info != 0)
860     mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
861   else
862     mod_tlen = tlen;
863 
864   if (infinite && qn->lower <= 1) {
865     if (qn->greedy) {
866       if (qn->lower == 1) {
867 	r = add_opcode_rel_addr(reg, OP_JUMP,
868 			(CKN_ON ? SIZE_OP_STATE_CHECK_PUSH : SIZE_OP_PUSH));
869 	if (r) return r;
870       }
871 
872       if (CKN_ON) {
873 	r = add_opcode(reg, OP_STATE_CHECK_PUSH);
874 	if (r) return r;
875 	r = add_state_check_num(reg, ckn);
876 	if (r) return r;
877 	r = add_rel_addr(reg, mod_tlen + SIZE_OP_JUMP);
878       }
879       else {
880 	r = add_opcode_rel_addr(reg, OP_PUSH, mod_tlen + SIZE_OP_JUMP);
881       }
882       if (r) return r;
883       r = compile_tree_empty_check(qn->target, reg, empty_info);
884       if (r) return r;
885       r = add_opcode_rel_addr(reg, OP_JUMP,
886 	      -(mod_tlen + (int )SIZE_OP_JUMP
887 		+ (int )(CKN_ON ? SIZE_OP_STATE_CHECK_PUSH : SIZE_OP_PUSH)));
888     }
889     else {
890       if (qn->lower == 0) {
891 	r = add_opcode_rel_addr(reg, OP_JUMP, mod_tlen);
892 	if (r) return r;
893       }
894       r = compile_tree_empty_check(qn->target, reg, empty_info);
895       if (r) return r;
896       if (CKN_ON) {
897 	r = add_opcode(reg, OP_STATE_CHECK_PUSH_OR_JUMP);
898 	if (r) return r;
899 	r = add_state_check_num(reg, ckn);
900 	if (r) return r;
901 	r = add_rel_addr(reg,
902 		 -(mod_tlen + (int )SIZE_OP_STATE_CHECK_PUSH_OR_JUMP));
903       }
904       else
905 	r = add_opcode_rel_addr(reg, OP_PUSH, -(mod_tlen + (int )SIZE_OP_PUSH));
906     }
907   }
908   else if (qn->upper == 0) {
909     if (qn->is_refered != 0) { /* /(?<n>..){0}/ */
910       r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
911       if (r) return r;
912       r = compile_tree(qn->target, reg);
913     }
914     else
915       r = 0;
916   }
917   else if (qn->upper == 1 && qn->greedy) {
918     if (qn->lower == 0) {
919       if (CKN_ON) {
920 	r = add_opcode(reg, OP_STATE_CHECK_PUSH);
921 	if (r) return r;
922 	r = add_state_check_num(reg, ckn);
923 	if (r) return r;
924 	r = add_rel_addr(reg, tlen);
925       }
926       else {
927 	r = add_opcode_rel_addr(reg, OP_PUSH, tlen);
928       }
929       if (r) return r;
930     }
931 
932     r = compile_tree(qn->target, reg);
933   }
934   else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) { /* '??' */
935     if (CKN_ON) {
936       r = add_opcode(reg, OP_STATE_CHECK_PUSH);
937       if (r) return r;
938       r = add_state_check_num(reg, ckn);
939       if (r) return r;
940       r = add_rel_addr(reg, SIZE_OP_JUMP);
941     }
942     else {
943       r = add_opcode_rel_addr(reg, OP_PUSH, SIZE_OP_JUMP);
944     }
945 
946     if (r) return r;
947     r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
948     if (r) return r;
949     r = compile_tree(qn->target, reg);
950   }
951   else {
952     r = compile_range_repeat_node(qn, mod_tlen, empty_info, reg);
953     if (CKN_ON) {
954       if (r) return r;
955       r = add_opcode(reg, OP_STATE_CHECK);
956       if (r) return r;
957       r = add_state_check_num(reg, ckn);
958     }
959   }
960   return r;
961 }
962 
963 #else /* USE_COMBINATION_EXPLOSION_CHECK */
964 
965 static int
compile_length_quantifier_node(QtfrNode * qn,regex_t * reg)966 compile_length_quantifier_node(QtfrNode* qn, regex_t* reg)
967 {
968   int len, mod_tlen;
969   int infinite = IS_REPEAT_INFINITE(qn->upper);
970   int empty_info = qn->target_empty_info;
971   int tlen = compile_length_tree(qn->target, reg);
972 
973   if (tlen < 0) return tlen;
974 
975   /* anychar repeat */
976   if (NTYPE(qn->target) == NT_CANY) {
977     if (qn->greedy && infinite) {
978       if (IS_NOT_NULL(qn->next_head_exact))
979         return SIZE_OP_ANYCHAR_STAR_PEEK_NEXT + tlen * qn->lower;
980       else
981         return SIZE_OP_ANYCHAR_STAR + tlen * qn->lower;
982     }
983   }
984 
985   if (empty_info != 0)
986     mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
987   else
988     mod_tlen = tlen;
989 
990   if (infinite &&
991       (qn->lower <= 1 || tlen * qn->lower <= QUANTIFIER_EXPAND_LIMIT_SIZE)) {
992     if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
993       len = SIZE_OP_JUMP;
994     }
995     else {
996       len = tlen * qn->lower;
997     }
998 
999     if (qn->greedy) {
1000       if (IS_NOT_NULL(qn->head_exact))
1001 	len += SIZE_OP_PUSH_OR_JUMP_EXACT1 + mod_tlen + SIZE_OP_JUMP;
1002       else if (IS_NOT_NULL(qn->next_head_exact))
1003 	len += SIZE_OP_PUSH_IF_PEEK_NEXT + mod_tlen + SIZE_OP_JUMP;
1004       else
1005 	len += SIZE_OP_PUSH + mod_tlen + SIZE_OP_JUMP;
1006     }
1007     else
1008       len += SIZE_OP_JUMP + mod_tlen + SIZE_OP_PUSH;
1009   }
1010   else if (qn->upper == 0 && qn->is_refered != 0) { /* /(?<n>..){0}/ */
1011     len = SIZE_OP_JUMP + tlen;
1012   }
1013   else if (!infinite && qn->greedy &&
1014            (qn->upper == 1 || (tlen + SIZE_OP_PUSH) * qn->upper
1015                                       <= QUANTIFIER_EXPAND_LIMIT_SIZE)) {
1016     len = tlen * qn->lower;
1017     len += (SIZE_OP_PUSH + tlen) * (qn->upper - qn->lower);
1018   }
1019   else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) { /* '??' */
1020     len = SIZE_OP_PUSH + SIZE_OP_JUMP + tlen;
1021   }
1022   else {
1023     len = SIZE_OP_REPEAT_INC
1024         + mod_tlen + SIZE_OPCODE + SIZE_RELADDR + SIZE_MEMNUM;
1025   }
1026 
1027   return len;
1028 }
1029 
1030 static int
compile_quantifier_node(QtfrNode * qn,regex_t * reg)1031 compile_quantifier_node(QtfrNode* qn, regex_t* reg)
1032 {
1033   int i, r, mod_tlen;
1034   int infinite = IS_REPEAT_INFINITE(qn->upper);
1035   int empty_info = qn->target_empty_info;
1036   int tlen = compile_length_tree(qn->target, reg);
1037 
1038   if (tlen < 0) return tlen;
1039 
1040   if (is_anychar_star_quantifier(qn)) {
1041     r = compile_tree_n_times(qn->target, qn->lower, reg);
1042     if (r) return r;
1043     if (IS_NOT_NULL(qn->next_head_exact)) {
1044       if (IS_MULTILINE(reg->options))
1045 	r = add_opcode(reg, OP_ANYCHAR_ML_STAR_PEEK_NEXT);
1046       else
1047 	r = add_opcode(reg, OP_ANYCHAR_STAR_PEEK_NEXT);
1048       if (r) return r;
1049       return add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
1050     }
1051     else {
1052       if (IS_MULTILINE(reg->options))
1053 	return add_opcode(reg, OP_ANYCHAR_ML_STAR);
1054       else
1055 	return add_opcode(reg, OP_ANYCHAR_STAR);
1056     }
1057   }
1058 
1059   if (empty_info != 0)
1060     mod_tlen = tlen + (SIZE_OP_NULL_CHECK_START + SIZE_OP_NULL_CHECK_END);
1061   else
1062     mod_tlen = tlen;
1063 
1064   if (infinite &&
1065       (qn->lower <= 1 || tlen * qn->lower <= QUANTIFIER_EXPAND_LIMIT_SIZE)) {
1066     if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
1067       if (qn->greedy) {
1068 	if (IS_NOT_NULL(qn->head_exact))
1069 	  r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH_OR_JUMP_EXACT1);
1070 	else if (IS_NOT_NULL(qn->next_head_exact))
1071 	  r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH_IF_PEEK_NEXT);
1072 	else
1073 	  r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_PUSH);
1074       }
1075       else {
1076 	r = add_opcode_rel_addr(reg, OP_JUMP, SIZE_OP_JUMP);
1077       }
1078       if (r) return r;
1079     }
1080     else {
1081       r = compile_tree_n_times(qn->target, qn->lower, reg);
1082       if (r) return r;
1083     }
1084 
1085     if (qn->greedy) {
1086       if (IS_NOT_NULL(qn->head_exact)) {
1087 	r = add_opcode_rel_addr(reg, OP_PUSH_OR_JUMP_EXACT1,
1088 			     mod_tlen + SIZE_OP_JUMP);
1089 	if (r) return r;
1090 	add_bytes(reg, NSTR(qn->head_exact)->s, 1);
1091 	r = compile_tree_empty_check(qn->target, reg, empty_info);
1092 	if (r) return r;
1093 	r = add_opcode_rel_addr(reg, OP_JUMP,
1094 	-(mod_tlen + (int )SIZE_OP_JUMP + (int )SIZE_OP_PUSH_OR_JUMP_EXACT1));
1095       }
1096       else if (IS_NOT_NULL(qn->next_head_exact)) {
1097 	r = add_opcode_rel_addr(reg, OP_PUSH_IF_PEEK_NEXT,
1098 				mod_tlen + SIZE_OP_JUMP);
1099 	if (r) return r;
1100 	add_bytes(reg, NSTR(qn->next_head_exact)->s, 1);
1101 	r = compile_tree_empty_check(qn->target, reg, empty_info);
1102 	if (r) return r;
1103 	r = add_opcode_rel_addr(reg, OP_JUMP,
1104           -(mod_tlen + (int )SIZE_OP_JUMP + (int )SIZE_OP_PUSH_IF_PEEK_NEXT));
1105       }
1106       else {
1107 	r = add_opcode_rel_addr(reg, OP_PUSH, mod_tlen + SIZE_OP_JUMP);
1108 	if (r) return r;
1109 	r = compile_tree_empty_check(qn->target, reg, empty_info);
1110 	if (r) return r;
1111 	r = add_opcode_rel_addr(reg, OP_JUMP,
1112 		     -(mod_tlen + (int )SIZE_OP_JUMP + (int )SIZE_OP_PUSH));
1113       }
1114     }
1115     else {
1116       r = add_opcode_rel_addr(reg, OP_JUMP, mod_tlen);
1117       if (r) return r;
1118       r = compile_tree_empty_check(qn->target, reg, empty_info);
1119       if (r) return r;
1120       r = add_opcode_rel_addr(reg, OP_PUSH, -(mod_tlen + (int )SIZE_OP_PUSH));
1121     }
1122   }
1123   else if (qn->upper == 0 && qn->is_refered != 0) { /* /(?<n>..){0}/ */
1124     r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
1125     if (r) return r;
1126     r = compile_tree(qn->target, reg);
1127   }
1128   else if (!infinite && qn->greedy &&
1129            (qn->upper == 1 || (tlen + SIZE_OP_PUSH) * qn->upper
1130                                   <= QUANTIFIER_EXPAND_LIMIT_SIZE)) {
1131     int n = qn->upper - qn->lower;
1132 
1133     r = compile_tree_n_times(qn->target, qn->lower, reg);
1134     if (r) return r;
1135 
1136     for (i = 0; i < n; i++) {
1137       r = add_opcode_rel_addr(reg, OP_PUSH,
1138 			   (n - i) * tlen + (n - i - 1) * SIZE_OP_PUSH);
1139       if (r) return r;
1140       r = compile_tree(qn->target, reg);
1141       if (r) return r;
1142     }
1143   }
1144   else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) { /* '??' */
1145     r = add_opcode_rel_addr(reg, OP_PUSH, SIZE_OP_JUMP);
1146     if (r) return r;
1147     r = add_opcode_rel_addr(reg, OP_JUMP, tlen);
1148     if (r) return r;
1149     r = compile_tree(qn->target, reg);
1150   }
1151   else {
1152     r = compile_range_repeat_node(qn, mod_tlen, empty_info, reg);
1153   }
1154   return r;
1155 }
1156 #endif /* USE_COMBINATION_EXPLOSION_CHECK */
1157 
1158 static int
compile_length_option_node(EncloseNode * node,regex_t * reg)1159 compile_length_option_node(EncloseNode* node, regex_t* reg)
1160 {
1161   int tlen;
1162   OnigOptionType prev = reg->options;
1163 
1164   reg->options = node->option;
1165   tlen = compile_length_tree(node->target, reg);
1166   reg->options = prev;
1167 
1168   if (tlen < 0) return tlen;
1169 
1170   if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1171     return SIZE_OP_SET_OPTION_PUSH + SIZE_OP_SET_OPTION + SIZE_OP_FAIL
1172            + tlen + SIZE_OP_SET_OPTION;
1173   }
1174   else
1175     return tlen;
1176 }
1177 
1178 static int
compile_option_node(EncloseNode * node,regex_t * reg)1179 compile_option_node(EncloseNode* node, regex_t* reg)
1180 {
1181   int r;
1182   OnigOptionType prev = reg->options;
1183 
1184   if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1185     r = add_opcode_option(reg, OP_SET_OPTION_PUSH, node->option);
1186     if (r) return r;
1187     r = add_opcode_option(reg, OP_SET_OPTION, prev);
1188     if (r) return r;
1189     r = add_opcode(reg, OP_FAIL);
1190     if (r) return r;
1191   }
1192 
1193   reg->options = node->option;
1194   r = compile_tree(node->target, reg);
1195   reg->options = prev;
1196 
1197   if (IS_DYNAMIC_OPTION(prev ^ node->option)) {
1198     if (r) return r;
1199     r = add_opcode_option(reg, OP_SET_OPTION, prev);
1200   }
1201   return r;
1202 }
1203 
1204 static int
compile_length_enclose_node(EncloseNode * node,regex_t * reg)1205 compile_length_enclose_node(EncloseNode* node, regex_t* reg)
1206 {
1207   int len;
1208   int tlen;
1209 
1210   if (node->type == ENCLOSE_OPTION)
1211     return compile_length_option_node(node, reg);
1212 
1213   if (node->target) {
1214     tlen = compile_length_tree(node->target, reg);
1215     if (tlen < 0) return tlen;
1216   }
1217   else
1218     tlen = 0;
1219 
1220   switch (node->type) {
1221   case ENCLOSE_MEMORY:
1222 #ifdef USE_SUBEXP_CALL
1223     if (IS_ENCLOSE_CALLED(node)) {
1224       len = SIZE_OP_MEMORY_START_PUSH + tlen
1225 	  + SIZE_OP_CALL + SIZE_OP_JUMP + SIZE_OP_RETURN;
1226       if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1227 	len += (IS_ENCLOSE_RECURSION(node)
1228 		? SIZE_OP_MEMORY_END_PUSH_REC : SIZE_OP_MEMORY_END_PUSH);
1229       else
1230 	len += (IS_ENCLOSE_RECURSION(node)
1231 		? SIZE_OP_MEMORY_END_REC : SIZE_OP_MEMORY_END);
1232     }
1233     else
1234 #endif
1235     {
1236       if (BIT_STATUS_AT(reg->bt_mem_start, node->regnum))
1237 	len = SIZE_OP_MEMORY_START_PUSH;
1238       else
1239 	len = SIZE_OP_MEMORY_START;
1240 
1241       len += tlen + (BIT_STATUS_AT(reg->bt_mem_end, node->regnum)
1242 		     ? SIZE_OP_MEMORY_END_PUSH : SIZE_OP_MEMORY_END);
1243     }
1244     break;
1245 
1246   case ENCLOSE_STOP_BACKTRACK:
1247     if (IS_ENCLOSE_STOP_BT_SIMPLE_REPEAT(node)) {
1248       QtfrNode* qn = NQTFR(node->target);
1249       tlen = compile_length_tree(qn->target, reg);
1250       if (tlen < 0) return tlen;
1251 
1252       len = tlen * qn->lower
1253 	  + SIZE_OP_PUSH + tlen + SIZE_OP_POP + SIZE_OP_JUMP;
1254     }
1255     else {
1256       len = SIZE_OP_PUSH_STOP_BT + tlen + SIZE_OP_POP_STOP_BT;
1257     }
1258     break;
1259 
1260   default:
1261     return ONIGERR_TYPE_BUG;
1262     break;
1263   }
1264 
1265   return len;
1266 }
1267 
1268 static int get_char_length_tree(Node* node, regex_t* reg, int* len);
1269 
1270 static int
compile_enclose_node(EncloseNode * node,regex_t * reg)1271 compile_enclose_node(EncloseNode* node, regex_t* reg)
1272 {
1273   int r, len;
1274 
1275   if (node->type == ENCLOSE_OPTION)
1276     return compile_option_node(node, reg);
1277 
1278   switch (node->type) {
1279   case ENCLOSE_MEMORY:
1280 #ifdef USE_SUBEXP_CALL
1281     if (IS_ENCLOSE_CALLED(node)) {
1282       r = add_opcode(reg, OP_CALL);
1283       if (r) return r;
1284       node->call_addr = BBUF_GET_OFFSET_POS(reg) + SIZE_ABSADDR + SIZE_OP_JUMP;
1285       node->state |= NST_ADDR_FIXED;
1286       r = add_abs_addr(reg, (int )node->call_addr);
1287       if (r) return r;
1288       len = compile_length_tree(node->target, reg);
1289       len += (SIZE_OP_MEMORY_START_PUSH + SIZE_OP_RETURN);
1290       if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1291 	len += (IS_ENCLOSE_RECURSION(node)
1292 		? SIZE_OP_MEMORY_END_PUSH_REC : SIZE_OP_MEMORY_END_PUSH);
1293       else
1294 	len += (IS_ENCLOSE_RECURSION(node)
1295 		? SIZE_OP_MEMORY_END_REC : SIZE_OP_MEMORY_END);
1296 
1297       r = add_opcode_rel_addr(reg, OP_JUMP, len);
1298       if (r) return r;
1299     }
1300 #endif
1301     if (BIT_STATUS_AT(reg->bt_mem_start, node->regnum))
1302       r = add_opcode(reg, OP_MEMORY_START_PUSH);
1303     else
1304       r = add_opcode(reg, OP_MEMORY_START);
1305     if (r) return r;
1306     r = add_mem_num(reg, node->regnum);
1307     if (r) return r;
1308     r = compile_tree(node->target, reg);
1309     if (r) return r;
1310 #ifdef USE_SUBEXP_CALL
1311     if (IS_ENCLOSE_CALLED(node)) {
1312       if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1313 	r = add_opcode(reg, (IS_ENCLOSE_RECURSION(node)
1314 			     ? OP_MEMORY_END_PUSH_REC : OP_MEMORY_END_PUSH));
1315       else
1316 	r = add_opcode(reg, (IS_ENCLOSE_RECURSION(node)
1317 			     ? OP_MEMORY_END_REC : OP_MEMORY_END));
1318 
1319       if (r) return r;
1320       r = add_mem_num(reg, node->regnum);
1321       if (r) return r;
1322       r = add_opcode(reg, OP_RETURN);
1323     }
1324     else
1325 #endif
1326     {
1327       if (BIT_STATUS_AT(reg->bt_mem_end, node->regnum))
1328 	r = add_opcode(reg, OP_MEMORY_END_PUSH);
1329       else
1330 	r = add_opcode(reg, OP_MEMORY_END);
1331       if (r) return r;
1332       r = add_mem_num(reg, node->regnum);
1333     }
1334     break;
1335 
1336   case ENCLOSE_STOP_BACKTRACK:
1337     if (IS_ENCLOSE_STOP_BT_SIMPLE_REPEAT(node)) {
1338       QtfrNode* qn = NQTFR(node->target);
1339       r = compile_tree_n_times(qn->target, qn->lower, reg);
1340       if (r) return r;
1341 
1342       len = compile_length_tree(qn->target, reg);
1343       if (len < 0) return len;
1344 
1345       r = add_opcode_rel_addr(reg, OP_PUSH, len + SIZE_OP_POP + SIZE_OP_JUMP);
1346       if (r) return r;
1347       r = compile_tree(qn->target, reg);
1348       if (r) return r;
1349       r = add_opcode(reg, OP_POP);
1350       if (r) return r;
1351       r = add_opcode_rel_addr(reg, OP_JUMP,
1352 	 -((int )SIZE_OP_PUSH + len + (int )SIZE_OP_POP + (int )SIZE_OP_JUMP));
1353     }
1354     else {
1355       r = add_opcode(reg, OP_PUSH_STOP_BT);
1356       if (r) return r;
1357       r = compile_tree(node->target, reg);
1358       if (r) return r;
1359       r = add_opcode(reg, OP_POP_STOP_BT);
1360     }
1361     break;
1362 
1363   default:
1364     return ONIGERR_TYPE_BUG;
1365     break;
1366   }
1367 
1368   return r;
1369 }
1370 
1371 static int
compile_length_anchor_node(AnchorNode * node,regex_t * reg)1372 compile_length_anchor_node(AnchorNode* node, regex_t* reg)
1373 {
1374   int len;
1375   int tlen = 0;
1376 
1377   if (node->target) {
1378     tlen = compile_length_tree(node->target, reg);
1379     if (tlen < 0) return tlen;
1380   }
1381 
1382   switch (node->type) {
1383   case ANCHOR_PREC_READ:
1384     len = SIZE_OP_PUSH_POS + tlen + SIZE_OP_POP_POS;
1385     break;
1386   case ANCHOR_PREC_READ_NOT:
1387     len = SIZE_OP_PUSH_POS_NOT + tlen + SIZE_OP_FAIL_POS;
1388     break;
1389   case ANCHOR_LOOK_BEHIND:
1390     len = SIZE_OP_LOOK_BEHIND + tlen;
1391     break;
1392   case ANCHOR_LOOK_BEHIND_NOT:
1393     len = SIZE_OP_PUSH_LOOK_BEHIND_NOT + tlen + SIZE_OP_FAIL_LOOK_BEHIND_NOT;
1394     break;
1395 
1396   default:
1397     len = SIZE_OPCODE;
1398     break;
1399   }
1400 
1401   return len;
1402 }
1403 
1404 static int
compile_anchor_node(AnchorNode * node,regex_t * reg)1405 compile_anchor_node(AnchorNode* node, regex_t* reg)
1406 {
1407   int r, len;
1408 
1409   switch (node->type) {
1410   case ANCHOR_BEGIN_BUF:      r = add_opcode(reg, OP_BEGIN_BUF);      break;
1411   case ANCHOR_END_BUF:        r = add_opcode(reg, OP_END_BUF);        break;
1412   case ANCHOR_BEGIN_LINE:     r = add_opcode(reg, OP_BEGIN_LINE);     break;
1413   case ANCHOR_END_LINE:       r = add_opcode(reg, OP_END_LINE);       break;
1414   case ANCHOR_SEMI_END_BUF:   r = add_opcode(reg, OP_SEMI_END_BUF);   break;
1415   case ANCHOR_BEGIN_POSITION: r = add_opcode(reg, OP_BEGIN_POSITION); break;
1416 
1417   case ANCHOR_WORD_BOUND:     r = add_opcode(reg, OP_WORD_BOUND);     break;
1418   case ANCHOR_NOT_WORD_BOUND: r = add_opcode(reg, OP_NOT_WORD_BOUND); break;
1419 #ifdef USE_WORD_BEGIN_END
1420   case ANCHOR_WORD_BEGIN:     r = add_opcode(reg, OP_WORD_BEGIN);     break;
1421   case ANCHOR_WORD_END:       r = add_opcode(reg, OP_WORD_END);       break;
1422 #endif
1423 
1424   case ANCHOR_PREC_READ:
1425     r = add_opcode(reg, OP_PUSH_POS);
1426     if (r) return r;
1427     r = compile_tree(node->target, reg);
1428     if (r) return r;
1429     r = add_opcode(reg, OP_POP_POS);
1430     break;
1431 
1432   case ANCHOR_PREC_READ_NOT:
1433     len = compile_length_tree(node->target, reg);
1434     if (len < 0) return len;
1435     r = add_opcode_rel_addr(reg, OP_PUSH_POS_NOT, len + SIZE_OP_FAIL_POS);
1436     if (r) return r;
1437     r = compile_tree(node->target, reg);
1438     if (r) return r;
1439     r = add_opcode(reg, OP_FAIL_POS);
1440     break;
1441 
1442   case ANCHOR_LOOK_BEHIND:
1443     {
1444       int n;
1445       r = add_opcode(reg, OP_LOOK_BEHIND);
1446       if (r) return r;
1447       if (node->char_len < 0) {
1448 	r = get_char_length_tree(node->target, reg, &n);
1449 	if (r) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
1450       }
1451       else
1452 	n = node->char_len;
1453       r = add_length(reg, n);
1454       if (r) return r;
1455       r = compile_tree(node->target, reg);
1456     }
1457     break;
1458 
1459   case ANCHOR_LOOK_BEHIND_NOT:
1460     {
1461       int n;
1462       len = compile_length_tree(node->target, reg);
1463       r = add_opcode_rel_addr(reg, OP_PUSH_LOOK_BEHIND_NOT,
1464 			   len + SIZE_OP_FAIL_LOOK_BEHIND_NOT);
1465       if (r) return r;
1466       if (node->char_len < 0) {
1467 	r = get_char_length_tree(node->target, reg, &n);
1468 	if (r) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
1469       }
1470       else
1471 	n = node->char_len;
1472       r = add_length(reg, n);
1473       if (r) return r;
1474       r = compile_tree(node->target, reg);
1475       if (r) return r;
1476       r = add_opcode(reg, OP_FAIL_LOOK_BEHIND_NOT);
1477     }
1478     break;
1479 
1480   default:
1481     return ONIGERR_TYPE_BUG;
1482     break;
1483   }
1484 
1485   return r;
1486 }
1487 
1488 static int
compile_length_tree(Node * node,regex_t * reg)1489 compile_length_tree(Node* node, regex_t* reg)
1490 {
1491   int len, type, r;
1492 
1493   type = NTYPE(node);
1494   switch (type) {
1495   case NT_LIST:
1496     len = 0;
1497     do {
1498       r = compile_length_tree(NCAR(node), reg);
1499       if (r < 0) return r;
1500       len += r;
1501     } while (IS_NOT_NULL(node = NCDR(node)));
1502     r = len;
1503     break;
1504 
1505   case NT_ALT:
1506     {
1507       int n;
1508 
1509       n = r = 0;
1510       do {
1511 	r += compile_length_tree(NCAR(node), reg);
1512 	n++;
1513       } while (IS_NOT_NULL(node = NCDR(node)));
1514       r += (SIZE_OP_PUSH + SIZE_OP_JUMP) * (n - 1);
1515     }
1516     break;
1517 
1518   case NT_STR:
1519     if (NSTRING_IS_RAW(node))
1520       r = compile_length_string_raw_node(NSTR(node), reg);
1521     else
1522       r = compile_length_string_node(node, reg);
1523     break;
1524 
1525   case NT_CCLASS:
1526     r = compile_length_cclass_node(NCCLASS(node), reg);
1527     break;
1528 
1529   case NT_CTYPE:
1530   case NT_CANY:
1531     r = SIZE_OPCODE;
1532     break;
1533 
1534   case NT_BREF:
1535     {
1536       BRefNode* br = NBREF(node);
1537 
1538 #ifdef USE_BACKREF_WITH_LEVEL
1539       if (IS_BACKREF_NEST_LEVEL(br)) {
1540         r = SIZE_OPCODE + SIZE_OPTION + SIZE_LENGTH +
1541             SIZE_LENGTH + (SIZE_MEMNUM * br->back_num);
1542       }
1543       else
1544 #endif
1545       if (br->back_num == 1) {
1546 	r = ((!IS_IGNORECASE(reg->options) && br->back_static[0] <= 2)
1547 	     ? SIZE_OPCODE : (SIZE_OPCODE + SIZE_MEMNUM));
1548       }
1549       else {
1550 	r = SIZE_OPCODE + SIZE_LENGTH + (SIZE_MEMNUM * br->back_num);
1551       }
1552     }
1553     break;
1554 
1555 #ifdef USE_SUBEXP_CALL
1556   case NT_CALL:
1557     r = SIZE_OP_CALL;
1558     break;
1559 #endif
1560 
1561   case NT_QTFR:
1562     r = compile_length_quantifier_node(NQTFR(node), reg);
1563     break;
1564 
1565   case NT_ENCLOSE:
1566     r = compile_length_enclose_node(NENCLOSE(node), reg);
1567     break;
1568 
1569   case NT_ANCHOR:
1570     r = compile_length_anchor_node(NANCHOR(node), reg);
1571     break;
1572 
1573   default:
1574     return ONIGERR_TYPE_BUG;
1575     break;
1576   }
1577 
1578   return r;
1579 }
1580 
1581 static int
compile_tree(Node * node,regex_t * reg)1582 compile_tree(Node* node, regex_t* reg)
1583 {
1584   int n, type, len, pos, r = 0;
1585 
1586   type = NTYPE(node);
1587   switch (type) {
1588   case NT_LIST:
1589     do {
1590       r = compile_tree(NCAR(node), reg);
1591     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
1592     break;
1593 
1594   case NT_ALT:
1595     {
1596       Node* x = node;
1597       len = 0;
1598       do {
1599 	len += compile_length_tree(NCAR(x), reg);
1600 	if (NCDR(x) != NULL) {
1601 	  len += SIZE_OP_PUSH + SIZE_OP_JUMP;
1602 	}
1603       } while (IS_NOT_NULL(x = NCDR(x)));
1604       pos = reg->used + len;  /* goal position */
1605 
1606       do {
1607 	len = compile_length_tree(NCAR(node), reg);
1608 	if (IS_NOT_NULL(NCDR(node))) {
1609 	  r = add_opcode_rel_addr(reg, OP_PUSH, len + SIZE_OP_JUMP);
1610 	  if (r) break;
1611 	}
1612 	r = compile_tree(NCAR(node), reg);
1613 	if (r) break;
1614 	if (IS_NOT_NULL(NCDR(node))) {
1615 	  len = pos - (reg->used + SIZE_OP_JUMP);
1616 	  r = add_opcode_rel_addr(reg, OP_JUMP, len);
1617 	  if (r) break;
1618 	}
1619       } while (IS_NOT_NULL(node = NCDR(node)));
1620     }
1621     break;
1622 
1623   case NT_STR:
1624     if (NSTRING_IS_RAW(node))
1625       r = compile_string_raw_node(NSTR(node), reg);
1626     else
1627       r = compile_string_node(node, reg);
1628     break;
1629 
1630   case NT_CCLASS:
1631     r = compile_cclass_node(NCCLASS(node), reg);
1632     break;
1633 
1634   case NT_CTYPE:
1635     {
1636       int op;
1637 
1638       switch (NCTYPE(node)->ctype) {
1639       case ONIGENC_CTYPE_WORD:
1640 	if (NCTYPE(node)->not != 0)  op = OP_NOT_WORD;
1641 	else                         op = OP_WORD;
1642 	break;
1643       default:
1644 	return ONIGERR_TYPE_BUG;
1645 	break;
1646       }
1647       r = add_opcode(reg, op);
1648     }
1649     break;
1650 
1651   case NT_CANY:
1652     if (IS_MULTILINE(reg->options))
1653       r = add_opcode(reg, OP_ANYCHAR_ML);
1654     else
1655       r = add_opcode(reg, OP_ANYCHAR);
1656     break;
1657 
1658   case NT_BREF:
1659     {
1660       BRefNode* br = NBREF(node);
1661 
1662 #ifdef USE_BACKREF_WITH_LEVEL
1663       if (IS_BACKREF_NEST_LEVEL(br)) {
1664 	r = add_opcode(reg, OP_BACKREF_WITH_LEVEL);
1665 	if (r) return r;
1666 	r = add_option(reg, (reg->options & ONIG_OPTION_IGNORECASE));
1667 	if (r) return r;
1668 	r = add_length(reg, br->nest_level);
1669 	if (r) return r;
1670 
1671 	goto add_bacref_mems;
1672       }
1673       else
1674 #endif
1675       if (br->back_num == 1) {
1676 	n = br->back_static[0];
1677 	if (IS_IGNORECASE(reg->options)) {
1678 	  r = add_opcode(reg, OP_BACKREFN_IC);
1679 	  if (r) return r;
1680 	  r = add_mem_num(reg, n);
1681 	}
1682 	else {
1683 	  switch (n) {
1684 	  case 1:  r = add_opcode(reg, OP_BACKREF1); break;
1685 	  case 2:  r = add_opcode(reg, OP_BACKREF2); break;
1686 	  default:
1687 	    r = add_opcode(reg, OP_BACKREFN);
1688 	    if (r) return r;
1689 	    r = add_mem_num(reg, n);
1690 	    break;
1691 	  }
1692 	}
1693       }
1694       else {
1695 	int i;
1696 	int* p;
1697 
1698         if (IS_IGNORECASE(reg->options)) {
1699           r = add_opcode(reg, OP_BACKREF_MULTI_IC);
1700         }
1701         else {
1702           r = add_opcode(reg, OP_BACKREF_MULTI);
1703         }
1704 	if (r) return r;
1705 
1706 #ifdef USE_BACKREF_WITH_LEVEL
1707       add_bacref_mems:
1708 #endif
1709 	r = add_length(reg, br->back_num);
1710 	if (r) return r;
1711 	p = BACKREFS_P(br);
1712 	for (i = br->back_num - 1; i >= 0; i--) {
1713 	  r = add_mem_num(reg, p[i]);
1714 	  if (r) return r;
1715 	}
1716       }
1717     }
1718     break;
1719 
1720 #ifdef USE_SUBEXP_CALL
1721   case NT_CALL:
1722     r = compile_call(NCALL(node), reg);
1723     break;
1724 #endif
1725 
1726   case NT_QTFR:
1727     r = compile_quantifier_node(NQTFR(node), reg);
1728     break;
1729 
1730   case NT_ENCLOSE:
1731     r = compile_enclose_node(NENCLOSE(node), reg);
1732     break;
1733 
1734   case NT_ANCHOR:
1735     r = compile_anchor_node(NANCHOR(node), reg);
1736     break;
1737 
1738   default:
1739 #ifdef ONIG_DEBUG
1740     fprintf(stderr, "compile_tree: undefined node type %d\n", NTYPE(node));
1741 #endif
1742     break;
1743   }
1744 
1745   return r;
1746 }
1747 
1748 #ifdef USE_NAMED_GROUP
1749 
1750 static int
noname_disable_map(Node ** plink,GroupNumRemap * map,int * counter)1751 noname_disable_map(Node** plink, GroupNumRemap* map, int* counter)
1752 {
1753   int r = 0;
1754   Node* node = *plink;
1755 
1756   switch (NTYPE(node)) {
1757   case NT_LIST:
1758   case NT_ALT:
1759     do {
1760       r = noname_disable_map(&(NCAR(node)), map, counter);
1761     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
1762     break;
1763 
1764   case NT_QTFR:
1765     {
1766       Node** ptarget = &(NQTFR(node)->target);
1767       Node*  old = *ptarget;
1768       r = noname_disable_map(ptarget, map, counter);
1769       if (*ptarget != old && NTYPE(*ptarget) == NT_QTFR) {
1770 	onig_reduce_nested_quantifier(node, *ptarget);
1771       }
1772     }
1773     break;
1774 
1775   case NT_ENCLOSE:
1776     {
1777       EncloseNode* en = NENCLOSE(node);
1778       if (en->type == ENCLOSE_MEMORY) {
1779 	if (IS_ENCLOSE_NAMED_GROUP(en)) {
1780 	  (*counter)++;
1781 	  map[en->regnum].new_val = *counter;
1782 	  en->regnum = *counter;
1783 	  r = noname_disable_map(&(en->target), map, counter);
1784 	}
1785 	else {
1786 	  *plink = en->target;
1787 	  en->target = NULL_NODE;
1788 	  onig_node_free(node);
1789 	  r = noname_disable_map(plink, map, counter);
1790 	}
1791       }
1792       else
1793 	r = noname_disable_map(&(en->target), map, counter);
1794     }
1795     break;
1796 
1797   default:
1798     break;
1799   }
1800 
1801   return r;
1802 }
1803 
1804 static int
renumber_node_backref(Node * node,GroupNumRemap * map)1805 renumber_node_backref(Node* node, GroupNumRemap* map)
1806 {
1807   int i, pos, n, old_num;
1808   int *backs;
1809   BRefNode* bn = NBREF(node);
1810 
1811   if (! IS_BACKREF_NAME_REF(bn))
1812     return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
1813 
1814   old_num = bn->back_num;
1815   if (IS_NULL(bn->back_dynamic))
1816     backs = bn->back_static;
1817   else
1818     backs = bn->back_dynamic;
1819 
1820   for (i = 0, pos = 0; i < old_num; i++) {
1821     n = map[backs[i]].new_val;
1822     if (n > 0) {
1823       backs[pos] = n;
1824       pos++;
1825     }
1826   }
1827 
1828   bn->back_num = pos;
1829   return 0;
1830 }
1831 
1832 static int
renumber_by_map(Node * node,GroupNumRemap * map)1833 renumber_by_map(Node* node, GroupNumRemap* map)
1834 {
1835   int r = 0;
1836 
1837   switch (NTYPE(node)) {
1838   case NT_LIST:
1839   case NT_ALT:
1840     do {
1841       r = renumber_by_map(NCAR(node), map);
1842     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
1843     break;
1844   case NT_QTFR:
1845     r = renumber_by_map(NQTFR(node)->target, map);
1846     break;
1847   case NT_ENCLOSE:
1848     r = renumber_by_map(NENCLOSE(node)->target, map);
1849     break;
1850 
1851   case NT_BREF:
1852     r = renumber_node_backref(node, map);
1853     break;
1854 
1855   default:
1856     break;
1857   }
1858 
1859   return r;
1860 }
1861 
1862 static int
numbered_ref_check(Node * node)1863 numbered_ref_check(Node* node)
1864 {
1865   int r = 0;
1866 
1867   switch (NTYPE(node)) {
1868   case NT_LIST:
1869   case NT_ALT:
1870     do {
1871       r = numbered_ref_check(NCAR(node));
1872     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
1873     break;
1874   case NT_QTFR:
1875     r = numbered_ref_check(NQTFR(node)->target);
1876     break;
1877   case NT_ENCLOSE:
1878     r = numbered_ref_check(NENCLOSE(node)->target);
1879     break;
1880 
1881   case NT_BREF:
1882     if (! IS_BACKREF_NAME_REF(NBREF(node)))
1883       return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
1884     break;
1885 
1886   default:
1887     break;
1888   }
1889 
1890   return r;
1891 }
1892 
1893 static int
disable_noname_group_capture(Node ** root,regex_t * reg,ScanEnv * env)1894 disable_noname_group_capture(Node** root, regex_t* reg, ScanEnv* env)
1895 {
1896   int r, i, pos, counter;
1897   BitStatusType loc;
1898   GroupNumRemap* map;
1899 
1900   map = (GroupNumRemap* )xalloca(sizeof(GroupNumRemap) * (env->num_mem + 1));
1901   CHECK_NULL_RETURN_MEMERR(map);
1902   for (i = 1; i <= env->num_mem; i++) {
1903     map[i].new_val = 0;
1904   }
1905   counter = 0;
1906   r = noname_disable_map(root, map, &counter);
1907   if (r != 0) return r;
1908 
1909   r = renumber_by_map(*root, map);
1910   if (r != 0) return r;
1911 
1912   for (i = 1, pos = 1; i <= env->num_mem; i++) {
1913     if (map[i].new_val > 0) {
1914       SCANENV_MEM_NODES(env)[pos] = SCANENV_MEM_NODES(env)[i];
1915       pos++;
1916     }
1917   }
1918 
1919   loc = env->capture_history;
1920   BIT_STATUS_CLEAR(env->capture_history);
1921   for (i = 1; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
1922     if (BIT_STATUS_AT(loc, i)) {
1923       BIT_STATUS_ON_AT_SIMPLE(env->capture_history, map[i].new_val);
1924     }
1925   }
1926 
1927   env->num_mem = env->num_named;
1928   reg->num_mem = env->num_named;
1929 
1930   return onig_renumber_name_table(reg, map);
1931 }
1932 #endif /* USE_NAMED_GROUP */
1933 
1934 #ifdef USE_SUBEXP_CALL
1935 static int
unset_addr_list_fix(UnsetAddrList * uslist,regex_t * reg)1936 unset_addr_list_fix(UnsetAddrList* uslist, regex_t* reg)
1937 {
1938   int i, offset;
1939   EncloseNode* en;
1940   AbsAddrType addr;
1941 
1942   for (i = 0; i < uslist->num; i++) {
1943     en = NENCLOSE(uslist->us[i].target);
1944     if (! IS_ENCLOSE_ADDR_FIXED(en)) return ONIGERR_PARSER_BUG;
1945     addr = en->call_addr;
1946     offset = uslist->us[i].offset;
1947 
1948     BBUF_WRITE(reg, offset, &addr, SIZE_ABSADDR);
1949   }
1950   return 0;
1951 }
1952 #endif
1953 
1954 #ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
1955 static int
quantifiers_memory_node_info(Node * node)1956 quantifiers_memory_node_info(Node* node)
1957 {
1958   int r = 0;
1959 
1960   switch (NTYPE(node)) {
1961   case NT_LIST:
1962   case NT_ALT:
1963     {
1964       int v;
1965       do {
1966 	v = quantifiers_memory_node_info(NCAR(node));
1967 	if (v > r) r = v;
1968       } while (v >= 0 && IS_NOT_NULL(node = NCDR(node)));
1969     }
1970     break;
1971 
1972 #ifdef USE_SUBEXP_CALL
1973   case NT_CALL:
1974     if (IS_CALL_RECURSION(NCALL(node))) {
1975       return NQ_TARGET_IS_EMPTY_REC; /* tiny version */
1976     }
1977     else
1978       r = quantifiers_memory_node_info(NCALL(node)->target);
1979     break;
1980 #endif
1981 
1982   case NT_QTFR:
1983     {
1984       QtfrNode* qn = NQTFR(node);
1985       if (qn->upper != 0) {
1986 	r = quantifiers_memory_node_info(qn->target);
1987       }
1988     }
1989     break;
1990 
1991   case NT_ENCLOSE:
1992     {
1993       EncloseNode* en = NENCLOSE(node);
1994       switch (en->type) {
1995       case ENCLOSE_MEMORY:
1996 	return NQ_TARGET_IS_EMPTY_MEM;
1997 	break;
1998 
1999       case ENCLOSE_OPTION:
2000       case ENCLOSE_STOP_BACKTRACK:
2001 	r = quantifiers_memory_node_info(en->target);
2002 	break;
2003       default:
2004 	break;
2005       }
2006     }
2007     break;
2008 
2009   case NT_BREF:
2010   case NT_STR:
2011   case NT_CTYPE:
2012   case NT_CCLASS:
2013   case NT_CANY:
2014   case NT_ANCHOR:
2015   default:
2016     break;
2017   }
2018 
2019   return r;
2020 }
2021 #endif /* USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT */
2022 
2023 static int
get_min_match_length(Node * node,OnigDistance * min,ScanEnv * env)2024 get_min_match_length(Node* node, OnigDistance *min, ScanEnv* env)
2025 {
2026   OnigDistance tmin;
2027   int r = 0;
2028 
2029   *min = 0;
2030   switch (NTYPE(node)) {
2031   case NT_BREF:
2032     {
2033       int i;
2034       int* backs;
2035       Node** nodes = SCANENV_MEM_NODES(env);
2036       BRefNode* br = NBREF(node);
2037       if (br->state & NST_RECURSION) break;
2038 
2039       backs = BACKREFS_P(br);
2040       if (backs[0] > env->num_mem)  return ONIGERR_INVALID_BACKREF;
2041       r = get_min_match_length(nodes[backs[0]], min, env);
2042       if (r != 0) break;
2043       for (i = 1; i < br->back_num; i++) {
2044 	if (backs[i] > env->num_mem)  return ONIGERR_INVALID_BACKREF;
2045 	r = get_min_match_length(nodes[backs[i]], &tmin, env);
2046 	if (r != 0) break;
2047 	if (*min > tmin) *min = tmin;
2048       }
2049     }
2050     break;
2051 
2052 #ifdef USE_SUBEXP_CALL
2053   case NT_CALL:
2054     if (IS_CALL_RECURSION(NCALL(node))) {
2055       EncloseNode* en = NENCLOSE(NCALL(node)->target);
2056       if (IS_ENCLOSE_MIN_FIXED(en))
2057 	*min = en->min_len;
2058     }
2059     else
2060       r = get_min_match_length(NCALL(node)->target, min, env);
2061     break;
2062 #endif
2063 
2064   case NT_LIST:
2065     do {
2066       r = get_min_match_length(NCAR(node), &tmin, env);
2067       if (r == 0) *min += tmin;
2068     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2069     break;
2070 
2071   case NT_ALT:
2072     {
2073       Node *x, *y;
2074       y = node;
2075       do {
2076 	x = NCAR(y);
2077 	r = get_min_match_length(x, &tmin, env);
2078 	if (r != 0) break;
2079 	if (y == node) *min = tmin;
2080 	else if (*min > tmin) *min = tmin;
2081       } while (r == 0 && IS_NOT_NULL(y = NCDR(y)));
2082     }
2083     break;
2084 
2085   case NT_STR:
2086     {
2087       StrNode* sn = NSTR(node);
2088       *min = sn->end - sn->s;
2089     }
2090     break;
2091 
2092   case NT_CTYPE:
2093     *min = 1;
2094     break;
2095 
2096   case NT_CCLASS:
2097   case NT_CANY:
2098     *min = 1;
2099     break;
2100 
2101   case NT_QTFR:
2102     {
2103       QtfrNode* qn = NQTFR(node);
2104 
2105       if (qn->lower > 0) {
2106 	r = get_min_match_length(qn->target, min, env);
2107 	if (r == 0)
2108 	  *min = distance_multiply(*min, qn->lower);
2109       }
2110     }
2111     break;
2112 
2113   case NT_ENCLOSE:
2114     {
2115       EncloseNode* en = NENCLOSE(node);
2116       switch (en->type) {
2117       case ENCLOSE_MEMORY:
2118 #ifdef USE_SUBEXP_CALL
2119 	if (IS_ENCLOSE_MIN_FIXED(en))
2120 	  *min = en->min_len;
2121 	else {
2122 	  r = get_min_match_length(en->target, min, env);
2123 	  if (r == 0) {
2124 	    en->min_len = *min;
2125 	    SET_ENCLOSE_STATUS(node, NST_MIN_FIXED);
2126 	  }
2127 	}
2128 	break;
2129 #endif
2130       case ENCLOSE_OPTION:
2131       case ENCLOSE_STOP_BACKTRACK:
2132 	r = get_min_match_length(en->target, min, env);
2133 	break;
2134       }
2135     }
2136     break;
2137 
2138   case NT_ANCHOR:
2139   default:
2140     break;
2141   }
2142 
2143   return r;
2144 }
2145 
2146 static int
get_max_match_length(Node * node,OnigDistance * max,ScanEnv * env)2147 get_max_match_length(Node* node, OnigDistance *max, ScanEnv* env)
2148 {
2149   OnigDistance tmax;
2150   int r = 0;
2151 
2152   *max = 0;
2153   switch (NTYPE(node)) {
2154   case NT_LIST:
2155     do {
2156       r = get_max_match_length(NCAR(node), &tmax, env);
2157       if (r == 0)
2158 	*max = distance_add(*max, tmax);
2159     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2160     break;
2161 
2162   case NT_ALT:
2163     do {
2164       r = get_max_match_length(NCAR(node), &tmax, env);
2165       if (r == 0 && *max < tmax) *max = tmax;
2166     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2167     break;
2168 
2169   case NT_STR:
2170     {
2171       StrNode* sn = NSTR(node);
2172       *max = sn->end - sn->s;
2173     }
2174     break;
2175 
2176   case NT_CTYPE:
2177     *max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
2178     break;
2179 
2180   case NT_CCLASS:
2181   case NT_CANY:
2182     *max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
2183     break;
2184 
2185   case NT_BREF:
2186     {
2187       int i;
2188       int* backs;
2189       Node** nodes = SCANENV_MEM_NODES(env);
2190       BRefNode* br = NBREF(node);
2191       if (br->state & NST_RECURSION) {
2192 	*max = ONIG_INFINITE_DISTANCE;
2193 	break;
2194       }
2195       backs = BACKREFS_P(br);
2196       for (i = 0; i < br->back_num; i++) {
2197 	if (backs[i] > env->num_mem)  return ONIGERR_INVALID_BACKREF;
2198 	r = get_max_match_length(nodes[backs[i]], &tmax, env);
2199 	if (r != 0) break;
2200 	if (*max < tmax) *max = tmax;
2201       }
2202     }
2203     break;
2204 
2205 #ifdef USE_SUBEXP_CALL
2206   case NT_CALL:
2207     if (! IS_CALL_RECURSION(NCALL(node)))
2208       r = get_max_match_length(NCALL(node)->target, max, env);
2209     else
2210       *max = ONIG_INFINITE_DISTANCE;
2211     break;
2212 #endif
2213 
2214   case NT_QTFR:
2215     {
2216       QtfrNode* qn = NQTFR(node);
2217 
2218       if (qn->upper != 0) {
2219 	r = get_max_match_length(qn->target, max, env);
2220 	if (r == 0 && *max != 0) {
2221 	  if (! IS_REPEAT_INFINITE(qn->upper))
2222 	    *max = distance_multiply(*max, qn->upper);
2223 	  else
2224 	    *max = ONIG_INFINITE_DISTANCE;
2225 	}
2226       }
2227     }
2228     break;
2229 
2230   case NT_ENCLOSE:
2231     {
2232       EncloseNode* en = NENCLOSE(node);
2233       switch (en->type) {
2234       case ENCLOSE_MEMORY:
2235 #ifdef USE_SUBEXP_CALL
2236 	if (IS_ENCLOSE_MAX_FIXED(en))
2237 	  *max = en->max_len;
2238 	else {
2239 	  r = get_max_match_length(en->target, max, env);
2240 	  if (r == 0) {
2241 	    en->max_len = *max;
2242 	    SET_ENCLOSE_STATUS(node, NST_MAX_FIXED);
2243 	  }
2244 	}
2245 	break;
2246 #endif
2247       case ENCLOSE_OPTION:
2248       case ENCLOSE_STOP_BACKTRACK:
2249 	r = get_max_match_length(en->target, max, env);
2250 	break;
2251       }
2252     }
2253     break;
2254 
2255   case NT_ANCHOR:
2256   default:
2257     break;
2258   }
2259 
2260   return r;
2261 }
2262 
2263 #define GET_CHAR_LEN_VARLEN           -1
2264 #define GET_CHAR_LEN_TOP_ALT_VARLEN   -2
2265 
2266 /* fixed size pattern node only */
2267 static int
get_char_length_tree1(Node * node,regex_t * reg,int * len,int level)2268 get_char_length_tree1(Node* node, regex_t* reg, int* len, int level)
2269 {
2270   int tlen;
2271   int r = 0;
2272 
2273   level++;
2274   *len = 0;
2275   switch (NTYPE(node)) {
2276   case NT_LIST:
2277     do {
2278       r = get_char_length_tree1(NCAR(node), reg, &tlen, level);
2279       if (r == 0)
2280 	*len = distance_add(*len, tlen);
2281     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2282     break;
2283 
2284   case NT_ALT:
2285     {
2286       int tlen2;
2287       int varlen = 0;
2288 
2289       r = get_char_length_tree1(NCAR(node), reg, &tlen, level);
2290       while (r == 0 && IS_NOT_NULL(node = NCDR(node))) {
2291 	r = get_char_length_tree1(NCAR(node), reg, &tlen2, level);
2292 	if (r == 0) {
2293 	  if (tlen != tlen2)
2294 	    varlen = 1;
2295 	}
2296       }
2297       if (r == 0) {
2298 	if (varlen != 0) {
2299 	  if (level == 1)
2300 	    r = GET_CHAR_LEN_TOP_ALT_VARLEN;
2301 	  else
2302 	    r = GET_CHAR_LEN_VARLEN;
2303 	}
2304 	else
2305 	  *len = tlen;
2306       }
2307     }
2308     break;
2309 
2310   case NT_STR:
2311     {
2312       StrNode* sn = NSTR(node);
2313       UChar *s = sn->s;
2314       while (s < sn->end) {
2315 	s += enclen(reg->enc, s);
2316 	(*len)++;
2317       }
2318     }
2319     break;
2320 
2321   case NT_QTFR:
2322     {
2323       QtfrNode* qn = NQTFR(node);
2324       if (qn->lower == qn->upper) {
2325 	r = get_char_length_tree1(qn->target, reg, &tlen, level);
2326 	if (r == 0)
2327 	  *len = distance_multiply(tlen, qn->lower);
2328       }
2329       else
2330 	r = GET_CHAR_LEN_VARLEN;
2331     }
2332     break;
2333 
2334 #ifdef USE_SUBEXP_CALL
2335   case NT_CALL:
2336     if (! IS_CALL_RECURSION(NCALL(node)))
2337       r = get_char_length_tree1(NCALL(node)->target, reg, len, level);
2338     else
2339       r = GET_CHAR_LEN_VARLEN;
2340     break;
2341 #endif
2342 
2343   case NT_CTYPE:
2344     *len = 1;
2345     break;
2346 
2347   case NT_CCLASS:
2348   case NT_CANY:
2349     *len = 1;
2350     break;
2351 
2352   case NT_ENCLOSE:
2353     {
2354       EncloseNode* en = NENCLOSE(node);
2355       switch (en->type) {
2356       case ENCLOSE_MEMORY:
2357 #ifdef USE_SUBEXP_CALL
2358 	if (IS_ENCLOSE_CLEN_FIXED(en))
2359 	  *len = en->char_len;
2360 	else {
2361 	  r = get_char_length_tree1(en->target, reg, len, level);
2362 	  if (r == 0) {
2363 	    en->char_len = *len;
2364 	    SET_ENCLOSE_STATUS(node, NST_CLEN_FIXED);
2365 	  }
2366 	}
2367 	break;
2368 #endif
2369       case ENCLOSE_OPTION:
2370       case ENCLOSE_STOP_BACKTRACK:
2371 	r = get_char_length_tree1(en->target, reg, len, level);
2372 	break;
2373       default:
2374 	break;
2375       }
2376     }
2377     break;
2378 
2379   case NT_ANCHOR:
2380     break;
2381 
2382   default:
2383     r = GET_CHAR_LEN_VARLEN;
2384     break;
2385   }
2386 
2387   return r;
2388 }
2389 
2390 static int
get_char_length_tree(Node * node,regex_t * reg,int * len)2391 get_char_length_tree(Node* node, regex_t* reg, int* len)
2392 {
2393   return get_char_length_tree1(node, reg, len, 0);
2394 }
2395 
2396 /* x is not included y ==>  1 : 0 */
2397 static int
is_not_included(Node * x,Node * y,regex_t * reg)2398 is_not_included(Node* x, Node* y, regex_t* reg)
2399 {
2400   int i, len;
2401   OnigCodePoint code;
2402   UChar *p;
2403   int ytype;
2404 
2405  retry:
2406   ytype = NTYPE(y);
2407   switch (NTYPE(x)) {
2408   case NT_CTYPE:
2409     {
2410       switch (ytype) {
2411       case NT_CTYPE:
2412 	if (NCTYPE(y)->ctype == NCTYPE(x)->ctype &&
2413 	    NCTYPE(y)->not   != NCTYPE(x)->not)
2414 	  return 1;
2415 	else
2416 	  return 0;
2417 	break;
2418 
2419       case NT_CCLASS:
2420       swap:
2421 	{
2422 	  Node* tmp;
2423 	  tmp = x; x = y; y = tmp;
2424 	  goto retry;
2425 	}
2426 	break;
2427 
2428       case NT_STR:
2429 	goto swap;
2430 	break;
2431 
2432       default:
2433 	break;
2434       }
2435     }
2436     break;
2437 
2438   case NT_CCLASS:
2439     {
2440       CClassNode* xc = NCCLASS(x);
2441       switch (ytype) {
2442       case NT_CTYPE:
2443 	switch (NCTYPE(y)->ctype) {
2444 	case ONIGENC_CTYPE_WORD:
2445 	  if (NCTYPE(y)->not == 0) {
2446 	    if (IS_NULL(xc->mbuf) && !IS_NCCLASS_NOT(xc)) {
2447 	      for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2448 		if (BITSET_AT(xc->bs, i)) {
2449 		  if (IS_CODE_SB_WORD(reg->enc, i)) return 0;
2450 		}
2451 	      }
2452 	      return 1;
2453 	    }
2454 	    return 0;
2455 	  }
2456 	  else {
2457 	    for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2458 	      if (! IS_CODE_SB_WORD(reg->enc, i)) {
2459 		if (!IS_NCCLASS_NOT(xc)) {
2460 		  if (BITSET_AT(xc->bs, i))
2461 		    return 0;
2462 		}
2463 		else {
2464 		  if (! BITSET_AT(xc->bs, i))
2465 		    return 0;
2466 		}
2467 	      }
2468 	    }
2469 	    return 1;
2470 	  }
2471 	  break;
2472 
2473 	default:
2474 	  break;
2475 	}
2476 	break;
2477 
2478       case NT_CCLASS:
2479 	{
2480 	  int v;
2481 	  CClassNode* yc = NCCLASS(y);
2482 
2483 	  for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
2484 	    v = BITSET_AT(xc->bs, i);
2485 	    if ((v != 0 && !IS_NCCLASS_NOT(xc)) ||
2486                 (v == 0 && IS_NCCLASS_NOT(xc))) {
2487 	      v = BITSET_AT(yc->bs, i);
2488 	      if ((v != 0 && !IS_NCCLASS_NOT(yc)) ||
2489                   (v == 0 && IS_NCCLASS_NOT(yc)))
2490 		return 0;
2491 	    }
2492 	  }
2493 	  if ((IS_NULL(xc->mbuf) && !IS_NCCLASS_NOT(xc)) ||
2494 	      (IS_NULL(yc->mbuf) && !IS_NCCLASS_NOT(yc)))
2495 	    return 1;
2496 	  return 0;
2497 	}
2498 	break;
2499 
2500       case NT_STR:
2501 	goto swap;
2502 	break;
2503 
2504       default:
2505 	break;
2506       }
2507     }
2508     break;
2509 
2510   case NT_STR:
2511     {
2512       StrNode* xs = NSTR(x);
2513       if (NSTRING_LEN(x) == 0)
2514 	break;
2515 
2516       //c = *(xs->s);
2517       switch (ytype) {
2518       case NT_CTYPE:
2519         switch (NCTYPE(y)->ctype) {
2520         case ONIGENC_CTYPE_WORD:
2521           if (ONIGENC_IS_MBC_WORD(reg->enc, xs->s, xs->end))
2522             return NCTYPE(y)->not;
2523           else
2524             return !(NCTYPE(y)->not);
2525           break;
2526         default:
2527           break;
2528         }
2529         break;
2530 
2531       case NT_CCLASS:
2532         {
2533           CClassNode* cc = NCCLASS(y);
2534 
2535           code = ONIGENC_MBC_TO_CODE(reg->enc, xs->s,
2536                                      xs->s + ONIGENC_MBC_MAXLEN(reg->enc));
2537           return (onig_is_code_in_cc(reg->enc, code, cc) != 0 ? 0 : 1);
2538         }
2539         break;
2540 
2541       case NT_STR:
2542         {
2543           UChar *q;
2544           StrNode* ys = NSTR(y);
2545           len = NSTRING_LEN(x);
2546           if (len > NSTRING_LEN(y)) len = NSTRING_LEN(y);
2547           if (NSTRING_IS_AMBIG(x) || NSTRING_IS_AMBIG(y)) {
2548             /* tiny version */
2549             return 0;
2550           }
2551           else {
2552             for (i = 0, p = ys->s, q = xs->s; i < len; i++, p++, q++) {
2553               if (*p != *q) return 1;
2554             }
2555           }
2556         }
2557         break;
2558 
2559       default:
2560         break;
2561       }
2562     }
2563     break;
2564 
2565   default:
2566     break;
2567   }
2568 
2569   return 0;
2570 }
2571 
2572 static Node*
get_head_value_node(Node * node,int exact,regex_t * reg)2573 get_head_value_node(Node* node, int exact, regex_t* reg)
2574 {
2575   Node* n = NULL_NODE;
2576 
2577   switch (NTYPE(node)) {
2578   case NT_BREF:
2579   case NT_ALT:
2580   case NT_CANY:
2581 #ifdef USE_SUBEXP_CALL
2582   case NT_CALL:
2583 #endif
2584     break;
2585 
2586   case NT_CTYPE:
2587   case NT_CCLASS:
2588     if (exact == 0) {
2589       n = node;
2590     }
2591     break;
2592 
2593   case NT_LIST:
2594     n = get_head_value_node(NCAR(node), exact, reg);
2595     break;
2596 
2597   case NT_STR:
2598     {
2599       StrNode* sn = NSTR(node);
2600 
2601       if (sn->end <= sn->s)
2602 	break;
2603 
2604       if (exact != 0 &&
2605 	  !NSTRING_IS_RAW(node) && IS_IGNORECASE(reg->options)) {
2606       }
2607       else {
2608 	n = node;
2609       }
2610     }
2611     break;
2612 
2613   case NT_QTFR:
2614     {
2615       QtfrNode* qn = NQTFR(node);
2616       if (qn->lower > 0) {
2617 	if (IS_NOT_NULL(qn->head_exact))
2618 	  n = qn->head_exact;
2619 	else
2620 	  n = get_head_value_node(qn->target, exact, reg);
2621       }
2622     }
2623     break;
2624 
2625   case NT_ENCLOSE:
2626     {
2627       EncloseNode* en = NENCLOSE(node);
2628       switch (en->type) {
2629       case ENCLOSE_OPTION:
2630 	{
2631 	  OnigOptionType options = reg->options;
2632 
2633 	  reg->options = NENCLOSE(node)->option;
2634 	  n = get_head_value_node(NENCLOSE(node)->target, exact, reg);
2635 	  reg->options = options;
2636 	}
2637 	break;
2638 
2639       case ENCLOSE_MEMORY:
2640       case ENCLOSE_STOP_BACKTRACK:
2641 	n = get_head_value_node(en->target, exact, reg);
2642 	break;
2643       }
2644     }
2645     break;
2646 
2647   case NT_ANCHOR:
2648     if (NANCHOR(node)->type == ANCHOR_PREC_READ)
2649       n = get_head_value_node(NANCHOR(node)->target, exact, reg);
2650     break;
2651 
2652   default:
2653     break;
2654   }
2655 
2656   return n;
2657 }
2658 
2659 static int
check_type_tree(Node * node,int type_mask,int enclose_mask,int anchor_mask)2660 check_type_tree(Node* node, int type_mask, int enclose_mask, int anchor_mask)
2661 {
2662   int type, r = 0;
2663 
2664   type = NTYPE(node);
2665   if ((NTYPE2BIT(type) & type_mask) == 0)
2666     return 1;
2667 
2668   switch (type) {
2669   case NT_LIST:
2670   case NT_ALT:
2671     do {
2672       r = check_type_tree(NCAR(node), type_mask, enclose_mask,
2673 			  anchor_mask);
2674     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2675     break;
2676 
2677   case NT_QTFR:
2678     r = check_type_tree(NQTFR(node)->target, type_mask, enclose_mask,
2679 			anchor_mask);
2680     break;
2681 
2682   case NT_ENCLOSE:
2683     {
2684       EncloseNode* en = NENCLOSE(node);
2685       if ((en->type & enclose_mask) == 0)
2686 	return 1;
2687 
2688       r = check_type_tree(en->target, type_mask, enclose_mask, anchor_mask);
2689     }
2690     break;
2691 
2692   case NT_ANCHOR:
2693     type = NANCHOR(node)->type;
2694     if ((type & anchor_mask) == 0)
2695       return 1;
2696 
2697     if (NANCHOR(node)->target)
2698       r = check_type_tree(NANCHOR(node)->target,
2699 			  type_mask, enclose_mask, anchor_mask);
2700     break;
2701 
2702   default:
2703     break;
2704   }
2705   return r;
2706 }
2707 
2708 #ifdef USE_SUBEXP_CALL
2709 
2710 #define RECURSION_EXIST       1
2711 #define RECURSION_INFINITE    2
2712 
2713 static int
subexp_inf_recursive_check(Node * node,ScanEnv * env,int head)2714 subexp_inf_recursive_check(Node* node, ScanEnv* env, int head)
2715 {
2716   int type;
2717   int r = 0;
2718 
2719   type = NTYPE(node);
2720   switch (type) {
2721   case NT_LIST:
2722     {
2723       Node *x;
2724       OnigDistance min;
2725       int ret;
2726 
2727       x = node;
2728       do {
2729 	ret = subexp_inf_recursive_check(NCAR(x), env, head);
2730 	if (ret < 0 || ret == RECURSION_INFINITE) return ret;
2731 	r |= ret;
2732 	if (head) {
2733 	  ret = get_min_match_length(NCAR(x), &min, env);
2734 	  if (ret != 0) return ret;
2735 	  if (min != 0) head = 0;
2736 	}
2737       } while (IS_NOT_NULL(x = NCDR(x)));
2738     }
2739     break;
2740 
2741   case NT_ALT:
2742     {
2743       int ret;
2744       r = RECURSION_EXIST;
2745       do {
2746 	ret = subexp_inf_recursive_check(NCAR(node), env, head);
2747 	if (ret < 0 || ret == RECURSION_INFINITE) return ret;
2748 	r &= ret;
2749       } while (IS_NOT_NULL(node = NCDR(node)));
2750     }
2751     break;
2752 
2753   case NT_QTFR:
2754     r = subexp_inf_recursive_check(NQTFR(node)->target, env, head);
2755     if (r == RECURSION_EXIST) {
2756       if (NQTFR(node)->lower == 0) r = 0;
2757     }
2758     break;
2759 
2760   case NT_ANCHOR:
2761     {
2762       AnchorNode* an = NANCHOR(node);
2763       switch (an->type) {
2764       case ANCHOR_PREC_READ:
2765       case ANCHOR_PREC_READ_NOT:
2766       case ANCHOR_LOOK_BEHIND:
2767       case ANCHOR_LOOK_BEHIND_NOT:
2768 	r = subexp_inf_recursive_check(an->target, env, head);
2769 	break;
2770       }
2771     }
2772     break;
2773 
2774   case NT_CALL:
2775     r = subexp_inf_recursive_check(NCALL(node)->target, env, head);
2776     break;
2777 
2778   case NT_ENCLOSE:
2779     if (IS_ENCLOSE_MARK2(NENCLOSE(node)))
2780       return 0;
2781     else if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
2782       return (head == 0 ? RECURSION_EXIST : RECURSION_INFINITE);
2783     else {
2784       SET_ENCLOSE_STATUS(node, NST_MARK2);
2785       r = subexp_inf_recursive_check(NENCLOSE(node)->target, env, head);
2786       CLEAR_ENCLOSE_STATUS(node, NST_MARK2);
2787     }
2788     break;
2789 
2790   default:
2791     break;
2792   }
2793 
2794   return r;
2795 }
2796 
2797 static int
subexp_inf_recursive_check_trav(Node * node,ScanEnv * env)2798 subexp_inf_recursive_check_trav(Node* node, ScanEnv* env)
2799 {
2800   int type;
2801   int r = 0;
2802 
2803   type = NTYPE(node);
2804   switch (type) {
2805   case NT_LIST:
2806   case NT_ALT:
2807     do {
2808       r = subexp_inf_recursive_check_trav(NCAR(node), env);
2809     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2810     break;
2811 
2812   case NT_QTFR:
2813     r = subexp_inf_recursive_check_trav(NQTFR(node)->target, env);
2814     break;
2815 
2816   case NT_ANCHOR:
2817     {
2818       AnchorNode* an = NANCHOR(node);
2819       switch (an->type) {
2820       case ANCHOR_PREC_READ:
2821       case ANCHOR_PREC_READ_NOT:
2822       case ANCHOR_LOOK_BEHIND:
2823       case ANCHOR_LOOK_BEHIND_NOT:
2824 	r = subexp_inf_recursive_check_trav(an->target, env);
2825 	break;
2826       }
2827     }
2828     break;
2829 
2830   case NT_ENCLOSE:
2831     {
2832       EncloseNode* en = NENCLOSE(node);
2833 
2834       if (IS_ENCLOSE_RECURSION(en)) {
2835 	SET_ENCLOSE_STATUS(node, NST_MARK1);
2836 	r = subexp_inf_recursive_check(en->target, env, 1);
2837 	if (r > 0) return ONIGERR_NEVER_ENDING_RECURSION;
2838 	CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
2839       }
2840       r = subexp_inf_recursive_check_trav(en->target, env);
2841     }
2842 
2843     break;
2844 
2845   default:
2846     break;
2847   }
2848 
2849   return r;
2850 }
2851 
2852 static int
subexp_recursive_check(Node * node)2853 subexp_recursive_check(Node* node)
2854 {
2855   int r = 0;
2856 
2857   switch (NTYPE(node)) {
2858   case NT_LIST:
2859   case NT_ALT:
2860     do {
2861       r |= subexp_recursive_check(NCAR(node));
2862     } while (IS_NOT_NULL(node = NCDR(node)));
2863     break;
2864 
2865   case NT_QTFR:
2866     r = subexp_recursive_check(NQTFR(node)->target);
2867     break;
2868 
2869   case NT_ANCHOR:
2870     {
2871       AnchorNode* an = NANCHOR(node);
2872       switch (an->type) {
2873       case ANCHOR_PREC_READ:
2874       case ANCHOR_PREC_READ_NOT:
2875       case ANCHOR_LOOK_BEHIND:
2876       case ANCHOR_LOOK_BEHIND_NOT:
2877 	r = subexp_recursive_check(an->target);
2878 	break;
2879       }
2880     }
2881     break;
2882 
2883   case NT_CALL:
2884     r = subexp_recursive_check(NCALL(node)->target);
2885     if (r != 0) SET_CALL_RECURSION(node);
2886     break;
2887 
2888   case NT_ENCLOSE:
2889     if (IS_ENCLOSE_MARK2(NENCLOSE(node)))
2890       return 0;
2891     else if (IS_ENCLOSE_MARK1(NENCLOSE(node)))
2892       return 1; /* recursion */
2893     else {
2894       SET_ENCLOSE_STATUS(node, NST_MARK2);
2895       r = subexp_recursive_check(NENCLOSE(node)->target);
2896       CLEAR_ENCLOSE_STATUS(node, NST_MARK2);
2897     }
2898     break;
2899 
2900   default:
2901     break;
2902   }
2903 
2904   return r;
2905 }
2906 
2907 
2908 static int
subexp_recursive_check_trav(Node * node,ScanEnv * env)2909 subexp_recursive_check_trav(Node* node, ScanEnv* env)
2910 {
2911 #define FOUND_CALLED_NODE    1
2912 
2913   int type;
2914   int r = 0;
2915 
2916   type = NTYPE(node);
2917   switch (type) {
2918   case NT_LIST:
2919   case NT_ALT:
2920     {
2921       int ret;
2922       do {
2923 	ret = subexp_recursive_check_trav(NCAR(node), env);
2924 	if (ret == FOUND_CALLED_NODE) r = FOUND_CALLED_NODE;
2925 	else if (ret < 0) return ret;
2926       } while (IS_NOT_NULL(node = NCDR(node)));
2927     }
2928     break;
2929 
2930   case NT_QTFR:
2931     r = subexp_recursive_check_trav(NQTFR(node)->target, env);
2932     if (NQTFR(node)->upper == 0) {
2933       if (r == FOUND_CALLED_NODE)
2934 	NQTFR(node)->is_refered = 1;
2935     }
2936     break;
2937 
2938   case NT_ANCHOR:
2939     {
2940       AnchorNode* an = NANCHOR(node);
2941       switch (an->type) {
2942       case ANCHOR_PREC_READ:
2943       case ANCHOR_PREC_READ_NOT:
2944       case ANCHOR_LOOK_BEHIND:
2945       case ANCHOR_LOOK_BEHIND_NOT:
2946 	r = subexp_recursive_check_trav(an->target, env);
2947 	break;
2948       }
2949     }
2950     break;
2951 
2952   case NT_ENCLOSE:
2953     {
2954       EncloseNode* en = NENCLOSE(node);
2955 
2956       if (! IS_ENCLOSE_RECURSION(en)) {
2957 	if (IS_ENCLOSE_CALLED(en)) {
2958 	  SET_ENCLOSE_STATUS(node, NST_MARK1);
2959 	  r = subexp_recursive_check(en->target);
2960 	  if (r != 0) SET_ENCLOSE_STATUS(node, NST_RECURSION);
2961 	  CLEAR_ENCLOSE_STATUS(node, NST_MARK1);
2962 	}
2963       }
2964       r = subexp_recursive_check_trav(en->target, env);
2965       if (IS_ENCLOSE_CALLED(en))
2966 	r |= FOUND_CALLED_NODE;
2967     }
2968     break;
2969 
2970   default:
2971     break;
2972   }
2973 
2974   return r;
2975 }
2976 
2977 static int
setup_subexp_call(Node * node,ScanEnv * env)2978 setup_subexp_call(Node* node, ScanEnv* env)
2979 {
2980   int type;
2981   int r = 0;
2982 
2983   type = NTYPE(node);
2984   switch (type) {
2985   case NT_LIST:
2986     do {
2987       r = setup_subexp_call(NCAR(node), env);
2988     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2989     break;
2990 
2991   case NT_ALT:
2992     do {
2993       r = setup_subexp_call(NCAR(node), env);
2994     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
2995     break;
2996 
2997   case NT_QTFR:
2998     r = setup_subexp_call(NQTFR(node)->target, env);
2999     break;
3000   case NT_ENCLOSE:
3001     r = setup_subexp_call(NENCLOSE(node)->target, env);
3002     break;
3003 
3004   case NT_CALL:
3005     {
3006       CallNode* cn = NCALL(node);
3007       Node** nodes = SCANENV_MEM_NODES(env);
3008 
3009       if (cn->group_num != 0) {
3010 	int gnum = cn->group_num;
3011 
3012 #ifdef USE_NAMED_GROUP
3013 	if (env->num_named > 0 &&
3014 	    IS_SYNTAX_BV(env->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
3015 	    !ONIG_IS_OPTION_ON(env->option, ONIG_OPTION_CAPTURE_GROUP)) {
3016 	  return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
3017 	}
3018 #endif
3019 	if (gnum > env->num_mem) {
3020 	  onig_scan_env_set_error_string(env,
3021 		 ONIGERR_UNDEFINED_GROUP_REFERENCE, cn->name, cn->name_end);
3022 	  return ONIGERR_UNDEFINED_GROUP_REFERENCE;
3023 	}
3024 
3025 #ifdef USE_NAMED_GROUP
3026       set_call_attr:
3027 #endif
3028 	cn->target = nodes[cn->group_num];
3029 	if (IS_NULL(cn->target)) {
3030 	  onig_scan_env_set_error_string(env,
3031 		 ONIGERR_UNDEFINED_NAME_REFERENCE, cn->name, cn->name_end);
3032 	  return ONIGERR_UNDEFINED_NAME_REFERENCE;
3033 	}
3034 	SET_ENCLOSE_STATUS(cn->target, NST_CALLED);
3035 	BIT_STATUS_ON_AT(env->bt_mem_start, cn->group_num);
3036 	cn->unset_addr_list = env->unset_addr_list;
3037       }
3038 #ifdef USE_NAMED_GROUP
3039       else {
3040 	int *refs;
3041 
3042 	int n = onig_name_to_group_numbers(env->reg, cn->name, cn->name_end,
3043 					   &refs);
3044 	if (n <= 0) {
3045 	  onig_scan_env_set_error_string(env,
3046 		 ONIGERR_UNDEFINED_NAME_REFERENCE, cn->name, cn->name_end);
3047 	  return ONIGERR_UNDEFINED_NAME_REFERENCE;
3048 	}
3049 	else if (n > 1) {
3050 	  onig_scan_env_set_error_string(env,
3051 	    ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL, cn->name, cn->name_end);
3052 	  return ONIGERR_MULTIPLEX_DEFINITION_NAME_CALL;
3053 	}
3054 	else {
3055 	  cn->group_num = refs[0];
3056 	  goto set_call_attr;
3057 	}
3058       }
3059 #endif
3060     }
3061     break;
3062 
3063   case NT_ANCHOR:
3064     {
3065       AnchorNode* an = NANCHOR(node);
3066 
3067       switch (an->type) {
3068       case ANCHOR_PREC_READ:
3069       case ANCHOR_PREC_READ_NOT:
3070       case ANCHOR_LOOK_BEHIND:
3071       case ANCHOR_LOOK_BEHIND_NOT:
3072 	r = setup_subexp_call(an->target, env);
3073 	break;
3074       }
3075     }
3076     break;
3077 
3078   default:
3079     break;
3080   }
3081 
3082   return r;
3083 }
3084 #endif
3085 
3086 /* divide different length alternatives in look-behind.
3087   (?<=A|B) ==> (?<=A)|(?<=B)
3088   (?<!A|B) ==> (?<!A)(?<!B)
3089 */
3090 static int
divide_look_behind_alternatives(Node * node)3091 divide_look_behind_alternatives(Node* node)
3092 {
3093   Node *head, *np, *insert_node;
3094   AnchorNode* an = NANCHOR(node);
3095   int anc_type = an->type;
3096 
3097   head = an->target;
3098   np = NCAR(head);
3099   swap_node(node, head);
3100   NCAR(node) = head;
3101   NANCHOR(head)->target = np;
3102 
3103   np = node;
3104   while ((np = NCDR(np)) != NULL_NODE) {
3105     insert_node = onig_node_new_anchor(anc_type);
3106     CHECK_NULL_RETURN_MEMERR(insert_node);
3107     NANCHOR(insert_node)->target = NCAR(np);
3108     NCAR(np) = insert_node;
3109   }
3110 
3111   if (anc_type == ANCHOR_LOOK_BEHIND_NOT) {
3112     np = node;
3113     do {
3114       SET_NTYPE(np, NT_LIST);  /* alt -> list */
3115     } while ((np = NCDR(np)) != NULL_NODE);
3116   }
3117   return 0;
3118 }
3119 
3120 static int
setup_look_behind(Node * node,regex_t * reg,ScanEnv * env)3121 setup_look_behind(Node* node, regex_t* reg, ScanEnv* env)
3122 {
3123   int r, len;
3124   AnchorNode* an = NANCHOR(node);
3125 
3126   r = get_char_length_tree(an->target, reg, &len);
3127   if (r == 0)
3128     an->char_len = len;
3129   else if (r == GET_CHAR_LEN_VARLEN)
3130     r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
3131   else if (r == GET_CHAR_LEN_TOP_ALT_VARLEN) {
3132     if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND))
3133       r = divide_look_behind_alternatives(node);
3134     else
3135       r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
3136   }
3137 
3138   return r;
3139 }
3140 
3141 static int
next_setup(Node * node,Node * next_node,regex_t * reg)3142 next_setup(Node* node, Node* next_node, regex_t* reg)
3143 {
3144   int type;
3145 
3146  retry:
3147   type = NTYPE(node);
3148   if (type == NT_QTFR) {
3149     QtfrNode* qn = NQTFR(node);
3150     if (qn->greedy && IS_REPEAT_INFINITE(qn->upper)) {
3151 #ifdef USE_QTFR_PEEK_NEXT
3152       Node* n = get_head_value_node(next_node, 1, reg);
3153       /* '\0': for UTF-16BE etc... */
3154       if (IS_NOT_NULL(n) && NSTR(n)->s[0] != '\0') {
3155 	qn->next_head_exact = n;
3156       }
3157 #endif
3158       /* automatic posseivation a*b ==> (?>a*)b */
3159       if (qn->lower <= 1) {
3160 	int ttype = NTYPE(qn->target);
3161 	if (IS_NODE_TYPE_SIMPLE(ttype)) {
3162 	  Node *x, *y;
3163 	  x = get_head_value_node(qn->target, 0, reg);
3164 	  if (IS_NOT_NULL(x)) {
3165 	    y = get_head_value_node(next_node,  0, reg);
3166 	    if (IS_NOT_NULL(y) && is_not_included(x, y, reg)) {
3167 	      Node* en = onig_node_new_enclose(ENCLOSE_STOP_BACKTRACK);
3168 	      CHECK_NULL_RETURN_MEMERR(en);
3169 	      SET_ENCLOSE_STATUS(en, NST_STOP_BT_SIMPLE_REPEAT);
3170 	      swap_node(node, en);
3171 	      NENCLOSE(node)->target = en;
3172 	    }
3173 	  }
3174 	}
3175       }
3176     }
3177   }
3178   else if (type == NT_ENCLOSE) {
3179     EncloseNode* en = NENCLOSE(node);
3180     if (en->type == ENCLOSE_MEMORY) {
3181       node = en->target;
3182       goto retry;
3183     }
3184   }
3185   return 0;
3186 }
3187 
3188 
3189 static int
update_string_node_case_fold(regex_t * reg,Node * node)3190 update_string_node_case_fold(regex_t* reg, Node *node)
3191 {
3192   UChar *p, *end, buf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
3193   UChar *sbuf, *ebuf, *sp;
3194   int r, i, len, sbuf_size;
3195   StrNode* sn = NSTR(node);
3196 
3197   end = sn->end;
3198   sbuf_size = (end - sn->s) * 2;
3199   sbuf = (UChar* )xmalloc(sbuf_size);
3200   CHECK_NULL_RETURN_MEMERR(sbuf);
3201   ebuf = sbuf + sbuf_size;
3202 
3203   sp = sbuf;
3204   p = sn->s;
3205   while (p < end) {
3206     len = ONIGENC_MBC_CASE_FOLD(reg->enc, reg->case_fold_flag, &p, end, buf);
3207     for (i = 0; i < len; i++) {
3208       if (sp >= ebuf) {
3209         sbuf = (UChar* )xrealloc(sbuf, sbuf_size * 2);
3210         CHECK_NULL_RETURN_MEMERR(sbuf);
3211         sp = sbuf + sbuf_size;
3212         sbuf_size *= 2;
3213         ebuf = sbuf + sbuf_size;
3214       }
3215 
3216       *sp++ = buf[i];
3217     }
3218   }
3219 
3220   r = onig_node_str_set(node, sbuf, sp);
3221   if (r != 0) {
3222     xfree(sbuf);
3223     return r;
3224   }
3225 
3226   xfree(sbuf);
3227   return 0;
3228 }
3229 
3230 static int
expand_case_fold_make_rem_string(Node ** rnode,UChar * s,UChar * end,regex_t * reg)3231 expand_case_fold_make_rem_string(Node** rnode, UChar *s, UChar *end,
3232 				 regex_t* reg)
3233 {
3234   int r;
3235   Node *node;
3236 
3237   node = onig_node_new_str(s, end);
3238   if (IS_NULL(node)) return ONIGERR_MEMORY;
3239 
3240   r = update_string_node_case_fold(reg, node);
3241   if (r != 0) {
3242     onig_node_free(node);
3243     return r;
3244   }
3245 
3246   NSTRING_SET_AMBIG(node);
3247   NSTRING_SET_DONT_GET_OPT_INFO(node);
3248   *rnode = node;
3249   return 0;
3250 }
3251 
3252 static int
expand_case_fold_string_alt(int item_num,OnigCaseFoldCodeItem items[],UChar * p,int slen,UChar * end,regex_t * reg,Node ** rnode)3253 expand_case_fold_string_alt(int item_num, OnigCaseFoldCodeItem items[],
3254 			    UChar *p, int slen, UChar *end,
3255 			    regex_t* reg, Node **rnode)
3256 {
3257   int r, i, j, len, varlen;
3258   Node *anode, *var_anode, *snode, *xnode, *an;
3259   UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
3260 
3261   *rnode = var_anode = NULL_NODE;
3262 
3263   varlen = 0;
3264   for (i = 0; i < item_num; i++) {
3265     if (items[i].byte_len != slen) {
3266       varlen = 1;
3267       break;
3268     }
3269   }
3270 
3271   if (varlen != 0) {
3272     *rnode = var_anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3273     if (IS_NULL(var_anode)) return ONIGERR_MEMORY;
3274 
3275     xnode = onig_node_new_list(NULL, NULL);
3276     if (IS_NULL(xnode)) goto mem_err;
3277     NCAR(var_anode) = xnode;
3278 
3279     anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3280     if (IS_NULL(anode)) goto mem_err;
3281     NCAR(xnode) = anode;
3282   }
3283   else {
3284     *rnode = anode = onig_node_new_alt(NULL_NODE, NULL_NODE);
3285     if (IS_NULL(anode)) return ONIGERR_MEMORY;
3286   }
3287 
3288   snode = onig_node_new_str(p, p + slen);
3289   if (IS_NULL(snode)) goto mem_err;
3290 
3291   NCAR(anode) = snode;
3292 
3293   for (i = 0; i < item_num; i++) {
3294     snode = onig_node_new_str(NULL, NULL);
3295     if (IS_NULL(snode)) goto mem_err;
3296 
3297     for (j = 0; j < items[i].code_len; j++) {
3298       len = ONIGENC_CODE_TO_MBC(reg->enc, items[i].code[j], buf);
3299       if (len < 0) {
3300 	r = len;
3301 	goto mem_err2;
3302       }
3303 
3304       r = onig_node_str_cat(snode, buf, buf + len);
3305       if (r != 0) goto mem_err2;
3306     }
3307 
3308     an = onig_node_new_alt(NULL_NODE, NULL_NODE);
3309     if (IS_NULL(an)) {
3310       goto mem_err2;
3311     }
3312 
3313     if (items[i].byte_len != slen) {
3314       Node *rem;
3315       UChar *q = p + items[i].byte_len;
3316 
3317       if (q < end) {
3318         r = expand_case_fold_make_rem_string(&rem, q, end, reg);
3319         if (r != 0) {
3320           onig_node_free(an);
3321           goto mem_err2;
3322         }
3323 
3324         xnode = onig_node_list_add(NULL_NODE, snode);
3325         if (IS_NULL(xnode)) {
3326           onig_node_free(an);
3327           onig_node_free(rem);
3328           goto mem_err2;
3329         }
3330         if (IS_NULL(onig_node_list_add(xnode, rem))) {
3331           onig_node_free(an);
3332           onig_node_free(xnode);
3333           onig_node_free(rem);
3334           goto mem_err;
3335         }
3336 
3337         NCAR(an) = xnode;
3338       }
3339       else {
3340         NCAR(an) = snode;
3341       }
3342 
3343       NCDR(var_anode) = an;
3344       var_anode = an;
3345     }
3346     else {
3347       NCAR(an)     = snode;
3348       NCDR(anode) = an;
3349       anode = an;
3350     }
3351   }
3352 
3353   return varlen;
3354 
3355  mem_err2:
3356   onig_node_free(snode);
3357 
3358  mem_err:
3359   onig_node_free(*rnode);
3360 
3361   return ONIGERR_MEMORY;
3362 }
3363 
3364 static int
expand_case_fold_string(Node * node,regex_t * reg)3365 expand_case_fold_string(Node* node, regex_t* reg)
3366 {
3367 #define THRESHOLD_CASE_FOLD_ALT_FOR_EXPANSION  8
3368 
3369   int r, n, len, alt_num;
3370   UChar *start, *end, *p;
3371   Node *top_root, *root, *snode, *prev_node;
3372   OnigCaseFoldCodeItem items[ONIGENC_GET_CASE_FOLD_CODES_MAX_NUM];
3373   StrNode* sn = NSTR(node);
3374 
3375   if (NSTRING_IS_AMBIG(node)) return 0;
3376 
3377   start = sn->s;
3378   end   = sn->end;
3379   if (start >= end) return 0;
3380 
3381   r = 0;
3382   top_root = root = prev_node = snode = NULL_NODE;
3383   alt_num = 1;
3384   p = start;
3385   while (p < end) {
3386     n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(reg->enc, reg->case_fold_flag,
3387 					   p, end, items);
3388     if (n < 0) {
3389       r = n;
3390       goto err;
3391     }
3392 
3393 	SAFE_ENC_LEN(reg->enc, p, end, len);
3394 
3395     if (n == 0) {
3396       if (IS_NULL(snode)) {
3397 	if (IS_NULL(root) && IS_NOT_NULL(prev_node)) {
3398 	  top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3399 	  if (IS_NULL(root)) {
3400 	    onig_node_free(prev_node);
3401 	    goto mem_err;
3402 	  }
3403 	}
3404 
3405 	prev_node = snode = onig_node_new_str(NULL, NULL);
3406 	if (IS_NULL(snode)) goto mem_err;
3407 	if (IS_NOT_NULL(root)) {
3408 	  if (IS_NULL(onig_node_list_add(root, snode))) {
3409 	    onig_node_free(snode);
3410 	    goto mem_err;
3411 	  }
3412 	}
3413       }
3414 
3415       r = onig_node_str_cat(snode, p, p + len);
3416       if (r != 0) goto err;
3417     }
3418     else {
3419       alt_num *= (n + 1);
3420       if (alt_num > THRESHOLD_CASE_FOLD_ALT_FOR_EXPANSION) break;
3421 
3422       if (IS_NULL(root) && IS_NOT_NULL(prev_node)) {
3423 	top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3424 	if (IS_NULL(root)) {
3425 	  onig_node_free(prev_node);
3426 	  goto mem_err;
3427 	}
3428       }
3429 
3430       r = expand_case_fold_string_alt(n, items, p, len, end, reg, &prev_node);
3431       if (r < 0) goto mem_err;
3432       if (r == 1) {
3433 	if (IS_NULL(root)) {
3434 	  top_root = prev_node;
3435 	}
3436 	else {
3437 	  if (IS_NULL(onig_node_list_add(root, prev_node))) {
3438 	    onig_node_free(prev_node);
3439 	    goto mem_err;
3440 	  }
3441 	}
3442 
3443 	root = NCAR(prev_node);
3444       }
3445       else { /* r == 0 */
3446 	if (IS_NOT_NULL(root)) {
3447 	  if (IS_NULL(onig_node_list_add(root, prev_node))) {
3448 	    onig_node_free(prev_node);
3449 	    goto mem_err;
3450 	  }
3451 	}
3452       }
3453 
3454       snode = NULL_NODE;
3455     }
3456 
3457     p += len;
3458   }
3459 
3460   if (p < end) {
3461     Node *srem;
3462 
3463     r = expand_case_fold_make_rem_string(&srem, p, end, reg);
3464     if (r != 0) goto mem_err;
3465 
3466     if (IS_NOT_NULL(prev_node) && IS_NULL(root)) {
3467       top_root = root = onig_node_list_add(NULL_NODE, prev_node);
3468       if (IS_NULL(root)) {
3469 	onig_node_free(srem);
3470 	onig_node_free(prev_node);
3471 	goto mem_err;
3472       }
3473     }
3474 
3475     if (IS_NULL(root)) {
3476       prev_node = srem;
3477     }
3478     else {
3479       if (IS_NULL(onig_node_list_add(root, srem))) {
3480 	onig_node_free(srem);
3481 	goto mem_err;
3482       }
3483     }
3484   }
3485 
3486   /* ending */
3487   top_root = (IS_NOT_NULL(top_root) ? top_root : prev_node);
3488   swap_node(node, top_root);
3489   onig_node_free(top_root);
3490   return 0;
3491 
3492  mem_err:
3493   r = ONIGERR_MEMORY;
3494 
3495  err:
3496   onig_node_free(top_root);
3497   return r;
3498 }
3499 
3500 
3501 #ifdef USE_COMBINATION_EXPLOSION_CHECK
3502 
3503 #define CEC_THRES_NUM_BIG_REPEAT         512
3504 #define CEC_INFINITE_NUM          0x7fffffff
3505 
3506 #define CEC_IN_INFINITE_REPEAT    (1<<0)
3507 #define CEC_IN_FINITE_REPEAT      (1<<1)
3508 #define CEC_CONT_BIG_REPEAT       (1<<2)
3509 
3510 static int
setup_comb_exp_check(Node * node,int state,ScanEnv * env)3511 setup_comb_exp_check(Node* node, int state, ScanEnv* env)
3512 {
3513   int type;
3514   int r = state;
3515 
3516   type = NTYPE(node);
3517   switch (type) {
3518   case NT_LIST:
3519     {
3520       Node* prev = NULL_NODE;
3521       do {
3522 	r = setup_comb_exp_check(NCAR(node), r, env);
3523 	prev = NCAR(node);
3524       } while (r >= 0 && IS_NOT_NULL(node = NCDR(node)));
3525     }
3526     break;
3527 
3528   case NT_ALT:
3529     {
3530       int ret;
3531       do {
3532 	ret = setup_comb_exp_check(NCAR(node), state, env);
3533 	r |= ret;
3534       } while (ret >= 0 && IS_NOT_NULL(node = NCDR(node)));
3535     }
3536     break;
3537 
3538   case NT_QTFR:
3539     {
3540       int child_state = state;
3541       int add_state = 0;
3542       QtfrNode* qn = NQTFR(node);
3543       Node* target = qn->target;
3544       int var_num;
3545 
3546       if (! IS_REPEAT_INFINITE(qn->upper)) {
3547 	if (qn->upper > 1) {
3548 	  /* {0,1}, {1,1} are allowed */
3549 	  child_state |= CEC_IN_FINITE_REPEAT;
3550 
3551 	  /* check (a*){n,m}, (a+){n,m} => (a*){n,n}, (a+){n,n} */
3552 	  if (env->backrefed_mem == 0) {
3553 	    if (NTYPE(qn->target) == NT_ENCLOSE) {
3554 	      EncloseNode* en = NENCLOSE(qn->target);
3555 	      if (en->type == ENCLOSE_MEMORY) {
3556 		if (NTYPE(en->target) == NT_QTFR) {
3557 		  QtfrNode* q = NQTFR(en->target);
3558 		  if (IS_REPEAT_INFINITE(q->upper)
3559 		      && q->greedy == qn->greedy) {
3560 		    qn->upper = (qn->lower == 0 ? 1 : qn->lower);
3561 		    if (qn->upper == 1)
3562 		      child_state = state;
3563 		  }
3564 		}
3565 	      }
3566 	    }
3567 	  }
3568 	}
3569       }
3570 
3571       if (state & CEC_IN_FINITE_REPEAT) {
3572 	qn->comb_exp_check_num = -1;
3573       }
3574       else {
3575 	if (IS_REPEAT_INFINITE(qn->upper)) {
3576 	  var_num = CEC_INFINITE_NUM;
3577 	  child_state |= CEC_IN_INFINITE_REPEAT;
3578 	}
3579 	else {
3580 	  var_num = qn->upper - qn->lower;
3581 	}
3582 
3583 	if (var_num >= CEC_THRES_NUM_BIG_REPEAT)
3584 	  add_state |= CEC_CONT_BIG_REPEAT;
3585 
3586 	if (((state & CEC_IN_INFINITE_REPEAT) != 0 && var_num != 0) ||
3587 	    ((state & CEC_CONT_BIG_REPEAT) != 0 &&
3588 	     var_num >= CEC_THRES_NUM_BIG_REPEAT)) {
3589 	  if (qn->comb_exp_check_num == 0) {
3590 	    env->num_comb_exp_check++;
3591 	    qn->comb_exp_check_num = env->num_comb_exp_check;
3592 	    if (env->curr_max_regnum > env->comb_exp_max_regnum)
3593 	      env->comb_exp_max_regnum = env->curr_max_regnum;
3594 	  }
3595 	}
3596       }
3597 
3598       r = setup_comb_exp_check(target, child_state, env);
3599       r |= add_state;
3600     }
3601     break;
3602 
3603   case NT_ENCLOSE:
3604     {
3605       EncloseNode* en = NENCLOSE(node);
3606 
3607       switch (en->type) {
3608       case ENCLOSE_MEMORY:
3609 	{
3610 	  if (env->curr_max_regnum < en->regnum)
3611 	    env->curr_max_regnum = en->regnum;
3612 
3613 	  r = setup_comb_exp_check(en->target, state, env);
3614 	}
3615 	break;
3616 
3617       default:
3618 	r = setup_comb_exp_check(en->target, state, env);
3619 	break;
3620       }
3621     }
3622     break;
3623 
3624 #ifdef USE_SUBEXP_CALL
3625   case NT_CALL:
3626     if (IS_CALL_RECURSION(NCALL(node)))
3627       env->has_recursion = 1;
3628     else
3629       r = setup_comb_exp_check(NCALL(node)->target, state, env);
3630     break;
3631 #endif
3632 
3633   default:
3634     break;
3635   }
3636 
3637   return r;
3638 }
3639 #endif
3640 
3641 #define IN_ALT        (1<<0)
3642 #define IN_NOT        (1<<1)
3643 #define IN_REPEAT     (1<<2)
3644 #define IN_VAR_REPEAT (1<<3)
3645 
3646 /* setup_tree does the following work.
3647  1. check empty loop. (set qn->target_empty_info)
3648  2. expand ignore-case in char class.
3649  3. set memory status bit flags. (reg->mem_stats)
3650  4. set qn->head_exact for [push, exact] -> [push_or_jump_exact1, exact].
3651  5. find invalid patterns in look-behind.
3652  6. expand repeated string.
3653  */
3654 static int
setup_tree(Node * node,regex_t * reg,int state,ScanEnv * env)3655 setup_tree(Node* node, regex_t* reg, int state, ScanEnv* env)
3656 {
3657   int type;
3658   int r = 0;
3659 
3660   type = NTYPE(node);
3661   switch (type) {
3662   case NT_LIST:
3663     {
3664       Node* prev = NULL_NODE;
3665       do {
3666 	r = setup_tree(NCAR(node), reg, state, env);
3667 	if (IS_NOT_NULL(prev) && r == 0) {
3668 	  r = next_setup(prev, NCAR(node), reg);
3669 	}
3670 	prev = NCAR(node);
3671       } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3672     }
3673     break;
3674 
3675   case NT_ALT:
3676     do {
3677       r = setup_tree(NCAR(node), reg, (state | IN_ALT), env);
3678     } while (r == 0 && IS_NOT_NULL(node = NCDR(node)));
3679     break;
3680 
3681   case NT_CCLASS:
3682     break;
3683 
3684   case NT_STR:
3685     if (IS_IGNORECASE(reg->options) && !NSTRING_IS_RAW(node)) {
3686       r = expand_case_fold_string(node, reg);
3687     }
3688     break;
3689 
3690   case NT_CTYPE:
3691   case NT_CANY:
3692     break;
3693 
3694 #ifdef USE_SUBEXP_CALL
3695   case NT_CALL:
3696     break;
3697 #endif
3698 
3699   case NT_BREF:
3700     {
3701       int i;
3702       int* p;
3703       Node** nodes = SCANENV_MEM_NODES(env);
3704       BRefNode* br = NBREF(node);
3705       p = BACKREFS_P(br);
3706       for (i = 0; i < br->back_num; i++) {
3707 	if (p[i] > env->num_mem)  return ONIGERR_INVALID_BACKREF;
3708 	BIT_STATUS_ON_AT(env->backrefed_mem, p[i]);
3709 	BIT_STATUS_ON_AT(env->bt_mem_start, p[i]);
3710 #ifdef USE_BACKREF_WITH_LEVEL
3711 	if (IS_BACKREF_NEST_LEVEL(br)) {
3712 	  BIT_STATUS_ON_AT(env->bt_mem_end, p[i]);
3713 	}
3714 #endif
3715 	SET_ENCLOSE_STATUS(nodes[p[i]], NST_MEM_BACKREFED);
3716       }
3717     }
3718     break;
3719 
3720   case NT_QTFR:
3721     {
3722       OnigDistance d;
3723       QtfrNode* qn = NQTFR(node);
3724       Node* target = qn->target;
3725 
3726       if ((state & IN_REPEAT) != 0) {
3727         qn->state |= NST_IN_REPEAT;
3728       }
3729 
3730       if (IS_REPEAT_INFINITE(qn->upper) || qn->upper >= 1) {
3731 	r = get_min_match_length(target, &d, env);
3732 	if (r) break;
3733 	if (d == 0) {
3734 	  qn->target_empty_info = NQ_TARGET_IS_EMPTY;
3735 #ifdef USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT
3736 	  r = quantifiers_memory_node_info(target);
3737 	  if (r < 0) break;
3738 	  if (r > 0) {
3739 	    qn->target_empty_info = r;
3740 	  }
3741 #endif
3742 #if 0
3743 	  r = get_max_match_length(target, &d, env);
3744 	  if (r == 0 && d == 0) {
3745 	    /*  ()* ==> ()?, ()+ ==> ()  */
3746 	    qn->upper = 1;
3747 	    if (qn->lower > 1) qn->lower = 1;
3748 	    if (NTYPE(target) == NT_STR) {
3749 	      qn->upper = qn->lower = 0;  /* /(?:)+/ ==> // */
3750 	    }
3751 	  }
3752 #endif
3753 	}
3754       }
3755 
3756       state |= IN_REPEAT;
3757       if (qn->lower != qn->upper)
3758 	state |= IN_VAR_REPEAT;
3759       r = setup_tree(target, reg, state, env);
3760       if (r) break;
3761 
3762       /* expand string */
3763 #define EXPAND_STRING_MAX_LENGTH  100
3764       if (NTYPE(target) == NT_STR) {
3765 	if (!IS_REPEAT_INFINITE(qn->lower) && qn->lower == qn->upper &&
3766 	    qn->lower > 1 && qn->lower <= EXPAND_STRING_MAX_LENGTH) {
3767 	  int len = NSTRING_LEN(target);
3768 	  StrNode* sn = NSTR(target);
3769 
3770 	  if (len * qn->lower <= EXPAND_STRING_MAX_LENGTH) {
3771 	    int i, n = qn->lower;
3772 	    onig_node_conv_to_str_node(node, NSTR(target)->flag);
3773 	    for (i = 0; i < n; i++) {
3774 	      r = onig_node_str_cat(node, sn->s, sn->end);
3775 	      if (r) break;
3776 	    }
3777 	    onig_node_free(target);
3778 	    break; /* break case NT_QTFR: */
3779 	  }
3780 	}
3781       }
3782 
3783 #ifdef USE_OP_PUSH_OR_JUMP_EXACT
3784       if (qn->greedy && (qn->target_empty_info != 0)) {
3785 	if (NTYPE(target) == NT_QTFR) {
3786 	  QtfrNode* tqn = NQTFR(target);
3787 	  if (IS_NOT_NULL(tqn->head_exact)) {
3788 	    qn->head_exact  = tqn->head_exact;
3789 	    tqn->head_exact = NULL;
3790 	  }
3791 	}
3792 	else {
3793 	  qn->head_exact = get_head_value_node(qn->target, 1, reg);
3794 	}
3795       }
3796 #endif
3797     }
3798     break;
3799 
3800   case NT_ENCLOSE:
3801     {
3802       EncloseNode* en = NENCLOSE(node);
3803 
3804       switch (en->type) {
3805       case ENCLOSE_OPTION:
3806 	{
3807 	  OnigOptionType options = reg->options;
3808 	  reg->options = NENCLOSE(node)->option;
3809 	  r = setup_tree(NENCLOSE(node)->target, reg, state, env);
3810 	  reg->options = options;
3811 	}
3812 	break;
3813 
3814       case ENCLOSE_MEMORY:
3815 	if ((state & (IN_ALT | IN_NOT | IN_VAR_REPEAT)) != 0) {
3816 	  BIT_STATUS_ON_AT(env->bt_mem_start, en->regnum);
3817 	  /* SET_ENCLOSE_STATUS(node, NST_MEM_IN_ALT_NOT); */
3818 	}
3819         r = setup_tree(en->target, reg, state, env);
3820         break;
3821 
3822       case ENCLOSE_STOP_BACKTRACK:
3823 	{
3824 	  Node* target = en->target;
3825 	  r = setup_tree(target, reg, state, env);
3826 	  if (NTYPE(target) == NT_QTFR) {
3827 	    QtfrNode* tqn = NQTFR(target);
3828 	    if (IS_REPEAT_INFINITE(tqn->upper) && tqn->lower <= 1 &&
3829 		tqn->greedy != 0) {  /* (?>a*), a*+ etc... */
3830 	      int qtype = NTYPE(tqn->target);
3831 	      if (IS_NODE_TYPE_SIMPLE(qtype))
3832 		SET_ENCLOSE_STATUS(node, NST_STOP_BT_SIMPLE_REPEAT);
3833 	    }
3834 	  }
3835 	}
3836 	break;
3837       }
3838     }
3839     break;
3840 
3841   case NT_ANCHOR:
3842     {
3843       AnchorNode* an = NANCHOR(node);
3844 
3845       switch (an->type) {
3846       case ANCHOR_PREC_READ:
3847 	r = setup_tree(an->target, reg, state, env);
3848 	break;
3849       case ANCHOR_PREC_READ_NOT:
3850 	r = setup_tree(an->target, reg, (state | IN_NOT), env);
3851 	break;
3852 
3853 /* allowed node types in look-behind */
3854 #define ALLOWED_TYPE_IN_LB  \
3855   ( BIT_NT_LIST | BIT_NT_ALT | BIT_NT_STR | BIT_NT_CCLASS | BIT_NT_CTYPE | \
3856     BIT_NT_CANY | BIT_NT_ANCHOR | BIT_NT_ENCLOSE | BIT_NT_QTFR | BIT_NT_CALL )
3857 
3858 #define ALLOWED_ENCLOSE_IN_LB       ( ENCLOSE_MEMORY )
3859 #define ALLOWED_ENCLOSE_IN_LB_NOT   0
3860 
3861 #define ALLOWED_ANCHOR_IN_LB \
3862 ( ANCHOR_LOOK_BEHIND | ANCHOR_BEGIN_LINE | ANCHOR_END_LINE | ANCHOR_BEGIN_BUF | ANCHOR_BEGIN_POSITION )
3863 #define ALLOWED_ANCHOR_IN_LB_NOT \
3864 ( ANCHOR_LOOK_BEHIND | ANCHOR_LOOK_BEHIND_NOT | ANCHOR_BEGIN_LINE | ANCHOR_END_LINE | ANCHOR_BEGIN_BUF | ANCHOR_BEGIN_POSITION )
3865 
3866       case ANCHOR_LOOK_BEHIND:
3867 	{
3868 	  r = check_type_tree(an->target, ALLOWED_TYPE_IN_LB,
3869 			      ALLOWED_ENCLOSE_IN_LB, ALLOWED_ANCHOR_IN_LB);
3870 	  if (r < 0) return r;
3871 	  if (r > 0) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
3872 	  r = setup_look_behind(node, reg, env);
3873 	  if (r != 0) return r;
3874 	  r = setup_tree(an->target, reg, state, env);
3875 	}
3876 	break;
3877 
3878       case ANCHOR_LOOK_BEHIND_NOT:
3879 	{
3880 	  r = check_type_tree(an->target, ALLOWED_TYPE_IN_LB,
3881 		      ALLOWED_ENCLOSE_IN_LB_NOT, ALLOWED_ANCHOR_IN_LB_NOT);
3882 	  if (r < 0) return r;
3883 	  if (r > 0) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
3884 	  r = setup_look_behind(node, reg, env);
3885 	  if (r != 0) return r;
3886 	  r = setup_tree(an->target, reg, (state | IN_NOT), env);
3887 	}
3888 	break;
3889       }
3890     }
3891     break;
3892 
3893   default:
3894     break;
3895   }
3896 
3897   return r;
3898 }
3899 
3900 /* set skip map for Boyer-Moor search */
3901 static int
set_bm_skip(UChar * s,UChar * end,OnigEncoding enc ARG_UNUSED,UChar skip[],int ** int_skip)3902 set_bm_skip(UChar* s, UChar* end, OnigEncoding enc ARG_UNUSED,
3903 	    UChar skip[], int** int_skip)
3904 {
3905   int i, len;
3906 
3907   len = end - s;
3908   if (len < ONIG_CHAR_TABLE_SIZE) {
3909     for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) skip[i] = len;
3910 
3911     for (i = 0; i < len - 1; i++)
3912       skip[s[i]] = len - 1 - i;
3913   }
3914   else {
3915     if (IS_NULL(*int_skip)) {
3916       *int_skip = (int* )xmalloc(sizeof(int) * ONIG_CHAR_TABLE_SIZE);
3917       if (IS_NULL(*int_skip)) return ONIGERR_MEMORY;
3918     }
3919     for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) (*int_skip)[i] = len;
3920 
3921     for (i = 0; i < len - 1; i++)
3922       (*int_skip)[s[i]] = len - 1 - i;
3923   }
3924   return 0;
3925 }
3926 
3927 #define OPT_EXACT_MAXLEN   24
3928 
3929 typedef struct {
3930   OnigDistance min;  /* min byte length */
3931   OnigDistance max;  /* max byte length */
3932 } MinMaxLen;
3933 
3934 typedef struct {
3935   MinMaxLen        mmd;
3936   OnigEncoding     enc;
3937   OnigOptionType   options;
3938   OnigCaseFoldType case_fold_flag;
3939   ScanEnv*         scan_env;
3940 } OptEnv;
3941 
3942 typedef struct {
3943   int left_anchor;
3944   int right_anchor;
3945 } OptAncInfo;
3946 
3947 typedef struct {
3948   MinMaxLen  mmd; /* info position */
3949   OptAncInfo anc;
3950 
3951   int   reach_end;
3952   int   ignore_case;
3953   int   len;
3954   UChar s[OPT_EXACT_MAXLEN];
3955 } OptExactInfo;
3956 
3957 typedef struct {
3958   MinMaxLen mmd; /* info position */
3959   OptAncInfo anc;
3960 
3961   int   value;      /* weighted value */
3962   UChar map[ONIG_CHAR_TABLE_SIZE];
3963 } OptMapInfo;
3964 
3965 typedef struct {
3966   MinMaxLen    len;
3967 
3968   OptAncInfo   anc;
3969   OptExactInfo exb;    /* boundary */
3970   OptExactInfo exm;    /* middle */
3971   OptExactInfo expr;   /* prec read (?=...) */
3972 
3973   OptMapInfo   map;   /* boundary */
3974 } NodeOptInfo;
3975 
3976 
3977 static int
map_position_value(OnigEncoding enc,int i)3978 map_position_value(OnigEncoding enc, int i)
3979 {
3980   static const short int ByteValTable[] = {
3981      5,  1,  1,  1,  1,  1,  1,  1,  1, 10, 10,  1,  1, 10,  1,  1,
3982      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3983     12,  4,  7,  4,  4,  4,  4,  4,  4,  5,  5,  5,  5,  5,  5,  5,
3984      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  5,  5,  5,  5,
3985      5,  6,  6,  6,  6,  7,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3986      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  5,  6,  5,  5,  5,
3987      5,  6,  6,  6,  6,  7,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3988      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  5,  5,  5,  5,  1
3989   };
3990 
3991   if (i < (int )(sizeof(ByteValTable)/sizeof(ByteValTable[0]))) {
3992     if (i == 0 && ONIGENC_MBC_MINLEN(enc) > 1)
3993       return 20;
3994     else
3995       return (int )ByteValTable[i];
3996   }
3997   else
3998     return 4;   /* Take it easy. */
3999 }
4000 
4001 static int
distance_value(MinMaxLen * mm)4002 distance_value(MinMaxLen* mm)
4003 {
4004   /* 1000 / (min-max-dist + 1) */
4005   static const short int dist_vals[] = {
4006     1000,  500,  333,  250,  200,  167,  143,  125,  111,  100,
4007       91,   83,   77,   71,   67,   63,   59,   56,   53,   50,
4008       48,   45,   43,   42,   40,   38,   37,   36,   34,   33,
4009       32,   31,   30,   29,   29,   28,   27,   26,   26,   25,
4010       24,   24,   23,   23,   22,   22,   21,   21,   20,   20,
4011       20,   19,   19,   19,   18,   18,   18,   17,   17,   17,
4012       16,   16,   16,   16,   15,   15,   15,   15,   14,   14,
4013       14,   14,   14,   14,   13,   13,   13,   13,   13,   13,
4014       12,   12,   12,   12,   12,   12,   11,   11,   11,   11,
4015       11,   11,   11,   11,   11,   10,   10,   10,   10,   10
4016   };
4017 
4018   int d;
4019 
4020   if (mm->max == ONIG_INFINITE_DISTANCE) return 0;
4021 
4022   d = mm->max - mm->min;
4023   if (d < (int )(sizeof(dist_vals)/sizeof(dist_vals[0])))
4024     /* return dist_vals[d] * 16 / (mm->min + 12); */
4025     return (int )dist_vals[d];
4026   else
4027     return 1;
4028 }
4029 
4030 static int
comp_distance_value(MinMaxLen * d1,MinMaxLen * d2,int v1,int v2)4031 comp_distance_value(MinMaxLen* d1, MinMaxLen* d2, int v1, int v2)
4032 {
4033   if (v2 <= 0) return -1;
4034   if (v1 <= 0) return  1;
4035 
4036   v1 *= distance_value(d1);
4037   v2 *= distance_value(d2);
4038 
4039   if (v2 > v1) return  1;
4040   if (v2 < v1) return -1;
4041 
4042   if (d2->min < d1->min) return  1;
4043   if (d2->min > d1->min) return -1;
4044   return 0;
4045 }
4046 
4047 static int
is_equal_mml(MinMaxLen * a,MinMaxLen * b)4048 is_equal_mml(MinMaxLen* a, MinMaxLen* b)
4049 {
4050   return (a->min == b->min && a->max == b->max) ? 1 : 0;
4051 }
4052 
4053 
4054 static void
set_mml(MinMaxLen * mml,OnigDistance min,OnigDistance max)4055 set_mml(MinMaxLen* mml, OnigDistance min, OnigDistance max)
4056 {
4057   mml->min = min;
4058   mml->max = max;
4059 }
4060 
4061 static void
clear_mml(MinMaxLen * mml)4062 clear_mml(MinMaxLen* mml)
4063 {
4064   mml->min = mml->max = 0;
4065 }
4066 
4067 static void
copy_mml(MinMaxLen * to,MinMaxLen * from)4068 copy_mml(MinMaxLen* to, MinMaxLen* from)
4069 {
4070   to->min = from->min;
4071   to->max = from->max;
4072 }
4073 
4074 static void
add_mml(MinMaxLen * to,MinMaxLen * from)4075 add_mml(MinMaxLen* to, MinMaxLen* from)
4076 {
4077   to->min = distance_add(to->min, from->min);
4078   to->max = distance_add(to->max, from->max);
4079 }
4080 
4081 #if 0
4082 static void
4083 add_len_mml(MinMaxLen* to, OnigDistance len)
4084 {
4085   to->min = distance_add(to->min, len);
4086   to->max = distance_add(to->max, len);
4087 }
4088 #endif
4089 
4090 static void
alt_merge_mml(MinMaxLen * to,MinMaxLen * from)4091 alt_merge_mml(MinMaxLen* to, MinMaxLen* from)
4092 {
4093   if (to->min > from->min) to->min = from->min;
4094   if (to->max < from->max) to->max = from->max;
4095 }
4096 
4097 static void
copy_opt_env(OptEnv * to,OptEnv * from)4098 copy_opt_env(OptEnv* to, OptEnv* from)
4099 {
4100   *to = *from;
4101 }
4102 
4103 static void
clear_opt_anc_info(OptAncInfo * anc)4104 clear_opt_anc_info(OptAncInfo* anc)
4105 {
4106   anc->left_anchor  = 0;
4107   anc->right_anchor = 0;
4108 }
4109 
4110 static void
copy_opt_anc_info(OptAncInfo * to,OptAncInfo * from)4111 copy_opt_anc_info(OptAncInfo* to, OptAncInfo* from)
4112 {
4113   *to = *from;
4114 }
4115 
4116 static void
concat_opt_anc_info(OptAncInfo * to,OptAncInfo * left,OptAncInfo * right,OnigDistance left_len,OnigDistance right_len)4117 concat_opt_anc_info(OptAncInfo* to, OptAncInfo* left, OptAncInfo* right,
4118 		    OnigDistance left_len, OnigDistance right_len)
4119 {
4120   clear_opt_anc_info(to);
4121 
4122   to->left_anchor = left->left_anchor;
4123   if (left_len == 0) {
4124     to->left_anchor |= right->left_anchor;
4125   }
4126 
4127   to->right_anchor = right->right_anchor;
4128   if (right_len == 0) {
4129     to->right_anchor |= left->right_anchor;
4130   }
4131 }
4132 
4133 static int
is_left_anchor(int anc)4134 is_left_anchor(int anc)
4135 {
4136   if (anc == ANCHOR_END_BUF || anc == ANCHOR_SEMI_END_BUF ||
4137       anc == ANCHOR_END_LINE || anc == ANCHOR_PREC_READ ||
4138       anc == ANCHOR_PREC_READ_NOT)
4139     return 0;
4140 
4141   return 1;
4142 }
4143 
4144 static int
is_set_opt_anc_info(OptAncInfo * to,int anc)4145 is_set_opt_anc_info(OptAncInfo* to, int anc)
4146 {
4147   if ((to->left_anchor & anc) != 0) return 1;
4148 
4149   return ((to->right_anchor & anc) != 0 ? 1 : 0);
4150 }
4151 
4152 static void
add_opt_anc_info(OptAncInfo * to,int anc)4153 add_opt_anc_info(OptAncInfo* to, int anc)
4154 {
4155   if (is_left_anchor(anc))
4156     to->left_anchor |= anc;
4157   else
4158     to->right_anchor |= anc;
4159 }
4160 
4161 static void
remove_opt_anc_info(OptAncInfo * to,int anc)4162 remove_opt_anc_info(OptAncInfo* to, int anc)
4163 {
4164   if (is_left_anchor(anc))
4165     to->left_anchor &= ~anc;
4166   else
4167     to->right_anchor &= ~anc;
4168 }
4169 
4170 static void
alt_merge_opt_anc_info(OptAncInfo * to,OptAncInfo * add)4171 alt_merge_opt_anc_info(OptAncInfo* to, OptAncInfo* add)
4172 {
4173   to->left_anchor  &= add->left_anchor;
4174   to->right_anchor &= add->right_anchor;
4175 }
4176 
4177 static int
is_full_opt_exact_info(OptExactInfo * ex)4178 is_full_opt_exact_info(OptExactInfo* ex)
4179 {
4180   return (ex->len >= OPT_EXACT_MAXLEN ? 1 : 0);
4181 }
4182 
4183 static void
clear_opt_exact_info(OptExactInfo * ex)4184 clear_opt_exact_info(OptExactInfo* ex)
4185 {
4186   clear_mml(&ex->mmd);
4187   clear_opt_anc_info(&ex->anc);
4188   ex->reach_end   = 0;
4189   ex->ignore_case = 0;
4190   ex->len         = 0;
4191   ex->s[0]        = '\0';
4192 }
4193 
4194 static void
copy_opt_exact_info(OptExactInfo * to,OptExactInfo * from)4195 copy_opt_exact_info(OptExactInfo* to, OptExactInfo* from)
4196 {
4197   *to = *from;
4198 }
4199 
4200 static void
concat_opt_exact_info(OptExactInfo * to,OptExactInfo * add,OnigEncoding enc)4201 concat_opt_exact_info(OptExactInfo* to, OptExactInfo* add, OnigEncoding enc)
4202 {
4203   int i, j, len;
4204   UChar *p, *end;
4205   OptAncInfo tanc;
4206 
4207   if (! to->ignore_case && add->ignore_case) {
4208     if (to->len >= add->len) return ;  /* avoid */
4209 
4210     to->ignore_case = 1;
4211   }
4212 
4213   p = add->s;
4214   end = p + add->len;
4215   for (i = to->len; p < end; ) {
4216     len = enclen(enc, p);
4217     if (i + len > OPT_EXACT_MAXLEN) break;
4218     for (j = 0; j < len && p < end; j++)
4219       to->s[i++] = *p++;
4220   }
4221 
4222   to->len = i;
4223   to->reach_end = (p == end ? add->reach_end : 0);
4224 
4225   concat_opt_anc_info(&tanc, &to->anc, &add->anc, 1, 1);
4226   if (! to->reach_end) tanc.right_anchor = 0;
4227   copy_opt_anc_info(&to->anc, &tanc);
4228 }
4229 
4230 static void
concat_opt_exact_info_str(OptExactInfo * to,UChar * s,UChar * end,int raw ARG_UNUSED,OnigEncoding enc)4231 concat_opt_exact_info_str(OptExactInfo* to, UChar* s, UChar* end,
4232 			  int raw ARG_UNUSED, OnigEncoding enc)
4233 {
4234   int i, j, len;
4235   UChar *p;
4236 
4237   for (i = to->len, p = s; p < end && i < OPT_EXACT_MAXLEN; ) {
4238     len = enclen(enc, p);
4239     if (i + len > OPT_EXACT_MAXLEN) break;
4240     for (j = 0; j < len && p < end; j++)
4241       to->s[i++] = *p++;
4242   }
4243 
4244   to->len = i;
4245 }
4246 
4247 static void
alt_merge_opt_exact_info(OptExactInfo * to,OptExactInfo * add,OptEnv * env)4248 alt_merge_opt_exact_info(OptExactInfo* to, OptExactInfo* add, OptEnv* env)
4249 {
4250   int i, j, len;
4251 
4252   if (add->len == 0 || to->len == 0) {
4253     clear_opt_exact_info(to);
4254     return ;
4255   }
4256 
4257   if (! is_equal_mml(&to->mmd, &add->mmd)) {
4258     clear_opt_exact_info(to);
4259     return ;
4260   }
4261 
4262   for (i = 0; i < to->len && i < add->len; ) {
4263     if (to->s[i] != add->s[i]) break;
4264     len = enclen(env->enc, to->s + i);
4265 
4266     for (j = 1; j < len; j++) {
4267       if (to->s[i+j] != add->s[i+j]) break;
4268     }
4269     if (j < len) break;
4270     i += len;
4271   }
4272 
4273   if (! add->reach_end || i < add->len || i < to->len) {
4274     to->reach_end = 0;
4275   }
4276   to->len = i;
4277   to->ignore_case |= add->ignore_case;
4278 
4279   alt_merge_opt_anc_info(&to->anc, &add->anc);
4280   if (! to->reach_end) to->anc.right_anchor = 0;
4281 }
4282 
4283 static void
select_opt_exact_info(OnigEncoding enc,OptExactInfo * now,OptExactInfo * alt)4284 select_opt_exact_info(OnigEncoding enc, OptExactInfo* now, OptExactInfo* alt)
4285 {
4286   int v1, v2;
4287 
4288   v1 = now->len;
4289   v2 = alt->len;
4290 
4291   if (v2 == 0) {
4292     return ;
4293   }
4294   else if (v1 == 0) {
4295     copy_opt_exact_info(now, alt);
4296     return ;
4297   }
4298   else if (v1 <= 2 && v2 <= 2) {
4299     /* ByteValTable[x] is big value --> low price */
4300     v2 = map_position_value(enc, now->s[0]);
4301     v1 = map_position_value(enc, alt->s[0]);
4302 
4303     if (now->len > 1) v1 += 5;
4304     if (alt->len > 1) v2 += 5;
4305   }
4306 
4307   if (now->ignore_case == 0) v1 *= 2;
4308   if (alt->ignore_case == 0) v2 *= 2;
4309 
4310   if (comp_distance_value(&now->mmd, &alt->mmd, v1, v2) > 0)
4311     copy_opt_exact_info(now, alt);
4312 }
4313 
4314 static void
clear_opt_map_info(OptMapInfo * map)4315 clear_opt_map_info(OptMapInfo* map)
4316 {
4317   static const OptMapInfo clean_info = {
4318     {0, 0}, {0, 0}, 0,
4319     {
4320       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4321       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4322       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4323       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4324       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4325       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4326       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4327       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4328       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4329       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4330       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4331       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4332       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4333       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4334       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4335       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
4336     }
4337   };
4338 
4339   xmemcpy(map, &clean_info, sizeof(OptMapInfo));
4340 }
4341 
4342 static void
copy_opt_map_info(OptMapInfo * to,OptMapInfo * from)4343 copy_opt_map_info(OptMapInfo* to, OptMapInfo* from)
4344 {
4345   *to = *from;
4346 }
4347 
4348 static void
add_char_opt_map_info(OptMapInfo * map,UChar c,OnigEncoding enc)4349 add_char_opt_map_info(OptMapInfo* map, UChar c, OnigEncoding enc)
4350 {
4351   if (map->map[c] == 0) {
4352     map->map[c] = 1;
4353     map->value += map_position_value(enc, c);
4354   }
4355 }
4356 
4357 static int
add_char_amb_opt_map_info(OptMapInfo * map,UChar * p,UChar * end,OnigEncoding enc,OnigCaseFoldType case_fold_flag)4358 add_char_amb_opt_map_info(OptMapInfo* map, UChar* p, UChar* end,
4359                           OnigEncoding enc, OnigCaseFoldType case_fold_flag)
4360 {
4361   OnigCaseFoldCodeItem items[ONIGENC_GET_CASE_FOLD_CODES_MAX_NUM];
4362   UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
4363   int i, n;
4364 
4365   add_char_opt_map_info(map, p[0], enc);
4366 
4367   case_fold_flag = DISABLE_CASE_FOLD_MULTI_CHAR(case_fold_flag);
4368   n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, case_fold_flag, p, end, items);
4369   if (n < 0) return n;
4370 
4371   for (i = 0; i < n; i++) {
4372     ONIGENC_CODE_TO_MBC(enc, items[i].code[0], buf);
4373     add_char_opt_map_info(map, buf[0], enc);
4374   }
4375 
4376   return 0;
4377 }
4378 
4379 static void
select_opt_map_info(OptMapInfo * now,OptMapInfo * alt)4380 select_opt_map_info(OptMapInfo* now, OptMapInfo* alt)
4381 {
4382   static int z = 1<<15; /* 32768: something big value */
4383 
4384   int v1, v2;
4385 
4386   if (alt->value == 0) return ;
4387   if (now->value == 0) {
4388     copy_opt_map_info(now, alt);
4389     return ;
4390   }
4391 
4392   v1 = z / now->value;
4393   v2 = z / alt->value;
4394   if (comp_distance_value(&now->mmd, &alt->mmd, v1, v2) > 0)
4395     copy_opt_map_info(now, alt);
4396 }
4397 
4398 static int
comp_opt_exact_or_map_info(OptExactInfo * e,OptMapInfo * m)4399 comp_opt_exact_or_map_info(OptExactInfo* e, OptMapInfo* m)
4400 {
4401 #define COMP_EM_BASE  20
4402   int ve, vm;
4403 
4404   if (m->value <= 0) return -1;
4405 
4406   ve = COMP_EM_BASE * e->len * (e->ignore_case ? 1 : 2);
4407   vm = COMP_EM_BASE * 5 * 2 / m->value;
4408   return comp_distance_value(&e->mmd, &m->mmd, ve, vm);
4409 }
4410 
4411 static void
alt_merge_opt_map_info(OnigEncoding enc,OptMapInfo * to,OptMapInfo * add)4412 alt_merge_opt_map_info(OnigEncoding enc, OptMapInfo* to, OptMapInfo* add)
4413 {
4414   int i, val;
4415 
4416   /* if (! is_equal_mml(&to->mmd, &add->mmd)) return ; */
4417   if (to->value == 0) return ;
4418   if (add->value == 0 || to->mmd.max < add->mmd.min) {
4419     clear_opt_map_info(to);
4420     return ;
4421   }
4422 
4423   alt_merge_mml(&to->mmd, &add->mmd);
4424 
4425   val = 0;
4426   for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) {
4427     if (add->map[i])
4428       to->map[i] = 1;
4429 
4430     if (to->map[i])
4431       val += map_position_value(enc, i);
4432   }
4433   to->value = val;
4434 
4435   alt_merge_opt_anc_info(&to->anc, &add->anc);
4436 }
4437 
4438 static void
set_bound_node_opt_info(NodeOptInfo * opt,MinMaxLen * mmd)4439 set_bound_node_opt_info(NodeOptInfo* opt, MinMaxLen* mmd)
4440 {
4441   copy_mml(&(opt->exb.mmd),  mmd);
4442   copy_mml(&(opt->expr.mmd), mmd);
4443   copy_mml(&(opt->map.mmd),  mmd);
4444 }
4445 
4446 static void
clear_node_opt_info(NodeOptInfo * opt)4447 clear_node_opt_info(NodeOptInfo* opt)
4448 {
4449   clear_mml(&opt->len);
4450   clear_opt_anc_info(&opt->anc);
4451   clear_opt_exact_info(&opt->exb);
4452   clear_opt_exact_info(&opt->exm);
4453   clear_opt_exact_info(&opt->expr);
4454   clear_opt_map_info(&opt->map);
4455 }
4456 
4457 static void
copy_node_opt_info(NodeOptInfo * to,NodeOptInfo * from)4458 copy_node_opt_info(NodeOptInfo* to, NodeOptInfo* from)
4459 {
4460   *to = *from;
4461 }
4462 
4463 static void
concat_left_node_opt_info(OnigEncoding enc,NodeOptInfo * to,NodeOptInfo * add)4464 concat_left_node_opt_info(OnigEncoding enc, NodeOptInfo* to, NodeOptInfo* add)
4465 {
4466   int exb_reach, exm_reach;
4467   OptAncInfo tanc;
4468 
4469   concat_opt_anc_info(&tanc, &to->anc, &add->anc, to->len.max, add->len.max);
4470   copy_opt_anc_info(&to->anc, &tanc);
4471 
4472   if (add->exb.len > 0 && to->len.max == 0) {
4473     concat_opt_anc_info(&tanc, &to->anc, &add->exb.anc,
4474 			to->len.max, add->len.max);
4475     copy_opt_anc_info(&add->exb.anc, &tanc);
4476   }
4477 
4478   if (add->map.value > 0 && to->len.max == 0) {
4479     if (add->map.mmd.max == 0)
4480       add->map.anc.left_anchor |= to->anc.left_anchor;
4481   }
4482 
4483   exb_reach = to->exb.reach_end;
4484   exm_reach = to->exm.reach_end;
4485 
4486   if (add->len.max != 0)
4487     to->exb.reach_end = to->exm.reach_end = 0;
4488 
4489   if (add->exb.len > 0) {
4490     if (exb_reach) {
4491       concat_opt_exact_info(&to->exb, &add->exb, enc);
4492       clear_opt_exact_info(&add->exb);
4493     }
4494     else if (exm_reach) {
4495       concat_opt_exact_info(&to->exm, &add->exb, enc);
4496       clear_opt_exact_info(&add->exb);
4497     }
4498   }
4499   select_opt_exact_info(enc, &to->exm, &add->exb);
4500   select_opt_exact_info(enc, &to->exm, &add->exm);
4501 
4502   if (to->expr.len > 0) {
4503     if (add->len.max > 0) {
4504       if (to->expr.len > (int )add->len.max)
4505 	to->expr.len = add->len.max;
4506 
4507       if (to->expr.mmd.max == 0)
4508 	select_opt_exact_info(enc, &to->exb, &to->expr);
4509       else
4510 	select_opt_exact_info(enc, &to->exm, &to->expr);
4511     }
4512   }
4513   else if (add->expr.len > 0) {
4514     copy_opt_exact_info(&to->expr, &add->expr);
4515   }
4516 
4517   select_opt_map_info(&to->map, &add->map);
4518 
4519   add_mml(&to->len, &add->len);
4520 }
4521 
4522 static void
alt_merge_node_opt_info(NodeOptInfo * to,NodeOptInfo * add,OptEnv * env)4523 alt_merge_node_opt_info(NodeOptInfo* to, NodeOptInfo* add, OptEnv* env)
4524 {
4525   alt_merge_opt_anc_info  (&to->anc,  &add->anc);
4526   alt_merge_opt_exact_info(&to->exb,  &add->exb, env);
4527   alt_merge_opt_exact_info(&to->exm,  &add->exm, env);
4528   alt_merge_opt_exact_info(&to->expr, &add->expr, env);
4529   alt_merge_opt_map_info(env->enc, &to->map,  &add->map);
4530 
4531   alt_merge_mml(&to->len, &add->len);
4532 }
4533 
4534 
4535 #define MAX_NODE_OPT_INFO_REF_COUNT    5
4536 
4537 static int
optimize_node_left(Node * node,NodeOptInfo * opt,OptEnv * env)4538 optimize_node_left(Node* node, NodeOptInfo* opt, OptEnv* env)
4539 {
4540   int type;
4541   int r = 0;
4542 
4543   clear_node_opt_info(opt);
4544   set_bound_node_opt_info(opt, &env->mmd);
4545 
4546   type = NTYPE(node);
4547   switch (type) {
4548   case NT_LIST:
4549     {
4550       OptEnv nenv;
4551       NodeOptInfo nopt;
4552       Node* nd = node;
4553 
4554       copy_opt_env(&nenv, env);
4555       do {
4556 	r = optimize_node_left(NCAR(nd), &nopt, &nenv);
4557 	if (r == 0) {
4558 	  add_mml(&nenv.mmd, &nopt.len);
4559 	  concat_left_node_opt_info(env->enc, opt, &nopt);
4560 	}
4561       } while (r == 0 && IS_NOT_NULL(nd = NCDR(nd)));
4562     }
4563     break;
4564 
4565   case NT_ALT:
4566     {
4567       NodeOptInfo nopt;
4568       Node* nd = node;
4569 
4570       do {
4571 	r = optimize_node_left(NCAR(nd), &nopt, env);
4572 	if (r == 0) {
4573 	  if (nd == node) copy_node_opt_info(opt, &nopt);
4574 	  else            alt_merge_node_opt_info(opt, &nopt, env);
4575 	}
4576       } while ((r == 0) && IS_NOT_NULL(nd = NCDR(nd)));
4577     }
4578     break;
4579 
4580   case NT_STR:
4581     {
4582       StrNode* sn = NSTR(node);
4583       int slen = sn->end - sn->s;
4584       int is_raw = NSTRING_IS_RAW(node);
4585 
4586       if (! NSTRING_IS_AMBIG(node)) {
4587 	concat_opt_exact_info_str(&opt->exb, sn->s, sn->end,
4588 				  NSTRING_IS_RAW(node), env->enc);
4589 	if (slen > 0) {
4590 	  add_char_opt_map_info(&opt->map, *(sn->s), env->enc);
4591 	}
4592         set_mml(&opt->len, slen, slen);
4593       }
4594       else {
4595         int max;
4596 
4597 	if (NSTRING_IS_DONT_GET_OPT_INFO(node)) {
4598           int n = onigenc_strlen(env->enc, sn->s, sn->end);
4599           max = ONIGENC_MBC_MAXLEN_DIST(env->enc) * n;
4600 	}
4601 	else {
4602 	  concat_opt_exact_info_str(&opt->exb, sn->s, sn->end,
4603 				    is_raw, env->enc);
4604 	  opt->exb.ignore_case = 1;
4605 
4606 	  if (slen > 0) {
4607 	    r = add_char_amb_opt_map_info(&opt->map, sn->s, sn->end,
4608 					  env->enc, env->case_fold_flag);
4609 	    if (r != 0) break;
4610 	  }
4611 
4612 	  max = slen;
4613 	}
4614 
4615         set_mml(&opt->len, slen, max);
4616       }
4617 
4618       if (opt->exb.len == slen)
4619 	opt->exb.reach_end = 1;
4620     }
4621     break;
4622 
4623   case NT_CCLASS:
4624     {
4625       int i, z;
4626       CClassNode* cc = NCCLASS(node);
4627 
4628       /* no need to check ignore case. (setted in setup_tree()) */
4629 
4630       if (IS_NOT_NULL(cc->mbuf) || IS_NCCLASS_NOT(cc)) {
4631         OnigDistance min = ONIGENC_MBC_MINLEN(env->enc);
4632 	OnigDistance max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
4633 
4634 	set_mml(&opt->len, min, max);
4635       }
4636       else {
4637         for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
4638           z = BITSET_AT(cc->bs, i);
4639           if ((z && !IS_NCCLASS_NOT(cc)) || (!z && IS_NCCLASS_NOT(cc))) {
4640             add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
4641           }
4642         }
4643 	set_mml(&opt->len, 1, 1);
4644       }
4645     }
4646     break;
4647 
4648   case NT_CTYPE:
4649     {
4650       int i, min, max;
4651 
4652       max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
4653 
4654       if (max == 1) {
4655         min = 1;
4656 
4657 	switch (NCTYPE(node)->ctype) {
4658 	case ONIGENC_CTYPE_WORD:
4659 	  if (NCTYPE(node)->not != 0) {
4660 	    for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
4661 	      if (! ONIGENC_IS_CODE_WORD(env->enc, i)) {
4662 		add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
4663 	      }
4664 	    }
4665 	  }
4666 	  else {
4667 	    for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
4668 	      if (ONIGENC_IS_CODE_WORD(env->enc, i)) {
4669 		add_char_opt_map_info(&opt->map, (UChar )i, env->enc);
4670 	      }
4671 	    }
4672 	  }
4673 	  break;
4674 	}
4675       }
4676       else {
4677         min = ONIGENC_MBC_MINLEN(env->enc);
4678       }
4679       set_mml(&opt->len, min, max);
4680     }
4681     break;
4682 
4683   case NT_CANY:
4684     {
4685       OnigDistance min = ONIGENC_MBC_MINLEN(env->enc);
4686       OnigDistance max = ONIGENC_MBC_MAXLEN_DIST(env->enc);
4687       set_mml(&opt->len, min, max);
4688     }
4689     break;
4690 
4691   case NT_ANCHOR:
4692     switch (NANCHOR(node)->type) {
4693     case ANCHOR_BEGIN_BUF:
4694     case ANCHOR_BEGIN_POSITION:
4695     case ANCHOR_BEGIN_LINE:
4696     case ANCHOR_END_BUF:
4697     case ANCHOR_SEMI_END_BUF:
4698     case ANCHOR_END_LINE:
4699       add_opt_anc_info(&opt->anc, NANCHOR(node)->type);
4700       break;
4701 
4702     case ANCHOR_PREC_READ:
4703       {
4704 	NodeOptInfo nopt;
4705 
4706 	r = optimize_node_left(NANCHOR(node)->target, &nopt, env);
4707 	if (r == 0) {
4708 	  if (nopt.exb.len > 0)
4709 	    copy_opt_exact_info(&opt->expr, &nopt.exb);
4710 	  else if (nopt.exm.len > 0)
4711 	    copy_opt_exact_info(&opt->expr, &nopt.exm);
4712 
4713 	  opt->expr.reach_end = 0;
4714 
4715 	  if (nopt.map.value > 0)
4716 	    copy_opt_map_info(&opt->map, &nopt.map);
4717 	}
4718       }
4719       break;
4720 
4721     case ANCHOR_PREC_READ_NOT:
4722     case ANCHOR_LOOK_BEHIND: /* Sorry, I can't make use of it. */
4723     case ANCHOR_LOOK_BEHIND_NOT:
4724       break;
4725     }
4726     break;
4727 
4728   case NT_BREF:
4729     {
4730       int i;
4731       int* backs;
4732       OnigDistance min, max, tmin, tmax;
4733       Node** nodes = SCANENV_MEM_NODES(env->scan_env);
4734       BRefNode* br = NBREF(node);
4735 
4736       if (br->state & NST_RECURSION) {
4737 	set_mml(&opt->len, 0, ONIG_INFINITE_DISTANCE);
4738 	break;
4739       }
4740       backs = BACKREFS_P(br);
4741       r = get_min_match_length(nodes[backs[0]], &min, env->scan_env);
4742       if (r != 0) break;
4743       r = get_max_match_length(nodes[backs[0]], &max, env->scan_env);
4744       if (r != 0) break;
4745       for (i = 1; i < br->back_num; i++) {
4746 	r = get_min_match_length(nodes[backs[i]], &tmin, env->scan_env);
4747 	if (r != 0) break;
4748 	r = get_max_match_length(nodes[backs[i]], &tmax, env->scan_env);
4749 	if (r != 0) break;
4750 	if (min > tmin) min = tmin;
4751 	if (max < tmax) max = tmax;
4752       }
4753       if (r == 0) set_mml(&opt->len, min, max);
4754     }
4755     break;
4756 
4757 #ifdef USE_SUBEXP_CALL
4758   case NT_CALL:
4759     if (IS_CALL_RECURSION(NCALL(node)))
4760       set_mml(&opt->len, 0, ONIG_INFINITE_DISTANCE);
4761     else {
4762       OnigOptionType save = env->options;
4763       env->options = NENCLOSE(NCALL(node)->target)->option;
4764       r = optimize_node_left(NCALL(node)->target, opt, env);
4765       env->options = save;
4766     }
4767     break;
4768 #endif
4769 
4770   case NT_QTFR:
4771     {
4772       int i;
4773       OnigDistance min, max;
4774       NodeOptInfo nopt;
4775       QtfrNode* qn = NQTFR(node);
4776 
4777       r = optimize_node_left(qn->target, &nopt, env);
4778       if (r) break;
4779 
4780       if (qn->lower == 0 && IS_REPEAT_INFINITE(qn->upper)) {
4781 	if (env->mmd.max == 0 &&
4782 	    NTYPE(qn->target) == NT_CANY && qn->greedy) {
4783 	  if (IS_MULTILINE(env->options))
4784 	    add_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_ML);
4785 	  else
4786 	    add_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR);
4787 	}
4788       }
4789       else {
4790 	if (qn->lower > 0) {
4791 	  copy_node_opt_info(opt, &nopt);
4792 	  if (nopt.exb.len > 0) {
4793 	    if (nopt.exb.reach_end) {
4794 	      for (i = 2; i <= qn->lower &&
4795 		          ! is_full_opt_exact_info(&opt->exb); i++) {
4796 		concat_opt_exact_info(&opt->exb, &nopt.exb, env->enc);
4797 	      }
4798 	      if (i < qn->lower) {
4799 		opt->exb.reach_end = 0;
4800 	      }
4801 	    }
4802 	  }
4803 
4804 	  if (qn->lower != qn->upper) {
4805 	    opt->exb.reach_end = 0;
4806 	    opt->exm.reach_end = 0;
4807 	  }
4808 	  if (qn->lower > 1)
4809 	    opt->exm.reach_end = 0;
4810 	}
4811       }
4812 
4813       min = distance_multiply(nopt.len.min, qn->lower);
4814       if (IS_REPEAT_INFINITE(qn->upper))
4815 	max = (nopt.len.max > 0 ? ONIG_INFINITE_DISTANCE : 0);
4816       else
4817 	max = distance_multiply(nopt.len.max, qn->upper);
4818 
4819       set_mml(&opt->len, min, max);
4820     }
4821     break;
4822 
4823   case NT_ENCLOSE:
4824     {
4825       EncloseNode* en = NENCLOSE(node);
4826 
4827       switch (en->type) {
4828       case ENCLOSE_OPTION:
4829 	{
4830 	  OnigOptionType save = env->options;
4831 
4832 	  env->options = en->option;
4833 	  r = optimize_node_left(en->target, opt, env);
4834 	  env->options = save;
4835 	}
4836 	break;
4837 
4838       case ENCLOSE_MEMORY:
4839 #ifdef USE_SUBEXP_CALL
4840 	en->opt_count++;
4841 	if (en->opt_count > MAX_NODE_OPT_INFO_REF_COUNT) {
4842 	  OnigDistance min, max;
4843 
4844 	  min = 0;
4845 	  max = ONIG_INFINITE_DISTANCE;
4846 	  if (IS_ENCLOSE_MIN_FIXED(en)) min = en->min_len;
4847 	  if (IS_ENCLOSE_MAX_FIXED(en)) max = en->max_len;
4848 	  set_mml(&opt->len, min, max);
4849 	}
4850 	else
4851 #endif
4852 	{
4853 	  r = optimize_node_left(en->target, opt, env);
4854 
4855 	  if (is_set_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_MASK)) {
4856 	    if (BIT_STATUS_AT(env->scan_env->backrefed_mem, en->regnum))
4857 	      remove_opt_anc_info(&opt->anc, ANCHOR_ANYCHAR_STAR_MASK);
4858 	  }
4859 	}
4860 	break;
4861 
4862       case ENCLOSE_STOP_BACKTRACK:
4863 	r = optimize_node_left(en->target, opt, env);
4864 	break;
4865       }
4866     }
4867     break;
4868 
4869   default:
4870 #ifdef ONIG_DEBUG
4871     fprintf(stderr, "optimize_node_left: undefined node type %d\n",
4872 	    NTYPE(node));
4873 #endif
4874     r = ONIGERR_TYPE_BUG;
4875     break;
4876   }
4877 
4878   return r;
4879 }
4880 
4881 static int
set_optimize_exact_info(regex_t * reg,OptExactInfo * e)4882 set_optimize_exact_info(regex_t* reg, OptExactInfo* e)
4883 {
4884   int r;
4885 
4886   if (e->len == 0) return 0;
4887 
4888   if (e->ignore_case) {
4889     reg->exact = (UChar* )xmalloc(e->len);
4890     CHECK_NULL_RETURN_MEMERR(reg->exact);
4891     xmemcpy(reg->exact, e->s, e->len);
4892     reg->exact_end = reg->exact + e->len;
4893     reg->optimize = ONIG_OPTIMIZE_EXACT_IC;
4894   }
4895   else {
4896     int allow_reverse;
4897 
4898     reg->exact = str_dup(e->s, e->s + e->len);
4899     CHECK_NULL_RETURN_MEMERR(reg->exact);
4900     reg->exact_end = reg->exact + e->len;
4901 
4902     allow_reverse =
4903 	ONIGENC_IS_ALLOWED_REVERSE_MATCH(reg->enc, reg->exact, reg->exact_end);
4904 
4905     if (e->len >= 3 || (e->len >= 2 && allow_reverse)) {
4906       r = set_bm_skip(reg->exact, reg->exact_end, reg->enc,
4907 	              reg->map, &(reg->int_map));
4908       if (r) return r;
4909 
4910       reg->optimize = (allow_reverse != 0
4911 		       ? ONIG_OPTIMIZE_EXACT_BM : ONIG_OPTIMIZE_EXACT_BM_NOT_REV);
4912     }
4913     else {
4914       reg->optimize = ONIG_OPTIMIZE_EXACT;
4915     }
4916   }
4917 
4918   reg->dmin = e->mmd.min;
4919   reg->dmax = e->mmd.max;
4920 
4921   if (reg->dmin != ONIG_INFINITE_DISTANCE) {
4922     reg->threshold_len = reg->dmin + (reg->exact_end - reg->exact);
4923   }
4924 
4925   return 0;
4926 }
4927 
4928 static void
set_optimize_map_info(regex_t * reg,OptMapInfo * m)4929 set_optimize_map_info(regex_t* reg, OptMapInfo* m)
4930 {
4931   int i;
4932 
4933   for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
4934     reg->map[i] = m->map[i];
4935 
4936   reg->optimize   = ONIG_OPTIMIZE_MAP;
4937   reg->dmin       = m->mmd.min;
4938   reg->dmax       = m->mmd.max;
4939 
4940   if (reg->dmin != ONIG_INFINITE_DISTANCE) {
4941     reg->threshold_len = reg->dmin + 1;
4942   }
4943 }
4944 
4945 static void
set_sub_anchor(regex_t * reg,OptAncInfo * anc)4946 set_sub_anchor(regex_t* reg, OptAncInfo* anc)
4947 {
4948   reg->sub_anchor |= anc->left_anchor  & ANCHOR_BEGIN_LINE;
4949   reg->sub_anchor |= anc->right_anchor & ANCHOR_END_LINE;
4950 }
4951 
4952 #ifdef ONIG_DEBUG
4953 static void print_optimize_info(FILE* f, regex_t* reg);
4954 #endif
4955 
4956 static int
set_optimize_info_from_tree(Node * node,regex_t * reg,ScanEnv * scan_env)4957 set_optimize_info_from_tree(Node* node, regex_t* reg, ScanEnv* scan_env)
4958 {
4959 
4960   int r;
4961   NodeOptInfo opt;
4962   OptEnv env;
4963 
4964   env.enc            = reg->enc;
4965   env.options        = reg->options;
4966   env.case_fold_flag = reg->case_fold_flag;
4967   env.scan_env   = scan_env;
4968   clear_mml(&env.mmd);
4969 
4970   r = optimize_node_left(node, &opt, &env);
4971   if (r) return r;
4972 
4973   reg->anchor = opt.anc.left_anchor & (ANCHOR_BEGIN_BUF |
4974         ANCHOR_BEGIN_POSITION | ANCHOR_ANYCHAR_STAR | ANCHOR_ANYCHAR_STAR_ML);
4975 
4976   reg->anchor |= opt.anc.right_anchor & (ANCHOR_END_BUF | ANCHOR_SEMI_END_BUF);
4977 
4978   if (reg->anchor & (ANCHOR_END_BUF | ANCHOR_SEMI_END_BUF)) {
4979     reg->anchor_dmin = opt.len.min;
4980     reg->anchor_dmax = opt.len.max;
4981   }
4982 
4983   if (opt.exb.len > 0 || opt.exm.len > 0) {
4984     select_opt_exact_info(reg->enc, &opt.exb, &opt.exm);
4985     if (opt.map.value > 0 &&
4986 	comp_opt_exact_or_map_info(&opt.exb, &opt.map) > 0) {
4987       goto set_map;
4988     }
4989     else {
4990       r = set_optimize_exact_info(reg, &opt.exb);
4991       set_sub_anchor(reg, &opt.exb.anc);
4992     }
4993   }
4994   else if (opt.map.value > 0) {
4995   set_map:
4996     set_optimize_map_info(reg, &opt.map);
4997     set_sub_anchor(reg, &opt.map.anc);
4998   }
4999   else {
5000     reg->sub_anchor |= opt.anc.left_anchor & ANCHOR_BEGIN_LINE;
5001     if (opt.len.max == 0)
5002       reg->sub_anchor |= opt.anc.right_anchor & ANCHOR_END_LINE;
5003   }
5004 
5005 #if defined(ONIG_DEBUG_COMPILE) || defined(ONIG_DEBUG_MATCH)
5006   print_optimize_info(stderr, reg);
5007 #endif
5008   return r;
5009 }
5010 
5011 static void
clear_optimize_info(regex_t * reg)5012 clear_optimize_info(regex_t* reg)
5013 {
5014   reg->optimize      = ONIG_OPTIMIZE_NONE;
5015   reg->anchor        = 0;
5016   reg->anchor_dmin   = 0;
5017   reg->anchor_dmax   = 0;
5018   reg->sub_anchor    = 0;
5019   reg->exact_end     = (UChar* )NULL;
5020   reg->threshold_len = 0;
5021   if (IS_NOT_NULL(reg->exact)) {
5022     xfree(reg->exact);
5023     reg->exact = (UChar* )NULL;
5024   }
5025 }
5026 
5027 #ifdef ONIG_DEBUG
5028 
print_enc_string(FILE * fp,OnigEncoding enc,const UChar * s,const UChar * end)5029 static void print_enc_string(FILE* fp, OnigEncoding enc,
5030 			     const UChar *s, const UChar *end)
5031 {
5032   fprintf(fp, "\nPATTERN: /");
5033 
5034   if (ONIGENC_MBC_MINLEN(enc) > 1) {
5035     const UChar *p;
5036     OnigCodePoint code;
5037 
5038     p = s;
5039     while (p < end) {
5040       code = ONIGENC_MBC_TO_CODE(enc, p, end);
5041       if (code >= 0x80) {
5042 	fprintf(fp, " 0x%04x ", (int )code);
5043       }
5044       else {
5045 	fputc((int )code, fp);
5046       }
5047 
5048       p += enclen(enc, p);
5049     }
5050   }
5051   else {
5052     while (s < end) {
5053       fputc((int )*s, fp);
5054       s++;
5055     }
5056   }
5057 
5058   fprintf(fp, "/\n");
5059 }
5060 
5061 static void
print_distance_range(FILE * f,OnigDistance a,OnigDistance b)5062 print_distance_range(FILE* f, OnigDistance a, OnigDistance b)
5063 {
5064   if (a == ONIG_INFINITE_DISTANCE)
5065     fputs("inf", f);
5066   else
5067     fprintf(f, "(%u)", a);
5068 
5069   fputs("-", f);
5070 
5071   if (b == ONIG_INFINITE_DISTANCE)
5072     fputs("inf", f);
5073   else
5074     fprintf(f, "(%u)", b);
5075 }
5076 
5077 static void
print_anchor(FILE * f,int anchor)5078 print_anchor(FILE* f, int anchor)
5079 {
5080   int q = 0;
5081 
5082   fprintf(f, "[");
5083 
5084   if (anchor & ANCHOR_BEGIN_BUF) {
5085     fprintf(f, "begin-buf");
5086     q = 1;
5087   }
5088   if (anchor & ANCHOR_BEGIN_LINE) {
5089     if (q) fprintf(f, ", ");
5090     q = 1;
5091     fprintf(f, "begin-line");
5092   }
5093   if (anchor & ANCHOR_BEGIN_POSITION) {
5094     if (q) fprintf(f, ", ");
5095     q = 1;
5096     fprintf(f, "begin-pos");
5097   }
5098   if (anchor & ANCHOR_END_BUF) {
5099     if (q) fprintf(f, ", ");
5100     q = 1;
5101     fprintf(f, "end-buf");
5102   }
5103   if (anchor & ANCHOR_SEMI_END_BUF) {
5104     if (q) fprintf(f, ", ");
5105     q = 1;
5106     fprintf(f, "semi-end-buf");
5107   }
5108   if (anchor & ANCHOR_END_LINE) {
5109     if (q) fprintf(f, ", ");
5110     q = 1;
5111     fprintf(f, "end-line");
5112   }
5113   if (anchor & ANCHOR_ANYCHAR_STAR) {
5114     if (q) fprintf(f, ", ");
5115     q = 1;
5116     fprintf(f, "anychar-star");
5117   }
5118   if (anchor & ANCHOR_ANYCHAR_STAR_ML) {
5119     if (q) fprintf(f, ", ");
5120     fprintf(f, "anychar-star-pl");
5121   }
5122 
5123   fprintf(f, "]");
5124 }
5125 
5126 static void
print_optimize_info(FILE * f,regex_t * reg)5127 print_optimize_info(FILE* f, regex_t* reg)
5128 {
5129   static const char* on[] = { "NONE", "EXACT", "EXACT_BM", "EXACT_BM_NOT_REV",
5130                               "EXACT_IC", "MAP" };
5131 
5132   fprintf(f, "optimize: %s\n", on[reg->optimize]);
5133   fprintf(f, "  anchor: "); print_anchor(f, reg->anchor);
5134   if ((reg->anchor & ANCHOR_END_BUF_MASK) != 0)
5135     print_distance_range(f, reg->anchor_dmin, reg->anchor_dmax);
5136   fprintf(f, "\n");
5137 
5138   if (reg->optimize) {
5139     fprintf(f, "  sub anchor: "); print_anchor(f, reg->sub_anchor);
5140     fprintf(f, "\n");
5141   }
5142   fprintf(f, "\n");
5143 
5144   if (reg->exact) {
5145     UChar *p;
5146     fprintf(f, "exact: [");
5147     for (p = reg->exact; p < reg->exact_end; p++) {
5148       fputc(*p, f);
5149     }
5150     fprintf(f, "]: length: %d\n", (reg->exact_end - reg->exact));
5151   }
5152   else if (reg->optimize & ONIG_OPTIMIZE_MAP) {
5153     int c, i, n = 0;
5154 
5155     for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++)
5156       if (reg->map[i]) n++;
5157 
5158     fprintf(f, "map: n=%d\n", n);
5159     if (n > 0) {
5160       c = 0;
5161       fputc('[', f);
5162       for (i = 0; i < ONIG_CHAR_TABLE_SIZE; i++) {
5163 	if (reg->map[i] != 0) {
5164           if (c > 0)  fputs(", ", f);
5165           c++;
5166           if (ONIGENC_MBC_MAXLEN(reg->enc) == 1 &&
5167               ONIGENC_IS_CODE_PRINT(reg->enc, (OnigCodePoint )i))
5168             fputc(i, f);
5169           else
5170             fprintf(f, "%d", i);
5171         }
5172       }
5173       fprintf(f, "]\n");
5174     }
5175   }
5176 }
5177 #endif /* ONIG_DEBUG */
5178 
5179 
5180 extern void
onig_free_body(regex_t * reg)5181 onig_free_body(regex_t* reg)
5182 {
5183   if (IS_NOT_NULL(reg)) {
5184     if (IS_NOT_NULL(reg->p))                xfree(reg->p);
5185     if (IS_NOT_NULL(reg->exact))            xfree(reg->exact);
5186     if (IS_NOT_NULL(reg->int_map))          xfree(reg->int_map);
5187     if (IS_NOT_NULL(reg->int_map_backward)) xfree(reg->int_map_backward);
5188     if (IS_NOT_NULL(reg->repeat_range))     xfree(reg->repeat_range);
5189     if (IS_NOT_NULL(reg->chain))            onig_free(reg->chain);
5190 
5191 #ifdef USE_NAMED_GROUP
5192     onig_names_free(reg);
5193 #endif
5194   }
5195 }
5196 
5197 extern void
onig_free(regex_t * reg)5198 onig_free(regex_t* reg)
5199 {
5200   if (IS_NOT_NULL(reg)) {
5201     onig_free_body(reg);
5202     xfree(reg);
5203   }
5204 }
5205 
5206 #define REGEX_TRANSFER(to,from) do {\
5207   (to)->state = ONIG_STATE_MODIFY;\
5208   onig_free_body(to);\
5209   xmemcpy(to, from, sizeof(regex_t));\
5210   xfree(from);\
5211 } while (0)
5212 
5213 extern void
onig_transfer(regex_t * to,regex_t * from)5214 onig_transfer(regex_t* to, regex_t* from)
5215 {
5216   THREAD_ATOMIC_START;
5217   REGEX_TRANSFER(to, from);
5218   THREAD_ATOMIC_END;
5219 }
5220 
5221 #define REGEX_CHAIN_HEAD(reg) do {\
5222   while (IS_NOT_NULL((reg)->chain)) {\
5223     (reg) = (reg)->chain;\
5224   }\
5225 } while (0)
5226 
5227 extern void
onig_chain_link_add(regex_t * to,regex_t * add)5228 onig_chain_link_add(regex_t* to, regex_t* add)
5229 {
5230   THREAD_ATOMIC_START;
5231   REGEX_CHAIN_HEAD(to);
5232   to->chain = add;
5233   THREAD_ATOMIC_END;
5234 }
5235 
5236 extern void
onig_chain_reduce(regex_t * reg)5237 onig_chain_reduce(regex_t* reg)
5238 {
5239   regex_t *head, *prev;
5240 
5241   prev = reg;
5242   head = prev->chain;
5243   if (IS_NOT_NULL(head)) {
5244     reg->state = ONIG_STATE_MODIFY;
5245     while (IS_NOT_NULL(head->chain)) {
5246       prev = head;
5247       head = head->chain;
5248     }
5249     prev->chain = (regex_t* )NULL;
5250     REGEX_TRANSFER(reg, head);
5251   }
5252 }
5253 
5254 #ifdef ONIG_DEBUG
5255 static void print_compiled_byte_code_list P_((FILE* f, regex_t* reg));
5256 #endif
5257 #ifdef ONIG_DEBUG_PARSE_TREE
5258 static void print_tree P_((FILE* f, Node* node));
5259 #endif
5260 
5261 extern int
onig_compile(regex_t * reg,const UChar * pattern,const UChar * pattern_end,OnigErrorInfo * einfo)5262 onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
5263 	      OnigErrorInfo* einfo)
5264 {
5265 #define COMPILE_INIT_SIZE  20
5266 
5267   int r, init_size;
5268   Node*  root;
5269   ScanEnv  scan_env;
5270 #ifdef USE_SUBEXP_CALL
5271   UnsetAddrList  uslist;
5272 #endif
5273 
5274   if (IS_NOT_NULL(einfo)) einfo->par = (UChar* )NULL;
5275 
5276   reg->state = ONIG_STATE_COMPILING;
5277 
5278 #ifdef ONIG_DEBUG
5279   print_enc_string(stderr, reg->enc, pattern, pattern_end);
5280 #endif
5281 
5282   if (reg->alloc == 0) {
5283     init_size = (pattern_end - pattern) * 2;
5284     if (init_size <= 0) init_size = COMPILE_INIT_SIZE;
5285     r = BBUF_INIT(reg, init_size);
5286     if (r != 0) goto end;
5287   }
5288   else
5289     reg->used = 0;
5290 
5291   reg->num_mem            = 0;
5292   reg->num_repeat         = 0;
5293   reg->num_null_check     = 0;
5294   reg->repeat_range_alloc = 0;
5295   reg->repeat_range       = (OnigRepeatRange* )NULL;
5296 #ifdef USE_COMBINATION_EXPLOSION_CHECK
5297   reg->num_comb_exp_check = 0;
5298 #endif
5299 
5300   r = onig_parse_make_tree(&root, pattern, pattern_end, reg, &scan_env);
5301   if (r != 0) goto err;
5302 
5303 #ifdef USE_NAMED_GROUP
5304   /* mixed use named group and no-named group */
5305   if (scan_env.num_named > 0 &&
5306       IS_SYNTAX_BV(scan_env.syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
5307       !ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_CAPTURE_GROUP)) {
5308     if (scan_env.num_named != scan_env.num_mem)
5309       r = disable_noname_group_capture(&root, reg, &scan_env);
5310     else
5311       r = numbered_ref_check(root);
5312 
5313     if (r != 0) goto err;
5314   }
5315 #endif
5316 
5317 #ifdef USE_SUBEXP_CALL
5318   if (scan_env.num_call > 0) {
5319     r = unset_addr_list_init(&uslist, scan_env.num_call);
5320     if (r != 0) goto err;
5321     scan_env.unset_addr_list = &uslist;
5322     r = setup_subexp_call(root, &scan_env);
5323     if (r != 0) goto err_unset;
5324     r = subexp_recursive_check_trav(root, &scan_env);
5325     if (r  < 0) goto err_unset;
5326     r = subexp_inf_recursive_check_trav(root, &scan_env);
5327     if (r != 0) goto err_unset;
5328 
5329     reg->num_call = scan_env.num_call;
5330   }
5331   else
5332     reg->num_call = 0;
5333 #endif
5334 
5335   r = setup_tree(root, reg, 0, &scan_env);
5336   if (r != 0) goto err_unset;
5337 
5338 #ifdef ONIG_DEBUG_PARSE_TREE
5339   print_tree(stderr, root);
5340 #endif
5341 
5342   reg->capture_history  = scan_env.capture_history;
5343   reg->bt_mem_start     = scan_env.bt_mem_start;
5344   reg->bt_mem_start    |= reg->capture_history;
5345   if (IS_FIND_CONDITION(reg->options))
5346     BIT_STATUS_ON_ALL(reg->bt_mem_end);
5347   else {
5348     reg->bt_mem_end  = scan_env.bt_mem_end;
5349     reg->bt_mem_end |= reg->capture_history;
5350   }
5351 
5352 #ifdef USE_COMBINATION_EXPLOSION_CHECK
5353   if (scan_env.backrefed_mem == 0
5354 #ifdef USE_SUBEXP_CALL
5355       || scan_env.num_call == 0
5356 #endif
5357       ) {
5358     setup_comb_exp_check(root, 0, &scan_env);
5359 #ifdef USE_SUBEXP_CALL
5360     if (scan_env.has_recursion != 0) {
5361       scan_env.num_comb_exp_check = 0;
5362     }
5363     else
5364 #endif
5365     if (scan_env.comb_exp_max_regnum > 0) {
5366       int i;
5367       for (i = 1; i <= scan_env.comb_exp_max_regnum; i++) {
5368 	if (BIT_STATUS_AT(scan_env.backrefed_mem, i) != 0) {
5369 	  scan_env.num_comb_exp_check = 0;
5370 	  break;
5371 	}
5372       }
5373     }
5374   }
5375 
5376   reg->num_comb_exp_check = scan_env.num_comb_exp_check;
5377 #endif
5378 
5379   clear_optimize_info(reg);
5380 #ifndef ONIG_DONT_OPTIMIZE
5381   r = set_optimize_info_from_tree(root, reg, &scan_env);
5382   if (r != 0) goto err_unset;
5383 #endif
5384 
5385   if (IS_NOT_NULL(scan_env.mem_nodes_dynamic)) {
5386     xfree(scan_env.mem_nodes_dynamic);
5387     scan_env.mem_nodes_dynamic = (Node** )NULL;
5388   }
5389 
5390   r = compile_tree(root, reg);
5391   if (r == 0) {
5392     r = add_opcode(reg, OP_END);
5393 #ifdef USE_SUBEXP_CALL
5394     if (scan_env.num_call > 0) {
5395       r = unset_addr_list_fix(&uslist, reg);
5396       unset_addr_list_end(&uslist);
5397       if (r) goto err;
5398     }
5399 #endif
5400 
5401     if ((reg->num_repeat != 0) || (reg->bt_mem_end != 0))
5402       reg->stack_pop_level = STACK_POP_LEVEL_ALL;
5403     else {
5404       if (reg->bt_mem_start != 0)
5405 	reg->stack_pop_level = STACK_POP_LEVEL_MEM_START;
5406       else
5407 	reg->stack_pop_level = STACK_POP_LEVEL_FREE;
5408     }
5409   }
5410 #ifdef USE_SUBEXP_CALL
5411   else if (scan_env.num_call > 0) {
5412     unset_addr_list_end(&uslist);
5413   }
5414 #endif
5415   onig_node_free(root);
5416 
5417 #ifdef ONIG_DEBUG_COMPILE
5418 #ifdef USE_NAMED_GROUP
5419   onig_print_names(stderr, reg);
5420 #endif
5421   print_compiled_byte_code_list(stderr, reg);
5422 #endif
5423 
5424  end:
5425   reg->state = ONIG_STATE_NORMAL;
5426   return r;
5427 
5428  err_unset:
5429 #ifdef USE_SUBEXP_CALL
5430   if (scan_env.num_call > 0) {
5431     unset_addr_list_end(&uslist);
5432   }
5433 #endif
5434  err:
5435   if (IS_NOT_NULL(scan_env.error)) {
5436     if (IS_NOT_NULL(einfo)) {
5437       einfo->enc     = scan_env.enc;
5438       einfo->par     = scan_env.error;
5439       einfo->par_end = scan_env.error_end;
5440     }
5441   }
5442 
5443   onig_node_free(root);
5444   if (IS_NOT_NULL(scan_env.mem_nodes_dynamic))
5445       xfree(scan_env.mem_nodes_dynamic);
5446   return r;
5447 }
5448 
5449 #ifdef USE_RECOMPILE_API
5450 extern int
onig_recompile(regex_t * reg,const UChar * pattern,const UChar * pattern_end,OnigOptionType option,OnigEncoding enc,OnigSyntaxType * syntax,OnigErrorInfo * einfo)5451 onig_recompile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
5452 	    OnigOptionType option, OnigEncoding enc, OnigSyntaxType* syntax,
5453 	    OnigErrorInfo* einfo)
5454 {
5455   int r;
5456   regex_t *new_reg;
5457 
5458   r = onig_new(&new_reg, pattern, pattern_end, option, enc, syntax, einfo);
5459   if (r) return r;
5460   if (ONIG_STATE(reg) == ONIG_STATE_NORMAL) {
5461     onig_transfer(reg, new_reg);
5462   }
5463   else {
5464     onig_chain_link_add(reg, new_reg);
5465   }
5466   return 0;
5467 }
5468 #endif
5469 
5470 static int onig_inited = 0;
5471 
5472 extern int
onig_reg_init(regex_t * reg,OnigOptionType option,OnigCaseFoldType case_fold_flag,OnigEncoding enc,OnigSyntaxType * syntax)5473 onig_reg_init(regex_t* reg, OnigOptionType option,
5474 	      OnigCaseFoldType case_fold_flag,
5475 	      OnigEncoding enc, OnigSyntaxType* syntax)
5476 {
5477   if (! onig_inited)
5478     onig_init();
5479 
5480   if (IS_NULL(reg))
5481     return ONIGERR_INVALID_ARGUMENT;
5482 
5483   if (ONIGENC_IS_UNDEF(enc))
5484     return ONIGERR_DEFAULT_ENCODING_IS_NOT_SETTED;
5485 
5486   if ((option & (ONIG_OPTION_DONT_CAPTURE_GROUP|ONIG_OPTION_CAPTURE_GROUP))
5487       == (ONIG_OPTION_DONT_CAPTURE_GROUP|ONIG_OPTION_CAPTURE_GROUP)) {
5488     return ONIGERR_INVALID_COMBINATION_OF_OPTIONS;
5489   }
5490 
5491   (reg)->state = ONIG_STATE_MODIFY;
5492 
5493   if ((option & ONIG_OPTION_NEGATE_SINGLELINE) != 0) {
5494     option |= syntax->options;
5495     option &= ~ONIG_OPTION_SINGLELINE;
5496   }
5497   else
5498     option |= syntax->options;
5499 
5500   (reg)->enc              = enc;
5501   (reg)->options          = option;
5502   (reg)->syntax           = syntax;
5503   (reg)->optimize         = 0;
5504   (reg)->exact            = (UChar* )NULL;
5505   (reg)->int_map          = (int* )NULL;
5506   (reg)->int_map_backward = (int* )NULL;
5507   (reg)->chain            = (regex_t* )NULL;
5508 
5509   (reg)->p                = (UChar* )NULL;
5510   (reg)->alloc            = 0;
5511   (reg)->used             = 0;
5512   (reg)->name_table       = (void* )NULL;
5513 
5514   (reg)->case_fold_flag   = case_fold_flag;
5515   return 0;
5516 }
5517 
5518 extern int
onig_new_without_alloc(regex_t * reg,const UChar * pattern,const UChar * pattern_end,OnigOptionType option,OnigEncoding enc,OnigSyntaxType * syntax,OnigErrorInfo * einfo)5519 onig_new_without_alloc(regex_t* reg, const UChar* pattern,
5520           const UChar* pattern_end, OnigOptionType option, OnigEncoding enc,
5521           OnigSyntaxType* syntax, OnigErrorInfo* einfo)
5522 {
5523   int r;
5524 
5525   r = onig_reg_init(reg, option, ONIGENC_CASE_FOLD_DEFAULT, enc, syntax);
5526   if (r) return r;
5527 
5528   r = onig_compile(reg, pattern, pattern_end, einfo);
5529   return r;
5530 }
5531 
5532 extern int
onig_new(regex_t ** reg,const UChar * pattern,const UChar * pattern_end,OnigOptionType option,OnigEncoding enc,OnigSyntaxType * syntax,OnigErrorInfo * einfo)5533 onig_new(regex_t** reg, const UChar* pattern, const UChar* pattern_end,
5534 	  OnigOptionType option, OnigEncoding enc, OnigSyntaxType* syntax,
5535 	  OnigErrorInfo* einfo)
5536 {
5537   int r;
5538 
5539   *reg = (regex_t* )xmalloc(sizeof(regex_t));
5540   if (IS_NULL(*reg)) return ONIGERR_MEMORY;
5541 
5542   r = onig_reg_init(*reg, option, ONIGENC_CASE_FOLD_DEFAULT, enc, syntax);
5543   if (r) goto err;
5544 
5545   r = onig_compile(*reg, pattern, pattern_end, einfo);
5546   if (r) {
5547   err:
5548     onig_free(*reg);
5549     *reg = NULL;
5550   }
5551   return r;
5552 }
5553 
5554 
5555 extern int
onig_init(void)5556 onig_init(void)
5557 {
5558   if (onig_inited != 0)
5559     return 0;
5560 
5561   THREAD_SYSTEM_INIT;
5562   THREAD_ATOMIC_START;
5563 
5564   onig_inited = 1;
5565 
5566   onigenc_init();
5567   /* onigenc_set_default_caseconv_table((UChar* )0); */
5568 
5569 #ifdef ONIG_DEBUG_STATISTICS
5570   onig_statistics_init();
5571 #endif
5572 
5573   THREAD_ATOMIC_END;
5574   return 0;
5575 }
5576 
5577 
5578 static OnigEndCallListItemType* EndCallTop;
5579 
onig_add_end_call(void (* func)(void))5580 extern void onig_add_end_call(void (*func)(void))
5581 {
5582   OnigEndCallListItemType* item;
5583 
5584   item = (OnigEndCallListItemType* )xmalloc(sizeof(*item));
5585   if (item == 0) return ;
5586 
5587   item->next = EndCallTop;
5588   item->func = func;
5589 
5590   EndCallTop = item;
5591 }
5592 
5593 static void
exec_end_call_list(void)5594 exec_end_call_list(void)
5595 {
5596   OnigEndCallListItemType* prev;
5597   void (*func)(void);
5598 
5599   while (EndCallTop != 0) {
5600     func = EndCallTop->func;
5601     (*func)();
5602 
5603     prev = EndCallTop;
5604     EndCallTop = EndCallTop->next;
5605     xfree(prev);
5606   }
5607 }
5608 
5609 extern int
onig_end(void)5610 onig_end(void)
5611 {
5612   THREAD_ATOMIC_START;
5613 
5614   exec_end_call_list();
5615 
5616 #ifdef ONIG_DEBUG_STATISTICS
5617   onig_print_statistics(stderr);
5618 #endif
5619 
5620 #ifdef USE_SHARED_CCLASS_TABLE
5621   onig_free_shared_cclass_table();
5622 #endif
5623 
5624 #ifdef USE_PARSE_TREE_NODE_RECYCLE
5625   onig_free_node_list();
5626 #endif
5627 
5628   onig_inited = 0;
5629 
5630   THREAD_ATOMIC_END;
5631   THREAD_SYSTEM_END;
5632   return 0;
5633 }
5634 
5635 extern int
onig_is_in_code_range(const UChar * p,OnigCodePoint code)5636 onig_is_in_code_range(const UChar* p, OnigCodePoint code)
5637 {
5638   OnigCodePoint n, *data;
5639   OnigCodePoint low, high, x;
5640 
5641   GET_CODE_POINT(n, p);
5642   data = (OnigCodePoint* )p;
5643   data++;
5644 
5645   for (low = 0, high = n; low < high; ) {
5646     x = (low + high) >> 1;
5647     if (code > data[x * 2 + 1])
5648       low = x + 1;
5649     else
5650       high = x;
5651   }
5652 
5653   return ((low < n && code >= data[low * 2]) ? 1 : 0);
5654 }
5655 
5656 extern int
onig_is_code_in_cc_len(int elen,OnigCodePoint code,CClassNode * cc)5657 onig_is_code_in_cc_len(int elen, OnigCodePoint code, CClassNode* cc)
5658 {
5659   int found;
5660 
5661   if (elen > 1 || (code >= SINGLE_BYTE_SIZE)) {
5662     if (IS_NULL(cc->mbuf)) {
5663       found = 0;
5664     }
5665     else {
5666       found = (onig_is_in_code_range(cc->mbuf->p, code) != 0 ? 1 : 0);
5667     }
5668   }
5669   else {
5670     found = (BITSET_AT(cc->bs, code) == 0 ? 0 : 1);
5671   }
5672 
5673   if (IS_NCCLASS_NOT(cc))
5674     return !found;
5675   else
5676     return found;
5677 }
5678 
5679 extern int
onig_is_code_in_cc(OnigEncoding enc,OnigCodePoint code,CClassNode * cc)5680 onig_is_code_in_cc(OnigEncoding enc, OnigCodePoint code, CClassNode* cc)
5681 {
5682   int len;
5683 
5684   if (ONIGENC_MBC_MINLEN(enc) > 1) {
5685     len = 2;
5686   }
5687   else {
5688     len = ONIGENC_CODE_TO_MBCLEN(enc, code);
5689   }
5690   return onig_is_code_in_cc_len(len, code, cc);
5691 }
5692 
5693 
5694 #ifdef ONIG_DEBUG
5695 
5696 /* arguments type */
5697 #define ARG_SPECIAL     -1
5698 #define ARG_NON          0
5699 #define ARG_RELADDR      1
5700 #define ARG_ABSADDR      2
5701 #define ARG_LENGTH       3
5702 #define ARG_MEMNUM       4
5703 #define ARG_OPTION       5
5704 #define ARG_STATE_CHECK  6
5705 
5706 OnigOpInfoType OnigOpInfo[] = {
5707   { OP_FINISH,            "finish",          ARG_NON },
5708   { OP_END,               "end",             ARG_NON },
5709   { OP_EXACT1,            "exact1",          ARG_SPECIAL },
5710   { OP_EXACT2,            "exact2",          ARG_SPECIAL },
5711   { OP_EXACT3,            "exact3",          ARG_SPECIAL },
5712   { OP_EXACT4,            "exact4",          ARG_SPECIAL },
5713   { OP_EXACT5,            "exact5",          ARG_SPECIAL },
5714   { OP_EXACTN,            "exactn",          ARG_SPECIAL },
5715   { OP_EXACTMB2N1,        "exactmb2-n1",     ARG_SPECIAL },
5716   { OP_EXACTMB2N2,        "exactmb2-n2",     ARG_SPECIAL },
5717   { OP_EXACTMB2N3,        "exactmb2-n3",     ARG_SPECIAL },
5718   { OP_EXACTMB2N,         "exactmb2-n",      ARG_SPECIAL },
5719   { OP_EXACTMB3N,         "exactmb3n"  ,     ARG_SPECIAL },
5720   { OP_EXACTMBN,          "exactmbn",        ARG_SPECIAL },
5721   { OP_EXACT1_IC,         "exact1-ic",       ARG_SPECIAL },
5722   { OP_EXACTN_IC,         "exactn-ic",       ARG_SPECIAL },
5723   { OP_CCLASS,            "cclass",          ARG_SPECIAL },
5724   { OP_CCLASS_MB,         "cclass-mb",       ARG_SPECIAL },
5725   { OP_CCLASS_MIX,        "cclass-mix",      ARG_SPECIAL },
5726   { OP_CCLASS_NOT,        "cclass-not",      ARG_SPECIAL },
5727   { OP_CCLASS_MB_NOT,     "cclass-mb-not",   ARG_SPECIAL },
5728   { OP_CCLASS_MIX_NOT,    "cclass-mix-not",  ARG_SPECIAL },
5729   { OP_CCLASS_NODE,       "cclass-node",     ARG_SPECIAL },
5730   { OP_ANYCHAR,           "anychar",         ARG_NON },
5731   { OP_ANYCHAR_ML,        "anychar-ml",      ARG_NON },
5732   { OP_ANYCHAR_STAR,      "anychar*",        ARG_NON },
5733   { OP_ANYCHAR_ML_STAR,   "anychar-ml*",     ARG_NON },
5734   { OP_ANYCHAR_STAR_PEEK_NEXT, "anychar*-peek-next", ARG_SPECIAL },
5735   { OP_ANYCHAR_ML_STAR_PEEK_NEXT, "anychar-ml*-peek-next", ARG_SPECIAL },
5736   { OP_WORD,                "word",            ARG_NON },
5737   { OP_NOT_WORD,            "not-word",        ARG_NON },
5738   { OP_WORD_BOUND,          "word-bound",      ARG_NON },
5739   { OP_NOT_WORD_BOUND,      "not-word-bound",  ARG_NON },
5740   { OP_WORD_BEGIN,          "word-begin",      ARG_NON },
5741   { OP_WORD_END,            "word-end",        ARG_NON },
5742   { OP_BEGIN_BUF,           "begin-buf",       ARG_NON },
5743   { OP_END_BUF,             "end-buf",         ARG_NON },
5744   { OP_BEGIN_LINE,          "begin-line",      ARG_NON },
5745   { OP_END_LINE,            "end-line",        ARG_NON },
5746   { OP_SEMI_END_BUF,        "semi-end-buf",    ARG_NON },
5747   { OP_BEGIN_POSITION,      "begin-position",  ARG_NON },
5748   { OP_BACKREF1,            "backref1",             ARG_NON },
5749   { OP_BACKREF2,            "backref2",             ARG_NON },
5750   { OP_BACKREFN,            "backrefn",             ARG_MEMNUM  },
5751   { OP_BACKREFN_IC,         "backrefn-ic",          ARG_SPECIAL },
5752   { OP_BACKREF_MULTI,       "backref_multi",        ARG_SPECIAL },
5753   { OP_BACKREF_MULTI_IC,    "backref_multi-ic",     ARG_SPECIAL },
5754   { OP_BACKREF_WITH_LEVEL,    "backref_at_level",     ARG_SPECIAL },
5755   { OP_MEMORY_START_PUSH,   "mem-start-push",       ARG_MEMNUM  },
5756   { OP_MEMORY_START,        "mem-start",            ARG_MEMNUM  },
5757   { OP_MEMORY_END_PUSH,     "mem-end-push",         ARG_MEMNUM  },
5758   { OP_MEMORY_END_PUSH_REC, "mem-end-push-rec",     ARG_MEMNUM  },
5759   { OP_MEMORY_END,          "mem-end",              ARG_MEMNUM  },
5760   { OP_MEMORY_END_REC,      "mem-end-rec",          ARG_MEMNUM  },
5761   { OP_SET_OPTION_PUSH,     "set-option-push",      ARG_OPTION  },
5762   { OP_SET_OPTION,          "set-option",           ARG_OPTION  },
5763   { OP_FAIL,                "fail",                 ARG_NON },
5764   { OP_JUMP,                "jump",                 ARG_RELADDR },
5765   { OP_PUSH,                "push",                 ARG_RELADDR },
5766   { OP_POP,                 "pop",                  ARG_NON },
5767   { OP_PUSH_OR_JUMP_EXACT1, "push-or-jump-e1",      ARG_SPECIAL },
5768   { OP_PUSH_IF_PEEK_NEXT,   "push-if-peek-next",    ARG_SPECIAL },
5769   { OP_REPEAT,              "repeat",               ARG_SPECIAL },
5770   { OP_REPEAT_NG,           "repeat-ng",            ARG_SPECIAL },
5771   { OP_REPEAT_INC,          "repeat-inc",           ARG_MEMNUM  },
5772   { OP_REPEAT_INC_NG,       "repeat-inc-ng",        ARG_MEMNUM  },
5773   { OP_REPEAT_INC_SG,       "repeat-inc-sg",        ARG_MEMNUM  },
5774   { OP_REPEAT_INC_NG_SG,    "repeat-inc-ng-sg",     ARG_MEMNUM  },
5775   { OP_NULL_CHECK_START,    "null-check-start",     ARG_MEMNUM  },
5776   { OP_NULL_CHECK_END,      "null-check-end",       ARG_MEMNUM  },
5777   { OP_NULL_CHECK_END_MEMST,"null-check-end-memst", ARG_MEMNUM  },
5778   { OP_NULL_CHECK_END_MEMST_PUSH,"null-check-end-memst-push", ARG_MEMNUM  },
5779   { OP_PUSH_POS,             "push-pos",             ARG_NON },
5780   { OP_POP_POS,              "pop-pos",              ARG_NON },
5781   { OP_PUSH_POS_NOT,         "push-pos-not",         ARG_RELADDR },
5782   { OP_FAIL_POS,             "fail-pos",             ARG_NON },
5783   { OP_PUSH_STOP_BT,         "push-stop-bt",         ARG_NON },
5784   { OP_POP_STOP_BT,          "pop-stop-bt",          ARG_NON },
5785   { OP_LOOK_BEHIND,          "look-behind",          ARG_SPECIAL },
5786   { OP_PUSH_LOOK_BEHIND_NOT, "push-look-behind-not", ARG_SPECIAL },
5787   { OP_FAIL_LOOK_BEHIND_NOT, "fail-look-behind-not", ARG_NON },
5788   { OP_CALL,                 "call",                 ARG_ABSADDR },
5789   { OP_RETURN,               "return",               ARG_NON },
5790   { OP_STATE_CHECK_PUSH,         "state-check-push",         ARG_SPECIAL },
5791   { OP_STATE_CHECK_PUSH_OR_JUMP, "state-check-push-or-jump", ARG_SPECIAL },
5792   { OP_STATE_CHECK,              "state-check",              ARG_STATE_CHECK },
5793   { OP_STATE_CHECK_ANYCHAR_STAR, "state-check-anychar*",     ARG_STATE_CHECK },
5794   { OP_STATE_CHECK_ANYCHAR_ML_STAR,
5795     "state-check-anychar-ml*", ARG_STATE_CHECK },
5796   { -1, "", ARG_NON }
5797 };
5798 
5799 static char*
op2name(int opcode)5800 op2name(int opcode)
5801 {
5802   int i;
5803 
5804   for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
5805     if (opcode == OnigOpInfo[i].opcode)
5806       return OnigOpInfo[i].name;
5807   }
5808   return "";
5809 }
5810 
5811 static int
op2arg_type(int opcode)5812 op2arg_type(int opcode)
5813 {
5814   int i;
5815 
5816   for (i = 0; OnigOpInfo[i].opcode >= 0; i++) {
5817     if (opcode == OnigOpInfo[i].opcode)
5818       return OnigOpInfo[i].arg_type;
5819   }
5820   return ARG_SPECIAL;
5821 }
5822 
5823 static void
Indent(FILE * f,int indent)5824 Indent(FILE* f, int indent)
5825 {
5826   int i;
5827   for (i = 0; i < indent; i++) putc(' ', f);
5828 }
5829 
5830 static void
p_string(FILE * f,int len,UChar * s)5831 p_string(FILE* f, int len, UChar* s)
5832 {
5833   fputs(":", f);
5834   while (len-- > 0) { fputc(*s++, f); }
5835 }
5836 
5837 static void
p_len_string(FILE * f,LengthType len,int mb_len,UChar * s)5838 p_len_string(FILE* f, LengthType len, int mb_len, UChar* s)
5839 {
5840   int x = len * mb_len;
5841 
5842   fprintf(f, ":%d:", len);
5843   while (x-- > 0) { fputc(*s++, f); }
5844 }
5845 
5846 extern void
onig_print_compiled_byte_code(FILE * f,UChar * bp,UChar ** nextp,OnigEncoding enc)5847 onig_print_compiled_byte_code(FILE* f, UChar* bp, UChar** nextp,
5848                               OnigEncoding enc)
5849 {
5850   int i, n, arg_type;
5851   RelAddrType addr;
5852   LengthType len;
5853   MemNumType mem;
5854   StateCheckNumType scn;
5855   OnigCodePoint code;
5856   UChar *q;
5857 
5858   fprintf(f, "[%s", op2name(*bp));
5859   arg_type = op2arg_type(*bp);
5860   if (arg_type != ARG_SPECIAL) {
5861     bp++;
5862     switch (arg_type) {
5863     case ARG_NON:
5864       break;
5865     case ARG_RELADDR:
5866       GET_RELADDR_INC(addr, bp);
5867       fprintf(f, ":(%d)", addr);
5868       break;
5869     case ARG_ABSADDR:
5870       GET_ABSADDR_INC(addr, bp);
5871       fprintf(f, ":(%d)", addr);
5872       break;
5873     case ARG_LENGTH:
5874       GET_LENGTH_INC(len, bp);
5875       fprintf(f, ":%d", len);
5876       break;
5877     case ARG_MEMNUM:
5878       mem = *((MemNumType* )bp);
5879       bp += SIZE_MEMNUM;
5880       fprintf(f, ":%d", mem);
5881       break;
5882     case ARG_OPTION:
5883       {
5884 	OnigOptionType option = *((OnigOptionType* )bp);
5885 	bp += SIZE_OPTION;
5886 	fprintf(f, ":%d", option);
5887       }
5888       break;
5889 
5890     case ARG_STATE_CHECK:
5891       scn = *((StateCheckNumType* )bp);
5892       bp += SIZE_STATE_CHECK_NUM;
5893       fprintf(f, ":%d", scn);
5894       break;
5895     }
5896   }
5897   else {
5898     switch (*bp++) {
5899     case OP_EXACT1:
5900     case OP_ANYCHAR_STAR_PEEK_NEXT:
5901     case OP_ANYCHAR_ML_STAR_PEEK_NEXT:
5902       p_string(f, 1, bp++); break;
5903     case OP_EXACT2:
5904       p_string(f, 2, bp); bp += 2; break;
5905     case OP_EXACT3:
5906       p_string(f, 3, bp); bp += 3; break;
5907     case OP_EXACT4:
5908       p_string(f, 4, bp); bp += 4; break;
5909     case OP_EXACT5:
5910       p_string(f, 5, bp); bp += 5; break;
5911     case OP_EXACTN:
5912       GET_LENGTH_INC(len, bp);
5913       p_len_string(f, len, 1, bp);
5914       bp += len;
5915       break;
5916 
5917     case OP_EXACTMB2N1:
5918       p_string(f, 2, bp); bp += 2; break;
5919     case OP_EXACTMB2N2:
5920       p_string(f, 4, bp); bp += 4; break;
5921     case OP_EXACTMB2N3:
5922       p_string(f, 6, bp); bp += 6; break;
5923     case OP_EXACTMB2N:
5924       GET_LENGTH_INC(len, bp);
5925       p_len_string(f, len, 2, bp);
5926       bp += len * 2;
5927       break;
5928     case OP_EXACTMB3N:
5929       GET_LENGTH_INC(len, bp);
5930       p_len_string(f, len, 3, bp);
5931       bp += len * 3;
5932       break;
5933     case OP_EXACTMBN:
5934       {
5935 	int mb_len;
5936 
5937 	GET_LENGTH_INC(mb_len, bp);
5938 	GET_LENGTH_INC(len, bp);
5939 	fprintf(f, ":%d:%d:", mb_len, len);
5940 	n = len * mb_len;
5941 	while (n-- > 0) { fputc(*bp++, f); }
5942       }
5943       break;
5944 
5945     case OP_EXACT1_IC:
5946       len = enclen(enc, bp);
5947       p_string(f, len, bp);
5948       bp += len;
5949       break;
5950     case OP_EXACTN_IC:
5951       GET_LENGTH_INC(len, bp);
5952       p_len_string(f, len, 1, bp);
5953       bp += len;
5954       break;
5955 
5956     case OP_CCLASS:
5957       n = bitset_on_num((BitSetRef )bp);
5958       bp += SIZE_BITSET;
5959       fprintf(f, ":%d", n);
5960       break;
5961 
5962     case OP_CCLASS_NOT:
5963       n = bitset_on_num((BitSetRef )bp);
5964       bp += SIZE_BITSET;
5965       fprintf(f, ":%d", n);
5966       break;
5967 
5968     case OP_CCLASS_MB:
5969     case OP_CCLASS_MB_NOT:
5970       GET_LENGTH_INC(len, bp);
5971       q = bp;
5972 #ifndef PLATFORM_UNALIGNED_WORD_ACCESS
5973       ALIGNMENT_RIGHT(q);
5974 #endif
5975       GET_CODE_POINT(code, q);
5976       bp += len;
5977       fprintf(f, ":%d:%d", (int )code, len);
5978       break;
5979 
5980     case OP_CCLASS_MIX:
5981     case OP_CCLASS_MIX_NOT:
5982       n = bitset_on_num((BitSetRef )bp);
5983       bp += SIZE_BITSET;
5984       GET_LENGTH_INC(len, bp);
5985       q = bp;
5986 #ifndef PLATFORM_UNALIGNED_WORD_ACCESS
5987       ALIGNMENT_RIGHT(q);
5988 #endif
5989       GET_CODE_POINT(code, q);
5990       bp += len;
5991       fprintf(f, ":%d:%d:%d", n, (int )code, len);
5992       break;
5993 
5994     case OP_CCLASS_NODE:
5995       {
5996         CClassNode *cc;
5997 
5998         GET_POINTER_INC(cc, bp);
5999         n = bitset_on_num(cc->bs);
6000         fprintf(f, ":%u:%d", (unsigned int )cc, n);
6001       }
6002       break;
6003 
6004     case OP_BACKREFN_IC:
6005       mem = *((MemNumType* )bp);
6006       bp += SIZE_MEMNUM;
6007       fprintf(f, ":%d", mem);
6008       break;
6009 
6010     case OP_BACKREF_MULTI_IC:
6011     case OP_BACKREF_MULTI:
6012       fputs(" ", f);
6013       GET_LENGTH_INC(len, bp);
6014       for (i = 0; i < len; i++) {
6015 	GET_MEMNUM_INC(mem, bp);
6016 	if (i > 0) fputs(", ", f);
6017 	fprintf(f, "%d", mem);
6018       }
6019       break;
6020 
6021     case OP_BACKREF_WITH_LEVEL:
6022       {
6023 	OnigOptionType option;
6024 	LengthType level;
6025 
6026 	GET_OPTION_INC(option, bp);
6027 	fprintf(f, ":%d", option);
6028 	GET_LENGTH_INC(level, bp);
6029 	fprintf(f, ":%d", level);
6030 
6031 	fputs(" ", f);
6032 	GET_LENGTH_INC(len, bp);
6033 	for (i = 0; i < len; i++) {
6034 	  GET_MEMNUM_INC(mem, bp);
6035 	  if (i > 0) fputs(", ", f);
6036 	  fprintf(f, "%d", mem);
6037 	}
6038       }
6039       break;
6040 
6041     case OP_REPEAT:
6042     case OP_REPEAT_NG:
6043       {
6044 	mem = *((MemNumType* )bp);
6045 	bp += SIZE_MEMNUM;
6046 	addr = *((RelAddrType* )bp);
6047 	bp += SIZE_RELADDR;
6048 	fprintf(f, ":%d:%d", mem, addr);
6049       }
6050       break;
6051 
6052     case OP_PUSH_OR_JUMP_EXACT1:
6053     case OP_PUSH_IF_PEEK_NEXT:
6054       addr = *((RelAddrType* )bp);
6055       bp += SIZE_RELADDR;
6056       fprintf(f, ":(%d)", addr);
6057       p_string(f, 1, bp);
6058       bp += 1;
6059       break;
6060 
6061     case OP_LOOK_BEHIND:
6062       GET_LENGTH_INC(len, bp);
6063       fprintf(f, ":%d", len);
6064       break;
6065 
6066     case OP_PUSH_LOOK_BEHIND_NOT:
6067       GET_RELADDR_INC(addr, bp);
6068       GET_LENGTH_INC(len, bp);
6069       fprintf(f, ":%d:(%d)", len, addr);
6070       break;
6071 
6072     case OP_STATE_CHECK_PUSH:
6073     case OP_STATE_CHECK_PUSH_OR_JUMP:
6074       scn = *((StateCheckNumType* )bp);
6075       bp += SIZE_STATE_CHECK_NUM;
6076       addr = *((RelAddrType* )bp);
6077       bp += SIZE_RELADDR;
6078       fprintf(f, ":%d:(%d)", scn, addr);
6079       break;
6080 
6081     default:
6082       fprintf(stderr, "onig_print_compiled_byte_code: undefined code %d\n",
6083 	      *--bp);
6084     }
6085   }
6086   fputs("]", f);
6087   if (nextp) *nextp = bp;
6088 }
6089 
6090 static void
print_compiled_byte_code_list(FILE * f,regex_t * reg)6091 print_compiled_byte_code_list(FILE* f, regex_t* reg)
6092 {
6093   int ncode;
6094   UChar* bp = reg->p;
6095   UChar* end = reg->p + reg->used;
6096 
6097   fprintf(f, "code length: %d\n", reg->used);
6098 
6099   ncode = 0;
6100   while (bp < end) {
6101     ncode++;
6102     if (bp > reg->p) {
6103       if (ncode % 5 == 0)
6104 	fprintf(f, "\n");
6105       else
6106 	fputs(" ", f);
6107     }
6108     onig_print_compiled_byte_code(f, bp, &bp, reg->enc);
6109   }
6110 
6111   fprintf(f, "\n");
6112 }
6113 
6114 static void
print_indent_tree(FILE * f,Node * node,int indent)6115 print_indent_tree(FILE* f, Node* node, int indent)
6116 {
6117   int i, type;
6118   int add = 3;
6119   UChar* p;
6120 
6121   Indent(f, indent);
6122   if (IS_NULL(node)) {
6123     fprintf(f, "ERROR: null node!!!\n");
6124     exit (0);
6125   }
6126 
6127   type = NTYPE(node);
6128   switch (type) {
6129   case NT_LIST:
6130   case NT_ALT:
6131     if (NTYPE(node) == NT_LIST)
6132       fprintf(f, "<list:%x>\n", (int )node);
6133     else
6134       fprintf(f, "<alt:%x>\n", (int )node);
6135 
6136     print_indent_tree(f, NCAR(node), indent + add);
6137     while (IS_NOT_NULL(node = NCDR(node))) {
6138       if (NTYPE(node) != type) {
6139 	fprintf(f, "ERROR: list/alt right is not a cons. %d\n", NTYPE(node));
6140 	exit(0);
6141       }
6142       print_indent_tree(f, NCAR(node), indent + add);
6143     }
6144     break;
6145 
6146   case NT_STR:
6147     fprintf(f, "<string%s:%x>",
6148 	    (NSTRING_IS_RAW(node) ? "-raw" : ""), (int )node);
6149     for (p = NSTR(node)->s; p < NSTR(node)->end; p++) {
6150       if (*p >= 0x20 && *p < 0x7f)
6151 	fputc(*p, f);
6152       else {
6153 	fprintf(f, " 0x%02x", *p);
6154       }
6155     }
6156     break;
6157 
6158   case NT_CCLASS:
6159     fprintf(f, "<cclass:%x>", (int )node);
6160     if (IS_NCCLASS_NOT(NCCLASS(node))) fputs(" not", f);
6161     if (NCCLASS(node)->mbuf) {
6162       BBuf* bbuf = NCCLASS(node)->mbuf;
6163       for (i = 0; i < bbuf->used; i++) {
6164 	if (i > 0) fprintf(f, ",");
6165 	fprintf(f, "%0x", bbuf->p[i]);
6166       }
6167     }
6168     break;
6169 
6170   case NT_CTYPE:
6171     fprintf(f, "<ctype:%x> ", (int )node);
6172     switch (NCTYPE(node)->ctype) {
6173     case ONIGENC_CTYPE_WORD:
6174       if (NCTYPE(node)->not != 0)
6175 	fputs("not word",       f);
6176       else
6177 	fputs("word",           f);
6178       break;
6179 
6180     default:
6181       fprintf(f, "ERROR: undefined ctype.\n");
6182       exit(0);
6183     }
6184     break;
6185 
6186   case NT_CANY:
6187     fprintf(f, "<anychar:%x>", (int )node);
6188     break;
6189 
6190   case NT_ANCHOR:
6191     fprintf(f, "<anchor:%x> ", (int )node);
6192     switch (NANCHOR(node)->type) {
6193     case ANCHOR_BEGIN_BUF:      fputs("begin buf",      f); break;
6194     case ANCHOR_END_BUF:        fputs("end buf",        f); break;
6195     case ANCHOR_BEGIN_LINE:     fputs("begin line",     f); break;
6196     case ANCHOR_END_LINE:       fputs("end line",       f); break;
6197     case ANCHOR_SEMI_END_BUF:   fputs("semi end buf",   f); break;
6198     case ANCHOR_BEGIN_POSITION: fputs("begin position", f); break;
6199 
6200     case ANCHOR_WORD_BOUND:      fputs("word bound",     f); break;
6201     case ANCHOR_NOT_WORD_BOUND:  fputs("not word bound", f); break;
6202 #ifdef USE_WORD_BEGIN_END
6203     case ANCHOR_WORD_BEGIN:      fputs("word begin", f);     break;
6204     case ANCHOR_WORD_END:        fputs("word end", f);       break;
6205 #endif
6206     case ANCHOR_PREC_READ:       fputs("prec read",      f); break;
6207     case ANCHOR_PREC_READ_NOT:   fputs("prec read not",  f); break;
6208     case ANCHOR_LOOK_BEHIND:     fputs("look_behind",    f); break;
6209     case ANCHOR_LOOK_BEHIND_NOT: fputs("look_behind_not",f); break;
6210 
6211     default:
6212       fprintf(f, "ERROR: undefined anchor type.\n");
6213       break;
6214     }
6215     break;
6216 
6217   case NT_BREF:
6218     {
6219       int* p;
6220       BRefNode* br = NBREF(node);
6221       p = BACKREFS_P(br);
6222       fprintf(f, "<backref:%x>", (int )node);
6223       for (i = 0; i < br->back_num; i++) {
6224 	if (i > 0) fputs(", ", f);
6225 	fprintf(f, "%d", p[i]);
6226       }
6227     }
6228     break;
6229 
6230 #ifdef USE_SUBEXP_CALL
6231   case NT_CALL:
6232     {
6233       CallNode* cn = NCALL(node);
6234       fprintf(f, "<call:%x>", (int )node);
6235       p_string(f, cn->name_end - cn->name, cn->name);
6236     }
6237     break;
6238 #endif
6239 
6240   case NT_QTFR:
6241     fprintf(f, "<quantifier:%x>{%d,%d}%s\n", (int )node,
6242 	    NQTFR(node)->lower, NQTFR(node)->upper,
6243 	    (NQTFR(node)->greedy ? "" : "?"));
6244     print_indent_tree(f, NQTFR(node)->target, indent + add);
6245     break;
6246 
6247   case NT_ENCLOSE:
6248     fprintf(f, "<enclose:%x> ", (int )node);
6249     switch (NENCLOSE(node)->type) {
6250     case ENCLOSE_OPTION:
6251       fprintf(f, "option:%d", NENCLOSE(node)->option);
6252       break;
6253     case ENCLOSE_MEMORY:
6254       fprintf(f, "memory:%d", NENCLOSE(node)->regnum);
6255       break;
6256     case ENCLOSE_STOP_BACKTRACK:
6257       fprintf(f, "stop-bt");
6258       break;
6259 
6260     default:
6261       break;
6262     }
6263     fprintf(f, "\n");
6264     print_indent_tree(f, NENCLOSE(node)->target, indent + add);
6265     break;
6266 
6267   default:
6268     fprintf(f, "print_indent_tree: undefined node type %d\n", NTYPE(node));
6269     break;
6270   }
6271 
6272   if (type != NT_LIST && type != NT_ALT && type != NT_QTFR &&
6273       type != NT_ENCLOSE)
6274     fprintf(f, "\n");
6275   fflush(f);
6276 }
6277 #endif /* ONIG_DEBUG */
6278 
6279 #ifdef ONIG_DEBUG_PARSE_TREE
6280 static void
print_tree(FILE * f,Node * node)6281 print_tree(FILE* f, Node* node)
6282 {
6283   print_indent_tree(f, node, 0);
6284 }
6285 #endif
6286