dfa: avoid re-building a state built previously

* src/dfa.c (dfaexec): Avoid to re-build a state built previously.
grep: simplify dfa.c by having it not include mbsupport.h directly

* src/mbsupport.h: Remove.
* src/Makefile.am (noinst_HEADERS): Remove mbsupport.h.
* src/dfa.c, src/grep.c, src/search.h: Don't include mbsupport.h.
* src/dfa.c: Include wchar.h and wctype.h unconditionally, as
this simplifies the use of dfa.c in grep, and it does no harm
in gawk.
(setlocale, static_assert): Remove gawk-specific hacks, as
gawk now does these itself.
(struct dfa, dfambcache, mbs_to_wchar)
(is_valid_unibyte_character, setbit_wc, using_utf8, FETCH_WC)
(addtok_wc, add_utf8_anychar, atom, state_index, epsclosure)
(dfaanalyze, dfastate, prepare_wc_buf, dfaoptimize, dfafree, dfamust):
* src/dfasearch.c (EGexecute):
* src/grep.c (main):
* src/searchutils.c (mbtoupper):
Assume MBS_SUPPORT.
grep: reuse multibyte DFA buffers in non-UTF8 locales

* src/dfa.c (struct dfa): New members 'mblen_buf', 'nmblen_buf',
'inputwcs', 'ninputwcs', 'mb_follows' and 'mb_match_lens'.
(mblen_buf, inputwcs): Remove static vars.
(SKIP_REMAINS_MB_IF_INITIAL_STATE, match_anychar, match_mb_charset)
(transit_state_consume_1char, transit_state, prepare_wc_buf):
Use new members instead of global variables.
(check_matching_with_multibyte_ops): Use new members
instead of new allocation.
(dfaexec): Initialize new members.
(free_mbdata): Free new members.
grep: minor improvements to previous patch

* src/dfa.c (MAX): New macro.
(match_anychar, match_mb_charset, transit_state_consume_1char):
Use it to simplify assignments.
(SKIP_REMAINS_MB_IF_INITIAL_STATE): Prefer != 0 for unsigned.
(free_mbdata): Omit an unnecessary 'free'.
grep: fix performance bug with regex in line-by-line mode

* src/dfasearch.c (EGexecute): Match line-by-line with regex.
build: avoid OS X 10.8.5 build failure due to lack of static_assert

* bootstrap.conf (gnulib_modules): Add assert-h, to accommodate the
new use of static_assert on systems lacking support for that construct.
Without this change, compilation of dfa.c failed on OS X 10.8.5 with
gcc-4.9.0 20140324.  We should be using gnulib's assert-h module,
regardless, for its nominal improved portability, since grep includes
assert.h and uses assert.
grep: optimization with the superset of DFA

The superset of a DFA is like the DFA, except that for speed
ANYCHAR, MBCSET and BACKREF are replaced by (CSET full bits) STAR,
and mb_cur_max is 1.  For example, for 'a\(b\)c\1':
  original: a b CAT c CAT BACKREF CAT
  superset: a b CAT c CAT CSET STAR CAT  (The CSET has all bits set.)
If a string matches a DFA, it matches the DFA's superset.
Using the superset to filter can dramatically improve performance,
over 200x in some cases.  See <http://bugs.gnu.org/16966>.
* src/dfa.c (struct dfa): New member 'superset'.
(dfahint, dfasuperset): New functions.
(dfacomp): Create and analyze the superset.
(dfafree): Free only non-NULL items.
(dfaalloc): Initialize superset member.
(dfaoptimize): If succeed in optimization for UTF-8 locale, don't use
the superset.
* src/dfa.h (dfahint): New decl.
* src/dfasearch.c (EGexecute): Use dfahint.
grep: cleanup DFA superset optimization

* src/dfa.c (dfa_charclass_index): New function, with body of
old dfa_charclass but with an extra parameter D.
(charclass_index): Reimplement in terms of dfa_charclass_index.
(dfahint): Clarify.
(dfasuperset): Do not assign to 'dfa' static variable.  Instead,
use a local, and use the new dfa_charclass_index function.  This
doesn't fix any bugs, but it's clearer.  Initialize a few more
members, to simplify dfafree.  Copy the charclasses with
just one memcpy call.  Don't assign nonnull to D->superset until
it's known to be valid; that's simpler.
(dfafree, dfaalloc): Simplify based on dfasuperset initializations.
* src/dfa.h (dfahint): Add comment.
* src/dfasearch.c (EGexecute): Simplify use of memchr.
Simplify by using memrchr.  Fix typo that could cause a buffer
read overrun.
grep: use the Galil rule for Boyer-Moore algorithm in KWSet

The Boyer-Moore algorithm is O(m*n), which means it may be much
slower than the DFA.  Its Galil rule variant is O(n) and increases
efficiency in the typical case; it skips sections that are known
to match and does not compare more than once for a position in the text.
To use the Galil rule, look for the delta2 shift at each position
from the trie instead of the 'mind2' value.
* src/kwset.c (struct kwset): Replace member 'mind2' with 'shift'.
(kwsprep): Look for the delta2 shift.
(bmexec): Use it.
grep: minor cleanups for Galil speedups

* src/kwset.c: Update citations.
Include stdbool.h.
(kwsincr, kwsprep): Clarify by using C99 decls after statements.
(kwsprep): Clarify by using MIN.  Avoid a couple of buffer copies
when !TRANS.
(bmexec): Use bool for boolean.  Prefer "continue;" to ";".
grep: simplify memory allocation in kwset

* src/kwset.c: Include kwset.h first, to check its prereqs.
Include xalloc.h, for xmalloc.
(kwsalloc): Use xmalloc, not malloc, so that the caller need not
worry about memory allocation failure.
(kwsalloc, kwsincr, kwsprep): Do not worry about obstack_alloc
returning NULL, as that's not possible.
(kwsalloc, kwsincr, kwsprep, bmexec, cwexec, kwsexec, kwsfree):
Omit unnecessary conversion between struct kwset * and kwset_t.
(kwsincr, kwsprep): Return void since memory-allocation failure is
not possible now.  All uses changed.
* src/kwset.h: Include <stddef.h>, for size_t, so that this
include file doesn't require other files to be included first.
grep: remove trival_case_ignore

This optimization is no longer needed, given the other
optimizations recently installed.  Derived from a patch by
Norihiro Tanaka; see <http://bugs.gnu.org/17019>.
* bootstrap.conf (gnulib_modules): Remove assert-h.
* src/dfa.c (CASE_FOLDED_BUFSIZE): Move here from dfa.h.
Remove now-unnecessary static assert.
(case_folded_counterparts): Now static.
* src/dfa.h (CASE_FOLDED_BUFSIZE, case_folded_counterparts):
Remove decls; no longer public.
* src/dfasearch.c (kwsmusts): Use kwset even if fill MB_CUR_MAX > 1
and case-insensitive.
* src/grep.c (MBRTOWC, WCRTOMB): Remove.
(fgrep_to_grep_pattern): Use mbrtowc, not MBRTOWC.
(trivial_case_ignore): Remove; this optimization is no longer needed.
All uses removed.
grep: prefer regex to DFA for ANYCHAR in multibyte locales

* src/dfa.c (dfa_state): New member has_mbcset.
Rename backref to has_backref, and make it of type bool too.
All uses changed.
(state_index, dfastate): Initialize new member.
(dfaexec): Prefer regex to DFA for ANYCHAR in multibyte locales.
grep: prefer bool in DFA internals

* src/dfa.c (bool_bf): New type.
(dfa_state): Use it, as this seems to generate slightly better
code with GCC.
(struct mb_char_classes, struct dfa, equal, case_fold, dfasyntax)
(laststart, parse_bracket_exp, lex, dfaparse, dfaanalyze, dfastate)
(match_mb_charset, dfamust):
Use bool for boolean.
(using_utf8) [!HAVE_LANGINFO_CODESET]: Tune.
(dfaanalyze): Prefer & to && and | to || on booleans; it's simpler here.
(dfastate): Simplify charclass nonzero testing.  Redo has_mbcset
test so that the compiler's more likely to optimize it.
grep: port better to hosts with nonstandard nl_langinfo

On some hosts, nl_langinfo returns strings other than "UTF-8" when
UTF-8 is used, and (worse) return "UTF-8" even if the encoding is
single-byte.  Work around these problems by trying a sample
character instead.
* src/dfa.c, src/pcresearch.c, src/searchutils.c:
Don't include <langinfo.h>.
* src/dfa.c (using_utf8): Test for UTF-8 by trying a character
rather than by invoking nl_langinfo (CODESET); this is more
portable in practice, and removes a dependency on
HAVE_LANGINFO_CODESET.
* src/pcresearch.c: Include dfa.h, for using_utf8.
(Pcompile): Use using_utf8 rather than nl_langinfo.
maint: avoid sc_po_check syntax-check failure (kwset.c)

* po/POTFILES.in: Remove kwset.c from this list, since it
no longer contains a translatable diagnostic.
grep: remove bool_bf

The extra complexity of this microoptimization wasn't ever much help,
and currently it generated bigger code with gcc -O2 (x86-64).
* src/dfa.c (bool_bf): Remove.  All uses replaced by plain 'bool',
without a bitfield.
grep: no match for the empty string included in multiple patterns

* src/dfasearch.c (EGAcompile): Fix it.
* src/kwsearch.c (Fcompile): Fix it.
grep: cleanup for empty-string fix

* NEWS: Document it.
* src/dfasearch.c (GEAcompile):
* src/kwsearch.c (Fcompile):
Use C99-style decls to simplify.  Avoid duplicate code.
* tests/empty-line: Add some more tests like this.
grep: cleanup for HAS_DOS_FILE_CONTENTS issue

While cleaning up the empty-string fix, I noticed that one part of
the code worried about CRLF in pattern files whereas another part
did not.  Fix this by using the same approach in both places,
and make the CRLF code more modular in the process.
* src/dosbuf.c (dos_binary, dos_unix_byte_offsets): New functions.
(undossify_input, dossified_pos): Do nothing if ! O_BINARY.
* src/grep.c: Always include dosbuf.c so that the code is
checked statically even on non-DOS hosts.
(dos_binary, dos_unix_byte_offsets): New decls.
(undossify_input): Declare unconditionally.
* src/grep.c (fillbuf, print_line_head, main):
* src/kwsearch.c (Fcompile):
Simplify by not worrying about HAVE_DOS_FILE_CONTENTS.
* src/grep.c (main): fopen with "rt" if O_TEXT; this is simpler
than worrying about HAVE_DOS_FILE_CONTENTS elsewhere.
* src/system.h (HAVE_DOS_FILE_CONTENTS): Remove.