home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / MISC / GNU / GREP15AS.ZIP / GREP.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-22  |  25.1 KB  |  972 lines
  1. /* grep - print lines matching an extended regular expression
  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.    This program is free software; you can redistribute it and/or modify
  8.    it under the terms of the GNU General Public License as published by
  9.    the Free Software Foundation; either version 1, or (at your option)
  10.    any later version.
  11.  
  12.    This program is distributed in the hope that it will be useful,
  13.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.    GNU General Public License for more details.
  16.  
  17.    You should have received a copy of the GNU General Public License
  18.    along with this program; if not, write to the Free Software
  19.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. /* MS-DOS port (c) 1990 by Thorsten Ohl <ohl@gnu.ai.mit.edu>
  22.  
  23.    This port is also distributed under the terms of the
  24.    GNU General Public License as published by the
  25.    Free Software Foundation.
  26.  
  27.    Please note that this file is not identical to the
  28.    original GNU release, you should have received this
  29.    code as patch to the official release.
  30.  
  31.    $Header: e:/gnu/grep/RCS/grep.c 1.5.0.6 90/09/21 11:48:14 tho Exp $  */
  32.  
  33. #include <ctype.h>
  34. #include <stdio.h>
  35. #ifdef USG
  36. #include <memory.h>
  37. #include <string.h>
  38. #else
  39. #include <strings.h>
  40. #endif
  41. #include "dfa.h"
  42. #include "regex.h"
  43.  
  44. #ifdef __STDC__
  45.  
  46. #ifdef MSDOS
  47. #include <stdlib.h>
  48. extern getopt (int, char **, const char *);
  49. extern read (int, void *, int);
  50. extern open (const char *, int,...);
  51. extern void close (int fd);
  52. static void initialize_buffer (void);
  53. static int fill_buffer_retaining (int n);
  54. static int print_line (char *p, int number, int matching);
  55. static int grep (void);
  56. extern void usage_and_die (void);
  57. extern void main (int argc, char **argv);
  58. extern void regerror (char const * s);
  59. extern char *execute (struct regexp * r, char *begin, char *end, int newline,
  60.               int *count, int *try_backref);
  61. extern char *bmg_search (unsigned char *buffer, int buflen);
  62. extern void bmg_setup (char *pat, int folded);
  63. #endif /* MSDOS */
  64.  
  65. #else /* not __STDC__ */
  66.  
  67. extern char *strrchr();
  68.  
  69. extern errno;
  70. extern char *sys_errlist[];
  71.  
  72. #endif /* not __STDC__ */
  73.  
  74. extern char *optarg;
  75. extern optind, opterr;
  76.  
  77. #define MAX(a, b) ((a) > (b) ? (a) : (b))
  78.  
  79. /* Exit status codes. */
  80. #define MATCHES_FOUND 0        /* Exit 0 if no errors and matches found. */
  81. #define NO_MATCHES_FOUND 1    /* Exit 1 if no matches were found. */
  82. #define ERROR 2            /* Exit 2 if some error occurred. */
  83.  
  84. /* Error is set true if something awful happened. */
  85. static int error;
  86.  
  87. /* The program name for error messages. */
  88. static char *prog;
  89.  
  90. /* We do all our own buffering by hand for efficiency. */
  91. static char *buffer;        /* The buffer itself, grown as needed. */
  92. static bufbytes;        /* Number of bytes in the buffer. */
  93. static size_t bufalloc;        /* Number of bytes allocated to the buffer. */
  94. static bufprev;            /* Number of bytes that have been forgotten.
  95.                    This is used to get byte offsets from the
  96.                    beginning of the file. */
  97. static bufread;            /* Number of bytes to get with each read(). */
  98.  
  99. static void
  100. initialize_buffer()
  101. {
  102.   bufread = 8192;
  103.   bufalloc = bufread + bufread / 2;
  104.   buffer = malloc(bufalloc);
  105.   if (! buffer)
  106.     {
  107.       fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  108.           sys_errlist[errno]);
  109.       exit(ERROR);
  110.     }
  111. }
  112.  
  113. /* The current input file. */
  114. static fd;
  115. static char *filename;
  116. static eof;
  117.  
  118. /* Fill the buffer retaining the last n bytes at the beginning of the
  119.    newly filled buffer (for backward context).  Returns the number of new
  120.    bytes read from disk. */
  121. static
  122. fill_buffer_retaining(n)
  123.      int n;
  124. {
  125.   char *p, *q;
  126.   int i;
  127.  
  128.   /* See if we need to grow the buffer. */
  129.   if (bufalloc - n <= bufread)
  130.     {
  131.       while (bufalloc - n <= bufread)
  132.     {
  133.       bufalloc *= 2;
  134.       bufread *= 2;
  135.     }
  136.       buffer = realloc(buffer, bufalloc);
  137.       if (! buffer)
  138.     {
  139.       fprintf(stderr, "%s: Memory exhausted (%s)\n", prog,
  140.           sys_errlist[errno]);
  141.       exit(ERROR);
  142.     }
  143.     }
  144.  
  145.   bufprev += bufbytes - n;
  146.  
  147.   /* Shift stuff down. */
  148.   for (i = n, p = buffer, q = p + bufbytes - n; i--; )
  149.     *p++ = *q++;
  150.   bufbytes = n;
  151.  
  152.   if (eof)
  153.     return 0;
  154.  
  155.   /* Read in new stuff. */
  156.   i = read(fd, buffer + bufbytes, bufread);
  157.   if (i < 0)
  158.     {
  159.       fprintf(stderr, "%s: read on %s failed (%s)\n", prog,
  160.           filename ? filename : "<stdin>", sys_errlist[errno]);
  161.       error = 1;
  162.     }
  163.  
  164.   /* Kludge to pretend every nonempty file ends with a newline. */
  165.   if (i == 0 && bufbytes > 0 && buffer[bufbytes - 1] != '\n')
  166.     {
  167.       eof = i = 1;
  168.       buffer[bufbytes] = '\n';
  169.     }
  170.  
  171.   bufbytes += i;
  172.   return i;
  173. }
  174.  
  175. /* Various flags set according to the argument switches. */
  176. static trailing_context;    /* Lines of context to show after matches. */
  177. static leading_context;        /* Lines of context to show before matches. */
  178. static byte_count;        /* Precede output lines the byte count of the
  179.                    first character on the line. */
  180. static no_filenames;        /* Do not display filenames. */
  181. static line_numbers;        /* Precede output lines with line numbers. */
  182. static silent;            /* Produce no output at all.  This switch
  183.                    is bogus, ever hear of /dev/null? */
  184. static nonmatching_lines;    /* Print lines that don't match the regexp. */
  185.  
  186. static bmgexec;            /* Invoke Boyer-Moore-Gosper routines */
  187.  
  188. /* The compiled regular expression lives here. */
  189. static struct regexp reg;
  190.  
  191. /* The compiled regular expression for the backtracking matcher lives here. */
  192. static struct re_pattern_buffer regex;
  193.  
  194. /* Pointer in the buffer after the last character printed. */
  195. static char *printed_limit;
  196.  
  197. /* True when printed_limit has been artifically advanced without printing
  198.    anything. */
  199. static int printed_limit_fake;
  200.  
  201. /* Print a line at the given line number, returning the number of
  202.    characters actually printed.  Matching is true if the line is to
  203.    be considered a "matching line".  This is only meaningful if
  204.    surrounding context is turned on. */
  205. static
  206. print_line(p, number, matching)
  207.      char *p;
  208.      int number;
  209.      int matching;
  210. {
  211.   int count = 0;
  212.  
  213.   if (silent)
  214.     {
  215.       do
  216.     ++count;
  217.       while (*p++ != '\n');
  218.       printed_limit_fake = 0;
  219.       printed_limit = p;
  220.       return count;
  221.     }
  222.  
  223.   if (filename && !no_filenames)
  224.     printf("%s%c", filename, matching ? ':' : '-');
  225.   if (byte_count)
  226.     printf("%d%c", p - buffer + bufprev, matching ? ':' : '-');
  227.   if (line_numbers)
  228.     printf("%d%c", number, matching ? ':' : '-');
  229.   do
  230.     {
  231.       ++count;
  232.       putchar(*p);
  233.     }
  234.   while (*p++ != '\n');
  235.   printed_limit_fake = 0;
  236.   printed_limit = p;
  237.   return count;
  238. }
  239.  
  240. /* Print matching or nonmatching lines from the current file.  Returns a
  241.    count of matching or nonmatching lines. */
  242. static
  243. grep()
  244. {
  245.   int retain = 0;        /* Number of bytes to retain on next call
  246.                    to fill_buffer_retaining(). */
  247.   char *search_limit;        /* Pointer to the character after the last
  248.                    newline in the buffer. */
  249.   char saved_char;        /* Character after the last newline. */
  250.   char *resume;            /* Pointer to where to resume search. */
  251.   int resume_index = 0;        /* Count of characters to ignore after
  252.                    refilling the buffer. */
  253.   int line_count = 1;        /* Line number. */
  254.   int try_backref;        /* Set to true if we need to verify the
  255.                    match with a backtracking matcher. */
  256.   int initial_line_count;    /* Line count at beginning of last search. */
  257.   char *match;            /* Pointer to the first character after the
  258.                    string matching the regexp. */
  259.   int match_count = 0;        /* Count of matching lines. */
  260.   char *matching_line;        /* Pointer to first character of the matching
  261.                    line, or of the first line of context to
  262.                    print if context is turned on. */
  263.   char *real_matching_line;    /* Pointer to the first character of the
  264.                    real matching line. */
  265.   char *next_line;        /* Pointer to first character of the line
  266.                    following the matching line. */
  267.   int pending_lines = 0;    /* Lines of context left over from last match
  268.                    that we have to print. */
  269.   static first_match = 1;    /* True when nothing has been printed. */
  270.   int i;
  271.   char *tmp;
  272.   char *execute();
  273.  
  274.   printed_limit_fake = 0;
  275.   
  276.   while (fill_buffer_retaining(retain) > 0)
  277.     {
  278.       /* Find the last newline in the buffer. */
  279.       search_limit = buffer + bufbytes;
  280.       while (search_limit > buffer && search_limit[-1] != '\n')
  281.     --search_limit;
  282.       if (search_limit == buffer)
  283.     {
  284.       retain = bufbytes;
  285.       continue;
  286.     }
  287.  
  288.       /* Save the character after the last newline so regexecute can write
  289.      its own sentinel newline. */
  290.       saved_char = *search_limit;
  291.  
  292.       /* Search the buffer for a match. */
  293.       printed_limit = buffer;
  294.       resume = buffer + resume_index;
  295.       initial_line_count = line_count;
  296.  
  297.       while (match = execute(®, resume, search_limit, 0, &line_count, &try_backref))
  298.     {
  299.       ++match_count;
  300.  
  301.       /* Find the beginning of the matching line. */
  302.       matching_line = match;
  303.       while (matching_line > resume && matching_line[-1] != '\n')
  304.         --matching_line;
  305.       real_matching_line = matching_line;
  306.  
  307.       /* Find the beginning of the next line. */
  308.       next_line = match;
  309.       while (next_line < search_limit && *next_line++ != '\n')
  310.         ;
  311.  
  312.       /* If a potential backreference is indicated, try it out with
  313.          a backtracking matcher to make sure the line is a match. */
  314.       if (try_backref && re_search(®ex, matching_line,
  315.                        next_line - matching_line - 1,
  316.                        0,
  317.                        next_line - matching_line - 1,
  318.                        NULL) < 0)
  319.         {
  320.           resume = next_line;
  321.           if (resume == search_limit)
  322.         break;
  323.           else
  324.         continue;
  325.         }
  326.  
  327.       /* Print leftover lines from last time.  If nonmatching_lines is
  328.          turned on, print these as if they were matching lines. */
  329.       while (resume < matching_line && pending_lines)
  330.         {
  331.           resume += print_line(resume, initial_line_count++,
  332.                    nonmatching_lines);
  333.           --pending_lines;
  334.         }
  335.  
  336.       /* Print out the matching or nonmatching lines as necessary. */
  337.       if (! nonmatching_lines)
  338.         {
  339.           /* Back up over leading context if necessary. */
  340.           for (i = leading_context; matching_line > printed_limit
  341.            && i; --i)
  342.         {
  343.           while (matching_line > printed_limit
  344.              && (--matching_line)[-1] != '\n')
  345.             ;
  346.           --line_count;
  347.         }
  348.  
  349.           /* If context is enabled, we may have to print a separator. */
  350.           if ((leading_context || trailing_context) && !silent
  351.           && !first_match && (printed_limit_fake || matching_line
  352.                       > printed_limit))
  353.         printf("----------\n");
  354.           first_match = 0;
  355.  
  356.           /* Print the matching line and its leading context. */
  357.           while (matching_line < real_matching_line)
  358.         matching_line += print_line(matching_line, line_count++, 0);
  359.           matching_line += print_line(matching_line, line_count++, 1);
  360.  
  361.           /* If there's trailing context, leave some lines pending until
  362.          next time. */
  363.           pending_lines = trailing_context;
  364.         }
  365.       else if (matching_line > resume)
  366.         {
  367.           char *real_resume = resume;
  368.  
  369.           /* Back up over leading context if necessary. */
  370.           for (i = leading_context; resume > printed_limit && i; --i)
  371.         {
  372.           while (resume > printed_limit && (--resume)[-1] != '\n')
  373.             ;
  374.           --initial_line_count;
  375.         }
  376.  
  377.           /* If context is enabled, we may have to print a separator. */
  378.           if ((leading_context || trailing_context) && !silent
  379.           && !first_match && (printed_limit_fake || resume
  380.                       > printed_limit))
  381.         printf("----------\n");
  382.           first_match = 0;
  383.  
  384.           /* Print out the presumably matching leading context. */
  385.           while (resume < real_resume)
  386.         resume += print_line(resume, initial_line_count++, 0);
  387.  
  388.           /* Print out the nonmatching lines prior to the matching line. */
  389.           while (resume < matching_line)
  390.         resume += print_line(resume, initial_line_count++, 1);
  391.  
  392.           /* Deal with trailing context. */
  393.           if (trailing_context)
  394.         {
  395.           print_line(matching_line, line_count, 0);
  396.           pending_lines = trailing_context - 1;
  397.         }
  398.  
  399.           /* Count the current line. */
  400.           ++line_count;
  401.         }
  402.       else
  403.         {
  404.           /* The line immediately after a matching line has to be printed
  405.          because it was pending. */
  406.           if (pending_lines > 0)
  407.         {
  408.           --pending_lines;
  409.           print_line(matching_line, line_count, 0);
  410.         }
  411.           ++line_count;
  412.         }
  413.  
  414.       /* Resume searching at the beginning of the next line. */
  415.       initial_line_count = line_count;
  416.       resume = next_line;
  417.  
  418.       if (resume == search_limit)
  419.         break;
  420.     }
  421.  
  422.       /* Restore the saved character. */
  423.       *search_limit = saved_char;
  424.  
  425.       if (! nonmatching_lines)
  426.     {
  427.       while (resume < search_limit && pending_lines)
  428.         {
  429.           resume += print_line(resume, initial_line_count++, 0);
  430.           --pending_lines;
  431.         }
  432.     }
  433.       else if (search_limit > resume)
  434.     {
  435.       char *initial_resume = resume;
  436.  
  437.       /* Back up over leading context if necessary. */
  438.       for (i = leading_context; resume > printed_limit && i; --i)
  439.         {
  440.           while (resume > printed_limit && (--resume)[-1] != '\n')
  441.         ;
  442.           --initial_line_count;
  443.         }
  444.  
  445.       /* If context is enabled, we may have to print a separator. */
  446.       if ((leading_context || trailing_context) && !silent
  447.           && !first_match && (printed_limit_fake || resume
  448.                   > printed_limit))
  449.         printf("----------\n");
  450.       first_match = 0;
  451.  
  452.       /* Print out all the nonmatching lines up to the search limit. */
  453.       while (resume < initial_resume)
  454.         resume += print_line(resume, initial_line_count++, 0);
  455.       while (resume < search_limit)
  456.         resume += print_line(resume, initial_line_count++, 1);
  457.  
  458.       pending_lines = trailing_context;
  459.       resume_index = 0;
  460.       retain = bufbytes - (search_limit - buffer);
  461.       continue;
  462.     }
  463.       
  464.       /* Save the trailing end of the buffer for possible use as leading
  465.      context in the future. */
  466.       i = leading_context;
  467.       tmp = search_limit;
  468.       while (tmp > printed_limit && i--)
  469.     while (tmp > printed_limit && (--tmp)[-1] != '\n')
  470.       ;
  471.       resume_index = search_limit - tmp;
  472.       retain = bufbytes - (tmp - buffer);
  473.       if (tmp > printed_limit)
  474.     printed_limit_fake = 1;
  475.     }
  476.  
  477.   return nonmatching_lines ? (line_count - 1) - match_count : match_count;
  478. }
  479.  
  480. void
  481. usage_and_die()
  482. {
  483.   fprintf(stderr,
  484. "usage: %s [-CVbchilnsvwx] [-<num>] [-AB <num>] [-f file] [-e] expr [files]\n",
  485.           prog);
  486.   exit(ERROR);
  487. }
  488.  
  489. #ifndef MSDOS
  490. static char version[] = "GNU e?grep, version 1.5";
  491. #else /* MSDOS */
  492. static char version[] =
  493.   "GNU e?grep, version 1.5  (compiled " __DATE__ " " __TIME__ " for MS-DOS)";
  494.  
  495. void
  496. #endif /* MSDOS */
  497. main(argc, argv)
  498.      int argc;
  499.      char **argv;
  500. {
  501.   int c;
  502.   int ignore_case = 0;        /* Compile the regexp to ignore case. */
  503.   char *the_regexp = 0;        /* The regular expression. */
  504.   int regexp_len;        /* Length of the regular expression. */
  505.   char *regexp_file = 0;    /* File containing parallel regexps. */
  506.   int count_lines = 0;        /* Display only a count of matching lines. */
  507.   int list_files = 0;        /* Display only the names of matching files. */
  508.   int whole_word = 0;        /* Insist that the regexp match a word only. */
  509.   int whole_line = 0;        /* Insist on matching only whole lines. */
  510.   int line_count = 0;        /* Count of matching lines for a file. */
  511.   int matches_found = 0;    /* True if matches were found. */
  512.   char *regex_errmesg;        /* Error message from regex routines. */
  513.   char translate[_NOTCHAR];    /* Translate table for case conversion
  514.                    (needed by the backtracking matcher). */
  515.  
  516.   if (prog = strrchr(argv[0], '/'))
  517.     ++prog;
  518.   else
  519.     prog = argv[0];
  520.  
  521.   opterr = 0;
  522.   while ((c = getopt(argc, argv, "0123456789A:B:CVbce:f:hilnsvwx")) != EOF)
  523.     switch (c)
  524.       {
  525.       case '?':
  526.     usage_and_die();
  527.     break;
  528.  
  529.       case '0':
  530.       case '1':
  531.       case '2':
  532.       case '3':
  533.       case '4':
  534.       case '5':
  535.       case '6':
  536.       case '7':
  537.       case '8':
  538.       case '9':
  539.     trailing_context = 10 * trailing_context + c - '0';
  540.     leading_context = 10 * leading_context + c - '0';
  541.     break;
  542.  
  543.       case 'A':
  544.     if (! sscanf(optarg, "%d", &trailing_context)
  545.         || trailing_context < 0)
  546.       usage_and_die();
  547.     break;
  548.  
  549.       case 'B':
  550.     if (! sscanf(optarg, "%d", &leading_context)
  551.         || leading_context < 0)
  552.       usage_and_die();
  553.     break;
  554.  
  555.       case 'C':
  556.     trailing_context = leading_context = 2;
  557.     break;
  558.  
  559.       case 'V':
  560.     fprintf(stderr, "%s\n", version);
  561.     break;
  562.  
  563.       case 'b':
  564.     byte_count = 1;
  565.     break;
  566.  
  567.       case 'c':
  568.     count_lines = 1;
  569.     silent = 1;
  570.     break;
  571.  
  572.       case 'e':
  573.     /* It doesn't make sense to mix -f and -e. */
  574.     if (regexp_file)
  575.       usage_and_die();
  576.     the_regexp = optarg;
  577.     break;
  578.  
  579.       case 'f':
  580.     /* It doesn't make sense to mix -f and -e. */
  581.     if (the_regexp)
  582.       usage_and_die();
  583.     regexp_file = optarg;
  584.     break;
  585.  
  586.       case 'h':
  587.     no_filenames = 1;
  588.     break;
  589.  
  590.       case 'i':
  591.     ignore_case = 1;
  592.     for (c = 0; c < _NOTCHAR; ++c)
  593.       if (isupper(c))
  594.         translate[c] = tolower(c);
  595.       else
  596.         translate[c] = c;
  597.     regex.translate = translate;
  598.     break;
  599.  
  600.       case 'l':
  601.     list_files = 1;
  602.     silent = 1;
  603.     break;
  604.  
  605.       case 'n':
  606.     line_numbers = 1;
  607.     break;
  608.  
  609.       case 's':
  610.     silent = 1;
  611.     break;
  612.  
  613.       case 'v':
  614.     nonmatching_lines = 1;
  615.     break;
  616.  
  617.       case 'w':
  618.     whole_word = 1;
  619.     break;
  620.  
  621.       case 'x':
  622.     whole_line = 1;
  623.     break;
  624.  
  625.       default:
  626.     /* This can't happen. */
  627.     fprintf(stderr, "%s: getopt(3) let one by!\n", prog);
  628.     usage_and_die();
  629.     break;
  630.       }
  631.  
  632.   /* Set the syntax depending on whether we are EGREP or not. */
  633. #ifdef EGREP
  634.   regsyntax(RE_SYNTAX_EGREP, ignore_case);
  635.   re_set_syntax(RE_SYNTAX_EGREP);
  636. #else
  637.   regsyntax(RE_SYNTAX_GREP, ignore_case);
  638.   re_set_syntax(RE_SYNTAX_GREP);
  639. #endif
  640.  
  641.   /* Compile the regexp according to all the options. */
  642.   if (regexp_file)
  643.     {
  644.       FILE *fp = fopen(regexp_file, "r");
  645.       int len = 256;
  646.       int i = 0;
  647.  
  648.       if (! fp)
  649.     {
  650.       fprintf(stderr, "%s: %s: %s\n", prog, regexp_file,
  651.           sys_errlist[errno]);
  652.       exit(ERROR);
  653.     }
  654.  
  655.       the_regexp = malloc(len);
  656.       while ((c = getc(fp)) != EOF)
  657.     {
  658.       the_regexp[i++] = c;
  659.       if (i == len)
  660.         the_regexp = realloc(the_regexp, len *= 2);
  661.     }
  662.       fclose(fp);
  663.       /* Nuke the concluding newline so we won't match the empty string. */
  664.       if (i > 0 && the_regexp[i - 1] == '\n')
  665.     --i;
  666.       regexp_len = i;
  667.     }
  668.   else if (! the_regexp)
  669.     {
  670.       if (optind >= argc)
  671.     usage_and_die();
  672.       the_regexp = argv[optind++];
  673.       regexp_len = strlen(the_regexp);
  674.     }
  675.   else
  676.     regexp_len = strlen(the_regexp);
  677.   
  678.   if (whole_word || whole_line)
  679.     {
  680.       char *n = malloc(regexp_len + 8);
  681.       int i = 0;
  682.  
  683.       if (whole_line)
  684.     n[i++] = '^';
  685.       else
  686.     n[i++] = '\\', n[i++] = '<';
  687. #ifndef EGREP
  688.       n[i++] = '\\';
  689. #endif
  690.       n[i++] = '(';
  691.       memcpy(n + i, the_regexp, regexp_len);
  692.       i += regexp_len;
  693. #ifndef EGREP
  694.       n[i++] = '\\';
  695. #endif
  696.       n[i++] = ')';
  697.       if (whole_line)
  698.     n[i++] = '$';
  699.       else
  700.     n[i++] = '\\', n[i++] = '>';
  701.       the_regexp = n;
  702.       regexp_len = i;
  703.     }
  704.  
  705.   regcompile(the_regexp, regexp_len, ®, 1);
  706.   
  707.   if (regex_errmesg = re_compile_pattern(the_regexp, regexp_len, ®ex))
  708.     regerror(regex_errmesg);
  709.   
  710.   /*
  711.     Find the longest metacharacter-free string which must occur in the
  712.     regexpr, before short-circuiting regexecute() with Boyer-Moore-Gosper.
  713.     (Conjecture:  The problem in general is NP-complete.)  If there is no
  714.     such string (like for many alternations), then default to full automaton
  715.     search.  regmust() code and heuristics [see dfa.c] courtesy
  716.     Arthur David Olson.
  717.     */
  718.   if (line_numbers == 0 && nonmatching_lines == 0)
  719.     {
  720.       if (reg.mustn == 0 || reg.mustn == MUST_MAX ||
  721.         strchr(reg.must, '\0') != reg.must + reg.mustn)
  722.     bmgexec = 0;
  723.       else
  724.     {
  725.       reg.must[reg.mustn] = '\0';
  726.       if (getenv("MUSTDEBUG") != NULL)
  727.         (void) printf("must have: \"%s\"\n", reg.must);
  728.       bmg_setup(reg.must, ignore_case);
  729.       bmgexec = 1;
  730.     }
  731.     }
  732.   
  733.   if (argc - optind < 2)
  734.     no_filenames = 1;
  735.  
  736.   initialize_buffer();
  737.  
  738.   if (argc > optind)
  739.     while (optind < argc)
  740.       {
  741.     bufprev = eof = 0;
  742.     filename = argv[optind++];
  743.     fd = open(filename, 0, 0);
  744.     if (fd < 0)
  745.       {
  746.         fprintf(stderr, "%s: %s: %s\n", prog, filename,
  747.             sys_errlist[errno]);
  748.         error = 1;
  749.         continue;
  750.       }
  751.     if (line_count = grep())
  752.       matches_found = 1;
  753.     close(fd);
  754.     if (count_lines)
  755.       if (!no_filenames)
  756.         printf("%s:%d\n", filename, line_count);
  757.       else
  758.         printf("%d\n", line_count);
  759.     else if (list_files && line_count)
  760.       printf("%s\n", filename);
  761.       }
  762.   else
  763.     {
  764.       if (line_count = grep())
  765.     matches_found = 1;
  766.       if (count_lines)
  767.     printf("%d\n", line_count);
  768.       else if (list_files && line_count)
  769.     printf("<stdin>\n");
  770.     }
  771.  
  772.   if (error)
  773.     exit(ERROR);
  774.   if (matches_found)
  775.     exit(MATCHES_FOUND);
  776.   exit(NO_MATCHES_FOUND);
  777. }
  778.  
  779. /* Needed by the regexp routines.  This could be fancier, especially when
  780.    dealing with parallel regexps in files. */
  781. void
  782. regerror(s)
  783.      const char *s;
  784. {
  785.   fprintf(stderr, "%s: %s\n", prog, s);
  786.   exit(ERROR);
  787. }
  788.  
  789. /*
  790.    bmg_setup() and bmg_search() adapted from:
  791.      Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  792.      original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  793.      experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  794.      practical value.  However, to improve for worst case input, integrating
  795.      the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  796.      February 1986) deserves consideration.
  797.  
  798.      James A. Woods                Copyleft (C) 1986, 1988
  799.      NASA Ames Research Center
  800. */
  801.  
  802. char *
  803. execute(r, begin, end, newline, count, try_backref)
  804.   struct regexp *r;
  805.   char *begin;
  806.   char *end;
  807.   int newline;
  808.   int *count;
  809.   int *try_backref;
  810. {
  811.   register char *p, *s;
  812.   char *match;
  813.   char *start = begin;
  814.   char save;            /* regexecute() sentinel */
  815.   int len;
  816.   char *bmg_search();
  817.  
  818.   if (!bmgexec)            /* full automaton search */
  819.     return(regexecute(r, begin, end, newline, count, try_backref));
  820.   else
  821.     {
  822.       len = end - begin; 
  823.       while ((match = bmg_search((unsigned char *) start, len)) != NULL)
  824.     {
  825.       p = match;        /* narrow search range to submatch line */
  826.       while (p > begin && *p != '\n')
  827.         p--;
  828.       s = match;
  829.       while (s < end && *s != '\n')
  830.         s++;
  831.       s++;
  832.  
  833.       save = *s;
  834.       *s = '\0';
  835.       match = regexecute(r, p, s, newline, count, try_backref);
  836.       *s = save;
  837.  
  838.       if (match != NULL)
  839.         return((char *) match);
  840.       else
  841.         {
  842.           start = s;
  843.           len = end - start;
  844.         }
  845.     }
  846.       return(NULL);
  847.     }
  848. }
  849.  
  850. #include <ctype.h>
  851. int        delta0[256];
  852. unsigned char   cmap[256];        /* (un)folded characters */
  853. unsigned char    pattern[5000];
  854. int        patlen;
  855.  
  856. char *
  857. bmg_search(buffer, buflen)
  858.   unsigned char *buffer;
  859.   int buflen;
  860. {
  861.   register unsigned char *k, *strend, *s, *buflim;
  862.   register int t;
  863.   int j;
  864.  
  865.   if (patlen > buflen)
  866.     return NULL;
  867.  
  868.   buflim = buffer + buflen;
  869.   if (buflen > patlen * 4)
  870.     strend = buflim - patlen * 4;
  871.   else
  872.     strend = buffer;
  873.  
  874.   s = buffer;
  875.   k = buffer + patlen - 1;
  876.  
  877.   for (;;)
  878.     {
  879.       /* The dreaded inner loop, revisited. */
  880.       while (k < strend && (t = delta0[*k]))
  881.     {
  882.       k += t;
  883.       k += delta0[*k];
  884.       k += delta0[*k];
  885.     }
  886.       while (k < buflim && delta0[*k])
  887.     ++k;
  888.       if (k == buflim)
  889.     break;
  890.     
  891.       j = patlen - 1;
  892.       s = k;
  893.       while (--j >= 0 && cmap[*--s] == pattern[j])
  894.     ;
  895.       /* 
  896.     delta-less shortcut for literati, but 
  897.     short shrift for genetic engineers.
  898.       */
  899.       if (j >= 0)
  900.     k++;
  901.       else         /* submatch */
  902.     return ((char *)k);
  903.     }
  904.   return(NULL);
  905. }
  906.  
  907. #ifdef MSDOS
  908. void
  909. #endif
  910. bmg_setup(pat, folded)            /* compute "boyer-moore" delta table */
  911.   char *pat;
  912.   int folded;
  913. {                    /* ... HAKMEM lives ... */
  914.   int j;
  915.  
  916.   patlen = strlen(pat);
  917.  
  918.   if (folded)                 /* fold case while saving pattern */
  919.     for (j = 0; j < patlen; j++) 
  920.       pattern[j] = (isupper((int) pat[j]) ?
  921.     (char) tolower((int) pat[j]) : pat[j]);
  922.   else
  923.       memcpy(pattern, pat, patlen);
  924.  
  925.   for (j = 0; j < 256; j++)
  926.     {
  927.       delta0[j] = patlen;
  928.       cmap[j] = (char) j;        /* could be done at compile time */
  929.     }
  930.   for (j = 0; j < patlen - 1; j++)
  931.     delta0[pattern[j]] = patlen - j - 1;
  932.   delta0[pattern[patlen - 1]] = 0;
  933.  
  934.   if (folded)
  935.     {
  936.       for (j = 0; j < patlen - 1; j++)
  937.     if (islower((int) pattern[j]))
  938.       delta0[toupper((int) pattern[j])] = patlen - j - 1;
  939.     if (islower((int) pattern[patlen - 1]))
  940.       delta0[toupper((int) pattern[patlen - 1])] = 0;
  941.       for (j = 'A'; j <= 'Z'; j++)
  942.     cmap[j] = (char) tolower((int) j);
  943.     }
  944. }
  945.  
  946. #ifndef USG
  947.  
  948. /* (groan) compatibility */
  949.  
  950. char *
  951. strchr(s, c)
  952.      char *s;
  953. {
  954.   return index(s, c);
  955. }
  956.  
  957. char *
  958. strrchr(s, c)
  959.      char *s;
  960. {
  961.   return rindex(s, c);
  962. }
  963.  
  964. char *
  965. memcpy(d, s, n)
  966.      char *d, *s;
  967. {
  968.   return bcopy(s, d, n);
  969. }
  970.  
  971. #endif /* not USG */
  972.