Update.

2002-12-17  Isamu Hasegawa  <isamu@yamato.ibm.com>

	* posix/regcomp.c (free_workarea_compile): Free the new member
	ORG_INDICES.
	(analyze): Initialize ORG_INDICES.
	(duplicate_node_closure): Search for a existing node, which is
	duplicated from the node ORG_DEST and satisfies the constraint
	CONSTRAINT.  And use it to avoid inifimite loop.
	(search_duplicated_node): New function.
	(duplicate_node): Store the index of the original node.
	* posix/regex_internal.c (re_dfa_add_node): Realloc ORG_INDICES
	if needed.
	* posix/regex_internal.h (re_dfa_t): Add new members.

3 files changed, 59 insertions, 16 deletions

diff --git a/posix/regcomp.c b/posix/regcomp.c
index 876c45c..97ec6e3 100644
--- a/posix/regcomp.c
+++ b/posix/regcomp.c
@@ -90,6 +90,8 @@ static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node,
 					     unsigned int constraint);
 static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx,
 				     unsigned int constraint);
+static int search_duplicated_node (re_dfa_t *dfa, int org_node,
+				   unsigned int constraint);
 static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
 static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
 					 int node, int root);
@@ -865,6 +867,8 @@ free_workarea_compile (preg)
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
   free_bin_tree (dfa->str_tree);
   dfa->str_tree = NULL;
+  re_free (dfa->org_indices);
+  dfa->org_indices = NULL;
 }
 
 /* Create initial states for all contexts.  */
@@ -959,10 +963,11 @@ analyze (dfa)
 
   /* Allocate arrays.  */
   dfa->nexts = re_malloc (int, dfa->nodes_alloc);
+  dfa->org_indices = re_malloc (int, dfa->nodes_alloc);
   dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
   dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
   dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc);
-  if (BE (dfa->nexts == NULL || dfa->edests == NULL
+  if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
 	  || dfa->eclosures == NULL || dfa->inveclosures == NULL, 0))
     return REG_ESPACE;
   /* Initialize them.  */
@@ -1261,20 +1266,33 @@ duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
       else /* dfa->edests[org_node].nelem == 2 */
 	{
 	  /* In case of the node can epsilon-transit, and it has two
-	     destinations.  */
+	     destinations. E.g. '|', '*', '+', '?'.   */
 	  org_dest = dfa->edests[org_node].elems[0];
 	  re_node_set_empty (dfa->edests + clone_node);
-	  err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
-	  if (BE (err != REG_NOERROR, 0))
-	    return err;
-	  ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
-	  if (BE (ret < 0, 0))
-	    return REG_ESPACE;
-
-	  err = duplicate_node_closure (dfa, org_dest, clone_dest, root_node,
-					constraint);
-	  if (BE (err != REG_NOERROR, 0))
-	    return err;
+	  /* Search for a duplicated node which satisfies the constraint.  */
+	  clone_dest = search_duplicated_node (dfa, org_dest, constraint);
+	  if (clone_dest == -1)
+	    {
+	      /* There are no such a duplicated node, create a new one.  */
+	      err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
+	      if (BE (err != REG_NOERROR, 0))
+		return err;
+	      ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+	      if (BE (ret < 0, 0))
+		return REG_ESPACE;
+	      err = duplicate_node_closure (dfa, org_dest, clone_dest,
+					    root_node, constraint);
+	      if (BE (err != REG_NOERROR, 0))
+		return err;
+	    }
+	  else
+	    {
+	      /* There are a duplicated node which satisfy the constraint,
+		 use it to avoid infinite loop.  */
+	      ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+	      if (BE (ret < 0, 0))
+		return REG_ESPACE;
+	    }
 
 	  org_dest = dfa->edests[org_node].elems[1];
 	  err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
@@ -1290,6 +1308,25 @@ duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
   return REG_NOERROR;
 }
 
+/* Search for a node which is duplicated from the node ORG_NODE, and
+   satisfies the constraint CONSTRAINT.  */
+
+static int
+search_duplicated_node (dfa, org_node, constraint)
+     re_dfa_t *dfa;
+     int org_node;
+     unsigned int constraint;
+{
+  int idx;
+  for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
+    {
+      if (org_node == dfa->org_indices[idx]
+	  && constraint == dfa->nodes[idx].constraint)
+	return idx; /* Found.  */
+    }
+  return -1; /* Not found.  */
+}
+
 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
    The new index will be stored in NEW_IDX and return REG_NOERROR if succeeded,
    otherwise return the error code.  */
@@ -1315,6 +1352,8 @@ duplicate_node (new_idx, dfa, org_idx, constraint)
   re_node_set_init_empty (dfa->eclosures + dup_idx);
   re_node_set_init_empty (dfa->inveclosures + dup_idx);
 
+  /* Store the index of the original node.  */
+  dfa->org_indices[dup_idx] = org_idx;
   *new_idx = dup_idx;
   return REG_NOERROR;
 }
diff --git a/posix/regex_internal.c b/posix/regex_internal.c
index a9559e2..a3ce236 100644
--- a/posix/regex_internal.c
+++ b/posix/regex_internal.c
@@ -986,19 +986,22 @@ re_dfa_add_node (dfa, token, mode)
 	dfa->nodes = new_array;
       if (mode)
 	{
-	  int *new_nexts;
+	  int *new_nexts, *new_indices;
 	  re_node_set *new_edests, *new_eclosures, *new_inveclosures;
 
 	  new_nexts = re_realloc (dfa->nexts, int, dfa->nodes_alloc);
+	  new_indices = re_realloc (dfa->org_indices, int, dfa->nodes_alloc);
 	  new_edests = re_realloc (dfa->edests, re_node_set, dfa->nodes_alloc);
 	  new_eclosures = re_realloc (dfa->eclosures, re_node_set,
 				      dfa->nodes_alloc);
 	  new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
 					 dfa->nodes_alloc);
-	  if (BE (new_nexts == NULL || new_edests == NULL
-		  || new_eclosures == NULL || new_inveclosures == NULL, 0))
+	  if (BE (new_nexts == NULL || new_indices == NULL
+		  || new_edests == NULL || new_eclosures == NULL
+		  || new_inveclosures == NULL, 0))
 	    return -1;
 	  dfa->nexts = new_nexts;
+	  dfa->org_indices = new_indices;
 	  dfa->edests = new_edests;
 	  dfa->eclosures = new_eclosures;
 	  dfa->inveclosures = new_inveclosures;
diff --git a/posix/regex_internal.h b/posix/regex_internal.h
index 5086787..ea04a6f 100644
--- a/posix/regex_internal.h
+++ b/posix/regex_internal.h
@@ -508,6 +508,7 @@ struct re_dfa_t
   int nodes_len;
   bin_tree_t *str_tree;
   int *nexts;
+  int *org_indices;
   re_node_set *edests;
   re_node_set *eclosures;
   re_node_set *inveclosures;