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