home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / fileutil / tcggrep2.arj / GREP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-01-03  |  45.1 KB  |  1,658 lines
  1. /* grep - print lines matching an extended regular expression   -*-C-*-
  2.    Copyright (C) 1988 Free Software Foundation, Inc.
  3.                       Written June, 1988 by Mike Haertel
  4.                   BMG speedups added July, 1988
  5.             by James A. Woods and Arthur David Olson
  6.  
  7.                NO WARRANTY
  8.  
  9.   BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY
  10. NO WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT
  11. WHEN OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC,
  12. RICHARD M. STALLMAN AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS"
  13. WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
  14. BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  15. FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO THE QUALITY
  16. AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE PROGRAM PROVE
  17. DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
  18. CORRECTION.
  19.  
  20.  IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M.
  21. STALLMAN, THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY
  22. WHO MAY MODIFY AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE
  23. LIABLE TO YOU FOR DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR
  24. OTHER SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE
  25. USE OR INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR
  26. DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR
  27. A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS) THIS
  28. PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH
  29. DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  30.  
  31.         GENERAL PUBLIC LICENSE TO COPY
  32.  
  33.   1. You may copy and distribute verbatim copies of this source file
  34. as you receive it, in any medium, provided that you conspicuously and
  35. appropriately publish on each copy a valid copyright notice "Copyright
  36.  (C) 1988 Free Software Foundation, Inc."; and include following the
  37. copyright notice a verbatim copy of the above disclaimer of warranty
  38. and of this License.  You may charge a distribution fee for the
  39. physical act of transferring a copy.
  40.  
  41.   2. You may modify your copy or copies of this source file or
  42. any portion of it, and copy and distribute such modifications under
  43. the terms of Paragraph 1 above, provided that you also do the following:
  44.  
  45.     a) cause the modified files to carry prominent notices stating
  46.     that you changed the files and the date of any change; and
  47.  
  48.     b) cause the whole of any work that you distribute or publish,
  49.     that in whole or in part contains or is a derivative of this
  50.     program or any part thereof, to be licensed at no charge to all
  51.     third parties on terms identical to those contained in this
  52.     License Agreement (except that you may choose to grant more extensive
  53.     warranty protection to some or all third parties, at your option).
  54.  
  55.     c) You may charge a distribution fee for the physical act of
  56.     transferring a copy, and you may at your option offer warranty
  57.     protection in exchange for a fee.
  58.  
  59. Mere aggregation of another unrelated program with this program (or its
  60. derivative) on a volume of a storage or distribution medium does not bring
  61. the other program under the scope of these terms.
  62.  
  63.   3. You may copy and distribute this program or any portion of it in
  64. compiled, executable or object code form under the terms of Paragraphs
  65. 1 and 2 above provided that you do the following:
  66.  
  67.     a) accompany it with the complete corresponding machine-readable
  68.     source code, which must be distributed under the terms of
  69.     Paragraphs 1 and 2 above; or,
  70.  
  71.     b) accompany it with a written offer, valid for at least three
  72.     years, to give any third party free (except for a nominal
  73.     shipping charge) a complete machine-readable copy of the
  74.     corresponding source code, to be distributed under the terms of
  75.     Paragraphs 1 and 2 above; or,
  76.  
  77.     c) accompany it with the information you received as to where the
  78.     corresponding source code may be obtained.  (This alternative is
  79.     allowed only for noncommercial distribution and only if you
  80.     received the program in object code or executable form alone.)
  81.  
  82. For an executable file, complete source code means all the source code for
  83. all modules it contains; but, as a special exception, it need not include
  84. source code for modules which are standard libraries that accompany the
  85. operating system on which the executable file runs.
  86.  
  87.   4. You may not copy, sublicense, distribute or transfer this program
  88. except as expressly provided under this License Agreement.  Any attempt
  89. otherwise to copy, sublicense, distribute or transfer this program is void and
  90. your rights to use the program under this License agreement shall be
  91. automatically terminated.  However, parties who have received computer
  92. software programs from you with this License Agreement will not have
  93. their licenses terminated so long as such parties remain in full compliance.
  94.  
  95.   5. If you wish to incorporate parts of this program into other free
  96. programs whose distribution conditions are different, write to the Free
  97. Software Foundation at 675 Mass Ave, Cambridge, MA 02139.  We have not yet
  98. worked out a simple rule that can be stated here, but we will often permit
  99. this.  We will be guided by the two goals of preserving the free status of
  100. all derivatives our free software and of promoting the sharing and reuse of
  101. software.
  102.  
  103.  
  104. In other words, you are welcome to use, share and improve this program.
  105. You are forbidden to forbid anyone else to use, share and improve
  106. what you give them.   Help stamp out software-hoarding!  */
  107.  
  108. /*-
  109.   MODIFIED FOR MSDOS (MICROSOFT C 5.1) BY BARRY SCHWARTZ, SEPT. 1990.
  110.  
  111.   Includes the new option `-d <expression>' that has the same effect as
  112.   `-e <expression>' but strips enclosing quotes off of <expression>.
  113.  */
  114. /* modified for Turbo C Jim Segrave 00:28:49 Sat Nov 24 1990
  115.    added prototypes and include files, casts, etc. so it compiles
  116.    without warnings. Added environment variable GREP_OPTS which
  117.    supplies option flags. Added option -H to force output of
  118.    filenames, even if only one file is being grepped (I use a
  119.    micro-emacs macro for grep output which depends on the name
  120.    being present). it now compiles without warnings.
  121.    Added a help screen to replace terse usage and die message
  122.    renamed variable eof to is_eof, since it conflicts with a Turbo C
  123.    library routine
  124. */
  125. #include <ctype.h>
  126. #include <stdio.h>
  127. #ifdef USG
  128. #  ifdef __TURBOC__
  129. #    include <mem.h>
  130. #  else
  131. #    include <memory.h>
  132. #  endif
  133. #  include <string.h>
  134. #else
  135. #  include <strings.h>
  136. #endif
  137. #ifdef MSDOS
  138. #  include <fcntl.h>
  139. #  include <stddef.h>
  140. #  include "msdosmac.h"
  141. #    ifdef __TURBOC__
  142. #     include  <io.h>
  143. #    endif
  144. #endif
  145.  
  146. #include "dfa.h"
  147. #include "regex.h"
  148.  
  149. #if defined(__STDC__) 
  150.    extern getopt(int, char **, const char *);
  151.    extern read(int, void *, int);
  152.    extern open(const char *, int, ...);
  153.    extern void close();
  154. #else
  155.    #ifdef __TURBOC__
  156.       extern getopt(int, char **, const char *);
  157.    #else
  158.       extern char *strrchr();
  159.    #endif
  160. #endif
  161.  
  162. #ifdef __TURBOC__
  163.    static fill_buffer_retaining (int n);
  164.    char *execute (struct regexp *r, char *begin, char *end, int newline,
  165.    long *count, int *try_backref);
  166.    #ifdef GNU_GLOBBING
  167.      int globargv(int *argc, char ***argv, char **(*globber)(char *));
  168.    #endif
  169.    int getopt (int argc, char **argv, const char *optstring);
  170.    void usage_and_die (void);
  171.    void bmg_setup (char *pat, int folded);
  172.    static void initialize_buffer (void);
  173.    static long grep (void);
  174.    char *bmg_search (unsigned char *buffer, int buflen);
  175.    static print_line (char *p, long number, int matching);
  176. #endif
  177.  
  178. static char version[] = "GNU e?grep, version 1.5";
  179.  
  180. extern char *optarg;
  181. extern optind, opterr;
  182. #ifndef MSDOS    /* Avoid redefinition errors */
  183.    extern errno;
  184.    extern char *sys_errlist[];
  185. #endif
  186.  
  187. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  188.  
  189. /* Exit status codes. */
  190. #define MATCHES_FOUND 0        /* Exit 0 if no errors and matches found. */
  191. #define NO_MATCHES_FOUND 1    /* Exit 1 if no matches were found. */
  192. #define ERROR 2            /* Exit 2 if some error occurred. */
  193.  
  194. /* Error is set true if something awful happened. */
  195. static int error;
  196.  
  197. /* The program name for error messages. */
  198. static char *prog;
  199.  
  200. /* One of the flags determined by the options. */
  201. static byte_count;        /* Precede output lines the byte count of the
  202.                    first character on the line. */
  203.  
  204. /* We do all our own buffering by hand for efficiency. */
  205. static char *buffer;        /* The buffer itself, grown as needed. */
  206. static bufbytes;        /* Number of bytes in the buffer. */
  207. static size_t bufalloc;        /* Number of bytes allocated to the buffer. */
  208.  
  209. #ifndef MSDOS
  210.  
  211.   static bufprev;            /* Number of bytes that have been forgotten.
  212.                                     This is used to get byte offsets from the
  213.                                   beginning of the file. */
  214.  
  215. #else
  216.  
  217. /* MSDOS */
  218.   static unsigned long bufprev;    /* `static int' isn't long enough */
  219.   static char *char_weights;    /* `Weights' of buffer chars.  Normally chars
  220.                                    have weight 1, but `\r\n' is considered
  221.                                    equivalent to a `\n' of weight 2. */
  222.   static last_char_was_CR;        /* True if the last character input was a
  223.                                    carriage return and was stripped. */
  224.  
  225.   /* The following two variables are used to speed up the handling of
  226.      `char_weights' by saving partial sums between calls to print_line(). */
  227.   static char *weights_summing_ptr;
  228.   static unsigned long weights_partial_sum;
  229.  
  230. #endif
  231.  
  232. static bufread;            /* Number of bytes to get with each read(). */
  233.  
  234. static void
  235. initialize_buffer()
  236. {
  237. #ifndef MSDOS
  238.  
  239.   bufread = 8192;
  240.   bufalloc = bufread + bufread / 2;
  241.  
  242.   buffer = malloc(bufalloc);
  243.   if (! buffer)
  244.     {
  245.       fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  246.           sys_errlist[errno]);
  247.       exit(ERROR);
  248.     }
  249.  
  250. #else
  251.  
  252.   /* MSDOS */
  253.  
  254.   bufread = 8192;
  255.   bufalloc = 16383;        /* Twice this is 32766, which is about as
  256.                    big a buffer as we can handle; we really
  257.                    don't want to go increasing buffer size
  258.                    much on MSDOS systems.  B^(  */
  259.  
  260.   last_char_was_CR = 0;
  261.  
  262.   weights_summing_ptr = 0;    /* NULL means `undefined' */
  263.  
  264.   buffer = malloc(bufalloc);
  265.   char_weights = (byte_count) ? malloc(bufalloc) : (char *) -1;
  266.   if (! buffer || ! char_weights)
  267.     {
  268.       fprintf(stderr, "%s: Memory exhausted\n", prog);
  269.       exit(ERROR);
  270.     }
  271.  
  272. #endif
  273. }
  274.  
  275. /* The current input file. */
  276. static fd;
  277. static char *filename;
  278. static is_eof;
  279.  
  280. /* Fill the buffer retaining the last n bytes at the beginning of the
  281.    newly filled buffer (for backward context).  Returns the number of new
  282.    bytes read from disk. */
  283. static
  284. fill_buffer_retaining(n)
  285.      int n;
  286. {
  287.   char *p, *q;
  288.   int i;
  289. #ifdef MSDOS
  290.   int old_last_char_was_CR;
  291. #endif
  292.  
  293.   /* See if we need to grow the buffer. */
  294.   if (bufalloc - n <= bufread)
  295.     {
  296.       while (bufalloc - n <= bufread)
  297.     {
  298. #ifndef MSDOS
  299.       bufalloc *= 2;
  300.       bufread *= 2;
  301. #else
  302.       unsigned new_bufalloc = (unsigned) bufalloc * 2;
  303.  
  304.       /* This is demented, but I'm having trouble figuring out
  305.          another way to avoid the bizarre behaviour you get when
  306.          a line exceeds length 32767 after `\r\n' conversion.
  307.          (It would seem easy, but the code turns bizarre on me.)
  308.          This method limits buffer allocation to about half what
  309.          is possible without resorting to huge model data. */
  310.       if (new_bufalloc > 32767)
  311.         {
  312.           fprintf(stderr, "\
  313. %s: input buffering limit exceeded (very long line)\n", prog);
  314.           exit(ERROR);
  315.         }
  316.  
  317.       bufalloc = new_bufalloc;
  318.  
  319. #if 0    /* Don't increase `bufread', because little is gained and more
  320.        lines get rejected. */
  321.       bufread *= 2;
  322. #endif
  323.  
  324. #endif
  325.     }
  326.  
  327. #ifndef MSDOS
  328.       buffer = realloc(buffer, bufalloc);
  329.       if (! buffer)
  330.     {
  331.       fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  332.           sys_errlist[errno]);
  333.       exit(ERROR);
  334.     }
  335. #else
  336.       /* MSDOS */
  337.       buffer = realloc(buffer, bufalloc);
  338.       char_weights = (byte_count) ? realloc(char_weights, bufalloc)
  339.                     : (char *) -1;
  340.       if (! buffer || ! char_weights)
  341.     {
  342.       fprintf(stderr, "%s: Memory exhausted\n", prog);
  343.       exit(ERROR);
  344.     }
  345. #endif
  346.     }
  347.  
  348. #ifndef MSDOS
  349.   bufprev += bufbytes - n;
  350. #else
  351.   if (byte_count)
  352.     {
  353.       /* Increase bufprev by the weights of the unretained characters. */
  354.  
  355.       char *limit = char_weights + (bufbytes - n);
  356.  
  357.       if (weights_summing_ptr)
  358.     {
  359.       p = weights_summing_ptr;
  360.       bufprev += weights_partial_sum;
  361.     }
  362.       else
  363.     p = char_weights;
  364.       while (p != limit)
  365.     bufprev += *(p++);
  366.  
  367.       /* Discard the old partial sum (if it exists), now that it has been
  368.          absorbed into `bufprev'. */
  369.       weights_summing_ptr = 0;
  370.     }
  371. #endif
  372.  
  373.   /* Shift stuff down. */
  374.   for (i = n, p = buffer, q = p + bufbytes - n; i--; )
  375.     *p++ = *q++;
  376. #ifdef MSDOS
  377.   if (byte_count)
  378.     for (i = n, p = char_weights, q = p + bufbytes - n; i--; )
  379.       *p++ = *q++;
  380. #endif
  381.   bufbytes = n;
  382.  
  383.   if (is_eof)
  384.     return 0;
  385.  
  386.   /* Read in new stuff. */
  387.   i = read(fd, buffer + bufbytes, bufread);
  388. #ifdef MSDOS
  389.   if (i == -1)        /* Other negative values are really wrapped-around
  390.                positive values. */
  391. #else
  392.   if (i < 0)
  393. #endif
  394.     {
  395.       fprintf(stderr, "%s: read on %s failed (%s)\n", prog,
  396.           filename ? filename : "<stdin>", sys_errlist[errno]);
  397.       error = 1;
  398.     }
  399.  
  400. #ifdef MSDOS
  401.   /* Save the old value of `last_char_was_CR', because it is needed below. */
  402.   old_last_char_was_CR = last_char_was_CR;
  403.  
  404.   /* If the last character input is a `\r', strip it but note that
  405.      it has been stripped.  This means that `\r' at the end of a file
  406.      _may or may not_ be stripped, but for grepping I don't think this
  407.      makes much difference.  What do you think? */
  408.   if (i > 0 && buffer[bufbytes + i - 1] == '\r')
  409.     --i, last_char_was_CR = 1;
  410.  
  411.   /* Massage the newly input stuff:  convert most characters to pairs
  412.      consisting of themselves and a weight of 1, but convert each `\r\n'
  413.      sequence to a `\n' character and a weight of 2. */
  414.   {
  415.     char *t;
  416.     char *limit = buffer + (bufbytes + i);
  417.  
  418.     p = q = buffer + bufbytes;
  419.     if (byte_count)
  420.       t = char_weights + bufbytes;
  421.  
  422.     /* If the old value of `last_char_was_CR' is true and the first
  423.        character read is `\n', then give that character a weight of 2,
  424.        because it belongs to a `\r\n' sequence. */
  425.     if (old_last_char_was_CR && q != limit && *q == '\n')
  426.       {
  427.     ++p;  ++q;        /* Leave the newline where it is */
  428.     if (byte_count)
  429.       *(t++) = 2;
  430.       }
  431.  
  432.     while (q != limit)
  433.       {
  434.     if (*q != '\r' || q + 1 == limit || *(q + 1) != '\n')
  435.       {
  436.         *(p++) = *(q++);    /* Either copy the character onto itself
  437.                    or shift it */
  438.         if (byte_count)
  439.           *(t++) = 1;    /* It's weight is 1 */
  440.       }
  441.     else
  442.       {
  443.         ++q;  ++q;        /* Skip past the `\r\n' sequence */
  444.         *(p++) = '\n';    /* Store a newline . . .    */
  445.         if (byte_count)
  446.           *(t++) = 2;    /*   . . . and give it weight 2 */
  447.         --i;        /* Pretend we didn't read the `\r' */
  448.       }
  449.       }
  450.   }
  451. #endif /* MSDOS */
  452.  
  453.   /* Kludge to pretend every nonempty file ends with a newline. */
  454.   if (i == 0 && bufbytes > 0 && buffer[bufbytes - 1] != '\n')
  455.     {
  456.       is_eof = i = 1;
  457.       buffer[bufbytes] = '\n';
  458.     }
  459.  
  460.   bufbytes += i;
  461.   return i;
  462. }
  463.  
  464. /* Various flags set according to the argument switches. */
  465. static trailing_context;    /* Lines of context to show after matches. */
  466. static leading_context;        /* Lines of context to show before matches. */
  467. static no_filenames;        /* Do not display filenames. */
  468. static all_filenames;        /* display filenames, even on single file. */
  469. static line_numbers;        /* Precede output lines with line numbers. */
  470. static silent;            /* Produce no output at all.  This switch
  471.                    is bogus, ever hear of /dev/null? */
  472. static nonmatching_lines;    /* Print lines that don't match the regexp. */
  473.  
  474. static bmgexec;            /* Invoke Boyer-Moore-Gosper routines */
  475.  
  476. /* The compiled regular expression lives here. */
  477. static struct regexp reg;
  478.  
  479. /* The compiled regular expression for the backtracking matcher lives here. */
  480. static struct re_pattern_buffer regex;
  481.  
  482. /* Pointer in the buffer after the last character printed. */
  483. static char *printed_limit;
  484.  
  485. /* True when printed_limit has been artifically advanced without printing
  486.    anything. */
  487. static int printed_limit_fake;
  488.  
  489. /* Print a line at the given line number, returning the number of
  490.    characters actually printed.  Matching is true if the line is to
  491.    be considered a "matching line".  This is only meaningful if
  492.    surrounding context is turned on. */
  493. static
  494. print_line(p, number, matching)
  495.      char *p;
  496. #ifndef MSDOS
  497.      int number;
  498. #else
  499.      long number;
  500. #endif
  501.      int matching;
  502. {
  503.   int count = 0;
  504.  
  505.   if (silent)
  506.     {
  507.       do
  508.     ++count;
  509.       while (*p++ != '\n');
  510.       printed_limit_fake = 0;
  511.       printed_limit = p;
  512.       return count;
  513.     }
  514.  
  515.   if (filename && !no_filenames)
  516.     printf("%s%c", filename, matching ? ':' : '-');
  517. #ifndef MSDOS
  518.   if (byte_count)
  519.     printf("%d%c", p - buffer + bufprev, matching ? ':' : '-');
  520. #else
  521.   if (byte_count)
  522.     {
  523.       register char *q;
  524.       register char *limit = char_weights + (int) (p - buffer);
  525.       register unsigned long sum_of_weights;
  526.  
  527.       if (weights_summing_ptr)
  528.     {
  529.       q = weights_summing_ptr;
  530.       sum_of_weights = weights_partial_sum;
  531.     }
  532.       else
  533.     {
  534.       q = char_weights;
  535.       sum_of_weights = 0L;
  536.     }
  537.  
  538.       while (q != limit)
  539.     sum_of_weights += *(q++);
  540.  
  541.       /* Save the partial sum so we don't have to start from the
  542.      beginning of the buffer each time. */
  543.       weights_summing_ptr = q;        /* == limit */
  544.       weights_partial_sum = sum_of_weights;
  545.  
  546.       printf("%lu%c", sum_of_weights + bufprev, matching ? ':' : '-');
  547.     }
  548. #endif
  549. #ifndef MSDOS
  550.   if (line_numbers)
  551.     printf("%d%c", number, matching ? ':' : '-');
  552. #else
  553.   if (line_numbers)
  554.     printf("%ld%c", number, matching ? ':' : '-');
  555. #endif
  556.   do
  557.     {
  558.       ++count;
  559.       putchar(*p);
  560.     }
  561.   while (*p++ != '\n');
  562.   printed_limit_fake = 0;
  563.   printed_limit = p;
  564.   return count;
  565. }
  566.  
  567. /* Print matching or nonmatching lines from the current file.  Returns a
  568.    count of matching or nonmatching lines. */
  569. static
  570. #ifdef MSDOS
  571. long
  572. #endif
  573. grep()
  574. {
  575.   int retain = 0;        /* Number of bytes to retain on next call
  576.                    to fill_buffer_retaining(). */
  577.   char *search_limit;        /* Pointer to the character after the last
  578.                    newline in the buffer. */
  579.   char saved_char;        /* Character after the last newline. */
  580.   char *resume;            /* Pointer to where to resume search. */
  581.   int resume_index = 0;        /* Count of characters to ignore after
  582.                    refilling the buffer. */
  583. #ifndef MSDOS
  584.   int line_count = 1;        /* Line number. */
  585. #else
  586.   long line_count = 1L;
  587. #endif
  588.   int try_backref;        /* Set to true if we need to verify the
  589.                    match with a backtracking matcher. */
  590. #ifndef MSDOS
  591.   int initial_line_count;    /* Line count at beginning of last search. */
  592. #else
  593.   long initial_line_count;
  594. #endif
  595.   char *match;            /* Pointer to the first character after the
  596.                    string matching the regexp. */
  597. #ifndef MSDOS
  598.   int match_count = 0;        /* Count of matching lines. */
  599. #else
  600.   long match_count = 0L;
  601. #endif
  602.   char *matching_line;        /* Pointer to first character of the matching
  603.                    line, or of the first line of context to
  604.                    print if context is turned on. */
  605.   char *real_matching_line;    /* Pointer to the first character of the
  606.                    real matching line. */
  607.   char *next_line;        /* Pointer to first character of the line
  608.                    following the matching line. */
  609.   int pending_lines = 0;    /* Lines of context left over from last match
  610.                    that we have to print. */
  611.   static first_match = 1;    /* True when nothing has been printed. */
  612.   int i;
  613.   char *tmp;
  614.  
  615.   printed_limit_fake = 0;
  616.   
  617.   while (fill_buffer_retaining(retain) > 0)
  618.     {
  619.       /* Find the last newline in the buffer. */
  620.       search_limit = buffer + bufbytes;
  621.       while (search_limit > buffer && search_limit[-1] != '\n')
  622.     --search_limit;
  623.       if (search_limit == buffer)
  624.     {
  625.       retain = bufbytes;
  626.       continue;
  627.     }
  628.  
  629.       /* Save the character after the last newline so regexecute can write
  630.      its own sentinel newline. */
  631.       saved_char = *search_limit;
  632.  
  633.       /* Search the buffer for a match. */
  634.       printed_limit = buffer;
  635.       resume = buffer + resume_index;
  636.       initial_line_count = line_count;
  637.  
  638.       while ((match = execute(®, resume, search_limit, 0, &line_count, &try_backref)) != 0)
  639.     {
  640.       ++match_count;
  641.  
  642.       /* Find the beginning of the matching line. */
  643.       matching_line = match;
  644.       while (matching_line > resume && matching_line[-1] != '\n')
  645.         --matching_line;
  646.       real_matching_line = matching_line;
  647.  
  648.       /* Find the beginning of the next line. */
  649.       next_line = match;
  650.       while (next_line < search_limit && *next_line++ != '\n')
  651.         ;
  652.  
  653.       /* If a potential backreference is indicated, try it out with
  654.          a backtracking matcher to make sure the line is a match. */
  655.       if (try_backref && re_search(®ex, matching_line,
  656.                        (int) (next_line - matching_line - 1),
  657.                        0,
  658.                        (int) (next_line - matching_line - 1),
  659.                        NULL) < 0)
  660.         {
  661.           resume = next_line;
  662.           if (resume == search_limit)
  663.         break;
  664.           else
  665.         continue;
  666.         }
  667.  
  668.       /* Print leftover lines from last time.  If nonmatching_lines is
  669.          turned on, print these as if they were matching lines. */
  670.       while (resume < matching_line && pending_lines)
  671.         {
  672.           resume += print_line(resume, initial_line_count++,
  673.                    nonmatching_lines);
  674.           --pending_lines;
  675.         }
  676.  
  677.       /* Print out the matching or nonmatching lines as necessary. */
  678.       if (! nonmatching_lines)
  679.         {
  680.           /* Back up over leading context if necessary. */
  681.           for (i = leading_context; matching_line > printed_limit
  682.            && i; --i)
  683.         {
  684.           while (matching_line > printed_limit
  685.              && (--matching_line)[-1] != '\n')
  686.             ;
  687.           --line_count;
  688.         }
  689.  
  690.           /* If context is enabled, we may have to print a separator. */
  691.           if ((leading_context || trailing_context) && !silent
  692.           && !first_match && (printed_limit_fake || matching_line
  693.                       > printed_limit))
  694.         printf("----------\n");
  695.           first_match = 0;
  696.  
  697.           /* Print the matching line and its leading context. */
  698.           while (matching_line < real_matching_line)
  699.         matching_line += print_line(matching_line, line_count++, 0);
  700.           matching_line += print_line(matching_line, line_count++, 1);
  701.  
  702.           /* If there's trailing context, leave some lines pending until
  703.          next time. */
  704.           pending_lines = trailing_context;
  705.         }
  706.       else if (matching_line > resume)
  707.         {
  708.           char *real_resume = resume;
  709.  
  710.           /* Back up over leading context if necessary. */
  711.           for (i = leading_context; resume > printed_limit && i; --i)
  712.         {
  713.           while (resume > printed_limit && (--resume)[-1] != '\n')
  714.             ;
  715.           --initial_line_count;
  716.         }
  717.  
  718.           /* If context is enabled, we may have to print a separator. */
  719.           if ((leading_context || trailing_context) && !silent
  720.           && !first_match && (printed_limit_fake || resume
  721.                       > printed_limit))
  722.         printf("----------\n");
  723.           first_match = 0;
  724.  
  725.           /* Print out the presumably matching leading context. */
  726.           while (resume < real_resume)
  727.         resume += print_line(resume, initial_line_count++, 0);
  728.  
  729.           /* Print out the nonmatching lines prior to the matching line. */
  730.           while (resume < matching_line)
  731.         resume += print_line(resume, initial_line_count++, 1);
  732.  
  733.           /* Deal with trailing context. */
  734.           if (trailing_context)
  735.         {
  736.           print_line(matching_line, line_count, 0);
  737.           pending_lines = trailing_context - 1;
  738.         }
  739.  
  740.           /* Count the current line. */
  741.           ++line_count;
  742.         }
  743.       else
  744.         {
  745.           /* The line immediately after a matching line has to be printed
  746.          because it was pending. */
  747.           if (pending_lines > 0)
  748.         {
  749.           --pending_lines;
  750.           print_line(matching_line, line_count, 0);
  751.         }
  752.           ++line_count;
  753.         }
  754.  
  755.       /* Resume searching at the beginning of the next line. */
  756.       initial_line_count = line_count;
  757.       resume = next_line;
  758.  
  759.       if (resume == search_limit)
  760.         break;
  761.     }
  762.  
  763.       /* Restore the saved character. */
  764.       *search_limit = saved_char;
  765.  
  766.       if (! nonmatching_lines)
  767.     {
  768.       while (resume < search_limit && pending_lines)
  769.         {
  770.           resume += print_line(resume, initial_line_count++, 0);
  771.           --pending_lines;
  772.         }
  773.     }
  774.       else if (search_limit > resume)
  775.     {
  776.       char *initial_resume = resume;
  777.  
  778.       /* Back up over leading context if necessary. */
  779.       for (i = leading_context; resume > printed_limit && i; --i)
  780.         {
  781.           while (resume > printed_limit && (--resume)[-1] != '\n')
  782.         ;
  783.           --initial_line_count;
  784.         }
  785.  
  786.       /* If context is enabled, we may have to print a separator. */
  787.       if ((leading_context || trailing_context) && !silent
  788.           && !first_match && (printed_limit_fake || resume
  789.                   > printed_limit))
  790.         printf("----------\n");
  791.       first_match = 0;
  792.  
  793.       /* Print out all the nonmatching lines up to the search limit. */
  794.       while (resume < initial_resume)
  795.         resume += print_line(resume, initial_line_count++, 0);
  796.       while (resume < search_limit)
  797.         resume += print_line(resume, initial_line_count++, 1);
  798.  
  799.       pending_lines = trailing_context;
  800.       resume_index = 0;
  801.       retain = bufbytes - (int) (search_limit - buffer);
  802.       continue;
  803.     }
  804.       
  805.       /* Save the trailing end of the buffer for possible use as leading
  806.      context in the future. */
  807.       i = leading_context;
  808.       tmp = search_limit;
  809.       while (tmp > printed_limit && i--)
  810.     while (tmp > printed_limit && (--tmp)[-1] != '\n')
  811.       ;
  812.       resume_index = (int) (search_limit - tmp);
  813.       retain = bufbytes - (int) (tmp - buffer);
  814.       if (tmp > printed_limit)
  815.     printed_limit_fake = 1;
  816.     }
  817.  
  818.   return nonmatching_lines ? (line_count - 1) - match_count : match_count;
  819. }
  820.  
  821. void
  822. usage_and_die()
  823. {
  824. #ifdef BIG_HELP
  825.   fprintf(stderr,
  826. "%s   usage: %s <flags> <pattern> <files> [<files>...]\n"
  827. "  -A<n> print <num> lines before match   -B<num> print <num> lines after match\n"
  828. "  -C print 2 lines around match          -<num>  print <num> lines around match\n"
  829. "  -V display version                     -b display byte offset of match\n"
  830. "  -c only print count of matches         -d '<pat>' strip surrounding quotes\n"
  831. "  -e <pat> search for <expr>             -f <file> use pattern from <file>\n"
  832. #ifdef NEG_OPTS
  833. "  -H/h do/don't display file names       -i/I ignore/keep case during search\n"
  834. "  -l only list files containing matches  -n/N display/don't line no. of matches\n"
  835. #else
  836. "  -h don't display file names            -i ignore case during search\n"
  837. "  -l only list files containing matches  -n display line no. of matches\n"
  838. #endif
  839. "  -s don't display output                -v display lines which don't match\n"
  840. "  -w match only complete words           -x match only complete lines\n"
  841. "Regular expression chars:\n"
  842. "  \\<char> ignore special meaning of char \\\\ literal \\\n"
  843. "  <char>  matches char (if -i, any case) .  matches any char except newline\n"
  844. #ifndef EGREP
  845. "  \\? preceding item is optional          *  match zero or more of previous item\n"
  846. "  \\+ match one or more of previous item  \\| match previous or next item\n"
  847. "  $  match end of line                   \\< match beginning of word\n"
  848. "  ^  match beginning of line             \\> match end of word\n"
  849. "  [chars] match any char in <chars> <char>-<char> sets a range\n"
  850. "  [^chars] match any char not in <chars>\n"
  851. "  \\( start of subexpression              \\) end of subexpression\n"
  852. #else
  853. "  ?  preceding item is optional          *  match zero or more of previous item\n"
  854. "  +  match one or more of previous item  |  match previous or next item\n"
  855. "  $  match end of line                   \\< match beginning of word\n"
  856. "  ^  match beginning of line             \\> match end of word\n"
  857. "  [chars] match any char in <chars> <char>-<char> sets a range\n"
  858. "  [^chars] match any char not in <chars>.\n"
  859. "  (  start of subexpression              )  end of subexpression\n"
  860. #endif
  861. "  \\<digit> match text matched by subexpression inside nth parentheses\n"
  862. "  \\b match start or end of word          \\B match except at word start or end\n"
  863. "  \\w match char a-z A-Z 0-9 '_'          \\W match any except a-z A-Z 0-9 '_'\n",
  864.           version, prog);
  865. #else
  866.   fprintf(stderr,
  867. "usage: %s [-CVbchHilnsvwx] [-<num>] [-AB <num>] [-f file] [-e] expr [files]\n",
  868.           prog);
  869. #endif
  870.   exit(ERROR);
  871. }
  872.  
  873. #ifdef MSDOS
  874. #ifdef GNU_GLOBBING
  875. /* File attributes used by msd_dir2 routines */
  876. unsigned short dos_file_attributes;
  877. #endif
  878. #endif
  879.  
  880. void
  881. main(argc, argv
  882. #ifdef    MKSARGS
  883.                 , envp
  884. #endif
  885.                     )
  886.      int argc;
  887.      char **argv;
  888. #ifdef    MKSARGS
  889.      char **envp;
  890. #endif     
  891. {
  892.   int c;
  893.   int ignore_case = 0;        /* Compile the regexp to ignore case. */
  894.   char *the_regexp = 0;        /* The regular expression. */
  895.   int regexp_len;        /* Length of the regular expression. */
  896.   char *regexp_file = 0;    /* File containing parallel regexps. */
  897.   int count_lines = 0;        /* Display only a count of matching lines. */
  898.   int list_files = 0;        /* Display only the names of matching files. */
  899.   int whole_word = 0;        /* Insist that the regexp match a word only. */
  900.   int whole_line = 0;        /* Insist on matching only whole lines. */
  901. #ifndef MSDOS
  902.   int line_count = 0;        /* Count of matching lines for a file. */
  903. #else
  904.   long line_count = 0L;
  905. #endif
  906.   int matches_found = 0;    /* True if matches were found. */
  907.   char *regex_errmesg;        /* Error message from regex routines. */
  908.   char translate[_NOTCHAR];    /* Translate table for case conversion
  909.                    (needed by the backtracking matcher). */
  910.   char    **argv_copy;        /*    we'll copy argv[] so we can insert the    */
  911.                               /*    default options (if any) or fixup MKS's    */
  912.                               /*    argv[]                                    */
  913.   int    argc_copy;
  914.                                 
  915. #if defined(GREP_OPTS) || defined(MKSARGS)
  916.   int    i, j;
  917. #endif
  918.  
  919. #ifdef    GREP_OPTS
  920.     char    *g_opts = getenv ("GREP_OPTS");
  921. #endif
  922.  
  923. #ifdef MKSARGS
  924.     char    *mks = getenv ("MKS");
  925.     char    **ep = envp;
  926. #endif
  927.  
  928. #ifdef MKSARGS
  929.  
  930.     /*    if MKS is defined in the environment, we will set up a
  931.         new argv_copy with the pointers to the environment strings
  932.         and (possibly) the GREP_OPTS variable
  933.     */
  934.  
  935.     if (mks != NULL)
  936.         {
  937.         for (argc_copy = 0; ; ++ep, ++argc_copy)
  938.             {
  939.             if ((*ep == NULL) || (**ep != '~'))
  940.                 break;
  941.             }
  942.  
  943. #       ifdef GREP_OPTS
  944.  
  945.         if (g_opts != NULL)
  946.             ++argc_copy;        
  947.  
  948. #        endif
  949.  
  950.           if ((argv_copy = calloc (argc_copy, sizeof (char *))) == NULL)
  951.             {
  952.             fprintf (stderr, "%s: Memory exhausted\n", prog);
  953.             exit(ERROR);
  954.             }
  955.  
  956.         for (i = 0, ep = envp; i < argc_copy; ++i)    
  957.             {
  958. #            ifdef GREP_OPTS
  959.  
  960.             /*    copy environment string to argv_copy[1]    */
  961.             
  962.             if ((i == 1) && (g_opts != NULL))
  963.                 {
  964.                 argv_copy[1] = g_opts;
  965.                 continue;
  966.                 }
  967.  
  968. #            endif
  969.  
  970.             /*    copy environment string, omitting the leading '~'    */
  971.             
  972.             argv_copy[i] = *ep + 1;
  973.             ++ep;
  974.  
  975.             }    /*    for (i = 0, ep = envp; i < argc_copy; ++i)    */
  976.             
  977.         }    /*    if (mks != NULL)    */
  978.     else
  979. #endif
  980.         {
  981.         /*    this code is mainline if MKSARGS is not defined, otherwise
  982.             it's the else clause of the test on the MKS environment
  983.             variable. We'll copy argc and argv[] to argc_copy and
  984.             argv_copy[], possibly inserting the environment string
  985.             GREP_OPTS as argv_copy[1].
  986.         */
  987.  
  988.         argc_copy = argc;
  989.  
  990. #        ifdef    GREP_OPTS
  991.         if (g_opts != NULL)
  992.             ++argc_copy;
  993. #        endif            
  994.     
  995.           if ((argv_copy = calloc (argc_copy, sizeof (char *))) == NULL)
  996.             {
  997.             fprintf (stderr, "%s: Memory exhausted\n", prog);
  998.             exit(ERROR);
  999.             }
  1000.  
  1001.         for (i = j = 0; i < argc_copy; ++i)
  1002.             {
  1003. #            ifdef GREP_OPTS
  1004.  
  1005.             /*    copy environment string to argv_copy[1]    */
  1006.             
  1007.             if ((i == 1) && (g_opts != NULL))
  1008.                 {
  1009.                 argv_copy[i] = g_opts;
  1010.                 continue;
  1011.                 }
  1012.  
  1013. #            endif
  1014.  
  1015.             argv_copy[i] = argv[j++];
  1016.             }
  1017.         }
  1018.         
  1019. #ifdef MSDOS
  1020.   /* Leave the output in text mode, but set stdin to binary mode in
  1021.      case the input is read from there. */
  1022.   setmode(fileno(stdin), O_BINARY);
  1023.  
  1024.   EXTRACT_PROGRAM_NAME(argv_copy[0]);
  1025.   prog = argv[0];
  1026. #else
  1027.   if (prog = strrchr(argv_copy[0], '/'))
  1028.     ++prog;
  1029.   else
  1030.     prog = argv_copy[0];
  1031. #endif
  1032.  
  1033. #if defined(MSDOS) && defined(GNU_GLOBBING)
  1034. #  if defined(GLOB_CONTROL) || defined(MKSARGS)
  1035.  
  1036.     /*    allow environment variable NO_GLOB to suppress globbing    */
  1037.     /*    (useful if you sometimes run DOS with a shell which        */
  1038.     /*    globs and sometimes with one that doesn't. You can stop    */
  1039.     /*    globbing, which saves having to go through contortions    */
  1040.     /*    to get a regex through two levels of globbing            */
  1041.     /*    defining MKSARGS and setting the environment variable    */
  1042.     /*    MKS will also suppress globbing                            */
  1043.     
  1044.   if (
  1045. #    ifdef GLOB_CONTROL
  1046.         (getenv ("NO_GLOB") == NULL)
  1047. #       ifdef MKSARGS
  1048.                                       && (mks == NULL)
  1049. #      endif    /* ifdef MKSARGS    */
  1050. #    else
  1051.         (mks == NULL)
  1052. #    endif        /*    ifdef GLOB_CONTROL    */
  1053.                                                         )
  1054. #  endif          /*    if defined(GLOB_CONTROL) || defined(MKSARGS)    */
  1055.         {  
  1056.         dos_file_attributes = 0x11;        /* Regular, read-only, or directory */
  1057.               {
  1058.             char **glob_filename ();
  1059.             int globargv ();
  1060.  
  1061.             if (globargv (&argc_copy, &argv_copy, glob_filename))
  1062.                 {
  1063.                 fprintf(stderr, "%s: Memory exhausted\n", prog);
  1064.                 exit(ERROR);
  1065.                   }
  1066.               }
  1067.         }
  1068.  
  1069. #endif    /*    if defined(MSDOS) && defined(GNU_GLOBBING)    */
  1070.  
  1071.     opterr = 0;
  1072.  
  1073.     while ((c = getopt (argc_copy, argv_copy,
  1074. #ifdef MSDOS
  1075.      /* Include the `-d <expr>' (strip bracketing quotes) option */
  1076. #  ifdef NEG_OPTS     
  1077.                     "0123456789A:B:CVbcd:e:f:hHiIlnNsvwx"
  1078. #  else
  1079.                     "0123456789A:B:CVbcd:e:f:hilnsvwx"
  1080. #  endif
  1081. #else
  1082. #  ifdef NEG_OPTS     
  1083.                     "0123456789A:B:CVbce:f:hHiIlnNsvwx"
  1084. #  else
  1085.                     "0123456789A:B:CVbce:f:hilnsvwx"
  1086. #  endif
  1087. #endif
  1088.                                                         )) != EOF)
  1089.  
  1090.     {                                                        
  1091.     switch (c)
  1092.         {
  1093.           case '?':
  1094.             usage_and_die();
  1095.             break;
  1096.  
  1097.           case '0': case '1': case '2': case '3': case '4':
  1098.           case '5': case '6': case '7': case '8': case '9':
  1099.             trailing_context = 10 * trailing_context + c - '0';
  1100.             leading_context = 10 * leading_context + c - '0';
  1101.             break;
  1102.  
  1103.           case 'A':
  1104.             if (! sscanf(optarg, "%d", &trailing_context) ||
  1105.                                                 trailing_context < 0)
  1106.                   usage_and_die();
  1107.             break;
  1108.  
  1109.           case 'B':
  1110.             if (! sscanf(optarg, "%d", &leading_context) ||
  1111.                                                 leading_context < 0)
  1112.                   usage_and_die();
  1113.             break;
  1114.  
  1115.           case 'C':
  1116.             trailing_context = leading_context = 2;
  1117.             break;
  1118.  
  1119.           case 'V':
  1120.             fprintf(stderr, "%s\n", version);
  1121.             break;
  1122.  
  1123.           case 'b':
  1124.             byte_count = 1;
  1125.             break;
  1126.  
  1127.           case 'c':
  1128.             count_lines = 1;
  1129.             silent = 1;
  1130.             break;
  1131.  
  1132.           case 'e':
  1133.             /* It doesn't make sense to mix -f and -e. */
  1134.             if (regexp_file)
  1135.                   usage_and_die();
  1136.  
  1137.             the_regexp = optarg;
  1138.             break;
  1139.  
  1140. #ifdef MSDOS
  1141.           case 'd':
  1142.             /* It doesn't make sense to mix -f, -e, or -d */
  1143.             if (regexp_file)
  1144.                   usage_and_die();
  1145.  
  1146.              /* Strip off bracketing quotes */
  1147.              if (optarg[0] == '\'' || optarg[0] == '"')
  1148.                    {
  1149.                  char opening_quote = optarg[0];
  1150.                  int len = strlen (optarg);
  1151.  
  1152.                  if (len > 1 && optarg[len - 1] == opening_quote)
  1153.                        (optarg++)[len - 1] = '\0';
  1154.                    }
  1155.  
  1156.             the_regexp = optarg;
  1157.             break;
  1158. #endif
  1159.  
  1160.           case 'f':
  1161.             /* It doesn't make sense to mix -f and -e. */
  1162.             if (the_regexp)
  1163.                   usage_and_die();
  1164.  
  1165.             regexp_file = optarg;
  1166.             break;
  1167.  
  1168.           case 'h':
  1169.             no_filenames = 1;
  1170.             break;
  1171.  
  1172. #ifdef NEG_OPTS
  1173.           case 'H':
  1174.             no_filenames = 0;
  1175.             all_filenames = 1;
  1176.             break;
  1177. #endif
  1178.  
  1179.           case 'i':
  1180.             ignore_case = 1;
  1181.             for (c = 0; c < _NOTCHAR; ++c)
  1182.                   if (isupper(c))
  1183.                     translate[c] = tolower(c);
  1184.                   else
  1185.                     translate[c] = c;
  1186.  
  1187.             regex.translate = translate;
  1188.             break;
  1189.  
  1190. #ifdef NEG_OPTS
  1191.           case 'I':
  1192.             ignore_case = 0;
  1193.             for (c = 0; c < _NOTCHAR; ++c)
  1194.                 translate[c] = c;
  1195.  
  1196.             regex.translate = translate;
  1197.             break;
  1198. #endif
  1199.  
  1200.           case 'l':
  1201.             list_files = 1;
  1202.             silent = 1;
  1203.             break;
  1204.  
  1205.           case 'n':
  1206.             line_numbers = 1;
  1207.             break;
  1208.  
  1209. #ifdef    NEG_OPTS
  1210.           case 'N':
  1211.             line_numbers = 0;
  1212.             break;
  1213. #endif
  1214.  
  1215.           case 's':
  1216.             silent = 1;
  1217.             break;
  1218.  
  1219.           case 'v':
  1220.             nonmatching_lines = 1;
  1221.             break;
  1222.  
  1223.           case 'w':
  1224.             whole_word = 1;
  1225.             break;
  1226.  
  1227.           case 'x':
  1228.             whole_line = 1;
  1229.             break;
  1230.  
  1231.           default:
  1232.             /* This can't happen. */
  1233.             fprintf (stderr, "%s: getopt(3) let one by!\n", prog);
  1234.             usage_and_die();
  1235.             break;
  1236.         }
  1237.     }
  1238.  
  1239.   /* Set the syntax depending on whether we are EGREP or not. */
  1240. #ifdef EGREP
  1241.   regsyntax(RE_SYNTAX_EGREP, ignore_case);
  1242.   re_set_syntax(RE_SYNTAX_EGREP);
  1243. #else
  1244.   regsyntax(RE_SYNTAX_GREP, ignore_case);
  1245.   re_set_syntax(RE_SYNTAX_GREP);
  1246. #endif
  1247.  
  1248.   /* Compile the regexp according to all the options. */
  1249.   if (regexp_file)
  1250.     {
  1251. #ifdef MSDOS
  1252.       /* This file must be handled in text mode */
  1253.       FILE *fp = fopen(regexp_file, "rt");
  1254. #else
  1255.       FILE *fp = fopen(regexp_file, "r");
  1256. #endif
  1257.       int len = 256;
  1258.       int i = 0;
  1259.  
  1260.       if (! fp)
  1261.     {
  1262.       fprintf(stderr, "%s: %s: %s\n", prog, regexp_file,
  1263.           sys_errlist[errno]);
  1264.       exit(ERROR);
  1265.     }
  1266.  
  1267.       the_regexp = malloc(len);
  1268.       if (! the_regexp)
  1269.     {
  1270. #ifdef MSDOS
  1271.       fprintf(stderr, "%s: Memory exhausted\n", prog);
  1272. #else
  1273.       fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  1274.           sys_errlist[errno]);
  1275. #endif
  1276.       exit(ERROR);
  1277.     }
  1278.  
  1279.       while ((c = getc(fp)) != EOF)
  1280.     {
  1281.       the_regexp[i++] = c;
  1282.       if (i == len)
  1283.         {
  1284.           the_regexp = realloc(the_regexp, len *= 2);
  1285.           if (! the_regexp)
  1286.             {
  1287. #ifdef MSDOS
  1288.               fprintf(stderr, "%s: Memory exhausted\n", prog);
  1289. #else
  1290.               fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  1291.                   sys_errlist[errno]);
  1292. #endif
  1293.               exit(ERROR);
  1294.             }
  1295.         }
  1296.     }
  1297.       fclose(fp);
  1298.       /* Nuke the concluding newline so we won't match the empty string. */
  1299.       if (i > 0 && the_regexp[i - 1] == '\n')
  1300.     --i;
  1301.       regexp_len = i;
  1302.     }
  1303.   else if (! the_regexp)
  1304.     {
  1305.       if (optind >= argc_copy)
  1306.         usage_and_die();
  1307.  
  1308.       the_regexp = argv_copy[optind++];
  1309.       regexp_len = strlen(the_regexp);
  1310.     }
  1311.   else
  1312.     regexp_len = strlen(the_regexp);
  1313.   
  1314.   if (whole_word || whole_line)
  1315.     {
  1316.       char *n = malloc(regexp_len + 8);
  1317.       int i = 0;
  1318.  
  1319.       if (! n)
  1320.     {
  1321. #ifdef MSDOS
  1322.       fprintf(stderr, "%s: Memory exhausted\n", prog);
  1323. #else
  1324.       fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  1325.           sys_errlist[errno]);
  1326. #endif
  1327.       exit(ERROR);
  1328.     }
  1329.  
  1330.       if (whole_line)
  1331.     n[i++] = '^';
  1332.       else
  1333.     n[i++] = '\\', n[i++] = '<';
  1334. #ifndef EGREP
  1335.       n[i++] = '\\';
  1336. #endif
  1337.       n[i++] = '(';
  1338.       memcpy(n + i, the_regexp, regexp_len);
  1339.       i += regexp_len;
  1340. #ifndef EGREP
  1341.       n[i++] = '\\';
  1342. #endif
  1343.       n[i++] = ')';
  1344.       if (whole_line)
  1345.     n[i++] = '$';
  1346.       else
  1347.     n[i++] = '\\', n[i++] = '>';
  1348.       the_regexp = n;
  1349.       regexp_len = i;
  1350.     }
  1351.  
  1352.   regcompile(the_regexp, regexp_len, ®, 1);
  1353.   
  1354.   if ((regex_errmesg = re_compile_pattern(the_regexp, regexp_len, ®ex)) != 0)
  1355.     regerror(regex_errmesg);
  1356.   
  1357.   /*
  1358.     Find the longest metacharacter-free string which must occur in the
  1359.     regexpr, before short-circuiting regexecute() with Boyer-Moore-Gosper.
  1360.     (Conjecture:  The problem in general is NP-complete.)  If there is no
  1361.     such string (like for many alternations), then default to full automaton
  1362.     search.  regmust() code and heuristics [see dfa.c] courtesy
  1363.     Arthur David Olson.
  1364.     */
  1365.   if (line_numbers == 0 && nonmatching_lines == 0)
  1366.     {
  1367.       if (reg.mustn == 0 || reg.mustn == MUST_MAX ||
  1368.         strchr(reg.must, '\0') != reg.must + reg.mustn)
  1369.     bmgexec = 0;
  1370.       else
  1371.     {
  1372.       reg.must[reg.mustn] = '\0';
  1373.       if (getenv("MUSTDEBUG") != NULL)
  1374.         (void) printf("must have: \"%s\"\n", reg.must);
  1375.       bmg_setup(reg.must, ignore_case);
  1376.       bmgexec = 1;
  1377.     }
  1378.     }
  1379.   
  1380.   if (argc_copy - optind < 2)
  1381.     no_filenames = 1;
  1382.  
  1383.   if (all_filenames)
  1384.     no_filenames = 0;
  1385.  
  1386.   initialize_buffer();
  1387.  
  1388.   if (argc_copy > optind)
  1389.     while (optind < argc_copy)
  1390.       {
  1391.     bufprev = is_eof = 0;
  1392. #ifdef MSDOS
  1393.     /* Convert backslashes to slashes, and make all letters lower case */
  1394.  
  1395.      CONVERT_TO_SLASHES(argv_copy[optind]);
  1396. #endif
  1397.     filename = argv_copy[optind++];
  1398.     fd = open(filename, 0, 0);
  1399.     if (fd < 0)
  1400.       {
  1401.         fprintf(stderr, "%s: %s: %s\n", prog, filename,
  1402.             sys_errlist[errno]);
  1403.         error = 1;
  1404.         continue;
  1405.       }
  1406.     if ((line_count = grep()) != 0)
  1407.       matches_found = 1;
  1408.     close(fd);
  1409.     if (count_lines)
  1410.       if (!no_filenames)
  1411.         printf("%s:%d\n", filename, line_count);
  1412.       else
  1413.         printf("%d\n", line_count);
  1414.     else if (list_files && line_count)
  1415.       printf("%s\n", filename);
  1416.       }
  1417.   else
  1418.     {
  1419.       if ((line_count = grep()) != 0)
  1420.     matches_found = 1;
  1421.       if (count_lines)
  1422.     printf("%d\n", line_count);
  1423.       else if (list_files && line_count)
  1424.     printf("<stdin>\n");
  1425.     }
  1426.  
  1427.   if (error)
  1428.     exit(ERROR);
  1429.   if (matches_found)
  1430.     exit(MATCHES_FOUND);
  1431.   exit(NO_MATCHES_FOUND);
  1432. }
  1433.  
  1434. /* Needed by the regexp routines.  This could be fancier, especially when
  1435.    dealing with parallel regexps in files. */
  1436. void
  1437. regerror(s)
  1438.      const char *s;
  1439. {
  1440.   fprintf(stderr, "%s: %s\n", prog, s);
  1441.   exit(ERROR);
  1442. }
  1443.  
  1444. /*
  1445.    bmg_setup() and bmg_search() adapted from:
  1446.      Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  1447.      original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  1448.      experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  1449.      practical value.  However, to improve for worst case input, integrating
  1450.      the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  1451.      February 1986) deserves consideration.
  1452.  
  1453.      James A. Woods                Copyleft (C) 1986, 1988
  1454.      NASA Ames Research Center
  1455. */
  1456.  
  1457. char *
  1458. execute(r, begin, end, newline, count, try_backref)
  1459.   struct regexp *r;
  1460.   char *begin;
  1461.   char *end;
  1462.   int newline;
  1463. #ifndef MSDOS
  1464.   int *count;
  1465. #else
  1466.   long *count;
  1467. #endif
  1468.   int *try_backref;
  1469. {
  1470.   register char *p, *s;
  1471.   char *match;
  1472.   char *start = begin;
  1473.   char save;            /* regexecute() sentinel */
  1474.   int len;
  1475.   char *bmg_search();
  1476.  
  1477.   if (!bmgexec)            /* full automaton search */
  1478.     return(regexecute(r, begin, end, newline, count, try_backref));
  1479.   else
  1480.     {
  1481.       len = (int) (end - begin); 
  1482.       while ((match = bmg_search((unsigned char *) start, len)) != NULL)
  1483.     {
  1484.       p = match;        /* narrow search range to submatch line */
  1485.       while (p > begin && *p != '\n')
  1486.         p--;
  1487.       s = match;
  1488.       while (s < end && *s != '\n')
  1489.         s++;
  1490.       s++;
  1491.  
  1492.       save = *s;
  1493.       *s = '\0';
  1494.       match = regexecute(r, p, s, newline, count, try_backref);
  1495.       *s = save;
  1496.  
  1497.       if (match != NULL)
  1498.         return((char *) match);
  1499.       else
  1500.         {
  1501.           start = s;
  1502.           len = (int) (end - start);
  1503.         }
  1504.     }
  1505.       return(NULL);
  1506.     }
  1507. }
  1508.  
  1509. #include <ctype.h>
  1510. int        delta0[256];
  1511. unsigned char   cmap[256];        /* (un)folded characters */
  1512. unsigned char    pattern[5000];
  1513. int        patlen;
  1514.  
  1515. char *
  1516. bmg_search(buffer, buflen)
  1517.   unsigned char *buffer;
  1518.   int buflen;
  1519. {
  1520.   register unsigned char *k, *strend, *s, *buflim;
  1521.   register int t;
  1522.   int j;
  1523.  
  1524.   if (patlen > buflen)
  1525.     return NULL;
  1526.  
  1527.   buflim = buffer + buflen;
  1528.   if (buflen > patlen * 4)
  1529.     strend = buflim - patlen * 4;
  1530.   else
  1531.     strend = buffer;
  1532.  
  1533.   s = buffer;
  1534.   k = buffer + patlen - 1;
  1535.  
  1536.   for (;;)
  1537.     {
  1538.       /* The dreaded inner loop, revisited. */
  1539.       while (k < strend && ((t = delta0[*k]) != 0))
  1540.     {
  1541.       k += t;
  1542.       k += delta0[*k];
  1543.       k += delta0[*k];
  1544.     }
  1545.       while (k < buflim && delta0[*k])
  1546.     ++k;
  1547.       if (k == buflim)
  1548.     break;
  1549.     
  1550.       j = patlen - 1;
  1551.       s = k;
  1552.       while (--j >= 0 && cmap[*--s] == pattern[j])
  1553.     ;
  1554.       /* 
  1555.     delta-less shortcut for literati, but 
  1556.     short shrift for genetic engineers.
  1557.       */
  1558.       if (j >= 0)
  1559.     k++;
  1560.       else         /* submatch */
  1561.     return ((char *)k);
  1562.     }
  1563.   return(NULL);
  1564. }
  1565.  
  1566. void
  1567. bmg_setup(pat, folded)            /* compute "boyer-moore" delta table */
  1568.   char *pat;
  1569.   int folded;
  1570. {                    /* ... HAKMEM lives ... */
  1571.   int j;
  1572.  
  1573.   patlen = strlen(pat);
  1574.  
  1575.   if (folded)                 /* fold case while saving pattern */
  1576.     for (j = 0; j < patlen; j++) 
  1577.       pattern[j] = (isupper((int) pat[j]) ?
  1578.     (char) tolower((int) pat[j]) : pat[j]);
  1579.   else
  1580.       memcpy(pattern, pat, patlen);
  1581.  
  1582.   for (j = 0; j < 256; j++)
  1583.     {
  1584.       delta0[j] = patlen;
  1585.       cmap[j] = (char) j;        /* could be done at compile time */
  1586.     }
  1587.   for (j = 0; j < patlen - 1; j++)
  1588.     delta0[pattern[j]] = patlen - j - 1;
  1589.   delta0[pattern[patlen - 1]] = 0;
  1590.  
  1591.   if (folded)
  1592.     {
  1593.       for (j = 0; j < patlen - 1; j++)
  1594.     if (islower((int) pattern[j]))
  1595.       delta0[toupper((int) pattern[j])] = patlen - j - 1;
  1596.     if (islower((int) pattern[patlen - 1]))
  1597.       delta0[toupper((int) pattern[patlen - 1])] = 0;
  1598.       for (j = 'A'; j <= 'Z'; j++)
  1599.     cmap[j] = (char) tolower((int) j);
  1600.     }
  1601. }
  1602.  
  1603. #ifndef USG
  1604.  
  1605. /* (groan) compatibility */
  1606.  
  1607. char *
  1608. strchr(s, c)
  1609.      char *s;
  1610. {
  1611.   return index(s, c);
  1612. }
  1613.  
  1614. char *
  1615. strrchr(s, c)
  1616.      char *s;
  1617. {
  1618.   return rindex(s, c);
  1619. }
  1620.  
  1621. char *
  1622. memcpy(d, s, n)
  1623.      char *d, *s;
  1624. {
  1625.   return bcopy(s, d, n);
  1626. }
  1627.  
  1628. #else
  1629.  
  1630. char *
  1631. index(s, c)
  1632.      char *s;
  1633. {
  1634.   return strchr(s, c);
  1635. }
  1636.  
  1637. char *
  1638. bcopy(s, d, n)
  1639.      char *s, *d;
  1640. {
  1641.   return memcpy(d, s, n);
  1642. }
  1643.  
  1644. char *
  1645. bzero(s, n)
  1646.      char *s;
  1647. {
  1648.   return memset(s, 0, n);
  1649. }
  1650.  
  1651. bcmp(s, t, n)
  1652.      char *s, *t;
  1653. {
  1654.   return memcmp(s, t, n);
  1655. }
  1656.  
  1657. #endif
  1658.