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