sed: use grep's DFA matcher to speed up regular expression matching
authorNorihiro Tanaka <noritnk@kcn.ne.jp>
Sun, 7 Aug 2016 01:32:43 +0000 (18:32 -0700)
committerJim Meyering <meyering@fb.com>
Tue, 9 Aug 2016 00:50:49 +0000 (17:50 -0700)
commitcbd13f729dd196bd3058930206a1d4575e733871
treeb06e2cd0ee8f6c6b22211f75148f7e57a40622f8
parentab0cfea35c07faa80740e8ca9369ac76855833ac
sed: use grep's DFA matcher to speed up regular expression matching

When possible, sed now uses grep's DFA matcher to match regular
expression, often resulting in a 10x speed-up.
* NEWS (Improvements): Mention it.  Move this section to the top.
* sed/local.mk (sed_sed_SOURCES): Add dfa.c, and sort file names.
(noinst_HEADERS): Add dfa.h, and sort file names.
* sed/regexp.c (dfaerror, dfawarn): New functions.
(compile_regex_1): Compile pattern with dfa.
(match_regex): Use dfa.
* sed/sed.h: Include dfa.h.
(struct regex): New member dfa.
* sed/dfa.c: New file, copied from grep.
* sed/dfa.h: New file, copied from grep.
* po/POTFILES.in: Add sed/dfa.c.
NEWS
po/POTFILES.in
sed/dfa.c [new file with mode: 0644]
sed/dfa.h [new file with mode: 0644]
sed/local.mk
sed/regexp.c
sed/sed.h