xref: /openbsd/usr.bin/grep/util.c (revision 905646f0) 
1 /*	$OpenBSD: util.c,v 1.63 2020/07/23 20:19:27 martijn Exp $	*/
2 
3 /*-
4  * Copyright (c) 1999 James Howard and Dag-Erling Co�dan Sm�rgrav
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26  * SUCH DAMAGE.
27  */
28 
29 #include <sys/types.h>
30 #include <sys/stat.h>
31 
32 #include <ctype.h>
33 #include <err.h>
34 #include <errno.h>
35 #include <fts.h>
36 #include <regex.h>
37 #include <stdbool.h>
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <string.h>
41 #include <unistd.h>
42 #include <zlib.h>
43 
44 #include "grep.h"
45 
46 /*
47  * Process a file line by line...
48  */
49 
50 static int	linesqueued;
51 static int	procline(str_t *l, int);
52 static int	grep_search(fastgrep_t *, char *, size_t, regmatch_t *pmatch, int);
53 #ifndef SMALL
54 static bool	grep_cmp(const char *, const char *, size_t);
55 static void	grep_revstr(unsigned char *, int);
56 #endif
57 
58 int
59 grep_tree(char **argv)
60 {
61 	FTS	*fts;
62 	FTSENT	*p;
63 	int	c, fts_flags;
64 	char	*dot_argv[] = { ".", NULL };
65 	char	*path;
66 
67 	/* default to . if no path given */
68 	if (argv[0] == NULL)
69 		argv = dot_argv;
70 
71 	c = 0;
72 
73 	fts_flags = FTS_PHYSICAL | FTS_NOSTAT | FTS_NOCHDIR;
74 
75 	if (!(fts = fts_open(argv, fts_flags, NULL)))
76 		err(2, NULL);
77 	while ((p = fts_read(fts)) != NULL) {
78 		switch (p->fts_info) {
79 		case FTS_DNR:
80 			break;
81 		case FTS_ERR:
82 			file_err = 1;
83 			if(!sflag)
84 				warnc(p->fts_errno, "%s", p->fts_path);
85 			break;
86 		case FTS_D:
87 		case FTS_DP:
88 			break;
89 		default:
90 			path = p->fts_path;
91 			/* skip "./" if implied */
92 			if (argv == dot_argv && p->fts_pathlen >= 2)
93 				path += 2;
94 			c |= procfile(path);
95 			break;
96 		}
97 	}
98 	if (errno)
99 		err(2, "fts_read");
100 	fts_close(fts);
101 	return c;
102 }
103 
104 int
105 procfile(char *fn)
106 {
107 	str_t ln;
108 	file_t *f;
109 	int t, z, nottext, overflow = 0;
110 	unsigned long long c;
111 
112 	mcount = mlimit;
113 
114 	if (fn == NULL) {
115 		fn = "(standard input)";
116 		f = grep_fdopen(STDIN_FILENO);
117 	} else {
118 		f = grep_open(fn);
119 	}
120 	if (f == NULL) {
121 		if (errno == EISDIR)
122 			return 0;
123 		file_err = 1;
124 		if (!sflag)
125 			warn("%s", fn);
126 		return 0;
127 	}
128 
129 	nottext = grep_bin_file(f);
130 	if (nottext && binbehave == BIN_FILE_SKIP) {
131 		grep_close(f);
132 		return 0;
133 	}
134 
135 	ln.file = fn;
136 	if (labelname)
137 		ln.file = (char *)labelname;
138 	ln.line_no = 0;
139 	ln.len = 0;
140 	linesqueued = 0;
141 	tail = 0;
142 	ln.off = -1;
143 
144 	if (Bflag > 0)
145 		initqueue();
146 	for (c = 0;  c == 0 || !(lflag || qflag); ) {
147 		if (mflag && mlimit == 0)
148 			break;
149 		ln.off += ln.len + 1;
150 		if ((ln.dat = grep_fgetln(f, &ln.len)) == NULL)
151 			break;
152 		if (ln.len > 0 && ln.dat[ln.len - 1] == '\n')
153 			--ln.len;
154 		ln.line_no++;
155 
156 		z = tail;
157 
158 		if ((t = procline(&ln, nottext)) == 0 && Bflag > 0 && z == 0) {
159 			enqueue(&ln);
160 			linesqueued++;
161 		}
162 		if (ULLONG_MAX - c < (unsigned long long)t)
163 			overflow = 1;
164 		else
165 			c += t;
166 		if (mflag && mcount <= 0)
167 			break;
168 	}
169 	if (Bflag > 0)
170 		clearqueue();
171 	grep_close(f);
172 
173 	if (cflag) {
174 		if (!hflag)
175 			printf("%s:", ln.file);
176 		printf("%llu%s\n", c, overflow ? "+" : "");
177 	}
178 	if (lflag && c != 0)
179 		printf("%s\n", fn);
180 	if (Lflag && c == 0)
181 		printf("%s\n", fn);
182 	if (c && !cflag && !lflag && !Lflag &&
183 	    binbehave == BIN_FILE_BIN && nottext && !qflag)
184 		printf("Binary file %s matches\n", fn);
185 
186 	return overflow || c != 0;
187 }
188 
189 
190 /*
191  * Process an individual line in a file. Return non-zero if it matches.
192  */
193 
194 #define isword(x) (isalnum((unsigned char)x) || (x) == '_')
195 
196 static int
197 procline(str_t *l, int nottext)
198 {
199 	regmatch_t	pmatch = { 0 };
200 	int		c, i, r;
201 	regoff_t	offset;
202 
203 	/* size_t will be converted to regoff_t. ssize_t is guaranteed to fit
204 	 * into regoff_t */
205 	if (l->len > SSIZE_MAX) {
206 		errx(2, "Line is too big to process");
207 	}
208 
209 	c = 0;
210 	i = 0;
211 	if (matchall) {
212 		c = 1;
213 		goto print;
214 	}
215 
216 	for (i = 0; i < patterns; i++) {
217 		offset = 0;
218 redo:
219 		if (fg_pattern[i].pattern) {
220 			int flags = 0;
221 			if (offset)
222 				flags |= REG_NOTBOL;
223 			r = grep_search(&fg_pattern[i], l->dat + offset,
224 			    l->len - offset, &pmatch, flags);
225 			pmatch.rm_so += offset;
226 			pmatch.rm_eo += offset;
227 		} else {
228 			int flags = eflags;
229 			if (offset)
230 				flags |= REG_NOTBOL;
231 			pmatch.rm_so = offset;
232 			pmatch.rm_eo = l->len;
233 			r = regexec(&r_pattern[i], l->dat, 1, &pmatch, flags);
234 		}
235 		if (r == 0 && xflag) {
236 			if (pmatch.rm_so != 0 || pmatch.rm_eo != l->len)
237 				r = REG_NOMATCH;
238 		}
239 		if (r == 0) {
240 			c = 1;
241 			if (oflag && pmatch.rm_so != pmatch.rm_eo)
242 				goto print;
243 			break;
244 		}
245 	}
246 	if (oflag)
247 		return c;
248 print:
249 	if (vflag)
250 		c = !c;
251 
252 	/* Count the matches if we have a match limit */
253 	if (mflag)
254 		mcount -= c;
255 
256 	if (c && binbehave == BIN_FILE_BIN && nottext)
257 		return c; /* Binary file */
258 
259 	if ((tail > 0 || c) && !cflag && !qflag) {
260 		if (c) {
261 			if (first > 0 && tail == 0 && (Bflag < linesqueued) &&
262 			    (Aflag || Bflag))
263 				printf("--\n");
264 			first = 1;
265 			tail = Aflag;
266 			if (Bflag > 0)
267 				printqueue();
268 			linesqueued = 0;
269 			printline(l, ':', oflag ? &pmatch : NULL);
270 		} else {
271 			printline(l, '-', oflag ? &pmatch : NULL);
272 			tail--;
273 		}
274 	}
275 	if (oflag && !matchall) {
276 		offset = pmatch.rm_eo;
277 		goto redo;
278 	}
279 	return c;
280 }
281 
282 #ifndef SMALL
283 void
284 fgrepcomp(fastgrep_t *fg, const unsigned char *pattern)
285 {
286 	int i;
287 
288 	/* Initialize. */
289 	fg->patternLen = strlen(pattern);
290 	fg->bol = 0;
291 	fg->eol = 0;
292 	fg->wmatch = wflag;
293 	fg->reversedSearch = 0;
294 
295 	/*
296 	 * Make a copy and upper case it for later if in -i mode,
297 	 * else just copy the pointer.
298 	 */
299 	if (iflag) {
300 		fg->pattern = grep_malloc(fg->patternLen + 1);
301 		for (i = 0; i < fg->patternLen; i++)
302 			fg->pattern[i] = toupper(pattern[i]);
303 		fg->pattern[fg->patternLen] = '\0';
304 	} else
305 		fg->pattern = (unsigned char *)pattern;	/* really const */
306 
307 	/* Preprocess pattern. */
308 	for (i = 0; i <= UCHAR_MAX; i++)
309 		fg->qsBc[i] = fg->patternLen;
310 	for (i = 1; i < fg->patternLen; i++) {
311 		fg->qsBc[fg->pattern[i]] = fg->patternLen - i;
312 		/*
313 		 * If case is ignored, make the jump apply to both upper and
314 		 * lower cased characters.  As the pattern is stored in upper
315 		 * case, apply the same to the lower case equivalents.
316 		 */
317 		if (iflag)
318 			fg->qsBc[tolower(fg->pattern[i])] = fg->patternLen - i;
319 	}
320 }
321 #endif
322 
323 /*
324  * Returns: -1 on failure, 0 on success
325  */
326 int
327 fastcomp(fastgrep_t *fg, const char *pattern)
328 {
329 #ifdef SMALL
330 	return -1;
331 #else
332 	int i;
333 	int bol = 0;
334 	int eol = 0;
335 	int shiftPatternLen;
336 	int hasDot = 0;
337 	int firstHalfDot = -1;
338 	int firstLastHalfDot = -1;
339 	int lastHalfDot = 0;
340 
341 	/* Initialize. */
342 	fg->patternLen = strlen(pattern);
343 	fg->bol = 0;
344 	fg->eol = 0;
345 	fg->wmatch = 0;
346 	fg->reversedSearch = 0;
347 
348 	/* Remove end-of-line character ('$'). */
349 	if (fg->patternLen > 0 && pattern[fg->patternLen - 1] == '$') {
350 		eol++;
351 		fg->eol = 1;
352 		fg->patternLen--;
353 	}
354 
355 	/* Remove beginning-of-line character ('^'). */
356 	if (pattern[0] == '^') {
357 		bol++;
358 		fg->bol = 1;
359 		fg->patternLen--;
360 	}
361 
362 	/* Remove enclosing [[:<:]] and [[:>:]] (word match). */
363 	if (wflag) {
364 		/* basic re's use \( \), extended re's ( ) */
365 		int extra = Eflag ? 1 : 2;
366 		fg->patternLen -= 14 + 2 * extra;
367 		fg->wmatch = 7 + extra;
368 	} else if (fg->patternLen >= 14 &&
369 	    strncmp(pattern + fg->bol, "[[:<:]]", 7) == 0 &&
370 	    strncmp(pattern + fg->bol + fg->patternLen - 7, "[[:>:]]", 7) == 0) {
371 		fg->patternLen -= 14;
372 		fg->wmatch = 7;
373 	}
374 
375 	/*
376 	 * Copy pattern minus '^' and '$' characters as well as word
377 	 * match character classes at the beginning and ending of the
378 	 * string respectively.
379 	 */
380 	fg->pattern = grep_malloc(fg->patternLen + 1);
381 	memcpy(fg->pattern, pattern + bol + fg->wmatch, fg->patternLen);
382 	fg->pattern[fg->patternLen] = '\0';
383 
384 	/* Look for ways to cheat...er...avoid the full regex engine. */
385 	for (i = 0; i < fg->patternLen; i++)
386 	{
387 		switch (fg->pattern[i]) {
388 		case '.':
389 			hasDot = i;
390 			if (i < fg->patternLen / 2) {
391 				if (firstHalfDot < 0)
392 					/* Closest dot to the beginning */
393 					firstHalfDot = i;
394 			} else {
395 				/* Closest dot to the end of the pattern. */
396 				lastHalfDot = i;
397 				if (firstLastHalfDot < 0)
398 					firstLastHalfDot = i;
399 			}
400 			break;
401 		case '(': case ')':
402 		case '{': case '}':
403 			/* Special in BRE if preceded by '\\' */
404 		case '?':
405 		case '+':
406 		case '|':
407 			/* Not special in BRE. */
408 			if (!Eflag)
409 				goto nonspecial;
410 		case '\\':
411 		case '*':
412 		case '[': case ']':
413 			/* Free memory and let others know this is empty. */
414 			free(fg->pattern);
415 			fg->pattern = NULL;
416 			return (-1);
417 		default:
418 nonspecial:
419 			if (iflag)
420 				fg->pattern[i] = toupper(fg->pattern[i]);
421 			break;
422 		}
423 	}
424 
425 	/*
426 	 * Determine if a reverse search would be faster based on the placement
427 	 * of the dots.
428 	 */
429 	if ((!(lflag || cflag || oflag)) && ((!(bol || eol)) &&
430 	    ((lastHalfDot) && ((firstHalfDot < 0) ||
431 	    ((fg->patternLen - (lastHalfDot + 1)) < firstHalfDot))))) {
432 		fg->reversedSearch = 1;
433 		hasDot = fg->patternLen - (firstHalfDot < 0 ?
434 		    firstLastHalfDot : firstHalfDot) - 1;
435 		grep_revstr(fg->pattern, fg->patternLen);
436 	}
437 
438 	/*
439 	 * Normal Quick Search would require a shift based on the position the
440 	 * next character after the comparison is within the pattern.  With
441 	 * wildcards, the position of the last dot effects the maximum shift
442 	 * distance.
443 	 * The closer to the end the wild card is the slower the search.  A
444 	 * reverse version of this algorithm would be useful for wildcards near
445 	 * the end of the string.
446 	 *
447 	 * Examples:
448 	 * Pattern	Max shift
449 	 * -------	---------
450 	 * this		5
451 	 * .his		4
452 	 * t.is		3
453 	 * th.s		2
454 	 * thi.		1
455 	 */
456 
457 	/* Adjust the shift based on location of the last dot ('.'). */
458 	shiftPatternLen = fg->patternLen - hasDot;
459 
460 	/* Preprocess pattern. */
461 	for (i = 0; i <= UCHAR_MAX; i++)
462 		fg->qsBc[i] = shiftPatternLen;
463 	for (i = hasDot + 1; i < fg->patternLen; i++) {
464 		fg->qsBc[fg->pattern[i]] = fg->patternLen - i;
465 		/*
466 		 * If case is ignored, make the jump apply to both upper and
467 		 * lower cased characters.  As the pattern is stored in upper
468 		 * case, apply the same to the lower case equivalents.
469 		 */
470 		if (iflag)
471 			fg->qsBc[tolower(fg->pattern[i])] = fg->patternLen - i;
472 	}
473 
474 	/*
475 	 * Put pattern back to normal after pre-processing to allow for easy
476 	 * comparisons later.
477 	 */
478 	if (fg->reversedSearch)
479 		grep_revstr(fg->pattern, fg->patternLen);
480 
481 	return (0);
482 #endif
483 }
484 
485 /*
486  * Word boundaries using regular expressions are defined as the point
487  * of transition from a non-word char to a word char, or vice versa.
488  * This means that grep -w +a and grep -w a+ never match anything,
489  * because they lack a starting or ending transition, but grep -w a+b
490  * does match a line containing a+b.
491  */
492 #define wmatch(d, l, s, e)	\
493 	((s == 0 || !isword(d[s-1])) && (e == l || !isword(d[e])) && \
494 	  e > s && isword(d[s]) && isword(d[e-1]))
495 
496 static int
497 grep_search(fastgrep_t *fg, char *data, size_t dataLen, regmatch_t *pmatch,
498     int flags)
499 {
500 #ifdef SMALL
501 	return 0;
502 #else
503 	regoff_t j;
504 	int rtrnVal = REG_NOMATCH;
505 
506 	pmatch->rm_so = -1;
507 	pmatch->rm_eo = -1;
508 
509 	/* No point in going farther if we do not have enough data. */
510 	if (dataLen < fg->patternLen)
511 		return (rtrnVal);
512 
513 	/* Only try once at the beginning or ending of the line. */
514 	if (fg->bol || fg->eol) {
515 		if (fg->bol && (flags & REG_NOTBOL))
516 			return 0;
517 		/* Simple text comparison. */
518 		/* Verify data is >= pattern length before searching on it. */
519 		if (dataLen >= fg->patternLen) {
520 			/* Determine where in data to start search at. */
521 			if (fg->eol)
522 				j = dataLen - fg->patternLen;
523 			else
524 				j = 0;
525 			if (!((fg->bol && fg->eol) && (dataLen != fg->patternLen)))
526 				if (grep_cmp(fg->pattern, data + j,
527 				    fg->patternLen)) {
528 					pmatch->rm_so = j;
529 					pmatch->rm_eo = j + fg->patternLen;
530 					if (!fg->wmatch || wmatch(data, dataLen,
531 					    pmatch->rm_so, pmatch->rm_eo))
532 						rtrnVal = 0;
533 				}
534 		}
535 	} else if (fg->reversedSearch) {
536 		/* Quick Search algorithm. */
537 		j = dataLen;
538 		do {
539 			if (grep_cmp(fg->pattern, data + j - fg->patternLen,
540 			    fg->patternLen)) {
541 				pmatch->rm_so = j - fg->patternLen;
542 				pmatch->rm_eo = j;
543 				if (!fg->wmatch || wmatch(data, dataLen,
544 				    pmatch->rm_so, pmatch->rm_eo)) {
545 					rtrnVal = 0;
546 					break;
547 				}
548 			}
549 			/* Shift if within bounds, otherwise, we are done. */
550 			if (j == fg->patternLen)
551 				break;
552 			j -= fg->qsBc[(unsigned char)data[j - fg->patternLen - 1]];
553 		} while (j >= fg->patternLen);
554 	} else {
555 		/* Quick Search algorithm. */
556 		j = 0;
557 		do {
558 			if (grep_cmp(fg->pattern, data + j, fg->patternLen)) {
559 				pmatch->rm_so = j;
560 				pmatch->rm_eo = j + fg->patternLen;
561 				if (fg->patternLen == 0 || !fg->wmatch ||
562 				    wmatch(data, dataLen, pmatch->rm_so,
563 				    pmatch->rm_eo)) {
564 					rtrnVal = 0;
565 					break;
566 				}
567 			}
568 
569 			/* Shift if within bounds, otherwise, we are done. */
570 			if (j + fg->patternLen == dataLen)
571 				break;
572 			else
573 				j += fg->qsBc[(unsigned char)data[j + fg->patternLen]];
574 		} while (j <= (dataLen - fg->patternLen));
575 	}
576 
577 	return (rtrnVal);
578 #endif
579 }
580 
581 
582 void *
583 grep_malloc(size_t size)
584 {
585 	void	*ptr;
586 
587 	if ((ptr = malloc(size)) == NULL)
588 		err(2, "malloc");
589 	return ptr;
590 }
591 
592 void *
593 grep_calloc(size_t nmemb, size_t size)
594 {
595 	void	*ptr;
596 
597 	if ((ptr = calloc(nmemb, size)) == NULL)
598 		err(2, "calloc");
599 	return ptr;
600 }
601 
602 void *
603 grep_realloc(void *ptr, size_t size)
604 {
605 	if ((ptr = realloc(ptr, size)) == NULL)
606 		err(2, "realloc");
607 	return ptr;
608 }
609 
610 void *
611 grep_reallocarray(void *ptr, size_t nmemb, size_t size)
612 {
613 	if ((ptr = reallocarray(ptr, nmemb, size)) == NULL)
614 		err(2, "reallocarray");
615 	return ptr;
616 }
617 
618 #ifndef SMALL
619 /*
620  * Returns:	true on success, false on failure
621  */
622 static bool
623 grep_cmp(const char *pattern, const char *data, size_t len)
624 {
625 	size_t i;
626 
627 	for (i = 0; i < len; i++) {
628 		if (((pattern[i] == data[i]) || (!Fflag && pattern[i] == '.'))
629 		    || (iflag && pattern[i] == toupper((unsigned char)data[i])))
630 			continue;
631 		return false;
632 	}
633 
634 	return true;
635 }
636 
637 static void
638 grep_revstr(unsigned char *str, int len)
639 {
640 	int i;
641 	char c;
642 
643 	for (i = 0; i < len / 2; i++) {
644 		c = str[i];
645 		str[i] = str[len - i - 1];
646 		str[len - i - 1] = c;
647 	}
648 }
649 #endif
650 
651 void
652 printline(str_t *line, int sep, regmatch_t *pmatch)
653 {
654 	int n;
655 
656 	n = 0;
657 	if (!hflag) {
658 		fputs(line->file, stdout);
659 		++n;
660 	}
661 	if (nflag) {
662 		if (n)
663 			putchar(sep);
664 		printf("%lld", line->line_no);
665 		++n;
666 	}
667 	if (bflag) {
668 		if (n)
669 			putchar(sep);
670 		printf("%lld", (long long)line->off +
671 		    (pmatch ? pmatch->rm_so : 0));
672 		++n;
673 	}
674 	if (n)
675 		putchar(sep);
676 	if (pmatch)
677 		fwrite(line->dat + pmatch->rm_so,
678 		    pmatch->rm_eo - pmatch->rm_so, 1, stdout);
679 	else
680 		fwrite(line->dat, line->len, 1, stdout);
681 	putchar('\n');
682 }
683