Subject: bug#17204: closed (Re: bug#17204: [PATCH] grep: speed-up for exact matching with begline and endline constraints)

From: [email-masked] (GNU bug Tracking System)
Date: Mon, 21 Apr 2014 14:59:03 +0000

Your bug report

#17204: [PATCH] grep: speed-up for exact matching with begline and endline constraints

which was filed against the grep package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
17204: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=17204
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#17204: [PATCH] grep: speed-up for exact matching with begline and endline constraints
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>, [email-masked]
Date: Mon, 21 Apr 2014 07:58:43 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

Thanks, I looked at that, got derailed by finding and fixing a bug with 
NUL bytes that turned out to be a pre-existing bug, and finally 
installed it just now, with a slightly-reworded commit message.  I also 
installed the attached minor-improvement patch as well (some of it 
cleans up preexisting code in the neighborhood).
From 4af18dcace3879ac0b209e0a00babce45373568e Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 21 Apr 2014 07:27:14 -0700
Subject: [PATCH] dfa: minor improvements to previous patch

* src/dfa.c (dfamust): Use &=, not if-then.
* src/dfa.h (struct dfamust):
* src/dfasearch.c (begline, hwsmusts): Use bool for boolean.
* src/dfasearch.c (kwsmusts):
* src/kwsearch.c (Fcompile): Prefer decls after statements.
* src/dfasearch.c (kwsmusts): Avoid conditional branch.
* src/kwsearch.c (Fcompile): Unify the two calls to kwsincr.
---
 src/dfa.c       |  6 ++----
 src/dfa.h       |  7 ++++---
 src/dfasearch.c | 20 ++++++++------------
 src/kwsearch.c  | 17 ++++++++++-------
 4 files changed, 24 insertions(+), 26 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 0a6f061..65fc03d 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3916,10 +3916,8 @@ dfamust (struct dfa *d)
             /* Guaranteed to be.  Unlikely, but ...  */
             if (!STREQ (lmp->is, rmp->is))
               lmp->is[0] = '\0';
-            if (lmp->begline)
-              lmp->begline = rmp->begline;
-            if (lmp->endline)
-              lmp->endline = rmp->endline;
+            lmp->begline &= rmp->begline;
+            lmp->endline &= rmp->endline;
             /* Left side--easy */
             i = 0;
             while (lmp->left[i] != '\0' && lmp->left[i] == rmp->left[i])
diff --git a/src/dfa.h b/src/dfa.h
index 3829e6a..60aff11 100644
--- a/src/dfa.h
+++ b/src/dfa.h
@@ -19,15 +19,16 @@
 /* Written June, 1988 by Mike Haertel */
 
 #include <regex.h>
+#include <stdbool.h>
 #include <stddef.h>
 
 /* Element of a list of strings, at least one of which is known to
    appear in any R.E. matching the DFA. */
 struct dfamust
 {
-  int exact;
-  int begline;
-  int endline;
+  bool exact;
+  bool begline;
+  bool endline;
   char *must;
   struct dfamust *next;
 };
diff --git a/src/dfasearch.c b/src/dfasearch.c
index 34c4505..dc76397 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -51,7 +51,7 @@ static size_t pcount;
    call the regexp matcher at all. */
 static size_t kwset_exact_matches;
 
-static int begline;
+static bool begline;
 
 void
 dfaerror (char const *mesg)
@@ -87,25 +87,21 @@ kwsmusts (void)
   if (dm)
     {
       kwsinit (&kwset);
-      begline = 0;
       /* First, we compile in the substrings known to be exact
          matches.  The kwset matcher will return the index
          of the matching string that it chooses. */
       for (; dm; dm = dm->next)
         {
-          char *must, *mp;
-          size_t old_len, new_len;
           if (!dm->exact)
             continue;
           ++kwset_exact_matches;
-          old_len = strlen (dm->must);
-          new_len = old_len + dm->begline + dm->endline;
-          must = mp = xmalloc (new_len);
-          if (dm->begline)
-            {
-              (mp++)[0] = eolbyte;
-              begline = 1;
-            }
+          size_t old_len = strlen (dm->must);
+          size_t new_len = old_len + dm->begline + dm->endline;
+          char *must = xmalloc (new_len);
+          char *mp = must;
+          *mp = eolbyte;
+          mp += dm->begline;
+          begline |= dm->begline;
           memcpy (mp, dm->must, old_len);
           if (dm->endline)
             mp[old_len] = eolbyte;
diff --git a/src/kwsearch.c b/src/kwsearch.c
index 9904bfe..7c64c86 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -57,16 +57,19 @@ Fcompile (char const *pattern, size_t size)
           total = 0;
         }
 
+      char *buf = NULL;
       if (match_lines)
         {
-          char *buf = xmalloc (len + 2);
-          memcpy (&buf[1], p, len);
-          buf[0] = buf[len + 1] = eolbyte;
-          kwsincr (kwset, buf, len + 2);
-          free (buf);
+          buf = xmalloc (len + 2);
+          buf[0] = eolbyte;
+          memcpy (buf + 1, p, len);
+          buf[len + 1] = eolbyte;
+          p = buf;
+          len += 2;
         }
-      else
-        kwsincr (kwset, p, len);
+      kwsincr (kwset, p, len);
+      free (buf);
+
       p = sep;
     }
   while (p);
-- 
1.9.0

Subject: [PATCH] grep: speed-up for exact matching with begline and endline constraints
From: Norihiro Tanaka <[email-masked]>
To: [email-masked]
Date: Sun, 06 Apr 2014 18:55:03 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

dfamust turns on the flag when a state exactly matches the proposed one.
However, when the state has begline and/or endline constraints, turns
off it.

This patch enables to match a state exactly, even if the state has
begline and/or endline constraints.  If a exact string has one of their
constrations, the string adding eolbyte to a head and/or foot is pushed
to kwsincr().  In addition, if it has begline constration, start
searching from just before the position of the text.

Norihiro
From 642d6fed4310b3e4ee9569473b03e10dbee0e523 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Mon, 31 Mar 2014 21:51:48 +0900
Subject: [PATCH] grep: speed-up for exact matching with begline and endline
 constraints

dfamust turns on the flag when a state exactly matches the proposed one.
However, when the state has begline and/or endline constraints, turns
off it.

This patch enables to match a state exactly, even if the state has
begline and/or endline constraints.  If a exact string has one of their
constrations, the string adding eolbyte to a head and/or foot is pushed
to kwsincr().  In addition, if it has begline constration, start
searching from just before the position of the text.

* src/dfa.c (variable must): New members `begline' and `endline'.
(dfamust): Consideration of begline and endline constrations.
* src/dfa.h (struct dfamust): New members `begline' and `endline'.
* src/dfasearch.c (kwsmusts): If a exact string has begline constration,
start searching from just before the position of the text.
(EGexecute): Same as above.
* src/kwsearch.c (Fexecute): Same as above.
---
 src/dfa.c       | 40 +++++++++++++++++++++++++++++++++++-----
 src/dfa.h       |  2 ++
 src/dfasearch.c | 29 ++++++++++++++++++++++++-----
 src/kwsearch.c  | 32 +++++++++++++++++++-------------
 4 files changed, 80 insertions(+), 23 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index ef5c8a9..c4a3194 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3902,6 +3902,8 @@ typedef struct
   char *left;
   char *right;
   char *is;
+  int begline;
+  int endline;
 } must;
 
 static void
@@ -3920,6 +3922,8 @@ dfamust (struct dfa *d)
   size_t ri;
   size_t i;
   int exact;
+  int begline;
+  int endline;
   token t;
   static must must0;
   struct dfamust *dm;
@@ -3927,6 +3931,8 @@ dfamust (struct dfa *d)
 
   result = empty_string;
   exact = 0;
+  begline = 0;
+  endline = 0;
   MALLOC (musts, d->tindex + 1);
   mp = musts;
   for (i = 0; i <= d->tindex; ++i)
@@ -3939,6 +3945,8 @@ dfamust (struct dfa *d)
       mp[i].is = xmalloc (2);
       mp[i].left[0] = mp[i].right[0] = mp[i].is[0] = '\0';
       mp[i].in[0] = NULL;
+      mp[i].begline = 0;
+      mp[i].endline = 0;
     }
 #ifdef DEBUG
   fprintf (stderr, "dfamust:\n");
@@ -3953,12 +3961,18 @@ dfamust (struct dfa *d)
     {
       switch (t = d->tokens[ri])
         {
+        case BEGLINE:
+          resetmust (mp);
+          mp->begline = 1;
+          break;
+        case ENDLINE:
+          resetmust (mp);
+          mp->endline = 1;
+          break;
         case LPAREN:
         case RPAREN:
           assert (!"neither LPAREN nor RPAREN may appear here");
         case EMPTY:
-        case BEGLINE:
-        case ENDLINE:
         case BEGWORD:
         case ENDWORD:
         case LIMWORD:
@@ -3985,6 +3999,10 @@ dfamust (struct dfa *d)
             /* Guaranteed to be.  Unlikely, but ...  */
             if (!STREQ (lmp->is, rmp->is))
               lmp->is[0] = '\0';
+            if (lmp->begline)
+              lmp->begline = rmp->begline;
+            if (lmp->endline)
+              lmp->endline = rmp->endline;
             /* Left side--easy */
             i = 0;
             while (lmp->left[i] != '\0' && lmp->left[i] == rmp->left[i])
@@ -4021,7 +4039,11 @@ dfamust (struct dfa *d)
             if (strlen (musts[0].in[i]) > strlen (result))
               result = musts[0].in[i];
           if (STREQ (result, musts[0].is))
-            exact = 1;
+            {
+              exact = 1;
+              begline = musts[0].begline;
+              endline = musts[0].endline;
+            }
           goto done;
         case CAT:
           assert (&musts[2] <= mp);
@@ -4062,14 +4084,20 @@ dfamust (struct dfa *d)
             if (lmp->right == NULL)
               goto done;
             /* Guaranteed to be */
-            if (lmp->is[0] != '\0' && rmp->is[0] != '\0')
+            if ((lmp->is[0] != '\0' || lmp->begline)
+                && (rmp->is[0] != '\0' || rmp->endline))
               {
                 lmp->is = icatalloc (lmp->is, rmp->is);
                 if (lmp->is == NULL)
                   goto done;
+                lmp->endline = rmp->endline;
               }
             else
-              lmp->is[0] = '\0';
+              {
+                lmp->is[0] = '\0';
+                lmp->begline = 0;
+                lmp->endline = 0;
+              }
           }
           break;
         default:
@@ -4116,6 +4144,8 @@ done:
     {
       MALLOC (dm, 1);
       dm->exact = exact;
+      dm->begline = begline;
+      dm->endline = endline;
       dm->must = xmemdup (result, strlen (result) + 1);
       dm->next = d->musts;
       d->musts = dm;
diff --git a/src/dfa.h b/src/dfa.h
index 24fbcbe..7aa1b9a 100644
--- a/src/dfa.h
+++ b/src/dfa.h
@@ -26,6 +26,8 @@
 struct dfamust
 {
   int exact;
+  int begline;
+  int endline;
   char *must;
   struct dfamust *next;
 };
diff --git a/src/dfasearch.c b/src/dfasearch.c
index ca00505..f0ab4a8 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -51,6 +51,8 @@ static size_t pcount;
    call the regexp matcher at all. */
 static size_t kwset_exact_matches;
 
+static int begline;
+
 void
 dfaerror (char const *mesg)
 {
@@ -92,16 +94,31 @@ kwsmusts (void)
     {
       char const *err;
       kwsinit (&kwset);
+      begline = 0;
       /* First, we compile in the substrings known to be exact
          matches.  The kwset matcher will return the index
          of the matching string that it chooses. */
       for (; dm; dm = dm->next)
         {
+          char *must, *mp;
+          size_t old_len, new_len;
           if (!dm->exact)
             continue;
           ++kwset_exact_matches;
-          if ((err = kwsincr (kwset, dm->must, strlen (dm->must))) != NULL)
+          old_len = strlen (dm->must);
+          new_len = old_len + dm->begline + dm->endline;
+          must = mp = xmalloc (new_len);
+          if (dm->begline)
+            {
+              (mp++)[0] = eolbyte;
+              begline = 1;
+            }
+          memcpy (mp, dm->must, old_len);
+          if (dm->endline)
+            mp[old_len] = eolbyte;
+          if ((err = kwsincr (kwset, must, new_len)) != NULL)
             error (EXIT_TROUBLE, 0, "%s", err);
+          free (must);
         }
       /* Now, we compile the substrings that will require
          the use of the regexp matcher.  */
@@ -223,7 +240,8 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
           if (kwset)
             {
               /* Find a possible match using the KWset matcher. */
-              size_t offset = kwsexec (kwset, beg, buflim - beg, &kwsm);
+              size_t offset = kwsexec (kwset, beg - begline,
+                                       buflim - beg + begline, &kwsm);
               if (offset == (size_t) -1)
                 goto failure;
               beg += offset;
@@ -239,11 +257,12 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
               char const *dfa_start = beg;
               if (kwsm.index < kwset_exact_matches)
                 {
+                  if (MB_CUR_MAX == 1)
+                    goto success;
                   if (mb_start < beg)
                     mb_start = beg;
-                  if (MB_CUR_MAX == 1
-                      || !is_mb_middle (&mb_start, match, buflim,
-                                        kwsm.size[0]))
+                  if (!is_mb_middle (&mb_start, match, buflim,
+                                     kwsm.size[0] - begline))
                     goto success;
                   /* The matched line starts in the middle of a multibyte
                      character.  Perform the DFA search starting from the
diff --git a/src/kwsearch.c b/src/kwsearch.c
index dd01518..1e471d0 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -65,8 +65,20 @@ Fcompile (char const *pattern, size_t size)
 #endif
         }
 
-      if ((err = kwsincr (kwset, beg, end - beg)) != NULL)
-        error (EXIT_TROUBLE, 0, "%s", err);
+      if (match_lines)
+        {
+          char *new_beg = xmalloc (end - beg + 2);
+          new_beg[0] = new_beg[end - beg + 1] = eolbyte;
+          memcpy (&new_beg[1], beg, end - beg);
+          if ((err = kwsincr (kwset, new_beg, end - beg + 2)) != NULL)
+            error (EXIT_TROUBLE, 0, "%s", err);
+          free (new_beg);
+        }
+      else
+        {
+          if ((err = kwsincr (kwset, beg, end - beg)) != NULL)
+            error (EXIT_TROUBLE, 0, "%s", err);
+        }
       beg = lim;
     }
   while (beg < pat + psize);
@@ -119,11 +131,11 @@ Fexecute (char const *buf, size_t size, size_t *match_size,
 
   for (mb_start = beg = start_ptr ? start_ptr : buf; beg <= buf + size; beg++)
     {
-      size_t offset = kwsexec (kwset, beg, buf + size - beg, &kwsmatch);
+      size_t offset = kwsexec (kwset, beg - match_lines, buf + size - beg + match_lines, &kwsmatch);
       if (offset == (size_t) -1)
         goto failure;
-      len = kwsmatch.size[0];
-      if (MB_CUR_MAX > 1
+      len = kwsmatch.size[0] - match_lines;
+      if (MB_CUR_MAX > 1 && !match_lines
           && is_mb_middle (&mb_start, beg + offset, buf + size, len))
         {
           /* The match was a part of multibyte character, advance at least
@@ -140,14 +152,8 @@ Fexecute (char const *buf, size_t size, size_t *match_size,
       if (start_ptr && !match_words)
         goto success_in_beg_and_len;
       if (match_lines)
-        {
-          if (beg > buf && beg[-1] != eol)
-            continue;
-          if (beg + len < buf + size && beg[len] != eol)
-            continue;
-          goto success;
-        }
-      else if (match_words)
+        goto success_in_beg_and_len;
+      if (match_words)
         for (try = beg; ; )
           {
             if (try > buf && WCHAR(to_uchar (try[-1])))
-- 
1.9.1