From b5b7b9d2a8a3a69aad7f7249a634ebaf30f4ed2d Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Sun, 1 Nov 2020 16:31:38 +0900 Subject: [PATCH] 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. --- ChangeLog | 10 ++++++++++ lib/dfa.c | 5 ++++- 2 files changed, 14 insertions(+), 1 deletion(-) diff --git a/ChangeLog b/ChangeLog index b909746942..25c386e6c3 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,13 @@ +2020-11-01 Norihiro Tanaka + + 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 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; -- 2.39.5