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

  regexec.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 "regint.h"

#define IS_MBC_WORD_ASCII_MODE(enc,s,end,mode) \

  ((mode) == 0 ? ONIGENC_IS_MBC_WORD(enc,s,end) : ONIGENC_IS_MBC_WORD_ASCII(enc,s,end))

#ifdef USE_CRNL_AS_LINE_TERMINATOR

#define ONIGENC_IS_MBC_CRNL(enc,p,end) \

  (ONIGENC_MBC_TO_CODE(enc,p,end) == 13 && \

   ONIGENC_IS_MBC_NEWLINE(enc,(p+enclen(enc,p)),end))

#endif

#define CHECK_INTERRUPT_IN_MATCH

#ifdef USE_CALLOUT

typedef struct {

  int last_match_at_call_counter;

  struct {

    OnigType  type;

    OnigValue val;

  } slot[ONIG_CALLOUT_DATA_SLOT_NUM];

} CalloutData;

#endif

struct OnigMatchParamStruct {

  unsigned int    match_stack_limit;

  unsigned long   retry_limit_in_match;

#ifdef USE_CALLOUT

  OnigCalloutFunc progress_callout_of_contents;

  OnigCalloutFunc retraction_callout_of_contents;

  int             match_at_call_counter;

  void*           callout_user_data;

  CalloutData*    callout_data;

  int             callout_data_alloc_num;

#endif

};

extern int

onig_set_match_stack_limit_size_of_match_param(OnigMatchParam* param,

                                               unsigned int limit)

{

  param->match_stack_limit = limit;

  return ONIG_NORMAL;

}

extern int

onig_set_retry_limit_in_match_of_match_param(OnigMatchParam* param,

                                             unsigned long limit)

{

  param->retry_limit_in_match = limit;

  return ONIG_NORMAL;

}

extern int

onig_set_progress_callout_of_match_param(OnigMatchParam* param, OnigCalloutFunc f)

{

#ifdef USE_CALLOUT

  param->progress_callout_of_contents = f;

  return ONIG_NORMAL;

#else

  return ONIG_NO_SUPPORT_CONFIG;

#endif

}

extern int

onig_set_retraction_callout_of_match_param(OnigMatchParam* param, OnigCalloutFunc f)

{

#ifdef USE_CALLOUT

  param->retraction_callout_of_contents = f;

  return ONIG_NORMAL;

#else

  return ONIG_NO_SUPPORT_CONFIG;

#endif

}

extern int

onig_set_callout_user_data_of_match_param(OnigMatchParam* param, void* user_data)

{

#ifdef USE_CALLOUT

  param->callout_user_data = user_data;

  return ONIG_NORMAL;

#else

  return ONIG_NO_SUPPORT_CONFIG;

#endif

}

typedef struct {

  void* stack_p;

  int   stack_n;

  OnigOptionType options;

  OnigRegion*    region;

  int            ptr_num;

  const UChar*   start;   /* search start position (for \G: BEGIN_POSITION) */

  unsigned int   match_stack_limit;

  unsigned long  retry_limit_in_match;

  OnigMatchParam* mp;

#ifdef USE_FIND_LONGEST_SEARCH_ALL_OF_RANGE

  int    best_len;      /* for ONIG_OPTION_FIND_LONGEST */

  UChar* best_s;

#endif

} MatchArg;

#ifdef ONIG_DEBUG

/* arguments type */

typedef enum {

  ARG_SPECIAL =  -1,

  ARG_NON     =   0,

  ARG_RELADDR =   1,

  ARG_ABSADDR =   2,

  ARG_LENGTH  =   3,

  ARG_MEMNUM  =   4,

  ARG_OPTION  =   5,

  ARG_MODE    =   6

} OpArgType;

typedef struct {

  short int opcode;

  char*     name;

  OpArgType arg_type;

} OpInfoType;

static OpInfoType OpInfo[] = {

  { OP_FINISH,            "finish",          ARG_NON },

  { OP_END,               "end",             ARG_NON },

  { OP_EXACT1,            "exact1",          ARG_SPECIAL },

  { OP_EXACT2,            "exact2",          ARG_SPECIAL },

  { OP_EXACT3,            "exact3",          ARG_SPECIAL },

  { OP_EXACT4,            "exact4",          ARG_SPECIAL },

  { OP_EXACT5,            "exact5",          ARG_SPECIAL },

  { OP_EXACTN,            "exactn",          ARG_SPECIAL },

  { OP_EXACTMB2N1,        "exactmb2-n1",     ARG_SPECIAL },

  { OP_EXACTMB2N2,        "exactmb2-n2",     ARG_SPECIAL },

  { OP_EXACTMB2N3,        "exactmb2-n3",     ARG_SPECIAL },

  { OP_EXACTMB2N,         "exactmb2-n",      ARG_SPECIAL },

  { OP_EXACTMB3N,         "exactmb3n"  ,     ARG_SPECIAL },

  { OP_EXACTMBN,          "exactmbn",        ARG_SPECIAL },

  { OP_EXACT1_IC,         "exact1-ic",       ARG_SPECIAL },

  { OP_EXACTN_IC,         "exactn-ic",       ARG_SPECIAL },

  { OP_CCLASS,            "cclass",          ARG_SPECIAL },

  { OP_CCLASS_MB,         "cclass-mb",       ARG_SPECIAL },

  { OP_CCLASS_MIX,        "cclass-mix",      ARG_SPECIAL },

  { OP_CCLASS_NOT,        "cclass-not",      ARG_SPECIAL },

  { OP_CCLASS_MB_NOT,     "cclass-mb-not",   ARG_SPECIAL },

  { OP_CCLASS_MIX_NOT,    "cclass-mix-not",  ARG_SPECIAL },

#ifdef USE_OP_CCLASS_NODE

  { OP_CCLASS_NODE,       "cclass-node",     ARG_SPECIAL },

#endif

  { OP_ANYCHAR,           "anychar",         ARG_NON },

  { OP_ANYCHAR_ML,        "anychar-ml",      ARG_NON },

  { OP_ANYCHAR_STAR,      "anychar*",        ARG_NON },

  { OP_ANYCHAR_ML_STAR,   "anychar-ml*",     ARG_NON },

  { OP_ANYCHAR_STAR_PEEK_NEXT, "anychar*-peek-next", ARG_SPECIAL },

  { OP_ANYCHAR_ML_STAR_PEEK_NEXT, "anychar-ml*-peek-next", ARG_SPECIAL },

  { OP_WORD,                "word",            ARG_NON },

  { OP_WORD_ASCII,          "word-ascii",      ARG_NON },

  { OP_NO_WORD,             "not-word",        ARG_NON },

  { OP_NO_WORD_ASCII,       "not-word-ascii",  ARG_NON },

  { OP_WORD_BOUNDARY,       "word-boundary",     ARG_MODE },

  { OP_NO_WORD_BOUNDARY,    "not-word-boundary", ARG_MODE },

  { OP_WORD_BEGIN,          "word-begin",      ARG_MODE },

  { OP_WORD_END,            "word-end",        ARG_MODE },

  { OP_EXTENDED_GRAPHEME_CLUSTER_BOUNDARY, "extended-grapheme-cluster-boundary", ARG_NON },

  { OP_NO_EXTENDED_GRAPHEME_CLUSTER_BOUNDARY, "no-extended-grapheme-cluster-boundary", ARG_NON },

  { OP_BEGIN_BUF,           "begin-buf",       ARG_NON },

  { OP_END_BUF,             "end-buf",         ARG_NON },

  { OP_BEGIN_LINE,          "begin-line",      ARG_NON },

  { OP_END_LINE,            "end-line",        ARG_NON },

  { OP_SEMI_END_BUF,        "semi-end-buf",    ARG_NON },

  { OP_BEGIN_POSITION,      "begin-position",  ARG_NON },

  { OP_BACKREF1,            "backref1",             ARG_NON },

  { OP_BACKREF2,            "backref2",             ARG_NON },

  { OP_BACKREF_N,            "backref-n",           ARG_MEMNUM  },

  { OP_BACKREF_N_IC,         "backref-n-ic",        ARG_SPECIAL },

  { OP_BACKREF_MULTI,       "backref_multi",        ARG_SPECIAL },

  { OP_BACKREF_MULTI_IC,    "backref_multi-ic",     ARG_SPECIAL },

  { OP_BACKREF_WITH_LEVEL,  "backref_with_level",   ARG_SPECIAL },

  { OP_BACKREF_CHECK,       "backref_check",        ARG_SPECIAL },

  { OP_BACKREF_CHECK_WITH_LEVEL, "backref_check_with_level", ARG_SPECIAL },

  { OP_MEMORY_START_PUSH,   "mem-start-push",       ARG_MEMNUM  },

  { OP_MEMORY_START,        "mem-start",            ARG_MEMNUM  },

  { OP_MEMORY_END_PUSH,     "mem-end-push",         ARG_MEMNUM  },

  { OP_MEMORY_END_PUSH_REC, "mem-end-push-rec",     ARG_MEMNUM  },

  { OP_MEMORY_END,          "mem-end",              ARG_MEMNUM  },

  { OP_MEMORY_END_REC,      "mem-end-rec",          ARG_MEMNUM  },

  { OP_SET_OPTION_PUSH,     "set-option-push",      ARG_OPTION  },

  { OP_SET_OPTION,          "set-option",           ARG_OPTION  },

  { OP_FAIL,                "fail",                 ARG_NON },

  { OP_JUMP,                "jump",                 ARG_RELADDR },

  { OP_PUSH,                "push",                 ARG_RELADDR },

  { OP_PUSH_SUPER,          "push-super",           ARG_RELADDR },

  { OP_POP_OUT,             "pop-out",              ARG_NON },

  { OP_PUSH_OR_JUMP_EXACT1, "push-or-jump-e1",      ARG_SPECIAL },

  { OP_PUSH_IF_PEEK_NEXT,   "push-if-peek-next",    ARG_SPECIAL },

  { OP_REPEAT,              "repeat",               ARG_SPECIAL },

  { OP_REPEAT_NG,           "repeat-ng",            ARG_SPECIAL },

  { OP_REPEAT_INC,          "repeat-inc",           ARG_MEMNUM  },

  { OP_REPEAT_INC_NG,       "repeat-inc-ng",        ARG_MEMNUM  },

  { OP_REPEAT_INC_SG,       "repeat-inc-sg",        ARG_MEMNUM  },

  { OP_REPEAT_INC_NG_SG,    "repeat-inc-ng-sg",     ARG_MEMNUM  },

  { OP_EMPTY_CHECK_START,   "empty-check-start",    ARG_MEMNUM  },

  { OP_EMPTY_CHECK_END,     "empty-check-end",      ARG_MEMNUM  },

  { OP_EMPTY_CHECK_END_MEMST,"empty-check-end-memst", ARG_MEMNUM  },

  { OP_EMPTY_CHECK_END_MEMST_PUSH,"empty-check-end-memst-push", ARG_MEMNUM  },

  { OP_PREC_READ_START,      "push-pos",             ARG_NON },

  { OP_PREC_READ_END,        "pop-pos",              ARG_NON },

  { OP_PREC_READ_NOT_START,  "prec-read-not-start",  ARG_RELADDR },

  { OP_PREC_READ_NOT_END,    "prec-read-not-end",    ARG_NON },

  { OP_ATOMIC_START,         "atomic-start",         ARG_NON },

  { OP_ATOMIC_END,           "atomic-end",           ARG_NON },

  { OP_LOOK_BEHIND,          "look-behind",          ARG_SPECIAL },

  { OP_LOOK_BEHIND_NOT_START, "look-behind-not-start", ARG_SPECIAL },

  { OP_LOOK_BEHIND_NOT_END,  "look-behind-not-end",  ARG_NON },

  { OP_CALL,                 "call",                 ARG_ABSADDR },

  { OP_RETURN,               "return",               ARG_NON },

  { OP_PUSH_SAVE_VAL,        "push-save-val",        ARG_SPECIAL },

  { OP_UPDATE_VAR,           "update-var",           ARG_SPECIAL },

#ifdef USE_CALLOUT

  { OP_CALLOUT_CONTENTS,     "callout-contents",     ARG_SPECIAL },

  { OP_CALLOUT_NAME,         "callout-name",         ARG_SPECIAL },

#endif

  { -1, "", ARG_NON }

};

static char*

op2name(int opcode)

{

  int i;

  for (i = 0; OpInfo[i].opcode >= 0; i++) {

    if (opcode == OpInfo[i].opcode)

      return OpInfo[i].name;

  }

  return "";

}

static int

op2arg_type(int opcode)

{

  int i;

  for (i = 0; OpInfo[i].opcode >= 0; i++) {

    if (opcode == OpInfo[i].opcode)

      return OpInfo[i].arg_type;

  }

  return ARG_SPECIAL;

}

static void

p_string(FILE* f, int len, UChar* s)

{

  fputs(":", f);

  while (len-- > 0) { fputc(*s++, f); }

}

static void

p_len_string(FILE* f, LengthType len, int mb_len, UChar* s)

{

  int x = len * mb_len;

  fprintf(f, ":%d:", len);

  while (x-- > 0) { fputc(*s++, f); }

}

static void

p_rel_addr(FILE* f, RelAddrType rel_addr, UChar* p, UChar* start)

{

  RelAddrType curr = (RelAddrType )(p - start);

  fprintf(f, "{%d/%d}", rel_addr, curr + rel_addr);

}

static int

bitset_on_num(BitSetRef bs)

{

  int i, n;

  n = 0;

  for (i = 0; i < SINGLE_BYTE_SIZE; i++) {

    if (BITSET_AT(bs, i)) n++;

  }

  return n;

}

extern void

onig_print_compiled_byte_code(FILE* f, UChar* bp, UChar** nextp, UChar* start,

                              OnigEncoding enc)

{

  int i, n;

  OpArgType   arg_type;

  RelAddrType addr;

  LengthType  len;

  MemNumType  mem;

  OnigCodePoint  code;

  OnigOptionType option;

  ModeType mode;

  UChar *q;

  fprintf(f, "%s", op2name(*bp));

  arg_type = op2arg_type(*bp);

  if (arg_type != ARG_SPECIAL) {

    bp++;

    switch (arg_type) {

    case ARG_NON:

      break;

    case ARG_RELADDR:

      GET_RELADDR_INC(addr, bp);

      fputc(':', f);

      p_rel_addr(f, addr, bp, start);

      break;

    case ARG_ABSADDR:

      GET_ABSADDR_INC(addr, bp);

      fprintf(f, ":{/%d}", addr);

      break;

    case ARG_LENGTH:

      GET_LENGTH_INC(len, bp);

      fprintf(f, ":%d", len);

      break;

    case ARG_MEMNUM:

      mem = *((MemNumType* )bp);

      bp += SIZE_MEMNUM;

      fprintf(f, ":%d", mem);

      break;

    case ARG_OPTION:

      {

        OnigOptionType option = *((OnigOptionType* )bp);

        bp += SIZE_OPTION;

        fprintf(f, ":%d", option);

      }

      break;

    case ARG_MODE:

      mode = *((ModeType* )bp);

      bp += SIZE_MODE;

      fprintf(f, ":%d", mode);

      break;

    default:

      break;

    }

  }

  else {

    switch (*bp++) {

    case OP_EXACT1:

    case OP_ANYCHAR_STAR_PEEK_NEXT:

    case OP_ANYCHAR_ML_STAR_PEEK_NEXT:

      p_string(f, 1, bp++); break;

    case OP_EXACT2:

      p_string(f, 2, bp); bp += 2; break;

    case OP_EXACT3:

      p_string(f, 3, bp); bp += 3; break;

    case OP_EXACT4:

      p_string(f, 4, bp); bp += 4; break;

    case OP_EXACT5:

      p_string(f, 5, bp); bp += 5; break;

    case OP_EXACTN:

      GET_LENGTH_INC(len, bp);

      p_len_string(f, len, 1, bp);

      bp += len;

      break;

    case OP_EXACTMB2N1:

      p_string(f, 2, bp); bp += 2; break;

    case OP_EXACTMB2N2:

      p_string(f, 4, bp); bp += 4; break;

    case OP_EXACTMB2N3:

      p_string(f, 6, bp); bp += 6; break;

    case OP_EXACTMB2N:

      GET_LENGTH_INC(len, bp);

      p_len_string(f, len, 2, bp);

      bp += len * 2;

      break;

    case OP_EXACTMB3N:

      GET_LENGTH_INC(len, bp);

      p_len_string(f, len, 3, bp);

      bp += len * 3;

      break;

    case OP_EXACTMBN:

      {

        int mb_len;

        GET_LENGTH_INC(mb_len, bp);

        GET_LENGTH_INC(len, bp);

        fprintf(f, ":%d:%d:", mb_len, len);

        n = len * mb_len;

        while (n-- > 0) { fputc(*bp++, f); }

      }

      break;

    case OP_EXACT1_IC:

      len = enclen(enc, bp);

      p_string(f, len, bp);

      bp += len;

      break;

    case OP_EXACTN_IC:

      GET_LENGTH_INC(len, bp);

      p_len_string(f, len, 1, bp);

      bp += len;

      break;

    case OP_CCLASS:

      n = bitset_on_num((BitSetRef )bp);

      bp += SIZE_BITSET;

      fprintf(f, ":%d", n);

      break;

    case OP_CCLASS_NOT:

      n = bitset_on_num((BitSetRef )bp);

      bp += SIZE_BITSET;

      fprintf(f, ":%d", n);

      break;

    case OP_CCLASS_MB:

    case OP_CCLASS_MB_NOT:

      GET_LENGTH_INC(len, bp);

      q = bp;

#ifndef PLATFORM_UNALIGNED_WORD_ACCESS

      ALIGNMENT_RIGHT(q);

#endif

      GET_CODE_POINT(code, q);

      bp += len;

      fprintf(f, ":%d:%d", (int )code, len);

      break;

    case OP_CCLASS_MIX:

    case OP_CCLASS_MIX_NOT:

      n = bitset_on_num((BitSetRef )bp);

      bp += SIZE_BITSET;

      GET_LENGTH_INC(len, bp);

      q = bp;

#ifndef PLATFORM_UNALIGNED_WORD_ACCESS

      ALIGNMENT_RIGHT(q);

#endif

      GET_CODE_POINT(code, q);

      bp += len;

      fprintf(f, ":%d:%d:%d", n, (int )code, len);

      break;

#ifdef USE_OP_CCLASS_NODE

    case OP_CCLASS_NODE:

      {

        CClassNode *cc;

        GET_POINTER_INC(cc, bp);

        n = bitset_on_num(cc->bs);

        fprintf(f, ":%p:%d", cc, n);

      }

      break;

#endif

    case OP_BACKREF_N_IC:

      mem = *((MemNumType* )bp);

      bp += SIZE_MEMNUM;

      fprintf(f, ":%d", mem);

      break;

    case OP_BACKREF_MULTI_IC:

    case OP_BACKREF_MULTI:

    case OP_BACKREF_CHECK:

      fputs(" ", f);

      GET_LENGTH_INC(len, bp);

      for (i = 0; i < len; i++) {

        GET_MEMNUM_INC(mem, bp);

        if (i > 0) fputs(", ", f);

        fprintf(f, "%d", mem);

      }

      break;

    case OP_BACKREF_WITH_LEVEL:

      GET_OPTION_INC(option, bp);

      fprintf(f, ":%d", option);

      /* fall */

    case OP_BACKREF_CHECK_WITH_LEVEL:

      {

        LengthType level;

        GET_LENGTH_INC(level, bp);

        fprintf(f, ":%d", level);

        fputs(" ", f);

        GET_LENGTH_INC(len, bp);

        for (i = 0; i < len; i++) {

          GET_MEMNUM_INC(mem, bp);

          if (i > 0) fputs(", ", f);

          fprintf(f, "%d", mem);

        }

      }

      break;

    case OP_REPEAT:

    case OP_REPEAT_NG:

      {

        mem = *((MemNumType* )bp);

        bp += SIZE_MEMNUM;

        addr = *((RelAddrType* )bp);

        bp += SIZE_RELADDR;

        fprintf(f, ":%d:%d", mem, addr);

      }

      break;

    case OP_PUSH_OR_JUMP_EXACT1:

    case OP_PUSH_IF_PEEK_NEXT:

      addr = *((RelAddrType* )bp);

      bp += SIZE_RELADDR;

      fputc(':', f);

      p_rel_addr(f, addr, bp, start);

      p_string(f, 1, bp);

      bp += 1;

      break;

    case OP_LOOK_BEHIND:

      GET_LENGTH_INC(len, bp);

      fprintf(f, ":%d", len);

      break;

    case OP_LOOK_BEHIND_NOT_START:

      GET_RELADDR_INC(addr, bp);

      GET_LENGTH_INC(len, bp);

      fprintf(f, ":%d:", len);

      p_rel_addr(f, addr, bp, start);

      break;

    case OP_PUSH_SAVE_VAL:

      {

        SaveType type;

        GET_SAVE_TYPE_INC(type, bp);

        GET_MEMNUM_INC(mem, bp);

        fprintf(f, ":%d:%d", type, mem);

      }

      break;

    case OP_UPDATE_VAR:

      {

        UpdateVarType type;

        GET_UPDATE_VAR_TYPE_INC(type, bp);

        GET_MEMNUM_INC(mem, bp);

        fprintf(f, ":%d:%d", type, mem);

      }

      break;

#ifdef USE_CALLOUT

    case OP_CALLOUT_CONTENTS:

      {

        GET_MEMNUM_INC(mem,  bp); /* number */

        fprintf(f, ":%d", mem);

      }

      break;

    case OP_CALLOUT_NAME:

      {

        int id;

        GET_MEMNUM_INC(id,   bp); /* id */

        GET_MEMNUM_INC(mem,  bp); /* number */

        fprintf(f, ":%d:%d", id, mem);

      }

      break;

#endif

    default:

      fprintf(stderr, "onig_print_compiled_byte_code: undefined code %d\n", *--bp);

    }

  }

  if (nextp) *nextp = bp;

}

#endif /* ONIG_DEBUG */

#ifdef ONIG_DEBUG_COMPILE

extern void

onig_print_compiled_byte_code_list(FILE* f, regex_t* reg)

{

  UChar* bp;

  UChar* start = reg->p;

  UChar* end   = reg->p + reg->used;

  fprintf(f, "bt_mem_start: 0x%x, bt_mem_end: 0x%x\n",

          reg->bt_mem_start, reg->bt_mem_end);

  fprintf(f, "code-length: %d\n", reg->used);

  bp = start;

  while (bp < end) {

    int pos = bp - start;

    fprintf(f, "%4d: ", pos);

    onig_print_compiled_byte_code(f, bp, &bp, start, reg->enc);

    fprintf(f, "\n");

  }

  fprintf(f, "\n");

}

#endif

#ifdef USE_CAPTURE_HISTORY

static void history_tree_free(OnigCaptureTreeNode* node);

static void

history_tree_clear(OnigCaptureTreeNode* node)

{

  int i;

  if (IS_NOT_NULL(node)) {

    for (i = 0; i < node->num_childs; i++) {

      if (IS_NOT_NULL(node->childs[i])) {

        history_tree_free(node->childs[i]);

      }

    }

    for (i = 0; i < node->allocated; i++) {

      node->childs[i] = (OnigCaptureTreeNode* )0;

    }

    node->num_childs = 0;

    node->beg = ONIG_REGION_NOTPOS;

    node->end = ONIG_REGION_NOTPOS;

    node->group = -1;

  }

}

static void

history_tree_free(OnigCaptureTreeNode* node)

{

  history_tree_clear(node);

  xfree(node);

}

static void

history_root_free(OnigRegion* r)

{

  if (IS_NOT_NULL(r->history_root)) {

    history_tree_free(r->history_root);

    r->history_root = (OnigCaptureTreeNode* )0;

  }

}

static OnigCaptureTreeNode*

history_node_new(void)

{

  OnigCaptureTreeNode* node;

  node = (OnigCaptureTreeNode* )xmalloc(sizeof(OnigCaptureTreeNode));

  CHECK_NULL_RETURN(node);

  node->childs     = (OnigCaptureTreeNode** )0;

  node->allocated  = 0;

  node->num_childs = 0;

  node->group      = -1;

  node->beg        = ONIG_REGION_NOTPOS;

  node->end        = ONIG_REGION_NOTPOS;

  return node;

}

static int

history_tree_add_child(OnigCaptureTreeNode* parent, OnigCaptureTreeNode* child)

{

#define HISTORY_TREE_INIT_ALLOC_SIZE  8

  if (parent->num_childs >= parent->allocated) {

    int n, i;

    if (IS_NULL(parent->childs)) {

      n = HISTORY_TREE_INIT_ALLOC_SIZE;

      parent->childs =

        (OnigCaptureTreeNode** )xmalloc(sizeof(OnigCaptureTreeNode*) * n);

    }

    else {

      n = parent->allocated * 2;

      parent->childs =

        (OnigCaptureTreeNode** )xrealloc(parent->childs,

                                         sizeof(OnigCaptureTreeNode*) * n);

    }

    CHECK_NULL_RETURN_MEMERR(parent->childs);

    for (i = parent->allocated; i < n; i++) {

      parent->childs[i] = (OnigCaptureTreeNode* )0;

    }

    parent->allocated = n;

  }

  parent->childs[parent->num_childs] = child;

  parent->num_childs++;

  return 0;

}

static OnigCaptureTreeNode*

history_tree_clone(OnigCaptureTreeNode* node)

{

  int i;

  OnigCaptureTreeNode *clone, *child;

  clone = history_node_new();

  CHECK_NULL_RETURN(clone);

  clone->beg = node->beg;

  clone->end = node->end;

  for (i = 0; i < node->num_childs; i++) {

    child = history_tree_clone(node->childs[i]);

    if (IS_NULL(child)) {

      history_tree_free(clone);

      return (OnigCaptureTreeNode* )0;

    }

    history_tree_add_child(clone, child);

  }

  return clone;

}

extern  OnigCaptureTreeNode*

onig_get_capture_tree(OnigRegion* region)

{

  return region->history_root;

}

#endif /* USE_CAPTURE_HISTORY */

extern void

onig_region_clear(OnigRegion* region)

{

  int i;

  for (i = 0; i < region->num_regs; i++) {

    region->beg[i] = region->end[i] = ONIG_REGION_NOTPOS;

  }

#ifdef USE_CAPTURE_HISTORY

  history_root_free(region);

#endif

}

extern int

onig_region_resize(OnigRegion* region, int n)

{

  region->num_regs = n;

  if (n < ONIG_NREGION)

    n = ONIG_NREGION;

  if (region->allocated == 0) {

    region->beg = (int* )xmalloc(n * sizeof(int));

    region->end = (int* )xmalloc(n * sizeof(int));

    if (region->beg == 0 || region->end == 0)

      return ONIGERR_MEMORY;

    region->allocated = n;

  }

  else if (region->allocated < n) {

    region->beg = (int* )xrealloc(region->beg, n * sizeof(int));

    region->end = (int* )xrealloc(region->end, n * sizeof(int));

    if (region->beg == 0 || region->end == 0)

      return ONIGERR_MEMORY;

    region->allocated = n;

  }

  return 0;

}

static int

onig_region_resize_clear(OnigRegion* region, int n)

{

  int r;

  r = onig_region_resize(region, n);

  if (r != 0) return r;

  onig_region_clear(region);

  return 0;

}

extern int

onig_region_set(OnigRegion* region, int at, int beg, int end)

{

  if (at < 0) return ONIGERR_INVALID_ARGUMENT;

  if (at >= region->allocated) {

    int r = onig_region_resize(region, at + 1);

    if (r < 0) return r;

  }

  region->beg[at] = beg;

  region->end[at] = end;

  return 0;

}

extern void

onig_region_init(OnigRegion* region)

{

  region->num_regs     = 0;

  region->allocated    = 0;

  region->beg          = (int* )0;

  region->end          = (int* )0;

  region->history_root = (OnigCaptureTreeNode* )0;

}

extern OnigRegion*

onig_region_new(void)

{

  OnigRegion* r;

  r = (OnigRegion* )xmalloc(sizeof(OnigRegion));

  CHECK_NULL_RETURN(r);

  onig_region_init(r);

  return r;

}

extern void

onig_region_free(OnigRegion* r, int free_self)

{

  if (r != 0) {

    if (r->allocated > 0) {

      if (r->beg) xfree(r->beg);

      if (r->end) xfree(r->end);

      r->allocated = 0;

    }

#ifdef USE_CAPTURE_HISTORY

    history_root_free(r);

#endif

    if (free_self) xfree(r);

  }

}

extern void

onig_region_copy(OnigRegion* to, OnigRegion* from)

{

#define RREGC_SIZE   (sizeof(int) * from->num_regs)

  int i;

  if (to == from) return;

  if (to->allocated == 0) {

    if (from->num_regs > 0) {

      to->beg = (int* )xmalloc(RREGC_SIZE);

      if (IS_NULL(to->beg)) return;

      to->end = (int* )xmalloc(RREGC_SIZE);

      if (IS_NULL(to->end)) return;

      to->allocated = from->num_regs;

    }

  }

  else if (to->allocated < from->num_regs) {

    to->beg = (int* )xrealloc(to->beg, RREGC_SIZE);

    if (IS_NULL(to->beg)) return;

    to->end = (int* )xrealloc(to->end, RREGC_SIZE);

    if (IS_NULL(to->end)) return;

    to->allocated = from->num_regs;

  }

  for (i = 0; i < from->num_regs; i++) {

    to->beg[i] = from->beg[i];

    to->end[i] = from->end[i];

  }

  to->num_regs = from->num_regs;

#ifdef USE_CAPTURE_HISTORY

  history_root_free(to);

  if (IS_NOT_NULL(from->history_root)) {