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