util.c revision 322607 
1/*	$NetBSD: util.c,v 1.9 2011/02/27 17:33:37 joerg Exp $	*/
2/*	$FreeBSD: stable/11/usr.bin/grep/util.c 322607 2017-08-17 04:04:42Z kevans $	*/
3/*	$OpenBSD: util.c,v 1.39 2010/07/02 22:18:03 tedu Exp $	*/
4
5/*-
6 * Copyright (c) 1999 James Howard and Dag-Erling Co��dan Sm��rgrav
7 * Copyright (C) 2008-2010 Gabor Kovesdan <gabor@FreeBSD.org>
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 */
31
32#include <sys/cdefs.h>
33__FBSDID("$FreeBSD: stable/11/usr.bin/grep/util.c 322607 2017-08-17 04:04:42Z kevans $");
34
35#include <sys/stat.h>
36#include <sys/types.h>
37
38#include <ctype.h>
39#include <err.h>
40#include <errno.h>
41#include <fnmatch.h>
42#include <fts.h>
43#include <libgen.h>
44#include <stdbool.h>
45#include <stdio.h>
46#include <stdlib.h>
47#include <string.h>
48#include <unistd.h>
49#include <wchar.h>
50#include <wctype.h>
51
52#ifndef WITHOUT_FASTMATCH
53#include "fastmatch.h"
54#endif
55#include "grep.h"
56
57static bool	 first_match = true;
58
59/*
60 * Parsing context; used to hold things like matches made and
61 * other useful bits
62 */
63struct parsec {
64	regmatch_t matches[MAX_LINE_MATCHES];	/* Matches made */
65	struct str ln;				/* Current line */
66	size_t matchidx;			/* Latest used match index */
67	bool binary;				/* Binary file? */
68};
69
70
71static int procline(struct parsec *pc);
72static void printline(struct parsec *pc, int sep);
73static void printline_metadata(struct str *line, int sep);
74
75bool
76file_matching(const char *fname)
77{
78	char *fname_base, *fname_buf;
79	bool ret;
80
81	ret = finclude ? false : true;
82	fname_buf = strdup(fname);
83	if (fname_buf == NULL)
84		err(2, "strdup");
85	fname_base = basename(fname_buf);
86
87	for (unsigned int i = 0; i < fpatterns; ++i) {
88		if (fnmatch(fpattern[i].pat, fname, 0) == 0 ||
89		    fnmatch(fpattern[i].pat, fname_base, 0) == 0) {
90			if (fpattern[i].mode == EXCL_PAT) {
91				ret = false;
92				break;
93			} else
94				ret = true;
95		}
96	}
97	free(fname_buf);
98	return (ret);
99}
100
101static inline bool
102dir_matching(const char *dname)
103{
104	bool ret;
105
106	ret = dinclude ? false : true;
107
108	for (unsigned int i = 0; i < dpatterns; ++i) {
109		if (dname != NULL &&
110		    fnmatch(dpattern[i].pat, dname, 0) == 0) {
111			if (dpattern[i].mode == EXCL_PAT)
112				return (false);
113			else
114				ret = true;
115		}
116	}
117	return (ret);
118}
119
120/*
121 * Processes a directory when a recursive search is performed with
122 * the -R option.  Each appropriate file is passed to procfile().
123 */
124int
125grep_tree(char **argv)
126{
127	FTS *fts;
128	FTSENT *p;
129	int c, fts_flags;
130	bool ok;
131	const char *wd[] = { ".", NULL };
132
133	c = fts_flags = 0;
134
135	switch(linkbehave) {
136	case LINK_EXPLICIT:
137		fts_flags = FTS_COMFOLLOW;
138		break;
139	case LINK_SKIP:
140		fts_flags = FTS_PHYSICAL;
141		break;
142	default:
143		fts_flags = FTS_LOGICAL;
144
145	}
146
147	fts_flags |= FTS_NOSTAT | FTS_NOCHDIR;
148
149	fts = fts_open((argv[0] == NULL) ?
150	    __DECONST(char * const *, wd) : argv, fts_flags, NULL);
151	if (fts == NULL)
152		err(2, "fts_open");
153	while ((p = fts_read(fts)) != NULL) {
154		switch (p->fts_info) {
155		case FTS_DNR:
156			/* FALLTHROUGH */
157		case FTS_ERR:
158			file_err = true;
159			if(!sflag)
160				warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
161			break;
162		case FTS_D:
163			/* FALLTHROUGH */
164		case FTS_DP:
165			if (dexclude || dinclude)
166				if (!dir_matching(p->fts_name) ||
167				    !dir_matching(p->fts_path))
168					fts_set(fts, p, FTS_SKIP);
169			break;
170		case FTS_DC:
171			/* Print a warning for recursive directory loop */
172			warnx("warning: %s: recursive directory loop",
173				p->fts_path);
174			break;
175		default:
176			/* Check for file exclusion/inclusion */
177			ok = true;
178			if (fexclude || finclude)
179				ok &= file_matching(p->fts_path);
180
181			if (ok)
182				c += procfile(p->fts_path);
183			break;
184		}
185	}
186
187	fts_close(fts);
188	return (c);
189}
190
191/*
192 * Opens a file and processes it.  Each file is processed line-by-line
193 * passing the lines to procline().
194 */
195int
196procfile(const char *fn)
197{
198	struct parsec pc;
199	long long tail;
200	struct file *f;
201	struct stat sb;
202	struct str *ln;
203	mode_t s;
204	int c, last_outed, t;
205	bool doctx, printmatch, same_file;
206
207	if (strcmp(fn, "-") == 0) {
208		fn = label != NULL ? label : getstr(1);
209		f = grep_open(NULL);
210	} else {
211		if (!stat(fn, &sb)) {
212			/* Check if we need to process the file */
213			s = sb.st_mode & S_IFMT;
214			if (s == S_IFDIR && dirbehave == DIR_SKIP)
215				return (0);
216			if ((s == S_IFIFO || s == S_IFCHR || s == S_IFBLK
217				|| s == S_IFSOCK) && devbehave == DEV_SKIP)
218					return (0);
219		}
220		f = grep_open(fn);
221	}
222	if (f == NULL) {
223		file_err = true;
224		if (!sflag)
225			warn("%s", fn);
226		return (0);
227	}
228
229	/* Convenience */
230	ln = &pc.ln;
231	pc.ln.file = grep_malloc(strlen(fn) + 1);
232	strcpy(pc.ln.file, fn);
233	pc.ln.line_no = 0;
234	pc.ln.len = 0;
235	pc.ln.off = -1;
236	pc.binary = f->binary;
237	tail = 0;
238	last_outed = 0;
239	same_file = false;
240	doctx = false;
241	printmatch = true;
242	if ((pc.binary && binbehave == BINFILE_BIN) || cflag || qflag ||
243	    lflag || Lflag)
244		printmatch = false;
245	if (printmatch && (Aflag != 0 || Bflag != 0))
246		doctx = true;
247	mcount = mlimit;
248
249	for (c = 0;  c == 0 || !(lflag || qflag); ) {
250		/* Reset match count for every line processed */
251		pc.matchidx = 0;
252		pc.ln.off += pc.ln.len + 1;
253		if ((pc.ln.dat = grep_fgetln(f, &pc.ln.len)) == NULL ||
254		    pc.ln.len == 0) {
255			if (pc.ln.line_no == 0 && matchall)
256				/*
257				 * An empty file with an empty pattern and the
258				 * -w flag does not match
259				 */
260				exit(matchall && wflag ? 1 : 0);
261			else
262				break;
263		}
264
265		if (pc.ln.len > 0 && pc.ln.dat[pc.ln.len - 1] == fileeol)
266			--pc.ln.len;
267		pc.ln.line_no++;
268
269		/* Return if we need to skip a binary file */
270		if (pc.binary && binbehave == BINFILE_SKIP) {
271			grep_close(f);
272			free(pc.ln.file);
273			free(f);
274			return (0);
275		}
276
277		if ((t = procline(&pc)) == 0)
278			++c;
279
280		/* Deal with any -B context or context separators */
281		if (t == 0 && doctx) {
282			if (!first_match && (!same_file || last_outed > 0))
283				printf("--\n");
284			if (Bflag > 0)
285				printqueue();
286			tail = Aflag;
287		}
288		/* Print the matching line, but only if not quiet/binary */
289		if (t == 0 && printmatch) {
290			printline(&pc, ':');
291			first_match = false;
292			same_file = true;
293			last_outed = 0;
294		}
295		if (t != 0 && doctx) {
296			/* Deal with any -A context */
297			if (tail > 0) {
298				printline(&pc, '-');
299				tail--;
300				if (Bflag > 0)
301					clearqueue();
302			} else {
303				/*
304				 * Enqueue non-matching lines for -B context.
305				 * If we're not actually doing -B context or if
306				 * the enqueue resulted in a line being rotated
307				 * out, then go ahead and increment last_outed
308				 * to signify a gap between context/match.
309				 */
310				if (Bflag == 0 || (Bflag > 0 && enqueue(ln)))
311					++last_outed;
312			}
313		}
314
315		/* Count the matches if we have a match limit */
316		if (t == 0 && mflag) {
317			--mcount;
318			if (mflag && mcount <= 0)
319				break;
320		}
321
322	}
323	if (Bflag > 0)
324		clearqueue();
325	grep_close(f);
326
327	if (cflag) {
328		if (!hflag)
329			printf("%s:", pc.ln.file);
330		printf("%u\n", c);
331	}
332	if (lflag && !qflag && c != 0)
333		printf("%s%c", fn, nullflag ? 0 : '\n');
334	if (Lflag && !qflag && c == 0)
335		printf("%s%c", fn, nullflag ? 0 : '\n');
336	if (c && !cflag && !lflag && !Lflag &&
337	    binbehave == BINFILE_BIN && f->binary && !qflag)
338		printf(getstr(8), fn);
339
340	free(pc.ln.file);
341	free(f);
342	return (c);
343}
344
345#define iswword(x)	(iswalnum((x)) || (x) == L'_')
346
347/*
348 * Processes a line comparing it with the specified patterns.  Each pattern
349 * is looped to be compared along with the full string, saving each and every
350 * match, which is necessary to colorize the output and to count the
351 * matches.  The matching lines are passed to printline() to display the
352 * appropriate output.
353 */
354static int
355procline(struct parsec *pc)
356{
357	regmatch_t pmatch, lastmatch, chkmatch;
358	wchar_t wbegin, wend;
359	size_t st = 0, nst = 0;
360	unsigned int i;
361	int c = 0, r = 0, lastmatches = 0, leflags = eflags;
362	size_t startm = 0, matchidx;
363	int retry;
364
365	matchidx = pc->matchidx;
366
367	/* Special case: empty pattern with -w flag, check first character */
368	if (matchall && wflag) {
369		if (pc->ln.len == 0)
370			return (0);
371		wend = L' ';
372		if (sscanf(&pc->ln.dat[0], "%lc", &wend) != 1 || iswword(wend))
373			return (1);
374		else
375			return (0);
376	} else if (matchall)
377		return (0);
378
379	/* Initialize to avoid a false positive warning from GCC. */
380	lastmatch.rm_so = lastmatch.rm_eo = 0;
381
382	/* Loop to process the whole line */
383	while (st <= pc->ln.len) {
384		lastmatches = 0;
385		startm = matchidx;
386		retry = 0;
387		if (st > 0)
388			leflags |= REG_NOTBOL;
389		/* Loop to compare with all the patterns */
390		for (i = 0; i < patterns; i++) {
391			pmatch.rm_so = st;
392			pmatch.rm_eo = pc->ln.len;
393#ifndef WITHOUT_FASTMATCH
394			if (fg_pattern[i].pattern)
395				r = fastexec(&fg_pattern[i],
396				    pc->ln.dat, 1, &pmatch, leflags);
397			else
398#endif
399				r = regexec(&r_pattern[i], pc->ln.dat, 1,
400				    &pmatch, leflags);
401			if (r != 0)
402				continue;
403			/* Check for full match */
404			if (xflag && (pmatch.rm_so != 0 ||
405			    (size_t)pmatch.rm_eo != pc->ln.len))
406				continue;
407			/* Check for whole word match */
408#ifndef WITHOUT_FASTMATCH
409			if (wflag || fg_pattern[i].word) {
410#else
411			if (wflag) {
412#endif
413				wbegin = wend = L' ';
414				if (pmatch.rm_so != 0 &&
415				    sscanf(&pc->ln.dat[pmatch.rm_so - 1],
416				    "%lc", &wbegin) != 1)
417					r = REG_NOMATCH;
418				else if ((size_t)pmatch.rm_eo !=
419				    pc->ln.len &&
420				    sscanf(&pc->ln.dat[pmatch.rm_eo],
421				    "%lc", &wend) != 1)
422					r = REG_NOMATCH;
423				else if (iswword(wbegin) ||
424				    iswword(wend))
425					r = REG_NOMATCH;
426				/*
427				 * If we're doing whole word matching and we
428				 * matched once, then we should try the pattern
429				 * again after advancing just past the start of
430				 * the earliest match. This allows the pattern
431				 * to  match later on in the line and possibly
432				 * still match a whole word.
433				 */
434				if (r == REG_NOMATCH &&
435				    (retry == 0 || pmatch.rm_so + 1 < retry))
436					retry = pmatch.rm_so + 1;
437				if (r == REG_NOMATCH)
438					continue;
439			}
440
441			lastmatches++;
442			lastmatch = pmatch;
443
444			if (matchidx == 0)
445				c++;
446
447			/*
448			 * Replace previous match if the new one is earlier
449			 * and/or longer. This will lead to some amount of
450			 * extra work if -o/--color are specified, but it's
451			 * worth it from a correctness point of view.
452			 */
453			if (matchidx > startm) {
454				chkmatch = pc->matches[matchidx - 1];
455				if (pmatch.rm_so < chkmatch.rm_so ||
456				    (pmatch.rm_so == chkmatch.rm_so &&
457				    (pmatch.rm_eo - pmatch.rm_so) >
458				    (chkmatch.rm_eo - chkmatch.rm_so))) {
459					pc->matches[matchidx - 1] = pmatch;
460					nst = pmatch.rm_eo;
461				}
462			} else {
463				/* Advance as normal if not */
464				pc->matches[matchidx++] = pmatch;
465				nst = pmatch.rm_eo;
466			}
467			/* avoid excessive matching - skip further patterns */
468			if ((color == NULL && !oflag) || qflag || lflag ||
469			    matchidx >= MAX_LINE_MATCHES)
470				break;
471		}
472
473		/*
474		 * Advance to just past the start of the earliest match, try
475		 * again just in case we still have a chance to match later in
476		 * the string.
477		 */
478		if (lastmatches == 0 && retry > 0) {
479			st = retry;
480			continue;
481		}
482
483		/* One pass if we are not recording matches */
484		if (!wflag && ((color == NULL && !oflag) || qflag || lflag || Lflag))
485			break;
486
487		/* If we didn't have any matches or REG_NOSUB set */
488		if (lastmatches == 0 || (cflags & REG_NOSUB))
489			nst = pc->ln.len;
490
491		if (lastmatches == 0)
492			/* No matches */
493			break;
494		else if (st == nst && lastmatch.rm_so == lastmatch.rm_eo)
495			/* Zero-length match -- advance one more so we don't get stuck */
496			nst++;
497
498		/* Advance st based on previous matches */
499		st = nst;
500	}
501
502	/* Reflect the new matchidx in the context */
503	pc->matchidx = matchidx;
504	if (vflag)
505		c = !c;
506	return (c ? 0 : 1);
507}
508
509/*
510 * Safe malloc() for internal use.
511 */
512void *
513grep_malloc(size_t size)
514{
515	void *ptr;
516
517	if ((ptr = malloc(size)) == NULL)
518		err(2, "malloc");
519	return (ptr);
520}
521
522/*
523 * Safe calloc() for internal use.
524 */
525void *
526grep_calloc(size_t nmemb, size_t size)
527{
528	void *ptr;
529
530	if ((ptr = calloc(nmemb, size)) == NULL)
531		err(2, "calloc");
532	return (ptr);
533}
534
535/*
536 * Safe realloc() for internal use.
537 */
538void *
539grep_realloc(void *ptr, size_t size)
540{
541
542	if ((ptr = realloc(ptr, size)) == NULL)
543		err(2, "realloc");
544	return (ptr);
545}
546
547/*
548 * Safe strdup() for internal use.
549 */
550char *
551grep_strdup(const char *str)
552{
553	char *ret;
554
555	if ((ret = strdup(str)) == NULL)
556		err(2, "strdup");
557	return (ret);
558}
559
560/*
561 * Print an entire line as-is, there are no inline matches to consider. This is
562 * used for printing context.
563 */
564void grep_printline(struct str *line, int sep) {
565	printline_metadata(line, sep);
566	fwrite(line->dat, line->len, 1, stdout);
567	putchar(fileeol);
568}
569
570static void
571printline_metadata(struct str *line, int sep)
572{
573	bool printsep;
574
575	printsep = false;
576	if (!hflag) {
577		if (!nullflag) {
578			fputs(line->file, stdout);
579			printsep = true;
580		} else {
581			printf("%s", line->file);
582			putchar(0);
583		}
584	}
585	if (nflag) {
586		if (printsep)
587			putchar(sep);
588		printf("%d", line->line_no);
589		printsep = true;
590	}
591	if (bflag) {
592		if (printsep)
593			putchar(sep);
594		printf("%lld", (long long)line->off);
595		printsep = true;
596	}
597	if (printsep)
598		putchar(sep);
599}
600
601/*
602 * Prints a matching line according to the command line options.
603 */
604static void
605printline(struct parsec *pc, int sep)
606{
607	size_t a = 0;
608	size_t i, matchidx;
609	regmatch_t match;
610
611	/* If matchall, everything matches but don't actually print for -o */
612	if (oflag && matchall)
613		return;
614
615	matchidx = pc->matchidx;
616
617	/* --color and -o */
618	if ((oflag || color) && matchidx > 0) {
619		printline_metadata(&pc->ln, sep);
620		for (i = 0; i < matchidx; i++) {
621			match = pc->matches[i];
622			/* Don't output zero length matches */
623			if (match.rm_so == match.rm_eo)
624				continue;
625			if (!oflag)
626				fwrite(pc->ln.dat + a, match.rm_so - a, 1,
627				    stdout);
628			if (color)
629				fprintf(stdout, "\33[%sm\33[K", color);
630			fwrite(pc->ln.dat + match.rm_so,
631			    match.rm_eo - match.rm_so, 1, stdout);
632			if (color)
633				fprintf(stdout, "\33[m\33[K");
634			a = match.rm_eo;
635			if (oflag)
636				putchar('\n');
637		}
638		if (!oflag) {
639			if (pc->ln.len - a > 0)
640				fwrite(pc->ln.dat + a, pc->ln.len - a, 1,
641				    stdout);
642			putchar('\n');
643		}
644	} else
645		grep_printline(&pc->ln, sep);
646}
647