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