From c92426984828de1029fe72b3e0c252c1d551c2cb Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka Date: Tue, 2 Dec 2014 22:45:17 +0900 Subject: [PATCH 1/2] dfa: matching at next position or infinit loop in matching mode After failed to match in matching mode, dfa transits initial state when not allow newline or next state when allow new line instead of return NULL. That will cause next matching at position or infinit loop. By the way, theere is no affair for grep in order that it always uses not matching mode but searching mode. * src/dfa.c (dfaexec_main): After failed to match in matching mode return NULL instead of transition to next state. * tests/dfa-match: Add a new test. * tests/dfa-match-aux.c: Add a new program to drive the test. * tests/Makefile.am: Add a rule to build new test. * NEWS (Bug fixes): Mention it. --- NEWS | 6 +++++ src/dfa.c | 11 +++++--- tests/Makefile.am | 7 ++++-- tests/dfa-match | 45 +++++++++++++++++++++++++++++++++ tests/dfa-match-aux.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 132 insertions(+), 6 deletions(-) create mode 100755 tests/dfa-match create mode 100644 tests/dfa-match-aux.c diff --git a/NEWS b/NEWS index 6138c4e..8fe425c 100644 --- a/NEWS +++ b/NEWS @@ -2,6 +2,12 @@ GNU grep NEWS -*- outline -*- * Noteworthy changes in release ?.? (????-??-??) [?] +** Bug fixes + + dfa does not cause matched at an incorrect position or an infinite + loop even in matching mode. It is an internal bug so that grep always + use not matching mode but searching mode. + [bug present since "the beginning"] * Noteworthy changes in release 2.21 (2014-11-23) [stable] diff --git a/src/dfa.c b/src/dfa.c index 65862e8..4ab2b72 100644 --- a/src/dfa.c +++ b/src/dfa.c @@ -3498,13 +3498,16 @@ dfaexec_main (struct dfa *d, char const *begin, char *end, continue; } - if (p[-1] == eol && allow_nl) + if (p[-1] != eol || d->newlines[s1] < 0) { - s = d->newlines[s1]; - continue; + p = NULL; + goto done; } - s = 0; + if (allow_nl) + s = d->newlines[s1]; + else + s = 0; } done: diff --git a/tests/Makefile.am b/tests/Makefile.am index 217a731..67c165d 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -14,13 +14,15 @@ # You should have received a copy of the GNU General Public License # along with this program. If not, see . -check_PROGRAMS = get-mb-cur-max -AM_CPPFLAGS = -I$(top_builddir)/lib -I$(top_srcdir)/lib +check_PROGRAMS = get-mb-cur-max dfa-match-aux +AM_CPPFLAGS = -I$(top_builddir)/lib -I$(top_srcdir)/lib \ + -I$(top_srcdir)/src AM_CFLAGS = $(WARN_CFLAGS) $(WERROR_CFLAGS) # Tell the linker to omit references to unused shared libraries. AM_LDFLAGS = $(IGNORE_UNUSED_LIBRARIES_CFLAGS) LDADD = ../lib/libgreputils.a $(LIBINTL) ../lib/libgreputils.a +dfa_match_aux_LDADD = ../src/dfa.$(OBJEXT) $(LDADD) XFAIL_TESTS = triple-backref @@ -52,6 +54,7 @@ TESTS = \ count-newline \ dfa-coverage \ dfa-heap-overrun \ + dfa-match \ dfaexec-multibyte \ empty \ empty-line \ diff --git a/tests/dfa-match b/tests/dfa-match new file mode 100755 index 0000000..e956532 --- /dev/null +++ b/tests/dfa-match @@ -0,0 +1,45 @@ +#!/bin/sh +# This would fail for grep-2.21. + +# Copyright 2014 Free Software Foundation, Inc. + +# This program is free software: you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation, either version 3 of the License, or +# (at your option) any later version. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. + +# You should have received a copy of the GNU General Public License +# along with this program. If not, see . + +. "${srcdir=.}/init.sh"; path_prepend_ ../src + +# Add "." to PATH for the use of dfa-match-aux. +path_prepend_ . + +require_timeout_ + +fail=0 + +fail1=0 +dfa-match-aux a ba 0 > out || fail1=1 +compare /dev/null out || fail1=1 +if test $fail1 -ne 0; then + printf 'dfa-match test #1 failed\n' + fail=1 +fi + +fail2=0 +in=$(printf "bb\nbb") +timeout 3 dfa-match-aux a "$in" 1 > out || fail2=1 +compare /dev/null out || fail2=1 +if test $fail2 -ne 0; then + printf 'dfa-match test #2 failed\n' + fail=1 +fi + +Exit $fail diff --git a/tests/dfa-match-aux.c b/tests/dfa-match-aux.c new file mode 100644 index 0000000..c2918e0 --- /dev/null +++ b/tests/dfa-match-aux.c @@ -0,0 +1,69 @@ +/* Auxiliary program to test a code which can not happen for dfa. + Copyright 2014 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3, or (at your option) + any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA + 02110-1301, USA. */ + +#include +#include +#include +#include +#include +#include +#include + +#include "progname.h" + +void +dfaerror (char const *mesg) +{ + printf ("dfaerror: %s\n", mesg); + exit (EXIT_FAILURE); +} + +void +dfawarn (char const *mesg) +{ + printf ("dfawarn: %s\n", mesg); + exit (EXIT_FAILURE); +} + +int +main (int argc, char **argv) +{ + struct dfa *dfa; + char *beg, *end, *p; + int allow_nl; + + if (argc < 3) + exit (EXIT_FAILURE); + + setlocale (LC_ALL, ""); + + dfasyntax (RE_SYNTAX_GREP | RE_NO_EMPTY_RANGES, 0, '\n'); + dfa = dfaalloc (); + dfacomp (argv[1], strlen (argv[1]), dfa, 0); + + beg = argv[2]; + end = argv[2] + strlen (argv[2]); + allow_nl = argc > 3 && atoi (argv[3]); + + p = dfaexec (dfa, beg, end, allow_nl, NULL, NULL); + + if (p != NULL) + printf ("%zd\n", p - beg); + + exit (EXIT_SUCCESS); +} -- 2.2.0