Update.

2002-11-27  Isamu Hasegawa  <isamu@yamato.ibm.com>

	* posix/regcomp.c (parse_expression): Set the bit since the back
	reference is used in the regular expression.
	* posix/regex_internal.c (re_node_set_init_1): Make it clean in case
	of malloc failure.
	(re_node_set_init_copy): Likewise.
	* posix/regex_internal.h (state_array_t): New structure.
	(re_sub_match_last_t): Likewise.
	(re_sub_match_top_t): Likewise.
	(re_match_context_t): Add new members.
	(re_dfa_t): Likewise.
	* posix/regexec.c (re_search_internal): Invoke prune_impossible_nodes
	to check the matching is really correct, and retry if failed.
	Move the routin pruning the impossible nodes from here, ...
	(prune_impossible_nodes): To this function.
	(check_matching): Invoke check_subexp_matching_top, and replace
	redundant checking with transit_state_bkref invocation.
	(proceed_next_node): Replace strncmp with memcmp.  Reported by
	Paolo Bonzini  <bonzini@gnu.org>.
	(update_cur_sifted_state): Remove search_subexp invocation.
	(search_subexp): Remove this function.
	(check_dst_limits_calc_pos): Use search_cur_bkref_entry for
	optimization.
	(sift_states_bkref): Use search_cur_bkref_entry for optimization.
	Remove unused invocation of match_ctx_add_entry.
	(transit_state): Invoke check_subexp_matching_top.
	(check_subexp_matching_top): New function.
	(transit_state_bkref): Remove unused array.
	Merge transit_state_bkref_loop.
	(transit_state_bkref_loop): Use get_subexp instead of
	sift_states_backward.  Use search_cur_bkref_entry for optimization.
	Merge this function to transit_state_bkref.
	(get_subexp): New function.
	(get_subexp_sub): Likewise.
	(find_subexp_node): Likewise.
	(check_arrival): Likewise.
	(check_arrival_expand_ecl): Likewise.
	(check_arrival_expand_ecl_sub): Likewise.
	(expand_bkref_cache): Likewise.
	(match_ctx_init): Initialize new members.
	(match_ctx_clean): New function.
	(match_ctx_free): Release new members.
	(match_ctx_free_subtops): New function.
	(match_ctx_add_entry): Fix indent.
	(search_cur_bkref_entry): New function.
	(match_ctx_add_subtop): Likewise.
	(match_ctx_add_sublast): Likewise.

8 files changed, 1124 insertions, 394 deletions

diff --git a/ChangeLog b/ChangeLog
index d95decf6d4..10fea1df87 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,52 @@
+2002-11-27  Isamu Hasegawa  <isamu@yamato.ibm.com>
+
+	* posix/regcomp.c (parse_expression): Set the bit since the back
+	reference is used in the regular expression.
+	* posix/regex_internal.c (re_node_set_init_1): Make it clean in case
+	of malloc failure.
+	(re_node_set_init_copy): Likewise.
+	* posix/regex_internal.h (state_array_t): New structure.
+	(re_sub_match_last_t): Likewise.
+	(re_sub_match_top_t): Likewise.
+	(re_match_context_t): Add new members.
+	(re_dfa_t): Likewise.
+	* posix/regexec.c (re_search_internal): Invoke prune_impossible_nodes
+	to check the matching is really correct, and retry if failed.
+	Move the routin pruning the impossible nodes from here, ...
+	(prune_impossible_nodes): To this function.
+	(check_matching): Invoke check_subexp_matching_top, and replace
+	redundant checking with transit_state_bkref invocation.
+	(proceed_next_node): Replace strncmp with memcmp.  Reported by
+	Paolo Bonzini  <bonzini@gnu.org>.
+	(update_cur_sifted_state): Remove search_subexp invocation.
+	(search_subexp): Remove this function.
+	(check_dst_limits_calc_pos): Use search_cur_bkref_entry for
+	optimization.
+	(sift_states_bkref): Use search_cur_bkref_entry for optimization.
+	Remove unused invocation of match_ctx_add_entry.
+	(transit_state): Invoke check_subexp_matching_top.
+	(check_subexp_matching_top): New function.
+	(transit_state_bkref): Remove unused array.
+	Merge transit_state_bkref_loop.
+	(transit_state_bkref_loop): Use get_subexp instead of
+	sift_states_backward.  Use search_cur_bkref_entry for optimization.
+	Merge this function to transit_state_bkref.
+	(get_subexp): New function.
+	(get_subexp_sub): Likewise.
+	(find_subexp_node): Likewise.
+	(check_arrival): Likewise.
+	(check_arrival_expand_ecl): Likewise.
+	(check_arrival_expand_ecl_sub): Likewise.
+	(expand_bkref_cache): Likewise.
+	(match_ctx_init): Initialize new members.
+	(match_ctx_clean): New function.
+	(match_ctx_free): Release new members.
+	(match_ctx_free_subtops): New function.
+	(match_ctx_add_entry): Fix indent.
+	(search_cur_bkref_entry): New function.
+	(match_ctx_add_subtop): Likewise.
+	(match_ctx_add_sublast): Likewise.
+
 2002-11-25  Ulrich Drepper  <drepper@redhat.com>
 
 	* iconv/Makefile (tests): Remove tst-iconv4.c
diff --git a/nptl/sysdeps/i386/pthread_sigmask.c b/nptl/sysdeps/i386/pthread_sigmask.c
deleted file mode 100644
index aa071841db..0000000000
--- a/nptl/sysdeps/i386/pthread_sigmask.c
+++ /dev/null
@@ -1,38 +0,0 @@
-/* Copyright (C) 2002 Free Software Foundation, Inc.
-   This file is part of the GNU C Library.
-   Contributed by Ulrich Drepper <drepper@redhat.com>, 2002.
-
-   The GNU C Library is free software; you can redistribute it and/or
-   modify it under the terms of the GNU Lesser General Public
-   License as published by the Free Software Foundation; either
-   version 2.1 of the License, or (at your option) any later version.
-
-   The GNU C Library is distributed in the hope that it will be useful,
-   but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   Lesser General Public License for more details.
-
-   You should have received a copy of the GNU Lesser General Public
-   License along with the GNU C Library; if not, write to the Free
-   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
-   02111-1307 USA.  */
-
-#include <errno.h>
-#include <signal.h>
-#include <pthreadP.h>
-#include <tls.h>
-#include <sysdep.h>
-
-
-int
-pthread_sigmask (how, newmask, oldmask)
-     int how;
-     const sigset_t *newmask;
-     sigset_t *oldmask;
-{
-  int result = INTERNAL_SYSCALL (sigprocmask, 3, how, newmask, oldmask);
-
-  return (INTERNAL_SYSCALL_ERROR_P (result)
-	  ? INTERNAL_SYSCALL_ERRNO (result)
-	  : 0);
-}
diff --git a/nptl/sysdeps/pthread/pthread_sigmask.c b/nptl/sysdeps/pthread/pthread_sigmask.c
index 8ec7cf81ee..5b46c53715 100644
--- a/nptl/sysdeps/pthread/pthread_sigmask.c
+++ b/nptl/sysdeps/pthread/pthread_sigmask.c
@@ -17,8 +17,10 @@
    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
    02111-1307 USA.  */
 
+#include <errno.h>
 #include <signal.h>
 #include <pthreadP.h>
+#include <sysdep.h>
 
 
 int
@@ -40,5 +42,13 @@ pthread_sigmask (how, newmask, oldmask)
       newmask = &local_newmask;
     }
 
-  return sigprocmask (how, newmask, oldmask);
+#ifdef INTERNAL_SYSCALL
+  int result = INTERNAL_SYSCALL (sigprocmask, 3, how, newmask, oldmask);
+
+  return (INTERNAL_SYSCALL_ERROR_P (result)
+	  ? INTERNAL_SYSCALL_ERRNO (result)
+	  : 0);
+#else
+  return sigprocmask (how, newmask, oldmask) == -1 : errno : 0;
+#endif
 }
diff --git a/nptl/sysdeps/x86_64/pthread_sigmask.c b/nptl/sysdeps/x86_64/pthread_sigmask.c
deleted file mode 100644
index 802d61f819..0000000000
--- a/nptl/sysdeps/x86_64/pthread_sigmask.c
+++ /dev/null
@@ -1 +0,0 @@
-#include "../i386/pthread_sigmask.c"
diff --git a/posix/regcomp.c b/posix/regcomp.c
index c9c0d9eb37..28831fa409 100644
--- a/posix/regcomp.c
+++ b/posix/regcomp.c
@@ -1975,6 +1975,7 @@ parse_expression (regexp, preg, token, syntax, nest, err)
 	  *err = REG_ESUBREG;
 	  return NULL;
 	}
+      dfa->used_bkref_map |= 1 << (token->opr.idx - 1);
       new_idx = re_dfa_add_node (dfa, *token, 0);
       tree = create_tree (NULL, NULL, 0, new_idx);
       if (BE (new_idx == -1 || tree == NULL, 0))
diff --git a/posix/regex_internal.c b/posix/regex_internal.c
index a6d88ee07b..835406c60c 100644
--- a/posix/regex_internal.c
+++ b/posix/regex_internal.c
@@ -614,7 +614,10 @@ re_node_set_init_1 (set, elem)
   set->nelem = 1;
   set->elems = re_malloc (int, 1);
   if (BE (set->elems == NULL, 0))
-    return REG_ESPACE;
+    {
+      set->alloc = set->nelem = 0;
+      return REG_ESPACE;
+    }
   set->elems[0] = elem;
   return REG_NOERROR;
 }
@@ -661,7 +664,10 @@ re_node_set_init_copy (dest, src)
       dest->alloc = dest->nelem;
       dest->elems = re_malloc (int, dest->alloc);
       if (BE (dest->elems == NULL, 0))
-	return REG_ESPACE;
+	{
+	  dest->alloc = dest->nelem = 0;
+	  return REG_ESPACE;
+	}
       memcpy (dest->elems, src->elems, src->nelem * sizeof (int));
     }
   else
diff --git a/posix/regex_internal.h b/posix/regex_internal.h
index a49f4d9f2f..50867878ed 100644
--- a/posix/regex_internal.h
+++ b/posix/regex_internal.h
@@ -401,6 +401,39 @@ struct re_state_table_entry
   re_dfastate_t **array;
 };
 
+/* Array type used in re_sub_match_last_t and re_sub_match_top_t.  */
+
+typedef struct
+{
+  int next_idx;
+  int alloc;
+  re_dfastate_t **array;
+} state_array_t;
+
+/* Store information about the node NODE whose type is OP_CLOSE_SUBEXP.  */
+
+typedef struct
+{
+  int node;
+  int str_idx; /* The position NODE match at.  */
+  state_array_t path;
+} re_sub_match_last_t;
+
+/* Store information about the node NODE whose type is OP_OPEN_SUBEXP.
+   And information about the node, whose type is OP_CLOSE_SUBEXP,
+   corresponding to NODE is stored in LASTS.  */
+
+typedef struct
+{
+  int str_idx;
+  int node;
+  int next_last_offset;
+  state_array_t *path;
+  int alasts; /* Allocation size of LASTS.  */
+  int nlasts; /* The number of LASTS.  */
+  re_sub_match_last_t **lasts;
+} re_sub_match_top_t;
+
 struct re_backref_cache_entry
 {
   int node;
@@ -427,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
@@ -484,13 +520,15 @@ struct re_dfa_t
   int states_alloc;
   int init_node;
   int nbackref; /* The number of backreference in this dfa.  */
-  /* If this dfa has "multibyte node", which is a backreference or
-     a node which can accept multibyte character or multi character
-     collating element.  */
+  /* Bitmap expressing which backreference is used.  */
+  unsigned int used_bkref_map;
 #ifdef DEBUG
   char* re_str;
 #endif
   unsigned int has_plural_match : 1;
+  /* If this dfa has "multibyte node", which is a backreference or
+     a node which can accept multibyte character or multi character
+     collating element.  */
   unsigned int has_mb_node : 1;
 };
 typedef struct re_dfa_t re_dfa_t;
diff --git a/posix/regexec.c b/posix/regexec.c
index f7e0d7f062..de888592d2 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -45,10 +45,17 @@
 
 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
 				     re_string_t *input, int n);
+static void match_ctx_clean (re_match_context_t *mctx);
 static void match_ctx_free (re_match_context_t *cache);
+static void match_ctx_free_subtops (re_match_context_t *mctx);
 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
 					  int str_idx, int from, int to);
+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_init_state_context (reg_errcode_t *err,
 							 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_dfa_t *dfa,
 					  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 (re_dfa_t *dfa, re_dfastate_t **dst,
 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,
@@ -154,12 +163,40 @@ static reg_errcode_t transit_state_mb (const regex_t *preg,
 				       re_match_context_t *mctx);
 #endif /* RE_ENABLE_I18N */
 static reg_errcode_t transit_state_bkref (const regex_t *preg,
-					  re_dfastate_t *pstate,
+					  re_node_set *nodes,
 					  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);
+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);
+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,
+				    state_array_t *path, int top_node,
+				    int top_str, int last_node, int last_str,
+				    int fl_open);
+static reg_errcode_t check_arrival_add_next_nodes (const regex_t *preg,
+						   re_dfa_t *dfa,
+						   re_match_context_t *mctx,
+						   int str_idx,
+						   re_node_set *cur_nodes,
+						   re_node_set *next_nodes);
+static reg_errcode_t check_arrival_expand_ecl (re_dfa_t *dfa,
+					       re_node_set *cur_nodes,
+					       int ex_subexp, int fl_open);
+static reg_errcode_t check_arrival_expand_ecl_sub (re_dfa_t *dfa,
+						   re_node_set *dst_nodes,
+						   int target, int ex_subexp,
+						   int fl_open);
+static reg_errcode_t expand_bkref_cache (const regex_t *preg,
+					 re_match_context_t *mctx,
+					 re_node_set *cur_nodes, int cur_str,
+					 int last_str, int subexp_num,
+					 int fl_open);
 static re_dfastate_t **build_trtable (const regex_t *dfa,
 				      const re_dfastate_t *state,
 				      int fl_search);
@@ -590,7 +627,7 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
   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 +775,29 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
 		  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.  */
+		}
 	    }
+	  match_ctx_clean (&mctx);
 	}
-
       /* Update counter.  */
       match_first += incr;
       if (match_first < left_lim || right_lim < match_first)
@@ -759,66 +815,10 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
 
       /* 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 +843,90 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
   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);
+	  ret = sift_states_backward (preg, mctx, &sctx);
+	  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 +983,7 @@ check_matching (preg, mctx, fl_search, fl_longest_match)
     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 +997,20 @@ check_matching (preg, mctx, fl_search, fl_longest_match)
   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)
-		    {