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

  regcomp.c -  Oniguruma (regular expression library)

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

/*-

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

 * All rights reserved.

 *

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

 * modification, are permitted provided that the following conditions

 * are met:

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

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

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

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

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

 *

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

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

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

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

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

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

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

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

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

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

 * SUCH DAMAGE.

 */

#include "regparse.h"

OnigCaseFoldType OnigDefaultCaseFoldFlag = ONIGENC_CASE_FOLD_MIN;

#if 0

typedef struct {

  int  n;

  int  alloc;

  int* v;

} int_stack;

static int

make_int_stack(int_stack** rs, int init_size)

{

  int_stack* s;

  int* v;

  *rs = 0;

  s = xmalloc(sizeof(*s));

  if (IS_NULL(s)) return ONIGERR_MEMORY;

  v = (int* )xmalloc(sizeof(int) * init_size);

  if (IS_NULL(v)) {

    xfree(s);

    return ONIGERR_MEMORY;

  }

  s->n = 0;

  s->alloc = init_size;

  s->v = v;

  *rs = s;

  return ONIG_NORMAL;

}

static void

free_int_stack(int_stack* s)

{

  if (IS_NOT_NULL(s)) {

    if (IS_NOT_NULL(s->v))

      xfree(s->v);

    xfree(s);

  }

}

static int

int_stack_push(int_stack* s, int v)

{

  if (s->n >= s->alloc) {

    int new_size = s->alloc * 2;

    int* nv = (int* )xrealloc(s->v, sizeof(int) * new_size);

    if (IS_NULL(nv)) return ONIGERR_MEMORY;

    s->alloc = new_size;

    s->v = nv;

  }

  s->v[s->n] = v;

  s->n++;

  return ONIG_NORMAL;

}

static int

int_stack_pop(int_stack* s)

{

  int v;

#ifdef ONIG_DEBUG

  if (s->n <= 0) {

    fprintf(stderr, "int_stack_pop: fail empty. %p\n", s);

    return 0;

  }

#endif

  v = s->v[s->n];

  s->n--;

  return v;

}

#endif

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

int_multiply_cmp(int x, int y, int v)

{

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

  if (x < INT_MAX / y) {

    int xy = x * y;

    if (xy > v) return 1;

    else {

      if (xy == v) return 0;

      else return -1;

    }

  }

  else

    return 1;

}

#ifndef PLATFORM_UNALIGNED_WORD_ACCESS

static unsigned char PadBuf[WORD_ALIGNMENT_SIZE];

#endif

static void

swap_node(Node* a, Node* b)

{

  Node c;

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

  if (NODE_TYPE(a) == NODE_STRING) {

    StrNode* sn = STR_(a);

    if (sn->capa == 0) {

      int len = (int )(sn->end - sn->s);

      sn->s   = sn->buf;

      sn->end = sn->s + len;

    }

  }

  if (NODE_TYPE(b) == NODE_STRING) {

    StrNode* sn = STR_(b);

    if (sn->capa == 0) {

      int len = (int )(sn->end - sn->s);

      sn->s   = sn->buf;

      sn->end = sn->s + len;

    }

  }

}

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_SIZE; i++) {

    if (bs[i] != 0) return 0;

  }

  return 1;

}

extern int

onig_bbuf_init(BBuf* buf, int size)

{

  if (size <= 0) {

    size   = 0;

    buf->p = NULL;

  }

  else {

    buf->p = (UChar* )xmalloc(size);

    if (IS_NULL(buf->p)) return(ONIGERR_MEMORY);

  }

  buf->alloc = size;

  buf->used  = 0;

  return 0;

}

#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 */

static int

add_opcode(regex_t* reg, int opcode)

{

  BB_ADD1(reg, opcode);

  return 0;

}

static int

add_rel_addr(regex_t* reg, int addr)

{

  RelAddrType ra = (RelAddrType )addr;

  BB_ADD(reg, &ra, SIZE_RELADDR);

  return 0;

}

static int

add_abs_addr(regex_t* reg, int addr)

{

  AbsAddrType ra = (AbsAddrType )addr;

  BB_ADD(reg, &ra, SIZE_ABSADDR);

  return 0;

}

static int

add_length(regex_t* reg, int len)

{

  LengthType l = (LengthType )len;

  BB_ADD(reg, &l, SIZE_LENGTH);

  return 0;

}

static int

add_mem_num(regex_t* reg, int num)

{

  MemNumType n = (MemNumType )num;

  BB_ADD(reg, &n, SIZE_MEMNUM);

  return 0;

}

#if 0

static int

add_pointer(regex_t* reg, void* addr)

{

  PointerType ptr = (PointerType )addr;

  BB_ADD(reg, &ptr, SIZE_POINTER);

  return 0;

}

#endif

static int

add_option(regex_t* reg, OnigOptionType option)

{

  BB_ADD(reg, &option, SIZE_OPTION);

  return 0;

}

static int

add_save_type(regex_t* reg, enum SaveType type)

{

  SaveType t = (SaveType )type;

  BB_ADD(reg, &t, SIZE_SAVE_TYPE);

  return 0;

}

static int

add_update_var_type(regex_t* reg, enum UpdateVarType type)

{

  UpdateVarType t = (UpdateVarType )type;

  BB_ADD(reg, &t, SIZE_UPDATE_VAR_TYPE);

  return 0;

}

static int

add_mode(regex_t* reg, ModeType mode)

{

  BB_ADD(reg, &mode, SIZE_MODE);

  return 0;

}

static int

add_opcode_rel_addr(regex_t* reg, int opcode, int addr)

{

  int r;

  r = add_opcode(reg, opcode);

  if (r != 0) return r;

  r = add_rel_addr(reg, addr);

  return r;

}

static int

add_bytes(regex_t* reg, UChar* bytes, int len)

{

  BB_ADD(reg, bytes, len);

  return 0;

}

static int

add_bitset(regex_t* reg, BitSetRef bs)

{

  BB_ADD(reg, bs, SIZE_BITSET);

  return 0;

}

static int

add_opcode_option(regex_t* reg, int opcode, OnigOptionType option)

{

  int r;

  r = add_opcode(reg, opcode);

  if (r != 0) return r;

  r = add_option(reg, option);

  return r;

}

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

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

#define IS_NEED_STR_LEN_OP_EXACT(op) \

   ((op) == OP_EXACTN    || (op) == OP_EXACTMB2N ||\

    (op) == OP_EXACTMB3N || (op) == OP_EXACTMBN  || (op) == OP_EXACTN_IC)

static int

select_str_opcode(int mb_len, int str_len, int ignore_case)

{

  int op;

  if (ignore_case) {

    switch (str_len) {

    case 1:  op = OP_EXACT1_IC; break;

    default: op = OP_EXACTN_IC; break;

    }

  }

  else {

    switch (mb_len) {

    case 1:

      switch (str_len) {

      case 1:  op = OP_EXACT1; break;

      case 2:  op = OP_EXACT2; break;

      case 3:  op = OP_EXACT3; break;

      case 4:  op = OP_EXACT4; break;

      case 5:  op = OP_EXACT5; break;

      default: op = OP_EXACTN; break;

      }

      break;

    case 2:

      switch (str_len) {

      case 1:  op = OP_EXACTMB2N1; break;

      case 2:  op = OP_EXACTMB2N2; break;

      case 3:  op = OP_EXACTMB2N3; break;

      default: op = OP_EXACTMB2N;  break;

      }

      break;

    case 3:

      op = OP_EXACTMB3N;

      break;

    default:

      op = OP_EXACTMBN;

      break;

    }

  }

  return op;

}

static int

compile_tree_empty_check(Node* node, regex_t* reg, int empty_info, ScanEnv* env)

{

  int r;

  int saved_num_null_check = reg->num_null_check;

  if (empty_info != QUANT_BODY_IS_NOT_EMPTY) {

    r = add_opcode(reg, OP_EMPTY_CHECK_START);

    if (r != 0) return r;

    r = add_mem_num(reg, reg->num_null_check); /* NULL CHECK ID */

    if (r != 0) return r;

    reg->num_null_check++;

  }

  r = compile_tree(node, reg, env);

  if (r != 0) return r;

  if (empty_info != QUANT_BODY_IS_NOT_EMPTY) {

    if (empty_info == QUANT_BODY_IS_EMPTY)

      r = add_opcode(reg, OP_EMPTY_CHECK_END);

    else if (empty_info == QUANT_BODY_IS_EMPTY_MEM)

      r = add_opcode(reg, OP_EMPTY_CHECK_END_MEMST);

    else if (empty_info == QUANT_BODY_IS_EMPTY_REC)

      r = add_opcode(reg, OP_EMPTY_CHECK_END_MEMST_PUSH);

    if (r != 0) return r;

    r = add_mem_num(reg, saved_num_null_check); /* NULL CHECK ID */

  }

  return r;

}

#ifdef USE_CALL

static int

compile_call(CallNode* node, regex_t* reg, ScanEnv* env)

{

  int r;

  r = add_opcode(reg, OP_CALL);

  if (r != 0) return r;

  r = unset_addr_list_add(env->unset_addr_list, BB_GET_OFFSET_POS(reg),

                          NODE_CALL_BODY(node));

  if (r != 0) return r;

  r = add_abs_addr(reg, 0 /*dummy addr.*/);

  return r;

}

#endif

static int

compile_tree_n_times(Node* node, int n, regex_t* reg, ScanEnv* 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, int ignore_case)

{

  int len;

  int op = select_str_opcode(mb_len, str_len, ignore_case);

  len = SIZE_OPCODE;

  if (op == OP_EXACTMBN)  len += SIZE_LENGTH;

  if (IS_NEED_STR_LEN_OP_EXACT(op))

    len += SIZE_LENGTH;

  len += mb_len * str_len;

  return len;

}

static int

add_compile_string(UChar* s, int mb_len, int str_len,

                   regex_t* reg, int ignore_case)

{

  int op = select_str_opcode(mb_len, str_len, ignore_case);

  add_opcode(reg, op);

  if (op == OP_EXACTMBN)

    add_length(reg, mb_len);

  if (IS_NEED_STR_LEN_OP_EXACT(op)) {

    if (op == OP_EXACTN_IC)

      add_length(reg, mb_len * str_len);

    else

      add_length(reg, str_len);

  }

  add_bytes(reg, s, mb_len * str_len);

  return 0;

}

static int

compile_length_string_node(Node* node, regex_t* reg)

{

  int rlen, r, len, prev_len, slen, ambig;

  UChar *p, *prev;

  StrNode* sn;

  OnigEncoding enc = reg->enc;

  sn = STR_(node);

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

    return 0;

  ambig = NODE_STRING_IS_AMBIG(node);

  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, ambig);

      rlen += r;

      prev = p;

      slen = 1;

      prev_len = len;

    }

    p += len;

  }

  r = add_compile_string_length(prev, prev_len, slen, reg, ambig);

  rlen += r;

  return rlen;

}

static int

compile_length_string_raw_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, 0);

}

static int

compile_string_node(Node* node, regex_t* reg)

{

  int r, len, prev_len, slen, ambig;

  UChar *p, *prev, *end;

  StrNode* sn;

  OnigEncoding enc = reg->enc;

  sn = STR_(node);

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

    return 0;

  end = sn->end;

  ambig = NODE_STRING_IS_AMBIG(node);

  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, ambig);

      if (r != 0) return r;

      prev  = p;

      slen  = 1;

      prev_len = len;

    }

    p += len;

  }

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

}

static int

compile_string_raw_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, 0);

}

static int

add_multi_byte_cclass(BBuf* mbuf, regex_t* reg)

{

#ifdef PLATFORM_UNALIGNED_WORD_ACCESS

  add_length(reg, mbuf->used);

  return add_bytes(reg, mbuf->p, mbuf->used);

#else

  int r, pad_size;

  UChar* p = BB_GET_ADD_ADDRESS(reg) + SIZE_LENGTH;

  GET_ALIGNMENT_PAD_SIZE(p, pad_size);

  add_length(reg, mbuf->used + (WORD_ALIGNMENT_SIZE - 1));

  if (pad_size != 0) add_bytes(reg, PadBuf, pad_size);

  r = add_bytes(reg, mbuf->p, mbuf->used);

  /* padding for return value from compile_length_cclass_node() to be fix. */

  pad_size = (WORD_ALIGNMENT_SIZE - 1) - pad_size;

  if (pad_size != 0) add_bytes(reg, PadBuf, pad_size);

  return r;

#endif

}

static int

compile_length_cclass_node(CClassNode* cc, regex_t* reg)

{

  int len;

  if (IS_NULL(cc->mbuf)) {

    len = SIZE_OPCODE + SIZE_BITSET;

  }

  else {

    if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {

      len = SIZE_OPCODE;

    }

    else {

      len = SIZE_OPCODE + SIZE_BITSET;

    }

#ifdef PLATFORM_UNALIGNED_WORD_ACCESS

    len += SIZE_LENGTH + cc->mbuf->used;

#else

    len += SIZE_LENGTH + cc->mbuf->used + (WORD_ALIGNMENT_SIZE - 1);

#endif

  }

  return len;

}

static int

compile_cclass_node(CClassNode* cc, regex_t* reg)

{

  int r;

  if (IS_NULL(cc->mbuf)) {

    if (IS_NCCLASS_NOT(cc))

      add_opcode(reg, OP_CCLASS_NOT);

    else

      add_opcode(reg, OP_CCLASS);

    r = add_bitset(reg, cc->bs);

  }

  else {

    if (ONIGENC_MBC_MINLEN(reg->enc) > 1 || bitset_is_empty(cc->bs)) {

      if (IS_NCCLASS_NOT(cc))

        add_opcode(reg, OP_CCLASS_MB_NOT);

      else

        add_opcode(reg, OP_CCLASS_MB);

      r = add_multi_byte_cclass(cc->mbuf, reg);

    }

    else {

      if (IS_NCCLASS_NOT(cc))

        add_opcode(reg, OP_CCLASS_MIX_NOT);

      else

        add_opcode(reg, OP_CCLASS_MIX);

      r = add_bitset(reg, cc->bs);

      if (r != 0) return r;

      r = add_multi_byte_cclass(cc->mbuf, reg);

    }

  }

  return r;

}

static int

entry_repeat_range(regex_t* reg, int id, int lower, int upper)

{

#define REPEAT_RANGE_ALLOC  4

  OnigRepeatRange* p;

  if (reg->repeat_range_alloc == 0) {

    p = (OnigRepeatRange* )xmalloc(sizeof(OnigRepeatRange) * 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 = (OnigRepeatRange* )xrealloc(reg->repeat_range,

                                    sizeof(OnigRepeatRange) * 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_REPEAT_INFINITE(upper) ? 0x7fffffff : upper);

  return 0;

}

static int

compile_range_repeat_node(QuantNode* qn, int target_len, int empty_info,

                          regex_t* reg, ScanEnv* env)

{

  int r;

  int num_repeat = reg->num_repeat;

  r = add_opcode(reg, qn->greedy ? OP_REPEAT : OP_REPEAT_NG);

  if (r != 0) return r;

  r = add_mem_num(reg, num_repeat); /* OP_REPEAT ID */

  reg->num_repeat++;

  if (r != 0) return r;

  r = add_rel_addr(reg, target_len + SIZE_OP_REPEAT_INC);

  if (r != 0) return r;

  r = entry_repeat_range(reg, num_repeat, qn->lower, qn->upper);

  if (r != 0) return r;

  r = compile_tree_empty_check(NODE_QUANT_BODY(qn), reg, empty_info, env);

  if (r != 0) return r;

  if (

#ifdef USE_CALL

      NODE_IS_IN_MULTI_ENTRY(qn) ||

#endif

      NODE_IS_IN_REAL_REPEAT(qn)) {

    r = add_opcode(reg, qn->greedy ? OP_REPEAT_INC_SG : OP_REPEAT_INC_NG_SG);

  }

  else {

    r = add_opcode(reg, qn->greedy ? OP_REPEAT_INC : OP_REPEAT_INC_NG);

  }

  if (r != 0) return r;

  r = add_mem_num(reg, num_repeat); /* OP_REPEAT ID */

  return r;

}

static int

is_anychar_infinite_greedy(QuantNode* qn)

{

  if (qn->greedy && IS_REPEAT_INFINITE(qn->upper) &&

      NODE_IS_ANYCHAR(NODE_QUANT_BODY(qn)))

    return 1;

  else

    return 0;

}

#define QUANTIFIER_EXPAND_LIMIT_SIZE   50

#define CKN_ON   (ckn > 0)

static int

compile_length_quantifier_node(QuantNode* qn, regex_t* reg)

{

  int len, mod_tlen;

  int infinite = IS_REPEAT_INFINITE(qn->upper);

  enum QuantBodyEmpty empty_info = qn->body_empty_info;

  int tlen = compile_length_tree(NODE_QUANT_BODY(qn), reg);

  if (tlen < 0) return tlen;

  if (tlen == 0) return 0;

  /* anychar repeat */

  if (is_anychar_infinite_greedy(qn)) {

    if (qn->lower <= 1 ||

        int_multiply_cmp(tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0) {

      if (IS_NOT_NULL(qn->next_head_exact))

        return SIZE_OP_ANYCHAR_STAR_PEEK_NEXT + tlen * qn->lower;

      else

        return SIZE_OP_ANYCHAR_STAR + tlen * qn->lower;

    }

  }

  if (empty_info == QUANT_BODY_IS_NOT_EMPTY)

    mod_tlen = tlen;

  else

    mod_tlen = tlen + (SIZE_OP_EMPTY_CHECK_START + SIZE_OP_EMPTY_CHECK_END);

  if (infinite &&

      (qn->lower <= 1 ||

       int_multiply_cmp(tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {

    if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {

      len = SIZE_OP_JUMP;

    }

    else {

      len = tlen * qn->lower;

    }

    if (qn->greedy) {

      if (IS_NOT_NULL(qn->head_exact))

        len += SIZE_OP_PUSH_OR_JUMP_EXACT1 + mod_tlen + SIZE_OP_JUMP;

      else if (IS_NOT_NULL(qn->next_head_exact))

        len += SIZE_OP_PUSH_IF_PEEK_NEXT + mod_tlen + SIZE_OP_JUMP;

      else

        len += SIZE_OP_PUSH + mod_tlen + SIZE_OP_JUMP;

    }

    else

      len += SIZE_OP_JUMP + mod_tlen + SIZE_OP_PUSH;

  }

  else if (qn->upper == 0 && qn->is_refered != 0) { /* /(?<n>..){0}/ */

    len = SIZE_OP_JUMP + tlen;

  }

  else if (!infinite && qn->greedy &&

           (qn->upper == 1 ||

            int_multiply_cmp(tlen + SIZE_OP_PUSH, qn->upper,

                             QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {

    len = tlen * qn->lower;

    len += (SIZE_OP_PUSH + tlen) * (qn->upper - qn->lower);

  }

  else if (!qn->greedy && qn->upper == 1 && qn->lower == 0) { /* '??' */

    len = SIZE_OP_PUSH + SIZE_OP_JUMP + tlen;

  }

  else {

    len = SIZE_OP_REPEAT_INC

        + mod_tlen + SIZE_OPCODE + SIZE_RELADDR + SIZE_MEMNUM;

  }

  return len;

}

static int

compile_quantifier_node(QuantNode* qn, regex_t* reg, ScanEnv* env)

{

  int i, r, mod_tlen;

  int infinite = IS_REPEAT_INFINITE(qn->upper);

  enum QuantBodyEmpty empty_info = qn->body_empty_info;

  int tlen = compile_length_tree(NODE_QUANT_BODY(qn), reg);

  if (tlen < 0) return tlen;