granicus.if.org Git - onig/blob - src/regparse.c

   1 /**********************************************************************
   2   regparse.c -  Oniguruma (regular expression library)
   3 **********************************************************************/
   4 /*-
   5  * Copyright (c) 2002-2018  K.Kosako  <sndgk393 AT ybb DOT ne DOT jp>
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29
  30 #include "regparse.h"
  31 #include "st.h"
  32
  33 #ifdef DEBUG_NODE_FREE
  34 #include <stdio.h>
  35 #endif
  36
  37 #define WARN_BUFSIZE    256
  38
  39 #define CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS
  40
  41
  42 OnigSyntaxType OnigSyntaxOniguruma = {
  43   (( SYN_GNU_REGEX_OP | ONIG_SYN_OP_QMARK_NON_GREEDY |
  44      ONIG_SYN_OP_ESC_OCTAL3 | ONIG_SYN_OP_ESC_X_HEX2 |
  45      ONIG_SYN_OP_ESC_X_BRACE_HEX8 | ONIG_SYN_OP_ESC_O_BRACE_OCTAL |
  46      ONIG_SYN_OP_ESC_CONTROL_CHARS |
  47      ONIG_SYN_OP_ESC_C_CONTROL )
  48    & ~ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END )
  49   , ( ONIG_SYN_OP2_QMARK_GROUP_EFFECT |
  50       ONIG_SYN_OP2_OPTION_RUBY |
  51       ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP | ONIG_SYN_OP2_ESC_K_NAMED_BACKREF |
  52       ONIG_SYN_OP2_QMARK_LPAREN_IF_ELSE |
  53       ONIG_SYN_OP2_QMARK_TILDE_ABSENT_GROUP |
  54       ONIG_SYN_OP2_QMARK_BRACE_CALLOUT |
  55       ONIG_SYN_OP2_ESC_X_Y_GRAPHEME_CLUSTER |
  56       ONIG_SYN_OP2_ESC_CAPITAL_R_GENERAL_NEWLINE |
  57       ONIG_SYN_OP2_ESC_CAPITAL_N_O_SUPER_DOT |
  58       ONIG_SYN_OP2_ESC_CAPITAL_K_KEEP |
  59       ONIG_SYN_OP2_ESC_G_SUBEXP_CALL |
  60       ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY  |
  61       ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT |
  62       ONIG_SYN_OP2_PLUS_POSSESSIVE_REPEAT |
  63       ONIG_SYN_OP2_CCLASS_SET_OP | ONIG_SYN_OP2_ESC_CAPITAL_C_BAR_CONTROL |
  64       ONIG_SYN_OP2_ESC_CAPITAL_M_BAR_META | ONIG_SYN_OP2_ESC_V_VTAB |
  65       ONIG_SYN_OP2_ESC_H_XDIGIT | ONIG_SYN_OP2_ESC_U_HEX4 )
  66   , ( SYN_GNU_REGEX_BV |
  67       ONIG_SYN_ALLOW_INTERVAL_LOW_ABBREV |
  68       ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND |
  69       ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP |
  70       ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME |
  71       ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY |
  72       ONIG_SYN_WARN_CC_OP_NOT_ESCAPED |
  73       ONIG_SYN_WARN_REDUNDANT_NESTED_REPEAT )
  74   , ONIG_OPTION_NONE
  75   ,
  76   {
  77       (OnigCodePoint )'\\'                       /* esc */
  78     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar '.'  */
  79     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anytime '*'  */
  80     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* zero or one time '?' */
  81     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* one or more time '+' */
  82     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar anytime */
  83   }
  84 };
  85
  86 OnigSyntaxType OnigSyntaxRuby = {
  87   (( SYN_GNU_REGEX_OP | ONIG_SYN_OP_QMARK_NON_GREEDY |
  88      ONIG_SYN_OP_ESC_OCTAL3 | ONIG_SYN_OP_ESC_X_HEX2 |
  89      ONIG_SYN_OP_ESC_X_BRACE_HEX8 | ONIG_SYN_OP_ESC_O_BRACE_OCTAL |
  90      ONIG_SYN_OP_ESC_CONTROL_CHARS |
  91      ONIG_SYN_OP_ESC_C_CONTROL )
  92    & ~ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END )
  93   , ( ONIG_SYN_OP2_QMARK_GROUP_EFFECT |
  94       ONIG_SYN_OP2_OPTION_RUBY |
  95       ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP | ONIG_SYN_OP2_ESC_K_NAMED_BACKREF |
  96       ONIG_SYN_OP2_QMARK_LPAREN_IF_ELSE |
  97       ONIG_SYN_OP2_QMARK_TILDE_ABSENT_GROUP |
  98       ONIG_SYN_OP2_ESC_X_Y_GRAPHEME_CLUSTER |
  99       ONIG_SYN_OP2_ESC_CAPITAL_R_GENERAL_NEWLINE |
 100       ONIG_SYN_OP2_ESC_CAPITAL_K_KEEP |
 101       ONIG_SYN_OP2_ESC_G_SUBEXP_CALL |
 102       ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY  |
 103       ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT |
 104       ONIG_SYN_OP2_PLUS_POSSESSIVE_REPEAT |
 105       ONIG_SYN_OP2_CCLASS_SET_OP | ONIG_SYN_OP2_ESC_CAPITAL_C_BAR_CONTROL |
 106       ONIG_SYN_OP2_ESC_CAPITAL_M_BAR_META | ONIG_SYN_OP2_ESC_V_VTAB |
 107       ONIG_SYN_OP2_ESC_H_XDIGIT | ONIG_SYN_OP2_ESC_U_HEX4 )
 108   , ( SYN_GNU_REGEX_BV |
 109       ONIG_SYN_ALLOW_INTERVAL_LOW_ABBREV |
 110       ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND |
 111       ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP |
 112       ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME |
 113       ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY |
 114       ONIG_SYN_WARN_CC_OP_NOT_ESCAPED |
 115       ONIG_SYN_WARN_REDUNDANT_NESTED_REPEAT )
 116   , ONIG_OPTION_NONE
 117   ,
 118   {
 119       (OnigCodePoint )'\\'                       /* esc */
 120     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar '.'  */
 121     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anytime '*'  */
 122     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* zero or one time '?' */
 123     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* one or more time '+' */
 124     , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar anytime */
 125   }
 126 };
 127
 128 OnigSyntaxType*  OnigDefaultSyntax = ONIG_SYNTAX_ONIGURUMA;
 129
 130 extern void onig_null_warn(const char* s ARG_UNUSED) { }
 131
 132 #ifdef DEFAULT_WARN_FUNCTION
 133 static OnigWarnFunc onig_warn = (OnigWarnFunc )DEFAULT_WARN_FUNCTION;
 134 #else
 135 static OnigWarnFunc onig_warn = onig_null_warn;
 136 #endif
 137
 138 #ifdef DEFAULT_VERB_WARN_FUNCTION
 139 static OnigWarnFunc onig_verb_warn = (OnigWarnFunc )DEFAULT_VERB_WARN_FUNCTION;
 140 #else
 141 static OnigWarnFunc onig_verb_warn = onig_null_warn;
 142 #endif
 143
 144 extern void onig_set_warn_func(OnigWarnFunc f)
 145 {
 146   onig_warn = f;
 147 }
 148
 149 extern void onig_set_verb_warn_func(OnigWarnFunc f)
 150 {
 151   onig_verb_warn = f;
 152 }
 153
 154 extern void
 155 onig_warning(const char* s)
 156 {
 157   if (onig_warn == onig_null_warn) return ;
 158
 159   (*onig_warn)(s);
 160 }
 161
 162 #define DEFAULT_MAX_CAPTURE_NUM   32767
 163
 164 static int MaxCaptureNum = DEFAULT_MAX_CAPTURE_NUM;
 165
 166 extern int
 167 onig_set_capture_num_limit(int num)
 168 {
 169   if (num < 0) return -1;
 170
 171   MaxCaptureNum = num;
 172   return 0;
 173 }
 174
 175 static unsigned int ParseDepthLimit = DEFAULT_PARSE_DEPTH_LIMIT;
 176
 177 extern unsigned int
 178 onig_get_parse_depth_limit(void)
 179 {
 180   return ParseDepthLimit;
 181 }
 182
 183 extern int
 184 onig_set_parse_depth_limit(unsigned int depth)
 185 {
 186   if (depth == 0)
 187     ParseDepthLimit = DEFAULT_PARSE_DEPTH_LIMIT;
 188   else
 189     ParseDepthLimit = depth;
 190   return 0;
 191 }
 192
 193 static int
 194 positive_int_multiply(int x, int y)
 195 {
 196   if (x == 0 || y == 0) return 0;
 197
 198   if (x < INT_MAX / y)
 199     return x * y;
 200   else
 201     return -1;
 202 }
 203
 204 static void
 205 bbuf_free(BBuf* bbuf)
 206 {
 207   if (IS_NOT_NULL(bbuf)) {
 208     if (IS_NOT_NULL(bbuf->p)) xfree(bbuf->p);
 209     xfree(bbuf);
 210   }
 211 }
 212
 213 static int
 214 bbuf_clone(BBuf** rto, BBuf* from)
 215 {
 216   int r;
 217   BBuf *to;
 218
 219   *rto = to = (BBuf* )xmalloc(sizeof(BBuf));
 220   CHECK_NULL_RETURN_MEMERR(to);
 221   r = BB_INIT(to, from->alloc);
 222   if (r != 0) {
 223     xfree(to->p);
 224     *rto = 0;
 225     return r;
 226   }
 227   to->used = from->used;
 228   xmemcpy(to->p, from->p, from->used);
 229   return 0;
 230 }
 231
 232 static int backref_rel_to_abs(int rel_no, ScanEnv* env)
 233 {
 234   if (rel_no > 0) {
 235     return env->num_mem + rel_no;
 236   }
 237   else {
 238     return env->num_mem + 1 + rel_no;
 239   }
 240 }
 241
 242 #define OPTION_ON(v,f)     ((v) |= (f))
 243 #define OPTION_OFF(v,f)    ((v) &= ~(f))
 244
 245 #define OPTION_NEGATE(v,f,negative)    (negative) ? ((v) &= ~(f)) : ((v) |= (f))
 246
 247 #define MBCODE_START_POS(enc) \
 248   (OnigCodePoint )(ONIGENC_MBC_MINLEN(enc) > 1 ? 0 : 0x80)
 249
 250 #define SET_ALL_MULTI_BYTE_RANGE(enc, pbuf) \
 251   add_code_range_to_buf(pbuf, MBCODE_START_POS(enc), ~((OnigCodePoint )0))
 252
 253 #define ADD_ALL_MULTI_BYTE_RANGE(enc, mbuf) do {\
 254   if (! ONIGENC_IS_SINGLEBYTE(enc)) {\
 255     r = SET_ALL_MULTI_BYTE_RANGE(enc, &(mbuf));\
 256     if (r != 0) return r;\
 257   }\
 258 } while (0)
 259
 260
 261 #define BITSET_IS_EMPTY(bs,empty) do {\
 262   int i;\
 263   empty = 1;\
 264   for (i = 0; i < (int )BITSET_SIZE; i++) {\
 265     if ((bs)[i] != 0) {\
 266       empty = 0; break;\
 267     }\
 268   }\
 269 } while (0)
 270
 271 static void
 272 bitset_set_range(BitSetRef bs, int from, int to)
 273 {
 274   int i;
 275   for (i = from; i <= to && i < SINGLE_BYTE_SIZE; i++) {
 276     BITSET_SET_BIT(bs, i);
 277   }
 278 }
 279
 280 #if 0
 281 static void
 282 bitset_set_all(BitSetRef bs)
 283 {
 284   int i;
 285   for (i = 0; i < BITSET_SIZE; i++) { bs[i] = ~((Bits )0); }
 286 }
 287 #endif
 288
 289 static void
 290 bitset_invert(BitSetRef bs)
 291 {
 292   int i;
 293   for (i = 0; i < (int )BITSET_SIZE; i++) { bs[i] = ~(bs[i]); }
 294 }
 295
 296 static void
 297 bitset_invert_to(BitSetRef from, BitSetRef to)
 298 {
 299   int i;
 300   for (i = 0; i < (int )BITSET_SIZE; i++) { to[i] = ~(from[i]); }
 301 }
 302
 303 static void
 304 bitset_and(BitSetRef dest, BitSetRef bs)
 305 {
 306   int i;
 307   for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] &= bs[i]; }
 308 }
 309
 310 static void
 311 bitset_or(BitSetRef dest, BitSetRef bs)
 312 {
 313   int i;
 314   for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] |= bs[i]; }
 315 }
 316
 317 static void
 318 bitset_copy(BitSetRef dest, BitSetRef bs)
 319 {
 320   int i;
 321   for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] = bs[i]; }
 322 }
 323
 324 extern int
 325 onig_strncmp(const UChar* s1, const UChar* s2, int n)
 326 {
 327   int x;
 328
 329   while (n-- > 0) {
 330     x = *s2++ - *s1++;
 331     if (x) return x;
 332   }
 333   return 0;
 334 }
 335
 336 extern void
 337 onig_strcpy(UChar* dest, const UChar* src, const UChar* end)
 338 {
 339   int len = (int )(end - src);
 340   if (len > 0) {
 341     xmemcpy(dest, src, len);
 342     dest[len] = (UChar )0;
 343   }
 344 }
 345
 346 static UChar*
 347 strdup_with_null(OnigEncoding enc, UChar* s, UChar* end)
 348 {
 349   int slen, term_len, i;
 350   UChar *r;
 351
 352   slen = (int )(end - s);
 353   term_len = ONIGENC_MBC_MINLEN(enc);
 354
 355   r = (UChar* )xmalloc(slen + term_len);
 356   CHECK_NULL_RETURN(r);
 357   xmemcpy(r, s, slen);
 358
 359   for (i = 0; i < term_len; i++)
 360     r[slen + i] = (UChar )0;
 361
 362   return r;
 363 }
 364
 365 static int
 366 save_entry(ScanEnv* env, enum SaveType type, int* id)
 367 {
 368   int nid = env->save_num;
 369
 370 #if 0
 371   if (IS_NULL(env->saves)) {
 372     int n = 10;
 373     env->saves = (SaveItem* )xmalloc(sizeof(SaveItem) * n);
 374     CHECK_NULL_RETURN_MEMERR(env->saves);
 375     env->save_alloc_num = n;
 376   }
 377   else if (env->save_alloc_num <= nid) {
 378     int n = env->save_alloc_num * 2;
 379     SaveItem* p = (SaveItem* )xrealloc(env->saves, sizeof(SaveItem) * n);
 380     CHECK_NULL_RETURN_MEMERR(p);
 381     env->saves = p;
 382     env->save_alloc_num = n;
 383   }
 384
 385   env->saves[nid].type = type;
 386 #endif
 387
 388   env->save_num++;
 389   *id = nid;
 390   return 0;
 391 }
 392
 393 /* scan pattern methods */
 394 #define PEND_VALUE   0
 395
 396 #define PFETCH_READY  UChar* pfetch_prev
 397 #define PEND         (p < end ?  0 : 1)
 398 #define PUNFETCH     p = pfetch_prev
 399 #define PINC       do { \
 400   pfetch_prev = p; \
 401   p += ONIGENC_MBC_ENC_LEN(enc, p); \
 402 } while (0)
 403 #define PFETCH(c)  do { \
 404   c = ONIGENC_MBC_TO_CODE(enc, p, end); \
 405   pfetch_prev = p; \
 406   p += ONIGENC_MBC_ENC_LEN(enc, p); \
 407 } while (0)
 408
 409 #define PINC_S     do { \
 410   p += ONIGENC_MBC_ENC_LEN(enc, p); \
 411 } while (0)
 412 #define PFETCH_S(c) do { \
 413   c = ONIGENC_MBC_TO_CODE(enc, p, end); \
 414   p += ONIGENC_MBC_ENC_LEN(enc, p); \
 415 } while (0)
 416
 417 #define PPEEK        (p < end ? ONIGENC_MBC_TO_CODE(enc, p, end) : PEND_VALUE)
 418 #define PPEEK_IS(c)  (PPEEK == (OnigCodePoint )c)
 419
 420 static UChar*
 421 strcat_capa(UChar* dest, UChar* dest_end, const UChar* src, const UChar* src_end,
 422             int capa)
 423 {
 424   UChar* r;
 425
 426   if (dest)
 427     r = (UChar* )xrealloc(dest, capa + 1);
 428   else
 429     r = (UChar* )xmalloc(capa + 1);
 430
 431   CHECK_NULL_RETURN(r);
 432   onig_strcpy(r + (dest_end - dest), src, src_end);
 433   return r;
 434 }
 435
 436 /* dest on static area */
 437 static UChar*
 438 strcat_capa_from_static(UChar* dest, UChar* dest_end,
 439                         const UChar* src, const UChar* src_end, int capa)
 440 {
 441   UChar* r;
 442
 443   r = (UChar* )xmalloc(capa + 1);
 444   CHECK_NULL_RETURN(r);
 445   onig_strcpy(r, dest, dest_end);
 446   onig_strcpy(r + (dest_end - dest), src, src_end);
 447   return r;
 448 }
 449
 450
 451 #ifdef USE_ST_LIBRARY
 452
 453 typedef struct {
 454   UChar* s;
 455   UChar* end;
 456 } st_str_end_key;
 457
 458 static int
 459 str_end_cmp(st_str_end_key* x, st_str_end_key* y)
 460 {
 461   UChar *p, *q;
 462   int c;
 463
 464   if ((x->end - x->s) != (y->end - y->s))
 465     return 1;
 466
 467   p = x->s;
 468   q = y->s;
 469   while (p < x->end) {
 470     c = (int )*p - (int )*q;
 471     if (c != 0) return c;
 472
 473     p++; q++;
 474   }
 475
 476   return 0;
 477 }
 478
 479 static int
 480 str_end_hash(st_str_end_key* x)
 481 {
 482   UChar *p;
 483   int val = 0;
 484
 485   p = x->s;
 486   while (p < x->end) {
 487     val = val * 997 + (int )*p++;
 488   }
 489
 490   return val + (val >> 5);
 491 }
 492
 493 extern hash_table_type*
 494 onig_st_init_strend_table_with_size(int size)
 495 {
 496   static struct st_hash_type hashType = {
 497     str_end_cmp,
 498     str_end_hash,
 499   };
 500
 501   return (hash_table_type* )
 502            onig_st_init_table_with_size(&hashType, size);
 503 }
 504
 505 extern int
 506 onig_st_lookup_strend(hash_table_type* table, const UChar* str_key,
 507                       const UChar* end_key, hash_data_type *value)
 508 {
 509   st_str_end_key key;
 510
 511   key.s   = (UChar* )str_key;
 512   key.end = (UChar* )end_key;
 513
 514   return onig_st_lookup(table, (st_data_t )(&key), value);
 515 }
 516
 517 extern int
 518 onig_st_insert_strend(hash_table_type* table, const UChar* str_key,
 519                       const UChar* end_key, hash_data_type value)
 520 {
 521   st_str_end_key* key;
 522   int result;
 523
 524   key = (st_str_end_key* )xmalloc(sizeof(st_str_end_key));
 525   CHECK_NULL_RETURN_MEMERR(key);
 526
 527   key->s   = (UChar* )str_key;
 528   key->end = (UChar* )end_key;
 529   result = onig_st_insert(table, (st_data_t )key, value);
 530   if (result) {
 531     xfree(key);
 532   }
 533   return result;
 534 }
 535
 536 #endif /* USE_ST_LIBRARY */
 537
 538
 539 #define INIT_NAME_BACKREFS_ALLOC_NUM   8
 540
 541 typedef struct {
 542   UChar* name;
 543   int    name_len;   /* byte length */
 544   int    back_num;   /* number of backrefs */
 545   int    back_alloc;
 546   int    back_ref1;
 547   int*   back_refs;
 548 } NameEntry;
 549
 550 #ifdef USE_ST_LIBRARY
 551
 552 typedef st_table  NameTable;
 553 typedef st_data_t HashDataType;   /* 1.6 st.h doesn't define st_data_t type */
 554
 555 #define NAMEBUF_SIZE    24
 556 #define NAMEBUF_SIZE_1  25
 557
 558 #ifdef ONIG_DEBUG
 559 static int
 560 i_print_name_entry(UChar* key, NameEntry* e, void* arg)
 561 {
 562   int i;
 563   FILE* fp = (FILE* )arg;
 564
 565   fprintf(fp, "%s: ", e->name);
 566   if (e->back_num == 0)
 567     fputs("-", fp);
 568   else if (e->back_num == 1)
 569     fprintf(fp, "%d", e->back_ref1);
 570   else {
 571     for (i = 0; i < e->back_num; i++) {
 572       if (i > 0) fprintf(fp, ", ");
 573       fprintf(fp, "%d", e->back_refs[i]);
 574     }
 575   }
 576   fputs("\n", fp);
 577   return ST_CONTINUE;
 578 }
 579
 580 extern int
 581 onig_print_names(FILE* fp, regex_t* reg)
 582 {
 583   NameTable* t = (NameTable* )reg->name_table;
 584
 585   if (IS_NOT_NULL(t)) {
 586     fprintf(fp, "name table\n");
 587     onig_st_foreach(t, i_print_name_entry, (HashDataType )fp);
 588     fputs("\n", fp);
 589   }
 590   return 0;
 591 }
 592 #endif /* ONIG_DEBUG */
 593
 594 static int
 595 i_free_name_entry(UChar* key, NameEntry* e, void* arg ARG_UNUSED)
 596 {
 597   xfree(e->name);
 598   if (IS_NOT_NULL(e->back_refs)) xfree(e->back_refs);
 599   xfree(key);
 600   xfree(e);
 601   return ST_DELETE;
 602 }
 603
 604 static int
 605 names_clear(regex_t* reg)
 606 {
 607   NameTable* t = (NameTable* )reg->name_table;
 608
 609   if (IS_NOT_NULL(t)) {
 610     onig_st_foreach(t, i_free_name_entry, 0);
 611   }
 612   return 0;
 613 }
 614
 615 extern int
 616 onig_names_free(regex_t* reg)
 617 {
 618   int r;
 619   NameTable* t;
 620
 621   r = names_clear(reg);
 622   if (r != 0) return r;
 623
 624   t = (NameTable* )reg->name_table;
 625   if (IS_NOT_NULL(t)) onig_st_free_table(t);
 626   reg->name_table = (void* )NULL;
 627   return 0;
 628 }
 629
 630 static NameEntry*
 631 name_find(regex_t* reg, const UChar* name, const UChar* name_end)
 632 {
 633   NameEntry* e;
 634   NameTable* t = (NameTable* )reg->name_table;
 635
 636   e = (NameEntry* )NULL;
 637   if (IS_NOT_NULL(t)) {
 638     onig_st_lookup_strend(t, name, name_end, (HashDataType* )((void* )(&e)));
 639   }
 640   return e;
 641 }
 642
 643 typedef struct {
 644   int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*);
 645   regex_t* reg;
 646   void* arg;
 647   int ret;
 648   OnigEncoding enc;
 649 } INamesArg;
 650
 651 static int
 652 i_names(UChar* key ARG_UNUSED, NameEntry* e, INamesArg* arg)
 653 {
 654   int r = (*(arg->func))(e->name,
 655                          e->name + e->name_len,
 656                          e->back_num,
 657                          (e->back_num > 1 ? e->back_refs : &(e->back_ref1)),
 658                          arg->reg, arg->arg);
 659   if (r != 0) {
 660     arg->ret = r;
 661     return ST_STOP;
 662   }
 663   return ST_CONTINUE;
 664 }
 665
 666 extern int
 667 onig_foreach_name(regex_t* reg,
 668   int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*), void* arg)
 669 {
 670   INamesArg narg;
 671   NameTable* t = (NameTable* )reg->name_table;
 672
 673   narg.ret = 0;
 674   if (IS_NOT_NULL(t)) {
 675     narg.func = func;
 676     narg.reg  = reg;
 677     narg.arg  = arg;
 678     narg.enc  = reg->enc; /* should be pattern encoding. */
 679     onig_st_foreach(t, i_names, (HashDataType )&narg);
 680   }
 681   return narg.ret;
 682 }
 683
 684 static int
 685 i_renumber_name(UChar* key ARG_UNUSED, NameEntry* e, GroupNumRemap* map)
 686 {
 687   int i;
 688
 689   if (e->back_num > 1) {
 690     for (i = 0; i < e->back_num; i++) {
 691       e->back_refs[i] = map[e->back_refs[i]].new_val;
 692     }
 693   }
 694   else if (e->back_num == 1) {
 695     e->back_ref1 = map[e->back_ref1].new_val;
 696   }
 697
 698   return ST_CONTINUE;
 699 }
 700
 701 extern int
 702 onig_renumber_name_table(regex_t* reg, GroupNumRemap* map)
 703 {
 704   NameTable* t = (NameTable* )reg->name_table;
 705
 706   if (IS_NOT_NULL(t)) {
 707     onig_st_foreach(t, i_renumber_name, (HashDataType )map);
 708   }
 709   return 0;
 710 }
 711
 712
 713 extern int
 714 onig_number_of_names(regex_t* reg)
 715 {
 716   NameTable* t = (NameTable* )reg->name_table;
 717
 718   if (IS_NOT_NULL(t))
 719     return t->num_entries;
 720   else
 721     return 0;
 722 }
 723
 724 #else  /* USE_ST_LIBRARY */
 725
 726 #define INIT_NAMES_ALLOC_NUM    8
 727
 728 typedef struct {
 729   NameEntry* e;
 730   int        num;
 731   int        alloc;
 732 } NameTable;
 733
 734 #ifdef ONIG_DEBUG
 735 extern int
 736 onig_print_names(FILE* fp, regex_t* reg)
 737 {
 738   int i, j;
 739   NameEntry* e;
 740   NameTable* t = (NameTable* )reg->name_table;
 741
 742   if (IS_NOT_NULL(t) && t->num > 0) {
 743     fprintf(fp, "name table\n");
 744     for (i = 0; i < t->num; i++) {
 745       e = &(t->e[i]);
 746       fprintf(fp, "%s: ", e->name);
 747       if (e->back_num == 0) {
 748         fputs("-", fp);
 749       }
 750       else if (e->back_num == 1) {
 751         fprintf(fp, "%d", e->back_ref1);
 752       }
 753       else {
 754         for (j = 0; j < e->back_num; j++) {
 755           if (j > 0) fprintf(fp, ", ");
 756           fprintf(fp, "%d", e->back_refs[j]);
 757         }
 758       }
 759       fputs("\n", fp);
 760     }
 761     fputs("\n", fp);
 762   }
 763   return 0;
 764 }
 765 #endif
 766
 767 static int
 768 names_clear(regex_t* reg)
 769 {
 770   int i;
 771   NameEntry* e;
 772   NameTable* t = (NameTable* )reg->name_table;
 773
 774   if (IS_NOT_NULL(t)) {
 775     for (i = 0; i < t->num; i++) {
 776       e = &(t->e[i]);
 777       if (IS_NOT_NULL(e->name)) {
 778         xfree(e->name);
 779         e->name       = NULL;
 780         e->name_len   = 0;
 781         e->back_num   = 0;
 782         e->back_alloc = 0;
 783         if (IS_NOT_NULL(e->back_refs)) xfree(e->back_refs);
 784         e->back_refs = (int* )NULL;
 785       }
 786     }
 787     if (IS_NOT_NULL(t->e)) {
 788       xfree(t->e);
 789       t->e = NULL;
 790     }
 791     t->num = 0;
 792   }
 793   return 0;
 794 }
 795
 796 extern int
 797 onig_names_free(regex_t* reg)
 798 {
 799   int r;
 800   NameTable* t;
 801
 802   r = names_clear(reg);
 803   if (r != 0) return r;
 804
 805   t = (NameTable* )reg->name_table;
 806   if (IS_NOT_NULL(t)) xfree(t);
 807   reg->name_table = NULL;
 808   return 0;
 809 }
 810
 811 static NameEntry*
 812 name_find(regex_t* reg, UChar* name, UChar* name_end)
 813 {
 814   int i, len;
 815   NameEntry* e;
 816   NameTable* t = (NameTable* )reg->name_table;
 817
 818   if (IS_NOT_NULL(t)) {
 819     len = name_end - name;
 820     for (i = 0; i < t->num; i++) {
 821       e = &(t->e[i]);
 822       if (len == e->name_len && onig_strncmp(name, e->name, len) == 0)
 823         return e;
 824     }
 825   }
 826   return (NameEntry* )NULL;
 827 }
 828
 829 extern int
 830 onig_foreach_name(regex_t* reg,
 831   int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*), void* arg)
 832 {
 833   int i, r;
 834   NameEntry* e;
 835   NameTable* t = (NameTable* )reg->name_table;
 836
 837   if (IS_NOT_NULL(t)) {
 838     for (i = 0; i < t->num; i++) {
 839       e = &(t->e[i]);
 840       r = (*func)(e->name, e->name + e->name_len, e->back_num,
 841                   (e->back_num > 1 ? e->back_refs : &(e->back_ref1)),
 842                   reg, arg);
 843       if (r != 0) return r;
 844     }
 845   }
 846   return 0;
 847 }
 848
 849 extern int
 850 onig_number_of_names(regex_t* reg)
 851 {
 852   NameTable* t = (NameTable* )reg->name_table;
 853
 854   if (IS_NOT_NULL(t))
 855     return t->num;
 856   else
 857     return 0;
 858 }
 859
 860 #endif /* else USE_ST_LIBRARY */
 861
 862 static int
 863 name_add(regex_t* reg, UChar* name, UChar* name_end, int backref, ScanEnv* env)
 864 {
 865   int r;
 866   int alloc;
 867   NameEntry* e;
 868   NameTable* t = (NameTable* )reg->name_table;
 869
 870   if (name_end - name <= 0)
 871     return ONIGERR_EMPTY_GROUP_NAME;
 872
 873   e = name_find(reg, name, name_end);
 874   if (IS_NULL(e)) {
 875 #ifdef USE_ST_LIBRARY
 876     if (IS_NULL(t)) {
 877       t = onig_st_init_strend_table_with_size(5);
 878       reg->name_table = (void* )t;
 879     }
 880     e = (NameEntry* )xmalloc(sizeof(NameEntry));
 881     CHECK_NULL_RETURN_MEMERR(e);
 882
 883     e->name = strdup_with_null(reg->enc, name, name_end);
 884     if (IS_NULL(e->name)) {
 885       xfree(e);  return ONIGERR_MEMORY;
 886     }
 887     r = onig_st_insert_strend(t, e->name, (e->name + (name_end - name)),
 888                               (HashDataType )e);
 889     if (r < 0) return r;
 890
 891     e->name_len   = (int )(name_end - name);
 892     e->back_num   = 0;
 893     e->back_alloc = 0;
 894     e->back_refs  = (int* )NULL;
 895
 896 #else
 897
 898     if (IS_NULL(t)) {
 899       alloc = INIT_NAMES_ALLOC_NUM;
 900       t = (NameTable* )xmalloc(sizeof(NameTable));
 901       CHECK_NULL_RETURN_MEMERR(t);
 902       t->e     = NULL;
 903       t->alloc = 0;
 904       t->num   = 0;
 905
 906       t->e = (NameEntry* )xmalloc(sizeof(NameEntry) * alloc);
 907       if (IS_NULL(t->e)) {
 908         xfree(t);
 909         return ONIGERR_MEMORY;
 910       }
 911       t->alloc = alloc;
 912       reg->name_table = t;
 913       goto clear;
 914     }
 915     else if (t->num == t->alloc) {
 916       int i;
 917
 918       alloc = t->alloc * 2;
 919       t->e = (NameEntry* )xrealloc(t->e, sizeof(NameEntry) * alloc);
 920       CHECK_NULL_RETURN_MEMERR(t->e);
 921       t->alloc = alloc;
 922
 923     clear:
 924       for (i = t->num; i < t->alloc; i++) {
 925         t->e[i].name       = NULL;
 926         t->e[i].name_len   = 0;
 927         t->e[i].back_num   = 0;
 928         t->e[i].back_alloc = 0;
 929         t->e[i].back_refs  = (int* )NULL;
 930       }
 931     }
 932     e = &(t->e[t->num]);
 933     t->num++;
 934     e->name = strdup_with_null(reg->enc, name, name_end);
 935     if (IS_NULL(e->name)) return ONIGERR_MEMORY;
 936     e->name_len = name_end - name;
 937 #endif
 938   }
 939
 940   if (e->back_num >= 1 &&
 941       ! IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME)) {
 942     onig_scan_env_set_error_string(env, ONIGERR_MULTIPLEX_DEFINED_NAME,
 943                                    name, name_end);
 944     return ONIGERR_MULTIPLEX_DEFINED_NAME;
 945   }
 946
 947   e->back_num++;
 948   if (e->back_num == 1) {
 949     e->back_ref1 = backref;
 950   }
 951   else {
 952     if (e->back_num == 2) {
 953       alloc = INIT_NAME_BACKREFS_ALLOC_NUM;
 954       e->back_refs = (int* )xmalloc(sizeof(int) * alloc);
 955       CHECK_NULL_RETURN_MEMERR(e->back_refs);
 956       e->back_alloc = alloc;
 957       e->back_refs[0] = e->back_ref1;
 958       e->back_refs[1] = backref;
 959     }
 960     else {
 961       if (e->back_num > e->back_alloc) {
 962         alloc = e->back_alloc * 2;
 963         e->back_refs = (int* )xrealloc(e->back_refs, sizeof(int) * alloc);
 964         CHECK_NULL_RETURN_MEMERR(e->back_refs);
 965         e->back_alloc = alloc;
 966       }
 967       e->back_refs[e->back_num - 1] = backref;
 968     }
 969   }
 970
 971   return 0;
 972 }
 973
 974 extern int
 975 onig_name_to_group_numbers(regex_t* reg, const UChar* name,
 976                            const UChar* name_end, int** nums)
 977 {
 978   NameEntry* e = name_find(reg, name, name_end);
 979
 980   if (IS_NULL(e)) return ONIGERR_UNDEFINED_NAME_REFERENCE;
 981
 982   switch (e->back_num) {
 983   case 0:
 984     break;
 985   case 1:
 986     *nums = &(e->back_ref1);
 987     break;
 988   default:
 989     *nums = e->back_refs;
 990     break;
 991   }
 992   return e->back_num;
 993 }
 994
 995 extern int
 996 onig_name_to_backref_number(regex_t* reg, const UChar* name,
 997                             const UChar* name_end, OnigRegion *region)
 998 {
 999   int i, n, *nums;
1000
1001   n = onig_name_to_group_numbers(reg, name, name_end, &nums);
1002   if (n < 0)
1003     return n;
1004   else if (n == 0)
1005     return ONIGERR_PARSER_BUG;
1006   else if (n == 1)
1007     return nums[0];
1008   else {
1009     if (IS_NOT_NULL(region)) {
1010       for (i = n - 1; i >= 0; i--) {
1011         if (region->beg[nums[i]] != ONIG_REGION_NOTPOS)
1012           return nums[i];
1013       }
1014     }
1015     return nums[n - 1];
1016   }
1017 }
1018
1019 extern int
1020 onig_noname_group_capture_is_active(regex_t* reg)
1021 {
1022   if (ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_DONT_CAPTURE_GROUP))
1023     return 0;
1024
1025   if (onig_number_of_names(reg) > 0 &&
1026       IS_SYNTAX_BV(reg->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
1027       !ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_CAPTURE_GROUP)) {
1028     return 0;
1029   }
1030
1031   return 1;
1032 }
1033
1034
1035 #define INIT_SCANENV_MEMENV_ALLOC_SIZE   16
1036
1037 static void
1038 scan_env_clear(ScanEnv* env)
1039 {
1040   MEM_STATUS_CLEAR(env->capture_history);
1041   MEM_STATUS_CLEAR(env->bt_mem_start);
1042   MEM_STATUS_CLEAR(env->bt_mem_end);
1043   MEM_STATUS_CLEAR(env->backrefed_mem);
1044   env->error      = (UChar* )NULL;
1045   env->error_end  = (UChar* )NULL;
1046   env->num_call   = 0;
1047
1048 #ifdef USE_CALL
1049   env->unset_addr_list = NULL;
1050   env->has_call_zero   = 0;
1051 #endif
1052
1053   env->num_mem    = 0;
1054   env->num_named  = 0;
1055   env->mem_alloc  = 0;
1056   env->mem_env_dynamic = (MemEnv* )NULL;
1057
1058   xmemset(env->mem_env_static, 0, sizeof(env->mem_env_static));
1059
1060   env->parse_depth         = 0;
1061   env->keep_num            = 0;
1062   env->save_num            = 0;
1063   env->save_alloc_num      = 0;
1064   env->saves               = 0;
1065 }
1066
1067 static int
1068 scan_env_add_mem_entry(ScanEnv* env)
1069 {
1070   int i, need, alloc;
1071   MemEnv* p;
1072
1073   need = env->num_mem + 1;
1074   if (need > MaxCaptureNum && MaxCaptureNum != 0)
1075     return ONIGERR_TOO_MANY_CAPTURES;
1076
1077   if (need >= SCANENV_MEMENV_SIZE) {
1078     if (env->mem_alloc <= need) {
1079       if (IS_NULL(env->mem_env_dynamic)) {
1080         alloc = INIT_SCANENV_MEMENV_ALLOC_SIZE;
1081         p = (MemEnv* )xmalloc(sizeof(MemEnv) * alloc);
1082         CHECK_NULL_RETURN_MEMERR(p);
1083         xmemcpy(p, env->mem_env_static, sizeof(env->mem_env_static));
1084       }
1085       else {
1086         alloc = env->mem_alloc * 2;
1087         p = (MemEnv* )xrealloc(env->mem_env_dynamic, sizeof(MemEnv) * alloc);
1088         CHECK_NULL_RETURN_MEMERR(p);
1089       }
1090
1091       for (i = env->num_mem + 1; i < alloc; i++) {
1092         p[i].node = NULL_NODE;
1093 #if 0
1094         p[i].in   = 0;
1095         p[i].recursion = 0;
1096 #endif
1097       }
1098
1099       env->mem_env_dynamic = p;
1100       env->mem_alloc = alloc;
1101     }
1102   }
1103
1104   env->num_mem++;
1105   return env->num_mem;
1106 }
1107
1108 static int
1109 scan_env_set_mem_node(ScanEnv* env, int num, Node* node)
1110 {
1111   if (env->num_mem >= num)
1112     SCANENV_MEMENV(env)[num].node = node;
1113   else
1114     return ONIGERR_PARSER_BUG;
1115   return 0;
1116 }
1117
1118 extern void
1119 onig_node_free(Node* node)
1120 {
1121  start:
1122   if (IS_NULL(node)) return ;
1123
1124 #ifdef DEBUG_NODE_FREE
1125   fprintf(stderr, "onig_node_free: %p\n", node);
1126 #endif
1127
1128   switch (NODE_TYPE(node)) {
1129   case NODE_STRING:
1130     if (STR_(node)->capa != 0 &&
1131         IS_NOT_NULL(STR_(node)->s) && STR_(node)->s != STR_(node)->buf) {
1132       xfree(STR_(node)->s);
1133     }
1134     break;
1135
1136   case NODE_LIST:
1137   case NODE_ALT:
1138     onig_node_free(NODE_CAR(node));
1139     {
1140       Node* next_node = NODE_CDR(node);
1141
1142       xfree(node);
1143       node = next_node;
1144       goto start;
1145     }
1146     break;
1147
1148   case NODE_CCLASS:
1149     {
1150       CClassNode* cc = CCLASS_(node);
1151
1152       if (cc->mbuf)
1153         bbuf_free(cc->mbuf);
1154     }
1155     break;
1156
1157   case NODE_BACKREF:
1158     if (IS_NOT_NULL(BACKREF_(node)->back_dynamic))
1159       xfree(BACKREF_(node)->back_dynamic);
1160     break;
1161
1162   case NODE_ENCLOSURE:
1163     if (NODE_BODY(node))
1164       onig_node_free(NODE_BODY(node));
1165
1166     {
1167       EnclosureNode* en = ENCLOSURE_(node);
1168       if (en->type == ENCLOSURE_IF_ELSE) {
1169         onig_node_free(en->te.Then);
1170         onig_node_free(en->te.Else);
1171       }
1172     }
1173     break;
1174
1175   case NODE_QUANT:
1176   case NODE_ANCHOR:
1177     if (NODE_BODY(node))
1178       onig_node_free(NODE_BODY(node));
1179     break;
1180
1181   case NODE_CTYPE:
1182   case NODE_CALL:
1183   case NODE_GIMMICK:
1184     break;
1185   }
1186
1187   xfree(node);
1188 }
1189
1190 static void
1191 cons_node_free_alone(Node* node)
1192 {
1193   NODE_CAR(node) = 0;
1194   NODE_CDR(node) = 0;
1195   onig_node_free(node);
1196 }
1197
1198 extern void
1199 list_node_free_not_car(Node* node)
1200 {
1201   Node* next_node;
1202
1203  start:
1204   if (IS_NULL(node)) return;
1205
1206   next_node = NODE_CDR(node);
1207   xfree(node);
1208   node = next_node;
1209   goto start;
1210 }
1211
1212 static Node*
1213 node_new(void)
1214 {
1215   Node* node;
1216
1217   node = (Node* )xmalloc(sizeof(Node));
1218   xmemset(node, 0, sizeof(*node));
1219
1220 #ifdef DEBUG_NODE_FREE
1221   fprintf(stderr, "node_new: %p\n", node);
1222 #endif
1223   return node;
1224 }
1225
1226
1227 static void
1228 initialize_cclass(CClassNode* cc)
1229 {
1230   BITSET_CLEAR(cc->bs);
1231   cc->flags = 0;
1232   cc->mbuf  = NULL;
1233 }
1234
1235 static Node*
1236 node_new_cclass(void)
1237 {
1238   Node* node = node_new();
1239   CHECK_NULL_RETURN(node);
1240
1241   NODE_SET_TYPE(node, NODE_CCLASS);
1242   initialize_cclass(CCLASS_(node));
1243   return node;
1244 }
1245
1246 static Node*
1247 node_new_ctype(int type, int not, OnigOptionType options)
1248 {
1249   Node* node = node_new();
1250   CHECK_NULL_RETURN(node);
1251
1252   NODE_SET_TYPE(node, NODE_CTYPE);
1253   CTYPE_(node)->ctype   = type;
1254   CTYPE_(node)->not     = not;
1255   CTYPE_(node)->options = options;
1256   CTYPE_(node)->ascii_mode = IS_ASCII_MODE_CTYPE_OPTION(type, options);
1257   return node;
1258 }
1259
1260 static Node*
1261 node_new_anychar(void)
1262 {
1263   Node* node = node_new_ctype(CTYPE_ANYCHAR, 0, ONIG_OPTION_NONE);
1264   return node;
1265 }
1266
1267 static Node*
1268 node_new_anychar_with_fixed_option(OnigOptionType option)
1269 {
1270   CtypeNode* ct;
1271   Node* node;
1272
1273   node = node_new_anychar();
1274   ct = CTYPE_(node);
1275   ct->options = option;
1276   NODE_STATUS_ADD(node, NST_FIXED_OPTION);
1277   return node;
1278 }
1279
1280 static int
1281 node_new_no_newline(Node** node, ScanEnv* env)
1282 {
1283   Node* n;
1284
1285   n = node_new_anychar_with_fixed_option(ONIG_OPTION_NONE);
1286   CHECK_NULL_RETURN_MEMERR(n);
1287   *node = n;
1288   return 0;
1289 }
1290
1291 static int
1292 node_new_true_anychar(Node** node, ScanEnv* env)
1293 {
1294   Node* n;
1295
1296   n = node_new_anychar_with_fixed_option(ONIG_OPTION_MULTILINE);
1297   CHECK_NULL_RETURN_MEMERR(n);
1298   *node = n;
1299   return 0;
1300 }
1301
1302 static Node*
1303 node_new_list(Node* left, Node* right)
1304 {
1305   Node* node = node_new();
1306   CHECK_NULL_RETURN(node);
1307
1308   NODE_SET_TYPE(node, NODE_LIST);
1309   NODE_CAR(node)  = left;
1310   NODE_CDR(node) = right;
1311   return node;
1312 }
1313
1314 extern Node*
1315 onig_node_new_list(Node* left, Node* right)
1316 {
1317   return node_new_list(left, right);
1318 }
1319
1320 extern Node*
1321 onig_node_list_add(Node* list, Node* x)
1322 {
1323   Node *n;
1324
1325   n = onig_node_new_list(x, NULL);
1326   if (IS_NULL(n)) return NULL_NODE;
1327
1328   if (IS_NOT_NULL(list)) {
1329     while (IS_NOT_NULL(NODE_CDR(list)))
1330       list = NODE_CDR(list);
1331
1332     NODE_CDR(list) = n;
1333   }
1334
1335   return n;
1336 }
1337
1338 extern Node*
1339 onig_node_new_alt(Node* left, Node* right)
1340 {
1341   Node* node = node_new();
1342   CHECK_NULL_RETURN(node);
1343
1344   NODE_SET_TYPE(node, NODE_ALT);
1345   NODE_CAR(node)  = left;
1346   NODE_CDR(node) = right;
1347   return node;
1348 }
1349
1350 static Node*
1351 make_list_or_alt(NodeType type, int n, Node* ns[])
1352 {
1353   Node* r;
1354
1355   if (n <= 0) return NULL_NODE;
1356
1357   if (n == 1) {
1358     r = node_new();
1359     CHECK_NULL_RETURN(r);
1360     NODE_SET_TYPE(r, type);
1361     NODE_CAR(r) = ns[0];
1362     NODE_CDR(r) = NULL_NODE;
1363   }
1364   else {
1365     Node* right;
1366
1367     r = node_new();
1368     CHECK_NULL_RETURN(r);
1369
1370     right = make_list_or_alt(type, n - 1, ns + 1);
1371     if (IS_NULL(right)) {
1372       onig_node_free(r);
1373       return NULL_NODE;
1374     }
1375
1376     NODE_SET_TYPE(r, type);
1377     NODE_CAR(r) = ns[0];
1378     NODE_CDR(r) = right;
1379   }
1380
1381   return r;
1382 }
1383
1384 static Node*
1385 make_list(int n, Node* ns[])
1386 {
1387   return make_list_or_alt(NODE_LIST, n, ns);
1388 }
1389
1390 static Node*
1391 make_alt(int n, Node* ns[])
1392 {
1393   return make_list_or_alt(NODE_ALT, n, ns);
1394 }
1395
1396 extern Node*
1397 onig_node_new_anchor(int type, int ascii_mode)
1398 {
1399   Node* node = node_new();
1400   CHECK_NULL_RETURN(node);
1401
1402   NODE_SET_TYPE(node, NODE_ANCHOR);
1403   ANCHOR_(node)->type       = type;
1404   ANCHOR_(node)->char_len   = -1;
1405   ANCHOR_(node)->ascii_mode = ascii_mode;
1406   return node;
1407 }
1408
1409 static Node*
1410 node_new_backref(int back_num, int* backrefs, int by_name,
1411 #ifdef USE_BACKREF_WITH_LEVEL
1412                  int exist_level, int nest_level,
1413 #endif
1414                  ScanEnv* env)
1415 {
1416   int i;
1417   Node* node = node_new();
1418
1419   CHECK_NULL_RETURN(node);
1420
1421   NODE_SET_TYPE(node, NODE_BACKREF);
1422   BACKREF_(node)->back_num = back_num;
1423   BACKREF_(node)->back_dynamic = (int* )NULL;
1424   if (by_name != 0)
1425     NODE_STATUS_ADD(node, NST_BY_NAME);
1426
1427 #ifdef USE_BACKREF_WITH_LEVEL
1428   if (exist_level != 0) {
1429     NODE_STATUS_ADD(node, NST_NEST_LEVEL);
1430     BACKREF_(node)->nest_level  = nest_level;
1431   }
1432 #endif
1433
1434   for (i = 0; i < back_num; i++) {
1435     if (backrefs[i] <= env->num_mem &&
1436         IS_NULL(SCANENV_MEMENV(env)[backrefs[i]].node)) {
1437       NODE_STATUS_ADD(node, NST_RECURSION);   /* /...(\1).../ */
1438       break;
1439     }
1440   }
1441
1442   if (back_num <= NODE_BACKREFS_SIZE) {
1443     for (i = 0; i < back_num; i++)
1444       BACKREF_(node)->back_static[i] = backrefs[i];
1445   }
1446   else {
1447     int* p = (int* )xmalloc(sizeof(int) * back_num);
1448     if (IS_NULL(p)) {
1449       onig_node_free(node);
1450       return NULL;
1451     }
1452     BACKREF_(node)->back_dynamic = p;
1453     for (i = 0; i < back_num; i++)
1454       p[i] = backrefs[i];
1455   }
1456   return node;
1457 }
1458
1459 static Node*
1460 node_new_backref_checker(int back_num, int* backrefs, int by_name,
1461 #ifdef USE_BACKREF_WITH_LEVEL
1462                          int exist_level, int nest_level,
1463 #endif
1464                          ScanEnv* env)
1465 {
1466   Node* node;
1467
1468   node = node_new_backref(back_num, backrefs, by_name,
1469 #ifdef USE_BACKREF_WITH_LEVEL
1470                           exist_level, nest_level,
1471 #endif
1472                           env);
1473   CHECK_NULL_RETURN(node);
1474
1475   NODE_STATUS_ADD(node, NST_CHECKER);
1476   return node;
1477 }
1478
1479 #ifdef USE_CALL
1480 static Node*
1481 node_new_call(UChar* name, UChar* name_end, int gnum, int by_number)
1482 {
1483   Node* node = node_new();
1484   CHECK_NULL_RETURN(node);
1485
1486   NODE_SET_TYPE(node, NODE_CALL);
1487   CALL_(node)->by_number   = by_number;
1488   CALL_(node)->name        = name;
1489   CALL_(node)->name_end    = name_end;
1490   CALL_(node)->group_num   = gnum;
1491   CALL_(node)->entry_count = 1;
1492   return node;
1493 }
1494 #endif
1495
1496 static Node*
1497 node_new_quantifier(int lower, int upper, int by_number)
1498 {
1499   Node* node = node_new();
1500   CHECK_NULL_RETURN(node);
1501
1502   NODE_SET_TYPE(node, NODE_QUANT);
1503   QUANT_(node)->lower  = lower;
1504   QUANT_(node)->upper  = upper;
1505   QUANT_(node)->greedy = 1;
1506   QUANT_(node)->body_empty_info = QUANT_BODY_IS_NOT_EMPTY;
1507   QUANT_(node)->head_exact      = NULL_NODE;
1508   QUANT_(node)->next_head_exact = NULL_NODE;
1509   QUANT_(node)->is_refered      = 0;
1510   if (by_number != 0)
1511     NODE_STATUS_ADD(node, NST_BY_NUMBER);
1512
1513   return node;
1514 }
1515
1516 static Node*
1517 node_new_enclosure(enum EnclosureType type)
1518 {
1519   Node* node = node_new();
1520   CHECK_NULL_RETURN(node);
1521
1522   NODE_SET_TYPE(node, NODE_ENCLOSURE);
1523   ENCLOSURE_(node)->type = type;
1524
1525   switch (type) {
1526   case ENCLOSURE_MEMORY:
1527     ENCLOSURE_(node)->m.regnum       =  0;
1528     ENCLOSURE_(node)->m.called_addr  = -1;
1529     ENCLOSURE_(node)->m.entry_count  =  1;
1530     ENCLOSURE_(node)->m.called_state =  0;
1531     break;
1532
1533   case ENCLOSURE_OPTION:
1534     ENCLOSURE_(node)->o.options =  0;
1535     break;
1536
1537   case ENCLOSURE_STOP_BACKTRACK:
1538     break;
1539
1540   case ENCLOSURE_IF_ELSE:
1541     ENCLOSURE_(node)->te.Then = 0;
1542     ENCLOSURE_(node)->te.Else = 0;
1543     break;
1544   }
1545
1546   ENCLOSURE_(node)->opt_count = 0;
1547   return node;
1548 }
1549
1550 extern Node*
1551 onig_node_new_enclosure(int type)
1552 {
1553   return node_new_enclosure(type);
1554 }
1555
1556 static Node*
1557 node_new_enclosure_if_else(Node* cond, Node* Then, Node* Else)
1558 {
1559   Node* n;
1560   n = node_new_enclosure(ENCLOSURE_IF_ELSE);
1561   CHECK_NULL_RETURN(n);
1562
1563   NODE_BODY(n) = cond;
1564   ENCLOSURE_(n)->te.Then = Then;
1565   ENCLOSURE_(n)->te.Else = Else;
1566   return n;
1567 }
1568
1569 static Node*
1570 node_new_memory(int is_named)
1571 {
1572   Node* node = node_new_enclosure(ENCLOSURE_MEMORY);
1573   CHECK_NULL_RETURN(node);
1574   if (is_named != 0)
1575     NODE_STATUS_ADD(node, NST_NAMED_GROUP);
1576
1577   return node;
1578 }
1579
1580 static Node*
1581 node_new_option(OnigOptionType option)
1582 {
1583   Node* node = node_new_enclosure(ENCLOSURE_OPTION);
1584   CHECK_NULL_RETURN(node);
1585   ENCLOSURE_(node)->o.options = option;
1586   return node;
1587 }
1588
1589 static int
1590 node_new_fail(Node** node, ScanEnv* env)
1591 {
1592   *node = node_new();
1593   CHECK_NULL_RETURN_MEMERR(*node);
1594
1595   NODE_SET_TYPE(*node, NODE_GIMMICK);
1596   GIMMICK_(*node)->type = GIMMICK_FAIL;
1597   return ONIG_NORMAL;
1598 }
1599
1600 static int
1601 node_new_save_gimmick(Node** node, enum SaveType save_type, ScanEnv* env)
1602 {
1603   int id;
1604   int r;
1605
1606   r = save_entry(env, save_type, &id);
1607   if (r != ONIG_NORMAL) return r;
1608
1609   *node = node_new();
1610   CHECK_NULL_RETURN_MEMERR(*node);
1611
1612   NODE_SET_TYPE(*node, NODE_GIMMICK);
1613   GIMMICK_(*node)->id   = id;
1614   GIMMICK_(*node)->type = GIMMICK_SAVE;
1615   GIMMICK_(*node)->detail_type = (int )save_type;
1616
1617   return ONIG_NORMAL;
1618 }
1619
1620 static int
1621 node_new_update_var_gimmick(Node** node, enum UpdateVarType update_var_type,
1622                             int id, ScanEnv* env)
1623 {
1624   *node = node_new();
1625   CHECK_NULL_RETURN_MEMERR(*node);
1626
1627   NODE_SET_TYPE(*node, NODE_GIMMICK);
1628   GIMMICK_(*node)->id   = id;
1629   GIMMICK_(*node)->type = GIMMICK_UPDATE_VAR;
1630   GIMMICK_(*node)->detail_type = (int )update_var_type;
1631
1632   return ONIG_NORMAL;
1633 }
1634
1635 static int
1636 node_new_keep(Node** node, ScanEnv* env)
1637 {
1638   int r;
1639
1640   r = node_new_save_gimmick(node, SAVE_KEEP, env);
1641   if (r != 0) return r;
1642
1643   env->keep_num++;
1644   return ONIG_NORMAL;
1645 }
1646
1647 static int
1648 node_new_callout(Node** node, enum CalloutType callout_type, ScanEnv* env)
1649 {
1650   int r;
1651   RegexExt* ext;
1652
1653   ext = onig_get_regex_ext(env->reg);
1654   CHECK_NULL_RETURN_MEMERR(ext);
1655   if (IS_NULL(ext->pattern)) {
1656     r = onig_ext_set_pattern(env->reg, env->pattern, env->pattern_end);
1657     if (r != ONIG_NORMAL) return r;
1658   }
1659
1660   *node = node_new();
1661   CHECK_NULL_RETURN_MEMERR(*node);
1662
1663   NODE_SET_TYPE(*node, NODE_GIMMICK);
1664   GIMMICK_(*node)->id   = 0;
1665   GIMMICK_(*node)->type = GIMMICK_CALLOUT;
1666   GIMMICK_(*node)->detail_type = (int )callout_type;
1667   GIMMICK_(*node)->start = -1;
1668   GIMMICK_(*node)->end   = -1;
1669
1670   return ONIG_NORMAL;
1671 }
1672
1673
1674 static int
1675 make_extended_grapheme_cluster(Node** node, ScanEnv* env)
1676 {
1677   int r;
1678   int i;
1679   Node* x;
1680   Node* ns[2];
1681
1682   /* \X == (?>\O(?:\Y\O)*) */
1683
1684   ns[1] = NULL_NODE;
1685
1686   r = ONIGERR_MEMORY;
1687   ns[0] = onig_node_new_anchor(ANCHOR_NO_EXTENDED_GRAPHEME_CLUSTER_BOUNDARY, 0);
1688   if (IS_NULL(ns[0])) goto err;
1689
1690   r = node_new_true_anychar(&ns[1], env);
1691   if (r != 0) goto err1;
1692
1693   x = make_list(2, ns);
1694   if (IS_NULL(x)) goto err;
1695   ns[0] = x;
1696   ns[1] = NULL_NODE;
1697
1698   x = node_new_quantifier(0, REPEAT_INFINITE, 1);
1699   if (IS_NULL(x)) goto err;
1700
1701   NODE_BODY(x) = ns[0];
1702   ns[0] = NULL_NODE;
1703   ns[1] = x;
1704
1705   r = node_new_true_anychar(&ns[0], env);
1706   if (r != 0) goto err1;
1707
1708   x = make_list(2, ns);
1709   if (IS_NULL(x)) goto err;
1710
1711   ns[0] = x;
1712   ns[1] = NULL_NODE;
1713
1714   x = node_new_enclosure(ENCLOSURE_STOP_BACKTRACK);
1715   if (IS_NULL(x)) goto err;
1716
1717   NODE_BODY(x) = ns[0];
1718
1719   *node = x;
1720   return ONIG_NORMAL;
1721
1722  err:
1723   r = ONIGERR_MEMORY;
1724  err1:
1725   for (i = 0; i < 2; i++) onig_node_free(ns[i]);
1726   return r;
1727 }
1728
1729 static int
1730 make_absent_engine(Node** node, int pre_save_right_id, Node* absent,
1731                    Node* step_one, int lower, int upper, int possessive,
1732                    int is_range_cutter, ScanEnv* env)
1733 {
1734   int r;
1735   int i;
1736   int id;
1737   Node* x;
1738   Node* ns[4];
1739
1740   for (i = 0; i < 4; i++) ns[i] = NULL_NODE;
1741
1742   ns[1] = absent;
1743   ns[3] = step_one; // for err
1744   r = node_new_save_gimmick(&ns[0], SAVE_S, env);
1745   if (r != 0) goto err;
1746
1747   id = GIMMICK_(ns[0])->id;
1748   r = node_new_update_var_gimmick(&ns[2], UPDATE_VAR_RIGHT_RANGE_FROM_S_STACK,
1749                                   id, env);
1750   if (r != 0) goto err;
1751
1752   r = node_new_fail(&ns[3], env);
1753   if (r != 0) goto err;
1754
1755   x = make_list(4, ns);
1756   if (IS_NULL(x)) goto err0;
1757
1758   ns[0] = x;
1759   ns[1] = step_one;
1760   ns[2] = ns[3] = NULL_NODE;
1761
1762   x = make_alt(2, ns);
1763   if (IS_NULL(x)) goto err0;
1764
1765   ns[0] = x;
1766
1767   x = node_new_quantifier(lower, upper, 0);
1768   if (IS_NULL(x)) goto err0;
1769
1770   NODE_BODY(x) = ns[0];
1771   ns[0] = x;
1772
1773   if (possessive != 0) {
1774     x = node_new_enclosure(ENCLOSURE_STOP_BACKTRACK);
1775     if (IS_NULL(x)) goto err0;
1776
1777     NODE_BODY(x) = ns[0];
1778     ns[0] = x;
1779   }
1780
1781   r = node_new_update_var_gimmick(&ns[1], UPDATE_VAR_RIGHT_RANGE_FROM_STACK,
1782                                   pre_save_right_id, env);
1783   if (r != 0) goto err;
1784
1785   r = node_new_fail(&ns[2], env);
1786   if (r != 0) goto err;
1787
1788   x = make_list(2, ns + 1);
1789   if (IS_NULL(x)) goto err0;
1790
1791   ns[1] = x; ns[2] = NULL_NODE;
1792
1793   x = make_alt(2, ns);
1794   if (IS_NULL(x)) goto err0;
1795
1796   if (is_range_cutter != 0)
1797     NODE_STATUS_ADD(x, NST_SUPER);
1798
1799   *node = x;
1800   return ONIG_NORMAL;
1801
1802  err0:
1803   r = ONIGERR_MEMORY;
1804  err:
1805   for (i = 0; i < 4; i++) onig_node_free(ns[i]);
1806   return r;
1807 }
1808
1809 static int
1810 make_absent_tail(Node** node1, Node** node2, int pre_save_right_id,
1811                  ScanEnv* env)
1812 {
1813   int r;
1814   int id;
1815   Node* save;
1816   Node* x;
1817   Node* ns[2];
1818
1819   *node1 = *node2 = NULL_NODE;
1820   save = ns[0] = ns[1] = NULL_NODE;
1821
1822   r = node_new_save_gimmick(&save, SAVE_RIGHT_RANGE, env);
1823   if (r != 0) goto err;
1824
1825   id = GIMMICK_(save)->id;
1826   r = node_new_update_var_gimmick(&ns[0], UPDATE_VAR_RIGHT_RANGE_FROM_STACK,
1827                                   id, env);
1828   if (r != 0) goto err;
1829
1830   r = node_new_fail(&ns[1], env);
1831   if (r != 0) goto err;
1832
1833   x = make_list(2, ns);
1834   if (IS_NULL(x)) goto err0;
1835
1836   ns[0] = NULL_NODE; ns[1] = x;
1837
1838   r = node_new_update_var_gimmick(&ns[0], UPDATE_VAR_RIGHT_RANGE_FROM_STACK,
1839                                   pre_save_right_id, env);
1840   if (r != 0) goto err;
1841
1842   x = make_alt(2, ns);
1843   if (IS_NULL(x)) goto err0;
1844
1845   *node1 = save;
1846   *node2 = x;
1847   return ONIG_NORMAL;
1848
1849  err0:
1850   r = ONIGERR_MEMORY;
1851  err:
1852   onig_node_free(save);
1853   onig_node_free(ns[0]);
1854   onig_node_free(ns[1]);
1855   return r;
1856 }
1857
1858 static int
1859 make_range_clear(Node** node, ScanEnv* env)
1860 {
1861   int r;
1862   int id;
1863   Node* save;
1864   Node* x;
1865   Node* ns[2];
1866
1867   *node = NULL_NODE;
1868   save = ns[0] = ns[1] = NULL_NODE;
1869
1870   r = node_new_save_gimmick(&save, SAVE_RIGHT_RANGE, env);
1871   if (r != 0) goto err;
1872
1873   id = GIMMICK_(save)->id;
1874   r = node_new_update_var_gimmick(&ns[0], UPDATE_VAR_RIGHT_RANGE_FROM_STACK,
1875                                   id, env);
1876   if (r != 0) goto err;
1877
1878   r = node_new_fail(&ns[1], env);
1879   if (r != 0) goto err;
1880
1881   x = make_list(2, ns);
1882   if (IS_NULL(x)) goto err0;
1883
1884   ns[0] = NULL_NODE; ns[1] = x;
1885
1886   r = node_new_update_var_gimmick(&ns[0], UPDATE_VAR_RIGHT_RANGE_INIT, 0, env);
1887   if (r != 0) goto err;
1888
1889   x = make_alt(2, ns);
1890   if (IS_NULL(x)) goto err0;
1891
1892   NODE_STATUS_ADD(x, NST_SUPER);
1893
1894   ns[0] = save;
1895   ns[1] = x;
1896   save = NULL_NODE;
1897   x = make_list(2, ns);
1898   if (IS_NULL(x)) goto err0;
1899
1900   *node = x;
1901   return ONIG_NORMAL;
1902
1903  err0:
1904   r = ONIGERR_MEMORY;
1905  err:
1906   onig_node_free(save);
1907   onig_node_free(ns[0]);
1908   onig_node_free(ns[1]);
1909   return r;
1910 }
1911
1912 static int
1913 is_simple_one_char_repeat(Node* node, Node** rquant, Node** rbody,
1914                           int* is_possessive, ScanEnv* env)
1915 {
1916   Node* quant;
1917   Node* body;
1918
1919   *rquant = *rbody = 0;
1920   *is_possessive = 0;
1921
1922   if (NODE_TYPE(node) == NODE_QUANT) {
1923     quant = node;
1924   }
1925   else {
1926     if (NODE_TYPE(node) == NODE_ENCLOSURE) {
1927       EnclosureNode* en = ENCLOSURE_(node);
1928       if (en->type == ENCLOSURE_STOP_BACKTRACK) {
1929         *is_possessive = 1;
1930         quant = NODE_ENCLOSURE_BODY(en);
1931         if (NODE_TYPE(quant) != NODE_QUANT)
1932           return 0;
1933       }
1934       else
1935         return 0;
1936     }
1937     else
1938       return 0;
1939   }
1940
1941   if (QUANT_(quant)->greedy == 0)
1942     return 0;
1943
1944   body = NODE_BODY(quant);
1945   switch (NODE_TYPE(body)) {
1946   case NODE_STRING:
1947     {
1948       int len;
1949       StrNode* sn = STR_(body);
1950       UChar *s = sn->s;
1951
1952       len = 0;
1953       while (s < sn->end) {
1954         s += enclen(env->enc, s);
1955         len++;
1956       }
1957       if (len != 1)
1958         return 0;
1959     }
1960
1961   case NODE_CCLASS:
1962     break;
1963
1964   default:
1965     return 0;
1966     break;
1967   }
1968
1969   if (node != quant) {
1970     NODE_BODY(node) = 0;
1971     onig_node_free(node);
1972   }
1973   NODE_BODY(quant) = NULL_NODE;
1974   *rquant = quant;
1975   *rbody  = body;
1976   return 1;
1977 }
1978
1979 static int
1980 make_absent_tree_for_simple_one_char_repeat(Node** node, Node* absent, Node* quant,
1981                                             Node* body, int possessive, ScanEnv* env)
1982 {
1983   int r;
1984   int i;
1985   int id1;
1986   int lower, upper;
1987   Node* x;
1988   Node* ns[4];
1989
1990   *node = NULL_NODE;
1991   r = ONIGERR_MEMORY;
1992   ns[0] = ns[1] = NULL_NODE;
1993   ns[2] = body, ns[3] = absent;
1994
1995   lower = QUANT_(quant)->lower;
1996   upper = QUANT_(quant)->upper;
1997   onig_node_free(quant);
1998
1999   r = node_new_save_gimmick(&ns[0], SAVE_RIGHT_RANGE, env);
2000   if (r != 0) goto err;
2001
2002   id1 = GIMMICK_(ns[0])->id;
2003
2004   r = make_absent_engine(&ns[1], id1, absent, body, lower, upper, possessive,
2005                          0, env);
2006   if (r != 0) goto err;
2007
2008   ns[2] = ns[3] = NULL_NODE;
2009
2010   r = node_new_update_var_gimmick(&ns[2], UPDATE_VAR_RIGHT_RANGE_FROM_STACK,
2011                                   id1, env);
2012   if (r != 0) goto err;
2013
2014   x = make_list(3, ns);
2015   if (IS_NULL(x)) goto err0;
2016
2017   *node = x;
2018   return ONIG_NORMAL;
2019
2020  err0:
2021   r = ONIGERR_MEMORY;
2022  err:
2023   for (i = 0; i < 4; i++) onig_node_free(ns[i]);
2024   return r;
2025 }
2026
2027 static int
2028 make_absent_tree(Node** node, Node* absent, Node* expr, int is_range_cutter,
2029                  ScanEnv* env)
2030 {
2031   int r;
2032   int i;
2033   int id1, id2;
2034   int possessive;
2035   Node* x;
2036   Node* ns[7];
2037
2038   r = ONIGERR_MEMORY;
2039   for (i = 0; i < 7; i++) ns[i] = NULL_NODE;
2040   ns[4] = expr; ns[5] = absent;
2041
2042   if (is_range_cutter == 0) {
2043     Node* quant;
2044     Node* body;
2045
2046     if (expr == NULL_NODE) {
2047       /* default expr \O* */
2048       quant = node_new_quantifier(0, REPEAT_INFINITE, 0);
2049       if (IS_NULL(quant)) goto err0;
2050
2051       r = node_new_true_anychar(&body, env);
2052       if (r != 0) {
2053         onig_node_free(quant);
2054         goto err;
2055       }
2056       possessive = 0;
2057       goto simple;
2058     }
2059     else {
2060       if (is_simple_one_char_repeat(expr, &quant, &body, &possessive, env)) {
2061       simple:
2062         r = make_absent_tree_for_simple_one_char_repeat(node, absent, quant,
2063                                                         body, possessive, env);
2064         if (r != 0) {
2065           ns[4] = NULL_NODE;
2066           onig_node_free(quant);
2067           onig_node_free(body);
2068           goto err;
2069         }
2070
2071         return ONIG_NORMAL;
2072       }
2073     }
2074   }
2075
2076   r = node_new_save_gimmick(&ns[0], SAVE_RIGHT_RANGE, env);
2077   if (r != 0) goto err;
2078
2079   id1 = GIMMICK_(ns[0])->id;
2080
2081   r = node_new_save_gimmick(&ns[1], SAVE_S, env);
2082   if (r != 0) goto err;
2083
2084   id2 = GIMMICK_(ns[1])->id;
2085
2086   r = node_new_true_anychar(&ns[3], env);
2087   if (r != 0) goto err;
2088
2089   possessive = 1;
2090   r = make_absent_engine(&ns[2], id1, absent, ns[3], 0, REPEAT_INFINITE,
2091                          possessive, is_range_cutter, env);
2092   if (r != 0) goto err;
2093
2094   ns[3] = NULL_NODE;
2095   ns[5] = NULL_NODE;
2096
2097   r = node_new_update_var_gimmick(&ns[3], UPDATE_VAR_S_FROM_STACK, id2, env);
2098   if (r != 0) goto err;
2099
2100   if (is_range_cutter != 0) {
2101     x = make_list(4, ns);
2102     if (IS_NULL(x)) goto err0;
2103   }
2104   else {
2105     r = make_absent_tail(&ns[5], &ns[6], id1, env);
2106     if (r != 0) goto err;
2107
2108     x = make_list(7, ns);
2109     if (IS_NULL(x)) goto err0;
2110   }
2111
2112   *node = x;
2113   return ONIG_NORMAL;
2114
2115  err0:
2116   r = ONIGERR_MEMORY;
2117  err:
2118   for (i = 0; i < 7; i++) onig_node_free(ns[i]);
2119   return r;
2120 }
2121
2122 extern int
2123 onig_node_str_cat(Node* node, const UChar* s, const UChar* end)
2124 {
2125   int addlen = (int )(end - s);
2126
2127   if (addlen > 0) {
2128     int len  = (int )(STR_(node)->end - STR_(node)->s);
2129
2130     if (STR_(node)->capa > 0 || (len + addlen > NODE_STRING_BUF_SIZE - 1)) {
2131       UChar* p;
2132       int capa = len + addlen + NODE_STRING_MARGIN;
2133
2134       if (capa <= STR_(node)->capa) {
2135         onig_strcpy(STR_(node)->s + len, s, end);
2136       }
2137       else {
2138         if (STR_(node)->s == STR_(node)->buf)
2139           p = strcat_capa_from_static(STR_(node)->s, STR_(node)->end,
2140                                       s, end, capa);
2141         else
2142           p = strcat_capa(STR_(node)->s, STR_(node)->end, s, end, capa);
2143
2144         CHECK_NULL_RETURN_MEMERR(p);
2145         STR_(node)->s    = p;
2146         STR_(node)->capa = capa;
2147       }
2148     }
2149     else {
2150       onig_strcpy(STR_(node)->s + len, s, end);
2151     }
2152     STR_(node)->end = STR_(node)->s + len + addlen;
2153   }
2154
2155   return 0;
2156 }
2157
2158 extern int
2159 onig_node_str_set(Node* node, const UChar* s, const UChar* end)
2160 {
2161   onig_node_str_clear(node);
2162   return onig_node_str_cat(node, s, end);
2163 }
2164
2165 static int
2166 node_str_cat_char(Node* node, UChar c)
2167 {
2168   UChar s[1];
2169
2170   s[0] = c;
2171   return onig_node_str_cat(node, s, s + 1);
2172 }
2173
2174 extern void
2175 onig_node_conv_to_str_node(Node* node, int flag)
2176 {
2177   NODE_SET_TYPE(node, NODE_STRING);
2178   STR_(node)->flag = flag;
2179   STR_(node)->capa = 0;
2180   STR_(node)->s    = STR_(node)->buf;
2181   STR_(node)->end  = STR_(node)->buf;
2182 }
2183
2184 extern void
2185 onig_node_str_clear(Node* node)
2186 {
2187   if (STR_(node)->capa != 0 &&
2188       IS_NOT_NULL(STR_(node)->s) && STR_(node)->s != STR_(node)->buf) {
2189     xfree(STR_(node)->s);
2190   }
2191
2192   STR_(node)->capa = 0;
2193   STR_(node)->flag = 0;
2194   STR_(node)->s    = STR_(node)->buf;
2195   STR_(node)->end  = STR_(node)->buf;
2196 }
2197
2198 static Node*
2199 node_new_str(const UChar* s, const UChar* end)
2200 {
2201   Node* node = node_new();
2202   CHECK_NULL_RETURN(node);
2203
2204   NODE_SET_TYPE(node, NODE_STRING);
2205   STR_(node)->capa = 0;
2206   STR_(node)->flag = 0;
2207   STR_(node)->s    = STR_(node)->buf;
2208   STR_(node)->end  = STR_(node)->buf;
2209   if (onig_node_str_cat(node, s, end)) {
2210     onig_node_free(node);
2211     return NULL;
2212   }
2213   return node;
2214 }
2215
2216 extern Node*
2217 onig_node_new_str(const UChar* s, const UChar* end)
2218 {
2219   return node_new_str(s, end);
2220 }
2221
2222 static Node*
2223 node_new_str_raw(UChar* s, UChar* end)
2224 {
2225   Node* node = node_new_str(s, end);
2226   NODE_STRING_SET_RAW(node);
2227   return node;
2228 }
2229
2230 static Node*
2231 node_new_empty(void)
2232 {
2233   return node_new_str(NULL, NULL);
2234 }
2235
2236 static Node*
2237 node_new_str_raw_char(UChar c)
2238 {
2239   UChar p[1];
2240
2241   p[0] = c;
2242   return node_new_str_raw(p, p + 1);
2243 }
2244
2245 static Node*
2246 str_node_split_last_char(StrNode* sn, OnigEncoding enc)
2247 {
2248   const UChar *p;
2249   Node* n = NULL_NODE;
2250
2251   if (sn->end > sn->s) {
2252     p = onigenc_get_prev_char_head(enc, sn->s, sn->end);
2253     if (p && p > sn->s) { /* can be split. */
2254       n = node_new_str(p, sn->end);
2255       if ((sn->flag & STRING_RAW) != 0)
2256         NODE_STRING_SET_RAW(n);
2257
2258       sn->end = (UChar* )p;
2259     }
2260   }
2261   return n;
2262 }
2263
2264 static int
2265 str_node_can_be_split(StrNode* sn, OnigEncoding enc)
2266 {
2267   if (sn->end > sn->s) {
2268     return ((enclen(enc, sn->s) < sn->end - sn->s)  ?  1 : 0);
2269   }
2270   return 0;
2271 }
2272
2273 #ifdef USE_PAD_TO_SHORT_BYTE_CHAR
2274 static int
2275 node_str_head_pad(StrNode* sn, int num, UChar val)
2276 {
2277   UChar buf[NODE_STRING_BUF_SIZE];
2278   int i, len;
2279
2280   len = sn->end - sn->s;
2281   onig_strcpy(buf, sn->s, sn->end);
2282   onig_strcpy(&(sn->s[num]), buf, buf + len);
2283   sn->end += num;
2284
2285   for (i = 0; i < num; i++) {
2286     sn->s[i] = val;
2287   }
2288 }
2289 #endif
2290
2291 extern int
2292 onig_scan_unsigned_number(UChar** src, const UChar* end, OnigEncoding enc)
2293 {
2294   unsigned int num, val;
2295   OnigCodePoint c;
2296   UChar* p = *src;
2297   PFETCH_READY;
2298
2299   num = 0;
2300   while (! PEND) {
2301     PFETCH(c);
2302     if (IS_CODE_DIGIT_ASCII(enc, c)) {
2303       val = (unsigned int )DIGITVAL(c);
2304       if ((INT_MAX_LIMIT - val) / 10UL < num)
2305         return -1;  /* overflow */
2306
2307       num = num * 10 + val;
2308     }
2309     else {
2310       PUNFETCH;
2311       break;
2312     }
2313   }
2314   *src = p;
2315   return num;
2316 }
2317
2318 static int
2319 scan_unsigned_hexadecimal_number(UChar** src, UChar* end, int minlen,
2320                                  int maxlen, OnigEncoding enc)
2321 {
2322   OnigCodePoint c;
2323   unsigned int num, val;
2324   int n;
2325   UChar* p = *src;
2326   PFETCH_READY;
2327
2328   num = 0;
2329   n = 0;
2330   while (! PEND && n < maxlen) {
2331     PFETCH(c);
2332     if (IS_CODE_XDIGIT_ASCII(enc, c)) {
2333       n++;
2334       val = (unsigned int )XDIGITVAL(enc,c);
2335       if ((INT_MAX_LIMIT - val) / 16UL < num)
2336         return ONIGERR_TOO_BIG_NUMBER; /* overflow */
2337
2338       num = (num << 4) + XDIGITVAL(enc,c);
2339     }
2340     else {
2341       PUNFETCH;
2342       break;
2343     }
2344   }
2345
2346   if (n < minlen)
2347     return ONIGERR_INVALID_CODE_POINT_VALUE;
2348
2349   *src = p;
2350   return num;
2351 }
2352
2353 static int
2354 scan_unsigned_octal_number(UChar** src, UChar* end, int maxlen,
2355                            OnigEncoding enc)
2356 {
2357   OnigCodePoint c;
2358   unsigned int num, val;
2359   UChar* p = *src;
2360   PFETCH_READY;
2361
2362   num = 0;
2363   while (! PEND && maxlen-- != 0) {
2364     PFETCH(c);
2365     if (IS_CODE_DIGIT_ASCII(enc, c) && c < '8') {
2366       val = ODIGITVAL(c);
2367       if ((INT_MAX_LIMIT - val) / 8UL < num)
2368         return -1;  /* overflow */
2369
2370       num = (num << 3) + val;
2371     }
2372     else {
2373       PUNFETCH;
2374       break;
2375     }
2376   }
2377   *src = p;
2378   return num;
2379 }
2380
2381
2382 #define BB_WRITE_CODE_POINT(bbuf,pos,code) \
2383     BB_WRITE(bbuf, pos, &(code), SIZE_CODE_POINT)
2384
2385 /* data format:
2386      [n][from-1][to-1][from-2][to-2] ... [from-n][to-n]
2387      (all data size is OnigCodePoint)
2388  */
2389 static int
2390 new_code_range(BBuf** pbuf)
2391 {
2392 #define INIT_MULTI_BYTE_RANGE_SIZE  (SIZE_CODE_POINT * 5)
2393   int r;
2394   OnigCodePoint n;
2395   BBuf* bbuf;
2396
2397   bbuf = *pbuf = (BBuf* )xmalloc(sizeof(BBuf));
2398   CHECK_NULL_RETURN_MEMERR(bbuf);
2399   r = BB_INIT(bbuf, INIT_MULTI_BYTE_RANGE_SIZE);
2400   if (r != 0) {
2401     xfree(bbuf);
2402     *pbuf = 0;
2403     return r;
2404   }
2405
2406   n = 0;
2407   BB_WRITE_CODE_POINT(bbuf, 0, n);
2408   return 0;
2409 }
2410
2411 static int
2412 add_code_range_to_buf(BBuf** pbuf, OnigCodePoint from, OnigCodePoint to)
2413 {
2414   int r, inc_n, pos;
2415   int low, high, bound, x;
2416   OnigCodePoint n, *data;
2417   BBuf* bbuf;
2418
2419   if (from > to) {
2420     n = from; from = to; to = n;
2421   }
2422
2423   if (IS_NULL(*pbuf)) {
2424     r = new_code_range(pbuf);
2425     if (r != 0) return r;
2426     bbuf = *pbuf;
2427     n = 0;
2428   }
2429   else {
2430     bbuf = *pbuf;
2431     GET_CODE_POINT(n, bbuf->p);
2432   }
2433   data = (OnigCodePoint* )(bbuf->p);
2434   data++;
2435
2436   for (low = 0, bound = n; low < bound; ) {
2437     x = (low + bound) >> 1;
2438     if (from > data[x*2 + 1])
2439       low = x + 1;
2440     else
2441       bound = x;
2442   }
2443
2444   high = (to == ~((OnigCodePoint )0)) ? n : low;
2445   for (bound = n; high < bound; ) {
2446     x = (high + bound) >> 1;
2447     if (to + 1 >= data[x*2])
2448       high = x + 1;
2449     else
2450       bound = x;
2451   }
2452
2453   inc_n = low + 1 - high;
2454   if (n + inc_n > ONIG_MAX_MULTI_BYTE_RANGES_NUM)
2455     return ONIGERR_TOO_MANY_MULTI_BYTE_RANGES;
2456
2457   if (inc_n != 1) {
2458     if (from > data[low*2])
2459       from = data[low*2];
2460     if (to < data[(high - 1)*2 + 1])
2461       to = data[(high - 1)*2 + 1];
2462   }
2463
2464   if (inc_n != 0 && (OnigCodePoint )high < n) {
2465     int from_pos = SIZE_CODE_POINT * (1 + high * 2);
2466     int to_pos   = SIZE_CODE_POINT * (1 + (low + 1) * 2);
2467     int size = (n - high) * 2 * SIZE_CODE_POINT;
2468
2469     if (inc_n > 0) {
2470       BB_MOVE_RIGHT(bbuf, from_pos, to_pos, size);
2471     }
2472     else {
2473       BB_MOVE_LEFT_REDUCE(bbuf, from_pos, to_pos);
2474     }
2475   }
2476
2477   pos = SIZE_CODE_POINT * (1 + low * 2);
2478   BB_ENSURE_SIZE(bbuf, pos + SIZE_CODE_POINT * 2);
2479   BB_WRITE_CODE_POINT(bbuf, pos, from);
2480   BB_WRITE_CODE_POINT(bbuf, pos + SIZE_CODE_POINT, to);
2481   n += inc_n;
2482   BB_WRITE_CODE_POINT(bbuf, 0, n);
2483
2484   return 0;
2485 }
2486
2487 static int
2488 add_code_range(BBuf** pbuf, ScanEnv* env, OnigCodePoint from, OnigCodePoint to)
2489 {
2490   if (from > to) {
2491     if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_EMPTY_RANGE_IN_CC))
2492       return 0;
2493     else
2494       return ONIGERR_EMPTY_RANGE_IN_CHAR_CLASS;
2495   }
2496
2497   return add_code_range_to_buf(pbuf, from, to);
2498 }
2499
2500 static int
2501 not_code_range_buf(OnigEncoding enc, BBuf* bbuf, BBuf** pbuf)
2502 {
2503   int r, i, n;
2504   OnigCodePoint pre, from, *data, to = 0;
2505
2506   *pbuf = (BBuf* )NULL;
2507   if (IS_NULL(bbuf)) {
2508   set_all:
2509     return SET_ALL_MULTI_BYTE_RANGE(enc, pbuf);
2510   }
2511
2512   data = (OnigCodePoint* )(bbuf->p);
2513   GET_CODE_POINT(n, data);
2514   data++;
2515   if (n <= 0) goto set_all;
2516
2517   r = 0;
2518   pre = MBCODE_START_POS(enc);
2519   for (i = 0; i < n; i++) {
2520     from = data[i*2];
2521     to   = data[i*2+1];
2522     if (pre <= from - 1) {
2523       r = add_code_range_to_buf(pbuf, pre, from - 1);
2524       if (r != 0) return r;
2525     }
2526     if (to == ~((OnigCodePoint )0)) break;
2527     pre = to + 1;
2528   }
2529   if (to < ~((OnigCodePoint )0)) {
2530     r = add_code_range_to_buf(pbuf, to + 1, ~((OnigCodePoint )0));
2531   }
2532   return r;
2533 }
2534
2535 #define SWAP_BB_NOT(bbuf1, not1, bbuf2, not2) do {\
2536   BBuf *tbuf; \
2537   int  tnot; \
2538   tnot = not1;  not1  = not2;  not2  = tnot; \
2539   tbuf = bbuf1; bbuf1 = bbuf2; bbuf2 = tbuf; \
2540 } while (0)
2541
2542 static int
2543 or_code_range_buf(OnigEncoding enc, BBuf* bbuf1, int not1,
2544                   BBuf* bbuf2, int not2, BBuf** pbuf)
2545 {
2546   int r;
2547   OnigCodePoint i, n1, *data1;
2548   OnigCodePoint from, to;
2549
2550   *pbuf = (BBuf* )NULL;
2551   if (IS_NULL(bbuf1) && IS_NULL(bbuf2)) {
2552     if (not1 != 0 || not2 != 0)
2553       return SET_ALL_MULTI_BYTE_RANGE(enc, pbuf);
2554     return 0;
2555   }
2556
2557   r = 0;
2558   if (IS_NULL(bbuf2))
2559     SWAP_BB_NOT(bbuf1, not1, bbuf2, not2);
2560
2561   if (IS_NULL(bbuf1)) {
2562     if (not1 != 0) {
2563       return SET_ALL_MULTI_BYTE_RANGE(enc, pbuf);
2564     }
2565     else {
2566       if (not2 == 0) {
2567         return bbuf_clone(pbuf, bbuf2);
2568       }
2569       else {
2570         return not_code_range_buf(enc, bbuf2, pbuf);
2571       }
2572     }
2573   }
2574
2575   if (not1 != 0)
2576     SWAP_BB_NOT(bbuf1, not1, bbuf2, not2);
2577
2578   data1 = (OnigCodePoint* )(bbuf1->p);
2579   GET_CODE_POINT(n1, data1);
2580   data1++;
2581
2582   if (not2 == 0 && not1 == 0) { /* 1 OR 2 */
2583     r = bbuf_clone(pbuf, bbuf2);
2584   }
2585   else if (not1 == 0) { /* 1 OR (not 2) */
2586     r = not_code_range_buf(enc, bbuf2, pbuf);
2587   }
2588   if (r != 0) return r;
2589
2590   for (i = 0; i < n1; i++) {
2591     from = data1[i*2];
2592     to   = data1[i*2+1];
2593     r = add_code_range_to_buf(pbuf, from, to);
2594     if (r != 0) return r;
2595   }
2596   return 0;
2597 }
2598
2599 static int
2600 and_code_range1(BBuf** pbuf, OnigCodePoint from1, OnigCodePoint to1,
2601                 OnigCodePoint* data, int n)
2602 {
2603   int i, r;
2604   OnigCodePoint from2, to2;
2605
2606   for (i = 0; i < n; i++) {
2607     from2 = data[i*2];
2608     to2   = data[i*2+1];
2609     if (from2 < from1) {
2610       if (to2 < from1) continue;
2611       else {
2612         from1 = to2 + 1;
2613       }
2614     }
2615     else if (from2 <= to1) {
2616       if (to2 < to1) {
2617         if (from1 <= from2 - 1) {
2618           r = add_code_range_to_buf(pbuf, from1, from2-1);
2619           if (r != 0) return r;
2620         }
2621         from1 = to2 + 1;
2622       }
2623       else {
2624         to1 = from2 - 1;
2625       }
2626     }
2627     else {
2628       from1 = from2;
2629     }
2630     if (from1 > to1) break;
2631   }
2632   if (from1 <= to1) {
2633     r = add_code_range_to_buf(pbuf, from1, to1);
2634     if (r != 0) return r;
2635   }
2636   return 0;
2637 }
2638
2639 static int
2640 and_code_range_buf(BBuf* bbuf1, int not1, BBuf* bbuf2, int not2, BBuf** pbuf)
2641 {
2642   int r;
2643   OnigCodePoint i, j, n1, n2, *data1, *data2;
2644   OnigCodePoint from, to, from1, to1, from2, to2;
2645
2646   *pbuf = (BBuf* )NULL;
2647   if (IS_NULL(bbuf1)) {
2648     if (not1 != 0 && IS_NOT_NULL(bbuf2)) /* not1 != 0 -> not2 == 0 */
2649       return bbuf_clone(pbuf, bbuf2);
2650     return 0;
2651   }
2652   else if (IS_NULL(bbuf2)) {
2653     if (not2 != 0)
2654       return bbuf_clone(pbuf, bbuf1);
2655     return 0;
2656   }
2657
2658   if (not1 != 0)
2659     SWAP_BB_NOT(bbuf1, not1, bbuf2, not2);
2660
2661   data1 = (OnigCodePoint* )(bbuf1->p);
2662   data2 = (OnigCodePoint* )(bbuf2->p);
2663   GET_CODE_POINT(n1, data1);
2664   GET_CODE_POINT(n2, data2);
2665   data1++;
2666   data2++;
2667
2668   if (not2 == 0 && not1 == 0) { /* 1 AND 2 */
2669     for (i = 0; i < n1; i++) {
2670       from1 = data1[i*2];
2671       to1   = data1[i*2+1];
2672       for (j = 0; j < n2; j++) {
2673         from2 = data2[j*2];
2674         to2   = data2[j*2+1];
2675         if (from2 > to1) break;
2676         if (to2 < from1) continue;
2677         from = MAX(from1, from2);
2678         to   = MIN(to1, to2);
2679         r = add_code_range_to_buf(pbuf, from, to);
2680         if (r != 0) return r;
2681       }
2682     }
2683   }
2684   else if (not1 == 0) { /* 1 AND (not 2) */
2685     for (i = 0; i < n1; i++) {
2686       from1 = data1[i*2];
2687       to1   = data1[i*2+1];
2688       r = and_code_range1(pbuf, from1, to1, data2, n2);
2689       if (r != 0) return r;
2690     }
2691   }
2692
2693   return 0;
2694 }
2695
2696 static int
2697 and_cclass(CClassNode* dest, CClassNode* cc, OnigEncoding enc)
2698 {
2699   int r, not1, not2;
2700   BBuf *buf1, *buf2, *pbuf;
2701   BitSetRef bsr1, bsr2;
2702   BitSet bs1, bs2;
2703
2704   not1 = IS_NCCLASS_NOT(dest);
2705   bsr1 = dest->bs;
2706   buf1 = dest->mbuf;
2707   not2 = IS_NCCLASS_NOT(cc);
2708   bsr2 = cc->bs;
2709   buf2 = cc->mbuf;
2710
2711   if (not1 != 0) {
2712     bitset_invert_to(bsr1, bs1);
2713     bsr1 = bs1;
2714   }
2715   if (not2 != 0) {
2716     bitset_invert_to(bsr2, bs2);
2717     bsr2 = bs2;
2718   }
2719   bitset_and(bsr1, bsr2);
2720   if (bsr1 != dest->bs) {
2721     bitset_copy(dest->bs, bsr1);
2722   }
2723   if (not1 != 0) {
2724     bitset_invert(dest->bs);
2725   }
2726
2727   if (! ONIGENC_IS_SINGLEBYTE(enc)) {
2728     if (not1 != 0 && not2 != 0) {
2729       r = or_code_range_buf(enc, buf1, 0, buf2, 0, &pbuf);
2730     }
2731     else {
2732       r = and_code_range_buf(buf1, not1, buf2, not2, &pbuf);
2733       if (r == 0 && not1 != 0) {
2734         BBuf *tbuf;
2735         r = not_code_range_buf(enc, pbuf, &tbuf);
2736         if (r != 0) {
2737           bbuf_free(pbuf);
2738           return r;
2739         }
2740         bbuf_free(pbuf);
2741         pbuf = tbuf;
2742       }
2743     }
2744     if (r != 0) return r;
2745
2746     dest->mbuf = pbuf;
2747     bbuf_free(buf1);
2748     return r;
2749   }
2750   return 0;
2751 }
2752
2753 static int
2754 or_cclass(CClassNode* dest, CClassNode* cc, OnigEncoding enc)
2755 {
2756   int r, not1, not2;
2757   BBuf *buf1, *buf2, *pbuf;
2758   BitSetRef bsr1, bsr2;
2759   BitSet bs1, bs2;
2760
2761   not1 = IS_NCCLASS_NOT(dest);
2762   bsr1 = dest->bs;
2763   buf1 = dest->mbuf;
2764   not2 = IS_NCCLASS_NOT(cc);
2765   bsr2 = cc->bs;
2766   buf2 = cc->mbuf;
2767
2768   if (not1 != 0) {
2769     bitset_invert_to(bsr1, bs1);
2770     bsr1 = bs1;
2771   }
2772   if (not2 != 0) {
2773     bitset_invert_to(bsr2, bs2);
2774     bsr2 = bs2;
2775   }
2776   bitset_or(bsr1, bsr2);
2777   if (bsr1 != dest->bs) {
2778     bitset_copy(dest->bs, bsr1);
2779   }
2780   if (not1 != 0) {
2781     bitset_invert(dest->bs);
2782   }
2783
2784   if (! ONIGENC_IS_SINGLEBYTE(enc)) {
2785     if (not1 != 0 && not2 != 0) {
2786       r = and_code_range_buf(buf1, 0, buf2, 0, &pbuf);
2787     }
2788     else {
2789       r = or_code_range_buf(enc, buf1, not1, buf2, not2, &pbuf);
2790       if (r == 0 && not1 != 0) {
2791         BBuf *tbuf;
2792         r = not_code_range_buf(enc, pbuf, &tbuf);
2793         if (r != 0) {
2794           bbuf_free(pbuf);
2795           return r;
2796         }
2797         bbuf_free(pbuf);
2798         pbuf = tbuf;
2799       }
2800     }
2801     if (r != 0) return r;
2802
2803     dest->mbuf = pbuf;
2804     bbuf_free(buf1);
2805     return r;
2806   }
2807   else
2808     return 0;
2809 }
2810
2811 static OnigCodePoint
2812 conv_backslash_value(OnigCodePoint c, ScanEnv* env)
2813 {
2814   if (IS_SYNTAX_OP(env->syntax, ONIG_SYN_OP_ESC_CONTROL_CHARS)) {
2815     switch (c) {
2816     case 'n': return '\n';
2817     case 't': return '\t';
2818     case 'r': return '\r';
2819     case 'f': return '\f';
2820     case 'a': return '\007';
2821     case 'b': return '\010';
2822     case 'e': return '\033';
2823     case 'v':
2824       if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_ESC_V_VTAB))
2825         return '\v';
2826       break;
2827
2828     default:
2829       break;
2830     }
2831   }
2832   return c;
2833 }
2834
2835 static int
2836 is_invalid_quantifier_target(Node* node)
2837 {
2838   switch (NODE_TYPE(node)) {
2839   case NODE_ANCHOR:
2840   case NODE_GIMMICK:
2841     return 1;
2842     break;
2843
2844   case NODE_ENCLOSURE:
2845     /* allow enclosed elements */
2846     /* return is_invalid_quantifier_target(NODE_BODY(node)); */
2847     break;
2848
2849   case NODE_LIST:
2850     do {
2851       if (! is_invalid_quantifier_target(NODE_CAR(node))) return 0;
2852     } while (IS_NOT_NULL(node = NODE_CDR(node)));
2853     return 0;
2854     break;
2855
2856   case NODE_ALT:
2857     do {
2858       if (is_invalid_quantifier_target(NODE_CAR(node))) return 1;
2859     } while (IS_NOT_NULL(node = NODE_CDR(node)));
2860     break;
2861
2862   default:
2863     break;
2864   }
2865   return 0;
2866 }
2867
2868 /* ?:0, *:1, +:2, ??:3, *?:4, +?:5 */
2869 static int
2870 quantifier_type_num(QuantNode* q)
2871 {
2872   if (q->greedy) {
2873     if (q->lower == 0) {
2874       if (q->upper == 1) return 0;
2875       else if (IS_REPEAT_INFINITE(q->upper)) return 1;
2876     }
2877     else if (q->lower == 1) {
2878       if (IS_REPEAT_INFINITE(q->upper)) return 2;
2879     }
2880   }
2881   else {
2882     if (q->lower == 0) {
2883       if (q->upper == 1) return 3;
2884       else if (IS_REPEAT_INFINITE(q->upper)) return 4;
2885     }
2886     else if (q->lower == 1) {
2887       if (IS_REPEAT_INFINITE(q->upper)) return 5;
2888     }
2889   }
2890   return -1;
2891 }
2892
2893
2894 enum ReduceType {
2895   RQ_ASIS = 0, /* as is */
2896   RQ_DEL  = 1, /* delete parent */
2897   RQ_A,        /* to '*'    */
2898   RQ_AQ,       /* to '*?'   */
2899   RQ_QQ,       /* to '??'   */
2900   RQ_P_QQ,     /* to '+)??' */
2901   RQ_PQ_Q      /* to '+?)?' */
2902 };
2903
2904 static enum ReduceType ReduceTypeTable[6][6] = {
2905   {RQ_DEL,  RQ_A,    RQ_A,   RQ_QQ,   RQ_AQ,   RQ_ASIS}, /* '?'  */
2906   {RQ_DEL,  RQ_DEL,  RQ_DEL, RQ_P_QQ, RQ_P_QQ, RQ_DEL},  /* '*'  */
2907   {RQ_A,    RQ_A,    RQ_DEL, RQ_ASIS, RQ_P_QQ, RQ_DEL},  /* '+'  */
2908   {RQ_DEL,  RQ_AQ,   RQ_AQ,  RQ_DEL,  RQ_AQ,   RQ_AQ},   /* '??' */
2909   {RQ_DEL,  RQ_DEL,  RQ_DEL, RQ_DEL,  RQ_DEL,  RQ_DEL},  /* '*?' */
2910   {RQ_ASIS, RQ_PQ_Q, RQ_DEL, RQ_AQ,   RQ_AQ,   RQ_DEL}   /* '+?' */
2911 };
2912
2913 extern void
2914 onig_reduce_nested_quantifier(Node* pnode, Node* cnode)
2915 {
2916   int pnum, cnum;
2917   QuantNode *p, *c;
2918
2919   p = QUANT_(pnode);
2920   c = QUANT_(cnode);
2921   pnum = quantifier_type_num(p);
2922   cnum = quantifier_type_num(c);
2923   if (pnum < 0 || cnum < 0) {
2924     if ((p->lower == p->upper) && ! IS_REPEAT_INFINITE(p->upper)) {
2925       if ((c->lower == c->upper) && ! IS_REPEAT_INFINITE(c->upper)) {
2926         int n = positive_int_multiply(p->lower, c->lower);
2927         if (n >= 0) {
2928           p->lower = p->upper = n;
2929           NODE_BODY(pnode) = NODE_BODY(cnode);
2930           goto remove_cnode;
2931         }
2932       }
2933     }
2934
2935     return ;
2936   }
2937
2938   switch(ReduceTypeTable[cnum][pnum]) {
2939   case RQ_DEL:
2940     *pnode = *cnode;
2941     break;
2942   case RQ_A:
2943     NODE_BODY(pnode) = NODE_BODY(cnode);
2944     p->lower  = 0;  p->upper = REPEAT_INFINITE;  p->greedy = 1;
2945     break;
2946   case RQ_AQ:
2947     NODE_BODY(pnode) = NODE_BODY(cnode);
2948     p->lower  = 0;  p->upper = REPEAT_INFINITE;  p->greedy = 0;
2949     break;
2950   case RQ_QQ:
2951     NODE_BODY(pnode) = NODE_BODY(cnode);
2952     p->lower  = 0;  p->upper = 1;  p->greedy = 0;
2953     break;
2954   case RQ_P_QQ:
2955     NODE_BODY(pnode) = cnode;
2956     p->lower  = 0;  p->upper = 1;  p->greedy = 0;
2957     c->lower  = 1;  c->upper = REPEAT_INFINITE;  c->greedy = 1;
2958     return ;
2959     break;
2960   case RQ_PQ_Q:
2961     NODE_BODY(pnode) = cnode;
2962     p->lower  = 0;  p->upper = 1;  p->greedy = 1;
2963     c->lower  = 1;  c->upper = REPEAT_INFINITE;  c->greedy = 0;
2964     return ;
2965     break;
2966   case RQ_ASIS:
2967     NODE_BODY(pnode) = cnode;
2968     return ;
2969     break;
2970   }
2971
2972  remove_cnode:
2973   NODE_BODY(cnode) = NULL_NODE;
2974   onig_node_free(cnode);
2975 }
2976
2977 static int
2978 node_new_general_newline(Node** node, ScanEnv* env)
2979 {
2980   int r;
2981   int dlen, alen;
2982   UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN * 2];
2983   Node* crnl;
2984   Node* ncc;
2985   Node* x;
2986   CClassNode* cc;
2987
2988   dlen = ONIGENC_CODE_TO_MBC(env->enc, 0x0d, buf);
2989   if (dlen < 0) return dlen;
2990   alen = ONIGENC_CODE_TO_MBC(env->enc, 0x0a, buf + dlen);
2991   if (alen < 0) return alen;
2992
2993   crnl = node_new_str_raw(buf, buf + dlen + alen);
2994   CHECK_NULL_RETURN_MEMERR(crnl);
2995
2996   ncc = node_new_cclass();
2997   if (IS_NULL(ncc)) goto err2;
2998
2999   cc = CCLASS_(ncc);
3000   if (dlen == 1) {
3001     bitset_set_range(cc->bs, 0x0a, 0x0d);
3002   }
3003   else {
3004     r = add_code_range(&(cc->mbuf), env, 0x0a, 0x0d);
3005     if (r != 0) {
3006     err1:
3007       onig_node_free(ncc);
3008     err2:
3009       onig_node_free(crnl);
3010       return ONIGERR_MEMORY;
3011     }
3012   }
3013
3014   if (ONIGENC_IS_UNICODE_ENCODING(env->enc)) {
3015     r = add_code_range(&(cc->mbuf), env, 0x85, 0x85);
3016     if (r != 0) goto err1;
3017     r = add_code_range(&(cc->mbuf), env, 0x2028, 0x2029);
3018     if (r != 0) goto err1;
3019   }
3020
3021   x = node_new_enclosure_if_else(crnl, 0, ncc);
3022   if (IS_NULL(x)) goto err1;
3023
3024   *node = x;
3025   return 0;
3026 }
3027
3028 enum TokenSyms {
3029   TK_EOT      = 0,   /* end of token */
3030   TK_RAW_BYTE = 1,
3031   TK_CHAR,
3032   TK_STRING,
3033   TK_CODE_POINT,
3034   TK_ANYCHAR,
3035   TK_CHAR_TYPE,
3036   TK_BACKREF,
3037   TK_CALL,
3038   TK_ANCHOR,
3039   TK_OP_REPEAT,
3040   TK_INTERVAL,
3041   TK_ANYCHAR_ANYTIME,  /* SQL '%' == .* */
3042   TK_ALT,
3043   TK_SUBEXP_OPEN,
3044   TK_SUBEXP_CLOSE,
3045   TK_CC_OPEN,
3046   TK_QUOTE_OPEN,
3047   TK_CHAR_PROPERTY,    /* \p{...}, \P{...} */
3048   TK_KEEP,             /* \K */
3049   TK_GENERAL_NEWLINE,  /* \R */
3050   TK_NO_NEWLINE,       /* \N */
3051   TK_TRUE_ANYCHAR,     /* \O */
3052   TK_EXTENDED_GRAPHEME_CLUSTER, /* \X */
3053
3054   /* in cc */
3055   TK_CC_CLOSE,
3056   TK_CC_RANGE,
3057   TK_POSIX_BRACKET_OPEN,
3058   TK_CC_AND,             /* && */
3059   TK_CC_CC_OPEN          /* [ */
3060 };
3061
3062 typedef struct {
3063   enum TokenSyms type;
3064   int escaped;
3065   int base;   /* is number: 8, 16 (used in [....]) */
3066   UChar* backp;
3067   union {
3068     UChar* s;
3069     int   c;
3070     OnigCodePoint code;
3071     int   anchor;
3072     int   subtype;
3073     struct {
3074       int lower;
3075       int upper;
3076       int greedy;
3077       int possessive;
3078     } repeat;
3079     struct {
3080       int  num;
3081       int  ref1;
3082       int* refs;
3083       int  by_name;
3084 #ifdef USE_BACKREF_WITH_LEVEL
3085       int  exist_level;
3086       int  level;   /* \k<name+n> */
3087 #endif
3088     } backref;
3089     struct {
3090       UChar* name;
3091       UChar* name_end;
3092       int    gnum;
3093       int    by_number;
3094     } call;
3095     struct {
3096       int ctype;
3097       int not;
3098     } prop;
3099   } u;
3100 } OnigToken;
3101
3102
3103 static int
3104 fetch_range_quantifier(UChar** src, UChar* end, OnigToken* tok, ScanEnv* env)
3105 {
3106   int low, up, syn_allow, non_low = 0;
3107   int r = 0;
3108   OnigCodePoint c;
3109   OnigEncoding enc = env->enc;
3110   UChar* p = *src;
3111   PFETCH_READY;
3112
3113   syn_allow = IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_INVALID_INTERVAL);
3114
3115   if (PEND) {
3116     if (syn_allow)
3117       return 1;  /* "....{" : OK! */
3118     else
3119       return ONIGERR_END_PATTERN_AT_LEFT_BRACE;  /* "....{" syntax error */
3120   }
3121
3122   if (! syn_allow) {
3123     c = PPEEK;
3124     if (c == ')' || c == '(' || c == '|') {
3125       return ONIGERR_END_PATTERN_AT_LEFT_BRACE;
3126     }
3127   }
3128
3129   low = onig_scan_unsigned_number(&p, end, env->enc);
3130   if (low < 0) return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE;
3131   if (low > ONIG_MAX_REPEAT_NUM)
3132     return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE;
3133
3134   if (p == *src) { /* can't read low */
3135     if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_INTERVAL_LOW_ABBREV)) {
3136       /* allow {,n} as {0,n} */
3137       low = 0;
3138       non_low = 1;
3139     }
3140     else
3141       goto invalid;
3142   }
3143
3144   if (PEND) goto invalid;
3145   PFETCH(c);
3146   if (c == ',') {
3147     UChar* prev = p;
3148     up = onig_scan_unsigned_number(&p, end, env->enc);
3149     if (up < 0) return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE;
3150     if (up > ONIG_MAX_REPEAT_NUM)
3151       return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE;
3152
3153     if (p == prev) {
3154       if (non_low != 0)
3155         goto invalid;
3156       up = REPEAT_INFINITE;  /* {n,} : {n,infinite} */
3157     }
3158   }
3159   else {
3160     if (non_low != 0)
3161       goto invalid;
3162
3163     PUNFETCH;
3164     up = low;  /* {n} : exact n times */
3165     r = 2;     /* fixed */
3166   }
3167
3168   if (PEND) goto invalid;
3169   PFETCH(c);
3170   if (IS_SYNTAX_OP(env->syntax, ONIG_SYN_OP_ESC_BRACE_INTERVAL)) {
3171     if (c != MC_ESC(env->syntax)) goto invalid;
3172     PFETCH(c);
3173   }
3174   if (c != '}') goto invalid;
3175
3176   if (!IS_REPEAT_INFINITE(up) && low > up) {
3177     return ONIGERR_UPPER_SMALLER_THAN_LOWER_IN_REPEAT_RANGE;
3178   }
3179
3180   tok->type = TK_INTERVAL;
3181   tok->u.repeat.lower = low;
3182   tok->u.repeat.upper = up;
3183   *src = p;
3184   return r; /* 0: normal {n,m}, 2: fixed {n} */
3185
3186  invalid:
3187   if (syn_allow) {
3188     /* *src = p; */ /* !!! Don't do this line !!! */
3189     return 1;  /* OK */
3190   }
3191   else
3192     return ONIGERR_INVALID_REPEAT_RANGE_PATTERN;
3193 }
3194
3195 /* \M-, \C-, \c, or \... */
3196 static int
3197 fetch_escaped_value(UChar** src, UChar* end, ScanEnv* env, OnigCodePoint* val)
3198 {
3199   int v;
3200   OnigCodePoint c;
3201   OnigEncoding enc = env->enc;
3202   UChar* p = *src;
3203
3204   if (PEND) return ONIGERR_END_PATTERN_AT_ESCAPE;
3205
3206   PFETCH_S(c);
3207   switch (c) {
3208   case 'M':
3209     if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_ESC_CAPITAL_M_BAR_META)) {
3210       if (PEND) return ONIGERR_END_PATTERN_AT_META;
3211       PFETCH_S(c);
3212       if (c != '-') return ONIGERR_META_CODE_SYNTAX;
3213       if (PEND) return ONIGERR_END_PATTERN_AT_META;
3214       PFETCH_S(c);
3215       if (c == MC_ESC(env->syntax)) {
3216         v = fetch_escaped_value(&p, end, env, &c);
3217         if (v < 0) return v;
3218       }
3219       c = ((c & 0xff) | 0x80);
3220     }
3221     else
3222       goto backslash;
3223     break;
3224
3225   case 'C':
3226     if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_ESC_CAPITAL_C_BAR_CONTROL)) {
3227       if (PEND) return ONIGERR_END_PATTERN_AT_CONTROL;
3228       PFETCH_S(c);
3229       if (c != '-') return ONIGERR_CONTROL_CODE_SYNTAX;
3230       goto control;
3231     }
3232     else
3233       goto backslash;
3234
3235   case 'c':
3236     if (IS_SYNTAX_OP(env->syntax, ONIG_SYN_OP_ESC_C_CONTROL)) {
3237     control:
3238       if (PEND) return ONIGERR_END_PATTERN_AT_CONTROL;
3239       PFETCH_S(c);
3240       if (c == '?') {
3241         c = 0177;
3242       }
3243       else {
3244         if (c == MC_ESC(env->syntax)) {
3245           v = fetch_escaped_value(&p, end, env, &c);
3246           if (v < 0) return v;
3247         }
3248         c &= 0x9f;
3249       }
3250       break;
3251     }
3252     /* fall through */
3253
3254   default:
3255     {
3256     backslash:
3257       c = conv_backslash_value(c, env);
3258     }
3259     break;
3260   }
3261
3262   *src = p;
3263   *val = c;
3264   return 0;
3265 }
3266
3267 static int fetch_token(OnigToken* tok, UChar** src, UChar* end, ScanEnv* env);
3268
3269 static OnigCodePoint
3270 get_name_end_code_point(OnigCodePoint start)
3271 {
3272   switch (start) {
3273   case '<':  return (OnigCodePoint )'>';  break;
3274   case '\'': return (OnigCodePoint )'\''; break;
3275   case '(':  return (OnigCodePoint )')';  break;
3276   default:
3277     break;
3278   }
3279
3280   return (OnigCodePoint )0;
3281 }
3282
3283 enum REF_NUM {
3284   IS_NOT_NUM = 0,
3285   IS_ABS_NUM = 1,
3286   IS_REL_NUM = 2
3287 };
3288
3289 #ifdef USE_BACKREF_WITH_LEVEL
3290 /*
3291    \k<name+n>, \k<name-n>
3292    \k<num+n>,  \k<num-n>
3293    \k<-num+n>, \k<-num-n>
3294    \k<+num+n>, \k<+num-n>
3295 */
3296 static int
3297 fetch_name_with_level(OnigCodePoint start_code, UChar** src, UChar* end,
3298                       UChar** rname_end, ScanEnv* env,
3299                       int* rback_num, int* rlevel, enum REF_NUM* num_type)
3300 {
3301   int r, sign, exist_level;
3302   int digit_count;
3303   OnigCodePoint end_code;
3304   OnigCodePoint c = 0;
3305   OnigEncoding enc = env->enc;
3306   UChar *name_end;
3307   UChar *pnum_head;
3308   UChar *p = *src;
3309   PFETCH_READY;
3310
3311   *rback_num = 0;
3312   exist_level = 0;
3313   *num_type = IS_NOT_NUM;
3314   sign = 1;
3315   pnum_head = *src;
3316
3317   end_code = get_name_end_code_point(start_code);
3318
3319   digit_count = 0;
3320   name_end = end;
3321   r = 0;
3322   if (PEND) {
3323     return ONIGERR_EMPTY_GROUP_NAME;
3324   }
3325   else {
3326     PFETCH(c);
3327     if (c == end_code)
3328       return ONIGERR_EMPTY_GROUP_NAME;
3329
3330     if (IS_CODE_DIGIT_ASCII(enc, c)) {
3331       *num_type = IS_ABS_NUM;
3332       digit_count++;
3333     }
3334     else if (c == '-') {
3335       *num_type = IS_REL_NUM;
3336       sign = -1;
3337       pnum_head = p;
3338     }
3339     else if (c == '+') {
3340       *num_type = IS_REL_NUM;
3341       sign = 1;
3342       pnum_head = p;
3343     }
3344     else if (!ONIGENC_IS_CODE_WORD(enc, c)) {
3345       r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME;
3346     }
3347   }
3348
3349   while (!PEND) {
3350     name_end = p;
3351     PFETCH(c);
3352     if (c == end_code || c == ')' || c == '+' || c == '-') {
3353       if (*num_type != IS_NOT_NUM && digit_count == 0)
3354         r = ONIGERR_INVALID_GROUP_NAME;
3355       break;
3356     }
3357
3358     if (*num_type != IS_NOT_NUM) {
3359       if (IS_CODE_DIGIT_ASCII(enc, c)) {
3360         digit_count++;
3361       }
3362       else {
3363         r = ONIGERR_INVALID_GROUP_NAME;
3364         *num_type = IS_NOT_NUM;
3365       }
3366     }
3367     else if (!ONIGENC_IS_CODE_WORD(enc, c)) {
3368       r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME;
3369     }
3370   }
3371
3372   if (r == 0 && c != end_code) {
3373     if (c == '+' || c == '-') {
3374       int level;
3375       int flag = (c == '-' ? -1 : 1);
3376
3377       if (PEND) {
3378         r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME;
3379         goto end;
3380       }
3381       PFETCH(c);
3382       if (! IS_CODE_DIGIT_ASCII(enc, c)) goto err;
3383       PUNFETCH;
3384       level = onig_scan_unsigned_number(&p, end, enc);
3385       if (level < 0) return ONIGERR_TOO_BIG_NUMBER;
3386       *rlevel = (level * flag);
3387       exist_level = 1;
3388
3389       if (!PEND) {
3390         PFETCH(c);
3391         if (c == end_code)
3392           goto end;
3393       }
3394     }
3395
3396   err:
3397     name_end = end;
3398   err2:
3399     r = ONIGERR_INVALID_GROUP_NAME;
3400   }
3401
3402  end:
3403   if (r == 0) {
3404     if (*num_type != IS_NOT_NUM) {
3405       *rback_num = onig_scan_unsigned_number(&pnum_head, name_end, enc);
3406       if (*rback_num < 0) return ONIGERR_TOO_BIG_NUMBER;
3407       else if (*rback_num == 0) {
3408         if (*num_type == IS_REL_NUM)
3409           goto err2;
3410       }
3411
3412       *rback_num *= sign;
3413     }
3414
3415     *rname_end = name_end;
3416     *src = p;
3417     return (exist_level ? 1 : 0);
3418   }
3419   else {
3420     onig_scan_env_set_error_string(env, r, *src, name_end);
3421     return r;
3422   }
3423 }
3424 #endif /* USE_BACKREF_WITH_LEVEL */
3425
3426 /*
3427   ref: 0 -> define name    (don't allow number name)
3428        1 -> reference name (allow number name)
3429 */
3430 static int
3431 fetch_name(OnigCodePoint start_code, UChar** src, UChar* end,
3432            UChar** rname_end, ScanEnv* env, int* rback_num,
3433            enum REF_NUM* num_type, int ref)
3434 {
3435   int r, sign;
3436   int digit_count;
3437   OnigCodePoint end_code;
3438   OnigCodePoint c = 0;
3439   OnigEncoding enc = env->enc;
3440   UChar *name_end;
3441   UChar *pnum_head;
3442   UChar *p = *src;
3443
3444   *rback_num = 0;
3445
3446   end_code = get_name_end_code_point(start_code);
3447
3448   digit_count = 0;
3449   name_end = end;
3450   pnum_head = *src;
3451   r = 0;
3452   *num_type = IS_NOT_NUM;
3453   sign = 1;
3454   if (PEND) {
3455     return ONIGERR_EMPTY_GROUP_NAME;
3456   }
3457   else {
3458     PFETCH_S(c);
3459     if (c == end_code)
3460       return ONIGERR_EMPTY_GROUP_NAME;
3461
3462     if (IS_CODE_DIGIT_ASCII(enc, c)) {
3463       if (ref == 1)
3464         *num_type = IS_ABS_NUM;
3465       else {
3466         r = ONIGERR_INVALID_GROUP_NAME;
3467       }
3468       digit_count++;
3469     }
3470     else if (c == '-') {
3471       if (ref == 1) {
3472         *num_type = IS_REL_NUM;
3473         sign = -1;
3474         pnum_head = p;
3475       }
3476       else {
3477         r = ONIGERR_INVALID_GROUP_NAME;
3478       }
3479     }
3480     else if (c == '+') {
3481       if (ref == 1) {
3482         *num_type = IS_REL_NUM;
3483         sign = 1;
3484         pnum_head = p;
3485       }
3486       else {
3487         r = ONIGERR_INVALID_GROUP_NAME;
3488       }
3489     }
3490     else if (!ONIGENC_IS_CODE_WORD(enc, c)) {
3491       r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME;
3492     }
3493   }
3494
3495   if (r == 0) {
3496     while (!PEND) {
3497       name_end = p;
3498       PFETCH_S(c);
3499       if (c == end_code || c == ')') {
3500         if (*num_type != IS_NOT_NUM && digit_count == 0)
3501           r = ONIGERR_INVALID_GROUP_NAME;
3502         break;
3503       }
3504
3505       if (*num_type != IS_NOT_NUM) {
3506         if (IS_CODE_DIGIT_ASCII(enc, c)) {
3507           digit_count++;
3508         }
3509         else {
3510           if (!ONIGENC_IS_CODE_WORD(enc, c))
3511             r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME;
3512           else
3513             r = ONIGERR_INVALID_GROUP_NAME;
3514
3515           *num_type = IS_NOT_NUM;
3516         }
3517       }
3518       else {
3519         if (!ONIGENC_IS_CODE_WORD(enc, c)) {
3520           r = ONIGERR_INVALID_CHAR_IN_GROUP_NAME;
3521         }
3522       }
3523     }
3524
3525     if (c != end_code) {
3526       r = ONIGERR_INVALID_GROUP_NAME;
3527       goto err;
3528     }
3529
3530     if (*num_type != IS_NOT_NUM) {
3531       *rback_num = onig_scan_unsigned_number(&pnum_head, name_end, enc);
3532       if (*rback_num < 0) return ONIGERR_TOO_BIG_NUMBER;
3533       else if (*rback_num == 0) {
3534         if (*num_type == IS_REL_NUM) {
3535           r = ONIGERR_INVALID_GROUP_NAME;
3536           goto err;
3537         }
3538       }
3539
3540       *rback_num *= sign;
3541     }
3542
3543     *rname_end = name_end;
3544     *src = p;
3545     return 0;
3546   }
3547   else {
3548     while (!PEND) {
3549       name_end = p;
3550       PFETCH_S(c);
3551       if (c == end_code || c == ')')
3552         break;
3553     }
3554     if (PEND)
3555       name_end = end;
3556
3557   err:
3558     onig_scan_env_set_error_string(env, r, *src, name_end);
3559     return r;
3560   }
3561 }
3562
3563 static void
3564 CC_ESC_WARN(ScanEnv* env, UChar *c)
3565 {
3566   if (onig_warn == onig_null_warn) return ;
3567
3568   if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_WARN_CC_OP_NOT_ESCAPED) &&
3569       IS_SYNTAX_BV(env->syntax, ONIG_SYN_BACKSLASH_ESCAPE_IN_CC)) {
3570     UChar buf[WARN_BUFSIZE];
3571     onig_snprintf_with_pattern(buf, WARN_BUFSIZE, env->enc,
3572                                env->pattern, env->pattern_end,
3573                                (UChar* )"character class has '%s' without escape",
3574                                c);
3575     (*onig_warn)((char* )buf);
3576   }
3577 }
3578
3579 static void
3580 CLOSE_BRACKET_WITHOUT_ESC_WARN(ScanEnv* env, UChar* c)
3581 {
3582   if (onig_warn == onig_null_warn) return ;
3583
3584   if (IS_SYNTAX_BV((env)->syntax, ONIG_SYN_WARN_CC_OP_NOT_ESCAPED)) {
3585     UChar buf[WARN_BUFSIZE];
3586     onig_snprintf_with_pattern(buf, WARN_BUFSIZE, (env)->enc,
3587                          (env)->pattern, (env)->pattern_end,
3588                          (UChar* )"regular expression has '%s' without escape", c);
3589     (*onig_warn)((char* )buf);
3590   }
3591 }
3592
3593 static UChar*
3594 find_str_position(OnigCodePoint s[], int n, UChar* from, UChar* to,
3595                   UChar **next, OnigEncoding enc)
3596 {
3597   int i;
3598   OnigCodePoint x;
3599   UChar *q;
3600   UChar *p = from;
3601
3602   while (p < to) {
3603     x = ONIGENC_MBC_TO_CODE(enc, p, to);
3604     q = p + enclen(enc, p);
3605     if (x == s[0]) {
3606       for (i = 1; i < n && q < to; i++) {
3607         x = ONIGENC_MBC_TO_CODE(enc, q, to);
3608         if (x != s[i]) break;
3609         q += enclen(enc, q);
3610       }
3611       if (i >= n) {
3612         if (IS_NOT_NULL(next))
3613           *next = q;
3614         return p;
3615       }
3616     }
3617     p = q;
3618   }
3619   return NULL_UCHARP;
3620 }
3621
3622 static int
3623 str_exist_check_with_esc(OnigCodePoint s[], int n, UChar* from, UChar* to,
3624                          OnigCodePoint bad, OnigEncoding enc, OnigSyntaxType* syn)
3625 {
3626   int i, in_esc;
3627   OnigCodePoint x;
3628   UChar *q;
3629   UChar *p = from;
3630
3631   in_esc = 0;
3632   while (p < to) {
3633     if (in_esc) {
3634       in_esc = 0;
3635       p += enclen(enc, p);
3636     }
3637     else {
3638       x = ONIGENC_MBC_TO_CODE(enc, p, to);
3639       q = p + enclen(enc, p);
3640       if (x == s[0]) {
3641         for (i = 1; i < n && q < to; i++) {
3642           x = ONIGENC_MBC_TO_CODE(enc, q, to);
3643           if (x != s[i]) break;
3644           q += enclen(enc, q);
3645         }
3646         if (i >= n) return 1;
3647         p += enclen(enc, p);
3648       }
3649       else {
3650         x = ONIGENC_MBC_TO_CODE(enc, p, to);
3651         if (x == bad) return 0;
3652         else if (x == MC_ESC(syn)) in_esc = 1;
3653         p = q;
3654       }
3655     }
3656   }
3657   return 0;
3658 }
3659
3660 static int
3661 fetch_token_in_cc(OnigToken* tok, UChar** src, UChar* end, ScanEnv* env)
3662 {
3663   int num;
3664   OnigCodePoint c, c2;
3665   OnigSyntaxType* syn = env->syntax;
3666   OnigEncoding enc = env->enc;
3667   UChar* prev;
3668   UChar* p = *src;
3669   PFETCH_READY;
3670
3671   if (PEND) {
3672     tok->type = TK_EOT;
3673     return tok->type;
3674   }
3675
3676   PFETCH(c);
3677   tok->type = TK_CHAR;
3678   tok->base = 0;
3679   tok->u.c  = c;
3680   tok->escaped = 0;
3681
3682   if (c == ']') {
3683     tok->type = TK_CC_CLOSE;
3684   }
3685   else if (c == '-') {
3686     tok->type = TK_CC_RANGE;
3687   }
3688   else if (c == MC_ESC(syn)) {
3689     if (! IS_SYNTAX_BV(syn, ONIG_SYN_BACKSLASH_ESCAPE_IN_CC))
3690       goto end;
3691
3692     if (PEND) return ONIGERR_END_PATTERN_AT_ESCAPE;
3693
3694     PFETCH(c);
3695     tok->escaped = 1;
3696     tok->u.c = c;
3697     switch (c) {
3698     case 'w':
3699       tok->type = TK_CHAR_TYPE;
3700       tok->u.prop.ctype = ONIGENC_CTYPE_WORD;
3701       tok->u.prop.not   = 0;
3702       break;
3703     case 'W':
3704       tok->type = TK_CHAR_TYPE;
3705       tok->u.prop.ctype = ONIGENC_CTYPE_WORD;
3706       tok->u.prop.not   = 1;
3707       break;
3708     case 'd':
3709       tok->type = TK_CHAR_TYPE;
3710       tok->u.prop.ctype = ONIGENC_CTYPE_DIGIT;
3711       tok->u.prop.not   = 0;
3712       break;
3713     case 'D':
3714       tok->type = TK_CHAR_TYPE;
3715       tok->u.prop.ctype = ONIGENC_CTYPE_DIGIT;
3716       tok->u.prop.not   = 1;
3717       break;
3718     case 's':
3719       tok->type = TK_CHAR_TYPE;
3720       tok->u.prop.ctype = ONIGENC_CTYPE_SPACE;
3721       tok->u.prop.not   = 0;
3722       break;
3723     case 'S':
3724       tok->type = TK_CHAR_TYPE;
3725       tok->u.prop.ctype = ONIGENC_CTYPE_SPACE;
3726       tok->u.prop.not   = 1;
3727       break;
3728     case 'h':
3729       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_H_XDIGIT)) break;
3730       tok->type = TK_CHAR_TYPE;
3731       tok->u.prop.ctype = ONIGENC_CTYPE_XDIGIT;
3732       tok->u.prop.not   = 0;
3733       break;
3734     case 'H':
3735       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_H_XDIGIT)) break;
3736       tok->type = TK_CHAR_TYPE;
3737       tok->u.prop.ctype = ONIGENC_CTYPE_XDIGIT;
3738       tok->u.prop.not   = 1;
3739       break;
3740
3741     case 'p':
3742     case 'P':
3743       if (PEND) break;
3744
3745       c2 = PPEEK;
3746       if (c2 == '{' &&
3747           IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY)) {
3748         PINC;
3749         tok->type = TK_CHAR_PROPERTY;
3750         tok->u.prop.not = (c == 'P' ? 1 : 0);
3751
3752         if (!PEND && IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT)) {
3753           PFETCH(c2);
3754           if (c2 == '^') {
3755             tok->u.prop.not = (tok->u.prop.not == 0 ? 1 : 0);
3756           }
3757           else
3758             PUNFETCH;
3759         }
3760       }
3761       break;
3762
3763     case 'o':
3764       if (PEND) break;
3765
3766       prev = p;
3767       if (PPEEK_IS('{') && IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_O_BRACE_OCTAL)) {
3768         PINC;
3769         num = scan_unsigned_octal_number(&p, end, 11, enc);
3770         if (num < 0) return ONIGERR_TOO_BIG_WIDE_CHAR_VALUE;
3771         if (!PEND) {
3772           c2 = PPEEK;
3773           if (IS_CODE_DIGIT_ASCII(enc, c2))
3774             return ONIGERR_TOO_LONG_WIDE_CHAR_VALUE;
3775         }
3776
3777         if (p > prev + enclen(enc, prev) && !PEND && (PPEEK_IS('}'))) {
3778           PINC;
3779           tok->type   = TK_CODE_POINT;
3780           tok->base   = 8;
3781           tok->u.code = (OnigCodePoint )num;
3782         }
3783         else {
3784           /* can't read nothing or invalid format */
3785           p = prev;
3786         }
3787       }
3788       break;
3789
3790     case 'x':
3791       if (PEND) break;
3792
3793       prev = p;
3794       if (PPEEK_IS('{') && IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_X_BRACE_HEX8)) {
3795         PINC;
3796         num = scan_unsigned_hexadecimal_number(&p, end, 0, 8, enc);
3797         if (num < 0) {
3798           if (num == ONIGERR_TOO_BIG_NUMBER)
3799             return ONIGERR_TOO_BIG_WIDE_CHAR_VALUE;
3800           else
3801             return num;
3802         }
3803         if (!PEND) {
3804           c2 = PPEEK;
3805           if (IS_CODE_XDIGIT_ASCII(enc, c2))
3806             return ONIGERR_TOO_LONG_WIDE_CHAR_VALUE;
3807         }
3808
3809         if (p > prev + enclen(enc, prev) && !PEND && (PPEEK_IS('}'))) {
3810           PINC;
3811           tok->type   = TK_CODE_POINT;
3812           tok->base   = 16;
3813           tok->u.code = (OnigCodePoint )num;
3814         }
3815         else {
3816           /* can't read nothing or invalid format */
3817           p = prev;
3818         }
3819       }
3820       else if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_X_HEX2)) {
3821         num = scan_unsigned_hexadecimal_number(&p, end, 0, 2, enc);
3822         if (num < 0) return num;
3823         if (p == prev) {  /* can't read nothing. */
3824           num = 0; /* but, it's not error */
3825         }
3826         tok->type = TK_RAW_BYTE;
3827         tok->base = 16;
3828         tok->u.c  = num;
3829       }
3830       break;
3831
3832     case 'u':
3833       if (PEND) break;
3834
3835       prev = p;
3836       if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_U_HEX4)) {
3837         num = scan_unsigned_hexadecimal_number(&p, end, 4, 4, enc);
3838         if (num < 0) return num;
3839         if (p == prev) {  /* can't read nothing. */
3840           num = 0; /* but, it's not error */
3841         }
3842         tok->type   = TK_CODE_POINT;
3843         tok->base   = 16;
3844         tok->u.code = (OnigCodePoint )num;
3845       }
3846       break;
3847
3848     case '0':
3849     case '1': case '2': case '3': case '4': case '5': case '6': case '7':
3850       if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_OCTAL3)) {
3851         PUNFETCH;
3852         prev = p;
3853         num = scan_unsigned_octal_number(&p, end, 3, enc);
3854         if (num < 0 || num >= 256) return ONIGERR_TOO_BIG_NUMBER;
3855         if (p == prev) {  /* can't read nothing. */
3856           num = 0; /* but, it's not error */
3857         }
3858         tok->type = TK_RAW_BYTE;
3859         tok->base = 8;
3860         tok->u.c  = num;
3861       }
3862       break;
3863
3864     default:
3865       PUNFETCH;
3866       num = fetch_escaped_value(&p, end, env, &c2);
3867       if (num < 0) return num;
3868       if (tok->u.c != c2) {
3869         tok->u.code = c2;
3870         tok->type   = TK_CODE_POINT;
3871       }
3872       break;
3873     }
3874   }
3875   else if (c == '[') {
3876     if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_POSIX_BRACKET) && (PPEEK_IS(':'))) {
3877       OnigCodePoint send[] = { (OnigCodePoint )':', (OnigCodePoint )']' };
3878       tok->backp = p; /* point at '[' is read */
3879       PINC;
3880       if (str_exist_check_with_esc(send, 2, p, end,
3881                                    (OnigCodePoint )']', enc, syn)) {
3882         tok->type = TK_POSIX_BRACKET_OPEN;
3883       }
3884       else {
3885         PUNFETCH;
3886         goto cc_in_cc;
3887       }
3888     }
3889     else {
3890     cc_in_cc:
3891       if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_CCLASS_SET_OP)) {
3892         tok->type = TK_CC_CC_OPEN;
3893       }
3894       else {
3895         CC_ESC_WARN(env, (UChar* )"[");
3896       }
3897     }
3898   }
3899   else if (c == '&') {
3900     if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_CCLASS_SET_OP) &&
3901         !PEND && (PPEEK_IS('&'))) {
3902       PINC;
3903       tok->type = TK_CC_AND;
3904     }
3905   }
3906
3907  end:
3908   *src = p;
3909   return tok->type;
3910 }
3911
3912 static int
3913 fetch_token(OnigToken* tok, UChar** src, UChar* end, ScanEnv* env)
3914 {
3915   int r, num;
3916   OnigCodePoint c;
3917   OnigEncoding enc = env->enc;
3918   OnigSyntaxType* syn = env->syntax;
3919   UChar* prev;
3920   UChar* p = *src;
3921   PFETCH_READY;
3922
3923  start:
3924   if (PEND) {
3925     tok->type = TK_EOT;
3926     return tok->type;
3927   }
3928
3929   tok->type  = TK_STRING;
3930   tok->base  = 0;
3931   tok->backp = p;
3932
3933   PFETCH(c);
3934   if (IS_MC_ESC_CODE(c, syn)) {
3935     if (PEND) return ONIGERR_END_PATTERN_AT_ESCAPE;
3936
3937     tok->backp = p;
3938     PFETCH(c);
3939
3940     tok->u.c = c;
3941     tok->escaped = 1;
3942     switch (c) {
3943     case '*':
3944       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_ASTERISK_ZERO_INF)) break;
3945       tok->type = TK_OP_REPEAT;
3946       tok->u.repeat.lower = 0;
3947       tok->u.repeat.upper = REPEAT_INFINITE;
3948       goto greedy_check;
3949       break;
3950
3951     case '+':
3952       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_PLUS_ONE_INF)) break;
3953       tok->type = TK_OP_REPEAT;
3954       tok->u.repeat.lower = 1;
3955       tok->u.repeat.upper = REPEAT_INFINITE;
3956       goto greedy_check;
3957       break;
3958
3959     case '?':
3960       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_QMARK_ZERO_ONE)) break;
3961       tok->type = TK_OP_REPEAT;
3962       tok->u.repeat.lower = 0;
3963       tok->u.repeat.upper = 1;
3964     greedy_check:
3965       if (!PEND && PPEEK_IS('?') &&
3966           IS_SYNTAX_OP(syn, ONIG_SYN_OP_QMARK_NON_GREEDY)) {
3967         PFETCH(c);
3968         tok->u.repeat.greedy     = 0;
3969         tok->u.repeat.possessive = 0;
3970       }
3971       else {
3972       possessive_check:
3973         if (!PEND && PPEEK_IS('+') &&
3974             ((IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_PLUS_POSSESSIVE_REPEAT) &&
3975               tok->type != TK_INTERVAL)  ||
3976              (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_PLUS_POSSESSIVE_INTERVAL) &&
3977               tok->type == TK_INTERVAL))) {
3978           PFETCH(c);
3979           tok->u.repeat.greedy     = 1;
3980           tok->u.repeat.possessive = 1;
3981         }
3982         else {
3983           tok->u.repeat.greedy     = 1;
3984           tok->u.repeat.possessive = 0;
3985         }
3986       }
3987       break;
3988
3989     case '{':
3990       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_BRACE_INTERVAL)) break;
3991       r = fetch_range_quantifier(&p, end, tok, env);
3992       if (r < 0) return r;  /* error */
3993       if (r == 0) goto greedy_check;
3994       else if (r == 2) { /* {n} */
3995         if (IS_SYNTAX_BV(syn, ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY))
3996           goto possessive_check;
3997
3998         goto greedy_check;
3999       }
4000       /* r == 1 : normal char */
4001       break;
4002
4003     case '|':
4004       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_VBAR_ALT)) break;
4005       tok->type = TK_ALT;
4006       break;
4007
4008     case '(':
4009       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_LPAREN_SUBEXP)) break;
4010       tok->type = TK_SUBEXP_OPEN;
4011       break;
4012
4013     case ')':
4014       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_LPAREN_SUBEXP)) break;
4015       tok->type = TK_SUBEXP_CLOSE;
4016       break;
4017
4018     case 'w':
4019       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_W_WORD)) break;
4020       tok->type = TK_CHAR_TYPE;
4021       tok->u.prop.ctype = ONIGENC_CTYPE_WORD;
4022       tok->u.prop.not   = 0;
4023       break;
4024
4025     case 'W':
4026       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_W_WORD)) break;
4027       tok->type = TK_CHAR_TYPE;
4028       tok->u.prop.ctype = ONIGENC_CTYPE_WORD;
4029       tok->u.prop.not   = 1;
4030       break;
4031
4032     case 'b':
4033       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_B_WORD_BOUND)) break;
4034       tok->type = TK_ANCHOR;
4035       tok->u.anchor = ANCHOR_WORD_BOUNDARY;
4036       break;
4037
4038     case 'B':
4039       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_B_WORD_BOUND)) break;
4040       tok->type = TK_ANCHOR;
4041       tok->u.anchor = ANCHOR_NO_WORD_BOUNDARY;
4042       break;
4043
4044     case 'y':
4045       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP2_ESC_X_Y_GRAPHEME_CLUSTER)) break;
4046       tok->type = TK_ANCHOR;
4047       tok->u.anchor = ANCHOR_EXTENDED_GRAPHEME_CLUSTER_BOUNDARY;
4048       break;
4049
4050     case 'Y':
4051       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP2_ESC_X_Y_GRAPHEME_CLUSTER)) break;
4052       tok->type = TK_ANCHOR;
4053       tok->u.anchor = ANCHOR_NO_EXTENDED_GRAPHEME_CLUSTER_BOUNDARY;
4054       break;
4055
4056 #ifdef USE_WORD_BEGIN_END
4057     case '<':
4058       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END)) break;
4059       tok->type = TK_ANCHOR;
4060       tok->u.anchor = ANCHOR_WORD_BEGIN;
4061       break;
4062
4063     case '>':
4064       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END)) break;
4065       tok->type = TK_ANCHOR;
4066       tok->u.anchor = ANCHOR_WORD_END;
4067       break;
4068 #endif
4069
4070     case 's':
4071       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_S_WHITE_SPACE)) break;
4072       tok->type = TK_CHAR_TYPE;
4073       tok->u.prop.ctype = ONIGENC_CTYPE_SPACE;
4074       tok->u.prop.not   = 0;
4075       break;
4076
4077     case 'S':
4078       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_S_WHITE_SPACE)) break;
4079       tok->type = TK_CHAR_TYPE;
4080       tok->u.prop.ctype = ONIGENC_CTYPE_SPACE;
4081       tok->u.prop.not   = 1;
4082       break;
4083
4084     case 'd':
4085       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_D_DIGIT)) break;
4086       tok->type = TK_CHAR_TYPE;
4087       tok->u.prop.ctype = ONIGENC_CTYPE_DIGIT;
4088       tok->u.prop.not   = 0;
4089       break;
4090
4091     case 'D':
4092       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_D_DIGIT)) break;
4093       tok->type = TK_CHAR_TYPE;
4094       tok->u.prop.ctype = ONIGENC_CTYPE_DIGIT;
4095       tok->u.prop.not   = 1;
4096       break;
4097
4098     case 'h':
4099       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_H_XDIGIT)) break;
4100       tok->type = TK_CHAR_TYPE;
4101       tok->u.prop.ctype = ONIGENC_CTYPE_XDIGIT;
4102       tok->u.prop.not   = 0;
4103       break;
4104
4105     case 'H':
4106       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_H_XDIGIT)) break;
4107       tok->type = TK_CHAR_TYPE;
4108       tok->u.prop.ctype = ONIGENC_CTYPE_XDIGIT;
4109       tok->u.prop.not   = 1;
4110       break;
4111
4112     case 'K':
4113       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_CAPITAL_K_KEEP)) break;
4114       tok->type = TK_KEEP;
4115       break;
4116
4117     case 'R':
4118       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_CAPITAL_R_GENERAL_NEWLINE)) break;
4119       tok->type = TK_GENERAL_NEWLINE;
4120       break;
4121
4122     case 'N':
4123       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_CAPITAL_N_O_SUPER_DOT)) break;
4124       tok->type = TK_NO_NEWLINE;
4125       break;
4126
4127     case 'O':
4128       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_CAPITAL_N_O_SUPER_DOT)) break;
4129       tok->type = TK_TRUE_ANYCHAR;
4130       break;
4131
4132     case 'X':
4133       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_X_Y_GRAPHEME_CLUSTER)) break;
4134       tok->type = TK_EXTENDED_GRAPHEME_CLUSTER;
4135       break;
4136
4137     case 'A':
4138       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_AZ_BUF_ANCHOR)) break;
4139     begin_buf:
4140       tok->type = TK_ANCHOR;
4141       tok->u.subtype = ANCHOR_BEGIN_BUF;
4142       break;
4143
4144     case 'Z':
4145       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_AZ_BUF_ANCHOR)) break;
4146       tok->type = TK_ANCHOR;
4147       tok->u.subtype = ANCHOR_SEMI_END_BUF;
4148       break;
4149
4150     case 'z':
4151       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_AZ_BUF_ANCHOR)) break;
4152     end_buf:
4153       tok->type = TK_ANCHOR;
4154       tok->u.subtype = ANCHOR_END_BUF;
4155       break;
4156
4157     case 'G':
4158       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_CAPITAL_G_BEGIN_ANCHOR)) break;
4159       tok->type = TK_ANCHOR;
4160       tok->u.subtype = ANCHOR_BEGIN_POSITION;
4161       break;
4162
4163     case '`':
4164       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_GNU_BUF_ANCHOR)) break;
4165       goto begin_buf;
4166       break;
4167
4168     case '\'':
4169       if (! IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_GNU_BUF_ANCHOR)) break;
4170       goto end_buf;
4171       break;
4172
4173     case 'o':
4174       if (PEND) break;
4175
4176       prev = p;
4177       if (PPEEK_IS('{') && IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_O_BRACE_OCTAL)) {
4178         PINC;
4179         num = scan_unsigned_octal_number(&p, end, 11, enc);
4180         if (num < 0) return ONIGERR_TOO_BIG_WIDE_CHAR_VALUE;
4181         if (!PEND) {
4182           if (IS_CODE_DIGIT_ASCII(enc, PPEEK))
4183             return ONIGERR_TOO_LONG_WIDE_CHAR_VALUE;
4184         }
4185
4186         if ((p > prev + enclen(enc, prev)) && !PEND && PPEEK_IS('}')) {
4187           PINC;
4188           tok->type   = TK_CODE_POINT;
4189           tok->u.code = (OnigCodePoint )num;
4190         }
4191         else {
4192           /* can't read nothing or invalid format */
4193           p = prev;
4194         }
4195       }
4196       break;
4197
4198     case 'x':
4199       if (PEND) break;
4200
4201       prev = p;
4202       if (PPEEK_IS('{') && IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_X_BRACE_HEX8)) {
4203         PINC;
4204         num = scan_unsigned_hexadecimal_number(&p, end, 0, 8, enc);
4205         if (num < 0) {
4206           if (num == ONIGERR_TOO_BIG_NUMBER)
4207             return ONIGERR_TOO_BIG_WIDE_CHAR_VALUE;
4208           else
4209             return num;
4210         }
4211         if (!PEND) {
4212           if (IS_CODE_XDIGIT_ASCII(enc, PPEEK))
4213             return ONIGERR_TOO_LONG_WIDE_CHAR_VALUE;
4214         }
4215
4216         if ((p > prev + enclen(enc, prev)) && !PEND && PPEEK_IS('}')) {
4217           PINC;
4218           tok->type   = TK_CODE_POINT;
4219           tok->u.code = (OnigCodePoint )num;
4220         }
4221         else {
4222           /* can't read nothing or invalid format */
4223           p = prev;
4224         }
4225       }
4226       else if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_X_HEX2)) {
4227         num = scan_unsigned_hexadecimal_number(&p, end, 0, 2, enc);
4228         if (num < 0) return num;
4229         if (p == prev) {  /* can't read nothing. */
4230           num = 0; /* but, it's not error */
4231         }
4232         tok->type = TK_RAW_BYTE;
4233         tok->base = 16;
4234         tok->u.c  = num;
4235       }
4236       break;
4237
4238     case 'u':
4239       if (PEND) break;
4240
4241       prev = p;
4242       if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_U_HEX4)) {
4243         num = scan_unsigned_hexadecimal_number(&p, end, 4, 4, enc);
4244         if (num < 0) return num;
4245         if (p == prev) {  /* can't read nothing. */
4246           num = 0; /* but, it's not error */
4247         }
4248         tok->type   = TK_CODE_POINT;
4249         tok->base   = 16;
4250         tok->u.code = (OnigCodePoint )num;
4251       }
4252       break;
4253
4254     case '1': case '2': case '3': case '4':
4255     case '5': case '6': case '7': case '8': case '9':
4256       PUNFETCH;
4257       prev = p;
4258       num = onig_scan_unsigned_number(&p, end, enc);
4259       if (num < 0 || num > ONIG_MAX_BACKREF_NUM) {
4260         goto skip_backref;
4261       }
4262
4263       if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_DECIMAL_BACKREF) &&
4264           (num <= env->num_mem || num <= 9)) { /* This spec. from GNU regex */
4265         if (IS_SYNTAX_BV(syn, ONIG_SYN_STRICT_CHECK_BACKREF)) {
4266           if (num > env->num_mem || IS_NULL(SCANENV_MEMENV(env)[num].node))
4267             return ONIGERR_INVALID_BACKREF;
4268         }
4269
4270         tok->type = TK_BACKREF;
4271         tok->u.backref.num     = 1;
4272         tok->u.backref.ref1    = num;
4273         tok->u.backref.by_name = 0;
4274 #ifdef USE_BACKREF_WITH_LEVEL
4275         tok->u.backref.exist_level = 0;
4276 #endif
4277         break;
4278       }
4279
4280     skip_backref:
4281       if (c == '8' || c == '9') {
4282         /* normal char */
4283         p = prev; PINC;
4284         break;
4285       }
4286
4287       p = prev;
4288       /* fall through */
4289     case '0':
4290       if (IS_SYNTAX_OP(syn, ONIG_SYN_OP_ESC_OCTAL3)) {
4291         prev = p;
4292         num = scan_unsigned_octal_number(&p, end, (c == '0' ? 2:3), enc);
4293         if (num < 0 || num >= 256) return ONIGERR_TOO_BIG_NUMBER;
4294         if (p == prev) {  /* can't read nothing. */
4295           num = 0; /* but, it's not error */
4296         }
4297         tok->type = TK_RAW_BYTE;
4298         tok->base = 8;
4299         tok->u.c  = num;
4300       }
4301       else if (c != '0') {
4302         PINC;
4303       }
4304       break;
4305
4306     case 'k':
4307       if (!PEND && IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_K_NAMED_BACKREF)) {
4308         PFETCH(c);
4309         if (c == '<' || c == '\'') {
4310           UChar* name_end;
4311           int* backs;
4312           int back_num;
4313           enum REF_NUM num_type;
4314
4315           prev = p;
4316
4317 #ifdef USE_BACKREF_WITH_LEVEL
4318           name_end = NULL_UCHARP; /* no need. escape gcc warning. */
4319           r = fetch_name_with_level((OnigCodePoint )c, &p, end, &name_end,
4320                                  env, &back_num, &tok->u.backref.level, &num_type);
4321           if (r == 1) tok->u.backref.exist_level = 1;
4322           else        tok->u.backref.exist_level = 0;
4323 #else
4324           r = fetch_name(c, &p, end, &name_end, env, &back_num, &num_type, 1);
4325 #endif
4326           if (r < 0) return r;
4327
4328           if (num_type != IS_NOT_NUM) {
4329             if (num_type == IS_REL_NUM) {
4330               back_num = backref_rel_to_abs(back_num, env);
4331             }
4332             if (back_num <= 0)
4333               return ONIGERR_INVALID_BACKREF;
4334
4335             if (IS_SYNTAX_BV(syn, ONIG_SYN_STRICT_CHECK_BACKREF)) {
4336               if (back_num > env->num_mem ||
4337                   IS_NULL(SCANENV_MEMENV(env)[back_num].node))
4338                 return ONIGERR_INVALID_BACKREF;
4339             }
4340             tok->type = TK_BACKREF;
4341             tok->u.backref.by_name = 0;
4342             tok->u.backref.num  = 1;
4343             tok->u.backref.ref1 = back_num;
4344           }
4345           else {
4346             num = onig_name_to_group_numbers(env->reg, prev, name_end, &backs);
4347             if (num <= 0) {
4348               onig_scan_env_set_error_string(env,
4349                         ONIGERR_UNDEFINED_NAME_REFERENCE, prev, name_end);
4350               return ONIGERR_UNDEFINED_NAME_REFERENCE;
4351             }
4352             if (IS_SYNTAX_BV(syn, ONIG_SYN_STRICT_CHECK_BACKREF)) {
4353               int i;
4354               for (i = 0; i < num; i++) {
4355                 if (backs[i] > env->num_mem ||
4356                     IS_NULL(SCANENV_MEMENV(env)[backs[i]].node))
4357                   return ONIGERR_INVALID_BACKREF;
4358               }
4359             }
4360
4361             tok->type = TK_BACKREF;
4362             tok->u.backref.by_name = 1;
4363             if (num == 1) {
4364               tok->u.backref.num  = 1;
4365               tok->u.backref.ref1 = backs[0];
4366             }
4367             else {
4368               tok->u.backref.num  = num;
4369               tok->u.backref.refs = backs;
4370             }
4371           }
4372         }
4373         else
4374           PUNFETCH;
4375       }
4376       break;
4377
4378 #ifdef USE_CALL
4379     case 'g':
4380       if (!PEND && IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_G_SUBEXP_CALL)) {
4381         PFETCH(c);
4382         if (c == '<' || c == '\'') {
4383           int gnum;
4384           UChar* name_end;
4385           enum REF_NUM num_type;
4386
4387           prev = p;
4388           r = fetch_name((OnigCodePoint )c, &p, end, &name_end, env,
4389                          &gnum, &num_type, 1);
4390           if (r < 0) return r;
4391
4392           if (num_type != IS_NOT_NUM) {
4393             if (num_type == IS_REL_NUM) {
4394               gnum = backref_rel_to_abs(gnum, env);
4395               if (gnum < 0)
4396                 return ONIGERR_UNDEFINED_GROUP_REFERENCE;
4397             }
4398             tok->u.call.by_number = 1;
4399             tok->u.call.gnum      = gnum;
4400           }
4401           else {
4402             tok->u.call.by_number = 0;
4403             tok->u.call.gnum      = 0;
4404           }
4405
4406           tok->type = TK_CALL;
4407           tok->u.call.name     = prev;
4408           tok->u.call.name_end = name_end;
4409         }
4410         else
4411           PUNFETCH;
4412       }
4413       break;
4414 #endif
4415
4416     case 'Q':
4417       if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_CAPITAL_Q_QUOTE)) {
4418         tok->type = TK_QUOTE_OPEN;
4419       }
4420       break;
4421
4422     case 'p':
4423     case 'P':
4424       if (!PEND && PPEEK_IS('{') &&
4425           IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY)) {
4426         PINC;
4427         tok->type = TK_CHAR_PROPERTY;
4428         tok->u.prop.not = (c == 'P' ? 1 : 0);
4429
4430         if (!PEND &&
4431             IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT)) {
4432           PFETCH(c);
4433           if (c == '^') {
4434             tok->u.prop.not = (tok->u.prop.not == 0 ? 1 : 0);
4435           }
4436           else
4437             PUNFETCH;
4438         }
4439       }
4440       break;
4441
4442     default:
4443       {
4444         OnigCodePoint c2;
4445
4446         PUNFETCH;
4447         num = fetch_escaped_value(&p, end, env, &c2);
4448         if (num < 0) return num;
4449         /* set_raw: */
4450         if (tok->u.c != c2) {
4451           tok->type = TK_CODE_POINT;
4452           tok->u.code = c2;
4453         }
4454         else { /* string */
4455           p = tok->backp + enclen(enc, tok->backp);
4456         }
4457       }
4458       break;
4459     }
4460   }
4461   else {
4462     tok->u.c = c;
4463     tok->escaped = 0;
4464
4465 #ifdef USE_VARIABLE_META_CHARS
4466     if ((c != ONIG_INEFFECTIVE_META_CHAR) &&
4467         IS_SYNTAX_OP(syn, ONIG_SYN_OP_VARIABLE_META_CHARACTERS)) {
4468       if (c == MC_ANYCHAR(syn))
4469         goto any_char;
4470       else if (c == MC_ANYTIME(syn))
4471         goto anytime;
4472       else if (c == MC_ZERO_OR_ONE_TIME(syn))
4473         goto zero_or_one_time;
4474       else if (c == MC_ONE_OR_MORE_TIME(syn))
4475         goto one_or_more_time;
4476       else if (c == MC_ANYCHAR_ANYTIME(syn)) {
4477         tok->type = TK_ANYCHAR_ANYTIME;
4478         goto out;
4479       }
4480     }
4481 #endif
4482
4483     switch (c) {
4484     case '.':
4485       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_DOT_ANYCHAR)) break;
4486 #ifdef USE_VARIABLE_META_CHARS
4487     any_char:
4488 #endif
4489       tok->type = TK_ANYCHAR;
4490       break;
4491
4492     case '*':
4493       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_ASTERISK_ZERO_INF)) break;
4494 #ifdef USE_VARIABLE_META_CHARS
4495     anytime:
4496 #endif
4497       tok->type = TK_OP_REPEAT;
4498       tok->u.repeat.lower = 0;
4499       tok->u.repeat.upper = REPEAT_INFINITE;
4500       goto greedy_check;
4501       break;
4502
4503     case '+':
4504       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_PLUS_ONE_INF)) break;
4505 #ifdef USE_VARIABLE_META_CHARS
4506     one_or_more_time:
4507 #endif
4508       tok->type = TK_OP_REPEAT;
4509       tok->u.repeat.lower = 1;
4510       tok->u.repeat.upper = REPEAT_INFINITE;
4511       goto greedy_check;
4512       break;
4513
4514     case '?':
4515       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_QMARK_ZERO_ONE)) break;
4516 #ifdef USE_VARIABLE_META_CHARS
4517     zero_or_one_time:
4518 #endif
4519       tok->type = TK_OP_REPEAT;
4520       tok->u.repeat.lower = 0;
4521       tok->u.repeat.upper = 1;
4522       goto greedy_check;
4523       break;
4524
4525     case '{':
4526       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_BRACE_INTERVAL)) break;
4527       r = fetch_range_quantifier(&p, end, tok, env);
4528       if (r < 0) return r;  /* error */
4529       if (r == 0) goto greedy_check;
4530       else if (r == 2) { /* {n} */
4531         if (IS_SYNTAX_BV(syn, ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY))
4532           goto possessive_check;
4533
4534         goto greedy_check;
4535       }
4536       /* r == 1 : normal char */
4537       break;
4538
4539     case '|':
4540       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_VBAR_ALT)) break;
4541       tok->type = TK_ALT;
4542       break;
4543
4544     case '(':
4545       if (!PEND && PPEEK_IS('?') &&
4546           IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_QMARK_GROUP_EFFECT)) {
4547         PINC;
4548         if (! PEND) {
4549           c = PPEEK;
4550           if (c == '#') {
4551             PFETCH(c);
4552             while (1) {
4553               if (PEND) return ONIGERR_END_PATTERN_IN_GROUP;
4554               PFETCH(c);
4555               if (c == MC_ESC(syn)) {
4556                 if (! PEND) PFETCH(c);
4557               }
4558               else {
4559                 if (c == ')') break;
4560               }
4561             }
4562             goto start;
4563           }
4564           else if (IS_SYNTAX_OP2(syn, ONIG_SYN_OP2_QMARK_PERL_SUBEXP_CALL)) {
4565             int gnum;
4566             UChar* name;
4567             UChar* name_end;
4568             enum REF_NUM num_type;
4569
4570             switch (c) {
4571             case '&':
4572               {
4573                 PINC;
4574                 name = p;
4575                 r = fetch_name((OnigCodePoint )'(', &p, end, &name_end, env, &gnum,
4576                                &num_type, 0);
4577                 if (r < 0) return r;
4578
4579                 tok->type = TK_CALL;
4580                 tok->u.call.by_number = 0;
4581                 tok->u.call.gnum      = 0;
4582                 tok->u.call.name      = name;
4583                 tok->u.call.name_end  = name_end;
4584               }
4585               break;
4586
4587             case 'R':
4588               tok->type = TK_CALL;
4589               tok->u.call.by_number = 1;
4590               tok->u.call.gnum      = 0;
4591               tok->u.call.name      = p;
4592               PINC;
4593               if (! PPEEK_IS(')')) return ONIGERR_INVALID_GROUP_NAME;
4594               tok->u.call.name_end  = p;
4595               break;
4596
4597             case '-':
4598             case '+':
4599               goto lparen_qmark_num;
4600               break;
4601             default:
4602               if (! ONIGENC_IS_CODE_DIGIT(enc, c)) goto lparen_qmark_end;
4603
4604             lparen_qmark_num:
4605               {
4606                 name = p;
4607                 r = fetch_name((OnigCodePoint )'(', &p, end, &name_end, env,
4608                                &gnum, &num_type, 1);
4609                 if (r < 0) return r;
4610
4611                 if (num_type == IS_NOT_NUM) {
4612                   return ONIGERR_INVALID_GROUP_NAME;
4613                 }
4614                 else {
4615                   if (num_type == IS_REL_NUM) {
4616                     gnum = backref_rel_to_abs(gnum, env);
4617                     if (gnum < 0)
4618                       return ONIGERR_UNDEFINED_GROUP_REFERENCE;
4619                   }
4620                   tok->u.call.by_number = 1;
4621                   tok->u.call.gnum      = gnum;
4622                 }
4623
4624                 tok->type = TK_CALL;
4625                 tok->u.call.name     = name;
4626                 tok->u.call.name_end = name_end;
4627               }
4628               break;
4629             }
4630           }
4631         }
4632       lparen_qmark_end:
4633         PUNFETCH;
4634       }
4635
4636       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_LPAREN_SUBEXP)) break;
4637       tok->type = TK_SUBEXP_OPEN;
4638       break;
4639
4640     case ')':
4641       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_LPAREN_SUBEXP)) break;
4642       tok->type = TK_SUBEXP_CLOSE;
4643       break;
4644
4645     case '^':
4646       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_LINE_ANCHOR)) break;
4647       tok->type = TK_ANCHOR;
4648       tok->u.subtype = (IS_SINGLELINE(env->options)
4649                         ? ANCHOR_BEGIN_BUF : ANCHOR_BEGIN_LINE);
4650       break;
4651
4652     case '$':
4653       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_LINE_ANCHOR)) break;
4654       tok->type = TK_ANCHOR;
4655       tok->u.subtype = (IS_SINGLELINE(env->options)
4656                         ? ANCHOR_SEMI_END_BUF : ANCHOR_END_LINE);
4657       break;
4658
4659     case '[':
4660       if (! IS_SYNTAX_OP(syn, ONIG_SYN_OP_BRACKET_CC)) break;
4661       tok->type = TK_CC_OPEN;
4662       break;
4663
4664     case ']':
4665       if (*src > env->pattern)   /* /].../ is allowed. */
4666         CLOSE_BRACKET_WITHOUT_ESC_WARN(env, (UChar* )"]");
4667       break;
4668
4669     case '#':
4670       if (IS_EXTEND(env->options)) {
4671         while (!PEND) {
4672           PFETCH(c);
4673           if (ONIGENC_IS_CODE_NEWLINE(enc, c))
4674             break;
4675         }
4676         goto start;
4677         break;
4678       }
4679       break;
4680
4681     case ' ': case '\t': case '\n': case '\r': case '\f':
4682       if (IS_EXTEND(env->options))
4683         goto start;
4684       break;
4685
4686     default:
4687       /* string */
4688       break;
4689     }
4690   }
4691
4692 #ifdef USE_VARIABLE_META_CHARS
4693  out:
4694 #endif
4695   *src = p;
4696   return tok->type;
4697 }
4698
4699 static int
4700 add_ctype_to_cc_by_range(CClassNode* cc, int ctype ARG_UNUSED, int not,
4701                          OnigEncoding enc ARG_UNUSED, OnigCodePoint sb_out,
4702                          const OnigCodePoint mbr[])
4703 {
4704   int i, r;
4705   OnigCodePoint j;
4706
4707   int n = ONIGENC_CODE_RANGE_NUM(mbr);
4708
4709   if (not == 0) {
4710     for (i = 0; i < n; i++) {
4711       for (j  = ONIGENC_CODE_RANGE_FROM(mbr, i);
4712            j <= ONIGENC_CODE_RANGE_TO(mbr, i); j++) {
4713         if (j >= sb_out) {
4714           if (j > ONIGENC_CODE_RANGE_FROM(mbr, i)) {
4715             r = add_code_range_to_buf(&(cc->mbuf), j,
4716                                       ONIGENC_CODE_RANGE_TO(mbr, i));
4717             if (r != 0) return r;
4718             i++;
4719           }
4720
4721           goto sb_end;
4722         }
4723         BITSET_SET_BIT(cc->bs, j);
4724       }
4725     }
4726
4727   sb_end:
4728     for ( ; i < n; i++) {
4729       r = add_code_range_to_buf(&(cc->mbuf),
4730                                 ONIGENC_CODE_RANGE_FROM(mbr, i),
4731                                 ONIGENC_CODE_RANGE_TO(mbr, i));
4732       if (r != 0) return r;
4733     }
4734   }
4735   else {
4736     OnigCodePoint prev = 0;
4737
4738     for (i = 0; i < n; i++) {
4739       for (j = prev; j < ONIGENC_CODE_RANGE_FROM(mbr, i); j++) {
4740         if (j >= sb_out) {
4741           goto sb_end2;
4742         }
4743         BITSET_SET_BIT(cc->bs, j);
4744       }
4745       prev = ONIGENC_CODE_RANGE_TO(mbr, i) + 1;
4746     }
4747     for (j = prev; j < sb_out; j++) {
4748       BITSET_SET_BIT(cc->bs, j);
4749     }
4750
4751   sb_end2:
4752     prev = sb_out;
4753
4754     for (i = 0; i < n; i++) {
4755       if (prev < ONIGENC_CODE_RANGE_FROM(mbr, i)) {
4756         r = add_code_range_to_buf(&(cc->mbuf), prev,
4757                                   ONIGENC_CODE_RANGE_FROM(mbr, i) - 1);
4758         if (r != 0) return r;
4759       }
4760       prev = ONIGENC_CODE_RANGE_TO(mbr, i) + 1;
4761       if (prev == 0) goto end;
4762     }
4763
4764     r = add_code_range_to_buf(&(cc->mbuf), prev, MAX_CODE_POINT);
4765     if (r != 0) return r;
4766   }
4767
4768  end:
4769   return 0;
4770 }
4771
4772 static int
4773 add_ctype_to_cc_by_range_limit(CClassNode* cc, int ctype ARG_UNUSED, int not,
4774                                OnigEncoding enc ARG_UNUSED,
4775                                OnigCodePoint sb_out,
4776                                const OnigCodePoint mbr[], OnigCodePoint limit)
4777 {
4778   int i, r;
4779   OnigCodePoint j;
4780   OnigCodePoint from;
4781   OnigCodePoint to;
4782
4783   int n = ONIGENC_CODE_RANGE_NUM(mbr);
4784
4785   if (not == 0) {
4786     for (i = 0; i < n; i++) {
4787       for (j  = ONIGENC_CODE_RANGE_FROM(mbr, i);
4788            j <= ONIGENC_CODE_RANGE_TO(mbr, i); j++) {
4789         if (j > limit) goto end;
4790         if (j >= sb_out) {
4791           if (j > ONIGENC_CODE_RANGE_FROM(mbr, i)) {
4792             to = ONIGENC_CODE_RANGE_TO(mbr, i);
4793             if (to > limit) to = limit;
4794             r = add_code_range_to_buf(&(cc->mbuf), j, to);
4795             if (r != 0) return r;
4796             i++;
4797           }
4798
4799           goto sb_end;
4800         }
4801         BITSET_SET_BIT(cc->bs, j);
4802       }
4803     }
4804
4805   sb_end:
4806     for ( ; i < n; i++) {
4807       from = ONIGENC_CODE_RANGE_FROM(mbr, i);
4808       to   = ONIGENC_CODE_RANGE_TO(mbr, i);
4809       if (from > limit) break;
4810       if (to   > limit) to = limit;
4811       r = add_code_range_to_buf(&(cc->mbuf), from, to);
4812       if (r != 0) return r;
4813     }
4814   }
4815   else {
4816     OnigCodePoint prev = 0;
4817
4818     for (i = 0; i < n; i++) {
4819       from = ONIGENC_CODE_RANGE_FROM(mbr, i);
4820       if (from > limit) {
4821         for (j = prev; j < sb_out; j++) {
4822           BITSET_SET_BIT(cc->bs, j);
4823         }
4824         goto sb_end2;
4825       }
4826       for (j = prev; j < from; j++) {
4827         if (j >= sb_out) goto sb_end2;
4828         BITSET_SET_BIT(cc->bs, j);
4829       }
4830       prev = ONIGENC_CODE_RANGE_TO(mbr, i);
4831       if (prev > limit) prev = limit;
4832       prev++;
4833       if (prev == 0) goto end;
4834     }
4835     for (j = prev; j < sb_out; j++) {
4836       BITSET_SET_BIT(cc->bs, j);
4837     }
4838
4839   sb_end2:
4840     prev = sb_out;
4841
4842     for (i = 0; i < n; i++) {
4843       from = ONIGENC_CODE_RANGE_FROM(mbr, i);
4844       if (from > limit) goto last;
4845
4846       if (prev < from) {
4847         r = add_code_range_to_buf(&(cc->mbuf), prev, from - 1);
4848         if (r != 0) return r;
4849       }
4850       prev = ONIGENC_CODE_RANGE_TO(mbr, i);
4851       if (prev > limit) prev = limit;
4852       prev++;
4853       if (prev == 0) goto end;
4854     }
4855
4856   last:
4857     r = add_code_range_to_buf(&(cc->mbuf), prev, MAX_CODE_POINT);
4858     if (r != 0) return r;
4859   }
4860
4861  end:
4862   return 0;
4863 }
4864
4865 static int
4866 add_ctype_to_cc(CClassNode* cc, int ctype, int not, ScanEnv* env)
4867 {
4868 #define ASCII_LIMIT    127
4869
4870   int c, r;
4871   int ascii_mode;
4872   const OnigCodePoint *ranges;
4873   OnigCodePoint limit;
4874   OnigCodePoint sb_out;
4875   OnigEncoding enc = env->enc;
4876
4877   ascii_mode = IS_ASCII_MODE_CTYPE_OPTION(ctype, env->options);
4878
4879   r = ONIGENC_GET_CTYPE_CODE_RANGE(enc, ctype, &sb_out, &ranges);
4880   if (r == 0) {
4881     if (ascii_mode == 0)
4882       r = add_ctype_to_cc_by_range(cc, ctype, not, env->enc, sb_out, ranges);
4883     else
4884       r = add_ctype_to_cc_by_range_limit(cc, ctype, not, env->enc, sb_out,
4885                                          ranges, ASCII_LIMIT);
4886     return r;
4887   }
4888   else if (r != ONIG_NO_SUPPORT_CONFIG) {
4889     return r;
4890   }
4891
4892   r = 0;
4893   limit = ascii_mode ? ASCII_LIMIT : SINGLE_BYTE_SIZE;
4894
4895   switch (ctype) {
4896   case ONIGENC_CTYPE_ALPHA:
4897   case ONIGENC_CTYPE_BLANK:
4898   case ONIGENC_CTYPE_CNTRL:
4899   case ONIGENC_CTYPE_DIGIT:
4900   case ONIGENC_CTYPE_LOWER:
4901   case ONIGENC_CTYPE_PUNCT:
4902   case ONIGENC_CTYPE_SPACE:
4903   case ONIGENC_CTYPE_UPPER:
4904   case ONIGENC_CTYPE_XDIGIT:
4905   case ONIGENC_CTYPE_ASCII:
4906   case ONIGENC_CTYPE_ALNUM:
4907     if (not != 0) {
4908       for (c = 0; c < (int )limit; c++) {
4909         if (! ONIGENC_IS_CODE_CTYPE(enc, (OnigCodePoint )c, ctype))
4910           BITSET_SET_BIT(cc->bs, c);
4911       }
4912       for (c = limit; c < SINGLE_BYTE_SIZE; c++) {
4913         BITSET_SET_BIT(cc->bs, c);
4914       }
4915
4916       ADD_ALL_MULTI_BYTE_RANGE(enc, cc->mbuf);
4917     }
4918     else {
4919       for (c = 0; c < (int )limit; c++) {
4920         if (ONIGENC_IS_CODE_CTYPE(enc, (OnigCodePoint )c, ctype))
4921           BITSET_SET_BIT(cc->bs, c);
4922       }
4923     }
4924     break;
4925
4926   case ONIGENC_CTYPE_GRAPH:
4927   case ONIGENC_CTYPE_PRINT:
4928   case ONIGENC_CTYPE_WORD:
4929     if (not != 0) {
4930       for (c = 0; c < (int )limit; c++) {
4931         if (ONIGENC_CODE_TO_MBCLEN(enc, c) > 0 /* check invalid code point */
4932             && ! ONIGENC_IS_CODE_CTYPE(enc, (OnigCodePoint )c, ctype))
4933           BITSET_SET_BIT(cc->bs, c);
4934       }
4935       for (c = limit; c < SINGLE_BYTE_SIZE; c++) {
4936         if (ONIGENC_CODE_TO_MBCLEN(enc, c) > 0)
4937           BITSET_SET_BIT(cc->bs, c);
4938       }
4939     }
4940     else {
4941       for (c = 0; c < (int )limit; c++) {
4942         if (ONIGENC_IS_CODE_CTYPE(enc, (OnigCodePoint )c, ctype))
4943           BITSET_SET_BIT(cc->bs, c);
4944       }
4945       if (ascii_mode == 0)
4946         ADD_ALL_MULTI_BYTE_RANGE(enc, cc->mbuf);
4947     }
4948     break;
4949
4950   default:
4951     return ONIGERR_PARSER_BUG;
4952     break;
4953   }
4954
4955   return r;
4956 }
4957
4958 static int
4959 parse_posix_bracket(CClassNode* cc, UChar** src, UChar* end, ScanEnv* env)
4960 {
4961 #define POSIX_BRACKET_CHECK_LIMIT_LENGTH  20
4962 #define POSIX_BRACKET_NAME_MIN_LEN         4
4963
4964   static PosixBracketEntryType PBS[] = {
4965     { (UChar* )"alnum",  ONIGENC_CTYPE_ALNUM,  5 },
4966     { (UChar* )"alpha",  ONIGENC_CTYPE_ALPHA,  5 },
4967     { (UChar* )"blank",  ONIGENC_CTYPE_BLANK,  5 },
4968     { (UChar* )"cntrl",  ONIGENC_CTYPE_CNTRL,  5 },
4969     { (UChar* )"digit",  ONIGENC_CTYPE_DIGIT,  5 },
4970     { (UChar* )"graph",  ONIGENC_CTYPE_GRAPH,  5 },
4971     { (UChar* )"lower",  ONIGENC_CTYPE_LOWER,  5 },
4972     { (UChar* )"print",  ONIGENC_CTYPE_PRINT,  5 },
4973     { (UChar* )"punct",  ONIGENC_CTYPE_PUNCT,  5 },
4974     { (UChar* )"space",  ONIGENC_CTYPE_SPACE,  5 },
4975     { (UChar* )"upper",  ONIGENC_CTYPE_UPPER,  5 },
4976     { (UChar* )"xdigit", ONIGENC_CTYPE_XDIGIT, 6 },
4977     { (UChar* )"ascii",  ONIGENC_CTYPE_ASCII,  5 },
4978     { (UChar* )"word",   ONIGENC_CTYPE_WORD,   4 },
4979     { (UChar* )NULL,     -1, 0 }
4980   };
4981
4982   PosixBracketEntryType *pb;
4983   int not, i, r;
4984   OnigCodePoint c;
4985   OnigEncoding enc = env->enc;
4986   UChar *p = *src;
4987
4988   if (PPEEK_IS('^')) {
4989     PINC_S;
4990     not = 1;
4991   }
4992   else
4993     not = 0;
4994
4995   if (onigenc_strlen(enc, p, end) < POSIX_BRACKET_NAME_MIN_LEN + 3)
4996     goto not_posix_bracket;
4997
4998   for (pb = PBS; IS_NOT_NULL(pb->name); pb++) {
4999     if (onigenc_with_ascii_strncmp(enc, p, end, pb->name, pb->len) == 0) {
5000       p = (UChar* )onigenc_step(enc, p, end, pb->len);
5001       if (onigenc_with_ascii_strncmp(enc, p, end, (UChar* )":]", 2) != 0)
5002         return ONIGERR_INVALID_POSIX_BRACKET_TYPE;
5003
5004       r = add_ctype_to_cc(cc, pb->ctype, not, env);
5005       if (r != 0) return r;
5006
5007       PINC_S; PINC_S;
5008       *src = p;
5009       return 0;
5010     }
5011   }
5012
5013  not_posix_bracket:
5014   c = 0;
5015   i = 0;
5016   while (!PEND && ((c = PPEEK) != ':') && c != ']') {
5017     PINC_S;
5018     if (++i > POSIX_BRACKET_CHECK_LIMIT_LENGTH) break;
5019   }
5020   if (c == ':' && ! PEND) {
5021     PINC_S;
5022     if (! PEND) {
5023       PFETCH_S(c);
5024       if (c == ']')
5025         return ONIGERR_INVALID_POSIX_BRACKET_TYPE;
5026     }
5027   }
5028
5029   return 1;  /* 1: is not POSIX bracket, but no error. */
5030 }
5031
5032 static int
5033 fetch_char_property_to_ctype(UChar** src, UChar* end, ScanEnv* env)
5034 {
5035   int r;
5036   OnigCodePoint c;
5037   OnigEncoding enc = env->enc;
5038   UChar *prev, *start, *p = *src;
5039
5040   r = 0;
5041   start = prev = p;
5042
5043   while (!PEND) {
5044     prev = p;
5045     PFETCH_S(c);
5046     if (c == '}') {
5047       r = ONIGENC_PROPERTY_NAME_TO_CTYPE(enc, start, prev);
5048       if (r < 0) break;
5049
5050       *src = p;
5051       return r;
5052     }
5053     else if (c == '(' || c == ')' || c == '{' || c == '|') {
5054       r = ONIGERR_INVALID_CHAR_PROPERTY_NAME;
5055       break;
5056     }
5057   }
5058
5059   onig_scan_env_set_error_string(env, r, *src, prev);
5060   return r;
5061 }
5062
5063 static int
5064 parse_char_property(Node** np, OnigToken* tok, UChar** src, UChar* end, ScanEnv* env)
5065 {
5066   int r, ctype;
5067   CClassNode* cc;
5068
5069   ctype = fetch_char_property_to_ctype(src, end, env);
5070   if (ctype < 0) return ctype;
5071
5072   *np = node_new_cclass();
5073   CHECK_NULL_RETURN_MEMERR(*np);
5074   cc = CCLASS_(*np);
5075   r = add_ctype_to_cc(cc, ctype, 0, env);
5076   if (r != 0) return r;
5077   if (tok->u.prop.not != 0) NCCLASS_SET_NOT(cc);
5078
5079   return 0;
5080 }
5081
5082
5083 enum CCSTATE {
5084   CCS_VALUE,
5085   CCS_RANGE,
5086   CCS_COMPLETE,
5087   CCS_START
5088 };
5089
5090 enum CCVALTYPE {
5091   CCV_SB,
5092   CCV_CODE_POINT,
5093   CCV_CLASS
5094 };
5095
5096 static int
5097 next_state_class(CClassNode* cc, OnigCodePoint* vs, enum CCVALTYPE* type,
5098                  enum CCSTATE* state, ScanEnv* env)
5099 {
5100   int r;
5101
5102   if (*state == CCS_RANGE)
5103     return ONIGERR_CHAR_CLASS_VALUE_AT_END_OF_RANGE;
5104
5105   if (*state == CCS_VALUE && *type != CCV_CLASS) {
5106     if (*type == CCV_SB)
5107       BITSET_SET_BIT(cc->bs, (int )(*vs));
5108     else if (*type == CCV_CODE_POINT) {
5109       r = add_code_range(&(cc->mbuf), env, *vs, *vs);
5110       if (r < 0) return r;
5111     }
5112   }
5113
5114   *state = CCS_VALUE;
5115   *type  = CCV_CLASS;
5116   return 0;
5117 }
5118
5119 static int
5120 next_state_val(CClassNode* cc, OnigCodePoint *from, OnigCodePoint to,
5121                int* from_israw, int to_israw,
5122                enum CCVALTYPE intype, enum CCVALTYPE* type,
5123                enum CCSTATE* state, ScanEnv* env)
5124 {
5125   int r;
5126
5127   switch (*state) {
5128   case CCS_VALUE:
5129     if (*type == CCV_SB) {
5130       if (*from > 0xff)
5131           return ONIGERR_INVALID_CODE_POINT_VALUE;
5132
5133       BITSET_SET_BIT(cc->bs, (int )(*from));
5134     }
5135     else if (*type == CCV_CODE_POINT) {
5136       r = add_code_range(&(cc->mbuf), env, *from, *from);
5137       if (r < 0) return r;
5138     }
5139     break;
5140
5141   case CCS_RANGE:
5142     if (intype == *type) {
5143       if (intype == CCV_SB) {
5144         if (*from > 0xff || to > 0xff)
5145           return ONIGERR_INVALID_CODE_POINT_VALUE;
5146
5147         if (*from > to) {
5148           if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_EMPTY_RANGE_IN_CC))
5149             goto ccs_range_end;
5150           else
5151             return ONIGERR_EMPTY_RANGE_IN_CHAR_CLASS;
5152         }
5153         bitset_set_range(cc->bs, (int )*from, (int )to);
5154       }
5155       else {
5156         r = add_code_range(&(cc->mbuf), env, *from, to);
5157         if (r < 0) return r;
5158       }
5159     }
5160     else {
5161       if (*from > to) {
5162         if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_EMPTY_RANGE_IN_CC))
5163           goto ccs_range_end;
5164         else
5165           return ONIGERR_EMPTY_RANGE_IN_CHAR_CLASS;
5166       }
5167       bitset_set_range(cc->bs, (int )*from, (int )(to < 0xff ? to : 0xff));
5168       r = add_code_range(&(cc->mbuf), env, (OnigCodePoint )*from, to);
5169       if (r < 0) return r;
5170     }
5171   ccs_range_end:
5172     *state = CCS_COMPLETE;
5173     break;
5174
5175   case CCS_COMPLETE:
5176   case CCS_START:
5177     *state = CCS_VALUE;
5178     break;
5179
5180   default:
5181     break;
5182   }
5183
5184   *from_israw = to_israw;
5185   *from       = to;
5186   *type       = intype;
5187   return 0;
5188 }
5189
5190 static int
5191 code_exist_check(OnigCodePoint c, UChar* from, UChar* end, int ignore_escaped,
5192                  ScanEnv* env)
5193 {
5194   int in_esc;
5195   OnigCodePoint code;
5196   OnigEncoding enc = env->enc;
5197   UChar* p = from;
5198
5199   in_esc = 0;
5200   while (! PEND) {
5201     if (ignore_escaped && in_esc) {
5202       in_esc = 0;
5203     }
5204     else {
5205       PFETCH_S(code);
5206       if (code == c) return 1;
5207       if (code == MC_ESC(env->syntax)) in_esc = 1;
5208     }
5209   }
5210   return 0;
5211 }
5212
5213 static int
5214 parse_char_class(Node** np, OnigToken* tok, UChar** src, UChar* end, ScanEnv* env)
5215 {
5216   int r, neg, len, fetched, and_start;
5217   OnigCodePoint v, vs;
5218   UChar *p;
5219   Node* node;
5220   CClassNode *cc, *prev_cc;
5221   CClassNode work_cc;
5222
5223   enum CCSTATE state;
5224   enum CCVALTYPE val_type, in_type;
5225   int val_israw, in_israw;
5226
5227   *np = NULL_NODE;
5228   env->parse_depth++;
5229   if (env->parse_depth > ParseDepthLimit)
5230     return ONIGERR_PARSE_DEPTH_LIMIT_OVER;
5231   prev_cc = (CClassNode* )NULL;
5232   r = fetch_token_in_cc(tok, src, end, env);
5233   if (r == TK_CHAR && tok->u.c == '^' && tok->escaped == 0) {
5234     neg = 1;
5235     r = fetch_token_in_cc(tok, src, end, env);
5236   }
5237   else {
5238     neg = 0;
5239   }
5240
5241   if (r < 0) return r;
5242   if (r == TK_CC_CLOSE) {
5243     if (! code_exist_check((OnigCodePoint )']',
5244                            *src, env->pattern_end, 1, env))
5245       return ONIGERR_EMPTY_CHAR_CLASS;
5246
5247     CC_ESC_WARN(env, (UChar* )"]");
5248     r = tok->type = TK_CHAR;  /* allow []...] */
5249   }
5250
5251   *np = node = node_new_cclass();
5252   CHECK_NULL_RETURN_MEMERR(node);
5253   cc = CCLASS_(node);
5254
5255   and_start = 0;
5256   state = CCS_START;
5257   p = *src;
5258   while (r != TK_CC_CLOSE) {
5259     fetched = 0;
5260     switch (r) {
5261     case TK_CHAR:
5262     any_char_in:
5263       len = ONIGENC_CODE_TO_MBCLEN(env->enc, tok->u.c);
5264       if (len > 1) {
5265         in_type = CCV_CODE_POINT;
5266       }
5267       else if (len < 0) {
5268         r = len;
5269         goto err;
5270       }
5271       else {
5272         /* sb_char: */
5273         in_type = CCV_SB;
5274       }
5275       v = (OnigCodePoint )tok->u.c;
5276       in_israw = 0;
5277       goto val_entry2;
5278       break;
5279
5280     case TK_RAW_BYTE:
5281       /* tok->base != 0 : octal or hexadec. */
5282       if (! ONIGENC_IS_SINGLEBYTE(env->enc) && tok->base != 0) {
5283         UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
5284         UChar* bufe = buf + ONIGENC_CODE_TO_MBC_MAXLEN;
5285         UChar* psave = p;
5286         int i, base = tok->base;
5287
5288         buf[0] = tok->u.c;
5289         for (i = 1; i < ONIGENC_MBC_MAXLEN(env->enc); i++) {
5290           r = fetch_token_in_cc(tok, &p, end, env);
5291           if (r < 0) goto err;
5292           if (r != TK_RAW_BYTE || tok->base != base) {
5293             fetched = 1;
5294             break;
5295           }
5296           buf[i] = tok->u.c;
5297         }
5298
5299         if (i < ONIGENC_MBC_MINLEN(env->enc)) {
5300           r = ONIGERR_TOO_SHORT_MULTI_BYTE_STRING;
5301           goto err;
5302         }
5303
5304         len = enclen(env->enc, buf);
5305         if (i < len) {
5306           r = ONIGERR_TOO_SHORT_MULTI_BYTE_STRING;
5307           goto err;
5308         }
5309         else if (i > len) { /* fetch back */
5310           p = psave;
5311           for (i = 1; i < len; i++) {
5312             r = fetch_token_in_cc(tok, &p, end, env);
5313           }
5314           fetched = 0;
5315         }
5316
5317         if (i == 1) {
5318           v = (OnigCodePoint )buf[0];
5319           goto raw_single;
5320         }
5321         else {
5322           v = ONIGENC_MBC_TO_CODE(env->enc, buf, bufe);
5323           in_type = CCV_CODE_POINT;
5324         }
5325       }
5326       else {
5327         v = (OnigCodePoint )tok->u.c;
5328       raw_single:
5329         in_type = CCV_SB;
5330       }
5331       in_israw = 1;
5332       goto val_entry2;
5333       break;
5334
5335     case TK_CODE_POINT:
5336       v = tok->u.code;
5337       in_israw = 1;
5338     val_entry:
5339       len = ONIGENC_CODE_TO_MBCLEN(env->enc, v);
5340       if (len < 0) {
5341         r = len;
5342         goto err;
5343       }
5344       in_type = (len == 1 ? CCV_SB : CCV_CODE_POINT);
5345     val_entry2:
5346       r = next_state_val(cc, &vs, v, &val_israw, in_israw, in_type, &val_type,
5347                          &state, env);
5348       if (r != 0) goto err;
5349       break;
5350
5351     case TK_POSIX_BRACKET_OPEN:
5352       r = parse_posix_bracket(cc, &p, end, env);
5353       if (r < 0) goto err;
5354       if (r == 1) {  /* is not POSIX bracket */
5355         CC_ESC_WARN(env, (UChar* )"[");
5356         p = tok->backp;
5357         v = (OnigCodePoint )tok->u.c;
5358         in_israw = 0;
5359         goto val_entry;
5360       }
5361       goto next_class;
5362       break;
5363
5364     case TK_CHAR_TYPE:
5365       r = add_ctype_to_cc(cc, tok->u.prop.ctype, tok->u.prop.not, env);
5366       if (r != 0) goto err;
5367
5368     next_class:
5369       r = next_state_class(cc, &vs, &val_type, &state, env);
5370       if (r != 0) goto err;
5371       break;
5372
5373     case TK_CHAR_PROPERTY:
5374       {
5375         int ctype = fetch_char_property_to_ctype(&p, end, env);
5376         if (ctype < 0) {
5377           r = ctype;
5378           goto err;
5379         }
5380         r = add_ctype_to_cc(cc, ctype, tok->u.prop.not, env);
5381         if (r != 0) goto err;
5382         goto next_class;
5383       }
5384       break;
5385
5386     case TK_CC_RANGE:
5387       if (state == CCS_VALUE) {
5388         r = fetch_token_in_cc(tok, &p, end, env);
5389         if (r < 0) goto err;
5390         fetched = 1;
5391         if (r == TK_CC_CLOSE) { /* allow [x-] */
5392         range_end_val:
5393           v = (OnigCodePoint )'-';
5394           in_israw = 0;
5395           goto val_entry;
5396         }
5397         else if (r == TK_CC_AND) {
5398           CC_ESC_WARN(env, (UChar* )"-");
5399           goto range_end_val;
5400         }
5401
5402         if (val_type == CCV_CLASS) {
5403           r = ONIGERR_UNMATCHED_RANGE_SPECIFIER_IN_CHAR_CLASS;
5404           goto err;
5405         }
5406
5407         state = CCS_RANGE;
5408       }
5409       else if (state == CCS_START) {
5410         /* [-xa] is allowed */
5411         v = (OnigCodePoint )tok->u.c;
5412         in_israw = 0;
5413
5414         r = fetch_token_in_cc(tok, &p, end, env);
5415         if (r < 0) goto err;
5416         fetched = 1;
5417         /* [--x] or [a&&-x] is warned. */
5418         if (r == TK_CC_RANGE || and_start != 0)
5419           CC_ESC_WARN(env, (UChar* )"-");
5420
5421         goto val_entry;
5422       }
5423       else if (state == CCS_RANGE) {
5424         CC_ESC_WARN(env, (UChar* )"-");
5425         goto any_char_in;  /* [!--x] is allowed */
5426       }
5427       else { /* CCS_COMPLETE */
5428         r = fetch_token_in_cc(tok, &p, end, env);
5429         if (r < 0) goto err;
5430         fetched = 1;
5431         if (r == TK_CC_CLOSE) goto range_end_val; /* allow [a-b-] */
5432         else if (r == TK_CC_AND) {
5433           CC_ESC_WARN(env, (UChar* )"-");
5434           goto range_end_val;
5435         }
5436
5437         if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_DOUBLE_RANGE_OP_IN_CC)) {
5438           CC_ESC_WARN(env, (UChar* )"-");
5439           goto range_end_val;   /* [0-9-a] is allowed as [0-9\-a] */
5440         }
5441         r = ONIGERR_UNMATCHED_RANGE_SPECIFIER_IN_CHAR_CLASS;
5442         goto err;
5443       }
5444       break;
5445
5446     case TK_CC_CC_OPEN: /* [ */
5447       {
5448         Node *anode;
5449         CClassNode* acc;
5450
5451         r = parse_char_class(&anode, tok, &p, end, env);
5452         if (r != 0) {
5453           onig_node_free(anode);
5454           goto cc_open_err;
5455         }
5456         acc = CCLASS_(anode);
5457         r = or_cclass(cc, acc, env->enc);
5458         onig_node_free(anode);
5459
5460       cc_open_err:
5461         if (r != 0) goto err;
5462       }
5463       break;
5464
5465     case TK_CC_AND: /* && */
5466       {
5467         if (state == CCS_VALUE) {
5468           r = next_state_val(cc, &vs, 0, &val_israw, 0, val_type,
5469                              &val_type, &state, env);
5470           if (r != 0) goto err;
5471         }
5472         /* initialize local variables */
5473         and_start = 1;
5474         state = CCS_START;
5475
5476         if (IS_NOT_NULL(prev_cc)) {
5477           r = and_cclass(prev_cc, cc, env->enc);
5478           if (r != 0) goto err;
5479           bbuf_free(cc->mbuf);
5480         }
5481         else {
5482           prev_cc = cc;
5483           cc = &work_cc;
5484         }
5485         initialize_cclass(cc);
5486       }
5487       break;
5488
5489     case TK_EOT:
5490       r = ONIGERR_PREMATURE_END_OF_CHAR_CLASS;
5491       goto err;
5492       break;
5493     default:
5494       r = ONIGERR_PARSER_BUG;
5495       goto err;
5496       break;
5497     }
5498
5499     if (fetched)
5500       r = tok->type;
5501     else {
5502       r = fetch_token_in_cc(tok, &p, end, env);
5503       if (r < 0) goto err;
5504     }
5505   }
5506
5507   if (state == CCS_VALUE) {
5508     r = next_state_val(cc, &vs, 0, &val_israw, 0, val_type,
5509                        &val_type, &state, env);
5510     if (r != 0) goto err;
5511   }
5512
5513   if (IS_NOT_NULL(prev_cc)) {
5514     r = and_cclass(prev_cc, cc, env->enc);
5515     if (r != 0) goto err;
5516     bbuf_free(cc->mbuf);
5517     cc = prev_cc;
5518   }
5519
5520   if (neg != 0)
5521     NCCLASS_SET_NOT(cc);
5522   else
5523     NCCLASS_CLEAR_NOT(cc);
5524   if (IS_NCCLASS_NOT(cc) &&
5525       IS_SYNTAX_BV(env->syntax, ONIG_SYN_NOT_NEWLINE_IN_NEGATIVE_CC)) {
5526     int is_empty = (IS_NULL(cc->mbuf) ? 1 : 0);
5527     if (is_empty != 0)
5528       BITSET_IS_EMPTY(cc->bs, is_empty);
5529
5530     if (is_empty == 0) {
5531 #define NEWLINE_CODE    0x0a
5532
5533       if (ONIGENC_IS_CODE_NEWLINE(env->enc, NEWLINE_CODE)) {
5534         if (ONIGENC_CODE_TO_MBCLEN(env->enc, NEWLINE_CODE) == 1)
5535           BITSET_SET_BIT(cc->bs, NEWLINE_CODE);
5536         else
5537           add_code_range(&(cc->mbuf), env, NEWLINE_CODE, NEWLINE_CODE);
5538       }
5539     }
5540   }
5541   *src = p;
5542   env->parse_depth--;
5543   return 0;
5544
5545  err:
5546   if (cc != CCLASS_(*np))
5547     bbuf_free(cc->mbuf);
5548   return r;
5549 }
5550
5551 static int parse_subexp(Node** top, OnigToken* tok, int term,
5552                         UChar** src, UChar* end, ScanEnv* env);
5553
5554 /* (?{...}) (?{{...}}) */
5555 static int
5556 parse_code_callout(Node** np, int cterm, UChar** src, UChar* end, ScanEnv* env)
5557 {
5558   int r;
5559   int i;
5560   OnigCodePoint c;
5561   UChar* code_start;
5562   UChar* code_end;
5563   int brace_nest;
5564   OnigEncoding enc = env->enc;
5565   UChar* p = *src;
5566
5567   //PFETCH_READY;
5568
5569   if (PEND) return ONIGERR_INVALID_CALLOUT_PATTERN;
5570
5571   brace_nest = 0;
5572   while (PPEEK_IS('{')) {
5573     brace_nest++;
5574     PINC_S;
5575     if (PEND) return ONIGERR_INVALID_CALLOUT_PATTERN;
5576   }
5577
5578   code_start = p;
5579   while (1) {
5580     if (PEND) return ONIGERR_INVALID_CALLOUT_PATTERN;
5581
5582     code_end = p;
5583     PFETCH_S(c);
5584     if (c == '}') {
5585       i = brace_nest;
5586       while (i > 0) {
5587         if (PEND) return ONIGERR_INVALID_CALLOUT_PATTERN;
5588         PFETCH_S(c);
5589         if (c == '}') i--;
5590         else break;
5591       }
5592       if (i == 0) break;
5593     }
5594   }
5595
5596   if (PEND) return ONIGERR_END_PATTERN_IN_GROUP;
5597   PFETCH_S(c);
5598   if (c != cterm)
5599     return ONIGERR_INVALID_CALLOUT_PATTERN;
5600
5601   r = node_new_callout(np, CALLOUT_CODE, env);
5602   if (r != 0) return r;
5603
5604   GIMMICK_(*np)->start = code_start - env->pattern;
5605   GIMMICK_(*np)->end   = code_end   - env->pattern;
5606
5607   *src = p;
5608   return 0;
5609 }
5610
5611 static int
5612 parse_enclosure(Node** np, OnigToken* tok, int term, UChar** src, UChar* end,
5613                 ScanEnv* env)
5614 {
5615   int r, num;
5616   Node *target;
5617   OnigOptionType option;
5618   OnigCodePoint c;
5619   int list_capture;
5620   OnigEncoding enc = env->enc;
5621
5622   UChar* p = *src;
5623   PFETCH_READY;
5624
5625   *np = NULL;
5626   if (PEND) return ONIGERR_END_PATTERN_WITH_UNMATCHED_PARENTHESIS;
5627
5628   option = env->options;
5629   if (PPEEK_IS('?') &&
5630       IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_GROUP_EFFECT)) {
5631     PINC;
5632     if (PEND) return ONIGERR_END_PATTERN_IN_GROUP;
5633
5634     PFETCH(c);
5635     switch (c) {
5636     case ':':   /* (?:...) grouping only */
5637     group:
5638       r = fetch_token(tok, &p, end, env);
5639       if (r < 0) return r;
5640       r = parse_subexp(np, tok, term, &p, end, env);
5641       if (r < 0) return r;
5642       *src = p;
5643       return 1; /* group */
5644       break;
5645
5646     case '=':
5647       *np = onig_node_new_anchor(ANCHOR_PREC_READ, 0);
5648       break;
5649     case '!':  /*         preceding read */
5650       *np = onig_node_new_anchor(ANCHOR_PREC_READ_NOT, 0);
5651       break;
5652     case '>':            /* (?>...) stop backtrack */
5653       *np = node_new_enclosure(ENCLOSURE_STOP_BACKTRACK);
5654       break;
5655
5656     case '\'':
5657       if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP)) {
5658         goto named_group1;
5659       }
5660       else
5661         return ONIGERR_UNDEFINED_GROUP_OPTION;
5662       break;
5663
5664     case '<':   /* look behind (?<=...), (?<!...) */
5665       if (PEND) return ONIGERR_END_PATTERN_WITH_UNMATCHED_PARENTHESIS;
5666       PFETCH(c);
5667       if (c == '=')
5668         *np = onig_node_new_anchor(ANCHOR_LOOK_BEHIND, 0);
5669       else if (c == '!')
5670         *np = onig_node_new_anchor(ANCHOR_LOOK_BEHIND_NOT, 0);
5671       else {
5672         if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP)) {
5673           UChar *name;
5674           UChar *name_end;
5675           enum REF_NUM num_type;
5676
5677           PUNFETCH;
5678           c = '<';
5679
5680         named_group1:
5681           list_capture = 0;
5682
5683         named_group2:
5684           name = p;
5685           r = fetch_name((OnigCodePoint )c, &p, end, &name_end, env, &num,
5686                          &num_type, 0);
5687           if (r < 0) return r;
5688
5689           num = scan_env_add_mem_entry(env);
5690           if (num < 0) return num;
5691           if (list_capture != 0 && num >= (int )MEM_STATUS_BITS_NUM)
5692             return ONIGERR_GROUP_NUMBER_OVER_FOR_CAPTURE_HISTORY;
5693
5694           r = name_add(env->reg, name, name_end, num, env);
5695           if (r != 0) return r;
5696           *np = node_new_memory(1);
5697           CHECK_NULL_RETURN_MEMERR(*np);
5698           ENCLOSURE_(*np)->m.regnum = num;
5699           if (list_capture != 0)
5700             MEM_STATUS_ON_SIMPLE(env->capture_history, num);
5701           env->num_named++;
5702         }
5703         else {
5704           return ONIGERR_UNDEFINED_GROUP_OPTION;
5705         }
5706       }
5707       break;
5708
5709     case '~':
5710       if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_TILDE_ABSENT_GROUP)) {
5711         Node* absent;
5712         Node* expr;
5713         int head_bar;
5714         int is_range_cutter;
5715
5716         if (PEND) return ONIGERR_END_PATTERN_IN_GROUP;
5717
5718         if (PPEEK_IS('|')) { // (?~|generator|absent)
5719           PINC;
5720           if (PEND) return ONIGERR_END_PATTERN_IN_GROUP;
5721
5722           head_bar = 1;
5723           if (PPEEK_IS(')')) { // (?~|)  : range clear
5724             PINC;
5725             r = make_range_clear(np, env);
5726             if (r != 0) return r;
5727             goto end;
5728           }
5729         }
5730         else
5731           head_bar = 0;
5732
5733         r = fetch_token(tok, &p, end, env);
5734         if (r < 0) return r;
5735         r = parse_subexp(&absent, tok, term, &p, end, env);
5736         if (r < 0) {
5737           onig_node_free(absent);
5738           return r;
5739         }
5740
5741         expr = NULL_NODE;
5742         is_range_cutter = 0;
5743         if (head_bar != 0) {
5744           Node* top = absent;
5745           if (NODE_TYPE(top) != NODE_ALT || IS_NULL(NODE_CDR(top))) {
5746             expr = NULL_NODE;
5747             is_range_cutter = 1;
5748             //return ONIGERR_INVALID_ABSENT_GROUP_GENERATOR_PATTERN;
5749           }
5750           else {
5751             absent = NODE_CAR(top);
5752             expr   = NODE_CDR(top);
5753             NODE_CAR(top) = NULL_NODE;
5754             NODE_CDR(top) = NULL_NODE;
5755             onig_node_free(top);
5756             if (IS_NULL(NODE_CDR(expr))) {
5757               top = expr;
5758               expr = NODE_CAR(top);
5759               NODE_CAR(top) = NULL_NODE;
5760               onig_node_free(top);
5761             }
5762           }
5763         }
5764
5765         r = make_absent_tree(np, absent, expr, is_range_cutter, env);
5766         if (r != 0) {
5767           return r;
5768         }
5769         goto end;
5770       }
5771       else {
5772         return ONIGERR_UNDEFINED_GROUP_OPTION;
5773       }
5774       break;
5775
5776     case '{':
5777       if (! IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_BRACE_CALLOUT))
5778         return ONIGERR_UNDEFINED_GROUP_OPTION;
5779
5780       /* (?{...}) (?{{...}}) */
5781       r = parse_code_callout(np, ')', &p, end, env);
5782       if (r != 0) return r;
5783
5784       goto end;
5785       break;
5786
5787     case '(':
5788       /* (?()...) */
5789       if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_LPAREN_IF_ELSE)) {
5790         UChar *prev;
5791         Node* condition;
5792         int condition_is_checker;
5793
5794         if (PEND) return ONIGERR_END_PATTERN_IN_GROUP;
5795         PFETCH(c);
5796         if (PEND) return ONIGERR_END_PATTERN_IN_GROUP;
5797
5798         if (IS_CODE_DIGIT_ASCII(enc, c)
5799             || c == '-' || c == '+' || c == '<' || c == '\'') {
5800           UChar* name_end;
5801           int back_num;
5802           int exist_level;
5803           int level;
5804           enum REF_NUM num_type;
5805           int is_enclosed;
5806
5807           is_enclosed = (c == '<' || c == '\'') ? 1 : 0;
5808           if (! is_enclosed)
5809             PUNFETCH;
5810           prev = p;
5811           exist_level = 0;
5812 #ifdef USE_BACKREF_WITH_LEVEL
5813           name_end = NULL_UCHARP; /* no need. escape gcc warning. */
5814           r = fetch_name_with_level(
5815                     (OnigCodePoint )(is_enclosed != 0 ? c : '('),
5816                     &p, end, &name_end,
5817                     env, &back_num, &level, &num_type);
5818           if (r == 1) exist_level = 1;
5819 #else
5820           r = fetch_name((OnigCodePoint )(is_enclosed != 0 ? c : '('),
5821                          &p, end, &name_end, env, &back_num, &num_type, 1);
5822 #endif
5823           if (r < 0) {
5824             if (is_enclosed == 0) {
5825               goto any_condition;
5826             }
5827             else
5828               return r;
5829           }
5830
5831           condition_is_checker = 1;
5832           if (num_type != IS_NOT_NUM) {
5833             if (num_type == IS_REL_NUM) {
5834               back_num = backref_rel_to_abs(back_num, env);
5835             }
5836             if (back_num <= 0)
5837               return ONIGERR_INVALID_BACKREF;
5838
5839             if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_STRICT_CHECK_BACKREF)) {
5840               if (back_num > env->num_mem ||
5841                   IS_NULL(SCANENV_MEMENV(env)[back_num].node))
5842                 return ONIGERR_INVALID_BACKREF;
5843             }
5844
5845             condition = node_new_backref_checker(1, &back_num, 0,
5846 #ifdef USE_BACKREF_WITH_LEVEL
5847                                                  exist_level, level,
5848 #endif
5849                                                  env);
5850           }
5851           else {
5852             int num;
5853             int* backs;
5854
5855             num = onig_name_to_group_numbers(env->reg, prev, name_end, &backs);
5856             if (num <= 0) {
5857               onig_scan_env_set_error_string(env,
5858                         ONIGERR_UNDEFINED_NAME_REFERENCE, prev, name_end);
5859               return ONIGERR_UNDEFINED_NAME_REFERENCE;
5860             }
5861             if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_STRICT_CHECK_BACKREF)) {
5862               int i;
5863               for (i = 0; i < num; i++) {
5864                 if (backs[i] > env->num_mem ||
5865                     IS_NULL(SCANENV_MEMENV(env)[backs[i]].node))
5866                   return ONIGERR_INVALID_BACKREF;
5867               }
5868             }
5869
5870             condition = node_new_backref_checker(num, backs, 1,
5871 #ifdef USE_BACKREF_WITH_LEVEL
5872                                                  exist_level, level,
5873 #endif
5874                                                  env);
5875           }
5876
5877           if (is_enclosed != 0) {
5878             if (PEND) goto err_if_else;
5879             PFETCH(c);
5880             if (c != ')') goto err_if_else;
5881           }
5882         }
5883         else {
5884         any_condition:
5885           PUNFETCH;
5886           condition_is_checker = 0;
5887           r = fetch_token(tok, &p, end, env);
5888           if (r < 0) return r;
5889           r = parse_subexp(&condition, tok, term, &p, end, env);
5890           if (r < 0) {
5891             onig_node_free(condition);
5892             return r;
5893           }
5894         }
5895
5896         CHECK_NULL_RETURN_MEMERR(condition);
5897
5898         if (PEND) {
5899         err_if_else:
5900           onig_node_free(condition);
5901           return ONIGERR_END_PATTERN_IN_GROUP;
5902         }
5903
5904         if (PPEEK_IS(')')) { /* case: empty body: make backref checker */
5905           if (condition_is_checker == 0) {
5906             onig_node_free(condition);
5907             return ONIGERR_INVALID_IF_ELSE_SYNTAX;
5908           }
5909           PFETCH(c);
5910           *np = condition;
5911         }
5912         else { /* if-else */
5913           int then_is_empty;
5914           Node *Then, *Else;
5915
5916           if (PPEEK_IS('|')) {
5917             PFETCH(c);
5918             Then = 0;
5919             then_is_empty = 1;
5920           }
5921           else
5922             then_is_empty = 0;
5923
5924           r = fetch_token(tok, &p, end, env);
5925           if (r < 0) {
5926             onig_node_free(condition);
5927             return r;
5928           }
5929           r = parse_subexp(&target, tok, term, &p, end, env);
5930           if (r < 0) {
5931             onig_node_free(condition);
5932             onig_node_free(target);
5933             return r;
5934           }
5935
5936           if (then_is_empty != 0) {
5937             Else = target;
5938           }
5939           else {
5940             if (NODE_TYPE(target) == NODE_ALT) {
5941               Then = NODE_CAR(target);
5942               if (NODE_CDR(NODE_CDR(target)) == NULL_NODE) {
5943                 Else = NODE_CAR(NODE_CDR(target));
5944                 cons_node_free_alone(NODE_CDR(target));
5945               }
5946               else {
5947                 Else = NODE_CDR(target);
5948               }
5949               cons_node_free_alone(target);
5950             }
5951             else {
5952               Then = target;
5953               Else = 0;
5954             }
5955           }
5956
5957           *np = node_new_enclosure_if_else(condition, Then, Else);
5958           if (IS_NULL(*np)) {
5959             onig_node_free(condition);
5960             onig_node_free(Then);
5961             onig_node_free(Else);
5962             return ONIGERR_MEMORY;
5963           }
5964         }
5965         goto end;
5966       }
5967       else {
5968         return ONIGERR_UNDEFINED_GROUP_OPTION;
5969       }
5970       break;
5971
5972     case '@':
5973       if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_ATMARK_CAPTURE_HISTORY)) {
5974         if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP)) {
5975           PFETCH(c);
5976           if (c == '<' || c == '\'') {
5977             list_capture = 1;
5978             goto named_group2; /* (?@<name>...) */
5979           }
5980           PUNFETCH;
5981         }
5982
5983         *np = node_new_memory(0);
5984         CHECK_NULL_RETURN_MEMERR(*np);
5985         num = scan_env_add_mem_entry(env);
5986         if (num < 0) {
5987           return num;
5988         }
5989         else if (num >= (int )MEM_STATUS_BITS_NUM) {
5990           return ONIGERR_GROUP_NUMBER_OVER_FOR_CAPTURE_HISTORY;
5991         }
5992         ENCLOSURE_(*np)->m.regnum = num;
5993         MEM_STATUS_ON_SIMPLE(env->capture_history, num);
5994       }
5995       else {
5996         return ONIGERR_UNDEFINED_GROUP_OPTION;
5997       }
5998       break;
5999
6000 #ifdef USE_POSIXLINE_OPTION
6001     case 'p':
6002 #endif
6003     case '-': case 'i': case 'm': case 's': case 'x':
6004     case 'W': case 'D': case 'S': case 'P':
6005       {
6006         int neg = 0;
6007
6008         while (1) {
6009           switch (c) {
6010           case ':':
6011           case ')':
6012             break;
6013
6014           case '-':  neg = 1; break;
6015           case 'x':  OPTION_NEGATE(option, ONIG_OPTION_EXTEND,     neg); break;
6016           case 'i':  OPTION_NEGATE(option, ONIG_OPTION_IGNORECASE, neg); break;
6017           case 's':
6018             if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_OPTION_PERL)) {
6019               OPTION_NEGATE(option, ONIG_OPTION_MULTILINE,  neg);
6020             }
6021             else
6022               return ONIGERR_UNDEFINED_GROUP_OPTION;
6023             break;
6024
6025           case 'm':
6026             if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_OPTION_PERL)) {
6027               OPTION_NEGATE(option, ONIG_OPTION_SINGLELINE, (neg == 0 ? 1 : 0));
6028             }
6029             else if (IS_SYNTAX_OP2(env->syntax, ONIG_SYN_OP2_OPTION_RUBY)) {
6030               OPTION_NEGATE(option, ONIG_OPTION_MULTILINE,  neg);
6031             }
6032             else
6033               return ONIGERR_UNDEFINED_GROUP_OPTION;
6034             break;
6035 #ifdef USE_POSIXLINE_OPTION
6036           case 'p':
6037             OPTION_NEGATE(option, ONIG_OPTION_MULTILINE|ONIG_OPTION_SINGLELINE, neg);
6038             break;
6039 #endif
6040           case 'W': OPTION_NEGATE(option, ONIG_OPTION_WORD_IS_ASCII, neg); break;
6041           case 'D': OPTION_NEGATE(option, ONIG_OPTION_DIGIT_IS_ASCII, neg); break;
6042           case 'S': OPTION_NEGATE(option, ONIG_OPTION_SPACE_IS_ASCII, neg); break;
6043           case 'P': OPTION_NEGATE(option, ONIG_OPTION_POSIX_IS_ASCII, neg); break;
6044
6045           default:
6046             return ONIGERR_UNDEFINED_GROUP_OPTION;
6047           }
6048
6049           if (c == ')') {
6050             *np = node_new_option(option);
6051             CHECK_NULL_RETURN_MEMERR(*np);
6052             *src = p;
6053             return 2; /* option only */
6054           }
6055           else if (c == ':') {
6056             OnigOptionType prev = env->options;
6057
6058             env->options = option;
6059             r = fetch_token(tok, &p, end, env);
6060             if (r < 0) return r;
6061             r = parse_subexp(&target, tok, term, &p, end, env);
6062             env->options = prev;
6063             if (r < 0) {
6064               onig_node_free(target);
6065               return r;
6066             }
6067             *np = node_new_option(option);
6068             CHECK_NULL_RETURN_MEMERR(*np);
6069             NODE_BODY(*np) = target;
6070             *src = p;
6071             return 0;
6072           }
6073
6074           if (PEND) return ONIGERR_END_PATTERN_IN_GROUP;
6075           PFETCH(c);
6076         }
6077       }
6078       break;
6079
6080     default:
6081       return ONIGERR_UNDEFINED_GROUP_OPTION;
6082     }
6083   }
6084   else {
6085     if (ONIG_IS_OPTION_ON(env->options, ONIG_OPTION_DONT_CAPTURE_GROUP))
6086       goto group;
6087
6088     *np = node_new_memory(0);
6089     CHECK_NULL_RETURN_MEMERR(*np);
6090     num = scan_env_add_mem_entry(env);
6091     if (num < 0) return num;
6092     ENCLOSURE_(*np)->m.regnum = num;
6093   }
6094
6095   CHECK_NULL_RETURN_MEMERR(*np);
6096   r = fetch_token(tok, &p, end, env);
6097   if (r < 0) return r;
6098   r = parse_subexp(&target, tok, term, &p, end, env);
6099   if (r < 0) {
6100     onig_node_free(target);
6101     return r;
6102   }
6103
6104   NODE_BODY(*np) = target;
6105
6106   if (NODE_TYPE(*np) == NODE_ENCLOSURE) {
6107     if (ENCLOSURE_(*np)->type == ENCLOSURE_MEMORY) {
6108       /* Don't move this to previous of parse_subexp() */
6109       r = scan_env_set_mem_node(env, ENCLOSURE_(*np)->m.regnum, *np);
6110       if (r != 0) return r;
6111     }
6112   }
6113
6114  end:
6115   *src = p;
6116   return 0;
6117 }
6118
6119 static const char* PopularQStr[] = {
6120   "?", "*", "+", "??", "*?", "+?"
6121 };
6122
6123 static const char* ReduceQStr[] = {
6124   "", "", "*", "*?", "??", "+ and ??", "+? and ?"
6125 };
6126
6127 static int
6128 set_quantifier(Node* qnode, Node* target, int group, ScanEnv* env)
6129 {
6130   QuantNode* qn;
6131
6132   qn = QUANT_(qnode);
6133   if (qn->lower == 1 && qn->upper == 1)
6134     return 1;
6135
6136   switch (NODE_TYPE(target)) {
6137   case NODE_STRING:
6138     if (! group) {
6139       StrNode* sn = STR_(target);
6140       if (str_node_can_be_split(sn, env->enc)) {
6141         Node* n = str_node_split_last_char(sn, env->enc);
6142         if (IS_NOT_NULL(n)) {
6143           NODE_BODY(qnode) = n;
6144           return 2;
6145         }
6146       }
6147     }
6148     break;
6149
6150   case NODE_QUANT:
6151     { /* check redundant double repeat. */
6152       /* verbose warn (?:.?)? etc... but not warn (.?)? etc... */
6153       QuantNode* qnt   = QUANT_(target);
6154       int nestq_num   = quantifier_type_num(qn);
6155       int targetq_num = quantifier_type_num(qnt);
6156
6157 #ifdef USE_WARNING_REDUNDANT_NESTED_REPEAT_OPERATOR
6158       if (! NODE_IS_BY_NUMBER(qnode) && ! NODE_IS_BY_NUMBER(target) &&
6159           IS_SYNTAX_BV(env->syntax, ONIG_SYN_WARN_REDUNDANT_NESTED_REPEAT)) {
6160         UChar buf[WARN_BUFSIZE];
6161
6162         switch(ReduceTypeTable[targetq_num][nestq_num]) {
6163         case RQ_ASIS:
6164           break;
6165
6166         case RQ_DEL:
6167           if (onig_verb_warn != onig_null_warn) {
6168             onig_snprintf_with_pattern(buf, WARN_BUFSIZE, env->enc,
6169                                   env->pattern, env->pattern_end,
6170                                   (UChar* )"redundant nested repeat operator");
6171             (*onig_verb_warn)((char* )buf);
6172           }
6173           goto warn_exit;
6174           break;
6175
6176         default:
6177           if (onig_verb_warn != onig_null_warn) {
6178             onig_snprintf_with_pattern(buf, WARN_BUFSIZE, env->enc,
6179                                        env->pattern, env->pattern_end,
6180             (UChar* )"nested repeat operator %s and %s was replaced with '%s'",
6181             PopularQStr[targetq_num], PopularQStr[nestq_num],
6182             ReduceQStr[ReduceTypeTable[targetq_num][nestq_num]]);
6183             (*onig_verb_warn)((char* )buf);
6184           }
6185           goto warn_exit;
6186           break;
6187         }
6188       }
6189
6190     warn_exit:
6191 #endif
6192       if (targetq_num >= 0 && nestq_num < 0) {
6193         if (targetq_num == 1 || targetq_num == 2) { /* * or + */
6194           /* (?:a*){n,m}, (?:a+){n,m} => (?:a*){n,n}, (?:a+){n,n} */
6195           if (! IS_REPEAT_INFINITE(qn->upper) && qn->upper > 1 && qn->greedy) {
6196             qn->upper = (qn->lower == 0 ? 1 : qn->lower);
6197           }
6198         }
6199       }
6200       else {
6201         NODE_BODY(qnode) = target;
6202         onig_reduce_nested_quantifier(qnode, target);
6203         goto q_exit;
6204       }
6205     }
6206     break;
6207
6208   default:
6209     break;
6210   }
6211
6212   NODE_BODY(qnode) = target;
6213  q_exit:
6214   return 0;
6215 }
6216
6217
6218 #ifndef CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS
6219 static int
6220 clear_not_flag_cclass(CClassNode* cc, OnigEncoding enc)
6221 {
6222   BBuf *tbuf;
6223   int r;
6224
6225   if (IS_NCCLASS_NOT(cc)) {
6226     bitset_invert(cc->bs);
6227
6228     if (! ONIGENC_IS_SINGLEBYTE(enc)) {
6229       r = not_code_range_buf(enc, cc->mbuf, &tbuf);
6230       if (r != 0) return r;
6231
6232       bbuf_free(cc->mbuf);
6233       cc->mbuf = tbuf;
6234     }
6235
6236     NCCLASS_CLEAR_NOT(cc);
6237   }
6238
6239   return 0;
6240 }
6241 #endif /* CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS */
6242
6243 typedef struct {
6244   ScanEnv*    env;
6245   CClassNode* cc;
6246   Node*       alt_root;
6247   Node**      ptail;
6248 } IApplyCaseFoldArg;
6249
6250 static int
6251 i_apply_case_fold(OnigCodePoint from, OnigCodePoint to[], int to_len, void* arg)
6252 {
6253   IApplyCaseFoldArg* iarg;
6254   ScanEnv* env;
6255   CClassNode* cc;
6256   BitSetRef bs;
6257
6258   iarg = (IApplyCaseFoldArg* )arg;
6259   env = iarg->env;
6260   cc  = iarg->cc;
6261   bs = cc->bs;
6262
6263   if (to_len == 1) {
6264     int is_in = onig_is_code_in_cc(env->enc, from, cc);
6265 #ifdef CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS
6266     if ((is_in != 0 && !IS_NCCLASS_NOT(cc)) ||
6267         (is_in == 0 &&  IS_NCCLASS_NOT(cc))) {
6268       if (ONIGENC_MBC_MINLEN(env->enc) > 1 || *to >= SINGLE_BYTE_SIZE) {
6269         add_code_range(&(cc->mbuf), env, *to, *to);
6270       }
6271       else {
6272         BITSET_SET_BIT(bs, *to);
6273       }
6274     }
6275 #else
6276     if (is_in != 0) {
6277       if (ONIGENC_MBC_MINLEN(env->enc) > 1 || *to >= SINGLE_BYTE_SIZE) {
6278         if (IS_NCCLASS_NOT(cc)) clear_not_flag_cclass(cc, env->enc);
6279         add_code_range(&(cc->mbuf), env, *to, *to);
6280       }
6281       else {
6282         if (IS_NCCLASS_NOT(cc)) {
6283           BITSET_CLEAR_BIT(bs, *to);
6284         }
6285         else
6286           BITSET_SET_BIT(bs, *to);
6287       }
6288     }
6289 #endif /* CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS */
6290   }
6291   else {
6292     int r, i, len;
6293     UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
6294     Node *snode = NULL_NODE;
6295
6296     if (onig_is_code_in_cc(env->enc, from, cc)
6297 #ifdef CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS
6298         && !IS_NCCLASS_NOT(cc)
6299 #endif
6300         ) {
6301       for (i = 0; i < to_len; i++) {
6302         len = ONIGENC_CODE_TO_MBC(env->enc, to[i], buf);
6303         if (i == 0) {
6304           snode = onig_node_new_str(buf, buf + len);
6305           CHECK_NULL_RETURN_MEMERR(snode);
6306
6307           /* char-class expanded multi-char only
6308              compare with string folded at match time. */
6309           NODE_STRING_SET_AMBIG(snode);
6310         }
6311         else {
6312           r = onig_node_str_cat(snode, buf, buf + len);
6313           if (r < 0) {
6314             onig_node_free(snode);
6315             return r;
6316           }
6317         }
6318       }
6319
6320       *(iarg->ptail) = onig_node_new_alt(snode, NULL_NODE);
6321       CHECK_NULL_RETURN_MEMERR(*(iarg->ptail));
6322       iarg->ptail = &(NODE_CDR((*(iarg->ptail))));
6323     }
6324   }
6325
6326   return 0;
6327 }
6328
6329 static int
6330 parse_exp(Node** np, OnigToken* tok, int term, UChar** src, UChar* end,
6331           ScanEnv* env)
6332 {
6333   int r, len, group = 0;
6334   Node* qn;
6335   Node** targetp;
6336
6337   *np = NULL;
6338   if (tok->type == (enum TokenSyms )term)
6339     goto end_of_token;
6340
6341   switch (tok->type) {
6342   case TK_ALT:
6343   case TK_EOT:
6344   end_of_token:
6345   *np = node_new_empty();
6346   return tok->type;
6347   break;
6348
6349   case TK_SUBEXP_OPEN:
6350     r = parse_enclosure(np, tok, TK_SUBEXP_CLOSE, src, end, env);
6351     if (r < 0) return r;
6352     if (r == 1) group = 1;
6353     else if (r == 2) { /* option only */
6354       Node* target;
6355       OnigOptionType prev = env->options;
6356
6357       env->options = ENCLOSURE_(*np)->o.options;
6358       r = fetch_token(tok, src, end, env);
6359       if (r < 0) return r;
6360       r = parse_subexp(&target, tok, term, src, end, env);
6361       env->options = prev;
6362       if (r < 0) {
6363         onig_node_free(target);
6364         return r;
6365       }
6366       NODE_BODY(*np) = target;
6367       return tok->type;
6368     }
6369     break;
6370
6371   case TK_SUBEXP_CLOSE:
6372     if (! IS_SYNTAX_BV(env->syntax, ONIG_SYN_ALLOW_UNMATCHED_CLOSE_SUBEXP))
6373       return ONIGERR_UNMATCHED_CLOSE_PARENTHESIS;
6374
6375     if (tok->escaped) goto tk_raw_byte;
6376     else goto tk_byte;
6377     break;
6378
6379   case TK_STRING:
6380   tk_byte:
6381     {
6382       *np = node_new_str(tok->backp, *src);
6383       CHECK_NULL_RETURN_MEMERR(*np);
6384
6385       while (1) {
6386         r = fetch_token(tok, src, end, env);
6387         if (r < 0) return r;
6388         if (r != TK_STRING) break;
6389
6390         r = onig_node_str_cat(*np, tok->backp, *src);
6391         if (r < 0) return r;
6392       }
6393
6394     string_end:
6395       targetp = np;
6396       goto repeat;
6397     }
6398     break;
6399
6400   case TK_RAW_BYTE:
6401   tk_raw_byte:
6402     {
6403       *np = node_new_str_raw_char((UChar )tok->u.c);
6404       CHECK_NULL_RETURN_MEMERR(*np);
6405       len = 1;
6406       while (1) {
6407         if (len >= ONIGENC_MBC_MINLEN(env->enc)) {
6408           if (len == enclen(env->enc, STR_(*np)->s)) {//should not enclen_end()
6409             r = fetch_token(tok, src, end, env);
6410             NODE_STRING_CLEAR_RAW(*np);
6411             goto string_end;
6412           }
6413         }
6414
6415         r = fetch_token(tok, src, end, env);
6416         if (r < 0) return r;
6417         if (r != TK_RAW_BYTE) {
6418           /* Don't use this, it is wrong for little endian encodings. */
6419 #ifdef USE_PAD_TO_SHORT_BYTE_CHAR
6420           int rem;
6421           if (len < ONIGENC_MBC_MINLEN(env->enc)) {
6422             rem = ONIGENC_MBC_MINLEN(env->enc) - len;
6423             (void )node_str_head_pad(STR_(*np), rem, (UChar )0);
6424             if (len + rem == enclen(env->enc, STR_(*np)->s)) {
6425               NODE_STRING_CLEAR_RAW(*np);
6426               goto string_end;
6427             }
6428           }
6429 #endif
6430           return ONIGERR_TOO_SHORT_MULTI_BYTE_STRING;
6431         }
6432
6433         r = node_str_cat_char(*np, (UChar )tok->u.c);
6434         if (r < 0) return r;
6435
6436         len++;
6437       }
6438     }
6439     break;
6440
6441   case TK_CODE_POINT:
6442     {
6443       UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
6444       int num = ONIGENC_CODE_TO_MBC(env->enc, tok->u.code, buf);
6445       if (num < 0) return num;
6446 #ifdef NUMBERED_CHAR_IS_NOT_CASE_AMBIG
6447       *np = node_new_str_raw(buf, buf + num);
6448 #else
6449       *np = node_new_str(buf, buf + num);
6450 #endif
6451       CHECK_NULL_RETURN_MEMERR(*np);
6452     }
6453     break;
6454
6455   case TK_QUOTE_OPEN:
6456     {
6457       OnigCodePoint end_op[2];
6458       UChar *qstart, *qend, *nextp;
6459
6460       end_op[0] = (OnigCodePoint )MC_ESC(env->syntax);
6461       end_op[1] = (OnigCodePoint )'E';
6462       qstart = *src;
6463       qend = find_str_position(end_op, 2, qstart, end, &nextp, env->enc);
6464       if (IS_NULL(qend)) {
6465         nextp = qend = end;
6466       }
6467       *np = node_new_str(qstart, qend);
6468       CHECK_NULL_RETURN_MEMERR(*np);
6469       *src = nextp;
6470     }
6471     break;
6472
6473   case TK_CHAR_TYPE:
6474     {
6475       switch (tok->u.prop.ctype) {
6476       case ONIGENC_CTYPE_WORD:
6477         *np = node_new_ctype(tok->u.prop.ctype, tok->u.prop.not, env->options);
6478         CHECK_NULL_RETURN_MEMERR(*np);
6479         break;
6480
6481       case ONIGENC_CTYPE_SPACE:
6482       case ONIGENC_CTYPE_DIGIT:
6483       case ONIGENC_CTYPE_XDIGIT:
6484         {
6485           CClassNode* cc;
6486
6487           *np = node_new_cclass();
6488           CHECK_NULL_RETURN_MEMERR(*np);
6489           cc = CCLASS_(*np);
6490           add_ctype_to_cc(cc, tok->u.prop.ctype, 0, env);
6491           if (tok->u.prop.not != 0) NCCLASS_SET_NOT(cc);
6492         }
6493         break;
6494
6495       default:
6496         return ONIGERR_PARSER_BUG;
6497         break;
6498       }
6499     }
6500     break;
6501
6502   case TK_CHAR_PROPERTY:
6503     r = parse_char_property(np, tok, src, end, env);
6504     if (r != 0) return r;
6505     break;
6506
6507   case TK_CC_OPEN:
6508     {
6509       CClassNode* cc;
6510
6511       r = parse_char_class(np, tok, src, end, env);
6512       if (r != 0) return r;
6513
6514       cc = CCLASS_(*np);
6515       if (IS_IGNORECASE(env->options)) {
6516         IApplyCaseFoldArg iarg;
6517
6518         iarg.env      = env;
6519         iarg.cc       = cc;
6520         iarg.alt_root = NULL_NODE;
6521         iarg.ptail    = &(iarg.alt_root);
6522
6523         r = ONIGENC_APPLY_ALL_CASE_FOLD(env->enc, env->case_fold_flag,
6524                                         i_apply_case_fold, &iarg);
6525         if (r != 0) {
6526           onig_node_free(iarg.alt_root);
6527           return r;
6528         }
6529         if (IS_NOT_NULL(iarg.alt_root)) {
6530           Node* work = onig_node_new_alt(*np, iarg.alt_root);
6531           if (IS_NULL(work)) {
6532             onig_node_free(iarg.alt_root);
6533             return ONIGERR_MEMORY;
6534           }
6535           *np = work;
6536         }
6537       }
6538     }
6539     break;
6540
6541   case TK_ANYCHAR:
6542     *np = node_new_anychar();
6543     CHECK_NULL_RETURN_MEMERR(*np);
6544     break;
6545
6546   case TK_ANYCHAR_ANYTIME:
6547     *np = node_new_anychar();
6548     CHECK_NULL_RETURN_MEMERR(*np);
6549     qn = node_new_quantifier(0, REPEAT_INFINITE, 0);
6550     CHECK_NULL_RETURN_MEMERR(qn);
6551     NODE_BODY(qn) = *np;
6552     *np = qn;
6553     break;
6554
6555   case TK_BACKREF:
6556     len = tok->u.backref.num;
6557     *np = node_new_backref(len,
6558                   (len > 1 ? tok->u.backref.refs : &(tok->u.backref.ref1)),
6559                   tok->u.backref.by_name,
6560 #ifdef USE_BACKREF_WITH_LEVEL
6561                            tok->u.backref.exist_level,
6562                            tok->u.backref.level,
6563 #endif
6564                            env);
6565     CHECK_NULL_RETURN_MEMERR(*np);
6566     break;
6567
6568 #ifdef USE_CALL
6569   case TK_CALL:
6570     {
6571       int gnum = tok->u.call.gnum;
6572
6573       *np = node_new_call(tok->u.call.name, tok->u.call.name_end,
6574                           gnum, tok->u.call.by_number);
6575       CHECK_NULL_RETURN_MEMERR(*np);
6576       env->num_call++;
6577       if (tok->u.call.by_number != 0 && gnum == 0) {
6578         env->has_call_zero = 1;
6579       }
6580     }
6581     break;
6582 #endif
6583
6584   case TK_ANCHOR:
6585     {
6586       int ascii_mode =
6587         IS_WORD_ASCII(env->options) && IS_WORD_ANCHOR_TYPE(tok->u.anchor) ? 1 : 0;
6588       *np = onig_node_new_anchor(tok->u.anchor, ascii_mode);
6589     }
6590     break;
6591
6592   case TK_OP_REPEAT:
6593   case TK_INTERVAL:
6594     if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_CONTEXT_INDEP_REPEAT_OPS)) {
6595       if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_CONTEXT_INVALID_REPEAT_OPS))
6596         return ONIGERR_TARGET_OF_REPEAT_OPERATOR_NOT_SPECIFIED;
6597       else
6598         *np = node_new_empty();
6599     }
6600     else {
6601       goto tk_byte;
6602     }
6603     break;
6604
6605   case TK_KEEP:
6606     r = node_new_keep(np, env);
6607     if (r < 0) return r;
6608     break;
6609
6610   case TK_GENERAL_NEWLINE:
6611     r = node_new_general_newline(np, env);
6612     if (r < 0) return r;
6613     break;
6614
6615   case TK_NO_NEWLINE:
6616     r = node_new_no_newline(np, env);
6617     if (r < 0) return r;
6618     break;
6619
6620   case TK_TRUE_ANYCHAR:
6621     r = node_new_true_anychar(np, env);
6622     if (r < 0) return r;
6623     break;
6624
6625   case TK_EXTENDED_GRAPHEME_CLUSTER:
6626     r = make_extended_grapheme_cluster(np, env);
6627     if (r < 0) return r;
6628     break;
6629
6630   default:
6631     return ONIGERR_PARSER_BUG;
6632     break;
6633   }
6634
6635   {
6636     targetp = np;
6637
6638   re_entry:
6639     r = fetch_token(tok, src, end, env);
6640     if (r < 0) return r;
6641
6642   repeat:
6643     if (r == TK_OP_REPEAT || r == TK_INTERVAL) {
6644       if (is_invalid_quantifier_target(*targetp))
6645         return ONIGERR_TARGET_OF_REPEAT_OPERATOR_INVALID;
6646
6647       qn = node_new_quantifier(tok->u.repeat.lower, tok->u.repeat.upper,
6648                                (r == TK_INTERVAL ? 1 : 0));
6649       CHECK_NULL_RETURN_MEMERR(qn);
6650       QUANT_(qn)->greedy = tok->u.repeat.greedy;
6651       r = set_quantifier(qn, *targetp, group, env);
6652       if (r < 0) {
6653         onig_node_free(qn);
6654         return r;
6655       }
6656
6657       if (tok->u.repeat.possessive != 0) {
6658         Node* en;
6659         en = node_new_enclosure(ENCLOSURE_STOP_BACKTRACK);
6660         if (IS_NULL(en)) {
6661           onig_node_free(qn);
6662           return ONIGERR_MEMORY;
6663         }
6664         NODE_BODY(en) = qn;
6665         qn = en;
6666       }
6667
6668       if (r == 0) {
6669         *targetp = qn;
6670       }
6671       else if (r == 1) {
6672         onig_node_free(qn);
6673       }
6674       else if (r == 2) { /* split case: /abc+/ */
6675         Node *tmp;
6676
6677         *targetp = node_new_list(*targetp, NULL);
6678         if (IS_NULL(*targetp)) {
6679           onig_node_free(qn);
6680           return ONIGERR_MEMORY;
6681         }
6682         tmp = NODE_CDR(*targetp) = node_new_list(qn, NULL);
6683         if (IS_NULL(tmp)) {
6684           onig_node_free(qn);
6685           return ONIGERR_MEMORY;
6686         }
6687         targetp = &(NODE_CAR(tmp));
6688       }
6689       goto re_entry;
6690     }
6691   }
6692
6693   return r;
6694 }
6695
6696 static int
6697 parse_branch(Node** top, OnigToken* tok, int term, UChar** src, UChar* end,
6698              ScanEnv* env)
6699 {
6700   int r;
6701   Node *node, **headp;
6702
6703   *top = NULL;
6704   r = parse_exp(&node, tok, term, src, end, env);
6705   if (r < 0) {
6706     onig_node_free(node);
6707     return r;
6708   }
6709
6710   if (r == TK_EOT || r == term || r == TK_ALT) {
6711     *top = node;
6712   }
6713   else {
6714     *top  = node_new_list(node, NULL);
6715     headp = &(NODE_CDR(*top));
6716     while (r != TK_EOT && r != term && r != TK_ALT) {
6717       r = parse_exp(&node, tok, term, src, end, env);
6718       if (r < 0) {
6719         onig_node_free(node);
6720         return r;
6721       }
6722
6723       if (NODE_TYPE(node) == NODE_LIST) {
6724         *headp = node;
6725         while (IS_NOT_NULL(NODE_CDR(node))) node = NODE_CDR(node);
6726         headp = &(NODE_CDR(node));
6727       }
6728       else {
6729         *headp = node_new_list(node, NULL);
6730         headp = &(NODE_CDR(*headp));
6731       }
6732     }
6733   }
6734
6735   return r;
6736 }
6737
6738 /* term_tok: TK_EOT or TK_SUBEXP_CLOSE */
6739 static int
6740 parse_subexp(Node** top, OnigToken* tok, int term, UChar** src, UChar* end,
6741              ScanEnv* env)
6742 {
6743   int r;
6744   Node *node, **headp;
6745
6746   *top = NULL;
6747   env->parse_depth++;
6748   if (env->parse_depth > ParseDepthLimit)
6749     return ONIGERR_PARSE_DEPTH_LIMIT_OVER;
6750   r = parse_branch(&node, tok, term, src, end, env);
6751   if (r < 0) {
6752     onig_node_free(node);
6753     return r;
6754   }
6755
6756   if (r == term) {
6757     *top = node;
6758   }
6759   else if (r == TK_ALT) {
6760     *top  = onig_node_new_alt(node, NULL);
6761     headp = &(NODE_CDR(*top));
6762     while (r == TK_ALT) {
6763       r = fetch_token(tok, src, end, env);
6764       if (r < 0) return r;
6765       r = parse_branch(&node, tok, term, src, end, env);
6766       if (r < 0) {
6767         onig_node_free(node);
6768         return r;
6769       }
6770       *headp = onig_node_new_alt(node, NULL);
6771       headp = &(NODE_CDR(*headp));
6772     }
6773
6774     if (tok->type != (enum TokenSyms )term)
6775       goto err;
6776   }
6777   else {
6778     onig_node_free(node);
6779   err:
6780     if (term == TK_SUBEXP_CLOSE)
6781       return ONIGERR_END_PATTERN_WITH_UNMATCHED_PARENTHESIS;
6782     else
6783       return ONIGERR_PARSER_BUG;
6784   }
6785
6786   env->parse_depth--;
6787   return r;
6788 }
6789
6790 static int
6791 parse_regexp(Node** top, UChar** src, UChar* end, ScanEnv* env)
6792 {
6793   int r;
6794   OnigToken tok;
6795
6796   r = fetch_token(&tok, src, end, env);
6797   if (r < 0) return r;
6798   r = parse_subexp(top, &tok, TK_EOT, src, end, env);
6799   if (r < 0) return r;
6800
6801   return 0;
6802 }
6803
6804 #ifdef USE_CALL
6805 static int
6806 make_call_zero_body(Node* node, ScanEnv* env, Node** rnode)
6807 {
6808   int r;
6809
6810   Node* x = node_new_memory(0 /* 0: is not named */);
6811   CHECK_NULL_RETURN_MEMERR(x);
6812
6813   NODE_BODY(x) = node;
6814   ENCLOSURE_(x)->m.regnum = 0;
6815   r = scan_env_set_mem_node(env, 0, x);
6816   if (r != 0) {
6817     onig_node_free(x);
6818     return r;
6819   }
6820
6821   *rnode = x;
6822   return 0;
6823 }
6824 #endif
6825
6826 extern int
6827 onig_parse_tree(Node** root, const UChar* pattern, const UChar* end,
6828                 regex_t* reg, ScanEnv* env)
6829 {
6830   int r;
6831   UChar* p;
6832
6833   names_clear(reg);
6834
6835   scan_env_clear(env);
6836   env->options        = reg->options;
6837   env->case_fold_flag = reg->case_fold_flag;
6838   env->enc            = reg->enc;
6839   env->syntax         = reg->syntax;
6840   env->pattern        = (UChar* )pattern;
6841   env->pattern_end    = (UChar* )end;
6842   env->reg            = reg;
6843
6844   *root = NULL;
6845
6846   if (! ONIGENC_IS_VALID_MBC_STRING(env->enc, pattern, end))
6847     return ONIGERR_INVALID_WIDE_CHAR_VALUE;
6848
6849   p = (UChar* )pattern;
6850   r = parse_regexp(root, &p, (UChar* )end, env);
6851
6852 #ifdef USE_CALL
6853   if (r != 0) return r;
6854
6855   if (env->has_call_zero != 0) {
6856     Node* zero_node;
6857     r = make_call_zero_body(*root, env, &zero_node);
6858     if (r != 0) return r;
6859
6860     *root = zero_node;
6861   }
6862 #endif
6863
6864   reg->num_mem = env->num_mem;
6865   return r;
6866 }
6867
6868 extern void
6869 onig_scan_env_set_error_string(ScanEnv* env, int ecode ARG_UNUSED,
6870                                UChar* arg, UChar* arg_end)
6871 {
6872   env->error     = arg;
6873   env->error_end = arg_end;
6874 }