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