Subject: bug#26864: Clarification on obscure regular expressions mentioned in known bugs

From: Paul Eggert <[email-masked]>
Date: Mon, 30 Dec 2019 01:01:21 -0800

On 5/10/17 1:48 AM, Sundeep Agarwal wrote:

> my question is whether these regular expression examples come under
> 'obscure regular expressions' mentioned in the man page.

No, they're bugs in grep's regular expression implementation, which is taken
from glibc. I filed a bug report against glibc here:

https://sourceware.org/bugzilla/show_bug.cgi?id=25322

and installed the attached patches to GNU grep to try to document this mess
better. The first patch is the important one; the other two merely standardize
spelling and fix a typo in the first patch. Thanks for reporting the problem.
>From eac1e4d50a73bb33c35e5f9f95a201e22d295827 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 30 Dec 2019 00:48:20 -0800
Subject: [PATCH 1/3] doc: mention back-reference bugs

Inspired by Bug#26864.
* doc/grep.texi (Known Bugs): New section.
Mention back-reference issues.
---
 doc/grep.texi | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/doc/grep.texi b/doc/grep.texi
index 42832ab..8866ec4 100644
--- a/doc/grep.texi
+++ b/doc/grep.texi
@@ -1536,6 +1536,8 @@ When multiple regular expressions are given with
 @option{-e} or from a file (@samp{-f @var{file}}),
 back-references are local to each expression.
 
+@xref{Known Bugs}, for some known problems with back-references.
+
 @node Basic vs Extended
 @section Basic vs Extended Regular Expressions
 @cindex basic regular expressions
@@ -1965,6 +1967,11 @@ GNU bug report logs for @command{grep}}.
 If you find a bug not listed there, please email it to
 @email{bug-grep@@gnu.org} to create a new bug report.
 
+@menu
+* Known Bugs::
+@end menu
+
+@node Known Bugs
 @section Known Bugs
 @cindex Bugs, known
 
@@ -1974,7 +1981,17 @@ In addition, certain other
 obscure regular expressions require exponential time and
 space, and may cause @command{grep} to run out of memory.
 
-Back-references are very slow, and may require exponential time.
+Back-references can greatly slow down matching, as they can generate
+exponentially many matching possibilities that can consume both time
+and memory to explore.  Also, the POSIX specification for
+back-references is at times unclear.  Furthermore, many regular
+expression implementations have back-reference bugs that can cause
+programs to return incorrect answers or even crash, and fixing these
+bugs has often been low-priority---for example, as of 2019 the GNU C
+library bug database contained back-reference bugs 52, 10844, 11053,
+and 23522, with little sign of forthcoming fixes.  Luckily,
+back-references are rarely useful and it should be little trouble to
+avoid them in practical applications.

 @node Copying
-- 
2.17.1

>From bc5ac38040eb49c751e39700651f2b98cd866228 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 30 Dec 2019 00:52:10 -0800
Subject: [PATCH 2/3] doc: spell "back-reference" more consistently

---
 NEWS                  | 12 ++++++------
 README                |  2 +-
 doc/grep.in.1         |  2 +-
 src/dfasearch.c       | 12 ++++++------
 tests/backref         |  2 +-
 tests/pcre-wx-backref |  2 +-
 tests/tests           |  4 ++--
 7 files changed, 18 insertions(+), 18 deletions(-)

diff --git a/NEWS b/NEWS
index 4f04ec3..e4083a1 100644
--- a/NEWS
+++ b/NEWS
@@ -22,7 +22,7 @@ GNU grep NEWS                                    -*- outline -*-
   [Bug#37716 introduced in grep 3.2]
 
   A performance bug has been fixed when grep is given many patterns,
-  each with no backreference.
+  each with no back-reference.
   [Bug#33249 introduced in grep 2.5]
 
   A performance bug has been fixed for patterns like '01.2' that
@@ -47,7 +47,7 @@ GNU grep NEWS                                    -*- outline -*-
   the following would print nothing (it should print the input line):
     echo 123-x|LC_ALL=C grep '.\bx'
   Using a multibyte locale, using certain regexp constructs (some ranges,
-  backreferences), or forcing use of the PCRE matcher via --perl-regexp (-P)
+  back-references), or forcing use of the PCRE matcher via --perl-regexp (-P)
   would avoid the bug.
   [bug introduced in grep 3.2]
 
@@ -240,7 +240,7 @@ GNU grep NEWS                                    -*- outline -*-
 
   grep -z would match strings it should not.  To trigger the bug, you'd
   have to use a regular expression including an anchor (^ or $) and a
-  feature like a range or a backreference, causing grep to forego its DFA
+  feature like a range or a back-reference, causing grep to forego its DFA
   matcher and resort to using re_search.  With a multibyte locale, that
   matcher could mistakenly match a string containing a newline.
   For example, this command:
@@ -473,7 +473,7 @@ GNU grep NEWS                                    -*- outline -*-
   Previously it was unreliable, and sometimes crashed or looped.
   [bug introduced in grep-2.16]
 
-  grep -P now works with -w and -x and backreferences. Before,
+  grep -P now works with -w and -x and back-references. Before,
   echo aa|grep -Pw '(.)\1' would fail to match, yet
   echo aa|grep -Pw '(.)\2' would match.
 
@@ -809,7 +809,7 @@ GNU grep NEWS                                    -*- outline -*-
   X{0,0} is implemented correctly.  It used to be a synonym of X{0,1}.
   [bug present since "the beginning"]
 
-  In multibyte locales, regular expressions including backreferences
+  In multibyte locales, regular expressions including back-references
   no longer exhibit quadratic complexity (i.e., they are orders
   of magnitude faster). [bug present since multi-byte character set
   support was introduced in 2.5.2]
@@ -967,7 +967,7 @@ Version 2.5
   - The new option --line-buffered fflush on everyline.  There is a noticeable
     slow down when forcing line buffering.
 
-  - Back references  are now local to the regex.
+  - Back-references are now local to the regex.
     grep -e '\(a\)\1' -e '\(b\)\1'
     The last backref \1 in the second expression refer to \(b\)
 
diff --git a/README b/README
index 0120973..2c15d9b 100644
--- a/README
+++ b/README
@@ -17,7 +17,7 @@ twice as fast as stock Unix egrep) hybridized with a Boyer-Moore-Gosper
 search for a fixed string that eliminates impossible text from being
 considered by the full regexp matcher without necessarily having to
 look at every character.  The result is typically many times faster
-than Unix grep or egrep.  (Regular expressions containing backreferencing
+than Unix grep or egrep.  (Regular expressions containing back-references
 will run more slowly, however.)
 
 See the files AUTHORS and THANKS for a list of authors and other contributors.
diff --git a/doc/grep.in.1 b/doc/grep.in.1
index a91b2a6..e095d5c 100644
--- a/doc/grep.in.1
+++ b/doc/grep.in.1
@@ -920,7 +920,7 @@ Repetition takes precedence over concatenation, which in turn
 takes precedence over alternation.
 A whole expression may be enclosed in parentheses
 to override these precedence rules and form a subexpression.
-.SS "Back References and Subexpressions"
+.SS "Back-references and Subexpressions"
 The back-reference
 .BI \e n\c
 \&, where
diff --git a/src/dfasearch.c b/src/dfasearch.c
index b1a242a..0160d71 100644
--- a/src/dfasearch.c
+++ b/src/dfasearch.c
@@ -103,8 +103,8 @@ kwsmusts (struct dfa_comp *dc)
   dfamustfree (dm);
 }
 
-/* Return true if KEYS, of length LEN, might contain a backreference.
-   Return false if KEYS cannot contain a backreference.
+/* Return true if KEYS, of length LEN, might contain a back-reference.
+   Return false if KEYS cannot contain a back-reference.
    BS_SAFE is true of encodings where a backslash cannot appear as the
    last byte of a multibyte character.  */
 static bool _GL_ATTRIBUTE_PURE
@@ -116,13 +116,13 @@ possible_backrefs_in_pattern (char const *keys, ptrdiff_t len, bool bs_safe)
      multibyte character.  */
   int second_backslash = bs_safe ? '\\' : CHAR_MAX + 1;
 
-  /* This code can return true even if KEYS lacks a backreference, for
+  /* This code can return true even if KEYS lacks a back-reference, for
      patterns like [\2], or for encodings where '\' appears as the last
      byte of a multibyte character.  However, false alarms should be
      rare and do not affect correctness.  */
 
   /* Do not look for a backslash in the pattern's last byte, since it
-     can't be part of a backreference and this streamlines the code.  */
+     can't be part of a back-reference and this streamlines the code.  */
   len--;
 
   if (0 <= len)
@@ -204,7 +204,7 @@ GEAcompile (char *pattern, size_t size, reg_syntax_t syntax_bits)
 
   char const *prev = pattern;
 
-  /* Buffer containing backreference-free patterns.  */
+  /* Buffer containing back-reference-free patterns.  */
   char *buf = NULL;
   ptrdiff_t buflen = 0;
   size_t bufalloc = 0;
@@ -449,7 +449,7 @@ EGexecute (void *vdc, char const *buf, size_t size, size_t *match_size,
           end = memchr (next_beg, eol, buflim - next_beg);
           end = end ? end + 1 : buflim;
 
-          /* Successful, no backreferences encountered! */
+          /* Successful, no back-references encountered! */
           if (!backref)
             goto success;
           ptr = beg;
diff --git a/tests/backref b/tests/backref
index eaa16cf..384b7ca 100755
--- a/tests/backref
+++ b/tests/backref
@@ -1,5 +1,5 @@
 #! /bin/sh
-# Test for backreferences and other things.
+# Test for back-references and other things.
 #
 # Copyright (C) 2001, 2006, 2009-2019 Free Software Foundation, Inc.
 #
diff --git a/tests/pcre-wx-backref b/tests/pcre-wx-backref
index 63536f9..b63009a 100755
--- a/tests/pcre-wx-backref
+++ b/tests/pcre-wx-backref
@@ -1,5 +1,5 @@
 #! /bin/sh
-# Before grep-2.19, grep -P and -w/-x would not with a backreference.
+# Before grep-2.19, grep -P and -w/-x would not work with a back-reference.
 #
 # Copyright (C) 2014-2019 Free Software Foundation, Inc.
 #
diff --git a/tests/tests b/tests/tests
index af9ae8a..f95c28a 100644
--- a/tests/tests
+++ b/tests/tests
@@ -152,7 +152,7 @@ a\\$		&	a$
 a\\$		&	a\$
 a\\$		&	a\	a\
 
-# back references, ugh
+# back-references, ugh
 ##a\(b\)\2c	bC	ESUBREG
 ##a\(b\1\)c	bC	ESUBREG
 a\(b*\)c\1d	b	abbcbbd	abbcbbd	bb
@@ -166,7 +166,7 @@ a\(\([bc]\)\2\)*d	b	abbcbd
 a\(\(b\)*\2\)*d		b	abbbd	abbbd
 # here is a case that no NFA implementation does right
 \(ab*\)[ab]*\1	b	ababaaa	ababaaa	a
-# check out normal matching in the presence of back refs
+# check out normal matching in the presence of back-references
 \(a\)\1bcd	b	aabcd	aabcd
 \(a\)\1bc*d	b	aabcd	aabcd
 \(a\)\1bc*d	b	aabd	aabd
-- 
2.17.1

>From 71635837d14c842ceb8a0c096b52656936ac4965 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Mon, 30 Dec 2019 00:58:03 -0800
Subject: [PATCH 3/3] doc: fix bug# typo

---
 doc/grep.texi | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/doc/grep.texi b/doc/grep.texi
index 8866ec4..13b8df0 100644
--- a/doc/grep.texi
+++ b/doc/grep.texi
@@ -1989,7 +1989,7 @@ expression implementations have back-reference bugs that can cause
 programs to return incorrect answers or even crash, and fixing these
 bugs has often been low-priority---for example, as of 2019 the GNU C
 library bug database contained back-reference bugs 52, 10844, 11053,
-and 23522, with little sign of forthcoming fixes.  Luckily,
+and 25322, with little sign of forthcoming fixes.  Luckily,
 back-references are rarely useful and it should be little trouble to
 avoid them in practical applications.
 
-- 
2.17.1