![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to egrep.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / grep / egrep|
Return to egrep.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / grep / egrep |
1.1 root 1: #ifndef lint
2: static char sccsid[] = "@(#)egrep.c 5.12 (Berkeley) 5/11/89";
3: #endif not lint
4:
5: /*
6: Hybrid Boyer/Moore/Gosper-assisted 'grep/egrep/fgrep' search, with delta0
7: table as in original paper (CACM, October, 1977). No delta1 or delta2.
8: According to experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of
9: minimal practical value. However, to improve for worst case input,
10: integrating the improved Galil strategies (Apostolico/Giancarlo, SIAM. J.
11: Comput., Feb. 1986) deserves consideration.
12:
13: Method: extract longest metacharacter-free string from expression.
14: this is done using a side-effect from henry spencer's regcomp().
15: use boyer-moore to match such, then pass submatching lines
16: to either regexp() or standard 'egrep', depending on certain
17: criteria within execstrategy() below. [this tradeoff is due
18: to the general slowness of the regexp() nondeterministic
19: machine on complex expressions, as well as the startup time
20: of standard 'egrep' on short files.] alternatively, one may
21: change the vendor-supplied 'egrep' automaton to include
22: boyer-moore directly. see accompanying writeup for discussion
23: of kanji expression treatment.
24:
25: late addition: apply trickbag for fast match of simple
26: alternations (sublinear, in common low-cardinality cases).
27: trap fgrep into this lair.
28:
29: gnu additions: -f, newline as |, \< and \> [in regexec()], more
30: comments. inspire better dfa exec() strategy.
31: serious testing and help with special cases.
32:
33: Algorithm amalgam summary:
34:
35: dfa e?grep (aho/thompson)
36: ndfa regexp() (spencer/aho)
37: bmg (boyer/moore/gosper)
38: "superimposed" bmg (jaw)
39: fgrep (aho/corrasick)
40:
41: sorry, but the knuth/morris/pratt machine, horspool's
42: "frequentist" code, and the rabin/karp matcher, however cute,
43: just don't cut it for this production.
44:
45: James A. Woods Copyright (c) 1986
46: NASA Ames Research Center
47: */
48: #include <sys/types.h>
49: #include <sys/stat.h>
50: #include <sys/file.h>
51: #include <regexp.h> /* must be henry spencer's version */
52: #include <stdio.h>
53: #include <ctype.h>
54: #include "pathnames.h"
55:
56: #define MIN(A, B) ((A) > (B) ? (B) : (A))
57:
58: #ifdef SLOWSYS
59: #define read xread
60: #endif
61:
62: #define BUFSIZE 8192 /* make higher for cray */
63: #define PATSIZE 6000
64: #define LARGE BUFSIZE + PATSIZE
65:
66: #define NALT 7 /* tied to scanf() size in alternate() */
67: #define NMUSH 6 /* loosely relates to expected alt length */
68:
69: #define FIRSTFEW 33 /* Always do FIRSTFEW matches with regexec() */
70: #define PUNTPERCENT 10 /* After FIRSTFEW, if PUNTPERCENT of the input
71: * was processed by regexp(), exec std egrep. */
72: #define NL '\n'
73: #define EOS '\0'
74: #define NONASCII 0200 /* Bit mask for Kanji non-ascii chars */
75: #define META "\n^$.[]()?+*|\\" /* egrep meta-characters */
76: #define SS2 '\216' /* EUC Katakana (or Chinese2) prefix */
77: #define SS3 '\217' /* EUC Kanji2 (or Chinese3) prefix */
78:
79: extern char *optarg;
80: extern int optind;
81: char *progname;
82:
83: int cflag, iflag, eflag, fflag, lflag, nflag; /* SVID flags */
84: int sflag, hflag; /* v7, v8, bsd */
85:
86: int firstflag; /* Stop at first match */
87: int grepflag; /* Called as "grep" */
88: int fgrepflag; /* Called as "fgrep" */
89: int altflag; /* Simple alternation in pattern */
90: int boyonly; /* No regexp needed -- all simple */
91: int flushflag;
92: int grepold, egrepold, fgrepold;
93:
94: int nalt; /* Number of alternatives */
95: int nsuccess; /* 1 for match, 2 for error */
96: int altmin; /* Minimum length of all the alternate
97: * strings */
98: int firstfile; /* argv index of first file argument */
99: int patind; /* argv index of pattern */
100: long nmatch; /* Number of matches in this file */
101: long incount, counted; /* Amount of input consumed */
102: long rxcount; /* Bytes of input processed by regexec() */
103: int boyfound; /* accumulated partial matches (tripped by
104: * FIRSTFEW) */
105: int prevmatch; /* next three lines aid fast -n */
106: long nline, prevnline;
107: char *prevloc;
108:
109: regexp *rspencer;
110: char *pattern;
111: char *patboy; /* Pattern for simple Boyer-Moore */
112: char *patfile; /* Filename containing pattern(s) */
113:
114: int delta0[256]; /* Boyer-Moore algorithm core */
115: char cmap[256]; /* Usually 0-255, but if -i, maps upper to
116: * lower case */
117: char str[BUFSIZE + 2];
118: int nleftover;
119: char linetemp[BUFSIZE];
120: char *altpat[NALT]; /* alternation component storage */
121: int altlen[NALT];
122: short altset[NMUSH + 1][256];
123: char preamble[200]; /* match prefix (filename, line no.) */
124:
125: int fd;
126: char *
127: strchr(), *strrchr(), *strcpy(), *strncpy(), *strpbrk(), *malloc();
128: char *
129: grepxlat(), *fold(), *pfile(), *alternate(), *isolate();
130: char *gotamatch(), *kanji(), *linesave(), *submatch();
131: char **args;
132:
133: main(argc, argv)
134: int argc;
135: char *argv[];
136: {
137: int c, oflag;
138: int errflag = 0;
139:
140: args = argv;
141:
142: if ((progname = strrchr(argv[0], '/')) != 0)
143: progname++;
144: else
145: progname = argv[0];
146: if (strcmp(progname, "grep") == 0)
147: grepflag++;
148: else if (strcmp(progname, "fgrep") == 0)
149: fgrepflag++;
150:
151: oflag = 0;
152: while ((c = getopt(argc, argv, "bchie:f:lnosvwxy1")) != EOF) {
153: switch (c) {
154:
155: case 'f':
156: fflag++;
157: patfile = optarg;
158: continue;
159: case 'b':
160: case 'v':
161: egrepold++; /* boyer-moore of little help here */
162: continue;
163: case 'c':
164: cflag++;
165: continue;
166: case 'e':
167: eflag++;
168: pattern = optarg;
169: continue;
170: case 'h':
171: hflag++;
172: continue;
173: case 'o':
174: oflag++;
175: continue;
176: case '1': /* Stop at very first match */
177: firstflag++; /* spead freaks only */
178: continue;
179: case 'i':
180: iflag++;
181: continue;
182: case 'l':
183: lflag++;
184: continue;
185: case 'n':
186: nflag++;
187: continue;
188: case 's':
189: sflag++;
190: continue;
191: case 'w':
192: case 'y':
193: if (!grepflag)
194: errflag++;
195: grepold++;
196: continue;
197: case 'x': /* needs more work, like -b above */
198: if (!fgrepflag)
199: errflag++;
200: fgrepold++;
201: continue;
202: case '?':
203: errflag++;
204: }
205: }
206: if (errflag || ((argc <= optind) && !fflag && !eflag)) {
207: if (grepflag)
208: oops("usage: grep [-bchilnosvwy] [-e] pattern [file ...]");
209: else if (fgrepflag)
210: oops("usage: fgrep [-bchilnosvx] {-f patfile | [-e] strings} [file ...]");
211: else /* encourage SVID options, though we provide
212: * others */
213: oops("usage: egrep [-bchilnosv] {-f patfile | [-e] pattern} [file ...]");
214: }
215: if (fflag)
216: pattern = pfile(patfile);
217: else if (!eflag) {
218: patind = optind;
219: pattern = argv[optind++];
220: }
221:
222: if (!oflag && (argc - optind) <= 1) /* Filename invisible given < 2 files */
223: hflag++;
224: if (pattern[0] == EOS)
225: kernighan(argv); /* same as it ever was */
226: /*
227: * 'grep/egrep' merger -- "old" grep is called to handle: tagged
228: * exprs \( \), word matches \< and \>, -w and -y options, char
229: * classes with '-' at end (egrep bug?), and patterns beginning with
230: * an asterisk (don't ask why). otherwise, characters meaningful to
231: * 'egrep' but not to 'grep' are escaped; the entire expr is then
232: * passed to 'egrep'.
233: */
234: if (grepflag && !grepold) {
235: if (strindex(pattern, "\\(") >= 0 ||
236: strindex(pattern, "\\<") >= 0 ||
237: strindex(pattern, "\\>") >= 0 ||
238: strindex(pattern, "-]") >= 0 ||
239: pattern[0] == '*') /* grep bug */
240: grepold++;
241: else
242: pattern = grepxlat(pattern);
243: }
244: if (grepold || egrepold || fgrepold)
245: kernighan(argv);
246:
247: if (iflag)
248: strcpy(pattern, fold(pattern));
249: /*
250: * If the pattern is a plain string, just run boyer-moore. If it
251: * consists of meta-free alternatives, run "superimposed" bmg.
252: * Otherwise, find best string, and compile pattern for regexec().
253: */
254: if (strpbrk(pattern, META) == NULL) { /* do boyer-moore only */
255: boyonly++;
256: patboy = pattern;
257: } else {
258: if ((patboy = alternate(pattern)) != NULL)
259: boyonly++;
260: else {
261: if ((patboy = isolate(pattern)) == NULL)
262: kernighan(argv); /* expr too involved */
263: #ifndef NOKANJI
264: for (c = 0; pattern[c] != EOS; c++)
265: if (pattern[c] & NONASCII) /* kanji + meta */
266: kernighan(argv);
267: #endif
268: if ((rspencer = regcomp(pattern)) == NULL)
269: oops("regcomp failure");
270: }
271: }
272: gosper(patboy); /* "pre-conditioning is wonderful"
273: * -- v. strassen */
274:
275: if ((firstfile = optind) >= argc) {
276: /* Grep standard input */
277: if (lflag) /* We don't know its name! */
278: exit(1);
279: egsecute((char *) NULL);
280: } else {
281: while (optind < argc) {
282: egsecute(argv[optind]);
283: optind++;
284: if (firstflag && (nsuccess == 1))
285: break;
286: }
287: }
288: exit((nsuccess == 2) ? 2 : (nsuccess == 0));
289: }
290:
291: char *
292: pfile(pfname) /* absorb expression from file */
293: char *pfname;
294: {
295: int fd;
296: struct stat patstat;
297: static char *pat;
298:
299: if ((fd = open(pfname, O_RDONLY, 0)) < 0)
300: oops("can't read pattern file");
301: if (fstat(fd, &patstat) != 0)
302: oops("can't stat pattern file");
303: if (patstat.st_size > PATSIZE) {
304: if (fgrepflag) { /* defer to unix version */
305: fgrepold++;
306: return "dummy";
307: } else
308: oops("pattern file too big");
309: }
310: if ((pat = malloc((unsigned) patstat.st_size + 1)) == NULL)
311: oops("out of memory to read pattern file");
312: if (patstat.st_size != read(fd, pat, (int)patstat.st_size))
313: oops("error reading pattern file");
314: (void) close(fd);
315:
316: pat[patstat.st_size] = EOS;
317: if (pat[patstat.st_size - 1] == NL) /* NOP for egrep; helps grep */
318: pat[patstat.st_size - 1] = EOS;
319:
320: if (nlcount(pat, &pat[patstat.st_size]) > NALT) {
321: if (fgrepflag)
322: fgrepold++; /* "what's it all about, alfie?" */
323: else
324: egrepold++;
325: }
326: return (pat);
327: }
328:
329: egsecute(file)
330: char *file;
331: {
332: if (file == NULL)
333: fd = 0;
334: else if ((fd = open(file, O_RDONLY, 0)) <= 0) {
335: fprintf(stderr, "%s: can't open %s\n", progname, file);
336: nsuccess = 2;
337: return;
338: }
339: chimaera(file, patboy);
340:
341: if (!boyonly && !flushflag && file != NULL)
342: flushmatches();
343: if (file != NULL)
344: close(fd);
345: }
346:
347: chimaera(file, pat) /* "reach out and boyer-moore search someone" */
348: char *file, *pat; /* -- soon-to-be-popular bumper sticker */
349: {
350: register char *k, *strend, *s;
351: register int j, count;
352: register int *deltazero = delta0;
353: int patlen = altmin;
354: char *t;
355:
356: nleftover = boyfound = flushflag = 0;
357: nline = 1L;
358: prevmatch = 0;
359: nmatch = counted = rxcount = 0L;
360:
361: while ((count = read(fd, str + nleftover, BUFSIZE - nleftover)) > 0) {
362:
363: counted += count;
364: strend = linesave(str, count);
365:
366: for (k = str + patlen - 1; k < strend;) {
367: /*
368: * for a large class of patterns, upwards of 80% of
369: * match time is spent on the next line. we beat
370: * existing microcode (vax 'matchc') this way.
371: */
372: while ((k += deltazero[*(unsigned char *) k]) < strend);
373: if (k < (str + LARGE))
374: break;
375: k -= LARGE;
376:
377: if (altflag) {
378: /*
379: * Parallel Boyer-Moore. Check whether each
380: * of the previous <altmin> chars COULD be
381: * from one of the alternative strings.
382: */
383: s = k - 1;
384: j = altmin;
385: while (altset[--j][(unsigned char)
386: cmap[*(unsigned char *) s--]]);
387: /*
388: * quick test fails. in this life, compare
389: * 'em all. but, a "reverse trie" would
390: * attenuate worst case (linear w/delta2?).
391: */
392: if (--j < 0) {
393: count = nalt - 1;
394: do {
395: s = k;
396: j = altlen[count];
397: t = altpat[count];
398:
399: while
400: (cmap[*(unsigned char *) s--]
401: == t[--j]);
402: if (j < 0)
403: break;
404: }
405: while (count--);
406: }
407: } else {
408: /* One string -- check it */
409: j = patlen - 1;
410: s = k - 1;
411: while (cmap[*(unsigned char *) s--] == pat[--j]);
412: }
413: /*
414: * delta-less shortcut for literati. short shrift for
415: * genetic engineers?
416: */
417: if (j >= 0) {
418: k++; /* no match; restart next char */
419: continue;
420: }
421: k = submatch(file, pat, str, strend, k, count);
422: if (k == NULL)
423: return;
424: }
425: if (nflag) {
426: if (prevmatch)
427: nline = prevnline + nlcount(prevloc, k);
428: else
429: nline = nline + nlcount(str, k);
430: prevmatch = 0;
431: }
432: strncpy(str, linetemp, nleftover);
433: }
434: if (cflag) {
435: /* Bug from old grep: -c overrides -h. We fix the bug. */
436: if (!hflag)
437: printf("%s:", file);
438: printf("%ld\n", nmatch);
439: }
440: }
441:
442: char *
443: linesave(str, count) /* accumulate partial line at end of buffer */
444: char str[];
445: register int count;
446: {
447: register int j;
448:
449: count += nleftover;
450: if (count != BUFSIZE && fd != 0)
451: str[count++] = NL; /* insurance for broken last line */
452: str[count] = EOS;
453: for (j = count - 1; str[j] != NL && j >= 0;)
454: j--;
455: /*
456: * break up these lines: long line (> BUFSIZE), last line of file, or
457: * short return from read(), as from tee(1) input
458: */
459: if (j < 0 && (count == (BUFSIZE - nleftover))) {
460: str[count++] = NL;
461: str[count] = EOS;
462: linetemp[0] = EOS;
463: nleftover = 0;
464: return (str + count);
465: } else {
466: nleftover = count - j - 1;
467: strncpy(linetemp, str + j + 1, nleftover);
468: return (str + j);
469: }
470: }
471:
472: /*
473: * Process partial match. First check for mis-aligned Kanji, then match line
474: * against full compiled r.e. if statistics do not warrant handing off to
475: * standard egrep.
476: */
477: char *
478: submatch(file, pat, str, strend, k, altindex)
479: char file[], pat[], str[];
480: register char *strend, *k;
481: int altindex;
482: {
483: register char *s;
484: char *t, c;
485:
486: t = k;
487: s = ((altflag) ? k - altlen[altindex] + 1 : k - altmin + 1);
488: #ifndef NOKANJI
489: c = ((altflag) ? altpat[altindex][0] : pat[0]);
490: if (c & NONASCII)
491: if ((s = kanji(str, s, k)) == NULL)
492: return (++k); /* reject false kanji */
493: #endif
494: do;
495: while (*s != NL && --s >= str);
496: k = s + 1; /* now at line start */
497:
498: if (boyonly)
499: return (gotamatch(file, k));
500:
501: incount = counted - (strend - k);
502: if (boyfound++ == FIRSTFEW)
503: execstrategy(file);
504:
505: s = t;
506: do
507: rxcount++;
508: while (*s++ != NL);
509: *--s = EOS;
510: /*
511: * "quick henry -- the flit" (after theodor geisel)
512: */
513: if (regexec(rspencer, ((iflag) ? fold(k) : k)) == 1) {
514: *s = NL;
515: if (gotamatch(file, k) == NULL)
516: return (NULL);
517: }
518: *s = NL;
519: return (s + 1);
520: }
521:
522: #ifndef NOKANJI
523: /*
524: * EUC code disambiguation -- scan backwards to first 7-bit code, while
525: * counting intervening 8-bit codes. If odd, reject unaligned Kanji pattern.
526: * SS2/3 checks are for intermixed Japanase Katakana or Kanji2.
527: */
528: char *
529: kanji(str, s, k)
530: register char *str, *s, *k;
531: {
532: register int j = 0;
533:
534: for (s--; s >= str; s--) {
535: if (*s == SS2 || *s == SS3 || (*s & NONASCII) == 0)
536: break;
537: j++;
538: }
539: #ifndef CHINESE
540: if (*s == SS2)
541: j -= 1;
542: #endif CHINESE
543: return ((j & 01) ? NULL : k);
544: }
545: #endif
546:
547: /*
548: * Compute "Boyer-Moore" delta table -- put skip distance in delta0[c]
549: */
550: gosper(pattern)
551: char *pattern; /* ... HAKMEM lives ... */
552: {
553: register int i, j;
554: unsigned char c;
555:
556: /* Make one-string case look like simple alternatives case */
557: if (!altflag) {
558: nalt = 1;
559: altmin = altlen[0] = strlen(pattern);
560: altpat[0] = pattern;
561: }
562: /* For chars that aren't in any string, skip by string length. */
563: for (j = 0; j < 256; j++) {
564: delta0[j] = altmin;
565: cmap[j] = j; /* Sneak in initialization of cmap */
566: }
567:
568: /* For chars in a string, skip distance from char to end of string. */
569: /* (If char appears more than once, skip minimum distance.) */
570: for (i = 0; i < nalt; i++)
571: for (j = 0; j < altlen[i] - 1; j++) {
572: c = altpat[i][j];
573: delta0[c] = MIN(delta0[c], altlen[i] - j - 1);
574: if (iflag && islower((int) c))
575: delta0[toupper((int) c)] = delta0[c];
576: }
577:
578: /* For last char of each string, fall out of search loop. */
579: for (i = 0; i < nalt; i++) {
580: c = altpat[i][altlen[i] - 1];
581: delta0[c] = LARGE;
582: if (iflag && islower((int) c))
583: delta0[toupper((int) c)] = LARGE;
584: }
585: if (iflag)
586: for (j = 'A'; j <= 'Z'; j++)
587: cmap[j] = tolower((int) j);
588: }
589:
590: /*
591: * Print, count, or stop on full match. Result is either the location for
592: * continued search, or NULL to stop.
593: */
594: char *
595: gotamatch(file, s)
596: register char *file, *s;
597: {
598: char *savematch();
599: int squirrel = 0; /* nonzero to squirrel away FIRSTFEW matches */
600:
601: nmatch++;
602: nsuccess = 1;
603: if (!boyonly && boyfound <= FIRSTFEW && file != NULL)
604: squirrel = 1;
605:
606: if (sflag)
607: return (NULL); /* -s usurps all flags (unlike some versions) */
608: if (cflag) { /* -c overrides -l, we guess */
609: do;
610: while (*s++ != NL);
611: } else if (lflag) {
612: puts(file);
613: return (NULL);
614: } else {
615: if (!hflag)
616: if (!squirrel)
617: printf("%s:", file);
618: else
619: (void)sprintf(preamble, "%s:", file);
620: if (nflag) {
621: if (prevmatch)
622: prevnline = prevnline + nlcount(prevloc, s);
623: else
624: prevnline = nline + nlcount(str, s);
625: prevmatch = 1;
626:
627: if (!squirrel)
628: printf("%ld:", prevnline);
629: else
630: (void)sprintf(preamble + strlen(preamble),
631: "%ld:", prevnline);
632: }
633: if (!squirrel) {
634: do
635: putchar(*s);
636: while (*s++ != NL);
637: } else
638: s = savematch(s);
639:
640: if (nflag)
641: prevloc = s - 1;
642: }
643: return ((firstflag && !cflag) ? NULL : s);
644: }
645:
646: char *
647: fold(line)
648: char *line;
649: {
650: static char fline[BUFSIZE];
651: register char *s, *t = fline;
652:
653: for (s = line; *s != EOS; s++)
654: *t++ = (isupper((int) *s) ? (char) tolower((int) *s) : *s);
655: *t = EOS;
656: return (fline);
657: }
658:
659: strindex(s, t) /* the easy way, as in K&P, p. 192 */
660: char *s, *t;
661: {
662: int i, n;
663:
664: n = strlen(t);
665: for (i = 0; s[i] != '\0'; i++)
666: if (strncmp(s + i, t, n) == 0)
667: return (i);
668: return (-1);
669: }
670:
671: char *
672: grepxlat(pattern) /* grep pattern meta conversion */
673: char *pattern;
674: {
675: register char *p, *s;
676: static char newpat[BUFSIZE];
677:
678: for (s = newpat, p = pattern; *p != EOS;) {
679: if (*p == '\\') { /* skip escapes ... */
680: *s++ = *p++;
681: if (*p)
682: *s++ = *p++;
683: } else if (*p == '[') { /* ... and char classes */
684: while (*p != EOS && *p != ']')
685: *s++ = *p++;
686: } else if (strchr("+?|()", *p) != NULL) {
687: *s++ = '\\'; /* insert protection */
688: *s++ = *p++;
689: } else
690: *s++ = *p++;
691: }
692: *s = EOS;
693: grepflag = ((patind) ? 0 : 1);
694: return (newpat);
695: }
696:
697: /*
698: * Test for simple alternation. Result is NULL if it's not so simple, or is
699: * a pointer to the first string if it is. Warning: sscanf size is a
700: * fixpoint, beyond which the speedup linearity starts to break down. In the
701: * wake of the elegant aho/corrasick "trie"-based fgrep, generalizing
702: * altpat[] to arbitrary size is not useful.
703: */
704: char *
705: alternate(regexpr)
706: char *regexpr;
707: {
708: register int i, j;
709: register char *start, *stop;
710: unsigned char c;
711:
712: if (fgrepflag && strchr(regexpr, '|'))
713: return (NULL);
714:
715: /*
716: * break pattern up into altpat array; delimit on newline, bar,
717: * or EOS. We know we won't overflow, we've already checked the
718: * number of patterns we're going to find against NALT.
719: * Also, set length of pattern and find minimum pattern length.
720: */
721: nalt = 0;
722: altmin = NMUSH;
723: for (start = stop = regexpr;; ++stop)
724: if (!*stop || *stop == '|' || *stop == NL) {
725: altlen[nalt] = j = stop - start;
726: if (j < altmin)
727: altmin = j;
728: if (!(altpat[nalt] = malloc((u_int)(j + 1))))
729: oops("out of memory");
730: bcopy(start, altpat[nalt], j);
731: altpat[nalt][j] = EOS;
732: ++nalt;
733: if (!*stop)
734: break;
735: if (nalt == NALT)
736: return(NULL);
737: if (*stop == NL)
738: *stop = '|';
739: start = stop + 1;
740: }
741: if (!fgrepflag) {
742: if (strchr(regexpr, '|') == NULL || regexpr[0] == '|')
743: return (NULL);
744: if (strpbrk(regexpr, "^$.[]()?+*\\") != NULL
745: || strindex(regexpr, "||") >= 0)
746: return (NULL);
747: }
748:
749: if (nalt > 1) { /* build superimposed "pre-match" sets per
750: * char */
751: altflag++;
752: for (j = 0; j < nalt; j++)
753: for (i = 0; i < altmin; i++) {
754: c = altpat[j][altlen[j] - altmin + i];
755: altset[i + 1][c] = 1; /* offset for sentinel */
756: }
757: }
758: return (altpat[0]);
759: }
760:
761: /*
762: * Grapple with the dfa (std egrep) vs. ndfa (regexp) tradeoff. Criteria to
763: * determine whether to use dfa-based egrep: We do FIRSTFEW matches with
764: * regexec(). If Boyer-Moore up to now matched more than PUNTPERCENT
765: * of the input, the r.e. is likely to be underspecified, so do old *grep,
766: * which is faster on complex patterns than regexp(). At FIRSTFEW,
767: * dump the saved matches collected by savematch(). They are saved
768: * so that a "PUNT" can "rewind" to ignore them. Stdin is problematic,
769: * since it's hard to rewind.
770: */
771:
772: execstrategy(file)
773: char *file;
774: {
775: int pctmatch;
776:
777: pctmatch = (100 * rxcount) / incount;
778: if (pctmatch > PUNTPERCENT && file != NULL)
779: kernighan(args);
780: if (file != NULL)
781: flushmatches();
782: }
783:
784: nlcount(bstart, bstop) /* flail interval to totalize newlines. */
785: char *bstart, *bstop;
786: {
787: register char *s = bstart;
788: register char *t = bstop;
789: register int count = 0;
790:
791: do { /* loop unroll for older architectures */
792: if (*t == NL) /* ... ask ames!jaw for sample code */
793: count++;
794: } while (t-- > s);
795:
796: return (count);
797: }
798:
799: char *
800: isolate(regexpr) /* isolate longest metacharacter-free string */
801: char *regexpr;
802: {
803: char *dummyexpr;
804:
805: /*
806: * We add (.)* because Henry's regcomp only figures regmust if it
807: * sees a leading * pattern. Foo!
808: */
809: dummyexpr = malloc((unsigned) strlen(regexpr) + 5);
810: (void)sprintf(dummyexpr, "(.)*%s", regexpr);
811: if ((rspencer = regcomp(dummyexpr)) == NULL)
812: kernighan(args);
813: return (rspencer->regmust);
814: }
815:
816: char *matches[FIRSTFEW];
817: static int mcount = 0;
818:
819: char *
820: savematch(s) /* horde matches during statistics gathering */
821: register char *s;
822: {
823: char *p;
824: char *start = s;
825: int msize = 0;
826: int psize = strlen(preamble);
827:
828: while (*s++ != NL)
829: msize++;
830: *--s = EOS;
831:
832: p = malloc((unsigned) msize + 1 + psize);
833: strcpy(p, preamble);
834: strcpy(p + psize, start);
835: matches[mcount++] = p;
836:
837: preamble[0] = 0;
838: *s = NL;
839: return (s);
840: }
841:
842: flushmatches()
843: {
844: int n;
845:
846: flushflag = 1;
847: for (n = 0; n < mcount; n++)
848: printf("%s\n", matches[n]);
849: mcount = 0;
850: }
851:
852: oops(message)
853: char *message;
854: {
855: fprintf(stderr, "%s: %s\n", progname, message);
856: exit(2);
857: }
858:
859: kernighan(args) /* "let others do the hard part ..." */
860: char *args[];
861: {
862: /*
863: * We may have already run grep on some of the files; remove them
864: * from the arg list we pass on. Note that we can't delete them
865: * totally because the number of file names affects the output
866: * (automatic -h).
867: */
868: /* better would be fork/exec per punted file -- jaw */
869:
870: while (firstfile && optind > firstfile)
871: args[firstfile++] = _PATH_DEVNULL;
872: if (patind)
873: args[patind] = pattern;
874: (void) fflush(stdout);
875:
876: if (grepflag)
877: execvp(_PATH_GREPSTD, args), oops("can't exec old 'grep'");
878: else if (fgrepflag)
879: execvp(_PATH_FGREPSTD, args), oops("can't exec old 'fgrep'");
880: else
881: execvp(_PATH_EGREPSTD, args), oops("can't exec old 'egrep'");
882: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.