/* dfasearch.c - searching subroutines using dfa and regex for grep.

   Copyright 1992, 1998, 2000, 2007, 2009-2017 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; either version 3, or (at your option)

   any later version.

   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License

   along with this program; if not, write to the Free Software

   Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA

   02110-1301, USA.  */

/* Written August 1992 by Mike Haertel. */

#include <config.h>

#include "intprops.h"

#include "search.h"

#include "die.h"

#include <error.h>

struct dfa_comp

{

  /* KWset compiled pattern.  For Ecompile and Gcompile, we compile

     a list of strings, at least one of which is known to occur in

     any string matching the regexp. */

  kwset_t kwset;

  /* DFA compiled regexp. */

  struct dfa *dfa;

  /* Regex compiled regexps. */

  struct re_pattern_buffer* patterns;

  size_t pcount;

  struct re_registers regs;

  /* Number of compiled fixed strings known to exactly match the regexp.

     If kwsexec returns < kwset_exact_matches, then we don't need to

     call the regexp matcher at all. */

  ptrdiff_t kwset_exact_matches;

  bool begline;

};

void

dfaerror (char const *mesg)

{

  die (EXIT_TROUBLE, 0, "%s", mesg);

}

/* For now, the sole dfawarn-eliciting condition (use of a regexp

   like '[:lower:]') is unequivocally an error, so treat it as such,

   when possible.  */

void

dfawarn (char const *mesg)

{

  if (!getenv ("POSIXLY_CORRECT"))

    dfaerror (mesg);

}

/* If the DFA turns out to have some set of fixed strings one of

   which must occur in the match, then we build a kwset matcher

   to find those strings, and thus quickly filter out impossible

   matches. */

static void

kwsmusts (struct dfa_comp *dc)

{

  struct dfamust *dm = dfamust (dc->dfa);

  if (!dm)

    return;

  dc->kwset = kwsinit (false);

  if (dm->exact)

    {

      /* Prepare a substring whose presence implies a match.

         The kwset matcher will return the index of the matching

         string that it chooses. */

      ++dc->kwset_exact_matches;

      ptrdiff_t old_len = strlen (dm->must);

      ptrdiff_t new_len = old_len + dm->begline + dm->endline;

      char *must = xmalloc (new_len);

      char *mp = must;

      *mp = eolbyte;

      mp += dm->begline;

      dc->begline |= dm->begline;

      memcpy (mp, dm->must, old_len);

      if (dm->endline)

        mp[old_len] = eolbyte;

      kwsincr (dc->kwset, must, new_len);

      free (must);

    }

  else

    {

      /* Otherwise, filtering with this substring should help reduce the

         search space, but we'll still have to use the regexp matcher.  */

      kwsincr (dc->kwset, dm->must, strlen (dm->must));

    }

  kwsprep (dc->kwset);

  dfamustfree (dm);

}

void *

GEAcompile (char *pattern, size_t size, reg_syntax_t syntax_bits)

{

  char *motif;

  struct dfa_comp *dc = xcalloc (1, sizeof (*dc));

  dc->dfa = dfaalloc ();

  if (match_icase)

    syntax_bits |= RE_ICASE;

  re_set_syntax (syntax_bits);

  int dfaopts = eolbyte ? 0 : DFA_EOL_NUL;

  dfasyntax (dc->dfa, &localeinfo, syntax_bits, dfaopts);

  /* For GNU regex, pass the patterns separately to detect errors like

     "[\nallo\n]\n", where the patterns are "[", "allo" and "]", and

     this should be a syntax error.  The same for backref, where the

     backref should be local to each pattern.  */

  char const *p = pattern;

  char const *patlim = pattern + size;

  bool compilation_failed = false;

  size_t palloc = 0;

  do

    {

      size_t len;

      char const *sep = memchr (p, '\n', patlim - p);

      if (sep)

        {

          len = sep - p;

          sep++;

        }

      else

        len = patlim - p;

      if (palloc <= dc->pcount)

        dc->patterns = x2nrealloc (dc->patterns, &palloc, sizeof *dc->patterns);

      struct re_pattern_buffer *pat = &dc->patterns[dc->pcount];

      pat->buffer = NULL;

      pat->allocated = 0;

      /* Do not use a fastmap with -i, to work around glibc Bug#20381.  */

      pat->fastmap = match_icase ? NULL : xmalloc (UCHAR_MAX + 1);

      pat->translate = NULL;

      char const *err = re_compile_pattern (p, len, pat);

      if (err)

        {

          /* With patterns specified only on the command line, emit the bare

             diagnostic.  Otherwise, include a filename:lineno: prefix.  */

          size_t lineno;

          char const *pat_filename = pattern_file_name (dc->pcount + 1,

                                                        &lineno);

          if (*pat_filename == '\0')

            error (0, 0, "%s", err);

          else

            error (0, 0, "%s:%zu: %s", pat_filename, lineno, err);

          compilation_failed = true;

        }

      dc->pcount++;

      p = sep;

    }

  while (p);

  if (compilation_failed)

    exit (EXIT_TROUBLE);

  /* In the match_words and match_lines cases, we use a different pattern

     for the DFA matcher that will quickly throw out cases that won't work.

     Then if DFA succeeds we do some hairy stuff using the regex matcher

     to decide whether the match should really count. */

  if (match_words || match_lines)

    {

      static char const line_beg_no_bk[] = "^(";

      static char const line_end_no_bk[] = ")$";

      static char const word_beg_no_bk[] = "(^|[^[:alnum:]_])(";

      static char const word_end_no_bk[] = ")([^[:alnum:]_]|$)";

      static char const line_beg_bk[] = "^\\(";

      static char const line_end_bk[] = "\\)$";

      static char const word_beg_bk[] = "\\(^\\|[^[:alnum:]_]\\)\\(";

      static char const word_end_bk[] = "\\)\\([^[:alnum:]_]\\|$\\)";

      int bk = !(syntax_bits & RE_NO_BK_PARENS);

      char *n = xmalloc (sizeof word_beg_bk - 1 + size + sizeof word_end_bk);

      strcpy (n, match_lines ? (bk ? line_beg_bk : line_beg_no_bk)

                             : (bk ? word_beg_bk : word_beg_no_bk));

      size_t total = strlen (n);

      memcpy (n + total, pattern, size);

      total += size;

      strcpy (n + total, match_lines ? (bk ? line_end_bk : line_end_no_bk)

                                     : (bk ? word_end_bk : word_end_no_bk));

      total += strlen (n + total);

      pattern = motif = n;

      size = total;

    }

  else

    motif = NULL;

  dfacomp (pattern, size, dc->dfa, 1);

  kwsmusts (dc);

  free (motif);

  return dc;

}

size_t

EGexecute (void *vdc, char const *buf, size_t size, size_t *match_size,

           char const *start_ptr)

{

  char const *buflim, *beg, *end, *ptr, *match, *best_match, *mb_start;

  char eol = eolbyte;

  regoff_t start;

  size_t len, best_len;

  struct kwsmatch kwsm;

  size_t i;

  struct dfa_comp *dc = vdc;

  struct dfa *superset = dfasuperset (dc->dfa);

  bool dfafast = dfaisfast (dc->dfa);

  mb_start = buf;

  buflim = buf + size;

  for (beg = end = buf; end < buflim; beg = end)

    {

      end = buflim;

      if (!start_ptr)

        {

          char const *next_beg, *dfa_beg = beg;

          size_t count = 0;

          bool exact_kwset_match = false;

          bool backref = false;

          /* Try matching with KWset, if it's defined.  */

          if (dc->kwset)

            {

              char const *prev_beg;

              /* Find a possible match using the KWset matcher.  */

              ptrdiff_t offset = kwsexec (dc->kwset, beg - dc->begline,

                                          buflim - beg + dc->begline,

                                          &kwsm, true);

              if (offset < 0)

                goto failure;

              match = beg + offset;

              prev_beg = beg;

              /* Narrow down to the line containing the possible match.  */

              beg = memrchr (buf, eol, match - buf);

              beg = beg ? beg + 1 : buf;

              dfa_beg = beg;

              /* Determine the end pointer to give the DFA next.  Typically

                 this is after the first newline after MATCH; but if the KWset

                 match is not exact, the DFA is fast, and the offset from

                 PREV_BEG is less than 64 or (MATCH - PREV_BEG), this is the

                 greater of the latter two values; this temporarily prefers

                 the DFA to KWset.  */

              exact_kwset_match = kwsm.index < dc->kwset_exact_matches;

              end = ((exact_kwset_match || !dfafast

                      || MAX (16, match - beg) < (match - prev_beg) >> 2)

                     ? match

                     : MAX (16, match - beg) < (buflim - prev_beg) >> 2

                     ? prev_beg + 4 * MAX (16, match - beg)

                     : buflim);

              end = memchr (end, eol, buflim - end);

              end = end ? end + 1 : buflim;

              if (exact_kwset_match)

                {

                  if (!localeinfo.multibyte | localeinfo.using_utf8)

                    goto success;

                  if (mb_start < beg)

                    mb_start = beg;

                  if (mb_goback (&mb_start, match, buflim) == 0)

                    goto success;

                  /* The matched line starts in the middle of a multibyte

                     character.  Perform the DFA search starting from the

                     beginning of the next character.  */

                  dfa_beg = mb_start;

                }

            }

          /* Try matching with the superset of DFA, if it's defined.  */

          if (superset && !exact_kwset_match)

            {

              /* Keep using the superset while it reports multiline

                 potential matches; this is more likely to be fast

                 than falling back to KWset would be.  */

              next_beg = dfaexec (superset, dfa_beg, (char *) end, 0,

                                  &count, NULL);

              if (next_beg == NULL || next_beg == end)

                continue;

              /* Narrow down to the line we've found.  */

              if (count != 0)

                {

                  beg = memrchr (buf, eol, next_beg - buf);

                  beg++;

                  dfa_beg = beg;

                }

              end = memchr (next_beg, eol, buflim - next_beg);

              end = end ? end + 1 : buflim;

              count = 0;

            }

          /* Try matching with DFA.  */

          next_beg = dfaexec (dc->dfa, dfa_beg, (char *) end, 0, &count,

                              &backref);

          /* If there's no match, or if we've matched the sentinel,

             we're done.  */

          if (next_beg == NULL || next_beg == end)

            continue;

          /* Narrow down to the line we've found.  */

          if (count != 0)

            {

              beg = memrchr (buf, eol, next_beg - buf);

              beg++;

            }

          end = memchr (next_beg, eol, buflim - next_beg);

          end = end ? end + 1 : buflim;

          /* Successful, no backreferences encountered! */

          if (!backref)

            goto success;

          ptr = beg;

        }

      else

        {

          /* We are looking for the leftmost (then longest) exact match.

             We will go through the outer loop only once.  */

          ptr = start_ptr;

        }

      /* If the "line" is longer than the maximum regexp offset,

         die as if we've run out of memory.  */

      if (TYPE_MAXIMUM (regoff_t) < end - beg - 1)

        xalloc_die ();

      /* Run the possible match through Regex.  */

      best_match = end;

      best_len = 0;

      for (i = 0; i < dc->pcount; i++)

        {

          dc->patterns[i].not_eol = 0;

          dc->patterns[i].newline_anchor = eolbyte == '\n';

          start = re_search (&dc->patterns[i], beg, end - beg - 1,

                             ptr - beg, end - ptr - 1, &dc->regs);

          if (start < -1)

            xalloc_die ();

          else if (0 <= start)

            {

              len = dc->regs.end[0] - start;

              match = beg + start;

              if (match > best_match)

                continue;

              if (start_ptr && !match_words)

                goto assess_pattern_match;

              if ((!match_lines && !match_words)

                  || (match_lines && len == end - ptr - 1))

                {

                  match = ptr;

                  len = end - ptr;

                  goto assess_pattern_match;

                }

              /* If -w and not -x, check whether the match aligns with

                 word boundaries.  Do this iteratively because:

                 (a) the line may contain more than one occurrence of the

                 pattern, and

                 (b) Several alternatives in the pattern might be valid at a

                 given point, and we may need to consider a shorter one to

                 find a word boundary.  */

              if (!match_lines && match_words)

                while (match <= best_match)

                  {

                    regoff_t shorter_len = 0;

                    if (! wordchar_next (match + len, end - 1)

                        && ! wordchar_prev (beg, match, end - 1))

                      goto assess_pattern_match;

                    if (len > 0)

                      {

                        /* Try a shorter length anchored at the same place. */

                        --len;

                        dc->patterns[i].not_eol = 1;

                        shorter_len = re_match (&dc->patterns[i], beg,

                                                match + len - ptr, match - beg,

                                                &dc->regs);

                        if (shorter_len < -1)

                          xalloc_die ();

                      }

                    if (0 < shorter_len)

                      len = shorter_len;

                    else

                      {

                        /* Try looking further on. */

                        if (match == end - 1)

                          break;

                        match++;

                        dc->patterns[i].not_eol = 0;

                        start = re_search (&dc->patterns[i], beg, end - beg - 1,

                                           match - beg, end - match - 1,

                                           &dc->regs);

                        if (start < 0)

                          {

                            if (start < -1)

                              xalloc_die ();

                            break;

                          }

                        len = dc->regs.end[0] - start;

                        match = beg + start;

                      }

                  } /* while (match <= best_match) */

              continue;

            assess_pattern_match:

              if (!start_ptr)

                {

                  /* Good enough for a non-exact match.

                     No need to look at further patterns, if any.  */

                  goto success;

                }

              if (match < best_match || (match == best_match && len > best_len))

                {

                  /* Best exact match:  leftmost, then longest.  */

                  best_match = match;

                  best_len = len;

                }

            } /* if re_search >= 0 */

        } /* for Regex patterns.  */

        if (best_match < end)

          {

            /* We have found an exact match.  We were just

               waiting for the best one (leftmost then longest).  */

            beg = best_match;

            len = best_len;

            goto success_in_len;

          }

    } /* for (beg = end ..) */

 failure:

  return -1;

 success:

  len = end - beg;

 success_in_len:;

  size_t off = beg - buf;

  *match_size = len;

  return off;

}