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