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