Subject: Re: bug#44351: Bug in grep v3.2 onwards in regular expression matching

From: Norihiro Tanaka <[email-masked]>
Date: Sun, 01 Nov 2020 16:42:21 +0900

Example,

  a+a+a
  1 2 3

position 1 has a repetition of "a" and other transition with "a".
position 2 has a repetition of "a" and other transition with "a", too.
Then DFA was merging the two nodes, but it is wrong.

Now similar nodes in series are not merged.
From 88bad5597445650f4e1bca663a82d4e4d14c93f3 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sun, 1 Nov 2020 16:31:38 +0900
Subject: [PATCH] dfa: remain similar nodes in series in optimization

DFA was merging similar nodes illegally, example a+a+a as a+a.
Now similar nodes in series are not merged.

Problem reported by Gonzalo Padrino in:
https://lists.gnu.org/archive/html/bug-grep/2020-10/msg00015.html

* lib/dfa.c (merge_nfa_state): Skip the follow for repetition in
optimization.
---
 lib/dfa.c |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

diff --git a/lib/dfa.c b/lib/dfa.c
index 74aafa2..6d880c1 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2438,7 +2438,7 @@ merge_nfa_state (struct dfa *d, idx_t tindex, char *flags,
           continue;
         }
 
-      if (!(flags[sindex] & (OPT_LPAREN | OPT_RPAREN)))
+      if (sindex != tindex && !(flags[sindex] & (OPT_LPAREN | OPT_RPAREN)))
         {
           idx_t j;
 
@@ -2446,6 +2446,9 @@ merge_nfa_state (struct dfa *d, idx_t tindex, char *flags,
             {
               idx_t dindex = follows[tindex].elems[j].index;
 
+              if (dindex == tindex)
+                continue;
+
               if (follows[tindex].elems[j].constraint != iconstraint)
                 continue;
 
-- 
1.7.1

From 64333960e09591f27287eedecfd71a5f3dac8510 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sun, 1 Nov 2020 16:24:15 +0900
Subject: [PATCH] tests: add the test for bugfix in gnulib's dfa

* tests/ere.tests: Add new test.
---
 tests/ere.tests |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/tests/ere.tests b/tests/ere.tests
index 8ab6510..7d89508 100644
--- a/tests/ere.tests
+++ b/tests/ere.tests
@@ -218,3 +218,4 @@
 0@)@)
 1@)@x
 0@\()\((a\())(b))@()(a()b)
+1@a+a+a@aa
-- 
1.7.1