New upstream version 6.9.5upstream/6.9.5

1 files changed, 1384 insertions, 838 deletions

diff --git a/src/regcomp.c b/src/regcomp.c
index 69d4b95..4d5b78f 100644
--- a/src/regcomp.c
+++ b/src/regcomp.c
@@ -2,7 +2,7 @@
   regcomp.c -  Oniguruma (regular expression library)
 **********************************************************************/
 /*-
- * Copyright (c) 2002-2019  K.Kosako
+ * Copyright (c) 2002-2020  K.Kosako
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -31,8 +31,21 @@
 
 #define OPS_INIT_SIZE  8
 
+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, ScanEnv* env);
+
 #if 0
 typedef struct {
   int  n;
@@ -99,7 +112,7 @@ int_stack_pop(int_stack* s)
 
 #ifdef ONIG_DEBUG
   if (s->n <= 0) {
-    fprintf(stderr, "int_stack_pop: fail empty. %p\n", s);
+    fprintf(DBGFP, "int_stack_pop: fail empty. %p\n", s);
     return 0;
   }
 #endif
@@ -228,13 +241,13 @@ ops_free(regex_t* reg)
       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: case OP_STR_N_IC:
+    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: case OP_STR_1_IC:
+    case OP_STR_MB2N3:
       break;
 
     case OP_CCLASS_NOT: case OP_CCLASS:
@@ -302,9 +315,6 @@ ops_calc_size_of_string_pool(regex_t* reg)
       total += op->exact_len_n.len * op->exact_len_n.n;
       break;
     case OP_STR_N:
-    case OP_STR_N_IC:
-      total += op->exact_n.n;
-      break;
     case OP_STR_MB2N:
       total += op->exact_n.n * 2;
       break;
@@ -357,7 +367,6 @@ ops_make_string_pool(regex_t* reg)
       curr += len;
       break;
     case OP_STR_N:
-    case OP_STR_N_IC:
       len = op->exact_n.n;
     copy:
       xmemcpy(curr, op->exact_n.s, len);
@@ -398,12 +407,12 @@ onig_set_default_case_fold_flag(OnigCaseFoldType case_fold_flag)
 }
 
 static int
-int_multiply_cmp(int x, int y, int v)
+len_multiply_cmp(OnigLen x, int y, OnigLen v)
 {
   if (x == 0 || y == 0) return -1;
 
-  if (x < INT_MAX / y) {
-    int xy = x * y;
+  if (x < INFINITE_LEN / y) {
+    OnigLen xy = x * (OnigLen )y;
     if (xy > v) return 1;
     else {
       if (xy == v) return 0;
@@ -411,7 +420,7 @@ int_multiply_cmp(int x, int y, int v)
     }
   }
   else
-    return 1;
+    return v == INFINITE_LEN ? 0 : 1;
 }
 
 extern int
@@ -419,7 +428,7 @@ onig_positive_int_multiply(int x, int y)
 {
   if (x == 0 || y == 0) return 0;
 
-  if (x < INT_MAX / y)
+  if (x < ONIG_INT_MAX / y)
     return x * y;
   else
     return -1;
@@ -489,42 +498,29 @@ node_str_node_cat(Node* node, Node* add)
 {
   int r;
 
-  if (STR_(node)->flag != STR_(add)->flag)
+  if (NODE_STATUS(node) != NODE_STATUS(add))
     return ONIGERR_TYPE_BUG;
 
-  r = onig_node_str_cat(node, STR_(add)->s, STR_(add)->end);
-  if (r != 0) return r;
-
-  if (NODE_STRING_IS_CASE_FOLD_MATCH(node))
-    STR_(node)->case_min_len += STR_(add)->case_min_len;
-
-  return 0;
-}
-
-static int
-node_str_cat_case_fold(Node* node, const UChar* s, const UChar* end, int case_min_len)
-{
-  int r;
-
-  if (! NODE_STRING_IS_CASE_FOLD_MATCH(node))
+  if (STR_(node)->flag != STR_(add)->flag)
     return ONIGERR_TYPE_BUG;
 
-  r = onig_node_str_cat(node, s, end);
+  r = onig_node_str_cat(node, STR_(add)->s, STR_(add)->end);
   if (r != 0) return r;
 
-  STR_(node)->case_min_len += case_min_len;
   return 0;
 }
 
 static void
-node_conv_to_str_node(Node* node, int flag)
+node_conv_to_str_node(Node* node, Node* ref_node)
 {
+  xmemset(node, 0, sizeof(*node));
   NODE_SET_TYPE(node, NODE_STRING);
-  STR_(node)->flag     = flag;
+  NODE_STATUS(node) = NODE_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;
-  STR_(node)->case_min_len = 0;
 }
 
 static OnigLen
@@ -554,7 +550,7 @@ bitset_is_empty(BitSetRef bs)
 {
   int i;
 
-  for (i = 0; i < (int )BITSET_SIZE; i++) {
+  for (i = 0; i < (int )BITSET_REAL_SIZE; i++) {
     if (bs[i] != 0) return 0;
   }
   return 1;
@@ -602,6 +598,351 @@ unset_addr_list_add(UnsetAddrList* list, int offset, struct _Node* node)
 }
 #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 != 0 && to->min_is_sure != 0;
+}
+
+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;
+    if (alt->min_is_sure != 0)
+      to->min_is_sure = TRUE;
+  }
+
+  if (to->max < alt->max) to->max = alt->max;
+}
+
+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;
+}
+
+/* fixed size pattern node only */
+static int
+node_char_len1(Node* node, regex_t* reg, MinMaxCharLen* ci, ScanEnv* env,
+               int level)
+{
+  MinMaxCharLen tci;
+  int r = CHAR_LEN_NORMAL;
+
+  level++;
+
+  switch (NODE_TYPE(node)) {
+  case NODE_LIST:
+    {
+      int first = TRUE;
+      do {
+        r = node_char_len1(NODE_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 = NODE_CDR(node)));
+    }
+    break;
+
+  case NODE_ALT:
+    {
+      int fixed;
+
+      r = node_char_len1(NODE_CAR(node), reg, ci, env, level);
+      if (r < 0) break;
+
+      fixed = TRUE;
+      while (IS_NOT_NULL(node = NODE_CDR(node))) {
+        r = node_char_len1(NODE_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 NODE_STRING:
+    {
+      OnigLen clen;
+      StrNode* sn = STR_(node);
+      UChar *s = sn->s;
+
+      if (NODE_IS_IGNORECASE(node) && ! NODE_STRING_IS_CRUDE(node)) {
+        /* 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 NODE_QUANT:
+    {
+      QuantNode* qn = QUANT_(node);
+
+      if (qn->lower == qn->upper) {
+        if (qn->upper == 0) {
+          mmcl_set(ci, 0);
+        }
+        else {
+          r = node_char_len1(NODE_BODY(node), reg, ci, env, level);
+          if (r < 0) break;
+          mmcl_multiply(ci, qn->lower);
+        }
+      }
+      else {
+        r = node_char_len1(NODE_BODY(node), reg, ci, env, level);
+        if (r < 0) break;
+        mmcl_repeat_range_multiply(ci, qn->lower, qn->upper);
+      }
+    }
+    break;
+
+#ifdef USE_CALL
+  case NODE_CALL:
+    if (NODE_IS_RECURSION(node))
+      mmcl_set_min_max(ci, 0, INFINITE_LEN, FALSE);
+    else
+      r = node_char_len1(NODE_BODY(node), reg, ci, env, level);
+    break;
+#endif
+
+  case NODE_CTYPE:
+  case NODE_CCLASS:
+    mmcl_set(ci, 1);
+    break;
+
+  case NODE_BAG:
+    {
+      BagNode* en = BAG_(node);
+
+      switch (en->type) {
+      case BAG_MEMORY:
+        if (NODE_IS_FIXED_CLEN(node)) {
+          mmcl_set_min_max(ci, en->min_char_len, en->max_char_len,
+                           NODE_IS_FIXED_CLEN_MIN_SURE(node));
+        }
+        else {
+          if (NODE_IS_MARK1(node)) {
+            mmcl_set_min_max(ci, 0, INFINITE_LEN, FALSE);
+          }
+          else {
+            NODE_STATUS_ADD(node, MARK1);
+            r = node_char_len1(NODE_BODY(node), reg, ci, env, level);
+            NODE_STATUS_REMOVE(node, MARK1);
+            if (r < 0) break;
+
+            en->min_char_len = ci->min;
+            en->max_char_len = ci->max;
+            NODE_STATUS_ADD(node, FIXED_CLEN);
+            if (ci->min_is_sure != 0)
+              NODE_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(NODE_BODY(node), reg, ci, env, level);
+        break;
+      case BAG_IF_ELSE:
+        {
+          MinMaxCharLen eci;
+
+          r = node_char_len1(NODE_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 NODE_ANCHOR:
+    mmcl_set(ci, 0);
+    /* can't optimize look-behind if anchor exists. */
+    ci->min_is_sure = FALSE;
+    break;
+
+  case NODE_GIMMICK:
+  zero:
+    mmcl_set(ci, 0);
+    break;
+
+  case NODE_BACKREF:
+    if (NODE_IS_CHECKER(node))
+      goto zero;
+
+    if (NODE_IS_RECURSION(node)) {
+#ifdef USE_BACKREF_WITH_LEVEL
+      if (NODE_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 = SCANENV_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, ScanEnv* env)
+{
+  return node_char_len1(node, reg, ci, env, 0);
+}
+
 
 static int
 add_op(regex_t* reg, int opcode)
@@ -626,7 +967,7 @@ static int compile_tree(Node* node, regex_t* reg, ScanEnv* env);
 
 #define IS_NEED_STR_LEN_OP(op) \
    ((op) == OP_STR_N    || (op) == OP_STR_MB2N ||\
-    (op) == OP_STR_MB3N || (op) == OP_STR_MBN  || (op) == OP_STR_N_IC)
+    (op) == OP_STR_MB3N || (op) == OP_STR_MBN)
 
 static int
 select_str_opcode(int mb_len, int str_len)
@@ -711,16 +1052,16 @@ compile_quant_body_with_empty_check(QuantNode* qn, regex_t* reg, ScanEnv* env)
   if (r != 0) return r;
 
   if (emptiness != BODY_IS_NOT_EMPTY) {
-    if (emptiness == BODY_IS_EMPTY_POSSIBILITY)
+    if (emptiness == BODY_MAY_BE_EMPTY)
       r = add_op(reg, OP_EMPTY_CHECK_END);
-    else if (emptiness == BODY_IS_EMPTY_POSSIBILITY_MEM) {
+    else if (emptiness == BODY_MAY_BE_EMPTY_MEM) {
       if (NODE_IS_EMPTY_STATUS_CHECK(qn) != 0)
         r = add_op(reg, OP_EMPTY_CHECK_END_MEMST);
       else
         r = add_op(reg, OP_EMPTY_CHECK_END);
     }
 #ifdef USE_CALL
-    else if (emptiness == BODY_IS_EMPTY_POSSIBILITY_REC)
+    else if (emptiness == BODY_MAY_BE_EMPTY_REC)
       r = add_op(reg, OP_EMPTY_CHECK_END_MEMST_PUSH);
 #endif
 
@@ -794,12 +1135,7 @@ add_compile_string(UChar* s, int mb_len, int str_len, regex_t* reg)
   else if (IS_NEED_STR_LEN_OP(op)) {
     p = onigenc_strdup(reg->enc, s, end);
     CHECK_NULL_RETURN_MEMERR(p);
-
-    if (op == OP_STR_N_IC)
-      COP(reg)->exact_n.n = byte_len;
-    else
-      COP(reg)->exact_n.n = str_len;
-
+    COP(reg)->exact_n.n = str_len;
     COP(reg)->exact_n.s = p;
   }
   else {
@@ -822,8 +1158,6 @@ compile_length_string_node(Node* node, regex_t* reg)
   if (sn->end <= sn->s)
     return 0;
 
-  if (NODE_STRING_IS_CASE_FOLD_MATCH(node) != 0) return 1;
-
   p = prev = sn->s;
   prev_len = enclen(enc, p);
   p += prev_len;
@@ -861,40 +1195,6 @@ compile_length_string_crude_node(StrNode* sn, regex_t* reg)
 }
 
 static int
-compile_ambig_string_node(Node* node, regex_t* reg)
-{
-  int r;
-  int len;
-  int byte_len;
-  UChar* p;
-  StrNode* sn;
-  OnigEncoding enc = reg->enc;
-
-  sn = STR_(node);
-  len = enclen(enc, sn->s);
-  byte_len = (int )(sn->end - sn->s);
-  if (len == byte_len) {
-    r = add_op(reg, OP_STR_1_IC);
-    if (r != 0) return r;
-
-    xmemset(COP(reg)->exact.s, 0, sizeof(COP(reg)->exact.s));
-    xmemcpy(COP(reg)->exact.s, sn->s, (size_t )byte_len);
-  }
-  else {
-    r = add_op(reg, OP_STR_N_IC);
-    if (r != 0) return r;
-
-    p = onigenc_strdup(enc, sn->s, sn->end);
-    CHECK_NULL_RETURN_MEMERR(p);
-
-    COP(reg)->exact_n.s = p;
-    COP(reg)->exact_n.n = byte_len;
-  }
-
-  return 0;
-}
-
-static int
 compile_string_node(Node* node, regex_t* reg)
 {
   int r, len, prev_len, slen;
@@ -907,9 +1207,6 @@ compile_string_node(Node* node, regex_t* reg)
     return 0;
 
   end = sn->end;
-  if (NODE_STRING_IS_CASE_FOLD_MATCH(node) != 0) {
-    return compile_ambig_string_node(node, reg);
-  }
 
   p = prev = sn->s;
   prev_len = enclen(enc, p);
@@ -1103,7 +1400,7 @@ compile_length_quantifier_node(QuantNode* qn, regex_t* reg)
   /* anychar repeat */
   if (is_anychar_infinite_greedy(qn)) {
     if (qn->lower <= 1 ||
-        int_multiply_cmp(tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0) {
+        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
@@ -1117,7 +1414,7 @@ compile_length_quantifier_node(QuantNode* qn, regex_t* reg)
 
   if (infinite &&
       (qn->lower <= 1 ||
-       int_multiply_cmp(tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
+       len_multiply_cmp(tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
     if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
       len = OPSIZE_JUMP;
     }
@@ -1148,7 +1445,7 @@ compile_length_quantifier_node(QuantNode* qn, regex_t* reg)
   }
   else if (!infinite && qn->greedy &&
            (qn->upper == 1 ||
-            int_multiply_cmp(tlen + OPSIZE_PUSH, qn->upper,
+            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);
@@ -1176,12 +1473,12 @@ compile_quantifier_node(QuantNode* qn, regex_t* reg, ScanEnv* env)
 
   if (is_anychar_infinite_greedy(qn) &&
       (qn->lower <= 1 ||
-       int_multiply_cmp(tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
+       len_multiply_cmp((OnigLen )tlen, qn->lower,
+                        QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
     r = compile_tree_n_times(NODE_QUANT_BODY(qn), qn->lower, reg, env);
     if (r != 0) return r;
     if (IS_NOT_NULL(qn->next_head_exact)) {
-      r = add_op(reg,
-                 IS_MULTILINE(CTYPE_OPTION(NODE_QUANT_BODY(qn), reg)) ?
+      r = add_op(reg, NODE_IS_MULTILINE(NODE_QUANT_BODY(qn)) ?
                  OP_ANYCHAR_ML_STAR_PEEK_NEXT : OP_ANYCHAR_STAR_PEEK_NEXT);
       if (r != 0) return r;
 
@@ -1189,8 +1486,7 @@ compile_quantifier_node(QuantNode* qn, regex_t* reg, ScanEnv* env)
       return 0;
     }
     else {
-      r = add_op(reg,
-                 IS_MULTILINE(CTYPE_OPTION(NODE_QUANT_BODY(qn), reg)) ?
+      r = add_op(reg, NODE_IS_MULTILINE(NODE_QUANT_BODY(qn)) ?
                  OP_ANYCHAR_ML_STAR : OP_ANYCHAR_STAR);
       return r;
     }
@@ -1202,7 +1498,8 @@ compile_quantifier_node(QuantNode* qn, regex_t* reg, ScanEnv* env)
 
   if (infinite &&
       (qn->lower <= 1 ||
-       int_multiply_cmp(tlen, qn->lower, QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
+       len_multiply_cmp((OnigLen )tlen, qn->lower,
+                        QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
     int addr;
 
     if (qn->lower == 1 && tlen > QUANTIFIER_EXPAND_LIMIT_SIZE) {
@@ -1297,7 +1594,7 @@ compile_quantifier_node(QuantNode* qn, regex_t* reg, ScanEnv* env)
   }
   else if (! infinite && qn->greedy &&
            (qn->upper == 1 ||
-            int_multiply_cmp(tlen + OPSIZE_PUSH, qn->upper,
+            len_multiply_cmp((OnigLen )tlen + OPSIZE_PUSH, qn->upper,
                              QUANTIFIER_EXPAND_LIMIT_SIZE) <= 0)) {
     int n = qn->upper - qn->lower;
 
@@ -1337,11 +1634,8 @@ static int
 compile_length_option_node(BagNode* node, regex_t* reg)
 {
   int tlen;
-  OnigOptionType prev = reg->options;
 
-  reg->options = node->o.options;
   tlen = compile_length_tree(NODE_BAG_BODY(node), reg);
-  reg->options = prev;
 
   return tlen;
 }
@@ -1350,11 +1644,8 @@ static int
 compile_option_node(BagNode* node, regex_t* reg, ScanEnv* env)
 {
   int r;
-  OnigOptionType prev = reg->options;
 
-  reg->options = node->o.options;
   r = compile_tree(NODE_BAG_BODY(node), reg, env);
-  reg->options = prev;
 
   return r;
 }
@@ -1423,10 +1714,10 @@ compile_length_bag_node(BagNode* node, regex_t* reg)
 
       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_OUT + OPSIZE_JUMP;
+      len = v + OPSIZE_PUSH + tlen + OPSIZE_POP + OPSIZE_JUMP;
     }
     else {
-      len = OPSIZE_ATOMIC_START + tlen + OPSIZE_ATOMIC_END;
+      len = OPSIZE_MARK + tlen + OPSIZE_CUT_TO_MARK;
     }
     break;
 
@@ -1438,8 +1729,7 @@ compile_length_bag_node(BagNode* node, regex_t* reg)
 
       len = compile_length_tree(cond, reg);
       if (len < 0) return len;
-      len += OPSIZE_PUSH;
-      len += OPSIZE_ATOMIC_START + OPSIZE_ATOMIC_END;
+      len += OPSIZE_PUSH + OPSIZE_MARK + OPSIZE_CUT_TO_MARK;
 
       if (IS_NOT_NULL(Then)) {
         tlen = compile_length_tree(Then, reg);
@@ -1447,7 +1737,7 @@ compile_length_bag_node(BagNode* node, regex_t* reg)
         len += tlen;
       }
 
-      len += OPSIZE_JUMP + OPSIZE_ATOMIC_END;
+      len += OPSIZE_JUMP + OPSIZE_CUT_TO_MARK;
 
       if (IS_NOT_NULL(Else)) {
         tlen = compile_length_tree(Else, reg);
@@ -1466,8 +1756,6 @@ compile_length_bag_node(BagNode* node, regex_t* reg)
   return len;
 }
 
-static int get_char_len_node(Node* node, regex_t* reg, int* len);
-
 static int
 compile_bag_memory_node(BagNode* node, regex_t* reg, ScanEnv* env)
 {
@@ -1481,7 +1769,7 @@ compile_bag_memory_node(BagNode* node, regex_t* reg, ScanEnv* env)
     if (r != 0) return r;
 
     node->m.called_addr = COP_CURR_OFFSET(reg) + 1 + OPSIZE_JUMP;
-    NODE_STATUS_ADD(node, ADDR_FIXED);
+    NODE_STATUS_ADD(node, FIXED_ADDR);
     COP(reg)->call.addr = (int )node->m.called_addr;
 
     if (node->m.regnum == 0) {
@@ -1574,35 +1862,49 @@ compile_bag_node(BagNode* node, regex_t* reg, ScanEnv* env)
 
       r = add_op(reg, OP_PUSH);
       if (r != 0) return r;
-      COP(reg)->push.addr = SIZE_INC + len + OPSIZE_POP_OUT + OPSIZE_JUMP;
+      COP(reg)->push.addr = SIZE_INC + len + OPSIZE_POP + OPSIZE_JUMP;
 
       r = compile_tree(NODE_QUANT_BODY(qn), reg, env);
       if (r != 0) return r;
-      r = add_op(reg, OP_POP_OUT);
+      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_OUT);
+      COP(reg)->jump.addr = -((int )OPSIZE_PUSH + len + (int )OPSIZE_POP);
     }
     else {
-      r = add_op(reg, OP_ATOMIC_START);
+      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(NODE_BAG_BODY(node), reg, env);
       if (r != 0) return r;
-      r = add_op(reg, OP_ATOMIC_END);
+      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 = NODE_BAG_BODY(node);
       Node* Then = node->te.Then;
       Node* Else = node->te.Else;
 
-      r = add_op(reg, OP_ATOMIC_START);
+      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);
       if (cond_len < 0) return cond_len;
@@ -1613,7 +1915,7 @@ compile_bag_node(BagNode* node, regex_t* reg, ScanEnv* env)
       else
         then_len = 0;
 
-      jump_len = cond_len + then_len + OPSIZE_ATOMIC_END + OPSIZE_JUMP;
+      jump_len = cond_len + then_len + OPSIZE_CUT_TO_MARK + OPSIZE_JUMP;
 
       r = add_op(reg, OP_PUSH);
       if (r != 0) return r;
@@ -1621,8 +1923,10 @@ compile_bag_node(BagNode* node, regex_t* reg, ScanEnv* env)
 
       r = compile_tree(cond, reg, env);
       if (r != 0) return r;
-      r = add_op(reg, OP_ATOMIC_END);
+      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);
@@ -1638,10 +1942,12 @@ compile_bag_node(BagNode* node, regex_t* reg, ScanEnv* env)
 
       r = add_op(reg, OP_JUMP);
       if (r != 0) return r;
-      COP(reg)->jump.addr = OPSIZE_ATOMIC_END + else_len + SIZE_INC;
+      COP(reg)->jump.addr = OPSIZE_CUT_TO_MARK + else_len + SIZE_INC;
 
-      r = add_op(reg, OP_ATOMIC_END);
+      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);
@@ -1666,16 +1972,38 @@ compile_length_anchor_node(AnchorNode* node, regex_t* reg)
 
   switch (node->type) {
   case ANCR_PREC_READ:
-    len = OPSIZE_PREC_READ_START + tlen + OPSIZE_PREC_READ_END;
+    len = OPSIZE_MARK + tlen + OPSIZE_CUT_TO_MARK;
     break;
   case ANCR_PREC_READ_NOT:
-    len = OPSIZE_PREC_READ_NOT_START + tlen + OPSIZE_PREC_READ_NOT_END;
+    len = OPSIZE_PUSH + OPSIZE_MARK + tlen + OPSIZE_POP_TO_MARK + OPSIZE_POP + OPSIZE_FAIL;
     break;
   case ANCR_LOOK_BEHIND:
-    len = OPSIZE_LOOK_BEHIND + tlen;
+    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);
+        if (llen < 0) return llen;
+
+        len += OPSIZE_MOVE + llen;
+      }
+    }
     break;
   case ANCR_LOOK_BEHIND_NOT:
-    len = OPSIZE_LOOK_BEHIND_NOT_START + tlen + OPSIZE_LOOK_BEHIND_NOT_END;
+    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);
+        if (llen < 0) return llen;
+
+        len += OPSIZE_MOVE + llen;
+      }
+    }
     break;
 
   case ANCR_WORD_BOUNDARY:
@@ -1701,10 +2029,254 @@ compile_length_anchor_node(AnchorNode* node, regex_t* reg)
 }
 
 static int
+compile_anchor_look_behind_node(AnchorNode* node, regex_t* reg, ScanEnv* 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(NODE_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;
+    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;
+
+    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(NODE_ANCHOR_BODY(node), reg, env);
+    if (r != 0) return r;
+
+    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,
+                                    ScanEnv* env)
+{
+  int r;
+  int len;
+
+  len = compile_length_tree(NODE_ANCHOR_BODY(node), reg);
+
+  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(NODE_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;
+    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 (IS_NOT_NULL(node->lead_node)) {
+      int clen;
+      MinMaxCharLen ci;
+
+      clen = compile_length_tree(node->lead_node, reg);
+      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;
+    }
+
+    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(NODE_ANCHOR_BODY(node), reg, env);
+    if (r != 0) return r;
+
+    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, ScanEnv* env)
 {
   int r, len;
   enum OpCode op;
+  MemNumType mid;
 
   switch (node->type) {
   case ANCR_BEGIN_BUF:      r = add_op(reg, OP_BEGIN_BUF);      break;
@@ -1712,7 +2284,11 @@ compile_anchor_node(AnchorNode* node, regex_t* reg, ScanEnv* env)
   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_BEGIN_POSITION); 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;
@@ -1744,7 +2320,7 @@ compile_anchor_node(AnchorNode* node, regex_t* reg, ScanEnv* env)
 
       type = EXTENDED_GRAPHEME_CLUSTER_BOUNDARY;
 #ifdef USE_UNICODE_WORD_BREAK
-      if (ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_TEXT_SEGMENT_WORD))
+      if (NODE_IS_TEXT_SEGMENT_WORD(node))
         type = WORD_BOUNDARY;
 #endif
 
@@ -1755,66 +2331,60 @@ compile_anchor_node(AnchorNode* node, regex_t* reg, ScanEnv* env)
     break;
 
   case ANCR_PREC_READ:
-    r = add_op(reg, OP_PREC_READ_START);
-    if (r != 0) return r;
-    r = compile_tree(NODE_ANCHOR_BODY(node), reg, env);
-    if (r != 0) return r;
-    r = add_op(reg, OP_PREC_READ_END);
-    break;
-
-  case ANCR_PREC_READ_NOT:
-    len = compile_length_tree(NODE_ANCHOR_BODY(node), reg);
-    if (len < 0) return len;
-
-    r = add_op(reg, OP_PREC_READ_NOT_START);
-    if (r != 0) return r;
-    COP(reg)->prec_read_not_start.addr = SIZE_INC + len + OPSIZE_PREC_READ_NOT_END;
-    r = compile_tree(NODE_ANCHOR_BODY(node), reg, env);
-    if (r != 0) return r;
-    r = add_op(reg, OP_PREC_READ_NOT_END);
-    break;
-
-  case ANCR_LOOK_BEHIND:
     {
-      int n;
-      r = add_op(reg, OP_LOOK_BEHIND);
+      ID_ENTRY(env, mid);
+      r = add_op(reg, OP_MARK);
       if (r != 0) return r;
-      if (node->char_len < 0) {
-        r = get_char_len_node(NODE_ANCHOR_BODY(node), reg, &n);
-        if (r != 0) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
-      }
-      else
-        n = node->char_len;
+      COP(reg)->mark.id = mid;
+      COP(reg)->mark.save_pos = TRUE;
 
-      COP(reg)->look_behind.len = n;
       r = compile_tree(NODE_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_LOOK_BEHIND_NOT:
+  case ANCR_PREC_READ_NOT:
     {
-      int n;
-
       len = compile_length_tree(NODE_ANCHOR_BODY(node), reg);
-      r = add_op(reg, OP_LOOK_BEHIND_NOT_START);
-      if (r != 0) return r;
-      COP(reg)->look_behind_not_start.addr = SIZE_INC + len + OPSIZE_LOOK_BEHIND_NOT_END;
+      if (len < 0) return len;
 
-      if (node->char_len < 0) {
-        r = get_char_len_node(NODE_ANCHOR_BODY(node), reg, &n);
-        if (r != 0) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
-      }
-      else
-        n = node->char_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;
 
-      COP(reg)->look_behind_not_start.len = n;
+      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(NODE_ANCHOR_BODY(node), reg, env);
       if (r != 0) return r;
-      r = add_op(reg, OP_LOOK_BEHIND_NOT_END);
+
+      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;
@@ -1826,7 +2396,7 @@ compile_anchor_node(AnchorNode* node, regex_t* reg, ScanEnv* env)
 static int
 compile_gimmick_node(GimmickNode* node, regex_t* reg)
 {
-  int r;
+  int r = 0;
 
   switch (node->type) {
   case GIMMICK_FAIL:
@@ -1834,10 +2404,10 @@ compile_gimmick_node(GimmickNode* node, regex_t* reg)
     break;
 
   case GIMMICK_SAVE:
-    r = add_op(reg, OP_PUSH_SAVE_VAL);
+    r = add_op(reg, OP_SAVE_VAL);
     if (r != 0) return r;
-    COP(reg)->push_save_val.type = node->detail_type;
-    COP(reg)->push_save_val.id   = node->id;
+    COP(reg)->save_val.type = node->detail_type;
+    COP(reg)->save_val.id   = node->id;
     break;
 
   case GIMMICK_UPDATE_VAR:
@@ -1845,6 +2415,7 @@ compile_gimmick_node(GimmickNode* node, regex_t* reg)
     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
@@ -1888,7 +2459,7 @@ compile_length_gimmick_node(GimmickNode* node, regex_t* reg)
     break;
 
   case GIMMICK_SAVE:
-    len = OPSIZE_PUSH_SAVE_VAL;
+    len = OPSIZE_SAVE_VAL;
     break;
 
   case GIMMICK_UPDATE_VAR:
@@ -2055,8 +2626,7 @@ compile_tree(Node* node, regex_t* reg, ScanEnv* env)
 
       switch (CTYPE_(node)->ctype) {
       case CTYPE_ANYCHAR:
-        r = add_op(reg, IS_MULTILINE(CTYPE_OPTION(node, reg)) ?
-                   OP_ANYCHAR_ML : OP_ANYCHAR);
+        r = add_op(reg, NODE_IS_MULTILINE(node) ? OP_ANYCHAR_ML : OP_ANYCHAR);
         break;
 
       case ONIGENC_CTYPE_WORD:
@@ -2098,7 +2668,7 @@ compile_tree(Node* node, regex_t* reg, ScanEnv* env)
       else {
 #ifdef USE_BACKREF_WITH_LEVEL
         if (NODE_IS_NEST_LEVEL(node)) {
-          if ((reg->options & ONIG_OPTION_IGNORECASE) != 0)
+          if (NODE_IS_IGNORECASE(node))
             r = add_op(reg, OP_BACKREF_WITH_LEVEL_IC);
           else
             r = add_op(reg, OP_BACKREF_WITH_LEVEL);
@@ -2111,7 +2681,7 @@ compile_tree(Node* node, regex_t* reg, ScanEnv* env)
 #endif
         if (br->back_num == 1) {
           n = br->back_static[0];
-          if (IS_IGNORECASE(reg->options)) {
+          if (NODE_IS_IGNORECASE(node)) {
             r = add_op(reg, OP_BACKREF_N_IC);
             if (r != 0) return r;
             COP(reg)->backref_n.n1 = n;
@@ -2132,7 +2702,7 @@ compile_tree(Node* node, regex_t* reg, ScanEnv* env)
           int num;
           int* p;
 
-          r = add_op(reg, IS_IGNORECASE(reg->options) ?
+          r = add_op(reg, NODE_IS_IGNORECASE(node) ?
                      OP_BACKREF_MULTI_IC : OP_BACKREF_MULTI);
           if (r != 0) return r;
 
@@ -2183,7 +2753,7 @@ compile_tree(Node* node, regex_t* reg, ScanEnv* env)
 
   default:
 #ifdef ONIG_DEBUG
-    fprintf(stderr, "compile_tree: undefined node type %d\n", NODE_TYPE(node));
+    fprintf(DBGFP, "compile_tree: undefined node type %d\n", NODE_TYPE(node));
 #endif
     break;
   }
@@ -2192,7 +2762,7 @@ compile_tree(Node* node, regex_t* reg, ScanEnv* env)
 }
 
 static int
-noname_disable_map(Node** plink, GroupNumRemap* map, int* counter)
+make_named_capture_number_map(Node** plink, GroupNumMap* map, int* counter)
 {
   int r = 0;
   Node* node = *plink;
@@ -2201,7 +2771,7 @@ noname_disable_map(Node** plink, GroupNumRemap* map, int* counter)
   case NODE_LIST:
   case NODE_ALT:
     do {
-      r = noname_disable_map(&(NODE_CAR(node)), map, counter);
+      r = make_named_capture_number_map(&(NODE_CAR(node)), map, counter);
     } while (r == 0 && IS_NOT_NULL(node = NODE_CDR(node)));
     break;
 
@@ -2209,7 +2779,7 @@ noname_disable_map(Node** plink, GroupNumRemap* map, int* counter)
     {
       Node** ptarget = &(NODE_BODY(node));
       Node*  old = *ptarget;
-      r = noname_disable_map(ptarget, map, counter);
+      r = make_named_capture_number_map(ptarget, map, counter);
       if (r != 0) return r;
       if (*ptarget != old && NODE_TYPE(*ptarget) == NODE_QUANT) {
         r = onig_reduce_nested_quantifier(node);
@@ -2225,35 +2795,35 @@ noname_disable_map(Node** plink, GroupNumRemap* map, int* counter)
           (*counter)++;
           map[en->m.regnum].new_val = *counter;
           en->m.regnum = *counter;
-          r = noname_disable_map(&(NODE_BODY(node)), map, counter);
+          r = make_named_capture_number_map(&(NODE_BODY(node)), map, counter);
         }
         else {
           *plink = NODE_BODY(node);
           NODE_BODY(node) = NULL_NODE;
           onig_node_free(node);
-          r = noname_disable_map(plink, map, counter);
+          r = make_named_capture_number_map(plink, map, counter);
         }
       }
       else if (en->type == BAG_IF_ELSE) {
-        r = noname_disable_map(&(NODE_BAG_BODY(en)), map, counter);
+        r = make_named_capture_number_map(&(NODE_BAG_BODY(en)), map, counter);
         if (r != 0) return r;
         if (IS_NOT_NULL(en->te.Then)) {
-          r = noname_disable_map(&(en->te.Then), map, counter);
+          r = make_named_capture_number_map(&(en->te.Then), map, counter);
           if (r != 0) return r;
         }
         if (IS_NOT_NULL(en->te.Else)) {
-          r = noname_disable_map(&(en->te.Else), map, counter);
+          r = make_named_capture_number_map(&(en->te.Else), map, counter);
           if (r != 0) return r;
         }
       }
       else
-        r = noname_disable_map(&(NODE_BODY(node)), map, counter);
+        r = make_named_capture_number_map(&(NODE_BODY(node)), map, counter);
     }
     break;
 
   case NODE_ANCHOR:
     if (IS_NOT_NULL(NODE_BODY(node)))
-      r = noname_disable_map(&(NODE_BODY(node)), map, counter);
+      r = make_named_capture_number_map(&(NODE_BODY(node)), map, counter);
     break;
 
   default:
@@ -2264,7 +2834,7 @@ noname_disable_map(Node** plink, GroupNumRemap* map, int* counter)
 }
 
 static int
-renumber_node_backref(Node* node, GroupNumRemap* map)
+renumber_backref_node(Node* node, GroupNumMap* map)
 {
   int i, pos, n, old_num;
   int *backs;
@@ -2292,7 +2862,7 @@ renumber_node_backref(Node* node, GroupNumRemap* map)
 }
 
 static int
-renumber_by_map(Node* node, GroupNumRemap* map)
+renumber_backref_traverse(Node* node, GroupNumMap* map)
 {
   int r = 0;
 
@@ -2300,28 +2870,28 @@ renumber_by_map(Node* node, GroupNumRemap* map)
   case NODE_LIST:
   case NODE_ALT:
     do {
-      r = renumber_by_map(NODE_CAR(node), map);
+      r = renumber_backref_traverse(NODE_CAR(node), map);
     } while (r == 0 && IS_NOT_NULL(node = NODE_CDR(node)));
     break;
 
   case NODE_QUANT:
-    r = renumber_by_map(NODE_BODY(node), map);
+    r = renumber_backref_traverse(NODE_BODY(node), map);
     break;
 
   case NODE_BAG:
     {
       BagNode* en = BAG_(node);
 
-      r = renumber_by_map(NODE_BODY(node), map);
+      r = renumber_backref_traverse(NODE_BODY(node), map);
       if (r != 0) return r;
 
       if (en->type == BAG_IF_ELSE) {
         if (IS_NOT_NULL(en->te.Then)) {
-          r = renumber_by_map(en->te.Then, map);
+          r = renumber_backref_traverse(en->te.Then, map);
           if (r != 0) return r;
         }
         if (IS_NOT_NULL(en->te.Else)) {
-          r = renumber_by_map(en->te.Else, map);
+          r = renumber_backref_traverse(en->te.Else, map);
           if (r != 0) return r;
         }
       }
@@ -2329,12 +2899,12 @@ renumber_by_map(Node* node, GroupNumRemap* map)
     break;
 
   case NODE_BACKREF:
-    r = renumber_node_backref(node, map);
+    r = renumber_backref_node(node, map);
     break;
 
   case NODE_ANCHOR:
     if (IS_NOT_NULL(NODE_BODY(node)))
-      r = renumber_by_map(NODE_BODY(node), map);
+      r = renumber_backref_traverse(NODE_BODY(node), map);
     break;
 
   default:
@@ -2403,18 +2973,18 @@ disable_noname_group_capture(Node** root, regex_t* reg, ScanEnv* env)
 {
   int r, i, pos, counter;
   MemStatusType loc;
-  GroupNumRemap* map;
+  GroupNumMap* map;
 
-  map = (GroupNumRemap* )xalloca(sizeof(GroupNumRemap) * (env->num_mem + 1));
+  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 = noname_disable_map(root, map, &counter);
+  r = make_named_capture_number_map(root, map, &counter);
   if (r != 0) return r;
 
-  r = renumber_by_map(*root, map);
+  r = renumber_backref_traverse(*root, map);
   if (r != 0) return r;
 
   for (i = 1, pos = 1; i <= env->num_mem; i++) {
@@ -2448,8 +3018,18 @@ fix_unset_addr_list(UnsetAddrList* uslist, regex_t* reg)
   AbsAddrType* paddr;
 
   for (i = 0; i < uslist->num; i++) {
-    if (! NODE_IS_ADDR_FIXED(uslist->us[i].target))
-      return ONIGERR_PARSER_BUG;
+    if (! NODE_IS_FIXED_ADDR(uslist->us[i].target)) {
+      if (NODE_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;
@@ -2462,173 +3042,6 @@ fix_unset_addr_list(UnsetAddrList* uslist, regex_t* reg)
 }
 #endif
 
-
-#define GET_CHAR_LEN_VARLEN           -1
-#define GET_CHAR_LEN_TOP_ALT_VARLEN   -2
-
-/* fixed size pattern node only */
-static int
-get_char_len_node1(Node* node, regex_t* reg, int* len, int level)
-{
-  int tlen;
-  int r = 0;
-
-  level++;
-  *len = 0;
-  switch (NODE_TYPE(node)) {
-  case NODE_LIST:
-    do {
-      r = get_char_len_node1(NODE_CAR(node), reg, &tlen, level);
-      if (r == 0)
-        *len = distance_add(*len, tlen);
-    } while (r == 0 && IS_NOT_NULL(node = NODE_CDR(node)));
-    break;
-
-  case NODE_ALT:
-    {
-      int tlen2;
-      int varlen = 0;
-
-      r = get_char_len_node1(NODE_CAR(node), reg, &tlen, level);
-      while (r == 0 && IS_NOT_NULL(node = NODE_CDR(node))) {
-        r = get_char_len_node1(NODE_CAR(node), reg, &tlen2, level);
-        if (r == 0) {
-          if (tlen != tlen2)
-            varlen = 1;
-        }
-      }
-      if (r == 0) {
-        if (varlen != 0) {
-          if (level == 1)
-            r = GET_CHAR_LEN_TOP_ALT_VARLEN;
-          else
-            r = GET_CHAR_LEN_VARLEN;
-        }
-        else
-          *len = tlen;
-      }
-    }
-    break;
-
-  case NODE_STRING:
-    {
-      StrNode* sn = STR_(node);
-      UChar *s = sn->s;
-
-      while (s < sn->end) {
-        s += enclen(reg->enc, s);
-        (*len)++;
-      }
-    }
-    break;
-
-  case NODE_QUANT:
-    {
-      QuantNode* qn = QUANT_(node);
-
-      if (qn->lower == qn->upper) {
-        if (qn->upper == 0) {
-          *len = 0;
-        }
-        else {
-          r = get_char_len_node1(NODE_BODY(node), reg, &tlen, level);
-          if (r == 0)
-            *len = distance_multiply(tlen, qn->lower);
-        }
-      }
-      else
-        r = GET_CHAR_LEN_VARLEN;
-    }
-    break;
-
-#ifdef USE_CALL
-  case NODE_CALL:
-    if (! NODE_IS_RECURSION(node))
-      r = get_char_len_node1(NODE_BODY(node), reg, len, level);
-    else
-      r = GET_CHAR_LEN_VARLEN;
-    break;
-#endif
-
-  case NODE_CTYPE:
-  case NODE_CCLASS:
-    *len = 1;
-    break;
-
-  case NODE_BAG:
-    {
-      BagNode* en = BAG_(node);
-
-      switch (en->type) {
-      case BAG_MEMORY:
-#ifdef USE_CALL
-        if (NODE_IS_CLEN_FIXED(node))
-          *len = en->char_len;
-        else {
-          r = get_char_len_node1(NODE_BODY(node), reg, len, level);
-          if (r == 0) {
-            en->char_len = *len;
-            NODE_STATUS_ADD(node, CLEN_FIXED);
-          }
-        }
-        break;
-#endif
-      case BAG_OPTION:
-      case BAG_STOP_BACKTRACK:
-        r = get_char_len_node1(NODE_BODY(node), reg, len, level);
-        break;
-      case BAG_IF_ELSE:
-        {
-          int clen, elen;
-
-          r = get_char_len_node1(NODE_BODY(node), reg, &clen, level);
-          if (r == 0) {
-            if (IS_NOT_NULL(en->te.Then)) {
-              r = get_char_len_node1(en->te.Then, reg, &tlen, level);
-              if (r != 0) break;
-            }
-            else tlen = 0;
-            if (IS_NOT_NULL(en->te.Else)) {
-              r = get_char_len_node1(en->te.Else, reg, &elen, level);
-              if (r != 0) break;
-            }
-            else elen = 0;
-
-            if (clen + tlen != elen) {
-              r = GET_CHAR_LEN_VARLEN;
-            }
-            else {
-              *len = elen;
-            }
-          }
-        }
-        break;
-      }
-    }
-    break;
-
-  case NODE_ANCHOR:
-  case NODE_GIMMICK:
-    break;
-
-  case NODE_BACKREF:
-    if (NODE_IS_CHECKER(node))
-      break;
-    /* fall */
-  default:
-    r = GET_CHAR_LEN_VARLEN;
-    break;
-  }
-
-  return r;
-}
-
-static int
-get_char_len_node(Node* node, regex_t* reg, int* len)
-{
-  return get_char_len_node1(node, reg, len, 0);
-}
-
 /* x is not included y ==>  1 : 0 */
 static int
 is_exclusive(Node* x, Node* y, regex_t* reg)
@@ -2804,14 +3217,9 @@ is_exclusive(Node* x, Node* y, regex_t* reg)
 
           len = NODE_STRING_LEN(x);
           if (len > NODE_STRING_LEN(y)) len = NODE_STRING_LEN(y);
-          if (NODE_STRING_IS_CASE_FOLD_MATCH(x) || NODE_STRING_IS_CASE_FOLD_MATCH(y)) {
-            /* tiny version */
-            return 0;
-          }
-          else {
-            for (i = 0, p = ys->s, q = xs->s; i < len; i++, p++, q++) {
-              if (*p != *q) return 1;
-            }
+
+          for (i = 0, p = ys->s, q = xs->s; i < len; i++, p++, q++) {
+            if (*p != *q) return 1;
           }
         }
         break;
@@ -2830,7 +3238,7 @@ is_exclusive(Node* x, Node* y, regex_t* reg)
 }
 
 static Node*
-get_head_value_node(Node* node, int exact, regex_t* reg)
+get_tree_head_literal(Node* node, int exact, regex_t* reg)
 {
   Node* n = NULL_NODE;
 
@@ -2853,7 +3261,7 @@ get_head_value_node(Node* node, int exact, regex_t* reg)
     break;
 
   case NODE_LIST:
-    n = get_head_value_node(NODE_CAR(node), exact, reg);
+    n = get_tree_head_literal(NODE_CAR(node), exact, reg);
     break;
 
   case NODE_STRING:
@@ -2864,7 +3272,7 @@ get_head_value_node(Node* node, int exact, regex_t* reg)
         break;
 
       if (exact == 0 ||
-          ! IS_IGNORECASE(reg->options) || NODE_STRING_IS_CRUDE(node)) {
+          ! NODE_IS_IGNORECASE(node) || NODE_STRING_IS_CRUDE(node)) {
         n = node;
       }
     }
@@ -2877,7 +3285,7 @@ get_head_value_node(Node* node, int exact, regex_t* reg)
         if (IS_NOT_NULL(qn->head_exact))
           n = qn->head_exact;
         else
-          n = get_head_value_node(NODE_BODY(node), exact, reg);
+          n = get_tree_head_literal(NODE_BODY(node), exact, reg);
       }
     }
     break;
@@ -2887,19 +3295,10 @@ get_head_value_node(Node* node, int exact, regex_t* reg)
       BagNode* en = BAG_(node);
       switch (en->type) {
       case BAG_OPTION:
-        {
-          OnigOptionType options = reg->options;
-
-          reg->options = BAG_(node)->o.options;
-          n = get_head_value_node(NODE_BODY(node), exact, reg);
-          reg->options = options;
-        }
-        break;
-
       case BAG_MEMORY:
       case BAG_STOP_BACKTRACK:
       case BAG_IF_ELSE:
-        n = get_head_value_node(NODE_BODY(node), exact, reg);
+        n = get_tree_head_literal(NODE_BODY(node), exact, reg);
         break;
       }
     }
@@ -2907,7 +3306,7 @@ get_head_value_node(Node* node, int exact, regex_t* reg)
 
   case NODE_ANCHOR:
     if (ANCHOR_(node)->type == ANCR_PREC_READ)
-      n = get_head_value_node(NODE_BODY(node), exact, reg);
+      n = get_tree_head_literal(NODE_BODY(node), exact, reg);
     break;
 
   case NODE_GIMMICK:
@@ -2918,42 +3317,244 @@ get_head_value_node(Node* node, int exact, regex_t* reg)
   return n;
 }
 
+enum GetValue {
+  GET_VALUE_NONE   = -1,
+  GET_VALUE_IGNORE =  0,
+  GET_VALUE_FOUND  =  1
+};
+
+static int
+get_tree_tail_literal(Node* node, Node** rnode, regex_t* reg)
+{
+  int r;
+
+  switch (NODE_TYPE(node)) {
+  case NODE_LIST:
+    if (IS_NULL(NODE_CDR(node))) {
+      r = get_tree_tail_literal(NODE_CAR(node), rnode, reg);
+    }
+    else {
+      r = get_tree_tail_literal(NODE_CDR(node), rnode, reg);
+      if (r == GET_VALUE_IGNORE) {
+        r = get_tree_tail_literal(NODE_CAR(node), rnode, reg);
+      }
+    }
+    break;
+
+#ifdef USE_CALL
+  case NODE_CALL:
+    r = get_tree_tail_literal(NODE_BODY(node), rnode, reg);
+    break;
+#endif
+
+  case NODE_CTYPE:
+    if (CTYPE_(node)->ctype == CTYPE_ANYCHAR) {
+      r = GET_VALUE_NONE;
+      break;
+    }
+    /* fall */
+  case NODE_CCLASS:
+    *rnode = node;
+    r = GET_VALUE_FOUND;
+    break;
+
+  case NODE_STRING:
+    {
+      StrNode* sn = STR_(node);
+
+      if (sn->end <= sn->s) {
+        r = GET_VALUE_IGNORE;
+        break;
+      }
+
+      if (NODE_IS_IGNORECASE(node) && ! NODE_STRING_IS_CRUDE(node)) {
+        r = GET_VALUE_NONE;
+        break;
+      }
+
+      *rnode = node;
+      r = GET_VALUE_FOUND;
+    }
+    break;
+
+  case NODE_QUANT:
+    {
+      QuantNode* qn = QUANT_(node);
+      if (qn->lower != 0) {
+        r = get_tree_tail_literal(NODE_BODY(node), rnode, reg);
+      }
+      else
+        r = GET_VALUE_NONE;
+    }
+    break;
+
+  case NODE_BAG:
+    {
+      BagNode* en = BAG_(node);
+
+      if (en->type == BAG_MEMORY) {
+        if (NODE_IS_MARK1(node))
+          r = GET_VALUE_NONE;
+        else {
+          NODE_STATUS_ADD(node, MARK1);
+          r = get_tree_tail_literal(NODE_BODY(node), rnode, reg);
+          NODE_STATUS_REMOVE(node, MARK1);
+        }
+      }
+      else {
+        r = get_tree_tail_literal(NODE_BODY(node), rnode, reg);
+      }
+    }
+    break;
+
+  case NODE_ANCHOR:
+  case NODE_GIMMICK:
+    r = GET_VALUE_IGNORE;
+    break;
+
+  case NODE_ALT:
+  case NODE_BACKREF:
+  default:
+    r = GET_VALUE_NONE;
+    break;
+  }
+
+  return r;
+}
+
 static int
-check_type_tree(Node* node, int type_mask, int bag_mask, int anchor_mask)
+check_called_node_in_look_behind(Node* node, int not)
 {
+  int r;
+
+  r = 0;
+
+  switch (NODE_TYPE(node)) {
+  case NODE_LIST:
+  case NODE_ALT:
+    do {
+      r = check_called_node_in_look_behind(NODE_CAR(node), not);
+    } while (r == 0 && IS_NOT_NULL(node = NODE_CDR(node)));
+    break;
+
+  case NODE_QUANT:
+    r = check_called_node_in_look_behind(NODE_BODY(node), not);
+    break;
+
+  case NODE_BAG:
+    {
+      BagNode* en = BAG_(node);
+
+      if (en->type == BAG_MEMORY) {
+        if (NODE_IS_MARK1(node))
+          return 0;
+        else {
+          NODE_STATUS_ADD(node, MARK1);
+          r = check_called_node_in_look_behind(NODE_BODY(node), not);
+          NODE_STATUS_REMOVE(node, MARK1);
+        }
+      }
+      else {
+        r = check_called_node_in_look_behind(NODE_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 NODE_ANCHOR:
+    if (IS_NOT_NULL(NODE_BODY(node)))
+      r = check_called_node_in_look_behind(NODE_BODY(node), not);
+    break;
+
+  case NODE_GIMMICK:
+    if (NODE_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 \
+  ( NODE_BIT_LIST | NODE_BIT_ALT | NODE_BIT_STRING | NODE_BIT_CCLASS \
+  | NODE_BIT_CTYPE | NODE_BIT_ANCHOR | NODE_BIT_BAG | NODE_BIT_QUANT \
+  | NODE_BIT_CALL | NODE_BIT_BACKREF | NODE_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 = NODE_TYPE(node);
-  if ((NODE_TYPE2BIT(type) & type_mask) == 0)
+  if ((NODE_TYPE2BIT(type) & ALLOWED_TYPE_IN_LB) == 0)
     return 1;
 
   switch (type) {
   case NODE_LIST:
   case NODE_ALT:
     do {
-      r = check_type_tree(NODE_CAR(node), type_mask, bag_mask, anchor_mask);
+      r = check_node_in_look_behind(NODE_CAR(node), not, used);
     } while (r == 0 && IS_NOT_NULL(node = NODE_CDR(node)));
     break;
 
   case NODE_QUANT:
-    r = check_type_tree(NODE_BODY(node), type_mask, bag_mask, anchor_mask);
+    r = check_node_in_look_behind(NODE_BODY(node), not, used);
     break;
 
   case NODE_BAG:
     {
       BagNode* en = BAG_(node);
-      if (((1<<en->type) & bag_mask) == 0)
+      if (((1<<en->type) & bag_mask[not]) == 0)
         return 1;
 
-      r = check_type_tree(NODE_BODY(node), type_mask, bag_mask, anchor_mask);
-      if (r == 0 && en->type == BAG_IF_ELSE) {
+      r = check_node_in_look_behind(NODE_BODY(node), not, used);
+      if (r != 0) break;
+
+      if (en->type == BAG_MEMORY) {
+        if (NODE_IS_BACKREF(node) || NODE_IS_CALLED(node)) *used = TRUE;
+      }
+      else if (en->type == BAG_IF_ELSE) {
         if (IS_NOT_NULL(en->te.Then)) {
-          r = check_type_tree(en->te.Then, type_mask, bag_mask, anchor_mask);
+          r = check_node_in_look_behind(en->te.Then, not, used);
           if (r != 0) break;
         }
         if (IS_NOT_NULL(en->te.Else)) {
-          r = check_type_tree(en->te.Else, type_mask, bag_mask, anchor_mask);
+          r = check_node_in_look_behind(en->te.Else, not, used);
         }
       }
     }
@@ -2961,14 +3562,22 @@ check_type_tree(Node* node, int type_mask, int bag_mask, int anchor_mask)
 
   case NODE_ANCHOR:
     type = ANCHOR_(node)->type;
-    if ((type & anchor_mask) == 0)
+    if ((type & anchor_mask[not]) == 0)
       return 1;
 
     if (IS_NOT_NULL(NODE_BODY(node)))
-      r = check_type_tree(NODE_BODY(node), type_mask, bag_mask, anchor_mask);
+      r = check_node_in_look_behind(NODE_BODY(node), not, used);
     break;
 
   case NODE_GIMMICK:
+    if (NODE_IS_ABSENT_WITH_SIDE_EFFECTS(node) != 0)
+      return 1;
+    break;
+
+  case NODE_CALL:
+    r = check_called_node_in_look_behind(NODE_BODY(node), not);
+    break;
+
   default:
     break;
   }
@@ -2976,7 +3585,7 @@ check_type_tree(Node* node, int type_mask, int bag_mask, int anchor_mask)
 }
 
 static OnigLen
-tree_min_len(Node* node, ScanEnv* env)
+node_min_byte_len(Node* node, ScanEnv* env)
 {
   OnigLen len;
   OnigLen tmin;
@@ -2992,9 +3601,9 @@ tree_min_len(Node* node, ScanEnv* env)
       if (NODE_IS_RECURSION(node)) break;
 
       backs = BACKREFS_P(br);
-      len = tree_min_len(mem_env[backs[0]].mem_node, env);
+      len = node_min_byte_len(mem_env[backs[0]].mem_node, env);
       for (i = 1; i < br->back_num; i++) {
-        tmin = tree_min_len(mem_env[backs[i]].mem_node, env);
+        tmin = node_min_byte_len(mem_env[backs[i]].mem_node, env);
         if (len > tmin) len = tmin;
       }
     }
@@ -3005,18 +3614,18 @@ tree_min_len(Node* node, ScanEnv* env)
     {
       Node* t = NODE_BODY(node);
       if (NODE_IS_RECURSION(node)) {
-        if (NODE_IS_MIN_FIXED(t))
+        if (NODE_IS_FIXED_MIN(t))
           len = BAG_(t)->min_len;
       }
       else
-        len = tree_min_len(t, env);
+        len = node_min_byte_len(t, env);
     }
     break;
 #endif
 
   case NODE_LIST:
     do {
-      tmin = tree_min_len(NODE_CAR(node), env);
+      tmin = node_min_byte_len(NODE_CAR(node), env);
       len = distance_add(len, tmin);
     } while (IS_NOT_NULL(node = NODE_CDR(node)));
     break;
@@ -3027,7 +3636,7 @@ tree_min_len(Node* node, ScanEnv* env)
       y = node;
       do {
         x = NODE_CAR(y);
-        tmin = tree_min_len(x, env);
+        tmin = node_min_byte_len(x, env);
         if (y == node) len = tmin;
         else if (len > tmin) len = tmin;
       } while (IS_NOT_NULL(y = NODE_CDR(y)));
@@ -3051,7 +3660,7 @@ tree_min_len(Node* node, ScanEnv* env)
       QuantNode* qn = QUANT_(node);
 
       if (qn->lower > 0) {
-        len = tree_min_len(NODE_BODY(node), env);
+        len = node_min_byte_len(NODE_BODY(node), env);
         len = distance_multiply(len, qn->lower);
       }
     }
@@ -3062,35 +3671,35 @@ tree_min_len(Node* node, ScanEnv* env)
       BagNode* en = BAG_(node);
       switch (en->type) {
       case BAG_MEMORY:
-        if (NODE_IS_MIN_FIXED(node))
+        if (NODE_IS_FIXED_MIN(node))
           len = en->min_len;
         else {
           if (NODE_IS_MARK1(node))
             len = 0;  /* recursive */
           else {
             NODE_STATUS_ADD(node, MARK1);
-            len = tree_min_len(NODE_BODY(node), env);
+            len = node_min_byte_len(NODE_BODY(node), env);
             NODE_STATUS_REMOVE(node, MARK1);
 
             en->min_len = len;
-            NODE_STATUS_ADD(node, MIN_FIXED);
+            NODE_STATUS_ADD(node, FIXED_MIN);
           }
         }
         break;
 
       case BAG_OPTION:
       case BAG_STOP_BACKTRACK:
-        len = tree_min_len(NODE_BODY(node), env);
+        len = node_min_byte_len(NODE_BODY(node), env);
         break;
       case BAG_IF_ELSE:
         {
           OnigLen elen;
 
-          len = tree_min_len(NODE_BODY(node), env);
+          len = node_min_byte_len(NODE_BODY(node), env);
           if (IS_NOT_NULL(en->te.Then))
-            len += tree_min_len(en->te.Then, env);
+            len += node_min_byte_len(en->te.Then, env);
           if (IS_NOT_NULL(en->te.Else))
-            elen = tree_min_len(en->te.Else, env);
+            elen = node_min_byte_len(en->te.Else, env);
           else elen = 0;
 
           if (elen < len) len = elen;
@@ -3118,7 +3727,7 @@ tree_min_len(Node* node, ScanEnv* env)
 }
 
 static OnigLen
-tree_max_len(Node* node, ScanEnv* env)
+node_max_byte_len(Node* node, ScanEnv* env)
 {
   OnigLen len;
   OnigLen tmax;
@@ -3127,14 +3736,14 @@ tree_max_len(Node* node, ScanEnv* env)
   switch (NODE_TYPE(node)) {
   case NODE_LIST:
     do {
-      tmax = tree_max_len(NODE_CAR(node), env);
+      tmax = node_max_byte_len(NODE_CAR(node), env);
       len = distance_add(len, tmax);
     } while (IS_NOT_NULL(node = NODE_CDR(node)));
     break;
 
   case NODE_ALT:
     do {
-      tmax = tree_max_len(NODE_CAR(node), env);
+      tmax = node_max_byte_len(NODE_CAR(node), env);
       if (len < tmax) len = tmax;
     } while (IS_NOT_NULL(node = NODE_CDR(node)));
     break;
@@ -3158,12 +3767,16 @@ tree_max_len(Node* node, ScanEnv* env)
       MemEnv* mem_env = SCANENV_MEMENV(env);
       BackRefNode* br = BACKREF_(node);
       if (NODE_IS_RECURSION(node)) {
-        len = INFINITE_LEN;
+#ifdef USE_BACKREF_WITH_LEVEL
+        if (NODE_IS_NEST_LEVEL(node)) {
+          len = INFINITE_LEN;
+        }
+#endif
         break;
       }
       backs = BACKREFS_P(br);
       for (i = 0; i < br->back_num; i++) {
-        tmax = tree_max_len(mem_env[backs[i]].mem_node, env);
+        tmax = node_max_byte_len(mem_env[backs[i]].mem_node, env);
         if (len < tmax) len = tmax;
       }
     }
@@ -3172,7 +3785,7 @@ tree_max_len(Node* node, ScanEnv* env)
 #ifdef USE_CALL
   case NODE_CALL:
     if (! NODE_IS_RECURSION(node))
-      len = tree_max_len(NODE_BODY(node), env);
+      len = node_max_byte_len(NODE_BODY(node), env);
     else
       len = INFINITE_LEN;
     break;
@@ -3183,7 +3796,7 @@ tree_max_len(Node* node, ScanEnv* env)
       QuantNode* qn = QUANT_(node);
 
       if (qn->upper != 0) {
-        len = tree_max_len(NODE_BODY(node), env);
+        len = node_max_byte_len(NODE_BODY(node), env);
         if (len != 0) {
           if (! IS_INFINITE_REPEAT(qn->upper))
             len = distance_multiply(len, qn->upper);
@@ -3199,37 +3812,37 @@ tree_max_len(Node* node, ScanEnv* env)
       BagNode* en = BAG_(node);
       switch (en->type) {
       case BAG_MEMORY:
-        if (NODE_IS_MAX_FIXED(node))
+        if (NODE_IS_FIXED_MAX(node))
           len = en->max_len;
         else {
           if (NODE_IS_MARK1(node))
             len = INFINITE_LEN;
           else {
             NODE_STATUS_ADD(node, MARK1);
-            len = tree_max_len(NODE_BODY(node), env);
+            len = node_max_byte_len(NODE_BODY(node), env);
             NODE_STATUS_REMOVE(node, MARK1);
 
             en->max_len = len;
-            NODE_STATUS_ADD(node, MAX_FIXED);
+            NODE_STATUS_ADD(node, FIXED_MAX);
           }
         }
         break;
 
       case BAG_OPTION:
       case BAG_STOP_BACKTRACK:
-        len = tree_max_len(NODE_BODY(node), env);
+        len = node_max_byte_len(NODE_BODY(node), env);
         break;
       case BAG_IF_ELSE:
         {
           OnigLen tlen, elen;
 
-          len = tree_max_len(NODE_BODY(node), env);
+          len = node_max_byte_len(NODE_BODY(node), env);
           if (IS_NOT_NULL(en->te.Then)) {
-            tlen = tree_max_len(en->te.Then, env);
+            tlen = node_max_byte_len(en->te.Then, env);
             len = distance_add(len, tlen);
           }
           if (IS_NOT_NULL(en->te.Else))
-            elen = tree_max_len(en->te.Else, env);
+            elen = node_max_byte_len(en->te.Else, env);
           else elen = 0;
 
           if (elen > len) len = elen;
@@ -3537,7 +4150,7 @@ infinite_recursive_call_check(Node* node, ScanEnv* env, int head)
         if (ret < 0 || (ret & RECURSION_INFINITE) != 0) return ret;
         r |= ret;
         if (head != 0) {
-          min = tree_min_len(NODE_CAR(x), env);
+          min = node_min_byte_len(NODE_CAR(x), env);
           if (min != 0) head = 0;
         }
       } while (IS_NOT_NULL(x = NODE_CDR(x)));
@@ -3602,7 +4215,7 @@ infinite_recursive_call_check(Node* node, ScanEnv* env, int head)
         if (IS_NOT_NULL(en->te.Then)) {
           OnigLen min;
           if (head != 0) {
-            min = tree_min_len(NODE_BODY(node), env);
+            min = node_min_byte_len(NODE_BODY(node), env);
           }
           else min = 0;
 
@@ -3888,7 +4501,9 @@ reduce_string_list(Node* node)
         next_node = NODE_CDR(node);
         curr = NODE_CAR(node);
         if (NODE_TYPE(curr) == NODE_STRING) {
-          if (IS_NULL(prev) || STR_(curr)->flag != STR_(prev)->flag) {
+          if (IS_NULL(prev)
+              || STR_(curr)->flag  != STR_(prev)->flag
+              || NODE_STATUS(curr) != NODE_STATUS(prev)) {
             prev = curr;
             prev_node = node;
           }
@@ -3967,9 +4582,13 @@ reduce_string_list(Node* node)
 static int
 divide_look_behind_alternatives(Node* node)
 {
+  int r;
+  int anc_type;
   Node *head, *np, *insert_node;
-  AnchorNode* an = ANCHOR_(node);
-  int anc_type = an->type;
+  AnchorNode* an;
+
+  an = ANCHOR_(node);
+  anc_type = an->type;
 
   head = NODE_ANCHOR_BODY(an);
   np = NODE_CAR(head);
@@ -3979,7 +4598,8 @@ divide_look_behind_alternatives(Node* node)
 
   np = node;
   while (IS_NOT_NULL(np = NODE_CDR(np))) {
-    insert_node = onig_node_new_anchor(anc_type, an->ascii_mode);
+    r = onig_node_copy(&insert_node, head);
+    if (r != 0) return r;
     CHECK_NULL_RETURN_MEMERR(insert_node);
     NODE_BODY(insert_node) = NODE_CAR(np);
     NODE_CAR(np) = insert_node;
@@ -3995,21 +4615,162 @@ divide_look_behind_alternatives(Node* node)
 }
 
 static int
-tune_look_behind(Node* node, regex_t* reg, ScanEnv* env)
+node_reduce_in_look_behind(Node* node)
 {
-  int r, len;
+  NodeType type;
+  Node* body;
+
+  if (NODE_TYPE(node) != NODE_QUANT) return 0;
+
+  body = NODE_BODY(node);
+  type = NODE_TYPE(body);
+  if (type == NODE_STRING || type == NODE_CTYPE ||
+      type == NODE_CCLASS || type == NODE_BACKREF) {
+    QuantNode* qn = QUANT_(node);
+    qn->upper = qn->lower;
+    if (qn->upper == 0)
+      return 1; /* removed */
+  }
+
+  return 0;
+}
+
+static int
+list_reduce_in_look_behind(Node* node)
+{
+  int r;
+
+  switch (NODE_TYPE(node)) {
+  case NODE_QUANT:
+    r = node_reduce_in_look_behind(node);
+    if (r > 0) r = 0;
+    break;
+
+  case NODE_LIST:
+    do {
+      r = node_reduce_in_look_behind(NODE_CAR(node));
+      if (r <= 0) break;
+    } while (IS_NOT_NULL(node = NODE_CDR(node)));
+    break;
+
+  default:
+    r = 0;
+    break;
+  }
+
+  return r;
+}
+
+static int
+alt_reduce_in_look_behind(Node* node, regex_t* reg, ScanEnv* env)
+{
+  int r;
+
+  switch (NODE_TYPE(node)) {
+  case NODE_ALT:
+    do {
+      r = list_reduce_in_look_behind(NODE_CAR(node));
+    } while (r == 0 && IS_NOT_NULL(node = NODE_CDR(node)));
+    break;
+
+  default:
+    r = list_reduce_in_look_behind(node);
+    break;
+  }
+
+  return r;
+}
+
+static int tune_tree(Node* node, regex_t* reg, int state, ScanEnv* env);
+
+static int
+tune_look_behind(Node* node, regex_t* reg, int state, ScanEnv* env)
+{
+  int r;
+  int state1;
+  int used;
+  MinMaxCharLen ci;
+  Node* body;
   AnchorNode* an = ANCHOR_(node);
 
-  r = get_char_len_node(NODE_ANCHOR_BODY(an), reg, &len);
-  if (r == 0)
-    an->char_len = len;
-  else if (r == GET_CHAR_LEN_VARLEN)
-    r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
-  else if (r == GET_CHAR_LEN_TOP_ALT_VARLEN) {
-    if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND))
-      r = divide_look_behind_alternatives(node);
-    else
-      r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
+  used = FALSE;
+  r = check_node_in_look_behind(NODE_ANCHOR_BODY(an),
+                                an->type == ANCR_LOOK_BEHIND_NOT ? 1 : 0,
+                                &used);
+  if (r < 0) return r;
+  if (r > 0) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
+
+  if (an->type == ANCR_LOOK_BEHIND_NOT)
+    state1 = state | IN_NOT | IN_LOOK_BEHIND;
+  else
+    state1 = state | IN_LOOK_BEHIND;
+
+  body = NODE_ANCHOR_BODY(an);
+  /* Execute tune_tree(body) before call node_char_len().
+     Because case-fold expansion must be done before node_char_len().
+   */
+  r = tune_tree(body, reg, state1, env);
+  if (r != 0) return r;
+
+  r = alt_reduce_in_look_behind(body, reg, env);
+  if (r != 0) return r;
+
+  r = node_char_len(body, reg, &ci, env);
+  if (r >= 0) {
+    /* #177: overflow in onigenc_step_back() */
+    if ((ci.max != INFINITE_LEN && ci.max > LOOK_BEHIND_MAX_CHAR_LEN)
+      || ci.min > LOOK_BEHIND_MAX_CHAR_LEN) {
+      return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
+    }
+
+    if (ci.min == 0 && ci.min_is_sure != 0 && used == FALSE) {
+      if (an->type == ANCR_LOOK_BEHIND_NOT)
+        r = onig_node_reset_fail(node);
+      else
+        r = onig_node_reset_empty(node);
+
+      return r;
+    }
+
+    if (r == CHAR_LEN_TOP_ALT_FIXED) {
+      if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_DIFFERENT_LEN_ALT_LOOK_BEHIND)) {
+        r = divide_look_behind_alternatives(node);
+        if (r == 0)
+          r = tune_tree(node, reg, state, env);
+      }
+      else if (IS_SYNTAX_BV(env->syntax, ONIG_SYN_VARIABLE_LEN_LOOK_BEHIND))
+        goto normal;
+      else
+        r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
+    }
+    else { /* CHAR_LEN_NORMAL */
+    normal:
+      if (ci.min == INFINITE_LEN) {
+        r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
+      }
+      else {
+        if (ci.min != ci.max &&
+            ! IS_SYNTAX_BV(env->syntax, ONIG_SYN_VARIABLE_LEN_LOOK_BEHIND)) {
+          r = ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
+        }
+        else {
+          Node* tail;
+
+          /* check lead_node is already set by double call after
+             divide_look_behind_alternatives() */
+          if (IS_NULL(an->lead_node)) {
+            an->char_min_len = ci.min;
+            an->char_max_len = ci.max;
+            r = get_tree_tail_literal(body, &tail, reg);
+            if (r == GET_VALUE_FOUND) {
+              r = onig_node_copy(&(an->lead_node), tail);
+              if (r != 0) return r;
+            }
+          }
+          r = ONIG_NORMAL;
+        }
+      }
+    }
   }
 
   return r;
@@ -4026,7 +4787,7 @@ tune_next(Node* node, Node* next_node, regex_t* reg)
     QuantNode* qn = QUANT_(node);
     if (qn->greedy && IS_INFINITE_REPEAT(qn->upper)) {
 #ifdef USE_QUANT_PEEK_NEXT
-      Node* n = get_head_value_node(next_node, 1, reg);
+      Node* n = get_tree_head_literal(next_node, 1, reg);
       /* '\0': for UTF-16BE etc... */
       if (IS_NOT_NULL(n) && STR_(n)->s[0] != '\0') {
         qn->next_head_exact = n;
@@ -4036,9 +4797,9 @@ tune_next(Node* node, Node* next_node, regex_t* reg)
       if (qn->lower <= 1) {
         if (is_strict_real_node(NODE_BODY(node))) {
           Node *x, *y;
-          x = get_head_value_node(NODE_BODY(node), 0, reg);
+          x = get_tree_head_literal(NODE_BODY(node), 0, reg);
           if (IS_NOT_NULL(x)) {
-            y = get_head_value_node(next_node,  0, reg);
+            y = get_tree_head_literal(next_node,  0, reg);
             if (IS_NOT_NULL(y) && is_exclusive(x, y, reg)) {
               Node* en = onig_node_new_bag(BAG_STOP_BACKTRACK);
               CHECK_NULL_RETURN_MEMERR(en);
@@ -4076,11 +4837,13 @@ is_all_code_len_1_items(int n, OnigCaseFoldCodeItem items[])
 }
 
 static int
-get_min_max_byte_len_case_fold_items(int n, OnigCaseFoldCodeItem items[], int* rmin, int* rmax)
+get_min_max_byte_len_case_fold_items(int n, OnigCaseFoldCodeItem items[],
+                                     OnigLen* rmin, OnigLen* rmax)
 {
-  int i, len, minlen, maxlen;
+  int i;
+  OnigLen len, minlen, maxlen;
 
-  minlen = INT_MAX;
+  minlen = INFINITE_LEN;
   maxlen = 0;
   for (i = 0; i < n; i++) {
     OnigCaseFoldCodeItem* item = items + i;
@@ -4096,45 +4859,6 @@ get_min_max_byte_len_case_fold_items(int n, OnigCaseFoldCodeItem items[], int* r
 }
 
 static int
-conv_string_case_fold(OnigEncoding enc, OnigCaseFoldType case_fold_flag,
-           UChar* s, UChar* end, UChar** rs, UChar** rend, int* rcase_min_len)
-{
-  UChar *p, buf[ONIGENC_MBC_CASE_FOLD_MAXLEN];
-  UChar *sbuf, *ebuf, *sp;
-  int i, n, len, sbuf_size;
-
-  *rs = NULL;
-  sbuf_size = (int )(end - s) * 2;
-  sbuf = (UChar* )xmalloc(sbuf_size);
-  CHECK_NULL_RETURN_MEMERR(sbuf);
-  ebuf = sbuf + sbuf_size;
-
-  n = 0;
-  sp = sbuf;
-  p = s;
-  while (p < end) {
-    len = ONIGENC_MBC_CASE_FOLD(enc, case_fold_flag, &p, end, buf);
-    for (i = 0; i < len; i++) {
-      if (sp >= ebuf) {
-        sbuf = (UChar* )xrealloc(sbuf, sbuf_size * 2);
-        CHECK_NULL_RETURN_MEMERR(sbuf);
-        sp = sbuf + sbuf_size;
-        sbuf_size *= 2;
-        ebuf = sbuf + sbuf_size;
-      }
-
-      *sp++ = buf[i];
-    }
-    n++;
-  }
-
-  *rs = sbuf;
-  *rend = sp;
-  *rcase_min_len = n;
-  return 0;
-}
-
-static int
 make_code_list_to_string(Node** rnode, OnigEncoding enc,
                          int n, OnigCodePoint codes[])
 {
@@ -4186,7 +4910,7 @@ unravel_cf_node_add(Node** rlist, Node* add)
 
 static int
 unravel_cf_string_add(Node** rlist, Node** rsn, UChar* s, UChar* end,
-                      unsigned int flag, int case_min_len)
+                      unsigned int flag)
 {
   int r;
   Node *sn, *list;
@@ -4195,17 +4919,13 @@ unravel_cf_string_add(Node** rlist, Node** rsn, UChar* s, UChar* end,
   sn   = *rsn;
 
   if (IS_NOT_NULL(sn) && STR_(sn)->flag == flag) {
-    if (NODE_STRING_IS_CASE_FOLD_MATCH(sn))
-      r = node_str_cat_case_fold(sn, s, end, case_min_len);
-    else
-      r = onig_node_str_cat(sn, s, end);
+    r = onig_node_str_cat(sn, s, end);
   }
   else {
     sn = onig_node_new_str(s, end);
     CHECK_NULL_RETURN_MEMERR(sn);
 
     STR_(sn)->flag = flag;
-    STR_(sn)->case_min_len = case_min_len;
     r = unravel_cf_node_add(&list, sn);
   }
 
@@ -4217,27 +4937,8 @@ unravel_cf_string_add(Node** rlist, Node** rsn, UChar* s, UChar* end,
 }
 
 static int
-unravel_cf_string_fold_add(Node** rlist, Node** rsn, OnigEncoding enc,
-                      OnigCaseFoldType case_fold_flag, UChar* s, UChar* end)
-{
-  int r;
-  int case_min_len;
-  UChar *rs, *rend;
-
-  r = conv_string_case_fold(enc, case_fold_flag, s, end,
-                            &rs, &rend, &case_min_len);
-  if (r != 0) return r;
-
-  r = unravel_cf_string_add(rlist, rsn, rs, rend,
-                            NODE_STRING_CASE_FOLD_MATCH, case_min_len);
-  xfree(rs);
-
-  return r;
-}
-
-static int
 unravel_cf_string_alt_or_cc_add(Node** rlist, int n,
-            OnigCaseFoldCodeItem items[], int byte_len, OnigEncoding enc,
+            OnigCaseFoldCodeItem items[], OnigEncoding enc,
             OnigCaseFoldType case_fold_flag, UChar* s, UChar* end)
 {
   int r, i;
@@ -4294,7 +4995,7 @@ unravel_cf_string_alt_or_cc_add(Node** rlist, int n,
 static int
 unravel_cf_look_behind_add(Node** rlist, Node** rsn,
                 int n, OnigCaseFoldCodeItem items[], OnigEncoding enc,
-                UChar* s, int one_len)
+                UChar* s, OnigLen one_len)
 {
   int r, i, found;
 
@@ -4309,7 +5010,7 @@ unravel_cf_look_behind_add(Node** rlist, Node** rsn,
   }
 
   if (found == 0) {
-    r = unravel_cf_string_add(rlist, rsn, s, s + one_len, 0 /* flag */, 0);
+    r = unravel_cf_string_add(rlist, rsn, s, s + one_len, 0 /* flag */);
   }
   else {
     Node* node;
@@ -4340,7 +5041,8 @@ unravel_cf_look_behind_add(Node** rlist, Node** rsn,
 static int
 unravel_case_fold_string(Node* node, regex_t* reg, int state)
 {
-  int r, n, one_len, min_len, max_len, in_look_behind;
+  int r, n, in_look_behind;
+  OnigLen min_len, max_len, one_len;
   UChar *start, *end, *p, *q;
   StrNode* snode;
   Node *sn, *list;
@@ -4349,8 +5051,8 @@ unravel_case_fold_string(Node* node, regex_t* reg, int state)
 
   if (NODE_STRING_IS_CASE_EXPANDED(node)) return 0;
 
+  NODE_STATUS_REMOVE(node, IGNORECASE);
   snode = STR_(node);
-
   start = snode->s;
   end   = snode->end;
   if (start >= end) return 0;
@@ -4368,32 +5070,36 @@ unravel_case_fold_string(Node* node, regex_t* reg, int state)
       goto err;
     }
 
-    one_len = enclen(enc, p);
+    one_len = (OnigLen )enclen(enc, p);
     if (n == 0) {
       q = p + one_len;
-      r = unravel_cf_string_add(&list, &sn, p, q, 0 /* flag */, 0);
+      r = unravel_cf_string_add(&list, &sn, p, q, 0 /* flag */);
       if (r != 0) goto err;
     }
     else {
       if (in_look_behind != 0) {
         q = p + one_len;
+        if (items[0].byte_len != one_len) {
+          r = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, reg->case_fold_flag, p, q,
+                                                 items);
+          if (r < 0) goto err;
+          n = r;
+        }
         r = unravel_cf_look_behind_add(&list, &sn, n, items, enc, p, one_len);
         if (r != 0) goto err;
       }
       else {
         get_min_max_byte_len_case_fold_items(n, items, &min_len, &max_len);
-        q = p + max_len;
-        if (one_len == max_len && min_len == max_len) {
-          r = unravel_cf_string_alt_or_cc_add(&list, n, items, max_len, enc,
-                                              reg->case_fold_flag, p, q);
-          if (r != 0) goto err;
-          sn = NULL_NODE;
-        }
-        else {
-          r = unravel_cf_string_fold_add(&list, &sn, enc, reg->case_fold_flag,
-                                         p, q);
-          if (r != 0) goto err;
+        if (min_len != max_len) {
+          r = ONIGERR_PARSER_BUG;
+          goto err;
         }
+
+        q = p + max_len;
+        r = unravel_cf_string_alt_or_cc_add(&list, n, items, enc,
+                                            reg->case_fold_flag, p, q);
+        if (r != 0) goto err;
+        sn = NULL_NODE;
       }
     }
 
@@ -4428,7 +5134,7 @@ unravel_case_fold_string(Node* node, regex_t* reg, int state)
 static enum BodyEmptyType
 quantifiers_memory_node_info(Node* node)
 {
-  int r = BODY_IS_EMPTY_POSSIBILITY;
+  int r = BODY_MAY_BE_EMPTY;
 
   switch (NODE_TYPE(node)) {
   case NODE_LIST:
@@ -4445,7 +5151,7 @@ quantifiers_memory_node_info(Node* node)
 #ifdef USE_CALL
   case NODE_CALL:
     if (NODE_IS_RECURSION(node)) {
-      return BODY_IS_EMPTY_POSSIBILITY_REC; /* tiny version */
+      return BODY_MAY_BE_EMPTY_REC; /* tiny version */
     }
     else
       r = quantifiers_memory_node_info(NODE_BODY(node));
@@ -4467,9 +5173,9 @@ quantifiers_memory_node_info(Node* node)
       switch (en->type) {
       case BAG_MEMORY:
         if (NODE_IS_RECURSION(node)) {
-          return BODY_IS_EMPTY_POSSIBILITY_REC;
+          return BODY_MAY_BE_EMPTY_REC;
         }
-        return BODY_IS_EMPTY_POSSIBILITY_MEM;
+        return BODY_MAY_BE_EMPTY_MEM;
         break;
 
       case BAG_OPTION:
@@ -4524,7 +5230,7 @@ tune_call_node_call(CallNode* cn, ScanEnv* env, int state)
 
     if (env->num_named > 0 &&
         IS_SYNTAX_BV(env->syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
-        ! ONIG_IS_OPTION_ON(env->options, ONIG_OPTION_CAPTURE_GROUP)) {
+        ! OPTON_CAPTURE_GROUP(env->options)) {
       return ONIGERR_NUMBERED_BACKREF_OR_CALL_NOT_ALLOWED;
     }
 
@@ -4935,35 +5641,12 @@ tune_called_state(Node* node, int state)
 #endif  /* USE_CALL */
 
 
-static int tune_tree(Node* node, regex_t* reg, int state, ScanEnv* env);
-
 #ifdef __GNUC__
 __inline
 #endif
 static int
 tune_anchor(Node* node, regex_t* reg, int state, ScanEnv* env)
 {
-/* allowed node types in look-behind */
-#define ALLOWED_TYPE_IN_LB \
-  ( NODE_BIT_LIST | NODE_BIT_ALT | NODE_BIT_STRING | NODE_BIT_CCLASS \
-  | NODE_BIT_CTYPE | NODE_BIT_ANCHOR | NODE_BIT_BAG | NODE_BIT_QUANT \
-  | NODE_BIT_CALL | NODE_BIT_GIMMICK)
-
-#define ALLOWED_BAG_IN_LB       ( 1<<BAG_MEMORY | 1<<BAG_OPTION | 1<<BAG_IF_ELSE )
-#define ALLOWED_BAG_IN_LB_NOT   ( 1<<BAG_OPTION | 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 )
-
   int r;
   AnchorNode* an = ANCHOR_(node);
 
@@ -4976,28 +5659,8 @@ tune_anchor(Node* node, regex_t* reg, int state, ScanEnv* env)
     break;
 
   case ANCR_LOOK_BEHIND:
-    {
-      r = check_type_tree(NODE_ANCHOR_BODY(an), ALLOWED_TYPE_IN_LB,
-                          ALLOWED_BAG_IN_LB, ALLOWED_ANCHOR_IN_LB);
-      if (r < 0) return r;
-      if (r > 0) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
-      r = tune_tree(NODE_ANCHOR_BODY(an), reg, (state|IN_LOOK_BEHIND), env);
-      if (r != 0) return r;
-      r = tune_look_behind(node, reg, env);
-    }
-    break;
-
   case ANCR_LOOK_BEHIND_NOT:
-    {
-      r = check_type_tree(NODE_ANCHOR_BODY(an), ALLOWED_TYPE_IN_LB,
-                          ALLOWED_BAG_IN_LB_NOT, ALLOWED_ANCHOR_IN_LB_NOT);
-      if (r < 0) return r;
-      if (r > 0) return ONIGERR_INVALID_LOOK_BEHIND_PATTERN;
-      r = tune_tree(NODE_ANCHOR_BODY(an), reg, (state|IN_NOT|IN_LOOK_BEHIND),
-                    env);
-      if (r != 0) return r;
-      r = tune_look_behind(node, reg, env);
-    }
+    r = tune_look_behind(node, reg, state, env);
     break;
 
   default:
@@ -5015,7 +5678,6 @@ static int
 tune_quant(Node* node, regex_t* reg, int state, ScanEnv* env)
 {
   int r;
-  OnigLen d;
   QuantNode* qn = QUANT_(node);
   Node* body = NODE_BODY(node);
 
@@ -5027,12 +5689,12 @@ tune_quant(Node* node, regex_t* reg, int state, ScanEnv* env)
   }
 
   if (IS_INFINITE_REPEAT(qn->upper) || qn->upper >= 1) {
-    d = tree_min_len(body, env);
+    OnigLen d = node_min_byte_len(body, env);
     if (d == 0) {
 #ifdef USE_STUBBORN_CHECK_CAPTURES_IN_EMPTY_REPEAT
       qn->emptiness = quantifiers_memory_node_info(body);
 #else
-      qn->emptiness = BODY_IS_EMPTY_POSSIBILITY;
+      qn->emptiness = BODY_MAY_BE_EMPTY;
 #endif
     }
   }
@@ -5054,7 +5716,7 @@ tune_quant(Node* node, regex_t* reg, int state, ScanEnv* env)
 
       if (len * qn->lower <= EXPAND_STRING_MAX_LENGTH) {
         int i, n = qn->lower;
-        node_conv_to_str_node(node, STR_(body)->flag);
+        node_conv_to_str_node(node, body);
         for (i = 0; i < n; i++) {
           r = node_str_node_cat(node, body);
           if (r != 0) return r;
@@ -5074,7 +5736,7 @@ tune_quant(Node* node, regex_t* reg, int state, ScanEnv* env)
       }
     }
     else {
-      qn->head_exact = get_head_value_node(NODE_BODY(node), 1, reg);
+      qn->head_exact = get_tree_head_literal(NODE_BODY(node), 1, reg);
     }
   }
 
@@ -5115,7 +5777,7 @@ tune_tree(Node* node, regex_t* reg, int state, ScanEnv* env)
     break;
 
   case NODE_STRING:
-    if (IS_IGNORECASE(reg->options) && !NODE_STRING_IS_CRUDE(node)) {
+    if (NODE_IS_IGNORECASE(node) && ! NODE_STRING_IS_CRUDE(node)) {
       r = unravel_case_fold_string(node, reg, state);
     }
     break;
@@ -5299,14 +5961,8 @@ set_sunday_quick_search_or_bmh_skip_table(regex_t* reg, int case_expand,
 #endif
 
 typedef struct {
-  OnigLen min;  /* min byte length */
-  OnigLen max;  /* max byte length */
-} MinMax;
-
-typedef struct {
-  MinMax           mm;
+  MinMaxLen        mm;
   OnigEncoding     enc;
-  OnigOptionType   options;
   OnigCaseFoldType case_fold_flag;
   ScanEnv*         scan_env;
 } OptEnv;
@@ -5317,23 +5973,22 @@ typedef struct {
 } OptAnc;
 
 typedef struct {
-  MinMax     mm;   /* position */
+  MinMaxLen  mm;   /* position */
   OptAnc     anc;
   int        reach_end;
-  int        case_fold;
   int        len;
   UChar      s[OPT_EXACT_MAXLEN];
 } OptStr;
 
 typedef struct {
-  MinMax    mm;     /* position */
+  MinMaxLen mm;     /* position */
   OptAnc    anc;
   int       value;  /* weighted value */
   UChar     map[CHAR_MAP_SIZE];
 } OptMap;
 
 typedef struct {
-  MinMax  len;
+  MinMaxLen len;
   OptAnc  anc;
   OptStr  sb;     /* boundary */
   OptStr  sm;     /* middle */
@@ -5367,7 +6022,7 @@ map_position_value(OnigEncoding enc, int i)
 }
 
 static int
-distance_value(MinMax* mm)
+distance_value(MinMaxLen* mm)
 {
   /* 1000 / (min-max-dist + 1) */
   static const short int dist_vals[] = {
@@ -5396,7 +6051,7 @@ distance_value(MinMax* mm)
 }
 
 static int
-comp_distance_value(MinMax* d1, MinMax* d2, int v1, int v2)
+comp_distance_value(MinMaxLen* d1, MinMaxLen* d2, int v1, int v2)
 {
   if (v2 <= 0) return -1;
   if (v1 <= 0) return  1;
@@ -5412,46 +6067,6 @@ comp_distance_value(MinMax* d1, MinMax* d2, int v1, int v2)
   return 0;
 }
 
-static int
-is_equal_mml(MinMax* a, MinMax* b)
-{
-  return a->min == b->min && a->max == b->max;
-}
-
-static void
-set_mml(MinMax* l, OnigLen min, OnigLen max)
-{
-  l->min = min;
-  l->max = max;
-}
-
-static void
-clear_mml(MinMax* l)
-{
-  l->min = l->max = 0;
-}
-
-static void
-copy_mml(MinMax* to, MinMax* from)
-{
-  to->min = from->min;
-  to->max = from->max;
-}
-
-static void
-add_mml(MinMax* to, MinMax* from)
-{
-  to->min = distance_add(to->min, from->min);
-  to->max = distance_add(to->max, from->max);
-}
-
-static void
-alt_merge_mml(MinMax* to, MinMax* from)
-{
-  if (to->min > from->min) to->min = from->min;
-  if (to->max < from->max) to->max = from->max;
-}
-
 static void
 copy_opt_env(OptEnv* to, OptEnv* from)
 {
@@ -5543,12 +6158,11 @@ is_full_opt_exact(OptStr* e)
 static void
 clear_opt_exact(OptStr* e)
 {
-  clear_mml(&e->mm);
+  mml_clear(&e->mm);
   clear_opt_anc_info(&e->anc);
-  e->reach_end      = 0;
-  e->case_fold      = 0;
-  e->len            = 0;
-  e->s[0]           = '\0';
+  e->reach_end = 0;
+  e->len       = 0;
+  e->s[0]      = '\0';
 }
 
 static void
@@ -5564,14 +6178,6 @@ concat_opt_exact(OptStr* to, OptStr* add, OnigEncoding enc)
   UChar *p, *end;
   OptAnc tanc;
 
-  if (add->case_fold != 0) {
-    if (! to->case_fold) {
-      if (to->len > 1 || to->len >= add->len) return 0;  /* avoid */
-
-      to->case_fold = 1;
-    }
-  }
-
   r = 0;
   p = add->s;
   end = p + add->len;
@@ -5610,7 +6216,7 @@ concat_opt_exact_str(OptStr* to, UChar* s, UChar* end, OnigEncoding enc)
 
   to->len = i;
 
-  if (p >= end && to->len == (int )(end - s))
+  if (p >= end)
     to->reach_end = 1;
 }
 
@@ -5624,7 +6230,7 @@ alt_merge_opt_exact(OptStr* to, OptStr* add, OptEnv* env)
     return ;
   }
 
-  if (! is_equal_mml(&to->mm, &add->mm)) {
+  if (! mml_is_equal(&to->mm, &add->mm)) {
     clear_opt_exact(to);
     return ;
   }
@@ -5644,8 +6250,6 @@ alt_merge_opt_exact(OptStr* to, OptStr* add, OptEnv* env)
     to->reach_end = 0;
   }
   to->len = i;
-  if (add->case_fold != 0)
-    to->case_fold = 1;
 
   alt_merge_opt_anc_info(&to->anc, &add->anc);
   if (! to->reach_end) to->anc.right = 0;
@@ -5675,8 +6279,8 @@ select_opt_exact(OnigEncoding enc, OptStr* now, OptStr* alt)
     if (alt->len > 1) va += 5;
   }
 
-  if (now->case_fold == 0) vn *= 2;
-  if (alt->case_fold == 0) va *= 2;
+  vn *= 2;
+  va *= 2;
 
   if (comp_distance_value(&now->mm, &alt->mm, vn, va) > 0)
     copy_opt_exact(now, alt);
@@ -5725,28 +6329,6 @@ add_char_opt_map(OptMap* m, UChar c, OnigEncoding enc)
   }
 }
 
-static int
-add_char_amb_opt_map(OptMap* map, UChar* p, UChar* end,
-                     OnigEncoding enc, OnigCaseFoldType fold_flag)
-{
-  OnigCaseFoldCodeItem items[ONIGENC_GET_CASE_FOLD_CODES_MAX_NUM];
-  UChar buf[ONIGENC_CODE_TO_MBC_MAXLEN];
-  int i, n;
-
-  add_char_opt_map(map, p[0], enc);
-
-  fold_flag = DISABLE_CASE_FOLD_MULTI_CHAR(fold_flag);
-  n = ONIGENC_GET_CASE_FOLD_CODES_BY_STR(enc, fold_flag, p, end, items);
-  if (n < 0) return n;
-
-  for (i = 0; i < n; i++) {
-    ONIGENC_CODE_TO_MBC(enc, items[i].code[0], buf);
-    add_char_opt_map(map, buf[0], enc);
-  }
-
-  return 0;
-}
-
 static void
 select_opt_map(OptMap* now, OptMap* alt)
 {
@@ -5775,12 +6357,7 @@ comp_opt_exact_or_map(OptStr* e, OptMap* m)
 
   if (m->value <= 0) return -1;
 
-  if (e->case_fold != 0) {
-    case_value = 1;
-  }
-  else
-    case_value = 3;
-
+  case_value = 3;
   ae = COMP_EM_BASE * e->len * case_value;
   am = COMP_EM_BASE * 5 * 2 / m->value;
   return comp_distance_value(&e->mm, &m->mm, ae, am);
@@ -5791,14 +6368,14 @@ alt_merge_opt_map(OnigEncoding enc, OptMap* to, OptMap* add)
 {
   int i, val;
 
-  /* if (! is_equal_mml(&to->mm, &add->mm)) return ; */
+  /* if (! mml_is_equal(&to->mm, &add->mm)) return ; */
   if (to->value == 0) return ;
   if (add->value == 0 || to->mm.max < add->mm.min) {
     clear_opt_map(to);
     return ;
   }
 
-  alt_merge_mml(&to->mm, &add->mm);
+  mml_alt_merge(&to->mm, &add->mm);
 
   val = 0;
   for (i = 0; i < CHAR_MAP_SIZE; i++) {
@@ -5814,17 +6391,17 @@ alt_merge_opt_map(OnigEncoding enc, OptMap* to, OptMap* add)
 }
 
 static void
-set_bound_node_opt_info(OptNode* opt, MinMax* plen)
+set_bound_node_opt_info(OptNode* opt, MinMaxLen* plen)
 {
-  copy_mml(&(opt->sb.mm),  plen);
-  copy_mml(&(opt->spr.mm), plen);
-  copy_mml(&(opt->map.mm), plen);
+  mml_copy(&(opt->sb.mm),  plen);
+  mml_copy(&(opt->spr.mm), plen);
+  mml_copy(&(opt->map.mm), plen);
 }
 
 static void
 clear_node_opt_info(OptNode* opt)
 {
-  clear_mml(&opt->len);
+  mml_clear(&opt->len);
   clear_opt_anc_info(&opt->anc);
   clear_opt_exact(&opt->sb);
   clear_opt_exact(&opt->sm);
@@ -5889,7 +6466,7 @@ concat_left_node_opt_info(OnigEncoding enc, OptNode* to, OptNode* add)
   }
 
   select_opt_map(&to->map, &add->map);
-  add_mml(&to->len, &add->len);
+  mml_add(&to->len, &add->len);
 }
 
 static void
@@ -5901,7 +6478,7 @@ alt_merge_node_opt_info(OptNode* to, OptNode* add, OptEnv* env)
   alt_merge_opt_exact(&to->spr, &add->spr, env);
   alt_merge_opt_map(env->enc, &to->map, &add->map);
 
-  alt_merge_mml(&to->len, &add->len);
+  mml_alt_merge(&to->len, &add->len);
 }
 
 
@@ -5930,7 +6507,7 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
       do {
         r = optimize_nodes(NODE_CAR(nd), &xo, &nenv);
         if (r == 0) {
-          add_mml(&nenv.mm, &xo.len);
+          mml_add(&nenv.mm, &xo.len);
           concat_left_node_opt_info(enc, opt, &xo);
         }
       } while (r == 0 && IS_NOT_NULL(nd = NODE_CDR(nd)));
@@ -5956,29 +6533,11 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
       StrNode* sn = STR_(node);
       int slen = (int )(sn->end - sn->s);
 
-      if (! NODE_STRING_IS_CASE_FOLD_MATCH(node)) {
-        concat_opt_exact_str(&opt->sb, sn->s, sn->end, enc);
-        if (slen > 0) {
-          add_char_opt_map(&opt->map, *(sn->s), enc);
-        }
-        set_mml(&opt->len, slen, slen);
-      }
-      else {
-        int max, min;
-
-        concat_opt_exact_str(&opt->sb, sn->s, sn->end, enc);
-        opt->sb.case_fold = 1;
-
-        if (slen > 0) {
-          r = add_char_amb_opt_map(&opt->map, sn->s, sn->end,
-                                   enc, env->case_fold_flag);
-          if (r != 0) break;
-        }
-
-        max = slen;
-        min = sn->case_min_len * ONIGENC_MBC_MINLEN(enc);
-        set_mml(&opt->len, min, max);
+      concat_opt_exact_str(&opt->sb, sn->s, sn->end, enc);
+      if (slen > 0) {
+        add_char_opt_map(&opt->map, *(sn->s), enc);
       }
+      mml_set_min_max(&opt->len, slen, slen);
     }
     break;
 
@@ -5993,7 +6552,7 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
         OnigLen min = ONIGENC_MBC_MINLEN(enc);
         OnigLen max = ONIGENC_MBC_MAXLEN_DIST(enc);
 
-        set_mml(&opt->len, min, max);
+        mml_set_min_max(&opt->len, min, max);
       }
       else {
         for (i = 0; i < SINGLE_BYTE_SIZE; i++) {
@@ -6002,7 +6561,7 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
             add_char_opt_map(&opt->map, (UChar )i, enc);
           }
         }
-        set_mml(&opt->len, 1, 1);
+        mml_set_min_max(&opt->len, 1, 1);
       }
     }
     break;
@@ -6046,7 +6605,7 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
       else {
         min = ONIGENC_MBC_MINLEN(enc);
       }
-      set_mml(&opt->len, min, max);
+      mml_set_min_max(&opt->len, min, max);
     }
     break;
 
@@ -6087,37 +6646,20 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
 
   case NODE_BACKREF:
     if (! NODE_IS_CHECKER(node)) {
-      int* backs;
-      OnigLen min, max, tmin, tmax;
-      MemEnv* mem_env = SCANENV_MEMENV(env->scan_env);
-      BackRefNode* br = BACKREF_(node);
+      OnigLen min, max;
 
-      if (NODE_IS_RECURSION(node)) {
-        set_mml(&opt->len, 0, INFINITE_LEN);
-        break;
-      }
-      backs = BACKREFS_P(br);
-      min = tree_min_len(mem_env[backs[0]].mem_node, env->scan_env);
-      max = tree_max_len(mem_env[backs[0]].mem_node, env->scan_env);
-      for (i = 1; i < br->back_num; i++) {
-        tmin = tree_min_len(mem_env[backs[i]].mem_node, env->scan_env);
-        tmax = tree_max_len(mem_env[backs[i]].mem_node, env->scan_env);
-        if (min > tmin) min = tmin;
-        if (max < tmax) max = tmax;
-      }
-      set_mml(&opt->len, min, max);
+      min = node_min_byte_len(node, env->scan_env);
+      max = node_max_byte_len(node, env->scan_env);
+      mml_set_min_max(&opt->len, min, max);
     }
     break;
 
 #ifdef USE_CALL
   case NODE_CALL:
     if (NODE_IS_RECURSION(node))
-      set_mml(&opt->len, 0, INFINITE_LEN);
+      mml_set_min_max(&opt->len, 0, INFINITE_LEN);
     else {
-      OnigOptionType save = env->options;
-      env->options = BAG_(NODE_BODY(node))->o.options;
       r = optimize_nodes(NODE_BODY(node), opt, env);
-      env->options = save;
     }
     break;
 #endif
@@ -6127,6 +6669,20 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
       OnigLen min, max;
       QuantNode* qn = QUANT_(node);
 
+      /* Issue #175
+         ex. /\g<1>{0}(?<=|())/
+
+         Empty and unused nodes in look-behind is removed in
+         tune_look_behind().
+         Called group nodes are assigned to be not called if the caller side is
+         inside of zero-repetition.
+         As a result, the nodes are considered unused.
+       */
+      if (qn->upper == 0) {
+        mml_set_min_max(&opt->len, 0, 0);
+        break;
+      }
+
       r = optimize_nodes(NODE_BODY(node), &xo, env);
       if (r != 0) break;
 
@@ -6153,7 +6709,7 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
       if (IS_INFINITE_REPEAT(qn->upper)) {
         if (env->mm.max == 0 &&
             NODE_IS_ANYCHAR(NODE_BODY(node)) && qn->greedy != 0) {
-          if (IS_MULTILINE(CTYPE_OPTION(NODE_QUANT_BODY(qn), env)))
+          if (NODE_IS_MULTILINE(NODE_QUANT_BODY(qn)))
             add_opt_anc_info(&opt->anc, ANCR_ANYCHAR_INF_ML);
           else
             add_opt_anc_info(&opt->anc, ANCR_ANYCHAR_INF);
@@ -6166,7 +6722,7 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
       }
 
       min = distance_multiply(xo.len.min, qn->lower);
-      set_mml(&opt->len, min, max);
+      mml_set_min_max(&opt->len, min, max);
     }
     break;
 
@@ -6175,14 +6731,9 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
       BagNode* en = BAG_(node);
 
       switch (en->type) {
+      case BAG_STOP_BACKTRACK:
       case BAG_OPTION:
-        {
-          OnigOptionType save = env->options;
-
-          env->options = en->o.options;
-          r = optimize_nodes(NODE_BODY(node), opt, env);
-          env->options = save;
-        }
+        r = optimize_nodes(NODE_BODY(node), opt, env);
         break;
 
       case BAG_MEMORY:
@@ -6193,9 +6744,9 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
 
           min = 0;
           max = INFINITE_LEN;
-          if (NODE_IS_MIN_FIXED(node)) min = en->min_len;
-          if (NODE_IS_MAX_FIXED(node)) max = en->max_len;
-          set_mml(&opt->len, min, max);
+          if (NODE_IS_FIXED_MIN(node)) min = en->min_len;
+          if (NODE_IS_FIXED_MAX(node)) max = en->max_len;
+          mml_set_min_max(&opt->len, min, max);
         }
         else
 #endif
@@ -6208,10 +6759,6 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
           }
         break;
 
-      case BAG_STOP_BACKTRACK:
-        r = optimize_nodes(NODE_BODY(node), opt, env);
-        break;
-
       case BAG_IF_ELSE:
         {
           OptEnv nenv;
@@ -6219,7 +6766,7 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
           copy_opt_env(&nenv, env);
           r = optimize_nodes(NODE_BAG_BODY(en), &xo, &nenv);
           if (r == 0) {
-            add_mml(&nenv.mm, &xo.len);
+            mml_add(&nenv.mm, &xo.len);
             concat_left_node_opt_info(enc, opt, &xo);
             if (IS_NOT_NULL(en->te.Then)) {
               r = optimize_nodes(en->te.Then, &xo, &nenv);
@@ -6245,7 +6792,7 @@ optimize_nodes(Node* node, OptNode* opt, OptEnv* env)
 
   default:
 #ifdef ONIG_DEBUG
-    fprintf(stderr, "optimize_nodes: undefined node type %d\n", NODE_TYPE(node));
+    fprintf(DBGFP, "optimize_nodes: undefined node type %d\n", NODE_TYPE(node));
 #endif
     r = ONIGERR_TYPE_BUG;
     break;
@@ -6258,6 +6805,7 @@ static int
 set_optimize_exact(regex_t* reg, OptStr* e)
 {
   int r;
+  int allow_reverse;
 
   if (e->len == 0) return 0;
 
@@ -6266,40 +6814,28 @@ set_optimize_exact(regex_t* reg, OptStr* e)
   xmemcpy(reg->exact, e->s, e->len);
   reg->exact_end = reg->exact + e->len;
 
-  if (e->case_fold) {
-    reg->optimize = OPTIMIZE_STR_CASE_FOLD;
-  }
-  else {
-    int allow_reverse;
+  allow_reverse =
+    ONIGENC_IS_ALLOWED_REVERSE_MATCH(reg->enc, reg->exact, reg->exact_end);
 
-    allow_reverse =
-      ONIGENC_IS_ALLOWED_REVERSE_MATCH(reg->enc, reg->exact, reg->exact_end);
-
-    if (e->len >= 2 || (e->len >= 1 && allow_reverse)) {
-      r = set_sunday_quick_search_or_bmh_skip_table(reg, 0,
-                                         reg->exact, reg->exact_end,
-                                         reg->map, &(reg->map_offset));
-      if (r != 0) return r;
+  if (e->len >= 2 || (e->len >= 1 && allow_reverse)) {
+    r = set_sunday_quick_search_or_bmh_skip_table(reg, 0,
+                                                  reg->exact, reg->exact_end,
+                                                  reg->map, &(reg->map_offset));
+    if (r != 0) return r;
 
-      reg->optimize = (allow_reverse != 0
-                       ? OPTIMIZE_STR_FAST
-                       : OPTIMIZE_STR_FAST_STEP_FORWARD);
-    }
-    else {
-      reg->optimize = OPTIMIZE_STR;
-    }
+    reg->optimize = (allow_reverse != 0
+                     ? OPTIMIZE_STR_FAST
+                     : OPTIMIZE_STR_FAST_STEP_FORWARD);
+  }
+  else {
+    reg->optimize = OPTIMIZE_STR;
   }
 
   reg->dist_min = e->mm.min;
   reg->dist_max = e->mm.max;
 
   if (reg->dist_min != INFINITE_LEN) {
-    int n;
-    if (e->case_fold != 0)
-      n = 1;
-    else
-      n = (int )(reg->exact_end - reg->exact);
-
+    int n = (int )(reg->exact_end - reg->exact);
     reg->threshold_len = reg->dist_min + n;
   }
 
@@ -6319,7 +6855,7 @@ set_optimize_map(regex_t* reg, OptMap* m)
   reg->dist_max   = m->mm.max;
 
   if (reg->dist_min != INFINITE_LEN) {
-    reg->threshold_len = reg->dist_min + 1;
+    reg->threshold_len = reg->dist_min + ONIGENC_MBC_MINLEN(reg->enc);
   }
 }
 
@@ -6342,10 +6878,9 @@ set_optimize_info_from_tree(Node* node, regex_t* reg, ScanEnv* scan_env)
   OptEnv env;
 
   env.enc            = reg->enc;
-  env.options        = reg->options;
   env.case_fold_flag = reg->case_fold_flag;
   env.scan_env       = scan_env;
-  clear_mml(&env.mm);
+  mml_clear(&env.mm);
 
   r = optimize_nodes(node, &opt, &env);
   if (r != 0) return r;
@@ -6387,7 +6922,7 @@ set_optimize_info_from_tree(Node* node, regex_t* reg, ScanEnv* scan_env)
   }
 
 #if defined(ONIG_DEBUG_COMPILE) || defined(ONIG_DEBUG_MATCH)
-  print_optimize_info(stderr, reg);
+  print_optimize_info(DBGFP, reg);
 #endif
   return r;
 }
@@ -6414,8 +6949,6 @@ clear_optimize_info(regex_t* reg)
 static void print_enc_string(FILE* fp, OnigEncoding enc,
                              const UChar *s, const UChar *end)
 {
-  fprintf(fp, "\nPATTERN: /");
-
   if (ONIGENC_MBC_MINLEN(enc) > 1) {
     const UChar *p;
     OnigCodePoint code;
@@ -6515,9 +7048,8 @@ print_anchor(FILE* f, int anchor)
 static void
 print_optimize_info(FILE* f, regex_t* reg)
 {
-  static const char* on[] = { "NONE", "STR",
-                              "STR_FAST", "STR_FAST_STEP_FORWARD",
-                              "STR_CASE_FOLD", "MAP" };
+  static const char* on[] =
+    { "NONE", "STR", "STR_FAST", "STR_FAST_STEP_FORWARD", "MAP" };
 
   fprintf(f, "optimize: %s\n", on[reg->optimize]);
   fprintf(f, "  anchor: "); print_anchor(f, reg->anchor);
@@ -6537,7 +7069,12 @@ print_optimize_info(FILE* f, regex_t* reg)
     for (p = reg->exact; p < reg->exact_end; p++) {
       fputc(*p, f);
     }
-    fprintf(f, "]: length: %ld\n", (reg->exact_end - reg->exact));
+    fprintf(f, "]: length: %ld, dmin: %u, ",
+            (reg->exact_end - reg->exact), reg->dist_min);
+    if (reg->dist_max == INFINITE_LEN)
+      fprintf(f, "dmax: inf.\n");
+    else
+      fprintf(f, "dmax: %u\n", reg->dist_max);
   }
   else if (reg->optimize & OPTIMIZE_MAP) {
     int c, i, n = 0;
@@ -6545,7 +7082,8 @@ print_optimize_info(FILE* f, regex_t* reg)
     for (i = 0; i < CHAR_MAP_SIZE; i++)
       if (reg->map[i]) n++;
 
-    fprintf(f, "map: n=%d\n", n);
+    fprintf(f, "map: n=%d, dmin: %u, dmax: %u\n",
+            n, reg->dist_min, reg->dist_max);
     if (n > 0) {
       c = 0;
       fputc('[', f);
@@ -6680,7 +7218,8 @@ onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
   }
 
 #ifdef ONIG_DEBUG
-  print_enc_string(stderr, reg->enc, pattern, pattern_end);
+  fprintf(DBGFP, "\nPATTERN: /");
+  print_enc_string(DBGFP, reg->enc, pattern, pattern_end);
 #endif
 
   if (reg->ops_alloc == 0) {
@@ -6708,7 +7247,7 @@ onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
   /* mixed use named group and no-named group */
   if (scan_env.num_named > 0 &&
       IS_SYNTAX_BV(scan_env.syntax, ONIG_SYN_CAPTURE_ONLY_NAMED_GROUP) &&
-      ! ONIG_IS_OPTION_ON(reg->options, ONIG_OPTION_CAPTURE_GROUP)) {
+      ! OPTON_CAPTURE_GROUP(reg->options)) {
     if (scan_env.num_named != scan_env.num_mem)
       r = disable_noname_group_capture(&root, reg, &scan_env);
     else
@@ -6741,10 +7280,10 @@ onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
 #endif
 
 #ifdef ONIG_DEBUG_PARSE
-  fprintf(stderr, "MAX PARSE DEPTH: %d\n", scan_env.max_parse_depth);
-  fprintf(stderr, "TREE (parsed)\n");
-  print_tree(stderr, root);
-  fprintf(stderr, "\n");
+  fprintf(DBGFP, "MAX PARSE DEPTH: %d\n", scan_env.max_parse_depth);
+  fprintf(DBGFP, "TREE (parsed)\n");
+  print_tree(DBGFP, root);
+  fprintf(DBGFP, "\n");
 #endif
 
   r = tune_tree(root, reg, 0, &scan_env);
@@ -6758,13 +7297,13 @@ onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
   }
 
 #ifdef ONIG_DEBUG_PARSE
-  fprintf(stderr, "TREE (after tune)\n");
-  print_tree(stderr, root);
-  fprintf(stderr, "\n");
+  fprintf(DBGFP, "TREE (after tune)\n");
+  print_tree(DBGFP, root);
+  fprintf(DBGFP, "\n");
 #endif
 
-  reg->capture_history  = scan_env.cap_history;
-  reg->push_mem_start   = scan_env.backtrack_mem | scan_env.cap_history;
+  reg->capture_history = scan_env.cap_history;
+  reg->push_mem_start  = scan_env.backtrack_mem | scan_env.cap_history;
 
 #ifdef USE_CALLOUT
   if (IS_NOT_NULL(reg->extp) && reg->extp->callout_num != 0) {
@@ -6804,6 +7343,7 @@ onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
 
       COP(reg)->update_var.type = UPDATE_VAR_KEEP_FROM_STACK_LAST;
       COP(reg)->update_var.id   = 0; /* not used */
+      COP(reg)->update_var.clear = FALSE;
     }
 
     r = add_op(reg, OP_END);
@@ -6827,6 +7367,9 @@ onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
 #ifdef USE_CALLOUT
         || (IS_NOT_NULL(reg->extp) && reg->extp->callout_num != 0)
 #endif
+#ifdef USE_CALL
+        || scan_env.num_call > 0
+#endif
         )
       reg->stack_pop_level = STACK_POP_LEVEL_ALL;
     else {
@@ -6847,8 +7390,8 @@ onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
   onig_node_free(root);
 
 #ifdef ONIG_DEBUG_COMPILE
-  onig_print_names(stderr, reg);
-  onig_print_compiled_byte_code_list(stderr, reg);
+  onig_print_names(DBGFP, reg);
+  onig_print_compiled_byte_code_list(DBGFP, reg);
 #endif
 
 #ifdef USE_DIRECT_THREADED_CODE
@@ -6920,20 +7463,18 @@ onig_reg_init(regex_t* reg, OnigOptionType option, OnigCaseFoldType case_fold_fl
   else
     option |= syntax->options;
 
-  (reg)->enc              = enc;
-  (reg)->options          = option;
-  (reg)->syntax           = syntax;
-  (reg)->optimize         = 0;
-  (reg)->exact            = (UChar* )NULL;
-  (reg)->extp             = (RegexExt* )NULL;
-
-  (reg)->ops              = (Operation* )NULL;
-  (reg)->ops_curr         = (Operation* )NULL;
-  (reg)->ops_used         = 0;
-  (reg)->ops_alloc        = 0;
-  (reg)->name_table       = (void* )NULL;
-
-  (reg)->case_fold_flag   = case_fold_flag;
+  (reg)->enc            = enc;
+  (reg)->options        = option;
+  (reg)->syntax         = syntax;
+  (reg)->optimize       = 0;
+  (reg)->exact          = (UChar* )NULL;
+  (reg)->extp           = (RegexExt* )NULL;
+  (reg)->ops            = (Operation* )NULL;
+  (reg)->ops_curr       = (Operation* )NULL;
+  (reg)->ops_used       = 0;
+  (reg)->ops_alloc      = 0;
+  (reg)->name_table     = (void* )NULL;
+  (reg)->case_fold_flag = case_fold_flag;
   return 0;
 }
 
@@ -7171,8 +7712,8 @@ print_indent_tree(FILE* f, Node* node, int indent)
 
       if (NODE_STRING_IS_CRUDE(node))
         mode = "-crude";
-      else if (NODE_STRING_IS_CASE_FOLD_MATCH(node))
-        mode = "-case_fold_match";
+      else if (NODE_IS_IGNORECASE(node))
+        mode = "-ignorecase";
       else
         mode = "";
 
@@ -7208,7 +7749,7 @@ print_indent_tree(FILE* f, Node* node, int indent)
     fprintf(f, "<ctype:%p> ", node);
     switch (CTYPE_(node)->ctype) {
     case CTYPE_ANYCHAR:
-      fprintf(f, "<anychar:%p>", node);
+      fprintf(f, "anychar");
       break;
 
     case ONIGENC_CTYPE_WORD:
@@ -7295,9 +7836,10 @@ print_indent_tree(FILE* f, Node* node, int indent)
 #endif
 
   case NODE_QUANT:
-    fprintf(f, "<quantifier:%p>{%d,%d}%s\n", node,
+    fprintf(f, "<quantifier:%p>{%d,%d}%s%s\n", node,
             QUANT_(node)->lower, QUANT_(node)->upper,
-            (QUANT_(node)->greedy ? "" : "?"));
+            (QUANT_(node)->greedy ? "" : "?"),
+            QUANT_(node)->include_referred == 0 ? "" : " referred");
     print_indent_tree(f, NODE_BODY(node), indent + add);
     break;
 
@@ -7337,6 +7879,10 @@ print_indent_tree(FILE* f, Node* node, int indent)
       break;
     case BAG_MEMORY:
       fprintf(f, "memory:%d", BAG_(node)->m.regnum);
+      if (NODE_IS_CALLED(node))
+        fprintf(f, ", called");
+      if (NODE_IS_FIXED_ADDR(node))
+        fprintf(f, ", fixed-addr");
       break;
     case BAG_STOP_BACKTRACK:
       fprintf(f, "stop-bt");