diff -urNp libc-/posix/regex_internal.h libc/posix/regex_internal.h
--- libc-/posix/regex_internal.h	2002-11-21 20:53:56.000000000 +0900
+++ libc/posix/regex_internal.h	2002-11-21 20:58:01.000000000 +0900
@@ -405,6 +405,33 @@ struct re_state_table_entry
   re_dfastate_t **array;
 };
 
+typedef struct
+{
+  int next_idx;
+  int alloc;
+  re_dfastate_t **array;
+} state_array_t;
+
+typedef struct
+{
+  int node;
+  int str_idx;
+  state_array_t path;
+  re_node_set *limits;
+} re_sub_match_last_t;
+
+typedef struct
+{
+  int str_idx;
+  int node;
+  int next_last_offset;
+  int alasts;
+  int nlasts;
+  re_sub_match_last_t **lasts;
+  state_array_t *path;
+  re_node_set *limits;
+} re_sub_match_top_t;
+
 struct re_backref_cache_entry
 {
   int node;
@@ -412,6 +439,8 @@ struct re_backref_cache_entry
   int subexp_from;
   int subexp_to;
   int flag;
+  re_sub_match_top_t *top;
+  re_sub_match_last_t *last;
 };
 
 typedef struct
@@ -431,6 +460,9 @@ typedef struct
   int abkref_ents;
   struct re_backref_cache_entry *bkref_ents;
   int max_mb_elem_len;
+  int nsub_tops;
+  int asub_tops;
+  re_sub_match_top_t **sub_tops;
 } re_match_context_t;
 
 typedef struct
diff -urNp libc-/posix/regexec.c libc/posix/regexec.c
--- libc-/posix/regexec.c	2002-11-21 20:53:49.000000000 +0900
+++ libc/posix/regexec.c	2002-11-21 20:58:55.000000000 +0900
@@ -47,8 +47,15 @@ static reg_errcode_t match_ctx_init (re_
 				     re_string_t *input, int n);
 static void match_ctx_free (re_match_context_t *cache);
 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
-					  int str_idx, int from, int to);
+					  int str_idx, int from, int to,
+					  re_sub_match_top_t *top,
+					  re_sub_match_last_t *last);
+static int search_cur_bkref_entry (re_match_context_t *mctx, int str_idx);
 static void match_ctx_clear_flag (re_match_context_t *mctx);
+static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, int node,
+					   int str_idx);
+static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
+						   int node, int str_idx);
 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
 			   re_dfastate_t **limited_sts, int last_node,
 			   int last_str_idx, int check_subexp);
@@ -72,6 +79,8 @@ static inline re_dfastate_t *acquire_ini
 							 const regex_t *preg,
 							 const re_match_context_t *mctx,
 							 int idx);
+static reg_errcode_t prune_impossible_nodes (const regex_t *preg,
+					     re_match_context_t *mctx);
 static int check_matching (const regex_t *preg, re_match_context_t *mctx,
 			   int fl_search, int fl_longest_match);
 static int check_halt_node_context (const re_dfa_t *dfa, int node,
@@ -129,10 +138,6 @@ static reg_errcode_t check_subexp_limits
 					  re_node_set *limits,
 					  struct re_backref_cache_entry *bkref_ents,
 					  int str_idx);
-static reg_errcode_t search_subexp (const regex_t *preg,
-				    re_match_context_t *mctx,
-				    re_sift_context_t *sctx, int str_idx,
-				    re_node_set *dest_nodes);
 static reg_errcode_t sift_states_bkref (const regex_t *preg,
 					re_match_context_t *mctx,
 					re_sift_context_t *sctx,
@@ -144,6 +149,10 @@ static reg_errcode_t merge_state_array (
 static re_dfastate_t *transit_state (reg_errcode_t *err, const regex_t *preg,
 				     re_match_context_t *mctx,
 				     re_dfastate_t *state, int fl_search);
+static reg_errcode_t check_subexp_matching_top (re_dfa_t *dfa,
+						re_match_context_t *mctx,
+						re_node_set *cur_nodes,
+						int str_idx);
 static re_dfastate_t *transit_state_sb (reg_errcode_t *err, const regex_t *preg,
 					re_dfastate_t *pstate,
 					int fl_search,
@@ -158,8 +167,32 @@ static reg_errcode_t transit_state_bkref
 					  re_match_context_t *mctx);
 static reg_errcode_t transit_state_bkref_loop (const regex_t *preg,
 					       re_node_set *nodes,
-					       re_dfastate_t **work_state_log,
 					       re_match_context_t *mctx);
+static reg_errcode_t get_subexp (const regex_t *preg, re_match_context_t *mctx,
+				 int bkref_node,
+				 int bkref_str_idx, int subexp_idx);
+static reg_errcode_t get_subexp_sub (const regex_t *preg,
+				     re_match_context_t *mctx,
+				     re_sub_match_top_t *sub_top,
+				     re_sub_match_last_t *sub_last,
+				     int bkref_node, int bkref_str,
+				     int subexp_idx);
+static int find_subexp_node (re_dfa_t *dfa, re_node_set *nodes,
+			     int subexp_idx, int fl_open);
+static reg_errcode_t check_arrival (const regex_t *preg,
+				    re_match_context_t *mctx,
+				    re_sub_match_top_t *sub_top,
+				    re_sub_match_last_t *sub_last,
+				    int bkref_node, int bkref_str);
+static reg_errcode_t expand_eclosures (re_dfa_t *dfa, re_node_set *cur_nodes,
+				       int ex_subexp, int fl_open);
+static reg_errcode_t expand_bkref_cache (const regex_t *preg,
+					 re_match_context_t *mctx,
+					 re_sub_match_top_t *sub_top,
+					 re_sub_match_last_t *sub_last,
+					 re_node_set *cur_nodes, int cur_str,
+					 int last_str, int ex_subexp,
+					 int fl_open);
 static re_dfastate_t **build_trtable (const regex_t *dfa,
 				      const re_dfastate_t *state,
 				      int fl_search);
@@ -590,7 +623,7 @@ re_search_internal (preg, string, length
   memset (&mctx, '\0', sizeof (re_match_context_t));
 
   /* We must check the longest matching, if nmatch > 0.  */
-  fl_longest_match = (nmatch != 0);
+  fl_longest_match = (nmatch != 0 || dfa->nbackref);
 
   err = re_string_allocate (&input, string, length, dfa->nodes_len + 1,
 			    preg->translate, preg->syntax & RE_ICASE);
@@ -738,10 +771,28 @@ re_search_internal (preg, string, length
 		  goto free_return;
 		}
 	      else
-		break; /* We found a matching.  */
+		{
+		  mctx.match_last = match_last;
+		  if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
+		    {
+		      re_dfastate_t *pstate = mctx.state_log[match_last];
+		      mctx.last_node = check_halt_state_context (preg, pstate,
+								 &mctx, match_last);
+		    }
+		  if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
+		      || dfa->nbackref)
+		    {
+		      err = prune_impossible_nodes (preg, &mctx);
+		      if (err == REG_NOERROR)
+			break;
+		      if (BE (err != REG_NOMATCH, 0))
+			goto free_return;
+		    }
+		  else
+		    break; /* We found a matching.  */
+		}
 	    }
 	}
-
       /* Update counter.  */
       match_first += incr;
       if (match_first < left_lim || right_lim < match_first)
@@ -759,66 +810,10 @@ re_search_internal (preg, string, length
 
       /* Set the points where matching start/end.  */
       pmatch[0].rm_so = 0;
-      mctx.match_last = pmatch[0].rm_eo = match_last;
+      pmatch[0].rm_eo = mctx.match_last;
 
       if (!preg->no_sub && nmatch > 1)
 	{
-	  /* We need the ranges of all the subexpressions.  */
-	  int halt_node;
-	  re_dfastate_t **sifted_states;
-	  re_dfastate_t **lim_states = NULL;
-	  re_dfastate_t *pstate = mctx.state_log[match_last];
-	  re_sift_context_t sctx;
-#ifdef DEBUG
-	  assert (mctx.state_log != NULL);
-#endif
-	  halt_node = check_halt_state_context (preg, pstate, &mctx,
-						match_last);
-	  if (dfa->has_plural_match)
-	    {
-	      match_ctx_clear_flag (&mctx);
-	      sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
-	      if (BE (sifted_states == NULL, 0))
-		{
-		  err = REG_ESPACE;
-		  goto free_return;
-		}
-	      if (dfa->nbackref)
-		{
-		  lim_states = calloc (sizeof (re_dfastate_t *),
-				       match_last + 1);
-		  if (BE (lim_states == NULL, 0))
-		    {
-		      re_free (sifted_states);
-		      err = REG_ESPACE;
-		      goto free_return;
-		    }
-		}
-	      sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
-			     mctx.match_last, 0);
-	      err = sift_states_backward (preg, &mctx, &sctx);
-	      re_node_set_free (&sctx.limits);
-	      if (BE (err != REG_NOERROR, 0))
-		{
-		  re_free (sifted_states);
-		  re_free (lim_states);
-		  goto free_return;
-		}
-	      if (lim_states != NULL)
-		{
-		  err = merge_state_array (dfa, sifted_states, lim_states,
-					   match_last + 1);
-		  re_free (lim_states);
-		  if (BE (err != REG_NOERROR, 0))
-		    {
-		      re_free (sifted_states);
-		      goto free_return;
-		    }
-		}
-	      re_free (mctx.state_log);
-	      mctx.state_log = sifted_states;
-	    }
-	  mctx.last_node = halt_node;
 	  err = set_regs (preg, &mctx, nmatch, pmatch,
 			  dfa->has_plural_match && dfa->nbackref > 0);
 	  if (BE (err != REG_NOERROR, 0))
@@ -843,6 +838,92 @@ re_search_internal (preg, string, length
   return err;
 }
 
+static reg_errcode_t
+prune_impossible_nodes (preg, mctx)
+     const regex_t *preg;
+     re_match_context_t *mctx;
+{
+  int halt_node, match_last;
+  reg_errcode_t ret;
+  re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
+  re_dfastate_t **sifted_states;
+  re_dfastate_t **lim_states = NULL;
+  re_sift_context_t sctx;
+#ifdef DEBUG
+  assert (mctx->state_log != NULL);
+#endif
+  match_last = mctx->match_last;
+  halt_node = mctx->last_node;
+  sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
+  if (BE (sifted_states == NULL, 0))
+    {
+      ret = REG_ESPACE;
+      goto free_return;
+    }
+  if (dfa->nbackref)
+    {
+      lim_states = re_malloc (re_dfastate_t *, match_last + 1);
+      if (BE (lim_states == NULL, 0))
+	{
+	  ret = REG_ESPACE;
+	  goto free_return;
+	}
+      while (1)
+	{
+	  memset (lim_states, '\0',
+		  sizeof (re_dfastate_t *) * (match_last + 1));
+	  match_ctx_clear_flag (mctx);
+	  sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
+			 match_last, 0);
+	  START_TIMER
+	    ret = sift_states_backward (preg, mctx, &sctx);
+	  STOP_TIMER
+	  re_node_set_free (&sctx.limits);
+	  if (BE (ret != REG_NOERROR, 0))
+	      goto free_return;
+	  if (sifted_states[0] != NULL || lim_states[0] != NULL)
+	    break;
+	  do
+	    {
+	      --match_last;
+	      if (match_last < 0)
+		{
+		  ret = REG_NOMATCH;
+		  goto free_return;
+		}
+	    } while (!mctx->state_log[match_last]->halt);
+	  halt_node = check_halt_state_context (preg,
+						mctx->state_log[match_last],
+						mctx, match_last);
+	}
+      ret = merge_state_array (dfa, sifted_states, lim_states,
+			       match_last + 1);
+      re_free (lim_states);
+      lim_states = NULL;
+      if (BE (ret != REG_NOERROR, 0))
+	goto free_return;
+    }
+  else
+    {
+      sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
+		     match_last, 0);
+      ret = sift_states_backward (preg, mctx, &sctx);
+      re_node_set_free (&sctx.limits);
+      if (BE (ret != REG_NOERROR, 0))
+	goto free_return;
+    }
+  re_free (mctx->state_log);
+  mctx->state_log = sifted_states;
+  sifted_states = NULL;
+  mctx->last_node = halt_node;
+  mctx->match_last = match_last;
+  ret = REG_NOERROR;
+ free_return:
+  re_free (sifted_states);
+  re_free (lim_states);
+  return ret;
+}
+
 /* Acquire an initial state and return it.
    We must select appropriate initial state depending on the context,
    since initial states may have constraints like "\<", "^", etc..  */
@@ -899,6 +980,7 @@ check_matching (preg, mctx, fl_search, f
     re_match_context_t *mctx;
     int fl_search, fl_longest_match;
 {
+  re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
   reg_errcode_t err;
   int match = 0;
   int match_last = -1;
@@ -912,33 +994,20 @@ check_matching (preg, mctx, fl_search, f
   if (mctx->state_log != NULL)
     mctx->state_log[cur_str_idx] = cur_state;
 
+  /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
+     later.  E.g. Processing back references.  */
+  if (dfa->nbackref)
+    {
+      err = check_subexp_matching_top (dfa, mctx, &cur_state->nodes, 0);
+      if (BE (err != REG_NOERROR, 0))
+	return err;
+    }
+
   if (cur_state->has_backref)
     {
-      int i;
-      re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
-      for (i = 0; i < cur_state->nodes.nelem; ++i)
-	{
-	  int node = cur_state->nodes.elems[i];
-	  re_token_type_t type = dfa->nodes[node].type;
-	  if (type == OP_BACK_REF)
-	    {
-	      int clexp_idx;
-	      for (clexp_idx = 0; clexp_idx < cur_state->nodes.nelem;
-		   ++clexp_idx)
-		{
-		  re_token_t *clexp_node;
-		  clexp_node = dfa->nodes + cur_state->nodes.elems[clexp_idx];
-		  if (clexp_node->type == OP_CLOSE_SUBEXP
-		      && clexp_node->opr.idx + 1== dfa->nodes[node].opr.idx)
-		    {
-		      err = match_ctx_add_entry (mctx, node, 0, 0, 0);
-		      if (BE (err != REG_NOERROR, 0))
-			return -2;
-		      break;
-		    }
-		}
-	    }
-	}
+      err = transit_state_bkref (preg, cur_state, mctx);
+      if (BE (err != REG_NOERROR, 0))
+	return err;
     }
 
   /* If the RE accepts NULL string.  */
@@ -1552,15 +1621,6 @@ update_cur_sifted_state (preg, mctx, sct
   if (BE (sctx->sifted_states[str_idx] == NULL && err != REG_NOERROR, 0))
     return err;
 
-  /* If we are searching for the subexpression candidates.
-     Note that we were from transit_state_bkref_loop() in this case.  */
-  if (dest_nodes->nelem && sctx->check_subexp)
-    {
-      err = search_subexp (preg, mctx, sctx, str_idx, dest_nodes);
-      if (BE (err != REG_NOERROR, 0))
-	return err;
-    }
-
   if ((mctx->state_log[str_idx] != NULL
        && mctx->state_log[str_idx]->has_backref))
     {
@@ -1706,12 +1766,13 @@ check_dst_limits_calc_pos (dfa, mctx, li
 	  re_token_type_t type= dfa->nodes[node].type;
 	  if (type == OP_BACK_REF)
 	    {
-	      int bi;
-	      for (bi = 0; bi < mctx->nbkref_ents; ++bi)
+	      int bi = search_cur_bkref_entry (mctx, str_idx);
+	      for (; bi < mctx->nbkref_ents; ++bi)
 		{
 		  struct re_backref_cache_entry *ent = mctx->bkref_ents + bi;
-		  if (ent->node == node && ent->subexp_from == ent->subexp_to
-		      && ent->str_idx == str_idx)
+		  if (ent->str_idx > str_idx)
+		    break;
+		  if (ent->node == node && ent->subexp_from == ent->subexp_to)
 		    {
 		      int cpos, dst;
 		      dst = dfa->edests[node].elems[0];
@@ -1835,155 +1896,6 @@ check_subexp_limits (dfa, dest_nodes, ca
   return REG_NOERROR;
 }
 
-/* Search for the top (in case of sctx->check_subexp < 0) or the
-   bottom (in case of sctx->check_subexp > 0) of the subexpressions
-   which the backreference sctx->cur_bkref can match.  */
-
-static reg_errcode_t
-search_subexp (preg, mctx, sctx, str_idx, dest_nodes)
-     const regex_t *preg;
-     re_match_context_t *mctx;
-     re_sift_context_t *sctx;
-     int str_idx;
-     re_node_set *dest_nodes;
-{
-  reg_errcode_t err;
-  re_dfa_t *dfa = (re_dfa_t *)preg->buffer;
-  re_sift_context_t local_sctx;
-  int node_idx, node;
-  const re_node_set *candidates;
-  re_dfastate_t **lim_states = NULL;
-  candidates = ((mctx->state_log[str_idx] == NULL) ? &empty_set
-		: &mctx->state_log[str_idx]->nodes);
-  local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized.  */
-
-  for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
-    {
-      re_token_type_t type;
-      node = dest_nodes->elems[node_idx];
-      type = dfa->nodes[node].type;
-
-      if (type == OP_CLOSE_SUBEXP
-	  && sctx->check_subexp == dfa->nodes[node].opr.idx + 1)
-	{
-	  re_dfastate_t *cur_state;
-	  /* Found the bottom of the subexpression, then search for the
-	     top of it.  */
-	  if (local_sctx.sifted_states == NULL)
-	    {
-	      /* It hasn't been initialized yet, initialize it now.  */
-	      local_sctx = *sctx;
-	      err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
-	      if (BE (err != REG_NOERROR, 0))
-		goto free_return;
-	    }
-	  local_sctx.check_subexp = -sctx->check_subexp;
-	  local_sctx.limited_states = sctx->limited_states;
-	  local_sctx.last_node = node;
-	  local_sctx.last_str_idx = local_sctx.cls_subexp_idx = str_idx;
-	  cur_state = local_sctx.sifted_states[str_idx];
-	  err = sift_states_backward (preg, mctx, &local_sctx);
-	  local_sctx.sifted_states[str_idx] = cur_state;
-	  if (BE (err != REG_NOERROR, 0))
-	    goto free_return;
-	  /* There must not 2 same node in a node set.  */
-	  break;
-	}
-      else if (type == OP_OPEN_SUBEXP
-	       && -sctx->check_subexp == dfa->nodes[node].opr.idx + 1)
-	{
-	  /* Found the top of the subexpression, check that the
-	     backreference can match the input string.  */
-	  char *buf;
-	  int dest_str_idx;
-	  int bkref_str_idx = re_string_cur_idx (mctx->input);
-	  int subexp_len = sctx->cls_subexp_idx - str_idx;
-	  if (subexp_len < 0 || bkref_str_idx + subexp_len > mctx->input->len)
-	    break;
-
-	  if (bkref_str_idx + subexp_len > mctx->input->valid_len
-	      && mctx->input->valid_len < mctx->input->len)
-	    {
-	      reg_errcode_t err;
-	      err = extend_buffers (mctx);
-	      if (BE (err != REG_NOERROR, 0))
-		goto free_return;
-	    }
-	  buf = (char *) re_string_get_buffer (mctx->input);
-	  if (strncmp (buf + str_idx, buf + bkref_str_idx, subexp_len) != 0)
-	    break;
-
-	  if (sctx->limits.nelem && str_idx > 0)
-	    {
-	      re_dfastate_t *cur_state = sctx->sifted_states[str_idx];
-	      if (lim_states == NULL)
-		{
-		  lim_states = re_malloc (re_dfastate_t *, str_idx + 1);
-		  if (BE (lim_states == NULL, 0))
-		    {
-		      err = REG_ESPACE;
-		      goto free_return;
-		    }
-		}
-	      if (local_sctx.sifted_states == NULL)
-		{
-		  /* It hasn't been initialized yet, initialize it now.  */
-		  local_sctx = *sctx;
-		  err = re_node_set_init_copy (&local_sctx.limits,
-					       &sctx->limits);
-		  if (BE (err != REG_NOERROR, 0))
-		    goto free_return;
-		}
-	      local_sctx.check_subexp = 0;
-	      local_sctx.last_node = node;
-	      local_sctx.last_str_idx = str_idx;
-	      local_sctx.limited_states = lim_states;
-	      memset (lim_states, '\0',
-		      sizeof (re_dfastate_t*) * (str_idx + 1));
-	      err = sift_states_backward (preg, mctx, &local_sctx);
-	      if (BE (err != REG_NOERROR, 0))
-		goto free_return;
-	      if (local_sctx.sifted_states[0] == NULL
-		  && local_sctx.limited_states[0] == NULL)
-		{
-		  sctx->sifted_states[str_idx] = cur_state;
-		  break;
-		}
-	      sctx->sifted_states[str_idx] = cur_state;
-	    }
-	  /* Successfully matched, add a new cache entry.  */
-	  dest_str_idx = bkref_str_idx + subexp_len;
-	  err = match_ctx_add_entry (mctx, sctx->cur_bkref, bkref_str_idx,
-				     str_idx, sctx->cls_subexp_idx);
-	  if (BE (err != REG_NOERROR, 0))
-	    goto free_return;
-	  err = clean_state_log_if_need (mctx, dest_str_idx);
-	  if (BE (err != REG_NOERROR, 0))
-	    goto free_return;
-	  break;
-	}
-    }
-
-  /* Remove the top/bottom of the sub expression we processed.  */
-  if (node_idx < dest_nodes->nelem)
-    {
-      err = sub_epsilon_src_nodes(dfa, node, dest_nodes, candidates);
-      if (BE (err != REG_NOERROR, 0))
-	goto free_return;
-      /* Update state_log.  */
-      sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
-      if (BE (err != REG_NOERROR, 0))
-	goto free_return;
-    }
-  err = REG_NOERROR;
- free_return:
-  if (local_sctx.sifted_states != NULL)
-    re_node_set_free (&local_sctx.limits);
-  if (lim_states != NULL)
-    re_free (lim_states);
-  return err;
-}
-
 static reg_errcode_t
 sift_states_bkref (preg, mctx, sctx, str_idx, dest_nodes)
      const regex_t *preg;
@@ -2014,45 +1926,28 @@ sift_states_bkref (preg, mctx, sctx, str
 	continue;
       if (type == OP_BACK_REF)
 	{
-	  int enabled_idx;
-	  for (enabled_idx = 0; enabled_idx < mctx->nbkref_ents; ++enabled_idx)
+	  int enabled_idx = search_cur_bkref_entry (mctx, str_idx);
+	  for (; enabled_idx < mctx->nbkref_ents; ++enabled_idx)
 	    {
 	      int disabled_idx, subexp_len, to_idx, dst_node;
 	      struct re_backref_cache_entry *entry;
 	      entry = mctx->bkref_ents + enabled_idx;
+	      if (entry->str_idx > str_idx)
+		break;
+	      if (entry->node != node)
+		  continue;
 	      subexp_len = entry->subexp_to - entry->subexp_from;
 	      to_idx = str_idx + subexp_len;
 	      dst_node = (subexp_len ? dfa->nexts[node]
 			  : dfa->edests[node].elems[0]);
 
-	      if (entry->node != node || entry->str_idx != str_idx
-		  || to_idx > sctx->last_str_idx
-		  || sctx->sifted_states[to_idx] == NULL)
-		continue;
-	      if (!STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node))
+	      if (to_idx > sctx->last_str_idx
+		  || sctx->sifted_states[to_idx] == NULL
+		  || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx],
+					   dst_node)
+		  || check_dst_limits (dfa, &sctx->limits, mctx, node,
+				       str_idx, dst_node, to_idx))
 		continue;
-
-	      if (check_dst_limits (dfa, &sctx->limits, mctx, node,
-				    str_idx, dst_node, to_idx))
-		continue;
-	      if (sctx->check_subexp == dfa->nodes[node].opr.idx)
-		{
-		  char *buf;
-		  buf = (char *) re_string_get_buffer (mctx->input);
-		  if (strncmp (buf + entry->subexp_from,
-			       buf + cur_bkref_idx, subexp_len) != 0)
-		    continue;
-		  err = match_ctx_add_entry (mctx, sctx->cur_bkref,
-					     cur_bkref_idx, entry->subexp_from,
-					     entry->subexp_to);
-		  if (BE (err != REG_NOERROR, 0))
-		    goto free_return;
-		  err = clean_state_log_if_need (mctx, cur_bkref_idx
-						 + subexp_len);
-		  if (BE (err != REG_NOERROR, 0))
-		    goto free_return;
-		}
-	      else
 		{
 		  re_dfastate_t *cur_state;
 		  entry->flag = 0;
@@ -2061,9 +1956,9 @@ sift_states_bkref (preg, mctx, sctx, str
 		    {
 		      struct re_backref_cache_entry *entry2;
 		      entry2 = mctx->bkref_ents + disabled_idx;
-		      if (entry2->node != node || entry2->str_idx != str_idx)
-			continue;
-		      entry2->flag = 1;
+		      if (entry2->str_idx > str_idx)
+			break;
+		      entry2->flag = (entry2->node == node) ? 1 : entry2->flag;
 		    }
 
 		  if (local_sctx.sifted_states == NULL)
@@ -2101,11 +1996,14 @@ sift_states_bkref (preg, mctx, sctx, str
 		  mctx->bkref_ents[enabled_idx].flag = 1;
 		}
 	    }
-	  for (enabled_idx = 0; enabled_idx < mctx->nbkref_ents; ++enabled_idx)
+	  enabled_idx = search_cur_bkref_entry (mctx, str_idx);
+	  for (; enabled_idx < mctx->nbkref_ents; ++enabled_idx)
 	    {
 	      struct re_backref_cache_entry *entry;
 	      entry = mctx->bkref_ents + enabled_idx;
-	      if (entry->node == node && entry->str_idx == str_idx)
+	      if (entry->str_idx > str_idx)
+		break;
+	      if (entry->node == node)
 		entry->flag = 0;
 	    }
 	}
@@ -2165,6 +2063,7 @@ transit_state (err, preg, mctx, state, f
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
   re_dfastate_t **trtable, *next_state;
   unsigned char ch;
+  int cur_idx;
 
   if (re_string_cur_idx (mctx->input) + 1 >= mctx->input->bufs_len
       || (re_string_cur_idx (mctx->input) + 1 >= mctx->input->valid_len
@@ -2218,10 +2117,10 @@ transit_state (err, preg, mctx, state, f
 	}
     }
 
+  cur_idx = re_string_cur_idx (mctx->input);
   /* Update the state_log if we need.  */
   if (mctx->state_log != NULL)
     {
-      int cur_idx = re_string_cur_idx (mctx->input);
       if (cur_idx > mctx->state_log_top)
 	{
 	  mctx->state_log[cur_idx] = next_state;
@@ -2266,20 +2165,55 @@ transit_state (err, preg, mctx, state, f
 	  if (table_nodes != NULL)
 	    re_node_set_free (&next_nodes);
 	}
-      /* If the next state has back references.  */
-      if (next_state != NULL && next_state->has_backref)
-	{
-	  *err = transit_state_bkref (preg, next_state, mctx);
-	  if (BE (*err != REG_NOERROR, 0))
-	    return NULL;
-	  next_state = mctx->state_log[cur_idx];
-	}
+    }
+
+  /* Check OP_OPEN_SUBEXP in the current state in case that we use them
+     later.  We must check them here, since the back references in the
+     next state might use them.  */
+  if (dfa->nbackref && next_state/* && fl_process_bkref */)
+    {
+      *err = check_subexp_matching_top (dfa, mctx, &next_state->nodes,
+					cur_idx);
+      if (BE (*err != REG_NOERROR, 0))
+	return NULL;
+    }
+
+  /* If the next state has back references.  */
+  if (next_state != NULL && next_state->has_backref)
+    {
+      *err = transit_state_bkref (preg, next_state, mctx);
+      if (BE (*err != REG_NOERROR, 0))
+	return NULL;
+      next_state = mctx->state_log[cur_idx];
     }
   return next_state;
 }
 
 /* Helper functions for transit_state.  */
 
+static reg_errcode_t
+check_subexp_matching_top (dfa, mctx, cur_nodes, str_idx)
+     re_dfa_t *dfa;
+     re_match_context_t *mctx;
+     re_node_set *cur_nodes;
+     int str_idx;
+{
+  int node_idx;
+  reg_errcode_t err;
+
+  for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
+    {
+      int node = cur_nodes->elems[node_idx];
+      if (dfa->nodes[node].type == OP_OPEN_SUBEXP)
+	{
+	  err = match_ctx_add_subtop (mctx, node, str_idx);
+	  if (BE (err != REG_NOERROR, 0))
+	    return err;
+	}
+    }
+  return REG_NOERROR;
+}
+
 /* Return the next state to which the current state STATE will transit by
    accepting the current input byte.  */
 
@@ -2428,25 +2362,14 @@ transit_state_bkref (preg, pstate, mctx)
     re_match_context_t *mctx;
 {
   reg_errcode_t err;
-  re_dfastate_t **work_state_log;
-
-  work_state_log = re_malloc (re_dfastate_t *,
-			      re_string_cur_idx (mctx->input) + 1);
-  if (BE (work_state_log == NULL, 0))
-    return REG_ESPACE;
-
-  err = transit_state_bkref_loop (preg, &pstate->nodes, work_state_log, mctx);
-  re_free (work_state_log);
+  err = transit_state_bkref_loop (preg, &pstate->nodes, mctx);
   return err;
 }
 
-/* Caller must allocate `work_state_log'.  */
-
 static reg_errcode_t
-transit_state_bkref_loop (preg, nodes, work_state_log, mctx)
+transit_state_bkref_loop (preg, nodes, mctx)
     const regex_t *preg;
     re_node_set *nodes;
-    re_dfastate_t **work_state_log;
     re_match_context_t *mctx;
 {
   reg_errcode_t err;
@@ -2464,7 +2387,6 @@ transit_state_bkref_loop (preg, nodes, w
       unsigned int context;
       re_token_t *node = dfa->nodes + node_idx;
       re_node_set *new_dest_nodes;
-      re_sift_context_t sctx;
 
       /* Check whether `node' is a backreference or not.  */
       if (node->type == OP_BACK_REF)
@@ -2482,11 +2404,7 @@ transit_state_bkref_loop (preg, nodes, w
 
       /* `node' is a backreference.
 	 Check the substring which the substring matched.  */
-      sift_ctx_init (&sctx, work_state_log, NULL, node_idx, cur_str_idx,
-		     subexp_idx);
-      sctx.cur_bkref = node_idx;
-      match_ctx_clear_flag (mctx);
-      err = sift_states_backward (preg, mctx, &sctx);
+      err = get_subexp (preg, mctx, node_idx, cur_str_idx, subexp_idx - 1);
       if (BE (err != REG_NOERROR, 0))
 	goto free_return;
 
@@ -2495,7 +2413,8 @@ transit_state_bkref_loop (preg, nodes, w
 #ifdef DEBUG
       assert (dfa->nexts[node_idx] != -1);
 #endif
-      for (bkc_idx = 0; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
+      bkc_idx = search_cur_bkref_entry (mctx, cur_str_idx);
+      for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
 	{
 	  int subexp_len;
 	  re_dfastate_t *dest_state;
@@ -2509,9 +2428,8 @@ transit_state_bkref_loop (preg, nodes, w
 			    : dfa->eclosures + dfa->nexts[node_idx]);
 	  dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
 			  - bkref_ent->subexp_from);
-	  context = (IS_WORD_CHAR (re_string_byte_at (mctx->input,
-						      dest_str_idx - 1))
-		     ? CONTEXT_WORD : 0);
+	  context = re_string_context_at (mctx->input, dest_str_idx - 1,
+					  mctx->eflags, preg->newline_anchor);
 	  dest_state = mctx->state_log[dest_str_idx];
 	  prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
 			: mctx->state_log[cur_str_idx]->nodes.nelem);
@@ -2548,8 +2466,11 @@ transit_state_bkref_loop (preg, nodes, w
 	  if (subexp_len == 0
 	      && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
 	    {
-	      err = transit_state_bkref_loop (preg, new_dest_nodes,
-					      work_state_log, mctx);
+	      err = check_subexp_matching_top (dfa, mctx, new_dest_nodes,
+					       cur_str_idx);
+	      if (BE (err != REG_NOERROR, 0))
+		goto free_return;
+	      err = transit_state_bkref_loop (preg, new_dest_nodes, mctx);
 	      if (BE (err != REG_NOERROR, 0))
 		goto free_return;
 	    }
@@ -2561,6 +2482,553 @@ transit_state_bkref_loop (preg, nodes, w
   return err;
 }
 
+static reg_errcode_t
+get_subexp (preg, mctx, bkref_node, bkref_str_idx, subexp_idx)
+     const regex_t *preg;
+     re_match_context_t *mctx;
+     int bkref_node, bkref_str_idx, subexp_idx;
+{
+  int sub_top_idx;
+  re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
+  char *buf = re_string_get_buffer (mctx->input);
+  /* For each sub expression...  */
+  for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
+    {
+      reg_errcode_t err;
+      re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
+      re_sub_match_last_t *sub_last;
+      int sub_last_idx, sl_str;
+      char *bkref_str;
+
+      if (dfa->nodes[sub_top->node].opr.idx != subexp_idx)
+	continue; /* It isn't related.  */
+
+      sl_str = sub_top->str_idx;
+      bkref_str = buf + bkref_str_idx;
+      /* At first, check the last node of sub expressions we already
+	 evaluated.  */
+      for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
+	{
+	  int sl_str_diff;
+	  sub_last = sub_top->lasts[sub_last_idx];
+	  sl_str_diff = sub_last->str_idx - sl_str;
+	  /* The matched string by the sub expression match with the substring
+	     at the back reference?  */
+	  if (sl_str_diff > 0
+	      && memcmp (bkref_str, buf + sl_str, sl_str_diff) != 0)
+	    break; /* We don't need to search this sub expression any more.  */
+	  bkref_str += sl_str_diff;
+	  sl_str += sl_str_diff;
+	  err = get_subexp_sub (preg, mctx, sub_top, sub_last, bkref_node,
+				bkref_str_idx, subexp_idx);
+	  if (err == REG_NOMATCH)
+	    continue;
+	  if (BE (err != REG_NOERROR, 0))
+	    return err;
+	}
+      if (sub_last_idx < sub_top->nlasts)
+	continue;
+      if (sub_last_idx > 0)
+	++sl_str;
+      /* Then, search for the other last nodes of the sub expression.  */
+      for (; sl_str <= bkref_str_idx; ++sl_str)
+	{
+	  int cls_node, sl_str_off;
+	  re_sub_match_last_t cur_last;
+	  re_node_set *nodes;
+	  sl_str_off = sl_str - sub_top->str_idx;
+	  /* The matched string by the sub expression match with the substring
+	     at the back reference?  */
+	  if (sl_str_off > 0
+	      && memcmp (bkref_str++, buf + sl_str - 1, 1) != 0)
+	    break; /* We don't need to search this sub expression any more.  */
+	  if (mctx->state_log[sl_str] == NULL)
+	    continue;
+	  /* Does this state have a ')' of the sub expression?  */
+	  nodes = &mctx->state_log[sl_str]->nodes;
+	  cls_node = find_subexp_node (dfa, nodes, subexp_idx, 0);
+	  if (cls_node == -1)
+	    continue; /* No.  */
+	  if (sub_top->path == NULL)
+	    {
+	      sub_top->path = calloc (sizeof (state_array_t), 1);
+	      if (sub_top->path == NULL)
+		return REG_ESPACE;
+	    }
+	  /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
+	     in the current context?  */
+	  memset (&cur_last, '\0', sizeof (re_sub_match_last_t));
+	  cur_last.node = cls_node;
+	  cur_last.str_idx = sl_str;
+	  err = check_arrival (preg, mctx, sub_top, &cur_last, -1, -1);
+	  if (err == REG_NOMATCH)
+	      continue;
+	  if (BE (err != REG_NOERROR, 0))
+	      return err;
+	  sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
+	  if (BE (sub_last == NULL, 0))
+	    return REG_ESPACE;
+	  err = get_subexp_sub (preg, mctx, sub_top, sub_last, bkref_node,
+				bkref_str_idx, subexp_idx);
+	  if (err == REG_NOMATCH)
+	    continue;
+	}
+    }
+  return REG_NOERROR;
+}
+
+static reg_errcode_t
+get_subexp_sub (preg, mctx, sub_top, sub_last, bkref_node, bkref_str,
+		subexp_idx)
+     const regex_t *preg;
+     re_match_context_t *mctx;
+     re_sub_match_top_t *sub_top;
+     re_sub_match_last_t *sub_last;
+     int bkref_node, bkref_str, subexp_idx;
+{
+  reg_errcode_t err;
+  int to_idx;
+  /* Can the subexpression arrive the back reference?  */
+  err = check_arrival (preg, mctx, sub_top, sub_last, bkref_node, bkref_str);
+  if (err != REG_NOERROR)
+    return err;
+  err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
+			     sub_last->str_idx, sub_top, sub_last);
+  if (BE (err != REG_NOERROR, 0))
+    return err;
+  to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
+  clean_state_log_if_need (mctx, to_idx);
+  return REG_NOERROR;
+}
+
+/* Find the first node which is '(' or ')', and whose index is SUBEXP_IDX.
+   Search '(' if FL_OPEN, or search ')' otherwise.  */
+
+static int
+find_subexp_node (dfa, nodes, subexp_idx, fl_open)
+     re_dfa_t *dfa;
+     re_node_set *nodes;
+     int subexp_idx, fl_open;
+{
+  int cls_idx;
+  for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
+    {
+      int cls_node = nodes->elems[cls_idx];
+      re_token_t *node = dfa->nodes + cls_node;
+      if (((fl_open && node->type == OP_OPEN_SUBEXP)
+	  || (!fl_open && node->type == OP_CLOSE_SUBEXP))
+	  && node->opr.idx == subexp_idx)
+	return cls_node;
+    }
+  return -1;
+}
+
+static reg_errcode_t
+check_arrival (preg, mctx, sub_top, sub_last, bkref_node, bkref_str)
+     const regex_t *preg;
+     re_match_context_t *mctx;
+     re_sub_match_top_t *sub_top;
+     re_sub_match_last_t *sub_last;
+     int bkref_node, bkref_str;
+{
+  re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
+  reg_errcode_t err;
+  int backup_cur_idx, str_idx, null_cnt;
+  re_dfastate_t *cur_state = NULL;
+  re_node_set *cur_nodes;
+  re_dfastate_t **backup_state_log;
+
+  state_array_t *path;
+  int top_node, top_str, ex_subexp, last_node, last_str, fl_open;
+
+  path = bkref_node < 0 ? sub_top->path : &sub_last->path;
+  top_node = bkref_node < 0 ? sub_top->node : sub_last->node;
+  top_str = bkref_node < 0 ? sub_top->str_idx : sub_last->str_idx;
+  last_node = bkref_node < 0 ? sub_last->node : bkref_node;
+  last_str = bkref_node < 0 ? sub_last->str_idx : bkref_str;
+
+  ex_subexp = dfa->nodes[sub_top->node].opr.idx;
+  fl_open = (bkref_node >= 0);
+
+  /* Extend the buffer if we need.  */
+  if (path->alloc < last_str + mctx->max_mb_elem_len + 1)
+    {
+      int old_alloc = path->alloc;
+      path->alloc = last_str + mctx->max_mb_elem_len + 1;
+      path->array = re_realloc (path->array, re_dfastate_t *, path->alloc);
+      if (path->array == NULL)
+	return REG_ESPACE;
+      memset (path->array + old_alloc, '\0',
+	      sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
+    }
+
+  str_idx = path->next_idx == 0 ? top_str : path->next_idx;
+
+  /* Temporary modify MCTX.  */
+  backup_state_log = mctx->state_log;
+  backup_cur_idx = mctx->input->cur_idx;
+  mctx->state_log = path->array;
+  mctx->input->cur_idx = str_idx;
+
+  /* Setup initial node set.  */
+  if (str_idx == top_str)
+    {
+      unsigned int context;
+      re_node_set init_nodes;
+      context = re_string_context_at (mctx->input, str_idx - 1, mctx->eflags,
+				      preg->newline_anchor);
+      err = re_node_set_init_1 (&init_nodes, top_node);
+      if (BE (err != REG_NOERROR, 0))
+	return err;
+      err = expand_eclosures (dfa, &init_nodes, ex_subexp, fl_open);
+      if (BE (err != REG_NOERROR, 0))
+	return err;
+
+      if (init_nodes.nelem)
+	{
+	  err = expand_bkref_cache (preg, mctx, sub_top, sub_last, &init_nodes,
+				    str_idx, last_str, ex_subexp, fl_open);
+	  if (BE ( err != REG_NOERROR, 0))
+	    return err;
+	}
+      cur_state = re_acquire_state_context (&err, dfa, &init_nodes, context);
+      if (BE (cur_state == NULL && err != REG_NOERROR, 0))
+	return err;
+      mctx->state_log[str_idx] = cur_state;
+      re_node_set_free (&init_nodes);
+    }
+  else
+    {
+      cur_state = mctx->state_log[str_idx];
+      if (cur_state && cur_state->has_backref)
+	{
+	  unsigned int context;
+	  re_node_set init_nodes;
+	  context = re_string_context_at (mctx->input, str_idx - 1,
+					  mctx->eflags, preg->newline_anchor);
+	  err = re_node_set_init_copy (&init_nodes, &cur_state->nodes);
+	  if (BE ( err != REG_NOERROR, 0))
+	    return err;
+	  err = expand_bkref_cache (preg, mctx, sub_top, sub_last, &init_nodes,
+				    str_idx, last_str, ex_subexp, fl_open);
+	  if (BE ( err != REG_NOERROR, 0))
+	    return err;
+	  cur_state = re_acquire_state_context (&err, dfa, &init_nodes,
+						context);
+	  if (BE (cur_state == NULL && err != REG_NOERROR, 0))
+	    return err;
+	  mctx->state_log[str_idx] = cur_state;
+	  re_node_set_free (&init_nodes);
+	}
+    }
+
+  for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
+    {
+      int cur_idx;
+      unsigned int context;
+      re_node_set next_nodes;
+      if (mctx->state_log[str_idx + 1])
+	{
+	  err = re_node_set_init_copy (&next_nodes,
+				       &mctx->state_log[str_idx + 1]->nodes);
+	  if (BE (cur_state == NULL && err != REG_NOERROR, 0))
+	    return err;
+	}
+      else
+	re_node_set_init_empty (&next_nodes);
+
+      cur_nodes = cur_state? &cur_state->nodes : &empty_set;
+      for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
+	{
+	  int naccepted = 0;
+	  int cur_node = cur_nodes->elems[cur_idx];
+	  re_token_type_t type = dfa->nodes[cur_node].type;
+	  if (IS_EPSILON_NODE(type))
+	    continue;
+#ifdef RE_ENABLE_I18N
+	  /* If the node may accept `multi byte'.  */
+	  if (ACCEPT_MB_NODE (type))
+	    {
+	      naccepted = check_node_accept_bytes (preg, cur_node, mctx->input,
+						   str_idx);
+	      if (naccepted > 1)
+		{
+		  re_node_set union_set;
+		  re_dfastate_t *dest_state;
+		  int next_node = dfa->nexts[cur_node];
+		  int next_idx = str_idx + naccepted;
+		  dest_state = mctx->state_log[next_idx];
+		  if (dest_state)
+		    {
+		      err = re_node_set_init_copy (&union_set,
+						   &dest_state->nodes);
+		      if (BE (err != REG_NOERROR, 0))
+			return err;
+		      err = re_node_set_insert (&union_set, next_node);
+		      if (BE (err < 0, 0))
+			return REG_ESPACE;
+		    }
+		  else
+		    {
+		      err = re_node_set_init_1 (&union_set, next_node);
+		      if (BE (err != REG_NOERROR, 0))
+			return err;
+		    }
+		  mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
+								&union_set);
+		  re_node_set_free (&union_set);
+		  if (BE (mctx->state_log[next_idx] == NULL
+			  && err != REG_NOERROR, 0))
+		    return err;
+		}
+	    }
+#endif /* RE_ENABLE_I18N */
+	  if (naccepted
+	      || check_node_accept (preg, dfa->nodes + cur_node, mctx,
+				    str_idx))
+	    {
+	      err = re_node_set_insert (&next_nodes, dfa->nexts[cur_node]);
+	      if (BE (err < 0, 0))
+		return REG_ESPACE;
+	    }
+	}
+
+      ++str_idx;
+      if (next_nodes.nelem)
+	{
+	  err = expand_eclosures (dfa, &next_nodes, ex_subexp, fl_open);
+	  if (BE (err != REG_NOERROR, 0))
+	    return err;
+	}
+      if (next_nodes.nelem)
+	{
+	  err = expand_bkref_cache (preg, mctx, sub_top, sub_last, &next_nodes,
+				    str_idx, last_str, ex_subexp, fl_open);
+	  if (BE ( err != REG_NOERROR, 0))
+	    return err;
+	}
+      context = re_string_context_at (mctx->input, str_idx - 1, mctx->eflags,
+				      preg->newline_anchor);
+      cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
+      if (BE (cur_state == NULL && err != REG_NOERROR, 0))
+	return err;
+      mctx->state_log[str_idx] = cur_state;
+      re_node_set_free (&next_nodes);
+      null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
+    }
+  cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
+	       : &mctx->state_log[last_str]->nodes);
+  path->next_idx = str_idx;
+
+  /* Fix MCTX.  */
+  mctx->state_log = backup_state_log;
+  mctx->input->cur_idx = backup_cur_idx;
+
+  if (cur_nodes == NULL)
+    return REG_NOMATCH;
+  /* Then check the current node set has the node LAST_NODE.  */
+  return (re_node_set_contains (cur_nodes, last_node)
+	  || re_node_set_contains (cur_nodes, last_node) ? REG_NOERROR
+	  : REG_NOMATCH);
+}
+
+/* Helper functions for check_arrival.  */
+
+static reg_errcode_t
+expand_eclosures (dfa, cur_nodes, ex_subexp, fl_open)
+     re_dfa_t *dfa;
+     re_node_set *cur_nodes;
+     int ex_subexp, fl_open;
+{
+  reg_errcode_t err;
+  int idx, outside_node;
+  re_node_set new_nodes;
+#ifdef DEBUG
+  assert (cur_nodes->nelem);
+#endif
+  re_node_set_alloc (&new_nodes, cur_nodes->nelem);
+  /* Create a new node set with the nodes which are epsilon closures of
+     a node in cur_nodes.  */
+  for (idx = 0; idx < cur_nodes->nelem; ++idx)
+    {
+      int cur_node = cur_nodes->elems[idx];
+      err = re_node_set_merge (&new_nodes, dfa->eclosures + cur_node);
+      if (BE (err != REG_NOERROR, 0))
+	return err;
+    }
+  outside_node = find_subexp_node (dfa, &new_nodes, ex_subexp, fl_open);
+  if (outside_node == -1)
+    {
+      re_node_set_free (cur_nodes);
+      *cur_nodes = new_nodes;
+      return REG_NOERROR;
+    }
+  /* In this case, we have some nodes which are outside, remove them.  */
+  re_node_set_empty (&new_nodes);
+  for (idx = 0; idx < cur_nodes->nelem; ++idx)
+    {
+      int cur_node = cur_nodes->elems[idx];
+      re_node_set *eclosure = dfa->eclosures + cur_node;
+      outside_node = find_subexp_node (dfa, eclosure, ex_subexp, fl_open);
+      if (outside_node == -1)
+	{
+	  err = re_node_set_merge (&new_nodes, eclosure);
+	  if (BE (err != REG_NOERROR, 0))
+	    return err;
+	}
+      else
+	{
+	  err = expand_eclosures_sub (dfa, &new_nodes, cur_node, ex_subexp,
+				      fl_open);
+	  if (BE (err != REG_NOERROR, 0))
+	    return err;
+	}
+    }
+  re_node_set_free (cur_nodes);
+  *cur_nodes = new_nodes;
+  return REG_NOERROR;
+}
+
+static reg_errcode_t
+expand_eclosures_sub (dfa, dst_nodes, target, ex_subexp, fl_open)
+     re_dfa_t *dfa;
+     int target, ex_subexp, fl_open;
+     re_node_set *dst_nodes;
+{
+  int cur_node, type;
+  for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
+    {
+      int err;
+      type = dfa->nodes[cur_node].type;
+
+      if (((type == OP_OPEN_SUBEXP && fl_open)
+	   || (type == OP_CLOSE_SUBEXP && !fl_open))
+	  && dfa->nodes[cur_node].opr.idx == ex_subexp)
+	{
+	  if (!fl_open)
+	    {
+	      err = re_node_set_insert (dst_nodes, cur_node);
+	      if (BE (err == -1, 0))
+		return REG_ESPACE;
+	    }
+	  break;
+	}
+      err = re_node_set_insert (dst_nodes, cur_node);
+      if (BE (err == -1, 0))
+	return REG_ESPACE;
+      if (dfa->edests[cur_node].nelem == 0)
+	break;
+      if (dfa->edests[cur_node].nelem == 2)
+	{
+	  err = expand_eclosures_sub (dfa, dst_nodes,
+				      dfa->edests[cur_node].elems[1],
+				      ex_subexp, fl_open);
+	  if (BE (err != REG_NOERROR, 0))
+	    return err;
+	}
+      cur_node = dfa->edests[cur_node].elems[0];
+    }
+  return REG_NOERROR;
+}
+
+
+/* For all the back references in the current state, calculate the
+   destination of the back references by the appropriate entry
+   in MCTX->BKREF_ENTS.  */
+
+static reg_errcode_t
+expand_bkref_cache (preg, mctx, sub_top, sub_last, cur_nodes, cur_str,
+		    last_str, ex_subexp, fl_open)
+     const regex_t *preg;
+     re_match_context_t *mctx;
+     re_sub_match_top_t *sub_top;
+     re_sub_match_last_t *sub_last;
+     int cur_str, last_str, ex_subexp, fl_open;
+     re_node_set *cur_nodes;
+{
+  reg_errcode_t err;
+  re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
+  re_node_set processed_nodes;
+  int node_idx, cache_idx, cur_subexp_idx;
+  /* The current state.  */
+  cur_subexp_idx = dfa->nodes[sub_top->node].opr.idx;
+  re_node_set_init_empty (&processed_nodes);
+  for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
+    {
+      int bkref_node = cur_nodes->elems[node_idx];
+      if (dfa->nodes[bkref_node].type != OP_BACK_REF
+	  || re_node_set_contains (&processed_nodes, bkref_node))
+	continue;
+
+      for (cache_idx = 0; cache_idx < mctx->nbkref_ents; ++cache_idx)
+	{
+	  int to_idx, next_node;
+	  struct re_backref_cache_entry *ent = mctx->bkref_ents + cache_idx;
+	  /* Is this entry ENT is appropriate?  */
+	  if (ent->str_idx != cur_str
+	      || !re_node_set_contains (cur_nodes, ent->node))
+	    continue; /* No.  */
+
+	  to_idx = cur_str + ent->subexp_to - ent->subexp_from;
+	  /* Calculate the destination of the back reference, and append it
+	     to MCTX->STATE_LOG.  */
+	  if (to_idx == cur_str)
+	    {
+	      re_node_set new_dests;
+	      next_node = dfa->edests[ent->node].elems[0];
+	      if (re_node_set_contains (cur_nodes, next_node))
+		continue;
+	      err = re_node_set_init_1 (&new_dests, next_node);
+	      if (BE (err != REG_NOERROR, 0))
+		return err;
+	      err = expand_eclosures (dfa, &new_dests, ex_subexp, fl_open);
+	      if (BE (err != REG_NOERROR, 0))
+		return err;
+	      err = re_node_set_merge (cur_nodes, &new_dests);
+	      if (BE (err != REG_NOERROR, 0))
+		return err;
+	      re_node_set_free (&new_dests);
+	      /* TODO: It is still inefficient...  */
+	      node_idx = -1;
+	      break;
+	    }
+	  else
+	    {
+	      re_node_set union_set;
+	      next_node = dfa->nexts[ent->node];
+	      if (mctx->state_log[to_idx])
+		{
+		  int ret;
+		  if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
+					    next_node))
+		    continue;
+		  err = re_node_set_init_copy (&union_set,
+					      &mctx->state_log[to_idx]->nodes);
+		  if (BE (err != REG_NOERROR, 0))
+		    return err;
+		  ret = re_node_set_insert (&union_set, next_node);
+		  if (BE (err < 0, 0))
+		    return REG_ESPACE;
+		}
+	      else
+		{
+		  err = re_node_set_init_1 (&union_set, next_node);
+		  if (BE (err != REG_NOERROR, 0))
+		    return err;
+		}
+	      mctx->state_log[to_idx] = re_acquire_state (&err, dfa,
+							  &union_set);
+	      re_node_set_free (&union_set);
+	      if (BE (mctx->state_log[to_idx] == NULL
+		      && err != REG_NOERROR, 0))
+		return err;
+	    }
+	}
+    }
+  re_node_set_free (&processed_nodes);
+  return REG_NOERROR;
+}
+
 /* Build transition table for the state.
    Return the new table if succeeded, otherwise return NULL.  */
 
@@ -3257,14 +3725,17 @@ match_ctx_init (mctx, eflags, input, n)
   if (n > 0)
     {
       mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
-      if (BE (mctx->bkref_ents == NULL, 0))
+      mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
+      if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
 	return REG_ESPACE;
     }
   else
     mctx->bkref_ents = NULL;
   mctx->nbkref_ents = 0;
   mctx->abkref_ents = n;
-  mctx->max_mb_elem_len = 0;
+  mctx->max_mb_elem_len = 1;
+  mctx->nsub_tops = 0;
+  mctx->asub_tops = n;
   return REG_NOERROR;
 }
 
@@ -3272,16 +3743,52 @@ static void
 match_ctx_free (mctx)
     re_match_context_t *mctx;
 {
+  int st_idx;
+  for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
+    {
+      int sl_idx;
+      re_sub_match_top_t *top = mctx->sub_tops[st_idx];
+      for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
+	{
+	  re_sub_match_last_t *last = top->lasts[sl_idx];
+	  re_free (last->path.array);
+	  if (last->limits)
+	    re_node_set_free (last->limits);
+	  re_free (last);
+	}
+      re_free (top->lasts);
+      if (top->path)
+	{
+	  re_free (top->path->array);
+	  re_free (top->path);
+	}
+      if (top->limits)
+	re_node_set_free (top->limits);
+      free (top);
+    }
+  re_free (mctx->sub_tops);
   re_free (mctx->bkref_ents);
 }
 
 /* Add a new backreference entry to the cache.  */
 
 static reg_errcode_t
-match_ctx_add_entry (mctx, node, str_idx, from, to)
-    re_match_context_t *mctx;
-    int node, str_idx, from, to;
+match_ctx_add_entry (mctx, node, str_idx, from, to, top, last)
+     re_match_context_t *mctx;
+     int node, str_idx, from, to;
+     re_sub_match_top_t *top;
+     re_sub_match_last_t *last;
 {
+  /* TODO: It can be more efficient.  */
+  int i;
+  for (i = 0; i < mctx->nbkref_ents; ++i)
+    {
+      struct re_backref_cache_entry *entry = mctx->bkref_ents + i;
+      if (entry->node == node && entry->str_idx == str_idx
+	  &&  entry->subexp_from == from &&  entry->subexp_to == to)
+	return REG_NOERROR;
+    }
+
   if (mctx->nbkref_ents >= mctx->abkref_ents)
     {
       struct re_backref_cache_entry* new_entry;
@@ -3301,12 +3808,32 @@ match_ctx_add_entry (mctx, node, str_idx
   mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
   mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
   mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
+  mctx->bkref_ents[mctx->nbkref_ents].top = top;
+  mctx->bkref_ents[mctx->nbkref_ents].last = last;
   mctx->bkref_ents[mctx->nbkref_ents++].flag = 0;
   if (mctx->max_mb_elem_len < to - from)
     mctx->max_mb_elem_len = to - from;
   return REG_NOERROR;
 }
 
+static int
+search_cur_bkref_entry (mctx, str_idx)
+     re_match_context_t *mctx;
+     int str_idx;
+{
+  int left, right, mid;
+  right = mctx->nbkref_ents;
+  for (left = 0; left < right;)
+    {
+      mid = (left + right) / 2;
+      if (mctx->bkref_ents[mid].str_idx < str_idx)
+	left = mid + 1;
+      else
+	right = mid;
+    }
+  return left;
+}
+
 static void
 match_ctx_clear_flag (mctx)
      re_match_context_t *mctx;
@@ -3318,6 +3845,54 @@ match_ctx_clear_flag (mctx)
     }
 }
 
+static reg_errcode_t
+match_ctx_add_subtop (mctx, node, str_idx)
+     re_match_context_t *mctx;
+     int node, str_idx;
+{
+#ifdef DEBUG
+  assert (mctx->sub_tops != NULL);
+  assert (mctx->asub_tops > 0);
+#endif
+  if (mctx->nsub_tops == mctx->asub_tops)
+    {
+      mctx->asub_tops *= 2;
+      mctx->sub_tops = re_realloc (mctx->sub_tops, re_sub_match_top_t *,
+				   mctx->asub_tops);
+      if (BE (mctx->sub_tops == NULL, 0))
+	return REG_ESPACE;
+    }
+  mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
+  if (mctx->sub_tops[mctx->nsub_tops] == NULL)
+    return REG_ESPACE;
+  mctx->sub_tops[mctx->nsub_tops]->node = node;
+  mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
+  return REG_NOERROR;
+}
+
+static re_sub_match_last_t *
+match_ctx_add_sublast (subtop, node, str_idx)
+     re_sub_match_top_t *subtop;
+     int node, str_idx;
+{
+  re_sub_match_last_t *new_entry;
+  if (subtop->nlasts == subtop->alasts)
+    {
+      subtop->alasts = 2 * subtop->alasts + 1;
+      subtop->lasts = re_realloc (subtop->lasts, re_sub_match_last_t *,
+				  subtop->alasts);
+      if (BE (subtop->lasts == NULL, 0))
+	return NULL;
+    }
+  new_entry = calloc (1, sizeof (re_sub_match_last_t));
+  subtop->lasts[subtop->nlasts] = new_entry;
+  new_entry->node = node;
+  new_entry->str_idx = str_idx;
+  new_entry->limits = NULL;
+  ++subtop->nlasts;
+  return new_entry;
+}
+
 static void
 sift_ctx_init (sctx, sifted_sts, limited_sts, last_node, last_str_idx,
 	       check_subexp)
