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