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

From: Norihiro Tanaka <[email-masked]>
Date: Sat, 12 Apr 2014 09:13:00 +0900

I rebased this patch because of confliction in src/kwsearch.c.
From 086fd579726f9956e04b8d04db92ef780c0ae850 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  | 27 +++++++++++++++------------
 4 files changed, 76 insertions(+), 22 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index a3cfa8d..15099aa 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -4018,6 +4018,8 @@ typedef struct
   char *left;
   char *right;
   char *is;
+  bool begline;
+  bool endline;
 } must;
 
 static void
@@ -4036,6 +4038,8 @@ dfamust (struct dfa *d)
   size_t ri;
   size_t i;
   bool exact;
+  bool begline;
+  bool endline;
   token t;
   static must must0;
   struct dfamust *dm;
@@ -4043,6 +4047,8 @@ dfamust (struct dfa *d)
 
   result = empty_string;
   exact = false;
+  begline = false;
+  endline = false;
   MALLOC (musts, d->tindex + 1);
   mp = musts;
   for (i = 0; i <= d->tindex; ++i)
@@ -4055,6 +4061,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 = false;
+      mp[i].endline = false;
     }
 #ifdef DEBUG
   fprintf (stderr, "dfamust:\n");
@@ -4069,12 +4077,18 @@ dfamust (struct dfa *d)
     {
       switch (t = d->tokens[ri])
         {
+        case BEGLINE:
+          resetmust (mp);
+          mp->begline = true;
+          break;
+        case ENDLINE:
+          resetmust (mp);
+          mp->endline = true;
+          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:
@@ -4101,6 +4115,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])
@@ -4137,7 +4155,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 = true;
+            {
+              exact = true;
+              begline = musts[0].begline;
+              endline = musts[0].endline;
+            }
           goto done;
         case CAT:
           assert (&musts[2] <= mp);
@@ -4178,14 +4200,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 = false;
+                lmp->endline = false;
+              }
           }
           break;
         default:
@@ -4232,6 +4260,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 db29a62..3829e6a 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 1266c80..34c4505 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)
 {
@@ -85,15 +87,30 @@ 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;
-          kwsincr (kwset, dm->must, strlen (dm->must));
+          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;
+          kwsincr (kwset, must, new_len);
+          free (must);
         }
       /* Now, we compile the substrings that will require
          the use of the regexp matcher.  */
@@ -212,7 +229,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;
@@ -225,11 +243,12 @@ EGexecute (char const *buf, size_t size, size_t *match_size,
               beg = beg ? beg + 1 : buf;
               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 5f3f233..ed90a33 100644
--- a/src/kwsearch.c
+++ b/src/kwsearch.c
@@ -57,7 +57,16 @@ Fcompile (char const *pattern, size_t size)
           total = 0;
         }
 
-      kwsincr (kwset, p, len);
+      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);
+        }
+      else
+        kwsincr (kwset, p, len);
       p = sep;
     }
   while (p);
@@ -109,11 +118,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
@@ -130,14 +139,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.2