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