xref: /openbsd-src/usr.bin/grep/util.c (revision 25c4e8bd056e974b28f4a0ffd39d76c190a56013) 
1 /*	$OpenBSD: util.c,v 1.67 2022/07/12 18:09:31 op 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 && tail <= 0)
167 			break;
168 	}
169 	if (Bflag > 0)
170 		clearqueue();
171 	grep_close(f);
172 
173 	if (cflag) {
174 		if (!hflag)
175 			printf("%s%c", ln.file, nullflag ? '\0' : ':');
176 		printf("%llu%s\n", c, overflow ? "+" : "");
177 	}
178 	if (lflag && c != 0)
179 		printf("%s%c", fn, nullflag ? '\0' : '\n');
180 	if (Lflag && c == 0)
181 		printf("%s%c", fn, nullflag ? '\0' : '\n');
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 	if (mflag && mcount <= 0)
216 		goto print;
217 
218 	for (i = 0; i < patterns; i++) {
219 		offset = 0;
220 redo:
221 		if (fg_pattern[i].pattern) {
222 			int flags = 0;
223 			if (offset)
224 				flags |= REG_NOTBOL;
225 			r = grep_search(&fg_pattern[i], l->dat + offset,
226 			    l->len - offset, &pmatch, flags);
227 			pmatch.rm_so += offset;
228 			pmatch.rm_eo += offset;
229 		} else {
230 			int flags = eflags;
231 			if (offset)
232 				flags |= REG_NOTBOL;
233 			pmatch.rm_so = offset;
234 			pmatch.rm_eo = l->len;
235 			r = regexec(&r_pattern[i], l->dat, 1, &pmatch, flags);
236 		}
237 		if (r == 0 && xflag) {
238 			if (pmatch.rm_so != 0 || pmatch.rm_eo != l->len)
239 				r = REG_NOMATCH;
240 		}
241 		if (r == 0) {
242 			c = 1;
243 			if (oflag && pmatch.rm_so != pmatch.rm_eo)
244 				goto print;
245 			break;
246 		}
247 	}
248 	if (oflag)
249 		return c;
250 print:
251 	if (vflag)
252 		c = !c;
253 
254 	/* Count the matches if we have a match limit */
255 	if (mflag)
256 		mcount -= c;
257 
258 	if (c && binbehave == BIN_FILE_BIN && nottext)
259 		return c; /* Binary file */
260 
261 	if ((tail > 0 || c) && !cflag && !qflag) {
262 		if (c) {
263 			if (first > 0 && tail == 0 && (Aflag || (Bflag &&
264 			    Bflag < linesqueued)))
265 				printf("--\n");
266 			first = 1;
267 			tail = Aflag;
268 			if (Bflag > 0)
269 				printqueue();
270 			linesqueued = 0;
271 			printline(l, ':', oflag ? &pmatch : NULL);
272 		} else {
273 			printline(l, '-', oflag ? &pmatch : NULL);
274 			tail--;
275 		}
276 	}
277 	if (oflag && !matchall) {
278 		offset = pmatch.rm_eo;
279 		goto redo;
280 	}
281 	return c;
282 }
283 
284 #ifndef SMALL
285 void
286 fgrepcomp(fastgrep_t *fg, const unsigned char *pattern)
287 {
288 	int i;
289 
290 	/* Initialize. */
291 	fg->patternLen = strlen(pattern);
292 	fg->bol = 0;
293 	fg->eol = 0;
294 	fg->wmatch = wflag;
295 	fg->reversedSearch = 0;
296 
297 	/*
298 	 * Make a copy and upper case it for later if in -i mode,
299 	 * else just copy the pointer.
300 	 */
301 	if (iflag) {
302 		fg->pattern = grep_malloc(fg->patternLen + 1);
303 		for (i = 0; i < fg->patternLen; i++)
304 			fg->pattern[i] = toupper(pattern[i]);
305 		fg->pattern[fg->patternLen] = '\0';
306 	} else
307 		fg->pattern = (unsigned char *)pattern;	/* really const */
308 
309 	/* Preprocess pattern. */
310 	for (i = 0; i <= UCHAR_MAX; i++)
311 		fg->qsBc[i] = fg->patternLen;
312 	for (i = 1; i < fg->patternLen; i++) {
313 		fg->qsBc[fg->pattern[i]] = fg->patternLen - i;
314 		/*
315 		 * If case is ignored, make the jump apply to both upper and
316 		 * lower cased characters.  As the pattern is stored in upper
317 		 * case, apply the same to the lower case equivalents.
318 		 */
319 		if (iflag)
320 			fg->qsBc[tolower(fg->pattern[i])] = fg->patternLen - i;
321 	}
322 }
323 #endif
324 
325 /*
326  * Returns: -1 on failure, 0 on success
327  */
328 int
329 fastcomp(fastgrep_t *fg, const char *pattern)
330 {
331 #ifdef SMALL
332 	return -1;
333 #else
334 	int i;
335 	int bol = 0;
336 	int eol = 0;
337 	int shiftPatternLen;
338 	int hasDot = 0;
339 	int firstHalfDot = -1;
340 	int firstLastHalfDot = -1;
341 	int lastHalfDot = 0;
342 
343 	/* Initialize. */
344 	fg->patternLen = strlen(pattern);
345 	fg->bol = 0;
346 	fg->eol = 0;
347 	fg->wmatch = 0;
348 	fg->reversedSearch = 0;
349 
350 	/* Remove end-of-line character ('$'). */
351 	if (fg->patternLen > 0 && pattern[fg->patternLen - 1] == '$') {
352 		eol++;
353 		fg->eol = 1;
354 		fg->patternLen--;
355 	}
356 
357 	/* Remove beginning-of-line character ('^'). */
358 	if (pattern[0] == '^') {
359 		bol++;
360 		fg->bol = 1;
361 		fg->patternLen--;
362 	}
363 
364 	/* Remove enclosing [[:<:]] and [[:>:]] (word match). */
365 	if (wflag) {
366 		/* basic re's use \( \), extended re's ( ) */
367 		int extra = Eflag ? 1 : 2;
368 		fg->patternLen -= 14 + 2 * extra;
369 		fg->wmatch = 7 + extra;
370 	} else if (fg->patternLen >= 14 &&
371 	    strncmp(pattern + fg->bol, "[[:<:]]", 7) == 0 &&
372 	    strncmp(pattern + fg->bol + fg->patternLen - 7, "[[:>:]]", 7) == 0) {
373 		fg->patternLen -= 14;
374 		fg->wmatch = 7;
375 	}
376 
377 	/*
378 	 * Copy pattern minus '^' and '$' characters as well as word
379 	 * match character classes at the beginning and ending of the
380 	 * string respectively.
381 	 */
382 	fg->pattern = grep_malloc(fg->patternLen + 1);
383 	memcpy(fg->pattern, pattern + bol + fg->wmatch, fg->patternLen);
384 	fg->pattern[fg->patternLen] = '\0';
385 
386 	/* Look for ways to cheat...er...avoid the full regex engine. */
387 	for (i = 0; i < fg->patternLen; i++)
388 	{
389 		switch (fg->pattern[i]) {
390 		case '.':
391 			hasDot = i;
392 			if (i < fg->patternLen / 2) {
393 				if (firstHalfDot < 0)
394 					/* Closest dot to the beginning */
395 					firstHalfDot = i;
396 			} else {
397 				/* Closest dot to the end of the pattern. */
398 				lastHalfDot = i;
399 				if (firstLastHalfDot < 0)
400 					firstLastHalfDot = i;
401 			}
402 			break;
403 		case '(': case ')':
404 		case '{': case '}':
405 			/* Special in BRE if preceded by '\\' */
406 		case '?':
407 		case '+':
408 		case '|':
409 			/* Not special in BRE. */
410 			if (!Eflag)
411 				goto nonspecial;
412 		case '\\':
413 		case '*':
414 		case '[': case ']':
415 			/* Free memory and let others know this is empty. */
416 			free(fg->pattern);
417 			fg->pattern = NULL;
418 			return (-1);
419 		default:
420 nonspecial:
421 			if (iflag)
422 				fg->pattern[i] = toupper(fg->pattern[i]);
423 			break;
424 		}
425 	}
426 
427 	/*
428 	 * Determine if a reverse search would be faster based on the placement
429 	 * of the dots.
430 	 */
431 	if ((!(lflag || cflag || oflag)) && ((!(bol || eol)) &&
432 	    ((lastHalfDot) && ((firstHalfDot < 0) ||
433 	    ((fg->patternLen - (lastHalfDot + 1)) < firstHalfDot))))) {
434 		fg->reversedSearch = 1;
435 		hasDot = fg->patternLen - (firstHalfDot < 0 ?
436 		    firstLastHalfDot : firstHalfDot) - 1;
437 		grep_revstr(fg->pattern, fg->patternLen);
438 	}
439 
440 	/*
441 	 * Normal Quick Search would require a shift based on the position the
442 	 * next character after the comparison is within the pattern.  With
443 	 * wildcards, the position of the last dot effects the maximum shift
444 	 * distance.
445 	 * The closer to the end the wild card is the slower the search.  A
446 	 * reverse version of this algorithm would be useful for wildcards near
447 	 * the end of the string.
448 	 *
449 	 * Examples:
450 	 * Pattern	Max shift
451 	 * -------	---------
452 	 * this		5
453 	 * .his		4
454 	 * t.is		3
455 	 * th.s		2
456 	 * thi.		1
457 	 */
458 
459 	/* Adjust the shift based on location of the last dot ('.'). */
460 	shiftPatternLen = fg->patternLen - hasDot;
461 
462 	/* Preprocess pattern. */
463 	for (i = 0; i <= UCHAR_MAX; i++)
464 		fg->qsBc[i] = shiftPatternLen;
465 	for (i = hasDot + 1; i < fg->patternLen; i++) {
466 		fg->qsBc[fg->pattern[i]] = fg->patternLen - i;
467 		/*
468 		 * If case is ignored, make the jump apply to both upper and
469 		 * lower cased characters.  As the pattern is stored in upper
470 		 * case, apply the same to the lower case equivalents.
471 		 */
472 		if (iflag)
473 			fg->qsBc[tolower(fg->pattern[i])] = fg->patternLen - i;
474 	}
475 
476 	/*
477 	 * Put pattern back to normal after pre-processing to allow for easy
478 	 * comparisons later.
479 	 */
480 	if (fg->reversedSearch)
481 		grep_revstr(fg->pattern, fg->patternLen);
482 
483 	return (0);
484 #endif
485 }
486 
487 /*
488  * Word boundaries using regular expressions are defined as the point
489  * of transition from a non-word char to a word char, or vice versa.
490  * This means that grep -w +a and grep -w a+ never match anything,
491  * because they lack a starting or ending transition, but grep -w a+b
492  * does match a line containing a+b.
493  */
494 #define wmatch(d, l, s, e)	\
495 	((s == 0 || !isword(d[s-1])) && (e == l || !isword(d[e])) && \
496 	  e > s && isword(d[s]) && isword(d[e-1]))
497 
498 static int
499 grep_search(fastgrep_t *fg, char *data, size_t dataLen, regmatch_t *pmatch,
500     int flags)
501 {
502 #ifdef SMALL
503 	return 0;
504 #else
505 	regoff_t j;
506 	int rtrnVal = REG_NOMATCH;
507 
508 	pmatch->rm_so = -1;
509 	pmatch->rm_eo = -1;
510 
511 	/* No point in going farther if we do not have enough data. */
512 	if (dataLen < fg->patternLen)
513 		return (rtrnVal);
514 
515 	/* Only try once at the beginning or ending of the line. */
516 	if (fg->bol || fg->eol) {
517 		if (fg->bol && (flags & REG_NOTBOL))
518 			return 0;
519 		/* Simple text comparison. */
520 		/* Verify data is >= pattern length before searching on it. */
521 		if (dataLen >= fg->patternLen) {
522 			/* Determine where in data to start search at. */
523 			if (fg->eol)
524 				j = dataLen - fg->patternLen;
525 			else
526 				j = 0;
527 			if (!((fg->bol && fg->eol) && (dataLen != fg->patternLen)))
528 				if (grep_cmp(fg->pattern, data + j,
529 				    fg->patternLen)) {
530 					pmatch->rm_so = j;
531 					pmatch->rm_eo = j + fg->patternLen;
532 					if (!fg->wmatch || wmatch(data, dataLen,
533 					    pmatch->rm_so, pmatch->rm_eo))
534 						rtrnVal = 0;
535 				}
536 		}
537 	} else if (fg->reversedSearch) {
538 		/* Quick Search algorithm. */
539 		j = dataLen;
540 		do {
541 			if (grep_cmp(fg->pattern, data + j - fg->patternLen,
542 			    fg->patternLen)) {
543 				pmatch->rm_so = j - fg->patternLen;
544 				pmatch->rm_eo = j;
545 				if (!fg->wmatch || wmatch(data, dataLen,
546 				    pmatch->rm_so, pmatch->rm_eo)) {
547 					rtrnVal = 0;
548 					break;
549 				}
550 			}
551 			/* Shift if within bounds, otherwise, we are done. */
552 			if (j == fg->patternLen)
553 				break;
554 			j -= fg->qsBc[(unsigned char)data[j - fg->patternLen - 1]];
555 		} while (j >= fg->patternLen);
556 	} else {
557 		/* Quick Search algorithm. */
558 		j = 0;
559 		do {
560 			if (grep_cmp(fg->pattern, data + j, fg->patternLen)) {
561 				pmatch->rm_so = j;
562 				pmatch->rm_eo = j + fg->patternLen;
563 				if (fg->patternLen == 0 || !fg->wmatch ||
564 				    wmatch(data, dataLen, pmatch->rm_so,
565 				    pmatch->rm_eo)) {
566 					rtrnVal = 0;
567 					break;
568 				}
569 			}
570 
571 			/* Shift if within bounds, otherwise, we are done. */
572 			if (j + fg->patternLen == dataLen)
573 				break;
574 			else
575 				j += fg->qsBc[(unsigned char)data[j + fg->patternLen]];
576 		} while (j <= (dataLen - fg->patternLen));
577 	}
578 
579 	return (rtrnVal);
580 #endif
581 }
582 
583 
584 void *
585 grep_malloc(size_t size)
586 {
587 	void	*ptr;
588 
589 	if ((ptr = malloc(size)) == NULL)
590 		err(2, "malloc");
591 	return ptr;
592 }
593 
594 void *
595 grep_calloc(size_t nmemb, size_t size)
596 {
597 	void	*ptr;
598 
599 	if ((ptr = calloc(nmemb, size)) == NULL)
600 		err(2, "calloc");
601 	return ptr;
602 }
603 
604 void *
605 grep_realloc(void *ptr, size_t size)
606 {
607 	if ((ptr = realloc(ptr, size)) == NULL)
608 		err(2, "realloc");
609 	return ptr;
610 }
611 
612 void *
613 grep_reallocarray(void *ptr, size_t nmemb, size_t size)
614 {
615 	if ((ptr = reallocarray(ptr, nmemb, size)) == NULL)
616 		err(2, "reallocarray");
617 	return ptr;
618 }
619 
620 #ifndef SMALL
621 /*
622  * Returns:	true on success, false on failure
623  */
624 static bool
625 grep_cmp(const char *pattern, const char *data, size_t len)
626 {
627 	size_t i;
628 
629 	for (i = 0; i < len; i++) {
630 		if (((pattern[i] == data[i]) || (!Fflag && pattern[i] == '.'))
631 		    || (iflag && pattern[i] == toupper((unsigned char)data[i])))
632 			continue;
633 		return false;
634 	}
635 
636 	return true;
637 }
638 
639 static void
640 grep_revstr(unsigned char *str, int len)
641 {
642 	int i;
643 	char c;
644 
645 	for (i = 0; i < len / 2; i++) {
646 		c = str[i];
647 		str[i] = str[len - i - 1];
648 		str[len - i - 1] = c;
649 	}
650 }
651 #endif
652 
653 void
654 printline(str_t *line, int sep, regmatch_t *pmatch)
655 {
656 	int n;
657 
658 	n = 0;
659 	if (!hflag) {
660 		fputs(line->file, stdout);
661 		if (nullflag)
662 			putchar(0);
663 		else
664 			++n;
665 	}
666 	if (nflag) {
667 		if (n)
668 			putchar(sep);
669 		printf("%lld", line->line_no);
670 		++n;
671 	}
672 	if (bflag) {
673 		if (n)
674 			putchar(sep);
675 		printf("%lld", (long long)line->off +
676 		    (pmatch ? pmatch->rm_so : 0));
677 		++n;
678 	}
679 	if (n)
680 		putchar(sep);
681 	if (pmatch)
682 		fwrite(line->dat + pmatch->rm_so,
683 		    pmatch->rm_eo - pmatch->rm_so, 1, stdout);
684 	else
685 		fwrite(line->dat, line->len, 1, stdout);
686 	putchar('\n');
687 }
688