dfa: retain sequences of similar nodes in optimization

DFA was merging similar nodes when it should not.  For example,
it would convert a+a+a to a+a.  Now, a sequence of similar nodes
is not merged.

Problem reported by Gonzalo Padrino in https://bugs.gnu.org/44351

* lib/dfa.c (merge_nfa_state): Skip the follow for repetition in
optimization.

2 files changed, 14 insertions, 1 deletions

diff --git a/ChangeLog b/ChangeLog
index b909746942..25c386e6c3 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2020-11-01  Norihiro Tanaka  <noritnk@kcn.ne.jp>
+
+	dfa: retain sequences of similar nodes in optimization
+	DFA was merging similar nodes when it should not.  For example,
+	it would convert a+a+a to a+a.  Now, a sequence of similar nodes
+	is not merged.  Problem reported by Gonzalo Padrino in
+	https://bugs.gnu.org/44351
+	* lib/dfa.c (merge_nfa_state): Skip the follow for repetition in
+	optimization.
+
 2020-11-01  Jim Meyering  <meyering@fb.com>
 
 	test-dfa-match-aux.c: accept EREs, not BREs
diff --git a/lib/dfa.c b/lib/dfa.c
index 74aafa2ee9..6d880c1331 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;