home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / textprocess / grep_2 / release / c / grep < prev    next >
Text File  |  1998-09-23  |  36KB  |  1,202 lines
  1. /*->c.grep */
  2.  
  3. /* grep - print lines matching an extended regular expression
  4.    Copyright (C) 1988 Free Software Foundation, Inc.
  5.                       Written June, 1988 by Mike Haertel
  6.                       BMG speedups added July, 1988
  7.                         by James A. Woods and Arthur David Olson
  8.  
  9.                        NO WARRANTY
  10.  
  11.   BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY
  12. NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT
  13. WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC,
  14. RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS"
  15. WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
  16. BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17. FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY
  18. AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE
  19. DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
  20. CORRECTION.
  21.  
  22.  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M.
  23. STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY
  24. WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE
  25. LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR
  26. OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
  27. USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR
  28. DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR
  29. A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS
  30. PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
  31. DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  32.  
  33.                 GENERAL PUBLIC LICENSE TO COPY
  34.  
  35.   1. You may copy and distribute verbatim copies of this source file
  36. as you receive it, in any medium, provided that you conspicuously and
  37. appropriately publish on each copy a valid copyright notice "Copyright
  38.  (C) 1988 Free Software Foundation, Inc."; and include following the
  39. copyright notice a verbatim copy of the above disclaimer of warranty
  40. and of this License.  You may charge a distribution fee for the
  41. physical act of transferring a copy.
  42.  
  43.   2. You may modify your copy or copies of this source file or
  44. any portion of it, and copy and distribute such modifications under
  45. the terms of Paragraph 1 above, provided that you also do the following:
  46.  
  47.     a) cause the modified files to carry prominent notices stating
  48.     that you changed the files and the date of any change; and
  49.  
  50.     b) cause the whole of any work that you distribute or publish,
  51.     that in whole or in part contains or is a derivative of this
  52.     program or any part thereof, to be licensed at no charge to all
  53.     third parties on terms identical to those contained in this
  54.     License Agreement (except that you may choose to grant more extensive
  55.     warranty protection to some or all third parties, at your option).
  56.  
  57.     c) You may charge a distribution fee for the physical act of
  58.     transferring a copy, and you may at your option offer warranty
  59.     protection in exchange for a fee.
  60.  
  61. Mere aggregation of another unrelated program with this program (or its
  62. derivative) on a volume of a storage or distribution medium does not bring
  63. the other program under the scope of these terms.
  64.  
  65.   3. You may copy and distribute this program or any portion of it in
  66. compiled, executable or object code form under the terms of Paragraphs
  67. 1 and 2 above provided that you do the following:
  68.  
  69.     a) accompany it with the complete corresponding machine-readable
  70.     source code, which must be distributed under the terms of
  71.     Paragraphs 1 and 2 above; or,
  72.  
  73.     b) accompany it with a written offer, valid for at least three
  74.     years, to give any third party free (except for a nominal
  75.     shipping charge) a complete machine-readable copy of the
  76.     corresponding source code, to be distributed under the terms of
  77.     Paragraphs 1 and 2 above; or,
  78.  
  79.     c) accompany it with the information you received as to where the
  80.     corresponding source code may be obtained.  (This alternative is
  81.     allowed only for noncommercial distribution and only if you
  82.     received the program in object code or executable form alone.)
  83.  
  84. For an executable file, complete source code means all the source code for
  85. all modules it contains; but, as a special exception, it need not include
  86. source code for modules which are standard libraries that accompany the
  87. operating system on which the executable file runs.
  88.  
  89.   4. You may not copy, sublicense, distribute or transfer this program
  90. except as expressly provided under this License Agreement.  Any attempt
  91. otherwise to copy, sublicense, distribute or transfer this program is void and
  92. your rights to use the program under this License agreement shall be
  93. automatically terminated.  However, parties who have received computer
  94. software programs from you with this License Agreement will not have
  95. their licenses terminated so long as such parties remain in full compliance.
  96.  
  97.   5. If you wish to incorporate parts of this program into other free
  98. programs whose distribution conditions are different, write to the Free
  99. Software Foundation at 675 Mass Ave, Cambridge, MA 02139.  We have not yet
  100. worked out a simple rule that can be stated here, but we will often permit
  101. this.  We will be guided by the two goals of preserving the free status of
  102. all derivatives our free software and of promoting the sharing and reuse of
  103. software.
  104.  
  105.  
  106. In other words, you are welcome to use, share and improve this program.
  107. You are forbidden to forbid anyone else to use, share and improve
  108. what you give them.   Help stamp out software-hoarding!  */
  109.  
  110. /*
  111.  
  112. #include <ctype.h>
  113. #include <stdio.h>
  114. #ifdef USG
  115. #include <memory.h>
  116. #include <string.h>
  117. #else
  118. #include <strings.h>
  119. #endif
  120.  */
  121.  
  122. #ifdef ACORN
  123. #include "kernel.h"
  124. #define DDEUtils_ThrowbackSend (0x42588)
  125. #define DDEUtils_ThrowbackStart (0x42587)
  126. #define DDEUtils_ThrowbackEnd (0x42589)
  127. #endif
  128.  
  129. #include <stdlib.h>
  130. #include <stdio.h>
  131. #include <string.h>
  132. #include <ctype.h>
  133.  
  134.  
  135. /* wildcards */
  136. extern int zxpand(char *);
  137. extern int znext(char *);
  138.  
  139.  
  140. #include "dfa.h"
  141. #include "regex.h"
  142.  
  143. #ifdef __STDC__
  144. extern getopt(int, char **, const char *);
  145. extern read(int, void *, int);
  146. extern open(const char *, int, ...);
  147. extern void close();
  148. #else
  149. extern char *strrchr();
  150. #endif
  151.  
  152.  
  153.  
  154. extern char *optarg;
  155. extern optind, opterr;
  156. /* extern errno; */
  157. /* extern char *sys_errlist[]; */
  158.  
  159. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  160.  
  161. /* Exit status codes. */
  162. #define MATCHES_FOUND 0         /* Exit 0 if no errors and matches found. */
  163. #define NO_MATCHES_FOUND 1      /* Exit 1 if no matches were found. */
  164. #define ERROR 2                 /* Exit 2 if some error occurred. */
  165.  
  166. /* Error is set true if something awful happened. */
  167. static int error;
  168.  
  169. /* The program name for error messages. */
  170. static char *prog;
  171.  
  172. /* We do all our own buffering by hand for efficiency. */
  173. static char *buffer;            /* The buffer itself, grown as needed. */
  174. static bufbytes;                /* Number of bytes in the buffer. */
  175. static size_t bufalloc;         /* Number of bytes allocated to the buffer. */
  176. static bufprev;                 /* Number of bytes that have been forgotten.
  177.                                    This is used to get byte offsets from the
  178.                                    beginning of the file. */
  179. static bufread;                 /* Number of bytes to get with each read(). */
  180.  
  181. static void
  182. initialize_buffer()
  183. {
  184.   bufread = 8192;
  185.   bufalloc = bufread + bufread / 2;
  186.   buffer = malloc(bufalloc);
  187.   if (! buffer)
  188.     {
  189.     /*  fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  190.               sys_errlist[errno]); */
  191.       fprintf(stderr, "%s: Memory exhausted \n", prog);
  192.  
  193.       exit(ERROR);
  194.     }
  195. }
  196.  
  197. /* The current input file. */
  198. static FILE * fd;
  199. static char *filename;
  200. static eof;
  201.  
  202. /* Fill the buffer retaining the last n bytes at the beginning of the
  203.    newly filled buffer (for backward context).  Returns the number of new
  204.    bytes read from disk. */
  205. static
  206. fill_buffer_retaining(n)
  207.      int n;
  208. {
  209.   char *p, *q;
  210.   int i;
  211.  
  212.   /* See if we need to grow the buffer. */
  213.   if (bufalloc - n <= bufread)
  214.     {
  215.       while (bufalloc - n <= bufread)
  216.         {
  217.           bufalloc *= 2;
  218.           bufread *= 2;
  219.         }
  220.       buffer = realloc(buffer, bufalloc);
  221.       if (! buffer)
  222.         {
  223.          /* fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  224.                   sys_errlist[errno]); */
  225.  
  226.           fprintf(stderr, "%s: Memory exhausted \n", prog);
  227.  
  228.           exit(ERROR);
  229.         }
  230.     }
  231.  
  232.   bufprev += bufbytes - n;
  233.  
  234.   /* Shift stuff down. */
  235.   for (i = n, p = buffer, q = p + bufbytes - n; i--; )
  236.     *p++ = *q++;
  237.   bufbytes = n;
  238.  
  239.   if (eof)
  240.     return 0;
  241.  
  242.   /* Read in new stuff. */
  243.   i = fread(buffer + bufbytes, 1, bufread, fd);    /* read(fd,... dp */
  244.  
  245.  
  246.  
  247.   if (i < 0)
  248.     {
  249. /*    fprintf(stderr, "%s: read on %s failed (%s)\n", prog,
  250.               filename ? filename : "<stdin>", sys_errlist[errno]); */
  251.  
  252.       fprintf(stderr, "%s: read on %s failed \n", prog,
  253.               filename ? filename : "<stdin>" );
  254.  
  255.       error = 1;
  256.     }
  257.  
  258.   /* Kludge to pretend every nonempty file ends with a newline. */
  259.   if (i == 0 && bufbytes > 0 && buffer[bufbytes - 1] != '\n')
  260.     {
  261.       eof = i = 1;
  262.       buffer[bufbytes] = '\n';
  263.     }
  264.  
  265.   bufbytes += i;
  266.   return i;
  267. }
  268.  
  269. /* Various flags set according to the argument switches. */
  270. static trailing_context;        /* Lines of context to show after matches. */
  271. static leading_context;         /* Lines of context to show before matches. */
  272. static byte_count;              /* Precede output lines the byte count of the
  273.                                    first character on the line. */
  274. static no_filenames;            /* Do not display filenames. */
  275. static line_numbers;            /* Precede output lines with line numbers. */
  276. static throwback;               /* Precede output lines with line numbers. */
  277. static silent;                  /* Produce no output at all.  This switch
  278.                                    is bogus, ever hear of /dev/null? */
  279. static nonmatching_lines;       /* Print lines that don't match the regexp. */
  280.  
  281. static bmgexec;                 /* Invoke Boyer-Moore-Gosper routines */
  282.  
  283. /* The compiled regular expression lives here. */
  284. static struct regexp reg;
  285.  
  286. /* The compiled regular expression for the backtracking matcher lives here. */
  287. static struct re_pattern_buffer regex;
  288.  
  289. /* Pointer in the buffer after the last character printed. */
  290. static char *printed_limit;
  291.  
  292. /* True when printed_limit has been artifically advanced without printing
  293.    anything. */
  294. static int printed_limit_fake;
  295.  
  296. /* Print a line at the given line number, returning the number of
  297.    characters actually printed.  Matching is true if the line is to
  298.    be considered a "matching line".  This is only meaningful if
  299.    surrounding context is turned on. */
  300. static
  301. print_line(p, number, matching)
  302.      char *p;
  303.      int number;
  304.      int matching;
  305. {
  306.   int count = 0;
  307.  
  308.   if (silent)
  309.     {
  310.       do
  311.         ++count;
  312.       while (*p++ != '\n');
  313.       printed_limit_fake = 0;
  314.       printed_limit = p;
  315.       return count;
  316.     }
  317.  
  318.   if (filename && !no_filenames)
  319.     printf("%s%c", filename, matching ? ':' : '-');
  320.   if (byte_count)
  321.     printf("%d%c", p - buffer + bufprev, matching ? ':' : '-');
  322.   if (line_numbers)
  323.     printf("%d%c", number, matching ? ':' : '-');
  324. #ifdef ACORN
  325.   if (throwback && matching)
  326.   {
  327.     _kernel_swi_regs ARM;
  328.  
  329.     char buf[200];
  330.     char *p2=p;
  331.     char *b=buf;
  332.     int c=0;
  333.     do
  334.     {
  335.       *b++ = *p2;
  336.       c++;
  337.     } while (*p2++ != '\n' && (c<199));
  338.  
  339.     *(--b) = '\0';
  340.     ARM.r[0]=2; /* Informational */
  341.     ARM.r[2]=(int)filename;
  342.     ARM.r[3]=number;
  343.     ARM.r[4]=0; /* Warning? */
  344.     ARM.r[5]=(int)buf; /* message */
  345.  
  346.     _kernel_swi(DDEUtils_ThrowbackSend,&ARM,&ARM);
  347.   }
  348. #endif
  349.   do
  350.     {
  351.       ++count;
  352.       putchar(*p);
  353.     }
  354.   while (*p++ != '\n');
  355.   printed_limit_fake = 0;
  356.   printed_limit = p;
  357.   return count;
  358. }
  359.  
  360. /* Print matching or nonmatching lines from the current file.  Returns a
  361.    count of matching or nonmatching lines. */
  362. static
  363. grep()
  364. {
  365.   int retain = 0;               /* Number of bytes to retain on next call
  366.                                    to fill_buffer_retaining(). */
  367.   char *search_limit;           /* Pointer to the character after the last
  368.                                    newline in the buffer. */
  369.   char saved_char;              /* Character after the last newline. */
  370.   char *resume;                 /* Pointer to where to resume search. */
  371.   int resume_index = 0;         /* Count of characters to ignore after
  372.                                    refilling the buffer. */
  373.   int line_count = 1;           /* Line number. */
  374.   int try_backref;              /* Set to true if we need to verify the
  375.                                    match with a backtracking matcher. */
  376.   int initial_line_count;       /* Line count at beginning of last search. */
  377.   char *match;                  /* Pointer to the first character after the
  378.                                    string matching the regexp. */
  379.   int match_count = 0;          /* Count of matching lines. */
  380.   char *matching_line;          /* Pointer to first character of the matching
  381.                                    line, or of the first line of context to
  382.                                    print if context is turned on. */
  383.   char *real_matching_line;     /* Pointer to the first character of the
  384.                                    real matching line. */
  385.   char *next_line;              /* Pointer to first character of the line
  386.                                    following the matching line. */
  387.   int pending_lines = 0;        /* Lines of context left over from last match
  388.                                    that we have to print. */
  389.   static first_match = 1;       /* True when nothing has been printed. */
  390.   int i;
  391.   char *tmp;
  392.   char *execute();
  393.  
  394.   printed_limit_fake = 0;
  395.  
  396.   while (fill_buffer_retaining(retain) > 0)
  397.     {
  398.       /* Find the last newline in the buffer. */
  399.       search_limit = buffer + bufbytes;
  400.       while (search_limit > buffer && search_limit[-1] != '\n')
  401.         --search_limit;
  402.       if (search_limit == buffer)
  403.         {
  404.           retain = bufbytes;
  405.           continue;
  406.         }
  407.  
  408.       /* Save the character after the last newline so regexecute can write
  409.          its own sentinel newline. */
  410.       saved_char = *search_limit;
  411.  
  412.       /* Search the buffer for a match. */
  413.       printed_limit = buffer;
  414.       resume = buffer + resume_index;
  415.       initial_line_count = line_count;
  416.  
  417.       while (match = execute(®, resume, search_limit, 0, &line_count, &try_backref))
  418.         {
  419.           ++match_count;
  420.  
  421.           /* Find the beginning of the matching line. */
  422.           matching_line = match;
  423.           while (matching_line > resume && matching_line[-1] != '\n')
  424.             --matching_line;
  425.           real_matching_line = matching_line;
  426.  
  427.           /* Find the beginning of the next line. */
  428.           next_line = match;
  429.           while (next_line < search_limit && *next_line++ != '\n')
  430.             ;
  431.  
  432.           /* If a potential backreference is indicated, try it out with
  433.              a backtracking matcher to make sure the line is a match. */
  434.           if (try_backref && re_search(®ex, matching_line,
  435.                                        next_line - matching_line - 1,
  436.                                        0,
  437.                                        next_line - matching_line - 1,
  438.                                        NULL) < 0)
  439.             {
  440.               resume = next_line;
  441.               if (resume == search_limit)
  442.                 break;
  443.               else
  444.                 continue;
  445.             }
  446.  
  447.           /* Print leftover lines from last time.  If nonmatching_lines is
  448.              turned on, print these as if they were matching lines. */
  449.           while (resume < matching_line && pending_lines)
  450.             {
  451.               resume += print_line(resume, initial_line_count++,
  452.                                    nonmatching_lines);
  453.               --pending_lines;
  454.             }
  455.  
  456.           /* Print out the matching or nonmatching lines as necessary. */
  457.           if (! nonmatching_lines)
  458.             {
  459.               /* Back up over leading context if necessary. */
  460.               for (i = leading_context; matching_line > printed_limit
  461.                    && i; --i)
  462.                 {
  463.                   while (matching_line > printed_limit
  464.                          && (--matching_line)[-1] != '\n')
  465.                     ;
  466.                   --line_count;
  467.                 }
  468.  
  469.               /* If context is enabled, we may have to print a separator. */
  470.               if ((leading_context || trailing_context) && !silent
  471.                   && !first_match && (printed_limit_fake || matching_line
  472.                                       > printed_limit))
  473.                 printf("----------\n");
  474.               first_match = 0;
  475.  
  476.               /* Print the matching line and its leading context. */
  477.               while (matching_line < real_matching_line)
  478.                 matching_line += print_line(matching_line, line_count++, 0);
  479.               matching_line += print_line(matching_line, line_count++, 1);
  480.  
  481.               /* If there's trailing context, leave some lines pending until
  482.                  next time. */
  483.               pending_lines = trailing_context;
  484.             }
  485.           else if (matching_line > resume)
  486.             {
  487.               char *real_resume = resume;
  488.  
  489.               /* Back up over leading context if necessary. */
  490.               for (i = leading_context; resume > printed_limit && i; --i)
  491.                 {
  492.                   while (resume > printed_limit && (--resume)[-1] != '\n')
  493.                     ;
  494.                   --initial_line_count;
  495.                 }
  496.  
  497.               /* If context is enabled, we may have to print a separator. */
  498.               if ((leading_context || trailing_context) && !silent
  499.                   && !first_match && (printed_limit_fake || resume
  500.                                       > printed_limit))
  501.                 printf("----------\n");
  502.               first_match = 0;
  503.  
  504.               /* Print out the presumably matching leading context. */
  505.               while (resume < real_resume)
  506.                 resume += print_line(resume, initial_line_count++, 0);
  507.  
  508.               /* Print out the nonmatching lines prior to the matching line. */
  509.               while (resume < matching_line)
  510.                 resume += print_line(resume, initial_line_count++, 1);
  511.  
  512.               /* Deal with trailing context. */
  513.               if (trailing_context)
  514.                 {
  515.                   print_line(matching_line, line_count, 0);
  516.                   pending_lines = trailing_context - 1;
  517.                 }
  518.  
  519.               /* Count the current line. */
  520.               ++line_count;
  521.             }
  522.           else
  523.             {
  524.               /* The line immediately after a matching line has to be printed
  525.                  because it was pending. */
  526.               if (pending_lines > 0)
  527.                 {
  528.                   --pending_lines;
  529.                   print_line(matching_line, line_count, 0);
  530.                 }
  531.               ++line_count;
  532.             }
  533.  
  534.           /* Resume searching at the beginning of the next line. */
  535.           initial_line_count = line_count;
  536.           resume = next_line;
  537.  
  538.           if (resume == search_limit)
  539.             break;
  540.         }
  541.  
  542.       /* Restore the saved character. */
  543.       *search_limit = saved_char;
  544.  
  545.       if (! nonmatching_lines)
  546.         {
  547.           while (resume < search_limit && pending_lines)
  548.             {
  549.               resume += print_line(resume, initial_line_count++, 0);
  550.               --pending_lines;
  551.             }
  552.         }
  553.       else if (search_limit > resume)
  554.         {
  555.           char *initial_resume = resume;
  556.  
  557.           /* Back up over leading context if necessary. */
  558.           for (i = leading_context; resume > printed_limit && i; --i)
  559.             {
  560.               while (resume > printed_limit && (--resume)[-1] != '\n')
  561.                 ;
  562.               --initial_line_count;
  563.             }
  564.  
  565.           /* If context is enabled, we may have to print a separator. */
  566.           if ((leading_context || trailing_context) && !silent
  567.               && !first_match && (printed_limit_fake || resume
  568.                                   > printed_limit))
  569.             printf("----------\n");
  570.           first_match = 0;
  571.  
  572.           /* Print out all the nonmatching lines up to the search limit. */
  573.           while (resume < initial_resume)
  574.             resume += print_line(resume, initial_line_count++, 0);
  575.           while (resume < search_limit)
  576.             resume += print_line(resume, initial_line_count++, 1);
  577.  
  578.           pending_lines = trailing_context;
  579.           resume_index = 0;
  580.           retain = bufbytes - (search_limit - buffer);
  581.           continue;
  582.         }
  583.  
  584.       /* Save the trailing end of the buffer for possible use as leading
  585.          context in the future. */
  586.       i = leading_context;
  587.       tmp = search_limit;
  588.       while (tmp > printed_limit && i--)
  589.         while (tmp > printed_limit && (--tmp)[-1] != '\n')
  590.           ;
  591.       resume_index = search_limit - tmp;
  592.       retain = bufbytes - (tmp - buffer);
  593.       if (tmp > printed_limit)
  594.         printed_limit_fake = 1;
  595.     }
  596.  
  597.   return nonmatching_lines ? line_count - match_count : match_count;
  598. }
  599.  
  600. void
  601. usage_and_die()
  602. {
  603. #ifndef ACORN
  604.   fprintf(stderr,
  605. "usage: %s [-CTVbchilnsvwx] [-<num>] [-AB <num>] [-f file] [-e] expr [files]\n",
  606.           prog);
  607. #else
  608.   fprintf(stderr,"\
  609. usage: %s [-CTVbchilnsvwx] [-<num>] [-AB <num>] [-f file] [-e] expr [files]\n\
  610. \n\
  611. Options:\n\
  612.     -<num>      Print <num> lines of context around matches\n\
  613.     -A <num>    Print <num> lines of context after matches\n\
  614.     -B <num>    Print <num> lines of context before matches\n\
  615.     -b          Print the byte offset before each match\n\
  616.     -C          Print 2 lines of context around matches\n\
  617.     -c          Print a total count of matching lines only\n\
  618.     -d          Print debugging information\n\
  619.     -e <expr>   Search for <expr>\n\
  620.     -f <file>   Take search expressions from <file>\n\
  621.     -h          Do not display filenames on matches\n\
  622.     -i          Ignore case in matches\n\
  623.     -l          List files containing matches only\n\
  624.     -n          Print the line number before each match\n\
  625.     -s          Run silently (no output except error messages)\n\
  626.     -T          Produce throwback output\n\
  627.     -V          Print the program version number\n\
  628.     -v          Print lines which do NOT match\n\
  629.     -w          Only match complete words\n\
  630.     -x          Only match complete lines\n\
  631. \n",prog);
  632. #endif
  633.  
  634.   exit(ERROR);
  635. }
  636.  
  637. static char version[] = "GNU e?grep, version 1.3";
  638.  
  639. main(argc, argv)
  640.      int argc;
  641.      char **argv;
  642. {
  643.   int c;
  644.   int ignore_case = 0;          /* Compile the regexp to ignore case. */
  645.   char *the_regexp = 0;         /* The regular expression. */
  646.   int regexp_len;               /* Length of the regular expression. */
  647.   char *regexp_file = 0;        /* File containing parallel regexps. */
  648.   int count_lines = 0;          /* Display only a count of matching lines. */
  649.   int list_files = 0;           /* Display only the names of matching files. */
  650.   int whole_word = 0;           /* Insist that the regexp match a word only. */
  651.   int whole_line = 0;           /* Insist on matching only whole lines. */
  652.   int line_count = 0;           /* Count of matching lines for a file. */
  653.   int matches_found = 0;        /* True if matches were found. */
  654.   char *regex_errmesg;          /* Error message from regex routines. */
  655.   char translate[_NOTCHAR];     /* Translate table for case conversion
  656.                                    (needed by the backtracking matcher). */
  657.  
  658.   if (prog = strrchr(argv[0], '/'))
  659.     ++prog;
  660.   else
  661.     prog = argv[0];
  662.  
  663. #ifdef ACORN
  664.   {
  665.     char *x=getenv("Grep$Throwback");
  666.     if (x!=NULL)
  667.     {
  668.       throwback=atoi(x); /* Gerph: I'm lazy */
  669.     }
  670.   }
  671. #endif
  672.  
  673.   opterr = 0;
  674.   while ((c = getopt(argc, argv, "0123456789A:B:CVbce:f:hilnsvwxT")) != EOF)
  675.     switch (c)
  676.       {
  677.       case '?':
  678.         usage_and_die();
  679.         break;
  680.  
  681.       case '0':
  682.       case '1':
  683.       case '2':
  684.       case '3':
  685.       case '4':
  686.       case '5':
  687.       case '6':
  688.       case '7':
  689.       case '8':
  690.       case '9':
  691.         trailing_context = 10 * trailing_context + c - '0';
  692.         leading_context = 10 * leading_context + c - '0';
  693.         break;
  694.  
  695.       case 'A':
  696.         if (! sscanf(optarg, "%d", &trailing_context)
  697.             || trailing_context < 0)
  698.           usage_and_die();
  699.         break;
  700.  
  701.       case 'B':
  702.         if (! sscanf(optarg, "%d", &leading_context)
  703.             || leading_context < 0)
  704.           usage_and_die();
  705.         break;
  706.  
  707.       case 'C':
  708.         trailing_context = leading_context = 2;
  709.         break;
  710.  
  711.       case 'V':
  712.         fprintf(stderr, "%s\n", version);
  713. #ifdef ACORN
  714.         /* I found it difficult to get hold of this source, partly because
  715.            I didn't know who to contact. This should help. */
  716.         fprintf(stderr, "Port by David Pilling. Modifications by Justin Fletcher.\n");
  717. #endif
  718.         break;
  719.  
  720.       case 'b':
  721.         byte_count = 1;
  722.         break;
  723.  
  724.       case 'c':
  725.         count_lines = 1;
  726.         silent = 1;
  727.         break;
  728.  
  729.       case 'e':
  730.         /* It doesn't make sense to mix -f and -e. */
  731.         if (regexp_file)
  732.           usage_and_die();
  733.         the_regexp = optarg;
  734.         break;
  735.  
  736.       case 'f':
  737.         /* It doesn't make sense to mix -f and -e. */
  738.         if (the_regexp)
  739.           usage_and_die();
  740.         regexp_file = optarg;
  741.         break;
  742.  
  743.       case 'h':
  744.         no_filenames = 1;
  745.         break;
  746.  
  747.       case 'i':
  748.         ignore_case = 1;
  749.         for (c = 0; c < _NOTCHAR; ++c)
  750.           if (isupper(c))
  751.             translate[c] = tolower(c);
  752.           else
  753.             translate[c] = c;
  754.         regex.translate = translate;
  755.         break;
  756.  
  757.       case 'l':
  758.         list_files = 1;
  759.         silent = 1;
  760.         break;
  761.  
  762.       case 'n':
  763.         line_numbers = 1;
  764.         break;
  765.  
  766.       case 'T':
  767.         throwback = 1;
  768.         break;
  769.  
  770.       case 's':
  771.         silent = 1;
  772.         break;
  773.  
  774.       case 'v':
  775.         nonmatching_lines = 1;
  776.         break;
  777.  
  778.       case 'w':
  779.         whole_word = 1;
  780.         break;
  781.  
  782.       case 'x':
  783.         whole_line = 1;
  784.         break;
  785.  
  786.       default:
  787.         /* This can't happen. */
  788.         fprintf(stderr, "%s: getopt(3) let one by!\n", prog);
  789.         usage_and_die();
  790.         break;
  791.       }
  792.  
  793. #define EGREP
  794.  
  795.   /* Set the syntax depending on whether we are EGREP or not. */
  796. #ifdef EGREP
  797.   regsyntax(RE_SYNTAX_EGREP, ignore_case);
  798.   re_set_syntax(RE_SYNTAX_EGREP);
  799. #else
  800.   regsyntax(RE_SYNTAX_GREP, ignore_case);
  801.   re_set_syntax(RE_SYNTAX_GREP);
  802. #endif
  803.  
  804.   /* Compile the regexp according to all the options. */
  805.   if (regexp_file)
  806.     {
  807.       FILE *fp = fopen(regexp_file, "r");
  808.       int len = 256;
  809.       int i = 0;
  810.  
  811.       if (! fp)
  812.         {
  813.          /* fprintf(stderr, "%s: %s: %s\n", prog, regexp_file,
  814.                   sys_errlist[errno]); */
  815.  
  816.             fprintf(stderr, "%s: %s: (failed to open)\n", prog, regexp_file);
  817.  
  818.           exit(ERROR);
  819.         }
  820.  
  821.       the_regexp = malloc(len);
  822.       while ((c = getc(fp)) != EOF)
  823.         {
  824.           the_regexp[i++] = c;
  825.           if (i == len)
  826.             the_regexp = realloc(the_regexp, len *= 2);
  827.         }
  828.       fclose(fp);
  829.       /* Nuke the concluding newline so we won't match the empty string. */
  830.       if (i > 0 && the_regexp[i - 1] == '\n')
  831.         --i;
  832.       regexp_len = i;
  833.     }
  834.   else if (! the_regexp)
  835.     {
  836.       if (optind >= argc)
  837.         usage_and_die();
  838.       the_regexp = argv[optind++];
  839.       regexp_len = strlen(the_regexp);
  840.     }
  841.   else
  842.     regexp_len = strlen(the_regexp);
  843.  
  844.   if (whole_word || whole_line)
  845.     {
  846.       char *n = malloc(regexp_len + 8);
  847.       int i = 0;
  848.  
  849.       if (whole_line)
  850.         n[i++] = '^';
  851.       else
  852.         n[i++] = '\\', n[i++] = '<';
  853.       if (*prog != 'e')
  854.         n[i++] = '\\';
  855.       n[i++] = '(';
  856.       memcpy(n + i, the_regexp, regexp_len);
  857.       i += regexp_len;
  858.       if (*prog != 'e')
  859.         n[i++] = '\\';
  860.       n[i++] = ')';
  861.       if (whole_line)
  862.         n[i++] = '$';
  863.       else
  864.         n[i++] = '\\', n[i++] = '>';
  865.       the_regexp = n;
  866.       regexp_len = i;
  867.     }
  868.  
  869.   regcompile(the_regexp, regexp_len, ®, 1);
  870.  
  871.   if (regex_errmesg = re_compile_pattern(the_regexp, regexp_len, ®ex))
  872.     regerror(regex_errmesg);
  873.  
  874.   /*
  875.     Find the longest metacharacter-free string which must occur in the
  876.     regexpr, before short-circuiting regexecute() with Boyer-Moore-Gosper.
  877.     (Conjecture:  The problem in general is NP-complete.)  If there is no
  878.     such string (like for many alternations), then default to full automaton
  879.     search.  regmust() code and heuristics [see dfa.c] courtesy
  880.     Arthur David Olson.
  881.     */
  882.   if (line_numbers == 0 && nonmatching_lines == 0 && throwback == 0)
  883.     {
  884.       if (reg.mustn == 0 || reg.mustn == MUST_MAX ||
  885.           strchr(reg.must, '\0') != reg.must + reg.mustn)
  886.         bmgexec = 0;
  887.       else
  888.         {
  889.           reg.must[reg.mustn] = '\0';
  890.           if (getenv("MUSTDEBUG") != NULL)
  891.             (void) printf("must have: \"%s\"\n", reg.must);
  892.           bmg_setup(reg.must, ignore_case);
  893.           bmgexec = 1;
  894.         }
  895.     }
  896.  
  897.  
  898. /*
  899.   if (argc - optind < 2)    taken out for wildcards
  900.     no_filenames = 1;
  901.  
  902.  */
  903.  
  904. #ifdef ACORN
  905.   if (throwback)
  906.   {
  907.     _kernel_swi_regs ARM;
  908.     _kernel_swi(DDEUtils_ThrowbackStart,&ARM,&ARM);
  909.   }
  910. #endif
  911.  
  912.   initialize_buffer();
  913.  
  914.   if (argc > optind)
  915.     while (optind < argc)
  916.       {
  917.         char wbuf[132];           /* wildcards */
  918.  
  919.         bufprev = eof = 0;
  920.  
  921.         strcpy(wbuf,argv[optind++]);
  922.         filename=wbuf;             /* filename = argv[optind++];  */
  923.  
  924.         zxpand(filename);          /* wildcards   */
  925.         while(znext(filename))     /*             */
  926.        {                           /*             */
  927.  
  928.         fd = fopen(filename,"r");  /* open(filename,0,0) dp */
  929.         if (!fd)
  930.           {
  931.             /* fprintf(stderr, "%s: %s: %s\n", prog, filename,
  932.                     sys_errlist[errno]);  */
  933.  
  934.             fprintf(stderr, "%s: %s: (failed to open)\n", prog, filename);
  935.  
  936.             error = 1;
  937.             continue;
  938.           }
  939.         if (line_count = grep())
  940.           matches_found = 1;
  941.         fclose(fd);
  942.         if (count_lines)
  943.           if (!no_filenames)
  944.             printf("%s:%d\n", filename, line_count);
  945.           else
  946.             printf("%d\n", line_count);
  947.         else if (list_files && line_count)
  948.           printf("%s\n", filename);
  949.  
  950.        } /* wildcards */
  951.  
  952.       }
  953.   else
  954.     {
  955.  
  956.       fd=stdin; /* added dp */
  957.  
  958.       if (line_count = grep())
  959.         matches_found = 1;
  960.       if (count_lines)
  961.         printf("%d\n", line_count);
  962.       else if (list_files && line_count)
  963.         printf("<stdin>\n");
  964.     }
  965.  
  966. #ifdef ACORN
  967.   if (throwback)
  968.   {
  969.     _kernel_swi_regs ARM;
  970.     _kernel_swi(DDEUtils_ThrowbackEnd,&ARM,&ARM);
  971.   }
  972. #endif
  973.  
  974.   if (error)
  975.     exit(ERROR);
  976.   if (matches_found)
  977.     exit(MATCHES_FOUND);
  978.   exit(NO_MATCHES_FOUND);
  979. }
  980.  
  981. /* Needed by the regexp routines.  This could be fancier, especially when
  982.    dealing with parallel regexps in files. */
  983. void
  984. regerror(s)
  985.      const char *s;
  986. {
  987.   fprintf(stderr, "%s: %s\n", prog, s);
  988.   exit(ERROR);
  989. }
  990.  
  991. /*
  992.    bmg_setup() and bmg_search() adapted from:
  993.      Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  994.      original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  995.      experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  996.      practical value.  However, to improve for worst case input, integrating
  997.      the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  998.      February 1986) deserves consideration.
  999.  
  1000.      James A. Woods                             Copyleft (C) 1986, 1988
  1001.      NASA Ames Research Center
  1002. */
  1003.  
  1004. char *
  1005. execute(r, begin, end, newline, count, try_backref)
  1006.   struct regexp *r;
  1007.   char *begin;
  1008.   char *end;
  1009.   int newline;
  1010.   int *count;
  1011.   int *try_backref;
  1012. {
  1013.   register char *p, *s;
  1014.   char *match;
  1015.   char *start = begin;
  1016.   char save;                    /* regexecute() sentinel */
  1017.   int len;
  1018.   char *bmg_search();
  1019.  
  1020.   if (!bmgexec)                 /* full automaton search */
  1021.     return(regexecute(r, begin, end, newline, count, try_backref));
  1022.   else
  1023.     {
  1024.       len = end - begin;
  1025.       while ((match = bmg_search((unsigned char *) start, len)) != NULL)
  1026.         {
  1027.           p = match;            /* narrow search range to submatch line */
  1028.           while (p > begin && *p != '\n')
  1029.             p--;
  1030.           s = match;
  1031.           while (s < end && *s != '\n')
  1032.             s++;
  1033.           s++;
  1034.  
  1035.           save = *s;
  1036.           *s = '\0';
  1037.           match = regexecute(r, p, s, newline, count, try_backref);
  1038.           *s = save;
  1039.  
  1040.           if (match != NULL)
  1041.             return((char *) match);
  1042.           else
  1043.             {
  1044.               start = s;
  1045.               len = end - start;
  1046.             }
  1047.         }
  1048.       return(NULL);
  1049.     }
  1050. }
  1051.  
  1052. #include <ctype.h>
  1053. int             delta0[256];
  1054. unsigned char   cmap[256];              /* (un)folded characters */
  1055. unsigned char   pattern[5000];
  1056. int             patlen;
  1057.  
  1058. char *
  1059. bmg_search(buffer, buflen)
  1060.   unsigned char *buffer;
  1061.   int buflen;
  1062. {
  1063.   register unsigned char *k, *strend, *s, *buflim;
  1064.   register int t;
  1065.   int j;
  1066.  
  1067.   if (patlen > buflen)
  1068.     return NULL;
  1069.  
  1070.   buflim = buffer + buflen;
  1071.   if (buflen > patlen * 4)
  1072.     strend = buflim - patlen * 4;
  1073.   else
  1074.     strend = buffer;
  1075.  
  1076.   s = buffer;
  1077.   k = buffer + patlen - 1;
  1078.  
  1079.   for (;;)
  1080.     {
  1081.       /* The dreaded inner loop, revisited. */
  1082.       while (k < strend && (t = delta0[*k]))
  1083.         {
  1084.           k += t;
  1085.           k += delta0[*k];
  1086.           k += delta0[*k];
  1087.         }
  1088.       while (k < buflim && delta0[*k])
  1089.         ++k;
  1090.       if (k == buflim)
  1091.         break;
  1092.  
  1093.       j = patlen - 1;
  1094.       s = k;
  1095.       while (cmap[*--s] == pattern[--j])
  1096.         ;
  1097.       /*
  1098.         delta-less shortcut for literati, but
  1099.         short shrift for genetic engineers.
  1100.       */
  1101.       if (j >= 0)
  1102.         k++;
  1103.       else              /* submatch */
  1104.         return ((char *)k);
  1105.     }
  1106.   return(NULL);
  1107. }
  1108.  
  1109. bmg_setup(pat, folded)                  /* compute "boyer-moore" delta table */
  1110.   char *pat;
  1111.   int folded;
  1112. {                                       /* ... HAKMEM lives ... */
  1113.   int j;
  1114.  
  1115.   patlen = strlen(pat);
  1116.  
  1117.   if (folded)                           /* fold case while saving pattern */
  1118.     for (j = 0; j < patlen; j++)
  1119.       pattern[j] = (isupper((int) pat[j]) ?
  1120.         (char) tolower((int) pat[j]) : pat[j]);
  1121.   else
  1122.       memcpy(pattern, pat, patlen);
  1123.  
  1124.   for (j = 0; j < 256; j++)
  1125.     {
  1126.       delta0[j] = patlen;
  1127.       cmap[j] = (char) j;               /* could be done at compile time */
  1128.     }
  1129.   for (j = 0; j < patlen - 1; j++)
  1130.     delta0[pattern[j]] = patlen - j - 1;
  1131.   delta0[pattern[patlen - 1]] = 0;
  1132.  
  1133.   if (folded)
  1134.     {
  1135.       for (j = 0; j < patlen - 1; j++)
  1136.         if (islower((int) pattern[j]))
  1137.           delta0[toupper((int) pattern[j])] = patlen - j - 1;
  1138.         if (islower((int) pattern[patlen - 1]))
  1139.           delta0[toupper((int) pattern[patlen - 1])] = 0;
  1140.       for (j = 'A'; j <= 'Z'; j++)
  1141.         cmap[j] = (char) tolower((int) j);
  1142.     }
  1143. }
  1144.  
  1145. #define USG
  1146.  
  1147. #ifndef USG
  1148.  
  1149. /* (groan) compatibility */
  1150.  
  1151. char *
  1152. strchr(s, c)
  1153.      char *s;
  1154. {
  1155.   return index(s, c);
  1156. }
  1157.  
  1158. char *
  1159. strrchr(s, c)
  1160.      char *s;
  1161. {
  1162.   return rindex(s, c);
  1163. }
  1164.  
  1165. char *
  1166. memcpy(d, s, n)
  1167.      char *d, *s;
  1168. {
  1169.   return bcopy(s, d, n);
  1170. }
  1171.  
  1172. #else
  1173.  
  1174. char *
  1175. index(s, c)
  1176.      char *s;
  1177. {
  1178.   return strchr(s, c);
  1179. }
  1180.  
  1181. char *
  1182. bcopy(s, d, n)
  1183.      char *s, *d;
  1184. {
  1185.   return memcpy(d, s, n);
  1186. }
  1187.  
  1188. char *
  1189. bzero(s, n)
  1190.      char *s;
  1191. {
  1192.   return memset(s, 0, n);
  1193. }
  1194.  
  1195. bcmp(s, t, n)
  1196.      char *s, *t;
  1197. {
  1198.   return memcmp(s, t, n);
  1199. }
  1200.  
  1201. #endif
  1202.