grep: grouping of a pattern with multiple lines

When grep uses regex, it splits a pattern with multiple lines by
newline character into fragments.  Compilation and execution run for
each fragment.  That causes slowdown.  By this change, each fragment is
divided into groups by whether the fragment includes back references.
A fragment with back references constitutes group, and all fragments
that lack back references also constitute a group.

This change extremely speeds-up following case.

  $ seq -f '%040g' 0 9999 | sed '1s/$/\\(0\\)\\1/' >pat
  $ yes 00000000000000000000000000000000000000000x | head -10000 >in
  $ time -p env LC_ALL=C src/grep -f pat in

* src/dfasearch.c (find_backref_in_pattern, regex_compile):
New functions.
(GEAcompile): Use the new functions to group fragments
as mentioned above.

0 files changed, 0 insertions, 0 deletions