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