GNU bug report logs - #16966
[PATCH] grep: optimization with the superset of DFA

Previous Next

Package: grep;

Reported by: Norihiro Tanaka <noritnk <at> kcn.ne.jp>

Date: Sat, 8 Mar 2014 05:43:01 UTC

Severity: normal

Tags: patch

Done: Paul Eggert <eggert <at> cs.ucla.edu>

Bug is archived. No further changes may be made.

Full log

View this message in rfc822 format

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Paolo Bonzini <bonzini <at> gnu.org>
Cc: 16966 <at> debbugs.gnu.org
Subject: bug#16966: [PATCH] grep: optimization with the superset of DFA
Date: Wed, 02 Apr 2014 22:52:43 +0900

Norihiro Tanaka wrote:
> s0: The position set is none. 
> s1: The position set is 1:a 
> s2: The position set is 1:a 2:CSET
> s3: The position set is 1:a 2:CSET 3:b (accepted)

Sorry, it was wrong.  It should be as follows.

s0: The position set is none.
s1: The position set is 1:a
s2: The position set is 1:a 2:CSET
s3: The position set is 2:CSET 3:b (accepted)
s4: The position set is 2:CSET

        1  accccccccccccccccccccccccccccccccccccccc
           ^ s1

        1  accccccccccccccccccccccccccccccccccccccc
            ^ s4

        1  accccccccccccccccccccccccccccccccccccccc
             ^ s4

              ......

1,000,000  cccccccccccccccccccccccccccccccccccccccb
                                                 ^ s4

1,000,000  cccccccccccccccccccccccccccccccccccccccb
                                                  ^ s3 accepted

Then re-searched with the superset because matched on multi-lines.

1,000,000  cccccccccccccccccccccacccccccccccccccccb
           ^ s0


1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                ^ s1

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                 ^ s4

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                                 ^ s4

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                                  ^ s3 accepted


s0: The position set is none. 
s1: The position set is 1:a 
s2: The position set is 1:a 2:ANYCHAR
s3: The position set is 2:ANYCHAR 3:b (accepted)
s4: The position set is 2:ANYCHAR

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                ^ s1

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                 ^ s4

1,000,000  cccccccccccccccccccccacccccccccccccccccb
                                  ^ s0 rejected
This bug report was last modified 11 years and 107 days ago.

Previous Next

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