1 /********************************************************************** 2 regparse.c - Oniguruma (regular expression library) 3 **********************************************************************/ 4 /*- 5 * Copyright (c) 2002-2008 K.Kosako <sndgk393 AT ybb DOT ne DOT jp> 6 * All rights reserved. 7 * 8 * (C) Copyright 2015 Hewlett Packard Enterprise Development LP<BR> 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 */ 31 32 #include "regparse.h" 33 #include "st.h" 34 35 #define WARN_BUFSIZE 256 36 37 #define CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS 38 39 40 OnigSyntaxType OnigSyntaxRuby = { 41 (( SYN_GNU_REGEX_OP | ONIG_SYN_OP_QMARK_NON_GREEDY | 42 ONIG_SYN_OP_ESC_OCTAL3 | ONIG_SYN_OP_ESC_X_HEX2 | 43 ONIG_SYN_OP_ESC_X_BRACE_HEX8 | ONIG_SYN_OP_ESC_CONTROL_CHARS | 44 ONIG_SYN_OP_ESC_C_CONTROL ) 45 & ~ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END ) 46 , ( ONIG_SYN_OP2_QMARK_GROUP_EFFECT | 47 ONIG_SYN_OP2_OPTION_RUBY | 48 ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP | ONIG_SYN_OP2_ESC_K_NAMED_BACKREF | 49 ONIG_SYN_OP2_ESC_G_SUBEXP_CALL | 50 ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY | 51 ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT | 52 ONIG_SYN_OP2_PLUS_POSSESSIVE_REPEAT | 53 ONIG_SYN_OP2_CCLASS_SET_OP | ONIG_SYN_OP2_ESC_CAPITAL_C_BAR_CONTROL | 54 ONIG_SYN_OP2_ESC_CAPITAL_M_BAR_META | ONIG_SYN_OP2_ESC_V_VTAB | 55 ONIG_SYN_OP2_ESC_H_XDIGIT ) 56 , ( SYN_GNU_REGEX_BV | 57 ONIG_SYN_ALLOW_INTERVAL_LOW_ABBREV | 58 ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND | 59 ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP | 60 ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME | 61 ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY | 62 ONIG_SYN_WARN_CC_OP_NOT_ESCAPED | 63 ONIG_SYN_WARN_REDUNDANT_NESTED_REPEAT ) 64 , ONIG_OPTION_NONE 65 , 66 { 67 (OnigCodePoint )'\\' /* esc */ 68 , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar '.' */ 69 , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anytime '*' */ 70 , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* zero or one time '?' */ 71 , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* one or more time '+' */ 72 , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar anytime */ 73 } 74 }; 75 76 OnigSyntaxType* OnigDefaultSyntax = ONIG_SYNTAX_RUBY; 77 78 extern void onig_null_warn(const char* s ARG_UNUSED) { } 79 80 #ifdef DEFAULT_WARN_FUNCTION 81 static OnigWarnFunc onig_warn = (OnigWarnFunc )DEFAULT_WARN_FUNCTION; 82 #else 83 static OnigWarnFunc onig_warn = onig_null_warn; 84 #endif 85 86 #ifdef DEFAULT_VERB_WARN_FUNCTION 87 static OnigWarnFunc onig_verb_warn = (OnigWarnFunc )DEFAULT_VERB_WARN_FUNCTION; 88 #else 89 static OnigWarnFunc onig_verb_warn = onig_null_warn; 90 #endif 91 92 extern void onig_set_warn_func(OnigWarnFunc f) 93 { 94 onig_warn = f; 95 } 96 97 extern void onig_set_verb_warn_func(OnigWarnFunc f) 98 { 99 onig_verb_warn = f; 100 } 101 102 static void 103 bbuf_free(BBuf* bbuf) 104 { 105 if (IS_NOT_NULL(bbuf)) { 106 if (IS_NOT_NULL(bbuf->p)) xfree(bbuf->p); 107 xfree(bbuf); 108 } 109 } 110 111 static int 112 bbuf_clone(BBuf** rto, BBuf* from) 113 { 114 int r; 115 BBuf *to; 116 117 *rto = to = (BBuf* )xmalloc(sizeof(BBuf)); 118 CHECK_NULL_RETURN_MEMERR(to); 119 r = BBUF_INIT(to, from->alloc); 120 if (r != 0) return r; 121 to->used = from->used; 122 xmemcpy(to->p, from->p, from->used); 123 return 0; 124 } 125 126 #define BACKREF_REL_TO_ABS(rel_no, env) \ 127 ((env)->num_mem + 1 + (rel_no)) 128 129 #define ONOFF(v,f,negative) (negative) ? ((v) &= ~(f)) : ((v) |= (f)) 130 131 #define MBCODE_START_POS(enc) \ 132 (OnigCodePoint )(ONIGENC_MBC_MINLEN(enc) > 1 ? 0 : 0x80) 133 134 #define SET_ALL_MULTI_BYTE_RANGE(enc, pbuf) \ 135 add_code_range_to_buf(pbuf, MBCODE_START_POS(enc), ~((OnigCodePoint )0)) 136 137 #define ADD_ALL_MULTI_BYTE_RANGE(enc, mbuf) do {\ 138 if (! ONIGENC_IS_SINGLEBYTE(enc)) {\ 139 r = SET_ALL_MULTI_BYTE_RANGE(enc, &(mbuf));\ 140 if (r) return r;\ 141 }\ 142 } while (0) 143 144 145 #define BITSET_IS_EMPTY(bs,empty) do {\ 146 int i;\ 147 empty = 1;\ 148 for (i = 0; i < (int )BITSET_SIZE; i++) {\ 149 if ((bs)[i] != 0) {\ 150 empty = 0; break;\ 151 }\ 152 }\ 153 } while (0) 154 155 static void 156 bitset_set_range(BitSetRef bs, int from, int to) 157 { 158 int i; 159 for (i = from; i <= to && i < SINGLE_BYTE_SIZE; i++) { 160 BITSET_SET_BIT(bs, i); 161 } 162 } 163 164 #if 0 165 static void 166 bitset_set_all(BitSetRef bs) 167 { 168 int i; 169 for (i = 0; i < BITSET_SIZE; i++) { bs[i] = ~((Bits )0); } 170 } 171 #endif 172 173 static void 174 bitset_invert(BitSetRef bs) 175 { 176 int i; 177 for (i = 0; i < (int )BITSET_SIZE; i++) { bs[i] = ~(bs[i]); } 178 } 179 180 static void 181 bitset_invert_to(BitSetRef from, BitSetRef to) 182 { 183 int i; 184 for (i = 0; i < (int )BITSET_SIZE; i++) { to[i] = ~(from[i]); } 185 } 186 187 static void 188 bitset_and(BitSetRef dest, BitSetRef bs) 189 { 190 int i; 191 for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] &= bs[i]; } 192 } 193 194 static void 195 bitset_or(BitSetRef dest, BitSetRef bs) 196 { 197 int i; 198 for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] |= bs[i]; } 199 } 200 201 static void 202 bitset_copy(BitSetRef dest, BitSetRef bs) 203 { 204 int i; 205 for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] = bs[i]; } 206 } 207 208 extern int 209 onig_strncmp(const UChar* s1, const UChar* s2, int n) 210 { 211 int x; 212 213 while (n-- > 0) { 214 x = *s2++ - *s1++; 215 if (x) return x; 216 } 217 return 0; 218 } 219 220 extern void 221 onig_strcpy(UChar* dest, const UChar* src, const UChar* end) 222 { 223 int len = (int)(end - src); 224 if (len > 0) { 225 xmemcpy(dest, src, len); 226 dest[len] = (UChar )0; 227 } 228 } 229 230 #ifdef USE_NAMED_GROUP 231 static UChar* 232 strdup_with_null(OnigEncoding enc, UChar* s, UChar* end) 233 { 234 int slen, term_len, i; 235 UChar *r; 236 237 slen = (int)(end - s); 238 term_len = ONIGENC_MBC_MINLEN(enc); 239 240 r = (UChar* )xmalloc(slen + term_len); 241 CHECK_NULL_RETURN(r); 242 xmemcpy(r, s, slen); 243 244 for (i = 0; i < term_len; i++) 245 r[slen + i] = (UChar )0; 246 247 return r; 248 } 249 #endif 250 251 /* scan pattern methods */ 252 #define PEND_VALUE 0 253 254 #define PFETCH_READY UChar* pfetch_prev 255 #define PEND (p < end ? 0 : 1) 256 #define PUNFETCH p = pfetch_prev 257 #define PINC do { \ 258 pfetch_prev = p; \ 259 p += ONIGENC_MBC_ENC_LEN(enc, p); \ 260 } while (0) 261 #define PFETCH(c) do { \ 262 c = ONIGENC_MBC_TO_CODE(enc, p, end); \ 263 pfetch_prev = p; \ 264 p += ONIGENC_MBC_ENC_LEN(enc, p); \ 265 } while (0) 266 267 #define PINC_S do { \ 268 p += ONIGENC_MBC_ENC_LEN(enc, p); \ 269 } while (0) 270 #define PFETCH_S(c) do { \ 271 c = ONIGENC_MBC_TO_CODE(enc, p, end); \ 272 p += ONIGENC_MBC_ENC_LEN(enc, p); \ 273 } while (0) 274 275 #define PPEEK (p < end ? ONIGENC_MBC_TO_CODE(enc, p, end) : PEND_VALUE) 276 #define PPEEK_IS(c) (PPEEK == (OnigCodePoint )c) 277 278 static UChar* 279 strcat_capa(UChar* dest, UChar* dest_end, const UChar* src, const UChar* src_end, 280 int capa, int oldCapa) 281 { 282 UChar* r; 283 284 if (dest) 285 r = (UChar* )xrealloc(dest, capa + 1, oldCapa); 286 else 287 r = (UChar* )xmalloc(capa + 1); 288 289 CHECK_NULL_RETURN(r); 290 onig_strcpy(r + (dest_end - dest), src, src_end); 291 return r; 292 } 293 294 /* dest on static area */ 295 static UChar* 296 strcat_capa_from_static(UChar* dest, UChar* dest_end, 297 const UChar* src, const UChar* src_end, int capa) 298 { 299 UChar* r; 300 301 r = (UChar* )xmalloc(capa + 1); 302 CHECK_NULL_RETURN(r); 303 onig_strcpy(r, dest, dest_end); 304 onig_strcpy(r + (dest_end - dest), src, src_end); 305 return r; 306 } 307 308 309 #ifdef USE_ST_LIBRARY 310 311 typedef struct { 312 UChar* s; 313 UChar* end; 314 } st_str_end_key; 315 316 static int 317 str_end_cmp(st_str_end_key* x, st_str_end_key* y) 318 { 319 UChar *p, *q; 320 int c; 321 322 if ((x->end - x->s) != (y->end - y->s)) 323 return 1; 324 325 p = x->s; 326 q = y->s; 327 while (p < x->end) { 328 c = (int )*p - (int )*q; 329 if (c != 0) return c; 330 331 p++; q++; 332 } 333 334 return 0; 335 } 336 337 static int 338 str_end_hash(st_str_end_key* x) 339 { 340 UChar *p; 341 int val = 0; 342 343 p = x->s; 344 while (p < x->end) { 345 val = val * 997 + (int )*p++; 346 } 347 348 return val + (val >> 5); 349 } 350 351 extern hash_table_type* 352 onig_st_init_strend_table_with_size(int size) 353 { 354 static struct st_hash_type hashType = { 355 str_end_cmp, 356 str_end_hash, 357 }; 358 359 return (hash_table_type* ) 360 onig_st_init_table_with_size(&hashType, size); 361 } 362 363 extern int 364 onig_st_lookup_strend(hash_table_type* table, const UChar* str_key, 365 const UChar* end_key, hash_data_type *value) 366 { 367 st_str_end_key key; 368 369 key.s = (UChar* )str_key; 370 key.end = (UChar* )end_key; 371 372 return onig_st_lookup(table, (st_data_t )(UINTN)(&key), value); 373 } 374 375 extern int 376 onig_st_insert_strend(hash_table_type* table, const UChar* str_key, 377 const UChar* end_key, hash_data_type value) 378 { 379 st_str_end_key* key; 380 int result; 381 382 key = (st_str_end_key* )xmalloc(sizeof(st_str_end_key)); 383 CHECK_NULL_RETURN_MEMERR(key); 384 key->s = (UChar* )str_key; 385 key->end = (UChar* )end_key; 386 result = onig_st_insert(table, (st_data_t )(UINTN)key, value); 387 if (result) { 388 xfree(key); 389 } 390 return result; 391 } 392 393 #endif /* USE_ST_LIBRARY */ 394 395 396 #ifdef USE_NAMED_GROUP 397 398 #define INIT_NAME_BACKREFS_ALLOC_NUM 8 399 400 typedef struct { 401 UChar* name; 402 int name_len; /* byte length */ 403 int back_num; /* number of backrefs */ 404 int back_alloc; 405 int back_ref1; 406 int* back_refs; 407 } NameEntry; 408 409 #ifdef USE_ST_LIBRARY 410 411 typedef st_table NameTable; 412 typedef st_data_t HashDataType; /* 1.6 st.h doesn't define st_data_t type */ 413 414 #define NAMEBUF_SIZE 24 415 #define NAMEBUF_SIZE_1 25 416 417 #ifdef ONIG_DEBUG 418 static int 419 i_print_name_entry(UChar* key, NameEntry* e, void* arg) 420 { 421 int i; 422 FILE* fp = (FILE* )arg; 423 424 fprintf(fp, "%s: ", e->name); 425 if (e->back_num == 0) 426 fputs("-", fp); 427 else if (e->back_num == 1) 428 fprintf(fp, "%d", e->back_ref1); 429 else { 430 for (i = 0; i < e->back_num; i++) { 431 if (i > 0) fprintf(fp, ", "); 432 fprintf(fp, "%d", e->back_refs[i]); 433 } 434 } 435 fputs("\n", fp); 436 return ST_CONTINUE; 437 } 438 439 extern int 440 onig_print_names(FILE* fp, regex_t* reg) 441 { 442 NameTable* t = (NameTable* )reg->name_table; 443 444 if (IS_NOT_NULL(t)) { 445 fprintf(fp, "name table\n"); 446 onig_st_foreach(t, i_print_name_entry, (HashDataType )fp); 447 fputs("\n", fp); 448 } 449 return 0; 450 } 451 #endif /* ONIG_DEBUG */ 452 453 static int 454 i_free_name_entry(UChar* key, NameEntry* e, void* arg ARG_UNUSED) 455 { 456 xfree(e->name); 457 if (IS_NOT_NULL(e->back_refs)) xfree(e->back_refs); 458 xfree(key); 459 xfree(e); 460 return ST_DELETE; 461 } 462 463 static int 464 names_clear(regex_t* reg) 465 { 466 NameTable* t = (NameTable* )reg->name_table; 467 468 if (IS_NOT_NULL(t)) { 469 onig_st_foreach(t, i_free_name_entry, 0); 470 } 471 return 0; 472 } 473 474 extern int 475 onig_names_free(regex_t* reg) 476 { 477 int r; 478 NameTable* t; 479 480 r = names_clear(reg); 481 if (r) return r; 482 483 t = (NameTable* )reg->name_table; 484 if (IS_NOT_NULL(t)) onig_st_free_table(t); 485 reg->name_table = (void* )NULL; 486 return 0; 487 } 488 489 static NameEntry* 490 name_find(regex_t* reg, const UChar* name, const UChar* name_end) 491 { 492 NameEntry* e; 493 NameTable* t = (NameTable* )reg->name_table; 494 495 e = (NameEntry* )NULL; 496 if (IS_NOT_NULL(t)) { 497 onig_st_lookup_strend(t, name, name_end, (HashDataType* )((void* )(&e))); 498 } 499 return e; 500 } 501 502 typedef struct { 503 int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*); 504 regex_t* reg; 505 void* arg; 506 int ret; 507 OnigEncoding enc; 508 } INamesArg; 509 510 static int 511 i_names(UChar* key ARG_UNUSED, NameEntry* e, INamesArg* arg) 512 { 513 int r = (*(arg->func))(e->name, 514 e->name + e->name_len, 515 e->back_num, 516 (e->back_num > 1 ? e->back_refs : &(e->back_ref1)), 517 arg->reg, arg->arg); 518 if (r != 0) { 519 arg->ret = r; 520 return ST_STOP; 521 } 522 return ST_CONTINUE; 523 } 524 525 extern int 526 onig_foreach_name(regex_t* reg, 527 int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*), void* arg) 528 { 529 INamesArg narg; 530 NameTable* t = (NameTable* )reg->name_table; 531 532 narg.ret = 0; 533 if (IS_NOT_NULL(t)) { 534 narg.func = func; 535 narg.reg = reg; 536 narg.arg = arg; 537 narg.enc = reg->enc; /* should be pattern encoding. */ 538 onig_st_foreach(t, i_names, (HashDataType )(UINTN)&narg); 539 } 540 return narg.ret; 541 } 542 543 static int 544 i_renumber_name(UChar* key ARG_UNUSED, NameEntry* e, GroupNumRemap* map) 545 { 546 int i; 547 548 if (e->back_num > 1) { 549 for (i = 0; i < e->back_num; i++) { 550 e->back_refs[i] = map[e->back_refs[i]].new_val; 551 } 552 } 553 else if (e->back_num == 1) { 554 e->back_ref1 = map[e->back_ref1].new_val; 555 } 556 557 return ST_CONTINUE; 558 } 559 560 extern int 561 onig_renumber_name_table(regex_t* reg, GroupNumRemap* map) 562 { 563 NameTable* t = (NameTable* )reg->name_table; 564 565 if (IS_NOT_NULL(t)) { 566 onig_st_foreach(t, i_renumber_name, (HashDataType )(UINTN)map); 567 } 568 return 0; 569 } 570 571 572 extern int 573 onig_number_of_names(regex_t* reg) 574 { 575 NameTable* t = (NameTable* )reg->name_table; 576 577 if (IS_NOT_NULL(t)) 578 return t->num_entries; 579 else 580 return 0; 581 } 582 583 #else /* USE_ST_LIBRARY */ 584 585 #define INIT_NAMES_ALLOC_NUM 8 586 587 typedef struct { 588 NameEntry* e; 589 int num; 590 int alloc; 591 } NameTable; 592 593 #ifdef ONIG_DEBUG 594 extern int 595 onig_print_names(FILE* fp, regex_t* reg) 596 { 597 int i, j; 598 NameEntry* e; 599 NameTable* t = (NameTable* )reg->name_table; 600 601 if (IS_NOT_NULL(t) && t->num > 0) { 602 fprintf(fp, "name table\n"); 603 for (i = 0; i < t->num; i++) { 604 e = &(t->e[i]); 605 fprintf(fp, "%s: ", e->name); 606 if (e->back_num == 0) { 607 fputs("-", fp); 608 } 609 else if (e->back_num == 1) { 610 fprintf(fp, "%d", e->back_ref1); 611 } 612 else { 613 for (j = 0; j < e->back_num; j++) { 614 if (j > 0) fprintf(fp, ", "); 615 fprintf(fp, "%d", e->back_refs[j]); 616 } 617 } 618 fputs("\n", fp); 619 } 620 fputs("\n", fp); 621 } 622 return 0; 623 } 624 #endif 625 626 static int 627 names_clear(regex_t* reg) 628 { 629 int i; 630 NameEntry* e; 631 NameTable* t = (NameTable* )reg->name_table; 632 633 if (IS_NOT_NULL(t)) { 634 for (i = 0; i < t->num; i++) { 635 e = &(t->e[i]); 636 if (IS_NOT_NULL(e->name)) { 637 xfree(e->name); 638 e->name = NULL; 639 e->name_len = 0; 640 e->back_num = 0; 641 e->back_alloc = 0; 642 if (IS_NOT_NULL(e->back_refs)) xfree(e->back_refs); 643 e->back_refs = (int* )NULL; 644 } 645 } 646 if (IS_NOT_NULL(t->e)) { 647 xfree(t->e); 648 t->e = NULL; 649 } 650 t->num = 0; 651 } 652 return 0; 653 } 654 655 extern int 656 onig_names_free(regex_t* reg) 657 { 658 int r; 659 NameTable* t; 660 661 r = names_clear(reg); 662 if (r) return r; 663 664 t = (NameTable* )reg->name_table; 665 if (IS_NOT_NULL(t)) xfree(t); 666 reg->name_table = NULL; 667 return 0; 668 } 669 670 static NameEntry* 671 name_find(regex_t* reg, UChar* name, UChar* name_end) 672 { 673 int i, len; 674 NameEntry* e; 675 NameTable* t = (NameTable* )reg->name_table; 676 677 if (IS_NOT_NULL(t)) { 678 len = name_end - name; 679 for (i = 0; i < t->num; i++) { 680 e = &(t->e[i]); 681 if (len == e->name_len && onig_strncmp(name, e->name, len) == 0) 682 return e; 683 } 684 } 685 return (NameEntry* )NULL; 686 } 687 688 extern int 689 onig_foreach_name(regex_t* reg, 690 int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*), void* arg) 691 { 692 int i, r; 693 NameEntry* e; 694 NameTable* t = (NameTable* )reg->name_table; 695 696 if (IS_NOT_NULL(t)) { 697 for (i = 0; i < t->num; i++) { 698 e = &(t->e[i]); 699 r = (*func)(e->name, e->name + e->name_len, e->back_num, 700 (e->back_num > 1 ? e->back_refs : &(e->back_ref1)), 701 reg, arg); 702 if (r != 0) return r; 703 } 704 } 705 return 0; 706 } 707 708 extern int 709 onig_number_of_names(regex_t* reg) 710 { 711 NameTable* t = (NameTable* )reg->name_table; 712 713 if (IS_NOT_NULL(t)) 714 return t->num; 715 else 716 return 0; 717 } 718 719 #endif /* else USE_ST_LIBRARY */ 720 721 static int 722 name_add(regex_t* reg, UChar* name, UChar* name_end, int backref, ScanEnv* env) 723 { 724 int alloc; 725 NameEntry* e; 726 NameTable* t = (NameTable* )reg->name_table; 727 728 if (name_end - name <= 0) 729 return ONIGERR_EMPTY_GROUP_NAME; 730 731 e = name_find(reg, name, name_end); 732 if (IS_NULL(e)) { 733 #ifdef USE_ST_LIBRARY 734 if (IS_NULL(t)) { 735 t = onig_st_init_strend_table_with_size(5); 736 CHECK_NULL_RETURN_MEMERR(t); 737 reg->name_table = (void* )t; 738 } 739 e = (NameEntry* )xmalloc(sizeof(NameEntry)); 740 CHECK_NULL_RETURN_MEMERR(e); 741 742 e->name = strdup_with_null(reg->enc, name, name_end); 743 if (IS_NULL(e->name)) { 744 xfree(e); return ONIGERR_MEMORY; 745 } 746 onig_st_insert_strend(t, e->name, (e->name + (name_end - name)), 747 (HashDataType )(UINTN)e); 748 749 e->name_len = (int)(name_end - name); 750 e->back_num = 0; 751 e->back_alloc = 0; 752 e->back_refs = (int* )NULL; 753 754 #else 755 756 if (IS_NULL(t)) { 757 alloc = INIT_NAMES_ALLOC_NUM; 758 t = (NameTable* )xmalloc(sizeof(NameTable)); 759 CHECK_NULL_RETURN_MEMERR(t); 760 t->e = NULL; 761 t->alloc = 0; 762 t->num = 0; 763 764 t->e = (NameEntry* )xmalloc(sizeof(NameEntry) * alloc); 765 if (IS_NULL(t->e)) { 766 xfree(t); 767 return ONIGERR_MEMORY; 768 } 769 t->alloc = alloc; 770 reg->name_table = t; 771 goto clear; 772 } 773 else if (t->num == t->alloc) { 774 int i; 775 776 alloc = t->alloc * 2; 777 t->e = (NameEntry* )xrealloc(t->e, sizeof(NameEntry) * alloc); 778 CHECK_NULL_RETURN_MEMERR(t->e); 779 t->alloc = alloc; 780 781 clear: 782 for (i = t->num; i < t->alloc; i++) { 783 t->e[i].name = NULL; 784 t->e[i].name_len = 0; 785 t->e[i].back_num = 0; 786 t->e[i].back_alloc = 0; 787 t->e[i].back_refs = (int* )NULL; 788 } 789 } 790 e = &(t->e[t->num]); 791 t->num++; 792 e->name = strdup_with_null(reg->enc, name, name_end); 793 if (IS_NULL(e->name)) return ONIGERR_MEMORY; 794 e->name_len = name_end - name; 795 #endif 796 } 797 798 if (e->back_num >= 1 && 799 ! IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME)) { 800 onig_scan_env_set_error_string(env, ONIGERR_MULTIPLEX_DEFINED_NAME, 801 name, name_end); 802 return ONIGERR_MULTIPLEX_DEFINED_NAME; 803 } 804 805 e->back_num++; 806 if (e->back_num == 1) { 807 e->back_ref1 = backref; 808 } 809 else { 810 if (e->back_num == 2) { 811 alloc = INIT_NAME_BACKREFS_ALLOC_NUM; 812 e->back_refs = (int* )xmalloc(sizeof(int) * alloc); 813 CHECK_NULL_RETURN_MEMERR(e->back_refs); 814 e->back_alloc = alloc; 815 e->back_refs[0] = e->back_ref1; 816 e->back_refs[1] = backref; 817 } 818 else { 819 if (e->back_num > e->back_alloc) { 820 alloc = e->back_alloc * 2; 821 e->back_refs = (int* )xrealloc(e->back_refs, sizeof(int) * alloc, sizeof(int) * e->back_alloc); 822 CHECK_NULL_RETURN_MEMERR(e->back_refs); 823 e->back_alloc = alloc; 824 } 825 e->back_refs[e->back_num - 1] = backref; 826 } 827 } 828 829 return 0; 830 } 831 832 extern int 833 onig_name_to_group_numbers(regex_t* reg, const UChar* name, 834 const UChar* name_end, int** nums) 835 { 836 NameEntry* e = name_find(reg, name, name_end); 837 838 if (IS_NULL(e)) return ONIGERR_UNDEFINED_NAME_REFERENCE; 839 840 switch (e->back_num) { 841 case 0: 842 break; 843 case 1: 844 *nums = &(e->back_ref1); 845 break; 846 default: 847 *nums = e->back_refs; 848 break; 849 } 850 return e->back_num; 851 } 852 853 extern int 854 onig_name_to_backref_number(regex_t* reg, const UChar* name, 855 const UChar* name_end, OnigRegion *region) 856 { 857 int i, n, *nums; 858 859 n = onig_name_to_group_numbers(reg, name, name_end, &nums); 860 if (n < 0) 861 return n; 862 else if (n == 0) 863 return ONIGERR_PARSER_BUG; 864 else if (n == 1) 865 return nums[0]; 866 else { 867 if (IS_NOT_NULL(region)) { 868 for (i = n - 1; i >= 0; i--) { 869 if (region->beg[nums[i]] != ONIG_REGION_NOTPOS) 870 return nums[i]; 871 } 872 } 873 return nums[n - 1]; 874 } 875 } 876 877 #else /* USE_NAMED_GROUP */ 878 879 extern int 880 onig_name_to_group_numbers(regex_t* reg, const UChar* name, 881 const UChar* name_end, int** nums) 882 { 883 return ONIG_NO_SUPPORT_CONFIG; 884 } 885 886 extern int 887 onig_name_to_backref_number(regex_t* reg, const UChar* name, 888 const UChar* name_end, OnigRegion* region) 889 { 890 return ONIG_NO_SUPPORT_CONFIG; 891 } 892 893 extern int 894 onig_foreach_name(regex_t* reg, 895 int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*), void* arg) 896 { 897 return ONIG_NO_SUPPORT_CONFIG; 898 } 899 900 extern int 901 onig_number_of_names(regex_t* reg) 902 { 903 return 0; 904 } 905 #endif /* else USE_NAMED_GROUP */ 906 907 extern int 908 onig_noname_group_capture_is_active(regex_t* reg) 909 { 910 if (ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_DONT_CAPTURE_GROUP)) 911 return 0; 912 913 #ifdef USE_NAMED_GROUP 914 if (onig_number_of_names(reg) > 0 && 915 IS_SYNTAX_BV(reg->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) && 916 !ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_CAPTURE_GROUP)) { 917 return 0; 918 } 919 #endif 920 921 return 1; 922 } 923 924 925 #define INIT_SCANENV_MEMNODES_ALLOC_SIZE 16 926 927 static void 928 scan_env_clear(ScanEnv* env) 929 { 930 int i; 931 932 BIT_STATUS_CLEAR(env->capture_history); 933 BIT_STATUS_CLEAR(env->bt_mem_start); 934 BIT_STATUS_CLEAR(env->bt_mem_end); 935 BIT_STATUS_CLEAR(env->backrefed_mem); 936 env->error = (UChar* )NULL; 937 env->error_end = (UChar* )NULL; 938 env->num_call = 0; 939 env->num_mem = 0; 940 #ifdef USE_NAMED_GROUP 941 env->num_named = 0; 942 #endif 943 env->mem_alloc = 0; 944 env->mem_nodes_dynamic = (Node** )NULL; 945 946 for (i = 0; i < SCANENV_MEMNODES_SIZE; i++) 947 env->mem_nodes_static[i] = NULL_NODE; 948 949 #ifdef USE_COMBINATION_EXPLOSION_CHECK 950 env->num_comb_exp_check = 0; 951 env->comb_exp_max_regnum = 0; 952 env->curr_max_regnum = 0; 953 env->has_recursion = 0; 954 #endif 955 } 956 957 static int 958 scan_env_add_mem_entry(ScanEnv* env) 959 { 960 int i, need, alloc; 961 Node** p; 962 963 need = env->num_mem + 1; 964 if (need >= SCANENV_MEMNODES_SIZE) { 965 if (env->mem_alloc <= need) { 966 if (IS_NULL(env->mem_nodes_dynamic)) { 967 alloc = INIT_SCANENV_MEMNODES_ALLOC_SIZE; 968 p = (Node** )xmalloc(sizeof(Node*) * alloc); 969 CHECK_NULL_RETURN_MEMERR(p); 970 971 xmemcpy(p, env->mem_nodes_static, 972 sizeof(Node*) * SCANENV_MEMNODES_SIZE); 973 } 974 else { 975 alloc = env->mem_alloc * 2; 976 p = (Node** )xrealloc(env->mem_nodes_dynamic, sizeof(Node*) * alloc, sizeof(Node*) * env->mem_alloc); 977 } 978 CHECK_NULL_RETURN_MEMERR(p); 979 980 for (i = env->num_mem + 1; i < alloc; i++) 981 p[i] = NULL_NODE; 982 983 env->mem_nodes_dynamic = p; 984 env->mem_alloc = alloc; 985 } 986 } 987 988 env->num_mem++; 989 return env->num_mem; 990 } 991 992 static int 993 scan_env_set_mem_node(ScanEnv* env, int num, Node* node) 994 { 995 if (env->num_mem >= num) 996 SCANENV_MEM_NODES(env)[num] = node; 997 else 998 return ONIGERR_PARSER_BUG; 999 return 0; 1000 } 1001 1002 1003 #ifdef USE_PARSE_TREE_NODE_RECYCLE 1004 typedef struct _FreeNode { 1005 struct _FreeNode* next; 1006 } FreeNode; 1007 1008 static FreeNode* FreeNodeList = (FreeNode* )NULL; 1009 #endif 1010 1011 extern void 1012 onig_node_free(Node* node) 1013 { 1014 start: 1015 if (IS_NULL(node)) return ; 1016 1017 switch (NTYPE(node)) { 1018 case NT_STR: 1019 if (NSTR(node)->capa != 0 && 1020 IS_NOT_NULL(NSTR(node)->s) && NSTR(node)->s != NSTR(node)->buf) { 1021 xfree(NSTR(node)->s); 1022 } 1023 break; 1024 1025 case NT_LIST: 1026 case NT_ALT: 1027 onig_node_free(NCAR(node)); 1028 { 1029 Node* next_node = NCDR(node); 1030 1031 #ifdef USE_PARSE_TREE_NODE_RECYCLE 1032 { 1033 FreeNode* n = (FreeNode* )node; 1034 1035 THREAD_ATOMIC_START; 1036 n->next = FreeNodeList; 1037 FreeNodeList = n; 1038 THREAD_ATOMIC_END; 1039 } 1040 #else 1041 xfree(node); 1042 #endif 1043 node = next_node; 1044 goto start; 1045 } 1046 break; 1047 1048 case NT_CCLASS: 1049 { 1050 CClassNode* cc = NCCLASS(node); 1051 1052 if (IS_NCCLASS_SHARE(cc)) return ; 1053 if (cc->mbuf) 1054 bbuf_free(cc->mbuf); 1055 } 1056 break; 1057 1058 case NT_QTFR: 1059 if (NQTFR(node)->target) 1060 onig_node_free(NQTFR(node)->target); 1061 break; 1062 1063 case NT_ENCLOSE: 1064 if (NENCLOSE(node)->target) 1065 onig_node_free(NENCLOSE(node)->target); 1066 break; 1067 1068 case NT_BREF: 1069 if (IS_NOT_NULL(NBREF(node)->back_dynamic)) 1070 xfree(NBREF(node)->back_dynamic); 1071 break; 1072 1073 case NT_ANCHOR: 1074 if (NANCHOR(node)->target) 1075 onig_node_free(NANCHOR(node)->target); 1076 break; 1077 } 1078 1079 #ifdef USE_PARSE_TREE_NODE_RECYCLE 1080 { 1081 FreeNode* n = (FreeNode* )node; 1082 1083 THREAD_ATOMIC_START; 1084 n->next = FreeNodeList; 1085 FreeNodeList = n; 1086 THREAD_ATOMIC_END; 1087 } 1088 #else 1089 xfree(node); 1090 #endif 1091 } 1092 1093 #ifdef USE_PARSE_TREE_NODE_RECYCLE 1094 extern int 1095 onig_free_node_list(void) 1096 { 1097 FreeNode* n; 1098 1099 /* THREAD_ATOMIC_START; */ 1100 while (IS_NOT_NULL(FreeNodeList)) { 1101 n = FreeNodeList; 1102 FreeNodeList = FreeNodeList->next; 1103 xfree(n); 1104 } 1105 /* THREAD_ATOMIC_END; */ 1106 return 0; 1107 } 1108 #endif 1109 1110 static Node* 1111 node_new(void) 1112 { 1113 Node* node; 1114 1115 #ifdef USE_PARSE_TREE_NODE_RECYCLE 1116 THREAD_ATOMIC_START; 1117 if (IS_NOT_NULL(FreeNodeList)) { 1118 node = (Node* )FreeNodeList; 1119 FreeNodeList = FreeNodeList->next; 1120 THREAD_ATOMIC_END; 1121 return node; 1122 } 1123 THREAD_ATOMIC_END; 1124 #endif 1125 1126 node = (Node* )xmalloc(sizeof(Node)); 1127 /* xmemset(node, 0, sizeof(Node)); */ 1128 return node; 1129 } 1130 1131 1132 static void 1133 initialize_cclass(CClassNode* cc) 1134 { 1135 BITSET_CLEAR(cc->bs); 1136 /* cc->base.flags = 0; */ 1137 cc->flags = 0; 1138 cc->mbuf = NULL; 1139 } 1140 1141 static Node* 1142 node_new_cclass(void) 1143 { 1144 Node* node = node_new(); 1145 CHECK_NULL_RETURN(node); 1146 1147 SET_NTYPE(node, NT_CCLASS); 1148 initialize_cclass(NCCLASS(node)); 1149 return node; 1150 } 1151 1152 static Node* 1153 node_new_cclass_by_codepoint_range(int not, OnigCodePoint sb_out, 1154 const OnigCodePoint ranges[]) 1155 { 1156 int n, i; 1157 CClassNode* cc; 1158 OnigCodePoint j; 1159 1160 Node* node = node_new_cclass(); 1161 CHECK_NULL_RETURN(node); 1162 1163 cc = NCCLASS(node); 1164 if (not != 0) NCCLASS_SET_NOT(cc); 1165 1166 BITSET_CLEAR(cc->bs); 1167 if (sb_out > 0 && IS_NOT_NULL(ranges)) { 1168 n = ONIGENC_CODE_RANGE_NUM(ranges); 1169 for (i = 0; i < n; i++) { 1170 for (j = ONIGENC_CODE_RANGE_FROM(ranges, i); 1171 j <= (OnigCodePoint )ONIGENC_CODE_RANGE_TO(ranges, i); j++) { 1172 if (j >= sb_out) goto sb_end; 1173 1174 BITSET_SET_BIT(cc->bs, j); 1175 } 1176 } 1177 } 1178 1179 sb_end: 1180 if (IS_NULL(ranges)) { 1181 is_null: 1182 cc->mbuf = NULL; 1183 } 1184 else { 1185 BBuf* bbuf; 1186 1187 n = ONIGENC_CODE_RANGE_NUM(ranges); 1188 if (n == 0) goto is_null; 1189 1190 bbuf = (BBuf* )xmalloc(sizeof(BBuf)); 1191 CHECK_NULL_RETURN(bbuf); 1192 bbuf->alloc = n + 1; 1193 bbuf->used = n + 1; 1194 bbuf->p = (UChar* )((void* )ranges); 1195 1196 cc->mbuf = bbuf; 1197 } 1198 1199 return node; 1200 } 1201 1202 static Node* 1203 node_new_ctype(int type, int not) 1204 { 1205 Node* node = node_new(); 1206 CHECK_NULL_RETURN(node); 1207 1208 SET_NTYPE(node, NT_CTYPE); 1209 NCTYPE(node)->ctype = type; 1210 NCTYPE(node)->not = not; 1211 return node; 1212 } 1213 1214 static Node* 1215 node_new_anychar(void) 1216 { 1217 Node* node = node_new(); 1218 CHECK_NULL_RETURN(node); 1219 1220 SET_NTYPE(node, NT_CANY); 1221 return node; 1222 } 1223 1224 static Node* 1225 node_new_list(Node* left, Node* right) 1226 { 1227 Node* node = node_new(); 1228 CHECK_NULL_RETURN(node); 1229 1230 SET_NTYPE(node, NT_LIST); 1231 NCAR(node) = left; 1232 NCDR(node) = right; 1233 return node; 1234 } 1235 1236 extern Node* 1237 onig_node_new_list(Node* left, Node* right) 1238 { 1239 return node_new_list(left, right); 1240 } 1241 1242 extern Node* 1243 onig_node_list_add(Node* list, Node* x) 1244 { 1245 Node *n; 1246 1247 n = onig_node_new_list(x, NULL); 1248 if (IS_NULL(n)) return NULL_NODE; 1249 1250 if (IS_NOT_NULL(list)) { 1251 while (IS_NOT_NULL(NCDR(list))) 1252 list = NCDR(list); 1253 1254 NCDR(list) = n; 1255 } 1256 1257 return n; 1258 } 1259 1260 extern Node* 1261 onig_node_new_alt(Node* left, Node* right) 1262 { 1263 Node* node = node_new(); 1264 CHECK_NULL_RETURN(node); 1265 1266 SET_NTYPE(node, NT_ALT); 1267 NCAR(node) = left; 1268 NCDR(node) = right; 1269 return node; 1270 } 1271 1272 extern Node* 1273 onig_node_new_anchor(int type) 1274 { 1275 Node* node = node_new(); 1276 CHECK_NULL_RETURN(node); 1277 1278 SET_NTYPE(node, NT_ANCHOR); 1279 NANCHOR(node)->type = type; 1280 NANCHOR(node)->target = NULL; 1281 NANCHOR(node)->char_len = -1; 1282 return node; 1283 } 1284 1285 static Node* 1286 node_new_backref(int back_num, int* backrefs, int by_name, 1287 #ifdef USE_BACKREF_WITH_LEVEL 1288 int exist_level, int nest_level, 1289 #endif 1290 ScanEnv* env) 1291 { 1292 int i; 1293 Node* node = node_new(); 1294 1295 CHECK_NULL_RETURN(node); 1296 1297 SET_NTYPE(node, NT_BREF); 1298 NBREF(node)->state = 0; 1299 NBREF(node)->back_num = back_num; 1300 NBREF(node)->back_dynamic = (int* )NULL; 1301 if (by_name != 0) 1302 NBREF(node)->state |= NST_NAME_REF; 1303 1304 #ifdef USE_BACKREF_WITH_LEVEL 1305 if (exist_level != 0) { 1306 NBREF(node)->state |= NST_NEST_LEVEL; 1307 NBREF(node)->nest_level = nest_level; 1308 } 1309 #endif 1310 1311 for (i = 0; i < back_num; i++) { 1312 if (backrefs[i] <= env->num_mem && 1313 IS_NULL(SCANENV_MEM_NODES(env)[backrefs[i]])) { 1314 NBREF(node)->state |= NST_RECURSION; /* /...(\1).../ */ 1315 break; 1316 } 1317 } 1318 1319 if (back_num <= NODE_BACKREFS_SIZE) { 1320 for (i = 0; i < back_num; i++) 1321 NBREF(node)->back_static[i] = backrefs[i]; 1322 } 1323 else { 1324 int* p = (int* )xmalloc(sizeof(int) * back_num); 1325 if (IS_NULL(p)) { 1326 onig_node_free(node); 1327 return NULL; 1328 } 1329 NBREF(node)->back_dynamic = p; 1330 for (i = 0; i < back_num; i++) 1331 p[i] = backrefs[i]; 1332 } 1333 return node; 1334 } 1335 1336 #ifdef USE_SUBEXP_CALL 1337 static Node* 1338 node_new_call(UChar* name, UChar* name_end, int gnum) 1339 { 1340 Node* node = node_new(); 1341 CHECK_NULL_RETURN(node); 1342 1343 SET_NTYPE(node, NT_CALL); 1344 NCALL(node)->state = 0; 1345 NCALL(node)->target = NULL_NODE; 1346 NCALL(node)->name = name; 1347 NCALL(node)->name_end = name_end; 1348 NCALL(node)->group_num = gnum; /* call by number if gnum != 0 */ 1349 return node; 1350 } 1351 #endif 1352 1353 static Node* 1354 node_new_quantifier(int lower, int upper, int by_number) 1355 { 1356 Node* node = node_new(); 1357 CHECK_NULL_RETURN(node); 1358 1359 SET_NTYPE(node, NT_QTFR); 1360 NQTFR(node)->state = 0; 1361 NQTFR(node)->target = NULL; 1362 NQTFR(node)->lower = lower; 1363 NQTFR(node)->upper = upper; 1364 NQTFR(node)->greedy = 1; 1365 NQTFR(node)->target_empty_info = NQ_TARGET_ISNOT_EMPTY; 1366 NQTFR(node)->head_exact = NULL_NODE; 1367 NQTFR(node)->next_head_exact = NULL_NODE; 1368 NQTFR(node)->is_refered = 0; 1369 if (by_number != 0) 1370 NQTFR(node)->state |= NST_BY_NUMBER; 1371 1372 #ifdef USE_COMBINATION_EXPLOSION_CHECK 1373 NQTFR(node)->comb_exp_check_num = 0; 1374 #endif 1375 1376 return node; 1377 } 1378 1379 static Node* 1380 node_new_enclose(int type) 1381 { 1382 Node* node = node_new(); 1383 CHECK_NULL_RETURN(node); 1384 1385 SET_NTYPE(node, NT_ENCLOSE); 1386 NENCLOSE(node)->type = type; 1387 NENCLOSE(node)->state = 0; 1388 NENCLOSE(node)->regnum = 0; 1389 NENCLOSE(node)->option = 0; 1390 NENCLOSE(node)->target = NULL; 1391 NENCLOSE(node)->call_addr = -1; 1392 NENCLOSE(node)->opt_count = 0; 1393 return node; 1394 } 1395 1396 extern Node* 1397 onig_node_new_enclose(int type) 1398 { 1399 return node_new_enclose(type); 1400 } 1401 1402 static Node* 1403 node_new_enclose_memory(OnigOptionType option, int is_named) 1404 { 1405 Node* node = node_new_enclose(ENCLOSE_MEMORY); 1406 CHECK_NULL_RETURN(node); 1407 if (is_named != 0) 1408 SET_ENCLOSE_STATUS(node, NST_NAMED_GROUP); 1409 1410 #ifdef USE_SUBEXP_CALL 1411 NENCLOSE(node)->option = option; 1412 #endif 1413 return node; 1414 } 1415 1416 static Node* 1417 node_new_option(OnigOptionType option) 1418 { 1419 Node* node = node_new_enclose(ENCLOSE_OPTION); 1420 CHECK_NULL_RETURN(node); 1421 NENCLOSE(node)->option = option; 1422 return node; 1423 } 1424 1425 extern int 1426 onig_node_str_cat(Node* node, const UChar* s, const UChar* end) 1427 { 1428 int addlen = (int)(end - s); 1429 1430 if (addlen > 0) { 1431 int len = (int)(NSTR(node)->end - NSTR(node)->s); 1432 1433 if (NSTR(node)->capa > 0 || (len + addlen > NODE_STR_BUF_SIZE - 1)) { 1434 UChar* p; 1435 int capa = len + addlen + NODE_STR_MARGIN; 1436 1437 if (capa <= NSTR(node)->capa) { 1438 onig_strcpy(NSTR(node)->s + len, s, end); 1439 } 1440 else { 1441 if (NSTR(node)->s == NSTR(node)->buf) 1442 p = strcat_capa_from_static(NSTR(node)->s, NSTR(node)->end, 1443 s, end, capa); 1444 else 1445 p = strcat_capa(NSTR(node)->s, NSTR(node)->end, s, end, capa, NSTR(node)->capa); 1446 1447 CHECK_NULL_RETURN_MEMERR(p); 1448 NSTR(node)->s = p; 1449 NSTR(node)->capa = capa; 1450 } 1451 } 1452 else { 1453 onig_strcpy(NSTR(node)->s + len, s, end); 1454 } 1455 NSTR(node)->end = NSTR(node)->s + len + addlen; 1456 } 1457 1458 return 0; 1459 } 1460 1461 extern int 1462 onig_node_str_set(Node* node, const UChar* s, const UChar* end) 1463 { 1464 onig_node_str_clear(node); 1465 return onig_node_str_cat(node, s, end); 1466 } 1467 1468 static int 1469 node_str_cat_char(Node* node, UChar c) 1470 { 1471 UChar s[1]; 1472 1473 s[0] = c; 1474 return onig_node_str_cat(node, s, s + 1); 1475 } 1476 1477 extern void 1478 onig_node_conv_to_str_node(Node* node, int flag) 1479 { 1480 SET_NTYPE(node, NT_STR); 1481 NSTR(node)->flag = flag; 1482 NSTR(node)->capa = 0; 1483 NSTR(node)->s = NSTR(node)->buf; 1484 NSTR(node)->end = NSTR(node)->buf; 1485 } 1486 1487 extern void 1488 onig_node_str_clear(Node* node) 1489 { 1490 if (NSTR(node)->capa != 0 && 1491 IS_NOT_NULL(NSTR(node)->s) && NSTR(node)->s != NSTR(node)->buf) { 1492 xfree(NSTR(node)->s); 1493 } 1494 1495 NSTR(node)->capa = 0; 1496 NSTR(node)->flag = 0; 1497 NSTR(node)->s = NSTR(node)->buf; 1498 NSTR(node)->end = NSTR(node)->buf; 1499 } 1500 1501 static Node* 1502 node_new_str(const UChar* s, const UChar* end) 1503 { 1504 Node* node = node_new(); 1505 CHECK_NULL_RETURN(node); 1506 1507 SET_NTYPE(node, NT_STR); 1508 NSTR(node)->capa = 0; 1509 NSTR(node)->flag = 0; 1510 NSTR(node)->s = NSTR(node)->buf; 1511 NSTR(node)->end = NSTR(node)->buf; 1512 if (onig_node_str_cat(node, s, end)) { 1513 onig_node_free(node); 1514 return NULL; 1515 } 1516 return node; 1517 } 1518 1519 extern Node* 1520 onig_node_new_str(const UChar* s, const UChar* end) 1521 { 1522 return node_new_str(s, end); 1523 } 1524 1525 static Node* 1526 node_new_str_raw(UChar* s, UChar* end) 1527 { 1528 Node* node = node_new_str(s, end); 1529 CHECK_NULL_RETURN(node); 1530 NSTRING_SET_RAW(node); 1531 return node; 1532 } 1533 1534 static Node* 1535 node_new_empty(void) 1536 { 1537 return node_new_str(NULL, NULL); 1538 } 1539 1540 static Node* 1541 node_new_str_raw_char(UChar c) 1542 { 1543 UChar p[1]; 1544 1545 p[0] = c; 1546 return node_new_str_raw(p, p + 1); 1547 } 1548 1549 static Node* 1550 str_node_split_last_char(StrNode* sn, OnigEncoding enc) 1551 { 1552 const UChar *p; 1553 Node* n = NULL_NODE; 1554 1555 if (sn->end > sn->s) { 1556 p = onigenc_get_prev_char_head(enc, sn->s, sn->end); 1557 if (p && p > sn->s) { /* can be splitted. */ 1558 n = node_new_str(p, sn->end); 1559 CHECK_NULL_RETURN(n); 1560 if ((sn->flag & NSTR_RAW) != 0) 1561 NSTRING_SET_RAW(n); 1562 sn->end = (UChar* )p; 1563 } 1564 } 1565 return n; 1566 } 1567 1568 static int 1569 str_node_can_be_split(StrNode* sn, OnigEncoding enc) 1570 { 1571 if (sn->end > sn->s) { 1572 return ((enclen(enc, sn->s) < sn->end - sn->s) ? 1 : 0); 1573 } 1574 return 0; 1575 } 1576 1577 #ifdef USE_PAD_TO_SHORT_BYTE_CHAR 1578 static int 1579 node_str_head_pad(StrNode* sn, int num, UChar val) 1580 { 1581 UChar buf[NODE_STR_BUF_SIZE]; 1582 int i, len; 1583 1584 len = sn->end - sn->s; 1585 onig_strcpy(buf, sn->s, sn->end); 1586 onig_strcpy(&(sn->s[num]), buf, buf + len); 1587 sn->end += num; 1588 1589 for (i = 0; i < num; i++) { 1590 sn->s[i] = val; 1591 } 1592 } 1593 #endif 1594 1595 extern int 1596 onig_scan_unsigned_number(UChar** src, const UChar* end, OnigEncoding enc) 1597 { 1598 unsigned int num, val; 1599 OnigCodePoint c; 1600 UChar* p = *src; 1601 PFETCH_READY; 1602 1603 num = 0; 1604 while (!PEND) { 1605 PFETCH(c); 1606 if (ONIGENC_IS_CODE_DIGIT(enc, c)) { 1607 val = (unsigned int )DIGITVAL(c); 1608 if ((INT_MAX_LIMIT - val) / 10UL < num) 1609 return -1; /* overflow */ 1610 1611 num = num * 10 + val; 1612 } 1613 else { 1614 PUNFETCH; 1615 break; 1616 } 1617 } 1618 *src = p; 1619 return num; 1620 } 1621 1622 static int 1623 scan_unsigned_hexadecimal_number(UChar** src, UChar* end, int maxlen, 1624 OnigEncoding enc) 1625 { 1626 OnigCodePoint c; 1627 unsigned int num, val; 1628 UChar* p = *src; 1629 PFETCH_READY; 1630 1631 num = 0; 1632 while (!PEND && maxlen-- != 0) { 1633 PFETCH(c); 1634 if (ONIGENC_IS_CODE_XDIGIT(enc, c)) { 1635 val = (unsigned int )XDIGITVAL(enc,c); 1636 if ((INT_MAX_LIMIT - val) / 16UL < num) 1637 return -1; /* overflow */ 1638 1639 num = (num << 4) + XDIGITVAL(enc,c); 1640 } 1641 else { 1642 PUNFETCH; 1643 break; 1644 } 1645 } 1646 *src = p; 1647 return num; 1648 } 1649 1650 static int 1651 scan_unsigned_octal_number(UChar** src, UChar* end, int maxlen, 1652 OnigEncoding enc) 1653 { 1654 OnigCodePoint c; 1655 unsigned int num, val; 1656 UChar* p = *src; 1657 PFETCH_READY; 1658 1659 num = 0; 1660 while (!PEND && maxlen-- != 0) { 1661 PFETCH(c); 1662 if (ONIGENC_IS_CODE_DIGIT(enc, c) && c < '8') { 1663 val = ODIGITVAL(c); 1664 if ((INT_MAX_LIMIT - val) / 8UL < num) 1665 return -1; /* overflow */ 1666 1667 num = (num << 3) + val; 1668 } 1669 else { 1670 PUNFETCH; 1671 break; 1672 } 1673 } 1674 *src = p; 1675 return num; 1676 } 1677 1678 1679 #define BBUF_WRITE_CODE_POINT(bbuf,pos,code) \ 1680 BBUF_WRITE(bbuf, pos, &(code), SIZE_CODE_POINT) 1681 1682 /* data format: 1683 [n][from-1][to-1][from-2][to-2] ... [from-n][to-n] 1684 (all data size is OnigCodePoint) 1685 */ 1686 static int 1687 new_code_range(BBuf** pbuf) 1688 { 1689 #define INIT_MULTI_BYTE_RANGE_SIZE (SIZE_CODE_POINT * 5) 1690 int r; 1691 OnigCodePoint n; 1692 BBuf* bbuf; 1693 1694 bbuf = *pbuf = (BBuf* )xmalloc(sizeof(BBuf)); 1695 CHECK_NULL_RETURN_MEMERR(*pbuf); 1696 r = BBUF_INIT(*pbuf, INIT_MULTI_BYTE_RANGE_SIZE); 1697 if (r) return r; 1698 1699 n = 0; 1700 BBUF_WRITE_CODE_POINT(bbuf, 0, n); 1701 return 0; 1702 } 1703 1704 static int 1705 add_code_range_to_buf(BBuf** pbuf, OnigCodePoint from, OnigCodePoint to) 1706 { 1707 int r, inc_n, pos; 1708 int low, high, bound, x; 1709 OnigCodePoint n, *data; 1710 BBuf* bbuf; 1711 1712 if (from > to) { 1713 n = from; from = to; to = n; 1714 } 1715 1716 if (IS_NULL(*pbuf)) { 1717 r = new_code_range(pbuf); 1718 if (r) return r; 1719 bbuf = *pbuf; 1720 n = 0; 1721 } 1722 else { 1723 bbuf = *pbuf; 1724 GET_CODE_POINT(n, bbuf->p); 1725 } 1726 data = (OnigCodePoint* )(bbuf->p); 1727 data++; 1728 1729 for (low = 0, bound = n; low < bound; ) { 1730 x = (low + bound) >> 1; 1731 if (from > data[x*2 + 1]) 1732 low = x + 1; 1733 else 1734 bound = x; 1735 } 1736 1737 for (high = low, bound = n; high < bound; ) { 1738 x = (high + bound) >> 1; 1739 if (to >= data[x*2] - 1) 1740 high = x + 1; 1741 else 1742 bound = x; 1743 } 1744 1745 inc_n = low + 1 - high; 1746 if (n + inc_n > ONIG_MAX_MULTI_BYTE_RANGES_NUM) 1747 return ONIGERR_TOO_MANY_MULTI_BYTE_RANGES; 1748 1749 if (inc_n != 1) { 1750 if (from > data[low*2]) 1751 from = data[low*2]; 1752 if (to < data[(high - 1)*2 + 1]) 1753 to = data[(high - 1)*2 + 1]; 1754 } 1755 1756 if (inc_n != 0 && (OnigCodePoint )high < n) { 1757 int from_pos = SIZE_CODE_POINT * (1 + high * 2); 1758 int to_pos = SIZE_CODE_POINT * (1 + (low + 1) * 2); 1759 int size = (n - high) * 2 * SIZE_CODE_POINT; 1760 1761 if (inc_n > 0) { 1762 BBUF_MOVE_RIGHT(bbuf, from_pos, to_pos, size); 1763 } 1764 else { 1765 BBUF_MOVE_LEFT_REDUCE(bbuf, from_pos, to_pos); 1766 } 1767 } 1768 1769 pos = SIZE_CODE_POINT * (1 + low * 2); 1770 BBUF_ENSURE_SIZE(bbuf, pos + SIZE_CODE_POINT * 2); 1771 BBUF_WRITE_CODE_POINT(bbuf, pos, from); 1772 BBUF_WRITE_CODE_POINT(bbuf, pos + SIZE_CODE_POINT, to); 1773 n += inc_n; 1774 BBUF_WRITE_CODE_POINT(bbuf, 0, n); 1775 1776 return 0; 1777 } 1778 1779 static int 1780 add_code_range(BBuf** pbuf, ScanEnv* env, OnigCodePoint from, OnigCodePoint to) 1781 { 1782 if (from > to) { 1783 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_EMPTY_RANGE_IN_CC)) 1784 return 0; 1785 else 1786 return ONIGERR_EMPTY_RANGE_IN_CHAR_CLASS; 1787 } 1788 1789 return add_code_range_to_buf(pbuf, from, to); 1790 } 1791 1792 static int 1793 not_code_range_buf(OnigEncoding enc, BBuf* bbuf, BBuf** pbuf) 1794 { 1795 int r, i, n; 1796 OnigCodePoint pre, from, *data, to = 0; 1797 1798 *pbuf = (BBuf* )NULL; 1799 if (IS_NULL(bbuf)) { 1800 set_all: 1801 return SET_ALL_MULTI_BYTE_RANGE(enc, pbuf); 1802 } 1803 1804 data = (OnigCodePoint* )(bbuf->p); 1805 GET_CODE_POINT(n, data); 1806 data++; 1807 if (n <= 0) goto set_all; 1808 1809 r = 0; 1810 pre = MBCODE_START_POS(enc); 1811 for (i = 0; i < n; i++) { 1812 from = data[i*2]; 1813 to = data[i*2+1]; 1814 if (pre <= from - 1) { 1815 r = add_code_range_to_buf(pbuf, pre, from - 1); 1816 if (r != 0) return r; 1817 } 1818 if (to == ~((OnigCodePoint )0)) break; 1819 pre = to + 1; 1820 } 1821 if (to < ~((OnigCodePoint )0)) { 1822 r = add_code_range_to_buf(pbuf, to + 1, ~((OnigCodePoint )0)); 1823 } 1824 return r; 1825 } 1826 1827 #define SWAP_BBUF_NOT(bbuf1, not1, bbuf2, not2) do {\ 1828 BBuf *tbuf; \ 1829 int tnot; \ 1830 tnot = not1; not1 = not2; not2 = tnot; \ 1831 tbuf = bbuf1; bbuf1 = bbuf2; bbuf2 = tbuf; \ 1832 } while (0) 1833 1834 static int 1835 or_code_range_buf(OnigEncoding enc, BBuf* bbuf1, int not1, 1836 BBuf* bbuf2, int not2, BBuf** pbuf) 1837 { 1838 int r; 1839 OnigCodePoint i, n1, *data1; 1840 OnigCodePoint from, to; 1841 1842 *pbuf = (BBuf* )NULL; 1843 if (IS_NULL(bbuf1) && IS_NULL(bbuf2)) { 1844 if (not1 != 0 || not2 != 0) 1845 return SET_ALL_MULTI_BYTE_RANGE(enc, pbuf); 1846 return 0; 1847 } 1848 1849 r = 0; 1850 if (IS_NULL(bbuf2)) 1851 SWAP_BBUF_NOT(bbuf1, not1, bbuf2, not2); 1852 1853 if (IS_NULL(bbuf1)) { 1854 if (not1 != 0) { 1855 return SET_ALL_MULTI_BYTE_RANGE(enc, pbuf); 1856 } 1857 else { 1858 if (not2 == 0) { 1859 return bbuf_clone(pbuf, bbuf2); 1860 } 1861 else { 1862 return not_code_range_buf(enc, bbuf2, pbuf); 1863 } 1864 } 1865 } 1866 1867 if (not1 != 0) 1868 SWAP_BBUF_NOT(bbuf1, not1, bbuf2, not2); 1869 1870 data1 = (OnigCodePoint* )(bbuf1->p); 1871 GET_CODE_POINT(n1, data1); 1872 data1++; 1873 1874 if (not2 == 0 && not1 == 0) { /* 1 OR 2 */ 1875 r = bbuf_clone(pbuf, bbuf2); 1876 } 1877 else if (not1 == 0) { /* 1 OR (not 2) */ 1878 r = not_code_range_buf(enc, bbuf2, pbuf); 1879 } 1880 if (r != 0) return r; 1881 1882 for (i = 0; i < n1; i++) { 1883 from = data1[i*2]; 1884 to = data1[i*2+1]; 1885 r = add_code_range_to_buf(pbuf, from, to); 1886 if (r != 0) return r; 1887 } 1888 return 0; 1889 } 1890 1891 static int 1892 and_code_range1(BBuf** pbuf, OnigCodePoint from1, OnigCodePoint to1, 1893 OnigCodePoint* data, int n) 1894 { 1895 int i, r; 1896 OnigCodePoint from2, to2; 1897 1898 for (i = 0; i < n; i++) { 1899 from2 = data[i*2]; 1900 to2 = data[i*2+1]; 1901 if (from2 < from1) { 1902 if (to2 < from1) continue; 1903 else { 1904 from1 = to2 + 1; 1905 } 1906 } 1907 else if (from2 <= to1) { 1908 if (to2 < to1) { 1909 if (from1 <= from2 - 1) { 1910 r = add_code_range_to_buf(pbuf, from1, from2-1); 1911 if (r != 0) return r; 1912 } 1913 from1 = to2 + 1; 1914 } 1915 else { 1916 to1 = from2 - 1; 1917 } 1918 } 1919 else { 1920 from1 = from2; 1921 } 1922 if (from1 > to1) break; 1923 } 1924 if (from1 <= to1) { 1925 r = add_code_range_to_buf(pbuf, from1, to1); 1926 if (r != 0) return r; 1927 } 1928 return 0; 1929 } 1930 1931 static int 1932 and_code_range_buf(BBuf* bbuf1, int not1, BBuf* bbuf2, int not2, BBuf** pbuf) 1933 { 1934 int r; 1935 OnigCodePoint i, j, n1, n2, *data1, *data2; 1936 OnigCodePoint from, to, from1, to1, from2, to2; 1937 1938 *pbuf = (BBuf* )NULL; 1939 if (IS_NULL(bbuf1)) { 1940 if (not1 != 0 && IS_NOT_NULL(bbuf2)) /* not1 != 0 -> not2 == 0 */ 1941 return bbuf_clone(pbuf, bbuf2); 1942 return 0; 1943 } 1944 else if (IS_NULL(bbuf2)) { 1945 if (not2 != 0) 1946 return bbuf_clone(pbuf, bbuf1); 1947 return 0; 1948 } 1949 1950 if (not1 != 0) 1951 SWAP_BBUF_NOT(bbuf1, not1, bbuf2, not2); 1952 1953 data1 = (OnigCodePoint* )(bbuf1->p); 1954 data2 = (OnigCodePoint* )(bbuf2->p); 1955 GET_CODE_POINT(n1, data1); 1956 GET_CODE_POINT(n2, data2); 1957 data1++; 1958 data2++; 1959 1960 if (not2 == 0 && not1 == 0) { /* 1 AND 2 */ 1961 for (i = 0; i < n1; i++) { 1962 from1 = data1[i*2]; 1963 to1 = data1[i*2+1]; 1964 for (j = 0; j < n2; j++) { 1965 from2 = data2[j*2]; 1966 to2 = data2[j*2+1]; 1967 if (from2 > to1) break; 1968 if (to2 < from1) continue; 1969 from = MAX(from1, from2); 1970 to = MIN(to1, to2); 1971 r = add_code_range_to_buf(pbuf, from, to); 1972 if (r != 0) return r; 1973 } 1974 } 1975 } 1976 else if (not1 == 0) { /* 1 AND (not 2) */ 1977 for (i = 0; i < n1; i++) { 1978 from1 = data1[i*2]; 1979 to1 = data1[i*2+1]; 1980 r = and_code_range1(pbuf, from1, to1, data2, n2); 1981 if (r != 0) return r; 1982 } 1983 } 1984 1985 return 0; 1986 } 1987 1988 static int 1989 and_cclass(CClassNode* dest, CClassNode* cc, OnigEncoding enc) 1990 { 1991 int r, not1, not2; 1992 BBuf *buf1, *buf2, *pbuf; 1993 BitSetRef bsr1, bsr2; 1994 BitSet bs1, bs2; 1995 1996 not1 = IS_NCCLASS_NOT(dest); 1997 bsr1 = dest->bs; 1998 buf1 = dest->mbuf; 1999 not2 = IS_NCCLASS_NOT(cc); 2000 bsr2 = cc->bs; 2001 buf2 = cc->mbuf; 2002 2003 if (not1 != 0) { 2004 bitset_invert_to(bsr1, bs1); 2005 bsr1 = bs1; 2006 } 2007 if (not2 != 0) { 2008 bitset_invert_to(bsr2, bs2); 2009 bsr2 = bs2; 2010 } 2011 bitset_and(bsr1, bsr2); 2012 if (bsr1 != dest->bs) { 2013 bitset_copy(dest->bs, bsr1); 2014 bsr1 = dest->bs; 2015 } 2016 if (not1 != 0) { 2017 bitset_invert(dest->bs); 2018 } 2019 2020 if (! ONIGENC_IS_SINGLEBYTE(enc)) { 2021 if (not1 != 0 && not2 != 0) { 2022 r = or_code_range_buf(enc, buf1, 0, buf2, 0, &pbuf); 2023 } 2024 else { 2025 r = and_code_range_buf(buf1, not1, buf2, not2, &pbuf); 2026 if (r == 0 && not1 != 0) { 2027 BBuf *tbuf; 2028 r = not_code_range_buf(enc, pbuf, &tbuf); 2029 if (r != 0) { 2030 bbuf_free(pbuf); 2031 return r; 2032 } 2033 bbuf_free(pbuf); 2034 pbuf = tbuf; 2035 } 2036 } 2037 if (r != 0) return r; 2038 2039 dest->mbuf = pbuf; 2040 bbuf_free(buf1); 2041 return r; 2042 } 2043 return 0; 2044 } 2045 2046 static int 2047 or_cclass(CClassNode* dest, CClassNode* cc, OnigEncoding enc) 2048 { 2049 int r, not1, not2; 2050 BBuf *buf1, *buf2, *pbuf; 2051 BitSetRef bsr1, bsr2; 2052 BitSet bs1, bs2; 2053 2054 not1 = IS_NCCLASS_NOT(dest); 2055 bsr1 = dest->bs; 2056 buf1 = dest->mbuf; 2057 not2 = IS_NCCLASS_NOT(cc); 2058 bsr2 = cc->bs; 2059 buf2 = cc->mbuf; 2060 2061 if (not1 != 0) { 2062 bitset_invert_to(bsr1, bs1); 2063 bsr1 = bs1; 2064 } 2065 if (not2 != 0) { 2066 bitset_invert_to(bsr2, bs2); 2067 bsr2 = bs2; 2068 } 2069 bitset_or(bsr1, bsr2); 2070 if (bsr1 != dest->bs) { 2071 bitset_copy(dest->bs, bsr1); 2072 bsr1 = dest->bs; 2073 } 2074 if (not1 != 0) { 2075 bitset_invert(dest->bs); 2076 } 2077 2078 if (! ONIGENC_IS_SINGLEBYTE(enc)) { 2079 if (not1 != 0 && not2 != 0) { 2080 r = and_code_range_buf(buf1, 0, buf2, 0, &pbuf); 2081 } 2082 else { 2083 r = or_code_range_buf(enc, buf1, not1, buf2, not2, &pbuf); 2084 if (r == 0 && not1 != 0) { 2085 BBuf *tbuf; 2086 r = not_code_range_buf(enc, pbuf, &tbuf); 2087 if (r != 0) { 2088 bbuf_free(pbuf); 2089 return r; 2090 } 2091 bbuf_free(pbuf); 2092 pbuf = tbuf; 2093 } 2094 } 2095 if (r != 0) return r; 2096 2097 dest->mbuf = pbuf; 2098 bbuf_free(buf1); 2099 return r; 2100 } 2101 else 2102 return 0; 2103 } 2104 2105 static int 2106 conv_backslash_value(int c, ScanEnv* env) 2107 { 2108 if (IS_SYNTAX_OP(env->syntax, ONIG_SYN_OP_ESC_CONTROL_CHARS)) { 2109 switch (c) { 2110 case 'n': return '\n'; 2111 case 't': return '\t'; 2112 case 'r': return '\r'; 2113 case 'f': return '\f'; 2114 case 'a': return '\007'; 2115 case 'b': return '\010'; 2116 case 'e': return '\033'; 2117 case 'v': 2118 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_ESC_V_VTAB)) 2119 return '\v'; 2120 break; 2121 2122 default: 2123 break; 2124 } 2125 } 2126 return c; 2127 } 2128 2129 static int 2130 is_invalid_quantifier_target(Node* node) 2131 { 2132 switch (NTYPE(node)) { 2133 case NT_ANCHOR: 2134 return 1; 2135 break; 2136 2137 case NT_ENCLOSE: 2138 /* allow enclosed elements */ 2139 /* return is_invalid_quantifier_target(NENCLOSE(node)->target); */ 2140 break; 2141 2142 case NT_LIST: 2143 do { 2144 if (! is_invalid_quantifier_target(NCAR(node))) return 0; 2145 } while (IS_NOT_NULL(node = NCDR(node))); 2146 return 0; 2147 break; 2148 2149 case NT_ALT: 2150 do { 2151 if (is_invalid_quantifier_target(NCAR(node))) return 1; 2152 } while (IS_NOT_NULL(node = NCDR(node))); 2153 break; 2154 2155 default: 2156 break; 2157 } 2158 return 0; 2159 } 2160 2161 /* ?:0, *:1, +:2, ??:3, *?:4, +?:5 */ 2162 static int 2163 popular_quantifier_num(QtfrNode* q) 2164 { 2165 if (q->greedy) { 2166 if (q->lower == 0) { 2167 if (q->upper == 1) return 0; 2168 else if (IS_REPEAT_INFINITE(q->upper)) return 1; 2169 } 2170 else if (q->lower == 1) { 2171 if (IS_REPEAT_INFINITE(q->upper)) return 2; 2172 } 2173 } 2174 else { 2175 if (q->lower == 0) { 2176 if (q->upper == 1) return 3; 2177 else if (IS_REPEAT_INFINITE(q->upper)) return 4; 2178 } 2179 else if (q->lower == 1) { 2180 if (IS_REPEAT_INFINITE(q->upper)) return 5; 2181 } 2182 } 2183 return -1; 2184 } 2185 2186 2187 enum ReduceType { 2188 RQ_ASIS = 0, /* as is */ 2189 RQ_DEL = 1, /* delete parent */ 2190 RQ_A, /* to '*' */ 2191 RQ_AQ, /* to '*?' */ 2192 RQ_QQ, /* to '??' */ 2193 RQ_P_QQ, /* to '+)??' */ 2194 RQ_PQ_Q /* to '+?)?' */ 2195 }; 2196 2197 static enum ReduceType ReduceTypeTable[6][6] = { 2198 {RQ_DEL, RQ_A, RQ_A, RQ_QQ, RQ_AQ, RQ_ASIS}, /* '?' */ 2199 {RQ_DEL, RQ_DEL, RQ_DEL, RQ_P_QQ, RQ_P_QQ, RQ_DEL}, /* '*' */ 2200 {RQ_A, RQ_A, RQ_DEL, RQ_ASIS, RQ_P_QQ, RQ_DEL}, /* '+' */ 2201 {RQ_DEL, RQ_AQ, RQ_AQ, RQ_DEL, RQ_AQ, RQ_AQ}, /* '??' */ 2202 {RQ_DEL, RQ_DEL, RQ_DEL, RQ_DEL, RQ_DEL, RQ_DEL}, /* '*?' */ 2203 {RQ_ASIS, RQ_PQ_Q, RQ_DEL, RQ_AQ, RQ_AQ, RQ_DEL} /* '+?' */ 2204 }; 2205 2206 extern void 2207 onig_reduce_nested_quantifier(Node* pnode, Node* cnode) 2208 { 2209 int pnum, cnum; 2210 QtfrNode *p, *c; 2211 2212 p = NQTFR(pnode); 2213 c = NQTFR(cnode); 2214 pnum = popular_quantifier_num(p); 2215 cnum = popular_quantifier_num(c); 2216 if (pnum < 0 || cnum < 0) return ; 2217 2218 switch(ReduceTypeTable[cnum][pnum]) { 2219 case RQ_DEL: 2220 CopyMem (pnode, cnode, sizeof (Node)); 2221 break; 2222 case RQ_A: 2223 p->target = c->target; 2224 p->lower = 0; p->upper = REPEAT_INFINITE; p->greedy = 1; 2225 break; 2226 case RQ_AQ: 2227 p->target = c->target; 2228 p->lower = 0; p->upper = REPEAT_INFINITE; p->greedy = 0; 2229 break; 2230 case RQ_QQ: 2231 p->target = c->target; 2232 p->lower = 0; p->upper = 1; p->greedy = 0; 2233 break; 2234 case RQ_P_QQ: 2235 p->target = cnode; 2236 p->lower = 0; p->upper = 1; p->greedy = 0; 2237 c->lower = 1; c->upper = REPEAT_INFINITE; c->greedy = 1; 2238 return ; 2239 break; 2240 case RQ_PQ_Q: 2241 p->target = cnode; 2242 p->lower = 0; p->upper = 1; p->greedy = 1; 2243 c->lower = 1; c->upper = REPEAT_INFINITE; c->greedy = 0; 2244 return ; 2245 break; 2246 case RQ_ASIS: 2247 p->target = cnode; 2248 return ; 2249 break; 2250 } 2251 2252 c->target = NULL_NODE; 2253 onig_node_free(cnode); 2254 } 2255 2256 2257 enum TokenSyms { 2258 TK_EOT = 0, /* end of token */ 2259 TK_RAW_BYTE = 1, 2260 TK_CHAR, 2261 TK_STRING, 2262 TK_CODE_POINT, 2263 TK_ANYCHAR, 2264 TK_CHAR_TYPE, 2265 TK_BACKREF, 2266 TK_CALL, 2267 TK_ANCHOR, 2268 TK_OP_REPEAT, 2269 TK_INTERVAL, 2270 TK_ANYCHAR_ANYTIME, /* SQL '%' == .* */ 2271 TK_ALT, 2272 TK_SUBEXP_OPEN, 2273 TK_SUBEXP_CLOSE, 2274 TK_CC_OPEN, 2275 TK_QUOTE_OPEN, 2276 TK_CHAR_PROPERTY, /* \p{...}, \P{...} */ 2277 /* in cc */ 2278 TK_CC_CLOSE, 2279 TK_CC_RANGE, 2280 TK_POSIX_BRACKET_OPEN, 2281 TK_CC_AND, /* && */ 2282 TK_CC_CC_OPEN /* [ */ 2283 }; 2284 2285 typedef struct { 2286 enum TokenSyms type; 2287 int escaped; 2288 int base; /* is number: 8, 16 (used in [....]) */ 2289 UChar* backp; 2290 union { 2291 UChar* s; 2292 int c; 2293 OnigCodePoint code; 2294 int anchor; 2295 int subtype; 2296 struct { 2297 int lower; 2298 int upper; 2299 int greedy; 2300 int possessive; 2301 } repeat; 2302 struct { 2303 int num; 2304 int ref1; 2305 int* refs; 2306 int by_name; 2307 #ifdef USE_BACKREF_WITH_LEVEL 2308 int exist_level; 2309 int level; /* \k<name+n> */ 2310 #endif 2311 } backref; 2312 struct { 2313 UChar* name; 2314 UChar* name_end; 2315 int gnum; 2316 } call; 2317 struct { 2318 int ctype; 2319 int not; 2320 } prop; 2321 } u; 2322 } OnigToken; 2323 2324 2325 static int 2326 fetch_range_quantifier(UChar** src, UChar* end, OnigToken* tok, ScanEnv* env) 2327 { 2328 int low, up, syn_allow, non_low = 0; 2329 int r = 0; 2330 OnigCodePoint c; 2331 OnigEncoding enc = env->enc; 2332 UChar* p = *src; 2333 PFETCH_READY; 2334 2335 syn_allow = IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_INVALID_INTERVAL); 2336 2337 if (PEND) { 2338 if (syn_allow) 2339 return 1; /* "....{" : OK! */ 2340 else 2341 return ONIGERR_END_PATTERN_AT_LEFT_BRACE; /* "....{" syntax error */ 2342 } 2343 2344 if (! syn_allow) { 2345 c = PPEEK; 2346 if (c == ')' || c == '(' || c == '|') { 2347 return ONIGERR_END_PATTERN_AT_LEFT_BRACE; 2348 } 2349 } 2350 2351 low = onig_scan_unsigned_number(&p, end, env->enc); 2352 if (low < 0) return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE; 2353 if (low > ONIG_MAX_REPEAT_NUM) 2354 return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE; 2355 2356 if (p == *src) { /* can't read low */ 2357 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_INTERVAL_LOW_ABBREV)) { 2358 /* allow {,n} as {0,n} */ 2359 low = 0; 2360 non_low = 1; 2361 } 2362 else 2363 goto invalid; 2364 } 2365 2366 if (PEND) goto invalid; 2367 PFETCH(c); 2368 if (c == ',') { 2369 UChar* prev = p; 2370 up = onig_scan_unsigned_number(&p, end, env->enc); 2371 if (up < 0) return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE; 2372 if (up > ONIG_MAX_REPEAT_NUM) 2373 return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE; 2374 2375 if (p == prev) { 2376 if (non_low != 0) 2377 goto invalid; 2378 up = REPEAT_INFINITE; /* {n,} : {n,infinite} */ 2379 } 2380 } 2381 else { 2382 if (non_low != 0) 2383 goto invalid; 2384 2385 PUNFETCH; 2386 up = low; /* {n} : exact n times */ 2387 r = 2; /* fixed */ 2388 } 2389 2390 if (PEND) goto invalid; 2391 PFETCH(c); 2392 if (IS_SYNTAX_OP(env->syntax, ONIG_SYN_OP_ESC_BRACE_INTERVAL)) { 2393 if (c != MC_ESC(env->syntax)) goto invalid; 2394 PFETCH(c); 2395 } 2396 if (c != '}') goto invalid; 2397 2398 if (!IS_REPEAT_INFINITE(up) && low > up) { 2399 return ONIGERR_UPPER_SMALLER_THAN_LOWER_IN_REPEAT_RANGE; 2400 } 2401 2402 tok->type = TK_INTERVAL; 2403 tok->u.repeat.lower = low; 2404 tok->u.repeat.upper = up; 2405 *src = p; 2406 return r; /* 0: normal {n,m}, 2: fixed {n} */ 2407 2408 invalid: 2409 if (syn_allow) 2410 return 1; /* OK */ 2411 else 2412 return ONIGERR_INVALID_REPEAT_RANGE_PATTERN; 2413 } 2414 2415 /* \M-, \C-, \c, or \... */ 2416 static int 2417 fetch_escaped_value(UChar** src, UChar* end, ScanEnv* env) 2418 { 2419 int v; 2420 OnigCodePoint c; 2421 OnigEncoding enc = env->enc; 2422 UChar* p = *src; 2423 2424 if (PEND) return ONIGERR_END_PATTERN_AT_ESCAPE; 2425 2426 PFETCH_S(c); 2427 switch (c) { 2428 case 'M': 2429 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_ESC_CAPITAL_M_BAR_META)) { 2430 if (PEND) return ONIGERR_END_PATTERN_AT_META; 2431 PFETCH_S(c); 2432 if (c != '-') return ONIGERR_META_CODE_SYNTAX; 2433 if (PEND) return ONIGERR_END_PATTERN_AT_META; 2434 PFETCH_S(c); 2435 if (c == MC_ESC(env->syntax)) { 2436 v = fetch_escaped_value(&p, end, env); 2437 if (v < 0) return v; 2438 c = (OnigCodePoint )v; 2439 } 2440 c = ((c & 0xff) | 0x80); 2441 } 2442 else 2443 goto backslash; 2444 break; 2445 2446 case 'C': 2447 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_ESC_CAPITAL_C_BAR_CONTROL)) { 2448 if (PEND) return ONIGERR_END_PATTERN_AT_CONTROL; 2449 PFETCH_S(c); 2450 if (c != '-') return ONIGERR_CONTROL_CODE_SYNTAX; 2451 goto control; 2452 } 2453 else 2454 goto backslash; 2455 2456 case 'c': 2457 if (IS_SYNTAX_OP(env->syntax, ONIG_SYN_OP_ESC_C_CONTROL)) { 2458 control: 2459 if (PEND) return ONIGERR_END_PATTERN_AT_CONTROL; 2460 PFETCH_S(c); 2461 if (c == '?') { 2462 c = 0177; 2463 } 2464 else { 2465 if (c == MC_ESC(env->syntax)) { 2466 v = fetch_escaped_value(&p, end, env); 2467 if (v < 0) return v; 2468 c = (OnigCodePoint )v; 2469 } 2470 c &= 0x9f; 2471 } 2472 break; 2473 } 2474 /* fall through */ 2475 2476 default: 2477 { 2478 backslash: 2479 c = conv_backslash_value(c, env); 2480 } 2481 break; 2482 } 2483 2484 *src = p; 2485 return c; 2486 } 2487 2488 static int fetch_token(OnigToken* tok, UChar** src, UChar* end, ScanEnv* env); 2489 2490 static OnigCodePoint 2491 get_name_end_code_point(OnigCodePoint start) 2492 { 2493 switch (start) { 2494 case '<': return (OnigCodePoint )'>'; break; 2495 case '\'': return (OnigCodePoint )'\''; break; 2496 default: 2497 break; 2498 } 2499 2500 return (OnigCodePoint )0; 2501 } 2502 2503 #ifdef USE_NAMED_GROUP 2504 #ifdef USE_BACKREF_WITH_LEVEL 2505 /* 2506 \k<name+n>, \k<name-n> 2507 \k<num+n>, \k<num-n> 2508 \k<-num+n>, \k<-num-n> 2509 */ 2510 static int 2511 fetch_name_with_level(OnigCodePoint start_code, UChar** src, UChar* end, 2512 UChar** rname_end, ScanEnv* env, 2513 int* rback_num, int* rlevel) 2514 { 2515 int r, sign, is_num, exist_level; 2516 OnigCodePoint end_code; 2517 OnigCodePoint c = 0; 2518 OnigEncoding enc = env->enc; 2519 UChar *name_end; 2520 UChar *pnum_head; 2521 UChar *p = *src; 2522 PFETCH_READY; 2523 2524 *rback_num = 0; 2525 is_num = exist_level = 0; 2526 sign = 1; 2527 pnum_head = *src; 2528 2529 end_code = get_name_end_code_point(start_code); 2530 2531 name_end = end; 2532 r = 0; 2533 if (PEND) { 2534 return ONIGERR_EMPTY_GROUP_NAME; 2535 } 2536 else { 2537 PFETCH(c); 2538 if (c == end_code) 2539 return ONIGERR_EMPTY_GROUP_NAME; 2540 2541 if (ONIGENC_IS_CODE_DIGIT(enc, c)) { 2542 is_num = 1; 2543 } 2544 else if (c == '-') { 2545 is_num = 2; 2546 sign = -1; 2547 pnum_head = p; 2548 } 2549 else if (!ONIGENC_IS_CODE_WORD(enc, c)) { 2550 r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME; 2551 } 2552 } 2553 2554 while (!PEND) { 2555 name_end = p; 2556 PFETCH(c); 2557 if (c == end_code || c == ')' || c == '+' || c == '-') { 2558 if (is_num == 2) r = ONIGERR_INVALID_GROUP_NAME; 2559 break; 2560 } 2561 2562 if (is_num != 0) { 2563 if (ONIGENC_IS_CODE_DIGIT(enc, c)) { 2564 is_num = 1; 2565 } 2566 else { 2567 r = ONIGERR_INVALID_GROUP_NAME; 2568 is_num = 0; 2569 } 2570 } 2571 else if (!ONIGENC_IS_CODE_WORD(enc, c)) { 2572 r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME; 2573 } 2574 } 2575 2576 if (r == 0 && c != end_code) { 2577 if (c == '+' || c == '-') { 2578 int level; 2579 int flag = (c == '-' ? -1 : 1); 2580 2581 PFETCH(c); 2582 if (! ONIGENC_IS_CODE_DIGIT(enc, c)) goto err; 2583 PUNFETCH; 2584 level = onig_scan_unsigned_number(&p, end, enc); 2585 if (level < 0) return ONIGERR_TOO_BIG_NUMBER; 2586 *rlevel = (level * flag); 2587 exist_level = 1; 2588 2589 PFETCH(c); 2590 if (c == end_code) 2591 goto end; 2592 } 2593 2594 err: 2595 r = ONIGERR_INVALID_GROUP_NAME; 2596 name_end = end; 2597 } 2598 2599 end: 2600 if (r == 0) { 2601 if (is_num != 0) { 2602 *rback_num = onig_scan_unsigned_number(&pnum_head, name_end, enc); 2603 if (*rback_num < 0) return ONIGERR_TOO_BIG_NUMBER; 2604 else if (*rback_num == 0) goto err; 2605 2606 *rback_num *= sign; 2607 } 2608 2609 *rname_end = name_end; 2610 *src = p; 2611 return (exist_level ? 1 : 0); 2612 } 2613 else { 2614 onig_scan_env_set_error_string(env, r, *src, name_end); 2615 return r; 2616 } 2617 } 2618 #endif /* USE_BACKREF_WITH_LEVEL */ 2619 2620 /* 2621 def: 0 -> define name (don't allow number name) 2622 1 -> reference name (allow number name) 2623 */ 2624 static int 2625 fetch_name(OnigCodePoint start_code, UChar** src, UChar* end, 2626 UChar** rname_end, ScanEnv* env, int* rback_num, int ref) 2627 { 2628 int r, is_num, sign; 2629 OnigCodePoint end_code; 2630 OnigCodePoint c = 0; 2631 OnigEncoding enc = env->enc; 2632 UChar *name_end; 2633 UChar *pnum_head; 2634 UChar *p = *src; 2635 2636 *rback_num = 0; 2637 2638 end_code = get_name_end_code_point(start_code); 2639 2640 name_end = end; 2641 pnum_head = *src; 2642 r = 0; 2643 is_num = 0; 2644 sign = 1; 2645 if (PEND) { 2646 return ONIGERR_EMPTY_GROUP_NAME; 2647 } 2648 else { 2649 PFETCH_S(c); 2650 if (c == end_code) 2651 return ONIGERR_EMPTY_GROUP_NAME; 2652 2653 if (ONIGENC_IS_CODE_DIGIT(enc, c)) { 2654 if (ref == 1) 2655 is_num = 1; 2656 else { 2657 r = ONIGERR_INVALID_GROUP_NAME; 2658 is_num = 0; 2659 } 2660 } 2661 else if (c == '-') { 2662 if (ref == 1) { 2663 is_num = 2; 2664 sign = -1; 2665 pnum_head = p; 2666 } 2667 else { 2668 r = ONIGERR_INVALID_GROUP_NAME; 2669 is_num = 0; 2670 } 2671 } 2672 else if (!ONIGENC_IS_CODE_WORD(enc, c)) { 2673 r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME; 2674 } 2675 } 2676 2677 if (r == 0) { 2678 while (!PEND) { 2679 name_end = p; 2680 PFETCH_S(c); 2681 if (c == end_code || c == ')') { 2682 if (is_num == 2) r = ONIGERR_INVALID_GROUP_NAME; 2683 break; 2684 } 2685 2686 if (is_num != 0) { 2687 if (ONIGENC_IS_CODE_DIGIT(enc, c)) { 2688 is_num = 1; 2689 } 2690 else { 2691 if (!ONIGENC_IS_CODE_WORD(enc, c)) 2692 r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME; 2693 else 2694 r = ONIGERR_INVALID_GROUP_NAME; 2695 is_num = 0; 2696 } 2697 } 2698 else { 2699 if (!ONIGENC_IS_CODE_WORD(enc, c)) { 2700 r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME; 2701 } 2702 } 2703 } 2704 2705 if (c != end_code) { 2706 r = ONIGERR_INVALID_GROUP_NAME; 2707 name_end = end; 2708 } 2709 2710 if (is_num != 0) { 2711 *rback_num = onig_scan_unsigned_number(&pnum_head, name_end, enc); 2712 if (*rback_num < 0) return ONIGERR_TOO_BIG_NUMBER; 2713 else if (*rback_num == 0) { 2714 r = ONIGERR_INVALID_GROUP_NAME; 2715 goto err; 2716 } 2717 2718 *rback_num *= sign; 2719 } 2720 2721 *rname_end = name_end; 2722 *src = p; 2723 return 0; 2724 } 2725 else { 2726 while (!PEND) { 2727 name_end = p; 2728 PFETCH_S(c); 2729 if (c == end_code || c == ')') 2730 break; 2731 } 2732 if (PEND) 2733 name_end = end; 2734 2735 err: 2736 onig_scan_env_set_error_string(env, r, *src, name_end); 2737 return r; 2738 } 2739 } 2740 #else 2741 static int 2742 fetch_name(OnigCodePoint start_code, UChar** src, UChar* end, 2743 UChar** rname_end, ScanEnv* env, int* rback_num, int ref) 2744 { 2745 int r, is_num, sign; 2746 OnigCodePoint end_code; 2747 OnigCodePoint c = 0; 2748 UChar *name_end; 2749 OnigEncoding enc = env->enc; 2750 UChar *pnum_head; 2751 UChar *p = *src; 2752 PFETCH_READY; 2753 2754 *rback_num = 0; 2755 2756 end_code = get_name_end_code_point(start_code); 2757 2758 *rname_end = name_end = end; 2759 r = 0; 2760 pnum_head = *src; 2761 is_num = 0; 2762 sign = 1; 2763 2764 if (PEND) { 2765 return ONIGERR_EMPTY_GROUP_NAME; 2766 } 2767 else { 2768 PFETCH(c); 2769 if (c == end_code) 2770 return ONIGERR_EMPTY_GROUP_NAME; 2771 2772 if (ONIGENC_IS_CODE_DIGIT(enc, c)) { 2773 is_num = 1; 2774 } 2775 else if (c == '-') { 2776 is_num = 2; 2777 sign = -1; 2778 pnum_head = p; 2779 } 2780 else { 2781 r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME; 2782 } 2783 } 2784 2785 while (!PEND) { 2786 name_end = p; 2787 2788 PFETCH(c); 2789 if (c == end_code || c == ')') break; 2790 if (! ONIGENC_IS_CODE_DIGIT(enc, c)) 2791 r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME; 2792 } 2793 if (r == 0 && c != end_code) { 2794 r = ONIGERR_INVALID_GROUP_NAME; 2795 name_end = end; 2796 } 2797 2798 if (r == 0) { 2799 *rback_num = onig_scan_unsigned_number(&pnum_head, name_end, enc); 2800 if (*rback_num < 0) return ONIGERR_TOO_BIG_NUMBER; 2801 else if (*rback_num == 0) { 2802 r = ONIGERR_INVALID_GROUP_NAME; 2803 goto err; 2804 } 2805 *rback_num *= sign; 2806 2807 *rname_end = name_end; 2808 *src = p; 2809 return 0; 2810 } 2811 else { 2812 err: 2813 onig_scan_env_set_error_string(env, r, *src, name_end); 2814 return r; 2815 } 2816 } 2817 #endif /* USE_NAMED_GROUP */ 2818 2819 static void 2820 CC_ESC_WARN(ScanEnv* env, UChar *c) 2821 { 2822 if (onig_warn == onig_null_warn) return ; 2823 2824 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_WARN_CC_OP_NOT_ESCAPED) && 2825 IS_SYNTAX_BV(env->syntax, ONIG_SYN_BACKSLASH_ESCAPE_IN_CC)) { 2826 UChar buf[WARN_BUFSIZE]; 2827 onig_snprintf_with_pattern(buf, WARN_BUFSIZE, env->enc, 2828 env->pattern, env->pattern_end, 2829 (UChar* )"character class has '%s' without escape", c); 2830 (*onig_warn)((char* )buf); 2831 } 2832 } 2833 2834 static void 2835 CLOSE_BRACKET_WITHOUT_ESC_WARN(ScanEnv* env, UChar* c) 2836 { 2837 if (onig_warn == onig_null_warn) return ; 2838 2839 if (IS_SYNTAX_BV((env)->syntax, ONIG_SYN_WARN_CC_OP_NOT_ESCAPED)) { 2840 UChar buf[WARN_BUFSIZE]; 2841 onig_snprintf_with_pattern(buf, WARN_BUFSIZE, (env)->enc, 2842 (env)->pattern, (env)->pattern_end, 2843 (UChar* )"regular expression has '%s' without escape", c); 2844 (*onig_warn)((char* )buf); 2845 } 2846 } 2847 2848 static UChar* 2849 find_str_position(OnigCodePoint s[], int n, UChar* from, UChar* to, 2850 UChar **next, OnigEncoding enc) 2851 { 2852 int i; 2853 OnigCodePoint x; 2854 UChar *q; 2855 UChar *p = from; 2856 2857 while (p < to) { 2858 x = ONIGENC_MBC_TO_CODE(enc, p, to); 2859 q = p + enclen(enc, p); 2860 if (x == s[0]) { 2861 for (i = 1; i < n && q < to; i++) { 2862 x = ONIGENC_MBC_TO_CODE(enc, q, to); 2863 if (x != s[i]) break; 2864 q += enclen(enc, q); 2865 } 2866 if (i >= n) { 2867 if (IS_NOT_NULL(next)) 2868 *next = q; 2869 return p; 2870 } 2871 } 2872 p = q; 2873 } 2874 return NULL_UCHARP; 2875 } 2876 2877 static int 2878 str_exist_check_with_esc(OnigCodePoint s[], int n, UChar* from, UChar* to, 2879 OnigCodePoint bad, OnigEncoding enc, OnigSyntaxType* syn) 2880 { 2881 int i, in_esc; 2882 OnigCodePoint x; 2883 UChar *q; 2884 UChar *p = from; 2885 2886 in_esc = 0; 2887 while (p < to) { 2888 if (in_esc) { 2889 in_esc = 0; 2890 p += enclen(enc, p); 2891 } 2892 else { 2893 x = ONIGENC_MBC_TO_CODE(enc, p, to); 2894 q = p + enclen(enc, p); 2895 if (x == s[0]) { 2896 for (i = 1; i < n && q < to; i++) { 2897 x = ONIGENC_MBC_TO_CODE(enc, q, to); 2898 if (x != s[i]) break; 2899 q += enclen(enc, q); 2900 } 2901 if (i >= n) return 1; 2902 p += enclen(enc, p); 2903 } 2904 else { 2905 x = ONIGENC_MBC_TO_CODE(enc, p, to); 2906 if (x == bad) return 0; 2907 else if (x == MC_ESC(syn)) in_esc = 1; 2908 p = q; 2909 } 2910 } 2911 } 2912 return 0; 2913 } 2914 2915 static int 2916 fetch_token_in_cc(OnigToken* tok, UChar** src, UChar* end, ScanEnv* env) 2917 { 2918 int num; 2919 OnigCodePoint c, c2; 2920 OnigSyntaxType* syn = env->syntax; 2921 OnigEncoding enc = env->enc; 2922 UChar* prev; 2923 UChar* p = *src; 2924 PFETCH_READY; 2925 2926 if (PEND) { 2927 tok->type = TK_EOT; 2928 return tok->type; 2929 } 2930 2931 PFETCH(c); 2932 tok->type = TK_CHAR; 2933 tok->base = 0; 2934 tok->u.c = c; 2935 tok->escaped = 0; 2936 2937 if (c == ']') { 2938 tok->type = TK_CC_CLOSE; 2939 } 2940 else if (c == '-') { 2941 tok->type = TK_CC_RANGE; 2942 } 2943 else if (c == MC_ESC(syn)) { 2944 if (! IS_SYNTAX_BV(syn, ONIG_SYN_BACKSLASH_ESCAPE_IN_CC)) 2945 goto end; 2946 2947 if (PEND) return ONIGERR_END_PATTERN_AT_ESCAPE; 2948 2949 PFETCH(c); 2950 tok->escaped = 1; 2951 tok->u.c = c; 2952 switch (c) { 2953 case 'w': 2954 tok->type = TK_CHAR_TYPE; 2955 tok->u.prop.ctype = ONIGENC_CTYPE_WORD; 2956 tok->u.prop.not = 0; 2957 break; 2958 case 'W': 2959 tok->type = TK_CHAR_TYPE; 2960 tok->u.prop.ctype = ONIGENC_CTYPE_WORD; 2961 tok->u.prop.not = 1; 2962 break; 2963 case 'd': 2964 tok->type = TK_CHAR_TYPE; 2965 tok->u.prop.ctype = ONIGENC_CTYPE_DIGIT; 2966 tok->u.prop.not = 0; 2967 break; 2968 case 'D': 2969 tok->type = TK_CHAR_TYPE; 2970 tok->u.prop.ctype = ONIGENC_CTYPE_DIGIT; 2971 tok->u.prop.not = 1; 2972 break; 2973 case 's': 2974 tok->type = TK_CHAR_TYPE; 2975 tok->u.prop.ctype = ONIGENC_CTYPE_SPACE; 2976 tok->u.prop.not = 0; 2977 break; 2978 case 'S': 2979 tok->type = TK_CHAR_TYPE; 2980 tok->u.prop.ctype = ONIGENC_CTYPE_SPACE; 2981 tok->u.prop.not = 1; 2982 break; 2983 case 'h': 2984 if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_H_XDIGIT)) break; 2985 tok->type = TK_CHAR_TYPE; 2986 tok->u.prop.ctype = ONIGENC_CTYPE_XDIGIT; 2987 tok->u.prop.not = 0; 2988 break; 2989 case 'H': 2990 if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_H_XDIGIT)) break; 2991 tok->type = TK_CHAR_TYPE; 2992 tok->u.prop.ctype = ONIGENC_CTYPE_XDIGIT; 2993 tok->u.prop.not = 1; 2994 break; 2995 2996 case 'p': 2997 case 'P': 2998 c2 = PPEEK; 2999 if (c2 == '{' && 3000 IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY)) { 3001 PINC; 3002 tok->type = TK_CHAR_PROPERTY; 3003 tok->u.prop.not = (c == 'P' ? 1 : 0); 3004 3005 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT)) { 3006 PFETCH(c2); 3007 if (c2 == '^') { 3008 tok->u.prop.not = (tok->u.prop.not == 0 ? 1 : 0); 3009 } 3010 else 3011 PUNFETCH; 3012 } 3013 } 3014 break; 3015 3016 case 'x': 3017 if (PEND) break; 3018 3019 prev = p; 3020 if (PPEEK_IS('{') && IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_X_BRACE_HEX8)) { 3021 PINC; 3022 num = scan_unsigned_hexadecimal_number(&p, end, 8, enc); 3023 if (num < 0) return ONIGERR_TOO_BIG_WIDE_CHAR_VALUE; 3024 if (!PEND) { 3025 c2 = PPEEK; 3026 if (ONIGENC_IS_CODE_XDIGIT(enc, c2)) 3027 return ONIGERR_TOO_LONG_WIDE_CHAR_VALUE; 3028 } 3029 3030 if (p > prev + enclen(enc, prev) && !PEND && (PPEEK_IS('}'))) { 3031 PINC; 3032 tok->type = TK_CODE_POINT; 3033 tok->base = 16; 3034 tok->u.code = (OnigCodePoint )num; 3035 } 3036 else { 3037 /* can't read nothing or invalid format */ 3038 p = prev; 3039 } 3040 } 3041 else if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_X_HEX2)) { 3042 num = scan_unsigned_hexadecimal_number(&p, end, 2, enc); 3043 if (num < 0) return ONIGERR_TOO_BIG_NUMBER; 3044 if (p == prev) { /* can't read nothing. */ 3045 num = 0; /* but, it's not error */ 3046 } 3047 tok->type = TK_RAW_BYTE; 3048 tok->base = 16; 3049 tok->u.c = num; 3050 } 3051 break; 3052 3053 case 'u': 3054 if (PEND) break; 3055 3056 prev = p; 3057 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_U_HEX4)) { 3058 num = scan_unsigned_hexadecimal_number(&p, end, 4, enc); 3059 if (num < 0) return ONIGERR_TOO_BIG_NUMBER; 3060 if (p == prev) { /* can't read nothing. */ 3061 num = 0; /* but, it's not error */ 3062 } 3063 tok->type = TK_CODE_POINT; 3064 tok->base = 16; 3065 tok->u.code = (OnigCodePoint )num; 3066 } 3067 break; 3068 3069 case '0': 3070 case '1': case '2': case '3': case '4': case '5': case '6': case '7': 3071 if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_OCTAL3)) { 3072 PUNFETCH; 3073 prev = p; 3074 num = scan_unsigned_octal_number(&p, end, 3, enc); 3075 if (num < 0) return ONIGERR_TOO_BIG_NUMBER; 3076 if (p == prev) { /* can't read nothing. */ 3077 num = 0; /* but, it's not error */ 3078 } 3079 tok->type = TK_RAW_BYTE; 3080 tok->base = 8; 3081 tok->u.c = num; 3082 } 3083 break; 3084 3085 default: 3086 PUNFETCH; 3087 num = fetch_escaped_value(&p, end, env); 3088 if (num < 0) return num; 3089 if (tok->u.c != num) { 3090 tok->u.code = (OnigCodePoint )num; 3091 tok->type = TK_CODE_POINT; 3092 } 3093 break; 3094 } 3095 } 3096 else if (c == '[') { 3097 if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_POSIX_BRACKET) && (PPEEK_IS(':'))) { 3098 OnigCodePoint send[] = { (OnigCodePoint )':', (OnigCodePoint )']' }; 3099 tok->backp = p; /* point at '[' is readed */ 3100 PINC; 3101 if (str_exist_check_with_esc(send, 2, p, end, 3102 (OnigCodePoint )']', enc, syn)) { 3103 tok->type = TK_POSIX_BRACKET_OPEN; 3104 } 3105 else { 3106 PUNFETCH; 3107 goto cc_in_cc; 3108 } 3109 } 3110 else { 3111 cc_in_cc: 3112 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_CCLASS_SET_OP)) { 3113 tok->type = TK_CC_CC_OPEN; 3114 } 3115 else { 3116 CC_ESC_WARN(env, (UChar* )"["); 3117 } 3118 } 3119 } 3120 else if (c == '&') { 3121 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_CCLASS_SET_OP) && 3122 !PEND && (PPEEK_IS('&'))) { 3123 PINC; 3124 tok->type = TK_CC_AND; 3125 } 3126 } 3127 3128 end: 3129 *src = p; 3130 return tok->type; 3131 } 3132 3133 static int 3134 fetch_token(OnigToken* tok, UChar** src, UChar* end, ScanEnv* env) 3135 { 3136 int r, num; 3137 OnigCodePoint c; 3138 OnigEncoding enc = env->enc; 3139 OnigSyntaxType* syn = env->syntax; 3140 UChar* prev; 3141 UChar* p = *src; 3142 PFETCH_READY; 3143 3144 start: 3145 if (PEND) { 3146 tok->type = TK_EOT; 3147 return tok->type; 3148 } 3149 3150 tok->type = TK_STRING; 3151 tok->base = 0; 3152 tok->backp = p; 3153 3154 PFETCH(c); 3155 if (IS_MC_ESC_CODE(c, syn)) { 3156 if (PEND) return ONIGERR_END_PATTERN_AT_ESCAPE; 3157 3158 tok->backp = p; 3159 PFETCH(c); 3160 3161 tok->u.c = c; 3162 tok->escaped = 1; 3163 switch (c) { 3164 case '*': 3165 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_ASTERISK_ZERO_INF)) break; 3166 tok->type = TK_OP_REPEAT; 3167 tok->u.repeat.lower = 0; 3168 tok->u.repeat.upper = REPEAT_INFINITE; 3169 goto greedy_check; 3170 break; 3171 3172 case '+': 3173 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_PLUS_ONE_INF)) break; 3174 tok->type = TK_OP_REPEAT; 3175 tok->u.repeat.lower = 1; 3176 tok->u.repeat.upper = REPEAT_INFINITE; 3177 goto greedy_check; 3178 break; 3179 3180 case '?': 3181 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_QMARK_ZERO_ONE)) break; 3182 tok->type = TK_OP_REPEAT; 3183 tok->u.repeat.lower = 0; 3184 tok->u.repeat.upper = 1; 3185 greedy_check: 3186 if (!PEND && PPEEK_IS('?') && 3187 IS_SYNTAX_OP(syn, ONIG_SYN_OP_QMARK_NON_GREEDY)) { 3188 PFETCH(c); 3189 tok->u.repeat.greedy = 0; 3190 tok->u.repeat.possessive = 0; 3191 } 3192 else { 3193 possessive_check: 3194 if (!PEND && PPEEK_IS('+') && 3195 ((IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_PLUS_POSSESSIVE_REPEAT) && 3196 tok->type != TK_INTERVAL) || 3197 (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_PLUS_POSSESSIVE_INTERVAL) && 3198 tok->type == TK_INTERVAL))) { 3199 PFETCH(c); 3200 tok->u.repeat.greedy = 1; 3201 tok->u.repeat.possessive = 1; 3202 } 3203 else { 3204 tok->u.repeat.greedy = 1; 3205 tok->u.repeat.possessive = 0; 3206 } 3207 } 3208 break; 3209 3210 case '{': 3211 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_BRACE_INTERVAL)) break; 3212 r = fetch_range_quantifier(&p, end, tok, env); 3213 if (r < 0) return r; /* error */ 3214 if (r == 0) goto greedy_check; 3215 else if (r == 2) { /* {n} */ 3216 if (IS_SYNTAX_BV(syn, ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY)) 3217 goto possessive_check; 3218 3219 goto greedy_check; 3220 } 3221 /* r == 1 : normal char */ 3222 break; 3223 3224 case '|': 3225 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_VBAR_ALT)) break; 3226 tok->type = TK_ALT; 3227 break; 3228 3229 case '(': 3230 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_LPAREN_SUBEXP)) break; 3231 tok->type = TK_SUBEXP_OPEN; 3232 break; 3233 3234 case ')': 3235 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_LPAREN_SUBEXP)) break; 3236 tok->type = TK_SUBEXP_CLOSE; 3237 break; 3238 3239 case 'w': 3240 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_W_WORD)) break; 3241 tok->type = TK_CHAR_TYPE; 3242 tok->u.prop.ctype = ONIGENC_CTYPE_WORD; 3243 tok->u.prop.not = 0; 3244 break; 3245 3246 case 'W': 3247 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_W_WORD)) break; 3248 tok->type = TK_CHAR_TYPE; 3249 tok->u.prop.ctype = ONIGENC_CTYPE_WORD; 3250 tok->u.prop.not = 1; 3251 break; 3252 3253 case 'b': 3254 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_B_WORD_BOUND)) break; 3255 tok->type = TK_ANCHOR; 3256 tok->u.anchor = ANCHOR_WORD_BOUND; 3257 break; 3258 3259 case 'B': 3260 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_B_WORD_BOUND)) break; 3261 tok->type = TK_ANCHOR; 3262 tok->u.anchor = ANCHOR_NOT_WORD_BOUND; 3263 break; 3264 3265 #ifdef USE_WORD_BEGIN_END 3266 case '<': 3267 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END)) break; 3268 tok->type = TK_ANCHOR; 3269 tok->u.anchor = ANCHOR_WORD_BEGIN; 3270 break; 3271 3272 case '>': 3273 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END)) break; 3274 tok->type = TK_ANCHOR; 3275 tok->u.anchor = ANCHOR_WORD_END; 3276 break; 3277 #endif 3278 3279 case 's': 3280 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_S_WHITE_SPACE)) break; 3281 tok->type = TK_CHAR_TYPE; 3282 tok->u.prop.ctype = ONIGENC_CTYPE_SPACE; 3283 tok->u.prop.not = 0; 3284 break; 3285 3286 case 'S': 3287 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_S_WHITE_SPACE)) break; 3288 tok->type = TK_CHAR_TYPE; 3289 tok->u.prop.ctype = ONIGENC_CTYPE_SPACE; 3290 tok->u.prop.not = 1; 3291 break; 3292 3293 case 'd': 3294 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_D_DIGIT)) break; 3295 tok->type = TK_CHAR_TYPE; 3296 tok->u.prop.ctype = ONIGENC_CTYPE_DIGIT; 3297 tok->u.prop.not = 0; 3298 break; 3299 3300 case 'D': 3301 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_D_DIGIT)) break; 3302 tok->type = TK_CHAR_TYPE; 3303 tok->u.prop.ctype = ONIGENC_CTYPE_DIGIT; 3304 tok->u.prop.not = 1; 3305 break; 3306 3307 case 'h': 3308 if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_H_XDIGIT)) break; 3309 tok->type = TK_CHAR_TYPE; 3310 tok->u.prop.ctype = ONIGENC_CTYPE_XDIGIT; 3311 tok->u.prop.not = 0; 3312 break; 3313 3314 case 'H': 3315 if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_H_XDIGIT)) break; 3316 tok->type = TK_CHAR_TYPE; 3317 tok->u.prop.ctype = ONIGENC_CTYPE_XDIGIT; 3318 tok->u.prop.not = 1; 3319 break; 3320 3321 case 'A': 3322 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_AZ_BUF_ANCHOR)) break; 3323 begin_buf: 3324 tok->type = TK_ANCHOR; 3325 tok->u.subtype = ANCHOR_BEGIN_BUF; 3326 break; 3327 3328 case 'Z': 3329 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_AZ_BUF_ANCHOR)) break; 3330 tok->type = TK_ANCHOR; 3331 tok->u.subtype = ANCHOR_SEMI_END_BUF; 3332 break; 3333 3334 case 'z': 3335 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_AZ_BUF_ANCHOR)) break; 3336 end_buf: 3337 tok->type = TK_ANCHOR; 3338 tok->u.subtype = ANCHOR_END_BUF; 3339 break; 3340 3341 case 'G': 3342 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_CAPITAL_G_BEGIN_ANCHOR)) break; 3343 tok->type = TK_ANCHOR; 3344 tok->u.subtype = ANCHOR_BEGIN_POSITION; 3345 break; 3346 3347 case '`': 3348 if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_GNU_BUF_ANCHOR)) break; 3349 goto begin_buf; 3350 break; 3351 3352 case '\'': 3353 if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_GNU_BUF_ANCHOR)) break; 3354 goto end_buf; 3355 break; 3356 3357 case 'x': 3358 if (PEND) break; 3359 3360 prev = p; 3361 if (PPEEK_IS('{') && IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_X_BRACE_HEX8)) { 3362 PINC; 3363 num = scan_unsigned_hexadecimal_number(&p, end, 8, enc); 3364 if (num < 0) return ONIGERR_TOO_BIG_WIDE_CHAR_VALUE; 3365 if (!PEND) { 3366 if (ONIGENC_IS_CODE_XDIGIT(enc, PPEEK)) 3367 return ONIGERR_TOO_LONG_WIDE_CHAR_VALUE; 3368 } 3369 3370 if ((p > prev + enclen(enc, prev)) && !PEND && PPEEK_IS('}')) { 3371 PINC; 3372 tok->type = TK_CODE_POINT; 3373 tok->u.code = (OnigCodePoint )num; 3374 } 3375 else { 3376 /* can't read nothing or invalid format */ 3377 p = prev; 3378 } 3379 } 3380 else if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_X_HEX2)) { 3381 num = scan_unsigned_hexadecimal_number(&p, end, 2, enc); 3382 if (num < 0) return ONIGERR_TOO_BIG_NUMBER; 3383 if (p == prev) { /* can't read nothing. */ 3384 num = 0; /* but, it's not error */ 3385 } 3386 tok->type = TK_RAW_BYTE; 3387 tok->base = 16; 3388 tok->u.c = num; 3389 } 3390 break; 3391 3392 case 'u': 3393 if (PEND) break; 3394 3395 prev = p; 3396 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_U_HEX4)) { 3397 num = scan_unsigned_hexadecimal_number(&p, end, 4, enc); 3398 if (num < 0) return ONIGERR_TOO_BIG_NUMBER; 3399 if (p == prev) { /* can't read nothing. */ 3400 num = 0; /* but, it's not error */ 3401 } 3402 tok->type = TK_CODE_POINT; 3403 tok->base = 16; 3404 tok->u.code = (OnigCodePoint )num; 3405 } 3406 break; 3407 3408 case '1': case '2': case '3': case '4': 3409 case '5': case '6': case '7': case '8': case '9': 3410 PUNFETCH; 3411 prev = p; 3412 num = onig_scan_unsigned_number(&p, end, enc); 3413 if (num < 0 || num > ONIG_MAX_BACKREF_NUM) { 3414 goto skip_backref; 3415 } 3416 3417 if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_DECIMAL_BACKREF) && 3418 (num <= env->num_mem || num <= 9)) { /* This spec. from GNU regex */ 3419 if (IS_SYNTAX_BV(syn, ONIG_SYN_STRICT_CHECK_BACKREF)) { 3420 if (num > env->num_mem || IS_NULL(SCANENV_MEM_NODES(env)[num])) 3421 return ONIGERR_INVALID_BACKREF; 3422 } 3423 3424 tok->type = TK_BACKREF; 3425 tok->u.backref.num = 1; 3426 tok->u.backref.ref1 = num; 3427 tok->u.backref.by_name = 0; 3428 #ifdef USE_BACKREF_WITH_LEVEL 3429 tok->u.backref.exist_level = 0; 3430 #endif 3431 break; 3432 } 3433 3434 skip_backref: 3435 if (c == '8' || c == '9') { 3436 /* normal char */ 3437 p = prev; PINC; 3438 break; 3439 } 3440 3441 p = prev; 3442 /* fall through */ 3443 case '0': 3444 if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_OCTAL3)) { 3445 prev = p; 3446 num = scan_unsigned_octal_number(&p, end, (c == '0' ? 2:3), enc); 3447 if (num < 0) return ONIGERR_TOO_BIG_NUMBER; 3448 if (p == prev) { /* can't read nothing. */ 3449 num = 0; /* but, it's not error */ 3450 } 3451 tok->type = TK_RAW_BYTE; 3452 tok->base = 8; 3453 tok->u.c = num; 3454 } 3455 else if (c != '0') { 3456 PINC; 3457 } 3458 break; 3459 3460 #ifdef USE_NAMED_GROUP 3461 case 'k': 3462 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_K_NAMED_BACKREF)) { 3463 PFETCH(c); 3464 if (c == '<' || c == '\'') { 3465 UChar* name_end; 3466 int* backs; 3467 int back_num; 3468 3469 prev = p; 3470 3471 #ifdef USE_BACKREF_WITH_LEVEL 3472 name_end = NULL_UCHARP; /* no need. escape gcc warning. */ 3473 r = fetch_name_with_level((OnigCodePoint )c, &p, end, &name_end, 3474 env, &back_num, &tok->u.backref.level); 3475 if (r == 1) tok->u.backref.exist_level = 1; 3476 else tok->u.backref.exist_level = 0; 3477 #else 3478 r = fetch_name(&p, end, &name_end, env, &back_num, 1); 3479 #endif 3480 if (r < 0) return r; 3481 3482 if (back_num != 0) { 3483 if (back_num < 0) { 3484 back_num = BACKREF_REL_TO_ABS(back_num, env); 3485 if (back_num <= 0) 3486 return ONIGERR_INVALID_BACKREF; 3487 } 3488 3489 if (IS_SYNTAX_BV(syn, ONIG_SYN_STRICT_CHECK_BACKREF)) { 3490 if (back_num > env->num_mem || 3491 IS_NULL(SCANENV_MEM_NODES(env)[back_num])) 3492 return ONIGERR_INVALID_BACKREF; 3493 } 3494 tok->type = TK_BACKREF; 3495 tok->u.backref.by_name = 0; 3496 tok->u.backref.num = 1; 3497 tok->u.backref.ref1 = back_num; 3498 } 3499 else { 3500 num = onig_name_to_group_numbers(env->reg, prev, name_end, &backs); 3501 if (num <= 0) { 3502 onig_scan_env_set_error_string(env, 3503 ONIGERR_UNDEFINED_NAME_REFERENCE, prev, name_end); 3504 return ONIGERR_UNDEFINED_NAME_REFERENCE; 3505 } 3506 if (IS_SYNTAX_BV(syn, ONIG_SYN_STRICT_CHECK_BACKREF)) { 3507 int i; 3508 for (i = 0; i < num; i++) { 3509 if (backs[i] > env->num_mem || 3510 IS_NULL(SCANENV_MEM_NODES(env)[backs[i]])) 3511 return ONIGERR_INVALID_BACKREF; 3512 } 3513 } 3514 3515 tok->type = TK_BACKREF; 3516 tok->u.backref.by_name = 1; 3517 if (num == 1) { 3518 tok->u.backref.num = 1; 3519 tok->u.backref.ref1 = backs[0]; 3520 } 3521 else { 3522 tok->u.backref.num = num; 3523 tok->u.backref.refs = backs; 3524 } 3525 } 3526 } 3527 else 3528 PUNFETCH; 3529 } 3530 break; 3531 #endif 3532 3533 #ifdef USE_SUBEXP_CALL 3534 case 'g': 3535 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_G_SUBEXP_CALL)) { 3536 PFETCH(c); 3537 if (c == '<' || c == '\'') { 3538 int gnum; 3539 UChar* name_end; 3540 3541 prev = p; 3542 r = fetch_name((OnigCodePoint )c, &p, end, &name_end, env, &gnum, 1); 3543 if (r < 0) return r; 3544 3545 tok->type = TK_CALL; 3546 tok->u.call.name = prev; 3547 tok->u.call.name_end = name_end; 3548 tok->u.call.gnum = gnum; 3549 } 3550 else 3551 PUNFETCH; 3552 } 3553 break; 3554 #endif 3555 3556 case 'Q': 3557 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_CAPITAL_Q_QUOTE)) { 3558 tok->type = TK_QUOTE_OPEN; 3559 } 3560 break; 3561 3562 case 'p': 3563 case 'P': 3564 if (PPEEK_IS('{') && 3565 IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY)) { 3566 PINC; 3567 tok->type = TK_CHAR_PROPERTY; 3568 tok->u.prop.not = (c == 'P' ? 1 : 0); 3569 3570 if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT)) { 3571 PFETCH(c); 3572 if (c == '^') { 3573 tok->u.prop.not = (tok->u.prop.not == 0 ? 1 : 0); 3574 } 3575 else 3576 PUNFETCH; 3577 } 3578 } 3579 break; 3580 3581 default: 3582 PUNFETCH; 3583 num = fetch_escaped_value(&p, end, env); 3584 if (num < 0) return num; 3585 /* set_raw: */ 3586 if (tok->u.c != num) { 3587 tok->type = TK_CODE_POINT; 3588 tok->u.code = (OnigCodePoint )num; 3589 } 3590 else { /* string */ 3591 p = tok->backp + enclen(enc, tok->backp); 3592 } 3593 break; 3594 } 3595 } 3596 else { 3597 tok->u.c = c; 3598 tok->escaped = 0; 3599 3600 #ifdef USE_VARIABLE_META_CHARS 3601 if ((c != ONIG_INEFFECTIVE_META_CHAR) && 3602 IS_SYNTAX_OP(syn, ONIG_SYN_OP_VARIABLE_META_CHARACTERS)) { 3603 if (c == MC_ANYCHAR(syn)) 3604 goto any_char; 3605 else if (c == MC_ANYTIME(syn)) 3606 goto anytime; 3607 else if (c == MC_ZERO_OR_ONE_TIME(syn)) 3608 goto zero_or_one_time; 3609 else if (c == MC_ONE_OR_MORE_TIME(syn)) 3610 goto one_or_more_time; 3611 else if (c == MC_ANYCHAR_ANYTIME(syn)) { 3612 tok->type = TK_ANYCHAR_ANYTIME; 3613 goto out; 3614 } 3615 } 3616 #endif 3617 3618 switch (c) { 3619 case '.': 3620 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_DOT_ANYCHAR)) break; 3621 #ifdef USE_VARIABLE_META_CHARS 3622 any_char: 3623 #endif 3624 tok->type = TK_ANYCHAR; 3625 break; 3626 3627 case '*': 3628 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ASTERISK_ZERO_INF)) break; 3629 #ifdef USE_VARIABLE_META_CHARS 3630 anytime: 3631 #endif 3632 tok->type = TK_OP_REPEAT; 3633 tok->u.repeat.lower = 0; 3634 tok->u.repeat.upper = REPEAT_INFINITE; 3635 goto greedy_check; 3636 break; 3637 3638 case '+': 3639 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_PLUS_ONE_INF)) break; 3640 #ifdef USE_VARIABLE_META_CHARS 3641 one_or_more_time: 3642 #endif 3643 tok->type = TK_OP_REPEAT; 3644 tok->u.repeat.lower = 1; 3645 tok->u.repeat.upper = REPEAT_INFINITE; 3646 goto greedy_check; 3647 break; 3648 3649 case '?': 3650 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_QMARK_ZERO_ONE)) break; 3651 #ifdef USE_VARIABLE_META_CHARS 3652 zero_or_one_time: 3653 #endif 3654 tok->type = TK_OP_REPEAT; 3655 tok->u.repeat.lower = 0; 3656 tok->u.repeat.upper = 1; 3657 goto greedy_check; 3658 break; 3659 3660 case '{': 3661 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_BRACE_INTERVAL)) break; 3662 r = fetch_range_quantifier(&p, end, tok, env); 3663 if (r < 0) return r; /* error */ 3664 if (r == 0) goto greedy_check; 3665 else if (r == 2) { /* {n} */ 3666 if (IS_SYNTAX_BV(syn, ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY)) 3667 goto possessive_check; 3668 3669 goto greedy_check; 3670 } 3671 /* r == 1 : normal char */ 3672 break; 3673 3674 case '|': 3675 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_VBAR_ALT)) break; 3676 tok->type = TK_ALT; 3677 break; 3678 3679 case '(': 3680 if (PPEEK_IS('?') && 3681 IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_QMARK_GROUP_EFFECT)) { 3682 PINC; 3683 if (PPEEK_IS('#')) { 3684 PFETCH(c); 3685 while (1) { 3686 if (PEND) return ONIGERR_END_PATTERN_IN_GROUP; 3687 PFETCH(c); 3688 if (c == MC_ESC(syn)) { 3689 if (!PEND) PFETCH(c); 3690 } 3691 else { 3692 if (c == ')') break; 3693 } 3694 } 3695 goto start; 3696 } 3697 PUNFETCH; 3698 } 3699 3700 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_LPAREN_SUBEXP)) break; 3701 tok->type = TK_SUBEXP_OPEN; 3702 break; 3703 3704 case ')': 3705 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_LPAREN_SUBEXP)) break; 3706 tok->type = TK_SUBEXP_CLOSE; 3707 break; 3708 3709 case '^': 3710 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_LINE_ANCHOR)) break; 3711 tok->type = TK_ANCHOR; 3712 tok->u.subtype = (IS_SINGLELINE(env->option) 3713 ? ANCHOR_BEGIN_BUF : ANCHOR_BEGIN_LINE); 3714 break; 3715 3716 case '$': 3717 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_LINE_ANCHOR)) break; 3718 tok->type = TK_ANCHOR; 3719 tok->u.subtype = (IS_SINGLELINE(env->option) 3720 ? ANCHOR_SEMI_END_BUF : ANCHOR_END_LINE); 3721 break; 3722 3723 case '[': 3724 if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_BRACKET_CC)) break; 3725 tok->type = TK_CC_OPEN; 3726 break; 3727 3728 case ']': 3729 if (*src > env->pattern) /* /].../ is allowed. */ 3730 CLOSE_BRACKET_WITHOUT_ESC_WARN(env, (UChar* )"]"); 3731 break; 3732 3733 case '#': 3734 if (IS_EXTEND(env->option)) { 3735 while (!PEND) { 3736 PFETCH(c); 3737 if (ONIGENC_IS_CODE_NEWLINE(enc, c)) 3738 break; 3739 } 3740 goto start; 3741 break; 3742 } 3743 break; 3744 3745 case ' ': case '\t': case '\n': case '\r': case '\f': 3746 if (IS_EXTEND(env->option)) 3747 goto start; 3748 break; 3749 3750 default: 3751 /* string */ 3752 break; 3753 } 3754 } 3755 3756 #ifdef USE_VARIABLE_META_CHARS 3757 out: 3758 #endif 3759 *src = p; 3760 return tok->type; 3761 } 3762 3763 static int 3764 add_ctype_to_cc_by_range(CClassNode* cc, int ctype ARG_UNUSED, int not, 3765 OnigEncoding enc ARG_UNUSED, 3766 OnigCodePoint sb_out, const OnigCodePoint mbr[]) 3767 { 3768 int i, r; 3769 OnigCodePoint j; 3770 3771 int n = ONIGENC_CODE_RANGE_NUM(mbr); 3772 3773 if (not == 0) { 3774 for (i = 0; i < n; i++) { 3775 for (j = ONIGENC_CODE_RANGE_FROM(mbr, i); 3776 j <= ONIGENC_CODE_RANGE_TO(mbr, i); j++) { 3777 if (j >= sb_out) { 3778 if (j == ONIGENC_CODE_RANGE_TO(mbr, i)) i++; 3779 else if (j > ONIGENC_CODE_RANGE_FROM(mbr, i)) { 3780 r = add_code_range_to_buf(&(cc->mbuf), j, 3781 ONIGENC_CODE_RANGE_TO(mbr, i)); 3782 if (r != 0) return r; 3783 i++; 3784 } 3785 3786 goto sb_end; 3787 } 3788 BITSET_SET_BIT(cc->bs, j); 3789 } 3790 } 3791 3792 sb_end: 3793 for ( ; i < n; i++) { 3794 r = add_code_range_to_buf(&(cc->mbuf), 3795 ONIGENC_CODE_RANGE_FROM(mbr, i), 3796 ONIGENC_CODE_RANGE_TO(mbr, i)); 3797 if (r != 0) return r; 3798 } 3799 } 3800 else { 3801 OnigCodePoint prev = 0; 3802 3803 for (i = 0; i < n; i++) { 3804 for (j = prev; 3805 j < ONIGENC_CODE_RANGE_FROM(mbr, i); j++) { 3806 if (j >= sb_out) { 3807 goto sb_end2; 3808 } 3809 BITSET_SET_BIT(cc->bs, j); 3810 } 3811 prev = ONIGENC_CODE_RANGE_TO(mbr, i) + 1; 3812 } 3813 for (j = prev; j < sb_out; j++) { 3814 BITSET_SET_BIT(cc->bs, j); 3815 } 3816 3817 sb_end2: 3818 prev = sb_out; 3819 3820 for (i = 0; i < n; i++) { 3821 if (prev < ONIGENC_CODE_RANGE_FROM(mbr, i)) { 3822 r = add_code_range_to_buf(&(cc->mbuf), prev, 3823 ONIGENC_CODE_RANGE_FROM(mbr, i) - 1); 3824 if (r != 0) return r; 3825 } 3826 prev = ONIGENC_CODE_RANGE_TO(mbr, i) + 1; 3827 } 3828 if (prev < 0x7fffffff) { 3829 r = add_code_range_to_buf(&(cc->mbuf), prev, 0x7fffffff); 3830 if (r != 0) return r; 3831 } 3832 } 3833 3834 return 0; 3835 } 3836 3837 static int 3838 add_ctype_to_cc(CClassNode* cc, int ctype, int not, ScanEnv* env) 3839 { 3840 int c, r; 3841 const OnigCodePoint *ranges; 3842 OnigCodePoint sb_out; 3843 OnigEncoding enc = env->enc; 3844 3845 r = ONIGENC_GET_CTYPE_CODE_RANGE(enc, ctype, &sb_out, &ranges); 3846 if (r == 0) { 3847 return add_ctype_to_cc_by_range(cc, ctype, not, env->enc, sb_out, ranges); 3848 } 3849 else if (r != ONIG_NO_SUPPORT_CONFIG) { 3850 return r; 3851 } 3852 3853 r = 0; 3854 switch (ctype) { 3855 case ONIGENC_CTYPE_ALPHA: 3856 case ONIGENC_CTYPE_BLANK: 3857 case ONIGENC_CTYPE_CNTRL: 3858 case ONIGENC_CTYPE_DIGIT: 3859 case ONIGENC_CTYPE_LOWER: 3860 case ONIGENC_CTYPE_PUNCT: 3861 case ONIGENC_CTYPE_SPACE: 3862 case ONIGENC_CTYPE_UPPER: 3863 case ONIGENC_CTYPE_XDIGIT: 3864 case ONIGENC_CTYPE_ASCII: 3865 case ONIGENC_CTYPE_ALNUM: 3866 if (not != 0) { 3867 for (c = 0; c < SINGLE_BYTE_SIZE; c++) { 3868 if (! ONIGENC_IS_CODE_CTYPE(enc, (OnigCodePoint )c, ctype)) 3869 BITSET_SET_BIT(cc->bs, c); 3870 } 3871 ADD_ALL_MULTI_BYTE_RANGE(enc, cc->mbuf); 3872 } 3873 else { 3874 for (c = 0; c < SINGLE_BYTE_SIZE; c++) { 3875 if (ONIGENC_IS_CODE_CTYPE(enc, (OnigCodePoint )c, ctype)) 3876 BITSET_SET_BIT(cc->bs, c); 3877 } 3878 } 3879 break; 3880 3881 case ONIGENC_CTYPE_GRAPH: 3882 case ONIGENC_CTYPE_PRINT: 3883 if (not != 0) { 3884 for (c = 0; c < SINGLE_BYTE_SIZE; c++) { 3885 if (! ONIGENC_IS_CODE_CTYPE(enc, (OnigCodePoint )c, ctype)) 3886 BITSET_SET_BIT(cc->bs, c); 3887 } 3888 } 3889 else { 3890 for (c = 0; c < SINGLE_BYTE_SIZE; c++) { 3891 if (ONIGENC_IS_CODE_CTYPE(enc, (OnigCodePoint )c, ctype)) 3892 BITSET_SET_BIT(cc->bs, c); 3893 } 3894 ADD_ALL_MULTI_BYTE_RANGE(enc, cc->mbuf); 3895 } 3896 break; 3897 3898 case ONIGENC_CTYPE_WORD: 3899 if (not == 0) { 3900 for (c = 0; c < SINGLE_BYTE_SIZE; c++) { 3901 if (IS_CODE_SB_WORD(enc, c)) BITSET_SET_BIT(cc->bs, c); 3902 } 3903 ADD_ALL_MULTI_BYTE_RANGE(enc, cc->mbuf); 3904 } 3905 else { 3906 for (c = 0; c < SINGLE_BYTE_SIZE; c++) { 3907 if ((ONIGENC_CODE_TO_MBCLEN(enc, c) > 0) /* check invalid code point */ 3908 && ! ONIGENC_IS_CODE_WORD(enc, c)) 3909 BITSET_SET_BIT(cc->bs, c); 3910 } 3911 } 3912 break; 3913 3914 default: 3915 return ONIGERR_PARSER_BUG; 3916 break; 3917 } 3918 3919 return r; 3920 } 3921 3922 static int 3923 parse_posix_bracket(CClassNode* cc, UChar** src, UChar* end, ScanEnv* env) 3924 { 3925 #define POSIX_BRACKET_CHECK_LIMIT_LENGTH 20 3926 #define POSIX_BRACKET_NAME_MIN_LEN 4 3927 3928 static PosixBracketEntryType PBS[] = { 3929 { (UChar* )"alnum", ONIGENC_CTYPE_ALNUM, 5 }, 3930 { (UChar* )"alpha", ONIGENC_CTYPE_ALPHA, 5 }, 3931 { (UChar* )"blank", ONIGENC_CTYPE_BLANK, 5 }, 3932 { (UChar* )"cntrl", ONIGENC_CTYPE_CNTRL, 5 }, 3933 { (UChar* )"digit", ONIGENC_CTYPE_DIGIT, 5 }, 3934 { (UChar* )"graph", ONIGENC_CTYPE_GRAPH, 5 }, 3935 { (UChar* )"lower", ONIGENC_CTYPE_LOWER, 5 }, 3936 { (UChar* )"print", ONIGENC_CTYPE_PRINT, 5 }, 3937 { (UChar* )"punct", ONIGENC_CTYPE_PUNCT, 5 }, 3938 { (UChar* )"space", ONIGENC_CTYPE_SPACE, 5 }, 3939 { (UChar* )"upper", ONIGENC_CTYPE_UPPER, 5 }, 3940 { (UChar* )"xdigit", ONIGENC_CTYPE_XDIGIT, 6 }, 3941 { (UChar* )"ascii", ONIGENC_CTYPE_ASCII, 5 }, 3942 { (UChar* )"word", ONIGENC_CTYPE_WORD, 4 }, 3943 { (UChar* )NULL, -1, 0 } 3944 }; 3945 3946 PosixBracketEntryType *pb; 3947 int not, i, r; 3948 OnigCodePoint c; 3949 OnigEncoding enc = env->enc; 3950 UChar *p = *src; 3951 3952 if (PPEEK_IS('^')) { 3953 PINC_S; 3954 not = 1; 3955 } 3956 else 3957 not = 0; 3958 3959 if (onigenc_strlen(enc, p, end) < POSIX_BRACKET_NAME_MIN_LEN + 3) 3960 goto not_posix_bracket; 3961 3962 for (pb = PBS; IS_NOT_NULL(pb->name); pb++) { 3963 if (onigenc_with_ascii_strncmp(enc, p, end, pb->name, pb->len) == 0) { 3964 p = (UChar* )onigenc_step(enc, p, end, pb->len); 3965 if (onigenc_with_ascii_strncmp(enc, p, end, (UChar* )":]", 2) != 0) 3966 return ONIGERR_INVALID_POSIX_BRACKET_TYPE; 3967 3968 r = add_ctype_to_cc(cc, pb->ctype, not, env); 3969 if (r != 0) return r; 3970 3971 PINC_S; PINC_S; 3972 *src = p; 3973 return 0; 3974 } 3975 } 3976 3977 not_posix_bracket: 3978 c = 0; 3979 i = 0; 3980 while (!PEND && ((c = PPEEK) != ':') && c != ']') { 3981 PINC_S; 3982 if (++i > POSIX_BRACKET_CHECK_LIMIT_LENGTH) break; 3983 } 3984 if (c == ':' && ! PEND) { 3985 PINC_S; 3986 if (! PEND) { 3987 PFETCH_S(c); 3988 if (c == ']') 3989 return ONIGERR_INVALID_POSIX_BRACKET_TYPE; 3990 } 3991 } 3992 3993 return 1; /* 1: is not POSIX bracket, but no error. */ 3994 } 3995 3996 static int 3997 fetch_char_property_to_ctype(UChar** src, UChar* end, ScanEnv* env) 3998 { 3999 int r; 4000 OnigCodePoint c; 4001 OnigEncoding enc = env->enc; 4002 UChar *prev, *start, *p = *src; 4003 4004 r = 0; 4005 start = prev = p; 4006 4007 while (!PEND) { 4008 prev = p; 4009 PFETCH_S(c); 4010 if (c == '}') { 4011 r = ONIGENC_PROPERTY_NAME_TO_CTYPE(enc, start, prev); 4012 if (r < 0) break; 4013 4014 *src = p; 4015 return r; 4016 } 4017 else if (c == '(' || c == ')' || c == '{' || c == '|') { 4018 r = ONIGERR_INVALID_CHAR_PROPERTY_NAME; 4019 break; 4020 } 4021 } 4022 4023 onig_scan_env_set_error_string(env, r, *src, prev); 4024 return r; 4025 } 4026 4027 static int 4028 parse_char_property(Node** np, OnigToken* tok, UChar** src, UChar* end, 4029 ScanEnv* env) 4030 { 4031 int r, ctype; 4032 CClassNode* cc; 4033 4034 ctype = fetch_char_property_to_ctype(src, end, env); 4035 if (ctype < 0) return ctype; 4036 4037 *np = node_new_cclass(); 4038 CHECK_NULL_RETURN_MEMERR(*np); 4039 cc = NCCLASS(*np); 4040 r = add_ctype_to_cc(cc, ctype, 0, env); 4041 if (r != 0) return r; 4042 if (tok->u.prop.not != 0) NCCLASS_SET_NOT(cc); 4043 4044 return 0; 4045 } 4046 4047 4048 enum CCSTATE { 4049 CCS_VALUE, 4050 CCS_RANGE, 4051 CCS_COMPLETE, 4052 CCS_START 4053 }; 4054 4055 enum CCVALTYPE { 4056 CCV_SB, 4057 CCV_CODE_POINT, 4058 CCV_CLASS 4059 }; 4060 4061 static int 4062 next_state_class(CClassNode* cc, OnigCodePoint* vs, enum CCVALTYPE* type, 4063 enum CCSTATE* state, ScanEnv* env) 4064 { 4065 int r; 4066 4067 if (*state == CCS_RANGE) 4068 return ONIGERR_CHAR_CLASS_VALUE_AT_END_OF_RANGE; 4069 4070 if (*state == CCS_VALUE && *type != CCV_CLASS) { 4071 if (*type == CCV_SB) 4072 BITSET_SET_BIT(cc->bs, (int )(*vs)); 4073 else if (*type == CCV_CODE_POINT) { 4074 r = add_code_range(&(cc->mbuf), env, *vs, *vs); 4075 if (r < 0) return r; 4076 } 4077 } 4078 4079 *state = CCS_VALUE; 4080 *type = CCV_CLASS; 4081 return 0; 4082 } 4083 4084 static int 4085 next_state_val(CClassNode* cc, OnigCodePoint *vs, OnigCodePoint v, 4086 int* vs_israw, int v_israw, 4087 enum CCVALTYPE intype, enum CCVALTYPE* type, 4088 enum CCSTATE* state, ScanEnv* env) 4089 { 4090 int r; 4091 4092 switch (*state) { 4093 case CCS_VALUE: 4094 if (*type == CCV_SB) 4095 BITSET_SET_BIT(cc->bs, (int )(*vs)); 4096 else if (*type == CCV_CODE_POINT) { 4097 r = add_code_range(&(cc->mbuf), env, *vs, *vs); 4098 if (r < 0) return r; 4099 } 4100 break; 4101 4102 case CCS_RANGE: 4103 if (intype == *type) { 4104 if (intype == CCV_SB) { 4105 if (*vs > 0xff || v > 0xff) 4106 return ONIGERR_INVALID_CODE_POINT_VALUE; 4107 4108 if (*vs > v) { 4109 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_EMPTY_RANGE_IN_CC)) 4110 goto ccs_range_end; 4111 else 4112 return ONIGERR_EMPTY_RANGE_IN_CHAR_CLASS; 4113 } 4114 bitset_set_range(cc->bs, (int )*vs, (int )v); 4115 } 4116 else { 4117 r = add_code_range(&(cc->mbuf), env, *vs, v); 4118 if (r < 0) return r; 4119 } 4120 } 4121 else { 4122 #if 0 4123 if (intype == CCV_CODE_POINT && *type == CCV_SB) { 4124 #endif 4125 if (*vs > v) { 4126 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_EMPTY_RANGE_IN_CC)) 4127 goto ccs_range_end; 4128 else 4129 return ONIGERR_EMPTY_RANGE_IN_CHAR_CLASS; 4130 } 4131 bitset_set_range(cc->bs, (int )*vs, (int )(v < 0xff ? v : 0xff)); 4132 r = add_code_range(&(cc->mbuf), env, (OnigCodePoint )*vs, v); 4133 if (r < 0) return r; 4134 #if 0 4135 } 4136 else 4137 return ONIGERR_MISMATCH_CODE_LENGTH_IN_CLASS_RANGE; 4138 #endif 4139 } 4140 ccs_range_end: 4141 *state = CCS_COMPLETE; 4142 break; 4143 4144 case CCS_COMPLETE: 4145 case CCS_START: 4146 *state = CCS_VALUE; 4147 break; 4148 4149 default: 4150 break; 4151 } 4152 4153 *vs_israw = v_israw; 4154 *vs = v; 4155 *type = intype; 4156 return 0; 4157 } 4158 4159 static int 4160 code_exist_check(OnigCodePoint c, UChar* from, UChar* end, int ignore_escaped, 4161 ScanEnv* env) 4162 { 4163 int in_esc; 4164 OnigCodePoint code; 4165 OnigEncoding enc = env->enc; 4166 UChar* p = from; 4167 4168 in_esc = 0; 4169 while (! PEND) { 4170 if (ignore_escaped && in_esc) { 4171 in_esc = 0; 4172 } 4173 else { 4174 PFETCH_S(code); 4175 if (code == c) return 1; 4176 if (code == MC_ESC(env->syntax)) in_esc = 1; 4177 } 4178 } 4179 return 0; 4180 } 4181 4182 static int 4183 parse_char_class(Node** np, OnigToken* tok, UChar** src, UChar* end, 4184 ScanEnv* env) 4185 { 4186 int r, neg, len, fetched, and_start; 4187 OnigCodePoint v, vs; 4188 UChar *p; 4189 Node* node; 4190 CClassNode *cc, *prev_cc; 4191 CClassNode work_cc; 4192 4193 enum CCSTATE state; 4194 enum CCVALTYPE val_type, in_type; 4195 int val_israw, in_israw; 4196 4197 prev_cc = (CClassNode* )NULL; 4198 *np = NULL_NODE; 4199 r = fetch_token_in_cc(tok, src, end, env); 4200 if (r == TK_CHAR && tok->u.c == '^' && tok->escaped == 0) { 4201 neg = 1; 4202 r = fetch_token_in_cc(tok, src, end, env); 4203 } 4204 else { 4205 neg = 0; 4206 } 4207 4208 if (r < 0) return r; 4209 if (r == TK_CC_CLOSE) { 4210 if (! code_exist_check((OnigCodePoint )']', 4211 *src, env->pattern_end, 1, env)) 4212 return ONIGERR_EMPTY_CHAR_CLASS; 4213 4214 CC_ESC_WARN(env, (UChar* )"]"); 4215 r = tok->type = TK_CHAR; /* allow []...] */ 4216 } 4217 4218 *np = node = node_new_cclass(); 4219 CHECK_NULL_RETURN_MEMERR(node); 4220 cc = NCCLASS(node); 4221 4222 and_start = 0; 4223 state = CCS_START; 4224 p = *src; 4225 while (r != TK_CC_CLOSE) { 4226 fetched = 0; 4227 switch (r) { 4228 case TK_CHAR: 4229 len = ONIGENC_CODE_TO_MBCLEN(env->enc, tok->u.c); 4230 if (len > 1) { 4231 in_type = CCV_CODE_POINT; 4232 } 4233 else if (len < 0) { 4234 r = len; 4235 goto err; 4236 } 4237 else { 4238 sb_char: 4239 in_type = CCV_SB; 4240 } 4241 v = (OnigCodePoint )tok->u.c; 4242 in_israw = 0; 4243 goto val_entry2; 4244 break; 4245 4246 case TK_RAW_BYTE: 4247 /* tok->base != 0 : octal or hexadec. */ 4248 if (! ONIGENC_IS_SINGLEBYTE(env->enc) && tok->base != 0) { 4249 UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN]; 4250 UChar* bufe = buf + ONIGENC_CODE_TO_MBC_MAXLEN; 4251 UChar* psave = p; 4252 int i, base = tok->base; 4253 4254 buf[0] = (UChar)tok->u.c; 4255 for (i = 1; i < ONIGENC_MBC_MAXLEN(env->enc); i++) { 4256 r = fetch_token_in_cc(tok, &p, end, env); 4257 if (r < 0) goto err; 4258 if (r != TK_RAW_BYTE || tok->base != base) { 4259 fetched = 1; 4260 break; 4261 } 4262 buf[i] = (UChar)tok->u.c; 4263 } 4264 4265 if (i < ONIGENC_MBC_MINLEN(env->enc)) { 4266 r = ONIGERR_TOO_SHORT_MULTI_BYTE_STRING; 4267 goto err; 4268 } 4269 4270 len = enclen(env->enc, buf); 4271 if (i < len) { 4272 r = ONIGERR_TOO_SHORT_MULTI_BYTE_STRING; 4273 goto err; 4274 } 4275 else if (i > len) { /* fetch back */ 4276 p = psave; 4277 for (i = 1; i < len; i++) { 4278 r = fetch_token_in_cc(tok, &p, end, env); 4279 } 4280 fetched = 0; 4281 } 4282 4283 if (i == 1) { 4284 v = (OnigCodePoint )buf[0]; 4285 goto raw_single; 4286 } 4287 else { 4288 v = ONIGENC_MBC_TO_CODE(env->enc, buf, bufe); 4289 in_type = CCV_CODE_POINT; 4290 } 4291 } 4292 else { 4293 v = (OnigCodePoint )tok->u.c; 4294 raw_single: 4295 in_type = CCV_SB; 4296 } 4297 in_israw = 1; 4298 goto val_entry2; 4299 break; 4300 4301 case TK_CODE_POINT: 4302 v = tok->u.code; 4303 in_israw = 1; 4304 val_entry: 4305 len = ONIGENC_CODE_TO_MBCLEN(env->enc, v); 4306 if (len < 0) { 4307 r = len; 4308 goto err; 4309 } 4310 in_type = (len == 1 ? CCV_SB : CCV_CODE_POINT); 4311 val_entry2: 4312 r = next_state_val(cc, &vs, v, &val_israw, in_israw, in_type, &val_type, 4313 &state, env); 4314 if (r != 0) goto err; 4315 break; 4316 4317 case TK_POSIX_BRACKET_OPEN: 4318 r = parse_posix_bracket(cc, &p, end, env); 4319 if (r < 0) goto err; 4320 if (r == 1) { /* is not POSIX bracket */ 4321 CC_ESC_WARN(env, (UChar* )"["); 4322 p = tok->backp; 4323 v = (OnigCodePoint )tok->u.c; 4324 in_israw = 0; 4325 goto val_entry; 4326 } 4327 goto next_class; 4328 break; 4329 4330 case TK_CHAR_TYPE: 4331 r = add_ctype_to_cc(cc, tok->u.prop.ctype, tok->u.prop.not, env); 4332 if (r != 0) return r; 4333 4334 next_class: 4335 r = next_state_class(cc, &vs, &val_type, &state, env); 4336 if (r != 0) goto err; 4337 break; 4338 4339 case TK_CHAR_PROPERTY: 4340 { 4341 int ctype; 4342 4343 ctype = fetch_char_property_to_ctype(&p, end, env); 4344 if (ctype < 0) return ctype; 4345 r = add_ctype_to_cc(cc, ctype, tok->u.prop.not, env); 4346 if (r != 0) return r; 4347 goto next_class; 4348 } 4349 break; 4350 4351 case TK_CC_RANGE: 4352 if (state == CCS_VALUE) { 4353 r = fetch_token_in_cc(tok, &p, end, env); 4354 if (r < 0) goto err; 4355 fetched = 1; 4356 if (r == TK_CC_CLOSE) { /* allow [x-] */ 4357 range_end_val: 4358 v = (OnigCodePoint )'-'; 4359 in_israw = 0; 4360 goto val_entry; 4361 } 4362 else if (r == TK_CC_AND) { 4363 CC_ESC_WARN(env, (UChar* )"-"); 4364 goto range_end_val; 4365 } 4366 state = CCS_RANGE; 4367 } 4368 else if (state == CCS_START) { 4369 /* [-xa] is allowed */ 4370 v = (OnigCodePoint )tok->u.c; 4371 in_israw = 0; 4372 4373 r = fetch_token_in_cc(tok, &p, end, env); 4374 if (r < 0) goto err; 4375 fetched = 1; 4376 /* [--x] or [a&&-x] is warned. */ 4377 if (r == TK_CC_RANGE || and_start != 0) 4378 CC_ESC_WARN(env, (UChar* )"-"); 4379 4380 goto val_entry; 4381 } 4382 else if (state == CCS_RANGE) { 4383 CC_ESC_WARN(env, (UChar* )"-"); 4384 goto sb_char; /* [!--x] is allowed */ 4385 } 4386 else { /* CCS_COMPLETE */ 4387 r = fetch_token_in_cc(tok, &p, end, env); 4388 if (r < 0) goto err; 4389 fetched = 1; 4390 if (r == TK_CC_CLOSE) goto range_end_val; /* allow [a-b-] */ 4391 else if (r == TK_CC_AND) { 4392 CC_ESC_WARN(env, (UChar* )"-"); 4393 goto range_end_val; 4394 } 4395 4396 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_DOUBLE_RANGE_OP_IN_CC)) { 4397 CC_ESC_WARN(env, (UChar* )"-"); 4398 goto sb_char; /* [0-9-a] is allowed as [0-9\-a] */ 4399 } 4400 r = ONIGERR_UNMATCHED_RANGE_SPECIFIER_IN_CHAR_CLASS; 4401 goto err; 4402 } 4403 break; 4404 4405 case TK_CC_CC_OPEN: /* [ */ 4406 { 4407 Node *anode; 4408 CClassNode* acc; 4409 4410 r = parse_char_class(&anode, tok, &p, end, env); 4411 if (r != 0) goto cc_open_err; 4412 acc = NCCLASS(anode); 4413 r = or_cclass(cc, acc, env->enc); 4414 4415 onig_node_free(anode); 4416 cc_open_err: 4417 if (r != 0) goto err; 4418 } 4419 break; 4420 4421 case TK_CC_AND: /* && */ 4422 { 4423 if (state == CCS_VALUE) { 4424 r = next_state_val(cc, &vs, 0, &val_israw, 0, val_type, 4425 &val_type, &state, env); 4426 if (r != 0) goto err; 4427 } 4428 /* initialize local variables */ 4429 and_start = 1; 4430 state = CCS_START; 4431 4432 if (IS_NOT_NULL(prev_cc)) { 4433 r = and_cclass(prev_cc, cc, env->enc); 4434 if (r != 0) goto err; 4435 bbuf_free(cc->mbuf); 4436 } 4437 else { 4438 prev_cc = cc; 4439 cc = &work_cc; 4440 } 4441 initialize_cclass(cc); 4442 } 4443 break; 4444 4445 case TK_EOT: 4446 r = ONIGERR_PREMATURE_END_OF_CHAR_CLASS; 4447 goto err; 4448 break; 4449 default: 4450 r = ONIGERR_PARSER_BUG; 4451 goto err; 4452 break; 4453 } 4454 4455 if (fetched) 4456 r = tok->type; 4457 else { 4458 r = fetch_token_in_cc(tok, &p, end, env); 4459 if (r < 0) goto err; 4460 } 4461 } 4462 4463 if (state == CCS_VALUE) { 4464 r = next_state_val(cc, &vs, 0, &val_israw, 0, val_type, 4465 &val_type, &state, env); 4466 if (r != 0) goto err; 4467 } 4468 4469 if (IS_NOT_NULL(prev_cc)) { 4470 r = and_cclass(prev_cc, cc, env->enc); 4471 if (r != 0) goto err; 4472 bbuf_free(cc->mbuf); 4473 cc = prev_cc; 4474 } 4475 4476 if (neg != 0) 4477 NCCLASS_SET_NOT(cc); 4478 else 4479 NCCLASS_CLEAR_NOT(cc); 4480 if (IS_NCCLASS_NOT(cc) && 4481 IS_SYNTAX_BV(env->syntax, ONIG_SYN_NOT_NEWLINE_IN_NEGATIVE_CC)) { 4482 int is_empty; 4483 4484 is_empty = (IS_NULL(cc->mbuf) ? 1 : 0); 4485 if (is_empty != 0) 4486 BITSET_IS_EMPTY(cc->bs, is_empty); 4487 4488 if (is_empty == 0) { 4489 #define NEWLINE_CODE 0x0a 4490 4491 if (ONIGENC_IS_CODE_NEWLINE(env->enc, NEWLINE_CODE)) { 4492 if (ONIGENC_CODE_TO_MBCLEN(env->enc, NEWLINE_CODE) == 1) 4493 BITSET_SET_BIT(cc->bs, NEWLINE_CODE); 4494 else 4495 add_code_range(&(cc->mbuf), env, NEWLINE_CODE, NEWLINE_CODE); 4496 } 4497 } 4498 } 4499 *src = p; 4500 return 0; 4501 4502 err: 4503 if (cc != NCCLASS(*np)) 4504 bbuf_free(cc->mbuf); 4505 onig_node_free(*np); 4506 return r; 4507 } 4508 4509 static int parse_subexp(Node** top, OnigToken* tok, int term, 4510 UChar** src, UChar* end, ScanEnv* env); 4511 4512 static int 4513 parse_enclose(Node** np, OnigToken* tok, int term, UChar** src, UChar* end, 4514 ScanEnv* env) 4515 { 4516 int r, num; 4517 Node *target; 4518 OnigOptionType option; 4519 OnigCodePoint c; 4520 OnigEncoding enc = env->enc; 4521 4522 #ifdef USE_NAMED_GROUP 4523 int list_capture; 4524 #endif 4525 4526 UChar* p = *src; 4527 PFETCH_READY; 4528 4529 *np = NULL; 4530 if (PEND) return ONIGERR_END_PATTERN_WITH_UNMATCHED_PARENTHESIS; 4531 4532 option = env->option; 4533 if (PPEEK_IS('?') && 4534 IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_GROUP_EFFECT)) { 4535 PINC; 4536 if (PEND) return ONIGERR_END_PATTERN_IN_GROUP; 4537 4538 PFETCH(c); 4539 switch (c) { 4540 case ':': /* (?:...) grouping only */ 4541 group: 4542 r = fetch_token(tok, &p, end, env); 4543 if (r < 0) return r; 4544 r = parse_subexp(np, tok, term, &p, end, env); 4545 if (r < 0) return r; 4546 *src = p; 4547 return 1; /* group */ 4548 break; 4549 4550 case '=': 4551 *np = onig_node_new_anchor(ANCHOR_PREC_READ); 4552 break; 4553 case '!': /* preceding read */ 4554 *np = onig_node_new_anchor(ANCHOR_PREC_READ_NOT); 4555 break; 4556 case '>': /* (?>...) stop backtrack */ 4557 *np = node_new_enclose(ENCLOSE_STOP_BACKTRACK); 4558 break; 4559 4560 #ifdef USE_NAMED_GROUP 4561 case '\'': 4562 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP)) { 4563 goto named_group1; 4564 } 4565 else 4566 return ONIGERR_UNDEFINED_GROUP_OPTION; 4567 break; 4568 #endif 4569 4570 case '<': /* look behind (?<=...), (?<!...) */ 4571 PFETCH(c); 4572 if (c == '=') 4573 *np = onig_node_new_anchor(ANCHOR_LOOK_BEHIND); 4574 else if (c == '!') 4575 *np = onig_node_new_anchor(ANCHOR_LOOK_BEHIND_NOT); 4576 #ifdef USE_NAMED_GROUP 4577 else { 4578 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP)) { 4579 UChar *name; 4580 UChar *name_end; 4581 4582 PUNFETCH; 4583 c = '<'; 4584 4585 named_group1: 4586 list_capture = 0; 4587 4588 named_group2: 4589 name = p; 4590 r = fetch_name((OnigCodePoint )c, &p, end, &name_end, env, &num, 0); 4591 if (r < 0) return r; 4592 4593 num = scan_env_add_mem_entry(env); 4594 if (num < 0) return num; 4595 if (list_capture != 0 && num >= (int )BIT_STATUS_BITS_NUM) 4596 return ONIGERR_GROUP_NUMBER_OVER_FOR_CAPTURE_HISTORY; 4597 4598 r = name_add(env->reg, name, name_end, num, env); 4599 if (r != 0) return r; 4600 *np = node_new_enclose_memory(env->option, 1); 4601 CHECK_NULL_RETURN_MEMERR(*np); 4602 NENCLOSE(*np)->regnum = num; 4603 if (list_capture != 0) 4604 BIT_STATUS_ON_AT_SIMPLE(env->capture_history, num); 4605 env->num_named++; 4606 } 4607 else { 4608 return ONIGERR_UNDEFINED_GROUP_OPTION; 4609 } 4610 } 4611 #else 4612 else { 4613 return ONIGERR_UNDEFINED_GROUP_OPTION; 4614 } 4615 #endif 4616 break; 4617 4618 case '@': 4619 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_ATMARK_CAPTURE_HISTORY)) { 4620 #ifdef USE_NAMED_GROUP 4621 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP)) { 4622 PFETCH(c); 4623 if (c == '<' || c == '\'') { 4624 list_capture = 1; 4625 goto named_group2; /* (?@<name>...) */ 4626 } 4627 PUNFETCH; 4628 } 4629 #endif 4630 *np = node_new_enclose_memory(env->option, 0); 4631 CHECK_NULL_RETURN_MEMERR(*np); 4632 num = scan_env_add_mem_entry(env); 4633 if (num < 0) { 4634 onig_node_free(*np); 4635 return num; 4636 } 4637 else if (num >= (int )BIT_STATUS_BITS_NUM) { 4638 onig_node_free(*np); 4639 return ONIGERR_GROUP_NUMBER_OVER_FOR_CAPTURE_HISTORY; 4640 } 4641 NENCLOSE(*np)->regnum = num; 4642 BIT_STATUS_ON_AT_SIMPLE(env->capture_history, num); 4643 } 4644 else { 4645 return ONIGERR_UNDEFINED_GROUP_OPTION; 4646 } 4647 break; 4648 4649 #ifdef USE_POSIXLINE_OPTION 4650 case 'p': 4651 #endif 4652 case '-': case 'i': case 'm': case 's': case 'x': 4653 { 4654 int neg = 0; 4655 4656 while (1) { 4657 switch (c) { 4658 case ':': 4659 case ')': 4660 break; 4661 4662 case '-': neg = 1; break; 4663 case 'x': ONOFF(option, ONIG_OPTION_EXTEND, neg); break; 4664 case 'i': ONOFF(option, ONIG_OPTION_IGNORECASE, neg); break; 4665 case 's': 4666 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_OPTION_PERL)) { 4667 ONOFF(option, ONIG_OPTION_MULTILINE, neg); 4668 } 4669 else 4670 return ONIGERR_UNDEFINED_GROUP_OPTION; 4671 break; 4672 4673 case 'm': 4674 if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_OPTION_PERL)) { 4675 ONOFF(option, ONIG_OPTION_SINGLELINE, (neg == 0 ? 1 : 0)); 4676 } 4677 else if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_OPTION_RUBY)) { 4678 ONOFF(option, ONIG_OPTION_MULTILINE, neg); 4679 } 4680 else 4681 return ONIGERR_UNDEFINED_GROUP_OPTION; 4682 break; 4683 #ifdef USE_POSIXLINE_OPTION 4684 case 'p': 4685 ONOFF(option, ONIG_OPTION_MULTILINE|ONIG_OPTION_SINGLELINE, neg); 4686 break; 4687 #endif 4688 default: 4689 return ONIGERR_UNDEFINED_GROUP_OPTION; 4690 } 4691 4692 if (c == ')') { 4693 *np = node_new_option(option); 4694 CHECK_NULL_RETURN_MEMERR(*np); 4695 *src = p; 4696 return 2; /* option only */ 4697 } 4698 else if (c == ':') { 4699 OnigOptionType prev = env->option; 4700 4701 env->option = option; 4702 r = fetch_token(tok, &p, end, env); 4703 if (r < 0) return r; 4704 r = parse_subexp(&target, tok, term, &p, end, env); 4705 env->option = prev; 4706 if (r < 0) return r; 4707 *np = node_new_option(option); 4708 CHECK_NULL_RETURN_MEMERR(*np); 4709 NENCLOSE(*np)->target = target; 4710 *src = p; 4711 return 0; 4712 } 4713 4714 if (PEND) return ONIGERR_END_PATTERN_IN_GROUP; 4715 PFETCH(c); 4716 } 4717 } 4718 break; 4719 4720 default: 4721 return ONIGERR_UNDEFINED_GROUP_OPTION; 4722 } 4723 } 4724 else { 4725 if (ONIG_IS_OPTION_ON(env->option, ONIG_OPTION_DONT_CAPTURE_GROUP)) 4726 goto group; 4727 4728 *np = node_new_enclose_memory(env->option, 0); 4729 CHECK_NULL_RETURN_MEMERR(*np); 4730 num = scan_env_add_mem_entry(env); 4731 if (num < 0) return num; 4732 NENCLOSE(*np)->regnum = num; 4733 } 4734 4735 CHECK_NULL_RETURN_MEMERR(*np); 4736 r = fetch_token(tok, &p, end, env); 4737 if (r < 0) return r; 4738 r = parse_subexp(&target, tok, term, &p, end, env); 4739 if (r < 0) return r; 4740 4741 if (NTYPE(*np) == NT_ANCHOR) 4742 NANCHOR(*np)->target = target; 4743 else { 4744 NENCLOSE(*np)->target = target; 4745 if (NENCLOSE(*np)->type == ENCLOSE_MEMORY) { 4746 /* Don't move this to previous of parse_subexp() */ 4747 r = scan_env_set_mem_node(env, NENCLOSE(*np)->regnum, *np); 4748 if (r != 0) return r; 4749 } 4750 } 4751 4752 *src = p; 4753 return 0; 4754 } 4755 4756 static const char* PopularQStr[] = { 4757 "?", "*", "+", "??", "*?", "+?" 4758 }; 4759 4760 static const char* ReduceQStr[] = { 4761 "", "", "*", "*?", "??", "+ and ??", "+? and ?" 4762 }; 4763 4764 static int 4765 set_quantifier(Node* qnode, Node* target, int group, ScanEnv* env) 4766 { 4767 QtfrNode* qn; 4768 4769 qn = NQTFR(qnode); 4770 if (qn->lower == 1 && qn->upper == 1) { 4771 return 1; 4772 } 4773 4774 switch (NTYPE(target)) { 4775 case NT_STR: 4776 if (! group) { 4777 StrNode* sn = NSTR(target); 4778 if (str_node_can_be_split(sn, env->enc)) { 4779 Node* n = str_node_split_last_char(sn, env->enc); 4780 if (IS_NOT_NULL(n)) { 4781 qn->target = n; 4782 return 2; 4783 } 4784 } 4785 } 4786 break; 4787 4788 case NT_QTFR: 4789 { /* check redundant double repeat. */ 4790 /* verbose warn (?:.?)? etc... but not warn (.?)? etc... */ 4791 QtfrNode* qnt = NQTFR(target); 4792 int nestq_num = popular_quantifier_num(qn); 4793 int targetq_num = popular_quantifier_num(qnt); 4794 if (nestq_num < 0 || targetq_num < 0) { 4795 return ONIGERR_TYPE_BUG; 4796 } 4797 4798 #ifdef USE_WARNING_REDUNDANT_NESTED_REPEAT_OPERATOR 4799 if (!IS_QUANTIFIER_BY_NUMBER(qn) && !IS_QUANTIFIER_BY_NUMBER(qnt) && 4800 IS_SYNTAX_BV(env->syntax, ONIG_SYN_WARN_REDUNDANT_NESTED_REPEAT)) { 4801 UChar buf[WARN_BUFSIZE]; 4802 4803 switch(ReduceTypeTable[targetq_num][nestq_num]) { 4804 case RQ_ASIS: 4805 break; 4806 4807 case RQ_DEL: 4808 if (onig_verb_warn != onig_null_warn) { 4809 onig_snprintf_with_pattern(buf, WARN_BUFSIZE, env->enc, 4810 env->pattern, env->pattern_end, 4811 (UChar* )"redundant nested repeat operator"); 4812 (*onig_verb_warn)((char* )buf); 4813 } 4814 goto warn_exit; 4815 break; 4816 4817 default: 4818 if (onig_verb_warn != onig_null_warn) { 4819 onig_snprintf_with_pattern(buf, WARN_BUFSIZE, env->enc, 4820 env->pattern, env->pattern_end, 4821 (UChar* )"nested repeat operator %s and %s was replaced with '%s'", 4822 PopularQStr[targetq_num], PopularQStr[nestq_num], 4823 ReduceQStr[ReduceTypeTable[targetq_num][nestq_num]]); 4824 (*onig_verb_warn)((char* )buf); 4825 } 4826 goto warn_exit; 4827 break; 4828 } 4829 } 4830 4831 warn_exit: 4832 #endif 4833 if (targetq_num >= 0) { 4834 if (nestq_num >= 0) { 4835 onig_reduce_nested_quantifier(qnode, target); 4836 goto q_exit; 4837 } 4838 else if (targetq_num == 1 || targetq_num == 2) { /* * or + */ 4839 /* (?:a*){n,m}, (?:a+){n,m} => (?:a*){n,n}, (?:a+){n,n} */ 4840 if (! IS_REPEAT_INFINITE(qn->upper) && qn->upper > 1 && qn->greedy) { 4841 qn->upper = (qn->lower == 0 ? 1 : qn->lower); 4842 } 4843 } 4844 } 4845 } 4846 break; 4847 4848 default: 4849 break; 4850 } 4851 4852 qn->target = target; 4853 q_exit: 4854 return 0; 4855 } 4856 4857 4858 #ifdef USE_SHARED_CCLASS_TABLE 4859 4860 #define THRESHOLD_RANGE_NUM_FOR_SHARE_CCLASS 8 4861 4862 /* for ctype node hash table */ 4863 4864 typedef struct { 4865 OnigEncoding enc; 4866 int not; 4867 int type; 4868 } type_cclass_key; 4869 4870 static int type_cclass_cmp(type_cclass_key* x, type_cclass_key* y) 4871 { 4872 if (x->type != y->type) return 1; 4873 if (x->enc != y->enc) return 1; 4874 if (x->not != y->not) return 1; 4875 return 0; 4876 } 4877 4878 static int type_cclass_hash(type_cclass_key* key) 4879 { 4880 int i, val; 4881 UChar *p; 4882 4883 val = 0; 4884 4885 p = (UChar* )&(key->enc); 4886 for (i = 0; i < (int )sizeof(key->enc); i++) { 4887 val = val * 997 + (int )*p++; 4888 } 4889 4890 p = (UChar* )(&key->type); 4891 for (i = 0; i < (int )sizeof(key->type); i++) { 4892 val = val * 997 + (int )*p++; 4893 } 4894 4895 val += key->not; 4896 return val + (val >> 5); 4897 } 4898 4899 static struct st_hash_type type_type_cclass_hash = { 4900 type_cclass_cmp, 4901 type_cclass_hash, 4902 }; 4903 4904 static st_table* OnigTypeCClassTable; 4905 4906 4907 static int 4908 i_free_shared_class(type_cclass_key* key, Node* node, void* arg ARG_UNUSED) 4909 { 4910 if (IS_NOT_NULL(node)) { 4911 CClassNode* cc = NCCLASS(node); 4912 if (IS_NOT_NULL(cc->mbuf)) xfree(cc->mbuf); 4913 xfree(node); 4914 } 4915 4916 if (IS_NOT_NULL(key)) xfree(key); 4917 return ST_DELETE; 4918 } 4919 4920 extern int 4921 onig_free_shared_cclass_table(void) 4922 { 4923 if (IS_NOT_NULL(OnigTypeCClassTable)) { 4924 onig_st_foreach(OnigTypeCClassTable, i_free_shared_class, 0); 4925 onig_st_free_table(OnigTypeCClassTable); 4926 OnigTypeCClassTable = NULL; 4927 } 4928 4929 return 0; 4930 } 4931 4932 #endif /* USE_SHARED_CCLASS_TABLE */ 4933 4934 4935 #ifndef CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS 4936 static int 4937 clear_not_flag_cclass(CClassNode* cc, OnigEncoding enc) 4938 { 4939 BBuf *tbuf; 4940 int r; 4941 4942 if (IS_NCCLASS_NOT(cc)) { 4943 bitset_invert(cc->bs); 4944 4945 if (! ONIGENC_IS_SINGLEBYTE(enc)) { 4946 r = not_code_range_buf(enc, cc->mbuf, &tbuf); 4947 if (r != 0) return r; 4948 4949 bbuf_free(cc->mbuf); 4950 cc->mbuf = tbuf; 4951 } 4952 4953 NCCLASS_CLEAR_NOT(cc); 4954 } 4955 4956 return 0; 4957 } 4958 #endif /* CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS */ 4959 4960 typedef struct { 4961 ScanEnv* env; 4962 CClassNode* cc; 4963 Node* alt_root; 4964 Node** ptail; 4965 } IApplyCaseFoldArg; 4966 4967 static int 4968 i_apply_case_fold(OnigCodePoint from, OnigCodePoint to[], 4969 int to_len, void* arg) 4970 { 4971 IApplyCaseFoldArg* iarg; 4972 ScanEnv* env; 4973 CClassNode* cc; 4974 BitSetRef bs; 4975 4976 iarg = (IApplyCaseFoldArg* )arg; 4977 env = iarg->env; 4978 cc = iarg->cc; 4979 bs = cc->bs; 4980 4981 if (to_len == 1) { 4982 int is_in = onig_is_code_in_cc(env->enc, from, cc); 4983 #ifdef CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS 4984 if ((is_in != 0 && !IS_NCCLASS_NOT(cc)) || 4985 (is_in == 0 && IS_NCCLASS_NOT(cc))) { 4986 if (ONIGENC_MBC_MINLEN(env->enc) > 1 || *to >= SINGLE_BYTE_SIZE) { 4987 add_code_range(&(cc->mbuf), env, *to, *to); 4988 } 4989 else { 4990 BITSET_SET_BIT(bs, *to); 4991 } 4992 } 4993 #else 4994 if (is_in != 0) { 4995 if (ONIGENC_MBC_MINLEN(env->enc) > 1 || *to >= SINGLE_BYTE_SIZE) { 4996 if (IS_NCCLASS_NOT(cc)) clear_not_flag_cclass(cc, env->enc); 4997 add_code_range(&(cc->mbuf), env, *to, *to); 4998 } 4999 else { 5000 if (IS_NCCLASS_NOT(cc)) { 5001 BITSET_CLEAR_BIT(bs, *to); 5002 } 5003 else 5004 BITSET_SET_BIT(bs, *to); 5005 } 5006 } 5007 #endif /* CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS */ 5008 } 5009 else { 5010 int r, i, len; 5011 UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN]; 5012 Node *snode = NULL_NODE; 5013 5014 if (onig_is_code_in_cc(env->enc, from, cc) 5015 #ifdef CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS 5016 && !IS_NCCLASS_NOT(cc) 5017 #endif 5018 ) { 5019 for (i = 0; i < to_len; i++) { 5020 len = ONIGENC_CODE_TO_MBC(env->enc, to[i], buf); 5021 if (i == 0) { 5022 snode = onig_node_new_str(buf, buf + len); 5023 CHECK_NULL_RETURN_MEMERR(snode); 5024 5025 /* char-class expanded multi-char only 5026 compare with string folded at match time. */ 5027 NSTRING_SET_AMBIG(snode); 5028 } 5029 else { 5030 r = onig_node_str_cat(snode, buf, buf + len); 5031 if (r < 0) { 5032 onig_node_free(snode); 5033 return r; 5034 } 5035 } 5036 } 5037 5038 *(iarg->ptail) = onig_node_new_alt(snode, NULL_NODE); 5039 CHECK_NULL_RETURN_MEMERR(*(iarg->ptail)); 5040 iarg->ptail = &(NCDR((*(iarg->ptail)))); 5041 } 5042 } 5043 5044 return 0; 5045 } 5046 5047 static int 5048 parse_exp(Node** np, OnigToken* tok, int term, 5049 UChar** src, UChar* end, ScanEnv* env) 5050 { 5051 int r, len, group = 0; 5052 Node* qn; 5053 Node** targetp; 5054 5055 *np = NULL; 5056 if (tok->type == (enum TokenSyms )term) 5057 goto end_of_token; 5058 5059 switch (tok->type) { 5060 case TK_ALT: 5061 case TK_EOT: 5062 end_of_token: 5063 *np = node_new_empty(); 5064 return tok->type; 5065 break; 5066 5067 case TK_SUBEXP_OPEN: 5068 r = parse_enclose(np, tok, TK_SUBEXP_CLOSE, src, end, env); 5069 if (r < 0) return r; 5070 if (r == 1) group = 1; 5071 else if (r == 2) { /* option only */ 5072 Node* target; 5073 OnigOptionType prev = env->option; 5074 5075 env->option = NENCLOSE(*np)->option; 5076 r = fetch_token(tok, src, end, env); 5077 if (r < 0) return r; 5078 r = parse_subexp(&target, tok, term, src, end, env); 5079 env->option = prev; 5080 if (r < 0) return r; 5081 NENCLOSE(*np)->target = target; 5082 return tok->type; 5083 } 5084 break; 5085 5086 case TK_SUBEXP_CLOSE: 5087 if (! IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_UNMATCHED_CLOSE_SUBEXP)) 5088 return ONIGERR_UNMATCHED_CLOSE_PARENTHESIS; 5089 5090 if (tok->escaped) goto tk_raw_byte; 5091 else goto tk_byte; 5092 break; 5093 5094 case TK_STRING: 5095 tk_byte: 5096 { 5097 *np = node_new_str(tok->backp, *src); 5098 CHECK_NULL_RETURN_MEMERR(*np); 5099 5100 while (1) { 5101 r = fetch_token(tok, src, end, env); 5102 if (r < 0) return r; 5103 if (r != TK_STRING) break; 5104 5105 r = onig_node_str_cat(*np, tok->backp, *src); 5106 if (r < 0) return r; 5107 } 5108 5109 string_end: 5110 targetp = np; 5111 goto repeat; 5112 } 5113 break; 5114 5115 case TK_RAW_BYTE: 5116 tk_raw_byte: 5117 { 5118 *np = node_new_str_raw_char((UChar )tok->u.c); 5119 CHECK_NULL_RETURN_MEMERR(*np); 5120 len = 1; 5121 while (1) { 5122 if (len >= ONIGENC_MBC_MINLEN(env->enc)) { 5123 if (len == enclen(env->enc, NSTR(*np)->s)) { 5124 r = fetch_token(tok, src, end, env); 5125 NSTRING_CLEAR_RAW(*np); 5126 goto string_end; 5127 } 5128 } 5129 5130 r = fetch_token(tok, src, end, env); 5131 if (r < 0) return r; 5132 if (r != TK_RAW_BYTE) { 5133 /* Don't use this, it is wrong for little endian encodings. */ 5134 #ifdef USE_PAD_TO_SHORT_BYTE_CHAR 5135 int rem; 5136 if (len < ONIGENC_MBC_MINLEN(env->enc)) { 5137 rem = ONIGENC_MBC_MINLEN(env->enc) - len; 5138 (void )node_str_head_pad(NSTR(*np), rem, (UChar )0); 5139 if (len + rem == enclen(env->enc, NSTR(*np)->s)) { 5140 NSTRING_CLEAR_RAW(*np); 5141 goto string_end; 5142 } 5143 } 5144 #endif 5145 return ONIGERR_TOO_SHORT_MULTI_BYTE_STRING; 5146 } 5147 5148 r = node_str_cat_char(*np, (UChar )tok->u.c); 5149 if (r < 0) return r; 5150 5151 len++; 5152 } 5153 } 5154 break; 5155 5156 case TK_CODE_POINT: 5157 { 5158 UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN]; 5159 int num = ONIGENC_CODE_TO_MBC(env->enc, tok->u.code, buf); 5160 if (num < 0) return num; 5161 #ifdef NUMBERED_CHAR_IS_NOT_CASE_AMBIG 5162 *np = node_new_str_raw(buf, buf + num); 5163 #else 5164 *np = node_new_str(buf, buf + num); 5165 #endif 5166 CHECK_NULL_RETURN_MEMERR(*np); 5167 } 5168 break; 5169 5170 case TK_QUOTE_OPEN: 5171 { 5172 OnigCodePoint end_op[2]; 5173 UChar *qstart, *qend, *nextp; 5174 5175 end_op[0] = (OnigCodePoint )MC_ESC(env->syntax); 5176 end_op[1] = (OnigCodePoint )'E'; 5177 qstart = *src; 5178 qend = find_str_position(end_op, 2, qstart, end, &nextp, env->enc); 5179 if (IS_NULL(qend)) { 5180 nextp = qend = end; 5181 } 5182 *np = node_new_str(qstart, qend); 5183 CHECK_NULL_RETURN_MEMERR(*np); 5184 *src = nextp; 5185 } 5186 break; 5187 5188 case TK_CHAR_TYPE: 5189 { 5190 switch (tok->u.prop.ctype) { 5191 case ONIGENC_CTYPE_WORD: 5192 *np = node_new_ctype(tok->u.prop.ctype, tok->u.prop.not); 5193 CHECK_NULL_RETURN_MEMERR(*np); 5194 break; 5195 5196 case ONIGENC_CTYPE_SPACE: 5197 case ONIGENC_CTYPE_DIGIT: 5198 case ONIGENC_CTYPE_XDIGIT: 5199 { 5200 CClassNode* cc; 5201 5202 #ifdef USE_SHARED_CCLASS_TABLE 5203 const OnigCodePoint *mbr; 5204 OnigCodePoint sb_out; 5205 5206 r = ONIGENC_GET_CTYPE_CODE_RANGE(env->enc, tok->u.prop.ctype, 5207 &sb_out, &mbr); 5208 if (r == 0 && 5209 ONIGENC_CODE_RANGE_NUM(mbr) 5210 >= THRESHOLD_RANGE_NUM_FOR_SHARE_CCLASS) { 5211 type_cclass_key key; 5212 type_cclass_key* new_key; 5213 5214 key.enc = env->enc; 5215 key.not = tok->u.prop.not; 5216 key.type = tok->u.prop.ctype; 5217 5218 THREAD_ATOMIC_START; 5219 5220 if (IS_NULL(OnigTypeCClassTable)) { 5221 OnigTypeCClassTable 5222 = onig_st_init_table_with_size(&type_type_cclass_hash, 10); 5223 if (IS_NULL(OnigTypeCClassTable)) { 5224 THREAD_ATOMIC_END; 5225 return ONIGERR_MEMORY; 5226 } 5227 } 5228 else { 5229 if (onig_st_lookup(OnigTypeCClassTable, (st_data_t )(UINTN)&key, 5230 (st_data_t* )np)) { 5231 THREAD_ATOMIC_END; 5232 break; 5233 } 5234 } 5235 5236 *np = node_new_cclass_by_codepoint_range(tok->u.prop.not, 5237 sb_out, mbr); 5238 if (IS_NULL(*np)) { 5239 THREAD_ATOMIC_END; 5240 return ONIGERR_MEMORY; 5241 } 5242 5243 cc = NCCLASS(*np); 5244 NCCLASS_SET_SHARE(cc); 5245 new_key = (type_cclass_key* )xmalloc(sizeof(type_cclass_key)); 5246 CHECK_NULL_RETURN_MEMERR(new_key); 5247 xmemcpy(new_key, &key, sizeof(type_cclass_key)); 5248 onig_st_add_direct(OnigTypeCClassTable, (st_data_t )(UINTN)new_key, 5249 (st_data_t )(UINTN)*np); 5250 5251 THREAD_ATOMIC_END; 5252 } 5253 else { 5254 #endif 5255 *np = node_new_cclass(); 5256 CHECK_NULL_RETURN_MEMERR(*np); 5257 cc = NCCLASS(*np); 5258 add_ctype_to_cc(cc, tok->u.prop.ctype, 0, env); 5259 if (tok->u.prop.not != 0) NCCLASS_SET_NOT(cc); 5260 #ifdef USE_SHARED_CCLASS_TABLE 5261 } 5262 #endif 5263 } 5264 break; 5265 5266 default: 5267 return ONIGERR_PARSER_BUG; 5268 break; 5269 } 5270 } 5271 break; 5272 5273 case TK_CHAR_PROPERTY: 5274 r = parse_char_property(np, tok, src, end, env); 5275 if (r != 0) return r; 5276 break; 5277 5278 case TK_CC_OPEN: 5279 { 5280 CClassNode* cc; 5281 5282 r = parse_char_class(np, tok, src, end, env); 5283 if (r != 0) return r; 5284 5285 cc = NCCLASS(*np); 5286 if (IS_IGNORECASE(env->option)) { 5287 IApplyCaseFoldArg iarg; 5288 5289 iarg.env = env; 5290 iarg.cc = cc; 5291 iarg.alt_root = NULL_NODE; 5292 iarg.ptail = &(iarg.alt_root); 5293 5294 r = ONIGENC_APPLY_ALL_CASE_FOLD(env->enc, env->case_fold_flag, 5295 i_apply_case_fold, &iarg); 5296 if (r != 0) { 5297 onig_node_free(iarg.alt_root); 5298 return r; 5299 } 5300 if (IS_NOT_NULL(iarg.alt_root)) { 5301 Node* work = onig_node_new_alt(*np, iarg.alt_root); 5302 if (IS_NULL(work)) { 5303 onig_node_free(iarg.alt_root); 5304 return ONIGERR_MEMORY; 5305 } 5306 *np = work; 5307 } 5308 } 5309 } 5310 break; 5311 5312 case TK_ANYCHAR: 5313 *np = node_new_anychar(); 5314 CHECK_NULL_RETURN_MEMERR(*np); 5315 break; 5316 5317 case TK_ANYCHAR_ANYTIME: 5318 *np = node_new_anychar(); 5319 CHECK_NULL_RETURN_MEMERR(*np); 5320 qn = node_new_quantifier(0, REPEAT_INFINITE, 0); 5321 CHECK_NULL_RETURN_MEMERR(qn); 5322 NQTFR(qn)->target = *np; 5323 *np = qn; 5324 break; 5325 5326 case TK_BACKREF: 5327 len = tok->u.backref.num; 5328 *np = node_new_backref(len, 5329 (len > 1 ? tok->u.backref.refs : &(tok->u.backref.ref1)), 5330 tok->u.backref.by_name, 5331 #ifdef USE_BACKREF_WITH_LEVEL 5332 tok->u.backref.exist_level, 5333 tok->u.backref.level, 5334 #endif 5335 env); 5336 CHECK_NULL_RETURN_MEMERR(*np); 5337 break; 5338 5339 #ifdef USE_SUBEXP_CALL 5340 case TK_CALL: 5341 { 5342 int gnum = tok->u.call.gnum; 5343 5344 if (gnum < 0) { 5345 gnum = BACKREF_REL_TO_ABS(gnum, env); 5346 if (gnum <= 0) 5347 return ONIGERR_INVALID_BACKREF; 5348 } 5349 *np = node_new_call(tok->u.call.name, tok->u.call.name_end, gnum); 5350 CHECK_NULL_RETURN_MEMERR(*np); 5351 env->num_call++; 5352 } 5353 break; 5354 #endif 5355 5356 case TK_ANCHOR: 5357 *np = onig_node_new_anchor(tok->u.anchor); 5358 CHECK_NULL_RETURN_MEMERR(*np); 5359 break; 5360 5361 case TK_OP_REPEAT: 5362 case TK_INTERVAL: 5363 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_CONTEXT_INDEP_REPEAT_OPS)) { 5364 if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_CONTEXT_INVALID_REPEAT_OPS)) 5365 return ONIGERR_TARGET_OF_REPEAT_OPERATOR_NOT_SPECIFIED; 5366 else 5367 *np = node_new_empty(); 5368 CHECK_NULL_RETURN_MEMERR(*np); 5369 } 5370 else { 5371 goto tk_byte; 5372 } 5373 break; 5374 5375 default: 5376 return ONIGERR_PARSER_BUG; 5377 break; 5378 } 5379 5380 { 5381 targetp = np; 5382 5383 re_entry: 5384 r = fetch_token(tok, src, end, env); 5385 if (r < 0) return r; 5386 5387 repeat: 5388 if (r == TK_OP_REPEAT || r == TK_INTERVAL) { 5389 if (is_invalid_quantifier_target(*targetp)) 5390 return ONIGERR_TARGET_OF_REPEAT_OPERATOR_INVALID; 5391 5392 qn = node_new_quantifier(tok->u.repeat.lower, tok->u.repeat.upper, 5393 (r == TK_INTERVAL ? 1 : 0)); 5394 CHECK_NULL_RETURN_MEMERR(qn); 5395 NQTFR(qn)->greedy = tok->u.repeat.greedy; 5396 r = set_quantifier(qn, *targetp, group, env); 5397 if (r < 0) { 5398 onig_node_free(qn); 5399 return r; 5400 } 5401 5402 if (tok->u.repeat.possessive != 0) { 5403 Node* en; 5404 en = node_new_enclose(ENCLOSE_STOP_BACKTRACK); 5405 if (IS_NULL(en)) { 5406 onig_node_free(qn); 5407 return ONIGERR_MEMORY; 5408 } 5409 NENCLOSE(en)->target = qn; 5410 qn = en; 5411 } 5412 5413 if (r == 0) { 5414 *targetp = qn; 5415 } 5416 else if (r == 1) { 5417 onig_node_free(qn); 5418 } 5419 else if (r == 2) { /* split case: /abc+/ */ 5420 Node *tmp; 5421 5422 *targetp = node_new_list(*targetp, NULL); 5423 if (IS_NULL(*targetp)) { 5424 onig_node_free(qn); 5425 return ONIGERR_MEMORY; 5426 } 5427 tmp = NCDR(*targetp) = node_new_list(qn, NULL); 5428 if (IS_NULL(tmp)) { 5429 onig_node_free(qn); 5430 return ONIGERR_MEMORY; 5431 } 5432 targetp = &(NCAR(tmp)); 5433 } 5434 goto re_entry; 5435 } 5436 } 5437 5438 return r; 5439 } 5440 5441 static int 5442 parse_branch(Node** top, OnigToken* tok, int term, 5443 UChar** src, UChar* end, ScanEnv* env) 5444 { 5445 int r; 5446 Node *node, **headp; 5447 5448 *top = NULL; 5449 r = parse_exp(&node, tok, term, src, end, env); 5450 if (r < 0) return r; 5451 5452 if (r == TK_EOT || r == term || r == TK_ALT) { 5453 *top = node; 5454 } 5455 else { 5456 *top = node_new_list(node, NULL); 5457 CHECK_NULL_RETURN_MEMERR(*top); 5458 headp = &(NCDR(*top)); 5459 while (r != TK_EOT && r != term && r != TK_ALT) { 5460 r = parse_exp(&node, tok, term, src, end, env); 5461 CHECK_NULL_RETURN_MEMERR(node); 5462 if (r < 0) return r; 5463 5464 if (NTYPE(node) == NT_LIST) { 5465 *headp = node; 5466 while (IS_NOT_NULL(NCDR(node))) node = NCDR(node); 5467 headp = &(NCDR(node)); 5468 } 5469 else { 5470 *headp = node_new_list(node, NULL); 5471 headp = &(NCDR(*headp)); 5472 } 5473 } 5474 } 5475 5476 return r; 5477 } 5478 5479 /* term_tok: TK_EOT or TK_SUBEXP_CLOSE */ 5480 static int 5481 parse_subexp(Node** top, OnigToken* tok, int term, 5482 UChar** src, UChar* end, ScanEnv* env) 5483 { 5484 int r; 5485 Node *node, **headp; 5486 5487 *top = NULL; 5488 r = parse_branch(&node, tok, term, src, end, env); 5489 if (r < 0) { 5490 onig_node_free(node); 5491 return r; 5492 } 5493 5494 if (r == term) { 5495 *top = node; 5496 } 5497 else if (r == TK_ALT) { 5498 *top = onig_node_new_alt(node, NULL); 5499 CHECK_NULL_RETURN_MEMERR(*top); 5500 headp = &(NCDR(*top)); 5501 while (r == TK_ALT) { 5502 r = fetch_token(tok, src, end, env); 5503 if (r < 0) return r; 5504 r = parse_branch(&node, tok, term, src, end, env); 5505 if (r < 0) return r; 5506 5507 *headp = onig_node_new_alt(node, NULL); 5508 headp = &(NCDR(*headp)); 5509 } 5510 5511 if (tok->type != (enum TokenSyms )term) 5512 goto err; 5513 } 5514 else { 5515 err: 5516 if (term == TK_SUBEXP_CLOSE) 5517 return ONIGERR_END_PATTERN_WITH_UNMATCHED_PARENTHESIS; 5518 else 5519 return ONIGERR_PARSER_BUG; 5520 } 5521 5522 return r; 5523 } 5524 5525 static int 5526 parse_regexp(Node** top, UChar** src, UChar* end, ScanEnv* env) 5527 { 5528 int r; 5529 OnigToken tok; 5530 5531 r = fetch_token(&tok, src, end, env); 5532 if (r < 0) return r; 5533 r = parse_subexp(top, &tok, TK_EOT, src, end, env); 5534 if (r < 0) return r; 5535 return 0; 5536 } 5537 5538 extern int 5539 onig_parse_make_tree(Node** root, const UChar* pattern, const UChar* end, 5540 regex_t* reg, ScanEnv* env) 5541 { 5542 int r; 5543 UChar* p; 5544 5545 #ifdef USE_NAMED_GROUP 5546 names_clear(reg); 5547 #endif 5548 5549 scan_env_clear(env); 5550 env->option = reg->options; 5551 env->case_fold_flag = reg->case_fold_flag; 5552 env->enc = reg->enc; 5553 env->syntax = reg->syntax; 5554 env->pattern = (UChar* )pattern; 5555 env->pattern_end = (UChar* )end; 5556 env->reg = reg; 5557 5558 *root = NULL; 5559 p = (UChar* )pattern; 5560 r = parse_regexp(root, &p, (UChar* )end, env); 5561 reg->num_mem = env->num_mem; 5562 return r; 5563 } 5564 5565 extern void 5566 onig_scan_env_set_error_string(ScanEnv* env, int ecode ARG_UNUSED, 5567 UChar* arg, UChar* arg_end) 5568 { 5569 env->error = arg; 5570 env->error_end = arg_end; 5571 } 5572
