/src/jq/modules/oniguruma/src/regcomp.c

Source (jump to first uncovered line)
/**********************************************************************
  regcomp.c -  Oniguruma (regular expression library)
**********************************************************************/
/*-
 * Copyright (c) 2002-2023  K.Kosako
 * 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"

#define OPS_INIT_SIZE  8

#define ND_IS_REAL_IGNORECASE(node) \
  (ND_IS_IGNORECASE(node) && !ND_STRING_IS_CRUDE(node))

typedef struct {
  OnigLen min;
  OnigLen max;
} MinMaxLen;

typedef struct {
  OnigLen min;
  OnigLen max;
  int min_is_sure;
} MinMaxCharLen;

OnigCaseFoldType OnigDefaultCaseFoldFlag = ONIGENC_CASE_FOLD_MIN;

static OnigLen node_min_byte_len(Node* node, ParseEnv* env);

static int
ops_init(regex_t* reg, int init_alloc_size)
{
  Operation* p;
  size_t size;

  if (init_alloc_size <= 0)
    return ONIGERR_PARSER_BUG;

  size = sizeof(Operation) * init_alloc_size;
  p = (Operation* )xrealloc(reg->ops, size);
  CHECK_NULL_RETURN_MEMERR(p);
  reg->ops = p;
#ifdef USE_DIRECT_THREADED_CODE
  {
    enum OpCode* cp;
    size = sizeof(enum OpCode) * init_alloc_size;
    cp = (enum OpCode* )xrealloc(reg->ocs, size);
    CHECK_NULL_RETURN_MEMERR(cp);
    reg->ocs = cp;
  }
#endif

  reg->ops_curr  = 0; /* !!! not yet done ops_new() */
  reg->ops_alloc = init_alloc_size;
  reg->ops_used  = 0;

  return ONIG_NORMAL;
}

static int
ops_resize(regex_t* reg, int n)
{
#ifdef USE_DIRECT_THREADED_CODE
  enum OpCode* cp;
#endif
  Operation* p;
  size_t size;

  if (n == reg->ops_alloc) return ONIG_NORMAL;
  if (n <= 0) return ONIGERR_PARSER_BUG;

  size = sizeof(Operation) * n;
  p = (Operation* )xrealloc(reg->ops, size);
  CHECK_NULL_RETURN_MEMERR(p);
  reg->ops = p;

#ifdef USE_DIRECT_THREADED_CODE
  size = sizeof(enum OpCode) * n;
  cp = (enum OpCode* )xrealloc(reg->ocs, size);
  CHECK_NULL_RETURN_MEMERR(cp);
  reg->ocs = cp;
#endif

  reg->ops_alloc = n;
  if (reg->ops_used == 0)
    reg->ops_curr = 0;
  else
    reg->ops_curr = reg->ops + (reg->ops_used - 1);

  return ONIG_NORMAL;
}

static int
ops_new(regex_t* reg)
{
  if (reg->ops_used >= reg->ops_alloc) {
    int r = ops_resize(reg, reg->ops_alloc << 1);
    if (r != ONIG_NORMAL) return r;
  }

  reg->ops_curr = reg->ops + reg->ops_used;
  reg->ops_used++;

  xmemset(reg->ops_curr, 0, sizeof(Operation));
  return ONIG_NORMAL;
}

static int
is_in_string_pool(regex_t* reg, UChar* s)
{
  return (s >= reg->string_pool && s < reg->string_pool_end);
}

static void
ops_free(regex_t* reg)
{
  int i;

  if (IS_NULL(reg->ops)) return ;

  for (i = 0; i < (int )reg->ops_used; i++) {
    enum OpCode opcode;
    Operation* op;

    op = reg->ops + i;

#ifdef USE_DIRECT_THREADED_CODE
    opcode = *(reg->ocs + i);
#else
    opcode = op->opcode;
#endif

    switch (opcode) {
    case OP_STR_MBN:
      if (! is_in_string_pool(reg, op->exact_len_n.s))
        xfree(op->exact_len_n.s);
      break;
    case OP_STR_N: case OP_STR_MB2N: case OP_STR_MB3N:
      if (! is_in_string_pool(reg, op->exact_n.s))
        xfree(op->exact_n.s);
      break;
    case OP_STR_1: case OP_STR_2: case OP_STR_3: case OP_STR_4:
    case OP_STR_5: case OP_STR_MB2N1: case OP_STR_MB2N2:
    case OP_STR_MB2N3:
      break;

    case OP_CCLASS_NOT: case OP_CCLASS:
      xfree(op->cclass.bsp);
      break;

    case OP_CCLASS_MB_NOT: case OP_CCLASS_MB:
      xfree(op->cclass_mb.mb);
      break;
    case OP_CCLASS_MIX_NOT: case OP_CCLASS_MIX:
      xfree(op->cclass_mix.mb);
      xfree(op->cclass_mix.bsp);
      break;

    case OP_BACKREF1: case OP_BACKREF2: case OP_BACKREF_N: case OP_BACKREF_N_IC:
      break;
    case OP_BACKREF_MULTI:      case OP_BACKREF_MULTI_IC:
    case OP_BACKREF_CHECK:
#ifdef USE_BACKREF_WITH_LEVEL
    case OP_BACKREF_WITH_LEVEL:
    case OP_BACKREF_WITH_LEVEL_IC:
    case OP_BACKREF_CHECK_WITH_LEVEL:
#endif
      if (op->backref_general.num != 1)
        xfree(op->backref_general.ns);
      break;

    default:
      break;
    }
  }

  xfree(reg->ops);
#ifdef USE_DIRECT_THREADED_CODE
  xfree(reg->ocs);
  reg->ocs = 0;
#endif

  reg->ops = 0;
  reg->ops_curr  = 0;
  reg->ops_alloc = 0;
  reg->ops_used  = 0;
}

static int
ops_calc_size_of_string_pool(regex_t* reg)
{
  int i;
  int total;

  if (IS_NULL(reg->ops)) return 0;

  total = 0;
  for (i = 0; i < (int )reg->ops_used; i++) {
    enum OpCode opcode;
    Operation* op;

    op = reg->ops + i;
#ifdef USE_DIRECT_THREADED_CODE
    opcode = *(reg->ocs + i);
#else
    opcode = op->opcode;
#endif

    switch (opcode) {
    case OP_STR_MBN:
      total += op->exact_len_n.len * op->exact_len_n.n;
      break;
    case OP_STR_N:
    case OP_STR_MB2N:
      total += op->exact_n.n * 2;
      break;
    case OP_STR_MB3N:
      total += op->exact_n.n * 3;
      break;

    default:
      break;
    }
  }

  return total;
}

static int
ops_make_string_pool(regex_t* reg)
{
  int i;
  int len;
  int size;
  UChar* pool;
  UChar* curr;

  size = ops_calc_size_of_string_pool(reg);
  if (size <= 0) {
    return 0;
  }

  curr = pool = (UChar* )xmalloc((size_t )size);
  CHECK_NULL_RETURN_MEMERR(pool);

  for (i = 0; i < (int )reg->ops_used; i++) {
    enum OpCode opcode;
    Operation* op;

    op = reg->ops + i;
#ifdef USE_DIRECT_THREADED_CODE
    opcode = *(reg->ocs + i);
#else
    opcode = op->opcode;
#endif

    switch (opcode) {
    case OP_STR_MBN:
      len = op->exact_len_n.len * op->exact_len_n.n;
      xmemcpy(curr, op->exact_len_n.s, len);
      xfree(op->exact_len_n.s);
      op->exact_len_n.s = curr;
      curr += len;
      break;
    case OP_STR_N:
      len = op->exact_n.n;
    copy:
      xmemcpy(curr, op->exact_n.s, len);
      xfree(op->exact_n.s);
      op->exact_n.s = curr;
      curr += len;
      break;
    case OP_STR_MB2N:
      len = op->exact_n.n * 2;
      goto copy;
      break;
    case OP_STR_MB3N:
      len = op->exact_n.n * 3;
      goto copy;
      break;

    default:
      break;
    }
  }

  reg->string_pool     = pool;
  reg->string_pool_end = pool + size;
  return 0;
}

extern OnigCaseFoldType
onig_get_default_case_fold_flag(void)
{
  return OnigDefaultCaseFoldFlag;
}

extern int
onig_set_default_case_fold_flag(OnigCaseFoldType case_fold_flag)
{
  OnigDefaultCaseFoldFlag = case_fold_flag;
  return 0;
}

static int
len_multiply_cmp(OnigLen x, int y, OnigLen v)
{
  if (x == 0 || y == 0) return -1;

  if (x < INFINITE_LEN / y) {
    OnigLen xy = x * (OnigLen )y;
    if (xy > v) return 1;
    else {
      if (xy == v) return 0;
      else return -1;
    }
  }
  else
    return v == INFINITE_LEN ? 0 : 1;
}

extern int
onig_positive_int_multiply(int x, int y)
{
  if (x == 0 || y == 0) return 0;

  if (x < ONIG_INT_MAX / y)
    return x * y;
  else
    return -1;
}


static void
node_swap(Node* a, Node* b)
{
  Node c;

  c = *a; *a = *b; *b = c;

  if (ND_TYPE(a) == ND_STRING) {
    StrNode* sn = STR_(a);
    if (sn->capacity == 0) {
      int len = (int )(sn->end - sn->s);
      sn->s   = sn->buf;
      sn->end = sn->s + len;
    }
  }

  if (ND_TYPE(b) == ND_STRING) {
    StrNode* sn = STR_(b);
    if (sn->capacity == 0) {
      int len = (int )(sn->end - sn->s);
      sn->s   = sn->buf;
      sn->end = sn->s + len;
    }
  }
}

static int
node_list_len(Node* list)
{
  int len;

  len = 1;
  while (IS_NOT_NULL(ND_CDR(list))) {
    list = ND_CDR(list);
    len++;
  }

  return len;
}

static Node*
node_list_add(Node* list, Node* x)
{
  Node *n;

  n = onig_node_new_list(x, NULL);
  if (IS_NULL(n)) return NULL_NODE;

  if (IS_NOT_NULL(list)) {
    while (IS_NOT_NULL(ND_CDR(list)))
      list = ND_CDR(list);

    ND_CDR(list) = n;
  }

  return n;
}

static int
node_str_node_cat(Node* node, Node* add)
{
  int r;

  if (ND_STATUS(node) != ND_STATUS(add))
    return ONIGERR_TYPE_BUG;

  if (STR_(node)->flag != STR_(add)->flag)
    return ONIGERR_TYPE_BUG;

  r = onig_node_str_cat(node, STR_(add)->s, STR_(add)->end);
  if (r != 0) return r;

  return 0;
}

static void
node_conv_to_str_node(Node* node, Node* ref_node)
{
  xmemset(node, 0, sizeof(*node));
  ND_SET_TYPE(node, ND_STRING);
  ND_STATUS(node) = ND_STATUS(ref_node);

  STR_(node)->flag     = STR_(ref_node)->flag;
  STR_(node)->s        = STR_(node)->buf;
  STR_(node)->end      = STR_(node)->buf;
  STR_(node)->capacity = 0;
}

static OnigLen
distance_add(OnigLen d1, OnigLen d2)
{
  if (d1 == INFINITE_LEN || d2 == INFINITE_LEN)
    return INFINITE_LEN;
  else {
    if (d1 <= INFINITE_LEN - d2) return d1 + d2;
    else return INFINITE_LEN;
  }
}

static OnigLen
distance_multiply(OnigLen d, int m)
{
  if (m == 0) return 0;

  if (d < INFINITE_LEN / m)
    return d * m;
  else
    return INFINITE_LEN;
}

static int
bitset_is_empty(BitSetRef bs)
{
  int i;

  for (i = 0; i < (int )BITSET_REAL_SIZE; i++) {
    if (bs[i] != 0) return 0;
  }
  return 1;
}

#ifdef USE_CALL

static int
unset_addr_list_init(UnsetAddrList* list, int size)
{
  UnsetAddr* p = (UnsetAddr* )xmalloc(sizeof(UnsetAddr)* size);
  CHECK_NULL_RETURN_MEMERR(p);

  list->num   = 0;
  list->alloc = size;
  list->us    = p;
  return 0;
}

static void
unset_addr_list_end(UnsetAddrList* list)
{
  if (IS_NOT_NULL(list->us))
    xfree(list->us);
}

static int
unset_addr_list_add(UnsetAddrList* list, int offset, struct _Node* node)
{
  UnsetAddr* p;
  int size;

  if (list->num >= list->alloc) {
    size = list->alloc * 2;
    p = (UnsetAddr* )xrealloc(list->us, sizeof(UnsetAddr) * size);
    CHECK_NULL_RETURN_MEMERR(p);
    list->alloc = size;
    list->us    = p;
  }

  list->us[list->num].offset = offset;
  list->us[list->num].target = node;
  list->num++;
  return 0;
}
#endif /* USE_CALL */

enum CharLenReturnType {
  CHAR_LEN_NORMAL = 0,       /* fixed or variable */
  CHAR_LEN_TOP_ALT_FIXED = 1
};

static int
mmcl_fixed(MinMaxCharLen* c)
{
  return (c->min == c->max && c->min != INFINITE_LEN);
}

static void
mmcl_set(MinMaxCharLen* l, OnigLen len)
{
  l->min = len;
  l->max = len;
  l->min_is_sure = TRUE;
}

static void
mmcl_set_min_max(MinMaxCharLen* l, OnigLen min, OnigLen max, int min_is_sure)
{
  l->min = min;
  l->max = max;
  l->min_is_sure = min_is_sure;
}

static void
mmcl_add(MinMaxCharLen* to, MinMaxCharLen* add)
{
  to->min = distance_add(to->min, add->min);
  to->max = distance_add(to->max, add->max);

  to->min_is_sure = add->min_is_sure != FALSE && to->min_is_sure != FALSE;
}

static void
mmcl_multiply(MinMaxCharLen* to, int m)
{
  to->min = distance_multiply(to->min, m);
  to->max = distance_multiply(to->max, m);
}

static void
mmcl_repeat_range_multiply(MinMaxCharLen* to, int mlow, int mhigh)
{
  to->min = distance_multiply(to->min, mlow);

  if (IS_INFINITE_REPEAT(mhigh))
    to->max = INFINITE_LEN;
  else
    to->max = distance_multiply(to->max, mhigh);
}

static void
mmcl_alt_merge(MinMaxCharLen* to, MinMaxCharLen* alt)
{
  if (to->min > alt->min) {
    to->min         = alt->min;
    to->min_is_sure = alt->min_is_sure;
  }
  else if (to->min == alt->min) {
    if (alt->min_is_sure != FALSE)
      to->min_is_sure = TRUE;
  }

  if (to->max < alt->max) to->max = alt->max;
}

#ifndef ONIG_DONT_OPTIMIZE

static int
mml_is_equal(MinMaxLen* a, MinMaxLen* b)
{
  return a->min == b->min && a->max == b->max;
}

static void
mml_set_min_max(MinMaxLen* l, OnigLen min, OnigLen max)
{
  l->min = min;
  l->max = max;
}

static void
mml_clear(MinMaxLen* l)
{
  l->min = l->max = 0;
}

static void
mml_copy(MinMaxLen* to, MinMaxLen* from)
{
  to->min = from->min;
  to->max = from->max;
}

static void
mml_add(MinMaxLen* to, MinMaxLen* add)
{
  to->min = distance_add(to->min, add->min);
  to->max = distance_add(to->max, add->max);
}

static void
mml_alt_merge(MinMaxLen* to, MinMaxLen* alt)
{
  if (to->min > alt->min) to->min = alt->min;
  if (to->max < alt->max) to->max = alt->max;
}

#endif

/* fixed size pattern node only */
static int
node_char_len1(Node* node, regex_t* reg, MinMaxCharLen* ci, ParseEnv* env,
               int level)
{
  MinMaxCharLen tci;
  int r = CHAR_LEN_NORMAL;

  level++;

  switch (ND_TYPE(node)) {
  case ND_LIST:
    {
      int first = TRUE;
      do {
        r = node_char_len1(ND_CAR(node), reg, &tci, env, level);
        if (r < 0) break;
        if (first == TRUE) {
          *ci = tci;
          first = FALSE;
        }
        else
          mmcl_add(ci, &tci);
      } while (IS_NOT_NULL(node = ND_CDR(node)));
    }
    break;

  case ND_ALT:
    {
      int fixed;

      r = node_char_len1(ND_CAR(node), reg, ci, env, level);
      if (r < 0) break;

      fixed = TRUE;
      while (IS_NOT_NULL(node = ND_CDR(node))) {
        r = node_char_len1(ND_CAR(node), reg, &tci, env, level);
        if (r < 0) break;
        if (! mmcl_fixed(&tci))
          fixed = FALSE;
        mmcl_alt_merge(ci, &tci);
      }
      if (r < 0) break;

      r = CHAR_LEN_NORMAL;
      if (mmcl_fixed(ci)) break;

      if (fixed == TRUE && level == 1) {
        r = CHAR_LEN_TOP_ALT_FIXED;
      }
    }
    break;

  case ND_STRING:
    {
      OnigLen clen;
      StrNode* sn = STR_(node);
      UChar *s = sn->s;

      if (ND_IS_REAL_IGNORECASE(node) &&
          CASE_FOLD_IS_NOT_ASCII_ONLY(env->case_fold_flag)) {
        /* Such a case is possible.
           ex. /(?i)(?<=\1)(a)/
           Backref node refer to capture group, but it doesn't tune yet.
         */
        r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
        break;
      }

      clen = 0;
      while (s < sn->end) {
        s += enclen(reg->enc, s);
        clen = distance_add(clen, 1);
      }
      mmcl_set(ci, clen);
    }
    break;

  case ND_QUANT:
    {
      QuantNode* qn = QUANT_(node);

      if (qn->lower == qn->upper) {
        if (qn->upper == 0) {
          mmcl_set(ci, 0);
        }
        else {
          r = node_char_len1(ND_BODY(node), reg, ci, env, level);
          if (r < 0) break;
          mmcl_multiply(ci, qn->lower);
        }
      }
      else {
        r = node_char_len1(ND_BODY(node), reg, ci, env, level);
        if (r < 0) break;
        mmcl_repeat_range_multiply(ci, qn->lower, qn->upper);
      }
    }
    break;

#ifdef USE_CALL
  case ND_CALL:
    if (ND_IS_RECURSION(node))
      mmcl_set_min_max(ci, 0, INFINITE_LEN, FALSE);
    else
      r = node_char_len1(ND_BODY(node), reg, ci, env, level);
    break;
#endif

  case ND_CTYPE:
  case ND_CCLASS:
    mmcl_set(ci, 1);
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      switch (en->type) {
      case BAG_MEMORY:
        if (ND_IS_FIXED_CLEN(node)) {
          mmcl_set_min_max(ci, en->min_char_len, en->max_char_len,
                           ND_IS_FIXED_CLEN_MIN_SURE(node));
        }
        else {
          if (ND_IS_MARK1(node)) {
            mmcl_set_min_max(ci, 0, INFINITE_LEN, FALSE);
          }
          else {
            ND_STATUS_ADD(node, MARK1);
            r = node_char_len1(ND_BODY(node), reg, ci, env, level);
            ND_STATUS_REMOVE(node, MARK1);
            if (r < 0) break;

            en->min_char_len = ci->min;
            en->max_char_len = ci->max;
            ND_STATUS_ADD(node, FIXED_CLEN);
            if (ci->min_is_sure != FALSE)
              ND_STATUS_ADD(node, FIXED_CLEN_MIN_SURE);
          }
        }
        /* can't optimize look-behind if capture exists. */
        ci->min_is_sure = FALSE;
        break;
      case BAG_OPTION:
      case BAG_STOP_BACKTRACK:
        r = node_char_len1(ND_BODY(node), reg, ci, env, level);
        break;
      case BAG_IF_ELSE:
        {
          MinMaxCharLen eci;

          r = node_char_len1(ND_BODY(node), reg, ci, env, level);
          if (r < 0) break;

          if (IS_NOT_NULL(en->te.Then)) {
            r = node_char_len1(en->te.Then, reg, &tci, env, level);
            if (r < 0) break;
            mmcl_add(ci, &tci);
          }

          if (IS_NOT_NULL(en->te.Else)) {
            r = node_char_len1(en->te.Else, reg, &eci, env, level);
            if (r < 0) break;
          }
          else {
            mmcl_set(&eci, 0);
          }

          mmcl_alt_merge(ci, &eci);
        }
        break;
      default: /* never come here */
        r = ONIGERR_PARSER_BUG;
        break;
      }
    }
    break;

  case ND_GIMMICK:
    mmcl_set(ci, 0);
    break;

  case ND_ANCHOR:
  zero:
    mmcl_set(ci, 0);
    /* can't optimize look-behind if anchor exists. */
    ci->min_is_sure = FALSE;
    break;

  case ND_BACKREF:
    if (ND_IS_CHECKER(node))
      goto zero;

    if (ND_IS_RECURSION(node)) {
#ifdef USE_BACKREF_WITH_LEVEL
      if (ND_IS_NEST_LEVEL(node)) {
        mmcl_set_min_max(ci, 0, INFINITE_LEN, FALSE);
        break;
      }
#endif

      mmcl_set_min_max(ci, 0, 0, FALSE);
      break;
    }

    {
      int i;
      int* backs;
      MemEnv* mem_env = PARSEENV_MEMENV(env);
      BackRefNode* br = BACKREF_(node);

      backs = BACKREFS_P(br);
      r = node_char_len1(mem_env[backs[0]].mem_node, reg, ci, env, level);
      if (r < 0) break;
      if (! mmcl_fixed(ci)) ci->min_is_sure = FALSE;

      for (i = 1; i < br->back_num; i++) {
        r = node_char_len1(mem_env[backs[i]].mem_node, reg, &tci, env, level);
        if (r < 0) break;
        if (! mmcl_fixed(&tci)) tci.min_is_sure = FALSE;
        mmcl_alt_merge(ci, &tci);
      }
    }
    break;

  default: /* never come here */
    r = ONIGERR_PARSER_BUG;
    break;
  }

  return r;
}

static int
node_char_len(Node* node, regex_t* reg, MinMaxCharLen* ci, ParseEnv* env)
{
  return node_char_len1(node, reg, ci, env, 0);
}


static int
add_op(regex_t* reg, int opcode)
{
  int r;

  r = ops_new(reg);
  if (r != ONIG_NORMAL) return r;

#ifdef USE_DIRECT_THREADED_CODE
  *(reg->ocs + (reg->ops_curr - reg->ops)) = opcode;
#else
  reg->ops_curr->opcode = opcode;
#endif

  return 0;
}

static int compile_length_tree(Node* node, regex_t* reg, ParseEnv* env);
static int compile_tree(Node* node, regex_t* reg, ParseEnv* env);


#define IS_NEED_STR_LEN_OP(op) \
   ((op) == OP_STR_N    || (op) == OP_STR_MB2N ||\
    (op) == OP_STR_MB3N || (op) == OP_STR_MBN)

static int
select_str_opcode(int mb_len, int str_len)
{
  int op;

  switch (mb_len) {
  case 1:
    switch (str_len) {
    case 1:  op = OP_STR_1; break;
    case 2:  op = OP_STR_2; break;
    case 3:  op = OP_STR_3; break;
    case 4:  op = OP_STR_4; break;
    case 5:  op = OP_STR_5; break;
    default: op = OP_STR_N; break;
    }
    break;

  case 2:
    switch (str_len) {
    case 1:  op = OP_STR_MB2N1; break;
    case 2:  op = OP_STR_MB2N2; break;
    case 3:  op = OP_STR_MB2N3; break;
    default: op = OP_STR_MB2N;  break;
    }
    break;

  case 3:
    op = OP_STR_MB3N;
    break;

  default:
    op = OP_STR_MBN;
    break;
  }

  return op;
}

static int
is_strict_real_node(Node* node)
{
  switch (ND_TYPE(node)) {
  case ND_STRING:
    {
      StrNode* sn = STR_(node);
      return (sn->end != sn->s);
    }
    break;

  case ND_CCLASS:
  case ND_CTYPE:
    return 1;
    break;

  default:
    return 0;
    break;
  }
}

static int
compile_quant_body_with_empty_check(QuantNode* qn, regex_t* reg, ParseEnv* env)
{
  int r;
  int saved_num_empty_check;
  int emptiness;
  Node* body;

  body = ND_BODY((Node* )qn);
  emptiness = qn->emptiness;
  saved_num_empty_check = reg->num_empty_check;

  if (emptiness != BODY_IS_NOT_EMPTY) {
    r = add_op(reg, OP_EMPTY_CHECK_START);
    if (r != 0) return r;
    COP(reg)->empty_check_start.mem = reg->num_empty_check; /* NULL CHECK ID */
    reg->num_empty_check++;
  }

  r = compile_tree(body, reg, env);
  if (r != 0) return r;

  if (emptiness != BODY_IS_NOT_EMPTY) {
    if (emptiness == BODY_MAY_BE_EMPTY)
      r = add_op(reg, OP_EMPTY_CHECK_END);
    else if (emptiness == BODY_MAY_BE_EMPTY_MEM) {
      if (ND_IS_EMPTY_STATUS_CHECK(qn) != 0 && qn->empty_status_mem != 0) {
        r = add_op(reg, OP_EMPTY_CHECK_END_MEMST);
        if (r != 0) return r;
        COP(reg)->empty_check_end.empty_status_mem = qn->empty_status_mem;
      }
      else
        r = add_op(reg, OP_EMPTY_CHECK_END);
    }
#ifdef USE_CALL
    else if (emptiness == BODY_MAY_BE_EMPTY_REC) {
      r = add_op(reg, OP_EMPTY_CHECK_END_MEMST_PUSH);
      if (r != 0) return r;
      COP(reg)->empty_check_end.empty_status_mem = qn->empty_status_mem;
    }
#endif

    if (r != 0) return r;
    COP(reg)->empty_check_end.mem = saved_num_empty_check; /* NULL CHECK ID */
  }
  return r;
}

#ifdef USE_CALL
static int
compile_call(CallNode* node, regex_t* reg, ParseEnv* env)
{
  int r;
  int offset;

  r = add_op(reg, OP_CALL);
  if (r != 0) return r;

  COP(reg)->call.addr = 0; /* dummy addr. */
#ifdef ONIG_DEBUG_MATCH_COUNTER
  COP(reg)->call.called_mem = node->called_gnum;
#endif

  offset = COP_CURR_OFFSET_BYTES(reg, call.addr);
  r = unset_addr_list_add(env->unset_addr_list, offset, ND_CALL_BODY(node));
  return r;
}
#endif

static int
compile_tree_n_times(Node* node, int n, regex_t* reg, ParseEnv* env)
{
  int i, r;

  for (i = 0; i < n; i++) {
    r = compile_tree(node, reg, env);
    if (r != 0) return r;
  }
  return 0;
}

static int
add_compile_string_length(UChar* s ARG_UNUSED, int mb_len, int str_len,
                          regex_t* reg ARG_UNUSED)
{
  return 1;
}

static int
add_compile_string(UChar* s, int mb_len, int str_len, regex_t* reg)
{
  int op;
  int r;
  int byte_len;
  UChar* p;
  UChar* end;

  op = select_str_opcode(mb_len, str_len);
  r = add_op(reg, op);
  if (r != 0) return r;

  byte_len = mb_len * str_len;
  end = s + byte_len;

  if (op == OP_STR_MBN) {
    p = onigenc_strdup(reg->enc, s, end);
    CHECK_NULL_RETURN_MEMERR(p);

    COP(reg)->exact_len_n.len = mb_len;
    COP(reg)->exact_len_n.n   = str_len;
    COP(reg)->exact_len_n.s   = p;
  }
  else if (IS_NEED_STR_LEN_OP(op)) {
    p = onigenc_strdup(reg->enc, s, end);
    CHECK_NULL_RETURN_MEMERR(p);
    COP(reg)->exact_n.n = str_len;
    COP(reg)->exact_n.s = p;
  }
  else {
    xmemset(COP(reg)->exact.s, 0, sizeof(COP(reg)->exact.s));
    xmemcpy(COP(reg)->exact.s, s, (size_t )byte_len);
  }

  return 0;
}

static int
compile_length_string_node(Node* node, regex_t* reg)
{
  int rlen, r, len, prev_len, slen;
  UChar *p, *prev;
  StrNode* sn;
  OnigEncoding enc = reg->enc;

  sn = STR_(node);
  if (sn->end <= sn->s)
    return 0;

  p = prev = sn->s;
  prev_len = enclen(enc, p);
  p += prev_len;
  slen = 1;
  rlen = 0;

  for (; p < sn->end; ) {
    len = enclen(enc, p);
    if (len == prev_len) {
      slen++;
    }
    else {
      r = add_compile_string_length(prev, prev_len, slen, reg);
      rlen += r;
      prev = p;
      slen = 1;
      prev_len = len;
    }
    p += len;
  }

  r = add_compile_string_length(prev, prev_len, slen, reg);
  rlen += r;
  return rlen;
}

static int
compile_length_string_crude_node(StrNode* sn, regex_t* reg)
{
  if (sn->end <= sn->s)
    return 0;

  return add_compile_string_length(sn->s, 1 /* sb */, (int )(sn->end - sn->s),
                                   reg);
}

static int
compile_string_node(Node* node, regex_t* reg)
{
  int r, len, prev_len, slen;
  UChar *p, *prev, *end;
  StrNode* sn;
  OnigEncoding enc = reg->enc;

  sn = STR_(node);
  if (sn->end <= sn->s)
    return 0;

  end = sn->end;

  p = prev = sn->s;
  prev_len = enclen(enc, p);
  p += prev_len;
  slen = 1;

  for (; p < end; ) {
    len = enclen(enc, p);
    if (len == prev_len) {
      slen++;
    }
    else {
      r = add_compile_string(prev, prev_len, slen, reg);
      if (r != 0) return r;

      prev  = p;
      slen  = 1;
      prev_len = len;
    }

    p += len;
  }

  return add_compile_string(prev, prev_len, slen, reg);
}

static int
compile_string_crude_node(StrNode* sn, regex_t* reg)
{
  if (sn->end <= sn->s)
    return 0;

  return add_compile_string(sn->s, 1 /* sb */, (int )(sn->end - sn->s), reg);
}

static void*
set_multi_byte_cclass(BBuf* mbuf, regex_t* reg)
{
  size_t len;
  void* p;

  len = (size_t )mbuf->used;
  p = xmalloc(len);
  if (IS_NULL(p)) return NULL;

  xmemcpy(p, mbuf->p, len);
  return p;
}

static int
compile_length_cclass_node(CClassNode* cc, regex_t* reg)
{
  return 1;
}

static int
compile_cclass_node(CClassNode* cc, regex_t* reg)
{
  int r;

  if (IS_NULL(cc->mbuf)) {
    r = add_op(reg, IS_NCCLASS_NOT(cc) ? OP_CCLASS_NOT : OP_CCLASS);
    if (r != 0) return r;

    COP(reg)->cclass.bsp = xmalloc(SIZE_BITSET);
    CHECK_NULL_RETURN_MEMERR(COP(reg)->cclass.bsp);
    xmemcpy(COP(reg)->cclass.bsp, cc->bs, SIZE_BITSET);
  }
  else {
    void* p;

    if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {
      r = add_op(reg, IS_NCCLASS_NOT(cc) ? OP_CCLASS_MB_NOT : OP_CCLASS_MB);
      if (r != 0) return r;

      p = set_multi_byte_cclass(cc->mbuf, reg);
      CHECK_NULL_RETURN_MEMERR(p);
      COP(reg)->cclass_mb.mb = p;
    }
    else {
      r = add_op(reg, IS_NCCLASS_NOT(cc) ? OP_CCLASS_MIX_NOT : OP_CCLASS_MIX);
      if (r != 0) return r;

      COP(reg)->cclass_mix.bsp = xmalloc(SIZE_BITSET);
      CHECK_NULL_RETURN_MEMERR(COP(reg)->cclass_mix.bsp);
      xmemcpy(COP(reg)->cclass_mix.bsp, cc->bs, SIZE_BITSET);

      p = set_multi_byte_cclass(cc->mbuf, reg);
      CHECK_NULL_RETURN_MEMERR(p);
      COP(reg)->cclass_mix.mb = p;
    }
  }

  return 0;
}

static void
set_addr_in_repeat_range(regex_t* reg)
{
  int i;

  for (i = 0; i < reg->num_repeat; i++) {
    RepeatRange* p = reg->repeat_range + i;
    int offset = p->u.offset;
    p->u.pcode = reg->ops + offset;
  }
}

static int
entry_repeat_range(regex_t* reg, int id, int lower, int upper, int ops_index)
{
#define REPEAT_RANGE_ALLOC  4

  RepeatRange* p;

  if (reg->repeat_range_alloc == 0) {
    p = (RepeatRange* )xmalloc(sizeof(RepeatRange) * REPEAT_RANGE_ALLOC);
    CHECK_NULL_RETURN_MEMERR(p);
    reg->repeat_range = p;
    reg->repeat_range_alloc = REPEAT_RANGE_ALLOC;
  }
  else if (reg->repeat_range_alloc <= id) {
    int n;
    n = reg->repeat_range_alloc + REPEAT_RANGE_ALLOC;
    p = (RepeatRange* )xrealloc(reg->repeat_range, sizeof(RepeatRange) * n);
    CHECK_NULL_RETURN_MEMERR(p);
    reg->repeat_range = p;
    reg->repeat_range_alloc = n;
  }
  else {
    p = reg->repeat_range;
  }

  p[id].lower    = lower;
  p[id].upper    = (IS_INFINITE_REPEAT(upper) ? 0x7fffffff : upper);
  p[id].u.offset = ops_index;
  return 0;
}

static int
compile_range_repeat_node(QuantNode* qn, int target_len, int emptiness,
                          regex_t* reg, ParseEnv* env)
{
  int r;
  int num_repeat = reg->num_repeat++;

  r = add_op(reg, qn->greedy ? OP_REPEAT : OP_REPEAT_NG);
  if (r != 0) return r;

  COP(reg)->repeat.id   = num_repeat;
  COP(reg)->repeat.addr = SIZE_INC + target_len + OPSIZE_REPEAT_INC;

  r = entry_repeat_range(reg, num_repeat, qn->lower, qn->upper,
                         COP_CURR_OFFSET(reg) + OPSIZE_REPEAT);
  if (r != 0) return r;

  r = compile_quant_body_with_empty_check(qn, reg, env);
  if (r != 0) return r;

  r = add_op(reg, qn->greedy ? OP_REPEAT_INC : OP_REPEAT_INC_NG);
  if (r != 0) return r;

  COP(reg)->repeat_inc.id = num_repeat;
  return r;
}

static int
is_anychar_infinite_greedy(QuantNode* qn)
{
  if (qn->greedy && IS_INFINITE_REPEAT(qn->upper) &&
      ND_IS_ANYCHAR(ND_QUANT_BODY(qn)))
    return 1;
  else
    return 0;
}

#define QUANTIFIER_EXPAND_LIMIT_SIZE   10
#define CKN_ON   (ckn > 0)

static int
compile_length_quantifier_node(QuantNode* qn, regex_t* reg, ParseEnv* env)
{
  int len, mod_tlen;
  int infinite = IS_INFINITE_REPEAT(qn->upper);
  enum BodyEmptyType emptiness = qn->emptiness;
  int tlen = compile_length_tree(ND_QUANT_BODY(qn), reg, env);

  if (tlen < 0) return tlen;
  if (tlen == 0) return 0;

  /* anychar repeat */
  if (is_anychar_infinite_greedy(qn)) {
    if (qn->lower <= 1 ||
        len_multiply_cmp((OnigLen )tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0) {
      if (IS_NOT_NULL(qn->next_head_exact))
        return OPSIZE_ANYCHAR_STAR_PEEK_NEXT + tlen * qn->lower;
      else
        return OPSIZE_ANYCHAR_STAR + tlen * qn->lower;
    }
  }

  mod_tlen = tlen;
  if (emptiness != BODY_IS_NOT_EMPTY)
    mod_tlen += OPSIZE_EMPTY_CHECK_START + OPSIZE_EMPTY_CHECK_END;

  if (infinite &&
      (qn->lower <= 1 ||
       len_multiply_cmp(tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
    if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
      len = OPSIZE_JUMP;
    }
    else {
      len = tlen * qn->lower;
    }

    if (qn->greedy) {
#ifdef USE_OP_PUSH_OR_JUMP_EXACT
      if (IS_NOT_NULL(qn->head_exact))
        len += OPSIZE_PUSH_OR_JUMP_EXACT1 + mod_tlen + OPSIZE_JUMP;
      else
#endif
      if (IS_NOT_NULL(qn->next_head_exact))
        len += OPSIZE_PUSH_IF_PEEK_NEXT + mod_tlen + OPSIZE_JUMP;
      else
        len += OPSIZE_PUSH + mod_tlen + OPSIZE_JUMP;
    }
    else
      len += OPSIZE_JUMP + mod_tlen + OPSIZE_PUSH;
  }
  else if (qn->upper == 0) {
    if (qn->include_referred != 0) { /* /(?<n>..){0}/ */
      len = OPSIZE_JUMP + tlen;
    }
    else
      len = 0;
  }
  else if (!infinite && qn->greedy &&
           (qn->upper == 1 ||
            len_multiply_cmp((OnigLen )tlen + OPSIZE_PUSH, qn->upper,
                             QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
    len = tlen * qn->lower;
    len += (OPSIZE_PUSH + tlen) * (qn->upper - qn->lower);
  }
  else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) { /* '??' */
    len = OPSIZE_PUSH + OPSIZE_JUMP + tlen;
  }
  else {
    len = OPSIZE_REPEAT_INC + mod_tlen + OPSIZE_REPEAT;
  }

  return len;
}

static int
compile_quantifier_node(QuantNode* qn, regex_t* reg, ParseEnv* env)
{
  int i, r, mod_tlen;
  int infinite = IS_INFINITE_REPEAT(qn->upper);
  enum BodyEmptyType emptiness = qn->emptiness;
  int tlen = compile_length_tree(ND_QUANT_BODY(qn), reg, env);

  if (tlen < 0) return tlen;
  if (tlen == 0) return 0;

  if (is_anychar_infinite_greedy(qn) &&
      (qn->lower <= 1 ||
       len_multiply_cmp((OnigLen )tlen, qn->lower,
                        QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
    r = compile_tree_n_times(ND_QUANT_BODY(qn), qn->lower, reg, env);
    if (r != 0) return r;
    if (IS_NOT_NULL(qn->next_head_exact)) {
      r = add_op(reg, ND_IS_MULTILINE(ND_QUANT_BODY(qn)) ?
                 OP_ANYCHAR_ML_STAR_PEEK_NEXT : OP_ANYCHAR_STAR_PEEK_NEXT);
      if (r != 0) return r;

      COP(reg)->anychar_star_peek_next.c = STR_(qn->next_head_exact)->s[0];
      return 0;
    }
    else {
      r = add_op(reg, ND_IS_MULTILINE(ND_QUANT_BODY(qn)) ?
                 OP_ANYCHAR_ML_STAR : OP_ANYCHAR_STAR);
      return r;
    }
  }

  mod_tlen = tlen;
  if (emptiness != BODY_IS_NOT_EMPTY)
    mod_tlen += OPSIZE_EMPTY_CHECK_START + OPSIZE_EMPTY_CHECK_END;

  if (infinite &&
      (qn->lower <= 1 ||
       len_multiply_cmp((OnigLen )tlen, qn->lower,
                        QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
    int addr;

    if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
      r = add_op(reg, OP_JUMP);
      if (r != 0) return r;
      if (qn->greedy) {
#ifdef USE_OP_PUSH_OR_JUMP_EXACT
        if (IS_NOT_NULL(qn->head_exact))
          COP(reg)->jump.addr = OPSIZE_PUSH_OR_JUMP_EXACT1 + SIZE_INC;
        else
#endif
        if (IS_NOT_NULL(qn->next_head_exact))
          COP(reg)->jump.addr = OPSIZE_PUSH_IF_PEEK_NEXT + SIZE_INC;
        else
          COP(reg)->jump.addr = OPSIZE_PUSH + SIZE_INC;
      }
      else {
        COP(reg)->jump.addr = OPSIZE_JUMP + SIZE_INC;
      }
    }
    else {
      r = compile_tree_n_times(ND_QUANT_BODY(qn), qn->lower, reg, env);
      if (r != 0) return r;
    }

    if (qn->greedy) {
#ifdef USE_OP_PUSH_OR_JUMP_EXACT
      if (IS_NOT_NULL(qn->head_exact)) {
        r = add_op(reg, OP_PUSH_OR_JUMP_EXACT1);
        if (r != 0) return r;
        COP(reg)->push_or_jump_exact1.addr = SIZE_INC + mod_tlen + OPSIZE_JUMP;
        COP(reg)->push_or_jump_exact1.c    = STR_(qn->head_exact)->s[0];

        r = compile_quant_body_with_empty_check(qn, reg, env);
        if (r != 0) return r;

        addr = -(mod_tlen + (int )OPSIZE_PUSH_OR_JUMP_EXACT1);
      }
      else
#endif
      if (IS_NOT_NULL(qn->next_head_exact)) {
        r = add_op(reg, OP_PUSH_IF_PEEK_NEXT);
        if (r != 0) return r;
        COP(reg)->push_if_peek_next.addr = SIZE_INC + mod_tlen + OPSIZE_JUMP;
        COP(reg)->push_if_peek_next.c    = STR_(qn->next_head_exact)->s[0];

        r = compile_quant_body_with_empty_check(qn, reg, env);
        if (r != 0) return r;

        addr = -(mod_tlen + (int )OPSIZE_PUSH_IF_PEEK_NEXT);
      }
      else {
        r = add_op(reg, OP_PUSH);
        if (r != 0) return r;
        COP(reg)->push.addr = SIZE_INC + mod_tlen + OPSIZE_JUMP;

        r = compile_quant_body_with_empty_check(qn, reg, env);
        if (r != 0) return r;

        addr = -(mod_tlen + (int )OPSIZE_PUSH);
      }

      r = add_op(reg, OP_JUMP);
      if (r != 0) return r;
      COP(reg)->jump.addr = addr;
    }
    else {
      r = add_op(reg, OP_JUMP);
      if (r != 0) return r;
      COP(reg)->jump.addr = mod_tlen + SIZE_INC;

      r = compile_quant_body_with_empty_check(qn, reg, env);
      if (r != 0) return r;

      r = add_op(reg, OP_PUSH);
      if (r != 0) return r;
      COP(reg)->push.addr = -mod_tlen;
    }
  }
  else if (qn->upper == 0) {
    if (qn->include_referred != 0) { /* /(?<n>..){0}/ */
      r = add_op(reg, OP_JUMP);
      if (r != 0) return r;
      COP(reg)->jump.addr = tlen + SIZE_INC;

      r = compile_tree(ND_QUANT_BODY(qn), reg, env);
    }
    else {
      /* Nothing output */
      r = 0;
    }
  }
  else if (! infinite && qn->greedy &&
           (qn->upper == 1 ||
            len_multiply_cmp((OnigLen )tlen + OPSIZE_PUSH, qn->upper,
                             QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
    int n = qn->upper - qn->lower;

    r = compile_tree_n_times(ND_QUANT_BODY(qn), qn->lower, reg, env);
    if (r != 0) return r;

    for (i = 0; i < n; i++) {
      int v = onig_positive_int_multiply(n - i, tlen + OPSIZE_PUSH);
      if (v < 0) return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE;

      r = add_op(reg, OP_PUSH);
      if (r != 0) return r;
      COP(reg)->push.addr = v;

      r = compile_tree(ND_QUANT_BODY(qn), reg, env);
      if (r != 0) return r;
    }
  }
  else if (! qn->greedy && qn->upper == 1 && qn->lower == 0) { /* '??' */
    r = add_op(reg, OP_PUSH);
    if (r != 0) return r;
    COP(reg)->push.addr = SIZE_INC + OPSIZE_JUMP;

    r = add_op(reg, OP_JUMP);
    if (r != 0) return r;
    COP(reg)->jump.addr = tlen + SIZE_INC;

    r = compile_tree(ND_QUANT_BODY(qn), reg, env);
  }
  else {
    r = compile_range_repeat_node(qn, mod_tlen, emptiness, reg, env);
  }
  return r;
}

static int
compile_length_option_node(BagNode* node, regex_t* reg, ParseEnv* env)
{
  int tlen;

  tlen = compile_length_tree(ND_BAG_BODY(node), reg, env);

  return tlen;
}

static int
compile_option_node(BagNode* node, regex_t* reg, ParseEnv* env)
{
  int r;

  r = compile_tree(ND_BAG_BODY(node), reg, env);

  return r;
}

static int
compile_length_bag_node(BagNode* node, regex_t* reg, ParseEnv* env)
{
  int len;
  int tlen;

  if (node->type == BAG_OPTION)
    return compile_length_option_node(node, reg, env);

  if (ND_BAG_BODY(node)) {
    tlen = compile_length_tree(ND_BAG_BODY(node), reg, env);
    if (tlen < 0) return tlen;
  }
  else
    tlen = 0;

  switch (node->type) {
  case BAG_MEMORY:
#ifdef USE_CALL

    if (node->m.regnum == 0 && ND_IS_CALLED(node)) {
      len = tlen + OPSIZE_CALL + OPSIZE_JUMP + OPSIZE_RETURN;
      return len;
    }

    if (ND_IS_CALLED(node)) {
      len = OPSIZE_MEM_START_PUSH + tlen
        + OPSIZE_CALL + OPSIZE_JUMP + OPSIZE_RETURN;
      if (MEM_STATUS_AT0(reg->push_mem_end, node->m.regnum))
        len += (ND_IS_RECURSION(node)
                ? OPSIZE_MEM_END_PUSH_REC : OPSIZE_MEM_END_PUSH);
      else
        len += (ND_IS_RECURSION(node)
                ? OPSIZE_MEM_END_REC : OPSIZE_MEM_END);
    }
    else if (ND_IS_RECURSION(node)) {
      len = OPSIZE_MEM_START_PUSH;
      len += tlen + (MEM_STATUS_AT0(reg->push_mem_end, node->m.regnum)
                     ? OPSIZE_MEM_END_PUSH_REC : OPSIZE_MEM_END_REC);
    }
    else
#endif
    {
      if (MEM_STATUS_AT0(reg->push_mem_start, node->m.regnum))
        len = OPSIZE_MEM_START_PUSH;
      else
        len = OPSIZE_MEM_START;

      len += tlen + (MEM_STATUS_AT0(reg->push_mem_end, node->m.regnum)
                     ? OPSIZE_MEM_END_PUSH : OPSIZE_MEM_END);
    }
    break;

  case BAG_STOP_BACKTRACK:
    if (ND_IS_STRICT_REAL_REPEAT(node)) {
      int v;
      QuantNode* qn;

      qn = QUANT_(ND_BAG_BODY(node));
      tlen = compile_length_tree(ND_QUANT_BODY(qn), reg, env);
      if (tlen < 0) return tlen;

      v = onig_positive_int_multiply(qn->lower, tlen);
      if (v < 0) return ONIGERR_TOO_BIG_NUMBER_FOR_REPEAT_RANGE;
      len = v + OPSIZE_PUSH + tlen + OPSIZE_POP + OPSIZE_JUMP;
    }
    else {
      len = OPSIZE_MARK + tlen + OPSIZE_CUT_TO_MARK;
    }
    break;

  case BAG_IF_ELSE:
    {
      Node* cond = ND_BAG_BODY(node);
      Node* Then = node->te.Then;
      Node* Else = node->te.Else;

      len = compile_length_tree(cond, reg, env);
      if (len < 0) return len;
      len += OPSIZE_PUSH + OPSIZE_MARK + OPSIZE_CUT_TO_MARK;

      if (IS_NOT_NULL(Then)) {
        tlen = compile_length_tree(Then, reg, env);
        if (tlen < 0) return tlen;
        len += tlen;
      }

      len += OPSIZE_JUMP + OPSIZE_CUT_TO_MARK;

      if (IS_NOT_NULL(Else)) {
        tlen = compile_length_tree(Else, reg, env);
        if (tlen < 0) return tlen;
        len += tlen;
      }
    }
    break;

  case BAG_OPTION:
    /* never come here, but set for escape warning */
    len = 0;
    break;

  default:
    return ONIGERR_TYPE_BUG;
    break;
  }

  return len;
}

static int
compile_bag_memory_node(BagNode* node, regex_t* reg, ParseEnv* env)
{
  int r;

#ifdef USE_CALL
  if (ND_IS_CALLED(node)) {
    int len;

    r = add_op(reg, OP_CALL);
    if (r != 0) return r;

    node->m.called_addr = COP_CURR_OFFSET(reg) + 1 + OPSIZE_JUMP;
    ND_STATUS_ADD(node, FIXED_ADDR);
    COP(reg)->call.addr = (int )node->m.called_addr;

    if (node->m.regnum == 0) {
      len = compile_length_tree(ND_BAG_BODY(node), reg, env);
      len += OPSIZE_RETURN;

      r = add_op(reg, OP_JUMP);
      if (r != 0) return r;
      COP(reg)->jump.addr = len + SIZE_INC;

      r = compile_tree(ND_BAG_BODY(node), reg, env);
      if (r != 0) return r;

      r = add_op(reg, OP_RETURN);
      return r;
    }
    else {
      len = compile_length_tree(ND_BAG_BODY(node), reg, env);
      len += (OPSIZE_MEM_START_PUSH + OPSIZE_RETURN);
      if (MEM_STATUS_AT0(reg->push_mem_end, node->m.regnum))
        len += (ND_IS_RECURSION(node)
                ? OPSIZE_MEM_END_PUSH_REC : OPSIZE_MEM_END_PUSH);
      else
        len += (ND_IS_RECURSION(node) ? OPSIZE_MEM_END_REC : OPSIZE_MEM_END);

      r = add_op(reg, OP_JUMP);
      if (r != 0) return r;
      COP(reg)->jump.addr = len + SIZE_INC;
    }
  }
#endif

  if (MEM_STATUS_AT0(reg->push_mem_start, node->m.regnum))
    r = add_op(reg, OP_MEM_START_PUSH);
  else
    r = add_op(reg, OP_MEM_START);
  if (r != 0) return r;
  COP(reg)->memory_start.num = node->m.regnum;

  r = compile_tree(ND_BAG_BODY(node), reg, env);
  if (r != 0) return r;

#ifdef USE_CALL
  if (MEM_STATUS_AT0(reg->push_mem_end, node->m.regnum))
    r = add_op(reg, (ND_IS_RECURSION(node)
                     ? OP_MEM_END_PUSH_REC : OP_MEM_END_PUSH));
  else
    r = add_op(reg, (ND_IS_RECURSION(node) ? OP_MEM_END_REC : OP_MEM_END));
  if (r != 0) return r;
  COP(reg)->memory_end.num = node->m.regnum;

  if (ND_IS_CALLED(node)) {
    r = add_op(reg, OP_RETURN);
  }
#else
  if (MEM_STATUS_AT0(reg->push_mem_end, node->m.regnum))
    r = add_op(reg, OP_MEM_END_PUSH);
  else
    r = add_op(reg, OP_MEM_END);
  if (r != 0) return r;
  COP(reg)->memory_end.num = node->m.regnum;
#endif

  return r;
}

static int
compile_bag_node(BagNode* node, regex_t* reg, ParseEnv* env)
{
  int r, len;

  switch (node->type) {
  case BAG_MEMORY:
    r = compile_bag_memory_node(node, reg, env);
    break;

  case BAG_OPTION:
    r = compile_option_node(node, reg, env);
    break;

  case BAG_STOP_BACKTRACK:
    if (ND_IS_STRICT_REAL_REPEAT(node)) {
      QuantNode* qn = QUANT_(ND_BAG_BODY(node));
      r = compile_tree_n_times(ND_QUANT_BODY(qn), qn->lower, reg, env);
      if (r != 0) return r;

      len = compile_length_tree(ND_QUANT_BODY(qn), reg, env);
      if (len < 0) return len;

      r = add_op(reg, OP_PUSH);
      if (r != 0) return r;
      COP(reg)->push.addr = SIZE_INC + len + OPSIZE_POP + OPSIZE_JUMP;

      r = compile_tree(ND_QUANT_BODY(qn), reg, env);
      if (r != 0) return r;
      r = add_op(reg, OP_POP);
      if (r != 0) return r;

      r = add_op(reg, OP_JUMP);
      if (r != 0) return r;
      COP(reg)->jump.addr = -((int )OPSIZE_PUSH + len + (int )OPSIZE_POP);
    }
    else {
      MemNumType mid;

      ID_ENTRY(env, mid);
      r = add_op(reg, OP_MARK);
      if (r != 0) return r;
      COP(reg)->mark.id = mid;
      COP(reg)->mark.save_pos = 0;

      r = compile_tree(ND_BAG_BODY(node), reg, env);
      if (r != 0) return r;
      r = add_op(reg, OP_CUT_TO_MARK);
      if (r != 0) return r;
      COP(reg)->cut_to_mark.id = mid;
      COP(reg)->cut_to_mark.restore_pos = 0;
    }
    break;

  case BAG_IF_ELSE:
    {
      int cond_len, then_len, else_len, jump_len;
      MemNumType mid;
      Node* cond = ND_BAG_BODY(node);
      Node* Then = node->te.Then;
      Node* Else = node->te.Else;

      ID_ENTRY(env, mid);

      r = add_op(reg, OP_MARK);
      if (r != 0) return r;
      COP(reg)->mark.id = mid;
      COP(reg)->mark.save_pos = 0;

      cond_len = compile_length_tree(cond, reg, env);
      if (cond_len < 0) return cond_len;
      if (IS_NOT_NULL(Then)) {
        then_len = compile_length_tree(Then, reg, env);
        if (then_len < 0) return then_len;
      }
      else
        then_len = 0;

      jump_len = cond_len + then_len + OPSIZE_CUT_TO_MARK + OPSIZE_JUMP;

      r = add_op(reg, OP_PUSH);
      if (r != 0) return r;
      COP(reg)->push.addr = SIZE_INC + jump_len;

      r = compile_tree(cond, reg, env);
      if (r != 0) return r;
      r = add_op(reg, OP_CUT_TO_MARK);
      if (r != 0) return r;
      COP(reg)->cut_to_mark.id = mid;
      COP(reg)->cut_to_mark.restore_pos = 0;

      if (IS_NOT_NULL(Then)) {
        r = compile_tree(Then, reg, env);
        if (r != 0) return r;
      }

      if (IS_NOT_NULL(Else)) {
        else_len = compile_length_tree(Else, reg, env);
        if (else_len < 0) return else_len;
      }
      else
        else_len = 0;

      r = add_op(reg, OP_JUMP);
      if (r != 0) return r;
      COP(reg)->jump.addr = OPSIZE_CUT_TO_MARK + else_len + SIZE_INC;

      r = add_op(reg, OP_CUT_TO_MARK);
      if (r != 0) return r;
      COP(reg)->cut_to_mark.id = mid;
      COP(reg)->cut_to_mark.restore_pos = 0;

      if (IS_NOT_NULL(Else)) {
        r = compile_tree(Else, reg, env);
      }
    }
    break;

  default:
    return ONIGERR_TYPE_BUG;
    break;
  }

  return r;
}

static int
compile_length_anchor_node(AnchorNode* node, regex_t* reg, ParseEnv* env)
{
  int len;
  int tlen = 0;

  if (IS_NOT_NULL(ND_ANCHOR_BODY(node))) {
    tlen = compile_length_tree(ND_ANCHOR_BODY(node), reg, env);
    if (tlen < 0) return tlen;
  }

  switch (node->type) {
  case ANCR_PREC_READ:
    len = OPSIZE_MARK + tlen + OPSIZE_CUT_TO_MARK;
    break;
  case ANCR_PREC_READ_NOT:
    len = OPSIZE_PUSH + OPSIZE_MARK + tlen + OPSIZE_POP_TO_MARK + OPSIZE_POP + OPSIZE_FAIL;
    break;
  case ANCR_LOOK_BEHIND:
    if (node->char_min_len == node->char_max_len)
      len = OPSIZE_MARK + OPSIZE_STEP_BACK_START + tlen + OPSIZE_CUT_TO_MARK;
    else {
      len = OPSIZE_SAVE_VAL + OPSIZE_UPDATE_VAR + OPSIZE_MARK + OPSIZE_PUSH + OPSIZE_UPDATE_VAR + OPSIZE_FAIL + OPSIZE_JUMP + OPSIZE_STEP_BACK_START + OPSIZE_STEP_BACK_NEXT + tlen + OPSIZE_CHECK_POSITION + OPSIZE_CUT_TO_MARK + OPSIZE_UPDATE_VAR;

      if (IS_NOT_NULL(node->lead_node)) {
        int llen = compile_length_tree(node->lead_node, reg, env);
        if (llen < 0) return llen;

        len += OPSIZE_MOVE + llen;
      }

      if ((env->flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0)
        len += OPSIZE_SAVE_VAL + OPSIZE_UPDATE_VAR;
    }
    break;
  case ANCR_LOOK_BEHIND_NOT:
    if (node->char_min_len == node->char_max_len)
      len = OPSIZE_MARK + OPSIZE_PUSH + OPSIZE_STEP_BACK_START + tlen + OPSIZE_POP_TO_MARK + OPSIZE_FAIL + OPSIZE_POP;
    else {
      len = OPSIZE_SAVE_VAL + OPSIZE_UPDATE_VAR + OPSIZE_MARK + OPSIZE_PUSH + OPSIZE_STEP_BACK_START + OPSIZE_STEP_BACK_NEXT + tlen + OPSIZE_CHECK_POSITION + OPSIZE_POP_TO_MARK + OPSIZE_UPDATE_VAR + OPSIZE_POP + OPSIZE_FAIL + OPSIZE_UPDATE_VAR + OPSIZE_POP + OPSIZE_POP;

      if (IS_NOT_NULL(node->lead_node)) {
        int llen = compile_length_tree(node->lead_node, reg, env);
        if (llen < 0) return llen;

        len += OPSIZE_MOVE + llen;
      }

      if ((env->flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0)
        len += OPSIZE_SAVE_VAL + OPSIZE_UPDATE_VAR;
    }
    break;

  case ANCR_WORD_BOUNDARY:
  case ANCR_NO_WORD_BOUNDARY:
#ifdef USE_WORD_BEGIN_END
  case ANCR_WORD_BEGIN:
  case ANCR_WORD_END:
#endif
    len = OPSIZE_WORD_BOUNDARY;
    break;

  case ANCR_TEXT_SEGMENT_BOUNDARY:
  case ANCR_NO_TEXT_SEGMENT_BOUNDARY:
    len = SIZE_OPCODE;
    break;

  default:
    len = SIZE_OPCODE;
    break;
  }

  return len;
}

static int
compile_anchor_look_behind_node(AnchorNode* node, regex_t* reg, ParseEnv* env)
{
  int r;

  if (node->char_min_len == node->char_max_len) {
    MemNumType mid;

    ID_ENTRY(env, mid);
    r = add_op(reg, OP_MARK);
    if (r != 0) return r;
    COP(reg)->mark.id = mid;
    COP(reg)->mark.save_pos = FALSE;

    r = add_op(reg, OP_STEP_BACK_START);
    if (r != 0) return r;
    COP(reg)->step_back_start.initial   = node->char_min_len;
    COP(reg)->step_back_start.remaining = 0;
    COP(reg)->step_back_start.addr      = 1;

    r = compile_tree(ND_ANCHOR_BODY(node), reg, env);
    if (r != 0) return r;

    r = add_op(reg, OP_CUT_TO_MARK);
    if (r != 0) return r;
    COP(reg)->cut_to_mark.id = mid;
    COP(reg)->cut_to_mark.restore_pos = FALSE;
  }
  else {
    MemNumType mid1, mid2, mid3;
    OnigLen diff;

    if (IS_NOT_NULL(node->lead_node)) {
      MinMaxCharLen ci;

      r = node_char_len(node->lead_node, reg, &ci, env);
      if (r < 0) return r;
      r = add_op(reg, OP_MOVE);
      if (r != 0) return r;
      COP(reg)->move.n = -((RelPositionType )ci.min);
      r = compile_tree(node->lead_node, reg, env);
      if (r != 0) return r;
    }

    ID_ENTRY(env, mid1);
    r = add_op(reg, OP_SAVE_VAL);
    if (r != 0) return r;
    COP(reg)->save_val.type = SAVE_RIGHT_RANGE;
    COP(reg)->save_val.id   = mid1;

    r = add_op(reg, OP_UPDATE_VAR);
    if (r != 0) return r;
    COP(reg)->update_var.type = UPDATE_VAR_RIGHT_RANGE_TO_S;

    ID_ENTRY(env, mid2);
    r = add_op(reg, OP_MARK);
    if (r != 0) return r;
    COP(reg)->mark.id = mid2;
    COP(reg)->mark.save_pos = FALSE;

    r = add_op(reg, OP_PUSH);
    if (r != 0) return r;
    COP(reg)->push.addr = SIZE_INC + OPSIZE_JUMP;

    r = add_op(reg, OP_JUMP);
    if (r != 0) return r;
    COP(reg)->jump.addr = SIZE_INC + OPSIZE_UPDATE_VAR + OPSIZE_FAIL;

    r = add_op(reg, OP_UPDATE_VAR);
    if (r != 0) return r;
    COP(reg)->update_var.type = UPDATE_VAR_RIGHT_RANGE_FROM_STACK;
    COP(reg)->update_var.id    = mid1;
    COP(reg)->update_var.clear = FALSE;
    r = add_op(reg, OP_FAIL);
    if (r != 0) return r;

    if ((env->flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0) {
      ID_ENTRY(env, mid3);
      r = add_op(reg, OP_SAVE_VAL);
      if (r != 0) return r;
      COP(reg)->save_val.type = SAVE_RIGHT_RANGE;
      COP(reg)->save_val.id   = mid3;
    }

    r = add_op(reg, OP_STEP_BACK_START);
    if (r != 0) return r;

    if (node->char_max_len != INFINITE_LEN)
      diff = node->char_max_len - node->char_min_len;
    else
      diff = INFINITE_LEN;

    COP(reg)->step_back_start.initial   = node->char_min_len;
    COP(reg)->step_back_start.remaining = diff;
    COP(reg)->step_back_start.addr      = 2;

    r = add_op(reg, OP_STEP_BACK_NEXT);
    if (r != 0) return r;

    r = compile_tree(ND_ANCHOR_BODY(node), reg, env);
    if (r != 0) return r;

    if ((env->flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0) {
      r = add_op(reg, OP_UPDATE_VAR);
      if (r != 0) return r;
      COP(reg)->update_var.type = UPDATE_VAR_RIGHT_RANGE_FROM_STACK;
      COP(reg)->update_var.id    = mid3;
      COP(reg)->update_var.clear = FALSE;
    }

    r = add_op(reg, OP_CHECK_POSITION);
    if (r != 0) return r;
    COP(reg)->check_position.type = CHECK_POSITION_CURRENT_RIGHT_RANGE;

    r = add_op(reg, OP_CUT_TO_MARK);
    if (r != 0) return r;
    COP(reg)->cut_to_mark.id = mid2;
    COP(reg)->cut_to_mark.restore_pos = FALSE;

    r = add_op(reg, OP_UPDATE_VAR);
    if (r != 0) return r;
    COP(reg)->update_var.type = UPDATE_VAR_RIGHT_RANGE_FROM_STACK;
    COP(reg)->update_var.id    = mid1;
    COP(reg)->update_var.clear = TRUE;
  }

  return r;
}

static int
compile_anchor_look_behind_not_node(AnchorNode* node, regex_t* reg,
                                    ParseEnv* env)
{
  int r;
  int len;

  len = compile_length_tree(ND_ANCHOR_BODY(node), reg, env);

  if (node->char_min_len == node->char_max_len) {
    MemNumType mid;

    ID_ENTRY(env, mid);
    r = add_op(reg, OP_MARK);
    if (r != 0) return r;
    COP(reg)->mark.id = mid;
    COP(reg)->mark.save_pos = FALSE;

    r = add_op(reg, OP_PUSH);
    if (r != 0) return r;
    COP(reg)->push.addr = SIZE_INC + OPSIZE_STEP_BACK_START + len + OPSIZE_POP_TO_MARK + OPSIZE_FAIL;

    r = add_op(reg, OP_STEP_BACK_START);
    if (r != 0) return r;
    COP(reg)->step_back_start.initial   = node->char_min_len;
    COP(reg)->step_back_start.remaining = 0;
    COP(reg)->step_back_start.addr      = 1;

    r = compile_tree(ND_ANCHOR_BODY(node), reg, env);
    if (r != 0) return r;

    r = add_op(reg, OP_POP_TO_MARK);
    if (r != 0) return r;
    COP(reg)->pop_to_mark.id = mid;
    r = add_op(reg, OP_FAIL);
    if (r != 0) return r;
    r = add_op(reg, OP_POP);
  }
  else {
    MemNumType mid1, mid2, mid3;
    OnigLen diff;

    ID_ENTRY(env, mid1);
    r = add_op(reg, OP_SAVE_VAL);
    if (r != 0) return r;
    COP(reg)->save_val.type = SAVE_RIGHT_RANGE;
    COP(reg)->save_val.id   = mid1;

    r = add_op(reg, OP_UPDATE_VAR);
    if (r != 0) return r;
    COP(reg)->update_var.type = UPDATE_VAR_RIGHT_RANGE_TO_S;

    ID_ENTRY(env, mid2);
    r = add_op(reg, OP_MARK);
    if (r != 0) return r;
    COP(reg)->mark.id = mid2;
    COP(reg)->mark.save_pos = FALSE;

    r = add_op(reg, OP_PUSH);
    if (r != 0) return r;

    COP(reg)->push.addr = SIZE_INC + OPSIZE_STEP_BACK_START + OPSIZE_STEP_BACK_NEXT + len + OPSIZE_CHECK_POSITION + OPSIZE_POP_TO_MARK + OPSIZE_UPDATE_VAR + OPSIZE_POP + OPSIZE_FAIL;
    if ((env->flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0)
      COP(reg)->push.addr += OPSIZE_SAVE_VAL + OPSIZE_UPDATE_VAR;

    if (IS_NOT_NULL(node->lead_node)) {
      int clen;
      MinMaxCharLen ci;

      clen = compile_length_tree(node->lead_node, reg, env);
      COP(reg)->push.addr += OPSIZE_MOVE + clen;

      r = node_char_len(node->lead_node, reg, &ci, env);
      if (r < 0) return r;
      r = add_op(reg, OP_MOVE);
      if (r != 0) return r;
      COP(reg)->move.n = -((RelPositionType )ci.min);

      r = compile_tree(node->lead_node, reg, env);
      if (r != 0) return r;
    }

    if ((env->flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0) {
      ID_ENTRY(env, mid3);
      r = add_op(reg, OP_SAVE_VAL);
      if (r != 0) return r;
      COP(reg)->save_val.type = SAVE_RIGHT_RANGE;
      COP(reg)->save_val.id   = mid3;
    }

    r = add_op(reg, OP_STEP_BACK_START);
    if (r != 0) return r;

    if (node->char_max_len != INFINITE_LEN)
      diff = node->char_max_len - node->char_min_len;
    else
      diff = INFINITE_LEN;

    COP(reg)->step_back_start.initial   = node->char_min_len;
    COP(reg)->step_back_start.remaining = diff;
    COP(reg)->step_back_start.addr      = 2;

    r = add_op(reg, OP_STEP_BACK_NEXT);
    if (r != 0) return r;

    r = compile_tree(ND_ANCHOR_BODY(node), reg, env);
    if (r != 0) return r;

    if ((env->flags & PE_FLAG_HAS_ABSENT_STOPPER) != 0) {
      r = add_op(reg, OP_UPDATE_VAR);
      if (r != 0) return r;
      COP(reg)->update_var.type = UPDATE_VAR_RIGHT_RANGE_FROM_STACK;
      COP(reg)->update_var.id    = mid3;
      COP(reg)->update_var.clear = FALSE;
    }

    r = add_op(reg, OP_CHECK_POSITION);
    if (r != 0) return r;
    COP(reg)->check_position.type = CHECK_POSITION_CURRENT_RIGHT_RANGE;

    r = add_op(reg, OP_POP_TO_MARK);
    if (r != 0) return r;
    COP(reg)->pop_to_mark.id = mid2;

    r = add_op(reg, OP_UPDATE_VAR);
    if (r != 0) return r;
    COP(reg)->update_var.type = UPDATE_VAR_RIGHT_RANGE_FROM_STACK;
    COP(reg)->update_var.id   = mid1;
    COP(reg)->update_var.clear = FALSE;

    r = add_op(reg, OP_POP); /* pop save val */
    if (r != 0) return r;
    r = add_op(reg, OP_FAIL);
    if (r != 0) return r;

    r = add_op(reg, OP_UPDATE_VAR);
    if (r != 0) return r;
    COP(reg)->update_var.type = UPDATE_VAR_RIGHT_RANGE_FROM_STACK;
    COP(reg)->update_var.id   = mid1;
    COP(reg)->update_var.clear = FALSE;

    r = add_op(reg, OP_POP); /* pop mark */
    if (r != 0) return r;
    r = add_op(reg, OP_POP); /* pop save val */
  }

  return r;
}

static int
compile_anchor_node(AnchorNode* node, regex_t* reg, ParseEnv* env)
{
  int r, len;
  enum OpCode op;
  MemNumType mid;

  switch (node->type) {
  case ANCR_BEGIN_BUF:      r = add_op(reg, OP_BEGIN_BUF);      break;
  case ANCR_END_BUF:        r = add_op(reg, OP_END_BUF);        break;
  case ANCR_BEGIN_LINE:     r = add_op(reg, OP_BEGIN_LINE);     break;
  case ANCR_END_LINE:       r = add_op(reg, OP_END_LINE);       break;
  case ANCR_SEMI_END_BUF:   r = add_op(reg, OP_SEMI_END_BUF);   break;
  case ANCR_BEGIN_POSITION:
    r = add_op(reg, OP_CHECK_POSITION);
    if (r != 0) return r;
    COP(reg)->check_position.type = CHECK_POSITION_SEARCH_START;
    break;

  case ANCR_WORD_BOUNDARY:
    op = OP_WORD_BOUNDARY;
  word:
    r = add_op(reg, op);
    if (r != 0) return r;
    COP(reg)->word_boundary.mode = (ModeType )node->ascii_mode;
    break;

  case ANCR_NO_WORD_BOUNDARY:
    op = OP_NO_WORD_BOUNDARY; goto word;
    break;
#ifdef USE_WORD_BEGIN_END
  case ANCR_WORD_BEGIN:
    op = OP_WORD_BEGIN; goto word;
    break;
  case ANCR_WORD_END:
    op = OP_WORD_END; goto word;
    break;
#endif

  case ANCR_TEXT_SEGMENT_BOUNDARY:
  case ANCR_NO_TEXT_SEGMENT_BOUNDARY:
    {
      enum TextSegmentBoundaryType type;

      r = add_op(reg, OP_TEXT_SEGMENT_BOUNDARY);
      if (r != 0) return r;

      type = EXTENDED_GRAPHEME_CLUSTER_BOUNDARY;
#ifdef USE_UNICODE_WORD_BREAK
      if (ND_IS_TEXT_SEGMENT_WORD(node))
        type = WORD_BOUNDARY;
#endif

      COP(reg)->text_segment_boundary.type = type;
      COP(reg)->text_segment_boundary.not =
        (node->type == ANCR_NO_TEXT_SEGMENT_BOUNDARY ? 1 : 0);
    }
    break;

  case ANCR_PREC_READ:
    {
      ID_ENTRY(env, mid);
      r = add_op(reg, OP_MARK);
      if (r != 0) return r;
      COP(reg)->mark.id = mid;
      COP(reg)->mark.save_pos = TRUE;

      r = compile_tree(ND_ANCHOR_BODY(node), reg, env);
      if (r != 0) return r;

      r = add_op(reg, OP_CUT_TO_MARK);
      if (r != 0) return r;
      COP(reg)->cut_to_mark.id = mid;
      COP(reg)->cut_to_mark.restore_pos = TRUE;
    }
    break;

  case ANCR_PREC_READ_NOT:
    {
      len = compile_length_tree(ND_ANCHOR_BODY(node), reg, env);
      if (len < 0) return len;

      ID_ENTRY(env, mid);
      r = add_op(reg, OP_PUSH);
      if (r != 0) return r;
      COP(reg)->push.addr = SIZE_INC + OPSIZE_MARK + len +
                            OPSIZE_POP_TO_MARK + OPSIZE_POP + OPSIZE_FAIL;

      r = add_op(reg, OP_MARK);
      if (r != 0) return r;
      COP(reg)->mark.id = mid;
      COP(reg)->mark.save_pos = FALSE;

      r = compile_tree(ND_ANCHOR_BODY(node), reg, env);
      if (r != 0) return r;

      r = add_op(reg, OP_POP_TO_MARK);
      if (r != 0) return r;
      COP(reg)->pop_to_mark.id = mid;

      r = add_op(reg, OP_POP);
      if (r != 0) return r;
      r = add_op(reg, OP_FAIL);
    }
    break;

  case ANCR_LOOK_BEHIND:
    r = compile_anchor_look_behind_node(node, reg, env);
    break;

  case ANCR_LOOK_BEHIND_NOT:
    r = compile_anchor_look_behind_not_node(node, reg, env);
    break;

  default:
    return ONIGERR_TYPE_BUG;
    break;
  }

  return r;
}

static int
compile_gimmick_node(GimmickNode* node, regex_t* reg)
{
  int r = 0;

  switch (node->type) {
  case GIMMICK_FAIL:
    r = add_op(reg, OP_FAIL);
    break;

  case GIMMICK_SAVE:
    r = add_op(reg, OP_SAVE_VAL);
    if (r != 0) return r;
    COP(reg)->save_val.type = node->detail_type;
    COP(reg)->save_val.id   = node->id;
    break;

  case GIMMICK_UPDATE_VAR:
    r = add_op(reg, OP_UPDATE_VAR);
    if (r != 0) return r;
    COP(reg)->update_var.type = node->detail_type;
    COP(reg)->update_var.id   = node->id;
    COP(reg)->update_var.clear = FALSE;
    break;

#ifdef USE_CALLOUT
  case GIMMICK_CALLOUT:
    switch (node->detail_type) {
    case ONIG_CALLOUT_OF_CONTENTS:
    case ONIG_CALLOUT_OF_NAME:
      {
        if (node->detail_type == ONIG_CALLOUT_OF_NAME) {
          r = add_op(reg, OP_CALLOUT_NAME);
          if (r != 0) return r;
          COP(reg)->callout_name.id  = node->id;
          COP(reg)->callout_name.num = node->num;
        }
        else {
          r = add_op(reg, OP_CALLOUT_CONTENTS);
          if (r != 0) return r;
          COP(reg)->callout_contents.num = node->num;
        }
      }
      break;

    default:
      r = ONIGERR_TYPE_BUG;
      break;
    }
#endif
  }

  return r;
}

static int
compile_length_gimmick_node(GimmickNode* node, regex_t* reg)
{
  int len;

  switch (node->type) {
  case GIMMICK_FAIL:
    len = OPSIZE_FAIL;
    break;

  case GIMMICK_SAVE:
    len = OPSIZE_SAVE_VAL;
    break;

  case GIMMICK_UPDATE_VAR:
    len = OPSIZE_UPDATE_VAR;
    break;

#ifdef USE_CALLOUT
  case GIMMICK_CALLOUT:
    switch (node->detail_type) {
    case ONIG_CALLOUT_OF_CONTENTS:
      len = OPSIZE_CALLOUT_CONTENTS;
      break;
    case ONIG_CALLOUT_OF_NAME:
      len = OPSIZE_CALLOUT_NAME;
      break;

    default:
      len = ONIGERR_TYPE_BUG;
      break;
    }
    break;
#endif

  default:
    return ONIGERR_TYPE_BUG;
    break;
  }

  return len;
}

static int
compile_length_tree(Node* node, regex_t* reg, ParseEnv* env)
{
  int len, r;

  switch (ND_TYPE(node)) {
  case ND_LIST:
    len = 0;
    do {
      r = compile_length_tree(ND_CAR(node), reg, env);
      if (r < 0) return r;
      len += r;
    } while (IS_NOT_NULL(node = ND_CDR(node)));
    r = len;
    break;

  case ND_ALT:
    {
      int n;

      n = r = 0;
      do {
        r += compile_length_tree(ND_CAR(node), reg, env);
        n++;
      } while (IS_NOT_NULL(node = ND_CDR(node)));
      r += (OPSIZE_PUSH + OPSIZE_JUMP) * (n - 1);
    }
    break;

  case ND_STRING:
    if (ND_STRING_IS_CRUDE(node))
      r = compile_length_string_crude_node(STR_(node), reg);
    else
      r = compile_length_string_node(node, reg);
    break;

  case ND_CCLASS:
    r = compile_length_cclass_node(CCLASS_(node), reg);
    break;

  case ND_CTYPE:
    r = SIZE_OPCODE;
    break;

  case ND_BACKREF:
    r = OPSIZE_BACKREF;
    break;

#ifdef USE_CALL
  case ND_CALL:
    r = OPSIZE_CALL;
    break;
#endif

  case ND_QUANT:
    r = compile_length_quantifier_node(QUANT_(node), reg, env);
    break;

  case ND_BAG:
    r = compile_length_bag_node(BAG_(node), reg, env);
    break;

  case ND_ANCHOR:
    r = compile_length_anchor_node(ANCHOR_(node), reg, env);
    break;

  case ND_GIMMICK:
    r = compile_length_gimmick_node(GIMMICK_(node), reg);
    break;

  default:
    return ONIGERR_TYPE_BUG;
    break;
  }

  return r;
}

static int
compile_tree(Node* node, regex_t* reg, ParseEnv* env)
{
  int n, len, pos, r = 0;

  switch (ND_TYPE(node)) {
  case ND_LIST:
    do {
      r = compile_tree(ND_CAR(node), reg, env);
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ALT:
    {
      Node* x = node;
      len = 0;
      do {
        len += compile_length_tree(ND_CAR(x), reg, env);
        if (IS_NOT_NULL(ND_CDR(x))) {
          len += OPSIZE_PUSH + OPSIZE_JUMP;
        }
      } while (IS_NOT_NULL(x = ND_CDR(x)));
      pos = COP_CURR_OFFSET(reg) + 1 + len;  /* goal position */

      do {
        len = compile_length_tree(ND_CAR(node), reg, env);
        if (IS_NOT_NULL(ND_CDR(node))) {
          enum OpCode push = ND_IS_SUPER(node) ? OP_PUSH_SUPER : OP_PUSH;
          r = add_op(reg, push);
          if (r != 0) break;
          COP(reg)->push.addr = SIZE_INC + len + OPSIZE_JUMP;
        }
        r = compile_tree(ND_CAR(node), reg, env);
        if (r != 0) break;
        if (IS_NOT_NULL(ND_CDR(node))) {
          len = pos - (COP_CURR_OFFSET(reg) + 1);
          r = add_op(reg, OP_JUMP);
          if (r != 0) break;
          COP(reg)->jump.addr = len;
        }
      } while (IS_NOT_NULL(node = ND_CDR(node)));
    }
    break;

  case ND_STRING:
    if (ND_STRING_IS_CRUDE(node))
      r = compile_string_crude_node(STR_(node), reg);
    else
      r = compile_string_node(node, reg);
    break;

  case ND_CCLASS:
    r = compile_cclass_node(CCLASS_(node), reg);
    break;

  case ND_CTYPE:
    {
      int op;

      switch (CTYPE_(node)->ctype) {
      case CTYPE_ANYCHAR:
        r = add_op(reg, ND_IS_MULTILINE(node) ? OP_ANYCHAR_ML : OP_ANYCHAR);
        break;

      case ONIGENC_CTYPE_WORD:
        if (CTYPE_(node)->ascii_mode == 0) {
          op = CTYPE_(node)->not != 0 ? OP_NO_WORD : OP_WORD;
        }
        else {
          op = CTYPE_(node)->not != 0 ? OP_NO_WORD_ASCII : OP_WORD_ASCII;
        }
        r = add_op(reg, op);
        break;

      default:
        return ONIGERR_TYPE_BUG;
        break;
      }
    }
    break;

  case ND_BACKREF:
    {
      BackRefNode* br = BACKREF_(node);

      if (ND_IS_CHECKER(node)) {
#ifdef USE_BACKREF_WITH_LEVEL
        if (ND_IS_NEST_LEVEL(node)) {
          r = add_op(reg, OP_BACKREF_CHECK_WITH_LEVEL);
          if (r != 0) return r;
          COP(reg)->backref_general.nest_level = br->nest_level;
        }
        else
#endif
          {
            r = add_op(reg, OP_BACKREF_CHECK);
            if (r != 0) return r;
          }
        goto add_bacref_mems;
      }
      else {
#ifdef USE_BACKREF_WITH_LEVEL
        if (ND_IS_NEST_LEVEL(node)) {
          if (ND_IS_IGNORECASE(node))
            r = add_op(reg, OP_BACKREF_WITH_LEVEL_IC);
          else
            r = add_op(reg, OP_BACKREF_WITH_LEVEL);

          if (r != 0) return r;
          COP(reg)->backref_general.nest_level = br->nest_level;
          goto add_bacref_mems;
        }
        else
#endif
        if (br->back_num == 1) {
          n = br->back_static[0];
          if (ND_IS_IGNORECASE(node)) {
            r = add_op(reg, OP_BACKREF_N_IC);
            if (r != 0) return r;
            COP(reg)->backref_n.n1 = n;
          }
          else {
            switch (n) {
            case 1:  r = add_op(reg, OP_BACKREF1); break;
            case 2:  r = add_op(reg, OP_BACKREF2); break;
            default:
              r = add_op(reg, OP_BACKREF_N);
              if (r != 0) return r;
              COP(reg)->backref_n.n1 = n;
              break;
            }
          }
        }
        else {
          int num;
          int* p;

          r = add_op(reg, ND_IS_IGNORECASE(node) ?
                     OP_BACKREF_MULTI_IC : OP_BACKREF_MULTI);
          if (r != 0) return r;

        add_bacref_mems:
          num = br->back_num;
          COP(reg)->backref_general.num = num;
          if (num == 1) {
            COP(reg)->backref_general.n1 = br->back_static[0];
          }
          else {
            int i, j;
            MemNumType* ns;

            ns = xmalloc(sizeof(MemNumType) * num);
            CHECK_NULL_RETURN_MEMERR(ns);
            COP(reg)->backref_general.ns = ns;
            p = BACKREFS_P(br);
            for (i = num - 1, j = 0; i >= 0; i--, j++) {
              ns[j] = p[i];
            }
          }
        }
      }
    }
    break;

#ifdef USE_CALL
  case ND_CALL:
    r = compile_call(CALL_(node), reg, env);
    break;
#endif

  case ND_QUANT:
    r = compile_quantifier_node(QUANT_(node), reg, env);
    break;

  case ND_BAG:
    r = compile_bag_node(BAG_(node), reg, env);
    break;

  case ND_ANCHOR:
    r = compile_anchor_node(ANCHOR_(node), reg, env);
    break;

  case ND_GIMMICK:
    r = compile_gimmick_node(GIMMICK_(node), reg);
    break;

  default:
#ifdef ONIG_DEBUG
    fprintf(DBGFP, "compile_tree: undefined node type %d\n", ND_TYPE(node));
#endif
    break;
  }

  return r;
}

static int
make_named_capture_number_map(Node** plink, GroupNumMap* map, int* counter)
{
  int r;
  Node* node = *plink;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      r = make_named_capture_number_map(&(ND_CAR(node)), map, counter);
    } while (r >= 0 && IS_NOT_NULL(node = ND_CDR(node)));
    if (r < 0) return r;
    break;

  case ND_QUANT:
    {
      Node** ptarget = &(ND_BODY(node));
      r = make_named_capture_number_map(ptarget, map, counter);
      if (r < 0) return r;
      if (r == 1 && ND_TYPE(*ptarget) == ND_QUANT) {
        return onig_reduce_nested_quantifier(node);
      }
    }
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);
      if (en->type == BAG_MEMORY) {
        if (ND_IS_NAMED_GROUP(node)) {
          (*counter)++;
          map[en->m.regnum].new_val = *counter;
          en->m.regnum = *counter;
          r = make_named_capture_number_map(&(ND_BODY(node)), map, counter);
          if (r < 0) return r;
        }
        else {
          *plink = ND_BODY(node);
          ND_BODY(node) = NULL_NODE;
          onig_node_free(node);
          r = make_named_capture_number_map(plink, map, counter);
          if (r < 0) return r;
          return 1;
        }
      }
      else if (en->type == BAG_IF_ELSE) {
        r = make_named_capture_number_map(&(ND_BAG_BODY(en)), map, counter);
        if (r < 0) return r;
        if (IS_NOT_NULL(en->te.Then)) {
          r = make_named_capture_number_map(&(en->te.Then), map, counter);
          if (r < 0) return r;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r = make_named_capture_number_map(&(en->te.Else), map, counter);
          if (r < 0) return r;
        }
      }
      else {
        r = make_named_capture_number_map(&(ND_BODY(node)), map, counter);
        if (r < 0) return r;
      }
    }
    break;

  case ND_ANCHOR:
    if (IS_NOT_NULL(ND_BODY(node))) {
      r = make_named_capture_number_map(&(ND_BODY(node)), map, counter);
      if (r < 0) return r;
    }
    break;

  default:
    break;
  }

  return 0;
}

static int
renumber_backref_node(Node* node, GroupNumMap* map)
{
  int i, pos, n, old_num;
  int *backs;
  BackRefNode* bn = BACKREF_(node);

  if (! ND_IS_BY_NAME(node))
    return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;

  old_num = bn->back_num;
  if (IS_NULL(bn->back_dynamic))
    backs = bn->back_static;
  else
    backs = bn->back_dynamic;

  for (i = 0, pos = 0; i < old_num; i++) {
    n = map[backs[i]].new_val;
    if (n > 0) {
      backs[pos] = n;
      pos++;
    }
  }

  bn->back_num = pos;
  return 0;
}

static int
renumber_backref_traverse(Node* node, GroupNumMap* map)
{
  int r = 0;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      r = renumber_backref_traverse(ND_CAR(node), map);
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_QUANT:
    r = renumber_backref_traverse(ND_BODY(node), map);
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      r = renumber_backref_traverse(ND_BODY(node), map);
      if (r != 0) return r;

      if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then)) {
          r = renumber_backref_traverse(en->te.Then, map);
          if (r != 0) return r;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r = renumber_backref_traverse(en->te.Else, map);
          if (r != 0) return r;
        }
      }
    }
    break;

  case ND_BACKREF:
    r = renumber_backref_node(node, map);
    break;

  case ND_ANCHOR:
    if (IS_NOT_NULL(ND_BODY(node)))
      r = renumber_backref_traverse(ND_BODY(node), map);
    break;

  default:
    break;
  }

  return r;
}

static int
numbered_ref_check(Node* node)
{
  int r = 0;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      r = numbered_ref_check(ND_CAR(node));
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ANCHOR:
    if (IS_NULL(ND_BODY(node)))
      break;
    /* fall */
  case ND_QUANT:
    r = numbered_ref_check(ND_BODY(node));
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      r = numbered_ref_check(ND_BODY(node));
      if (r != 0) return r;

      if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then)) {
          r = numbered_ref_check(en->te.Then);
          if (r != 0) return r;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r = numbered_ref_check(en->te.Else);
          if (r != 0) return r;
        }
      }
    }

    break;

  case ND_BACKREF:
    if (! ND_IS_BY_NAME(node))
      return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
    break;

  default:
    break;
  }

  return r;
}

static int
disable_noname_group_capture(Node** root, regex_t* reg, ParseEnv* env)
{
  int r, i, pos, counter;
  MemStatusType loc;
  GroupNumMap* map;

  map = (GroupNumMap* )xalloca(sizeof(GroupNumMap) * (env->num_mem + 1));
  CHECK_NULL_RETURN_MEMERR(map);
  for (i = 1; i <= env->num_mem; i++) {
    map[i].new_val = 0;
  }
  counter = 0;
  r = make_named_capture_number_map(root, map, &counter);
  if (r < 0) return r;

  r = renumber_backref_traverse(*root, map);
  if (r != 0) return r;

  for (i = 1, pos = 1; i <= env->num_mem; i++) {
    if (map[i].new_val > 0) {
      PARSEENV_MEMENV(env)[pos] = PARSEENV_MEMENV(env)[i];
      pos++;
    }
  }

  loc = env->cap_history;
  MEM_STATUS_CLEAR(env->cap_history);
  for (i = 1; i <= ONIG_MAX_CAPTURE_HISTORY_GROUP; i++) {
    if (MEM_STATUS_AT(loc, i)) {
      MEM_STATUS_ON_SIMPLE(env->cap_history, map[i].new_val);
    }
  }

  env->num_mem = env->num_named;
  reg->num_mem = env->num_named;

  return onig_renumber_name_table(reg, map);
}

#ifdef USE_CALL
static int
fix_unset_addr_list(UnsetAddrList* uslist, regex_t* reg)
{
  int i, offset;
  BagNode* en;
  AbsAddrType addr;
  AbsAddrType* paddr;

  for (i = 0; i < uslist->num; i++) {
    if (! ND_IS_FIXED_ADDR(uslist->us[i].target)) {
      if (ND_IS_CALLED(uslist->us[i].target))
        return ONIGERR_PARSER_BUG;
      else {
        /* CASE: called node doesn't have called address.
           ex. /((|a\g<1>)(.){0}){0}\g<3>/
           group-1 doesn't called, but compiled into bytecodes,
           because group-3 is referred from outside.
        */
        continue;
      }
    }

    en = BAG_(uslist->us[i].target);
    addr   = en->m.called_addr;
    offset = uslist->us[i].offset;

    paddr = (AbsAddrType* )((char* )reg->ops + offset);
    *paddr = addr;
  }
  return 0;
}
#endif

/* x is not included y ==>  1 : 0 */
static int
is_exclusive(Node* x, Node* y, regex_t* reg)
{
  int i, len;
  OnigCodePoint code;
  UChar *p;
  NodeType ytype;

 retry:
  ytype = ND_TYPE(y);
  switch (ND_TYPE(x)) {
  case ND_CTYPE:
    {
      if (CTYPE_(x)->ctype == CTYPE_ANYCHAR ||
          CTYPE_(y)->ctype == CTYPE_ANYCHAR)
        break;

      switch (ytype) {
      case ND_CTYPE:
        if (CTYPE_(y)->ctype == CTYPE_(x)->ctype &&
            CTYPE_(y)->not   != CTYPE_(x)->not &&
            CTYPE_(y)->ascii_mode == CTYPE_(x)->ascii_mode)
          return 1;
        else
          return 0;
        break;

      case ND_CCLASS:
      swap:
        {
          Node* tmp;
          tmp = x; x = y; y = tmp;
          goto retry;
        }
        break;

      case ND_STRING:
        goto swap;
        break;

      default:
        break;
      }
    }
    break;

  case ND_CCLASS:
    {
      int range;
      CClassNode* xc = CCLASS_(x);

      switch (ytype) {
      case ND_CTYPE:
        switch (CTYPE_(y)->ctype) {
        case CTYPE_ANYCHAR:
          return 0;
          break;

        case ONIGENC_CTYPE_WORD:
          if (CTYPE_(y)->not == 0) {
            if (IS_NULL(xc->mbuf) && !IS_NCCLASS_NOT(xc)) {
              range = CTYPE_(y)->ascii_mode != 0 ? 128 : SINGLE_BYTE_SIZE;
              for (i = 0; i < range; i++) {
                if (BITSET_AT(xc->bs, i)) {
                  if (ONIGENC_IS_CODE_WORD(reg->enc, i)) return 0;
                }
              }
              return 1;
            }
            return 0;
          }
          else {
            if (IS_NOT_NULL(xc->mbuf)) return 0;
            if (IS_NCCLASS_NOT(xc)) return 0;

            range = CTYPE_(y)->ascii_mode != 0 ? 128 : SINGLE_BYTE_SIZE;
            for (i = 0; i < range; i++) {
              if (! ONIGENC_IS_CODE_WORD(reg->enc, i)) {
                if (BITSET_AT(xc->bs, i))
                  return 0;
              }
            }
            for (i = range; i < SINGLE_BYTE_SIZE; i++) {
              if (BITSET_AT(xc->bs, i)) return 0;
            }
            return 1;
          }
          break;

        default:
          break;
        }
        break;

      case ND_CCLASS:
        {
          int v;
          CClassNode* yc = CCLASS_(y);

          for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
            v = BITSET_AT(xc->bs, i);
            if ((v != 0 && !IS_NCCLASS_NOT(xc)) || (v == 0 && IS_NCCLASS_NOT(xc))) {
              v = BITSET_AT(yc->bs, i);
              if ((v != 0 && !IS_NCCLASS_NOT(yc)) ||
                  (v == 0 && IS_NCCLASS_NOT(yc)))
                return 0;
            }
          }
          if ((IS_NULL(xc->mbuf) && !IS_NCCLASS_NOT(xc)) ||
              (IS_NULL(yc->mbuf) && !IS_NCCLASS_NOT(yc)))
            return 1;
          return 0;
        }
        break;

      case ND_STRING:
        goto swap;
        break;

      default:
        break;
      }
    }
    break;

  case ND_STRING:
    {
      StrNode* xs = STR_(x);

      if (ND_STRING_LEN(x) == 0)
        break;

      switch (ytype) {
      case ND_CTYPE:
        switch (CTYPE_(y)->ctype) {
        case CTYPE_ANYCHAR:
          break;

        case ONIGENC_CTYPE_WORD:
          if (CTYPE_(y)->ascii_mode == 0) {
            if (ONIGENC_IS_MBC_WORD(reg->enc, xs->s, xs->end))
              return CTYPE_(y)->not;
            else
              return !(CTYPE_(y)->not);
          }
          else {
            if (ONIGENC_IS_MBC_WORD_ASCII(reg->enc, xs->s, xs->end))
              return CTYPE_(y)->not;
            else
              return !(CTYPE_(y)->not);
          }
          break;
        default:
          break;
        }
        break;

      case ND_CCLASS:
        {
          CClassNode* cc = CCLASS_(y);

          code = ONIGENC_MBC_TO_CODE(reg->enc, xs->s,
                                     xs->s + ONIGENC_MBC_MAXLEN(reg->enc));
          return onig_is_code_in_cc(reg->enc, code, cc) == 0;
        }
        break;

      case ND_STRING:
        {
          UChar *q;
          StrNode* ys = STR_(y);

          len = ND_STRING_LEN(x);
          if (len > ND_STRING_LEN(y)) len = ND_STRING_LEN(y);

          for (i = 0, p = ys->s, q = xs->s; i < len; i++, p++, q++) {
            if (*p != *q) return 1;
          }
        }
        break;

      default:
        break;
      }
    }
    break;

  default:
    break;
  }

  return 0;
}

static Node*
get_tree_head_literal(Node* node, int exact, regex_t* reg)
{
  Node* n = NULL_NODE;

  switch (ND_TYPE(node)) {
  case ND_BACKREF:
  case ND_ALT:
#ifdef USE_CALL
  case ND_CALL:
#endif
    break;

  case ND_CTYPE:
    if (CTYPE_(node)->ctype == CTYPE_ANYCHAR)
      break;
    /* fall */
  case ND_CCLASS:
    if (exact == 0) {
      n = node;
    }
    break;

  case ND_LIST:
    n = get_tree_head_literal(ND_CAR(node), exact, reg);
    break;

  case ND_STRING:
    {
      StrNode* sn = STR_(node);

      if (sn->end <= sn->s)
        break;

      if (exact == 0 || !ND_IS_REAL_IGNORECASE(node)) {
        n = node;
      }
    }
    break;

  case ND_QUANT:
    {
      QuantNode* qn = QUANT_(node);
      if (qn->lower > 0) {
        if (IS_NOT_NULL(qn->head_exact))
          n = qn->head_exact;
        else
          n = get_tree_head_literal(ND_BODY(node), exact, reg);
      }
    }
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);
      switch (en->type) {
      case BAG_OPTION:
      case BAG_MEMORY:
      case BAG_STOP_BACKTRACK:
        n = get_tree_head_literal(ND_BODY(node), exact, reg);
        break;
      default:
        break;
      }
    }
    break;

  case ND_ANCHOR:
    if (ANCHOR_(node)->type == ANCR_PREC_READ)
      n = get_tree_head_literal(ND_BODY(node), exact, reg);
    break;

  case ND_GIMMICK:
  default:
    break;
  }

  return n;
}

enum GetValue {
  GET_VALUE_NONE   = -1,
  GET_VALUE_IGNORE =  0,
  GET_VALUE_FOUND  =  1
};

#define MAX_NEST_LEVEL_GET_TREE_TAIL_LITERAL  16

static int
get_tree_tail_literal(Node* node, Node** rnode, regex_t* reg, int nest_level)
{
  int r;

  nest_level++;
  if (nest_level >= MAX_NEST_LEVEL_GET_TREE_TAIL_LITERAL) {
    return GET_VALUE_NONE;
  }

  switch (ND_TYPE(node)) {
  case ND_LIST:
    if (IS_NULL(ND_CDR(node))) {
      r = get_tree_tail_literal(ND_CAR(node), rnode, reg, nest_level);
    }
    else {
      r = get_tree_tail_literal(ND_CDR(node), rnode, reg, nest_level);
      if (r == GET_VALUE_IGNORE) {
        r = get_tree_tail_literal(ND_CAR(node), rnode, reg, nest_level);
      }
    }
    break;

#ifdef USE_CALL
  case ND_CALL:
    r = get_tree_tail_literal(ND_BODY(node), rnode, reg, nest_level);
    break;
#endif

  case ND_CTYPE:
    if (CTYPE_(node)->ctype == CTYPE_ANYCHAR) {
      r = GET_VALUE_NONE;
      break;
    }
    /* fall */
  case ND_CCLASS:
    *rnode = node;
    r = GET_VALUE_FOUND;
    break;

  case ND_STRING:
    {
      StrNode* sn = STR_(node);

      if (sn->end <= sn->s) {
        r = GET_VALUE_IGNORE;
        break;
      }

      if (ND_IS_REAL_IGNORECASE(node)) {
        r = GET_VALUE_NONE;
        break;
      }

      *rnode = node;
      r = GET_VALUE_FOUND;
    }
    break;

  case ND_QUANT:
    {
      QuantNode* qn = QUANT_(node);
      if (qn->lower != 0) {
        r = get_tree_tail_literal(ND_BODY(node), rnode, reg, nest_level);
      }
      else
        r = GET_VALUE_NONE;
    }
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      if (en->type == BAG_MEMORY) {
        if (ND_IS_MARK1(node))
          r = GET_VALUE_NONE;
        else {
          ND_STATUS_ADD(node, MARK1);
          r = get_tree_tail_literal(ND_BODY(node), rnode, reg, nest_level);
          ND_STATUS_REMOVE(node, MARK1);
        }
      }
      else {
        r = get_tree_tail_literal(ND_BODY(node), rnode, reg, nest_level);
      }
    }
    break;

  case ND_ANCHOR:
  case ND_GIMMICK:
    r = GET_VALUE_IGNORE;
    break;

  case ND_ALT:
  case ND_BACKREF:
  default:
    r = GET_VALUE_NONE;
    break;
  }

  return r;
}

static int
check_called_node_in_look_behind(Node* node, int not)
{
  int r;

  r = 0;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      r = check_called_node_in_look_behind(ND_CAR(node), not);
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_QUANT:
    r = check_called_node_in_look_behind(ND_BODY(node), not);
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      if (en->type == BAG_MEMORY) {
        if (ND_IS_MARK1(node))
          return 0;
        else {
          ND_STATUS_ADD(node, MARK1);
          r = check_called_node_in_look_behind(ND_BODY(node), not);
          ND_STATUS_REMOVE(node, MARK1);
        }
      }
      else {
        r = check_called_node_in_look_behind(ND_BODY(node), not);
        if (r == 0 && en->type == BAG_IF_ELSE) {
          if (IS_NOT_NULL(en->te.Then)) {
            r = check_called_node_in_look_behind(en->te.Then, not);
            if (r != 0) break;
          }
          if (IS_NOT_NULL(en->te.Else)) {
            r = check_called_node_in_look_behind(en->te.Else, not);
          }
        }
      }
    }
    break;

  case ND_ANCHOR:
    if (IS_NOT_NULL(ND_BODY(node)))
      r = check_called_node_in_look_behind(ND_BODY(node), not);
    break;

  case ND_GIMMICK:
    if (ND_IS_ABSENT_WITH_SIDE_EFFECTS(node) != 0)
      return 1;
    break;

  default:
    break;
  }

  return r;
}

/* allowed node types in look-behind */
#define ALLOWED_TYPE_IN_LB \
  ( ND_BIT_LIST | ND_BIT_ALT | ND_BIT_STRING | ND_BIT_CCLASS \
  | ND_BIT_CTYPE | ND_BIT_ANCHOR | ND_BIT_BAG | ND_BIT_QUANT \
  | ND_BIT_CALL | ND_BIT_BACKREF | ND_BIT_GIMMICK)

#define ALLOWED_BAG_IN_LB       ( 1<<BAG_MEMORY | 1<<BAG_OPTION | 1<<BAG_STOP_BACKTRACK | 1<<BAG_IF_ELSE )
#define ALLOWED_BAG_IN_LB_NOT   ( 1<<BAG_OPTION | 1<<BAG_STOP_BACKTRACK | 1<<BAG_IF_ELSE )

#define ALLOWED_ANCHOR_IN_LB \
  ( ANCR_LOOK_BEHIND | ANCR_BEGIN_LINE | ANCR_END_LINE | ANCR_BEGIN_BUF \
  | ANCR_BEGIN_POSITION | ANCR_WORD_BOUNDARY | ANCR_NO_WORD_BOUNDARY \
  | ANCR_WORD_BEGIN | ANCR_WORD_END \
  | ANCR_TEXT_SEGMENT_BOUNDARY | ANCR_NO_TEXT_SEGMENT_BOUNDARY )

#define ALLOWED_ANCHOR_IN_LB_NOT \
  ( ANCR_LOOK_BEHIND | ANCR_LOOK_BEHIND_NOT | ANCR_BEGIN_LINE \
  | ANCR_END_LINE | ANCR_BEGIN_BUF | ANCR_BEGIN_POSITION | ANCR_WORD_BOUNDARY \
  | ANCR_NO_WORD_BOUNDARY | ANCR_WORD_BEGIN | ANCR_WORD_END \
  | ANCR_TEXT_SEGMENT_BOUNDARY | ANCR_NO_TEXT_SEGMENT_BOUNDARY )


static int
check_node_in_look_behind(Node* node, int not, int* used)
{
  static unsigned int
    bag_mask[2] = { ALLOWED_BAG_IN_LB, ALLOWED_BAG_IN_LB_NOT };

  static unsigned int
    anchor_mask[2] = { ALLOWED_ANCHOR_IN_LB, ALLOWED_ANCHOR_IN_LB_NOT };

  NodeType type;
  int r = 0;

  type = ND_TYPE(node);
  if ((ND_TYPE2BIT(type) & ALLOWED_TYPE_IN_LB) == 0)
    return 1;

  switch (type) {
  case ND_LIST:
  case ND_ALT:
    do {
      r = check_node_in_look_behind(ND_CAR(node), not, used);
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_QUANT:
    r = check_node_in_look_behind(ND_BODY(node), not, used);
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);
      if (((1<<en->type) & bag_mask[not]) == 0)
        return 1;

      r = check_node_in_look_behind(ND_BODY(node), not, used);
      if (r != 0) break;

      if (en->type == BAG_MEMORY) {
        if (ND_IS_BACKREF(node) || ND_IS_CALLED(node)
         || ND_IS_REFERENCED(node))
          *used = TRUE;
      }
      else if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then)) {
          r = check_node_in_look_behind(en->te.Then, not, used);
          if (r != 0) break;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r = check_node_in_look_behind(en->te.Else, not, used);
        }
      }
    }
    break;

  case ND_ANCHOR:
    type = ANCHOR_(node)->type;
    if ((type & anchor_mask[not]) == 0)
      return 1;

    if (IS_NOT_NULL(ND_BODY(node)))
      r = check_node_in_look_behind(ND_BODY(node), not, used);
    break;

  case ND_GIMMICK:
    if (ND_IS_ABSENT_WITH_SIDE_EFFECTS(node) != 0)
      return 1;

    {
      GimmickNode* g = GIMMICK_(node);
      if (g->type == GIMMICK_SAVE && g->detail_type == SAVE_KEEP)
        *used = TRUE;
    }
    break;

  case ND_CALL:
    if (ND_IS_RECURSION(node)) {
      /* fix: Issue 38040 in oss-fuzz */
      /* This node should be removed before recursive call check. */
      *used = TRUE;
    }
    else
      r = check_called_node_in_look_behind(ND_BODY(node), not);
    break;

  default:
    break;
  }
  return r;
}

static OnigLen
node_min_byte_len(Node* node, ParseEnv* env)
{
  OnigLen len;
  OnigLen tmin;

  len = 0;
  switch (ND_TYPE(node)) {
  case ND_BACKREF:
    if (! ND_IS_CHECKER(node)) {
      int i;
      int* backs;
      MemEnv* mem_env = PARSEENV_MEMENV(env);
      BackRefNode* br = BACKREF_(node);
      if (ND_IS_RECURSION(node)) break;

      backs = BACKREFS_P(br);
      len = node_min_byte_len(mem_env[backs[0]].mem_node, env);
      for (i = 1; i < br->back_num; i++) {
        tmin = node_min_byte_len(mem_env[backs[i]].mem_node, env);
        if (len > tmin) len = tmin;
      }
    }
    break;

#ifdef USE_CALL
  case ND_CALL:
    {
      Node* t = ND_BODY(node);
      if (ND_IS_FIXED_MIN(t))
        len = BAG_(t)->min_len;
      else
        len = node_min_byte_len(t, env);
    }
    break;
#endif

  case ND_LIST:
    do {
      tmin = node_min_byte_len(ND_CAR(node), env);
      len = distance_add(len, tmin);
    } while (IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ALT:
    {
      Node *x, *y;
      y = node;
      do {
        x = ND_CAR(y);
        tmin = node_min_byte_len(x, env);
        if (y == node) len = tmin;
        else if (len > tmin) len = tmin;
      } while (IS_NOT_NULL(y = ND_CDR(y)));
    }
    break;

  case ND_STRING:
    {
      StrNode* sn = STR_(node);
      len = (int )(sn->end - sn->s);
    }
    break;

  case ND_CTYPE:
  case ND_CCLASS:
    len = ONIGENC_MBC_MINLEN(env->enc);
    break;

  case ND_QUANT:
    {
      QuantNode* qn = QUANT_(node);

      if (qn->lower > 0) {
        len = node_min_byte_len(ND_BODY(node), env);
        len = distance_multiply(len, qn->lower);
      }
    }
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);
      switch (en->type) {
      case BAG_MEMORY:
        if (ND_IS_FIXED_MIN(node))
          len = en->min_len;
        else {
          if (ND_IS_MARK1(node))
            len = 0;  /* recursive */
          else {
            ND_STATUS_ADD(node, MARK1);
            len = node_min_byte_len(ND_BODY(node), env);
            ND_STATUS_REMOVE(node, MARK1);

            en->min_len = len;
            ND_STATUS_ADD(node, FIXED_MIN);
          }
        }
        break;

      case BAG_OPTION:
      case BAG_STOP_BACKTRACK:
        len = node_min_byte_len(ND_BODY(node), env);
        break;
      case BAG_IF_ELSE:
        {
          OnigLen elen;

          len = node_min_byte_len(ND_BODY(node), env);
          if (IS_NOT_NULL(en->te.Then))
            len += node_min_byte_len(en->te.Then, env);
          if (IS_NOT_NULL(en->te.Else))
            elen = node_min_byte_len(en->te.Else, env);
          else elen = 0;

          if (elen < len) len = elen;
        }
        break;
      }
    }
    break;

  case ND_GIMMICK:
    {
      GimmickNode* g = GIMMICK_(node);
      if (g->type == GIMMICK_FAIL) {
        len = INFINITE_LEN;
        break;
      }
    }
    /* fall */
  case ND_ANCHOR:
  default:
    break;
  }

  return len;
}

static int
check_backrefs(Node* node, ParseEnv* env)
{
  int r;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      r = check_backrefs(ND_CAR(node), env);
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ANCHOR:
    if (! ANCHOR_HAS_BODY(ANCHOR_(node))) {
      r = 0;
      break;
    }
    /* fall */
  case ND_QUANT:
    r = check_backrefs(ND_BODY(node), env);
    break;

  case ND_BAG:
    r = check_backrefs(ND_BODY(node), env);
    {
      BagNode* en = BAG_(node);

      if (en->type == BAG_IF_ELSE) {
        if (r != 0) return r;
        if (IS_NOT_NULL(en->te.Then)) {
          r = check_backrefs(en->te.Then, env);
          if (r != 0) return r;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r = check_backrefs(en->te.Else, env);
        }
      }
    }
    break;

  case ND_BACKREF:
    {
      int i;
      BackRefNode* br = BACKREF_(node);
      int* backs = BACKREFS_P(br);
      MemEnv* mem_env = PARSEENV_MEMENV(env);

      for (i = 0; i < br->back_num; i++) {
        if (backs[i] > env->num_mem)
          return ONIGERR_INVALID_BACKREF;

        ND_STATUS_ADD(mem_env[backs[i]].mem_node, BACKREF);
      }
      r = 0;
    }
    break;

  default:
    r = 0;
    break;
  }

  return r;
}

static int
set_empty_repeat_node_trav(Node* node, Node* empty, ParseEnv* env)
{
  int r;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      r = set_empty_repeat_node_trav(ND_CAR(node), empty, env);
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ANCHOR:
    {
      AnchorNode* an = ANCHOR_(node);

      if (! ANCHOR_HAS_BODY(an)) {
        r = 0;
        break;
      }

      switch (an->type) {
      case ANCR_PREC_READ:
      case ANCR_LOOK_BEHIND:
        empty = NULL_NODE;
        break;
      default:
        break;
      }
      r = set_empty_repeat_node_trav(ND_BODY(node), empty, env);
    }
    break;

  case ND_QUANT:
    {
      QuantNode* qn = QUANT_(node);

      if (qn->emptiness != BODY_IS_NOT_EMPTY) empty = node;
      r = set_empty_repeat_node_trav(ND_BODY(node), empty, env);
    }
    break;

  case ND_BAG:
    if (IS_NOT_NULL(ND_BODY(node))) {
      r = set_empty_repeat_node_trav(ND_BODY(node), empty, env);
      if (r != 0) return r;
    }
    {
      BagNode* en = BAG_(node);

      r = 0;
      if (en->type == BAG_MEMORY) {
        if (ND_IS_BACKREF(node)) {
          if (IS_NOT_NULL(empty))
            PARSEENV_MEMENV(env)[en->m.regnum].empty_repeat_node = empty;
        }
      }
      else if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then)) {
          r = set_empty_repeat_node_trav(en->te.Then, empty, env);
          if (r != 0) return r;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r = set_empty_repeat_node_trav(en->te.Else, empty, env);
        }
      }
    }
    break;

  default:
    r = 0;
    break;
  }

  return r;
}

static int
is_ancestor_node(Node* node, Node* me)
{
  Node* parent;

  while ((parent = ND_PARENT(me)) != NULL_NODE) {
    if (parent == node) return 1;
    me = parent;
  }
  return 0;
}

static void
set_empty_status_check_trav(Node* node, ParseEnv* env)
{
  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      set_empty_status_check_trav(ND_CAR(node), env);
    } while (IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ANCHOR:
    {
      AnchorNode* an = ANCHOR_(node);

      if (! ANCHOR_HAS_BODY(an)) break;
      set_empty_status_check_trav(ND_BODY(node), env);
    }
    break;

  case ND_QUANT:
    set_empty_status_check_trav(ND_BODY(node), env);
    break;

  case ND_BAG:
    if (IS_NOT_NULL(ND_BODY(node)))
      set_empty_status_check_trav(ND_BODY(node), env);
    {
      BagNode* en = BAG_(node);

      if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then)) {
          set_empty_status_check_trav(en->te.Then, env);
        }
        if (IS_NOT_NULL(en->te.Else)) {
          set_empty_status_check_trav(en->te.Else, env);
        }
      }
    }
    break;

  case ND_BACKREF:
    {
      int i;
      int* backs;
      MemEnv* mem_env = PARSEENV_MEMENV(env);
      BackRefNode* br = BACKREF_(node);
      backs = BACKREFS_P(br);
      for (i = 0; i < br->back_num; i++) {
        Node* ernode = mem_env[backs[i]].empty_repeat_node;
        if (IS_NOT_NULL(ernode)) {
          if (! is_ancestor_node(ernode, node)) {
            MEM_STATUS_LIMIT_ON(QUANT_(ernode)->empty_status_mem, backs[i]);
            ND_STATUS_ADD(ernode, EMPTY_STATUS_CHECK);
            ND_STATUS_ADD(mem_env[backs[i]].mem_node, EMPTY_STATUS_CHECK);
          }
        }
      }
    }
    break;

  default:
    break;
  }
}

static void
set_parent_node_trav(Node* node, Node* parent)
{
  ND_PARENT(node) = parent;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      set_parent_node_trav(ND_CAR(node), node);
    } while (IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ANCHOR:
    if (! ANCHOR_HAS_BODY(ANCHOR_(node))) break;
    set_parent_node_trav(ND_BODY(node), node);
    break;

  case ND_QUANT:
    set_parent_node_trav(ND_BODY(node), node);
    break;

  case ND_BAG:
    if (IS_NOT_NULL(ND_BODY(node)))
      set_parent_node_trav(ND_BODY(node), node);
    {
      BagNode* en = BAG_(node);

      if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then))
          set_parent_node_trav(en->te.Then, node);
        if (IS_NOT_NULL(en->te.Else)) {
          set_parent_node_trav(en->te.Else, node);
        }
      }
    }
    break;

  default:
    break;
  }
}


#ifdef USE_CALL

#define RECURSION_EXIST        (1<<0)
#define RECURSION_MUST         (1<<1)
#define RECURSION_INFINITE     (1<<2)

static int
infinite_recursive_call_check(Node* node, ParseEnv* env, int head)
{
  int ret;
  int r = 0;

  switch (ND_TYPE(node)) {
  case ND_LIST:
    {
      Node *x;
      OnigLen min;

      x = node;
      do {
        ret = infinite_recursive_call_check(ND_CAR(x), env, head);
        if (ret < 0 || (ret & RECURSION_INFINITE) != 0) return ret;
        r |= ret;
        if (head != 0) {
          min = node_min_byte_len(ND_CAR(x), env);
          if (min != 0) head = 0;
        }
      } while (IS_NOT_NULL(x = ND_CDR(x)));
    }
    break;

  case ND_ALT:
    {
      int must;

      must = RECURSION_MUST;
      do {
        ret = infinite_recursive_call_check(ND_CAR(node), env, head);
        if (ret < 0 || (ret & RECURSION_INFINITE) != 0) return ret;

        r    |= (ret & RECURSION_EXIST);
        must &= ret;
      } while (IS_NOT_NULL(node = ND_CDR(node)));
      r |= must;
    }
    break;

  case ND_QUANT:
    if (QUANT_(node)->upper == 0) break;

    r = infinite_recursive_call_check(ND_BODY(node), env, head);
    if (r < 0) return r;
    if ((r & RECURSION_MUST) != 0) {
      if (QUANT_(node)->lower == 0)
        r &= ~RECURSION_MUST;
    }
    break;

  case ND_ANCHOR:
    if (! ANCHOR_HAS_BODY(ANCHOR_(node)))
      break;
    /* fall */
  case ND_CALL:
    r = infinite_recursive_call_check(ND_BODY(node), env, head);
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      if (en->type == BAG_MEMORY) {
        if (ND_IS_MARK2(node))
          return 0;
        else if (ND_IS_MARK1(node))
          return (head == 0 ? RECURSION_EXIST | RECURSION_MUST
                  : RECURSION_EXIST | RECURSION_MUST | RECURSION_INFINITE);
        else {
          ND_STATUS_ADD(node, MARK2);
          r = infinite_recursive_call_check(ND_BODY(node), env, head);
          ND_STATUS_REMOVE(node, MARK2);
        }
      }
      else if (en->type == BAG_IF_ELSE) {
        int eret;

        ret = infinite_recursive_call_check(ND_BODY(node), env, head);
        if (ret < 0 || (ret & RECURSION_INFINITE) != 0) return ret;
        r |= ret;
        if (IS_NOT_NULL(en->te.Then)) {
          OnigLen min;
          if (head != 0) {
            min = node_min_byte_len(ND_BODY(node), env);
          }
          else min = 0;

          ret = infinite_recursive_call_check(en->te.Then, env, min != 0 ? 0:head);
          if (ret < 0 || (ret & RECURSION_INFINITE) != 0) return ret;
          r |= ret;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          eret = infinite_recursive_call_check(en->te.Else, env, head);
          if (eret < 0 || (eret & RECURSION_INFINITE) != 0) return eret;
          r |= (eret & RECURSION_EXIST);
          if ((eret & RECURSION_MUST) == 0)
            r &= ~RECURSION_MUST;
        }
        else {
          r &= ~RECURSION_MUST;
        }
      }
      else {
        r = infinite_recursive_call_check(ND_BODY(node), env, head);
      }
    }
    break;

  default:
    break;
  }

  return r;
}

static int
infinite_recursive_call_check_trav(Node* node, ParseEnv* env)
{
  int r;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    do {
      r = infinite_recursive_call_check_trav(ND_CAR(node), env);
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ANCHOR:
    if (! ANCHOR_HAS_BODY(ANCHOR_(node))) {
      r = 0;
      break;
    }
    /* fall */
  case ND_QUANT:
    r = infinite_recursive_call_check_trav(ND_BODY(node), env);
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      if (en->type == BAG_MEMORY) {
        if (ND_IS_RECURSION(node) && ND_IS_CALLED(node)) {
          int ret;

          ND_STATUS_ADD(node, MARK1);

          ret = infinite_recursive_call_check(ND_BODY(node), env, 1);
          if (ret < 0) return ret;
          else if ((ret & (RECURSION_MUST | RECURSION_INFINITE)) != 0)
            return ONIGERR_NEVER_ENDING_RECURSION;

          ND_STATUS_REMOVE(node, MARK1);
        }
      }
      else if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then)) {
          r = infinite_recursive_call_check_trav(en->te.Then, env);
          if (r != 0) return r;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r = infinite_recursive_call_check_trav(en->te.Else, env);
          if (r != 0) return r;
        }
      }
    }

    r = infinite_recursive_call_check_trav(ND_BODY(node), env);
    break;

  default:
    r = 0;
    break;
  }

  return r;
}

static int
recursive_call_check(Node* node)
{
  int r;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    r = 0;
    do {
      r |= recursive_call_check(ND_CAR(node));
    } while (IS_NOT_NULL(node = ND_CDR(node)));
    break;

  case ND_ANCHOR:
    if (! ANCHOR_HAS_BODY(ANCHOR_(node))) {
      r = 0;
      break;
    }
    /* fall */
  case ND_QUANT:
    r = recursive_call_check(ND_BODY(node));
    break;

  case ND_CALL:
    r = recursive_call_check(ND_BODY(node));
    if (r != 0) {
      if (ND_IS_MARK1(ND_BODY(node)))
        ND_STATUS_ADD(node, RECURSION);
    }
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      if (en->type == BAG_MEMORY) {
        if (ND_IS_MARK2(node))
          return 0;
        else if (ND_IS_MARK1(node))
          return 1; /* recursion */
        else {
          ND_STATUS_ADD(node, MARK2);
          r = recursive_call_check(ND_BODY(node));
          ND_STATUS_REMOVE(node, MARK2);
        }
      }
      else if (en->type == BAG_IF_ELSE) {
        r = 0;
        if (IS_NOT_NULL(en->te.Then)) {
          r |= recursive_call_check(en->te.Then);
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r |= recursive_call_check(en->te.Else);
        }
        r |= recursive_call_check(ND_BODY(node));
      }
      else {
        r = recursive_call_check(ND_BODY(node));
      }
    }
    break;

  default:
    r = 0;
    break;
  }

  return r;
}

#define IN_RECURSION         (1<<0)
#define FOUND_CALLED_NODE    1

static int
recursive_call_check_trav(Node* node, ParseEnv* env, int state)
{
  int r = 0;

  switch (ND_TYPE(node)) {
  case ND_LIST:
  case ND_ALT:
    {
      int ret;
      do {
        ret = recursive_call_check_trav(ND_CAR(node), env, state);
        if (ret == FOUND_CALLED_NODE) r = FOUND_CALLED_NODE;
        else if (ret < 0) return ret;
      } while (IS_NOT_NULL(node = ND_CDR(node)));
    }
    break;

  case ND_QUANT:
    r = recursive_call_check_trav(ND_BODY(node), env, state);
    if (QUANT_(node)->upper == 0) {
      if (r == FOUND_CALLED_NODE)
        QUANT_(node)->include_referred = 1;
    }
    break;

  case ND_ANCHOR:
    {
      AnchorNode* an = ANCHOR_(node);
      if (ANCHOR_HAS_BODY(an))
        r = recursive_call_check_trav(ND_ANCHOR_BODY(an), env, state);
    }
    break;

  case ND_BAG:
    {
      int ret;
      int state1;
      BagNode* en = BAG_(node);

      if (en->type == BAG_MEMORY) {
        if (ND_IS_CALLED(node)) {
          r = FOUND_CALLED_NODE;
          goto check_recursion;
        }
        else if ((state & IN_RECURSION) != 0) {
        check_recursion:
          if (! ND_IS_RECURSION(node)) {
            ND_STATUS_ADD(node, MARK1);
            ret = recursive_call_check(ND_BODY(node));
            if (ret != 0) {
              ND_STATUS_ADD(node, RECURSION);
              MEM_STATUS_ON(env->backtrack_mem, en->m.regnum);
            }
            ND_STATUS_REMOVE(node, MARK1);
          }
        }
      }

      state1 = state;
      if (ND_IS_RECURSION(node))
        state1 |= IN_RECURSION;

      ret = recursive_call_check_trav(ND_BODY(node), env, state1);
      if (ret == FOUND_CALLED_NODE)
        r = FOUND_CALLED_NODE;

      if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then)) {
          ret = recursive_call_check_trav(en->te.Then, env, state1);
          if (ret == FOUND_CALLED_NODE)
            r = FOUND_CALLED_NODE;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          ret = recursive_call_check_trav(en->te.Else, env, state1);
          if (ret == FOUND_CALLED_NODE)
            r = FOUND_CALLED_NODE;
        }
      }
    }
    break;

  default:
    break;
  }

  return r;
}

#endif

static void
remove_from_list(Node* prev, Node* a)
{
  if (ND_CDR(prev) != a) return ;

  ND_CDR(prev) = ND_CDR(a);
  ND_CDR(a) = NULL_NODE;
}

static int
reduce_string_list(Node* node, OnigEncoding enc)
{
  int r = 0;

  switch (ND_TYPE(node)) {
  case ND_LIST:
    {
      Node* prev;
      Node* curr;
      Node* prev_node;
      Node* next_node;

      prev = NULL_NODE;
      do {
        next_node = ND_CDR(node);
        curr = ND_CAR(node);
        if (ND_TYPE(curr) == ND_STRING) {
          if (IS_NULL(prev)
              || STR_(curr)->flag  != STR_(prev)->flag
              || ND_STATUS(curr) != ND_STATUS(prev)) {
            prev = curr;
            prev_node = node;
          }
          else {
            r = node_str_node_cat(prev, curr);
            if (r != 0) return r;
            remove_from_list(prev_node, node);
            onig_node_free(node);
          }
        }
        else {
          if (IS_NOT_NULL(prev)) {
#ifdef USE_CHECK_VALIDITY_OF_STRING_IN_TREE
            StrNode* sn = STR_(prev);
            if (! ONIGENC_IS_VALID_MBC_STRING(enc, sn->s, sn->end))
              return ONIGERR_INVALID_WIDE_CHAR_VALUE;
#endif
            prev = NULL_NODE;
          }
          r = reduce_string_list(curr, enc);
          if (r != 0) return r;
          prev_node = node;
        }

        node = next_node;
      } while (r == 0 && IS_NOT_NULL(node));

#ifdef USE_CHECK_VALIDITY_OF_STRING_IN_TREE
      if (IS_NOT_NULL(prev)) {
        StrNode* sn = STR_(prev);
        if (! ONIGENC_IS_VALID_MBC_STRING(enc, sn->s, sn->end))
          return ONIGERR_INVALID_WIDE_CHAR_VALUE;
      }
#endif
    }
    break;

  case ND_ALT:
    do {
      r = reduce_string_list(ND_CAR(node), enc);
    } while (r == 0 && IS_NOT_NULL(node = ND_CDR(node)));
    break;

#ifdef USE_CHECK_VALIDITY_OF_STRING_IN_TREE
  case ND_STRING:
    {
      StrNode* sn = STR_(node);
      if (! ONIGENC_IS_VALID_MBC_STRING(enc, sn->s, sn->end))
        return ONIGERR_INVALID_WIDE_CHAR_VALUE;
    }
    break;
#endif

  case ND_ANCHOR:
    if (IS_NULL(ND_BODY(node)))
      break;
    /* fall */
  case ND_QUANT:
    r = reduce_string_list(ND_BODY(node), enc);
    break;

  case ND_BAG:
    {
      BagNode* en = BAG_(node);

      r = reduce_string_list(ND_BODY(node), enc);
      if (r != 0) return r;

      if (en->type == BAG_IF_ELSE) {
        if (IS_NOT_NULL(en->te.Then)) {
          r = reduce_string_list(en->te.Then, enc);
          if (r != 0) return r;
        }
        if (IS_NOT_NULL(en->te.Else)) {
          r = reduce_string_list(en->te.Else, enc);
          if (r != 0) return r;
        }
      }
    }
    break;

  default:
    break;
  }

  return r;
}


#define IN_ALT          (1<<0)
#define IN_NOT          (1<<1)
#define IN_REAL_REPEAT  (1<<2)
#define IN_VAR_REPEAT   (1<<3)
#define IN_ZERO_REPEAT  (1<<4)
#define IN_MULTI_ENTRY  (1<<5)
#define IN_PREC_READ    (1<<6)
#define IN_LOOK_BEHIND  (1<<7)
#define IN_PEEK         (1<<8)

/* divide different length alternatives in look-behind.
  (?<=A|B) ==> (?<=A)|(?<=B)
  (?<!A|B) ==> (?<!A)(?<!B)
*/
static int
divide_look_behind_alternatives(Node* node)
{
  int r;
  int anc_type;
  Node *head, *np, *insert_node;
  AnchorNode* an;

  an = ANCHOR_(node);
  anc_type = an->type;

  head = ND_ANCHOR_BODY(an);
  np = ND_CAR(head);
  node_swap(node, head);
  ND_CAR(node) = head;
  ND_BODY(head) = np;

  np = node;
  while (IS_NOT_NULL(np = ND_CDR(np))) {
    r = onig_node_copy(&insert_node, head);
    if (r != 0) return r;
    CHECK_NULL_RETURN_MEMERR(insert_node);
    ND_BODY(insert_node) = ND_CAR(np);
    ND_CAR(np) = insert_node;
  }

  if (anc_type == ANCR_LOOK_BEHIND_NOT

Coverage Report

Created: 2023-11-19 06:57