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