xref: /illumos-gate/usr/src/cmd/grep/grep.c (revision 6dde88b51419b99fe0aab8e56184c693945826b8)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 * grep - pattern matching program - combined grep, egrep, and fgrep.
 *	Based on MKS grep command, with XCU & Solaris mods.
 */

/*
 * Copyright 1985, 1992 by Mortice Kern Systems Inc.  All rights reserved.
 *
 */

/*
 * Copyright 2020 Peter Tribble.
 * Copyright 2018 RackTop Systems.
 * Copyright 2018 Nexenta Systems, Inc.
 * Copyright 2013 Damian Bogel. All rights reserved.
 * Copyright 2020 Oxide Computer Company
 */

#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdarg.h>
#include <regex.h>
#include <limits.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <locale.h>
#include <wchar.h>
#include <errno.h>
#include <unistd.h>
#include <wctype.h>
#include <ftw.h>
#include <sys/param.h>
#include <getopt.h>

#define	STDIN_FILENAME gettext("(standard input)")

#define	BSIZE		512		/* Size of block for -b */
#define	BUFSIZE		8192		/* Input buffer size */
#define	MAX_DEPTH	1000		/* how deep to recurse */

#define	AFTER	1			/* 'After' Context */
#define	BEFORE	2			/* 'Before' Context */
#define	CONTEXT	(AFTER|BEFORE)		/* Full Context */

#define	M_CSETSIZE	256		/* singlebyte chars */
static int	bmglen;			/* length of BMG pattern */
static char	*bmgpat;		/* BMG pattern */
static int	bmgtab[M_CSETSIZE];	/* BMG delta1 table */

typedef	struct	_PATTERN	{
	char	*pattern;		/* original pattern */
	struct	_PATTERN	*next;
	regex_t	re;			/* compiled pattern */
} PATTERN;

static PATTERN	*patterns;
static char	errstr[128];		/* regerror string buffer */
static int	regflags = 0;		/* regcomp options */
static int	matched = 0;		/* return of the grep() */
static int	errors = 0;		/* count of errors */
static uchar_t	fgrep = 0;		/* Invoked as fgrep */
static uchar_t	egrep = 0;		/* Invoked as egrep */
static boolean_t	nvflag = B_TRUE;	/* Print matching lines */
static uchar_t	cflag;			/* Count of matches */
static uchar_t	iflag;			/* Case insensitve matching */
static uchar_t	Hflag;			/* Precede lines by file name */
static uchar_t	hflag;			/* Suppress printing of filename */
static uchar_t	lflag;			/* Print file names of matches */
static uchar_t	Lflag;			/* Print file names of non-matches */
static uchar_t	nflag;			/* Precede lines by line number */
static uchar_t	rflag;			/* Search directories recursively */
static uchar_t	bflag;			/* Precede matches by block number */
static uchar_t	sflag;			/* Suppress file error messages */
static uchar_t	qflag;			/* Suppress standard output */
static uchar_t	wflag;			/* Search for expression as a word */
static uchar_t	xflag;			/* Anchoring */
static uchar_t	Eflag;			/* Egrep or -E flag */
static uchar_t	Fflag;			/* Fgrep or -F flag */
static uchar_t	Rflag;			/* Like rflag, but follow symlinks */
static uchar_t	outfn;			/* Put out file name */
static uchar_t	conflag;		/* show context of matches */
static uchar_t	oflag;			/* Print only matching output */
static char	*cmdname;
static char	*stdin_label;		/* Optional lable for stdin */

static int	use_bmg, mblocale;

static size_t	prntbuflen, conbuflen;
static unsigned long	conalen, conblen, conmatches;
static char	*prntbuf, *conbuf;

static void	addfile(const char *fn);
static void	addpattern(char *s);
static void	fixpatterns(void);
static void	usage(void);
static int	grep(int, const char *);
static void	bmgcomp(char *, int);
static char	*bmgexec(char *, char *);
static int	recursive(const char *, const struct stat *, int, struct FTW *);
static void	process_path(const char *);
static void	process_file(const char *, int);

/*
 * These are values that we use to return from getopt_long. They start at
 * SHRT_MAX to avoid any possible conflict with the normal options. These are
 * used for long options that have no short option equivalent.
 */
enum grep_opts {
	OPT_LABEL = SHRT_MAX + 1
};

static struct option grep_options[] = {
	{ "label", required_argument, NULL, OPT_LABEL },
	{ NULL }
};

/*
 * mainline for grep
 */
int
main(int argc, char **argv)
{
	char	*ap, *test;
	int	c;
	int	fflag = 0;
	int	i, n_pattern = 0, n_file = 0;
	char	**pattern_list = NULL;
	char	**file_list = NULL;

	(void) setlocale(LC_ALL, "");
#if !defined(TEXT_DOMAIN)	/* Should be defined by cc -D */
#define	TEXT_DOMAIN	"SYS_TEST"	/* Use this only if it weren't */
#endif
	(void) textdomain(TEXT_DOMAIN);

	/*
	 * true if this is running on the multibyte locale
	 */
	mblocale = (MB_CUR_MAX > 1);
	/*
	 * Skip leading slashes
	 */
	cmdname = argv[0];
	if (ap = strrchr(cmdname, '/'))
		cmdname = ap + 1;

	ap = cmdname;
	/*
	 * Detect egrep/fgrep via command name, map to -E and -F options.
	 */
	if (*ap == 'e' || *ap == 'E') {
		regflags |= REG_EXTENDED;
		egrep++;
	} else {
		if (*ap == 'f' || *ap == 'F') {
			fgrep++;
			regflags |= REG_NOSPEC;
		}
	}

	/* check for non-standard "-line-count" option */
	for (i = 1; i < argc; i++) {
		if (strcmp(argv[i], "--") == 0)
			break;

		/* isdigit() check prevents negative arguments */
		if ((argv[i][0] == '-') && isdigit(argv[i][1])) {
			if (strlen(&argv[i][1]) !=
			    strspn(&argv[i][1], "0123456789")) {
				(void) fprintf(stderr, gettext(
				    "%s: Bad number flag\n"), argv[0]);
				usage();
			}

			errno = 0;
			conalen = conblen = strtoul(&argv[i][1], (char **)NULL,
			    10);

			if (errno != 0 || conalen >= ULONG_MAX) {
				(void) fprintf(stderr, gettext(
				    "%s: Bad context argument\n"), argv[0]);
			} else if (conalen)
				conflag = CONTEXT;

			while (i < argc) {
				argv[i] = argv[i + 1];
				i++;
			}
			argc--;
		}
	}

	while ((c = getopt_long(argc, argv, "+vwchHilLnrbse:f:qxEFIRA:B:C:o",
	    grep_options, NULL)) != EOF) {
		unsigned long tval;
		switch (c) {
		case 'v':	/* POSIX: negate matches */
			nvflag = B_FALSE;
			break;

		case 'c':	/* POSIX: write count */
			cflag++;
			break;

		case 'i':	/* POSIX: ignore case */
			iflag++;
			regflags |= REG_ICASE;
			break;

		/*
		 * The last of -l and -L are honored.
		 */
		case 'l':	/* POSIX: Write filenames only */
			lflag++;
			Lflag = 0;
			break;

		case 'L':	/* Write non-matching filenames */
			Lflag++;
			lflag = 0;
			break;

		case 'n':	/* POSIX: Write line numbers */
			nflag++;
			break;

		case 'r':	/* Solaris: search recursively */
			rflag++;
			break;

		case 'b':	/* Solaris: Write file block numbers */
			bflag++;
			break;

		case 's':	/* POSIX: No error msgs for files */
			sflag++;
			break;

		case 'e':	/* POSIX: pattern list */
			n_pattern++;
			pattern_list = realloc(pattern_list,
			    sizeof (char *) * n_pattern);
			if (pattern_list == NULL) {
				(void) fprintf(stderr,
				    gettext("%s: out of memory\n"),
				    cmdname);
				exit(2);
			}
			*(pattern_list + n_pattern - 1) = optarg;
			break;

		case 'f':	/* POSIX: pattern file */
			fflag = 1;
			n_file++;
			file_list = realloc(file_list,
			    sizeof (char *) * n_file);
			if (file_list == NULL) {
				(void) fprintf(stderr,
				    gettext("%s: out of memory\n"),
				    cmdname);
				exit(2);
			}
			*(file_list + n_file - 1) = optarg;
			break;

		/* based on options order h or H is set as in GNU grep */
		case 'h':	/* Solaris: suppress printing of file name */
			hflag = 1;
			Hflag = 0;
			break;
		/* Solaris: precede every match with file name */
		case 'H':
			Hflag = 1;
			hflag = 0;
			break;

		case 'q':	/* POSIX: quiet: status only */
			qflag++;
			break;

		case 'w':	/* Solaris: treat pattern as word */
			wflag++;
			break;

		case 'x':	/* POSIX: full line matches */
			xflag++;
			break;

		case 'E':	/* POSIX: Extended RE's */
			regflags |= REG_EXTENDED;
			Eflag++;
			break;

		case 'F':	/* POSIX: strings, not RE's */
			Fflag++;
			regflags |= REG_NOSPEC;
			break;

		case 'R':	/* Solaris: like rflag, but follow symlinks */
			Rflag++;
			rflag++;
			break;

		case 'A':	/* print N lines after each match */
			errno = 0;
			conalen = strtoul(optarg, &test, 10);
			/* *test will be non-null if optarg is negative */
			if (errno != 0 || *test != '\0' ||
			    conalen >= ULONG_MAX) {
				(void) fprintf(stderr, gettext(
				    "%s: Bad context argument: %s\n"),
				    argv[0], optarg);
				exit(2);
			}
			if (conalen)
				conflag |= AFTER;
			else
				conflag &= ~AFTER;
			break;
		case 'B':	/* print N lines before each match */
			errno = 0;
			conblen = strtoul(optarg, &test, 10);
			/* *test will be non-null if optarg is negative */
			if (errno != 0 || *test != '\0' ||
			    conblen >= ULONG_MAX) {
				(void) fprintf(stderr, gettext(
				    "%s: Bad context argument: %s\n"),
				    argv[0], optarg);
				exit(2);
			}
			if (conblen)
				conflag |= BEFORE;
			else
				conflag &= ~BEFORE;
			break;
		case 'C':	/* print N lines around each match */
			errno = 0;
			tval = strtoul(optarg, &test, 10);
			/* *test will be non-null if optarg is negative */
			if (errno != 0 || *test != '\0' || tval >= ULONG_MAX) {
				(void) fprintf(stderr, gettext(
				    "%s: Bad context argument: %s\n"),
				    argv[0], optarg);
				exit(2);
			}
			if (tval) {
				if ((conflag & BEFORE) == 0)
					conblen = tval;
				if ((conflag & AFTER) == 0)
					conalen = tval;
				conflag = CONTEXT;
			}
			break;

		case OPT_LABEL:
			stdin_label = optarg;
			break;

		case 'o':
			oflag++;
			break;

		default:
			usage();
		}
	}
	/*
	 * If we're invoked as egrep or fgrep we need to do some checks
	 */

	if (egrep || fgrep) {
		/*
		 * Use of -E or -F with egrep or fgrep is illegal
		 */
		if (Eflag || Fflag)
			usage();
		/*
		 * Don't allow use of wflag with egrep / fgrep
		 */
		if (wflag)
			usage();
		/*
		 * For Solaris the -s flag is equivalent to XCU -q
		 */
		if (sflag)
			qflag++;
		/*
		 * done with above checks - set the appropriate flags
		 */
		if (egrep)
			Eflag++;
		else			/* Else fgrep */
			Fflag++;
	}

	if (wflag && (Eflag || Fflag)) {
		/*
		 * -w cannot be specified with grep -F
		 */
		usage();
	}

	/*
	 * -E and -F flags are mutually exclusive - check for this
	 */
	if (Eflag && Fflag)
		usage();

	/*
	 * -l or -L overrides -H like in GNU grep. It also overrides -o.
	 */
	if (lflag || Lflag) {
		Hflag = 0;
		oflag = 0;
	}

	/*
	 * -c, -l and -q flags are mutually exclusive
	 * We have -c override -l like in Solaris.
	 * -q overrides -l & -c programmatically in grep() function.
	 * -c overrides -o in GNU grep, we honor that.
	 */
	if (cflag) {
		lflag = 0;
		Lflag = 0;
		oflag = 0;
	}

	/*
	 * If -o is set then we ignore all context related options, like other
	 * greps.
	 */
	if (oflag) {
		conflag = 0;
	}

	/*
	 * These flags are a semantic mess with no clear answers as to their
	 * behvaior. Based on some experimentation GNU grep will exit zero if a
	 * non-match is present, but never print anything. BSD grep seems to
	 * exit 1 and not print anything, even if there would have been a match.
	 * Also, you probably don't want to ask about what happens with grep -x
	 * -o -v, some implementations seem to just ignore -v.
	 */
	if (oflag && !nvflag) {
		(void) fprintf(stderr, gettext("%s: the combination of -v and "
		    "-o is not supported currently\n"), argv[0]);
		exit(2);
	}

	argv += optind - 1;
	argc -= optind - 1;

	/*
	 * Now handling -e and -f option
	 */
	if (pattern_list) {
		for (i = 0; i < n_pattern; i++) {
			addpattern(pattern_list[i]);
		}
		free(pattern_list);
	}
	if (file_list) {
		for (i = 0; i < n_file; i++) {
			addfile(file_list[i]);
		}
		free(file_list);
	}

	/*
	 * No -e or -f?  Make sure there is one more arg, use it as the pattern.
	 */
	if (patterns == NULL && !fflag) {
		if (argc < 2)
			usage();
		addpattern(argv[1]);
		argc--;
		argv++;
	}

	/*
	 * Compile Patterns and also decide if BMG can be used
	 */
	fixpatterns();

	if (stdin_label == NULL) {
		stdin_label = STDIN_FILENAME;
	}

	/* Process all files: stdin, or rest of arg list */
	if (argc < 2) {
		matched = grep(0, stdin_label);
	} else {
		if (Hflag || (argc > 2 && hflag == 0))
			outfn = 1;	/* Print filename on match line */
		for (argv++; *argv != NULL; argv++) {
			process_path(*argv);
		}
	}
	/*
	 * Return() here is used instead of exit
	 */

	(void) fflush(stdout);

	if (errors)
		return (2);
	return (matched ? 0 : 1);
}

static void
process_path(const char *path)
{
	struct	stat st;
	int	walkflags = FTW_CHDIR;
	char	*buf = NULL;

	if (rflag) {
		if (stat(path, &st) != -1 &&
		    (st.st_mode & S_IFMT) == S_IFDIR) {
			if (!hflag)
				outfn = 1; /* Print filename unless -h */

			/*
			 * Add trailing slash if arg
			 * is directory, to resolve symlinks.
			 */
			if (path[strlen(path) - 1] != '/') {
				(void) asprintf(&buf, "%s/", path);
				if (buf != NULL)
					path = buf;
			}

			/*
			 * Search through subdirs if path is directory.
			 * Don't follow symlinks if Rflag is not set.
			 */
			if (!Rflag)
				walkflags |= FTW_PHYS;

			if (nftw(path, recursive, MAX_DEPTH, walkflags) != 0) {
				if (!sflag)
					(void) fprintf(stderr,
					    gettext("%s: can't open \"%s\"\n"),
					    cmdname, path);
				errors = 1;
			}
			return;
		}
	}
	process_file(path, 0);
}

/*
 * Read and process all files in directory recursively.
 */
static int
recursive(const char *name, const struct stat *statp, int info, struct FTW *ftw)
{
	/*
	 * Process files and follow symlinks if Rflag set.
	 */
	if (info != FTW_F) {
		/* Report broken symlinks and unreadable files */
		if (!sflag &&
		    (info == FTW_SLN || info == FTW_DNR || info == FTW_NS)) {
			(void) fprintf(stderr,
			    gettext("%s: can't open \"%s\"\n"), cmdname, name);
		}
		return (0);
	}


	/* Skip devices and pipes if Rflag is not set */
	if (!Rflag && !S_ISREG(statp->st_mode))
		return (0);
	/* Pass offset to relative name from FTW_CHDIR */
	process_file(name, ftw->base);
	return (0);
}

/*
 * Opens file and call grep function.
 */
static void
process_file(const char *name, int base)
{
	int fd;

	if ((fd = open(name + base, O_RDONLY)) == -1) {
		errors = 1;
		if (!sflag) /* Silent mode */
			(void) fprintf(stderr, gettext(
			    "%s: can't open \"%s\"\n"),
			    cmdname, name);
		return;
	}
	matched |= grep(fd, name);
	(void) close(fd);

	if (ferror(stdout)) {
		(void) fprintf(stderr, gettext(
		    "%s: error writing to stdout\n"),
		    cmdname);
		(void) fflush(stdout);
		exit(2);
	}

}

/*
 * Add a file of strings to the pattern list.
 */
static void
addfile(const char *fn)
{
	FILE	*fp;
	char	*inbuf;
	char	*bufp;
	size_t	bufsiz, buflen, bufused;

	/*
	 * Open the pattern file
	 */
	if ((fp = fopen(fn, "r")) == NULL) {
		(void) fprintf(stderr, gettext("%s: can't open \"%s\"\n"),
		    cmdname, fn);
		exit(2);
	}
	bufsiz = BUFSIZE;
	if ((inbuf = malloc(bufsiz)) == NULL) {
		(void) fprintf(stderr,
		    gettext("%s: out of memory\n"), cmdname);
		exit(2);
	}
	bufp = inbuf;
	bufused = 0;
	/*
	 * Read in the file, reallocing as we need more memory
	 */
	while (fgets(bufp, bufsiz - bufused, fp) != NULL) {
		buflen = strlen(bufp);
		bufused += buflen;
		if (bufused + 1 == bufsiz && bufp[buflen - 1] != '\n') {
			/*
			 * if this line does not fit to the buffer,
			 * realloc larger buffer
			 */
			bufsiz += BUFSIZE;
			if ((inbuf = realloc(inbuf, bufsiz)) == NULL) {
				(void) fprintf(stderr,
				    gettext("%s: out of memory\n"),
				    cmdname);
				exit(2);
			}
			bufp = inbuf + bufused;
			continue;
		}
		if (bufp[buflen - 1] == '\n') {
			bufp[--buflen] = '\0';
		}
		addpattern(inbuf);

		bufp = inbuf;
		bufused = 0;
	}
	free(inbuf);
	free(prntbuf);
	free(conbuf);
	(void) fclose(fp);
}

/*
 * Add a string to the pattern list.
 */
static void
addpattern(char *s)
{
	PATTERN	*pp;
	char	*wordbuf;
	char	*np;

	for (; ; ) {
		np = strchr(s, '\n');
		if (np != NULL)
			*np = '\0';
		if ((pp = malloc(sizeof (PATTERN))) == NULL) {
			(void) fprintf(stderr, gettext(
			    "%s: out of memory\n"),
			    cmdname);
			exit(2);
		}
		if (wflag) {
			/*
			 * Solaris wflag support: Add '<' '>' to pattern to
			 * select it as a word. Doesn't make sense with -F
			 * but we're Libertarian.
			 */
			size_t	slen, wordlen;

			slen = strlen(s);
			wordlen = slen + 5; /* '\\' '<' s '\\' '>' '\0' */
			if ((wordbuf = malloc(wordlen)) == NULL) {
				(void) fprintf(stderr,
				    gettext("%s: out of memory\n"),
				    cmdname);
				exit(2);
			}
			(void) strcpy(wordbuf, "\\<");
			(void) strcpy(wordbuf + 2, s);
			(void) strcpy(wordbuf + 2 + slen, "\\>");
		} else {
			if ((wordbuf = strdup(s)) == NULL) {
				(void) fprintf(stderr,
				    gettext("%s: out of memory\n"),
				    cmdname);
				exit(2);
			}
		}
		pp->pattern = wordbuf;
		pp->next = patterns;
		patterns = pp;
		if (np == NULL)
			break;
		s = np + 1;
	}
}

/*
 * Check if a given grep pattern that is being used with egrep or grep can be
 * considered 'simple'. That is there are no characters that would be treated
 * differently from fgrep. In this particular case, we're a little bit
 * conservative and look for characters that are:
 *
 *  o 7-bit ASCII
 *  o Letters
 *  o Numbers
 *  o Meta-characters not used in BREs/EREs: !, @, #, /, -, _, <, >, =
 *
 * This can certianly be made more complex and less restrictive with additional
 * testing.
 */
static boolean_t
simple_pattern(const char *str)
{
	for (; *str != '\0'; str++) {
		if (!isascii(*str)) {
			return (B_FALSE);
		}

		if (isalnum(*str)) {
			continue;
		}

		switch (*str) {
		case '!':
		case '@':
		case '#':
		case '/':
		case '-':
		case '_':
		case '<':
		case '>':
		case '=':
			continue;
		default:
			return (B_FALSE);
		}
	}

	return (B_TRUE);
}

/*
 * Fix patterns.
 * Must do after all arguments read, in case later -i option.
 */
static void
fixpatterns(void)
{
	PATTERN	*pp;
	int	rv, fix_pattern;

	/*
	 * Decide if we are able to run the Boyer-Moore-Gosper algorithm.
	 * Use the Boyer-Moore-Gosper algorithm if:
	 * - fgrep or non-BRE/ERE	(Fflag || simple_pattern())
	 * - singlebyte locale		(!mblocale)
	 * - no ignoring case		(!iflag)
	 * - no printing line numbers	(!nflag)
	 * - no negating the output	(nvflag)
	 * - only one pattern		(patterns != NULL && patterns->next ==
	 *				    NULL)
	 * - non zero length pattern	(strlen(patterns->pattern) != 0)
	 * - no context required	(conflag == 0)
	 * - no exact matches		(!oflag)
	 * - no word matches		(!wlag)
	 */
	use_bmg = !mblocale && !iflag && !nflag && nvflag && !oflag &&
	    (patterns != NULL && patterns->next == NULL) && !wflag &&
	    (strlen(patterns->pattern) != 0) && conflag == 0 &&
	    (Fflag || simple_pattern(patterns->pattern));

	if (use_bmg) {
		return;
	}

	/*
	 * Fix the specified pattern if -x is specified.
	 */
	fix_pattern = !Fflag && xflag;

	for (pp = patterns; pp != NULL; pp = pp->next) {
		if (fix_pattern) {
			char	*cp, *cq;
			size_t	plen, nplen;

			plen = strlen(pp->pattern);
			/* '^' pattern '$' */
			nplen = 1 + plen + 1 + 1;
			if ((cp = malloc(nplen)) == NULL) {
				(void) fprintf(stderr,
				    gettext("%s: out of memory\n"),
				    cmdname);
				exit(2);
			}
			cq = cp;
			*cq++ = '^';
			cq = strcpy(cq, pp->pattern) + plen;
			*cq++ = '$';
			*cq = '\0';
			free(pp->pattern);
			pp->pattern = cp;
		}

		/*
		 * Compile the regular expression, give an informative error
		 * message, and exit if it didn't compile.
		 */
		if ((rv = regcomp(&pp->re, pp->pattern, regflags)) != 0) {
			(void) regerror(rv, &pp->re, errstr, sizeof (errstr));
			(void) fprintf(stderr,
			    gettext("%s: RE error in %s: %s\n"),
			    cmdname, pp->pattern, errstr);
			exit(2);
		}
		free(pp->pattern);
	}
}

/*
 * Search a newline from the beginning of the string
 */
static char *
find_nl(const char *ptr, size_t len)
{
	while (len-- != 0) {
		if (*ptr++ == '\n') {
			return ((char *)--ptr);
		}
	}
	return (NULL);
}

/*
 * Search a newline from the end of the string
 */
static char *
rfind_nl(const char *ptr, size_t len)
{
	const char	*uptr = ptr + len;
	while (len--) {
		if (*--uptr == '\n') {
			return ((char *)uptr);
		}
	}
	return (NULL);
}

/*
 * Do grep on a single file.
 * Return true in any lines matched.
 *
 * We have two strategies:
 * The fast one is used when we have a single pattern with
 * a string known to occur in the pattern. We can then
 * do a BMG match on the whole buffer.
 * This is an order of magnitude faster.
 * Otherwise we split the buffer into lines,
 * and check for a match on each line.
 */
static int
grep(int fd, const char *fn)
{
	PATTERN *pp;
	off_t	data_len;	/* length of the data chunk */
	off_t	line_len;	/* length of the current line */
	off_t	line_offset;	/* current line's offset from the beginning */
	off_t	blkoffset;	/* line_offset but context-compatible */
	long long	lineno, linenum;
	long long	matches = 0;	/* Number of matching lines */
	long long	conacnt = 0, conbcnt = 0;	/* context line count */
	int	newlinep;	/* 0 if the last line of file has no newline */
	char	*ptr, *ptrend, *prntptr, *prntptrend;
	char	*nextptr = NULL, *nextend = NULL;
	char	*conptr = NULL, *conptrend = NULL;
	char	*matchptr = NULL;
	int	conaprnt = 0, conbprnt = 0, lastmatch = 0;
	boolean_t	nearmatch; /* w/in N+1 of last match */
	boolean_t	havematch = B_FALSE; /* have a match in context */
	boolean_t	sameline = B_FALSE; /* Are we still on the same line? */
	size_t	prntlen;

	if (patterns == NULL)
		return (0);	/* no patterns to match -- just return */

	pp = patterns;

	if (use_bmg) {
		bmgcomp(pp->pattern, strlen(pp->pattern));
	}

	if (prntbuf == NULL) {
		prntbuflen = BUFSIZE;
		if ((prntbuf = malloc(prntbuflen + 1)) == NULL) {
			(void) fprintf(stderr, gettext("%s: out of memory\n"),
			    cmdname);
			exit(2);
		}
	}

	if (conflag != 0 && (conbuf == NULL)) {
		conbuflen = BUFSIZE;
		if ((conbuf = malloc(BUFSIZE+1)) == NULL) {
			(void) fprintf(stderr, gettext("%s: out of memory\n"),
			    cmdname);
			exit(2);
		}
	}

	nearmatch = (conmatches != 0);
	blkoffset = line_offset = 0;
	lineno = 0;
	linenum = 1;
	newlinep = 1;
	data_len = 0;
	for (; ; ) {
		long	count;
		off_t	offset = 0;
		char	separate;
		char	*startmatch = NULL; /* -o, start of match */
		char	*postmatch = NULL; /* -o, character after match */
		boolean_t	last_ctx = B_FALSE, eof = B_FALSE;

		if (data_len == 0) {
			/*
			 * If no data in the buffer, reset ptr
			 */
			ptr = prntbuf;
			if (conflag != 0 && conptr == NULL) {
				conptr = conbuf;
				conptrend = conptr - 1;
			}
		}
		if (ptr == prntbuf) {
			/*
			 * The current data chunk starts from prntbuf.
			 * This means either the buffer has no data
			 * or the buffer has no newline.
			 * So, read more data from input.
			 */
			count = read(fd, ptr + data_len, prntbuflen - data_len);
			if (count < 0) {
				/* read error */
				if (cflag) {
					if (outfn && !rflag) {
						(void) fprintf(stdout,
						    "%s:", fn);
					}
					if (!qflag && !rflag) {
						(void) fprintf(stdout, "%lld\n",
						    matches);
					}
				}
				return (0);
			} else if (count == 0) {
				/* no new data */
				eof = B_TRUE;

				if (data_len == 0) {
					/* end of file already reached */
					if (conflag != 0) {
						if (conptrend >= conptr)
							*conptrend = '\n';
						last_ctx = B_TRUE;
						goto L_next_line;
					} else {
						goto out;
					}
				}
				/* last line of file has no newline */
				ptrend = ptr + data_len;
				newlinep = 0;
				goto L_start_process;
			}
			offset = data_len;
			data_len += count;
		}

		/*
		 * Look for newline in the chunk
		 * between ptr + offset and ptr + data_len - offset.
		 */
		ptrend = find_nl(ptr + offset, data_len - offset);
		if (ptrend == NULL) {
			/* no newline found in this chunk */
			if (ptr > prntbuf) {
				/*
				 * Move remaining data to the beginning
				 * of the buffer.
				 * Remaining data lie from ptr for
				 * data_len bytes.
				 */
				(void) memmove(prntbuf, ptr, data_len);
			}
			if (data_len == prntbuflen) {
				/*
				 * Not enough room in the buffer
				 */
				if (prntbuflen > SIZE_MAX - BUFSIZE) {
					(void) fprintf(stderr,
					    gettext("%s: buflen would"
					    " overflow\n"),
					    cmdname);
					exit(2);
				}

				prntbuflen += BUFSIZE;
				prntbuf = realloc(prntbuf, prntbuflen + 1);
				if (prntbuf == NULL) {
					(void) fprintf(stderr,
					    gettext("%s: out of memory\n"),
					    cmdname);
					exit(2);
				}
			}
			ptr = prntbuf;
			/* read the next input */
			continue;
		}
L_start_process:

		/*
		 * Beginning of the chunk:	ptr
		 * End of the chunk:		ptr + data_len
		 * Beginning of the line:	ptr
		 * End of the line:		ptrend
		 *
		 * conptr:	Beginning of the context.
		 * conptrend: If context is empty, conptr - 1 (invalid memory).
		 *	Otherwise, Last newline in the context.
		 */

		if (use_bmg) {
			/*
			 * Use Boyer-Moore-Gosper algorithm to find out if
			 * this chunk (not this line) contains the specified
			 * pattern.  If not, restart from the last line
			 * of this chunk.
			 */
			char	*bline;
			bline = bmgexec(ptr, ptr + data_len);
			if (bline == NULL) {
				/*
				 * No pattern found in this chunk.
				 * Need to find the last line
				 * in this chunk.
				 */
				ptrend = rfind_nl(ptr, data_len);

				/*
				 * When this chunk does not contain newline,
				 * ptrend becomes NULL, which should happen
				 * when the last line of file does not end
				 * with a newline.  At such a point,
				 * newlinep should have been set to 0.
				 * Therefore, just after jumping to
				 * L_skip_line, the main for-loop quits,
				 * and the line_len value won't be
				 * used.
				 */
				line_len = ptrend - ptr;
				goto L_skip_line;
			}
			if (bline > ptrend) {
				/*
				 * Pattern found not in the first line
				 * of this chunk.
				 * Discard the first line.
				 */
				line_len = ptrend - ptr;
				goto L_skip_line;
			}
			/*
			 * Pattern found in the first line of this chunk.
			 * Using this result.
			 */
			*ptrend = '\0';
			line_len = ptrend - ptr;

			/*
			 * before jumping to L_next_line,
			 * need to handle xflag if specified
			 */
			if (xflag && (line_len != bmglen ||
			    strcmp(bmgpat, ptr) != 0)) {
				/* didn't match */
				pp = NULL;
			} else {
				pp = patterns; /* to make it happen */
			}
			goto L_next_line;
		}

		/*
		 * When using -o, we might actually loop around while still on
		 * the same line. In such a case, we need to make sure we don't
		 * increment the line number.
		 */
		if (!sameline) {
			lineno++;
		} else {
			sameline = B_FALSE;
		}

		/*
		 * Line starts from ptr and ends at ptrend.
		 * line_len will be the length of the line.
		 */
		*ptrend = '\0';
		line_len = ptrend - ptr;

		/*
		 * From now, the process will be performed based
		 * on the line from ptr to ptrend.
		 */
		for (pp = patterns; pp; pp = pp->next) {
			int	rv;
			regmatch_t rm;
			size_t nmatch = 0;

			/*
			 * The current implementation of regexec has a higher
			 * cost when you ask for match information. As a result,
			 * we only ask for a match when we know that we need it
			 * specifically. This is always needed for -o because we
			 * rely on it to tell us what we matched. For fgrep -x
			 * we need it so we can determine whether we matched the
			 * entire line.
			 */
			if (oflag || (Fflag && xflag))
				nmatch = 1;

			rv = regexec(&pp->re, ptr, nmatch, &rm, 0);
			if (rv == REG_OK) {
				/*
				 * fgrep in this form cannot insert the
				 * metacharacters to verify whether or not we
				 * were the entire line. As a result, we check
				 * the pattern length against the line length.
				 */
				if (Fflag && xflag &&
				    line_len != rm.rm_eo - rm.rm_so) {
					continue;
				}

				/* matched */
				if (oflag) {
					startmatch = ptr + rm.rm_so;
					postmatch = ptr + rm.rm_eo;
				}
				break;
			}

			switch (rv) {
			case REG_NOMATCH:
				break;
			case REG_ECHAR:
				(void) fprintf(stderr, gettext(
	    "%s: input file \"%s\": line %lld: invalid multibyte character\n"),
				    cmdname, fn, lineno);
				break;
			default:
				(void) regerror(rv, &pp->re, errstr,
				    sizeof (errstr));
				(void) fprintf(stderr, gettext(
	    "%s: input file \"%s\": line %lld: %s\n"),
				    cmdname, fn, lineno, errstr);
				exit(2);
			}
		}

		/*
		 * Context is set up as follows:
		 * For a 'Before' context, we maintain a set of pointers
		 * containing 'N' lines of context. If the current number of
		 * lines contained is greater than N, and N isn't a match, the
		 * start pointer is moved forward to the next newline.
		 *
		 * If we ever find a match, we print out immediately.
		 * 'nearmatch' tells us if we're within N+1 lines of the last
		 * match ; if we are, and we find another match, we don't
		 * separate the matches. 'nearmatch' becomes false when
		 * a line gets rotated out of the context.
		 *
		 * For an 'After' context, we simply wait until we've found a
		 * match, then create a context N+1 lines big. If we don't find
		 * a match within the context, we print out the current context.
		 * Otherwise, we save a reference to the new matching line,
		 * print out the other context, and reset our context pointers
		 * to the new matching line.
		 *
		 * 'nearmatch' becomes false when we find a non-matching line
		 * that isn't a part of any context.
		 *
		 * A full-context is implemented as a combination of the
		 * 'Before' and 'After' context logic. Before we find a match,
		 * we follow the Before logic. When we find a match, we
		 * follow the After logic. 'nearmatch' is handled by the Before
		 * logic.
		 */

		if (conflag == 0)
			goto L_next_line;

		/* Do we have room to add this line to the context buffer? */
		while ((line_len + 1) > (conbuflen -
		    ((conptrend >= conptr) ? conptrend - conbuf : 0))) {
			char *oldconbuf = conbuf;
			char *oldconptr = conptr;
			long tmp = matchptr - conptr;

			if (conbuflen > SIZE_MAX - BUFSIZE) {
				(void) fprintf(stderr,
				    gettext("%s: buflen would overflow\n"),
				    cmdname);
				exit(2);
			}

			conbuflen += BUFSIZE;
			conbuf = realloc(conbuf, conbuflen + 1);
			if (conbuf == NULL) {
				(void) fprintf(stderr,
				    gettext("%s: out of memory\n"),
				    cmdname);
				exit(2);
			}

			conptr = conbuf + (conptr - oldconbuf);
			conptrend = conptr + (conptrend - oldconptr);
			if (matchptr)
				matchptr = conptr + tmp;
		}
		(void) memcpy(conptrend + 1, ptr, line_len);
		conptrend += line_len + 1;
		*conptrend = '\n';

		if (nvflag == (pp != NULL)) {
			/* matched */
			if (havematch) {
				if ((conflag & AFTER) != 0) {
					conaprnt = 1;
					nextend = conptrend;
					conptrend = conptr + lastmatch;
					nextptr = conptrend + 1;
					*nextend = '\n';
				}
			} else {
				if (conflag == AFTER) {
					conptr = conptrend - (line_len);
					linenum = lineno;
				}
				blkoffset = line_offset -
				    (conptrend - conptr - line_len);
			}

			if (conflag == BEFORE)
				conbprnt = 1;

			lastmatch = conptrend - conptr;
			havematch = B_TRUE;
			goto L_next_line;
		}

		if (!havematch) {
			if ((conflag & BEFORE) != 0) {
				if (conbcnt >= conblen) {
					char *tmp = conptr;
					conptr = find_nl(conptr,
					    conptrend - conptr) + 1;
					if (bflag)
						blkoffset += conptr - tmp;
					linenum++;
					nearmatch = B_TRUE;
				} else {
					conbcnt++;
				}
			}
			if (conflag == AFTER)
				nearmatch = B_TRUE;
		} else  {
			if (++conacnt >= conalen && !conaprnt && conalen)
				conaprnt = 1;
			else
				lastmatch = conptrend - conptr;
		}

L_next_line:
		/*
		 * Here, if pp points to non-NULL, something has been matched
		 * to the pattern.
		 */
		if (!last_ctx && nvflag == (pp != NULL)) {
			matches++;
			if (!nextend) {
				if (conflag != 0) {
					matchptr = conptrend;
				} else if (oflag) {
					matchptr = postmatch - 1;
				} else {
					matchptr = ptrend;
				}
			}
		}

		if (pp != NULL && oflag && postmatch == NULL) {
			(void) fprintf(stderr, gettext("%s: internal error, "
			    "-o set, but failed to find postmatch\n"), cmdname);
			abort();
		}

		/*
		 * Set up some print context so that we can treat
		 * single-line matches as a zero-N context.
		 * Apply CLI flags to each line of the context.
		 *
		 * For context, we only print if we both have a match and are
		 * either at the end of the data stream, or we've previously
		 * declared that we want to print for a particular context.
		 */
		if (havematch && (eof || conaprnt || conbprnt)) {

			/*
			 * We'd normally do this earlier, but we had to
			 * escape early because we reached the end of the data.
			 */
			if (eof && nextptr)
				conptrend = nextend;

			prntlen = conptrend - conptr + 1;
			prntptr = conptr;
			if (conmatches++ && nearmatch && !cflag)
				(void) fwrite("--\n", 1, 3, stdout);
		} else if (conflag == 0 && nvflag == (pp != NULL)) {
			*ptrend = '\n';
			if (oflag) {
				prntptr = startmatch;
			} else {
				prntptr = ptr;
			}
			prntlen = line_len + 1;
			linenum = lineno;
			blkoffset = line_offset;
			if (oflag) {
				blkoffset += startmatch - ptr;
			}
		} else if (eof) {
			/* No match and no more data */
			goto out;
		} else {
			/* No match, or we're not done building context */
			goto L_skip_line;
		}

		if (oflag) {
			prntptrend = postmatch - 1;
		} else {
			prntptrend = prntptr - 1;
		}
		while (oflag || (prntptrend = find_nl(prntptrend + 1,
		    prntlen)) != NULL) {
			/*
			 * GNU grep uses '-' for context lines and ':' for
			 * matching lines, so replicate that here.
			 */
			if (prntptrend == matchptr) {
				if (eof && nextptr) {
					matchptr = nextend;
					nextptr = NULL;
				} else {
					matchptr = NULL;
				}
				separate = ':';
			} else {
				separate = '-';
			}

			/*
			 * Handle q, l, and c flags.
			 */
			if (qflag) {
				/* no need to continue */
				/*
				 * End of this line is ptrend.
				 * We have read up to ptr + data_len.
				 */
				off_t	pos;
				pos = ptr + data_len - (ptrend + 1);
				(void) lseek(fd, -pos, SEEK_CUR);
				exit(0);
			}
			if (lflag) {
				(void) printf("%s\n", fn);
				goto out;
			}
			if (Lflag) {
				goto out;
			}
			if (!cflag) {
				if (Hflag || outfn) {
					(void) printf("%s%c", fn, separate);
				}
				if (bflag) {
					(void) printf("%lld%c", (offset_t)
					    (blkoffset / BSIZE), separate);
				}
				if (nflag) {
					(void) printf("%lld%c", linenum,
					    separate);
				}
				(void) fwrite(prntptr, 1,
				    prntptrend - prntptr + 1, stdout);

				if (oflag) {
					(void) fputc('\n', stdout);
				}
			}
			if (ferror(stdout)) {
				return (0);
			}

			/*
			 * With -o we'll only ever take this loop once. Manually
			 * break out.
			 */
			if (oflag) {
				goto L_skip_line;
			}

			linenum++;
			prntlen -= prntptrend - prntptr + 1;
			blkoffset += prntptrend - prntptr + 1;
			prntptr = prntptrend + 1;
		}

		if (eof)
			goto out;

		/*
		 * Update context buffer and variables post-print
		 */
		if (conflag != 0) {
			conptr = conbuf;
			conaprnt = conbprnt = 0;
			nearmatch = B_FALSE;
			conacnt = conbcnt = 0;

			if (nextptr) {
				(void) memmove(conbuf, nextptr,
				    nextend - nextptr + 1);
				blkoffset += nextptr - conptrend - 1;
				conptrend = conptr + (nextend - nextptr);
				matchptr = conptrend;
				linenum = lineno;
				lastmatch = conptrend - conptr;
				havematch = B_TRUE;
			} else {
				conptrend = conptr - 1;
				conacnt = 0;
				lastmatch = 0;
				havematch = B_FALSE;
			}
			nextptr = nextend = NULL;
		}

L_skip_line:
		if (!newlinep)
			break;

		if (oflag && postmatch != NULL) {
			line_len = postmatch - 1 - ptr;
			ptr = postmatch;
			sameline = B_TRUE;
		} else {
			ptr = ptrend + 1;
		}
		data_len -= line_len + 1;
		line_offset += line_len + 1;
	}

out:
	if (cflag) {
		if (Hflag || outfn) {
			(void) printf("%s:", fn);
		}
		if (!qflag) {
			(void) printf("%lld\n", matches);
		}
	}

	/*
	 * -L tells us to print the filename only when it doesn't match. So we
	 * run through the normal operationa and then invert it.
	 */
	if (Lflag) {
		if (matches == 0) {
			(void) printf("%s\n", fn);
			matches = 1;
		} else {
			matches = 0;
		}
	}

	return (matches != 0);
}

/*
 * usage message for grep
 */
static void
usage(void)
{
	(void) fprintf(stderr, gettext("usage: %5s"), cmdname);
	if (!egrep && !fgrep)
		(void) fprintf(stderr, gettext(" [-E|-F]"));
	(void) fprintf(stderr, gettext(" [-bchHilLnoqrRsvx] [-A num] [-B num] "
	    "[-C num|-num]\n             [--label=name] [-e pattern_list]... "
	    "[-f pattern_file]...\n             [pattern_list] [file]...\n"));
	exit(2);
	/* NOTREACHED */
}

/*
 * Compile literal pattern into BMG tables
 */
static void
bmgcomp(char *pat, int len)
{
	int	i;
	int	tlen;
	unsigned char	*uc = (unsigned char *)pat;

	bmglen = len;
	bmgpat = pat;

	for (i = 0; i < M_CSETSIZE; i++) {
		bmgtab[i] = len;
	}

	len--;
	for (tlen = len, i = 0; i <= len; i++, tlen--) {
		bmgtab[*uc++] = tlen;
	}
}

/*
 * BMG search.
 */
static char *
bmgexec(char *str, char *end)
{
	int	t;
	char	*k, *s, *p;

	k = str + bmglen - 1;
	if (bmglen == 1) {
		return (memchr(str, bmgpat[0], end - str));
	}
	for (; ; ) {
		/* inner loop, should be most optimized */
		while (k < end && (t = bmgtab[(unsigned char)*k]) != 0) {
			k += t;
		}
		if (k >= end) {
			return (NULL);
		}
		for (s = k, p = bmgpat + bmglen - 1; *--s == *--p; ) {
			if (p == bmgpat) {
				return (s);
			}
		}
		k++;
	}
	/* NOTREACHED */
}