049dfb15eb8195c00dfcaf9171e66ec046641f6b
[mes.git] / scaffold / tinycc / 46_grep.c
1 /*
2  * The  information  in  this  document  is  subject  to  change
3  * without  notice  and  should not be construed as a commitment
4  * by Digital Equipment Corporation or by DECUS.
5  *
6  * Neither Digital Equipment Corporation, DECUS, nor the authors
7  * assume any responsibility for the use or reliability of  this
8  * document or the described software.
9  *
10  *      Copyright (C) 1980, DECUS
11  *
12  * General permission to copy or modify, but not for profit,  is
13  * hereby  granted,  provided that the above copyright notice is
14  * included and reference made to  the  fact  that  reproduction
15  * privileges were granted by DECUS.
16  */
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <ctype.h>      // tolower()
20
21 /*
22  * grep
23  *
24  * Runs on the Decus compiler or on vms, On vms, define as:
25  *      grep :== "$disk:[account]grep"      (native)
26  *      grep :== "$disk:[account]grep grep" (Decus)
27  * See below for more information.
28  */
29
30 char    *documentation[] = {
31    "grep searches a file for a given pattern.  Execute by",
32    "   grep [flags] regular_expression file_list\n",
33    "Flags are single characters preceded by '-':",
34    "   -c      Only a count of matching lines is printed",
35    "   -f      Print file name for matching lines switch, see below",
36    "   -n      Each line is preceded by its line number",
37    "   -v      Only print non-matching lines\n",
38    "The file_list is a list of files (wildcards are acceptable on RSX modes).",
39    "\nThe file name is normally printed if there is a file given.",
40    "The -f flag reverses this action (print name no file, not if more).\n",
41    0 };
42
43 char    *patdoc[] = {
44    "The regular_expression defines the pattern to search for.  Upper- and",
45    "lower-case are always ignored.  Blank lines never match.  The expression",
46    "should be quoted to prevent file-name translation.",
47    "x      An ordinary character (not mentioned below) matches that character.",
48    "'\\'    The backslash quotes any character.  \"\\$\" matches a dollar-sign.",
49    "'^'    A circumflex at the beginning of an expression matches the",
50    "       beginning of a line.",
51    "'$'    A dollar-sign at the end of an expression matches the end of a line.",
52    "'.'    A period matches any character except \"new-line\".",
53    "':a'   A colon matches a class of characters described by the following",
54    "':d'     character.  \":a\" matches any alphabetic, \":d\" matches digits,",
55    "':n'     \":n\" matches alphanumerics, \": \" matches spaces, tabs, and",
56    "': '     other control characters, such as new-line.",
57    "'*'    An expression followed by an asterisk matches zero or more",
58    "       occurrences of that expression: \"fo*\" matches \"f\", \"fo\"",
59    "       \"foo\", etc.",
60    "'+'    An expression followed by a plus sign matches one or more",
61    "       occurrences of that expression: \"fo+\" matches \"fo\", etc.",
62    "'-'    An expression followed by a minus sign optionally matches",
63    "       the expression.",
64    "'[]'   A string enclosed in square brackets matches any character in",
65    "       that string, but no others.  If the first character in the",
66    "       string is a circumflex, the expression matches any character",
67    "       except \"new-line\" and the characters in the string.  For",
68    "       example, \"[xyz]\" matches \"xx\" and \"zyx\", while \"[^xyz]\"",
69    "       matches \"abc\" but not \"axb\".  A range of characters may be",
70    "       specified by two characters separated by \"-\".  Note that,",
71    "       [a-z] matches alphabetics, while [z-a] never matches.",
72    "The concatenation of regular expressions is a regular expression.",
73    0};
74
75 #define LMAX    512
76 #define PMAX    256
77
78 #define CHAR    1
79 #define BOL     2
80 #define EOL     3
81 #define ANY     4
82 #define CLASS   5
83 #define NCLASS  6
84 #define STAR    7
85 #define PLUS    8
86 #define MINUS   9
87 #define ALPHA   10
88 #define DIGIT   11
89 #define NALPHA  12
90 #define PUNCT   13
91 #define RANGE   14
92 #define ENDPAT  15
93
94 int cflag=0, fflag=0, nflag=0, vflag=0, nfile=0, debug=0;
95
96 char *pp, lbuf[LMAX], pbuf[PMAX];
97
98 char *cclass();
99 char *pmatch();
100 void store(int);
101 void error(char *);
102 void badpat(char *, char *, char *);
103 int match(void);
104
105
106 /*** Display a file name *******************************/
107 void file(char *s)
108 {
109    printf("File %s:\n", s);
110 }
111
112 /*** Report unopenable file ****************************/
113 void cant(char *s)
114 {
115    fprintf(stderr, "%s: cannot open\n", s);
116 }
117
118 /*** Give good help ************************************/
119 void help(char **hp)
120 {
121    char   **dp;
122
123    for (dp = hp; *dp; ++dp)
124       printf("%s\n", *dp);
125 }
126
127 /*** Display usage summary *****************************/
128 void usage(char *s)
129 {
130    fprintf(stderr, "?GREP-E-%s\n", s);
131    fprintf(stderr,
132          "Usage: grep [-cfnv] pattern [file ...].  grep ? for help\n");
133    exit(1);
134 }
135
136 /*** Compile the pattern into global pbuf[] ************/
137 void compile(char *source)
138 {
139    char  *s;         /* Source string pointer     */
140    char  *lp;        /* Last pattern pointer      */
141    int   c;          /* Current character         */
142    int            o;          /* Temp                      */
143    char           *spp;       /* Save beginning of pattern */
144
145    s = source;
146    if (debug)
147       printf("Pattern = \"%s\"\n", s);
148    pp = pbuf;
149    while (c = *s++) {
150       /*
151        * STAR, PLUS and MINUS are special.
152        */
153       if (c == '*' || c == '+' || c == '-') {
154          if (pp == pbuf ||
155                (o=pp[-1]) == BOL ||
156                o == EOL ||
157                o == STAR ||
158                o == PLUS ||
159                o == MINUS)
160             badpat("Illegal occurrence op.", source, s);
161          store(ENDPAT);
162          store(ENDPAT);
163          spp = pp;               /* Save pattern end     */
164          while (--pp > lp)       /* Move pattern down    */
165             *pp = pp[-1];        /* one byte             */
166          *pp =   (c == '*') ? STAR :
167             (c == '-') ? MINUS : PLUS;
168          pp = spp;               /* Restore pattern end  */
169          continue;
170       }
171       /*
172        * All the rest.
173        */
174       lp = pp;         /* Remember start       */
175       switch(c) {
176
177          case '^':
178             store(BOL);
179             break;
180
181          case '$':
182             store(EOL);
183             break;
184
185          case '.':
186             store(ANY);
187             break;
188
189          case '[':
190             s = cclass(source, s);
191             break;
192
193          case ':':
194             if (*s) {
195                switch(tolower(c = *s++)) {
196
197                   case 'a':
198                   case 'A':
199                      store(ALPHA);
200                      break;
201
202                   case 'd':
203                   case 'D':
204                      store(DIGIT);
205                      break;
206
207                   case 'n':
208                   case 'N':
209                      store(NALPHA);
210                      break;
211
212                   case ' ':
213                      store(PUNCT);
214                      break;
215
216                   default:
217                      badpat("Unknown : type", source, s);
218
219                }
220                break;
221             }
222             else    badpat("No : type", source, s);
223
224          case '\\':
225             if (*s)
226                c = *s++;
227
228          default:
229             store(CHAR);
230             store(tolower(c));
231       }
232    }
233    store(ENDPAT);
234    store(0);                /* Terminate string     */
235    if (debug) {
236       for (lp = pbuf; lp < pp;) {
237          if ((c = (*lp++ & 0377)) < ' ')
238             printf("\\%o ", c);
239          else    printf("%c ", c);
240       }
241       printf("\n");
242    }
243 }
244
245 /*** Compile a class (within []) ***********************/
246 char *cclass(char *source, char *src)
247    /* char       *source;   // Pattern start -- for error msg. */
248    /* char       *src;      // Class start */
249 {
250    char   *s;        /* Source pointer    */
251    char   *cp;       /* Pattern start     */
252    int    c;         /* Current character */
253    int             o;         /* Temp              */
254
255    s = src;
256    o = CLASS;
257    if (*s == '^') {
258       ++s;
259       o = NCLASS;
260    }
261    store(o);
262    cp = pp;
263    store(0);                          /* Byte count      */
264    while ((c = *s++) && c!=']') {
265       if (c == '\\') {                /* Store quoted char    */
266          if ((c = *s++) == '\0')      /* Gotta get something  */
267             badpat("Class terminates badly", source, s);
268          else    store(tolower(c));
269       }
270       else if (c == '-' &&
271             (pp - cp) > 1 && *s != ']' && *s != '\0') {
272          c = pp[-1];             /* Range start     */
273          pp[-1] = RANGE;         /* Range signal    */
274          store(c);               /* Re-store start  */
275          c = *s++;               /* Get end char and*/
276          store(tolower(c));      /* Store it        */
277       }
278       else {
279          store(tolower(c));      /* Store normal char */
280       }
281    }
282    if (c != ']')
283       badpat("Unterminated class", source, s);
284    if ((c = (pp - cp)) >= 256)
285       badpat("Class too large", source, s);
286    if (c == 0)
287       badpat("Empty class", source, s);
288    *cp = c;
289    return(s);
290 }
291
292 /*** Store an entry in the pattern buffer **************/
293 void store(int op)
294 {
295    if (pp >= &pbuf[PMAX])
296       error("Pattern too complex\n");
297    *pp++ = op;
298 }
299
300 /*** Report a bad pattern specification ****************/
301 void badpat(char *message, char *source, char *stop)
302    /* char  *message;       // Error message */
303    /* char  *source;        // Pattern start */
304    /* char  *stop;          // Pattern end   */
305 {
306    fprintf(stderr, "-GREP-E-%s, pattern is\"%s\"\n", message, source);
307    fprintf(stderr, "-GREP-E-Stopped at byte %ld, '%c'\n",
308          stop-source, stop[-1]);
309    error("?GREP-E-Bad pattern\n");
310 }
311
312 /*** Scan the file for the pattern in pbuf[] ***********/
313 void grep(FILE *fp, char *fn)
314    /* FILE       *fp;       // File to process            */
315    /* char       *fn;       // File name (for -f option)  */
316 {
317    int lno, count, m;
318
319    lno = 0;
320    count = 0;
321    while (fgets(lbuf, LMAX, fp)) {
322       ++lno;
323       m = match();
324       if ((m && !vflag) || (!m && vflag)) {
325          ++count;
326          if (!cflag) {
327             if (fflag && fn) {
328                file(fn);
329                fn = 0;
330             }
331             if (nflag)
332                printf("%d\t", lno);
333             printf("%s\n", lbuf);
334          }
335       }
336    }
337    if (cflag) {
338       if (fflag && fn)
339          file(fn);
340       printf("%d\n", count);
341    }
342 }
343
344 /*** Match line (lbuf) with pattern (pbuf) return 1 if match ***/
345 int match()
346 {
347    char   *l;        /* Line pointer       */
348
349    for (l = lbuf; *l; ++l) {
350       if (pmatch(l, pbuf))
351          return(1);
352    }
353    return(0);
354 }
355
356 /*** Match partial line with pattern *******************/
357 char *pmatch(char *line, char *pattern)
358    /* char               *line;     // (partial) line to match      */
359    /* char               *pattern;  // (partial) pattern to match   */
360 {
361    char   *l;        /* Current line pointer         */
362    char   *p;        /* Current pattern pointer      */
363    char   c;         /* Current character            */
364    char            *e;        /* End for STAR and PLUS match  */
365    int             op;        /* Pattern operation            */
366    int             n;         /* Class counter                */
367    char            *are;      /* Start of STAR match          */
368
369    l = line;
370    if (debug > 1)
371       printf("pmatch(\"%s\")\n", line);
372    p = pattern;
373    while ((op = *p++) != ENDPAT) {
374       if (debug > 1)
375          printf("byte[%ld] = 0%o, '%c', op = 0%o\n",
376                l-line, *l, *l, op);
377       switch(op) {
378
379          case CHAR:
380             if (tolower(*l++) != *p++)
381                return(0);
382             break;
383
384          case BOL:
385             if (l != lbuf)
386                return(0);
387             break;
388
389          case EOL:
390             if (*l != '\0')
391                return(0);
392             break;
393
394          case ANY:
395             if (*l++ == '\0')
396                return(0);
397             break;
398
399          case DIGIT:
400             if ((c = *l++) < '0' || (c > '9'))
401                return(0);
402             break;
403
404          case ALPHA:
405             c = tolower(*l++);
406             if (c < 'a' || c > 'z')
407                return(0);
408             break;
409
410          case NALPHA:
411             c = tolower(*l++);
412             if (c >= 'a' && c <= 'z')
413                break;
414             else if (c < '0' || c > '9')
415                return(0);
416             break;
417
418          case PUNCT:
419             c = *l++;
420             if (c == 0 || c > ' ')
421                return(0);
422             break;
423
424          case CLASS:
425          case NCLASS:
426             c = tolower(*l++);
427             n = *p++ & 0377;
428             do {
429                if (*p == RANGE) {
430                   p += 3;
431                   n -= 2;
432                   if (c >= p[-2] && c <= p[-1])
433                      break;
434                }
435                else if (c == *p++)
436                   break;
437             } while (--n > 1);
438             if ((op == CLASS) == (n <= 1))
439                return(0);
440             if (op == CLASS)
441                p += n - 2;
442             break;
443
444          case MINUS:
445             e = pmatch(l, p);       /* Look for a match    */
446             while (*p++ != ENDPAT); /* Skip over pattern   */
447             if (e)                  /* Got a match?        */
448                l = e;               /* Yes, update string  */
449             break;                  /* Always succeeds     */
450
451          case PLUS:                 /* One or more ...     */
452             if ((l = pmatch(l, p)) == 0)
453                return(0);           /* Gotta have a match  */
454          case STAR:                 /* Zero or more ...    */
455             are = l;                /* Remember line start */
456             while (*l && (e = pmatch(l, p)))
457                l = e;               /* Get longest match   */
458             while (*p++ != ENDPAT); /* Skip over pattern   */
459             while (l >= are) {      /* Try to match rest   */
460                if (e = pmatch(l, p))
461                   return(e);
462                --l;                 /* Nope, try earlier   */
463             }
464             return(0);              /* Nothing else worked */
465
466          default:
467             printf("Bad op code %d\n", op);
468             error("Cannot happen -- match\n");
469       }
470    }
471    return(l);
472 }
473
474 /*** Report an error ***********************************/
475 void error(char *s)
476 {
477    fprintf(stderr, "%s", s);
478    exit(1);
479 }
480
481 /*** Main program - parse arguments & grep *************/
482 int main(int argc, char **argv)
483 {
484    char   *p;
485    int    c, i;
486    int             gotpattern;
487
488    FILE            *f;
489
490    if (argc <= 1)
491       usage("No arguments");
492    if (argc == 2 && argv[1][0] == '?' && argv[1][1] == 0) {
493       help(documentation);
494       help(patdoc);
495       return 0;
496    }
497    nfile = argc-1;
498    gotpattern = 0;
499    for (i=1; i < argc; ++i) {
500       p = argv[i];
501       if (*p == '-') {
502          ++p;
503          while (c = *p++) {
504             switch(tolower(c)) {
505
506                case '?':
507                   help(documentation);
508                   break;
509
510                case 'C':
511                case 'c':
512                   ++cflag;
513                   break;
514
515                case 'D':
516                case 'd':
517                   ++debug;
518                   break;
519
520                case 'F':
521                case 'f':
522                   ++fflag;
523                   break;
524
525                case 'n':
526                case 'N':
527                   ++nflag;
528                   break;
529
530                case 'v':
531                case 'V':
532                   ++vflag;
533                   break;
534
535                default:
536                   usage("Unknown flag");
537             }
538          }
539          argv[i] = 0;
540          --nfile;
541       } else if (!gotpattern) {
542          compile(p);
543          argv[i] = 0;
544          ++gotpattern;
545          --nfile;
546       }
547    }
548    if (!gotpattern)
549       usage("No pattern");
550    if (nfile == 0)
551       grep(stdin, 0);
552    else {
553       fflag = fflag ^ (nfile > 0);
554       for (i=1; i < argc; ++i) {
555          if (p = argv[i]) {
556             if ((f=fopen(p, "r")) == NULL)
557                cant(p);
558             else {
559                grep(f, p);
560                fclose(f);
561             }
562          }
563       }
564    }
565    return 0;
566 }
567
568 /* vim: set expandtab ts=4 sw=3 sts=3 tw=80 :*/