GNU bug report logs - #19306
[PATCH 1/2] dfa: avoid execution for a pattern including an unsupported expression

Previous Next

Full log

View this message in rfc822 format

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Jim Meyering <jim <at> meyering.net>
Cc: 19306 <at> debbugs.gnu.org
Subject: bug#19306: [PATCH 1/2] dfa: avoid execution for a pattern including an unsupported expression
Date: Sun, 19 Jul 2015 16:42:46 +0900

[Message part 1 (text/plain, inline)]

On Sat, 18 Jul 2015 22:15:33 -0700
Jim Meyering <jim <at> meyering.net> wrote:

> Hello,
> Thank you for the patches in this report:
> 
>   http://bugs.gnu.org/19306
> 
> Please excuse my delay in getting back to you on this.
> Would you revise each of those to include a test case
> that demonstrates the problem/fix?

Thanks for your reviewing of this report.

This is not bug fix.  It avoids that BACKREF is found in the process of
DFAEXEC and passed to regex in multibyte locale.  In other words, if a
pattern includes BACKREF, grep does not try to use DFA from the
beginning.

I confirmed about 10% speed-up for a test case in attachment.

  Before patching: real 7.29  user 7.26  sys 0.02
  After patching : real 6.57  user 6.55  sys 0.01

KWset and DFA superset succeeds for all rows in the test case, and DFA
for multibyte succeeds, too.  However, all rows are rejected in regex.

After patching, grep does not try DFA for multibyte, as pattern includes
BACKREF.

In addtion, I believe that DFA is simplified by removal of handling for
BACKREF from dfaanalyze(), dfassbuild() and dfaexec().

[testcase.sh (text/plain, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.