Re: grep bug report

[Jim Meyering]

Paolo Bonzini wrote:
> On 05/01/2011 01:34 PM, beaver wrote:
>> ~/openbsdlyrics $ echo `xclip -o`
>> http://www.openbsd.org/lyrics.html
>> ~/openbsdlyrics $ wget `xclip -o`
>> --2011-05-01 15:00:25--  http://www.openbsd.org/lyrics.html
>> Преобразование адреса www.openbsd.org... 142.244.12.42
>> Устанавливается соединение с www.openbsd.org|142.244.12.42|:80... 
>> соединились.
>> Запрос HTTP послан, ожидание ответа... 200 OK
>> Длина: 96396 (94K) [text/html]
>> Saving to: "lyrics.html"
>>
>> 100%[======================================>] 96 396      28,2K/s   в 3,3s
>>
>> 2011-05-01 15:00:30 (28,2 KB/s) - "lyrics.html" saved [96396/96396]
>>
>> ~/openbsdlyrics $ cat lyrics.html |grep -o "http[^>]*"|grep -o
>> "[^\"<]*"|grep "^http"|grep -P
>> "^http://(([a-zA-Z0-9-]+\.{0,1})*/{0,1})+(ogg|mp3)$"
>> Аварийный останов (core dumped)
>>
>> ~/openbsdlyrics $ uname -s -r -v -m -o
>> Linux 2.6.35-28-generic #50-Ubuntu SMP Fri Mar 18 19:00:26 UTC 2011
>> i686 GNU/Linux
>>
>> ~/openbsdlyrics $ grep -V
>> GNU grep 2.6.3
>>
>> Copyright (C) 2009 Free Software Foundation, Inc.
>> Лицензия GPLv3+: GNU GPL версии 3 или новее<http://gnu.org/licenses/gpl.html>
>> Это свободное ПО: вы можете продавать и распространять его.
>> Нет НИКАКИХ ГАРАНТИЙ до степени, разрешённой законом.
>
> I think the bug is in pcre.  Minimal testcase:
>
> echo aaaaaaaaaaaaaab | grep -P "((a+)*)+$"

Hi Paolo,

Thanks for the minimal test case.
Actually it's a bug in grep: it would abort when
encountering PCRE's PCRE_ERROR_MATCHLIMIT error code.
Here's some test clean-up, followed by the bug fix in 5/5.

Now, it does this:

    $ echo aaaaaaaaaaaaaab | ./grep -P '((a+)*)+$'
    ./grep: exceeded PCRE's backtracking limit

From 8e6d2371460706b0ad48ee476fb5cde7f4cd61ee Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Sat, 21 May 2011 12:08:11 +0200
Subject: [PATCH 1/5] tests: clean up pcre

* tests/pcre: Skip (don't pass) the test when PCRE support is disabled.
Don't redirect so much to /dev/null, now that all test output goes to
pcre.log.  Remove unnecessary braces and diagnostic about failing test.
---
 tests/pcre |    9 +++------
 1 files changed, 3 insertions(+), 6 deletions(-)

diff --git a/tests/pcre b/tests/pcre
index fbb2755..bec6e37 100644
--- a/tests/pcre
+++ b/tests/pcre
@@ -1,5 +1,5 @@
 #! /bin/sh
-# Regression test for GNU grep.
+# Ensure that with -P, \s*$ matches a newline.
 #
 # Copyright (C) 2001, 2006, 2009-2011 Free Software Foundation, Inc.
 #
@@ -10,14 +10,11 @@
 . "${srcdir=.}/init.sh"; path_prepend_ ../src

 # Test that grep was compiled with HAVE_LIBPCRE.  Otherwise, pass.
-echo . | grep -P . >/dev/null 2>&1 || exit 0
+echo . | grep -P . || skip_ no PCRE support

 fail=0
-ft=

 # See CVS revision 1.32 of "src/search.c".
-echo | { grep -P '\s*$'; } > /dev/null 2>&1 || { ft="$ft 1"; fail=1; }
-
-test "x$ft" != x && echo "Failed PCRE tests:$ft"
+echo | grep -P '\s*$' || fail=1

 Exit $fail
--
1.7.5.2.1.g56b30


From 2be2b8c044f8bd0fc6723004840029bd85078196 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Sat, 21 May 2011 12:13:08 +0200
Subject: [PATCH 2/5] tests: factor out a new require_pcre_ function

* tests/init.cfg (require_pcre_): New function, factored out of...
* tests/pcre-z: ...here.  Use the function.
* tests/pcre: Likewise.
---
 tests/init.cfg |    6 ++++++
 tests/pcre     |    4 +---
 tests/pcre-z   |    4 +---
 3 files changed, 8 insertions(+), 6 deletions(-)

diff --git a/tests/init.cfg b/tests/init.cfg
index baa2b40..4c9d2d3 100644
--- a/tests/init.cfg
+++ b/tests/init.cfg
@@ -43,6 +43,12 @@ require_timeout_()
     || skip_ your system lacks the timeout program
 }

+require_pcre_()
+{
+  echo . | grep -P . 2>err || skip_ no PCRE support
+  compare err /dev/null || fail_ PCRE available, but stderr not empty.
+}
+
 # Some tests would fail without this particular locale.
 # If the locale is not available, just skip the test.
 require_en_utf8_locale_()
diff --git a/tests/pcre b/tests/pcre
index bec6e37..a712d19 100644
--- a/tests/pcre
+++ b/tests/pcre
@@ -8,9 +8,7 @@
 # notice and this notice are preserved.

 . "${srcdir=.}/init.sh"; path_prepend_ ../src
-
-# Test that grep was compiled with HAVE_LIBPCRE.  Otherwise, pass.
-echo . | grep -P . || skip_ no PCRE support
+require_pcre_

 fail=0

diff --git a/tests/pcre-z b/tests/pcre-z
index d1d5dd7..94e9a78 100755
--- a/tests/pcre-z
+++ b/tests/pcre-z
@@ -1,9 +1,7 @@
 #!/bin/sh
 # Test Perl regex with NUL-separated input
 . "${srcdir=.}/init.sh"; path_prepend_ ../src
-
-echo a | grep -P a >/dev/null 2>err || skip_ 'PCRE not available.'
-compare err /dev/null || fail_ 'PCRE available, but stderr not empty.'
+require_pcre_

 REGEX=a

--
1.7.5.2.1.g56b30


From cda56673b41c68b525c46d0d1737cc53a125b274 Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Sat, 21 May 2011 12:19:09 +0200
Subject: [PATCH 3/5] tests: fix oddities in pcre-z

* tests/pcre-z: Redirect stderr inside $(), not outside.
Remove double quotes around $REGEX (which is just 'a') within
double-quoted "$(...)".  Split a long line.
---
 tests/pcre-z |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/tests/pcre-z b/tests/pcre-z
index 94e9a78..169c44e 100755
--- a/tests/pcre-z
+++ b/tests/pcre-z
@@ -11,7 +11,8 @@ grep -z "$REGEX" in > exp 2>err || fail_ 'Cannot do BRE (grep 
-z) match.'
 compare err /dev/null || fail_ 'stderr not empty on grep -z.'

 # Sanity check the output
-test "$(grep -cz "$REGEX" in)" 2>err = 3 || fail_ 'Incorrect BRE (grep -cz) 
match.'
+test "$(grep -cz $REGEX in 2>err)" = 3 \
+    || fail_ 'Incorrect BRE (grep -cz) match.'
 compare err /dev/null || fail_ 'stderr not empty on grep -cz.'

 fail=0
--
1.7.5.2.1.g56b30


From 2c1a222ec4a90219486f01efcd7d1cfd2ce6d30f Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Sat, 21 May 2011 12:26:47 +0200
Subject: [PATCH 4/5] tests: show how to make grep -P abort

* tests/pcre-abort: New file.
Minimal testcase by Paolo Bonzini, derived from a report
by address@hidden
* tests/Makefile.am (TESTS): Add it.
(XFAIL_TESTS): Add it here, too, since this test always fails, for now.
---
 tests/Makefile.am |    2 ++
 tests/pcre-abort  |   19 +++++++++++++++++++
 2 files changed, 21 insertions(+), 0 deletions(-)
 create mode 100755 tests/pcre-abort

diff --git a/tests/Makefile.am b/tests/Makefile.am
index 53314a8..6109832 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -33,6 +33,7 @@ if USE_INCLUDED_REGEX
 XFAIL_TESTS += equiv-classes
 endif
 XFAIL_TESTS += turkish-I
+XFAIL_TESTS += pcre-abort

 TESTS =                                                \
   backref                                      \
@@ -66,6 +67,7 @@ TESTS =                                               \
   high-bit-range                               \
   options                                      \
   pcre                                         \
+  pcre-abort                                   \
   pcre-z                                       \
   prefix-of-multibyte                          \
   reversed-range-endpoints                     \
diff --git a/tests/pcre-abort b/tests/pcre-abort
new file mode 100755
index 0000000..fd67932
--- /dev/null
+++ b/tests/pcre-abort
@@ -0,0 +1,19 @@
+#! /bin/sh
+# Show how to make grep -P abort.
+#
+# Copyright (C) 2011 Free Software Foundation, Inc.
+#
+# Copying and distribution of this file, with or without modification,
+# are permitted in any medium without royalty provided the copyright
+# notice and this notice are preserved.
+
+. "${srcdir=.}/init.sh"; path_prepend_ ../src
+require_pcre_
+
+fail=0
+
+echo aaaaaaaaaaaaaab > in || framework_failure_
+grep -P '((a+)*)+$' in > out || fail=1
+compare in out || fail=1
+
+Exit $fail
--
1.7.5.2.1.g56b30


From c079748fd59d5562633dcc11d971347c58413feb Mon Sep 17 00:00:00 2001
From: Jim Meyering <address@hidden>
Date: Sat, 21 May 2011 12:58:55 +0200
Subject: [PATCH 5/5] grep -P: don't abort upon exceeding PCRE's backtracking
 limit

* src/pcresearch.c (Pexecute): Handle PCRE_ERROR_MATCHLIMIT.
* tests/Makefile.am (XFAIL_TESTS): Remove pcre-abort.
* tests/pcre-abort: Expect failure, no output, and increase
the length of the input string, in case the backtracking limit
is ever raised.  Adjust comment.
* NEWS (Bug fixes): Mention it.
---
 NEWS              |    6 ++++++
 src/pcresearch.c  |    4 ++++
 tests/Makefile.am |    1 -
 tests/pcre-abort  |   10 ++++++----
 4 files changed, 16 insertions(+), 5 deletions(-)

diff --git a/NEWS b/NEWS
index 4dcee07..312c803 100644
--- a/NEWS
+++ b/NEWS
@@ -2,6 +2,12 @@ GNU grep NEWS                                    -*- outline 
-*-

 * Noteworthy changes in release ?.? (????-??-??) [?]

+** Bug fixes
+
+  grep -P no longer aborts when PCRE's backtracking limit is exceeded
+  Before, echo aaaaaaaaaaaaaab |grep -P '((a+)*)+$' would abort.  Now,
+  it diagnoses the problem and exits with status 2.
+

 * Noteworthy changes in release 2.8 (2011-05-13) [stable]

diff --git a/src/pcresearch.c b/src/pcresearch.c
index afb8a29..52db987 100644
--- a/src/pcresearch.c
+++ b/src/pcresearch.c
@@ -148,6 +148,10 @@ Pexecute (char const *buf, size_t size, size_t *match_size,
         case PCRE_ERROR_NOMEMORY:
           error (EXIT_TROUBLE, 0, _("memory exhausted"));

+        case PCRE_ERROR_MATCHLIMIT:
+          error (EXIT_TROUBLE, 0,
+                 _("exceeded PCRE's backtracking limit"));
+
         default:
           abort ();
         }
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 6109832..a01b004 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -33,7 +33,6 @@ if USE_INCLUDED_REGEX
 XFAIL_TESTS += equiv-classes
 endif
 XFAIL_TESTS += turkish-I
-XFAIL_TESTS += pcre-abort

 TESTS =                                                \
   backref                                      \
diff --git a/tests/pcre-abort b/tests/pcre-abort
index fd67932..131fa47 100755
--- a/tests/pcre-abort
+++ b/tests/pcre-abort
@@ -1,5 +1,6 @@
 #! /bin/sh
-# Show how to make grep -P abort.
+# Show that grep handles PCRE's PCRE_ERROR_MATCHLIMIT.
+# In grep-2.8, it would abort.
 #
 # Copyright (C) 2011 Free Software Foundation, Inc.
 #
@@ -12,8 +13,9 @@ require_pcre_

 fail=0

-echo aaaaaaaaaaaaaab > in || framework_failure_
-grep -P '((a+)*)+$' in > out || fail=1
-compare in out || fail=1
+echo aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab > in || framework_failure_
+grep -P '((a+)*)+$' in > out
+test $? = 2 || fail=1
+compare out /dev/null || fail=1

 Exit $fail
--
1.7.5.2.1.g56b30