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