contrib/grep/src/dfasearch.c

   1 /* dfasearch.c - searching subroutines using dfa and regex for grep.
   2    Copyright 1992, 1998, 2000, 2007, 2009-2010 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 3, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA
  17    02110-1301, USA.  */
  18
  19 /* Written August 1992 by Mike Haertel. */
  20
  21 #include <config.h>
  22 #include "search.h"
  23 #include "dfa.h"
  24
  25 /* For -w, we also consider _ to be word constituent.  */
  26 #define WCHAR(C) (isalnum (C) || (C) == '_')
  27
  28 /* KWset compiled pattern.  For Ecompile and Gcompile, we compile
  29    a list of strings, at least one of which is known to occur in
  30    any string matching the regexp. */
  31 static kwset_t kwset;
  32
  33 /* DFA compiled regexp. */
  34 static struct dfa *dfa;
  35
  36 /* The Regex compiled patterns.  */
  37 static struct patterns
  38 {
  39   /* Regex compiled regexp. */
  40   struct re_pattern_buffer regexbuf;
  41   struct re_registers regs; /* This is here on account of a BRAIN-DEAD
  42                                Q@#%!# library interface in regex.c.  */
  43 } patterns0;
  44
  45 static struct patterns *patterns;
  46 static size_t pcount;
  47
  48 void
  49 dfaerror (char const *mesg)
  50 {
  51   error (EXIT_TROUBLE, 0, "%s", mesg);
  52
  53   /* notreached */
  54   /* Tell static analyzers that this function does not return.  */
  55   abort ();
  56 }
  57
  58 /* For now, the sole dfawarn-eliciting condition (use of a regexp
  59    like '[:lower:]') is unequivocally an error, so treat it as such,
  60    when possible.  */
  61 void
  62 dfawarn (char const *mesg)
  63 {
  64   static enum { NONE = 0, POSIX, GNU } mode;
  65   if (mode == NONE)
  66     mode = (getenv ("POSIXLY_CORRECT") ? POSIX : GNU);
  67   if (mode == GNU)
  68     dfaerror (mesg);
  69 }
  70
  71 /* Number of compiled fixed strings known to exactly match the regexp.
  72    If kwsexec returns < kwset_exact_matches, then we don't need to
  73    call the regexp matcher at all. */
  74 static int kwset_exact_matches;
  75
  76 static char const *
  77 kwsincr_case (const char *must)
  78 {
  79   const char *buf;
  80   size_t n;
  81
  82   n = strlen (must);
  83 #if MBS_SUPPORT
  84   if (match_icase && MB_CUR_MAX > 1)
  85     buf = mbtolower (must, &n);
  86   else
  87 #endif
  88     buf = must;
  89   return kwsincr (kwset, buf, n);
  90 }
  91
  92 /* If the DFA turns out to have some set of fixed strings one of
  93    which must occur in the match, then we build a kwset matcher
  94    to find those strings, and thus quickly filter out impossible
  95    matches. */
  96 static void
  97 kwsmusts (void)
  98 {
  99   struct dfamust const *dm;
 100   char const *err;
 101
 102   dm = dfamusts (dfa);
 103   if (dm)
 104     {
 105       kwsinit (&kwset);
 106       /* First, we compile in the substrings known to be exact
 107          matches.  The kwset matcher will return the index
 108          of the matching string that it chooses. */
 109       for (; dm; dm = dm->next)
 110         {
 111           if (!dm->exact)
 112             continue;
 113           ++kwset_exact_matches;
 114           if ((err = kwsincr_case (dm->must)) != NULL)
 115             error (EXIT_TROUBLE, 0, "%s", err);
 116         }
 117       /* Now, we compile the substrings that will require
 118          the use of the regexp matcher.  */
 119       for (dm = dfamusts (dfa); dm; dm = dm->next)
 120         {
 121           if (dm->exact)
 122             continue;
 123           if ((err = kwsincr_case (dm->must)) != NULL)
 124             error (EXIT_TROUBLE, 0, "%s", err);
 125         }
 126       if ((err = kwsprep (kwset)) != NULL)
 127         error (EXIT_TROUBLE, 0, "%s", err);
 128     }
 129 }
 130
 131 void
 132 GEAcompile (char const *pattern, size_t size, reg_syntax_t syntax_bits)
 133 {
 134   const char *err;
 135   const char *p, *sep;
 136   size_t total = size;
 137   char *motif;
 138
 139   if (match_icase)
 140     syntax_bits |= RE_ICASE;
 141   re_set_syntax (syntax_bits);
 142   dfasyntax (syntax_bits, match_icase, eolbyte);
 143
 144   /* For GNU regex compiler we have to pass the patterns separately to detect
 145      errors like "[\nallo\n]\n".  The patterns here are "[", "allo" and "]"
 146      GNU regex should have raise a syntax error.  The same for backref, where
 147      the backref should have been local to each pattern.  */
 148   p = pattern;
 149   do
 150     {
 151       size_t len;
 152       sep = memchr (p, '\n', total);
 153       if (sep)
 154         {
 155           len = sep - p;
 156           sep++;
 157           total -= (len + 1);
 158         }
 159       else
 160         {
 161           len = total;
 162           total = 0;
 163         }
 164
 165       patterns = realloc (patterns, (pcount + 1) * sizeof (*patterns));
 166       if (patterns == NULL)
 167         error (EXIT_TROUBLE, errno, _("memory exhausted"));
 168       patterns[pcount] = patterns0;
 169
 170       if ((err = re_compile_pattern (p, len,
 171                                     &(patterns[pcount].regexbuf))) != NULL)
 172         error (EXIT_TROUBLE, 0, "%s", err);
 173       pcount++;
 174
 175       p = sep;
 176     } while (sep && total != 0);
 177
 178   /* In the match_words and match_lines cases, we use a different pattern
 179      for the DFA matcher that will quickly throw out cases that won't work.
 180      Then if DFA succeeds we do some hairy stuff using the regex matcher
 181      to decide whether the match should really count. */
 182   if (match_words || match_lines)
 183     {
 184       static char const line_beg_no_bk[] = "^(";
 185       static char const line_end_no_bk[] = ")$";
 186       static char const word_beg_no_bk[] = "(^|[^[:alnum:]_])(";
 187       static char const word_end_no_bk[] = ")([^[:alnum:]_]|$)";
 188       static char const line_beg_bk[] = "^\\(";
 189       static char const line_end_bk[] = "\\)$";
 190       static char const word_beg_bk[] = "\\(^\\|[^[:alnum:]_]\\)\\(";
 191       static char const word_end_bk[] = "\\)\\([^[:alnum:]_]\\|$\\)";
 192       int bk = !(syntax_bits & RE_NO_BK_PARENS);
 193       char *n = xmalloc (sizeof word_beg_bk - 1 + size + sizeof word_end_bk);
 194
 195       strcpy (n, match_lines ? (bk ? line_beg_bk : line_beg_no_bk)
 196                              : (bk ? word_beg_bk : word_beg_no_bk));
 197       total = strlen(n);
 198       memcpy (n + total, pattern, size);
 199       total += size;
 200       strcpy (n + total, match_lines ? (bk ? line_end_bk : line_end_no_bk)
 201                                      : (bk ? word_end_bk : word_end_no_bk));
 202       total += strlen (n + total);
 203       pattern = motif = n;
 204       size = total;
 205     }
 206   else
 207     motif = NULL;
 208
 209   dfa = dfaalloc ();
 210   dfacomp (pattern, size, dfa, 1);
 211   kwsmusts ();
 212
 213   free(motif);
 214 }
 215
 216 size_t
 217 EGexecute (char const *buf, size_t size, size_t *match_size,
 218            char const *start_ptr)
 219 {
 220   char const *buflim, *beg, *end, *match, *best_match, *mb_start;
 221   char eol = eolbyte;
 222   int backref, start, len, best_len;
 223   struct kwsmatch kwsm;
 224   size_t i, ret_val;
 225 #if MBS_SUPPORT
 226   if (MB_CUR_MAX > 1)
 227     {
 228       if (match_icase)
 229         {
 230           /* mbtolower adds a NUL byte at the end.  That will provide
 231              space for the sentinel byte dfaexec may add.  */
 232           char *case_buf = mbtolower (buf, &size);
 233           if (start_ptr)
 234             start_ptr = case_buf + (start_ptr - buf);
 235           buf = case_buf;
 236         }
 237     }
 238 #endif /* MBS_SUPPORT */
 239
 240   mb_start = buf;
 241   buflim = buf + size;
 242
 243   for (beg = end = buf; end < buflim; beg = end)
 244     {
 245       if (!start_ptr)
 246         {
 247           /* We don't care about an exact match.  */
 248           if (kwset)
 249             {
 250               /* Find a possible match using the KWset matcher. */
 251               size_t offset = kwsexec (kwset, beg, buflim - beg, &kwsm);
 252               if (offset == (size_t) -1)
 253                 goto failure;
 254               beg += offset;
 255               /* Narrow down to the line containing the candidate, and
 256                  run it through DFA. */
 257               if ((end = memchr(beg, eol, buflim - beg)) != NULL)
 258                 end++;
 259               else
 260                 end = buflim;
 261               match = beg;
 262               while (beg > buf && beg[-1] != eol)
 263                 --beg;
 264               if (kwsm.index < kwset_exact_matches)
 265                 {
 266 #if MBS_SUPPORT
 267                   if (mb_start < beg)
 268                     mb_start = beg;
 269                   if (MB_CUR_MAX == 1
 270                       || !is_mb_middle (&mb_start, match, buflim,
 271                                         kwsm.size[0]))
 272 #endif
 273                     goto success;
 274                 }
 275               if (dfaexec (dfa, beg, (char *) end, 0, NULL, &backref) == NULL)
 276                 continue;
 277             }
 278           else
 279             {
 280               /* No good fixed strings; start with DFA. */
 281               char const *next_beg = dfaexec (dfa, beg, (char *) buflim,
 282                                               0, NULL, &backref);
 283               if (next_beg == NULL)
 284                 break;
 285               /* Narrow down to the line we've found. */
 286               beg = next_beg;
 287               if ((end = memchr(beg, eol, buflim - beg)) != NULL)
 288                 end++;
 289               else
 290                 end = buflim;
 291               while (beg > buf && beg[-1] != eol)
 292                 --beg;
 293             }
 294           /* Successful, no backreferences encountered! */
 295           if (!backref)
 296             goto success;
 297         }
 298       else
 299         {
 300           /* We are looking for the leftmost (then longest) exact match.
 301              We will go through the outer loop only once.  */
 302           beg = start_ptr;
 303           end = buflim;
 304         }
 305
 306       /* If we've made it to this point, this means DFA has seen
 307          a probable match, and we need to run it through Regex. */
 308       best_match = end;
 309       best_len = 0;
 310       for (i = 0; i < pcount; i++)
 311         {
 312           patterns[i].regexbuf.not_eol = 0;
 313           if (0 <= (start = re_search (&(patterns[i].regexbuf),
 314                                        buf, end - buf - 1,
 315                                        beg - buf, end - beg - 1,
 316                                        &(patterns[i].regs))))
 317             {
 318               len = patterns[i].regs.end[0] - start;
 319               match = buf + start;
 320               if (match > best_match)
 321                 continue;
 322               if (start_ptr && !match_words)
 323                 goto assess_pattern_match;
 324               if ((!match_lines && !match_words)
 325                   || (match_lines && len == end - beg - 1))
 326                 {
 327                   match = beg;
 328                   len = end - beg;
 329                   goto assess_pattern_match;
 330                 }
 331               /* If -w, check if the match aligns with word boundaries.
 332                  We do this iteratively because:
 333                  (a) the line may contain more than one occurence of the
 334                  pattern, and
 335                  (b) Several alternatives in the pattern might be valid at a
 336                  given point, and we may need to consider a shorter one to
 337                  find a word boundary.  */
 338               if (match_words)
 339                 while (match <= best_match)
 340                   {
 341                     if ((match == buf || !WCHAR ((unsigned char) match[-1]))
 342                         && (start + len == end - buf - 1
 343                             || !WCHAR ((unsigned char) match[len])))
 344                       goto assess_pattern_match;
 345                     if (len > 0)
 346                       {
 347                         /* Try a shorter length anchored at the same place. */
 348                         --len;
 349                         patterns[i].regexbuf.not_eol = 1;
 350                         len = re_match (&(patterns[i].regexbuf),
 351                                         buf, match + len - beg, match - buf,
 352                                         &(patterns[i].regs));
 353                       }
 354                     if (len <= 0)
 355                       {
 356                         /* Try looking further on. */
 357                         if (match == end - 1)
 358                           break;
 359                         match++;
 360                         patterns[i].regexbuf.not_eol = 0;
 361                         start = re_search (&(patterns[i].regexbuf),
 362                                            buf, end - buf - 1,
 363                                            match - buf, end - match - 1,
 364                                            &(patterns[i].regs));
 365                         if (start < 0)
 366                           break;
 367                         len = patterns[i].regs.end[0] - start;
 368                         match = buf + start;
 369                       }
 370                   } /* while (match <= best_match) */
 371               continue;
 372             assess_pattern_match:
 373               if (!start_ptr)
 374                 {
 375                   /* Good enough for a non-exact match.
 376                      No need to look at further patterns, if any.  */
 377                   goto success;
 378                 }
 379               if (match < best_match || (match == best_match && len > best_len))
 380                 {
 381                   /* Best exact match:  leftmost, then longest.  */
 382                   best_match = match;
 383                   best_len = len;
 384                 }
 385             } /* if re_search >= 0 */
 386         } /* for Regex patterns.  */
 387         if (best_match < end)
 388           {
 389             /* We have found an exact match.  We were just
 390                waiting for the best one (leftmost then longest).  */
 391             beg = best_match;
 392             len = best_len;
 393             goto success_in_len;
 394           }
 395     } /* for (beg = end ..) */
 396
 397  failure:
 398   ret_val = -1;
 399   goto out;
 400
 401  success:
 402   len = end - beg;
 403  success_in_len:
 404   *match_size = len;
 405   ret_val = beg - buf;
 406  out:
 407   return ret_val;
 408 }