Print this page
8858 /usr/bin/grep doesn't support -E option
4580 /usr/bin/grep can't handle multibyte characters
8929 8868 tests are not delivered with system/test/utiltest
8860 Example in grep(1) is incorrect
Reviewed by: Peter Tribble <peter.tribble@gmail.com>
Reviewed by: Toomas Soome <tsoome@me.com>
Reviewed by: Yuri Pankov <yuripv@gmx.com>

Split Close
Expand all
Collapse all
          --- old/usr/src/cmd/grep/grep.c
          +++ new/usr/src/cmd/grep/grep.c
↓ open down ↓ 12 lines elided ↑ open up ↑
  13   13   *
  14   14   * When distributing Covered Code, include this CDDL HEADER in each
  15   15   * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16   16   * If applicable, add the following below this CDDL HEADER, with the
  17   17   * fields enclosed by brackets "[]" replaced with your own identifying
  18   18   * information: Portions Copyright [yyyy] [name of copyright owner]
  19   19   *
  20   20   * CDDL HEADER END
  21   21   */
  22   22  /*
  23      - * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
       23 + * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
  24   24   * Use is subject to license terms.
  25   25   */
  26   26  
  27      -/*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
  28      -/*        All Rights Reserved   */
  29      -
  30      -/*      Copyright (c) 1987, 1988 Microsoft Corporation  */
  31      -/*        All Rights Reserved   */
  32      -
  33      -/* Copyright 2012 Nexenta Systems, Inc.  All rights reserved. */
  34      -
  35   27  /*
  36      - * Copyright 2013 Damian Bogel. All rights reserved.
       28 + * grep - pattern matching program - combined grep, egrep, and fgrep.
       29 + *      Based on MKS grep command, with XCU & Solaris mods.
  37   30   */
  38   31  
  39   32  /*
  40      - * grep -- print lines matching (or not matching) a pattern
       33 + * Copyright 1985, 1992 by Mortice Kern Systems Inc.  All rights reserved.
  41   34   *
  42      - *      status returns:
  43      - *              0 - ok, and some matches
  44      - *              1 - ok, but no matches
  45      - *              2 - some error
  46   35   */
  47   36  
  48      -#include <sys/types.h>
       37 +/* Copyright 2017 Nexenta Systems, Inc.  All rights reserved. */
       38 +
       39 +/*
       40 + * Copyright 2013 Damian Bogel. All rights reserved.
       41 + */
  49   42  
       43 +#include <string.h>
       44 +#include <stdlib.h>
  50   45  #include <ctype.h>
       46 +#include <stdarg.h>
       47 +#include <regex.h>
       48 +#include <limits.h>
       49 +#include <sys/types.h>
       50 +#include <sys/stat.h>
  51   51  #include <fcntl.h>
  52      -#include <locale.h>
  53      -#include <memory.h>
  54      -#include <regexpr.h>
  55   52  #include <stdio.h>
  56      -#include <stdlib.h>
  57      -#include <string.h>
       53 +#include <locale.h>
       54 +#include <wchar.h>
       55 +#include <errno.h>
  58   56  #include <unistd.h>
       57 +#include <wctype.h>
  59   58  #include <ftw.h>
  60      -#include <limits.h>
  61   59  #include <sys/param.h>
  62   60  
  63      -static const char *errstr[] = {
  64      -        "Range endpoint too large.",
  65      -        "Bad number.",
  66      -        "``\\digit'' out of range.",
  67      -        "No remembered search string.",
  68      -        "\\( \\) imbalance.",
  69      -        "Too many \\(.",
  70      -        "More than 2 numbers given in \\{ \\}.",
  71      -        "} expected after \\.",
  72      -        "First number exceeds second in \\{ \\}.",
  73      -        "[ ] imbalance.",
  74      -        "Regular expression overflow.",
  75      -        "Illegal byte sequence.",
  76      -        "Unknown regexp error code!!",
  77      -        NULL
  78      -};
  79      -
  80      -#define STDIN_FILENAME  gettext("(standard input)")
  81      -
  82      -#define errmsg(msg, arg)        (void) fprintf(stderr, gettext(msg), arg)
  83      -#define BLKSIZE 512
  84      -#define GBUFSIZ 8192
  85      -#define MAX_DEPTH       1000
  86      -
  87      -static int      temp;
  88      -static long long        lnum;
  89      -static char     *linebuf;
  90      -static char     *prntbuf = NULL;
  91      -static long     fw_lPrntBufLen = 0;
  92      -static int      nflag;
  93      -static int      bflag;
  94      -static int      lflag;
  95      -static int      cflag;
  96      -static int      rflag;
  97      -static int      Rflag;
  98      -static int      vflag;
  99      -static int      sflag;
 100      -static int      iflag;
 101      -static int      wflag;
 102      -static int      hflag;
 103      -static int      Hflag;
 104      -static int      qflag;
 105      -static int      errflg;
 106      -static int      nfile;
 107      -static long long        tln;
 108      -static int      nsucc;
 109      -static int      outfn = 0;
 110      -static int      nlflag;
 111      -static char     *ptr, *ptrend;
 112      -static char     *expbuf;
 113      -
 114      -static void     execute(const char *, int);
 115      -static void     regerr(int);
 116      -static void     prepare(const char *);
       61 +#define STDIN_FILENAME gettext("(standard input)")
       62 +
       63 +#define BSIZE           512             /* Size of block for -b */
       64 +#define BUFSIZE         8192            /* Input buffer size */
       65 +#define MAX_DEPTH       1000            /* how deep to recurse */
       66 +
       67 +#define AFTER   1                       /* 'After' Context */
       68 +#define BEFORE  2                       /* 'Before' Context */
       69 +#define CONTEXT (AFTER|BEFORE)          /* Full Context */
       70 +
       71 +#define M_CSETSIZE      256             /* singlebyte chars */
       72 +static int      bmglen;                 /* length of BMG pattern */
       73 +static char     *bmgpat;                /* BMG pattern */
       74 +static int      bmgtab[M_CSETSIZE];     /* BMG delta1 table */
       75 +
       76 +typedef struct  _PATTERN        {
       77 +        char    *pattern;               /* original pattern */
       78 +        wchar_t *wpattern;              /* wide, lowercased pattern */
       79 +        struct  _PATTERN        *next;
       80 +        regex_t re;                     /* compiled pattern */
       81 +} PATTERN;
       82 +
       83 +static PATTERN  *patterns;
       84 +static char     errstr[128];            /* regerror string buffer */
       85 +static int      regflags = 0;           /* regcomp options */
       86 +static int      matched = 0;            /* return of the grep() */
       87 +static int      errors = 0;             /* count of errors */
       88 +static uchar_t  fgrep = 0;              /* Invoked as fgrep */
       89 +static uchar_t  egrep = 0;              /* Invoked as egrep */
       90 +static boolean_t        nvflag = B_TRUE;        /* Print matching lines */
       91 +static uchar_t  cflag;                  /* Count of matches */
       92 +static uchar_t  iflag;                  /* Case insensitve matching */
       93 +static uchar_t  Hflag;                  /* Precede lines by file name */
       94 +static uchar_t  hflag;                  /* Supress printing of filename */
       95 +static uchar_t  lflag;                  /* Print file names of matches */
       96 +static uchar_t  nflag;                  /* Precede lines by line number */
       97 +static uchar_t  rflag;                  /* Search directories recursively */
       98 +static uchar_t  bflag;                  /* Preccede matches by block number */
       99 +static uchar_t  sflag;                  /* Suppress file error messages */
      100 +static uchar_t  qflag;                  /* Suppress standard output */
      101 +static uchar_t  wflag;                  /* Search for expression as a word */
      102 +static uchar_t  xflag;                  /* Anchoring */
      103 +static uchar_t  Eflag;                  /* Egrep or -E flag */
      104 +static uchar_t  Fflag;                  /* Fgrep or -F flag */
      105 +static uchar_t  Rflag;                  /* Like rflag, but follow symlinks */
      106 +static uchar_t  outfn;                  /* Put out file name */
      107 +static uchar_t  conflag;                /* show context of matches */
      108 +static char     *cmdname;
      109 +
      110 +static int      use_wchar, use_bmg, mblocale;
      111 +
      112 +static size_t   outbuflen, prntbuflen, conbuflen;
      113 +static unsigned long    conalen, conblen, conmatches;
      114 +static char     *prntbuf, *conbuf;
      115 +static wchar_t  *outline;
      116 +
      117 +static void     addfile(const char *fn);
      118 +static void     addpattern(char *s);
      119 +static void     fixpatterns(void);
      120 +static void     usage(void);
      121 +static int      grep(int, const char *);
      122 +static void     bmgcomp(char *, int);
      123 +static char     *bmgexec(char *, char *);
 117  124  static int      recursive(const char *, const struct stat *, int, struct FTW *);
 118      -static int      succeed(const char *);
      125 +static void     process_path(const char *);
      126 +static void     process_file(const char *, int);
 119  127  
      128 +/*
      129 + * mainline for grep
      130 + */
 120  131  int
 121  132  main(int argc, char **argv)
 122  133  {
      134 +        char    *ap, *test;
 123  135          int     c;
 124      -        char    *arg;
 125      -        extern int      optind;
      136 +        int     fflag = 0;
      137 +        int     i, n_pattern = 0, n_file = 0;
      138 +        char    **pattern_list = NULL;
      139 +        char    **file_list = NULL;
 126  140  
 127  141          (void) setlocale(LC_ALL, "");
 128  142  #if !defined(TEXT_DOMAIN)       /* Should be defined by cc -D */
 129      -#define TEXT_DOMAIN "SYS_TEST"  /* Use this only if it weren't */
      143 +#define TEXT_DOMAIN     "SYS_TEST"      /* Use this only if it weren't */
 130  144  #endif
 131  145          (void) textdomain(TEXT_DOMAIN);
 132  146  
 133      -        while ((c = getopt(argc, argv, "hHqblcnRrsviyw")) != -1)
 134      -                switch (c) {
 135      -                /* based on options order h or H is set as in GNU grep */
 136      -                case 'h':
 137      -                        hflag++;
 138      -                        Hflag = 0; /* h excludes H */
      147 +        /*
      148 +         * true if this is running on the multibyte locale
      149 +         */
      150 +        mblocale = (MB_CUR_MAX > 1);
      151 +        /*
      152 +         * Skip leading slashes
      153 +         */
      154 +        cmdname = argv[0];
      155 +        if (ap = strrchr(cmdname, '/'))
      156 +                cmdname = ap + 1;
      157 +
      158 +        ap = cmdname;
      159 +        /*
      160 +         * Detect egrep/fgrep via command name, map to -E and -F options.
      161 +         */
      162 +        if (*ap == 'e' || *ap == 'E') {
      163 +                regflags |= REG_EXTENDED;
      164 +                egrep++;
      165 +        } else {
      166 +                if (*ap == 'f' || *ap == 'F') {
      167 +                        fgrep++;
      168 +                }
      169 +        }
      170 +
      171 +        /* check for non-standard "-line-count" option */
      172 +        for (i = 1; i < argc; i++) {
      173 +                if (strcmp(argv[i], "--") == 0)
 139  174                          break;
 140      -                case 'H':
 141      -                        if (!lflag) /* H is excluded by l */
 142      -                                Hflag++;
 143      -                        hflag = 0; /* H excludes h */
      175 +
      176 +                /* isdigit() check prevents negative arguments */
      177 +                if ((argv[i][0] == '-') && isdigit(argv[i][1])) {
      178 +                        if (strlen(&argv[i][1]) !=
      179 +                            strspn(&argv[i][1], "0123456789")) {
      180 +                                (void) fprintf(stderr, gettext(
      181 +                                    "%s: Bad number flag\n"), argv[0]);
      182 +                                usage();
      183 +                        }
      184 +
      185 +                        errno = 0;
      186 +                        conalen = conblen = strtoul(&argv[i][1], (char **)NULL,
      187 +                            10);
      188 +
      189 +                        if (errno != 0 || conalen >= ULONG_MAX) {
      190 +                                (void) fprintf(stderr, gettext(
      191 +                                    "%s: Bad context argument\n"), argv[0]);
      192 +                        } else if (conalen)
      193 +                                conflag = CONTEXT;
      194 +
      195 +                        while (i < argc) {
      196 +                                argv[i] = argv[i + 1];
      197 +                                i++;
      198 +                        }
      199 +                        argc--;
      200 +                }
      201 +        }
      202 +
      203 +        while ((c = getopt(argc, argv, "vwchHilnrbse:f:qxEFIRA:B:C:")) != EOF) {
      204 +                unsigned long tval;
      205 +                switch (c) {
      206 +                case 'v':       /* POSIX: negate matches */
      207 +                        nvflag = B_FALSE;
 144  208                          break;
 145      -                case 'q':       /* POSIX: quiet: status only */
 146      -                        qflag++;
      209 +
      210 +                case 'c':       /* POSIX: write count */
      211 +                        cflag++;
 147  212                          break;
 148      -                case 'v':
 149      -                        vflag++;
      213 +
      214 +                case 'i':       /* POSIX: ignore case */
      215 +                        iflag++;
      216 +                        regflags |= REG_ICASE;
 150  217                          break;
 151      -                case 'c':
 152      -                        cflag++;
      218 +
      219 +                case 'l':       /* POSIX: Write filenames only */
      220 +                        lflag++;
 153  221                          break;
 154      -                case 'n':
      222 +
      223 +                case 'n':       /* POSIX: Write line numbers */
 155  224                          nflag++;
 156  225                          break;
 157      -                case 'R':
 158      -                        Rflag++;
 159      -                        /* FALLTHROUGH */
 160      -                case 'r':
      226 +
      227 +                case 'r':       /* Solaris: search recursively */
 161  228                          rflag++;
 162  229                          break;
 163      -                case 'b':
      230 +
      231 +                case 'b':       /* Solaris: Write file block numbers */
 164  232                          bflag++;
 165  233                          break;
 166      -                case 's':
      234 +
      235 +                case 's':       /* POSIX: No error msgs for files */
 167  236                          sflag++;
 168  237                          break;
 169      -                case 'l':
 170      -                        lflag++;
 171      -                        Hflag = 0; /* l excludes H */
      238 +
      239 +                case 'e':       /* POSIX: pattern list */
      240 +                        n_pattern++;
      241 +                        pattern_list = realloc(pattern_list,
      242 +                            sizeof (char *) * n_pattern);
      243 +                        if (pattern_list == NULL) {
      244 +                                (void) fprintf(stderr,
      245 +                                    gettext("%s: out of memory\n"),
      246 +                                    cmdname);
      247 +                                exit(2);
      248 +                        }
      249 +                        *(pattern_list + n_pattern - 1) = optarg;
 172  250                          break;
 173      -                case 'y':
 174      -                case 'i':
 175      -                        iflag++;
      251 +
      252 +                case 'f':       /* POSIX: pattern file */
      253 +                        fflag = 1;
      254 +                        n_file++;
      255 +                        file_list = realloc(file_list,
      256 +                            sizeof (char *) * n_file);
      257 +                        if (file_list == NULL) {
      258 +                                (void) fprintf(stderr,
      259 +                                    gettext("%s: out of memory\n"),
      260 +                                    cmdname);
      261 +                                exit(2);
      262 +                        }
      263 +                        *(file_list + n_file - 1) = optarg;
      264 +                        break;
      265 +
      266 +                /* based on options order h or H is set as in GNU grep */
      267 +                case 'h':       /* Solaris: supress printing of file name */
      268 +                        hflag = 1;
      269 +                        Hflag = 0;
      270 +                        break;
      271 +                /* Solaris: precede every matching with file name */
      272 +                case 'H':
      273 +                        Hflag = 1;
      274 +                        hflag = 0;
      275 +                        break;
      276 +
      277 +                case 'q':       /* POSIX: quiet: status only */
      278 +                        qflag++;
 176  279                          break;
 177      -                case 'w':
      280 +
      281 +                case 'w':       /* Solaris: treat pattern as word */
 178  282                          wflag++;
 179  283                          break;
 180      -                case '?':
 181      -                        errflg++;
      284 +
      285 +                case 'x':       /* POSIX: full line matches */
      286 +                        xflag++;
      287 +                        regflags |= REG_ANCHOR;
      288 +                        break;
      289 +
      290 +                case 'E':       /* POSIX: Extended RE's */
      291 +                        regflags |= REG_EXTENDED;
      292 +                        Eflag++;
      293 +                        break;
      294 +
      295 +                case 'F':       /* POSIX: strings, not RE's */
      296 +                        Fflag++;
      297 +                        break;
      298 +
      299 +                case 'R':       /* Solaris: like rflag, but follow symlinks */
      300 +                        Rflag++;
      301 +                        rflag++;
      302 +                        break;
      303 +
      304 +                case 'A':       /* print N lines after each match */
      305 +                        errno = 0;
      306 +                        conalen = strtoul(optarg, &test, 10);
      307 +                        /* *test will be non-null if optarg is negative */
      308 +                        if (errno != 0 || *test != '\0' ||
      309 +                            conalen >= ULONG_MAX) {
      310 +                                (void) fprintf(stderr, gettext(
      311 +                                    "%s: Bad context argument: %s\n"),
      312 +                                    argv[0], optarg);
      313 +                                exit(2);
      314 +                        }
      315 +                        if (conalen)
      316 +                                conflag |= AFTER;
      317 +                        else
      318 +                                conflag &= ~AFTER;
      319 +                        break;
      320 +                case 'B':       /* print N lines before each match */
      321 +                        errno = 0;
      322 +                        conblen = strtoul(optarg, &test, 10);
      323 +                        /* *test will be non-null if optarg is negative */
      324 +                        if (errno != 0 || *test != '\0' ||
      325 +                            conblen >= ULONG_MAX) {
      326 +                                (void) fprintf(stderr, gettext(
      327 +                                    "%s: Bad context argument: %s\n"),
      328 +                                    argv[0], optarg);
      329 +                                exit(2);
      330 +                        }
      331 +                        if (conblen)
      332 +                                conflag |= BEFORE;
      333 +                        else
      334 +                                conflag &= ~BEFORE;
      335 +                        break;
      336 +                case 'C':       /* print N lines around each match */
      337 +                        errno = 0;
      338 +                        tval = strtoul(optarg, &test, 10);
      339 +                        /* *test will be non-null if optarg is negative */
      340 +                        if (errno != 0 || *test != '\0' || tval >= ULONG_MAX) {
      341 +                                (void) fprintf(stderr, gettext(
      342 +                                    "%s: Bad context argument: %s\n"),
      343 +                                    argv[0], optarg);
      344 +                                exit(2);
      345 +                        }
      346 +                        if (tval) {
      347 +                                if ((conflag & BEFORE) == 0)
      348 +                                        conblen = tval;
      349 +                                if ((conflag & AFTER) == 0)
      350 +                                        conalen = tval;
      351 +                                conflag = CONTEXT;
      352 +                        }
      353 +                        break;
      354 +
      355 +                default:
      356 +                        usage();
 182  357                  }
      358 +        }
      359 +        /*
      360 +         * If we're invoked as egrep or fgrep we need to do some checks
      361 +         */
 183  362  
 184      -        if (errflg || (optind >= argc)) {
 185      -                errmsg("Usage: grep [-c|-l|-q] [-r|-R] -hHbnsviw "
 186      -                    "pattern file . . .\n",
 187      -                    (char *)NULL);
 188      -                exit(2);
      363 +        if (egrep || fgrep) {
      364 +                /*
      365 +                 * Use of -E or -F with egrep or fgrep is illegal
      366 +                 */
      367 +                if (Eflag || Fflag)
      368 +                        usage();
      369 +                /*
      370 +                 * Don't allow use of wflag with egrep / fgrep
      371 +                 */
      372 +                if (wflag)
      373 +                        usage();
      374 +                /*
      375 +                 * For Solaris the -s flag is equivalent to XCU -q
      376 +                 */
      377 +                if (sflag)
      378 +                        qflag++;
      379 +                /*
      380 +                 * done with above checks - set the appropriate flags
      381 +                 */
      382 +                if (egrep)
      383 +                        Eflag++;
      384 +                else                    /* Else fgrep */
      385 +                        Fflag++;
 189  386          }
 190  387  
 191      -        argv = &argv[optind];
 192      -        argc -= optind;
 193      -        nfile = argc - 1;
      388 +        if (wflag && (Eflag || Fflag)) {
      389 +                /*
      390 +                 * -w cannot be specified with grep -F
      391 +                 */
      392 +                usage();
      393 +        }
      394 +
      395 +        /*
      396 +         * -E and -F flags are mutually exclusive - check for this
      397 +         */
      398 +        if (Eflag && Fflag)
      399 +                usage();
      400 +
      401 +        /*
      402 +         * -l overrides -H like in GNU grep
      403 +         */
      404 +        if (lflag)
      405 +                Hflag = 0;
 194  406  
 195      -        if (strrchr(*argv, '\n') != NULL)
 196      -                regerr(41);
      407 +        /*
      408 +         * -c, -l and -q flags are mutually exclusive
      409 +         * We have -c override -l like in Solaris.
      410 +         * -q overrides -l & -c programmatically in grep() function.
      411 +         */
      412 +        if (cflag && lflag)
      413 +                lflag = 0;
 197  414  
 198      -        if (iflag) {
 199      -                for (arg = *argv; *arg != NULL; ++arg)
 200      -                        *arg = (char)tolower((int)((unsigned char)*arg));
      415 +        argv += optind - 1;
      416 +        argc -= optind - 1;
      417 +
      418 +        /*
      419 +         * Now handling -e and -f option
      420 +         */
      421 +        if (pattern_list) {
      422 +                for (i = 0; i < n_pattern; i++) {
      423 +                        addpattern(pattern_list[i]);
      424 +                }
      425 +                free(pattern_list);
      426 +        }
      427 +        if (file_list) {
      428 +                for (i = 0; i < n_file; i++) {
      429 +                        addfile(file_list[i]);
      430 +                }
      431 +                free(file_list);
 201  432          }
 202  433  
 203      -        if (wflag) {
 204      -                unsigned int    wordlen;
 205      -                char            *wordbuf;
      434 +        /*
      435 +         * No -e or -f?  Make sure there is one more arg, use it as the pattern.
      436 +         */
      437 +        if (patterns == NULL && !fflag) {
      438 +                if (argc < 2)
      439 +                        usage();
      440 +                addpattern(argv[1]);
      441 +                argc--;
      442 +                argv++;
      443 +        }
 206  444  
 207      -                wordlen = strlen(*argv) + 5; /* '\\' '<' *argv '\\' '>' '\0' */
 208      -                if ((wordbuf = malloc(wordlen)) == NULL) {
 209      -                        errmsg("grep: Out of memory for word\n", (char *)NULL);
 210      -                        exit(2);
      445 +        /*
      446 +         * If -x flag is not specified or -i flag is specified
      447 +         * with fgrep in a multibyte locale, need to use
      448 +         * the wide character APIs.  Otherwise, byte-oriented
      449 +         * process will be done.
      450 +         */
      451 +        use_wchar = Fflag && mblocale && (!xflag || iflag);
      452 +
      453 +        /*
      454 +         * Compile Patterns and also decide if BMG can be used
      455 +         */
      456 +        fixpatterns();
      457 +
      458 +        /* Process all files: stdin, or rest of arg list */
      459 +        if (argc < 2) {
      460 +                matched = grep(0, STDIN_FILENAME);
      461 +        } else {
      462 +                if (Hflag || (argc > 2 && hflag == 0))
      463 +                        outfn = 1;      /* Print filename on match line */
      464 +                for (argv++; *argv != NULL; argv++) {
      465 +                        process_path(*argv);
 211  466                  }
      467 +        }
      468 +        /*
      469 +         * Return() here is used instead of exit
      470 +         */
 212  471  
 213      -                (void) strcpy(wordbuf, "\\<");
 214      -                (void) strcat(wordbuf, *argv);
 215      -                (void) strcat(wordbuf, "\\>");
 216      -                *argv = wordbuf;
 217      -        }
 218      -
 219      -        expbuf = compile(*argv, (char *)0, (char *)0);
 220      -        if (regerrno)
 221      -                regerr(regerrno);
 222      -
 223      -        if (--argc == 0)
 224      -                execute(NULL, 0);
 225      -        else
 226      -                while (argc-- > 0)
 227      -                        prepare(*++argv);
      472 +        (void) fflush(stdout);
 228  473  
 229      -        return (nsucc == 2 ? 2 : (nsucc == 0 ? 1 : 0));
      474 +        if (errors)
      475 +                return (2);
      476 +        return (matched ? 0 : 1);
 230  477  }
 231  478  
 232  479  static void
 233      -prepare(const char *path)
      480 +process_path(const char *path)
 234  481  {
 235  482          struct  stat st;
 236  483          int     walkflags = FTW_CHDIR;
 237  484          char    *buf = NULL;
 238  485  
 239  486          if (rflag) {
 240  487                  if (stat(path, &st) != -1 &&
 241  488                      (st.st_mode & S_IFMT) == S_IFDIR) {
 242      -                        outfn = 1;
      489 +                        outfn = 1; /* Print filename */
 243  490  
 244  491                          /*
 245  492                           * Add trailing slash if arg
 246  493                           * is directory, to resolve symlinks.
 247  494                           */
 248  495                          if (path[strlen(path) - 1] != '/') {
 249  496                                  (void) asprintf(&buf, "%s/", path);
 250  497                                  if (buf != NULL)
 251  498                                          path = buf;
 252  499                          }
 253  500  
 254  501                          /*
 255  502                           * Search through subdirs if path is directory.
 256  503                           * Don't follow symlinks if Rflag is not set.
 257  504                           */
 258  505                          if (!Rflag)
 259  506                                  walkflags |= FTW_PHYS;
 260  507  
 261  508                          if (nftw(path, recursive, MAX_DEPTH, walkflags) != 0) {
 262  509                                  if (!sflag)
 263      -                                        errmsg("grep: can't open %s\n", path);
 264      -                                nsucc = 2;
      510 +                                        (void) fprintf(stderr,
      511 +                                            gettext("%s: can't open \"%s\"\n"),
      512 +                                            cmdname, path);
      513 +                                errors = 1;
 265  514                          }
 266  515                          return;
 267  516                  }
 268  517          }
 269      -        execute(path, 0);
      518 +        process_file(path, 0);
 270  519  }
 271  520  
      521 +/*
      522 + * Read and process all files in directory recursively.
      523 + */
 272  524  static int
 273  525  recursive(const char *name, const struct stat *statp, int info, struct FTW *ftw)
 274  526  {
 275  527          /*
 276      -         * process files and follow symlinks if Rflag set.
      528 +         * Process files and follow symlinks if Rflag set.
 277  529           */
 278  530          if (info != FTW_F) {
      531 +                /* Report broken symlinks and unreadable files */
 279  532                  if (!sflag &&
 280  533                      (info == FTW_SLN || info == FTW_DNR || info == FTW_NS)) {
 281      -                        /* report broken symlinks and unreadable files */
 282      -                        errmsg("grep: can't open %s\n", name);
      534 +                        (void) fprintf(stderr,
      535 +                            gettext("%s: can't open \"%s\"\n"), cmdname, name);
 283  536                  }
 284  537                  return (0);
 285  538          }
 286  539  
 287      -        /* skip devices and pipes if Rflag is not set */
      540 +
      541 +        /* Skip devices and pipes if Rflag is not set */
 288  542          if (!Rflag && !S_ISREG(statp->st_mode))
 289  543                  return (0);
 290      -
 291      -        /* pass offset to relative name from FTW_CHDIR */
 292      -        execute(name, ftw->base);
      544 +        /* Pass offset to relative name from FTW_CHDIR */
      545 +        process_file(name, ftw->base);
 293  546          return (0);
 294  547  }
 295  548  
      549 +/*
      550 + * Opens file and call grep function.
      551 + */
 296  552  static void
 297      -execute(const char *file, int base)
      553 +process_file(const char *name, int base)
 298  554  {
 299      -        char    *lbuf, *p;
 300      -        long    count;
 301      -        long    offset = 0;
 302      -        char    *next_ptr = NULL;
 303      -        long    next_count = 0;
      555 +        int fd;
 304  556  
 305      -        tln = 0;
      557 +        if ((fd = open(name + base, O_RDONLY)) == -1) {
      558 +                errors = 1;
      559 +                if (!sflag) /* Silent mode */
      560 +                        (void) fprintf(stderr, gettext(
      561 +                            "%s: can't open \"%s\"\n"),
      562 +                            cmdname, name);
      563 +                return;
      564 +        }
      565 +        matched |= grep(fd, name);
      566 +        (void) close(fd);
 306  567  
 307      -        if (prntbuf == NULL) {
 308      -                fw_lPrntBufLen = GBUFSIZ + 1;
 309      -                if ((prntbuf = malloc(fw_lPrntBufLen)) == NULL) {
 310      -                        exit(2); /* out of memory - BAIL */
 311      -                }
 312      -                if ((linebuf = malloc(fw_lPrntBufLen)) == NULL) {
 313      -                        exit(2); /* out of memory - BAIL */
      568 +        if (ferror(stdout)) {
      569 +                (void) fprintf(stderr, gettext(
      570 +                    "%s: error writing to stdout\n"),
      571 +                    cmdname);
      572 +                (void) fflush(stdout);
      573 +                exit(2);
      574 +        }
      575 +
      576 +}
      577 +
      578 +/*
      579 + * Add a file of strings to the pattern list.
      580 + */
      581 +static void
      582 +addfile(const char *fn)
      583 +{
      584 +        FILE    *fp;
      585 +        char    *inbuf;
      586 +        char    *bufp;
      587 +        size_t  bufsiz, buflen, bufused;
      588 +
      589 +        /*
      590 +         * Open the pattern file
      591 +         */
      592 +        if ((fp = fopen(fn, "r")) == NULL) {
      593 +                (void) fprintf(stderr, gettext("%s: can't open \"%s\"\n"),
      594 +                    cmdname, fn);
      595 +                exit(2);
      596 +        }
      597 +        bufsiz = BUFSIZE;
      598 +        if ((inbuf = malloc(bufsiz)) == NULL) {
      599 +                (void) fprintf(stderr,
      600 +                    gettext("%s: out of memory\n"), cmdname);
      601 +                exit(2);
      602 +        }
      603 +        bufp = inbuf;
      604 +        bufused = 0;
      605 +        /*
      606 +         * Read in the file, reallocing as we need more memory
      607 +         */
      608 +        while (fgets(bufp, bufsiz - bufused, fp) != NULL) {
      609 +                buflen = strlen(bufp);
      610 +                bufused += buflen;
      611 +                if (bufused + 1 == bufsiz && bufp[buflen - 1] != '\n') {
      612 +                        /*
      613 +                         * if this line does not fit to the buffer,
      614 +                         * realloc larger buffer
      615 +                         */
      616 +                        bufsiz += BUFSIZE;
      617 +                        if ((inbuf = realloc(inbuf, bufsiz)) == NULL) {
      618 +                                (void) fprintf(stderr,
      619 +                                    gettext("%s: out of memory\n"),
      620 +                                    cmdname);
      621 +                                exit(2);
      622 +                        }
      623 +                        bufp = inbuf + bufused;
      624 +                        continue;
      625 +                }
      626 +                if (bufp[buflen - 1] == '\n') {
      627 +                        bufp[--buflen] = '\0';
 314  628                  }
      629 +                addpattern(inbuf);
      630 +
      631 +                bufp = inbuf;
      632 +                bufused = 0;
 315  633          }
      634 +        free(inbuf);
      635 +        free(prntbuf);
      636 +        free(conbuf);
      637 +        (void) fclose(fp);
      638 +}
 316  639  
 317      -        if (file == NULL) {
 318      -                temp = 0;
 319      -                file = STDIN_FILENAME;
 320      -        } else if ((temp = open(file + base, O_RDONLY)) == -1) {
 321      -                if (!sflag)
 322      -                        errmsg("grep: can't open %s\n", file);
 323      -                nsucc = 2;
 324      -                return;
      640 +/*
      641 + * Add a string to the pattern list.
      642 + */
      643 +static void
      644 +addpattern(char *s)
      645 +{
      646 +        PATTERN *pp;
      647 +        char    *wordbuf;
      648 +        char    *np;
      649 +
      650 +        for (; ; ) {
      651 +                np = strchr(s, '\n');
      652 +                if (np != NULL)
      653 +                        *np = '\0';
      654 +                if ((pp = malloc(sizeof (PATTERN))) == NULL) {
      655 +                        (void) fprintf(stderr, gettext(
      656 +                            "%s: out of memory\n"),
      657 +                            cmdname);
      658 +                        exit(2);
      659 +                }
      660 +                if (wflag) {
      661 +                        /*
      662 +                         * Solaris wflag support: Add '<' '>' to pattern to
      663 +                         * select it as a word. Doesn't make sense with -F
      664 +                         * but we're Libertarian.
      665 +                         */
      666 +                        size_t  slen, wordlen;
      667 +
      668 +                        slen = strlen(s);
      669 +                        wordlen = slen + 5; /* '\\' '<' s '\\' '>' '\0' */
      670 +                        if ((wordbuf = malloc(wordlen)) == NULL) {
      671 +                                (void) fprintf(stderr,
      672 +                                    gettext("%s: out of memory\n"),
      673 +                                    cmdname);
      674 +                                exit(2);
      675 +                        }
      676 +                        (void) strcpy(wordbuf, "\\<");
      677 +                        (void) strcpy(wordbuf + 2, s);
      678 +                        (void) strcpy(wordbuf + 2 + slen, "\\>");
      679 +                } else {
      680 +                        if ((wordbuf = strdup(s)) == NULL) {
      681 +                                (void) fprintf(stderr,
      682 +                                    gettext("%s: out of memory\n"),
      683 +                                    cmdname);
      684 +                                exit(2);
      685 +                        }
      686 +                }
      687 +                pp->pattern = wordbuf;
      688 +                pp->next = patterns;
      689 +                patterns = pp;
      690 +                if (np == NULL)
      691 +                        break;
      692 +                s = np + 1;
 325  693          }
      694 +}
 326  695  
 327      -        /* read in first block of bytes */
 328      -        if ((count = read(temp, prntbuf, GBUFSIZ)) <= 0) {
 329      -                (void) close(temp);
 330      -
 331      -                if (cflag && !qflag) {
 332      -                        if (Hflag || (nfile > 1 && !hflag))
 333      -                                (void) fprintf(stdout, "%s:", file);
 334      -                        if (!rflag)
 335      -                        (void) fprintf(stdout, "%lld\n", tln);
      696 +/*
      697 + * Fix patterns.
      698 + * Must do after all arguments read, in case later -i option.
      699 + */
      700 +static void
      701 +fixpatterns(void)
      702 +{
      703 +        PATTERN *pp;
      704 +        int     rv, fix_pattern, npatterns;
      705 +
      706 +        /*
      707 +         * As REG_ANCHOR flag is not supported in the current Solaris,
      708 +         * need to fix the specified pattern if -x is specified with
      709 +         * grep or egrep
      710 +         */
      711 +        fix_pattern = !Fflag && xflag;
      712 +
      713 +        for (npatterns = 0, pp = patterns; pp != NULL; pp = pp->next) {
      714 +                npatterns++;
      715 +                if (fix_pattern) {
      716 +                        char    *cp, *cq;
      717 +                        size_t  plen, nplen;
      718 +
      719 +                        plen = strlen(pp->pattern);
      720 +                        /* '^' pattern '$' */
      721 +                        nplen = 1 + plen + 1 + 1;
      722 +                        if ((cp = malloc(nplen)) == NULL) {
      723 +                                (void) fprintf(stderr,
      724 +                                    gettext("%s: out of memory\n"),
      725 +                                    cmdname);
      726 +                                exit(2);
      727 +                        }
      728 +                        cq = cp;
      729 +                        *cq++ = '^';
      730 +                        cq = strcpy(cq, pp->pattern) + plen;
      731 +                        *cq++ = '$';
      732 +                        *cq = '\0';
      733 +                        free(pp->pattern);
      734 +                        pp->pattern = cp;
 336  735                  }
 337      -                return;
      736 +
      737 +                if (Fflag) {
      738 +                        if (use_wchar) {
      739 +                                /*
      740 +                                 * Fflag && mblocale && iflag
      741 +                                 * Fflag && mblocale && !xflag
      742 +                                 */
      743 +                                size_t  n;
      744 +                                n = strlen(pp->pattern) + 1;
      745 +                                if ((pp->wpattern =
      746 +                                    malloc(sizeof (wchar_t) * n)) == NULL) {
      747 +                                        (void) fprintf(stderr,
      748 +                                            gettext("%s: out of memory\n"),
      749 +                                            cmdname);
      750 +                                        exit(2);
      751 +                                }
      752 +                                if (mbstowcs(pp->wpattern, pp->pattern, n) ==
      753 +                                    (size_t)-1) {
      754 +                                        (void) fprintf(stderr,
      755 +                                            gettext("%s: failed to convert "
      756 +                                            "\"%s\" to wide-characters\n"),
      757 +                                            cmdname, pp->pattern);
      758 +                                        exit(2);
      759 +                                }
      760 +                                if (iflag) {
      761 +                                        wchar_t *wp;
      762 +                                        for (wp = pp->wpattern; *wp != L'\0';
      763 +                                            wp++) {
      764 +                                                *wp = towlower((wint_t)*wp);
      765 +                                        }
      766 +                                }
      767 +                                free(pp->pattern);
      768 +                        } else {
      769 +                                /*
      770 +                                 * Fflag && mblocale && !iflag
      771 +                                 * Fflag && !mblocale && iflag
      772 +                                 * Fflag && !mblocale && !iflag
      773 +                                 */
      774 +                                if (iflag) {
      775 +                                        unsigned char   *cp;
      776 +                                        for (cp = (unsigned char *)pp->pattern;
      777 +                                            *cp != '\0'; cp++) {
      778 +                                                *cp = tolower(*cp);
      779 +                                        }
      780 +                                }
      781 +                        }
      782 +                        /*
      783 +                         * fgrep: No regular expressions.
      784 +                         */
      785 +                        continue;
      786 +                }
      787 +
      788 +                /*
      789 +                 * For non-fgrep, compile the regular expression,
      790 +                 * give an informative error message, and exit if
      791 +                 * it didn't compile.
      792 +                 */
      793 +                if ((rv = regcomp(&pp->re, pp->pattern, regflags)) != 0) {
      794 +                        (void) regerror(rv, &pp->re, errstr, sizeof (errstr));
      795 +                        (void) fprintf(stderr,
      796 +                            gettext("%s: RE error in %s: %s\n"),
      797 +                            cmdname, pp->pattern, errstr);
      798 +                        exit(2);
      799 +                }
      800 +                free(pp->pattern);
 338  801          }
 339  802  
 340      -        lnum = 0;
 341      -        ptr = prntbuf;
 342      -        for (;;) {
 343      -                /* look for next newline */
 344      -                if ((ptrend = memchr(ptr + offset, '\n', count)) == NULL) {
 345      -                        offset += count;
      803 +        /*
      804 +         * Decide if we are able to run the Boyer-Moore-Gosper algorithm.
      805 +         * Use the Boyer-Moore-Gosper algorithm if:
      806 +         * - fgrep                      (Fflag)
      807 +         * - singlebyte locale          (!mblocale)
      808 +         * - no ignoring case           (!iflag)
      809 +         * - no printing line numbers   (!nflag)
      810 +         * - no negating the output     (nvflag)
      811 +         * - only one pattern           (npatterns == 1)
      812 +         * - non zero length pattern    (strlen(patterns->pattern) != 0)
      813 +         * - no context required        (conflag == 0)
      814 +         *
      815 +         * It's guaranteed patterns->pattern is still alive
      816 +         * when Fflag && !mblocale.
      817 +         */
      818 +        use_bmg = Fflag && !mblocale && !iflag && !nflag && nvflag &&
      819 +            (npatterns == 1) && (strlen(patterns->pattern) != 0) &&
      820 +            conflag == 0;
      821 +}
      822 +
      823 +/*
      824 + * Search a newline from the beginning of the string
      825 + */
      826 +static char *
      827 +find_nl(const char *ptr, size_t len)
      828 +{
      829 +        while (len-- != 0) {
      830 +                if (*ptr++ == '\n') {
      831 +                        return ((char *)--ptr);
      832 +                }
      833 +        }
      834 +        return (NULL);
      835 +}
 346  836  
      837 +/*
      838 + * Search a newline from the end of the string
      839 + */
      840 +static char *
      841 +rfind_nl(const char *ptr, size_t len)
      842 +{
      843 +        const char      *uptr = ptr + len;
      844 +        while (len--) {
      845 +                if (*--uptr == '\n') {
      846 +                        return ((char *)uptr);
      847 +                }
      848 +        }
      849 +        return (NULL);
      850 +}
      851 +
      852 +/*
      853 + * Duplicate the specified string converting each character
      854 + * into a lower case.
      855 + */
      856 +static char *
      857 +istrdup(const char *s1)
      858 +{
      859 +        static size_t   ibuflen = 0;
      860 +        static char     *ibuf = NULL;
      861 +        size_t  slen;
      862 +        char    *p;
      863 +
      864 +        slen = strlen(s1);
      865 +        if (slen >= ibuflen) {
      866 +                /* ibuf does not fit to s1 */
      867 +                ibuflen = slen + 1;
      868 +                ibuf = realloc(ibuf, ibuflen);
      869 +                if (ibuf == NULL) {
      870 +                        (void) fprintf(stderr,
      871 +                            gettext("%s: out of memory\n"), cmdname);
      872 +                        exit(2);
      873 +                }
      874 +        }
      875 +        p = ibuf;
      876 +        do {
      877 +                *p++ = tolower(*s1);
      878 +        } while (*s1++ != '\0');
      879 +        return (ibuf);
      880 +}
      881 +
      882 +/*
      883 + * Do grep on a single file.
      884 + * Return true in any lines matched.
      885 + *
      886 + * We have two strategies:
      887 + * The fast one is used when we have a single pattern with
      888 + * a string known to occur in the pattern. We can then
      889 + * do a BMG match on the whole buffer.
      890 + * This is an order of magnitude faster.
      891 + * Otherwise we split the buffer into lines,
      892 + * and check for a match on each line.
      893 + */
      894 +static int
      895 +grep(int fd, const char *fn)
      896 +{
      897 +        PATTERN *pp;
      898 +        off_t   data_len;       /* length of the data chunk */
      899 +        off_t   line_len;       /* length of the current line */
      900 +        off_t   line_offset;    /* current line's offset from the beginning */
      901 +        off_t   blkoffset;      /* line_offset but context-compatible */
      902 +        long long       lineno, linenum;
      903 +        long long       matches = 0;    /* Number of matching lines */
      904 +        long long       conacnt = 0, conbcnt = 0;       /* context line count */
      905 +        int     newlinep;       /* 0 if the last line of file has no newline */
      906 +        char    *ptr, *ptrend, *prntptr, *prntptrend;
      907 +        char    *nextptr = NULL, *nextend = NULL;
      908 +        char    *conptr = NULL, *conptrend = NULL;
      909 +        char    *matchptr = NULL;
      910 +        int     conaprnt = 0, conbprnt = 0, lastmatch = 0;
      911 +        boolean_t       nearmatch; /* w/in N+1 of last match */
      912 +        boolean_t       havematch = B_FALSE; /* have a match in context */
      913 +        size_t  prntlen;
      914 +
      915 +        if (patterns == NULL)
      916 +                return (0);     /* no patterns to match -- just return */
      917 +
      918 +        pp = patterns;
      919 +
      920 +        if (use_bmg) {
      921 +                bmgcomp(pp->pattern, strlen(pp->pattern));
      922 +        }
      923 +
      924 +        if (use_wchar && outline == NULL) {
      925 +                outbuflen = BUFSIZE + 1;
      926 +                outline = malloc(sizeof (wchar_t) * outbuflen);
      927 +                if (outline == NULL) {
      928 +                        (void) fprintf(stderr, gettext("%s: out of memory\n"),
      929 +                            cmdname);
      930 +                        exit(2);
      931 +                }
      932 +        }
      933 +
      934 +        if (prntbuf == NULL) {
      935 +                prntbuflen = BUFSIZE;
      936 +                if ((prntbuf = malloc(prntbuflen + 1)) == NULL) {
      937 +                        (void) fprintf(stderr, gettext("%s: out of memory\n"),
      938 +                            cmdname);
      939 +                        exit(2);
      940 +                }
      941 +        }
      942 +
      943 +        if (conflag != 0 && (conbuf == NULL)) {
      944 +                conbuflen = BUFSIZE;
      945 +                if ((conbuf = malloc(BUFSIZE+1)) == NULL) {
      946 +                        (void) fprintf(stderr, gettext("%s: out of memory\n"),
      947 +                            cmdname);
      948 +                        exit(2);
      949 +                }
      950 +        }
      951 +
      952 +        nearmatch = (conmatches != 0);
      953 +        blkoffset = line_offset = 0;
      954 +        lineno = 0;
      955 +        linenum = 1;
      956 +        newlinep = 1;
      957 +        data_len = 0;
      958 +        for (; ; ) {
      959 +                long    count;
      960 +                off_t   offset = 0;
      961 +                char    separate;
      962 +                boolean_t       last_ctx = B_FALSE, eof = B_FALSE;
      963 +
      964 +                if (data_len == 0) {
 347  965                          /*
 348      -                         * shift unused data to the beginning of the buffer
      966 +                         * If no data in the buffer, reset ptr
 349  967                           */
      968 +                        ptr = prntbuf;
      969 +                        if (conflag != 0 && conptr == NULL) {
      970 +                                conptr = conbuf;
      971 +                                conptrend = conptr - 1;
      972 +                        }
      973 +                }
      974 +                if (ptr == prntbuf) {
      975 +                        /*
      976 +                         * The current data chunk starts from prntbuf.
      977 +                         * This means either the buffer has no data
      978 +                         * or the buffer has no newline.
      979 +                         * So, read more data from input.
      980 +                         */
      981 +                        count = read(fd, ptr + data_len, prntbuflen - data_len);
      982 +                        if (count < 0) {
      983 +                                /* read error */
      984 +                                if (cflag) {
      985 +                                        if (outfn && !rflag) {
      986 +                                                (void) fprintf(stdout,
      987 +                                                    "%s:", fn);
      988 +                                        }
      989 +                                        if (!qflag && !rflag) {
      990 +                                                (void) fprintf(stdout, "%lld\n",
      991 +                                                    matches);
      992 +                                        }
      993 +                                }
      994 +                                return (0);
      995 +                        } else if (count == 0) {
      996 +                                /* no new data */
      997 +                                eof = B_TRUE;
      998 +
      999 +                                if (data_len == 0) {
     1000 +                                        /* end of file already reached */
     1001 +                                        if (conflag != 0) {
     1002 +                                                if (conptrend >= conptr)
     1003 +                                                        *conptrend = '\n';
     1004 +                                                last_ctx = B_TRUE;
     1005 +                                                goto L_next_line;
     1006 +                                        } else {
     1007 +                                                goto out;
     1008 +                                        }
     1009 +                                }
     1010 +                                /* last line of file has no newline */
     1011 +                                ptrend = ptr + data_len;
     1012 +                                newlinep = 0;
     1013 +                                goto L_start_process;
     1014 +                        }
     1015 +                        offset = data_len;
     1016 +                        data_len += count;
     1017 +                }
     1018 +
     1019 +                /*
     1020 +                 * Look for newline in the chunk
     1021 +                 * between ptr + offset and ptr + data_len - offset.
     1022 +                 */
     1023 +                ptrend = find_nl(ptr + offset, data_len - offset);
     1024 +                if (ptrend == NULL) {
     1025 +                        /* no newline found in this chunk */
 350 1026                          if (ptr > prntbuf) {
 351      -                                (void) memmove(prntbuf, ptr, offset);
 352      -                                ptr = prntbuf;
     1027 +                                /*
     1028 +                                 * Move remaining data to the beginning
     1029 +                                 * of the buffer.
     1030 +                                 * Remaining data lie from ptr for
     1031 +                                 * data_len bytes.
     1032 +                                 */
     1033 +                                (void) memmove(prntbuf, ptr, data_len);
     1034 +                        }
     1035 +                        if (data_len == prntbuflen) {
     1036 +                                /*
     1037 +                                 * Not enough room in the buffer
     1038 +                                 */
     1039 +                                if (prntbuflen > SIZE_MAX - BUFSIZE) {
     1040 +                                        (void) fprintf(stderr,
     1041 +                                            gettext("%s: buflen would"
     1042 +                                            " overflow\n"),
     1043 +                                            cmdname);
     1044 +                                        exit(2);
     1045 +                                }
     1046 +
     1047 +                                prntbuflen += BUFSIZE;
     1048 +                                prntbuf = realloc(prntbuf, prntbuflen + 1);
     1049 +                                if (prntbuf == NULL) {
     1050 +                                        (void) fprintf(stderr,
     1051 +                                            gettext("%s: out of memory\n"),
     1052 +                                            cmdname);
     1053 +                                        exit(2);
     1054 +                                }
 353 1055                          }
     1056 +                        ptr = prntbuf;
     1057 +                        /* read the next input */
     1058 +                        continue;
     1059 +                }
     1060 +L_start_process:
     1061 +
     1062 +                /*
     1063 +                 * Beginning of the chunk:      ptr
     1064 +                 * End of the chunk:            ptr + data_len
     1065 +                 * Beginning of the line:       ptr
     1066 +                 * End of the line:             ptrend
     1067 +                 *
     1068 +                 * conptr:      Beginning of the context.
     1069 +                 * conptrend: If context is empty, conptr - 1 (invalid memory).
     1070 +                 *      Otherwise, Last newline in the context.
     1071 +                 */
 354 1072  
     1073 +                if (use_bmg) {
 355 1074                          /*
 356      -                         * re-allocate a larger buffer if this one is full
     1075 +                         * Use Boyer-Moore-Gosper algorithm to find out if
     1076 +                         * this chunk (not this line) contains the specified
     1077 +                         * pattern.  If not, restart from the last line
     1078 +                         * of this chunk.
 357 1079                           */
 358      -                        if (offset + GBUFSIZ > fw_lPrntBufLen) {
     1080 +                        char    *bline;
     1081 +                        bline = bmgexec(ptr, ptr + data_len);
     1082 +                        if (bline == NULL) {
 359 1083                                  /*
 360      -                                 * allocate a new buffer and preserve the
 361      -                                 * contents...
     1084 +                                 * No pattern found in this chunk.
     1085 +                                 * Need to find the last line
     1086 +                                 * in this chunk.
 362 1087                                   */
 363      -                                fw_lPrntBufLen += GBUFSIZ;
 364      -                                if ((prntbuf = realloc(prntbuf,
 365      -                                    fw_lPrntBufLen)) == NULL)
 366      -                                        exit(2);
     1088 +                                ptrend = rfind_nl(ptr, data_len);
 367 1089  
 368 1090                                  /*
 369      -                                 * set up a bigger linebuffer (this is only used
 370      -                                 * for case insensitive operations). Contents do
 371      -                                 * not have to be preserved.
     1091 +                                 * When this chunk does not contain newline,
     1092 +                                 * ptrend becomes NULL, which should happen
     1093 +                                 * when the last line of file does not end
     1094 +                                 * with a newline.  At such a point,
     1095 +                                 * newlinep should have been set to 0.
     1096 +                                 * Therefore, just after jumping to
     1097 +                                 * L_skip_line, the main for-loop quits,
     1098 +                                 * and the line_len value won't be
     1099 +                                 * used.
 372 1100                                   */
 373      -                                free(linebuf);
 374      -                                if ((linebuf = malloc(fw_lPrntBufLen)) == NULL)
     1101 +                                line_len = ptrend - ptr;
     1102 +                                goto L_skip_line;
     1103 +                        }
     1104 +                        if (bline > ptrend) {
     1105 +                                /*
     1106 +                                 * Pattern found not in the first line
     1107 +                                 * of this chunk.
     1108 +                                 * Discard the first line.
     1109 +                                 */
     1110 +                                line_len = ptrend - ptr;
     1111 +                                goto L_skip_line;
     1112 +                        }
     1113 +                        /*
     1114 +                         * Pattern found in the first line of this chunk.
     1115 +                         * Using this result.
     1116 +                         */
     1117 +                        *ptrend = '\0';
     1118 +                        line_len = ptrend - ptr;
     1119 +
     1120 +                        /*
     1121 +                         * before jumping to L_next_line,
     1122 +                         * need to handle xflag if specified
     1123 +                         */
     1124 +                        if (xflag && (line_len != bmglen ||
     1125 +                            strcmp(bmgpat, ptr) != 0)) {
     1126 +                                /* didn't match */
     1127 +                                pp = NULL;
     1128 +                        } else {
     1129 +                                pp = patterns; /* to make it happen */
     1130 +                        }
     1131 +                        goto L_next_line;
     1132 +                }
     1133 +                lineno++;
     1134 +                /*
     1135 +                 * Line starts from ptr and ends at ptrend.
     1136 +                 * line_len will be the length of the line.
     1137 +                 */
     1138 +                *ptrend = '\0';
     1139 +                line_len = ptrend - ptr;
     1140 +
     1141 +                /*
     1142 +                 * From now, the process will be performed based
     1143 +                 * on the line from ptr to ptrend.
     1144 +                 */
     1145 +                if (use_wchar) {
     1146 +                        size_t  len;
     1147 +
     1148 +                        if (line_len >= outbuflen) {
     1149 +                                outbuflen = line_len + 1;
     1150 +                                outline = realloc(outline,
     1151 +                                    sizeof (wchar_t) * outbuflen);
     1152 +                                if (outline == NULL) {
     1153 +                                        (void) fprintf(stderr,
     1154 +                                            gettext("%s: out of memory\n"),
     1155 +                                            cmdname);
 375 1156                                          exit(2);
     1157 +                                }
     1158 +                        }
     1159 +
     1160 +                        len = mbstowcs(outline, ptr, line_len);
     1161 +                        if (len == (size_t)-1) {
     1162 +                                (void) fprintf(stderr, gettext(
     1163 +        "%s: input file \"%s\": line %lld: invalid multibyte character\n"),
     1164 +                                    cmdname, fn, lineno);
     1165 +                                /* never match a line with invalid sequence */
     1166 +                                goto L_skip_line;
     1167 +                        }
     1168 +                        outline[len] = L'\0';
     1169 +
     1170 +                        if (iflag) {
     1171 +                                wchar_t *cp;
     1172 +                                for (cp = outline; *cp != '\0'; cp++) {
     1173 +                                        *cp = towlower((wint_t)*cp);
     1174 +                                }
     1175 +                        }
     1176 +
     1177 +                        if (xflag) {
     1178 +                                for (pp = patterns; pp; pp = pp->next) {
     1179 +                                        if (outline[0] == pp->wpattern[0] &&
     1180 +                                            wcscmp(outline,
     1181 +                                            pp->wpattern) == 0) {
     1182 +                                                /* matched */
     1183 +                                                break;
     1184 +                                        }
     1185 +                                }
     1186 +                        } else {
     1187 +                                for (pp = patterns; pp; pp = pp->next) {
     1188 +                                        if (wcswcs(outline, pp->wpattern)
     1189 +                                            != NULL) {
     1190 +                                                /* matched */
     1191 +                                                break;
     1192 +                                        }
     1193 +                                }
     1194 +                        }
     1195 +                } else if (Fflag) {
     1196 +                        /* fgrep in byte-oriented handling */
     1197 +                        char    *fptr;
     1198 +                        if (iflag) {
     1199 +                                fptr = istrdup(ptr);
     1200 +                        } else {
     1201 +                                fptr = ptr;
     1202 +                        }
     1203 +                        if (xflag) {
     1204 +                                /* fgrep -x */
     1205 +                                for (pp = patterns; pp; pp = pp->next) {
     1206 +                                        if (fptr[0] == pp->pattern[0] &&
     1207 +                                            strcmp(fptr, pp->pattern) == 0) {
     1208 +                                                /* matched */
     1209 +                                                break;
     1210 +                                        }
     1211 +                                }
     1212 +                        } else {
     1213 +                                for (pp = patterns; pp; pp = pp->next) {
     1214 +                                        if (strstr(fptr, pp->pattern) != NULL) {
     1215 +                                                /* matched */
     1216 +                                                break;
     1217 +                                        }
     1218 +                                }
     1219 +                        }
     1220 +                } else {
     1221 +                        /* grep or egrep */
     1222 +                        for (pp = patterns; pp; pp = pp->next) {
     1223 +                                int     rv;
     1224 +
     1225 +                                rv = regexec(&pp->re, ptr, 0, NULL, 0);
     1226 +                                if (rv == REG_OK) {
     1227 +                                        /* matched */
     1228 +                                        break;
     1229 +                                }
     1230 +
     1231 +                                switch (rv) {
     1232 +                                case REG_NOMATCH:
     1233 +                                        break;
     1234 +                                case REG_ECHAR:
     1235 +                                        (void) fprintf(stderr, gettext(
     1236 +            "%s: input file \"%s\": line %lld: invalid multibyte character\n"),
     1237 +                                            cmdname, fn, lineno);
     1238 +                                        break;
     1239 +                                default:
     1240 +                                        (void) regerror(rv, &pp->re, errstr,
     1241 +                                            sizeof (errstr));
     1242 +                                        (void) fprintf(stderr, gettext(
     1243 +            "%s: input file \"%s\": line %lld: %s\n"),
     1244 +                                            cmdname, fn, lineno, errstr);
     1245 +                                        exit(2);
     1246 +                                }
     1247 +                        }
     1248 +                }
     1249 +
     1250 +                /*
     1251 +                 * Context is set up as follows:
     1252 +                 * For a 'Before' context, we maintain a set of pointers
     1253 +                 * containing 'N' lines of context. If the current number of
     1254 +                 * lines contained is greater than N, and N isn't a match, the
     1255 +                 * start pointer is moved forward to the next newline.
     1256 +                 *
     1257 +                 * If we ever find a match, we print out immediately.
     1258 +                 * 'nearmatch' tells us if we're within N+1 lines of the last
     1259 +                 * match ; if we are, and we find another match, we don't
     1260 +                 * separate the matches. 'nearmatch' becomes false when
     1261 +                 * a line gets rotated out of the context.
     1262 +                 *
     1263 +                 * For an 'After' context, we simply wait until we've found a
     1264 +                 * match, then create a context N+1 lines big. If we don't find
     1265 +                 * a match within the context, we print out the current context.
     1266 +                 * Otherwise, we save a reference to the new matching line,
     1267 +                 * print out the other context, and reset our context pointers
     1268 +                 * to the new matching line.
     1269 +                 *
     1270 +                 * 'nearmatch' becomes false when we find a non-matching line
     1271 +                 * that isn't a part of any context.
     1272 +                 *
     1273 +                 * A full-context is implemented as a combination of the
     1274 +                 * 'Before' and 'After' context logic. Before we find a match,
     1275 +                 * we follow the Before logic. When we find a match, we
     1276 +                 * follow the After logic. 'nearmatch' is handled by the Before
     1277 +                 * logic.
     1278 +                 */
     1279 +
     1280 +                if (conflag == 0)
     1281 +                        goto L_next_line;
     1282 +
     1283 +                /* Do we have room to add this line to the context buffer? */
     1284 +                if ((line_len + 1) > (conbuflen -
     1285 +                    (conptrend >= conptr) ? conptrend - conbuf : 0)) {
     1286 +                        char *oldconbuf = conbuf;
     1287 +                        char *oldconptr = conptr;
     1288 +                        long tmp = matchptr - conptr;
     1289 +
     1290 +                        if (conbuflen > SIZE_MAX - BUFSIZE) {
     1291 +                                (void) fprintf(stderr,
     1292 +                                    gettext("%s: buflen would overflow\n"),
     1293 +                                    cmdname);
     1294 +                                exit(2);
     1295 +                        }
     1296 +
     1297 +                        conbuflen += BUFSIZE;
     1298 +                        conbuf = realloc(conbuf, conbuflen + 1);
     1299 +                        if (conbuf == NULL) {
     1300 +                                (void) fprintf(stderr,
     1301 +                                    gettext("%s: out of memory\n"),
     1302 +                                    cmdname);
     1303 +                                exit(2);
     1304 +                        }
     1305 +
     1306 +                        conptr = conbuf + (conptr - oldconbuf);
     1307 +                        conptrend = conptr + (conptrend - oldconptr);
     1308 +                        if (matchptr)
     1309 +                                matchptr = conptr + tmp;
     1310 +                }
     1311 +                (void) memcpy(conptrend + 1, ptr, line_len);
     1312 +                conptrend += line_len + 1;
     1313 +                *conptrend = '\n';
     1314 +
     1315 +                if (nvflag == (pp != NULL)) {
     1316 +                        /* matched */
     1317 +                        if (havematch) {
     1318 +                                if ((conflag & AFTER) != 0) {
     1319 +                                        conaprnt = 1;
     1320 +                                        nextend = conptrend;
     1321 +                                        conptrend = conptr + lastmatch;
     1322 +                                        nextptr = conptrend + 1;
     1323 +                                        *nextend = '\n';
     1324 +                                }
     1325 +                        } else {
     1326 +                                if (conflag == AFTER) {
     1327 +                                        conptr = conptrend - (line_len);
     1328 +                                        linenum = lineno;
     1329 +                                }
     1330 +                                blkoffset = line_offset -
     1331 +                                    (conptrend - conptr - line_len);
     1332 +                        }
     1333 +
     1334 +                        if (conflag == BEFORE)
     1335 +                                conbprnt = 1;
     1336 +
     1337 +                        lastmatch = conptrend - conptr;
     1338 +                        havematch = B_TRUE;
     1339 +                        goto L_next_line;
     1340 +                }
 376 1341  
 377      -                                ptr = prntbuf;
     1342 +                if (!havematch) {
     1343 +                        if ((conflag & BEFORE) != 0) {
     1344 +                                if (conbcnt >= conblen) {
     1345 +                                        char *tmp = conptr;
     1346 +                                        conptr = find_nl(conptr,
     1347 +                                            conptrend - conptr) + 1;
     1348 +                                        if (bflag)
     1349 +                                                blkoffset += conptr - tmp;
     1350 +                                        linenum++;
     1351 +                                        nearmatch = B_TRUE;
     1352 +                                } else {
     1353 +                                        conbcnt++;
     1354 +                                }
 378 1355                          }
     1356 +                        if (conflag == AFTER)
     1357 +                                nearmatch = B_TRUE;
     1358 +                } else  {
     1359 +                        if (++conacnt >= conalen && !conaprnt && conalen)
     1360 +                                conaprnt = 1;
     1361 +                        else
     1362 +                                lastmatch = conptrend - conptr;
     1363 +                }
     1364 +
     1365 +L_next_line:
     1366 +                /*
     1367 +                 * Here, if pp points to non-NULL, something has been matched
     1368 +                 * to the pattern.
     1369 +                 */
     1370 +                if (!last_ctx && nvflag == (pp != NULL)) {
     1371 +                        matches++;
     1372 +                        if (!nextend)
     1373 +                                matchptr = (conflag != 0) ? conptrend : ptrend;
     1374 +                }
 379 1375  
 380      -                        p = prntbuf + offset;
 381      -                        if ((count = read(temp, p, GBUFSIZ)) > 0)
 382      -                                continue;
     1376 +                /*
     1377 +                 * Set up some print context so that we can treat
     1378 +                 * single-line matches as a zero-N context.
     1379 +                 * Apply CLI flags to each line of the context.
     1380 +                 *
     1381 +                 * For context, we only print if we both have a match and are
     1382 +                 * either at the end of the data stream, or we've previously
     1383 +                 * declared that we want to print for a particular context.
     1384 +                 */
     1385 +                if (havematch && (eof || conaprnt || conbprnt)) {
 383 1386  
 384      -                        if (offset == 0)
 385      -                                /* end of file already reached */
 386      -                                break;
     1387 +                        /*
     1388 +                         * We'd normally do this earlier, but we had to
     1389 +                         * escape early because we reached the end of the data.
     1390 +                         */
     1391 +                        if (eof && nextptr)
     1392 +                                conptrend = nextend;
 387 1393  
 388      -                        /* last line of file has no newline */
 389      -                        ptrend = ptr + offset;
 390      -                        nlflag = 0;
     1394 +                        prntlen = conptrend - conptr + 1;
     1395 +                        prntptr = conptr;
     1396 +                        if (conmatches++ && nearmatch && !cflag)
     1397 +                                (void) fwrite("--\n", 1, 3, stdout);
     1398 +                } else if (conflag == 0 && nvflag == (pp != NULL)) {
     1399 +                        *ptrend = '\n';
     1400 +                        prntlen = line_len + 1;
     1401 +                        prntptr = ptr;
     1402 +                        linenum = lineno;
     1403 +                        blkoffset = line_offset;
     1404 +                } else if (eof) {
     1405 +                        /* No match and no more data */
     1406 +                        goto out;
 391 1407                  } else {
 392      -                        next_ptr = ptrend + 1;
 393      -                        next_count = offset + count - (next_ptr - ptr);
 394      -                        nlflag = 1;
     1408 +                        /* No match, or we're not done building context */
     1409 +                        goto L_skip_line;
 395 1410                  }
 396      -                lnum++;
 397      -                *ptrend = '\0';
 398 1411  
 399      -                if (iflag) {
     1412 +                prntptrend = prntptr - 1;
     1413 +                while ((prntptrend = find_nl(prntptrend + 1,
     1414 +                    prntlen)) != NULL) {
     1415 +
 400 1416                          /*
 401      -                         * Make a lower case copy of the record
     1417 +                         * GNU grep uses '-' for context lines and ':' for
     1418 +                         * matching lines, so replicate that here.
 402 1419                           */
 403      -                        p = ptr;
 404      -                        for (lbuf = linebuf; p < ptrend; )
 405      -                                *lbuf++ = (char)tolower((int)
 406      -                                    (unsigned char)*p++);
 407      -                        *lbuf = '\0';
 408      -                        lbuf = linebuf;
 409      -                } else
     1420 +                        if (prntptrend == matchptr) {
     1421 +                                if (eof && nextptr) {
     1422 +                                        matchptr = nextend;
     1423 +                                        nextptr = NULL;
     1424 +                                } else {
     1425 +                                        matchptr = NULL;
     1426 +                                }
     1427 +                                separate = ':';
     1428 +                        } else {
     1429 +                                separate = '-';
     1430 +                        }
     1431 +
 410 1432                          /*
 411      -                         * Use record as is
     1433 +                         * Handle q, l, and c flags.
 412 1434                           */
 413      -                        lbuf = ptr;
     1435 +                        if (qflag) {
     1436 +                                /* no need to continue */
     1437 +                                /*
     1438 +                                 * End of this line is ptrend.
     1439 +                                 * We have read up to ptr + data_len.
     1440 +                                 */
     1441 +                                off_t   pos;
     1442 +                                pos = ptr + data_len - (ptrend + 1);
     1443 +                                (void) lseek(fd, -pos, SEEK_CUR);
     1444 +                                exit(0);
     1445 +                        }
     1446 +                        if (lflag) {
     1447 +                                (void) printf("%s\n", fn);
     1448 +                                goto out;
     1449 +                        }
     1450 +                        if (!cflag) {
     1451 +                                if (Hflag || outfn) {
     1452 +                                        (void) printf("%s%c", fn, separate);
     1453 +                                }
     1454 +                                if (bflag) {
     1455 +                                        (void) printf("%lld%c", (offset_t)
     1456 +                                            (blkoffset / BSIZE), separate);
     1457 +                                }
     1458 +                                if (nflag) {
     1459 +                                        (void) printf("%lld%c", linenum,
     1460 +                                            separate);
     1461 +                                }
     1462 +                                (void) fwrite(prntptr, 1,
     1463 +                                    prntptrend - prntptr + 1, stdout);
     1464 +                        }
     1465 +                        if (ferror(stdout)) {
     1466 +                                return (0);
     1467 +                        }
     1468 +                        linenum++;
     1469 +                        prntlen -= prntptrend - prntptr + 1;
     1470 +                        blkoffset += prntptrend - prntptr + 1;
     1471 +                        prntptr = prntptrend + 1;
     1472 +                }
 414 1473  
 415      -                /* lflag only once */
 416      -                if ((step(lbuf, expbuf) ^ vflag) && succeed(file) == 1)
 417      -                        break;
     1474 +                if (eof)
     1475 +                        goto out;
 418 1476  
 419      -                if (!nlflag)
     1477 +                /*
     1478 +                 * Update context buffer and variables post-print
     1479 +                 */
     1480 +                if (conflag != 0) {
     1481 +                        conptr = conbuf;
     1482 +                        conaprnt = conbprnt = 0;
     1483 +                        nearmatch = B_FALSE;
     1484 +                        conacnt = conbcnt = 0;
     1485 +
     1486 +                        if (nextptr) {
     1487 +                                (void) memmove(conbuf, nextptr,
     1488 +                                    nextend - nextptr + 1);
     1489 +                                blkoffset += nextptr - conptrend - 1;
     1490 +                                conptrend = conptr + (nextend - nextptr);
     1491 +                                matchptr = conptrend;
     1492 +                                linenum = lineno;
     1493 +                                lastmatch = conptrend - conptr;
     1494 +                                havematch = B_TRUE;
     1495 +                        } else {
     1496 +                                conptrend = conptr - 1;
     1497 +                                conacnt = 0;
     1498 +                                lastmatch = 0;
     1499 +                                havematch = B_FALSE;
     1500 +                        }
     1501 +                        nextptr = nextend = NULL;
     1502 +                }
     1503 +
     1504 +L_skip_line:
     1505 +                if (!newlinep)
 420 1506                          break;
 421 1507  
 422      -                ptr = next_ptr;
 423      -                count = next_count;
 424      -                offset = 0;
     1508 +                data_len -= line_len + 1;
     1509 +                line_offset += line_len + 1;
     1510 +                ptr = ptrend + 1;
 425 1511          }
 426      -        (void) close(temp);
 427 1512  
 428      -        if (cflag && !qflag) {
 429      -                if (Hflag || (!hflag && ((nfile > 1) ||
 430      -                    (rflag && outfn))))
 431      -                        (void) fprintf(stdout, "%s:", file);
 432      -                (void) fprintf(stdout, "%lld\n", tln);
     1513 +out:
     1514 +        if (cflag) {
     1515 +                if (Hflag || outfn) {
     1516 +                        (void) printf("%s:", fn);
     1517 +                }
     1518 +                if (!qflag) {
     1519 +                        (void) printf("%lld\n", matches);
     1520 +                }
 433 1521          }
     1522 +        return (matches != 0);
 434 1523  }
 435 1524  
 436      -static int
 437      -succeed(const char *f)
     1525 +/*
     1526 + * usage message for grep
     1527 + */
     1528 +static void
     1529 +usage(void)
 438 1530  {
 439      -        int nchars;
 440      -        nsucc = (nsucc == 2) ? 2 : 1;
 441      -
 442      -        if (qflag) {
 443      -                /* no need to continue */
 444      -                return (1);
     1531 +        if (egrep || fgrep) {
     1532 +                (void) fprintf(stderr, gettext("Usage:\t%s"), cmdname);
     1533 +                (void) fprintf(stderr,
     1534 +                    gettext(" [-c|-l|-q] [-r|-R] "
     1535 +                    "[-A num] [-B num] [-C num|-num] "
     1536 +                    "[-bhHinsvx] pattern_list [file ...]\n"));
     1537 +
     1538 +                (void) fprintf(stderr, "\t%s", cmdname);
     1539 +                (void) fprintf(stderr,
     1540 +                    gettext(" [-c|-l|-q] [-r|-R] "
     1541 +                    "[-A num] [-B num] [-C num|-num] "
     1542 +                    "[-bhHinsvx] [-e pattern_list]... "
     1543 +                    "[-f pattern_file]... [file...]\n"));
     1544 +        } else {
     1545 +                (void) fprintf(stderr, gettext("Usage:\t%s"), cmdname);
     1546 +                (void) fprintf(stderr,
     1547 +                    gettext(" [-c|-l|-q] [-r|-R] "
     1548 +                    "[-A num] [-B num] [-C num|-num] "
     1549 +                    "[-bhHinsvx] pattern_list [file ...]\n"));
     1550 +
     1551 +                (void) fprintf(stderr, "\t%s", cmdname);
     1552 +                (void) fprintf(stderr,
     1553 +                    gettext(" [-c|-l|-q] [-r|-R] "
     1554 +                    "[-A num] [-B num] [-C num|-num] "
     1555 +                    "[-bhHinsvx] [-e pattern_list]... "
     1556 +                    "[-f pattern_file]... [file...]\n"));
     1557 +
     1558 +                (void) fprintf(stderr, "\t%s", cmdname);
     1559 +                (void) fprintf(stderr,
     1560 +                    gettext(" -E [-c|-l|-q] [-r|-R] "
     1561 +                    "[-A num] [-B num] [-C num|-num] "
     1562 +                    "[-bhHinsvx] pattern_list [file ...]\n"));
     1563 +
     1564 +                (void) fprintf(stderr, "\t%s", cmdname);
     1565 +                (void) fprintf(stderr,
     1566 +                    gettext(" -E [-c|-l|-q] [-r|-R] "
     1567 +                    "[-A num] [-B num] [-C num|-num] "
     1568 +                    "[-bhHinsvx] [-e pattern_list]... "
     1569 +                    "[-f pattern_file]... [file...]\n"));
     1570 +
     1571 +                (void) fprintf(stderr, "\t%s", cmdname);
     1572 +                (void) fprintf(stderr,
     1573 +                    gettext(" -F [-c|-l|-q] [-r|-R] "
     1574 +                    "[-A num] [-B num] [-C num|-num] "
     1575 +                    "[-bhHinsvx] pattern_list [file ...]\n"));
     1576 +
     1577 +                (void) fprintf(stderr, "\t%s", cmdname);
     1578 +                (void) fprintf(stderr,
     1579 +                    gettext(" -F [-c|-l|-q] "
     1580 +                    "[-A num] [-B num] [-C num|-num] "
     1581 +                    "[-bhHinsvx] [-e pattern_list]... "
     1582 +                    "[-f pattern_file]... [file...]\n"));
 445 1583          }
     1584 +        exit(2);
     1585 +        /* NOTREACHED */
     1586 +}
 446 1587  
 447      -        if (cflag) {
 448      -                tln++;
 449      -                return (0);
 450      -        }
     1588 +/*
     1589 + * Compile literal pattern into BMG tables
     1590 + */
     1591 +static void
     1592 +bmgcomp(char *pat, int len)
     1593 +{
     1594 +        int     i;
     1595 +        int     tlen;
     1596 +        unsigned char   *uc = (unsigned char *)pat;
 451 1597  
 452      -        if (lflag) {
 453      -                (void) fprintf(stdout, "%s\n", f);
 454      -                return (1);
 455      -        }
     1598 +        bmglen = len;
     1599 +        bmgpat = pat;
 456 1600  
 457      -        if (Hflag || (!hflag && (nfile > 1 || (rflag && outfn)))) {
 458      -                /* print filename */
 459      -                (void) fprintf(stdout, "%s:", f);
     1601 +        for (i = 0; i < M_CSETSIZE; i++) {
     1602 +                bmgtab[i] = len;
 460 1603          }
 461 1604  
 462      -        if (bflag)
 463      -                /* print block number */
 464      -                (void) fprintf(stdout, "%lld:", (offset_t)
 465      -                    ((lseek(temp, (off_t)0, SEEK_CUR) - 1) / BLKSIZE));
 466      -
 467      -        if (nflag)
 468      -                /* print line number */
 469      -                (void) fprintf(stdout, "%lld:", lnum);
 470      -
 471      -        if (nlflag) {
 472      -                /* newline at end of line */
 473      -                *ptrend = '\n';
 474      -                nchars = ptrend - ptr + 1;
 475      -        } else {
 476      -                /* don't write sentinel \0 */
 477      -                nchars = ptrend - ptr;
     1605 +        len--;
     1606 +        for (tlen = len, i = 0; i <= len; i++, tlen--) {
     1607 +                bmgtab[*uc++] = tlen;
 478 1608          }
 479      -
 480      -        (void) fwrite(ptr, 1, nchars, stdout);
 481      -        return (0);
 482 1609  }
 483 1610  
 484      -static void
 485      -regerr(int err)
     1611 +/*
     1612 + * BMG search.
     1613 + */
     1614 +static char *
     1615 +bmgexec(char *str, char *end)
 486 1616  {
 487      -        errmsg("grep: RE error %d: ", err);
 488      -        switch (err) {
 489      -                case 11:
 490      -                        err = 0;
 491      -                        break;
 492      -                case 16:
 493      -                        err = 1;
 494      -                        break;
 495      -                case 25:
 496      -                        err = 2;
 497      -                        break;
 498      -                case 41:
 499      -                        err = 3;
 500      -                        break;
 501      -                case 42:
 502      -                        err = 4;
 503      -                        break;
 504      -                case 43:
 505      -                        err = 5;
 506      -                        break;
 507      -                case 44:
 508      -                        err = 6;
 509      -                        break;
 510      -                case 45:
 511      -                        err = 7;
 512      -                        break;
 513      -                case 46:
 514      -                        err = 8;
 515      -                        break;
 516      -                case 49:
 517      -                        err = 9;
 518      -                        break;
 519      -                case 50:
 520      -                        err = 10;
 521      -                        break;
 522      -                case 67:
 523      -                        err = 11;
 524      -                        break;
 525      -                default:
 526      -                        err = 12;
 527      -                        break;
 528      -        }
     1617 +        int     t;
     1618 +        char    *k, *s, *p;
 529 1619  
 530      -        errmsg("%s\n", gettext(errstr[err]));
 531      -        exit(2);
     1620 +        k = str + bmglen - 1;
     1621 +        if (bmglen == 1) {
     1622 +                return (memchr(str, bmgpat[0], end - str));
     1623 +        }
     1624 +        for (; ; ) {
     1625 +                /* inner loop, should be most optimized */
     1626 +                while (k < end && (t = bmgtab[(unsigned char)*k]) != 0) {
     1627 +                        k += t;
     1628 +                }
     1629 +                if (k >= end) {
     1630 +                        return (NULL);
     1631 +                }
     1632 +                for (s = k, p = bmgpat + bmglen - 1; *--s == *--p; ) {
     1633 +                        if (p == bmgpat) {
     1634 +                                return (s);
     1635 +                        }
     1636 +                }
     1637 +                k++;
     1638 +        }
     1639 +        /* NOTREACHED */
 532 1640  }
    
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX