dfa: don't overrun a malloc'd buffer for certain regexps

* src/dfa.c (dfaanalyze): Allocate space for twice as many
positions as there are leaves.  Before this change, for some
regular expressions, DFA analysis would have inserted far more
"positions" than dfa->nleaves (up to double).
Reported by Raymond Russell in http://savannah.gnu.org/bugs/?33547
* tests/dfa-heap-overrun: Trigger the overrun.
* tests/Makefile.am (TESTS): Add it.
* NEWS (Bug fixes): Mention it.

1 files changed, 26 insertions, 0 deletions

diff --git a/tests/dfa-heap-overrun b/tests/dfa-heap-overrun
new file mode 100755
index 00000000..dda1c12b
--- /dev/null
+++ b/tests/dfa-heap-overrun
@@ -0,0 +1,26 @@
+#!/bin/sh
+# Trigger a heap overrun in grep-2.6..grep-2.8.
+
+# Copyright (C) 2011 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 <http://www.gnu.org/licenses/>.
+
+. "${srcdir=.}/init.sh"; path_prepend_ ../src
+
+fail=0
+
+grep -E '(^| )*(a|b)*(c|d)*( |$)' < /dev/null
+test $? = 1 || fail=1
+
+Exit $fail