home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / std_unix / pax / 6 / regexp.c
Encoding:
C/C++ Source or Header  |  1989-01-07  |  29.9 KB  |  1,322 lines

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