Subject: bug#21670: surprising bug in grep -e with anchors

From: Norihiro Tanaka <[email-masked]>
Date: Tue, 13 Oct 2015 22:30:03 +0900

On Sun, 11 Oct 2015 21:34:05 -0700
Paul Eggert <[email-masked]> wrote:

> greg boyd wrote:
> > test case (single line)
> > abchelloabc
> >
> > grep does not find the line with grep -e '^hello'  nor with grep -e 'hello$'
> > however, the line is output with
> > grep -e '^hello' -e 'hello$'
> 
> Oooo, that's a good one.  Give your student extra credit!  As it happens, the bug was recently fixed by this patch by Norihiro Tanaka:
> 
> http://git.savannah.gnu.org/cgit/grep.git/commit/?id=256a4b494fe1c48083ba73b4f62607234e4fefd5
> 
> and the fix should appear in the next grep release.  However, since the patch was supposed to affect only performance, it appears that the bug fix was due to luck, and I'm taking the liberty of adding your student's test case by installing the attached further patch, to help prevent this bug from coming back in a future version.

I found above patch is also buggy.  It is never fix.  It returns shorter
`must' than expected.  e.g. `must' for pattern `.hello' is `hello', but
returns `hell' by this bug.  Next, `must' for pattern `^hello' is `hello'
but returns `hell'.  It will cause slite performance down, and disappear
bug#21670,  BTW, I guess the bug does not change external behavior.

First patch fixes the bug.  After the patch is applied, bug#21670
appears again.  And, second patch fixes bug#21670.

When pattern has ^ and/or $, if begline and/or endline flag of mp is
turned off, EXACT should be false.
From d4f86e62c854f323feccea76889d2298a5f335d4 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Tue, 13 Oct 2015 11:43:49 +0900
Subject: [PATCH 1/2] dfa: don't use DFA for exact matching

If a pattern constraint beginning of line a pattern, DFA is used after
matched in KWset, even when it is exact.  The behavior is not expected.
Now, whenever a pattern is exact, DFA is not used.

* src/dfa.c (dfamust): Don't use DFA for exact matching.
---
 src/dfa.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/dfa.c b/src/dfa.c
index ac5129b..5b9a4fe 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -4135,7 +4135,7 @@ dfamust (struct dfa const *d)
                 = case_fold && MB_CUR_MAX == 1 ? toupper (t) : t;
             }
           mp->is[i] = mp->left[i] = mp->right[i] = '\0';
-          mp->in = enlist (mp->in, mp->is, i - 1);
+          mp->in = enlist (mp->in, mp->is, i);
           break;
         }
     }
-- 
2.4.1

From 3be0bc551387911faf98d89dc076f39561a753f3 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Tue, 13 Oct 2015 01:19:43 +0900
Subject: [PATCH 2/2] dfa: fix bug in alternate of sub-patterns different in
 only the constraints

A line may incorrectly matches alternate of sub-patterns different in
only the constraints e.g. ^a|a$ in extended regular expression.  This
change fixes the bug.  Reported by Greg Boyd in
http://debbugs.gnu.org/21670

* src/dfa.c (dfamust): For a pattern with constraints, check that it is
matched including the constraints, to judge whether it is exact.
---
 src/dfa.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/src/dfa.c b/src/dfa.c
index 5b9a4fe..cdea4e5 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3940,6 +3940,8 @@ dfamust (struct dfa const *d)
   bool exact = false;
   bool begline = false;
   bool endline = false;
+  bool need_begline = false;
+  bool need_endline = false;
 
   for (size_t ri = 0; ri < d->tindex; ++ri)
     {
@@ -3949,10 +3951,12 @@ dfamust (struct dfa const *d)
         case BEGLINE:
           mp = allocmust (mp, 2);
           mp->begline = true;
+          need_begline = true;
           break;
         case ENDLINE:
           mp = allocmust (mp, 2);
           mp->endline = true;
+          need_endline = true;
           break;
         case LPAREN:
         case RPAREN:
@@ -4029,7 +4033,9 @@ dfamust (struct dfa const *d)
               result = mp->in[i];
           if (STREQ (result, mp->is))
             {
-              exact = true;
+              if ((!need_begline || mp->begline) && (!need_endline
+                                                     || mp->endline))
+                exact = true;
               begline = mp->begline;
               endline = mp->endline;
             }
-- 
2.4.1