Annotation of src/usr.bin/grep/util.c, Revision 1.23
1.23 ! millert 1: /* $OpenBSD: util.c,v 1.22 2004/01/25 21:36:00 millert Exp $ */
1.3 deraadt 2:
1.1 deraadt 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 <stdio.h>
38: #include <stdlib.h>
39: #include <string.h>
40: #include <unistd.h>
41: #include <zlib.h>
42:
43: #include "grep.h"
44:
45: /*
46: * Process a file line by line...
47: */
48:
49: static int linesqueued;
1.4 tedu 50: static int procline(str_t *l, int);
1.23 ! millert 51: static int grep_search(fastgrep_t *, unsigned char *, size_t, regmatch_t *pmatch);
1.6 tedu 52: static int grep_cmp(const unsigned char *, const unsigned char *, size_t);
53: static void grep_revstr(unsigned char *, int);
1.1 deraadt 54:
1.2 deraadt 55: int
1.1 deraadt 56: grep_tree(char **argv)
57: {
1.10 deraadt 58: FTS *fts;
59: FTSENT *p;
60: int c, fts_flags;
1.1 deraadt 61:
62: c = fts_flags = 0;
63:
64: if (Hflag)
65: fts_flags = FTS_COMFOLLOW;
66: if (Pflag)
67: fts_flags = FTS_PHYSICAL;
68: if (Sflag)
69: fts_flags = FTS_LOGICAL;
70:
71: fts_flags |= FTS_NOSTAT | FTS_NOCHDIR;
72:
1.11 millert 73: if (!(fts = fts_open(argv, fts_flags, NULL)))
1.14 millert 74: err(2, NULL);
1.1 deraadt 75: while ((p = fts_read(fts)) != NULL) {
76: switch (p->fts_info) {
77: case FTS_DNR:
78: break;
79: case FTS_ERR:
1.14 millert 80: errx(2, "%s: %s", p->fts_path, strerror(p->fts_errno));
1.1 deraadt 81: break;
82: case FTS_DP:
83: break;
84: default:
85: c += procfile(p->fts_path);
86: break;
87: }
88: }
89:
90: return c;
91: }
92:
93: int
94: procfile(char *fn)
95: {
96: str_t ln;
97: file_t *f;
1.4 tedu 98: int c, t, z, nottext;
1.1 deraadt 99:
100: if (fn == NULL) {
101: fn = "(standard input)";
102: f = grep_fdopen(STDIN_FILENO, "r");
103: } else {
104: f = grep_open(fn, "r");
105: }
106: if (f == NULL) {
107: if (!sflag)
108: warn("%s", fn);
109: return 0;
110: }
1.4 tedu 111:
112: nottext = grep_bin_file(f);
113: if (nottext && binbehave == BIN_FILE_SKIP) {
1.1 deraadt 114: grep_close(f);
115: return 0;
116: }
117:
118: ln.file = fn;
119: ln.line_no = 0;
1.20 espie 120: ln.len = 0;
1.1 deraadt 121: linesqueued = 0;
122: ln.off = -1;
123:
124: if (Bflag > 0)
125: initqueue();
126: for (c = 0; !(lflag && c);) {
127: ln.off += ln.len + 1;
128: if ((ln.dat = grep_fgetln(f, &ln.len)) == NULL)
129: break;
130: if (ln.len > 0 && ln.dat[ln.len - 1] == '\n')
131: --ln.len;
132: ln.line_no++;
133:
134: z = tail;
1.2 deraadt 135:
1.4 tedu 136: if ((t = procline(&ln, nottext)) == 0 && Bflag > 0 && z == 0) {
1.1 deraadt 137: enqueue(&ln);
138: linesqueued++;
139: }
140: c += t;
141: }
142: if (Bflag > 0)
143: clearqueue();
144: grep_close(f);
145:
146: if (cflag) {
147: if (!hflag)
148: printf("%s:", ln.file);
149: printf("%u\n", c);
150: }
151: if (lflag && c != 0)
152: printf("%s\n", fn);
153: if (Lflag && c == 0)
154: printf("%s\n", fn);
1.4 tedu 155: if (c && !cflag && !lflag && !Lflag &&
1.7 tedu 156: binbehave == BIN_FILE_BIN && nottext && !qflag)
1.4 tedu 157: printf("Binary file %s matches\n", fn);
158:
1.1 deraadt 159: return c;
160: }
161:
162:
163: /*
164: * Process an individual line in a file. Return non-zero if it matches.
165: */
166:
167: #define isword(x) (isalnum(x) || (x) == '_')
168:
169: static int
1.4 tedu 170: procline(str_t *l, int nottext)
1.1 deraadt 171: {
172: regmatch_t pmatch;
1.15 dhartmei 173: int c, i, r;
1.1 deraadt 174:
175: if (matchall) {
176: c = !vflag;
177: goto print;
178: }
1.2 deraadt 179:
1.1 deraadt 180: for (c = i = 0; i < patterns; i++) {
1.22 millert 181: if (fg_pattern[i].pattern) {
1.6 tedu 182: r = grep_search(&fg_pattern[i], (unsigned char *)l->dat,
1.9 millert 183: l->len, &pmatch);
1.22 millert 184: } else {
185: pmatch.rm_so = 0;
186: pmatch.rm_eo = l->len;
1.9 millert 187: r = regexec(&r_pattern[i], l->dat, 1, &pmatch, eflags);
1.22 millert 188: }
189: if (r == 0 && xflag) {
190: if (pmatch.rm_so != 0 || pmatch.rm_eo != l->len)
191: r = REG_NOMATCH;
1.1 deraadt 192: }
1.15 dhartmei 193: if (r == 0) {
1.1 deraadt 194: c++;
195: break;
196: }
197: }
1.15 dhartmei 198: if (vflag)
199: c = !c;
1.2 deraadt 200:
1.1 deraadt 201: print:
1.4 tedu 202: if (c && binbehave == BIN_FILE_BIN && nottext)
203: return c; /* Binary file */
204:
1.1 deraadt 205: if ((tail > 0 || c) && !cflag && !qflag) {
206: if (c) {
1.5 deraadt 207: if (first > 0 && tail == 0 && (Bflag < linesqueued) &&
208: (Aflag || Bflag))
1.1 deraadt 209: printf("--\n");
210: first = 1;
211: tail = Aflag;
212: if (Bflag > 0)
213: printqueue();
214: linesqueued = 0;
215: printline(l, ':');
216: } else {
217: printline(l, '-');
218: tail--;
219: }
220: }
221: return c;
222: }
223:
1.6 tedu 224: /*
1.10 deraadt 225: * Returns: -1 on failure, 0 on success
1.6 tedu 226: */
227: int
228: fastcomp(fastgrep_t *fg, const char *pattern)
229: {
230: int i;
231: int bol = 0;
232: int eol = 0;
233: int origPatternLen;
234: int shiftPatternLen;
235: int hasDot = 0;
236: int firstHalfDot = -1;
237: int firstLastHalfDot = -1;
238: int lastHalfDot = 0;
239:
1.8 tedu 240: if (Fflag) {
241: fg->pattern = NULL;
242: return (-1);
243: }
244:
1.6 tedu 245: /* Initialize. */
246: origPatternLen = fg->patternLen = strlen(pattern);
247: fg->bol = 0;
248: fg->eol = 0;
1.22 millert 249: fg->wmatch = 0;
1.6 tedu 250: fg->reversedSearch = 0;
251:
252: /* Remove end-of-line character ('$'). */
253: if (pattern[fg->patternLen - 1] == '$') {
254: eol++;
255: fg->eol = 1;
256: fg->patternLen--;
257: boleol = 1;
258: }
259:
260: /* Remove beginning-of-line character ('^'). */
261: if (pattern[0] == '^') {
262: bol++;
263: fg->bol = 1;
264: fg->patternLen--;
265: boleol = 1;
266: }
267:
1.22 millert 268: /* Remove enclosing [[:<:]] and [[:>:]] (word match). */
269: if (fg->patternLen > 14 + fg->bol + fg->eol &&
270: strncmp(pattern + fg->bol, "[[:<:]]", 7) == 0 &&
271: strncmp(pattern + fg->patternLen - (7 + fg->eol), "[[:>:]]", 7) == 0) {
272: fg->patternLen -= 14;
273: fg->wmatch = 7;
274: }
275:
1.6 tedu 276: /*
1.22 millert 277: * Copy pattern minus '^' and '$' characters as well as word
278: * match character classes at the beginning and ending of the
279: * string respectively.
1.6 tedu 280: */
1.22 millert 281: fg->pattern = grep_malloc(fg->patternLen + 1);
282: memcpy(fg->pattern, pattern + bol + fg->wmatch, fg->patternLen);
283: fg->pattern[fg->patternLen] = '\0';
1.6 tedu 284:
285: /* Look for ways to cheat...er...avoid the full regex engine. */
286: for (i = 0; i < fg->patternLen; i++)
287: {
288: /* Can still cheat? */
289: if ((isalnum(fg->pattern[i])) || isspace(fg->pattern[i]) ||
290: (fg->pattern[i] == '_') || (fg->pattern[i] == ',') ||
291: (fg->pattern[i] == '^') || (fg->pattern[i] == '$') ||
292: (fg->pattern[i] == '=') || (fg->pattern[i] == '-') ||
293: (fg->pattern[i] == ':') || (fg->pattern[i] == '/')) {
294: /* As long as it is good, upper case it for later. */
295: if (iflag)
296: fg->pattern[i] = toupper(fg->pattern[i]);
297: } else if (fg->pattern[i] == '.') {
298: hasDot = i;
299: if (i < fg->patternLen / 2) {
1.19 otto 300: if (firstHalfDot < 0)
1.6 tedu 301: /* Closest dot to the beginning */
302: firstHalfDot = i;
303: } else {
304: /* Closest dot to the end of the pattern. */
305: lastHalfDot = i;
306: if (firstLastHalfDot < 0)
307: firstLastHalfDot = i;
308: }
309: } else {
310: /* Free memory and let others know this is empty. */
311: free(fg->pattern);
312: fg->pattern = NULL;
313: return (-1);
314: }
315: }
316:
317: /*
318: * Determine if a reverse search would be faster based on the placement
319: * of the dots.
320: */
321: if ((!(lflag || cflag)) && ((!(bol || eol)) &&
322: ((lastHalfDot) && ((firstHalfDot < 0) ||
323: ((fg->patternLen - (lastHalfDot + 1)) < firstHalfDot))))) {
324: fg->reversedSearch = 1;
325: hasDot = fg->patternLen - (firstHalfDot < 0 ?
326: firstLastHalfDot : firstHalfDot) - 1;
327: grep_revstr(fg->pattern, fg->patternLen);
328: }
329:
330: /*
331: * Normal Quick Search would require a shift based on the position the
332: * next character after the comparison is within the pattern. With
333: * wildcards, the position of the last dot effects the maximum shift
334: * distance.
335: * The closer to the end the wild card is the slower the search. A
1.10 deraadt 336: * reverse version of this algorithm would be useful for wildcards near
1.6 tedu 337: * the end of the string.
338: *
339: * Examples:
340: * Pattern Max shift
341: * ------- ---------
342: * this 5
343: * .his 4
344: * t.is 3
345: * th.s 2
346: * thi. 1
347: */
348:
349: /* Adjust the shift based on location of the last dot ('.'). */
350: shiftPatternLen = fg->patternLen - hasDot;
351:
352: /* Preprocess pattern. */
353: for (i = 0; i <= UCHAR_MAX; i++)
354: fg->qsBc[i] = shiftPatternLen;
355: for (i = hasDot + 1; i < fg->patternLen; i++) {
356: fg->qsBc[fg->pattern[i]] = fg->patternLen - i;
357: /*
358: * If case is ignored, make the jump apply to both upper and
359: * lower cased characters. As the pattern is stored in upper
360: * case, apply the same to the lower case equivalents.
361: */
362: if (iflag)
363: fg->qsBc[tolower(fg->pattern[i])] = fg->patternLen - i;
364: }
365:
366: /*
367: * Put pattern back to normal after pre-processing to allow for easy
368: * comparisons later.
369: */
370: if (fg->reversedSearch)
371: grep_revstr(fg->pattern, fg->patternLen);
372:
373: return (0);
374: }
375:
1.22 millert 376: #define wmatch(d, l, s, e) \
377: ((s == 0 || !isword(d[s-1])) && (e == l || !isword(d[e])))
378:
1.9 millert 379: static int
1.23 ! millert 380: grep_search(fastgrep_t *fg, unsigned char *data, size_t dataLen, regmatch_t *pmatch)
1.6 tedu 381: {
382: int j;
383: int rtrnVal = REG_NOMATCH;
384:
1.9 millert 385: pmatch->rm_so = -1;
386: pmatch->rm_eo = -1;
387:
1.6 tedu 388: /* No point in going farther if we do not have enough data. */
389: if (dataLen < fg->patternLen)
390: return (rtrnVal);
391:
392: /* Only try once at the beginning or ending of the line. */
393: if (fg->bol || fg->eol) {
394: /* Simple text comparison. */
395: /* Verify data is >= pattern length before searching on it. */
396: if (dataLen >= fg->patternLen) {
397: /* Determine where in data to start search at. */
398: if (fg->eol)
399: j = dataLen - fg->patternLen;
400: else
401: j = 0;
402: if (!((fg->bol && fg->eol) && (dataLen != fg->patternLen)))
1.22 millert 403: if (grep_cmp(fg->pattern, data + j,
404: fg->patternLen) == -1) {
1.9 millert 405: pmatch->rm_so = j;
406: pmatch->rm_eo = j + fg->patternLen;
1.22 millert 407: if (!fg->wmatch || wmatch(data, dataLen,
408: pmatch->rm_so, pmatch->rm_eo))
409: rtrnVal = 0;
1.9 millert 410: }
1.6 tedu 411: }
412: } else if (fg->reversedSearch) {
413: /* Quick Search algorithm. */
1.17 millert 414: j = dataLen;
415: do {
1.6 tedu 416: if (grep_cmp(fg->pattern, data + j - fg->patternLen,
417: fg->patternLen) == -1) {
1.9 millert 418: pmatch->rm_so = j - fg->patternLen;
419: pmatch->rm_eo = j;
1.22 millert 420: if (!fg->wmatch || wmatch(data, dataLen,
421: pmatch->rm_so, pmatch->rm_eo)) {
422: rtrnVal = 0;
423: break;
424: }
1.6 tedu 425: }
1.17 millert 426: /* Shift if within bounds, otherwise, we are done. */
427: if (j == fg->patternLen)
428: break;
429: j -= fg->qsBc[data[j - fg->patternLen - 1]];
430: } while (j >= fg->patternLen);
1.6 tedu 431: } else {
432: /* Quick Search algorithm. */
433: j = 0;
434: do {
435: if (grep_cmp(fg->pattern, data + j, fg->patternLen) == -1) {
1.9 millert 436: pmatch->rm_so = j;
437: pmatch->rm_eo = j + fg->patternLen;
1.22 millert 438: if (!fg->wmatch || wmatch(data, dataLen,
439: pmatch->rm_so, pmatch->rm_eo)) {
440: rtrnVal = 0;
441: break;
442: }
1.6 tedu 443: }
444:
445: /* Shift if within bounds, otherwise, we are done. */
446: if (j + fg->patternLen == dataLen)
447: break;
448: else
449: j += fg->qsBc[data[j + fg->patternLen]];
450: } while (j <= (dataLen - fg->patternLen));
451: }
452:
453: return (rtrnVal);
454: }
455:
456:
1.1 deraadt 457: void *
458: grep_malloc(size_t size)
459: {
1.10 deraadt 460: void *ptr;
1.1 deraadt 461:
462: if ((ptr = malloc(size)) == NULL)
1.14 millert 463: err(2, "malloc");
1.1 deraadt 464: return ptr;
465: }
466:
467: void *
468: grep_realloc(void *ptr, size_t size)
469: {
470: if ((ptr = realloc(ptr, size)) == NULL)
1.14 millert 471: err(2, "realloc");
1.6 tedu 472: return ptr;
473: }
474:
475: /*
476: * Returns: i >= 0 on failure (position that it failed)
477: * -1 on success
478: */
1.18 avsm 479: static int
1.9 millert 480: grep_cmp(const unsigned char *pattern, const unsigned char *data, size_t len)
1.6 tedu 481: {
482: int i;
483:
484: for (i = 0; i < len; i++) {
485: if (((pattern[i] == data[i]) || (pattern[i] == '.')) ||
486: (iflag && pattern[i] == toupper(data[i])))
487: continue;
488: return (i);
489: }
490:
491: return (-1);
492: }
493:
494: static void
495: grep_revstr(unsigned char *str, int len)
496: {
497: int i;
498: char c;
499:
500: for (i = 0; i < len / 2; i++) {
501: c = str[i];
502: str[i] = str[len - i - 1];
503: str[len - i - 1] = c;
504: }
1.1 deraadt 505: }
506:
507: void
508: printline(str_t *line, int sep)
509: {
510: int n;
1.2 deraadt 511:
1.1 deraadt 512: n = 0;
513: if (!hflag) {
514: fputs(line->file, stdout);
515: ++n;
516: }
517: if (nflag) {
518: if (n)
519: putchar(sep);
520: printf("%d", line->line_no);
521: ++n;
522: }
523: if (bflag) {
524: if (n)
525: putchar(sep);
1.21 otto 526: printf("%lld", (long long)line->off);
527: ++n;
1.1 deraadt 528: }
529: if (n)
530: putchar(sep);
531: fwrite(line->dat, line->len, 1, stdout);
532: putchar('\n');
533: }