/**********************************************************************

  regparse.c -  Oniguruma (regular expression library)

**********************************************************************/

/*-

 * Copyright (c) 2002-2018  K.Kosako  <sndgk393 AT ybb DOT ne DOT jp>

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND

 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE

 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

 * SUCH DAMAGE.

 */

#include "regparse.h"

#include "st.h"

#ifdef DEBUG_NODE_FREE

#include <stdio.h>

#endif

#define INIT_TAG_NAMES_ALLOC_NUM   5

#define WARN_BUFSIZE    256

#define CASE_FOLD_IS_APPLIED_INSIDE_NEGATIVE_CCLASS

#define IS_ALLOWED_CODE_IN_CALLOUT_NAME(c) \

  ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') || c == '_' /* || c == '!' */)

#define IS_ALLOWED_CODE_IN_CALLOUT_TAG_NAME(c) \

  ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') || c == '_')

OnigSyntaxType OnigSyntaxOniguruma = {

  (( SYN_GNU_REGEX_OP | ONIG_SYN_OP_QMARK_NON_GREEDY |

     ONIG_SYN_OP_ESC_OCTAL3 | ONIG_SYN_OP_ESC_X_HEX2 |

     ONIG_SYN_OP_ESC_X_BRACE_HEX8 | ONIG_SYN_OP_ESC_O_BRACE_OCTAL |

     ONIG_SYN_OP_ESC_CONTROL_CHARS |

     ONIG_SYN_OP_ESC_C_CONTROL )

   & ~ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END )

  , ( ONIG_SYN_OP2_QMARK_GROUP_EFFECT |

      ONIG_SYN_OP2_OPTION_RUBY |

      ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP | ONIG_SYN_OP2_ESC_K_NAMED_BACKREF |

      ONIG_SYN_OP2_QMARK_LPAREN_IF_ELSE |

      ONIG_SYN_OP2_QMARK_TILDE_ABSENT_GROUP |

      ONIG_SYN_OP2_QMARK_BRACE_CALLOUT_CONTENTS |

      ONIG_SYN_OP2_ASTERISK_CALLOUT_NAME    |

      ONIG_SYN_OP2_ESC_X_Y_GRAPHEME_CLUSTER |

      ONIG_SYN_OP2_ESC_CAPITAL_R_GENERAL_NEWLINE |

      ONIG_SYN_OP2_ESC_CAPITAL_N_O_SUPER_DOT |

      ONIG_SYN_OP2_ESC_CAPITAL_K_KEEP |

      ONIG_SYN_OP2_ESC_G_SUBEXP_CALL |

      ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY  |

      ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT |

      ONIG_SYN_OP2_PLUS_POSSESSIVE_REPEAT |

      ONIG_SYN_OP2_CCLASS_SET_OP | ONIG_SYN_OP2_ESC_CAPITAL_C_BAR_CONTROL |

      ONIG_SYN_OP2_ESC_CAPITAL_M_BAR_META | ONIG_SYN_OP2_ESC_V_VTAB |

      ONIG_SYN_OP2_ESC_H_XDIGIT | ONIG_SYN_OP2_ESC_U_HEX4 )

  , ( SYN_GNU_REGEX_BV | 

      ONIG_SYN_ALLOW_INTERVAL_LOW_ABBREV |

      ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND |

      ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP |

      ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME |

      ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY |

      ONIG_SYN_WARN_CC_OP_NOT_ESCAPED |

      ONIG_SYN_WARN_REDUNDANT_NESTED_REPEAT )

  , ONIG_OPTION_NONE

  ,

  {

      (OnigCodePoint )'\\'                       /* esc */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar '.'  */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anytime '*'  */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* zero or one time '?' */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* one or more time '+' */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar anytime */

  }

};

OnigSyntaxType OnigSyntaxRuby = {

  (( SYN_GNU_REGEX_OP | ONIG_SYN_OP_QMARK_NON_GREEDY |

     ONIG_SYN_OP_ESC_OCTAL3 | ONIG_SYN_OP_ESC_X_HEX2 |

     ONIG_SYN_OP_ESC_X_BRACE_HEX8 | ONIG_SYN_OP_ESC_O_BRACE_OCTAL |

     ONIG_SYN_OP_ESC_CONTROL_CHARS |

     ONIG_SYN_OP_ESC_C_CONTROL )

   & ~ONIG_SYN_OP_ESC_LTGT_WORD_BEGIN_END )

  , ( ONIG_SYN_OP2_QMARK_GROUP_EFFECT |

      ONIG_SYN_OP2_OPTION_RUBY |

      ONIG_SYN_OP2_QMARK_LT_NAMED_GROUP | ONIG_SYN_OP2_ESC_K_NAMED_BACKREF |

      ONIG_SYN_OP2_QMARK_LPAREN_IF_ELSE |

      ONIG_SYN_OP2_QMARK_TILDE_ABSENT_GROUP |

      ONIG_SYN_OP2_ESC_X_Y_GRAPHEME_CLUSTER |

      ONIG_SYN_OP2_ESC_CAPITAL_R_GENERAL_NEWLINE |

      ONIG_SYN_OP2_ESC_CAPITAL_K_KEEP |

      ONIG_SYN_OP2_ESC_G_SUBEXP_CALL |

      ONIG_SYN_OP2_ESC_P_BRACE_CHAR_PROPERTY  |

      ONIG_SYN_OP2_ESC_P_BRACE_CIRCUMFLEX_NOT |

      ONIG_SYN_OP2_PLUS_POSSESSIVE_REPEAT |

      ONIG_SYN_OP2_CCLASS_SET_OP | ONIG_SYN_OP2_ESC_CAPITAL_C_BAR_CONTROL |

      ONIG_SYN_OP2_ESC_CAPITAL_M_BAR_META | ONIG_SYN_OP2_ESC_V_VTAB |

      ONIG_SYN_OP2_ESC_H_XDIGIT | ONIG_SYN_OP2_ESC_U_HEX4 )

  , ( SYN_GNU_REGEX_BV | 

      ONIG_SYN_ALLOW_INTERVAL_LOW_ABBREV |

      ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND |

      ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP |

      ONIG_SYN_ALLOW_MULTIPLEX_DEFINITION_NAME |

      ONIG_SYN_FIXED_INTERVAL_IS_GREEDY_ONLY |

      ONIG_SYN_WARN_CC_OP_NOT_ESCAPED |

      ONIG_SYN_WARN_REDUNDANT_NESTED_REPEAT )

  , ONIG_OPTION_NONE

  ,

  {

      (OnigCodePoint )'\\'                       /* esc */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar '.'  */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anytime '*'  */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* zero or one time '?' */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* one or more time '+' */

    , (OnigCodePoint )ONIG_INEFFECTIVE_META_CHAR /* anychar anytime */

  }

};

OnigSyntaxType*  OnigDefaultSyntax = ONIG_SYNTAX_ONIGURUMA;

extern void onig_null_warn(const char* s ARG_UNUSED) { }

#ifdef DEFAULT_WARN_FUNCTION

static OnigWarnFunc onig_warn = (OnigWarnFunc )DEFAULT_WARN_FUNCTION;

#else

static OnigWarnFunc onig_warn = onig_null_warn;

#endif

#ifdef DEFAULT_VERB_WARN_FUNCTION

static OnigWarnFunc onig_verb_warn = (OnigWarnFunc )DEFAULT_VERB_WARN_FUNCTION;

#else

static OnigWarnFunc onig_verb_warn = onig_null_warn;

#endif

extern void onig_set_warn_func(OnigWarnFunc f)

{

  onig_warn = f;

}

extern void onig_set_verb_warn_func(OnigWarnFunc f)

{

  onig_verb_warn = f;

}

extern void

onig_warning(const char* s)

{

  if (onig_warn == onig_null_warn) return ;

  (*onig_warn)(s);

}

#define DEFAULT_MAX_CAPTURE_NUM   32767

static int MaxCaptureNum = DEFAULT_MAX_CAPTURE_NUM;

extern int

onig_set_capture_num_limit(int num)

{

  if (num < 0) return -1;

  MaxCaptureNum = num;

  return 0;

}

static unsigned int ParseDepthLimit = DEFAULT_PARSE_DEPTH_LIMIT;

extern unsigned int

onig_get_parse_depth_limit(void)

{

  return ParseDepthLimit;

}

extern int

onig_set_parse_depth_limit(unsigned int depth)

{

  if (depth == 0)

    ParseDepthLimit = DEFAULT_PARSE_DEPTH_LIMIT;

  else

    ParseDepthLimit = depth;

  return 0;

}

static int

positive_int_multiply(int x, int y)

{

  if (x == 0 || y == 0) return 0;

  if (x < INT_MAX / y)

    return x * y;

  else

    return -1;

}

static void

bbuf_free(BBuf* bbuf)

{

  if (IS_NOT_NULL(bbuf)) {

    if (IS_NOT_NULL(bbuf->p)) xfree(bbuf->p);

    xfree(bbuf);

  }

}

static int

bbuf_clone(BBuf** rto, BBuf* from)

{

  int r;

  BBuf *to;

  *rto = to = (BBuf* )xmalloc(sizeof(BBuf));

  CHECK_NULL_RETURN_MEMERR(to);

  r = BB_INIT(to, from->alloc);

  if (r != 0) {

    xfree(to->p);

    *rto = 0;

    return r;

  }

  to->used = from->used;

  xmemcpy(to->p, from->p, from->used);

  return 0;

}

static int backref_rel_to_abs(int rel_no, ScanEnv* env)

{

  if (rel_no > 0) {

    return env->num_mem + rel_no;

  }

  else {

    return env->num_mem + 1 + rel_no;

  }

}

#define OPTION_ON(v,f)     ((v) |= (f))

#define OPTION_OFF(v,f)    ((v) &= ~(f))

#define OPTION_NEGATE(v,f,negative)    (negative) ? ((v) &= ~(f)) : ((v) |= (f))

#define MBCODE_START_POS(enc) \

  (OnigCodePoint )(ONIGENC_MBC_MINLEN(enc) > 1 ? 0 : 0x80)

#define SET_ALL_MULTI_BYTE_RANGE(enc, pbuf) \

  add_code_range_to_buf(pbuf, MBCODE_START_POS(enc), ~((OnigCodePoint )0))

#define ADD_ALL_MULTI_BYTE_RANGE(enc, mbuf) do {\

  if (! ONIGENC_IS_SINGLEBYTE(enc)) {\

    r = SET_ALL_MULTI_BYTE_RANGE(enc, &(mbuf));\

    if (r != 0) return r;\

  }\

} while (0)

#define BITSET_IS_EMPTY(bs,empty) do {\

  int i;\

  empty = 1;\

  for (i = 0; i < (int )BITSET_SIZE; i++) {\

    if ((bs)[i] != 0) {\

      empty = 0; break;\

    }\

  }\

} while (0)

static void

bitset_set_range(BitSetRef bs, int from, int to)

{

  int i;

  for (i = from; i <= to && i < SINGLE_BYTE_SIZE; i++) {

    BITSET_SET_BIT(bs, i);

  }

}

#if 0

static void

bitset_set_all(BitSetRef bs)

{

  int i;

  for (i = 0; i < BITSET_SIZE; i++) { bs[i] = ~((Bits )0); }

}

#endif

static void

bitset_invert(BitSetRef bs)

{

  int i;

  for (i = 0; i < (int )BITSET_SIZE; i++) { bs[i] = ~(bs[i]); }

}

static void

bitset_invert_to(BitSetRef from, BitSetRef to)

{

  int i;

  for (i = 0; i < (int )BITSET_SIZE; i++) { to[i] = ~(from[i]); }

}

static void

bitset_and(BitSetRef dest, BitSetRef bs)

{

  int i;

  for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] &= bs[i]; }

}

static void

bitset_or(BitSetRef dest, BitSetRef bs)

{

  int i;

  for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] |= bs[i]; }

}

static void

bitset_copy(BitSetRef dest, BitSetRef bs)

{

  int i;

  for (i = 0; i < (int )BITSET_SIZE; i++) { dest[i] = bs[i]; }

}

extern int

onig_strncmp(const UChar* s1, const UChar* s2, int n)

{

  int x;

  while (n-- > 0) {

    x = *s2++ - *s1++;

    if (x) return x;

  }

  return 0;

}

extern void

onig_strcpy(UChar* dest, const UChar* src, const UChar* end)

{

  int len = (int )(end - src);

  if (len > 0) {

    xmemcpy(dest, src, len);

    dest[len] = (UChar )0;

  }

}

static int

save_entry(ScanEnv* env, enum SaveType type, int* id)

{

  int nid = env->save_num;

#if 0

  if (IS_NULL(env->saves)) {

    int n = 10;

    env->saves = (SaveItem* )xmalloc(sizeof(SaveItem) * n);

    CHECK_NULL_RETURN_MEMERR(env->saves);

    env->save_alloc_num = n;

  }

  else if (env->save_alloc_num <= nid) {

    int n = env->save_alloc_num * 2;

    SaveItem* p = (SaveItem* )xrealloc(env->saves, sizeof(SaveItem) * n);

    CHECK_NULL_RETURN_MEMERR(p);

    env->saves = p;

    env->save_alloc_num = n;

  }

  env->saves[nid].type = type;

#endif

  env->save_num++;

  *id = nid;

  return 0;

}

/* scan pattern methods */

#define PEND_VALUE   0

#define PFETCH_READY  UChar* pfetch_prev

#define PEND         (p < end ?  0 : 1)

#define PUNFETCH     p = pfetch_prev

#define PINC       do { \

  pfetch_prev = p; \

  p += ONIGENC_MBC_ENC_LEN(enc, p); \

} while (0)

#define PFETCH(c)  do { \

  c = ONIGENC_MBC_TO_CODE(enc, p, end); \

  pfetch_prev = p; \

  p += ONIGENC_MBC_ENC_LEN(enc, p); \

} while (0)

#define PINC_S     do { \

  p += ONIGENC_MBC_ENC_LEN(enc, p); \

} while (0)

#define PFETCH_S(c) do { \

  c = ONIGENC_MBC_TO_CODE(enc, p, end); \

  p += ONIGENC_MBC_ENC_LEN(enc, p); \

} while (0)

#define PPEEK        (p < end ? ONIGENC_MBC_TO_CODE(enc, p, end) : PEND_VALUE)

#define PPEEK_IS(c)  (PPEEK == (OnigCodePoint )c)

static UChar*

strcat_capa(UChar* dest, UChar* dest_end, const UChar* src, const UChar* src_end,

            int capa)

{

  UChar* r;

  if (dest)

    r = (UChar* )xrealloc(dest, capa + 1);

  else

    r = (UChar* )xmalloc(capa + 1);

  CHECK_NULL_RETURN(r);

  onig_strcpy(r + (dest_end - dest), src, src_end);

  return r;

}

/* dest on static area */

static UChar*

strcat_capa_from_static(UChar* dest, UChar* dest_end,

                        const UChar* src, const UChar* src_end, int capa)

{

  UChar* r;

  r = (UChar* )xmalloc(capa + 1);

  CHECK_NULL_RETURN(r);

  onig_strcpy(r, dest, dest_end);

  onig_strcpy(r + (dest_end - dest), src, src_end);

  return r;

}

#ifdef USE_ST_LIBRARY

typedef struct {

  UChar* s;

  UChar* end;

} st_str_end_key;

static int

str_end_cmp(st_str_end_key* x, st_str_end_key* y)

{

  UChar *p, *q;

  int c;

  if ((x->end - x->s) != (y->end - y->s))

    return 1;

  p = x->s;

  q = y->s;

  while (p < x->end) {

    c = (int )*p - (int )*q;

    if (c != 0) return c;

    p++; q++;

  }

  return 0;

}

static int

str_end_hash(st_str_end_key* x)

{

  UChar *p;

  int val = 0;

  p = x->s;

  while (p < x->end) {

    val = val * 997 + (int )*p++;

  }

  return val + (val >> 5);

}

extern hash_table_type*

onig_st_init_strend_table_with_size(int size)

{

  static struct st_hash_type hashType = {

    str_end_cmp,

    str_end_hash,

  };

  return (hash_table_type* )

           onig_st_init_table_with_size(&hashType, size);

}

extern int

onig_st_lookup_strend(hash_table_type* table, const UChar* str_key,

                      const UChar* end_key, hash_data_type *value)

{

  st_str_end_key key;

  key.s   = (UChar* )str_key;

  key.end = (UChar* )end_key;

  return onig_st_lookup(table, (st_data_t )(&key), value);

}

extern int

onig_st_insert_strend(hash_table_type* table, const UChar* str_key,

                      const UChar* end_key, hash_data_type value)

{

  st_str_end_key* key;

  int result;

  key = (st_str_end_key* )xmalloc(sizeof(st_str_end_key));

  CHECK_NULL_RETURN_MEMERR(key);

  key->s   = (UChar* )str_key;

  key->end = (UChar* )end_key;

  result = onig_st_insert(table, (st_data_t )key, value);

  if (result) {

    xfree(key);

  }

  return result;

}

typedef struct {

  OnigEncoding enc;

  int    type; /* callout type: single or not */

  UChar* s;

  UChar* end;

} st_callout_name_key;

static int

callout_name_table_cmp(st_callout_name_key* x, st_callout_name_key* y)

{

  UChar *p, *q;

  int c;

  if (x->enc  != y->enc)  return 1;

  if (x->type != y->type) return 1;

  if ((x->end - x->s) != (y->end - y->s))

    return 1;

  p = x->s;

  q = y->s;

  while (p < x->end) {

    c = (int )*p - (int )*q;

    if (c != 0) return c;

    p++; q++;

  }

  return 0;

}

static int

callout_name_table_hash(st_callout_name_key* x)

{

  UChar *p;

  int val = 0;

  p = x->s;

  while (p < x->end) {

    val = val * 997 + (int )*p++;

  }

  /* use intptr_t for escape warning in Windows */

  return val + (val >> 5) + ((intptr_t )x->enc & 0xffff) + x->type;

}

extern hash_table_type*

onig_st_init_callout_name_table_with_size(int size)

{

  static struct st_hash_type hashType = {

    callout_name_table_cmp,

    callout_name_table_hash,

  };

  return (hash_table_type* )

           onig_st_init_table_with_size(&hashType, size);

}

extern int

onig_st_lookup_callout_name_table(hash_table_type* table,

                                  OnigEncoding enc,

                                  int type,

                                  const UChar* str_key,

                                  const UChar* end_key,

                                  hash_data_type *value)

{

  st_callout_name_key key;

  key.enc  = enc;

  key.type = type;

  key.s    = (UChar* )str_key;

  key.end  = (UChar* )end_key;

  return onig_st_lookup(table, (st_data_t )(&key), value);

}

static int

st_insert_callout_name_table(hash_table_type* table,

                             OnigEncoding enc, int type,

                             UChar* str_key, UChar* end_key,

                             hash_data_type value)

{

  st_callout_name_key* key;

  int result;

  key = (st_callout_name_key* )xmalloc(sizeof(st_callout_name_key));

  CHECK_NULL_RETURN_MEMERR(key);

  /* key->s: don't duplicate, because str_key is duped in callout_name_entry() */

  key->enc  = enc;

  key->type = type;

  key->s    = str_key;

  key->end  = end_key;

  result = onig_st_insert(table, (st_data_t )key, value);

  if (result) {

    xfree(key);

  }

  return result;

}

#endif /* USE_ST_LIBRARY */

#define INIT_NAME_BACKREFS_ALLOC_NUM   8

typedef struct {

  UChar* name;

  int    name_len;   /* byte length */

  int    back_num;   /* number of backrefs */

  int    back_alloc;

  int    back_ref1;

  int*   back_refs;

} NameEntry;

#ifdef USE_ST_LIBRARY

#define INIT_NAMES_ALLOC_NUM    5

typedef st_table  NameTable;

typedef st_data_t HashDataType;   /* 1.6 st.h doesn't define st_data_t type */

#define NAMEBUF_SIZE    24

#define NAMEBUF_SIZE_1  25

#ifdef ONIG_DEBUG

static int

i_print_name_entry(UChar* key, NameEntry* e, void* arg)

{

  int i;

  FILE* fp = (FILE* )arg;

  fprintf(fp, "%s: ", e->name);

  if (e->back_num == 0)

    fputs("-", fp);

  else if (e->back_num == 1)

    fprintf(fp, "%d", e->back_ref1);

  else {

    for (i = 0; i < e->back_num; i++) {

      if (i > 0) fprintf(fp, ", ");

      fprintf(fp, "%d", e->back_refs[i]);

    }

  }

  fputs("\n", fp);

  return ST_CONTINUE;

}

extern int

onig_print_names(FILE* fp, regex_t* reg)

{

  NameTable* t = (NameTable* )reg->name_table;

  if (IS_NOT_NULL(t)) {

    fprintf(fp, "name table\n");

    onig_st_foreach(t, i_print_name_entry, (HashDataType )fp);

    fputs("\n", fp);

  }

  return 0;

}

#endif /* ONIG_DEBUG */

static int

i_free_name_entry(UChar* key, NameEntry* e, void* arg ARG_UNUSED)

{

  xfree(e->name);

  if (IS_NOT_NULL(e->back_refs)) xfree(e->back_refs);

  xfree(key);

  xfree(e);

  return ST_DELETE;

}

static int

names_clear(regex_t* reg)

{

  NameTable* t = (NameTable* )reg->name_table;

  if (IS_NOT_NULL(t)) {

    onig_st_foreach(t, i_free_name_entry, 0);

  }

  return 0;

}

extern int

onig_names_free(regex_t* reg)

{

  int r;

  NameTable* t;

  r = names_clear(reg);

  if (r != 0) return r;

  t = (NameTable* )reg->name_table;

  if (IS_NOT_NULL(t)) onig_st_free_table(t);

  reg->name_table = (void* )NULL;

  return 0;

}

static NameEntry*

name_find(regex_t* reg, const UChar* name, const UChar* name_end)

{

  NameEntry* e;

  NameTable* t = (NameTable* )reg->name_table;

  e = (NameEntry* )NULL;

  if (IS_NOT_NULL(t)) {

    onig_st_lookup_strend(t, name, name_end, (HashDataType* )((void* )(&e)));

  }

  return e;

}

typedef struct {

  int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*);

  regex_t* reg;

  void* arg;

  int ret;

  OnigEncoding enc;

} INamesArg;

static int

i_names(UChar* key ARG_UNUSED, NameEntry* e, INamesArg* arg)

{

  int r = (*(arg->func))(e->name,

                         e->name + e->name_len,

                         e->back_num,

                         (e->back_num > 1 ? e->back_refs : &(e->back_ref1)),

                         arg->reg, arg->arg);

  if (r != 0) {

    arg->ret = r;

    return ST_STOP;

  }

  return ST_CONTINUE;

}

extern int

onig_foreach_name(regex_t* reg,

  int (*func)(const UChar*, const UChar*,int,int*,regex_t*,void*), void* arg)

{

  INamesArg narg;

  NameTable* t = (NameTable* )reg->name_table;

  narg.ret = 0;

  if (IS_NOT_NULL(t)) {

    narg.func = func;

    narg.reg  = reg;

    narg.arg  = arg;

    narg.enc  = reg->enc; /* should be pattern encoding. */

    onig_st_foreach(t, i_names, (HashDataType )&narg);

  }

  return narg.ret;

}

static int

i_renumber_name(UChar* key ARG_UNUSED, NameEntry* e, GroupNumRemap* map)

{

  int i;

  if (e->back_num > 1) {

    for (i = 0; i < e->back_num; i++) {

      e->back_refs[i] = map[e->back_refs[i]].new_val;

    }

  }

  else if (e->back_num == 1) {

    e->back_ref1 = map[e->back_ref1].new_val;

  }

  return ST_CONTINUE;

}

extern int

onig_renumber_name_table(regex_t* reg, GroupNumRemap* map)

{

  NameTable* t = (NameTable* )reg->name_table;

  if (IS_NOT_NULL(t)) {

    onig_st_foreach(t, i_renumber_name, (HashDataType )map);

  }

  return 0;

}

extern int

onig_number_of_names(regex_t* reg)

{

  NameTable* t = (NameTable* )reg->name_table;

  if (IS_NOT_NULL(t))

    return t->num_entries;

  else

    return 0;

}

#else  /* USE_ST_LIBRARY */

#define INIT_NAMES_ALLOC_NUM    8

typedef struct {

  NameEntry* e;

  int        num;

  int        alloc;

} NameTable;

#ifdef ONIG_DEBUG

extern int

onig_print_names(FILE* fp, regex_t* reg)

{

  int i, j;

  NameEntry* e;

  NameTable* t = (NameTable* )reg->name_table;

  if (IS_NOT_NULL(t) && t->num > 0) {

    fprintf(fp, "name table\n");

    for (i = 0; i < t->num; i++) {

      e = &(t->e[i]);

      fprintf(fp, "%s: ", e->name);

      if (e->back_num == 0) {

        fputs("-", fp);

      }

      else if (e->back_num == 1) {

        fprintf(fp, "%d", e->back_ref1);

      }

      else {

        for (j = 0; j < e->back_num; j++) {

          if (j > 0) fprintf(fp, ", ");

          fprintf(fp, "%d", e->back_refs[j]);

        }

      }

      fputs("\n", fp);

    }

    fputs("\n", fp);

  }

  return 0;

}

#endif

static int

names_clear(regex_t* reg)

{

  int i;

  NameEntry* e;

  NameTable* t = (NameTable* )reg->name_table;

  if (IS_NOT_NULL(t)) {

    for (i = 0; i < t->num; i++) {

      e = &(t->e[i]);

      if (IS_NOT_NULL(e->name)) {

        xfree(e->name);

        e->name       = NULL;

        e->name_len   = 0;

        e->back_num   = 0;

        e->back_alloc = 0;

        if (IS_NOT_NULL(e->back_refs)) xfree(e->back_refs);

        e->back_refs = (int* )NULL;

      }

    }

    if (IS_NOT_NULL(t->e)) {

      xfree(t->e);

      t->e = NULL;