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