Re: [BZ558] Part 1: more efficient lowering of {m,n}

[Paolo Bonzini <paolo dot bonzini at lu dot unisi dot ch>]

> Does this DTRT with say ([abcdefgh]){1,5}\1, e.g. when matching
> abcdee or abb? If yes, it would be good to have that in the testsuite
> too.

Yes, it does.  It is simply a different way of lowering: if matching a . 
failed, it is not productive to try the epsilon transition and try to 
match another one.

PCRE does this to lower repetitions of subexpressions, by the way.

> > Patch at 
> > http://sources.redhat.com/bugzilla/attachment.cgi?id=289&action=view
>
> Even if you put patches into bugzilla, please mail them as well to
> the mailing list.

Ok, here it is.

Paolo
2004-11-23  Paolo Bonzini  <bonzini@gnu.org>

	* regcomp.c (analyze_tree): Always call calc_epsdest.
	(calc_inveclosure): Use re_node_set_insert_last.
	(parse_dup_op): Lower X{1,5} to (X(X(X(XX?)?)?)?)?
	rather than X?X?X?X?X?.
	* regex_internal.h (re_node_set_insert_last): New declaration.
	* regex_internal.c (re_node_set_insert_last): New function.
	* PCRE.tests: Add testcases.

--- orig/lib/regcomp.c
+++ mod/lib/regcomp.c
@@ -1269,8 +1269,8 @@ analyze_tree (dfa, node)
     calc_first (dfa, node);
   if (node->next == -1)
     calc_next (dfa, node);
-  if (node->eclosure.nelem == 0)
-    calc_epsdest (dfa, node);
+  calc_epsdest (dfa, node);
+
   /* Calculate "first" etc. for the left child.  */
   if (node->left != NULL)
     {
@@ -1626,7 +1626,7 @@ calc_inveclosure (dfa)
       for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
 	{
 	  dest = dfa->eclosures[src].elems[idx];
-	  re_node_set_insert (dfa->inveclosures + dest, src);
+	  re_node_set_insert_last (dfa->inveclosures + dest, src);
 	}
     }
 }
@@ -2538,7 +2538,7 @@ parse_dup_op (elem, regexp, dfa, token, 
      reg_errcode_t *err;
 {
   re_token_t dup_token;
-  bin_tree_t *tree = NULL;
+  bin_tree_t *tree = NULL, *old_tree = NULL;
   int i, start, end, start_idx = re_string_cur_idx (regexp);
   re_token_t start_token = *token;
 
@@ -2598,12 +2598,14 @@ parse_dup_op (elem, regexp, dfa, token, 
       end = (token->type == OP_DUP_QUESTION) ? 1 : -1;
     }
 
+  fetch_token (token, regexp, syntax);
+
   /* Treat "<re>{0}*" etc. as "<re>{0}".  */
-  if (BE (elem == NULL, 0))
-    start = end = 0;
+  if (BE (elem == NULL || (start == 0 && end == 0), 0))
+    return NULL;
 
   /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}".  */
-  else if (BE (start > 0, 0))
+  if (BE (start > 0, 0))
     {
       tree = elem;
       for (i = 2; i <= start; ++i)
@@ -2613,52 +2615,41 @@ parse_dup_op (elem, regexp, dfa, token, 
 	  if (BE (elem == NULL || tree == NULL, 0))
 	    goto parse_dup_op_espace;
 	}
-    }
 
-  if (BE (end != start, 1))
-    {
-      dup_token.type = (end == -1 ? OP_DUP_ASTERISK : OP_DUP_QUESTION);
-      if (BE (start > 0, 0))
-	{
-          elem = duplicate_tree (elem, dfa);
-          if (BE (elem == NULL, 0))
-	    goto parse_dup_op_espace;
+      if (start == end)
+	return tree;
 
-          /* This subexpression will be marked as optional, so that
-             empty matches do not touch the registers.  */
-          mark_opt_subexp (elem, dfa);
-
-          /* Prepare the tree with the modifier.  */
-          elem = re_dfa_add_tree_node (dfa, elem, NULL, &dup_token);
-          tree = create_tree (dfa, tree, elem, CONCAT, 0);
-	}
-      else
-	{
-	  /* We do not need to duplicate the tree because we have not
-	     created it yet.  */
-          mark_opt_subexp (elem, dfa);
-          tree = elem = re_dfa_add_tree_node (dfa, elem, NULL, &dup_token);
-	}
+      /* Duplicate ELEM before it is marked optional.  */
+      elem = duplicate_tree (elem, dfa);
+      old_tree = tree;
+    }
+  else
+    old_tree = NULL;
+
+  mark_opt_subexp (elem, dfa);
+  dup_token.type = (end == -1 ? OP_DUP_ASTERISK : OP_DUP_QUESTION);
+  tree = re_dfa_add_tree_node (dfa, elem, NULL, &dup_token);
+  if (BE (tree == NULL, 0))
+    goto parse_dup_op_espace;
 
+  /* This loop is actually executed only when end != -1,
+     to rewrite <re>{0,n} as (<re>(<re>...<re>?)?)?...  We have
+     already created the start+1-th copy.  */
+  for (i = start + 2; i <= end; ++i)
+    {
+      elem = duplicate_tree (elem, dfa);
+      tree = create_tree (dfa, tree, elem, CONCAT, 0);
       if (BE (elem == NULL || tree == NULL, 0))
         goto parse_dup_op_espace;
 
-      /* This loop is actually executed only when end != -1,
-         to rewrite <re>{0,n} as <re>?<re>?<re>?...  We have
-         already created the start+1-th copy.  */
-      for (i = start + 2; i <= end; ++i)
-        {
-          elem = duplicate_tree (elem, dfa);
-          tree = create_tree (dfa, tree, elem, CONCAT, 0);
-          if (BE (elem == NULL || tree == NULL, 0))
-	    {
-	      *err = REG_ESPACE;
-	      return NULL;
-	    }
-        }
+      tree = re_dfa_add_tree_node (dfa, tree, NULL, &dup_token);
+      if (BE (tree == NULL, 0))
+        goto parse_dup_op_espace;
     }
 
-  fetch_token (token, regexp, syntax);
+  if (old_tree)
+    tree = create_tree (dfa, old_tree, tree, CONCAT, 0);
+
   return tree;
 
  parse_dup_op_espace:


--- orig/lib/regex_internal.c
+++ mod/lib/regex_internal.c
@@ -1250,6 +1250,33 @@ re_node_set_insert (set, elem)
   return 1;
 }
 
+/* Insert the new element ELEM to the re_node_set* SET.
+   SET should not already have any element greater than or equal to ELEM.
+   Return -1 if an error is occured, return 1 otherwise.  */
+
+static int
+re_node_set_insert_last (set, elem)
+     re_node_set *set;
+     int elem;
+{
+  int idx;
+
+  /* Realloc if we need.  */
+  if (set->alloc == set->nelem)
+    {
+      int *new_array;
+      set->alloc = (set->alloc + 1) * 2;
+      new_array = re_realloc (set->elems, int, set->alloc);
+      if (BE (new_array == NULL, 0))
+	return -1;
+      set->elems = new_array;
+    }
+
+  /* Insert the new element.  */
+  set->elems[set->nelem++] = elem;
+  return 1;
+}
+
 /* Compare two node sets SET1 and SET2.
    return 1 if SET1 and SET2 are equivalent, return 0 otherwise.  */
 


--- orig/lib/regex_internal.h
+++ mod/lib/regex_internal.h
@@ -667,6 +668,8 @@ static reg_errcode_t re_node_set_init_un
 static reg_errcode_t re_node_set_merge (re_node_set *dest,
 					const re_node_set *src) internal_function;
 static int re_node_set_insert (re_node_set *set, int elem) internal_function;
+static int re_node_set_insert_last (re_node_set *set,
+				    int elem) internal_function;
 static int re_node_set_compare (const re_node_set *set1,
 				const re_node_set *set2) internal_function;
 static int re_node_set_contains (const re_node_set *set, int elem) internal_function;



--- orig/testsuite/PCRE.tests
+++ mod/testsuite/PCRE.tests
@@ -2365,3 +2365,22 @@ No match
  0: bc123bc
  1: bc
  2: bc
+
+/^a{2,5}$/
+    aa
+ 0: aa
+    aaa
+ 0: aaa
+    aaaa
+ 0: aaaa
+    aaaaa
+ 0: aaaaa
+    *** Failers
+No match
+    a
+No match
+    b
+No match
+    aaaaab
+No match
+    aaaaaa