gnu/usr.bin/grep/search.c

   1 /* search.c - searching subroutines using dfa, kwset and regex for grep.
   2    Copyright (C) 1992, 1998 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 2, 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., 59 Temple Place - Suite 330, Boston, MA
  17    02111-1307, USA.  */
  18
  19 /* Written August 1992 by Mike Haertel. */
  20
  21 /* $FreeBSD: src/gnu/usr.bin/grep/search.c,v 1.10 2000/01/31 13:28:57 ru Exp $ */
  22
  23 #ifdef HAVE_CONFIG_H
  24 # include <config.h>
  25 #endif
  26 #include <sys/types.h>
  27 #include "system.h"
  28 #include "grep.h"
  29 #ifdef __FreeBSD__
  30 #include <gnuregex.h>
  31 #else
  32 #include "regex.h"
  33 #endif
  34 #include "dfa.h"
  35 #include "kwset.h"
  36
  37 #define NCHAR (UCHAR_MAX + 1)
  38
  39 static void Gcompile PARAMS((char *, size_t));
  40 static void Ecompile PARAMS((char *, size_t));
  41 static char *EGexecute PARAMS((char *, size_t, char **));
  42 static void Fcompile PARAMS((char *, size_t));
  43 static char *Fexecute PARAMS((char *, size_t, char **));
  44 static void kwsinit PARAMS((void));
  45
  46 /* Here is the matchers vector for the main program. */
  47 struct matcher matchers[] = {
  48   { "default", Gcompile, EGexecute },
  49   { "grep", Gcompile, EGexecute },
  50   { "egrep", Ecompile, EGexecute },
  51   { "awk", Ecompile, EGexecute },
  52   { "fgrep", Fcompile, Fexecute },
  53   { 0, 0, 0 },
  54 };
  55
  56 /* For -w, we also consider _ to be word constituent.  */
  57 #define WCHAR(C) (ISALNUM(C) || (C) == '_')
  58
  59 /* DFA compiled regexp. */
  60 static struct dfa dfa;
  61
  62 /* Regex compiled regexp. */
  63 static struct re_pattern_buffer regexbuf;
  64
  65 /* KWset compiled pattern.  For Ecompile and Gcompile, we compile
  66    a list of strings, at least one of which is known to occur in
  67    any string matching the regexp. */
  68 static kwset_t kwset;
  69
  70 /* Last compiled fixed string known to exactly match the regexp.
  71    If kwsexec() returns < lastexact, then we don't need to
  72    call the regexp matcher at all. */
  73 static int lastexact;
  74
  75 void
  76 dfaerror (char const *mesg)
  77 {
  78   fatal(mesg, 0);
  79 }
  80
  81 static void
  82 kwsinit (void)
  83 {
  84   static char trans[NCHAR];
  85   int i;
  86
  87   if (match_icase)
  88     for (i = 0; i < NCHAR; ++i)
  89       trans[i] = TOLOWER(i);
  90
  91   if (!(kwset = kwsalloc(match_icase ? trans : (char *) 0)))
  92     fatal("memory exhausted", 0);
  93 }
  94
  95 /* If the DFA turns out to have some set of fixed strings one of
  96    which must occur in the match, then we build a kwset matcher
  97    to find those strings, and thus quickly filter out impossible
  98    matches. */
  99 static void
 100 kwsmusts (void)
 101 {
 102   struct dfamust *dm;
 103   char *err;
 104
 105   if (dfa.musts)
 106     {
 107       kwsinit();
 108       /* First, we compile in the substrings known to be exact
 109          matches.  The kwset matcher will return the index
 110          of the matching string that it chooses. */
 111       for (dm = dfa.musts; dm; dm = dm->next)
 112         {
 113           if (!dm->exact)
 114             continue;
 115           ++lastexact;
 116           if ((err = kwsincr(kwset, dm->must, strlen(dm->must))) != 0)
 117             fatal(err, 0);
 118         }
 119       /* Now, we compile the substrings that will require
 120          the use of the regexp matcher.  */
 121       for (dm = dfa.musts; dm; dm = dm->next)
 122         {
 123           if (dm->exact)
 124             continue;
 125           if ((err = kwsincr(kwset, dm->must, strlen(dm->must))) != 0)
 126             fatal(err, 0);
 127         }
 128       if ((err = kwsprep(kwset)) != 0)
 129         fatal(err, 0);
 130     }
 131 }
 132
 133 static void
 134 Gcompile (char *pattern, size_t size)
 135 {
 136   const char *err;
 137
 138   re_set_syntax(RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE);
 139   dfasyntax(RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE, match_icase, eolbyte);
 140
 141   if ((err = re_compile_pattern(pattern, size, &regexbuf)) != 0)
 142     fatal(err, 0);
 143
 144   /* In the match_words and match_lines cases, we use a different pattern
 145      for the DFA matcher that will quickly throw out cases that won't work.
 146      Then if DFA succeeds we do some hairy stuff using the regex matcher
 147      to decide whether the match should really count. */
 148   if (match_words || match_lines)
 149     {
 150       /* In the whole-word case, we use the pattern:
 151          (^|[^A-Za-z_])(userpattern)([^A-Za-z_]|$).
 152          In the whole-line case, we use the pattern:
 153          ^(userpattern)$.
 154          BUG: Using [A-Za-z_] is locale-dependent!
 155          So will use [:alnum:] */
 156
 157       char *n = malloc(size + 50);
 158       int i = 0;
 159
 160       strcpy(n, "");
 161
 162       if (match_lines)
 163         strcpy(n, "^\\(");
 164       if (match_words)
 165         strcpy(n, "\\(^\\|[^[:alnum:]_]\\)\\(");
 166
 167       i = strlen(n);
 168       memcpy(n + i, pattern, size);
 169       i += size;
 170
 171       if (match_words)
 172         strcpy(n + i, "\\)\\([^[:alnum:]_]\\|$\\)");
 173       if (match_lines)
 174         strcpy(n + i, "\\)$");
 175
 176       i += strlen(n + i);
 177       dfacomp(n, i, &dfa, 1);
 178     }
 179   else
 180     dfacomp(pattern, size, &dfa, 1);
 181
 182   kwsmusts();
 183 }
 184
 185 static void
 186 Ecompile (char *pattern, size_t size)
 187 {
 188   const char *err;
 189
 190   if (strcmp(matcher, "awk") == 0)
 191     {
 192       re_set_syntax(RE_SYNTAX_AWK);
 193       dfasyntax(RE_SYNTAX_AWK, match_icase, eolbyte);
 194     }
 195   else
 196     {
 197       re_set_syntax (RE_SYNTAX_POSIX_EGREP);
 198       dfasyntax (RE_SYNTAX_POSIX_EGREP, match_icase, eolbyte);
 199     }
 200
 201   if ((err = re_compile_pattern(pattern, size, &regexbuf)) != 0)
 202     fatal(err, 0);
 203
 204   /* In the match_words and match_lines cases, we use a different pattern
 205      for the DFA matcher that will quickly throw out cases that won't work.
 206      Then if DFA succeeds we do some hairy stuff using the regex matcher
 207      to decide whether the match should really count. */
 208   if (match_words || match_lines)
 209     {
 210       /* In the whole-word case, we use the pattern:
 211          (^|[^A-Za-z_])(userpattern)([^A-Za-z_]|$).
 212          In the whole-line case, we use the pattern:
 213          ^(userpattern)$.
 214          BUG: Using [A-Za-z_] is locale-dependent!
 215          so will use the char class */
 216
 217       char *n = malloc(size + 50);
 218       int i = 0;
 219
 220       strcpy(n, "");
 221
 222       if (match_lines)
 223         strcpy(n, "^(");
 224       if (match_words)
 225         strcpy(n, "(^|[^[:alnum:]_])(");
 226
 227       i = strlen(n);
 228       memcpy(n + i, pattern, size);
 229       i += size;
 230
 231       if (match_words)
 232         strcpy(n + i, ")([^[:alnum:]_]|$)");
 233       if (match_lines)
 234         strcpy(n + i, ")$");
 235
 236       i += strlen(n + i);
 237       dfacomp(n, i, &dfa, 1);
 238     }
 239   else
 240     dfacomp(pattern, size, &dfa, 1);
 241
 242   kwsmusts();
 243 }
 244
 245 static char *
 246 EGexecute (char *buf, size_t size, char **endp)
 247 {
 248   register char *buflim, *beg, *end, save;
 249   char eol = eolbyte;
 250   int backref, start, len;
 251   struct kwsmatch kwsm;
 252   static struct re_registers regs; /* This is static on account of a BRAIN-DEAD
 253                                     Q@#%!# library interface in regex.c.  */
 254
 255   buflim = buf + size;
 256
 257   for (beg = end = buf; end < buflim; beg = end + 1)
 258     {
 259       if (kwset)
 260         {
 261           /* Find a possible match using the KWset matcher. */
 262           beg = kwsexec(kwset, beg, buflim - beg, &kwsm);
 263           if (!beg)
 264             goto failure;
 265           /* Narrow down to the line containing the candidate, and
 266              run it through DFA. */
 267           end = memchr(beg, eol, buflim - beg);
 268           if (!end)
 269             end = buflim;
 270           while (beg > buf && beg[-1] != eol)
 271             --beg;
 272           save = *end;
 273           if (kwsm.index < lastexact)
 274             goto success;
 275           if (!dfaexec(&dfa, beg, end, 0, (int *) 0, &backref))
 276             {
 277               *end = save;
 278               continue;
 279             }
 280           *end = save;
 281           /* Successful, no backreferences encountered. */
 282           if (!backref)
 283             goto success;
 284         }
 285       else
 286         {
 287           /* No good fixed strings; start with DFA. */
 288           save = *buflim;
 289           beg = dfaexec(&dfa, beg, buflim, 0, (int *) 0, &backref);
 290           *buflim = save;
 291           if (!beg)
 292             goto failure;
 293           /* Narrow down to the line we've found. */
 294           end = memchr(beg, eol, buflim - beg);
 295           if (!end)
 296             end = buflim;
 297           while (beg > buf && beg[-1] != eol)
 298             --beg;
 299           /* Successful, no backreferences encountered! */
 300           if (!backref)
 301             goto success;
 302         }
 303       /* If we've made it to this point, this means DFA has seen
 304          a probable match, and we need to run it through Regex. */
 305       regexbuf.not_eol = 0;
 306       if ((start = re_search(&regexbuf, beg, end - beg, 0, end - beg, &regs)) >= 0)
 307         {
 308           len = regs.end[0] - start;
 309           if ((!match_lines && !match_words)
 310               || (match_lines && len == end - beg))
 311             goto success;
 312           /* If -w, check if the match aligns with word boundaries.
 313              We do this iteratively because:
 314              (a) the line may contain more than one occurence of the pattern, and
 315              (b) Several alternatives in the pattern might be valid at a given
 316              point, and we may need to consider a shorter one to find a word
 317              boundary. */
 318           if (match_words)
 319             while (start >= 0)
 320               {
 321                 if ((start == 0 || !WCHAR ((unsigned char) beg[start - 1]))
 322                     && (len == end - beg
 323                         || !WCHAR ((unsigned char) beg[start + len])))
 324                   goto success;
 325                 if (len > 0)
 326                   {
 327                     /* Try a shorter length anchored at the same place. */
 328                     --len;
 329                     regexbuf.not_eol = 1;
 330                     len = re_match(&regexbuf, beg, start + len, start, &regs);
 331                   }
 332                 if (len <= 0)
 333                   {
 334                     /* Try looking further on. */
 335                     if (start == end - beg)
 336                       break;
 337                     ++start;
 338                     regexbuf.not_eol = 0;
 339                     start = re_search(&regexbuf, beg, end - beg,
 340                                       start, end - beg - start, &regs);
 341                     len = regs.end[0] - start;
 342                   }
 343               }
 344         }
 345     }
 346
 347  failure:
 348   return 0;
 349
 350  success:
 351   *endp = end < buflim ? end + 1 : end;
 352   return beg;
 353 }
 354
 355 static void
 356 Fcompile (char *pattern, size_t size)
 357 {
 358   char *beg, *lim, *err;
 359
 360   kwsinit();
 361   beg = pattern;
 362   do
 363     {
 364       for (lim = beg; lim < pattern + size && *lim != '\n'; ++lim)
 365         ;
 366       if ((err = kwsincr(kwset, beg, lim - beg)) != 0)
 367         fatal(err, 0);
 368       if (lim < pattern + size)
 369         ++lim;
 370       beg = lim;
 371     }
 372   while (beg < pattern + size);
 373
 374   if ((err = kwsprep(kwset)) != 0)
 375     fatal(err, 0);
 376 }
 377
 378 static char *
 379 Fexecute (char *buf, size_t size, char **endp)
 380 {
 381   register char *beg, *try, *end;
 382   register size_t len;
 383   char eol = eolbyte;
 384   struct kwsmatch kwsmatch;
 385
 386   for (beg = buf; beg <= buf + size; ++beg)
 387     {
 388       if (!(beg = kwsexec(kwset, beg, buf + size - beg, &kwsmatch)))
 389         return 0;
 390       len = kwsmatch.size[0];
 391       if (match_lines)
 392         {
 393           if (beg > buf && beg[-1] != eol)
 394             continue;
 395           if (beg + len < buf + size && beg[len] != eol)
 396             continue;
 397           goto success;
 398         }
 399       else if (match_words)
 400         for (try = beg; len && try;)
 401           {
 402             if (try > buf && WCHAR((unsigned char) try[-1]))
 403               break;
 404             if (try + len < buf + size && WCHAR((unsigned char) try[len]))
 405               {
 406                 try = kwsexec(kwset, beg, --len, &kwsmatch);
 407                 len = kwsmatch.size[0];
 408               }
 409             else
 410               goto success;
 411           }
 412       else
 413         goto success;
 414     }
 415
 416   return 0;
 417
 418  success:
 419   if ((end = memchr(beg + len, eol, (buf + size) - (beg + len))) != 0)
 420     ++end;
 421   else
 422     end = buf + size;
 423   *endp = end;
 424   while (beg > buf && beg[-1] != '\n')
 425     --beg;
 426   return beg;
 427 }