home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / AWK.ZIP / REGEX.C < prev    next >
Encoding:
Text File  |  1988-09-09  |  52.1 KB  |  1,740 lines
  1. /**
  2.  * $Revision:   1.1  $
  3.  * $Log:   C:/AWK/REGEX.C_V  $
  4.  * 
  5.  *    Rev 1.1   09 Sep 1988 18:31:46   vince
  6.  * MC 5.1 version
  7.  * 
  8.  *    Rev 1.0   09 Sep 1988 18:03:20   vince
  9.  * Original source
  10.  *
  11.  * Extended regular expression matching and search.
  12.  *   Copyright (C) 1985 Free Software Foundation, Inc. 
  13.  *
  14.  * NO WARRANTY 
  15.  *
  16.  * BECAUSE THIS PROGRAM IS LICENSED FREE OF CHARGE, WE PROVIDE ABSOLUTELY NO
  17.  * WARRANTY, TO THE EXTENT PERMITTED BY APPLICABLE STATE LAW.  EXCEPT WHEN
  18.  * OTHERWISE STATED IN WRITING, FREE SOFTWARE FOUNDATION, INC, RICHARD M. STALLMAN
  19.  * AND/OR OTHER PARTIES PROVIDE THIS PROGRAM "AS IS" WITHOUT WARRANTY OF ANY
  20.  * KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  21.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE
  22.  * ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.
  23.  * SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY
  24.  * SERVICING, REPAIR OR CORRECTION. 
  25.  *
  26.  * IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL RICHARD M. STALLMAN,
  27.  * THE FREE SOFTWARE FOUNDATION, INC., AND/OR ANY OTHER PARTY WHO MAY MODIFY
  28.  * AND REDISTRIBUTE THIS PROGRAM AS PERMITTED BELOW, BE LIABLE TO YOU FOR
  29.  * DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR OTHER SPECIAL,
  30.  * INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO
  31.  * USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED
  32.  * INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR A FAILURE OF THE PROGRAM TO
  33.  * OPERATE WITH ANY OTHER PROGRAMS) THIS PROGRAM, EVEN IF YOU HAVE BEEN ADVISED
  34.  * OF THE POSSIBILITY OF SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. 
  35.  *
  36.  * GENERAL PUBLIC LICENSE TO COPY 
  37.  *
  38.  * 1. You may copy and distribute verbatim copies of this source file as you
  39.  *    receive it, in any medium, provided that you conspicuously and appropriately
  40.  *    publish on each copy a valid copyright notice "Copyright (C) 1986 Free
  41.  *    Software Foundation, Inc."; and include following the copyright notice
  42.  *    a verbatim copy of the above disclaimer of warranty and of this License. 
  43.  *
  44.  * 2. You may modify your copy or copies of this source file or any portion of
  45.  *    it, and copy and distribute such modifications under the terms of Paragraph 1
  46.  *    above, provided that you also do the following: 
  47.  *
  48.  *    a) cause the modified files to carry prominent notices stating that you changed
  49.  *       the files and the date of any change; and 
  50.  *
  51.  *    b) cause the whole of any work that you distribute or publish, that in whole or
  52.  *       in part contains or is a derivative of this program or any part thereof,
  53.  *       to be freely distributed and licensed to all third parties on terms identical
  54.  *       to those contained in this License Agreement (except that you may choose
  55.  *       to grant more extensive warranty protection to third parties, at your option). 
  56.  *
  57.  * 3. You may copy and distribute this program or any portion of it in compiled,
  58.  *    executable or object code form under the terms of Paragraphs 1 and 2 above
  59.  *    provided that you do the following: 
  60.  *
  61.  *    a) cause each such copy to be accompanied by the corresponding machine-
  62.  *       readable source code, which must be distributed under the terms of
  63.  *       Paragraphs 1 and 2 above; or, 
  64.  *
  65.  *    b) cause each such copy to be accompanied by a written offer, with no
  66.  *       time limit, to give any third party free (except for a nominal shipping
  67.  *       charge) a machine readable copy of the corresponding source code, to be
  68.  *       distributed under the terms of Paragraphs 1 and 2 above; or, 
  69.  *
  70.  *    c) in the case of a recipient of this program in compiled, executable or
  71.  *       object code form (without the corresponding source code) you shall
  72.  *       cause copies you distribute to be accompanied by a copy of the written
  73.  *       offer of source code which you received along with the copy you received. 
  74.  *
  75.  * 4. You may not copy, sublicense, distribute or transfer this program except as
  76.  *    expressly provided under this License Agreement.  Any attempt otherwise
  77.  *    to copy, sublicense, distribute or transfer this program is void and your
  78.  *    rights to use the program under this License agreement shall be
  79.  *    automatically terminated.  However, parties who have received computer
  80.  *    software programs from you with this License Agreement will not have their
  81.  *    licenses terminated so long as such parties remain in full compliance. 
  82.  *
  83.  *
  84.  * In other words, you are welcome to use, share and improve this program.
  85.  * You are forbidden to forbid anyone else to use, share and
  86.  * improve what you give them.   Help stamp out software-hoarding!
  87.  *
  88.  * Modifications by Andrew D. Estes, July 1988 
  89.  */
  90.  
  91. #include "awk.h"
  92.  
  93. /*
  94.  * To test, compile with -Dtest. This Dtestable feature turns this into a
  95.  * self-contained program which reads a pattern, describes
  96.  * how it compiles, then reads a string and searches for it.  
  97.  */
  98.  
  99. /*
  100.  * JF this var has taken on whole new meanings as time goes by.
  101.  * Various bits in this int tell how certain pieces of syntax should work 
  102.  */
  103.  
  104. static int obscure_syntax = 0;
  105.  
  106. #ifdef emacs
  107.  
  108. /*
  109.  * The `emacs' switch turns on certain special matching commands that make sense only in emacs. 
  110.  */
  111.  
  112. #include "config.h"
  113. #include "lisp.h"
  114. #include "buffer.h"
  115. #include "syntax.h"
  116.  
  117. #else
  118.  
  119. /*
  120.  * Define the syntax stuff, so we can do the \<...\> things. 
  121.  */
  122.  
  123. #ifndef Sword
  124. #define Sword 1
  125. #endif
  126.  
  127. #define SYNTAX(c) re_syntax_table[c]
  128.  
  129. #ifdef SYNTAX_TABLE
  130.  
  131. char *re_syntax_table;
  132.  
  133. #else
  134.  
  135. static char re_syntax_table[256];
  136.  
  137. static void init_syntax_once()
  138. {
  139.    register int c;
  140.    static int done = 0;
  141.  
  142.    if (done)
  143.       return;
  144.  
  145.    bzero(re_syntax_table, sizeof re_syntax_table);
  146.  
  147.    for (c = 'a'; c <= 'z'; c++)
  148.       re_syntax_table[c] = Sword;
  149.  
  150.    for (c = 'A'; c <= 'Z'; c++)
  151.       re_syntax_table[c] = Sword;
  152.  
  153.    for (c = '0'; c <= '9'; c++)
  154.       re_syntax_table[c] = Sword;
  155.  
  156.    done = 1;
  157. }
  158.  
  159. #endif
  160. #endif
  161.  
  162. #include "regex.h"
  163.  
  164. /*
  165.  * Number of failure points to allocate space for initially, when matching.  If this number is exceeded, more space is allocated,
  166.  * so it is not a hard limit.  
  167.  */
  168.  
  169. #ifndef NFAILURES
  170. #define NFAILURES 80
  171. #endif
  172.  
  173. /* width of a byte in bits */
  174.  
  175. #define BYTEWIDTH 8
  176.  
  177. #ifndef SIGN_EXTEND_CHAR
  178. #define SIGN_EXTEND_CHAR(x) (x)
  179. #endif
  180.  
  181.  
  182. /*
  183.  * compile_pattern takes a regular-expression descriptor string in the user's
  184.  * format and converts it into a buffer full of byte commands for matching. 
  185.  *
  186.  *    pattern   is the address of the pattern string
  187.  *    size      is the length of it.
  188.  *    bufp      is a  struct re_pattern_buffer
  189.  * which points to the info on where to store the byte commands. This structure
  190.  * contains a  char *  which points to the actual space, which should have
  191.  * been obtained with malloc. compile_pattern may use  realloc  to grow the
  192.  * buffer space. 
  193.  *
  194.  * The number of bytes of commands can be found out by looking in the
  195.  * struct re_pattern_buffer  that bufp pointed to, after compile_pattern returns. 
  196.  */
  197.  
  198. #define PATPUSH(ch) (*b++ = (char) (ch))
  199.  
  200. #define PATFETCH(c) \
  201.  {if (p == pend) goto end_of_pattern; \
  202.   c = * (unsigned char *) p++; \
  203.   if (translate) c = translate[c]; }
  204.  
  205. #define PATFETCH_RAW(c) \
  206.  {if (p == pend) goto end_of_pattern; \
  207.   c = * (unsigned char *) p++; }
  208.  
  209. #define PATUNFETCH p--
  210.  
  211. #define EXTEND_BUFFER 
  212.  
  213. static int store_jump(), insert_jump();
  214.  
  215. /*
  216.  * JF this function is used to compile UN*X style regexps.  In particular, ( ) and | don't have to be \ed to have a special meaning 
  217.  */
  218.  
  219. int re_set_syntax(syntax)
  220. {
  221.    int ret;
  222.  
  223.    ret = obscure_syntax;
  224.    obscure_syntax = syntax;
  225.    return ret;
  226. }
  227.  
  228. char *re_compile_pattern(pattern, size, bufp)
  229. char *pattern;
  230. int size;
  231. struct re_pattern_buffer *bufp;
  232. {
  233.    register char *b = bufp->buffer;
  234.    register char *p = pattern;
  235.    char *pend = pattern + size;
  236.    register unsigned c, c1;
  237.    char *p1;
  238.    unsigned char *translate = (unsigned char *) bufp->translate;
  239.  
  240.    /*
  241.     * address of the count-byte of the most recently inserted "exactn" command.
  242.     * This makes it possible to tell whether a new exact-match character can
  243.     * be added to that command or requires a new "exactn" command. 
  244.     */
  245.  
  246.    char *pending_exact = 0;
  247.  
  248.    /*
  249.     * address of the place where a forward-jump should go to the end of the
  250.     * containing expression. Each alternative of an "or", except the last,
  251.     * ends with a forward-jump of this sort. 
  252.     */
  253.  
  254.    char *fixup_jump = 0;
  255.  
  256.    /*
  257.     * address of start of the most recently finished expression. This tells
  258.     * postfix where to find the start of its operand. 
  259.     */
  260.  
  261.    char *laststart = 0;
  262.  
  263.    /* In processing a repeat, 1 means zero matches is allowed */
  264.  
  265.    char zero_times_ok;
  266.  
  267.    /* In processing a repeat, 1 means many matches is allowed */
  268.  
  269.    char many_times_ok;
  270.  
  271.    /* address of beginning of regexp, or inside of last \( */
  272.  
  273.    char *begalt = b;
  274.  
  275.    /*
  276.     * Stack of information saved by \( and restored by \). Four stack elements
  277.     * are pushed by each \(:
  278.     *   First, the value of b.
  279.     *   Second, the value of fixup_jump.
  280.     *   Third, the value of regnum.
  281.     *   Fourth, the value of begalt.  
  282.     */
  283.  
  284.    int stackb[40];
  285.    int *stackp = stackb;
  286.    int *stacke = stackb + 40;
  287.    int *stackt;
  288.  
  289.    /*
  290.     * Counts \('s as they are encountered.  Remembered for the matching \),
  291.     * where it becomes the "register number" to put in the stop_memory command 
  292.     */
  293.  
  294.    int regnum = 1;
  295.  
  296.    bufp->fastmap_accurate = 0;
  297.  
  298. #ifndef emacs
  299. #ifndef SYNTAX_TABLE
  300.    /*
  301.     * Initialize the syntax table. 
  302.     */
  303.    init_syntax_once();
  304. #endif
  305. #endif
  306.  
  307.    if (bufp->allocated == 0)
  308.    {
  309.       bufp->allocated = 28;
  310.       if (bufp->buffer)
  311.          /* EXTEND_BUFFER loses when bufp->allocated is 0 */
  312.          bufp->buffer = (char *) realloc(bufp->buffer, 28);
  313.       else
  314.          /* Caller did not allocate a buffer.  Do it for him */
  315.          bufp->buffer = (char *) malloc(28);
  316.       if (!bufp->buffer)
  317.          goto memory_exhausted;
  318.       begalt = b = bufp->buffer;
  319.    }
  320.  
  321.    while (p != pend)
  322.    {
  323.       if (b - bufp->buffer > bufp->allocated - 10)
  324.          /* Note that EXTEND_BUFFER clobbers c */
  325.          EXTEND_BUFFER;
  326.  
  327.       PATFETCH(c);
  328.  
  329.       switch (c)
  330.       {
  331.       case '$':
  332.          /*
  333.           * $ means succeed if at end of line, but only in special contexts.
  334.           * If randomly in the middle of a pattern, it is a normal character. 
  335.           */
  336.          if (p == pend || (*p == '\\' && (p[1] == ')' || p[1] == '|')))
  337.          {
  338.             PATPUSH(endline);
  339.             break;
  340.          }
  341.          goto normal_char;
  342.  
  343.       case '^':
  344.          /* ^ means succeed if at beg of line, but only if no preceding pattern. */
  345.          if (laststart)
  346.             goto normal_char;
  347.          PATPUSH(begline);
  348.          break;
  349.  
  350.       case '*':
  351.       case '+':
  352.       case '?':
  353.          /* If there is no previous pattern, char not special. */
  354.          if (!laststart)
  355.             goto normal_char;
  356.          /*
  357.           * If there is a sequence of repetition chars, collapse it down to equivalent to just one.  
  358.           */
  359.          zero_times_ok = 0;
  360.          many_times_ok = 0;
  361.          while (1)
  362.          {
  363.             zero_times_ok |= c != '+';
  364.             many_times_ok |= c != '?';
  365.             if (p == pend)
  366.                break;
  367.             PATFETCH(c);
  368.             if (!(c == '*' || c == '+' || c == '?'))
  369.             {
  370.                PATUNFETCH;
  371.                break;
  372.             }
  373.          }
  374.  
  375.          /*
  376.           * Now we know whether 0 matches is allowed, and whether 2 or more matches is allowed.  
  377.           */
  378.          if (many_times_ok)
  379.          {
  380.             /*
  381.              * If more than one repetition is allowed, put in a backward jump at the end.  
  382.              */
  383.             store_jump(b, maybe_finalize_jump, laststart - 3);
  384.             b += 3;
  385.          }
  386.          insert_jump(on_failure_jump, laststart, b + 3, b);
  387.          pending_exact = 0;
  388.          b += 3;
  389.          if (!zero_times_ok)
  390.          {
  391.             /*
  392.              * At least one repetition required: insert before the loop a skip over the initial on-failure-jump instruction 
  393.              */
  394.             insert_jump(dummy_failure_jump, laststart, laststart + 6, b);
  395.             b += 3;
  396.          }
  397.          break;
  398.  
  399.       case '.':
  400.          laststart = b;
  401.          PATPUSH(anychar);
  402.          break;
  403.  
  404.       case '[':
  405.          if (b - bufp->buffer
  406.              > bufp->allocated - 3 - (1 << BYTEWIDTH) / BYTEWIDTH)
  407.             /* Note that EXTEND_BUFFER clobbers c */
  408.             EXTEND_BUFFER;
  409.  
  410.          laststart = b;
  411.          if (*p == '^')
  412.             PATPUSH(charset_not), p++;
  413.          else
  414.             PATPUSH(charset);
  415.          p1 = p;
  416.  
  417.          PATPUSH((1 << BYTEWIDTH) / BYTEWIDTH);
  418.          /* Clear the whole map */
  419.          bzero(b, (1 << BYTEWIDTH) / BYTEWIDTH);
  420.          /* Read in characters and ranges, setting map bits */
  421.          while (1)
  422.          {
  423.             PATFETCH(c);
  424.             if (c == ']' && p != p1 + 1)
  425.                break;
  426.             if (*p == '-')
  427.             {
  428.                PATFETCH(c1);
  429.                PATFETCH(c1);
  430.                while (c <= c1)
  431.                   b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH), c++;
  432.             }
  433.             else
  434.             {
  435.                b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH);
  436.             }
  437.          }
  438.          /*
  439.           * Discard any bitmap bytes that are all 0 at the end of the map. Decrement the map-length byte too. 
  440.           */
  441.          while (b[-1] > 0 && b[b[-1] - 1] == 0)
  442.             b[-1]--;
  443.          b += b[-1];
  444.          break;
  445.  
  446.       case '(':
  447.          if (!(obscure_syntax & RE_NO_BK_PARENS))
  448.             goto normal_char;
  449.          if (stackp == stacke)
  450.             goto nesting_too_deep;
  451.          if (regnum < RE_NREGS)
  452.          {
  453.             PATPUSH(start_memory);
  454.             PATPUSH(regnum);
  455.          }
  456.          *stackp++ = b - bufp->buffer;
  457.          *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0;
  458.          *stackp++ = regnum++;
  459.          *stackp++ = begalt - bufp->buffer;
  460.          fixup_jump = 0;
  461.          laststart = 0;
  462.          begalt = b;
  463.          break;
  464.  
  465.       case ')':
  466.          if (!(obscure_syntax & RE_NO_BK_PARENS))
  467.             goto normal_char;
  468.          if (stackp == stackb)
  469.             goto unmatched_close;
  470.          begalt = *--stackp + bufp->buffer;
  471.          if (fixup_jump)
  472.             store_jump(fixup_jump, jump, b);
  473.          if (stackp[-1] < RE_NREGS)
  474.          {
  475.             PATPUSH(stop_memory);
  476.             PATPUSH(stackp[-1]);
  477.          }
  478.          stackp -= 2;
  479.          fixup_jump = 0;
  480.          if (*stackp)
  481.             fixup_jump = *stackp + bufp->buffer - 1;
  482.          laststart = *--stackp + bufp->buffer;
  483.          break;
  484.  
  485.       case '|':
  486.          if (!(obscure_syntax & RE_NO_BK_VBAR))
  487.             goto normal_char;
  488.          insert_jump(on_failure_jump, begalt, b + 6, b);
  489.          pending_exact = 0;
  490.          b += 3;
  491.          if (fixup_jump)
  492.             store_jump(fixup_jump, jump, b);
  493.          fixup_jump = b;
  494.          b += 3;
  495.          laststart = 0;
  496.          begalt = b;
  497.          break;
  498.  
  499.       case '\\':
  500.          if (p == pend)
  501.             goto invalid_pattern;
  502.          PATFETCH_RAW(c);
  503.          switch (c)
  504.          {
  505. #ifdef emacs
  506.          case '=':
  507.             PATPUSH(at_dot);
  508.             break;
  509.  
  510.          case 's':
  511.             laststart = b;
  512.             PATPUSH(syntaxspec);
  513.             PATFETCH(c);
  514.             PATPUSH(syntax_spec_code[c]);
  515.             break;
  516.  
  517.          case 'S':
  518.             laststart = b;
  519.             PATPUSH(notsyntaxspec);
  520.             PATFETCH(c);
  521.             PATPUSH(syntax_spec_code[c]);
  522.             break;
  523. #endif
  524.  
  525.          case '(':
  526.             if (obscure_syntax & RE_NO_BK_PARENS)
  527.                goto normal_backsl;
  528.             if (stackp == stacke)
  529.                goto nesting_too_deep;
  530.             if (regnum < RE_NREGS)
  531.             {
  532.                PATPUSH(start_memory);
  533.                PATPUSH(regnum);
  534.             }
  535.             *stackp++ = b - bufp->buffer;
  536.             *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0;
  537.             *stackp++ = regnum++;
  538.             *stackp++ = begalt - bufp->buffer;
  539.             fixup_jump = 0;
  540.             laststart = 0;
  541.             begalt = b;
  542.             break;
  543.  
  544.          case ')':
  545.             if (obscure_syntax & RE_NO_BK_PARENS)
  546.                goto normal_backsl;
  547.             if (stackp == stackb)
  548.                goto unmatched_close;
  549.             begalt = *--stackp + bufp->buffer;
  550.             if (fixup_jump)
  551.                store_jump(fixup_jump, jump, b);
  552.             if (stackp[-1] < RE_NREGS)
  553.             {
  554.                PATPUSH(stop_memory);
  555.                PATPUSH(stackp[-1]);
  556.             }
  557.             stackp -= 2;
  558.             fixup_jump = 0;
  559.             if (*stackp)
  560.                fixup_jump = *stackp + bufp->buffer - 1;
  561.             laststart = *--stackp + bufp->buffer;
  562.             break;
  563.  
  564.          case '|':
  565.             if (obscure_syntax & RE_NO_BK_VBAR)
  566.                goto normal_backsl;
  567.             insert_jump(on_failure_jump, begalt, b + 6, b);
  568.             pending_exact = 0;
  569.             b += 3;
  570.             if (fixup_jump)
  571.                store_jump(fixup_jump, jump, b);
  572.             fixup_jump = b;
  573.             b += 3;
  574.             laststart = 0;
  575.             begalt = b;
  576.             break;
  577.  
  578.          case 'w':
  579.             laststart = b;
  580.             PATPUSH(wordchar);
  581.             break;
  582.  
  583.          case 'W':
  584.             laststart = b;
  585.             PATPUSH(notwordchar);
  586.             break;
  587.  
  588.          case '<':
  589.             PATPUSH(wordbeg);
  590.             break;
  591.  
  592.          case '>':
  593.             PATPUSH(wordend);
  594.             break;
  595.  
  596.          case 'b':
  597.             PATPUSH(wordbound);
  598.             break;
  599.  
  600.          case 'B':
  601.             PATPUSH(notwordbound);
  602.             break;
  603.  
  604.          case '`':
  605.             PATPUSH(begbuf);
  606.             break;
  607.  
  608.          case '\'':
  609.             PATPUSH(endbuf);
  610.             break;
  611.  
  612.          case '1':
  613.          case '2':
  614.          case '3':
  615.          case '4':
  616.          case '5':
  617.          case '6':
  618.          case '7':
  619.          case '8':
  620.          case '9':
  621.             c1 = c - '0';
  622.             if (c1 >= regnum)
  623.                goto normal_char;
  624.             for (stackt = stackp - 2; stackt > stackb; stackt -= 4)
  625.                if (*stackt == c1)
  626.                   goto normal_char;
  627.             laststart = b;
  628.             PATPUSH(duplicate);
  629.             PATPUSH(c1);
  630.             break;
  631.          default:
  632.       normal_backsl:
  633.             /*
  634.              * You might think it wuld be useful for \ to mean not to
  635.              * translate; but if we don't translate it it will never match
  636.              * anything.  
  637.              */
  638.             if (translate)
  639.                c = translate[c];
  640.             goto normal_char;
  641.          }
  642.          break;
  643.  
  644.       default:
  645.    normal_char:
  646.          if (!pending_exact || pending_exact + *pending_exact + 1 != b
  647.              || *pending_exact == 0177 || *p == '*' || *p == '^'
  648.              || *p == '+' || *p == '?')
  649.          {
  650.             laststart = b;
  651.             PATPUSH(exactn);
  652.             pending_exact = b;
  653.             PATPUSH(0);
  654.          }
  655.          PATPUSH(c);
  656.          (*pending_exact)++;
  657.       }
  658.    }
  659.  
  660.    if (fixup_jump)
  661.       store_jump(fixup_jump, jump, b);
  662.  
  663.    if (stackp != stackb)
  664.       goto unmatched_open;
  665.  
  666.    bufp->used = b - bufp->buffer;
  667.    return 0;
  668.  
  669. invalid_pattern:
  670.    return "Invalid regular expression";
  671.  
  672. unmatched_open:
  673.    return "Unmatched \\(";
  674.  
  675. unmatched_close:
  676.    return "Unmatched \\)";
  677.  
  678. end_of_pattern:
  679.    return "Premature end of regular expression";
  680.  
  681. nesting_too_deep:
  682.    return "Nesting too deep";
  683.  
  684. too_big:
  685.    return "Regular expression too big";
  686.  
  687. memory_exhausted:
  688.    return "Memory exhausted";
  689. }
  690.  
  691. /*
  692.  * Store where `from' points a jump operation to jump to where `to' points. `opcode' is the opcode to store. 
  693.  */
  694.  
  695. static int store_jump(from, opcode, to)
  696. char *from, *to;
  697. char opcode;
  698. {
  699.    from[0] = opcode;
  700.    from[1] = (to - (from + 3)) & 0377;
  701.    from[2] = (to - (from + 3)) >> 8;
  702. }
  703.  
  704. /*
  705.  * Open up space at char FROM, and insert there a jump to TO.
  706.  * CURRENT_END gives te end of the storage no in use, so we know how
  707.  * much data to copy up. OP is the opcode of the jump to insert. 
  708.  *
  709.  * If you call this function, you must zero out pending_exact.  
  710.  */
  711.  
  712. static int insert_jump(op, from, to, current_end)
  713. char op;
  714. char *from, *to, *current_end;
  715. {
  716.    register char *pto = current_end + 3;
  717.    register char *pfrom = current_end;
  718.    while (pfrom != from)
  719.       *--pto = *--pfrom;
  720.    store_jump(from, op, to);
  721. }
  722.  
  723.  
  724. /*
  725.  * Given a pattern, compute a fastmap from it. The fastmap records which of
  726.  * the (1 << BYTEWIDTH) possible characters can start a string that matches
  727.  * the pattern. This fastmap is used by re_search to skip quickly over
  728.  * totally implausible text. 
  729.  *
  730.  * The caller must supply the address of a (1 << BYTEWIDTH)-byte data area
  731.  * as bufp->fastmap. The other components of bufp describe the pattern to be
  732.  * used.  
  733.  */
  734.  
  735. void re_compile_fastmap(bufp)
  736. struct re_pattern_buffer *bufp;
  737. {
  738.    unsigned char *pattern = (unsigned char *) bufp->buffer;
  739.    int size = bufp->used;
  740.    register char *fastmap = bufp->fastmap;
  741.    register unsigned char *p = pattern;
  742.    register unsigned char *pend = pattern + size;
  743.    register int j, k;
  744.    unsigned char *translate = (unsigned char *) bufp->translate;
  745.  
  746.    unsigned char *stackb[NFAILURES];
  747.    unsigned char **stackp = stackb;
  748.  
  749.    bzero(fastmap, (1 << BYTEWIDTH));
  750.    bufp->fastmap_accurate = 1;
  751.    bufp->can_be_null = 0;
  752.  
  753.    while (p)
  754.    {
  755.       if (p == pend)
  756.       {
  757.          bufp->can_be_null = 1;
  758.          break;
  759.       }
  760. #ifdef SWITCH_ENUM_BUG
  761.       switch ((int) ((enum regexpcode) * p++))
  762. #else
  763.       switch ((enum regexpcode) * p++)
  764. #endif
  765.       {
  766.       case exactn:
  767.          if (translate)
  768.             fastmap[translate[p[1]]] = 1;
  769.          else
  770.             fastmap[p[1]] = 1;
  771.          break;
  772.  
  773.       case begline:
  774.       case before_dot:
  775.       case at_dot:
  776.       case after_dot:
  777.       case begbuf:
  778.       case endbuf:
  779.       case wordbound:
  780.       case notwordbound:
  781.       case wordbeg:
  782.       case wordend:
  783.          continue;
  784.  
  785.       case endline:
  786.          if (translate)
  787.             fastmap[translate['\n']] = 1;
  788.          else
  789.             fastmap['\n'] = 1;
  790.          if (bufp->can_be_null != 1)
  791.             bufp->can_be_null = 2;
  792.          break;
  793.  
  794.       case finalize_jump:
  795.       case maybe_finalize_jump:
  796.       case jump:
  797.       case dummy_failure_jump:
  798.          bufp->can_be_null = 1;
  799.          j = *p++ & 0377;
  800.          j += SIGN_EXTEND_CHAR(*(char *) p) << 8;
  801.          p += j + 1;                   /* The 1 compensates for missing ++ above */
  802.          if (j > 0)
  803.             continue;
  804.          /*
  805.           * Jump backward reached implies we just went through the body of a loop
  806.           * and matched nothing. Opcode jumped to should be an on_failure_jump.
  807.           * Just treat it like an ordinary jump. For a * loop, it has pushed its
  808.           * failure point already; if so, discard that as redundant.  
  809.           */
  810.          if ((enum regexpcode) * p != on_failure_jump)
  811.             continue;
  812.          p++;
  813.          j = *p++ & 0377;
  814.          j += SIGN_EXTEND_CHAR(*(char *) p) << 8;
  815.          p += j + 1;                   /* The 1 compensates for missing ++ above */
  816.          if (stackp != stackb && *stackp == p)
  817.             stackp--;
  818.          continue;
  819.  
  820.       case on_failure_jump:
  821.          j = *p++ & 0377;
  822.          j += SIGN_EXTEND_CHAR(*(char *) p) << 8;
  823.          p++;
  824.          *++stackp = p + j;
  825.          continue;
  826.  
  827.       case start_memory:
  828.       case stop_memory:
  829.          p++;
  830.          continue;
  831.  
  832.       case duplicate:
  833.          bufp->can_be_null = 1;
  834.          fastmap['\n'] = 1;
  835.       case anychar:
  836.          for (j = 0; j < (1 << BYTEWIDTH); j++)
  837.             if (j != '\n')
  838.                fastmap[j] = 1;
  839.          if (bufp->can_be_null)
  840.             return;
  841.          /*
  842.           * Don't return; check the alternative paths so we can set can_be_null if appropriate.  
  843.           */
  844.          break;
  845.  
  846.       case wordchar:
  847.          for (j = 0; j < (1 << BYTEWIDTH); j++)
  848.             if (SYNTAX(j) == Sword)
  849.                fastmap[j] = 1;
  850.          break;
  851.  
  852.       case notwordchar:
  853.          for (j = 0; j < (1 << BYTEWIDTH); j++)
  854.             if (SYNTAX(j) != Sword)
  855.                fastmap[j] = 1;
  856.          break;
  857.  
  858. #ifdef emacs
  859.       case syntaxspec:
  860.          k = *p++;
  861.          for (j = 0; j < (1 << BYTEWIDTH); j++)
  862.             if (SYNTAX(j) == (enum syntaxcode) k)
  863.                fastmap[j] = 1;
  864.          break;
  865.  
  866.       case notsyntaxspec:
  867.          for (j = 0; j < (1 << BYTEWIDTH); j++)
  868.             if (SYNTAX(j) != (enum syntaxcode) k)
  869.                fastmap[j] = 1;
  870.          break;
  871. #endif
  872.  
  873.       case charset:
  874.          for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
  875.             if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
  876.             {
  877.                if (translate)
  878.                   fastmap[translate[j]] = 1;
  879.                else
  880.                   fastmap[j] = 1;
  881.             }
  882.          break;
  883.  
  884.       case charset_not:
  885.          /* Chars beyond end of map must be allowed */
  886.          for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
  887.             if (translate)
  888.                fastmap[translate[j]] = 1;
  889.             else
  890.                fastmap[j] = 1;
  891.  
  892.          for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
  893.             if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
  894.             {
  895.                if (translate)
  896.                   fastmap[translate[j]] = 1;
  897.                else
  898.                   fastmap[j] = 1;
  899.             }
  900.          break;
  901.       }
  902.  
  903.       /*
  904.        * Get here means we have successfully found the possible starting characters of one path of the pattern.  We need not follow
  905.        * this path any farther. Instead, look at the next alternative remembered in the stack. 
  906.        */
  907.       if (stackp != stackb)
  908.          p = *stackp--;
  909.       else
  910.          break;
  911.    }
  912. }
  913.  
  914.  
  915. /* Like re_search_2, below, but only one string is specified. */
  916.  
  917. int re_search(pbufp, string, size, startpos, range, regs)
  918. struct re_pattern_buffer *pbufp;
  919. char *string;
  920. int size, startpos, range;
  921. struct re_registers *regs;
  922. {
  923.    return re_search_2(pbufp, 0, 0, string, size, startpos, range, regs, size);
  924. }
  925.  
  926. /*
  927.  * Like re_match_2 but tries first a match starting at index `startpos', then
  928.  * at startpos + 1, and so on. `range' is the number of places to try before
  929.  * giving up. If `range' is negative, the starting positions tried are startpos,
  930.  * startpos - 1, etc. It is up to the caller to make sure that range is not so
  931.  * large as to take the starting position outside of the input strings. 
  932.  *
  933.  * The value returned is the position at which the match was found, or -1 if no match was found. 
  934.  */
  935.  
  936. int re_search_2(pbufp, string1, size1, string2, size2, startpos, range, regs, mstop)
  937. struct re_pattern_buffer *pbufp;
  938. char *string1, *string2;
  939. int size1, size2;
  940. int startpos;
  941. register int range;
  942. struct re_registers *regs;
  943. int mstop;
  944. {
  945.    register char *fastmap = pbufp->fastmap;
  946.    register char *translate = pbufp->translate;
  947.    int total = size1 + size2;
  948.  
  949.    /* Update the fastmap now if not correct already */
  950.    if (fastmap && !pbufp->fastmap_accurate)
  951.       re_compile_fastmap(pbufp);
  952.  
  953.    while (1)
  954.    {
  955.       /*
  956.        * If a fastmap is supplied, skip quickly over characters that cannot possibly be the start of a match. Note, however, that
  957.        * if the pattern can possibly match the null string, we must test it at each starting point so that we take the first null
  958.        * string we get.  
  959.        */
  960.  
  961.       if (fastmap && startpos < total && pbufp->can_be_null != 1)
  962.       {
  963.          if (range > 0)
  964.          {
  965.             register int lim = 0;
  966.             register char *p;
  967.             int irange = range;
  968.             if (startpos < size1 && startpos + range >= size1)
  969.                lim = range - (size1 - startpos);
  970.  
  971.             p = &(startpos >= size1 ? string2 - size1 : string1)[startpos];
  972.  
  973.             if (translate)
  974.             {
  975.                while (range > lim && !fastmap[translate[*p++]])
  976.                   range--;
  977.             }
  978.             else
  979.             {
  980.                while (range > lim && !fastmap[*p++])
  981.                   range--;
  982.             }
  983.             startpos += irange - range;
  984.          }
  985.          else
  986.          {
  987.             register char c;
  988.             if (startpos >= size1)
  989.                c = string2[startpos - size1];
  990.             else
  991.                c = string1[startpos];
  992.             if (translate ? !fastmap[translate[c]] : !fastmap[c])
  993.                goto advance;
  994.          }
  995.       }
  996.  
  997.       if (range >= 0 && startpos == total && fastmap && pbufp->can_be_null == 0)
  998.          return -1;
  999.  
  1000.       if (0 <= re_match_2(pbufp, string1, size1, string2, size2, startpos, regs, mstop))
  1001.          return startpos;
  1002.  
  1003. #ifdef C_ALLOCA
  1004.       alloca(0);
  1005. #endif
  1006.  
  1007. advance:
  1008.       if (!range)
  1009.          break;
  1010.       if (range > 0)
  1011.          range--, startpos++;
  1012.       else
  1013.          range++, startpos--;
  1014.    }
  1015.    return -1;
  1016. }
  1017.  
  1018.  
  1019. #ifndef emacs
  1020. int re_match(pbufp, string, size, pos, regs)
  1021. struct re_pattern_buffer *pbufp;
  1022. char *string;
  1023. int size, pos;
  1024. struct re_registers *regs;
  1025. {
  1026.    return re_match_2(pbufp, 0, 0, string, size, pos, regs, size);
  1027. }
  1028. #endif
  1029.  
  1030. /*
  1031.  * Match the pattern described by `pbufp' against data which is the virtual
  1032.  * concatenation of `string1' and `string2'. `size1' and `size2' are the sizes
  1033.  * of the two data strings. Start the match at position `pos'. Do not consider
  1034.  * matching past the position `mstop'. 
  1035.  *
  1036.  * If pbufp->fastmap is nonzero, then it had better be up to date. 
  1037.  *
  1038.  * The reason that the data to match is specified as two components which are to
  1039.  * be regarded as concatenated is so that this function can be used directly
  1040.  * on the contents of an Emacs buffer. 
  1041.  *
  1042.  * -1 is returned if there is no match.  Otherwise the value is the length of
  1043.  * the substring which was matched. 
  1044.  */
  1045.  
  1046. int re_match_2(pbufp, string1, size1, string2, size2, pos, regs, mstop)
  1047. struct re_pattern_buffer *pbufp;
  1048. char *string1, *string2;
  1049. int size1, size2;
  1050. int pos;
  1051. struct re_registers *regs;
  1052. int mstop;
  1053. {
  1054.    register char *p = pbufp->buffer;
  1055.    register char *pend = p + pbufp->used;
  1056.    /* End of first string */
  1057.    char *end1;
  1058.    /* End of second string */
  1059.    char *end2;
  1060.    /* Pointer just past last char to consider matching */
  1061.    char *end_match_1, *end_match_2;
  1062.    register char *d, *dend;
  1063.    register int mcnt;
  1064.    char *translate = pbufp->translate;
  1065.  
  1066.    /*
  1067.     * Failure point stack.  Each place that can handle a failure further down the line pushes a failure point on this stack.  It
  1068.     * consists of two char *'s. The first one pushed is where to resume scanning the pattern; the second pushed is where to resume
  1069.     * scanning the strings. If the latter is zero, the failure point is a "dummy". If a failure happens and the innermost failure
  1070.     * point is dormant, it discards that failure point and tries the next one. 
  1071.     */
  1072.  
  1073.    char **stackb = (char **) alloca(2 * NFAILURES * sizeof(char *));
  1074.    char **stackp = stackb, **stacke = &stackb[2 * NFAILURES];
  1075.  
  1076.    /*
  1077.     * Information on the "contents" of registers. These are pointers into the input strings; they record just what was matched (on
  1078.     * this attempt) by some part of the pattern. The start_memory command stores the start of a register's contents and the
  1079.     * stop_memory command stores the end. 
  1080.     *
  1081.     * At that point, regstart[regnum] points to the first character in the register, regend[regnum] points to the first character
  1082.     * beyond the end of the register, and regstart_segend[regnum] is either the same as regend[regnum] or else points to the end of
  1083.     * the input string into which regstart[regnum] points. The latter case happens when regstart[regnum] is in string1 and
  1084.     * regend[regnum] is in string2.  
  1085.     */
  1086.  
  1087.    char *regstart[RE_NREGS];
  1088.    char *regstart_segend[RE_NREGS];
  1089.    char *regend[RE_NREGS];
  1090.  
  1091.    /*
  1092.     * Set up pointers to ends of strings. Don't allow the second string to be empty unless both are empty.  
  1093.     */
  1094.    if (!size2)
  1095.    {
  1096.       string2 = string1;
  1097.       size2 = size1;
  1098.       string1 = 0;
  1099.       size1 = 0;
  1100.    }
  1101.    end1 = string1 + size1;
  1102.    end2 = string2 + size2;
  1103.  
  1104.    /* Compute where to stop matching, within the two strings */
  1105.    if (mstop <= size1)
  1106.    {
  1107.       end_match_1 = string1 + mstop;
  1108.       end_match_2 = string2;
  1109.    }
  1110.    else
  1111.    {
  1112.       end_match_1 = end1;
  1113.       end_match_2 = string2 + mstop - size1;
  1114.    }
  1115.  
  1116.    /*
  1117.     * Initialize \( and \) text positions to -1 to mark ones that no \( or \) has been seen for.  
  1118.     */
  1119.  
  1120.    for (mcnt = 0; mcnt < sizeof(regstart) / sizeof(*regstart); mcnt++)
  1121.       regstart[mcnt] = (char *) -1;
  1122.  
  1123.    /*
  1124.     * `p' scans through the pattern as `d' scans through the data. `dend' is the end of the input string that `d' points within.
  1125.     * `d' is advanced into the following input string whenever necessary, but this happens before fetching; therefore, at the
  1126.     * beginning of the loop, `d' can be pointing at the end of a string, but it cannot equal string2.  
  1127.     */
  1128.  
  1129.    if (pos <= size1)
  1130.       d = string1 + pos, dend = end_match_1;
  1131.    else
  1132.       d = string2 + pos - size1, dend = end_match_2;
  1133.  
  1134.    /* Write PREFETCH; just before fetching a character with *d.  */
  1135. #define PREFETCH \
  1136.  while (d == dend)          \
  1137.   { if (dend == end_match_2) goto fail;  /* end of string2 => failure */   \
  1138.     d = string2;  /* end of string1 => advance to string2. */       \
  1139.     dend = end_match_2; }
  1140.  
  1141.    /*
  1142.     * This loop loops over pattern commands. It exits by returning from the
  1143.     * function if match is complete, or it drops through if
  1144.     * match fails at this starting point in the input data. 
  1145.     */
  1146.  
  1147.    while (1)
  1148.    {
  1149.       if (p == pend)        /* End of pattern means we have succeeded! */
  1150.       {
  1151.          /* If caller wants register contents data back, convert it to indices */
  1152.          if (regs)
  1153.          {
  1154.             regend[0] = d;
  1155.             regstart[0] = string1;
  1156.             for (mcnt = 0; mcnt < RE_NREGS; mcnt++)
  1157.             {
  1158.                if ((mcnt != 0) && regstart[mcnt] == (char *) -1)
  1159.                {
  1160.                   regs->start[mcnt] = -1;
  1161.                   regs->end[mcnt] = -1;
  1162.                   continue;
  1163.                }
  1164.                if (regstart[mcnt] - string1 < 0 ||
  1165.                    regstart[mcnt] - string1 > size1)
  1166.                   regs->start[mcnt] = regstart[mcnt] - string2 + size1;
  1167.                else
  1168.                   regs->start[mcnt] = regstart[mcnt] - string1;
  1169.                if (regend[mcnt] - string1 < 0 ||
  1170.                    regend[mcnt] - string1 > size1)
  1171.                   regs->end[mcnt] = regend[mcnt] - string2 + size1;
  1172.                else
  1173.                   regs->end[mcnt] = regend[mcnt] - string1;
  1174.             }
  1175.             regs->start[0] = pos;
  1176.          }
  1177.          if (d - string1 >= 0 && d - string1 <= size1)
  1178.             return d - string1 - pos;
  1179.          else
  1180.             return d - string2 + size1 - pos;
  1181.       }
  1182.  
  1183.       /* Otherwise match next pattern command */
  1184. #ifdef SWITCH_ENUM_BUG
  1185.       switch ((int) ((enum regexpcode) * p++))
  1186. #else
  1187.       switch ((enum regexpcode) * p++)
  1188. #endif
  1189.       {
  1190.          /*
  1191.           * \( is represented by a start_memory, \) by a stop_memory. Both of those commands contain a "register number" argument.
  1192.           * The text matched within the \( and \) is recorded under that number. Then, \<digit> turns into a `duplicate' command
  1193.           * which is followed by the numeric value of <digit> as the register number. 
  1194.           */
  1195.  
  1196.       case start_memory:
  1197.          regstart[*p] = d;
  1198.          regstart_segend[*p++] = dend;
  1199.          break;
  1200.  
  1201.       case stop_memory:
  1202.          regend[*p] = d;
  1203.          if (regstart_segend[*p] == dend)
  1204.             regstart_segend[*p] = d;
  1205.          p++;
  1206.          break;
  1207.  
  1208.       case duplicate:
  1209.          {
  1210.             int regno = *p++;          /* Get which register to match against */
  1211.             register char *d2, *dend2;
  1212.  
  1213.             d2 = regstart[regno];
  1214.             dend2 = regstart_segend[regno];
  1215.             while (1)
  1216.             {
  1217.                /* Advance to next segment in register contents, if necessary */
  1218.                while (d2 == dend2)
  1219.                {
  1220.                   if (dend2 == end_match_2)
  1221.                      break;
  1222.                   if (dend2 == regend[regno])
  1223.                      break;
  1224.                   d2 = string2, dend2 = regend[regno];  /* end of string1 => advance to string2. */
  1225.                }
  1226.                /* At end of register contents => success */
  1227.                if (d2 == dend2)
  1228.                   break;
  1229.  
  1230.                /* Advance to next segment in data being matched, if necessary */
  1231.                PREFETCH;
  1232.  
  1233.                /* mcnt gets # consecutive chars to compare */
  1234.                mcnt = dend - d;
  1235.                if (mcnt > dend2 - d2)
  1236.                   mcnt = dend2 - d2;
  1237.                /* Compare that many; failure if mismatch, else skip them. */
  1238.                if (translate ? bcmp_translate(d, d2, mcnt, translate) : bcmp(d, d2, mcnt))
  1239.                   goto fail;
  1240.                d += mcnt, d2 += mcnt;
  1241.             }
  1242.          }
  1243.          break;
  1244.  
  1245.       case anychar:
  1246.          /* fetch a data character */
  1247.          PREFETCH;
  1248.          /* Match anything but a newline.  */
  1249.          if ((translate ? translate[*d++] : *d++) == '\n')
  1250.             goto fail;
  1251.          break;
  1252.  
  1253.       case charset:
  1254.       case charset_not:
  1255.          {
  1256.             /* Nonzero for charset_not */
  1257.             int not = 0;
  1258.             register int c;
  1259.             if (*(p - 1) == (char) charset_not)
  1260.                not = 1;
  1261.  
  1262.             /* fetch a data character */
  1263.             PREFETCH;
  1264.  
  1265.             if (translate)
  1266.                c = translate[*(unsigned char *) d];
  1267.             else
  1268.                c = *(unsigned char *) d;
  1269.  
  1270.             if (c < *p * BYTEWIDTH
  1271.                 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
  1272.                not = !not;
  1273.  
  1274.             p += 1 + *p;
  1275.  
  1276.             if (!not)
  1277.                goto fail;
  1278.             d++;
  1279.             break;
  1280.          }
  1281.  
  1282.       case begline:
  1283.          if (d == string1 || d[-1] == '\n')
  1284.             break;
  1285.          goto fail;
  1286.  
  1287.       case endline:
  1288.          if (d == end2
  1289.              || (d == end1 ? (size2 == 0 || *string2 == '\n') : *d == '\n'))
  1290.             break;
  1291.          goto fail;
  1292.  
  1293.          /*
  1294.           * "or" constructs ("|") are handled by starting each alternative with an on_failure_jump that points to the start of the
  1295.           * next alternative. Each alternative except the last ends with a jump to the joining point. (Actually, each jump except
  1296.           * for the last one really jumps to the following jump, because tensioning the jumps is a hassle.) 
  1297.           */
  1298.  
  1299.          /*
  1300.           * The start of a stupid repeat has an on_failure_jump that points past the end of the repeat text. This makes a failure
  1301.           * point so that, on failure to match a repetition, matching restarts past as many repetitions have been found with no way
  1302.           * to fail and look for another one.  
  1303.           */
  1304.  
  1305.          /*
  1306.           * A smart repeat is similar but loops back to the on_failure_jump so that each repetition makes another failure point. 
  1307.           */
  1308.  
  1309.       case on_failure_jump:
  1310.          if (stackp == stacke)
  1311.          {
  1312.             char **stackx = (char **) alloca(2 * (stacke - stackb) * sizeof(char *));
  1313.             bcopy(stackb, stackx, (stacke - stackb) * sizeof(char *));
  1314.             stackp += stackx - stackb;
  1315.             stacke = stackx + 2 * (stacke - stackb);
  1316.             stackb = stackx;
  1317.          }
  1318.          mcnt = *p++ & 0377;
  1319.          mcnt += SIGN_EXTEND_CHAR(*p) << 8;
  1320.          p++;
  1321.          *stackp++ = mcnt + p;
  1322.          *stackp++ = d;
  1323.          break;
  1324.  
  1325.          /*
  1326.           * The end of a smart repeat has an maybe_finalize_jump back. Change it either to a finalize_jump or an ordinary jump. 
  1327.           */
  1328.  
  1329.       case maybe_finalize_jump:
  1330.          mcnt = *p++ & 0377;
  1331.          mcnt += SIGN_EXTEND_CHAR(*p) << 8;
  1332.          p++;
  1333.          /*
  1334.           * Compare what follows with the begining of the repeat. If we can establish that there is nothing that they would both
  1335.           * match, we can change to finalize_jump 
  1336.           */
  1337.          if (p == pend)
  1338.             p[-3] = (char) finalize_jump;
  1339.          else
  1340.          if (*p == (char) exactn || *p == (char) endline)
  1341.          {
  1342.             register int c = *p == (char) endline ? '\n' : p[2];
  1343.             register char *p1 = p + mcnt;
  1344.             /*
  1345.              * p1[0] ... p1[2] are an on_failure_jump. Examine what follows that 
  1346.              */
  1347.             if (p1[3] == (char) exactn && p1[5] != c)
  1348.                p[-3] = (char) finalize_jump;
  1349.             else
  1350.             if (p1[3] == (char) charset || p1[3] == (char) charset_not)
  1351.             {
  1352.                int not = p1[3] == (char) charset_not;
  1353.                if (c < p1[4] * BYTEWIDTH
  1354.                    && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
  1355.                   not = !not;
  1356.                /* not is 1 if c would match */
  1357.                /* That means it is not safe to finalize */
  1358.                if (!not)
  1359.                   p[-3] = (char) finalize_jump;
  1360.             }
  1361.          }
  1362.          p -= 2;
  1363.          if (p[-1] != (char) finalize_jump)
  1364.          {
  1365.             p[-1] = (char) jump;
  1366.             goto nofinalize;
  1367.          }
  1368.  
  1369.          /*
  1370.           * The end of a stupid repeat has a finalize-jump back to the start, where another failure point will be made which will
  1371.           * point after all the repetitions found so far. 
  1372.           */
  1373.  
  1374.       case finalize_jump:
  1375.          stackp -= 2;
  1376.  
  1377.       case jump:
  1378.    nofinalize:
  1379.          mcnt = *p++ & 0377;
  1380.          mcnt += SIGN_EXTEND_CHAR(*p) << 8;
  1381.          p += mcnt + 1;                /* The 1 compensates for missing ++ above */
  1382.          break;
  1383.  
  1384.       case dummy_failure_jump:
  1385.          if (stackp == stacke)
  1386.          {
  1387.             char **stackx = (char **) alloca(2 * (stacke - stackb) * sizeof(char *));
  1388.             bcopy(stackb, stackx, (stacke - stackb) * sizeof(char *));
  1389.             stackp += stackx - stackb;
  1390.             stacke = stackx + 2 * (stacke - stackb);
  1391.             stackb = stackx;
  1392.          }
  1393.          *stackp++ = 0;
  1394.          *stackp++ = 0;
  1395.          goto nofinalize;
  1396.  
  1397.       case wordbound:
  1398.          if (d == string1              /* Points to first char */
  1399.              || d == end2              /* Points to end */
  1400.              || (d == end1 && size2 == 0))      /* Points to end */
  1401.             break;
  1402.          if ((SYNTAX(((unsigned char *) d)[-1]) == Sword)
  1403.              != (SYNTAX(d == end1 ? *(unsigned char *) string2 : *(unsigned char *) d) == Sword))
  1404.             break;
  1405.          goto fail;
  1406.  
  1407.       case notwordbound:
  1408.          if (d == string1              /* Points to first char */
  1409.              || d == end2              /* Points to end */
  1410.              || (d == end1 && size2 == 0))      /* Points to end */
  1411.             goto fail;
  1412.          if ((SYNTAX(((unsigned char *) d)[-1]) == Sword)
  1413.              != (SYNTAX(d == end1 ? *(unsigned char *) string2 : *(unsigned char *) d) == Sword))
  1414.             goto fail;
  1415.          break;
  1416.  
  1417.       case wordbeg:
  1418.          if (d == end2                 /* Points to end */
  1419.              || (d == end1 && size2 == 0)       /* Points to end */
  1420.              || SYNTAX(*(unsigned char *) (d == end1 ? string2 : d)) != Sword)  /* Next char not a letter */
  1421.             goto fail;
  1422.          if (d == string1              /* Points to first char */
  1423.              || SYNTAX(((unsigned char *) d)[-1]) != Sword)     /* prev char not letter */
  1424.             break;
  1425.          goto fail;
  1426.  
  1427.       case wordend:
  1428.          if (d == string1              /* Points to first char */
  1429.              || SYNTAX(((unsigned char *) d)[-1]) != Sword)     /* prev char not letter */
  1430.             goto fail;
  1431.          if (d == end2                 /* Points to end */
  1432.              || (d == end1 && size2 == 0)       /* Points to end */
  1433.              || SYNTAX(d == end1 ? *(unsigned char *) string2 : *(unsigned char *) d) != Sword) /* Next char not a letter */
  1434.             break;
  1435.          goto fail;
  1436.  
  1437. #ifdef emacs
  1438.       case before_dot:
  1439.          if (((d - string2 <= (unsigned) size2)
  1440.               ? d - (char *) bf_p2 : d - (char *) bf_p1)
  1441.              <= point)
  1442.             goto fail;
  1443.          break;
  1444.  
  1445.       case at_dot:
  1446.          if (((d - string2 <= (unsigned) size2)
  1447.               ? d - (char *) bf_p2 : d - (char *) bf_p1)
  1448.              == point)
  1449.             goto fail;
  1450.          break;
  1451.  
  1452.       case after_dot:
  1453.          if (((d - string2 <= (unsigned) size2)
  1454.               ? d - (char *) bf_p2 : d - (char *) bf_p1)
  1455.              >= point)
  1456.             goto fail;
  1457.          break;
  1458.  
  1459.       case wordchar:
  1460.          mcnt = (int) Sword;
  1461.          goto matchsyntax;
  1462.  
  1463.       case syntaxspec:
  1464.          mcnt = *p++;
  1465.    matchsyntax:
  1466.          PREFETCH;
  1467.          if (SYNTAX(*(unsigned char *) d++) != (enum syntaxcode) mcnt)
  1468.             goto fail;
  1469.          break;
  1470.  
  1471.       case notwordchar:
  1472.          mcnt = (int) Sword;
  1473.          goto matchnotsyntax;
  1474.  
  1475.       case notsyntaxspec:
  1476.          mcnt = *p++;
  1477.    matchnotsyntax:
  1478.          PREFETCH;
  1479.          if (SYNTAX(*(unsigned char *) d++) == (enum syntaxcode) mcnt)
  1480.             goto fail;
  1481.          break;
  1482. #else
  1483.       case wordchar:
  1484.          PREFETCH;
  1485.          if (SYNTAX(*(unsigned char *) d++) == 0)
  1486.             goto fail;
  1487.          break;
  1488.  
  1489.       case notwordchar:
  1490.          PREFETCH;
  1491.          if (SYNTAX(*(unsigned char *) d++) != 0)
  1492.             goto fail;
  1493.          break;
  1494. #endif
  1495.  
  1496.       case begbuf:
  1497.          if (d == string1)             /* Note, d cannot equal string2 */
  1498.             break;                     /* unless string1 == string2.  */
  1499.          goto fail;
  1500.  
  1501.       case endbuf:
  1502.          if (d == end2 || (d == end1 && size2 == 0))
  1503.             break;
  1504.          goto fail;
  1505.  
  1506.       case exactn:
  1507.          /*
  1508.           * Match the next few pattern characters exactly. mcnt is how many characters to match. 
  1509.           */
  1510.          mcnt = *p++;
  1511.          if (translate)
  1512.          {
  1513.             do
  1514.             {
  1515.                PREFETCH;
  1516.                if (translate[*(unsigned char *) d++] != *p++)
  1517.                   goto fail;
  1518.             }
  1519.             while (--mcnt);
  1520.          }
  1521.          else
  1522.          {
  1523.             do
  1524.             {
  1525.                PREFETCH;
  1526.                if (*d++ != *p++)
  1527.                   goto fail;
  1528.             }
  1529.             while (--mcnt);
  1530.          }
  1531.          break;
  1532.       }
  1533.       continue;                        /* Successfully matched one pattern command; keep matching */
  1534.  
  1535.       /* Jump here if any matching operation fails. */
  1536. fail:
  1537.       if (stackp != stackb)
  1538.          /* A restart point is known.  Restart there and pop it. */
  1539.       {
  1540.          if (!stackp[-2])
  1541.          {                             /* If innermost failure point is dormant, flush it and keep looking */
  1542.             stackp -= 2;
  1543.             goto fail;
  1544.          }
  1545.          d = *--stackp;
  1546.          p = *--stackp;
  1547.          if (d >= string1 && d <= end1)
  1548.             dend = end_match_1;
  1549.       }
  1550.       else
  1551.          break;                        /* Matching at this starting point really fails! */
  1552.    }
  1553.    return -1;                          /* Failure to match */
  1554. }
  1555.  
  1556. static int bcmp_translate(s1, s2, len, translate)
  1557. char *s1, *s2;
  1558. register int len;
  1559. char *translate;
  1560. {
  1561.    register char *p1 = s1, *p2 = s2;
  1562.    while (len)
  1563.    {
  1564.       if (translate[*p1++] != translate[*p2++])
  1565.          return 1;
  1566.       len--;
  1567.    }
  1568.    return 0;
  1569. }
  1570.  
  1571.  
  1572. /* Entry points compatible with bsd4.2 regex library */
  1573.  
  1574. #ifndef emacs
  1575.  
  1576. static struct re_pattern_buffer re_comp_buf;
  1577.  
  1578. char *re_comp(s)
  1579. char *s;
  1580. {
  1581.    if (!s)
  1582.    {
  1583.       if (!re_comp_buf.buffer)
  1584.          return "No previous regular expression";
  1585.       return 0;
  1586.    }
  1587.  
  1588.    if (!re_comp_buf.buffer)
  1589.    {
  1590.       if (!(re_comp_buf.buffer = (char *) malloc(200)))
  1591.          return "Memory exhausted";
  1592.       re_comp_buf.allocated = 200;
  1593.       if (!(re_comp_buf.fastmap = (char *) malloc(1 << BYTEWIDTH)))
  1594.          return "Memory exhausted";
  1595.    }
  1596.    return re_compile_pattern(s, strlen(s), &re_comp_buf);
  1597. }
  1598.  
  1599. int re_exec(s)
  1600. char *s;
  1601. {
  1602.    int len = strlen(s);
  1603.    return 0 <= re_search(&re_comp_buf, s, len, 0, len, 0);
  1604. }
  1605.  
  1606. #endif
  1607.  
  1608.  
  1609. #ifdef test
  1610.  
  1611. #include <stdio.h>
  1612.  
  1613. /* Indexed by a character, gives the upper case equivalent of the character */
  1614.  
  1615. static char upcase[0400] ={
  1616.    000, 001, 002, 003, 004, 005, 006, 007,
  1617.    010, 011, 012, 013, 014, 015, 016, 017,
  1618.    020, 021, 022, 023, 024, 025, 026, 027,
  1619.    030, 031, 032, 033, 034, 035, 036, 037,
  1620.    040, 041, 042, 043, 044, 045, 046, 047,
  1621.    050, 051, 052, 053, 054, 055, 056, 057,
  1622.    060, 061, 062, 063, 064, 065, 066, 067,
  1623.    070, 071, 072, 073, 074, 075, 076, 077,
  1624.    0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
  1625.    0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
  1626.    0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
  1627.    0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137,
  1628.    0140, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
  1629.    0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
  1630.    0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
  1631.    0130, 0131, 0132, 0173, 0174, 0175, 0176, 0177,
  1632.    0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207,
  1633.    0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217,
  1634.    0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227,
  1635.    0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237,
  1636.    0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247,
  1637.    0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257,
  1638.    0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267,
  1639.    0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277,
  1640.    0300, 0301, 0302, 0303, 0304, 0305, 0306, 0307,
  1641.    0310, 0311, 0312, 0313, 0314, 0315, 0316, 0317,
  1642.    0320, 0321, 0322, 0323, 0324, 0325, 0326, 0327,
  1643.    0330, 0331, 0332, 0333, 0334, 0335, 0336, 0337,
  1644.    0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347,
  1645.    0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357,
  1646.    0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367,
  1647.    0370, 0371, 0372, 0373, 0374, 0375, 0376, 0377
  1648. };
  1649.  
  1650. main()
  1651. {
  1652.    char pat[80];
  1653.    struct re_pattern_buffer buf;
  1654.    int i;
  1655.    char c;
  1656.    char fastmap[(1 << BYTEWIDTH)];
  1657.    char *gets();
  1658.  
  1659.    buf.allocated = 40;
  1660.    buf.buffer = (char *) malloc(buf.allocated);
  1661.    buf.fastmap = fastmap;
  1662.    buf.translate = upcase;
  1663.  
  1664.    while (gets(pat))
  1665.    {
  1666.       if (*pat)
  1667.       {
  1668.          re_compile_pattern(pat, strlen(pat), &buf);
  1669.  
  1670.          for (i = 0; i < buf.used; i++)
  1671.             printchar(buf.buffer[i]);
  1672.  
  1673.          putchar('\n');
  1674.  
  1675.          printf("%d allocated, %d used.\n", buf.allocated, buf.used);
  1676.  
  1677.          re_compile_fastmap(&buf);
  1678.          printf("Allowed by fastmap: ");
  1679.          for (i = 0; i < (1 << BYTEWIDTH); i++)
  1680.             if (fastmap[i])
  1681.                printchar(i);
  1682.          putchar('\n');
  1683.       }
  1684.  
  1685.       gets(pat);                       /* Now read the string to match against */
  1686.  
  1687.       i = re_match(&buf, pat, strlen(pat), 0, 0);
  1688.       printf("Match value %d.\n", i);
  1689.    }
  1690. }
  1691.  
  1692. #ifdef NOTDEF
  1693. print_buf(bufp)
  1694. struct re_pattern_buffer *bufp;
  1695. {
  1696.    int i;
  1697.  
  1698.    printf("buf is :\n----------------\n");
  1699.    for (i = 0; i < bufp->used; i++)
  1700.       printchar(bufp->buffer[i]);
  1701.  
  1702.    printf("\n%d allocated, %d used.\n", bufp->allocated, bufp->used);
  1703.  
  1704.    printf("Allowed by fastmap: ");
  1705.    for (i = 0; i < (1 << BYTEWIDTH); i++)
  1706.       if (bufp->fastmap[i])
  1707.          printchar(i);
  1708.    printf("\nAllowed by translate: ");
  1709.    if (bufp->translate)
  1710.       for (i = 0; i < (1 << BYTEWIDTH); i++)
  1711.          if (bufp->translate[i])
  1712.             printchar(i);
  1713.    printf("\nfastmap is%s accurate\n", bufp->fastmap_accurate ? "" : "n't");
  1714.    printf("can %s be null\n----------", bufp->can_be_null ? "" : "not");
  1715. }
  1716. #endif
  1717.  
  1718. printchar(c)
  1719. char c;
  1720. {
  1721.    if (c < 041 || c >= 0177)
  1722.    {
  1723.       putchar('\\');
  1724.       putchar(((c >> 6) & 3) + '0');
  1725.       putchar(((c >> 3) & 7) + '0');
  1726.       putchar((c & 7) + '0');
  1727.    }
  1728.    else
  1729.       putchar(c);
  1730. }
  1731.  
  1732. error(string)
  1733. char *string;
  1734. {
  1735.    puts(string);
  1736.    exit(1);
  1737. }
  1738.  
  1739. #endif
  1740.