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