home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / cawf407.zip / src / regexp.c < prev    next >
C/C++ Source or Header  |  1993-12-28  |  29KB  |  1,246 lines
  1. /*
  2.  * regcomp and regexec -- regsub and regerror are elsewhere
  3.  *
  4.  *    Copyright (c) 1986 by University of Toronto.
  5.  *    Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *    Permission is granted to anyone to use this software for any
  8.  *    purpose on any computer system, and to redistribute it freely,
  9.  *    subject to the following restrictions:
  10.  *
  11.  *    1. The author is not responsible for the consequences of use of
  12.  *        this software, no matter how awful, even if they arise
  13.  *        from defects in it.
  14.  *
  15.  *    2. The origin of this software must not be misrepresented, either
  16.  *        by explicit claim or by omission.
  17.  *
  18.  *    3. Altered versions must be plainly marked as such, and must not
  19.  *        be misrepresented as being the original software.
  20.  *
  21.  * Beware that some of this code is subtly aware of the way operator
  22.  * precedence is structured in regular expressions.  Serious changes in
  23.  * regular-expression syntax might require a total rethink.
  24.  */
  25. #include <stdio.h>
  26. #ifdef    UNIX
  27. # ifdef    USG
  28. #include <string.h>
  29. # else
  30. #include <strings.h>
  31. # endif
  32. #else
  33. #include <string.h>
  34. # ifdef    _BCC
  35. #pragma warn -rch
  36. # endif
  37. #endif
  38. #include "regexp.h"
  39. #include "regmagic.h"
  40. #include "proto.h"
  41.  
  42. /*
  43.  * The "internal use only" fields in regexp.h are present to pass info from
  44.  * compile to execute that permits the execute phase to run lots faster on
  45.  * simple cases.  They are:
  46.  *
  47.  * regstart    char that must begin a match; '\0' if none obvious
  48.  * reganch    is the match anchored (at beginning-of-line only)?
  49.  * regmust    string (pointer into program) that match must include, or NULL
  50.  * regmlen    length of regmust string
  51.  *
  52.  * Regstart and reganch permit very fast decisions on suitable starting points
  53.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  54.  * of lines that cannot possibly match.  The regmust tests are costly enough
  55.  * that regcomp() supplies a regmust only if the r.e. contains something
  56.  * potentially expensive (at present, the only such thing detected is * or +
  57.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  58.  * supplied because the test in regexec() needs it and regcomp() is computing
  59.  * it anyway.
  60.  */
  61.  
  62. /*
  63.  * Structure for regexp "program".  This is essentially a linear encoding
  64.  * of a nondeterministic finite-state machine (aka syntax charts or
  65.  * "railroad normal form" in parsing technology).  Each node is an opcode
  66.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  67.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  68.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  69.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  70.  * opposed to a collection of them) is never concatenated with anything
  71.  * because of operator precedence.)  The operand of some types of node is
  72.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  73.  * particular, the operand of a BRANCH node is the first node of the branch.
  74.  * (NB this is *not* a tree structure:  the tail of the branch connects
  75.  * to the thing following the set of BRANCHes.)  The opcodes are:
  76.  */
  77.  
  78. /* definition    number    opnd?    meaning */
  79. #define    END    0    /* no    End of program. */
  80. #define    BOL    1    /* no    Match "" at beginning of line. */
  81. #define    EOL    2    /* no    Match "" at end of line. */
  82. #define    ANY    3    /* no    Match any one character. */
  83. #define    ANYOF    4    /* str    Match any character in this string. */
  84. #define    ANYBUT    5    /* str    Match any character not in this string. */
  85. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  86. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  87. #define    EXACTLY    8    /* str    Match this string. */
  88. #define    NOTHING    9    /* no    Match empty string. */
  89. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  90. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  91. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  92.             /*    OPEN+1 is number 1, etc. */
  93. #define    CLOSE    30    /* no    Analogous to OPEN. */
  94.  
  95. /*
  96.  * Opcode notes:
  97.  *
  98.  * BRANCH    The set of branches constituting a single choice are hooked
  99.  *        together with their "next" pointers, since precedence prevents
  100.  *        anything being concatenated to any individual branch.  The
  101.  *        "next" pointer of the last BRANCH in a choice points to the
  102.  *        thing following the whole choice.  This is also where the
  103.  *        final "next" pointer of each individual branch points; each
  104.  *        branch starts with the operand node of a BRANCH node.
  105.  *
  106.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  107.  *        exists to make loop structures possible.
  108.  *
  109.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  110.  *        BRANCH structures using BACK.  Simple cases (one character
  111.  *        per match) are implemented with STAR and PLUS for speed
  112.  *        and to minimize recursive plunges.
  113.  *
  114.  * OPEN,CLOSE    ...are numbered at compile time.
  115.  */
  116.  
  117. /*
  118.  * A node is one char of opcode followed by two chars of "next" pointer.
  119.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  120.  * value is a positive offset from the opcode of the node containing it.
  121.  * An operand, if any, simply follows the node.  (Note that much of the
  122.  * code generation knows about this implicit relationship.)
  123.  *
  124.  * Using two bytes for the "next" pointer is vast overkill for most things,
  125.  * but allows patterns to get big without disasters.
  126.  */
  127. #define    OP(p)    (*(p))
  128. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  129. #define    OPERAND(p)    ((p) + 3)
  130.  
  131. /*
  132.  * See regmagic.h for one further detail of program structure.
  133.  */
  134.  
  135.  
  136. /*
  137.  * Utility definitions.
  138.  */
  139. #ifndef CHARBITS
  140. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  141. #else
  142. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  143. #endif
  144.  
  145. #define    FAIL(m)    { regerror(m); return(NULL); }
  146. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  147. #define    META    "^$.[()|?+*\\"
  148.  
  149. /*
  150.  * Flags to be passed up and down.
  151.  */
  152. #define    HASWIDTH    01    /* Known never to match null string. */
  153. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  154. #define    SPSTART        04    /* Starts with * or +. */
  155. #define    WORST        0    /* Worst case. */
  156. #define STATIC 
  157. /*
  158.  * Global work variables for regcomp().
  159.  */
  160.  
  161. STATIC char *regparse;        /* Input-scan pointer. */
  162. STATIC int regnpar;        /* () count. */
  163. STATIC unsigned char regdummy;
  164. STATIC unsigned char *regcode;    /* Code-emit pointer; ®dummy = don't. */
  165. STATIC long regsize;        /* Code size. */
  166.  
  167. /*
  168.  * Forward declarations for regcomp()'s friends.
  169.  */
  170. _PROTOTYPE(STATIC unsigned char *reg, (int paren, int *flagp ));
  171. _PROTOTYPE(STATIC unsigned char *regbranch, (int *flagp ));
  172. _PROTOTYPE(STATIC unsigned char *regpiece, (int *flagp ));
  173. _PROTOTYPE(STATIC unsigned char *regatom, (int *flagp ));
  174. _PROTOTYPE(STATIC unsigned char *regnode, (int op ));
  175. _PROTOTYPE(STATIC void regc, (int b ));
  176. _PROTOTYPE(STATIC void reginsert, (int op, unsigned char *opnd ));
  177. _PROTOTYPE(STATIC void regtail, (unsigned char *p, unsigned char *val ));
  178. _PROTOTYPE(STATIC void regoptail, (unsigned char *p, unsigned char *val ));
  179. _PROTOTYPE(STATIC int regtry, (regexp *prog, unsigned char *string ));
  180. _PROTOTYPE(STATIC int regmatch, (unsigned char *prog ));
  181. _PROTOTYPE(STATIC int regrepeat, (unsigned char *p ));
  182. _PROTOTYPE(STATIC unsigned char *regnext, (unsigned char *p ));
  183. _PROTOTYPE(STATIC unsigned char *regprop, (unsigned char *op ));
  184.  
  185. #ifdef STRCSPN
  186. _PROTOTYPE(STATIC int strcspn, (unsigned char *s1, unsigned char *s2 ));
  187. #endif
  188.  
  189. /*
  190.  - regcomp - compile a regular expression into internal code
  191.  *
  192.  * We can't allocate space until we know how big the compiled form will be,
  193.  * but we can't compile it (and thus know how big it is) until we've got a
  194.  * place to put the code.  So we cheat:  we compile it twice, once with code
  195.  * generation turned off and size counting turned on, and once "for real".
  196.  * This also means that we don't allocate space until we are sure that the
  197.  * thing really will compile successfully, and we never have to move the
  198.  * code and thus invalidate pointers into it.  (Note that it has to be in
  199.  * one piece because free() must be able to free it all.)
  200.  *
  201.  * Beware that the optimization-preparation code in here knows about some
  202.  * of the structure of the compiled regexp.
  203.  */
  204. regexp *
  205. regcomp(exp)
  206. char *exp;
  207. {
  208.     register regexp *r;
  209.     register unsigned char *scan;
  210.     register unsigned char *longest;
  211.     register int len;
  212.     int flags;
  213.  
  214.     if (exp == NULL)
  215.         FAIL("NULL argument");
  216.  
  217.     /* First pass: determine size, legality. */
  218.     regparse = exp;
  219.     regnpar = 1;
  220.     regsize = 0L;
  221.     regcode = ®dummy;
  222.     regc(MAGIC);
  223.     if (reg(0, &flags) == NULL)
  224.         return(NULL);
  225.  
  226.     /* Small enough for pointer-storage convention? */
  227.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  228.         FAIL("regexp too big");
  229.  
  230.     /* Allocate space. */
  231.     r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
  232.     if (r == NULL)
  233.         FAIL("out of space");
  234.  
  235.     /* Second pass: emit code. */
  236.     regparse = exp;
  237.     regnpar = 1;
  238.     regcode = r->program;
  239.     regc(MAGIC);
  240.     if (reg(0, &flags) == NULL)
  241.         return(NULL);
  242.  
  243.     /* Dig out information for optimizations. */
  244.     r->regstart = '\0';    /* Worst-case defaults. */
  245.     r->reganch = 0;
  246.     r->regmust = NULL;
  247.     r->regmlen = 0;
  248.     scan = r->program+1;            /* First BRANCH. */
  249.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  250.         scan = OPERAND(scan);
  251.  
  252.         /* Starting-point info. */
  253.         if (OP(scan) == EXACTLY)
  254.             r->regstart = *OPERAND(scan);
  255.         else if (OP(scan) == BOL)
  256.             r->reganch++;
  257.  
  258.         /*
  259.          * If there's something expensive in the r.e., find the
  260.          * longest literal string that must appear and make it the
  261.          * regmust.  Resolve ties in favor of later strings, since
  262.          * the regstart check works with the beginning of the r.e.
  263.          * and avoiding duplication strengthens checking.  Not a
  264.          * strong reason, but sufficient in the absence of others.
  265.          */
  266.         if (flags&SPSTART) {
  267.             longest = NULL;
  268.             len = 0;
  269.             for (; scan != NULL; scan = regnext(scan))
  270.                 if (OP(scan) == EXACTLY
  271.                 && strlen((char *)OPERAND(scan)) >= len) {
  272.                     longest = OPERAND(scan);
  273.                     len = strlen((char *)OPERAND(scan));
  274.                 }
  275.             r->regmust = longest;
  276.             r->regmlen = len;
  277.         }
  278.     }
  279.  
  280.     return(r);
  281. }
  282.  
  283. /*
  284.  - reg - regular expression, i.e. main body or parenthesized thing
  285.  *
  286.  * Caller must absorb opening parenthesis.
  287.  *
  288.  * Combining parenthesis handling with the base level of regular expression
  289.  * is a trifle forced, but the need to tie the tails of the branches to what
  290.  * follows makes it hard to avoid.
  291.  */
  292. STATIC unsigned char *
  293. reg(paren, flagp)
  294. int paren;            /* Parenthesized? */
  295. int *flagp;
  296. {
  297.     register unsigned char *ret;
  298.     register unsigned char *br;
  299.     register unsigned char *ender;
  300.     register int parno;
  301.     int flags;
  302.  
  303.     *flagp = HASWIDTH;    /* Tentatively. */
  304.  
  305.     /* Make an OPEN node, if parenthesized. */
  306.     if (paren) {
  307.         if (regnpar >= NSUBEXP)
  308.             FAIL("too many ()");
  309.         parno = regnpar;
  310.         regnpar++;
  311.         ret = regnode(OPEN+parno);
  312.     } else
  313.         ret = NULL;
  314.  
  315.     /* Pick up the branches, linking them together. */
  316.     br = regbranch(&flags);
  317.     if (br == NULL)
  318.         return(NULL);
  319.     if (ret != NULL)
  320.         regtail(ret, br);    /* OPEN -> first. */
  321.     else
  322.         ret = br;
  323.     if (!(flags&HASWIDTH))
  324.         *flagp &= ~HASWIDTH;
  325.     *flagp |= flags&SPSTART;
  326.     while (*regparse == '|') {
  327.         regparse++;
  328.         br = regbranch(&flags);
  329.         if (br == NULL)
  330.             return(NULL);
  331.         regtail(ret, br);    /* BRANCH -> BRANCH. */
  332.         if (!(flags&HASWIDTH))
  333.             *flagp &= ~HASWIDTH;
  334.         *flagp |= flags&SPSTART;
  335.     }
  336.  
  337.     /* Make a closing node, and hook it on the end. */
  338.     ender = regnode((paren) ? CLOSE+parno : END);    
  339.     regtail(ret, ender);
  340.  
  341.     /* Hook the tails of the branches to the closing node. */
  342.     for (br = ret; br != NULL; br = regnext(br))
  343.         regoptail(br, ender);
  344.  
  345.     /* Check for proper termination. */
  346.     if (paren && *regparse++ != ')') {
  347.         FAIL("unmatched ()");
  348.     } else if (!paren && *regparse != '\0') {
  349.         if (*regparse == ')') {
  350.             FAIL("unmatched ()");
  351.         } else
  352.             FAIL("junk on end");    /* "Can't happen". */
  353.         /* NOTREACHED */
  354.     }
  355.  
  356.     return(ret);
  357. }
  358.  
  359. /*
  360.  - regbranch - one alternative of an | operator
  361.  *
  362.  * Implements the concatenation operator.
  363.  */
  364. STATIC unsigned char *
  365. regbranch(flagp)
  366. int *flagp;
  367. {
  368.     register unsigned char *ret;
  369.     register unsigned char *chain;
  370.     register unsigned char *latest;
  371.     int flags;
  372.  
  373.     *flagp = WORST;        /* Tentatively. */
  374.  
  375.     ret = regnode(BRANCH);
  376.     chain = NULL;
  377.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  378.         latest = regpiece(&flags);
  379.         if (latest == NULL)
  380.             return(NULL);
  381.         *flagp |= flags&HASWIDTH;
  382.         if (chain == NULL)    /* First piece. */
  383.             *flagp |= flags&SPSTART;
  384.         else
  385.             regtail(chain, latest);
  386.         chain = latest;
  387.     }
  388.     if (chain == NULL)    /* Loop ran zero times. */
  389.         (void) regnode(NOTHING);
  390.  
  391.     return(ret);
  392. }
  393.  
  394. /*
  395.  - regpiece - something followed by possible [*+?]
  396.  *
  397.  * Note that the branching code sequences used for ? and the general cases
  398.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  399.  * both the endmarker for their branch list and the body of the last branch.
  400.  * It might seem that this node could be dispensed with entirely, but the
  401.  * endmarker role is not redundant.
  402.  */
  403. STATIC unsigned char *
  404. regpiece(flagp)
  405. int *flagp;
  406. {
  407.     register unsigned char *ret;
  408.     register unsigned char op;
  409.     register unsigned char *next;
  410.     int flags;
  411.  
  412.     ret = regatom(&flags);
  413.     if (ret == NULL)
  414.         return(NULL);
  415.  
  416.     op = *regparse;
  417.     if (!ISMULT(op)) {
  418.         *flagp = flags;
  419.         return(ret);
  420.     }
  421.  
  422.     if (!(flags&HASWIDTH) && op != '?')
  423.         FAIL("*+ operand could be empty");
  424.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  425.  
  426.     if (op == '*' && (flags&SIMPLE))
  427.         reginsert(STAR, ret);
  428.     else if (op == '*') {
  429.         /* Emit x* as (x&|), where & means "self". */
  430.         reginsert(BRANCH, ret);            /* Either x */
  431.         regoptail(ret, regnode(BACK));        /* and loop */
  432.         regoptail(ret, ret);            /* back */
  433.         regtail(ret, regnode(BRANCH));        /* or */
  434.         regtail(ret, regnode(NOTHING));        /* null. */
  435.     } else if (op == '+' && (flags&SIMPLE))
  436.         reginsert(PLUS, ret);
  437.     else if (op == '+') {
  438.         /* Emit x+ as x(&|), where & means "self". */
  439.         next = regnode(BRANCH);            /* Either */
  440.         regtail(ret, next);
  441.         regtail(regnode(BACK), ret);        /* loop back */
  442.         regtail(next, regnode(BRANCH));        /* or */
  443.         regtail(ret, regnode(NOTHING));        /* null. */
  444.     } else if (op == '?') {
  445.         /* Emit x? as (x|) */
  446.         reginsert(BRANCH, ret);            /* Either x */
  447.         regtail(ret, regnode(BRANCH));        /* or */
  448.         next = regnode(NOTHING);        /* null. */
  449.         regtail(ret, next);
  450.         regoptail(ret, next);
  451.     }
  452.     regparse++;
  453.     if (ISMULT(*regparse))
  454.         FAIL("nested *?+");
  455.  
  456.     return(ret);
  457. }
  458.  
  459. /*
  460.  - regatom - the lowest level
  461.  *
  462.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  463.  * it can turn them into a single node, which is smaller to store and
  464.  * faster to run.  Backslashed characters are exceptions, each becoming a
  465.  * separate node; the code is simpler that way and it's not worth fixing.
  466.  */
  467. STATIC unsigned char *
  468. regatom(flagp)
  469. int *flagp;
  470. {
  471.     register unsigned char *ret;
  472.     int flags;
  473.  
  474.     *flagp = WORST;        /* Tentatively. */
  475.  
  476.     switch (*regparse++) {
  477.     case '^':
  478.         ret = regnode(BOL);
  479.         break;
  480.     case '$':
  481.         ret = regnode(EOL);
  482.         break;
  483.     case '.':
  484.         ret = regnode(ANY);
  485.         *flagp |= HASWIDTH|SIMPLE;
  486.         break;
  487.     case '[': {
  488.             register int class;
  489.             register int classend;
  490.  
  491.             if (*regparse == '^') {    /* Complement of range. */
  492.                 ret = regnode(ANYBUT);
  493.                 regparse++;
  494.             } else
  495.                 ret = regnode(ANYOF);
  496.             if (*regparse == ']' || *regparse == '-')
  497.                 regc(*regparse++);
  498.             while (*regparse != '\0' && *regparse != ']') {
  499.                 if (*regparse == '-') {
  500.                     regparse++;
  501.                     if (*regparse == ']' || *regparse == '\0')
  502.                         regc('-');
  503.                     else {
  504.                         class = UCHARAT(regparse-2)+1;
  505.                         classend = UCHARAT(regparse);
  506.                         if (class > classend+1)
  507.                             FAIL("invalid [] range");
  508.                         for (; class <= classend; class++)
  509.                             regc(class);
  510.                         regparse++;
  511.                     }
  512.                 } else
  513.                     regc(*regparse++);
  514.             }
  515.             regc('\0');
  516.             if (*regparse != ']')
  517.                 FAIL("unmatched []");
  518.             regparse++;
  519.             *flagp |= HASWIDTH|SIMPLE;
  520.         }
  521.         break;
  522.     case '(':
  523.         ret = reg(1, &flags);
  524.         if (ret == NULL)
  525.             return(NULL);
  526.         *flagp |= flags&(HASWIDTH|SPSTART);
  527.         break;
  528.     case '\0':
  529.     case '|':
  530.     case ')':
  531.         FAIL("internal urp");    /* Supposed to be caught earlier. */
  532.         break;
  533.     case '?':
  534.     case '+':
  535.     case '*':
  536.         FAIL("?+* follows nothing");
  537.         break;
  538.     case '\\':
  539.         if (*regparse == '\0')
  540.             FAIL("trailing \\");
  541.         ret = regnode(EXACTLY);
  542.         regc(*regparse++);
  543.         regc('\0');
  544.         *flagp |= HASWIDTH|SIMPLE;
  545.         break;
  546.     default: {
  547.             register int len;
  548.             register unsigned char ender;
  549.  
  550.             regparse--;
  551. #ifdef    STRCSPN
  552.             len = strcspn(regparse, (unsigned char *)META);
  553. #else
  554.             len = strcspn((char *)regparse, META);
  555. #endif
  556.             if (len <= 0)
  557.                 FAIL("internal disaster");
  558.             ender = *(regparse+len);
  559.             if (len > 1 && ISMULT(ender))
  560.                 len--;        /* Back off clear of ?+* operand. */
  561.             *flagp |= HASWIDTH;
  562.             if (len == 1)
  563.                 *flagp |= SIMPLE;
  564.             ret = regnode(EXACTLY);
  565.             while (len > 0) {
  566.                 regc(*regparse++);
  567.                 len--;
  568.             }
  569.             regc('\0');
  570.         }
  571.         break;
  572.     }
  573.  
  574.     return(ret);
  575. }
  576.  
  577. /*
  578.  - regnode - emit a node
  579.  */
  580. STATIC unsigned char *            /* Location. */
  581. regnode(iop)
  582. int iop;
  583. {
  584.     register unsigned char *ret;
  585.     register unsigned char *ptr;
  586.     unsigned char op;
  587.  
  588.     op = (unsigned char) iop;
  589.     ret = regcode;
  590.     if (ret == ®dummy) {
  591.         regsize += 3;
  592.         return(ret);
  593.     }
  594.  
  595.     ptr = ret;
  596.     *ptr++ = op;
  597.     *ptr++ = '\0';        /* Null "next" pointer. */
  598.     *ptr++ = '\0';
  599.     regcode = ptr;
  600.  
  601.     return(ret);
  602. }
  603.  
  604. /*
  605.  - regc - emit (if appropriate) a byte of code
  606.  */
  607. STATIC void
  608. regc(ib)
  609. int ib;
  610. {
  611.     unsigned char b;
  612.  
  613.     b = (unsigned char) ib;
  614.     if (regcode != ®dummy)
  615.         *regcode++ = b;
  616.     else
  617.         regsize++;
  618. }
  619.  
  620. /*
  621.  - reginsert - insert an operator in front of already-emitted operand
  622.  *
  623.  * Means relocating the operand.
  624.  */
  625. STATIC void
  626. reginsert(iop, opnd)
  627. int iop;
  628. unsigned char *opnd;
  629. {
  630.     register unsigned char *src;
  631.     register unsigned char *dst;
  632.     register unsigned char *place;
  633.     unsigned char op;
  634.  
  635.     op = (unsigned char) iop;
  636.     if (regcode == ®dummy) {
  637.         regsize += 3;
  638.         return;
  639.     }
  640.  
  641.     src = regcode;
  642.     regcode += 3;
  643.     dst = regcode;
  644.     while (src > opnd)
  645.         *--dst = *--src;
  646.  
  647.     place = opnd;        /* Op node, where operand used to be. */
  648.     *place++ = op;
  649.     *place++ = '\0';
  650.     *place++ = '\0';
  651. }
  652.  
  653. /*
  654.  - regtail - set the next-pointer at the end of a node chain
  655.  */
  656. STATIC void
  657. regtail(p, val)
  658. unsigned char *p;
  659. unsigned char *val;
  660. {
  661.     register unsigned char *scan;
  662.     register unsigned char *temp;
  663.     register int offset;
  664.  
  665.     if (p == ®dummy)
  666.         return;
  667.  
  668.     /* Find last node. */
  669.     scan = p;
  670.     for (;;) {
  671.         temp = regnext(scan);
  672.         if (temp == NULL)
  673.             break;
  674.         scan = temp;
  675.     }
  676.  
  677.     if (OP(scan) == BACK)
  678.         offset = scan - val;
  679.     else
  680.         offset = val - scan;
  681.     *(scan+1) = (offset>>8)&0377;
  682.     *(scan+2) = offset&0377;
  683. }
  684.  
  685. /*
  686.  - regoptail - regtail on operand of first argument; nop if operandless
  687.  */
  688. STATIC void
  689. regoptail(p, val)
  690. unsigned char *p;
  691. unsigned char *val;
  692. {
  693.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  694.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  695.         return;
  696.     regtail(OPERAND(p), val);
  697. }
  698.  
  699. /*
  700.  * regexec and friends
  701.  */
  702.  
  703. /*
  704.  * Global work variables for regexec().
  705.  */
  706. STATIC unsigned char *reginput;        /* String-input pointer. */
  707. STATIC unsigned char *regbol;        /* Beginning of input, for ^ check. */
  708. STATIC unsigned char **regstartp;    /* Pointer to startp array. */
  709. STATIC unsigned char **regendp;        /* Ditto for endp. */
  710.  
  711. #ifdef DEBUG
  712. int regnarrate = 0;
  713. void regdump();
  714. STATIC unsigned char *regprop();
  715. #endif
  716.  
  717. /*
  718.  - regexec - match a regexp against a string
  719.  */
  720. int
  721. regexec(prog, string)
  722. register regexp *prog;
  723. register unsigned char *string;
  724. {
  725.     register unsigned char *s;
  726. #ifndef    STDLIB
  727.     extern char *strchr();
  728. #endif
  729.  
  730.     /* Be paranoid... */
  731.     if (prog == NULL || string == NULL) {
  732.         regerror("NULL parameter");
  733.         return(0);
  734.     }
  735.  
  736.     /* Check validity of program. */
  737.     if (UCHARAT(prog->program) != MAGIC) {
  738.         regerror("corrupted program");
  739.         return(0);
  740.     }
  741.  
  742.     /* If there is a "must appear" string, look for it. */
  743.     if (prog->regmust != NULL) {
  744.         s = string;
  745.         while ((s = (unsigned char *)strchr((char *)s,prog->regmust[0]))
  746.         != NULL) {
  747.             if (strncmp((char *)s, (char *)prog->regmust,
  748.                 prog->regmlen)
  749.             == 0)
  750.                 break;    /* Found it. */
  751.             s++;
  752.         }
  753.         if (s == NULL)    /* Not present. */
  754.             return(0);
  755.     }
  756.  
  757.     /* Mark beginning of line for ^ . */
  758.     regbol = string;
  759.  
  760.     /* Simplest case:  anchored match need be tried only once. */
  761.     if (prog->reganch)
  762.         return(regtry(prog, string));
  763.  
  764.     /* Messy cases:  unanchored match. */
  765.     s = string;
  766.     if (prog->regstart != '\0')
  767.         /* We know what char it must start with. */
  768.         while ((s = (unsigned char *)strchr((char *)s, prog->regstart))
  769.         != NULL) {
  770.             if (regtry(prog, s))
  771.                 return(1);
  772.             s++;
  773.         }
  774.     else
  775.         /* We don't -- general case. */
  776.         do {
  777.             if (regtry(prog, s))
  778.                 return(1);
  779.         } while (*s++ != '\0');
  780.  
  781.     /* Failure. */
  782.     return(0);
  783. }
  784.  
  785. /*
  786.  - regtry - try match at specific point
  787.  */
  788. STATIC int            /* 0 failure, 1 success */
  789. regtry(prog, string)
  790. regexp *prog;
  791. unsigned char *string;
  792. {
  793.     register int i;
  794.     register unsigned char **sp;
  795.     register unsigned char **ep;
  796.  
  797.     reginput = string;
  798.     regstartp = prog->startp;
  799.     regendp = prog->endp;
  800.  
  801.     sp = prog->startp;
  802.     ep = prog->endp;
  803.     for (i = NSUBEXP; i > 0; i--) {
  804.         *sp++ = NULL;
  805.         *ep++ = NULL;
  806.     }
  807.     if (regmatch(prog->program + 1)) {
  808.         prog->startp[0] = string;
  809.         prog->endp[0] = reginput;
  810.         return(1);
  811.     } else
  812.         return(0);
  813. }
  814.  
  815. /*
  816.  - regmatch - main matching routine
  817.  *
  818.  * Conceptually the strategy is simple:  check to see whether the current
  819.  * node matches, call self recursively to see whether the rest matches,
  820.  * and then act accordingly.  In practice we make some effort to avoid
  821.  * recursion, in particular by going through "ordinary" nodes (that don't
  822.  * need to know whether the rest of the match failed) by a loop instead of
  823.  * by recursion.
  824.  */
  825. STATIC int            /* 0 failure, 1 success */
  826. regmatch(prog)
  827. unsigned char *prog;
  828. {
  829.     register unsigned char *scan;    /* Current node. */
  830.     unsigned char *next;        /* Next node. */
  831. #ifndef    STDLIB
  832.     extern char *strchr();
  833. #endif
  834.  
  835.     scan = prog;
  836. #ifdef DEBUG
  837.     if (scan != NULL && regnarrate)
  838.         fprintf(stderr, "%s(\n", regprop(scan));
  839. #endif
  840.     while (scan != NULL) {
  841. #ifdef DEBUG
  842.         if (regnarrate)
  843.             fprintf(stderr, "%s...\n", regprop(scan));
  844. #endif
  845.         next = regnext(scan);
  846.  
  847.         switch (OP(scan)) {
  848.         case BOL:
  849.             if (reginput != regbol)
  850.                 return(0);
  851.             break;
  852.         case EOL:
  853.             if (*reginput != '\0')
  854.                 return(0);
  855.             break;
  856.         case ANY:
  857.             if (*reginput == '\0')
  858.                 return(0);
  859.             reginput++;
  860.             break;
  861.         case EXACTLY: {
  862.                 register int len;
  863.                 register unsigned char *opnd;
  864.  
  865.                 opnd = OPERAND(scan);
  866.                 /* Inline the first character, for speed. */
  867.                 if (*opnd != *reginput)
  868.                     return(0);
  869.                 len = strlen((char *)opnd);
  870.                 if (len > 1 && strncmp((char *)opnd,
  871.                    (char *)reginput, len)
  872.                 != 0)
  873.                     return(0);
  874.                 reginput += len;
  875.             }
  876.             break;
  877.         case ANYOF:
  878.             if (*reginput == '\0'
  879.             || strchr((char *)OPERAND(scan), *reginput) == NULL)
  880.                 return(0);
  881.             reginput++;
  882.             break;
  883.         case ANYBUT:
  884.             if (*reginput == '\0'
  885.             || strchr((char *)OPERAND(scan), *reginput) != NULL)
  886.                 return(0);
  887.             reginput++;
  888.             break;
  889.         case NOTHING:
  890.             break;
  891.         case BACK:
  892.             break;
  893.         case OPEN+1:
  894.         case OPEN+2:
  895.         case OPEN+3:
  896.         case OPEN+4:
  897.         case OPEN+5:
  898.         case OPEN+6:
  899.         case OPEN+7:
  900.         case OPEN+8:
  901.         case OPEN+9: {
  902.                 register int no;
  903.                 register unsigned char *save;
  904.  
  905.                 no = OP(scan) - OPEN;
  906.                 save = reginput;
  907.  
  908.                 if (regmatch(next)) {
  909.                     /*
  910.                      * Don't set startp if some later
  911.                      * invocation of the same parentheses
  912.                      * already has.
  913.                      */
  914.                     if (regstartp[no] == NULL)
  915.                         regstartp[no] = save;
  916.                     return(1);
  917.                 } else
  918.                     return(0);
  919.             }
  920.             break;
  921.         case CLOSE+1:
  922.         case CLOSE+2:
  923.         case CLOSE+3:
  924.         case CLOSE+4:
  925.         case CLOSE+5:
  926.         case CLOSE+6:
  927.         case CLOSE+7:
  928.         case CLOSE+8:
  929.         case CLOSE+9: {
  930.                 register int no;
  931.                 register unsigned char *save;
  932.  
  933.                 no = OP(scan) - CLOSE;
  934.                 save = reginput;
  935.  
  936.                 if (regmatch(next)) {
  937.                     /*
  938.                      * Don't set endp if some later
  939.                      * invocation of the same parentheses
  940.                      * already has.
  941.                      */
  942.                     if (regendp[no] == NULL)
  943.                         regendp[no] = save;
  944.                     return(1);
  945.                 } else
  946.                     return(0);
  947.             }
  948.             break;
  949.         case BRANCH: {
  950.                 register unsigned char *save;
  951.  
  952.                 if (OP(next) != BRANCH)        /* No choice. */
  953.                     next = OPERAND(scan);    /* Avoid recursion. */
  954.                 else {
  955.                     do {
  956.                         save = reginput;
  957.                         if (regmatch(OPERAND(scan)))
  958.                             return(1);
  959.                         reginput = save;
  960.                         scan = regnext(scan);
  961.                     } while (scan != NULL && OP(scan) == BRANCH);
  962.                     return(0);
  963.                     /* NOTREACHED */
  964.                 }
  965.             }
  966.             break;
  967.         case STAR:
  968.         case PLUS: {
  969.                 register unsigned char nextch;
  970.                 register int no;
  971.                 register unsigned char *save;
  972.                 register int min;
  973.  
  974.                 /*
  975.                  * Lookahead to avoid useless match attempts
  976.                  * when we know what character comes next.
  977.                  */
  978.                 nextch = '\0';
  979.                 if (OP(next) == EXACTLY)
  980.                     nextch = *OPERAND(next);
  981.                 min = (OP(scan) == STAR) ? 0 : 1;
  982.                 save = reginput;
  983.                 no = regrepeat(OPERAND(scan));
  984.                 while (no >= min) {
  985.                     /* If it could work, try it. */
  986.                     if (nextch == '\0' || *reginput == nextch)
  987.                         if (regmatch(next))
  988.                             return(1);
  989.                     /* Couldn't or didn't -- back up. */
  990.                     no--;
  991.                     reginput = save + no;
  992.                 }
  993.                 return(0);
  994.             }
  995.             break;
  996.         case END:
  997.             return(1);    /* Success! */
  998.             break;
  999.         default:
  1000.             regerror("memory corruption");
  1001.             return(0);
  1002.             break;
  1003.         }
  1004.  
  1005.         scan = next;
  1006.     }
  1007.  
  1008.     /*
  1009.      * We get here only if there's trouble -- normally "case END" is
  1010.      * the terminating point.
  1011.      */
  1012.     regerror("corrupted pointers");
  1013.     return(0);
  1014. }
  1015.  
  1016. /*
  1017.  - regrepeat - repeatedly match something simple, report how many
  1018.  */
  1019. STATIC int
  1020. regrepeat(p)
  1021. unsigned char *p;
  1022. {
  1023.     register int count = 0;
  1024.     register unsigned char *scan;
  1025.     register unsigned char *opnd;
  1026.  
  1027.     scan = reginput;
  1028.     opnd = OPERAND(p);
  1029.     switch (OP(p)) {
  1030.     case ANY:
  1031.         count = strlen((char *)scan);
  1032.         scan += count;
  1033.         break;
  1034.     case EXACTLY:
  1035.         while (*opnd == *scan) {
  1036.             count++;
  1037.             scan++;
  1038.         }
  1039.         break;
  1040.     case ANYOF:
  1041.         while (*scan != '\0' && strchr((char *)opnd, *scan) != NULL) {
  1042.             count++;
  1043.             scan++;
  1044.         }
  1045.         break;
  1046.     case ANYBUT:
  1047.         while (*scan != '\0' && strchr((char *)opnd, *scan) == NULL) {
  1048.             count++;
  1049.             scan++;
  1050.         }
  1051.         break;
  1052.     default:        /* Oh dear.  Called inappropriately. */
  1053.         regerror("internal foulup");
  1054.         count = 0;    /* Best compromise. */
  1055.         break;
  1056.     }
  1057.     reginput = scan;
  1058.  
  1059.     return(count);
  1060. }
  1061.  
  1062. /*
  1063.  - regnext - dig the "next" pointer out of a node
  1064.  */
  1065. STATIC unsigned char *
  1066. regnext(p)
  1067. register unsigned char *p;
  1068. {
  1069.     register int offset;
  1070.  
  1071.     if (p == ®dummy)
  1072.         return(NULL);
  1073.  
  1074.     offset = NEXT(p);
  1075.     if (offset == 0)
  1076.         return(NULL);
  1077.  
  1078.     if (OP(p) == BACK)
  1079.         return(p-offset);
  1080.     else
  1081.         return(p+offset);
  1082. }
  1083.  
  1084. #ifdef DEBUG
  1085.  
  1086. STATIC unsigned char *regprop();
  1087.  
  1088. /*
  1089.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1090.  */
  1091. void
  1092. regdump(r)
  1093. regexp *r;
  1094. {
  1095.     register unsigned char *s;
  1096.     register unsigned char op = EXACTLY;    /* Arbitrary non-END op. */
  1097.     register unsigned char *next;
  1098.     extern char *strchr();
  1099.  
  1100.  
  1101.     s = r->program + 1;
  1102.     while (op != END) {    /* While that wasn't END last time... */
  1103.         op = OP(s);
  1104.         printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1105.         next = regnext(s);
  1106.         if (next == NULL)        /* Next ptr. */
  1107.             printf("(0)");
  1108.         else 
  1109.             printf("(%d)", (s-r->program)+(next-s));
  1110.         s += 3;
  1111.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1112.             /* Literal string, where present. */
  1113.             while (*s != '\0') {
  1114.                 putchar(*s);
  1115.                 s++;
  1116.             }
  1117.             s++;
  1118.         }
  1119.         putchar('\n');
  1120.     }
  1121.  
  1122.     /* Header fields of interest. */
  1123.     if (r->regstart != '\0')
  1124.         printf("start `%c' ", r->regstart);
  1125.     if (r->reganch)
  1126.         printf("anchored ");
  1127.     if (r->regmust != NULL)
  1128.         printf("must have \"%s\"", r->regmust);
  1129.     printf("\n");
  1130. }
  1131.  
  1132. /*
  1133.  - regprop - printable representation of opcode
  1134.  */
  1135. STATIC unsigned char *
  1136. regprop(op)
  1137. unsigned char *op;
  1138. {
  1139.     register unsigned char *p;
  1140.     STATIC unsigned char buf[50];
  1141.  
  1142.     (void) strcpy(buf, ":");
  1143.  
  1144.     switch (OP(op)) {
  1145.     case BOL:
  1146.         p = "BOL";
  1147.         break;
  1148.     case EOL:
  1149.         p = "EOL";
  1150.         break;
  1151.     case ANY:
  1152.         p = "ANY";
  1153.         break;
  1154.     case ANYOF:
  1155.         p = "ANYOF";
  1156.         break;
  1157.     case ANYBUT:
  1158.         p = "ANYBUT";
  1159.         break;
  1160.     case BRANCH:
  1161.         p = "BRANCH";
  1162.         break;
  1163.     case EXACTLY:
  1164.         p = "EXACTLY";
  1165.         break;
  1166.     case NOTHING:
  1167.         p = "NOTHING";
  1168.         break;
  1169.     case BACK:
  1170.         p = "BACK";
  1171.         break;
  1172.     case END:
  1173.         p = "END";
  1174.         break;
  1175.     case OPEN+1:
  1176.     case OPEN+2:
  1177.     case OPEN+3:
  1178.     case OPEN+4:
  1179.     case OPEN+5:
  1180.     case OPEN+6:
  1181.     case OPEN+7:
  1182.     case OPEN+8:
  1183.     case OPEN+9:
  1184.         sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1185.         p = NULL;
  1186.         break;
  1187.     case CLOSE+1:
  1188.     case CLOSE+2:
  1189.     case CLOSE+3:
  1190.     case CLOSE+4:
  1191.     case CLOSE+5:
  1192.     case CLOSE+6:
  1193.     case CLOSE+7:
  1194.     case CLOSE+8:
  1195.     case CLOSE+9:
  1196.         sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1197.         p = NULL;
  1198.         break;
  1199.     case STAR:
  1200.         p = "STAR";
  1201.         break;
  1202.     case PLUS:
  1203.         p = "PLUS";
  1204.         break;
  1205.     default:
  1206.         regerror("corrupted opcode");
  1207.         break;
  1208.     }
  1209.     if (p != NULL)
  1210.         (void) strcat(buf, p);
  1211.     return(buf);
  1212. }
  1213. #endif
  1214.  
  1215. /*
  1216.  * The following is provided for those people who do not have strcspn() in
  1217.  * their C libraries.  They should get off their butts and do something
  1218.  * about it; at least one public-domain implementation of those (highly
  1219.  * useful) string routines has been published on Usenet.
  1220.  */
  1221. #ifdef STRCSPN
  1222. /*
  1223.  * strcspn - find length of initial segment of s1 consisting entirely
  1224.  * of characters not from s2
  1225.  */
  1226.  
  1227. STATIC int
  1228. strcspn(s1, s2)
  1229. unsigned char *s1;
  1230. unsigned char *s2;
  1231. {
  1232.     register unsigned char *scan1;
  1233.     register unsigned char *scan2;
  1234.     register int count;
  1235.  
  1236.     count = 0;
  1237.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1238.         for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1239.             if (*scan1 == *scan2++)
  1240.                 return(count);
  1241.         count++;
  1242.     }
  1243.     return(count);
  1244. }
  1245. #endif
  1246.